A q-player impartial avoidance game for generating finite groups

Abstract

We study a q-player variation of the impartial avoidance game introduced by Anderson and Harary, where q is a prime. The game is played by the q players taking turns selecting previously-unselected elements of a finite group. The losing player is the one who selects an element that causes the set of jointly-selected elements to be a generating set for the group, with the previous player winning. We introduce a ranking system for the other players to prevent coalitions. We describe the winning strategy for these games on cyclic, nilpotent, dihedral, and dicyclic groups.

1 Introduction

The game Do Not Generate was introduced by Anderson and Harary Anderson and Harary (1987). In this game, two players take turns selecting previously unselected elements of a finite group until the group is generated by the jointly-selected elements. The losing player is the first player who selects an element that causes the jointly-selected elements to generate the entire group. The strategies were classified in Barnes (1988), and the strategies and nim-numbers for these games were classified in Benesh et al. (2016a) and Benesh et al. (2016b). Do Not Generate cannot be played on the trivial group, as in this case the empty set generates the entire group implying there are no legal moves for either player. Thus, we will assume that all groups are nontrivial. We modify this game to include q players for a prime q, and we use the notation $\text{ DNG }_q(G)$ to denote the game on a nontrivial finite group G with q players.

If n is an integer, we define $[n]_q$ to be the unique integer i in $\{1,2,3,\ldots ,q\}$ such that $n \equiv i \bmod {q}$. We will simply write [n] for $[n]_q$ if there is no risk of confusion, and we will write [H] instead of [|H|] if H is a group. Additionally, let $P_1,P_2,\ldots ,P_q$ denote the q players of $\text{ DNG }_q(G)$ for a nontrivial finite group G, where $P_i$ makes the ith move of the game.

We give two results on $\text{ DNG }_q(G)$ on finite nilpotent groups G, which are finite groups that can be written as a direct product of their Sylow subgroups. The first is a special case of the second, and d(G) denotes the minimum size of a generating set of a group G.

Theorem 7 Let G be a nontrivial finite cyclic group of order n. Let p be a prime divisor of n such that [n / p] is minimal. Then $P_{[n/p]}$has a winning strategy in $\text{ DNG }_q(G)$.

Theorem 12 Let Gbe a nontrivial finite nilpotent group. If qis a prime that divides |G|,then the winner of $\text{ DNG }_q(G)$is

1.:

$P_j$ if $|G| \equiv jq \bmod {q^2}$ for some $j \in \{1,2,\ldots ,q-1\}$ and $d(G)\le j$

2.:

$P_q$ if $|G| \equiv jq \bmod {q^2}$ for some $j \in \{1,2,\ldots ,q-1\}$ and $d(G)> j$

3.:

$P_q$if $|G| \equiv 0 \bmod {q^2}$.

If we are considering $\text{ DNG }_3(G)$, we can be more specific than the previous result.

Corollary 13 Let G be a nontrivial finite nilpotent group, and let Hbe the direct product of Sylow r-groups of Gsuch that $r \equiv 1 \bmod {3}$and Kbe the direct product of Sylow t-groups of G such that $t \equiv 2 \bmod {3}$. Then for $\text{ DNG }_3(G)$,

1.:

$P_1$ has a winning strategy in the following cases.

(a):

$|G| \equiv 1 \bmod {3}$ and $2d(H) \ge d(K)+1$

(b):

$|G| \equiv 2 \bmod {3}$ and $2d(K) \ge d(H)+1$

(c):

$|G| \equiv 3 \bmod {9}$ and $d(G)=1$

2.:

$P_2$ has a winning strategy in the following cases.

(a):

$|G| \equiv 1 \bmod {3}$ and $2d(H) < d(K)+1$

(b):

$|G| \equiv 2 \bmod {3}$ and $2d(K) < d(H)+1$

(c):

$|G| \equiv 6 \bmod {9}$ and $d(G)\le 2$

3. :

$P_3$ has a winning strategy in the following cases.

(a) :

$|G| \equiv 0 \bmod {9}$

(b) :

$|G| \equiv 3 \bmod {9}$ and $d(G) \ge 2$

(c) :

$|G| \equiv 6 \bmod {9}$ and $d(G) \ge 3$

Our final result is about dihedral and dicyclic groups, where dicyclic groups are generalizations of the quaternion group of order 8.

Theorem 15 Let Gbe a dihedral group or dicyclic group and define

$$\begin{aligned} W= & {} \left\{ [|G|/p] : p \mid |G|, p \text{ odd }\right\} \\ X= & {} \left\{ [|G|/p] : p \mid |G|, p \text{ odd }, [|G|/p] \not =1\right\} \end{aligned}$$

We let $m=\min W$if $W \not =\emptyset$and $m'=\min X$if $X \not =\emptyset$.Then for $\text{ DNG }_q(G)$,

1.:

$P_{[|G|/2]}$ has a winning strategy if one of the following is true.

(a):

$|G|=2^k$for some k.

(b):

$[|G|/2] \le m$

(c):

$1= m < [|G|/2]$, $X=\emptyset$, and |G| / 2 is even

(d):

$1= m < [|G|/2] \le m'$, $X\not =\emptyset$

2.:

$P_{m}$ has a winning strategy if one of the following is true.

(a):

$1< m < [|G|/2]$

(b):

$m=1$, $X=\emptyset$, and |G| / 2 is odd

3.:

$P_{m'}$has a winning strategy if $1= m< m' < [|G|/2]$ and $X \not =\emptyset$.

2 Preliminaries

We are generalizing a 2-player game to a q-player game for a prime $q \ge 2$. This introduces the possibility of the players forming coalitions, which greatly adds to the complexity of the game. Such games were studied in Li (1978), Propp (2000), and Straffin (1985), with various strategies for reducing the complexity. We adopt the convention from Li (1978), which is described next.

We will call the players $P_1, \ldots , P_q$, where $P_i$ makes the nth move if and only if $n \equiv i \bmod {q}$. If $P_m$ makes the last legal move, we say that $P_m$ wins, and we rank each player in the following order:

$$\begin{aligned} P_m, P_{m+1},P_{m+2},\ldots ,P_q,P_1,P_2,\ldots ,P_{m-1}. \end{aligned}$$

Thus, $P_m$ wins, $P_{m+1}$ is runner-up, $P_{m+2}$ is the second runner-up, and so on. Thus, if $P_m$ wins, then $P_i$ ends up in $[i-m+1]$th place. We will assume that each $P_i$ plays optimally to optimize the $P_i$’s rank at the end of the game by minimizing $[i-m+1]$.

The intuition for the game $\text{ DNG }_q(G)$ on a nontrivial finite group G follows. Once the game is over, the q players will realize that they simply took turns selecting elements from a single maximal subgroup M, although they may not realize what M is early in the game. To see this, consider that if the elements $X:=\{x_1,\ldots ,x_n\}$ have been selected after the nth turn of the game, then one considers the subgroup $H:=\langle X \rangle$ to determine whether the game is over. If $H < G$, play continues. Because G is a finite group, H is contained in a maximal subgroup M. The $[n+1]$st player will be able to avoid losing on the $(n+1)$st turn exactly when $X \not =M$ by selecting any $g \in M {\setminus } X$. If $X=M$, then $\langle X \cup \{h\}\rangle =G$ for any $h \in G {\setminus } X$.

Thus, for every $\text{ DNG }_q(G)$ game, there will be a unique maximal subgroup M such that every element of M will be selected if the game is played optimally; let $\overline{M}$ denote this maximal subgroup. We can now determine the outcome of the game according to the value of $[\overline{M}]$.

Lemma 1

For any nontrivial finite group G, $P_{[\overline{M}]}$ wins $\text{ DNG }_q(G)$.

Proof

We can use the Division Algorithm to write $|\overline{M}|=nq+r$ for some $0 \le r \le q-1$. Then we see that each of the q players contributes n elements to the pool of selected elements, and the first r players get to select an additional element of $\overline{M}$. Therefore, $P_{r+1}$ must select an element outside of $\overline{M}$, and hence generates the group and loses. Because $r=[\overline{M}]$ if $r>0$ and $P_q$ wins if $r=0$, we see that $P_{[\overline{M}]}$ wins $\text{ DNG }_q(G)$.

The following lemma describes $P_q$’s advantage, noting that Cauchy’s Theorem guarantees that an element of order q exists.

Lemma 2

Let G be a nontrivial finite group G and $X=\{x_1,\ldots ,x_{j}\}$ denote the set of elements selected by $P_1,\ldots ,P_{j}$. If $\langle X \rangle < G$ and X contains an element of order q, then $P_q$ wins $\text{ DNG }_q(G)$.

Proof

Since $X \subseteq \overline{M}$, $\overline{M}$ will contain an element of order q. By Lagrange’s Theorem, q divides $|\overline{M}|$. By Lemma 1, $P_{[\overline{M}]}=P_q$ wins.

Let $D_8$ denote the dihedral group of order 8. Figure 1 shows an optimally played game of $\text{ DNG }_3(G)$ for the nilpotent group $G:=D_8 \times \mathbb {Z}_3$, where $P_2$ wins with the help of $P_1$ by Lemma 1. Figure 2 shows an optimally played game where $P_3$ wins on $\text{ DNG }_3(G)$ on $G:=\mathbb {Z}_2 \times \mathbb {Z}_2 \times \mathbb {Z}_3$ by Lemma 2, with help from $P_2$.

Fig. 1

This is an optimally played game for $\text{ DNG }_3(G)$ on $G:=D_8 \times \mathbb {Z}_3$ with $D_8=\langle r,f \rangle$ of order 8 and $\mathbb {Z}_3=\{0,1,2\}$. Notice that the game is determined with the selection of $\mathbf {(f,0)}$, since that guarantees that $|\overline{M}|$ will be $8 \equiv 2 \bmod {3}$, guaranteeing a victory for $P_2$ by Lemma 1

Fig. 2

This is an optimally played game for $\text{ DNG }_3(G)$ on $G:=\mathbb {Z}_2 \times \mathbb {Z}_2 \times \mathbb {Z}_3$ with $\mathbb {Z}_2=\{0,1\}$ and $\mathbb {Z}_3=\{0,1,2\}$. Notice that the game is determined with the selection of $\mathbf {(0,0,1)}$, since that guarantees that $|\overline{M}|$ will be divisible by 3, guaranteeing a victory for $P_3$ by Lemma 2

Let d(G) denote the minimum size of a generating set of a group G. We end with a couple of general results.

Proposition 3

If G is a finite group such that q divides |G| and $d(G) \ge q+1$, then $P_q$ has a winning strategy in $\text{ DNG }_q(G)$.

Proof

Suppose that $P_i$ selects $x_i$ for $1\le i \le q-1$. If there is a i such that $x_i$ has order q, then $P_q$ wins by Lemma 2. So suppose that none of the $x_i$ have order q. By Cauchy’s Theorem, there is an element t of order q in G, and $\langle x_1,\ldots ,x_{q-1},t \rangle < G$ since $d(G) \ge q+1$. Then $P_q$ wins by Lemma 2.

We now discuss some qualities of groups where Lemma 2 applies, which will allow us to partially generalize the results about $\text{ DNG }_2(G)$ from Benesh et al. (2016b). Before stating the results for $\text{ DNG }_2(G)$, we state a definition.

Definition 4

Let G be a noncyclic finite group, and denote the set of maximal subgroups of G by $\mathcal {M}_G$. We say that a subset $\mathcal {X}$ of $\mathcal {M}_G$ n-covers G if for every n elements $g_1,\ldots ,g_n \in G$, there is a maximal subgroup $M \in \mathcal {X}$ such that $g_1,\ldots ,g_n \in M$.

One of the main results of Benesh et al. (2016b) about $\text{ DNG }_2(G)$ is below.

Corollary 5

[Benesh et al. (2016b), Corollary 5.5] If G is a noncyclic group of even order, then the second player has a winning strategy if and only if the set of maximal subgroups of even order 1-covers G.

We let $\mathcal {M}_G^q$ be the set of maximal subgroups of G with orders divisible by q. The next proposition is a first approximation for a $\text{ DNG }_q(G)$ version of the Corollary 5.

Proposition 6

Let G be a finite noncyclic group. If $\mathcal {M}_G^q$ j-covers G, then $P_i$ does not have a winning strategy for $1\le i \le j$ for $\text{ DNG }_q(G)$. In particular, $P_q$ has a winning strategy if $\mathcal {M}_G^q$ $(q-1)$-covers G. Additionally, if $\mathcal {M}_G^q$ does not 1-cover G, then $P_q$ does not have a winning strategy for $\text{ DNG }_q(G)$.

Proof

Suppose that $\mathcal {M}_G^q$ j-covers G and $P_i$ initially selects an element $x_i$ of G for $1 \le i \le j$. Because $\mathcal {M}_G^q$ j-covers G, there is a maximal subgroup $M \in \mathcal {M}_G^q$ such that $x_1,\ldots ,x_j\in M$. Since $P_{j+1}$ prefers $P_q$ to win over $P_i$ for $1 \le i \le j$, $P_{j+1}$ could prevent such $P_i$ from winning by selecting an element t of M of order q, which would result in a win for $P_q$ by Lemma 2. Since $P_{j+1}$ may have a better strategy than selecting t, we conclude that $P_k$ will win for some $j+1 \le k \le q$. So if $j=q-1$, then $P_q$ wins.

Now assume that $\mathcal {M}_G^q$ does not 1-cover G. Recall that $P_1$ prefers any player to win over $P_q$. Since $\mathcal {M}_G^q$ does not 1-cover G, $P_1$ can choose an element not contained in $\cup \mathcal {M}_G^q$. Then $\overline{M} \not \in \mathcal {M}_G^q$, so $P_q$ does not win by Lemma 1. $\square$

3 Cyclic groups

We start by considering a cyclic group G with generator g and order n. In the case of cyclic groups, $P_1$ can determine $\overline{M}$ by selecting $g^p$ on the first move to generate a maximal subgroup of order n / p for some prime p. This allows us to conclude the following.

Theorem 7

Let G be a nontrivial finite cyclic group of order n. Let p be a prime divisor of n such that [n / p] is minimal. Then $P_{[n/p]}$ has a winning strategy in $\text{ DNG }_q(G)$.

Proof

By Lemma 1, it suffices to consider the maximal subgroups of G. It is well-known that every maximal subgroup M of G has order n / t for some prime t if G is cyclic, so we conclude that the winner will be $P_{[n/t]}$ for some t. Because G is cyclic, every subgroup is also cyclic, and $P_1$ can optimize its ranking by selecting a generator of a maximal subgroup of order n / p such that [n / p] is minimal. Thus, $P_{[n/p]}$ wins by Lemma 1.

Corollary 8

Let G be a nontrivial finite cyclic group of order n, and suppose that the game is $\text{ DNG }_3(G)$.

• 1. If $n \equiv 1 \bmod {3}$ and there is a prime number p dividing n such that $p \equiv 1 \bmod {3}$, then $P_1$ has a winning strategy.

• 2. If $n \equiv 1 \bmod {3}$ and every prime number p dividing n is such that $p \equiv 2 \bmod {3}$, then $P_2$ has a winning strategy.

• 3. If $n \equiv 2 \bmod {3}$, then $P_1$ has a winning strategy.

• 4. If $n \equiv 0 \bmod {9}$, then $P_3$ has a winning strategy.

• 5. If $n \equiv 3 \bmod {9}$, then $P_1$ has a winning strategy.

• 6. If $n \equiv 6 \bmod {9}$, then $P_2$ has a winning strategy.

Proof

If $n \equiv 1 \bmod {3}$, then $[n/p]=1$ if $p \equiv 1 \bmod {3}$ and $[n/p]=2$ otherwise. Thus, $P_1$ wins if there is a prime p such that $[n/p]=1$ and $P_2$ wins otherwise when $n \equiv 1 \bmod {3}$. If $n \equiv 2 \bmod {3}$, then there must be a prime p such that $p \equiv 2 \bmod {3}$. Then $[n/p]=1$ and $P_1$ wins.

So assume that $n \equiv 0 \bmod {3}$, in which case $[n/p]=3$ for all primes $p \not =3$. If $n \equiv 0 \bmod {9}$, then $[n/3]=3$ as well, and hence $P_3$ wins regardless of strategy. If $n \equiv 3 \bmod {9}$, then $[n/3]=1$ and $P_1$ wins. If $n \equiv 6 \bmod {9}$, then $[n/3]=2$, and $P_2$ wins because $P_1$ prefers $P_2$ over $P_3$.

4 Nilpotent groups

Recall that nilpotent groups are a generalization of abelian groups and have the following properties.

Theorem 9

[Isaacs (2009), Theorem 8.19] Let G be a finite group. Then the following are equivalent.

• 1. G is nilpotent.

• 2. Every maximal subgroup of G is normal in G.

• 3. G is isomorphic to a direct product of its Sylow subgroups.

Proposition 10

[Isaacs (2009), Problem 8.11] If M is a maximal subgroup of a finite nilpotent group G, then $|M|=|G|/p$ for some prime divisor p of |G|.

Corollary 11

If p is a prime and G is a nontrivial finite p-group of order $p^n$, then $P_{[p^{n-1}]}$ wins $\text{ DNG }_q(G)$.

Proof

Every maximal subgroup has order $|G|/p = p^{n-1}$, so $P_{[p^{n-1}]}$ wins by Lemma 1.

We will generalize Theorem 7 in the theorem below by determining the outcomes when $d(G) \ge 2$ in the case where q divides |G|. By Lemma 1, the orders of the maximal subgroups are key to proving the next result. Thus, we will first use Proposition 10 to determine the orders of the maximal subgroups, and then we will determine which of those orders can be the order of $\overline{M}$.

Theorem 12

Let G be a nontrivial finite nilpotent group. If q is a prime that divides |G|, then the winner of $\text{ DNG }_q(G)$ is

• 1. $P_j$ if $|G| \equiv jq \bmod {q^2}$ for some $j \in \{1,2,\ldots ,q-1\}$ and $d(G)\le j$

• 2. $P_q$ if $|G| \equiv jq \bmod {q^2}$ for some $j \in \{1,2,\ldots ,q-1\}$ and $d(G)> j$

• 3. $P_q$ if $|G| \equiv 0 \bmod {q^2}$.

Proof

If $d(G) \ge 1$ and $|G| \equiv 0 \bmod {q^2}$, then $|G|/p \equiv 0 \bmod {q}$ for all such p dividing |G|, including $p=q$. Therefore, $P_q$ wins in this case, regardless of strategy.

So suppose $|G| \equiv jq \bmod {q^2}$ for some $j \in \{1,\ldots ,q-1\}$. Then for every maximal subgroup M, $[M]=[|G|/p]=j$ if $p=q$ and $[M]=q$ otherwise. Thus, $P_j$ and $P_q$ are the only two players who can win, with $P_k$ preferring $P_j$ to win for $k \in \{1,\ldots ,j\}$ and $P_l$ preferring $P_q$ to win for $l \in \{j+1,j+2,\ldots ,q\}$.

We can write $G=Q \times H$ for some subgroup Q of order q and subgroup H such that q does not divide |H|. Note that Q is cyclic, so $d(G)=d(H)$ since $G = Q \times H$ and $\gcd (|Q|,|H|)=1$. If $d(H)=d(G) \le j$, then $P_1$ to $P_{d(H)}$ will select generators of H with their first moves, with H a maximal subgroup of order |G| / q. Thus, $P_j$ will win.

If $d(H)=d(G) > j$, then suppose that $P_1$ to $P_j$ select elements $x_1,\ldots ,x_j \in G$ with $X:=\langle x_1,\ldots ,x_j \rangle$ with their first moves. If q divides |X|, then $P_q$ will win by Lemma 1. If q does not divide |X|, then X is a subgroup of H. But $d(H) > j$, so X is a proper subgroup of H. Since $P_{j+1}$ prefers $P_q$ to win, $P_{j+1}$ can select an element $t \in G$ of order q, yielding a proper subgroup isomorphic to $Q \times X < Q \times H = G$. Thus, q divides $|\langle x_1,\ldots ,x_j,t \rangle |$ and $P_q$ wins by Lemma 2.

Note that Theorem 12 agrees with Theorem 7 for cyclic groups.

Corollary 13

Let G be a nontrivial finite nilpotent group, and let H be the direct product of all Sylow $r_i$-groups of G such that $r_i \equiv 1 \bmod {3}$ and K be the direct product of Sylow $t_j$-groups of G such that $t_j \equiv 2 \bmod {3}$. Then the following is true for $\text{ DNG }_3(G)$.

• 1. $P_1$ has a winning strategy in the following cases.

  • (a) $|G| \equiv 1 \bmod {3}$ and $2d(H) \ge d(K)+1$

  • (b) $|G| \equiv 2 \bmod {3}$ and $2d(K) \ge d(H)+1$

  • (c) $|G| \equiv 3 \bmod {9}$ and $d(G)=1$

• 2. $P_2$ has a winning strategy in the following cases.

  • (a) $|G| \equiv 1 \bmod {3}$ and $2d(H) < d(K)+1$

  • (b) $|G| \equiv 2 \bmod {3}$ and $2d(K) < d(H)+1$

  • (c) $|G| \equiv 6 \bmod {9}$ and $d(G)\le 2$

• 3. $P_3$ has a winning strategy in the following cases.

  • (a) $|G| \equiv 0 \bmod {9}$

  • (b) $|G| \equiv 3 \bmod {9}$ and $d(G) \ge 2$

  • (c) $|G| \equiv 6 \bmod {9}$ and $d(G) \ge 3$

Proof

The results follow from Theorem 12 if 3 divides |G|, so we may assume that 3 does not divide |G|. Thus, we may write $G = H \times K$, and $P_3$ cannot win because no maximal subgroup has order divisible by 3. Then $P_3$ will help $P_1$ and, after the first two elements are selected, $P_1$ effectively selects two elements for every element $P_2$ selects.

Suppose first that $|G| \equiv 1\bmod {3}$. Note that since |H| and |K| are coprime, the maximal subgroups of G have the form $L \times K$ and $H \times J$ for maximal subgroups L of H and J of K by Thévenaz (1997, Lemma 1.3). Since $P_1$ wants $[\overline{M}]=1$, $P_1$ wants $|\overline{M}|=|G|/r_i$ for some i. In other words, $P_1$ wants $\{e\} \times K \le \overline{M}$. Therefore, $P_1$ and $P_3$ should select elements of the form $(e,k) \in H \times K$ where e is the identity of H and k is an element of a generating set of minimal size of K. Similarly, $P_2$ will select elements of the form $(h,e')$ where $e'$ is the identity of K and h is an element of a generating set of H of minimal size. Because $P_1$ and $P_3$ each get to choose a generator of K for every generator of H that $P_2$ chooses, we see after some simple algebra that $P_1$ (with $P_3$’s help) will be able to generate K before $P_2$ can generate H if and only if $2d(H) \ge d(K)+1$. A similar argument shows that $P_1$ wins when $|G| \equiv 2 \bmod {3}$ if and only if $2d(K) \ge d(H)+1$.

5 Dihedral and dicyclic groups

Let $D_{2n}$ denote a dihedral group of order 2n and $Q_{4n}$ denote the dicyclic group of order 4n, which has the presentation $\langle a,x \mid a^{2n}=1,x^2=a^n,x^{-1}ax=a^{-1}\rangle$ where 1 is the identity of $Q_{4n}$. Note that $Q_{8}$ is isomorphic to the quaternion group. Additionally, $D_2 \cong \mathbb {Z}_2 \times \mathbb {Z}_2 \cong Q_4$ if $n=1$, and $D_2$ is not usually considered a dihedral group and $Q_4$ is not usually considered a dicyclic group. However, the results below hold for $n=1$, so we will allow for $n=1$.

Notice that both $D_{2n}$ and $Q_{4n}$ have a cyclic subgroup C of index 2 such that every element not in C acts on C by inversion. We start with a statement about the maximal subgroups of certain metacyclic groups that are similar to $D_{2n}$ and $Q_{4n}$.

Proposition 14

Let G be finite group with a cyclic subgroup C of index 2 such that every $g \in G {\setminus } C$ acts on C via inversion. If M is a maximal subgroup of G, then either $|M|=|G|/2$ or $|M|=|G|/p$ for some prime p dividing |C|. Moreover, there is a maximal subgroup L of each such order in G, where $d(L)=1$ if $L=C$ and $d(L)=2$ otherwise.

Proof

Let M be a maximal subgroup of G. If $M \le C$, then $M=C$ with $|G:M|=2$. Then C is a maximal subgroup of order |G| / 2 with $d(C)=1$.

So assume that M is not contained in C, let $H=M \cap C$, and let t be any element of order 2 in $M {\setminus } C$. The element t acts by inversion on all elements of C, so t normalizes H and hence $H\langle t \rangle$ is a subgroup of M. We will show that $M=H\langle t \rangle$. It is clear that $H\langle t \rangle \le M$, so it suffices to show that M is contained in $H\langle t \rangle$. Let $x \in M$. If $x \in M \cap C = H$, then $x \in H\langle t \rangle$. So assume that x is not in C. Since $G=C\langle t \rangle$, we see that $x=ct$ for some $c \in C$. Then $c=(ct)t=xt \in M$, so $c \in M \cap C = H$ and $x=ct \in H\langle t \rangle$. Therefore, $M \le H\langle t \rangle$, and we conclude that $M=H\langle t \rangle$.

If H is not maximal in C, then there is proper subgroup K of C properly containing H. Because t acts by inversion on all of C, we have $M=H\langle t \rangle< K\langle t \rangle < C\langle t \rangle = G$, which contradicts the maximality of M. Therefore, H is maximal in C and has order |C| / p for some prime divisor p of |C|. Then

$$\begin{aligned} |M|=|H\langle t \rangle | = |H||\langle t \rangle |/|H \cap \langle t \rangle | = |H||\langle t \rangle | = (|C|/p)(2)=|G|/p. \end{aligned}$$

Finally, let p be an odd prime divisor of |G|. Then p divides |C|. Because C is cyclic, it has a maximal subgroup D of order |C| / p. Then $L:=D\langle t\rangle$ is a maximal subgroup of G of order |G| / p for any $t \in G {\setminus } C$. Since $L=\langle D, t\rangle$ and D is cyclic, $d(L)=2$.

We can now again determine the outcomes of the avoidance game on dihedral and dicyclic groups by considering the orders of maximal subgroups.

Theorem 15

Let G be a dihedral group or dicyclic group and define

$$\begin{aligned} W= & {} \{[|G|/p] : p \text{ divides } |G|, p \text{ odd }\}\\ X= & {} \{[|G|/p] : p \text{ divides } |G|, p \text{ odd }, [|G|/p] \not =1\} \end{aligned}$$

We let $m=\min W$ if $W \not =\emptyset$ and $m'=\min X$ if $X \not =\emptyset$. Then for $\text{ DNG }_q(G)$,

• 1. $P_{[|G|/2]}$ has a winning strategy if one of the following is true.

  • (a) $|G|=2^k$ for some k.

  • (b) $[|G|/2] \le m$

  • (c) $1= m < [|G|/2]$, $X=\emptyset$, and |G| / 2 is even

  • (d) $1= m < [|G|/2] \le m'$, $X\not =\emptyset$

• 2. $P_{m}$ has a winning strategy if one of the following is true.

  • (a) $1< m < [|G|/2]$

  • (b) $m=1$, $X=\emptyset$, and |G| / 2 is odd

• 3. $P_{m'}$ has a winning strategy if $1= m< m' < [|G|/2]$ and $X \not =\emptyset$.

Proof

If $|G|=2^k$ for some k, then every maximal subgroup of G has order $2^{k-1}$ by Proposition 14. Thus, $P_{[|G|/2]}$ will win. So suppose that |G| is not a power of 2. Then an odd prime divides |G|, so W is nonempty and m is defined.

Let C denote the cyclic subgroup of order |G| / 2. By Proposition 14, $P_{k}$ will win for some $k=[|G|/p]$ for a prime p that divides |G|, and $P_1$ will prefer that k is [|G| / 2] if $|G|/2 \le m$ and m otherwise. Because C has order |G| / 2, $P_1$ will select a generator of C on the first move if $[|G|/2] \le m$, so $P_{[|G|/2]}$ will win in this case.

So suppose that $m < [|G|/2]$. This means that $P_1$ wants $P_m$ to win, and thus will help generate a maximal subgroup of order |G| / p for some odd p dividing G. Let p be an odd prime dividing |G|. Then there is a maximal subgroup $M_p$ of order |G| / p with $d(M_p)=2$ by Proposition 14. Since $d(M_p)=2$, $P_1$ cannot unilaterally determine $\overline{M}$ unless $\overline{M}=C$, which $P_1$ does not want.

If $1< m < [|G|/2]$, then $P_2$ also prefers $P_m$ to win. Since all maximal subgroups are 2-generated by Proposition 14, $P_1$, and $P_2$ can select elements that generate a maximal subgroup of order |G| / p such that $[|G|/p]=m$. Thus, $P_m$ wins.

If $1 = m < [|G|/2]$, however, then $P_2$ does not prefer $P_m=P_1$ to win. If $X=\emptyset$, then $[|G|/p]=1$ for all odd primes p that divide |G| and $P_2$ prefers that $P_{[|G|/2]}$ wins. If $|C|=|G|/2$ is odd, then $P_1$ can pick any $t \in G {\setminus } C$, which implies $\overline{M}$ will have order |G| / p for some odd prime p dividing |C|. Then $[\overline{M}]=1$ and $P_1$ wins.

If $X=\emptyset$ and n is even, then $\overline{M}$ will have order |G| / 2 or |G| / p for some p dividing |C| with $[|G|/p]=1$ if p is odd. In this case, $P_2$ prefers $|\overline{M}|=|G|/2$. If $P_1$ picks an element of C, then $P_2$ selects a generator of C to ensure that $\overline{M}=C$. If $P_1$ picks a $t \in G {\setminus } C$, then $P_2$ selects an element $c \in C$ such that $|\langle c \rangle | = |C|/2$. Then $|\langle t,c\rangle | = |G|/2$. In either case, $P_{[|G|/2]}$ wins.

Suppose now that $1 = m < [|G|/2]$ and $X \not = \emptyset$. In this case, $P_1$ could potentially win, but $P_2$ still prefers that anyone but $P_{1}$ wins. Because $X \not =\emptyset$, there is a $y \in C$ such that $|C:\langle y \rangle |=p_{m'}$ for some prime $p_{m'}$ with $[|G|/p_{m'}]=m'$.

• 1. If $P_1$ selects some $x \in C$ on the first move, then because C is cyclic, $P_2$ can select any $y \in C$ such that $\langle x, y \rangle =C$. Then $\overline{M}=C$ and $P_{[C]}=P_{[|G|/2]}$ wins.

• 2. If $P_1$ selects any $t \in G {\setminus } C$ on the first move, then $P_2$ selects y so that $P_{m'}$ wins.

Therefore, $P_1$ cannot win. If $[|G|/2] \le m'$, $P_1$’s second preference is for $P_{[|G|/2]}$ to win. Then $P_1$ can select a generator of C on the first move so that $P_{[|G|/2]}$ wins. If $m' < |G|/2$, then $P_1$ and $P_2$ both want $P_{m'}$ to win, and will select t and y as above.

Corollary 16

Let $D_{2n}$ be a dihedral group. Then for $\text{ DNG }_3(D_{2n})$,

• 1. $P_1$ has a winning strategy if and only if $n \equiv 1 \bmod {3}$.

• 2. $P_2$ has a winning strategy if and only if $n \equiv 2 \bmod {3}$ or $n \equiv 3 \bmod {9}$.

• 3. $P_3$ has a winning strategy if and only if $n \equiv 0 \bmod {9}$ or $n \equiv 6 \bmod {9}$.

Proof

We will use the notation from Theorem 15. If $n \equiv 1 \bmod {3}$, then $[|G|/2]=[n]=1 \le m$, so $P_1$ wins. If $n \equiv 0 \bmod {9}$, then $[|G|/2]=3=m$, so $P_3$ wins. If $n \equiv 3 \bmod {9}$, then $[|G|/2]=3$ and $[|G|/p]=[2n/p]$ is 2 if $p=3$ and 3 otherwise, so $m=2$. Thus, $P_2$ wins if $n \equiv 3 \bmod {9}$ since $1< 2 = m < 3 = [|G|/2]$.

If $n \equiv 6 \bmod {9}$, then $[|G|/3]=1$ and $[|G|/p]=3$ if $p\not =3$. This implies that $m=1$. Since $n \equiv 6 \bmod {9}$, either $n=2^k\cdot 3$ for some $k \ge 1$ or there is an odd prime $p \not =3$ that divides n. If $n=2^k\cdot 3$, then $X=\emptyset$ and $|G|/2=2^k\cdot 3$ is even, so $P_{[|G|/2]}=P_3$ wins by Item 1c of Theorem 15. If such an odd p exists, then $[|G|/p]=3\not =1$ and $X \not =\emptyset$. This time, $P_3$ wins by Item 1d of Theorem 15. In either case, $P_3$ wins.

Now suppose that $n \equiv 2 \bmod {3}$, in which case n must have a prime divisor u such that $u \equiv 2 \bmod {3}$. Additionally, 3 will not divide $|\overline{M}|$, so $P_3$ cannot win. However, we see that there is no case in Theorem 15 where $P_1$ wins since $[|G|/2]=2$ is not odd and $1 \not \in \{[|G|/2],m'\}$. Because $P_3$ cannot win, we conclude that $P_2$ wins.

The proof of the next corollary exactly mirrors that of Corollary 16, and is thus omitted. The only difference worth noting is that the cyclic subgroup of index 2 in a dicyclic group has order 2n rather than n.

Corollary 17

Let $Q_{4n}$ be a dicyclic group. Then for $\text{ DNG }_3(Q_{4n})$,

• 1. $P_1$ has a winning strategy if and only if $2n \equiv 1 \bmod {3}$.

• 2. $P_2$ has a winning strategy if and only if $2n \equiv 2 \bmod {3}$ or $2n \equiv 3 \bmod {9}$.

• 3. $P_3$ has a winning strategy if and only if $2n \equiv 0 \bmod {9}$ or $2n \equiv 6 \bmod {9}$.

6 Further questions

We close with some open questions.

• 1. What are the strategies and outcomes for groups other than cyclic, dihedral, and nilpotent groups? Perhaps supersolvable or simple groups could be classified—supersolvable groups are a next logical generalization of nilpotent groups, and a lot is known about the maximal subgroups of finite simple groups.

• 2. Can we generalize these results for the analogous game involving n players when n is not prime? In this case, Lemma 2 may not apply because Cauchy’s Theorem does not guarantee an element of order n.

• 3. What are the winning strategies in the analogous achievement game where the player who generates the group wins, rather than loses?

• 4. Can we extend the result in Proposition 6 by determining exactly who wins if $\mathcal {M}_G^q$ j-covers G? This has been done in Benesh et al. (2016b) for $\text{ DNG }_2(G)$, as stated in Corollary 5.