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 LaTeX endpoint.

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.

1. [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.

1. [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

and

Equivalently, for \(P_S(\theta)=\sum_{s\in S}e^{2\pi i s\theta}\),

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

Indeed, positivity of the elements gives

Conversely, every representation of \(n\leq x\) uses only elements of \(A_x\), so

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\),

In particular \(D_1(A_x)=|A_x|\), hence

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

which, after rescaling, gives

Combining (2.4) and (2.5),

Finally, pairing every ordered \(j\)-tuple with itself shows

Together with (2.3), this proves

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

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,

Exact colour expansion

[a] Sorting each six-tuple by its \(X/Y\) colour pattern gives

If the sets overlap, the right side remains an upper bound.

For equal colour counts, translation cancels. Directly rearranging the energy equation gives

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

for a fixed integer \(c\). It has at most one integer solution \(t\). Consequently, for every finite admissible set of translations \(T\),

After summing the twelve unequal pairs with their binomial coefficients, some \(t\in T\) satisfies

At the critical scale

the right side of (3.5) is \(O(P^3)\). Hence the exact one-step estimate is

What the missing lemma must say

[a] The zero-difference portions already have the right size under the critical hierarchy:

Thus the problem is the off-zero correlation, not the unavoidable diagonal.

[a] A direct Cauchy--Schwarz estimate is insufficient:

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;

1. 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

and energy

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<m\), convexity gives

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

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.

1. [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.

1. [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.

1. [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.

1. [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.

1. [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.