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.

Research log for issue #47. The full conjecture remains open.

Let s(n)=σ(n)−ns(n)=\sigma(n)-n be the sum of the proper divisors of nn. If AA is a set of positive integers of natural density zero, the conjecture says that {n≥2:s(n)∈A}\{n\ge2:s(n)\in A\} also has natural density zero.

Literature

The November 2026 search covered the original papers, later preprints and their references, and the problem discussion. No proof or counterexample for arbitrary density-zero sets was found.

The proof route uses Luca and Pomerance's second moment after separating inputs by their small-prime parts. The new calculation retains quadratic congruences modulo prime powers, so it avoids the use of squarefreeness in the original collision count.

A preimage theorem for a family with three large prime factors

Theorem. Fix any η>0\eta>0. Let ℬη\mathcal B_\eta consist of the integers n=pqrwn=pqrw, where p>q>rp>q>r are the three largest distinct prime divisors, none divides ww, and

p≥n1/2+η,r≥nη,q≥nηrw.p\ge n^{1/2+\eta},\qquad r\ge n^\eta,\qquad q\ge n^\eta rw.

For every set AA of natural density zero,

#{n≤X:n∈ℬη,s(n)∈A}=o(X).\#\{n\le X:n\in\mathcal B_\eta,\ s(n)\in A\}=o(X).

There is no parity or deficiency restriction. The proof adapts Luca and Pomerance, §3. It replaces their squarefree-modulus step with two bounds for a quadratic congruence modulo an arbitrary odd modulus.

Reduction to a second moment

Work on X/2<n≤XX/2<n\le X, and put m=qrwm=qrw, ℓ=rw\ell=rw. Enlarge the allowed ranges slightly to use powers of XX in the hypotheses. Split the possible values of logℓ/logX\log\ell/\log X into finitely many intervals of length at most η/16\eta/16. On each interval there are fixed exponents α,β,κ,γ,ϵ>0\alpha,\beta,\kappa,\gamma,\epsilon>0 such that

m≤X1/2−ϵ,r≥Xβ,ℓ≤Xκ,q≥Xα,κ<α,β/2<γ<α.m\le X^{1/2-\epsilon},\quad r\ge X^\beta,\quad \ell\le X^\kappa,\quad q\ge X^\alpha,\quad \kappa\lt\alpha,\quad \beta/2\lt\gamma\lt\alpha .

Here β≤κ\beta\le\kappa. It suffices to show the conclusion on each interval.

Write y(t)=loglogt/logloglogty(t)=\log\log t/\log\log\log t, set Y=y(Xβ)Y=y(X^\beta), and write tYt_Y for the largest YY-smooth divisor of tt. The following conditions can be imposed after discarding an arbitrarily small upper proportion of inputs. Put d=nYd=n_Y. For t=n,m,ℓt=n,m,\ell require

tY=(s(t))Y=gcd(t,σ(t))=d,π∣σ(t)/dfor every prime π≤Y.t_Y=(s(t))_Y=\gcd(t,\sigma(t))=d,\qquad \pi\mid \sigma(t)/d\quad\text{for every prime }\pi\le Y.

For mm also require s(m)≍ms(m)\asymp m, s(m)/φ(s(m))≪1s(m)/\varphi(s(m))\ll1, and ∑j∣σ(m),j>(loglogX)21/j≤1\sum_{j\mid\sigma(m),\, j>(\log\log X)^2}1/j\le1. The implied constants may depend on the permitted exceptional proportion. We also take d≤logXd\le\log X.

Here is the justification for the discards. The small-prime conditions come from Luca and Pomerance's Lemma 2.1, with y(t)y(t) in place of YY. For Xβ≤t≤XX^\beta\le t\le X the interval between these thresholds is contained in a common interval of width o(1)o(1). Removing inputs divisible by the possible prime in that interval costs o(X)o(X). The three prime factors p,q,rp,q,r all exceed YY, so the remaining smooth parts coincide. The reciprocal-divisor condition follows from their Lemma 2.5. Davenport's distribution theorem lets us restrict s(m)/ms(m)/m to a compact subinterval of the positive reals with arbitrarily small exceptional density. The original paper's Theorem 5.1 gives s(s(m))/s(m)=s(m)/m+o(1)s(s(m))/s(m)=s(m)/m+o(1) on a set of density one. This bounds s(m)/φ(s(m))s(m)/\varphi(s(m)) on the same retained range because t/φ(t)≤ζ(2)σ(t)/tt/\varphi(t)\le\zeta(2)\sigma(t)/t. To transfer an exceptional set of cofactors mm to inputs pmpm, use #{p≤X/m}≪X/(mlogX)\#\{p\le X/m\}\ll X/(m\log X). For an exceptional set of ℓ\ell the extra sum over qq costs Oα(1)O_\alpha(1) since ∑Xα≤q≤X1/q=Oα(1)\sum_{X^\alpha\le q\le X}1/q=O_\alpha(1) over primes. An exceptional set of upper density δ\delta has reciprocal sum at most (δ+o(1))logX(\delta+o(1))\log X in the upper-limit sense. Finally ∑n≤Xlog(nY)≪XlogY\sum_{n\le X}\log(n_Y)\ll X\log Y follows by summing prime-power divisibility, so nY>logXn_Y>\log X costs o(X)o(X).

For these inputs s(n)=ps(m)+σ(m)≪Xs(n)=p s(m)+\sigma(m)\ll X. Write R(v)R(v) for the number of retained inputs giving output vv. We prove ∑vR(v)2≪X\sum_v R(v)^2\ll X. Cauchy–Schwarz bounds the preimages of AA by O(X1/2|A∩[1,CX]|1/2)=o(X)O(X^{1/2}|A\cap[1,CX]|^{1/2})=o(X). The exceptional proportion can then be arbitrarily small. The dyadic estimates sum to the stated bound up to XX.

Counting collisions

A collision has the same dd on both inputs, since d=(s(n))Yd=(s(n))_Y. The diagonal contributes at most XX after summing all strata. For distinct cofactors m,m′m,m' put a=s(m),a′=s(m′)a=s(m), a'=s(m'), b=σ(m),b′=σ(m′)b=\sigma(m), b'=\sigma(m'), and dh=gcd(a,a′)dh=\gcd(a,a'). All prime divisors of hh exceed YY. If there is a collision, dh∣b−b′dh\mid b-b'. Also b≠b′b\ne b': otherwise ap=a′p′ap=a'p' and p,p′p,p' exceed both coefficients, forcing p=p′p=p', a=a′a=a' and m=m′m=m'. The two prime variables in the collision equation run along linear forms in one integer variable. The upper-bound sieve used in Luca and Pomerance, (3.7) bounds their count by

≪Xdhmm′(logX)2Dφ(D),D=adha′dh|b−b′|dh.\ll \frac{Xdh}{m m'(\log X)^2}\frac{D}{\varphi(D)}, \qquad D=\frac{a}{dh}\frac{a'}{dh}\frac{|b-b'|}{dh}.

The progression parameter has range of scale Xdh/(mm′)Xdh/(m m'), which exceeds X2ϵX^{2\epsilon}, and both affine forms have nonzero determinant. As in the cited estimate, the local factors are bounded by a constant times D/φ(D)D/\varphi(D).

For h>Xγh>X^\gamma, the collision gives m≡m′(modh)m\equiv m'\pmod h. Writing m=qℓm=q\ell and m′=q′ℓ′m'=q'\ell', the congruences h∣s(m),s(m′)h\mid s(m),s(m') then give

h∣Δ,Δ=ℓσ(ℓ)s(ℓ′)−ℓ′σ(ℓ′)s(ℓ).h\mid \Delta,\qquad \Delta=\ell\sigma(\ell)s(\ell')-\ell'\sigma(\ell')s(\ell).

Indeed gcd(h,ℓσ(ℓ)s(ℓ))=1\gcd(h,\ell\sigma(\ell)s(\ell))=1. A prime of hh in ℓ\ell is excluded by gcd(m,s(m))=d\gcd(m,s(m))=d. If a prime of hh divides σ(ℓ)\sigma(\ell), then it divides qs(ℓ)q s(\ell). It cannot equal qq, because that would make it a common prime of mm and σ(m)\sigma(m) outside dd. It cannot divide s(ℓ)s(\ell) either, by the corresponding gcd condition on ℓ\ell. The claimed congruence follows by solving for qq and q′q'. For Δ≠0\Delta\ne0, fix ℓ,ℓ′\ell,\ell' and one of the τ(|Δ|)=Xo(1)\tau(|\Delta|)=X^{o(1)} possible divisors hh. The congruences put q,q′q,q' in fixed residue classes modulo hh. In dyadic ranges q≍Qq\asymp Q, q′≍Q′q'\asymp Q', their reciprocal sums are O(1/h+1/Q)O(1/h+1/Q) and O(1/h+1/Q′)O(1/h+1/Q'). If the ranges contain a collision, then h≪min(ℓQ,ℓ′Q′)h\ll\min(\ell Q,\ell'Q') by h∣s(m),s(m′)h\mid s(m),s(m'). Consequently the product of the two sums, multiplied by hh, is at most a constant times

1h+1Q+1Q′+hQQ′≪X−γ+X−α+Xκ−α.\frac1h+\frac1Q+\frac1{Q'}+\frac{h}{QQ'} \ll X^{-\gamma}+X^{-\alpha}+X^{\kappa-\alpha}.

This has a power saving in every dyadic range. Summing over hh, the dyadic ranges, and ℓ,ℓ′\ell,\ell' with weights 1/(ℓℓ′)1/(\ell\ell') leaves that saving, up to Xo(1)X^{o(1)}. The factor D/φ(D)≪loglogXD/\varphi(D)\ll\log\log X is harmless here.

For Δ=0\Delta=0 we have ℓ+ℓ2/s(ℓ)=ℓ′+(ℓ′)2/s(ℓ′)\ell+\ell^2/s(\ell)=\ell'+(\ell')^2/s(\ell'). The reduced denominators on the two sides are s(ℓ)/ds(\ell)/d and s(ℓ′)/ds(\ell')/d, since gcd(ℓ2,s(ℓ))=d\gcd(\ell^2,s(\ell))=d. So s(ℓ)=s(ℓ′)s(\ell)=s(\ell'), and strict monotonicity with that denominator gives ℓ=ℓ′\ell=\ell'.

Thus q≠q′q\ne q' and q≡q′(modh)q\equiv q'\pmod h. Choose the order q>q′q>q'. The reciprocal sum of such qq is at most O(logX/h)O(\log X/h), even without primality. Using D/φ(D)≪loglogXD/\varphi(D)\ll\log\log X, the bound τ(s(m′))=Xo(1)\tau(s(m'))=X^{o(1)}, ∑Xα≤q′≤X1/q′=O(1)\sum_{X^\alpha\le q'\le X}1/q'=O(1) over primes, and ∑ℓ≥Xβ1/ℓ2≪X−β\sum_{\ell\ge X^\beta}1/\ell^2\ll X^{-\beta}, the Δ=0\Delta=0 contribution is X1−β+o(1)X^{1-\beta+o(1)} per stratum. This is negligible in total since d≤logXd\le\log X.

Small and intermediate moduli

Suppose h≤Xγh\le X^\gamma. Fix m′m', a divisor h∣s(m′)/dh\mid s(m')/d, and the tail ww. For a collision we must have

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

The residue m′m' is a unit modulo hh. Thus w,σ(w)w,\sigma(w) are units, the congruences determine qrqr and q+rq+r modulo hh, and rr satisfies a monic quadratic modulo hh. For a fixed rr, qq is in a single residue class modulo hh.

We first average over qq, retaining the factor D/φ(D)D/\varphi(D). Factors from a/(dh),a′/(dh)a/(dh),a'/(dh) are bounded by the retained totient ratios. Put Z=(loglogX)2Z=(\log\log X)^2 and W=logXW=\log X. In the factor arising from b−b′b-b', the primes at most ZZ contribute O(logY)O(\log Y) by Mertens' theorem. Those above WW contribute O(1)O(1), since |b−b′|≤XO(1)|b-b'|\le X^{O(1)}. In the middle range, primes dividing hh contribute O(1)O(1) by the totient ratio of a′a'. Those dividing bb contribute O(1)O(1) by the retained bound on the sum of reciprocals of divisors of bb. Define

F=∑Z<π≤W,π∣b−b′π∤hb1π(π prime).F=\sum_{\substack{Z<\pi\le W,\ \pi\mid b-b'\\ \pi\nmid hb}}\frac{1}{\pi} \quad(\pi\text{ prime}).

If F≤1F\le1, the remaining product is bounded. If F>1F>1, use the overall bound D/φ(D)≪loglogXD/\varphi(D)\ll\log\log X. Together,

D/φ(D)≪logY(1+loglogXlogYF).D/\varphi(D)\ll \log Y \left(1+\frac{\log\log X}{\log Y}F\right).

For each summand in FF, the equation b=σ(rw)(q+1)≡b′(modπ)b=\sigma(rw)(q+1)\equiv b'\pmod\pi fixes a single residue class of qq modulo π\pi. Its modulus combines with hh by the Chinese remainder theorem. Brun–Titchmarsh and partial summation bound the harmonic sum of q≥Xαq\ge X^\alpha in this class by O(1/φ(πh))O(1/\varphi(\pi h)): the modulus is at most XγlogXX^\gamma\log X, with γ<α\gamma<\alpha. A noncoprime residue cannot contain any of the eligible primes. As ∑π>Z1/(πφ(π))≪1/Z\sum_{\pi>Z}1/(\pi\varphi(\pi))\ll1/Z, this proves, for each fixed rr in its admissible classes,

∑q1qDφ(D)≪logYφ(h).\sum_q \frac{1}{q}\frac{D}{\varphi(D)} \ll \frac{\log Y}{\varphi(h)}.

For an odd prime power πe\pi^e, a monic quadratic has at most 2π⌊e/2⌋2\pi^{\lfloor e/2\rfloor} roots modulo πe\pi^e. Its roots lie in at most two classes modulo π⌈e/2⌉\pi^{\lceil e/2\rceil}. Both statements follow by completing the square. For a nonzero square with valuation 2j<e2j<e the two unit roots lift to two classes modulo πe−j\pi^{e-j}. For the zero square the roots are multiples of π⌈e/2⌉\pi^{\lceil e/2\rceil}.

For h≤Xβ/2h\le X^{\beta/2}, apply Brun–Titchmarsh to the rr-sum in all root classes modulo hh. Their number is at most B(h)=∏πe∥h2π⌊e/2⌋B(h)=\prod_{\pi^e\parallel h}2\pi^{\lfloor e/2\rfloor}. The resulting contribution for each dd is at most

≪XdlogY(logX)2∑m′1m′∑w1w∑h∣a′/dhB(h)φ(h)2.\ll \frac{Xd\log Y}{(\log X)^2} \sum_{m'}\frac{1}{m'}\sum_w\frac{1}{w} \sum_{h\mid a'/d}\frac{h B(h)}{\varphi(h)^2}.

The final divisor sum is bounded uniformly. At a prime π\pi the sum over all positive exponents is 4/((π−1)(1−1/π)2)=O(1/π)4/((\pi-1)(1-1/\pi)^2)=O(1/\pi), so the product is bounded by a fixed power of a′/φ(a′)a'/\varphi(a'). The reciprocal sums over m′m' and ww are O(logX/(dlogY))O(\log X/(d\log Y)) each, by the Euler product on YY-rough integers. Thus this range contributes O(X/(dlogY))O(X/(d\log Y)).

For Xβ/2<h≤XγX^{\beta/2}<h\le X^\gamma, the quadratic-root cover gives at most 2ω(h)2^{\omega(h)} classes modulo ∏πe∥hπ⌈e/2⌉≥h\prod_{\pi^e\parallel h}\pi^{\lceil e/2\rceil}\ge\sqrt h. Over those classes, the harmonic sum of integers r≥Xβr\ge X^\beta is O(2ω(h)((logX)/h+X−β))O(2^{\omega(h)}((\log X)/\sqrt h+X^{-\beta})). Multiplying by h/φ(h)≪1h/\varphi(h)\ll1 and summing all h∣a′/dh\mid a'/d still yields a power saving, since 2ω(h)τ(a′)=Xo(1)2^{\omega(h)}\tau(a')=X^{o(1)}. The intermediate contribution is negligible in total.

Finally ∑dY-smooth1/d=O(logY)\sum_{d\ \,Y\text{-smooth}}1/d=O(\log Y) by Mertens' theorem. Summing the main contributions, the negligible terms and the diagonal gives ∑vR(v)2≪X\sum_v R(v)^2\ll X, as required.

Remaining gap

This treats arbitrary zero-density target sets on the stated large-prime family. The proof uses pp large for the final two-prime sieve and qq larger than its remaining cofactor to bound the largest collision moduli. These inequalities do not hold on all but o(X)o(X) inputs. A proof or disproof of the full conjecture must control inputs outside this family.

The margins can be removed on a set of density (log2)2({\log 2})^2

Let ℬ\mathcal B be the integers admitting n=pqℓn=pq\ell with p,qp,q prime, p>qℓp>q\ell and q>ℓq>\ell. These inequalities determine the primes uniquely as the two largest prime factors. For every set AA of natural density zero,

#{n≤X:n∈ℬ,s(n)∈A}=o(X),#(ℬ∩[1,X])∼(log2)2X.\#\{n\le X:n\in\mathcal B,\ s(n)\in A\}=o(X), \qquad \#(\mathcal B\cap[1,X])\sim (\log 2)^2 X.

To remove the margins, work on X/2<n≤XX/2<n\le X. For fixed q,ℓq,\ell, the number of choices of pp is O(X/(qℓlogX))O(X/(q\ell\log X)) by the prime number theorem, since qℓ≤Xq\ell\le\sqrt X. Fix 0<η<δ<1/40<\eta<\delta<1/4. The inputs with ℓ≤Xδ\ell\le X^\delta have total count

≪XlogX∑ℓ≤Xδ1ℓ∑ℓ<q≤X1q≪Xδ(1+log(1/δ))+o(X).\ll \frac{X}{\log X} \sum_{\ell\le X^\delta}\frac1\ell \sum_{\ell<q\le X}\frac1q \ll X\delta(1+\log(1/\delta))+o(X).

Here the inner sum is over primes. For ℓ≥2\ell\ge2 it is O(1+log(logX/logℓ))O(1+\log(\log X/\log\ell)) by Mertens' theorem. Summing against 1/ℓ1/\ell gives the displayed bound. The term ℓ=1\ell=1 contributes O(XloglogX/logX)O(X\log\log X/\log X).

Among the remaining inputs, failure of p≥n1/2+ηp\ge n^{1/2+\eta} puts qℓq\ell between constant multiples of X1/2−ηX^{1/2-\eta} and X\sqrt X. The reciprocal sum over these cofactors is O(1+ηlogX)O(1+\eta\log X), giving O(ηX)+o(X)O(\eta X)+o(X) inputs. Failure of q≥nηℓq\ge n^\eta\ell puts qq in (ℓ,Xηℓ)(\ell,X^\eta\ell). As ℓ≥Xδ\ell\ge X^\delta, the prime reciprocal sum there is O(η/δ)+o(1)O(\eta/\delta)+o(1) uniformly in ℓ\ell, again by Mertens. This gives O((η/δ)X)+o(X)O((\eta/\delta)X)+o(X) inputs.

If the largest prime of ℓ\ell is below nηn^\eta, the XηX^\eta-smooth part of nn contains ℓ\ell and hence exceeds XδX^\delta. The average logarithm of this smooth part is O(ηlogX)O(\eta\log X), by summing prime-power divisibility. This excludes a further O((η/δ)X)O((\eta/\delta)X) inputs. Finally, the inputs divisible by a square of a prime at least (X/2)η(X/2)^\eta are o(X)o(X). Outside these exceptions we are in ℬη\mathcal B_\eta. Taking δ=η\delta=\sqrt{\eta} and then η\eta arbitrarily small gives the preimage assertion.

For the density, first let C(T)C(T) count m≤Tm\le T of the form qℓq\ell with q>ℓq>\ell prime. Such representations are unique. The prime number theorem gives

C(T)=∑ℓ≤T(π(T/ℓ)−π(ℓ))∼T∑ℓ≤T1ℓlog(T/ℓ)∼Tlog2.C(T)=\sum_{\ell\le\sqrt T}\big(\pi(T/\ell)-\pi(\ell)\big) \sim T\sum_{\ell\le\sqrt T}\frac{1}{\ell\log(T/\ell)} \sim T\log 2.

The subtracted sum is O(T/logT)O(T/\log T), and the last sum is computed by integrating 1/(tlog(T/t))1/(t\log(T/t)). For n∈ℬn\in\mathcal B, count the possible prime p>mp>m over these m=qℓ≤Xm=q\ell\le\sqrt X. Another use of the prime number theorem gives

#(ℬ∩[1,X])=(1+o(1))X∑m≤Xm=qℓ,q>ℓ1mlog(X/m)+O(X/logX).\#(\mathcal B\cap[1,X]) =(1+o(1)) X\! \sum_{\substack{m\le\sqrt X\\ m=q\ell,\ q>\ell}} \frac1{m\log(X/m)} +O(X/\log X).

Partial summation using C(T)∼Tlog2C(T)\sim T\log 2 multiplies the unrestricted reciprocal sum by log2\log 2. The latter sum tends to log2\log 2 by the same integral. This yields the stated density.

Collisions with a zero cofactor determinant

Write each input as n=pqℓn=pq\ell, with two distinct primes p,qp,q coprime to ℓ\ell. Put a=s(ℓ)a=s(\ell) and b=σ(ℓ)b=\sigma(\ell), and use primes on the coefficients for the other input n′=p′q′ℓ′n'=p'q'\ell'. The shifted-product identity from Pollack, Pomerance, and Thompson, §3 is

as(n)+ℓb=(ap+b)(aq+b). a s(n)+\ell b=(a p+b)(a q+b).

In particular, a collision implies

a′(ap+b)(aq+b)−a(a′p′+b′)(a′q′+b′)=Δ,Δ=a′ℓb−aℓ′b′. a'(a p+b)(a q+b)-a(a'p'+b')(a'q'+b') = \Delta,\qquad \Delta=a'\ell b-a\ell'b'.

Proposition. Fix β>0\beta>0 and 0<c0<C00<c_0<C_0. Consider inputs n=pqℓ≤Xn=pq\ell\le X with ℓ≥Xβ\ell\ge X^\beta, c0ℓ≤s(ℓ)≤C0ℓc_0\ell\le s(\ell)\le C_0\ell, and the small-prime conditions above for n,ℓn,\ell, including d≤logXd\le\log X. The number of ordered pairs of distinct such inputs having s(n)=s(n′)s(n)=s(n') and Δ=0\Delta=0 is O(X1−β+o(1))O(X^{1-\beta+o(1)}). There is no dominance condition on either of the two primes.

In a collision the two small-prime parts d=(s(n))Yd=(s(n))_Y are equal. For Δ=0\Delta=0, the denominator argument above gives ℓ=ℓ′\ell=\ell'. For this common ℓ\ell, set A=s(ℓ)/dA=s(\ell)/d and B=σ(ℓ)/dB=\sigma(\ell)/d. These are relatively prime, and B/AB/A is bounded in terms of c0c_0. The two shifted products are equal. Writing the gcd of Ap+BAp+B and Ap′+BAp'+B as xx yields a factorization

Ap+B=cx,Ap′+B=ex,Aq+B=ey,Aq′+B=cy,gcd(c,e)=1. Ap+B=cx,\quad Ap'+B=ex,\quad Aq+B=ey,\quad Aq'+B=cy,\qquad \gcd(c,e)=1 .

All four integers c,e,x,yc,e,x,y are units modulo AA. Comparing the shifted factors gives c≡e(modA)c\equiv e\pmod A, x≡y(modA)x\equiv y\pmod A, and ey≡B(modA)ey\equiv B\pmod A. If c=ec=e or x=yx=y, the two unordered prime pairs coincide. For distinct inputs, by interchanging the two inputs and the prime labels we may count only c>ec>e and x>yx>y at a constant factor in the bound.

Split the four integers into intervals of the form [H,2H)[H,2H) with HH a power of two. Write C,E,T,UC,E,T,U for the four lower endpoints. In a nonempty box we have C,T≫AC,T\gg A, since the respective differences are positive multiples of AA. Also EU≫AEU\gg A, since ey=Aq+Bey=Aq+B. There are O((EU/A+1)Xo(1))O((EU/A+1)X^{o(1)}) possibilities for e,ye,y: count their possible products in the residue class BB and use the divisor bound. Once e,ye,y are fixed, the other two residue classes allow O(CT/A2)O(CT/A^2) choices of c,xc,x. Finally, the bound n≤Xn\le X gives

CETU≤cexy=(Ap+B)(Aq+B)≪A2X/ℓ. CETU\le cexy=(Ap+B)(Aq+B)\ll A^2X/\ell.

The count per box is thus at most X1+o(1)/(Aℓ)X^{1+o(1)}/(A\ell). There are O((logX)4)O((\log X)^4) boxes, and A≫ℓ/logXA\gg\ell/\log X. Summing over ℓ≥Xβ\ell\ge X^\beta gives the claimed bound.

A second-moment argument on a larger family would still need to handle Δ≠0\Delta\ne0 uniformly in the two tails and the ranges of the prime variables.

The small-cofactor theorem also covers inputs whose largest prime is at most the square root and whose two largest primes have product at least n6/7n^{6/7}. A refinement by prime and cofactor size brings the combined natural density to approximately 51.96%51.96\%.

A third-prime theorem also treats n=pqrwn=pqrw with p>np>\sqrt n and r>w3r>w^3, including inputs with q≤rwq\le rw. The three proved families have combined natural density approximately 53.46%53.46\%.