IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES
FOR GENERATING FINITE GROUPS

arXiv:1407.0784v2 [math.CO] 1 Oct 2017

DANA C. ERNST AND NÁNDOR SIEBEN
Abstract. We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected
elements of a finite group. The first player who builds a generating set from the jointly selected
elements wins the first game. The first player who cannot select an element without building a
generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some
conjectures based on computer calculations. Our main computational and theoretical tool is the
structure diagram of a game, which is a type of identification digraph of the game digraph that
is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet
intuitive visualizations of these games that capture the complexity of the positions.

1. Introduction
Anderson and Harary [2] introduced two impartial games in which two players alternately select
previously unselected elements of a finite group until the group is generated by the chosen elements.
The first player who builds a generating set from the jointly selected elements wins the achievement
game denoted by GEN. The first player who cannot select an element without building a generating
set loses the avoidance game denoted by DNG.
In the original description of the avoidance game given in [2], the game ends when a generating
set is built. This suggests misère-play convention. We want to study both the achievement and
the avoidance game under normal-play convention. So, our version of the avoidance game does
not allow the creation of a generating set, and the game ends when there are no available moves.
Our version of the avoidance game has the same outcome as the original, and so the difference is
immaterial since Anderson and Harary do not consider game sums.
The outcome of both games was determined for finite abelian groups in [2]. Barnes [3] provides
criteria for determining the outcome of each game for an arbitrary finite group. Barnes applies his
criteria to determine the outcome of some of the more familiar finite groups, including abelian,
dihedral, symmetric, and alternating groups, although his analysis is incomplete for alternating
groups in the avoidance game.
Brandenburg studies related games in [4]. In one of the variations, two players alternate moves,
where a move consists of picking some non-identity element from a finitely generated abelian
group. The game then continues with a group that results by taking the quotient by the subgroup
generated by the chosen element. The player with the last possible move wins.
The fundamental problem in the theory of impartial combinatorial games is the determination of
the nim-number of the game. This allows for the calculation of the nim-numbers of game sums and
the determination of the outcome of the games. The major aim of this paper is the development
of some theoretical tools that allow the calculation of the nim-numbers of the achievement and
avoidance games for a variety of familiar groups.
Date: 10/3/2017.
2000 Mathematics Subject Classification. 91A46, 20D30.
Key words and phrases. impartial game, maximal subgroup, structure diagram.
1

2

DANA C. ERNST AND NÁNDOR SIEBEN

The paper is organized as follows. In Section 2, we review the basic terminology of impartial
games and establish our notation. We further our general study of avoidance and achievement
games in Sections 3 and 4, respectively. In particular, we introduce the structure diagram of a
game, which is an identification digraph of the game digraph that is compatible with the nimnumbers of the positions. Structure diagrams also provide simple but intuitive visualizations of
these games that capture the complexity of the positions. By making further identifications, we
obtain the simplified structure diagram of a game, which will be our main computational and
theoretical tool in the remainder of the paper. The main result of Section 3 states that the nimnumber of the avoidance game is 0, 1, or 3 for an arbitrary finite group (see Corollary 3.21).
Analogously, in Section 4, we show that if the order of a group is odd, then the nim-number
of the corresponding achievement game is 1 or 2 (see Corollary 4.8). We conjecture that if the
group is of even order, then the nim-number of the achievement game is in {0, 1, 2, 3, 4} (see
Conjecture 4.9). Section 5 describes the algorithms we implemented via a computer program to
generate our initial conjectures and verify our results. Sections 6, 7, and 8 contain a complete
analysis of the nim-numbers for cyclic, dihedral, and abelian groups, respectively. In Section 9,
we study the symmetric and alternating groups. In particular, we provide a description of the
nim-numbers for the avoidance game for the symmetric groups. In addition, we provide a partial
characterization for the achievement game for the symmetric groups, as well as both games for
the alternating groups. We conclude with several open questions in Section 10.
The authors thank Bret Benesh and the anonymous referee for suggestions that greatly improved
the paper.
2. Preliminaries
We briefly recall the basic terminology of impartial games to introduce our notation. A comprehensive treatment of impartial games can be found in [1, 13]. For our purposes, an impartial game is
a finite set X of positions together with a starting position and a collection {Opt(P ) ⊆ X | P ∈ X}
of possible options. Two players take turns choosing one of the available options in Opt(P ) of the
current position P . The player who encounters an empty option set cannot move and therefore
loses. All games must come to an end in finitely many turns, so we do not allow infinite lines
of play. There are two possible outcomes for an impartial game. The game is an N-position if
the next player (i.e., the player that is about to move) wins and it is a P-position if the previous
player (i.e., the player that just moved) wins.
The minimum excludant mex(A) of a set A of ordinals is the smallest ordinal not contained
in the set. The nim-number nim(P ) of a position P is the minimum excludant of the set of
nim-numbers of the options of P . That is,
nim(P ) := mex(nOpt(P )),
where nOpt(P ) := {nim(Q) | Q ∈ Opt(P )}. Note that the minimum excludant of the empty set
is 0, and so the terminal positions of a game have nim-number 0. The nim-number of a game is
the nim-number of its starting position. The nim-number of a game determines the outcome of a
game since a position P is a P-position if and only if nim(P ) = 0.
The sum of the games P and R is the game P + R whose set of options is
Opt(P + R) := {Q + R | Q ∈ Opt(P )} ∪ {P + S | S ∈ Opt(R)}.

This means that in each turn a player makes a valid move either in game P or in game Q. The
nim-number of the sum of two games can be determined as the nim-sum
nim(P + R) = nim(P ) ⊕ nim(R),

which requires binary addition without carry.

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

3

We write P = R if the outcome of P + T and R + T is the same for every game T . The
one pile NIM game with n stones is denoted by the nimber ∗n. The set of options of ∗n is
Opt(∗n) = {∗0, . . . , ∗(n − 1)}. The following fundamental result shows the significance of the
nimbers.
Theorem 2.1. (Sprague–Grundy) If P is an impartial game, then P = ∗ nim(P ).

We now recall a few well-known group-theoretic results and definitions that will be useful in the
remainder of the paper. The subgroup of a group G generated by the subset S is the intersection
of all subgroups of G containing S. Note that the empty set generates the trivial subgroup.
A maximal proper subgroup of a group G is called a maximal subgroup of G. It is clear that
every proper subgroup of a finite group is contained in a maximal subgroup. Note that the finite
requirement is necessary. For example, the group (Q, +) has no maximal subgroups. Maximal
subgroups play an important role for us because of the following easy fact.
Proposition 2.2. A subset S of a finite group is a generating set if and only if S is not contained
in any maximal subgroup.
Next, we provide a more precise overview of the achievement and avoidance games. Let G be a
finite group. We define the avoidance game DNG(G) as follows. The first player chooses x1 ∈ G
such that hx1 i =
6 G and at the kth turn, the concerned player selects xk ∈ G \ {x1 , . . . , xk−1 }, such
that hx1 , . . . , xk i 6= G. That is, a position in DNG(G) is a set of jointly selected elements that
must be a non-generating subset of G. The player who cannot select an element without building
a generating set loses the game.
In the achievement game GEN(G), the first player chooses any x1 ∈ G and at the kth turn, the
concerned player selects xk ∈ G \ {x1 , . . . , xk−1 }. That is, a position in GEN(G) is a set of jointly
selected elements. A player wins on the nth turn as soon as hx1 , . . . , xn i = G.
In this paper, we use Zn := {0, 1, . . . , n − 1} to denote the cyclic group of order n under addition
modulo n, so that Zn ∼
= Z/nZ.
Example 2.3. The trivial group Z1 has no maximal subgroups. We cannot play DNG(Z1 ) since
every subset of the group, including the empty set, is a generating set. The only position of
GEN(Z1 ) is the empty set, and so the second player wins before the first player can make a move.
This implies that GEN(Z1 ) = ∗0.

Example 2.4. Consider the avoidance game on the cyclic group Z4 . No player can choose either
1 or 3 since these elements individually generate the group. If the first player chooses 0, then the
only option for the second player is 2. After this move, the first player has no available options.
We arrive at the same conclusion if the first player chooses 2 on the opening move. Regardless, the
second player wins DNG(Z4 ), which implies that DNG(Z4 ) = ∗0. The game digraph for DNG(Z4 ) is
given in Figure 2.1(a). In the digraph, the vertices are the positions of the game, every position is
connected to its options by arrows, and every position is labeled by the nimber of the corresponding
position.
For the achievement game, it is easy to see that the first player can win on the opening move
by choosing 1 or 3. However, if the first player happens to choose 0 or 2 on the opening move,
then the second player may choose 1, 3, or the opposite choice that the first player made on the
opening move. The second player wins the game if they choose either 1 or 3. However, if the
second player makes the opposite choice between 0 and 2 that the first player made, then the first
player wins by choosing either 1 or 3. The game digraph for GEN(Z4 ) is given in Figure 2.1(b).
By looking at the top node of the digraph, we see that GEN(Z4 ) = ∗1.
We call two subsets P and Q of a group G automorphism equivalent if there is an automorphism
φ of G such that φ(P ) = Q. It is clear that an automorphism φ of G induces an automorphism

4

DANA C. ERNST AND NÁNDOR SIEBEN

∅

∅

∗0

{0}

{2}

∗1

∅

∗1

{1}

∗1

{0, 2}
∗0

{0}

∗0

{2}

∗2

{3}

∗2

{1}

∗0

∗0

∗0

∗0

∗1

∗0

{0}

∗0

{0, 3} {0, 1} {0, 2} {1, 2} {2, 3}
{0, 1, 2}

(a) DNG(Z4 )

∗1

∗0

{0, 2, 3}
∗0

(b) GEN(Z4 )

{2}

∗2

∗2

{0, 1} {0, 2} {1, 2}
∗0

∗1

∗0

{0, 1, 2}
∗0

(c) GEN(Z4 )

Figure 2.1. Game digraphs of DNG(Z4 ) and GEN(Z4 ), and representative game
digraph for GEN(Z4 ). Nimbers corresponding to each position of the game are
included. The second digraph can be created from the first by adding the dotted
arrows that represent options that create terminal positions.
of the game digraph, and so nim(P ) = nim(Q) if P and Q are automorphism equivalent. For
simplicity, we can eliminate some of the positions of a game digraph without changing the nimnumbers of the remaining positions. For each position P , the set Opt(P ) of options is partitioned
into automorphism equivalence classes. We delete all but one representative from each of these
classes. The resulting digraph will be referred to as a representative game digraph.
Example 2.5. Consider the achievement game on the cyclic group Z4 . It is clear that the subsets
{3}, {0, 3}, {2, 3}, and {0, 2, 3} are automorphism equivalent to {1}, {0, 1}, {1, 2}, and {0, 1, 3},
respectively. As a result, one possible representative game digraph for GEN(Z4 ) is provided in
Figure 2.1(c).
We define pty(n) := n mod 2. The parity of a subset of a group is defined to be the parity of the
size of the subset. Observe that an option of a position in both DNG and GEN has the opposite
parity.
3. Avoidance games
In this section we study the avoidance game DNG(G) on a finite group G. In [2], Anderson and
Harary proved the following criterion for determining the outcome of DNG(G) for a finite abelian
group.
Proposition 3.1. Let G be a finite abelian group. The first player wins DNG(G) if and only if G
is nontrivial of odd order or G ∼
= Z2k with k odd. The second player wins otherwise.
Barnes [3] reproved this result using the following criterion for determining the outcome of
DNG(G) for an arbitrary finite group G. Recall that an involution in a group is an element of
order 2.
Proposition 3.2. Let G be a nontrivial finite group. Then the first player wins DNG(G) if and
only if there exists α ∈ G such that α has odd order and hα, βi = G for every involution β ∈ G.
Note that the last condition of the previous proposition vacuously holds if the order of G is
odd. Since the first player wins precisely when DNG(G) 6= ∗0, we immediately have the following
corollary of Proposition 3.1.
Corollary 3.3. Let G be a nontrivial finite abelian group. Then DNG(G) 6= ∗0 if and only if G
has odd order or G ∼
= Z2k with k odd.

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

5

The next proposition follows immediately from Proposition 2.2.
Proposition 3.4. The positions of DNG(G) are the subsets of the maximal subgroups of G and
the terminal positions of DNG(G) are the maximal subgroups of G.
It turns out that positions that are contained in the same collection of maximal subgroups are
closely related. This motivates the next two definitions.
Definition 3.5. Let M be the set of maximal subgroups of G. The set of intersection subgroups
is defined to be the set
I := {∩N | ∅ =
6 N ⊆ M}
containing all the possible intersections of some maximal subgroups.
Note that the elements of I are in fact subgroups of G. If G is nontrivial, then the smallest
intersection subgroup is the Frattini subgroup Φ(G). Not every subgroup of G is an intersection
subgroup. For example, Φ(G) may not be trivial. The set I of intersection subgroups is partially
ordered by inclusion. We use interval notation to denote certain subsets of I. For example, if
I ∈ I, then (−∞, I) := {J ∈ I | J ⊂ I}.
Definition 3.6. For each I ∈ I let

XI := P(I) \ ∪{P(J) | J ∈ (−∞, I)}

be the collection of those subsets of I that are not contained in any other intersection subgroup
smaller than I. We let X := {XI | I ∈ I} and call an element of X a structure class.
The largest element of XI is I. The starting position ∅ is in XΦ(G) . We say that XI is terminal
if I is terminal. The parity of a structure class is defined to be pty(XI ) := pty(I).
Example 3.7. The subset P = {0} generates the trivial subgroup of G = Z4 . If I = Φ(G) = {0, 2}
is the Frattini subgroup of G, then P ∈ XI since P ⊆ I and (−∞, I) is empty. This shows that
P ∈ XI does not imply that P generates I.
Proposition 3.8. If I and J are different elements of I, then XI ∩ XJ = ∅.
Proof. Assume P ∈ XI ∩ XJ and let K := I ∩ J ∈ I. Since I 6= J, we must have K 6= I or K 6= J.
Without loss of generality, assume that K 6= I. Then P ⊆ K ∈ (−∞, I), which contradicts
P ∈ XI .

Corollary 3.9. The set X of structure classes is a partition of the set of game positions of
DNG(G).
As we shall see, the structure classes play a pivotal role in the remainder of this paper. Proposition 3.10 and Corollary 3.11 imply that the collection of structure classes is compatible with the
option relationship between game positions. This will allow us to define the structure digraph of
DNG(G) (see Definition 3.12), which will capture the option relationship among structure classes.
Then in Proposition 3.15, we show that two elements of a structure class have the same nim-number
if and only if they have the same parity. In other words, each structure class is associated with two
nim-numbers. By appending this data to the corresponding structure digraph, we can visualize
the nim-number relationship among structure classes using a structure diagram. By defining an
appropriate equivalence relation on the collection of structure classes (see Definition 3.17), we
will be able to make identifications that allow us to greatly simplify the task of computing the
nim-number of DNG(G) for a wide class of groups.
Proposition 3.10. Assume XI , XJ ∈ X and P ∈ XI 6= XJ . Then Opt(P ) ∩ XJ 6= ∅ if and only
if Opt(I) ∩ XJ 6= ∅.

6

DANA C. ERNST AND NÁNDOR SIEBEN

Proof. First, assume that Opt(P )∩XJ 6= ∅. Then there exists a g ∈ G\P such that P ∪{g} ∈ XJ .
That is, P ∪ {g} ⊆ J but P ∪ {g} is not contained in any K ∈ (−∞, J). This implies that I ⊂ J,
otherwise we would have P ⊆ I ∩ J ∈ (−∞, I), contradicting P ∈ XI . There is no K satisfying
I ∪ {g} ⊆ K ∈ (−∞, J) since we would then have P ∪ {g} ⊆ I ∪ {g} ⊆ K ∈ (−∞, J), which
contradicts P ∪ {g} ∈ XJ . Thus, I ∪ {g} ∈ XJ , which shows that Opt(I) ∩ XJ 6= ∅.
Now, assume that Opt(I) ∩ XJ 6= ∅. Then I ∪ {g} ∈ XJ for some g ∈ J \ I, that is, I ∪ {g} ⊆ J
but I ∪ {g} is not contained in any K ∈ (−∞, J). Then clearly P ∪ {g} ⊆ J. There is no K
satisfying P ∪ {g} ⊆ K ∈ (−∞, J), otherwise we would have P ⊆ K ∩ I ∈ (−∞, I) contradicting
P ∈ XI . Hence P ∪ {g} ∈ XJ , and so Opt(P ) ∩ XJ 6= ∅, as desired.

Corollary 3.11. Assume XI , XJ ∈ X and P, Q ∈ XI 6= XJ . Then Opt(P ) ∩ XJ 6= ∅ if and only
if Opt(Q) ∩ XJ 6= ∅.
This motivates the following definition.
Definition 3.12. We say that XJ is an option of XI and we write XJ ∈ Opt(XI ) if Opt(I)∩XJ =
6
∅. The structure digraph of DNG(G) has vertex set {XI | I ∈ I} and edge set {(XI , XJ ) | XJ ∈
Opt(XI )}.
If I 6= P ∈ XI , then P ∪ {g} ∈ Opt(P ) ∩ XI for all g ∈ I \ P 6= ∅. So, I is the only element of
XI without an option in XI . Note that there are no loops in the structure digraph and XΦ(G) is
the only source vertex.
Example 3.13. The set of maximal subgroups of G = Z6 is M = {{0, 2, 4}, {0, 3}}. The intersection subgroups are in I = {{0}, {0, 2, 4}, {0, 3}}. Note that Φ(G) = {0}. The elements of X
are
X{0} = {∅, {0}},

X{0,2,4} = {{2}, {4}, {0, 2}, {0, 4}, {2, 4}, {0, 2, 4}},

The structure digraph is visualized by

X{0,3} = {{3}, {0, 3}}.

X{0,2,4} ←− X{0} −→ X{0,3} .
The following lemma will be useful in the proof of Proposition 3.15.
Lemma 3.14. Let A and B be subsets of {0, 1, 2, . . .} such that mex(A) ∈ B. Then mex(A ∪
{mex(B)}) = mex(A).

Proof. Since mex(A) ∈ B, mex(B) 6= mex(A). This implies that mex(A ∪ {mex(B)}) = mex(A).

Proposition 3.15. If P, Q ∈ XI ∈ X and pty(P ) = pty(Q), then nim(P ) = nim(Q).

Proof. We proceed by structural induction. Our inductive hypothesis states that if pty(M ) =
pty(N ) and either M, N ∈ XI with |M |, |N | > min{|P |, |Q|} or M, N ∈ XJ ∈ Opt(XI ) for some
J ∈ I, then nim(M ) = nim(N ). Without loss of generality, assume that |P | ≤ |Q|.
We will consider two cases indicated by the diagrams in Figure 3.1: Q 6= I and Q = I. Each
figure is referred to as an “unfolded structure diagram” and is meant to help visualize the structure
of the proof. In the figures, each triangle represents a structure class and each horizontal band
represents the collection of subsets from the given structure class that have the same size. An
arrow from one set to another in the figure indicates that the second set is an option of the first
set. In the first case (Q 6= I), we will show that nOpt(P ) = nOpt(Q). The second case (Q = I)
is more complicated as we will only have nOpt(Q) ⊆ nOpt(P ). In this case, we will make use of
Lemma 3.14 to conclude that we still have mex(nOpt(P )) = mex(nOpt(I)).
First, assume that Q 6= I. Every option of P is either an element of XI or of some XJ ∈ Opt(XI ).
If T ∈ Opt(P ) ∩ XI , then we can choose Te ∈ Opt(Q) ∩ XI . By induction, nim(T ) = nim(Te)

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

XI

XI

.
.
.

.
.
.
P

a

P

XJ

T

b
.
.
.
Q

a
b

a

XJ

T

b

.
.
.

.
.
.
.
.
.

S

c
Te
.
.
.

.
.
.

S

c

.
.
.

T0

b
a

I
c

7

I

e
S

c

.
.
.

(a) Q 6= I

e
S
.
.
.

(b) Q = I

Figure 3.1. Unfolded structure diagrams for Proposition 3.15. We define a :=
nim(Q), b := nim(T ) and c := nim(S). Shading types represent parities.
since pty(T ) = pty(T̃ ). On the other hand, if S ∈ Opt(P ) ∩ XJ for some XJ ∈ Opt(XI ),
then by Corollary 3.11, there exists S̃ ∈ Opt(Q) ∩ XJ . Since pty(S) = pty(S̃), we must have
nim(S) = nim(S̃) by induction. We have shown that nOpt(P ) ⊆ nOpt(Q). A similar argument
shows that nOpt(Q) ⊆ nOpt(P ).
Now, assume that Q = I. If P = Q = I, then the desired result follows trivially, so assume
that P 6= Q = I. Note that this implies that |P | < |Q|. In this case, we might not have
nOpt(Q) = nOpt(P ) because Opt(I) ∩ XI = ∅. Instead we fix a T 0 ∈ XI such that I ∈ Opt(T 0 ).
Such a T 0 exists since I 6= ∅. We are going to show that nOpt(P ) = nOpt(I) ∪ {nim(T 0 )}.
First, we verify nOpt(P ) ⊆ nOpt(I) ∪ {nim(T 0 )}. Every option of P is either an element of
XI or of some XJ ∈ Opt(XI ). In the latter case, if S ∈ Opt(P ) ∩ XJ for some XJ ∈ Opt(XI ),
then there exists S̃ ∈ Opt(Q) ∩ XJ by Corollary 3.11. Since pty(S) = pty(S̃), we must have
nim(S) = nim(S̃) ∈ nOpt(I) by induction. In the former case, if T ∈ Opt(P ) ∩ XI , then
nim(T ) = nim(T 0 ) by induction and nim(T ) ∈ {nim(T 0 )}.
Now, we verify nOpt(P ) ⊇ nOpt(I) ∪ {nim(T 0 )}. Suppose Se ∈ Opt(I). Then Se ∈ XJ for some
XJ ∈ Opt(XI ) since the only options of I must exist outside XI . Then by Corollary 3.11, there
e = pty(S), we must have nim(S)
e = nim(S) by induction.
exists S ∈ Opt(P ) ∩ XJ . Since pty(S)
This implies that nOpt(I) ⊆ nOpt(P ). Since P 6= I, there exits T ∈ Opt(P ) ∩ XI . By induction,
nim(T 0 ) = nim(T ) and so {nim(T 0 )} ⊆ nOpt(P ) by induction.
Finally
nim(P ) = mex(nOpt(P )) = mex(nOpt(I) ∪ {nim(T 0 )})
= mex(nOpt(I) ∪ {mex(nOpt(T 0 ))})
= mex(nOpt(I)) = nim(Q)

by Lemma 3.14 since mex(nOpt(I)) = nim(I) ∈ nOpt(T 0 ).



The upshot of Proposition 3.15 is that each structure class is associated with two nim-numbers.
In light of this, we can append this information to a structure digraph to form a (folded) structure
diagram, which is visualized as follows. A structure class XI is represented by a triangle pointing
down if I is odd and by a triangle pointing up if I is even. The triangles are divided into a smaller

8

DANA C. ERNST AND NÁNDOR SIEBEN

∅

1

∗1

{3}

{0}

∗0

0

∗0

{3, 6} {0, 3}

1

{0, 3, 6}

0

1
0

(a)

(b)

(c)

∗1

∗1

∗0

Figure 3.2. Representative game digraph, unfolded structure diagram, and structure diagram for DNG(Z9 ).
triangle and a trapezoid. The smaller triangle represents the odd positions of XI and the trapezoid
represents the even positions of XI . The numbers are the nim-numbers of these positions. There
is a directed edge from XI to XJ provided XJ ∈ Opt(XI ).
For a nontrivial group G, Φ(G) and Φ(G) \ {e} are positions in XΦ(G) . Hence XΦ(G) contains
both even and odd positions. Corollary 3.11 now implies that every structure class contains both
even and odd positions. The nim-number of the game can be easily read from the structure
diagram. It is the number in the trapezoid part of the triangle representing the source vertex of
the structure digraph.
Example 3.16. Figure 3.2 shows a representative game digraph and the corresponding unfolded
and folded structure diagrams for DNG(Z9 ). Since Z9 only has a single maximal subgroup, there is a
unique structure class. The small triangle in the structure diagram represents the collection of odd
positions with nim-number 0. This collection includes the representative positions {0, 3, 6}, {3},
and {0}. The trapezoid represents the collection of even positions with nim-number 1. This
collection includes positions {3, 6}, {0, 3}, and ∅. Every position in a collection is connected to
another position on the next level. The chain shown in the figure ends on an odd level with the
terminal position I = {0, 3, 6}. This is why the large triangle representing XI points down and
the small triangle representing the odd positions is on the bottom.
The structure diagram can be used to find the nim-numbers. Since the only terminal position
is in the smaller triangle, these positions have nim-number 0. The positions in the trapezoid are
only connected to the positions in the smaller triangle so they have nim-number mex{0} = 1. The
non-terminal positions in the smaller triangle are only connected to positions in the trapezoid so
they have nim-number mex{1} = 0. We conclude that DNG(Z9 ) = ∗1.
We want to recognize similar structure classes.
Definition 3.17. The type of the structure class XI is the triple
type(XI ) := (pty(I), nim(P ), nim(Q))
where P, Q ∈ XI with pty(P ) = 0 and pty(Q) = 1. The option type of XI is the set
otype(XI ) := {type(XK ) | XK ∈ Opt(XI )},
and the full option type of XI is the set
Otype(XI ) := otype(XI ) ∪ {type(XI )}.
We say XI and XJ are type equivalent if type(XI ) = type(XJ ) and Otype(XI ) = Otype(XJ ).

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS
a
b

b
a

XI

9

type(XI ) (0, a, b) (1, a, b)
Figure 3.3. Visualization of structure classes and their corresponding types.
(1,0,1)
{(0,0,1),(1,3,2)}
0
1

Z1
(0,0,1)
{(0,0,1)}

Z2

Z6

Z6

Z3

Z3

Z6

Z6

Z3

1
0

Z3

Z3 × Z3

(a) Intersection subgroup poset. Subgroups
are denoted by their isomorphism types.

1
0

1
0

3
2

3
2

1
0

1
0

(1,3,2)
{(0,0,1),(1,1,0)}
3
2

3
2

1
0
(1,1,0)
∅

(0,0,1)
∅

(b) Structure diagram with
type and otype.

{(0,0,1),(1,3,2),(1,0,1)}
0
1
{(0,0,1)}

{(1,3,2), {(1,3,2), {(1,3,2), {(1,3,2),
(0,0,1), (0,0,1), (0,0,1), (0,0,1),
(1,1,0)} (1,1,0)} (1,1,0)} (1,1,0)}

{(0,0,1)} {(0,0,1)} {(0,0,1)} {(0,0,1)}

{(1,1,0)}

(c) The Otype of each structure class.

3
2

1
0

1
0

(d) Simplified structure diagram.

Figure 3.4. The process for obtaining the simplified structure diagram for
DNG(Z6 × Z3 ). The double headed arrow XΦ(G)  XZ2 indicates that XΦ(G) is
also connected to the options of XZ2 .
Once the structure digraph is known, the types of the structure classes can be computed recursively from the bottom up using the formulas type(XI ) = (pty(I), a, b), where
A = {ã | (, ã, b̃) ∈ otype(XI )},

B = {b̃ | (, ã, b̃) ∈ otype(XI )},

a := mex(B), b := mex(A ∪ {a}) if pty(I) = 0

b := mex(A), a := mex(B ∪ {b}) if pty(I) = 1.
Figure 3.3 shows the type-dependent visualization of structure classes that occur as nodes of a
structure diagram. Note that if XI is terminal, then type(XI ) must be either (0, 0, 1) or (1, 1, 0)
depending on the parity of XI . A structure digraph can be quite complicated, but we can simplify
it by identifying some vertices.
Definition 3.18. The simplified structure digraph of DNG(G) is built from the structure digraph
of DNG(G) by the identification of type equivalent structure classes followed by the removal of
any resulting loops. The simplified structure diagram is built from the structure diagram using
the same identification process.

10

DANA C. ERNST AND NÁNDOR SIEBEN

Example 3.19. Figure 3.4 illustrates the main steps of finding the simplified structure diagram
of DNG(G) with G = Z6 × Z3 . Subfigure (a) shows the Hasse diagram of the poset of intersection
subgroups. For this group every proper subgroup is an intersection subgroup. Each intersection
subgroup corresponds to a structure class shown in Subfigure (b).
The arrows coming out of a structure class XI are determined by finding the structure classes
containing I ∪ {g} for g ∈ G \ I according to Definition 3.12. Next, we compute type(XI ) and
otype(XI ) for all XI . These values are also shown in Subfigure (b). For example, XΦ(G) is
the structure class at the top of the diagram with type(XΦ(G) ) = (1, 0, 1) and otype(XΦ(G) ) =
{(0, 0, 1), (1, 3, 2)}.
Subfigure (c) depicts Otype(XI ) for all XI , which are computed as the union of type(XI ) and
otype(XI ). Note that each structure class XI with type(XI ) = (0, 0, 1) have the same Otype(XI )
even though they do not have the same otype(XI ).
The final step is the identification of the structure classes according to type and Otype. This
results in the simplified structure diagram of Subfigure (d). We have shaded the triangles in the
simplified structure diagram to signify that we have identified type equivalent structure classes. In
addition, if more than one structure class has been identified, the boundary of the corresponding
triangle is bold.
Proposition 3.20. The type of a structure class XI of DNG(G) is in
T = {t1 := (0, 0, 1), t2 := (1, 0, 1), t3 := (1, 1, 0), t4 := (1, 3, 2)}.
Proof. Recall that the type of a terminal structure class is either t1 or t3 . We show that if
otype(XI ) ⊆ T , then type(XI ) ∈ T , as well. This implies the statement by structural induction.
If XJ is an option of XI , then I is a subgroup of J, and so pty(XJ ) = 1 implies pty(XI ) = 1.
Hence if (1, a, b) ∈ otype(XI ) for some a and b, then type(XI ) must be of the form (1, c, d). The
following table shows the possibilities for otype(XI ) and type(XI ):
1
otype(XI ) type(XI )
otype(XI ) type(XI )
otype(XI ) type(XI )
1
0
0
{t1 }
t1 or t2
{t1 , t3 }
t4
{t1 , t2 , t3 }
t4
t1
t3
{t2 }
t2
{t1 , t4 }
t2
{t1 , t2 , t4 }
t2
0
3
{t3 }
t3
{t2 , t3 }
t4
{t1 , t3 , t4 }
t4
1
2
{t4 }
t3
{t2 , t4 }
t2
{t2 , t3 , t4 }
t4
{t1 , t2 }
t2
{t3 , t4 }
t3
{t1 , t2 , t3 , t4 }
t4
t2
t4
We show the calculation for the case otype(XI ) = {t4 } which is the fourth case in the first column
of the table. Since a structure class with type t4 = (1, 3, 2) is odd, XI must be odd, and so
type(XI ) = (1, c, d) as shown below:
XI

c
d

3
2

We know that a position and any of its option have the opposite parity. So, d = mex{3} = 0, and
hence c = mex{d, 2} = mex{0, 2} = 1. Thus, type(XI ) = (1, 1, 0) = t3 .
Now we show the calculation for the case otype(XI ) = {t1 , t4 } which is the second case in the
second table. Again since t4 ∈ otype(XI ), type(XI ) is of the form (1, c, d). Then d = mex{0, 3} =
1, and hence c = mex{d, 1, 2} = mex{1, 2} = 0. Thus, type(XI ) = (1, 0, 1) = t2 .
The rest of the calculations in the table are done similarly.

The next three results strengthen Corollary 3.3.
Corollary 3.21. The nim-number of DNG(G) is 0, 1, or 3.
Proof. The nim-number of DNG(G) is the second digit of type(XΦ(G) ).



IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

11

Proposition 3.22. If G is nontrivial with odd order, then the simplified structure diagram of
DNG(G) is
1
0

and hence DNG(G) = ∗1.
Proof. It is clear that every structure class is odd. Structural induction on the structure classes
shows that type(XI ) = (1, 1, 0) and Otype(XI ) = {(1, 1, 0)} for all XI ∈ X .

Proposition 3.23. If G has an even Frattini subgroup, then the simplified structure diagram of
DNG(G) is
1
0

and hence DNG(G) = ∗0.
Proof. Every structure class is even since every intersection subgroup contains the Frattini subgroup. Structural induction on the structure classes shows that type(XI ) = (0, 0, 1) and Otype(XI ) =
{(0, 0, 1)} for all XI ∈ X .

4. Achievement games
In this section we study the achievement game GEN(G) on the finite group G. For achievement
games, we must include an additional structure class XG containing terminal positions. A subset
S ⊆ G belongs to XG whenever S generates G while S \{s} does not for some s ∈ S. Note that this
is a slightly abusive notation because, for example, XG does not always contain G. For nontrivial
groups, the positions of GEN(G) are the positions of DNG(G) together with the elements of XG .
If G is the trivial group, then Φ(G) = G is not a game position of GEN(G) = ∗0 and XG = {∅} is
the only structure class. The following is immediate.
Proposition 4.1. The set Y := X ∪ {XG } is a partition of the set of game positions of GEN(G).
We show that the partition Y is compatible with the option relationship between positions. The
next result is analogous to Proposition 3.10.
Proposition 4.2. Assume XI , XJ ∈ Y and P ∈ XI 6= XJ . Then Opt(P ) ∩ XJ 6= ∅ if and only
if Opt(I) ∩ XJ 6= ∅.
Proof. It suffices to consider the case when J = G since the proofs of the other cases are the
same as that of Proposition 3.10. We show that Opt(P ) ∩ XG 6= ∅ for P ∈ XI if and only if
Opt(I) ∩ XG 6= ∅. Note that Opt(P ) ∩ XG 6= ∅ when there exists a g ∈ G \ I such that P ∪ {g}
generates G.
First, assume that Opt(I) ∩ XG = ∅. Then hP ∪ {g}i ⊆ hI ∪ {g}i =
6 G for all g ∈ G \ I and so
Opt(P ) ∩ XG = ∅.
Now, assume that Opt(I)∩XG 6= ∅. Then I ∪{g} ∈ XG for some g ∈ G\I, so that hI ∪{g}i = G.
For a contradiction, assume that Opt(P ) ∩ XG = ∅. Then H := hP ∪ {g}i is a proper subgroup
of G, and so H is contained is some maximal subgroup M . This implies that I is not a subset
of M since g ∈ M and I ∪ {g} generates G. Hence P ⊆ M ∩ I ∈ (−∞, I), which contradicts
P ∈ XI .

Corollary 4.3. Assume XI , XJ ∈ Y and P, Q ∈ XI 6= XJ . Then Opt(P ) ∩ XJ 6= ∅ if and only if
Opt(Q) ∩ XJ 6= ∅.

12

DANA C. ERNST AND NÁNDOR SIEBEN
0
2
4
3

2
0
2
1

2
1

0

Figure 4.1. Simplified structure diagram for GEN(Z6 × Z3 ).
As with DNG(G), it is convenient to append the nim-number data for each structure class
to the structure digraph for GEN(G), which we visualize in a structure diagram. The following
proposition guarantees that we may define the simplified structure diagram of GEN(G) analogously
to that of DNG(G).
Proposition 4.4. If P, Q ∈ XI ∈ Y and pty(P ) = pty(Q), then nim(P ) = nim(Q).
Proof. The proof is analogous to that of Proposition 3.15 using Corollary 4.3.



Given a structure class XI , we define type(XI ), otype(XI ), and Otype(XI ) as before. Note
that by definition the type of the terminal structure class XG is type(XG ) = (pty(G), 0, 0). As
in the avoidance games, we define XI and XJ to be type equivalent if type(XI ) = type(XJ ) and
Otype(XI ) = Otype(XJ ). The simplified structure digraph of GEN(G) is the identification digraph
of the structure digraph with respect to type equivalence. The simplified structure diagram is
visualized as expected, but the structure class XG will be denoted by 0, regardless of the parity
of XG .
Example 4.5. Figure 4.1 shows a simplified structure diagram for GEN(Z6 × Z3 ) = ∗0. Note
that in the simplified structure diagram of DNG(Z6 × Z3 ), shown in Figure 3.4(d), all the classes
with type (0, 0, 1) were identified. This is not the case in the simplified structure digraph of
GEN(Z6 × Z3 ) since some of these classes are connected to terminal positions while others are not.
The use of the dotted arrows is to emphasize that these arrows are not present in DNG(Z6 × Z3 ).
Definition 4.6. We call a structure class XI semi-terminal if the terminal class XG is an option
of XI . We call XI non-terminal if XI is neither terminal nor semi-terminal.
Note that if I is a maximal subgroup, then XI is semi-terminal. However, XI may be semiterminal even if I is not a maximal subgroup. For example, Xh(0,1)i is semi-terminal in GEN(Z6 ×Z3 )
but h(0, 1)i ∼
= Z3 is not a maximal subgroup of Z6 × Z3 , as shown in Figures 3.4(a) and 4.1. Also
note that a semi-terminal structure class cannot have a non-terminal option since if XJ is an
option of XI , then I ≤ J.
Proposition 4.7. If G is a nontrivial group with |G| odd, then the type of a structure class XI
of GEN(G) is in
T = {t0 := (1, 0, 0), t1 := (1, 1, 0), t2 := (1, 2, 0), t3 := (1, 2, 1)}.
Proof. First, it is clear that type(XI ) = t0 if and only if XI is terminal. Now, we use structural
induction to argue that type(XI ) = t3 if XI is semi-terminal and type(XI ) ∈ {t1 , t2 } if XI is
non-terminal.
If XI is semi-terminal, then every option of XI is either terminal or semi-terminal, and so
otype(XI ) = {t0 } or otype(XI ) = {t0 , t3 } by induction. In both cases the type of XI must be t3 .
If XI is non-terminal, then no option of XI has type t0 and so otype(XI ) ⊆ {t1 , t2 , t3 }. In each
case, type(XI ) ∈ {t1 , t2 }. The following table shows the possibilities for otype(XI ) and type(XI ):

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

13

get the set M of maximal subgroups of G from GAP // terminal positions
compute the set I of intersection subgroups
for I, J ∈ I // findSarrows
if I ⊆ J and J \ {K ∈ I | I ⊆ K and J 6⊆ K} =
6 ∅
add arrow (XI , XJ ) to the structure digraph
for I ∈ I with type(XI ) undetermined // compute types
if type(XJ ) is determined for all XJ ∈ Opt(XI )
compute otype(XI )
type(XI ) := (pty(I), mex{c | (a, b, c) ∈ otype(XI )}, mex{b | (a, b, c) ∈ otype(XI )})
for I, J ∈ I // compute the structure classes
if type(XI ) = type(XJ ) and Otype(XI ) = Otype(XJ )
identify XI and XJ
Figure 5.1. Algorithm to compute the simplified structure digraph of DNG(G).
otype(XI ) type(XI )
{t1 }
t1
{t2 }
t1
{t3 }
t2

otype(XI ) type(XI )
{t1 , t2 }
t1
{t1 , t3 }
t2
{t2 , t3 }
t2

otype(XI ) type(XI )
{t1 , t2 , t3 }
t2

1
0

2
0

2
1

t1

t2

t3


Corollary 4.8. If G is nontrivial with |G| odd, then the nim-number of GEN(G) is 1 or 2.
The computer experiments [8] of the next section hint at the following.
Conjecture 4.9. If |G| is even, then the nim-number of GEN(G) is in {0, 1, 2, 3, 4}.
The techniques used to prove Proposition 4.7 do not seem to be sufficient to settle this conjecture.
A proof probably requires a more careful analysis of the forbidden configurations in a structure
diagram.
5. Algorithms
We developed a software package that computes the simplified structure digraph of DNG(G)
and GEN(G). We used GAP [10] to get the maximal subgroups and the rest of the computation is
implemented in C++. The software is efficient enough to allow us to compute the nim-numbers
for the smallest 100, 000 groups which includes all groups up to size 511. The result is available
on our companion web page [8]. The algorithms used are shown in Figures 5.1 and 5.2. Both are
based on the results of this section.
If I and J are intersection subgroups, it is useful to define K := {K ∈ I | I ⊆ K and J 6⊆ K}.
Lemma 5.1. If I, J ∈ I with I ≤ J, then [I, J) = {J ∩ K | K ∈ K}.
T
Proof. Let L ∈ [I, J). Then L =
N with some N ⊆ M such that I ⊆ L ⊂ J, and so
L ∈ K. This implies that [I, J) ⊆ K. Now, suppose K ∈ K. Then K ∩ J ∈ [I, J), and hence
{K ∩ J | K ∈ K} ⊆ [I, J). Therefore, [I, J) = {J ∩ K | K ∈ K}.

The following result is used by the algorithms in Figures 5.1 and 5.2.
Proposition 5.2. Let I, J ∈ I. We have XJ ∈ Opt(XI ) if and only if I ⊆ J and J \

S

K 6= ∅.

Proof. Assume I ≤ J. First, assume that XJ ∈ Opt(XI ). Then there exists g ∈ G \ I such that
I ∪ {g} ∈ XJ . This means there exists g ∈ J \ I such that I ∪ {g} ⊆ J but I ∪ {g} * L for any
L ∈ (−∞, J). Let K ∈ K, so that I ⊆ K and J * K. Then by Lemma 5.1, J ∩ K ∈ [I, J) ⊆

14

DANA C. ERNST AND NÁNDOR SIEBEN

get the set M of maximal subgroups of G from GAP
compute the set I of intersection subgroups
for I, J ∈ I // find arrows
if I ⊆ J and J \ ∪{K ∈ I | I ⊆ K and J 6⊆ K} =
6 ∅
add arrow (XI , XJ ) to the structure digraph
for I ∈ I
if (∃g ∈ G)(∀M ∈ M) I ∪ {g} 6⊆ M // XI is semi-terminal
add arrow (XI , XG ) to the structure digraph
type(XG ) := (pty(G), 0, 0) // the only terminal class
for I ∈ I with type(XI ) undetermined
if type(XJ ) is determined for all XJ ∈ Opt(XI )
compute otype(XI )
type(XI ) := (pty(I), mex{c | (a, b, c) ∈ otype(XI )}, mex{b | (a, b, c) ∈ otype(XI )})
for I, J ∈ I // compute the structure classes
if type(XI ) = type(XJ ) and Otype(XI ) = Otype(XJ )
identify XI and XJ
Figure 5.2. Algorithm to compute the simplified structure digraph of GEN(G).
(−∞, J). Then it mustSbe the case that I ∪ {g} *SK for all K ∈ K, which implies that g ∈
/ K for
all K ∈ K. Hence g ∈
/ K. But since g ∈SJ, J \ K 6= ∅.
Now, S
assume that there exist g ∈ J \ K. Then I ∪ {g} ⊆ J since I ≤ J. Moreover, since
g ∈ J \ K, g ∈
/ K for all K ∈ K. But then g ∈
/ J ∩ K for all K ∈ K. Thus, XJ ∈ Opt(XI ), as
desired.

6. Cyclic groups
In this section we study the avoidance game DNG(G) and the achievement game GEN(G) for a
cyclic group G. First, we recall some general results about maximal subgroups.
According to [6, Theorem 2] and [15, Exercise 7 on page 144], we can decompose the Frattini
subgroup of a direct product.
Proposition 6.1. If G and H are finite groups, then Φ(G × H) = Φ(G) × Φ(H).
The following result can be found in [6, Corollary 2] and [5, Problem 8.1] and is a consequence
of Proposition 6.1.
Proposition 6.2. If n has prime factorization n = pn1 1 · · · pnk k , then the Frattini subgroup of Zn is
generated by p1 · · · pk and so it is isomorphic to the cyclic group of order pn1 1 −1 · · · pknk −1 .
The next result follows from [7, Exercise 6.1.4 ] and [12, Problem 140(v)].
Proposition 6.3. A subgroup of a finite abelian group is maximal if and only if it has prime
index.
Now we are ready to prove our first result about nim-numbers for finite cyclic groups.
Proposition 6.4. If k ≥ 1, then the simplified structure diagram of DNG(Z4k ) is the one shown
in Figure 6.1(a), and hence DNG(Z4k ) = ∗0.
Proof. The result follows from Proposition 3.23 since Φ(Z4k ) is even by Proposition 6.2.



Proposition 6.5. If k ≥ 1, then the simplified structure diagram of DNG(Z4k+2 ) is the one shown
in Figure 6.1(c), and hence DNG(Z4k+2 ) = ∗3.

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

15

S3
2

3
2

p

1
0

1
0

(a) DNG(Z4k )

(b) DNG(Z2k+1 )
DNG(Z2 )

(c) DNG(Z4k+2 )

2
1

2
1

4
3

S1

1
0

1
0

2
1

S2

2
1

0

0

0

(d) GEN(Z4k )

(e) GEN(Z2k+1 )
GEN(Z2 )

(f) GEN(Z4k+2 )

Figure 6.1. Simplified structure diagrams for cyclic groups assuming k ≥ 1.
Proof. Define the following collection of sets that form a partition of X :
S1 := {XI ∈ X | I = h2i};

S2 := {XI ∈ X | XI is even};

S3 := {XI ∈ X | XI is odd but I 6= h2i}.
We use structural induction on the structure classes to show that these sets are nonempty and are
the type equivalence classes of the structure classes, and that

(1, 1, 0), XI ∈ S1
type(XI ) = (0, 0, 1), XI ∈ S2
(1, 3, 2), X ∈ S .
I
3
First, note that h2i has order 2k + 1, and hence index 2. By Proposition 6.3, h2i is a maximal
subgroup, which implies that Xh2i ∈ S1 is a terminal structure class. Since h2i is odd, type(Xh2i ) =
(1, 1, 0). Hence Otype(Xh2i ) = {(1, 1, 0)}.
Next, let q be an odd prime divisor of 4k + 2. Then hqi has index q, and so hqi is a maximal
subgroup by Proposition 6.3. Moreover, hqi has even order. It follows that Xhqi ∈ S2 , and hence
S2 6= ∅. Let XI ∈ S2 . If XI is terminal, then type(XI ) = (0, 0, 1) and otype(XI ) = ∅. If XI is not
terminal, then any option of XI must be even since XI is even. In this case, otype(XI ) = {(0, 0, 1)}
by induction. In both cases, type(XI ) = (0, 0, 1), and so Otype(XI ) = {(0, 0, 1)}.
For the final case, suppose 4k + 2 has prime factorization 2pn1 1 · · · pnr r , where the pi ’s are distinct
odd primes. By Proposition 6.2, Φ(Z4k+2 ) is generated by 2p1 · · · pr and is isomorphic to the
cyclic group of odd order pn1 1 −1 · · · pnr r −1 6= 2k + 1. This implies that Φ(Z4k+2 ) 6= h2i. Hence
Φ(Z4k+2 ) ∈ S3 , and so S3 6= ∅. Let XI ∈ S3 so that I is an odd intersection subgroup different
from h2i. Since the Frattini subgroup is a subgroup of I, I = h2ai for some a 6= 1 that divides
p1 · · · pr . This implies that hI ∪ {2}i = h2i, and so Xh2i ∈ S1 is an option of XI . Now, let p
be a prime divisor of a, which is odd. Then hI ∪ {p}i = hpi has index p, and hence is an even
maximal subgroup by Proposition 6.3. This implies that Xhpi ∈ S2 is an option of XI . Thus,
otype(XI ) is either {(1, 1, 0), (0, 0, 1)} or {(1, 1, 0), (0, 0, 1), (1, 3, 2)} by induction. In both cases,
type(XI ) = (1, 3, 2). Therefore, Otype(XI ) = {(1, 1, 0), (0, 0, 1), (1, 3, 2)}.
It follows that the simplified structure diagram of DNG(Z4k+2 ) is the one shown in Figure 6.1(c),
and so DNG(Z4k+2 ) = ∗3.


16

DANA C. ERNST AND NÁNDOR SIEBEN

∅

∗3

{2}
∗0

{0}
∗2

{2, 4} {0, 2}
∗1

∗1

{3}
∗1

3
2

{0, 3}

1
0

∗0

1
0

{0, 2, 4}
∗0

(a)

(b)

Figure 6.2. A representative game digraph and the simplified structure diagram for DNG(Z6 ).
Example 6.6. Figure 6.2 shows a representative game digraph and the simplified structure diagram for DNG(Z6 ).
An easy calculation in the Z2 case together with Propositions 6.4, 6.5, and 3.22 immediately
yield the following result.
Corollary 6.7. The nim-number of DNG(Z2 ) is 1. If

∗1,
DNG(Zn ) = ∗0,
∗3,

n ≥ 3, then

n ≡2 1
n ≡4 0 .
n ≡4 2

Proposition 6.8. The nim-number of GEN(Zn ) with n ≥ 2 is one larger than the nim-number of
DNG(Zn ).
Proof. The game digraph of GEN(Zn ) is an extension of the game digraph of DNG(Zn ). In this extension every old vertex in the game digraph of DNG(Zn ) gets a new option that is a generating set
since Zn is cyclic. These generating sets are terminal positions with nim-number 0. Figures 2.1(a)
and 2.1(b) show this extension for Z4 . After the extension, the nim-number of every old vertex is
increased by one. Figure 6.1 shows how the structure diagrams change during the extension. 
Corollary 6.9. The nim-number of GEN(Z2 ) is 2. If

∗2,
GEN(Zn ) = ∗1,
∗4,

n ≥ 3, then
n ≡2 1
n ≡4 0 .
n ≡4 2

7. Dihedral groups
In this section we study the avoidance game DNG(G) and the achievement game GEN(G) for a
dihedral group G. The following result is folklore.
Proposition 7.1. The subgroups of the dihedral group Dn = hr, f | rn = f 2 = e, rf = f rn−1 i are
either dihedral or cyclic. The maximal subgroups of Dn are the cyclic group hri and the dihedral
groups of the form hrp , ri f i ∼
= Dn/p with prime divisors p of n.
The following result can be found in [5, Problem 8.1].
Proposition 7.2. If n has prime factorization n = pn1 1 · · · pnk k , then the Frattini subgroup of Dn
is a cyclic group of order pn1 1 −1 · · · pnk k −1 .

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS
3
2
1
0

1
0

(a) DNG(D4k )

17

0
1
1
0

1
0

(b) DNG(D2k+1 )

(c) DNG(D4k+2 )
1
2
1
0

3
0

2
0
2
1

2
1

0

(d) GEN(D4k )

2
1

2
1

2
0

0

0

(e) GEN(D2k+1 )

(f) GEN(D4k+2 )

Figure 7.1. Simplified structure diagrams for the dihedral groups assuming k ≥ 1.
Proposition 7.3. If k ≥ 1, then the simplified structure diagrams of DNG(D4k ) and DNG(D4k+2 )
are the ones shown in Figures 7.1(a) and 7.1(c), respectively, and hence DNG(D2k+2 ) = ∗0.

Proof. The Frattini subgroup of D4k is even by Proposition 7.2. Thus, the simplified structure
diagram of DNG(D4k ) is the one depicted in Figure 7.1(a) by Proposition 3.23.
The terminal structure classes of DNG(D4k+2 ) are even since the maximal subgroups are even by
Proposition 7.1. On the other hand, the Frattini subgroup is odd by Proposition 7.2. Structural
induction on the structure classes shows that type(XI ) = (0, 0, 1) and Otype(XI ) = {(0, 0, 1)} if
XI is even, while type(XI ) = (1, 0, 1) and Otype(XI ) = {(1, 0, 1)} if XI is odd. Every position that
is not terminal has a terminal option since by Proposition 7.1 we can add an appropriate rotation
to the position that creates a terminal position. Therefore, the simplified structure diagram of
DNG(D4k+2 ) is the one depicted in Figure 7.1(c).

Proposition 7.4. If k ≥ 1, then the simplified structure diagram of DNG(D2k+1 ) is the one shown
in Figure 7.1(b), and hence DNG(D2k+1 ) = ∗3.
Proof. This argument is essentially the same as the one for DNG(Z4k+2 ) (see the proof of Proposition 6.5), where we replace 2 with r. The only maximal subgroup with odd order is hri. Every
other maximal subgroup has even order.

Corollary 7.5. For n ≥ 3, we have


∗3,
DNG(Dn ) =
∗0,

n ≡2 1
.
n ≡2 0

The outcome of GEN(D4k ) can be determined using [3, Section 3.3]. We provide information
about the structure diagram of the game.
Proposition 7.6. If k ≥ 1, then the simplified structure diagram of GEN(D4k ) is the one shown
in Figure 7.1(d), and hence GEN(D4k ) = ∗0.
Proof. Define the following collection of sets that form a partition of Y:
S1 := {XI ∈ Y | XI is terminal};

S2 := {XI ∈ Y | XI is semi-terminal};

S3 := {XI ∈ Y | XI is non-terminal}.

18

DANA C. ERNST AND NÁNDOR SIEBEN

We use structural induction on the structure classes to show that these sets are nonempty and are
the type equivalence classes of the structure classes, and that

(0, 0, 0), XI ∈ S1
type(XI ) = (0, 1, 2), XI ∈ S2 .
(0, 0, 2), X ∈ S
I
3

First, observe that the Frattini subgroup has even order by Proposition 7.2. This implies that
every structure class is even, as well.
It is clear that S1 = {XG } =
6 ∅ and type(XG ) = (0, 0, 0).
Consider the even maximal subgroup R = hri of D4k . Then XR ∈ S2 since hR ∪ {f }i = D4k ,
and so S2 6= ∅. If XI ∈ S2 , then XI is semi-terminal, and so otype(XI ) is either {(0, 0, 0)}
or {(0, 0, 0), (0, 1, 2)} by induction. In either case, type(XI ) = (0, 1, 2), and so Otype(XI ) =
{(0, 0, 0), (0, 1, 2)}.
For the final case, observe that S3 6= ∅ since the empty position is non-terminal and belongs
to XΦ(D4k ) . If XI ∈ S3 , then every option of XI must be semi-terminal or non-terminal, and
so otype(XI ) is either {(0, 0, 2)} or {(0, 0, 2), (0, 1, 2)} by induction. In either case, type(XI ) =
(0, 0, 2), and hence Otype(XI ) = {(0, 0, 2), (0, 1, 2)}.
It follows that the simplified structure diagram of GEN(D4k ) is the one shown in Figure 7.1(d),
and so GEN(D4k ) = ∗0.

Proposition 7.7. If k ≥ 1, then the simplified structure diagram of GEN(D2k+1 ) is the one shown
in Figure 7.1(e), and hence GEN(D2k+1 ) = ∗3.
Proof. Let G := D2k+1 . Define the following collection of sets that form a partition of Y:
S1 := {XI ∈ Y | XI is terminal};
S2 := {XI ∈ Y | XI is odd and semi-terminal};

S3 := {XI ∈ Y | XI is even and semi-terminal};
S4 := {XI ∈ Y | XI is non-terminal}.

We use structural induction on the structure classes to show that these sets are nonempty and are
the type equivalence classes of the structure classes, and that

(0, 0, 0), XI ∈ S1



(1, 2, 1), XI ∈ S2
type(XI ) =
.
(0, 1, 2), XI ∈ S3


(1, 3, 0), X ∈ S
I

4

It is clear that S1 = {XG } =
6 ∅ and type(XG ) = (0, 0, 0).
Next, consider the maximal subgroup R = hri of G. The only odd maximal subgroup is R by
Proposition 7.1, and so S2 = {XR }. Any T ∈ Opt(R) generates G since R is a maximal subgroup.
So R has no option in a semi-terminal structure class, and hence otype(XR ) = {(0, 0, 0)}. Thus,
type(XR ) = (1, 2, 1), and so Otype(XR ) = {(0, 0, 0), (1, 2, 1)}.
For the third case, consider the even subgroup F = hf i. Then F is a position of an even
semi-terminal structure class since hF ∪ {r}i = G, and so S3 6= ∅. Suppose XI ∈ S3 . Since XI
is semi-terminal, otype(XI ) is either {(0, 0, 0)} or {(0, 0, 0), (0, 1, 2)} by induction. In either case,
type(XI ) = (0, 1, 2), and so Otype(XI ) = {(0, 0, 0), (0, 1, 2)}.
For the final case, note that Φ(G) is a proper subgroup of hri by Proposition 7.2. If g is
a rotation in G, then Φ(G) ∪ {g} generates a subgroup of hri. If g is a reflection in G, then
Φ(G) ∪ {g} generates a subgroup H of G. It is easy to see that H is isomorphic to a dihedral
group whose order is twice the order of Φ(G). Thus H 6= G which means XΦ(G) ∈ S4 , and so
S4 6= ∅. Let XI ∈ S4 . Since XI is non-terminal, I does not contain r or any reflections. Then

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

19

∅

∗3

{(123)}

{()}

{(23)}

{(), (123)}

{(23), (123)}

{(), (23)}

∗1

{(123), (132)}
∗2

{(23), (123), (132)}
∗0

∗2

{(), (123), (132)}
∗1

∗0

∗0

{(), (23), (123)}
∗0

∗2

∗1

{(12), (23)}
∗0

{(), (12), (23)}
∗0

{(), (23), (123), (132)}
∗0

Figure 7.2. Representative game digraph of GEN(D3 ). We use permutation notation after the identification of D3 with S3 .
XI must be odd by Cauchy’s Theorem because there are no even order rotations in G. Hence
hI ∪{r}i = hri is an option of XI in S2 and hI ∪{f }i is an option of XI in S3 . So otype(XI ) is either
{(1, 2, 1), (0, 1, 2)} or {(1, 2, 1), (0, 1, 2), (1, 3, 0)} by induction. In either case, type(XI ) = (1, 3, 0),
and hence Otype(XI ) = {(1, 2, 1), (0, 1, 2), (1, 3, 0)}.
It follows that the simplified structure diagram of GEN(G) is the one shown in Figure 7.1(e),
and so GEN(G) = ∗3.

Example 7.8. Figure 7.2 shows a representative game digraph for GEN(D3 ) and Figure 7.1(e)
shows the simplified structure diagram for GEN(D3 ).
Proposition 7.9. If k ≥ 1, then the simplified structure diagram of GEN(D4k+2 ) is the one shown
in Figure 7.1(f ), and hence GEN(D4k+2 ) = ∗1.
Proof. Let G := D4k+2 . Define the following collection of sets that form a partition of Y:
S1 := {XI ∈ Y | XI is terminal};

S2 := {XI ∈ Y | XI is semi-terminal};

S3 := {XI ∈ Y | XI is even and non-terminal};

S4 := {XI ∈ Y | XI is odd and non-terminal without any even non-terminal option};
S5 := {XI ∈ Y | XI is odd and non-terminal with an even non-terminal option}.

We use structural induction on the structure classes to show that these sets are nonempty and are
the type equivalence classes of the structure classes and that


(0, 0, 0), XI ∈ S1



(0, 1, 2), XI ∈ S2
type(XI ) = (0, 0, 2), XI ∈ S3 .


(1, 1, 0), XI ∈ S4


(1, 1, 2), X ∈ S
I
5
As usual, we have S1 = {XG } =
6 ∅ and type(XG ) = (0, 0, 0).
Next, consider the even maximal subgroup R := hri. Then XR ∈ S2 since hR ∪ {f }i = G, and
so S2 6= ∅. Suppose XI ∈ S2 . Then I = R or I contains a reflection, and so XI must be even.
Since XI is semi-terminal, otype(XI ) is one of {(0, 0, 0)} and {(0, 0, 0), (0, 1, 2)} by induction. In
either case, type(XI ) = (0, 1, 2), and so Otype(XI ) = {(0, 0, 0), (0, 1, 2)}.

20

DANA C. ERNST AND NÁNDOR SIEBEN

For the third case, consider the even subgroup Q = hr2k+1 i = {e, r2k+1 }. Then Q ∈ S3 since
for all h ∈ G, hQ ∪ {h}i 6= G, and so S3 6= ∅. Let XI ∈ S3 . Then every option of XI is even.
Moreover, it must be the case that hI ∪ {x}i is an option in a structure class belonging to S2
exactly when x is a reflection or x is a rotation such that hI ∪ {x}i is the full rotation subgroup.
Otherwise, hI ∪ {x}i is an option in a structure class belonging to S3 . This shows that otype(XI )
is either {(0, 1, 2)} or {(0, 1, 2), (0, 0, 2)} by induction. In either case, type(XI ) = (0, 0, 2), and
hence Otype(XI ) = {(0, 1, 2), (0, 0, 2)}.
To show that S4 6= ∅, consider the odd subgroup P = hr2 i and let x be any even order element
of G. Then either x is a reflection or equal to rm , where m is odd. In either case, hP ∪ {x}i
is maximal, and hence hP ∪ {x}i must be an element of a semi-terminal structure class in S2 .
Hence P ∈ S4 . Now, let XI ∈ S4 , so that XI is an odd non-terminal structure class without
any even non-terminal options. We see that hI ∪ {r}i contains the maximal subgroup hri, which
has even order. So XI has an option in S2 . Next, we show that XI has no option in S5 . For a
contradiction, suppose XI has an option XJ in S5 . By the definition of S5 , XJ has an option XH
in S3 . Let t be an element of order 2 in H and let I ∪ {t} ∈ XK . Then K is even and K ≤ H ≤ G.
So XK is an option of XI in S3 , which is a contradiction. This shows that otype(XI ) is either
{(0, 1, 2)} or {(0, 1, 2), (1, 1, 0)} by induction. In either case, otype(XI ) = {(1, 1, 0)}, and hence
Otype(XI ) = {(0, 1, 2), (1, 1, 0)}.
For the final case, consider the non-terminal structure class XΦ(G) , which contains the empty
position ∅ and is odd by Proposition 7.2. We see that h∅ ∪ {r2k+1 }i = {e, r2k+1 } is an option
in a structure class belonging to S3 . This shows that XΦ(G) ∈ S5 , and so S5 6= ∅. Suppose
XI ∈ S5 . Since I is of odd order, it must be a subgroup of hr2 i. However, since hr2 i is an
element of a structure class belonging to S4 , I must be a proper subgroup of hr2 i. We see
that hI ∪ {r}i = hri and hI ∪ {r2 }i = hr2 i, which are elements of structure classes belonging
to S2 and S4 , respectively. As a consequence, otype(XI ) is either {(0, 0, 2), (1, 1, 0), (0, 1, 2)} or
{(0, 0, 2), (1, 1, 0), (0, 1, 2), (1, 1, 2)} by induction. In either case, type(XI ) = (1, 1, 2), and hence
Otype(XI ) = {(0, 0, 2), (1, 1, 0), (0, 1, 2), (1, 1, 2)}.
It follows that the simplified structure diagram of GEN(G) is the one shown in Figure 7.1(f),
which implies that GEN(G) = ∗1.

Corollary 7.10. For n ≥ 3, we have

∗3,
GEN(Dn ) = ∗0,
∗1,

n ≡2 1
n ≡4 0 .
n ≡4 2

The simplified structure diagrams for GEN(Dn ) are shown in Figure 7.1.

8. Abelian groups
In this section, we study the avoidance game DNG(G) and the achievement game GEN(G) for a
finite abelian group G. The following result is from [15, Corollary on page 141].
Proposition 8.1. If G and H are finite groups of relatively prime orders, then any subgroup of
G × H is of the form K × L for some subgroups K ≤ G and L ≤ H.
The next result completely characterizes the nim-numbers for DNG(G) for finite abelian groups
G.

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

Proposition 8.2. If G is a finite abelian

∗1,



∗1,
DNG(G) =
∗3,


∗0,

21

group, then
G is nontrivial of odd order
G∼
= Z2
.
G∼
= Z2 × Z2k+1 with k ≥ 1
else

Proof. The case when G is nontrivial of odd order is proved in Proposition 3.22. Corollary 6.7
covers both the G ∼
= Z2 and G ∼
= Z2 × Z2k+1 cases. In every other case, DNG(G) = ∗0 since the
second player has a winning strategy as was shown in [2, Section 3] and in [3, Section 2.1] (see
Proposition 3.1).

The remainder of this section tackles GEN(G) for finite abelian groups G. Our analysis involving
groups with non-zero nim-numbers handles three cases, which are addressed in Propositions 8.11,
8.14, and 8.15.
Recall that every finite abelian group G has an invariant factor decomposition G ∼
= Zα1 ×· · ·×Zαk
where the positive non-unit elementary divisors α1 , . . . , αk are uniquely determined by G and
satisfy αi | αi+1 for i ∈ {1, . . . , k − 1}. Our proof of Proposition 8.11 requires the following notion
and the lemmas that follow.
Definition 8.3. We define the spread spr(G) of the finite abelian group G to be the number of
elementary divisors in the invariant factor decomposition of G.
Note that the trivial group has spread spr(Z1 ) = 0. If G = Zpr11 × · · · × Zprk is an abelian group
k
with primes p1 , . . . , pk , then spr(G) = max{ni | i ∈ {1, . . . , k}} where ni := |{j | pi = pj }|. In this
case, G is isomorphic to the direct product of spr(G)-many cyclic groups, but it is not isomorphic
to the direct product of fewer cyclic groups. It follows that the spread of G is the minimum size
of a generating set of G.
Example 8.4. Let G = Z3 × Z9 × Z5 × Z49 × Z7 . Then spr(G) = 2. If g = (1, 1, 0, 1, 0),
then G/hgi ∼
= Z3 × Z5 × Z7 , and so spr(G/hgi) = 1 = spr(G) − 1. If h = (0, 3, 1, 1, 0), then
∼
G/hhi = Z3 ×Z3 ×Z7 , and so spr(G/hhi) = 2 = spr(G). If k = (1, 3, 1, 0, 1), then G/hki ∼
= Z9 ×Z49 ,
and so spr(G/hki) = 1 = spr(G) − 1.
The following is an easy consequence of the definitions.

Lemma 8.5. Let G = Zpr11 × · · · × Zprk be an abelian group with primes p1 , . . . , pk . If g =
k
(g1 , . . . , gk ) with

1, i = min{j | pi = pj }
gi :=
,
0, else
then spr(G/hgi) = spr(G) − 1.

Definition 8.6. If A is an m × n integer matrix, then we define Grp(A) to be the abelian group
with generators g1 , . . . , gn satisfying the relations
   
g1
0
.



.
A . = ...  .
gn
0
It is well-known that Grp(A) ∼
= Grp(Snf(A)) where Snf(A) is the Smith Normal Form of A.
The diagonal entries α1 , . . . , αk of Snf(A) can be calculated as α1 = d1 (A) and αi = di (A)/di−1 (A)
for i ∈ {2, . . . , k}, where di (A) is the greatest common divisor of all i × i minors of A [11, Theorem
3.9]. Elementary integer row and column operations can be used on A to get Snf(A). The non-unit
diagonal elements of Snf(A) are the invariant factors of Grp(A) and so spr(Grp(A)) is the number
of non-unit elements of {α1 , . . . , αk }.

22

DANA C. ERNST AND NÁNDOR SIEBEN

The truncated Smith Normal Form tSnf(A) of A is created from Snf(A) by removing every zero
row and every column containing a single nonzero entry equal to 1. We clearly have Grp(A) ∼
=
Grp(tSnf(A)). It is also clear that spr(Grp(A)) is equal to the size of tSnf(A).
3 0
∼
Example
h
i8.7. Let G = Z3 ×h Z15i = Grp ([ 0 15 ]). Then spr(G) = 2. Now, let g = (1, 2) ∈ G and
3 0
1 0
A = 0 15 . Then Snf(A) = 0 3 and tSnf(A) = [ 3 ], and so G/hgi ∼
= Grp(A) ∼
= Grp(Snf(A)) ∼
=
1 2

0 0

Z3 . Hence spr(G/hgi) = 1 = spr(G) − 1.

Definition 8.8. Let Zr1 × · · · × Zrk be the invariant factor decomposition of G and ei :=
(0, . . . , 0, 1, 0, . . . , 0) for i ∈ {1, . . . , k}, where 1 occurs in the ith component. For g ∈ G we
let ĝ := ĝ1 · · · ĝk ∈ Z1×k such that gˆi is the smallest nonnegative integer satisfying
X
g=
gˆi ei .
Lemma 8.9. If g is an element of the abelian group G, then spr(G/hgi) ≥ spr(G) − 1.

Proof. Let Zr1 ×· · ·×Zrk be the invariant factor decomposition of G. Note that 1 6= r1 | r2 | · · · | rk .
Then G ∼
= Grp(A) with A = diag(r1 , . . . , rk ) and G/hgi ∼
= Grp(B) ∼
= Grp(Snf(B)) where


r1
0


.


..
A
.
=
B=
 0
ĝ
rk 
ĝ1 · · · ĝk

Let α1 , . . . , αk be the diagonal elements of Snf(B). If spr(G/hgi) ≤ spr(G) − 2 = k − 2, then
d1 (B) = α1 = α2 = 1. This is impossible since it is easy to see that every 2 × 2 minor of B is
divisible by r1 and so α2 = d2 (B)/d1 (B) = d2 (B) is divisible by r1 .

Proposition 8.10. If H is a subgroup and g is an element of the finite abelian group G, then
spr(G/hH ∪ {g}i) ≥ spr(G/H) − 1.

Proof. Let Zr1 × · · · × Zrk be the invariant factor decomposition of G and H = {h1 , . . . , hm }. Then
G∼
= Grp(A) with A = diag(r1 , . . . , rk ) and G/H ∼
= Grp(B) ∼
= Grp(tSnf(B)) with


c
h1


 . 
A
. 
B=
and Ĥ = 
 . .
Ĥ
hc
m
h
i
Note that hbi = hbi 1 · · · hbi m . Applying elementary integer row and column operations gives






I
0
B
tSnf(B)
∼
G/hH ∪ {g}i ∼
= Grp
= Grp  0 tSnf(B)  ∼
= Grp
ĝ
g̃
0
g̃
for some g̃. So, G/hH ∪ {g}i is isomorphic to a quotient of G/H by a cyclic subgroup. The result
now follows as in the proof of Lemma 8.9.

Proposition 8.11. If G = Zpr11 × · · · × Zprk is an abelian group with odd primes p1 , . . . , pk , then
k
the simplified structure diagram of GEN(G) is one of the diagrams shown in Figure 8.1, and hence

∗0, spr(G) = 0
GEN(G) = ∗2, 1 ≤ spr(G) ≤ 2 .

∗1, 3 ≤ spr(G)

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

2
0

2
1

2
0

2
1

0

0

(a) spr(G) = 1

1
0

1
0

1
0

2
1

2
0

2
1

0

(b) spr(G) = 2

23

0

(d) spr(G) ≥ 4

(c) spr(G) = 3

Figure 8.1. Simplified structure diagrams for GEN(G) with G = Zpr11 × · · · × Zprk
k
and odd primes p1 , . . . , pk .

0
1

1
0
2
1

0

(a) n = 1

2
1

2
1

0

(b) n = 2

2
0

0

(c) n = 3

1
0
2
1

0
1

0
1

2
0

1
0

0

(d) n = 4

2
1

1
0
2
0

0

(e) n ≥ 5

Figure 8.2. Simplified structure diagrams for GEN(Zn2 ).
Proof. The Frattini subgroup is Φ(G) ∼
= Zpr1 −1 × · · · × Zprk −1 by Propositions 6.1 and 6.2, and
1
k
so G/Φ(G) ∼
= Zp1 × · · · × Zpk . One can show that this implies that every proper subgroup of G
containing Φ(G) is an intersection subgroup. We use structural induction on the structure classes
to show that the simplified structure diagram is only dependent on spr(G) as shown in Figure 8.1,
and

t := (1, 0, 0), spr(G/I) = 0


0
t1 := (1, 2, 1), spr(G/I) = 1
.
type(XI ) =
t2 := (1, 2, 0), spr(G/I) = 2


t := (1, 1, 0), spr(G) ≥ spr(G/I) ≥ 3
3

The statement is clearly true when spr(G/I) = 0, that is, I = G. Assume spr(G/I) = i ≥ 1. Then
XI has an option XK such that spr(G/K) = i − 1 by Lemma 8.5 and the proof of Proposition 8.10.
Now, suppose g ∈ G \ I. By Proposition 8.10, spr(G/hI ∪ {g}i) ≥ spr(G/I) − 1, which implies
that if XJ is an option of XI , then spr(G/J) ∈ {spr(G/I), spr(G/I) − 1}.
First, assume j := spr(G/I) ∈ {1, 2, 3}. Then otype(XI ) = {tj−1 } or otype(XI ) = {tj−1 , tj } by
induction. In either case, type(XI ) = tj , and so Otype(XI ) = {tj−1 , tj }. Now, assume spr(G/I) ≥
4. Then otype(XI ) = {t3 } by induction. Hence type(XI ) = t3 , and so Otype(XI ) = {t3 }.

Example 8.12. It is easy to check that the simplified structure diagram of GEN(Zn2 ), shown
in Figure 8.2, follows a pattern somewhat similar to that of GEN(Zpr11 × · · · × Zprk ), shown in
k
Figure 8.1. Note that the only odd order subgroup is the Frattini subgroup, which is the trivial
subgroup.
The following result of [3] is an easy consequence of the Third Isomorphism Theorem.
Lemma 8.13. If I is a proper intersection subgroup of the abelian group G, then XI is semiterminal in GEN(G) if and only if G/I is cyclic.

Proposition 8.14. If G = Z2 × Z2 × Zm × Zk such that m and k are odd and relatively prime,
then the simplified structure diagram of GEN(G) is the one shown in Figure 8.3(a), and hence
GEN(G) = ∗1.

24

DANA C. ERNST AND NÁNDOR SIEBEN
S5

1
0

1
2
g3

g4
S4

2
1

g2

1
0
h4

2
1

2
0
h3

S3

S2

0

0

(a) gcd(m, k) = 1

(b) gcd(m, k) 6= 1

Figure 8.3. Simplified structure diagram for GEN(Z2 × Z2 × Zm × Zk ) with odd
m and k.
Proof. Define the following collection of sets that form a partition of Y:
S1 := {XI ∈ Y | XI is terminal};

S2 := {XI ∈ Y | XI is semi-terminal};

S3 := {XI ∈ Y | XI is non-terminal}.

We use structural induction on the structure classes to show that these sets are nonempty and are
the type equivalence classes of the structure classes, and that

(0, 0, 0), XI ∈ S1
type(XI ) = (0, 1, 2), XI ∈ S2 .

(1, 1, 0), XI ∈ S3

First, note that since the orders of Z2 × Z2 and Zm × Zk are relatively prime, every subgroup
is of the form I = H × K for some H ≤ Z2 × Z2 and K ≤ Zm × Zk by Proposition 8.1.
We show that if I is an intersection subgroup, then XI is even if and only if XI is semi-terminal.
Suppose that XI is even. Then H is nontrivial, which implies that (Z2 × Z2 )/H is isomorphic to
h0i or Z2 . Since m and k are relatively prime, Zm × Zk is cyclic, and hence (Zm × Zk )/K is cyclic,
as well. This implies that
G/I = G/(H × K) ∼
= (Z2 × Z2 )/H × (Zm × Zk )/K

is cyclic since the orders of (Z2 × Z2 )/H and (Zm × Zk )/K are relatively prime and each group
is cyclic. Hence XI is semi-terminal by Lemma 8.13. On the other hand, if XI is semi-terminal,
reversing the above argument presents no difficulties, so XI is even.
It is clear that S1 = {XG } =
6 ∅ and type(XG ) = (0, 0, 0).
The maximal subgroup R = h0i × Z2 × Zm × Zk is even. Hence XR ∈ S2 , and so S2 6= ∅. Let
XI ∈ S2 . Then by the above, XI is even. Hence otype(XI ) is either {(0, 0, 0)} or {(0, 0, 0), (0, 1, 2)}
by induction. In either case, type(XI ) = (0, 1, 2), and so Otype(XI ) = {(0, 0, 0), (0, 1, 2)}.
For the final case, observe that XΦ(G) ∈ S3 since Φ(G) is odd by Propositions 6.1 and 6.2, and
so S3 6= ∅. Let XI ∈ S3 . Then XI must be odd. Moreover, I ∪ {(1, 0, 0, 0)} is an option of I that
lies in a semi-terminal structure class. Hence otype(XI ) is either {(0, 1, 2)} or {(0, 1, 2), (1, 1, 0)}
by induction. In either case, type(XI ) = (1, 1, 0), and hence Otype(XI ) = {(0, 1, 2), (1, 1, 0)}.
It follows that the simplified structure diagram of GEN(G) is the one shown in Figure 8.3(a),
and so GEN(G) = ∗1.

Proposition 8.15. If G = Z2 × Z2 × Zm × Zk such that m and k are odd and not relatively prime,
then the simplified structure diagram of GEN(G) is the one shown in Figure 8.3(b), and hence
GEN(G) = ∗1.

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS

25

Proof. Define the following collection of sets that form a partition of Y:
S1 := {XI ∈ Y | XI is terminal};
S2 := {XI ∈ Y | XI is semi-terminal};

S3 := {XI ∈ Y | XI is even and non-terminal};

S4 := {XI ∈ Y | XI is odd and non-terminal without any even non-terminal option};
S5 := {XI ∈ Y | XI is odd and non-terminal with an even non-terminal option}.

We use structural induction on the structure classes to show that these sets are nonempty and are
the type equivalence classes of the structure classes and that


(0, 0, 0), XI ∈ S1



(0, 1, 2), XI ∈ S2
type(XI ) = (0, 0, 2), XI ∈ S3 .


(1, 1, 0), XI ∈ S4


(1, 1, 2), X ∈ S
I
5
It is clear that S1 = {XG } =
6 ∅ and type(XG ) = (0, 0, 0).
Next, consider the even maximal subgroup R = h0i × Z2 × Zm × Zk . Then XR ∈ S2 since
hR ∪ {(1, 0, 0, 0)}i = G, and so S2 6= ∅. Let XI ∈ S2 . Note that the orders of Z2 × Z2 and Zm × Zk
are relatively prime, so I = H × K for some H ≤ Z2 × Z2 and K ≤ Zm × Zk by Proposition 8.1.
Since XI is semi-terminal, the quotient
G/I = G/(H × K) ∼
= (Z2 × Z2 )/H × (Zm × Zk )/K
is cyclic by Lemma 8.13. This happens only if

H ∈ {h0i × Z2 , Z2 × h0i, h(1, 1)i, Z2 × Z2 },

which shows that XI must be even. Hence otype(XI ) is either {(0, 0, 0)} or {(0, 0, 0), (0, 1, 2)} by
induction since XI is semi-terminal. In either case, type(XI ) = (0, 1, 2), and hence Otype(XI ) =
{(0, 0, 0), (0, 1, 2)}.
For the third case, consider the even subgroups R1 = Z2 ×h0i×h0i×h0i, R2 = h0i×Z2 ×h0i×h0i,
and R3 = h(1, 1)i × h0i × h0i. Let XIi be the structure class containing Ri . Since m and k are not
relatively prime, we can choose m0 and k 0 such that m/m0 = k/k 0 is a prime. Then Ii is contained
in the sets
M := Z2 × Z2 × hm/m0 i × Zk ∼
= Z2 × Z2 × Zm0 × Zk
0 ∼
N := Z2 × Z2 × Zm × hk/k i = Z2 × Z2 × Zm × Zk0 .
By Proposition 6.3, M and N are maximal subgroups. Since M ∩ N ∼
= Z2 × Z2 × Zm0 × Zk0 ,
2
∼
G/M ∩ N = Zm/m0 is not cyclic. Hence each G/Ii is not cyclic. So each XIi is even and nonterminal by Lemma 8.13. Thus each Ri is an element of an even non-terminal structure class,
which shows that S3 6= ∅. Let XI ∈ S3 . We show that XI has an option in S2 . Since I is even,
at least one of R1 , R2 , or R3 is a subgroup of I. Let h3 = (0, 0, 1, 0). Since gcd(2, k) = 1, each
G/hRi ∪ {h3 }i ∼
= Z2 × Zm is cyclic. This implies that G/hI ∪ {h3 }i is cyclic, and hence I ∪ {h3 }
is an element of an even semi-terminal structure class. It is clear that every option of XI is in
S2 ∪ S3 . Therefore, otype(XI ) is either {(0, 1, 2)} or {(0, 1, 2), (0, 0, 2)} by induction. In either
case, type(XI ) = (0, 0, 2), and so Otype(XI ) = {(0, 1, 2), (0, 0, 2)}.
For the fourth case, consider the odd subgroup Q := h0i × h0i × Zm × h0i. Then Q is contained
in an odd structure class XJ since Q is a subset of the maximal subgroups h0i × Z2 × Zm × Zk
and Z2 × h0i × Zm × Zk . We show that XJ ∈ S4 . For a contradiction, assume that Q ∪ {h} is in a
structure class inside S3 for some h. Then hQ ∪ {h}i ∼
= Z2 × Zm × U , where U ≤ Zk . This implies
that G/hQ ∪ {h}i ∼
= Z2 × (Zk /U ), which is cyclic since k is odd. Then Q ∪ {h} is in a structure

26

DANA C. ERNST AND NÁNDOR SIEBEN

n
2 3 ≥4
DNG(Sn ) ∗1 ∗3 ∗0

n
3 4 5 6 7 8
DNG(An ) ∗3 ∗3 ∗0 ∗0 ∗0 ∗0

Table 9.1. Nimbers for DNG(Sn ) and DNG(An ).
class in S2 by Lemma 8.13. This is a contradiction, and so S4 6= ∅. Now consider XI ∈ S4 . If h4 is
any element of G with even order, then I ∪ {h4 } is contained in an even semi-terminal structure
class by the definition of S4 . So XI has an option in S2 . Next, we show that XI has no option in
S5 . For a contradiction, suppose XI has an option XJ in S5 . By the definition of S5 , XJ has an
option XH in S3 . Let t be an element of order 2 in H and let I ∪ {t} ∈ XK . Then K is even and
K ≤ H ≤ G. So XK is an option of XI in S3 , which is a contradiction. Hence any option of XI
is in S2 or S4 . Thus, otype(XI ) is either {(0, 1, 2)} or {(0, 1, 2), (1, 1, 0)} by induction. In either
case, type(XI ) = (1, 1, 0) and so Otype(XI ) = {(0, 1, 2), (1, 1, 0)}.
To show that S5 6= ∅, consider the empty position ∅, which is an element of the odd structure
class XΦ(G) . Since G is not cyclic, XΦ(G) must be a non-terminal structure class. Let g3 :=
(1, 0, 0, 0). The empty position has the option {g3 } that belongs to a structure class in S3 by
Lemma 8.13, since
G/h{g3 }i = G/(Z2 × h0i × h0i × h0i) ∼
= Z2 × Zm × Zk

is not cyclic as gcd(m, k) 6= 1. Hence XΦ(G) ∈ S5 . Next, let XI ∈ S5 . Let g2 = (1, 0, 1, 0) and
g4 = (0, 0, 1, 0). Then I ∪ {g2 } belongs to an even semi-terminal structure class by Lemma 8.13
since G/hI ∪ {g2 }i is cyclic. This implies that XI has an option in S2 . Lastly, we will show
that I ∪ {g4 } is an option of I in a structure class in S4 . We see that Q is a subgroup of
hI ∪ {g4 }i. We know from the fourth case that hg4 i = Q ∈ XJ ∈ S4 . Hence the odd structure class
containing I ∪{g4 } belongs to S4 . As a consequence, otype(XI ) is either {(0, 0, 2), (1, 1, 0), (0, 1, 2)}
or {(0, 0, 2), (1, 1, 0), (0, 1, 2), (1, 1, 2)} by induction. In either case, type(XI ) = (1, 1, 2), and hence
Otype(XI ) = {(0, 0, 2), (1, 1, 0), (0, 1, 2), (1, 1, 2)}.
It follows that the simplified structure diagram of GEN(G) is the one shown in Figure 8.3(b),
which implies that GEN(G) = ∗1.

It is interesting to notice that the simplified structure diagram from the previous theorem is the
same as that of GEN(D4k+2 ) shown in Figure 7.1(f).
Corollary 8.16. If G is a finite abelian group, then

∗2, |G| is odd and 1 ≤ spr(G) ≤ 2




∗1, |G| is odd and spr(G) ≥ 3



∗2, G ∼
= Z2
∼
GEN(G) = ∗1, G = Z4k with k ≥ 1
.

∼

∗4,
G
Z
with
k
≥
1
=

4k+2


∼

∗1,
G
Z
=

2 × Z2 × Zm × Zk for m, k odd

∗0, else

Proof. By [3, Section 3.2], the first player wins GEN(G) exactly when G is cyclic, odd, or isomorphic
to Z2 × Z2 × Zm × Zk with odd m and k. We already proved the result in these cases. In every
other case the second player wins, so in these cases GEN(G) = ∗0.

9. Symmetric and alternating groups

According to [3, Section 2.3], the second player wins DNG(Sn ) for n ≥ 4. Hence DNG(Sn ) = ∗0
for n ≥ 4. We already studied the remaining cases. In particular, we know that DNG(S2 ) =
DNG(Z2 ) = ∗1 and DNG(S3 ) = DNG(D3 ) = ∗3. These results are summarized in Table 9.1.

IMPARTIAL ACHIEVEMENT AND AVOIDANCE GAMES FOR GENERATING FINITE GROUPS
0
2
3
0
2
1

2
1

1
2

2
1

0

(a) GEN(A4 )

1
0
1
2

2
0

2
1

0

(b) GEN(S4 )

27

0

(c) GEN(Sn ), GEN(An ), n ≥ 5

n
2 3 4 ≥5
GEN(Sn ) ∗2 ∗3 ∗0 ∗1?
GEN(An )
∗2 ∗3 ∗1?
Figure 9.1. Known and conjectured values and simplified structure diagrams for
GEN(Sn ) and GEN(An ).
The DNG(An ) games remain a bit of a mystery. There is an incomplete analysis of DNG(An )
in [3, Section 2.4] that involves some fairly deep group-theoretic results. By Proposition 3.22,
we know DNG(A3 ) = DNG(Z3 ) = ∗1. Some additional computer calculated values are listed in
Table 9.1.
By [3, Section 3.4], the first player wins GEN(Sn ) for n ≥ 5 and GEN(An ) for all n ≥ 4. On the
other hand, GEN(S2 ) = GEN(Z2 ) = ∗2, GEN(S3 ) = GEN(D3 ) = ∗3, GEN(A3 ) = GEN(Z3 ) = ∗2,
and computer calculations show that GEN(S4 ) = ∗0.
Conjecture 9.1. For n ≥ 5, we have GEN(Sn ) = ∗1 = GEN(An ).
We have verified the conjecture for n ∈ {5, 6, 7, 8} using our software. The conjectured simplified
structure diagrams are shown in Figure 9.1.
10. Further questions
We conclude with a few open problems that may not be out of reach.
(1) Is it possible to have a directed cycle in the simplified structure digraph? This never
happens for the groups we have considered, but are there groups for which this is possible?
(2) Does Conjecture 9.1 about GEN(Sn ) and GEN(An ) hold? Structural induction on the
structure classes could work to show that the simplified structure diagram of Figure 9.1(c)
is correct.
(3) What are the remaining nim-numbers for DNG(An )? The partial results of [3, Theorem
2] are quite complicated. Settling this question likely requires some sophisticated group
theory arguments.
(4) What are the nim-numbers of other families of groups? In particular, what are the nimnumbers of generalized dihedral groups of the form A o Z2 where A is a finite abelian
group?
(5) Are there any general results regarding quotient groups and direct products of groups? A
positive answer would be very helpful in the study of more complicated groups.
(6) Does Conjecture 4.9 about the spectrum of GEN(G) hold? Is the set {nim(GEN(G)) |
G is a finite group} at least bounded?
(7) Can the structure diagram approach be generalized to study DNG and GEN on other
algebraic structures with generators (e.g., semigroups, inverse semigroups) and compute
their corresponding nim-numbers?

28

DANA C. ERNST AND NÁNDOR SIEBEN

(8) The Sprague-Grundy theory is generalized to infinite loopy games in [9, 14]. A recent
description of the theory can be found in [13, IV.4]. Can our techniques be generalized to
find the loopy nim-numbers of some families of infinite groups?
References
1. Michael Albert, Richard Nowakowski, and David Wolfe, Lessons in play: an introduction to combinatorial game
theory, AMC 10 (2007), 12.
2. M. Anderson and F. Harary, Achievement and avoidance games for generating abelian groups, Internat. J.
Game Theory 16 (1987), no. 4, 321–325.
3. F. W. Barnes, Some games of F. Harary, based on finite groups, Ars Combin. 25 (1988), no. A, 21–30, Eleventh
British Combinatorial Conference (London, 1987).
4. Martin Brandenburg, Algebraic games playing with groups and rings, Inter. J. of Game Theory (2017), 1–34.
5. John D. Dixon, Problems in group theory, Blaisdell Publishing Co. Ginn and Co., Waltham, Mass.-Toronto,
Ont.-London, 1967.
6. Vlastimil Dlab, The Frattini subgroups of abelian groups, Czechoslovak Mathematical Journal 10 (1960), no. 1.
7. David S. Dummit and Richard M. Foote, Abstract algebra, third ed., John Wiley & Sons, Inc., Hoboken, NJ,
2004.
8. Dana C. Ernst and Nándor Sieben, Companion web site, 2013, http://jan.ucc.nau.edu/ns46/GroupGenGame.
9. A. S. Fraenkel and Y. Perl, Constructions in combinatorial games with cycles, Infinite and finite sets (Colloq.,
Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, North-Holland, Amsterdam, 1975,
pp. 667–699. Colloq. Math. Soc. Janós Bolyai, Vol. 10.
10. The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.6.4, 2013.
11. Nathan Jacobson, Basic algebra. I, second ed., W. H. Freeman and Company, New York, 1985.
12. J.S. Rose, A course on group theory, Dover Publications, Inc., New York, 1994.
13. Aaron N. Siegel, Combinatorial game theory, Graduate Studies in Mathematics, vol. 146, American Mathematical Society, Providence, RI, 2013.
14. Cedric A. B. Smith, Graphs and composite games, J. Combinatorial Theory 1 (1966), 51–81.
15. Michio Suzuki, Group theory. I, Grundlehren der Mathematischen Wissenschaften, vol. 247, Springer-Verlag,
Berlin, 1982.
Current address: Northern Arizona University, Department of Mathematics and Statistics, Flagstaff, AZ 860115717, USA
E-mail address: dana.ernst@nau.edu
E-mail address: nandor.sieben@nau.edu

