Let G be a finite abelian group, and let T(G) be the smallest integer t such that every sequence of length t over G contains a nonempty zero-sum subsequence of cross number 1. We determine the exact value of T(Cn) for every positive integer n, showing that T(Cn)=2n−1 when n is odd and T(Cn)=3n/2−1 when n is even. In particular, T(Cn)=s(Cn) for odd n.
Introduction and main results
Given a positive integer n and integers a1,…,aℓ, we ask whether there exists a nonempty subset I⊆[1,ℓ] such that n∣∑i∈Iai and ∑i∈Igcd(ai,n)=n. We show that the sharp bound is ℓ=2n−1 for odd n and ℓ=3n/2−1 for even n. This problem can be formulated in terms of zero-sum subsequences of cross number 1 over cyclic groups.
Let G be a finite abelian group, written additively. We denote by Cn a cyclic group of order n. For a general finite abelian group G, we can decompose G as a direct sum of cyclic groups Cn1⊕⋯⊕Cnr such that 1<n1∣⋯∣nr∈N (if n1=⋯=nr=n, it will be abbreviated as Cnr), where r and nr are respectively called the rank and exponent of G. Usually, the exponent of G is simply denoted by exp(G). The order of an element g of G will be written as ord(g).
A sequence over G is a finite unordered product S=g1⋯gℓ, where repetitions are allowed. The cross number of S=g1⋯gℓ is
k(S)=i=1∑ℓord(gi)1.
For a finite abelian group G and a positive integer k, let sk(G) denote the smallest integer t such that every sequence over G of length t contains a zero-sum subsequence of length kexp(G). In particular, s1(G)=s(G) is the classical Erdős–Ginzburg–Ziv constant. The Erdős–Ginzburg–Ziv theorem gives s(Cn)=2n−1 for every positive integer n (see [1]). For further results on these constants, we refer to [2, 5].
Let T(G) be the smallest integer t such that every sequence of length t over G contains a nonempty zero-sum subsequence of cross number 1. In recent years, Gao, Hui, Jiang, Li and
Keywords: Finite abelian group, Zero-sum theory, Cross number. Wang introduced T(G) and studied its relation to classical zero-sum constants (see [3]). They determined T(Cn) for prime powers and established T(Cn)=s(Cn) for several further classes of odd integers. They also conjectured that T(Cnr)=s(Cnr) for all odd integers n>1 and positive integers r. We determine the invariant for all cyclic groups Cn.
Theorem 1.1.For every positive integer n,
T(Cn)={2n−1,23n−1,nodd,neven.
The lower bounds follow from the sequences in [3 Lemma 3.1]. For n=1, there is nothing to prove. Let n>1 and let g generate Cn. If n is odd, then gn−1⋅(−g)n−1 contains no zero-sum subsequence of length n. If n is even, the same holds for gn−1⋅(−g)n/2−1. Since every term of these sequences has order n, a subsequence T satisfies k(T)=∣T∣/n. Hence, neither sequence contains a zero-sum subsequence of cross number 1. For the upper bounds, we prove the stronger statement in Proposition 2.5.
The paper is organized as follows. Some notation and some preliminary results are gathered in § 2. § 3 and § 4 are devoted to the proofs of Proposition 2.5(i) and (ii), respectively.
Notation and preliminaries
We denote by N the set of positive integers, by N0 the set N∪{0} and by Z the set of integers. For any a,b∈Z, we set [a,b]={x∈Z∣a≤x≤b}. For any real number x, let ⌈x⌉ be the smallest integer not less than x, and ⌊x⌋ be the largest integer not greater than x.
Throughout this paper, let p be a prime and G be a finite additive abelian group with identity element 0. For a set X, we denote by F(X) the free (abelian, multiplicative) monoid with basis X. The elements of F(X) are called sequences over X. We can write a sequence S∈F(X) in the form
S=g∈X∏gvg(S),
where vg(S)∈N0 is called the multiplicity of the element g in S. We say that S contains the element g of X if vg(S)>0. A sequence S′ is called a subsequence of S, denoted by S′∣S, if vg(S′)≤vg(S) for all g∈X. The sequence SS′−1 denotes the subsequence obtained from S by deleting S′. Two subsequences S′ and S′′ of S are called disjoint if S′∣SS′′−1. The unit element 1∈F(X) is called the empty sequence.
For a group G and a sequence
S=g1⋯gℓ=g∈G∏gvg(S)∈F(G),
we define
∣S∣=ℓ=∑g∈Gvg(S)∈N0 the length of S,
h(S)=max{vg(S)∣g∈G}∈[0,∣S∣] the maximum of the multiplicities of S,
σ(S)=∑i=1ℓgi=∑g∈Gvg(S)g∈G the sum of S,
supp(S)={g∈G∣vg(S)>0}⊆G the support of S,
S a zero-sum sequence if $\sigma(S)=0\in G.
Every map of abelian groups φ:G→H can be extended to a homomorphism φ:F(G)→F(H), where φ(S)=φ(g1)⋯φ(gℓ). If φ is a homomorphism, then φ(S) is a zero-sum sequence over H if and only if σ(S)∈ker(φ). Moreover, φ(σ(S))=σ(φ(S)).
We collect some known results which will be used later.
Lemma 2.1[4]. Let n,k be positive integers. Every sequence of length (k+1)n−1 over Cn has a zero-sum subsequence of length kn.
Lemma 2.2[2 Lemma 2.2]. Let n,k,t be positive integers with 2≤t<n/2+1, and let S be a sequence over Cn of length (k+1)n−t. If S contains no zero-sum subsequence of length kn, then there exist distinct x,y∈Cn such that
vx(S)+vy(S)≥(k+1)n−2t+2.
Lemma 2.3 (Kleitman–Lemke [6]). Let n be a positive integer. Every sequence of length n over Cn has a nonempty zero-sum subsequence T with k(T)≤1.
For a positive integer n, let τ(n) denote its number of positive divisors, ω(n) its number of distinct prime divisors, and vp(n) the exponent of a prime p in n. All sums indexed by p∣n are over the distinct prime divisors of n.
Lemma 2.4. Let n be a positive integer and let k=ω(n).
(i) If n≥3 is odd, then k(τ(n)−3)≤(n+3)/4.
(ii) If 4∣n and k≥4, then n≥4kτ(n).
(iii) If n is odd and k≥4, then n≥8kτ(n).
Proof. For every prime p, the ratio pa/(a+1) increases with a≥1, since the ratio of consecutive terms is p(a+1)/(a+2)>1.
For (i), let n=p1a1⋯pkak with p1<⋯<pk odd primes. If k=1, then 4(a1−2)≤3a1+3≤n+3. If k=2, it suffices to prove 8τ(n)≤n+27. We prove it by induction. This holds for a1=a2=1, since τ(n)=4 and n≥15. Suppose that 8τ(m)≤m+27, where m has exactly two distinct odd prime divisors. For any prime p∣m, we have τ(pm)≤3τ(m)/2. Thus,
For each d∣n, let Sd∈F(dCn) be a prescribed sequence, and let S=∏d∣nSd. The subsequences Sd are distinguished by their indices d, even if their supports intersect. For example, S1 is a prescribed subsequence, not the subsequence of all terms belonging to Cn.
Proposition 2.5. Let n be a positive integer, and let Sd∈F(dCn) for every d∣n. Suppose that one of the following holds:
(i) n is odd and ∑d∣n∣Sd∣=2n−1;
(ii) n is even, ∑d∣n∣Sd∣=3n/2−1, and supp(Sd)∩2dCn=∅ if 2d∣n.
Proof of Theorem 1.1. Let S be a sequence of length 2n−1 for odd n, or 3n/2−1 for even n over Cn. For each d∣n, let Sd consist of its terms of order exactly n/d. Such terms generate dCn, so Sd∈F(dCn) and, if 2d∣n, no term belongs to the proper subgroup 2dCn. Proposition 2.5 gives Td∣Sd satisfying (2.1). Then T=∏d∣nTd is nonempty and zero-sum, and
k(T)=d∣n∑n/d∣Td∣=n1d∣n∑d∣Td∣=1.
Together with the lower bounds, this proves the theorem. □
In Proposition 2.5, the terms of Sd are not required to have order exactly n/d. This is essential for the inductive argument. If pd∣n and R∣Sd satisfies ∣R∣=p and σ(R)∈pdCn, then replacing R by the single term σ(R) in Spd preserves the total sum and the value of ∑d∣nd∣Sd∣, since d∣R∣=pd. This does not require ord(σ(R))=n/(pd).
Odd order
Proof of Proposition 2.5(i). We prove the assertion by induction on the odd integer n. The assertion is immediate for n=1. Let n>1, and suppose it holds for every positive odd integer d<n. Suppose, to the contrary, that a sequence S=∏d∣nSd of length 2n−1 has no subsequences satisfying (2.1). Since nCn={0}, we have Sn=1F(Cn). For every prime p∣n, let Xp=∑d∣n,p∣d∣Sd∣, and let M=∑d∣n,d>1∣Sd∣.
We first prove that Xp≤τ(n)−3 for every prime p∣n.
Choose a prime p∣n. For each d∣n with p∤d, let πp:dCn→dCn/pdCn≅Cp be the canonical homomorphism. By Lemma 2.1, choose a maximal family of pairwise disjoint subsequences Td,1,…,Td,ad∣Sd with ∣Td,i∣=p and σ(πp(Td,i))=0, and hence σ(Td,i)∈pdCn for every i∈[1,ad]. Let Rd=Sd⋅(Td,1⋯Td,ad)−1, and hence ∣Rd∣≤2p−2.
Let φ:Cn/p→pCn be an isomorphism. For each e∣n/p, set
Since φ(eCn/p)=peCn, we have Ue∈F(eCn/p) and ∑e∣n/p∣Ue∣=Xp+∑d∣n,p∤dad. Suppose that ∑e∣n/p∣Ue∣≥2(n/p)−1. By the induction hypothesis, there exist Ve∣Ue such that
e∣n/p∑σ(Ve)=0,e∣n/p∑e∣Ve∣=pn.
Write φ(Ve)=Ae⋅∏i∈Ieσ(Te,i), where Ae∣Spe, Ie⊆[1,ae] if p∤e, and Ie=∅ if p∣e. Then ∣Ve∣=∣Ae∣+∣Ie∣. For each d∣n, let
Td={∏i∈IdTd,i,Ad/p,p∤d,p∣d.
Since the subsequences Td,1,…,Td,ad are pairwise disjoint, we have Td∣Sd for every d∣n. Moreover,
If n is prime, the estimate Xn≤τ(n)−3=−1 is already a contradiction. We may therefore assume that n is composite, so n≥9.
Since the sequence S1 of length 2n−1−M has no zero-sum subsequence of length n, by Lemma 2.1, we have M≥1. Taking t=M+1, we have 2≤t<n/2+1 by (4). By Lemma 2.2, with k=1, there exist distinct x,y∈Cn such that vx(S1)+vy(S1)≥2n−2M.
Since S1 contains no zero-sum subsequence of length n and ng=0 for every g∈Cn, we have vg(S1)≤n−1 for every g∈Cn. Write vx(S1)=n−1−α and vy(S1)=n−1−β, where α,β≥0. Then
α+β≤2M−2≤2n−1.
We claim that u=x−y generates Cn. Otherwise, e=ord(u) is a proper divisor of n, so e≤n/3. For every integer a with β+1≤a≤n−1−α, the sequence xa⋅yn−a divides S1 and has sum au. This interval contains n−1−α−β≥(n−1)/2≥e consecutive integers, and hence contains a multiple of e. The corresponding subsequence is zero-sum and has length n, a contradiction.
Let r=α+β+1. Choose g1,…,gr∈Cn and divisors d1,…,dr of n such that, for every d∣n,
Then S=xn−1−α⋅yn−1−β⋅g1⋅…⋅gr, where gj∈djCn for every j∈[1,r], and gj∈/{x,y} whenever dj=1. Since u=x−y generates Cn and djy−gj∈djCn, there is a unique Dj∈{0,dj,2dj,…,n−dj} such that gj=djy−Dju.
Consider the subsequence T=xa⋅yb⋅∏j∈Jgj∣S, where J⊆[1,r], 0≤a≤n−1−α and 0≤b≤n−1−β, with the factorization T1=xayb∏j∈J,dj=1gj and Td=∏j∈J,dj=dgj for d>1. Then
d∣n∑d∣Td∣=a+b+j∈J∑dj,
and,
σ(T)=a+b+j∈J∑djy+a−j∈J∑Dju.
Hence, T satisfies (2.1) as soon as a+b+∑j∈Jdj=n and a≡∑j∈JDj(modn).
We shall show that these two conditions hold for some J⊆[1,r], 0≤a≤n−1−α, and 0≤b≤n−1−β.
Suppose first that there exists j∈[1,r] such that Dj≤n−1−α and Dj+dj≥β+1. Take J={j}, a=Dj, and b=n−dj−Dj. Then these two conditions hold.
Otherwise, for every j∈[1,r], either Dj+dj≤β or n−Dj≤α. These two inequalities cannot both hold, since their sum would give n+dj≤α+β≤(n−1)/2. Thus
Y={j∈[1,r]:Dj+dj≤β},X={j∈[1,r]:n−Dj≤α}
partition [1,r].
For j∈Y, we have Dj+dj≥2. Otherwise, dj=1 and Dj=0, which gives gj=y, contradicting gj∈/{x,y} whenever dj=1. Similarly, for j∈X, we have n−Dj≥2. Otherwise, Dj=n−1 and dj=1, which gives gj=x, contradicting gj∈/{x,y} whenever dj=1. Consequently,
j∈Y∑(Dj+dj)+j∈X∑(n−Dj)≥2r>α+β.
Suppose that ∑j∈Y(Dj+dj)≥β+1. Choose a minimal subset J⊆Y such that ∑j∈J(Dj+dj)≥β+1. Since Dj+dj≤β for j∈Y, minimality gives β+1≤∑j∈J(Dj+dj)≤2β. Take a=∑j∈JDj and b=n−∑j∈J(Dj+dj). Since α+β≤(n−1)/2, we obtain 0≤a≤2β≤n−1−α, 0≤n−2β≤b≤n−1−β. Hence, these two conditions hold.
It remains to consider ∑j∈Y(Dj+dj)≤β. Then ∑j∈X(n−Dj)≥α+1. Choose a minimal subset J⊆X such that ∑j∈J(n−Dj)≥α+1. Since n−Dj≤α for j∈X, we have α+1≤∑j∈J(n−Dj)≤2α. Take a=n−∑j∈J(n−Dj) and b=∑j∈J(n−Dj−dj). Since Dj≤n−dj and α+β≤(n−1)/2, we obtain 0≤n−2α≤a≤n−1−α, 0≤b≤2α≤n−1−β. Thus, these two conditions also hold in this situation.
In each situation, the resulting subsequences Td∣Sd satisfy (2.1), contrary to our assumption. This completes the induction.
Even order
For T=∏d∣nTd with Td∣Sd, let w(T)=∑d∣nd∣Td∣, where the terms of each Td are taken from the prescribed sequence Sd. Then ∣T∣≤w(T), and w(UV)=w(U)+w(V) for disjoint subsequences U,V with these factorizations. Thus (1) is equivalent to σ(T)=0 and w(T)=n.
Lemma 4.1. Let n=2m be a positive even integer, and let S=∏d∣nSd, where Sd∈F(dCn), ∣S∣=3m−1, and supp(Sd)∩2dCn=∅ whenever 2d∣n. Suppose that x∈Cn∖2Cn and P∣S satisfy m−1≤w(P)≤m, and that, for every j∈[0,w(P)], there exists Q∣P such that w(Q)=j and σ(Q)=jx. Then S contains a zero-sum subsequence T with w(T)=n.
Proof. Choose U∣SP−1 satisfying σ(U)=w(U)x and w(U)≤n−1−w(P) such that w(U) is maximal, where the empty sequence is admitted. Since ∣P∣≤w(P) and ∣U∣≤w(U), we have
∣S(PU)−1∣≥3m−1−w(P)−w(U)≥3m−1−(n−1)=m.
Let R=g1⋅…⋅gm be a subsequence of S(PU)−1, where, for each i∈[1,m], gi is a term of Sdi with di∣n.
If di is even, then gi,dix∈diCn⊆2Cn. If di is odd, then 2di∣n and diCn∩2Cn=2diCn. Since supp(Sdi)∩2diCn=∅, we have gi∈diCn∖2diCn and hence gi∈/2Cn. Also, dix∈/2Cn, since x∈/2Cn and di is odd. Thus, we have gi−dix∈diCn∩2Cn for any i∈[1,m], and hence ord(gi−dix)∣n/di.
Consider the sequence
R′=i=1∏m(gi−dix)∈F(2Cn).
Since ∣R′∣=m=∣2Cn∣, by Lemma 2.3, there exists a nonempty subsequence V′=∏i∈I(gi−dix)∣R′ such that σ(V′)=0 and k(V′)=∑i∈Iord(gi−dix)1≤1, where ∅=I⊆[1,m]. Let V=∏i∈Igi∣R. Then σ(V)=∑i∈Igi=∑i∈Idix=w(V)x and 1≤w(V)=∑i∈Idi≤n∑i∈Iord(gi−dix)1≤n. Thus, U and V are disjoint, and σ(UV)=w(UV)x. The maximality of w(U) therefore implies w(U)+w(V)≥n−w(P). If w(V)≤n−w(P)−1, we take V∗=UV. Since w(P)≥m−1, we have
n−w(P)≤w(V∗)=w(U)+w(V)≤2(n−1−w(P))≤n.
If w(V)≥n−w(P), we take V∗=V. Thus, we have V∗∣SP−1, n−w(P)≤w(V∗)≤n and σ(V∗)=w(V∗)x. Since 0≤n−w(V∗)≤w(P), the hypothesis gives Q∣P such that w(Q)=n−w(V∗) and σ(Q)=(n−w(V∗))x. Hence, T=QV∗ is the required subsequence. □
Proof of Proposition 2.5(ii). We prove the assertion by induction on the even integer n. The assertion is immediate for n=2. Let n=2m>2, and suppose it holds for every positive even integer d<n. Suppose, to the contrary, that a sequence S=∏d∣nSd of length 3n/2−1 has no subsequences satisfying (1). Since nCn={0}, we have Sn=1F(Cn). For every prime p∣n, let Xp=∑d∣n,p∣d∣Sd∣, and let M=∑d∣n,d>1∣Sd∣.
We first prove that
Xp≤νp(n)+12τ(n)−3,(5)
for every prime p∣n such that n/p is even. Choose a prime p∣n such that n/p is even, and let d∣n with p∤d.
Suppose that p is odd. If ∣Sd∣≥2p−1, let R∣Sd with ∣R∣=2p−1. Applying Lemma 2.1 to the image of R in dCn/pdCn≅Cp, we obtain a subsequence T∣R of length p satisfying σ(T)∈pdCn. When 2pd∣n, we have supp(Sd)⊆dCn∖2dCn. Let π2:dCn→dCn/2dCn≅C2 be the canonical homomorphism. Thus π2(T)=hp, where h is the unique nonzero element of dCn/2dCn. Since p is odd and ord(h)=2, we have π2(σ(T))=σ(π2(T))=ph=h=0. Thus, σ(T)∈pdCn∖2pdCn.
Suppose now that p=2. Then 4∣n and d is odd, so 4d∣n. Let π4:dCn→dCn/4dCn≅C4 be the canonical homomorphism. If ∣Sd∣≥3, let R=g1g2g3∣Sd, where gi∈dCn∖2dCn for every i∈[1,3], so ord(π4(gi))=4. Since dCn/4dCn≅C4 has exactly two elements of order 4, there exist distinct i,j∈[1,3] such that π4(gi)=π4(gj). For T=gigj∣R, we have ∣T∣=2 and π4(σ(T))=π4(gi)+π4(gj)=2π4(gi). It follows that σ(T)∈2dCn∖4dCn.
Consequently, as in the odd-order proof, there is a factorization Sd=Td,1⋅…⋅Td,ad⋅Rd such that ∣Td,i∣=p for i∈[1,ad], ∣Rd∣≤2p−2, and
σ(Td,i)∈pdCn,σ(Td,i)∈/2pdCn if 2pd∣n.
Let φ:Cn/p→pCn be an isomorphism and define Ue by (3.1). Since φ(2eCn/p)=2peCn, we have Ue∈F(eCn/p) for every e∣n/p, and supp(Ue)∩2eCn/p=∅ whenever 2e∣n/p. If
e∣n/p∑∣Ue∣≥2p3m−1,
the induction hypothesis and the same construction of Td as in the odd-order proof would give (2.1). Therefore
Xp+d∣npi∣d∑ad=e∣n/p∑∣Ue∣≤p3m−2.
Since ∣Sd∣=pad+∣Rd∣ and ∑d∣np∤d∣Sd∣=3m−1−Xp, we obtain
We claim that h(S1)≤m−2. For every x∈Cn, if xm−1∣S1, then x∈/2Cn. Taking P=xm−1 in Lemma 4.1 gives a contradiction, since Q=xj satisfies w(Q)=j and σ(Q)=jx for every j∈[0,m−1].
Fix g0∈Cn∖2Cn. Let S1=g1⋅…⋅g∣S1∣ and let
W=i=1∏∣S1∣(gi−g0)∈F(2Cn)≅F(Cm).
If W contains a zero-sum subsequence W′=∏i∈I(gi−g0), where I⊆[1,∣S1∣] and ∣I∣=2m, then the sequence T=∏i∈Igi∣S1 satisfies (2.1), a contradiction. Thus, W has no zero-sum subsequence of length 2m, and Lemma 2.1 gives ∣W∣≤3m−2. If ∣W∣≥⌊5m/2⌋, then t=3m−∣W∣ satisfies 2≤t≤⌈m/2⌉<m/2+1. By Lemma 2.2, with k=2, there exist distinct h1,h2∈2Cn≅Cm such that
νh1(W)+νh2(W)≥3m−2t+2≥2m+1.
Since νhi(W)=νhi+g0(S1) for i∈{1,2}, this contradicts h(S1)≤m−2. Therefore ∣S1∣≤⌊5m/2⌋−1, which proves M≥⌈2m⌉.
Suppose that m is even. Then n/p is even for every prime p∣n. By the definition of M,
Together with (6), this gives pXp≤M−1 for every prime p∣n. If ω(n)≤2, then M≤(5/6)(M−1), a contradiction. If ω(n)=3, set n=2αpβqλ, where α≥2, β,λ≥1, and 3≤p<q. By (5), we have
M≤X2+Xp+Xq≤2(β+1)(λ+1)−3+158(M−1).
and hence
7M≤30(β+1)(λ+1)−53.
Since β+λ≤2βλ, pβ≥3β, and qλ≥5λ, we obtain
7M≤90βλ−23<105βλ≤7pβqλ≤47n,
contrary to M≥⌈2n⌉≥n/4. If ω(n)≥4, Lemma 2.4(ii) and (5) yield
M≤p∣n∑(vp(n)+12τ(n)−3)≤ω(n)(τ(n)−3)<n/4,
again a contradiction.
It remains to consider n=2m with m≥3 odd. Then n/p is even for every prime p∣m. Let b=∣S2∣. Then
For ω(m)=1, (5) gives M−b≤1. For ω(m)=2 and M−b≥3, (7) gives
M−b≤158(M−b−3)+4,
so M−b≤5. If M−b=5, then Xp≤⌊(2p+2)/p⌋=2 for both primes, giving M−b≤4, a contradiction. Thus M−b≤4≤(m+1)/4. For ω(m)=3 and M−b≥3, by (7), we have
M−b≤(31+51+71)(M−b−3)+6=10571(M−b−3)+6,
so M−b≤12<(m+1)/4, since m≥105. If ω(m)∈{2,3} and M−b≤2, then (8) holds trivially. For ω(m)≥4, Lemma 2.4(iii) and (5) give
M−b≤p∣m∑(vp(m)+14τ(m)−3)≤ω(m)(2τ(m)−3)<m/4.
This proves the claim.
Since m is odd, Cn≅C2⊕Cm. Let π:Cn→Cm be the projection. Then supp(S1)⊆{1}×Cm and supp(S2)⊆{0}×Cm. By (8) and M≥⌈2m⌉, we have
b=M−(M−b)≥M−4m+1≥2M.(9)
Let e be a generator of Cm. Pairing equal terms of S1 as far as possible, we may write
S1=x12⋅…⋅xr2⋅(1,z1e)⋅…⋅(1,zte),
where 0≤z1<⋯<zt≤m−1 and t≤m. Set Pi=xi2 for i∈[1,r] and Pr+j=(1,z2j−1e)⋅(1,z2je) for j∈[1,⌊t/2⌋]. If t is odd, let R′=(1,zte). Otherwise, let R′ be the empty sequence. Then S1=P1⋅…⋅Ps⋅R′, where ∣Pi∣=2, ∣R′∣≤1 and s=r+⌊2t⌋=⌊2∣S1∣⌋.
Let
V=π(S2)⋅i=1∏sπ(σ(Pi))∈F(Cm),
and let ℓ=∣V∣=b+⌊2∣S1∣⌋.
If V has a zero-sum subsequence of length m, there exist A∣S2 and I⊆[1,s] such that ∣A∣+∣I∣=m and π(σ(A)+∑i∈Iσ(Pi))=0. Since σ(A)+∑i∈Iσ(Pi)∈2Cn and π is injective on 2Cn, it follows that T1=∏i∈IPi and T2=A, with all other Td empty, satisfy (2.1), a contradiction. By Lemma 2.1, we have ℓ≤2m−2.
If m=3, we have h(S1)≤m−2=1, and hence ∣S1∣≤3. By (8), we have M−b≤1. Since M=8−∣S1∣, ℓ≥7−⌈∣S1∣/2⌉≥5>2m−2, a contradiction. Thus m≥5, and (8) implies M−b≤⌊(m+1)/4⌋≤(m−3)/2.
For every h∈supp(π(S1)), we claim that
v2h(V)≤2m−3.(10)
Assume that there exists h∈supp(π(S1)) satisfying v2h(V)≥(m−1)/2, and let x=(1,h). By the definition of V, there exist pairwise disjoint subsequences W1,…,W(m−1)/2 of S such that w(Wi)=2 and σ(Wi)=2x for every i∈[1,(m−1)/2]. Each Wi is either a term of S2 or one of the pairs Pj for some j∈[1,s].
If x∤W1⋅…⋅W(m−1)/2, let P=x⋅W1⋅…⋅W(m−1)/2. Then w(P)=m, and for j∈[0,m] we take Q=xε∏i∈IWi with ε∈{0,1}, ε≡j(mod2) and ∣I∣=(j−ε)/2. If x∣W1⋅…⋅W(m−1)/2, there exists i0∈[1,(m−1)/2] such that x∣Wi0. Since σ(Wi0)=2x, we have Wi0=x2. Let P=W1⋅…⋅W(m−1)/2, so w(P)=m−1. For even j, we take Q=∏i∈IWi with ∣I∣=j/2. For odd j, we take Q=x⋅∏i∈IWi with I⊆[1,(m−1)/2]∖{i0} and ∣I∣=(j−1)/2≤(m−3)/2. In either case, we have w(Q)=j and σ(Q)=jx. This contradicts Lemma 4.1 and proves (10).
Applying Lemma 2.2 to V with k=1, there exist distinct u,v∈Cm satisfying
vu(V)+vv(V)≥2ℓ−2m+2≥m+2b−M.(11)
For every w∈2supp(π(S1))={2h:h∈supp(π(S1))}, by (10), we have vw(V)≤2m−3. Since 1≤z1+z2≤z3+z4≤⋯≤2m−3, and ord(e)=m, each element of Cm occurs at most twice among the sums (z2j−1+z2j)e. Thus, for every w∈/2supp(π(S1)), we have