Ruzsa's number $R_m$: every finite cyclic group has an absolutely-bounded-representation basis (Ruzsa, 1990)

Statement

The (still open, Erdős #28 — additive basis forces unbounded representations) Erdős–Turán conjecture (1941) says that if $A\subseteq\mathbb N$ has $A+A$ cofinite in $\mathbb N$, then its representation function $\sigma_A(n)=\#\{(a,a')\in A\times A: a+a'=n\}$ must be unbounded: no additive basis of order 2 of $\mathbb N$ can have a uniformly bounded number of representations for every large $n$.

Ruzsa (1990) posed and solved the natural finite periodic analogue, replacing $\mathbb N$ by the cyclic group $\mathbb Z_m$. For a positive integer $m$ and $A\subseteq\mathbb Z_m$, write $\sigma_A(n)=\#\{(a,a')\in A\times A: a+a'\equiv n\pmod m\}$, and call $A$ an *additive basis* of $\mathbb Z_m$ if $\sigma_A(n)\ge1$ for every $n\in\mathbb Z_m$. Define Ruzsa's number $$R_m \;=\; \min\bigl\{\, r\in\mathbb Z_{>0} \;:\; \exists\, A\subseteq\mathbb Z_m \text{ with } 1\le\sigma_A(n)\le r \ \ \forall n\in\mathbb Z_m \,\bigr\}.$$

Question

is $R_m$ bounded by a constant independent of $m$ — i.e. does *every* finite cyclic group, no matter how large, admit an additive basis whose representation function never exceeds some universal ceiling?

Facts

- This is a genuinely solved theorem, not a conjecture — it is the point on which this page differs from its infinite sibling Erdős #28 — additive basis forces unbounded representations, which is still open 85 years later. Ruzsa (1990) proved: *there exists an absolute constant $C$, independent of $m$, such that $R_m\le C$ for every positive integer $m$* [I.Z. Ruzsa, "A just basis," Monatsh. Math. 109 (1990), 145–151]. - Chain of explicit upper bounds on the constant (the qualitative "is it bounded" question was closed in 1990; the *quantitative* "what is the best constant" question is a live, currently-improving research program): - Ruzsa 1990: existence only, constant not made fully explicit. - Tang–Chen 2006 (Colloq. Math. 104, 99–103): $R_m\le768$ for all *sufficiently large* $m$, using Ruzsa's construction directly. - Tang–Chen 2007 ("A basis of $\mathbb Z_m$, II," Colloq. Math. 108, 141–145): $R_m\le5120$ for *all* $m$ (closing the small-$m$ gap). - Chen 2008 (J. Number Theory 128, 2573–2581): $R_m\le288$ for all $m$, via a hard-core bound $R_{2p^2}\le48$ (prime $p$) plus a comparison lemma. - Ding–Zhao 2023/2024 (arXiv:2307.12311; Int. J. Number Theory 20 (2024), 1515–1523): $R_m\le192$ for all $m$, via a refined comparison lemma. - Current record, upper side: $R_m\le192$ (unimproved since 2023/24). - Lower bound: Chen (2008) could show only the trivial $R_m\ge3$ for $m\ne1,2,3$. Sándor–Yang 2017 (arXiv:1612.08722; Acta Arith. 180, 161–169) gave the first non-trivial lower bound, $R_m\ge6$ for $m\ge36$ (later corrected to $m>45$ by Ding et al. 2026, who found small computational errors — $R_{37}=4$ and $R_{39}=5$ are genuine exceptions dipping *below* 6 that survived past $m=36$), via the Lev–Sárközy second-moment inequality on the group $\mathbb Z_m$ plus finite computer verification of the resulting Diophantine system. - Small values are fully tabulated. $R_2=R_3=2$; $R_4=R_5=3$ (also $R_7=3$); $R_m=4$ for $m\in\{6,8,9,\dots,15,19,37\}$; and — per Ding, Li, Li, Niu, Zhao, arXiv:2606.11069 (9 Jun 2026), which extends the table with certificate-based computation to every $m\le100$ — the values appear to converge to exactly 6 for all sufficiently large $m$: their Conjecture 2.3 states $R_m=6$ for $m\ge40$, verified computationally for the entire range $46\le m\le100$ (with a mechanically-verified certificate: an explicit basis $A\subseteq\mathbb Z_m$ with $\max_n\sigma_A(n)=6$, plus the Sándor–Yang lower bound $R_m\ge6$ for the same range). If Conjecture 2.3 is true, the entire $[6,192]$ bracket collapses to a single number — the current $192$ upper bound is then a proof-technique artifact, not close to sharp. - Adjacent-modulus regularity: the same 2026 paper proves $|R_{m+1}-R_m|\le144$ unconditionally (down from the "trivial" $192-6=186$ obtainable by just subtracting the known bounds), and conjectures (Ding–Zhao's original Conjecture 3.1, now revised to Conjecture 1.2 after the $m=36,37$ counterexample) that $|R_{m+1}-R_m|\le1$ for all sufficiently large $m$ — i.e. $R_m$ should not just be bounded but nearly *constant* and *slowly varying* once $m$ is large. - Non-trivial size bounds on the extremal basis $A$: since $|A|^2=\sum_n\sigma_A(n)\le mR_m$, trivially $|A|\le\sqrt{mR_m}\le\sqrt{192m}$; Ding et al. 2026 sharpen this via a *second* application of the Lev–Sárközy inequality (Theorem 1.2) to the essentially matching two-sided bound $|A|\approx\sqrt{3m}$ when $R_m=6$ (Corollary 1.2: $(\sqrt3-\varepsilon)\sqrt m\le|A|\le(2+\varepsilon)\sqrt m$). - Contrast with general infinite abelian groups — informative for why $\mathbb N$ is special (per this wiki's Erdős #28 — additive basis forces unbounded representations page): Konyagin–Lev (arXiv:0901.1649) show that most infinite abelian groups $G$ (with $|2G|=|G|$) admit a *perfect* basis ($\sigma\equiv1$, no boundedness issue at all) — the Erdős–Turán obstruction is specific to $\mathbb N$'s Archimedean order structure, not to "being infinite" or "being a group" per se. Ruzsa's $R_m$ result is the finite-cyclic-group data point in the same landscape: boundedness is easy to achieve once you leave $\mathbb N$'s specific order structure, whether by going to a general infinite group or by going finite/periodic.

Solution

High-level shape of the proof: reduce *all* moduli $m$ to a single, explicitly-constructed hard-core case at $m=2p^2$ ($p$ prime) via a finite-field quadratic-residue construction, then transport that bound to every other $m$ via a chain of comparison lemmas relating $R_{m_1}$ and $R_{m_2}$ for $m_1,m_2$ in a fixed ratio window, glued together using explicit short-interval prime-existence results (Bertrand-postulate-type). This two-layer engine — *(algebraic base case) + (multiplicative doubling/folding lemma) + (analytic prime-gap glue)* — is the reusable idea; three independent papers (Chen 2008; Ding–Zhao 2023; Ding et al. 2026) each re-ran the same shape with a sharper comparison lemma to shrink the constant $768\to5120\to288\to192$, and the ratio-window trick generalizes immediately to *adjacent*-modulus statements ($|R_{m+1}-R_m|\le144$).

Layer 1 — the algebraic hard core (Ruzsa 1990). Work in $\mathbb F_p\times\mathbb F_p$ for a prime $p$ with $\left(\tfrac2p\right)=-1$ (2 is a quadratic non-residue mod $p$). Ruzsa constructs an explicit basis of this group — built from the quadratic-character/finite-field structure — in which every group element has at most 18 representations as a sum of two basis elements. Transported to the cyclic group $\mathbb Z_{2p^2}$ (via the ring isomorphism structure this construction sits inside), this is the seed fact that every finite cyclic group of this special shape has a small-constant basis; Chen's 2008 refinement of the same construction gives the cleaner, still-used bound $R_{2p^2}\le48$.

Layer 2 — comparison lemmas: transport the bound to every modulus. The single hard-core fact $R_{2p^2}\le48$ says nothing directly about, say, $R_{10^9+7}$. The bridge is a family of comparison lemmas, each of the shape *"if $m_1,m_2$ lie in a controlled ratio window, a good basis of $\mathbb Z_{m_1}$ can be surgically converted into a good basis of $\mathbb Z_{m_2}$, at a bounded multiplicative cost."* Three successive refinements: - Chen's comparison lemma (2008): for $m_1<m_2\le\tfrac32 m_1$, $R_{m_1}\le6R_{m_2}$. - Ding–Zhao's refined comparison lemma (2023): for $\tfrac32 m_1\le m_2<2m_1$, $R_{m_2}\le4R_{m_1}$ — a *sharper constant* (4 instead of 6) obtained by re-deriving the construction in the *opposite direction* (grow a basis of the smaller group into a basis of the larger one, rather than shrink), which the authors show makes the "wrap parameter" $k$ in the key identity $n+km_2=b_1+b_2$ take only the values $0,1$ (never $2$) — a cleaner case split that is the concrete source of the improvement from 6 to 4 (Ding–Zhao, Remark 2.1). - The adjacent (±1) comparison lemma (Ding et al., 2026): proves the *symmetric two-directional* bound $R_m\le4R_{m+1}$ and $R_{m+1}\le4R_m$ simultaneously, for *every* consecutive pair $m,m+1$ (not just a ratio window), via a "split-and-shift" construction: partition a good basis $A\subseteq\mathbb Z_m$ into a high half $A_1=\{a\in A: a\ge\lfloor m/2\rfloor\}$ and low half $A_2=A\setminus A_1$; form $B=A\cup(A_1+1)\subseteq\mathbb Z_{m+1}$ by shifting only the *high half* forward by one; a case analysis on which half each summand of a representation of $n$ came from shows $B$ still covers $\mathbb Z_{m+1}$ and that its representation function is bounded by a sum of at most 4 translates of $\sigma_A$ (using that certain cross-terms like $f_{A_1,A_+}(n)$ vanish identically because $A_1$ elements are too large to combine with a shifted copy without overflowing the modulus). This "split by a threshold, shift only the upper half across the modulus boundary, and bound the new representation count by disjoint-case additivity of the old one" is the fully reusable move — it needs only that $A$ is confined to a fixed interval $[0,m-1]$ and works for any step size, not just moving between a special ratio window.

Gluing step (explicit prime-gap lemma). To finish $R_m\le192$ for *every* $m$: for $m>4356$, apply an explicit prime-counting bound (Panaitopol's refinement of the prime number theorem, verified numerically for small $x$) to find a prime $p$ with $\sqrt{m/4}<p\le\sqrt{m/3}$, guaranteeing $\tfrac32(2p^2)\le m<2(2p^2)$ — exactly the window where the Ding–Zhao comparison lemma applies — giving $R_m\le4R_{2p^2}\le4\cdot48=192$. Small $m\le4356$ are handled by a trivial explicit construction ($A=\{0,1,\dots,66\}\cup\{66,132,\dots,66^2\}$, giving $R_m\le132$ by Euclidean division). This "reduce every large case to a nearby algebraically-clean hard core via an explicit short-interval prime, then patch the remaining finite range by brute force" pattern is a standard transfer trick usable anywhere a construction is naturally clean only at special moduli (here $2p^2$) but the target statement must hold for *all* moduli.

The lower-bound technique (the companion tool): Lev–Sárközy's second-moment/variance inequality. For $A$ in *any* finite abelian group $G$ and any real $c$, $$\sum_{g\in G}\bigl(\sigma_A(g)-c\bigr)^2 \;\ge\; \frac{1}{|G|-1}\left(\frac{|A|^4}{|G|}-2|A|^3+|A|^2|G|\right).$$ This is a Cauchy–Schwarz-flavored identity: it lower-bounds how *unequally* the representation counts must be spread, purely from $|A|$ and $|G|$, forcing some $\sigma_A(n)$ to be large if $A$ is neither too small (fails to cover $G$) nor too large. Combined with elementary size bounds ($|A|>\sqrt{2m}-\tfrac12$ from covering, $|A|\le\sqrt{rm}$ from the bound $r$) and, in the hardest residual finite range, an explicit Baumert difference-set existence test (used to rule out $R_{45}\le5$ directly), this identity is what pins $R_m\ge6$ for $m>45$ — the general-purpose transferable lower-bound tool for *any* bounded-representation-function extremal problem on a finite abelian group.

Why this transfers to open problems: the *comparison-lemma engine* (hard algebraic core + doubling/folding surgery + prime-gap gluing) is a template for turning "a bound provable only at special, algebraically rigid moduli/structures" into "a bound provable everywhere," and the *Lev–Sárközy second-moment inequality* is a template for turning "$A$ covers $G$" into "$\sigma_A$ cannot be too flat," both usable wherever a finite/periodic analogue of an unresolved infinite extremal problem is being calibrated (as with Erdős #28 — additive basis forces unbounded representations and Erdős #40 — sharp density threshold for Erdős–Turán above it) or wherever an open problem needs a bounded-representation-function gadget on $\mathbb Z_m$ as a building block.

Related

- Erdős #28 — additive basis forces unbounded representations — the still-open ($500 prize) infinite Erdős–Turán conjecture this is the finite/periodic analogue of; that page's own Facts section already cites this exact literature chain and treats $R_m$ as evidence that the true difficulty of #28 is specifically about the infinite/cofinite/asymptotic regime, not about finiteness. - Erdős #40 — sharp density threshold for Erdős–Turán — the density-sharpened sibling conjecture to #28; same "what quantitative hypothesis forces unbounded representation" question, one level more refined. - Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998) — the sibling Ruzsa solved-problem page (a different 1998 paper, on infinite Sidon sets): same author, adjacent problem cluster (bounded/controlled representation functions in additive combinatorics), different toolkit (probabilistic digit-encoding rather than finite-field quadratic residues + comparison lemmas) — useful contrast in what "Ruzsa's method" can mean depending on the target regime. - Ruzsa's number $R_m$ on $\\mathbb Z_m$ — the finite/periodic analogue of the Erdős–Turán additive-basis problem — the concept page for $R_m$ itself (already referenced from Erdős #28 — additive basis forces unbounded representations's Related section); this page is its full derivation/technique writeup. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — the general finite-field/discrete-log Sidon-construction toolkit this page's Layer-1 quadratic-residue construction belongs to. - Additive representation function $r_{B,h}(n)$ — $\sigma_A(n)$, the central object shared across this whole problem family. - Perfect additive basis / unique representation basis ($r_A\\equiv1$) — the $\sigma\equiv1$ extreme case; provably exists for most infinite abelian groups (Konyagin–Lev) and is exactly the object the classical (infinite, $\mathbb N$) Erdős–Turán conjecture forbids in the bounded (not just unique) sense.