Erdős–Rényi (1960) — probabilistic construction of density-$N^{1/2-\\epsilon}$ sets with bounded representation function

Statement

Question (Erdős–Rényi, 1960; the "$g=1$-relaxation" question adjacent to Sidon-set theory). For a set of positive integers $A$, let $r_{h,A}(n)=\#\{(a_1,\dots,a_h)\in A^h : a_1\le\cdots\le a_h,\ n=a_1+\cdots+a_h\}$ be its order-$h$ representation function ($h=2$: $A$ is a genuine *Sidon set* iff $r_{2,A}(n)\le1$ for all $n$). The trivial pigeonhole bound gives $|A\cap[1,N]|\ll N^{1/h}$ for any $A$ with $r_{h,A}$ bounded by a constant $g$ (a "$B_h[g]$ sequence"). The question: is this ceiling actually achievable, up to an arbitrarily small loss in the exponent, once the multiplicity bound $g$ is allowed to grow (but stay finite) as the loss $\epsilon\to0$? Concretely, for $h=2$: does there exist, for every $\epsilon>0$, a set $A\subset\mathbb N$ and a finite $g=g(\epsilon)$ such that $r_{2,A}(n)\le g$ for all $n$, while $|A\cap[1,N]|\gg_\epsilon N^{1/2-\epsilon}$?

Facts

- Source (primary, read in full this session): P. Erdős, A. Rényi, "Additive properties of random sequences of positive integers," *Acta Arithmetica* 6 (1960), 83–110; PDF at users.renyi.hu/~p_erdos/1960-02.pdf. - Answer: yes, proved for $h=2$ (Theorem 8 of the paper) via a direct probabilistic-existence argument; claimed but not proved for general $h\ge2$ in the paper's own closing remark ("By the same method one can prove the existence of $B_l$-sequences $\{a_k\}$ such that $a_k=O(k^{l+\delta})$ for any $\delta>0$, $l=3,4,\dots$"); the general-$h$ case was first correctly proved 40 years later by V. H. Vu ("On a refinement of Waring's problem," *Duke Math. J.* 105 (2000), 107–134), using the Sunflower Lemma (an idea borrowed from Erdős–Tetali 1990), because — as later diagnosed explicitly by Cilleruelo–Kiss–Ruzsa–Vinuesa (arXiv:0911.2870) — "when $h\ge3$ two distinct representations of an integer as a sum of $h$ numbers can share common elements," breaking the exact independence Erdős–Rényi's own $h=2$ proof relies on. - Precise $h=2$ constant, as actually proved: for every $g>\tfrac1{2\epsilon}-1$ there is a $B_2[g]$ sequence $A$ with $A(x)\gg x^{1/2-\epsilon}$ (equivalently: for every positive integer $g$, a sequence with $r_{2,A}(n)\le g$ everywhere and $A(x)\gg x^{\frac12+\frac2g-o(1)}$). - Later sharpenings of the same constant, same underlying method: J. Cilleruelo, "Probabilistic constructions of $B_2[g]$ sequences," *Acta Math. Sinica* (2009), used the explicit "alteration method" to improve the constant to $g_2(\epsilon)>\tfrac1{4\epsilon}-\tfrac12$. Cilleruelo–Kiss–Ruzsa–Vinuesa (arXiv:0911.2870, 2009) proved the general-$h$ case with $g_h(\epsilon)\ll\epsilon^{-1}$ (improving Vu's $g_h(\epsilon)\ll\epsilon^{-h+1}$), and, specializing the alteration method to $h=3$, the sharp $g_3(\epsilon)>\tfrac2{9\epsilon}-\tfrac23$, i.e. for every $g\ge1$ a $B_3[g]$ sequence with $A(x)\gg x^{g/(3g+2)-\epsilon}$. - The trade-off this founded: as $g\to\infty$ (i.e. $\epsilon\to0$), the achievable density exponent $\to1/2$ (for $h=2$) or $\to1/h$ (general $h$) — the theoretical pigeonhole ceiling. This is *exactly* the phenomenon later re-derived, with a sharper exponent formula $x^{g/(2g+1)}\to x^{1/2}$, by Kolountzakis, Cilleruelo–Trujillo, and Pliego (arXiv:2405.04154, 2024), all of whom explicitly cite this construction as their starting point. - Downstream role in this wiki's open-problem cluster: this exact theorem is the citation erdosproblems.com/39 gives for why the target density $N^{1/2-\epsilon}$ in Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set (best-known strict Sidon-set, $g=1$) is *not* trivially achievable — it is achievable only once $g$ is allowed to grow — and it is the citation erdosproblems.com/40 gives for why Erdős #40 — sharp density threshold for Erdős–Turán's threshold function $g(N)$ cannot be any fixed polynomial $N^\epsilon$: this construction already kills every such $g(N)$.

Solution

Answer: yes — for every $\epsilon>0$ there is a finite $g(\epsilon)$ and a set $A$ with $r_{2,A}(n)\le g(\epsilon)$ for all $n$ and $|A\cap[1,N]|\gg_\epsilon N^{1/2-\epsilon}$ (for general $h$: $r_{h,A}\le g_h(\epsilon)$, $|A\cap[1,N]|\gg_\epsilon N^{1/h-\epsilon}$).

**The transferable technique: build the set by independent random coin-flips at a polynomial rate, then either (a) show the "bad" tail probability decays fast enough for Borel–Cantelli to give boundedness directly (works when the representations are index-disjoint, i.e. $h=2$), or (b), when independence fails, keep the random construction but explicitly *delete* the sparse set of elements causing overflow — the "alteration method."**

1. Set up the random-inclusion model at a polynomial rate. Fix $p_n=c\,n^{-\alpha}$ for a target exponent $\alpha=1-\tfrac1h+\epsilon$ (so density order will be $x^{1-\alpha}=x^{1/h-\epsilon}$), and let $A=\{v_k\}$ include each $n$ independently with probability $p_n$. Since $\Sigma p_n=\infty$, Borel–Cantelli makes $A$ a.s. infinite; the strong law of large numbers pins its counting function to $A(N)=|A\cap[1,N]|\sim\Sigma_{n\le N}p_n\sim N^{1-\alpha}$ in expectation and, by a first Chernoff/Borel–Cantelli pass on $A(N)$ itself, almost surely — this is the paper's own §1 apparatus, reused unchanged in every later refinement (Cilleruelo–Kiss–Ruzsa–Vinuesa's Thm 3.2 is the identical statement for a general polynomial rate, proved the identical way). 2. Bound the expected representation count $E[r_{h,A}(n)]$ directly. This is a finite sum/integral over $(h-1)$-tuples below $n$: $E[r_{h,A}(n)]=\Sigma\prod P(x_i\in A)\ll n^{h(1-\alpha)-1}$ — a routine computation (the paper's own §8 computes it in closed form via the Beta function for $h=2$; the general-$h$ version is Lemma 3.5 of arXiv:0911.2870, via a direct $j$-fold-sum/integral bound). This single estimate is the load-bearing fact the entire technique hangs on — everything after this step is bookkeeping to convert "expectation is small" into "true almost surely, everywhere." 3. Case $h=2$ (the original 1960 argument — no deletion needed): exploit index-disjointness for exact independence, then use the FULL exponential moment (Chernoff bound), not just the first moment. For $h=2$, $f(n)=\Sigma_{k<n/2}\xi_k\xi_{n-k}$ sums over *disjoint* index-pairs $\{k,n-k\}$ as $k$ ranges — so, unlike for $h\ge3$, the terms $\xi_k\xi_{n-k}$ are genuinely independent across $k$ (no representation can share an element with a different representation in a way that couples two terms). This lets Erdős–Rényi compute the *full* moment generating function exactly as a product, $M(e^{tf(n)})=\prod_{k<n/2}(1-p_kp_{n-k}+p_kp_{n-k}e^t)$, get a Chernoff-type tail bound $P(f(n)>K+1)\ll n^{-2\epsilon(K+1)}$, sum over $n$, and invoke Borel–Cantelli directly on the sequence of events $\{f(n)>K+1\}$ — giving $f(n)$ bounded by $K=\lceil1/2\epsilon\rceil-1$ for all but finitely many $n$ with probability 1, with zero elements of $A$ ever deleted (the finitely many exceptional $n$ are harmless — a finite number of possibly-larger-but-still-finite representation counts does not affect any asymptotic density statement). 4. Case $h\ge3$ (or sharper constants even at $h=2$): independence breaks — switch to the alteration/deletion method. When representations can share elements (any $h\ge3$), the exact-product moment trick of step 3 is unavailable. The fix, introduced by Cilleruelo (2009) and made fully explicit by Cilleruelo–Kiss–Ruzsa–Vinuesa (arXiv:0911.2870, §4), is: - Define "bad" elements, not bad integers: $x\in A$ is $(g{+}1)$-bad if it is the top term of some representation of some $n$ that has $\ge g+1$ representations in total. $A$ is a genuine $B_h[g]$ sequence iff it has no bad elements. - **Bound the *expected number* of bad elements in each dyadic block $[h^k,h^{k+1})$ using the step-2 estimate plus Markov's inequality — a first-moment argument, no independence required. - Show the bad-element count is $o(A(x))$** — a vanishing *fraction*, not merely finite in absolute terms (this is the key quantitative upgrade over step 3's "finitely many exceptional $n$": here the exceptional set can be infinite, but must have density $0$ relative to $A$ itself). - Delete every bad element from $A$. What remains, $A'=A\setminus\{\text{bad elements}\}$, is by construction a genuine $B_h[g]$ set (Definition 4.2's own phrasing: "$A\in\tilde B_h[g]$ if removing a few elements from it ('a little $o$'), it is a $B_h[g]$ sequence"), and since only an $o(A(x))$ fraction was removed, $A'(x)=(1-o(1))A(x)\gg x^{1/h-\epsilon}$ — the density order survives deletion intact. 5. Recurse across $h$ to control the general case with a purely combinatorial lemma, sidestepping full independence entirely. Cilleruelo–Kiss–Ruzsa–Vinuesa's simpler alternative to Vu's Sunflower-Lemma route: define the auxiliary notion $B_h^*[g]$ (bounded number of pairwise-disjoint representations, easy to bound by a first-moment/Markov argument exactly as in step 4, since disjoint representations *are* independent events by construction), then prove the purely set-theoretic inclusion $B_h^*[g]\cap B_{h-1}[k]\subseteq B_h[hkg]$ — if every representation-cluster has bounded "disjoint-representative count" *and* one order down is already bounded, the full order-$h$ representation count is automatically bounded too. This converts an $h$-body dependency problem into an induction on $h$ using only first-moment estimates at each step, entirely avoiding any need for higher joint moments or the sunflower lemma.

Why this is the reusable part. The general recipe — (i) build the object by independent coin-flips at a tunable polynomial rate; (ii) compute a first-moment (expectation) bound on the "collision"/violation count; (iii) if the violations are exactly independent across witnesses (a structural accident, as with $h=2$ sums), promote step (ii) to a full exponential-moment/Chernoff bound and finish with Borel–Cantelli directly, no deletion needed; (iv) if not (any higher-order or shared-element pattern), instead bound the expected count of "bad" witnesses via Markov, show it is a *vanishing fraction* of the whole random object, and delete them — the object that remains inherits the almost-sure high-probability density estimate essentially for free, since deleting an $o(1)$-fraction cannot change the order of a $\gg x^c$ lower bound — is the "probabilistic-deletion" (alteration) method in its purest form, and is exactly the mechanism every downstream $B_2[g]$/$B_h[g]$-type existence result in this wiki's Sidon-set cluster (Kolountzakis, Cilleruelo–Trujillo, Pliego arXiv:2405.04154) reuses, tuning only the target exponent $\alpha$ and the definition of "bad."

Related

- Erdős #40 — sharp density threshold for Erdős–Turán — open: for which threshold functions $g(N)\to\infty$ does $|A\cap[1,N]|\gg N^{1/2}/g(N)$ force $\limsup r_{2,A}(n)=\infty$? This page's construction is the exact tool that rules out every fixed polynomial $g(N)=N^\epsilon$ — the closed, non-open half of #40's landscape. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — open: does an infinite strict Sidon set ($g=1$ exactly, not merely bounded) achieve density $N^{1/2-\epsilon}$ for every $\epsilon$? This page's theorem shows the target density $N^{1/2-\epsilon}$ *is* reachable once $g$ is allowed to grow with $1/\epsilon$ — the open question is whether the same density survives forcing $g\equiv1$. Best known genuine-Sidon exponent is Ruzsa's $N^{\sqrt2-1+o(1)}\approx N^{0.4142}$, strictly below this page's $N^{1/2-\epsilon}$. - Erdős #28 — additive basis forces unbounded representations — the Erdős–Turán conjecture ($L^\infty$/uniform-boundedness of the representation function of a genuine additive *basis*, i.e. $r_{2,A}(n)\ge1$ everywhere as well as bounded); this page's construction is a basis-*building block* technique but the theorem here does not itself construct a basis, only a bounded-but-not-necessarily-covering set — a distinct (weaker) requirement. - Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — how large can $\limsup|A\cap[1,N]|/N^{1/2}$ be for a genuine ($g=1$) Sidon set; same critical exponent $N^{1/2}$, complementary "no relaxation allowed" endpoint of the same trade-off this page's $B_2[g]$ result sits at the other end of. - Sidon sets / B_2 sets / Golomb rulers — parent concept; its own Facts section already documents the $N^{g/(2g+1)}\to N^{1/2}$ trade-off this page's theorem originates. - Additive representation function $r_{B,h}(n)$ — the central object $r_{h,A}(n)$; already forward-links to this page's slug family as "the 1960 probabilistic-deletion method." - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs / B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation *(forward link — not yet written)* — the general moment-method toolkit this page's Chernoff/Borel–Cantelli (step 3) and Markov/alteration (step 4) machinery both instantiate. - Cilleruelo, J., Kiss, S.Z., Ruzsa, I.Z., Vinuesa, C., "Generalization of a theorem of Erdős and Rényi on Sidon Sequences," arXiv:0911.2870 (2009) — the paper that both completes (general $h$) and sharpens (explicit alteration-method constants) this page's construction, and the direct source for the deletion-method mechanics documented in step 4–5 above. - Vu, V.H., "On a refinement of Waring's problem," *Duke Math. J.* 105 (2000), 107–134 — first correct proof of the general-$h\ge3$ case Erdős–Rényi only claimed, via the Sunflower Lemma. - Pliego, A., "On the Erdős-Turán Conjecture and the growth of $B_2[g]$ sequences," arXiv:2405.04154 (2024) — most recent sharpening of the same density-vs-boundedness trade-off ($x^{g/(2g+1)}$), explicitly citing "earlier results of Cilleruelo and of Erdős and Rényi" as its starting point.