Search for: All records

Abstract We characterise, in terms of Dixmier–Ohno invariants, the types of singularities that a plane quartic curve can have. We then use these results to obtain new criteria for determining the stable reduction types of non-hyperelliptic curves of genus 3. 

Abstract We give an alternative derivation of (N, N)-isogenies between fast Kummer surfaces which complements existing works based on the theory of theta functions. We use this framework to produce explicit formulæ for the case of$$N=3$$ $N=3$, and show that the resulting algorithms are more efficient than all prior (3, 3)-isogeny algorithms. 

Abstract We give an algorithm to compute representatives of the conjugacy classes of semisimple square integral matrices with given minimal and characteristic polynomials. We also give an algorithm to compute the $$\mathbb {F}_q$$ $F_q$-isomorphism classes of abelian varieties over a finite field $$\mathbb {F}_q$$ $F_q$which belong to an isogeny class determined by a characteristic polynomial hof Frobenius when his ordinary, or qis prime and hhas no real roots. 

Abstract The Chabauty–Kim method and its refined variant by Betts and Dogra aim to cut out theS-integral points$$X(\mathbb {Z}_S)$$ $X\left(Z_S\right)$on a curve inside thep-adic points$$X(\mathbb {Z}_p)$$ $X\left(Z_p\right)$by producing enough Coleman functions vanishing on them. We derive new functions in the case of the thrice-punctured line whenScontains two primes. We describe an algorithm for computing refined Chabauty–Kim loci and verify Kim’s Conjecture over$$\mathbb {Z}[1/6]$$ $Z[1/6]$for all choices of auxiliary prime $$p < 10{,}000$$ $p<10,000$. 

Abstract The Markoff graphs modulopwere proven by Chen (Ann Math 199(1), 2024) to be connected for all but finitely many primes, and Baragar (The Markoff equation and equations of Hurwitz. Brown University, 1991) conjectured that they are connected for all primes, equivalently that every solution to the Markoff equation moduloplifts to a solution over$$\mathbb {Z}$$ $Z$. In this paper, we provide an algorithmic realization of the process introduced by Bourgain et al. [arXiv:1607.01530] to test whether the Markoff graph modulopis connected for arbitrary primes. Our algorithm runs in$$o(p^{1 + \epsilon })$$ $o\left(p^{1+ϵ}\right)$time for every$$\epsilon > 0$$ $ϵ>0$. We demonstrate this algorithm by confirming that the Markoff graph modulopis connected for all primes less than one million. 

Abstract We present an efficient algorithm to compute the Euler factor of a genus 2 curve$$C/\mathbb {Q}$$ $C/Q$at an odd primepthat is of bad reduction forCbut of good reduction for the Jacobian ofC(a prime of “almost good” reduction). Our approach is based on the theory of cluster pictures introduced by Dokchitser, Dokchitser, Maistret, and Morgan, which allows us to reduce the problem to a short, explicit computation over$$\mathbb {Z}$$ $Z$and$$\mathbb {F}_p$$ $F_p$, followed by a point-counting computation on two elliptic curves over$$\mathbb {F}_p$$ $F_p$, or a single elliptic curve over$$\mathbb {F}_{p^2}$$ $F_{p^2}$. A key feature of our approach is that we avoid the need to compute a regular model forC. This allows us to efficiently compute many examples that are infeasible to handle using the algorithms currently available in computer algebra systems such as Magma and Pari/GP. 

Abstract We describe an algorithm for computing, for all primes$$p \le X$$ $p\le X$, the trace of Frobenius atpof a hypergeometric motive over$$\mathbb {Q}$$ $Q$in time quasilinear inX. This involves computing the trace modulo$$p^e$$ $p^e$for suitablee; as in our previous work treating the case$$e=1$$ $e=1$, we combine the Beukers–Cohen–Mellit trace formula with average polynomial time techniques of Harvey and Harvey–Sutherland. The key new ingredient for$$e>1$$ $e>1$is an expanded version of Harvey’s “generic prime” construction, making it possible to incorporate certainp-adic transcendental functions into the computation; one of these is thep-adic Gamma function, whose average polynomial time computation is an intermediate step which may be of independent interest. We also provide an implementation in Sage and discuss the remaining computational issues around tabulating hypergeometricL-series. 

Abstract We report that there are 49679870 Carmichael numbers less than$$10^{22}$$ ${10}^{22}$which is an order of magnitude improvement on Richard Pinch’s prior work. We find Carmichael numbers of the form$$n = Pqr$$ $n=Pqr$using an algorithm bifurcated by the size ofPwith respect to the tabulation boundB. For$$P < 7 \times 10^7$$ $P<7\times {10}^7$, we found 35985331 Carmichael numbers and 1202914 of them were less than$$10^{22}$$ ${10}^{22}$. When$$P > 7 \times 10^7$$ $P>7\times {10}^7$, we found 48476956 Carmichael numbers less than$$10^{22}$$ ${10}^{22}$. We provide a comprehensive overview of both cases of the algorithm. For the large case, we show and implement asymptotically faster ways to tabulate compared to the prior tabulation. We also provide an asymptotic estimate of the cost of this algorithm. It is interesting that Carmichael numbers are worst case inputs to this algorithm. So, providing a more robust asymptotic analysis of the cost of the algorithm would likely require resolution of long-standing open questions regarding the asymptotic density of Carmichael numbers. 

Abstract We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre’s conjecture claims that for every positive integern, there exists a prime between$$n^2$$ $n^2$and$$(n+1)^2$$ ${(n+1)}^2$. Oppermann’s conjecture subsumes Legendre’s conjecture by claiming there are primes between$$n^2$$ $n^2$and$$n(n+1)$$ $n(n+1)$and also between$$n(n+1)$$ $n(n+1)$and$$(n+1)^2$$ ${(n+1)}^2$. Using Cramér’s conjecture as the basis for a heuristic run-time analysis, we show that our algorithm can verify Oppermann’s conjecture, and hence also Legendre’s conjecture, for all$$n\le N$$ $n\le N$in time$$O( N \log N \log \log N)$$ $O(NlogNloglogN)$and space$$N^{O(1/\log \log N)}$$ $N^{O(1/loglogN)}$. We implemented a parallel version of our algorithm and improved the empirical verification of Oppermann’s conjecture from the previous$$N = 2\cdot 10^{9}$$ $N=2·{10}^9$up to$$N = 7.05\cdot 10^{13} > 2^{46}$$ $N=7.05·{10}^{13}>2^{46}$, so we were finding 27 digit primes. The computation ran for about half a year on each of two platforms: four Intel Xeon Phi 7210 processors using a total of 256 cores, and a 192-core cluster of Intel Xeon E5-2630 2.3GHz processors.