WorksMathematics
The equality fails for
Abstract
Let be a finite abelian group. The Erdős-Ginzburg-Ziv constant is the smallest positive integer such that every sequence over of length at least contains a zero-sum subsequence of length . The short zero-sum constant is defined similarly, with the requirement that the zero-sum subsequence is nonempty and has length at most . It is known that A conjecture proposed by W. Gao in 2003, which has been widely studied in zero-sum theory, predicts that for every nontrivial finite abelian group . In this paper, we prove that this conjecture fails for the group .
Introduction
Let be a finite abelian group, and let . A nonempty zero-sum subsequence is called short if its length is at most . The constant is the least integer such that every sequence over of length at least has a short zero-sum subsequence. The Erdős–Ginzburg–Ziv constant is defined in the same way, with the required length equal to ; 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 ; while holds trivially. For general groups, an elementary construction gives
Gao [2 Conjecture 2.3] conjectured that equality always holds in (1).
Several substantial classes of groups satisfy this equality. For , the exact formulas are
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 for every .
In this paper, we prove that this conjectured equality in (1) fails for the group as given in the following theorem.
Theorem 1.1. For , we have .
Notation and preliminaries
We follow the conventions of [3 Section 2]. The free abelian monoid over is denoted by . Its elements are sequences, written multiplicatively:
Here is the length, is the multiplicity of , is the support, and is the sum. The empty sequence is denoted by . We write when is a subsequence of ; its complementary subsequence is . 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 , put
Thus the empty subsequence is excluded from and . When it is to be included, we write
For a subset , these definitions refer to the squarefree sequence . In particular, consists of sums of distinct elements, whereas allows the two summands to coincide.
A sequence is zero-sumfree if .
The Davenport constant is the least integer such that every sequence over of length at least has a nonempty zero-sum subsequence.
A homomorphism is applied to sequences term by term. In particular, and . Translation also acts term by term: .
We identify with the vector space . Let be nonempty. Its even relation code is
The Hamming weight is the number of nonzero coordinates. Thus a word of weight in corresponds to a zero-sum subsequence of of length . The matrix with columns has rank , so
Let 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 means 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 ,
Consequently, if three nonzero words each have weight at least and are supported on coordinates, then . 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
and let and be the projections. We write the elements of as . For a sequence , let be its subsequence of all terms with -coordinate . Thus . Whenever is squarefree, we put
The sets are then pairwise disjoint. We use subsets of 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 of length 32 without a zero-sum subsequence of length 6.
Proof. Let be a basis of , and set
The only nonempty subset of having even cardinality and sum zero is itself. Indeed, a relation involving must involve every , and the point is then needed to make its cardinality even. Suppose that six distinct points of had sum zero. The points of 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 , a contradiction.
Now use , and take
If has length six and sum zero, its -coordinate forces all six terms to have coordinate or all six to have coordinate . Their first coordinates would be six distinct elements of summing to zero, which is impossible. Hence . This is the binary doubling construction of [8 Theorem 5.4]. □
For the upper bound, suppose that has no short zero-sum subsequence. Three elementary restrictions will be useful. First, . Otherwise ten of its projected terms have two independent binary relations . Every nonzero relation has weight at least seven, contradicting for . Second, , since . Third, has at most two pairwise disjoint subsequences of length two with . Such a has . Two disjoint such subsequences cannot have opposite sums in , 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 satisfy
(1) is squarefree, , and ;
(2) if , and , then ;
(3) if , and , then .
Then , and equality implies .
(P) Squarefree projections. If has length , is squarefree, and , then has a short zero-sum subsequence.
Lemma 3.2. Assertions (R) and (P) imply .
Proof. Suppose that and has no short zero-sum subsequence. If is squarefree and does not contain , assertion (P) applies. Otherwise choose as follows: take two terms with equal projection if such terms exist, and otherwise take one term projecting to zero. Thus and . Its -sum is nonzero. Applying the automorphism if necessary, assume .
Every subsequence whose projection is squarefree and avoids satisfies the hypotheses of (R). To see the only additional condition, let have projected sum zero and length three or four. Its -sum cannot be zero, since is short, and cannot be , since would be short and zero-sum. It must therefore be . The conditions for lengths five and six follow directly from the assumption on .
Suppose first that contains no two disjoint pairs of terms with equal projection. Delete the chosen subsequence . After also removing any remaining term projecting to zero, at least 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 , each with projected sum zero. Their -sums agree, and we may normalize both to . Put , so . There is no repeated projection in , since it would give a third disjoint pair. Nor can a term project to zero: according as , one of , , would be short and zero-sum. Assertion (R) therefore applies, and all terms of have -coordinate 0 or 1.
Let be the common projection of the terms of . If and , adjoining either term of to gives a sequence of length 24 satisfying (R), using as the deleted subsequence . If , the two terms of and the term of with projection give three possible pairs, each disjoint from . Their -sums must all be 1. Writing their coordinates as , the equations force , contrary to the conclusion for . Thus . The same argument applies to , yielding four terms projecting to zero, contrary to . □
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 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 satisfy . The code is a direct sum of unused coordinates and blocks of the following types:
, for : partition the coordinates into pairs, and take the unions of an even number of these pairs;
and : the even relation codes of a punctured affine three-space and a full affine three-space, respectively.
The pairs in a 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 is squarefree. Thus any two tetrads meet evenly. The decomposition theorem of Pless–Sloane [6 Theorem 6.5] gives precisely the stated blocks.
In , the union of any two coordinate pairs is a tetrad. Consequently the two pairs have the same sum; denote this sum by . The corresponding points are therefore pairs . An block, , supplies 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 consists of two blocks, written and , where have dimension three. Their direction spaces meet trivially: a common nonzero direction would give a tetrad meeting both blocks. Also , because the two affine spaces are disjoint. Hence
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 ; reversing the blocks gives . For four-term sums, selections of types , and give ; selections of types and give . These are exactly the sets in (3.1).
Second, let consist of pairs with common sum , and write for their distinct images in . 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 , 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 , record the indices used an odd number of times. Changing the chosen point at any such index changes the sum by . It follows that consists of both lifts of every one-index and three-index sum.
Similarly, 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 of the blocks above, let and be the numbers of cosets of represented by words of weight two and three, respectively. The component counts are
| length | |||
For disjoint components of lengths ,
If , then
Proof. For , 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 and cosets, respectively.
For , 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 , choose a point of the block. There are at least three pairs with sum ; at most one contains , 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 , and weight three has distributions . 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 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 , and conversely a common coset gives equal sums. All odd sums belong to the affine span of , proving (3.5). □
For a block code of length , let be the number of blocks and let be the number of unused coordinates. Define
and put except that . As usual, a binomial coefficient is zero when its upper argument is smaller than its lower argument. The subtractions in will account for overlaps between three-term sums and translates.
Lemma 3.5. For , one has . Moreover,
(1) forces ;
(2) forces or , with values 112 and 128, respectively;
(3) forces .
Every squarefree sequence over 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 . Replace each pair of unused coordinates formally by a block with counts . This is only a counting device. It increases by two and increases the subtracted quantity in by two, so is unchanged.
Next merge paired blocks of half-lengths into . Using (3.3) and (3.4), the decrease in is
Indeed, and . Thus repeated merging gives a lower bound for the original .
Call the sum of the blocks the exceptional core, and let its length, pair count and triple count be . Write . After merging, the remaining coordinates consist of one paired block and, when is odd, one unused coordinate. Applying the direct-sum formulas gives
For example, when , the paired block has counts , ; its subtraction of cancels the terms in the direct-sum formula. For odd , the same calculation uses . The cases follow directly as well.
An empty core gives . For one exceptional block, the excess is as follows:
| core | ||
Table 3.
Every entry is nonnegative except the last one at . That exception is , whose value is , explaining the definition of .
There can be at most two exceptional blocks, since . Their core counts, obtained from (3)–(4), are
| core | |||
| 14 | 63 | 114 | |
| 15 | 70 | 121 | |
| 16 | 78 | 128 |
Table 4.
In particular . For , we have and ; for , we have and ; for , we have . This proves ; 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 other than , the last merger has half-lengths and decreases by . Since , the resulting lower bounds at are 100, 154, 224. For nonempty cores, (3.6) gives the following table:
| core | |||
| 149 | 231 | 335 | |
| 100 | 168 | 258 | |
| 114 | 240 | 394 | |
| -- | 191 | 361 | |
| -- | 128 | 284 |
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
For a squarefree sequence in with this contradicts .
Lemma 3.6. Suppose satisfies , and let satisfy
Then
Proof. Put . If a sum of three distinct points of equals , with and , then that triple contains . Otherwise the four distinct -points would represent , contrary to . The other two points therefore form a pair representing .
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 . 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 or , an affine plane can be chosen through one endpoint and avoiding the other (and the missing point in the case), with the same consequence. Within , , 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 , there are three possible pair directions, but two of them cannot both belong to : their sum belongs to .
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 would then belong to .
Thus at most block directions can contribute to the overlap, each through at most choices of . At most unused pairs contribute, each through at most choices, since must avoid that pair. Subtracting these upper bounds from proves the claim. □
Proposition 3.7. Suppose has no short zero-sum subsequence, is squarefree, and . Use the classes , , and lengths , , defined above, and put . Then
If , then and .
Proof. All sums of at most three distinct points of , including the empty sum, are different: a collision gives a nonempty zero-sum subsequence of of length at most six. Thus there are such sums. Also has elements, because two different representations give a zero-sum subsequence with two terms of each nonzero -coordinate. The four sets
are pairwise disjoint: an intersection would again give a short zero-sum subsequence. For example, three terms from have -sum zero, as do three from . Lemma 3.6 applies with , and also with 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, . If , take a subsequence with and write its even class size as . Then . On the even class , and on the odd class , so expansion gives
For the six possible integers , the last product is nonnegative. This contradicts the first inequality and proves .
Now suppose . The preliminary bound and give . For these integers,
If , then and . Hence (3.7) implies
a contradiction. The same argument applies to .
It remains to exclude . The binary relation space of has dimension one: it is nonzero because , and two independent relations would give , 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 , a repeated sum comes from complementary parts of that word. There are at most 35 pairs of equal sums ( or ). Thus . This set is disjoint from , so . Since and , only remains. But then
the final contradiction. □
Lemma 3.8. Let satisfy the hypotheses of (R). If , then .
Proof. The hypotheses are inherited by subsequences, so it suffices to exclude . Let be the projected classes with -coordinates , of lengths . The preliminary bound and Lemma 3.5, which gives , imply . Put
The translates , for , are pairwise disjoint. Indeed, a collision between two translates gives two distinct points of together with one or two points of , having projected sum zero and -sum 2, contrary to (R). Also , because . Consequently
Let be the number of three-element subsets of whose sums belong to . Their sums are all different: two representations would give a nonempty zero-sum subsequence of of length at most six, forbidden by the hypotheses on . Every represented point of is unused in . Otherwise a tetrad through that point, combined with its representation by , gives three points of and two or three points of with total projected sum zero and -sum zero.
There cannot be eight unused coordinates of . Choose eight of them and any seven other coordinates, which exist because . Three-term selections supported on these fifteen coordinates give at least
distinct cosets of . 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 . Thus (3.9) contradicts . We have proved
We now count ordered zero-sum triples in ; write their number as . Their terms are distinct because . Each has a unique expression with , . In a zero-sum triple, the three -coordinates cannot all be distinct: together with the uncancelled -coordinates they would give a forbidden subsequence of of length between three and six and -sum zero. The three -coordinates are distinct as well. If two were equal, cancelling them and the repeated -coordinate would force a point of to belong to .
To bound from above, choose the pair of positions with equal -coordinates, their common value, and the ordered triple from . There are at most 3, and choices, respectively; the remaining -coordinate is then determined by the zero-sum condition. This may overcount, which is harmless. Hence
For the lower bound, fix the first term . The possible second terms form , and each determines the third. Since both sets have size in , . Thus
For , (3.8) gives , while . Together with (3.10), this gives , a contradiction.
Therefore and . As in the proof of Proposition 3.7, the sets and are disjoint. Hence . In particular , so Lemma 3.5 forces . There are no unused coordinates, hence . By (12), has size 126 and is sum-free, meaning that .
We use the Davydov–Tombak classification in the form recorded in [5 Fact 2]. A maximal sum-free subset of of size greater than is either a nonzero hyperplane coset or has size . Extend to a maximal sum-free set. Since , only the hyperplane-coset alternative is possible. As , the nine parallel pairs of 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 , the final contradiction. □
Proposition 3.9. Assertion (R) holds.
Proof. First let and assume the hypotheses of (R). Adjoin the term and translate every term by ; call the resulting sequence . Its projection is squarefree. For every with , we have
For a four-term subsequence not using the adjoined term, the translation subtracts from its original -sum 1. If it uses the adjoined term, the other three terms originally had -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 be the projected classes with -coordinates , and put . They are pairwise disjoint and . Suppose, towards a contradiction, that . The conditions (3.12) are invariant under the automorphism , so we may assume .
Step 1: disjoint sumsets. Neither nor has a zero-sum subsequence of length four or six: four equal nonzero -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 . Eleven points in have at least two independent even relations, and the three nonzero words they generate would each have weight at least eight, contradicting .
Put
The sets and all translates , , are pairwise disjoint. Here is how (3.12) rules out the possible intersections.
An intersection of and gives either a four-term relation with -sum 1 or , or a six-term relation with -sum zero. The one-term sets themselves are disjoint.
An intersection of with gives, after cancellation, coordinates , or, without cancellation in the three-term case, . 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 is symmetric.
If and meet with , cancellation leaves two terms from 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
The first exclusion uses three terms from together with one or three from or ; the second uses four from , one from and one from . Their -sums are precisely those forbidden in (3.12). Disjointness of the translates also gives . Applying Lemma 3.6 with , and counting all the disjoint sets just described, yields
Notice also that
both pair-sum sets on the left are contained in , by translating with one fixed point of the opposite nonempty class.
Step 2: the possible lengths. By (3.12), , so . Together with this gives
For , let count its representations as . Two different representations determine a common element of and . Conversely, each common pair sum gives exactly two unordered pairs of representations. Since the pair sums in each class are unique,
Using , we obtain
Cauchy’s inequality now gives the single bound
Inserting it and into (3.14) shows that
The following table gives every value in the range . A dash denotes a pair outside that range; the only values at most 256 are in bold.
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | — | — | 274 | 297 | 267 | 297 | 290 | 331 |
| 2 | — | 286 | 321 | 284 | 321 | 318 | 360 | 376 |
| 3 | 248 | 282 | 275 | 307 | 312 | 346 | 365 | 416 |
| 4 | — | 240 | 285 | 272 | 328 | 340 | 383 | 408 |
| 5 | — | — | 240 | 280 | 301 | 339 | 368 | 412 |
| 6 | — | — | — | 260 | 306 | 330 | 368 | 404 |
| 7 | — | — | — | — | 294 | 328 | 359 | 404 |
| 8 | — | — | — | — | — | 328 | 368 | 400 |
| 9 | — | — | — | — | — | — | 368 | 400 |
| 10 | — | — | — | — | — | — | — | 404 |
Table 1.
Thus only remain. Returning to the stronger inequality (3.14) gives
| 3 | 18 | 4 | 176 | |
| 4 | 16 | 7 | 128 | or |
| 5 | 14 | 10 | 86 |
Table 2.
The last column follows from Lemma 3.5.
Step 3: the two hyperplane configurations. If , take and use (3.1). If , 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 .
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 , so they fill an affine six-space. Their two-index sums and four-index sums, together with zero, fill its direction space: there are possibilities, with complementary four-subsets giving the same sum. Lifting back to gives
where is an affine hyperplane. The missing element is the common pair direction; zero itself is the sum of two complete pairs. For the same conclusion holds with no missing element.
By (14), both and avoid . The complement of an affine hyperplane is its other coset, so . But , whence , contradicting the table above.
Step 4: seven parallel pairs. The remaining possibilities are and , with or . Choose seven of their parallel pairs, with common direction , and let their affine span be . Translate all projected points so that . This preserves every condition concerning sums of four or six points. Project modulo and choose coordinates so that the seven pair indices are the seven unit vectors of . This is possible because the indices are affinely independent and their affine span does not contain zero.
The parallel-pair description shows that contains both lifts of all words of weights one and three, and contains both lifts of all words of weights two and four. Each of projects injectively: two points with the same projection differ by , 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 .
Separate each projected class into its even-weight and odd-weight words. An odd word of or 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 . 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 avoids . 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 is empty. Undo any negation of the -coordinate. The adjoined term has coordinate , so the class with coordinate must be empty. Translating back, every term of the original has coordinate or ; that is, .
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 throughout, contradicting Lemma 3.8. This proves (R). □
The case of distinct binary coordinates
We now prove assertion (P). Suppose, to the contrary, that has length 27, that is squarefree with , and that has no zero-sum subsequence. Retain the sets , and , of cardinalities , respectively. Proposition 3.7 gives and ; in particular, .
We shall compare their intersections with cosets of three-dimensional subspaces. A coordinate subspace is a subspace generated by three independent elements of . For and , write , and put
Thus is the maximum multiplicity of the image of the squarefree sequence in . The quantity 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 be a three-dimensional subspace and let satisfy . At most two -cosets contain three or more elements of . Moreover,
and the stronger bound holds unless contains an entire -coset.
Proof. Three elements in one coset give three pair sums, which are the nonzero elements of a plane in . If three cosets each contained at least three elements of , let these planes be , , . We can choose nonzero with . Indeed, if , choose and express it as a sum of the other two nonzero elements of . Otherwise choose ; it has a decomposition with nonzero summands in and . The three corresponding pairs are disjoint and have total sum zero, contrary to .
We also need to restrict the sizes of the two possible larger intersections. Any set of more than four elements in an -coset has every nonzero element of as a pair sum. For six elements in one coset, complementation therefore gives
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 . 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 contributes to . 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 is independent and . Set
If , and are the numbers of one-element intersections of , respectively, then
If also , then
and the analogous assertion holds with interchanged. If , then and
Without assuming that is independent, the same conclusions hold with in place of whenever meets at most cosets of .
Proof. Every element of has a unique representation. Otherwise two different representations would give a zero-sum subsequence with two terms from and two from . Consider the array . Two entries in the same -coset and in different rows and columns must differ by . Every other difference in is a sum of at most two of , and would complete those four terms to a short zero-sum subsequence.
This has two consequences. First, a rectangle within one quotient coset is impossible: comparing its first entry with two entries in the other column would make those entries equal. Thus forces . Second, if either or has size at least two, the sumset is the only contribution to the quotient coset . An entry from another contribution would have to differ by 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 gives more precise restrictions. The images of are independent in , and avoids . The resulting bounds are
| quotient coset | number of such cosets | allowed weight |
| 0 or () | 0 | |
| () | 1 | |
| all remaining cosets | 2 |
In the first row, every element uses at most four elements of . In the second row, all elements except use at most four. In particular, that coset cannot contain a contribution of weight two. Summing the last column with these multiplicities gives .
If and , counting the four types of pairs of intersections gives total weight
Subtracting leaves , proving (18). If , neither set can have only singleton intersections. Fix a two-element intersection of with pair sum . For every two-element intersection of , with pair sum , the array condition gives . All these pair sums are therefore equal. There are nonempty intersections of . Their representatives have difference space of dimension at most ; adjoining the common pair sum proves (19).
If , we have already proved . Each element of contributes total weight , which proves (20). The argument with total capacity uses only the universal weight bound two per coset, so it does not require independence of . □
Lemma 3.12. Suppose , and let be in either order, with and . Suppose that, for every coordinate subspace , the condition implies , where is fixed. If , then for every coordinate subspace .
In particular, when is independent, this conclusion holds if
For , it holds throughout .
Proof. Suppose . The strict inequality gives , so Lemma 3.10 forces to contain a full coset . Choose , and replace by . The set meets exactly two -cosets, in four elements each. Both cosets lie in the affine four-space .
There is no third -coset containing three elements of . Consequently, every element of outside contributes one to , while the two cosets inside it contribute four in total. Since , the same strict inequality gives . Therefore
Choose ten of these elements, forming a set . Lemmas 3.4 and 3.5 give . 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 , the left side of (21) minus is a concave quadratic in . At the two endpoints its values are
| 4 | 5 | 6 | 7 | 8 | |
| 5 | 3 | 2 | 2 | 3 | |
| 17 | 9 | 2 | 2 | 3 |
and hence it is positive throughout the interval. □
Lemma 3.13. If is independent and or , then .
Proof. By symmetry, suppose . Proposition 3.7 gives , so Lemma 3.5 leaves or . If , or if the eight pair indices for are affinely dependent, the block sumset formulas give a hyperplane such that
In the dependent-index case, the only possible even relation among the eight indices involves all eight; the same formulas apply. Since avoids , we have , and thus and . The set avoids , so it has at most one element in . It has at most two outside : three such elements have sum in , giving a zero-sum subsequence of length six. This contradicts .
We may therefore assume that consists of eight parallel pairs with common pair sum , and that their indices modulo are affinely independent. In particular, affinely spans , and .
We first show that is a sum of at most two elements of . The following table gives the intersection sizes of two Hamming balls whose centers have distance :
| dimension, radius | |||
| 7 and 2 | 6 | 0 | 0 |
| 8 and 3 | 38 | 20 | 0 |
Table 6.
To check the table, translate one center to zero. If the other center has weight , a point with ones in those coordinates and elsewhere belongs to both radius- balls exactly when and . For example, at distance three the counts are and , respectively.
The set is invariant under translation by and avoids . If , complementation with respect to the basis sends its elements into the radius-three ball. Translation invariance puts all of them in the intersection of two such balls whose centers differ by . Since , the table gives .
If , put . Were , the set would avoid both and its translate by . These are disjoint sets of size . Only elements would remain for the distinct mixed sums, which is impossible. Thus . Since affinely spans , it meets both -cosets; both intersections have positive even size because . Each element of consequently gives at least two mixed sums in , all distinct. Their number is at least . Complementation in the basis puts them in two radius-two balls in , again with centers differing by . Since , we obtain in this case as well.
Set , so . We can choose a coordinate subspace containing such that
Indeed, if , the candidates for are the pair sums of the remaining elements of ; their span has dimension . If is a sum of two elements of , the candidates are the remaining individual elements, again spanning dimension . In either case , so not all candidates lie in .
Now . Otherwise two elements of in the same -coset would have pair sum , but the mixed-array condition, applied with a -pair of , would give , contrary to (3.21). Every nonempty has even size. None is full, since four pair indices would then lie in an affine plane of and would be affinely dependent. Lemma 3.10 therefore gives ; this number is even, so it is at least 12. There are at least six nonempty intersections of , each of size at least two. Pairing them with the singleton intersections of requires at least distinct quotient cosets, each with allowed weight two. The table in Lemma 3.11 provides only
_久久爱 But is or , respectively. This final contradiction excludes . □
Lemma 3.14
Lemma 3.14. Suppose and . Then every has size at most four, at most two have size at least two, and at most one has size four. In particular,
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 has size at most eight: it is disjoint from its translate by any of its elements. Hence there is a triple with .
The plane has . At least seven of the remaining elements lie outside . 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 . We can therefore select one pair from each coset with different sums . Adjoining to the first pair and to the second gives two disjoint zero-sum triples. Translating back proves the fact.
Let be the image of in . 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 whose sum lies in ; at most three elements of 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 of a hyperplane of . The set is an affine four-space.
Every has two disjoint three-term representations from , by the preceding fact. Every has two four-term representations sharing exactly one term: fix , delete it, and apply the same fact to the at least eleven remaining elements with target . In each case the two corresponding sums in are distinct. Equality would give six distinct elements of with sum zero.
For five elements of in one -coset, complementation of pairs gives . If its quotient coset lies in , these seven sums must meet the two distinct corresponding sums from , which is impossible. For four elements of in one -coset, put . We have . Indeed, two missing elements would force to avoid two translates of . Two different translates of this simplex have union of size at least six, leaving room for at most two elements of , not four. If the quotient coset of lies outside , it lies in . The two distinct four-term sums from in that coset must then meet . This contradicts
which follow from the absence of short zero-sum subsequences. Thus all intersections of size four lie in , and none has size five or more.
Finally, suppose are distinct intersections of size at least two and . The translates and 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 . There are at most two altogether, and at most one of size four. They contribute at most beyond . If and all intersections are singletons, then . Otherwise there is one nonsingleton intersection and at most one further element; hence . □
Lemma 3.15
Lemma 3.15. Let . If , some coordinate subspace satisfies . Moreover, if and , where or , then
Proof. The image of modulo has dimension at least three. Choose three elements of with independent images; their span is the required .
For the second assertion, an -coset and an -coset meet in at most one element. If either quotient has all intersections of size at most two, then . Otherwise consider the -cosets. If two intersections have size at least two, they already contribute four to , so and there are no others. Every -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 other elements. The large intersection meets each -coset at most once. The other elements can create at most elements in total beyond the first two in each -coset: for there is only one other element, and for there are at most two. Thus . □
Proof of (P). Interchange if necessary so that .
First suppose that 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 . Thus there is a unique nonzero relation, of weight seven or eight. Put .
If , replacing a subset by its symmetric difference with this relation shows that every element of is a sum of at most four elements of . Hence , and lies in the other -coset. If , then and . The images of in are disjoint, because avoids . Each image also misses a nonzero element of : representatives of all three nonzero elements would form a triple whose sum lies in , and at most three elements of would complete a short zero-sum subsequence.
In this latter case, a class meeting has at most two elements there and at most one in each other coset. Three elements in , or one in and two in another coset, would give the same forbidden type of triple. Since , such a class must have intersection sizes . 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 . Thus neither class meets . Their disjoint supports among the three nonzero quotient elements then put in at most two -cosets.
For , one -coset contains sixteen cosets of a coordinate subspace. For , two -cosets contain such cosets. In both cases Lemma 3.11 therefore applies with total capacity 32 for every coordinate subspace. The permitted sizes give (the minimum is 44 when and 33 when ). Lemma 3.12 gives for every .
Suppose for some . Since , the dimension bound gives . As , Lemma 3.15 supplies a coordinate subspace transverse to this difference space. Its quotient map is injective on , so the mixed bound becomes , a contradiction. We conclude that for every . The mixed bound now gives .
Choose two coordinate subspaces with , using six independent elements of . Relative to , the set lies in one intersection of size at least three and at most one additional element. The large intersection meets each -coset at most once; the additional element can only create an intersection of size two. This contradicts .
Now suppose that is independent. Lemma 3.13 excludes for . For , the possibility is also excluded by packing:
It follows that . For , 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 , the weighted bound cannot hold with . Indeed, and . For even , its minimum is ; for odd , its minimum is . Both exceed . Interchange so that ; then . Combining with gives
Since , this forces . Lemma 3.14 improves to , giving the contradiction .
We may now assume . Since , we have for every coordinate subspace. Suppose first that for at least one , and set . The permitted sizes give , so Lemma 3.11 gives . If , a coordinate subspace transverse to would have , and hence , again impossible. Consequently
There is also a useful parity restriction. In (18), and . The expression is nondecreasing in each of , so its minimum is
The conditions and (24) leave only two possibilities:
| consequence | ||
| 4 | 60 | gives |
| 5 | 57 | or |
| 6 | 53 | gives |
| 7 | 48 | gives |
| 8 | 42 | gives |
Table 1 (PDF p. 17).
For completeness, at the pairs with have parity costs 71, 60, 69, 56, 63, 48, respectively.
In either surviving case, is impossible for any . It would force . For , we would then have and, by Lemma 3.14, . For , we would have and the same lemma would give . Thus both classes have intersections of size at most two for every .
For , inequality (18) reads . Since are even, it forces . For , it reads , forcing . 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 is nonzero and satisfies for that class . Such a period is unique: two distinct nonzero periods would generate a four-element translation group, making divisible by four, whereas is 14 or 6. The same nonzero period must therefore belong to every coordinate subspace. Their intersection is zero, since is independent and . This contradiction excludes the possibility for any .
We have proved that for every coordinate subspace. We finish by applying the same bounds twice. Lemma 3.12 gives , so . For , one has ; hence the mixed bound gives for every . If , then and , so Lemma 3.14, with the classes interchanged, gives . If , two disjoint coordinate subspaces and Lemma 3.15 give .
These improvements give in the first case and in the second. In either case , so now for every . Repeat the preceding bounds. For , Lemma 3.14 gives , whereas requires . For , Lemma 3.15 gives , whereas we already know . 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]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]W. D. Gao, On zero-sum subsequences of restricted size II, Discrete Math. 271 (2003), 51–59.DOI
- [3]W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: A survey, Expo. Math. 24 (2006), 337–369.DOI
- [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]D. J. Grynkiewicz 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]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]C. Reiher, On Kemnitz’ conjecture concerning lattice-points in the plane, Ramanujan J. 13 (2007), 333–337.DOI
- [8]A. Sidorenko, On generalized Erdős–Ginzburg–Ziv constants for Z₂ᵈ, J. Combin. Theory Ser. A 174 (2020), Article 105254.