Cilleruelo–Tesoro (2012/2015) — dense infinite $B_3,B_4$ sequences via Gaussian-prime arguments (construction side)

Statement

For an integer $h\ge2$, a set $B\subset\mathbb N$ is a $B_h$ sequence if all sums $b_1+\cdots+b_h$ ($b_k\in B$, $b_1\le\cdots\le b_h$) are distinct ($h=2$ is the classical Sidon/$B_2$ case). Write $B(x):=|B\cap[1,x]|$. A trivial counting bound gives $B(x)\ll x^{1/h}$ for any infinite $B_h$ sequence, and Erdős conjectured an infinite $B_h$ sequence exists with $B(x)\gg x^{1/h-\epsilon}$ for every $\epsilon>0$ — open for all $h$. Before this paper, the best *proven* growth rate for $h\ge3$ was the greedy-algorithm bound $B(x)\gg x^{1/(2h-1)}$, essentially unimproved since the trivial inductive construction (for $h=2$, Ajtai–Komlós–Szemerédi's nibble method and then Ruzsa's probabilistic construction, giving $x^{\sqrt2-1+o(1)}$, had already beaten this — see Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998) and Cilleruelo (2012/2014) — an explicit, deterministic infinite Sidon set matching Ruzsa's exponent $x^{\\sqrt2-1+o(1)}$, via discrete logarithms).

The problem this paper solves: can Ruzsa's exponent-beating technique for $h=2$ be adapted to construct infinite $B_3$ and $B_4$ sequences whose counting function beats the greedy exponent $1/(2h-1)$, matching a single unified formula that recovers Ruzsa's own exponent at $h=2$?

Facts

- Source: Javier Cilleruelo and Rafael Tesoro, "Dense infinite $B_h$ sequences," arXiv:1206.3087 (submitted 14 Jun 2012, v2 11 Jul 2012 — the revision added the $h=4$ case to an original $h=3$-only draft); published in *Publicacions Matemàtiques* 59 (2015), no. 1, 55–73. - Answer: yes, for $h=3,4$ (and $h=2$, reproving Ruzsa). Theorem 1.1: for $h=2,3,4$ there is an infinite $B_h$ sequence $B$ with $$B(x) = x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}.$$ - $h=2$: exponent $\sqrt2-1\approx0.4142$ (exactly reproduces Ruzsa's 1998 record). - $h=3$: exponent $\sqrt5-2\approx0.2361$ — beats the greedy $1/(2\cdot3-1)=1/5=0.2$. - $h=4$: exponent $\sqrt{10}-3\approx0.1623$ — beats the greedy $1/(2\cdot4-1)=1/7\approx0.1429$. - A single formula, but the proof is genuinely case-by-case beyond $h=4$. The paper states explicitly: "except for Lemma 3.3 the proof presented here works for all $h\ge2$. The technical details in Lemma 3.3 become significantly involved as $h$ increases and we are still looking for a proof for the general case." Lemma 3.3 is proved only for $l=2,3,4$ (Propositions 4.5, 4.6, 4.7) via three separate, increasingly intricate calculations — the construction for $h\ge5$ with this same exponent formula is an open gap the authors flag themselves, not (as of this search) resolved by any later paper. - The substrate swap that drives the whole paper: Gaussian primes instead of rational primes. Ruzsa's original $h=2$ construction used $\{\log p:p\text{ prime}\}\subset\mathbb R$, an unbounded additive Sidon set of reals coming from the multiplicative-Sidon-ness of the primes. Cilleruelo–Tesoro instead use the arguments of Gaussian primes $\mathfrak p=a+bi\in\mathbb Z[i]$ ($p=a^2+b^2\equiv1\!\!\pmod4$, $a>b>0$) restricted to the first octant, $\theta(\mathfrak p)\in(0,1/8)$ — a *bounded* real interval instead of an unbounded one. This idea traces to Cilleruelo–Ruzsa, "Real and $p$-adic Sidon sequences," Acta Sci. Math. (Szeged) 70 (1983/2004), and was first written up for $h=2$ by J. Maldonado, arXiv:1103.5732 (2011); Cilleruelo–Tesoro generalize the same substrate swap to $h=3,4$. - Why boundedness matters (a genuine simplification, not just an aesthetic swap). Ruzsa's construction had to separately encode the integer part of $\alpha\log p$ in a reserved block of digits. Because $\theta(\mathfrak p)\in(0,1/8)$ has integer part $0$, this bookkeeping vanishes entirely (paper, Remark 3.1: "Since in our construction the integral part of $\alpha\theta(p)$ is zero we don't need to care about this"). - The still-open targets this feeds: Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf ($500, open) asks whether every infinite $B_3$ set must satisfy $\liminf_N|A\cap[1,N]|/N^{1/3}=0$. This paper's $B_3$ construction (exponent $\sqrt5-2\approx0.236$, well below $1/3$) is the best known dense $B_3$ *construction* — the natural "witness" direction for a "no" answer to #41 — but its exponent is far short of $1/3$, so it neither resolves #41 nor is expected to without a fundamentally stronger idea. Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set ($500, open, $h=2$ analogue) is the parent case this paper's method reproves exactly.

Solution

**The transferable technique — run Ruzsa's "probabilistic digit-encoding + measure-theoretic alteration" machine over a *bounded* number-theoretic log-analogue (Gaussian-prime arguments) instead of an unbounded one (real logarithms of primes), and control carrying in the $h$-fold-sum digit arithmetic with a fixed zero-padding width tuned to $h$, so the same skeleton that gave Ruzsa's $h=2$ record now produces a full family of $B_h$ constructions for a genuinely new object at each $h$.**

1. Find a bounded number-theoretic analogue of "log $p$" with the same multiplicative-Sidon pedigree. For $p\equiv1\pmod4$, write $p=a^2+b^2$ ($a>b>0$) as a Gaussian prime $\mathfrak p=a+bi\in\mathbb Z[i]$, and let $\theta(\mathfrak p)\in(0,1/8)$ be its argument. Because $\mathbb Z[i]$ is a UFD and no product of distinct first-octant Gaussian primes (and conjugates) is real, an arctan/UFD argument (Lemma 2.1) shows: for any $h$ distinct first-octant Gaussian primes $\mathfrak p_1,\dots,\mathfrak p_h,\mathfrak p_1',\dots,\mathfrak p_h'$, $$\Bigl|\sum_{r=1}^h(\theta(\mathfrak p_r)-\theta(\mathfrak p_r'))\Bigr| > \frac{1}{7\,|\mathfrak p_1\cdots\mathfrak p_h\mathfrak p_1'\cdots\mathfrak p_h'|}.$$ This is the exact structural analogue of "primes are multiplicatively Sidon $\Rightarrow\{\log p\}$ is additively Sidon," but landing in the *bounded* interval $(0,1/8)$ rather than $\mathbb R_{>0}$ — the substrate swap that removes Ruzsa's integer-part bookkeeping (step 0 above) essentially for free.

2. Digit-encode a real multiple of the (bounded) map with carry-blocking zero-padding tuned to $h$. For a real parameter $\alpha\in[1,2]$, expand $\alpha\theta(\mathfrak p)=\sum_i\delta_i(p)2^{-i}$ in binary, truncate at the $K^2$-th place for $\mathfrak p$ in the $K$-th size class $P_K$ (Gaussian primes with $|\mathfrak p|^2$ in a doubly-exponential range depending on a parameter $c_h$), group digits into blocks $\Delta_j\mathfrak p$ of $j^2-(j-1)^2$ bits, reverse the block order, and insert a filling block of $2d+1$ zero digits between consecutive blocks, with $d=\lceil\log_2 h\rceil$ — exactly enough slack that summing up to $h$ such integers coordinate-wise, with no carry crossing a block boundary, is provably valid (this is the direct generalization of the $h=2$ "no-carry" trick to general $h$: the padding width scales with $\log h$ because up to $h$ digit-sums, each $\le1$, must stay $<2^{2d+1}$ apart from the next block). This turns the encoding into a genuine additive homomorphism on truncated digit-vectors for any fixed $h$-fold sum.

3. A repeated $h$-fold sum forces an exact digit-level identity, reducing the whole problem to Diophantine approximation in one real variable $\alpha$. If two disjoint $h$-tuples of encoded integers $b_{\mathfrak p_1},\dots,b_{\mathfrak p_h}$ and $b_{\mathfrak p_1'},\dots,b_{\mathfrak p_h'}$ collide (a "bad $2l$-tuple," $l\le h$), the no-carry property (step 2) forces the *truncated* digit sums to match exactly, block by block (Lemma 3.2) — which forces $\sum_r(\widehat{\alpha\theta(\mathfrak p_r)}-\widehat{\alpha\theta(\mathfrak p_r')})=0$ exactly. Combined with Lemma 2.1's lower bound on the *un*truncated version of this same sum, this pins $\alpha$ into an explicit, shrinking nested sequence of intervals (Lemmas 4.1–4.3) — i.e., a bad tuple can only exist for $\alpha$ in a set of small, computable measure, converting "does this tuple collide" from an integer-collision question into a quantitative Diophantine-approximation / interval-counting question in the single real variable $\alpha$.

4. Bound the measure of "bad" $\alpha$ via a visible-lattice-point-in-a-sector count (the genuinely new technical engine, and the place the proof stops being uniform in $h$). The integral $\int_1^2|E_{2l}(\alpha;K)|\,d\alpha$ (expected number of bad $2l$-tuples at scale $K$, averaged over $\alpha$) is bounded by counting Gaussian-integer products $\nu=\mathfrak p_1\mathfrak p_1'\cdots$ that are visible from the origin (coprime coordinates) with bounded norm and near-zero argument, inside a circular sector — a clean, elementary lattice-point lemma (Lemma 4.4: at most $\epsilon R^2+1$ visible points in a sector of angle $\epsilon$, radius $R$, via a "non-overlapping triangles of area $\ge1/2$" packing argument). Reused three separate times for $l=2$ (Proposition 4.5, reproving Ruzsa's own $h=2$ bound in this language), $l=3$ (Proposition 4.6), and $l=4$ (Proposition 4.7), each requiring a new case-specific splitting of the tuple into two coupled sub-products $\nu_1,\nu_2$ and a fresh dyadic-sum bookkeeping argument — this is exactly the step whose difficulty visibly compounds with $l$, and exactly the step the authors say they could not close in general.

5. Tune the one free scale parameter to the critical threshold where the total badness (summed over all scales $K$) provably converges, then delete. Set $c_h=\sqrt{(h-1)^2+1}+(h-1)$ — the largest value making the exponent in the $K$-sum, $2(h-1)/c_h-1-1/c_h$, non-positive. At this critical $c_h$, $\sum_K|\mathrm{Bad}_{\alpha,K}|/|B_{\alpha,K}|$ converges for almost every $\alpha\in[1,2]$ (a measure/Borel–Cantelli-style argument, not a search): pick any one such $\alpha_0$, and delete every element flagged as "bad" (the classical alteration-method move, identical in spirit to Cilleruelo (2012/2014) — an explicit, deterministic infinite Sidon set matching Ruzsa's exponent $x^{\\sqrt2-1+o(1)}$, via discrete logarithms's deletion step and to Ruzsa's own $h=2$ argument). Because the deleted fraction is $o(1)$ at every scale, the surviving set $B=\bigcup_K(B_{\alpha_0,K}\setminus\mathrm{Bad}_{\alpha_0,K})$ is a genuine $B_h$ sequence with unchanged leading exponent, $B(x)=x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$.

Why this is the reusable part. The general recipe — (i) find a *bounded* substrate carrying the same "unique-factorization $\Rightarrow$ additive-Sidon-quality-lower-bound" property as $\{\log p\}$ (here: arguments of Gaussian primes in $\mathbb Z[i]$, chosen specifically because boundedness kills an entire class of bookkeeping that plagued the original real-log construction); (ii) digit-encode a real-parameter multiple of that map with a zero-padding width that scales with $\log h$ so that up to $h$-fold sums are provably carry-free; (iii) convert "did encoding create a spurious $h$-fold collision" into a Diophantine-approximation statement about the single sweep parameter $\alpha$; (iv) bound the *measure* of bad $\alpha$ at each scale via an elementary visible-lattice-point-in-a-sector count, generalized tuple-configuration by tuple-configuration as $h$ grows; (v) tune the one scale parameter to the exact critical exponent where the total badness measure converges, and delete — is directly the model for extending dense $B_h$ constructions to $h\ge5$ (the open technical gap the authors themselves flag) and for any future attack that needs an infinite, alteration-built extremal additive set governed by an $h$-fold (not just 2-fold) collision condition. It is also a clean illustration that the "critical-parameter alteration" trick recurs across this whole problem cluster in *different* guises: Ruzsa/Cilleruelo–Tesoro tune a continuous sweep parameter $\alpha$ over a measure-theoretic space, Cilleruelo's own discrete-log construction (Cilleruelo (2012/2014) — an explicit, deterministic infinite Sidon set matching Ruzsa's exponent $x^{\\sqrt2-1+o(1)}$, via discrete logarithms) instead tunes a discrete growth-rate parameter $c$ via a purely combinatorial divisor-count, and Pliego (Pliego 2024 — sharp density-vs-boundedness trade-off for $B_2[g]$ sequences) tunes a random-inclusion probability via a moment bound — three structurally different "tune-then-delete" engines converging on the same alteration-method shape.

Related

- Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the still-open $500 Erdős problem this paper's $B_3$ construction is the best-known dense witness for (not a resolution): does every infinite $B_3$ set satisfy $\liminf_N|A\cap[1,N]|/N^{1/3}=0$? This paper's exponent $\sqrt5-2\approx0.236$ is well below $1/3$, so it neither proves nor disproves #41, but any future attempt to disprove #41 (build a $B_3$ set of density $\gg N^{1/3}$) would need to beat this exponent using a related or stronger technique. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the $h=2$ parent problem (infinite Sidon set of density $N^{1/2-\epsilon}$?), $500, open; this paper's method exactly reproves Ruzsa's own record exponent $\sqrt2-1$ at $h=2$ as a special case of its unified formula. - Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998) and Ruzsa's infinite Sidon set of density $x^{\\sqrt2-1+o(1)}$ (1998) — current record — Ruzsa's original 1998 non-constructive $h=2$ construction (real logs of primes, probabilistic parameter sweep) that this paper directly generalizes to $h=3,4$ using a bounded Gaussian-argument substrate instead of unbounded real logs. - Cilleruelo (2012/2014) — an explicit, deterministic infinite Sidon set matching Ruzsa's exponent $x^{\\sqrt2-1+o(1)}$, via discrete logarithms — Cilleruelo's *other*, structurally different $h=2$ construction (fully deterministic discrete logarithms mod a sequence of primes, no residual randomness); shares the general "encode via a log-like map, bound bad tuples, delete" skeleton with this paper but is a genuinely different proof engine (deterministic divisor-counting vs. measure-theoretic Diophantine approximation) — useful as a contrasting reference for what a fully derandomized $B_3,B_4$ construction might look like (not yet achieved for $h\ge3$, as far as this search found). - Pliego 2024 — sharp density-vs-boundedness trade-off for $B_2[g]$ sequences — sibling solved problem in the same "tune a critical parameter, bound badness via a sharper-than-naive estimate, delete" template family, applied to $B_2[g]$ (bounded-multiplicity) sequences instead of $B_h$ (bounded-order) sequences. - Sidon sets / B_2 sets / Golomb rulers — parent concept page for the whole Sidon/$B_h$ area. - Finite-field / projective-plane constructions for extremal additive sets — broader family of explicit algebraic/UFD-based constructions this paper's Gaussian-integer substrate belongs to, alongside Cilleruelo's own discrete-log route and Singer's finite-field route (Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets).