GENERATING BINARY SPACES

VSEVOLOD F. LEV

Abstract. Let r and ρ be integers satisfying r ≥ ρ ≥ 3, and let 𝔽_{2}^{r} denote the elementary 2-group of rank r. We show that the maximum possible cardinality of a generating subset A ⊆ 𝔽_{2}^{r}, such that not all elements of 𝔽 r_{2} are representable as a sum of fewer than ρ elements of A, is (ρ + 1) 2^{r−ρ}. This proves a conjecture of Zemor and solves a well-known problem, related to covering radii of linear binary codes.

Indeed, we give a full description of all those generating subsets A ⊆ 𝔽_{2}^{r} of cardinality |A| > (ρ + 5) 2^{r−ρ−1} such that not all elements of 𝔽_{2}^{r} are representable as a sum of fewer than ρ elements of A.

1. Summary of results

For a positive integer r, denote by 𝔽_{2}^{r} the elementary abelian 2-group of rank r. We identify this group with the r-dimensional vector space over the field 𝔽_{2}; this allows us to speak about linear dependence, bases, spans, etc.

Given a positive integer k and a subset A ⊆ 𝔽_{2}^{r} we write

kA := {a_{1} + ⋯ + a_{k}: a_{1}, …, a_{k} ∈ A},

the set of all elements of 𝔽_{2}^{r} representable as a sum of k (not necessarily distinct) elements of A.

Suppose that an integer ρ ≥ 2 is fixed. If A ⊆ 𝔽_{2}^{r} is contained in a proper coset (that is, in a coset of a subgroup H ≨ G) then the set (ρ − 1)A is contained in a proper coset, too, and consequently (ρ − 1)A ≠ 𝔽_{2}^{r}. How large can A be given that it is not contained in a proper coset, and yet (ρ − 1)A ≠ 𝔽_{2}^{r}? We set

s_{ρ}(𝔽_{2}^{r}) := max{|A|: A ⊆ 𝔽_{2}^{r} is not contained in a proper coset and (ρ − 1)A ≠ 𝔽_{2}^{r}}.

In fact it is possible that any subset A ⊆ 𝔽_{2}^{r}, not contained in a proper coset, satisfies (ρ − 1)A = 𝔽_{2}^{r}; to extend our definition onto this case we agree that max ∅ = 0.

Observe that the condition (ρ − 1)A ≠ 𝔽_{2}^{r} has plain interpretation in generation terms: it means that there are elements of 𝔽_{2}^{r}, not representable as a sum of fewer than ρ elements of A.

1991 Mathematics Subject Classification. Primary: 11B75; Secondary: 20K01, 20D60, 94B65, 11P99.

2 VSEVOLOD F. LEV

The quantity s_{ρ}(𝔽_{2}^{r}) was introduced by Zemor^{1} in [Z92a] and then studied by a number of authors; see [Z92b, CHLL97, CZ99].

It is not difficult to verify that s_{ρ}(𝔽_{2}^{r}) = 0 for r < ρ; see Corollary 1 below. Also, s_{2}(𝔽_{2}^{r}) = 2^{r} − 1 for r ≥ 2 (this is immediate from the definition) and s_{3}(𝔽_{2}^{r}) = 2^{r−1} for r ≥ 3 (see Lemma 1). Zemor has shown that

s_{4}(𝔽_{2}^{r}) < 2^{r}/3, s_{ρ}(𝔽_{2}^{r}) ≤ 2^{r−ρ+1+⌊log_{2} ρ⌋} (ρ ≥ 5),

and on the other hand

s_{ρ}(𝔽_{2}^{r}) ≥ (ρ + 1) 2^{r−ρ}  (1)

for r ≥ ρ ≥ 3.

To establish (1), Zemor introduces sets which he calls cylindrical.

Example 1 (Zemor’s cylindrical sets). Fix a subgroup H < 𝔽_{2}^{r} of index [𝔽_{2}^{r} : H] = 2^{ρ} and choose e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} so that 𝔽_{2}^{r} = ⟨e_{1}, …, e_{ρ}⟩⊕H. Let A := {0, e_{1}, …, e_{ρ}}+H. Then e_{1} +⋯+e_{ρ} ∉ (ρ−1)A, and A is not contained in a proper coset since ρA = 𝔽_{2}^{r}. Thus s_{ρ}(𝔽_{2}^{r}) ≥ |A| = (ρ + 1) 2^{r−ρ}.

Indeed, Zemor conjectured that in fact equality holds in (1), and our first goal is to prove this conjecture.

Theorem 1 (Conjectured by Zemor). For any integers r and ρ such that r ≥ ρ ≥ 3 we have

s_{ρ}(𝔽_{2}^{r}) = (ρ + 1) 2^{r−ρ}.

In fact, we go considerably beyond this showing that any “large” A ⊆ 𝔽_{2}^{r}, not contained in a proper coset and such that (ρ − 1)A ≠ 𝔽_{2}^{r}, is a subset of a translated cylindrical set.

Theorem 2. Let r and ρ be integers such that r ≥ ρ ≥ 4. Suppose that A ⊆ 𝔽_{2}^{r} is not contained in a proper coset and satisfies (ρ − 1)A ≠ 𝔽_{2}^{r}. If |A| > (ρ + 5) 2^{r−ρ−1} then there exist a subgroup H < 𝔽_{2}^{r} of index [𝔽_{2}^{r} : H] = 2^{ρ} and elements g, e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} such that 𝔽_{2}^{r} = ⟨e_{1}, …, e_{ρ}⟩ ⊕ H and A ⊆ g + {0, e_{1}, …, e_{ρ}} + H. Moreover, if 0 ∈ A then g = 0 can be chosen.

We show in Section 4 (Example 2) that the bound (ρ + 5) 2^{r−ρ−1} is best possible: there are sets A ⊆ 𝔽_{2}^{r} of cardinality |A| = (ρ + 5) 2^{r−ρ−1}, satisfying (ρ − 1)A ≠ 𝔽_{2}^{r}, and contained neither in a proper coset nor in a translated cylindrical set.

1 In fact, Zemor considers a slightly different quantity which he denotes s_{𝔽 r_{2}}(t). It is easily verified, however, that s_{𝔽 r_{2}}(t) = s_{t+1}(𝔽 r_{2}) + 1 and s_{ρ}(𝔽 r_{2}) = s_{𝔽 r_{2}}(ρ − 1) − 1.

GENERATING BINARY SPACES 3

As indicated above, the case ρ = 3 of Theorem 1 is easy, and we include it mainly for the sake of completeness. For ρ = 4 the assertions of Theorems 1 and 2 follow from a basic result of Davydov and Tombak [DT89, Theorem 1], well-known to coding theorists and specialists in finite geometries. In addition, Theorem 1 for ρ = 4 was independently re-established in [CP92]. The result of Davydov and Tombak and its connections with the case ρ = 4 of Theorems 1 and 2 are discussed in Section 4.

Evidently, for ρ ≥ 4 Theorem 1 is an immediate corollary of Theorem 2; the latter theorem is proved in Section 6, and formally there is no need in a separate proof of the former. Nevertheless, we present such a separate independent proof of Theorem 1 in Section 5: firstly because of its striking simplicity, and secondly to introduce an idea which plays an important role in our subsequent argument.

In Section 2 we put our results into a broader algebraic context relating them to the problems area studied in [KL], a recent joint paper of Benjamin Klopsch and the present author. In particular, an alternative definition of s_{ρ}(𝔽_{2}^{r}) in terms of generating subsets (rather than subsets, not contained in a proper coset) is presented.

In Section 3 we give a coding theory interpretation of Theorems 1 and 2 and use it to answer a classical question concerning covering radii of linear binary codes.

Finally, in Section 7 we discuss a deep underlying problem and formulate a conjecture, towards the proof of which we were able to make a very modest progress only. The conjecture is, in fact, a strengthening of Theorems 1 and 2; in a sense, it establishes the structure of all subsets A ⊆ 𝔽_{2}^{r}, not contained in a proper coset, satisfying (ρ − 1)A ≠ 𝔽_{2}^{r}, and such that |A| ≥ 2^{r−ρ+2} + ρ − 2. Our conjecture can be considered as an extension of the result of Davydov and Tombak; indeed, for ρ = 4 the former reduces to the latter.

2. The algebraic perspective

The sole aim of this section is to explain how our results fit into a more general algebraic framework and to present our vision of the Big Picture.

Let G be a finite abelian group and let A be a subset of G. The subgroup generated by A is ⟨A⟩ := ⋂ {H ≤ G: A ⊆ H}, the intersection of all subgroups containing A. This is the smallest subgroup of G lying above A. If ⟨A⟩ = G then A is said to be generating; thus A is generating if and only if it is not contained in any proper subgroup of G.

Clearly, if A is not contained in a proper coset of G, then A is generating; conversely, if A is generating, then A ∪ {0} is not contained in a proper coset of G. In particular, if 0 ∈ A then for A to be generating it is necessary and sufficient that A is not contained in a proper coset.

4 VSEVOLOD F. LEV

Let A^{±} := (−A) ∪ {0} ∪ A denote the “symmetric closure of A with respect to addition”. Then ⟨A⟩ consists of all those g ∈ G representable as a sum of elements of A^{±}, and for every positive integer k we define ⟨A⟩_{k} := kA^{±}, the set of all g ∈ G representable as a sum of k elements of A^{±}. Evidently, these sets form an ascending chain ⟨A⟩_{1} ⊆ ⟨A⟩_{2} ⊆ …, and their union is ⟨A⟩, the subgroup generated by A.

Suppose that ρ ≥ 2 is an integer. If A ⊆ G is contained in a proper subgroup, then ⟨A⟩_{ρ−1} is contained in this subgroup, too, and consequently ⟨A⟩_{ρ−1} ≠ G. How large can |A| be given that A ⊆ G is generating, and yet ⟨A⟩_{ρ−1} ≠ G? We put

s_{ρ}(G) := max{|A|: A ⊆ G, ⟨A⟩_{ρ−1} ≠ ⟨A⟩ = G},

the maximum cardinality of a generating subset A ⊆ G such that there are elements of G, not representable as an “algebraic sum” of fewer than ρ elements of A. This is consistent with the definition of s_{ρ}(𝔽_{2}^{r}) given in Section 1, as it is readily seen from the two following observations:

i) if A ⊆ 𝔽_{2}^{r} satisfies ⟨A⟩_{ρ−1} ≠ ⟨A⟩ = 𝔽_{2}^{r} and is maximal subject to this condition, then 0 ∈ A; consequently, A is not contained in a proper coset and (ρ − 1)A = ⟨A⟩_{ρ−1} ≠ 𝔽_{2}^{r};

ii) if A ⊆ 𝔽_{2}^{r} is not contained in a proper coset and satisfies (ρ − 1)A ≠ 𝔽_{2}^{r}, then for any a ∈ A the set A′ := A + a is generating and satisfies ⟨A′⟩_{ρ−1} = (ρ − 1)A′ = (ρ − 1)A + (ρ − 1)a ≠ 𝔽_{2}^{r}.

We mention yet another equivalent way to rewrite the definition of s_{ρ}(G). Specifically, for a generating subset A ⊆ G let diam_{A}(G) be the minimum positive integer h such that ⟨A⟩_{h} = G, and let diam_{A}(G) = ∞ if A is not generating. Thus, diam_{A}(G) is the diameter of the Cayley graph, induced by A on G. Then evidently

s_{ρ}(G) = max{|A|: A ⊆ G, ρ ≤ diam_{A}(G) < ∞}.

The quantity s_{ρ}(G) was systematically studied in [KL], where in particular we were able to find it for all cyclic groups G (and arbitrary ρ ≥ 2) and also for ρ ∈ {2, 3} (and all groups G). As follows from the explanations above, Theorem 1 of the present paper establishes the values of s_{ρ}(G) for the groups G = 𝔽_{2}^{r} for all ρ ≥ 2. It is a challenging (and perhaps, quite difficult) problem to determine s_{ρ}(G) for other infinite families of groups, like G = (ℤ/mℤ)^{r} with an integer m > 2, or groups of rank two.

3. Coding theory interpretation

This section is intended for those readers interested in coding theory applications; everybody else can safely skip it. Consequently, we assume here acquaintance with basic coding theory notions.

GENERATING BINARY SPACES 5

We say that a linear binary code is non-degenerate if its minimum distance is at least three; that is, its check matrices contain no zero columns and no identical columns. The question that motivated coding theorists to study s_{ρ}(𝔽_{2}^{r}) (or related quantities, see footnote on page 2) is:

How large can be the length of a non-degenerate linear binary code of prescribed covering radius ρ and co-dimension r?

The connection between covering radii and s_{ρ}(𝔽_{2}^{r}) is established by the following argument. Suppose that a basis of 𝔽_{2}^{r} is fixed and declared “standard”. Given a subset A ⊆ 𝔽_{2}^{r}, write n := |A \ {0}| and arrange the coordinates of the non-zero elements of A with respect to the standard basis as matrix columns. If A is generating, then the columns of the resulting r × n binary matrix generate 𝔽_{2}^{r}, hence its rows are linearly independent over 𝔽_{2} and we consider it as a check matrix of a linear code of length n and co-dimension r. Since the matrix columns are pairwise distinct, the code constructed is non-degenerate. Evidently, the process is reversible; thus, we have a natural correspondence between generating subsets A ⊆ 𝔽_{2}^{r} of cardinality |A| = n + 1 such that 0 ∈ A, on the one hand, and non-degenerate linear codes of length n and co-dimension r, on the other hand. Moreover, the covering radius of codes, corresponding to A, is easily seen to equal diam_{A}(𝔽_{2}^{r}). (See the end of the previous section for the definition of diam_{A}(𝔽_{2}^{r}).)

Suppose that ρ ≥ 2 is fixed. We see that non-degenerate codes of co-dimension r and covering radius at least ρ correspond to subsets A ⊆ 𝔽_{2}^{r} such that 0 ∈ A and ρ ≤ diam_{A}(𝔽_{2}^{r}) < ∞, and that the length of the codes corresponding to A is |A| − 1. It follows that codes with the above properties exist if and only if r ≥ ρ, and in this case the maximum length of such codes is s_{ρ}(𝔽_{2}^{r})−1 = (ρ+1) 2^{r−ρ}−1 (by Theorem 1). Since (ρ + 1) 2^{r−ρ} − 1 is a strictly decreasing function of ρ, this expression actually gives the maximum possible length of codes with covering radius exactly ρ. This proves

Theorem 3. Let r and ρ ≥ 2 be positive integers. For non-degenerate linear binary codes of co-dimension r and covering radius ρ to exist, it is necessary and sufficient that r ≥ ρ. In this case the maximum length of such codes is (ρ + 1) 2^{r−ρ} − 1.

The question asked at the beginning of this section (and answered by Theorem 3) can be considered from another viewpoint:

How large can be the covering radius of a non-degenerate linear binary code of prescribed length n and co-dimension r?

6 VSEVOLOD F. LEV

We use the notation of [CHLL97], where this maximum covering radius is denoted by T [n, n − r, 3]. Notice, that one is actually interested in those values of r and n satisfying r ≤ n ≤ 2^{r} − 1, for otherwise non-degenerate codes of length n and co-dimension r do not exist.

Theorem 4. Let n and r ≥ 2 be positive integers such that r ≤ n ≤ 2^{r} − 1. Then the maximum possible covering radius of a non-degenerate linear binary code of length n and co-dimension r is

T [n, n − r, 3] = \begin{cases}1 & if n = 2^{r} − 1, \\ 2 & if 2^{r−1} ≤ n < 2^{r} − 1, \\ max\{ρ: ρ ∈ ℤ, (ρ + 1) 2^{r−ρ} > n\} & if r ≤ n < 2^{r−1}. \end{cases}

Proof. For 2^{r−1} ≤ n ≤ 2^{r} − 1 and also for n = r the assertion is easy to verify, and we assume that r < n < 2^{r−1}. Assume further that ρ is the integer satisfying (ρ + 1) 2^{r−ρ} > n and maximal subject to this condition, so that ρ ∈ [3, r − 1]. We want to show that T [n, n − r, 3] = ρ; in other words, to show that ρ is the maximum possible value of diam_{A}(𝔽_{2}^{r}) for a generating subset A ⊆ 𝔽_{2}^{r} of cardinality |A| = n + 1 such that 0 ∈ A.

i) Let A ⊆ 𝔽_{2}^{r} be a generating subset of cardinality |A| = n + 1 such that 0 ∈ A. Suppose that diam_{A}(𝔽_{2}^{r}) ≥ ρ + 1. Since ρ + 1 ≤ r, by Theorem 1 we have then

n + 1 = |A| ≤ s_{ρ+1}(𝔽_{2}^{r}) = (ρ + 2) 2^{r−(ρ+1)} ≤ n,

a contradiction. Thus diam_{A}(𝔽_{2}^{r}) ≤ ρ.

ii) To complete the proof, we construct a subset A ⊆ 𝔽_{2}^{r} of cardinality |A| = n + 1 such that 0 ∈ A and diam_{A}(𝔽_{2}^{r}) = ρ. For this we fix arbitrarily a subgroup H < 𝔽_{2}^{r} of index [𝔽_{2}^{r} : H] = 2^{ρ}, choose e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} such that 𝔽_{2}^{r} = ⟨e_{1}, …, e_{ρ}⟩ ⊕ H, and set

A_{1} := H ∪ (e_{1} + H) ∪ {e_{2}, …, e_{ρ}} and A_{2} := {0, e_{1}, …, e_{ρ}} + H,

so that 0 ∈ A_{1} ⊆ A_{2}. We have

|A_{1}| = 2^{r−ρ+1} + ρ − 1 ≤ (ρ + 2) 2^{r−ρ−1} + 1 ≤ n + 1 ≤ (ρ + 1) 2^{r−ρ} = |A_{2}|,

hence there exists a set A of cardinality |A| = n + 1 satisfying A_{1} ⊆ A ⊆ A_{2}. It is easily verified that diam_{A_{1}}(𝔽_{2}^{r}) = diam_{A_{2}}(𝔽_{2}^{r}) = ρ: indeed, ρA_{1} = 𝔽_{2}^{r} whereas e_{1} + ⋯ + e_{ρ} ∉ (ρ − 1)A_{2}. Therefore diam_{A}(𝔽_{2}^{r}) = ρ also. □

We say that a linear code of co-dimension r is cylindrical if there exist a subgroup H < 𝔽_{2}^{r}, elements e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} such that 𝔽_{2}^{r} = ⟨e_{1}, …, e_{ρ}⟩ ⊕ H, and a check matrix of the code whose columns are formed by the non-zero elements of the set

GENERATING BINARY SPACES 7

{0, e_{1}, …, e_{ρ}} + H (written in the standard basis of 𝔽_{2}^{r}). The length of such a code is n = (ρ + 1) 2^{r−ρ} − 1 and its covering radius is ρ. The reader will verify easily that Theorem 2 leads to the following conclusion.

Theorem 5. Let r and ρ be integers such that r ≥ ρ ≥ 4. Then any non-degenerate linear binary code of co-dimension r, covering radius at least ρ, and length n ≥ (ρ + 5) 2^{r−ρ−1} can be obtained by shortening a cylindrical code of co-dimension r and covering radius ρ.

4. Preliminaries

We establish here some facts, mentioned in Section 1 without proofs, and discuss briefly the result of Davydov and Tombak.

Lemma 1. We have s_{3}(𝔽_{2}^{r}) = 2^{r−1} for any integer r ≥ 3.

Proof. If A ⊆ 𝔽_{2}^{r} and |A| > 2^{r−1} then by the boxing principle any element of 𝔽_{2}^{r} is a sum of two elements of A; that is, 2A = 𝔽_{2}^{r}. This shows that s_{3}(𝔽_{2}^{r}) ≤ 2^{r−1}.

On the other hand, fix arbitrarily an index two subgroup H < 𝔽_{2}^{r} and an element z ∈ 𝔽_{2}^{r} \ H and let A := (H \ {0}) ∪ {z}. Then z ∉ 2A and A is not contained in a proper coset since 3A = 𝔽_{2}^{r}; therefore, s_{3}(𝔽_{2}^{r}) ≥ |A| = 2^{r−1}. □

Lemma 2. For an integer r ≥ 2 and a non-empty subset A ⊆ 𝔽_{2}^{r} the following conditions are equivalent:

(i) rA = 𝔽_{2}^{r}; (ii) kA = 𝔽_{2}^{r} for some (and therefore, for every sufficiently large) positive integer

k; (iii) A is not contained in a proper coset of 𝔽_{2}^{r}.

Moreover, if A satisfies conditions (i)–(iii) and (r − 1)A ≠ 𝔽_{2}^{r}, then for any a ∈ A we have A = a + {0, e_{1}, …, e_{r}}, where e_{1}, …, e_{r} form a basis of 𝔽_{2}^{r}. (Conversely, if A has this form then evidently A satisfies (i)–(iii) and (r − 1)A ≠ 𝔽_{2}^{r}.)

Proof. Plainly, (i) implies (ii) and (ii) implies (iii). Suppose that A satisfies (iii) and fix arbitrarily an element a ∈ A. Since A is not contained in a proper coset, the translate A + a is not contained in a proper subgroup, and therefore contains a basis of 𝔽_{2}^{r}, say {e_{1}, …, e_{r}}. Now

r(A + a) ⊇ r{0, e_{1}, …, e_{r}} = 𝔽_{2}^{r},

whence rA = 𝔽_{2}^{r}; that is, A satisfies (i). Moreover, it is clear that if A+a contains an element other than zero and the e_{i}s, then (r − 1)(A + a) = 𝔽_{2}^{r}, whence (r − 1)A = 𝔽_{2}^{r}. This proves the last assertion. □

Corollary 1. We have s_{ρ}(𝔽_{2}^{r}) = 0 for any integers r and ρ such that 2 ≤ r < ρ.

Proof. If A ⊆ 𝔽_{2}^{r} is not contained in a proper coset and r < ρ, then (ρ − 1)A ⊇ rA = 𝔽_{2}^{r}. □

We now show that for any r > ρ ≥ 2 there exist sets A ⊆ 𝔽_{2}^{r} such that (ρ − 1)A ≠ 𝔽_{2}^{r}, |A| = (ρ + 5) 2^{r−ρ−1}, and A is contained neither in a proper coset nor in a translated cylindrical set. Thus Theorem 2 is, in a sense, best possible.

Example 2. Fix arbitrarily a subgroup H < 𝔽_{2}^{r} of index [𝔽_{2}^{r} : H] = 2^{r−ρ−1} and elements e_{0}, e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} such that 𝔽_{2}^{r} = ⟨e_{0}, e_{1}, …, e_{ρ}⟩ ⊕ H and let

A := ({0, e_{1}, …, e_{ρ}} ∪ (⟨e_{1}, e_{2}⟩ + e_{0})) + H.

It is easily seen that |A| = (ρ + 5) 2^{r−ρ−1} and ρA = 𝔽_{2}^{r}, so that A is not contained in a proper coset. Furthermore, 𝔽_{2}^{r} \ (ρ − 1)A = e_{1} + ⋯ + e_{ρ} + H whereas for any cylindrical set C ⊆ 𝔽_{2}^{r} we have |𝔽_{2}^{r} \ (ρ − 1)C| = 2^{r−ρ}; thus |(ρ − 1)A| > |(ρ − 1)C| whence A ⊈ C.

Recall that a subset A ⊆ G of an abelian group G is called periodic if there exists a non-zero element h ∈ G such that A + h = A; otherwise A is aperiodic. The set of all elements h ∈ G with this property (including h = 0) is called the period of A and denoted H(A):

H(A) := {h ∈ G: A + h = A}.

Clearly, H(A) is a subgroup of G and A is a union of H(A)-cosets. Observe that A/H(A) is an aperiodic subset of the quotient group G/H(A).

The central result of [DT89] can be formulated as follows.

Theorem 6 (Davydov-Tombak, [DT89]). Let r ≥ 4 be an integer. Suppose that A ⊆ 𝔽_{2}^{r} satisfies 3A ≠ 𝔽_{2}^{r} and is maximal (by inclusion) subject to this condition. If |A| ≥ 2^{r−2} + 2, then A is periodic.

What is so exciting about the fact that A is periodic and how can one utilize this information? To exhibit the strength of Theorem 6 we show that it readily implies case ρ = 4 of Theorems 1 and 2. For this, suppose that A ⊆ 𝔽_{2}^{r} is not contained in a proper coset and satisfies 3A ≠ 𝔽_{2}^{r}. Without loss of generality we can assume that A is maximal subject to 3A ≠ 𝔽_{2}^{r}. Let H = H(A) < 𝔽_{2}^{r} be the period of A and let integer s ∈ [0, r] be defined by [𝔽_{2}^{r} : H] = 2^{s}, so that 𝔽_{2}^{r}/H ≅ 𝔽_{2}^{s}. Set \overline{A} = A/H, the image of A under the canonical homomorphism 𝔽_{2}^{r} → 𝔽_{2}^{r}/H. Then \overline{A} ⊆ 𝔽_{2}^{r}/H satisfies 3\overline{A} ≠ 𝔽_{2}^{r}/H and is maximal subject to this condition, and \overline{A} is not contained in a proper coset of 𝔽_{2}^{r}/H; therefore, s ≥ 4 by Corollary 1. Moreover, \overline{A} is aperiodic, hence by Theorem 6 we have |\overline{A}| ≤ 2^{s−2} + 1. It follows that

|A| = |\overline{A}||H| ≤ (2^{s−2} + 1) 2^{r−s} = 2^{r−2} + 2^{r−s} ≤ 2^{r−2} + 2^{r−4} = 5 · 2^{r−4},

as claimed by Theorem 1. Now assume that |A| > 9 · 2^{r−5}. Then from

9 · 2^{r−5} < |A| ≤ 2^{r−2} + 2^{r−s}

we get 2^{r−5} < 2^{r−s}, whence s = 4. In view of \overline{A} ⊆ 𝔽_{2}^{r}/H ≅ 𝔽_{2}^{4} and 3\overline{A} ≠ 𝔽_{2}^{4} and by Lemma 2, for any ā ∈ \overline{A} there exist linearly independent ē_{1}, …, ē_{4} ∈ 𝔽_{2}^{r}/H such that \overline{A} = ā + \{0, ē_{1}, …, ē_{4}\}. Now if a, e_{1}, …, e_{4} ∈ 𝔽_{2}^{r} are any fixed pre-images of ā, ē_{1}, …, ē_{4}, respectively, then A = a + {0, e_{1}, …, e_{4}} + H, and Theorem 2 follows.

5. Proof of Theorem 1

Lemma 3. Let r ≥ 3 be an integer and let e := {e_{1}, …, e_{r}} ⊆ 𝔽_{2}^{r} be a basis of 𝔽_{2}^{r}. Suppose that U ⊆ 𝔽_{2}^{r} is a subset such that no element of 2U is a sum of three or more pairwise distinct elements of e. Then |U| ≤ r + 1.

Proof. This is a particular case of a well-known theorem of Kleitman; see, for instance, [CHLL97, Theorem 2.4.16]. For a short independent proof see Lemma 5 below. □

Proof of Theorem 1. In view of (1), it suffices to show that for any subset A ⊆ 𝔽_{2}^{r}, not contained in a proper coset and such that (ρ−1)A ≠ 𝔽_{2}^{r}, holds |A| ≤ (ρ+1) 2^{r−ρ}. We can assume that 0 ∈ A: otherwise, A can be replaced by A+a where a is suitably chosen. We have then (ρ−1)A ⊆ ρA and we claim that the inclusion is strict: indeed, if (ρ − 1)A = ρA then for any integer k > ρ we have

kA = (k − ρ)A + ρA = (k − ρ)A + (ρ − 1)A = (k − 1)A = … = ρA = (ρ − 1)A,

hence ∪_{k=1}^{∞}kA = (ρ − 1)A is a proper subgroup of 𝔽_{2}^{r}, containing A.

Since (ρ−1)A ≠ ρA, there exist e_{1}, …, e_{ρ} ∈ A such that σ := e_{1}+⋯+e_{ρ} ∉ (ρ−1)A. Clearly, the elements e_{1}, …, e_{ρ} are linearly independent over 𝔽_{2}: for if I ⊆ {1, …, ρ} is a non-empty set such that ∑_{i∈I} e_{i} = 0, then σ = ∑_{i∉I} e_{i} ∈ (ρ − |I|)A ⊆ (ρ − 1)A, a contradiction. Thus L := ⟨e_{1}, …, e_{ρ}⟩ is a subgroup of 𝔽_{2}^{r} of index [𝔽_{2}^{r} : L] = 2^{r−ρ}, and to complete the proof we show any L-coset contains at most ρ + 1 elements of A.

For a contradiction, suppose that |(z + L) ∩ A| > ρ + 1 for some z ∈ 𝔽_{2}^{r}. Then U := (A + z) ∩ L is a subset of L of cardinality |U| > ρ + 1, and by Lemma 3 as applied to L ≅ 𝔽_{2}^{ρ} there are a_{1}, a_{2} ∈ A and I ⊆ {1, …, ρ} of cardinality |I| ≥ 3 such that

a_{1} + a_{2} = (a_{1} + z) + (a_{2} + z) = ∑_{i∈I} e_{i}.

10 VSEVOLOD F. LEV

Consequently,

σ = a_{1} + a_{2} + ∑_{i∉I} e_{i} ∈ (2 + ρ − |I|)A ⊆ (ρ − 1)A,

the contradiction sought. □

6. Proof of Theorem 2

As shown in Section 4, the case ρ = 4 is a corollary of the result of Davydov and Tombak and we assume below that r ≥ ρ ≥ 5. Suppose that A ⊆ 𝔽_{2}^{r} satisfies the assumptions of Theorem 2: that is, A is not contained in a proper coset, (ρ−1)A ≠ 𝔽_{2}^{r}, and |A| > (ρ + 5) 2^{r−ρ−1}. In addition, we can assume without loss of generality that 0 ∈ A, and then as in the proof of Theorem 1 there exist e_{1}, …, e_{ρ} ∈ A such that e_{1} + ⋯ + e_{ρ} ∉ (ρ − 1)A. This shows that Theorem 2 will follow from

Proposition 1. Let r ≥ ρ ≥ 5 be integers, and let A ⊆ 𝔽_{2}^{r} be a set of cardinality |A| > (ρ+5) 2^{r−ρ−1} such that 0 ∈ A. Suppose that e_{1}, …, e_{ρ} ∈ A satisfy e_{1}+⋯+e_{ρ} ∉ (ρ − 1)A (hence, are linearly independent over 𝔽_{2}). Then there exists a subgroup H < 𝔽_{2}^{r} such that 𝔽_{2}^{r} = ⟨e_{1}, …, e_{ρ}⟩ ⊕ H and A ⊆ {0, e_{1}, …, e_{ρ}} + H.

The rest of this section is devoted to the proof of Proposition 1. Consequently, we assume that A, e_{1}, …, e_{ρ} are as in the proposition, and for brevity we write

σ := e_{1} + ⋯ + e_{ρ}, P := {0, e_{1}, …, e_{ρ}}, and L := ⟨e_{1}, …, e_{ρ}⟩.  (2)

To prove Proposition 1 we have to find a subgroup H < 𝔽_{2}^{r} such that 𝔽_{2}^{r} = L ⊕ H and A ⊆ P + H. We use induction by r. For r = ρ the assertion is almost immediate. Indeed, from P ⊆ A and σ ∉ (ρ − 1)A it follows that A ∩ L = P; however, if r = ρ then L = 𝔽_{2}^{r} whence A = P and we choose H to be the zero subgroup. Assume now that r ≥ ρ + 1.

For z ∈ 𝔽_{2}^{r} define

L_{A}(z) := (A + z) ∩ L;  (3)

thus z +L_{A}(z) ⊆ A and indeed, L_{A}(z) is the set of all those l ∈ L satisfying z +l ∈ A. Notice, that L_{A}(z + l) = L_{A}(z) + l for any z ∈ 𝔽_{2}^{r} and l ∈ L. We seek H < 𝔽_{2}^{r} such that 𝔽_{2}^{r} = L ⊕ H and L_{A}(z) ⊆ P for any z ∈ H.

The following lemma establishes the basic property of the sets L_{A}(z).

Lemma 4. Let r, ρ, A, and e_{1}, …, e_{ρ} ∈ A be as in Proposition 1, let L and P be defined by (2) and L_{A}(z) by (3). Suppose that z_{1}, …, z_{k} ∈ 𝔽_{2}^{r} satisfy z_{1} + ⋯ + z_{k} = 0 (where k is a positive integer). Then

L_{A}(z_{1}) + ⋯ + L_{A}(z_{k}) ⊆ kP.

GENERATING BINARY SPACES 11

Proof. For k ≥ ρ the assertion is trivial and we assume that k ≤ ρ − 1. Suppose that there exist l_{i} ∈ L_{A}(z_{i}) (i = 1, …, k) such that l := l_{1} + ⋯ + l_{k} ∉ kP; in other words, there is a subset I ⊆ [1, ρ] of cardinality |I| > k such that l = ∑_{i∈I} e_{i}. Then

σ = l + ∑_{i∉I} e_{i} = (z_{1} + l_{1}) + ⋯ + (z_{k} + l_{k}) + ∑_{i∉I} e_{i} ∈ (k + ρ − |I|)A ⊆ (ρ − 1)A,

a contradiction. □

Corollary 2. For any z ∈ 𝔽_{2}^{r} we have 2L_{A}(z) ⊆ 2P.

Lemma 5. Let r and ρ be positive integers. Suppose that e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} are linearly independent over 𝔽_{2}, and let L and P be defined by (2). Suppose further that U ⊆ L is a set of cardinality |U| ≥ 5 satisfying 2U ⊆ 2P. Then there exists l ∈ L such that U ⊆ l + P.

Proof. We can assume that 0 ∈ U, and then U ⊆ 2U ⊆ 2P; consequently, if U ⊈ P then there exist i, j ∈ [1, ρ] (i ≠ j) such that e_{i} + e_{j} ∈ U. Renumbering the e_{i}s, if necessary, we can assume that i = 1 and j = 2. Now for any u ∈ U we have u+e_{1} +e_{2} ∈ 2P whence U ⊆ (e_{1} +e_{2} +2P)∩2P = (e_{1} +P)∪(e_{2} +P). Since |U| ≥ 5, there exists t ∈ [3, ρ] such that either e_{1} + e_{t} ∈ U, or e_{2} + e_{t} ∈ U. Without loss of generality we assume that e_{1} + e_{3} ∈ U, and then

U ⊆ ((e_{1} + P) ∪ (e_{2} + P)) ∩ ((e_{1} + P) ∪ (e_{3} + P)) = (e_{1} + P) ∪ {e_{2} + e_{3}}.

If e_{2} + e_{3} ∉ U then U ⊆ e_{1} + P and the proof is over. Otherwise we have e_{1} ∉ U (as (e_{2} +e_{3})+e_{1} ∉ 2P) and moreover, U does not contain any element of the form e_{1} +e_{s} for s ∈ [4, ρ]; hence U ⊆ {0, e_{1} + e_{2}, e_{1} + e_{3}, e_{2} + e_{3}}, contradicting the assumption that |U| ≥ 5. □

Remark . The restriction |U| ≥ 5 cannot be relaxed: there are four element subsets U ⊆ L such that 2U ⊆ 2P, and yet U ⊈ l + P for l ∈ L. Specifically, for pairwise distinct i, j, k ∈ [1, ρ] write S(e_{i}, e_{j}) := ⟨e_{i}, e_{j}⟩ and S(e_{i}, e_{j}, e_{k}) := ⟨e_{i} + e_{j}, e_{i} + e_{k}⟩. Then evidently 2S(e_{i}, e_{j}) ⊆ 2P and 2S(e_{i}, e_{j}, e_{k}) ⊆ 2P, and it not difficult to see that neither S(e_{i}, e_{j}) nor S(e_{i}, e_{j}, e_{k}) are contained in a shift of P. Moreover, it can be shown that any U ⊆ L satisfying 2U ⊆ 2P is a shifted subset of one of the sets S(e_{i}, e_{j}), S(e_{i}, e_{j}, e_{k}), or P.

From Corollary 2 and Lemma 5 we get

Corollary 3. Suppose that |L_{A}(z)| ≥ 5 for some z ∈ 𝔽_{2}^{r}. Then there exists l ∈ L such that L_{A}(z) ⊆ l + P. Thus, |L_{A}(z)| ≤ ρ + 1 for all z ∈ 𝔽_{2}^{r} and therefore |A| ≤ (ρ + 1) 2^{r−ρ}.

12 VSEVOLOD F. LEV

Remark . The last assertion of Corollary 3 does not follow from Theorem 1 since we do not assume here that A is not contained in a proper coset. On the other hand, Theorem 1 follows readily from Corollary 3.

Lemma 6. Let r, ρ, and k be positive integers. Suppose that e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} are linearly independent over 𝔽_{2}, and let L and P be defined by (2). Suppose further that U ⊆ L and V ⊆ P satisfy U + V ⊆ kP and |V | ≥ k + 2. Then U ⊆ (k − 1)P.

Proof. For any u ∈ U and v ∈ V we have u + v ∈ kP, hence u ∈ v + kP and we derive that U ⊆ (k + 1)P. Therefore, if u ∈ U \ kP then u is a sum of exactly k + 1 of the e_{i}s and in view of |V | ≥ k + 2 there exists v ∈ V such that u + v ∉ kP, a contradiction; thus in fact U ⊆ kP. Now if u ∈ U \(k−1)P then u is a sum of exactly k of the e_{i}s and in view of |V | ≥ k + 2 there exists v ∈ V such that u + v ∉ kP. Thus U ⊆ (k − 1)P, as claimed. □

Lemma 7. Let r, ρ, A, and e_{1}, …, e_{ρ} ∈ A be as in Proposition 1, and let L be defined by (2). Suppose that r ≥ ρ + 1. Then there exists an index two subgroup F < 𝔽_{2}^{r} satisfying L ≤ F and such that letting A_{0} := A ∩ F we have |A_{0}| ≥ \frac{1}{2}|A|.

Proof. There are 2^{r−ρ} − 1 index two subgroups F < 𝔽_{2}^{r} such that L ≤ F; we choose one at random and estimate E |A ∩ F |, the expected number of elements of A in F. It is not difficult to see that for any a ∈ A \ L there are exactly 2^{r−ρ−1} − 1 subgroups F such that a ∈ F. Consequently, recalling that |A ∩ L| = ρ + 1 and using the estimate of Corollary 3 we obtain

E |A ∩ F | = ∑_{a∈A} Pr{a ∈ F }

= |A ∩ L| + \frac{2^{r−ρ−1} − 1}{2^{r−ρ} − 1} |A \ L|

= \frac{1}{2^{r−ρ} − 1} ((2^{r−ρ−1} − 1)|A| + (ρ + 1) 2^{r−ρ−1})

≥ \frac{1}{2^{r−ρ} − 1} ((2^{r−ρ−1} − 1)|A| + |A|/2)

= \frac{1}{2} |A|.

The assertion follows. □

We are ready now to complete the proof of Proposition 1. Let F and A_{0} be as in Lemma 7. By the induction hypothesis as applied to A_{0} ⊆ F, there exists a subgroup H_{0} < F such that F = L ⊕ H_{0} and L_{A}(h) ⊆ P for any h ∈ H_{0}. (Observe that for any

GENERATING BINARY SPACES 13

z ∈ F we have L_{A_{0}}(z) = (A_{0} + z) ∩ L = (A + z) ∩ L = L_{A}(z).) For a positive integer j write

H_{j} := {h ∈ H_{0} : |L_{A}(h)| ≥ j},

the set of all those h ∈ H_{0} such that h+L contains at least j elements of A_{0}. Thus |H_{j}| is the number of L-cosets in F, containing at least j elements of A. We distinguish two cases.

i) Suppose first that there exists z_{0} ∈ 𝔽_{2}^{r} \ F such that |L_{A}(z_{0})| ≥ 6. By Corollary 3 we have L_{A}(z_{0}) ⊆ l + P for some l ∈ L, and having replaced z_{0} by z_{0} + l we can assume that in fact L_{A}(z_{0}) ⊆ P. We define H := H_{0} ⊕ ⟨z_{0}⟩; thus 𝔽_{2}^{r} = L ⊕ H and we show that L_{A}(z_{0} + h) ⊆ P for any h ∈ H_{0}.

We notice that

(ρ + 1)|H_{5}| + 4(|H_{0}| − |H_{5}|) ≥ |A_{0}| ≥ \frac{1}{2}|A| > (ρ + 5) 2^{r−2−ρ},

whence (ρ − 3)|H_{5}| > (ρ + 5) 2^{r−2−ρ} − 4|H_{0}| = (ρ − 3) 2^{r−2−ρ} and |H_{5}| > 2^{r−2−ρ} = |H_{0}|/2. By the pigeonhole principle, any h ∈ H_{0} has a representation h = h′_{5}+h′′_{5} with h′_{5}, h′′_{5} ∈ H_{5} and then by Lemma 4 we have L_{A}(z_{0} + h) + L_{A}(h′_{5}) + L_{A}(h′′_{5}) + L_{A}(z_{0}) ⊆ 4P. Now we recall that L_{A}(h) ⊆ P for any h ∈ H_{0} and use Lemma 6 to obtain subsequently

L_{A}(z_{0} + h) + L_{A}(h′_{5}) + L_{A}(h′′_{5}) ⊆ 3P,
L_{A}(z_{0} + h) + L_{A}(h′_{5}) ⊆ 2P,
L_{A}(z_{0} + h) ⊆ P,

as required.

ii) Suppose now that |L_{A}(z)| ≤ 5 for any z ∈ 𝔽_{2}^{r} \ F. Since

|A \ F | > (ρ + 5) 2^{r−ρ−1} − (ρ + 1) 2^{r−ρ−1} = 4 · 2^{r−ρ−1}

by Corollary 3, there exists z_{0} ∈ 𝔽_{2}^{r} \ F such that |L_{A}(z_{0})| = 5. As above we can assume that L_{A}(z_{0}) ⊆ P and it suffices to show that L_{A}(z_{0} + h) ⊆ P for any h ∈ H_{0}.

We have

|A_{0}| ≥ |A| − 5 · [F : L] > (ρ + 5) 2^{r−ρ−1} − 5 · 2^{r−ρ−1} = ρ 2^{r−ρ−1}

whereas in view of ρ ≥ 5

|A_{0}| ≤ (ρ + 1)|H_{6}| + 5(|H_{4}| − |H_{6}|) + 3(|H_{0}| − |H_{4}|)
= (ρ − 4)|H_{6}| + 2|H_{4}| + 3 · 2^{r−ρ−1}
≤ (ρ − 3)(|H_{6}| + |H_{4}|) + 3 · 2^{r−ρ−1}.

14 VSEVOLOD F. LEV

It follows that |H_{6}|+|H_{4}| > 2^{r−ρ−1} = |H_{0}| and by the pigeonhole principle any h ∈ H_{0} can be represented as h = h_{4} + h_{6} with h_{4} ∈ H_{4} and h_{6} ∈ H_{6}. By Lemma 4 we have L_{A}(z_{0} + h) + L_{A}(h_{4}) + L_{A}(z_{0}) + L_{A}(h_{6}) ⊆ 4P and then

L_{A}(z_{0} + h) + L_{A}(h_{4}) + L_{A}(z_{0}) ⊆ 3P,
L_{A}(z_{0} + h) + L_{A}(h_{4}) ⊆ 2P,
L_{A}(z_{0} + h) ⊆ P

by Lemma 6. This completes the proof.

7. Periodicity and ρ-maximal sets

Let r ≥ 1 and ρ ≥ 2 be integers. To describe sets A ⊆ 𝔽_{2}^{r} satisfying (ρ − 1)A ≠ 𝔽_{2}^{r} it suffices to consider only those sets which are maximal (by inclusion) subject to this condition. We call such sets ρ-maximal; any set satisfying (ρ−1)A ≠ 𝔽_{2}^{r} is, therefore, a subset of a ρ-maximal set.

Plainly, if A ⊆ 𝔽_{2}^{r} is ρ-maximal and contained in a proper coset, then A is the coset itself. Suppose now that A ⊆ 𝔽_{2}^{r} is ρ-maximal and not contained in a proper coset, and let H := H(A) be the period of A. (See Section 4 for the definitions of period and periodicity.) Then \overline{A} := A/H is an aperiodic ρ-maximal subset of the quotient group 𝔽_{2}^{r}/H with |\overline{A}| > 1. Conversely, if H ≤ 𝔽_{2}^{r} is a subgroup and \overline{A} is a ρ-maximal subset of the quotient group 𝔽_{2}^{r}/H, then the full pre-image A ⊆ 𝔽_{2}^{r} of \overline{A} under the canonical homomorphism 𝔽_{2}^{r} → 𝔽_{2}^{r}/H is a ρ-maximal subset of 𝔽_{2}^{r} — save for the case ρ = 2 when maximality is violated. Moreover, if \overline{A} ⊆ 𝔽_{2}^{r}/H is aperiodic and |\overline{A}| > 1, then A is not contained in a proper coset of 𝔽_{2}^{r}.

This shows that periodic ρ-maximal sets are induced by aperiodic ones; in this sense aperiodic ρ-maximal sets are primitive, whereas periodic ρ-maximal sets can be obtained by their “lifting”. In other words, aperiodic ρ-maximal subsets are the “building blocks” of which all other ρ-maximal sets are constructed; their properties, therefore, determine the properties of all ρ-maximal sets. Motivated by this observation, we define

t_{ρ}(𝔽_{2}^{r}) := max{|A|: A ⊆ 𝔽_{2}^{r} is aperiodic and ρ-maximal and |A| > 1};

here we assume max ∅ = 0 so that t_{ρ}(𝔽_{2}^{r}) = 0 if no aperiodic ρ-maximal sets A ⊆ 𝔽_{2}^{r} with |A| > 1 exist. Notice that the restriction |A| > 1 can be dropped, unless r = 1: this is because one-element sets are never ρ-maximal if r ≥ 2.

Our definition of t_{ρ}(𝔽_{2}^{r}) can be extended onto arbitrary finite abelian group G in several ways. One of such extensions was considered in [KL] where, in particular, we were able to determine t_{ρ}(G) for ρ ∈ {2, 3} and also for any ρ ≥ 2 in the special case

GENERATING BINARY SPACES 15

of G cyclic. It follows immediately from the results of [KL] (and can be easily shown directly) that

s_{ρ}(𝔽_{2}^{r}) = max_{1≤k≤r} 2^{r−k} t_{ρ}(𝔽_{2}^{k}) for r ≥ ρ ≥ 2.

Furthermore, we have

t_{ρ}(𝔽_{2}^{r}) = 0  for r < ρ

(Lemma 2: if r < ρ and A ⊆ 𝔽_{2}^{r} is ρ-maximal, then A is a proper coset, hence either A is periodic or |A| = 1);

t_{2}(𝔽_{2}^{r}) = 2^{r} − 1 for r ≥ 2  (4)

(for any z ∈ 𝔽_{2}^{r} the set A := 𝔽_{2}^{r} \ {z} is 2-maximal and aperiodic); and finally,

t_{3}(𝔽_{2}^{r}) = 2^{r−1} for r ≥ 3  (5)

(the set constructed in the proof of Lemma 1 is aperiodic).

As to the value of t_{4}(𝔽_{2}^{r}), Theorem 6 shows that t_{4}(𝔽_{2}^{r}) ≤ 2^{r−2} + 1. In fact, Davydov and Tombak constructed in [DT89] aperiodic 4-maximal sets A ⊆ 𝔽_{2}^{r} of this cardinality, whence

t_{4}(𝔽_{2}^{r}) = 2^{r−2} + 1 for r ≥ 4.  (6)

We note that (6) is a deep result with applications to coding theory and finite geometries, while (4) and (5) are almost immediate.

Though we were unable to determine t_{ρ}(𝔽_{2}^{r}) for ρ ≥ 5, we conjecture the following.

Conjecture 1. We have t_{ρ}(𝔽_{2}^{r}) = 2^{r+2−ρ} + ρ − 3 for any integers r ≥ ρ ≥ 2.

As shown in Section 4, Theorem 6 implies case ρ = 4 of Theorems 1 and 2, and in a similar way Conjecture 1 (which is an extension of Theorem 6) implies the general case of these theorems. Indeed, the importance of Conjecture 1 is that it describes the structure of all subsets A ⊆ 𝔽_{2}^{r} of cardinality |A| > 2^{r−ρ+2} + ρ − 3, not contained in a proper coset and such that (ρ − 1)A ≠ 𝔽_{2}^{r}. More precisely: assuming Conjecture 1, for each fixed ε > 0 one can effectively find a finite family of sets \overline{A} such that any A ⊆ 𝔽_{2}^{r}, not contained in a proper coset and satisfying |A| > (1 + ε) 2^{r−ρ+2} and (ρ − 1)A ≠ 𝔽_{2}^{r}, is a subset of the “lifting” of some \overline{A}. We leave the details to the reader.

Observe that (4)–(6) establish our conjecture for ρ ≤ 4. Furthermore, the lower bound of the conjecture is not difficult to prove.

16 VSEVOLOD F. LEV

Example 3. Fix arbitrarily a subgroup H < 𝔽_{2}^{r} of index [𝔽_{2}^{r} : H] = 2^{ρ} and elements e_{1}, …, e_{ρ} ∈ 𝔽_{2}^{r} such that 𝔽_{2}^{r} = ⟨e_{1}, …, e_{ρ}⟩ ⊕ H and let

A := {0, e_{1}, …, e_{ρ}} ∪ (⟨e_{1}, e_{2}⟩ + (H \ {0})).

Then (ρ − 1)A = 𝔽_{2}^{r} \ {e_{1} + ⋯ + e_{ρ}}, whence A is ρ-maximal and aperiodic. Thus

t_{ρ}(𝔽_{2}^{r}) ≥ |A| = (ρ + 1) + 4(|H| − 1) = 2^{r−ρ+2} + ρ − 3.

Apart from the case ρ ≤ 4, we can prove Conjecture 1 for r ≤ ρ + 2 only. Indeed, for r = ρ the conjecture claims that t_{r}(𝔽_{2}^{r}) = r + 1, and this follows readily from Lemma 2. The case r = ρ + 1 is settled by the following lemma.

Lemma 8. Let ρ ≥ 5 be an integer and let r = ρ + 1. Suppose that A ⊆ 𝔽_{2}^{r} is ρ-maximal and aperiodic. Then |A| ≤ ρ + 5.

Proof. As in the proof of Theorems 1 and 2 we can assume without loss of generality that there exist e_{1}, …, e_{ρ} ∈ A such that, with σ, P, and L defined by (2), we have A ∩ L = P and σ ∉ (ρ − 1)A. Fix arbitrarily z ∈ 𝔽_{2}^{r} \ L and let L_{A}(z) be defined by (3). Then |L_{A}(z)| = |A| − |P | = |A| − (ρ + 1), and assuming that |A| > ρ + 5 we get |L_{A}(z)| ≥ 5. Corollary 3 shows then that L_{A}(z) ⊆ l + P for some l ∈ L, and hence A ⊆ {0, z + l} + P. However, the set A_{0} := {0, z + l} + P is periodic (we have A_{0} + z + l = A_{0}) and satisfies σ ∉ (ρ − 1)A_{0}. This contradicts the assumption that A ⊆ A_{0} is ρ-maximal and aperiodic. □

As indicated above, we can prove the conjecture in the case r = ρ+2, too; however, the proof is rather complicated and we do not present it here. For r ≥ ρ + 3 the only upper bound we have is t_{ρ}(𝔽_{2}^{r}) ≤ (ρ + 5) 2^{r−ρ−1}, following from Theorem 2.

Acknowledgement

I am indebted to Benjamin Klopsch for fruitful discussions, to Simon Litsyn for useful coding theory consultations, and to the anonymous referees for a number of valuable remarks.

References

[CZ99] G. Cohen and G. Zemor, Subsut sums and coding theory, Astérisque 258 (1999), 327–339.

[CHLL97] G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering codes, North-Holland Math. Library 54 (1997), Elsevier.

[CP92] W. E. Clark and J. Pedersen, Sum-free sets in vector spaces over GF(2), J. Comb. Theory, A 61 (2) (1992), 222–229.

[DT89] A. Davydov and L. Tombak, Quasi-perfect linear binary codes with distance 4 and complete caps in projective geometry, Problemy Peredachi Informatzii 25 (4) (1989), 11–23.

[KL] B. Klopsch and V. F. Lev, How long does it take to generate a group?, J. of Algebra, to appear.

[Z92a] G. Zemor, Algebraic coding, Lecture Notes in Computer Science 573 (1992), Springer-Verlag, Berlin. (Proceedings of the First French-Soviet Workshop held in Paris, July 22–24, 1991.)

[Z92b] G. Zemor, Subset sums in binary spaces, European J. Combin. 13 (2) (1992), 221–230.

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel.

  E-mail address: seva@math.haifa.ac.il