Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you retrieve the article in DVI,       *
%_ * PostScript, or PDF format.                                             *
%_ **************************************************************************
%  Author Package
%% Translation via Omnimark script a2l, June 26, 2003 (all in one day!)
\controldates{7-JUL-2003,7-JUL-2003,7-JUL-2003,7-JUL-2003}
 
\RequirePackage[warning,log]{snapshot}
\documentclass{era-l}
\usepackage{amssymb}



\theoremstyle{plain}
\newtheorem*{theorem1}{The EGZ Theorem}
\newtheorem*{theorem2}{Theorem 1.1}
\newtheorem*{theorem3}{Combinatorial Nullstellenstaz}
\newtheorem*{theorem4}{Theorem 1.2}
\newtheorem*{theorem5}{Theorem 1.3}
\newtheorem*{theorem6}{The Main Theorem}
\newtheorem*{theorem7}{Theorem 2.1}
\newtheorem*{theorem8}{Corollary 2.1}
\newtheorem*{theorem9}{Theorem 2.2}
\newtheorem*{theorem10}{Corollary 2.2}
\newtheorem*{theorem11}{Theorem 2.3}
\newtheorem*{theorem12}{Corollary 2.3}
\newtheorem*{theorem13}{Theorem 2.4}
\newtheorem*{theorem14}{Theorem 2.5}
\newtheorem*{theorem15}{Lemma 3.1}
\newtheorem*{theorem16}{Theorem 3.1}
\newtheorem*{theorem17}{Theorem 3.2}
\newtheorem*{theorem18}{Lemma 3.2}



\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\bg}{\bigg }
\newcommand{\myt}{\text }
\newcommand{\f}{\frac }
\newcommand{\mycolon}{{:}\;}
\newcommand{\mo}{\operatorname{mod}}
\newcommand{\myem}{\emptyset }
\newcommand{\se}{\subseteq }
\newcommand{\eq}{\equiv }
\newcommand{\cs}{\cdots }
\newcommand{\ls}{\leqslant }
\newcommand{\gs}{\geqslant }
\newcommand{\al}{\alpha }


\begin{document}

\title{Unification of zero-sum problems, \linebreak[1] subset sums and covers of 
${\mathbb Z}$}
\author{Zhi-Wei Sun}
\address{Department of Mathematics, Nanjing University,
Nanjing 210093, People's Republic of China}
\email{zwsun@nju.edu.cn}
\issueinfo{9}{07}{}{2003}
\dateposted{July 10, 2003}
\pagespan{51}{60}
\PII{S 1079-6762(03)00111-2}
\thanks{The website {\tt http://pweb.nju.edu.cn/zwsun/csz.htm} 
is devoted to the topics covered by this paper.}
\thanks{Supported by
the Teaching and Research Award Fund for Outstanding Young Teachers
in Higher Education Institutions of MOE, and
the National Natural Science Foundation of P. R. China.}
\dedicatory{In memory of Paul Erd\"{o}s}
\keywords{Zero-sum, subset sums, covers of $\mathbb{Z}$}
\subjclass[2000]{Primary 11B75; Secondary 05A05, 05C07, 11B25, 11C08, 
11D68, 11P70, 11T99, 20D60}
\copyrightinfo{2003}{American Mathematical Society}
\date{March 20, 2003}
\commby{Ronald L. Graham}
\begin{abstract}In combinatorial number theory,
zero-sum problems, subset sums and covers of the integers
are three different topics initiated by P. Erd\"{o}s
and investigated by many researchers; they play
important roles in both number theory and combinatorics.
In this paper we announce some deep connections
among these seemingly unrelated fascinating areas,
and aim at establishing a unified theory!
Our main theorem unifies many results in these three realms
and also has applications 
in many aspects such as finite fields and graph theory.
To illustrate this, here
we state our extension of the Erd\"{o}s-Ginzburg-Ziv theorem:
If $A=\{a_{s}(\mathrm{mod}\ n_{s})\}_{s=1}^{k}$ covers
some integers exactly $2p-1$ times and
others exactly $2p$ times, where $p$ is a prime,
then for any $c_{1},\cdots ,c_{k}\in \mathbb{Z}/p\mathbb{Z}$
there exists an $I\se \{1,\cdots ,k\}$ such that $\sum _{s\in 
I}1/n_{s}=p$ and
$\sum _{s\in I}c_{s}=0$.
\end{abstract}
\maketitle



\section*{1. Background}

In 1961 Erd\"{o}s, Ginzburg and Ziv \cite{EGZ} established
the following celebrated theorem and thus laid the foundation
of the zero-sum theory.
\begin{theorem1} For any $c_{1},\cs ,c_{2n-1}\in \Z $, there
is an $I\se [1,2n-1]=\{1,\cs ,2n-1\}$ with $|I|=n$ such that
$\sum _{s\in I}c_{s}\eq 0\ (\mo \ n)$. In other words,
given $2n-1$ (not necessarily distinct) elements of the ring $\Z _{n}=\Z 
/n\Z$ of residues
modulo $n$, we can select $n$ of them with the sum vanishing.
\end{theorem1}


The EGZ theorem can be easily reduced to the case
where $n$ is a prime (and hence $\Z _{n}$ is a field),
and then deduced from
the well-known Cauchy-Davenport theorem or the Chevalley-Warning
theorem (see, e.g., Nathanson \cite[pp. 48--51]{N}).

Here is another fundamental result due to Olson \cite{O}.

\begin{theorem2}[Olson] Let $p$ be a prime and $\Z _{p}^{l}$
be the direct sum of $l$ copies of the ring $\Z _{p}$.
Given $c,c_{1},\cs ,c_{l(p-1)+1}\in \Z _{p}^{l}$ we have
\begin{equation*}\sum _{\substack{I\se [1,l(p-1)+1]\\ \sum _{s\in 
I}c_{s}=c}}(-1)^{|I|}\eq 0\ \ (\mo \ p);
\tag{1.1}\end{equation*}
in particular there exists a nonempty $I\se [1,l(p-1)+1]$
with $\sum _{s\in I}c_{s}=0$.
\end{theorem2}


Observe that the additive group of the finite field with $p^{l}$ elements
is isomorphic to $\Z _{p}^{l}$.
For convenience we let $\Z _{p}^{0}$ be the additive subgroup $\{\bar 
0=p\Z \}$
of $\Z _{p}$ throughout this paper; thus Theorem 1.1 remains valid even 
if $l=0$.

Let $p$ be a prime and $c,c_{1},\cs ,c_{2p-1}\in \Z _{p}$.
 In 1996 Gao \cite{G} proved that
\begin{equation*}\bg |\bg \{I\se [1,2p-1]\mycolon |I|=p\ \myt {and}\ \sum 
_{s\in I}c_{s}=c\bg \}\bg |
  \eq [c=0]\ \ (\mo \ p),\end{equation*}
 where for a predicate $P$ we let $[P]$ be $1$ or $0$
 according to whether $P$ holds or not.
 Note that Gao's result 
clearly follows from Olson's congruence (1.1) in the case $l=2$.

 In 1994 Alford, Granville and Pomerance \cite{AGP}
 employed a result of zero-sum type to prove that
 there are infinitely many Carmichael numbers.
 For results and conjectures on zero-sum problems,
 the reader is referred to the survey \cite{C}.

   What is the smallest integer $k=s(\Z _{n}^{2})$ such that every
 sequence of $k$ elements in $\Z _{n}^{2}$ contains a zero-sum
 subsequence of length $n$? In 1983 Kemnitz \cite{K} conjectured that
 $s(\Z _{n}^{2})=4n-3$. In 1993 Alon and Dubiner \cite{AD} showed that
 $s(\Z _{n}^{2})\ls 6n-5$. In 2000 R\'{o}nyai \cite{R} was able to prove 
that
 $s(\Z _{p}^{2})\ls 4p-2$ for every prime $p$.

 For a finite set $S=\{a_{1},\cs ,a_{k}\}$ contained in the ring $\Z $ or 
a field, sums of the form $\sum _{s\in I}a_{s}$ with $I\se [1,k]$ are
 called subset sums of $S$. It is interesting to provide a nontrivial 
lower bound for the cardinality of the set
 \begin{equation*}\{a_{1}x_{1}+\cs +a_{k}x_{k}\mycolon x_{1},\cs 
,x_{k}\in \{0,1\}\}
 =\bg \{\sum _{s\in I}a_{s}\mycolon I\se [1,k]\bg \}.\end{equation*}
 A more general problem is to study restricted sumsets
 in the form
 \begin{equation*}\{x_{1}+\cs +x_{k}\mycolon x_{1}\in X_{1},\cs , 
x_{k}\in X_{k},\
 P(x_{1},\cs ,x_{k})\not =0\},\tag{1.2}\end{equation*}
 where $X_{1},\cs ,X_{k}$ are subsets of a field
 and $P(x_{1},\cs ,x_{k})$ is a polynomial with coefficients in the
 field. In 1964 Erd\"{o}s and Heilbronn \cite{EH} conjectured that
 if $p$ is a prime and $\myem \not =X\se \Z _{p}$, then
 \begin{equation*}|\{x+y\mycolon x,y\in X\ \myt {and}\ x\not =y\}|\gs 
\min \{p,2|X|-3\}.\end{equation*}
 This conjecture was first confirmed by Dias da Silva and
 Hamidoune \cite{DH} in 1994, who obtained
 a generalization which implies that
 if $S\se \Z _{p}$ and $|S|>\sqrt {4p-7}$, then
 any element of $\Z _{p}$ is a subset sum of $S$.
 In this direction the most powerful tool is
 the following remarkable principle (see Alon \cite{A99}, \cite{A03}),
rooted in
 Alon and Tarsi \cite{AT} and  applied in
 \cite{AF}, \cite{ANR1}, \cite{ANR2}, \cite{DKSS}, \cite{HS}, \cite{LS} 
and \cite{PS}.

 \begin{theorem3}
 Let $X_{1},\cs ,X_{k}$ be finite subsets
 of a field $F$ with $|X_{s}|>l_{s}$ for $s\in [1,k]$,
 where $l_{1},\cs ,l_{k}\in \N =\{0,1,2,\cs \}$.
 If $f(x_{1},\cs ,x_{k})\in F[x_{1},\cs ,x_{k}]$,
  $[x_{1}^{l_{1}}\cs x_{k}^{l_{k}}]f(x_{1},\cs ,x_{k})$
 (the coefficient
 of the monomial $\prod _{s=1}^{k}x_{s}^{l_{s}}$ in $f$)
 is nonzero and $\sum _{s=1}^{k}l_{s}$ is
 the total degree of $f$,
 then there are $x_{1}\in X_{1},\cs ,x_{k}\in X_{k}$ such that
 $f(x_{1},\cs ,x_{k})\not =0$.
 \end{theorem3}


 One of the many applications of the Combinatorial Nullstellenstaz
 is the following result of \cite{AT} on finite fields.

 \begin{theorem4}[Alon and Tarsi] Let $F$ be a finite field with
 $|F|$ not a prime, and let $M$ be a nonsingular $k\times k$
 matrix over $F$. Then there exists a vector $\vec x\in F^{k}$
 such that neither $\vec x$ nor $M\vec x$ has zero component.
 \end{theorem4}


 Now we turn to covers of $\Z $.

 For $a\in \Z $ and $n\in \Z ^{+}=\{1,2,3,\cs \}$ we call
 \begin{equation*}a(n)=a+n\Z =\{a+nx\mycolon x\in \Z \}\end{equation*}
 a residue class with modulus $n$. For a finite system
 \begin{equation*}A=\{a_{s}(n_{s})\}_{s=1}^{k}\tag{1.3}\end{equation*}
 of residue classes, its {\em covering function} $w_{A}(x)=|\{1\ls s\ls 
k\mycolon x\in a_{s}(n_{s})\}|$ is periodic modulo the least
 common multiple $N_{A}$ of the moduli $n_{1},\cs ,n_{k}$. Sun \cite{S99}
 called $m(A)=\min _{x\in \Z }w_{A}(x)$
 the {\em covering multiplicity} of (1.3).
 One can easily verify the following well-known inequality:
 \begin{equation*}\sum _{s=1}^{k}\f 1{n_{s}}=\f 1{N_{A}}\sum 
_{x=0}^{N_{A}-1}w_{A}(x)\gs m(A).\tag{1.4}\end{equation*}

  If $\bigcup _{s=1}^{k}a_{s}(n_{s})=\Z $ (i.e., $m(A)\gs 1$), then
 we call (1.3) a {\em cover} (or {\em covering system}) of $\Z $.
 The concept of cover was first introduced by Erd\"{o}s in
 the 1930's (cf. \cite{E}); it has many surprising applications
 (cf. \cite{Cr}, \cite{S00} and \cite{S01}).
 Erd\"{o}s was very proud of this invention; he said:
 {\em ``Perhaps my favorite problem of all concerns covering systems}."

 For $m\in \Z ^{+}$, if $m(A)\gs m$, then $A$ is said to be an {\em 
$m$-cover}
 of $\Z $; general $m$-covers were first studied by the author in 
\cite{S95}.
 If (1.3) forms an $m$-cover of $\Z $
 but $A_{t}=\{a_{s}(n_{s})\}_{s\not =t}$ does not,
 then we say that $(1.3)$ is an $m$-cover of $\Z $
 with $a_{t}(n_{t})$ {\em essential}.

 If $w_{A}(x)=m$ for all $x\in \Z $, then we call $(1.3)$ an {\em exact 
$m$-cover} of $\Z $.
 (Note that in this case we have $\sum _{s=1}^{k}1/n_{s}=m$ by (1.4).)
 Such covers were first introduced by Porubsk\'{y} \cite{P} in 1976.
 Clearly $m$ copies of $0(1)$ form a trivial exact $m$-cover of $\Z $.
 Using a graph-theoretic argument
 Zhang \cite{Z91} proved that for each $m=2,3,\cs $ there are exact 
$m$-covers of
 $\Z $ which are not unions of an $n$-cover and an $(m-n)$-cover with
 $0m(A)-l(p-1),\tag{2.1}\end{equation*}
 or $|\{I\in \mathcal{I}\mycolon \sum _{s\in I}c_{s0}-c_{0}\in p\Z 
_{p}'\}|\not =1$ and furthermore
 \begin{equation*}\sum _{\substack{I\in \mathcal{I}\\\sum _{s\in 
I}c_{s0}-c_{0}\in p\Z _{p}'}}(-1)^{|I|}e^{2\pi i\sum _{s\in 
I}a_{s}m_{s}/n_{s}}\eq 0\ \ (\mo \ p).\tag{2.2}\end{equation*}

 {\rm (ii)} Suppose that $m(A)0\quad \myt {for all}\ 
r=0,1,\cs ,n-1,\tag{2.3}\end{equation*}
 where \begin{equation*}S_{r}=\bg \{\sum _{s=1}^{k}x_{s}\mycolon x_{s}\in 
X_{s},\ P(x_{1},\cs ,x_{k})\not =0,
 \  \bg \{\sum ^{k}_{\substack{s=1\\x_{s}\not =b_{s}}}\f 
{m_{s}}{n_{s}}\bg \}=\f {\al +r}n\bg \}.
 \tag{2.4}\end{equation*}
 \end{theorem6}


 When $l=\theta =0$, $c_{s0}\in \{1,m_{s}/n_{s}\}$
 and $p$ is a sufficiently large prime, part (i) of the Main Theorem
 yields  Theorem 1.3(i). Theorem 1.3(ii)
 follows from the first part of the Main Theorem
 in the case $l=0$ and $c_{s0}=2^{s}$
 because two subsets $I,J$ of $[1,k]$ are equal if and only if
 $\sum _{s\in I}2^{s}=\sum _{s\in J}2^{s}$.

 In the case $n_{1}=\cs =n_{k}=n=1$, part (ii) of the Main Theorem
 yields the \linebreak following basic lemma of the so-called polynomial
 method due to Alon, Nathanson \linebreak and Ruzsa \cite{ANR1}, \cite{ANR2}:
 Let $X_{1},\cs ,X_{k}$ be subsets of a field $F$ with
 $|X_{s}|=\break h_{s}\in \{1,2\}$ for $s\in [1,k]$. If $P(x_{1},\cs ,x_{k})
 \in F[x_{1},\cs ,x_{k}]\setminus \{0\}$, 
 $\deg P\ls \break \sum _{s=1}^{k}(h_{s}-1)$ and
 \begin{equation*}[x_{1}^{h_{1}-1}\cdots x_{k}^{h_{k}-1}]P(x_{1},\cs 
,x_{k})(x_{1}+\cs +x_{k})^{\sum _{s=1}^{k}(h_{s}-1)-\deg P}
 \not =0,\end{equation*}
 then
 \begin{equation*}\bg |\bg \{\sum _{s=1}^{k}x_{s}\mycolon x_{s}\in X_{s}\ 
\myt {and}
 \ P(x_{1},\cs ,x_{k})\not =0\bg \}\bg |
 \gs \sum _{s=1}^{k}(h_{s}-1)-\deg P+1.\end{equation*}
 Actually this remains valid even if $h_{s}$ may be greater than two.

 In the rest of this section we will list various other results
 deduced from the Main Theorem.

 \begin{theorem7} Let $(1.3)$ be an $l(p-1)+1$-cover of $\Z $,
 where $l\in \N $ and $p$ is a prime. Let $m_{1},\cs ,m_{k}\in \Z $
 and $c_{1},\cs ,c_{k}\in \Z _{p}^{l}$. Then for any $0\ls \theta <1$ and
 $c\in \Z _{p}^{l}$ we have
 \begin{equation*}\sum _{\substack{I\se [1,k]\\\sum _{s\in I}c_{s}=c
 \\\{\sum _{s\in I}m_{s}/n_{s}\}=\theta }}(-1)^{|I|}
 e^{2\pi i\sum _{s\in I}a_{s}m_{s}/n_{s}}\eq 0\ \ (\mo \ 
p);\tag{2.5}\end{equation*}
 in particular, there is a nonempty subset $I$ of $[1,k]$ such that
 $\sum _{s\in I}c_{s}=0$ and \linebreak $\sum _{s\in I}m_{s}/n_{s}\in \Z $.
 \end{theorem7}


 Since a system of $k$ copies of $0(1)$ forms a $k$-cover of $\Z $,
 Theorem 1.1 is a special case of Theorem 2.1. In the case
 $l=0$ Theorem 2.1 yields Zhang's result (1.5) on covers of $\Z $.
 

  In 1984 Alon, Friedland and Kalai \cite{AFK1}, \cite{AFK2}
 proved that if $p$ is a prime, then
 any loopless graph with average degree bigger than $2p-2$
 and maximum degree at most $2p-1$ must contain a $p$-regular
 subgraph. Now we apply Theorem 2.1 to
 strengthen this result.

\begin{theorem8} Let $G$ be a loopless graph of $l$ vertices
with the edge set $\{1,\cs ,k\}$. Suppose that all the vertices
of $G$ have degree not greater than $2p-1$ and that $(1.3)$
forms an $l(p-1)+1$-cover of $\Z $, where $p$ is a prime.
Then for any $m_{1},\cs ,m_{k}\in \Z $ we have
\begin{equation*}\mathcal{H}=\bg \{p\myt {-regular subgraph}\ H\ \myt 
{of}\ G\mycolon \sum _{s\in E(H)}\f {m_{s}}{n_{s}}\in \Z \bg \}\not =\myem, 
\end{equation*}
where $E(H)$ denotes the edge set of the subgraph $H$;
furthermore
\begin{equation*}\sum _{H\in \mathcal{H}}(-1)^{|E(H)|}e^{2\pi i\sum 
_{s\in E(H)}a_{s}m_{s}/n_{s}}
\eq -1\ (\mo \ p).\tag{2.6}\end{equation*}
\end{theorem8}


  \begin{theorem9} Let $(1.3)$ be a system of residue classes
  with $m(A)>(l+1)(p-1)$, where $l\in \N $ and $p$ is a prime.
  Let $m_{1},\cs ,m_{k}\in \Z $
  and $c_{1},\cs ,c_{k}\in \Z _{p}^{l}$.
  Then for any $c\in \Z _{p}^{l}$ and $r\in \Q $ we have
  \begin{equation*}\sum _{\substack{I\se [1,k]
  \\\sum _{s\in I}c_{s}=c\\\sum _{s\in I}m_{s}/n_{s}\in r+p\Z 
}}(-1)^{|I|}e^{2\pi i\sum _{s\in I}a_{s}m_{s}/n_{s}}\eq 0\ \ (\mo \ 
p);\tag{2.7}\end{equation*}
  in particular, there is a nonempty subset $I$ of $[1,k]$
  such that $\sum _{s\in I}c_{s}=0$ and \linebreak 
$\sum _{s\in I}m_{s}/n_{s}\in 
p\Z $.
  \end{theorem9}


  \begin{theorem10} Let $(1.3)$
  be a system of residue classes, and let $p$ be a prime.

 {\rm (i)} If $2p-1\in \{w_{A}(x)\mycolon x\in \Z \}\se \{2p-1,2p\}$,
 then for any $c_{1},\cs ,c_{k}\in \Z _{p}$ there exists an $I\se [1,k]$
 such that $\sum _{s\in I}1/n_{s}=p$ and $\sum _{s\in I}c_{s}=0$.

 {\rm (ii)} If $(1.3)$ forms an exact $3p$-cover of $\Z $,
 then for any $c_{1},\cs ,c_{k}\in \Z _{p}^{2}$ with $c_{1}+\cs +c_{k}=0$,
 there exists an $I\se [1,k]$
 such that $\sum _{s\in I}1/n_{s}=p$ and $\sum _{s\in I}c_{s}=0$.
 \end{theorem10}


  The EGZ theorem and
 Lemma 3.2 of Alon and Dubiner \cite{AD}
 are parts (i) and (ii) of our Corollary 2.2
 in the case $n_{1}=\cs =n_{k}=1$.
 An interesting open question is whether we can replace
 the prime $p$ in Corollary 2.2 by any positive integer $n$. The answer 
is affirmative if $n$ is a prime power.

\begin{theorem11} Suppose that $(1.3)$ is an $m$-cover of
$\Z $ with $a_{k}(n_{k})$ essential. Let $m_{1},\cs ,m_{k-1}\in \Z $
be relatively prime to $n_{1},\cs ,n_{k-1}$, respectively.
Let $F$ be a field with characteristic $p$ not dividing $N_{A}$, and let
$X_{1}=\{b_{1},c_{1}\},\cs ,X_{k-1}=\{b_{k-1},c_{k-1}\}$
be any subsets of $F$ with cardinality $2$. Then for some
$0\ls \al <1$ we have
\begin{equation*}\bg |\bg \{\sum _{s=1}^{k-1}x_{s}\mycolon x_{s}\in X_{s},
\ \bg \{\sum _{\substack{1\ls s