Erdős–Granville–Pomerance–Spiro conjecture

This entry is a partial result on an open problem. It does not claim a solution of the general conjecture.

The full conjecture remains open. This note extends the dominant-largest-prime argument to a family where the second-largest prime can be smaller than its cofactor. Work is tracked in issue #47.

Theorem. Let ℰ\mathcal E consist of n=pqrwn=pqrw with p>q>rp>q>r prime, p>np>\sqrt n, and r>w3r>w^3. For every set 𝒜\mathcal A of natural density zero,

#{n≤X:n∈ℰ,s(n)∈𝒜}=o(X). \#\{n\le X:n\in\mathcal E,\ s(n)\in\mathcal A\}=o(X).

In particular, r>w3r>w^3 implies r>wr>w when w≥1w\ge1, so the displayed primes are the largest three and are coprime to ww. The result adds a family of density about 1.50%1.50\% to the previously covered inputs.

Reductions

Work on X/2<n≤XX/2<n\le X. We can impose fixed positive margins on the bounds for p,rp,r and ww after discarding an arbitrarily small upper proportion of inputs. To see this, the number of possible pp for each q,r,wq,r,w is O(X/(qrwlogX))O(X/(qrw\log X)). If w≤Xδw\le X^\delta, sum the reciprocal condition q>r>wq>r>w over the two primes. For w≥2w\ge2 it costs at most O((1+log(logX/logw))2)O((1+\log(\log X/\log w))^2). The sum of these weights against 1/w1/w for 2≤w≤Xδ2\le w\le X^\delta is O(δ(1+log(1/δ))2logX)+o(logX)O(\delta(1+\log(1/\delta))^2\log X)+o(\log X) by integration. The case w=1w=1 costs o(X)o(X).

Requiring p≥n1/2+ηp\ge n^{1/2+\eta} removes only O(ηX)+o(X)O(\eta X)+o(X) inputs by the reciprocal sum over m=qrwm=qrw between constant multiples of X1/2−ηX^{1/2-\eta} and X\sqrt X. For w≥Xδw\ge X^\delta, the interval w3<r<Xηw3w^3<r<X^\eta w^3 has prime reciprocal sum O(η/δ)+o(1)O(\eta/\delta)+o(1) uniformly in ww, by Mertens' theorem. The reciprocal sum over q>rq>r is now bounded in terms of δ\delta. Thus we can require r≥nηw3r\ge n^\eta w^3 as well. Finally, for a sufficiently small fixed ζ>0\zeta>0, we can require that ww have a prime factor j≥Xζj\ge X^\zeta of exponent one. The inputs failing this because ww is XζX^\zeta-smooth cost O((ζ/δ)X)O((\zeta/\delta)X) by the average logarithm of the XζX^\zeta-smooth part. The inputs divisible by the square of any prime at least XζX^\zeta cost o(X)o(X).

Apply the small-prime and normality reductions in the main note. Take Y=y(Xβ)Y=y(X^\beta) with fixed β>0\beta>0 smaller than the power lower bounds on w,r,qw,r,q. For n,m=qrw,wn,m=qrw,w the common YY-smooth part is d≤logXd\le\log X, and we require gcd(t,s(t))=(s(t))Y=d\gcd(t,s(t))=(s(t))_Y=d and π∣σ(t)/d\pi\mid \sigma(t)/d for each prime π≤Y\pi\le Y and t=n,m,wt=n,m,w. Also require s(m)≍ms(m)\asymp m, s(w)≍ws(w)\asymp w, σ(s(m))≪m\sigma(s(m))\ll m, and the reciprocal-divisor condition for σ(m)\sigma(m). In particular s(m)/φ(s(m))≪1s(m)/\varphi(s(m))\ll1. Davenport's theorem and the iterate theorem from the original paper give the normality bounds. Exceptional sets in ww transfer by summing over pp and the reciprocal prime sums over q,rq,r, which are bounded since q,rq,r have fixed power lower bounds.

Partition the allowed logarithmic exponents of q,r,wq,r,w into finitely many boxes of width at most 2ξ2\xi, centered at (v,b,c)(v,b,c). The margins give b>3cb>3c and c>0c>0, uniformly away from equality. We will take ξ\xi sufficiently small in terms of the margins and ζ\zeta. It suffices to prove a second moment of size O(X)O(X) within each box. No collisions between different boxes are needed for the preimage bound.

Small and intermediate collision moduli

For distinct cofactors m,m′m,m' in a collision, put dh=gcd(s(m),s(m′))d h=\gcd(s(m),s(m')). The two-prime sieve for p,p′p,p' in the main note applies since m,m′≪X1/2−ηm,m'\ll X^{1/2-\eta} up to constants. For each such pair of cofactors it gives at most

≪Xdhmm′(logX)2Dφ(D),D=s(m)dhs(m′)dh|σ(m)−σ(m′)|dh \ll \frac{X d h}{m m'(\log X)^2}\frac{D}{\varphi(D)},\qquad D=\frac{s(m)}{dh}\frac{s(m')}{dh} \frac{|\sigma(m)-\sigma(m')|}{dh}

prime pairs. In a collision m≡m′(modh)m\equiv m'\pmod h and h∣s(m),s(m′)h\mid s(m),s(m'). We use the quadratic congruence in q,rq,r from the main note for h≤Xγh\le X^\gamma, with any fixed γ\gamma between half a power lower bound for rr and a power lower bound for qq. That argument only requires these prime power bounds and the stated normality conditions. It gives O(X)O(X) after summing over dd.

Split q,rq,r further into dyadic intervals with lower endpoints Q,RQ,R, and use primes on these endpoints for m′m'. For Xγ<h≤QRX−μX^\gamma<h\le QR X^{-\mu}, where μ>0\mu>0 will be chosen small, fix m′,h,wm',h,w. The congruences qrw≡σ(w)(q+1)(r+1)≡m′(modh)qrw\equiv\sigma(w)(q+1)(r+1)\equiv m'\pmod h determine qrqr and q+rq+r modulo hh since the coefficients and m′m' are units. The permitted rr lie in at most 2ω(h)2^{\omega(h)} residue classes modulo a modulus at least h\sqrt h, by the quadratic root cover in the main note. For each rr, the prime qq lies in a single class modulo hh. Even ignoring primality, the product of the reciprocal sums over q,rq,r, multiplied by hh, is at most

O(2ω(h)(1h+1R+hQ+hQR)). O\left(2^{\omega(h)} \left(\frac1{\sqrt h}+\frac1R+\frac{\sqrt h}{Q} +\frac h{QR}\right)\right).

This saves a power of XX since R≤2QR\le 2Q, h≤QRX−μh\le QR X^{-\mu}, and RR has a fixed power lower bound. The number of divisors of s(m′)s(m') and 2ω(h)2^{\omega(h)} are Xo(1)X^{o(1)}. All other sums, including the reciprocal sums over w,m′w,m' and the sieve singular factor, cost only Xo(1)X^{o(1)}. This range gives o(X)o(X).

Exact relations for the largest collision moduli

It remains to bound h>QRX−μh>QR X^{-\mu}. In this range replace D/φ(D)D/\varphi(D) in the sieve by O(loglogX)O(\log\log X). The identity s(qrw)=s(w)qr+σ(w)(q+r+1)s(qrw)=s(w)qr+\sigma(w)(q+r+1) gives

wσ(w)(q+r+1)≡−s(w)m′(modh). w\sigma(w)(q+r+1)\equiv -s(w)m'\pmod h.

Comparing this congruence with the corresponding congruence for m′m' yields wσ(w)s(w′)(q+r+1)≡w′σ(w′)s(w)(q′+r′+1)(modh)w\sigma(w)s(w')(q+r+1)\equiv w'\sigma(w')s(w)(q'+r'+1)\pmod h. Both sides are O(Xv+3c+O(ξ))O(X^{v+3c+O(\xi)}), whereas h≥Xv+b−μ+O(ξ)h\ge X^{v+b-\mu+O(\xi)}. Since b>3cb>3c, take μ,ξ\mu,\xi small enough that the congruence is an equality. Define

tw=w/d,aw=s(w)/d,bw=σ(w)/d,qquadNw=twbw=tw(tw+aw). t_w=w/d,\qquad a_w=s(w)/d,\qquad b_w=\sigma(w)/d,qquad N_w=t_w b_w=t_w(t_w+a_w).

The equality now says (Nw/aw)(q+r+1)=(Nw′/aw′)(q′+r′+1)(N_w/a_w)(q+r+1)=(N_{w'}/a_{w'})(q'+r'+1). For fixed w,w′,q′,r′w,w',q',r', it determines q+rq+r. Together with qr≡m′/w(modh)qr\equiv m'/w\pmod h this gives at most O(1+QR/h)O(1+QR/h) choices of q,rq,r: the product is strictly increasing in the smaller prime when their sum is fixed, and lies in an interval of length O(QR)O(QR). The inverse of ww modulo hh exists because gcd(m,s(m))=d\gcd(m,s(m))=d.

When w=w′w=w', the sums are equal and qr≠q′r′qr\ne q'r' for distinct m,m′m,m'. Thus h≤|qr−q′r′|≪QR+Q′R′h\le |qr-q'r'|\ll QR+Q'R'. After multiplying by h/mh/m and summing h∣s(m′)/dh\mid s(m')/d, the resulting bound is O(X−c+O(ξ)+o(1))O(X^{-c+O(\xi)+o(1)}) for each m′m'. This gives o(X)o(X) such collisions after the prime-pair sieve.

When w≠w′w\ne w', put

Aw,w′=Nwaw′gcd(Nwaw′,Nw′aw). A_{w,w'}=\frac{N_w a_{w'}} {\gcd(N_w a_{w'},N_{w'} a_w)}.

This integer divides q′+r′+1q'+r'+1. For each w,q′,r′,w′w,q',r',w', the sum over choices of m,hm,h of the sieve weight h/mh/m is at most a constant times

σ(s(m′))QRw+τ(s(m′))w≪XO(ξ)+o(1). \frac{\sigma(s(m'))}{QRw}+\frac{\tau(s(m'))}{w} \ll X^{O(\xi)+o(1)}.

Here the first term follows by summing hh over the divisors of s(m′)/ds(m')/d, and the second follows from the QR/hQR/h term in the number of choices of q,rq,r. The retained σ(s(m′))≪m′\sigma(s(m'))\ll m' bounds the first term. Since Aw,w′≪X3c+O(ξ)A_{w,w'}\ll X^{3c+O(\xi)} and q′≍Q′q'\asymp Q' has exponent v≥b>3cv\ge b>3c, the sum of 1/m′1/m' over the eligible q′,r′q',r' for each w,w′w,w' in their dyadic boxes is O(1/(w′Aw,w′))O(1/(w'A_{w,w'})), by counting q′q' in one residue class. Including the outer prime-pair sieve and summing the dyadic boxes costs at most

X1+O(ξ)+o(1)∑w′1w′∑w≠w′1Aw,w′. X^{1+O(\xi)+o(1)} \sum_{w'}\frac1{w'}\sum_{w\ne w'}\frac1{A_{w,w'}}.

We show that the displayed reciprocal sum saves a fixed power of XX.

Rational ratios of two cofactors

Write gN=gcd(Nw,Nw′)g_N=\gcd(N_w,N_{w'}) and ga=gcd(aw,aw′)g_a=\gcd(a_w,a_{w'}). The gcd in the definition of Aw,w′A_{w,w'} is gNgag_N g_a because gcd(Nw,aw)=gcd(Nw′,aw′)=1\gcd(N_w,a_w)=\gcd(N_{w'},a_{w'})=1. Also gcd(tw,bw)=1\gcd(t_w,b_w)=1, by the retained gcd condition. Take 0<ε<min(c/2,ζ/10)0<\varepsilon<\min(c/2,\zeta/10) and later take ξ\xi sufficiently small in terms of ε\varepsilon.

First suppose gNga<X3c−εg_N g_a<X^{3c-\varepsilon}. For each fixed w′w', there are Xo(1)X^{o(1)} possible choices of the divisors ga∣aw′g_a\mid a_{w'} and u1,u2∣Nw′u_1,u_2\mid N_{w'} such that u1u2=gNu_1u_2=g_N, u1∣twu_1\mid t_w, and u2∣bwu_2\mid b_w. They are pairwise coprime. The pair (tw,bw)(t_w,b_w) is a primitive integer point in the lattice specified by these two divisibilities and by bw−tw≡0(modga)b_w-t_w\equiv0\pmod{g_a}. The lattice has determinant u1u2gau_1u_2g_a, by the Chinese remainder theorem. In a centered box of side length O(L)O(L) a planar lattice of determinant D0D_0 has O(1+L2/D0)O(1+L^2/D_0) primitive integer points. Indeed, if the points lie on one line through the origin, there are at most two. Otherwise a shortest nonzero lattice vector has length l≪Ll\ll L and belongs to a basis. The lattice lies on parallel lines in that direction at spacing D0/l≪LD_0/l\ll L, since there is a point off the line through the origin. Counting lines and then points on each gives O(L2/D0)O(L^2/D_0).

Here L≪Xc+O(ξ)L\ll X^{c+O(\xi)}, and 1/Aw,w′=gNga/(Nwaw′)1/A_{w,w'}=g_N g_a/(N_w a_{w'}) with Nwaw′=X3c+O(ξ)+o(1)N_w a_{w'}=X^{3c+O(\xi)+o(1)}. Consequently the inner sum in this range is at most X−c+O(ξ)+o(1)+X−ε+O(ξ)+o(1)X^{-c+O(\xi)+o(1)}+X^{-\varepsilon+O(\xi)+o(1)}, uniformly in w′w'. The outer reciprocal sum over w′w' costs at most O(logX)O(\log X).

Now suppose gNga≥X3c−εg_N g_a\ge X^{3c-\varepsilon}. The numerator and denominator of each reduced ratio α=aw/aw′\alpha=a_w/a_{w'} and λ=Nw/Nw′\lambda=N_w/N_{w'} are O(Xε+O(ξ)+o(1))O(X^{\varepsilon+O(\xi)+o(1)}). Write w′=jzw'=jz where j≥Xζj\ge X^\zeta is a prime coprime to zz, and let S=σ(z)S=\sigma(z). For each fixed z,α,λz,\alpha,\lambda, the identity (2tw+aw)2=aw2+4Nw(2t_w+a_w)^2=a_w^2+4N_w gives

d2(2tw+aw)2=α2((S−z)j+S)2+4λzSj(j+1). d^2(2t_w+a_w)^2 =\alpha^2((S-z)j+S)^2+4\lambda zS\,j(j+1).

This polynomial in jj has discriminant 16λz2S2(λ−α2)16\lambda z^2 S^2(\lambda-\alpha^2). If λ=α2\lambda=\alpha^2, we have tw(tw+aw)/aw2=tw′(tw′+aw′)/aw′2t_w(t_w+a_w)/a_w^2=t_{w'}(t_{w'}+a_{w'})/a_{w'}^2, so tw/aw=tw′/aw′t_w/a_w=t_{w'}/a_{w'} by monotonicity. Both fractions are reduced, giving w=w′w=w', which has already been treated.

Otherwise the square condition on the right gives at most Xo(1)X^{o(1)} choices of jj for fixed z,α,λz,\alpha,\lambda. For completeness, clear denominators by multiplying both sides by a square, giving y2=Pj2+Q0j+R0y^2=P j^2+Q_0 j+R_0 with integer coefficients of polynomial size in XX, P>0P>0, and nonzero discriminant N=Q02−4PR0N=Q_0^2-4P R_0. Completing the square gives (2Pj+Q0)2−P(2y)2=N(2Pj+Q_0)^2-P(2y)^2=N. If PP is a square, factor and use the divisor bound. Otherwise, remove the square part of PP and work in the ring of integers of the real quadratic field with the resulting squarefree radicand. An algebraic integer of norm NN generates an ideal dividing (N)(N), with only Xo(1)X^{o(1)} possibilities by unique ideal factorization. Within one ideal, generators differ by units. Their absolute values at one real embedding lie between X−O(1)X^{-O(1)} and XO(1)X^{O(1)} because both embeddings are polynomially bounded and the product is the nonzero norm. A unit of absolute value greater than one has absolute value at least the golden ratio, by its integral trace and norm ±1\pm1. Thus only O(logX)O(\log X) generators in the given range occur per ideal. This is the usual quadratic norm argument for generalized Pell equations, with the bound uniform since the radicand is of polynomial size.

There are O(Xc−ζ+O(ξ))O(X^{c-\zeta+O(\xi)}) choices of zz and at most X4ε+O(ξ)+o(1)X^{4\varepsilon+O(\xi)+o(1)} choices for the two ratios. Each w′w' and the ratios determine ww uniquely, since tw(tw+aw)=Nwt_w(t_w+a_w)=N_w is increasing in positive twt_w with awa_w fixed. Thus the sum over these pairs, using 1/w′≤X−c+O(ξ)1/w'\le X^{-c+O(\xi)} and 1/Aw,w′≤11/A_{w,w'}\le1, is at most X−ζ+4ε+O(ξ)+o(1)X^{-\zeta+4\varepsilon+O(\xi)+o(1)}. This completes the required power saving in both ranges.

The diagonal and small-modulus terms give O(X)O(X), and the intermediate and large-modulus terms give o(X)o(X), even after summing over d≤logXd\le\log X. The second moment in each box is therefore O(X)O(X). Cauchy–Schwarz proves the preimage statement after the discarded upper proportion is taken arbitrarily small.

Added density

The family ℰ\mathcal E overlaps ℬ\mathcal B whenever q>rwq>rw. The added inputs satisfy p>np>\sqrt n and q≤rwq\le rw, so they are also disjoint from the covered family below the square root. For the density on X/2<n≤XX/2<n\le X use u,v,tu,v,t for the logarithmic exponents of w,r,qw,r,q with respect to XX. The region is

0≤u≤1/14,3u≤v≤(1/2−u)/2,v≤t≤min(v+u,1/2−v−u). 0\le u\le 1/14,\quad 3u\le v\le (1/2-u)/2,\quad v\le t\le \min(v+u,1/2-v-u).

Away from the boundary, the prime number theorem gives (1+o(1))X/(2qrw(1−u−v−t)logX)(1+o(1))X/(2qrw(1-u-v-t)\log X) possible pp for each q,r,wq,r,w. Partial summation in the integer ww and the two primes gives the density

∫01/14∫3u(1/2−u)/2∫vmin(v+u,1/2−v−u)dtdvdutv(1−u−v−t)=0.01502759…. \int_0^{1/14}\int_{3u}^{(1/2-u)/2} \int_v^{\min(v+u,1/2-v-u)} \frac{dt\,dv\,du}{t v(1-u-v-t)} =0.01502759\ldots \,.

The bounds in the reduction control the strip near u=0u=0; away from that strip, the integrand is bounded and the other boundary strips cost a vanishing proportion. Summing the dyadic intervals gives the natural density. Taken together, the proved families have natural density approximately 53.46%53.46\%.