Erdős Problem #1192 — Bases with bounded second moments of representation counts
For each integer , does there exist a set such that, writing for the number of solutions of
is a basis of order and its representation counts satisfy
for some constant ? Here “basis of order ” means that there is an such that for every integer . Thus the basis condition is eventual positivity; the 1980 survey’s phrase “for every ” is not used literally in this formulation. Erdős Problems #1192 Erdős (1980), p. 99
Background
The question asks whether a set can simultaneously cover all sufficiently large integers by sums of exactly of its elements and keep the total squared representation count small. The sum of squares measures aggregate multiplicity: a bound linear in limits the average of over integers up to , but by itself does not ensure that any particular integer has a representation. The additional basis requirement is therefore substantive, not a consequence of the moment bound. Erdős Problems #1192
Erdős stated the question in his 1980 survey immediately after reporting a probabilistic construction due to Rényi and himself. That construction achieves the same linear bound without the asserted basis property, and Erdős proposed that the bound might persist even when the sequence is a basis of order . Erdős (1980), p. 99
References
P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89-115.
Source: P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89-115.
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.