Olson's theorem for cyclic groups
Van Vu
Let $n$ be a large number. A subset $A$ of $Z_n$ is complete if $S_A = Z_n$, where $S_A$ is the collection of the subset sums of $A$. Olson proved that if $n$ is prime and $|A|> 2n^{1/2} $, then $S_A$ is complete. We show that a similar result for the case when $n$ is a composite number, using a different approach.
math0506483.tex
  \documentstyle[amssymb,amsfonts]{amsart}

% \usepackage{amsmath}
% \usepackage{amsthm}
% \usepackage{amsfonts}


% \usepackage{amssymb}
\newcommand{\norm}[1]{ \left|  #1 \right| }
\newcommand{\Norm}[1]{ \left\|  #1 \right\| }
\newcommand{\ifof}{\Leftrightarrow}
\newcommand{\set}[1]{ \left\{ #1 \right\} }
\newcommand{\floor}[1]{\lfloor #1 \rfloor }




\def\Vol{\hbox{\rm Vol}}
\def\Var{\hbox{\bf Var}}
\def\Conv{\hbox{ Conv}}
\def\R{{\hbox{\bf R}}}
\def\C{{\hbox{\bf C}}}
\def\Q{{\hbox{\bf Q}}}
\def\G{{\hbox{\bf G}}}
\def\P{{\hbox{\bf P}}}
\def\E{{\hbox{\bf E}}}
\def\v{{\hbox{\bf v}}}
\def\f{{\overline{f}}}
\font \roman = cmr10 at 10 true pt
\def\x{{\hbox{\roman x}}}
\def\y{{\hbox{\roman y}}}
\def\z{{\hbox{\roman z}}}
\def\Ecal{{\cal E}}
\def\Itil{{\tilde I}}
\def\Otil{{\tilde O}}
\renewcommand{\H}{\mbox{{\bf H}}}
\def\T{{\hbox{\bf T}}}
\def\ts{{T_\sigma}}
\def\Ts{{\T_\sigma}}
\def\sd{{\rho}}
\def\se{{\sqrt{\epsilon}}}
\def\sN{{\sqrt{N}}}
\def\tsd{{T_\sd}}
\def\tsda{{T_\sd^1}}
\def\tsdb{{T_\sd^2}}
\def\tsdc{{T_\sd^3}}
\def\tsdi{{T_\sd^i}}
\def\Tsd{{\T_\sd}}
\def\Tsdp{{\T'_\sd}}
\def\fant{{\widetilde{Fan}}}
\def\mult{{\mu}}

\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\barray{\begin{eqnarray*}}
\def\earray{\end{eqnarray*}}
\def\be#1{ \begin{equation}\label{#1} }

\def\bas{\begin{align*}}
\def\eas{\end{align*}}
\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}

\def\diam{{\hbox{\roman diam}}}
\def\supp{{\hbox{\roman supp}}}
\def\dim{{\hbox{\roman dim}}}
\def\codim{{\hbox{\roman codim}}}
\def\Gr{{\hbox{\roman Gr}}}
\def\M{{\hbox{\roman M}}}
\def\dimsup{{\roman \overline{dim}}}
\def\dist{{\hbox{\roman dist}}}
\def\rp{{r^\prime}}
\def\rpt{{\tilde r^\prime}}
\newcommand{\qtil}{\tilde{q}}
\newcommand{\rtil}{\tilde{r}}
\def\kp{{k^\prime}}
\def\kt{{\tilde{k}}}
\def\et{{\tilde{E}}}
\def\qp{{q^\prime}}
\def\qpt{{\tilde q^\prime}}
\def\ap{{a^\prime}}
\def\bp{{b^\prime}}
\def\chik{{\chi_k}}
\def\chikp{{\tilde \chi_\kp}}
\def\chikt{{\tilde \chi_\kt}}
\def\Rd{{\hbox{\bf R}_d}}
\def\Z{{\hbox{\bf Z}}}
\def\U{{\hbox{\bf U}}}
\def\A{{\hbox{\bf A}}}
\def\eps{\varepsilon}
% \def\lesssim{<_\sim}
\newenvironment{proof}{\noindent {\bf Proof} }{\endprf\par}
\def \endprf{\hfill  {\vrule height6pt width6pt depth0pt}\medskip}
\def\emph#1{{\it #1}}
\def\textbf#1{{\bf #1}}
\def\g{{\frak g}}
\def\Span{\hbox{ \rm Span} \,\,\, }
\def\smd{\hbox{smd}}
\def\Ba{{\mathbf a}}
\def\Bb{{\mathbf b}}
\def\Bc{{\mathbf c}}
\def\Bd{{\mathbf d}}
\def\Be{{\mathbf e}}
\def\Bf{{\mathbf f}}
\def\Bg{{\mathbf g}}
\def\Bh{{\mathbf h}}
\def\Bi{{\mathbf i}}
\def\Bj{{\mathbf j}}
\def\Bk{{\mathbf k}}
\def\Bl{{\mathbf l}}
\def\Bm{{\mathbf m}}
\def\Bn{{\mathbf n}}
\def\Bo{{\mathbf o}}
\def\Bp{{\mathbf p}}
\def\Bq{{\mathbf q}}
\def\Bs{{\mathbf s}}
\def\Bt{{\mathbf t}}
\def\Bu{{\mathbf u}}
\def\Bv{{\mathbf v}}
\def\Bw{{\mathbf w}}
\def\Bx{{\mathbf x}}
\def\By{{\mathbf y}}
\def\Bz{{\mathbf z}}

%

\def\BA{{\mathbf A}}
\def\BB{{\mathbf B}}
\def\BC{{\mathbf C}}
\def\BD{{\mathbf D}}
\def\BE{{\mathbf E}}
\def\BF{{\mathbf F}}
\def\BG{{\mathbf G}}
\def\BH{{\mathbf H}}
\def\BI{{\mathbf I}}
\def\BJ{{\mathbf J}}
\def\BK{{\mathbf K}}
\def\BL{{\mathbf L}}
\def\BM{{\mathbf M}}
\def\BN{{\mathbf N}}
\def\BO{{\mathbf O}}
\def\BP{{\mathbf P}}
\def\BQ{{\mathbf Q}}
\def\BS{{\mathbf S}}
\def\BT{{\mathbf T}}
\def\BU{{\mathbf U}}
\def\BV{{\mathbf V}}
\def\BW{{\mathbf W}}
\def\BX{{\mathbf X}}
\def\BY{{\mathbf Y}}
\def\BZ{{\mathbf Z}}
\def\Pr{{\mathbf P }}

%cal letter

\def\CA{{\mathcal A}}
\def\CB{{\mathcal B}}
\def\CC{{\mathcal C}}
\def\CD{{\mathcal D}}
\def\CE{{\mathcal E}}
\def\CF{{\mathcal F}}
\def\CG{{\mathcal G}}
\def\CH{{\mathcal H}}
\def\CI{{\mathcal I}}
\def\CJ{{\mathcal J}}
\def\CK{{\mathcal K}}
\def\CL{{\mathcal L}}
\def\CM{{\mathcal M}}
\def\CN{{\mathcal N}}
\def\CO{{\mathcal O}}
\def\CP{{\mathcal P}}
\def\CQ{{\mathcal Q}}
\def\CS{{\mathcal S}}
\def\CT{{\mathcal T}}
\def\CU{{\mathcal U}}
\def\CV{{\mathcal V}}
\def\CW{{\mathcal W}}
\def\CX{{\mathcal X}}
\def\CY{{\mathcal Y}}
\def\CZ{{\mathcal Z}}

%number theory

\def\BBN{{\mathbb N}}
\def\BBQ {{\mathbb Q}}
\def\BBI {{\mathbb I}}
\def\BBR {{\mathbb R}}
\def\BBZ {{\mathbb Z}}

% tilde

\def\ta{{\tilde a}}
\def\tb{{\tilde b}}
\def\tc{{\tilde c}}
\def\td{{\tilde d}}
\def\te{{\tilde e}}
\def\tf{{\tilde f}}
\def\tg{{\tilde g}}
\def\th{{\tilde h}}
\def\ti{{\tilde i}}
\def\tj{{\tilde j}}
\def\tk{{\tilde k}}
\def\tl{{\tilde l}}
\def\tm{{\tilde m}}
\def\tn{{\tilde n}}
\def\to{{\tilde o}}
\def\tp{{\tilde p}}
\def\tq{{\tilde q}}
\def\ts{{\tilde s}}
\def\tt{{\tilde t}}
\def\tu{{\tilde u}}
\def\tv{{\tilde v}}
\def\tw{{\tilde w}}
\def\tx{{\tilde x}}
\def\ty{{\tilde y}}
\def\tz{{\tilde z}}
\def\ep{{\epsilon}}
% special
\def\rfl {\rfloor}
\def\lfl {\lfloor}
\def\hs{\hfill $\square$}
\def\dd{\partial}
\def\PE{ P. Erd\H os}
\def\mod {\hbox {\rm mod}}
\def\Disc {\hbox {Disc} \,\,}
\def \small {\scriptsize}


% \swapnumbers
% \pagestyle{headings}
\parindent = 0 pt
\parskip = 12 pt

\theoremstyle{plain}
  \newtheorem{theorem}[subsection]{Theorem}
  \newtheorem{conjecture}[subsection]{Conjecture}
  \newtheorem{problem}[subsection]{Problem}
  \newtheorem{assumption}[subsection]{Assumption}
  \newtheorem{heuristic}[subsection]{Heuristic}
  \newtheorem{proposition}[subsection]{Proposition}
  \newtheorem{fact}[subsection]{Fact}
  \newtheorem{lemma}[subsection]{Lemma}
  \newtheorem{cor}[subsection]{Corollary}
   \newtheorem{claim}[subsection]{Claim}

\theoremstyle{remark}
  \newtheorem{remark}[subsection]{Remark}
  \newtheorem{remarks}[subsection]{Remarks}

\theoremstyle{definition}
  \newtheorem{definition}[subsection]{Definition}

\include{psfig}

\begin{document}

\title{  Olson's theorem for cyclic groups}

%\date{Note}
\author{  Van Vu}
\address{Department of Mathematics, UCSD, La Jolla, CA 92093-0112}
\email{vanvu@@ucsd.edu}

\thanks{V. Vu is an A. Sloan  Fellow and is supported by an NSF Career Grant.}




\begin{abstract} Let $n$ be a large number. A subset $A$ of $Z_n$
is complete if $S_A = Z_n$, where $S_A$ is the collection of the
subset sums of $A$. Olson proved that if $n$ is prime and $|A|>
2n^{1/2} $,  then $S_A$ is complete. We show that  a similar
result for the case when $n$ is a composite number, using a
different approach.


\end{abstract}

\maketitle

\section {Introduction}

Let $G$ be an additive  group. For a subset $A \subset G$, we
denote by $S_A$ the collection of the subset sums of $A$

$$S_A =\{ \sum_{x \in B} x | B \subset A, |B| < \infty \}. $$

Following \cite{erd}, we  say that $A$ is {\it complete} (with
respect to $G$) if $S_A=G$; in other words, every element of $G$
can be represented as a sum of different elements of $A$.


In this short note, we investigate the case when $G=Z_n$, the
cyclic group of order $n$,  where $n$ is a large positive integer.

A well-known result of Olson \cite{Olson}, answering a question of
Erd\"os and Heilbronn, shows that if $n$ is a prime and $|A| >
2n^{1/2}$, then $A$ is complete.


\begin{theorem} \label{theo:olson}  If $n$ is a prime and $A$ is a
subset of $Z_n$ with cardinality larger than $2n^{1/2}$, then $A$
is complete.
\end{theorem}


The bound is sharp. To see this observe that if the sum of the
elements in $A$ (viewed as integers between $1$ and $n-1$) is less
than $n$, then $A$ is not complete.

We  extend this result for the case when $n$ is a composite
number. Our result is



\begin{theorem} \label{theo:main}  There is a constant $C$ such that the following holds.
Let $n$ be a  sufficiently large positive integer  and  $A$ be a
subset of  $Z_n$, where $|A| \ge Cn^{1/2}$ and the elements of $A$
are co-primes with $n$. Then  $A$ is complete.
\end{theorem}





\begin{remark} \label{remark:diderich} The assumption that the
elements of $A$ are co-primes with $n$ is necessary. For instance,
if $n$ is divisible by 3 then it is possible to have  an
incomplete set of size $n/3$. Without the co-prime assumption, the
problem of bounding $|A|$ is known as Diderrich's problem. It has
been proved that the sharp bound for $|A|$ is $p+n/p-2$, where $p$
is the smallest prime divisor of $n$ (see \cite{Lipkin} for the
case of cyclic groups and \cite {Gao} for the general case of
arbitrary abelian groups).
\end{remark}





In the current proof, the constant $C$ in Theorem \ref{theo:main}
is fairly large. However, we believe that the constant $C$ in
Theorem \ref{theo:main} can be set to (the asymptotically optimal
value) $2+o(1)$.


It seems to be of interest  to investigate the general case. Given
a finite abelian group $G$, one would like to find a parameter
$f(G)$  so that if $A$ is a set of at least $f(G)$ primitive
elements, then $A$ is complete. This problem can be seen as a
variant of Diderrich's problem. On the other hand, by comparing
the bounds in Theorem \ref{theo:main} and Remark
\ref{remark:diderich}, it is plausible that the answer would be
quite different. In fact, we think  that the nature of this
problem is closer  to  that of Olson's than to Diderrich's.


\vskip2mm

{\bf Notation.}  In the whole paper, we understand that the
elements of a set are different. If there are possible repetitions
we use the phrase multi-set instead.


\section{Lemmas}


\noindent For a set $A$ of integers and a positive integer $l \le
|A|$, let $l^{\ast}A$ denote the set of sums of $l$ different
elements of $A$

$$l^{\ast}A = \{a_1+ \dots a_l| a_i \in A, a_i \neq a_j\}. $$



\noindent  Denote by $[n]$ the set $\{1,2, \dots, n\}$. In
\cite{szemvu1}, Szemer\'edi and the author proved the following
theorem.

\begin{theorem} \label {theo:szemvu1} There are positive constants $C$
and $c$ such that the following holds. Let $l$, $n$ be positive
integers and  $A$ be a subset of $[n]$ such that $|A|/2 \ge l$ and
$l|A| \ge Cn$. Then $l^{\ast}A$ contains an arithmetic progression
of length $cl|A|$.
\end{theorem}





\noindent Since $l^{\ast}A \subset S_A$, this theorem implies the
following corollary.

\begin{cor} \label {cor:szemvu1} There is a positive constant $C$
such that the following holds. For every sufficiently large
integer $n$ and a subset $A$ of $[n]$ of cardinality at least $C
n^{1/2}$, $S_A$ contains an arithmetic progression of length $n$.
\end{cor}


\begin{remark} \label{remark:FS} The bounds on both $|A|$ and the length of the arithmetic progression is
sharp, up to constant factors. Freiman \cite{Fre} and
 S\'ark\"ozy \cite{Sar}, independently,  showed that  the same statement holds under the stronger assumption that
 $|A| \ge C \sqrt {n \log n}$.   \end{remark}




\noindent We also need the following simple lemma.

\begin{lemma} \label{lemma:lemma2} Let $n$ be a positive integer and  $A$ be a multi-set of
$n$  integers co-prime to $n$. Then $S_A$ contains every residue
modulo $n$.
\end{lemma}





{\bf \noindent Proof of Lemma \ref{lemma:lemma2}.} Assume that
$a_1, a_2, \dots , a_n$ are the elements of $A$. We are going to
prove, by induction, that $|S_{A_i}| \ge i$, where $A_i=\{a_1,
\dots, a_i \}$. The case $i=1$ is trivial. Assume that the
statement holds for $i-1$. Let $b_1, \dots, b_{i-1}$ be $i-1$
different elements (modulo $n$) of $S_{A_{i-1}}$. Since  the
statement is invariant under dilation,
 we can assume that $a_i=1$. Consider the elements


 $$b_1, \dots, b_{i-1}, 1, 1+ b_1, \dots, 1+ b_{i-1}. $$


 At least $i$ of the above must be different (modulo $n$) and this concludes
 the proof. \hs


 \section {Proof of Theorem \ref{theo:main}.} Assume that $A$ has
 at least
 $2 \lceil C  n^{1/2} \rceil $ elements, where $C$ is the
 constant in Corollary \ref{cor:szemvu1}. For convenience, we  think of the elements of $A$
 as  positive integers between one and $n-1$. We are going to
 prove that $S_A$  contains every residue modulo $n$.


 Let $A'$
be a subset of $A$ of $ \lceil Cn^{1/2} \rceil $ elements. Apply
Corollary \ref{cor:szemvu1} to $A'$ to get an arithmetic
progression $P'$ of length $n$. If the difference $d'$ of $P'$ is
co-prime to $n$, then $P'$ contains every residue modulo $n$ and
we are done. If $d'$ is not co-prime to $n$, set $d= \gcd (d',n)$.


Since the largest element in $S_{A'}$ is less than $Cn^{3/2}$, $d$
is less than $Cn^{1/2}$. The set $B= A \backslash A'$ has at least
$ \lceil Cn^{1/2} \rceil
> d $ elements, each of which is  co-prime to $n$ (and thus co-prime to $d$). By Lemma
\ref{lemma:lemma2}, we conclude that $S_{B'}$ contains every
residue modulo $d$.


The set $S_{A'} +S_{B}$ thus contains every residue modulo $n$.
But this set is clearly a subset of $S_A$, completing the proof.
\hs


%\section{Concluding remarks}

Notice that the proof requires that the elements of $B$ are
co-prime to $n$; but for $A'$, it is enough to assume that its
elements are non-zero modulo $n$.




{\it Acknowledgement.} We would like to thank T. Tao for reading
the manuscript.


\begin{thebibliography}{99}


\bibitem {erd} P. Erd\"os, On the representation of large
interges as sums of distinct summands taken from a fixed set, {\it
Acta. Arith.} 7 (1962) 345-354.

\bibitem {Fre} G. Freiman, New analytical results in subset-sum problem.
Combinatorics and algorithms (Jerusalem, 1988). {\it  Discrete
Math.}  114 (1993), no. 1-3, 205--217.

\bibitem{Gao} W. Gao and  Y.O.  Hamidoune,  On additive bases, {\it Acta Arith. }
88 (1999), no. 3, 233--237.


\bibitem{Lipkin}
E. Lipkin, Subset sums of sets of residues. Structure theory of
set addition, {\it Ast�risque}   258 (1999) 187--193.

\bibitem {Olson} J. E. Olson, An addition theorem modulo $p$, {\it J. Combinatorial
Theory} 5  (1968) 45--52.


\bibitem {Sar} A. S\'ark\"ozi,
Finite addition theorems I, {\it J. Number Theory,} 32, 1989,
114--130.

\bibitem {szemvu1} E. Szemer\'edi and V.H. Vu, Long arithmetic
progressions in finite and infinite sets, {\it to appear in Annals
of Mathematics}.

\end{thebibliography}



\end{document}

math0506483.extracted_bib
\begin{thebibliography}{99}


\bibitem {erd} P. Erd\"os, On the representation of large
interges as sums of distinct summands taken from a fixed set, {\it
Acta. Arith.} 7 (1962) 345-354.

\bibitem {Fre} G. Freiman, New analytical results in subset-sum problem.
Combinatorics and algorithms (Jerusalem, 1988). {\it  Discrete
Math.}  114 (1993), no. 1-3, 205--217.

\bibitem{Gao} W. Gao and  Y.O.  Hamidoune,  On additive bases, {\it Acta Arith. }
88 (1999), no. 3, 233--237.


\bibitem{Lipkin}
E. Lipkin, Subset sums of sets of residues. Structure theory of
set addition, {\it Ast�risque}   258 (1999) 187--193.

\bibitem {Olson} J. E. Olson, An addition theorem modulo $p$, {\it J. Combinatorial
Theory} 5  (1968) 45--52.


\bibitem {Sar} A. S\'ark\"ozi,
Finite addition theorems I, {\it J. Number Theory,} 32, 1989,
114--130.

\bibitem {szemvu1} E. Szemer\'edi and V.H. Vu, Long arithmetic
progressions in finite and infinite sets, {\it to appear in Annals
of Mathematics}.

\end{thebibliography}