\input amstex \documentstyle{amsppt} \magnification=\magstephalf \pagewidth{6.25 truein} \pageheight{9.25 truein} \parskip=10pt \voffset=0pt \font\smallit=cmti9 \font\smalltt=cmtt9 \font\smallrm=cmr8 %%%%%%%%%%%%%%%%%%%% \topmatter \leftheadtext{\hskip 8pt \smalltt INTEGERS: \smallrm Electronic Journal of Combinatorial Number Theory \smalltt 0 (2000), \#A11 \hfill} \rightheadtext{\hskip 8pt \smalltt INTEGERS: \smallrm Electronic Journal of Combinatorial Number Theory \smalltt 0 (2000), \#A11 \hfill} \endtopmatter \document \centerline{\bf GAPS IN DENSE SIDON SETS} \vskip 20pt \centerline{\bf Javier Cilleruelo} \vskip 2pt \centerline{\smallit Departamento de Matem\'aticas, Universidad Aut\'onoma de Madrid, Madrid, Spain 28049} \vskip 2pt \centerline{\tt franciscojavier.cilleruelo\@uam.es} \vskip 30pt \centerline{\smallit Received: 3/23/00, Accepted: 8/22/00, Published: 8/24/00} \vskip 30pt \centerline{\bf Abstract} \noindent We prove that if $A\subset [1,N]$ is a Sidon set with $N^{1/2}-L$ elements, then any interval $I\subset [1,N]$ of length $cN$ contains $c|A|+E_I$ elements of $A$, with $|E_I|\le 52N^{1/4}(1+c^{1/2}N^{1/8})(1+L_+^{1/2}N^{-1/8})$, $L_+=\max \{0,L\}.$ In particular, if $|A|=N^{1/2}+O(N^{1/4})$, and $g(A)$ is the maximum gap in $A$, we deduce that $g(A)\ll N^{3/4}$. Also we prove that, under this condition, the exponent $3/4$ is sharp. \baselineskip=15pt \vskip 20pt \subhead \nofrills{\bf 1. Introduction} \endsubhead We say that $A$ is a Sidon set if all the sums $a+a'$, $a\le a' $, are different. Erd\H os and Turan \cite{5} proved that if $A\subset [1,N]$ is a Sidon set then $|A|\le N^{1/2}+ O(N^{1/4})$. On the other hand, Bose and Chowla \cite{1} proved that if $N=p^2+p+1$, then there exists a Sidon set $A\subset [1,N]$ with $p$ elements; i.e, the upper bound (1.1) is sharp except for the error term. Sidon sets of large size have notable properties of regularity. In \cite{7}, M. Koluntzakis proved that the elements of a Sidon set of large size, $|A|\sim N^{1/2}$, are well distribuited in the classes of residues of small modulo. See \cite{5} for an elementary proof of this result. Erd\H os and Freud \cite{4} proved that if $|A|\sim N^{1/2}$ then the elements of $A$ are well distributed in the interval $[1,N]$. \proclaim{Theorem A (Erd\H os-Freud)} Let $c>0$ and $A\subset [1,N]$ a Sidon set with $|A|\sim N^{1/2}$ elements. Then, any interval of length $cN$ contains $\sim cN^{1/2}$ elements. \endproclaim S.W. Graham \cite{6} has proved a more precise result. \proclaim{Theorem B (S. Graham)} Let $A\subset [1,N]$ be a Sidon set with $N^{1/2}+O(N^{1/4})$ elements. Then, any interval of length $cN$ contains $cN^{1/2}+O(N^{3/8})$ elements. \endproclaim If we denote by $g(A)=\max_{a_{k-1},a_k\in A}\{a_k-a_{k-1}\}$ the maximum gap in $A$, from the Theorem B it is easy to deduce that if $A$ is a Sidon set $A\subset [1,N]$ with $N^{1/2}+O(N^{1/4})$, then $g(A)\ll N^{7/8}$. In this paper we shall use an identity (Lemma 2.1), which was introduced in [2] and [3], to obtain a better result. \proclaim{Theorem 1.1} Let $A\subset [1,N]$ a Sidon set with $N^{1/2}-L$ elements. Then, any interval of length $cN$ contains $c|A|+E_I$ elements of $A$, with $$|E_I|\le 52N^{1/4}(1+c^{1/2}N^{1/8})(1+L_+^{1/2}N^{-1/8}),\quad L_+=\max \{0,L\}.$$ \endproclaim In particular we deduce from this theorem the following corollary for gaps. \proclaim{Corollary 1.1} If $A\subset [1,N]$ is a Sidon set and $|A|=N^{1/2}+O(N^{1/4})$, then $g(A)\ll N^{3/4}$. \endproclaim It is easy to see that the exponent $3/4$ is the best possible if $A\subset [1,N]$ is a Sidon set with $|A|=N^{1/2}+O(N^{1/4})$. Consider $N=p^2+p+1$, and a Sidon set $A$, $A\subset [1,N]$ with $p\ge \sqrt N-1$ elements. If we split the interval $[1,N]$ in intervals of length $[N^{3/4}]$, then, one of them contains less than $2N^{1/4}$ elements. If we remove these elements from $A$ we have a Sidon set $A'$ with $|A'|=N^{1/2}+O(N^{1/4})$ elements and $g(A')\gg N^{3/4}$. \medpagebreak We don't know how to derive a better estimate for $g(A)$ when the error term is less than $N^{1/4}$. It is related with the difficulty of improving the error term in the upper bound for finite Sidon sets. It would be interesting to know a good upper bound for $g(A)$ when $A$ is a Sidon set of maximal size. Maybe, it is possible an upper bound like $g(A)\ll N^{1/2+\epsilon}$. It should be noted that the classical construction of Erd\H os and Turan [5] of Sidon sets, $A_p=\{ 2kp+(k^2)_p: k=0,1,\dots ,p-1\}$, gives $g(A)\ll N^{1/2}$ for these sets. It seems not to be the case for the Ruzsa's construction [8] of finite Sidon sets. Numerical and heuristic arguments suggest that $g(A)/N^{1/2}\to \infty $ in this case. In particular, it would imply that the Erd\H os's Conjecture, $F(N)\le N^{1/2}+O(1)$, is not true. \subhead \nofrills{\bf 2. Proofs} \endsubhead The proof of the following lemma can be found in [2] or [3]. \proclaim{Lemma 2.1} Let $A\subset [1,N]$ be a sequence of integers. Then, for any integer $H\ge 1$ we have $$2\sum_{1\le h\le H}d(h)(H-h)=\frac{H^2|A|^2}{N+H-1}-H|A|+D_H, $$ where $$D_H=\sum_{1\le n\le N+H-1}\left (A(n)-A(n-H)- \frac{H|A|}{N+H-1}\right )^2, $$ $A(n)$ is the counting function of $A$ and $d(h)=\# \{ h=a-a';\quad a,a'\in A \} .$\hfil\qed \endproclaim $A(n)-A(n-H)$ is the number of elements of $A$ lying in the interval $(n-H,n]$ and the quantity $\frac{H|A|}{N+H-1}$ is the expected value of $A(n)-A(n-H)$. Then, $D_H$ is a measure of the distribution of the elements of $A$ in the interval $[1,N+H-1]$. The argument of the proof of the Theorem 1.1 is the following: If $|A|$ is close to $N^{1/2}$, ($L$ small), then $D_H$ is ``small" and consequently, the number of elements of $A$ lying in intervals of length $H$ is ``close", at least in average, to the expected number. From that we can deduce a ``good" distribution in any interval $I=(\alpha N, \beta N]$. Upper and lower bounds for the error $E_I=|A\cap I|-(\beta -\alpha)|A|$ are obtained in two different steps (Lemma 2.3 and Lemma 2.4). \proclaim{Lemma 2.2} If $A\subset [1,N]$ is a Sidon set with $|A|=N^{1/2}-L$ then, for any integer $H$ we have $$D_H\le \frac{3H^2L_+}{N^{1/2}}+\frac{H^3}N+2HN^{1/2} $$ where $L_+=\max \{0, L\} $. \endproclaim \demo{Proof} We apply Lemma 2.1 to the sequence $A$. Since $A$ is a Sidon set, hence $d(h)\le 1$ for any integer $h\ge 1$ and $2\sum_{1\le h\le H-1}d(h)(H-h)\le H^2$. Also we use the trivial estimate for the size of a Sidon set, $|A|\le 2N^{1/2}$. $$ D_H\le H^2-\frac{H^2|A|^2}{N+H-1}+H|A| =\frac{H^2N+H^3-H^2-H^2|A|^2}{N+H-1}+H|A| $$ \hskip 184pt $ \le \frac{H^2(N-|A|^2)}N+\frac{H^3}N+2HN^{1/2}. $ If $L\le 0$ , then $D_H\le \frac{H^3}N+2HN^{1/2}. $ If $L>0$, then $D_H\le \frac{H^2}{N}(N^{1/2}+|A|)L_+ +\frac{H^3}N+2HN^{1/2}\le \frac{3H^2L_+}{N^{1/2}}+\frac{H^3}N+2HN^{1/2}.$\hfil \qed \enddemo \medpagebreak Let $I=(\alpha N, \beta N]$, $c=\beta -\alpha$ and we write $|A\cap I|=c|A| +E_I $. We will choose $H=[N^{3/4}]$ in all the proofs. \pagebreak \proclaim{Lemma 2.3} $E_I\le 10N^{1/4}(c^{1/2}N^{1/8}+1)(L_+^{1/2}N^{-1/8}+1) $. \endproclaim \demo{Proof} We write $I_H=(\alpha N, \beta N+H]$, then $cN+H-1\le|I_H|\le cN+H+1$. We have $$\sum_{n\in I_H}A(n)-A(n-H)\ge H|A\cap I|,$$ since each $a\in A\cap I$ is counted $H$ times in the sum. Then, $$\sum_{n\in I_H}\left (A(n)-A(n-H)-\frac{H|A|}{N+H-1}\right )\ge H|A\cap I|-\frac{|I_H|H|A|}{N+H-1}$$ $$=E_IH+H|A|\left (c-\frac{|I_H|}{N+H-1}\right )\ge E_IH-H|A|\frac{(1-c)(H+1)}{N+H-1}\ge E_IH-\frac{H^2|A|}N.$$ Then $$E_I\le H^{-1}\sum_{n\in I_H}\left (A(n)-A(n-H)-\frac{H|A|}{N+H-1}\right )+\frac{H|A|}{N}. $$ Now we apply Cauchy's inequality, Lemma 2.1 and the trivial estimates $|A|\le 2N^{1/2}$, $N^{3/4}/2\le H \le N^{3/4}$ to get $$E_I\le H^{-1}|I_H|^{1/2}D_H^{1/2}+\frac{H|A|}{N} $$ $$\le H^{-1}\left ((cN)^{1/2}+(H+1)^{1/2}\right )\left (\frac{\sqrt 3 HL_+^{1/2}}{N^{1/4}}+\frac{H^{3/2}}{N^{1/2}}+\sqrt 2 H^{1/2}N^{1/4} \right )+\frac{H|A|}{N} $$ $$\le 2N^{-3/4}\left (c^{1/2}N^{1/2}+\sqrt 2N^{3/8}\right )\left (\sqrt 3 N^{1/2}L_+^{1/2}+N^{5/8}+\sqrt 2N^{5/8}\right )+2N^{1/4} $$ $$\le 10N^{1/4}\left (c^{1/2}N^{1/8}+1 \right )\left (L_+^{1/2}N^{-1/8}+1 \right ).\hfil \qed $$ \enddemo \proclaim{Lemma 2.4} $-E_I\le 52N^{1/4}(c^{1/2}N^{1/8}+1)(L_+^{1/2}N^{-1/8}+1) $. \endproclaim \demo{Proof} $$\sum_{n\in I_H}A(n)-A(n-H) \le H \left (|A\cap I|+|A\cap(\alpha N -H,\alpha N]|+|A\cap (\beta N, \beta N+H]| \right ). $$ We apply Lemma 2.3 to the intervals $(\alpha N-H,\alpha N]$ and $(\beta N, \beta N+H]$ to obtain an upper bound for the last two terms. $$|A\cap (\alpha N -H, \alpha N]|+|A\cap (\beta N, \beta N+H]|\le 2\frac HN |A|+ 20N^{1/4}\left (\frac{H^{1/2}N^{1/8}}{N^{1/2}}+1\right )\left (L_+^{1/2}N^{-1/8}+1\right ) $$ $$\le 4N^{1/4}+40N^{1/4}(L_+^{1/2}N^{-1/8}+1)\le 44N^{1/4}+40N^{1/8}L_+^{1/2}.$$ Then, $$\sum_{n\in I_H}\left (A(n)-A(n-H)-\frac{H|A|}{N+H-1}\right )\le H|A\cap I|-\frac{|I_H|H|A|}{N+H-1}+H\left (44N^{1/4}+40N^{1/8}L_+^{1/2}\right )$$ $$=E_IH+H|A|\left (c -\frac{|I_H|}{N+H-1} \right )+ H\left (44N^{1/4}+40N^{1/8}L_+^{1/2} \right ) $$ \hskip 55pt $ \le E_IH+H(44N^{1/4}+40N^{1/8}L_+^{1/2}),$ because $|I_H|\ge cN+H-1$. Finally we apply Cauchy inequality and Lemma 2.2 to obtain $$-E_I\le 44N^{1/4}+40N^{1/8}L_+^{1/2}+H^{-1}\sum_{n\in I_H}\left |A(n)-A(n-H)-\frac{H|A|}{N+H-1}\right | $$ $$\le 44N^{1/4}+40N^{1/8}L_+^{1/2}+2N^{-3/4}|I_H|^{1/2}D_H^{1/2} $$ $$\le 44N^{\frac{1}{4}}+40N^{\frac{1}{8}}L_+^{\frac{1}{2}}+2N^{\frac{-3}{4}}\left ((cN)^{1/2}+(H+1)^{1/2}\right )\left (\frac{\sqrt 3 H L_+^{1/2}}{N^{1/4}}+\frac{H^{3/2}}{N^{1/2}}+\sqrt 2H^{1/2}N^{1/4}\right ) $$ $$\le 44N^{1/4}+40N^{1/8}L_+^{1/2}+2N^{-3/4}\left (c^{1/2}N^{1/2}+\sqrt 2N^{3/8}\right )\left (\sqrt 3N^{1/2}L_+^{1/2}+N^{5/8}+\sqrt 2N^{5/8}\right ) $$ $$\le 52N^{1/4}(1+c^{1/2}N^{1/8})(1+L_+^{1/2}N^{-1/8}).\hfil \qed $$ \enddemo \medpagebreak Lemma 2.3 and Lemma 2.4 imply Theorem 1.1. To prove Corollary 1.1, suppose that $A=N^{1/2}-L$, with $L_+\le kN^{1/4}$, and let $I$ be any interval of length $k'N^{3/4}$. If we apply Lemma 2.4 we have $$|A\cap I|>\frac{k'}{N^{1/4}}|A|-52N^{1/4}(1+{k'}^{1/2})(1+k^{1/2})>k'N^{1/4}-kk'- 52 N^{1/4}(1+{k'}^{1/2})(1+k^{1/2}).$$ If we take $k'$ large enough, $k'>10000k$, then $|A\cap I|>0$ for any interval of length greater than $k'N^{3/4}$. \subhead \nofrills{\bf References} \endsubhead \ref \no 1 \by R.C. Bose and S. Chowla \pages 141-147 \paper Theorems in the additive theory of numbers \yr1962-3 \vol 37 \jour Comment. Math. Helvet \endref \ref \no 2 \by J. Cilleruelo \paper New upper bounds for $B_h$ sequences \jour (preprint) \endref \ref \no 3 \by J. Cilleruelo and G. Tenenbaum \paper An overlapping lemma and applications \jour (preprint) \endref \ref \no 4 \by P. Erd\H os and R. Freud \pages 196-205 \paper On Sums of a Sidon-Sequence \yr1991 \vol 38 \jour J. Number Theory \endref \ref \no 5 \by P. Erd\H os and P. Turan \pages 212-215 \paper On a problem of Sidon in additive number theory and on some related problems \yr1941 \vol 16 \jour J. London Math. Soc. \moreref \paper Addendum \by P. Erd\H os \yr1944 \vol 19 \page 208 \endref \ref \no 6 \by S.W. Graham \paper $B_h$ sequences \inbook Proceedings of a Conference in Honor of Heini Halberstam \eds B.C.Berndt, H.G.Diamond, A.J.Hildebrand \publaddr Birkhauser \yr1996\pages 337-355 \endref \ref \no 7 \by M. Kolountzakis \pages 147-153 \paper On the uniform distribution in residue classes of dense sets of integers with distinct sums \yr1999 \vol 76 \jour J. Number Theory \endref \ref \no 8 \by I. Ruzsa \pages 259-282 \paper Solving a linear equation in a set of integers I \yr 1993 \vol LXV.3 \jour Acta Arithmetica \endref \end