IMPARTIAL AVOIDANCE AND ACHIEVEMENT GAMES FOR
GENERATING SYMMETRIC AND ALTERNATING GROUPS

arXiv:1508.03419v2 [math.CO] 14 Jul 2016

BRET J. BENESH, DANA C. ERNST, AND NÁNDOR SIEBEN
Abstract. Anderson and Harary introduced two impartial games on finite groups. 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. We determine the nim-numbers, and therefore the outcomes, of these
games for symmetric and alternating groups.

1. Introduction
Anderson and Harary [3] introduced two impartial games Generate and Do Not Generate
in which two players alternately take turns selecting previously-unselected elements of a finite
group G. The first player who builds a generating set for the group from the jointly-selected
elements wins the achievement game GEN(G). The first player who cannot select an element
without building a generating set loses the avoidance game DNG(G). The outcomes of both
games were studied for some of the more familiar finite groups, including abelian, dihedral,
symmetric, and alternating groups in [3, 4], although the analysis was incomplete for alternating
groups.
Brandenburg studies a similar game in [6]. This variation of the game is played on a finitely
generated abelian group G. Players alternate replacing G by the quotient G/hgi for a choice of
a nontrivial element g. The player with the last possible move wins.
A fundamental problem in the theory of impartial combinatorial games is finding the nimnumber of a game. The nim-number determines the outcome of the game and also allows for
the easy calculation of the nim-numbers of game sums. The last two authors [11] developed
tools for studying the nim-numbers of both games, which they applied in the context of certain
finite groups including cyclic, abelian, and dihedral. In [5], we developed a complete set of
criteria for determining the nim-numbers of avoidance games and calculated the corresponding
nim-numbers for several families of groups, including symmetric groups.
The previous work in [5, 11] left open the determination of the nim-numbers of DNG(An ),
GEN(Sn ), and GEN(An ), except for a handful of cases. In this paper, we provide a complete
classification of the nim-numbers of the games involving the symmetric and alternating groups.
Since nim-numbers determine the outcome, our classification completes the analysis from [4].
In particular, under optimal play, the first player will win the achievement game and lose the
avoidance game for most symmetric and alternating groups. Moreover, building on the work
of [5], we lay the foundation for how one might ascertain the nim-numbers for finite simple
groups.
Date: January 6, 2018.
2000 Mathematics Subject Classification. 91A46, 20B30, 20D06, 20D30.
Key words and phrases. impartial game, maximal subgroup, symmetric group, alternating group.
This work was conducted during the third author’s visit to DIMACS partially enabled through support from
the National Science Foundation under grant number #CCF-1445755.
1

2

BRET J. BENESH, DANA C. ERNST, AND NÁNDOR SIEBEN

The paper is organized as follows. In Section 2, we recall the basic terminology of impartial
games, establish our notation, and review several necessary results from [11]. The following
section describes how to compute GEN(G) for G in a family called Γ1 , which includes the
nonabelian alternating and symmetric groups, as well as all other finite nonabelian simple
groups. In Section 4, we review the known results for DNG(Sn ) and compute the nim-numbers
for GEN(Sn ), and then we find the nim-numbers for DNG(An ) and GEN(An ) in Section 5. We
close with some open questions.
The authors thank the referee for making suggestions that improved the quality of this paper.
2. Preliminaries
2.1. Impartial Games. In this section, we briefly recall the basic terminology of impartial
games and establish our notation. For a comprehensive treatment of impartial games, see [2, 19].
An impartial game is a finite set X of positions together with a starting position and a
collection {Opt(P ) ⊆ X | P ∈ X}, where Opt(P ) is the set of possible options for a position
P . Two players take turns replacing the current position P with one of the available options
in Opt(P ). A position P with Opt(P ) = ∅ is called terminal. The player who moves into a
terminal position wins. All games must come to an end in finitely many turns.
The minimum excludant mex(A) of a set A of ordinals is the smallest ordinal not contained
in the set. The nim-number of a position P is the minimum excludant
nim(P ) := mex{nim(Q) | Q ∈ Opt(P )}
of the set of nim-numbers of the options of P . Since the minimum excludant of the empty set
is 0, 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 since
the second player has a winning strategy if and only if the nim-number for a game is 0. The
winning strategy is to always pick an option that has nim-number 0. This puts the opponent
into a losing position at every turn.
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)}.
We write P = R if the second player of the game P + R has a winning strategy.
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 Sprague–Grundy Theorem [2, 19] states that P = ∗ nim(P )
for every impartial game P .
2.2. Achievement and Avoidance Games for Generating Groups. We now provide a
more precise description of the achievement and avoidance games for generating a finite group
G. For additional details, see [3, 4, 11]. For both games, the starting position is the empty set.
The players take turns choosing previously-unselected elements to create jointly-selected sets
of elements, which are the positions of the game.
In the avoidance game DNG(G), the first player chooses x1 ∈ G such that hx1 i =
6 G and at
the kth turn, the designated player selects xk ∈ G \ {x1 , . . . , xk−1 } such that hx1 , . . . , xk i =
6 G
to create the position {x1 , . . . , xk }. Notice that the positions of DNG(G) are exactly the nongenerating subsets of G. A position Q is an option of P if Q = P ∪ {g} for some g ∈ G \ P ,
where hQi =
6 G. The player who cannot select an element without building a generating set is
the loser. We note that there is no avoidance game for the trivial group since the empty set
generates the whole group.

IMPARTIAL GAMES FOR GENERATING SYMMETRIC AND ALTERNATING GROUPS

3

In the achievement game GEN(G), the first player chooses any x1 ∈ G and at the kth turn, the
designated player selects xk ∈ G \ {x1 , . . . , xk−1 } to create the position {x1 , . . . , xk }. A player
wins on the nth turn if hx1 , . . . , xn i = G. In this case, the positions of GEN(G) are subsets of
terminal positions, which are certain generating sets of G. Note that the second player has a
winning strategy if G is trivial since h∅i = G, so the first player has no legal opening move. In
particular, GEN(S1 ) = GEN(A1 ) = GEN(A2 ) = ∗0.
Maximal subgroups play an important role because a subset S of a finite group is a generating
set if and only if S is not contained in any maximal subgroup. Let M be the set of maximal
subgroups of G. Following [11], the set of intersection subgroups is defined to be the set
I := {∩N | ∅ =
6 N ⊆ M}
containing all possible intersections of maximal subgroups. Note that the elements of I are in
fact subgroups of G. The smallest intersection subgroup is the Frattini subgroup Φ(G) of G,
and we say that an intersection subgroup I is non-Frattini if I 6= Φ(G). Not every subgroup of
G need be an intersection subgroup. For instance, no proper subgroup of a nontrivial Frattini
subgroup is an intersection subgroup. Even a subgroup that contains the Frattini subgroup
need not be intersection subgroup, as shown in [5, Example 1].
The set I of intersection subgroups is partially ordered by inclusion. For each I ∈ I, we let
XI := P(I) \ ∪{P(J) | J ∈ I, J < I}
be the collection of those subsets of I that are not contained in any other intersection subgroup
smaller than I. We define X := {XI | I ∈ I} and call an element of X a structure class. The
starting position ∅ is in XΦ(G) for both games.
The set X of structure classes is a partition of the set of game positions of DNG(G). The partition X is compatible with the option relationship between game positions [11, Corollary 3.11]:
if XI , XJ ∈ X and P, Q ∈ XI 6= XJ , then Opt(P ) ∩ XJ 6= ∅ if and only if Opt(Q) ∩ XJ 6= ∅.
We say that XJ is an option of XI and write XJ ∈ Opt(XI ) if Opt(I) ∩ XJ 6= ∅.
For the achievement game GEN(G), 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 we are abusing notation since XG may not contain G. The
positions of GEN(G) are the positions of DNG(G) together with the elements of XG . The set
Y := X ∪ {XG } is a partition of the set of game positions of GEN(G). As in the avoidance case,
the partition Y is compatible with the option relationship between positions [11, Corollary 4.3].
For any position {g} of either DNG(G) or GEN(G), we define ⌈g⌉ to be the unique element
of I ∪ {G} such that {g} ∈ X⌈g⌉ . For example, if e is the identity of G, then ⌈e⌉ = Φ(G).
We define pty(S) of a set S to be 0 if |S| is even and 1 if |S| is odd, and we say that S is
even if pty(S) = 0 and odd if pty(S) = 1. 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; by [11, Proposition 3.15], this is welldefined. The type can be calculated as in the following example: if an odd XI has options of
type (0, a, b) and (1, c, d), then type(XI ) = (1, mex{b, d, x}, x), where x = mex{a, c}. In the
achievement case, the type of the structure class XG is defined to be type(XG ) = (pty(G), 0, 0).
The option type of XI is the set
otype(XI ) := {type(XK ) | XK ∈ Opt(XI )}.

4

BRET J. BENESH, DANA C. ERNST, AND NÁNDOR SIEBEN

For both the avoidance and achievement games, the nim-number of the game is the same as
the nim-number of the initial position ∅, which is an even subset of Φ(G). Because of this, the
nim-number of the game is the second component of type(XΦ(G) ).
2.3. Achievement and Avoidance Game Strategy and Intuition. Let G be a nontrivial
finite group. In general, describing strategies in terms of nim-numbers is difficult, however we
are able to provide a full description of the relationship between the strategy and the nimnumber of DNG(G). A complete characterization is elusive for GEN(G).
After playing the avoidance game, the two players can notice that they spent the entire game
choosing elements from a single maximal subgroup M. The first player will have won if M
is odd, and the second player will have won if M is even. These facts immediately yield the
winning strategies for the two players. The second player should attempt to choose any legal
element of even order since that will ensure a final maximal subgroup of even order, while the
first player should try to select an element g ∈ G such that hg, ti = G for any element t ∈ G
of even order. Of course, only one of these strategies can be successful. Note that a winning
strategy for the first player is equivalent to choosing an element g ∈ G that is not contained
in any even maximal subgroup. The nim-numbers of the avoidance game were characterized in
the following theorem.
Theorem 2.1. [5, Theorem 6.3] Let G be a nontrivial finite group.
(1) If |G| = 2 or G is odd, then DNG(G) = ∗1.
(2) If G is cyclic with |G| ≡4 0 or the set of even maximal subgroups covers G, then
DNG(G) = ∗0.
(3) Otherwise, DNG(G) = ∗3.
It follows that a nim-number of 0 indicates that there is always an element of even order for
the second player to choose, regardless of the first player’s initial choice. Notice that G only
has odd maximal subgroups if |G| = 2 or G is odd, so a nim-number of 1 indicates that the
first player cannot lose, independent of strategy. A nim-number of 3 indicates that there is an
element not contained in any even maximal subgroup, and choosing this element on the first
move is sufficient to guarantee victory for the first player. However, the first player may lose by
failing to choose this element. Thus, the difference between DNG(G) = ∗1 and DNG(G) = ∗3
is that the first player needs to make a wise first move to ensure a win only in the latter case.
Now let G be Sn or An for n ≥ 5. We provide a description of the strategy for GEN(G),
but different positive nim-numbers for GEN(G) do not seem to translate to any obvious grouptheoretic description. The group G has the property that for every nontrivial g ∈ G, there is
an x ∈ G such that hg, xi = G. The first player can win by choosing the identity with the first
selection and an x such that hg, xi = G for the third move after the second player chooses a
nonidentity element g.
3. Achievement Games for Γ1 Groups
In this section we develop some general results about GEN(G) for a special class of groups
containing all of the nonabelian alternating groups and all but one of the nonabelian symmetric
groups.
Following [13, Definition 1.1], two elements x and y of a group G are called mates if hx, yi = G.
We say that a finite nonabelian group is in Γ1 if every nontrivial element of the group has a
mate (see [7, Definition 1.01] for a general definition of Γr ). It is known that Sn ∈ Γ1 for
n 6∈ {1, 2, 4} [16] and An ∈ Γ1 for n 6∈ {1, 2, 3} [8]. Moreover, Guralnick and Kantor [14] proved
that every finite nonabelian simple group is in Γ1 .

IMPARTIAL GAMES FOR GENERATING SYMMETRIC AND ALTERNATING GROUPS

5

For the remainder of this paper, we will rely on Γ1 groups having trivial Frattini subgroups.
Proposition 3.1. If G ∈ Γ1 , then Φ(G) = {e}.
Proof. For sake of a contradiction suppose that x is a nontrivial element of Φ(G). Since G ∈ Γ1 ,
x has a mate y. Then G = hx, yi ≤ hΦ(G), yi = hyi, where the last equality holds because
Φ(G) is the set of all nongenerators of G (see [15, Problem 2.7], for instance). This implies G
is cyclic and hence abelian, which contradicts the assumption that G ∈ Γ1 .

The following general results about Γ1 groups will be used to determine the nim-numbers of
GEN(Sn ) and GEN(An ). We define T := {t0 , . . . , t4 }, where the types ti are defined in Table 1.

t0
t1
t2
t3
t4

:= (pty(G), 0, 0)
:= (1, 1, 2)
:= (1, 2, 1)
:= (1, 4, 3)
:= (0, 1, 2)

otype(XI )

type(XI )

otype(XI )

type(XI )

{t0 }
{t0 , t1 }
{t0 , t2 }
{t0 , t3 }
{t0 , t1 , t2 }
{t0 , t1 , t3 }
{t0 , t2 , t3 }
{t0 , t1 , t2 , t3 }

t2 or t4
t1
t2
t2
t3
t1
t2
t3

{t0 , t4 }
{t0 , t1 , t4 }
{t0 , t2 , t4 }
{t0 , t3 , t4 }
{t0 , t1 , t2 , t4 }
{t0 , t1 , t3 , t4 }
{t0 , t2 , t3 , t4 }
{t0 , t1 , t2 , t3 , t4 }

t1 or t4
t1
t3
t1
t3
t1
t3
t3

Table 1. Complete list of possible option types for a nonterminal structure
class XI in GEN(G) with I 6= Φ(G) when G is a Γ1 group. Note that pty(I) and
otype(XI ) determine type(XI ).

Proposition 3.2. If I is a non-Frattini intersection subgroup of a Γ1 group G, then type(XI )
in GEN(G) satisfies

t1 , I is odd, otype(XI ) ∩ {t1 , t4 } =
6 ∅, t2 6∈ otype(XI )


t , I is odd, otype(X ) ∩ {t , t } = ∅
2
I
1 4
type(XI ) =
t
,
I
is
odd,
otype(X
)
∩
{t
6 ∅, t2 ∈ otype(XI )

3
I
1 , t4 } =

t , I is even.
4

Proof. The type of a terminal structure class must be t0 . The option type of any nonterminal
structure class XI of a Γ1 group with I 6= Φ(G) contains t0 . Structural induction and the
calculations in Table 1 shows that otype(XI ) ⊆ T implies type(XI ) ∈ T . That is, no types
outside of T arise. Note that a structure class of type t4 can never have an odd option by
Lagrange’s Theorem, so t4 only appears if otype(XI ) is a subset of {t0 , t4 }.

For odd G, only some of the calculations from Table 1 are needed since the only possible
option types are {t0 } and {t0 , t2 }. This observation is sufficient to determine GEN(G) for odd
G.
Corollary 3.3. If I is a non-Frattini intersection subgroup of an odd Γ1 group G, then type(XI )
in GEN(G) is t2 .
Proposition 3.4. If G is an odd Γ1 group, then GEN(G) = ∗2.

6

BRET J. BENESH, DANA C. ERNST, AND NÁNDOR SIEBEN

Proof. Every option of Φ(G) has type t2 by Corollary 3.3, so otype(XΦ(G) ) = {t2 }. Then
type(XΦ(G) ) = (1, mex{0, 1}, mex{2}) = (1, 2, 0),
so GEN(G) = ∗2.



Example 3.5. Since H := Z7 ⋊Z3 is in Γ1 , GEN(H) = ∗2 by Proposition 3.4. Note that H is the
smallest odd Γ1 group. The smallest odd nonabelian group that is not Γ1 is K := (Z3 ×Z3 )⋊Z3 ,
yet GEN(K) = ∗2, too. It is possible to get nim-numbers other than ∗2 for odd groups; in fact,
GEN(Z3 × Z3 × Z3 ) = ∗1. These three examples agree with [11, Corollary 4.8], which states
that GEN(G) ∈ {∗1, ∗2} for odd nontrivial G.
Proposition 3.6. Assume G ∈ Γ1 and I is an odd non-Frattini intersection subgroup of
G. If I is only contained in odd (respectively, even) maximal subgroups, then type(XI ) is t2
(respectively, t1 ).
Proof. Since I 6= Φ(G) and G ∈ Γ1 , t0 ∈ otype(XI ). In both cases of the proof, we use structural
induction on the structure classes.
First, we assume that I is only contained in odd maximal subgroups. If XJ is a nonterminal
option of XI , then J is also only contained in odd maximal subgroups. So type(XJ ) = t2 by
induction. Hence {t0 } ⊆ otype(XI ) ⊆ {t0 , t2 }, which implies type(XI ) = t2 using Proposition 3.2.
Next, we assume that I is only contained in even maximal subgroups. Since I is odd, there
is an involution t ∈
/ I such that I ∪ {t} is contained in an even maximal subgroup. The
structure class XJ containing I ∪ {t} is a type t4 option of XI . So we may conclude that
{t0 , t4 } ⊆ otype(XI ). Let XJ be a nonterminal option XI . If XI is even, then type(XJ ) = t4
by Table 1. If XJ is odd, then type(XJ ) = t1 by induction, since J is contained only in even
maximal subgroups. Hence {t0 , t4 } ⊆ otype(XI ) ⊆ {t0 , t1 , t4 }, which implies type(XI ) = t1
using Proposition 3.2.

For the rest of the paper we will only consider even groups.
Proposition 3.7. If G is an even Γ1

∗1,
GEN(G) = ∗3,

∗4,

group, then
t2 ∈
/ otype(XΦ(G) )
t2 ∈ otype(XΦ(G) ), t3 ∈
/ otype(XΦ(G) )
t2 , t3 ∈ otype(XΦ(G) ).

Proof. Since G ∈ Γ1 , XΦ(G) has no option of type t0 . Let t be an involution of G and XJ be
the structure class containing Φ(G) ∪ {t}. Then XJ is a type t4 option of XΦ(G) . Hence {t4 } ⊆
otype(XΦ(G) ) ⊆ {t1 , . . . , t4 }. We compute type(XΦ(G) ) for every possibility for otype(XΦ(G) )
in Table 2. The result follows from this calculation and the fact that GEN(G) is equal to the
second component of type(XΦ(G) ).

S
Recall that a subset C of the power set of a group G is a covering of G if C = G; in this
case, we also say that C covers G or G is covered by C.
Corollary 3.8. If a Γ1 group G is covered by the set of even maximal subgroups of G, then
GEN(G) = ∗1.
Proof. We will demonstrate that t2 ∈
/ otype(XΦ(G) ), which will suffice by Proposition 3.7. Let
XI be an option of XΦ(G) . Then I = ⌈g⌉ for some g ∈ G. If ⌈g⌉ is even, then type(X⌈g⌉ ) = t4 6= t2
by Proposition 3.2. Now assume that ⌈g⌉ is odd. Since G is covered by the set of even maximal
subgroups, g is contained in an even maximal subgroup M. By Cauchy’s Theorem, there is

IMPARTIAL GAMES FOR GENERATING SYMMETRIC AND ALTERNATING GROUPS

7

otype(XΦ(G) ) otype(XΦ(G) ) type(XΦ(G) )
{t4 }
{t2 , t4 }
{t3 , t4 }
{t2 , t3 , t4 }

{t1 , t4 }
{t1 , t2 , t4 }
{t1 , t3 , t4 }
{t1 , t2 , t3 , t4 }

(1, 1, 0)
(1, 3, 0)
(1, 1, 0)
(1, 4, 0)

Table 2. Spectrum of type(XΦ(G) ) for G ∈ Γ1 . Note that Φ(G) is the trivial
group in this case.
an involution t in M. The structure class XJ containing {g, t} is a type t4 option of X⌈g⌉ by
Proposition 3.2. So type(X⌈g⌉ ) cannot be t2 again by Proposition 3.2.

If a noncyclic group G has only even maximal subgroups, then the set of even maximal
subgroups covers G. The next corollary then follows immediately from Corollary 3.8.
Corollary 3.9. If G is a Γ1 group with only even maximal subgroups, then GEN(G) = ∗1.
4. Symmetric Groups
In light of Corollary 3.9, we need only a simple proposition to completely determine the
nim-numbers for the achievement and avoidance games for symmetric groups.
Proposition 4.1. If n ≥ 4, then every maximal subgroup of Sn has even order.
Proof. An odd subgroup cannot be maximal since it is contained in the even subgroup An . 
The nim-numbers for the avoidance game for generating symmetric groups were computed
in [11] for n ∈ {2, 3, 4} and in [5] for n ≥ 5. We include the statement of the result here for
completeness. Note that S1 is trivial, so DNG(S1 ) does not exist.
Theorem 4.2. The values of DNG(Sn ) are

∗1, n = 2
DNG(Sn ) = ∗3, n = 3
∗0, n ≥ 4.

We are now ready to determine the nim-numbers for GEN(Sn ). This result verifies the portion
of [11, Conjecture 9.1] on symmetric groups.
Theorem 4.3. The values of GEN(Sn ) are

∗0, n ∈ {1, 4}


∗2, n = 2
GEN(Sn ) =
∗3, n = 3


∗1, n ≥ 5.

Proof. The empty set is a generating set for the trivial group, so GEN(S1 ) = ∗0. The cases
where n ∈ {2, 3, 4} were done in [11], so assume n ≥ 5. By [16], Sn ∈ Γ1 . By Proposition 4.1,
every maximal subgroup of Sn has even order. Hence GEN(Sn ) = ∗1 by Corollary 3.9.

Theorems 4.2 and 4.3 immediately yield the following result.
Corollary 4.4. The first player has a winning strategy for

8

BRET J. BENESH, DANA C. ERNST, AND NÁNDOR SIEBEN

• DNG(Sn ) if and only if n ∈ {2, 3};
• GEN(Sn ) if and only if n 6∈ {1, 4}.
5. Alternating Groups
Determining the nim-numbers of DNG(An ) and GEN(An ) requires much more background.
The following well-known proposition follows from Feit and Thompson’s Odd Order Theorem [12] and the fact that every group of order 2m for some odd m has a normal subgroup of
order m (see [15, Corollary 6.12] for example).
Proposition 5.1. If U is a nonabelian simple group, then 4 divides |U|.
Below, we will make use of a special case of the O’Nan–Scott Theorem (see [17] for instance).
Recall that the general affine group of degree n over a field of size pk for a prime p is defined
to be the semidirect product AGL(n, pk ) := V ⋊ GL(n, pk ) of a vector space V of size pnk (i.e.,
dimension n) and the general linear group, where the latter acts on V by linear transformations.
Theorem 5.2 (O’Nan–Scott). Let An act on a set Ω of size n. If M is a maximal subgroup of
An , then M must be one of the following:
(1) (Intransitive Case) M = (Sm × Sk ) ∩ An with n = m + k;
(2) (Imprimitive Case) M = (Sm ≀ Sk ) ∩ An with n = mk, m, k > 1;
(3) (Affine Case) M = AGL(k, p) ∩ An with n = pk and p prime;
(4) (Diagonal Case) M = (U k .(Out(U) × Sk )) ∩ An with U a nonabelian simple group,
k ≥ 2, and n = |U|k−1 ;
(5) (Wreath Case) M = (Sm ≀ Sk ) ∩ An with n = mk , m ≥ 5, k > 1, and either k 6= 2 or
m 6≡4 2;
(6) (Almost Simple Case) U ⊳ M ≤ Aut(U), where U is a nonabelian simple group and M
acts primitively on Ω.
Remark 5.3. We will see that AGL(1, p) plays an important role in determining the nim×
numbers for alternating groups. Note that GL(1, p) ∼
= Z×
p , where Zp is the group of units
of Zp , which is cyclic of order p − 1. Then AGL(1, p) ∼
= Zp ⋊ Z×
p , where the action is field
multiplication. It is also easy to check that every element of AGL(1, p) either has order p or
has order dividing p − 1.
Corollary 5.4. Let n ≥ 5. If An has an odd maximal subgroup, then n is prime, n ≡4 3,
and every odd maximal subgroup of An is isomorphic to AGL(1, n) ∩ An , and hence has order
1
n(n − 1).
2
Proof. If H is a subgroup of Sn that is not contained in An , then |H ∩ An | = 21 |H|. Then
H ∩ An is even if 4 divides |H|. By inspection, Sm × Sk and Sm ≀ Sk have orders that are
divisible by 4 under the conditions specified in the Intransitive, Imprimitive, and Wreath Cases
of Theorem 5.2, so An cannot have an odd maximal subgroup in those cases. Similarly, any
U k .(Out(U)) ×Sk ) and any almost simple M are divisible by 4 by Proposition 5.1, so An cannot
have an odd maximal subgroup in the Diagonal or Almost Simple Cases of Theorem 5.2.
This leaves only the Affine Case to be considered. Assume that n = pk for some prime
p, and let M be a maximal subgroup of An in the Affine case of Theorem 5.2. The order
of AGL(k, p) is pk (pk − 1)(pk − p)(pk − p2 ) · · · (pk − pk−1 ), which is divisible by 4 if k ≥ 2.
Then we may assume that k = 1, so p = n ≥ 5 and we conclude that p is odd. Then
M ∼
= Zp ⋊ Z×
= AGL(1, p) ∩ Ap ∼
p ∩ Ap by Remark 5.3. Since Ap does not contain a (p − 1)1
cycle, we conclude that |M| = 2 p(p − 1), which is odd if and only if p ≡4 3.


IMPARTIAL GAMES FOR GENERATING SYMMETRIC AND ALTERNATING GROUPS

9

The next result follows directly from Remark 5.3 and Corollary 5.4.
Corollary 5.5. Let n ≥ 5. If An has an odd maximal subgroup M, then every nontrivial
element of M is either an n-cycle or a power of a product of two 21 (n − 1)-cycles.
Proposition 5.6. Let n ≥ 5. Then An has an odd maximal subgroup if and only if n is prime,
n ≡4 3, and n 6∈ {7, 11, 23}.
Proof. Suppose that An has an odd maximal subgroup M. Then by Corollary 5.4, n is prime,
n ≡4 3, and M ∼
= AGL(1, n) ∩ An is not maximal if
= AGL(1, n) ∩ An . The subgroup M ∼
n ∈ {7, 11, 23} by the main theorem from [17].
Thus, we may assume that n is prime, n ≡4 3, and n 6∈ {7, 11, 23}. Again by the main
theorem from [17], we have that AGL(1, n) ∩ An is maximal in An . Its order is 21 n(n − 1) by
Corollary 5.4, which is odd because n ≡4 3.

Recall [10] that a prime p is a generalized repunit prime if there is a prime-power q and
integer n such that p = (q n − 1)/(q − 1). The next definition will simplify the statement of the
proposition that follows.
Definition 5.7. A prime p is said to be a ζ-prime if all of the following conditions hold:
(1) p ≡4 3;
(2) p ∈
/ {11, 23};
(3) p is not a generalized repunit prime.
The ζ-primes that are less than 100 are 19, 43, 47, 59, 67, 71, 79, and 83 [1]. Note that 7 = 1112
is a generalized repunit prime, so we did not have to explicitly exclude the prime 7 from
Condition (2) to match the set of exceptions from Proposition 5.6.
Proposition 5.8. If n ≥ 5, then the following are equivalent.
(1) The even maximal subgroups of n fail to cover An .
(2) There exists an n-cycle of An that is not in any even maximal subgroup.
(3) n is a ζ-prime.
Proof. First, we show that Items (1) and (2) are equivalent. If there exists an n-cycle of An
that is not in any even maximal subgroup, then the even maximal subgroups of An fail to cover
An by definition. Now suppose that the even maximal subgroups of n fail to cover An . Then
there must be an odd maximal subgroup of An , so n is equal to some prime p with p ≡4 3
and p 6∈ {7, 11, 23} by Proposition 5.6. Let r be the integer such that p = 2r + 1. If M is an
odd maximal subgroup of Ap , then each element of M is either trivial, a p-cycle, or a power
of two disjoint r-cycles by Corollary 5.5. The identity and every power of two disjoint r-cycles
is contained in an even subgroup isomorphic to (Sr × Sr ) ∩ Ap , which is contained in some
even maximal subgroup. Therefore, it must be a p-cycle that is not contained an even maximal
subgroup.
To finish, we show that Items (2) and (3) are equivalent. Let g be an n-cycle of An that is not
in any even maximal subgroup. Then g must be contained in an odd maximal subgroup because
An is not cyclic. Proposition 5.6 implies that n is a prime such that n ≡4 3 with n 6∈ {7, 11, 23}.
Theorem 5.2 and the fact that n is prime imply that any maximal subgroup containing g must
be isomorphic to AGL(1, n) ∩ An or an almost simple group H that acts primitively on a set of
size n. The former has odd order, and [18, Table 3] lists all the possibilities for H. Therefore, g
will be contained in an even maximal subgroup H if and only if H appears in [18, Table 3]. The
only rows in this table where the second column (labeled by n) is equal to the fourth column

10

BRET J. BENESH, DANA C. ERNST, AND NÁNDOR SIEBEN

(labeled by p, which is equal to n in our case) correspond to the first PSL(d, q), Sz(q), M23 ,
and M11 . But the row for PSL(d, q) implies that n is a generalized repunit prime, the row for
Sz(q) implies that n ≡4 1, and the other two imply that n ∈ {7, 11, 23}. So the ζ-primes were
defined exactly to exclude the entries in this table. Therefore, if g is not contained in any even
maximal subgroup, then g is not in any H listed in [18, Table 3] and hence p is a ζ-prime.
Conversely, assume that n is a ζ-prime. Then n is a prime such that n ≡4 3 and n ∈
/
{7, 11, 23}. So An has no subgroup H from [18, Table 3], and hence g is not contained in any
even maximal subgroup, proving Item (2).

5.1. Avoidance Games for Generating Alternating Groups. We will use the following
result to determine the nim-numbers of DNG(An ).
Proposition 5.9. [5, Corollary 6.4] Let G be a nontrivial finite group.
(1) If all maximal subgroups of G are odd, then DNG(G) = ∗1.
(2) If all maximal subgroups of G are even, then DNG(G) = ∗0.
(3) Assume G has both even and odd maximal subgroups.
(a) If the set of even maximal subgroups covers G, then DNG(G) = ∗0.
(b) If the set of even maximal subgroups does not cover G, then DNG(G) = ∗3.
Theorem 5.10. The values of DNG(An ) are

∗3, n ∈ {3, 4} or n is a ζ-prime
DNG(An ) =
∗0, otherwise.
Proof. The cases where n ∈ {3, 4} were done in [11], so assume n ≥ 5. If n is not a ζ-prime, then
the set of even maximal subgroups covers An by Proposition 5.8; in this case, DNG(An ) = ∗0 by
Proposition 5.9. If n is a ζ-prime, then the set of even maximal subgroups fails to cover An by
Proposition 5.8. This implies that An has an odd maximal subgroup. The group An contains
the proper subgroup h(1, 2)(3, 4)i of order 2, and so An must also contain an even maximal
subgroup. We may conclude that DNG(An ) = ∗3 if n is a ζ-prime by Proposition 5.9.

Just like for S1 , A1 and A2 are trivial, so DNG(A1 ) and DNG(A2 ) do not exist.
5.2. Achievement Games for Generating Alternating Groups. We will see that ζ-primes
play an important role in determining the nim-numbers of GEN(An ) as they did for DNG(An ).
The following theorem refutes the portion of [11, Conjecture 9.1] on alternating groups.
Theorem 5.11. The values of GEN(An ) are

∗0,



∗2,
GEN(An ) = ∗3,



∗4,
∗1,

n ∈ {1, 2}
n=3
n=4
n is a ζ-prime
otherwise.

Proof. The empty set is a generating set for the trivial group, so GEN(A1 ) = ∗0 = GEN(A2 ).
The cases where n ∈ {3, 4} were done in [11], so assume n ≥ 5. By [8], An ∈ Γ1 . If every
maximal subgroup of An has even order, then GEN(An ) = ∗1 by Corollary 3.9. We only need
to determine what happens in the case that An has an odd maximal subgroup. Then n = p for
some prime p 6∈ {7, 11, 23} such that p ≡4 3 by Proposition 5.6. We may write p = 2r + 1 for
some odd r. If p is not a ζ-prime, then the even maximal subgroups cover Ap by Proposition 5.8,
so GEN(Ap ) = ∗1 by Corollary 3.8.

IMPARTIAL GAMES FOR GENERATING SYMMETRIC AND ALTERNATING GROUPS

11

So assume that p is a ζ-prime. Then there is an odd maximal subgroup M of Ap ; we know
that M must be isomorphic to AGL(1, p) ∩ Ap by Corollary 5.4. Then M = hg, xi where g is a
p-cycle and x is the product of two r-cycles and each element of M is either trivial, a p-cycle,
or a power of two disjoint r-cycles by Corollary 5.5. By Proposition 3.6, type(M) = t2 .
The element x is contained in an even subgroup isomorphic to (Sr × Sr ) ∩ Ap , so X⌈x⌉ has an
even option of type t4 . The structure class X⌈x⌉ has the type t2 option XM , since {x, g} ∈ XM .
Proposition 3.2 implies type(X⌈x⌉ ) = t3 .
Since p is a ζ-prime, there is a p-cycle y that is not contained in any even maximal subgroup by
Proposition 5.8. Since all p-cycles are conjugate in Sp , we conclude that g is also only contained
in odd maximal subgroups, so type(X⌈g⌉ ) = t2 by Proposition 3.6. Then t2 , t3 ∈ otype(XΦ(Ap ) ),
so GEN(Ap ) = ∗4 by Proposition 3.7.

5.3. Outcomes for Alternating Groups. Theorems 5.10 and 5.11 immediately yield the
following result.
Corollary 5.12. The first player has a winning strategy for
• DNG(An ) if and only if n ∈ {3, 4} or n is a ζ-prime;
• GEN(An ) if and only if n 6∈ {1, 2}.
6. Further Questions
We conclude with a few open problems.
(1) Recall that every finite simple group is in Γ1 by [14]. It is well-known that many finite
simple groups have the property that every maximal subgroup has even order (see [5], [9],
and [20]). For such G, DNG(G) = ∗0 by the main results from [5] and GEN(G) = ∗1 by
Corollary 3.9. Can we determine the nim-numbers for DNG(G) and GEN(G) for every
finite simple group G?
(2) Can we determine the nim-numbers for DNG(G) and GEN(G) if G is almost simple?
(3) Can the conditions from Proposition 3.7 be translated into group-theoretic conditions?
For instance, can one describe when t2 ∈ otype(XΦ(G) ) based on the subgroup structure
of G?
References
1. The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org (2010),
Sequence A270123.
2. M.H. Albert, R.J. Nowakowski, and D. Wolfe, Lessons in play: an introduction to combinatorial game
theory, AMC 10 (2007), 12.
3. M. Anderson and F. Harary, Achievement and avoidance games for generating abelian groups, Internat. J.
Game Theory 16 (1987), no. 4, 321–325.
4. 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).
5. B.J. Benesh, D.C. Ernst, and N. Sieben, Impartial avoidance games for generating finite groups, NorthWestern European Journal of Mathematics 2 (2016), 83–102.
6. M. Brandenburg, Algebraic games, arXiv:1205.2884 (2012).
7. J.L. Brenner and J. Wiegold, Two-generator groups. I, Michigan Math. J. 22 (1975), 53–64.
8. N. Chigira et al., Generating alternating groups, Hokkaido Mathematical Journal 26 (1997), 435–438.
9. J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson, Atlas of finite groups: maximal
subgroups and ordinary characters for simple groups, Oxford University Press Eynsham, 1985.
10. H. Dubner, Generalized repunit primes, Math. Comp. 61 (1993), no. 204, 927–930.
11. D.C. Ernst and N. Sieben, Impartial achievement and avoidance games for generating finite groups,
arXiv:1407.0784 (2014).

12

BRET J. BENESH, DANA C. ERNST, AND NÁNDOR SIEBEN

12. W. Feit and J.G. Thompson, Solvability of groups of odd order, Pacific J. Math. 13 (1963), 775–1029.
13. T. Foguel, Finite groups with a special 2-generator property, Pacific J. Math. 170 (1995), no. 2, 483–495.
14. R.M. Guralnick and W.M. Kantor, Probabilistic generation of finite simple groups, J. Algebra 234 (2000),
no. 2, 743–792, Special issue in honor of Helmut Wielandt.
15. I.M. Isaacs, Algebra: a graduate course, Graduate Studies in Mathematics, vol. 100, American Mathematical
Society, Providence, RI, 2009, Reprint of the 1994 original.
16. I.M. Isaacs and T. Zieschang, Generating symmetric groups, American Mathematical Monthly (1995), 734–
739.
17. M.W. Liebeck, C.E. Praeger, and J. Saxl, A classification of the maximal subgroups of the finite alternating
and symmetric groups, J. Algebra 111 (1987), no. 2, 365–383.
18. M.W. Liebeck and J. Saxl, Primitive permutation groups containing an element of large prime order, J.
Lond. Math. Soc. 2 (1985), no. 2, 237–249.
19. A.N. Siegel, Combinatorial game theory, Graduate Studies in Mathematics, vol. 146, American Mathematical Society, Providence, RI, 2013.
20. R.A. Wilson, The finite simple groups, Graduate Texts in Mathematics, vol. 251, Springer-Verlag London,
Ltd., London, 2009.
Bret Benesh, Department of Mathematics, College of Saint Benedict and Saint John’s
University, 37 College Avenue South, Saint Joseph, MN 56374-5011, USA
E-mail address: bbenesh@csbsju.edu
Dana Ernst and Nándor Sieben, Department of Mathematics and Statistics, Northern Arizona University, PO Box 5717, Flagstaff, AZ 86011-5717, USA
E-mail address: Dana.Ernst@nau.edu, Nandor.Sieben@nau.edu

