HOW LONG DOES IT TAKE TO GENERATE A GROUP?

BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

Abstract. The diameter of a finite group G with respect to a generating set A is the smallest non-negative integer n such that every element of G can be written as a product of at most n elements of A ∪ A^{−1}. We denote this invariant by diam_{A}(G). It can be interpreted as the diameter of the Cayley graph induced by A on G and arises, for instance, in the context of efficient communication networks.

In this paper we study the diameters of a finite abelian group G with respect to its various generating sets A. We determine the maximum possible value of diam_{A}(G) and classify all generating sets for which this maximum value is attained. Also, we determine the maximum possible cardinality of A subject to the condition that diam_{A}(G) is “not too small”. Connections with caps, sum-free sets, and quasi-perfect codes are discussed.

1. Introduction

Let G be a finite group and let A be a subset of G. The subgroup generated by A in G 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 called a generating set for G; so A generates G if and only if it is not contained in any proper subgroup of G. Loosely speaking, the aim of this paper is to determine whether and how quickly A generates G, using only information about the cardinality of A.

For this we regard generation as a dynamic step-by-step process. Since eventually we restrict to the situation where G is abelian, we use additive notation throughout. Let A^{±} := (−A) ∪ {0} ∪ A denote the “symmetric closure” of A with respect to addition. Thus ⟨A⟩ consists of all those g ∈ G representable as a sum of elements of A^{±}, and for every non-negative integer ρ we define

⟨A⟩_{ρ} := ρA^{±} = {a_{1} + ⋯ + a_{ρ}: a_{i} ∈ A^{±}} ⊆ G,

At the time our collaboration started the first author held a PIMS postdoctoral fellowship at the University of Alberta (Canada) while the second author was a postdoctoral fellow at the Hebrew University of Jerusalem (Israel). We express our gratitude for the support provided by these institutions.

2 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

the set of all g ∈ G representable as a sum of at most ρ elements of A^{±}. Evidently, these sets form an ascending chain {0} = ⟨A⟩_{0} ⊆ ⟨A⟩_{1} ⊆ …, and their union ⋃_{ρ≥0}⟨A⟩_{ρ} = ⟨A⟩ provides a bottom-up description of the subgroup generated by A. We notice that ⟨A^{±}⟩_{ρ} = ⟨A⟩_{ρ} for every ρ ∈ ℕ_{0} := ℕ ∪ {0}.

We define the diameter of G with respect to A as

diam_{A}(G) := min{ρ ∈ ℕ_{0} : ⟨A⟩_{ρ} = G}.

To explain this nomenclature we introduce a suitable length function. For every g ∈ G we define the length of g with respect to A as

l_{A}(g) := min{ρ ∈ ℕ_{0} : g ∈ ⟨A⟩_{ρ}}.

Here we agree that min ∅ = ∞, so that for g ∈ G we have g ∈ ⟨A⟩ if and only if l_{A}(g) < ∞. Observe that l_{A}(g) is simply the minimum number of (not necessarily distinct) elements of A^{±} required to represent g as their sum. Thus we have

⟨A⟩_{ρ} = {g ∈ G: l_{A}(g) ≤ ρ}

and

diam_{A}(G) = max{l_{A}(g): g ∈ G}.

From this point of view the diameter allows a simple graph-theoretic interpretation. Indeed, l_{A}(g) is the distance from zero to g in the Cayley graph induced by A on G, and diam_{A}(G) is the diameter of this graph. Moreover, diam_{A}(G) describes quantitatively “how long” it takes to generate G from A. In particular, A is a generating set for G if and only if diam_{A}(G) < ∞.

The length of a given element and the diameter of G depend upon the choice of A ⊆ G. In contrast, the absolute diameter

diam(G) := max{diam_{A}(G): ⟨A⟩ = G}

is an invariant of G itself: every generating set produces the group in at most that many steps.

The two problems addressed in this paper are:

P1. What is the value of diam(G) and what are the generating sets A ⊆ G such that

diam_{A}(G) = diam(G)? P2. How large can diam_{A}(G) be, given that |A| is large? Under the assumption that G is abelian, we solve the first problem completely (see

Theorems 2.1 and 2.2) and we provide several partial answers to the second one (see Theorems 2.7, 2.9, and 2.12). Our results are presented in detail in the next section.

GENERATING AN ABELIAN GROUP 3

At first sight the restriction to abelian groups may seem too strong — after all, finite abelian groups are rather trivial objects from a group-theoretic point of view. But here we are concerned with combinatorial properties of finite groups, and already the case where G is homocyclic leads to interesting applications in coding theory and other areas; see Section 3.

Remark . Our starting point in this paper are representations of the elements of G by “algebraic sums” ±a_{1} ± ⋯ ± a_{n}. However, it would be equally natural to allow only “pure sums” a_{1} + ⋯ + a_{n}. Formally, we could have put A^{+} := A ∪ {0} and then proceeded to define ⟨A⟩_{ρ}^{+}, diam_{A}^{+}(G), l_{A}^{+}(g), diam^{+}(G), etc. This approach leads to a significantly different theory, which we are going to cover in a separate paper.

Organization of the paper . In Sections 2 and 3 we describe our results in detail and place them into a broader context. Section 4 contains a list of auxiliary results. All proofs are collected in Sections 5 to 9.

Notation. The notation used is mostly standard, but the following list may be of help. ℕ, ℕ_{0}, and ℤ the sets of positive, non-negative, and all integers, respectively. For natural numbers n, n_{1}, …, n_{r}: ℤ_{n} (or ℤ/nℤ) the group of residues modulo n; gcd(n_{1}, …, n_{r}) the greatest common divisor of n_{1}, …, n_{r}; lcm(n_{1}, …, n_{r}) the least common multiple of n_{1}, …, n_{r}. For real numbers x, y: ⌊x⌋ the greatest integer not exceeding x; ⌈x⌉ the smallest integer no smaller than x; [x, y] the set of all integers n satisfying x ≤ n ≤ y. For a non-negative integer r and subsets A, A_{1}, …, A_{r} of an abelian group G: A_{1} + ⋯ + A_{r} the set {a_{1} + ⋯ + a_{r}: a_{1} ∈ A_{1}, …, a_{r} ∈ A_{r}}; rA the set A + ⋯ + A (r summands); r ∗ A the set {ra: a ∈ A}. (For r = 0 the expressions A_{1} + ⋯ + A_{r} and rA should be interpreted as {0}.)

Also, for integers m and n we write m | n to indicate that m divides n.

2. Summary of results

We state our results in several blocks: first we look at the absolute diameter of a finite abelian group and then at the maximum size of small diameter sets; cf. Problems P1 and P2 of the Introduction.

4 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

2.1. The absolute diameter. Up to isomorphism, every finite abelian group is completely characterized by its type. Let G be a finite abelian group of type (m_{1}, …, m_{r}); that is, G ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r}} where 1 ≠ m_{1} | ⋯ | m_{r}. The number r is called the rank of G and denoted rk(G); it is the minimum number of elements required to generate G. A standard generating set for G is a subset A = {a_{1}, …, a_{r}} ⊆ G such that G = ⟨a_{1}⟩ ⊕ ⋯ ⊕ ⟨a_{r}⟩ and ord(a_{i}) = m_{i} for all i ∈ [1, r]. It is worth pointing out that the trivial group {0} has type (), rank 0, and precisely one standard generating set, namely ∅.

Perhaps not surprisingly, the diameter of G with respect to a standard generating set is as large as possible. Indeed, if A is a standard generating set for G, then plainly diam_{A}(G) = ∑_{i=1}^{r}⌊m_{i}/2⌋, and we establish

Theorem 2.1. A finite abelian group G of type (m_{1}, …, m_{r}) has diameter

diam(G) = ∑_{i=1}^{r}⌊m_{i}/2⌋.

Conversely, if A is a generating set for G with diam_{A}(G) = diam(G), then A is “nearly standard”; a small wrinkle is observed if G has invariant factors of order three. To make this precise, for m ∈ ℕ we define

ν_{m}(G) := #{i ∈ [1, r]: m_{i} = m},  (2.1)

the number of components of (m_{1}, …, m_{r}) equal to m. We notice that, if m is prime and ν_{m}(G) ≠ 0, then m_{i} = m for all i ∈ [1, ν_{m}(G)]. Furthermore, if m′ and m′′ are co-prime, then at least one of ν_{m′}(G) and ν_{m′′}(G) is zero.

Theorem 2.2. Let G be a finite abelian group of rank r. Then for every subset A ⊆ G the following assertions are equivalent:

(i) diam_{A}(G) = diam(G); (ii) there exists a standard generating set B = {b_{1}, …, b_{r}} for G such that

B^{±} ⊆ A^{±} ⊆ (B ∪ {b_{2i−1} + b_{2i}: i ∈ [1, ν_{3}(G)/2]})^{±}.

Corollary 2.3. Let G be a finite abelian group. Then for every subset A ⊆ G satisfying diam_{A}(G) = diam(G) we have

rk(G) ≤ |A| ≤ 1 + 2 rk(G) − ν_{2}(G) + 2⌊ν_{3}(G)/2⌋.

Indeed, both bounds are sharp.

GENERATING AN ABELIAN GROUP 5

For abelian groups these theorems provide a complete solution to Problem P1 of the Introduction. In contrast, for no infinite family H of non-abelian finite groups such explicit formulae for the diameters diam(H), H ∈ H, seem to be known.

2.2. The maximum size of small diameter sets: definitions. Let G be a finite abelian group. Intuitively, it is clear that the larger a subset A ⊆ G, the smaller the corresponding diameter diam_{A}(G). But to what extent does the size of A alone guarantee fast generation?

Suppose that ρ ∈ ℕ. We want to find an upper bound for the sizes of generating sets A for G with diam_{A}(G) ≥ ρ. Agreeing that max ∅ = 0, we define

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

Equivalently, we have s_{ρ}(G) = max{|A|: A ⊆ G such that ⟨A⟩_{ρ−1} ≠ ⟨A⟩ = G}. The significance of this new invariant stems from the observation that every generating set A for G of size larger than s_{ρ}(G) surely generates G in less than ρ steps.

In order to better understand s_{ρ}(G) we introduce a related and perhaps more fundamental invariant, t_{ρ}(G); this requires a short preparation. Recall that the period of a subset S ⊆ G is the subgroup π(S) := {g ∈ G: S + g = S} ≤ G, and S is periodic or aperiodic according to whether π(S) ≠ {0} or π(S) = {0}. Clearly, S is a union of π(S)-cosets; consequently, if gcd(|S|, |G|) = 1 then S is aperiodic. Another useful observation is that the image of S under the canonical homomorphism G → G/π(S) is an aperiodic subset of the quotient group G/π(S).

We say that a subset A ⊆ G is ρ-maximal if it is maximal (under inclusion) subject to diam_{A}(G) ≥ ρ; that is, subject to ⟨A⟩_{ρ−1} ≠ G. Plainly, we have

s_{ρ}(G) = max{|A|: A is a ρ-maximal generating set for G}.

One can construct ρ-maximal generating sets by a “lifting process” as follows. Suppose that H ≨ G, and let φ : G → G/H denote the canonical homomorphism. If \overline{A} = \overline{A} ^{±} is a generating set for G/H, then the full pre-image A := φ^{−1}(\overline{A}) is a generating set for G with diam_{A}(G) = diam\overline{A}(G/H) and π(A) ≥ H. Conversely, suppose A = A^{±} is a generating set for G and H ≤ π(A). Then the image \overline{A} = φ(A) is a generating set for G/H and diam\overline{A}(G/H) = diam_{A}(G). Furthermore, if A is ρ-maximal then so is \overline{A}, and if H = π(A) then \overline{A} is aperiodic. This shows that every ρ-maximal generating set is induced by an aperiodic one. A natural point of view, therefore, is to consider aperiodic ρ-maximal generating sets as “primitive” and concentrate on their properties first. Accordingly, we let

t_{ρ}(G) := max{|A|: A is an aperiodic ρ-maximal generating set for G},

6 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

again subject to the agreement that max ∅ = 0.

We notice that, if ρ > diam(G), then ρ > diam_{A}(G) for all generating subsets A ⊆ G; consequently, G admits no ρ-maximal generating sets and t_{ρ}(G) = 0. On the other hand, if ρ ∈ [1, diam(G)] then in the definition of t_{ρ}(G) we can safely disregard the requirement that A generates G. Indeed, suppose that A ⊆ G is ρ-maximal, but does not generate G. Then A is a proper subgroup of G. Suppose that in addition A is aperiodic. Then A = {0} lies in the symmetric closure B^{±} of every subset B ⊆ G; it follows that diam(G) < ρ. In summary, we have

t_{ρ}(G) = \begin{cases}max\{|A|: A ⊆ G is aperiodic and ρ-maximal\} & if ρ ∈ [1, diam(G)], \\ 0 & if ρ > diam(G). \end{cases}

The close connection between t_{ρ}(G) and s_{ρ}(G) is described by

Lemma 2.4. Let G be a finite abelian group and let ρ ∈ [2, diam(G)]. Then

s_{ρ}(G) = max{|H| · t_{ρ}(G/H): H ≨ G}.

Unless G is trivial, the only 1-maximal subset of G is G itself; so s_{1}(G) = |G| and t_{1}(G) = 0. In fact, it can happen that t_{ρ}(G) = 0 also for ρ ∈ [2, diam(G)]. Examples of this kind can be constructed as follows.

Example 2.5. Let n ∈ ℕ with n ≥ 2, and let G = ℤ_{2} ⊕ ℤ_{2^{n+1}}. Then diam(G) = 1 + 2^{n}, and every 2^{n}-maximal subset of G is periodic.

Perhaps it is feasible to classify all pairs (G, ρ) such that t_{ρ}(G) = 0, but beyond Example 2.5 nothing much is known.

2.3. The maximum size of small diameter sets: explicit formulae. We completely determine t_{ρ}(G) and s_{ρ}(G) in the following particular cases:

(i) G is an arbitrary finite abelian group and ρ ∈ {1, 2, 3, diam(G)}; (ii) G is a finite cyclic group and ρ ∈ [1, diam(G)] is arbitrary.

The case ρ = 1 is settled by the observation preceding Example 2.5. The case ρ = 2 is not difficult either.

Proposition 2.6. Let G be a finite abelian group with diam(G) ≥ 2. Then

t_{2}(G) = s_{2}(G) = \begin{cases}|G| − 1 & if |G| is even, \\ |G| − 2 & if |G| is odd. \end{cases}

GENERATING AN ABELIAN GROUP 7

For the next theorem recall that the exponent of an abelian group G is exp(G) = max{ord(g): g ∈ G}, where ord(g) denotes the order of g ∈ G. The 2-rank of G, denoted rk_{2}(G), is the rank of the Sylow 2-subgroup of G. The group G is called homocyclic if it can be written as a direct sum of pairwise isomorphic cyclic groups.

Suppose that G is of type (m_{1}, …, m_{r}). Then we have rk(G) = r and, unless G is trivial, exp(G) = m_{r}. Moreover, rk_{2}(G) is the number of indices i ∈ [1, r] for which m_{i} is even, and rk_{2}(2 ∗ G) is the number of indices i ∈ [1, r] for which m_{i} is divisible by four. (Here 2 ∗ G denotes the set {2g: g ∈ G}; see our list of definitions at the end of Section 1.) Clearly, G is homocyclic if and only if m_{1} = ⋯ = m_{r}.

Theorem 2.7. Let G be a finite abelian group with diam(G) ≥ 3.

(i) Suppose that |G| is odd, and let n := exp(G). Then

t_{3}(G) = s_{3}(G) = \begin{cases}\frac{n−1}{2n} |G| − 1 & if n ≡ 1 (mod 4), \\ \frac{n−1}{2n} |G| & if n ≡ 3 (mod 4). \end{cases}

(ii) Suppose that |G| is even. Then

t_{3}(G) = \begin{cases}(|G| − \sqrt{|G|})/2 & if G is homocyclic of exponent 4, \\ |G|/2 − 1 & if rk_{2}(G) = rk_{2}(2 ∗ G) and exp(G) > 4, \\ |G|/2 & if rk_{2}(G) > rk_{2}(2 ∗ G), \end{cases}

s_{3}(G) = \begin{cases}|G|/2 − 1 & if G is a cyclic 2-group, \\ |G|/2 & otherwise. \end{cases}

The proof of this theorem already requires a fair amount of work. Probably, it will be significantly more difficult to find explicit formulae for t_{4}(G) and s_{4}(G). Some general estimates are given later in this section.

Our next result is a consequence of Theorem 2.2; see also Corollary 2.3.

Corollary 2.8. Let G be a finite abelian group, and suppose that ρ := diam(G) ≥ 2. Then

t_{ρ}(G) = s_{ρ}(G) = 1 + 2 rk(G) − ν_{2}(G) + 2⌊ν_{3}(G)/2⌋.

We now turn our attention towards cyclic groups. Notice that diam(ℤ_{m}) = ⌊m/2⌋ for all m ∈ ℕ, by Theorem 2.1.

Theorem 2.9. Let m ∈ ℕ and ρ ∈ [2, m/2]. Then

t_{ρ}(ℤ_{m}) = 2 ⌊\frac{m − 2}{2(ρ − 1)}⌋ + 1

8 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

and

s_{ρ}(ℤ_{m}) = max \{\frac{m}{d} (2 ⌊\frac{d − 2}{2(ρ − 1)}⌋ + 1) : d | m, d ≥ 2ρ\} .

In particular, for cyclic groups of prime order this reduces to

Corollary 2.10. Let p ≥ 5 be a prime and suppose that ρ ∈ [2, (p − 1)/2]. Then

t_{ρ}(ℤ_{p}) = s_{ρ}(ℤ_{p}) = 2 ⌊\frac{p − 2}{2(ρ − 1)}⌋ + 1.

2.4. The maximum size of small diameter sets: estimates. Let G be a finite abelian group and let ρ ∈ [1, diam(G)]. For ρ ≥ 4 the exact values of t_{ρ}(G) and s_{ρ}(G) are likely to depend — in an increasingly complicated way — on the algebraic structure of G. Nevertheless, some general estimates in terms of ρ and |G| can be given. To some extent such estimates compensate for the lack of explicit formulae as those we were able to provide for ρ ≤ 3. Moreover, the bounds given by the following proposition are used in the proofs of several of the results stated above.

Proposition 2.11. Let G be a finite abelian group, and suppose that ρ ≥ 2. Then

t_{ρ}(G) ≤ ⌊\frac{|G| − 2}{ρ − 1}⌋ + 1.

Moreover, if rk_{2}(G) ≤ 1 then

t_{ρ}(G) ≤ 2 ⌊\frac{|G| − 2}{2(ρ − 1)}⌋ + 1.

Our two final results provide further bounds.

Theorem 2.12. Let G be a finite abelian group, and suppose that ρ ≥ 4. Then s_{ρ}(G) ≤ \frac{3}{2} ρ^{−1}|G|, and equality holds if and only if G has a subgroup H such that G/H is cyclic of order 2ρ. Indeed, the following assertions are equivalent:

(i) A is a generating set for G satisfying diam_{A}(G) ≥ ρ and |A| = \frac{3}{2} ρ^{−1}|G|; (ii) A = (−g + H) ∪ H ∪ (g + H), where H is a subgroup of G such that G/H is

cyclic of order 2ρ, and g is an element of G such that g + H is a generator of G/H.

This theorem shows that the maximum possible cardinality of a generating set A with diam_{A}(G) ≥ ρ is \frac{3}{2} ρ^{−1}|G| and it describes the structure of all A with precisely this cardinality. Our next result goes beyond this, establishing the structure of those generating sets A with diam_{A}(G) ≥ ρ and |A^{±}| > \frac{4}{3ρ−1} |G|.

GENERATING AN ABELIAN GROUP 9

Theorem 2.13. Let G be a finite abelian group, and suppose that ρ ≥ 4. If A is a generating set for G such that diam_{A}(G) ≥ ρ and |A^{±}| > 4|G|/(3ρ − 1), then there exist H ≤ G and g ∈ G satisfying the following conditions:

(i) A ⊆ (−g + H) ∪ H ∪ (g + H), and |A^{±}| > (3 − \frac{ρ−3}{3ρ−1})|H|; (ii) G/H is cyclic of order 2ρ ≤ |G/H| ≤ \frac{9}{4} ρ − 1, and g + H generates G/H.

3. Context and motivation

As far as we know, diameters of finite groups have never been studied systematically. Nevertheless, many individual problems have been considered and to a certain extent solved. We provide several selected examples, mainly to illustrate the various interconnections with other areas of research.

A lot of attention has been given to homocyclic groups of exponent 2, that is groups isomorphic to ℤ_{2}^{r} for some r ∈ ℕ_{0}. There are at least three good reasons for this.

(i) Connections with the Covering Radius in Coding Theory. There is a natural correspondence between generating sets A for ℤ_{2}^{r} and linear binary block codes of codimension r and minimum distance d ≥ 3. (Given such a set A, one can arrange its non-zero elements in columns to obtain a check matrix of the code associated to A. For more details, see [4, Section 18.1] or [5].) The length of the code corresponding to A is |A \ {0}| and its covering radius is diam_{A}(ℤ_{2}^{r}). This shows that codes of minimum distance d ≥ 3, co-dimension r, and covering radius at least ρ exist if and only if ρ ∈ [1, r]; in this case the maximum possible length of such a code is s_{ρ}(ℤ_{2}^{r}) − 1. (ii) Connections with Caps in Projective Geometries. A cap in a projective geometry is a collection of points no three of which are collinear. In a finite projective geometry PG(r − 1, 2) over the field with two elements, points can be identified with the non-zero elements of ℤ_{2}^{r}, and then caps correspond to subsets A ⊆ ℤ_{2}^{r} \ {0} such that no three elements of A add up to zero. Evidently, if A is a cap, then for any a ∈ A we have a ∉ ⟨A + a⟩_{3}, whence diam_{A+a}(ℤ_{2}^{r}) ≥ 4; moreover, if A is not contained in a hyperplane of PG(r − 1, 2), then A + a generates ℤ_{2}^{r}. Conversely, suppose that B is a generating set for ℤ_{2}^{r} such that diam_{B}(ℤ_{2}^{r}) ≥ 4 and 0 ∈ B. Then for any g ∈ ℤ_{2}^{r} \ ⟨B⟩_{3} the set A := B + g is a cap, not contained in a hyperplane. Therefore the maximum size of a cap, not contained in a hyperplane, is s_{4}(ℤ_{2}^{r}). For (much) more on caps we refer the reader to [2, 7]. (iii) Connections with Sum-free Sets in Combinatorial Number Theory. A subset A ⊆ G of an abelian group G is said to be sum-free if no two elements of A add up to another element of A. For G = ℤ_{2}^{r} this reduces to a_{1} + a_{2} + a_{3} ≠ 0 for all a_{1}, a_{2}, a_{3} ∈ A.

10 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

As shown above, sets with this property are translates of sets of diameter greater than three. Thus the maximum size of a sum-free subset of ℤ_{2}^{r}, not contained in any coset of any proper subgroup, is s_{4}(ℤ_{2}^{r}). More information on sum-free subsets of ℤ_{2}^{r} can be found in [3].

The remarks in (i) and (iii) lead to further connections with coding theory: it is not difficult to see that the code C, corresponding to a maximal (under inclusion) sum-free subset of ℤ_{2}^{r}, has minimum distance d ∈ {4, 5} and covering radius ρ = 2. If d = 5, then C is a perfect code; in fact, it is known that the only code with d = 5 and ρ = 2 is the repetition code of length 5, which has co-dimension r = 4. For r > 4 we necessarily have d = 4, and C is a quasi-perfect code. Thus s_{4}(ℤ_{2}^{r}) can be interpreted as the maximum length of a “non-trivial” quasi-perfect code of co-dimension r and covering radius ρ = 2. (“Trivial” quasi-perfect codes correspond to sum-free sets that are complements of index two subgroups. These codes are extensions of the Hamming codes.)

In their remarkable paper [6], Davydov and Tombak have shown that

t_{4}(ℤ_{2}^{r}) = 2^{r−2} + 1 and s_{4}(ℤ_{2}^{r}) = 5 · 2^{r−4}  (3.1)

for r ≥ 4. We note that the first of these equalities is much subtler than the second one. Indeed, the value of s_{4}(ℤ_{2}^{r}) was re-established independently by other authors [2, 3], whereas — to our knowledge — no alternative proof of the formula for t_{4}(ℤ_{2}^{r}) has been found. Using the first of equations (3.1), Davydov and Tombak were able to treat several related problems; for instance, they found all possible lengths n ≥ 2^{r−1} + 1 of quasi-perfect codes of co-dimension r and covering radius ρ = 2.

For ρ ≥ 5, until recently only estimates and no precise formulae for s_{ρ}(ℤ_{2}^{r}) were known; see [5, 13] or [4, Chapter 18]. The exact values are determined in a forthcoming paper by one of the present authors [11]. Concerning general bounds we mention that [8, Lemma 3] can be regarded as a precursor of our Theorem 2.12: in our notation, it asserts that

diam_{A}(G) ≤ max \{2, \frac{3|G|}{2|A|}\}

for every generating set A of a finite abelian group G.

It is worth pointing out that there are also investigations of the diameters of nonabelian finite simple groups. Apart from the 26 so-called sporadic isomorphism classes, non-abelian finite simple groups are known to fall into two categories: they are either alternating or of Lie type. In the survey [1] one finds a discussion of three types of generating sets for these groups: “worst” (giving maximal diameter), “average” (a random choice of a prescribed number of generators) and “best” (giving minimal diameter while

GENERATING AN ABELIAN GROUP 11

keeping the number of generators limited). Instead of precise formulae the authors describe asymptotic bounds, as the group order tends to infinity. One of the important, as yet unproven conjectures [1, Section 2] states that for non-abelian finite simple groups G, one has diam(G) = (log |G|)^{O(1)} as |G| → ∞.

4. Auxiliary results

For later use we list three well-known results about abelian groups. The first two are very basic lemmata, which will be used freely without further reference.

Lemma 4.1. If {g_{1}, …, g_{r}} is a generating set for a finite abelian group G, then exp(G) = lcm(ord(g_{1}), …, ord(g_{r})).

Lemma 4.2. If G is a finite abelian group and g ∈ G has order ord(g) = exp(G), then there exists a subgroup H ≤ G such that G = H ⊕ ⟨g⟩.

The next result is a much deeper theorem due to Kneser.

Theorem 4.3 (Kneser, [9, 10]; see also [12]). Let A and B be finite non-empty subsets of an abelian group G such that

|A + B| ≤ |A| + |B| − 1.

Then, letting H := π(A + B), we have

|A + B| = |A + H| + |B + H| − |H|.

Since, in the above notation, we have |A + H| ≥ |A| and |B + H| ≥ |B|, Theorem 4.3 shows that |A + B| ≥ |A| + |B| − |H|. A straightforward induction yields

Corollary 4.4. Let A_{1}, …, A_{r} be finite non-empty subsets of an abelian group G, and write H := π(A_{1} + ⋯ + A_{r}). Then we have

|A_{1} + ⋯ + A_{r}| ≥ |A_{1}| + ⋯ + |A_{r}| − (r − 1)|H|.

In particular, if A_{1} + ⋯ + A_{r} is aperiodic, then

|A_{1} + ⋯ + A_{r}| ≥ |A_{1}| + ⋯ + |A_{r}| − (r − 1).

In fact, Theorem 4.3 and Corollary 4.4 are equivalent, as the former can easily be derived from the latter. For this reason we often refer to Corollary 4.4 simply as “Kneser’s theorem”.

12 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

5. The absolute diameter

In this section we establish Theorem 2.1, Theorem 2.2, and Corollary 2.3 after proving some subsidiary results.

Lemma 5.1. Let G = G_{1} ⊕ ⋯ ⊕ G_{r} be a finite abelian group, and let A = A_{1} ∪ ⋯ ∪ A_{r} where A_{i} ⊆ G_{i} for all i ∈ [1, r]. Then

diam_{A}(G) = diam_{A_{1}}(G_{1}) + ⋯ + diam_{A_{r}}(G_{r}).

Proof. Given g = g_{1} + ⋯ + g_{r} ∈ G, with g_{i} ∈ G_{i} for all i ∈ [1, r], we have

l_{A}(g) = l_{A_{1}}(g_{1}) + ⋯ + l_{A_{r}}(g_{r}),

and the assertion follows. □

Lemma 5.2. Let n_{1}, …, n_{r} ∈ ℕ where r ≥ 2. Suppose that for every i ∈ [1, r] we have

lcm(n_{1}, …, n_{r}) > lcm(n_{1}, …, n_{i−1}, n_{i+1}, …, n_{r}).

Then

lcm(n_{1}, …, n_{r}) ≥ 2^{r−1} max{n_{i}: i ∈ [1, r]}.

Consequently,

lcm(n_{1}, …, n_{r}) > n_{1} + ⋯ + n_{r}

and

⌊\frac{lcm(n_{1}, …, n_{r})}{2}⌋ > ⌊\frac{n_{1}}{2} ⌋ + ⋯ + ⌊\frac{n_{r}}{2} ⌋ .

Proof. Without loss of generality we can assume that max{n_{i}: i ∈ [1, r]} = n_{1}. Since lcm(n_{1}, …, n_{i}) is a proper divisor of lcm(n_{1}, …, n_{i+1}) for every i ∈ [1, r − 1], we have

lcm(n_{1}, …, n_{r}) ≥ 2 lcm(n_{1}, …, n_{r−1}) ≥ 4 lcm(n_{1}, …, n_{r−2}) ≥ … ≥ 2^{r−1}n_{1}.

Next, as 2^{r−1} ≥ r, we obtain lcm(n_{1}, …, n_{r}) > n_{1} + ⋯ + n_{r}. For the last assertion we note that, if lcm(n_{1}, …, n_{r}) is odd, then so are all of n_{1}, …, n_{r}. □

Proof of Theorem 2.1. Suppose that G ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r}} where 1 ≠ m_{1} | ⋯ | m_{r}. Considering standard generating sets we already observed that diam(G) ≥ ⌊m_{1}/2⌋ + ⋯ + ⌊m_{r}/2⌋. It remains to establish the reverse inequality.

Let A be a generating set for G, and let g ∈ G. We use induction on r to verify that

l_{A}(g) ≤ ⌊m_{1}/2⌋ + ⋯ + ⌊m_{r}/2⌋.  (5.1)

For r = 0 there is nothing to prove, and we assume that r ≥ 1. Put s := |A| and write A = {a_{1}, …, a_{s}}. Renumbering the elements of A, if necessary, we find t ∈ [1, s] such that

GENERATING AN ABELIAN GROUP 13

(i) the group ⟨a_{t}, a_{t+1}, …, a_{s}⟩ contains an element a of order ord(a) = m_{r}; (ii) for every i ∈ [t, s] the group ⟨a_{t}, …, a_{i−1}, a_{i+1}, …, a_{s}⟩ does not contain any

elements of order m_{r}. For later use we note that these conditions are equivalent to

(I) lcm(ord(a_{t}), …, ord(a_{s})) = m_{r}; (II) lcm(ord(a_{t}), …, ord(a_{i−1}), ord(a_{i+1}), …, ord(a_{s})) < m_{r} for all i ∈ [t, s].

Regarding the interpretation of conditions (ii) and (II) for t = s we notice that ⟨∅⟩ = {0} and lcm(∅) = 1, in accordance with standard definitions.

We find a subgroup H ≤ G such that G = H ⊕ ⟨a⟩ and H ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r−1}}. Let β_{1}, …, β_{s} ∈ ℤ such that b_{i} := a_{i} + β_{i}a ∈ H for all i ∈ [1, s].

We note that H = ⟨b_{1}, …, b_{s}⟩. Indeed, given h ∈ H we find λ_{1}, …, λ_{s} ∈ ℤ such that

h = ∑_{i=1}^{s} λ_{i}a_{i} = ∑_{i=1}^{s} λ_{i}(b_{i} − β_{i}a) = ∑_{i=1}^{s} λ_{i}b_{i} − ( ∑_{i=1}^{s} λ_{i}β_{i})a,

and G = H ⊕ ⟨a⟩ implies that h = ∑_{i=1}^{s} λ_{i}b_{i} ∈ ⟨b_{1}, …, b_{s}⟩.

Now we are ready to prove (5.1). We find h ∈ H and ν ∈ ℤ such that g = h + νa. By the induction hypothesis, there are λ_{1}, …, λ_{s} ∈ ℤ such that h = ∑_{i=1}^{s} λ_{i}b_{i} and ∑_{i=1}^{s} |λ_{i}| ≤ ∑_{i=1}^{r−1}⌊m_{i}/2⌋. By (i), there exist μ_{t}, …, μ_{s} ∈ ℤ with |μ_{i}| ≤ ⌊ord(a_{i})/2⌋ for i ∈ [t, s] so that

g = ∑_{i=1}^{s} λ_{i}b_{i} + νa = ∑_{i=1}^{s} λ_{i}a_{i} + (ν + ∑_{i=1}^{s} λ_{i}β_{i})a = ∑_{i=1}^{t−1} λ_{i}a_{i} + ∑_{i=t}^{s} μ_{i}a_{i}.

Recalling (I) and (II), we apply Lemma 5.2 to find

l_{A}(g) ≤ ∑_{i=1}^{t−1} |λ_{i}| + ∑_{i=t}^{s} |μ_{i}| ≤ ∑_{i=1}^{r−1}⌊m_{i}/2⌋ + ∑_{i=t}^{s}⌊ord(a_{i})/2⌋ ≤ ∑_{i=1}^{r}⌊m_{i}/2⌋

as required. □

Lemma 5.3. Let G be a finite abelian group, and suppose that A ⊆ G is minimal (under inclusion) subject to diam_{A}(G) = diam(G). Then A is a standard generating set.

Proof. Suppose that G has type (m_{1}, …, m_{r}), that is G ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r}} where 1 ≠ m_{1} | ⋯ | m_{r}. We use induction on r.

The case r = 0 is trivial and we assume that r ≥ 1. Revisit the proof of Theorem 2.1; write A = {a_{1}, …, a_{s}} and define t as before. Following the original argument (while keeping in mind that the last inequality in Lemma 5.2 is strict), the equation diam_{A}(G) = diam(G) = ∑_{i=1}^{r}⌊m_{i}/2⌋ now shows that t = s, so ord(a_{s}) = m_{r}.

14 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

As in the proof of Theorem 2.1, we find H ≤ G such that G = H ⊕ ⟨a_{s}⟩, and consequently H ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r−1}}. Furthermore, for every i ∈ [1, s − 1] we find β_{i} ∈ ℤ such that b_{i} := a_{i} + β_{i}a_{s} ∈ H. By minimality of A, we have b_{i} ≠ 0, and b_{i} ≠ b_{j} (unless i = j) for all i, j ∈ [1, s − 1].

It is easily seen that B := {b_{1}, …, b_{s−1}} satisfies diam_{B}(H) = ∑_{i=1}^{r−1}⌊m_{i}/2⌋ = diam(H) and is minimal subject to this condition. By the induction hypothesis, B is a standard generating set for H. This yields s = r,

G = H ⊕ ⟨a_{r}⟩ = ⟨b_{1}⟩ ⊕ ⋯ ⊕ ⟨b_{r−1}⟩ ⊕ ⟨a_{r}⟩

and without loss of generality we may assume that ord(b_{j}) = m_{j} for all j ∈ [1, r − 1] .

To show that A is a standard generating set for G, it is enough to prove that ord(a_{j}) | m_{j}, or equivalently

m_{r} | m_{j}β_{j}  (5.2)

for all j ∈ [1, r − 1].

For a contradiction, suppose that j ∈ [1, r − 1] is an index for which (5.2) fails. Fix g ∈ G such that l_{A}(g) = diam(G) and write g = λ_{1}b_{1} + ⋯ + λ_{r−1}b_{r−1} + λa_{r}, with −m_{i}/2 < λ_{i} ≤ m_{i}/2 for i ∈ [1, r − 1]. Substituting b_{i} = a_{i} + β_{i}a_{r} we get g = λ_{1}a_{1} + ⋯ + λ_{r−1}a_{r−1} + λ_{r}a_{r} with −m_{r}/2 < λ_{r} ≤ m_{r}/2. As l_{A}(g) = ∑_{i=1}^{r}⌊m_{i}/2⌋, we actually have |λ_{i}| = ⌊m_{i}/2⌋ for all i ∈ [1, r]. Define

ε := \begin{cases}0 & if λ_{j} = m_{j}/2, \\ 1 & if λ_{j} = (m_{j} − 1)/2, \\ −1 & if λ_{j} = −(m_{j} − 1)/2. \end{cases}

and

μ_{i} := \begin{cases}λ_{i} & if i ∈ [1, r − 1], i ≠ j, \\ −λ_{j} − ε & if i = j. \end{cases}

Furthermore, choose μ_{r} ∈ ℤ such that |μ_{r}| ≤ ⌊m_{r}/2⌋ and μ_{r} ≡ λ_{r}+(μ_{j}−λ_{j})β_{j} (mod m_{r}). Notice that |μ_{j}| = |λ_{j}| + |ε| and μ_{j} ≡ λ_{j} (mod m_{j}). The latter relation implies

μ_{j}a_{j} + μ_{r}a_{r} = μ_{j}(b_{j} − β_{j}a_{r}) + (λ_{r} + (μ_{j} − λ_{j})β_{j}) a_{r} = λ_{j}a_{j} + λ_{r}a_{r},

and hence g = μ_{1}a_{1} + ⋯ + μ_{r}a_{r}.

Moreover, μ_{r} ≡ λ_{r}−m_{j}β_{j} (mod m_{r}) if ε = 0, and μ_{r} ≡ λ_{r}−εm_{j}β_{j} (mod m_{r}) otherwise. From the fact that m_{j} is a proper divisor of m_{r} and m_{r} ∤ m_{j}β_{j}, it is not difficult to derive that |μ_{r}| ≤ |λ_{r}| − m_{j} + 1. Thus |μ_{j}| + |μ_{r}| ≤ |λ_{j}| + |ε| + |λ_{r}| − m_{j} + 1 < |λ_{j}| + |λ_{r}|.

Therefore we obtain g = μ_{1}a_{1} + ⋯ + μ_{r}a_{r} where ∑_{i=1}^{r} |μ_{i}| < ∑_{i=1}^{r} |λ_{i}| = l_{A}(g), a contradiction, as required. □

GENERATING AN ABELIAN GROUP 15

Lemma 5.4. (i) Let G = ℤ_{3} ⊕ℤ_{3} and put A := {(1, 0), (0, 1), (1, 1)}^{±}. Then A satisfies diam_{A}(G) = diam(G) and is maximal (under inclusion) subject to this condition. (ii) Let G = ℤ_{3} ⊕ ℤ_{3} ⊕ ℤ_{3} and put A := {(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, ε_{1}, 0), (1, 0, ε_{2})}^{±}, where ε_{1}, ε_{2} ∈ {−1, 1}. Then diam_{A}(G) < diam(G).

Proof. (i) Theorem 2.1 shows that diam(G) = 2, and the claim follows easily from A = G \ {(1, −1), (−1, 1)}. (ii) Theorem 2.1 shows that diam(G) = 3. Applying an automorphism of G if necessary, we may assume without loss of generality that ε_{1} = ε_{2} = 1. Now it is easy to check that diam_{A}(G) = 2. □

Proof of Theorem 2.2. Let A ⊆ G. If ⟨A⟩ ≠ G, then neither (i) nor (ii) holds. Now suppose that A generates G and show that assertions (i) and (ii) of the theorem are equivalent. One direction is easy: if (ii) holds, then Lemmata 5.1 and 5.4 show that diam_{A}(G) = diam_{B}(G), as wanted.

Now suppose that (i) holds, that is diam_{A}(G) = diam(G). We can assume that A^{±} = A. By Lemma 5.3, there is a standard generating set B ⊆ A.

To simplify the notation, we assume further that G = ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r}} where 1 < m_{1} | ⋯ | m_{r} and that B = {(1, 0, …, 0), …, (0, …, 0, 1)}. Let g ∈ G with l_{A}(g) = diam(G) = ∑_{i=1}^{r}⌊m_{i}/2⌋. Then certainly l_{B}(g) = ∑_{i=1}^{r}⌊m_{i}/2⌋, and so g = (λ_{1}, …, λ_{r}) for suitable λ_{1}, …, λ_{r} ∈ ℤ with |λ_{i}| = ⌊m_{i}/2⌋ for all i ∈ [1, r].

Now suppose that a = (α_{1}, …, α_{r}) ∈ A \ B^{±}. Then a has at least two non-zero components. If it had more than two non-zero components, then l_{B}(g + a) or l_{B}(g − a) would be less than l_{B}(g)−1, a contradiction to l_{A}(g) = l_{B}(g). So exactly two components of a are non-zero, say α_{i} and α_{j} where i < j.

Moreover, we must have α_{i}, α_{j} ∈ {−1, 1}, because otherwise l_{B}(g + a) or l_{B}(g − a) would again be less than l_{B}(g) − 1. Our next aim is to show that m_{i} = m_{j} = 3.

If one of m_{i}, m_{j} were even, then l_{B}(g + a) or l_{B}(g − a) would be less than l_{B}(g) − 1, a contradiction. If m_{i} and m_{j} were both greater than 4, then l_{B}(g + 2a) or l_{B}(g − 2a) would be less than l_{B}(g) − 2, impossible. If m_{i} = 3 and m_{j} > 3, then either one of l_{B}(g + a), l_{B}(g − a) would be less than l_{B}(g) − 1 or one of l_{B}(g + 2a), l_{B}(g − 2a) would be less than l_{B}(g) − 2, again a contradiction.

The only remaining possibility is m_{i} = m_{j} = 3, and in view of Lemma 5.1, we are reduced to the case where G is a homocyclic group of exponent 3. Now (ii) follows from Lemma 5.4. □

Proof of Corollary 2.3. We have to bound the size of A ⊆ G satisfying diam_{A}(G) = diam(G). For brevity, we write ν_{2} := ν_{2}(G), ν_{3} := ν_{3}(G), and r := rk(G). Since A

16 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

generates G, we certainly have r ≤ |A|, and it remains to show that |A| ≤ 1 + 2r − ν_{2} + 2⌊ν_{3}/2⌋.

Based upon Theorem 2.2, we pick a standard generating set B = {b_{1}, …, b_{r}} for G such that

A ⊆ (B ∪ {b_{2i−1} + b_{2i}: i ∈ [1, ν_{3}/2]})^{±}.

First suppose that ν_{3} = 0. Then we have A ⊆ B^{±}, and B^{±} is the disjoint union of {0}, {b_{i}: i ∈ [1, ν_{2}]}, {b_{i}: i ∈ [ν_{2} + 1, r]}, and {−b_{i}: i ∈ [ν_{2} + 1, r]}. This gives |A| ≤ 1 + ν_{2} + 2(r − ν_{2}) = 1 + 2r − ν_{2}, as wanted.

Now suppose that ν_{3} ≠ 0. Then ν_{2} = 0, and the set (B ∪ {b_{2i−1} + b_{2i}: i ∈ [1, ν_{3}/2]})^{±} is the disjoint union of {0}, B, −B, {b_{2i−1} + b_{2i}: i ∈ [1, ν_{3}/2]}, and {−(b_{2i−1} + b_{2i}): i ∈ [1, ν_{3}/2]}. This gives |A| ≤ 1 + 2r + 2⌊ν_{3}/2⌋, completing the proof. □

6. The size of small diameter sets, I: First results

Let G be a finite abelian group, and suppose that ρ ∈ [2, diam(G)]. In this section we collect some general observations regarding the invariants t_{ρ}(G) and s_{ρ}(G), and we determine them completely for ρ = 2. The assertions of Lemma 2.4, Example 2.5, Proposition 2.6, Corollary 2.8, and Proposition 2.11 will be proved.

We start with Lemma 2.4, explaining the relation between t_{ρ}(G) and s_{ρ}(G).

Proof of Lemma 2.4. Recall that ρ ∈ [2, diam(G)]. We have to show that

s_{ρ}(G) = max{|H| · t_{ρ}(G/H): H ≨ G}.

Suppose that A is a ρ-maximal generating set for G, and write H := π(A) ≨ G. Then the image \overline{A} of A under the canonical homomorphism G → G/H is ρ-maximal in G/H, non-zero, and aperiodic; see the discussion in Section 2.2. We get t_{ρ}(G/H) ≥ |\overline{A}| = |A|/|H|, and if A is chosen so that |A| = s_{ρ}(G), this yields

s_{ρ}(G) ≤ |H| · t_{ρ}(G/H).

Conversely, let H ≨ G and suppose that \overline{A} is an aperiodic ρ-maximal generating set for G/H. Let A denote the full pre-image of \overline{A} in G under the canonical homomorphism G → G/H. Then A is a generating set for G with diam_{A}(G) ≥ ρ. If \overline{A} is chosen so that |\overline{A}| = t_{ρ}(G/H), we get

s_{ρ}(G) ≥ |A| = |H| · |\overline{A}| = |H| · t_{ρ}(G/H).
□

In connection with the equation t_{1}(G) = 0 it was indicated that t_{ρ}(G) may also vanish for certain ρ ∈ [2, diam(G)]. Example 2.5 describes a situation of this kind.

GENERATING AN ABELIAN GROUP 17

Explanation of Example 2.5. Let G = ℤ_{2} ⊕ ℤ_{2^{n+1}} with n ≥ 2. Theorem 2.1 shows that diam(G) = 1 + 2^{n}. Let A ⊆ G be maximal subject to ⟨A⟩_{2^{n}−1} ≠ ⟨A⟩ = G; we have to show that A is periodic.

By maximality, we have A = A^{±}. Since A generates G, there exists an element a_{1} ∈ A of order ord(a_{1}) = 2^{n+1}, and furthermore there exists an element a_{2} ∈ A such that a_{2} ∉ ⟨a_{1}⟩. Without loss of generality, we may assume that a_{1} = (0, 1) and a_{2} = (1, α) with 0 ≤ α ≤ 2^{n}.

Notice that, whenever (1, β) ∈ A (this holds for instance for β = α), then

\begin{aligned}G \ ⟨A⟩_{2^{n}−1} & ⊆ (ℤ_{2} ⊕ ℤ_{2^{n+1}}) \ ⟨(1, β), (0, 1)⟩_{2^{n}−1} \\ & ⊆ \{(0, 2^{n}), (1, 2^{n} − β), (1, 2^{n} − 1 − β), (1, 2^{n} + 1 − β)\}^{±}, \end{aligned}  (6.1)

and because ⟨A⟩_{2^{n}−1} ≠ G, at least one of (0, 2^{n}), (1, 2^{n}−β), (1, 2^{n}−1−β), (1, 2^{n}+1−β) has length greater than 2^{n} − 1 with respect to A. Assertion. If b = (1, β) ∈ A, then b ∈ {(1, 0), (1, 1), (1, 2^{n} − 1), (1, 2^{n})}^{±}. For a contradiction, suppose that b = (1, β) ∈ A \ {(1, 0), (1, 1), (1, 2^{n} − 1), (1, 2^{n})}^{±}. Then we have 2b = (0, 2β) ∉ {(0, 0), (0, 1), (0, 2), (0, 3)}^{±}, and thus

(0, 2^{n}) − 2b = (0, 2^{n} − 2β) ∈ ⟨a_{1}⟩_{2^{n}−4},  so l_{A}(0, 2^{n}) ≤ 2^{n} − 2;
(1, 2^{n} − β) − b = (0, 2^{n} − 2β) ∈ ⟨a_{1}⟩_{2^{n}−4},  so l_{A}(1, 2^{n} − β) ≤ 2^{n} − 3;
(1, 2^{n} − 1 − β) − b = (0, 2^{n} − 1 − 2β) ∈ ⟨a_{1}⟩_{2^{n}−3}, so l_{A}(1, 2^{n} − 1 − β) ≤ 2^{n} − 2;
(1, 2^{n} + 1 − β) − b = (0, 2^{n} + 1 − 2β) ∈ ⟨a_{1}⟩_{2^{n}−3}, so l_{A}(1, 2^{n} + 1 − β) ≤ 2^{n} − 2.

This contradicts the observation following (6.1). Assertion. If c = (0, γ) ∈ A, then c ∈ {(0, 1)}^{±}. Let c = (0, γ) ∈ G \ {(0, 1)}^{±}. Then it is easily seen that ⟨a_{1}, c⟩_{2^{n}−2} = {(0, δ): δ ∈ ℤ_{2^{n+1}}}, and hence ⟨a_{1}, a_{2}, c⟩_{2^{n}−1} = G. It follows that c ∉ A, as required.

The two assertions above yield

{(0, 1), (1, α)}^{±} ⊆ A ⊆ {(0, 1), (1, 0), (1, 1), (1, 2^{n} − 1), (1, 2^{n})}^{±}.

Case 1: (1, α) = (1, 0). Because of (6.1) we certainly have (1, 2^{n} − 1), (1, 2^{n}) ∉ A. On the other hand, (0, 2^{n}) ∉ ⟨(0, 1), (1, 0), (1, 1)⟩_{2^{n}−1}. So A = {(0, 1), (1, 0), (1, 1)}^{±} has non-trivial period {(0, 0), (1, 0)}. Case 2: (1, α) = (1, 1). Again (6.1) shows that (1, 2^{n} − 1), (1, 2^{n}) ∉ A. So as in in the first case A = {(0, 1), (1, 0), (1, 1)}^{±} has non-trivial period {(0, 0), (1, 0)}. Case 3: (1, α) ∈ {(1, 2^{n} − 1), (1, 2^{n})}. Write the elements of G with respect to the generating pair ((1, 2^{n}), (0, 1)) rather than ((1, 0), (0, 1)). In these new coordinates, a_{1} is still represented by (0, 1), but a_{2} is represented by (1, 0) or (1, −1). We are reduced to either Case 1 or to Case 2. □

We now determine t_{2}(G) and s_{2}(G). Observe that diam(G) ≥ 2 if and only if |G| > 3 by Theorem 2.1.

Proof of Proposition 2.6. Let A ⊆ G. Then A is 2-maximal in G if and only if it has the form A = G \ {a, −a} for some a ∈ G \ {0}. Furthermore we have π(A) = π(G \ A), hence A is 2-maximal and aperiodic if and only if A = G \ {a, −a} for some a ∈ G with ord(a) ∉ {1, 4}.

Now, if |G| is even, then |G \ {a, −a}| = |G| − 1 for every a ∈ G with ord(a) = 2. If |G| is odd, then |G \ {a, −a}| = |G| − 2 for every a ∈ G \ {0}. □

Next we determine t_{ρ}(G) and s_{ρ}(G) for ρ = diam(G).

Proof of Corollary 2.8. Recall that G is a finite abelian group and ρ = diam(G) ≥ 2. Write r := rk(G). Then Corollary 2.3 shows that s_{ρ}(G) = 1 + 2r − ν_{2}(G) + 2 ⌊ν_{3}(G)/2⌋, and it remains to prove that t_{ρ}(G) has the same value.

In fact, Theorem 2.2 explains how to construct a ρ-maximal generating set for G: fix a standard generating set B = {b_{1}, …, b_{r}}, and put

A := (B ∪ {b_{2i−1} + b_{2i}: i ∈ [1, ν_{3}(G)/2]})^{±}.

To conclude the proof we show that A is aperiodic.

For r = 1 the claim is clear. Now consider the case r ≥ 2. First suppose that G is not homocyclic of exponent 3, or that r is odd. Then we have (A + b_{r}) ∩ A ⊆ {0, b_{r}, −b_{r}}. So {−b_{1}, −b_{r}, 0} ⊆ A implies that

π(A) ⊆ (A + b_{1}) ∩ (A + b_{r}) ∩ A = {0}.

Now suppose that G is a homocyclic group of exponent 3 and that r is even. Then by construction |A| = 1 + 2r + r ≡ 1(mod 3). As A is a union of π(A)-cosets, it follows that π(A) = {0}. □

We end this section with two more lemmata and a proof of Proposition 2.11.

Lemma 6.1. Let G be a finite abelian group of odd order, and suppose that ρ ∈ [2, diam(G)]. Then s_{ρ}(G) is odd, and t_{ρ}(G) is either zero or odd.

Proof. Let A be a ρ-maximal subset of G. Then A = A^{±}, and since G contains no elements of order two, |A| = |A^{±}| is odd. □

Lemma 6.2. Let A be a ρ-maximal subset of a finite abelian group G, where ρ ∈ [2, diam(G)]. Then π(A) = π(⟨A⟩_{τ}) for all τ ∈ [1, ρ − 1].

GENERATING AN ABELIAN GROUP 19

Proof. Clearly, we have π(A) ⊆ π(⟨A⟩_{2}) ⊆ ⋯ ⊆ π(⟨A⟩_{ρ−1}). Write H := π(⟨A⟩_{ρ−1}). Since

⟨A + H⟩_{ρ−1} = ⟨A⟩_{ρ−1} + H = ⟨A⟩_{ρ−1} ⫋ G,

by maximality of A we have A + H = A, whence H ⊆ π(A). □

Proof of Proposition 2.11. Let A be a ρ-maximal aperiodic subset of G. By Lemma 6.2 we have π(⟨A⟩_{τ}) = {0} for all τ ∈ [1, ρ − 1]. So Kneser’s theorem (Corollary 4.4) shows that

|G| − 1 ≥ |⟨A⟩_{ρ−1}| ≥ (ρ − 1)|A| − (ρ − 2),

hence |A| ≤ (|G| − 2)/(ρ − 1) + 1, proving the first assertion.

Note that the largest odd integer, not exceeding the right-hand side of this inequality, is 2⌊(|G| − 2)/(2(ρ − 1))⌋ + 1. So, if rk_{2}(G) = 0, the second assertion follows from Lemma 6.1.

Finally, suppose that rk_{2}(G) = 1, and let g denote the unique element of order two in G. Put k := ⌊(|G| − 2)/(2(ρ − 1))⌋. By the above we have

|A| ≤ \frac{|G| − 2}{ρ − 1} + 1 < 2k + 3,

and we need to show that in fact |A| ≤ 2k + 1.

For a contradiction, suppose that |A| = 2k + 2. Since 0 ∈ A = A^{±} and since |A| is even, we conclude that g ∈ A and therefore g ∈ ⟨A⟩_{τ} for all τ ∈ [1, ρ − 1]. So for these values of τ the cardinalities |⟨A⟩_{τ}| are even, too. By Lemma 6.2, the sets ⟨A⟩_{τ} are aperiodic, and Kneser’s theorem implies

|⟨A⟩_{τ}| ≥ |⟨A⟩_{τ−1}| + |A| − 1 (τ ∈ [1, ρ − 1]).

Comparing the parities of the two sides (for each of these inequalities) we get

|⟨A⟩_{ρ−1}| ≥ |⟨A⟩_{ρ−2}| + |A| ≥ ⋯ ≥ (ρ − 1)|A| = 2(ρ − 1)(k + 1) > |G| − 2.

Since |⟨A⟩_{ρ−1}| and |G| are both even, we have ⟨A⟩_{ρ−1} = G, a contradiction. □

7. The size of small diameter sets, II: Cyclic groups

Let G ≅ ℤ_{m} be the cyclic group of order m. According to Theorem 2.1 we have diam(G) = ⌊m/2⌋. In this section we prove Theorem 2.9, thus determining t_{ρ}(G) and s_{ρ}(G) for all ρ ∈ [1, m/2].

Proof of Theorem 2.9. It suffices to show that

t_{ρ}(ℤ_{m}) = 2 ⌊\frac{m − 2}{2(ρ − 1)}⌋ + 1;

20 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

the formula for s_{ρ}(ℤ_{m}) then follows from Lemma 2.4.

Set k := ⌊(m − 2)/(2(ρ − 1))⌋, so that k ≥ 1 in view of ρ ≤ m/2 and

2(ρ − 1)k + 1 ≤ (m − 2) + 1 < m.  (7.1)

By Proposition 2.11, we have t_{ρ}(ℤ_{m}) ≤ 2k + 1. Therefore, it suffices to exhibit a ρ-maximal aperiodic subset A ⊆ ℤ_{m} of cardinality |A| ≥ 2k + 1.

Put B := {−k, −k + 1, …, k}. Then (7.1) yields

⟨B⟩_{ρ−1} = {−(ρ − 1)k, −(ρ − 1)k + 1, …, (ρ − 1)k} ≠ ℤ_{m},  (7.2)

and we pick a ρ-maximal subset A ⊆ ℤ_{m} containing B. It is enough to show that A is aperiodic; in fact this will imply that A = B.

Writing H := π(A), we observe that

⟨B⟩_{ρ−1} + H ⊆ ⟨A⟩_{ρ−1} + H = ⟨A⟩_{ρ−1} ⫋ ℤ_{m}

by Lemma 6.2. On the other hand, (7.2) shows that

|⟨B⟩_{ρ−1}| = 2(ρ − 1)k + 1 > 2(ρ − 1) \frac{(m − 2)}{4(ρ − 1)} + 1 = m/2.

Thus ⟨B⟩_{ρ−1} + H ⫋ ℤ_{m} implies H = {0}, as claimed. □

For later use we record separately the case ρ = 3.

Corollary 7.1. For every m ∈ ℕ with m ≥ 6 we have

t_{3}(ℤ_{m}) = 2 ⌊\frac{m − 2}{4}⌋ + 1,

and

s_{3}(ℤ_{m}) = \begin{cases}\frac{m−1}{2} − 1 & if m ≡ 1 (mod 4), \\ \frac{m−1}{2} & if m ≡ 3 (mod 4), \\ \frac{m}{2} − 1 & if m is a power of 2, \\ \frac{m}{2} & otherwise. \end{cases}

Proof. The expression for t_{3}(ℤ_{m}) comes directly from Theorem 2.9, which also yields

s_{3}(ℤ_{m}) = \frac{m}{2} − min \{\frac{2m}{d} \{\frac{d − 2}{4}\} : d | m, d ≥ 6\} ,  (7.3)

where {x} := x − ⌊x⌋ denotes the fractional part of x ∈ ℝ.

If m = 2^{k}n with n, k ∈ ℕ and n ≥ 3 odd, then the minimum on the right hand side of (7.3) is attained for d = 2n ≡ 2(mod 4).

If m = 2^{k} with an integer k ≥ 3, then {(d − 2)/4} = 1/2 for any d | m, d ≥ 6; therefore the minimum is attained for d = m.

GENERATING AN ABELIAN GROUP 21

If m ≡ 3(mod 4), then {(d − 2)/4} ≥ 1/4 = {(m − 2)/4}; again, the minimum is attained for d = m.

Finally, suppose that m ≡ 1(mod 4). If d | m and d ≡ 1(mod 4), then

\frac{2m}{d} \{\frac{d − 2}{4}\} ≥ \frac{2m}{m} \{\frac{m − 2}{4}\} = \frac{3}{2}.

If d | m and d ≡ 3(mod 4), then d ≤ m/3, and so we have

\frac{2m}{d} \{\frac{d − 2}{4}\} ≥ \frac{2m}{m/3} \frac{1}{4} = \frac{3}{2}.

The minimum, once again, is attained for d = m. □

8. The size of small diameter sets, III: Sets of diameter 3

Let G be a finite abelian group. In this section we determine t_{3}(G) and s_{3}(G), proving Theorem 2.7.

Lemma 8.1. Let G be a finite abelian group and let H ≤ G. Then for every ρ ∈ [1, diam(G/H)] we have s_{ρ}(G) ≥ |H| · s_{ρ}(G/H). In particular, diam(G) ≥ diam(G/H).

Proof. Given ρ ∈ [1, diam(G/H)], we choose a generating subset \overline{A} ⊆ G/H such that diam\overline{A}(G/H) ≥ ρ and |\overline{A}| = s_{ρ}(G/H). Let A ⊆ G denote the full pre-image of \overline{A} under the canonical homomorphism G → G/H. Then A is a generating subset of G with diam_{A}(G) ≥ ρ and |A| = |H| · |\overline{A}| = |H| · s_{ρ}(G/H); cf. the discussion in Section 2.2. □

Lemma 8.2. Let G be a finite abelian group with diam(G) ≥ 3. Then

s_{3}(G) ≤ |G|/2.

Moreover, if |G| is odd and n := exp(G), then

s_{3}(G) ≤ \begin{cases}\frac{n−1}{2n} |G| − 1 & if n ≡ 1 (mod 4), \\ \frac{n−1}{2n} |G| & if n ≡ 3 (mod 4). \end{cases}

Proof. The first assertion is immediate from the boxing principle: if A ⊆ G satisfies |A| > |G|/2, then ⟨A⟩_{2} = 2A^{±} = G.

Now suppose that |G| is odd. Let A be a generating subset with diam_{A}(G) ≥ 3. Fix z ∈ G \ ⟨A⟩_{2} and write d := ord(z). Since z ∉ A − A, for every g ∈ G at least one of the elements g and g + z does not belong to A. Thus every ⟨z⟩-coset in G contains at most (d − 1)/2 elements of A, and therefore

|A| ≤ \frac{d − 1}{2} \frac{|G|}{d} ≤ \frac{n − 1}{2n} |G|.

The second assertion now follows from Lemma 6.1. □

22 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

Lemma 8.3. Let G be a non-trivial finite abelian group.

(i) Suppose that rk_{2}(G) = 0. Then there exists an aperiodic subset A ⊆ G such that |A| = (|G| − 1)/2 and 0 ∉ 2A.

(ii) Suppose that rk_{2}(G) > rk_{2}(2 ∗ G) and G ≅ ℤ̸_{2} ⊕ ℤ_{2}. Then t_{3}(G) ≥ |G|/2.

(iii) Suppose that rk_{2}(G) = rk_{2}(2 ∗ G) ≥ 1 and exp(G) > 4. Then t_{3}(G) ≥ |G|/2 − 1.

Proof. (i) As G contains no elements of order two, G \ {0} is the disjoint union of 2subsets of the form {g, −g} (g ∈ G \ {0}). Suppose that A ⊆ G contains exactly one element from each of these 2-subsets. Then it is immediate that |A| = (|G| − 1)/2 and 0 ∉ 2A. Since gcd(|G|, |A|) = 1, the set A is aperiodic; see Section 2.2.

(ii) Fix an element h ∈ G with ord(h) = 2 and a subgroup K ≤ G such that G = K⊕⟨h⟩. Put A := {0} ∪ (K + h) \ {h}. As |A| = |G|/2, it suffices to show that A is 3-maximal and aperiodic. The former follows from the first part of Lemma 8.2 and ⟨A⟩_{2} = G\{h}. This also yields π(A) ⊆ π(⟨A⟩_{2}) = π(G \ ⟨A⟩_{2}) = π({h}) = {0}.

(iii) Fix an element h ∈ G of order ord(h) > 4 and a subgroup K ≤ G of index [G : K] = 2 so that G = K + ⟨h⟩. Put A := {0} ∪ (K + h) \ {h, −h}. Evidently, we have |A| = |G|/2 − 1. Since |G| is divisible by four, we obtain gcd(|G|, |A|) = gcd(2, |G|/2 − 1) = 1. Therefore A is aperiodic; see Section 2.2.

It remains to show that A is 3-maximal. For this we observe that ⟨A⟩_{2} = G\{h, −h}. For a contradiction, suppose that there exists g ∈ G \ A satisfying ⟨{g} ∪ A⟩_{2} ≠ G. Then g ∈ K \ {0}, and h − g, h + g ∉ A. This implies that h − g = −h = h + g, hence 4h = 2g = 0, a contradiction. □

Lemma 8.4. Let G be a non-cyclic finite abelian group of odd order with diam(G) ≥ 3. Writing n := exp(G), we have

t_{3}(G) = \begin{cases}\frac{n−1}{2n} |G| − 1 & if n ≡ 1 (mod 4), \\ \frac{n−1}{2n} |G| & if n ≡ 3 (mod 4). \end{cases}

Proof. In view of Lemma 8.2, it suffices to construct an aperiodic generating set A for G of diameter diam_{A}(G) ≥ 3 and appropriate size.

Since G is not cyclic, we may assume that G = H⊕ℤ_{n} where {0} ≠ H ≤ G. Elements of G will be written as pairs (h, x) with h ∈ H and x ∈ ℤ_{n}.

By Lemma 8.3 (i), there exists an aperiodic subset B ⊆ H of cardinality |B| = (|H| − 1)/2 such that 0 ∉ 2B, and all the more so, 0 ∉ B. Put k := ⌊n/4⌋ so that k ≥ 1, unless n = 3 (in which case G is homocyclic of exponent 3).

If n = 4k + 1, we define

A := (H + {(0, −k + 1), (0, −k + 2), …, (0, k − 2), (0, k − 1)}) ∪ (B + {(0, k)}) ∪ (−B − {(0, k)}).

If n = 4k + 3 ≥ 7, we define

A := (H + {(0, −k + 1), (0, −k + 2), …, (0, k − 2), (0, k − 1)})

∪ (B + {(0, k), (0, k + 1)}) ∪ (−B − {(0, k), (0, k + 1)})

∪ {(0, k), (0, −k)}.

Finally, if n = 3, we define

A := (B + {(0, 1)}) ∪ (−B − {(0, 1)}) ∪ {(0, 0)}.

We have π(A) = 0. Indeed, if n ≠ 3, then projecting onto the second coordinate shows that π(A) ⊆ H, and thus π(A) ⊆ π(B) = {0}. If n = 3, it is likewise easy to see that π(A) ⊆ H and thus π(A) ⊆ π(B) = {0}.

Moreover, it is easily verified that ⟨A⟩ = G and diam_{A}(G) ≥ 3: the latter follows from

⟨A⟩_{2} ∌ \begin{cases}(0, 2k) & if n = 4k + 1, \\ (0, 2k + 1) & if n = 4k + 3. \end{cases}

Finally, we count

|A| = \begin{cases}(2k − 1)|H| + 2|B| = 2k|H| − 1 & if n = 4k + 1, \\ (2k − 1)|H| + 4|B| + 2 = (2k + 1)|H| & if n = 4k + 3 ≥ 7, \\ 2|B| + 1 = |H| & if n = 3. \end{cases}

Noticing that |H| = |G|/n we get

|A| = \begin{cases}\frac{n−1}{2n} |G| − 1 & if n ≡ 1 (mod 4), \\ \frac{n−1}{2n} |G| & if n ≡ 3 (mod 4). \end{cases}

□

Lemma 8.5. Let G be a finite abelian group with diam(G) ≥ 3 and rk_{2}(G) > rk_{2}(2∗G). Then t_{3}(G) = s_{3}(G) = |G|/2.

Proof. Lemma 8.2 shows that t_{3}(G) ≤ s_{3}(G) ≤ |G|/2, while by Lemma 8.3 (ii) we have t_{3}(G) ≥ |G|/2. □

Lemma 8.6. Let G be a finite abelian group and let A ⊆ G. Suppose that 2∗G ⊈ ⟨A⟩_{2}. Then

|A| ≤ (|G| − 2^{rk_{2}(G)})/2.

24 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

Proof. Fix g ∈ G such that 2g ∉ ⟨A⟩_{2}, and put X := {x ∈ G: 2x = 0}. Then the sets A − g, A + g, and X are pairwise disjoint, whence

|A| ≤ (|G| − |X|)/2 = (|G| − 2^{rk_{2}(G)})/2.
□

Lemma 8.7. Let G be a finite abelian group with rk_{2}(G) = rk_{2}(2∗G) ≥ 1 and exp(G) > 4. Then we have t_{3}(G) = |G|/2 − 1.

Proof. In view of Lemmata 8.2 and 8.3(iii), it suffices to show that t_{3}(G) ≠ |G|/2. For a contradiction, suppose that A is a 3-maximal aperiodic subset of G of cardinality |A| = |G|/2. Kneser’s theorem and Lemma 6.2 show that |⟨A⟩_{2}| = |G| − 1, so ⟨A⟩_{2} = G \ {h} for some h ∈ {x ∈ G: 2x = 0} ⊆ 2 ∗ G. Now by Lemma 8.6 we have |A| ≤ (|G| − 2)/2 = |G|/2 − 1, a contradiction. □

Lemma 8.8. Let G = ℤ_{4} ⊕ ⋯ ⊕ ℤ_{4} be a homocyclic group of exponent 4 and rank r ≥ 2. Suppose that A ⊆ G is a 3-maximal subset such that (2 ∗ G) ∪ ⟨A⟩_{2} ≠ G. Then A is periodic.

Proof. Choose h ∈ G \ ((2 ∗ G) ∪ ⟨A⟩_{2}), so that in particular ord(h) = 4. We claim that 2h ∈ π(A). Indeed, it is enough to show that a + 2h ∈ A for any given a ∈ A, and since A is 3-maximal this will follow from h ∉ ⟨A ∪ {a + 2h}⟩_{2}.

Since h ∉ 2 ∗ G, we have h ≠ 2(a + 2h). Since a ∈ A and h ∉ ⟨A⟩_{2}, we have h − (a + 2h) = −a − h ∉ A and h + (a + 2h) = a − h ∉ A. This shows that h ∉ ⟨A ∪ {a + 2h}⟩_{2}. □

Lemma 8.9. Let G = ℤ_{4} ⊕ ⋯ ⊕ ℤ_{4} be a homocyclic group of exponent 4 and rank r ≥ 2. Then t_{3}(G) = (|G| − \sqrt{|G|})/2 = (4^{r} − 2^{r})/2.

Proof. From Lemmata 8.6 and 8.8 it follows that t_{3}(G) ≤ (|G|−2^{rk_{2}(G)})/2 = (4^{r} −2^{r})/2. Thus, it remains to construct a 3-maximal aperiodic subset A ⊆ G of size |A| = (4^{r} − 2^{r})/2. We use induction on r.

If r = 2, then G = ℤ_{4} ⊕ ℤ_{4}, and we define

A := {(k, 0): k ∈ ℤ_{4}} ∪ {(1, 1), (−1, −1)}.

Here |A| = 6 = (16 − 4)/2, and it is readily checked that A is a 3-maximal aperiodic subset of G. Indeed, we have ⟨A⟩_{2} = G \ {(0, 2), (1, 2), (−1, 2)}.

Now suppose that r ≥ 3. We write G = H ⊕ ℤ_{4}, where H is a homocyclic group of exponent 4 and rank r − 1. By the induction hypothesis, there exists a 3-maximal aperiodic subset B ⊆ H with |B| = (4^{r−1} − 2^{r−1})/2. Put

A := {(h, 0): h ∈ H} ∪ {(b, 1): b ∈ B} ∪ {(−b, −1): b ∈ B}.

Then |A| = |H| + 2|B| = 4^{r−1} + 4^{r−1} − 2^{r−1} = (4^{r} − 2^{r})/2, and it is readily checked that A is 3-maximal and aperiodic. Indeed, we have ⟨A⟩_{2} = G \ {(h, 2): h ∉ ⟨B⟩_{2}}. □

Lemma 8.10. Let G be a finite abelian group. Suppose that G is not cyclic and rk_{2}(G) = rk_{2}(2 ∗ G) ≥ 1. Then s_{3}(G) = |G|/2.

Proof. First suppose that rk_{2}(G) = 1. Then we can write G = H ⊕ ℤ_{m}, where m is even and not a power of 2. By Lemmata 8.2 and 8.1 and Corollary 7.1 we have

|G|/2 ≥ s_{3}(G) ≥ |H| · s_{3}(ℤ_{m}) = |G|/2,

and the claim follows.

Now suppose that rk_{2}(G) ≥ 2. In this case we find H ≤ G such that G/H ≅ ℤ_{2} ⊕ℤ_{4}. Considering the set A = {(0, 0), (1, 0), (0, 1), (0, 3)} ⊆ ℤ_{2} ⊕ℤ_{4}, one concludes easily that s_{3}(ℤ_{2} ⊕ ℤ_{4}) ≥ 4, and the proof can be completed as above. □

Proof of Theorem 2.7. (i) Suppose that |G| is odd. If G is cyclic, the assertion follows from Corollary 7.1. If G is not cyclic, the assertion follows from Lemmata 8.2 and 8.4. (ii) Suppose that |G| is even. If G is cyclic, the assertion follow from Corollary 7.1. Now suppose that G is not cyclic. Then the claim regarding t_{3}(G) follows from Lemmata 8.5, 8.7, and 8.9. Finally, the claim regarding s_{3}(G) follows from Lemmata 8.5 and 8.10. □

9. The size of small diameter sets, IV: General estimates

In this section we prove Theorems 2.12 and 2.13.

Proof of Theorem 2.12. It suffices to show that s_{ρ}(G) ≤ \frac{3}{2} ρ^{−1}|G| and that (i) implies (ii). Indeed, (ii) trivially implies (i), and it is easily seen that, if (i) and (ii) are equivalent, then equality holds in s_{ρ}(G) ≤ \frac{3}{2} ρ^{−1}|G| if and only if G has a subgroup H such that G/H is cyclic of order 2ρ.

Let A be a generating set for G with diam_{A}(G) ≥ ρ. We write H := π(⟨A⟩_{ρ−1}) and note that both G and ⟨A⟩_{ρ−1} are unions of H-cosets, whence |G| ≥ |⟨A⟩_{ρ−1}|+|H|. Since

⟨A⟩_{ρ−1} = (ρ − 1)A^{±} + H = (ρ − 1)(A^{±} + H),

Kneser’s theorem yields

|⟨A⟩_{ρ−1}| ≥ (ρ − 1)|A^{±} + H| − (ρ − 2)|H|.

Combining these observations, we obtain

|G| ≥ (ρ − 1)|A^{±} + H| − (ρ − 3)|H|.  (9.1)

26 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

Since 0 ∈ A^{±} ⊈ H, the set A^{±} + H is the union of at least two H-cosets. Moreover, if A^{±} were the union of exactly two H-cosets, then A^{±} + H = H ∪ (g + H) for some g ∈ G \ H satisfying g + H = −g + H, and hence 2g ∈ H. But this would yield

G = ⟨A^{±}⟩ ⊆ ⟨A^{±} + H⟩ = H ∪ (g + H) = (ρ − 1)(A^{±} + H) = ⟨A⟩_{ρ−1} ⫋ G,

a contradiction.

We conclude that A^{±} +H consists of at least three H-cosets, and so |A^{±} +H| ≥ 3|H|. From (9.1) we obtain

|G| ≥ (ρ − 1 − \frac{1}{3} (ρ − 3))|A^{±} + H| ≥ \frac{2}{3} ρ|A|.  (9.2)

This gives the upper bound s_{ρ}(G) ≤ \frac{3}{2} ρ^{−1}|G|; it remains to show that (i) implies (ii).

To this end, in addition to our earlier assumption that A is a generating set for G with diam_{A}(G) ≥ ρ, we assume that |A| = \frac{3}{2} ρ^{−1}|G|. Then (9.2) yields A = A^{±}+H, and this set is the union of exactly three H-cosets. Consequently, there are two possibilities: either A = H ∪ (g_{1} + H) ∪ (g_{2} + H), where g_{1} + H, g_{2} + H ∈ G/H are distinct elements of order two, or A = (−g + H) ∪ H ∪ (g + H), where g + H ∈ G/H is of order greater than two. In the first case we would have

G = ⟨A⟩ = {0, g_{1}, g_{2}, g_{1} + g_{2}} + H = ⟨A⟩_{ρ−1} ⫋ G,

a contradiction. Thus we are left with the second case: A = (−g + H) ∪ H ∪ (g + H), where g + H ∈ G/H has order strictly greater than two.

Since A generates G, the quotient group G/H is cyclic and generated by g +H. Since

⋃ {kg + H: − ρ + 1 ≤ k ≤ ρ − 1} = ⟨A⟩_{ρ−1} ⫋ G,

the order of G/H is at least 2ρ. As |A| = \frac{3}{2} ρ^{−1}|G|, the estimate

|A| = 3|H| = 3 \frac{|G|}{|G/H|} ≤ 3 \frac{|G|}{2ρ} = |A|

yields |G/H| = 2ρ, as desired. □

Proof of Theorem 2.13. Let A ⊆ G be a generating set such that diam_{A}(G) ≥ ρ and |A^{±}| > 4|G|/(3ρ − 1). We set H := π(⟨A⟩_{ρ−1}) and show that there exists g ∈ G such that

(i) A ⊆ (−g + H) ∪ H ∪ (g + H), and |A^{±}| > (3 − \frac{ρ−3}{3ρ−1})|H|; (ii) G/H is cyclic of order 2ρ ≤ |G/H| ≤ \frac{9}{4} ρ − 1, and g + H generates G/H.

As in the proof of Theorem 2.12 we see that A^{±} + H consists of three H-cosets: the possibility |A^{±} + H| ≥ 4|H| is ruled out, since otherwise

|G| ≥ (ρ − 1 − \frac{1}{4} (ρ − 3))|A^{±} + H| ≥ \frac{3ρ − 1}{4} |A^{±}|,

contrary to the assumptions. Exactly as before, the quotient group G/H is cyclic of order at least 2ρ, and there exists g ∈ G such that g + H is a generator of G/H and A^{±} + H = (−g + H) ∪ H ∪ (g + H).

Finally, from

3|H| = |A^{±} + H| ≥ |A^{±}| > 4|H||G/H|/(3ρ − 1)

it follows that |G/H| ≤ \frac{9}{4}ρ − 1, and from

|A^{±}| > |H| \frac{4|G/H|}{3ρ − 1} ≥ |H| \frac{8ρ}{3ρ − 1}

we obtain |A^{±}| > (3 − (ρ − 3)/(3ρ − 1))|H|, as required. □

In fact one can go further and, given ε > 0, describe in a similar way the structure of those generating sets A for G which satisfy diam_{A}(G) ≥ ρ and |A^{±}| > (1+ε)|G|/(ρ−1). Indeed, in this case A^{±} + H consists of at most ⌈ε^{−1}⌉ H-cosets. However, for small ε the description is likely to become quite complicated.

Acknowledgment. We thank the referee for reading our manuscript so carefully. His (or her) suggestions and comments led to several improvements of exposition.

References

[1] L. Babai, G. Hetyei, W. M. Kantor, A. Lubotzky, and Á. Seress, On the diameter of finite groups, in “31st Annual Symposium on Foundations of Computer Science,” Vol. II, held in St. Louis, Missouri, 22-24 October 1990, IEEE Computer Society Press, 1990, 857–865.

[2] A. Bruen, L. Haddad, and D. Lucien, Binary codes and caps, J. Combin. Des. 6 (4) (1998), 275–284.

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

[4] G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, “Covering Codes,” North-Holland Mathematical Library, Vol. 54, North-Holland Publishing Co., Amsterdam, 1997.

[5] G. Cohen and G. Zémor, Subset sums and coding theory, in “Structure theory of set addition” (Deshouillers, Jean-Marc et al., Eds.), Astérisque, Vol. 258, Société Mathématique de France, Paris, 1999, 327–339.

[6] A. A. Davydov and L. M. Tombak, Quasiperfect linear binary codes with distance 4 and complete caps in projective geometry (Russian), Problemy Peredachi Informatsii 25 (4) (1989), 11–23. (Translation in Problems Inform. Transmission 25 (4) (1989), 265–275.)

[7] G. Faina and F. Pambianco, On the spectrum of the values k for which a complete k-cap in PG(n, q) exists, J. Geom. 62 (1–2) (1998), 84–98.

[8] Y. O. Hamidoune and Ö. J. Rödseth, On bases for σ-finite groups, Math. Scand. 78 (2) (1996), 246–254.

[9] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z. 58 (1953), 459–484.

[10] , Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen, Math. Z. 61 (1955), 429–434.

[11] V. F. Lev, Generating binary spaces, submitted.

[12] H. B. Mann, “Addition Theorems: The Addition Theorems of Group Theory and Number Theory,” Interscience Publishers, a division of John Wiley and Sons, New York, 1965.

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

Mathematisches Institut, Heinrich-Heine-Universität, 40225 Düsseldorf, Germany

  E-mail address: klopsch@math.uni-duesseldorf.de

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

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