% 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 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}