How long does it take to generate a group?

✍ Scribed by Benjamin Klopsch; Vsevolod F. Lev

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 229 KB
• Volume: 261
• Category: Article
• ISSN: 0021-8693
• DOI: 10.1016/s0021-8693(02)00671-3

✦ Synopsis

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.