Konyagin–Lev: the Erdős–Turán problem, fully resolved for infinite abelian groups

Statement

Let $G$ be an abelian group (written additively) and call $S\subseteq G$ a (additive) basis of order 2, or basis for short, if every element of $G$ is representable as $s+s'$ with $s,s'\in S$. The representation function $r_S(g)$ counts the (ordered) representations $g=s+s'$, $s,s'\in S$. A basis is perfect if every element has a *unique* representation up to order of summands — equivalently, in an involution-free ambient group, $r_S\le 2$ everywhere (arXiv:0901.1649, §1).

The classical, still-open Erdős–Turán conjecture (Erdős, Turán, *J. London Math. Soc.* 16 (1941), 212–215) asserts that every basis $S\subseteq\mathbb N_0$ of the semigroup of non-negative integers has *unbounded* representation function — this is Erdős #28 — additive basis forces unbounded representations and remains unresolved after 85 years.

The problem this page solves is the natural analog for infinite abelian groups, posed and studied across [ET41], [N03] (Nathanson), [R90] (Ruzsa), [HH04] (Haddad–Helou): for which infinite abelian groups $G$ does there exist a *perfect* (or at least boundedly-representable) additive basis?

For an integer $n\ge1$ write $nG:=\{ng:g\in G\}$ and $G_n:=\{g\in G: ng=0\}$. Konyagin–Lev's Theorem 1: let $G$ be an infinite abelian group with $|2G|=|G|$.

(i) If $G$ is not the direct sum of a group of exponent 3 and the group of order 2, then $G$ has a perfect basis.

(ii) If $G$ is the direct sum of a group of exponent 3 and the group of order 2, then $G$ has *no* perfect basis, but it does have a basis such that every element has at most two representations (distinct under permuting summands) as a sum of two basis elements.

Theorem 2 (the excluded $|2G|<|G|$ case, i.e. exponent 2): every abelian group of exponent 2 possesses a basis such that every *non-zero* element has at most 36 representations as a sum of two basis elements. (For exponent-2 groups $2G=\{0\}$ is forced to be tiny, so $0$ itself is unavoidably hit $|G|$-many times by any basis of size $|G|$ — Theorem 2 shows this is the *only* obstruction.)

Facts

- Why $|2G|=|G|$ is exactly the right dividing line: if $G$ is infinite with $|2G|<|G|$, then for *any* $S\subseteq G$ with $|S|=|G|$ some element has as many as $|G|$ representations of the trivial form $2s$, $s\in S$ — so no bounded-representation basis of any kind can exist (arXiv:0901.1649, §2, remark before Theorem 2). This class is exactly the exponent-2 groups, handled separately by Theorem 2. - The single genuine exception, $G\cong(\text{exponent-3 group})\oplus\mathbb Z/2$, is pinned down exactly, not just bounded: the paper proves *both* that a perfect basis is provably impossible there *and* exhibits an explicit near-perfect ($r\le2$) basis, so the classification is airtight, not asymptotic. - Corollary 1 (combining Theorem 1, Theorem 2, Ruzsa's 1990 finite-cyclic-group result [R90], and Haddad–Helou's 2004 finite-field result [HH04]): every abelian group $G$ that is either infinite with $|2G|=|G|$, or of prime exponent, has a basis with representation function bounded by an absolute constant — except possibly at $0$ when $G$ has exponent 2. - Explicit constant achieved for exponent 2: 36 (via a union of three "hyperbola" pieces $S_i=\{(x,d_i/x):x\in F^\times\}$ over $F\times F$, a construction adapted from Gabidulin–Davydov–Tombak's 1991 covering-codes paper [GDT91] on codes of covering radius 2 — not the transfinite method). - Full proof uses the Axiom of Choice explicitly (stated up front, §3) — both for the transfinite well-ordering of $G$ and for the linear-basis existence in Lemma 1. - Origin/dedication: the paper is dedicated to Melvyn B. Nathanson's 60th birthday and published as a chapter of his Festschrift, *Additive Number Theory* (Springer, 2010); it directly extends Nathanson's own 2003 result [N03] that $\mathbb Z$ itself has a perfect basis. - Relation to the still-open classical conjecture Erdős #28 — additive basis forces unbounded representations: this result goes in the *opposite* direction from what #28 conjectures — most infinite abelian groups have *no* Erdős–Turán obstruction at all (perfect bases exist generically). This is strong structural evidence that whatever forces boundedness-impossibility in $\mathbb N_0$ is genuinely arithmetic/Archimedean (order-theoretic), not a general group-theoretic phenomenon — a fact already recorded on the Erdős #28 — additive basis forces unbounded representations page as a "structural clue about where a proof would have to bite."

Solution

Answer: for infinite abelian groups with $|2G|=|G|$, the Erdős–Turán problem is fully and exactly resolved — TRUE (perfect basis exists) for all such groups except one precisely-identified exceptional family, where the sharp near-perfect ($r\le2$) substitute is exhibited instead. Konyagin & Lev, arXiv:0901.1649 (2009), published in the Nathanson Festschrift (Springer, 2010).

The transferable technique — two independent tools, one algebraic-reduction and one transfinite-greedy, plus an explicit ad hoc construction for small-exponent cases:

1. Algebraic reduction of prime-exponent groups to $F\times F$ (Lemma 1). If $G$ is an infinite abelian group of prime exponent $p$, there is an algebraically closed field $F$ of characteristic $p$ with $G\cong F\times F$. Proof sketch: take a linear basis $B$ of $G$ as an $\mathbb F_p$-vector space, split it in half ($B=B_1\sqcup B_2$, equal cardinality — possible by basic infinite-cardinal arithmetic), giving $G\cong G_1\times G_2$ with $G_1\cong G_2$; then realize $G_1$ as (the additive group of) the algebraic closure of the rational-function field over $\mathbb F_p$ in variables indexed by $B_1$, using that this closure has the same cardinality as $B_1$. This converts a bare abelian-group question into an explicit algebraic-geometry/polynomial question over a field, which is the move that makes the exponent-3 case tractable at all: over $F\times F$ one can just *write down* a curve. 2. Explicit parabola/quadratic-curve basis for odd prime exponent. Once $G=F\times F$, take $S:=\{(x,x^2):x\in F\}$. The representation count of $(u,v)$ is the number of roots of $x^2+(u-x)^2=v$ — a single quadratic, so always $1$ or $2$. This one-line construction (which the authors note works for *any* odd prime exponent, not just 3) directly gives Theorem 1(ii)'s near-perfect basis on the exponent-3 factor, and combining it with a coset shift by the order-2 element handles the full exceptional family — with a matching impossibility proof (a short direct computation shows any purported perfect basis $T=T_0\cup(h+T_1)$ forces a forbidden double-representation). 3. The general case — transfinite-greedy construction with an explicit forbidden-set budget (the heart of the paper). Let $\mu$ be the initial ordinal of cardinality $|G|$ and well-order $G=\{g_\iota:\iota<\mu\}$. Build an increasing chain $S_0=\varnothing\subseteq S_1\subseteq\cdots\subseteq S_\mu$ (unions at limit ordinals) maintaining the invariant "every element of $G$ has at most one representation as a sum of two elements of $S_\iota$" at every stage, while forcing $g_\iota\in S_\mu+S_\mu$ for every $\iota$. At each successor step, if $g_{\nu-1}$ is not yet covered, add a *fresh pair* $\{s,t\}$ with $s+t=g_{\nu-1}$, chosen to avoid five explicit forbidden sets simultaneously: $s,t\notin S_{\nu-1}+3G$ (technical, when $|3G|<|G|$); $s,t\notin S_{\nu-1}+S_{\nu-1}-S_{\nu-1}$; $2s,2t\notin S_{\nu-1}+S_{\nu-1}$; $s-t\notin S_{\nu-1}-S_{\nu-1}$; $2s-t,\,2t-s\notin S_{\nu-1}$. Each condition is engineered to be exactly what's needed to preserve uniqueness one step further. 4. Why the greedy step always succeeds (Lemma 2, the counting engine). The forbidden sets above each have size $<|S_{\nu-1}|\cdot(\text{const})\le|\nu-1|<|G|$ — strictly fewer than $|G|$ possible values are ever excluded at any single stage, because the chain is built one pair at a time along an ordinal sequence of length $\mu=|G|$. Lemma 2 packages the residual hard case (when $S_{\nu-1}$ could still be "small" relative to $G$) into a clean standalone statement: if $\max(|A|,|B|)<\min(|2G|,|3G|)$ then some $s\in G$ has $2s\notin A$ and $3s\notin B$ simultaneously — proved by a slick contradiction argument using coset-counting in $2G$ and $3G$. This is the load-bearing cardinality lemma: it converts "avoid boundedly-many-relative-to-$|G|$ bad values" into a guaranteed-nonempty-choice statement purely from $|2G|=|3G|=|G|$ (or a coset-disjointness trick when $|3G|<|G|$). 5. A genuinely different, explicit finite/algebraic construction for exponent 2 (Theorem 2). Not transfinite at all — reuses the $F\times F$ reduction (Lemma 1) but builds $S$ as a union of three hyperbola pieces $S_i=\{(x,d_i/x):x\in F^\times\}$ ($i=1,2,3$, $d_1+d_2+d_3=0$), adapting a construction of Gabidulin–Davydov–Tombak from coding theory (covering-radius-2 codes) [GDT91]. Each pairwise representation count reduces to counting roots of an explicit quadratic, capping the total at 18 per Ruzsa-style pair, 36 overall. 6. Portable takeaway. The reusable pattern for building a Sidon-like / uniquely-representable infinite structure in an abelian group is: (a) if the group has prime exponent, reduce via a linear-basis/cardinality argument to an explicit field $F\times F$ and look for a *low-degree curve* (parabola, hyperbola) whose representation count is controlled by Bézout/degree bounds; (b) in general, run a transfinite recursion of length $|G|$, adding one fresh generator-pair per ordinal step while excluding a family of "bad-value" sets that are provably always *strictly smaller than $|G|$* — a cardinal-arithmetic greedy method that works whenever the ambient object is infinite and the per-step obstruction count is genuinely sub-$|G|$. This second tool generalizes far beyond additive bases: any "build an infinite substructure one element at a time, avoiding finitely-or-boundedly-many-relative-to-$|G|$ collisions at each step" problem is a candidate for the same transfinite-greedy-with-a-counting-lemma template.

Related

- Erdős #28 — additive basis forces unbounded representations — the original, still-open Erdős–Turán conjecture on $\mathbb N_0$ (unbounded representation function forced). This solved problem is its infinite-abelian-group analog, resolved in the *opposite* direction (perfect bases exist generically), giving structural evidence that #28's obstruction is Archimedean/order-theoretic, not group-theoretic. - Erdős #40 — sharp density threshold for Erdős–Turán — weaker-hypothesis variant of #28 (density $\gg N^{1/2}/g(N)$), also open; sits in the same unresolved cluster. - Perfect additive basis / unique representation basis ($r_A\\equiv1$) — the $r\equiv1$ (or $r\le2$) object at the center of both the open and solved problems; this page is its main "exists generically" positive result. - Additive representation function $r_{B,h}(n)$ — $r_{S,h}(n)$, the shared central object across the whole Erdős–Turán family. - 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; Konyagin–Lev's Corollary 1 explicitly combines their infinite-group result with Ruzsa's 1990 finite-field result to get one unified "bounded representation function" statement across almost all abelian groups. - concept/transfinite-induction — the general well-ordering/ordinal-recursion proof method; this paper's §3 general case is a clean, reusable worked example of the pattern "recurse along an ordinal of length $|G|$, at each step avoid a provably-sub-$|G|$ forbidden set."