Ruzsa's number $R_m$ on $\\mathbb Z_m$ — the finite/periodic analogue of the Erdős–Turán additive-basis problem

Statement

Fix a positive integer $m$ and work in the cyclic group $\mathbb Z_m$. For $A\subseteq\mathbb Z_m$ and $n\in\mathbb Z_m$, let $$\sigma_A(n) \;=\; \#\{(a,a')\in A\times A : a+a'\equiv n \pmod m\}$$ be the (ordered) representation function. Call $A$ an additive basis of $\mathbb Z_m$ if $\sigma_A(n)\ge1$ for every $n\in\mathbb Z_m$ — i.e. $A+A=\mathbb Z_m$. Ruzsa's number is $$R_m \;=\; \min\bigl\{\, r\in\mathbb Z_{>0} \;:\; \exists\, A\subseteq\mathbb Z_m \text{ with } 1\le\sigma_A(n)\le r \text{ for all } n\in\mathbb Z_m \,\bigr\},$$ the smallest uniform ceiling on the representation function achievable by *some* basis of $\mathbb Z_m$.

The theorem this technique is built around (Ruzsa, 1990, "A just basis," *Monatsh. Math.* 109, 145–151): there is an absolute constant $C$, independent of $m$, with $R_m\le C$ for every positive integer $m$. This is the finite/periodic, fully-resolved analogue of the still-open ($500-prize) Erdős #28 — additive basis forces unbounded representations Erdős–Turán conjecture, which asks whether an additive basis $A$ of $\mathbb N$ (with $A+A$ cofinite) can have *any* uniform bound on $\sigma_A(n)$ for all large $n$ — Erdős conjectured no. Ruzsa's number $R_m$ is the object measuring exactly how tight a bound is achievable once $\mathbb N$ is replaced by the finite, wraparound group $\mathbb Z_m$: since $R_m\le C$ uniformly, the finite/periodic version of the Erdős–Turán question has answer "yes, boundedly," in stark contrast to the still-unresolved infinite question.

Facts

- Qualitative existence is a closed theorem (1990); the quantitative best constant is a live, still-moving research program. The sequence of explicit upper bounds: - Ruzsa 1990: existence of *some* constant $C$, via a quadratic-residue construction in $\mathbb F_p\times\mathbb F_p$ (not made fully explicit in the original paper). - Tang–Chen 2006 (*Colloq. Math.* 104, 99–103): $R_m\le768$ for sufficiently large $m$. - Tang–Chen 2007 (*Colloq. Math.* 108, 141–145): $R_m\le5120$ for all $m$. - Chen 2008 (*J. Number Theory* 128, 2573–2581): $R_m\le288$ for all $m$, via the hard-core bound $R_{2p^2}\le48$ ($p$ prime) plus a comparison lemma $R_{m_1}\le6R_{m_2}$ for $m_1<m_2\le\tfrac32m_1$. - Ding–Zhao 2023/2024 (arXiv:2307.12311; *Int. J. Number Theory* 20 (2024), 1515–1523): current record, $R_m\le192$ for all $m$, via a sharper comparison lemma $R_{m_2}\le4R_{m_1}$ for $\tfrac32m_1\le m_2<2m_1$. - Lower bound: Chen (2008) had only the trivial $R_m\ge3$ for $m\ne1,2,3$. Sándor–Yang 2017 (arXiv:1612.08722; *Acta Arith.* 180, 161–169) proved the first nontrivial lower bound, $R_m\ge6$ for $m\ge36$ — using the Lev–Sárközy second-moment inequality plus finite computation. Ding, Li, Li, Niu, Zhao 2026 (arXiv:2606.11069) later corrected the small-$m$ threshold, finding genuine exceptions $R_{37}=4$, $R_{39}=5$ (so the clean $\ge6$ threshold really starts at $m>45$), and computed exact $R_m$ for all $m\le100$, conjecturing $R_m=6$ for all $m\ge40$ (Conjecture 2.3) — if true, the entire $[6,192]$ upper/lower gap collapses to a single exact value, and $192$ is revealed as purely a proof-technique artifact. - Adjacent-modulus regularity: Ding et al. 2026 also prove the two-directional comparison $R_m\le4R_{m+1}$ and $R_{m+1}\le4R_m$ for *every* consecutive pair (not just a ratio window), yielding $|R_{m+1}-R_m|\le144$ unconditionally, and conjecture $|R_{m+1}-R_m|\le1$ for large $m$ — $R_m$ should be not just bounded but nearly constant and slowly varying. - Size of the extremal basis: since $|A|^2\le\sum_n\sigma_A(n)\le m\cdot R_m$ (Cauchy–Schwarz-style counting), any near-optimal $A$ has $|A|\asymp\sqrt m$ — a basis achieving small $R_m$ must be genuinely sparse (density $\sim1/\sqrt m$), not a bulk fraction of $\mathbb Z_m$. - Contrast with $\mathbb Z$ and general infinite groups. Nathanson (2003) showed the *full* Erdős–Turán statement is false on $\mathbb Z$ (as opposed to $\mathbb N$): a genuinely bounded-by-2, pointwise ($L^\infty$) basis of $\mathbb Z$ exists, exploiting the extra degree of freedom from negative numbers. Konyagin–Lev (arXiv:0901.1649) show most infinite abelian groups $G$ (with $|2G|=|G|$) admit a *perfect* basis ($\sigma\equiv1$) with no boundedness obstruction at all. Ruzsa's $R_m$ result is the finite-cyclic-group data point in the same landscape: boundedness is easy to obtain the moment you leave $\mathbb N$'s specific Archimedean/order structure — by going finite (Ruzsa), signed (Nathanson), or to a different infinite group (Konyagin–Lev). This triangulates exactly where the real difficulty of Erdős #28 — additive basis forces unbounded representations lives: not in "infiniteness" as such, but in the interaction of $A+A$-cofiniteness with the one-sided (non-negative, unbounded, no wraparound) order of $\mathbb N$. - Ruzsa's own motivation was actually the $L^2$, not $L^\infty$, question on $\mathbb N$: his 1990 paper's headline result is a genuine basis of $\mathbb N$ with $\sum_{n\le N}\sigma_A(n)^2=O(N)$ (bounded in square-mean — sharp, since this sum is always $\asymp N$ for any order-2 basis). The finite/periodic $R_m\le C$ statement is presented in the same paper as "a related finite problem," proved en route; it is a strictly stronger (pointwise, not average) statement, but only about $\mathbb Z_m$, not $\mathbb N$. An $L^2$ bound carries zero logical weight toward the $L^\infty$ Erdős–Turán conjecture — this exact non-implication was flagged and an over-claim explicitly retracted in an 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 (see Ruzsa's number $R_m$: every finite cyclic group has an absolutely-bounded-representation basis (Ruzsa, 1990) provenance).

Technique

WHEN this applies: whenever an infinite/asymptotic extremal additive-combinatorics conjecture (representation function boundedness, basis density, etc.) is open, and one wants either (a) a calibration data point showing the difficulty is genuinely about the infinite/asymptotic regime and not about finiteness per se, or (b) a bounded-representation-function gadget on $\mathbb Z_m$ as a building block for a larger construction (e.g. lacunary-scale gluing arguments that stitch together periodic blocks — see Finite-field parabola/Sidon-block construction with lacunary-scale gluing).

WHY it works — the two-layer engine, reusable as a template

1. Algebraic hard core at a special, rigid modulus. Ruzsa's original (and Chen's sharpened) construction works directly in $\mathbb F_p\times\mathbb F_p\cong\mathbb Z_{2p^2}$-adjacent structure, for $p$ prime with $2$ a quadratic non-residue mod $p$: an explicit basis built from quadratic-character/finite-field structure achieves a small constant ($\le48$ in Chen's version) *only* at this algebraically clean modulus shape. Finite-field constructions are stiff and exact — they give small constants precisely *because* they exploit rigid multiplicative structure unavailable at a generic modulus. 2. Comparison lemmas transport the bound to every modulus. A family of lemmas of the shape "if $m_1,m_2$ lie in a controlled ratio window (e.g. $\tfrac32m_1\le m_2<2m_1$), a good basis of $\mathbb Z_{m_1}$ surgically converts into a good basis of $\mathbb Z_{m_2}$ at bounded multiplicative cost" — Chen's original $R_{m_1}\le6R_{m_2}$, sharpened by Ding–Zhao to $R_{m_2}\le4R_{m_1}$ by re-deriving the construction in the opposite direction so a "wrap parameter" in the key sumset identity takes fewer possible values. Ding et al. 2026 further generalize this to a *symmetric adjacent* ($m\leftrightarrow m+1$) version via a "split-and-shift" construction: partition a basis into a high half and low half by threshold, shift only the high half across the modulus boundary, and bound the new representation count by disjoint-case additivity of the old one. 3. Analytic prime-gap gluing closes the loop. An explicit short-interval prime-existence bound (a Bertrand-postulate-type / Panaitopol prime-counting estimate) guarantees, for every sufficiently large $m$, a prime $p$ with $m/4<p\le m/3$ landing $2p^2$ inside the comparison-lemma's ratio window of $m$ — so *every* modulus is within one comparison-lemma hop of the algebraic hard core. Small $m$ below the threshold are patched by a trivial explicit construction. 4. The lower-bound companion tool is different in kind: the Lev–Sárközy second-moment/variance inequality. For $A$ in any finite abelian group $G$ and 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 Cauchy–Schwarz-flavored identity forces representation counts to be unequally spread whenever $|A|$ is calibrated to cover $G$ (not too small) without being too large — i.e. it converts "$A$ is a basis" into "$\sigma_A$ cannot be too flat," giving a genuine lower bound on $\max_n\sigma_A(n)$ purely from $|A|,|G|$. Combined with elementary size bounds and, at the hardest residual finite cases, explicit difference-set non-existence tests (e.g. Baumert's tables), this pins down $R_m\ge6$.

HOW to reuse this for derivation

- Recipe for a new finite/periodic analogue of an open infinite additive-basis question: (i) find an algebraically rigid special-case modulus/structure (finite field, quadratic residues, discrete logs) where a strong explicit bound is provable directly; (ii) build a comparison lemma relating nearby moduli/structures at bounded multiplicative cost, ideally in *both* directions to get adjacent-modulus regularity; (iii) glue via an explicit short-interval existence result (primes, prime powers) so every instance is within reach of the hard core; (iv) separately attack the *lower*-bound direction with a second-moment/variance inequality, which is a generically reusable "basis coverage $\Rightarrow$ representation function cannot be flat" tool independent of the upper-bound machinery. - Recipe for using $R_m$-type gadgets inside a larger infinite construction: lift a bounded-representation basis of $\mathbb Z_m$ to a finite interval of $\mathbb N$ of length $\sim m$, then glue many such blocks across rapidly-growing (scale-separated) moduli so that within-block sums stay pointwise bounded but cross-block interactions are only aggregate/average-bounded — this is exactly how Ruzsa's 1990 $L^2$ result on $\mathbb N$ is built from the $R_m$ machinery, and the same "block $\to$ packet $\to$ lacunary-scale gluing" architecture reappears in 2026 work on the density-relaxed Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open (see Finite-field parabola/Sidon-block construction with lacunary-scale gluing). - When it does NOT resolve the parent problem: a finite/periodic or $L^2$/average-type positive result on $\mathbb Z_m$ or $\mathbb N$ carries no logical implication toward an $L^\infty$/pointwise/limsup statement on $\mathbb N$ — this is the central trap to avoid when trying to leverage $R_m$-type results toward Erdős #28 — additive basis forces unbounded representations itself; it is calibration/technique fuel, not partial progress on the pointwise conjecture.

Related

- Erdős #28 — additive basis forces unbounded representations — the still-open ($500) infinite Erdős–Turán conjecture on additive bases of $\mathbb N$ that $R_m$ is the finite/periodic analogue of. - Ruzsa's number $R_m$: every finite cyclic group has an absolutely-bounded-representation basis (Ruzsa, 1990) — the full worked solved-problem page for $R_m$ itself: complete proof-technique writeup (comparison-lemma chain, prime-gap gluing, Lev–Sárközy inequality), exact bound history, and full extremal-set tables to $m\le100$. - Ruzsa (1990) — a basis of order 2 with representation function bounded in square mean, $\\sum_{n\\le N}\\sigma_A(n)^2=O(N)$ — Ruzsa's original 1990 result on $\mathbb N$ (square-mean-bounded basis), of which the $R_m\le C$ statement is the finite byproduct; documents the "finite gadget + lacunary gluing" architecture in full. - 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 sibling of #28; its 2026-resolved upper-density case reuses the same finite-block/lacunary-gluing architecture that $R_m$ exemplifies. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — a different Ruzsa construction (1998, infinite Sidon sets via log-of-primes/discrete-log encoding) — same author, same broad "bounded/controlled representation function via explicit or comparison-lemma construction" cluster, distinct toolkit; useful contrast in what "Ruzsa's method" can mean depending on target regime. - Finite-field parabola/Sidon-block construction with lacunary-scale gluing — the general finite-field/lacunary-scale-gluing toolkit that $R_m$-type periodic gadgets feed into for infinite constructions. - Singer perfect difference sets / finite-field constructions for Sidon-type lower bounds — the $\sigma\equiv1$ extremal cousin (no boundedness slack at all); relevant contrast structure in the same finite-abelian-group representation-function landscape.