-
A Potential Recoiling Supermassive Black Hole CXO J101527.2+625911
Authors:
D. -C. Kim,
Ilsang Yoon,
G. C. Privon,
A. S. Evans,
D. Harvey,
S. Stierwalt,
Ji Hoon Kim
Abstract:
We have carried out a systematic search for recoiling supermassive black holes (rSMBH) using the Chandra Source and SDSS Cross Matched Catalog. From the survey, we have detected a potential rSMBH, 'CXO J101527.2+625911' at z=0.3504. The CXO J101527.2+625911 has a spatially offset (1.26$\pm$0.05 kpc) active SMBH and kinematically offset broad emission lines (175$\pm$25 km s$^{\rm -1}$ relative to s…
▽ More
We have carried out a systematic search for recoiling supermassive black holes (rSMBH) using the Chandra Source and SDSS Cross Matched Catalog. From the survey, we have detected a potential rSMBH, 'CXO J101527.2+625911' at z=0.3504. The CXO J101527.2+625911 has a spatially offset (1.26$\pm$0.05 kpc) active SMBH and kinematically offset broad emission lines (175$\pm$25 km s$^{\rm -1}$ relative to systemic velocity). The observed spatial and velocity offsets suggest this galaxy could be a rSMBH, but we also have considered a possibility of dual SMBH scenario. The column density towards the galaxy center was found to be Compton thin, but no X-ray source was detected. The non-detection of the X-ray source in the nucleus suggests either there is no obscured actively accreting SMBH, or there exists an SMBH but has a low accretion rate (i.e. low-luminosity AGN (LLAGN)). The possibility of the LLAGN was investigated and found to be unlikely based on the H$α$ luminosity, radio power, and kinematic arguments. This, along with the null detection of X-ray source in the nucleus supports our hypothesis that the CXO J101527.2+625911 is a rSMBH. Our GALFIT analysis shows the host galaxy to be a bulge-dominated elliptical. The weak morphological disturbance and small spatial and velocity offsets suggest that CXO J101527.2+625911 could be in the final stage of merging process and about to turn into a normal elliptical galaxy.
△ Less
Submitted 18 April, 2017;
originally announced April 2017.
-
A detection of wobbling Brightest Cluster Galaxies within massive galaxy clusters
Authors:
David Harvey,
F. Courbin,
J. P. Kneib,
Ian G. McCarthy
Abstract:
A striking signal of dark matter beyond the standard model is the existence of cores in the centre of galaxy clusters. Recent simulations predict that a Brightest Cluster Galaxy (BCG) inside a cored galaxy cluster will exhibit residual wobbling due to previous major mergers, long after the relaxation of the overall cluster. This phenomenon is absent with standard cold dark matter where a cuspy den…
▽ More
A striking signal of dark matter beyond the standard model is the existence of cores in the centre of galaxy clusters. Recent simulations predict that a Brightest Cluster Galaxy (BCG) inside a cored galaxy cluster will exhibit residual wobbling due to previous major mergers, long after the relaxation of the overall cluster. This phenomenon is absent with standard cold dark matter where a cuspy density profile keeps a BCG tightly bound at the centre. We test this hypothesis using cosmological simulations and deep observations of 10 galaxy clusters acting as strong gravitational lenses. Modelling the BCG wobble as a simple harmonic oscillator, we measure the wobble amplitude, $A_w$, in the BAHAMAS suite of cosmological hydrodynamical simulations, finding an upper limit for the CDM paradigm of $A_w < 2$kpc at the 95% confidence limit. We carry out the same test on the data finding a non-zero amplitude of $A_w=11.82^{+7.3}_{-3.0}$kpc, with the observations dis-favouring $A_w = 0$ at the 3$σ$ confidence level. This detection of BCG wobbling is evidence for a dark matter core at the heart of galaxy clusters. It also shows that strong lensing models of clusters cannot assume that the BCG is exactly coincident with the large scale halo. While our small sample of galaxy clusters already indicates a non-zero $A_w$, with larger surveys, e.g. Euclid, we will be able to not only to confirm the effect but also to use it to determine whether or not the wobbling finds its origin in new fundamental physics or astrophysical process.
△ Less
Submitted 9 August, 2017; v1 submitted 21 March, 2017;
originally announced March 2017.
-
Faster truncated integer multiplication
Authors:
David Harvey
Abstract:
We present new algorithms for computing the low $n$ bits or the high $n$ bits of the product of two $n$-bit integers. We show that these problems may be solved in asymptotically 75% of the time required to compute the full $2n$-bit product, assuming that the underlying integer multiplication algorithm relies on computing cyclic convolutions of real sequences.
We present new algorithms for computing the low $n$ bits or the high $n$ bits of the product of two $n$-bit integers. We show that these problems may be solved in asymptotically 75% of the time required to compute the full $2n$-bit product, assuming that the underlying integer multiplication algorithm relies on computing cyclic convolutions of real sequences.
△ Less
Submitted 1 August, 2023; v1 submitted 2 March, 2017;
originally announced March 2017.
-
A test for skewed distributions of dark matter and a possible detection in galaxy cluster Abell 3827
Authors:
Peter Taylor,
Richard Massey,
Mathilde Jauzac,
Frédéric Courbin,
David Harvey,
Rémy Joseph,
Andrew Robertson
Abstract:
Simulations of self-interacting dark matter (SIDM) predict that dark matter should lag behind galaxies during a collision. If the interaction is mediated by a high-mass force carrier, the distribution of dark matter can also develop asymmetric dark matter tails. To search for this asymmetry, we compute the gravitational lensing properties of a mass distribution with a free {\em skewness} parameter…
▽ More
Simulations of self-interacting dark matter (SIDM) predict that dark matter should lag behind galaxies during a collision. If the interaction is mediated by a high-mass force carrier, the distribution of dark matter can also develop asymmetric dark matter tails. To search for this asymmetry, we compute the gravitational lensing properties of a mass distribution with a free {\em skewness} parameter. We apply this to the dark matter around the four central galaxies in cluster Abell~3827. In the galaxy whose dark matter peak has previously been found to be offset, we tentatively measure a skewness $s=0.23^{+0.05}_{-0.22}$ in the same direction as the peak offset. Our method may be useful in future gravitational lensing analyses of colliding galaxy clusters and merging galaxies.
△ Less
Submitted 13 April, 2017; v1 submitted 16 January, 2017;
originally announced January 2017.
-
Faster integer multiplication using plain vanilla FFT primes
Authors:
David Harvey,
Joris van der Hoeven
Abstract:
Assuming a conjectural upper bound for the least prime in an arithmetic progression, we show that n-bit integers may be multiplied in O(n log n 4^(log^* n)) bit operations.
Assuming a conjectural upper bound for the least prime in an arithmetic progression, we show that n-bit integers may be multiplied in O(n log n 4^(log^* n)) bit operations.
△ Less
Submitted 16 October, 2017; v1 submitted 21 November, 2016;
originally announced November 2016.
-
Abell 2744: Too much substructure for Lambda CDM?
Authors:
J. Schwinn,
M. Jauzac,
C. M. Baugh,
M. Bartelmann,
D. Eckert,
D. Harvey,
P. Natarajan,
R. Massey
Abstract:
The massive substructures found in Abell 2744 by Jauzac et al. (2016) present a challenge to the cold dark matter paradigm due to their number and proximity to the cluster centre. We use one of the biggest N-body simulations, the Millennium XXL, to investigate the substructure in a large sample of massive dark matter haloes. A range of effects which influence the comparison with the observations i…
▽ More
The massive substructures found in Abell 2744 by Jauzac et al. (2016) present a challenge to the cold dark matter paradigm due to their number and proximity to the cluster centre. We use one of the biggest N-body simulations, the Millennium XXL, to investigate the substructure in a large sample of massive dark matter haloes. A range of effects which influence the comparison with the observations is considered, extending the preliminary evaluation carried out by Jauzac et al. (2016). There are many tens of haloes in the simulation with a total mass comparable with or larger than that of Abell 2744. However, we find no haloes with a number and distribution of massive substructures (> 5 10^13 Msun) that is close to that inferred from the observations of Abell 2744. The application of extreme value statistics suggests that we would need a simulation of at least ten times the volume of the Millennium XXL to find a single dark matter halo with a similar internal structure to Abell 2744. Explaining the distribution of massive substructures in clusters is a new hurdle for hierarchical models to negotiate, which is not weakened by appeals to baryonic physics or uncertainty over the nature of the dark matter particle.
△ Less
Submitted 2 February, 2017; v1 submitted 8 November, 2016;
originally announced November 2016.
-
Looking for dark matter trails in colliding galaxy clusters
Authors:
David Harvey,
Andrew Robertson,
Richard Massey,
Jean-Paul Kneib
Abstract:
If dark matter interacts, even weakly, via non-gravitational forces, simulations predict that it will be preferentially scattered towards the trailing edge of the halo during collisions between galaxy clusters. This will temporarily create a non-symmetric mass profile, with a trailing over-density along the direction of motion. To test this hypothesis, we fit (and subtract) symmetric halos to the…
▽ More
If dark matter interacts, even weakly, via non-gravitational forces, simulations predict that it will be preferentially scattered towards the trailing edge of the halo during collisions between galaxy clusters. This will temporarily create a non-symmetric mass profile, with a trailing over-density along the direction of motion. To test this hypothesis, we fit (and subtract) symmetric halos to the weak gravitational data of 72 merging galaxy clusters observed with the Hubble Space Telescope. We convert the shear directly into excess κ and project in to a one dimensional profile. We generate numerical simulations and find that the one dimensional profile is well described with simple Gaussian approximations. We detect the weak lensing signal of trailing gas at a 4σ confidence, finding a mean gas fraction of Mgas/Mdm = 0.13 +/- 0.035. We find no evidence for scattered dark matter particles with a estimated scattering fraction of f = 0.03 +/- 0.05. Finally we find that if we can reduce the statistical error on the positional estimate of a single dark matter halo to <2.5", then we will be able to detect a scattering fraction of 10% at the 3σ level with current surveys. This poten- tially interesting new method can provide an important independent test for other complimentary studies of the self-interaction cross-section of dark matter.
△ Less
Submitted 17 October, 2016;
originally announced October 2016.
-
Mode-locked Yb-doped fiber laser emitting broadband pulses at ultra-low repetition rates
Authors:
Patrick Bowen,
Miro Erkintalo,
Richard Provo,
John D. Harvey,
Neil G. R. Broderick
Abstract:
We report on an environmentally stable, Yb-doped, all-normal dispersion, mode-locked fibre laser that is capable of creating broadband pulses with ultra-low repetition rates. Specifically, through careful positioning of fibre sections in an all-PM-fibre cavity mode-locked with a nonlinear amplifying loop mirror, we achieve stable pulse trains with repetition rates as low as 506 kHz. The pulses hav…
▽ More
We report on an environmentally stable, Yb-doped, all-normal dispersion, mode-locked fibre laser that is capable of creating broadband pulses with ultra-low repetition rates. Specifically, through careful positioning of fibre sections in an all-PM-fibre cavity mode-locked with a nonlinear amplifying loop mirror, we achieve stable pulse trains with repetition rates as low as 506 kHz. The pulses have several nanojules of energy and are compressible down to ultrashort (< 500 fs) durations.
△ Less
Submitted 13 September, 2016;
originally announced September 2016.
-
The Extraordinary Amount of Substructure in the Hubble Frontier Fields Cluster Abell 2744
Authors:
M. Jauzac,
D. Eckert,
J. Schwinn,
D. Harvey,
C. M. Baugh,
A. Robertson,
S. Bose,
R. Massey,
M. Owers,
H. Ebeling,
H. Y. Shan,
E. Jullo,
J. -P. Kneib,
J. Richard,
H. Atek,
B. Clément,
E. Egami,
H. Israel,
K. Knowles,
M. Limousin,
P. Natarajan,
M. Rexroth,
P. Taylor,
C. Tchernin
Abstract:
We present a joint optical/X-ray analysis of the massive galaxy cluster Abell 2744 (z=0.308). Our strong- and weak-lensing analysis within the central region of the cluster, i.e., at R<1Mpc from the brightest cluster galaxy, reveals eight substructures, including the main core. All of these dark-matter halos are detected with a significance of at least 5sigma and feature masses ranging from 0.5 to…
▽ More
We present a joint optical/X-ray analysis of the massive galaxy cluster Abell 2744 (z=0.308). Our strong- and weak-lensing analysis within the central region of the cluster, i.e., at R<1Mpc from the brightest cluster galaxy, reveals eight substructures, including the main core. All of these dark-matter halos are detected with a significance of at least 5sigma and feature masses ranging from 0.5 to 1.4x10^{14}Msun within R<150kpc. Merten et al. (2011) and Medezinski et al. (2016) substructures are also detected by us. We measure a slightly higher mass for the main core component than reported previously and attribute the discrepancy to the inclusion of our tightly constrained strong-lensing mass model built on Hubble Frontier Fields data. X-ray data obtained by XMM-Newton reveal four remnant cores, one of them a new detection, and three shocks. Unlike Merten et al. (2011), we find all cores to have both dark and luminous counterparts. A comparison with clusters of similar mass in the MXXL simulations yields no objects with as many massive substructures as observed in Abell 2744, confirming that Abell 2744 is an extreme system. We stress that these properties still do not constitute a challenge to $Λ$CDM, as caveats apply to both the simulation and the observations: for instance, the projected mass measurements from gravitational lensing and the limited resolution of the sub-haloes finders. We discuss implications of Abell 2744 for the plausibility of different dark-matter candidates and, finally, measure a new upper limit on the self-interaction cross-section of dark matter of sigma_{DM}<1.28cm2/g(68\% CL), in good agreement with previous results from Harvey et al. (2015).
△ Less
Submitted 14 June, 2016;
originally announced June 2016.
-
Computing L-series of geometrically hyperelliptic curves of genus three
Authors:
David Harvey,
Maike Massierer,
Andrew V. Sutherland
Abstract:
Let C/Q be a curve of genus three, given as a double cover of a plane conic. Such a curve is hyperelliptic over the algebraic closure of Q, but may not have a hyperelliptic model of the usual form over Q. We describe an algorithm that computes the local zeta functions of C at all odd primes of good reduction up to a prescribed bound N. The algorithm relies on an adaptation of the "accumulating rem…
▽ More
Let C/Q be a curve of genus three, given as a double cover of a plane conic. Such a curve is hyperelliptic over the algebraic closure of Q, but may not have a hyperelliptic model of the usual form over Q. We describe an algorithm that computes the local zeta functions of C at all odd primes of good reduction up to a prescribed bound N. The algorithm relies on an adaptation of the "accumulating remainder tree" to matrices with entries in a quadratic field. We report on an implementation, and compare its performance to previous algorithms for the ordinary hyperelliptic case.
△ Less
Submitted 16 May, 2016;
originally announced May 2016.
-
Irregular primes to two billion
Authors:
William Hart,
David Harvey,
Wilson Ong
Abstract:
We compute all irregular primes less than 2^31 = 2 147 483 648. We verify the Kummer-Vandiver conjecture for each of these primes, and we check that the p-part of the class group of Q(zeta_p) has the simplest possible structure consistent with the index of irregularity of p. Our method for computing the irregular indices saves a constant factor in time relative to previous methods, by adapting Rad…
▽ More
We compute all irregular primes less than 2^31 = 2 147 483 648. We verify the Kummer-Vandiver conjecture for each of these primes, and we check that the p-part of the class group of Q(zeta_p) has the simplest possible structure consistent with the index of irregularity of p. Our method for computing the irregular indices saves a constant factor in time relative to previous methods, by adapting Rader's algorithm for evaluating discrete Fourier transforms.
△ Less
Submitted 8 May, 2016;
originally announced May 2016.
-
Recurrent Network Models Of Sequence Generation And Memory
Authors:
Kanaka Rajan,
Christopher D Harvey,
David W Tank
Abstract:
Sequential activation of neurons is a common feature of network activity during a variety of behaviors, including working memory and decision making. Previous network models for sequences and memory emphasized specialized architectures in which a principled mechanism is pre-wired into their connectivity. Here we demonstrate that, starting from random connectivity and modifying a small fraction of…
▽ More
Sequential activation of neurons is a common feature of network activity during a variety of behaviors, including working memory and decision making. Previous network models for sequences and memory emphasized specialized architectures in which a principled mechanism is pre-wired into their connectivity. Here we demonstrate that, starting from random connectivity and modifying a small fraction of connections, a largely disordered recur- rent network can produce sequences and implement working memory efficiently. We use this process, called Partial In-Network Training (PINning), to model and match cellular resolution imaging data from the posterior parietal cortex during a virtual memory- guided two-alternative forced-choice task. Analysis of the connectivity reveals that sequences propagate by the cooperation between recurrent synaptic interactions and external inputs, rather than through feedforward or asymmetric connections. Together our results suggest that neural sequences may emerge through learning from largely unstructured network architectures.
△ Less
Submitted 14 March, 2016;
originally announced March 2016.
-
Systematic or Signal? How dark matter misalignments can bias strong lensing models of galaxy clusters
Authors:
David Harvey,
Jean-Paul Kneib,
Mathilde Jauzac
Abstract:
We explore how assuming that mass traces light in strong gravitational lensing models can lead to systematic errors in the predicted position of multiple images. Using a model based on the galaxy cluster MACSJ0416 (z = 0.397) from the Hubble Frontier Fields, we split each galactic halo into a baryonic and dark matter component. We then shift the dark matter halo such that it no longer aligns with…
▽ More
We explore how assuming that mass traces light in strong gravitational lensing models can lead to systematic errors in the predicted position of multiple images. Using a model based on the galaxy cluster MACSJ0416 (z = 0.397) from the Hubble Frontier Fields, we split each galactic halo into a baryonic and dark matter component. We then shift the dark matter halo such that it no longer aligns with the baryonic halo and investigate how this affects the resulting position of multiple images. We find for physically motivated misalignments in dark halo position, ellipticity, position angle and density profile, that multiple images can move on average by more than 0.2" with individual images moving greater than 1". We finally estimate the full error induced by assuming that light traces mass and find that this assumption leads to an expected RMS error of 0.5", almost the entire error budget observed in the Frontier Fields. Given the large potential contribution from the assumption that light traces mass to the error budget in mass reconstructions, we predict that it should be possible to make a first significant detection and characterisation of dark halo misalignments in the Hubble Frontier Fields with strong lensing. Finally, we find that it may be possible to detect ~1kpc offsets between dark matter and baryons, the smoking gun for self-interacting dark matter, should the correct alignment of multiple images be observed.
△ Less
Submitted 25 January, 2016;
originally announced January 2016.
-
A Multivariate Cure Model for Left- and Right-Censored Data with Application to Colorectal Cancer Screening Patterns
Authors:
Yolanda Hagar,
Danielle Harvey,
Laurel Beckett
Abstract:
We develop a multivariate cure survival model to estimate lifetime patterns of colorectal cancer screening. Screening data cover long periods of time, with sparse observations for each person. Some events may occur before the study begins or after the study ends, so the data are both left- and right-censored, and some individuals are never screened (the "cured" population). We propose a multivaria…
▽ More
We develop a multivariate cure survival model to estimate lifetime patterns of colorectal cancer screening. Screening data cover long periods of time, with sparse observations for each person. Some events may occur before the study begins or after the study ends, so the data are both left- and right-censored, and some individuals are never screened (the "cured" population). We propose a multivariate parametric cure model that can be used with left- and right-censored data. Our model allows for the estimation of the time to screening as well as the average number of times individuals will be screened. We calculate likelihood functions based on the observations for each subject using a distribution that accounts for within-subject correlation, and estimate parameters using Markov Chain Monte Carlo methods. We apply our methods to the estimation of lifetime colorectal cancer screening behavior in the SEER-Medicare data set.
△ Less
Submitted 15 September, 2015;
originally announced September 2015.
-
Average degree conditions forcing a minor
Authors:
Daniel J. Harvey,
David R. Wood
Abstract:
Mader first proved that high average degree forces a given graph as a minor. Often motivated by Hadwiger's Conjecture, much research has focused on the average degree required to force a complete graph as a minor. Subsequently, various authors have consider the average degree required to force an arbitrary graph $H$ as a minor. Here, we strengthen (under certain conditions) a recent result by Reed…
▽ More
Mader first proved that high average degree forces a given graph as a minor. Often motivated by Hadwiger's Conjecture, much research has focused on the average degree required to force a complete graph as a minor. Subsequently, various authors have consider the average degree required to force an arbitrary graph $H$ as a minor. Here, we strengthen (under certain conditions) a recent result by Reed and Wood, giving better bounds on the average degree required to force an $H$-minor when $H$ is a sparse graph with many high degree vertices. This solves an open problem of Reed and Wood, and also generalises (to within a constant factor) known results when $H$ is an unbalanced complete bipartite graph.
△ Less
Submitted 5 June, 2015;
originally announced June 2015.
-
A weak lensing comparability study of galaxy mergers that host AGNs
Authors:
David Harvey,
Frederic Courbin
Abstract:
We compared the total mass density profiles of three different types of galaxies using weak gravitational lensing: (i) 29 galaxies that host quasars at z~0.32 that are in a post-starburst (PSQ) phase with high star formation indicating recent merger activity, (ii) 22 large elliptical galaxies from the SLACS sample that do not host a quasar at z~0.23, and (iii) 17 galaxies that host moderately lumi…
▽ More
We compared the total mass density profiles of three different types of galaxies using weak gravitational lensing: (i) 29 galaxies that host quasars at z~0.32 that are in a post-starburst (PSQ) phase with high star formation indicating recent merger activity, (ii) 22 large elliptical galaxies from the SLACS sample that do not host a quasar at z~0.23, and (iii) 17 galaxies that host moderately luminous quasars at z~0.36 powered by disk instabilities, but with no intense star formation. On an initial test we found no evidence for a connection between the merger state of a galaxy and the profile of the halo, with the PSQ profile comparable to that of the other two samples and consistent with the Leauthaud et al. (2014) study of moderately luminous quasars in COSMOS. Given the compatibility of the two quasar samples, we combined these and found no evidence for any connection between black hole activity and the dark matter halo. All three mass profiles remained compatible with isothermality given the present data.
△ Less
Submitted 14 May, 2015;
originally announced May 2015.
-
The behaviour of dark matter associated with 4 bright cluster galaxies in the 10kpc core of Abell 3827
Authors:
Richard Massey,
Liliya Williams,
Renske Smit,
Mark Swinbank,
Thomas Kitching,
David Harvey,
Mathilde Jauzac,
Holger Israel,
Douglas Clowe,
Alastair Edge,
Matt Hilton,
Eric Jullo,
Adrienne Leonard,
Jori Liesenborgs,
Julian Merten,
Irshad Mohammed,
Daisuke Nagai,
Johan Richard,
Andrew Robertson,
Prasenjit Saha,
Rebecca Santana,
John Stott,
Eric Tittley
Abstract:
Galaxy cluster Abell 3827 hosts the stellar remnants of four almost equally bright elliptical galaxies within a core of radius 10kpc. Such corrugation of the stellar distribution is very rare, and suggests recent formation by several simultaneous mergers. We map the distribution of associated dark matter, using new Hubble Space Telescope imaging and VLT/MUSE integral field spectroscopy of a gravit…
▽ More
Galaxy cluster Abell 3827 hosts the stellar remnants of four almost equally bright elliptical galaxies within a core of radius 10kpc. Such corrugation of the stellar distribution is very rare, and suggests recent formation by several simultaneous mergers. We map the distribution of associated dark matter, using new Hubble Space Telescope imaging and VLT/MUSE integral field spectroscopy of a gravitationally lensed system threaded through the cluster core. We find that each of the central galaxies retains a dark matter halo, but that (at least) one of these is spatially offset from its stars. The best-constrained offset is 1.62+/-0.48kpc, where the 68% confidence limit includes both statistical error and systematic biases in mass modelling. Such offsets are not seen in field galaxies, but are predicted during the long infall to a cluster, if dark matter self-interactions generate an extra drag force. With such a small physical separation, it is difficult to definitively rule out astrophysical effects operating exclusively in dense cluster core environments - but if interpreted solely as evidence for self-interacting dark matter, this offset implies a cross-section sigma/m=(1.7+/-0.7)x10^{-4}cm^2/g x (t/10^9yrs)^{-2}, where t is the infall duration.
△ Less
Submitted 13 April, 2015;
originally announced April 2015.
-
The non-gravitational interactions of dark matter in colliding galaxy clusters
Authors:
David Harvey,
Richard Massey,
Thomas Kitching,
Andy Taylor,
Eric Tittley
Abstract:
Collisions between galaxy clusters provide a test of the non-gravitational forces acting on dark matter. Dark matter's lack of deceleration in the `bullet cluster collision' constrained its self-interaction cross-section σ_DM/m < 1.25cm2/g (68% confidence limit) for long-ranged forces. Using the Chandra and Hubble Space Telescopes we have now observed 72 collisions, including both `major' and `min…
▽ More
Collisions between galaxy clusters provide a test of the non-gravitational forces acting on dark matter. Dark matter's lack of deceleration in the `bullet cluster collision' constrained its self-interaction cross-section σ_DM/m < 1.25cm2/g (68% confidence limit) for long-ranged forces. Using the Chandra and Hubble Space Telescopes we have now observed 72 collisions, including both `major' and `minor' mergers. Combining these measurements statistically, we detect the existence of dark mass at 7.6σsignificance. The position of the dark mass has remained closely aligned within 5.8+/-8.2 kpc of associated stars: implying a self-interaction cross-section σ_DM/m < 0.47 cm2/g (95% CL) and disfavoring some proposed extensions to the standard model.
△ Less
Submitted 13 April, 2015; v1 submitted 26 March, 2015;
originally announced March 2015.
-
Cycles of given size in a dense graph
Authors:
Daniel J. Harvey,
David R. Wood
Abstract:
We generalise a result of Corrádi and Hajnal and show that every graph with average degree at least $\tfrac{4}{3}kr$ contains $k$ vertex disjoint cycles, each of order at least $r$, as long as $k \geq 6$. This bound is sharp when $r=3$.
We generalise a result of Corrádi and Hajnal and show that every graph with average degree at least $\tfrac{4}{3}kr$ contains $k$ vertex disjoint cycles, each of order at least $r$, as long as $k \geq 6$. This bound is sharp when $r=3$.
△ Less
Submitted 12 February, 2015;
originally announced February 2015.
-
Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time, II
Authors:
David Harvey,
Andrew V. Sutherland
Abstract:
We present an algorithm that computes the Hasse-Witt matrix of given hyperelliptic curve over Q at all primes of good reduction up to a given bound N. It is simpler and faster than the previous algorithm developed by the authors.
We present an algorithm that computes the Hasse-Witt matrix of given hyperelliptic curve over Q at all primes of good reduction up to a given bound N. It is simpler and faster than the previous algorithm developed by the authors.
△ Less
Submitted 20 October, 2014;
originally announced October 2014.
-
The Treewidth of Line Graphs
Authors:
Daniel J. Harvey,
David R. Wood
Abstract:
The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph $G$ is equivalent to determining the minimum vertex congestion of an embedding of $G$ into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and av…
▽ More
The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph $G$ is equivalent to determining the minimum vertex congestion of an embedding of $G$ into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of $G$. These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth.
△ Less
Submitted 23 September, 2014;
originally announced September 2014.
-
Faster polynomial multiplication over finite fields
Authors:
David Harvey,
Joris van der Hoeven,
Grégoire Lecerf
Abstract:
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(n log n 8^(log^* n) log p), where log^* is the iterated logarithm. This is the first known Fürer-type complexity bound for F_p[X], and improves on the previously best known bound M_p(n) = O(n log n log log n log p).
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(n log n 8^(log^* n) log p), where log^* is the iterated logarithm. This is the first known Fürer-type complexity bound for F_p[X], and improves on the previously best known bound M_p(n) = O(n log n log log n log p).
△ Less
Submitted 12 July, 2014;
originally announced July 2014.
-
Even faster integer multiplication
Authors:
David Harvey,
Joris van der Hoeven,
Grégoire Lecerf
Abstract:
We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike Fürer, our method does not require constructing special coefficient rings with "fast" roots of unity. Moreover, we prove the more explicit bound O(n log n K^(log^* n))$ with K = 8. We show that an optimised variant of Fürer's algorithm achieves only K = 16, suggesting that the new al…
▽ More
We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike Fürer, our method does not require constructing special coefficient rings with "fast" roots of unity. Moreover, we prove the more explicit bound O(n log n K^(log^* n))$ with K = 8. We show that an optimised variant of Fürer's algorithm achieves only K = 16, suggesting that the new algorithm is faster than Fürer's by a factor of 2^(log^* n). Assuming standard conjectures about the distribution of Mersenne primes, we give yet another algorithm that achieves K = 4.
△ Less
Submitted 12 July, 2014;
originally announced July 2014.
-
Hubble Frontier Fields: The Geometry and Dynamics of the Massive Galaxy Cluster Merger MACSJ0416.1-2403
Authors:
Mathilde Jauzac,
Eric Jullo,
Dominique Eckert,
Harald Ebeling,
Johan Richard,
Marceau Limousin,
Hakim Atek,
Jean-Paul Kneib,
Benjamin Clément,
Eiichi Egami,
David Harvey,
Kenda Knowles,
Richard Massey,
Priyamvada Natarajan,
Benoît Neichel,
Markus Rexroth
Abstract:
We use a joint optical/X-ray analysis to constrain the geometry and history of the ongoing merging event in the massive galaxy cluster MACSJ0416.1-2403 (z=0.397). Our investigation of cluster substructure rests primarily on a combined strong- and weak-lensing mass reconstruction based on the deep, high-resolution images obtained for the Hubble Frontier Fields initiative. To reveal the system's dyn…
▽ More
We use a joint optical/X-ray analysis to constrain the geometry and history of the ongoing merging event in the massive galaxy cluster MACSJ0416.1-2403 (z=0.397). Our investigation of cluster substructure rests primarily on a combined strong- and weak-lensing mass reconstruction based on the deep, high-resolution images obtained for the Hubble Frontier Fields initiative. To reveal the system's dynamics, we complement this lensing analysis with a study of the intra-cluster gas using shallow Chandra data, and a three-dimensional model of the distribution and motions of cluster galaxies derived from over 100 spectroscopic redshifts. The multi-scale grid model obtained from our combined lensing analysis extends the high-precision strong-lensing mass reconstruction recently performed to cluster-centric distances of almost 1 Mpc. Our analysis detects the two well known mass concentrations in the cluster core. A pronounced offset between collisional and collisionless matter is only observed for the SW cluster component, while excellent alignment is found for the NE cluster. Both the lensing analysis and the distribution of cluster light strongly suggest the presence of a third massive structure, almost 2 arcmin SW of the cluster centre. Since no X-ray emission is detected in this region, we conclude that this structure is non-virialised and speculate that it might be part of a large-scale filament almost aligned with our line of sight. Combining all evidence from the distribution of dark and luminous matter, we propose two alternative scenarios for the trajectories of the components of MACSJ0416.1-2403. Upcoming deep X-ray observations that allow the detection of shock fronts, cold cores, and sloshing gas (all key diagnostics for studies of cluster collisions) will allow us to test, and distinguish between these two scenarios.
△ Less
Submitted 22 October, 2014; v1 submitted 11 June, 2014;
originally announced June 2014.
-
Computing zeta functions of arithmetic schemes
Authors:
David Harvey
Abstract:
We present new algorithms for computing zeta functions of algebraic varieties over finite fields. In particular, let X be an arithmetic scheme (scheme of finite type over Z), and for a prime p let zeta_{X_p}(s) be the local factor of its zeta function. We present an algorithm that computes zeta_{X_p}(s) for a single prime p in time p^(1/2+o(1)), and another algorithm that computes zeta_{X_p}(s) fo…
▽ More
We present new algorithms for computing zeta functions of algebraic varieties over finite fields. In particular, let X be an arithmetic scheme (scheme of finite type over Z), and for a prime p let zeta_{X_p}(s) be the local factor of its zeta function. We present an algorithm that computes zeta_{X_p}(s) for a single prime p in time p^(1/2+o(1)), and another algorithm that computes zeta_{X_p}(s) for all primes p < N in time N (log N)^(3+o(1)). These generalise previous results of the author from hyperelliptic curves to completely arbitrary varieties.
△ Less
Submitted 2 September, 2015; v1 submitted 14 February, 2014;
originally announced February 2014.
-
Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
Authors:
David Harvey,
Andrew V. Sutherland
Abstract:
We present an efficient algorithm to compute the Hasse-Witt matrix of a hyperelliptic curve C/Q modulo all primes of good reduction up to a given bound N, based on the average polynomial-time algorithm recently introduced by Harvey. An implementation for hyperelliptic curves of genus 2 and 3 is more than an order of magnitude faster than alternative methods for N = 2^26.
We present an efficient algorithm to compute the Hasse-Witt matrix of a hyperelliptic curve C/Q modulo all primes of good reduction up to a given bound N, based on the average polynomial-time algorithm recently introduced by Harvey. An implementation for hyperelliptic curves of genus 2 and 3 is more than an order of magnitude faster than alternative methods for N = 2^26.
△ Less
Submitted 13 February, 2014;
originally announced February 2014.
-
Parameters Tied to Treewidth
Authors:
Daniel J. Harvey,
David R. Wood
Abstract:
Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds…
▽ More
Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs and show that the inequalities presented are tight.
△ Less
Submitted 27 January, 2016; v1 submitted 11 December, 2013;
originally announced December 2013.
-
Observing Dark Worlds: A crowdsourcing experiment for dark matter mapping
Authors:
David Harvey,
Thomas D. Kitching,
Joyce Noah-Vanhoucke,
Ben Hamner,
Tim Salimans
Abstract:
We present the results and conclusions from the citizen science competition `Observing Dark Worlds', where we asked participants to calculate the positions of dark matter halos from 120 catalogues of simulated weak lensing galaxy data, using computational methods. In partnership with Kaggle (http://www.kaggle.com), 357 users participated in the competition which saw 2278 downloads of the data and…
▽ More
We present the results and conclusions from the citizen science competition `Observing Dark Worlds', where we asked participants to calculate the positions of dark matter halos from 120 catalogues of simulated weak lensing galaxy data, using computational methods. In partnership with Kaggle (http://www.kaggle.com), 357 users participated in the competition which saw 2278 downloads of the data and 3358 submissions. We found that the best algorithms improved on the benchmark code, LENSTOOL by > 30% and could measure the positions of > 3x10^14MSun halos to less than 5'' and < 10^14MSun to within 1'. In this paper, we present a brief overview of the winning algorithms with links to available code. We also discuss the implications of the experiment for future citizen science competitions.
△ Less
Submitted 4 November, 2013;
originally announced November 2013.
-
Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
Authors:
Daniel J. Harvey,
David R. Wood
Abstract:
Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n,k) is the graph with vertex set $\binom{[n]}{k}$, such that two vertices are adjacent if they are disjoint. We determine, for large values of n with respect to k, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdős-K…
▽ More
Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n,k) is the graph with vertex set $\binom{[n]}{k}$, such that two vertices are adjacent if they are disjoint. We determine, for large values of n with respect to k, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdős-Ko-Rado Theorem (for large n with respect to k) when a number of disjoint pairs of k-sets are allowed.
△ Less
Submitted 20 October, 2013;
originally announced October 2013.
-
An incomplete variant of Wilson's congruence
Authors:
Joel Beeren,
David Harvey,
Tim Trudgian
Abstract:
This article examines the nontrivial solutions of the congruence \[ (p-1)\cdots(p-r) \equiv -1 \pmod p. \] We discuss heuristics for the proportion of primes $p$ that have exactly $N$ solutions to this congruence. We supply numerical evidence in favour of these conjectures, and discuss the algorithms used in our calculations.
This article examines the nontrivial solutions of the congruence \[ (p-1)\cdots(p-r) \equiv -1 \pmod p. \] We discuss heuristics for the proportion of primes $p$ that have exactly $N$ solutions to this congruence. We supply numerical evidence in favour of these conjectures, and discuss the algorithms used in our calculations.
△ Less
Submitted 9 October, 2013;
originally announced October 2013.
-
On the cross-section of Dark Matter using substructure infall into galaxy clusters
Authors:
David Harvey,
Eric Tittley,
Richard Massey,
Thomas D. Kitching,
Andy Taylor,
Simon R. Pike,
Scott T. Kay,
Erwin T. Lau,
Daisuke Nagai
Abstract:
We develop a statistical method to measure the interaction cross-section of Dark Matter, exploiting the continuous minor merger events in which small substructures fall into galaxy clusters. We find that by taking the ratio of the distances between the galaxies and Dark Matter, and galaxies and gas in accreting sub-halos, we form a quantity that can be statistically averaged over a large sample of…
▽ More
We develop a statistical method to measure the interaction cross-section of Dark Matter, exploiting the continuous minor merger events in which small substructures fall into galaxy clusters. We find that by taking the ratio of the distances between the galaxies and Dark Matter, and galaxies and gas in accreting sub-halos, we form a quantity that can be statistically averaged over a large sample of systems whilst removing any inherent line-of-sight projections. In order to interpret this ratio as a cross-section of Dark Matter we derive an analytical description of sub-halo infall which encompasses; the force of the main cluster potential, the drag on a gas sub-halo, a model for Dark Matter self-interactions and the resulting sub-halo drag, the force on the gas and galaxies due to the Dark Matter sub-halo potential, and finally the buoyancy on the gas and Dark Matter. We create mock observations from cosmological simulations of structure formation and find that collisionless Dark Matter becomes physically separated from X-ray gas by up to 20h^-1 kpc. Adding realistic levels of noise, we are able to predict achievable constraints from observational data. Current archival data should be able to detect a difference in the dynamical behaviour of Dark Matter and standard model particles at 6 sigma, and measure the total interaction cross-section sigma/m with 68% confidence limits of +/- 1cm2g^-1. We note that this method is not restricted by the limited number of major merging events and is easily extended to large samples of clusters from future surveys which could potentially push statistical errors to 0.1cm^2g^-1.
△ Less
Submitted 20 November, 2013; v1 submitted 7 October, 2013;
originally announced October 2013.
-
Dark Matter Astrometry: Accuracy of sub-halo positions for the measurement of self-interaction cross sections
Authors:
David Harvey,
Richard Massey,
Thomas Kitching,
Andy Taylor,
Eric Jullo,
Jean-Paul Kneib,
Eric Tittley,
Philip J. Marshall
Abstract:
Direct evidence for the existence of dark matter and measurements of its interaction cross-section have been provided by the physical offset between dark matter and intra- cluster gas in merging systems like the Bullet Cluster. Although a smaller signal, this effect is more abundant in minor mergers where infalling substructure dark matter and gas are segregated. In such low-mass systems the gravi…
▽ More
Direct evidence for the existence of dark matter and measurements of its interaction cross-section have been provided by the physical offset between dark matter and intra- cluster gas in merging systems like the Bullet Cluster. Although a smaller signal, this effect is more abundant in minor mergers where infalling substructure dark matter and gas are segregated. In such low-mass systems the gravitational lensing signal comes primarily from weak lensing. A fundamental step in determining such an offset in sub- structure is the ability to accurately measure the positions of dark matter sub-peaks. Using simulated Hubble Space Telescope observations, we make a first assessment of the precision and accuracy with which we can measure infalling groups using weak gravitational lensing. We demonstrate that using an existing and well-used mass re- construction algorithm can measure the positions of 1.5x1013 M substructures that have parent halos ten times more massive with a bias of less than 0.3 . In this regime, our analysis suggests the precision is sufficient to detect (at 3 σ statistical significance) the expected mean offset between dark matter and baryonic gas in infalling groups from a sample of 50 massive clusters.
△ Less
Submitted 9 May, 2013;
originally announced May 2013.
-
BK Lyncis: The Oldest Old Nova?... And a Bellwether for Cataclysmic-Variable Evolution
Authors:
Joseph Patterson,
Helena Uthas,
Jonathan Kemp,
Enrique de Miguel,
Thomas Krajci,
Jerry Foote,
Franz-Josef Hambsch,
Tut Campbell,
George Roberts,
David Cejudo,
Shawn Dvorak,
Tonny Vanmunster,
Robert Koff,
David Skillman,
David Harvey,
Brian Martin,
John Rock,
David Boyd,
Arto Oksanen,
Etienne Morelle,
Joseph Ulowetz,
Anthony Kroes,
Richard Sabo,
Lasse Jensen
Abstract:
We summarize the results of a 20-year campaign to study the light curves of BK Lyncis, a nova-like star strangely located below the 2-3 hour orbital period gap in the family of cataclysmic variables. Two apparent "superhumps" dominate the nightly light curves - with periods 4.6% longer, and 3.0% shorter, than P_orb. The first appears to be associated with the star's brighter states (V~14), while t…
▽ More
We summarize the results of a 20-year campaign to study the light curves of BK Lyncis, a nova-like star strangely located below the 2-3 hour orbital period gap in the family of cataclysmic variables. Two apparent "superhumps" dominate the nightly light curves - with periods 4.6% longer, and 3.0% shorter, than P_orb. The first appears to be associated with the star's brighter states (V~14), while the second appears to be present throughout and becomes very dominant in the low state (V~15.7).
Starting in the year 2005, the star's light curve became indistinguishable from that of a dwarf nova - in particular, that of the ER UMa subclass. Reviewing all the star's oddities, we speculate: (a) BK Lyn is the remnant of the probable nova on 30 December 101, and (b) it has been fading ever since, but has taken ~2000 years for the accretion rate to drop sufficiently to permit dwarf-nova eruptions. If such behavior is common, it can explain other puzzles of CV evolution. One: why the ER UMa class even exists (because all members can be remnants of recent novae). Two: why ER UMa stars and short-period novalikes are rare (because their lifetimes, which are essentially cooling times, are short). Three: why short-period novae all decline to luminosity states far above their true quiescence (because they're just getting started in their postnova cooling). Four: why the orbital periods, accretion rates, and white-dwarf temperatures of short-period CVs are somewhat too large to arise purely from the effects of gravitational radiation (because the unexpectedly long interval of enhanced postnova brightness boosts the mean mass-transfer rate). These are substantial rewards in return for one investment of hypothesis: that the second parameter in CV evolution, besides P_orb, is time since the last classical-nova eruption.
△ Less
Submitted 23 December, 2012;
originally announced December 2012.
-
Statistics of Different Reduction Types of Fermat Curves
Authors:
David Harvey,
Igor Shparlinski
Abstract:
We present some theoretic bounds and algorithms concerning the statistics of different reduction types in the family of Fermat curves $Y^p = X^s(1-X)$, where $p$ is prime and $s =1, ..., p-2$.
We present some theoretic bounds and algorithms concerning the statistics of different reduction types in the family of Fermat curves $Y^p = X^s(1-X)$, where $p$ is prime and $s =1, ..., p-2$.
△ Less
Submitted 4 December, 2012;
originally announced December 2012.
-
Counting points on hyperelliptic curves in average polynomial time
Authors:
David Harvey
Abstract:
Let g >= 1 and let Q be a monic, squarefree polynomial of degree 2g + 1 in Z[x]. For an odd prime p not dividing the discriminant of Q, let Z_p(T) denote the zeta function of the hyperelliptic curve of genus g over the finite field F_p obtained by reducing the coefficients of the equation y^2 = Q(x) modulo p. We present an explicit deterministic algorithm that given as input Q and a positive integ…
▽ More
Let g >= 1 and let Q be a monic, squarefree polynomial of degree 2g + 1 in Z[x]. For an odd prime p not dividing the discriminant of Q, let Z_p(T) denote the zeta function of the hyperelliptic curve of genus g over the finite field F_p obtained by reducing the coefficients of the equation y^2 = Q(x) modulo p. We present an explicit deterministic algorithm that given as input Q and a positive integer N, computes Z_p(T) simultaneously for all such primes p < N, whose average complexity per prime is polynomial in g, log N, and the number of bits required to represent Q.
△ Less
Submitted 26 September, 2013; v1 submitted 31 October, 2012;
originally announced October 2012.
-
Treewidth of the Line Graph of Complete and Complete Multipartite Graphs
Authors:
Daniel J. Harvey,
David R. Wood
Abstract:
In recent papers by Grohe and Marx, the treewidth of the line graph of the complete graph is a critical example. We determine the exact treewidth of the line graph of the complete graph. By extending these techniques, we determine the exact treewidth of the line graph of a regular complete multipartite graph. For an arbitrary complete multipartite graph, we determine the treewidth of the line grap…
▽ More
In recent papers by Grohe and Marx, the treewidth of the line graph of the complete graph is a critical example. We determine the exact treewidth of the line graph of the complete graph. By extending these techniques, we determine the exact treewidth of the line graph of a regular complete multipartite graph. For an arbitrary complete multipartite graph, we determine the treewidth of the line graph up to a lower order term.
△ Less
Submitted 1 August, 2014; v1 submitted 30 October, 2012;
originally announced October 2012.
-
Origins of weak lensing systematics, and requirements on future instrumentation (or knowledge of instrumentation)
Authors:
Richard Massey,
Henk Hoekstra,
Thomas Kitching,
Jason Rhodes,
Mark Cropper,
Jerome Amiaux,
David Harvey,
Yannick Mellier,
Massimo Meneghetti,
Lance Miller,
Stephane Paulin-Henriksson,
Sandrine Pires,
Roberto Scaramella,
Tim Schrabback
Abstract:
The first half of this paper explores the origin of systematic biases in the measurement of weak gravitational lensing. Compared to previous work, we expand the investigation of PSF instability and fold in for the first time the effects of non-idealities in electronic imaging detectors and imperfect galaxy shape measurement algorithms. Together, these now explain the additive A(l) and multiplicati…
▽ More
The first half of this paper explores the origin of systematic biases in the measurement of weak gravitational lensing. Compared to previous work, we expand the investigation of PSF instability and fold in for the first time the effects of non-idealities in electronic imaging detectors and imperfect galaxy shape measurement algorithms. Together, these now explain the additive A(l) and multiplicative M(l) systematics typically reported in current lensing measurements. We find that overall performance is driven by a product of a telescope/camera's *absolute performance*, and our *knowledge about its performance*.
The second half of this paper propagates any residual shear measurement biases through to their effect on cosmological parameter constraints. Fully exploiting the statistical power of Stage IV weak lensing surveys will require additive biases A<1.8e-12 and multiplicative biases M<4.0e-3. These can be allocated between individual budgets in hardware, calibration data and software, using results from the first half of the paper.
If instrumentation is stable and well-calibrated, we find extant shear measurement software from GREAT10 already meet requirements on galaxies detected at S/N=40. Averaging over a population of galaxies with a realistic distribution of sizes, it also meets requirements for a 2D cosmic shear analysis from space. If used on fainter galaxies or for 3D cosmic shear tomography, existing algorithms would need calibration on simulations to avoid introducing bias at a level similar to the statistical error. Requirements on hardware and calibration data are discussed in more detail in a companion paper. Our analysis is intentionally general, but is specifically being used to drive the hardware and ground segment performance budget for the design of the European Space Agency's recently-selected Euclid mission.
△ Less
Submitted 29 October, 2012;
originally announced October 2012.
-
A search for Wilson primes
Authors:
Edgar Costa,
Robert Gerbicz,
David Harvey
Abstract:
A Wilson prime is a prime p such that (p-1)! = -1 mod p^2. We report on a search for Wilson primes up to 2 * 10^13, and describe several new algorithms that were used in the search. In particular we give the first known algorithm that computes (p-1)! mod p^2 in average polynomial time per prime.
A Wilson prime is a prime p such that (p-1)! = -1 mod p^2. We report on a search for Wilson primes up to 2 * 10^13, and describe several new algorithms that were used in the search. In particular we give the first known algorithm that computes (p-1)! mod p^2 in average polynomial time per prime.
△ Less
Submitted 4 December, 2012; v1 submitted 15 September, 2012;
originally announced September 2012.
-
A subquadratic algorithm for computing the n-th Bernoulli number
Authors:
David Harvey
Abstract:
We describe a new algorithm that computes the n-th Bernoulli number in n^(4/3 + o(1)) bit operations. This improves on previous algorithms that had complexity n^(2 + o(1)).
We describe a new algorithm that computes the n-th Bernoulli number in n^(4/3 + o(1)) bit operations. This improves on previous algorithms that had complexity n^(2 + o(1)).
△ Less
Submitted 1 May, 2013; v1 submitted 4 September, 2012;
originally announced September 2012.
-
Faster arithmetic for number-theoretic transforms
Authors:
David Harvey
Abstract:
We show how to improve the efficiency of the computation of fast Fourier transforms over F_p where p is a word-sized prime. Our main technique is optimisation of the basic arithmetic, in effect decreasing the total number of reductions modulo p, by making use of a redundant representation for integers modulo p. We give performance results showing a significant improvement over Shoup's NTL library.
We show how to improve the efficiency of the computation of fast Fourier transforms over F_p where p is a word-sized prime. Our main technique is optimisation of the basic arithmetic, in effect decreasing the total number of reductions modulo p, by making use of a redundant representation for integers modulo p. We give performance results showing a significant improvement over Shoup's NTL library.
△ Less
Submitted 25 September, 2013; v1 submitted 13 May, 2012;
originally announced May 2012.
-
A linear-time algorithm for finding a complete graph minor in a dense graph
Authors:
Vida Dujmović,
Daniel J. Harvey,
Gwenaël Joret,
Bruce Reed,
David R. Wood
Abstract:
Let g(t) be the minimum number such that every graph G with average degree d(G) \geq g(t) contains a K_{t}-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) \in Θ(t*sqrt{log t}). This article shows that for all fixed ε> 0 and fixed sufficiently large t \geq t(ε), if d(G) \geq (2+ε)g(t) then we can find this K_{t}-minor in…
▽ More
Let g(t) be the minimum number such that every graph G with average degree d(G) \geq g(t) contains a K_{t}-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) \in Θ(t*sqrt{log t}). This article shows that for all fixed ε> 0 and fixed sufficiently large t \geq t(ε), if d(G) \geq (2+ε)g(t) then we can find this K_{t}-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when d(G) \geq 2^{t-2}.
△ Less
Submitted 23 April, 2013; v1 submitted 12 February, 2012;
originally announced February 2012.
-
Faster deterministic integer factorization
Authors:
Edgar Costa,
David Harvey
Abstract:
The best known unconditional deterministic complexity bound for computing the prime factorization of an integer N is O(M_int(N^(1/4) log N)), where M_int(k) denotes the cost of multiplying k-bit integers. This result is due to Bostan--Gaudry--Schost, following the Pollard--Strassen approach. We show that this bound can be improved by a factor of (log log N)^(1/2).
The best known unconditional deterministic complexity bound for computing the prime factorization of an integer N is O(M_int(N^(1/4) log N)), where M_int(k) denotes the cost of multiplying k-bit integers. This result is due to Bostan--Gaudry--Schost, following the Pollard--Strassen approach. We show that this bound can be improved by a factor of (log log N)^(1/2).
△ Less
Submitted 10 January, 2012;
originally announced January 2012.
-
Fast computation of Bernoulli, Tangent and Secant numbers
Authors:
Richard P. Brent,
David Harvey
Abstract:
We consider the computation of Bernoulli, Tangent (zag), and Secant (zig or Euler) numbers. In particular, we give asymptotically fast algorithms for computing the first n such numbers in O(n^2.(log n)^(2+o(1))) bit-operations. We also give very short in-place algorithms for computing the first n Tangent or Secant numbers in O(n^2) integer operations. These algorithms are extremely simple, and fas…
▽ More
We consider the computation of Bernoulli, Tangent (zag), and Secant (zig or Euler) numbers. In particular, we give asymptotically fast algorithms for computing the first n such numbers in O(n^2.(log n)^(2+o(1))) bit-operations. We also give very short in-place algorithms for computing the first n Tangent or Secant numbers in O(n^2) integer operations. These algorithms are extremely simple, and fast for moderate values of n. They are faster and use less space than the algorithms of Atkinson (for Tangent and Secant numbers) and Akiyama and Tanigawa (for Bernoulli numbers).
△ Less
Submitted 5 September, 2011; v1 submitted 1 August, 2011;
originally announced August 2011.
-
Characterizing projective spaces on deformations of Hilbert schemes of K3 surfaces
Authors:
David Harvey,
Brendan Hassett,
Yuri Tschinkel
Abstract:
We seek to characterize homology classes of Lagrangian projective spaces embedded in irreducible holomorphic-symplectic manifolds, up to the action of the monodromy group. This paper addresses the case of manifolds deformation-equivalent to the Hilbert scheme of length-three subschemes of a K3 surface. The class of the projective space in the cohomology ring has prescribed intersection properties,…
▽ More
We seek to characterize homology classes of Lagrangian projective spaces embedded in irreducible holomorphic-symplectic manifolds, up to the action of the monodromy group. This paper addresses the case of manifolds deformation-equivalent to the Hilbert scheme of length-three subschemes of a K3 surface. The class of the projective space in the cohomology ring has prescribed intersection properties, which translate into Diophantine equations. Possible homology classes correspond to integral points on an explicit elliptic curve; our proof entails showing that the only such point is two-torsion.
△ Less
Submitted 4 November, 2010;
originally announced November 2010.
-
An in-place truncated Fourier transform and applications to polynomial multiplication
Authors:
David Harvey,
Daniel S. Roche
Abstract:
The truncated Fourier transform (TFT) was introduced by van der Hoeven in 2004 as a means of smoothing the "jumps" in running time of the ordinary FFT algorithm that occur at power-of-two input sizes. However, the TFT still introduces these jumps in memory usage. We describe in-place variants of the forward and inverse TFT algorithms, achieving time complexity O(n log n) with only O(1) auxiliary…
▽ More
The truncated Fourier transform (TFT) was introduced by van der Hoeven in 2004 as a means of smoothing the "jumps" in running time of the ordinary FFT algorithm that occur at power-of-two input sizes. However, the TFT still introduces these jumps in memory usage. We describe in-place variants of the forward and inverse TFT algorithms, achieving time complexity O(n log n) with only O(1) auxiliary space. As an application, we extend the second author's results on space-restricted FFT-based polynomial multiplication to polynomials of arbitrary degree.
△ Less
Submitted 28 January, 2010;
originally announced January 2010.
-
Irregular primes to 163 million
Authors:
Joe P. Buhler,
David Harvey
Abstract:
We compute all irregular primes less than 163,577,356. For all of these primes we verify that the Kummer-Vandiver conjecture holds and that the lambda-invariant is equal to the index of irregularity.
We compute all irregular primes less than 163,577,356. For all of these primes we verify that the Kummer-Vandiver conjecture holds and that the lambda-invariant is equal to the index of irregularity.
△ Less
Submitted 12 December, 2009; v1 submitted 10 December, 2009;
originally announced December 2009.
-
Faster exponentials of power series
Authors:
David Harvey
Abstract:
We describe a new algorithm for computing exp(f) where f is a power series in C[[x]]. If M(n) denotes the cost of multiplying polynomials of degree n, the new algorithm costs (2.1666... + o(1)) M(n) to compute exp(f) to order n. This improves on the previous best result, namely (2.333... + o(1)) M(n).
We describe a new algorithm for computing exp(f) where f is a power series in C[[x]]. If M(n) denotes the cost of multiplying polynomials of degree n, the new algorithm costs (2.1666... + o(1)) M(n) to compute exp(f) to order n. This improves on the previous best result, namely (2.333... + o(1)) M(n).
△ Less
Submitted 16 November, 2009;
originally announced November 2009.
-
Faster algorithms for the square root and reciprocal of power series
Authors:
David Harvey
Abstract:
We give new algorithms for the computation of square roots and reciprocals of power series in C[[x]]. If M(n) denotes the cost of multiplying polynomials of degree n, the square root to order n costs (1.333... + o(1)) M(n) and the reciprocal costs (1.444... + o(1)) M(n). These improve on the previous best results, respectively (1.8333... + o(1)) M(n) and (1.5 + o(1)) M(n).
We give new algorithms for the computation of square roots and reciprocals of power series in C[[x]]. If M(n) denotes the cost of multiplying polynomials of degree n, the square root to order n costs (1.333... + o(1)) M(n) and the reciprocal costs (1.444... + o(1)) M(n). These improve on the previous best results, respectively (1.8333... + o(1)) M(n) and (1.5 + o(1)) M(n).
△ Less
Submitted 10 October, 2009;
originally announced October 2009.
-
A cache-friendly truncated FFT
Authors:
David Harvey
Abstract:
We describe a cache-friendly version of van der Hoeven's truncated FFT and inverse truncated FFT, focusing on the case of `large' coefficients, such as those arising in the Schonhage--Strassen algorithm for multiplication in Z[x]. We describe two implementations and examine their performance.
We describe a cache-friendly version of van der Hoeven's truncated FFT and inverse truncated FFT, focusing on the case of `large' coefficients, such as those arising in the Schonhage--Strassen algorithm for multiplication in Z[x]. We describe two implementations and examine their performance.
△ Less
Submitted 17 October, 2008;
originally announced October 2008.
-
A multimodular algorithm for computing Bernoulli numbers
Authors:
David Harvey
Abstract:
We describe an algorithm for computing Bernoulli numbers. Using a parallel implementation, we have computed B(k) for k = 10^8, a new record. Our method is to compute B(k) modulo p for many small primes p, and then reconstruct B(k) via the Chinese Remainder Theorem. The asymptotic time complexity is O(k^2 log(k)^(2+epsilon)), matching that of existing algorithms that exploit the relationship betw…
▽ More
We describe an algorithm for computing Bernoulli numbers. Using a parallel implementation, we have computed B(k) for k = 10^8, a new record. Our method is to compute B(k) modulo p for many small primes p, and then reconstruct B(k) via the Chinese Remainder Theorem. The asymptotic time complexity is O(k^2 log(k)^(2+epsilon)), matching that of existing algorithms that exploit the relationship between B(k) and the Riemann zeta function. Our implementation is significantly faster than several existing implementations of the zeta-function method.
△ Less
Submitted 13 October, 2008; v1 submitted 8 July, 2008;
originally announced July 2008.
