Erdős–Rényi random-subset-plus-deletion construction (power-law random sets for additive bases)

Statement

The technique in one sentence. To build a set $A\subseteq\mathbb N$ that is simultaneously *dense* (large $|A\cap[1,x]|$) and *additively well-behaved* (some representation function $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\}$ bounded, or growing slower than a target rate) — a tension that cannot be resolved by any *explicit* formula at the time — put each integer $x$ into a random set $A$ independently with probability $p(x)=x^{-\alpha}$ (a *polynomially decaying*, not uniform, inclusion probability — the defining feature that distinguishes this from the Erdős–Rényi *random graph* $G(n,p)$ model), tune $\alpha$ so the expected density and expected representation-count both land where you want them, prove the density lower bound holds almost surely (Chernoff + Borel–Cantelli), prove the representation-count upper bound holds almost surely (first- or second-moment bound + a summable-tail argument, e.g. Markov's inequality per dyadic block + $\sum 1/k^2$), and, if a few isolated integers still misbehave, delete every element responsible for a "bad" (over-full) representation — the alteration/deletion method — leaving a genuinely, exactly-correct set with density unchanged up to lower-order terms.

The probability space (Cilleruelo–Kiss–Ruzsa–Vinuesa, arXiv:0911.2870, Def. 3.1, read in full). Fix $0<\alpha<1$ and $m\in\mathbb N$; define the random sequence $A\subseteq\mathbb N$ by including each $x$ independently with $$ \mathbb P(x\in A)=\begin{cases}0 & x<m\\ x^{-\alpha} & x\ge m.\end{cases} $$

Density theorem (Theorem 3.2, proof read in full). $\mathbb E[A(x)]=\sum_{m\le n\le x}n^{-\alpha}=\frac{x^{1-\alpha}}{1-\alpha}+O_{\alpha,m}(1)$; applying Chernoff's inequality gives $\mathbb P\big(A(x)\le\tfrac12\mathbb E A(x)\big)\le2e^{-\Theta(x^{1-\alpha})}$, summable in $x$, so Borel–Cantelli gives, with probability $1$, $$ A(x)\;\gg\;x^{1-\alpha}. $$

Representation-count bound, $h=2$ case (the original 1960 Erdős–Rényi theorem). With $\alpha=\tfrac12+\epsilon'$ tuned appropriately, the expected number of representations $\mathbb E[r_{2,A}(n)]$ is $O_\epsilon(1)$ uniformly in $n$, and a routine tail bound over all $n\ge m$ makes "some $n$ has $>g$ representations" a summable-probability event — giving, for every $\epsilon>0$, a $g=g(\epsilon)$ and a set $A$ with $$ |A\cap[1,N]|\;\gg_\epsilon\;N^{1/2-\epsilon},\qquad r_{2,A}(n)\;\ll_\epsilon\;1\ \text{ for all }n $$ (quoted verbatim from erdosproblems.com/39's remarks, matching arXiv:0911.2870 Introduction's restatement "for every $g>\tfrac1{2\epsilon}-1$ there is a $B_2[g]$ sequence $A$ with $A(x)\gg x^{1/2-\epsilon}$"). This is the $h=2$, no-deletion-needed instance: for $h=2$, any two representations sharing one addend automatically share the other (so the relevant events are literally independent), and Erdős–Rényi's original proof needs no alteration step at all.

General $h\ge2$ theorem (Theorem 1.2 of arXiv:0911.2870, restating and correcting what Erdős–Rényi *claimed* for general $h$; full machinery below). For every $h\ge2$ and $0<\epsilon<1/h$, there exists $g=g_h(\epsilon)\ll_h\epsilon^{-1}$ and a $B_h[g]$ sequence $A$ (i.e. $r_{h,A}(n)\le g$ for all $n$) with $$ A(x)\;\gg\;x^{1/h-\epsilon}. $$ For $h\ge3$, two distinct representations of $n$ as a sum of $h$ elements can *share* some but not all addends, so the naive independence used at $h=2$ breaks; the fix is the disjoint-representation device: define $r^*_{h,A}(n)$ as the maximum number of *pairwise-disjoint* (no shared coordinate at all) representations of $n$, note $\mathbb P(r^*_{h,A}(n)\ge s)\le\mathbb E[r_{h,A}(n)]^s$ (true independence between disjoint tuples), get a probability-$1$ bound on $r^*_{h,A}$ this way, then use the purely combinatorial lemma $B^*_h[g]\cap B_{h-1}[k]\subseteq B_h[hkg]$ (Lemma 3.9/Remark 3.10, full proof read: bound how many representations can *intersect* a fixed one, using an already-established bound on order-$(h-1)$ representations) to induct on $h$, converting a bound on the disjoint-representation count into a genuine bound on the ordinary representation count $r_{h,A}(n)$.

The deletion/alteration step (Theorem 4.5 of arXiv:0911.2870, full proof read). Call $x\in A$ $(g+1)_h$-bad if $x$ is the *largest* element of some representation $x_1+\cdots+x_{h-1}+x$ that has $\ge g+1$ total representations. $A$ is an exact $B_h[g]$ sequence iff it has *no* bad elements. Even when a raw random $A$ fails to be $B_h[g]$ everywhere, one shows via a first-moment (Markov) bound per dyadic-in-base-$h$ block, summed over blocks with $\sum_k 1/k^2<\infty$, that the count $B(x)$ of bad elements up to $x$ satisfies $B(x)=o(A(x))$ with probability $1-O(1/\log m)$. Since bad elements are a vanishing fraction of $A$, deleting every bad element yields a genuine $B_h[g]$ sequence whose density is unaffected in the leading exponent — this is the "$+$ deletion" half of the technique's name, formalized here as membership in the class $\tilde B_h[g]$ (a set that becomes exactly $B_h[g]$ after removing an $o(\cdot)$-fraction of elements).

Facts

- Origin and what was actually proved in 1960 vs. only claimed. P. Erdős & A. Rényi, "Additive properties of random sequences of positive integers," Acta Arith. 6 (1960), 83–110, proved the $h=2$ (Sidon/$B_2[g]$) case rigorously using the probabilistic method; they *claimed* (arXiv:0911.2870's Introduction, p.1–2, read in full: "In this paper they claimed (but did not prove)...") that the same method extends to all $h\ge2$, but apparently did not notice that for $h\ge3$ two distinct representations can share *some* addends without sharing all of them, breaking the independence the $h=2$ argument relies on. V. H. Vu, "On a refinement of Waring's problem," Duke Math. J. 105 (2000), 107–134, gave the first *correct* proof for general $h$, importing the Sunflower Lemma (to extract $g+1$ pairwise-disjoint representations from "enough" representations) plus ideas from Erdős–Tetali's related basis-existence paper — see Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm) — obtaining $g_h(\epsilon)\ll\epsilon^{-h+1}$. Cilleruelo–Kiss–Ruzsa–Vinuesa (arXiv:0911.2870, 2009/2010) gave a simpler proof avoiding the Sunflower Lemma (using the disjoint-representation device $r^*_{h,A}$ instead), improving the bound to $g_h(\epsilon)\ll_h\epsilon^{-1}$. - The original 1960 scan is not machine-text-readable. users.renyi.hu/~p_erdos/1960-02.pdf is a genuine 28-page image scan; automated text extraction (both WebFetch's summarizer and direct pypdf extraction) fails on it. Every precise statement on this page is therefore sourced through the *modern* re-derivations (arXiv:0911.2870, arXiv:1601.00928) that explicitly quote and restate what the 1960 paper proved, not the original text directly — flagged here for calibration. - Deletion is not always needed — it depends on $h$. For $h=2$, the raw random construction (no deletion) already works exactly, because any two representations of $n$ that share one addend automatically share the other (so bad events are already independent, no cleanup needed). Deletion becomes necessary precisely when $h\ge3$ (overlapping-but-not-identical representations exist) or when a *sharper* constant is wanted than the raw first-moment bound gives — e.g. J. Cilleruelo's own follow-up, "Probabilistic constructions of $B_2[g]$ sequences," Acta Math. Sinica 26 (2010), 1309–1314 (cited via arXiv:1601.00928's reference table, not independently fetched), applies deletion even to the $h=2$ case to sharpen the constant from $g_2(\epsilon)\ll2/\epsilon$ (raw Erdős–Rényi) to $g_2(\epsilon)\ll1/\epsilon$ (alteration method) — i.e. deletion is a general-purpose *sharpening* tool, not only a correctness patch. - Direct application ruling out an Erdős-problem regime. This construction is the cited negative-direction evidence in Erdős #40 — sharp density threshold for Erdős–Turán (Erdős's sharpened, quantitative form of the Erdős–Turán conjecture Erdős #28 — additive basis forces unbounded representations): the $N^{1/2-\epsilon}$ density with bounded representation function rules out every polynomial threshold function $g(N)=N^\epsilon$, $\epsilon>0$ fixed, in #40's statement (erdosproblems.com/40, fetched directly per wiki/problems/40.md's own provenance) — leaving only the *sub-polynomial* regime ($g(N)=\log N$, etc.) genuinely open. It is also the historical starting point of Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set's density chain (best known infinite Sidon-set density is now Ruzsa's $N^{\sqrt2-1+o(1)}$, a *different*, non-probabilistic log/discrete-log technique — see Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — but Erdős–Rényi's $N^{1/2-\epsilon}$-with-bounded-$g$ result remains the reference point the whole $B_2[g]$-density literature (Kolountzakis, Cilleruelo–Trujillo, Pliego arXiv:2405.04154) measures itself against). - A textbook-standard technique, not an isolated trick. arXiv:0911.2870's Introduction explicitly cites N. Alon & J. H. Spencer, *The Probabilistic Method* (Wiley) as "an excellent exposition of the method" this construction instantiates — i.e. the Erdős–Rényi random-subset-plus-deletion construction is presented in the literature as a canonical worked example of the general probabilistic-method-with-alteration paradigm, applied specifically to power-law-probability random subsets of $\mathbb N$ for additive-combinatorics targets (as opposed to, e.g., uniform-probability random graphs/hypergraphs, or random 2-colorings, which are the same general paradigm applied to different combinatorial objects). - Later refinements swap the concentration tool, not the skeleton. J. H. Kim & V. H. Vu, "Concentration of multivariate polynomials and its applications," Combinatorica 20(3) (2000), 417–434 (cited via arXiv:0911.2870's references, not independently fetched) supply a sharper concentration inequality that later authors substitute in place of the raw first/second-moment argument at the "prove the bound holds a.s." step, without changing the random-subset-plus-deletion architecture itself — see Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm) for the closely related Janson-inequality/Vu-polynomial-concentration combination used in the Erdős–Tetali economical-basis theorem, which shares the same overall shape (random set at a reverse-engineered density, control the representation function, no deletion needed there because Janson already gives a lower-tail bound directly).

Technique

WHEN it applies. Whenever the target object is a subset $A\subseteq\mathbb N$ (or similar countable domain) that must simultaneously satisfy (a) a density lower bound ($|A\cap[1,x]|\gg x^{\beta}$ for a target exponent $\beta$) and (b) an additive/representation-count upper bound (some $r_{h,A}(n)$ bounded, or growing more slowly than a target rate), where no explicit algebraic construction achieving both simultaneously is known or sufficient — this is precisely the "dense coverage vs. bounded collisions" tension that recurs across the whole Erdős–Turán/Sidon-set/additive-basis problem family (Erdős #28 — additive basis forces unbounded representations, Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, and by extension any "set with bounded representation function" question — cf. Finite-field parabola/Sidon-block construction with lacunary-scale gluing for a structurally different, purely algebraic route to the same shape of tension, and Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm) for the Janson/Vu-powered sibling used when a *sharp constant* rather than a *polynomial exponent* is the target).

WHY it works (the mechanism). 1. Reverse-engineer the inclusion probability. Choosing $p(x)=x^{-\alpha}$ rather than a constant probability is what makes both a density target *and* a representation-count target simultaneously tunable via a single parameter $\alpha$: $\mathbb E[A(x)]\sim x^{1-\alpha}/(1-\alpha)$ (density grows as $\alpha$ shrinks) while $\mathbb E[r_{h,A}(n)]\ll n^{h(1-\alpha)-1}$ (representation count grows as $\alpha$ shrinks too, in the *opposite* useful direction for large $h$) — the whole art of the method is picking $\alpha$ at the exact point where the density exponent you want is achieved while the representation-count exponent stays controllable by an auxiliary parameter $g$. 2. Independence does the heavy lifting for concentration. Because each $x\in A$ is included *independently*, both the density statistic $A(x)$ (a sum of independent indicators — Chernoff applies directly) and, for $h=2$, the representation-count statistic (also expressible via independent events, since sharing one addend forces sharing the other) concentrate sharply around their means. For $h\ge3$, the fix is to restrict to disjoint tuples ($r^*_{h,A}$) precisely to recover genuine independence, then transport the bound back to ordinary $r_{h,A}$ via the purely combinatorial "how many representations can intersect a fixed one" counting lemma (Lemma 3.9) — this two-step "prove it for the independent sub-statistic, then combinatorially bound the gap to the real statistic" move is the reusable trick whenever raw independence is broken by partial overlaps. 3. Deletion converts "true for most $n$" into "true for every $n$." The raw random construction typically satisfies the target bound for *all but a vanishing fraction* of witnesses (a first-moment/Markov argument, cheaper to prove than a full concentration inequality, suffices here because you only need the *expected count* of violations to be small, not a high-probability bound on each one individually). Since the "bad" elements form an $o(\cdot)$-density subset, removing them cannot damage the leading-order density exponent — this is exactly the general alteration method: build something *almost* right cheaply, then pay a negligible density cost to make it *exactly* right.

HOW to use it to prove things (recombination steps)

1. Identify the two competing statistics — a density statistic $A(x)=|A\cap[1,x]|$ you want large, and a representation/collision statistic $r_{h,A}(n)$ (or an analogous "how many ways can $n$ arise" count) you want small/bounded — and write down the target exponents. 2. Choose the random model. Define inclusion probability $p(x)=x^{-\alpha}$ (or another parametrized family matched to the problem's scaling) and treat $\alpha$ (plus, if needed, an auxiliary bound $g$) as the free parameters to solve for. 3. Compute $\mathbb E[A(x)]$ and $\mathbb E[r_{h,A}(n)]$ via linearity of expectation — routine sums/integrals (geometric-series-style bounds on $\sum_{x<n}x^{-\alpha}$ dominate the representation-count computation, since the largest summand in any representation of $n$ is $\ge n/h$). 4. Prove the density lower bound holds a.s.: Chernoff/Chebyshev on the sum-of-independent-indicators $A(x)$, summed via Borel–Cantelli across a sequence of $x$-values (or dyadic blocks) to get an almost-sure statement, not just a single-$x$ high-probability one. 5. Prove the representation-count upper bound holds a.s.: if $h=2$ (or more generally whenever the relevant collision events are already independent), a direct tail bound suffices. If $h\ge3$ (or whenever collision events overlap only partially), first bound the *disjoint*-representation count $r^*_{h,A}(n)$ (genuinely independent events, so $\mathbb P(r^*_{h,A}(n)\ge s)\le \mathbb E[r_{h,A}(n)]^s$ by literal independence), then transport this to the real $r_{h,A}(n)$ via an inductive combinatorial lemma bounding "how many representations can intersect one fixed representation" (using an already-proved bound for smaller $h$). 6. If the raw construction isn't already exact, define "bad" elements/witnesses precisely (those responsible for a violation of the target bound), bound their *expected count* via Markov's inequality on a convenient decomposition (e.g. per dyadic block, summed via a convergent series like $\sum1/k^2$), conclude the bad set has density $o(A(x))$ with probability $1-O(1/\log m)$ or similar, and delete every bad element — the resulting set is exactly correct and its density is unchanged to leading order. 7. Iterate/induct across the free parameters ($h$, or a chain of nested constructions) if the target statement is itself parametrized (e.g. proving the $h$-case using the $(h-1)$-case as an inductive hypothesis, as in Proposition 3.11).

What this technique does NOT give (limits, when to reach for something else)

- It gives existence, not an explicit/constructive set — for genuinely explicit alternatives with comparable or better exponents, see Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue (log/discrete-log + digit-block encoding, giving $N^{\sqrt2-1+o(1)}$ for exact Sidon sets, better than what this method reaches for $g=1$) and Finite-field parabola/Sidon-block construction with lacunary-scale gluing (finite-field/quadratic-character constructions). - The dependence of the auxiliary bound $g$ on the target exponent gap $\epsilon$ is exponentially bad for naive versions and only polynomial ($g_h(\epsilon)\ll_h\epsilon^{-1}$) after the disjoint-representation refinement — for $g=1$ (true Sidon sets, no slack at all), this technique's exponent bound degrades to something *worse* than the best known ($N^{1/2-\epsilon}$ requires $g\to\infty$ as $\epsilon\to0$; getting all the way to $g=1$ needs a fundamentally different technique). - It does not, by itself, supply the sharpest possible *constant* in front of the leading exponent — that is the domain of sharper concentration tools (Janson's inequality, Kim–Vu polynomial concentration — see Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm)) substituted into the same random-subset skeleton. - It is a lower-tail-adjacent, one-directional existence tool: it proves a set *exists* with the desired properties; it says nothing about how *many* such sets exist, their typical structure, or upper bounds on what any Sidon-type set can achieve (that is a separate, deterministic counting argument — e.g. the classical $N^{1/2}+O(N^{1/4})$ Sidon-set ceiling, Sidon sets / B_2 sets / Golomb rulers).

Related

- Erdős #40 — sharp density threshold for Erdős–Turán — Erdős's sharpened, quantitative form of the Erdős–Turán conjecture asking for the exact threshold growth rate $g(N)$; this construction is the direct source of the negative-direction fact ruling out every polynomial $g(N)=N^\epsilon$. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — best known infinite Sidon-set (i.e. $g=1$ extreme) density question; this construction is the historical starting point of the density chain that Ruzsa's later, non-probabilistic $N^{\sqrt2-1+o(1)}$ construction surpasses. - Erdős #28 — additive basis forces unbounded representations — the parent 85-year-old Erdős–Turán conjecture on additive bases; #40 (and hence this construction's relevance) is explicitly framed as a stronger, quantitative sharpening of it. - Sidon sets / B_2 sets / Golomb rulers — the $g=1$ extremal object family whose density ceiling ($\approx N^{1/2}$) is the theoretical target this construction approaches for large $g$. - B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation — the bounded-but-not-unique-representation ($B_2[g]$) relaxation that is exactly this construction's output object; documents the broader density-vs-$g$ trade-off literature (Kolountzakis, Cilleruelo–Trujillo, Pliego) that measures itself against the Erdős–Rényi baseline. - Additive representation function $r_{B,h}(n)$ — $r_{h,A}(n)$, the statistic this construction's second half (density) and first half (deletion) are jointly built to control. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the more elementary Chebyshev/variance ancestor of the concentration step used here; this construction typically needs only first-moment (Markov) control for the deletion step and Chernoff/Borel–Cantelli for the density step, reserving genuine second-moment/Janson-type machinery for sharper follow-up constants. - Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm) — the closely related random-set-plus-Janson/Vu-concentration sibling technique (same "reverse-engineer a density, control a representation function" skeleton) used for the Erdős–Tetali economical-basis theorem; illustrates how the concentration tool at steps 4–5 can be swapped for a sharper black box without changing the overall architecture. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — a structurally different, fully explicit (log/discrete-log + digit-block + measure-theoretic alteration) technique achieving a better exponent at the $g=1$ extreme; useful contrast for what "probabilistic vs. explicit" trade off in this exact problem family. - Finite-field parabola/Sidon-block construction with lacunary-scale gluing — another explicit-algebraic alternative (quadratic-character/parabola-union constructions) to the same "dense + bounded-representation" target, contrasting a near-exact algebraic certification against this page's probabilistic-existence-plus-cleanup approach.