Erdős–Ruzsa conjecture

Erdős Problem 1200 asks whether there is a constant KK such that for every sufficiently large NN, residue classes apmodpa_p\bmod p, one for each selected prime p≤Np\le N, cover [1,N][1,N] with ∑p1/p≤K\sum_p1/p\le K. Question 2 in the joint paper asks whether every fixed budget leaves a uniformly positive proportion of survivors. An affirmative answer to that question would disprove the covering conjecture.

The argument below establishes a survivor theorem when there is a common shift on the larger selected primes. The arbitrary-residue conjecture remains open in the sources checked.

Sources

Common shift on the larger primes

Theorem. Fix K,A>0K,A>0 and 0<θ<1/40\lt\theta\lt1/4. Let PP be any set of primes up to NN with ∑p∈P1/p≤K\sum_{p\in P}1/p\le K and choose a residue apmodpa_p\bmod p for each. If there is an integer aa with |a|≤AN|a|\le AN such that ap≡amodpa_p\equiv a\bmod p for every p∈Pp\in P above NθN^\theta, then at least c(K,A,θ)Nc(K,A,\theta)N integers of [1,N][1,N] avoid all the classes for sufficiently large NN.

The lower-prime classes can vary independently, including at primes comparable to NθN^\theta. The choice of shift can vary with NN.

Counting integers with excluded prime factors

Let ff be completely multiplicative with f(p)∈{0,1}f(p)\in\{0,1\}, and suppose that ∑p≤X:f(p)=01/p≤L\sum_{p\le X:f(p)=0}1/p\le L. Put F(x)=∑n≤xf(n)F(x)=\sum_{n\le x}f(n), g=μ*fg=\mu*f and h=|g|h=|g|, where ** is Dirichlet convolution. Thus hh is the indicator of squarefree integers supported on the primes excluded by ff. For 2≤t≤X2\le t\le X,

∑d≤Xh(d)d≤eL,∑d≤th(d)≪Ltlog(2t).\sum_{d\le X}\frac{h(d)}d\le e^L,\qquad \sum_{d\le t}h(d)\ll_L\frac{t}{\log(2t)}.

Indeed, the first bound is an Euler product. Since hh is supported on squarefree integers, ∑d≤th(d)logd≤∑m≤th(m)∑p≤t/mlogp≪teL\sum_{d\le t}h(d)\log d\le\sum_{m\le t}h(m)\sum_{p\le t/m}\log p\ll t e^L. The terms d≤td\le\sqrt t can be counted trivially. From f=1*gf=1*g one gets F(t)/t=∑d≤tg(d)/d+OL(1/log(2t))F(t)/t=\sum_{d\le t}g(d)/d+O_L(1/\log(2t)). Partial summation gives

|F(t)t−F(s)s|≪L1+log(t/s)log(2s)(2≤s≤t≤X).\left|\frac{F(t)}t-\frac{F(s)}s\right| \ll_L\frac{1+\log(t/s)}{\log(2s)} \qquad(2\le s\le t\le X). \tag{1}

We also need a mean square over small primitive characters. For every fixed C>0C>0, uniformly as x→∞x\to\infty with x≤Xx\le X,

∑1<r≤(logx)C∑ψmodr*|∑n≤xf(n)ψ(n)|2=oL,C(x2).\sum_{1\lt r\le(\log x)^C}\ \sum_{\psi\bmod r}^{*} \left|\sum_{n\le x}f(n)\psi(n)\right|^2=o_{L,C}(x^2). \tag{2}

The star indicates primitive characters. Write f=f0+f1f=f_0+f_1 on [1,x][1,x], with f0(n)=∑d∣n,d≤x/Tg(d)f_0(n)=\sum_{d\mid n,\ d\le x/T}g(d) and T=(logx)HT=(\log x)^H, where H>2C+2H>2C+2. For each nonprincipal primitive character of conductor rr, the sum against f0f_0 is bounded by rx/Trx/T by completing periods in the inner sum over n/dn/d. There are O((logx)2C)O((\log x)^{2C}) characters to consider. For f1f_1,

∑n≤x|f1(n)|2≤∑m,m′≤T∑v≤x/[m,m′]h(v)≪Lxlogx∑m,m′≤T1[m,m′]≪L,Hx(loglogx)3logx.\sum_{n\le x}|f_1(n)|^2 \le \sum_{m,m'\le T}\ \sum_{v\le x/[m,m']} h(v) \ll_L \frac{x}{\log x}\sum_{m,m'\le T}\frac1{[m,m']} \ll_{L,H}\frac{x(\log\log x)^3}{\log x}.

Here the cofactor m=n/dm=n/d in a tail term is at most TT. In the product of two tail terms write n=[m,m′]vn=[m,m']v, where brackets denote the least common multiple. The support condition for h(n/m)h(n/m) implies h(v)=1h(v)=1, and all the inner cutoffs satisfy x/[m,m′]≥x/T2x/[m,m']\ge x/T^2. To bound the last double sum, group by b=gcd(m,m′)b=\gcd(m,m'), giving the bound ∑b≤Tb−1(1+log(T/b))2\sum_{b\le T}b^{-1}(1+\log(T/b))^2. The multiplicative large sieve applied to f1f_1 now proves (2).

Distribution over the sieve moduli

Let QQ be a set of primes with ∑p∈Q1/p≤K\sum_{p\in Q}1/p\le K and let 𝒟\mathcal D contain the squarefree products of primes of QQ, including 1. We have ∑d∈𝒟1/φ(d)≤e2K\sum_{d\in\mathcal D}1/\varphi(d)\le e^{2K}. Fix 0<δ<1/20\lt\delta\lt1/2, and choose 0<ϵ<min(δ,1/10)0\lt\epsilon\lt\min(\delta,1/10). In addition to the hypotheses above on ff, assume it is supported on xϵx^\epsilon-smooth integers and f(p)=1f(p)=1 for all p∈Qp\in Q up to w=(logx)1/2w=(\log x)^{1/2}. Then

∑d∈𝒟d≤x1/2−δmax(b,d)=1|∑n≤xn≡bmoddf(n)−F(x)d|=oL,K,δ,ϵ(x).\sum_{\substack{d\in\mathcal D\\ d\le x^{1/2-\delta}}} \max_{(b,d)=1} \left|\sum_{\substack{n\le x\\n\equiv b\bmod d}} f(n) -\frac{F(x)}d\right| =o_{L,K,\delta,\epsilon}(x). \tag{3}

Apply Granville–Shao, Theorem 1.6, with B=3B=3. Its class 𝒞\mathcal C includes 1-bounded completely multiplicative functions. The theorem gives a set of O((logx)26)O((\log x)^{26}) primitive characters and an error O(x/(logx)3)O(x/(\log x)^3) summed over each dyadic range of d≤x1/2−δd\le x^{1/2-\delta} after these characters are subtracted. Enlarge the set to include the principal primitive character if needed. We bound the total contribution of the remaining exceptional characters, including the characters they induce, on 𝒟\mathcal D.

A character of conductor rr can contribute only when r∣dr\mid d, so r∈𝒟r\in\mathcal D. Its total possible weight is at most e2K/φ(r)e^{2K}/\varphi(r). Thus all exceptional characters with r>(logx)60r>(\log x)^{60} contribute o(x)o(x), even with the trivial bound xx on each character sum, using φ(r)≥r/2\varphi(r)\ge\sqrt{r/2}.

For the smaller conductors, let ψ\psi be primitive modulo r>1r>1, and let ψd\psi_d be the character modulo dd induced from ψ\psi. For squarefree dd divisible by rr, complete multiplicativity gives

∑n≤xf(n)ψd(n)=∑e∣d/rμ(e)f(e)ψ(e)∑n≤x/ef(n)ψ(n).\sum_{n\le x}f(n)\psi_d(n) =\sum_{e\mid d/r}\mu(e)f(e)\psi(e)\sum_{n\le x/e}f(n)\psi(n).

Summing the absolute values with weight 1/φ(d)1/\varphi(d) and then over the exceptional characters with r≤(logx)60r\le(\log x)^{60}, the total is at most

e2K∑e∈𝒟1φ(e)∑ψexceptional1<r≤(logx)60r∈𝒟1φ(r)|∑n≤x/ef(n)ψ(n)|.e^{2K}\sum_{e\in\mathcal D}\frac1{\varphi(e)} \sum_{\substack{\psi\ \mathrm{exceptional}\\1\lt r\le(\log x)^{60}\\r\in\mathcal D}} \frac1{\varphi(r)} \left|\sum_{n\le x/e}f(n)\psi(n)\right|. \tag{4}

Indeed, with r,er,e fixed and coprime, write d=recd=rec and sum 1/φ(c)1/\varphi(c). If e>x1/4e>x^{1/4}, the trivial bound x/ex/e for each of the O((logx)26)O((\log x)^{26}) character sums contributes o(x)o(x), using ∑e>V1/(eφ(e))≪V−1/2\sum_{e>V}1/(e\varphi(e))\ll V^{-1/2}. For e≤x1/4e\le x^{1/4}, apply Cauchy–Schwarz to the inner sum in (4). The sum of squares of the weights is at most ∑r∈𝒟1/φ(r)\sum_{r\in\mathcal D}1/\varphi(r), since there are at most φ(r)\varphi(r) characters modulo rr. Equation (2) with x/e≥x3/4x/e\ge x^{3/4} bounds the other factor by o(x/e)o(x/e), uniformly in ee. Summation using ∑e1/(eφ(e))<∞\sum_e 1/(e\varphi(e))\lt \infty completes the estimate of (4).

It follows that the residue counts in (3) can be replaced, with total error o(x)o(x), by φ(d)−1∑n≤x,(n,d)=1f(n)\varphi(d)^{-1}\sum_{n\le x,(n,d)=1} f(n). To replace this principal term by F(x)/dF(x)/d, write d=d0d1d=d_0d_1 where d0d_0 contains the primes up to ww. Dropping the coprimality condition at p∣d1p\mid d_1 changes the unnormalized count by at most x∑p∣d11/px\sum_{p\mid d_1}1/p, and the corresponding change in F(x)φ(d)/dF(x)\varphi(d)/d is bounded by the same expression. Their total weighted cost is

≪xe2K∑p>w1p(p−1)=o(x).\ll x e^{2K}\sum_{p>w}\frac1{p(p-1)}=o(x).

For d0d_0, since f(e)=1f(e)=1 for e∣d0e\mid d_0, Möbius inversion gives ∑e∣d0μ(e)F(x/e)\sum_{e\mid d_0}\mu(e)F(x/e). By (1), each term differs from μ(e)F(x)/e\mu(e)F(x)/e by OL(x(1+loge)/(elogx))O_L(x(1+\log e)/(e\log x)). Here loge≤∑p≤wlogp≪w\log e\le\sum_{p\le w}\log p\ll w. The sum over d∈𝒟d\in\mathcal D of φ(d)−1∑e∣d01/e\varphi(d)^{-1}\sum_{e\mid d_0}1/e is bounded by the Euler product ∏p∈Q(1+(1+1/p)/(p−1))=OK(1)\prod_{p\in Q}(1+(1+1/p)/(p-1))=O_K(1). This gives (3).

Applying the lower sieve

Choose the longer of the portions n<an\lt a and n>an>a of [1,N][1,N]. On it let m=|n−a|m=|n-a|. The numbers mm form an interval (M,X](M,X] of at least (N−1)/2(N-1)/2 integers, with X≤(A+1)NX\le(A+1)N. After translation and possibly reflection the zero classes are those primes with ap≡amodpa_p\equiv a\bmod p. Put the rest in QQ, so all primes of QQ are at most NθN^\theta, and their forbidden residues modulo pp are nonzero.

Choose δ>0\delta>0 with 2θ<1/2−δ2\theta\lt 1/2-\delta, then choose ϵ\epsilon as in (3). Define f(n)f(n) to be the indicator that nn is Nϵ/2N^{\epsilon/2}-smooth and divisible by none of the selected zero-class primes. The reciprocal cost of excluding the zero-class primes and all the primes in (Nϵ/2,X](N^{\epsilon/2},X] is OK,A,ϵ(1)O_{K,A,\epsilon}(1) by Mertens' theorem. Theorem 1 of Erdős–Ruzsa gives F(X)≫K,A,ϵXF(X)\gg_{K,A,\epsilon}X. Equation (1) gives

F(X)−F(M)=X−MXF(X)+o(X)≫K,A,ϵN.F(X)-F(M)=\frac{X-M}{X}F(X)+o(X)\gg_{K,A,\epsilon}N.

For M<X/(logX)2M\lt X/(\log X)^2 use F(M)≤MF(M)\le M, and otherwise use (1). Fix d*d_* with 2θ<d*<1/2−δ2\theta\lt d_*\lt 1/2-\delta and set D=Nd*D=N^{d_*}. To apply (3) to the interval (M,X](M,X], first apply it at x=Xx=X. If M≥X/(logX)2M\ge X/(\log X)^2, apply it also at x=Mx=M, since Nϵ/2≤xϵN^{\epsilon/2}\le x^\epsilon, D≤x1/2−δD\le x^{1/2-\delta} and f(p)=1f(p)=1 for p∈Qp\in Q up to (logx)1/2(\log x)^{1/2}. For smaller MM, the total error at that endpoint for the indicated moduli is bounded by 2M∑d∈𝒟1/d+D=o(N)2M\sum_{d\in\mathcal D}1/d+D=o(N) from the interval count without the weight ff.

For each d∈𝒟d\in\mathcal D, the simultaneous forbidden conditions for the primes dividing dd specify one reduced residue class modulo dd, by the Chinese remainder theorem. The weight of this class in (M,X](M,X] has the form (F(X)−F(M))/d+rd(F(X)-F(M))/d+r_d, where the sum of |rd||r_d| for d≤Dd\le D is o(N)o(N) by (3). Apply the dimension-one lower sieve with density 1/p1/p on QQ, cutoff z=Nθz=N^\theta, and level DD. Its dimension bound follows from Mertens' product over all primes. The lower sieve function is positive at the fixed parameter logD/logz=d*/θ>2\log D/\log z=d_*/\theta>2, and ∏p∈Q(1−1/p)≥e−2K\prod_{p\in Q}(1-1/p)\ge e^{-2K}. Hence the number of survivors with f(m)=1f(m)=1 is ≫K,A,θN\gg_{K,A,\theta}N.

Consequence for deviations from a common shift

Fix K,A,θK,A,\theta as in the theorem. In any bounded-cost full cover, every integer aa with |a|≤AN|a|\le AN must have

∑p∈P,p>Nθap≢amodp1p≥c′(K,A,θ)>0\sum_{\substack{p\in P,\ p>N^\theta\\a_p\not\equiv a\bmod p}}\frac1p \ge c'(K,A,\theta)>0

for large NN. Delete the indicated classes, apply the theorem, and use that the deleted classes cover at most NN times their reciprocal sum plus π(N)=o(N)\pi(N)=o(N) points. In particular, the common-shift theorem also allows independent deviations for all primes above N1−ηN^{1-\eta}, for sufficiently small fixed η\eta depending on K,A,θK,A,\theta, by Mertens' theorem. The proof uses a single shift to make the larger forbidden conditions multiplicative. Independently chosen classes in the middle range lack this feature.