ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 89–102
https://doi.org/10.26493/1855-3974.2154.cda
(Also available at http://amc-journal.eu)
Graphical Frobenius representations
of non-abelian groups*
Gábor Korchmáros
Dipartimento di Matematica, Informatica ed Economia, Università della Basilicata,
Contrada Macchia Romana, 85100 Potenza, Italy
Gábor P. Nagy
Department of Algebra, Budapest University of Technology and Economics,
Egry József utca 1, H-1111 Budapest, Hungary, and
Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, H-6720 Szeged, Hungary
Received 14 October 2019, accepted 19 October 2020, published online 18 August 2021
Abstract
A group G has a Frobenius graphical representation (GFR) if there is a simple graph Γ
whose full automorphism group is isomorphic to G acting on the vertices as a Frobenius
group. In particular, any group G with a GFR is a Frobenius group and Γ is a Cayley
graph. By very recent results of Spiga, there exists a function f such that if G is a finite
Frobenius group with complement H and |G| > f(|H|) then G admits a GFR. This paper
provides an infinite family of graphs that admit GFRs despite not meeting Spiga’s bound.
In our construction, the group G is the Higman group A(f, q0) for an infinite sequence of
f and q0, having a nonabelian kernel and a complement of odd order.
Keywords: Cayley graph, Frobenius group, Suzuki 2-group, Frobenius graphical representation.
Math. Subj. Class. (2020): 20B25, 05C25
1 Introduction
Graphs and their automorphism groups have intensively been investigated especially for
vertex-transitive (and hence regular) graphs. Many contributions have concerned vertex-
transitive graphs with large automorphism groups compared to the degree of the graph, and
have in several cases relied upon deep results from group theory, such as the classification
of primitive permutation groups.
On the other end, the smallest vertex-transitive automorphism groups of graphs occur
*Support provided by NKFIH-OTKA Grants 114614, 115288 and 119687.
E-mail addresses: gabor.korchmaros@unibas.it (Gábor Korchmáros), nagyg@math.bme.hu (Gábor P. Nagy)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
90 Ars Math. Contemp. 20 (2021) 89–102
when the group is regular on the vertex-set. A group is said to have a graphical regular rep-
resentation (GRR) if there exists a graph whose (full) automorphism group is isomorphic to
G acting regularly on the vertex-set. Actually, almost all finite groups have GRRs. In fact,
all the few exceptions were found in the 1970-80s by a common effort of G. Sabidussi,
W. Imrich, M. E. Watkins, L. A. Nowitz, D. Hetzel, C. D. Godsil, and L. Babai, see [2,
Section 1]. Since regular automorphism groups of a graph are those which are vertex tran-
sitive but contain no non-trivial automorphism fixing a vertex, a natural next choice as a
small vertex-transitive automorphism group of a graph may be a Frobenius group on the
vertex-set: an automorphism group of a graph that is vertex-transitive but not regular and
only the identity fixes more than one vertex. It is well known that any group may be a
Frobenius group in at most one way. Furthermore, each graph Γ with a (sub)group G of
automorphisms acting regularly on the vertex-set is a Cayley graph Cay(G,S).
All these give a motivation for the study of Frobenius groups G which have a graphical
Frobenius representation (GFR), that is, there exists a graph whose (full) automorphism
group is isomorphic to G acting on the vertex-set as a Frobenius group. The systematic
study of the GFR problem was initiated by J. K. Doyle, T. W. Tucker and M. E. Watkins in
their recent paper [2]. As pointed out by those authors, the GFR problem is largely not anal-
ogous to the GRR problem since all groups have a regular representation whereas Frobenius
groups have highly restricted algebraic structures. Nevertheless, they conjectured that like
the GRR-case, “all but finitely many Frobenius groups with a given Frobenius complement
have a GFR”. Very recently Spiga [9, 10] was able to prove that conjecture for Cayley
graphs and Cayley digraphs (digraphical Frobenius representations, or DFRs). Spiga com-
bined combinatorial properties of Cayley graphs with some deeper results on the 1-point
stabilizers of primitive permutation groups to obtain a function f : N → N such that if G
is a finite Frobenius group with complement H satisfying |G| > f(|H|), then G admits a
GFR; see [10, Theorem 1.1], [9, Theorem 1], and Section 9.
It is apparent from Spiga’s work and from the results, examples and classification of
smaller groups with GFRs in [2], see in particular [2, Theorem 5.3 and Remark 5.4], that
an interesting open problem is the explicit constructions of GFR for Frobenius groups G
which do not meet Spiga’s bound and whose kernel H is a non-abelian 2-group.
In this paper we provide such a construction. Our choice of Frobenius groups is in-
fluenced by Higman’s classification of Suzuki 2-groups [5], as we take for G the group
A(f, q0) from Higman’s list where q0 and q = 2f are 2-powers. The group A(f, q0) is a
subgroup of G of GL(3,Fq) whose main properties are recalled in Section 2. We build a
Cayley graph Γu on the Frobenius kernel K of G, with a certain inverse closed subset S of
K as connecting set, constructed from an element u ∈ Fq . We show that G has GFR on Γu
provided that q = 2f , q0 and u are carefully chosen.
Our notation and terminology are standard. For the definitions and known results on
Frobenius groups which play a role in the present paper, the reader is referred to [2].
2 The group A(f, q0)
Let Fq be the finite field of order q = 2f with f ≥ 4, and let q0 = 2f0 be another power of
2 smaller than q. For a, c ∈ Fq and λ ∈ F∗q , we write
Φa,c =
1 0 0a 1 0
c aq0 1
 , Ψλ =
1 0 00 λ 0
0 0 λq0+1
 .
G. Korchmáros and G. P. Nagy: Graphical Frobenius representations of non-abelian groups 91
We define the groups
K = {Φa,c | a, c ∈ Fq},
H = {Ψλ | λ ∈ F∗q}.
Then, K is a 2-group of order q2 and H is a cyclic group of order q − 1. Moreover,
H normalizes K, and its action fixes no nontrivial element in K. Their closure group is
HK, and denoted by A(f, q0) in Higman’s paper [5]. For brevity, we write G in place of
A(f, q0). With this change G = HK. Since H ∩Hg = 1 holds for any g ∈ G \H , G is
a Frobenius group in its action on the set G/H of right cosets of H . The point stabilizer
is H and K is a regular normal subgroup. It may be noticed that when q = 2q20 then G is
similar to the 1-point stabilizer of the Suzuki group Sz(q) in its double transitive action on
q2 + 1 points. A straightforward computation shows that the H-orbits on K are
Ωu = {Φa,uaq0+1 | a ∈ F∗q}, u ∈ Fq, (2.1)
and
Ω∞ = {Φ0,c | c ∈ F∗q}.
3 A Cayley graph arising from G
For every u ∈ Fq , we may build a Cayley graph in the usual way:
Γu = Cay(K,Ωu ∪ Ωu+1).
Since Ωu ∪ Ωu+1 is H-invariant, the group G induces automorphisms of Γu. This allows
us to look at (the matrix group) G as a Frobenius group on K = V (Γu). Our aim is to
show that if q, q0 and u ∈ Fq are carefully chosen then Aut(Γu) coincides with G. Define
the set Uq,q0 of elements u ∈ Fq which satisfy both conditions:
(U1) u = (1 + ηq0)/(η + ηq0) for some primitive element η of Fq;
(U2) the polynomial Xq0+1 + uXq0 + (u+ 1)X + 1 has no roots in Fq .
Then such an appropriate choice of the triple (q, q0, u) is given in the following theo-
rem.
Theorem 3.1. Assume that q − 1 and q20 − 1 are relatively prime. Then
(i) Γu is connected Cayley graph.
(ii) If, in addition, u ∈ Uq,q0 , then Aut(Γu) = G, that is, G has a graphical Frobenius
representation on Γu.
The question whether Theorem 3.1 provides an infinite family is also answered posi-
tively.
Theorem 3.2. For infinitely many 2-powers q it is true that whenever the 2-power q0 sat-
isfies gcd(q − 1, q20 − 1) = 1, the set Uq,q0 is not empty.
Computer calculations show that for many u ̸∈ Uq,q0 , the graph Γu is still a GFR for G.
Hence, the conditions (U1) and (U2) are only needed for our proofs. However, Uq,q0 = ∅
implies φ(q)/q ≤ 3, which happens extremely rarely for q = 2f , f odd; see Section 5.
92 Ars Math. Contemp. 20 (2021) 89–102
4 Some more properties of the abstract structure of the group G
Lemma 4.1. The following hold in K:
(i) Φ2a,c = Φ0,aq0+1 and Φ
−1
a,c = Φa,c+aq0+1 .
(ii) Φ−1a,cΦ
−1
b,dΦa,cΦb,d = Φ0,aq0b+abq0 .
(iii) Ω∞ consists of central involutions of K.
(iv) For each u ∈ Fq , we have Ω−1u = Ωu+1.
Proof. Straightforward matrix computation.
Lemma 4.2. Assume that gcd(q20 − 1, q − 1) = 1. Then the following hold:
(i) K ′ = Z(K) = {1} ∪ Ω∞.
(ii) K ′ and K/K ′ are elementary abelian 2-groups of order q.
(iii) For u ∈ Fq , the set Ωu generates K.
(iv) H acts transitively (hence irreducibly) on the nontrivial elements of K ′ and K/K ′.
(v) The subgroup H is maximal in HK ′, which is maximal in G.
Proof. By the assumption, the map a 7→ a + aq0 has kernel F2, and, a 7→ aq0+1 is a
bijection of F∗q . Hence, any element of Fq can be written in the form aq0b + abq0 , which
implies (i). For a ∈ F∗q , we have Φ2a,uaq0+1 = Φ0,aq0+1 . Thus, Ω∞ ⊆ ⟨Ωu⟩ and (iii)
follows. The rest is straightforward computation.
Notice that Lemma 4.2(iii) yields Theorem 3.1(i).
5 On Conditions (U1) and (U2)
A natural key question regarding the applicability of Theorem 3.1 is the existence of some
q such that Uq,q0 is not empty, that is, Fq contains an element u satisfying both Conditions
(U1) and (U2). Theorem 3.2 states that infinitely many such q exist and we are going to
show how to prove it using Euler’s phi function and the Möbius function. For this purpose,
we need some algebraic preparatory results stated in the next lemmas.
Lemma 5.1. Let q = 2f be a power of 2 with odd exponent f . There exist at least
2(q + 1)/3 elements u ∈ Fq such that Xq0+1 + uXq0 + (u+ 1)X + 1 has no roots in Fq .
Proof. Define the rational function
U(x) =
xq0+1 + x+ 1
xq0 + x
.
Clearly, 0 and 1 are never roots of Xq0+1 + uXq0 + (u + 1)X + 1. Moreover, Xq0+1 +
uXq0 + (u+ 1)X + 1 has a root in Fq if and only if u = U(x) for some x ∈ Fq \ {0, 1}.
Since U(0) = U(1) = ∞ and
U(x) = U
(
x+ 1
x
)
= U
(
1
x+ 1
)
identically, we have |U(Fq \ {0, 1})| ≤ (q − 2)/3. Here we use the fact that F4 is not a
subfield of Fq and x, (x+ 1)/x, 1/(x+ 1) are distinct elements of Fq .
G. Korchmáros and G. P. Nagy: Graphical Frobenius representations of non-abelian groups 93
Lemma 5.2. For infinitely many odd integers n, inequality φ(2n − 1)/(2n − 1) > 1/3
holds.
Proof. The claim follows from the asymptotic formula of [7, Theorem 3]
1
M
∑
1≤m≤M
φ(2m − 1)
2m − 1
= µ+O(M−1 logM),
with µ is given by the absolute convergent series
µ =
∑
d odd
µ(d)
dtd
≈ 0.73192,
where td is the multiplicative order of 2 modulo d, and µ(d) is the Möbius function; see
[11, Theorem 4.1].
We give a second, elementary proof based on Fermat’s Little Theorem. We show that
for primes p, φ(2p − 1)/(2p − 1) → 1. Let r1, . . . , rk be the different prime factors of
2p − 1. For i = 1, . . . , k, let mi be the order of 2 modulo ri. Then mi | p and p = mi.
Moreover, 2ri−1 ≡ 1 (mod ri) implies p | (ri−1). In fact, p | (ri−1)/2 and ri = 2sip+1
holds for some integer si ≥ 1. This implies
k < log2p(2
p − 1) < p
log2 p
.
Hence,
1 >
φ(2p − 1)
2p − 1
=
k∏
i=1
(
1− 1
ri
)
>
(
1− 1
2p
) p
log2 p
,
where the latter term converges to 1. This proves our claim.
Remark 5.3. As pointed out in [8], much more is true: [7] implies that given any ε > 0,
there is a c > 0 such that φ(2n − 1)/(2n − 1) > c apart from a set of n with upper density
< ε.
We are in a position to prove Theorem 3.2. By Lemma 5.2, it suffices to show that for
an arbitrary odd integer f with φ(2f − 1)/(2f − 1) > 1/3, q = 2f fulfills the conditions
of Theorem 3.2. Fix such an f and choose an arbitrary integer f0, coprime to f . Then
q0 = 2
f0 satisfies gcd(q − 1, q20 − 1) = 1. By the choice of f , Fq has more than (q − 1)/3
primitive elements. In our case, x 7→ xq0−1 is bijective in Fq , hence the maps
η 7→ η′ = 1 + η
q0
η + ηq0
, u 7→ u′ = 1 +
(
u
u+ 1
) 1
q0−1
are well-defined inverses to each other. Now, the claim follows from Lemma 5.1.
6 Incidences
Recall that Γu denotes the Cayley graph Cay(K,Ωu ∪Ωu+1), where the vertices of Γu are
the elements of K and Ωu is defined in (2.1). The identity Φ0,0 of K will also be denoted
by ε. The group G = HK acts on K, the action is induced as follows: The elements of
94 Ars Math. Contemp. 20 (2021) 89–102
K act in the right regular action and the elements of H act by conjugation. In the sequel,
we identify G with its permutation action on K, whereby some caution is required since
for a subset X of K, the point-wise stabilizer of X in G and the centralizer of X in G are
in general different. As a permutation group, G is a subgroup of the automorphism group
Aut(Γu), and H is its cyclic subgroup of order q − 1, fixing ε and preserving both Ωu and
Ωu+1. Formally, ε is viewed as an element of Aut(Γu); nevertheless, we will also use the
notation id to denote the trivial automorphism of Aut(Γu).
For any two elements Φa,c, Φb,d ∈ K with Φa,cΦ−1b,d ∈ Ωu, we introduce the directed
edge notation Φa,c
u−→ Φb,d in Γu and we refer to it as a u-edge. It should be noticed
that our notation is not the usual one for Cayley digraphs, where the arrows point in the
opposite direction. An obvious observation is that the following are equivalent:
(i) Φa,c
u−→ Φb,d,
(ii) Φa,cΦ−1b,d ∈ Ωu,
(iii) c+ d = (a+ b)q0(ua+ (u+ 1)b),
(iv) c+ d = u(a+ b)q0+1 + aq0b+ bq0+1.
Now we collect some incidences in Γu which play a role in our proof.
Lemma 6.1. Assume gcd(q − 1, q20 − 1) = 1 and define
η = 1 +
(
u
u+ 1
) 1
q0−1
for u ∈ Fq \ {0, 1}. Then the following hold in Γu for a, b ̸= 0:
Φa,uaq0+1
u−→ Φb,ubq0+1 ⇐⇒ b =
a
η
, (6.1a)
Φa,uaq0+1
u+1−→ Φb,ubq0+1 ⇐⇒ b = aη, (6.1b)
Φa,(u+1)aq0+1
u−→ Φb,(u+1)bq0+1 ⇐⇒ b = a ·
η
1 + η
, (6.1c)
Φa,(u+1)aq0+1
u+1−→ Φb,(u+1)bq0+1 ⇐⇒ b = a ·
1 + η
η
, (6.1d)
Φa,uaq0+1
u−→ Φb,(u+1)bq0+1 ⇐⇒ b =
a
1 + η
, (6.1e)
Φa,uaq0+1
u+1−→ Φb,(u+1)bq0+1 ⇐⇒
(a
b
)q0+1
+ u
(a
b
)q0
+ (u+ 1)
(a
b
)
+ 1 = 0.
(6.1f)
Proof. (6.1a): Since Γu has no loops, we may assume a ̸= b.
Φa,uaq0+1
u−→ Φb,ubq0+1 ⇐⇒ uaq0+1 + ubq0+1 = (a+ b)q0(ua+ (u+ 1)b)
⇐⇒ 0 = (u+ 1)aq0b+ uabq0 + bq0+1
⇐⇒ 0 = (u+ 1)
(a
b
)q0
+ u
(a
b
)
+ 1
⇐⇒ 0 = (u+ 1)
(a
b
+ 1
)q0
+ u
(a
b
+ 1
)
G. Korchmáros and G. P. Nagy: Graphical Frobenius representations of non-abelian groups 95
⇐⇒
(a
b
+ 1
)q0−1
=
u
u+ 1
= (η + 1)q0−1
⇐⇒ a
b
= η.
Since (u + 1)-edges are reversed u-edges, we obtain (6.1b) by switching a and b in the
computation above. To show (6.1d), we replace u by u+ 1 and use the computation above
to obtain
Φa,(u+1)aq0+1
u+1−→ Φb,(u+1)bq0+1 ⇐⇒
(a
b
+ 1
)q0−1
=
u+ 1
u
=
(
1
1 + η
)q0−1
⇐⇒ a
b
=
η
1 + η
.
This proves (6.1c) by switching a and b. For (6.1e):
Φa,uaq0+1
u−→ Φb,(u+1)bq0+1 ⇐⇒ uaq0+1 + (u+ 1)bq0+1 = (a+ b)q0(ua+ (u+ 1)b)
⇐⇒ 0 = (u+ 1)aq0b+ uabq0
⇐⇒
(a
b
)q0−1
=
u
u+ 1
= (η + 1)q0−1
⇐⇒ a
b
= 1 + η.
Finally,
Φa,uaq0+1
u+1−→ Φb,(u+1)bq0+1 ⇐⇒ uaq0+1 + (u+ 1)bq0+1 = (a+ b)q0((u+ 1)a+ ub)
⇐⇒ 0 = aq0+1 + uaq0b+ (u+ 1)abq0 + bq0+1
⇐⇒ 0 =
(a
b
)q0+1
+ u
(a
b
)q0
+ (u+ 1)
(a
b
)
+ 1,
which shows (6.1f).
Our next step is to describe the structure of the neighborhood of the vertex ε in Γu.
For this purpose, we recall the concept of generalized Petersen graphs [3]. Let n and k be
integers with 1 ≤ k < n/2, the vertex set of GPG(n, k) is {c1, . . . , cn, c′1, . . . , c′n} and
the edge set consists of all pairs of the form
cici+1, cic
′
i, cic
′
i+k, i ∈ {1, . . . , n},
where all subscripts are to be read modulo n. In order to describe the automorphism group
of GPG(n, k), define the permutations
ρ : ci 7→ ci+1, c′i 7→ c′i+1,
δ : ci 7→ c−i, c′i 7→ c′−i,
α : ci 7→ c′ki, c′i 7→ cki
for all i ∈ {1, . . . , n}. By [3, Theorem 1 and 2],
⟨ρ, δ⟩ ≤ Aut(GPG(n, k)) ≤ ⟨ρ, δ, α⟩
96 Ars Math. Contemp. 20 (2021) 89–102
provided that n ̸∈ {4, 5, 8, 10, 12, 24}. Moreover, the generators ρ, δ, satisfy the relations
ρn = δ2 = id, δρδ = ρ−1, hence, ⟨ρ, δ⟩ is isomorphic to the dihedral group of order
2n. Also, αδ = δα, α2 ∈ {id, δ}, and most importantly α−1ρα = ρk. This implies the
following lemma:
Lemma 6.2. Let n be an odd integer, n ̸= 5, and 1 ≤ k < n. In Aut(GPG(n, k)), the
following properties hold:
(i) The elements of odd order form a unique cyclic normal subgroup of order n.
(ii) For k ̸= ±1, no involution commutes with the cyclic normal subgroup of order n.
Proposition 6.3. Assume gcd(q − 1, q20 − 1) = 1 and u ∈ Uq,q0 . Then, the neighborhood
Ωu ∪ Ωu+1 of ε in Γu is isomorphic to the generalized Petersen graph GPG(q − 1, k),
where u = (1 + ηq0)/(η + ηq0) and the integer k is defined by 1 + η = ηk+1.
Proof. By the choice of u, η is a primitive element of Fq . Define
ci = Φηi,uηi(q0+1) , c
′
i = Φηi/(1+η),(u+1)(ηi/(1+η))q0+1 .
From Lemma 6.1, cici+1, cic′i are edges and there are no more edges in Ωu and between
Ωu and Ωu+1. In Ωu+1, c′i and c
′
j are connected with an u-edge if and only if
ηj
1 + η
=
ηi
1 + η
· 1 + η
η
⇐⇒ ηj−i+1 = 1 + η = ηk+1 ⇐⇒ j ≡ i+ k (mod q − 1).
This finishes the proof.
Notice that k = ±1 would imply η = 0 or 1 + η + η2 = 0, which is not possible if
gcd(q − 1, q20 − 1) = 1 and η generates F∗q .
Corollary 6.4. Assume gcd(q − 1, q20 − 1) = 1 and u ∈ Uq,q0 . Let A be the permutation
group induced by the stabilizer Aut(Γu)ε on Ωu ∪ Ωu+1. Then A is solvable, its order is
either (q − 1), 2(q − 1) or 4(q − 1), and it has a unique cyclic normal subgroup of odd
order q − 1. Moreover, Aut(Γu)ε either preserves Ωu and Ωu+1, or it interchanges them.
Proof. A contains the cyclic subgroup of order q − 1 that is induced by H on Ωu ∪ Ωu+1.
Proposition 6.3 and Lemma 6.2 apply.
We finish this section with another property of the stabilizer of ε in Aut(Γu).
Lemma 6.5. Assume gcd(q − 1, q20 − 1) = 1 and u ∈ Uq,q0 .
(i) Let A be the centralizer of the commutator subgroup K ′ in Aut(Γu). Then K ≤ A
and |A : K| ≤ 2. Moreover, any element of A \ K interchanges the sets Ωu and
Ωu+1.
(ii) Let α ∈ Aut(Γ) be an involution which centralizes H . Then α fixes Ωu ∪ Ωu+1
point-wise.
G. Korchmáros and G. P. Nagy: Graphical Frobenius representations of non-abelian groups 97
Proof. (i): Obvoiusly, K ≤ A and A is transitive. From the last sentence of Corollary 6.4,
an element α ∈ Aε either preserves Ωu and Ωu+1, or it interchanges them. We show
that if α preserves Ωu then α = id. This will imply |Aε| ≤ 2 and |A| ≤ 2q2. Since α
commutes with K ′ and fixes ε, it fixes all points in the orbit εK
′
= {ε}∪Ω∞. The elements
Φa,uaq0+1 ∈ Ωu and Φ0,d ∈ K ′ satisfy both relations
Φa,uaq0+1
u−→ Φ0,d ⇐⇒ d = 0,
Φa,uaq0+1
u+1−→ Φ0,d ⇐⇒ d = aq0+1.
This means that each element in Ωu is connected with a unique element in Ω∞. Hence, α
fixes all elements in Ωu. As each K ′-orbit contains a unique element in Ωu, we see that
each K ′-orbit is preserved. Once again, α commutes with K ′ and fixes an element in each
K ′-orbit. Therefore, α fixes all points in each K ′-orbit.
(ii): As ε is the unique fixed point of H , εα = ε and α leaves the neighborhood
Ωu∪Ωu+1 of ε invariant. By Lemma 6.2(ii), the restriction of α to Ωu∪Ωu+1 cannot have
order 2, therefore, it must be trivial.
7 Imprimitivity
In this section we show that an appropriate choice of u ∈ Fq ensures that Aut(Γu) cannot
act primitively on the set of vertices of Γu. We recall that a primitive permutation group G is
of affine type if it has an abelian regular normal subgroup, which is necessarily elementary
abelian of order rn for some prime r. In this case G is embedded in the affine group
AGL(n, r) with the socle being the translation subgroup. Its stabiliser of 0 ∈ Fnr is a
subgroup of GL(n, r) which acts irreducibly on Fnr . For our purpuse, a useful tool is the
following result by Guralnick and Saxl.
Proposition 7.1 (Guralnick and Saxl [4]). Let G be a primitive permutation group of degree
2n. Then either G is of affine type, or G has a unique minimal normal subgroup N =
S × · · · × S = St, t ≥ 1, S is a non-abelian simple group, and one of the following holds:
(i) S = Am, m = 2e ≥ 8, n = te, and the 1-point stabilizer in N is N1 = Am−1 ×
· · · ×Am−1, or
(ii) S = PSL(2, p), p = 2e − 1 ≥ 7 is a Mersenne prime, n = te, and the 1-point
stabilizer in N is the direct product of maximal parabolic subgroups each stabilizing
a 1-space.
Lemma 7.2. Let G be a group acting transitively on the set X . For x ∈ X and let H = Gx
be the stabilizer of x in G.
(i) For y ∈ X , choose g ∈ G such that y = xg . Then the subgroup of H , fixing the
H-orbit of y point-wise, coincides with ∩h∈HHgh.
(ii) If G is 2-transitive on X then ∩h∈HHgh is either H or {1}, depending upon whether
g ∈ H or g ̸∈ H .
Proof. If y′ ∈ yH , then y′ = yh = xgh for some h ∈ H . Hence, for the stabilizer we
have Gy′ = Gghx = H
gh. Therefore, the point-wise stabilizer of yH is ∩y′∈yHGy′ =
∩h∈HHgh. This proves (i). Clearly, if g ∈ H then ∩h∈HHgh = H . If g ∈ G \ H
then x ̸= y = xg and ∩h∈HHgh fixes all points in {x} ∪ yH . The latter set is X if G is
2-transitive.
98 Ars Math. Contemp. 20 (2021) 89–102
Lemma 7.3. Assume gcd(q − 1, q20 − 1) = 1 and u ∈ Uq,q0 . If Aut(Γu) acts primitively
on Γu, then its action is of affine type.
Proof. Let us assume on the contrary that Aut(Γu) is not of affine type. Let N be its unique
minimal normal subgroup. With the notation in Proposition 7.1, we have N = St where
either S = Am, m ≥ 8, or S = PSL(2, p), with a Mersenne prime p = m − 1 ≥ 7. In
both cases, S has a 2-transitive action on m points. Moreover, if B is the 1-point stabilizer
in S, then the point stabilizer of ε = Φ0,0 in N is Nε = Bt. For (g1, . . . , gt) ∈ St take
a generic vertex y = ε(g1,...,gt) of Γu. Let Y be the Bt-orbit of y. By Lemma 7.2(i) the
point-wise stabilizer of Y is
(∩b∈BBg1b)× · · · × (∩b∈BBgtb).
By Lemma 7.2(ii), each factor is either {1} or B, depending upon whether gi ∈ B or not.
Thus, the point-wise stabilizer of Y in Bt is Bt0 , where 0 ≤ t0 ≤ t, and t0 = t occurs
if and only if Y = {ε}. Therefore, the Bt induces a permutation group on Y which is
isomorphic to Bt1 , where t1 = t− t0. Furthermore, t1 = 0 if and only if Y = {ε}.
The stabilizer Nε acts on Ωu ∪ Ωu+1. Let Y be a nontrivial Nε-orbit contained in
Ωu ∪ Ωu+1. If S = Am, then Nε induces a nonsolvable group of automorphisms of
Ωu ∪ Ωu+1. If S = PSL(2, p), then |B| = p(p− 1)/2, and Nε induces a noncyclic group
of odd order on Ωu ∪ Ωu+1. Both possibilities are inconsistent with Corollary 6.4.
We are now able to prove the imprimitivity of Aut(Γu).
Proposition 7.4. Assume gcd(q − 1, q20 − 1) = 1 and u ∈ Uq,q0 . Then, Aut(Γu) acts
imprimitively on Γu.
Proof. As before, G is identified with its permutation action on Γu. In particular, we
consider H , K as subgroups of Aut(Γu). At the same time, K is the set of vertices of Γu.
Assume on the contrary that Aut(Γu) is primitive, hence of affine type by Lemma 7.3.
Let N be the unique minimal normal subgroup of Aut(Γu). Then N is a regular elementary
abelian 2-group. Since H has odd order, N decomposes into the direct product of H-
invariant subgroups. For any 1 ̸= h ∈ H and 1 ̸= n ∈ N , h has a unique fixed point,
while n has no fixed point. Hence nh ̸= hn. Therefore N = A1 × A2 where Ai is an
elementary abelian group of order q and H acts regularly on Ai \ {1}, i = 1, 2. Consider
the subgroup M = NNK(K). Since NK is nilpotent, we have K ⪇ M and K ′ ◁ M . The
latter implies K ′ ∩ Z(M) ̸= {1}. Since both K ′ and Z(M) are H-invariant while H acts
regularly on K ′ \ {1}, we have K ′ ≤ Z(M). By Lemma 6.5, |M : K| = 2. On the one
hand, M = (M ∩ N)K. On the other hand, N ∩ K is an H-submodule of M ∩ N . By
Maschke’s Theorem [1, (10.8)] applied to M ∩N , viewed as a F2-vector space, there is an
H-invariant subgroup B in M ∩N such that M ∩N = B × (N ∩K). Therefore,
B ∼= (M ∩N)/(N ∩K) ∼= (M ∩N)K/K ∼= M/K ∼= F2,
that is, the nontrivial element of B ≤ N commutes with H , a contradiction.
8 Proof of the main result Theorem 3.1(ii)
In this section, we complete the proof of Theorem 3.1. As before, G is identified with
its permutation action on Γu. From Proposition 7.4, we know that A = Aut(Γu) acts
G. Korchmáros and G. P. Nagy: Graphical Frobenius representations of non-abelian groups 99
imprimitively on Γu. We claim that the only nontrivial blocks of imprimitivity of A are
the cosets of the commutator subgroup K ′ of K. Or equivalently, K ′ is the only nontrivial
block containing ε. Let B be an arbitrary nontrivial block of imprimitivity of A which
contains ε. Then the stabilizer of the set B in G is a subgroup GB of G, lying properly
between H and G. By Lemma 4.2(v), GB = HK ′ and B = K ′, which proves the claim.
The next two lemmas describe the point-wise stabilizer of K ′ in A.
Lemma 8.1. Let E be the point-wise stabilizer of K ′ = {ε} ∪Ω∞ in Aut(Γu). Then E is
either trivial or it is an elementary abelian 2-group which fixes all pairs {Φa,c, Φ−1a,c}.
Proof. The observations made prior to Lemma 6.1 show
Φa,c
u−→ Φ0,d ⇐⇒ d = c+ uaq0+1
for all a, c, d ∈ Fq . Thus, any vertex Φa,c, a ̸= 0, is u-connected to a unique element Φ0,d1
of K ′ and (u+1)-connected to a unique element Φ0,d2 of K
′, where d1 = c+ uaq0+1 and
d2 = c + (u + 1)a
q0+1. If d1 and d2 are distinct nonzero elements, then Φ0,d1 , Φ0,d2 are
distinct vertices in Ω∞, whose common neighbors are Φa,c and Φ−1a,c = Φa,c+aq0+1 , where
a = (d1 + d2)
1
q0+1 and c ∈ {d1 + uaq0+1, d2 + uaq0+1}.
This shows that any automorphism of Γu, which fixes Ω∞ point-wise, must leave the pair
{Φa,c, Φ−1a,c} invariant. It follows that E either trivial or has exponent 2 and in the latter
case E is elementary abelian.
Actually, E is trivial by the following lemma.
Lemma 8.2. The only automorphism that fixes {ε} ∪ Ω∞ point-wise is the identity.
Proof. Let E be defined as in Lemma 8.1. Since HK ′ preserves the set of vertices in K ′,
HK ′ normalizes E. Assume on the contrary that E ̸= {1}, then CE(K ′) ̸= {1} is H-
invariant. Since K ′ acts regularly on itself, E ∩ K ′ = {1}. We apply Lemma 6.5(i) to
conclude that |CE(K ′)| = 2. This means that there is a unique involutory automorphism
α ∈ A which centralizes both K ′ and H . Now, Lemma 6.5(ii) implies that α fixes Ωu ∪
Ωu+1 point-wise. Finally, Lemma 6.5(i) yields α ∈ K, a contradiction.
Let us now focus on the point stabilizer Aε of ε in A = Aut(Γu). Clearly, Aε leaves
Ωu∪Ωu+1 invariant. Moreover, by the imprimitivity of A, Aε preserves Ω∞ as well. Since
any element of Ωu is connected with a unique element of Ω∞, each automorphism fixing
all points in {ε} ∪ Ωu ∪ Ωu+1 fixes all points in Ω∞. Hence by Lemma 8.2, the action of
Aε on Ωu ∪ Ωu+1 is faithful and the possibilities for |Aε| are q − 1, 2(q − 1) or 4(q − 1)
by Corollary 6.4.
Let S denote the stabilizer of the set K ′ in A. On the one hand, HK ′ ≤ S, hence
S is transitive on K ′. On the other hand, Aε ≤ S since K ′ is a block of imprimitivity.
Therefore, Aε = Sε, and
|S| = q|Aε| ∈ {q(q − 1), 2q(q − 1), 4q(q − 1)}.
This implies that S induces a 2-transitive solvable permutation group S̄ on K ′. Since the
order of K ′ is a power of 2, Huppert’s Theorem [6, Theorem XII.7.3] yields that S̄ is
similar to a subgroup of the group AΓL(1, q) of all semilinear mappings
z 7→ azα + b, a, b ∈ Fq, a ̸= 0, α ∈ Aut(Fq)
100 Ars Math. Contemp. 20 (2021) 89–102
on Fq . Here, |AΓL(1, q)| = fq(q − 1) for q = 2f . Since gcd(q − 1, q20 − 1) = 1, f is
odd, and the only possibility for the cardinality of S̄ is q(q−1). We apply Lemma 8.2 once
more to conclude that |S| = q(q − 1), which implies Aε = H and A = HK = G. This
finishes the proof of Theorem 3.1(ii).
Remark 8.3. Since the proof of Lemma 8.2 depends on Huppert’s classification of solvable
2-transitive groups of degree 2h + 1, a natural question is whether the possibility |S| ∈
{2q(q − 1), 4q(q − 1)} can be ruled out by purely combinatorial arguments based on the
structure of the graph Γu rather than by the use of Huppert’s classification. We are likely
to think that the answer is negative. In fact, the action of an extra-automorphism in case
|S| ∈ {2q(q − 1), 4q(q − 1)} does not seem to produce further useful constraint on the
structure of the graph Gu in the case where the kernel K is nonabelian and the complement
H has odd order. Actually, as Spiga himself pointed out in [10, Section 1.1], this case is by
far the hardest in the GFR problem.
9 Spiga’s bound
To state Spiga’s bound we need some notation consistent with that used in [9]. For a
Frobenius group G = N ⋊H with kernel N and complement H , let
d11(|N |, |H|) = 1 +
|N | − 1
|H|
−
(√
|N |
4
− (log2 |N |)2
)
;
d12(|N |, |H|) = 1 +
|N | − 1
|H|
−
(√
|N | − 1− |H|
|H|(1 + 2|H|)
log2
4
3 − 2 log2
√
|N |+ 1
)
;
d1(|N |, |H|) = (log2 |N |)2;
f1(|N |, |H|) = 2d1(|N |,|H|)( 12 |N | − 1)max{2
d11(|N |,|H|), 2d12(|N |,|H|)};
c2(|N |, |H|) =
3
4
|N |
|H|
− 1
2|H|
+
1
2
+
√
|N | |H| − 1
2|H|
+ (log2 |N |)2;
f2(|N |, |H|) = 2c2(|(N |,|H|);
d31(|N |, |H|) =
(
2|N |
|H|
) 2
3
− 2|H|
√
|N |;
d32(|N |, |H|) =
√
N ;
d33(|N |, |H|) = 4
√
|N | − 2|H| 4
√
|N |;
F3(|N |, |H|) =
1
4|H|
min{d31(|N |, |H|), d32(|N |, |H|), d33(|N |, |H|)};
c3(|N |, |H|) =
3
2
+
|N |
|H|
+
1
2|H|
− F3(|N |, |H|) + (log2 |N |)2;
f3(|N |, |H|) = 2c3(|N |,|H|).
Theorem 9.1 (Spiga’s Bound). If
21+(|N |−1)/|H| > f1(|N |, |H|) + f2(|N |, |H|) + f3(|N |, |H|)
then G admits a GFR.
G. Korchmáros and G. P. Nagy: Graphical Frobenius representations of non-abelian groups 101
As stated in [9, Theorem 2], Spiga’s bound implies that when |N | is large compared
to |H|, then a random H-invariant subset S of N gives rise to GFR on Cay(N,S). Spiga
also claimed on his strategy that “Theoretically this strategy is sound, in practice, even for
relatively small groups H , the lower bound on |N | is so large that it seems hopeless and
infeasible to study the small groups N with a computer.”
Proposition 9.2. For a 2-power q ≥ 2, let G be a Frobenius group of order q2(q− 1) with
nucleus of order q2 and complement of order q − 1. Then Spiga’s bound does not hold
for G.
Proof. In our case, in the exponent on the left hand side in Spiga’s bound we have q + 2.
On the other hand, for q = 2m,
c2(|N |, |H|) >
3
4
q2
q − 1
+
q(q − 2)
2(q − 1)
+ 2m ≥ q(5q − 4)
4(q − 1)
+ 2.
A straightforward computation shows that the last number is always bigger than q+2 when
the claim follows.
ORCID iDs
Gábor Korchmáros https://orcid.org/0000-0002-2776-5754
Gábor P. Nagy https://orcid.org/0000-0002-9558-4197
References
[1] C. W. Curtis and I. Reiner, Representation Theory of Finite Groups and Associative Algebras,
AMS Chelsea Publishing, Providence, RI, 2006, doi:10.1090/chel/356.
[2] J. K. Doyle, T. W. Tucker and M. E. Watkins, Graphical Frobenius representations, J. Algebraic
Combin. 48 (2018), 405–428, doi:10.1007/s10801-018-0814-6.
[3] R. Frucht, J. E. Graver and M. E. Watkins, The groups of the generalized Petersen graphs, Proc.
Cambridge Philos. Soc. 70 (1971), 211–218, doi:10.1017/s0305004100049811.
[4] R. M. Guralnick and J. Saxl, Monodromy groups of polynomials, in: W. M. Kantor and
L. Di Martino (eds.), Groups of Lie Type and Their Geometries, Cambridge University Press,
Cambridge, volume 207 of London Mathematical Society Lecture Note Series, pp. 125–150,
1995, doi:10.1017/cbo9780511565823.012, proceedings of the conference held in Como, June
14 – 19, 1993.
[5] G. Higman, Suzuki 2-groups, Illinois J. Math. 7 (1963), 79–96, doi:10.1215/ijm/1255637483.
[6] B. Huppert and N. Blackburn, Finite Groups III, volume 243 of Grundlehren der
Mathematischen Wissenschaften, Springer-Verlag, Berlin-New York, 1982, doi:10.1007/
978-3-642-67997-1.
[7] I. E. Shparlinskiı̆, Some arithmetic properties of recurrence sequences, Mat. Zametki 47 (1990),
124–131, doi:10.1007/bf01170895.
[8] so-called friend Don (https://mathoverflow.net/users/16510/so-called-friend-don), How often
is 2n − 1 a number with few divisors?, MathOverflow, version: 19 October 2015, https:
//mathoverflow.net/q/221269.
[9] P. Spiga, On the existence of Frobenius digraphical representations, Electron. J. Combin. 25
(2018), #P2.6 (19 pages), doi:10.37236/7097.
102 Ars Math. Contemp. 20 (2021) 89–102
[10] P. Spiga, On the existence of graphical Frobenius representations and their asymptotic enumer-
ation, J. Comb. Theory Ser. B 142 (2020), 210–243, doi:10.1016/j.jctb.2019.10.003.
[11] J. von zur Gathen, A. Knopfmacher, F. Luca, L. G. Lucht and I. E. Shparlinski, Average order
in cyclic groups, J. Théor. Nombres Bordeaux 16 (2004), 107–123, doi:10.5802/jtnb.436.