$\gamma$-Golomb rulers (bounded-multiplicity difference sets generalizing Sidon sets)

Statement

Definition (O'Bryant, arXiv:2606.28651, §1, verbatim structure). Let $\gamma\ge1$ be an integer. A set $A$ of nonnegative integers is a $\gamma$-Golomb ruler if for every $d>0$ there are at most $\gamma$ unordered pairs $(a,b)\in A\times A$ with $d=a-b$. Equivalently, the difference-representation function $r_A(d):=\#\{(a,b)\in A\times A: a-b=d\}$ satisfies $r_A(d)\le\gamma$ for every $d>0$.

- $\gamma=1$ is exactly the classical object: no difference repeats — this is the Sidon set / Golomb ruler / Babcock set / $B_2$-sequence studied in Sidon sets / B_2 sets / Golomb rulers (same equivalence: distinct-differences $\Leftrightarrow$ distinct-sums $\Leftrightarrow$ Golomb ruler). - $\gamma>1$ relaxes uniqueness to bounded multiplicity: every difference may recur, but never more than $\gamma$ times. This is the same relaxation the Sidon-set literature calls $B_2[\gamma]$ (bounded-representation Sidon sets), now organized as a one-parameter family indexed by $\gamma$, with the classical Sidon/Golomb-ruler theory as the $\gamma=1$ boundary case.

The two extremal questions this concept answers (O'Bryant's Theorems 1–2, the paper's main new results — "the extension from Sidon sets to $\gamma$-Golomb rulers is new, but easy," per the Introduction, verbatim):

- Theorem 1 (liminf/thickness upper bound, the paper's headline new constant). For every $\gamma$-Golomb ruler $A$, writing $A(n):=|A\cap[0,n)|$, $$\liminf_{n\to\infty}\frac{A(n)}{\sqrt{n/\log n}}\ \le\ \frac{2}{\sqrt{\log 2}}\sqrt\gamma\ \approx\ 2.402\sqrt\gamma.$$ This sharpens the $\gamma=1$ (Sidon) constant from Cilleruelo's $8/7\cdot\sqrt7\approx21.2$ down to $2/\sqrt{\log2}$ — bringing Cilleruelo's own posed "exercise" target of $4$ down further, to $\approx2.402$.

- Theorem 2 (limsup, both directions). Every $\gamma$-Golomb ruler $A$ satisfies the universal upper bound $$\limsup_{n\to\infty}\frac{A(n)}{\sqrt n}\ \le\ \sqrt\gamma,$$ and there exists a $\gamma$-Golomb ruler $G$ (explicit tower construction, §4) attaining $$\limsup_{n\to\infty}\frac{G(n)}{\sqrt n}\ \ge\ \frac{1}{\sqrt2}\sqrt\gamma\ =\ \sqrt{\gamma/2}.$$ For $\gamma=1$ the lower half recovers the classical Erdős ($1/2$) $\to$ Krückeberg ($2^{-1/2}$) constant chain — this is exactly Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? (the limsup companion of Erdős #1191 — how small can an infinite Sidon set's liminf density be?).

Supporting finite-ruler bounds it all rests on (Caicedo–Martos–Trujillo, quoted as Lemma 3/Lemma 4 in arXiv:2606.28651):

- Lemma 3 (finite upper bound / "how big can a bounded-diameter $\gamma$-Golomb ruler be"). If $A$ is a $\gamma$-Golomb ruler with $\max A-\min A<N$, then $|A|\le(\gamma N)^{1/2}+(\gamma N)^{1/4}+1\le 3\sqrt{\gamma N}$ — the direct $\gamma$-generalization of the classical Sidon/Golomb-ruler counting bound $\binom{|A|}2\le N-1$. - Lemma 4 (finite-field lower-bound construction, the $\gamma$-generalization of Singer's construction). For every prime power $q\equiv1\pmod\gamma$, there is an explicit $\gamma$-Golomb ruler $B\subseteq[0,(q^2-1)/\gamma)$ with $|B|=q$ — an exact, deterministic construction (Caicedo–Martos–Trujillo 2015, "$g$-Golomb rulers," Rev. Integr. Temas Mat. 33) matching Lemma 3's upper bound in leading order, playing the same structural role for general $\gamma$ that the Singer/Bose–Chowla finite-field construction (Finite-field / projective-plane constructions for extremal additive sets, Singer finite-field perfect difference set construction) plays for $\gamma=1$.

Facts

- **Historical origin: Erdős, via Halberstam & Roth [HaRo66], proved only *finiteness*** — that $\liminf_n A(n)\sqrt{\log n}/\sqrt n$ is bounded by *some* finite constant for every infinite Sidon set — without pinning down the constant. Cilleruelo (2015 lecture notes, "Conjuntos de Sidon," AGRA II school) was the first to give an *explicit* value, $8\sqrt7/7\approx21.2$, and posed reducing it to $4$ as an exercise. O'Bryant's arXiv:2606.28651 is the paper that (a) actually closes Cilleruelo's exercise, landing at $2/\sqrt{\log2}\approx2.402$ — well below the posed target of $4$ — and (b) simultaneously generalizes the whole framework from Sidon sets ($\gamma=1$) to the bounded-multiplicity $\gamma$-Golomb-ruler family, calling the generalization itself "new, but easy" (the hard part was sharpening the constant, not the $\gamma$-generalization). - **This is the *identical* block-decomposition/energy technique Erdős used in 1955–1966, only re-run with a sharper choice of weights. O'Bryant states explicitly (§3, verbatim): "The general structure of the proof is the same as Erdős's for Sidon sets... We believe that we have fully optimized this argument." The paper's own §3.1 "Nonrigorous thoughts" section speculates (without proof) that further improvement would need a genuinely different mechanism — a reverse-martingale reformulation (the block-truncation step "is (up to normalization) that of taking the conditional expectation of the indicator function of $A$ relative to the $\sigma$-algebra generated by $\{[T+iN,T+(i+1)N):i\ge0\}$") or an entropy-inequality analogue of the energy argument — flagging the block-energy method as believed-exhausted for this specific constant. - The $\gamma$-parameter is a genuine one-parameter deformation, not a relabeling.** Both Theorem 1's and Theorem 2's bounds scale as $\sqrt\gamma$ exactly (not $\gamma$, not $\gamma^{1/4}$) — the $\gamma$-Golomb-ruler density ceiling grows like the *square root* of the multiplicity budget, matching the intuition that allowing $\gamma$-fold difference-collisions is like taking a "union of $\gamma$ interleaved Sidon-type structures" in a density sense (density scales as $\sqrt{\#\text{structures}}$, the same scaling Erdős–Rényi/Kolountzakis/Cilleruelo–Trujillo/Pliego $B_2[g]$ constructions exhibit — cf. Sidon sets / B_2 sets / Golomb rulers Facts, "$N^{g/(2g+1)}\to N^{1/2}$ as $g\to\infty$"). - The lower-bound construction (Theorem 2, §4) is an explicit gluing/tower argument, not probabilistic. Starting from Lemma 4's finite-field $\gamma$-Golomb rulers $B_i$ at a tower of prime powers $q_i\mapsto q_{i+1}=q_i^3$, a gluing lemma (Lemma 7: combining two well-separated $\gamma$-Golomb rulers $\mathcal V,\mathcal W$ by discarding at most $\gamma\binom{|\mathcal V|}2$ elements of $\mathcal W$ to kill cross-collisions) inductively builds an infinite $\gamma$-Golomb ruler $G=\bigcup_i G_i$ attaining $\limsup G(n)/\sqrt n\to\sqrt{\gamma/2}$ — the same "explicit finite pieces glued along a growing tower, discarding negligibly many elements at each stage" pattern used elsewhere in this wiki's Sidon-set-adjacent constructions (cf. Erdős #28 — additive basis forces unbounded representations's Ruzsa-1990-style gluing, per concepts/finite-field-constructions.md). - Ruzsa's $x^{\sqrt2-1+o(1)}$ infinite-Sidon-set construction (1998) is explicitly noted as untouched by this paper: O'Bryant's Introduction states plainly that Ruzsa's construction "remains the record for an infinite set" — Theorems 1–2 are about the $\liminf$/$\limsup$ *oscillation* of the counting function relative to $\sqrt n$ (or $\sqrt{n/\log n}$), a different quantity from the *growth-rate exponent* problem (Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) that Ruzsa's construction addresses. The two problem families (oscillation-constant vs. growth-exponent) use overlapping machinery but are not the same question — see Erdős #1191 — how small can an infinite Sidon set's liminf density be? Facts for the explicit disentangling. - Direct open-problem payload: O'Bryant's Theorem 1 is stated for and directly used to attack Erdős #1191 — how small can an infinite Sidon set's liminf density be? (Erdős's \$1000 liminf-oscillation problem, originally Stöhr 1955) — Theorem 1's bound *is* the current best explicit constant in Erdős's own inequality, but it resolves neither of Erdős's two actual sub-questions (is the liminf forced to $0$? can it be kept bounded away from $0$ against a weaker $(\log x)^c$ weight, $0<c<1/2$?) — both remain open. Theorem 2's lower half is content-identical to Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? (the limsup companion problem), generalized from $\gamma=1$ to all $\gamma$. - AI-tooling provenance is explicit and dated in the source. The paper's "Tool and computational resource disclosure" section states verbatim: "This work was developed in interaction with Anthropic's ClaudeAI, which was helpful in some ways and an incredible time-sink in others... Harmonic's AristotleAI located a dozen typos and small errors (all now removed)" — a directly-dated (June 2026) primary-source data point on AI-assisted work in exactly this problem cluster, though the disclosure is candidly mixed ("time-sink") rather than a clean AI-solved-it narrative.

Technique

WHY the block-decomposition + weighted-Cauchy–Schwarz "energy" argument works (mechanism, Theorem 1's proof, arXiv:2606.28651 §3):

1. Set up an energy functional over blocks. Partition (a long truncation of) $A$ into consecutive blocks $[t+(\ell-1)N,\,t+\ell N)$ of fixed length $N$, for an offset $t$ and $\ell=1,\dots,M$; let $F_\ell^{(t)}=|A\cap\text{block }\ell|$ be the block counts, and define the energy $E:=\sum_\ell F_\ell^2$ (after averaging over $t$ to fix a good offset $T$). 2. Upper-bound the energy using the $\gamma$-Golomb property (pure double counting). Every unordered pair $\{a,b\}\subset A$ with difference $d<N$ is counted in $F_\ell^{(t)}$ for roughly $N-d$ choices of offset $t$; averaging over $t\in[0,N)$ and using $r_A(d)\le\gamma$ for every $d$ gives $\sum_\ell\binom{F_\ell}2\le\gamma(N-1)/2$ — hence, since $F_\ell^2=2\binom{F_\ell}2+F_\ell$ and $\sum_\ell F_\ell=A(T+MN)-A(T)=o(N)$ (by the finite-ruler bound, Lemma 3, applied to the whole truncated range), $E\le\gamma N+o(N)$. This is the only place the $\gamma$-Golomb hypothesis is used — it converts the combinatorial bounded-multiplicity constraint into a clean quadratic (energy) upper bound. 3. Lower-bound the same energy via weighted Cauchy–Schwarz, using weights $w_\ell:=(\ell\,\psi(\ell N))^{-1/2}$ where $\psi(x)=\log(ex)$: $E\ge\big(\sum_\ell w_\ell F_\ell\big)^2/\sum_\ell w_\ell^2$. The denominator $\sum w_\ell^2$ is bounded by an integral-comparison argument ($\le\log2+o(1)$, "Claim 5"), and the numerator is bounded below (via Abel summation / summation-by-parts on $F_\ell=a_\ell-a_{\ell-1}$, "Claim 6") using the *definition* of $\tau_N:=\inf_{n\ge N}A(n)/\sqrt{n/\psi(n)}$ — i.e. the very liminf-type quantity Theorem 1 is trying to bound. 4. Equate the two bounds and solve for $\tau_N$. Combining steps 2–3 gives $\tau_N^2\cdot(\log2)/4\le\gamma+o(1)$, i.e. $\tau_N\le2\sqrt\gamma/\sqrt{\log2}+o(1)$; letting $N\to\infty$ (through a subsequence where $\tau_N$ nearly attains the liminf, since $\tau_N$ is monotonically increasing in $N$) gives exactly Theorem 1.

WHEN this technique applies: any problem of the form "how thin/oscillatory can an infinite set with a *bounded-multiplicity local additive constraint* (bounded-difference-multiplicity, bounded-sum-multiplicity, more generally bounded representation-function values) be forced to be, relative to a target density profile ($\sqrt n$, $\sqrt{n/\log n}$, etc.)" — the constraint only needs to give a *quadratic* (pairwise) upper bound on block energy; the weighted-Cauchy–Schwarz half is generic and reusable independent of the specific constraint.

HOW to reuse this for derivation (recombination steps)

1. Identify the pairwise/quadratic obstruction. Any hypothesis of the shape "for all $d$, $r(d)\le\gamma$" (bounded representation multiplicity of *any* kind — differences here, but the same double-counting works for sums, or other bounded bilinear patterns) plugs directly into step 2 above to produce an energy upper bound $E\lesssim\gamma N$. 2. Choose the weight profile to match your target normalization. The specific weights $w_\ell=(\ell\psi(\ell N))^{-1/2}$ are tuned so that $\beta(x)=\sqrt{xN/\psi(xN)}$ (the target growth profile, $\sqrt{n/\log n}$ here) appears naturally after the Abel-summation step; a different target normalization (e.g. plain $\sqrt n$, as in Theorem 2, whose proof "closely follows Halberstam & Roth [3], modified to allow $\gamma>1$") calls for a different, simpler weight profile — swapping the weight function is the standard knob for retargeting this technique to a different growth-rate question. 3. For the matching lower bound (construction side), use the finite-field-tower-plus-gluing pattern (Lemma 4 + Lemma 7 above): get an exact finite $\gamma$-Golomb ruler from a prime-power finite-field construction at each scale, then glue successive scales together, discarding a controlled ($O(\gamma\cdot|\text{smaller piece}|^2)$) number of elements to kill cross-scale collisions — this is a general-purpose "build an infinite extremal object from a tower of finite near-extremal ones" recipe, reusable whenever a suitable finite building-block construction (here, Lemma 4) and a suitable well-separation/gluing lemma (here, Lemma 7) are available. 4. **When it does *not* directly apply**: the technique bounds *oscillation constants* (liminf/limsup relative to a fixed target profile), not *growth-rate exponents* — for the latter (e.g. beating Ruzsa's $x^{\sqrt2-1+o(1)}$, Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) a structurally different discrete-logarithm/multiplicative-Sidon toolkit is needed (see Sidon sets / B_2 sets / Golomb rulers Technique §3). Also, per the paper's own §3.1, the author believes the *specific* weighted-Cauchy–Schwarz choice made here is close to optimal for this exact constant — pushing the constant further plausibly needs a different inequality (entropy, martingale) rather than a better weight profile within the same Cauchy–Schwarz template.

Related

- Sidon sets / B_2 sets / Golomb rulers — the $\gamma=1$ special case; the central combinatorial object this whole family generalizes (Sidon set = distinct-differences = Golomb ruler = $B_2$-sequence = $\gamma$-Golomb ruler with $\gamma=1$). - Finite-field / projective-plane constructions for extremal additive sets — the umbrella technique family; Lemma 4's prime-power construction ($q\equiv1\pmod\gamma$, ruler of size $q$ in $[0,(q^2-1)/\gamma)$) is a direct $\gamma$-generalization of the Singer/Bose–Chowla recipe documented there. - Singer finite-field perfect difference set construction — the $\gamma=1$, $n=2$ cyclic-orbit special case of the same finite-field construction mechanism underlying Lemma 4. - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — Erdős's \$1000 liminf-oscillation problem (Stöhr 1955 origin) that Theorem 1's constant $2/\sqrt{\log2}\approx2.402$ is the current best explicit bound for; neither of the problem's two sub-questions is resolved by this concept's technique, which the paper's own author flags as "fully optimized." - Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — the limsup companion problem; Theorem 2's two-sided bound ($\sqrt\gamma$ upper, $\sqrt{\gamma/2}$ lower) is the direct $\gamma$-generalization, with $\gamma=1$ recovering the classical Erdős/Krückeberg constants exactly. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the growth-*rate*-exponent sibling problem (density $N^{1/2-\epsilon}$ for all $\epsilon$); explicitly a *different* quantity from what this concept's Theorems 1–2 bound (oscillation constant, not exponent) — Ruzsa's $x^{\sqrt2-1+o(1)}$ construction remains untouched by this technique, per the paper's own Introduction. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite-Sidon-set sharp-asymptotics sibling; shares the same Erdős–Turán/double-counting ancestry but is a genuinely different (finite, not liminf/limsup) extremal question. - Concept referenced but not yet its own page: "dyadic/block-energy method" (the general block-decomposition-plus-weighted-Cauchy–Schwarz template used by Erdős 1955/1966, Halberstam–Roth, and O'Bryant 2026 — flagged here, in problems/1191.md, and in concepts/sidon-sets.md as a natural next concept page, since the mechanism in this page's Technique section is the fullest write-up of it currently in the wiki).