The non-commuting, non-generating graph of a finite simple group

ABSTRACT

Let G be a group such that $G / Z (G)$ is finite and simple. The non-commuting, non-generating graph $Ξ (G)$ of G has vertex set $G ∖ Z (G)$ ⁠, with edges corresponding to pairs of elements that do not commute and do not generate G. Complementing our previous investigation of this graph for non-simple groups, we show that $Ξ (G)$ is connected with diameter at most 5, with smaller upper bounds for certain families of groups. Using these bounds, we then prove that when G is simple, the diameter of the complement of the generating graph of G has a tight upper bound of 4, with the exception of at most one group with a graph of diameter 5.

Issue Section:

Article

1. INTRODUCTION

The generating graph of a group G has been investigated by many authors (for example, [5, 6, 13]) and encodes information about the 2-generation properties of G: its vertex set is $G ∖ {1}$ and its edges are the generating pairs for G. The complement of this graph has also been studied (for example, in [38]), and for G non-abelian, its edge set necessarily includes all pairs of commuting elements. The remaining (and more interesting) non-generating pairs are described by the non-commuting, non-generating graph $Ξ (G)$ of G, with vertex set $G ∖ Z (G)$ and ${x, y}$ an edge if and only if $[x, y] \neq 1$ and $⟨ x, y ⟩ \neq G$ ⁠.

Since its introduction in [10], the study of the graph $Ξ (G)$ has been motivated by the importance of the 2-generation properties of groups throughout (abstract and computational) group theory and its applications, and by Cameron’s [9, Section 2.6] hierarchy of graphs. This is a sequence of graphs defined on G (for convenience, we will take the vertex set of each to be $G ∖ {1}$ ⁠) such that, as long as G is non-abelian, each is a spanning subgraph of the next graph in the sequence. The final three of these graphs are the commuting graph (whose edges are the commuting pairs of elements of G), the non-generating graph (that is, the complement of the generating graph) and the complete graph. The well-studied generating graph is the difference between the final two graphs. It is therefore natural to investigate the next difference, between the non-generating graph and the commuting graph, with all vertices corresponding to central elements deleted (these would otherwise necessarily be isolated). This difference is precisely $Ξ (G)$ ⁠.

It was proved in [10] that if G is nilpotent (or more generally, if all maximal subgroups of G are normal) and $Ξ (G)$ has an edge, then either the subgraph $Ξ^{+} (G)$ induced by the non-isolated vertices of $Ξ (G)$ is connected with diameter 2 or $Ξ (G)$ itself is connected with diameter 3. In our companion paper [22], we extend these results to the general case where $G / Z (G)$ is not simple. The only additional possibilities here are that G is infinite and $Ξ^{+} (G)$ has diameter 3 or 4, or that $Ξ (G)$ is the union of two connected components of diameter 2 (we provide in that paper a detailed structural description of the finite groups G satisfying this case).

In this paper, we address the case where $G / Z (G)$ is finite and (non-abelian) simple. Our main theorem assumes that G itself is simple. Here, $diam (Ξ (G))$ denotes the diameter of $Ξ (G)$ ⁠, which is always at least 2, since no vertex is adjacent to any of its powers. Compared to Theorem 6.1 from the thesis [21] on which this paper is based, our theorem takes into account new information on the maximal subgroups of the monster group $M$ ⁠; see Remark 2.7.

Theorem 1.1

Let G be a non-abelian finite simple group.

$Ξ (G)$ is connected with diameter at most 5.
If $G = M$ ⁠, then $diam (Ξ (G)) \in {4, 5}$ ⁠. If instead G is any other sporadic simple group or the Tits group, then $diam (Ξ (G)) ⩽ 4$ ⁠.
For certain simple groups G, Table 1 lists exact values or upper bounds for $diam (Ξ (G))$ ⁠.

Table 1.

Open in new tab

Exact values or upper bounds for $diam (Ξ (G))$ ⁠, for certain simple groups G

G	Conditions	$diam (Ξ (G))$
$M_{11}, M_{12}, M_{22}, J_{2}$		2
$PSL (2, q)$	q even or $q ⩽ 9$	2
$M_{23}, J_{1}$		3
$PSL (2, q)$	q odd and $q ⩾ 11$	3
$B, PSU (7, 2)$		4
A_n	n even	$⩽ 3$
A_n	n odd	$⩽ 4$
$PSL (n, q), Sz (q)$		$⩽ 4$
$G_{2} (q),^{2} G_{2} (q),^{3} D_{4} (q), F_{4} (q), E_{8} (q)$	q odd	$⩽ 4$

Table 1.

Open in new tab

Exact values or upper bounds for $diam (Ξ (G))$ ⁠, for certain simple groups G

G	Conditions	$diam (Ξ (G))$
$M_{11}, M_{12}, M_{22}, J_{2}$		2
$PSL (2, q)$	q even or $q ⩽ 9$	2
$M_{23}, J_{1}$		3
$PSL (2, q)$	q odd and $q ⩾ 11$	3
$B, PSU (7, 2)$		4
A_n	n even	$⩽ 3$
A_n	n odd	$⩽ 4$
$PSL (n, q), Sz (q)$		$⩽ 4$
$G_{2} (q),^{2} G_{2} (q),^{3} D_{4} (q), F_{4} (q), E_{8} (q)$	q odd	$⩽ 4$

Remark 1.2

Table 1 shows that there exist non-abelian finite simple groups G with $diam (Ξ (G))$ equal to 2, 3 or 4. We note that the baby monster group $B$ ⁠, the monster group $M$ and $PSU (7, 2)$ are the only known simple groups G for which $diam (Ξ (G)) > 3$ ⁠. Indeed, we do not know if infinitely many such groups exist, nor if $diam (Ξ (G)) = 5$ is possible.

At the end of each of Sections 3.1, 3.3, 5.1 and 5.2, we provide further examples of diameters achieved by various simple groups, computed using Magma [3] (see Section 2.1 for a discussion of our computational methods). Notably, none of our examples meet the upper bounds in rows 6–9 of Table 1.

Continuing the comparison between $Ξ (G)$ and the generating graph of G from [10, 22], we note that in the non-abelian finite simple case, the diameter of the former graph may be larger than that of the latter, which is equal to 2 by [5, Theorem 1.2].

Remark 1.3

It is easy to determine the connectedness and diameter of the non-commuting, non-generating graphs of certain infinite simple groups G. For instance, if G is a Tarski monster, then each nontrivial proper subgroup of G has a fixed prime order, and so each vertex of $Ξ (G)$ is isolated. Additionally, it is a straightforward consequence of [1, Proposition 2.1] that $diam (Ξ (G)) = 2$ whenever G is not 2-generated. However, it is an open problem to investigate the connectedness and diameter of $Ξ (G)$ when the infinite simple group G is 2-generated and $Ξ (G)$ has an edge.

Remark 1.4

Our proof of Theorem 1.1 involves Proposition 3.10, which corrects [20, Theorem 1.1] on the intersection graph (defined in Section 2.1), in the case of the monster group. Additionally, our proof uses Theorem 4.5, on subspace stabilizers in simple unitary groups. In [21, Ch. 3], we prove more general versions of that theorem to obtain lower bounds for the base sizes of primitive subspace actions of almost simple classical groups.

We also note that our proof of Theorem 1.1(i) relies on the classification of finite simple groups. In Section 2.2, we prove the following special case that does not depend on the classification.

Proposition 1.5

Let G be a non-abelian finite simple group, and suppose that every maximal subgroup of G has even order. Then $Ξ (G)$ is connected with diameter at most 5.

In fact, it follows from the classification (see Theorem 2.6 and Remark 2.7) that in addition to a few sporadic groups, the finite simple groups containing maximal subgroups of odd order belong to only three infinite families. Thus the above proposition serves as a useful reduction for the proof of Theorem 1.1(i).

Now, if $G / Z (G)$ is simple, then $Z (G) x$ is a vertex of $Ξ (G / Z (G))$ whenever $x \in G ∖ Z (G)$ ⁠. Thus [22, Lemma 2.9(ii)] yields the following corollary of Theorem 1.1(i).

Corollary 1.6

Let G be a group such that $G / Z (G)$ is finite and simple. Then $Ξ (G)$ is connected, with $diam (Ξ (G)) ⩽ diam (Ξ (G / Z (G))) ⩽ 5$ ⁠.

If instead $G / Z (G)$ is finite and almost simple but not simple, then we observe from [22, Theorems 1.2–1.3 and Lemma 6.5] that $Ξ (G)$ is connected with diameter 2 or 3. Magma computations show that $diam (Ξ (S_{5})) = 2$ and $diam (Ξ (S_{6})) = 3$ ⁠, and so both possibilities occur.

Finally, as a consequence of Theorem 1.1, we will prove the following analogue of that theorem for the non-generating graph $\overset{―}{Γ} (G)$ of a non-abelian finite simple group G. Recall that this graph is the complement of the generating graph of G. Hence its vertex set is $G ∖ {1}$ ⁠, and vertices x and y are adjacent if and only if $⟨ x, y ⟩ \neq G$ ⁠. Note that $Ξ (G)$ is a spanning subgraph of $\overset{―}{Γ} (G)$ (since $Z (G) = 1$ ⁠). As above, we write $B$ to denote the baby monster group and $M$ to denote the monster group. Similar to Theorem 1.1, we incorporate new information on the maximal subgroups of $M$ (compared to [21, Theorem 6.5.4]) and its intersection graph.

Theorem 1.7

Let G be a non-abelian finite simple group. The non-generating graph $\overset{―}{Γ} (G)$ is connected with diameter 4 or 5 if $G = M$ ⁠, at most 4 if $G ≇ M$ and at most 3 if every maximal subgroup of G has even order. Furthermore, if $G \in {B, PSU (7, 2)}$ ⁠, then $diam (\overset{―}{Γ} (G)) = 4$ ⁠.

An earlier version of this theorem was communicated by this paper’s author to Peter Cameron, and appears as a remark after Proposition 12.3 in his paper [9]. That version of the theorem is a key component of the proof of [38, Theorem 1] (see the proof of [38, Proposition 10]), which investigates the connectedness and diameter of $\overset{―}{Γ} (G)$ for a finite group G. This graph is closely related to the soluble graph of G, recently studied in [8]; see Remark 7 in that paper.

The remainder of this paper is structured as follows. The focus of Section 2 is on preliminary results and includes a comment on our computational methods and a proof of Proposition 1.5. In Section 3, we prove the alternating, sporadic and exceptional cases of Theorem 1.1. We consider matrices and stabilizers of subspaces in linear and unitary groups in Section 4 and then apply our results in Section 5 to prove Theorem 1.1 for those groups. Additionally, Section 5 concludes with a proof of Theorem 1.7.

2. PRELIMINARIES

Here, we present preliminary results on the non-commuting, non-generating graph of a group and on maximal subgroups of finite simple groups; in particular, we prove Proposition 1.5.

2.1. The non-commuting, non-generating graph

In this subsection, G is an arbitrary group, unless specified otherwise. Given vertices x and y of a graph Γ, we denote the distance in Γ between x and y by $d (x, y)$ ⁠, and if x and y are adjacent, then we write $x \sim y$ ⁠.

Lemma 2.1

([10, Corollary 6])

Let H be a proper non-abelian subgroup of G. Then the induced subgraph of $Ξ (G)$ corresponding to $H ∖ Z (H)$ is connected with diameter 2.

Proposition 2.2

Suppose that G is finite and insoluble. Then $Ξ (G)$ has no isolated vertices. Equivalently, each element of $G ∖ Z (G)$ is a non-central element of some maximal subgroup.

Proof.

It is clear from the definition of $Ξ (G)$ that a vertex $x \in Ξ (G)$ is isolated if and only if x lies in a unique maximal subgroup M of G and $x \in Z (M)$ ⁠. Since G is finite, it follows from [22, Proposition 2.6] that each isolated vertex of $Ξ (G)$ lies in an abelian maximal subgroup of G. However, each maximal subgroup of the finite insoluble group G is non-abelian [29].

Our next result highlights a connection between $Ξ (G)$ and the intersection graph $Δ_{G}$ of G. This latter graph, introduced in [14], has vertex set the proper nontrivial subgroups of G, with subgroups adjacent if and only if they intersect nontrivially.

Lemma 2.3

Let Γ be equal to $Ξ (G)$ or the non-generating graph of G. Additionally, suppose that $Z (G) = 1$ and that Γ is connected with a finite diameter. Then $diam (Γ) ⩾ diam (Δ_{G}) - 1$ ⁠.

Proof.

By Propositions 12.1 and 2.3 of [9] (which assume that G is finite, but whose proofs also hold for infinite groups), the diameters of $Δ_{G}$ and the non-generating graph of G differ by at most one. As Z(G) is trivial, $Ξ (G)$ is a spanning subgraph of the non-generating graph of G, and so the diameter of the former is at least the diameter of the latter.

We conclude this subsection with a brief description of our computational methods for determining $diam (Ξ (G))$ in Magma (for sufficiently small G). Let X be a set of representatives of generators for the non-central cyclic subgroups of G, and for each $x \in X$ ⁠, let Y_x be a set of representatives for the elements of X up to conjugacy in $C_{G} (x)$ ⁠. We also obtain a set Xʹ from X by identifying elements if they generate conjugate cyclic subgroups. It is easy to see that $Aut (Ξ (G))$ contains $Aut (G)$ and that $diam (Ξ (G)) = max {2, diam (Γ)}$ ⁠, where Γ is the graph obtained from $Ξ (G)$ by identifying vertices that generate identical cyclic subgroups. We obtain $diam (Ξ (G))$ by calculating the maximum distance in Γ between the elements in each pair (x, y) with $x \in X^{'}$ and $y \in Y_{x}$ ⁠, via computations involving centralizers of elements and intersections of maximal subgroups.

The Magma code used in these calculations is contained in the file diam_nc_ng in [19]; see also [21, Appendix A] for further information. When using this code to calculate $diam (Ξ (G))$ in this paper, we always represent G as a permutation group of minimal degree. We note that the time and memory requirements for running this code are negligible for sufficiently small groups (such as A₅), but are in the order of a few days and a few gigabytes for the largest groups investigated in this paper via these methods, namely, $G_{2} (3)$ ⁠, $PSL (4, 3)$ and $M_{23}$ ⁠.

2.2. Maximal subgroups of non-abelian finite simple groups

Assume throughout this subsection that G is non-abelian, finite and simple.

Lemma 2.4

Let L and M be maximal subgroups of G, with $| L |$ even.

If Z(L) contains an involution a, then $L ∖ Z (L)$ contains a G-conjugate of a.
L contains an involution that does not lie in $Z (L) \cup Z (M)$ ⁠.
Suppose that $| M |$ is even, and let a be an involution of $L ∖ M$ ⁠. Then $M ∖ Z (M)$ contains an involution b that does not commute with a.
Suppose that $L \cap M$ lies in Z(M) and contains an involution f. Additionally, let $u \in L ∖ M$ ⁠. Then $L ∖ M$ contains an involution fʹ with $[u, f^{'}] \neq 1$ ⁠.

Proof.

(i) Suppose that Z(L) contains an involution a, so that $C_{G} (a) = L$ ⁠. By [25, Corollary 1], there exists $g \in G$ such that $a \neq a^{g} \in C_{G} (a) = L$ ⁠. In fact, $g \notin L$ ⁠, as $a \in Z (L)$ ⁠. Thus $L \neq L^{g} = C_{G} (a^{g})$ ⁠, and so the involution a^g is non-central in L.

(ii) We will prove that L contains an involution $s \notin Z (L) \cup Z (M)$ ⁠. By (i), there exists an involution $y \in L ∖ Z (L)$ ⁠. If $y \notin Z (M)$ ⁠, then we can set s = y. If instead $y \in Z (M)$ (so that $L \neq M$ ⁠), then $C_{G} (y) = M$ ⁠. Additionally, since Z(L) and $L \cap M$ are proper subgroups of L, there exists $h \in L ∖ (Z (L) \cup M)$ ⁠, and y^h is a non-central involution of L. Moreover, $M \neq M^{h} = C_{G} (y^{h})$ ⁠. Therefore, $y^{h} \notin Z (M)$ ⁠, and so we can set $s = y^{h}$ ⁠.

(iii) Suppose first that $| Z (M) |$ is odd, let S be the set of involutions of M and let $Q_{M} ⊴ M$ be the subgroup generated by S. If the involution $a \in L ∖ M$ commutes with each element of S, then $a \in C_{G} (Q_{M})$ ⁠, and so $Q_{M} ⊴ ⟨ M, a ⟩ = G$ ⁠, contradicting the simplicity of G. Thus there exists $r \in S ∖ C_{G} (a)$ ⁠. As $S \cap Z (M) = 1$ ⁠, we can set b = r.

If instead Z(M) contains an involution z, then by applying (i) to M, we deduce that $M ∖ Z (M)$ contains an involution c. If $[a, c] \neq 1$ ⁠, then we can set b = c. Otherwise, as $a \notin M = C_{G} (z)$ ⁠, we see that $[a, z c] = [a, z]^{c} \neq 1$ ⁠. Thus we may set b to be the involution $z c \in M ∖ Z (M)$ ⁠.

(iv) Let s be the involution from (ii), so that $s \in L$ and $s \notin L \cap M ⩽ Z (M)$ ⁠. If $[u, s] \neq 1$ ⁠, then we can set $f^{'} = s$ ⁠. Assume therefore that $[u, s] = 1$ ⁠. Since $C_{G} (f) = M$ and similarly $C_{G} (f^{s}) = M^{s}$ $\neq M$ ⁠, we obtain $f^{s} \in L ∖ Z (M)$ ⁠, and hence $f^{s} \notin L \cap M$ ⁠. If $f^{s} \in C_{G} (u)$ ⁠, then $C_{L} (u)$ contains $⟨ s, f^{s} ⟩$ ⁠, which contains f. This contradicts $u \notin M = C_{G} (f)$ ⁠, and so we can set $f^{'} = f^{s}$ ⁠.

The following lemma is one of the main ingredients in the proof of Theorem 1.1.

Lemma 2.5

Let L and M be maximal subgroups of G of even order, and let $x \in L ∖ Z (L)$ and $y \in M ∖ Z (M)$ ⁠. Then $d (x, y) ⩽ 5$ ⁠, as vertices of $Ξ (G)$ ⁠. Moreover, if L contains an involution a such that $d (x, a) ⩽ 1$ ⁠, then $d (x, y) ⩽ 4$ ⁠.

Proof.

We will use Lemma 2.1 several times in this proof without further reference. First, we may assume that $L \neq M$ ⁠, as otherwise $d (x, y) ⩽ 2$ ⁠. Let $C$ be the set of involutions in $L ∖ Z (L)$ ⁠. Lemma 2.4(ii) shows that there exists $c \in C ∖ Z (M)$ ⁠. Notice that $d (x, c) ⩽ 2$ ⁠. If $c \in M ∖ Z (M)$ ⁠, then $d (c, y) ⩽ 2$ ⁠, and so $d (x, y) ⩽ d (x, c) + d (c, y) ⩽ 4$ ⁠. If instead $c \in G ∖ M$ ⁠, then Lemma 2.4(iii) yields an involution $b \in M ∖ Z (M)$ such that $[c, b] \neq 1$ ⁠. As $⟨ c, b ⟩$ is dihedral, $c \sim b$ ⁠. Since $d (b, y) ⩽ 2$ ⁠, we conclude in this case that $d (x, y) ⩽ 5$ ⁠, with $d (x, y) ⩽ 4$ if $d (x, c) ⩽ 1$ ⁠.

Now, let $A$ be the set of involutions $a \in C$ with $d (x, a) ⩽ 1$ ⁠. By the previous paragraph, it remains to consider the case where $C \subseteq (G ∖ M) \cup Z (M)$ and $\emptyset \neq A \subseteq Z (M)$ ⁠. Note that $c \in C ∖ M$ in this case.

Let $a \in A \subseteq Z (M)$ ⁠, so that $C_{G} (a) = M$ ⁠. Then $a \sim c$ ⁠, and since $c \notin A$ ⁠, it follows from the definition of $A$ that $a \neq x$ and $a \sim x$ ⁠. Thus $x \notin M$ ⁠. Lemma 2.4(iv) (with f = a and u = x) now shows that $L \cap M ⩽̸ Z (M)$ ⁠, as otherwise $L ∖ M$ would contain an involution in $A$ ⁠. Hence $L \cap M$ contains an element not centralizing M and the element a not centralizing x. As no group is the union of two proper subgroups, there exists $h \in L \cap M$ centralizing neither M nor x. Thus $d (h, y) ⩽ 2$ and $x \sim h$ ⁠, and therefore $d (x, y) ⩽ 3$ ⁠.

Proof of Proposition 1.5

For each $x \in Ξ (G)$ ⁠, Proposition 2.2 gives $x \in K ∖ Z (K)$ for some maximal subgroup K of G (of even order). Thus $diam (Ξ (G)) ⩽ 5$ by Lemma 2.5.

As the proofs of [25, Corollary 1] and Proposition 2.2 are independent of the classification of finite simple groups, so are the proofs of Lemmas 2.4 and 2.5 and Proposition 1.5.

To prove Theorem 1.1(i), it remains to consider the non-abelian finite simple groups that contain maximal subgroups of odd order.

Theorem 2.6

([35, Theorem 2])

Suppose that G is not isomorphic to the monster group. Then G has a maximal subgroup of odd order if and only if G is isomorphic to one of the following:

A_p, with p being a prime, $p \equiv 3 (\mod 4)$ and $p \notin {7, 11, 23}$ ⁠;
$PSL (n, q)$ ⁠, with n being a prime, $(n, q) \neq (3, 4)$ and $q \equiv 3 (\mod 4)$ if n = 2;
$PSU (n, q)$ ⁠, with n an odd prime and $(n, q) \notin {(3, 3), (3, 5), (5, 2)}$ ⁠; or
the Mathieu group $M_{23}$ ⁠, the Thompson group $Th$ or the baby monster group $B$ ⁠.

Remark 2.7

Let G be the monster group. By [35, Theorem 2], any maximal subgroup of G of odd order has shape 59:29 or 71:35. It was claimed in [31, 32] that maximal subgroups of G isomorphic to $PSL (2, 59)$ and $PSL (2, 71)$ were constructed computationally (using data that were not made publicly available). This suggested that no maximal subgroup of shape 59:29 or 71:35 exists. However, a brand new computational paper [17] shows (via publicly available code) that, up to conjugacy, G has unique maximal subgroups of shape 59:29 and $PSL (2, 71)$ ⁠, but no subgroup isomorphic to $PSL (2, 59)$ ⁠. Hence, up to conjugacy, 59:29 is the unique maximal subgroup of G of odd order.

3. ALTERNATING, SPORADIC AND EXCEPTIONAL SIMPLE GROUPS

In this section, we prove the alternating, sporadic and exceptional cases of Theorem 1.1. Note that we consider the Tits group $^{2} F_{4} (2)^{'}$ together with the sporadic groups.

3.1. Alternating groups

Let G be the alternating group A_n of degree $n ⩾ 5$ ⁠. We will prove the following result by considering the standard action of G on the set $Ω := {1, 2, \dots, n}$ ⁠.

Theorem 3.1

The graph $Ξ (G)$ of the alternating group G of degree $n ⩾ 5$ is connected with diameter at most 4 or at most 3 if n is even.

Recall that a derangement of G is an element with no fixed points.

Lemma 3.2

Let x be a derangement of G such that $⟨ x ⟩$ acts intransitively on Ω. In addition, let ${α_{1}, α_{2}}$ and ${β_{1}, β_{2}}$ be 2-subsets of distinct orbits of x on Ω. Finally, if x has exactly two orbits on Ω, then let $g := (α_{1}, α_{2}) (β_{1}, β_{2})$ ⁠, and otherwise, let $g := (α_{1}, α_{2}, β_{1})$ ⁠. Then $x \sim g$ ⁠.

Proof.

If $⟨ x ⟩$ has exactly two orbits on Ω, then at least one of these orbits has length at least three. Hence, in each case, $x^{g} \neq x$ ⁠, and so $[x, g] \neq 1$ ⁠. Additionally, $⟨ x, g ⟩$ acts intransitively on Ω and is therefore a proper subgroup of G. Thus $x \sim g$ ⁠.

Lemma 3.3

Let $x, y \in G ∖ {1}$ ⁠. Then $d (x, y) ⩽ 4$ ⁠. If $d (x, y) ⩾ 3$ ⁠, then at least one of x and y is a derangement, and if $d (x, y) = 4$ ⁠, then both are derangements.

Proof.

Let α and β be distinct points in Ω. The point stabilizer $G_{α} ≅ A_{n - 1}$ is a maximal subgroup of G. As $Z (G_{α}) = 1$ ⁠, it follows from Lemma 2.1 that $d (g, h) ⩽ 2$ for all $g, h \in G_{α} ∖ {1}$ ⁠. Additionally, $H := G_{α} \cap G_{β} ≅ A_{n - 2}$ is maximal in each of G_α and G_β. Let $g \in G_{α}$ and $k \in G_{β}$ ⁠, such that $g, k \notin H$ ⁠. Then $C_{H} (g) < H$ ⁠, as otherwise $⟨ H, g ⟩ = G_{α}$ would centralize g. Similarly, $C_{H} (k) < H$ ⁠. Hence some element of H centralizes neither g nor k, and it follows that $d (g, k) ⩽ 2$ ⁠.

To complete the proof, we will show that each derangement $x \in G$ is adjacent in $Ξ (G)$ to some non-derangement. This follows immediately from Lemma 3.2 if $⟨ x ⟩$ is intransitive on Ω. Assume therefore that x is an n-cycle $(α_{1}, \dots, α_{n})$ ⁠, with $α_{i} \in Ω$ for each i, and n is odd. It suffices to prove that there exists $t \in N_{G_{α_{1}}} (⟨ x ⟩)$ with $x^{t} \neq x$ ⁠; it will then follow that $⟨ x, t ⟩ ⩽ N_{G} (⟨ x ⟩) < G$ and $[x, t] \neq 1$ ⁠, so that $x \sim t$ ⁠. For each n-cycle $r \in ⟨ x ⟩$ with $r \neq x$ ⁠, there exists an element $s \in N_{(S_{n})_{α_{1}}} (⟨ x ⟩)$ such that $x^{s} = r$ ⁠. There are $ϕ (n) - 1 > 1$ of these n-cycles, where ϕ is Euler’s totient function. We deduce that there exist $s, s^{'} \in N_{(S_{n})_{α_{1}}} (⟨ x ⟩)$ such that $x^{s} = x^{- 1}$ and $x^{s^{'}} = x^{i}$ for some $i \in {2, \dots, n - 2}$ ⁠. Since $x^{s s^{'}} = x^{- i} \neq x$ ⁠, we can choose $t \in G \cap {s, s^{'}, s s^{'}} \neq \emptyset$ ⁠.

We will write $supp (g)$ to denote the support ${α \in Ω ∣ α^{g} \neq α}$ of an element $g \in G$ ⁠.

Lemma 3.4

Let x and y be derangements of G such that each of $⟨ x ⟩$ and $⟨ y ⟩$ acts intransitively on Ω. Then $d (x, y) ⩽ 3$ ⁠.

Proof.

Let ${α_{1}, α_{2}}$ and $B := {β_{1}, β_{2}}$ be two subsets of distinct orbits of $⟨ x ⟩$ on Ω, such that $| α_{1}^{⟨ x ⟩} | ⩾ | β_{1}^{⟨ x ⟩} |$ ⁠, and let ${γ_{1}, γ_{2}}$ and $D := {δ_{1}, δ_{2}}$ be 2-subsets of distinct orbits of $⟨ y ⟩$ on Ω. We may assume that $α_{1} = γ_{1}$ ⁠. If n = 5, then each of $⟨ x ⟩$ and $⟨ y ⟩$ has exactly two orbits on Ω.

Case (a): $⟨ x ⟩$ and $⟨ y ⟩$ each have exactly two orbits on Ω. We see from Lemma 3.2 that $x \sim a := (α_{1}, α_{2}) (β_{1}, β_{2})$ and $y \sim b := (α_{1}, γ_{2}) (δ_{1}, δ_{2})$ ⁠. In particular, if a = b, then $d (x, y) ⩽ 2$ ⁠.

Assume therefore that $a \neq b$ ⁠, and hence either $α_{2} \neq γ_{2}$ or $B \neq D$ ⁠. If $[a, b] = 1$ ⁠, then either $γ_{2} = α_{2}$ and $B \cap D = \emptyset$ ⁠; or ${γ_{2}} \cup D = {α_{2}} \cup B$ ⁠. As $| α_{1}^{⟨ x ⟩} | ⩾ 3$ ⁠, we can repeat the argument with α₂ replaced by an element of $α_{1}^{⟨ x ⟩} ∖ {α_{1}, α_{2}}$ to obtain $[a, b] \neq 1$ ⁠. Since $⟨ a, b ⟩$ is dihedral, $(x, a, b, y)$ is a path in $Ξ (G)$ and $d (x, y) ⩽ 3$ ⁠.

Case (b): $⟨ x ⟩$ and $⟨ y ⟩$ each have at least three orbits on Ω. By Lemma 3.2, $x \sim a :=$ $(α_{1}, α_{2}, β_{1})$ and $y \sim b := (α_{1}, γ_{2}, δ_{1})$ ⁠. Observe that $t := supp (a) \cup supp (b)$ $⩽ 5 < n$ ⁠, and so $⟨ a, b ⟩ < G$ ⁠. Hence if $[a, b] \neq 1$ ⁠, then $(x, a, b, y)$ is a path in $Ξ (G)$ ⁠, and so $d (x, y) ⩽ 3$ ⁠. If instead $[a, b] = 1$ ⁠, then t = 3 and $b \in {a, a^{- 1}}$ ⁠, hence $a \sim y$ and $d (x, y) ⩽ 2$ ⁠.

Case (c): Exactly one of $⟨ x ⟩$ and $⟨ y ⟩$ has exactly two orbits on Ω. We may assume that $⟨ x ⟩$ has exactly two orbits on Ω. Lemma 3.2 shows that $x \sim a := (α_{1}, α_{2}) (β_{1}, β_{2})$ and $y \sim b := (α_{1}, γ_{2}, δ_{1})$ ⁠. Observe that $[a, b] \neq 1$ and $⟨ a, b ⟩$ is intransitive. Hence $a \sim b$ and $d (x, y) ⩽ 3$ ⁠.

Proof of Theorem 3.1

Lemma 3.3 shows that $Ξ (G)$ is connected with diameter at most 4. Furthermore, if n is even, then each derangement of G generates a subgroup that acts intransitively on Ω. Hence Lemmas 3.3 and 3.4 yield $diam (Ξ (G)) ⩽ 3$ ⁠.

Magma calculations show that $diam (Ξ (A_{n})) = 2$ whenever $5 ⩽ n ⩽ 10$ ⁠. We do not know if there exists n > 10 such that $diam (Ξ (A_{n})) > 2$ ⁠.

3.2. Sporadic groups

Let G be a sporadic finite simple group, or the Tits group $^{2} F_{4} (2)^{'}$ ⁠. In this subsection, we implicitly use [12, 43] to determine information about maximal subgroups, conjugacy classes and centralizers in G. In particular, all maximal subgroups of the sporadic groups are listed in [43] (up to conjugacy), with the exceptions of the maximal subgroups of the monster group $M$ isomorphic to $PGL (2, 13)$ and $Aut (PSU (3, 4))$ constructed in [18] and the maximal subgroups isomorphic to 59:29 constructed in [17] (see the introductions of those last two papers for further details). Additionally, the subgroup $PSL (2, 59)$ listed in [43] is not in fact a subgroup of $M$ ⁠; see Remark 2.7.

Theorem 3.5

The graph $Ξ (G)$ of the sporadic group or Tits group G is connected with diameter 4 or 5 if $G = M$ and at most 4 otherwise. If $G \in {M_{11}, M_{12}, M_{22}, M_{23}, J_{1}, J_{2}, B}$ ⁠, then $diam (Ξ (G))$ is given in Table 1.

A few of the proofs in this subsection, where specified, involve straightforward computations in GAP [24] that utilize the Character Table Library [4], with runtimes of at most a few seconds. This library contains the necessary information regarding all maximal subgroups of G, except for certain maximal subgroups of the monster group.

Proposition 3.6

Each maximal subgroup of G has a centre of order at most 2.

Proof.

For each maximal subgroup M of $M$ not included in the GAP Character Table Library, no element of $M$ has a centralizer of order $| M |$ ⁠, hence $Z (M) = 1$ ⁠. For each other maximal subgroup of each G, we verify the result using GAP.

In light of Lemma 2.5, it will be useful to determine neighbours of involutions in $Ξ (G)$ ⁠.

Proposition 3.7

Let x be an element of G of order at least 3, and suppose that x lies in a maximal subgroup of G of even order. Then x is adjacent in $Ξ (G)$ to some involution of G.

Proof.

It suffices to show that there exists a maximal subgroup of G that contains both x and an involution that does not centralize x. Let M be a maximal subgroup of G of even order, with $x \in M$ ⁠. Since $| x | > 2$ ⁠, Proposition 3.6 shows that $x \notin Z (M)$ ⁠. Let T_M be the set of involutions of M. If $| T_{M} | > | C_{M} (x) |$ ⁠, or if the normal subgroup $⟨ T_{M} ⟩$ of M is equal to M, then x does not centralize every involution of M. Note that this second condition holds whenever M is simple.

Using GAP, we see that if x does not lie in any simple maximal subgroup, nor in any maximal subgroup M with $| T_{M} | > | C_{M} (x) |$ ⁠, then one of the following holds:

$G = J_{1}$ and $| x | \in {7, 19}$ ⁠;
$G = Ly$ and $| x | \in {37, 67}$ ⁠;
$G = {Co}_{1}$ and $| x | = 3$ ⁠;
$G = J_{4}$ and $| x | \in {29, 43}$ ⁠; or
$G = {Fi}_{24}^{'}$ and $| x | = 29$ ⁠.

Our computations here involve the fusion of M-conjugacy classes in G. As such, when $G = M$ ⁠, we consider only the set of maximal subgroups of $M$ for which this fusion is stored in GAP (this is a subset of the set returned by the NamesOfFusionSources function). Similarly, when $G = B$ ⁠, our computations exclude the maximal subgroups of shape $(2^{2} \times F_{4} (2)) : 2$ ⁠, for which this fusion is not stored.

Now, in case (iii), x is an element of the G-conjugacy class labelled $3 A$ in the atlas [12] and lies in a maximal subgroup $K ≅ (A_{5} \times J_{2}) : 2$ ⁠, which clearly satisfies $⟨ T_{K} ⟩ = K$ ⁠. In all other cases, $| x |$ is odd and $C_{G} (x) = ⟨ x ⟩$ ⁠, and hence x does not commute with any involution of M.

Lemma 3.8

Suppose that $G = B$ ⁠, and let R and M be maximal subgroups of G isomorphic to ${Fi}_{23}$ ⁠. Additionally, let $s \in R$ with $| s | = 23$ ⁠. Then there exists $f \in R \cap M$ such that $d (s, f) ⩽ 1$ ⁠.

Proof.

Let $S := ⟨ s ⟩$ ⁠. If $S ⩽ M$ ⁠, then we can set f = s. Otherwise, $S \cap M = 1$ ⁠, and since $| R | | M | > | G |$ ⁠, there exists $f \in (M \cap R) ∖ {1}$ ⁠. As $f \notin S = C_{R} (s)$ ⁠, we observe that $s \sim f$ ⁠.

Lemma 3.9

Suppose that $G = B$ ⁠, and let $s, y \in G ∖ {1}$ ⁠, with $| s | = 23$ ⁠. Then $d (s, y) ⩽ 3$ ⁠.

Proof.

The element s generates a Sylow 23-subgroup S of G and lies in maximal subgroups $R ≅ {Fi}_{23}$ and $T ≅ 2^{1 + 22} \cdot {Co}_{2}$ ⁠. Each maximal subgroup of G that contains s and is not G-conjugate to R or T has shape 47:23. Moreover, $C_{R} (s) = S$ and (using Proposition 3.6 and the atlas) $C_{G} (s) = C_{T} (s) = Z (T) \times S ≅ C_{2} \times S$ ⁠. In addition, Proposition 2.2 shows that $y \in L ∖ Z (L)$ for some maximal subgroup L of G. We will show that $d (s, y) ⩽ 3$ whenever L satisfies certain properties and that we may often choose L to satisfy those properties.

Suppose first that $Z (L) > 1$ and $| L | | T | > | G |$ ⁠, so that $L \cap T \neq 1$ ⁠. We may assume that $L \neq T$ ⁠, else $d (s, y) ⩽ 2$ by Lemma 2.1. If there exists a non-identity element $u$ that lies in $(L \cap T) \cap (Z (L) \cup Z (T))$ then $Z (L) \cup Z (T) \subseteq L \cap T$ (if $u \in Z (L)$ ⁠, say, then $u \notin Z (G)$ implies that $Z (T) ⩽ L \cap T$ ⁠, and then $Z (T) ∖ Z (G) \neq \emptyset$ yields $Z (L) ⩽ L \cap T$ ⁠). Note also that $Z (L) \cup Z (T)$ is a proper subset of $⟨ Z (L), Z (T) ⟩$ ⁠, since $Z (L) \cap Z (T) = 1$ ⁠. Thus regardless of whether such an element u exists, $L \cap T$ contains an element $c \notin Z (L) \cup Z (T)$ ⁠. Moreover, any such c satisfies $d (c, y) ⩽ 2$ by Lemma 2.1. In particular, if $S ⩽ L \cap T$ ⁠, then we can set c = s, and so $d (s, y) ⩽ 2$ ⁠. Assume therefore that $S ⩽̸ L \cap T$ ⁠. We claim that $s \sim c$ ⁠. Indeed, if $s ≁ c$ ⁠, then c centralizes s and hence lies in $(Z (T) \times S) ∖ (Z (T) \cup S)$ ⁠. Thus $c = z s^{i}$ for some $i \in {1, 2, \dots, 22}$ ⁠, where z is the unique involution of Z(T). This implies that $⟨ c^{2} ⟩ = ⟨ s^{2 i} ⟩ = S$ ⁠, and so $S ⩽ L \cap T$ ⁠, a contradiction. Therefore, $s \sim c$ and $d (s, y) ⩽ 3$ ⁠.

Next, suppose that $Z (L) = 1$ ⁠, $| L | | R | > | G |$ and $L ≇ R$ ⁠. Then $L \cap R \neq 1$ ⁠, while $S \cap L = 1$ (since no L satisfying the given assumptions has order divisible by $| S |$ ⁠). As $C_{R} (s) = S$ ⁠, each $b \in L \cap R$ is adjacent to s in $Ξ (G)$ ⁠. Moreover, $d (b, y) ⩽ 2$ by Lemma 2.1, and so again $d (s, y) ⩽ 3$ ⁠.

Assume now that $| y | \notin {25, 47, 55}$ ⁠. Using GAP, we see that there exists a maximal subgroup K of G containing y, such that either $Z (K) > 1$ and $| K | | T | > | G |$ ⁠; or $Z (K) = 1$ ⁠, $| K | | R | > | G |$ and $K ≇ R$ ⁠. Moreover, Proposition 3.6 and Lemma 2.4(i) show that $K ∖ Z (K)$ contains a G-conjugate of y. Hence we can choose L to be a G-conjugate of K, and $d (s, y) ⩽ 3$ by the previous two paragraphs. To complete the proof, we will consider the remaining elements y.

Case (a): $| y | = 47$ ⁠. Here, $C_{G} (y) = ⟨ y ⟩$ ⁠, and each maximal subgroup of G containing y has shape 47:23. As S is a Sylow subgroup of G, it follows that $y \sim s^{'}$ for some $s^{'} \neq 1$ in a G-conjugate Sʹ of S. To complete the proof in this case, we will show that $d (s, s^{'}) ⩽ 2$ ⁠.

The element sʹ lies in a G-conjugate M of R. If $⟨ s ⟩ = ⟨ s^{'} ⟩$ ⁠, then it is clear that $d (s, s^{'}) = 2$ ⁠. Otherwise, $[s, s^{'}] \neq 1$ ⁠, and so if s or sʹ lies in $R \cap M$ ⁠, then $d (s, s^{'}) = 1$ ⁠. Suppose finally that $s, s^{'} \notin R \cap M$ ⁠. We deduce from Lemma 3.8 that $d (s, f) = 1 = d (s^{'}, f^{'})$ for some $f, f^{'} \in R \cap M$ ⁠. Hence there exists $t \in R \cap M$ centralizing neither s nor sʹ, and $(s, t, s^{'})$ is a path in $Ξ (G)$ ⁠.

Case (b): $| y | \in {25, 55}$ ⁠. There is a unique G-conjugacy class of elements of order $| y |$ ⁠, and so we may choose $L ≅ HN : 2$ if $| y | = 25$ or $L ≅ (5 : 4) \times (HS : 2)$ if $| y | = 55$ ⁠. In either case, no involution of G has a centralizer of order $| L |$ ⁠, and so Proposition 3.6 yields $Z (L) = 1$ ⁠.

First suppose that there exists $g \in (L \cap R) ∖ {1}$ ⁠. Then $g \notin S \cup Z (L) \cup Z (R)$ ⁠, as $| S |$ does not divide $| L |$ and $Z (L) = Z (R) = 1$ ⁠. Hence Lemma 2.1 yields $d (s, g), d (g, y) ⩽ 2$ ⁠. Additionally, $C_{G} (y) = ⟨ y ⟩$ ⁠, and so $C_{G} (y) \cap C_{G} (s) = 1$ ⁠. Thus either $s \sim g$ or $d (g, y) ⩽ 1$ ⁠, and $d (s, y) ⩽ 3$ ⁠.

Suppose finally that $L \cap R = 1$ ⁠. Each of G and R has a unique conjugacy class of elements of order 35, and L also contains elements of order 35. Hence there exists a G-conjugate M of R such that $L \cap M$ contains an element m of order 35, and $m \sim y$ since $C_{G} (y) = ⟨ y ⟩$ ⁠. Additionally, Lemma 3.8 shows that $d (s, f) ⩽ 1$ for some $f \in R \cap M$ ⁠. Note that $f \in M ∖ ⟨ m ⟩ = M ∖ C_{M} (m)$ ⁠, since $m \in L$ and $L \cap R = 1$ ⁠. Thus $f \sim m$ and $d (s, y) ⩽ 3$ ⁠.

Recall that the vertices of the intersection graph $Δ_{G}$ of G are the proper nontrivial subgroups of G, and the graph’s edges are the pairs of subgroups that intersect nontrivially. The result [20, Theorem 1.1] on the diameter of $Δ_{G}$ (for all non-abelian finite simple groups G) does not take into account the new information about $M$ mentioned in Remark 2.7. We now correct that theorem in the case $G = M$ ⁠; this will be useful in the proofs of Theorems 3.5 and 1.7.

Proposition 3.10

Suppose that $G = M$ ⁠. Then the intersection graph $Δ_{G}$ of G is connected with diameter 5 or 6.

Proof.

Let M₁ and M₂ be maximal subgroups of G, with $| M_{1} |$ being odd. By elementary arguments from the proof of [20, Theorem 1.1], it suffices to bound $d (S_{1}, S_{2})$ ⁠, where S₁ and S₂ are proper nontrivial subgroups of M₁ and M₂, respectively, such that S₁ lies in no maximal subgroup of even order. By Remark 2.7, M₁ has shape $59 : 29$ ⁠. Let S and H be subgroups of M₁ of order 59 and 29, respectively, so that H is a Sylow subgroup of G.

We observe from [12] that $| N_{G} (H) | = 2436$ ⁠. Arguing almost exactly as in the $B$ case of the proof of [20, Theorem 1.1], with the aid of computations involving the GAP Character Table Library, we determine that M₁ is the unique maximal subgroup of G containing S; that the maximal subgroups of G containing H are precisely 84 conjugates of M₁, three conjugates of $PGL (2, 29)$ ⁠, and one conjugate of $3. {Fi}_{24}$ ⁠; and that $d (S, S^{g}) ⩾ 5$ for some $g \in G$ ⁠. In particular, we may assume that $S_{1} = S$ ⁠.

Now, let R be a maximal subgroup of even order containing H. If S₂ is not conjugate to S, then M₂ can be chosen to have even order. Observe that the subgroup D generated by an involution of R and an involution of M₂ is dihedral. Hence $S_{1} \sim M_{1} \sim R \sim D \sim M_{2} \sim S_{2}$ ⁠, and we obtain $d (S_{1}, S_{2}) ⩽ 5$ ⁠. If instead $S_{2} = S^{x}$ for some $x \in G$ ⁠, then we similarly deduce that $S_{1} \sim M_{1} \sim R \sim \hat{D} \sim R^{x} \sim M_{1}^{x} \sim S_{2}$ for some dihedral group $\hat{D}$ ⁠, and thus $d (S_{1}, S_{2}) ⩽ 6$ ⁠. Therefore, $diam (Δ_{G}) \in {5, 6}$ ⁠.

Remark 3.11

Let G, S and $M_{1} ≅$ 59:29 be as in the proof of Proposition 3.10, and let F be a maximal subgroup of G of shape $3. {Fi}_{24}$ ⁠. It follows from the proof of Proposition 3.10 that $diam (Δ_{G}) = 6$ if and only if there exists $x \in G$ such that $d (S, S^{x}) = 6$ ⁠. Since M₁ is the unique neighbour of S₁ in $Δ_{G}$ ⁠, this occurs if and only if $d (M_{1}, M_{1}^{x}) = 4$ ⁠.

One possible obstruction to this occurring is the existence of elements $w, y \in G$ such that $M_{1} \sim F^{w} \sim F^{y} \sim M_{1}^{x}$ ⁠. Since H lies in a unique conjugate of F, and M₁ contains 59 conjugates of H, exactly 59 conjugates of F are adjacent to M₁ in $Δ_{G}$ ⁠. An elementary counting argument now shows that exactly $α := 59 | F | / | M_{1} | \approx 2.6 \times 10^{23}$ conjugates of M₁ are adjacent to F. Additionally, by the proof of [37, Theorem 1.3], the number β of conjugates of F adjacent to F is at most $γ := | G : F | \sum_{r \in R} \frac{| r^{G} \cap F |^{2}}{| r^{G} |}$ ⁠, where R is a set of representatives for the G-conjugacy classes of elements of prime order. We calculate using the GAP Character Table Library that $γ \approx 4.2 \times 10^{28}$ ⁠. We therefore deduce that there are at most $59 α γ \approx 6.5 \times 10^{53}$ conjugates $M_{1}^{x}$ of M₁ such that $M_{1} \sim F^{w} \sim F^{y} \sim M_{1}^{x}$ for some $w, y \in G$ ⁠. This is unfortunately not a useful upper bound, as it is larger than the number $| G : M_{1} | \approx 4.7 \times 10^{50}$ of conjugates of M₁.

Determining a better estimate for β is difficult due to the large index of F in G. However, if a sufficiently small upper bound for β can be obtained, then the above argument (along with similar arguments for the other types of path between M₁ and $M_{1}^{x}$ of length at most three) would yield the existence of an element x such that $d (M_{1}, M_{1}^{x}) = 4$ ⁠, so that $diam (Δ_{G}) = 6$ ⁠. Otherwise, deducing the exact value of $diam (Δ_{G})$ would require more detailed information about the neighbourhoods of conjugates of M₁, F and the maximal subgroup $PGL (2, 29)$ of G. The large order of G is again a significant obstacle to obtaining this information.

Proof of Theorem 3.5

For each $G \in {M_{11}, M_{12}, M_{22}, M_{23}, J_{1}, J_{2}}$ ⁠, we obtain $diam (Ξ (G))$ using Magma. In all other cases, for $i \in {1, 2}$ ⁠, let x_i be an element of $G ∖ {1}$ that lies in a maximal subgroup of even order, say L_i. By Proposition 3.7, $d (x_{i}, a_{i}) ⩽ 1$ for some involution a_i of G, and so (using Proposition 2.2 if $| x_{i} | = 2$ ⁠) we may choose L_i so that $x_{i} \notin Z (L_{i})$ ⁠. Lemma 2.5 now gives $d (x_{1}, x_{2}) ⩽ 4$ ⁠. Hence $diam (Ξ (G)) ⩽ 4$ if each maximal subgroup of G has even order.

It remains to consider the case where G has a maximal subgroup K of odd order. By Theorem 2.6 and Remark 2.7, $G \in {Th, B, M}$ ⁠. Let $g, h \in G ∖ {1}$ such that h lies in no maximal subgroup of even order.

First assume that $G = Th$ ⁠. Then $K ≅$ 31:15. Let $m \in K$ ⁠. If $| m | = 31$ ⁠, then m lies in a maximal subgroup of G of shape $2^{5} \cdot PSL (5, 2)$ ⁠, and otherwise $| C_{G} (m) |$ is even. Thus each element of G lies in a maximal subgroup of even order, and so the element h does not exist. Hence the first paragraph of the proof yields $diam (Ξ (G)) ⩽ 4$ ⁠.

Suppose next that $G = B$ ⁠. In this case, $K ≅$ 47:23, $| h | = 47$ and $C_{G} (h) = ⟨ h ⟩$ ⁠. Thus $h \sim s$ for each $s \in K$ of order 23. As $d (s, g) ⩽ 3$ by Lemma 3.9, we conclude that $d (h, g) ⩽ 4$ ⁠. It follows that $diam (Ξ (G)) ⩽ 4$ ⁠. In addition, the intersection graph of G has diameter 5 [20, Theorem 1.1], and so Lemma 2.3 yields $diam (Ξ (G)) ⩾ 4$ ⁠. Therefore, $diam (Ξ (G)) = 4$ ⁠.

Finally, assume that $G = M$ ⁠, so that $K ≅$ 59:29, $| h | = 59$ and $C_{G} (h) = ⟨ h ⟩$ ⁠. Thus $h \sim s$ for each $s \in K$ of order 29. Let R be a maximal subgroup of G of even order containing s, and note that $⟨ s ⟩$ is a Sylow subgroup of G. If g is not conjugate to h, then, as in the first paragraph of the proof, $d (g, a) ⩽ 1$ for some involution a of G, there exists a maximal subgroup L of G such that $g, a \in L ∖ Z (L)$ ⁠. By Lemma 2.4(iii) and the fact that two involutions generate a dihedral group, R contains an involution b such that $a \sim b$ ⁠. Moreover, $| C_{G} (s) | = 87$ ⁠, which implies that $s \sim b$ ⁠. Hence $h \sim s \sim b \sim a \sim g$ ⁠, and so $d (h, g) ⩽ 4$ ⁠. If instead $g = h^{j}$ for some $j \in G$ ⁠, then we similarly deduce the existence of involutions aʹ and bʹ such that $h \sim s \sim b^{'} \sim a^{'} \sim s^{j} \sim g$ ⁠, and so $d (h, g) ⩽ 5$ ⁠. Therefore, $diam (Ξ (G)) ⩽ 5$ ⁠. As the intersection graph of G has diameter at least 5 by Proposition 3.10, Lemma 2.3 implies that $diam (Ξ (G)) \in {4, 5}$ ⁠.

Determining the exact diameter of $Ξ (M)$ (and similarly for the non-generating graph of $M$ in Theorem 1.7) is difficult for reasons similar to those discussed in Remark 3.11.

3.3. Exceptional groups of Lie type

We now prove Theorem 1.1 in the case where G is an exceptional group of Lie type. In view of Proposition 1.5 and Theorem 2.6, it remains to prove the following. Here, q denotes a prime power, and we do not include $^{2} G_{2} (3)^{'} ≅ PSL (2, 8)$ ⁠; for that group, see Theorem 5.1.

Theorem 3.12

Let G be a finite simple group. If $G ≅ Sz (q)$ ⁠, or if q is odd and $G \in {G_{2} (q),$ $^{2} G_{2} (q),^{3} D_{4} (q), F_{4} (q), E_{8} (q)}$ ⁠, then $Ξ (G)$ is connected with diameter at most 4.

Given a group X, let Q_X be the (characteristic) subgroup generated by the involutions of X.

Lemma 3.13

Let $S := SL (2, q)$ ⁠, and let H be a quasisimple group containing a subgroup K, such that $K ≅ S$ and $Z (H) = Z (K)$ ⁠. Additionally, let R be the central product $S \circ H$ ⁠, and let π be the natural epimorphism $S \times H \to R$ ⁠. If $Q_{R} \neq R$ ⁠, then q = 3, Q_R is a maximal subgroup of R that contains $(H) π$ ⁠, and $C_{R} (Q_{R}) = Z (R)$ ⁠.

Proof.

We observe that $\tilde{S} := (S) π$ and $\tilde{K} := (K) π$ are normal subgroups of $J := S \circ K =$ $(S \times K) π$ and $\tilde{S}$ and $\tilde{H} := (H) π$ are normal subgroups of R, with $\tilde{S} ≅ S$ ⁠, $\tilde{K} ≅ K$ and $\tilde{H} ≅ H$ ⁠. Additionally, $[\tilde{H}, \tilde{S}] = ([H, S]) π = 1$ and $\tilde{H} \tilde{S} = R$ ⁠. Furthermore, the centres of R, J, $\tilde{H}$ ⁠, $\tilde{S}$ and $\tilde{K}$ all coincide, and this common centre $Z$ of order $(2, q - 1)$ is equal to $\tilde{H} \cap \tilde{S}$ ⁠. We divide the rest of the proof into two cases.

Case (a): $q \neq 3$ ⁠. We first show that $Q_{J} = J$ ⁠. This is clear if q = 2, so assume otherwise. Considering K as a copy of $SL (2, q)$ ⁠, let $L := {(A, B) \in S \times K ∣ A^{2} = B^{2} = - I_{2}}$ ⁠, where I₂ is the $2 \times 2$ identity matrix. The choices for A and B include the matrix

(\begin{matrix} 0 & a \\ - a^{- 1} & 0 \end{matrix})

for each

a \in F_{q}^{\times}

⁠. As S is quasisimple, and a quasisimple group’s proper normal subgroups are precisely its central subgroups, we see that

⟨ L ⟩^{S \times K}

projects onto each of S and K and that the kernel of each projection map is isomorphic to

S ≅ K

⁠. Thus

⟨ L ⟩^{S \times K} = S \times K

⁠. Since the image under π of each element of L is an involution, it follows that

Q_{J} = J

⁠.

Now, since $\tilde{H}$ is quasisimple and $Z < \tilde{K} ⩽ \tilde{H}$ ⁠, no proper normal subgroup of $\tilde{H}$ contains $\tilde{K}$ ⁠. Hence no proper normal subgroup of R contains J. As $J = Q_{J} ⩽ Q_{R} ⊴ R$ ⁠, we obtain $Q_{R} = R$ ⁠.

Case (b): q = 3. Here, Q_J is the image under π of the direct product of the normal Sylow 2-subgroups of S and K, which are isomorphic to the quaternion group Q₈. Thus $\tilde{S} \cap Q_{J}$ is maximal in $\tilde{S}$ and $\tilde{K} \cap Q_{J} > Z$ ⁠. As the normal subgroup $\tilde{H} \cap Q_{R}$ of $\tilde{H}$ contains $\tilde{K} \cap Q_{J}$ ⁠, it follows that $\tilde{H} ⩽ Q_{R}$ ⁠. Since $R = \tilde{H} \tilde{S}$ ⁠, we deduce that $Q_{R} = \tilde{H} \tilde{S} \cap Q_{R} = \tilde{H} (\tilde{S} \cap Q_{R})$ ⁠.

If $\tilde{S} \cap Q_{R} = \tilde{S}$ ⁠, then $Q_{R} = R$ ⁠. We will therefore assume that $\tilde{S} \cap Q_{R} < \tilde{S}$ ⁠. Then $\tilde{S} \cap Q_{R}$ is the maximal subgroup $\tilde{S} \cap Q_{J}$ of $\tilde{S}$ ⁠, and $Q_{R} = \tilde{H} (\tilde{S} \cap Q_{J})$ ⁠, which is maximal in $\tilde{H} \tilde{S} = R$ ⁠. Since $[\tilde{H}, \tilde{S}] = 1$ ⁠, we obtain $Z ⩽ C_{R} (Q_{R}) = C_{\tilde{H} \tilde{S}} (\tilde{H} (\tilde{S} \cap Q_{J})) ⩽ Z (\tilde{H}) C_{\tilde{S}} (\tilde{S} \cap Q_{J}) .$ The centralizer $C_{\tilde{S}} (\tilde{S} \cap Q_{J})$ is equal to $Z = Z (\tilde{H}) = Z (R)$ ⁠, and hence so is $C_{R} (Q_{R})$ ⁠.

For an example where $Q_{R} \neq R$ ⁠, take H to be the quasisimple group $SL (2, 9)$ ⁠.

Proposition 3.14

Let H be a finite quasisimple group. If $| Z (H) | = 2$ ⁠, then assume that $H / Z (H)$ is not isomorphic to A₇ or to $PSL (2, q)$ for any odd q. Then $Q_{H} = H$ ⁠.

Proof.

This is a straightforward consequence of the main theorem of [27], which implies that there exists an involution $a \in H ∖ Z (H)$ if $| Z (H) |$ is even. Clearly, a also exists if $| Z (H) |$ is odd. Each proper normal subgroup of the quasisimple group H lies in Z(H), and so $Q_{H} = H$ ⁠.

Lemma 3.15

Let G be a simple group in ${G_{2} (q),^{2} G_{2} (q),^{3} D_{4} (q), F_{4} (q), E_{8} (q)}$ with q odd (so that $q ⩾ 27$ if $G =^{2} G_{2} (q)$ ⁠), let a be an involution of G and let $Y := C_{G} (a)$ ⁠. Then $C_{Y} (Q_{Y}) = Z (Y) = ⟨ a ⟩$ ⁠.

Proof.

We observe from [26, pp. 171–177] that $Z (Y) = ⟨ a ⟩$ ⁠, and

$G ≅^{2} G_{2} (q)$ and $Y ≅ C_{2} \times PSL (2, q)$ ⁠;
$G ≅ F_{4} (q)$ and $Y ≅ Spin (9, q)$ ⁠;
$G ≅ E_{8} (q)$ and $Y ≅ J : 2$ ⁠, where $J := ({Spin}^{+} (16, q) / A)$ ⁠, in which A is a central subgroup of ${Spin}^{+} (16, q)$ of order 2; or
$Y = R : A$ ⁠, with $| A | = 2$ and $R ≅ SL (2, q) \circ H$ ⁠, where (G, H) lies in the set
${(G_{2} (q), SL (2, q)), (^{3} D_{4} (q), SL (2, q^{3})), (F_{4} (q), Sp (6, q)), (E_{8} (q), E_{7} (q)_{sc})} .$
Additionally, $Z (Y) = Z (R)$ ⁠, and A induces an outer automorphism on the image of H under the natural epimorphism $π : SL (2, q) \times H \to R$ ⁠.

We will divide the remainder of the proof into the above cases. In each case, since $Z (Y) = ⟨ a ⟩$ ⁠, it remains to show that $C_{Y} (Q_{Y}) = Z (Y)$ ⁠. Note that this is certainly the case if $Q_{Y} = Y$ ⁠.

Cases (a)–(c). By applying Proposition 3.14 to Y in Case (b) and J in Case (c), we easily deduce that $Q_{Y} = Y$ in each case.

Case (d). If $G ≅ G_{2} (3)$ ⁠, then $Y ≅ {SO}^{+} (4, 3)$ [42, p. 125], and $Q_{Y} = Y$ ⁠. Suppose therefore that $G ≇ G_{2} (3)$ and that $Q_{Y} < Y$ ⁠. Notice that Q_Y contains $⟨ Q_{R}, A ⟩ = Q_{R} : A$ ⁠, and thus $Q_{R} < R$ ⁠.

In order to apply Lemma 3.13, we will show that the quasisimple group H contains a subgroup K such that $K ≅ SL (2, q)$ and $Z (H) = Z (K)$ ⁠. Such K clearly exists if there exists $L ⩽ H$ with $Z (H) = Z (L)$ and $L ≅ SL (2, q^{i})$ for some positive integer i. Hence this is the case if $H \in {SL (2, q), SL (2, q^{3})}$ ⁠. If instead $H = E_{7} (q)_{sc}$ ⁠, then H contains a subgroup $L ≅ SL (2, q^{7})$ ⁠, with $Z (H) = Z (L)$ [28, p. 927, item (3)]. Finally, if $H = Sp (6, q)$ ⁠, then let V₁, V₂ and V₃ be non-degenerate two-dimensional subspaces of the symplectic space $V := F_{q}^{6}$ ⁠, such that $V = V_{1} ⊥ V_{2} ⊥ V_{3}$ ⁠. Then the intersection of the stabilizers in H of V₁, V₂ and V₃ is isomorphic to $Sp (2, q)^{3} = SL (2, q)^{3}$ ⁠. The diagonal subgroup of this direct product is isomorphic to $SL (2, q)$ and has centre Z(H).

Lemma 3.13 now shows that Q_R is a maximal subgroup of R, that $(H) π ⩽ Q_{R}$ and that $C_{R} (Q_{R}) = Z (R)$ ⁠. It follows from this first fact that the proper subgroup Q_Y of Y is maximal and equal to $Q_{R} : A$ ⁠. Since $(H) π ⩽ Q_{R} ⩽ R = (SL (2, q)) π (H) π$ and $[(SL (2, q)) π,$ $(H) π] = 1$ ⁠, each inner automorphism of Q_R acts on $(H) π$ as an inner automorphism of $(H) π$ ⁠. Thus the outer automorphism of $(H) π$ induced by A does not extend to an inner automorphism of Q_R. Therefore, $C_{Y} (Q_{R}) = C_{R} (Q_{R}) = Z (R)$ ⁠, which is equal to Z(Y) from the start of the proof. As $Z (Y) ⩽ C_{Y} (Q_{Y}) ⩽ C_{Y} (Q_{R})$ ⁠, we conclude that $C_{Y} (Q_{Y}) = Z (Y)$ ⁠.

Proof of Theorem 3.12

Theorem 2.6 implies that each maximal subgroup of G has even order, and so it suffices by Proposition 2.2 and Lemma 2.5 to show that each non-involution $x \in G ∖ {1}$ is adjacent in $Ξ (G)$ to some involution. Let M be a maximal subgroup of G containing x. Assume first that $G ≇ Sz (q)$ ⁠, so that q is odd, and let a be an involution of M. If $x \sim a$ ⁠, then we are done. Otherwise, $x \in C_{G} (a)$ ⁠. By Lemma 3.15, a is the unique non-identity element of $C_{G} (a)$ that centralizes each involution of $C_{G} (a)$ ⁠. Hence $x \sim a^{'}$ for some involution $a^{'} \in C_{G} (a)$ ⁠.

Assume now that $G ≅ Sz (q)$ ⁠. By Theorem 4 on page 122 of [41], $C_{G} (y)$ is nilpotent for each $y \in G ∖ {1}$ ⁠. As the only non-abelian finite simple groups with nilpotent maximal subgroups are $PSL (2, p)$ for various primes p (see [40, p. 183]), we deduce that $Z (M) = 1$ and $C_{M} (x) < M$ ⁠. If $M ≅ Sz (q_{0})$ ⁠, for some proper power q₀ of 2 dividing q, then $M = Q_{M}$ ⁠. It follows in this case that M contains an involution a not centralizing x, and so $x \sim a$ ⁠. If instead $M ≇ Sz (q_{0})$ ⁠, then by Section 4, page 133 and Theorem 9 on page 137 of [41], M is conjugate in G to

the Frobenius group $W := S : C_{q - 1}$ ⁠, where S is a Sylow 2-subgroup of G;
the dihedral group $X := D_{2 (q - 1)}$ ⁠; or
a Frobenius group $Y_{\pm} := C_{q \pm \sqrt{2 q} + 1} : C_{4}$ ⁠.

If $M ≅ X$ ⁠, then again $Q_{M} = M$ and $x \sim a$ for some involution $a \in M$ ⁠. If instead $M ≅ Y_{\pm}$ ⁠, then let N be the normal subgroup $C_{q \pm \sqrt{2 q} + 1}$ of M. As M is Frobenius, there exists a complement H of N with $x \notin H$ ⁠. No non-identity element of H centralizes x, and so x is adjacent in $Ξ (G)$ to the unique involution of H.

Suppose finally that $M ≅ W$ ⁠. If $x \notin S$ ⁠, then x centralizes no non-identity element of S, and so x is adjacent in $Ξ (G)$ to each involution of S. Now, Z(S) consists of all elements of S of order at most 2, and each element of $S ∖ Z (S)$ has order 4, by Lemma 1 on page 112 and Theorem 7 on page 133 of [41]. Additionally, G has a unique conjugacy class of cyclic subgroups of order 4 (see the final sentence of page 121 and Proposition 18 on page 126 of [41]), and so if the non-involution x lies in S, then it also lies in a maximal subgroup $L ≅ Y_{\pm}$ ⁠. By the previous paragraph, x is adjacent in $Ξ (G)$ to an involution of L.

Magma calculations show that $diam (Ξ (Sz (8))) = 3$ and $diam (Ξ (G_{2} (3))) = 2$ ⁠. We do not know if any finite simple exceptional group G satisfies $diam (Ξ (G)) > 3$ ⁠. Observe also that the proof of Theorem 3.12 relies on useful properties of the involution centralizers in G (and of $Sz (q)$ and its maximal subgroups). Indeed, in the q odd case, we have considered precisely those finite simple groups whose involutions are all centralized by maximal subgroups of maximal rank (see [26, Theorem 4.5.1] and [36]). The involution centralizers for the remaining exceptional groups have more complicated structures (see for example [2] and [26, Theorem 4.5.1]), so alternative methods would be necessary to prove an analogue of Theorem 3.12 for those groups.

4. Matrices and subspace stabilizers

We now consider various matrices and subspace stabilizers. The results here will be useful when proving Theorem 1.1 for linear and unitary groups. Let n be a positive integer, q a prime power and I_k the k × k identity matrix over $F_{q}$ ⁠, for a positive integer k. Additionally, let $E_{i, j}$ be the n × n matrix with (i, j) entry equal to 1 and all other entries equal to 0.

4.1. Matrices and subspace stabilizers in linear groups

([39, p. 148 & pp. 161–162])

Definition 4.1

Let

f (x) := x^{n} - β_{n} x^{n - 1} - \dots - β_{2} x - β_{1}

be a (monic) polynomial in

F_{q} [x]

⁠. The companion matrix of f is the n × n matrix

C (f) := (\begin{matrix} 0 & I_{n - 1} \\ A & B \end{matrix}),

where

$A:=(

\begin{matrix} β_{1} \end{matrix}

⁠,

$B:=(

\begin{matrix} β_{2} & \dots & β_{n} \end{matrix}

and

C (f) = A

when n = 1. If f is irreducible over

F_{q}

⁠, then for each positive integer k, the hypercompanion matrix of f ^k is the kn × kn matrix

C_{k} (f) := (\begin{matrix} C (f) & E_{n, 1} & 0 & \dots & 0 \\ 0 & C (f) & E_{n, 1} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋱ & ⋮ \\ 0 & 0 & 0 & ⋱ & E_{n, 1} \\ 0 & 0 & 0 & \dots & C (f) \end{matrix}) .

Since a subgroup $⟨ A ⟩$ of $GL (n, q)$ is irreducible if and only if the characteristic polynomial χ_A of A is irreducible, the following lemma will shed light on certain irreducible subgroups.

Lemma 4.2

Let $a \in F_{q}^{\times}$ ⁠. Then the set of irreducible factors in $F_{q} [x]$ of the binomial $x^{q - 1} - a$ is ${x^{| a |} - b ∣ b \in F_{q}^{\times}, b^{(q - 1) / | a |} = a}$ ⁠.

Proof.

For each positive integer k, let ϕ_k be the homomorphism $s \mapsto s^{k}$ of $F_{q}^{\times}$ ⁠, and let H_k be the image of ϕ_k, of order $(q - 1) / (k, q - 1)$ ⁠. Additionally, let $r := | a |$ and $t := (q - 1) / r$ ⁠. Then $H_{t} = ⟨ a ⟩$ ⁠. Since $| \ker (ϕ_{t}) | = t$ ⁠, there are exactly t distinct roots $b_{1}, \dots, b_{t} \in F_{q}^{\times}$ of the binomial $f (x) := x^{t} - a$ ⁠. Hence $f (x) = \prod_{i = 1}^{t} (x^{t} - b_{i})$ ⁠, and $x^{q - 1} - a = f (x^{r}) = \prod_{i = 1}^{t} (x^{r} - b_{i}) .$

It remains to show that the binomial $x^{r} - b_{i}$ is irreducible over $F_{q}$ for each i. Since $b_{i}^{t} = a$ ⁠, we see that $r = | a |$ divides $| b_{i} |$ ⁠. Additionally, if r is divisible by 4, then so is q − 1. It therefore suffices by [34, Theorems 3.3 and 3.35] to prove that r is coprime to $u := (q - 1) / | b_{i} |$ ⁠.

Since $| H_{u} | = | b_{i} |$ ⁠, there exists $c_{i} \in F_{q}^{\times}$ with $c_{i}^{u} = b_{i}$ ⁠, and hence $c_{i}^{u t} = a$ ⁠. Thus $a \in H_{u t}$ ⁠, and so r divides $| H_{u t} | = (q - 1) / (u t, q - 1) = t r / (u t, t r) = r / (u, r)$ ⁠. Hence $(u, r) = 1$ ⁠.

Recall that matrices $A, B \in GL (n, q)$ are similar if and only if $χ_{A} = χ_{B}$ ⁠.

Lemma 4.3

Let $A \in SL (n, q)$ ⁠, and suppose that $A^{q^{2} - 1} \in Z (SL (n, q))$ and that $⟨ A ⟩$ acts irreducibly on $F_{q}^{n}$ ⁠. Then $n \in {1, 2}$ ⁠. If, in addition, n = 2 and $A^{q - 1} \in Z (SL (2, q))$ ⁠, then $q \equiv 3 (\mod 4)$ ⁠.

Proof.

Since $A^{q^{2} - 1} \in Z (SL (n, q))$ ⁠, there exists $a \in F_{q}^{\times}$ such that $A^{q^{2} - 1} - a I_{n} = 0$ ⁠. Thus χ_A, which is irreducible over $F_{q}$ ⁠, divides $x^{q^{2} - 1} - a \in F_{q} [x]$ ⁠. Furthermore, $F_{q^{n}}$ is the splitting field for χ_A over $F_{q}$ ⁠, and A is similar to the companion matrix $C (χ_{A})$ ⁠. To prove the required result, we will study χ_A as a polynomial in $F_{q^{2}} [x]$ ⁠. By Lemma 4.2, the set of irreducible factors in $F_{q^{2}} [x]$ of $x^{q^{2} - 1} - a$ is ${x^{| a |} - b ∣ b \in F_{q^{2}}^{\times}, b^{(q^{2} - 1) / | a |} = a}$ ⁠.

If n is odd, then χ_A is irreducible over $F_{q^{2}}$ ⁠. Thus $n = | a |$ ⁠, and $χ_{A} = x^{n} - b$ for some $b \in F_{q}^{\times}$ ⁠, with $b^{(q^{2} - 1) / n} = a$ ⁠. Since $det (C (x^{n} - b)) = b$ ⁠, we deduce that b = 1. Hence a = 1 and n = 1.

If instead n is even, then each irreducible factor of χ_A in

F_{q^{2}}

has degree

n / 2

⁠. In particular,

| a | = n / 2

⁠, and there exist

b_{1}, b_{2} \in F_{q^{2}}^{\times}

such that

χ_{A} (x) = (x^{n / 2} - b_{1}) (x^{n / 2} - b_{2}) = x^{n} - (b_{1} + b_{2}) x^{n / 2} + b_{1} b_{2},

with

b_{1}^{(q^{2} - 1) / (n / 2)} = b_{2}^{(q^{2} - 1) / (n / 2)} = a

and

b_{1} b_{2}, b_{1} + b_{2} \in F_{q}

⁠. Here,

det (C (χ_{A})) = b_{1} b_{2}

⁠, and thus

b_{2} = b_{1}^{- 1}

⁠. Therefore,

a = a^{- 1}

⁠, and hence

n / 2 = | a | \in {1, 2}

⁠. In particular, if q is even, then

a \in F_{q}^{\times}

has odd order, and n = 2. Otherwise, arguing as in [11, pp. 569–570] shows that the irreducible polynomial

x^{n} - (b_{1} + b_{2}) x^{n / 2} + 1 \in F_{q} [x]

cannot have degree 4, and again n = 2.

Finally, if n = 2 and $A^{q - 1} \in Z (SL (2, q))$ ⁠, then $A^{q - 1} - c I_{2} = 0$ for some $c \in {- 1, 1}$ ⁠. Hence the irreducible polynomial χ_A divides $x^{q - 1} - c$ ⁠. It follows from Lemma 4.2 and the previous paragraph that $χ_{A} (x) = x^{2} + 1$ ⁠, which is irreducible if and only if $q \equiv 3 (\mod 4)$ ⁠.

Let $H := SL (n, q)$ ⁠, with $n ⩾ 2$ and $q ⩾ 4$ if n = 2, so that $H / Z (H)$ is simple. Additionally, let $V := F_{q}^{n}$ be the natural module for H and let H_X be the stabilizer in H of a subspace X of V.

Lemma 4.4

Let X and Y be distinct one-dimensional subspaces of V. Then:

no commutator in H_X is a non-identity scalar matrix;
$C_{H} (H_{X}) = Z (H)$ ⁠; and
$C_H(H_X \cap H_Y) = ${\begin{cases} H_{X} \cap H_{Y}, & if n = 2, or n = 3 \, a n d q = 2, \\ Z (H), & otherwise. \end{cases}$ $

Proof.

Up to conjugacy by a fixed element of H, the stabilizer H_X consists of the matrices in H with a first row of the form

\begin{matrix} (λ_{1} & 0 & 0 & \dots & 0) \end{matrix}

⁠, with

λ_{1} \in F_{q}^{\times}

⁠, and H_Y is the set of matrices with a second row of the form

\begin{matrix} (0 & λ_{2} & 0 & \dots & 0) \end{matrix}

⁠, with

λ_{2} \in F_{q}^{\times}

⁠. The restriction of a matrix in H_X to its (1, 1) entry is a homomorphism from H_X to the abelian group

F_{q}^{\times}

⁠, and its kernel clearly contains all commutators in H_X. Thus (i) holds. We split the proof of (ii) and (iii) into two cases. In each case, let

W \in C_{H} (H_{X} \cap H_{Y})

⁠.

Case (a): n = 2. Let ω be a primitive element of $F_{q}$ ⁠, $A := diag (ω, ω^{- 1}) \in H_{X} \cap H_{Y}$ and $D := I_{2} + E_{2, 1} \in H_{X}$ ⁠. The equality AW = WA gives $W \in H_{X} \cap H_{Y}$ ⁠, which is abelian. Hence we obtain (iii). If $W \in C_{H} (X)$ ⁠, then DW = WD, and we deduce that $W \in Z (H)$ ⁠, hence (ii).

Case (b): $n ⩾ 3$ ⁠. It is easy to check the result if n = 3 and q = 2, so assume otherwise. If n = 3, then let $b \in F_{q}^{\times} ∖ {1}$ and $B := diag (1, b, b^{- 1}), B^{'} := diag (b, 1, b^{- 1}) \in H_{X} \cap H_{Y}$ ⁠. We deduce from the equalities BW = WB and $B^{'} W = W B^{'}$ that W is diagonal. If instead $n ⩾ 4$ ⁠, then let r and s be distinct integers with $3 ⩽ r ⩽ n$ and $1 ⩽ s ⩽ n$ ⁠. Then $C_{r, s} := I_{n} + E_{r, s} ⩽$ $H_{X} \cap H_{Y}$ ⁠, and the equalities $C_{r, s} W = W C_{r, s}$ (for all r and s) imply that W is again diagonal.

In each case, let $F \in H_{X} \cap H_{Y}$ be the matrix obtained from I_n by setting all entries in the final row to 1. As W is diagonal, the equality WF = FW yields $W \in Z (H)$ ⁠. Thus we have proved (iii), and (ii) follows immediately.

4.2. Subspace stabilizers in unitary groups

Throughout this subsection, let $n ⩾ 3$ ⁠, with $q ⩾ 3$ if n = 3, so that $G := PSU (n, q)$ is simple. Additionally, let V be the natural module $F_{q^{2}}^{n}$ for $SU (n, q)$ ⁠, equipped with the unitary form with Gram matrix I_n. Then a matrix $A \in SL (n, q^{2})$ lies in $SU (n, q)$ if and only if $A A^{σ T} = I_{n}$ ⁠, where σ is the automorphism $α \mapsto α^{q}$ of $F_{q^{2}}$ ⁠. The following theorem will be useful when considering $Ξ (G)$ ⁠. Here, $G_{(Δ)}$ denotes the pointwise stabilizer in G of a set Δ of subspaces of V.

Theorem 4.5

Let Δ be a set of k-dimensional subspaces of V.

Suppose that $| Δ | < ⌈ n / k ⌉$ ⁠. If $(q + 1) ∤ n$ ⁠, or if $k ∤ (n - 1)$ ⁠, then $G_{(Δ)} \neq 1$ ⁠.
Suppose that $| Δ | < ⌈ n / k ⌉ - 1$ ⁠. Then $G_{(Δ)} \neq 1$ ⁠.

An analogue of the following lemma holds for certain classical algebraic groups; see [7, Section 4.1].

Lemma 4.6

Let W be an $(n - 1)$ -dimensional subspace of V. Then $SU (n, q)$ contains a non-scalar matrix that acts as a scalar on W if and only if $W^{⊥}$ is totally singular or $(q + 1) ∤ n$ ⁠.

Proof.

First, $SU (n, q)$ has two orbits on the set of one-dimensional subspaces of V: the non-degenerate subspaces and the totally singular subspaces (cf. Witt’s Lemma). Thus it suffices to consider two choices for W, one for each possible orbit containing $W^{⊥}$ ⁠. Let ${e_{1}, \dots, e_{n}}$ be the basis for V corresponding to the Gram matrix I_n, and let ω be a primitive element of $F_{q^{2}}$ ⁠.

Case (a): $W^{⊥}$ is non-degenerate. We may assume that $W^{⊥} = ⟨ e_{1} ⟩$ ⁠, so that $W = ⟨ e_{2}, e_{3}, \dots, e_{n} ⟩$ ⁠. Any matrix in $SL (n, q^{2})$ that acts as a scalar on W also stabilizes $W^{⊥}$ and hence is equal to $B_{α} := diag (α^{- (n - 1)}, α, \dots, α)$ for some $α \in F_{q^{2}}^{\times}$ ⁠. Moreover, $B_{α} \in SU (n, q)$ if and only if $α^{q + 1} = 1$ ⁠.

Let $λ := ω^{q - 1}$ ⁠. Observe that if $(q + 1) ∤ n$ ⁠, then B_λ is a non-scalar matrix in $SU (n, q)$ that acts as λ on W. If instead $q + 1 ∣ n$ ⁠, then any scalar $α \in F_{q^{2}}^{\times}$ satisfying $α^{q + 1} = 1$ also satisfies $α^{- (n - 1)} = α$ ⁠. Therefore, in this case, no non-scalar matrix in $SU (n, q)$ acts as a scalar on W.

Case (b): $W^{⊥}$ is totally singular. If q is even, then let $γ := ω^{q + 1}$ and $δ := 1$ ⁠, and otherwise, let $γ := ω$ and $δ := ω^{(q - 1) / 2}$ ⁠. Then $δ^{q + 1} = - 1$ for all q, and so $δ e_{1} + e_{2}$ is singular. Hence we may assume that $W^{⊥} = ⟨ δ e_{1} + e_{2} ⟩$ ⁠, so that $W = ⟨ δ e_{1} + e_{2}, e_{3}, \dots, e_{n} ⟩$ ⁠. The direct sum of

$\left(

\begin{matrix} 1 + γ δ & γ \\ - γ δ^{2} & 1 - γ δ \end{matrix}

\right)$

and

I_{n - 2}

is a non-scalar matrix in

SU (n, q)

that acts trivially on W.

Corollary 4.7

Let U be an $(n - 2)$ -dimensional subspace of V. Then $SU (n, q)$ contains a non-scalar matrix that acts as a scalar on U.

Proof.

Observe that $U^{⊥}$ contains a one-dimensional totally singular subspace X. By Lemma 4.6, some non-scalar matrix in $SU (n, q)$ acts as a scalar on $X^{⊥}$ and hence on $U \subseteq X^{⊥}$ ⁠.

Proof of Theorem 4.5

If $| Δ | < ⌈ n / k ⌉$ ⁠, then the subspace $⟨ Δ ⟩$ of V lies in an $(n - 1)$ -dimensional subspace W. Lemma 4.6 shows that if $(q + 1) ∤ n$ ⁠, then $SU (n, q)$ contains a non-scalar matrix that acts as a scalar on W and hence on $⟨ Δ ⟩$ ⁠. Therefore, $G_{(Δ)} \neq 1$ ⁠.

Finally, assume that $| Δ | < ⌈ n / k ⌉ - 1$ or that $| Δ | = ⌈ n / k ⌉ - 1$ and $k ∤ (n - 1)$ ⁠. Then $⟨ Δ ⟩$ lies in an $(n - 2)$ -dimensional subspace U of V. By Corollary 4.7, $SU (n, q)$ contains a non-scalar matrix that acts as a scalar on U and hence on $⟨ Δ ⟩$ ⁠. We again conclude that $G_{(Δ)} \neq 1$ ⁠.

5. LINEAR AND UNITARY GROUPS AND THE NON-GENERATING GRAPH

In this section, we complete the proof of Theorem 1.1 by showing that it holds for linear and unitary groups. In addition, we prove Theorem 1.7. Define n, q, I_k and $E_{i, j}$ as in Section 4, and let $H \in {SL (n, q), SU (n, q)}$ ⁠, $Z := Z (H)$ and $G := H / Z$ ⁠. We will largely work in the group H, appealing to the following consequence of the definition of $Ξ (G)$ ⁠: for $A, B \in H ∖ Z$ ⁠, the vertices $Z A$ and $Z B$ of $Ξ (G)$ are adjacent if and only if $[A, B] \notin Z$ and $⟨ A, B, Z ⟩ < H$ ⁠.

5.1. Linear groups

Assume that $H = SL (n, q)$ ⁠, with $n ⩾ 2$ and $q ⩾ 4$ if n = 2, so that G is simple.

Theorem 5.1

Let G be the linear group $PSL (n, q)$ ⁠. Then $diam (Ξ (G)) ⩽ 4$ ⁠. Moreover, if n = 2, then $diam (Ξ (G)) = 2$ if q is even or $q ⩽ 9$ ⁠, and $diam (Ξ (G)) = 3$ otherwise.

Let $U$ be the set of one-dimensional subspaces of the natural module $V := F_{q}^{n}$ for H. We proceed by considering paths in $Ξ (H)$ containing elements that stabilize subspaces in $U$ ⁠.

Lemma 5.2

Let $X, Y \in U$ ⁠, $K \in H_{X} ∖ Z$ and $L \in H_{Y} ∖ Z$ ⁠. Then $d (Z K, Z L) ⩽ 2$ ⁠.

Proof.

We may assume that $K \neq L$ ⁠. We claim that there exists a path $(U_{1}, \dots, U_{j})$ in $Ξ (H)$ ⁠, where $j ⩽ 3$ ⁠, $U_{1} = K$ ⁠, $U_{j} = L$ and $U_{2} \in H_{X} \cap H_{Y}$ ⁠. Since $Z (H_{X}) = Z (H_{Y}) = Z$ by Lemma 4.4(ii), the claim follows from Lemma 2.1 if K or L lies in $H_{X} \cap H_{Y}$ ⁠. Otherwise, Lemma 4.4(iii) implies that $C_{H_{X} \cap H_{Y}} (K)$ and $C_{H_{X} \cap H_{Y}} (L)$ are proper subgroups of $H_{X} \cap H_{Y}$ ⁠. Thus there exists an $M \in H_{X} \cap H_{Y}$ centralizing neither K nor L, and we can set $U_{2} = M$ ⁠.

Now, $[U_{i}, U_{i + 1}] \neq 1$ for all $i \in {1, \dots, j - 1}$ ⁠, and so $[U_{i}, U_{i + 1}] \notin Z$ by Lemma 4.4(i). Moreover, $⟨ U_{i}, U_{i + 1}, Z ⟩$ lies in H_X or H_Y. Hence $(Z U_{1}, \dots, Z U_{j})$ is a path in $Ξ (G)$ ⁠.

Lemma 5.3

Suppose that n > 2 or $q ≢ 3 (\mod 4)$ ⁠, and let $A \in H$ such that $⟨ A ⟩$ stabilizes no subspace in $U$ ⁠. Then there exist $X \in U$ and $K \in H_{X}$ such that $Z A \sim Z K$ ⁠.

Proof.

We divide the proof into two cases.

Case (a): $⟨ A ⟩$ acts reducibly on V. It is clear that n > 2. The matrix A is similar to a block matrix whose final row of blocks is

\begin{matrix} (0 & \dots & 0 & R) \end{matrix}

⁠, with R being a hypercompanion matrix and a proper submatrix of A (see [39, Theorem 8.10]). Since

Aut (G) ⩽ Aut (Ξ (G))

⁠, we may assume without loss of generality that A is this block matrix.

Let $K := I_{n} + E_{2, 1}$ ⁠. Then $K \in H_{X}$ ⁠, where $X \in U$ is spanned by

\begin{matrix} (1 & 0 & \dots & 0) \end{matrix}

\in V$

⁠. Each matrix in

Z \cup {K}

can be viewed as a block matrix, with a final row

\begin{matrix} (0 & \dots & 0 & S) \end{matrix}

of blocks, for some nonzero block S with the same dimensions as R. Hence

⟨ A, K, Z ⟩ < H

⁠.

It remains to prove that $[A, K] \notin Z$ ⁠. For a contradiction, suppose otherwise, so that $(K^{- 1})^{A} K = c I_{n}$ for some $c \in F_{q}^{\times}$ ⁠. Then $(K^{- 1})^{A} = c K^{- 1}$ ⁠. As K has eigenvalue 1 with algebraic multiplicity n, while cK⁻¹ has eigenvalue c, we deduce that $[A, K] = 1$ ⁠. However, $(A K)_{11} = 1$ and $(K A)_{11} = 0$ ⁠, a contradiction.

Case (b): $⟨ A ⟩$ acts irreducibly on V. By [15, Proposition 3.6.1], A lies in a Singer subgroup S of $GL (n, q)$ ⁠, that is, a cyclic subgroup of order $q^{n} - 1$ ⁠. Additionally, $N := N_{GL (n, q)} (S)$ is the group $S : ⟨ B ⟩$ of order $n (q^{n} - 1)$ ⁠, where $B \in GL (n, q)$ is similar to the companion matrix $C (x^{n} - 1)$ and satisfies $F^{B} = F^{q}$ for each $F \in S$ (see [33, pp. 187–188] and [30, p. 497]). As $C (x^{n} - 1)$ stabilizes the subspace in $U$ spanned by the all-ones vector, B also stabilizes some $X \in U$ ⁠. Note that $det (B) = det (C (x^{n} - 1))$ is equal to 1 if q is even or n is odd, and −1 otherwise. Additionally, N is soluble, and so its subgroup $⟨ A, B, Z ⟩$ is proper in H. Furthermore, $[A, B] = A^{- 1} A^{B} = A^{q - 1}$ ⁠. Since $A^{q^{2} - 1} \in ⟨ A^{q - 1} ⟩$ ⁠, Lemma 4.3 and our assumptions on n and q yield $[A, B] \notin Z$ ⁠.

It again suffices to find a matrix $K \in H_{X}$ with $[A, K] \notin Z$ and $⟨ A, K, Z ⟩ < H$ ⁠. If n is odd or q is even, then set K = B. If instead n = 2 and $q \equiv 1 (\mod 4)$ ⁠, then set $K = α B$ for some square root $α \in F_{q}$ of −1. Finally, if q is odd and n is even and greater than 2, then $B^{2} \in H_{X}$ ⁠. Additionally, $[A, B^{2}] = A^{q^{2} - 1}$ ⁠, which does not lie in $Z$ by Lemma 4.3. Thus we set $K = B^{2}$ ⁠.

Proof of Theorem 5.1

Let $x, y \in G ∖ {1}$ ⁠. We will bound $d (x, y)$ ⁠. By Lemma 5.2, $d (x, y) ⩽ 2$ if $⟨ x ⟩$ and $⟨ y ⟩$ stabilize one-dimensional subspaces of V. Since $diam (Ξ (G)) ⩾ 2$ ⁠, we may assume without loss of generality that $⟨ x ⟩$ stabilizes no such subspace. If $n ⩾ 3$ ⁠, then Lemma 5.3 shows that $x \sim s$ for some $s \in G_{X}$ with $X \in U$ ⁠. Similarly, $d (y, t) ⩽ 1$ for some $t \in G_{Y}$ with $Y \in U$ ⁠. Hence $d (x, y) ⩽ d (x, s) + d (s, t) + d (t, y) ⩽ 4$ ⁠, as required.

Suppose from now on that n = 2. Magma computations show that $diam (Ξ (G)) = 2$ when q is odd and at most 9, so we will assume that q is even or at least 11. Let p be the prime dividing q, and let $r := (2, q - 1)$ ⁠. In what follows, all information about elements and subgroups of G is from [16, Ch. XII], except where stated otherwise. We first note that $| G | = q (q^{2} - 1) / r$ and that each non-identity element of G lies in either a unique cyclic subgroup of order $(q - 1) / r$ ⁠, a unique cyclic subgroup of order $(q + 1) / r$ ⁠, or a unique Sylow p-subgroup isomorphic to the elementary abelian group E of order q. Moreover, all cyclic subgroups of G of a given order $(q \pm 1) / r$ are conjugate. In addition, each element of order dividing q or $(q - 1) / r$ lies in a parabolic maximal subgroup of shape $E : \frac{q - 1}{r}$ ⁠, which is the stabilizer in G of a subspace in $U$ ⁠.

It now follows that $| x |$ divides $(q + 1) / r$ ⁠. The unique cyclic subgroup of order $(q + 1) / r$ containing x lies in a unique maximal subgroup $L ≅ D_{2 (q + 1) / r}$ ⁠. We divide the remainder of the proof into two cases.

Case (a): q is even. Suppose first that $| y |$ does not divide q − 1. All involutions of G are conjugate, as are all cyclic subgroups of order q + 1, and so y lies in a G-conjugate M of L. As $Z (L) = 1$ ⁠, Lemma 2.1 yields $d (x, y) ⩽ 2$ if L = M. If instead $L \neq M$ ⁠, then $L \cap M$ contains an involution a [23, Lemma 2.3], and it is clear that $C_{L} (a) = ⟨ a ⟩ = C_{M} (a)$ ⁠. Hence $x \sim a$ and $d (a, y) ⩽ 1$ ⁠, and so $d (x, y) ⩽ 2$ ⁠.

Next, suppose that $| y |$ divides q − 1. Then y lies in a parabolic subgroup P of G of shape $E : (q - 1)$ ⁠. As $| P | | L | = 2 | G |$ ⁠, there exists an involution $b \in P \cap L$ ⁠. The centralizer of b in G is the Sylow 2-subgroup of P, and thus $x \sim b \sim y$ ⁠. Therefore, $diam (Ξ (G)) ⩽ 2$ ⁠.

Case (b): q is odd. There exist G-conjugates J and K of L with $J \cap K = 1$ [23, Lemma 2.2]. As above, J is the unique maximal subgroup of G containing an element s of order $(q + 1) / 2$ and K is the unique maximal subgroup containing a conjugate t of s. Neither s nor any neighbour of s in $Ξ (G)$ is a neighbour of t, and so $d (s, t) ⩾ 3$ ⁠. Hence it remains to show that $d (x, y) ⩽ 3$ ⁠.

Suppose first that $| y |$ divides $(q + 1) / 2$ ⁠. Notice that $Z (L) = 1$ if $q \equiv 1 (\mod 4)$ ⁠, else $| Z (L) | = 2$ ⁠. Additionally, since all cyclic subgroups of G of a given order $(q \pm 1) / 2$ are conjugate, so are all involutions of G. It follows that there exist G-conjugates R and S of L with $x \in R ∖ Z (R)$ and $y \in S ∖ Z (S)$ ⁠. If R = S, then $d (x, y) ⩽ 2$ by Lemma 2.1. Otherwise, as the dihedral group R is generated by a pair of non-commuting involutions, there exists an involution $a \in R ∖ (Z (R) \cup S)$ ⁠. In addition, Lemma 2.4(iii) yields an involution $b \in S ∖ Z (S)$ with $[a, b] \neq 1$ ⁠. Since $⟨ a, b ⟩$ is dihedral, with $C_{R} (a) = Z (R) \times ⟨ a ⟩$ and $C_{S} (b) = Z (S) \times ⟨ b ⟩$ ⁠, we deduce that $(x, a, b, y)$ contains a path in $Ξ (G)$ from x to y. Hence $d (x, y) ⩽ 3$ ⁠.

Assume from now on that $| y |$ does not divide $(q + 1) / 2$ ⁠, so that y lies in a parabolic subgroup P of shape $E : \frac{q - 1}{2}$ ⁠, with $P = G_{X}$ for some $X \in U$ ⁠. If $q \equiv 1 (\mod 4)$ ⁠, then Lemma 5.3 yields $x \sim k$ for some $k \in G_{Y}$ with $Y \in U$ ⁠. Since $d (k, y) ⩽ 2$ by Lemma 5.2, we obtain $d (x, y) ⩽ 3$ ⁠.

Suppose therefore that $q \equiv 3 (\mod 4)$ ⁠, and let c be an element of P of order $(q - 1) / 2$ ⁠. Then $⟨ c ⟩$ is the pointwise stabilizer $G_{(X, Y_{c})}$ for some $Y_{c} \in U ∖ {X}$ ⁠, and $N_{c} := N_{G} (⟨ c ⟩)$ is dihedral of order q − 1 and equal to the setwise stabilizer $G_{{X, Y_{c}}}$ ⁠. It is also clear that $c \sim f$ for each of the $(q - 1) / 2$ involutions $f \in N_{c}$ ⁠, and in fact $y \sim f$ if $y \in ⟨ c ⟩$ ⁠, since $| y | \neq 2$ ⁠. In addition, $C_{G} (⟨ c ⟩) = ⟨ c ⟩$ ⁠, and so if $y \notin ⟨ c ⟩$ ⁠, then $y \sim c \sim f$ ⁠. Now, let cʹ be an element of $P ∖ ⟨ c ⟩$ of order $| c |$ ⁠, so that $Y_{c} \neq Y_{c^{'}}$ ⁠. Then $N_{c} \cap N_{c^{'}} = G_{{X, Y_{c}}} \cap G_{{X, Y_{c^{'}}}} = G_{(X, Y_{c})} \cap G_{(X, Y_{c^{'}})} =$ $⟨ c ⟩ \cap ⟨ c^{'} ⟩ = 1$ ⁠. Since there are q cyclic subgroups of order $| c |$ in P, it follows that y has distance at most two from at least $m := q (q - 1) / 2$ involutions of G. This in fact accounts for all involutions of G, since the centralizer in G of an involution is conjugate to L, which has order $| G | / m$ ⁠. Hence if $| x | = 2$ ⁠, then $d (x, y) ⩽ 2$ ⁠. Otherwise, x is adjacent to each involution in $L ∖ Z (L)$ ⁠, and so $d (x, y) ⩽ 3$ ⁠, completing the proof.

Using Magma, we see that $Ξ (G)$ has diameter 2 when $G \in {PSL (3, 4), PSL (4, 2)}$ and diameter 3 when $G \in {PSL (3, 3), PSL (3, 5), PSL (3, 7), PSL (4, 3)}$ ⁠. Note that the diameter of $Ξ (PSL (3, 4))$ was incorrectly reported as 3 in [21].

5.2. Unitary groups

Assume that $H = SU (n, q)$ ⁠, with $n ⩾ 3$ and $q ⩾ 3$ if n = 3, so that G is simple. In fact, by Proposition 1.5 and Theorem 2.6, we may assume that n is prime.

Theorem 5.4

Let G be the unitary group $PSU (n, q)$ ⁠, with n being an odd prime.

$Ξ (G)$ is connected with diameter at most 5.
Suppose that n = 7 and q = 2. Then $Ξ (G)$ is connected with diameter 4.

Let V be the natural module $F_{q^{2}}^{n}$ for $H = SU (n, q)$ ⁠, and fix a basis ${e_{1}, \dots, e_{n}}$ for V so that the unitary form on V has Gram matrix I_n.

Lemma 5.5

Suppose that n = 3, let ω be a primitive element of $F_{q^{2}}$ and let $λ := ω^{q - 1}$ ⁠. Let $B_{1} := diag (λ^{- 2}, λ, λ)$ ⁠, $B_{2} := diag (λ, λ^{- 2}, λ)$ and $B_{3} := diag (λ, λ, λ^{- 2})$ ⁠. Additionally, let A₁ and A₂ be H-conjugates of B₁.

$B_{i} \in H ∖ Z$ for each i.
B₂ and B₃ are each conjugate to B₁ in H.
$⟨ A_{1}, A_{2} ⟩$ stabilizes a one-dimensional subspace of V.
If $[B_{i}, A_{1}] = 1$ for all i, then $A_{1} \in {B_{1}, B_{2}, B_{3}}$ ⁠.

Proof.

Since $λ^{q} = λ^{- 1}$ and $det (B_{i}) = 1$ ⁠, we see that $B_{i} \in H$ ⁠. Additionally, $ω^{3 (q - 1)} \neq 1$ ⁠, and so $B_{i} \notin Z$ ⁠, hence (i). For (ii), note that the matrices

$\left(

\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & - 1 \end{matrix}

\right)$

and

$\left(

\begin{matrix} 0 & 0 & 1 \\ 0 & - 1 & 0 \\ 1 & 0 & 0 \end{matrix}

\right)$

lie in H and conjugate B₁ to B₂ and B₃, respectively.

To prove (iii), we may assume that $A_{1} = B_{1}$ ⁠. Let $F \in H$ such that $A_{2} = B_{1}^{F}$ ⁠, and note that B₁ and A₂ act as λ on the subspaces $E := ⟨ e_{2}, e_{3} ⟩$ and E^F of V, respectively. Hence $⟨ B_{1}, A_{2} ⟩$ stabilizes each subspace of $E \cap E^{F}$ ⁠, which has positive dimension since $\dim (V) = 3$ ⁠.

Finally, $C_{H} ({B_{1}, B_{2}, B_{3}})$ consists of diagonal matrices, and all H-conjugates of B₁ have the same characteristic polynomial as B₁. Since B₁, B₂ and B₃ are the only diagonal matrices in $GL (n, q^{2})$ with this characteristic polynomial, we obtain (iv).

Lemma 5.6

Suppose that n is an odd prime.

The companion matrix $C (x^{n} - 1)$ is an element of H.
Let R be an element of H that is conjugate to $C (x^{n} - 1)$ ⁠. Then $Z R$ is adjacent in $Ξ (G)$ to an involution of G.
Let R and S be H-conjugates of the companion matrix $C (x^{n} - 1)$ ⁠. Then $d (Z R, Z S)$ is at most 3 if n = 3 or at most 2 otherwise.

Proof.

(i) This holds since $C (x^{n} - 1)^{- 1} = C (x^{n} - 1)^{T}$ and $det (C (x^{n} - 1)) = 1$ ⁠.

(ii) We may assume that $R = C (x^{n} - 1)$ ⁠. If q is odd, then let A be the direct sum of the matrices $I_{n - 2}$ and $- I_{2}$ ⁠, so that the (1, 1) and (n, n) entries of $[R, A]$ are equal to −1 and 1, respectively. If instead q is even, then let $A \in H$ be the direct sum of the matrices $I_{n - 2}$ and

(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix})

⁠, so that the (1, 1) entry of

[R, A]

is equal to 0. In either case,

[R, A] \notin Z

⁠. Moreover, R and A are monomial, and so

⟨ R, A, Z ⟩ < H

⁠. Thus

Z R \sim Z A

⁠. As A is an involution, so is

Z A

⁠.

(iii) We may assume that $R = C (x^{n} - 1)$ and $d (Z R, Z S) > 1$ ⁠. Then R stabilizes the one-dimensional subspace X of V spanned by the all-ones vector. Let $F \in H$ such that $S = R^{F}$ ⁠, and let $L := H_{X}$ ⁠, so that $R \in L$ and $S \in L^{F}$ ⁠. Additionally, let $L_{0} := H_{⟨ e_{1} ⟩}$ ⁠. It is easy to show that $C_{L_{0}} (R) = Z$ ⁠, and thus $C_{L_{0}^{F}} (S) = Z$ ⁠. Furthermore, as $Z ⩽ L$ and L < H, it follows from Lemma 4.4(i) that if $[R, A] \neq 1$ for some $A \in L$ ⁠, then $Z R \sim Z A$ ⁠. Similarly, if $[S, D] \neq 1$ for some $D \in L^{F}$ ⁠, then $Z S \sim Z D$ ⁠. We split the remainder of the proof into three cases.

Case (a): $n ⩾ 7$ ⁠, or n = 5 and $q \neq 4$ ⁠. By Theorem 4.5, the pointwise stabilizer $L \cap L^{F} \cap L_{0} \cap L_{0}^{F}$ in H of ${X, X^{F}, ⟨ e_{1} ⟩, ⟨ e_{1} ⟩^{F}}$ contains a non-scalar matrix D. The previous paragraph shows that D centralizes neither R nor S, and in fact that $Z R \sim Z D \sim Z S$ ⁠.

Case (b): n = 5 and q = 4. Straightforward computations in Magma (with a runtime of about 1.5 h) show that $| L \cap L^{F} |$ is even (for all $F \in H$ ⁠), while $| C_{H} (R) | = 625$ (and hence $| C_{H} (S) | = 625$ ⁠). It follows from the second last paragraph that $Z R \sim Z D \sim Z S$ for each involution $D \in L \cap L^{F}$ ⁠.

Case (c): n = 3. For each $i \in {1, 2, 3}$ ⁠, define $B_{i} \in H ∖ Z$ as in Lemma 5.5. It is easy to check that $[R, B_{i}] \notin Z$ ⁠, and since $Z$ ⁠, R and B_i are monomial matrices, $⟨ Z, R, B_{i} ⟩ < H$ ⁠. Thus $Z R \sim Z B_{i}$ ⁠. Similarly, $Z S \sim Z B_{i}^{F}$ ⁠. Recall also from Lemma 5.5(ii)–(iii) that $⟨ B_{i}, B_{1}^{F} ⟩$ stabilizes a one-dimensional subspace of V. Hence, as in the third last paragraph, if $[B_{i}, B_{1}^{F}] \neq 1$ for some i, then $Z B_{i} \sim Z B_{1}^{F}$ ⁠, and so $Z R \sim Z B_{i} \sim Z B_{1}^{F} \sim Z S$ ⁠. Otherwise, Lemma 5.5(iv) yields $B_{1}^{F} = B_{i}$ for some i, and so $Z R \sim Z B_{i} \sim Z S$ ⁠.

Proof of Theorem 5.4

(i) Let $x, y \in G ∖ Z (G)$ ⁠. We will show that $d (x, y) ⩽ 5$ ⁠. By Proposition 2.2, each of x and y is non-central in some maximal subgroup. Using Lemma 2.5, we may assume that each maximal subgroup K of G with $x \in K ∖ Z (K)$ has odd order. By [35, Theorem 2], $K = N_{H} (S) / Z$ ⁠, where S is a Singer subgroup of H, that is, the intersection of H and a Singer subgroup of $GL (n, q^{2})$ ⁠. It follows from [30, p. 497 and p. 512] that $N_{H} (S) = S : ⟨ C ⟩$ for some H-conjugate C of $C (x^{n} - 1)$ ⁠.

Now, by Lemma 5.6(ii), $Z C \sim r$ for some involution $r \in G$ ⁠, and so $Z C, r \in L ∖ Z (L)$ for some maximal subgroup L of G of even order. As $| C | = n$ is prime, each non-identity element of $⟨ Z C ⟩$ lies in $L ∖ Z (L)$ ⁠. Since $Z ⩽ S$ ⁠, it follows that $x = Z A C^{i}$ for some $A \in S ∖ Z$ and some $i \in {0, 1, \dots, n - 1}$ ⁠. Again using the fact that n is prime, it follows from Clifford’s Theorem that $⟨ A ⟩$ acts irreducibly on $F_{q^{2}}^{n}$ ⁠. Similar to Case (b) in the proof of Lemma 5.3 (but now working over $F_{q^{2}}$ ⁠), we see that $[A, C] = A^{q^{2} - 1}$ ⁠. By Lemma 4.3, $A^{q^{4} - 1} \notin Z$ ⁠, and so $[A, C] \notin Z$ ⁠. Moreover, $⟨ A, C, Z ⟩ ⩽ N_{H} (S) < H$ ⁠. Therefore, $Z A \sim Z C$ ⁠. It is now easy to see that $Z A C^{i} \sim Z C$ for all i, and, in particular, $x \sim Z C$ ⁠.

If $y \in M ∖ Z (M)$ for some maximal subgroup M of G of even order, then since $Z C \sim r$ and $| r | = 2$ ⁠, Lemma 2.5 shows that $d (Z C, y) ⩽ 4$ ⁠. Hence $d (x, y) ⩽ 5$ ⁠. Otherwise, y lies in a G-conjugate of $N_{H} (S) / Z$ ⁠. By the previous paragraph, $y \sim Z D$ for some H-conjugate D of C. Since $x \sim Z C$ and $d (Z C, Z D) ⩽ 3$ by Lemma 5.6(iii), we again obtain $d (x, y) ⩽ 5$ ⁠.

(ii) By [20, Remark 1.3] (see also [21, Ch. 4]), the intersection graph of G has diameter 5. Thus $diam (Ξ (G)) ⩾ 4$ by Lemma 2.3. It remains to show that $d (x, y) ⩽ 4$ for all $x, y \in G ∖ {1}$ ⁠. In what follows, except where stated otherwise, all information about G is determined using Magma, via computations involving conjugacy classes of elements and subgroups of G, with a runtime of about 2 min.

If $| x |, | y | \neq 43$ ⁠, then each of x and y is adjacent in $Ξ (G)$ to an involution, and Lemma 2.5 yields $d (x, y) ⩽ 4$ ⁠. Assume from now on that $| x | = 43$ ⁠. Then x lies in no maximal subgroup of G of even order. As in the proof of (i), $x \sim t$ ⁠, where t is the image in G of some H-conjugate of $C (x^{7} - 1)$ ⁠. Since n > 3, it follows from Lemma 5.6(iii) that if $| y | = 43$ ⁠, then $d (x, y) ⩽ 4$ ⁠.

Suppose finally that $| y | \neq 43$ ⁠, and let $T := ⟨ t ⟩$ ⁠. Then there exist maximal subgroups K and L of G such that $y \in K ∖ Z (K)$ ⁠, $t \in L ∖ Z (L)$ and either

$| K \cap L | > | C_{G} (t) | + | Z (K) |$ ⁠; or
$Z (K) = 1$ ⁠, $C_{L} (t) = T$ ⁠, $T \cap K = 1$ and $| K | | L | > | G |$ ⁠.

In case (I), there exists an element $f \in K \cap L$ that centralizes neither t nor K. Hence $t \sim f$ ⁠, and $d (f, y) ⩽ 2$ by Lemma 2.1, yielding $d (t, y) ⩽ 3$ ⁠. In case (II), we observe that $K \cap L > 1$ and that $t \sim w$ for each non-identity $w \in K \cap L$ ⁠. As $d (w, y) ⩽ 2$ by Lemma 2.1, we again obtain $d (t, y) ⩽ 3$ ⁠. We conclude in general that $d (x, y) ⩽ d (x, t) + d (t, y) ⩽ 4$ ⁠.

Using Magma, we observe that the non-commuting, non-generating graphs of $PSU (3, 3)$ ⁠, $PSU (3, 4)$ and $PSU (4, 2)$ have diameters 2, 2 and 3, respectively.

5.3. The non-generating graph of a non-abelian finite simple group

Proof of Theorem 1.7

Let $x, y \in G ∖ {1}$ ⁠, and let M₁ and M₂ be maximal subgroups of G containing x and y, respectively. If $| M_{1} |$ and $| M_{2} |$ are even, then $⟨ a, b ⟩$ is dihedral for involutions $a \in M_{1}$ and $b \in M_{2}$ ⁠. Hence $(x, a, b, y)$ contains a path from x to y in $\overset{―}{Γ} (G)$ ⁠, and $d (x, y) ⩽ 3$ ⁠. Thus we are done if every maximal subgroup of G has even order.

Assume now that $| M_{1} |$ is odd. Since $Ξ (G)$ is a spanning subgraph of $\overset{―}{Γ} (G)$ ⁠, it follows from Theorems 2.6 and 1.1 that if G is not unitary of odd prime dimension, then $diam (\overset{―}{Γ} (G))$ is at most 5 if $G = M$ ⁠, and at most 4 otherwise.

Suppose therefore that $G = PSU (n, q)$ ⁠, with n being an odd prime. As in the proof of Theorem 5.4, M₁ is the image in G of the subgroup $S : ⟨ C ⟩$ of $SU (n, q)$ ⁠, with S being a Singer subgroup of $SU (n, q)$ and C being a conjugate of the companion matrix $C (x^{n} - 1)$ ⁠. By Lemma 5.6(ii), there exists an involution $a \in G$ such that the image c of C in G is adjacent to a in $Ξ (G)$ ⁠, and hence in $\overset{―}{Γ} (G)$ ⁠.

Now, if M₂ contains an involution b, then $(x, c, a, b, y)$ contains a path from x to y in $\overset{―}{Γ} (G)$ and $d (x, y) ⩽ 4$ ⁠. Otherwise, by the previous paragraph, $y \sim c^{'}$ for some G-conjugate cʹ of c. Moreover, c and cʹ stabilize one-dimensional subspaces X and Xʹ, respectively, of $F_{q^{2}}^{n}$ ⁠. Since $q \neq 2$ when n = 3, we deduce from Theorem 4.5 that $G_{X} \cap G_{X^{'}}$ contains an element $t \neq 1$ ⁠. Hence $(x, c, t, c^{'}, y)$ contains a path from x to y in $\overset{―}{Γ} (G)$ and $d (x, y) ⩽ 4$ ⁠. Therefore, $diam (\overset{―}{Γ} (G)) ⩽ 4$ ⁠.

It remains to determine lower bounds for $diam (\overset{―}{Γ} (G))$ when $G \in {B, PSU (7, 2), M}$ ⁠. Here, [20, Theorem 1.1 and Remark 1.3] and Proposition 3.10 show that the intersection graph of G is connected with diameter at least 5, and so Lemma 2.3 yields $diam (\overset{―}{Γ} (G)) ⩾ 4$ ⁠.

Acknowledgements

The author is grateful to Colva Roney-Dougal and Peter Cameron for helpful discussions regarding the original thesis on which this work is based and to Colva and anonymous referees for their useful comments on this paper.

Funding

This work was supported by the University of St Andrews (St Leonard’s International Doctoral Fees Scholarship and School of Mathematics and Statistics PhD Funding Scholarship) and EPSRC grant number EP/W522422/1.

References

Abdollahi

Akbari

and

H. R.

Maimani

Non-commuting graph of a group

J. Algebra

298

(

2006

468

–

492

Month:	Total Views:
January 2025	39
February 2025	96
March 2025	52
April 2025	52

Article Contents

The non-commuting, non-generating graph of a finite simple group

ABSTRACT

1. INTRODUCTION

2. PRELIMINARIES

2.1. The non-commuting, non-generating graph

2.2. Maximal subgroups of non-abelian finite simple groups

3. ALTERNATING, SPORADIC AND EXCEPTIONAL SIMPLE GROUPS

3.1. Alternating groups

3.2. Sporadic groups

3.3. Exceptional groups of Lie type

4. Matrices and subspace stabilizers

4.1. Matrices and subspace stabilizers in linear groups

([39, p. 148 & pp. 161–162])

4.2. Subspace stabilizers in unitary groups

5. LINEAR AND UNITARY GROUPS AND THE NON-GENERATING GRAPH

5.1. Linear groups

5.2. Unitary groups

5.3. The non-generating graph of a non-abelian finite simple group

Proof of Theorem 1.7

Acknowledgements

Funding

References

Citations

Views

Altmetric

Email alerts

Citing articles via

Latest

Most Read

Most Cited

This Feature Is Available To Subscribers Only