betaFeedback

WorksMathematics

Zero-sum subsequences of cross number 11 over cyclic groups

Abstract

Let GG be a finite abelian group, and let T(G)\mathsf{T}(G) be the smallest integer tt such that every sequence of length tt over GG contains a nonempty zero-sum subsequence of cross number 11. We determine the exact value of T(Cn)\mathsf{T}(C_n) for every positive integer nn, showing that T(Cn)=2n−1\mathsf{T}(C_n)=2n-1 when nn is odd and T(Cn)=3n/2−1\mathsf{T}(C_n)=3n/2-1 when nn is even. In particular, T(Cn)=s(Cn)\mathsf{T}(C_n)=\mathsf{s}(C_n) for odd nn.

Introduction and main results

Given a positive integer nn and integers a1,…,aℓa_1,\ldots,a_\ell, we ask whether there exists a nonempty subset I⊆[1,ℓ]I\subseteq[1,\ell] such that n∣∑i∈Iain\mid\sum_{i\in I}a_i and ∑i∈Igcd⁡(ai,n)=n\sum_{i\in I}\gcd(a_i,n)=n. We show that the sharp bound is ℓ=2n−1\ell=2n-1 for odd nn and ℓ=3n/2−1\ell=3n/2-1 for even nn. This problem can be formulated in terms of zero-sum subsequences of cross number 1 over cyclic groups.

Let GG be a finite abelian group, written additively. We denote by CnC_n a cyclic group of order nn. For a general finite abelian group GG, we can decompose GG as a direct sum of cyclic groups Cn1⊕⋯⊕CnrC_{n_1}\oplus\cdots\oplus C_{n_r} such that 1<n1∣⋯∣nr∈N1<n_1\mid\cdots\mid n_r\in\mathbb{N} (if n1=⋯=nr=nn_1=\cdots=n_r=n, it will be abbreviated as CnrC_n^r), where rr and nrn_r are respectively called the rank and exponent of GG. Usually, the exponent of GG is simply denoted by exp⁡(G)\exp(G). The order of an element gg of GG will be written as ord⁡(g)\operatorname{ord}(g).

A sequence over GG is a finite unordered product S=g1⋯gℓS=g_1\cdots g_\ell, where repetitions are allowed. The cross number of S=g1⋯gℓS=g_1\cdots g_\ell is

k(S)=∑i=1ℓ1ord⁡(gi).\mathrm{k}(S)=\sum_{i=1}^{\ell}\frac{1}{\operatorname{ord}(g_i)}.

For a finite abelian group GG and a positive integer kk, let sk(G)s_k(G) denote the smallest integer tt such that every sequence over GG of length tt contains a zero-sum subsequence of length kexp⁡(G)k\exp(G). In particular, s1(G)=s(G)s_1(G)=s(G) is the classical Erdős–Ginzburg–Ziv constant. The Erdős–Ginzburg–Ziv theorem gives s(Cn)=2n−1s(C_n)=2n-1 for every positive integer nn (see [1]). For further results on these constants, we refer to [2, 5].

Let T(G)T(G) be the smallest integer tt such that every sequence of length tt over GG contains a nonempty zero-sum subsequence of cross number 1. In recent years, Gao, Hui, Jiang, Li and

2020 Mathematics Subject Classification: 11B30, 11B75, 20K01.

Keywords: Finite abelian group, Zero-sum theory, Cross number. Wang introduced T(G)T(G) and studied its relation to classical zero-sum constants (see [3]). They determined T(Cn)T(C_n) for prime powers and established T(Cn)=s(Cn)T(C_n)=s(C_n) for several further classes of odd integers. They also conjectured that T(Cnr)=s(Cnr)T(C_n^r)=s(C_n^r) for all odd integers n>1n>1 and positive integers rr. We determine the invariant for all cyclic groups CnC_n.

Theorem 1.1. For every positive integer nn,

T(Cn)={2n−1,n odd,3n2−1,n even.T(C_n)= \begin{cases} 2n-1, & n\ \text{odd},\\ \frac{3n}{2}-1, & n\ \text{even}. \end{cases}

The lower bounds follow from the sequences in [3 Lemma 3.1]. For n=1n=1, there is nothing to prove. Let n>1n>1 and let gg generate CnC_n. If nn is odd, then gn−1⋅(−g)n−1g^{n-1}\cdot(-g)^{n-1} contains no zero-sum subsequence of length nn. If nn is even, the same holds for gn−1⋅(−g)n/2−1g^{n-1}\cdot(-g)^{n/2-1}. Since every term of these sequences has order nn, a subsequence TT satisfies k(T)=∣T∣/n\mathsf{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\mathbb{N} the set of positive integers, by N0\mathbb{N}_0 the set N∪{0}\mathbb{N}\cup\{0\} and by Z\mathbb{Z} the set of integers. For any a,b∈Za,b\in\mathbb{Z}, we set [a,b]={x∈Z∣a≤x≤b}[a,b]=\{x\in\mathbb{Z}\mid a\leq x\leq b\}. For any real number xx, let ⌈x⌉\lceil x\rceil be the smallest integer not less than xx, and ⌊x⌋\lfloor x\rfloor be the largest integer not greater than xx.

Throughout this paper, let pp be a prime and GG be a finite additive abelian group with identity element 00. For a set XX, we denote by F(X)\mathcal{F}(X) the free (abelian, multiplicative) monoid with basis XX. The elements of F(X)\mathcal{F}(X) are called sequences over XX. We can write a sequence S∈F(X)S\in\mathcal{F}(X) in the form

S=∏g∈Xgvg(S),S=\prod_{g\in X}g^{\mathsf{v}_g(S)},

where vg(S)∈N0\mathsf{v}_g(S)\in\mathbb{N}_0 is called the multiplicity of the element gg in SS. We say that SS contains the element gg of XX if vg(S)>0\mathsf{v}_g(S)>0. A sequence S′S' is called a subsequence of SS, denoted by S′∣SS'\mid S, if vg(S′)≤vg(S)\mathsf{v}_g(S')\leq\mathsf{v}_g(S) for all g∈Xg\in X. The sequence SS′−1SS'^{-1} denotes the subsequence obtained from SS by deleting S′S'. Two subsequences S′S' and S′′S'' of SS are called disjoint if S′∣SS′′−1S'\mid SS''^{-1}. The unit element 1∈F(X)1\in\mathcal{F}(X) is called the empty sequence.

For a group GG and a sequence

S=g1⋯gℓ=∏g∈Ggvg(S)∈F(G),S=g_1\cdots g_\ell=\prod_{g\in G}g^{\mathsf{v}_g(S)}\in\mathcal{F}(G),

we define

  • ∣S∣=ℓ=∑g∈Gvg(S)∈N0|S|=\ell=\sum_{g\in G}\mathsf{v}_g(S)\in\mathbb{N}_0 the length of SS,

  • h(S)=max⁡{vg(S)∣g∈G}∈[0,∣S∣]\mathsf{h}(S)=\max\{\mathsf{v}_g(S)\mid g\in G\}\in[0,|S|] the maximum of the multiplicities of SS,

  • σ(S)=∑i=1ℓgi=∑g∈Gvg(S)g∈G\sigma(S)=\sum_{i=1}^{\ell}g_i=\sum_{g\in G}\mathsf{v}_g(S)g\in G the sum of SS,

  • supp⁡(S)={g∈G∣vg(S)>0}⊆G\operatorname{supp}(S)=\{g\in G\mid\mathsf{v}_g(S)>0\}\subseteq G the support of SS,

  • SS a zero-sum sequence if $\sigma(S)=0\in G.

Every map of abelian groups φ:G→H\varphi:G\to H can be extended to a homomorphism φ:F(G)→F(H)\varphi:\mathcal{F}(G)\to\mathcal{F}(H), where φ(S)=φ(g1)⋯φ(gℓ)\varphi(S)=\varphi(g_1)\cdots\varphi(g_\ell). If φ\varphi is a homomorphism, then φ(S)\varphi(S) is a zero-sum sequence over HH if and only if σ(S)∈ker⁡(φ)\sigma(S)\in\ker(\varphi). Moreover, φ(σ(S))=σ(φ(S))\varphi(\sigma(S))=\sigma(\varphi(S)).

We collect some known results which will be used later.

Lemma 2.1 [4]. Let n,kn,k be positive integers. Every sequence of length (k+1)n−1(k+1)n-1 over CnC_n has a zero-sum subsequence of length knkn.

Lemma 2.2 [2 Lemma 2.2]. Let n,k,tn,k,t be positive integers with 2≤t<n/2+12\le t<n/2+1, and let SS be a sequence over CnC_n of length (k+1)n−t(k+1)n-t. If SS contains no zero-sum subsequence of length knkn, then there exist distinct x,y∈Cnx,y\in C_n such that

vx(S)+vy(S)≥(k+1)n−2t+2.v_x(S)+v_y(S)\ge(k+1)n-2t+2.

Lemma 2.3 (Kleitman–Lemke [6]). Let nn be a positive integer. Every sequence of length nn over CnC_n has a nonempty zero-sum subsequence TT with k(T)≤1\mathsf{k}(T)\le1.

For a positive integer nn, let τ(n)\tau(n) denote its number of positive divisors, ω(n)\omega(n) its number of distinct prime divisors, and vp(n)v_p(n) the exponent of a prime pp in nn. All sums indexed by p∣np\mid n are over the distinct prime divisors of nn.

Lemma 2.4. Let nn be a positive integer and let k=ω(n)k=\omega(n).

(i) If n≥3n\ge3 is odd, then k(τ(n)−3)≤(n+3)/4k(\tau(n)-3)\le(n+3)/4.

(ii) If 4∣n4\mid n and k≥4k\ge4, then n≥4kτ(n)n\ge4k\tau(n).

(iii) If nn is odd and k≥4k\ge4, then n≥8kτ(n)n\ge8k\tau(n).

Proof. For every prime pp, the ratio pa/(a+1)p^a/(a+1) increases with a≥1a\ge1, since the ratio of consecutive terms is p(a+1)/(a+2)>1p(a+1)/(a+2)>1.

For (i), let n=p1a1⋯pkakn=p_1^{a_1}\cdots p_k^{a_k} with p1<⋯<pkp_1<\cdots<p_k odd primes. If k=1k=1, then 4(a1−2)≤3a1+3≤n+34(a_1-2)\le3^{a_1}+3\le n+3. If k=2k=2, it suffices to prove 8τ(n)≤n+278\tau(n)\le n+27. We prove it by induction. This holds for a1=a2=1a_1=a_2=1, since τ(n)=4\tau(n)=4 and n≥15n\ge15. Suppose that 8τ(m)≤m+278\tau(m)\le m+27, where mm has exactly two distinct odd prime divisors. For any prime p∣mp\mid m, we have τ(pm)≤3τ(m)/2\tau(pm)\le3\tau(m)/2. Thus,

8τ(pm)≤12τ(m)≤32(m+27)≤3m+27≤pm+27.8\tau(pm)\le12\tau(m)\le\frac{3}{2}(m+27)\le3m+27\le pm+27.

If k≥3k\ge3,

nτ(n)≥32⋅52⋅72⋅(32)k−3≥1058(32)k−3≥4k,\frac{n}{\tau(n)}\ge\frac{3}{2}\cdot\frac{5}{2}\cdot\frac{7}{2}\cdot\left(\frac{3}{2}\right)^{k-3}\ge\frac{105}{8}\left(\frac{3}{2}\right)^{k-3}\ge4k,

which proves (i).

For (ii), the exponent of 22 is at least 22, so

nτ(n)≥43⋅32⋅52⋅72⋅(32)k−4=352(32)k−4≥4k.\frac{n}{\tau(n)}\ge\frac{4}{3}\cdot\frac{3}{2}\cdot\frac{5}{2}\cdot\frac{7}{2}\cdot\left(\frac{3}{2}\right)^{k-4}=\frac{35}{2}\left(\frac{3}{2}\right)^{k-4}\ge4k.

For (iii), similarly,

nτ(n)≥32⋅52⋅72⋅112⋅(32)k−4=115516(32)k−4≥8k.\frac{n}{\tau(n)}\ge\frac{3}{2}\cdot\frac{5}{2}\cdot\frac{7}{2}\cdot\frac{11}{2}\cdot\left(\frac{3}{2}\right)^{k-4}=\frac{1155}{16}\left(\frac{3}{2}\right)^{k-4}\ge8k.

For each d∣nd\mid n, let Sd∈F(dCn)S_d\in\mathcal{F}(dC_n) be a prescribed sequence, and let S=∏d∣nSdS=\prod_{d\mid n}S_d. The subsequences SdS_d are distinguished by their indices dd, even if their supports intersect. For example, S1S_1 is a prescribed subsequence, not the subsequence of all terms belonging to CnC_n.

Proposition 2.5. Let nn be a positive integer, and let Sd∈F(dCn)S_d \in\mathcal{F}(dC_n) for every d∣nd \mid n. Suppose that one of the following holds:

(i) nn is odd and ∑d∣n∣Sd∣=2n−1\sum_{d\mid n} |S_d| = 2n - 1;

(ii) nn is even, ∑d∣n∣Sd∣=3n/2−1\sum_{d\mid n} |S_d| = 3n/2 - 1, and supp⁡(Sd)∩2dCn=∅\operatorname{supp}(S_d) \cap2dC_n = \varnothing if 2d∣n2d \mid n.

Then there exist Td∣SdT_d \mid S_d such that

∑d∣nσ(Td)=0,∑d∣nd∣Td∣=n.(1)\sum_{d\mid n} \sigma(T_d) = 0,\qquad\sum_{d\mid n} d|T_d| = n. \tag*{(1)}

We now give a short proof of Theorem 1.1 using Proposition 2.5.

Proof of Theorem 1.1. Let SS be a sequence of length 2n−12n - 1 for odd nn, or 3n/2−13n/2 - 1 for even nn over CnC_n. For each d∣nd \mid n, let SdS_d consist of its terms of order exactly n/dn/d. Such terms generate dCndC_n, so Sd∈F(dCn)S_d \in\mathcal{F}(dC_n) and, if 2d∣n2d \mid n, no term belongs to the proper subgroup 2dCn2dC_n. Proposition 2.5 gives Td∣SdT_d \mid S_d satisfying (2.1). Then T=∏d∣nTdT = \prod_{d\mid n} T_d is nonempty and zero-sum, and

k(T)=∑d∣n∣Td∣n/d=1n∑d∣nd∣Td∣=1.\mathsf{k}(T) = \sum_{d\mid n} \frac{|T_d|}{n/d} = \frac{1}{n}\sum_{d\mid n}d|T_d| = 1.

Together with the lower bounds, this proves the theorem. □

In Proposition 2.5, the terms of SdS_d are not required to have order exactly n/dn/d. This is essential for the inductive argument. If pd∣npd \mid n and R∣SdR \mid S_d satisfies ∣R∣=p|R| = p and σ(R)∈pdCn\sigma(R) \in pdC_n, then replacing RR by the single term σ(R)\sigma(R) in SpdS_{pd} preserves the total sum and the value of ∑d∣nd∣Sd∣\sum_{d\mid n}d|S_d|, since d∣R∣=pdd|R| = pd. This does not require ord⁡(σ(R))=n/(pd)\operatorname{ord}(\sigma(R)) = n/(pd).

Odd order

Proof of Proposition 2.5(i). We prove the assertion by induction on the odd integer nn. The assertion is immediate for n=1n = 1. Let n>1n > 1, and suppose it holds for every positive odd integer d<nd < n. Suppose, to the contrary, that a sequence S=∏d∣nSdS = \prod_{d\mid n} S_d of length 2n−12n - 1 has no subsequences satisfying (2.1). Since nCn={0}nC_n = \{0\}, we have Sn=1F(Cn)S_n = 1_{\mathcal{F}(C_n)}. For every prime p∣np \mid n, let Xp=∑d∣n, p∣d∣Sd∣X_p = \sum_{d\mid n,\,p\mid d}|S_d|, and let M=∑d∣n, d>1∣Sd∣M = \sum_{d\mid n,\,d>1}|S_d|.

We first prove that Xp≤τ(n)−3X_p \leq\tau(n) - 3 for every prime p∣np \mid n.

Choose a prime p∣np \mid n. For each d∣nd \mid n with p∤dp \nmid d, let πp:dCn→dCn/pdCn≅Cp\pi_p : dC_n \to dC_n/pdC_n \cong C_p be the canonical homomorphism. By Lemma 2.1, choose a maximal family of pairwise disjoint subsequences Td,1,…,Td,ad∣SdT_{d,1},\ldots,T_{d,a_d} \mid S_d with ∣Td,i∣=p|T_{d,i}| = p and σ(πp(Td,i))=0\sigma(\pi_p(T_{d,i})) = 0, and hence σ(Td,i)∈pdCn\sigma(T_{d,i}) \in pdC_n for every i∈[1,ad]i \in[1,a_d]. Let Rd=Sd⋅(Td,1⋯Td,ad)−1R_d = S_d \cdot(T_{d,1}\cdots T_{d,a_d})^{-1}, and hence ∣Rd∣≤2p−2|R_d| \leq2p - 2.

Let φ:Cn/p→pCn\varphi: C_{n/p} \to pC_n be an isomorphism. For each e∣n/pe \mid n/p, set

Ue={φ−1(Spe)⋅∏i=1aeφ−1(σ(Te,i)),p∤e,φ−1(Spe),p∣e.(2)U_e = \begin{cases} \varphi^{-1}(S_{pe}) \cdot\prod_{i=1}^{a_e}\varphi^{-1}(\sigma(T_{e,i})), & p \nmid e,\\ \varphi^{-1}(S_{pe}), & p \mid e. \end{cases} \tag*{(2)}

Since φ(eCn/p)=peCn\varphi(eC_{n/p}) = peC_n, we have Ue∈F(eCn/p)U_e \in\mathcal{F}(eC_{n/p}) and ∑e∣n/p∣Ue∣=Xp+∑d∣n, p∤dad\sum_{e\mid n/p}|U_e| = X_p + \sum_{d\mid n,\,p\nmid d}a_d. Suppose that ∑e∣n/p∣Ue∣≥2(n/p)−1\sum_{e\mid n/p}|U_e| \geq2(n/p) - 1. By the induction hypothesis, there exist Ve∣UeV_e \mid U_e such that

∑e∣n/pσ(Ve)=0,∑e∣n/pe∣Ve∣=np.\sum_{e\mid n/p}\sigma(V_e) = 0,\qquad\sum_{e\mid n/p}e|V_e| = \frac{n}{p}.

Write φ(Ve)=Ae⋅∏i∈Ieσ(Te,i)\varphi(V_e)=A_e\cdot\prod_{i\in I_e}\sigma(T_{e,i}), where Ae∣SpeA_e\mid S_{p e}, Ie⊆[1,ae]I_e\subseteq[1,a_e] if p∤ep\nmid e, and Ie=∅I_e=\varnothing if p∣ep\mid e. Then ∣Ve∣=∣Ae∣+∣Ie∣|V_e|=|A_e|+|I_e|. For each d∣nd\mid n, let

Td={∏i∈IdTd,i,p∤d,Ad/p,p∣d.T_d= \begin{cases} \prod_{i\in I_d}T_{d,i}, & p\nmid d,\\ A_{d/p}, & p\mid d. \end{cases}

Since the subsequences Td,1,…,Td,adT_{d,1},\ldots,T_{d,a_d} are pairwise disjoint, we have Td∣SdT_d\mid S_d for every d∣nd\mid n. Moreover,

∑d∣nσ(Td)=∑e∣n/p(σ(Ae)+∑i∈Ieσ(Te,i))=φ(∑e∣n/pσ(Ve))=0,\sum_{d\mid n}\sigma(T_d)=\sum_{e\mid n/p}\left(\sigma(A_e)+\sum_{i\in I_e}\sigma(T_{e,i})\right) =\varphi\left(\sum_{e\mid n/p}\sigma(V_e)\right)=0,

and

∑d∣nd∣Td∣=∑d∣np∣dd∣Ad/p∣+∑d∣np∤dpd∣Id∣=p∑e∣n/pe(∣Ae∣+∣Ie∣)=p∑e∣n/pe∣Ve∣=n.\sum_{d\mid n}d|T_d|=\sum_{\substack{d\mid n\\p\mid d}}d|A_{d/p}|+\sum_{\substack{d\mid n\\p\nmid d}}pd|I_d| =p\sum_{e\mid n/p}e(|A_e|+|I_e|)=p\sum_{e\mid n/p}e|V_e|=n.

This contradicts our assumption. Hence,

Xp+∑d∣np∣dad≤2np−2.(3)X_p+\sum_{\substack{d\mid n\\p\mid d}}a_d\le\frac{2n}{p}-2. \tag*{(3)}

Since ∑d∣np∤d∣Sd∣=2n−1−Xp\sum_{\substack{d\mid n\\p\nmid d}}|S_d|=2n-1-X_p, multiplying (3) by pp yields

(p−1)Xp+2p−1≤∑d∣np∣d∣Rd∣.(p-1)X_p+2p-1\le\sum_{\substack{d\mid n\\p\mid d}}|R_d|.

Since precisely τ(n)/(vp(n)+1)\tau(n)/(v_p(n)+1) positive divisors of nn are not divisible by pp, we have

∑d∣np∣d∣Rd∣≤(2p−2)τ(n)vp(n)+1≤(p−1)τ(n).\sum_{\substack{d\mid n\\p\mid d}}|R_d|\le\frac{(2p-2)\tau(n)}{v_p(n)+1}\le(p-1)\tau(n).

It follows that Xp≤τ(n)−(2p−1)/(p−1)<τ(n)−2X_p\le\tau(n)-(2p-1)/(p-1)<\tau(n)-2, and therefore Xp≤τ(n)−3X_p\le\tau(n)-3. By the definition of XpX_p and Lemma 2.4(i), we have

M=∑d∣nd>1∣Sd∣≤∑d∣nd>1ω(d)∣Sd∣=∑p∣nXp≤ω(n)(τ(n)−3)≤n+34.(4)M=\sum_{\substack{d\mid n\\d>1}}|S_d|\le\sum_{\substack{d\mid n\\d>1}}\omega(d)|S_d|=\sum_{p\mid n}X_p\le\omega(n)(\tau(n)-3)\le\frac{n+3}{4}. \tag*{(4)}

If nn is prime, the estimate Xn≤τ(n)−3=−1X_n\le\tau(n)-3=-1 is already a contradiction. We may therefore assume that nn is composite, so n≥9n\ge9.

Since the sequence S1S_1 of length 2n−1−M2n-1-M has no zero-sum subsequence of length nn, by Lemma 2.1, we have M≥1M\ge1. Taking t=M+1t=M+1, we have 2≤t<n/2+12\le t<n/2+1 by (4). By Lemma 2.2, with k=1k=1, there exist distinct x,y∈Cnx,y\in C_n such that vx(S1)+vy(S1)≥2n−2Mv_x(S_1)+v_y(S_1)\ge2n-2M.

Since S1S_1 contains no zero-sum subsequence of length nn and ng=0ng=0 for every g∈Cng\in C_n, we have vg(S1)≤n−1v_g(S_1)\le n-1 for every g∈Cng\in C_n. Write vx(S1)=n−1−αv_x(S_1)=n-1-\alpha and vy(S1)=n−1−βv_y(S_1)=n-1-\beta, where α,β≥0\alpha,\beta\ge0. Then

α+β≤2M−2≤n−12.\alpha+\beta\le2M-2\le\frac{n-1}{2}.

We claim that u=x−yu=x-y generates CnC_n. Otherwise, e=ord⁡(u)e=\operatorname{ord}(u) is a proper divisor of nn, so e≤n/3e\le n/3. For every integer aa with β+1≤a≤n−1−α\beta+1\le a\le n-1-\alpha, the sequence xa⋅yn−ax^a\cdot y^{n-a} divides S1S_1 and has sum auau. This interval contains n−1−α−β≥(n−1)/2≥en-1-\alpha-\beta\ge(n-1)/2\ge e consecutive integers, and hence contains a multiple of ee. The corresponding subsequence is zero-sum and has length nn, a contradiction.

Let r=α+β+1r=\alpha+\beta+1. Choose g1,…,gr∈Cng_1,\ldots,g_r\in C_n and divisors d1,…,drd_1,\ldots,d_r of nn such that, for every d∣nd\mid n,

∏1≤j≤rdj=dgj={S1(xn−1−α⋅yn−1−β)−1,d=1,Sd,d>1.\prod_{\substack{1\le j\le r\\d_j=d}}g_j= \begin{cases} S_1(x^{n-1-\alpha}\cdot y^{n-1-\beta})^{-1}, & d=1,\\ S_d, & d>1. \end{cases}

Then S=xn−1−α⋅yn−1−β⋅g1⋅…⋅grS=x^{n-1-\alpha}\cdot y^{n-1-\beta}\cdot g_1\cdot\ldots\cdot g_r, where gj∈djCng_j\in d_jC_n for every j∈[1,r]j\in[1,r], and gj∉{x,y}g_j\notin\{x,y\} whenever dj=1d_j=1. Since u=x−yu=x-y generates CnC_n and djy−gj∈djCnd_jy-g_j\in d_jC_n, there is a unique Dj∈{0,dj,2dj,…,n−dj}D_j\in\{0,d_j,2d_j,\ldots,n-d_j\} such that gj=djy−Djug_j=d_jy-D_ju.

Consider the subsequence T=xa⋅yb⋅∏j∈Jgj∣ST=x^a\cdot y^b\cdot\prod_{j\in J}g_j\mid S, where J⊆[1,r]J\subseteq[1,r], 0≤a≤n−1−α0\le a\le n-1-\alpha and 0≤b≤n−1−β0\le b\le n-1-\beta, with the factorization T1=xayb∏j∈J,dj=1gjT_1=x^ay^b\prod_{j\in J,d_j=1}g_j and Td=∏j∈J,dj=dgjT_d=\prod_{j\in J,d_j=d}g_j for d>1d>1. Then

∑d∣nd∣Td∣=a+b+∑j∈Jdj,\sum_{d\mid n}d|T_d|=a+b+\sum_{j\in J}d_j,

and,

σ(T)=(a+b+∑j∈Jdj)y+(a−∑j∈JDj)u.\sigma(T)=\left(a+b+\sum_{j\in J}d_j\right)y+\left(a-\sum_{j\in J}D_j\right)u.

Hence, TT satisfies (2.1) as soon as a+b+∑j∈Jdj=na+b+\sum_{j\in J}d_j=n and a≡∑j∈JDj(modn)a\equiv\sum_{j\in J}D_j\pmod n.

We shall show that these two conditions hold for some J⊆[1,r]J\subseteq[1,r], 0≤a≤n−1−α0\le a\le n-1-\alpha, and 0≤b≤n−1−β0\le b\le n-1-\beta.

Suppose first that there exists j∈[1,r]j\in[1,r] such that Dj≤n−1−αD_j\le n-1-\alpha and Dj+dj≥β+1D_j+d_j\ge\beta+1. Take J={j}J=\{j\}, a=Dja=D_j, and b=n−dj−Djb=n-d_j-D_j. Then these two conditions hold.

Otherwise, for every j∈[1,r]j\in[1,r], either Dj+dj≤βD_j+d_j\le\beta or n−Dj≤αn-D_j\le\alpha. These two inequalities cannot both hold, since their sum would give n+dj≤α+β≤(n−1)/2n+d_j\le\alpha+\beta\le(n-1)/2. Thus

Y={j∈[1,r]:Dj+dj≤β},X={j∈[1,r]:n−Dj≤α}Y=\{j\in[1,r]:D_j+d_j\le\beta\},\qquad X=\{j\in[1,r]:n-D_j\le\alpha\}

partition [1,r][1,r].

For j∈Yj\in Y, we have Dj+dj≥2D_j+d_j\ge2. Otherwise, dj=1d_j=1 and Dj=0D_j=0, which gives gj=yg_j=y, contradicting gj∉{x,y}g_j\notin\{x,y\} whenever dj=1d_j=1. Similarly, for j∈Xj\in X, we have n−Dj≥2n-D_j\ge2. Otherwise, Dj=n−1D_j=n-1 and dj=1d_j=1, which gives gj=xg_j=x, contradicting gj∉{x,y}g_j\notin\{x,y\} whenever dj=1d_j=1. Consequently,

∑j∈Y(Dj+dj)+∑j∈X(n−Dj)≥2r>α+β.\sum_{j\in Y}(D_j+d_j)+\sum_{j\in X}(n-D_j)\ge2r>\alpha+\beta.

Suppose that ∑j∈Y(Dj+dj)≥β+1\sum_{j\in Y}(D_j+d_j)\ge\beta+1. Choose a minimal subset J⊆YJ\subseteq Y such that ∑j∈J(Dj+dj)≥β+1\sum_{j\in J}(D_j+d_j)\ge\beta+1. Since Dj+dj≤βD_j+d_j\le\beta for j∈Yj\in Y, minimality gives β+1≤∑j∈J(Dj+dj)≤2β\beta+1\le\sum_{j\in J}(D_j+d_j)\le2\beta. Take a=∑j∈JDja=\sum_{j\in J}D_j and b=n−∑j∈J(Dj+dj)b=n-\sum_{j\in J}(D_j+d_j). Since α+β≤(n−1)/2\alpha+\beta\le(n-1)/2, we obtain 0≤a≤2β≤n−1−α0\le a\le2\beta\le n-1-\alpha, 0≤n−2β≤b≤n−1−β0\le n-2\beta\le b\le n-1-\beta. Hence, these two conditions hold.

It remains to consider ∑j∈Y(Dj+dj)≤β\sum_{j\in Y}(D_j+d_j)\le\beta. Then ∑j∈X(n−Dj)≥α+1\sum_{j\in X}(n-D_j)\ge\alpha+1. Choose a minimal subset J⊆XJ\subseteq X such that ∑j∈J(n−Dj)≥α+1\sum_{j\in J}(n-D_j)\ge\alpha+1. Since n−Dj≤αn-D_j\le\alpha for j∈Xj\in X, we have α+1≤∑j∈J(n−Dj)≤2α\alpha+1\le\sum_{j\in J}(n-D_j)\le2\alpha. Take a=n−∑j∈J(n−Dj)a=n-\sum_{j\in J}(n-D_j) and b=∑j∈J(n−Dj−dj)b=\sum_{j\in J}(n-D_j-d_j). Since Dj≤n−djD_j\le n-d_j and α+β≤(n−1)/2\alpha+\beta\le(n-1)/2, we obtain 0≤n−2α≤a≤n−1−α0\le n-2\alpha\le a\le n-1-\alpha, 0≤b≤2α≤n−1−β0\le b\le2\alpha\le n-1-\beta. Thus, these two conditions also hold in this situation.

In each situation, the resulting subsequences Td∣SdT_d\mid S_d satisfy (2.1), contrary to our assumption. This completes the induction.

Even order

For T=∏d∣nTdT = \prod_{d\mid n} T_d with Td∣SdT_d \mid S_d, let w(T)=∑d∣nd∣Td∣\mathop{\rm w}(T) = \sum_{d\mid n} d|T_d|, where the terms of each TdT_d are taken from the prescribed sequence SdS_d. Then ∣T∣≤w(T)|T| \le\mathop{\rm w}(T), and w(UV)=w(U)+w(V)\mathop{\rm w}(UV) = \mathop{\rm w}(U) + \mathop{\rm w}(V) for disjoint subsequences U,VU,V with these factorizations. Thus (1) is equivalent to σ(T)=0\sigma(T) = 0 and w(T)=n\mathop{\rm w}(T) = n.

Lemma 4.1. Let n=2mn = 2m be a positive even integer, and let S=∏d∣nSdS = \prod_{d\mid n} S_d, where Sd∈F(dCn)S_d \in\mathcal{F}(dC_n), ∣S∣=3m−1|S| = 3m - 1, and supp⁡(Sd)∩2dCn=∅\operatorname{supp}(S_d) \cap2dC_n = \varnothing whenever 2d∣n2d \mid n. Suppose that x∈Cn∖2Cnx \in C_n \setminus2C_n and P∣SP \mid S satisfy m−1≤w(P)≤mm - 1 \le\mathop{\rm w}(P) \le m, and that, for every j∈[0,w(P)]j \in[0,\mathop{\rm w}(P)], there exists Q∣PQ \mid P such that w(Q)=j\mathop{\rm w}(Q) = j and σ(Q)=jx\sigma(Q) = jx. Then SS contains a zero-sum subsequence TT with w(T)=n\mathop{\rm w}(T) = n.

Proof. Choose U∣SP−1U \mid SP^{-1} satisfying σ(U)=w(U)x\sigma(U) = \mathop{\rm w}(U)x and w(U)≤n−1−w(P)\mathop{\rm w}(U) \le n - 1 - \mathop{\rm w}(P) such that w(U)\mathop{\rm w}(U) is maximal, where the empty sequence is admitted. Since ∣P∣≤w(P)|P| \le\mathop{\rm w}(P) and ∣U∣≤w(U)|U| \le\mathop{\rm w}(U), we have

∣S(PU)−1∣≥3m−1−w(P)−w(U)≥3m−1−(n−1)=m.|S(PU)^{-1}| \ge3m - 1 - \mathop{\rm w}(P) - \mathop{\rm w}(U) \ge3m - 1 - (n - 1) = m.

Let R=g1⋅…⋅gmR = g_1 \cdot\ldots\cdot g_m be a subsequence of S(PU)−1S(PU)^{-1}, where, for each i∈[1,m]i \in[1,m], gig_i is a term of SdiS_{d_i} with di∣nd_i \mid n.

If did_i is even, then gi,dix∈diCn⊆2Cng_i,d_i x \in d_iC_n \subseteq2C_n. If did_i is odd, then 2di∣n2d_i \mid n and diCn∩2Cn=2diCnd_iC_n \cap2C_n = 2d_iC_n. Since supp⁡(Sdi)∩2diCn=∅\operatorname{supp}(S_{d_i}) \cap2d_iC_n = \varnothing, we have gi∈diCn∖2diCng_i \in d_iC_n \setminus2d_iC_n and hence gi∉2Cng_i \notin2C_n. Also, dix∉2Cnd_i x \notin2C_n, since x∉2Cnx \notin2C_n and did_i is odd. Thus, we have gi−dix∈diCn∩2Cng_i - d_i x \in d_iC_n \cap2C_n for any i∈[1,m]i \in[1,m], and hence ord⁡(gi−dix)∣n/di\operatorname{ord}(g_i - d_i x) \mid n/d_i.

Consider the sequence

R′=∏i=1m(gi−dix)∈F(2Cn).R' = \prod_{i=1}^{m}(g_i-d_i x) \in\mathcal{F}(2C_n).

Since ∣R′∣=m=∣2Cn∣|R'| = m = |2C_n|, by Lemma 2.3, there exists a nonempty subsequence V′=∏i∈I(gi−dix)∣R′V' = \prod_{i\in I}(g_i-d_i x) \mid R' such that σ(V′)=0\sigma(V') = 0 and k(V′)=∑i∈I1ord⁡(gi−dix)≤1k(V') = \sum_{i\in I} \frac{1}{\operatorname{ord}(g_i-d_i x)} \le1, where ∅≠I⊆[1,m]\varnothing\ne I \subseteq[1,m]. Let V=∏i∈Igi∣RV = \prod_{i\in I} g_i \mid R. Then σ(V)=∑i∈Igi=∑i∈Idix=w(V)x\sigma(V) = \sum_{i\in I} g_i = \sum_{i\in I} d_i x = \mathop{\rm w}(V)x and 1≤w(V)=∑i∈Idi≤n∑i∈I1ord⁡(gi−dix)≤n1 \le\mathop{\rm w}(V) = \sum_{i\in I} d_i \le n\sum_{i\in I}\frac{1}{\operatorname{ord}(g_i-d_i x)} \le n. Thus, UU and VV are disjoint, and σ(UV)=w(UV)x\sigma(UV) = \mathop{\rm w}(UV)x. The maximality of w(U)\mathop{\rm w}(U) therefore implies w(U)+w(V)≥n−w(P)\mathop{\rm w}(U) + \mathop{\rm w}(V) \ge n - \mathop{\rm w}(P). If w(V)≤n−w(P)−1\mathop{\rm w}(V) \le n - \mathop{\rm w}(P) - 1, we take V∗=UVV^* = UV. Since w(P)≥m−1\mathop{\rm w}(P) \ge m - 1, we have

n−w(P)≤w(V∗)=w(U)+w(V)≤2(n−1−w(P))≤n.n-\mathop{\rm w}(P) \le\mathop{\rm w}(V^*)=\mathop{\rm w}(U)+\mathop{\rm w}(V)\le2(n-1-\mathop{\rm w}(P))\le n.

If w(V)≥n−w(P)\mathop{\rm w}(V) \ge n - \mathop{\rm w}(P), we take V∗=VV^* = V. Thus, we have V∗∣SP−1V^* \mid SP^{-1}, n−w(P)≤w(V∗)≤nn - \mathop{\rm w}(P) \le\mathop{\rm w}(V^*) \le n and σ(V∗)=w(V∗)x\sigma(V^*) = \mathop{\rm w}(V^*)x. Since 0≤n−w(V∗)≤w(P)0 \le n - \mathop{\rm w}(V^*) \le\mathop{\rm w}(P), the hypothesis gives Q∣PQ \mid P such that w(Q)=n−w(V∗)\mathop{\rm w}(Q) = n-\mathop{\rm w}(V^*) and σ(Q)=(n−w(V∗))x\sigma(Q) = (n-\mathop{\rm w}(V^*))x. Hence, T=QV∗T = QV^* is the required subsequence. □

Proof of Proposition 2.5(ii). We prove the assertion by induction on the even integer nn. The assertion is immediate for n=2n = 2. Let n=2m>2n = 2m > 2, and suppose it holds for every positive even integer d<nd < n. Suppose, to the contrary, that a sequence S=∏d∣nSdS = \prod_{d\mid n} S_d of length 3n/2−13n/2 - 1 has no subsequences satisfying (1). Since nCn={0}nC_n = \{0\}, we have Sn=1F(Cn)S_n = 1_{\mathcal{F}(C_n)}. For every prime p∣np \mid n, let Xp=∑d∣n, p∣d∣Sd∣X_p = \sum_{d\mid n,\,p\mid d}|S_d|, and let M=∑d∣n, d>1∣Sd∣M = \sum_{d\mid n,\,d>1}|S_d|.

We first prove that

Xp≤2τ(n)νp(n)+1−3,(5)X_p \le\frac{2\tau(n)}{\nu_p(n)+1}-3, \tag*{(5)}

for every prime p∣np \mid n such that n/pn/p is even. Choose a prime p∣np \mid n such that n/pn/p is even, and let d∣nd \mid n with p∤dp\nmid d.

Suppose that pp is odd. If ∣Sd∣≥2p−1|S_d| \ge2p-1, let R∣SdR \mid S_d with ∣R∣=2p−1|R| = 2p-1. Applying Lemma 2.1 to the image of RR in dCn/pdCn≅CpdC_n/pdC_n \cong C_p, we obtain a subsequence T∣RT \mid R of length pp satisfying σ(T)∈pdCn\sigma(T) \in pdC_n. When 2pd∣n2pd \mid n, we have supp⁡(Sd)⊆dCn∖2dCn\operatorname{supp}(S_d) \subseteq dC_n \setminus2dC_n. Let π2:dCn→dCn/2dCn≅C2\pi_2 : dC_n \to dC_n/2dC_n \cong C_2 be the canonical homomorphism. Thus π2(T)=hp\pi_2(T) = h^p, where hh is the unique nonzero element of dCn/2dCndC_n/2dC_n. Since pp is odd and ord⁡(h)=2\operatorname{ord}(h)=2, we have π2(σ(T))=σ(π2(T))=ph=h≠0\pi_2(\sigma(T))=\sigma(\pi_2(T))=ph=h\ne0. Thus, σ(T)∈pdCn∖2pdCn\sigma(T)\in pdC_n\setminus2pdC_n.

Suppose now that p=2p=2. Then 4∣n4\mid n and dd is odd, so 4d∣n4d\mid n. Let π4:dCn→dCn/4dCn≅C4\pi_4:dC_n\to dC_n/4dC_n\cong C_4 be the canonical homomorphism. If ∣Sd∣≥3|S_d|\ge3, let R=g1g2g3∣SdR=g_1g_2g_3\mid S_d, where gi∈dCn∖2dCng_i\in dC_n\setminus2dC_n for every i∈[1,3]i\in[1,3], so ord⁡(π4(gi))=4\operatorname{ord}(\pi_4(g_i))=4. Since dCn/4dCn≅C4dC_n/4dC_n\cong C_4 has exactly two elements of order 44, there exist distinct i,j∈[1,3]i,j\in[1,3] such that π4(gi)=π4(gj)\pi_4(g_i)=\pi_4(g_j). For T=gigj∣RT=g_ig_j\mid R, we have ∣T∣=2|T|=2 and π4(σ(T))=π4(gi)+π4(gj)=2π4(gi)\pi_4(\sigma(T))=\pi_4(g_i)+\pi_4(g_j)=2\pi_4(g_i). It follows that σ(T)∈2dCn∖4dCn\sigma(T)\in2dC_n\setminus4dC_n.

Consequently, as in the odd-order proof, there is a factorization Sd=Td,1⋅…⋅Td,ad⋅RdS_d=T_{d,1}\cdot\ldots\cdot T_{d,a_d}\cdot R_d such that ∣Td,i∣=p|T_{d,i}|=p for i∈[1,ad]i\in[1,a_d], ∣Rd∣≤2p−2|R_d|\le2p-2, and

σ(Td,i)∈pdCn,σ(Td,i)∉2pdCn if 2pd∣n.\sigma(T_{d,i})\in pdC_n,\qquad\sigma(T_{d,i})\notin2pdC_n\text{ if }2pd\mid n.

Let φ:Cn/p→pCn\varphi:C_{n/p}\to pC_n be an isomorphism and define UeU_e by (3.1). Since φ(2eCn/p)=2peCn\varphi(2eC_{n/p})=2peC_n, we have Ue∈F(eCn/p)U_e\in\mathcal{F}(eC_{n/p}) for every e∣n/pe\mid n/p, and supp⁡(Ue)∩2eCn/p=∅\operatorname{supp}(U_e)\cap2eC_{n/p}=\varnothing whenever 2e∣n/p2e\mid n/p. If

∑e∣n/p∣Ue∣≥3m2p−1,\sum_{e\mid n/p}|U_e|\ge\frac{3m}{2p}-1,

the induction hypothesis and the same construction of TdT_d as in the odd-order proof would give (2.1). Therefore

Xp+∑d∣npi∣dad=∑e∣n/p∣Ue∣≤3mp−2.X_p+\sum_{\substack{d\mid n\\p^i\mid d}}a_d=\sum_{e\mid n/p}|U_e|\le\frac{3m}{p}-2.

Since ∣Sd∣=pad+∣Rd∣|S_d|=pa_d+|R_d| and ∑d∣np∤d∣Sd∣=3m−1−Xp\sum_{\substack{d\mid n\\p\nmid d}}|S_d|=3m-1-X_p, we obtain

(p−1)Xp+2p−1≤∑d∣np∤d∣Rd∣≤(2p−2)τ(n)vp(n)+1.(6)(p-1)X_p+2p-1\le\sum_{\substack{d\mid n\\p\nmid d}}|R_d|\le\frac{(2p-2)\tau(n)}{v_p(n)+1}. \tag*{(6)}

Thus, Xp≤2τ(n)vp(n)+1−3X_p\le\frac{2\tau(n)}{v_p(n)+1}-3.

We claim that h(S1)≤m−2h(S_1)\le m-2. For every x∈Cnx\in C_n, if xm−1∣S1x^{m-1}\mid S_1, then x∉2Cnx\notin2C_n. Taking P=xm−1P=x^{m-1} in Lemma 4.1 gives a contradiction, since Q=xjQ=x^j satisfies w(Q)=jw(Q)=j and σ(Q)=jx\sigma(Q)=jx for every j∈[0,m−1]j\in[0,m-1].

Fix g0∈Cn∖2Cng_0\in C_n\setminus2C_n. Let S1=g1⋅…⋅g∣S1∣S_1=g_1\cdot\ldots\cdot g_{|S_1|} and let

W=∏i=1∣S1∣(gi−g0)∈F(2Cn)≅F(Cm).W=\prod_{i=1}^{|S_1|}(g_i-g_0)\in\mathcal{F}(2C_n)\cong\mathcal{F}(C_m).

If WW contains a zero-sum subsequence W′=∏i∈I(gi−g0)W'=\prod_{i\in I}(g_i-g_0), where I⊆[1,∣S1∣]I\subseteq[1,|S_1|] and ∣I∣=2m|I|=2m, then the sequence T=∏i∈Igi∣S1T=\prod_{i\in I}g_i\mid S_1 satisfies (2.1), a contradiction. Thus, WW has no zero-sum subsequence of length 2m2m, and Lemma 2.1 gives ∣W∣≤3m−2|W|\le3m-2. If ∣W∣≥⌊5m/2⌋|W|\ge\lfloor5m/2\rfloor, then t=3m−∣W∣t=3m-|W| satisfies 2≤t≤⌈m/2⌉<m/2+12\le t\le\lceil m/2\rceil<m/2+1. By Lemma 2.2, with k=2k=2, there exist distinct h1,h2∈2Cn≅Cmh_1,h_2\in2C_n\cong C_m such that

νh1(W)+νh2(W)≥3m−2t+2≥2m+1.\nu_{h_1}(W)+\nu_{h_2}(W)\ge3m-2t+2\ge2m+1.

Since νhi(W)=νhi+g0(S1)\nu_{h_i}(W)=\nu_{h_i+g_0}(S_1) for i∈{1,2}i\in\{1,2\}, this contradicts h(S1)≤m−2h(S_1)\le m-2. Therefore ∣S1∣≤⌊5m/2⌋−1|S_1|\le\lfloor5m/2\rfloor-1, which proves M≥⌈m2⌉M\ge\left\lceil\frac{m}{2}\right\rceil.

Suppose that mm is even. Then n/pn/p is even for every prime p∣np\mid n. By the definition of MM,

M≤∑d∣nd>1ω(d)∣Sd∣=∑p∣nXp.M\le\sum_{\substack{d\mid n\\d>1}}\omega(d)|S_d|=\sum_{p\mid n}X_p.

Moreover, for each prime p∣np\mid n,

∑d∣np∤d∣Rd∣≤∣R1∣+∑d>1, d∣np∤d∣Sd∣≤2p−2+M−Xp.\sum_{\substack{d\mid n\\p\nmid d}}|R_d|\le|R_1|+\sum_{\substack{d>1,\ d\mid n\\p\nmid d}}|S_d|\le2p-2+M-X_p.

Together with (6), this gives pXp≤M−1pX_p \le M-1 for every prime p∣np \mid n. If ω(n)≤2\omega(n) \le2, then M≤(5/6)(M−1)M \le(5/6)(M-1), a contradiction. If ω(n)=3\omega(n)=3, set n=2αpβqλn=2^\alpha p^\beta q^\lambda, where α≥2\alpha\ge2, β,λ≥1\beta,\lambda\ge1, and 3≤p<q3 \le p<q. By (5), we have

M≤X2+Xp+Xq≤2(β+1)(λ+1)−3+815(M−1).M \le X_2+X_p+X_q \le2(\beta+1)(\lambda+1)-3+\frac{8}{15}(M-1).

and hence

7M≤30(β+1)(λ+1)−53.7M \le30(\beta+1)(\lambda+1)-53.

Since β+λ≤2βλ\beta+\lambda\le2\beta\lambda, pβ≥3βp^\beta\ge3\beta, and qλ≥5λq^\lambda\ge5\lambda, we obtain

7M≤90βλ−23<105βλ≤7pβqλ≤7n4,7M \le90\beta\lambda-23<105\beta\lambda\le7p^\beta q^\lambda\le\frac{7n}{4},

contrary to M≥⌈n2⌉≥n/4M \ge\left\lceil\frac{n}{2}\right\rceil\ge n/4. If ω(n)≥4\omega(n)\ge4, Lemma 2.4(ii) and (5) yield

M≤∑p∣n(2τ(n)vp(n)+1−3)≤ω(n)(τ(n)−3)<n/4,M\le\sum_{p\mid n}\left(\frac{2\tau(n)}{v_p(n)+1}-3\right)\le\omega(n)(\tau(n)-3)<n/4,

again a contradiction.

It remains to consider n=2mn=2m with m≥3m\ge3 odd. Then n/pn/p is even for every prime p∣mp\mid m. Let b=∣S2∣b=|S_2|. Then

M−b=∑d∣md>1(∣Sd∣+∣S2d∣)≤∑d∣md>1ω(d)(∣Sd∣+∣S2d∣)=∑p∣mXp.M-b=\sum_{\substack{d\mid m\\d>1}}(|S_d|+|S_{2d}|)\le\sum_{\substack{d\mid m\\d>1}}\omega(d)(|S_d|+|S_{2d}|)=\sum_{p\mid m}X_p.

For each prime p∣mp\mid m, we also have

∑d∣np∤d∣Rd∣≤∣R1∣+∣R2∣+∑d∣nd∉{1,2},p∤d∣Sd∣≤4p−4+M−b−Xp.\sum_{\substack{d\mid n\\p\nmid d}}|R_d|\le|R_1|+|R_2|+\sum_{\substack{d\mid n\\d\notin\{1,2\},\,p\nmid d}}|S_d|\le4p-4+M-b-X_p.

Together with (6), this gives

pXp≤M−b+2p−3,(7)pX_p\le M-b+2p-3, \tag*{(7)}

for every prime p∣mp\mid m. We claim that

M−b≤m+14.(8)M-b\le\frac{m+1}{4}. \tag*{(8)}

For ω(m)=1\omega(m)=1, (5) gives M−b≤1M-b\le1. For ω(m)=2\omega(m)=2 and M−b≥3M-b\ge3, (7) gives

M−b≤815(M−b−3)+4,M-b\le\frac{8}{15}(M-b-3)+4,

so M−b≤5M-b\le5. If M−b=5M-b=5, then Xp≤⌊(2p+2)/p⌋=2X_p\le\lfloor(2p+2)/p\rfloor=2 for both primes, giving M−b≤4M-b\le4, a contradiction. Thus M−b≤4≤(m+1)/4M-b\le4\le(m+1)/4. For ω(m)=3\omega(m)=3 and M−b≥3M-b\ge3, by (7), we have

M−b≤(13+15+17)(M−b−3)+6=71105(M−b−3)+6,M-b\le\left(\frac{1}{3}+\frac{1}{5}+\frac{1}{7}\right)(M-b-3)+6=\frac{71}{105}(M-b-3)+6,

so M−b≤12<(m+1)/4M-b\le12<(m+1)/4, since m≥105m\ge105. If ω(m)∈{2,3}\omega(m)\in\{2,3\} and M−b≤2M-b\le2, then (8) holds trivially. For ω(m)≥4\omega(m)\ge4, Lemma 2.4(iii) and (5) give

M−b≤∑p∣m(4τ(m)vp(m)+1−3)≤ω(m)(2τ(m)−3)<m/4.M-b\le\sum_{p\mid m}\left(\frac{4\tau(m)}{v_p(m)+1}-3\right)\le\omega(m)(2\tau(m)-3)<m/4.

This proves the claim.

Since mm is odd, Cn≅C2⊕CmC_n \cong C_2 \oplus C_m. Let π:Cn→Cm\pi: C_n \to C_m be the projection. Then supp⁡(S1)⊆{1}×Cm\operatorname{supp}(S_1) \subseteq\{1\} \times C_m and supp⁡(S2)⊆{0}×Cm\operatorname{supp}(S_2) \subseteq\{0\} \times C_m. By (8) and M≥⌈m2⌉M \ge\left\lceil\frac{m}{2} \right\rceil, we have

b=M−(M−b)≥M−m+14≥M2.(9)b = M - (M-b) \ge M - \frac{m+1}{4} \ge\frac{M}{2}. \tag*{(9)}

Let ee be a generator of CmC_m. Pairing equal terms of S1S_1 as far as possible, we may write

S1=x12⋅…⋅xr2⋅(1,z1e)⋅…⋅(1,zte),S_1 = x_1^2 \cdot\ldots\cdot x_r^2 \cdot(1,z_1e) \cdot\ldots\cdot(1,z_te),

where 0≤z1<⋯<zt≤m−10 \le z_1 < \cdots< z_t \le m-1 and t≤mt \le m. Set Pi=xi2P_i=x_i^2 for i∈[1,r]i \in[1,r] and Pr+j=(1,z2j−1e)⋅(1,z2je)P_{r+j}=(1,z_{2j-1}e)\cdot(1,z_{2j}e) for j∈[1,⌊t/2⌋]j \in[1,\lfloor t/2\rfloor]. If tt is odd, let R′=(1,zte)R'=(1,z_te). Otherwise, let R′R' be the empty sequence. Then S1=P1⋅…⋅Ps⋅R′S_1=P_1\cdot\ldots\cdot P_s\cdot R', where ∣Pi∣=2|P_i|=2, ∣R′∣≤1|R'|\le1 and s=r+⌊t2⌋=⌊∣S1∣2⌋s=r+\left\lfloor\frac{t}{2}\right\rfloor=\left\lfloor\frac{|S_1|}{2}\right\rfloor.

Let

V=π(S2)⋅∏i=1sπ(σ(Pi))∈F(Cm),V=\pi(S_2)\cdot\prod_{i=1}^{s}\pi(\sigma(P_i))\in\mathcal{F}(C_m),

and let ℓ=∣V∣=b+⌊∣S1∣2⌋\ell=|V|=b+\left\lfloor\frac{|S_1|}{2}\right\rfloor.

If VV has a zero-sum subsequence of length mm, there exist A∣S2A\mid S_2 and I⊆[1,s]I\subseteq[1,s] such that ∣A∣+∣I∣=m|A|+|I|=m and π(σ(A)+∑i∈Iσ(Pi))=0\pi(\sigma(A)+\sum_{i\in I}\sigma(P_i))=0. Since σ(A)+∑i∈Iσ(Pi)∈2Cn\sigma(A)+\sum_{i\in I}\sigma(P_i)\in2C_n and π\pi is injective on 2Cn2C_n, it follows that T1=∏i∈IPiT_1=\prod_{i\in I}P_i and T2=AT_2=A, with all other TdT_d empty, satisfy (2.1), a contradiction. By Lemma 2.1, we have ℓ≤2m−2\ell\le2m-2.

If m=3m=3, we have h(S1)≤m−2=1h(S_1)\le m-2=1, and hence ∣S1∣≤3|S_1|\le3. By (8), we have M−b≤1M-b\le1. Since M=8−∣S1∣M=8-|S_1|, ℓ≥7−⌈∣S1∣/2⌉≥5>2m−2\ell\ge7-\lceil|S_1|/2\rceil\ge5>2m-2, a contradiction. Thus m≥5m\ge5, and (8) implies M−b≤⌊(m+1)/4⌋≤(m−3)/2M-b\le\lfloor(m+1)/4\rfloor\le(m-3)/2.

For every h∈supp⁡(π(S1))h\in\operatorname{supp}(\pi(S_1)), we claim that

v2h(V)≤m−32.(10)v_{2h}(V)\le\frac{m-3}{2}. \tag*{(10)}

Assume that there exists h∈supp⁡(π(S1))h\in\operatorname{supp}(\pi(S_1)) satisfying v2h(V)≥(m−1)/2v_{2h}(V)\ge(m-1)/2, and let x=(1,h)x=(1,h). By the definition of VV, there exist pairwise disjoint subsequences W1,…,W(m−1)/2W_1,\ldots,W_{(m-1)/2} of SS such that w(Wi)=2\mathrm{w}(W_i)=2 and σ(Wi)=2x\sigma(W_i)=2x for every i∈[1,(m−1)/2]i\in[1,(m-1)/2]. Each WiW_i is either a term of S2S_2 or one of the pairs PjP_j for some j∈[1,s]j\in[1,s].

If x∤W1⋅…⋅W(m−1)/2x\nmid W_1\cdot\ldots\cdot W_{(m-1)/2}, let P=x⋅W1⋅…⋅W(m−1)/2P=x\cdot W_1\cdot\ldots\cdot W_{(m-1)/2}. Then w(P)=m\mathrm{w}(P)=m, and for j∈[0,m]j\in[0,m] we take Q=xε∏i∈IWiQ=x^\varepsilon\prod_{i\in I}W_i with ε∈{0,1}\varepsilon\in\{0,1\}, ε≡j(mod2)\varepsilon\equiv j\pmod2 and ∣I∣=(j−ε)/2|I|=(j-\varepsilon)/2. If x∣W1⋅…⋅W(m−1)/2x\mid W_1\cdot\ldots\cdot W_{(m-1)/2}, there exists i0∈[1,(m−1)/2]i_0\in[1,(m-1)/2] such that x∣Wi0x\mid W_{i_0}. Since σ(Wi0)=2x\sigma(W_{i_0})=2x, we have Wi0=x2W_{i_0}=x^2. Let P=W1⋅…⋅W(m−1)/2P=W_1\cdot\ldots\cdot W_{(m-1)/2}, so w(P)=m−1\mathrm{w}(P)=m-1. For even jj, we take Q=∏i∈IWiQ=\prod_{i\in I}W_i with ∣I∣=j/2|I|=j/2. For odd jj, we take Q=x⋅∏i∈IWiQ=x\cdot\prod_{i\in I}W_i with I⊆[1,(m−1)/2]∖{i0}I\subseteq[1,(m-1)/2]\setminus\{i_0\} and ∣I∣=(j−1)/2≤(m−3)/2|I|=(j-1)/2\le(m-3)/2. In either case, we have w(Q)=j\mathrm{w}(Q)=j and σ(Q)=jx\sigma(Q)=jx. This contradicts Lemma 4.1 and proves (10).

By (9) and ∣S1∣=3m−1−M|S_1|=3m-1-M, we have

2ℓ≥2b+∣S1∣−1=3m−2+2b−M≥3m−2.2\ell\ge2b+|S_1|-1=3m-2+2b-M\ge3m-2.

Since mm is odd, ℓ≥(3m−1)/2\ell\ge(3m-1)/2. Hence,

2≤2m−ℓ≤(m+1)/2<m/2+1.2\le2m-\ell\le(m+1)/2<m/2+1.

Applying Lemma 2.2 to VV with k=1k=1, there exist distinct u,v∈Cmu,v\in C_m satisfying

vu(V)+vv(V)≥2ℓ−2m+2≥m+2b−M.(11)v_u(V)+v_v(V)\ge2\ell-2m+2\ge m+2b-M. \tag*{(11)}

For every w∈2supp⁡(π(S1))={2h:h∈supp⁡(π(S1))}w\in2\operatorname{supp}(\pi(S_1))=\{2h:h\in\operatorname{supp}(\pi(S_1))\}, by (10), we have vw(V)≤m−32v_w(V)\le\frac{m-3}{2}. Since 1≤z1+z2≤z3+z4≤⋯≤2m−31\le z_1+z_2\le z_3+z_4\le\cdots\le2m-3, and ord⁡(e)=m\operatorname{ord}(e)=m, each element of CmC_m occurs at most twice among the sums (z2j−1+z2j)e(z_{2j-1}+z_{2j})e. Thus, for every w∉2supp⁡(π(S1))w\notin2\operatorname{supp}(\pi(S_1)), we have

vw(V)≤vw(π(S2))+2.v_w(V)\le v_w(\pi(S_2))+2.

If u,v∉2supp⁡(π(S1))u,v\notin2\operatorname{supp}(\pi(S_1)) are distinct, then we have

νu(V)+νv(V)≤νu(π(S2))+νv(π(S2))+⌊t/2⌋≤b+m−12.\nu_u(V)+\nu_v(V)\le\nu_u(\pi(S_2))+\nu_v(\pi(S_2))+\lfloor t/2\rfloor\le b+\frac{m-1}{2}.

If u,v∈2supp⁡(π(S1))u,v\in2\operatorname{supp}(\pi(S_1)) are distinct, then νu(V)+νv(V)≤m−3\nu_u(V)+\nu_v(V)\le m-3. If exactly one of u,vu,v belongs to 2supp⁡(π(S1))2\operatorname{supp}(\pi(S_1)), then

νu(V)+νv(V)≤m−32+b+2=b+m+12.\nu_u(V)+\nu_v(V)\le\frac{m-3}{2}+b+2=b+\frac{m+1}{2}.

Consequently, in all cases,

νu(V)+νv(V)≤max⁡{m−3, b+m+12}<m+2b−M.\nu_u(V)+\nu_v(V)\le\max\left\{m-3,\ b+\frac{m+1}{2}\right\}<m+2b-M.

where the last inequality follows from (4.4) and (4.5). This contradicts (4.7) and completes the induction. □

References

  1. [1]P. Erdős, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel 10F (1961), 41–43.
  2. [2]W. Gao, D. Han, J. Peng and F. Sun, On zero-sum subsequences of length k exp(G), J. Combin. Theory Ser. A 125 (2014), 240–253.DOI
  3. [3]W. Gao, W. Hui, X. Jiang, Y. Li and X. Wang, On zero-sum subsequences of cross number 1, Acta Arith. 219 (2025), 347–363.DOI
  4. [4]W. Gao and R. Thangadurai, On zero-sum sequences of prescribed length, Aequationes Math. 72 (2006), 201–212.DOI
  5. [5]A. Geroldinger and F. Halter-Koch, Non-unique factorizations. Algebraic, Combinatorial and Analytic Theory, Pure Appl. Math., vol. 278, Chapman & Hall/CRC, 2006.
  6. [6]P. Lemke and D. Kleitman, An addition theorem on the integers modulo n, J. Number Theory 31 (1989), 335–345.DOI

Paper details

vlnc:W_uebzrvya
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents