Generating set of a group

If ${\displaystyle S}$ is finite, then a group ${\displaystyle G=\langle S\rangle }$ is called finitely generated. The structure of finitely generated abelian groups in particular is easily described. Many theorems that are true for finitely generated groups fail for groups in general. It has been proven that if a finite group is generated by a subset ${\displaystyle S}$, then each group element may be expressed as a word from the alphabet ${\displaystyle S}$ of length less than or equal to the order of the group.

Every finite group is finitely generated since ${\displaystyle \langle G\rangle =G}$. The integers under addition are an example of an infinite group which is finitely generated by both 1 and −1, but the group of rationals under addition cannot be finitely generated. No uncountable group can be finitely generated. For example, the group of real numbers under addition, ${\displaystyle (\mathbb {R} ,+)}$.

Different subsets of the same group can be generating subsets. For example, if ${\displaystyle p}$ and ${\displaystyle q}$ are integers with gcd(p, q) = 1, then ${\displaystyle \{p,q\}}$ also generates the group of integers under addition by Bézout's identity.

While it is true that every quotient of a finitely generated group is finitely generated (the images of the generators in the quotient give a finite generating set), a subgroup of a finitely generated group need not be finitely generated. For example, let ${\displaystyle G}$ be the free group in two generators, ${\displaystyle x}$ and ${\displaystyle y}$ (which is clearly finitely generated, since ${\displaystyle G=\langle \{x,y\}\rangle }$), and let ${\displaystyle S}$ be the subset consisting of all elements of ${\displaystyle G}$ of the form ${\displaystyle y^{n}xy^{-n}}$ for some natural number ${\displaystyle n}$. ${\displaystyle \langle S\rangle }$ is isomorphic to the free group in countably infinitely many generators, and so cannot be finitely generated. However, every subgroup of a finitely generated abelian group is in itself finitely generated. In fact, more can be said: the class of all finitely generated groups is closed under extensions. To see this, take a generating set for the (finitely generated) normal subgroup and quotient. Then the generators for the normal subgroup, together with preimages of the generators for the quotient, generate the group.

• The multiplicative group of integers modulo 9, U₉ = {1, 2, 4, 5, 7, 8}, is the group of all integers relatively prime to 9 under multiplication mod 9. Note that 7 is not a generator of U₉, since
    ${\displaystyle \{7^{i}{\bmod {9}}\ |\ i\in \mathbb {N} \}=\{7,4,1\},}$
  while 2 is, since
    ${\displaystyle \{2^{i}{\bmod {9}}\ |\ i\in \mathbb {N} \}=\{2,4,8,7,5,1\}.}$

• On the other hand, S_n, the symmetric group of degree n, is not generated by any one element (is not cyclic) when n > 2. However, in these cases S_n can always be generated by two permutations which are written in cycle notation as (1 2) and (1 2 3 ... n). For example, the 6 elements of S₃ can be generated from the two generators, (1 2) and (1 2 3), as shown by the right hand side of the following equations (composition is left-to-right):

e = (1 2)(1 2)

(1 2) = (1 2)

(1 3) = (1 2)(1 2 3)

(2 3) = (1 2 3)(1 2)

(1 2 3) = (1 2 3)

(1 3 2) = (1 2)(1 2 3)(1 2)

• Infinite groups can also have finite generating sets. The additive group of integers has 1 as a generating set. The element 2 is not a generating set, as the odd numbers will be missing. The two-element subset {3, 5} is a generating set, since (−5) + 3 + 3 = 1 (in fact, any pair of coprime numbers is, as a consequence of Bézout's identity).

• The dihedral group of an n-gon (which has order 2n) is generated by the set {r, s}, where r represents rotation by 2π/n and s is any reflection across a line of symmetry.^[1]

• The cyclic group of order ${\displaystyle n}$, ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$, and the ${\displaystyle n}$^th roots of unity are all generated by a single element (in fact, these groups are isomorphic to one another).^[2]

• A presentation of a group is defined as a set of generators and a collection of relations between them, so any of the examples listed on that page contain examples of generating sets.^[3]

The most general group generated by a set ${\displaystyle S}$ is the group freely generated by ${\displaystyle S}$. Every group generated by ${\displaystyle S}$ is isomorphic to a quotient of this group, a feature which is utilized in the expression of a group's presentation.

An interesting companion topic is that of non-generators. An element ${\displaystyle x}$ of the group ${\displaystyle G}$ is a non-generator if every set ${\displaystyle S}$ containing ${\displaystyle x}$ that generates ${\displaystyle G}$, still generates ${\displaystyle G}$ when ${\displaystyle x}$ is removed from ${\displaystyle S}$. In the integers with addition, the only non-generator is 0. The set of all non-generators forms a subgroup of ${\displaystyle G}$, the Frattini subgroup.

If ${\displaystyle G}$ is a semigroup or a monoid, one can still use the notion of a generating set ${\displaystyle S}$ of ${\displaystyle G}$. ${\displaystyle S}$ is a semigroup/monoid generating set of ${\displaystyle G}$ if ${\displaystyle G}$ is the smallest semigroup/monoid containing ${\displaystyle S}$.

The definitions of generating set of a group using finite sums, given above, must be slightly modified when one deals with semigroups or monoids. Indeed, this definition should not use the notion of inverse operation anymore. The set ${\displaystyle S}$ is said to be a semigroup generating set of ${\displaystyle G}$ if each element of ${\displaystyle G}$ is a finite sum of elements of ${\displaystyle S}$. Similarly, a set ${\displaystyle S}$ is said to be a monoid generating set of ${\displaystyle G}$ if each non-zero element of ${\displaystyle G}$ is a finite sum of elements of ${\displaystyle S}$.

For example, {1} is a monoid generator of the set of natural numbers ${\displaystyle \mathbb {N} }$. The set {1} is also a semigroup generator of the positive natural numbers ${\displaystyle \mathbb {N} _{>0}}$. However, the integer 0 can not be expressed as a (non-empty) sum of 1s, thus {1} is not a semigroup generator of the natural numbers.

Similarly, while {1} is a group generator of the set of integers ${\displaystyle \mathbb {Z} }$, {1} is not a monoid generator of the set of integers. Indeed, the integer −1 cannot be expressed as a finite sum of 1s.

• Generating set for related meanings in other structures
• Presentation of a group
• Primitive element (finite field)
• Cayley graph