INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A30

DAVENPORT CONSTANT WITH WEIGHTS AND SOME RELATED QUESTIONS

Sukumar Das Adhikari

Harish-Chandra Research Institute, Chhatnag Road, Jhusi, Allahabad 211 019, INDIA

                           adhikari@mri.ernet.in

Purusottam Rath

Harish-Chandra Research Institute, Chhatnag Road, Jhusi, Allahabad 211 019, INDIA

                             rath@mri.ernet.in

Received: 5/22/06, Revised: 7/5/06, Accepted: 8/12/06, Published: 10/20/06

Abstract

Let n ∈ ℕ and let A ⊆ ℤ/nℤ be such that A does not contain 0 and it is non–empty. Generalizing a well known constant, E_{A}(n) is defined to be the least t ∈ ℕ such that for all sequences (x_{1}, …, x_{t}) ∈ ℤ^{t}, there exist indices j_{1}, …, j_{n} ∈ ℕ, 1 ≤ j_{1} < ⋯ < j_{n} ≤ t, and (ϑ_{1}, ⋯, ϑ_{n}) ∈ A^{n} with ∑_{i=1}^{n} ϑ_{i}x_{j_{i}} ≡ 0 (mod n). Similarly, for any such set A, we define the Davenport Constant of ℤ/nℤ with weight A denoted by D_{A}(n) to be the least natural number k such that for any sequence (x_{1}, ⋯, x_{k}) ∈ ℤ^{k}, there exists a non-empty subsequence {x_{j_{1}}, ⋯, x_{j_{l}}} and (a_{1}, ⋯ a_{l}) ∈ A^{l} such that ∑_{i=1}^{l} a_{i}x_{j_{i}} ≡ 0 (mod n). In the present paper, in the special case where n = p is a prime, we determine the values of D_{A}(p) and E_{A}(p) where A is {1, 2, ⋯, r} or the set of quadratic residues (mod p).

1. Introduction

Here we shall be concerned with certain generalizations of two important combinatorial invariants related to zero-sum problems (for detailed accounts one may see [10], [3], [13], [9]) in finite abelian groups.

For an abelian group G, the Davenport constant D(G) is defined to be the smallest natural number k such that any sequence of k elements in G has a non-empty subsequence whose sum is zero (the identity element). For an abelian group G of cardinality n, another interesting constant is the smallest natural number k such that any sequence of k elements in G has a subsequence of length n whose sum is zero; we shall denote it by E(G).

The following result due to Gao [8] (see also [10], Proposition 5.7.9) connects these two invariants.

Theorem 1. If G is a finite abelian group of order n, then E(G) = D(G) + n − 1.

For the particular group ℤ/nℤ, the following generalization of E(G) was considered in [2] recently. Let n ∈ ℕ and assume A ⊆ ℤ/nℤ. Then E_{A}(n) is the least t ∈ ℕ such that for all sequences (x_{1}, …, x_{t}) ∈ ℤ^{t} there exist indices j_{1}, …, j_{n} ∈ ℕ, 1 ≤ j_{1} < ⋯ < j_{n} ≤ t, and (ϑ_{1}, ⋯, ϑ_{n}) ∈ A^{n} with

∑_{i=1}^{n} ϑ_{i}x_{j_{i}} ≡ 0 (mod n).

To avoid trivial cases, one assumes that the weight set A does not contain 0 and it is non– empty.

Similarly, for any such set A ⊂ ℤ/nℤ \ {0} of weights, we define the Davenport Constant of ℤ/nℤ with weight A denoted by D_{A}(n) to be the least natural number k such that for any sequence (x_{1}, ⋯, x_{k}) ∈ ℤ^{k}, there exists a non-empty subsequence {x_{j_{1}}, ⋯, x_{j_{l}}} and (a_{1}, ⋯ a_{l}) ∈ A^{l} such that

∑_{i=1}^{l} a_{i}x_{j_{i}} ≡ 0 (mod n).

Thus, for the group G = ℤ/nℤ, if we take A = {1}, then E_{A}(n) and D_{A}(n) are respectively E(G) and D(G) as defined earlier.

For several sets A ⊂ ℤ/nℤ \ {0} of weights, exact values of E_{A}(n) and D_{A}(n) have been determined: The case A = {1} is classical and is covered by the well-known theorem (EGZ theorem) due to Erdős, Ginzburg and Ziv [6] (one may also see [11] or [10]) and Theorem 1 is also applicable; the case A = {1, −1}, was done in [2] where it is shown that E_{A}(n) = n+[log_{2} n]. Furthermore, by the pigeonhole principle (see [2]), D_{A}(n) ≤ [log_{2} n]+1, and by considering the sequence (1, 2, …, 2^{r}), where r is defined by 2^{r+1} ≤ n < 2^{r+2}, it follows that D_{A}(n) ≥ [log_{2} n]+1; the case observed in [2] shows that for A = {1, 2 ⋯ n−1} we have E_{A}(n) = n+1. In this case, it is easy to see that D_{A}(n) = 2; lastly, settling a conjecture from [2], it was proved in [7] that for A = (ℤ/nℤ)^{∗} = {a : (a, n) = 1}, E_{A}(n) = n + Ω(n), where Ω(n) denotes the number of prime factors of n, multiplicity included.

It is not difficult to observe that

E_{A}(n) ≥ D_{A}(n) + n − 1 for any A ⊂ ℤ/nℤ \ {0}.  (1)

Taking A = (ℤ/nℤ)^{∗}, it follows from (1) and the above result that D_{A}(n) ≤ 1+Ω(n). On the other hand, in this case, writing n = p_{1} ⋯ p_{s} as a product of s = Ω(n) (not necessarily distinct) primes, the sequence (1, p_{1}, p_{1}p_{2}, …, p_{1}p_{2} ⋯ p_{s−1}) gives the lower bound D_{A}(n) ≥ 1 + Ω(n).

Thus, in all these above cases, namely when A is one of the sets appearing in the chain {1} ⊂ {1, −1} ⊂ (ℤ/nℤ)^{∗} ⊂ {1, 2, ⋯, n − 1}, one has E_{A}(n) = D_{A}(n) + n − 1.

In the present paper, in the special case where n = p is a prime (other than 2, the trivial case), we determine the values of D_{A}(p) and E_{A}(p) where A is {1, 2, ⋯, r} or the set of quadratic residues (mod p). In both cases, the equality E_{A}(p) = D_{A}(p) + p − 1 holds.

Perhaps one would expect that for any set A ⊂ ℤ/nℤ \ {0} of weights, the equality E_{A}(n) = D_{A}(n) + n − 1 holds.

2. D_{A}(p) and E_{A}(p) for certain subsets A of (ℤ/pℤ)^{∗}

In what follows, p will always denote an odd prime.

Theorem 2. Let A = {1, 2, ⋯, r}, where r is an integer such that 1 < r < p. We have

(i) D_{A}(p) = ⌈\frac{p}{r}⌉, where for a real number x, ⌈x⌉ denotes the smallest integer ≥ x,

(ii) E_{A}(p) = p − 1 + D_{A}(p).

Proof. Consider any sequence S = (s_{1}, ⋯, s_{⌈ \frac{p}{r} ⌉}) of elements of ℤ/pℤ of length ⌈\frac{p}{r}⌉. Considering the sequence

S′ = (\overbrace{s_{1}, s_{1}, ⋯, s_{1}}^{r times}, \overbrace{s_{2}, s_{2}, ⋯, s_{2}}^{r times}, ⋯, \overbrace{s_{⌈ \frac{p}{r} ⌉}, ⋯, s_{⌈ \frac{p}{r} ⌉}}^{r times}),

obtained from S by repeating each element r times, and observing that the length of this sequence is ≥ p, it follows that

D_{A}(p) ≤ ⌈\frac{p}{r}⌉ .  (2)

On the other hand, considering the sequence (\overbrace{1, 1, ⋯, 1}^{(⌈ \frac{p}{r} ⌉−1) times}), for any non-empty subsequence (s_{j_{1}}, ⋯, s_{j_{l}}) of this sequence and (a_{1}, ⋯ a_{l}) ∈ A^{l},

0 < ∑_{i=1}^{l} a_{i}s_{j_{i}} < rl ≤ p − 1.

Therefore,

D_{A}(p) ≥ ⌈\frac{p}{r}⌉ .  (3)

From equations (2) and (3), part (i) follows.

Now, consider any sequence S = (s_{1}, ⋯, s_{N}) of elements of ℤ/pℤ of length

N = p − 1 + ⌈\frac{p}{r}⌉ .

Case I. (The sequence S has at least p non-zero elements in it).

Let (s_{i_{1}}, s_{i_{2}}, ⋯, s_{i_{p}}) be a subsequence of S of p non-zero elements and let A_{k} = {s_{i_{k}}, 2s_{i_{k}}} for k = 1, ⋯, p. Since |A_{k}| = 2 for all k, by the Cauchy-Davenport Theorem (see [11], Theorem 2.3) it follows that |A_{1} + A_{2} + ⋯ + A_{p}| ≥ p and hence

∑_{k=1}^{p} a_{k}s_{i_{k}} = 0, where a_{k} ∈ {1, 2} ⊂ A.

Case II. (The sequence S has less than p non-zero elements in it).

In this case, at least ⌈\frac{p}{r}⌉ elements of the sequence are equal to zero. We reorder the sequence in such a way that s_{1} = s_{2} = ⋯ = s_{t} = 0 and the remaining elements are non-zero. We have N − t < p. Let B = {r_{1}, …, r_{l}} ⊆ {t + 1, t + 2, ⋯, N} be maximal with respect to the property that there exist a_{1}, ⋯, a_{l} ∈ {1, 2, ⋯, r} with

∑_{j=1}^{l} a_{j}s_{r_{j}} = 0.

Now we claim that l + t ≥ p. Indeed, if this were not the case then the set C = \{t + 1, ⋯, N\} \ \{r_{1}, ⋯, r_{l}\} would contain N − t − l ≥ ⌈\frac{p}{r}⌉ elements. Hence by part (i), there would exist a non–empty B′ ⊂ C and a_{j} ∈ {1, 2, ⋯, r} for each j ∈ B′ such that

∑_{j∈B′} a_{j}s_{j} = 0.

Now, B∪B′ would contradict the maximality of B. Hence l+t ≥ p. Therefore, appending the sequence B to (s_{1}, s_{2}, ⋯, s_{p−l}) = (0, 0, ⋯, 0), we get a sequence of length p with desired property.

From Cases (I) and (II), and part (i), E_{A}(p) ≤ p − 1 + ⌈\frac{p}{r}⌉ = p − 1 + D_{A}(p), and hence from equation (1), part (ii) follows.

Theorem 3. Let A be the set of quadratic residues (mod p). That is, A consists of all the squares in (ℤ/pℤ)^{∗}. We have

(i) D_{A}(p) = 3,

(ii) E_{A}(p) = p + 2.

Proof. Given any sequence S = (s_{1}, ⋯, s_{p+2}) of elements of ℤ/pℤ of length p+2, we consider the following system of equations in (p + 2) variables over the finite field 𝔽_{p}:

∑_{i=1}^{p+2} s_{i}x_{i}^{2} = 0, ∑_{i=1}^{p+2} x_{i}^{p−1} = 0.

By Chevalley - Warning Theorem (see [12] or [1], for instance), there is a nontrivial solution (y_{1}, ⋯, y_{p+2}) of the above system. Writing I = {i : y_{i} ≠ 0}, from the first equation it follows that ∑_{i∈I} a_{i}s_{i} = 0 where a_{i}’s belong to the set of squares in (ℤ/pℤ)^{∗}. By Fermat’s little theorem, from the second equation we have |I| = p. Hence

E_{A}(p) ≤ p + 2.  (4)

From (1), we have E_{A}(p) ≥ D_{A}(p) + p − 1, and hence by (4),

D_{A}(p) ≤ E_{A}(p) − p + 1 ≤ 3.  (5)

On the other hand, considering a sequence v_{1}, −v_{2}, where v_{1} is a quadratic residue and v_{2} a quadratic non-residue (mod p), for two elements a_{1}, a_{2} ∈ A, a_{1}v_{1} + a_{2}(−v_{2}) = 0 implies a_{1}v_{1} = a_{2}v_{2}, – an absurdity, since a_{1}v_{1} is a quadratic residue and a_{2}v_{2} a non-residue.

Therefore, D_{A}(p) ≥ 3 and this together with (5) proves part (i) of the theorem.

Again, since E_{A}(p) ≥ D_{A}(p) + p − 1, by part (i), E_{A}(p) ≥ p + 2, which, together with (4) gives part (ii) of the theorem.

Remarks. First, we note that the values of D_{A}(p) and E_{A}(p) remain unchanged if one replaces A by cA = {ca|a ∈ A} for any c ∈ (ℤ/pℤ)^{∗}. Hence, in particular, the statement of Theorem 3 holds with A as the set of quadratic non-residues (mod p).

Finally, in Theorem 2, if A ⊂ {1, 2, ⋯, r}, where r is an integer such that 1 < r < p, then also the lower bound (3) for D_{A}(p) (and hence a corresponding lower bound for E_{A}(p), namely E_{A}(p) ≥ p − 1 + ⌈\frac{p}{r}⌉, obtained by (1)) holds. However, taking A = \{1, p − 1\}, for instance, this may not be a good lower bound in general. It is interesting to note the difference in the values of the constant D_{A}(p) (from Theorem 2 and the result in [2] quoted in the introduction) corresponding to the weight sets {1, 2} and {1, −1} having the same cardinality.

Acknowledgement. We thank the referee whose suggestions helped us improve the presentation of the paper.

References

[1] S. D. Adhikari, Aspects of combinatorics and combinatorial number theory, Narosa, New Delhi, 2002.

[2] S. D. Adhikari, Y. G. Chen, J. B. Friedlander, S. V. Konyagin and F. Pappalardi, Contributions to zero–sum problems, Discrete Math. 306, 1–10 (2006).

[3] Y. Caro, Zero-sum problems – A survey, Discrete Math. 152, 93–113 (1996).

[4] A. L. Cauchy, Recherches sur les nombres, J. Ecôle Polytech. 9, 99–123 (1813).

[5] H. Davenport, On the addition of residue classes, J. London Math. Soc. 22, 100–101 (1947).

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

[7] Florian Luca, A generalization of a classical zero-sum problem, Preprint.

[8] W. D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory, 58, 100–103 (1996).

[9] W. D. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: A survey, to appear.

[10] A. Geroldinger and F. Halter-Koch, Non-Unique Factorizations, Chapman & Hall, CRC (2006).

[11] Melvyn B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer, 1996.

[12] J. -P. Serre, A course in Arithmetic, Springer, 1973.

[13] R. Thangadurai, Interplay between four conjectures on certain zero-sum problems, Expo. Math. 20, no. 3, 215–228 (2002).