On the Size of Finite Sidon Sets

A Sidon set [1932.Sidon] is a set ${\cal A}$ of integers with no solutions to $a_{1}+a_{2}=a_{3}+a_{4},a_{i}\in{\cal A}$, aside from the trivial $\{a_{1},a_{2}\}=\{a_{3},a_{4}\}$. Equivalently, ${\cal A}$ is a Sidon set if the coefficients of $(\sum_{a\in{\cal A}}z^{a})^{2}$ are bounded by 2. It is also equivalent, and more useful in this particular work, that ${\cal A}$ is a Sidon set if there are no solutions to $a_{1}-a_{2}=a_{3}-a_{4}$ with $a_{1}\neq a_{2}$ and $a_{1}\neq a_{3}$. We refer our readers to [mybib] for a survey of Sidon sets and an extensive bibliography. Sidon sets are also known as $B_{2}$ sets, Golomb rulers, and 1-thin sets.

Throughout this work, ${\cal A}=\{a_{1}<a_{2}<\dots<a_{k}\}$ is a finite Sidon set of integers. We seek lower bounds on the diameter $\operatorname{diam}({\cal A}):=a_{k}-a_{1}$. For a given $k$, the minimum possible value of $\operatorname{diam}({\cal A})$ is denoted $s_{k}$. We let $R_{2}(n)$ be the maximum value of $k$ with $s_{k}\leq n-1$, i.e., the maximum possible size of a Sidon set contained in $\{1,2,\dots,n\}$.

In 1938, Singer [1938.Singer] constructed a Sidon set with $q+1$ elements and diameter $q^{2}+q+1$, where $q$ is any prime power, whence $s_{k}\leq k^{2}$ for infinitely many $k$. Alternatively, $R_{2}(n)>\sqrt{n}$ for infinitely many $n$. Using results on the distribution of primes (assuming RH), this construction gives $s_{k}\leq k^{2}+k^{3/2+\epsilon},R_{2}(n)\leq\sqrt{n}+n^{1/4+\epsilon}$ for any $\epsilon>0$ and sufficiently large $k,n$. Alternative constructions that have the same asymptotic implications for $s_{k},R_{2}(n)$ have been given by Bose [1942.Bose] and Ruzsa [Ruzsa]. Recently, Eberhard and Manners [Eberhard] have given a unified treatment that has these three constructions—and no others that are asymptotically as good—as special cases.

In 1941, Erdős-Turán [ET] use a “windowing” argument to derive the inequality (valid for any positive integers $n,T$)

and from this inequality find that $R_{2}(n)=n^{1/2}+O(n^{1/4})$. In subsequent years, analysis of this inequality was improved and finally it was noted [Cilleruelo] that $R_{2}(n)=n^{1/2}+n^{1/4}+\frac{1}{2}$ follows from (1). In 1969, Lindström gave another proof, with a different inequality, which also gives this bound on $R_{2}(n)$. In 2 below, we give an even-more-elementary form of the Erdős-Turán argument and a “book” analysis of 1 to give the sharpest expicit bound on $s_{k}$ that explicitly appears in the literature.

In light of the results cited above, the main term in $\operatorname{diam}({\cal A})$ is $k^{2}$, and the secondary term is between $k^{3/2+\epsilon}$ and $-2k^{3/2}$. Recently, Balogh, Füredi, and Roy [BFR] (hereafter referred to as BFR) improved the bound on the secondary term from $-2k^{3/2}$ to $-1.996k^{3/2}$. This was the first real improvement on the bound on $\operatorname{diam}({\cal A})$ or $R_{2}(n)$ since 1941. The number ($1.996$) appearing in their work is not fully optimized, and the important aspect of their work is that the number can be improved to below $2$ by combining the Erdős-Turán and Lindström proofs in a nontrivial manner. In this work we further improve the secondary term. The numerical improvement (also not fully optimized) is not the important aspect of this work, but that it is possible to improve the number below $2$ by a minor refinement the Erdős-Turán argument and not using the Lindström argument at all. Our method is logically simpler than the BFR method, but computationally more involved.

The “sufficiently large” phrase is not fundamentally needed. We expect further numerical improvements will appear in the next few years and it is premature to overly optimize at this stage.

We define $b_{k}$ by $s_{k}=k^{2}-b_{k}k^{3/2}$, and $b_{\infty}=\limsup_{k\to\infty}b_{k}$. The Erdős-Turán work proves that $b_{k}<2$, and the Balogh-Füredi-Roy work proves that $b_{\infty}\leq 1.996$. Explicit values of $b_{k}$ (see Figure 1) are known for $1\leq k\leq 27$ thanks to the Distributed.net “Optimal Golomb Ruler” project [Distnet].

Shearer [Shearer] (perhaps around 1986) constructed the Sidon set examples of Singer and Bose for prime powers up to around 150, and thereby gave a reasonably sharp upper bound on $s_{k}$ for $k\leq 150$. More recently, Dogon-Rokicki [DR] have taken this computation to its logical extreme. They computed the lower bound on $b_{k}$ that arises from looking at all subsets of modular dilations and translations of the sets described by Singer, Bose, and Ruzsa for all prime powers up to 40 200. This reproduces the known optimal sets for all $k\geq 17$ (and most $k$ below 17, too). Their amazing data, which includes specific candidates for $k$-element Sidon sets with minimal diameter for $k<40\,000$, has been instrumental to this work. Their bound for $k<40\,000$ is shown in Figure 2.

We first give a simplified account of the inequality that Erdős-Turán derived and used to prove $R(n)<n^{1/2}+O(n^{1/4})$, with a sharper derivation of the resulting bound. In fact, the bound given here is sharper than any explicit bound explicitly given in the literature of which this author is aware.

We can convert this to a bound on $k=R_{2}(n)$ easily. The expression $k^{2}-2k^{3/2}+k+\sqrt{k}-1$ is a polynomial in $\sqrt{k}$, and one easily sees that its derivative (with respect to $\sqrt{k}$) is positive for $k\geq 0$. Thus, the inequality $n-1\geq k^{2}-2k^{3/2}+k+\sqrt{k}-1$ implies an upper bound on $k$. To prove that $R_{2}(n)<n^{1/2}+n^{1/4}+\frac{1}{2}$, for example, one only needs to derive a contradiction from

While tedious, this purported inequality simplifies algebraically and can be proved impossible by hand.

This proof contains two innovations and a useful consequence. The first innovation is on (3), where we used algebra instead of Cauchy’s Inequality. The algebra of course constitutes a proof of Cauchy’s inequality, but the crux of this article rests on this nontrivial change. The second innovation is the discovery that this bound on $s_{k}$ produces a pleasantly useful factorization, allowing us to also replace asymptotic analysis entirely with simple algebra.

The consequence is made possible by the first innovation. We can use the equalities in (3) and (4) instead of the inequalities, and we arrive at the following theorem, which drives the rest of this work.

We find it philosophically interesting that Theorem 4 gives an equality. Given $|{\cal A}|$, any lower bound on $\operatorname{diam}({\cal A})$ is equivalent to a lower bound on $2S({\cal A},T)+V({\cal A},T)$, and vice versa. Know any three of $|{\cal A}|,\operatorname{diam}({\cal A}),V({\cal A},T),S({\cal A},T)$, and the fourth is uniquely determined.

For $i\leq T$, one has $A_{i}\leq R_{2}(i)$, and this gives a “trivial” lower bound on $V({\cal A},T)$. This allows Theorem 4 to improve the inequality $R_{2}(n)<n^{1/2}+n^{1/4}+\frac{1}{2}$ explicitly by $O(1)$. We mention this only because the number $1/2$ has been called the limit of what can be accomplished with the Erdős-Turán style argument.

In [BFR], a small variance (which arose by way of an inequality from coding theory, and a rephrasing of the Erdős-Turán argument in terms of degree sequences of hypergraphs) was used to imply a lumpiness in the difference set. This lumpiness was then used to supercharge a proof of Lindström’s, yielding

It is, as the proven value was rounded up to $0.998$, equivalent to

This work was the first real improvement in the bounds, upper or lower, of $R_{2}(n)$ since 1941. It was the direct inspiration for the current work.

We play the same gambit, but exploit the phenomenon in a different way. Instead of using the Lindström proof, we re-use Theorem 4 on a subset of ${\cal A}$. That is, either ${\cal A}$ has a large variance (and so a large diameter), or a large subset ${\cal M}\subseteq{\cal A}$ has a difference set that does not include many small values, and so the small diffs is large, forcing ${\cal M}$ to have a large diameter.