\documentclass[12pt]{article}
\usepackage{latexsym} 
\usepackage{amsfonts} 
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9 

\usepackage{amsmath} 
\usepackage{amssymb} 
\usepackage{verbatim} 
\usepackage{amscd} 
\usepackage{theorem} 

\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}


\def\sbeq{\subseteq}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\E{\mathbb {E}}    
\def\e{\varepsilon}
\def\l{\ell}
\def\I{{\cal I}}
\def\S{{\cal S}}
\def\P{{\mathbb P}}
\def\h{\hat}
\def\d{\delta}
\def\o{\omega}
\def\({\big (}
\def\){\big )}
\def\g{\gamma}
\def\a{\alpha}

\begin{document}

\begin{center}
{\bf MULTIPLE SET ADDITION IN $\Z_p$}
\vskip 20pt
{\bf Tomasz Schoen\footnote{Research partially supported by KBN Grant 2 P03A 007 24}}\\
{\smallit Department of Discrete Mathematics, Adam Mickiewicz University,
Pozna\'n, Poland}\\
{\tt schoen@amu.edu.pl}
\end{center}
\vskip 30pt
\centerline{\smallit Received: 2/22/03, Revised: 10/6/03,
Accepted: 11/1/03, Published: 11/5/03}
\vskip 30pt 

\centerline{\bf Abstract}

\noindent It is shown that there exists an absolute constant $H$ such that 
for every $h>H$, every prime  $p$, and every set $A\sbeq \Z_p$ such that  $10\le |A|\le
p(\ln h)^{1/2}/(9h^{9/4})$ and $|hA|\le {h^{3/2}|A|}/{(8(\ln h)^{1/2})}$,
the set  $A$ is contained in an arithmetic progression modulo $p$ of cardinality 
 $ \max_{1\le j\le h-1} \frac{|hA|-P_j(|A|)}{h-j}+1$,  
where $P_j(n)=\frac{(j+1)j}{2}n-j^2+1$.
This result can be viewed as a generalization of  Freiman's ``2.4-{theorem}''.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC
JOURNAL OF COMBINATORIAL NUMBER
THEORY \smalltt 3 (2003), \#A17\hfill}

\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt 

\section*{\normalsize 1. Introduction}

For a  non-empty subset $A$ of an additively written group and an integer $h\ge 2$ the $h$-sumset of $A$
is defined as   
$$hA=\{a_1+\dots +a_h: a_1,\dots, a_h\in A\};$$
and by a sumset we mean a 2-sumset of $A$.
The following well-known ``2.4-{theorem}''  of Freiman \cite{f} describes the structure of 
sets $A\subseteq { {\Z}_p}$ with small sumsets.



\noindent {\bf Theorem 1 (Freiman).} {\em Let  $A$, $|A|\le p/35$, be a subset of 
$\Z_p$ for some prime  $p$. If 
$$|2A|\le 2.4|A|-3,$$ 
then $A$ is contained in an arithmetic progression
of ${\mathbb Z_p}$ with $|2A|-|A|+1$ terms.} 



\noindent  Freiman's  proof goes  roughly as follows. 
Since $A$ has a small sumset, the characteristic function of  $A$
has a large non-zero Fourier coefficient.  Hence 
$A$ is dense in  some arithmetic progression  $P\sbeq \Z_p$
of length $(p-1)/2$. The set $A'=A\cap P$ is 
isomorphic (in the sense of Freiman) to a subset of integers,
hence one can apply to $A'$ Freiman's additive theorem for integers,
and infer  that $A'$ is contained in an arithmetic progression  of cardinality 
$|2A'|-|A'|+1$.  As a last step one   shows  that $A'=A$, otherwise we would have
$|2A|>2.4|A|-3$.



\noindent In this note we generalize Freiman's theorem  to $h$ summands, provided $h$ is 
large. Our main result is as follows. 



\noindent {\bf Theorem 2.} {\em There is an absolute constant $H$ such that 
for every $h>H$, every prime  $p$, and every $A\subseteq \Z_p$ such that 
  $10\le |A|\le \frac{p(\ln h)^{1/2}}{9h^{9/4}}$  and
$$|hA|\le \frac{h^{3/2}}{8(\ln h)^{1/2}}|A|,$$  
the set $A$ is contained in an arithmetic progression
 of cardinality  $ \max_{1\le j\le h-1} \frac{|hA|-P_j(|A|)}{h-j}+1,$  
where $P_j(n)=\frac{(j+1)j}{2}n-j^2+1.$} 




\noindent Our approach follows the main idea of Freiman's proof. 
First we observe that the absolute value of  some
 Fourier coefficient of the characteristic function of  $A$ is very close to $|A|.$
We use this fact to show the existence of a large subset 
$A'$ of $A$ contained in an arithmetic progression of cardinality roughly $p(\ln h/h)^{1/2}$.
Then we apply  a result of Lev (Theorem 3 below) 
to $A'$ and some $h_0>(h/\ln h)^{1/2}$ to prove that $A'$ is, in fact, contained in a
much shorter arithmetic progression. Finally 
we employ a well-known theorem of Cauchy-Davenport  to infer that $A'=A$.

\noindent In order for our method to work 
we have to impose some restrictions on the sizes of  
$A$ and  $hA$. Thus, we  assume that $h>H$, where the  value of an absolute constant $H$
can be explicitly computed.  In our result Freiman's  constant ``2.4'' 
is replaced by  ``$h^{3/2}/4(\ln h)^{1/2}$'', although one can expect that,
as in Theorem 3, 
the assertion holds for each $A$ with  $|hA|\le \frac{(h+1)h}{2}|A|-h^2$.


\vskip 30pt 


\section*{\normalsize 2. Auxiliary results}

\noindent  In this section we recall some theorems and definitions used in the proof 
of our main result.
First we state  a consequence of \cite[Corollary 1]{l} . Here and below $L(A)$ denotes the cardinality of the shortest arithmetic progression containing $A$. 



\noindent {\bf Theorem 3 (Lev \cite{l}).} {\em Let $h\ge 2$ and  $A$ be a finite subset of $\Z,~
|A|\ge 2$ such that
$|hA|\le \frac{(h+1)h}{2}|A|-h^2$. Then 
$$L(A) \le \max_{1\le j\le h-1} \frac{|hA|-P_j(|A|)}{h-j}+1,$$  
where $P_j(n)=\frac{(j+1)j}{2}n-j^2+1.$} 

\bigskip
\noindent {\sl  Remark 1.} The estimate of Theorem 3 is tight, as shows  the following   
example given in \cite{l}.  Let $\l\ge n-1, ~A=\{0,\dots,n-2\}\cup \{\l\}$
and put $k=\lceil \frac{\l-1}{n-2}\rceil -1.$
If $h>\frac{\l-1}{n-2}$ then it is easily seen that $|hA|=P_k(n)+(h-k)l<P_h(n)$
and
  $$ \max_{1\le j\le h-1} \frac{|hA|-P_j(n)}{h-j}+1 = \l+1=L(A), $$
maximum is attained for $j=k$.


\noindent {\sl  Remark 2.} Note that under the assumptions of  Theorem 3 we have  
$$L(A)\le \frac{2|hA|}{h}+1.$$ Indeed, suppose that the maximum is attained for $j_0.$ If 
$j_0\le h/2$ then the inequality follows immediately. Assume that $j_0>h/2$ and
$$\frac{|hA|-P_{j_0}(|A|)}{h-j_0}> \frac{2|hA|}{h}.$$
Then we  have
$$|hA|>\frac{h}{2j_0-h}P_{j_0}(|A|)\ge \min_{h/2<j\le h}  
\frac{h}{2j-h}P_{j}(|A|).$$
Since $\frac{h}{2j-h}P_{j}(n)$ is a strictly decreasing function of $j$ it follows that
$$|hA|>P_{h}(|A|)>\frac{(h+1)h}{2}|A|-h^2,$$
contradicting the assumptions of Theorem 3.



\noindent {\bf Theorem  4 (Cauchy-Davenport).} {\em Let $p$ be a prime number
and let  $A$ be a nonempty subset of $\Z_p.$ Then, for every integer $h\ge 2$,
$$|hA|\ge \min (p, h|A|-h+1).$$}



\noindent We will also need the following  
straightforward consequence of Theorem 4.



\noindent {\bf Corollary 1.} {\em Let $p$ be a prime number
and let  $A$ be a nonempty subset of $\Z_p$ such that $|hA|<p.$ 
Then, for every integers  $h\ge h_1 \ge 2$,
$$|h_1 A|< \lf h/h_1 \rf ^{-1}|hA|+1.$$}

\noindent {\it Proof.} By Cauchy-Davenport theorem, we have
\begin{eqnarray*}
|hA|\ge |\lf h/h_1 \rf (h_1A)|\ge {\lf h/h_1 \rf} |h_1A|-{\lf h/h_1
\rf}+1.
\end{eqnarray*}
\vskip -34pt
\hfill $\Box$



\noindent Let $G$ and $H$ be abelian groups and let $A\sbeq G$ and $B\sbeq H$.  
We say that a mapping $\phi: A\rightarrow B$ is a Freiman's  isomorphism of order $h$ 
( briefly, $F_h$-isomorphism), if for every $a_1,\dots,a_h,a'_1,\dots, a'_h\in A$ the equation
$$a_1+\dots+a_h=a'_1+\dots+ a'_h$$
holds if and only if
$$\phi(a_1)+\dots+\phi(a_h)=\phi(a'_1)+\dots+ \phi(a'_h)$$
holds. In particular  $F_h$-isomorphisms preserve  the  size of $h$-sumsets.

\vskip 20pt

\section*{\normalsize 3. Proof of the main theorem}

 For a set $S\sbeq \Z_p$ let 
$\{\h S(r)\}_{r\in \Z_p}$ denote the Fourier coefficients of the  indicator function of 
 $S~$ ($\, \h S(r)=\sum_{s\in S}e^{2\pi irs/p}\, $).
It is easy to see that $|\h S(0)|=|S|.$ We recall also Parseval formula 
\begin{equation*}
\sum_{r=0}^{p-1}|\h S(r)|^2=|S|p.
\end{equation*}
By the definition all sums $a_1+\dots+a_h,~ a_1,\dots, a_h\in A$ belong to
the set $hA$, hence
$$\sum_{r=0}^{p-1}\h A(r)^h \hat{ (hA)}(-r)=|A|^hp$$
and 
$$\sum_{r=1}^{p-1}\h A(r)^h \hat{(hA)}(-r)=|A|^hp-|A|^h|hA|\ge |A|^hp/2.$$
Put $M\!=\!\max_{r\not=0}|\h A(r)|$. By Cauchy-Schwarz
inequality and  Parseval formula
 we have
\begin{eqnarray}
|A|^hp/2&\le& \sum_{r=1}^{p-1}|\h A(r)|^h |\hat{(hA)}(-r)|
        \le M^{h-1} \sum_{r=1}^{p-1}|\h A(r)|| \hat{(hA)}(-r)|\nonumber \\
        &\le& M^{h-1} \big (\sum_{r=1}^{p-1}|\h A(r)|^2\big )^{1/2} 
        \big (\sum_{r=1}^{p-1}| \hat{(hA)}(-r)|^2\big )^{1/2}\nonumber\\
        &<& M^{h-1}|A|^{1/2}|hA|^{1/2}p.\nonumber
\end{eqnarray}
Thus,
\begin{eqnarray}\label{m}
M &>& \Big (\frac{|A|}{4|hA|}\Big )^{\frac{1}{2(h-1)}}|A|\ge
    (h^{-3/2} )^{\frac{1}{2(h-1)}}|A|\nonumber \\
  &=&\exp \Big (-\frac{3}{4}\frac{\ln h}{h-1}\Big )|A|>\Big (1-\frac{3}{4}\frac{\ln h}{h-1}
\Big )|A|\nonumber\\
&>& \Big (1-\frac{\ln h}{h}\Big )|A|.
\end{eqnarray}
Let $r_0\in \Z_p\setminus \{0\}$ be an element with 
$|\h A(r_0)|=M.$ Put $\g=\arg \h A(r_0),~ \a=\arccos \Big (1-\frac{2\ln h}{h}\Big ),$ so that 
$\a \le \pi \big (\frac{\ln h}{2h}\big )^{1/2}  .$ Define
$$B=\big \{r_0 a\colon a\in A \text{ and } d \big (\g- 2\pi \frac {(r_0a)_p}{p}\big ) \le \a \big \},$$
where $(r_0a)_p$ stands for the least non-negative integer congruent to $r_0a$ modulo $p$
and $d(x)$ denotes the distance of $x$ from the nearest number of the form $2\pi k,~k\in \Z$. 
It follows that
$$|\h A(r_0)|\le |B|+(\cos\a)(|A|-|B|),$$
and by (\ref{m})
\begin{equation}\label{a}
|B|\ge \frac{1-\frac{\ln h}{h}-\cos \a}{1-\cos \a}|A|
=|A|/2.
\end{equation}
Observe that  $B$ is  $F_{h_0}$-isomorphic to a subset of 
integers, where $ h_0=\lf 2\pi/\a \rf.$ Then $  h_0\ge 
2 \big (\frac{ h}{\ln h}\big )^{1/2}$ and by 
 Corollary 1, (\ref{m}), and (\ref{a}), we get
\begin{eqnarray}
|h_0B|&\le& \frac{|hB|}{\lf h/h_0 \rf }+1\le \frac{2h_0|hA|}{h}+1 
        \le \frac{h_0h^{1/2}|A|}{4(\ln h)^{1/2}}+1\nonumber \\
&\le& \frac{h_0h^{1/2}|B|}{2(\ln h)^{1/2}}+1\le  \frac{h^2_0}{4}|B|+1\nonumber\\
        &<& \frac{(h_0+1)h_0|B|}{2}-h^2_0+1\nonumber.
\end{eqnarray}
Thus, one can apply Theorem~3 to the set $B$, so that
$B$ is contained in an arithmetic progression in $\Z_p$ of 
size 
\begin{eqnarray}\label{s}
\max_{1\le j\le h_0-1} \frac{|h_0 B|-P_j(|B|)}{h_0-j}+1&\le& \frac{2|h_0B|}{h_0}+1\le 
\frac{2|hB|}{h_0 \lf h/h_0 \rf}+2\nonumber\\
&\le& \frac{4|h A|}{h}+2\le \frac{h^{1/2}|A|}{2(\ln h)^{1/2}}+2\nonumber\\
&\le& \frac{p}{2h^{7/4}}.
\end{eqnarray}

\noindent Let $A_1$ be any  subset of $A$ of the maximum cardinality, contained in an
arithmetic progression of cardinality $\lf p/h \rf$. From (\ref{a})
and (\ref{s}) it follows that $|A_1|\ge |A|/2$. 
An argument analogous to that used in (\ref{s}) 
shows that $A_1$ is contained in an arithmetic  progression of size  at most
$p/(2h^{7/4}).$ 
Without loss of generality we may assume that $A_1$ is a subset of the arithmetic  progression 
 with the common difference
$1$ centered at $0$ that means $\| a\| \le  p/(4h^{7/4})$ for every $a\in A_1,$
where $\| x\| =\min\big ((x)_p, (p-x)_p\big ).$
If  $a_0\in A\setminus A_1,$ then  
$$\| ka_0\| \le \frac{p}{2h},$$
for some $k\in \N$. Let $k$ be the smallest number with this property.
Observe that if $k\le h^{3/4},$ then for every $a\in A_1$
$$\|ka\|\le k\|a\|\le h^{3/4}\frac{p}{4h^{7/4}}< \frac{p}{2h},$$
so the set $A_1\cup\{a_0\}$ is contained in an arithmetic progression
of size at most $p/h$ and the common difference $k^{-1}$ (the multiplicative
inverse of $k$ in $\Z_p$), contradicting the maximality of $A_1.$
Hence we may assume that $k \ge h^{3/4}$. Put $\l=\lf h^{3/4}\rf$.
Then, the elements $a_0,2a_0,\dots,\l a_0$ are well-spaced:
$$\| ia_0-ja_0\| =\| (i-j)a_0\| \ge \frac{p}{2h},$$
for all $i\not= j, ~i,j\in \{1,\dots,\l \}$.
Consequently,  the sets
\begin{equation}\label{h}
\l A_1, a_0+(\l -1)A_1, \dots, (\l-1) a_0+ A_1
\end{equation}
are pairwise disjoint. 
Indeed, if  $(ia_0+(\l-i)A_1)\cap(ja_0+(\l-j)A_1)
\not= \emptyset$  for some $i\not= j, ~i,j\in \{0,\dots,\l-1 \},$
then there are elements $a_1,\dots ,a_{\l-i},b_1,\dots ,b_{\l-j}\in A_1$ such that 
$$ia_0+a_1+\dots +a_{\l-i}=ja_0+b_1+\dots +b_{\l-j},$$
so that we would have 
\begin{eqnarray*}
\| ja_0-ia_0\| &=& \|  a_1+\dots +a_{\l-i}-b_1-\dots -b_{\l-j}\|\\
& \le &  \|a_1\|+\dots +\|a_{\l-i}\|+\|b_1\|+\dots +\|b_{\l-j}\| \\
&\le& \frac{p}{2h}.
\end{eqnarray*}
Now by (\ref{h}) and Theorem~4
\begin{eqnarray}
|hA|&\ge& |\l A_1|+|a_0+(\l -1)A_1|+\dots +|(\l-1)a_0+ A_1| \nonumber \\ 
      &\ge& \big (\l |A_1|-\l+1\big ) +\big ((\l-1)|A_1|-\l+2\big ) +\dots + | A_1|\nonumber \\
      &>& \l^2|A|/4-\l^2/2>|hA|\nonumber,
\end{eqnarray}
a contradiction. Hence $A$ is contained in an arithmetic 
progression of cardinality $\lf p/h \rf$ in $\Z_p$ and is $F_h$-isomorphic to a
subset of integers. Applying Theorem 3 we infer that
$A$ is contained in  an arithmetic progression of
size $\max_{1\le j\le h-1} \frac{|hA|-P_j(|A|)}{h-j}+1,$  which completes the proof.
\hfill $\Box$


\noindent{\sl Remark.} Using a rectification principle from \cite{blr}, 
one can prove that the bound for $L(A)$ similar to that given in Theorem~3
holds also for $A\sbeq \Z_p$, provided we put  much more restrictive
bounds on the size of $A$.


\begin{thebibliography}{99}
\footnotesize

\bibitem{blr}
{\sc Y.~Bilu, V.~F.~Lev and I.~Z.~Ruzsa,} {\em Rectification principles in 
additive number theory,} Discrete Computational Geometry 19 (1998), 343--353. 
\bibitem{f}
{\sc G.~Freiman,} ``Foundations of a structural theory of set addition,''
 {\it Translations of Math.
Monographs} {\bf 37} (1973), American Math. Soc., Providence. 
\bibitem{l}
{\sc V.~F.~Lev,} {\em Structure theorem for multiple addition and 
the Frobenius problem,} Journal of Number Theory 58 (1996), 79--88. 
\end{thebibliography}


\end{document}

coulburn, ling