How long does it take to generate a group?
Preprint
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 \cup 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.
Keywords
All Related Versions
- Version 1, 2009-11-15, ArXiv
- Published version: Journal of Algebra, 261 (1), 145.
This publication has 4 references indexed in Scilit:
- Generating binary spacesJournal of Combinatorial Theory, Series A, 2003
- Sum-free sets in vector spaces over GF(2)Journal of Combinatorial Theory, Series A, 1992
- Subset sums in binary spacesEuropean Journal of Combinatorics, 1992
- Absch tzung der asymptotischen Dichte von SummenmengenMathematische Zeitschrift, 1953