ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P1.07 / 115–120
https://doi.org/10.26493/1855-3974.2558.173
(Also available at http://amc-journal.eu)
Oriented regular representations of out-valency
two for finite simple groups*
Gabriel Verret
Department of Mathematics, University of Auckland, PB 92019, Auckland, New Zealand
Binzhou Xia †
School of Mathematics and Statistics, University of Melbourne,
Parkville, VIC 3010, Australia
Received 16 February 2021, accepted 17 June 2021, published online 5 April 2022
Abstract
In this paper, we show that every finite simple group of order at least 5 admits an
oriented regular representation of out-valency 2.
Keywords: Finite simple group, DRR, ORR.
Math. Subj. Class. (2020): 05C25, 05C20, 20B25
1 Introduction
All groups and digraphs in this paper are finite. A digraph Γ consists of a set of vertices
V(Γ) and a set of arcs A(Γ), each arc being an ordered pair of vertices. A digraph is proper
if (u, v) being an arc implies that (v, u) is not an arc. The automorphisms of Γ are the
permutations of V(Γ) that preserve A(Γ). Under composition, they form the automorphism
group Aut(Γ) of Γ.
Let G be a group and S ⊆ G. The Cayley digraph Cay(G,S) on G with connection set
S is the digraph with vertex set G and (u, v) being an arc whenever vu−1 ∈ S. Note that
Cay(G,S) is a proper digraph if and only if S ∩ S−1 = ∅. Note also that every vertex u in
Cay(G,S) is contained in exactly |S| arcs of the form (u, v). We thus say that Cay(G,S)
has out-valency |S|.
It is easy to see that Aut(Cay(G,S)) contains the right regular representation of G.
If this containment is actually equality, then Cay(G,S) is called a digraphical regular
*The authors are grateful to the N.Z. Marsden Fund which helped support (via grant UOA1824) the second
author’s visit to the University of Auckland in 2019.
†Corresponding author.
E-mail addresses: g.verret@auckland.ac.nz (Gabriel Verret), binzhoux@unimelb.edu.au (Binzhou Xia)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
116 Ars Math. Contemp. 22 (2022) #P1.07 / 115–120
representation (or DRR) of G. A DRR that is a proper digraph is called an oriented regular
representation (or ORR).
Babai proved that, apart from five small groups, all groups admit a DRR [1, Theo-
rem 2.1]. He also asked which groups admit ORRs [1, Problem 2.7]. This was answered
by Morris and Spiga [9, 10, 12] who showed that apart from generalised dihedral groups
and a small list of exceptions, all groups admit ORRs.
In view of the above, a natural problem is to find “nice” DRRs and ORRs, say of “small”
out-valency. Clearly, only cyclic groups can have DRRs of out-valency 1, so out-valency 2
is the smallest interesting case. In this paper, we give the most satisfactory answer to this
question in the case of simple groups.
Theorem 1.1. Every finite simple group of order at least 5 has a ORR of out-valency 2.
A corollary of Theorem 1.1 is that every nonabelian simple group has a DRR of out-
valency 2. However, the latter conclusion is an immediate consequence of the fact that
every nonabelian simple group is generated by an involution and a non-involution (even
by an involution and an element of odd prime order, see [8, Theorem 1]. Indeed, consider
a Cayley digraph on a nonabelian simple group with connection set consisting of such a
generating pair. This digraph has out-valency 2, but one out-neighbour of every vertex is
also an in-neighbour while the other out-neighbour is not. This implies that fixing a vertex
must also fix its out-neighbours and, by connectedness, the whole digraph, and the digraph
is a DRR.
Note that Cayley digraphs of out-valency two of simple groups were previously studied
in [4]. Another interesting variant of this question would be to consider undirected graphs.
In this case, the smallest interesting valency is 3. The question of which simple groups
admit graphical regular representations of valency 3 has received some attention but is still
open [11, 13, 14, 15].
2 Preliminaries
2.1 Generation of finite simple groups
In this section we present some generation properties of finite simple groups, which will be
needed in the proof of Theorem 1.1. The following result is due to Guralnick and Kantor [7,
Corollary].
Theorem 2.1 (Guralnick-Kantor). Every nontrivial element of a finite simple group be-
longs to a pair of elements generating the group.
Note that Theorem 2.1 depends on the classification of finite simple groups.
Corollary 2.2. Let G be a finite nonabelian simple group with an element x of order 3.
Then there exists y ∈ G such that |y| ≥ 4 and G = ⟨x, y⟩.
Proof. By Theorem 2.1 there exists z ∈ G such that G = ⟨x, z⟩. Note that ⟨x, z⟩ = ⟨x, xz⟩
hence, if either z or xz has order at least 4, then the conclusion holds (by taking y = z or
y = xz). We may thus assume that z and xz both have order at most 3. This implies that
G is a quotient of the finitely presented group
⟨x, z | x3, zm, (xz)n⟩
G. Verret and B. Xia: Oriented regular representations of out-valency two for finite simple groups 117
with m,n ≤ 3. This is the “ordinary” (3,m, n) triangle group which is well known to be
solvable when m,n ≤ 3 (see for example [3]) and therefore so is G, which is a contradic-
tion.
The only nonabelian simple groups with no elements of order 3 are the Suzuki groups
(see [6, Page 8, Table I]), which we now consider. For a positive integer m and prime
number p, a prime number r is called a primitive prime divisor of pm − 1 if r divides
pm − 1 but does not divide pk − 1 for any positive integer k < m. By Zsigmondy’s
theorem [17], pm − 1 has a primitive prime divisor whenever m ≥ 3 and (p,m) ̸= (2, 6).
Proposition 2.3. Let G = Sz(q) with q = 22n+1 ≥ 8 and let r be a primitive prime divisor
of q4 − 1. Then r ≥ 5, G has an element y of order r and, for each such y, there exists
x ∈ G such that |x| = 4, |xy| ≥ 3 and G = ⟨x, y⟩.
Proof. First, recall that |G| = q2(q2 + 1)(q − 1) (see [6, Page 8, Table I]). Since r is a
primitive prime divisor of q4 − 1, it divides q4 − 1 but not q2 − 1 and thus must divide
q2+1. It follows that G has an element y of order r and that r ≥ 5. We will now prove that
there exists an element x of order 4 with the required properties, essentially by a somewhat
crude counting argument.
We denote by Eq the elementary abelian group of order q and, for an integer n ≥ 2, by
Cn the cyclic group of order n and D2n the dihedral group of order 2n.
Up to conjugation, the maximal subgroups of G are the following (see for instance [2,
Table 8.16]):
• (Eq.Eq)⋊ Cq−1,
• D2(q−1),
• Cq+√2q+1 ⋊ C4,
• Cq−√2q+1 ⋊ C4,
• Sz(q0), where q0 = q1/d > 2 for some prime divisor d of 2n+ 1.
Recall that r is odd, does not divide q − 1 nor q40 − 1 and thus does not divide its factor
(q20 + 1)(q0 − 1). This implies that r does not divide |Sz(q0)| = q20(q20 + 1)(q0 − 1). It
follows that a maximal subgroup M of G containing y must be of the form Cq±√2q+1⋊C4.
Since every subgroup of a cyclic group is characteristic, ⟨y⟩ is normal in M and thus M
is the only maximal subgroup of G containing y (for otherwise ⟨y⟩ would be normal in
another maximal subgroup N of G and thus normal in ⟨M,N⟩ = G).
Let Q be a Sylow 2-subgroup of G. Then Q = Eq.Eq and |NG(Q)| = (Eq.Eq)⋊Cq−1.
Hence the number n of Sylow 2-subgroups of G is
n =
|G|
|NG(Q)|
=
q2(q2 + 1)(q − 1)
q2(q − 1)
= q2 + 1.
Let n2 and n4 denote the numbers of elements of order 2 and 4, respectively, in G. Ac-
cording to [5, Lemma 3.2], there are q− 1 involutions and q2 − q elements of order 4 in Q,
and different conjugates of Q have trivial intersection. Then
n2 = n(q − 1) = (q2 + 1)(q − 1)
and
n4 = n(q
2 − q) = (q2 + 1)(q2 − q).
118 Ars Math. Contemp. 22 (2022) #P1.07 / 115–120
Let
I = {g ∈ G : |gy| ≤ 2}
and
J = {g ∈ G : ⟨g, y⟩ ≠ G}.
Then |I| = n2 + 1 and, since M is the unique maximal subgroup of G containing y,
|J | ≤ |M |. Since
|I|+ |J | ≤ n2 + |M |+ 1
= (q2 + 1)(q − 1) + 4(q ±
√
2q + 1) + 1
≤ (q2 + 1)(q − 1) + 4(q +
√
2q + 1) + 1
< (q2 + 1)(q2 − q) = n4,
it follows that there exists x ∈ G with |x| = 4 and x /∈ I ∪ J , as required.
2.2 Constructing ORRs of out-valency 2
Lemma 2.4. Let G = ⟨x, y⟩. If |x| = 3 and |y| ≥ 4, then Cay(G, {x, y}) is an ORR,
unless |y| = 6 and x = y4, and G ∼= C6.
Proof. Let Γ = Cay(G, {x, y}) and let A = Aut(Γ). Note that Γ is a strongly connected
proper digraph. Figure 1 shows all the directed paths of length at most 3 in Γ starting at 1.
1
x
y
x2
yx
y2
xy
x3
yx2
xyx
y2x
y3
xy2
yxy
x2y
Figure 1: All the directed paths of length at most 3 in Cay(G, {x, y}).
Since |y| ≥ 4, we have y3 ̸= 1 and y ̸= x−2. Moreover, if y2 = x−1, then |y| = 6 and
thus x = y4 and the result holds. We thus assume this is not the case. Since x3 = 1, this
implies that (1, x, x2, x3) is the only directed cycle of length 3 starting at 1. This implies
that the stabiliser A1 of the vertex 1 also fixes x. As 1 only has one out-neighbour other
than x, it must also be fixed. By vertex-transitivity, we find that fixing a vertex fixes its out
neighbours and, using connectedness, we conclude that A1 = 1 and thus Γ is an ORR.
Lemma 2.5. Let G = ⟨x, y⟩. If |x| = 4, |y| ≥ 5 and |xy| ≥ 3, then Cay(G, {x, y}) is an
ORR, unless |y| = 12 and x = y9, and G ∼= C12.
G. Verret and B. Xia: Oriented regular representations of out-valency two for finite simple groups 119
Proof. Let Γ = Cay(G, {x, y}) and let A = Aut(Γ). Note that Γ is a strongly connected
proper digraph. Figure 2 shows all the directed paths of length at most 4 in Γ starting at 1.
1
x
y
x2
yx
y2
xy
x3
yx2
xyx
y2x
y3
xy2
yxy
x2y
x4
yx3
xyx2
y2x2
x2yx
yxyx
xy2x
y3x
y4
xy3
yxy2
x2y2
y2xy
xyxy
yx2y
x3y
Figure 2: All the directed paths of length at most 4 in Cay(G, {x, y}).
Since |y| ≥ 5, we have y4 ̸= 1, y ̸= x−3 and y2 ̸= x−2. Similarly, |xy| ≥ 3 implies
that (xy)2 ̸= 1 ̸= (yx)2. Moreover, if y3 = x−1, then |y| = 12 and thus x = y9 and
the result holds. We thus assume this is not the case. Since x4 = 1, this implies that
(1, x, x2, x3, x4) is the only directed cycle of length 4 starting at 1 and, as in the previous
lemma, Γ is an ORR.
3 Proof of Theorem 1.1
Let G be a finite simple group with |G| ≥ 5. We first suppose that G = F+p for some prime
p ≥ 5. Let x, y ∈ Fp \ {0} such that x ̸= ±y and let Γ = Cay(G, {x, y}). Note that Γ is
a proper digraph of out-valency 2. By [16, Proposition 1.3 and Example 2.2], Γ is an ORR
if and only if the only solution to
{λx, λy} = {x, y} (3.1)
with λ ∈ F×p is λ = 1. Suppose otherwise, that is (3.1) holds with λ ̸= 1. This implies that
λx = y and λy = x, which yields that
λx2 = (λx)x = y(λy) = λy2,
and hence x2 = y2, contradicting x ̸= ±y. Thus we conclude that Γ is an ORR, as
required.
We may now assume that G is nonabelian. If G has an element x of order 3 then,
by Corollary 2.2 there exists y ∈ G such that |y| ≥ 4 and G = ⟨x, y⟩. By Lemma 2.4,
Cay(G, {x, y}) is an ORR. We may thus assume that G does not have an element of order
120 Ars Math. Contemp. 22 (2022) #P1.07 / 115–120
3 and thus G = Sz(q) for some q = 22n+1 ≥ 8. Let r be a primitive prime divisor of
q4 − 1. By Proposition 2.3, G contains elements x and y such that |x| = 4, |y| = r ≥ 5,
|xy| ≥ 3 and G = ⟨x, y⟩. By Lemma 2.5, Cay(G, {x, y}) is an ORR.
ORCID iDs
Gabriel Verret https://orcid.org/0000-0003-1766-4834
Binzhou Xia https://orcid.org/0000-0002-8031-2981
References
[1] L. Babai, Finite digraphs with given regular automorphism groups, Period. Math. Hungar. 11
(1980), 257–270, doi:10.1007/bf02107568.
[2] J. N. Bray, D. F. Holt and C. M. Roney-Dougal, The Maximal Subgroups of the Low-
Dimensional Finite Classical Groups, volume 407 of London Mathematical Society Lecture
Note Series, Cambridge University Press, Cambridge, 2013, doi:10.1017/cbo9781139192576.
[3] M. D. E. Conder, Some results on quotients of triangle groups, Bull. Austral. Math. Soc. 30
(1984), 73–90, doi:10.1017/s0004972700001738.
[4] X.-G. Fang, Z.-P. Lu, J. Wang and M.-Y. Xu, Cayley digraphs of finite simple groups with small
out-valency, Comm. Algebra 32 (2004), 1201–1211, doi:10.1081/agb-120027974.
[5] X. G. Fang and C. E. Praeger, Finite two-arc transitive graphs admitting a Suzuki simple group,
Comm. Algebra 27 (1999), 3727–3754, doi:10.1080/00927879908826659.
[6] D. Gorenstein, R. Lyons and R. Solomon, The Classification of the Finite Simple Groups, vol-
ume 40 of Mathematical Surveys and Monographs, American Mathematical Society, Provi-
dence, RI, 1994, doi:10.1090/surv/040.1.
[7] R. M. Guralnick and W. M. Kantor, Probabilistic generation of finite simple groups, J. Algebra
234 (2000), 743–792, doi:10.1006/jabr.2000.8357.
[8] C. S. H. King, Generation of finite simple groups by an involution and an element of prime
order, J. Algebra 478 (2017), 153–173, doi:10.1016/j.jalgebra.2016.12.031.
[9] J. Morris and P. Spiga, Every finite non-solvable group admits an oriented regular representa-
tion, J. Comb. Theory Ser. B 126 (2017), 198–234, doi:10.1016/j.jctb.2017.05.003.
[10] J. Morris and P. Spiga, Classification of finite groups that admit an oriented regular representa-
tion, Bull. Lond. Math. Soc. 50 (2018), 811–831, doi:10.1112/blms.12177.
[11] P. Spiga, Cubic graphical regular representations of finite non-abelian simple groups, Comm.
Algebra 46 (2018), 2440–2450, doi:10.1080/00927872.2017.1383997.
[12] P. Spiga, Finite groups admitting an oriented regular representation, J. Comb. Theory Ser. A 153
(2018), 76–97, doi:10.1016/j.jcta.2017.08.001.
[13] B. Xia, Cubic graphical regular representations of PSL3(q), Discrete Math. 343 (2020),
111646 (9 pages), doi:10.1016/j.disc.2019.111646.
[14] B. Xia, On cubic graphical regular representations of finite simple groups, J. Comb. Theory Ser.
B 141 (2020), 1–30, doi:10.1016/j.jctb.2019.06.002.
[15] B. Xia and T. Fang, Cubic graphical regular representations of PSL2(q), Discrete Math. 339
(2016), 2051–2055, doi:10.1016/j.disc.2016.03.008.
[16] M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182
(1998), 309–319, doi:10.1016/s0012-365x(97)00152-0.
[17] K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math. Phys. 3 (1892), 265–284, doi:
10.1007/bf01692444.