Ruzsa (1990) — a basis of order 2 with representation function bounded in square mean, $\\sum_{n\\le N}\\sigma_A(n)^2=O(N)$

Statement

**Question (Erdős–Turán, 1941; restated by Erdős across dozens of papers, Erdős #28 — additive basis forces unbounded representations). Does there exist a set $A\subseteq\mathbb N$ that is an additive basis of order 2 — i.e. every sufficiently large $n$ can be written as $n=a+a'$ with $a,a'\in A$ — for which the (ordered) representation function $$\sigma_A(n) := \#\{(a,a')\in A\times A : a+a'=n\}$$ is uniformly bounded (i.e. $\sigma_A(n)\le C$ for some constant $C$ and all $n$)? Erdős conjectured no: every basis of order 2 must have $\limsup_n \sigma_A(n)=\infty$. This full ($L^\infty$) conjecture is still open** (Erdős #28 — additive basis forces unbounded representations).

Ruzsa's weaker, solved question (1990). Can $\sigma_A(n)$ at least be bounded on average, in the square-mean (an $L^2$) sense, for a genuine basis $A$ (so $A+A$ covers all sufficiently large $n$)?

Facts

- Source: I. Z. Ruzsa, "A just basis," *Monatshefte für Mathematik* 109 (1990), 145–151. - Answer: yes. Ruzsa constructs a set $A$ of nonnegative integers forming a basis of order 2 ($\sigma_A(n)\ge1$ for all $n$) with $$\sum_{n\le N}\sigma_A(n)^2 = O(N).$$ Since $\sum_{n\le N}\sigma_A(n) \asymp |A\cap[1,N]|^2 \asymp N$ for any basis of order 2 (Cauchy–Schwarz-comparable counting), $O(N)$ is exactly the *best possible* order for the square-mean sum — this is a genuinely sharp result, not just "finite." - **What this does *not* say. An $L^2$ (average) bound is compatible with $\sigma_A(n)$ being unbounded (even $\to\infty$) on a sparse set of $n$, as long as those spikes are rare enough that their squares don't dominate the sum over $[1,N]$. So Ruzsa's theorem gives zero direct information** about the Erdős–Turán conjecture's $L^\infty$/$\limsup$ claim — it is compatible with either a "yes" or "no" resolution of Erdős #28 — additive basis forces unbounded representations. This gap was explicitly flagged (and an over-claim of relevance explicitly retracted) in the April 2026 erdosproblems.com forum thread on the closely related Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open (per wiki/problems/28.md's independently-verified Facts). - The paper explicitly answers "a related finite problem" first. Per the abstract itself, Ruzsa's route runs through a finite/periodic sub-question before assembling the infinite $\mathbb N$-basis. Two independent secondary sources (Ding–Zhao 2023, arXiv:2307.12311; Sándor–Yang 2017/arXiv:1612.08722) confirm, in near-identical language, that "Ruzsa's method implies that there exists a constant $C$ such that for any positive integer $m$, there exists an additive basis $A\subseteq\mathbb Z_m$ with $\sigma_A(n)\le C$ for all $n\in\mathbb Z_m$" — i.e. the finite/periodic byproduct of the *same* construction is a uniform pointwise ($L^\infty$) bound, strictly stronger than the $L^2$ statement claimed for the infinite object on $\mathbb N$. - This finite byproduct founded a whole sub-literature: "Ruzsa's number" $R_m$, defined (Y.-G. Chen, 2008) as the least $r$ such that some $A\subseteq\mathbb Z_m$ has $1\le\sigma_A(n)\le r$ for all $n\in\mathbb Z_m$. Ruzsa's 1990 argument gives the *existence* of a finite uniform $C$; the numerical value has been progressively sharpened: - Tang, M.; Chen, Y.-G., "A basis of $\mathbb Z_m$," *Colloq. Math.* 104 (2006), 99–103: $R_m\le768$ for all sufficiently large $m$ (using Ruzsa's construction directly). - Tang, Chen, "A basis of $\mathbb Z_m$, II," *Colloq. Math.* 108 (2007), 141–145: $R_m\le5120$ for all $m$ (not just large $m$). - Y.-G. Chen, "The analogue of Erdős–Turán conjecture in $\mathbb Z_m$," *J. Number Theory* 128 (2008), 2573–2581: $R_m\le288$ for all $m$ (and $R_{2p^2}\le48$ for primes $p$), via a different, sharper construction. - Ding, Y.; Zhao, L., "A new upper bound on Ruzsa's number on the Erdős–Turán conjecture," arXiv:2307.12311 (2023): $R_m\le192$ for all $m$ — current published record. - Lower bound: Sándor, C.; Yang, Q.-H., "A lower bound of Ruzsa's number related to the Erdős–Turán conjecture," *Acta Arith.* 180 (2017), 161–169, arXiv:1612.08722: $R_m\ge6$ for all $m\ge36$ (with all exact values of $R_m$ tabulated for $m\le35$), improving Chen's trivial $R_m\ge3$. - Why $L^\infty$ genuinely fails on $\mathbb N$ but succeeds on $\mathbb Z$ — the sharpest available context for what makes Ruzsa's result only $L^2$. Nathanson, M. B. (2003) proved the full Erdős–Turán conjecture is false on the integers $\mathbb Z$: there exists $A\subseteq\mathbb Z$ with $1\le\sigma_A(n)\le2$ for all $n\in\mathbb Z$ — a genuinely bounded ($L^\infty$), not just $L^2$, basis. This is possible on $\mathbb Z$ because negative numbers give an extra degree of freedom (a signed-digit-type construction) that is simply unavailable on $\mathbb N$; this precise asymmetry is exactly why Erdős's conjecture is stated for $\mathbb N$/asymptotic bases and remains open there, and it frames why Ruzsa (working on $\mathbb N$) could only reach the average ($L^2$) statement, not the pointwise one Nathanson later achieved in the easier signed setting. - Direct unconditional $L^\infty$ partial results on $\mathbb N$ (for contrast, none due to Ruzsa): Grekos, Haddad, Helou, Pihko (2003): any basis has $\limsup\sigma_A(n)\ge6$. Borwein, Choi, Chu (2006), *Math. Comp.* 75: improved to $\limsup\sigma_A(n)\ge8$ (also phrased "must eventually exceed 7" in some citing sources). Sándor (2008): if $\limsup\sigma_A(n)=K$ then $\liminf\sigma_A(n)\le K-2\sqrt K+1$. Konstantoulas (2013): near-cofinite $A+A$ (upper density of complement $<1/10$) forces $\sigma_A(n)>5$ infinitely often. None of these use Ruzsa's technique; they are finite pigeonhole/counting arguments on the $L^\infty$ statement directly, and none scale to "unbounded."

Solution

The transferable technique — solve the finite/periodic version with a uniform pointwise bound, then let scale-separated gluing convert "pointwise bounded on every finite piece" into "only average-bounded over the whole infinite object."

The reconstruction below is triangulated from the paper's abstract plus two independent, directly-verified secondary sources that report the *same* two-step structure; it is not a reading of Ruzsa's actual proof (paywalled — see provenance), and is offered as the best-available account of the recipe, consistent with how this wiki's own Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open page independently documents the identical "block → packet → lacunary-scale gluing" recipe as a technique family Ruzsa 1990 is credited with originating.

1. Reduce to a finite, $m$-uniform sub-problem. Instead of attacking $\mathbb N$ directly, first solve: does there exist, for every modulus $m$, a set $A_m\subseteq\mathbb Z_m$ with $\sigma_{A_m}(n)\ge1$ for all $n\in\mathbb Z_m$ (a genuine periodic basis) and $\sigma_{A_m}(n)\le C$ for all $n$, with $C$ independent of $m$? This is a strictly finite, and *pointwise* (not merely average), question — decidable in principle for each $m$, and the uniformity-in-$m$ is what makes the construction reusable at every scale. Ruzsa answers this "yes" (the byproduct that later founded the Ruzsa-number literature, $R_m\le C$ for an explicit constant). 2. Lift each periodic block to a finite interval of $\mathbb N$. A basis $A_m\subseteq\mathbb Z_m$ with bounded $\sigma_{A_m}$ gives, via any lift of residues to $\{0,\dots,m-1\}$, a finite set covering an interval of length $\sim m$ with the same bounded local representation count. 3. Glue infinitely many such blocks across rapidly growing (scale-separated) intervals of $\mathbb N$. Place blocks at moduli $m_1\ll m_2\ll\cdots$ growing fast enough that sums straddling two different blocks cannot collide with (or only contribute boundedly many extra representations to) sums that lie entirely within one block — the same scale-separation principle later formalized explicitly, for a structurally related problem, as "no cross terms between old and new packets" in Bhalla's 2026 resolution of the upper-density case of Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open (wiki/problems/749.md, Layer 3). 4. Why the assembled infinite set is only $L^2$-bounded, not $L^\infty$-bounded. Within any single block, $\sigma_A$ stays $\le C$ by construction. But nothing in this recipe prevents the total representation count at a boundary point $n$ from picking up contributions summed across several blocks (e.g. if $n$ happens to be expressible as $a+a'$ using elements from more than one block, or lies near a block boundary where multiple nearby blocks all contribute). As more blocks are laid down, a given $n$ can in principle draw contributions from a growing number of them, so no uniform-in-$n$ cap survives the gluing — but each individual contribution is small and increasingly rare as the blocks grow, so that $\sum_{n\le N}\sigma_A(n)^2$, an $L^2$/energy quantity, stays controlled at $O(N)$ even though the pointwise $L^\infty$ bound present inside each block does not propagate to the assembled infinite object. This "pointwise-bounded pieces, only energy-bounded whole" trade-off is precisely the gap between Ruzsa's solved $L^2$ result and the still-open $L^\infty$ Erdős–Turán conjecture. 5. Sharpen the finite gadget, not the gluing, to improve constants. All of the post-1990 numerical progress on $R_m$ (Tang–Chen $768\to5120\to$ Chen $288\to$ Ding–Zhao $192$) attacks step 1 only — finding better finite/periodic bounded-representation bases in $\mathbb Z_m$ — while re-using variants of Ruzsa's original gluing idea (or simply working with the periodic object $\mathbb Z_m$ directly, sidestepping gluing altogether for the finite question). This is itself the transferable meta-lesson: once a "finite gadget + scale-separated gluing" architecture exists, subsequent papers can improve the *gadget* in isolation without re-deriving the *assembly*.

Why this is the reusable part. The general shape — (i) isolate a finite/periodic sub-question that is *pointwise* (not average) solvable with a uniform-in-scale constant; (ii) lift solutions to finite intervals; (iii) glue across rapidly-separated scales so cross-block interactions stay rare/bounded in aggregate even though no uniform cap survives pointwise; (iv) let later work sharpen the finite gadget alone — is exactly the architecture this wiki's Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open page documents in fully worked-out, verified detail for Bhalla's 2026 resolution of the *upper-density* variant of the closely related problem, one technical generation later. Ruzsa 1990 is the earliest instance of this "finite-gadget-then-lacunary-gluing" recipe found for this problem family, making it the natural first stop for anyone attempting the still-open lower-density case of Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open or the flagship Erdős #28 — additive basis forces unbounded representations itself, even though (as Erdős #28 — additive basis forces unbounded representations's own Facts explicitly note) an $L^2$-type result by itself carries zero logical weight toward the $L^\infty$ conjecture.

Related

- Erdős #28 — additive basis forces unbounded representations — Erdős–Turán conjecture on additive bases (order 2): the still-open $L^\infty$ statement this page's $L^2$ result was motivated by but does not resolve; erdos/28.md's own Facts cite this exact theorem and its explicit non-relevance (flagged/retracted in the April 2026 #749 forum thread). - Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open — density-relaxed variant of #28; its upper-density case is solved (Bhalla, 2026) using a technique family — bounded-multiplicity finite block → linear amplification → scale-separated lacunary gluing — directly in the lineage of, and citing, Ruzsa's 1990 construction as an "earlier, weaker ($L^2$-only) partial-progress result on the same density/boundedness tension." - Ruzsa's number $R_m$ on $\\mathbb Z_m$ — the finite/periodic analogue of the Erdős–Turán additive-basis problem *(forward link — not yet written)* — $R_m$, the finite/periodic $\mathbb Z_m$-analogue this paper's "related finite problem" founded; history: Ruzsa 1990 (existence of uniform $C$) → Tang–Chen 2006/2007 ($768\to5120$) → Chen 2008 ($288$) → Ding–Zhao 2023 ($192$); lower bound Sándor–Yang 2017 ($\ge6$ for $m\ge36$). - concept/erdos-turan-conjecture *(forward link — not yet written)* — the parent $L^\infty$ conjecture family; the $L^2$-vs-$L^\infty$ gap this page documents is the central obstruction separating "solved" from "open" results across this whole cluster. - Finite-field parabola/Sidon-block construction with lacunary-scale gluing — the later (2026, Chen/Liang–Zhang–Zuo/Bhalla) elaboration of the same "bounded finite block + scale-separated lacunary gluing" architecture, documented in full technical detail on wiki/problems/749.md, applicable to the still-open lower-density case adjacent to #28. - Nathanson, M. B., "Every function is the representation function of an additive basis for the integers," arXiv:math/0302091 / related 2003 papers — proves the full $L^\infty$ Erdős–Turán statement is false on $\mathbb Z$ (bounded-by-2 basis exists), the sharp contrast case explaining why Ruzsa's $\mathbb N$-result could only reach $L^2$.