Four Proofs of a Theorem

A set of positive integers $A\subset \mathbb N$ is called a Sidon Set or a Sidon Sequence if the equation $a+b=c+d$ does not have any non-trivial solutions in $A$. They were named after Hungarian mathematician Simon Sidon who was inspired by certain problems in Fourier series to ask Erdős about the possible growth of such sequences.

Since then, there has been an extensive amount of work on this topic exploring a plethora of different questions about finite and infinite Sidon sets, and various generalizations of them. The classic result regarding bounds on sizes of Sidon sets was given by Erdős and Turan who also provided a first proof of their theorem. However, here we will discuss four other proofs which I find are easier than the original one. They all yield the same bound, with the exception of Ruzsa's proof which when refined can change the final constant to $1/2$ instead of $1$.

Theorem (Erdős, Turan) : Let $A\subset [n]$ be Sidon Set. Then

$$\left\lvert A\right\rvert < n^{1/2}+n^{1/4}+1$$

where $[n] := \{1,2,\dots , n\}$.

Proof 1 (Lindström) : Let $A=\{a_1<a_2\dots <a_k\}\subset [n]$, $a_j-a_i$ are all distinct. Indeed this property of all the differences (except $0$) being distinct is a defining feature of Sidon sets and is often one of the most important ingredients in proofs of quite strong results.

Define

$$S_1 := \sum_{1\le j\le k-1} (a_{j+1}-a_j) = a_k-a_1$$

so that

$$\frac{(k-1)\cdot k}{2}\le S_1\le n$$

as $S_1$ is the sum of $(k-1)$ distinct integers, and is therefore bigger than the sum of the first $(k-1)$ integers. This yields the bound $k\lesssim \sqrt{2n}$ and was already observed by Erdős. But to refine this further, we need to test the limits of this idea.

Define

$$S_2 := \sum_{1\le j\le k-1} (a_{j+2}-a_j) = a_k+a_{k-1}-a_2-a_1\le 2n$$

so that

$$\frac{(2k-3)\cdot (2k-2)}{2}\le S_1+S_2\le 3n$$

which again follows from the fact that the differences considered in $S_1$ are all different from those considered in $S_2$ and hence $S_1+S_2$ is the sum of $(2k-2)$ distinct integers. This by itself improves the bound to $k\lesssim \sqrt{1.5 \; n}$. Of course we do not need to stop here and can indeed continue to the $\ell$-th iteration. After iterating this $\ell$ times, we have

$$\frac{D\cdot (D+1)}{2}\le S_1+\dots +S_\ell \le (1+2+\dots +\ell)n$$

where $D := (k-1)+\dots +(k-\ell)=k\ell -\frac{\ell\cdot (\ell+1)}{2}$.

Rearranging, we get

$$k-\frac{\ell +1}{2}\le \sqrt{\frac{n\cdot (\ell+1)}{\ell}}$$ 

which gives

$$k\le \sqrt n + \frac{\sqrt n}{2\ell} + \frac{\ell}{2} + \frac 12$$

using the inequality $\sqrt{1+x}\le 1+x/2$.

It is easy to check that $\ell =\left\lfloor n^{1/4}\right\rfloor$ is the optimal choice, hence completing the proof. $\square$

Proof 2 (Ruzsa) : This proof uses a lemma which is fairly well known and appears in different texts and in a variety of different contexts. It is usually attributed to Johnson although it has been rediscovered several times.

Lemma : Let $\mathcal A$ be a family of $k$-sets $A_1,\dots ,A_m$ so that $A_i\cap A_j$ has cardinality atmost $t$ for any $i,j$. Then,

$$v \le \frac{k^2m}{tm+k-t}$$

where $v:= \left\lvert \cup A_i \right\rvert$.

Proof of Lemma : For an element $x\in \cup A_i$, let $d_x= \left\lvert \{i : x\in A_i\}\right\rvert$ so that

\begin{align*} tm(m-1)+mk&\ge \sum_{i}\left(\sum_{j} \left\lvert A_i\cap A_j\right\rvert\right)\\ &=\sum_{x} d_x^2\ge \frac{\left(\sum d_x\right)^2}{v}=\frac{k^2m^2}{v} \end{align*}

hence completing the proof. $\square$

Now let $A\subset [n]$ be a Sidon set and let $k := \left\lvert A\right\rvert$. Take a positive integer $m$ and construct

$$\mathcal A := \{A_i := A+(i-1) : i\in [m]\}$$

where $A+(i-1):=\{a+i-1 : a\in A\}$. Notice that $\cup A_i \subseteq [n+m-1]$.

The key observation is that $\left\lvert A_i\cap A_j\right\rvert\le 1$ for $i\neq j$ as if $x,y\in A_i\cap A_j$ for some $i<j$, then we have $a,b,c,d\in A$ with $a+i=x=b+j$ and $c+i=y=d+j$ implying $a+d=(x-i)+(y-j)=(x-j)+(y-i)=b+c$, and hence $x=y$.

Applying Lemma with $t=1$ and $v\le n+m-1$, we get

$$(n+m-1)(m+k-1)\ge k^2 m$$

hence completing the proof. $\square$

Proof 3 (Graham) : This is the shortest proof in the list. In fact, this is probably one of those proofs that are so short and immediate that they feel like magic. The proof is essentially a direct application of a well known lemma.

Recall the Weyl - van der Corput Lemma. This states that if $\xi(n)$ is a real valued function supported on the interval $[1, N]$, then

$$\left\lvert \sum_{n} \xi(n)\right\rvert ^2 \le \frac{N+H-1}{H} \sum_{\left\lvert h\right\rvert <H} \left(1-\frac{\left\lvert h\right\rvert}{H}\right)\sum_{n} \xi(n)\xi(n+h)$$

for any positive integer $H$.

Now, let $A$ be a Sidon set and $\xi(n)$ be the characteristic function of $A$, i.e., $\xi(n)=1$ if $n\in A$ and $\xi(n)=0$ otherwise. We have

$$\left\lvert A\right\rvert^2 \le \frac{N+H-1}{H} \left(\left\lvert A\right\rvert +H-1\right)$$

since $\sum_{n} \xi(n)\xi(n+h)=\left\lvert A\right\rvert$ if $h=0$ and $\sum_{n} \xi(n)\xi(n+h)\le 1$ otherwise. This is due to the fact that for a fixed constant $h$, there can be atmost one $n$ for which both $n$ and $n+h$ are in $A$ (since all differences in $A$ are distinct).

Using $H=\left\lfloor N^{3/4}\right\rfloor+1$ completes the proof. $\square$

Proof 4 (Cilleruelo) : This proof will require the introduction of some new definitions, including set additions. For $A,B\subset \mathbb N$ we define $A+B:=\{a+b : a\in A, b\in B\}$ to be the collection of all sums of $A$ and $B$. The set $A-B$ is defined analogously.

Now, for $A,B \subset \mathbb N$, let us define

$$r_{A+B} (z) := \left\lvert\{z=a+b : a\in A, b\in B\}\right\rvert$$

to be the number of representations of an integer $z$ as sum of an element from $A$ and another from $B$. We also define

$$E := \sum_{x\in A+B} r_{A+B}^2 (x)$$

and call it the additive energy of $A+B$.

We immediately have $r_{A-A}(0) = \left\lvert A\right\rvert$. It is straightforward to check that

\begin{align*} &\sum_{x\in A+B} r_{A+B}^2 (x) = \sum_{x\in A+B} r_{A-A}(x) r_{B-B}(x)\\ &\sum_{x\in A+B} r_{A+B} (x) = \left\lvert A\right\rvert \left\lvert B\right\rvert \le \sqrt{\left\lvert A+B\right\rvert \sum_{x\in A+B} r_{A+B}^2} = \sqrt{\left\lvert A+B\right\rvert \left(\left\lvert A\right\rvert \left\lvert B\right\rvert + \sum_{x\neq 0} r_{A-A}(x) r_{B-B}(x)\right)} \end{align*}

for any $A,B\subset \mathbb N$.

Now, let $A\subset [N]$ be a Sidon set and $B\subset [\ell]$ so that $A+B\subset [N+\ell]$. So, using the second property above, we have

$$\left\lvert A\right\rvert ^2 (\ell+1)^2 \le (N+\ell)\left(\left\lvert A\right\rvert (\ell +1) + \sum_{x\neq 0} r_{B-B}(x)\right)$$

as $r_{A-A}(x)\le 1$ for all $x$ since $A$ is Sidon (and hence all differences are distinct).

Also,

$$\sum_{x\neq 0} r_{B-B}(x) = \left\lvert \{b_1-b_2 : b_1\neq b_2 ; b_1,b_2\in B\}\right\rvert = \ell (\ell +1)$$

so that

$$\left\lvert A\right\rvert ^2 (\ell+1) \le (N+\ell) \left(\left\lvert A\right\rvert +\ell\right)$$

and hence putting $\ell = \left\lfloor \sqrt{n\left(\left\lvert A\right\rvert -1\right)}\right\rfloor$ completes the proof. $\square$

A keen reader might try to make a case for Proof 4 being essentially the same as Proof 2, only written in a different language. While this may be true to some extent, it should be noted that Cilleruelo's goal (in this paper) was to consider Sidon sets in $\mathbb N^d$ and to prove an analogous result for this case using the method of additive energy. So, this proof is almost a byproduct of his actual work.

It is also worth mentioning that the linked document to Graham's proof is an excellent article which tries to show how the Weyl - van der Corput Lemma alone can prove some really strong results in the field. It is quite surprising how one inequality by itself can describe so many results!

The theorem we described remained the best result until very recently when an improvement was provided by Balogh, Füredi and Roy proving

\begin{equation} \left\lvert A\right\rvert < n^{1/2} + (1-\gamma) n^{1/4} \end{equation}

for some $\gamma\ge 0.002$. In the same spirit, O'Bryant improved the constant from $0.998$ to $0.99703$, and then again to $0.98183$ with Carter and Hunter.

It should however be noted that we are still quite far away from proving what we expect to be true. Addressing the original question of Sidon, Erdős conjectured (and offered $500 for a proof or disproof) that 

$$\left\lvert A\right\rvert < n^{1/2} + o(n^\varepsilon)$$

for all $\varepsilon >0$. This is considered to be a pretty hard problem and it will probably require some time before we can answer it. Maybe one of the readers will be able to help someday!

Acknowledgement : I want to express my heartfelt thanks to my supervisor, Prof. Ramachandran Balasubramanian, who introduced me to the beautiful topic of Sidon sets. His straightforward approach to understanding mathematics has greatly influenced my own mathematical intuition and helped me greatly in understanding these proofs.