Pliego 2024 — sharp density-vs-boundedness trade-off for $B_2[g]$ sequences

Statement

For a fixed integer $g\ge 2$, a set $A\subseteq\mathbb N$ is a $B_2[g]$ sequence if every $m\in\mathbb N$ has at most $g$ distinct (unordered) representations $m=a+a'$ with $a\le a'\in A$ — i.e. the representation function $r_A(m)=\#\{(a,a')\in A^2:a\le a',\,a+a'=m\}$ is bounded above by $g$ everywhere ($B_2[1]$ = classical Sidon set).

The question this problem answers

how dense can a $B_2[g]$ sequence be made to grow *while also* being forced to serve as (a weak form of) an additive basis — specifically, while guaranteeing that every sufficiently large $n$ can be written as a sum of three elements of $A$, one of which is small ($a_3\le n^\varepsilon$ for prescribed $\varepsilon$)? This sits directly next to the still-open Erdős–Turán conjecture (Erdős #28 — additive basis forces unbounded representations) and its sharp quantitative form Erdős #40 (Erdős #40 — sharp density threshold for Erdős–Turán), both of which ask about the analogous trade-off for genuine order-2 bases ($A+A$ cofinite, not order-3-with-a-bounded-summand); Pliego's result is the current best negative-direction (construction) data point immediately adjacent to that open threshold.

Facts

- Source: Javier Pliego, "On the Erdős-Turán Conjecture and the growth of $B_2[g]$ sequences," arXiv:2405.04154 (submitted 7 May 2024; Università di Genova / formerly KTH postdoc under the Göran Gustafsson Foundation). Author explicitly thanks Javier Cilleruelo "for introducing him to the topic" and Akshat Mudgal "for inspiring remarks." - Main theorem (Thm. 1.1): for each $g\ge2$ there is a $B_2[g]$ sequence $A$ such that every sufficiently large $n$ can be written $n=a_1+a_2+a_3$, $a_i\in A$, with $a_3 \ll n^{1/g}(\log n)^{2+1/g}$, and $$|A\cap[1,x]| \gg x^{g/(2g+1)} \quad\text{for large } x.$$ - Clean corollary (Cor. 1.1): for every $0<\varepsilon<1$ and integer $g>1/\varepsilon$, there is a $B_2[g]$ sequence $A$ with every large $n=a_1+a_2+a_3$ ($a_i\in A$), $a_3\le n^\varepsilon$, and $|A\cap[1,x]|\gg x^{g/(2g+1)}$. - The trade-off is the point: the exponent $g/(2g+1)$ increases monotonically in $g$ and $\to 1/2$ as $g\to\infty$ — i.e. the more representations you permit ($g$ larger ⇒ weaker "boundedness"), the closer the density can be pushed toward the classical $N^{1/2}$ ceiling that bounds *any* $B_2[g]$ set (a one-line pigeonhole/counting argument gives $|A\cap[1,N]|\ll\sqrt{gN}$ for every $B_2[g]$ set, see Sidon sets / B_2 sets / Golomb rulers). Pliego's construction shows this ceiling is approached (not just bounded above) at the matching exponent, for every fixed $g$, simultaneously with the order-3-basis property. - Why "sharp": this is the first result to eliminate the $x^{o(1)}$/logarithmic loss in the exponent-$g/(2g+1)$ density bound. The abstract states this explicitly: prior constructions attaining this exponent lost a $(\log x)^{-c}$ factor; Pliego's does not. - Comparison chain (all for $B_2[g]$-type density lower bounds): | Source | Bound | Notes | |---|---|---| | Erdős–Rényi 1960 (Acta Arith. 6, 83–110) | $x^{g/(2(g+1))+o(1)}$ | classical probabilistic-deletion construction; weaker exponent than $g/(2g+1)$ | | Cilleruelo (alteration method, pre-2024) | $x^{g/(2g+1)}(\log x)^{-1/(2g+1)+o(1)}$ | matches the exponent $g/(2g+1)$ but with an unavoidable-looking $\log$ loss | | Pliego 2024 (arXiv:2405.04154) | $x^{g/(2g+1)}$, no log loss | first clean/optimal-exponent bound; additionally forces the order-3-basis property with a controlled smallest summand | - Relation to Erdős #40 (Erdős #40 — sharp density threshold for Erdős–Turán): erdosproblems.com/40 asks for which functions $g(N)\to\infty$ does density $\gg N^{1/2}/g(N)$ force $\limsup 1_A*1_A(n)=\infty$ for a genuine order-2 basis. Pliego's construction is cited (in this wiki's own Erdős #40 — sharp density threshold for Erdős–Turán page, independently sourced) as "the most recent progress in this exact cluster" on the negative/construction side — but it is explicitly a fixed-power result ($x^{1/2-\delta}$ for $\delta$ depending on the chosen finite $g$), not a sub-polynomial-correction-factor result, so it does not resolve #40 (which needs a single construction working simultaneously as $g(N)\to\infty$ arbitrarily slowly). It sharpens exactly how close a *bounded*-representation set can get to the $N^{1/2}$ wall. - Not yet found in a peer-reviewed venue as of this search (2026-07-02) — appears to remain an arXiv preprint; flagged as an open provenance gap (see provenance above).

Answer

Yes — for every $g\ge2$, a $B_2[g]$ sequence exists that is simultaneously (a) a "weak" additive basis of order 3 (every large $n$ is $a_1+a_2+a_3$ with $a_3$ polynomially small in $n$) and (b) as dense as $x^{g/(2g+1)}$, with no logarithmic loss — matching, and for the first time cleanly achieving, the natural exponent ceiling that grows to $x^{1/2}$ as $g\to\infty$.

The transferable technique: probabilistic construction by random inclusion, followed by alteration (deletion) governed by a moment (not conditional-expectation) estimate of the "badness" count — swapping the traditional Borel–Cantelli-over-conditional-expectations argument for an integral-moment upper-tail bound, which is precisely the move that kills the log-factor loss.

1. Random base set at the critical density. Build $A$ probabilistically: include each integer $x$ independently with probability $\Pr(x\in A)\asymp x^{-\alpha}$, $\alpha = (g+1)/(2g+1)$ — the exponent reverse-engineered so the expected density lands exactly at the target $x^{g/(2g+1)} = x^{1-\alpha}$. (This is the same "solve for the density that makes the target statistic land on the conjectured critical exponent" move used throughout this cluster, e.g. Erdős–Tetali's construction, Erdős–Tetali theorem — existence of $\\log n$-representation ('economical') additive bases of every order $h$.) 2. Identify the obstruction: over-represented sums. A purely random set at this density will, with positive probability, have some sums $m$ represented more than $g$ times — i.e. it will typically fail to be $B_2[g]$ outright. The classical fix (Erdős–Rényi, and later Cilleruelo) is alteration: delete every element that participates in "too many" coincidences, specifically elements lying in $g+1$ or more simultaneous Sidon-type equations $a_1+a_2=a_3+a_4=\cdots=a_{2g+1}+a_{2g+2}$ (bad tuples, denoted $T_n(A)$ in the paper). 3. Where earlier work lost a log factor. Prior alteration arguments (Cilleruelo's) bounded the number of deletions using conditional-expectation / power-saving estimates, which forced a Borel–Cantelli-style union bound over many scales and left an unavoidable $(\log x)^{-c}$ loss in the final density — the standard cost of the classic "expectation + union bound" alteration recipe when the union has to run over polynomially many thresholds. 4. The key new ingredient: control the upper tail of $|T_n(A)|$ via its integral moments directly, rather than via conditional expectations. Pliego's paper states this explicitly as its central innovation: "a robust estimate for the upper tail of $|T_n(A)|$ which hinges on the analysis of integral moments." By bounding higher moments of the bad-tuple count directly, the argument gets a tail bound sharp enough that the total number of deletions needed can be controlled without the extra logarithmic safety margin that a naive union-bound/Borel–Cantelli approach requires. 5. Alter and conclude. Deleting the (moment-bound-controlled, provably sparse) set of bad elements yields a genuine $B_2[g]$ set that retains density $\gg x^{g/(2g+1)}$ with no loss, and — because the deletions can be arranged to preserve enough of the original random set's coverage — every sufficiently large $n$ still admits a representation $n=a_1+a_2+a_3$ with a controllably small third summand $a_3\ll n^{1/g}(\log n)^{2+1/g}$.

Why this is the reusable part. The generic template — (i) fix a random-inclusion probability solving for the target critical exponent; (ii) recognize the failure mode as a sparse set of "bad" elements defined by an over-counting condition; (iii) when the *standard* alteration recipe (conditional-expectation/Borel–Cantelli) provably loses a logarithmic factor, replace it with a direct integral-moment tail bound on the bad-object count — is the transferable idea. It is a concrete instance of a general principle in probabilistic combinatorics: moment methods can remove log-losses that martingale/conditional-expectation-based alteration arguments structurally cannot avoid, whenever the "badness" statistic is itself amenable to higher-moment (rather than just first-moment) control. This is exactly the kind of technique the open problems in this cluster (Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #28 — additive basis forces unbounded representations) would need to borrow and push further — not at fixed $g$, but for $g=g(N)\to\infty$ simultaneously with $N$, which is the genuinely open regime.

Related

- Erdős #40 — sharp density threshold for Erdős–Turán — Erdős's own sharp quantitative form of the Erdős–Turán conjecture, asking for which $g(N)\to\infty$ density $\gg N^{1/2}/g(N)$ forces unbounded representation; this solved result is the best known negative/construction-side data point immediately adjacent to it, cited directly on that page, but does not resolve it (fixed-$g$ vs. $g(N)\to\infty$). - Erdős #28 — additive basis forces unbounded representations — the original Erdős–Turán conjecture on additive bases of order 2, the "order 2, no bounded-summand relaxation" ancestor question that #40 sharpens and this problem's order-3-with-small-summand relaxation sidesteps. - Erdős–Tetali theorem — existence of $\\log n$-representation ('economical') additive bases of every order $h$ — sibling solved problem in the same technique family: random inclusion probability tuned to a critical exponent, then concentration/alteration to convert "true on average" into "true simultaneously for all targets." Erdős–Tetali uses Janson's inequality + Vu polynomial concentration for the lower tail; Pliego uses a direct integral-moment upper-tail bound for the alteration step — both are "Poisson-paradigm"-style existence proofs for extremal additive objects. - Sidon sets / B_2 sets / Golomb rulers — parent concept: $B_2[g]$ sequences as the bounded-multiplicity generalization of Sidon ($B_2[1]$) sets; the $N^{1/2}$ density ceiling (approached as $g\to\infty$) and the classical Erdős–Rényi/Cilleruelo constructions this result improves on are documented there. - Additive representation function $r_{B,h}(n)$ — $r_A(m)$/$1_A*1_A(n)$, the central object whose boundedness-vs-density trade-off is exactly what this theorem quantifies. - B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation — dedicated concept page for the $B_2[g]$ object family (referenced from Erdős #40 — sharp density threshold for Erdős–Turán; not yet written in this wiki — a natural next concept page, since this solved problem and Sidon sets / B_2 sets / Golomb rulers are currently its only anchors).