betaFeedback

WorksMathematics

The equality s(G)=η(G)+exp⁡(G)−1s(G)=η(G)+\exp(G)-1 fails for G=C27⊕C6G=C_2^7\oplus C_6

Abstract

Let GG be a finite abelian group. The Erdős-Ginzburg-Ziv constant s(G)\mathsf{s}(G) is the smallest positive integer ℓ\ell such that every sequence over GG of length at least ℓ\ell contains a zero-sum subsequence of length exp⁡(G)\exp(G). The short zero-sum constant η(G)η(G) is defined similarly, with the requirement that the zero-sum subsequence is nonempty and has length at most exp⁡(G)\exp(G). It is known that s(G)≥η(G)+exp⁡(G)−1.\mathsf{s}(G)\ge η(G)+\exp(G)-1. A conjecture proposed by W. Gao in 2003, which has been widely studied in zero-sum theory, predicts that s(G)=η(G)+exp⁡(G)−1 \mathsf{s}(G)=η(G)+\exp(G)-1 for every nontrivial finite abelian group GG. In this paper, we prove that this conjecture fails for the group C27⊕C6C_2^7\oplus C_6.

Introduction

Let GG be a finite abelian group, and let n=exp⁡(G)n = \operatorname{exp}(G). A nonempty zero-sum subsequence is called short if its length is at most nn. The constant η(G)\eta(G) is the least integer ℓ\ell such that every sequence over GG of length at least ℓ\ell has a short zero-sum subsequence. The Erdős–Ginzburg–Ziv constant s(G)s(G) is defined in the same way, with the required length equal to nn; Both invariants are widely studied in zero-sum theory, see [3 Section 6] for a survey.

The celebrated Erdős–Ginzburg–Ziv Theorem [1] gives s(Cn)=2n−1s(C_n) = 2n - 1; while η(Cn)=n\eta(C_n) = n holds trivially. For general groups, an elementary construction gives

s(G)≥η(G)+n−1.(1)s(G) \ge\eta(G) + n - 1. \tag*{(1)}

Gao [2 Conjecture 2.3] conjectured that equality always holds in (1).

Several substantial classes of groups satisfy this equality. For 1≤m∣n1 \le m \mid n, the exact formulas are

η(Cm⊕Cn)=2m+n−2,s(Cm⊕Cn)=2m+2n−3;\eta(C_m \oplus C_n) = 2m + n - 2,\qquad s(C_m \oplus C_n) = 2m + 2n - 3;

see [3 Theorem 6.3]. The determination of the second constant rests on Reiher’s proof of Kemnitz’ conjecture [7]. Gao proved the equality for every group of exponent 2, 3 or 4 [2 Theorem 2.5]. There are also results beyond rank two: Girard and Schmid [4 Theorems 3.1 and 3.2], for example, established it for C2⊕C2m⊕C2mC_2 \oplus C_{2m} \oplus C_{2m} for every m≥1m \ge1.

In this paper, we prove that this conjectured equality in (1) fails for the group C27⊕C6C_2^7 \oplus C_6 as given in the following theorem.

Theorem 1.1. For G∗=C27⊕C6G_* = C_2^7 \oplus C_6, we have s(G∗)>η(G∗)+exp⁡(G∗)−1s(G_*) > \eta(G_*) + \operatorname{exp}(G_*) - 1.

Notation and preliminaries

We follow the conventions of [3 Section 2]. The free abelian monoid over GG is denoted by F(G)\mathcal{F}(G). Its elements are sequences, written multiplicatively:

S=g1⋯gℓ=∏g∈Ggvg(S).S = g_1 \cdots g_\ell= \prod_{g \in G} g^{v_g(S)}.

Here ∣S∣=ℓ|S| = \ell is the length, vg(S)v_g(S) is the multiplicity of gg, supp⁡(S)={g:vg(S)>0}\operatorname{supp}(S) = \{g : v_g(S) > 0\} is the support, and σ(S)=∑i=1ℓgi\sigma(S) = \sum_{i=1}^{\ell} g_i is the sum. The empty sequence is denoted by 11. We write T∣ST \mid S when TT is a subsequence of SS; its complementary subsequence is T−1ST^{-1}S. A sequence is squarefree if all multiplicities are at most one. We identify a squarefree sequence with its support whenever convenient.

keywords: Erdős–Ginzburg–Ziv constant, short zero-sum constant

For k≥1k \ge1, put

Σk(S)={σ(T):T∣S, ∣T∣=k},Σ≤k(S)=⋃j=1kΣj(S),Σ(S)=⋃j≥1Σj(S).\Sigma_k(S)=\{\sigma(T):T\mid S,\ |T|=k\},\qquad\Sigma_{\leq k}(S)=\bigcup_{j=1}^{k}\Sigma_j(S),\qquad\Sigma(S)=\bigcup_{j\geq1}\Sigma_j(S).

Thus the empty subsequence is excluded from Σ(S)\Sigma(S) and Σ≤k(S)\Sigma_{\leq k}(S). When it is to be included, we write

Σ0(S)={0},Σ≤k0(S)={0}∪Σ≤k(S).\Sigma_0(S)=\{0\},\qquad\Sigma_{\leq k}^{0}(S)=\{0\}\cup\Sigma_{\leq k}(S).

For a subset X⊂GX\subset G, these definitions refer to the squarefree sequence ∏x∈Xx\prod_{x\in X}x. In particular, Σ2(X)\Sigma_2(X) consists of sums of distinct elements, whereas X+XX+X allows the two summands to coincide.

A sequence SS is zero-sumfree if 0∉Σ(S)0\notin\Sigma(S).

The Davenport constant D(G)D(G) is the least integer ℓ\ell such that every sequence over GG of length at least ℓ\ell has a nonempty zero-sum subsequence.

A homomorphism φ:G→G′\varphi:G\to G' is applied to sequences term by term. In particular, φ(S)=φ(g1)⋯φ(gℓ)\varphi(S)=\varphi(g_1)\cdots\varphi(g_\ell) and σ(φ(S))=φ(σ(S))\sigma(\varphi(S))=\varphi(\sigma(S)). Translation also acts term by term: h+S=(h+g1)⋯(h+gℓ)h+S=(h+g_1)\cdots(h+g_\ell).

We identify C2rC_2^r with the vector space F2r\mathbb{F}_2^r. Let X={x1,…,xN}⊂F2rX=\{x_1,\ldots,x_N\}\subset\mathbb{F}_2^r be nonempty. Its even relation code is

KX={ε∈F2N:∑iεi=0, ∑iεixi=0}.K_X=\left\{\varepsilon\in\mathbb{F}_2^N:\sum_i\varepsilon_i=0,\ \sum_i\varepsilon_i x_i=0\right\}.

The Hamming weight wt⁡(ε)\operatorname{wt}(\varepsilon) is the number of nonzero coordinates. Thus a word of weight 2j2j in KXK_X corresponds to a zero-sum subsequence of XX of length 2j2j. The matrix with columns (1,xi)(1,x_i) has rank 1+dim⁡aff⁡(X)1+\dim\operatorname{aff}(X), so

dim⁡KX=N−1−dim⁡aff⁡(X).\dim K_X=N-1-\dim\operatorname{aff}(X).

Let TX≤KXT_X\leq K_X be generated by the words of weight four, called tetrads. Their supports connect the coordinates into components. A coordinate lying in no tetrad is called unused; otherwise it is called active. The notation 0u0_u means uu unused coordinates. These coding terms will be used only to describe the possible four-term zero-sum relations of a squarefree sequence.

We repeatedly use the following elementary observation. For two binary words x,yx,y,

wt⁡(x)+wt⁡(y)+wt⁡(x+y)=2∣supp⁡(x)∪supp⁡(y)∣.\operatorname{wt}(x)+\operatorname{wt}(y)+\operatorname{wt}(x+y)=2\lvert\operatorname{supp}(x)\cup\operatorname{supp}(y)\rvert.

Consequently, if three nonzero words x,y,x+yx,y,x+y each have weight at least mm and are supported on NN coordinates, then 3m≤2N3m\leq2N. This will rule out several small relation spaces.

Proof of Theorem 1.1

In this section, we shall prove Theorem 1.1. Throughout this section, identify

G∗=C27⊕C6≅V⊕C3,V=C28=F28.G_* = C_2^7\oplus C_6\cong V\oplus C_3,\qquad V=C_2^8=\mathbb{F}_2^8.

and let π:G∗→V\pi:G_*\to V and χ:G∗→C3\chi:G_*\to C_3 be the projections. We write the elements of C3C_3 as 0,1,−10,1,-1. For a sequence SS, let SiS_i be its subsequence of all terms with C3C_3-coordinate ii. Thus S=S0S1S−1S=S_0S_1S_{-1}. Whenever π(S)\pi(S) is squarefree, we put

A=supp⁡(π(S0)),B=supp⁡(π(S1)),C=supp⁡(π(S−1)),(a,b,c)=(∣A∣,∣B∣,∣C∣).A=\operatorname{supp}(\pi(S_0)),\qquad B=\operatorname{supp}(\pi(S_1)),\qquad C=\operatorname{supp}(\pi(S_{-1})),\qquad(a,b,c)=(|A|,|B|,|C|).

The sets A,B,CA,B,C are then pairwise disjoint. We use subsets of VV only after making this identification with squarefree sequences.

The rest of this section contains three subsections.

The lower bound and the reduction to squarefree projections

Lemma 3.1. There is a sequence over G∗G_* of length 32 without a zero-sum subsequence of length 6.

Proof. Let e1,…,e6e_1,\ldots,e_6 be a basis of F26\mathbb{F}_2^6, and set

C0={0,e1,…,e6,e1+⋯+e6},B0=C0×F2⊂F27.C_0=\{0,e_1,\ldots,e_6,e_1+\cdots+e_6\},\qquad B_0=C_0\times\mathbb{F}_2\subset\mathbb{F}_2^7.

The only nonempty subset of C0C_0 having even cardinality and sum zero is C0C_0 itself. Indeed, a relation involving e1+⋯+e6e_1+\cdots+e_6 must involve every eie_i, and the point 00 is then needed to make its cardinality even. Suppose that six distinct points of B0B_0 had sum zero. The points of C0C_0 whose fibers contribute an odd number of terms would form an even zero-sum subset of size at most six. That subset is empty, so the six points must be three complete fibers of size two. Their last coordinates sum to 11, a contradiction.

Now use G∗=F27⊕C6G_*=\mathbb{F}_2^7\oplus C_6, and take

S=∏b∈B0(b,0)(b,1).S=\prod_{b\in B_0}(b,0)(b,1).

If T∣ST\mid S has length six and sum zero, its C6C_6-coordinate forces all six terms to have coordinate 00 or all six to have coordinate 11. Their first coordinates would be six distinct elements of B0B_0 summing to zero, which is impossible. Hence s(G∗)≥33s(G_*)\ge33. This is the binary doubling construction of [8 Theorem 5.4]. □

For the upper bound, suppose that S∈F(G∗)S\in\mathcal{F}(G_*) has no short zero-sum subsequence. Three elementary restrictions will be useful. First, ∣S0∣≤9|S_0|\le9. Otherwise ten of its projected terms have two independent binary relations x,yx,y. Every nonzero relation has weight at least seven, contradicting 21≤2021\le20 for x,y,x+yx,y,x+y. Second, v0(π(S))≤2v_0(\pi(S))\le2, since D(C3)=3D(C_3)=3. Third, SS has at most two pairwise disjoint subsequences PP of length two with σ(π(P))=0\sigma(\pi(P))=0. Such a PP has χ(σ(P))≠0\chi(\sigma(P))\ne0. Two disjoint such subsequences cannot have opposite sums in C3C_3, and three with the same sum would together form a zero-sum subsequence of length six.

We reduce the remaining argument to the following two assertions.

(R) Residual subsequences. Let R∈F(G∗)R\in\mathcal{F}(G_*) satisfy

(1) π(R)\pi(R) is squarefree, 0∉supp⁡(π(R))0\notin\operatorname{supp}(\pi(R)), and ∣R0∣≤9|R_0|\le9;

(2) if T∣RT\mid R, σ(π(T))=0\sigma(\pi(T))=0 and ∣T∣∈{3,4}|T|\in\{3,4\}, then χ(σ(T))=1\chi(\sigma(T))=1;

(3) if T∣RT\mid R, σ(π(T))=0\sigma(\pi(T))=0 and ∣T∣∈{5,6}|T|\in\{5,6\}, then χ(σ(T))≠0\chi(\sigma(T))\ne0.

Then ∣R∣≤23|R|\le23, and equality implies R−1=1R_{-1}=1.

(P) Squarefree projections. If S∈F(G∗)S\in\mathcal{F}(G_*) has length 2727, π(S)\pi(S) is squarefree, 0∉supp⁡(π(S))0\notin\operatorname{supp}(\pi(S)) and ∣S0∣≤9|S_0|\le9, then SS has a short zero-sum subsequence.

Lemma 3.2. Assertions (R) and (P) imply η(G∗)≤27\eta(G_*)\le27.

Proof. Suppose that ∣S∣=27|S|=27 and SS has no short zero-sum subsequence. If π(S)\pi(S) is squarefree and does not contain 00, assertion (P) applies. Otherwise choose E∣SE\mid S as follows: take two terms with equal projection if such terms exist, and otherwise take one term projecting to zero. Thus ∣E∣∈{1,2}|E|\in\{1,2\} and σ(π(E))=0\sigma(\pi(E))=0. Its C3C_3-sum is nonzero. Applying the automorphism (v,i)↦(v,−i)(v,i)\mapsto(v,-i) if necessary, assume χ(σ(E))=1\chi(\sigma(E))=1.

Every subsequence R∣E−1SR\mid E^{-1}S whose projection is squarefree and avoids 00 satisfies the hypotheses of (R). To see the only additional condition, let T∣RT\mid R have projected sum zero and length three or four. Its C3C_3-sum cannot be zero, since TT is short, and cannot be −1-1, since ETET would be short and zero-sum. It must therefore be 11. The conditions for lengths five and six follow directly from the assumption on SS.

Suppose first that SS contains no two disjoint pairs of terms with equal projection. Delete the chosen subsequence EE. After also removing any remaining term projecting to zero, at least 2424 terms remain, with distinct nonzero projections. They give a contradiction to (R). Here a third occurrence of a projected value causes no difficulty: removing two occurrences leaves only one; four occurrences or two different repeated values would give two disjoint pairs.

It remains to consider two disjoint pairs P,Q∣SP,Q\mid S, each with projected sum zero. Their C3C_3-sums agree, and we may normalize both to 11. Put R=(PQ)−1SR=(PQ)^{-1}S, so ∣R∣=23|R|=23. There is no repeated projection in RR, since it would give a third disjoint pair. Nor can a term g∣Rg\mid R project to zero: according as χ(g)=0,−1,1\chi(g)=0,-1,1, one of gg, PgPg, PQgPQg would be short and zero-sum. Assertion (R) therefore applies, and all terms of RR have C3C_3-coordinate 0 or 1.

Let xx be the common projection of the terms of QQ. If x≠0x\ne0 and x∉supp⁡(π(R))x\notin\operatorname{supp}(\pi(R)), adjoining either term of QQ to RR gives a sequence of length 24 satisfying (R), using PP as the deleted subsequence EE. If x∈supp⁡(π(R))x\in\operatorname{supp}(\pi(R)), the two terms of QQ and the term of RR with projection xx give three possible pairs, each disjoint from PP. Their C3C_3-sums must all be 1. Writing their coordinates as i,j,ki,j,k, the equations i+j=i+k=j+k=1i+j=i+k=j+k=1 force i=j=k=−1i=j=k=-1, contrary to the conclusion for RR. Thus x=0x=0. The same argument applies to PP, yielding four terms projecting to zero, contrary to v0(π(S))≤2v_0(\pi(S))\le2. □

We now prove (R) and (P). The next subsection establishes the common counting estimates and proves (R); the last subsection proves (P) by counting in three-dimensional quotients.

Binary structure and residual subsequences

We first count three-term sums of a squarefree sequence in VV with no zero-sum subsequence of length six. The four-term relations determine this count. After establishing the counting and overlap estimates, we apply them to the projected coordinate classes and prove assertion (R).

Lemma 3.3. Let X⊂VX\subset V satisfy 0∉Σ6(X)0\notin\Sigma_6(X). The code TXT_X is a direct sum of unused coordinates and blocks of the following types:

  1. d2md_{2m}, for m≥2m\ge2: partition the 2m2m coordinates into mm pairs, and take the unions of an even number of these pairs;

  2. e7e_7 and e8e_8: the even relation codes of a punctured affine three-space and a full affine three-space, respectively.

The pairs in a d2md_{2m} block all have the same nonzero sum.

Proof. Two tetrads cannot meet in one point: their symmetric difference would be a zero-sum subsequence of length six. They cannot meet in three points either, since their symmetric difference would have length two and XX is squarefree. Thus any two tetrads meet evenly. The decomposition theorem of Pless–Sloane [6 Theorem 6.5] gives precisely the stated blocks.

In d2md_{2m}, the union of any two coordinate pairs is a tetrad. Consequently the two pairs have the same sum; denote this sum by dd. The corresponding points are therefore pairs {x,x+d}\{x,x+d\}. An ese_s block, s∈{7,8}s\in\{7,8\}, supplies s−4s-4 independent even relations, so its points have affine dimension at most three. There are more than four distinct points, so the affine dimension is exactly three. This identifies the points with the stated punctured or full affine three-space. □

We record two geometric consequences that will be used later. First, suppose that XX consists of two e8e_8 blocks, written x+U0x+U_0 and y+W0y+W_0, where U0,W0U_0,W_0 have dimension three. Their direction spaces meet trivially: a common nonzero direction would give a tetrad meeting both blocks. Also x+y∉U0+W0x+y\notin U_0+W_0, because the two affine spaces are disjoint. Hence

L=x+U0+W0+⟨x+y⟩ has affine dimension seven,Σ3(X)=L,Σ4(X)=L+L.(2)L=x+U_0+W_0+\langle x+y\rangle\text{ has affine dimension seven},\qquad\Sigma_3(X)=L,\qquad\Sigma_4(X)=L+L. \tag*{(2)}

For the three-term sums, separate the selections according to which block contributes an odd number of points. The selections using one point of the first block and two of the second, together with those using three of the first, fill x+U0+W0x+U_0+W_0; reversing the blocks gives y+U0+W0y+U_0+W_0. For four-term sums, selections of types 4+04+0, 2+22+2 and 0+40+4 give U0+W0U_0+W_0; selections of types 3+13+1 and 1+31+3 give x+y+U0+W0x+y+U_0+W_0. These are exactly the sets in (3.1).

Second, let DD consist of m≥7m\ge7 pairs with common sum dd, and write q1,…,qmq_1,\ldots,q_m for their distinct images in V/⟨d⟩V/\langle d\rangle. These indices have no even relation of length two, four or six. A four-term relation, together with a spare complete pair, would give six points summing to zero: choose the four lifts to sum to dd, and add the spare pair. A six-term relation gives the same contradiction by choosing lifts with sum zero. In particular, any seven indices are affinely independent, and the corresponding fourteen points span an affine seven-space.

The following description of the sumsets is useful. In a selection of points of DD, record the indices used an odd number of times. Changing the chosen point at any such index changes the sum by dd. It follows that Σ3(D)\Sigma_3(D) consists of both lifts of every one-index and three-index sum.

Similarly, Σ4(D)\Sigma_4(D) consists of both lifts of the two-index and four-index sums, together with 0, obtained from two complete pairs. The available spare pairs ensure that all these representations use distinct points.

Lemma 3.4. For a direct sum TT of the blocks above, let b(T)b(T) and r(T)r(T) be the numbers of cosets of TT represented by words of weight two and three, respectively. The component counts are

TTlengthb(T)b(T)r(T)r(T)
d2md_{2m}2m2m1+2(m2)1+2\binom{m}{2}2m+2(m3)2m+2\binom{m}{3}
e7e_7777788
e8e_8887788
010_1110000

For disjoint components of lengths n1,n2n_1,n_2,

b(T1⊕T2)=b(T1)+b(T2)+n1n2.(3)b(T_1\oplus T_2)=b(T_1)+b(T_2)+n_1n_2. \tag*{(3)}
r(T1⊕T2)=r(T1)+r(T2)+b(T1)n2+n1b(T2).(4)r(T_1\oplus T_2)=r(T_1)+r(T_2)+b(T_1)n_2+n_1b(T_2). \tag*{(4)}

If 0∉Σ6(X)0\notin\Sigma_6(X), then

r(TX)=∣Σ3(X)∣≤2dim⁡aff⁡(X).(5)r(T_X)=|\Sigma_3(X)|\le2^{\dim\operatorname{aff}(X)}. \tag*{(5)}

Proof. For d2md_{2m}, a weight-two word either selects one complete pair, giving one coset, or selects two different pair indices, giving two cosets for each pair of indices. A weight-three word has either one or three indices used oddly. These give 2m2m and 2(m3)2\binom{m}{3} cosets, respectively.

For e7,e8e_7,e_8, every nonzero direction in the affine three-space is a pair sum, giving seven possibilities. Every point of that affine space is also a three-term sum. Indeed, for a target tt, choose a point x≠tx\ne t of the block. There are at least three pairs with sum t+xt+x; at most one contains xx, so one of the others completes the required triple. This gives eight possibilities.

For a direct sum, distribute the selected coordinates between the two components. Weight two has distributions (2,0),(1,1),(0,2)(2,0),(1,1),(0,2), and weight three has distributions (3,0),(2,1),(1,2),(0,3)(3,0),(2,1),(1,2),(0,3). They give the terms in (3.3) and (3.4). The relevant cosets are distinct, since the component codes are even and have no words of weight two.

Finally, two distinct three-term selections of XX with equal sum have symmetric difference of weight two, four or six. Only weight four is possible, and this difference is a tetrad. Thus their incidence vectors lie in the same coset of TXT_X, and conversely a common coset gives equal sums. All odd sums belong to the affine span of XX, proving (3.5). □

For a block code TT of length nn, let d(T)d(T) be the number of blocks d2md_{2m} and let u(T)u(T) be the number of unused coordinates. Define

Fn(T)=r(T)−nd(T)−(n−2)⌊u(T)2⌋,g0(n)=2(⌈n/2⌉3),F_n(T)=r(T)-nd(T)-(n-2)\left\lfloor\frac{u(T)}{2}\right\rfloor,\qquad g_0(n)=2\binom{\lceil n/2\rceil}{3},

and put g(n)=g0(n)g(n)=g_0(n) except that g(9)=15g(9)=15. As usual, a binomial coefficient is zero when its upper argument is smaller than its lower argument. The subtractions in FnF_n will account for overlaps between three-term sums and translates.

Lemma 3.5. For n≤19n\le19, one has Fn(T)≥g(n)F_n(T)\ge g(n). Moreover,

(1) F14(T)≤99F_{14}(T)\le99 forces T=d14T=d_{14};

(2) F16(T)≤153F_{16}(T)\le153 forces T=d16T=d_{16} or e8⊕e8e_8\oplus e_8, with values 112 and 128, respectively;

(3) F18(T)≤223F_{18}(T)\le223 forces T=d18T=d_{18}.

Every squarefree sequence over VV of length nineteen has a zero-sum subsequence of length six.

Proof. We reduce the calculation to a single paired block and at most two exceptional blocks e7,e8e_7,e_8. Replace each pair of unused coordinates formally by a block d2d_2 with counts (n,b,r)=(2,1,2)(n,b,r)=(2,1,2). This is only a counting device. It increases r(T)r(T) by two and increases the subtracted quantity in Fn(T)F_n(T) by two, so FnF_n is unchanged.

Next merge paired blocks of half-lengths x,yx,y into d2(x+y)d_{2(x+y)}. Using (3.3) and (3.4), the decrease in FnF_n is

xy(2n−2−3x−3y)≥0.(6)xy(2n-2-3x-3y)\ge0. \tag*{(6)}

Indeed, n≥2(x+y)n \ge2(x+y) and x+y≥2x+y \ge2. Thus repeated merging gives a lower bound for the original FnF_n.

Call the sum of the e7,e8e_7,e_8 blocks the exceptional core, and let its length, pair count and triple count be (s,p,r)(s,p,r). Write m=n−sm=n-s. After merging, the remaining coordinates consist of one paired block and, when mm is odd, one unused coordinate. Applying the direct-sum formulas gives

Fn(T)≥Qn(s,p,r):=r+pm+2s(⌈m/2⌉2)+g0(m).(7)F_n(T) \ge Q_n(s,p,r) := r+pm+2s\binom{\lceil m/2\rceil}{2}+g_0(m). \tag*{(7)}

For example, when m=2ℓm=2\ell, the paired block has counts b=1+2(ℓ2)b=1+2\binom{\ell}{2}, r=m+2(ℓ3)r=m+2\binom{\ell}{3}; its subtraction of n=s+mn=s+m cancels the terms s+ms+m in the direct-sum formula. For odd mm, the same calculation uses (ℓ3)+(ℓ+12)=(ℓ+13)\binom{\ell}{3}+\binom{\ell+1}{2}=\binom{\ell+1}{3}. The cases m=0,1m=0,1 follow directly as well.

An empty core gives Qn=g0(n)Q_n=g_0(n). For one exceptional block, the excess Qn−g0(n)Q_n-g_0(n) is as follows:

corem=2ℓm=2\ellm=2ℓ+1m=2\ell+1
e7e_7ℓ(3ℓ−1)\ell(3\ell-1)4ℓ2+12ℓ+74\ell^2+12\ell+7
e8e_82ℓ(2ℓ−1)2\ell(2\ell-1)4ℓ2+6ℓ−54\ell^2+6\ell-5

Table 3.

Every entry is nonnegative except the last one at ℓ=0\ell=0. That exception is e8⊕01e_8\oplus0_1, whose value is F9=15F_9=15, explaining the definition of g(9)g(9).

There can be at most two exceptional blocks, since n≤19n\le19. Their core counts, obtained from (3)–(4), are

coresspprr
e7⊕e7e_7\oplus e_71463114
e7⊕e8e_7\oplus e_81570121
e8⊕e8e_8\oplus e_81678128

Table 4.

In particular Qn≥114+63mQ_n\ge114+63m. For m=0m=0, we have n≤16n\le16 and g0(n)≤112g_0(n)\le112; for m=1m=1, we have n≤17n\le17 and g0(n)≤168g_0(n)\le168; for m≥2m\ge2, we have g0(n)≤g0(19)=240≤114+63mg_0(n)\le g_0(19)=240\le114+63m. This proves Fn≥g(n)F_n\ge g(n); lengths at most three can also be checked immediately from the definitions.

We now retain the information needed for the three small profiles. For a core-free code of even length n=2ℓn=2\ell other than dnd_n, the last merger has half-lengths x+y=ℓx+y=\ell and decreases FnF_n by xy(ℓ−2)≥(ℓ−1)(ℓ−2)xy(\ell-2)\ge(\ell-1)(\ell-2). Since Fn(dn)=g0(n)F_n(d_n)=g_0(n), the resulting lower bounds at n=14,16,18n=14,16,18 are 100, 154, 224. For nonempty cores, (3.6) gives the following table:

coreQ14Q_{14}Q16Q_{16}Q18Q_{18}
e7e_7149231335
e8e_8100168258
e7⊕e7e_7\oplus e_7114240394
e7⊕e8e_7\oplus e_8--191361
e8⊕e8e_8\oplus e_8--128284

Table 5.

A dash means the core is too long. Comparing these entries with 99, 153, 223 proves the asserted profiles.

Finally, a block code of length nineteen has a paired block or at least three unused coordinates: without either, the two possible exceptional blocks and at most two unused coordinates use at most eighteen coordinates. Therefore

r(T)≥F19(T)+17≥g(19)+17=257.r(T)\ge F_{19}(T)+17\ge g(19)+17=257.

For a squarefree sequence in VV with 0∉Σ6(X)0\notin\Sigma_6(X) this contradicts r(TX)=∣Σ3(X)∣≤256r(T_X)=|\Sigma_3(X)|\le256. □\square

Lemma 3.6. Suppose B⊂VB\subset V satisfies 0∉Σ6(B)0\notin\Sigma_6(B), and let E⊂VE\subset V satisfy

E∩Σ4(B)=∅,Σ2(E)∩Σ2(B)=∅.E\cap\Sigma_4(B)=\varnothing,\qquad\Sigma_2(E)\cap\Sigma_2(B)=\varnothing.

Then

∣Σ3(B)∖(B+E)∣≥F∣B∣(TB).|\Sigma_3(B)\setminus(B+E)|\ge F_{|B|}(T_B).

Proof. Put n=∣B∣n=|B|. If a sum of three distinct points of BB equals b+eb+e, with b∈Bb\in B and e∈Ee\in E, then that triple contains bb. Otherwise the four distinct BB-points would represent ee, contrary to E∩Σ4(B)=∅E\cap\Sigma_4(B)=\varnothing. The other two points therefore form a pair representing ee.

Such a pair meets every tetrad evenly. If it met a tetrad in exactly one point, their symmetric difference would be a four-point representation of ee. It follows from the block description that the pair is either entirely unused or lies in one paired block. Indeed, an active pair crossing two blocks meets some tetrad in one point. In e7e_7 or e8e_8, an affine plane can be chosen through one endpoint and avoiding the other (and the missing point in the e7e_7 case), with the same consequence. Within d2md_{2m}, m≥3m\ge3, a third coordinate pair shows that a pair meeting every tetrad evenly must be one of the distinguished pairs, so its sum is the common direction. For d4d_4, there are three possible pair directions, but two of them cannot both belong to EE: their sum belongs to Σ2(B)\Sigma_2(B).

Pairs of unused coordinates have unique representations, since two different pairs with the same sum would produce a tetrad. Two selected unused pairs cannot share an endpoint either: the sum of their two different represented elements of EE would then belong to Σ2(B)\Sigma_2(B).

Thus at most d(TB)d(T_B) block directions can contribute to the overlap, each through at most nn choices of bb. At most ⌊u(TB)/2⌋\lfloor u(T_B)/2\rfloor unused pairs contribute, each through at most n−2n-2 choices, since bb must avoid that pair. Subtracting these upper bounds from r(TB)=∣Σ3(B)∣r(T_B)=|\Sigma_3(B)| proves the claim. □

Proposition 3.7. Suppose S∈F(G∗)S\in\mathcal{F}(G_*) has no short zero-sum subsequence, π(S)\pi(S) is squarefree, and 0∉supp⁡(π(S))0\notin\operatorname{supp}(\pi(S)). Use the classes AA, BB, CC and lengths aa, bb, cc defined above, and put H(a)=1+a+(a2)+(a3)H(a)=1+a+\binom{a}{2}+\binom{a}{3}. Then

H(a)+bc+Fb(TB)+Fc(TC)≤256,b+c≤24.(8)H(a)+bc+F_b(T_B)+F_c(T_C)\le256,\qquad b+c\le24. \tag*{(8)}

If ∣S∣=27|S|=27, then 3≤a≤83\le a\le8 and b,c≤16b,c\le16.

Proof. All sums of at most three distinct points of AA, including the empty sum, are different: a collision gives a nonempty zero-sum subsequence of S0S_0 of length at most six. Thus there are H(a)H(a) such sums. Also B+CB+C has bcbc elements, because two different representations give a zero-sum subsequence with two terms of each nonzero C3C_3-coordinate. The four sets

Σ≤30(A),B+C,Σ3(B)∖(B+C),Σ3(C)∖(B+C)\Sigma_{\le3}^{0}(A),\quad B+C,\quad\Sigma_3(B)\setminus(B+C),\quad\Sigma_3(C)\setminus(B+C)

are pairwise disjoint: an intersection would again give a short zero-sum subsequence. For example, three terms from BB have C3C_3-sum zero, as do three from CC. Lemma 3.6 applies with (B,E)=(B,C)(B,E)=(B,C), and also with B,CB,C interchanged. Its hypotheses follow by excluding projected relations with four terms from one class and one from the other, or two from each. This proves the first inequality.

By Lemma 3.5, b,c≤18b,c\le18. If b+c≥25b+c\ge25, take a subsequence with b+c=25b+c=25 and write its even class size as 2k2k. Then 4≤k≤94\le k\le9. On the even class g=g0g=g_0, and on the odd class g≥g0−5g\ge g_0-5, so expansion gives

bc+g(b)+g(c)≥259+(k−7)(7k−44)≥259.bc+g(b)+g(c)\ge259+(k-7)(7k-44)\ge259.

For the six possible integers kk, the last product is nonnegative. This contradicts the first inequality and proves b+c≤24b+c\le24.

Now suppose ∣S∣=27|S|=27. The preliminary bound a≤9a\le9 and b+c≤24b+c\le24 give 3≤a≤93\le a\le9. For these integers,

H(a)−16a+54=(a−5)(a−6)(a+11)6≥0.H(a)-16a+54=\frac{(a-5)(a-6)(a+11)}{6}\ge0.

If b∈{17,18}b\in\{17,18\}, then bc≥18(9−a)bc\ge18(9-a) and Fb(TB)≥168F_b(T_B)\ge168. Hence (3.7) implies

256≥H(a)+bc+168≥276−2a≥258,256\ge H(a)+bc+168\ge276-2a\ge258,

a contradiction. The same argument applies to cc.

It remains to exclude a=9a=9. The binary relation space of AA has dimension one: it is nonzero because A⊂VA\subset V, and two independent relations would give 21≤1821\le18, since every nonzero relation has weight at least seven. Its unique nonzero word has weight seven, eight or nine. Among the 256 selections of at most four points of AA, a repeated sum comes from complementary parts of that word. There are at most 35 pairs of equal sums ((73)=35\binom{7}{3}=35 or (84)/2=35\binom{8}{4}/2=35). Thus ∣Σ≤40(A)∣≥221|\Sigma_{\leq4}^{0}(A)| \geq221. This set is disjoint from B+CB+C, so bc≤35bc \leq35. Since b+c=18b+c=18 and b,c≤16b,c\leq16, only {b,c}={16,2}\{b,c\}=\{16,2\} remains. But then

256≥H(9)+32+g(16)=130+32+112=274,256 \geq H(9)+32+g(16)=130+32+112=274,

the final contradiction. □

Lemma 3.8. Let RR satisfy the hypotheses of (R). If supp⁡(χ(R))⊆{0,1}\operatorname{supp}(\chi(R))\subseteq\{0,1\}, then ∣R∣≤23|R|\leq23.

Proof. The hypotheses are inherited by subsequences, so it suffices to exclude ∣R∣=24|R|=24. Let A,BA,B be the projected classes with C3C_{3}-coordinates 0,10,1, of lengths a,ba,b. The preliminary bound a≤9a\leq9 and Lemma 3.5, which gives b≤18b\leq18, imply 6≤a≤96\leq a\leq9. Put

A0={0}∪A,Y=B+A0,M=∣Y∣.A^{0}=\{0\}\cup A,\qquad Y=B+A^{0},\qquad M=|Y|.

The translates b0+A0b_{0}+A^{0}, for b0∈Bb_{0}\in B, are pairwise disjoint. Indeed, a collision between two translates gives two distinct points of BB together with one or two points of AA, having projected sum zero and C3C_{3}-sum 2, contrary to (R). Also 0∉Y0\notin Y, because A0∩B=∅A^{0}\cap B=\varnothing. Consequently

M=b(a+1).(9)M=b(a+1). \tag*{(9)}

Let kk be the number of three-element subsets of A0A^{0} whose sums belong to BB. Their sums are all different: two representations would give a nonempty zero-sum subsequence of AA of length at most six, forbidden by the hypotheses on RR. Every represented point of BB is unused in TBT_{B}. Otherwise a tetrad through that point, combined with its representation by A0A^{0}, gives three points of BB and two or three points of AA with total projected sum zero and C3C_{3}-sum zero.

There cannot be eight unused coordinates of TBT_{B}. Choose eight of them and any seven other coordinates, which exist because b≥15b\geq15. Three-term selections supported on these fifteen coordinates give at least

(83)+7(82)+8⋅6=56+196+48=300(10)\binom{8}{3}+7\binom{8}{2}+8\cdot6=56+196+48=300 \tag*{(10)}

distinct cosets of TBT_{B}. The three terms count selections with three, two and one unused coordinates. For the last term, the other seven coordinates have at least six distinct pair sums: fix one of them and pair it with each of the other six. Different subsets of unused coordinates cannot be identified modulo TBT_{B}. Thus (3.9) contradicts r(TB)=∣Σ3(B)∣≤256r(T_{B})=|\Sigma_{3}(B)|\leq256. We have proved

k≤7.(11)k\leq7. \tag*{(11)}

We now count ordered zero-sum triples in YY; write their number as τ\tau. Their terms are distinct because 0∉Y0\notin Y. Each y∈Yy\in Y has a unique expression b0+a0b_{0}+a_{0} with b0∈Bb_{0}\in B, a0∈A0a_{0}\in A^{0}. In a zero-sum triple, the three BB-coordinates cannot all be distinct: together with the uncancelled AA-coordinates they would give a forbidden subsequence of RR of length between three and six and C3C_{3}-sum zero. The three A0A^{0}-coordinates are distinct as well. If two were equal, cancelling them and the repeated BB-coordinate would force a point of BB to belong to A0A^{0}.

To bound τ\tau from above, choose the pair of positions with equal BB-coordinates, their common value, and the ordered triple from A0A^{0}. There are at most 3, bb and 6k6k choices, respectively; the remaining BB-coordinate is then determined by the zero-sum condition. This may overcount, which is harmless. Hence

τ≤18bk.\tau\leq18bk.

For the lower bound, fix the first term y∈Yy\in Y. The possible second terms form Y∩(y+Y)Y\cap(y+Y), and each determines the third. Since both sets have size MM in VV, ∣Y∩(y+Y)∣≥2M−256|Y\cap(y+Y)|\geq2M-256. Thus

M(2M−256)≤τ≤18bk.(12)M(2M-256)\leq\tau\leq18bk. \tag*{(12)}

For a≥7a\geq7, (3.8) gives M≥136M\geq136, while b≤17b\leq17. Together with (3.10), this gives 2176≤τ≤18⋅17⋅7=21422176\leq\tau\leq18\cdot17\cdot7=2142, a contradiction.

Therefore a=6a=6 and b=18b=18. As in the proof of Proposition 3.7, the sets Σ≤30(A)\Sigma_{\leq3}^{0}(A) and Σ3(B)\Sigma_{3}(B) are disjoint. Hence r(TB)≤256−H(6)=214r(T_{B})\leq256-H(6)=214. In particular F18(TB)≤214F_{18}(T_{B})\leq214, so Lemma 3.5 forces TB=d18T_B = d_{18}. There are no unused coordinates, hence k=0k = 0. By (12), YY has size 126 and is sum-free, meaning that Y∩(Y+Y)=∅Y \cap(Y + Y) = \varnothing.

We use the Davydov–Tombak classification in the form recorded in [5 Fact 2]. A maximal sum-free subset of F2r\mathbb{F}_2^r of size greater than 9⋅2r−59 \cdot2^{r-5} is either a nonzero hyperplane coset or has size 5⋅2r−45 \cdot2^{r-4}. Extend YY to a maximal sum-free set. Since 126>80=5⋅24126 > 80 = 5 \cdot2^4, only the hyperplane-coset alternative is possible. As B⊆YB \subseteq Y, the nine parallel pairs of BB lie in that coset. Their common direction belongs to its direction hyperplane; after quotienting by this direction, their nine indices have affine dimension at most six. Their even relation space therefore has dimension at least two. Every nonzero even relation has weight at least eight, by the parallel-pair description above. Two independent relations and their sum would then give 24≤2⋅9=1824 \leq2 \cdot9 = 18, the final contradiction. □

Proposition 3.9. Assertion (R) holds.

Proof. First let ∣R∣=23|R| = 23 and assume the hypotheses of (R). Adjoin the term (0,0)(0, 0) and translate every term by (0,−1)(0, -1); call the resulting sequence SS. Its projection is squarefree. For every Q∣SQ \mid S with σ(π(Q))=0\sigma(\pi(Q)) = 0, we have

χ(σ(Q))=0if ∣Q∣=4,χ(σ(Q))≠0if ∣Q∣=6.(13)\chi(\sigma(Q)) = 0 \quad\text{if } |Q| = 4,\qquad\chi(\sigma(Q)) \ne0 \quad\text{if } |Q| = 6. \tag*{(13)}

For a four-term subsequence not using the adjoined term, the translation subtracts 4≡14 \equiv1 from its original C3C_3-sum 1. If it uses the adjoined term, the other three terms originally had C3C_3-sum 1, so the same conclusion holds. For length six, the translation does not change the sum; the original five- or six-term condition applies according as the adjoined term occurs.

Let U,B,W⊂VU, B, W \subset V be the projected classes with C3C_3-coordinates −1,0,1-1, 0, 1, and put (u,b,w)=(∣U∣,∣B∣,∣W∣)(u,b,w) = (|U|, |B|, |W|). They are pairwise disjoint and u+b+w=24u + b + w = 24. Suppose, towards a contradiction, that u,w>0u,w > 0. The conditions (3.12) are invariant under the automorphism (v,i)↦(v,−i)(v,i) \mapsto(v,-i), so we may assume u≥wu \geq w.

Step 1: disjoint sumsets. Neither UU nor WW has a zero-sum subsequence of length four or six: four equal nonzero C3C_3-coordinates have nonzero sum, whereas six have sum zero, in both cases contradicting (3.12). Consequently their two-term sums have unique unordered representations, and all their one- and three-term sums are distinct. Moreover u,w≤10u,w \leq10. Eleven points in VV have at least two independent even relations, and the three nonzero words they generate would each have weight at least eight, contradicting 24≤2224 \leq22.

Put

T=U+W,FU=U∪Σ3(U),FW=W∪Σ3(W).T = U + W,\qquad F_U = U \cup\Sigma_3(U),\qquad F_W = W \cup\Sigma_3(W).

The sets FU,FWF_U,F_W and all translates x+Tx + T, x∈Bx \in B, are pairwise disjoint. Here is how (3.12) rules out the possible intersections.

  • An intersection of FUF_U and FWF_W gives either a four-term relation with C3C_3-sum 1 or −1-1, or a six-term relation with C3C_3-sum zero. The one-term sets themselves are disjoint.

  • An intersection of FUF_U with x+Tx + T gives, after cancellation, coordinates 0,1,−1,−10,1,-1,-1, or, without cancellation in the three-term case, 0,1,−1,−1,−1,−10,1,-1,-1,-1,-1. The sums are respectively nonzero for length four and zero for length six. A cancellation leaving only two terms is impossible because the projected classes are disjoint. The argument for FWF_W is symmetric.

  • If x+Tx + T and x′+Tx' + T meet with x≠x′x \ne x', cancellation leaves two terms from BB and two from one nonzero coordinate class, or two from each of the three classes. These are again forbidden relations of length four or six.

We also have

Σ3(B)∩(FU∪FW)=∅,T∩Σ4(B)=∅.(14)\Sigma_3(B) \cap(F_U \cup F_W) = \varnothing,\qquad T \cap\Sigma_4(B) = \varnothing. \tag*{(14)}

The first exclusion uses three terms from BB together with one or three from UU or WW; the second uses four from BB, one from UU and one from WW. Their C3C_3-sums are precisely those forbidden in (3.12). Disjointness of the translates also gives Σ2(T)∩Σ2(B)=∅\Sigma_2(T) \cap\Sigma_2(B) = \varnothing. Applying Lemma 3.6 with E=TE = T, and counting all the disjoint sets just described, yields

u+w+(u3)+(w3)+b∣T∣+Fb(TB)≤256.(15)u + w + \binom{u}{3} + \binom{w}{3} + b|T| + F_b(T_B) \leq256. \tag*{(15)}

Notice also that

(Σ2(U)∪Σ2(W))∩Σ2(B)=∅:(16)(\Sigma_2(U) \cup\Sigma_2(W)) \cap\Sigma_2(B) = \varnothing: \tag*{(16)}

both pair-sum sets on the left are contained in Σ2(T)\Sigma_2(T), by translating with one fixed point of the opposite nonempty class.

Step 2: the possible lengths. By (3.12), 0∉Σ6(B)0 \notin\Sigma_6(B), so b≤18b \le18. Together with u,w≤10u,w \le10 this gives

4≤b≤18,6≤u+w≤20.4 \le b \le18,\qquad6 \le u+w \le20.

For t∈Tt \in T, let rtr_t count its representations as u0+w0u_0+w_0. Two different representations determine a common element of Σ2(U)\Sigma_2(U) and Σ2(W)\Sigma_2(W). Conversely, each common pair sum gives exactly two unordered pairs of representations. Since the pair sums in each class are unique,

∑t(rt2)=2∣Σ2(U)∩Σ2(W)∣≤2(w2).\sum_t \binom{r_t}{2}=2|\Sigma_2(U)\cap\Sigma_2(W)|\le2\binom{w}{2}.

Using ∑trt=uw\sum_t r_t=uw, we obtain

∑trt2≤uw+2w(w−1)=w(u+2w−2).\sum_t r_t^2\le uw+2w(w-1)=w(u+2w-2).

Cauchy’s inequality now gives the single bound

∣T∣≥⌈u2wu+2w−2⌉.(17)|T|\ge\left\lceil\frac{u^2w}{u+2w-2}\right\rceil. \tag*{(17)}

Inserting it and Fb(TB)≥g(b)F_b(T_B)\ge g(b) into (3.14) shows that

L(u,w):=u+w+(u3)+(w3)+(24−u−w)⌈u2wu+2w−2⌉+g(24−u−w)≤256.L(u,w):=u+w+\binom{u}{3}+\binom{w}{3}+(24-u-w)\left\lceil\frac{u^2w}{u+2w-2}\right\rceil+g(24-u-w)\le256.

The following table gives every value in the range max⁡{w,6−w}≤u≤10\max\{w,6-w\}\le u\le10. A dash denotes a pair outside that range; the only values at most 256 are in bold.

w\uw\backslash u345678910
1——274297267297290331
2—286321284321318360376
3248282275307312346365416
4—240285272328340383408
5——240280301339368412
6———260306330368404
7————294328359404
8—————328368400
9——————368400
10———————404

Table 1.

Thus only u=w=3,4,5u=w=3,4,5 remain. Returning to the stronger inequality (3.14) gives

u=wu=wbb∣T∣≥|T|\geFb(TB)≤F_b(T_B)\leTBT_B
3184176d18d_{18}
4167128d16d_{16} or e8⊕e8e_8\oplus e_8
5141086d14d_{14}

Table 2.

The last column follows from Lemma 3.5.

Step 3: the two hyperplane configurations. If TB=e8⊕e8T_B=e_8\oplus e_8, take D=BD=B and use (3.1). If TB=d18T_B=d_{18}, its nine pair indices lie in the seven-dimensional quotient by their common direction. They therefore have a nonzero even relation. Its weight must be eight, since weights two, four and six were excluded above. The eight indices in that relation give a sixteen-point set DD.

For completeness, these eight indices have just the one nonzero even relation, namely their total sum. Their affine span has dimension six. Their one-index and three-index sums are all distinct and number 8+(83)=648+\binom{8}{3}=64, so they fill an affine six-space. Their two-index sums and four-index sums, together with zero, fill its direction space: there are (82)+(84)/2+1=64\binom{8}{2}+\binom{8}{4}/2+1=64 possibilities, with complementary four-subsets giving the same sum. Lifting back to VV gives

Σ3(D)=L,∣(L+L)∖Σ4(D)∣=1,\Sigma_3(D)=L,\qquad|(L+L)\setminus\Sigma_4(D)|=1,

where LL is an affine hyperplane. The missing element is the common pair direction; zero itself is the sum of two complete pairs. For e8⊕e8e_8\oplus e_8 the same conclusion holds with no missing element.

By (14), both UU and WW avoid LL. The complement of an affine hyperplane is its other coset, so U+W⊂L+LU+W\subset L+L. But T∩Σ4(D)=∅T\cap\Sigma_4(D)=\varnothing, whence ∣T∣≤1|T|\le1, contradicting the table above.

Step 4: seven parallel pairs. The remaining possibilities are d16d_{16} and d14d_{14}, with u=w=4u=w=4 or 55. Choose seven of their parallel pairs, with common direction dd, and let their affine span be LL. Translate all projected points so that 0∉L0\notin L. This preserves every condition concerning sums of four or six points. Project modulo ⟨d⟩\langle d\rangle and choose coordinates so that the seven pair indices are the seven unit vectors of F27\mathbb{F}_2^7. This is possible because the indices are affinely independent and their affine span does not contain zero.

The parallel-pair description shows that Σ3(B)\Sigma_3(B) contains both lifts of all words of weights one and three, and Σ4(B)\Sigma_4(B) contains both lifts of all words of weights two and four. Each of U,WU,W projects injectively: two points with the same projection differ by d∈Σ2(B)d\in\Sigma_2(B), contradicting (16). The same condition excludes a weight-two difference between two projected points of either class, since both lifts of any two-index sum belong to Σ2(B)\Sigma_2(B).

Separate each projected class into its even-weight and odd-weight words. An odd word of UU or WW has weight five or seven, since weights one and three are excluded by (14). Complementing all seven bits therefore makes the odd words into zero or two-element subsets. The two-element subsets in one class must be disjoint: an intersection in one point would give a weight-two difference. If the zero word occurs, no two-element subset can occur with it. Thus each class has at most three odd words.

Since each class has at least four points, each also has an even word. Fix an even word of the opposite class. Its difference with any even word of the first class has weight zero or six: weights two and four would place the sum in Σ4(B)\Sigma_4(B). There is at most one word of each of these two types. Indeed, two different weight-six words in seven coordinates differ in weight two, which is forbidden within a class. Hence each class has at most two even words, and therefore has odd words as well.

Finally, complementing two odd words, one from each class, does not change their difference. That difference has even weight at most four, so it must be zero, again because TT avoids Σ4(B)\Sigma_4(B). All cross-pairs of odd words are therefore equal; each odd part has at most one point. Each class would then have at most one odd and two even words, fewer than four. This is the required contradiction.

We have proved that one of U,WU,W is empty. Undo any negation of the C3C_3-coordinate. The adjoined term has coordinate −1-1, so the class with coordinate 11 must be empty. Translating back, every term of the original RR has coordinate 00 or 11; that is, R−1=1R_{-1}=1.

If a sequence satisfying the hypotheses of (R) had length at least 24, restrict to length 24. Every one of its terms lies in a subsequence of length 23 satisfying the same hypotheses. The conclusion just proved would give only coordinates 0,10,1 throughout, contradicting Lemma 3.8. This proves (R). □

The case of distinct binary coordinates

We now prove assertion (P). Suppose, to the contrary, that S∈F(Gk)S\in\mathcal{F}(G_k) has length 27, that π(S)\pi(S) is squarefree with 0∉supp⁡(π(S))0\notin\operatorname{supp}(\pi(S)), and that SS has no zero-sum subsequence. Retain the sets A=supp⁡(π(S))A=\operatorname{supp}(\pi(S)), B=supp⁡(π(S1))B=\operatorname{supp}(\pi(S_1)) and C=supp⁡(π(S−1))C=\operatorname{supp}(\pi(S_{-1})), of cardinalities a,b,ca,b,c, respectively. Proposition 3.7 gives 3≤a≤83\le a\le8 and b,c≤16b,c\le16; in particular, b,c≥3b,c\ge3.

We shall compare their intersections with cosets of three-dimensional subspaces. A coordinate subspace is a subspace H=⟨a1,a2,a3⟩H=\langle a_1,a_2,a_3\rangle generated by three independent elements of AA. For D⊂VD\subset V and q∈V/Hq\in V/H, write Dq=D∩qD_q=D\cap q, and put

hH(D)=max⁡q∈V/H∣Dq∣,νH(D)=∑q∈V/Hmin⁡{2,∣Dq∣}.h_H(D)=\max_{q\in V/H}|D_q|,\qquad \nu_H(D)=\sum_{q\in V/H}\min\{2,|D_q|\}.

Thus hH(D)h_H(D) is the maximum multiplicity of the image of the squarefree sequence DD in V/HV/H. The quantity νH(D)\nu_H(D) counts one for an intersection of size one and two for an intersection of size at least two. Empty intersections contribute zero.

Lemma 3.10. Let HH be a three-dimensional subspace and let D⊂VD \subset V satisfy 0∉Σ6(D)0 \notin\Sigma_6(D). At most two HH-cosets contain three or more elements of DD. Moreover,

∣D∣≤νH(D)+6,|D| \le\nu_H(D) + 6,

and the stronger bound ∣D∣≤νH(D)+5|D| \le\nu_H(D) + 5 holds unless DD contains an entire HH-coset.

Proof. Three elements in one coset give three pair sums, which are the nonzero elements of a plane in HH. If three cosets each contained at least three elements of DD, let these planes be P1P_1, P2P_2, P3P_3. We can choose nonzero δi∈Pi\delta_i \in P_i with δ1+δ2=δ3\delta_1 + \delta_2 = \delta_3. Indeed, if P1=P2P_1 = P_2, choose δ3∈(P1∩P3)∖{0}\delta_3 \in(P_1 \cap P_3) \setminus\{0\} and express it as a sum of the other two nonzero elements of P1P_1. Otherwise choose δ3∈P3∖(P1∩P2)\delta_3 \in P_3 \setminus(P_1 \cap P_2); it has a decomposition with nonzero summands in P1P_1 and P2P_2. The three corresponding pairs are disjoint and have total sum zero, contrary to 0∉Σ6(D)0 \notin\Sigma_6(D).

We also need to restrict the sizes of the two possible larger intersections. Any set of more than four elements in an HH-coset has every nonzero element of HH as a pair sum. For six elements XX in one coset, complementation therefore gives

Σ2(X)=H∖{0},Σ4(X)=H∖{σ(X)}.\Sigma_2(X) = H \setminus\{0\}, \qquad\Sigma_4(X) = H \setminus\{\sigma(X)\}.

Its four-term sums meet the pair sums of any other intersection of size at least three. Consequently, an intersection of size six excludes any other of size at least three. For seven elements, the six-element subsets have different sums, so their four-term sumsets together cover HH. An intersection of size seven, or eight, therefore excludes every other intersection of size at least two. Finally, two intersections of size five are impossible: the four-term sums of one meet the pair sums of the other.

An intersection of size s≥2s \ge2 contributes s−2s - 2 to ∣D∣−νH(D)|D| - \nu_H(D). The restrictions just proved leave a total of at most five, except that a full eight-element coset can contribute six. This proves both bounds. □

Lemma 3.11. Suppose that AA is independent and 3≤a≤83 \le a \le8. Set

Ra=2(34−a)−(a−32),σH=a1+a2+a3.R_a = 2(34-a) - \binom{a-3}{2}, \qquad\sigma_H = a_1 + a_2 + a_3.

If hH(B),hH(C)≤2h_H(B), h_H(C) \le2, and t,ut, u are the numbers of one-element intersections of B,CB, C, respectively, then

b(c+u)2≤bc+bu+ct−tu2≤Ra.(18)\frac{b(c+u)}{2} \le\frac{bc+bu+ct-tu}{2} \le R_a. \tag*{(18)}

If also bc>Rabc > R_a, then

dim⁡⟨Σ2(C)⟩≤c+u2≤Rab,(19)\dim\langle\Sigma_2(C)\rangle\le\frac{c+u}{2} \le\frac{R_a}{b}, \tag*{(19)}

and the analogous assertion holds with B,CB, C interchanged. If hH(B)≥3h_H(B) \ge3, then hH(C)=1h_H(C) = 1 and

cνH(B)≤Ra.(20)c\nu_H(B) \le R_a. \tag*{(20)}

Without assuming that AA is independent, the same conclusions hold with 2m2m in place of RaR_a whenever B+CB+C meets at most mm cosets of HH.

Proof. Every element of B+CB+C has a unique representation. Otherwise two different representations would give a zero-sum subsequence with two terms from S1S_1 and two from S−1S_{-1}. Consider the array (b+c)b∈B,c∈C(b+c)_{b\in B,c\in C}. Two entries in the same HH-coset and in different rows and columns must differ by σH\sigma_H. Every other difference in HH is a sum of at most two of a1,a2,a3a_1,a_2,a_3, and would complete those four terms to a short zero-sum subsequence.

This has two consequences. First, a 3×23 \times2 rectangle within one quotient coset is impossible: comparing its first entry with two entries in the other column would make those entries equal. Thus hH(B)≥3h_H(B) \ge3 forces hH(C)=1h_H(C) = 1. Second, if either BqB_q or CrC_r has size at least two, the sumset Bq+CrB_q + C_r is the only contribution to the quotient coset q+rq+r. An entry from another contribution would have to differ by σH\sigma_H from two distinct entries. If all contributions are from singleton intersections, at most two of them can occupy one quotient coset.

Assign a pair of nonempty intersections weight one if both are singletons, and weight two otherwise. The preceding paragraph shows that each quotient coset accommodates total weight at most two. Independence of AA gives more precise restrictions. The images of a4,…,aaa_4,\ldots,a_a are independent in V/HV/H, and B+CB+C avoids Σ≤40(A)\Sigma_{\leq4}^{0}(A). The resulting bounds are

quotient cosetnumber of such cosetsallowed weight
0 or ai+Ha_i+H (i≥4i\geq4)a−2a-20
ai+aj+Ha_i+a_j+H (4≤i<j≤a4\leq i<j\leq a)(a−32)\binom{a-3}{2}1
all remaining cosets34−a−(a−32)3^4-a-\binom{a-3}{2}2

In the first row, every element uses at most four elements of AA. In the second row, all elements except ai+aj+σHa_i+a_j+\sigma_H use at most four. In particular, that coset cannot contain a contribution of weight two. Summing the last column with these multiplicities gives RaR_a.

If b=2r+tb=2r+t and c=2s+uc=2s+u, counting the four types of pairs of intersections gives total weight

2rs+2ru+2ts+tu=bc+bu+ct−tu22rs+2ru+2ts+tu=\frac{bc+bu+ct-tu}{2}

Subtracting b(c+u)/2b(c+u)/2 leaves t(c−u)/2≥0t(c-u)/2\geq0, proving (18). If bc>Rabc>R_a, neither set can have only singleton intersections. Fix a two-element intersection of BB with pair sum dd. For every two-element intersection of CC, with pair sum ee, the array condition gives d+e=σHd+e=\sigma_H. All these pair sums ee are therefore equal. There are (c+u)/2(c+u)/2 nonempty intersections of CC. Their representatives have difference space of dimension at most (c+u)/2−1(c+u)/2-1; adjoining the common pair sum proves (19).

If hH(B)≥3h_H(B)\geq3, we have already proved hH(C)=1h_H(C)=1. Each element of CC contributes total weight νH(B)\nu_H(B), which proves (20). The argument with total capacity 2m2m uses only the universal weight bound two per coset, so it does not require independence of AA. □

Lemma 3.12. Suppose dim⁡⟨A⟩≥4\dim\langle A\rangle\geq4, and let D,ED,E be B,CB,C in either order, with ∣D∣=N|D|=N and ∣E∣=M|E|=M. Suppose that, for every coordinate subspace HH, the condition hH(D)≥3h_H(D)\geq3 implies MνH(D)≤RM\nu_H(D)\leq R, where RR is fixed. If (N−5)M>R(N-5)M>R, then hH(D)≤2h_H(D)\leq2 for every coordinate subspace HH.

In particular, when AA is independent, this conclusion holds if

(N−5)(27−a−N)>Ra.(21)(N-5)(27-a-N)>R_a. \tag*{(21)}

For 4≤a≤84\leq a\leq8, it holds throughout 10≤N≤min⁡{16,22−a}10\leq N\leq\min\{16,22-a\}.

Proof. Suppose hH(D)≥3h_H(D)\geq3. The strict inequality gives νH(D)≤N−6\nu_H(D)\leq N-6, so Lemma 3.10 forces DD to contain a full coset F=x+HF=x+H. Choose a4∈A∖Ha_4\in A\setminus H, and replace H=⟨a1,a2,a3⟩H=\langle a_1,a_2,a_3\rangle by H′=⟨a1,a2,a4⟩H'=\langle a_1,a_2,a_4\rangle. The set FF meets exactly two H′H'-cosets, in four elements each. Both cosets lie in the affine four-space F+H′F+H'.

There is no third H′H'-coset containing three elements of DD. Consequently, every element of DD outside F+H′F+H' contributes one to νH′(D)\nu_{H'}(D), while the two cosets inside it contribute four in total. Since hH′(D)≥3h_{H'}(D)\geq3, the same strict inequality gives νH′(D)≤N−6\nu_{H'}(D)\leq N-6. Therefore

∣D∩(F+H′)∣=N−(νH′(D)−4)≥10.|D\cap(F+H')|=N-(\nu_{H'}(D)-4)\geq10.

Choose ten of these elements, forming a set XX. Lemmas 3.4 and 3.5 give ∣Σ3(X)∣=r(TX)≥F10(TX)≥g(10)=20|\Sigma_3(X)|=r(T_X)\geq F_{10}(T_X)\geq g(10)=20. But all these sums belong to the same affine four-space, which has only 16 elements. This contradiction proves the first assertion.

For the stated range of NN, the left side of (21) minus RaR_a is a concave quadratic in NN. At the two endpoints its values are

aa45678
N=10N=1053223
N=min⁡{16,22−a}N=\min\{16,22-a\}179223

and hence it is positive throughout the interval. □

Lemma 3.13. If AA is independent and a=7a=7 or 88, then b,c≤15b,c\leq15.

Proof. By symmetry, suppose b=16b=16. Proposition 3.7 gives F16(TB)≤128F_{16}(T_B)\leq128, so Lemma 3.5 leaves TB=d16T_B=d_{16} or e8⊕e8e_8\oplus e_8. If TB=e8⊕e8T_B=e_8\oplus e_8, or if the eight pair indices for d16d_{16} are affinely dependent, the block sumset formulas give a hyperplane K⊂VK\subset V such that

Σ3(B)=V∖K,∣K∖Σ4(B)∣≤1.\Sigma_3(B)=V\setminus K,\qquad|K\setminus\Sigma_4(B)|\leq1.

In the dependent-index case, the only possible even relation among the eight indices involves all eight; the same formulas apply. Since AA avoids Σ3(B)\Sigma_3(B), we have A⊂KA\subset K, and thus a=7a=7 and c=4c=4. The set CC avoids Σ4(B)\Sigma_4(B), so it has at most one element in KK. It has at most two outside KK: three such elements have sum in V∖K=Σ3(B)V\setminus K=\Sigma_3(B), giving a zero-sum subsequence of length six. This contradicts c=4c=4.

We may therefore assume that BB consists of eight parallel pairs with common pair sum d≠0d\ne0, and that their indices modulo ⟨d⟩\langle d\rangle are affinely independent. In particular, BB affinely spans VV, and B+d=BB+d=B.

We first show that dd is a sum of at most two elements of AA. The following table gives the intersection sizes of two Hamming balls whose centers have distance t≥3t\geq3:

dimension, radiust=3,4t=3,4t=5,6t=5,6t≥7t\geq7
7 and 2600
8 and 338200

Table 6.

To check the table, translate one center to zero. If the other center has weight tt, a point with ii ones in those tt coordinates and jj elsewhere belongs to both radius-rr balls exactly when i+j≤ri+j\leq r and t−i+j≤rt-i+j\leq r. For example, at distance three the counts are 3+3=63+3=6 and 2+6(1+5)=382+6(1+5)=38, respectively.

The set B+CB+C is invariant under translation by dd and avoids Σ≤40(A)\Sigma_{\leq4}^0(A). If a=8a=8, complementation with respect to the basis AA sends its bc=48bc=48 elements into the radius-three ball. Translation invariance puts all of them in the intersection of two such balls whose centers differ by dd. Since 48>3848>38, the table gives wt⁡A(d)≤2\operatorname{wt}_A(d)\leq2.

If a=7a=7, put W=⟨A⟩W=\langle A\rangle. Were d∉Wd\notin W, the set B+CB+C would avoid both Σ≤40(A)\Sigma_{\leq4}^0(A) and its translate by dd. These are disjoint sets of size 1+7+(72)+(73)+(74)=991+7+\binom{7}{2}+\binom{7}{3}+\binom{7}{4}=99. Only 256−198=58256-198=58 elements would remain for the bc=64bc=64 distinct mixed sums, which is impossible. Thus d∈Wd\in W. Since BB affinely spans VV, it meets both WW-cosets; both intersections have positive even size because B+d=BB+d=B. Each element of CC consequently gives at least two mixed sums in WW, all distinct. Their number is at least 2c=82c=8. Complementation in the basis AA puts them in two radius-two balls in WW, again with centers differing by dd. Since 8>68>6, we obtain wt⁡A(d)≤2\operatorname{wt}_A(d)\leq2 in this case as well.

Set J=⟨Σ2(C)⟩J=\langle\Sigma_2(C)\rangle, so dim⁡J≤c−1\dim J\leq c-1. We can choose a coordinate subspace HH containing dd such that

σH+d∉J(22)\sigma_H+d\notin J \tag*{(22)}

Indeed, if d∈Ad\in A, the candidates for σH+d\sigma_H+d are the pair sums of the remaining elements of AA; their span has dimension a−2a-2. If dd is a sum of two elements of AA, the candidates are the remaining individual elements, again spanning dimension a−2a-2. In either case a−2>c−1a-2>c-1, so not all candidates lie in JJ.

Now hH(C)=1h_H(C)=1. Otherwise two elements of CC in the same HH-coset would have pair sum u∈Hu\in H, but the mixed-array condition, applied with a dd-pair of BB, would give u+d=σHu+d=\sigma_H, contrary to (3.21). Every nonempty BqB_q has even size. None is full, since four pair indices would then lie in an affine plane of V/⟨d⟩V/\langle d\rangle and would be affinely dependent. Lemma 3.10 therefore gives νH(B)≥11\nu_H(B)\geq11; this number is even, so it is at least 12. There are at least six nonempty intersections of BB, each of size at least two. Pairing them with the cc singleton intersections of CC requires at least 6c6c distinct quotient cosets, each with allowed weight two. The table in Lemma 3.11 provides only

34−a−(a−32)={21,a=7,16,a=8.34-a-\binom{a-3}{2} = \begin{cases} 21,&a=7,\\ 16,&a=8. \end{cases}

_久久爱 But 6c6c is 2424 or 1818, respectively. This final contradiction excludes b=16b = 16. □

Lemma 3.14

Lemma 3.14. Suppose hH(C)=1h_H(C) = 1 and c≥13c \ge13. Then every BqB_q has size at most four, at most two have size at least two, and at most one has size four. In particular,

b≤νH(B)+3,νH(B)≤3⟹b≤5.b \le\nu_H(B) + 3,\qquad\nu_H(B) \le3 \Longrightarrow b \le5.

Proof. We first prove an elementary fact: eleven elements of an affine four-space have two disjoint triples of each prescribed sum in that space. Translate the prescribed sum to zero and discard zero if it occurs. At least ten elements remain. A sum-free subset of F24\mathbb{F}_2^4 has size at most eight: it is disjoint from its translate by any of its elements. Hence there is a triple EE with σ(E)=0\sigma(E) = 0.

The plane P=⟨E⟩P = \langle E\rangle has P∖{0}=EP \setminus\{0\} = E. At least seven of the remaining elements lie outside PP. They occupy its three other cosets, each of size four, so two cosets contain at least three and at least two elements, respectively. The three elements in the first coset give all three possible nonzero pair sums in PP. We can therefore select one pair from each coset with different sums u,v∈Eu,v \in E. Adjoining uu to the first pair and vv to the second gives two disjoint zero-sum triples. Translating back proves the fact.

Let C‾\overline{C} be the image of CC in V/HV/H. Its at least twelve nonzero elements form a sum-free set. Indeed, a zero-sum triple in the quotient would lift to three elements of CC whose sum lies in HH; at most three elements of AA would complete them to a short zero-sum subsequence. The Davydov–Tombak result in [5 Fact 2] puts these nonzero elements in a nonzero coset LL of a hyperplane of V/HV/H. The set LL is an affine four-space.

Every q∈Lq \in L has two disjoint three-term representations from C‾∩L\overline{C} \cap L, by the preceding fact. Every q∈L+Lq \in L + L has two four-term representations sharing exactly one term: fix p∈C‾∩Lp \in\overline{C} \cap L, delete it, and apply the same fact to the at least eleven remaining elements with target q+p∈Lq + p \in L. In each case the two corresponding sums in VV are distinct. Equality would give six distinct elements of CC with sum zero.

For five elements XX of BB in one HH-coset, complementation of pairs gives ∣Σ3(X)∣=7|\Sigma_3(X)| = 7. If its quotient coset lies in LL, these seven sums must meet the two distinct corresponding sums from Σ3(C)\Sigma_3(C), which is impossible. For four elements XX of BB in one HH-coset, put U={0,a1,a2,a3}U = \{0,a_1,a_2,a_3\}. We have ∣X+U∣≥7|X + U| \ge7. Indeed, two missing elements would force XX to avoid two translates of UU. Two different translates of this simplex have union of size at least six, leaving room for at most two elements of XX, not four. If the quotient coset of XX lies outside LL, it lies in L+LL + L. The two distinct four-term sums from CC in that coset must then meet X+UX + U. This contradicts

Σ3(B)∩Σ3(C)=∅,Σ4(C)∩(B+U)=∅,\Sigma_3(B) \cap\Sigma_3(C) = \varnothing,\qquad\Sigma_4(C) \cap(B + U) = \varnothing,

which follow from the absence of short zero-sum subsequences. Thus all intersections of size four lie in LL, and none has size five or more.

Finally, suppose Bq,BrB_q,B_r are distinct intersections of size at least two and q+r∈L+Lq + r \in L + L. The translates q+(C‾∩L)q + (\overline{C} \cap L) and r+(C‾∩L)r + (\overline{C} \cap L) each have at least twelve elements in the same sixteen-element coset, so they must meet. This contradicts the exclusive-contribution property in Lemma 3.11. There is therefore at most one nonsingleton intersection in each of the two cosets of L+LL + L. There are at most two altogether, and at most one of size four. They contribute at most (4−2)+(3−2)=3(4 - 2) + (3 - 2) = 3 beyond νH(B)\nu_H(B). If νH(B)≤3\nu_H(B) \le3 and all intersections are singletons, then b=νH(B)≤3b = \nu_H(B) \le3. Otherwise there is one nonsingleton intersection and at most one further element; hence b≤4+1=5b \le4 + 1 = 5. □

Lemma 3.15

Lemma 3.15. Let W=⟨A⟩W = \langle A\rangle. If dim⁡J≤dim⁡W−3\dim J \le\dim W - 3, some coordinate subspace HH satisfies H∩J=0H \cap J = 0. Moreover, if H∩H′=0H \cap H' = 0 and νH(D),νH′(D)≤m\nu_H(D),\nu_{H'}(D) \le m, where m=3m = 3 or 44, then

∣D∣≤2m−3.(23)|D| \le2m - 3. \tag*{(23)}

Proof. The image of WW modulo JJ has dimension at least three. Choose three elements of AA with independent images; their span is the required HH.

For the second assertion, an HH-coset and an H′H'-coset meet in at most one element. If either quotient has all intersections of size at most two, then ∣D∣≤m≤2m−3|D| \le m \le2m - 3. Otherwise consider the HH-cosets. If two intersections have size at least two, they already contribute four to νH(D)\nu_H(D), so m=4m=4 and there are no others. Every H′H'-intersection then has size at most two, reducing to the preceding case.

The only remaining possibility is one intersection of size at least three and at most m−2m-2 other elements. The large intersection meets each H′H'-coset at most once. The other elements can create at most m−3m-3 elements in total beyond the first two in each H′H'-coset: for m=3m=3 there is only one other element, and for m=4m=4 there are at most two. Thus ∣D∣≤νH′(D)+(m−3)≤2m−3|D| \le\nu_{H'}(D) + (m-3) \le2m-3. □

Proof of (P). Interchange B,CB,C if necessary so that b≥cb \ge c.

First suppose that AA is dependent. Every nonempty relation among its elements has weight at least seven. Two independent relations, together with their sum, would have total weight at least 21, whereas every coordinate occurs zero or twice, giving total weight at most 2a≤162a \le16. Thus there is a unique nonzero relation, of weight seven or eight. Put W=⟨A⟩W=\langle A\rangle.

If a=8a=8, replacing a subset by its symmetric difference with this relation shows that every element of WW is a sum of at most four elements of AA. Hence W=Σ≤40(A)W=\Sigma_{\leq4}^{0}(A), and B+CB+C lies in the other WW-coset. If a=7a=7, then dim⁡W=6\dim W=6 and W=Σ≤30(A)W=\Sigma_{\leq3}^{0}(A). The images of B,CB,C in V/WV/W are disjoint, because B+CB+C avoids WW. Each image also misses a nonzero element of V/WV/W: representatives of all three nonzero elements would form a triple whose sum lies in WW, and at most three elements of AA would complete a short zero-sum subsequence.

In this latter case, a class meeting WW has at most two elements there and at most one in each other coset. Three elements in WW, or one in WW and two in another coset, would give the same forbidden type of triple. Since b,c≥4b,c \ge4, such a class must have intersection sizes 2,1,12,1,1. The other class would consist of sixteen elements in the sole remaining coset. Its triple sums would lie in a 64-element affine space, contrary to r(T)≥g(16)=112r(T) \ge g(16)=112. Thus neither class meets WW. Their disjoint supports among the three nonzero quotient elements then put B+CB+C in at most two WW-cosets.

For a=8a=8, one WW-coset contains sixteen cosets of a coordinate subspace. For a=7a=7, two WW-cosets contain 2⋅8=162\cdot8=16 such cosets. In both cases Lemma 3.11 therefore applies with total capacity 32 for every coordinate subspace. The permitted sizes give (b−5)c≥33(b-5)c \ge33 (the minimum is 44 when a=7a=7 and 33 when a=8a=8). Lemma 3.12 gives hH(B)≤2h_H(B) \le2 for every HH.

Suppose hH(C)≤2h_H(C) \le2 for some HH. Since bc≥48>32bc \ge48 > 32, the dimension bound gives dim⁡⟨Σ2(C)⟩≤⌊32/b⌋≤3\dim\langle\Sigma_2(C)\rangle\le\lfloor32/b\rfloor\le3. As dim⁡W≥6\dim W \ge6, Lemma 3.15 supplies a coordinate subspace transverse to this difference space. Its quotient map is injective on CC, so the mixed bound becomes bc≤32bc \le32, a contradiction. We conclude that hH(C)≥3h_H(C) \ge3 for every HH. The mixed bound now gives νH(C)≤⌊32/b⌋≤3\nu_H(C) \le\lfloor32/b\rfloor\le3.

Choose two coordinate subspaces H,H′H,H' with H∩H′=0H\cap H'=0, using six independent elements of AA. Relative to HH, the set CC lies in one intersection of size at least three and at most one additional element. The large intersection meets each H′H'-coset at most once; the additional element can only create an intersection of size two. This contradicts hH′(C)≥3h_{H'}(C) \ge3.

Now suppose that AA is independent. Lemma 3.13 excludes b=16b=16 for a≥7a \ge7. For a=8a=8, the possibility b=15,c=4b=15,c=4 is also excluded by packing:

256≥1+8+(82)+(83)+15⋅4+g(15)=93+60+112=265.256 \ge1+8+\binom{8}{2}+\binom{8}{3}+15\cdot4+g(15)=93+60+112=265.

It follows that c≥5c \ge5. For a≥4a \ge4, every class of size at least ten falls within the range of Lemma 3.12; its intersection with each coordinate coset therefore has size at most two.

If a=3a=3, the weighted bound cannot hold with hH(B),hH(C)≤2h_H(B),h_H(C) \le2. Indeed, b+c=24b+c=24 and 8≤b,c≤168 \le b,c \le16. For even b,cb,c, its minimum is bc/2≥64bc/2 \ge64; for odd b,cb,c, its minimum is (bc+23)/2≥79(bc+23)/2 \ge79. Both exceed R3=62R_3=62. Interchange B,CB,C so that hH(B)≥3h_H(B) \ge3; then hH(C)=1h_H(C)=1. Combining b≤νH(B)+6b \le\nu_H(B)+6 with cνH(B)≤62c\nu_H(B) \le62 gives

c(18−c)=c(b−6)≤62.c(18-c)=c(b-6)\le62.

Since 8≤c≤168 \le c \le16, this forces 14≤c≤1614 \le c \le16. Lemma 3.14 improves b≤νH(B)+6b \le\nu_H(B)+6 to b≤νH(B)+3b \le\nu_H(B)+3, giving the contradiction 62≥c(b−3)=c(21−c)≥8062 \ge c(b-3)=c(21-c) \ge80.

We may now assume 4≤a≤84 \le a \le8. Since b≥10b \ge10, we have hH(B)≤2h_H(B) \le2 for every coordinate subspace. Suppose first that hH(C)≤2h_H(C) \le2 for at least one HH, and set J=⟨Σ2(C)⟩J=\langle\Sigma_2(C)\rangle. The permitted sizes give bc≥70>Rabc \ge70 > R_a, so Lemma 3.11 gives dim⁡J≤Ra/b\dim J \le R_a/b. If dim⁡J≤a−3\dim J \le a - 3, a coordinate subspace transverse to JJ would have hH(C)=1h_H(C) = 1, and hence bc≤Rabc \le R_a, again impossible. Consequently

b(a−2)≤Ra.(24)b(a - 2) \le R_a. \tag*{(24)}

There is also a useful parity restriction. In (18), t≡b(mod2)t \equiv b \pmod{2} and u≡c(mod2)u \equiv c \pmod{2}. The expression is nondecreasing in each of t,ut,u, so its minimum is

P(b,c)=2⌈b/2⌉⌈c/2⌉−{1,b,c both odd,0,otherwise.P(b,c)=2\lceil b/2\rceil\lceil c/2\rceil- \begin{cases} 1, & b,c\text{ both odd},\\ 0, & \text{otherwise}. \end{cases}

The conditions P(b,c)≤RaP(b,c) \le R_a and (24) leave only two possibilities:

aaRaR_aconsequence
460b+c=23b+c=23 gives P(b,c)≥64P(b,c)\ge64
557(b,c)=(14,8)(b,c)=(14,8) or (16,6)(16,6)
653b≤13b\le13 gives P(b,c)≥56P(b,c)\ge56
748b≥10b\ge10 gives b(a−2)≥50b(a-2)\ge50
842b≥10b\ge10 gives b(a−2)≥60b(a-2)\ge60

Table 1 (PDF p. 17).

For completeness, at a=5a=5 the pairs with b=11,…,16b=11,\ldots,16 have parity costs 71, 60, 69, 56, 63, 48, respectively.

In either surviving case, hH(C)≥3h_H(C)\ge3 is impossible for any HH. It would force hH(B)=1h_H(B)=1. For (b,c)=(14,8)(b,c)=(14,8), we would then have νH(C)≤⌊57/14⌋=4\nu_H(C)\le\lfloor57/14\rfloor=4 and, by Lemma 3.14, c≤7c\le7. For (b,c)=(16,6)(b,c)=(16,6), we would have νH(C)≤3\nu_H(C)\le3 and the same lemma would give c≤5c\le5. Thus both classes have intersections of size at most two for every HH.

For (b,c)=(14,8)(b,c)=(14,8), inequality (18) reads 14u+8t−tu≤214u+8t-tu\le2. Since t,ut,u are even, it forces t=u=0t=u=0. For (b,c)=(16,6)(b,c)=(16,6), it reads 16u+6t−tu≤1816u+6t-tu\le18, forcing u=0u=0. Hence every nonempty intersection of the 14-element class in the first case, or of the 6-element class in the second, has size two. Their common pair sum dHd_H is nonzero and satisfies D+dH=DD+d_H=D for that class DD. Such a period is unique: two distinct nonzero periods would generate a four-element translation group, making ∣D∣|D| divisible by four, whereas ∣D∣|D| is 14 or 6. The same nonzero period must therefore belong to every coordinate subspace. Their intersection is zero, since AA is independent and a=5a=5. This contradiction excludes the possibility hH(C)≤2h_H(C)\le2 for any HH.

We have proved that hH(C)≥3h_H(C)\ge3 for every coordinate subspace. We finish by applying the same bounds twice. Lemma 3.12 gives c≤9c\le9, so b≥18−ab\ge18-a. For a=4,…,8a=4,\ldots,8, one has 5(18−a)>Ra5(18-a)>R_a; hence the mixed bound gives νH(C)≤4\nu_H(C)\le4 for every HH. If a=4,5a=4,5, then b≥13b\ge13 and hH(B)=1h_H(B)=1, so Lemma 3.14, with the classes interchanged, gives c≤7c\le7. If a≥6a\ge6, two disjoint coordinate subspaces and Lemma 3.15 give c≤5c\le5.

These improvements give b≥20−ab\ge20-a in the first case and b≥22−ab\ge22-a in the second. In either case 4b>Ra4b>R_a, so now νH(C)≤3\nu_H(C)\le3 for every HH. Repeat the preceding bounds. For a=4,5a=4,5, Lemma 3.14 gives c≤5c\le5, whereas b≤16b\le16 requires c=27−a−b≥11−a≥6c=27-a-b\ge11-a\ge6. For a≥6a\ge6, Lemma 3.15 gives c≤3c\le3, whereas we already know c≥5c\ge5. These final contradictions prove (P).

Acknowledgements

This work was supported by the National Natural Science Foundation of China (grant nos. 12371335 and 12271520).

References

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

Sino-French Institute of Nuclear Engineering and Technology, Sun Yat-Sen University, Guangzhou 510275, P.R. China Email address: [email protected]

References

  1. [1]P. Erdős, A. Ginzburg, and A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel Sect. F 10 (1961), 41–43.
  2. [2]W. D. Gao, On zero-sum subsequences of restricted size II, Discrete Math. 271 (2003), 51–59.DOI
  3. [3]W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: A survey, Expo. Math. 24 (2006), 337–369.DOI
  4. [4]B. Girard and W. A. Schmid, Direct zero-sum problems for certain groups of rank three, J. Number Theory 197 (2019), 297–316.DOI
  5. [5]D. J. Gryn­kiewicz and V. F. Lev, 1-saturating sets, caps, and doubling-critical sets in binary spaces, SIAM J. Discrete Math. 24 (2010), 169–190.DOI
  6. [6]V. Pless and N. J. A. Sloane, On the classification and enumeration of self-dual codes, J. Combin. Theory Ser. A 18 (1975), 313–335.DOI
  7. [7]C. Reiher, On Kemnitz’ conjecture concerning lattice-points in the plane, Ramanujan J. 13 (2007), 333–337.DOI
  8. [8]A. Sidorenko, On generalized Erdős–Ginzburg–Ziv constants for Z₂ᵈ, J. Combin. Theory Ser. A 174 (2020), Article 105254.

Paper details

vlnc:W_dv2j7n9d
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

Not recorded for this paper

View statement
Looking for related papers…
Contents