Erdős–Fuchs theorem: average representation count can't be too close to linear

Statement

Let $A\subseteq\mathbb N_0$ be an infinite set of non-negative integers and let $$r_{A,2}(n)=\#\{(a,a')\in A\times A: a+a'=n\}$$ be the (ordered) representation function counting ways to write $n$ as a sum of two elements of $A$. Let $$s_{A,2}(N)=\sum_{n\le N} r_{A,2}(n)$$ be the accumulated (average/cumulative) representation function.

Erdős–Fuchs theorem (1956). For any constant $c>0$, it is impossible that $$s_{A,2}(N) = cN + o\!\left(N^{1/4}\log(N)^{-1/2}\right).$$ In words: the average number of representations of $n\le N$ as a sum of two elements of $A$ can never track a linear function $cN$ to within an error smaller than $\asymp N^{1/4}$ (up to a log factor) — some genuine oscillation of size at least $N^{1/4}$-ish is unavoidable, no matter how $A$ is chosen. This holds for every infinite $A\subseteq\mathbb N_0$; there is no exceptional construction.

Sharp form (log factor removed). Montgomery & Vaughan (1990, "On the Erdős–Fuchs theorem," in *A Tribute to Paul Erdős*) proved the stronger $$\max_{N\le M}\big|s_{A,2}(N)-cN\big| = \Omega(M^{1/4}\log^{-1/4}M),$$ and a result of Jurkat (reported via Hayashi's PhD thesis) removes the log factor entirely, giving $\Omega(N^{1/4})$ (en.wikipedia.org/wiki/Erdős–Fuchs_theorem; planetmath.org/erdhosfuchstheorem). This is essentially sharp: Ruzsa (1997) constructed sets $A$ achieving $s_{A,2}(N)=cN+O(N^{1/4}\log N)$, pinning the true exponent at exactly $1/4$ up to at most a log factor.

Historical origin. Hardy (1915) proved the prototype for $A=Q=\{0,1,4,9,\dots\}$ (perfect squares, so $s_{Q,2}(N)$ counts lattice points under a quarter-circle / representations as sums of two squares): $\limsup_{n\to\infty}|s_{Q,2}(n)-\pi n|/(n^{1/4}\log(n)^{1/4})>0$. Erdős and Turán (1941) conjectured the much stronger $s_{A,2}(n)=cn+O(1)$ is impossible for *any* additive basis $A$ (this stronger conjecture is a *separate*, still relevant, historical companion — see Erdős #28 — additive basis forces unbounded representations); Erdős and Fuchs (1956, *J. London Math. Soc.* 31:67–73) proved the theorem above, which is weaker in the error term ($o(n^{1/4}\log^{-1/2}n)$ rather than $O(1)$) but fully general and unconditional.

Facts

- Sign of the result: a "no basis is too smooth" impossibility theorem, not an existence/construction result. It says nothing about whether $A$ is a basis (covers all large $n$) — $r_{A,2}(n)$ can be zero for infinitely many $n$ and the theorem still applies; it only forbids the *average* $s_{A,2}(N)/N$ from converging to a positive constant too fast/smoothly. - The exponent $1/4$ is architectural, not an artifact of one proof. It recurs unchanged across every refinement and generalization found: Montgomery–Vaughan (1990, log-power reduced), Jurkat/Hayashi (log factor removed entirely), Ruzsa's 1997 converse construction (matching $O(N^{1/4}\log N)$), Sárközy's 1980 $k$-near-sequence extension (error form $o(n^{1/4}\log(n)^{1-3k/4})$), and the 2020 ordered-representation-function extension (arXiv:1911.12313, same $o(N^{1/4}\log^{-1/2}N)$ form). This is strong evidence the $1/4$ comes from the geometry of the proof method (a stationary-phase/singularity-order computation on the unit circle), not from a specific counting trick. - Generalizes beyond linear principal terms. Sándor (arXiv:2009.03392, 2020) proves Erdős–Fuchs-type theorems where the target "smooth" function is not $cn$ but a general discrete convolution $\sum_{k=0}^n b_kb_{n-k}$ for a sequence $b_n>0$ with $\limsup b_n<1$ — both for the pointwise $r_{A,2}(n)$ and the accumulated $s_{A,2}(N)$ forms. This is the natural machine to reach for when a problem's target growth rate is not literally linear (e.g. $c\log n$-type kernels, relevant to Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$). - Generalizes to ordered/multi-set representation functions. arXiv:1911.12313 ("An Erdős–Fuchs Theorem for Ordered Representation Functions," *Ramanujan J.* 2020) extends the impossibility to ordered $h$-fold representation counts $r_k^{\le}(A,n)$, $r_k^{<}(A,n)$, with the same $o(n^{1/4}\log^{-1/2}n)$-impossibility and an additional mean-squared-error form $\limsup E^\star_{k,c}(A,n)>0$. - A simplified, Fourier-series-free proof exists. D. J. Newman, "A simplified proof of the Erdős–Fuchs theorem," *Proc. AMS* 75(2):209–210 (1979) — the original Erdős–Fuchs argument used special results from the theory of Fourier series; Newman's version avoids these, using a more elementary generating-function/complex-analytic estimate. - **Distinct from, but a close historical companion of, the Erdős–Turán conjecture (Erdős #28 — additive basis forces unbounded representations).** Erdős–Turán is about the *pointwise* $\limsup r_{A,2}(n)$ for a covering ($A+A$ cofinite) set and remains open since 1941. Erdős–Fuchs is about the *cumulative average* $s_{A,2}(N)/N$ for *any* infinite $A$ (no covering hypothesis needed) and has been fully resolved (and sharpened) since 1956. Both live under the umbrella "additive bases cannot have arbitrarily regular representation functions," but are logically independent statements — resolving one does not resolve the other. See Additive representation function $r_{B,h}(n)$ for the full family tree.

Technique

How the theorem is proved (the transferable engine — generating functions + Parseval on the unit circle):

1. Encode $A$ as a power series. Form $F(z)=\sum_{a\in A}z^a$ for $|z|<1$. Then $F(z)^2=\sum_n r_{A,2}(n)z^n$, so the representation function is literally the coefficient sequence of $F(z)^2$. 2. Translate the hypothesis into an analytic singularity statement. The hypothesis "$s_{A,2}(N)=cN+o(N^{1/4}\log^{-1/2}N)$" is, by a Tauberian/Abelian argument, equivalent to $F(z)^2$ behaving like $c/(1-z)$ as $z\to1^-$ along the real axis (the accumulated sum turning linear forces the generating function to have a simple-pole-like singularity of residue $c$ at $z=1$). 3. Apply Parseval on circles $|z|=r\to1^-$. Parseval's identity gives $\frac{1}{2\pi}\int_0^{2\pi}|F(re^{i\theta})|^4\,d\theta = \sum_n r_{A,2}(n)^2 r^{2n}$ (mean-square of $F^2$ on the circle equals the $\ell^2$-sum of its coefficients). The over-strong smoothness hypothesis forces $|F(z)|^2$ to be simultaneously (a) concentrated near $z=1$ (to produce the linear growth $cN$) and (b) small elsewhere on the circle (forced by the tight error bound) — these two requirements are quantitatively incompatible once the error term is smaller than $N^{1/4}$-ish, producing a contradiction via the Parseval identity. The precise size of the incompatibility is where the $N^{1/4}$ exponent comes from. 4. Newman's simplification (1979) achieves the same conclusion with a more direct complex-analytic/generating-function estimate, sidestepping the original's Fourier-series machinery — useful as the more approachable proof to actually work through. 5. WHEN this technique applies: any time a problem asks "can the *cumulative/average* count of some additively-defined quantity track a smooth target function $g(N)$ (e.g. $cN$) to within a small error?" — encode the counted object as a generating function, relate the smoothness hypothesis to a singularity of a *power or product* of that generating function at $z=1$ (or more generally at the relevant boundary point), and apply a Parseval/$L^2$-mean-square estimate on a circle approaching that boundary to derive a lower bound on the unavoidable error. This is the reusable move for "no [additive structure] can be too smooth/regular" impossibility results — the direct ancestor and template for the Sándor (arXiv:2009.03392) and ordered-representation (arXiv:1911.12313) generalizations, and the natural first machine to reach for on any smoothness-flavored variant of representation-function problems such as Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$ and Erdős #1145 — two-set a_n/b_n→1 additive-basis generalization is OPEN; its own necessity clause is settled by Erdős #331 (Ruzsa's digit-parity construction, DISPROVED). 6. What this technique does NOT do: it produces impossibility results about *smoothness of averages*, not about *boundedness or unboundedness of pointwise values* (that is the separate pigeonhole/counting toolkit used for Erdős #28 — additive basis forces unbounded representations-style problems — see Additive representation function $r_{B,h}(n)$ Technique items 1–2). Do not reach for Erdős–Fuchs machinery when the target statement is about $\limsup r_{A,2}(n)$ itself rather than about $\sum_{n\le N} r_{A,2}(n)$.

Related

- Additive representation function $r_{B,h}(n)$ — the parent concept page for the whole representation-function family; contains the Erdős–Fuchs fact and technique in situ alongside the sibling Erdős–Turán/Erdős–Tetali/additive-energy results, and the fuller cross-reference network. - Erdős #28 — additive basis forces unbounded representations — the central, still-open Erdős–Turán conjecture (1941): order-2 basis + cofinite sumset $\Rightarrow\limsup r_{B,2}(n)=\infty$. Historically paired with Erdős–Fuchs (both descend from 1941 Erdős–Turán questions about representation-function regularity) but logically independent and NOT implied by or implying Erdős–Fuchs. - Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$ — asks whether $r_A(n)/\log n\to c\ne0$ as a genuine limit; the Erdős–Fuchs generating-function/Parseval machine is flagged as the direct technical ancestor of partial results here (Sárközy 1980, Horváth 2007), and Sándor's general-principal-term extension (arXiv:2009.03392) is the most promising unexploited tool for further progress. - Erdős #1145 — two-set a_n/b_n→1 additive-basis generalization is OPEN; its own necessity clause is settled by Erdős #331 (Ruzsa's digit-parity construction, DISPROVED) — two-sequence generalization ($A,B$ with $a_n/b_n\to1$); the ordered/two-set Erdős–Fuchs extension (arXiv:1911.12313) is the direct analytic analog in this exact setting. - Sidon sets / B_2 sets / Golomb rulers — the extremal $r_{B,2}\le1$ special case; shares the representation-function/generating-function toolkit but is governed by different (counting/extremal, not smoothness) machinery. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the Parseval/$L^2$-mean-square step in the Erdős–Fuchs proof is a close analytic cousin of the Chebyshev/second-moment concentration arguments catalogued there.