A Dense Infinite Sidon Sequence

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. In this post, we are mainly concerned about a breakthrough theorem in the field of infinite Sidon sets.

First consider the following example.

Example : (Greedy Algorithm) If $S\subset [1,n]$ is already a Sidon set, we can find $x$ such that $x$ does not equal $a$, $b$, $c$ or $a+b-c$ for any $a,b,c\in S$ and $S\cup \{x\}\subset \mathbb{N}$ is Sidon. Since there are at most $n$ choices for each of $a$, $b$ and $c$ and $a,b,c\le n$, choosing $x>n^3$ is enough.

It is clear that this sequence satisfies $S(x)\gg x^{1/3}$ where $S(x):=|S\cap [1,x]|$. It was conjectured by Erdős that there is a Sidon sequence $S$ with $S(x)\gg x^{1/2-\epsilon }$ for all $\epsilon >0$ (recall that $f(x)\gg g(x)$ means that there exists a constant $C$ such that $f(x)\ge Cg(x)$ for all large $x$ and $f(x)\ll g(x)$ is defined similarly). He also proved that any arbitrary Sidon sequence will have the close upper bound of

$$S(x)\ll x^{1/2}{(\log x)}^{-1/2}$$

for infinitely many $x$. This exhibits that finite segments of an infinite Sidon set must sometimes be much smaller than it is expected in finite Sidon sets.

The lower bound was first improved by Ajtai, Komlós and Szemerédi who proved the existence of $S$ satisfying

$$S(x)\gg x^{1/3}{(\log x)}^{1/3}$$

and then finally Ruzsa gave a breakthrough by finding another $S$ satisfying

$$S(x)\gg x^{\sqrt{2}-1-o(1)}$$

which has remained the best result in this area since $1998$. It is this proof that I will present in this post.

For those asking why we care, it is known that the number of elements in the biggest (usually called dense in literature) Sidon subset of the interval $[1,x]$ is of the order $\sqrt{x}$ (see here) and what Erdős' conjecture claims is that $\mathbb{N}$ is quite similar. In other words, we can find Sidon subsets of $\mathbb{N}$ with (logarithmic) density arbitrarily close to $\sqrt{x}$ (although $\sqrt{x}$ is not achievable, and this was proven by Erdős).

Theorem : There exists an infinite Sidon sequence $B$ such that

$$B(N)=N^{\gamma +o(1)}$$

where $\gamma =\sqrt{2}-1$.

Idea of the Proof : Notice that the set of primes $\mathcal{P}$ form a multiplicative Sidon set, that is $p_1{p}_2=p_3{p}_4$ for $p_i\in \mathcal{P}$ implies $\{p_1,p_2\}=\{p_3,p_4\}$. So, $\{\ln p{\}}_{p\in \mathcal{P}}$ forms a Sidon set in $\mathbb{R}$.

This means that if we can cut the binary representation of $\ln p$ in a proper way, we still almost surely retain the Sidon property. In fact, all the observations we made so far are true for $\{\alpha \ln p{\}}_{p\in \mathcal{P}}$ for all $\alpha$. Indeed we will start with a bunch of $\alpha$ so that we can later argue probabilistically. 

Proof Setup : The first step is to look at the number $\alpha \ln p$ in binary. Choose $\alpha \in [1,2]$ and write

$$\alpha \ln p=\sum _{i=0}^{k_p}{\epsilon }_{ip}{2}^i+\sum _{i=1}^{\mathrm{\infty }}{\delta }_{ip}{2}^{-i}$$

where $k_p=\lfloor \log (\alpha \ln p)\rfloor$. So, the $\epsilon$-string is the integral part of this number and the $\delta$-string is the part after the decimal point (or is it the binary point?). Here, and in the rest of the proof, $\log$ will represent ${\log }_2$ and $\ln$ will be a placeholder for logarithm to any pre-specified base - the reader can think of it as ${\log }_e$ for convinience.

Now, we set $\beta =\sqrt{2}+1$ and $\gamma =1/\beta$. Then, we define

$$K_p=min\{i>2:2^{(i-1{)}^2}>p^{\beta }\}$$

so that $K_p=2+\lfloor \sqrt{\beta \log p}\rfloor$. A more natural way to present this proof could have been to start with an arbitrary $\beta$ and realize at the end of the proof that this is the value of $\beta$ that optimizes the density.

Now, we need to do the proper cutting. So, we define

$${\lambda }_p=\sum _{i=0}^{k_p}{\epsilon }_{ip}{2}^i+\sum _{i=1}^{K_p^2}{\delta }_{ip}{2}^{-i}$$

by cutting the binary expansion of $\alpha \ln p$ at the $K_p^2$-th place.

Now, we use the square indices to construct

$${\mathrm{\Delta }}_{ip}=\sum _{j=(i-1{)}^2+1}^{i^2}{\delta }_j{2}^{i^2-j}$$

by cutting the bigger block into smaller pieces.

In binary, the numbers look like

$$\begin{array}{rl}{\mathrm{\Delta }}_{1,p}& ={\delta }_1\\ {\mathrm{\Delta }}_{2,p}& ={\delta }_2{\delta }_3{\delta }_4\\ {\mathrm{\Delta }}_{3,p}& ={\delta }_5{\delta }_6{\delta }_7{\delta }_8{\delta }_9\end{array}$$

and so on. From now on, we will often supress $p$ or $\alpha$ from our notation whenever it doesn't interfere with the clarity of the proof.

Finally, we define $b_p$ as

$$\dots \underset{―}{0}\underset{―}{1}\underset{―}{0}{\mathrm{\Delta }}_K\dots {\mathrm{\Delta }}_3\underset{―}{0}\underset{―}{{\epsilon }_2}\underset{―}{0}\underset{―}{0}\underset{―}{0}{\mathrm{\Delta }}_2\underset{―}{0}\underset{―}{{\epsilon }_1}\underset{―}{0}\underset{―}{0}\underset{―}{0}{\mathrm{\Delta }}_1\underset{―}{0}\underset{―}{{\epsilon }_0}\underset{―}{0}\underset{―}{0}\underset{―}{0}$$

which was done in the following way : first write the ${\mathrm{\Delta }}_i$'s in a piece of paper and put five blanks in between each of them, and after ${\mathrm{\Delta }}_1$. Fill up the second blank to the right of ${\mathrm{\Delta }}_i$ with ${\epsilon }_{i-1}$. The $4$th blank always contains a $0$ except the one to the left of ${\mathrm{\Delta }}_K$ - this is done to keep track of the size of $b_p$. The rest of the blanks are all $0$. 

More formally,

$$b_p=\sum _{i=1}^K{\mathrm{\Delta }}_{ip}{2}^{(i-1{)}^2+5i}+\sum _{i=0}^k{\epsilon }_{ip}{2}^{i^2+5i+2}+t_p$$

where $t_p=2^{K^2+5K+4}$.

Further, we put ${\mathrm{\Delta }}_{ip}=0$ for $i>K$ and ${\epsilon }_{ip}=0$ for $i>k$. Our Sidon set will be a subset of the set $\{b_p{\}}_{p\in \mathcal{P}}$.

Plan of the Proof : Recall how we introduced a padding of $0$'s in the definition of $b_p$. This was done to ensure that there are no carry overs when we add $b_{p_1}+b_{p_2}$. This makes sure that

$$\begin{array}{rl}{b}_p+b_s=b_q+b_r⟺& t_p+t_s=t_q+t_r,\\ & {\epsilon }_{ip}+{\epsilon }_{is}={\epsilon }_{iq}+{\epsilon }_{ir},\\ & {\mathrm{\Delta }}_{ip}+{\mathrm{\Delta }}_{is}={\mathrm{\Delta }}_{iq}+{\mathrm{\Delta }}_{ir}\end{array}$$

for all $i$. Now, consider

$$\begin{array}{}\text{(*)}& b_p+b_s=b_q+b_r,b_p>b_q\ge b_r>b_s\end{array}$$

for some $p,q,r,s$.

Define $P_K=\{p:K_p=K\}$. These sets provide a proper partitioning of the primes with respect to their sizes, and hence have the following important property. If $(\ast )$ holds, then there are integers $K\ge L$ such that

$$\begin{array}{}\text{(1)}& {\lambda }_p+{\lambda }_s={\lambda }_q+{\lambda }_r\end{array}$$

and $p,q\in P_K$, $r,s\in P_L$.

The artistic part is now over and what's left of our work is the technical part. This is the part where we try to filter out the largest Sidon subset of $\{b_p{\}}_{p\in \mathcal{P}}$. The techniques are all mainly aimed towards estimating the number of solutions of $(\ast )$ in the set $\{b_p{\}}_{p\in \mathcal{P}}$.

Bounds : Notice that

$$|{\lambda }_p-\alpha \ln p|\le 2^{-K^2}<p^{-\beta }$$

follows from definitions. Also, if $(\ast )$ holds, then

$$|ps-qr|<8qr\cdot 2^{-L^2},qr>2^{L^2-2},(K-1{)}^2>(\beta -1)(L-1{)}^2+\beta (2L-3)$$

where $K$ and $L$ are as in $(1)$.

Now, we define

$$J_{KL}=\left|\{p,q,r,s:p\ne q\in P_K,r\ne s\in P_L,|ps-qr|<8qr\cdot 2^{-L^2}\}\right|$$

and try to estimate it.

Lemma : We have

$$J_{KL}\ll 2^{2\gamma ((K-1{)}^2+(L-1{)}^2)-L^2}$$

where $J_{KL}$ is defined as above.

Proof : The Diophantine equation $ps-qr=a$ has the general solution

$$p=p_0+tr,q=q_0+ts$$

where $p_0$, $q_0$ are the smallest solution.

As $p<2^{\gamma (K-1{)}^2}$, we have $t<\frac{2^{\gamma (K-1{)}^2}}{r}$. So, for fixed $a,r,s$, the number of solutions is $\mathcal{O}\left(\frac{2^{\gamma (K-1{)}^2}}{r}\right)$.

Again, $\left|a\right|\ll r\cdot 2^{\gamma (K-1{)}^2-L^2}$. So, for fixed $r,s$, the number of solutions is $\mathcal{O}\left(2^{2\gamma (K-1{)}^2-L^2}\right)$ and $r,s<2^{\gamma (L-1{)}^2}$.

Lemma : We have

$$\lfloor 2^{K^2}\alpha \ln p\rfloor \equiv \lfloor 2^{K^2}\alpha \ln q\rfloor (\mathrm{mod}{2}^{K^2-L^2})$$

assuming $(\ast )$ holds.

Proof : It is clear that

$$\lfloor 2^{K^2}\alpha \ln p\rfloor \equiv \sum _{i=L^2+1}^{K^2}{\delta }_{ip}{2}^{K^2-i}(\mathrm{mod}{2}^{K^2-L^2})$$

from definition. Also for $L<i\le K$, we have ${\mathrm{\Delta }}_{ip}={\mathrm{\Delta }}_{iq}$ so that ${\delta }_{jp}={\delta }_{jq}$ for $L^2<j\le K^2$. So, RHS remains unchanged if we replace $p$ by $q$.

Lemma : Let $K>L$ and $p\ne q\in P_K$ be given. Let there be at least one pair $r,s\in P_L$ and an $\alpha \in [1,2]$ such that $(\ast )$ holds. Then, we have

$$\mu (\alpha :\lfloor 2^{K^2}\alpha \ln p\rfloor \equiv \lfloor 2^{K^2}\alpha \ln q\rfloor (\mathrm{mod}{2}^{K^2-L^2}))\ll 2^{L^2-K^2}$$

where $\mu$ is the Lebesgue measure.

Proof : Call $A=2^{K^2}\ln \frac{p}{q}$, $M=2^{K^2-L^2}$ and notice that the property we are after is

$$\lfloor A\alpha \rfloor \equiv 0\text{ or }-1(\mathrm{mod}M)$$

and since $\lfloor A\alpha \rfloor$ is evenly distributed modulo $M$, we have

$$\mu (\alpha :\lfloor A\alpha \rfloor \equiv 0\text{ or }-1(\mathrm{mod}M))\ll \frac{1}{M}$$

hence completing the proof.

The proofs of the next two lemmas are straightforward and hence we will refrain from exhibiting them.

Lemma : For $p\ne q\in P_K$ and $r,s\in P_L$, we have

$$\mu (\alpha :b_p+b_s=b_q+b_r)\{\begin{array}{ll}=0& \text{if}|ps-qr|\ge 8qr\cdot 2^{-L^2}\\ \ll 2^{L^2-K^2}& \text{if}|ps-qr|<8qr\cdot 2^{-L^2}\end{array}$$

for $K>L$.

Lemma : If

$$G_{KL}(\alpha ):=|\{p,q,r,s:p\ne q\in P_K,r,s\in P_L,(\ast )\text{ holds }\}|$$

then

$${\int }_1^2{G}_{KL}(\alpha )\text{d}\alpha \ll 2^{2\gamma ((L-1{)}^2+(K-1{)}^2)-K^2}$$

for $K>L$.

Lemma : Define

$$G_K(\alpha )=|\{p,q,r,s:p,q\in P_K,(\ast )\text{ holds }\}|$$

so that

$${\int }_1^2{G}_K(\alpha )\text{d}\alpha \ll 2^{\gamma {(K-1)}^2-2K}$$

for all $K$.

Proof : By definition, we have $G_K(\alpha )=\sum _{L\le K}{G}_{KL}(\alpha )$. And since $G_{KL}(\alpha )\ne 0$ only if $(L-1{)}^2<(K-1{)}^2/(\beta -1)$, we obtain an estimate of $\ll 2^Z$ with

$$Z=(\frac{2}{\beta -1}-1)(K-1{)}^2-2K+1$$

on which we use the fact that $\frac{2}{\beta -1}-1=\frac{1}{\beta }$.

In fact, the value of $\beta$ was chosen in the first place to satisfy $\frac{2}{\beta -1}-1=\frac{1}{\beta }$.

Proof of Main Theorem : With all the setup in hand, the rest of the proof is essentially an exercise in probability theory. Define the event

$$E_K:=[G_K\ge N_K]$$

where $N_K:=2^{\gamma (K-1{)}^2-K}$. This gives

$$\begin{array}{rl}\mathbb{P}(E_K)& =\mathbb{P}(G_K\ge N_K)\\ & \le \frac{\mathbb{E}(G_K)}{N_K}\text{(using Markov Inequality)}\\ & =\frac{1}{N_K}{\int }_1^2{G}_K(\alpha )\text{d}\alpha \\ & \ll 2^{-K}\end{array}$$

and hence

$$\sum _K\mathbb{P}(E_K)<\mathrm{\infty }⟹\mathbb{P}\left(\underset{K}{lim inf}{E}_K^C\right)=1$$

by Borel-Cantelli lemma.

This guarantees the existence of an $\alpha$ such that

$$G_K(\alpha )<2^{\gamma (K-1{)}^2-K}$$

for all (except at most finitely many) $K$. Fix this $\alpha$.

Using Prime Number Theorem, the cardinality of $P_K$ is

$$\left|P_K\right|=\pi \left(2^{\gamma (K-1{)}^2}\right)-\pi \left(2^{\gamma (K-2{)}^2}\right)\sim \frac{2^{\gamma (K-1{)}^2}}{\gamma K^2\ln 2}$$

and hence $G_K(\alpha )<\left|P_K\right|/2$ for $K>K_0$.

Now, for each $p,q,r,s$ satisfying $(\ast )$ with $p\in P_K$, we omit $p$ and define $Q_K$ to be the set of remaining elements. Then we define

$$B=\bigcup _{K>K_0}{Q}_K$$

which, by definition, is a Sidon set.

Now, we have

$$b_p<2^{K^2+5K+5}<2^{{(K+3)}^2}$$

implying that for $K=\lfloor \sqrt{\log x}-3\rfloor$, $max{Q}_K<x$. This gives

$$B(x)\gg (\frac{1}{2}-\epsilon )\pi \left(2^{\gamma {(K-1)}^2}\right)=x^{\gamma +o(1)}$$

hence completing the proof. The reader can check that a similar calculation yields an upper bound. $◻$

Although any improvements on the density is still beyond our reach, some analogues of this idea have been suggested and they have been able to yield similar results in more general settings. They have some excellent potential of their own, but that is a topic for a different post!

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 this paper.