← All problems

Erdős Problem #339 — Positive density of restricted basis representations

46 years old · traced to

Let A⊆Z≥0A\subseteq\mathbb Z_{\ge 0}, and for each positive integer jj let jAjA denote sums of exactly jj elements of AA, with repetitions allowed. Use the convention that AA is an additive basis of order rr if rr is the least positive integer such that every sufficiently large nonnegative integer belongs to ⋃j=1rjA\bigcup_{j=1}^{r}jA. Define the restricted sumset

r×A={a1+⋯+ar:ai∈A for all i, ai≠ak whenever i≠k}.r\times A=\{a_1+\cdots+a_r:a_i\in A\text{ for all }i,\ a_i\ne a_k\text{ whenever }i\ne k\}.

For X⊆Z≥0X\subseteq\mathbb Z_{\ge0}, write its lower asymptotic density as

d‾(X)=lim inf⁡x→∞∣X∩[0,x]∣x.\underline d(X)=\liminf_{x\to\infty}\frac{|X\cap[0,x]|}{x}.

The question is whether every additive basis AA of order rr satisfies d‾(r×A)>0\underline d(r\times A)>0. 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-rr convention above is the asymptotic-basis convention stated in the restricted-addition literature: every sufficiently large integer is a sum of at most rr terms, and rr 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 hh-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).

Source: 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

Never refreshed

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.