← All problems

Erdős Problem #1192 — Bases with bounded second moments of representation counts

46 years old · traced to

For each integer r≥2r\ge 2, does there exist a set Ar⊂NA_r\subset\mathbb N such that, writing fr(n)f_r(n) for the number of solutions of

n=a1+⋯+ar,ai∈Ar,n=a_1+\cdots+a_r,\qquad a_i\in A_r,

ArA_r is a basis of order rr and its representation counts satisfy

∑1≤n≤xfr(n)2≤Crx(x≥1)\sum_{1\le n\le x} f_r(n)^2\le C_r x\qquad(x\ge 1)

for some constant CrC_r? Here “basis of order rr” means that there is an n0n_0 such that fr(n)>0f_r(n)>0 for every integer n≥n0n\ge n_0. Thus the basis condition is eventual positivity; the 1980 survey’s phrase “for every nn” 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 rr of its elements and keep the total squared representation count small. The sum of squares measures aggregate multiplicity: a bound linear in xx limits the average of fr(n)2f_r(n)^2 over integers up to xx, 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 rr. 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

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.