These pages are not updated anymore. They reflect the state of . 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