Square-Weighted Zero-Sum Constants

Krishnendu Paul and Shameek Paul School of Mathematical Sciences

Ramakrishna Mission Vivekananda Educational and Research Institute

P.O. Belur Math, Dist. Howrah, West Bengal 711202 India

              krishnendu.p.math18@gm.rkmvu.ac.in
                   shameek.paul@rkmvu.ac.in

Abstract

Let A ⊆ ℤ_{n} be a subset. A sequence S = (x_{1}, …, x_{k}) in ℤ_{n} is said to be an Aweighted zero-sum sequence if there exist a_{1}, …, a_{k} ∈ A such that a_{1}x_{1}+⋯+a_{k}x_{k} = 0. By a square, we mean a non-zero square in ℤ_{n}. We determine the smallest natural number k, such that every sequence in ℤ_{n} whose length is k has a square-weighted zero-sum subsequence. We also determine the smallest natural number k, such that every sequence in ℤ_{n} whose length is k has a square-weighted zero-sum subsequence whose terms are consecutive terms of the given sequence.

1 Introduction

For a finite set A, we let |A| denote the number of elements of A. For a, b ∈ ℤ with a ≤ b, we let [a, b] denote the set {x ∈ ℤ : a ≤ x ≤ b}.

Let R be a commutative ring with unity, M be an R-module, and A ⊆ R. A subsequence T of a sequence S = (x_{1}, x_{2}, …, x_{k}) in M is called an A-weighted zero-sum subsequence if the set J = {i : x_{i} ∈ T } is non-empty, and for every i ∈ J there exists a_{i} ∈ A such that ∑_{i∈J} a_{i}x_{i} = 0 where 0 is the identity element of M.

For a finite R-module M and A ⊆ R, the A-weighted Davenport constant of M denoted by D_{A} is defined to be the least positive integer k, such that every sequence in M whose length is k, has an A-weighted zero-sum subsequence.

Adhikari and Chen [1] introduced this constant for the ring R = ℤ, i.e., for abelian groups. We define the constant C_{A} to be the least positive integer k, such that every sequence in M whose length is k, has an A-weighted zero-sum subsequence whose terms are consecutive terms. Remark 1. It is easy to observe that D_{A} ≤ C_{A} ≤ |M|.

We also denote the ring ℤ/nℤ by ℤ_{n}. Let U(n) denote the group of units in ℤ_{n} and U(n)^{2} denote the set {x^{2} : x ∈ U(n)}. For a divisor m of n, the homomorphism f_{n,m} : ℤ_{n} → ℤ_{m} is given by f_{n,m}(a + nℤ) = a + mℤ. Mondal et al. [7, Lem. 7] showed that the image of U(n) under f_{n,m} is U(m).

Let p be a prime divisor of n. We say that v_{p}(n) = r if p^{r} | n and p^{r+1} ∤ n. Suppose r = v_{p}(n). For every x ∈ ℤ_{n} we denote the image of x under f_{n, p^{r}} by x^{(p)}. Given a sequence S = (x_{1}, …, x_{l}) in ℤ_{n}, we get a sequence

S^{(p)} = (x_{1}^{(p)}, …, x_{l}^{(p)}) in ℤ_{p^{r}}.

From this point onwards, we will only consider the case when M = R = ℤ_{n}.

Adhikari and Rath [3] showed that D_{U(p)^{2}} = 3 when p is an odd prime. Let Ω(n) denote the number of prime factors of n counted with multiplicity. Grynkiewicz and Hennecart [5] showed that D_{U(n)^{2}} ≥ 2Ω(n) + min{v_{3}(n), v_{5}(n)} + 1 when n is odd, with equality if either 3 ∤ n or v_{3}(n) ≥ v_{5}(n). This extends a result of Chintamani and Moriya [4], and another of Adhikari, David, and Urroz [2].

These results lead quite naturally to the question of determining the value of D_{S(n)} where

S(n) = { x^{2} : x ∈ ℤ_{n}} \ {0}.

For an odd prime p we observe that S(p) = U(p)^{2}. We determine the value of D_{S(n)} for every n and show that it depends on the parity of n when n is a square, and on the parity of v_{2}(n) when n is not a square. We also investigate the value of C_{S(n)}.

We show that C_{U(25)^{2}} = 9, adding to the results which were obtained by Mondal et al. [8]. Using this fact, we get that C_{S(n)} ≤ 9 when n is an odd square. The values of D_{S(n)} for all n ∈ [2, 37] are given in the following table. When p is an odd prime, we see that S(p) = U(p)^{2} and so the value of D_{S(p)} had been determined in Adhikari and Rath [3].

\begin{matrix}n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ D_{S(n)} & 2 & 3 & 4 & 3 & 2 & 3 & 2 & 5 & 2 & 3 & 3 & 3 & 2 & 3 & 4 & 3 & 2 & 3 \end{matrix}

\begin{matrix}n & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 \\ D_{S(n)} & 3 & 3 & 2 & 3 & 2 & 5 & 2 & 3 & 3 & 3 & 2 & 3 & 2 & 3 & 2 & 3 & 4 & 3 \end{matrix}

Table 1: Values of D_{S(n)} for all n ∈ [2, 37].

The only values of n in the set [2, 37] for which C_{S(n)} differs from D_{S(n)} are 9 and 25. The smallest n for which we have not been able to determine C_{S(n)} is 81. In this article, we have obtained the following results:

• We determine the size of S(n) for every n.

• When n is a square, we get that D_{S(n)} = 4 or 5 when n is even or odd respectively.

• When n is not a square, we get that D_{S(n)} = 2 or 3 when v_{2}(n) is odd or even respectively.

• When n is not a square of an odd number, we get that C_{S(n)} = D_{S(n)}.

• When n is a square of an odd, squarefree number, we get that C_{S(n)} = 9.

• When n is a square of an odd number m such that m is divisible by p^{2} where p is a prime which is at least seven, we get that C_{S(n)} = D_{S(n)}.

2 The size of S(n)

Observation 2. Let n = p_{1}^{r_{1}} ⋯ p_{s}^{r_{s}} where the p_{i}’s are distinct primes. By the Chinese remainder theorem we get an isomorphism

φ : ℤ/nℤ → ℤ/p_{1}^{r_{1}}ℤ × ⋯ × ℤ/p_{s}^{r_{s}}ℤ

given by φ(a) = (a^{(p_{1})}, …, a^{(p_{s})}). As φ is an isomorphism, we have that a ∈ S(n) if and only if for every prime divisor q of n, we have that a^{(q)} is a square and there exists a prime divisor p of n such that a^{(p)} ≠ 0.

Hence, it follows that

|S(n)| + 1 = ( |S(p_{1}^{r_{1}})| + 1 ) ⋯ ( |S(p_{s}^{r_{s}})| + 1 ).

Thus, it is enough to determine the size of S(p^{r}) where p is a prime and r is a positive integer.

Observation 3. Let p be a prime, r be a positive integer, and a ∈ ℤ_{p^{r}} \ {0}. Then there exists a unique k ∈ [0, r − 1] such that a = p^{k}u where u is a unit.

For a real number x, we let ⌊x⌋ denote the greatest integer which is at most equal to x.

Lemma 4. Let p be a prime, r be a positive integer, and l = ⌊(r − 1)/2⌋. Then we have that S(p^{r}) = ⋃_{k∈[0, l]} p^{2k}U(p^{r})^{2}. Also, this is a disjoint union.

Proof. Let a ∈ S(p^{r}). Then there exists u ∈ U(p^{r}) and k ∈ [0, r − 1] such that a = p^{2k}u^{2}. As a ≠ 0, by Observation 3 we see that 2k ∈ [0, r − 1] and so k ∈ [0, l].

We omit the proof of the next result.

Lemma 5. Let p be a prime, r be a natural number, and l = ⌊(r − 1)/2⌋. Then for every k ∈ [0, l] we have that | p^{2k} U(p^{r})^{2} | = | U(p^{r−2k})^{2} |.

The next result follows from Lemmas 4 and 5.

Theorem 6. If r is even

|S(p^{r})| = |U(p^{r})^{2}| + |U(p^{r−2})^{2}| + ⋯ + |U(p^{4})^{2}| + |U(p^{2})^{2}|

and if r is odd

|S(p^{r})| = |U(p^{r})^{2}| + |U(p^{r−2})^{2}| + ⋯ + |U(p^{3})^{2}| + |U(p)^{2}|.

It remains to determine the size of U(n)^{2} when n is a prime power. Let n = p^{r} where p is an odd prime and r is a positive integer. Ireland and Rosen [6, Thm. 2, p. 43] have shown that U(n) is a cyclic group. So there is exactly one element of order two in U(n). Thus, the kernel of the onto map U(n) → U(n)^{2} given by x ↦ x^{2} has order two. Hence, we see that U(n)^{2} has index two in U(n). So it follows that

|U(n)^{2}| = |U(n)|/2 = p^{r−1}(p − 1)/2.

We have that U(4)^{2} = U(2)^{2} = {1}. Let n = 2^{r} where r is at least three. Ireland and Rosen [6, Thm. 2′, p. 43] have shown that U(n) ≃ ℤ_{2} × ℤ_{2^{r−2}}. So there are exactly three elements of order two in U(n). Thus, the kernel of the onto map U(n) → U(n)^{2} given by x ↦ x^{2} has order four. Hence, we see that U(n)^{2} has index four in U(n). So it follows that

|U(n)^{2}| = |U(n)|/4 = 2^{r−1}/4 = 2^{r−3}.

3 Some general results

Lemma 7. Let S be a sequence in ℤ_{n} and p be a prime divisor of n such that v_{p}(n) = r. Suppose the sequence S^{(p)} is an S(p^{r})-weighted zero-sum sequence. Then the sequence S is an S(n)-weighted zero-sum sequence.

Proof. Let S = (x_{1}, …, x_{l}). As S^{(p)} = (x_{1}^{(p)}, …, x_{l}^{(p)}), there exist b_{1}, …, b_{l} ∈ S(p^{r}) such that

b_{1}x_{1}^{(p)} + ⋯ + b_{l}x_{l}^{(p)} = 0.

By Observation 2 we see that for every i ∈ [1, l] there exists a_{i} ∈ S(n) such that a_{i}^{(p)} = b_{i} and for each prime divisor q of n/p^{r} we have a_{i}^{(q)} = 0. Let φ be the isomorphism given by the Chinese remainder theorem as in Observation 2. Since we get φ(a_{1}x_{1} + ⋯ + a_{l}x_{l}) = 0, it follows that a_{1}x_{1} + ⋯ + a_{l}x_{l} = 0. Hence, we see that S is an S(n)-weighted zero-sum sequence.

Corollary 8. Let p be a prime divisor of n and r = v_{p}(n). Then we have that C_{S(n)} ≤ C_{S(p^{r})}.

Proof. Let m = p^{r}. Suppose S is a sequence in ℤ_{n} having length C_{S(m)}. As S^{(p)} is a sequence in ℤ_{m} having length C_{S(m)}, it follows that there exists a subsequence T of S having consecutive terms such that T^{(p)} is an S(m)-weighted zero-sum sequence. So from Lemma 7 we see that T is an S(n)-weighted zero-sum sequence. Hence, it follows that C_{S(n)} ≤ C_{S(m)}.

We will apply the next result later in the case when p is a prime.

Lemma 9. Let p be an integer which is at least two, r be an odd number, and T be a sequence in ℤ_{p^{r}}. Suppose the image of T under f_{p^{r}, p} is an S(p)-weighted zero-sum sequence. Then T is an S(p^{r})-weighted zero-sum sequence.

Proof. Let T = (x_{1}, …, x_{k}) be a sequence in ℤ_{p^{r}} and T′ = (x′_{1}, …, x′_{k}) be the image of T under f_{p^{r}, p}. For each i ∈ [1, k] there exist a′_{i} ∈ S(p) such that

a′_{1}x′_{1} + ⋯ + a′_{k}x′_{k} = 0.

Mondal et al. [7, Lem. 7] showed that the image of U(p^{r})^{2} under f_{p^{r}, p} is S(p). So for each i ∈ [1, k] there exists a_{i} ∈ U(p^{r})^{2} such that f_{p^{r}, p}(a_{i}) = a′_{i}. Let x = a_{1}x_{1} + ⋯ + a_{k}x_{k}. As

f_{p^{r}, p}(x) = a′_{1}x′_{1} + ⋯ + a′_{k}x′_{k} = 0,

it follows that p divides x. We see that c = p^{r−1} = (p^{(r−1)/2})^{2} ∈ S(p^{r}). As p divides x, we see that cx = 0. Thus, it follows that (c a_{1})x_{1} + ⋯ + (c a_{k})x_{k} = 0. For each i ∈ [1, k] we see that c a_{i} ∈ S(p^{r}). Hence, it follows that T is an S(p^{r})-weighted zero-sum sequence.

4 C_{S(n)} and D_{S(n)} when n is an even square

The next two results will be used to determine the value of D_{S(n)} when n is an even square. As the image of U(2^{r})^{2} under f_{2^{r}, 4} is U(4)^{2} = {1} and the sequence (1, 1, 1) in ℤ_{4} does not have any zero-sum subsequence, it follows that S does not have any U(2^{r})^{2}-weighted zero-sum subsequence.

Lemma 10. Let r be a non-zero even number. Let S = (x_{1}, x_{2}, x_{3}) be a sequence in U(2^{r}) whose image under f_{2^{r}, 4} is the sequence (1, 1, 1). Then S does not have any S(2^{r})-weighted zero-sum subsequence.

Proof. Suppose T is an S(2^{r})-weighted zero-sum subsequence of S. Let

I = {i ∈ [1, 3] : x_{i} is a term of T }.

For each i ∈ I there exists a_{i} ∈ S(2^{r}) such that ∑_{i∈I} a_{i}x_{i} = 0. By Lemma 4 for each i ∈ I we see that a_{i} = 2^{r_{i}}u_{i} where r_{i} is an even number which is at most r − 2 and u_{i} ∈ U(2^{r})^{2}. So we get that

∑_{i∈I} 2^{r_{i}}u_{i}x_{i} = 0.

Let r′ be the minimum of the set {r_{i} : i ∈ I}, let J = {i ∈ I : r_{i} = r′}, and let f = f_{2^{r}, 4}. As r′ ≤ r − 2 we see that four divides ∑_{i∈J} u_{i} x_{i} and hence

0 = ∑_{i∈J} f(u_{i})f(x_{i}) = ∑_{i∈J} 1.

So we get the contradiction that the sequence (1, 1, 1) in ℤ_{4} has a zero-sum subsequence. Hence, it follows that S does not have any S(2^{r})-weighted zero-sum subsequence.

Lemma 11. Let p be a prime and r be a non-zero even number. Let (z_{1}, z_{2}) be a sequence in U(p^{2}) whose image under f_{p^{2}, p} is not an S(p)-weighted zero-sum sequence. Suppose there exists a sequence S = (x_{1}, x_{2}, y_{1}) in U(p^{r}) whose image under f_{p^{r}, p^{2}} is the sequence (z_{1}, z_{2}, p). Then the sequence S does not have any S(p^{r})-weighted zero-sum subsequence.

Proof. Suppose the sequence S has an S(p^{r})-weighted zero-sum subsequence T. Let

I = {i ∈ [1, 2] : x_{i} is a term of T }.

Let J = {1} if y_{1} is a term of T and let J = ∅ if y_{1} is not a term of T. Then for every i ∈ I and j ∈ J there exist a_{i}, b_{j} ∈ S(p^{r}) such that

∑_{i∈I} a_{i}x_{i} + ∑_{j∈J} b_{j}y_{j} = 0.

As y_{1} maps to p under f_{p^{r}, p^{2}} there exists w_{1} ∈ U(p^{r}) such that y_{1} = pw_{1}. By Lemma 4, for each i ∈ I and j ∈ J we see that a_{i} = p^{r_{i}}u_{i} and b_{j} = p^{s_{j}}v_{j} where r_{i}, s_{j} ∈ [0, r − 2] are even and u_{i}, v_{j} ∈ U(p^{r})^{2}. So we get that

∑_{i∈I} p^{r_{i}}u_{i} x_{i} + ∑_{j∈J} p^{s_{j}+1}v_{j}w_{j} = 0.  (1)

Consider the set L = {r_{i} : i ∈ I} ∪ {s_{j} + 1 : j ∈ J}. Let r′ be the minimum of L. As r ≥ 2 is even and s_{1} is even, it follows that r′ ≤ r − 1. Suppose there exists i ∈ I such that r_{i} = r′.

We claim that I = {1, 2} and r_{1} = r_{2} = r′. If not, from (1) we get that p^{r′+1} divides p^{r′}w where w is a unit. As r′ ≤ r − 1 we get the contradiction that p divides w. By a similar argument, we see that s_{1} + 1 ≠ r′. As r′ ≤ r − 1, from (1) we see that p divides u_{1}x_{1} + u_{2}x_{2}. Let f = f_{p^{r}, p}. We get that

f(u_{1})f(x_{1}) + f(u_{2})f(x_{2}) = 0.

As u_{1}, u_{2} ∈ U(p^{r})^{2}, it follows that f(u_{1}), f(u_{2}) ∈ S(p). So the sequence (f(x_{1}), f(x_{2})) is an S(p)-weighted zero-sum sequence. Thus, we get the contradiction that the image of the sequence (z_{1}, z_{2}) under f_{p^{2}, p} is an S(p)-weighted zero-sum sequence. Hence, it follows that S does not have any S(p^{r})-weighted zero-sum subsequence.

Theorem 12. Let n be an even square. Then we have that D_{S(n)} ≥ 4.

Proof. Mondal et al. [7, Cor. 2, Lem. 7] have shown that for every odd prime p we can find a sequence (u_{p}, v_{p}) in U(p^{2}) whose image under f_{p^{2}, p} is not an S(p)-weighted zero-sum sequence. Consider the sequence (u_{p}, v_{p}, p) in ℤ_{p^{2}}.

For each prime divisor p of n, the map f_{p^{vp(n)}, p^{2}} is onto. So by the Chinese remainder theorem we can find a sequence S = (x_{1}, x_{2}, x_{3}) in ℤ_{n} such that, for every prime divisor p of n, the image of S under f_{n, p^{2}} is (u_{p}, v_{p}, p) when p is odd, and the image of S under f_{n, 4} is (1, 1, 1).

For every prime divisor p of n, we see that the sequence S^{(p)} in ℤ_{p^{r}} has the form as in the statement of Lemma 10 if p = 2, or of Lemma 11 if p is odd. So for every prime divisor p of n, if r = v_{p}(n), it follows that the sequence S^{(p)} does not have any S(p^{r})-weighted zero-sum subsequence.

Suppose T is an S(n)-weighted zero-sum subsequence of S. Let x be a term of T and a ∈ S(n) be the coefficient of x in an S(n)-weighted zero-sum which is obtained from T. As a ≠ 0, there is a prime divisor p of n such that a^{(p)} ≠ 0. So we get the contradiction that the sequence S^{(p)} in ℤ_{p^{r}} has an S(p^{r})-weighted zero-sum subsequence where r = v_{p}(n).

Thus, it follows that the sequence S does not have any S(n)-weighted zero-sum subsequence. Hence, we see that D_{S(n)} ≥ 4.

Lemma 13. Let r be a non-zero even number and p be an integer which is at least two. Suppose T is a sequence in ℤ_{p^{r}} whose image under f_{p^{r}, p^{2}} is a U(p^{2})^{2}-weighted zero-sum sequence. Then the sequence T is an S(p^{r})-weighted zero-sum sequence.

Proof. The proof of this result is similar to the proof of Lemma 9. We need to use the facts that f_{p^{r}, p^{2}}(U(p^{r})^{2}) = U(p^{2})^{2} and that p^{r−2} = (p^{(r−2)/2})^{2} ∈ S(p^{r}).

The next result follows immediately from Lemma 13.

Corollary 14. Let r be a non-zero even number and p be a positive integer. Then we have that D_{S(p^{r})} ≤ D_{U(p^{2})^{2}} and C_{S(p^{r})} ≤ C_{U(p^{2})^{2}}.

Theorem 15. Let r be a non-zero even number. Then we have C_{S(2^{r})} ≤ 4.

Proof. Mondal et al. [8, Cor. 1] have shown that C_{{1}} = 4. As U(4)^{2} = {1}, from Corollary 14 it follows that C_{S(2^{r})} ≤ 4.

Corollary 16. Let n be an even square. Then we have D_{S(n)} = C_{S(n)} = 4.

Proof. From Theorem 12 we have D_{S(n)} ≥ 4. By Theorem 15 and Corollary 8 we have C_{S(n)} ≤ 4. As D_{A}(n) ≤ C_{A}(n) for every A ⊆ ℤ_{n}, it follows that D_{S(n)} = C_{S(n)} = 4.

5 C_{S(n)} and D_{S(n)} when n is not a square

Proposition 17. Let n be odd. We can find a sequence S = (u, v) in U(n) such that for each prime divisor p of n, the image of S under f_{n, p} does not have any S(p)-weighted zero-sum subsequence.

Proof. Let p be a prime divisor of n and v_{p}(n) = r. By [7, Cor. 2] there exist u_{p}, v_{p} ∈ U(p) such that the sequence (u_{p}, v_{p}) does not have any S(p)-weighted zero-sum subsequence. As the image of U(p^{r}) under f_{p^{r}, p} is U(p), there exist u′_{p}, v′_{p} ∈ U(p^{r}) such that the image of the sequence (u′_{p}, v′_{p}) under f_{p^{r}, p} is (u_{p}, v_{p}).

By the Chinese remainder theorem, there exist u, v ∈ U(n) such that for each prime divisor p of n if n_{p} = p^{v_{p}(n)}, then the image of the sequence S = (u, v) under f_{n,n_{p}} is (u′_{p}, v′_{p}). It follows that the image of S under f_{n, p} is (u_{p}, v_{p}) which is the same as the image of (u′_{p}, v′_{p}) under the map f_{n_{p}, p}.

Lemma 18. Let p be an odd prime and r be a positive integer. Suppose S = (v_{1}, v_{2}) is a sequence in U(p^{r}) such that the image of S under f_{p^{r}, p} is not an S(p)-weighted zero-sum sequence. Then the sequence S does not have any S(p^{r})-weighted zero-sum subsequence.

Proof. Suppose the sequence S is an S(p^{r})-weighted zero-sum sequence. Then there exist a_{1}, a_{2} ∈ S(p^{r}) such that a_{1}v_{1} +a_{2}v_{2} = 0. By Lemma 4 we see that there exist u_{1}, u_{2} ∈ U(p^{r})^{2} and even r_{1}, r_{2} ∈ [0, r − 1] such that a_{1} = p^{r_{1}}u_{1} and a_{2} = p^{r_{2}}u_{2}. So we get that

p^{r_{1}}u_{1}v_{1} + p^{r_{2}}u_{2}v_{2} = 0.

By Observation 3 we see that r_{1} = r_{2} and so p^{r_{1}}(u_{1}v_{1} + u_{2}v_{2}) = 0. As r_{1} < r, it follows that p divides u_{1}v_{1} + u_{2}v_{2}. If f is the map f_{p^{r}, p}, then we see that

f(u_{1})f(v_{1}) + f(u_{2})f(v_{2}) = 0.

As u_{1}, u_{2} ∈ U(p^{r})^{2}, it follows that f(u_{1}), f(u_{2}) ∈ S(p). Thus, we get the contradiction that the image of S under f_{p^{r}, p} is an S(p)-weighted zero-sum sequence. Hence, it follows that S is not an S(p^{r})-weighted zero-sum sequence. As v_{1}, v_{2} ∈ U(p^{r}), we see that S does not have any S(p^{r})-weighted zero-sum subsequence of length one.

Theorem 19. Let n be an odd number. Then we have that D_{S(n)} ≥ 3.

Proof. By Proposition 17 there exists a sequence S = (u, v) in U(n) such that for each prime divisor p of n, the image of S under f_{n, p} does not have any S(p)-weighted zero-sum subsequence.

Suppose T is an S(n)-weighted zero-sum subsequence of S. As the terms of S are in U(n), we see that T must be S. Thus, there exist a, b ∈ S(n) such that au + bv = 0. As a ≠ 0, there exists a prime divisor p of n such that a^{(p)} ≠ 0. Let k = v_{p}(n) and (u_{p}, v_{p}) be the image of S under f_{n, p^{k}}.

It follows that the sequence (u_{p}, v_{p}) in ℤ_{p^{k}} has an S(p^{k})-weighted zero-sum subsequence. As the image of S = (u, v) under f_{n, p} is the same as the image of (u_{p}, v_{p}) under f_{p^{k}, p}, it follows that (u_{p}, v_{p}) is a sequence in ℤ_{p^{k}} whose image under f_{p^{k}, p} does not have any S(p)-weighted zero-sum subsequence.

So by Lemma 18 we get the contradiction that the sequence (u_{p}, v_{p}) does not have any S(p^{k})-weighted zero-sum subsequence. Thus, we see that S does not have any S(n)-weighted zero-sum subsequence. Hence, it follows that D_{S(n)} ≥ 3.

Theorem 20. We have that D_{S(n)} ≥ 3 when v_{2}(n) is even and at least two.

Proof. By the results by Mondal et al. [7, Cor. 2, Lem. 7] and by the Chinese remainder theorem, we can find a sequence S = (v_{1}, v_{2}) in U(n) (by a similar method as in Proposition 17) such that for every odd prime divisor p of n the image of S under f_{n, p} is not an S(p)- weighted zero-sum sequence and the image of S under f_{n, 4} is (1, 1).

Suppose T is an S(n)-weighted zero-sum subsequence of S. As the terms of S are in U(n), we see that T must be S. Thus, there exists a, b ∈ S(n) such that au + bv = 0. As a ≠ 0, there is a prime divisor q of n such that a^{(q)} ≠ 0. We now use a similar argument as in the proof of Theorem 19, where we use Lemma 10 in addition to Lemma 18.

Theorem 21. Let p be an odd prime and r be odd. Then we have C_{S(p^{r})} ≤ 3.

Proof. Let S = (x, y, z) be a sequence in ℤ_{p^{r}} and let S′ be the image of S under f_{p^{r}, p}. Mondal et al. [8, Thm. 4] showed that for an odd prime p we have C_{S(p)} = 3. Thus, we can find a subsequence T whose terms are consecutive terms of S such that the image of T under f_{p^{r}, p} is an S(p)-weighted zero-sum subsequence of S′. So by Lemma 9 we see that T is an S(p^{r})-weighted zero-sum sequence. Hence, it follows that C_{S(p^{r})} ≤ 3.

Corollary 22. Suppose n is not a square and v_{2}(n) is a non-negative, even integer. Then we have that D_{S(n)} = C_{S(n)} = 3.

Proof. By Theorem 20 we have D_{S(n)} ≥ 3. From the assumptions on n, we see that there is an odd prime divisor p of n such that v_{p}(n) is odd. Thus, by Corollary 8 and Theorem 21 we have that C_{S(n)} ≤ 3. As D_{A}(n) ≤ C_{A}(n) for every A ⊆ ℤ_{n}, it follows that D_{S(n)} = C_{S(n)} = 3.

Theorem 23. We have that C_{S(2^{r})} ≤ 2 where r is an odd number.

Proof. Let S = (x, y) be a sequence in ℤ_{2^{r}} and S′ = (x′, y′) be the image of S under f_{2^{r}, 2}. We can find a subsequence T of S such that the image of T under f_{2^{r}, 2} is a zero-sum sequence. So by Lemma 9 we see that T is an S(2^{r})-weighted zero-sum sequence. Hence, it follows that C_{S(2^{r})} ≤ 2.

Corollary 24. Suppose n is an even positive integer such that v_{2}(n) is odd. Then we have that D_{S(n)} = C_{S(n)} = 2.

Proof. It is easy to see that D_{S(n)} ≥ 2. From Corollary 8 and Theorem 23, we get that C_{S(n)} ≤ 2. For every A ⊆ ℤ_{n} as D_{A}(n) ≤ C_{A}(n), it follows that D_{S(n)} = C_{S(n)} = 2.

6 D_{S(n)} when n is an odd square

Lemma 25. Let p be a prime and r be a non-zero even number. Suppose (w_{1}, w_{2}) is a sequence in U(p^{r}) whose image under f_{p^{r}, p} is not an S(p)-weighted zero-sum sequence. Let u ∈ U(p^{r}) and

S = (u w_{1}, u w_{2}, p w_{1}, p w_{2}).

Then the sequence S in ℤ_{p^{r}} does not have any S(p^{r})-weighted zero-sum subsequence.

Proof. Suppose T is an S(p^{r})-weighted zero-sum subsequence of S. Let

I = {i ∈ [1, 2] : u w_{i} is a term of T } and J = {j ∈ [1, 2] : p w_{j} is a term of T }.

As T is an S(p^{r})-weighted zero-sum sequence, for each i ∈ I there exists a_{i} ∈ S(p^{r}) and for each j ∈ J there exists b_{j} ∈ S(p^{r}) such that ∑_{i∈I} a_{i}u w_{i} + ∑_{j∈J} b_{j} p w_{j} = 0. From Lemma 4, for each i ∈ I we have a_{i} = p^{r_{i}}u_{i} for some even r_{i} < r and u_{i} ∈ U(p^{r})^{2} and for each j ∈ J we have b_{j} = p^{s_{j}}v_{j} for some even s_{j} < r and v_{j} ∈ U(p^{r})^{2}. So we have

u ∑_{i∈I} p^{r_{i}}u_{i} w_{i} + ∑_{j∈J} p^{s_{j}+1}v_{j}w_{j} = 0.  (2)

Consider the set L = {r_{i} : i ∈ I} ∪ {s_{j} + 1 : j ∈ J}. Let r′ be the minimum of L. As r is even and s_{j} is even for each j ∈ J, it follows that r′ ≤ r − 1. Observe that {r_{i} : i ∈ I} ∩ {s_{j} + 1 : j ∈ J} = ∅ as the r_{i}’s and s_{j}’s are even. Suppose there exists i ∈ I such that r_{i} = r′. We claim that I = {1, 2} and r_{1} = r_{2} = r′. If not, from (2) we get that p^{r′+1} divides p^{r′}w where w is a unit. As r′ ≤ r − 1 we get the contradiction that p divides w. By a similar argument if there exists j ∈ J such that s_{j} + 1 = r′, then J = {1, 2} and s_{1} + 1 = s_{2} + 1 = r′.

Suppose I = {1, 2} and r_{1} = r_{2} = r′. As r′ ≤ r − 1, from (2) we see that p divides u (u_{1}w_{1} + u_{2}w_{2}). As u ∈ U(p^{r}), it follows that f(u) ∈ U(p) where f = f_{p^{r}, p}. So we get that

f(u_{1})f(w_{1}) + f(u_{2})f(w_{2}) = 0.

As u_{1}, u_{2} ∈ U(p^{r})^{2}, it follows that f(u_{1}), f(u_{2}) ∈ S(p). Thus, we get the contradiction that the image of the sequence (w_{1}, w_{2}) under f_{p^{r}, p} is an S(p)-weighted zero-sum sequence. We will get the same contradiction if J = {1, 2} and s_{1} + 1 = s_{2} + 1 = r′. Thus, it follows that S does not have any S(p^{r})-weighted zero-sum subsequence.

Theorem 26. Let n be an odd square. Then we have that D_{S(n)} ≥ 5.

Proof. Let m be the radical of n, i.e., the largest squarefree divisor of n. By Proposition 17 there exists a sequence (u, v) in U(n) such that for each prime divisor p of n, the image of the sequence (u, v) under f_{n, p} does not have any S(p)-weighted zero-sum subsequence. Let

S = (u, v, mu, mv).

We claim that this sequence S does not have any S(n)-weighted zero-sum subsequence. From this it follows that D_{S(n)} ≥ 5.

Suppose T is an S(n)-weighted zero-sum subsequence of S. Let x be a term of T and a ∈ S(n) be the coefficient of x in an S(n)-weighted zero-sum which we obtain from T. As a ≠ 0, there exists a prime divisor p of n such that a^{(p)} ≠ 0. Let r = v_{p}(n). It follows that the sequence S^{(p)} has an S(p^{r})-weighted zero-sum subsequence.

The image of the sequence (u^{(p)}, v^{(p)}) under f_{p^{r}, p} does not have any S(p)-weighted zerosum subsequence. As m is the largest squarefree divisor of n, it follows that m^{(p)} = p w where w ∈ U(p^{r}). It follows that S^{(p)} is a sequence in ℤ_{p^{r}} which has the form as in the statement of Lemma 25. As n is a square, we see that r is a non-zero even number. So by Lemma 25 we arrive at the contradiction that the sequence S^{(p)} does not have any S(p^{r})-weighted zero-sum subsequence. Hence, our claim must be true.

We get the next result from the proof of [2, Thm. 7].

Lemma 27. Let p be an odd prime, r be a positive integer, and A = U(p^{r})^{2}. Suppose we are given y_{1}, y_{2}, y_{3} ∈ U(p^{r}). Then we have that

Ay_{1} + (Ay_{2} ∪ {0}) + (Ay_{3} ∪ {0}) = ℤ_{p^{r}}.

Theorem 28. Let r be a non-zero even number and p be an odd prime. Then we have that D_{S(p^{r})} ≤ 5.

Proof. Suppose S = (x_{1}, …, x_{5}) is a sequence in ℤ_{p^{r}}. If p^{2} divides some term x_{i} of S, then p^{r−2}x_{i} = 0. As r is even, we see that p^{r−2} = (p^{(r−2)/2})^{2} ∈ S(n). So we see that T = (x_{i}) is an S(p^{r})-weighted zero-sum subsequence of S of length one. Thus, we may assume that p^{2} does not divide any term of S.

It follows that each term of S is either a unit or a unit multiple of p. If at least three terms of S are units or at least three terms of S are unit multiples of p, by using Lemma 27 we get an S(p^{r})-weighted zero-sum subsequence of S. Thus, we see that D_{S(p^{r})} ≤ 5.

Corollary 29. Let n be an odd square. Then we have that D_{S(n)} = 5.

Proof. From Theorem 26 we see that D_{S(n)} ≥ 5 when n is an odd square. Since every prime divisor p of n is odd and v_{p}(n) is even, by using Corollary 8 and Theorem 28 we see that D_{S(n)} ≤ 5. Thus, it follows that D_{S(n)} = 5.

7 C_{S(n)} when n is an odd square

We will use the following notation.

If T is a subsequence of S, then S − T denotes the subsequence which is obtained by removing the terms of T from S. The concatenation of the sequences S − T and T gives us a sequence whose terms are a permutation of the terms of the sequence S.

If S is a sequence in ℤ_{n} and d ∈ ℤ_{n} such that all the terms of S are divisible by d, then S/d denotes the sequence in ℤ_{n} whose terms are obtained by dividing the corresponding terms of S by d.

Theorem 30. We have that C_{U(25)^{2}} = 9.

Proof. Let S = (x_{1}, …, x_{9}) be a sequence in ℤ_{25}. We may assume that all the terms of S are non-zero.

Suppose at least four terms of S are units. From [4, Lem. 2] it follows that S is a U(25)^{2}-weighted zero-sum sequence. Let

S_{1} = (x_{1}, x_{2}, x_{3}), S_{2} = (x_{4}, x_{5}, x_{6}), and S_{3} = (x_{7}, x_{8}, x_{9}).

Suppose at most two terms of S are units. Then we see that there exists i ∈ [1, 3] such that all the terms of S_{i} are divisible by 5. Let S′_{i} denote the sequence in ℤ_{5} which is the image of S_{i}/5 under f_{25,5}. From [8, Thm. 4] we have that C_{Q_{5}} = 3. Thus, the sequence S′_{i} has a Q_{5}-weighted zero-sum subsequence having consecutive terms. By [7, Lem. 5] it follows that the sequence S_{i} (and hence the sequence S) has a U(25)^{2}-weighted zero-sum subsequence having consecutive terms.

So we may assume that exactly three terms of S are units. If at least three consecutive terms of S are non-units, by a similar argument as in the previous paragraph we get a U(25)^{2}-weighted zero-sum subsequence of S having consecutive terms. So it follows that for each i ∈ [1, 3] there is exactly one term y_{i} in the sequence S_{i} which is a unit.

As C_{Q_{5}} = 3 we see that the sequence (y_{1}, y_{2}, y_{3}) has a subsequence S_{4} having consecutive terms whose image S′_{4} under f_{25,5} is a Q_{5}-weighted zero-sum sequence. As f_{25,5} is onto, it follows that there exists k ∈ ℤ_{25} such that a U(25)^{2}-weighted sum of the terms of S_{4} is −5k. We will use this observation a bit later in this proof. Let

J = {i ∈ [1, 3] : y_{i} is a term of S_{4}}.

Let T be the concatenation of the sequences S_{i} where i ∈ J. It follows that T is a subsequence of S having consecutive terms. We claim that T is a U(25)^{2}-weighted zero-sum sequence. Let T_{1} = T − S_{4}. As all the terms of S are non-zero, all the terms of T_{1} are of the form 5u where u ∈ U(25).

Let T′_{1} denote the image of T_{1}/5 under f_{25,5}. Chintamani and Moriya [4, Lem. 2] showed that f_{25,5}(k) ∈ ℤ_{5} is a Q_{5}-weighted sum of the terms of T′_{1}. Mondal et al. [7, Lem. 5] showed that 5k is a U(25)^{2}-weighted sum of the terms of T_{1}. As we have seen that −5k is a U(25)^{2}-weighted sum of the terms of S_{4}, it follows that T is a U(25)^{2}-weighted zero-sum sequence.

Thus, every sequence in ℤ_{25} having length nine has a U(25)^{2}-weighted zero-sum subsequence whose terms are consecutive terms of the given sequence. So it follows that C_{U(25)^{2}} ≤ 9. Mondal et al. [8, Cor. 5] showed that C_{U(25)^{2}} ≥ 9. Hence, it follows that C_{U(25)^{2}} = 9.

Theorem 31. Let n be an odd square. Then we have that C_{S(n)} ≤ 9.

Proof. Mondal et al. [8, Cor. 6] showed that C_{U(p^{2})^{2}} = 9 when p is a prime which is at least seven. From Remark 1 we see that C_{U(9)^{2}} ≤ 9 and from Theorem 30 we see that C_{U(25)^{2}} ≤ 9. Thus, from Corollaries 8 and 14 it follows that C_{S(n)} ≤ 9.

Chintamani and Moriya [4, Lem. 1] showed the next result.

Lemma 32. Let p be a prime which is at least seven and A = U(p^{r})^{2}. Then for every x_{1}, x_{2}, x_{3} ∈ U(p^{r}) we have that Ax_{1} + Ax_{2} + Ax_{3} = ℤ_{p^{r}}.

Mondal et al. [8, Lem. 7] showed the next result, which follows easily from Lemma 32.

Lemma 33. Let p be a prime which is at least seven and S = (x_{1}, …, x_{k}) be a sequence in ℤ_{p^{r}}. Suppose at least three terms of S are units. Then S is a U(p^{r})^{2}-weighted zero-sum sequence.

Theorem 34. Let p be a prime which is at least seven and r be an even number which is at least four. Then we have that C_{S(p^{r})} ≤ 5.

Proof. Let S = (x_{1}, …, x_{5}) be a sequence in ℤ_{p^{r}}. As r is even, we see that p^{r−2} = (p^{(r−2)/2})^{2} and hence p^{r−2} ∈ S(p^{r}). If p^{2} divides some term x of S, then it follows that p^{r−2}x = 0 and so S has an S(p^{r})-weighted zero-sum subsequence of length one. Thus, we may assume that p^{2} does not divide any term of S. So every term of S is either a unit or of the form p u where u is a unit.

If at least three terms of S are units, by Lemma 33 we see that S is an S(p^{r})-weighted zero-sum sequence. Thus, we may assume that at most two terms of S are units. Then at least three terms of S are of the form p u where u is a unit. We may assume that x_{1} = pu_{1}, x_{2} = pu_{2}, x_{3} = pu_{3} where u_{1}, u_{2}, u_{3} ∈ U(p^{r}). Consider the sequence

S′ = (u_{1}, u_{2}, u_{3}, px_{4}, px_{5}).

By Lemma 33 we see that S′ is a U(p^{r})^{2}-weighted zero-sum sequence. So there exist a_{i}’s in U(p^{r})^{2} such that

a_{1}u_{1} + a_{2}u_{2} + a_{3}u_{3} + a_{4}px_{4} + a_{5}px_{5} = 0.

Thus, it follows that

a_{1}x_{1} + a_{2}x_{2} + a_{3}x_{3} + p^{2}a_{4}x_{4} + p^{2}a_{5}x_{5} = 0.

As r ≥ 4, we see that p^{2} ≠ 0. Hence, it follows that S is an S(p^{r})-weighted zero-sum sequence.

Corollary 35. Let n be an odd square which is divisible by p^{4} where p is a prime which is at least seven. Then we have that C_{S(n)} = 5.

Proof. As n is a square, it follows that v_{p}(n) is even. So from Corollary 8 and Theorem 34 we have C_{S(n)} ≤ 5. As we have that D_{A}(n) ≤ C_{A}(n) for every A ⊆ ℤ_{n}, from Theorem 26 it follows that C_{S(n)} = 5.

The next result follows easily from a result by Chintamani and Moriya [4, Lem. 2].

Lemma 36. Let r be a positive integer and S be a sequence in ℤ_{5^{r}}. Suppose at least four terms of S are units. Then S is a U(5^{r})^{2}-weighted zero-sum sequence.

Theorem 37. We have that C_{S(5^{r})} ≤ 7 when r is an even number which is at least four.

Proof. We use a similar argument as in the proof of Theorem 34. The only change is that we replace Lemma 33 with Lemma 36.

Corollary 38. Let n be a square which is divisible by 5^{4}. Then we have that C_{S(n)} ≤ 7.

Proof. As n is a square, it follows that v_{5}(n) is even. Also, we have that v_{5}(n) ≥ 4. So from Corollary 8 and Theorem 37 we get that C_{S(n)} ≤ 7.

Theorem 39. Let n be a square of an odd squarefree number. Then we have that C_{S(n)} = 9.

Proof. By Theorem 31 we get that C_{S(n)} ≤ 9. We will construct a sequence S of length eight in ℤ_{n} which has no S(n)-weighted zero-sum subsequence having consecutive terms. Hence, it will follow that C_{S(n)} = 9.

By Proposition 17 there exists a sequence S′ = (u, v) in U(n) such that for every prime divisor p of n, the image (u_{p}, v_{p}) of S′ under f_{n, p} does not have any S(p)-weighted zero-sum subsequence. By the Chinese remainder theorem there exist x, y ∈ ℤ_{n} such that for each prime divisor p of n we have that x^{(p)} = p u^{(p)} and y^{(p)} = p v^{(p)}. In this proof, for every c ∈ ℤ_{n} we will denote f_{n, p}(c) by c_{p}. So it follows that x_{p} = y_{p} = 0. Consider the sequence S in ℤ_{n} defined as follows:

S = (x, y, u, x, y, v, x, y).

Suppose there exists a subsequence T of S having consecutive terms which is an S(n)- weighted zero-sum sequence.

Case 1: Either u or v is a term of T.

Without loss of generality, we may assume that u is a term of T.

Let a ∈ S(n) be the coefficient of u in the S(n)-weighted zero-sum which is obtained from T. As a ≠ 0, there exists a prime divisor p of n such that a^{(p)} ≠ 0. As n is the square of a squarefree number, it follows that v_{p}(n) = 2. So we see that a^{(p)} ∈ S(p^{2}). As every non-zero term of ℤ_{p^{2}} is either a unit or a unit multiple of p, we see that S(p^{2}) = U(p^{2})^{2}. As a^{(p)} ∈ U(p^{2})^{2}, it follows that f_{p^{2}, p}(a^{(p)}) ∈ S(p) and so a_{p} ∈ S(p).

We claim that the sequence (u_{p}, v_{p}) has an S(p)-weighted zero-sum subsequence.

Suppose v is a term of T. Let b ∈ S(n) be the coefficient of v in the S(n)-weighted zerosum which is obtained from T. As b ∈ S(n), it follows that b_{p} ∈ S(p) ∪ {0}. So we get that a_{p}u_{p} + b_{p}v_{p} = 0. If v is not a term of T then a_{p}u_{p} = 0. This proves our claim which contradicts our choice of the sequence (u_{p}, v_{p}).

Case 2: Neither u nor v is a term of T.

As T is a subsequence of consecutive terms, it follows that T is a subsequence of the sequence (x, y). Suppose x is a term of T. Let a ∈ S(n) be the coefficient of x in the S(n)-weighted zero-sum which is obtained from T. By a similar argument as in the previous case, we see that there is a prime divisor p of n such that a_{p} ∈ S(p).

We claim that the sequence (u_{p}, v_{p}) has an S(p)-weighted zero-sum subsequence.

Suppose y is a term of T. Then there exists b ∈ S(n) such that ax+by = 0. As b ∈ S(n), it follows that b_{p} ∈ S(p) ∪ {0}. As ax + by = 0, it follows that a^{(p)}x^{(p)} + b^{(p)}y^{(p)} = 0 in ℤ_{p^{2}}. Thus, we get that

p (a^{(p)}u^{(p)} + b^{(p)}v^{(p)}) = 0

and so a^{(p)}u^{(p)} + b^{(p)}v^{(p)} is divisible by p. Hence, it follows that a_{p}u_{p} + b_{p}v_{p} = 0. By a similar argument, we see that if y is not a term of T then a_{p}u_{p} = 0. This proves our claim which contradicts our choice of the sequence (u_{p}, v_{p}).

Hence, it follows that the sequence S does not have any S(n)-weighted zero-sum subsequence of consecutive terms.

8 Concluding remarks

We have been unable to determine the constants C_{S(3^{r})} and C_{S(5^{r})} where r is an even number which is at least four. For every such r we have shown that C_{S(3^{r})} ∈ [5, 9] and C_{S(5^{r})} ∈ [5, 7]. If the values of these constants are known, we can determine the value of C_{S(n)} for every n.

We can try to characterize the sequences in ℤ_{n} of length C_{S(n)} − 1 which do not have any S(n)-weighted zero-sum subsequence having consecutive terms. We can also try to characterize sequences in ℤ_{n} of length D_{S(n)} − 1 which do not have any S(n)-weighted zerosum subsequence.

9 Acknowledgments

We thank the anonymous referee for the helpful suggestions.

References

[1] S. D. Adhikari and Y. G. Chen, Davenport constant with weights and some related questions II, J. Combin. Theory Ser. A 115 (2008), 178–184.

[2] S. D. Adhikari, C. David, and J. J. Urroz, Generalizations of some zero-sum theorems, Integers 8 (2008), #A52.

[3] S. D. Adhikari and P. Rath, Davenport constant with weights and some related questions, Integers 6 (2006), #A30.

[4] M. N. Chintamani and B. K. Moriya, Generalizations of some zero-sum theorems, Proc. Indian Acad. Sci. Math. Sci. 122 (2012), 15–21.

[5] D. J. Grynkiewicz and F. Hennecart, A weighted zero-sum problem with quadratic residues, Unif. Distrib. Theory 10 (2015), 69–105.

[6] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, New York, 1990.

[7] S. Mondal, K. Paul, and S. Paul, Extremal sequences for a weighted zero-sum constant, Integers 22 (2022), #A93.

[8] S. Mondal, K. Paul, and S. Paul, On a different weighted zero-sum constant, Discrete Math. 346 (2023), 113350.

2020 Mathematics Subject Classification: Primary 11B50; Secondary 11B75. Keywords: Davenport constant, weighted zero-sum sequence.

(Concerned with sequence \underline{A371769}.)

Received March 22 2024; revised version received August 1 2024. Published in Journal of Integer Sequences, August 1 2024.

Return to Journal of Integer Sequences home page.