GENERATING ABELIAN GROUPS BY ADDITION ONLY

BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

Abstract. We define the positive diameter of a finite group G with respect to a generating set A ⊆ G to be 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. This invariant, which we denote by diam_{A}^{+}(G), can be interpreted as the diameter of the Cayley digraph induced by A on G.

In this paper we study the positive diameters of a finite abelian group G with respect to its various generating sets A. More specifically, 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”.

Conceptually, the problems studied are closely related to our earlier work [4] and the results obtained shed a new light on the subject. Our motivation comes from connections with caps, sum-free sets, and quasi-perfect codes.

1. Introduction

Let G be a finite group and let A be a subset of G. Recall, that the subgroup generated by A in G is the smallest subgroup of G, containing A; in other words, it is the intersection of all subgroups containing A:

⟨A⟩ := ⋂ {H ≤ G: A ⊆ H}.

If ⟨A⟩ = G, then A is called a generating set for 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.

Since eventually we restrict to the situation where G is abelian, we use additive notation throughout. Let A_{0} := A ∪ {0}, and for every non-negative integer ρ define

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

the set of all g ∈ G representable as a sum of at most ρ elements of A. Then ⟨A_{0}⟩_{ρ}^{+} = ⟨A⟩_{ρ}^{+} for all ρ ∈ ℕ_{0} := ℕ ∪ {0}, and, evidently, these sets form an ascending chain

An essential part of our work was carried out while the first named author paid a one-week visit to the University of Haifa in May 2006. He is grateful for the hospitality experienced during his visit, and he acknowledges the financial support provided by the Deutsche Forschungsgemeinschaft.

2 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

{0} = ⟨A⟩_{0}^{+} ⊆ ⟨A⟩_{1}^{+} ⊆ … which stabilizes after finitely many steps in the group ⟨A⟩ = ⋃_{ρ≥0}⟨A⟩_{ρ}^{+}.

For every g ∈ G we define the (positive) 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 the minimum number of elements of A required to represent g as their sum. Thus, for every ρ ∈ ℕ_{0} we have

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

We define the (positive) diameter of G with respect to A as

diam_{A}^{+}(G) := min{ρ ∈ ℕ_{0} : ⟨A⟩_{ρ}^{+} = G}
= max{l_{A}^{+}(g): g ∈ G}.

Note that the notion of a diameter allows a simple graph-theoretic interpretation. Indeed, for any x, y ∈ G, the distance from x to y in the Cayley digraph induced by A on G is given by l_{A}^{+}(−x+y), and thus diam_{A}^{+}(G) is the diameter of this digraph. In this sense, diam_{A}^{+}(G) gives a quantitative measure for the “number of steps” needed 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 (positive) 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 fundamental 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 and we provide a partial answer to the second one. Our main results are collected in Section 2; the proofs are presented in Sections 3 to 7.

We remark that different notions of length and diameter result from considering all “algebraic sums” ±a_{1} ± ⋯ ± a_{n}, a_{i} ∈ A at each step of generating the group G from its subset A. This approach, leading to a significantly different theory, was pursued in [4]. In the important “classical” case, where G is of exponent 2, the two approaches are identical. Our motivation is fittingly described in [4, Section 3], explaining connections with caps, sum-free sets, and quasi-perfect codes.

2. Summary of Results

Throughout this section let G denote a finite abelian group.

2.1. The Absolute Diameter. Up to isomorphism, every finite abelian groups is characterized by its type. Suppose that G has 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). A standard generating set for G is an ordered 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].

If A is a standard generating set for G, then plainly diam_{A}^{+}(G) = ∑_{i=1}^{r}(m_{i} − 1). Perhaps not surprisingly, this is as large as possible: specifically, we have

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

diam^{+}(G) = ∑_{i=1}^{r}(m_{i} − 1).

Conversely, if A is a generating set for G with diam_{A}^{+}(G) = diam^{+}(G), then A is “nearly standard”.

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 {e_{1}, …, e_{r}} for G with the following prop-

erty: one can write A_{0} = {0, a_{1}, …, a_{r}} so that for each i ∈ [1, r], either a_{i} = e_{i}, or a_{i} = e_{i} + a_{σ(i)} with σ(i) ∈ [i + 1, r].

Moreover, if G has type (m_{1}, …, m_{r}) and if A is as in (ii), then every element g ∈ G can be uniquely written as g = ∑_{i=1}^{r} λ_{i}a_{i} with λ_{i} ∈ [0, m_{i} − 1] for all i ∈ [1, r], and then l_{A}^{+}(g) = ∑_{i=1}^{r} λ_{i}.

The assertion (ii) above describes a general procedure which allows one to construct any set A = {a_{1}, …, a_{r}} with diam_{A}^{+}(G) = diam^{+}(G) from a standard generating set {e_{1}, …, e_{r}}, starting from a_{r} = e_{r} and working the way down to a_{1}.

2.2. The Maximum Size of Large Diameter Sets. For abelian groups, Theorems 2.1 and 2.2 provide a complete solution of Problem P1. Now we address Problem P2; that is, we want to determine to what extent the size of a generating set guarantees fast generation.

4 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

Our aim is to find, for ρ ∈ ℕ, 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) < ∞}
= max{|A|: A ⊆ G such that ⟨A⟩_{ρ−1}^{+} ≠ ⟨A⟩ = G}.

The significance of this 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. 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}.

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}.

It is not difficult to see that ρ-maximal generating sets for a group G can be constructed by a “lifting process” from aperiodic ρ-maximal generating sets for the quotient groups of G.^{1} This shows that every ρ-maximal generating set is induced by an aperiodic one, and 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}.

A slightly simpler description of t_{ρ}^{+}(G) can be provided. Suppose that A ⊆ G is aperiodic and ρ-maximal, but ⟨A⟩ ≠ G. Then, being ρ-maximal, A coincides with a maximal subgroup of G. Since A is aperiodic, we have A = {0}, and G is cyclic of prime order. Thus any non-empty subset B ⊆ G, other than {0}, satisfies ⟨B⟩_{ρ−1}^{+} = G. This implies diam^{+}(G) < ρ, and consequently t_{ρ}^{+}(G) = 0. Therefore,

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

Notice that if ρ > diam^{+}(G), then also s_{ρ}^{+}(G) = 0.

1Suppose that H ≨ G, and let φ: G → G/H denote the canonical homomorphism. If \overline{A} is a generating set for G/H with 0 ∈ \overline{A}, then the full pre-image A := φ^{−1}(\overline{A}) is a generating set for G with diam_{A}^{+}(G) = diam+ ; Ā(G/H) and H ≤ π(A). Conversely, suppose that A is a generating set for G with 0 ∈ A and π(A) ≤ H. Then the image \overline{A} = φ(A) is a generating set for G/H and diam+ ; Ā(G/H) = diam_{A}^{+}(G). Furthermore, if A is ρ-maximal then so is \overline{A}, and if H = π(A) then \overline{A} is aperiodic.

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

Lemma 2.3. Let G be a finite abelian group and let ρ ≥ 2. Then

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

2.2.1. Explicit Formulae for t_{ρ}^{+}(G) and s_{ρ}^{+}(G). Suppose that ρ ∈ [1, diam^{+}(G)]. We determine t_{ρ}^{+}(G) and s_{ρ}^{+}(G) explicitly in the following cases:

(i) G is an arbitrary finite abelian group and ρ ∈ {1, 2, 3, 4, diam^{+}(G)}, with some exceptions regarding t_{4}^{+}(G);

(ii) G is a finite cyclic group and ρ ∈ [1, diam^{+}(G)] is arbitrary.

The case of G arbitrary and ρ ∈ {1, 2, 3, diam^{+}(G)} is settled by

Theorem 2.4. Let G be a finite abelian group. We have (i) t_{1}^{+}(G) = 0 and s_{1}^{+}(G) = |G|, provided that diam^{+}(G) ≥ 1; (ii) t_{2}^{+}(G) = s_{2}^{+}(G) = |G| − 1, provided that diam^{+}(G) ≥ 2; (iii) t_{3}^{+}(G) = s_{3}^{+}(G) = ⌊|G|/2⌋, provided that diam^{+}(G) ≥ 3; (iv) if ρ = diam^{+}(G) ≥ 2, then t_{ρ}^{+}(G) = s_{ρ}^{+}(G) = rk(G) + 1.

Recall that by Theorem 2.1, for every m ∈ ℕ the diameter of the cyclic group ℤ_{m} of order m is diam^{+}(ℤ_{m}) = m − 1. The precise values of t_{ρ}^{+}(ℤ_{m}) and s_{ρ}^{+}(ℤ_{m}) are established by

Theorem 2.5. Let m ∈ ℕ and ρ ∈ [2, m − 1]. Then

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

Corollary 2.6. Let p be a prime and let ρ ∈ [2, p − 1]. Then

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

The case of G arbitrary and ρ = 4 remains partially open and deserves further comments. A remarkable result of Davydov and Tombak [2] motivated by coding theory and finite geometry applications (see [1, 3] and also [7] for some extensions) shows that

t_{4}^{+}(ℤ_{2}^{r}) = 2^{r−2} + 1 and s_{4}^{+}(ℤ_{2}^{r}) = 5 · 2^{r−4};  r ≥ 4.  (2.1)

We notice that the first formula is considerably subtler than the second. Indeed, applying Lemma 2.3 one can easily compute s_{4}^{+}(ℤ_{2}^{r}) from t_{4}^{+}(ℤ_{2}^{s}) with s ≤ r.

6 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

We obtain similarly explicit formulae for abelian groups, which are not of exponent 2, except that we have been unable to determine the exact value of t_{4}^{+}(G) for some particularly tough groups G. To state our results we introduce the new invariant

η(G) := max{|H|: H ≤ G with exp(G/H) ≠ 2 and |G/H| ≡ 2 (mod 3)} ∈ ℕ_{0}.

Theorem 2.7. Let G be a finite abelian group with diam^{+}(G) ≥ 4.

(i) We have

t_{4}^{+}(G) = \begin{cases}\frac{1}{3} |G| & if 3 divides |G|, \\ \frac{1}{3} (|G| − 1) & if every divisor of |G| is congruent to 1 modulo 3. \end{cases}

(ii) If G is not of exponent 2, then

s_{4}^{+}(G) = \begin{cases}\frac{1}{3} (|G| + η(G)) & if η(G) ≠ 0, \\ \frac{1}{3} |G| & if η(G) = 0 and 3 divides |G|, \\ \frac{1}{3} (|G| − 1) & if η(G) = 0 and 3 does not divide |G|. \end{cases}

It is an interesting open problem to determine t_{4}^{+}(G) for groups G, not covered by Theorem 2.7 (i) and not of exponent 2. The first case one may wish to consider is G ≅ ℤ_{5}^{r}, r ∈ ℕ. Indeed, we have made some progress towards proving that t_{4}^{+}(ℤ_{5}^{r}) = (3 · 5^{r−1} − 1)/2 for r ≥ 2.

2.2.2. General Estimates for t_{ρ}^{+}(G) and s_{ρ}^{+}(G). Suppose that ρ ≥ 5. We expect that finding general explicit formulae for t_{ρ}^{+}(G) and s_{ρ}^{+}(G) for finite abelian groups G with diam^{+}(G) ≥ 5 is very difficult, if at all feasible. Indeed, it is likely that for increasing values of ρ, the dependence of t_{ρ}^{+}(G) and s_{ρ}^{+}(G) on the algebraic structure of G becomes overly complicated. Nevertheless, some general estimates in terms of ρ and |G| can be given; to some extent, these estimates compensate for the lack of explicit formulae as those we were able to provide for ρ ≤ 4.

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

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

The next theorem determines the maximum possible cardinality of a generating set A with diam_{A}^{+}(G) ≥ ρ and describes the structure of all sets A of this cardinality.

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

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

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

Our final result goes somewhat beyond Theorem 2.9, establishing the structure of those generating sets A with diam_{A}^{+}(G) ≥ ρ and |A| > \frac{3}{2} ρ^{−1}|G|.

Theorem 2.10. 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| > \frac{3}{2} ρ^{−1}|G|, then there exist H ≤ G and g ∈ G satisfying the following conditions:

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

2.3. Organization and List of Notation. An important tool used in our argument is Kneser’s Theorem, stated in Section 3. The proofs of our results, discussed above, are collected in Sections 4 to 7. In the Appendix we discuss an open problem, related to the quantity t_{ρ}^{+}(G).

For convenience we include a list of standard notation, used throughout the paper.

ℕ, ℕ_{0}, and ℤ the sets of positive, non-negative, and all integers, respectively.

For natural numbers m, r, n_{1}, …, n_{r}:

ℤ_{m} the group ℤ/mℤ of residues modulo m; gcd(n_{1}, …, n_{r}) the greatest common divisor of n_{1}, …, n_{r}.

For real numbers x, y:

⌊x⌋ the greatest integer not exceeding x; [x, y] the set of all integers n satisfying x ≤ n ≤ y.

For a group G, an element g ∈ G, and a subset A ⊆ G:

rk(G) the rank (i.e. the minimal number of generators) of G; ord(g) the order of g; ⟨A⟩ the subgroup of G, generated by A; π(A) the period {g ∈ G: A + g = A} of A in G.

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}.

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

8 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

3. Kneser’s Theorem

We recall here a fundamental result due to Kneser, used in the proofs of Proposition 2.8 and Theorems 2.9 and 2.10.

Theorem 3.1 (Kneser [5, 6]; see also [8]). 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|, Kneser’s Theorem shows that |A + B| ≥ |A| + |B| − |H|. A straightforward induction yields

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

|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).

4. The absolute diameter: proofs of Theorems 2.1 and 2.2

Proof of Theorem 2.1. Suppose that G ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r}} where 1 ≠ m_{1} | ⋯ | m_{r}. If A is a standard generating set for G, it is easily seen that diam_{A}^{+}(G) = ∑_{i=1}^{r}(m_{i} − 1). It remains to show that diam^{+}(G) ≤ ∑_{i=1}^{r}(m_{i} − 1).

We argue by induction on |G|. For |G| = 1 there is nothing to prove. Next, consider the special case where G is of prime exponent. Then every generating set for G necessarily contains a standard generating set, namely a basis for G regarded as a vector space, and the claim follows.

Now return to the general case |G| > 1. Let A be a generating set for G, and choose a prime p dividing m_{1}. Clearly, p∗A = {pa: a ∈ A} is a generating set for the subgroup p ∗ G = \{pg: g ∈ G\} of G. Write \overline{G} := G/(p ∗ G), so that \overline{G} is elementary abelian of exponent p and rank r, and let \overline{A} be the image of A under the natural homomorphism G → \overline{G}. Then the special case, considered above, and induction applied to the group p ∗ G yield

diam_{A}^{+}(G) ≤ diam+ ; Ā(\overline{G}) + p · diam_{p∗A}^{+}(p ∗ G)

≤ r(p − 1) + p ∑_{i=1}^{r}(m_{i}/p − 1)

= ∑_{i=1}^{r}(m_{i} − 1).

□

Proof of Theorem 2.2. Suppose that G ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r}} where 1 ≠ m_{1} | ⋯ | m_{r}, and let A ⊆ G. Without loss of generality we assume that 0 ∈ A, that is A = A_{0}.

First we verify the last assertion of the theorem; in view of Theorem 2.1, this also yields the implication from (ii) to (i). Suppose that {e_{1}, …, e_{r}} is a standard generating set for G with the property that A = {0, a_{1}, …, a_{r}}, where for each i ∈ [1, r], either a_{i} = e_{i}, or a_{i} = e_{i} + a_{σ(i)} with σ(i) ∈ [i + 1, r]. We show that for every g ∈ G there exist λ_{1}, …, λ_{r} ∈ ℕ_{0} with g = ∑_{i=1}^{r} λ_{i}a_{i}, l_{A}^{+}(g) = ∑_{i=1}^{r} λ_{i}, and λ_{i} ≤ m_{i} − 1 for all i ∈ [1, r]. As |G| = ∏_{i=1}^{r} m_{i}, this also implies the uniqueness. Fix g ∈ G, and choose μ_{1}, …, μ_{r} ∈ ℕ_{0} such that g = ∑_{i=1}^{r} μ_{i}a_{i} and l_{A}^{+}(g) = ∑_{i=1}^{r} μ_{i}. If the set J := {j ∈ [1, r]: μ_{j} ≥ m_{j}} is empty, there is nothing further to prove. Assume that J ≠ ∅ and let j := min J. As μ_{j}e_{j} = (μ_{j} − m_{j})e_{j} and l_{A}^{+}(g) = ∑_{i=1}^{r} μ_{i}, we must have a_{j} = e_{j} + a_{σ(j)} with σ(j) ∈ [j + 1, r]. But then

μ_{j}a_{j} = (μ_{j} − m_{j})a_{j} + m_{j}a_{j} = (μ_{j} − m_{j})a_{j} + m_{j}a_{σ(j)},

and replacing μ_{i} by

μ′_{i} := \begin{cases}μ_{i} & if i ∉ \{j, σ(j)\}, \\ μ_{j} − m_{j} & if i = j, \\ μ_{σ(j)} + m_{j} & if i = σ(j), \end{cases}

we arrive at g = ∑_{i=1}^{r} μ′_{i}a_{i} with l_{A}^{+}(g) = ∑_{i=1}^{r} μ′_{i} and μ′_{i} ≥ 0 for i ∈ [1, r]. Moreover, μ′_{i} = μ_{i} for i ∈ [1, j − 1] and μ′_{j} < μ_{j}. Iteration of this process finitely many times yields λ_{1}, …, λ_{r} ∈ ℕ_{0} such that g = ∑_{i=1}^{r} λ_{i}a_{i}, l_{A}^{+}(g) = ∑_{i=1}^{r} λ_{i}, and λ_{i} ≤ m_{i} − 1 for all i ∈ [1, r], as wanted.

We now assume (i), i.e. diam_{A}^{+}(G) = diam^{+}(G), and derive (ii), using induction on |G|. Clearly, there is nothing to prove if |G| = 1, and we assume that |G| > 1.

Our first claim is that A contains an element of order m_{r} = exp(G). If m_{r} is prime, then all non-zero elements of G are of order m_{r}. Suppose now that m_{r} is composite. Choose a prime p dividing m_{1}, and note that m_{r}/p > 1. Write \overline{G} := G/(p ∗ G) and let \overline{A} be the image of A under the natural homomorphism G → \overline{G}. Now revisit the proof of Theorem 2.1: our assumption diam_{A}^{+}(G) = diam^{+}(G) implies that

diam_{p∗A}^{+}(p ∗ G) = ∑_{i=1}^{r}(m_{i}/p − 1) = diam^{+}(p ∗ G).

Choose s ∈ [1, r] so that m_{1} = ⋯ = m_{s−1} = p < m_{s}. Then the group p ∗ G is of type (m_{s}/p, …, m_{r}/p) and using the induction hypothesis, applied to this group and the generating set p ∗ A, we write p ∗ A = {0, b_{s}, …, b_{r}} so that ord(b_{r}) = m_{r}/p and every element of p ∗ G has a (unique) representation as ∑_{i=s}^{r} λ_{i}b_{i}, where the coefficients satisfy 0 ≤ λ_{i} < m_{i}/p for all i ∈ [s, r]. We choose a_{r} ∈ A so that b_{r} = pa_{r} and show that ord(a_{r}) = m_{r}. Suppose, for a contradiction, that ord(a_{r}) < m_{r}. Then ord(a_{r}) is a proper divisor of m_{r} while, at the same time, ord(a_{r}) is divisible by ord(pa_{r}) = m_{r}/p. It follows that ord(a_{r}) = m_{r}/p and ⟨a_{r}⟩ = ⟨pa_{r}⟩; therefore every element of p ∗ G has a (unique) representation as ∑_{i=s}^{r−1} λ_{i}b_{i} + λ_{r}a_{r} with 0 ≤ λ_{i} < m_{i}/p for all i ∈ [s, r]. Consequently, conferring to the proof of Theorem 2.1, we have

diam_{A}^{+}(G) ≤ diam+ ; Ā(\overline{G}) + p ∑_{i=s}^{r−1}(m_{i}/p − 1) + (m_{r}/p − 1)

= r(p − 1) + p ∑_{i=s}^{r}(m_{i}/p − 1) − (p − 1)(m_{r}/p − 1)

< ∑_{i=1}^{r}(m_{i} − 1)

= diam^{+}(G),

in contradiction to (i). Thus our claim is proved: A contains an element of order m_{r}.

The next step shows among other things that |A| = r + 1. Choose a ∈ A with ord(a) = m_{r}. Recalling that in a finite abelian group every cyclic subgroup of maximal possible order admits a complement, we find a subgroup H ≤ G such that G = H ⊕⟨a⟩, and consequently H ≅ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{r−1}}. Let \overline{A} denote the image of A under the projection of G onto H along ⟨a⟩. From

diam+ ; Ā(H) + (m_{r} − 1) ≥ diam_{A}^{+}(G) = diam^{+}(G) = diam^{+}(H) + (m_{r} − 1)

it follows that diam+ ; Ā(H) = diam^{+}(H). Applying the induction hypothesis to the group H, we find a standard generating set \{h_{1}, …, h_{r−1}\} for H so that, writing \overline{A} = {0, ā_{1}, …, ā_{r−1}}, for each i ∈ [1, r − 1] we either have ā_{i} = h_{i}, or ā_{i} = h_{i} + ā_{σ(i)} with σ(i) ∈ [i + 1, r]. For every i ∈ [1, r − 1] fix arbitrarily a_{i} ∈ A with a_{i} ∈ ā_{i} + ⟨a⟩, and let a_{r} := a.

Since every element of H can be written as ∑_{i=1}^{r−1} λ_{i}ā_{i} with λ_{i} ∈ [0, m_{i} − 1] for all i ∈ [1, r − 1], every element of G has a representation as ∑_{i=1}^{r} λ_{i}a_{i} with λ_{i} ∈ [0, m_{i} − 1] for all i ∈ [1, r]. This shows that any g ∈ G with g ≠ ∑_{i=1}^{r}(m_{i} − 1)a_{i} satisfies l_{A}^{+}(g) < ∑_{i=1}^{r}(m_{i} − 1) = diam^{+}(G), and hence l_{A}^{+}( ∑_{i=1}^{r}(m_{i} − 1)a_{i}) = ∑_{i=1}^{r}(m_{i} − 1) by (i). Consequently, for any choice of λ_{i} ∈ [0, m_{i} − 1], i ∈ [1, r], we have

l_{A}^{+}( ∑_{i=1}^{r} λ_{i}a_{i}) = ∑_{i=1}^{r} λ_{i}.  (4.1)

In particular, it follows that A contains no elements, other than 0 and a_{1}, …, a_{r}.

Finally, we are ready to complete the proof of (ii). Since a_{i} ∈ h_{i} +⟨a_{i+1}, …, a_{r}⟩ for all i ∈ [1, r − 1], the set Ã := {a_{2}, …, a_{r}} generates a proper subgroup K ≨ G isomorphic to ℤ_{m_{2}} ⊕ ⋯ ⊕ ℤ_{m_{r}}, which is complemented by ⟨h_{1}⟩ in G. By (4.1) and Theorem 2.1 we have diam+ ; Ã(K) = diam^{+}(K). Therefore, applying the induction hypothesis to the group K and the generating set Ã, we find a standard generating set {e_{2}, , …, e_{r}} for K such that, renumbering the elements of Ã, if necessary, for each i ∈ [2, r] we have either a_{i} = e_{i}, or a_{i} = e_{i} + a_{σ(i)} with σ(i) ∈ [i + 1, r].

We consider two cases. If ord(a_{1}) = m_{1}, we put e_{1} := a_{1}; it is then immediate that {e_{1}, …, e_{r}} is a standard generating set for G, satisfying our requirements.

Now assume that ord(a_{1}) > m_{1}, and write a_{1} = μ_{1}h_{1} +∑_{i=2}^{r} μ_{i}e_{i} with μ_{i} ∈ [0, m_{i} −1] for all i ∈ [1, r]. As G/K ≅ ℤ_{m_{1}}, we have m_{1}a_{1} ∈ K, and, applying induction to the group K, we obtain two expressions for m_{1}a_{1}:

m_{1}a_{1} = ∑_{i=2}^{r} m_{1}μ_{i}e_{i} and m_{1}a_{1} = ∑_{i=2}^{r} λ_{i}a_{i},  (4.2)

where λ_{i} ∈ [0, m_{i} − 1] for all i ∈ [2, r] and ∑_{i=2}^{r} λ_{i} = l+ ; Ã(m_{1}a_{1}).

For each i ∈ [2, r+1] let K_{i} := ⟨e_{i}, …, e_{r}⟩ = ⟨a_{i}, …, a_{r}⟩, and notice that this provides a descending chain of subgroups with K_{2} = K. Since m_{1}a_{1} ∈ K \ {0}, we find j ∈ [2, r] such that m_{1}a_{1} ∈ K_{j} \ K_{j+1}. From m_{1}a_{1} ∈ K_{j} and (4.2) we derive that

m_{1}μ_{i} ≡ 0 (mod m_{i}) and λ_{i} = 0 for all i ∈ [2, j − 1].  (4.3)

As m_{1}a_{1} ∉ K_{j+1}, this further implies

m_{1}μ_{j} ≢ 0 (mod m_{j}).  (4.4)

Comparing (4.2) and (4.3) we obtain m_{1}μ_{j}e_{j} − λ_{j}a_{j} ∈ K_{j+1}, whence (m_{1}μ_{j} − λ_{j})e_{j} ∈ K_{j+1}. This shows that m_{1}μ_{j} ≡ λ_{j} (mod m_{j}), and therefore λ_{j} ∈ [0, m_{j} − 1] is the least non-negative residue of m_{1}μ_{j} modulo m_{j}. In view of m_{1} | m_{j} and (4.4) we conclude that λ_{j} ≥ m_{1}. On the other hand, it is not difficult to derive from (4.1) that the length function l_{A}^{+} restricted to K agrees with l+ ; Ã, and hence

m_{1} ≤ λ_{j} ≤ ∑_{i=j}^{r} λ_{i} = l+ ; Ã(m_{1}a_{1}) = l_{A}^{+}(m_{1}a_{1}) ≤ m_{1}.

This implies λ_{j} = m_{1} and λ_{i} = 0 for i ∈ [j + 1, r]; consequently we have m_{1}a_{1} = m_{1}a_{j}. Putting e_{1} := a_{1} −a_{j}, we now obtain a standard generating set {e_{1}, …, e_{r}} for G which, clearly, satisfies the requirements. □

5. Proofs of Lemma 2.3, Theorems 2.4 and 2.5, and Proposition 2.8

Proof of Lemma 2.3. We have to show that

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

If ρ > diam^{+}(G), then s_{ρ}^{+}(G) = 0 and t_{ρ}^{+}(G/H) = 0 for all H ≨ G; assume now that ρ ∈ [2, diam^{+}(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. 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).
□

Proof of Theorem 2.4. (i) If diam^{+}(G) ≥ 1, then G is not trivial and the only 1-maximal subset of G is G itself; so t_{1}^{+}(G) = 0 and s_{1}^{+}(G) = |G|. (ii) Suppose that diam^{+}(G) ≥ 2, or equivalently |G| > 2. Fix a non-zero element g ∈ G and set A := G \ {g}. Then A is aperiodic, generating, and ⟨A⟩_{1}^{+} = A_{0} = A ≠ G. Thus t_{2}^{+}(G) = s_{2}^{+}(G) = |G| − 1. (iii) Suppose that diam^{+}(G) ≥ 3, which by Theorem 2.1 is equivalent to G ≅ ℤ_{4} or |G| ≥ 5. If A ⊆ G satisfies |A| > |G|/2, then ⟨A⟩_{2}^{+} ⊇ 2A = G by the box principle. Thus s_{3}^{+}(G) ≤ ⌊|G|/2⌋, and to complete the proof it suffices to construct an aperiodic generating subset A ⊆ G of cardinality |A| = ⌊|G|/2⌋ such that ⟨A⟩_{2}^{+} ≠ G.

GENERATING GROUPS BY ADDITION 13

Assume first that G has even order. Fix a subgroup H ≤ G with |G/H| = 2 and choose an element g ∈ G \ H. Set A := {0} ∪ (g + H) \ {g}. Clearly, we have ⟨A⟩ = G and |A| = |G|/2. Moreover it is easily seen that ⟨A⟩_{2}^{+} = 2A = G \ {g}. In particular, 2A is aperiodic, and so is A.

Now assume that G has odd order. Fix g ∈ G \ {0}, and let h ∈ G be the (unique) element satisfying 2h = g. The set G\{h} can be (uniquely) partitioned into (|G|−1)/2 pairs so that the two elements of each pair add up to g. Form a subset A ⊆ G by selecting one element out of each pair, subject to the requirement that 0 is selected (and therefore g is not). The construction ensures that |A| = (|G| − 1)/2 and g ∉ 2A = ⟨A⟩_{2}^{+}. Note that ⟨A⟩ = G, because proper subgroups of G have cardinality at most |G|/3 < |A|. Furthermore A is aperiodic in view of gcd(|A|, |G|) = 1. (iv) Suppose that ρ = diam^{+}(G) ≥ 2 and write r := rk(G). Theorem 2.2 shows that s_{ρ}^{+}(G) = r + 1 and, moreover, that, if A is a standard generating set, then A_{0} is ρmaximal. It remains to observe that the set A_{0} is aperiodic, as one can easily verify taking into account that |G| > 2. □

The following lemma prepares the proof of Proposition 2.8 which, in turn, is used to prove Theorem 2.5.

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

Proof. Write H := π(⟨A⟩_{ρ−1}^{+}). Since A is ρ-maximal, we have A_{0} = A; consequently, ⟨A⟩_{τ}^{+} = τA holds for every τ ∈ [1, ρ − 1], and hence π(A) ≤ π(⟨A⟩_{2}^{+}) ≤ ⋯ ≤ π(⟨A⟩_{ρ−1}^{+}) = H. On the other hand, 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.8. Let A be an aperiodic ρ-maximal subset of G. By Lemma 5.1 we have π(⟨A⟩_{τ}^{+}) = {0} for all τ ∈ [1, ρ − 1]. Now Kneser’s Theorem shows that

|G| − 1 ≥ |⟨A⟩_{ρ−1}^{+}| = |(ρ − 1)A_{0}| ≥ (ρ − 1)|A| − (ρ − 2),

and hence |A| ≤ (|G| − 2)/(ρ − 1) + 1. The assertion follows. □

Proof of Theorem 2.5. It suffices to show that

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

14 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

for any given m ∈ ℕ and ρ ∈ [2, m − 1]; the formula for s_{ρ}^{+}(ℤ_{m}) then follows from Lemma 2.3.

Set k := ⌊(m − 2)/(ρ − 1)⌋, so that k ≥ 1 in view of ρ ≤ m − 1. By Proposition 2.8, we have t_{ρ}^{+}(ℤ_{m}) ≤ k + 1. Therefore, it suffices to exhibit a ρ-maximal aperiodic subset A ⊆ ℤ_{m} of cardinality |A| ≥ k + 1. Put B := {0, 1, …, k} ⊆ ℤ_{m}, and let A be a ρ-maximal subset of ℤ_{m}, containing B. It is enough to show that A is aperiodic; in fact this will imply that A = B.

Writing H := π(A), we obtain

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

Now ⟨B⟩_{ρ−1}^{+} = {0, 1, …, (ρ − 1)k} and in particular

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

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

6. 4-maximal sets: proof of Theorem 2.7

We begin with an easy consequence of Proposition 2.8.

Lemma 6.1. Let G be a finite abelian group, and let n ∈ ℕ. If n | exp(G) and n ≤ |G|/3, then t_{n+1}^{+}(G) = |G|/n.

Proof. By Proposition 2.8 it suffices to construct an aperiodic (n + 1)-maximal generating set A for G of cardinality |A| = |G|/n.

Clearly, there is a surjective homomorphism from G onto the group ℤ_{n}. Let H be the kernel of this homomorphism, so that H is a proper subgroup of G with |H| ≥ 3. Choose g ∈ G such that g + H generates G/H, and put A := {0} ∪ (g + H) \ {g}. Evidently, we have |A| = |H| = |G|/n, and |H| ≥ 3 implies that ⟨A⟩ = G. Furthermore, ⟨A⟩_{n}^{+} = G \ {g} and A is maximal with this property. Finally, Lemma 5.1 shows that A is aperiodic. □

Now let G be a finite abelian group with diam^{+}(G) ≥ 4. Proposition 2.8 and Lemma 2.3 show that

t_{4}^{+}(G) ≤ ⌊\frac{|G| + 1}{3}⌋ ,  (6.1)
s_{4}^{+}(G) ≤ max{(|G|/d) · ⌊(d + 1)/3⌋ : d divides |G|}.

Our guiding idea is that in many situations these inequalities are sharp.

GENERATING GROUPS BY ADDITION 15

Proof of Theorem 2.7. (i) If 3 divides |G|, then Lemma 6.1 implies that t_{4}^{+}(G) = |G|/3, unless |G| = 6 in which case G is cyclic and t_{4}^{+}(G) = 2 by Theorem 2.5. Assume now that every divisor of |G| is congruent to 1 modulo 3.

We argue by induction on rk(G). If rk(G) = 1, then G is cyclic and Theorem 2.5 yields t_{4}^{+}(G) = (|G| − 1)/3. Now suppose that rk(G) ≥ 2. We write G = G_{1} ⊕ G_{2}, where G_{1} is cyclic of order m ≡ 1(mod 3) and rk(G_{2}) = rk(G) − 1. To simplify the notation we assume that G_{1} = ℤ_{m}. Then A_{1} := {0, 1, …, (m − 4)/3} is an aperiodic 4-maximal subset of G_{1} with |A_{1}| = (|G_{1}| − 1)/3. By induction we find an aperiodic 4-maximal subset A_{2} ⊆ G_{2} with |A_{2}| = (|G_{2}| − 1)/3. We define

A := (A_{1} + G_{2}) ∪ ({(m − 1)/3} + A_{2}) ⊆ G.

Clearly, we have |A| = |A_{1}||G_{2}|+|A_{2}| = (|G|−1)/3 and hence A is aperiodic. Moreover, it is easily seen that G \ ⟨A⟩_{3}^{+} = {m − 1} + (G_{2} \ ⟨A_{2}⟩_{3}^{+}) and A is 4-maximal. Thus t_{4}^{+}(G) ≥ |A| = (|G| − 1)/3; the reverse inequality holds by (6.1).

(ii) Recall that by the assumption G is not of exponent 2, and that

η(G) := max{|H|: H ≤ G with exp(G/H) ≠ 2 and |G/H| ≡ 2 (mod 3)}.

Proposition 2.8 and the results (2.1) of Davydov-Tombak show that for every H ≨ G we have

|H| · t_{4}^{+}(G/H) ≤ \begin{cases}\frac{1}{3} |G| & if |G/H| ≡ 0 (mod 3), \\ \frac{1}{3} (|G| − |H|) & if |G/H| ≡ 1 (mod 3), \\ \frac{1}{3} (|G| + |H|) & if |G/H| ≡ 2 (mod 3) and exp(G/H) ≠ 2, \\ \frac{1}{4} (|G| + 4|H|) & if |G/H| ≡ 2 (mod 3), exp(G/H) = 2, \\ & and rk(G/H) ≥ 4, \\ 0 & if G/H is isomorphic to a subgroup of ℤ_{2}^{3}. \end{cases}

Observe that in the fourth case, i.e. when G/H ≅ ℤ_{2}^{r} with r ≥ 4, we have (|G| + 4|H|)/4 ≤ (|G| − |H|)/3. Thus Lemma 2.3 yields

s_{4}^{+}(G) ≤ \begin{cases}\frac{1}{3}(|G| + η(G)) & if η(G) ≠ 0, \\ \frac{1}{3}|G| & if η(G) = 0 and 3 divides |G|, \\ \frac{1}{3}(|G| − 1) & if η(G) = 0 and 3 does not divide |G|, \end{cases}

and it remains to establish the reverse inequalities.

Assuming first that η(G) ≠ 0, we find H ≤ G such that exp(G/H) ≠ 2, |G/H| ≡ 2 (mod 3), and |H| = η(G). Considering the prime factorization of |G/H|, we see that there are three possibilities:

(a) |G/H| = p, where p ≡ 2(mod 3) is an odd prime, and then G/H ≅ ℤ_{p};

16 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

(b) |G/H| = 2q, where q ≡ 1(mod 3) is a prime, and then G/H ≅ ℤ_{2q};

(c) |G/H| = 8, and then G/H ≅ ℤ_{2} ⊕ ℤ_{4} or G/H ≅ ℤ_{8}. In cases (a) and (b) the group G/H is cyclic of order |G|/η(G), so Lemma 2.3 and Theorem 2.5 show that

s_{4}^{+}(G) ≥ |H| · t_{4}^{+}(G/H) = η(G) · (|G|/η(G) + 1)/3 = \frac{1}{3}(|G| + η(G)).

In case (c) the claim follows similarly, noting that t_{4}^{+}(ℤ_{2} ⊕ ℤ_{4}) = t_{4}^{+}(ℤ_{8}) = 3, by Theorems 2.4 and 2.5 respectively.

Next, if η(G) = 0 and 3 divides |G|, then by (i) we have s_{4}^{+}(G) ≥ t_{4}^{+}(G) = |G|/3. Finally, suppose that η(G) = 0 and that 3 does not divide |G|. Then, clearly, |G|

has no odd prime divisors congruent to 2 modulo 3, and |G| is not a power of 2. (If G were a 2-group, then, because diam^{+}(G) ≥ 4 and G is not of exponent 2, we could map G onto ℤ_{8} or ℤ_{4} ⊕ ℤ_{2} in contradiction to η(G) = 0.) Consequently, |G| has at least one prime divisor congruent to 1 modulo 3, and so 2 does not divide |G| at all. Thus every (prime) divisor of |G| is congruent to 1 modulo 3, and the claim follows again from (i). □

7. General Estimates for t_{ρ}^{+}(G) and s_{ρ}^{+}(G):

Proofs of Theorems 2.9 and 2.10

Proof of Theorem 2.9. It suffices to show that s_{ρ}^{+}(G) ≤ \frac{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{2}{ρ+1} |G| if and only if G has a subgroup H such that G/H is cyclic of order ρ + 1.

Let A be a generating set for G with diam_{A}^{+}(G) ≥ ρ. We write H := π(⟨A⟩_{ρ−1}^{+}) and note that |G| ≥ |⟨A⟩_{ρ−1}^{+}| + |H|. Since

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

Kneser’s Theorem yields

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

Combining these observations, we obtain

|G| ≥ (ρ − 1)|A_{0} + H| − (ρ − 3)|H|.  (7.1)

Since 0 ∈ A_{0} ⊈ H, the set A_{0} + H is the union of at least two H-cosets, and so |A_{0} + H| ≥ 2|H|. From (7.1) we obtain

|G| ≥ (ρ − 1 − \frac{1}{2} (ρ − 3))|A_{0} + H| ≥ \frac{ρ + 1}{2} |A|.  (7.2)

GENERATING GROUPS BY ADDITION 17

This gives the upper bound s_{ρ}^{+}(G) ≤ \frac{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{2}{ρ+1} |G|. Then (7.2) yields A = A_{0} + H, and this set is the union of exactly two H-cosets. Consequently, A = H ∪(g +H) with some g ∈ G \ H. Since A generates G, the quotient group G/H is cyclic and generated by g + H. Since

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

the order of G/H is at least ρ + 1. Finally, in view of |A| = \frac{2}{ρ+1} |G|, the estimate

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

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

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

(i) A ⊆ H ∪ (g + H), and |A| > (3 − \frac{ρ−3}{3ρ−1})|H|; (ii) G/H is cyclic of order ρ + 1 ≤ |G/H| ≤ \frac{4}{3} ρ, and g + H generates G/H. As in the proof of Theorem 2.9, we see that A_{0} + H consists of two H-cosets: the

possibility |A_{0} + H| ≥ 3|H| is ruled out, since otherwise

|G| ≥ (ρ − 1 − \frac{1}{3} (ρ − 3))|A_{0} + H| ≥ \frac{2}{3} ρ|A|,

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

Finally, from

2|H| = |A_{0} + H| ≥ |A| > \frac{3}{2} ρ^{−1}|H||G/H|

it follows that |G/H| < \frac{4}{3} ρ and

|A| > \frac{3(ρ + 1)}{2ρ} |H| = (2 − \frac{ρ − 3}{2ρ}) |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_{0} + H consists of O(ε^{−1}) H-cosets. However, for small ε the description is likely to become quite complicated.

18 BENJAMIN KLOPSCH AND VSEVOLOD F. LEV

Appendix A. An Example: t_{ρ}^{+}(G) May Vanish

As can be seen directly from the definition, for every abelian group G and every ρ ∈ [1, diam^{+}(G)] we have s_{ρ}^{+}(G) > 0. Theorem 2.4, on the other hand, contains the observation that t_{1}^{+}(G) = 0 for every finite abelian group G. In this appendix we construct examples, illustrating that t_{ρ}^{+}(G) may vanish for large values of ρ for less trivial reasons.

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

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

By maximality, we have A = A_{0}. Since A generates G, there exists an element a_{1} ∈ A of order ord(a_{1}) = 2^{n}, 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

G \ ⟨A⟩_{2^{n}−2}^{+} ⊆ {(0, 2^{n} − 1), (1, β + 2^{n} − 2), (1, β + 2^{n} − 1)},  (A.1)

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

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

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

The two assertions above yield

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

Case 1: (1, α) = (1, 0). Because of (A.1) we certainly have (1, 2^{n−1}), (1, 2^{n−1} + 1) ∉ A. On the other hand, (0, 2^{n}−1) ∉ ⟨(0, 1), (1, 0), (1, 1)⟩_{2^{n}−2}^{+}. So A = {(0, 0), (0, 1), (1, 0), (1, 1)} has non-trivial period {(0, 0), (1, 0)}. Case 2: (1, α) = (1, 1). Again (A.1) shows that (1, 2^{n−1}), (1, 2^{n−1} + 1) ∉ A. So as in in the first case A = {(0, 0), (0, 1), (1, 0), (1, 1)} has non-trivial period {(0, 0), (1, 0)}. Case 3: (1, α) ∈ {(1, 2^{n−1}), (1, 2^{n−1} + 1)}. Write the elements of G with respect to the generating pair ((1, 2^{n−1}), (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. □

Perhaps it is feasible to classify all pairs (G, ρ) such that t_{ρ}^{+}(G) = 0, but beyond the above example nothing is known.

References

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

[2] 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.)

[3] 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.

[4] B. Klopsch and V.F. Lev, How long does it take to generate a group?, J. Algebra 261 (1) (2003), 145–171.

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

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

[7] V.F. Lev, Generating binary spaces, J. Combin. Theory, Ser. A 102 (1) (2003), 94–109.

[8] 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.

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

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

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

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