Another Beautiful Pigeon-Hole Argument

I first encountered this question in an assignment in our Graph Theory and Combinatorics course. Later, I also saw this in an MSE post and answered immediately. I was extremely happy to be able to solve this problem and now seems to be a good time to put it on this blog.

Problem Statement -

Let $S=\{1,2,\dots ,280\}$. Find the smallest natural number $n$ such that every $n$-element subset of $S$ contains $5$ pairwise relatively prime numbers.

Solution -

Before we begin with the real question, we note that $\lfloor \sqrt{280}\rfloor =16$. This means that all composite numbers below $280$ must have one prime factor in the set $\{2,3,5,7,11,13\}$. We will use this fact in our answer.

First, we will consider the subset $A$ of $S$ that only contains multiples of $2,3,5$ and $7$. We can use Principle of Inclusion and Exclusion to find the cardinality of $A$ as

$$\begin{array}{rl}|A|=& \lfloor \frac{280}{2}\rfloor +\lfloor \frac{280}{7}\rfloor +\lfloor \frac{280}{3}\rfloor +\lfloor \frac{280}{5}\rfloor \\ & -\lfloor \frac{280}{14}\rfloor -\lfloor \frac{280}{6}\rfloor -\lfloor \frac{280}{10}\rfloor -\lfloor \frac{280}{15}\rfloor -\lfloor \frac{280}{21}\rfloor -\lfloor \frac{280}{35}\rfloor \\ & +\lfloor \frac{280}{70}\rfloor +\lfloor \frac{280}{105}\rfloor +\lfloor \frac{280}{42}\rfloor +\lfloor \frac{280}{30}\rfloor \\ & -\lfloor \frac{280}{210}\rfloor \end{array}$$

which gives $|A|=216$.

Now, note that, $A$ only has multiples of four prime numbers. So, using Pigeon Hole Principle, we can say that any five elements of $A$ must have at least two multiples of a particular prime, which proves that any $5$ element subset of $A$ is NOT pairwise relatively prime.

This proves that if we want to have an $n$-element subset of $S$ such that any five of them will be relatively prime, then we must have $n>216$.

Now, notice that the cardinality of $A$ is $216$ and $A$ contains exactly $4$ prime numbers (namely, $2,3,5$ and $7$). So, the other $212$ numbers in $A$ (and hence in $S$) are composite.

Let us try to find the other composite numbers in $S$. These must be of the form $11m$ or $13n$ for some $m,n\in \mathbb{N}$ such that $m,n>10$ (since all multiples till $10$ have already been counted). It is easy to check that the only such composite numbers are  $121,143,169,187,209,221,247,253$. That gives precisely $8$ more composite numbers in $S$. So, $S$ has $220$ composite numbers and $59$ primes (with a $1$ which neither).

Now, consider a subset $X$ of $S$ such that $|X|=217$. We claim that there are five elements in $X$ such that any two of them are pairwise relatively prime. To prove that, let us assume on the contrary that our claim is false. So, any five element subset of $X$ must have two relatively non-prime elements. This forces the number of prime numbers in $X$ to be less than or equal to $4$ since if there are more than four prime numbers, then the set of these primes has all pairwise relatively prime numbers. So, there are at most four primes in $X$ which means that there are at least $213$ composite numbers in $X$. This means that the number of composite numbers outside $X$ (i.e., in $S\mathrm{\setminus }X$) is at most $7$.

Now, consider the following eight sets

$$\begin{array}{rl}& \{2^2,3^2,5^2,7^2,{13}^2\}\\ & \{2\times 31,3\times 29,5\times 23,7\times 19,11\times 17\}\\ & \{2\times 47,3\times 43,5\times 41,7\times 37,13\times 19\}\\ & \{2\times 41,3\times 37,5\times 31,7\times 29,11\times 23\}\\ & \{2\times 23,3\times 19,5\times 17,7\times 13,{11}^2\}\\ & \{2\times 43,3\times 41,5\times 37,7\times 31,13\times 17\}\\ & \{2\times 37,3\times 31,5\times 29,7\times 23,11\times 19\}\\ & \{2\times 29,3\times 23,5\times 19,7\times 17,11\times 13\}\end{array}$$

and note that the $40$ elements in these $8$ sets are all distinct because of the Unique Factorization Theorem. Also, since there are eight sets, and at most seven composite numbers can be outside $X$, by the Pigeon Hole Principle, at least one of these sets must be in $X$. Also, clearly, in all of the above sets, the elements are mutually co-prime.

This completes the proof. $◻$

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|A\right|<n^{1/2}+n^{1/4}+1$$

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

Proof 1 (Lindström) : Let $A=\{a_1<a_2\cdots <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.5n}$. 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+\cdots +S_{\ell }\le (1+2+\cdots +\ell )n$$

where $D:=(k-1)+\cdots +(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{1}{2}$$

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

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

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^{2}m}{tm+k-t}$$

where $v:=|\cup A_i|$.

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

$$\begin{array}{rl}tm(m-1)+mk& \ge \sum _i\left(\sum _j|A_i\cap A_j|\right)\\ & =\sum _x{d}_x^2\ge \frac{{(\sum d_x)}^2}{v}=\frac{k^2{m}^2}{v}\end{array}$$

hence completing the proof. $◻$

Now let $A\subset [n]$ be a Sidon set and let $k:=\left|A\right|$. 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 $|A_i\cap A_j|\le 1$ for $i\ne 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. $◻$

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

$${|\sum _n\xi (n)|}^2\le \frac{N+H-1}{H}\sum _{\left|h\right|<H}(1-\frac{\left|h\right|}{H})\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|A\right|}^2\le \frac{N+H-1}{H}(\left|A\right|+H-1)$$

since $\sum _n\xi (n)\xi (n+h)=\left|A\right|$ 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=\lfloor N^{3/4}\rfloor +1$ completes the proof. $◻$

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):=|\{z=a+b:a\in A,b\in B\}|$$

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|A\right|$. It is straightforward to check that

$$\begin{array}{rl}& \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|A\right|\left|B\right|\le \sqrt{|A+B|\sum _{x\in A+B}{r}_{A+B}^2}=\sqrt{|A+B|(\left|A\right|\left|B\right|+\sum _{x\ne 0}{r}_{A-A}(x)r_{B-B}(x))}\end{array}$$

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|A\right|}^2(\ell +1{)}^2\le (N+\ell )(\left|A\right|(\ell +1)+\sum _{x\ne 0}{r}_{B-B}(x))$$

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

Also,

$$\sum _{x\ne 0}{r}_{B-B}(x)=|\{b_1-b_2:b_1\ne b_2;b_1,b_2\in B\}|=\ell (\ell +1)$$

so that

$${\left|A\right|}^2(\ell +1)\le (N+\ell )(\left|A\right|+\ell )$$

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

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

$$\left|A\right|<n^{1/2}+(1-\gamma )n^{1/4}$$

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|A\right|<n^{1/2}+o(n^{\epsilon })$$

for all $\epsilon >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.

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.

AMM problem 12451

This is AMM problem 12451 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -
Let $A$ and $B$ be complex $n\times n$ and $n\times m$ matrices respectively. Let $0_{m,n}$ denote the $m\times n$ zero matrix and let $I_m$ denote the $m\times m$ identity matrix. Prove 

$$\exp \left[\begin{array}{cc}A& B\\ 0_{m,n}& 0_{m,m}\end{array}\right]=\left[\begin{array}{cc}\exp (A)& ({\int }_0^1\exp (tA)dt)\cdot B\\ 0_{m,n}& I_m\end{array}\right]$$

where $\exp$ be the matrix exponential function.

Solution -
Setting 

$$P=\left[\begin{array}{cc}A& B\\ 0_{m,n}& 0_{m,m}\end{array}\right]$$

we observe that the (unique) solution of the IVP ${\mathbf{z}}^{\prime }=P\mathbf{z}$ with $\mathbf{z}(0)={\mathbf{z}}_0$ is precisely $\mathbf{z}(s)=\exp (sP){\mathbf{z}}_0$ for all ${\mathbf{z}}_0\in {\mathbb{C}}^{m+n}$.

Thus, it suffices to check that for all ${\mathbf{x}}_0\in {\mathbb{C}}^n,{\mathbf{y}}_0\in {\mathbb{C}}^m$, the curves

$$\begin{array}{rl}\mathbf{x}(s)& =\exp (sA)\cdot {\mathbf{x}}_0+({\int }_0^1\exp (stA)dt)\cdot sB\cdot {\mathbf{y}}_0,\\ \mathbf{y}(s)& ={\mathbf{y}}_0\end{array}$$

solve the system of differential equations

$$\begin{array}{rl}{\mathbf{x}}^{\prime }& =A\mathbf{x}+B\mathbf{y},\\ {\mathbf{y}}^{\prime }& =\mathbf{0}\end{array}$$

and then put $s=1$.

This is easily verified; with $\mathbf{x}(s)$ as above, we have

$$\begin{array}{rl}{\mathbf{x}}^{\prime }(s)& =A\exp (sA){\mathbf{x}}_0+({\int }_0^1(I_n+stA)\exp (stA)dt)B{\mathbf{y}}_0\\ & =A\exp (sA){\mathbf{x}}_0+\exp (sA)B{\mathbf{y}}_0\end{array}$$

via integration by parts, and

$$\begin{array}{rl}A\mathbf{x}(s)& =A\exp (sA){\mathbf{x}}_0+({\int }_0^{1}sA\exp (stA)dt)B{\mathbf{y}}_0\\ & =A\exp (sA){\mathbf{x}}_0+(\exp (sA)-I_n)B{\mathbf{y}}_0\\ & ={\mathbf{x}}^{\prime }(s)-B\mathbf{y}(s)\end{array}$$

hence completing the proof. $◻$

AMM problem 12450

This is AMM problem 12450 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -
Let $n$ be an odd positive number, and suppose that $x_1,\dots ,x_n$ are chosen randomly and uniformly from the interval $[0,1]$. For $1\le i\le n$, let $y_i=x_i-x_i^2$. What is the expected value of the median of $\{y_1,\dots ,y_n\}$?

Solution -
Let $g(x)=x-x^2$ on $[0,1]$, and let

$$h(y)=\frac{1-\sqrt{1-4y}}{2}$$

be the inverse of the $g$ restricted to $[0,1/2]$.

Let $X\sim \mathcal{U}(0,1)$, and set $Y=g(X)$.

Then, by symmetry, $Y$ has density 

$$f_Y(y)=2f_X(h(y))\cdot \frac{d}{dy}h(y)=2h^{\prime }(y)$$

from which it follows that the cdf of $Y$ on $[0,1/4]$ is $F_Y(y)=2h(y)$. From an iid sample $y_1,\dots ,y_n\sim F_Y$ where $n=2k+1$, the sample median $\xi =y_{[k+1]}$ has density

$$f_{\xi }(\xi )=\frac{n!}{(k!{)}^2}{F}_Y(\xi {)}^k(1-F_Y(\xi ){)}^k{f}_Y(\xi )=\frac{n!}{(k!{)}^2}(2h(\xi ){)}^k(1-2h(\xi ){)}^{k}2h^{\prime }(\xi )$$

and hence, the expected value of the median is

$$\begin{array}{rl}\mathbb{E}[\xi ]=\int \xi f_{\xi }(\xi )d\xi & ={\int }_0^{1/4}\frac{n!}{(k!{)}^2}\xi (2h(\xi ){)}^k(1-2h(\xi ){)}^k\cdot 2h^{\prime }(\xi )d\xi \\ & ={\int }_0^1\frac{n!}{(k!{)}^2}g(x/2)x^k(1-x{)}^{k}dx\\ & ={\int }_0^1\frac{n!}{(k!{)}^2}[\frac{x}{2}-\frac{x^2}{4}]x^k(1-x{)}^{k}dx\\ & =\frac{n!}{(k!{)}^2}[\frac{k!(k+1)!}{2(n+1)!}-\frac{k!(k+2)!}{4(n+2)!}]\\ & =\frac{3n+5}{16n+32}\end{array}$$

which is the final answer.