% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.12}{21(4)}{2014}
\usepackage{amsthm,amsmath,amssymb}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\newcommand{\prob}{\mathbb{P}}
\newcommand{\expect}{\mathbb{E}}
\newcommand{\variance}{\textrm{var}}
\newcommand{\rn}{\mathbb{R}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\eps}{\epsilon}
\newcommand{\points}{\mathcal{P}}
\newcommand{\lines}{\mathcal{L}}
\newcommand{\incidence}{\mathcal{I}}
\newcommand{\nn}{\mathbb{N}}
\newcommand{\ind}{1\hspace{-2.5mm}{1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf $k$-fold Sidon sets}

\author{Javier Cilleruelo\thanks{
Departamento de Matem\'{a}ticas, Universidad Aut\'{o}noma de Madrid, 28049 Madrid.}
\and
Craig Timmons\thanks{Department of Mathematics and Statistics, California State University Sacramento.
Partially supported by NSF Grant DMS-1101489 through Jacques Verstra\" ete.}}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Nov 4, 2013}{Sep 30, 2014}{Oct 9, 2014}\\
\small Mathematics Subject Classifications: 05D99, 11B75}

\begin{document}

\maketitle

\begin{abstract}
Let $k \geq 1$ be an integer.  A set $A \subset \integers$ is a \emph{$k$-fold Sidon set} if $A$ has only trivial solutions to each equation of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 = 0$ where
$0 \leq |c_i | \leq k$, and $c_1 + c_2 + c_3 + c_4 = 0$.  We prove that for any integer $k \geq 1$, a $k$-fold Sidon
set $A \subset [N]$ has at most $(N/k)^{1/2} + O((Nk)^{1/4})$ elements. Indeed we prove that given any $k$ positive integers $c_1<\cdots <c_k$, any set $A\subset [N]$ that contains only trivial solutions
to $c_i(x_1-x_2)=c_j(x_3-x_4)$ for each $1 \le i \le j \le k$, has at most $(N/k)^{1/2}+O((c_k^2N/k)^{1/4})$ elements. On the other hand, for any $k \geq 2$ we can exhibit $k$ positive integers $c_1,\dots, c_k$ and a set $A\subset [N]$ with
$|A|\ge (\frac 1k+o(1))N^{1/2}$, such that $A$ has only trivial solutions to $c_i(x_1 - x_2) = c_j (x_3 -  x_4)$
for each $1 \le i \le j\le k$.

  \bigskip\noindent \textbf{Keywords:} Sidon sets, $k$-fold Sidon sets
\end{abstract}

\section{Introduction}

Let $\Gamma$ be an abelian group.  A set $A \subset \Gamma$ is a \emph{Sidon} set if $a + b = c + d$ and $a,b,c,d \in A$ implies $\{a,b \} = \{c,d \}$.  Sidon sets in $\integers$ and in the group $\integers_N:= \integers / N \integers$ have been studied extensively.  Erd\H{o}s and Tur\'{a}n \cite{ET} proved that a Sidon set $A \subset [N]$ has at most $N^{1/2} + O(N^{1/4})$ elements.  Constructions of
Singer \cite{S}, Bose and Chowla \cite{BC}, and Ruzsa \cite{R} show that this upper bound is asymptotically best possible.  It is a prize problem of Erd\H{o}s \cite{E} to determine whether or not the error term is bounded.  For more on Sidon sets we recommend O'Bryant's survey \cite{OB}.

Let
\begin{equation}\label{r eq}
c_1 x_1 + \dots + c_r x_r = 0
\end{equation}
be an integer equation where $c_i \in \integers \backslash \{ 0 \}$, and $c_1 + \dots + c_r = 0$.
Call such an equation an \emph{invariant equation}.
A solution $(x_1 , \dots , x_r ) \in \integers^r$ to (\ref{r eq}) is \emph{trivial} if there is a partition of
$\{1, \dots , r \}$ into nonempty sets $T_1 , \dots , T_m$ such that for every $1 \leq i \leq m$, we have
$\sum_{j \in T_i} c_j = 0$, and $x_{j_1} = x_{j_2}$ whenever $j_1 , j_2 \in T_i$.  A natural extremal problem is to determine the maximum size of a set $A \subset [N]$ with only trivial solutions to (\ref{r eq}).
This problem was investigated in detail by Ruzsa \cite{R}.
One of the important open problems from \cite{R} is the genus problem.
Given an invariant equation $E : c_1 x_1+ \dots + c_r x_r = 0$, the \emph{genus} $g(E)$ is the largest
integer $m$ such that there is a partition of $\{1, \dots , r \}$ into nonempty sets $T_1 , \dots , T_m$, such that $\sum_{j \in T_i} c_j = 0$ for $1 \leq i \leq m$.  Ruzsa proved that if $E$ is an invariant equation
and $A \subset [N]$ has only trivial solutions to $E$, then $|A| \leq c_E N^{1 / g(E)}$.  Here $c_E$ is a positive constant
depending only on the equation $E$.
Determining if there are sets $A \subset [N]$ with $|A| = N^{1 / g(E) - o(1)}$ and having only trivial solutions to $E$ is open for most equations.  In particular, the genus problem is open for the equation $2x_1 + 2x_2 = 3x_3 + x_4$.  This equation has genus 1 but the best known construction \cite{R} gives a set $A \subset [N]$ with $|A| \geq c N^{1/2}$ where $c>0$ is a positive constant.
More generally, Ruzsa showed that for any four variable equation $E:c_1 x_1 + c_2 x_2 = c_3 x_3  + c_4 x_4$ with
$c_1 + c_2  = c_3 + c_4$ and $c_i \in \mathbb{N}$, there is a set $A \subset [N]$ with only trivial solutions
to $E$ and $|A| \geq c_E N^{1/2 - o(1)}$.  In this paper we consider special types of four variable invariant equations.

Let $k \geq 1$ be an integer.
A set $A \subset \integers$ is a \emph{$k$-fold Sidon} set if $A$ has only trivial solutions to each equation of the form
\begin{equation*}
c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 = 0
\end{equation*}
where $0 \leq |c_i | \leq k$, and $c_1 + c_2 +c_3 + c_4 = 0$.  A 1-fold Sidon set is a Sidon set.  A 2-fold Sidon set has only trivial solutions to each of the equations
\begin{equation*}
x_1 + x_2 - x_3 - x_4 = 0, ~~~~~ 2x_1 + x_2 - 2x_3 - x_4 = 0, ~~~~~ 2x_1 - x_2 - x_3 = 0.
\end{equation*}
One can also define $k$-fold Sidon sets in $\integers_N$.  We must add the condition that $N$ is relatively prime to
all integers in the set $\{1,2, \dots , k \}$.  The reason for this is that if a coefficient $c_i \in \{1,2, \dots , k \}$ has a common factor with $N$,
then in $\mathbb{Z}_{N}$ one could have $c_i ( a_1 - a_2 ) = 0$ with $a_1 \neq a_2$.  In this case, if $|A| \geq 3$, we can choose $a_3 \in A \backslash \{a_1,a_2 \}$, and obtain the nontrivial solution $(x_1,x_2,x_3,x_4) = (a_1,a_2,a_3,a_3)$
to the equation $c_i ( x_1 - x_2 ) + x_3 - x_4 = 0$.

Lazebnik and Verstra\"{e}te \cite{LV} were the first to define $k$-fold Sidon sets.  They conjectured the following.

\begin{conjecture}[Lazebnik, Verstra\"{e}te \cite{LV}]\label{LV conjecture}
For any integer $k \geq 3$, there is a positive constant $c_k > 0$ such that for all integers $N \geq 1$, there is a
$k$-fold Sidon set $A \subset [N]$ with $|A| \geq c_k N^{1/2}$.
\end{conjecture}

This conjecture is still open.  Lazebnik and Verstra\"{e}te proved that for infinitely many $N$, there is a 2-fold Sidon set $A \subset \integers_N$ with $|A| \geq \frac{1}{2}N^{1/2} - 3$.  Axenovich \cite{A} and Verstra\"{e}te (unpublished) observed that
one can adapt Ruzsa's construction for four variable equations (Theorem 7.3, \cite{R}) to construct $k$-fold Sidon
sets $A \subset [N]$ or $A \subset \integers_N$ with $|A| \geq c_k N^{1/2} e^{ - c_k \sqrt{ \log N } }$ for any $k \geq 3$.
An affirmative answer to Conjecture~\ref{LV conjecture}, even in the case when $k=3$, would have applications to hypergraph Tur\'{a}n problems \cite{LV} and extremal graph theory \cite{TV}.

Since any $k$-fold Sidon set is a Sidon set, the trivial upper bound $|A|\le \sqrt{N-3/4}+1/2$ for a Sidon set
$A \subset \mathbb Z_N$, and the Erd\H{o}s-Tur\'{a}n bound  $|A| \leq N^{1/2} + O(N^{1/4})$ for any Sidon set $A \subset [N]$, also hold for  $k$-fold Sidon sets.
We will obtain better upper bounds for $k$-fold Sidon sets.  Instead of considering all the possible equations $c_1x_1+c_2x_2+c_3x_3+c_4x_4=0$ with $c_1+c_2+c_3+c_4=0$, we will take advantage only of the equations of the form
$$c_1(x_1-x_2)=c_2(x_3-x_4).$$

For any $c_1,\dots,c_k$ with $(c_i,N)=1$, if $A\subset \mathbb Z_N$ contains only trivial solutions
to $c_i(x_1-x_2)=c_j(x_3-x_4)$ for each $1 \le i \le j \le k$, then
\begin{equation}\label{group}
|A|\le \sqrt{ \frac{N-1}k+\frac 14 }+\frac 12.
\end{equation}
To see this, consider all elements of the form $c_i(x-y)$ where $1 \le i \le k$, and $x \neq y$ are elements of $A$.
All of these elements are distinct and nonzero.  Therefore, $k|A|(|A|-1)\le N-1$ which is equivalent to (\ref{group}).

The short counting argument used to obtain \eqref{group} does not work in $\integers$.
Using a more sophisticated argument, we can show that a bound similar to \eqref{group} does hold in $\mathbb{Z}$.

\begin{theorem}\label{k ub}
Let $k \geq 1$ be an integer and $1 \leq c_1 < c_2 <  \dots < c_k$ be a set of $k$ distinct integers.  If $A \subset [N]$ is a set with only trivial solutions to $c_i (x_1 - x_2)  = c_j (x_3 - x_4)$ for each $1 \leq i \leq j \leq k$, then
\begin{equation*}
|A| \leq \left( \frac{N}{k} \right)^{1/2} + O \left( \left(  \frac{c_k^2N}{k} \right)^{1/4} \right).
\end{equation*}
\end{theorem}
Taking $c_j=j$ for $1\le j\le k$, we have the following corollary.
\begin{corollary}\label{k cor}
If $k \geq 1$ is an integer and $A \subset [N]$ is a $k$-fold Sidon set, then
\[
|A| \leq \left( \frac{N}{k} \right)^{1/2} + O ( (kN)^{1/4} ).
\]
\end{corollary}

In Theorem \ref{k ub} and Corollary \ref{k cor}, the Landau symbols are with respect to $N$.  That is, we view $k$, 
$c_1, \dots , c_k$ as being fixed, and $N$ tending to infinity.  

It is natural to ask if we can improve Corollary~\ref{k cor} if we make full use of the assumption that $A$ is a $k$-fold Sidon set.
For example, the bound $|A| \leq (N/3)^{1/2} + O(N^{1/4})$ holds under the assumption that
$A \subset [N]$ has only trivial solutions to $c_1 (x_1 - x_2) = c_2 (x_3 - x_4)$ for each $1 \leq c_1 \leq c_2 \leq 3$.  A 3-fold Sidon set additionally has only trivial solutions to $2x_1 + 2x_2 = 3x_3 + x_4$.  Our argument does not capture this property.  It is not known if this additional assumption would improve the upper bound $|A| \leq (N/3)^{1/2} + O(N^{1/4})$.

The method used by Lazebnik and Verstra\"{e}te to construct 2-fold Sidon sets is rather robust.
Using this method, we prove the following theorem.

\begin{theorem}\label{weak construction}
There exist $k$ distinct integers $c_1,\dots,c_k$ and  infinitely many $N$, such that there is a set $A \subset \integers_{N}$ with
\[
|A| \geq \frac{N^{1/2}}{k}(1 - o(1) )
\]
and  having only trivial solutions to $c_i(x_1 - x_2) = c_j(x_3 - x_4)$ for each $1\le i\le j\le k$.
\end{theorem}

The next section contains the proof of Theorem~\ref{k ub}.  Section 3 contains the proof of
Theorem~\ref{weak construction}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proof of  Theorem~\ref{k ub}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 For finite sets $B , C \subset \mathbb{Z}$, define
\[
r_{B + C} (x) = |  \{ (b,c) : b + c = x , b \in B , c \in C \} |
\]
and
\[
r_{B - C}(x) = |  \{ (b,c) : b - c = x , b \in B , c \in C \} |.
\]
The following useful lemma has appeared in the literature (see \cite{C} or \cite{R}).
\begin{lemma}\label{lemma1}
For any finite sets $B , C \subset \mathbb{Z}$,
\begin{equation}\label{eq lemma1}
\frac{  ( |B| |C| )^2 }{ | B + C | } \leq |B | |C| + \sum_{x \neq 0} r_{B - B} (x) r_{C - C}(x).
\end{equation}
\end{lemma}
\begin{proof}
Observe $\sum_{x \in B + C} r_{B +C}(x)$ counts every ordered pair $(b,c) \in B \times C$ exactly once so that 
$|B| |C| = \sum_{x \in B+ C} r_{B + C} (x)$.  By the Cauchy-Schwarz inequality, 
\begin{equation}\label{new eq1}
\frac{  ( |B| |C| )^2 }{ | B + C | }  =  \frac{  \left(  \sum_{x \in B + C} r_{B + C}(x) \right)^2 }{ |B + C| }
\leq  \sum_x r_{B + C}^2 (x). 
\end{equation}
The sum $\sum_{x} r_{B + C}^2 (x)$ counts 4-tuples $(b,b',c,c')$ with $b,b' \in B$, $c,c' \in C$, and 
$b + c = b' + c'$.  The equation $b + c = b' + c'$ is equivalent to $b - b' =  c' -c$ and so
\begin{equation}\label{new eq2}
\sum_{x} r_{B + C}^2 (x) = \sum_{x} r_{B - B} (x) r_{C - C} (x).
\end{equation} 
Combining (\ref{new eq1}) and (\ref{new eq2}), we have 
\[
\frac{ ( |B| |C| )^2 }{ |B + C| } \leq \sum_{x} r_{B - B} (x) r_{C - C} (x)  = |B| |C| + \sum_{x \neq 0} r_{B - B} (x) r_{C - C} (x)
\]
which proves (\ref{eq lemma1}).  
\end{proof}

Before giving the proof of Theorem \ref{k ub} we take a moment to describe some of ideas of the proof.  
Suppose $A \subset [N]$ is a set satisfying the hypothesis of Theorem \ref{k ub}.  
If $c_r  A := \{ c_r a : a \in A \}$, then the $k$-fold Sidon property implies that
\begin{equation}\label{new eq3}
\sum_{r=1}^{k} r_{c_r  A - c_r A} (y) \leq 1
\end{equation}
for any $y \neq 0$.  One may then apply Lemma \ref{lemma1} to $c_r  A$ and the interval 
$C = \{0,1, \dots , m-1 \}$ for each $1 \leq r \leq k$.
An obstacle in this approach is the expression 
$|c_r  A + C|$ that appears in the denominator on the left hand side of (\ref{eq lemma1}).  Since 
$c_r  A + C \subset \{1 , 2, \dots , c_r N + m - 1 \}$, we have 
$| c_r  A + C | \leq c_r N + m$ but this upper bound that is too large for our approach.  Instead of 
$c_r  A$, we will consider the sets $B_{r,i} := \{ x : c_r x + i \in A \}$, $0 \leq i \leq c_r - 1$.  We will show that 
an analogue of (\ref{new eq3}) holds for the $B_{r,i}$'s which, although not difficult, is one of the most important parts of the proof. 
Additionally, we have that $| B_{r ,i} + C| \leq N / c_r + m$ and this is what leads to a more effective application of Lemma \ref{lemma1}.  

\begin{proof}[Proof of Theorem~\ref{k ub}]  Let $1 \leq c_1 < c_2 < \dots < c_k$ be $k$ distinct integers.
Let $A \subset [N]$ be a set with only trivial solutions to $c_i (x_1 - x_2) = c_j (x_3 - x_4)$ for each $1 \leq i \leq j \leq k$.
Let
\[
B_{r,i} = \{ x : c_r x + i \in A \}
\]
for $1 \leq r \leq k$ and $0 \leq i \leq c_r -1$.  
Therefore,
 $$|A| =\sum_{i=0}^{c_r - 1} |\{a\in A:\ a\equiv i\pmod{c_r}\} |= \sum_{i=0}^{c_r - 1} | B_{r,i} |$$ so by the Cauchy-Schwarz inequality,
\begin{equation}\label{eq 2}
|A|^2 = \left(  \sum_{i=0}^{c_r-1} |B_{r,i} | \right)^2 \leq c_r \sum_{i=0}^{c_r-1} |B_{r,i} |^2.
\end{equation}
For any $y \neq 0$,
\begin{equation}\label{eq 1.5}
\sum_{r = 1}^{k} \sum_{i=0}^{c_r - 1} r_{B_{r,i} - B_{r,i} } (y) \leq 1.
\end{equation}
To see this, suppose
\begin{equation}\label{eq 2.5}
y = x_1 - x_2 = x_3 - x_4
\end{equation}
where $x_1 , x_2 \in B_{r,i}$ and $x_3 , x_4 \in B_{r' , i'}$ for some
$1 \leq r, r' \leq k$, $1 \leq i \leq c_r - 1$, and $1 \leq i' \leq c_{r'} - 1$.  There are elements $a_1 , a_2 , a_3 , a_4 \in A$ such that
\[
c_r x_1 + i = a_1,~~ c_r x_2 + i = a_2,~~ c_{r'} x_3 + i' = a_3, ~~\mbox{and}~~c_{r'} x_4 + i' = a_4.
\]
Then (\ref{eq 2.5}) implies
\[
\frac{1}{c_r} (a_1 - i ) - \frac{1}{c_r} ( a_2 - i) = \frac{1}{c_{r'}} ( a_3 - i') - \frac{1}{ c_{r'} } ( a_4 - i'),
\]
thus $c_{r'} (a_1 - a_2) = c_r (a_3 - a_4)$.  Since $y \neq 0$, we have $a_1 \neq a_2$ and $a_3 \neq a_4$ and then we would have a non trivial solution to the equation $c_{r'} (x_1 - x_2) = c_r (x_3 - x_4)$.
%and a non trivial solution of the equation $c_{r'}(x-y)=c_r(u-v)$.
%By hypothesis,
%$r' = r$, $a_1 = a_3$, and $a_2 = a_4$.  As a result, $c_r x_1 + i = a_1 = a_3 = c_r x_3 + i'$.
%If $i = i'$, then $x_1 = x_3$, $x_2 = x_4$ and we are done.  Assume $i \neq i'$.  Without loss of generality, say $i > i'$.  Then
%\begin{equation}\label{eq 2.6}
%i - i' = c_r (x_3 - x_1)
%\end{equation}
%Since $0 \leq i' < i \leq c_r - 1$, we have $0 < i - i' \leq c_r - 1$ but this contradicts (\ref{eq 2.6}).  This shows that if
%$y = x_1 - x_2$ with $x_1 , x_2 \in B_{r,i}$, then $r,i, x_1$, and $x_2$ are all unique which completes the proof of (\ref{eq 1.5}).

Let $C = \{ 0 ,1, \dots , m-1 \}$.  For any $1 \leq r \leq k$ and $0 \leq i \leq c_r-1$,
the set $B_{r,i} + C$ is contained in the interval $ \{ 0 ,1 , \dots ,\lfloor N/c_r \rfloor + m - 1 \}$.
This gives the trivial estimate $| B_{r , i } + C | \leq N/c_r  + m$.  By Lemma~\ref{lemma1} applied to $B_{r,i}$ and $C$,
\[
\frac{ |B_{r,i}|^2 m^2 }{ N/c_r + m} \leq |B_{r,i} | m + \sum_{y \neq 0} r_{B_{r,i} - B_{r,i} } (y) r_{C - C}(y).
\]
We sum this inequality over all $1 \leq r \leq k$ and $0 \leq i \leq c_r-1$ to get
\begin{eqnarray*}
m^2 \sum_{r =1 }^{k} \frac{1}{N/c_r  + m } \sum_{i=0}^{c_r-1} |B_{r,i} |^2 & \leq & \sum_{r = 1}^{k} \sum_{i=0}^{c_r-1} |B_{r,i} | m \\
& + & \sum_{y \neq 0} \sum_{r = 1}^{k} \sum_{i=0}^{c_r-1} r_{B_{r,i}  - B_{r,i} }(y)  r_{C - C}(y) \\
& \leq & k |A|m + \sum_{y \neq 0} r_{C - C}(y) \\
& \leq & m( k |A| + m ).
\end{eqnarray*}
From (\ref{eq 2}) and the previous inequality, we deduce that 
\begin{equation}\label{eq 3}
m^2 |A|^2 \sum_{r =1}^{k} \frac{1}{ N + c_r m} \leq m( k|A| + m).
\end{equation}
The left hand side of (\ref{eq 3}) is at least $\frac{ |A|^2 km^2 }{N + c_k m}$.  Therefore,
$\frac{ |A|^2 km }{N + c_k m} \leq k |A| + m$, and so
\[
|A|^2 km \leq ( N + c_k m)( m + k |A| ).
\]
We complete the square and use the inequality $(x+y)^2 \leq 2x^2 + 2y^2$ to obtain 
\begin{eqnarray*}
\left( |A| - \left( \frac{N}{2m} + \frac{c_k}{2} \right) \right)^2 & \leq & \frac{N}{k} + \frac{c_k m}{k} + \left( \frac{N}{2m} + \frac{c_k}{2} \right)^2 \\
& \leq & \frac{N}{k} + \frac{c_k m}{k} + \frac{N^2}{2m^2} + \frac{c_k^2}{2} \\
& = & \frac{N}{k} \left( 1 + \frac{c_k m}{N} + \frac{Nk}{2m^2} + \frac{k c_k^2}{2N} \right).
\end{eqnarray*}
Taking square roots and using the inequality $\sqrt{1 + x} \leq 1 + x$ for $x \geq 0$, we solve for $|A|$ to get
\begin{eqnarray*}
|A| & \leq & \left( \frac{N}{k} \right)^{1/2} \left(1 + \frac{c_k m}{N} + \frac{Nk}{2m^2} + \frac{k c_k^2}{2N} \right) + \frac{N}{2m} + \frac{c_k}{2} \\
& = & \left( \frac{N}{k} \right)^{1/2} + \frac{c_k m}{k^{1/2} N^{1/2}} + \frac{ N^{3/2} k^{1/2} }{2m^2}
+ \frac{k^{1/2}c_k^2 }{2N^{1/2} } + \frac{N}{2m} + \frac{c_k}{2}.
\end{eqnarray*}
Take $m = \lceil (N^{3/4} k^{1/4})/c_k^{1/2} \rceil$ to get $|A| \leq \left( \frac{N}{k} \right)^{1/2} + O ( (c_k^2 N/k)^{1/4})$.
This completes the proof of Theorem~\ref{k ub}.

\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proof of Theorem~\ref{weak construction}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Let $k \geq 2$ be an integer.  Let $p$ be a prime, and let $M \geq 1$ be a large integer.
Let $r$ be any prime with $r > Mk$.  Let $i \geq 1$ be an integer, and set $t = r^i$ and $q = p^t$.

We will prove that  for $c_j=p^{j-1}$ for $j=1,\dots k$ there exists a set $A\subset \mathbb Z_{q^2-1}$ with $|A|\ge \frac{q}{k} \left( 1 - \frac{1}{M} \right) - (p^4 - 1)(M - 1)$ and having only trivial solutions to
$$x_1-x_2=p^{j-1}(x_3-x_4)$$
for $1 \leq j \leq k$.  This proves Theorem~\ref{weak construction} because  as $i$ tends to infinity, the term
$\frac{q}{k} \left( 1 - \frac{1}{M} \right)$ is the dominant term.  $M$ can be taken  as large as we want, and $(p^4 - 1)(M-1)$ is constant with respect to $i$.

Let $\theta$ be a generator of the cyclic group $\mathbb{F}_{q^2}^{*}$.
Bose and Chowla \cite{BC} proved that the set
\begin{equation*}
C (q , \theta ) = \{ a \in \mathbb{Z}_{q^2 - 1} :  \theta^{a} - \theta \in \mathbb{F}_q \}
\end{equation*}
is a Sidon set in $\mathbb{Z}_{q^2 - 1}$.  Lindstr\"{o}m \cite{L} proved
\[
B(q , \theta ) = \{ b \in \mathbb{Z}_{q^2 - 1}:  \theta^b + \theta^{qb} = 1 \}
\]
is a translate of $C(q , \theta)$ and is therefore a Sidon set.

\begin{lemma}\label{closure}
The map $x \mapsto px$ is an injection from $\mathbb{Z}_{q^2- 1}$ to $\mathbb{Z}_{q^2 - 1}$ that maps $B (q , \theta )$ to $B(q, \theta )$.
\end{lemma}
\begin{proof}
The map $x \mapsto px$ is 1-to-1 since $p$ is relatively prime to $q^2 -1$.  If $b \in B ( q , \theta)$, then
\[
1 = ( \theta^{b} + \theta^{qb} )^p = \theta^{pb} + \theta^{q(pb)}
\]
so $pb \in B(q , \theta)$.
\end{proof}

Let $\pi : B(q , \theta ) \rightarrow B ( q , \theta )$ be the permutation $\pi (b) = pb$.  As in \cite{LV}, we use the cycles of
$\pi$ to define $A$.  Let $\sigma = (b_1 , \dots , b_m)$ be a cycle of $\pi$.  If $m < k$, then remove all elements of $\sigma$ from $B(q,\theta)$.  If $m \geq k$, then remove all $b_j$ in $\sigma$ for which $j$ is not divisible by $k$.  Do this for each cycle
of $\pi$.  Let $A$ be the resulting subset of $B(q, \theta )$.

\begin{lemma}\label{claim 1}
For each $c \in \{1,p , p^2 , \dots , p^{k-1} \}$, $A$ has only trivial solutions to
\[
x_1 - x_2 = c( x_3 - x_4).
\]
\end{lemma}
\begin{proof}
Suppose $a_1 , a_2 , a_3 , a_4 \in A$ and $a_1 - a_2 = p^j ( a_3 - a_4 )$ for some $0 \leq j \leq k-1$.
By Lemma~\ref{closure}, there are elements $b_3 , b_4 \in B(q, \theta )$ such that $p^j a_3 = b_3$ and $p^j a_4 = b_4$.
This gives $a_1 - a_2 = b_3 - b_4$.  Since $B(q , \theta )$ is a Sidon set, either $a_1 =a_2$, $b_3 = b_4$ or
$a_1 = b_3$, $a_2 = b_4$.

If $a_1 = a_2$ and $b_3 = b_4$, then $a_3 = a_4$ and the solution $(a_1,a_2,a_3,a_4)$ is trivial.  Suppose
$a_1 = b_3$ and $a_2 = b_4$.  This implies $b_3 \in A$, so both $p^j a_3$ and $a_3$ are in $A$.  This contradicts the way in which $A$ was constructed.
\end{proof}

\begin{lemma}\label{claim 2}
$|A| \geq \frac{q}{k} \left( 1 - \frac{1}{M} \right) - (p^4 - 1) (M-1)$.
\end{lemma}
\begin{proof}
In order to obtain a lower bound on $|A|$, we need to estimate the number of cycles of $\pi$ that are short.  For instance, if
all cycles of $\pi$ have length less than $k$, then $|A| = 0$.  For a cycle $\sigma$ of $\pi$ with length $mk  \geq Mk$, we delete at most
$m(k-1)$ elements from $B(q, \theta )$ and keep at least $m-1$ elements.

We estimate the number of cycles of length at most $Mk-1$.  Let $\sigma = ( b , pb , \dots , p^{e-1} b)$ be a cycle of $\pi$ of length
$e$ where $e \leq Mk - 1$.  The integer $e$ is the smallest positive integer such that $p^e b \equiv b ( \textup{mod}~q^2 - 1 )$.  This is the same
as saying that the order of $p$ in the multiplicative group of units $\integers_{n}^{*}$ is $e$ where
$n = \frac{ q^2 - 1}{ \textup{gcd}( b , q^2 - 1) }$.  Since
\[
p^{4t} - 1 = (p^{2t} - 1)( p^{2t} + 1) = (q^2 - 1)(p^{2t} +1 )
\]
we have $p^{4t} \equiv 1 ( \textup{mod}~q^2 - 1)$, so $e$ must divide $4t = 4r^i$.  Since $r$ is prime and $r \geq Mk$, $e$ cannot divide $r$, so $e$ must divide 4.  To count the number of cycles of $\pi$ with length at most $Mk-1$, it is enough to count the elements $x \in \integers_{q^2 - 1} \backslash \{0 \}$ such that $p^4 x \equiv x (\textup{mod}~q^2 - 1)$.  This follows from the fact that if $e \in \{1,2 \}$ and $p^e x \equiv x ( \textup{mod}~q^2 - 1)$, then
$p^4 x \equiv x ( \textup{mod}~q^2 - 1)$.  The number of solutions to this congruence is
$\textup{gcd}(p^4 - 1 , q^2 - 1) \leq p^4 - 1$.  Therefore, there are at most $p^4 - 1$ cycles of $\pi$ of length at most $Mk-1$.
For a cycle of length at least $Mk$, the proportion of elements of the cycle that are put into $A$ is at least
$\frac{ M - 1}{Mk}$ (the function $f(x) = \frac{x-1}{xk}$ is increasing provided $k > 0$).
Since $| B(q , \theta ) | = q$,
\[
|A|  \geq  \left( q - ( p^4 - 1) Mk \right) \left( \frac{M-1}{Mk} \right) = \frac{q}{k} \left( 1 - \frac{1}{M} \right) - (p^4 - 1)(M - 1).
\]
\end{proof}

Theorem~\ref{weak construction} follows from Lemmas~\ref{claim 1} and \ref{claim 2}.

%%%%%%%%%%%%%

\section{Concluding Remarks}

The most important open problem concerning $k$-fold Sidon sets is an answer to Conjecture~\ref{LV conjecture}.
The case $k=3$ is particularly interesting.  A 3-fold Sidon set $A \subset [N]$ with $|A| \geq cN^{1/2}$ is known to imply the existence of a graph with $c_1 N$ vertices, $c_2 N^{3/2}$ edges, and every edge is in exactly one cycle of length four \cite{TV}.

 Another problem is to determine the maximum size of a 2-fold Sidon set in $\mathbb{Z}_N$ or $[N]$.  Let
$S_k(N)$ be the maximum size of a $k$-fold Sidon set in $\mathbb{Z}_N$.
For any integer $t \geq 1$, there are 2-fold Sidon sets $A \subset \mathbb{Z}_N$, $N = 2^{2^{t+1}} + 2^{2^t} + 1$, with $|A| \geq \frac{1}{2}N^{1/2} - 3$ (see \cite{LV}).  Theorem~\ref{k ub} gives an upper bound of $(N/2)^{1/2} + O(N^{1/4})$ so
\[
\frac{1}{2} \leq \limsup_{N \rightarrow \infty} \frac{ S_2 (N) }{N^{1/2} } \leq \frac{1}{2^{1/2} }.
\]
It would be interesting to determine the above limit.  In the case of Sidon sets, we have
$\limsup_{N \rightarrow \infty} \frac{ S_1 (N) }{N^{1/2}} = 1$ by \cite{ET} and \cite{S}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{A}
M.\ Axenovich,
personal communication.

\bibitem{BC}
R.\ C.\ Bose, S.\ Chowla,
{\em Theorems in the additive theory of numbers},
Comment. Math. Helv. {\bf 37} (1962/1963), 141-147.

\bibitem{C}
J.\ Cilleruelo,
{\em Sidon sets in $\mathbb{N}^d$},
J. Combin. Theory, Series A {\bf 117} (2010) 857-871.

\bibitem{E}
P.\ Erd\H{o}s,
{\em A survey of problems in combinatorial number theory},
Annals of Discrete Mathematics {\bf 6} (1980), 89-115.

\bibitem{ET}
P.\ Erd\H{o}s, P.\ Tur\'{a}n,
{\em On a problem of Sidon in additive number theory, and on some related results},
Journal of the London Mathematical Society, 16 (1941).

\bibitem{LV}
F.\ Lazebnik, J. Verstra\"{e}te,
{\em On hypergraphs of girth five},
Electronic J. of Combinatorics, {\bf 10}, (2003), \#R25.

\bibitem{L}
B.\ Lindstr\"{o}m,
{\em A translate of Bose-Chowla $B_2$-sets},
Studia Sc.\ Math.\ Hungar., {\bf 36}, (2000), 331-333.

\bibitem{OB}
K.\ O'Bryant,
{\em A complete annotated bibliography of work related to Sidon sequences},
Electronic J. of Combinatorics {\bf DS 11} (2004).

\bibitem{R}
I.\ Ruzsa,
{\em Solving a linear equation in a set of integers I},
Acta Arith. {\bf 65} 3 (1993), 259-282.

\bibitem{S}
J.\ Singer,
{\em A theorem in finite projective geometry and some applications to number theory},
Trans.\ Amer.\ Math.\ Soc.\ 43 (1938), 377-385.

\bibitem{TV}
C.\ Timmons, J.\ Verstra\"{e}te,
{\em A counterexample to sparse removal}, submitted. \arxiv{1312.2994}.

\end{thebibliography}

\end{document}
