% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.33}{23(3)}{2016}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\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


% 
% 
% \documentclass[reqno,10pt]{article} % font size = 12
% \usepackage{amsmath,amsthm,amssymb,amscd,verbatim,framed}
% \usepackage{graphicx}
% \usepackage{stmaryrd}
% \usepackage{graphicx}
% \usepackage{epsfig}
% \usepackage{stmaryrd}
%\bibliographystyle{plain}

% %%%%%%%%%%%%%%% EXACT 1in MARGINS %%                  %%
% \setlength{\textwidth}{6.5in}     %%                  %%
% \setlength{\oddsidemargin}{0in}   %%                  %%
% \setlength{\evensidemargin}{0in}  %%                  %%
% \setlength{\textheight}{8.5in}    %% (modify at your  %%
% \setlength{\topmargin}{0in}       %%  own risk...)    %%
% \setlength{\headheight}{0in}      %%                  %%
% \setlength{\headsep}{.3in}         %%                  %%
% \setlength{\footskip}{.5in}       %%                  %%
% %\linespread{1.3}                  %%                  %%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \vfuzz2pt

%\setlength{\textheight}{8.7in} \setlength{\textwidth}{6.2in}
%\setlength{\oddsidemargin}{0in}


%\pagestyle{myheadings} \markright{\sc Circular chromatic index
%\hfill} \thispagestyle{empty}
%\usepackage{setspace}
%\textwidth = 15 cm \textheight = 22 cm \oddsidemargin = 0 cm
%\evensidemargin = 0 cm \topmargin = -1 cm
%\parskip = 1.0 mm


\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{\ignore}[1]{}
% 
% \input{epsf}
% \newcommand{\fig}[4]{
%         \begin{figure}[htbp]
%         \setlength{\epsfysize}{#2}
%         \centerline{\epsfbox{#4}}
%         \caption{#3} \label{#1}
%         \end{figure}
%         }
% 
% \newtheorem{prelem}{{\bf Theorem}}
% \renewcommand{\theprelem}{{\Alph{prelem}}}
% \newenvironment{theoremABC}{\begin{prelem}{\hspace{-0.5
%                em}{\bf.}}}{\end{prelem}}
% 
% 
% \newtheorem{theorem}{Theorem}
% \newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{definition}[theorem]{Definition}
% \newtheorem{conjecture}[theorem]{Conjecture}
% \newtheorem{claim}[theorem]{Claim}
% \newtheorem{problem}[theorem]{Problem}
% \newtheorem{question}[theorem]{Question}
% \newtheorem{lemma}[theorem]{Lemma}
% \newtheorem{proposition}[theorem]{Proposition}
% \newtheorem{observation}[theorem]{Observation}
% \newtheorem{prob}{Problem}
% 
% %\newenvironment{proof}{{\bf Proof.}}{\hfill\rule{2mm}{2mm}}
% \newtheorem{remarka}[theorem]{Remark}
% \newenvironment{remark}{\begin{remarka}\rm}{\hfill\rule{2mm}{2mm}\end{remarka}}
% \newtheorem{examplea}[theorem]{Example}
% \newenvironment{example}{\begin{examplea}\rm}{\hfill\rule{2mm}{2mm}\end{examplea}}
% 
% \newtheorem{exercisea}[theorem]{Exercise}
% \newenvironment{exercise}{\begin{exercisea}\rm}{\hfill\rule{2mm}{2mm}\end{exercisea}}


\def\mod {{\rm mod}\ }
\def\rank{{\mathrm{rank}}}
\def\span{{\mathrm{span}}}
\def\Ex {{\mathbb E}}
\def\Pr {{\rm Pr}}
\def\Var {{\rm Var}}
\def\supp{\mathrm{Supp}}
\def\exp{{e}}

\def\x{\mathbf{x}}
\def\X{\mathbf{X}}
\def\Y{\mathbf{Y}}
\def\u{\mathbf{u}}
\def\z{\mathbf{z}}
\def\a{\mathbf{a}}
\def\P{\mathcal{P}}


\def\Z{\mathbb{Z}}
\def\cS{\mathcal{S}}
\def\N{\mathbb{N}}
\def\e{\mathbf{e}}
\def\b{\mathbf{b}}


\title{\bf On the additive bases problem in finite fields}

\author{
Victoria de Quehen \\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small McGill University\\[-0.8ex] 
\small Montreal, Canada \\
\small\tt dequehen@math.mcgill.ca\\
\and
Hamed Hatami\thanks{Supported by an NSERC Discovery Grant.}\\
\small School of Computer Science\\[-0.8ex]
\small McGill University\\[-0.8ex]
\small Montreal, Canada \\
\small\tt hatami@cs.mcgill.ca
}

\date{\dateline{Jul 3, 2016}{Aug 5, 2016}{Aug 19, 2016}\\
\small Mathematics Subject Classifications: 11B13}

\begin{document}
\maketitle


\begin{abstract}
We prove that if $G$ is an Abelian group and $A_1,\ldots,A_k \subseteq G$ satisfy $m A_i=G$ (the $m$-fold sumset), then $A_1+\cdots+A_k=G$ provided that $k \ge c_m \log \log |G|$. This generalizes a result of Alon, Linial, and Meshulam~[Additive bases of vector spaces over prime fields. \emph{J. Combin. Theory Ser. A}, 57(2):203--210, 1991]  regarding so-called additive bases. 

\end{abstract}



\section{Introduction}

Let $p$ be a fixed prime, and let $\Z_p^n$ denote the $n$-dimensional vector space over the field $\Z_p$. Given a multiset $B$ with elements from $\Z_p^n$, let 
$\cS(B) = \left\{\left. \sum_{b \in S} b \ \right| \ S \subseteq B \right\}$. The set $B$ is called an \emph{additive basis} if $\cS(B)=\Z_p^n$. 

Jaeger, Linial, Payan, and Tarzi~\cite{MR1186753} made the following conjecture and showed that if true, it would provide a beautiful generalization of many important results regarding nowhere-zero flows. In particular the case $p=3$ would imply the weak $3$-flow conjecture, which has been proven only recently by Thomassen~\cite{MR2885433}.

\begin{conjecture}\cite{MR1186753}
\label{conj:JLPT}
For every prime $p$, there exists a constant $k_p$ such that the union (with repetitions) of any $k_p$ bases for $\Z_p^n$ forms an additive basis.
\end{conjecture}




Let us denote by $k_p(n)$ the smallest $k \in \N$ such that  the union  of any $k$ bases for $\Z_p^n$ forms an additive basis.  In~\cite{MR1111557} two different proofs are given to show that $k_p(n)\le c_p \log n$, where here and throughout the paper the logarithms are in base $2$. The first proof is based on exponential sums and yields the bound $k_p(n) \le 1+(p^2/2) \log 2pn$, and the second proof is based on an algebraic method and yields $k_p(n) \le (p-1) \log n + p-2$. As  observed in~\cite{MR1111557}, it is easy to construct examples showing that $k_p(n) \ge p$, and, to the best of our knowledge, it is quite possible that $k_p(n)=p$.

Let $G$ be an Abelian group, and for $A,B \subseteq G$, define the sumset $A+B=\{a+b \ | a \in A, b \in B\}$. For $A \subseteq G$ and $m \in \N$, let $mA=A+\cdots+A$ denote the $m$-fold sumset of $A$. Note that for a  basis $B$ of $\Z_p^n$, we have $(p-1) \cS(B) = \Z_p^n$.  On the other hand if $B= B_1 \cup \ldots \cup B_k$ is a union with repetitions of $k$ bases for $\Z_p^n$, then $\cS(B)=\cS(B_1)+\cdots+\cS(B_k)$. Hence  Theorem~\ref{thm:main} below is a generalization of the above mentioned theorem of Alon \emph{et al}~\cite{MR1111557}. 


\begin{theorem}[Main theorem]
\label{thm:main}
Let $G$ be a finite Abelian group. Suppose $A_1,\ldots,A_{2K} \subseteq G$ satisfy $m A_i=G$ for all $1\le i \le 2K$ where $K \ge  m \ln \log(|G|)$.  Then $A_1+\cdots+A_{2K}=G$. Moreover, for $m=2$, it suffices to have  $K \ge \log \log(|G|)$.
\end{theorem}

We present the proof of Theorem~\ref{thm:main} in Section~\ref{sec:proof}. While it is quite possible that Conjecture~\ref{conj:JLPT} is true, the following example shows that its generalization, Theorem~\ref{thm:main}, cannot be improved beyond $\Theta(\log \log |G|)$ even when $m=2$. 


\begin{example}
\label{ex:ConstructionLog}
Let $n=2^k$ and for $i=1,\ldots,k$, let $C_i \subseteq  \Z_p^{2^i}$ be the set of vectors in $\Z_p^{2^i} \setminus \{\vec{0}\}$ in which the first half or the second half (but not both)  of the coordinates are all $0$'s. Note that $C_i+C_i=\Z_p^{2^i}$. Define $A_0=(\Z_p \setminus \{0\})^{2^k}$ and for $i=1,\ldots,k$, let 
$$A_i=\underbrace{C_i \times \cdots \times C_i}_{2^{k-i}} \subseteq \Z_p^n.$$ It follows from $C_i+C_i=\Z_p^{2^i}$ that $A_i+A_i=\Z_p^n$. On the other hand a simple induction shows that for $j \le k$, 
$$A_0+\cdots+A_j= (\Z_p^{2^j} \setminus \{\vec{0} \})^{2^{k-j}} \neq \Z_p^n.$$
\end{example}

\begin{remark}
Theorem~\ref{thm:main} in particular implies that $k_p(n) \le 2 (p-1) \ln n + 2 (p-1) \ln \log p$, and  $k_3(n) \le 2 \log n + 2$. Note that for $p >3$, the algebraic proof of~\cite{MR1111557} provides a slightly better constant, however unlike the theorem of~\cite{MR1111557}, Theorem~\ref{thm:main} can be applied to the case where $p$ is not necessarily a prime. 
\end{remark}



\section{Proof of Theorem~\ref{thm:main}}
\label{sec:proof}

The proof is based on the Pl\"unnecke-Ruzsa inequality. 

\begin{lemma}[Pl\"unnecke-Ruzsa]
\label{lem:PlunneckeRuzsa}
If $A,B$ are finite sets in an Abelian group satisfying $|A+B| \le \alpha |B|$, then 
$$|k A | \le \alpha^{k} |B|,$$
provided that $k > 1$. 
\end{lemma}

Next we present the proof  of Theorem~\ref{thm:main}. For $2 \le i\le K$, substituting $k=m$, $A=A_{i}$ and $B=A_1+\cdots+A_{i-1}$ in Lemma~\ref{lem:PlunneckeRuzsa}, we obtain 
$$|G|= |mA_i| \le \left(\frac{|A_1+\cdots+A_{i-1}+A_i|}{|A_1+\cdots+A_{i-1}|} \right)^m |A_1+\cdots+A_{i-1}|,$$
which simplifies to
$$|G|^{1/m}  |A_1+\cdots+A_{i-1}|^{\frac{m-1}{m}} \le |A_1+\cdots+A_{i-1}+A_i|.$$
%
Consequently, 
$$|G|^{1-\lambda}  |A_1|^{\lambda} \le |A_1+\cdots+A_K|,$$
where $\lambda=\left(\frac{m-1}{m}\right)^K$. Since $K \ge  m \ln \log |G|$, we have $\lambda=\left(\frac{m-1}{m}\right)^K < e^{-K/m} \le 1/\log |G|$, and thus 
$|G|^\lambda < 2$ and   $|G|/2 <|A_1+\cdots+A_K|$. Similarly we obtain 
$$|G|/2 <  |A_{K+1}+\cdots+A_{2K}|.$$
Since $A+B=G$ if $|A|,|B| > |G|/2$, we conclude  
$$A_1+\cdots+A_{2K}=G.$$

Finally note that for $m=2$, we have $\lambda=2^{-K}$, and thus to obtain $|G|/2 < |G|^{1-\lambda}  |A_1|^{\lambda}$, it suffices to have $K \ge \log \log|G|$. 



\section{Quasi-random Groups}

While Example~\ref{ex:ConstructionLog} shows that the bound of $\Theta(\log \log |G|)$ is essential in Theorem~\ref{thm:main}, for certain non-Abelian groups, it is possible to achieve the constant bound similar to what is conjectured in Conjecture~\ref{conj:JLPT}.  A finite group $G$ is called $D$-quasirandom if all non-trivial unitary representations of $G$ have dimension at least $D$. The terminology ``quasirandom group'' was introduced explicitly by Gowers in the fundamental paper~\cite{MR2410393} where he showed that  dense Cayley graphs in quasirandom groups are quasirandom graphs in the sense of Chung, Graham, and Wilson~\cite{MR1054011}. The group $\mathrm{SL}_2(\Z_p)$ is an example of a highly quasirandom group. The so-called Frobenius lemma says that $\mathrm{SL}_2(\Z_p)$ is $(p-1)/2$-quasirandom. This has to be compared to the cardinality of this group,  $|\mathrm{SL}_2(\Z_p)|=p^3-p$. The basic fact that we will use about  quasirandom groups is the following theorem of Gowers (See also~\cite[Exercise 3.1.1]{MR3309986}). 

\begin{theorem}[{\cite{MR2410393}}]
\label{thm:GowersQuasirandom}
Let $G$ be a $D$-quasirandom finite group.  Then every $A,B,C \subseteq G$ with $|A||B||C| > |G|^3 /D$ satisfy $ABC=G$. 
\end{theorem}

We will also need the noncommutative version of Ruzsa's inequality.  

\begin{lemma}[Ruzsa inequality~\cite{MR1420216}]
\label{lem:Ruzsa}
Let $A,B,C \subseteq G$  be finite subsets of a group $G$. Then 
$$|A C^{-1}| \le \frac{|A B^{-1}||B C^{-1}|}{|B|}.$$
\end{lemma}
\begin{proof}
The claims follows immediately from fact that by the identity $ac^{-1}=a b^{-1} bc^{-1}$,  every element $ac^{-1}$ in $AC^{-1}$ has at least $|B|$ distinct representations of the from $xy$ with 
$(x,y) \in (AB^{-1}) \times (BC^{-1})$.
\end{proof}

Finally we can state the analogue of  Theorem~\ref{thm:main} for quasi-random groups. 

\begin{theorem}
Let $G$ be a $|G|^{\delta}$-quasirandom finite group for some $\delta > 0$. If the sets $A_1,\ldots,A_{K} \subseteq G$ satisfy $A_i A_i^{-1}=G$ for all $1\le i \le K$ where $K > \log(3/\delta)$.  Then $A_1\ldots A_{3K}=G$.
\end{theorem}
\begin{proof}
Obviously $|A_1| \ge |G|^{1/2}$. For $2 \le i\le K$, substituting $A=C=A_i^{-1}$ and $B=A_1  \ldots  A_{i-1}$ in Lemma~\ref{lem:Ruzsa}, we obtain 
$$\sqrt{|G||A_1  \ldots  A_{i-1}|} \le |A_1  \ldots  A_{i}|,$$
which in turn shows 
$$|G|^{1-2^{-K}} \le |A_1  \ldots A_{K}|.$$
Since $K > \log(3/\delta)$, we have 
$$|G| |G|^{-\delta/3} < |A_1\ \ldots  A_K|.$$
We obtain a similar bound for $|A_{K+1}  \ldots A_{2K}|$ and $|A_{2K+1}  \ldots A_{3K}|$, and the result follows from Theorem~\ref{thm:GowersQuasirandom}.
\end{proof}
% 
\begin{remark}
Note that in particular for $G=\mathrm{SL}_2(\Z_p)$, if $p \ge 7$, and $A_1,\ldots,A_{12} \subseteq G$ satisfy $A_i A_i^{-1}=G$, then $A_1 \ldots A_{12}=G$. 
\end{remark}


\section*{Acknowledgements.}
We would like to thank  Kaave Hosseini, Nati Linial, and Shachar Lovett for valuable discussions about this problem.

\begin{thebibliography}{JLPT92}

\bibitem[ALM91]{MR1111557}
N.~Alon, N.~Linial, and R.~Meshulam.
\newblock Additive bases of vector spaces over prime fields.
\newblock {\em J. Combin. Theory Ser. A}, 57(2):203--210, 1991.

\bibitem[CGW89]{MR1054011}
F.~Chung, R.~L. Graham, and R.~M. Wilson.
\newblock Quasi-random graphs.
\newblock {\em Combinatorica}, 9(4):345--362, 1989.

\bibitem[Gow08]{MR2410393}
W.~T. Gowers.
\newblock Quasirandom groups.
\newblock {\em Combin. Probab. Comput.}, 17(3):363--387, 2008.

\bibitem[JLPT92]{MR1186753}
F.~Jaeger, N.~Linial, C.~Payan, and M.~Tarsi.
\newblock Group connectivity of graphs---a nonhomogeneous analogue of
  nowhere-zero flow properties.
\newblock {\em J. Combin. Theory Ser. B}, 56(2):165--182, 1992.

\bibitem[Ruz96]{MR1420216}
I.~Z. Ruzsa.
\newblock Sums of finite sets.
\newblock In {\em Number theory ({N}ew {Y}ork, 1991--1995)}, pages 281--293.
  Springer, New York, 1996.

\bibitem[Tao15]{MR3309986}
T.~Tao.
\newblock {\em Expansion in finite simple groups of {L}ie type}, volume 164 of
  {\em Graduate Studies in Mathematics}.
\newblock American Mathematical Society, Providence, RI, 2015.

\bibitem[Tho12]{MR2885433}
C.~Thomassen.
\newblock The weak 3-flow conjecture and the weak circular flow conjecture.
\newblock {\em J. Combin. Theory Ser. B}, 102(2):521--529, 2012.

\end{thebibliography}

\end{document}
