Konstantoulas (2013) — near-cofinite sumset forces representation function $>5$ infinitely often

Statement

Let $A\subseteq\mathbb N$ and let $1_A*1_A(n)=\#\{(a,a')\in A\times A: a+a'=n\}$ be the (ordered) representation function of $n$ by $A$. Suppose the upper density of the un-represented set is small: $$\overline d\big(\mathbb N\setminus(A+A)\big) < \tfrac1{10}.$$ (In particular this holds whenever $A$ is an *asymptotic basis*, i.e. $A+A$ is cofinite — misses only finitely many integers, so its upper density of exceptions is $0<1/10$.) Theorem (Konstantoulas, 2013). Under this hypothesis, $$1_A*1_A(n) > 5 \quad\text{for infinitely many } n.$$ Equivalently, in contrapositive form: if $1_A*1_A(n)\le5$ for *every* $n$, then $\overline d(A+A)\le 9/10$ — a set whose sumset representation count is everywhere $\le5$ cannot come closer than density $9/10$ to covering $\mathbb N$.

Facts

- Source: I. Konstantoulas, "Lower bounds for a conjecture of Erdős and Turán," *Acta Arithmetica* 159 (2013), no. 4, 301–313, DOI [10.4064/aa159-4-1](https://doi.org/10.4064/aa159-4-1); EUDML record [eudml.org/doc/279150](https://eudml.org/doc/279150). - This is a genuine strengthening of the hypothesis-scope, not just a numeric refinement, relative to the two closest predecessor results: - Grekos, Haddad, Helou, Pihko (2003, *J. Number Theory* 102, 339–352): for every *exact* additive basis $A$ (every $n\in\mathbb N$ has $\ge1$ representation, i.e. $A+A=\mathbb N$ with zero exceptions), some $r_n\ge6$. - Borwein, Choi, Chu (2006, *Math. Comput.* 75, 475–484): sharpened this to some $r_n\ge8$, still under the exact-basis hypothesis. - Konstantoulas replaces "$A+A$ misses nothing" with the much weaker "$A+A$ misses only a set of upper density $<1/10$" — a genuinely different, density-flavored hypothesis that also covers many non-bases — and still forces a representation count $>5$ infinitely often. It sits strictly between "no structural assumption at all" and "exact basis," directly targeting the still-open Erdős–Turán conjecture on additive bases (Erdős #28 — additive basis forces unbounded representations: $A+A$ cofinite $\Rightarrow \limsup r_A(n)=\infty$, unbounded, not just $>5$). - erdosproblems.com's own remarks on Erdős #28 — additive basis forces unbounded representations flag Konstantoulas's paper as "the closest published quantitative result to #28's actual hypothesis" among the four (GHHP / Borwein–Choi–Chu / Konstantoulas / the conjecture itself). - The Erdős–Turán conjecture itself — of which this is a partial, density-relaxed lower-bound result — remains open (Erdős #28 — additive basis forces unbounded representations, \$500 prize on erdosproblems.com, unresolved since 1941). - The full journal text (Acta Arithmetica / EUDML) is paywalled; no free arXiv preprint was located. The theorem statement above is verified directly from the published abstract; the proof itself was not read (see provenance).

Solution

The answer: near-cofinite (density $<1/10$ missing) forces $r_A(n)>5$ for infinitely many $n$ — a genuine, quantitative lower bound obtained by relaxing "exact basis" to a density hypothesis while keeping the conclusion almost as strong (threshold $5$ vs. the exact-basis record of $7$/$8$).

The transferable idea — trade a pointwise boundedness assumption for a density obstruction, then contradict the hypothesis on density. This is the shared proof paradigm of the whole GHHP → Borwein–Choi–Chu → Konstantoulas lineage (documented directly, for the exact-basis case, in Haddad's 2015 survey arXiv:1507.05849, which Konstantoulas's paper sits inside the same research cluster as — same core authors' circle, same journal, explicitly framed as attacking the identical conjecture):

1. Assume the negation and turn it into a counting constraint. Suppose, for contradiction, $1_A*1_A(n)\le 5$ (or $\le k$, for whatever threshold is being pushed) for *all* $n$ past some point. A bound on the representation function is a bound on how many times each integer can be hit by pairwise sums from $A$ — i.e. a local multiplicity cap on the sumset $A+A$. 2. Convert the local cap into a global density bound via a counting/moment argument. Summing $1_A*1_A(n)$ over $n\le N$ counts ordered pairs $(a,a')\in A\times A$ with $a+a'\le N$, which is essentially $|A\cap[1,N]|^2$ (up to boundary terms). If every $n$ contributes at most $k=5$ to this sum, but $A\times A$ restricted to $a+a'\le N$ has $\asymp|A\cap[1,N]|^2$ pairs, then the number of distinct sums $n\le N$ actually achieved is forced to be $\gtrsim |A\cap[1,N]|^2/k$ — a lower bound on $|A+A\cap[1,N]|$ purely from the size of $A$ and the multiplicity cap $k$. This is the same "sum $\le$ (count of hit targets) $\times$ (per-target cap)" double-counting inequality that underlies the GHHP/Borwein–Choi–Chu algebraic identities for exact bases (there phrased via the "compliform polynomial"/idempotent generating-function algebra ETB: $a_n^2=a_n$ forces algebraic relations among consecutive $r_n$'s that are infeasible past a small threshold — see Erdős #28 — additive basis forces unbounded representations's Facts for the exact-basis version of this argument). 3. Push the counting argument through the density hypothesis, not an exact-covering hypothesis. Where the exact-basis proofs use $A+A=\mathbb N$ (every target is hit, so the "number of distinct sums $\le N$" is exactly $N$) to get a *contradiction from arithmetic infeasibility of a small finite system* (the "small surprise" identity in Haddad's survey: forcing $c_2=\dots=c_6=1$ algebraically yields $a_6=-1$, impossible), Konstantoulas's generalization instead compares the *counted* lower bound on $|A+A\cap[1,N]|$ from step 2 against the *assumed* upper bound $\overline d(\mathbb N\setminus(A+A))<1/10$ (i.e. $A+A$ must cover $>9/10$ of $[1,N]$ for infinitely many/all large $N$). Pushing the multiplicity cap $k=5$ through the double-counting inequality and comparing against the $9/10$-density floor is what produces the numerical contradiction — the density hypothesis substitutes for exact covering as the source of the arithmetic tension. 4. Contrapositive framing makes the trade explicit. The clean way to see why this is a genuine result rather than a restatement: it says a set whose sumset multiplicity never exceeds $5$ *cannot* get its exceptional density below $1/10$ — density and boundedness of the representation function are in direct tension, and the theorem pins down one specific point on that trade-off curve (compare Erdős #40 — sharp density threshold for Erdős–Turán, which is exactly Erdős's own open question asking for the *sharp* trade-off curve between $|A\cap[1,N]|$ growth and $\limsup r_A(n)=\infty$).

Why this is the technique the open problems actually need. Erdős #28 — additive basis forces unbounded representations (Erdős–Turán, $A+A$ cofinite $\Rightarrow$ $\limsup r_A(n)=\infty$, unbounded — not just $>5$) is precisely the $k\to\infty$, density-$\to0$ limit of the exact same density-vs-boundedness trade-off this theorem instantiates at $k=5$, density-threshold $1/10$. Erdős #40 — sharp density threshold for Erdős–Turán asks directly for the sharp function $g(N)$ governing this trade-off. Any future improvement on either open problem plausibly has to either (a) push Konstantoulas's density threshold down while pushing $k$ up along the same counting method, or (b) find a fundamentally different technique that removes the trade-off's dependence on a fixed density floor altogether — so the counting/moment inequality of step 2–3 above is exactly the reusable core to inherit or to beat.

Related

- Erdős #28 — additive basis forces unbounded representations — Erdős–Turán conjecture on additive bases (open, \$500): the $k\to\infty$ target this theorem approaches from below; erdos/28.md's own Facts cite this exact Konstantoulas result as "the closest published quantitative result to #28's actual hypothesis." - Erdős #40 — sharp density threshold for Erdős–Turán — sharp density-threshold form of Erdős–Turán (open): asks for the precise function $g(N)$ trading off $|A\cap[1,N]|$ growth against forced-unboundedness of $r_A(n)$; this theorem is one concrete, proven data point ($1/10$ exceptional density, threshold $5$) on that same trade-off curve. - Erdős–Tetali theorem — existence of $\\log n$-representation ('economical') additive bases of every order $h$ — the complementary *existence* side (bases with $r_A(n)\asymp\log n$ achievable) versus this theorem's *forcing* side (boundedness is impossible past a small threshold under a density hypothesis) — together they bracket what is and isn't known about how small $r_A(n)$ can be made. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the general family of counting/moment arguments (bound a sum two ways, compare) that step 2 of the Solution above specializes to sumset multiplicity counting.