Let and write . The question is whether for every with . 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 for the image of in and let
Theorem. The conjecture is equivalent to . If the liminf is zero, then for every there is a set for which both and equal . In that construction both lower asymptotic densities also equal .
From Schnirelmann density to cyclic groups. Suppose , where . Since , each finite prefix of has density strictly greater than . Indeed, if has a first gap in the prefix, it is preceded by a member of and is filled by . If there is no gap the prefix has density one. Thus there are with and .
These prefixes are asymptotically uniform on the scale . To prove it, take a subsequential uniform limit of their cumulative counts on . Such limits exist after linear interpolation, by the common Lipschitz bound. We have and . Consecutive positive elements of have ratio tending to one by Tijdeman's gap theorem. Thus for every fixed choose with and . For , the translate by of the -prefix of length lies in and contains only points outside . Passing to the limit gives . At this yields . Every limit is therefore . Tijdeman, Compositio Mathematica 1974
Choose a power of two with . In representatives , let and . Both sizes are by uniformity. Since , we also have , hence . A new point of is obtained by either a nonwrapping sum in or a sum wrapping from . In the latter case the original sum is either in or projects into . These two sets account for at most new points. Thus there are cyclic witnesses of density tending to and vanishing normalized expansion.
Changing the density of cyclic witnesses. Suppose on cyclic groups of orders has density tending to and normalized expansion under . As , shifting by one changes at most points. For a desired density choose a fixed with . The intersection of independently shifted copies has expected density tending to , and the union has expected density tending to . Thus some intersection is below and some union is above for large . Start with all shifts zero. If the starting density is at least , 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 , so along the path some set has density in . For either intersections or unions, the expansion of the combined set is at most , since every newly added point lies in an individual expansion of one of the copies. Delete excess elements to leave exactly . Expansion increases by at most the number deleted, which is at most . 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 . 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 , passing to a subsequence so fast that , where and . The resulting set has every prefix of density at least . At endpoint , contributions to from summands of at most , or from zero, number at most . Contributions using a member of in the last block can only use shifts less than . The points they reach by are contained in the cyclic expansion of that block's pattern, whose size is . Therefore , proving the converse and the claim for arbitrary .
How many intervals a cyclic witness needs
For a half-density set in a cyclic group of dyadic order , let count the maximal runs of consecutive occupied residues, and put . Any fixed translate by a sum of members of adds at most points outside , 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 , so some residue adds at least that many.
For a fixed positive integer , every in can be approximated from below by a sum of at most elements of with error at most , for some independent of . Subtract the largest smooth number up to the residual at each step. While the residual is at least , Tijdeman's upper gap bound shrinks it by a factor at most . If it drops below , this is already within the stated error bound for each fixed and large . Changing the translate by changes at most points, because each run is an interval. Therefore
If , this forces for every fixed . In the opposite direction , since has one new point per run. The exact double-base representation theorem of Dimitrov, Jullien and Miller permits with zero error for every , so all half-density sets satisfy . These estimates leave open the required uniform linear expansion. Dimitrov–Jullien–Miller, Theorem 1
A Fourier criterion in both directions
For a dyadic order , write for the best lower bound on the nonzero Fourier modes obtained by weighting the shifts. In formulas,
There is an absolute constant such that
A uniform positive lower bound on proves essentiality, while 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 , let and use Fourier coefficients normalized by . Parseval gives
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 on the nonzero frequencies such that, for every ,
Take independent standard real Gaussian variables and set
Each has standard normal law. The process is stationary. Write and decompose for each fixed . By minimax, . If the claimed upper bound follows from , so assume . The joint Gaussian vector of residuals is independent of , and each residual has variance . Membership of in implies and . By independence and the bounded normal density, the probability of this event is at most an absolute constant times . For that expectation is at most
This follows by bounding the exponential of the maximum by the sum of the individual exponentials and applying Jensen's inequality. Optimizing in bounds the expected normalized expansion by .
The random density lies in with probability at least . Indeed, the correlations have average zero over . At least a third of the shifts have , since all correlations are at least . For such a shift the chance of opposite Gaussian signs is , by rotational invariance of two independent standard Gaussians. Consequently . Outside the stated interval , and inside it . 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 and with 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 ,
This improves the lower bound from exact double-base representations by a factor of order .
For an odd integer , a row of consecutive powers starting at satisfies
for a sufficiently small absolute and all large . For each cosine equals . For the mean of a complete period of cosines is zero by direct evaluation. For the order of doubles from modulus to , so a complete period has zero exponential sum by pairing terms whose exponents differ by . Remove complete periods and let be the remaining length. If 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
Starting at exponent zero instead of one multiplies the odd coefficient by modulo , which preserves the bound. Since , shrinking makes the expression at most . Fuchs, Lemmas 4–7
For the modulus , the row with first factor has shifts. Put and with small enough that the row bound holds for every and . Indeed for these rows. Cover the possible denominator exponents by consecutive blocks of at most exponents. For the block starting at , use the uniform probability distribution on the row with . When a nonzero frequency reduces to with odd, its cosine mean under that block's distribution is at most , using . For each remaining exponent with , include the distribution supported only at , where the cosine for that denominator is .
Mix these distributions with equal weights. Every nonzero frequency receives a contribution at least to the weighted sum defining , since its own distribution contributes at least that much and the other summands are nonnegative. The estimate for follows from Parseval. The bound tends to zero and leaves the uniform expansion question open.
A binary digit condition necessary for essentiality
Let count changes between adjacent digits in the ordinary binary expansion of . A positive answer to the conjecture would imply
for every sufficiently large . In particular, a sequence of along which this maximum is would disprove essentiality.
To see this, use the uniform distribution on the distinct frequencies , , in the minimax formula for . Write the residue of in bits, starting with the least significant bit. For a prefix of length , let be the length of its terminal run of equal digits. The fractional part of begins with identical bits, so its distance to the nearest integer is at most . Therefore
In the last inequality, the successive inside a run are up to its length. For , multiplying by and padding to bits can add at most two runs to the runs of . The zero residue has zero cosine cost. Thus
Since , the upper bound on in terms of proves the digit condition. The lower bound for changes in individual powers from Bugeaud and Kaneko's smooth-number estimate is of order . 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 of Schnirelmann density . There is an absolute such that, for all sufficiently large depending only on ,
Write , and for integers . Then , , and . Fix large enough that the greedy approximation estimate above has . Given any , choose a sum of at most members of with , where . Translate by the summands one at a time, keeping only points in at each step. The intermediate sets stay inside and each step loses at most points. Therefore contains at least points. Adding the prefix of length yields
Choose the dyadic with , and take and as above. Translation by gives . Also , so . Every element of lifts to either a point of or a point of after wrapping. Hence .
The Fourier lower bound from Parseval at density is . If , the claimed estimate follows at once for sufficiently large . Otherwise the estimate for and give . This gives
Now 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 for each is the issue in the original conjecture.
Projecting a small boundary to smaller moduli
Let , , and be the projection of to . If , then there is a set of size satisfying
with an absolute constant . In particular , since . The projected set of shifts retains residues of all the smooth numbers up to .
Take a minimizing half-density set modulo and put . Write for the fraction of a coset modulo occupied by . The shifts in belong to and preserve each coset. Applying the Fourier lower bound inside each coset and averaging yields
For a coset , the occupied fraction contributed by is at least . Indeed every translation carrying to carries all the points of in that coset. Consequently . With , integrating over gives exactly . Some in therefore has normalized expansion at most .
For every such we have , so differs from by at most . Apply the density adjustment with a fixed for this interval of densities. Since , it yields of exactly half density with the claimed bound. By the short-sum estimate on , whenever is small this propagation applies for all up to a constant times .