On Toric Orbits in the Affine Sieve

Abstract

We give a detailed analysis of a probabilistic heuristic model for the failure of “saturation” in instances of the Affine Sieve having toral Zariski closure. Based on this model, we formulate precise conjectures on several classical problems of arithmetic interest and test these against empirical data.

Keywords:

• affine sieve
• prime factors
• Fibonacci numbers; Lucas numbers; Mersenne primes

Acknowledgments

The authors thank Jonathan Bober, Andrew Granville, Peter Sarnak, and Alireza Salehi Golsefidy for enlightening discussions, comments, and suggestions, and most of all, Danny Krashen and Sean Irvine for the highly nontrivial and time-consuming task of computing Ω for Lucas, Fibonacci, and Mersenne numbers from cumbersome online databases of their factorizations.

Notes

1 One can work more generally with entries in the ring of S-integers ${\mathbb{Z}}_S,$ but we restrict to $\mathbb{Z}$ for ease of exposition. Note that there exist $\Gamma <{\text{GL}}_N(\mathbb{Q})$ for which no vector ${\mathbf{v}}_0\ne (0,\dots ,0)$ gives an integral orbit, e.g., $\Gamma =〈A〉$ with $A=(\begin{array}{cc}\frac{1}{2}& 0\\ 0& \frac{1}{2}\end{array}).$

2 Recall that this Zariski closure can be thought of as the common zero set of all polynomials $p(x_1,x_2,\dots ,x_N)\in \mathbb{C}[x_1,\dots ,x_N]$ inside affine space ${\mathbb{A}}^N(\mathbb{C})={\mathbb{C}}^N$ that vanish on $\mathcal{O}.$

3 We need not assume any restriction on the orbit like “primitivity” (that the $\gcd (f(\mathcal{O}))=1$) since the fixed prime factors, if any, can be accounted for in the value of R.

4 For example, ${({\mathbb{C}}^{\times })}^n.$

5 For example, in the normal order sense of the [Hardy and Ramanujan 17] theorem, further refined in the Erdős-Kac theorem.

6 The probable primality of $F_{\mathfrak{n}}$ was found by T. D. Noe while that of $L_{\mathfrak{n}}$ by de Water; see OEIS for further credits. Both numbers have passed numerous pseudoprimality tests. Assuming GRH, one would need to run about ${(30000)}^4$ trials (that is, ${(\hspace{0.17em}\text{log}\hspace{0.17em}{F}_{\mathfrak{n}})}^2$ tests at a cost of ${(\hspace{0.17em}\text{log}\hspace{0.17em}{F}_{\mathfrak{n}})}^2$ each, ignoring epsilons) of the Miller primality test to certify these entries prime. Unconditionally, the exponent 4 would be replaced by a 6, see [Lenstra and Pomerance 11]. One could alternatively try the elliptic curve primality test, which is also unconditional and in practice runs faster, though a worst-case execution time is currently unknown.

7 In some very special cases, one can completely determine sets like Σ_FL. Indeed, see [Bober et al. 09], where all solutions to $x^2-3y^2=1$ with $\Omega (\mathit{xy})\le 3$ are effectively listed.

Additional information

Funding

Kontorovich is partially supported by an NSF CAREER grant DMS-1455705, an NSF FRG grant DMS-1463940, US-Israel Binational Science Foundation Grant #2014099, a Simons Fellowship, a von Neumann Fellowship at IAS, and the IAS’s NSF grant DMS-1638352. Lagarias is partially supported by NSF grants DMS-1401224 and DMS-1701576.