The Thickness of Infinite Sidon Sets

Kevin O’Bryant · 2026

Read The Thickness of Infinite Sidon Sets by Kevin O’Bryant (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28651.txt.

Introduction

Kevin O’Bryant, writing alone, measures how thick an infinite Sidon set can be. A Sidon set of nonnegative integers has the austere property that every positive difference arises from at most one pair of its elements. Allowing up to a fixed number of pairs per difference generalizes this to what he calls a gamma-Golomb ruler, named for rulers whose marks measure every distance once.

O’Bryant proves a two-sided story about density. For any ruler, he bounds the count of elements below n along a subsequence. It cannot outgrow the square root of gamma times the square root of n over log n, up to an explicit constant. In the other direction, he constructs a ruler whose count infinitely often reaches a constant times the square root of gamma times the square root of n. That shows the scale of the upper bound is truly attainable.

Catalog record

CREATORKevin O’Bryant
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.28651

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Thickness of Infinite Sidon Sets Kevin O’Bryant Abstract Let γ ≥ 1 \gamma\geq 1 . A set 𝒜 \mathcal{A} of nonnegative integers is a Sidon set if for each d > 0 d>0 there is at most one pair ( a , b ) ∈ 𝒜 × 𝒜 (a,b)\in\mathcal{A}\times\mathcal{A} with d = a − b d=a-b . If there are at most γ \gamma pairs, then 𝒜 \mathcal{A} is a γ \gamma -Golomb ruler. We prove that if 𝒜 \mathcal{A} is a γ \gamma -Golomb ruler, then lim inf n → ∞ | 𝒜 ∩ [ 0 , n ) | n / log ⁡ n ≤ 2 log ⁡ 2 ​ γ . \liminf_{n\to\infty}\frac{|\mathcal{A}\cap[0,n)|}{\sqrt{n/\log n}}\leq\frac{2}{\sqrt{\log 2}}\sqrt{\gamma}. There is a γ \gamma -Golomb ruler 𝒢 \mathcal{G} with lim sup n → ∞ | 𝒢 ∩ [ 0 , n ) | n ≥ 1 2 ​ γ . \limsup_{n\to\infty}\frac{|\mathcal{G}\cap[0,n)|}{\sqrt{n}}\geq\frac{1}{\sqrt{2}}\sqrt{\gamma}. 1 Introduction Let \gamma\geq 1 . A set \mathcal{A} of nonnegative integers is a \gamma -Golomb ruler if each d>0 has at most \gamma pairs (a,b)\in\mathcal{A}\times\mathcal{A} with d=a-b . With \gamma=1 , these are known as Sidon sets in combinatorics, Golomb rulers in recreational math, Babcock sets in electrical engineering, and B_{2} sequences in number theory. See the author’s comprehensive annotated bibliography [ 4 ] for hundreds of citations. Our main result is giving the constant in the following theorem. Erdős [ 6 ] proved finiteness for Sidon sets, and Cilleruelo [ 2 ] proved 8\sqrt{7}\approx 21.2 , and suggests bringing the constant down to 4 as an exercise. We bring the constant down to 2/\sqrt{\log 2}\approx 2.4 . The extension from Sidon sets to \gamma -Golomb rulers is new, but easy. Theorem 1 . Let \gamma be a positive integer. If \mathcal{A} is a \gamma -Golomb ruler, then \liminf_{n\to\infty}\frac{A(n)}{\sqrt{n/\log(n)}}\leq\frac{2}{\sqrt{\log 2}}\,\sqrt{\gamma}. There is a counterpart to Theorem 1 that also originates with Erdős [ 6 ] , who gave the constant \frac{1}{2} . This was improved by Krückeberg to 2^{-1/2} . We extend this result to \gamma -Golomb rulers. Theorem 2 . Every \gamma -Golomb ruler \mathcal{A} has \limsup_{n\to\infty}\frac{|\mathcal{A}\cap[0,n)|}{\sqrt{n}}\leq\sqrt{\gamma}. There is a \gamma -Golomb ruler \mathcal{G} with \limsup_{n\to\infty}\frac{|\mathcal{G}\cap[0,n)|}{\sqrt{n}}\geq\frac{1}{\sqrt{2}}\,\sqrt{\gamma}. Naturally, one asks if these results are close to best possible. Ruzsa [ 5 ] gives a beautiful construction of a Sidon set with A(n)\sim n^{-1+\sqrt{2}} , and this remains the record for an infinite set. Lemmas 3 and 4 below give upper and lower bounds on the size of \gamma -Golomb rulers in [0,N) . 2 Literature We quote two results from Caicedo & Martos & Trujillo [ 1 ] . Lemma 3 (Caicedo & Martos & Trujillo [ 1 ] ) . Let \gamma\geq 1 be an integer. If \mathcal{A} is a \gamma -Golomb ruler with \max\mathcal{A}-\min\mathcal{A}<N , then |\mathcal{A}|\leq(\gamma N)^{1/2}+(\gamma N)^{1/4}+1\leq 3\sqrt{\gamma N}. The crude “ 3\sqrt{\gamma N} ” bound is wasteful, but enough for some of our uses below. Sometimes, we will use Lemma 3 in the inexplicit form |\mathcal{A}|\leq\sqrt{\gamma N}+o(\sqrt{N}) . Lemma 4 (Caicedo & Martos & Trujillo [ 1 ] ) . Let \gamma\geq 1 be an integer. If q is a prime power with q\equiv 1\pmod{\gamma} , then there exists a \gamma -Golomb ruler \mathcal{B}\subseteq[0,(q^{2}-1)/\gamma) with |\mathcal{B}|=q . 3 The Proof of Theorem 1 The general structure of the proof is the same as Erdős’s for Sidon sets: we break the \gamma -Golomb ruler \mathcal{A} into blocks of length N , and will eventually take N\to\infty . We consider the energy E\coloneqq\sum_{\ell}\left|\mathcal{A}\cap[(\ell-1)N,\ell N)\right|^{2} and get an upper bound from the \gamma -Golomb property and a lower bound from Cauchy’s Inequality. We believe that we have fully optimized this argument. Nevertheless, after the proof, we discuss some alternative approaches and make some guesses about where improvements could originate. Proof. Let N be a positive integer (we will take it to \infty ) and set \displaystyle A(n) \displaystyle\coloneqq|\mathcal{A}\cap[0,n)| \displaystyle\psi(n) \displaystyle\coloneqq\log(en) (1) \displaystyle M \displaystyle\coloneqq\frac{N}{\psi(N)} (2) \displaystyle\tau_{N} \displaystyle\coloneqq\inf_{n\geq N}A(n)\sqrt{\frac{\psi(n)}{n}}. (3) We introduce the “ e ” in \psi so that \psi:[1,\infty)\to[1,\infty) , avoiding some division-by-zero pedantism. As N grows, \tau_{N} increases, and the content of Theorem 1 is that \tau_{N}\leq 2/\sqrt{\log 2}. We consider F_{\ell}^{(t)}\coloneqq\left|\mathcal{A}\cap[\,t+(\ell-1)N,\ t+\ell N)\right|, where 0\leq t<N and 1\leq\ell\leq M . Any particular unordered pair a<b in \binom{\mathcal{A}}{2} with difference d=b-a (where 1\leq d<N ) is usually counted in F_{\ell}^{(t)} for N-d different values of t , but will lie in fewer if b<N , so that \displaystyle\sum_{t=0}^{N-1}\sum_{\ell=1}^{M}\binom{F_{\ell}^{(t)}}{2} \displaystyle\leq\sum_{t=0}^{N-1}\sum_{\ell=1}^{\infty}\binom{F_{\ell}^{(t)}}{2} \displaystyle\leq\sum_{\begin{subarray}{c}\{a,b\}\subseteq\mathcal{A}\\ 1\leq a-b<N\end{subarray}}\bigl(N-(a-b)\bigr) \displaystyle\leq\gamma\sum_{d=1}^{N-1}(N-d) \displaystyle=\gamma\,\tfrac{N(N-1)}{2}. (4) Fix an offset T attaining at most the average, and define F_{\ell}\coloneqq F_{\ell}^{(T)}. The proof now proceeds by finding an upper and lower bound on the energy E\coloneqq\sum_{\ell=1}^{M}F_{\ell}^{2}. From Line ( 4 ) we have \sum_{\ell=1}^{M}\binom{F_{\ell}}{2}\leq\frac{\gamma(N-1)}{2}. (5) But F_{\ell}^{2}=2\binom{F_{\ell}}{2}+F_{\ell} and \sum_{\ell=1}^{M}F_{\ell}=A(T+MN)-A(T), so that the inequality in Line ( 5 ) gives E=2\sum_{\ell=1}^{M}\binom{F_{\ell}}{2}+\sum_{\ell=1}^{M}F_{\ell}\leq\gamma(N-1)+A(T+MN)-A(T). Since \mathcal{A}\cap[T,T+MN) is a \gamma -Golomb ruler, and MN\leq N^{2}/\log eN , Lemma 3 gives A(T+MN)-A(T)\leq 3\sqrt{\gamma MN}=o(N). Hence, we have the upper bound on E : E\leq\gamma N+o(N). (6) The lower bound on E uses Cauchy’s Inequality with the weights w_{\ell}\coloneqq\begin{cases}(\ell\,\psi(\ell N))^{-1/2}&1\leq\ell\leq M;\\ 0&\text{otherwise.}\end{cases} By Cauchy’s inequality, E\coloneqq\sum_{\ell=1}^{M}F_{\ell}^{2}\geq\frac{\bigl(\sum_{\ell=1}^{M}w_{\ell}F_{\ell}\bigr)^{2}}{\sum_{\ell=1}^{M}w_{\ell}^{2}}. (7) We need an upper bound on the denominator {\sum_{\ell=1}^{M}w_{\ell}^{2}} , and a lower bound on the numerator {\bigl(\sum_{\ell=1}^{M}w_{\ell}F_{\ell}\bigr)^{2}} . Claim 5 . \displaystyle{\sum_{\ell=1}^{M}w_{\ell}^{2}}\leq\log 2+o(1) . As x\mapsto\bigl(x\,\psi(xN)\bigr)^{-1} is decreasing, \displaystyle\sum_{\ell=1}^{M}w_{\ell}^{2} \displaystyle=\sum_{\ell=1}^{M}\frac{1}{\ell\,\psi(\ell N)} \displaystyle\leq\frac{1}{\psi(N)}+\int_{1}^{M}\frac{dx}{x\,\psi(xN)} \displaystyle=\frac{1}{\psi(N)}+\log\frac{\psi(MN)}{\psi(N)}. Now, by routine calculus, \log(e\frac{x}{\log(ex)}\cdot x)/\log(ex) increases to 2 while 1/\psi(x) decreases to 0 , so that \sum_{\ell=1}^{M}w_{\ell}^{2}\leq o(1)+\log 2, (8) as claimed in Claim 5 . Claim 6 . \displaystyle\bigg(\sum_{\ell=1}^{M}w_{\ell}F_{\ell}\bigg)^{2}\geq\tau_{N}^{2}\left(\frac{\log 2}{2}\right)^{2}N+o(N). To ease the notation visually, set a_{i}=A(T+iN) , and note that F_{\ell}=a_{\ell}-a_{\ell-1} . Also, set M^{\prime}=\mbox{$\left\lfloor M\right\rfloor$} . Rearranging the summation gives \displaystyle\sum_{\ell=1}^{M^{\prime}}w_{\ell}F_{\ell} \displaystyle=\sum_{\ell=1}^{M^{\prime}}w_{\ell}(a_{\ell}-a_{\ell-1}) \displaystyle=\sum_{\ell=1}^{M^{\prime}-1}a_{\ell}\,(w_{\ell}-w_{\ell+1})+w_{M^{\prime}}a_{M^{\prime}}-w_{1}a_{0} \displaystyle\geq\sum_{\ell=1}^{M^{\prime}-1}a_{\ell}\,(w_{\ell}-w_{\ell+1})-w_{1}a_{0}. Now, using Lemma 3 we have w_{1}a_{0}=\frac{A(T)}{\sqrt{\log(eN)}}\leq\frac{3\sqrt{\gamma T}}{\sqrt{\log(eN)}}=o(\sqrt{N}) For 1\leq\ell\leq M^{\prime}-1 we have T+\ell N\geq\ell N\geq N , so the definition of \tau_{N} on Line ( 3 ) yields a_{\ell}\geq\tau_{N}\sqrt{\ell N/\psi(\ell N)} . Writing \beta_{\ell}\coloneqq\sqrt{\ell N/\psi(\ell N)} and using w_{\ell}-w_{\ell+1}\geq 0 , \sum_{\ell=1}^{M^{\prime}}w_{\ell}F_{\ell}\geq\tau_{N}\sum_{\ell=1}^{M^{\prime}-1}\beta_{\ell}(w_{\ell}-w_{\ell+1})-o(\sqrt{N}). By rearranging the summation again, with \beta_{0}\coloneqq 0 , \sum_{\ell=1}^{M^{\prime}-1}\beta_{\ell}(w_{\ell}-w_{\ell+1})=\sum_{\ell=1}^{M^{\prime}-1}w_{\ell}(\beta_{\ell}-\beta_{\ell-1})-w_{{M^{\prime}}}\beta_{M^{\prime}-1}. Since the \beta sequence is positive and strictly increasing and the w sequence is positive, we have 0<w_{M^{\prime}}\beta_{M^{\prime}-1}\leq w_{M^{\prime}}\beta_{M^{\prime}}=\frac{\sqrt{M^{\prime}}}{\psi(M^{\prime}N)}=o(\sqrt{N}). At this point, we have \sum_{\ell=1}^{M}w_{\ell}F_{\ell}\geq o(\sqrt{N})+\tau_{N}\sum_{\ell=1}^{M^{\prime}}w_{\ell}(\beta_{\ell}-\beta_{\ell-1}), where w_{\ell} and \beta_{\ell} are explicit sequences with easily handled properties. Set w(x)=(x\log(exN))^{-1/2} and \beta(x)=(xN/\log(exN))^{1/2} , and we find that \displaystyle\sum_{\ell=1}^{M^{\prime}}w_{\ell}(\beta_{\ell}-\beta_{\ell-1}) \displaystyle\geq\int_{1}^{M^{\prime}-1}w(x)\beta^{\prime}(x)\,dx \displaystyle=\frac{\sqrt{N}}{2}\left(\log\left(\frac{\psi((M^{\prime}-1)N)}{\psi(N)}\right)-\frac{\log(M^{\prime}-1)}{\psi(N)\psi((M^{\prime}-1)N)}\right) \displaystyle=\frac{\sqrt{N}}{2}\left(\log(2+o(1))-o(1)\right) \displaystyle=\frac{\log 2}{2}\sqrt{N}+o(\sqrt{N}). Thus, \displaystyle\left(\sum_{\ell=1}^{M}w_{\ell}F_{\ell}\right)^{2} \displaystyle\geq\left(o(\sqrt{N})+\tau_{N}\left(\frac{\log 2}{2}\sqrt{N}+o(\sqrt{N})\right)\right)^{2} \displaystyle=\tau_{N}^{2}\frac{\log^{2}2}{4}N+o(N). Thus, Claim 6 is verified. Using Claim 5 and Claim 6 in Inequality ( 7 ), we get a lower bound on the energy: E\geq\frac{\tau_{N}^{2}\bigl(\tfrac{\log 2}{2}\bigr)^{2}N\,(1+o(1))}{(\log 2)(1+o(1))}=\tau_{N}^{2}\,\frac{\log 2}{4}\,N+o(N). (9) Compare the upper bound on Line ( 6 ), with N\to\infty , and we have \tau_{N}^{2}\frac{\log 2}{4}\leq\gamma, exactly the inequality stated in Theorem 1 . ∎ 3.1 Nonrigorous thoughts about the proof The author has given each of the suggestions below serious thought and effort and has received no benefit from them, but is not convinced that no benefit is possible. One only needs to take N through a subsequence to \infty , and this freedom plays no role in the proof. Perhaps some N allow for an improvement to Inequality ( 5 ); perhaps it is possible to also average over some values of N . The upper bound in Inequality ( 5 ) is unchanged if one sums \ell to \infty . That is, M

Read the complete text