Perfect additive basis / unique representation basis ($r_A\\equiv1$)

Statement

For $A\subseteq\mathbb Z$ (or a subset of any abelian group $G$), let $r_A(n)=\#\{(a,a')\in A\times A: a\le a',\ a+a'=n\}$ be the (unordered) representation function. $A$ is an additive basis (of order 2) for $\mathbb Z$ if $r_A(n)\ge1$ for every $n\in\mathbb Z$, and a unique representation basis — the standard term for a perfect additive basis of order 2 — if $$r_A(n)=1\quad\text{for every } n\in\mathbb Z.$$ (arxiv.org/pdf/math/0202137, §1, Nathanson's exact definitions.) The general group version: $S\subseteq G$ is a perfect basis of $G$ if every $g\in G$ has a *unique* representation as $s+s'$ ($s,s'\in S$) up to reordering the summands.

The key contrast that makes this concept nontrivial (Nathanson 2002, §1, "known in the oral tradition"): the classical Erdős–Turán conjecture (Erdős #28 — additive basis forces unbounded representations) asserts that on the semigroup $\mathbb N_0$, *no* basis of order 2 can have a *bounded* representation function — in particular no perfect basis of $\mathbb N_0$ can exist for a covering basis with $r_A\ge1$ eventually. But on the *group* $\mathbb Z$ (or almost any infinite abelian group), perfect bases do exist, and — sharply, as this page documents — can be made arbitrarily sparse, arbitrarily dense (up to a provable $\sqrt x$ ceiling), or tuned in between. The entire technical content of this concept is: *how* to build such bases, exactly how sparse/dense they can be forced to be, and *why* the group $\mathbb Z$ escapes the $\mathbb N_0$ obstruction.

Facts

- Existence, arbitrarily sparse (Nathanson, Theorem 1, math/0202137): for any $f(x)\to\infty$, there is a unique representation basis $A$ of $\mathbb Z$ with $A(-x,x):=|A\cap[-x,x]|\le f(x)$ for all sufficiently large $x$. So no positive-density lower bound is forced at all — a unique representation basis can grow slower than *any* prescribed divergent function. - Existence, logarithmic growth, sharp constants (Nathanson, Theorem 2): the greedy special case of the same construction gives an explicit unique representation basis $A$ with $$\frac{2\log x}{\log5}+2\Bigl(1-\frac{\log3}{\log5}\Bigr)\ \le\ A(-x,x)\ \le\ \frac{2\log x}{\log3}+2$$ for all $x\ge1$ — a fully explicit, two-sided $\Theta(\log x)$ basis (constants $2/\log3\approx1.82$, $2/\log5\approx1.24$). - Universal upper bound (Nathanson, Theorem 3): *any* $A\subseteq\mathbb Z$ with bounded representation function $r_A(n)\le r$ for all $n$ satisfies $A(-x,x)\le\sqrt{8rx}$ — in particular every unique representation basis ($r=1$) has $A(-x,x)\ll\sqrt x$; no basis can be denser than order $\sqrt x$. Proof is a one-line double-count: the $\binom{k+1}{2}$ ordered pairs from $A\cap[-x,x]$ ($k:=A(-x,x)$) all land in $[-2x,2x]$ with multiplicity $\le r$ per value, giving $k(k+1)/2\le r(4x+1)$. - The $\mathbb N_0$-vs-$\mathbb Z$ mechanism, made explicit (Nathanson, Theorem 4 + discussion): for $A\subseteq\mathbb N_0$ that is an (asymptotic) basis, coverage of $[0,2x]$ forces $A(0,x)\ge2\sqrt x-1$ — a basis of $\mathbb N_0$ is *always* dense ($\gg\sqrt x$), because the summands are confined to the finite window $[0,x]$ by nonnegativity; and if additionally $r_A\le r$, then also $A(0,x)\le2\sqrt{rx}$. So an $\mathbb N_0$-basis is *squeezed* into a $\Theta(\sqrt x)$-band by both directions simultaneously, which is exactly the pressure the Erdős–Turán conjecture claims is incompatible with boundedness. On $\mathbb Z$, by contrast, admitting negative summands lets $A$ be arbitrarily sparse (Theorem 1) precisely because a large positive $n$ can be hit by a pair $(a,a')$ with $a$ arbitrarily large negative and $a'=n-a$ arbitrarily large positive — the covering constraint no longer forces density. Nathanson: "this phenomenon may underlie the Erdős-Turán conjecture." - Nathanson's four open problems (2002/2003, Acta Arith. 108, §4): (1) does $c>2/\log5$ still admit a basis with $A(-x,x)\ge c\log x$ eventually? (2) does $\limsup A(-x,x)/\log x=\infty$ for some basis? (3) does some $\theta>0$ admit $A(-x,x)\ge x^\theta$ eventually? (4) does $\theta<1/2$ exist with $A(-x,x)\le x^\theta$ for every unique representation basis eventually (a universal upper-bound refinement of Theorem 3's $\sqrt x$)? - **Problem 4 resolved negatively (Chen 2007, *Eur. J. Comb.* 28:33–35)**: for every $\varepsilon>0$ there is a unique representation basis with $A(-x,x)\ge x^{1/2-\varepsilon}$ for *infinitely many* $x$ — ruling out any universal $\theta<1/2$ ceiling. This immediately posed two follow-ups (quoted in Ding 2024/Ding–Wang 2026 as "Chen's Problem 2/3"): does some $c>0$ give $A(-x,x)\ge c\sqrt x$ infinitely often, resp. for *all* $x\ge1$? - Problems 1–3 of Nathanson resolved affirmatively, in the strong "for all sufficiently large $x$" form (Ding 2024, arXiv:2406.06214, Theorem 1): there is a unique representation basis with $$A(-x,x)\ \ge\ \tfrac18 x^{1/3}\qquad\text{for all sufficiently large }x$$ — a genuine polynomial growth rate holding *eventually*, not just along a subsequence, settling Problems 1, 2, and 3 simultaneously (any function of $A(-x,x)$ growth exceeding $\log x$, e.g. via $\limsup A(-x,x)/\log x=\infty$, follows immediately from a $x^{1/3}$ eventual lower bound). - Chen's Problem 2 resolved affirmatively / Problem 3 resolved negatively (Ding 2024, Theorems 2–3): Theorem 2 builds a basis with $A(-x,x)\ge(\sqrt2/2-\varepsilon)\sqrt x$ for *infinitely many* $x$ (using an embedded Sidon set, near the Theorem-3 $\sqrt{8x}$ ceiling up to the constant); Theorem 3 shows $\liminf_{x\to\infty} A(-x,x)/\sqrt{x/\log x}\le4\sqrt7$ for *every* unique representation basis — so a uniform $c\sqrt x$ lower bound valid for *all* $x$ is impossible (there must be a $\sqrt{x/\log x}$-order dip infinitely often), a genuine oscillation phenomenon dual to Erdős–Fuchs-type non-smoothness results (see Additive representation function $r_{B,h}(n)$ Facts on the Erdős–Fuchs theorem — a structurally analogous "representation counts cannot stay too regular" obstruction, here for the *counting function* of the basis itself rather than the representation function). - The exact optimal $\limsup$-constant is still open, tightened from both sides (2024–2026): define $\mathscr A$ = unique representation bases with $\limsup A(-x,x)/\sqrt x>0$, and $c_A:=\limsup A(-x,x)/\sqrt x$ for $A\in\mathscr A$, $c_{\mathscr A}:=\sup_{A\in\mathscr A}c_A$. A trivial embedding argument (any $A\cap[-x,x]$ shifted by $x+1$ is itself a Sidon set in $[1,2x+1]$, so $A(-x,x)\le F_2(2x+1)\sim\sqrt{2x}$ where $F_2(N)\sim\sqrt N$ is the classical Sidon-set extremal function) gives $c_{\mathscr A}\le\sqrt2$. Ding 2024 (Theorem 2, via Lemma 1's asymptotic Sidon density $F_2(N)\sim N^{1/2}$ alone) got $c_{\mathscr A}\ge\sqrt2/2$; Ding–Wang 2026 (arXiv:2602.07743, Theorem 1) improve this to $c_{\mathscr A}\ge1$, using an *explicit finite* Sidon set from a Bose/Singer projective-plane-type construction mod $p^2-1$ (Bose 1942, "An affine analogue of Singer's theorem") rather than just the asymptotic $F_2(N)\sim\sqrt N$ bound — the explicit construction extracts a better multiplicative constant than the purely asymptotic embedding argument can. Conjectured $c_{\mathscr A}=\sqrt2$ (Ding–Wang 2026, closing remark, "due to some considerations from Sidon sets"); still open as of Feb 2026. - **Group-theoretic generalization, fully resolved in the opposite direction from Erdős–Turán (Konyagin–Lev, arXiv:0901.1649, full detail on erdos/erdos-turan-conjecture-infinite-groups): for infinite abelian $G$ with $|2G|=|G|$, a perfect basis exists unless** $G\cong(\text{exponent-3 group})\oplus\mathbb Z/2$ (in which case a near-perfect, $r\le2$, basis is the sharp substitute). $\mathbb Z$ is the archetypal case ($|2\mathbb Z|=|\mathbb Z|=\aleph_0$, not the exceptional family) where perfect bases exist — Nathanson's 2002 result is the $G=\mathbb Z$ special case, later subsumed by Konyagin–Lev's general transfinite-greedy classification. The general theorem's *existence* mechanism for arbitrary $G$ is a transfinite-length greedy construction (well-order $G$, add fresh generator pairs while avoiding five explicitly-bounded forbidden sets at each step) — the natural infinite-cardinality generalization of Nathanson's finite-inductive-doubling method below.

How this concept's proofs are actually built (recombination-ready steps)

1. The core inductive "patch one obstruction at a time, far away" construction (Nathanson 2002, proof of Theorem 1; refined by Chen 2007, Ding 2024, Ding–Wang 2026). Build an ascending chain $A_1\subset A_2\subset\cdots$ with the invariant $r_{A_k}(n)\le1$ for all $n$ and $r_{A_{2k}}(n)=1$ for all $|n|\le k$. At each step, let $m$ be the least-absolute-value integer *not yet* represented by $A_k$; choose a very large auxiliary offset $b\gg\max|A_k|$ (specifically $b=4|a^*_k|+|m|$ in Nathanson's version) and add the pair $\{-b,\,b+m\}$, so that $m=(b+m)+(-b)\in A_{k+1}+A_{k+1}$. Because $b$ is chosen far outside the range of $A_k$, the four sets $2A_k$, $A_k-b$, $A_k+b+m$, and $\{m,-2b,2b+2m\}$ are automatically pairwise disjoint (a one-line interval-disjointness check), so no old representation collides with the new one — uniqueness is preserved by construction, not by a separate argument. Repeat forever; the union is a full unique representation basis. This is the single load-bearing mechanism behind *every* construction on this page (Theorems 1–2 of Nathanson, Theorems 1–2 of Ding 2024, Theorem 1 of Ding–Wang 2026 all use verbatim this "patch $m$ with a far-offset pair, then verify disjointness by interval bounds" step) — it is the reusable engine for building any infinite structure that must maintain an exact (not merely bounded) local uniqueness invariant while growing to cover everything. 2. Tuning the growth rate by tuning how "far away" the offset is. The *only* free choice in step 1 is how large to make $b$ (equivalently $c_k$ in Nathanson's later notation) relative to the previous maximum $d_k=\max|A_k|$: taking $c_k=d_k$ (the *smallest* legal choice, "greedy") forces the *fastest* possible growth and yields the $\Theta(\log x)$ basis (Theorem 2); taking $c_k$ to grow superlinearly relative to a target $f$ instead *starves* the construction and yields the arbitrarily-sparse basis (Theorem 1). This single dial — "how aggressively do you delay/space out patches" — is the entire mechanism controlling counting-function growth in this family of constructions; it generalizes to any patch-based greedy construction where a growth-rate target needs to be hit exactly. 3. Grafting a Sidon set in to push density up toward the $\sqrt x$ ceiling (Chen 2007; refined Ding 2024 Thm 2; refined again Ding–Wang 2026 Thm 1). Since Nathanson's Theorem 3 shows $\sqrt x$ is an absolute density ceiling for *any* bounded-representation set, the way to approach it is to embed a near-extremal Sidon set $S$ (all pairwise sums distinct, $|S|\sim\sqrt N$ or, via Bose–Singer, an explicit $|S|\sim(1-\varepsilon)\sqrt N$ construction with a good constant) directly as new basis elements. The delicate step is collision management: $S$'s internal sums are automatically distinct (Sidon), but sums/differences *between* $S$ and the existing $A_{2h}$ can still collide; the fix is to bound the number of bad pairs ($\le2|A_{2h}|^2$, a *fixed finite* quantity independent of $|S|$) and delete the finitely many colliding elements of $S$ — since $|S|\to\infty$ with the construction while $|A_{2h}|$ is fixed at that stage, the deleted fraction is asymptotically negligible. This "build a big near-extremal auxiliary structure, then delete a bounded finite correction" move is the same template as the deletion technique in Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue (Facts, "the deletion technique") and in Sidon-set constructions generally — a broadly reusable pattern whenever a global exactness constraint (Sidon-ness, or here $r_A\equiv1$) must survive splicing in a dense external structure. 4. **Getting a better multiplicative constant by using an *explicit* Sidon construction instead of the asymptotic extremal function (Ding–Wang 2026). Ding 2024's Theorem 2 only used the bare asymptotic fact $F_2(N)\sim\sqrt N$ (any Sidon set achieving close to the extremal density would do), giving constant $\sqrt2/2$. Ding–Wang's improvement to $c_{\mathscr A}\ge1$ comes from swapping in a specific, structured** Sidon set — Bose's 1942 affine analogue of Singer's finite-projective-plane construction, an explicit set of $p$ residues mod $p^2-1$ with all pairwise sums distinct mod $p^2-1$ — split across *two* disjoint ranges (excising a thin symmetric middle band to keep uniform Sidon-ness after lifting from $\mathbb Z_{p^2-1}$ to $\mathbb Z$), which loses only a $(1-O(\varepsilon))$ fraction of density but is *structured* enough to interact more favorably with the deletion step in item 3. Lesson: when an asymptotic-density argument gives a suboptimal constant in a construction, check whether swapping in a named *explicit* extremal construction (Singer/Bose finite-field difference sets, cf. Singer finite-field perfect difference set construction, Finite-field parabola/Sidon-block construction with lacunary-scale gluing) for the bare asymptotic bound recovers a better constant — the extra algebraic structure of an explicit construction is often exactly what a delicate deletion/collision argument needs. 5. König's-lemma / compactness reduction: infinite existence $\Leftrightarrow$ arbitrarily-large finite examples (Nathanson, math/0302155, Theorem 4). For a general "$\mathcal R$-basis of order $\mathcal H$" (any prescribed sequence of allowed representation counts per $n$, generalizing $r_A(n,h)=f(n)$ or $r_A(n,2)\in[1,c]$), build a rooted tree $T$ whose vertices are *finite* valid prefixes $\{a_0<\cdots<a_n\}$ (each an $\mathcal R$-basis restricted to $[0,\max]$), with $V$ adjacent to $V\setminus\{\max V\}$. If the growth condition $\liminf \max(H_n)/n>0$ holds fails suitably (technically: $\lim\max(H_n)/n=0$), every vertex has finite degree — a short pigeonhole argument bounds how many one-element extensions are possible — so if the tree is infinite (equivalently, arbitrarily large finite valid prefixes exist), König's lemma guarantees an infinite path, i.e. an actual infinite basis. This is a genuinely different technique from items 1–4: instead of constructing the infinite object directly, it reduces the *existence* question to a purely combinatorial statement about *finite* sets ("do arbitrarily large finite valid configurations exist?") — recovering, as the special case $H_n=\{2\}$, $R_n=[1,c]$, Dowd's 1988 equivalence for the classical Erdős–Turán conjecture itself. When to reach for this instead of items 1–4: whenever direct greedy construction is awkward (e.g. the target representation-count profile $f(n)$ is not monotone/simple enough for an explicit patch rule) but *finite* feasibility is easier to check or already known — compactness converts "build one infinite witness" into "show finite witnesses get arbitrarily large," which is often the easier of the two. 6. Universal density bounds via double-counting pairs against the range of sums (Nathanson, Theorems 3–4; the Erdős/Stöhr block technique of Ding 2024 Theorem 3). For *upper* bounds: count ordered pairs from $A\cap[-x,x]$ ($\sim k^2/2$ of them) against how many land in each of the $O(x)$ possible sum values, each hit $\le r$ times — a one-line pigeonhole gives $k\ll\sqrt{rx}$. For the *sharper, universal-in-$x$ negative* result (Theorem 3 of Ding 2024, "no uniform $c\sqrt x$ floor"), partition $[-Nn,Nn]$ into $O(n)$ blocks of width $n$; uniqueness of *differences* within one block bounds $\sum N_\ell^2\ll n$ (Sidon-style, since $A$'s pairwise differences under $n$ apart are forced distinct by $r_A\equiv1$); uniqueness of *sums* between symmetric blocks ($\ell$-th positive, $\ell$-th negative) gives the cross term $N_\ell M_\ell\ll n$; Cauchy–Schwarz over the harmonic-weighted sum of these bounds then forces $A(-\ell n,\ell n)$ to dip below its $\sqrt{x/\log x}$-order "expected" value for some $\ell\le n$ — a technique traced explicitly by Ding back to Erdős's argument communicated to Stöhr (Stöhr 1955) for an analogous *infinite Sidon set* oscillation result, i.e. this dyadic/linear-block-plus-Cauchy–Schwarz oscillation argument is itself a reusable, portable technique beyond this specific problem (cf. Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) for a structurally similar block-decomposition-plus-Cauchy–Schwarz technique in a different Sidon-adjacent context). 7. WHEN this concept/technique applies: whenever a problem asks for an additive structure with an exact (not merely bounded) local uniqueness invariant that must extend to cover an entire (semi)group or set, on a substrate where the covering condition does *not* force density (typically: a two-sided/group-like ambient set, not a one-sided semigroup like $\mathbb N_0$) — reach first for the patch-far-away greedy construction (item 1) to get *existence at all*, then tune the offset growth rate (item 2) to hit a target density, then graft in a Sidon-type structure with a delete-the-bounded-collisions cleanup (items 3–4) to push density toward the provable $\sqrt x$ ceiling (item 6, upper direction), and reach for König's-lemma compactness (item 5) specifically when a direct greedy rule is awkward to state but finite feasibility is more tractable. This entire toolkit is the positive/constructive counterpart to the Erdős–Turán-family machinery on Additive representation function $r_{B,h}(n)$ (which is almost entirely about *impossibility*/lower-bound-forcing on $\mathbb N_0$): recognizing which "half" a given problem is in (does the ambient structure make exact uniqueness *achievable*, as here, or is boundedness itself in question on a one-sided semigroup, as in the still-open Erdős #28 — additive basis forces unbounded representations) is the first and most important recombination decision.

Related

- Erdős #28 — additive basis forces unbounded representations — the classical, still-open Erdős–Turán conjecture on $\mathbb N_0$: no order-2 basis can have bounded representation function. This page's entire subject exists precisely *because* the analogous statement is false on $\mathbb Z$ — Nathanson's "may underlie the conjecture" heuristic (Theorem 4 discussion) is the sharpest known structural explanation of *why* $\mathbb N_0$ and $\mathbb Z$ diverge. - erdos/erdos-turan-conjecture-infinite-groups — Konyagin–Lev's full classification of which infinite abelian groups admit a perfect basis (generic yes, one exceptional family no); the general transfinite-greedy proof technique there is the infinite-cardinality generalization of this page's finite-inductive item-1 technique, and its Related section already forward-links to this exact concept slug. - Additive representation function $r_{B,h}(n)$ — the parent survey page for $r_{B,h}(n)$ across all orders and ambient structures; this page is the deep-dive on its "Perfect basis" paragraph and on the group-theoretic Konyagin–Lev result it already summarizes. - Sidon sets / B_2 sets / Golomb rulers — the extremal-density building block (item 3–4) used to push unique representation bases toward the $\sqrt x$ ceiling; shares the classical $F_2(N)\sim\sqrt N$ extremal function and the deletion-cleanup template. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — a structurally parallel "build dense near-extremal object, delete bounded collisions" technique (item 3's template) in the *infinite* Sidon-set-density record-holding context, useful as a contrast/parallel case. - Singer finite-field perfect difference set construction and Finite-field parabola/Sidon-block construction with lacunary-scale gluing — the explicit finite-field/projective-plane construction family (Singer 1938, Bose 1942) that Ding–Wang 2026 swap in (item 4) to improve the $c_{\mathscr A}$ constant beyond what the bare asymptotic Sidon density gives. - Ruzsa's number $R_m$ on $\\mathbb Z_m$ — the finite/periodic analogue of the Erdős–Turán additive-basis problem — the finite cyclic-group ($\mathbb Z_m$) analog of bounded-representation bases; Konyagin–Lev's Corollary 1 (see erdos/erdos-turan-conjecture-infinite-groups) explicitly combines it with the infinite-group result to unify the picture across finite and infinite abelian groups. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — a structurally similar block-decomposition-plus-Cauchy–Schwarz technique (compare item 6's Erdős/Stöhr oscillation argument) applied in a different Sidon-extremal-constant context.