Erdős Problem #339 — Positive density of restricted basis representations
Let , and for each positive integer let denote sums of exactly elements of , with repetitions allowed. Use the convention that is an additive basis of order if is the least positive integer such that every sufficiently large nonnegative integer belongs to . Define the restricted sumset
For , write its lower asymptotic density as
The question is whether every additive basis of order satisfies . Erdős and Graham (1980) Hegyvári, Hennecart, and Plagne, “Answer to a Question of Burr and Erdős on Restricted Addition and Related Results”
Background
The question, recorded by Erdős and Graham, contrasts ordinary addition, where a summand may be reused, with restricted addition, where all summands must be distinct. The at-most- convention above is the asymptotic-basis convention stated in the restricted-addition literature: every sufficiently large integer is a sum of at most terms, and is least with this property. The broader subject also studies how gaps in ordinary sum sequences relate to gaps in restricted sum sequences. Erdős and Graham (1980) Hegyvári, Hennecart, and Plagne, “Answer to a Question of Burr and Erdős on Restricted Addition and Related Results”
In 2003, Hegyvári, Hennecart, and Plagne addressed two density conjectures of Erdős and Graham in a paper on restricted addition. One concerns positive upper density for ordinary -fold sums and the corresponding restricted sums; the basis question asks for the stronger lower-density conclusion under a basis hypothesis. Hegyvári, Hennecart, and Plagne (2003) Hegyvári, Hennecart, and Plagne (2003)
References
P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique 28 (1980).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.