betaFeedback

WorksMathematics

An asymptotic resolution of the Gao–Thangadurai conjecture on the Harborth constant

Abstract

The Harborth constant g(G)\mathsf g(G) of a finite abelian group GG of exponent nn is the least integer kk such that every subset of GG of size at least kk contains nn elements whose sum is zero. Let CnC_n be a cyclic group of order nn. Gao and Thangadurai \cite{gt} in 2004 conjectured that g(Cn⊕Cn)=2n+(−1)n\mathsf g(C_n\oplus C_n)=2n+(-1)^n for all integers n≥3n\ge3. We prove this conjecture for all sufficiently large integers nn.

Introduction

The Erdős–Ginzburg–Ziv theorem [4] states that for every positive integer nn, any sequence of 2n−12n - 1 integers contains nn terms whose sum is divisible by nn. Geometrically, these nn integers are points on the line whose centroid is again an integer.

Kemnitz [17] asked the corresponding question in the plane. How many points in Z2\mathbb{Z}^2 suffice to guarantee that some nn of them have a centroid in Z2\mathbb{Z}^2? The centroid of nn points is a lattice point precisely when both coordinate sums are divisible by nn. Reducing both coordinates modulo nn therefore gives an equivalent additive problem in Cn2=Cn⊕CnC_n^2 = C_n \oplus C_n, where Cn=Z/nZC_n = \mathbb{Z}/n\mathbb{Z} denotes the additive group of integers modulo nn. Each residue class has infinitely many lattice representatives, so distinct lattice points may give repeated terms in Cn2C_n^2. In these terms, Kemnitz asked how many elements of Cn2C_n^2, with repetitions allowed, suffice to guarantee that some nn of them sum to zero.

Taking n−1n - 1 copies of each vertex of the unit square shows that 4n−44n - 4 terms do not suffice. Kemnitz [17] conjectured that the exact value is 4n−34n - 3. This conjecture attracted considerable attention, with contributions on upper bounds and special cases [1, 5, 6, 22, 25, 26]. Alon and Dubiner [1, 2] proved that 6n−56n - 5 terms suffice for every nn. Rónyai [22] reduced the upper bound to 4n−24n - 2 for prime nn, and Gao [6] extended this bound to prime powers. Thangadurai [26] showed that 4n−34n - 3 terms suffice if some element occurs at least ⌊n/2⌋\lfloor n/2 \rfloor times. Gao and Geroldinger [7 Main Lemma 5.6] showed that the conjecture would follow from a lower bound on the number of affine hyperplanes avoiding the origin needed to cover certain sets over prime fields. Reiher [20] finally proved the conjecture for every positive integer nn.

The corresponding problem for sets predates Kemnitz’s conjecture. In 1973 Harborth [15] introduced the constant g(Cnd)g(C_n^d) for subsets of CndC_n^d. In the plane, how many lattice points with pairwise distinct residue classes modulo nn suffice to guarantee that some nn of them have a lattice centroid? In this case the sequence in Cn2C_n^2 is squarefree, so we may regard it as a set. For a finite abelian group GG of exponent nn, Gao and Thangadurai [10 Definition 1] define g(G)g(G) as the least positive integer kk such that every subset of GG of size at least kk contains an nn-element subset with sum zero. Following Marchan, Ordaz, Ramos and Schmid [18], we call g(G)g(G) the Harborth constant of GG.

The one-dimensional case G=CnG = C_n is trivial. In dimension two, for G=Cn2G = C_n^2, Kemnitz [17] proved that g(Cn2)≥2n+(−1)ng(C_n^2) \ge2n + (-1)^n for every n≥3n \ge3. Gao and Thangadurai [10] conjectured that these lower bounds are the precise values of g(Cn2)g(C_n^2).

Conjecture (Gao–Thangadurai, 2004 [10 Conjecture 1]). For every integer n≥3n \ge3,

g(Cn⊕Cn)={2n−1,n odd,2n+1,n even.(1)g(C_n \oplus C_n) = \begin{cases} 2n - 1, & n\ \text{odd},\\ 2n + 1, & n\ \text{even}. \end{cases} \tag*{(1)}

The formula g(Cn⊕Cn)=2n−1g(C_n \oplus C_n)=2n-1 was already known for n=3,5,7n=3,5,7: n=3n=3 goes back to Harborth [15], while Kemnitz [16] in 1982 established n=5,7n=5,7. Gao and Thangadurai [10] proved it for every prime p≥67p \ge67 and also established g(C42)=9g(C_4^2)=9. Gao, Geroldinger and Schmid [9 Theorem 5.1] extended the prime result to p≥47p \ge47 and described the extremal sets of size 2p−22p-2. Guillot, Marchan, Ordaz, Schmid and Zerdoum [14 Proposition 4.1] established the next even case, g(C62)=13g(C_6^2)=13. In a recent preprint, Graham [12] reports that g(Cp2)=2p−1g(C_p^2)=2p-1 for every prime p≥11p \ge11. Together with the known cases n=3,5,7n=3,5,7, this would settle the conjecture for every odd prime.

In this paper we prove the Gao–Thangadurai conjecture for all sufficiently large integers.

Theorem 1.1. For every sufficiently large integer nn,

g(Cn⊕Cn)={2n−1,n odd,2n+1,n even.g(C_n \oplus C_n) = \begin{cases} 2n-1, & n\ \text{odd},\\ 2n+1, & n\ \text{even}. \end{cases}

Notation and preliminary results

Throughout, GG is a finite abelian group with additive notation and identity 00. Let Cn=Z/nZC_n=\mathbb{Z}/n\mathbb{Z} and Cn2=Cn⊕CnC_n^2=C_n\oplus C_n. For an integer d≥1d \ge1, let dG={dg:g∈G}dG=\{dg:g\in G\}. The exponent exp⁡(G)\exp(G) is the least positive dd such that dG={0}dG=\{0\}. For H≤GH\le G, let φH:G→G/H\varphi_H:G\to G/H be the quotient map and let [G:H]=∣G/H∣[G:H]=|G/H| denote the index. If X⊆GX\subseteq G, then X/H=φH(X)X/H=\varphi_H(X).

We follow the sequence notation of Gao and Geroldinger [8 Section 2]. Let F(G)\mathcal{F}(G) denote the collection of all finite unordered sequences of elements of GG, with repetitions allowed. For S=g1⋯gℓ∈F(G)S=g_1\cdots g_\ell\in\mathcal{F}(G), its length is ∣S∣=ℓ|S|=\ell and its sum is σ(S)=g1+⋯+gℓ\sigma(S)=g_1+\cdots+g_\ell. The notation T∣ST\mid S means that TT is obtained by choosing some of the positions of SS. The sums of all subsequences of SS of length kk form the set

Σk(S)={σ(T):T∣S, ∣T∣=k}(0≤k≤∣S∣),\Sigma_k(S)=\{\sigma(T):T\mid S,\ |T|=k\}\qquad(0\le k\le|S|),

with Σ0(S)={0}\Sigma_0(S)=\{0\}. A zero-sum subsequence of length kk exists precisely when 0∈Σk(S)0\in\Sigma_k(S). A sequence is zero-sum free if none of its nonempty subsequences has sum zero. It is squarefree if its terms are pairwise distinct. We identify a finite set with the squarefree sequence of its elements. When we project that sequence into G/HG/H, we retain one term for each original point. Thus two equal terms in the quotient can come from distinct points of GG.

For nonempty sets X,Y⊆GX,Y\subseteq G, let X+Y={x+y:x∈X,y∈Y}X+Y=\{x+y:x\in X,y\in Y\} and X−Y={x−y:x∈X,y∈Y}X-Y=\{x-y:x\in X,y\in Y\}. In an expression such as 3X−2X3X-2X, the summands are chosen independently from XX and may repeat. In Σk(X)\Sigma_k(X), the kk summands are distinct. The stabilizer of XX is the subgroup Stab⁡X={g∈G:X+g=X}\operatorname{Stab}X=\{g\in G:X+g=X\}. We call XX aperiodic if Stab⁡X={0}\operatorname{Stab}X=\{0\}. In CnC_n every subgroup is tCntC_n for a unique divisor t∣nt\mid n. Its index is tt, and its cosets are the residue classes modulo tt.

A primitive row of Cn2C_n^2 is a coset of a cyclic direct summand of order nn. In coordinates adapted to that summand, the parallel rows are the sets Cn×{y}C_n\times\{y\}. We call yy the height and the first coordinate the horizontal coordinate. Translating all points by gg preserves every nn-point sum, since it changes that sum by ng=0ng=0.

A coset progression with rr directions is a set of the form

x0+H+{∑i=1rtigi:ti∈Z, 0≤ti<Wi},x_0+H+\left\{\sum_{i=1}^{r}t_i g_i:t_i\in\mathbb{Z},\ 0\le t_i<W_i\right\},

where H≤GH\le G, x0,g1,…,gr∈Gx_0,g_1,\ldots,g_r\in G, and the WiW_i are positive integers. It is proper if each of its elements has a unique representation x0+h+∑itigix_0+h+\sum_i t_i g_i with h∈Hh\in H and 0≤ti<Wi0\le t_i<W_i. When H={0}H=\{0\}, we call a proper progression a box. Its volume is the number of parameter choices, ∏i=1rWi\prod_{i=1}^{r}W_i.

The following sumset bound will control stabilizer indices. If X=X1+⋯+XkX = X_1 + \cdots+ X_k with nonempty finite sets Xi⊆GX_i \subseteq G and H=Stab⁡XH = \operatorname{Stab} X, Kneser’s theorem [3] gives

∣X/H∣≥1+∑i=1k(∣(Xi+H)/H∣−1).|X/H| \ge1 + \sum_{i=1}^{k} (|(X_i + H)/H| - 1).

We also need zero-sum subsequences of prescribed length in quotients. By the Erdős–Ginzburg–Ziv theorem (EGZ), 2b−12b - 1 terms in CbC_b suffice for a zero sum of length bb [4]. By Reiher, 4b−34b - 3 terms suffice in Cb2C_b^2 [20]. A quotient G1G_1 of Cn2C_n^2 with exponent bb embeds in Cb2C_b^2 by the invariant factor theorem. Consequently, for every positive multiple uu of bb,

∣S∣≥u+3(b−1),S∈F(G1)⟹0∈Σu(S).(2)|S| \ge u + 3(b - 1), \qquad S \in\mathcal{F}(G_1) \quad\Longrightarrow\quad0 \in\Sigma_u(S). \tag*{(2)}

Indeed, successively remove u/bu/b disjoint zero-sum subsequences of length bb. Before the last choice at least b+3(b−1)=4b−3b + 3(b - 1) = 4b - 3 terms remain, so Reiher’s theorem applies at every step. Their union has length uu and sum zero.

For restricted sumsets in a cyclic group, we use the following bound. If YY is a set of ss elements of a cyclic group, then ∣Σj(Y)∣≥s|\Sigma_j(Y)| \ge s for 1≤j<s1 \le j < s [11 Theorem 1.1]. For j=1j = 1 the sumset is YY, and for j=s−1j = s - 1 it is σ(Y)−Y\sigma(Y) - Y. The exception in the general abelian-group theorem requires a coset of an elementary 2-group of size at least four, which cannot occur in a cyclic group.

The remaining two results describe long sequences in cyclic groups. Savchev and Chen proved that a zero-sum free sequence in CbC_b of length >b/2> b/2 has, with respect to a suitable generator, positive representatives whose sum is <b< b [23]. They also proved that if b/2<k<bb/2 < k < b and a sequence of length b−1+kb - 1 + k in CbC_b has no zero sum of length bb, two values have combined multiplicity at least 2k2k [24 Corollary 7].

Proof of the main theorem

By Kemnitz’s lower bound g(Cn2)≥2n+(−1)ng(C_n^2) \ge2n + (-1)^n, it suffices to prove 2n+(−1)n2n + (-1)^n is also the upper bound for all sufficiently large nn. Throughout this section, a counterexample is a set A⊆G=Cn2A \subseteq G = C_n^2 with ∣A∣=2n+(−1)n|A| = 2n + (-1)^n and 0∉Σn(A)0 \notin\Sigma_n(A).

We begin by counting representations of a fixed sum by tuples of points of AA. The next lemma bounds their total number when no individual point occurs too often among the representations of any one sum.

Lemma 3.1. Let X⊆AX \subseteq A, ∣X∣≤n|X| \le n. Consider a family of ordered hh-tuples of distinct elements of XX, where h≥2h \ge2. Suppose that at most JJ tuples with a given sum contain a given element of XX, with J>0J > 0. The family has fewer than 32hn2J32hn^2J members.

Proof. We show that failure of the bound produces an nn-term zero-sum subsequence of AA. Let r(z)r(z) count the tuples with sum zz, choose z∗z_* with maximal r(z∗)r(z_*), and set ℓ=⌊r(z∗)/(8hJ)⌋\ell= \lfloor r(z_*)/(8hJ) \rfloor. For 1≤j≤ℓ1 \le j \le\ell let Yj={z:r(z)≥8hJj}Y_j = \{z : r(z) \ge8hJj\}. If the asserted bound fails, then

∑j∣Yj∣=∑z∈G⌊r(z)8hJ⌋≥3n2.\sum_j |Y_j| = \sum_{z \in G} \left\lfloor\frac{r(z)}{8hJ} \right\rfloor\ge3n^2.

Also hr(z∗)≤∣X∣Jhr(z_*) \le|X|J by incidence counting, so ℓ≤n/(8h2)\ell\le n/(8h^2). For U=∑jYjU = \sum_j Y_j, let H=Stab⁡UH = \operatorname{Stab} U, w=[G:H]w = [G:H], and e=exp⁡(G/H)e = \exp(G/H). Kneser gives

w≥1−ℓ+∑j∣(Yj+H)/H∣≥1−ℓ+3w.w \ge1 - \ell+ \sum_j |(Y_j + H)/H| \ge1 - \ell+ 3w.

Hence e≤w≤(ℓ−1)/2e \le w \le(\ell- 1)/2. The set UU contains ℓz∗+H\ell z_* + H. Round ℓ\ell up to a multiple ℓ′\ell' of ee, so ℓ′<3ℓ/2\ell' < 3\ell/2. Since e∣ℓ′e \mid\ell', we have ℓ′z∗∈H\ell' z_* \in H. Adjoining ℓ′−ℓ\ell' - \ell copies of the singleton {z∗}\{z_*\} therefore produces a sumset containing $H. Every such sum can be realized with hℓ′h\ell' distinct points of XX. Choose a tuple for each prescribed layer value in increasing order of jj. Earlier tuples use at most h(j−1)h(j-1) points, and hence exclude fewer than hjJhjJ representations at layer jj. At appended positions they exclude fewer than hℓ′J<8hℓJh\ell'J<8h\ell J, and the value z∗z_* has at least 8hℓJ8h\ell J representations. Since hℓ′<3n/(16h)<nh\ell'<3n/(16h)<n and ee divides both nn and ℓ′\ell', the integer u=n−hℓ′u=n-h\ell' is positive and divisible by ee. Outside XX are at least n−1n-1 points. This is at least u+3(e−1)u+3(e-1), since hℓ′≥2ℓh\ell'\ge2\ell and e≤(ℓ−1)/2e\le(\ell-1)/2. By (1), choose uu of them with sum in HH, and cancel that sum with the hℓ′h\ell' points inside XX. □

Lemma 3.2. Let E(X)=∣{(x1,x2,x3,x4)∈X4:x1+x2=x3+x4}∣E(X)=|\{(x_1,x_2,x_3,x_4)\in X^4:x_1+x_2=x_3+x_4\}|. For X⊆AX\subseteq A of size 24≤m≤n24\le m\le n, one has E(X)>m5/(4608n2)E(X)>m^5/(4608n^2). Also, if B1,B2⊆AB_1,B_2\subseteq A are disjoint of sizes b,c≥2b,c\ge2, with b+c≤nb+c\le n, then

max⁡z∣B2∩(z−B1)∣>b2c21024n2max⁡(b,c).\max_z |B_2\cap(z-B_1)|>\frac{b^2c^2}{1024n^2\max(b,c)}.

Proof. We first prove the energy bound. Let r2(s)r_2(s) count ordered pairs from X2X^2 with sum ss, and set t=m3/(576n2)t=m^3/(576n^2). If the pairs with r2(s)>tr_2(s)>t account for at most m2/8m^2/8 pairs, at least m3−3m2−3m3/8≥m3/2m^3-3m^2-3m^3/8\ge m^3/2 ordered triples have distinct entries and all three pair sums of multiplicity at most tt. Fixing a sum and one element leaves at most 3t3t such triples. Lemma 3.1 gives strictly fewer than 288n2t=m3/2288n^2t=m^3/2. Thus the pairs with r2(s)>tr_2(s)>t contribute more than tm2/8tm^2/8 to E(X)=∑sr2(s)2E(X)=\sum_s r_2(s)^2.

To bound the intersection, consider tuples (b1,b2,c1,c2)(b_1,b_2,c_1,c_2) with b1,b2∈B1b_1,b_2\in B_1 and c1,c2∈B2c_1,c_2\in B_2, and unequal entries within each pair. Since B1∩B2=∅B_1\cap B_2=\varnothing, all four entries are distinct. There are at least b2c2/4b^2c^2/4 such tuples. Given a sum and an element of B1B_1, choose its position and c1c_1. The last B1+B2B_1+B_2 pair has at most max⁡z∣B2∩(z−B1)∣\max_z|B_2\cap(z-B_1)| choices. The same bound holds after exchanging B1B_1 and B2B_2. Apply Lemma 3.1 with X=B1∪B2X=B_1\cup B_2, h=4h=4 and J=2max⁡(b,c)max⁡z∣B2∩(z−B1)∣J=2\max(b,c)\max_z|B_2\cap(z-B_1)|; the hypothesis ∣X∣≤n|X|\le n follows from b+c≤nb+c\le n. □

Lemma 3.3. Let K=2240K=2^{240}, s=K4s=K^4 and b0=2−K6b_0=2^{-K^6}. If n≥100n\ge100, a counterexample contains mm points in a box

x0+{∑i=1rtigi:0≤ti<Wi}x_0+\left\{\sum_{i=1}^{r}t_i g_i:0\le t_i<W_i\right\}

with unique representations, where r≤sr\le s, m≤n/2m\le n/2, m≥b0nm\ge b_0n and m≥V/K5m\ge V/K^5, with V=∏iWiV=\prod_i W_i.

Proof. We first find a subset with small doubling. Take X⊆AX\subseteq A of size ⌊n/2⌋\lfloor n/2\rfloor. Since ∣X∣≥n/3|X|\ge n/3, Lemma 3.2 gives E(X)≥∣X∣3/K0E(X)\ge|X|^3/K_0, where K0=41472K_0=41472. The energy form of the Balog–Szemerédi–Gowers theorem, in the explicit version of Reiher and Schoen [21 Theorem 1.2], with its parameter ε=1/4\varepsilon=1/4, gives B⊆XB\subseteq X satisfying

∣B∣≥3∣X∣1024≥n1024,∣B−B∣≤251K04∣B∣.|B|\ge\frac{3|X|}{1024}\ge\frac{n}{1024},\qquad|B-B|\le2^{51}K_0^4|B|.

The Plünnecke–Ruzsa inequalities [19], applied with base set −B-B and summand BB, give ∣B+B∣≤(251K04)2∣B∣≤K∣B∣|B+B|\le(2^{51}K_0^4)^2|B|\le K|B|. Hence ∣3B−2B∣≤K5∣B∣|3B-2B|\le K^5|B|.

To obtain the required box, we apply the result of Green and Ruzsa [13 Section 5, (5.1)], which gives a proper coset progression P⊆2B−2BP\subseteq2B-2B of rank at most 29K3log⁡2(K+2)2^9K^3\log_2(K+2) and size at least exp⁡(−214K3log⁡22(K+2))∣B∣\exp(-2^{14}K^3\log_2^2(K+2))|B|. Averaging the identity

∑z∈B−P∣B∩(z+P)∣=∣B∣∣P∣\sum_{z\in B-P}|B\cap(z+P)|=|B||P|

over B−P⊂3B−2BB-P\subset3B-2B gives a translate containing at least K−5∣P∣K^{-5}|P| points of BB. This number is at least b0nb_0n, since

214K3log⁡22(K+2)+log⁡(1024K5)<K6log⁡2.2^{14}K^3\log_2^2(K+2)+\log(1024K^5)<K^6\log2.

The subgroup part of PP has at most two invariant factors. Use one box coordinate for each such cyclic factor and translate the origin of each parameter interval to zero. Properness gives unique representations, so V=∣P∣V = |P|, each Wi≤nW_i \le n, and r≤2+29K3log⁡2(K+2)≤sr \le2 + 2^9 K^3 \log_2(K + 2) \le s. Take the points of BB in this translate as the mm points of the lemma. □

The box in Lemma 3.3 may have only one long direction. To handle this possibility we bound the number of points of a counterexample on a primitive row. We start with a row containing more than four fifths of its nn points.

Lemma 3.4. If n≥100n \ge100, every primitive row contains at most 4n/54n/5 points of a counterexample.

Proof. We first show that a row of this size attains every horizontal sum for every length between 2 and two less than its size. Suppose a row contains more than 4n/54n/5 points. Choose a largest row in the same direction and translate it to height zero. Let X⊂CnX \subset C_n be its set of first coordinates and c=∣X∣>4n/5c = |X| > 4n/5. We claim that Σk(X)=Cn\Sigma_k(X) = C_n whenever 2≤k≤c−22 \le k \le c - 2. By complementation take k≤c/2k \le c/2. For even kk choose two points summing to the target. For odd kk, first fix one point, then choose two others for the adjusted target. This works as ∣Y∩(t−Y)∣≥2∣Y∣−n>2|Y \cap(t - Y)| \ge2|Y| - n > 2 after removing at most one point, and at most two solutions have equal partners. There are initially at least (2c−n−2)/2(2c - n - 2)/2 disjoint opposite pairs in XX. Even after losing three pairs there are at least c/4c/4 left, since 3c≥2n+163c \ge2n + 16. They supply the remaining points in pairs.

We next exclude c=nc = n. If nn is odd, the full row sums to zero. If c=nc = n and nn is even, take n+1n + 1 outside heights. These heights have a nonempty zero-sum subsequence of length less than nn. Otherwise every nn-subset would itself have sum zero by the partial-sum argument in CnC_n. Comparing two such subsets differing in one entry makes all n+1n + 1 heights equal, exceeding row capacity. The full row also covers every target at sizes 1,n−11, n - 1, so one can cancel its horizontal sum with the required number of row points.

For c<nc < n, we use the outside heights to complete a zero-sum selection on the chosen row. Let r=n−c≥1r = n - c \ge1 and take n+r−1n + r - 1 outside points, available in either parity. A zero-sum subsequence of their heights of length in [r+2,n−2][r + 2, n - 2] would leave between 2 and c−2c - 2 places on the chosen row, where any required horizontal sum is attainable. Suppose there is no such subsequence. Some generator gg occurs at least n−3n - 3 times among these heights. To see this, if there is a minimal nonempty zero-sum subsequence of length n−1n - 1 or nn, delete one term and apply the zero-sum free sequence theorem of Savchev–Chen. Its remaining positive representatives have sum at most n−1n - 1. Restoring the deleted term with its representative in [1,n−1][1, n - 1] gives a positive multiple of nn strictly below 2n2n, hence total nn and at least n−2n - 2 ones. Otherwise remove disjoint minimal nonempty zero-sum subsequences until none remain. Each has length at most r+1r + 1. Their total cannot first exceed r+1r + 1, since it would be at most 2r+2≤n−22r + 2 \le n - 2. At least n−2n - 2 zero-sum free terms remain. Their positive representatives have sum at most n−1n - 1, so at least n−3n - 3 are ones.

We now bound the multiplicities of the remaining heights. Any agag with $3 \le a \le n - r - 1$ would give a forbidden zero-sum subsequence with n−an - a copies of gg. Two copies of $2g$ would do the same with n−4n - 4 copies of gg. The other possibilities are −jg-jg, 1≤j≤r1 \le j \le r. Their weights j+1j + 1 total at most r+1r + 1, since a first prefix exceeding r+1r + 1 could be completed with copies of gg to a zero-sum subsequence of length between r+2r + 2 and 2r+22r + 2. Such a prefix contains at least two negative-height terms and needs at most 2r<n−32r < n - 3 copies of gg, which are available. The height gg occurs at most c=n−rc = n - r times, since we started with a largest row in this direction. Thus for r≥2r \ge2 the outside count is at most n−r+1+⌊(r+1)/2⌋<n+r−1n - r + 1 + \lfloor(r + 1)/2\rfloor< n + r - 1. For r=1r = 1, if −g-g occurs take one point of each height gg, −g-g and n−2n - 2 from the center. The rr-row choice and center choice give respectively at least n−3n - 3 and n−1n - 1 horizontal sums, so their sum fills CnC_n. Here we use the fact that Y+Z=CnY + Z = C_n whenever Y,Z⊂CnY, Z \subset C_n and ∣Y∣+∣Z∣>n|Y| + |Z| > n. If −g-g is absent, the nn outside heights are n−1n - 1 copies of gg and one 2g2g. Take one point of height 2g2g, n−2n - 2 of height gg and one from the center. The latter two choices each give n−1n - 1 sums.

Lemma 3.5. Let d∣nd \mid n and n≥200d5n \ge200d^{5}. After deleting at most n/100n/100 points of a counterexample, one can select nn remaining points with height sum zero in CnC_n and first coordinate sum zero modulo dd.

Proof. We first prove the assertion for d=1d=1. Let SS be the sequence of remaining heights. If ∣S∣≥2n−1|S| \ge2n-1, cyclic EGZ gives the required selection. Otherwise, for k=∣S∣−n+1k=|S|-n+1, we have n/2<n−n/100≤k<nn/2<n-n/100\le k<n and ∣S∣=n−1+k|S|=n-1+k. If the selection fails, Savchev–Chen gives two heights with combined multiplicity at least 2k≥2(n−n/100)>8n/52k\ge2(n-n/100)>8n/5, contrary to Lemma 3.4.

For d≥2d\ge2, we seek m=n/dm=n/d disjoint blocks whose union gives the required selection. Let ℓ≤n/100\ell\le n/100 be the number deleted. A block consists of dd points whose two coordinate sums vanish modulo dd. Its value in CmC_m is its height sum divided by dd. Try to choose k0=⌈(ℓ+1)/d⌉+5k_0=\lceil(\ell+1)/d\rceil+5 disjoint triples of blocks with three different values in each triple.

If k0k_0 such triples exist, we obtain the selection from a maximal collection of disjoint blocks containing them. Reiher leaves at most 4d−44d-4 points, so the number bb of blocks is at least 2m−k02m-k_0. We need mm blocks of value sum zero. EGZ suffices if b≥2m−1b\ge2m-1. Otherwise m/2<b−m+1<mm/2<b-m+1<m, since k0≤m/100+7k_0\le m/100+7 and m=n/d≥200d4m=n/d\ge200d^4. If there were no such choice, Savchev–Chen would force all but 2m−2−b≤k0−22m-2-b\le k_0-2 blocks on two values, contradicting the triples.

If fewer than k0k_0 triples can be chosen, we concentrate the remaining heights in at most two residue classes. Discard a maximal collection of such triples. Among the remaining points take a maximal collection of disjoint blocks with pairwise distinct values and discard them as well. There are at most two such blocks, so the total number discarded is less than 3dk0≤3ℓ+3+18d3dk_0\le3\ell+3+18d. Every further block has value in the same set UU of at most two values. All but at most 8d28d^2 remaining heights belong to UU modulo mm. Indeed on the real circle of circumference nn mark every lift of UU. Each of at most 2d2d open arcs contains fewer than 4d−34d-3 points counted with multiplicity. Otherwise Reiher supplies a block in that arc. Its average height, computed in an open interval lifting the arc, is an integer strictly between the endpoints and represents its value modulo mm, which is impossible. If UU is empty there are at most 4d−44d-4 remaining points by Reiher’s theorem, again within the stated bound.

We next reduce the remaining points to at most two families with sufficiently many copies of each label. For each surviving height residue aia_i modulo mm, use a fixed integer representative and express the height as y=ai+mz2y=a_i+m z_2. Label the points in this family by z=(x mod d,z2)∈G1=Cd=Cd2z=(x\bmod d,z_2)\in G_1=C_d=C_d^2. Discard all label classes with fewer than d3d^3 elements. There are at most 2d22d^2 classes, so this discards fewer than 2d52d^5 points. At least 2n−4ℓ−5d52n-4\ell-5d^5 points survive, since 4+18d+8d2+2d5≤5d54+18d+8d^2+2d^5\le5d^5 for d≥2d\ge2. If one family has at least n+d3n+d^3 points, group equal labels into dd-tuples. Fewer than d3d^3 points are left over. Any mm of the groups have both required sums, since the nn heights are ai+mz2a_i+m z_2 with total z2z_2 divisible by dd. Otherwise there are two families, each of size greater than 0.9n0.9n. Indeed 2n−4ℓ−5d5−(n+d3)>0.9n2n-4\ell-5d^5-(n+d^3)>0.9n.

We show that each family attains every label sum in the appropriate coset. Fix a label hih_i in family ii, and let Hi≤G1H_i\le G_1 be generated by all label differences there. For every n/3≤k≤2n/3n/3\le k\le2n/3 the kk-sums of the labels fill khi+Hikh_i+H_i. For each other occurring label hh reserve ord⁡(h−hi)−1\operatorname{ord}(h-h_i)-1 disjoint pairs with labels hi,hh_i,h. Fewer than d3d^3 pairs suffice, and all required copies exist. Selecting one from each pair fills a coset of HiH_i. If RR is the number of reserved pairs, then R<d3≤n/800R<d^3\le n/800. Since the family has more than 0.9n0.9n points and n/3≤k≤2n/3n/3\le k\le2n/3, there are enough unused points to add a fixed selection of k−Rk-R points. All kk-term sums belong to khi+Hikh_i+H_i, so the coset attained is precisely khi+Hikh_i+H_i.

We distinguish two cases according to the order of the difference between the families. Let H=H0+H1H=H_0+H_1, and let tt be the order of g=(0,a0−a1)+m(h0−h1)g=(0,a_0-a_1)+m(h_0-h_1) in G1/HG_1/H. If t<dt<d, set u=t⌊d/(2t)⌋u=t\lfloor d/(2t)\rfloor. Since t∣dt\mid d, d/3≤u≤d/2d/3\le u\le d/2. Choose umum points in the first family and (d−u)m(d-u)m in the second. Their possible total labels include (0,−u(a0−a1))(0,-u(a_0-a_1)) because ug=0(modH)ug=0\pmod H. Then their horizontal sum is zero modulo dd and their height sum is m(u(a0−a1)−u(a0−a1))=0(modn)m(u(a_0-a_1)-u(a_0-a_1))=0\pmod n.

For t=dt=d, we obtain a primitive row contradicting Lemma 3.4. There is a homomorphism G1/H→CdG_1/H \to C_d taking gg to a unit. For each prime power exactly dividing dd, project onto a cyclic primary factor in which gg has that full prime-power order, then combine by the Chinese remainder theorem. The pullback to G1G_1 has the form cz1+ez2cz_1+ez_2. Choose e′≡e(modd)e' \equiv e \pmod d and e′≡1e' \equiv1 modulo each prime dividing mm but not dd. The form cmx+e′ycmx+e'y is primitive modulo nn. At a prime common to m,dm,d, its second coefficient is a unit since the character takes gg to a unit and reduces there to e(a0−a1)e(a_0-a_1). At a prime dividing dd alone, c,ec,e cannot both vanish modulo that prime. At every remaining prime use the choice of e′e'. On family ii the form equals e′ai+m(cz1+ez2)e'a_i+m(cz_1+ez_2), constant because the character kills HiH_i. Its fiber is a primitive row with more than 0.9n0.9n points, contrary to Lemma 3.4. □

Lemma 3.6. Let r0≥1r_0 \ge1 be an integer and c0=236r03c_0=2^{36}r_0^3. If n≥200(c0!)5n \ge200(c_0!)^5, a counterexample cannot have all but n/100n/100 of its points in r0r_0 parallel primitive rows.

Proof. We first obtain an nn-point selection with the required height sum and a controlled horizontal sum. Let m0=65536r0m_0=65536r_0, W=16r0m0W=16r_0m_0, c0=m0Wc_0=m_0W, and set

a=gcd⁡(n,lcm⁡(1,…,c0)).a=\gcd(n,\operatorname{lcm}(1,\ldots,c_0)).

Since a≤c0!a \le c_0!, our hypothesis gives n≥200a5n \ge200a^5, as required by Lemma 3.5. In every designated row of size cyc_y delete ⌊cy/256⌋\lfloor c_y/256\rfloor points, less than n/100n/100 in total. Make the projected selection of that lemma at d=ad=a. One designated row has k≥(n−n/100)/r0≥n/(2r0)k \ge(n-n/100)/r_0 \ge n/(2r_0) selected points. Its original size cc satisfies c−k≥⌈c/256⌉≥c/512c-k \ge\lceil c/256\rceil\ge c/512. Fix the choices on every other row. If w∈Cnw \in C_n is the needed horizontal sum, the projected selection gives a kk-subset FF on this row with sum ww mod aa. We may now choose from all cc original points on this row.

We next preserve the horizontal sum modulo aa while retaining enough independent choices on this row. Represent its cc original horizontal coordinates in [0,n−1][0,n-1]. Partition this interval into intervals of WW consecutive integers (the last may be shorter). Within each form disjoint packets of m0m_0 points until fewer than m0m_0 remain. At most (n/W+1)(m0−1)≤n/(8r0)(n/W+1)(m_0-1) \le n/(8r_0) points are left over, since n≥16r0m0n \ge16r_0m_0. As c≥n/(2r0)c \ge n/(2r_0), we can retain k0=⌊n/(4096r0m0)⌋k_0=\lfloor n/(4096r_0m_0)\rfloor packets. There exists a kk-set EE on the row taking exactly half of every retained packet, since k0m0/2≤min⁡(k,c−k)k_0m_0/2 \le\min(k,c-k). Pair E∖FE\setminus F bijectively with F∖EF\setminus E. Their oriented differences sum to w−∑Ew-\sum E mod aa. Repeatedly discard nonempty zero-sums of differences modulo aa until fewer than aa remain (the partial-sum principle in CaC_a). Perform these remaining exchanges. This gives a kk-set of the required sum modulo aa and disturbs at most 2a2a of the retained packets.

To attain the exact horizontal sum, fix everything except the choices of m0/2m_0/2 in each undisturbed packet. There are at least k0−2a≥n/(8192r0m0)k_0-2a \ge n/(8192r_0m_0) such packets. Indeed n≥200(c0!)5≥8192r0m0(2a+1)n \ge200(c_0!)^5 \ge8192r_0m_0(2a+1). Let tCntC_n be the stabilizer of the resulting horizontal sumset. If t>c0t>c_0, each packet gives at least 1+m02/41+m_0^2/4 sums modulo tt. Indeed, order its points increasingly and move the selected m0/2m_0/2 indices from the first half to the last by individual unit steps, always keeping them distinct. The integer sums strictly increase over m02/4m_0^2/4 steps, and their diameter is less than m0Wm_0W. In CtC_t the total sumset is aperiodic and proper. Kneser would give

t−2≥n8192r0m0m024≥2n.t-2 \ge\frac{n}{8192r_0m_0}\frac{m_0^2}{4} \ge2n.

which contradicts t∣nt\mid n. Thus t≤c0t\le c_0, so t∣at\mid a. The selection obtained from EE has sum congruent to ww modulo aa. Its difference from ww lies in the stabilizer. Consequently ww itself is attained. The fixed height sum then gives an nn-point zero-sum subset. □

Lemma 3.7. For 0<a≤10<a\le1, define

b=min⁡(a/4,1/400),ra=1+⌈3072/b3⌉,ca=236ra3,F(a)=200(ca!)5.b=\min(a/4,1/400),\qquad r_a=1+\lceil3072/b^3\rceil,\qquad c_a=2^{36}r_a^3,\qquad F(a)=200(c_a!)^5.

If n≥F(a)n\ge F(a), every primitive row of a counterexample contains fewer than anan points.

Proof. We show that such a row would concentrate almost all points on boundedly many parallel rows. Suppose a row contains at least anan points. Fix B1B_1 of size ⌊an/2⌋\lfloor an/2\rfloor on that row and mark its row. While at least n/100n/100 points are on unmarked rows take ⌊n/200⌋\lfloor n/200\rfloor such points as B2B_2. Their sizes add to at most nn, and n≥F(a)n \ge F(a) ensures n>max⁡(400,4/a)n > \max(400,4/a). Each set has size at least bnbn. By Lemma 3.2, some translate of −B1-B_1 contains more than b3n/1024b^3n/1024 members of B2B_2. Mark its row. These are new points each time, so 1+⌈3072/b3⌉1+\lceil3072/b^3\rceil rows suffice to leave fewer than n/100n/100 points. Apply Lemma 3.6. □

We now return to the box of Lemma 3.3. The bound on points in a primitive row will ensure that its long directions generate a subgroup with a sufficiently small quotient exponent. Retain the constants KK, ss, b0b_0 of that lemma and set

D=16sK5,ℓ0=D!,J=512s2ℓ0K10,bi+1=bi2/J(0≤i<s).(3)D=16sK^5,\qquad\ell_0=D!,\qquad J=512s^2\ell_0K^{10},\qquad b_{i+1}=b_i^2/J\quad(0\le i<s). \tag*{(3)}

The integer ℓ0\ell_0 is divisible by every possible stabilizer index up to DD. The numbers bib_i account for the points lost by fixing short coordinates of the box.

Lemma 3.8. Suppose n>2s/bsn>2s/b_s. Some slice of the box in Lemma 3.3 has r≥1r\ge1 remaining coordinates and contains mm of the chosen points, where

bsn≤m≤n/2,m≥V/K5,Wi≥Jn/m(1≤i≤r).b_sn\le m\le n/2,\qquad m\ge V/K^5,\qquad W_i\ge Jn/m\quad(1\le i\le r).

Here VV is the volume of the slice.

Proof. We successively fix short coordinates while preserving the density and a lower bound for the number of points. After ii coordinates have been fixed, suppose the current box contains at least binb_i n points and has density at least K−5K^{-5}. If a side has length W<J/biW<J/b_i, fix the value of that coordinate which retains the most points. The volume is divided by WW, and the new slice contains at least a 1/W1/W fraction of the points. Its density is therefore still at least K−5K^{-5}, and its population exceeds bi2n/J=bi+1nb_i^2n/J=b_{i+1}n. Repeat until all remaining sides have length at least J/biJ/b_i. Fixing every coordinate would leave one site containing at least bsn>1b_sn>1 points, which is impossible. At the stopping step, m≥bin≥bsnm\ge b_in\ge b_sn, and every remaining side has length at least J/bi≥Jn/mJ/b_i\ge Jn/m. □

We next bound the exponent of the quotient by the subgroup generated by the remaining directions. Translate the surviving box so that its base point is zero. We translate all of AA, since the sum of nn points is translation invariant. Let K1=⟨g1,…,gr⟩K_1=\langle g_1,\ldots,g_r\rangle, v=exp⁡(G/K1)v=\exp(G/K_1), and set

a0=bs248ℓ0.(4)a_0=\frac{b_s^2}{48\ell_0}. \tag*{(4)}

If n≥F(a0)n\ge F(a_0), Lemma 3.7 gives

v<m48ℓ0.(5)v<\frac{m}{48\ell_0}. \tag*{(5)}

Indeed, Smith normal form for the inverse image of K1K_1 in Z2\mathbb{Z}^2 gives a basis in which K1=uCn⊕vCnK_1=uC_n\oplus vC_n with u∣v∣nu\mid v\mid n. The mm points lie on at most n/vn/v parallel primitive rows. One row contains at least mv/nmv/n points. If v≥m/(48ℓ0)v\ge m/(48\ell_0), this is at least m2/(48ℓ0n)≥bs2n/(48ℓ0)=a0nm^2/(48\ell_0 n)\ge b_s^2n/(48\ell_0)=a_0n, a contradiction. In particular r≥2r\ge2, since for cyclic K1K_1 the invariant factors of K1K_1 have orders n/v∣n/un/v\mid n/u, forcing v=nv=n.

Lemma 3.9. Assume that the slice in Lemma 3.8 has r≥2r\ge2 remaining coordinates. Partition its mm points into disjoint sets A1,…,ArA_1,\ldots,A_r whose sizes differ by at most one. In AiA_i, consider the lines in the box obtained by varying only coordinate ii, and let W=WiW=W_i. Keep the lines containing at least W/(4rK5)W/(4rK^5) points of AiA_i. On each retained line of population cc, prescribe an integer k∈[c/3,c/2]k\in[c/3,c/2]. If XX is the set of ii-coordinates on that line, the sum of the sets Σk(X)\Sigma_k(X) over all retained lines has stabilizer of index at most DD in CnC_n.

Proof. We first estimate the total number of points on the retained lines. There are at most V/WV/W lines and ∣Ai∣≥m/(2r)|A_i| \ge m/(2r), since m>2sm > 2s. Discarding the shorter lines costs at most V/(4rK5)≤m/(4r)V/(4rK^5) \le m/(4r) points. The retained lines thus contain mi≥m/(4r)m_i \ge m/(4r) points. Because there is another side of length at least Jn/mJn/m, we also have

mi/W≥V/(4rK5W)≥Jn/(4rK5m)≥48rK5.(6)m_i/W \ge V/(4rK^5W) \ge Jn/(4rK^5m) \ge48rK^5. \tag*{(6)}

To bound the stabilizer index, let X⊆[0,W−1]X \subseteq[0,W-1] be the set of the distinct coordinate parameters on a retained line and consider its kk-sumset Σk(X)\Sigma_k(X). Let t∣nt \mid n be the stabilizer index of their total sumset. If t>1t>1, Kneser in CtC_t gives

∑X(∣Σk(X) mod t∣−1)≤t−2.\sum_X (|\Sigma_k(X)\bmod t|-1)\le t-2.

We exclude t>Dt>D in the two cases t≤Wt\le W and t>Wt>W. Suppose first that D<t≤WD<t\le W. A line of population cc occupies at least b≥c/⌈W/t⌉≥ct/(2W)b\ge c/\lceil W/t\rceil\ge ct/(2W) residues. Its sums of kk points occupy at least bb residues. For b≥2b\ge2, set aside one representative per residue and choose jj with 1≤j<b1\le j<b and 0≤k−j≤c−b0\le k-j\le c-b. Such jj exists since 0<k<c0<k<c. Fix k−jk-j of the other points and vary jj of the representatives, using the restricted sum bound in CtC_t. For b=1b=1 the claim is immediate. The total growth is therefore at least

mit2W≥VW≥mit4W≥t.\frac{m_i t}{2W}\ge\frac{V}{W}\ge\frac{m_i t}{4W}\ge t.

The middle inequality uses mi≥V/(4rK5)m_i\ge V/(4rK^5) and t>D≥16rK5t>D\ge16rK^5. The last follows from (5), contradicting the upper bound t−2t-2.

Suppose next that t>Wt>W, and let h=⌊(t−1)/W⌋≥1h=\lfloor(t-1)/W\rfloor\ge1. On each line fix k−jk-j points, where j=min⁡(k,h)j=\min(k,h). With b=c−kb=c-k, the remaining j+bj+b points give at least 1+jb1+jb distinct jj-sums modulo tt. The increasing-index chain used in Lemma 3.6 has jbjb steps and diameter at most j(W−1)<tj(W-1)<t. Let u0=∑Xk(c−k)u_0=\sum_X k(c-k) and k∗=max⁡Xkk_*=\max_X k. Since k(c−k)≥c2/6k(c-k)\ge c^2/6,

u0≥Wmi24rK5.u_0\ge\frac{Wm_i}{24rK^5}.

The right side is at least nn, since mi≥m/(4r)m_i\ge m/(4r) and W≥Jn/mW\ge Jn/m. It is also at least 2k∗W2k_*W, by (5) and k∗≤Wk_*\le W. If h≥k∗h\ge k_*, the sum of the jbjb's is u0≥tu_0\ge t. Otherwise it is at least hu0/k∗≥2hW≥t−1hu_0/k_*\ge2hW\ge t-1, since t−1<(h+1)Wt-1<(h+1)W. Both alternatives contradict Kneser. Hence t≤Dt\le D. □

Proof of Theorem 1.1. We first choose nn large enough to apply the preceding lemmas. The constants ss, bsb_s and a0a_0 in (2) and (3) are independent of nn, with bs,a0>0b_s,a_0>0. Thus for all sufficiently large nn we have n>2s/bsn>2s/b_s and n≥F(a0)n\ge F(a_0).

We choose a total number of points divisible by vℓ0v\ell_0. Suppose there were a counterexample for such an nn. Take the box of Lemma 3.8 and the disjoint point sets of the preceding lemma. On each retained line of population cc, choose the number kk of selected points to be a multiple of ℓ0\ell_0 in [c/3,c/2][c/3,c/2]. This is possible because c≥W/(4rK5)≥Jn/(4rK5m)≥24ℓ0c\ge W/(4rK^5)\ge Jn/(4rK^5m)\ge24\ell_0. The largest and smallest allowed choices on that line differ by at least c/6−2ℓ0≥c/12c/6-2\ell_0\ge c/12. Adding the corresponding arithmetic progressions over all lines gives every multiple of ℓ0\ell_0 between the extreme totals. At least m/4m/4 points lie on retained lines, so the interval of totals has width at least m/48m/48, lower endpoint at least m/12m/12, and upper endpoint at most m/2m/2. By (4), vℓ0<m/48v\ell_0<m/48. The interval therefore contains a multiple ℓ\ell of vℓ0v\ell_0, and ℓ≥3vℓ0\ell\ge3v\ell_0. Fix choices of kk giving that total.

We next show that the choices in AiA_i attain all multiples of the stabilizer index in coordinate ii. Let tit_i be the stabilizer index given by Lemma 3.9. Since ti≤Dt_i\le D, it divides ℓ0=D!\ell_0=D!. On every retained line we can choose kk points whose ii-coordinate sum vanishes modulo tit_i. Indeed, ti∣kt_i\mid k and c≥k+ti−1c\ge k+t_i-1, so this follows by successive applications of the cyclic Erdős–Ginzburg–Ziv theorem. We remove k/tik/t_i disjoint zero-sum subsequences of length tit_i, with at least 2ti−12t_i-1 terms available before the last choice. Thus the sumset of the varying ii-coordinates meets tiCnt_iC_n. Its stabilizer is tiCnt_iC_n, so it contains all of tiCnt_iC_n. The other coordinates on each line are constant. Their contributions are multiples of ℓ0\ell_0 because ℓ0∣k\ell_0 \mid k.

We combine these coordinate sums to cover a subgroup of GG. The AiA_i are disjoint, so these choices can be made independently. In coordinate ii, the fixed contributions from the other sets belong to ℓ0Cn⊆tiCn\ell_0C_n \subseteq t_iC_n. Mapping the coordinate sums back into GG, we conclude that every element of

H′=∑i=1rti⟨gi⟩H'=\sum_{i=1}^{r}t_i\langle g_i\rangle

is the sum of exactly ℓ\ell of the mm points.

It remains to complete the selection using points outside the chosen set of mm points. Since νG⊆K1\nu_G \subseteq K_1 and ℓ0K1⊆H′\ell_0K_1 \subseteq H', it follows that e=exp⁡(G/H′)e=\exp(G/H') divides both νℓ0\nu\ell_0 and nn. Hence u=n−ℓu=n-\ell is a positive multiple of ee. There are at least n−1n-1 points outside the chosen mm, and

u+3(e−1)=n−ℓ+3(e−1)≤n−1.u+3(e-1)=n-\ell+3(e-1)\leq n-1.

Apply (1) to their images in G/H′G/H'. We obtain uu points whose sum hh belongs to H′H'. Choose ℓ\ell points in the box with sum −h-h. The two choices are disjoint and contain u+ℓ=nu+\ell=n points with sum zero. This proves the upper bound. Kemnitz’s lower bound gives equality. □

Remark. Theorem 1.1 holds for every n≥n0n\geq n_0, where one may take

n0=2221000.n_0=2^{2^{2^{1000}}}.

Let x=s+3000x=s+3000. By (2), s=2960s=2^{960}, D=22164D=2^{2164}, and log⁡2ℓ0≤Dlog⁡2D<22176\log_2\ell_0\leq D\log_2D<2^{2176}. The recurrence gives

log⁡2(1/bs)≤2s(log⁡2(1/b0)+log⁡2J)<2s+2178,\log_2(1/b_s)\leq2^s\bigl(\log_2(1/b_0)+\log_2J\bigr)<2^{s+2178},

since log⁡2(1/b0)=K6=21440\log_2(1/b_0)=K^6=2^{1440} and log⁡2J=9+2log⁡2s+log⁡2ℓ0+10log⁡2K\log_2J=9+2\log_2s+\log_2\ell_0+10\log_2K. In particular, log⁡2(2s/bs)<2x\log_2(2^s/b_s)<2^x and log⁡2(1/a0)=log⁡2(48ℓ0)+2log⁡2(1/bs)<2x\log_2(1/a_0)=\log_2(48\ell_0)+2\log_2(1/b_s)<2^x. Since a0<1/100a_0<1/100, the definition in Lemma 3.7 gives ra0≤219a0−3r_{a_0}\leq2^{19}a_0^{-3}. Thus

log⁡2ra0<2x+3,log⁡2ca0=36+3log⁡2ra0<2x+6.\log_2r_{a_0}<2^{x+3},\qquad\log_2c_{a_0}=36+3\log_2r_{a_0}<2^{x+6}.

The elementary bound log⁡2(ca0!)≤ca0log⁡2ca0\log_2(c_{a_0}!)\leq c_{a_0}\log_2c_{a_0} now gives log⁡2F(a0)<22x+8\log_2F(a_0)<2^{2x+8}. Since x+8<21000x+8<2^{1000}, every n≥n0n\geq n_0 satisfies both size conditions in the proof.

The explicit threshold n0=2221000n_0=2^{2^{2^{1000}}} can be reduced by refining the estimates. We have chosen this value to keep the quantitative argument concise. We expect that further optimization, with the aid of large language models, could substantially reduce the threshold, while still leaving an extremely large bound. In our view, such improvements have limited theoretical significance unless n0n_0 can be reduced to a small integer.

Declaration of generative AI and AI-assisted technologies

The authors used a large language model during the preparation of this manuscript for assistance with mathematical exploration, checking arguments, organization and language editing. The authors are responsible for the mathematical statements, proofs, references and final text.

References

School of Mathematical Sciences, Tiangong University, Tianjin 300387, P.R. China Email address: [email protected]

Center for Combinatorics, Nankai University, Tianjin 300071, P.R. China Email address: [email protected]

References

  1. [1]N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in Combinatorics, Paul Erdős is Eighty, Vol. 1, János Bolyai Math. Soc., Budapest, 1993, 33–50.
  2. [2]N. Alon and M. Dubiner, A lattice point problem and additive number theory, Combinatorica 15 (1995), 301–309.DOI
  3. [3]M. DeVos, L. Goddyn and B. Mohar, A generalization of Kneser’s addition theorem, Adv. Math. 220 (2009), 1531–1548.DOI
  4. [4]P. Erdős, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel Sect. F 10 (1961), 41–43.
  5. [5]W. Gao, On zero-sum subsequences of restricted size, J. Number Theory 61 (1996), 97–102.DOI
  6. [6]W. Gao, Note on a zero-sum problem, J. Combin. Theory Ser. A 95 (2001), 387–389.DOI
  7. [7]W. Gao and A. Geroldinger, Zero-sum problems and coverings by proper cosets, European J. Combin. 24 (2003), 531–549.DOI
  8. [8]W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: a survey, Expo. Math. 24 (2006), 337–369.DOI
  9. [9]W. Gao, A. Geroldinger and W. A. Schmid, Inverse zero-sum problems, Acta Arith. 128 (2007), 245–279.DOI
  10. [10]W. D. Gao and R. Thangadurai, A variant of Kemnitz Conjecture, J. Combin. Theory Ser. A 107 (2004), 69–86.DOI
  11. [11]B. Girard, S. Griffiths and Y. O. Hamidoune, k-sums in abelian groups, Combin. Probab. Comput. 21 (2012), 582–596.DOI
  12. [12]P. Graham, The Harborth constant of Cₚ ⊕ Cₚ for every prime p ≥ 11, Zenodo preprint, 4 November 2026, doi:10.5281/zenodo.23968472, arXiv:2611.00487.
  13. [13]B. Green and I. Z. Ruzsa, Freiman’s theorem in an arbitrary abelian group, J. Lond. Math. Soc. 75 (2007), 163–175.DOI
  14. [14]P. Guillot, L. E. Marchan, O. Ordaz, W. A. Schmid and H. Zerdoum, On the Harborth constant of C₃ ⊕ C₃ₚ, J. Théor. Nombres Bordeaux 31 (2019), 613–633.
  15. [15]H. Harborth, Ein Extremalproblem für Gitterpunkte, J. Reine Angew. Math. 262/263 (1973), 356–360.DOI
  16. [16]A. Kemnitz, Extremalprobleme für Gitterpunkte, doctoral dissertation, Technische Universität Braunschweig, 1982.
  17. [17]A. Kemnitz, On a lattice point problem, Ars Combin. 16-B (1983), 151–160.
  18. [18]L. E. Marchan, O. Ordaz, D. Ramos and W. A. Schmid, Some exact values of the Harborth constant and its plus-minus weighted analogue, Arch. Math. 101 (2013), 501–512.arxiv.org/abs/1308.3315
  19. [19]G. Petridis, New proofs of Plünnecke-type estimates for product sets in groups, Combinatorica 32 (2012), 721–733.
  20. [20]C. Reiher, On Kemnitz’ conjecture concerning lattice-points in the plane, Ramanujan J. 13 (2007), 333–337.DOI
  21. [21]C. Reiher and T. Schoen, Note on the theorem of Balog, Szemerédi, and Gowers, Combinatorica 44 (2024), 691–698.DOI
  22. [22]L. Rónyai, On a conjecture of Kemnitz, Combinatorica 20 (2000), 569–573.DOI
  23. [23]S. Savchev and F. Chen, Long zero-free sequences in finite cyclic groups, Discrete Math. 307 (2007), 2671–2679.DOI
  24. [24]S. Savchev and F. Chen, Long n-zero-free sequences in finite cyclic groups, Discrete Math. 308 (2008), 1–8.
  25. [25]B. Sury and R. Thangadurai, Gao’s conjecture on zero-sum sequences, Proc. Indian Acad. Sci. Math. Sci. 112 (2002), 399–414.
  26. [26]R. Thangadurai, On a conjecture of Kemnitz, C. R. Math. Rep. Acad. Sci. Canada 23 (2001), 39–45.

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

a large language model

View statement
Looking for related papers…
Contents