
\documentstyle{article}

\textwidth=105mm
\textheight=160mm
\addtolength{\oddsidemargin}{-3cm}
\addtolength{\topmargin}{-3cm}
\sloppy

\begin{document}

\begin{center}
{\Large\bf Note on the maximum size of a Sidon set
}

\bigskip
{\large Martin Klazar
}

\bigskip
{\it Department of Applied Mathematics\\
Charles University\\
Malostransk\'e n\'am. 25\\
118 00 Praha 1\\
Czech Republic\\
{\tt klazar@kam.ms.mff.cuni.cz}
}
\end{center}

\bigskip
\begin{abstract}
We reprove an old result of Erd\H os and Tur\'an
which estimates from above the maximum size of a Sidon subset of $\{1,2,\ldots, n\}$. We show a connection with counting a special kind of up-down permutations.
\end{abstract}

\bigskip
$\bf N$ denotes the set of positive integers $\{1,2,\ldots\}$.
A set $X\subset \bf N$ is called a {\em Sidon set\/} if $x-y=n$ has at most
one solution $x, y\in X$ for any $n\in \bf N$. Let $F(n)$ be the maximum 
size of a Sidon subset $X\subset \{1, 2, \ldots, n\}$. The estimate
\begin{equation}
\label{old}
n^{1/2}-c_1n^{5/16}<F(n)<n^{1/2}+c_2n^{1/4},
\end{equation}
$c_1, c_2>0$ are constants, 
is a classical result. The upper bound was proved by
Erd\H os and Tur\'an \cite{erdosaturan} (this paper is reprinted in Tur\'an \cite{spisy}). The lower bound is due independently to Chowla 
\cite{chowla} and  Erd\H os \cite{erdos}. For further information we refer
the reader to Halberstam and Roth \cite{sequences}. A new proof of the upper bound in (\ref{old}) follows.

\bigskip
{\bf Proof. }Let $1\le x_1<x_2<\cdots <x_r\le n$ be a Sidon set and let
$k\in{\bf N}, k<r$. We consider a sum $S$ and estimate it from above and below,
\begin{equation}
\label{odhad}
{kr-{k+1\choose 2}+1\choose 2}\le S=\sum_{
0<j-i\le k} x_j-x_i<
{k+1\choose 2}n.
\end{equation}
To obtain the upper estimate write $x_j-x_i=(x_{i+1}-x_i)+(x_{i+2}-x_{i+1})+
\cdots +(x_j-x_{j-1})$ and observe that each term $x_l-x_{l-1}$ appears
then in $S$ at most $1+2+\cdots +k$ times, that is ${k+1\choose 2}$ times
("Gauss' lemma"). 
The lower estimate is immediate after realizing that $S$ consists of
$P=(r-1)+(r-2)+\cdots +(r-k)$ summands which are all {\em distinct\/} elements
of $\bf N$, thus $S\ge 1+2+\cdots +P$ (now we have applied "Gauss' lemma" twice). 

Easy simplifications turn (\ref{odhad})  in the inequality
$$
r<\sqrt{(1+1/k)n}+{(k+1)/2}.
$$
We can assume that $r>\lceil n^{1/4}\rceil$. Setting $k=\lceil n^{1/4}\rceil$ we finish the proof, 
\begin{equation}
\label{vysledek}
r<n^{1/2}+n^{1/4}+O(1).
\end{equation}
\hfill{$\Box$}

\bigskip
The original proof of Erd\H os and Tur\'an --- see \cite{erdosaturan}, 
\cite{sequences}, or \cite{spisy} --- is simple and elegant. However, we dare to say that the above proof is even simpler and more straightforward.
For instance, in the last step of the proof of Erd\H os and Tur\'an one has 
to choose the best $m$ to minimize
$$
{n\over m}+\left(n+m+{n^2\over m^2}\right)^{1/2}.
$$
The optimum choice $m=\sqrt{2}n^{3/4}$ implies
$$
r<n^{1/2}+\sqrt{2}n^{1/4}+O(1),
$$
i.e. a bound slightly worse compared to (\ref{vysledek}).

P. Erd\H os conjectured \cite{handbook} that in (\ref{old}) $c_1n^{5/16}$ can be replaced by $c_1$ and $c_2n^{1/4}$ by $n^{o(1)}$. We believe the full potential of our approach has not yet been exploited but so far we could not 
obtain in (\ref{vysledek}) even the modest improvement $o(n^{1/4})$.

Let us return to the lower estimate in (\ref{odhad}). For an $s$-tuple
$$
Y=(y_1, y_2,\ldots,y_s)\in {\bf N}^s 
$$
 and an interval $I=(y_i, y_{i+1}, \ldots, y_j), 1\le i\le j\le s,$ we define $|I|=j-i+1$ and $s(I)=\sum_{l=i}^j y_l$. We are interested in the quantity 
$$
S(s,k)=\min_Y \sum_{|I|\le k}s(I),
$$
where the minimum is taken over all
$s$-tuples $Y$ which have all $s(I)$ distinct.
With $P(s,k)$ denoting the number of summands $s(I)$, i.e. $P(s,k)=s+(s-1)+\cdots +(s-k+1)=k(s-(k-1)/2)$, we have
the trivial bound
$$
S(s,k)\ge 1+2+\cdots+P(s,k)={P(s,k)+1\choose 2}.
$$
We have used it in (\ref{odhad}), we had $s=r-1, y_i=x_{i+1}-x_i$, and
later $k\sim s^{1/2}$. An improvement here would imply an improvement
in (\ref{vysledek}).

\bigskip\noindent
{\bf Problem 1. }Improve for $k\sim s^{1/2}$ the trivial lower bound on $S(s,k)$.

\bigskip
It seems reasonable to consider a related quantity
$$
T(s,k)=\min_Y\sum_{|I|\le k}s(I),
$$
now we minimize over a larger family of $Y$'s which have totally distinct
only the $s(I)$'s with $|I|\le k$. For instance,
$$
T(s,1)=1+2+\cdots+P(s,1)={s+1\choose 2}
$$
and any permutation $Y=(y_1,\ldots,y_s)$ of $\{1, 2, \ldots, s\}$ attains
the minimum.

Our second group of problems arises from the natural question if $T(s,2)=1+2+\cdots+P(s,2)$. This to be true means there are natural numbers $y_1,\ldots, y_s$ so that
\begin{equation}
\label{perm}
y_1, y_1+y_2, y_2, y_2+y_3, y_3, \ldots, y_{s-1}, y_{s-1}+y_s, y_s
\end{equation}
is a permutation of $\{1, 2, \ldots, 2s-1\}$. 

Permutations $a_1a_2\ldots a_n$ of $\{1,2,\ldots, n\}$ satisfying
$a_1<a_2>a_3<\cdots$ are called {\em up-down\/} permutations, their counting is one
of the little gems of enumerative combinatorics (see Graham et al. \cite{beton}, p. 377). The permutation
in (\ref{perm}) is not only up-down, it meets a much more restrictive
condition --- each top number is a sum of its two neighbours.

\bigskip\noindent
{\bf Definition 2. }An up-down permutation $a_1a_2\ldots a_n$ of $\{1,2,\ldots, n\}$, $n$ is odd, is said to be a {\em sum-closed\/} permutation
if $a_{2i}=a_{2i-1}+a_{2i+1}$ for $i=1,2, \ldots, (n-1)/2$.

\bigskip\noindent
For instance, for $n=9$ the sum-closed permutations are 

\bigskip
\begin{center}
\begin{tabular}{lll}
$1\;4\;3\;9\;6\;8\;2\;7\;5$ & $1\;5\;4\;7\;3\;9\;6\;8\;2$ & 
$5\;9\;4\;6\;2\;3\;1\;8\;7$\\
$5\;7\;2\;8\;6\;9\;3\;4\;1$ & $2\;8\;6\;9\;3\;7\;4\;5\;1$ & 
$7\;8\;1\;3\;2\;6\;4\;9\;5.$
\end{tabular}
\end{center}

\bigskip
Let $Y(n)$, $n\in {\bf N}$ is odd, be the number of sum-closed permutations
of $\{1, 2, \ldots, n\}$. Reverting a sum-closed permutation produces
one, so $Y(n)$ is even for $n>1$. By hand and by computer, we have found
the following values of $Y(n)$.

\bigskip
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}\hline
$n$ & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17\\\hline
$Y(n)$ & 1 & 2 & 4 & 4 & 6 & 42 & 126 & 396 & 1786\\\hline
\end{tabular}

\smallskip
\begin{tabular}{|l|l|l|l|l|}\hline
$n$ & 19 & 21 & 23 & 25 \\\hline
$Y(n)$ & 7748 & 37962 & 213910 & 1228114\\\hline
\end{tabular}
\end{center}

\bigskip
Apparently $Y(2m-1)>0$ for any $m\in\bf N$ but it is not clear how to prove it
rigorously. 

\bigskip\noindent
{\bf Problem 3. }Show there is a sum-closed permutation for any odd $n$.

\bigskip\noindent
The enumeration of sum-closed permutations is a challenging task, they do not
seem to be easily tractable by the standard techniques.

\bigskip\noindent
{\bf Problem 4. }Is it true that the numbers $Y(2m-1)$ grow exponentially, i.e. 
$$
Y(2m-1)\sim c^m
$$
for some constant $c>1$ and $m\rightarrow\infty$?

\begin{thebibliography}{XX}

\bibitem{chowla} S. Chowla, Solution of a problem of Erd\"os and Tur\'an in
additive number theory, {\em Proc. Nat. Acad. Sci. India\/}, (1944) {\bf 14}, 1--2.

\bibitem{erdosaturan} P. Erd\"os and P. Tur\'an, On a problem of Sidon in additive
number theory, and some related problems, {\em J. London Math. Soc.\/}, (1941)
{\bf 16}, 212--215.

\bibitem{erdos} P. Erd\"os, Addendum, ibidem, (1944) {\bf 19}, 208.

\bibitem{beton} R. L. Graham, D. E. Knuth, and O. Patashnik, {\em Concrete 
Mathematics}, Addison-Wesley, Reading, 1994.

\bibitem{sequences} H. Halberstam and K. F. Roth, {\em Sequences\/},
Oxford University Press, Oxford, 1966.

\bibitem{handbook} C. Pomerance and A. S\'ark\"ozy, Combinatorial Number Theory,
in: {\em Handbook of Combinatorics,\/} R. L. Graham. M. Gr\"otschel and L. Lov\'asz (eds), North-Holland, 1995.

\bibitem{spisy} {\em Collected papers of P. Tur\'an\/} (ed. P. Erd\H os), 
Akad\'emiai Kiad\'o, Budapest, 1990.


\end{thebibliography}

\end{document}
