Erdős essential-component conjecture

Let A={2m3n:m,n≥0}∪{0}A=\{2^m3^n:m,n\ge0\}\cup\{0\} and write σ(B)=infN≥1|B∩[1,N]|/N\sigma(B)=\inf_{N\ge1}|B\cap[1,N]|/N. The question is whether σ(A+(B∪{0}))>σ(B)\sigma(A+(B\cup\{0\}))\gt\sigma(B) for every B⊆ℕB\subseteq\mathbb N with 0<σ(B)<10\lt\sigma(B)\lt1. Ruzsa records it on p. 147 of his 1999 survey. The zero-adjoined convention is the one used there for Schnirelmann density. The 1999 Budapest booklet, Ge and Lê's later discussion, the problem wiki and searches by the set and the expansion formulation revealed no full answer. Ruzsa, pp. 146–147 · Budapest booklet, Problem 1.19 · Ge–Lê · Erdős Problems wiki · Research issue

Equivalent expansion at half density

Write SqS_q for the image of A∩[0,q]A\cap[0,q] in ℤ/qℤ\mathbb Z/q\mathbb Z and let

gk=minX⊆ℤ/2kℤ,|X|=2k−1|X+S2k|−|X|2k.g_k=\min_{X\subseteq\mathbb Z/2^k\mathbb Z,\ |X|=2^{k-1}} \frac{|X+S_{2^k}|-|X|}{2^k}.

Theorem. The conjecture is equivalent to liminfk→∞gk>0\liminf_{k\to\infty}g_k\gt0. If the liminf is zero, then for every 0<α<10\lt\alpha\lt1 there is a set BB for which both σ(B)\sigma(B) and σ(A+(B∪{0}))\sigma(A+(B\cup\{0\})) equal α\alpha. In that construction both lower asymptotic densities also equal α\alpha.

From Schnirelmann density to cyclic groups. Suppose σ(C)=σ(B)=α∈(0,1)\sigma(C)=\sigma(B)=\alpha\in(0,1), where C=A+(B∪{0})C=A+(B\cup\{0\}). Since 1∈A1\in A, each finite prefix of CC has density strictly greater than α\alpha. Indeed, if BB has a first gap in the prefix, it is preceded by a member of BB and is filled by B+1B+1. If there is no gap the prefix has density one. Thus there are Nj→∞N_j\to\infty with |B∩[1,Nj]|/Nj→α|B\cap[1,N_j]|/N_j\to\alpha and |(C\B)∩[1,Nj]|=o(Nj)|(C\setminus B)\cap[1,N_j]|=o(N_j).

These prefixes are asymptotically uniform on the scale NjN_j. To prove it, take a subsequential uniform limit FF of their cumulative counts |B∩[1,tNj]|/Nj|B\cap[1,tN_j]|/N_j on 0≤t≤10\le t\le1. Such limits exist after linear interpolation, by the common Lipschitz bound. We have F(t)≥αtF(t)\ge\alpha t and F(1)=αF(1)=\alpha. Consecutive positive elements of AA have ratio tending to one by Tijdeman's gap theorem. Thus for every fixed 0≤d≤10\le d\le1 choose aj∈Aa_j\in A with aj/Nj→da_j/N_j\to d and aj≤dNja_j\le dN_j. For t+d≤1t+d\le1, the translate by aja_j of the BB-prefix of length ⌊tNj⌋\lfloor tN_j\rfloor lies in CC and contains only o(Nj)o(N_j) points outside BB. Passing to the limit gives F(t+d)−F(d)≥F(t)F(t+d)-F(d)\ge F(t). At d=1−td=1-t this yields F(t)≤α−F(1−t)≤αtF(t)\le\alpha-F(1-t)\le\alpha t. Every limit is therefore F(t)=αtF(t)=\alpha t. Tijdeman, Compositio Mathematica 1974

Choose a power of two qjq_j with Nj/4<qj≤Nj/2N_j/4\lt q_j\le N_j/2. In representatives 1,…,qj1,\ldots,q_j, let Xj=B∩[1,qj]X_j=B\cap[1,q_j] and Yj=(B∩[qj+1,2qj])−qjY_j=(B\cap[q_j+1,2q_j])-q_j. Both sizes are αqj+o(qj)\alpha q_j+o(q_j) by uniformity. Since qj∈Aq_j\in A, we also have |Xj\Yj|=o(qj)|X_j\setminus Y_j|=o(q_j), hence |Yj\Xj|=o(qj)|Y_j\setminus X_j|=o(q_j). A new point of Xj+SqjX_j+S_{q_j} is obtained by either a nonwrapping sum in C\BC\setminus B or a sum wrapping from [qj+1,2qj][q_j+1,2q_j]. In the latter case the original sum is either in C\BC\setminus B or projects into Yj\XjY_j\setminus X_j. These two sets account for at most o(qj)o(q_j) new points. Thus there are cyclic witnesses of density tending to α\alpha and vanishing normalized expansion.

Changing the density of cyclic witnesses. Suppose XjX_j on cyclic groups of orders qjq_j has density tending to β∈(0,1)\beta\in(0,1) and normalized expansion δj→0\delta_j\to0 under SqjS_{q_j}. As 1∈Sqj1\in S_{q_j}, shifting XjX_j by one changes at most 2δjqj2\delta_j q_j points. For a desired density α∈(0,1)\alpha\in(0,1) choose a fixed ll with βl<α<1−(1−β)l\beta^l\lt\alpha\lt1-(1-\beta)^l. The intersection of ll independently shifted copies has expected density tending to βl\beta^l, and the union has expected density tending to 1−(1−β)l1-(1-\beta)^l. Thus some intersection is below α\alpha and some union is above α\alpha for large jj. Start with all shifts zero. If the starting density is at least α\alpha, move the shifts one step at a time to the chosen intersection. Otherwise move them to the chosen union. Each step changes density by at most 2δj2\delta_j, so along the path some set has density in [α,α+2δj][\alpha,\alpha+2\delta_j]. For either intersections or unions, the expansion of the combined set is at most lδjqjl\delta_j q_j, since every newly added point lies in an individual expansion of one of the copies. Delete excess elements to leave exactly ⌈αqj⌉\lceil\alpha q_j\rceil. Expansion increases by at most the number deleted, which is at most 2δjqj2\delta_j q_j. In particular any density bounded away from zero and one yields witnesses at exactly half density along a subsequence of dyadic orders.

From cyclic groups to an infinite set. Take the cyclic witnesses at density ⌈αqj⌉/qj\lceil\alpha q_j\rceil/q_j. Rotate each binary circular pattern to make every prefix have density at least its full density. This is possible by starting just after a minimum of the cumulative sums of the pattern minus its mean. Concatenate the rotated patterns in blocks of lengths qjq_j, passing to a subsequence so fast that (Nj−1+1)(1+log2Nj)=o(qj)(N_{j-1}+1)(1+\log^2 N_j)=o(q_j), where Nj=Nj−1+qjN_j=N_{j-1}+q_j and N0=0N_0=0. The resulting set BB has every prefix of density at least α\alpha. At endpoint NjN_j, contributions to CC from summands of BB at most Nj−1N_{j-1}, or from zero, number at most (Nj−1+1)|A∩[0,Nj]|=o(qj)(N_{j-1}+1)|A\cap[0,N_j]|=o(q_j). Contributions using a member of BB in the last block can only use shifts less than qjq_j. The points they reach by NjN_j are contained in the cyclic expansion of that block's pattern, whose size is αqj+o(qj)\alpha q_j+o(q_j). Therefore |C∩[1,Nj]|/Nj→α|C\cap[1,N_j]|/N_j\to\alpha, proving the converse and the claim for arbitrary α\alpha.

How many intervals a cyclic witness needs

For a half-density set XX in a cyclic group of dyadic order qq, let R(X)R(X) count the maximal runs of consecutive occupied residues, and put E=|X+Sq|−|X|E=|X+S_q|-|X|. Any fixed translate by a sum of hh members of SqS_q adds at most hEhE points outside XX, by the triangle inequality for symmetric differences of equal-sized sets. The mean number of points a translate by an arbitrary residue adds is exactly q/4q/4, so some residue adds at least that many.

For a fixed positive integer hh, every ss in [0,q)[0,q) can be approximated from below by a sum of at most hh elements of AA with error at most Chq/(logq)ηhC_h q/(\log q)^{\eta h}, for some η>0\eta\gt0 independent of hh. Subtract the largest smooth number up to the residual at each step. While the residual is at least q\sqrt q, Tijdeman's upper gap bound shrinks it by a factor at most C/(logq)ηC/(\log q)^\eta. If it drops below q\sqrt q, this is already within the stated error bound for each fixed hh and large qq. Changing the translate by uu changes at most 2R(X)|u|2R(X)|u| points, because each run is an interval. Therefore

q4≤hE+2ChR(X)q(logq)ηh.\frac q4\le hE+2C_hR(X)\frac{q}{(\log q)^{\eta h}}.

If E/q→0E/q\to0, this forces R(X)/(logq)L→∞R(X)/(\log q)^L\to\infty for every fixed LL. In the opposite direction R(X)≤ER(X)\le E, since X+1X+1 has one new point per run. The exact double-base representation theorem of Dimitrov, Jullien and Miller permits h=O(logq/loglogq)h=O(\log q/\log\log q) with zero error for every ss, so all half-density sets satisfy E≫qloglogq/logqE\gg q\log\log q/\log q. These estimates leave open the required uniform linear expansion. Dimitrov–Jullien–Miller, Theorem 1

A Fourier criterion in both directions

For a dyadic order qq, write γq\gamma_q for the best lower bound on the nonzero Fourier modes obtained by weighting the shifts. In formulas,

γq=maxws≥0∑s∈Sqws=1minj≠0modq∑s∈Sqws(1−cos(2πjs/q)).\gamma_q=\max_{\substack{w_s\ge0\\ \sum_{s\in S_q}w_s=1}}\ \min_{j\ne0\bmod q}\ \sum_{s\in S_q}w_s\bigl(1-\cos(2\pi js/q)\bigr).

There is an absolute constant CC such that

γ2k4≤gk≤Cγ2klog(2|S2k|).\frac{\gamma_{2^k}}4\le g_k\le C\sqrt{\gamma_{2^k}\log(2|S_{2^k}|)}.

A uniform positive lower bound on γq\gamma_q proves essentiality, while γqlog(2|Sq|)→0\gamma_q\log(2|S_q|)\to0 along a sequence of dyadic orders disproves it. The first argument is the Fourier expansion estimate used in the theory of essential components. The second uses a Gaussian process on a cyclic group to control the one-sided boundary at half density. Reweighted eigenvalues for general directed vertex expansion are studied by Lau, Tung and Wang. Ruzsa, Essential Components · Ge–Lê, Lemma 10 · Lau–Tung–Wang

For a half-density set XX, let f=1Xf=1_X and use Fourier coefficients normalized by 1/q1/q. Parseval gives

1q∑s∈Sqws|(X+s)\X|=∑j≠0|f̂(j)|2∑s∈Sqws(1−cos(2πjs/q))≥γq4\frac1q\sum_{s\in S_q}w_s|(X+s)\setminus X| =\sum_{j\ne0}|\widehat f(j)|^2\sum_{s\in S_q}w_s(1-\cos(2\pi js/q)) \ge \frac{\gamma_q}{4}

when the weights maximize the lower bound. The union of the translated boundaries has at least their weighted mean size.

For the converse, finite minimax gives a probability distribution μ\mu on the nonzero frequencies such that, for every s∈Sqs\in S_q,

∑j≠0μj(1−cos(2πjs/q))≤γq.\sum_{j\ne0}\mu_j(1-\cos(2\pi js/q))\le\gamma_q.

Take independent standard real Gaussian variables Uj,VjU_j,V_j and set

Zx=∑j≠0μj(Ujcos(2πjx/q)+Vjsin(2πjx/q)),X={x:Zx≥0}.Z_x=\sum_{j\ne0}\sqrt{\mu_j}\bigl(U_j\cos(2\pi jx/q)+V_j\sin(2\pi jx/q)\bigr),\qquad X=\{x:Z_x\ge0\}.

Each ZxZ_x has standard normal law. The process is stationary. Write r(s)=𝔼[ZxZx−s]r(s)=\mathbb E[Z_xZ_{x-s}] and decompose Zx−s=r(s)Zx+WsZ_{x-s}=r(s)Z_x+W_s for each fixed xx. By minimax, 1−r(s)≤γq1-r(s)\le\gamma_q. If γq≥1/2\gamma_q\ge1/2 the claimed upper bound follows from gk≤1/2g_k\le1/2, so assume γq<1/2\gamma_q\lt1/2. The joint Gaussian vector of residuals WsW_s is independent of ZxZ_x, and each residual has variance 1−r(s)2≤2γq1-r(s)^2\le2\gamma_q. Membership of xx in (X+Sq)\X(X+S_q)\setminus X implies Zx<0Z_x\lt0 and |Zx|≤2max(0,maxsWs)|Z_x|\le2\max(0,\max_s W_s). By independence and the bounded normal density, the probability of this event is at most an absolute constant times 𝔼max(0,maxsWs)\mathbb E\max(0,\max_s W_s). For u>0u\gt0 that expectation is at most

log(1+|Sq|)u+uγq.\frac{\log(1+|S_q|)}{u}+u\gamma_q.

This follows by bounding the exponential of the maximum by the sum of the individual exponentials and applying Jensen's inequality. Optimizing in uu bounds the expected normalized expansion by O(γqlog(2|Sq|))O(\sqrt{\gamma_q\log(2|S_q|)}).

The random density b=|X|/qb=|X|/q lies in [1/72,71/72][1/72,71/72] with probability at least 1/61/6. Indeed, the correlations r(y)=∑j≠0μjcos(2πjy/q)r(y)=\sum_{j\ne0}\mu_j\cos(2\pi jy/q) have average zero over yy. At least a third of the shifts have r(y)≤1/2r(y)\le1/2, since all correlations are at least −1-1. For such a shift the chance of opposite Gaussian signs is arccos(r(y))/π≥1/3\arccos(r(y))/\pi\ge1/3, by rotational invariance of two independent standard Gaussians. Consequently 𝔼[2b(1−b)]≥1/9\mathbb E[2b(1-b)]\ge1/9. Outside the stated interval 2b(1−b)≤1/362b(1-b)\le1/36, and inside it 2b(1−b)≤1/22b(1-b)\le1/2. Markov's inequality then gives a realization in the interval with normalized expansion at most a constant times its expectation. Apply the density adjustment with α=1/2\alpha=1/2 and with ll uniform over the interval. This multiplies the expansion by at most an absolute constant and proves the upper bound.

An unconditional lower bound from short sums of powers

For all sufficiently large kk,

γ2k≫(logk)3/2k,gk≫(logk)3/2k.\gamma_{2^k}\gg \frac{(\log k)^{3/2}}{k}, \qquad g_k\gg \frac{(\log k)^{3/2}}{k}.

This improves the lower bound from exact double-base representations by a factor of order logk\sqrt{\log k}.

For an odd integer aa, a row of NN consecutive powers starting at 303^0 satisfies

1N∑n=0N−1cos(2πa3n/2h)≤12(1≤h≤c(logN)3/2)\frac1N\sum_{n=0}^{N-1}\cos(2\pi a3^n/2^h)\le\frac12 \qquad \bigl(1\le h\le c(\log N)^{3/2}\bigr)

for a sufficiently small absolute c>0c\gt0 and all large NN. For h=1h=1 each cosine equals −1-1. For h=2,3h=2,3 the mean of a complete period of cosines is zero by direct evaluation. For h≥4h\ge4 the order of 33 doubles from modulus 2h−12^{h-1} to 2h2^h, so a complete period has zero exponential sum by pairing terms whose exponents differ by 2h−32^{h-3}. Remove complete periods and let RR be the remaining length. If R≤N/2R\le N/2 the bound follows by counting terms. Otherwise use Korobov's short-sum bound as stated in Fuchs, Lemma 7. The absolute value of this remainder is at most

CRexp(−c1(logR)3(hlog2)2).C R\exp\!\left(-c_1\frac{(\log R)^3}{(h\log 2)^2}\right).

Starting at exponent zero instead of one multiplies the odd coefficient by 3−13^{-1} modulo 2h2^h, which preserves the bound. Since R>N/2R\gt N/2, shrinking cc makes the expression at most R/2R/2. Fuchs, Lemmas 4–7

For the modulus 2k2^k, the row with first factor 2m2^m has Nm=1+⌊(k−m)log32⌋N_m=1+\lfloor(k-m)\log_3 2\rfloor shifts. Put K=k−⌈k⌉K=k-\lceil\sqrt{k}\rceil and H=⌊c2(logk)3/2⌋H=\lfloor c_2(\log k)^{3/2}\rfloor with c2c_2 small enough that the row bound holds for every m≤Km\le K and h≤Hh\le H. Indeed Nm≫kN_m\gg\sqrt{k} for these rows. Cover the possible denominator exponents d=1,…,Kd=1,\ldots,K by consecutive blocks of at most HH exponents. For the block starting at d=m+1d=m+1, use the uniform probability distribution on the row 2m3n2^m3^n with 0≤n<Nm0\le n\lt N_m. When a nonzero frequency j/2kj/2^k reduces to a/2da/2^d with aa odd, its cosine mean under that block's distribution is at most 1/21/2, using h=d−mh=d-m. For each remaining exponent dd with K<d≤kK\lt d\le k, include the distribution supported only at 2d−12^{d-1}, where the cosine for that denominator is −1-1.

Mix these M=⌈K/H⌉+k−K=O(k/(logk)3/2)M=\lceil K/H\rceil+k-K=O(k/(\log k)^{3/2}) distributions with equal weights. Every nonzero frequency receives a contribution at least 1/(2M)1/(2M) to the weighted sum defining γ2k\gamma_{2^k}, since its own distribution contributes at least that much and the other summands 1−cos1-\cos are nonnegative. The estimate for gkg_k follows from Parseval. The bound tends to zero and leaves the uniform expansion question open.

A binary digit condition necessary for essentiality

Let T(n)T(n) count changes between adjacent digits in the ordinary binary expansion of 3n3^n. A positive answer to the conjecture would imply

max0≤n≤⌊klog32⌋T(n)≫klogk\max_{0\le n\le\lfloor k\log_3 2\rfloor} T(n) \gg \frac{k}{\log k}

for every sufficiently large kk. In particular, a sequence of kk along which this maximum is o(k/logk)o(k/\log k) would disprove essentiality.

To see this, use the uniform distribution on the kk distinct frequencies j/2k=1/2dj/2^k=1/2^d, 1≤d≤k1\le d\le k, in the minimax formula for γ2k\gamma_{2^k}. Write the residue of ss in kk bits, starting with the least significant bit. For a prefix of length dd, let ldl_d be the length of its terminal run of equal digits. The fractional part of s/2ds/2^d begins with ldl_d identical bits, so its distance to the nearest integer is at most 2−ld2^{-l_d}. Therefore

∑d=1k(1−cos(2πs/2d))≤2π2∑d=1k4−ld≤2π23(number of runs in the k bits).\sum_{d=1}^k\bigl(1-\cos(2\pi s/2^d)\bigr) \le 2\pi^2\sum_{d=1}^k4^{-l_d} \le \frac{2\pi^2}{3}\,(\text{number of runs in the }k\text{ bits}).

In the last inequality, the successive ldl_d inside a run are 1,2,…1,2,\ldots up to its length. For s=2m3n<2ks=2^m3^n\lt2^k, multiplying by 2m2^m and padding to kk bits can add at most two runs to the T(n)+1T(n)+1 runs of 3n3^n. The zero residue has zero cosine cost. Thus

γ2k≪1+max0≤n≤⌊klog32⌋T(n)k.\gamma_{2^k}\ll\frac{1+\max_{0\le n\le\lfloor k\log_3 2\rfloor}T(n)}{k}.

Since |S2k|=O(k2)|S_{2^k}|=O(k^2), the upper bound on gkg_k in terms of γ2k\gamma_{2^k} proves the digit condition. The lower bound for changes in individual powers from Bugeaud and Kaneko's smooth-number estimate is of order logn/loglogn\log n/\log\log n. Bugeaud–Kaneko, Corollary 1.5 and Remark 4.4 · Stephan, Theorem 1.3

A quantitative gain on every sufficiently long prefix

The same bounds give a finite density gain for every BB of Schnirelmann density α∈(0,1)\alpha\in(0,1). There is an absolute c>0c\gt0 such that, for all sufficiently large NN depending only on α\alpha,

|(A+(B∪{0}))∩[1,N]|N≥α+cα(1−α)(loglogN)3/2logN.\frac{|(A+(B\cup\{0\}))\cap[1,N]|}{N} \ge \alpha+c\,\alpha(1-\alpha) \frac{(\log\log N)^{3/2}}{\log N}.

Write C=A+(B∪{0})C=A+(B\cup\{0\}), E=|C∩[1,N]|−αNE=|C\cap[1,N]|-\alpha N and F(t)=|B∩[1,t]|−αtF(t)=|B\cap[1,t]|-\alpha t for integers 0≤t≤N0\le t\le N. Then F(t)≥0F(t)\ge0, F(N)≤EF(N)\le E, and |(C\B)∩[1,N]|≤E|(C\setminus B)\cap[1,N]|\le E. Fix hh large enough that the greedy approximation estimate above has ηh>2\eta h\gt2. Given any tt, choose a sum aa of at most hh members of AA with 0≤N−t−a≤D0\le N-t-a\le D, where D=O(N/(logN)2)D=O(N/(\log N)^2). Translate B∩[1,t]B\cap[1,t] by the summands one at a time, keeping only points in BB at each step. The intermediate sets stay inside [1,N][1,N] and each step loses at most EE points. Therefore B∩[a+1,N]B\cap[a+1,N] contains at least |B∩[1,t]|−hE|B\cap[1,t]|-hE points. Adding the prefix of length aa yields

0≤F(t)≤(h+1)E+D(0≤t≤N).0\le F(t)\le (h+1)E+D \qquad (0\le t\le N).

Choose the dyadic qq with N/4<q≤N/2N/4\lt q\le N/2, and take X=B∩[1,q]X=B\cap[1,q] and Y=(B∩[q+1,2q])−qY=(B\cap[q+1,2q])-q as above. Translation by qq gives |X\Y|≤E|X\setminus Y|\le E. Also |Y|−|X|=F(2q)−2F(q)≤(h+1)E+D|Y|-|X|=F(2q)-2F(q)\le(h+1)E+D, so |Y\X|≤(h+2)E+D|Y\setminus X|\le(h+2)E+D. Every element of (X+Sq)\X(X+S_q)\setminus X lifts to either a point of (C\B)∩[1,2q](C\setminus B)\cap[1,2q] or a point of Y\XY\setminus X after wrapping. Hence |(X+Sq)\X|≤(h+3)E+D|(X+S_q)\setminus X|\le(h+3)E+D.

The Fourier lower bound from Parseval at density β=|X|/q\beta=|X|/q is qγqβ(1−β)q\gamma_q\beta(1-\beta). If E≥(1−α)q/(4(h+1))E\ge(1-\alpha)q/(4(h+1)), the claimed estimate follows at once for sufficiently large NN. Otherwise the estimate for F(q)F(q) and D=o(q)D=o(q) give α≤β≤(1+α)/2\alpha\le\beta\le(1+\alpha)/2. This gives

(h+3)E+D≥12qγqα(1−α).(h+3)E+D\ge \frac12q\gamma_q\alpha(1-\alpha).

Now D=o(qγq)D=o(q\gamma_q) by the short-sum lower bound, so the result follows with an absolute constant. The gain on the right still tends to zero. A positive gain uniform in NN for each α\alpha is the issue in the original conjecture.

Projecting a small boundary to smaller moduli

Let 1≤r<k1\le r\lt k, q=2kq=2^k, q′=2k−rq'=2^{k-r} and S′S' be the projection of SqS_q to ℤ/q′ℤ\mathbb Z/q'\mathbb Z. If gk≤γ2r/16g_k\le\gamma_{2^r}/16, then there is a set X′X' of size q′/2q'/2 satisfying

|X′+S′|−|X′|q′≤Cgk\frac{|X'+S'|-|X'|}{q'}\le C g_k

with an absolute constant CC. In particular gk−r≤Cgkg_{k-r}\le Cg_k, since S′⊇Sq′S'\supseteq S_{q'}. The projected set of shifts retains residues of all the smooth numbers up to 2k2^k.

Take a minimizing half-density set XX modulo qq and put δ=gk\delta=g_k. Write pcp_c for the fraction of a coset cc modulo q′q' occupied by XX. The shifts in q′S2rq'S_{2^r} belong to SqS_q and preserve each coset. Applying the Fourier lower bound inside each coset and averaging yields

1q′∑cpc(1−pc)≤δγ2r.\frac1{q'}\sum_c p_c(1-p_c)\le\frac{\delta}{\gamma_{2^r}}.

For a coset cc, the occupied fraction contributed by X+SqX+S_q is at least Mc=maxs∈S′pc−sM_c=\max_{s\in S'}p_{c-s}. Indeed every translation carrying c−sc-s to cc carries all the points of XX in that coset. Consequently q′−1∑c(Mc−pc)≤δq'^{-1}\sum_c(M_c-p_c)\le\delta. With Xt={c:pc≥t}X_t=\{c:p_c\ge t\}, integrating |(Xt+S′)\Xt|/q′|(X_t+S')\setminus X_t|/q' over 0≤t≤10\le t\le1 gives exactly q′−1∑c(Mc−pc)q'^{-1}\sum_c(M_c-p_c). Some tt in [1/4,3/4][1/4,3/4] therefore has normalized expansion at most 2δ2\delta.

For every such tt we have |1{pc≥t}−pc|≤4pc(1−pc)|1_{\{p_c\ge t\}}-p_c|\le4p_c(1-p_c), so |Xt|/q′|X_t|/q' differs from 1/21/2 by at most 4δ/γ2r≤1/44\delta/\gamma_{2^r}\le1/4. Apply the density adjustment with a fixed ll for this interval of densities. Since 1∈S′1\in S', it yields X′X' of exactly half density with the claimed bound. By the short-sum estimate on γ2r\gamma_{2^r}, whenever gkg_k is small this propagation applies for all r<kr\lt k up to a constant times gk−1(log(1/gk))3/2g_k^{-1}(\log(1/g_k))^{3/2}.