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.

This note extends the divisor-sum collision argument to inputs whose two largest primes leave a small cofactor. The full conjecture remains open. Work is tracked in issue #47.

Counting a bilinear congruence in a box

For positive integers A,B,MA,B,M with gcd(A,B)=1\gcd(A,B)=1, and any integer KK, write

F(u,w)=Auw+B(u+w+1),D=AK+B(B−A). F(u,w)=Auw+B(u+w+1),\qquad D=AK+B(B-A).

Let ν(M)\nu(M) be the number of residue pairs satisfying F(u,w)≡K(modM)F(u,w)\equiv K\pmod M. Take two intervals containing PP and QQ consecutive integers, respectively. For any kk coprime to MM, restrict u,wu,w to one residue class each modulo kk. Let N1,N2N_1,N_2 be the resulting numbers of choices in the two intervals. The number of pairs in the restricted box with F(u,w)≡K(modM)F(u,w)\equiv K\pmod M is

ν(M)N1N2M2+Oϵ(Mϵ[Mgcd(A,M)gcd(D,M)+gcd(D,M)P+QM]). \frac{\nu(M)N_1N_2}{M^2}+ O_\epsilon\left(M^\epsilon \left[\sqrt{M\gcd(A,M)\gcd(D,M)} +\gcd(D,M)\frac{P+Q}{M}\right]\right).

This follows from completion and the Weil bound for Kloosterman sums, as used for modular hyperbolas by Shparlinski, §3.1. The factors involving gcds handle nonunit coefficients and nonunit right-hand sides.

Write em(t)=exp(2πit/m)e_m(t)=\exp(2\pi i t/m) and define

SM(h,j)=∑u,wmodMF(u,w)≡K(modM)eM(hu+jw). S_M(h,j)=\sum_{\substack{u,w\bmod M\\F(u,w)\equiv K\ (\mathrm{mod}\ M)}} e_M(hu+jw).

We first bound these sums for prime power moduli. The Chinese remainder theorem multiplies the bounds, with unit rescalings of the two frequencies that preserve the gcds.

For the elementary product congruence xy≡D(modL)xy\equiv D\pmod L put TL(H,J)=∑xy≡D(modL)eL(Hx+Jy)T_L(H,J)=\sum_{xy\equiv D\ (\mathrm{mod}\ L)}e_L(Hx+Jy). Partition this sum by g=gcd(x,L)g=\gcd(x,L). Then g∣Gg\mid G, where G=gcd(D,L)G=\gcd(D,L), and x=gzx=gz with zz a unit modulo L/gL/g. The congruence fixes yy modulo L/gL/g and summing over its gg lifts gives zero unless g∣Jg\mid J. If g∣Jg\mid J, this part of the sum is gg times the Kloosterman sum modulo L/gL/g with frequencies H,(J/g)(D/g)H,(J/g)(D/g). Because gcd(D/g,L/g)=G/g\gcd(D/g,L/g)=G/g, we have

gcd(H,(J/g)(D/g),L/g)≤(G/g)gcd(H,J,L). \gcd\big(H,(J/g)(D/g),L/g\big) \le (G/g)\gcd(H,J,L).

The Weil bound applied separately to these parts gives |TL(H,J)|≪ϵL1/2+ϵGgcd(H,J,L)|T_L(H,J)|\ll_\epsilon L^{1/2+\epsilon} \sqrt{G\gcd(H,J,L)}. For J=0J=0, the Kloosterman sums become Ramanujan sums, each of absolute value at most gcd(H,L/g)\gcd(H,L/g). This gives |TL(H,0)|≪ϵLϵGgcd(H,L)|T_L(H,0)|\ll_\epsilon L^\epsilon G\gcd(H,L).

Now take a prime power m=πe∥Mm=\pi^e\parallel M. If π∤A\pi\nmid A, the affine change x=Au+Bx=Au+B, y=Aw+By=Aw+B transforms Sm(h,j)S_m(h,j) into a product-congruence sum modulo mm with unit frequency rescalings. If a=vπ(A)>0a=v_\pi(A)>0, then DD is a unit at π\pi because D≡B2(modπ)D\equiv B^2\pmod\pi. For a≥ea\ge e, a trivial bound |Sm(h,j)|≤m|S_m(h,j)|\le m suffices, since each uu gives a unique ww. For 0<a<e0<a<e, use the same change of variables modulo L=πa+eL=\pi^{a+e}. The variables x,yx,y range over B(modπa)B\pmod{\pi^a}, and the condition becomes xy≡D(modL)xy\equiv D\pmod L. The additive projections for the two restrictions express Sm(h,j)S_m(h,j) as an average of TL(H,J)T_L(H,J) over lifts of the frequencies modulo mm, up to factors of modulus one and a unit rescaling by the inverse of A/πaA/\pi^a. If the two frequencies are divisible by πe\pi^e, the probability that both lifts are divisible by πe+i\pi^{e+i} is π−2i\pi^{-2i}. Otherwise the gcd valuation is fixed. Thus the average of gcd(H,J,L)1/2\gcd(H,J,L)^{1/2} is at most gcd(h,j,m)1/2(1+∑i≥1π−3i/2)\gcd(h,j,m)^{1/2}(1+\sum_{i\ge1}\pi^{-3i/2}). In this case G=1G=1 and L=mgcd(A,m)L=m\gcd(A,m). When one frequency is zero and π∣A\pi\mid A, the other coordinate is uniform since every coordinate determines the other one uniquely. Combining all prime powers gives

|SM(h,j)|≪ϵMϵMgcd(A,M)gcd(D,M)gcd(h,j,M),|SM(h,0)|≪ϵMϵgcd(D,M)gcd(h,M). \begin{aligned} |S_M(h,j)| &\ll_\epsilon M^\epsilon \sqrt{M\gcd(A,M)\gcd(D,M)\gcd(h,j,M)},\\ |S_M(h,0)| &\ll_\epsilon M^\epsilon\gcd(D,M)\gcd(h,M). \end{aligned}

The second estimate also holds with the coordinates exchanged.

Let Wi(h)W_i(h) be the sum of eM(−hv)e_M(-h v) over the respective restricted interval. For each d∣Md\mid M, the geometric-series bound gives

∑hmodMh≠0,d∣h|Wi(h)|≪(M/d)log(2M). \sum_{\substack{h\bmod M\\h\ne0,\ d\mid h}} |W_i(h)| \ll (M/d)\log(2M).

Indeed the chosen integers run through a progression of step kk, and multiplying the frequencies by kk permutes the nonzero multiples of dd modulo MM. In the Fourier expansion the zero pair contributes ν(M)N1N2/M2\nu(M)N_1N_2/M^2. For the other pairs, bound gcd(h,j,M)1/2\gcd(h,j,M)^{1/2} by the sum of d\sqrt d over the divisors d∣Md\mid M dividing both frequencies when both are nonzero. The two geometric-series bounds give a total frequency weight at most M2(log(2M))2∑d∣Md−3/2M^2(\log(2M))^2\sum_{d\mid M}d^{-3/2}. When exactly one frequency is zero, use |Wi(0)|=Ni|W_i(0)|=N_i there and bound gcd(h,M)\gcd(h,M) in the other coordinate by the sum of dd over d∣gcd(h,M)d\mid\gcd(h,M). This gives a weight at most NiMτ(M)log(2M)N_i M\tau(M)\log(2M). Dividing by M2M^2 and applying the respective complete-sum bounds gives the stated box estimate.

We also use the bound

ν(M)≤M∑h∣gcd(D,M)1. \nu(M)\le M\sum_{h\mid\gcd(D,M)}1.

For each prime power re∥Mr^e\parallel M with r∣Ar\mid A, the coefficient Au+BAu+B is a unit, so every uu has a unique ww. If r∤Ar\nmid A, the congruence is equivalent to xy≡D(modre)xy\equiv D\pmod{r^e}. For each g=gcd(x,re)∣Dg=\gcd(x,r^e)\mid D, the count is gφ(re/g)≤reg\varphi(r^e/g)\le r^e, which gives the bound by the Chinese remainder theorem.

A preimage theorem below the square root

Theorem. Let 𝒞\mathcal C consist of composite integers with largest prime factor at most n\sqrt n whose two largest prime factors, counted with multiplicity, have product at least n6/7n^{6/7}. For every set 𝒜\mathcal A of natural density zero,

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

The family 𝒞\mathcal C has positive natural density.

Reduction and the collision equation

First fix 0<λ<1/70<\lambda<1/7 and apply the argument to the subfamily whose two largest prime factors have product at least n1−λn^{1-\lambda}. Work in X/2<n≤XX/2<n\le X. A repeated prime factor of size at least (X/2)1/2−λ(X/2)^{1/2-\lambda} occurs on o(X)o(X) inputs. Write the remaining inputs as n=pqℓn=pq\ell, where p>qp>q are the two largest primes, coprime to ℓ\ell. We have

q≫X1/2−λ,q≤X/ℓ,p≤X,ℓ≤Xλ. q\gg X^{1/2-\lambda},\quad q\le\sqrt{X/\ell},\quad p\le\sqrt X,\quad \ell\le X^\lambda.

We may discard an arbitrarily small upper proportion of inputs to require that ℓ=rw\ell=rw with r≥Xβr\ge X^\beta a prime coprime to ww, for some fixed β>0\beta>0. In fact, the inputs with ℓ≤Xδ\ell\le X^\delta cost O(δX)+o(X)O(\delta X)+o(X), by bounding the number of choices of pp by O(X/(qℓlogX))O(X/(q\ell\log X)) and summing prime reciprocals over q≫X1/2−λq\gg X^{1/2-\lambda}. If the largest prime of ℓ\ell is below XβX^\beta and ℓ>Xδ\ell>X^\delta, the XβX^\beta-smooth part of nn exceeds XδX^\delta. This costs O((β/δ)X)O((\beta/\delta)X) by the mean of the logarithm of that smooth part. First choose δ\delta small and then β/δ\beta/\delta small.

Use the small-prime conditions in the main research note for each of n,m=qℓ,ℓn,m=q\ell,\ell, with Y=y(Xβ)Y=y(X^\beta) and d=nY≤logXd=n_Y\le\log X. Require s(ℓ)≍ℓs(\ell)\asymp\ell, s(m)/φ(s(m))≪1s(m)/\varphi(s(m))\ll1, and the reciprocal-divisor condition for σ(ℓ)\sigma(\ell) with threshold (loglogX)2(\log\log X)^2. The same transfer of exceptional sets by prime reciprocal sums works here, since both primes have a fixed power lower bound. In particular, s(n)≪Xs(n)\ll X. It suffices to bound the second moment on the retained set by O(X)O(X). Dependence on the allowed exceptional proportion is harmless.

For a collision with n′=p′q′ℓ′n'=p'q'\ell', the small-prime parts are equal since d=(s(n))Y=(s(n′))Yd=(s(n))_Y=(s(n'))_Y. Put

a=s(ℓ)/d,b=σ(ℓ)/d,t=ℓ/d=b−a,A=s(ℓ′)/d,B=σ(ℓ′)/d,t′=ℓ′/d=B−A. a=s(\ell)/d,\quad b=\sigma(\ell)/d,\quad t=\ell/d=b-a, \qquad A=s(\ell')/d,\quad B=\sigma(\ell')/d,\quad t'=\ell'/d=B-A.

Both coefficient pairs are coprime. Put M=aq+b=s(m)/dM=aq+b=s(m)/d and K=b(q+1)K=b(q+1). For fixed ℓ,ℓ′,q\ell,\ell',q, the collision condition is Mp+K=F(p′,q′)Mp+K=F(p',q'), with FF as above. Define the normalized determinant Δ=Atb−at′B\Delta=Atb-a t'B. The zero-determinant proposition in the main note bounds the off-diagonal collisions with Δ=0\Delta=0 by X1−β+o(1)X^{1-\beta+o(1)}. We now take Δ≠0\Delta\ne0. Two facts are

D=AK+Bt′,aD≡−Δ(modM). D=AK+Bt',\qquad aD\equiv-\Delta\pmod M .

Since gcd(a,M)=1\gcd(a,M)=1, every common divisor of D,MD,M divides Δ\Delta. Also |Δ|≪X3λ|\Delta|\ll X^{3\lambda}.

Sieving three prime variables with the fourth fixed

Split the choices of qq into ranges [Q,2Q)[Q,2Q) with QQ a power of two. For a fixed pair of tails and a fixed qq, split p′,q′p',q' into intervals I,JI,J of the same kind. For each interval for q′q' there are O(1)O(1) possible intervals for p′p' since X/2<p′q′ℓ′≤XX/2<p'q'\ell'\le X. In particular |I||J|≪X/ℓ′|I||J|\ll X/\ell' and |I|+|J|≪X1/2|I|+|J|\ll X^{1/2}. Over the entire box consider pairs (u,w)(u,w) with F(u,w)≡K(modM)F(u,w)\equiv K\pmod M. These determine the integer v=(F(u,w)−K)/Mv=(F(u,w)-K)/M. The retained collisions require u,w,vu,w,v all prime and all above z=Xθz=X^\theta, where θ>0\theta>0 is a sufficiently small fixed constant depending on λ\lambda.

For any squarefree kk coprime to MM, let ρ(k)\rho(k) be the number of residue pairs (u,w)modk(u,w)\bmod k for which k∣uwvk\mid uwv, where v≡M−1(F(u,w)−K)(modk)v\equiv M^{-1}(F(u,w)-K)\pmod k. It is multiplicative by the Chinese remainder theorem. By the box estimate, the number of pairs with k∣uwvk\mid uwv is

ν(M)|I||J|M2ρ(k)k2+O(k2Xo(1)[Mgcd(A,M)gcd(D,M)+gcd(D,M)|I|+|J|M]). \frac{\nu(M)|I||J|}{M^2}\frac{\rho(k)}{k^2} + O\left(k^2 X^{o(1)}\left[ \sqrt{M\gcd(A,M)\gcd(D,M)} +\gcd(D,M)\frac{|I|+|J|}{M}\right]\right).

In each residue pair the numbers of terms in the two intervals are |I|/k+O(1)|I|/k+O(1) and |J|/k+O(1)|J|/k+O(1). Rounding these factors is absorbed by the error using ν(M)/M≤τ(gcd(D,M))\nu(M)/M\le\tau(\gcd(D,M)).

Use Selberg's upper-bound sieve, Theorem 21.1 with the primes 7≤π≤z7\le\pi\le z not dividing MM, and g(π)=ρ(π)/π2g(\pi)=\rho(\pi)/\pi^2. We have 0<g(π)≤4/π0<g(\pi)\le4/\pi and

g(π)≥{3/π−O(1/π2),π∤B,2/π−O(1/π2),π∣B. g(\pi)\ge \begin{cases} 3/\pi-O(1/\pi^2),&\pi\nmid B,\\ 2/\pi-O(1/\pi^2),&\pi\mid B . \end{cases}

The two axes already give 2π−12\pi-1 points. When π∤B\pi\nmid B, the curve F=KF=K contributes at least π−1\pi-1 points and intersects the axes in at most two. This follows by completing the product if AA is a unit and by counting a line otherwise. The upper bound follows from at most two lines or a hyperbola plus the axes.

The reciprocal of the Selberg denominator is at most a constant times ∏(1−g(π))\prod(1-g(\pi)) over the permitted primes up to z1/20z^{1/20}. Indeed, the Euler product with local weights g(π)/(1−g(π))g(\pi)/(1-g(\pi)) defines a distribution on products of these primes in which each prime is present with probability g(π)g(\pi). The expected logarithm of the product is at most (4+o(1))log(z1/20)(4+o(1))\log(z^{1/20}), so at least half the weight is on products at most zz, which are included in the denominator. By Mertens' theorem the reciprocal is therefore

≪1(logX)3(Mφ(M))3∏π∣B(1−1/π)−1≪logY(logX)3. \ll \frac{1}{(\log X)^3} \left(\frac{M}{\varphi(M)}\right)^3 \prod_{\pi\mid B}(1-1/\pi)^{-1} \ll \frac{\log Y}{(\log X)^3}.

The retained totient bound on s(m)s(m) bounds the factor for MM. For BB, primes up to YY contribute O(logY)O(\log Y), primes between YY and (loglogX)2(\log\log X)^2 cost O(1)O(1) by Mertens, and the reciprocal-divisor condition for σ(ℓ′)\sigma(\ell') bounds the product over the remaining primes.

Thus the main contribution per box is at most a constant times

XdlogYℓℓ′Q(logX)3∑h∣gcd(D,M)1. \frac{Xd\log Y}{\ell\ell' Q(\log X)^3} \sum_{h\mid\gcd(D,M)}1.

The sieve error costs the displayed box error without k2k^2 times z6+o(1)z^{6+o(1)}, since the sieve weights the errors for k≤z2k\le z^2 by at most 3ω(k)3^{\omega(k)}.

Summing the errors

Fix the tails and QQ and write Gq=gcd(D,M)G_q=\gcd(D,M) and Jq=gcd(A,M)J_q=\gcd(A,M). Then Gq∣ΔG_q\mid\Delta and Gq,JqG_q,J_q are coprime since gcd(D,A)=1\gcd(D,A)=1. For g∣Ag\mid A and h∣Δh\mid\Delta with gcd(g,h)=1\gcd(g,h)=1, the condition gh∣aq+bgh\mid aq+b puts qq in at most one residue class modulo ghgh because a,ba,b are coprime. Even over all integers qq in the dyadic interval,

∑qJqGq≤∑g∣A,h∣Δgcd(g,h)=1gh#{q:gh∣M}≪(Q+A|Δ|)Xo(1),∑qGq≤∑h∣Δh#{q:h∣M}≪(Q+|Δ|)Xo(1). \begin{aligned} \sum_q \sqrt{J_q G_q} &\le \sum_{\substack{g\mid A,\ h\mid\Delta\\\gcd(g,h)=1}} \sqrt{gh}\,\#\{q:gh\mid M\} \ll (Q+\sqrt{A|\Delta|})X^{o(1)},\\ \sum_q G_q &\le \sum_{h\mid\Delta}h\,\#\{q:h\mid M\} \ll (Q+|\Delta|)X^{o(1)}. \end{aligned}

Here A|Δ|≪X2λ≪Q\sqrt{A|\Delta|}\ll X^{2\lambda}\ll Q since Q≫X1/2−λQ\gg X^{1/2-\lambda} and λ<1/7\lambda<1/7. With M≪ℓQM\ll\ell Q, the sum of the first error term is O(z6+o(1)ℓQ3/2Xo(1))O(z^{6+o(1)}\sqrt{\ell}Q^{3/2}X^{o(1)}), at most z6+o(1)X3/4+o(1)ℓ−1/4z^{6+o(1)}X^{3/4+o(1)}\ell^{-1/4} since Q≤X/ℓQ\le\sqrt{X/\ell}. For the second term use M≫ℓQ/dM\gg\ell Q/d and |I|+|J|≪X|I|+|J|\ll\sqrt X, so its sum is at most z6+o(1)X1/2+o(1)(1+|Δ|/Q)/ℓz^{6+o(1)}X^{1/2+o(1)}(1+|\Delta|/Q)/\ell. We have |Δ|/Q≪X4λ−1/2|\Delta|/Q\ll X^{4\lambda-1/2}.

Summing these bounds over ℓ,ℓ′≤Xλ\ell,\ell'\le X^\lambda and the O((logX)2)O((\log X)^2) pairs of boxes gives exponents at most

3/4+7λ/4+6θ+o(1),max(1/2+λ,5λ)+6θ+o(1), 3/4+7\lambda/4+6\theta+o(1),\qquad \max(1/2+\lambda,5\lambda)+6\theta+o(1),

respectively. Both are less than 11 for sufficiently small fixed θ\theta, so the total error is o(X)o(X).

Summing the main term

All prime factors of h∣gcd(D,M)h\mid\gcd(D,M) exceed YY. If π\pi is such a factor, it divides none of ℓ,ℓ′,a,A,b,B\ell,\ell',a,A,b,B. Indeed π∤qℓ\pi\nmid q\ell by the condition gcd(m,s(m))=d\gcd(m,s(m))=d. Together with π∣aq+b\pi\mid aq+b and gcd(a,b)=1\gcd(a,b)=1 this gives π∤ab\pi\nmid ab. Then Atb≡at′B(modπ)Atb\equiv a t'B\pmod\pi and the gcd conditions on ℓ′\ell' give π∤At′B\pi\nmid A t'B. Also π∤σ(w)\pi\nmid\sigma(w) when ℓ=rw\ell=rw.

For h>X1/10h>X^{1/10}, the sum of 1/Q1/Q over the eligible qq is at most O(1/h+1/Q)O(1/h+1/Q) even over integers. There are Xo(1)X^{o(1)} eligible divisors of Δ\Delta, so this range saves a power of XX and contributes o(X)o(X) in total. For h≤X1/10h\le X^{1/10}, Brun–Titchmarsh bounds the sum of 1/Q1/Q over the primes q∈[Q,2Q)q\in[Q,2Q) in the required class by O(1/(φ(h)logX))O(1/(\varphi(h)\log X)). A class sharing a prime with hh contains no eligible qq. Thus summing the main term over qq costs at most

XdlogYℓℓ′(logX)4H(ℓ,ℓ′),H(ℓ,ℓ′)=∏π∣Δ,π>Yπ∤At′Bσ(w)(1−1π)−1. \frac{Xd\log Y}{\ell\ell'(\log X)^4}\, H(\ell,\ell'),\qquad H(\ell,\ell')= \prod_{\substack{\pi\mid\Delta,\ \pi>Y\\ \pi\nmid A t'B\sigma(w)}} \left(1-\frac1{\pi}\right)^{-1}.

Here the sum of 1/φ(h)1/\varphi(h) over eligible divisors of Δ\Delta is bounded by a constant times HH: at each prime the sum over all exponents is 1+π/(π−1)21+\pi/(\pi-1)^2 and the ratio to (1−1/π)−1(1-1/\pi)^{-1} is 1+O(1/π2)1+O(1/\pi^2).

For each fixed ℓ′\ell' with small-prime part dd, we claim that the weighted sum of HH over the retained tails is

∑ℓ:ℓY=d,Δ≠0H(ℓ,ℓ′)ℓ≪logXdlogY. \sum_{\substack{\ell:\ \ell_Y=d,\ \Delta\ne0}} \frac{H(\ell,\ell')}{\ell} \ll \frac{\log X}{d\log Y}.

To prove this, set Z=(loglogX)2Z=(\log\log X)^2 and W=logXW=\log X. Primes in (Y,Z](Y,Z] cost a bounded factor by Mertens. Primes above WW cost a bounded factor because 0<|Δ|≪X3λ0<|\Delta|\ll X^{3\lambda}. Let TT sum 1/π1/\pi over the primes of HH in (Z,W](Z,W]. For T≤1T\le1, HH is bounded. For T>1T>1, the bound H≪loglogXH\ll\log\log X gives H≪1+(loglogX)TH\ll 1+(\log\log X)T in all cases. For fixed w,ℓ′w,\ell' and an eligible π\pi in this interval, the determinant is a polynomial of degree at most two in rr, since

t=rw/d,b=(r+1)σ(w)/d,a=(rs(w)+σ(w))/d. t=rw/d,\qquad b=(r+1)\sigma(w)/d,\qquad a=(r s(w)+\sigma(w))/d.

Modulo π\pi the constant term is −t′Bσ(w)/d≠0-t'B\sigma(w)/d\ne0. The polynomial has at most two roots, and each residue class has prime reciprocal sum Oβ(1/φ(π))O_\beta(1/\varphi(\pi)) over r≥Xβr\ge X^\beta up to XX by Brun–Titchmarsh. The unrestricted reciprocal sum over those rr is Oβ(1)O_\beta(1). Since wY=dw_Y=d, ∑w1/w≪logX/(dlogY)\sum_w 1/w\ll\log X/(d\log Y) by the Euler product over the YY-rough factors of w/dw/d. Consequently the term from TT costs at most this bound times (loglogX)∑π>Z1/(πφ(π))=O(1)(\log\log X)\sum_{\pi>Z}1/(\pi\varphi(\pi))=O(1). This proves the claim.

Now sum over the O((logX)2)O((\log X)^2) pairs of dyadic intervals for q,q′q,q'. The reciprocal sum over ℓ′\ell' with ℓ′Y=d\ell'_Y=d is also O(logX/(dlogY))O(\log X/(d\log Y)). The two tail sums therefore give O(X/(dlogY))O(X/(d\log Y)) for each dd. The sum of 1/d1/d over YY-smooth integers is O(logY)O(\log Y) by Mertens' theorem. The main terms, errors and diagonal together give O(X)O(X), as required. Cauchy–Schwarz now proves the assertion on the retained inputs, and the discarded upper proportion can be taken arbitrarily small.

Density beyond the dominant-prime family

The family 𝒞\mathcal C is disjoint from the family ℬ\mathcal B in the main note, which has p>np>\sqrt n. For the subfamily 𝒞λ\mathcal C_\lambda with ℓ≤nλ\ell\le n^\lambda, we obtain

limX→∞#(𝒞λ∩[1,X])X=∫0λ−log(1−2u)1−udu. \lim_{X\to\infty}\frac{\#(\mathcal C_\lambda\cap[1,X])}{X} =\int_0^\lambda\frac{-\log(1-2u)}{1-u}\,du.

For a count in (X/2,X](X/2,X], put u=logℓ/logXu=\log\ell/\log X and v=logq/logXv=\log q/\log X. The exponent of pp is 1−u−v+O(1/logX)1-u-v+O(1/\log X). Away from the boundaries the region is 0≤u≤λ0\le u\le\lambda and 1/2−u≤v≤(1−u)/21/2-u\le v\le(1-u)/2. For each q,ℓq,\ell there the prime number theorem counts (1+o(1))X/(2qℓ(1−u−v)logX)(1+o(1))X/(2q\ell(1-u-v)\log X) choices of pp. The integer reciprocal sum in ℓ\ell and prime reciprocal sum in qq converge to the integral

∫0λ∫1/2−u(1−u)/2dvduv(1−u−v)=∫0λ−log(1−2u)1−udu \int_0^\lambda\!\int_{1/2-u}^{(1-u)/2} \frac{dv\,du}{v(1-u-v)} =\int_0^\lambda\frac{-\log(1-2u)}{1-u}\,du

by partial summation and the prime number theorem. Boundary strips of width tending to zero cost a vanishing proportion by the same upper estimates. Summing the dyadic counts proves the density formula, also at λ=1/7\lambda=1/7. By continuity, the density of the inputs lost by using λ<1/7\lambda<1/7 tends to zero as λ→1/7\lambda\to1/7. The preimage assertion thus holds on all of 𝒞\mathcal C. The union ℬ∪𝒞\mathcal B\cup\mathcal C has density

(log2)2+∫01/7−log(1−2u)1−udu, (\log 2)^2+\int_0^{1/7}\frac{-\log(1-2u)}{1-u}\,du,

approximately 50.56%50.56\%.

Refinement using the cofactor and prime exponents

Use the same largest two prime factors p,qp,q in decreasing order, counted with multiplicity, and put ℓ=n/(pq)\ell=n/(pq). Let 𝒟\mathcal D consist of composite inputs with p≤np\le\sqrt n and logarithmic coordinates u=logℓ/lognu=\log\ell/\log n, v=logq/lognv=\log q/\log n in the region

0≤u,1/2−u≤v≤(1−u)/2,5u+3v≤2,9u+v≤2. 0\le u,\qquad 1/2-u\le v\le (1-u)/2,\qquad 5u+3v\le 2,\qquad 9u+v\le 2 .

Corollary. For every natural density-zero set 𝒜\mathcal A, the inputs in 𝒟\mathcal D with s(n)∈𝒜s(n)\in\mathcal A have density zero. The union ℬ∪𝒟\mathcal B\cup\mathcal D has natural density approximately 51.96%51.96\%.

It suffices to prove the corollary on closed rectangles strictly inside the region. The boundaries have density zero by the logarithmic prime-and-integer reciprocal count above. More precisely, omit strips of an arbitrarily small fixed width along the boundary, cover the remaining compact subset by finitely many sufficiently small rectangles, and sum the preimage bounds for these rectangles. The preimage assertion persists under such a finite union, so each second moment needs only to count within one rectangle.

Suppose a rectangle is centered at (u0,v0)(u_0,v_0) with side lengths at most 2ξ2\xi. On X/2<n≤XX/2<n\le X, the tails of both inputs have size Xu0+O(ξ)X^{u_0+O(\xi)}, and q,q′q,q' have size Xv0+O(ξ)X^{v_0+O(\xi)}. The discarded inputs and small-prime conditions are treated as before. The main-term bound also goes through: the region has u≤3/16u\le 3/16 and v≥5/16v\ge 5/16, so the prime intervals in qq have a power margin above the moduli h≤X1/10h\le X^{1/10}. The only change is to keep the sizes in the error terms, using

M=Xu0+v0+O(ξ)+o(1),|I|+|J|≪X1−u0−v0+O(ξ),|Δ|≪X3u0+O(ξ). M=X^{u_0+v_0+O(\xi)+o(1)},\qquad |I|+|J|\ll X^{1-u_0-v_0+O(\xi)},\qquad |\Delta|\ll X^{3u_0+O(\xi)} .

The first term in the box error, after summing over qq and the two tails, uses Q+A|Δ|Q+\sqrt{A|\Delta|} and therefore has two exponents (5u0+3v0)/2(5u_0+3v_0)/2 and (9u0+v0)/2(9u_0+v_0)/2, up to 6θ+O(ξ)+o(1)6\theta+O(\xi)+o(1). The second term uses Q+|Δ|Q+|\Delta| and gives the exponents 1−v01-v_0 and 1+3u0−2v01+3u_0-2v_0, up to the same error. The first two exponents are strictly below one in the interior. For the last two we have v≥5/16v\ge5/16 and 3u−2v≤−1/163u-2v\le-1/16 throughout the region. Taking ξ\xi and the sieve exponent θ\theta small enough proves the power saving on the rectangle.

To compute the density, the upper boundary for vv is U(u)=min((1−u)/2,(2−5u)/3,2−9u)U(u)=\min((1-u)/2,(2-5u)/3,2-9u), with respective intervals [0,1/7][0,1/7], [1/7,2/11][1/7,2/11], and [2/11,3/16][2/11,3/16]. The lower boundary is 1/2−u1/2-u. The integral giving the density of ℬ∪𝒟\mathcal B\cup\mathcal D is

(log2)2+∫03/1611−ulog(U(u)(1−u−U(u))(1−2u))du. (\log 2)^2+ \int_0^{3/16}\frac{1}{1-u} \log\left(\frac{U(u)}{(1-u-U(u))(1-2u)}\right)\,du.

This uses the same prime number theorem count on (X/2,X](X/2,X] and the integral of 1/(v(1−u−v))1/(v(1-u-v)) with respect to vv. Since p≤np\le\sqrt n on 𝒟\mathcal D, its density adds to that of ℬ\mathcal B.