% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % 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{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}{Jul 27, 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+\ldots+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+\ldots+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)+\ldots+\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+\ldots+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 \ldots \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+\ldots+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+\ldots+A_{i-1}$ in Lemma~\ref{lem:PlunneckeRuzsa}, we obtain $$|G|= |mA_i| \le \left(\frac{|A_1+\ldots+A_{i-1}+A_i|}{|A_1+\ldots+A_{i-1}|} \right)^m |A_1+\ldots+A_{i-1}|,$$ which simplifies to $$|G|^{1/m} |A_1+\ldots+A_{i-1}|^{\frac{m-1}{m}} \le |A_1+\ldots+A_{i-1}+A_i|.$$ % Consequently, $$|G|^{1-\lambda} |A_1|^{\lambda} \le |A_1+\ldots+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+\ldots+A_K|$. Similarly we obtain $$|G|/2 < |A_{K+1}+\ldots+A_{2K}|.$$ Since $A+B=G$ if $|A|,|B| > |G|/2$, we conclude $$A_1+\ldots+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\cdot \ldots \cdot 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 \cdot \ldots \cdot A_{i-1}$ in Lemma~\ref{lem:Ruzsa}, we obtain $$\sqrt{|G||A_1 \cdot \ldots \cdot A_{i-1}|} \le |A_1 \cdot \ldots \cdot A_{i}|,$$ which in turn shows $$|G|^{1-2^{-K}} \le |A_1 \cdot \ldots \cdot A_{K}|.$$ Since $K > \log(3/\delta)$, we have $$|G| |G|^{-\delta/3} < |A_1\cdot \ldots \cdot A_K|.$$ We obtain a similar bound for $|A_{K+1} \cdot \ldots \cdot A_{2K}|$ and $|A_{2K+1} \cdot \ldots \cdot 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}