ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 9, Pages 51–60 (July 10, 2003) S 1079-6762(03)00111-2

UNIFICATION OF ZERO-SUM PROBLEMS, SUBSET SUMS AND COVERS OF ℤ

ZHI-WEI SUN

(Communicated by Ronald L. Graham)

In memory of Paul Erdös

Abstract. In combinatorial number theory, zero-sum problems, subset sums and covers of the integers are three different topics initiated by P. Erdö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ös-Ginzburg-Ziv theorem: If A = {a_{s}(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}, ⋯, c_{k} ∈ ℤ/pℤ there exists an I ⊆ {1, ⋯, k} such that ∑_{s∈I} 1/n_{s} = p and ∑_{s∈I} c_{s} = 0.

1. Background

In 1961 Erdös, Ginzburg and Ziv [EGZ] established the following celebrated theorem and thus laid the foundation of the zero-sum theory.

The EGZ Theorem. For any c_{1}, ⋯, c_{2n−1} ∈ ℤ, there is an I ⊆ [1, 2n − 1] = {1, ⋯, 2n − 1} with |I| = n such that ∑_{s∈I} c_{s} ≡ 0 (mod n). In other words, given 2n−1 (not necessarily distinct) elements of the ring ℤ_{n} = ℤ/nℤ of residues modulo n, we can select n of them with the sum vanishing.

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

Here is another fundamental result due to Olson [O].

Received by the editors March 20, 2003. 2000 Mathematics Subject Classification. Primary 11B75; Secondary 05A05, 05C07, 11B25,

11C08, 11D68, 11P70, 11T99, 20D60.

Key words and phrases. Zero-sum, subset sums, covers of ℤ. The website http://pweb.nju.edu.cn/zwsun/csz.htm is devoted to the topics covered by this

paper.

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.

\begin{matrix}c \\ ◯ \end{matrix}2003 American Mathematical Society

Theorem 1.1 (Olson). Let p be a prime and ℤ_{p}^{l} be the direct sum of l copies of the ring ℤ_{p}. Given c, c_{1}, ⋯, c_{l(p−1)+1} ∈ ℤ_{p}^{l} we have

(1.1)  ∑_{\begin{matrix}I⊆[1,l(p−1)+1] \\ ∑_{s∈I} c_{s}=c \end{matrix}}(−1)^{|I|} ≡ 0 (mod p);

in particular there exists a nonempty I ⊆ [1, l(p − 1) + 1] with ∑_{s∈I} c_{s} = 0.

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

Let p be a prime and c, c_{1}, ⋯, c_{2p−1} ∈ ℤ_{p}. In 1996 Gao [G] proved that

|{I ⊆ [1, 2p − 1]: |I| = p and ∑_{s∈I} c_{s} = c}| ≡ [c = 0] (mod p),

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 [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 [C].

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

For a finite set S = {a_{1}, ⋯, a_{k}} contained in the ring ℤ or a field, sums of the form ∑_{s∈I} a_{s} with I ⊆ [1, k] are called subset sums of S. It is interesting to provide a nontrivial lower bound for the cardinality of the set

{a_{1}x_{1} + ⋯ + a_{k}x_{k}: x_{1}, ⋯, x_{k} ∈ {0, 1}} = { ∑_{s∈I} a_{s}: I ⊆ [1, k]}.

A more general problem is to study restricted sumsets in the form

(1.2)  {x_{1} + ⋯ + x_{k}: x_{1} ∈ X_{1}, ⋯, x_{k} ∈ X_{k}, P (x_{1}, ⋯, x_{k}) ≠ 0},

where X_{1}, ⋯, X_{k} are subsets of a field and P (x_{1}, ⋯, x_{k}) is a polynomial with coefficients in the field. In 1964 Erdös and Heilbronn [EH] conjectured that if p is a prime and ∅ ≠ X ⊆ ℤ_{p}, then

|{x + y: x, y ∈ X and x ≠ y}| ⩾ min{p, 2|X| − 3}.

This conjecture was first confirmed by Dias da Silva and Hamidoune [DH] in 1994, who obtained a generalization which implies that if S ⊆ ℤ_{p} and |S| > \sqrt{4p − 7}, then any element of ℤ_{p} is a subset sum of S. In this direction the most powerful tool is the following remarkable principle (see Alon [A99], [A03]), rooted in Alon and Tarsi [AT] and applied in [AF], [ANR1], [ANR2], [DKSS], [HS], [LS] and [PS].

Combinatorial Nullstellenstaz. Let X_{1}, ⋯, X_{k} be finite subsets of a field F with |X_{s}| > l_{s} for s ∈ [1, k], where l_{1}, ⋯, l_{k} ∈ ℕ = {0, 1, 2, ⋯ }. If f(x_{1}, ⋯, x_{k}) ∈ F [x_{1}, ⋯, x_{k}], [x_{1}^{l_{1}} ⋯ x_{k}^{l_{k}}]f(x_{1}, ⋯, x_{k}) (the coefficient of the monomial ∏_{s=1}^{k} x_{s}^{l_{s}} in f) is nonzero and ∑_{s=1}^{k} l_{s} is the total degree of f, then there are x_{1} ∈ X_{1}, ⋯, x_{k} ∈ X_{k} such that f(x_{1}, ⋯, x_{k}) ≠ 0.

UNIFICATION OF ZERO-SUM PROBLEMS, SUBSET SUMS AND COVERS OF ℤ 53

One of the many applications of the Combinatorial Nullstellenstaz is the following result of [AT] on finite fields.

Theorem 1.2 (Alon and Tarsi). Let F be a finite field with |F | not a prime, and let M be a nonsingular k × k matrix over F. Then there exists a vector x⃗ ∈ F^{k} such that neither x⃗ nor Mx⃗ has zero component.

Now we turn to covers of ℤ.

For a ∈ ℤ and n ∈ ℤ^{+} = {1, 2, 3, ⋯ } we call

a(n) = a + nℤ = {a + nx: x ∈ ℤ}

a residue class with modulus n. For a finite system

(1.3)  A = {a_{s}(n_{s})}_{s=1}^{k}

of residue classes, its covering function w_{A}(x) = |{1 ⩽ s ⩽ k: x ∈ a_{s}(n_{s})}| is periodic modulo the least common multiple N_{A} of the moduli n_{1}, ⋯, n_{k}. Sun [S99] called m(A) = min_{x∈ℤ} w_{A}(x) the covering multiplicity of (1.3). One can easily verify the following well-known inequality:

(1.4)  ∑_{s=1}^{k} \frac{1}{n_{s}} = \frac{1}{N_{A}} ∑_{x=0}^{N_{A}−1} w_{A}(x) ⩾ m(A).

If ⋃_{s=1}^{k} a_{s}(n_{s}) = ℤ (i.e., m(A) ⩾ 1), then we call (1.3) a cover (or covering system) of ℤ. The concept of cover was first introduced by Erdös in the 1930’s (cf. [E]); it has many surprising applications (cf. [Cr], [S00] and [S01]). Erdös was very proud of this invention; he said: “Perhaps my favorite problem of all concerns covering systems.”

For m ∈ ℤ^{+}, if m(A) ⩾ m, then A is said to be an m-cover of ℤ; general mcovers were first studied by the author in [S95]. If (1.3) forms an m-cover of ℤ but A_{t} = {a_{s}(n_{s})}_{s≠t} does not, then we say that (1.3) is an m-cover of ℤ with a_{t}(n_{t}) essential.

If w_{A}(x) = m for all x ∈ ℤ, then we call (1.3) an exact m-cover of ℤ. (Note that in this case we have ∑_{s=1}^{k} 1/n_{s} = m by (1.4).) Such covers were first introduced by Porubský [P] in 1976. Clearly m copies of 0(1) form a trivial exact m-cover of ℤ. Using a graph-theoretic argument Zhang [Z91] proved that for each m = 2, 3, ⋯ there are exact m-covers of ℤ which are not unions of an n-cover and an (m − n)- cover with 0 < n < m.

There are many problems and results on covers; the reader is recommended to consult the introduction part of [S96] and the recent survey [P-S].

Here we mention some properties of covers related to Egyptian fractions. The first nontrivial result of this nature is the following one discovered by Zhang [Z89] with the help of the Riemann zeta function: If (1.3) forms a cover of ℤ, then

(1.5)  ∑_{s∈I} \frac{1}{n_{s}} ∈ ℤ for some nonempty I ⊆ [1, k].

The author [S95], [S96], [S99] obtained the following further extensions of Zhang’s result.

Theorem 1.3 (Sun). Let (1.3) be an m-cover of ℤ and let m_{1}, ⋯, m_{k} ∈ ℤ^{+}.

(i) There are at least m positive integers in the form ∑_{s∈I} m_{s}/n_{s} with I ⊆ [1, k]. Also, |{|I|: I ⊆ [1, k] and ∑_{s∈I} m_{s}/n_{s} ∈ ℤ^{+}}| ⩾ m.

(ii) For any J ⊆ [1, k] there are at least m subsets I ≠ J of [1, k] such that {∑_{s∈I} m_{s}/n_{s}} = {∑_{s∈J} m_{s}/n_{s}}, where {α} denotes the fractional part of a real number α.

Zero-sum problems and subset sums seem to have nothing to do with covers of ℤ. Before this work no one has realized their close connections. Can you imagine that the EGZ theorem and the Alon-Tarsi theorem are related to covers of ℤ? The purpose of this paper is to announce a surprising unified theory and embed the study of zero-sum problems and subset sums in the investigation of covers.

In the next section we will present the Main Theorem together with its various consequences. In Section 3 we will state two key lemmas, the first of which connects the zero-sum problems with the study of subset sums, and the second plays an important role in the proof of the Main Theorem. Detailed proofs of the results in this announcement appeared in the preprint [S03], which contains a more general version of the Main Theorem.

2. Our main results

For a prime p we let ℤ′_{p} denote the ring of p-integers (i.e., the rationals with denominators not divisible by p). (Recall that ℤ_{p} denotes ℤ/pℤ.) If a, b, c ∈ ℤ and p ∤ b, then the congruence a/b ≡ c (mod p) over ℤ′_{p} is equivalent to the usual congruence a ≡ bc (mod p) over ℤ.

Let Ω be the ring of all algebraic integers. For ω_{1}, ω_{2}, γ ∈ Ω, by ω_{1} ≡ ω_{2} (mod γ) we mean ω_{1} − ω_{2} ∈ γΩ. For a, b, m ∈ ℤ it is well known that a − b ∈ mΩ if and only if a − b ∈ mℤ. For m ∈ ℤ and a root ζ of unity, if ζ ≡ 0 (mod m), then 1 = ζζ^{−1} ≡ 0 (mod m) (since ζ, ζ^{−1} ∈ Ω) and hence m must be 1 or −1.

Theorem 1.1 of zero-sum nature and Theorem 1.3 on covers of ℤ are both special cases of part (i) of the following general result.

The Main Theorem. Let (1.3) be a (finite) system of residue classes.

(i) Let m_{s} ∈ ℤ and c_{t}, c_{st} ∈ ℚ for all s ∈ [1, k] and t ∈ [0, l]. Let p be a prime and let 0 ⩽ θ < 1. Assume that whenever I ⊆ [1, k] and {∑_{s∈I} m_{s}/n_{s}} = θ we have ∑_{s∈I} c_{st} − c_{t} ∈ ℤ′_{p} for all t ∈ [0, l]. Set

I = \{I ⊆ [1, k]: \{ ∑_{s∈I} \frac{m_{s}}{n_{s}} \} = θ, ∑_{s∈I} c_{st} − c_{t} ∈ pℤ′_{p} for all t ∈ [1, l]\}.

Then, either we have the inequality

(2.1)  |{ ∑_{s∈I} c_{s0} − c_{0} mod p: I ∈ I}| > m(A) − l(p − 1),

or |{I ∈ I: ∑_{s∈I} c_{s0} − c_{0} ∈ pℤ′_{p}}| ≠ 1 and furthermore

(2.2)  ∑_{\begin{matrix}I∈I \\ ∑_{s∈I} c_{s0}−c_{0}∈pℤ′_{p} \end{matrix}}(−1)^{|I|}e^{2πi ∑_{s∈I} a_{s}m_{s}/n_{s}} ≡ 0 (mod p).

(ii) Suppose that m(A) < m(A′), where A′ = {a_{1}(n_{1}), ⋯, a_{k}(n_{k}), a(n)}, a ∈ ℤ, n ∈ ℤ^{+} and w_{A}(a) = m(A). Let m_{1}, ⋯, m_{k} ∈ ℤ be relatively prime to n_{1}, ⋯, n_{k}, respectively. Let J ⊆ {1 ⩽ s ⩽ k: a ∈ a_{s}(n_{s})} and P (x_{1}, ⋯, x_{k}) ∈ F [x_{1}, ⋯, x_{k}], where F is a field with characteristic not dividing N_{A}. Assume that 0 ⩽ deg P ⩽ |J| and

[ ∏_{j∈J} x_{j}]P (x_{1}, ⋯, x_{k})(x_{1} + ⋯ + x_{k})^{|J|−deg P} ≠ 0.

Let X_{1} = {b_{1}, c_{1}}, ⋯, X_{k} = {b_{k}, c_{k}} be subsets of F such that b_{s} = c_{s} only if a ∈ a_{s}(n_{s}) and s ∉ J. Then for some 0 ⩽ α < 1 we have

(2.3)  |S_{r}| ⩾ |J| − deg P + 1 > 0 for all r = 0, 1, ⋯, n − 1,

where

(2.4)  S_{r} = \{ ∑_{s=1}^{k} x_{s}: x_{s} ∈ X_{s}, P (x_{1}, ⋯, x_{k}) ≠ 0, \{ ∑_{\begin{matrix}s=1 \\ x_{s}≠b_{s} \end{matrix}}^{k} \frac{m_{s}}{n_{s}} \} = \frac{α + r}{n} \}.

When l = θ = 0, c_{s0} ∈ {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 ∑_{s∈I} 2^{s} = ∑_{s∈J} 2^{s}.

In the case n_{1} = ⋯ = n_{k} = n = 1, part (ii) of the Main Theorem yields the following basic lemma of the so-called polynomial method due to Alon, Nathanson and Ruzsa [ANR1], [ANR2]: Let X_{1}, ⋯, X_{k} be subsets of a field F with |X_{s}| = h_{s} ∈ {1, 2} for s ∈ [1, k]. If P (x_{1}, ⋯, x_{k}) ∈ F [x_{1}, ⋯, x_{k}] \ {0}, deg P ⩽ ∑_{s=1}^{k}(h_{s} − 1) and

[x_{1}^{h_{1}−1} ⋯ x_{k}^{h_{k}−1}]P (x_{1}, ⋯, x_{k})(x_{1} + ⋯ + x_{k})^{∑_{s=1}^{k}(h_{s}−1)−deg P} ≠ 0,

then

|{ ∑_{s=1}^{k} x_{s}: x_{s} ∈ X_{s} and P (x_{1}, ⋯, x_{k}) ≠ 0}| ⩾ ∑_{s=1}^{k}(h_{s} − 1) − deg P + 1.

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.

Theorem 2.1. Let (1.3) be an l(p − 1) + 1-cover of ℤ, where l ∈ ℕ and p is a prime. Let m_{1}, ⋯, m_{k} ∈ ℤ and c_{1}, ⋯, c_{k} ∈ ℤ_{p}^{l}. Then for any 0 ⩽ θ < 1 and c ∈ ℤ_{p}^{l} we have

(2.5)  ∑_{\begin{matrix}I⊆[1,k] \\ ∑_{s∈I} c_{s}=c \\ \{∑_{s∈I} m_{s}/n_{s}\}=θ \end{matrix}}(−1)^{|I|}e^{2πi ∑_{s∈I} a_{s}m_{s}/n_{s}} ≡ 0 (mod p);

in particular, there is a nonempty subset I of [1, k] such that ∑_{s∈I} c_{s} = 0 and ∑_{s∈I} m_{s}/n_{s} ∈ ℤ.

Since a system of k copies of 0(1) forms a k-cover of ℤ, 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 ℤ.

In 1984 Alon, Friedland and Kalai [AFK1], [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.

Corollary 2.1. Let G be a loopless graph of l vertices with the edge set {1, ⋯, 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 ℤ, where p is a prime. Then for any m_{1}, ⋯, m_{k} ∈ ℤ we have

H = \{p-regular subgraph H of G: ∑_{s∈E(H)} \frac{m_{s}}{n_{s}} ∈ ℤ\} ≠ ∅,

where E(H) denotes the edge set of the subgraph H; furthermore

(2.6)  ∑_{H∈H}(−1)^{|E(H)|}e^{2πi ∑_{s∈E(H)} a_{s}m_{s}/n_{s}} ≡ −1 (mod p).

Theorem 2.2. Let (1.3) be a system of residue classes with m(A) > (l + 1)(p − 1), where l ∈ ℕ and p is a prime. Let m_{1}, ⋯, m_{k} ∈ ℤ and c_{1}, ⋯, c_{k} ∈ ℤ_{p}^{l}. Then for any c ∈ ℤ_{p}^{l} and r ∈ ℚ we have

(2.7)  ∑_{\begin{matrix}I⊆[1,k] \\ ∑_{s∈I} c_{s}=c \\ ∑_{s∈I} m_{s}/n_{s}∈r+pℤ \end{matrix}}(−1)^{|I|}e^{2πi ∑_{s∈I} a_{s}m_{s}/n_{s}} ≡ 0 (mod p);

in particular, there is a nonempty subset I of [1, k] such that ∑_{s∈I} c_{s} = 0 and ∑_{s∈I} m_{s}/n_{s} ∈ pℤ.

Corollary 2.2. Let (1.3) be a system of residue classes, and let p be a prime.

(i) If 2p − 1 ∈ {w_{A}(x): x ∈ ℤ} ⊆ {2p − 1, 2p}, then for any c_{1}, ⋯, c_{k} ∈ ℤ_{p} there exists an I ⊆ [1, k] such that ∑_{s∈I} 1/n_{s} = p and ∑_{s∈I} c_{s} = 0.

(ii) If (1.3) forms an exact 3p-cover of ℤ, then for any c_{1}, ⋯, c_{k} ∈ ℤ_{p}^{2} with c_{1}+⋯+c_{k} = 0, there exists an I ⊆ [1, k] such that ∑_{s∈I} 1/n_{s} = p and ∑_{s∈I} c_{s} = 0.

The EGZ theorem and Lemma 3.2 of Alon and Dubiner [AD] are parts (i) and (ii) of our Corollary 2.2 in the case n_{1} = ⋯ = 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.

Theorem 2.3. Suppose that (1.3) is an m-cover of ℤ with a_{k}(n_{k}) essential. Let m_{1}, ⋯, m_{k−1} ∈ ℤ be relatively prime to n_{1}, ⋯, n_{k−1}, respectively. Let F be a field with characteristic p not dividing N_{A}, and let X_{1} = {b_{1}, c_{1}}, ⋯, X_{k−1} = {b_{k−1}, c_{k−1}} be any subsets of F with cardinality 2. Then for some 0 ⩽ α < 1 we have

(2.8)  |\{ ∑_{s=1}^{k−1} x_{s}: x_{s} ∈ X_{s}, \{ ∑_{\begin{matrix}1⩽s<k \\ x_{s}=c_{s} \end{matrix}} \frac{m_{s}}{n_{s}} \} = \frac{α + r}{n_{k}} \}| ⩾ min\{p′, m\}

for all r ∈ [0, n_{k} − 1], where p′ = p if p is a prime, and p′ = +∞ if p = 0.

Theorem 2.3 implies the second result stated in the abstract of [S99]. Provided that (1.3) forms an exact m-cover of ℤ, in 1997 the author [S97] proved that for any a = 0, 1, ⋯, mn_{k} − 1 we have

|\{I ⊆ [1, k − 1]: ∑_{s∈I} \frac{1}{n_{s}} = \frac{a}{n_{k}} \}| ⩾ \binom{m − 1}{⌊a/n_{k}⌋}.

We can show that this remains true if (1.3) is only an m-cover of ℤ with ∑_{s=1}^{k−1} 1/n_{s} < m.

Corollary 2.3. Suppose that (1.3) is a p-cover of ℤ with a_{k}(n_{k}) essential, where p is a prime not dividing N_{A}. Let m_{1}, ⋯, m_{k−1} ∈ ℤ be relatively prime to n_{1}, ⋯, n_{k−1}, respectively. Then, for any c, c_{1}, ⋯, c_{k−1} ∈ ℤ_{p} with c_{1} ⋯ c_{k−1} ≠ 0 the set

(2.9)  \{\{ ∑_{s∈I} \frac{m_{s}}{n_{s}} \}: I ⊆ [1, k − 1] and ∑_{s∈I} c_{s} = c\}

contains an arithmetic progression of length n_{k} with common difference 1/n_{k}.

Theorem 2.4. Assume that (1.3) does not form an m + 1-cover of ℤ but A′ = {a_{1}(n_{1}), ⋯, a_{k}(n_{k}), a(n)} does, where a ∈ ℤ and n ∈ ℤ^{+}. Let m_{1}, ⋯, m_{k} be integers relatively prime to n_{1}, ⋯, n_{k}, respectively. Let F be a field of prime characteristic p, and let a_{ij}, b_{i} ∈ F for all i ∈ [1, m] and j ∈ [1, k]. Set

(2.10)  X = { ∑_{j=1}^{k} x_{j}: x_{j} ∈ [0, p − 1] and ∑_{j=1}^{k} x_{j}a_{ij} ≠ b_{i} for all i ∈ [1, m]}.

If p does not divide N_{A} and the matrix (a_{ij})_{1⩽i⩽m,1⩽j⩽k} has rank m, then the set

(2.11)  \{\{ ∑_{s∈I} \frac{m_{s}}{n_{s}} \}: I ⊆ [1, k] and |I| ∈ X\}

contains an arithmetic progression of length n with common difference 1/n.

We mention that Theorem 1.2 follows from Theorem 2.4.

Theorem 2.5. Let (1.3) be an m-cover of ℤ with a_{k}(n_{k}) essential and n_{k} = N_{A}. Let m_{1}, ⋯, m_{k−1} ∈ ℤ be relatively prime to n_{1}, ⋯, n_{k−1}, respectively. Then for any r ∈ [0, N_{A} − 1] we have the inequality

(2.12)  |\{I ⊆ [1, k − 1]: \{ ∑_{s∈I} \frac{m_{s}}{n_{s}} \} = \frac{r}{N_{A}} \}| ⩾ 2^{m−1}.

Theorem 2.5 in the special case m = m_{1} = ⋯ = m_{k−1} = 1 was first observed by Z. H. Sun on the basis of the author’s work [S95]. If m_{1}, ⋯, m_{n−1} ∈ ℤ are relatively prime to n, then by applying Theorem 2.5 to the disjoint cover {r(n)}_{r=0}^{n−1} we find that {∑_{s∈I} m_{s} : I ⊆ [1, n − 1]} contains a complete system of residues modulo n.

3. Two technical lemmas

Lemma 3.1. Let R be a ring with identity, and let f(x_{1}, ⋯, x_{k}) be a polynomial over R. If J ⊆ [1, k] and |J| ⩾ deg f, then we have the identity

(3.1)  ∑_{I⊆J}(−1)^{|J|−|I|}f([1 ∈ I], ⋯, [k ∈ I]) = [ ∏_{j∈J} x_{j}]f(x_{1}, ⋯, x_{k}).

Our Lemma 3.1 is powerful; it implies Lemma 2.2 of [R] (used by Rónyai in his study of the Kemnitz conjecture), as well as Combinatorial Nullstellenstaz in the case l_{1}, ⋯, l_{k} ∈ {0, 1}.

By applying Lemma 3.1, we obtain the following two theorems.

Theorem 3.1. Let p be a prime. If c_{st}, c_{t} ∈ ℤ for all s ∈ [1, l(p − 1)] and t ∈ [1, l], then

(3.2)  ∑_{\begin{matrix}I_{1}∪···∪I_{l}=[1,l(p−1)] \\ |I_{1}|=···=|I_{l}|=p−1 \end{matrix}} ∏_{t=1}^{l} ∏_{s∈I_{t}} c_{st} ≡ ∑_{\begin{matrix}I⊆[1,l(p−1)] \\ p|∑_{s∈I} c_{st}−c_{t} for t∈[1,l] \end{matrix}}(−1)^{|I|} (mod p).

In particular, if c, c_{1}, ⋯, c_{2p−2} ∈ ℤ, then

(3.3)  ∑_{\begin{matrix}I⊆[1,p−1] \\ p|∑_{s∈I} c_{s}−c \end{matrix}}(−1)^{|I|} ≡ c_{1} ⋯ c_{p−1} (mod p)

and

|\{I ⊆ [1, 2p − 2]: |I| = p − 1, p | ∑_{s∈I} c_{s} − c\}| ≡ ∑_{\begin{matrix}I⊆[1,2p−2] \\ |I|=p−1 \end{matrix}} ∏_{s∈I} c_{s} (mod p).

We mention that Theorem 3.1 implies Theorem 1.1.

Theorem 3.2. Let a_{1}, ⋯, a_{4p−3}, b_{1}, ⋯, b_{4p−3} ∈ ℤ, where p is a prime. If

(3.4)  ∑_{\begin{matrix}I,J⊆[1,4p−3] \\ |I|=|J|=p−1 \\ I∩J=∅ \end{matrix}} ( ∏_{i∈I} a_{i})( ∏_{j∈J} b_{j}) ≢ 2 (mod p),

then there exists an I ⊆ [1, 4p − 3] with |I| = p such that ∑_{s∈I} a_{s} ≡ ∑_{s∈I} b_{s} ≡ 0 (mod p).

This provides an advance on the Kemnitz conjecture.

Our proof of the Main Theorem depends heavily on the following lemma.

Lemma 3.2. Let (1.3) be a system of residue classes, and let m_{1}, ⋯, m_{k} be any integers. Let F be a field containing an element ζ of (multiplicative) order N_{A}, and let f(x_{1}, ⋯, x_{k}) ∈ F [x_{1}, ⋯, x_{k}] and deg f ⩽ m(A). Set I_{z} = {1 ⩽ s ⩽ k: z ∈ a_{s}(n_{s})} for z ∈ ℤ. If [∏_{s∈I_{z}} x_{s}]f(x_{1}, ⋯, x_{k}) = 0 for all z ∈ ℤ, then

∑_{\begin{matrix}I⊆[1,k] \\ \{∑_{s∈I} m_{s}/n_{s}\}=θ \end{matrix}}(−1)^{|I|}f([1 ∈ I], ⋯, [k ∈ I])ζ^{N_{A} ∑_{s∈I} a_{s}m_{s}/n_{s}} = 0

for all 0 ⩽ θ < 1. The converse holds when m_{1}, ⋯, m_{k} are relatively prime to n_{1}, ⋯, n_{k}, respectively.

Observe that Lemma 3.2 in the case n_{1} = ⋯ = n_{k} = 1 follows from Lemma 3.1.

References

[AGP] W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. 139 (1994), 703–722. MR 95k:11114

[A99] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 7–29. MR 2000b:05001

[A03] N. Alon, Discrete mathematics: methods and challenges, in: Proceedings of the International Congress of Mathematicians (Beijing, 2002), Vol. I, Higher Education Press, Beijing, 2003, pp. 119–136.

[AD] N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in: Combinatorics, Paul Erdös is Eighty, János Bolyai Math. Soc., Budapest, 1993, pp. 33–50. MR 94j:11016

[AFK1] N. Alon, S. Friedland and G. Kalai, Regular subgraphs of almost regular graphs, J. Combin. Theory Ser. B 37 (1984), 79–91. MR 86d:05064a

[AFK2] N. Alon, S. Friedland and G. Kalai, Every 4-regular graph plus an edge contains a 3regular subgraph, J. Combin. Theory Ser. B 37 (1984), 92–93. MR 86d:05064b [AF] N. Alon and Z. Füredi, Covering the cube by affine hyperplanes, European J. Combin.

14 (1993), 79–83. MR 94a:52039

[ANR1] N. Alon, M. B. Nathanson and I. Z. Ruzsa, Adding distinct congruence classes modulo a prime, Amer. Math. Monthly 102 (1995), 250–255. MR 95k:11009

[ANR2] N. Alon, M. B. Nathanson and I. Z. Ruzsa, The polynomial method and restricted sums of congruence classes, J. Number Theory 56 (1996), 404–417. MR 96k:11011

[AT] N. Alon and M. Tarsi, A nowhere-zero point in linear mappings, Combinatorica 9 (1989), 393–395. MR 92a:11147

[C] Y. Caro, Zero-sum problems—a survey, Discrete Math. 152 (1996), 93–113. MR 97c:05156

[Cr] R. Crocker, On a sum of a prime and two powers of two, Pacific J. Math. 36 (1971), 103–107. MR 43:3200

[DKSS] S. Dasgupta, G. Károlyi, O. Serra and B. Szegedy, Transversals of additive Latin squares, Israel J. Math. 126 (2001), 17–28. MR 2002j:05027

[DH] J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), 140–146. MR 95i:11007

[E] P. Erdös, On integers of the form 2^{k} +p and some related problems, Summa Brasil. Math. 2 (1950), 113–123. MR 13:437i

[EGZ] P. Erdös, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Research Council Israel 10 (1961), 41–43.

[EH] P. Erdös and H. Heilbronn, On the addition of residue classes mod p, Acta Arith. 9 (1964), 149–159. MR 29:3463

[G] W. D. Gao, Two addition theorems on groups of prime order, J. Number Theory 56 (1996), 211–213. MR 96m:11008

[HS] Q. H. Hou and Z. W. Sun, Restricted sums in a field, Acta Arith. 102 (2002), 239–249. MR 2003e:11025

[K] A. Kemnitz, On a lattice point problem, Ars Combin. 16 (1983), 151–160. MR 85c:52022 [LS] J. X. Liu and Z. W. Sun, Sums of subsets with polynomial restrictions, J. Number Theory

97 (2002), 301–304.

[N] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Graduate texts in mathematics; 165), Springer-Verlag, New York, 1996. MR 98f:11011

[O] J. E. Olson, A combinatorial problem on finite abelian groups (I), J. Number Theory 1 (1969), 8–10. MR 38:5922

[PS] H. Pan and Z. W. Sun, A lower bound for |{a + b: a ∈ A, b ∈ B, P (a, b) ≠ 0}|, J. Combin. Theory Ser. A 100 (2002), 387–393.

[P] Š. Porubský, On m times covering systems of congruences, Acta Arith. 29 (1976), 159– 169. MR 53:2884

[P-S] Š. Porubský and J. Schönheim, Covering systems of Paul Erdös: past, present and future, in: Paul Erdös and his Mathematics. I (edited by G. Halász, L. Lovász, M. Simonvits, V. T. Sós), Bolyai Soc. Math. Studies 11, Budapest, 2002, pp. 581–627.

[R] L. Rónyai, On a conjecture of Kemnitz, Combinatorica 20 (2000), 569–573. MR 2001k:11025

[S95] Z. W. Sun, Covering the integers by arithmetic sequences, Acta Arith. 72 (1995), 109– 129. MR 96k:11013

[S96] Z. W. Sun, Covering the integers by arithmetic sequences II, Trans. Amer. Math. Soc. 348 (1996), 4279–4320. MR 97c:11011

[S97] Z. W. Sun, Exact m-covers and the linear form ∑_{s=1}^{k} x_{s}/n_{s}, Acta Arith. 81 (1997), 175–198. MR 98h:11019

[S99] Z. W. Sun, On covering multiplicity, Proc. Amer. Math. Soc. 127 (1999), 1293–1300. MR 99h:11012

[S00] Z. W. Sun, On integers not of the form ±p^{a} ± q^{b}, Proc. Amer. Math. Soc. 128 (2000), 997–1002. MR 2000i:11157

[S01] Z. W. Sun, Algebraic approaches to periodic arithmetical maps, J. Algebra 240 (2001), 723–743. MR 2002f:11009

[S03] Z. W. Sun, A unified theory of zero-sum problems, subset sums and covers of ℤ, preprint, Nanjing University, March 1, 2003. arXiv:math.NT/0305369 [Z89] M. Z. Zhang, A note on covering systems of residue classes, J. Sichuan Univ. (Nat. Sci.

Ed.) 26 (1989), Special Issue, 185–188. MR 92c:11003 [Z91] M. Z. Zhang, On irreducible exactly m times covering system of residue classes, J. Sichuan

Univ. (Nat. Sci. Ed.) 28 (1991), 403–408. MR 92j:11001

Department of Mathematics, Nanjing University, Nanjing 210093, People’s Republic of China

   E-mail address: zwsun@nju.edu.cn