Additive-energy / pigeonhole averaging identity — $\sum_n r_A(n)=|A|^2$ forces large representation values on the dense side

Statement

Let $A\subseteq\mathbb Z$ (or $\mathbb N_0$, or any abelian group) be finite, and let $$r_A(n) = \#\{(a,a')\in A\times A : a+a'=n\}$$ be the (ordered) representation function. Summing over all $n$ (equivalently, over the range $A+A$ occupies) counts every ordered pair exactly once, so $$\sum_n r_A(n) = |A|^2.$$ This is the identity — trivial to prove, load-bearing throughout additive combinatorics. Two immediate quantitative sharpenings drive almost every application:

Truncated / dense-basis form. If $A\subseteq\mathbb N$ has $A+A$ covering (or containing) an interval, e.g. $B$ a basis of order $h$ with $B+\cdots+B$ ($h$ summands) cofinite, then restricting to $n\le N$ gives (en.wikipedia.org/wiki/Erdős–Turán_conjecture_on_additive_bases, "Progress" section, quoted directly) $$n \;\le\; \sum_{m=1}^n r_{B,h}(m) \;\le\; |B\cap[1,n]|^h,$$ the left inequality from coverage (every $m\le n$ has $\ge1$ representation) and the right from the trivial bound "at most $|B\cap[1,n]|^h$ ordered $h$-tuples total." This yields the pigeonhole lower bound on density: $|B\cap[1,n]|\ge n^{1/h}$.

Averaging / dense-side forcing form. Because $A+A\subseteq[2\min A,\,2\max A]$, an interval of length $O(N)$ when $A\subseteq[1,N]$, the identity $\sum_n r_A(n)=|A|^2$ forces the average value of $r_A$ over that range to be $$\overline{r_A} \;=\; \frac{|A|^2}{O(N)}.$$ By pigeonhole, some $n$ has $r_A(n)\ge\overline{r_A}$. Whenever $|A\cap[1,N]|\gg N^{1/2}g(N)$ for some $g(N)\to\infty$, this forces $\overline{r_A}\to\infty$, hence $\max_n r_A(n)\to\infty$ — and running this over an increasing sequence of $N$ for a fixed infinite $A$ forces $\limsup_n r_A(n)=\infty$. This is the mechanical "easy direction" that brackets the open Erdős–Turán-family problems (density strictly *above* the $N^{1/2}$ threshold trivially forces unboundedness; the genuinely hard, still-open content is what happens at or just below that threshold).

Second-moment sharpening (additive energy). Cauchy–Schwarz strengthens plain averaging into a two-sided identity/inequality pair. Define the additive energy $$E(A) := \sum_n r_A(n)^2 = |\{(a,b,c,d)\in A^4 : a+b=c+d\}|$$ (Tao–Vu, *Additive Combinatorics*, Cambridge Univ. Press, 2006, Ch. 2; B. Green, "Additive Combinatorics" lecture notes Ch. 4 "Additive Energy and Balog–Szemerédi–Gowers," people.maths.ox.ac.uk/greenbj/papers/addcomb2009-4.pdf, PDF read directly). Applying Cauchy–Schwarz to $\sum_n r_A(n)=|A|^2$ against the (at most $|A+A|$)-many nonzero terms gives $$E(A) \;\ge\; \frac{|A|^4}{|A+A|}.$$ So: a small sumset ($|A+A|$ close to $|A|$) forces large energy — i.e. forces the representation function to concentrate heavily on few values rather than merely having a large max somewhere. This is the exact energy-theoretic upgrade of the plain-averaging pigeonhole fact: plain averaging only guarantees *some* $n$ with $r_A(n)\ge|A|^2/|A+A|$; the energy bound is the $\ell^2$ statement that the *bulk* of the mass, not just one point, must be concentrated when $|A+A|$ is small.

Facts

- The identity itself needs no hypothesis on $A$ — it holds for every finite $A$ in every abelian group, purely by re-indexing a double sum. All the content of "pigeonhole averaging" as a *technique* lives in what you plug in for the summation range and what auxiliary hypothesis (coverage, boundedness, sumset size) you combine it with. - This is literally the first, and easiest, half of the Erdős–Turán conjecture toolkit. Wikipedia's own "Progress" section on the Erdős–Turán conjecture on additive bases (en.wikipedia.org/wiki/Erdős–Turán_conjecture_on_additive_bases) states the $h$-fold truncated form verbatim and derives $|B\cap[1,n]|\ge n^{1/h}$ from it — this is *why* an additive basis of order $h$ can never be sparser than $n^{1/h}$, a floor fact used everywhere in this wiki's representation-function cluster (see Additive representation function $r_{B,h}(n)$ Fact #1 and Technique items 1–2, which document both directions — density-from-boundedness and unboundedness-from-density — in full). - **It is the exact mechanism flagged, but not resolved, in Erdős #40 — sharp density threshold for Erdős–Turán.** Erdős #40 — sharp density threshold for Erdős–Turán asks for the precise threshold function $g(N)\to\infty$ such that density $\gg N^{1/2}/g(N)$ forces $\limsup r_A(n)=\infty$; its own Related section already forward-references "concept/additive-energy / Additive-energy / pigeonhole averaging identity — $\sum_n r_A(n)=|A|^2$ forces large representation values on the dense side" as exactly the trivial dense-side bound (density $\gg N^{1/2}h(N)$, $h\to\infty$, forces unboundedness by this identity) that brackets the problem but does not touch its genuinely open sub-polynomial-$g$ regime. A logged AI attempt (gpt-5.2, per problems/40.md's own provenance) independently rediscovered exactly this fact and nothing stronger — direct evidence of its status as the "obvious first move," not a research contribution by itself. - Cauchy–Schwarz on the same identity is the origin of the additive-energy machinery underlying Balog–Szemerédi–Gowers and the whole Freiman/Plünnecke–Ruzsa inverse-sumset toolkit (Green's lecture notes, Ch. 4, PDF read directly): $E(A)\ge|A|^4/|A+A|$ converts "sumset is small" into "energy is large," and BSG partially inverts this (large energy $\Rightarrow$ a large structured subset with small sumset). See Additive representation function $r_{B,h}(n)$ Fact/Technique on the additive-energy bridge. - Same identity underlies the elementary $O(\sqrt N)$ Sidon-set upper bound. For a Sidon set $A\subseteq\{1,\dots,N\}$ (all pairwise differences distinct, i.e. $r_{A-A}(t)\le1$ for $t\ne0$), $\sum_t r_{A-A}(t)=|A|^2$ combined with the range constraint $t\in(-N,N)$ gives $|A|^2\lesssim N\cdot 1$, i.e. $|A|\lesssim\sqrt N$ — the same averaging move in its very simplest, one-line form (see Sidon sets / B_2 sets / Golomb rulers Facts, "elementary upper bound"). The refined $\sqrt N+O(N^{1/4})$ bound (Erdős–Turán 1941) and its descendants (Lindström, Balogh–Füredi–Roy, O'Bryant, Carter–Hunter–O'Bryant) replace the crude range bound with a windowed/shifted version of the *same* identity — see Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) and Lindström-style shift/collision double-counting (upper-bound method for Sidon sets) for the sharpened engines built directly on top of this base identity. - Distinct from, and strictly weaker than, the Erdős–Fuchs theorem (Erdős–Fuchs theorem: average representation count can't be too close to linear). Pigeonhole averaging bounds $\sum_n r_A(n)$ or $\sum_{n\le N}r_A(n)$ by a *crude* range/pigeonhole argument, giving existence of *some* large value or a density floor; Erdős–Fuchs is a much sharper analytic (generating-function/Parseval) statement about how close the cumulative sum $\sum_{n\le N}r_A(n)$ can track a *smooth target function* $cN$. Do not conflate: pigeonhole averaging is the blunt, always-available first move; Erdős–Fuchs is a delicate impossibility theorem reached for only when smoothness (not mere size) is the question. - It is a genuinely two-way tool. Direction (a): boundedness hypothesis $\Rightarrow$ density lower bound (used to show bases can't be too sparse). Direction (b): density hypothesis $\Rightarrow$ unboundedness (used to show representation counts can't stay bounded once density is high enough). Both directions are "trivial" in the sense of requiring no cleverness beyond the identity itself — the open problems in this cluster (Erdős #28 — additive basis forces unbounded representations, Erdős #40 — sharp density threshold for Erdős–Turán) live exactly in the regime where *neither* direction of this trivial argument applies (density too low for (b), no boundedness hypothesis given for (a) directly).

Technique

How to actually deploy this identity when attacking a new representation-function problem (recombination-ready steps):

1. Write down the identity for your exact object. Decide ordered vs. unordered, $h$-fold vs. $2$-fold, sums vs. differences — the identity $\sum_n r_A(n)=|A|^2$ (or its $h$-fold analog $\sum_n r_{A,h}(n)=|A|^h/(\text{symmetry factor})$) is always available for free; the only work is matching it to the problem's exact counting convention. 2. Identify the range the sum effectively runs over. If $A\subseteq[1,N]$, then $A+A\subseteq[2,2N]$ — a range of size $O(N)$, *not* $O(N^2)$. This mismatch between the $|A|^2$ total mass and the $O(N)$-sized range is the entire mechanism: it is what forces a large average whenever $|A|\gg\sqrt N$. 3. Direction (a) — extract a density floor from a boundedness/coverage hypothesis. If you're told (or trying to show) $r_{B,h}(n)\le M$ for all $n\le N$ in the covering range, combine with the coverage lower bound $\sum_{n\le N}r_{B,h}(n)\ge N$ to get $|B\cap[1,N]|^h\ge N$, i.e. $|B\cap[1,N]|\ge N^{1/h}$. This is the mechanical first move in essentially every Erdős–Turán-family problem (Erdős #28 — additive basis forces unbounded representations, Erdős #40 — sharp density threshold for Erdős–Turán, 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)) — always do this step first; it costs nothing and calibrates what "trivial" already gives you before reaching for harder machinery. 4. Direction (b) — extract unboundedness from a density hypothesis. If $|A\cap[1,N]|\gg N^{1/h}g(N)$ with $g(N)\to\infty$, plug into $\sum_{n\le hN}r_{A,h}(n)\asymp|A\cap[1,N]|^h$ against the $O(N)$-sized range to get average value $\gg g(N)^h\to\infty$, hence $\max_{n\le hN}r_{A,h}(n)\to\infty$; running over $N\to\infty$ gives $\limsup_n r_{A,h}(n)=\infty$. Use this to instantly dispatch the "easy" half of any density-vs-boundedness threshold question, and to locate precisely where the genuinely open regime begins (immediately below the threshold this argument reaches). 5. Upgrade to Cauchy–Schwarz / additive energy when you need concentration, not just a single large value. If the question is about sumset size, structure, or "how much" of the representation mass is concentrated (not just "is some value large"), apply Cauchy–Schwarz to the same identity: $E(A)=\sum_n r_A(n)^2\ge|A|^4/|A+A|$. This is the standard entry point into the Freiman/Plünnecke–Ruzsa/Balog–Szemerédi–Gowers toolkit — reach for it whenever "small sumset" or "structured set" needs to be extracted from a counting hypothesis, rather than just "some large representation value." 6. Sharpen with windowing/shifting when the crude range bound is too lossy. The plain identity uses the crudest possible range bound ($A+A\subseteq[2,2N]$, size $O(N)$); when this is not sharp enough (e.g. to shave error terms from $O(\sqrt N)$ down to $\sqrt N+O(N^{1/4})$ for Sidon sets), replace the flat range with a sliding window and re-run the same summing-and-Cauchy–Schwarz argument locally — this is exactly the block-decomposition / weighted-Cauchy–Schwarz engine documented in Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) and the shift/telescoping variant in Lindström-style shift/collision double-counting (upper-bound method for Sidon sets). Both are this page's identity, applied windowed instead of globally. 7. WHEN this technique applies: any problem of the form "a set with $h$-fold sums covering / densely hitting a range — what does that force about density, or about how large/concentrated the representation counts must be?" Reach for this identity *first*, before any Fourier-analytic (Erdős–Fuchs), probabilistic (second-moment/Janson), or algebraic (polynomial-method) machinery — it is free, requires no hypothesis beyond finiteness, and typically either resolves the "easy direction" outright or precisely locates the boundary where a harder technique is actually needed. 8. WHEN it does NOT apply / known ceiling: pure pigeonhole averaging can only ever produce a bound of the shape "average $\gg X$ $\Rightarrow$ some/many values $\gg X$" — it cannot show a $\limsup$ is infinite (as opposed to merely large-at-density-$N$) without an extra limiting argument over $N\to\infty$, and it cannot resolve threshold-regime questions where the density hypothesis sits *below* the $N^{1/h}$-type critical exponent (exactly the still-open content of Erdős #28 — additive basis forces unbounded representations and Erdős #40 — sharp density threshold for Erdős–Turán) — no amount of re-massaging the same first/second-moment identity closes that gap; a structurally different idea is needed. It also says nothing about *smoothness* of the cumulative sum (that is Erdős–Fuchs theorem: average representation count can't be too close to linear's separate, sharper territory), and nothing about *uniqueness/uniform bound* refinements beyond "some value is large" (that is the Cauchy–Schwarz/energy upgrade, item 5, or the finite case-analysis techniques of Borwein–Choi–Chu (2006) — the representation function of any order-2 additive basis cannot be bounded by 7).

Related

- Additive representation function $r_{B,h}(n)$ — the parent concept page for the whole representation-function family; this page's identity is documented in situ there (Fact #1, Technique items 1–2, and the additive-energy Fact/Technique item 7) and is factored out here as its own reusable concept per that page's and Erdős #40 — sharp density threshold for Erdős–Turán's own forward-references. - Erdős #28 — additive basis forces unbounded representations — the central open Erdős–Turán conjecture; this identity gives the density-floor half of its toolkit ($|B\cap[1,n]|\ge n^{1/2}$ from coverage) but does not touch the genuinely open $\limsup=\infty$ claim. - Erdős #40 — sharp density threshold for Erdős–Turán — explicitly brackets its open sub-polynomial-density regime using exactly this identity as the "trivial, non-open direction" (dense side forces unboundedness); the precise boundary of where this technique stops working is the entire content of the problem. - Erdős–Fuchs theorem: average representation count can't be too close to linear — the sharper, Fourier/Parseval-based sibling impossibility theorem about *smoothness* of the cumulative sum $\sum_{n\le N}r_A(n)$, as opposed to this page's crude size/pigeonhole statement; do not conflate the two. - Sidon sets / B_2 sets / Golomb rulers — the identity's simplest instantiation ($r_{A-A}(t)\le1\Rightarrow|A|\lesssim\sqrt N$), and the historical starting point (Erdős–Turán 1941) for every windowed refinement. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — the windowed/weighted-Cauchy–Schwarz sharpening of this same base identity, used for state-of-the-art Sidon-set and Golomb-ruler bounds. - Lindström-style shift/collision double-counting (upper-bound method for Sidon sets) — the sibling finite-extremal-count sharpening (telescoping shifted differences) of this identity, used for the current-record $h(N)\le N^{1/2}+O(N^{1/4})$ Sidon bounds. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the probabilistic cousin: where this page's Cauchy–Schwarz/energy step is a deterministic $\ell^2$ argument on a fixed finite set, the second-moment method is the same Cauchy–Schwarz/Chebyshev mechanism applied to a random variable's variance, used for existence (not just forcing) results.