Erdős problem #1192 — wave 8j
Date of live check and computation: 2026-07-28 UTC.
Claim labels used below:
- [a] elementary-rigorous;
- [b] rigorous modulo the named published theorem/source;
- [c] plausible or structural but unverified;
- [d] computational-only.
Page metadata transcriptions are direct source observations rather than
mathematical claims.
0. Mandatory live-page gate
I loaded the live problem page through the
Bright Data browser, not through a datacenter curl, and separately loaded its
The live page reported:
OPEN
0 comments on this problem
0 claimed proofs for this problem
Interested in collaborating None
Currently working on this problem None
It also said that it was last edited on 06 April 2026. Thus the skip condition
does not apply.
Verbatim current statement
For $A\subset \mathbb{N}$ let $f_r(n)$ count the number of solutions to $n=a_1+\cdots+a_r$ with $a_i\in A$.
Does there exist, for all $r\geq 2$, a basis $A$ of order $r$ (so that $f_r(n)>0$ for all large $n$) such that\[\sum_{n\leq x}f_r(n)^2 \ll x\]for all $x$?
Verbatim current known-results text
Erd\H{o}s and R\'{e}nyi proved by the probabilistic method that there exists a set $A$ such that\[\sum_{n\leq x}f_r(n)^2 \ll x\]and\[\lvert A\cap [1,x]\rvert\gg x^{1/r}\]for all $x$.
Ruzsa \cite{Ru90} proved that the answer is yes for $r=2$.
The reference rendered by the endpoint is:
[Ru90] Ruzsa, Imre Z., A just basis. Monatsh. Math. (1990), 145--151.
1. What was obtained
This run does not solve the infinite problem. It gives three checkable
pieces of progress:
1. [a] Critical-energy characterization. The requested estimate is
equivalent to \(D_r(A\cap[1,x])=O(x)\), where \(D_j\) is the \(j\)-fold
additive energy. Together with the basis property, it forces, simultaneously
for every \(1\leq j\leq r\),
\[ |A\cap[1,x]|=\Theta(x^{1/r}),\qquad D_j(A\cap[1,x])=\Theta(x^{j/r}). \]
Thus a solution cannot merely be a thin basis: it must have asymptotically
minimal energy at every lower order.
2. [a] Exact \(r=3\) gluing reduction. In a Ruzsa-style construction that
adjoins a translate \(V+t\) to the accumulated set \(X\), translation
averaging controls all terms having unequal numbers of new-block variables
on the two sides of an energy equation. Precisely two translation-invariant
mixed correlations remain:
\[ C_{11}(V,X)=\sum_d\Delta_{1,V}(d)\Delta_{2,X}(d),\qquad C_{22}(V,X)=\sum_d\Delta_{2,V}(d)\Delta_{1,X}(d). \]
These are the exact higher-order obstruction absent from the \(r=2\) gluing
calculation.
3. [d] Sharp finite computation. I exhaustively determined the globally
minimum ordered three-fold energy of a three-basis of
\(\mathbb Z/m\mathbb Z\) for every \(2\leq m\leq41\). This supplies exact
finite test data and shows that small cyclic three-bases can have
critical-scale local energy. It does not provide the uniform family or the
two mixed-correlation estimates needed for an infinite construction.
2. The critical-energy hierarchy
For a finite set \(S\subset\mathbb Z\), put
\[ R_{j,S}(n)=\#\{(s_1,\ldots,s_j)\in S^j:s_1+\cdots+s_j=n\} \]and
\[ D_j(S)=\sum_nR_{j,S}(n)^2. \]Equivalently, for
\(P_S(\theta)=\sum_{s\in S}e^{2\pi i s\theta}\),
\[ D_j(S)=\int_0^1|P_S(\theta)|^{2j}\,d\theta. \tag{2.1} \]Let \(A_x=A\cap[1,x]\).
Lemma 2.1: equivalence with finite energy
[a] The estimate in the problem is equivalent, up to replacing \(x\) by
\(rx\), to
\[ D_r(A_x)=O(x). \tag{2.2} \]Indeed, positivity of the elements gives
\[ D_r(A_x) \leq \sum_{n\leq rx}f_r(n)^2. \]Conversely, every representation of \(n\leq x\) uses only elements of \(A_x\),
so
\[ \sum_{n\leq x}f_r(n)^2\leq D_r(A_x). \]Lemma 2.2: every lower energy is forced to be minimal
[a] On the probability space \([0,1]\), monotonicity of \(L^p\) norms in
(2.1) gives, for \(1\leq j\leq r\),
\[ D_j(A_x)\leq D_r(A_x)^{j/r}=O(x^{j/r}). \tag{2.3} \]In particular \(D_1(A_x)=|A_x|\), hence
\[ |A_x|=O(x^{1/r}). \tag{2.4} \]If \(A\) is an asymptotic basis of order \(r\), all integers in
\([x,2x]\) are represented once \(x\) is large. Every summand in these
representations belongs to \(A_{2x}\), while the \(|A_{2x}|^r\) ordered tuples
can have at most that many distinct sums. Therefore
\[ |A_{2x}|^r\geq x, \]which, after rescaling, gives
\[ |A_x|=\Omega(x^{1/r}). \tag{2.5} \]Combining (2.4) and (2.5),
\[ |A_x|=\Theta(x^{1/r}). \tag{2.6} \]Finally, pairing every ordered \(j\)-tuple with itself shows
\[ D_j(A_x)\geq |A_x|^j=\Omega(x^{j/r}). \tag{2.7} \]Together with (2.3), this proves
\[ \boxed{D_j(A_x)=\Theta(x^{j/r})\quad(1\leq j\leq r).} \tag{2.8} \]This is a useful necessary-condition hierarchy: at the critical density, all
energies \(D_1,\ldots,D_r\) must be within a constant factor of their diagonal
lower bounds.
3. Exact one-block calculation for \(r=3\)
For \(j\geq0\), define the difference multiplicity
\[ \Delta_{j,S}(d) =\#\{(\mathbf u,\mathbf v)\in S^j\times S^j: \textstyle\sum u_i-\sum v_i=d\}, \]with \(R_{0,S}(0)=1\). Let \(X,V\subset\mathbb Z\), let \(Y=V+t\), and suppose
\(X\cap Y=\varnothing\).
For \(0\leq a,b\leq3\), let \(N_{a,b}(t)\) count an energy equation with exactly
\(a\) designated \(Y\)-variables among the three variables on the left and
\(b\) designated \(Y\)-variables on the right. In convolution notation,
\[ N_{a,b}(t)= \sum_n \bigl(R_{a,Y}*R_{3-a,X}\bigr)(n) \bigl(R_{b,Y}*R_{3-b,X}\bigr)(n). \tag{3.1} \]Exact colour expansion
[a] Sorting each six-tuple by its \(X/Y\) colour pattern gives
\[ D_3(X\cup Y)= \sum_{a,b=0}^3 {3\choose a}{3\choose b}N_{a,b}(t). \tag{3.2} \]If the sets overlap, the right side remains an upper bound.
For equal colour counts, translation cancels. Directly rearranging the energy
equation gives
\[ \begin{aligned} N_{0,0}&=D_3(X),\\ N_{3,3}&=D_3(V),\\ N_{1,1}&=\sum_d\Delta_{1,V}(d)\Delta_{2,X}(d)=C_{11}(V,X),\\ N_{2,2}&=\sum_d\Delta_{2,V}(d)\Delta_{1,X}(d)=C_{22}(V,X). \end{aligned} \tag{3.3} \]In particular, no choice of \(t\) changes either mixed correlation.
Unequal colours are controlled by translation averaging
[a] Fix \(a\ne b\) and fix all underlying \(X\)- and \(V\)-variables. The
corresponding equation has the form
\[ (a-b)t=c \]for a fixed integer \(c\). It has at most one integer solution \(t\).
Consequently, for every finite admissible set of translations \(T\),
\[ \sum_{t\in T}N_{a,b}(t) \leq |V|^{a+b}|X|^{6-a-b}. \tag{3.4} \]After summing the twelve unequal pairs with their binomial coefficients, some
\(t\in T\) satisfies
\[ \sum_{a\ne b}{3\choose a}{3\choose b}N_{a,b}(t) \leq \frac1{|T|} \sum_{a\ne b}{3\choose a}{3\choose b} |V|^{a+b}|X|^{6-a-b}. \tag{3.5} \]At the critical scale
\[ |X|,|V|=O(P),\qquad |T|=\Omega(P^3), \]the right side of (3.5) is \(O(P^3)\). Hence the exact one-step estimate is
\[ D_3(X\cup(V+t)) \leq D_3(X)+D_3(V)+9C_{11}(V,X)+9C_{22}(V,X)+O(P^3). \tag{3.6} \]What the missing lemma must say
[a] The zero-difference portions already have the right size under the
critical hierarchy:
\[ \Delta_{1,V}(0)\Delta_{2,X}(0)=|V|D_2(X)=O(P^3), \] \[ \Delta_{2,V}(0)\Delta_{1,X}(0)=D_2(V)|X|=O(P^3). \]Thus the problem is the off-zero correlation, not the unavoidable diagonal.
[a] A direct Cauchy--Schwarz estimate is insufficient:
\[ C_{11}\leq D_2(V)^{1/2}D_4(X)^{1/2},\qquad C_{22}\leq D_4(V)^{1/2}D_2(X)^{1/2}. \tag{3.7} \]Here I used
\(\sum_d\Delta_{j,S}(d)^2=D_{2j}(S)\).
The desired \(r=3\) hypothesis controls \(D_1,D_2,D_3\), but gives no
\(D_4\) estimate. This pinpoints why the generic energy inequality overshoots.
[a] Therefore a Ruzsa-style geometric block iteration would go through at
the energy-accounting level if one could uniformly construct blocks \(V\) and
admissible translation ranges \(T\) such that:
1. \(|V|=O(P)\), \(D_3(V)=O(P^3)\);
2. \(3V\) contains a long enough interval that all translations in
\(T\), with \(|T|=\Omega(P^3)\), still cover a common required interval;
3. against the accumulated earlier set \(X\),
\[ \sum_{d\ne0}\Delta_{1,V}(d)\Delta_{2,X}(d)=O(P^3),\qquad \sum_{d\ne0}\Delta_{2,V}(d)\Delta_{1,X}(d)=O(P^3). \tag{3.8} \]
[c] Conditions (3.8), together with interval coverage at every scale, are
the precise unresolved design task for this particular block-gluing route.
They are not claimed to be logically necessary for every possible solution of
problem #1192.
4. Exact finite cyclic computation
For \(B\subset\mathbb Z/m\mathbb Z\), define the ordered representation count
\[ \rho_B(s)=\#\{(a,b,c)\in B^3:a+b+c=s\pmod m\} \]and energy
\[ E_3(B)=\sum_{s\in\mathbb Z/m\mathbb Z}\rho_B(s)^2. \]Call \(B\) a cyclic three-basis if \(\rho_B(s)>0\) for every residue.
Completeness of the enumeration
The following parts of the certification logic are [a]:
- Translation invariance lets us impose \(0\in B\).
- If \(|B|=k\), there are only \({k+2\choose3}\) unordered triples with
repetition. Coverage therefore requires
\[ {k+2\choose3}\geq m. \tag{4.1} \]
- Every subset containing \(0\) at each feasible cardinality is enumerated.
Cyclic-gap rotation and reversal retain one or more representatives from
every translation/reflection orbit; both symmetries preserve coverage and
energy.
- The program counts unordered triples with weights \(1,3,6\), and separately
recounts each winning witness using all \(k^3\) ordered triples.
- Since \(\sum_s\rho_B(s)=k^3\), if \(k^3=qm+u\), \(0\leq u
the exact integer lower bound
\[ E_3(B)\geq (m-u)q^2+u(q+1)^2. \tag{4.2} \]
Once (4.2) for cardinality \(k+1\) is at least the best energy found at
cardinality \(k\), monotonicity excludes every larger cardinality. Thus the
reported minimum is global, not merely the minimum at a selected size.
The resulting values are [d]:
| \(m\) | winning \(|B|\) | minimum \(E_3(B)\) | one winner \(B\) |
|---:|---:|---:|:---|
| 2 | 2 | 32 | (0, 1) |
| 3 | 2 | 22 | (0, 1) |
| 4 | 2 | 20 | (0, 1) |
| 5 | 3 | 153 | (0, 1, 2) |
| 6 | 3 | 131 | (0, 1, 3) |
| 7 | 3 | 111 | (0, 1, 3) |
| 8 | 3 | 105 | (0, 1, 3) |
| 9 | 4 | 482 | (0, 1, 3, 4) |
| 10 | 4 | 442 | (0, 1, 2, 5) |
| 11 | 4 | 406 | (0, 1, 2, 5) |
| 12 | 4 | 372 | (0, 1, 3, 7) |
| 13 | 4 | 340 | (0, 1, 3, 9) |
| 14 | 4 | 328 | (0, 1, 4, 6) |
| 15 | 4 | 318 | (0, 1, 3, 10) |
| 16 | 4 | 400 | (0, 1, 4, 5) |
| 17 | 5 | 1001 | (0, 1, 2, 5, 8) |
| 18 | 5 | 949 | (0, 1, 2, 5, 11) |
| 19 | 5 | 899 | (0, 1, 2, 6, 9) |
| 20 | 5 | 875 | (0, 1, 2, 5, 14) |
| 21 | 5 | 805 | (0, 1, 4, 14, 16) |
| 22 | 5 | 809 | (0, 1, 3, 7, 12) |
| 23 | 5 | 815 | (0, 1, 2, 6, 14) |
| 24 | 5 | 745 | (0, 1, 3, 11, 20) |
| 25 | 5 | 1001 | (0, 1, 2, 8, 19) |
| 26 | 6 | 1956 | (0, 1, 2, 5, 9, 15) |
| 27 | 6 | 1886 | (0, 1, 2, 5, 13, 22) |
| 28 | 6 | 1824 | (0, 1, 4, 15, 20, 22) |
| 29 | 6 | 1800 | (0, 1, 2, 6, 10, 17) |
| 30 | 6 | 1718 | (0, 1, 2, 5, 14, 24) |
| 31 | 6 | 1626 | (0, 1, 3, 8, 12, 18) |
| 32 | 6 | 1626 | (0, 1, 3, 7, 19, 24) |
| 33 | 6 | 1628 | (0, 1, 2, 6, 15, 23) |
| 34 | 6 | 1572 | (0, 1, 3, 7, 15, 24) |
| 35 | 6 | 1512 | (0, 1, 3, 7, 16, 24) |
| 36 | 6 | 1530 | (0, 1, 3, 18, 23, 29) |
| 37 | 6 | 1464 | (0, 1, 3, 7, 17, 29) |
| 38 | 6 | 1446 | (0, 1, 3, 18, 25, 30) |
| 39 | 6 | 1442 | (0, 1, 3, 8, 17, 27) |
| 40 | 6 | 1416 | (0, 1, 3, 19, 26, 32) |
| 41 | 7 | 3181 | (0, 1, 3, 7, 12, 15, 25) |
At \(m=41\), the run visited 4,496,388 subsets containing zero over the
feasible cardinalities and evaluated 330,144 canonical dihedral
representatives. The last row is not a local-search output.
[c] The table is evidence that interval/cyclic coverage and critical local
three-energy are mutually compatible at small scales. It does not establish a
uniform constant as \(m\to\infty\), and even a uniform family of these cyclic
objects would still need a lifting/gluing argument controlling (3.8).
5. Primary-source literature audit
1. [b] The page's positive \(r=2\) assertion is consistent with Imre
Ruzsa's A just basis, Monatshefte für Mathematik 109 (1990). The
EuDML record gives pages 145--152, while the
live page and later bibliographies give 145--151. This is only a
bibliographic endpoint discrepancy.
2. [b] Min Tang's
A note on a result of Ruzsa, II,
Bull. Aust. Math. Soc. 82 (2010), 340--347,
DOI 10.1017/S0004972710000353, explicitly states Ruzsa's square-mean
theorem and proves the quantitative bound
\[ \sum_{n\leq N}\sigma_A(n)^2\leq1{,}069{,}693{,}154N \quad (N\geq7.628517798\times10^{27}). \]
Its Lemma 2.6 constructs \(V\subset[0,4p^2)\), \(|V|\leq12p\), with
\([4p^2,6p^2)\subset V+V\), \(\sigma_V\leq256\), and
\(\delta_V\leq176\) apart from at most eleven differences. This verifies
the finite block-and-difference mechanism behind the \(r=2\) comparison in
Section 3; it does not state an \(r\geq3\) extension.
3. [b] Artūras Dubickas's
A basis of finite and infinite sets with small representation function,
Electronic Journal of Combinatorics 19 (2012), P6, studies coefficients
of squares and two-term representation functions. I found no higher-order
square-mean construction in that paper.
4. [b] Cédric Pilatte proved the existence of an
asymptotic Sidon basis of order 3,
Compositio Mathematica 160 (2024). This is highly relevant nearby
progress, but the construction as written is too dense for #1192. It fixes
\(c=0.35\); Definition 3.2, the irreducible-polynomial count, and Lemma 3.4
give \(|S\cap[1,x]|=x^{0.35+o(1)}\) along its construction scales. For any
finite \(S_x=S\cap[1,x]\), the elementary Cauchy bound
\[ D_3(S_x)\geq \frac{|S_x|^6}{3x} \]
is then \(x^{1.1-o(1)}\), not \(O(x)\). Thus Pilatte's set itself is not the
requested critical-density object. This does not rule out a substantially
thinned or redesigned use of the method.
5. [b] A very recent preprint, Wei Niu's
An asymptotic Sidon basis of order \(3-\eta\),
arXiv:2607.11351v2 (submitted 13 July 2026, revised 20 July 2026), strengthens
Pilatte's coverage by arranging a summand at most \(m^{1-\eta}\) for
\(0<\eta<0.0527\). Its stated theorem does not assert the critical
mean-square estimate in #1192.
6. [b] Jain, Pham, Sawhney and Zakharov's
An explicit economical additive basis,
published online in 2025, is again an order-\(2\) result: it constructs
\(A+A=\mathbb N\) with a subpolynomial pointwise representation function.
It does not claim the all-\(r\) square-mean statement.
[c] Searches by the exact phrase “bounded in square mean,” by the displayed
formula, by Ruzsa's title and citations, and through arXiv/current
order-three-basis papers found no primary source claiming #1192 for
\(r\geq3\). This is a search report, not a proof that no such paper exists.
6. Reproduction and independent checks
The standalone standard-library verifier is
runs/verify_erdos1192_wave8j.py.
Run:
python3 runs/verify_erdos1192_wave8j.py
The full run reported:
independent ordered/multiset witness checks: PASS
unpruned symmetry audit through m=12: PASS
r=3 gluing and averaging identities: PASS
...
41 7 3181 (0, 1, 3, 7, 12, 15, 25) 4496388 330144
ALL CHECKS PASSED in 51.05 seconds
External /usr/bin/time measurement on this VM:
WALL_SECONDS=51.09 MAX_RSS_KB=14012
SHA-256 of the verifier:
b76d1849abe75211a8f4a872b7fd380a3efb2e7f4f0ee5d8ca172b6d32a2c6d6
Besides recomputing the table, the verifier:
- directly compares the weighted-unordered counter with an independent
ordered \(k^3\)-loop counter on every listed witness;
- reruns the minima without any symmetry pruning for \(m\leq12\);
- checks (3.2), (3.3), and (3.4) from their definitions on a fresh finite
example;
- checks the finite exact inequalities \(D_j^3\leq D_3^j\), \(j=1,2\), on
every witness.
[c] Extending the table is not the main computational bottleneck relevant
to the infinite problem. For orientation, already at \(m=100\) the first
cardinality allowed by (4.1) is \(k=8\), with
\({99\choose7}=14{,}887{,}031{,}544\) zero-normalized subsets before symmetry;
if size \(9\) were needed there would be another
\({99\choose8}=171{,}200{,}862{,}756\). A naive continuation would therefore
cost tens to hundreds of single-core hours while leaving the uniformity and
mixed-correlation problem untouched. I did not run it.
PARTIAL: Proved the critical-density/lower-energy hierarchy and the exact r=3 block-gluing reduction, and exhaustively certified the minimum cyclic three-basis energy for every modulus 2 through 41; the unresolved uniform step is simultaneous O(P^3) control of the two translation-invariant mixed correlations C11 and C22 while covering consecutive intervals.