Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 1–25
On pseudocyclic association schemes
Mikhail Muzychuk
Netanya Academic College, Netanya, Israel
Ilya Ponomarenko ∗
Steklov Institute of Mathematics at St. Petersburg, Russia
Received 15 October 2009, accepted 15 May 2011, published online 21 October 2011
Abstract
The notion of a pseudocyclic association scheme is generalized to the non-commutative
case. It is proved that any pseudocyclic scheme the rank of which is much more than the
valency is the scheme of a Frobenius group and is uniquely determined up to isomorphism
by its intersection number array. An immediate corollary of this result is that any scheme
of prime degree, valency k and rank at least k4 is schurian.
Keywords: Association schemes, Pseudocyclic schemes, Frobenius groups.
Math. Subj. Class.: 05E30,20B99
1 Introduction
A commutative association scheme is called pseudocyclic if the multiplicity of its non-
principal irreducible character does not depend on the choice of the character [4] (for a
background on theory of association schemes and coherent configurations we refer to [14]
and Section 2). It can be proved that such a scheme is equivalenced, i.e. the valencies of
its non-reflexive basis relations are pairwise equal. A classical example of a commutative
pseudocyclic scheme is a cyclotomic scheme over a finite field; two other series of such
schemes were constructed in [19]. A motivation to study pseudocyclic schemes is that any
of them produces special 2-designs.
In this paper we define an association scheme (not necessary commutative) to be pseu-
docyclic if the ratio of the multiplicity and degree of its non-principal irreducible character
does not depend on the choice of the character. Clearly, in the commutative case both defi-
nitions give the same concept. To formulate one of the main results of this paper (which, in
∗The work was partially supported by RFFI grant 11-01-00760-a.
E-mail addresses: muzy@netanya.ac.il (Mikhail Muzychuk), inp@pdmi.ras.ru (Ilya Ponomarenko)
Copyright c© 2012 DMFA Slovenije
2 Ars Math. Contemp. 5 (2012) 1–25
particular, shows that non-commutative pseudocyclic schemes do exist) we make two re-
marks. First, as in the commutative case we can prove (Theorem 3.2) that any pseudocyclic
scheme is equivalenced; the valency of its non-reflexive basis relation is called the valency
of the scheme. Secondly, under a Frobenius scheme we mean the scheme of a Frobenius
group (in its standard permutation representation in which the one point stabilizer coin-
cides with the Frobenius complement). Our first result is an immediate consequence of
Theorems 3.1 and 7.4.
Theorem 1.1. Any Frobenius scheme is pseudocyclic. Conversely, there exists a function
f(k) such that any pseudocyclic scheme of valency k > 1 and rank at least f(k) is a
Frobenius scheme.
The rough upper bound on the function f(k) obtained in the proof is O(k4). On the
other hand, the scheme of a non-Desarguesian affine plane of order q is non-schurian (see
Subsection 4.5), and hence can not be a Frobenius scheme. Besides, it is pseudocyclic of
valency q − 1 and rank q + 2. Thus f(k) ≥ k + 3.
The proof of the second part of Theorem 1.1 is based on Theorem 5.4 giving together
with Theorem 7.1 a sufficient condition for an equivalenced scheme to be schurian.
The celebrated Hanaki-Uno theorem states that any scheme of prime degree is pseudo-
cyclic [18]. Therefore as an immediate consequence of Theorem 1.1 we have the following
result.
Corollary 1.2. Any scheme of prime degree, valency k and rank at least f(k) is schurian.
One of the most important problems in association scheme theory is to determine a
scheme up to (ordinary) isomorphism by means of the intersection number array. For ex-
ample, the intersection number array of the scheme of a distance-regular graph is uniquely
determined by the parameters of the graph. Therefore the most part of characterizations of
the classical distance-regular graphs given in [4] are in fact the characterizations of their
schemes in the above sense (we refer to [14] for a survey of relevant results). In this paper
we prove the following result which is a direct consequence of Theorem 7.4.
Theorem 1.3. Any Frobenius scheme of valency k and rank at least f(k) is determined up
to isomorphism by its intersection number array.
All undefined terms and results concerning permutation groups can be found in mono-
graphs [27, 29]. To make the paper as self-contained as possible we give a background on
association schemes [30] and coherent configurations [14] in Section 2.
Section 3 contains the definition of a pseudocyclic scheme, several useful results on
these schemes and the proof of the first part of Theorem 1.1 (Theorem 3.1). In Section 4
we give a brief exposition of known families of pseudocyclic schemes. In Sections 5 and 6
under a special assumption we explicitly find a one point fission of a pseudocyclic scheme
and a one point fission of any algebraic isomorphism from it to another scheme (The-
orems 5.4 and 6.2). Based on these results we prove our main theorems in Section 7.
Section 8 includes some concluding remarks and special results concerning pseudocyclic
schemes.
Notation. Throughout the paper Ω denotes a finite set. Set 1Ω = {(α, α) : α ∈ Ω}
and 1α = 1{α} for all α ∈ Ω. For a relation r ⊂ Ω×Ω we set r∗ = {(β, α) : (α, β) ∈ r}
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 3
and αr = {β ∈ Ω : (α, β) ∈ r} for all α ∈ Ω. The adjacency matrix of r is denoted by
A(r). For s ⊂ Ω × Ω we set r · s = {(α, γ) : (α, β) ∈ r, (β, γ) ∈ s for some β ∈ Ω}.
If S and T are sets of relations, we set S · T = {s · t : s ∈ S, t ∈ T}. For a permutation
group G ≤ Sym(Ω) we denote by Orb(G) = Orb(G,Ω) the set of G-orbits.
2 Schemes, coherent configurations and permutation groups
This section collects all definitions and basic facts related to coherent configurations and
association schemes which are used in the paper. Our notation style is a mixture of the
styles used in [30] and [14].
2.1 Definitions
Let Ω be a finite set and S a partition of Ω × Ω. Denote by S∪ the set of all unions of
the elements of S. A pair (Ω, S) is called a coherent configuration on Ω if the following
conditions are satisfied:
(S1) the diagonal 1Ω ⊂ Ω× Ω belongs to S∪,
(S2) S is closed with respect to ∗,
(S3) given r, s, t ∈ S, the number ctrs = |{β ∈ Ω : (α, β) ∈ r, (β, γ) ∈ s}| does not
depend on the choice of (α, γ) ∈ t.
The elements of Ω, S, S∪ and the numbers in (S3) are called the points, the basis relations,
the relations and the intersection numbers of the coherent configuration (Ω, S), respec-
tively. The numbers |Ω| and |S| are called the degree and rank of it. The unique basis
relation containing a pair (α, β) ∈ Ω× Ω is denoted by r(α, β). The set of basis relations
contained in r · s with r, s ∈ S∪ is denoted by rs.
2.2 Homogeneity
The set Ω is the disjoint union of fibers of (Ω, S), i.e. those ∆ ⊂ Ω for which 1∆ ∈ S. For
any basis relation s ∈ S there exist uniquely determined fibers ∆,Γ such that s ⊂ ∆× Γ.
Moreover, the number |δs| does not depend on δ ∈ ∆ and coincides with ctss∗ where
t = 1∆. We denote it by ns and call valency of s. The coherent configuration (Ω, S) is
called homogeneous or an association scheme or a scheme if Ω is a fiber of it. In this case
ns = ns∗ , s ∈ S.
We say that (Ω, S) is an equivalenced scheme of valency k, when ns = k for all s ∈ S#
where here and below we put S# = S \ {1Ω}.
2.3 Isomorphisms and schurity
Two coherent configurations are called isomorphic if there exists a bijection between their
point sets preserving the basis relations. Any such bijection is called an isomorphism of
these coherent configurations. The group of all isomorphisms of a coherent configuration
(Ω, S) to itself (sometimes called the group of colored automorphisms) contains a normal
subgroup
Aut(Ω, S) = {f ∈ Sym(Ω) : sf = s, s ∈ S}
4 Ars Math. Contemp. 5 (2012) 1–25
called the automorphism group of (Ω, S). Conversely, let G ≤ Sym(Ω) be a permutation
group and S the set of its 2-orbits, i.e. the orbits of componentwise action of G on Ω× Ω.
Then (Ω, S) is a coherent configuration and we call it the coherent configuration ofG. This
coherent configuration is homogeneous if and only if the group G is transitive; in this case
we say that (Ω, S) is the scheme of G. A coherent configuration on Ω is called schurian if
it is the coherent configuration of 2-orbits of some permutation group on Ω.
2.4 Algebraic isomorphisms and separability
Two coherent configurations (Ω, S) and (Ω′, S′) are called algebraically isomorphic if
ctrs = c
t′
r′s′ , r, s, t ∈ S, (2.1)
for some bijection ϕ : S → S′, r 7→ r′ called an algebraic isomorphism from (Ω, S)
to (Ω′, S′). Each isomorphism f from (Ω, S) to (Ω′, S′) induces in a natural way an
algebraic isomorphism between these schemes denoted by ϕf . The set of all isomorphisms
inducing the algebraic isomorphism ϕ is denoted by Iso(S, S′, ϕ). In particular,
Iso(S, S, idS) = Aut(Ω, S)
where idS is the identical mapping on S. A coherent configurations (Ω, S) is called sepa-
rable if the set Iso(S, S′, ϕ) is non-empty for each algebraic isomorphism ϕ.
2.5 Semiregularity
A coherent configuration (Ω, S) is called semiregular if
|αs| ≤ 1, α ∈ Ω, s ∈ S. (2.2)
A semiregular scheme is called regular; regular schemes are exactly thin schemes in the
sense of [30]. One can see that a coherent configuration (resp. scheme) is semiregular
(resp. regular) if and only if it is a coherent configuration (resp. scheme) of a semiregular
(resp. regular) permutation group. The proof of this statement as well as the next one can
be found in [12].
Theorem 2.1. Any semiregular configuration is schurian and separable.
2.6 One point fission
Let (Ω, S) be a coherent configuration and α ∈ Ω. Denote by Sα the set of basis relations
of the smallest coherent configuration on Ω such that 1α ∈ Sα and S ⊂ S∪α (see [14]). The
coherent configuration (Ω, Sα) is called the α-fission (or a one point fission) of (Ω, S). It
is easily seen that
Aut(Ω, S)α = Aut(Ω, Sα). (2.3)
Notice that the set αs is a union of some fibers of (Ω, Sα) for all s ∈ S, and the relation
t ∩ (αr × αs) belongs to the set S∪α for all r, s, t ∈ S.
Let (Ω′, S′) be a coherent configuration and ϕ : (Ω, S) → (Ω′, S′) an algebraic iso-
morphism. Let α′ ∈ Ω′ and ψ : (Ω, Sα) → (Ω, S′α′) be an algebraic isomorphism such
that
ψ(1α) = 1α′ , ψ(s) ⊂ ϕ(s̃), s ∈ Sα, (2.4)
where s̃ is the unique basis relation of (Ω, S) that contains s. Thenψ is uniquely determined
by ϕ. We say that ϕα,α′ := ψ is the (α, α′)-extension (or one point extension) of ϕ.
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 5
2.7 t-condition
The following definition goes back to [15, p.70]. Let (Ω, S) be a coherent configuration.
Two sets ∆,∆′ ⊂ Ω have the same type with respect to the pair (α, β) ∈ Ω × Ω if
α, β ∈ ∆ ∩ ∆′ and there exists a bijection δ 7→ δ′ from ∆ onto ∆′ such that α′ = α,
β′ = β and
r(δ1, δ2) = r(δ
′
1, δ
′
2), δ1, δ2 ∈ ∆.
Let t ≥ 2 be an integer. The coherent configuration (Ω, S) satisfies the t-condition at a
relation s ∈ S if for each k = 2, . . . , t the number of k-subsets of Ω of each fixed type
with respect to the pair (α, β) ∈ s does not depend on the choice of this pair. If the t-
condition is satisfied at each s ∈ S, we say that (Ω, S) satisfies the t-condition. It can be
proved that the scheme on n points is schurian if and only if it satisfies the t-condition for
all t = 2, . . . , n− 1.
2.8 Indistinguishing number
Let (Ω, S) be a scheme. The indistinguishing number of a relation s ∈ S is defined to be
the number
c(s) =
∑
t∈S
cstt∗ .
The term goes back to [1, p.563] where the number n − c(s) with n = |Ω| was called the
distinguishing number of s. Clearly, c(1Ω) = n. The maximum of c(s), s ∈ S#, is called
the indistinguishing number of (Ω, S).
Lemma 2.2. Let (Ω, S) be an equivalenced scheme of valency k. Then the arithmetical
mean of c(s), s ∈ S#, equals k − 1.
Proof. Set n = |Ω|. Then |S#| = (n − 1)/k and |s| = nk for all s ∈ S#. Counting the
number of Ω-triples (α, β, γ) such that r(α, β) = r(α, γ) ∈ S# by two ways we obtain
that
nk
∑
s∈S#
c(s) = n(k − 1)k|S#|
whence the required statement follows.
2.9 Adjacency algebra
Let (Ω, S) be a coherent configuration. The set {A(s) : s ∈ S} forms a linear basis of an
algebra CS ⊂ MatΩ(C). It is called the adjacency algebra of the coherent configuration
(Ω, S). From the definition it follows that it is closed with respect to the transpose and
the Hadamard product. In particular, it is semisimple. So by the Wedderburn theorem
its standard module CΩ is completely reducible. For an irreducible submodule L of CΩ
corresponding to a central primitive idempotent P of the algebra CS, we set
nP = dimC(L), mP = rk(P )/nP , (2.5)
thus mP and nP are the multiplicity and the degree of the corresponding irreducible repre-
sentation of CS. Clearly,
|Ω| =
∑
P∈P
mPnP , |S| =
∑
P∈P
n2P (2.6)
6 Ars Math. Contemp. 5 (2012) 1–25
where P is the set of central primitive idempotents of CS. The coherent configuration
(Ω, S) is called commutative if the algebra CS is commutative (equivalently, nP = 1 for
all P ).
Let (Ω, S) be a scheme. It can be proved that mP ≥ nP for all P ∈ P [10]. Besides,
for the principal central primitive idempotent P0 = 1nJ where J is the all one matrix, we
have mP0 = nP0 = 1. The corresponding one-dimensional irreducible representation of
CS takes A to tr(AA∗). In particular, we have
nrns =
∑
t∈S
ctrsnt. (2.7)
We set P# = P \ {P0} and 〈A,B〉 = tr(AB∗) for all A,B ∈ CS.
2.10 Intersection numbers
There is a lot of useful identities for the intersection numbers of an arbitrary scheme [30].
One of them is (2.7), another one is
ntc
t∗
rs = nrc
r∗
st = nsc
s∗
tr , r, s, t ∈ S. (2.8)
We also need the following lemma.
Lemma 2.3. Let (Ω, S) be a scheme and r, s ∈ S#. Then ctr∗s ≤ 1 for all t ∈ S if and
only if rr∗ ∩ ss∗ = {1Ω}.
Proof. We have
nrns ≤ nrns +
∑
t∈(rr∗∩ss∗)#
ctrr∗c
t
ss∗nt = 〈rr∗, ss∗〉
and the bound is attained if and only if rr∗∩ss∗ = {1Ω}, where 〈rr∗, ss∗〉 = 〈A(r)A(r∗),
A(s)A(s∗)〉. Similarly, from (2.7) it follows that
〈r∗s, r∗s〉 =
∑
t∈S
(ctr∗s)
2nt ≥
∑
t∈S
ctr∗snt = nrns
and the bound is attained if and only if ctr∗s ≤ 1 for all t ∈ S. Since 〈rr∗, ss∗〉 = 〈r∗s, r∗s〉
we are done.
2.11 Frobenius groups
In this subsection we recall some well-known group theoretical facts on the Frobenius
groups [17, 27]. A non-regular transitive permutation group G ≤ Sym(Ω) is called a
Frobenius group if Gα,β = {idΩ} for all non-equal points α, β ∈ Ω. Any Frobenius group
G has a uniquely determined regular normal subgroup A called the kernel of G. Therefore
G = AK where K is a one point stabilizer of G, and GCD(|A|, |K|) = 1.
Theorem 2.4. Let G ≤ Sym(Ω) be a finite non-regular transitive permutation group with
point stabilizer K and
θ =
∑
χ∈Irr(G)
mχχ
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 7
the decomposition of the permutation character θ of G into irreducibles. Then G is a
Frobenius group if and only if χ(1)/mχ = |K| for each character χ ∈ Irr(G)# with
mχ 6= 0.
Proof. To prove the necessity suppose that G is a Frobenius group with a complement K.
Then from [17, p.318-319] it follows that given ϕ ∈ Irr(K)# the class function χϕ =
ϕG − ϕ(1)θ′ is an irreducible character of G of degree ϕ(1) and
ρ− |K|θ′ = 1 +
∑
ϕ∈Irr(K)#
ϕ(1)χϕ (2.9)
where 1 and ρ are the principal and regular characters of G, and θ′ = θ − 1. Since
χϕ ∈ Irr(G), we have [ρ, χϕ] = χϕ(1) = ϕ(1). Therefore by (2.9) we obtain∑
χ∈Irr(G)\Φ
χ(1)χ = |K|θ′ =
∑
χ∈Irr(G)#
|K|mχχ
where Φ = {1} ∪ {χϕ : ϕ ∈ Irr(K)#}. Thus χ(1) = |K|mχ for each character
χ ∈ Irr(G)# with mχ 6= 0.
To prove the sufficiency suppose that χ(1)/mχ = |K| for each non-principal character
χ ∈ Irr(G) with mχ 6= 0. Since
∑
χm
2
χ = r − 1 where r = |Orb(K)| (see [17,
Th. 16.6.14]), we have
|Ω| − 1 =
∑
χ∈Irr(G)#
χ(1)mχ =
∑
χ∈Irr(G)#
|K|m2χ = |K|(r − 1).
Therefore |K| = (|Ω| − 1)/(r − 1). Since each non-trivial orbit of K has cardinality at
most |K| and there are r− 1 orbits, we obtain that each non-trivial K-orbit has cardinality
K, that is Gα,β = {idΩ} whenever α 6= β.
3 Pseudocyclic schemes
A scheme (Ω, S) is called pseudocyclic if the number mP/nP does not depend on the
choice of the central primitive idempotent P ∈ P# (see Subsection 2.9). In the commu-
tative case nP = 1 for all P ∈ P , and our definition is compatible with that from [4].
Any regular scheme (not necessarily commutative) is pseudocyclic because in this case
mP = nP for all P . More elaborated example of a non-commutative pseudocyclic scheme
arises from a Frobenius group with non-abelian kernel. In what follows we use the family
of such groups given in [27, pp.187-189].
Example. Let q be a prime power and n > 1 an odd integer. Set H to be a subgroup of
GL(3, qn) that consists of all matrices of the form
A(a, b) =
1 a b0 1 aq
0 0 1
 a, b ∈ GF(qn).
Then the mapping σ : A(a, b) 7→ A(ca, c1+qb) is a fixed point free automorphism of
H whenever the multiplicative order of c equals (qn − 1)/(q − 1). So the semidirect
8 Ars Math. Contemp. 5 (2012) 1–25
product G = HK where K = 〈σ〉, is a Frobenius group with non-abelian kernel H and
complement K. The natural action of G on H produces an equivalenced scheme of degree
|H| = q2n, rank qn+1−qn+q and valency (qn−1)/(q−1). A straightforward calculation
for (q, n) = (2, 3) shows that the adjacency algebra of the corresponding scheme has
exactly four irreducible characters, the multiplicities and degrees of which are as follows:
(m1, n1) = (1, 1), (m2, n2) = (7, 1), (m3, n3) = (m4, n4) = (14, 2).
In particular, the scheme is not commutative but is pseudocyclic because mP/nP = 7 for
all P ∈ P#. In fact, this example is a special case of the following theorem.
Theorem 3.1. Any Frobenius scheme is pseudocyclic. Moreover, it is commutative if and
only if the kernel of the associated Frobenius group is abelian.
Proof. Let (Ω, S) be a Frobenius scheme, G ≤ Sym(Ω) the corresponding Frobenius
group and the mapping
π : CG→ MatΩ(C)
is induced by the permutation representation of G (in particular, π(g) is the permutation
matrix of a permutation g ∈ G). It is a well-known fact that a semisimple subalgebra of
MatΩ(C) coincides with the centralizer of its centralizer (in MatΩ(C)) [8, p.178]. Since
the algebra π(CG) is semisimple and its centralizer in MatΩ(C) equals CS, the centralizer
of CS in MatΩ(C) coincides with π(CG). Therefore these two algebras have the same
centre
Z(π(CG)) = Z(CS) = CS ∩ π(CG), (3.1)
and hence the same set of central primitive idempotents, say P . Moreover, one can see
that nP = mχP and mP = χP (1) for all P ∈ P where χP is the irreducible character of
G corresponding to the central primitive idempotent P . Since G is a Frobenius group, by
Theorem 2.4 this implies that
mP/nP = mχP /χP (1) = |K|, P ∈ P#,
where K is the complement of G. Thus (Ω, S) is a pseudocyclic scheme.
To prove the second statement we find the dimension of the left-hand side of (3.1).
First, we note that the algebra Z(CG) is spanned by the elements C+ =
∑
g∈C g where
C runs through the set of conjugacy classes of G. Moreover, if A denotes the kernel of G,
then
C ∩A = ∅ ⇒ π(C+) ∈ CJΩ.
(Indeed, C contains a−1ca = a−1acc for all a ∈ A and c ∈ C. On the other hand, since
c 6∈ A, the mapping a 7→ a−1ac, a ∈ A, is a bijection. Thus CA = C. Taking into account
that π(A+) = JΩ, we conclude that π(C+) is a scalar multiple of JΩ.) This implies that
dim(π(Z(CG))) = |ClaG(A)| (3.2)
where ClaG(A) is the set of conjugacy classes of G contained in A. Indeed, π(C+) is a
{0, 1} matrix. Since the sum of these matrices with C ∈ ClaG(A) equals JΩ, they are
linearly independent and form a basis of π(Z(CG)).
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 9
Next, the group K acts semiregularly on the set of non-trivial conjugacy classes of A.
So any set C ∈ ClaG(A) other than {1} is a disjoint union of exactly k = |K| of these
classes. This shows that
|ClaG(A)| = 1 + (|Cla(A)| − 1)/k (3.3)
where Cla(A) is the set of conjugacy classes of A. To complete the proof we note that
from (3.1) it follows that the scheme S is commutative if and only if CS = π(Z(CG)), or
equivalently if
1 + (|A| − 1)/k = |S| = dim(CS) = dim(Z(CS)) = dim(π(Z(CG))).
By (3.2) and (3.3) this is true if and only if |Cla(A)| = |A|, i.e. the group A is commuta-
tive.
We would like to have a characterization of a pseudocyclic scheme in terms of its va-
lences and indistiguishing numbers of basis relations. For commutative case it was done
in [4, Proposition 2.2.7].
Theorem 3.2. The following two statements are equivalent:
(1) (Ω, S) is a pseudocyclic scheme with mP/nP = k for all P ∈ P#,
(2) (Ω, S) is an equivalenced scheme of valency k with c(s) = k − 1 for all s ∈ S#.
Moreover, any pseudocyclic scheme with pairwise equal non-principal dimensions of irre-
ducible representations is commutative.
Proof.1 Denote by ρ and by χ respectively the regular and standard characters of the alge-
bra CS. Then for any s ∈ S we have
ρ(as) =
∑
t∈S
ctts = ns +
∑
P∈P#
nPχP (as), (3.4)
χ(as) = δs,1Ωn = ns +
∑
P∈P#
(mP/nP )nPχP (as) (3.5)
where as = A(s), n = |Ω| and χP is the irreducible character of of CS corresponding to
central primitive idempotent P .
Suppose that mP/nP = k for all P ∈ P#. Then from (3.4) and (3.5) it follows that
k(ns − ρ(as)) = ns for all s ∈ S#. Since ns > 0, we have ns − ρ(as) ≥ 1, and hence
ns ≥ k. By (2.6) this implies that
n− 1 =
∑
s∈S#
ns ≥ (r − 1)k =
∑
P∈P#
nPk =
∑
P∈P#
mPnP = n− 1
where r = |S|. Thus ns = k and (Ω, S) is an equivalenced scheme of valency k. In
particular, k(k − ρ(as)) = ns whence it follows that, ρ(as) = k − 1. However, by (3.4)
1The original proof was given in [24]. The authors thank to Paul-Hermann Zieschang who proposed a fruitful
idea used in the proof here.
10 Ars Math. Contemp. 5 (2012) 1–25
and (2.8) we have ρ(as) = c(s). Therefore c(s) = k − 1 and the implication (1)⇒(2) is
proved.
Assume now that ns = k and c(s) = k − 1 for all s ∈ S#. Then from (3.4) and (3.5)
it follows that k ≤ kmin := min{mP/nP : P ∈ P#}. Therefore by (2.6) we have
n− 1 =
∑
P∈P#
mPnP =
∑
P∈P#
(mP/nP )n
2
P ≥ kmin
∑
P∈P#
n2P ≥ k(r − 1) = n− 1.
Thus mP/nP = kmin = k for all P ∈ P#. The implication (2)⇒(1) is proved.
Let now (Ω, S) be a pseudocyclic scheme such that nP does not depend on P ∈ P#.
Denote this number by a. Then by the first part of the proof the scheme is equivalenced
of valency k where ka = mP for each P ∈ P#. So from (2.6) it follows that |P#|a2 =
r − 1 = (n − 1)/k. Therefore a is coprime to n. Taking into account that ns = k for all
s ∈ S#, we have
nr
∏
s∈S ns∏
P∈P m
n2P
P
=
nrkr−1
kr−1ar−1
=
nr
ar−1
.
The number in the left-hand side, known as the Frame number [28] of the scheme (Ω, S),
is an integer. Since r > 1, we conclude that a = 1. Thus nP = 1 for all P and the scheme
is commutative.
There is a lot of equivalenced schemes (Ω, S) for which the group of algebraic iso-
morphisms acts transitively on S#. These schemes were first studied by Ikuta, Ito and
Munemasa [20], and include the cyclotomic schemes over finite fields and the schemes of
affine planes (see Section 4). The following statement shows that all of them are pseudo-
cyclic.
Corollary 3.3. Let (Ω, S) be an equivalenced scheme. Suppose that a group of its alge-
braic isomorphisms acts transitively on S#. Then (Ω, S) is a pseudocyclic scheme.
Proof. From the hypothesis it follows that the number c(s) does not depend on s ∈ S#.
So by Lemma 2.2 this number equals k − 1 and we are done by Theorem 3.2.
Sometimes one can construct a new pseudocyclic scheme by means of an appropri-
ate algebraic fusion defined as follows (see also [10, Lemma 3.1]). Let G be a group of
algebraic isomorphisms of a coherent configuration (Ω, S). Set
SG = {sG : s ∈ S}
where sG is the union of the relations sg , g ∈ G. It is easily seen that the pair (Ω, SG) is a
coherent configuration. Moreover, if the group G is half-transitive on S# and the coherent
configuration (Ω, S) is equivalenced, then the scheme (Ω, SG) is equivalenced. An analog
of this statement holds for commutative pseudocyclic schemes. It generalizes the results of
Section 7.4 [22].
Theorem 3.4. Let (Ω, S) be a commutative pseudocyclic scheme of valency k and G a
group of algebraic isomorphisms of it. Suppose that G acts semiregularly on S#. Then
(Ω, SG) is a commutative pseudocyclic scheme of valency km where m = |G|.
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 11
Proof. We observe that (Ω, SG) being a fusion of a commutative scheme is also commu-
tative. Since it is equivalenced of valency km (see above), we have
|PG| = |SG| = 1 + (|S| − 1)/m (3.6)
where PG is the set of central primitive idempotents of the algebra CSG. On the other
hand, the group G naturally acts as an automorphism group of the algebra CS. Therefore
the set P of its central primitive idempotents is G-invariant. For P ∈ P denote by PG
the sum of all Q ∈ P belonging to the G-orbit containing P . Then obviously the set
P ′ = {PG : P ∈ P} consists of pairwise orthogonal central idempotents of the algebra
CSG. This implies that
|P ′| ≤ |PG|. (3.7)
Finally, anyG-orbit inP is of cardinality at mostm. SinceG leaves P0 fixed and |P| = |S|,
this implies that
|P ′| ≥ 1 + (|P| − 1)/m = 1 + (|S| − 1)/m
and the equality holds exactly when any G-orbit in P# is of size m. Together with (3.6)
and (3.7) this shows that |PG| = |P ′|. Therefore mPG = mmP = mk and nPG = 1 for
all P ∈ P#. Thus the scheme (Ω, SG) is pseudocyclic.
A schurian equivalenced non-regular scheme is nothing but the scheme of 3/2-transitive
group. In general, the latter is not a Frobenius group. However, the following statement
holds.
Theorem 3.5. A schurian pseudocyclic scheme of valency k > 1 and rank greater than
2(k − 1) is a Frobenius scheme the automorphism group of which is a Frobenius group.
Proof. Let (Ω, S) be a schurian pseudocyclic scheme of valency k > 1 and let G =
Aut(Ω, S). Then the set Fix(g) of points left fixed by a nonidentity permutation g ∈ G
does not coincide with Ω. So there exists α ∈ Ω such that αg 6= α. Since r(α, β) =
r(αg, β) for all β ∈ Fix(g), Theorem 3.2 implies that
|Fix(g)| ≤ |{β ∈ Ω : r(α, β) = r(αg, β)}| = c(s) = k − 1
where s = r(α, αg). Thus the permutation character of G takes the value in the set
{0, . . . , k − 1} on all nonidentity elements. Therefore by [6, Prop.1] a point stabilizer
Gα has at most 2(k − 1) − 1 non-regular orbits. If |S| > 2(k − 1), then at least one orbit
of Gα is regular. This implies that so are all non-trivial orbits. Thus G is a Frobenius
group.
4 Known examples of pseudocyclic schemes
4.1 Schemes of rank 3
Any pseudocyclic scheme of rank 3 arises from either a conference matrix (symmetric case)
or from a skew Hadamard matrix (antisymmetric case) [4, 25]. In any case the intersec-
tion number array is uniquely determined by the degree of the scheme. In particular, two
such schemes are algebraically isomorphic if and only if they have the same degree. Since
there is an infinite number of n for which there are at least two non-equivalent conference
matrices or non-equivalent skew Hadamard matrices of order n, in general pseudocyclic
12 Ars Math. Contemp. 5 (2012) 1–25
schemes of rank 3 are not separable (see also [12, Section 7]). Similarly, one can see that
most of them are non-schurian. For instance, it follows from [3] that an antisymmetric
pseudocyclic scheme of rank 3 is schurian if and only if it is a scheme of a Paley tourna-
ment. Moreover, in [15, p.75] one can find an infinite family of non-schurian pseudocyclic
schemes of rank 3 satisfying the 4-condition.
4.2 The Hollman schemes [4, p.390]
Let q > 4 be a power of 2. Denote by Ω the set of cyclic groups of order q+ 1 in the group
PSL(2, q). The latter acts transitively on Ω by conjugation and hence produces the scheme
of degree (q2 − q)/2. One can prove that this scheme is symmetric and pseudocyclic of
valency q + 1. Some algebraic fusions of the Hollman scheme that are also pseudocyclic
were studied in [19].
4.3 The Passman schemes [26]
Let q be an odd prime power and F the group consisting of the transformations(
x
y
)
→
(
a 0
0 a−1
)(
x
y
)
+
(
b
c
)
, (4.1)
where a, b, c ∈ GF(q), and a 6= 0. Then F is a Frobenius group acting on a 2-dimensional
space over GF(q). By Theorem 3.1 the scheme of F is pseudocyclic of valency q− 1. The
group
D =
{(
±1 0
0 ±1
)
,
(
0 ±1
±1 0
)}
(4.2)
normalizes F and, therefore, acts on the relations of the scheme of F as a group of algebraic
automorphisms. A direct check shows that the action of D on non-trivial relations of the
scheme of F is semiregular with orbit length two. By Theorem 3.4 the scheme of the group
FD pseudocyclic of valency 2(q − 1). We call the scheme of the group FD the Passman
scheme, because Passman pointed out that FD is 3/2-transitive non-Frobenius solvable
group.
4.4 Cyclotomic schemes
Let R be a finite local commutative ring with identity. Then its multiplicative group R× is
the direct product of the Teichmüller group T and the group of principal units [23]. The
Teichmüller group is isomorphic to the multiplicative group of the residue field of R, and
acts as a fixed point free automorphism group of the additive group R+ of R. Therefore
for a given K ≤ T , the scheme of the group (R+ o K,R+) is a Frobenius scheme and
hence pseudocyclic by Theorem 3.1. This example is a special case of a cyclotomic scheme
over a finite commutative ring [14]. In almost the same way one can construct a class of
pseudocyclic schemes where the ground ring R is replaced by a near-field [2], or even a
near-ring.
4.5 Affine schemes
Let Ω be the point set of a finite affine spaceA (see [5]). Denote by S the partition of Ω×Ω
containing 1Ω and such that two pairs (α, β), (α′, β′) ∈ Ω × Ω, α 6= β, α′ 6= β′, belong
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 13
to the same class if and only if the lines αβ and α′β′ are equal or parallel. Then the pair
(Ω, S) is a symmetric scheme and nonzero intersection numbers ctrs with 1Ω 6∈ {r, s} are
as follows:
ctrs =

q − 1, r = s, t = 1Ω,
q − 2, r = s = t,
1, r 6= s, t ∈ rs,
(4.3)
where q is the size of a line in A (called the order of A). It follows that it is a pseu-
docyclic scheme of valency q − 1. Each relation of an affine scheme is an involution in
the sense of [30]. It was shown in [9] that a scheme whose relations are involutions is
an affine scheme. Thus there is one-to-one correspondence between affine schemes and
affine spaces. It is straightforward to prove that the schemes of affine spaces are isomor-
phic (resp. algebraically isomorphic) if and only if the affine spaces are isomorphic (resp.
have the same order).
Theorem 4.1. The scheme of a finite affine space A is schurian if and only if A is Desar-
guesian.
Proof. By the Veblen-Young theorem (cf. [5]) a finite affine space A is either a non-
Desarguesian affine plane, or the n-dimensional affine geometry AG(n, q) over GF(q).
In the latter case the scheme of A coincides with the scheme of the group
TC ≤ AGL(n, q)
where T is the translation group andC is the centre of GL(n, q). This proves the sufficiency
part of the theorem. To prove the necessity assume that the scheme of A is schurian. Then
it satisfies the 4-condition and the required statement immediately follows from the lemma
below.
Lemma 4.2. Suppose that the scheme of an affine space A satisfies the 4-condition. Then
A is Desarguesian.
Proof. Let (Ω, S) be the scheme of A. It suffices to verify that given seven distinct points
α, α′, β, β′, γ, γ′ and δ, such that αα′, ββ′, and γγ′ are distinct lines through δ and αγ
is parallel to α′γ′ and βγ is parallel to β′γ′, then αβ is parallel to α′β′ (see Figure 1).
However, since δγ = δγ′, we have r(δ, γ) = r(δ, γ′). Due to the 4-condition there exist
points α′′, β′′ such that the 4-sets ∆ = {δ, γ, α, β} and ∆′ = {δ, γ′, α′′, β′′} have the
same type with respect to the pairs (δ, γ) and (δ, γ′) respectively. So r(α, δ) = r(α′′, δ)
and r(β, δ) = r(β′′, δ). This implies that
α′′ ∈ αδ = α′δ, β′′ ∈ βδ = β′δ. (4.4)
On the other hand, r(α, γ) = r(α′′, γ′) and r(β, γ) = r(β′′, γ′). Therefore αγ is parallel
to α′′γ′, and βγ is parallel to β′′γ′. Thus from (4.4) we conclude that α′′ = α′ and
β′′ = β′. Since also r(α, β) = r(α′′, β′′), the line αβ is parallel to α′′β′′ = α′β′, and we
are done.
14 Ars Math. Contemp. 5 (2012) 1–25
76540123δ




>>
>>
>>
>>
76540123α
HH
HH
HH





76540123γ
66
66
66
66
66
vv
vv
vv
76540123β
76540123α′
II
II
II
II
II
II
II
76540123γ′
uu
uu
uu
uu
uu
uu
uu
76540123β′
Figure 1:
4.6 Amorphic schemes
A scheme (Ω, S) is called amorphic [16] if any its fusion is a scheme. It was shown in
[16] that all basis graphs of an amorphic scheme of rank at least four are strongly regu-
lar either of Latin square type or of negative Latin square type. If an amorphic scheme is
equivalenced, then its group of algebraic automorphisms is Sym(S#). This implies (Corol-
lary 3.3) that (Ω, S) is pseudocyclic. A scheme of an affine plane of order q is an amorphic
(q − 1)-valenced scheme of rank q + 2. This yields us the following statement.
Theorem 4.3. Let q be the order of an affine plane. Then given a divisor m of q + 1 and a
partition of {1, . . . , q+ 1} in m classes of cardinality (q+ 1)/m, there exists an amorphic
pseudocyclic scheme of degree q2, valency (q2 − 1)/m and rank m+ 1.
5 One point fission of an equivalenced scheme.
5.1 Splitting sets
Let (Ω, S) be an equivalenced scheme of valency k. For each (possibly equal) basis rela-
tions u, v ∈ S# we define the splitting set D(u, v) of them as follows:
D(u, v) = {w ∈ S# : (uu∗ vv∗) ∩ ww∗ = {1Ω}}. (5.1)
It is easily seen that D(u, v) = D(v, u) and uu∗ ∩ ww∗ = vv∗ ∩ ww∗ = {1Ω} for all
w ∈ D(u, v). Therefore from Lemma 2.3 it follows that
csu∗w ≤ 1 and csw∗v ≤ 1 (5.2)
for all s ∈ S. In particular, |u∗w| = |w∗v| = k.
Theorem 5.1. Given w ∈ D(u, v) the following statements hold:
(1) |u∗v| = k ⇔ u ∈ D(v, w) ⇔ v ∈ D(w, u),
(2) |ab ∩ u∗v| = 1 for all a ∈ u∗w and b ∈ w∗v.
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 15
Proof. To prove statement (1) suppose that |u∗v| = k. Then ctu∗v ≤ 1 for all t ∈ S.
So from Lemma 2.3 it follows that uu∗ ∩ vv∗ = {1Ω}. On the other hand, given a re-
lation s ∈ (vv∗ ww∗) ∩ uu∗ one can find points α, β ∈ Ω to have the configuration at
Fig. 2. So r(α, β) ∈ (uu∗ vv∗) ∩ ww∗ = {1Ω} whence it follows that α = β. There-
76540123
u
 



s

v //76540123
76540123 76540123β
w
 



v
^>̂>>>>>>>
76540123α
u
^>̂>>>>>>>
w //76540123
Figure 2:
fore s ∈ vv∗ ∩ uu∗ = {1Ω}. Thus s = 1Ω, and hence u ∈ D(v, w). Conversely, if
u ∈ D(v, w), then (vv∗ ww∗)∩uu∗ = {1Ω}. So vv∗ ∩uu∗ = {1Ω}, and hence |u∗v| = k
by Lemma 2.3. This completes the proof of the first equivalence in statement (1). The sec-
ond equivalence immediately follows from the first one by interchanging u and v because
D(u, v) = D(v, u).
To prove statement (2) let a ∈ u∗w and b ∈ w∗v. Then w ∈ ua∩vb∗. This implies that
|ua ∩ vb∗| ≥ 1, and hence |ab ∩ u∗v| ≥ 1. Thus it suffices to verify that |ab ∩ u∗v| ≤ 1.
To do this we need the following auxiliary statement.
Lemma 5.2. Given a relation s ∈ ab ∩ u∗v and points α, β, γ ∈ Ω such that r(α, β) = s,
r(α, γ) = a and r(γ, β) = b there exists a unique point δ ∈ Ω for which r(δ, α) = u,
r(δ, β) = v and r(δ, γ) = w (see Fig. 3).
76540123α
s







a
3
33
33
33
33
33
33
3
76540123δ
u
OO
v
xxqqq
qqq
qq w
&&MM
MMM
MMM
76540123β 76540123γ
b
oo
Figure 3:
Proof. Since a ∈ u∗w and b ∈ w∗v, there exist points λ, µ, ν such that r(λ, α) = u,
r(λ, β) = v, r(µ, α) = u, r(µ, γ) = w and r(ν, γ) = w, r(ν, β) = v (see Fig. 4). Now
r(µ, ν) ∈ (uu∗ vv∗) ∩ ww∗ = {1Ω}. Thus µ = ν. Denote this point by δ. Then for δ the
statement of the lemma holds. To prove the uniqueness we note if δ1 and δ2 are two points
forming Fig. 3, then the relation r(δ1, δ2) belongs to the set ww∗∩uu∗∩vv∗ = {1Ω}, and
hence δ1 = δ2.
16 Ars Math. Contemp. 5 (2012) 1–25
76540123λ u //
v
>
>>
>>
>>
> 76540123α
s
 


 a
>
>>
>>
>>
> 76540123µuoo
w
 



76540123β 76540123γ
b
oo
76540123ν
v
^>̂>>>>>>> w
@@
Figure 4:
To complete the proof of Theorem 5.1 suppose that ab ∩ u∗v ⊃ {s1, s2} with s1 6= s2.
Then there exist points α, γ, β1, β2 ∈ Ω, such that β1 6= β2, r(α, γ) = a and r(γ, βi) = b,
r(α, βi) = si for i = 1, 2. By Lemma 5.2 with s = si one can find a point δi for which
r(δi, α) = u, r(δi, β) = v and r(δi, γ) = w (see Fig. 5). Since the relation r(δ1, δ2)
76540123γ
b
wwppp
ppp
ppp
ppp
ppp
ppp
b
''NN
NNN
NNN
NNN
NNN
NNN
N
76540123β1 76540123δ1voo
w
CC
u
6
66
66
66
66
76540123δ2 v //
w
[[666666666
u





76540123β2
76540123α
a
OO
s1
ggNNNNNNNNNNNNNNNNNN
s2
77pppppppppppppppppp
Figure 5:
belongs to the set ww∗ ∩ uu∗ = {1Ω}, we have δ1 = δ2. Denote this point by δ. Then
r(δ, βi) = v. Since r(βi, γ) = b∗, r(δ, γ) = w and β1 6= β2, this implies that cwvb∗ ≥
2. So by equivalencity (X,Ω) and (2.8) we conclude that cbw∗v ≥ 2 which contradicts
to (5.2).
5.2 A one point fission
By means of splitting sets we are going to find explicitly the α0-fission of the scheme
(Ω, S) for any point α0 ∈ Ω. To do this for any relations u, v ∈ S set
S(u, v) = Sα0(u, v) = {s ∩ (α0u× α0v) : s ∈ u∗v}. (5.3)
It is easily seen that the union of relations from S(u, v) coincides with the set α0u× α0v.
Suppose that w ∈ D(u, v). Then from statement (2) of Theorem 5.1 it follows that
S(u, v) ⊂ S(u, v;w)∪ (5.4)
where S(u, v;w) = Sα0(u, v;w) = S(u,w) · S(w, v). Suppose, in addition, that |u∗v| =
k. Then any relation in S(u, v) is of cardinality k. Since the same is true for the relations
in S(u, v;w), we conclude that
(w ∈ D(u, v) & |u∗v| = k) ⇒ S(u, v) = S(u, v;w). (5.5)
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 17
In particular, in this case the relations from S(u, v;w) form a partition of the set α0u ×
α0v. For arbitrary u and v we will prove the latter only under the following additional
assumption: ⋂
a∈{u,v}
b∈{w,w′}
D(a, b) 6= ∅, w, w′ ∈ D(u, v). (5.6)
In this case obviously D(u, v) 6= ∅.
Lemma 5.3. Let u, v ∈ S# be such that (5.6) holds. Then the set S(u, v;w) forms a
partition of the set α0u × α0v, and this partition does not depend on the choice of the
relation w ∈ D(u, v).
Proof. Let w,w′ ∈ D(u, v). Then |u∗w| = |u∗w′| = |v∗w| = |v∗w′| = k. On the other
hand, due to (5.6) one can find a relation
t ∈ D(u,w) ∩D(u,w′) ∩D(v, w) ∩D(v, w′).
So from (5.5) it follows that
S(x, y) = S(x, y; t) = S(x, t) · S(t, y), x ∈ {u, v}, y ∈ {w,w′}. (5.7)
Let a ∈ S(u, t) and b ∈ S(t, v). Since obviously b∗ ∈ S(v, t) by (5.7) with (x, y) = (u,w)
and (x, y) = (v, w) we obtain
a · c ∈ S(u,w), b∗ · c ∈ S(v, w), c ∈ S(t, w).
So the element a · b ∈ S(u, v;w) has at least k different representations (one for each
choice of c) of the form a · b = (a · c)(c∗ · b) with c∗ · b ∈ S(w, v). Since |S(u,w)| =
|S(w, v)| = k this implies that |S(u, v;w)| = k. Thus S(u, v;w) is a partition of α0u ×
α0v and S(u, v;w) = S(u, v; t). Similarly, using equalities (5.7) with (x, y) = (u,w′)
and (x, y) = (v, w′) one can prove that S(u, v;w′) is a partition of α0u × α0v and that
S(u, v;w′) = S(u, v; t). Thus
S(u, v;w) = S(u, v; t) = S(u, v;w′)
and we are done.
By Lemma 5.3 we can define a uniquely determined partition of the set Ω0×Ω0 where
Ω0 = Ω \ {α0}, as follows
S0 = S0(α0) =
⋃
w∈D(u,v)
Sα0(u, v;w). (5.8)
It is easily seen that 1α0u ∈ S0 for all u ∈ S#. Therefore 1Ω0 ∈ S∪0 . Besides, since
obviously S(u, v;w)∗ = S(v, u;w) for all u, v, w, the partition S0 is closed with respect
to ∗. Finally, the condition (2.2) is satisfied for S = S0. Therefore if (Ω0, S0) is a co-
herent configuration, then it is semiregular. We will prove the former under the following
assumption:
D(u, v) ∩D(v, w) ∩D(w, u) 6= ∅ (5.9)
for all u, v, w ∈ S#. Below we set
S1(α0) = {{α0} × α0v : v ∈ S} ∪ {α0v × {α0} : v ∈ S}.
18 Ars Math. Contemp. 5 (2012) 1–25
Theorem 5.4. Let (Ω, S) be an equivalenced scheme satisfying conditions (5.6) and (5.9)
for all u, v ∈ S#. Then
Sα0 = S0(α0) ∪ S1(α0), α0 ∈ Ω.
In particular, the α0-fission of (Ω, S) is a semiregular coherent configuration on Ω0 the
fibers of which are α0u, u ∈ S.
Proof. It suffices to verify that (Ω0, S0) is a coherent configuration. Indeed, if it is so and
S′ = S0(α0) ∪ S1(α0), then obviously (Ω, S′) is a semiregular coherent configuration the
fibers of which are α0u, u ∈ S. Therefore due to (5.4) we have 1α0 ∈ S′ and S ⊂ (S′)∪.
By the minimality of the α0-fission this implies that
Sα0 ⊂ (S′)∪. (5.10)
On the other hand, it is easily seen that the set S(u, v), and hence the set S(u, v;w) =
S(u,w) · S(w, v) is contained in (Sα0)∪ for all u, v, w ∈ S. Therefore S′ ⊂ (Sα0)∪.
Together with (5.10) this shows that (Sα0)
∪ = (S′)∪. Thus Sα0 = S
′ and we are done.
Let us prove that (Ω0, S0) is a coherent configuration. We observe that due to (5.6)
Lemma 5.3 implies that S0 is a partition of Ω0 × Ω0. Thus it suffices to verify that if
b, c ∈ S0 with b · c 6= ∅, then b · c ∈ S0. However, for such b and c we have
b ⊂ α0u× α0v, c ⊂ α0v × α0w
for appropriate u, v, w ∈ S#. By condition (5.9) one can find
t ∈ D(u, v) ∩D(v, w) ∩D(w, u).
Since b = a1 ·a2 for some a1 ∈ S(u, v; t) and a2 ∈ S(v, w; t), this implies that |S(v, t)| =
|S(w, t)| = k where k is the valency of (Ω, S). So by statement (1) of Theorem 5.1 we
have w ∈ D(v, t). Therefore a∗2 ∈ S(v, t;w) and hence there exists a3 ∈ S(t, w) such that
c = a∗2 · a3. Thus
b · c = (a1 · a2) · (a∗2 · a3) = a1 · (a2 · a∗2) · a3 ∈ S(u,w; t).
This means that b · c ∈ S0 which completes the proof.
6 One point extension of an algebraic isomorphism
We keep the notation of Section 5. Let (Ω′, S′) be a scheme and let
ϕ : (Ω, S)→ (Ω′, S′), s 7→ s′
be an algebraic isomorphism. Then obviously (Ω′, S′) is an equivalenced scheme of va-
lency k, and
w ∈ D(u, v) ⇔ w′ ∈ D(u′, v′), u, v ∈ S#.
Let us fix a point α′0 ∈ Ω′. Take u, v ∈ S. Since cwuv = cw
′
u′v′ for all w ∈ S, the mapping ϕ
induces a bijection
ϕu,v : Sα0(u, v)→ Sα′0(u
′, v′), a 7→ a′
where a = s ∩ (α0u × α0v) and a′ = s′ ∩ (α′0u′ × α′0v′). Below we set S′(u′, v′) =
Sα′0(u
′, v′).
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 19
Lemma 6.1. Let u, v ∈ S# be such that (5.6) holds. Then for any relations w1, w2 ∈
D(u, v) we have
b1 · c1 = b2 · c2 ⇒ b′1 · c′1 = b′2 · c′2
for all bi ∈ S(u,wi) and ci ∈ S(wi, v), i = 1, 2.
Proof. Suppose that b1 ·c1 = b2 ·c2 where bi ∈ S(u,wi) and ci ∈ S(wi, v), i = 1, 2. Then
|u∗w1| = |u∗w2| = |v∗w1| = |v∗w2| = k. Besides, by (5.6) one can find a relation
t ∈ D(u,w1) ∩D(u,w2) ∩D(v, w1) ∩D(v, w2).
So from (5.5) it follows that
S(x, y; t) = S(x, t) · S(t, y), x ∈ {u, v}, y ∈ {w1, w2}. (6.1)
Take any a1 ∈ S(u, t). By (6.1) we have d1 := a∗1b1 ∈ S(t, w1) and d2 := a∗1 · b2 ∈
S(t, w2). Since w1 ∈ D(t, v), we also have a2 := d1 · c1 ∈ S(t, v). Thus
a1 · a2 = (a1 · d1) · (d∗1 · a2) = b1 · c1 = b2 · c2 = a1 · d2 · c2
whence it follows that c2 = d∗2 · a2 (Figure 6). By Theorem 5.1 this implies that
76540123w1
c1
=
==
==
==
==
=
76540123u
b1
@@










a1
//
b2
=
==
==
==
==
= 76540123t
d1
OO
a2
//
d2

76540123v
76540123w2
c2
@@










Figure 6:
b′1 · c′1 = (a1 · d1)′ · (d∗1 · a2)′ = a′1 · (d′1 · (d′1)∗) · a′2 = a′1 · a′2 =
(b2 · d∗2)′ · (d2 · c2)′ = b′2 · (d′2 · (d∗2)′) · c′2 = b′2 · c′2
and we are done.
Let us define a mapping ϕ0 : S0 → S′0 where S0 = Sα0 and S
′
0 = S
′
α′0
, as follows.
Take s ∈ S0. Then s ⊂ α0u× α0v for some u, v ∈ S. Set
sϕ0 =
{
sϕu,v , if |u∗v| = k or 1Ω ∈ {u, v},
s
ϕu,w
1 · s
ϕw,v
2 , otherwise,
where w ∈ D(u, v) and s1 ∈ S(u,w), s2 ∈ S(w, v) are such that s1 · s2 = s. By
Theorem 5.4 and Lemma 6.1 the mapping ϕ0 is a correctly defined bijection.
20 Ars Math. Contemp. 5 (2012) 1–25
Theorem 6.2. Let (Ω, S) be an equivalenced scheme satisfying conditions (5.6) and (5.9)
for all u, v ∈ S#, and ϕ : (Ω, S) → (Ω′, S′) an algebraic isomorphism. Then ϕ0 is the
(α0, α
′
0)-extension of ϕ.
Proof. We observe that relations (2.4) hold by statement (2) of Theorem 5.1. Therefore it
suffices to verify that
(b · c)ϕ0 = bϕ0 · cϕ0 , b, c ∈ S0, b · c 6= ∅. (6.2)
To do this take such relations b and c. Then there exist u, v, w ∈ S# such that
b ⊂ α0u× α0v, c ⊂ α0v × α0w.
By condition (5.9) one can find t ∈ D(u, v) ∩ D(v, w) ∩ D(w, u). Since b ∈ S0, there
exist a1 ∈ S(u, t) and a2 ∈ S(t, v) such that b = a1 · a2. However, |S(u, t)| = |S(t, v)| =
k. Therefore bϕ0 = aϕ01 · a
ϕ0
2 (if |u∗v| = k, then this follows from statement (2) of
Theorem 5.1; otherwise this immediately follows from the definition of ϕ0). On the other
hand, we have |S(v, t)| = |S(w, t)| = k. Therefore a∗2 ∈ S(v, t) and there exists a3 ∈
S(t, w) such that c = a∗2 · a3 (see Figure 7). As above one can see that cϕ0 = (a∗2)ϕ0 · a
ϕ0
3
76540123t
a3
7
77
77
77
77
77
7
a2
76540123u
a1
CC
b
//76540123v c //76540123w
Figure 7:
and that (a1 · a3)ϕ0 = aϕ01 · a
ϕ0
3 . Thus
(b · c)ϕ0 = (a1 · a2 · a∗2 · a3)ϕ0 = (a1 · a3)ϕ0 = a
ϕ0
1 · a
ϕ0
3 =
aϕ01 · a
ϕ0
2 · (a∗2)ϕ0 · a
ϕ0
3 = (a1 · a2)ϕ0 · (a∗2 · a3)ϕ0 = bϕ0 · cϕ0
which completes the proof.
7 Schurity and separability of equivalenced schemes
7.1 Schurity
The conclusion of Theorem 5.4 gives a sufficient condition for a scheme to be schurian.
Theorem 7.1. Let (Ω, S) be a scheme such that for each α ∈ Ω the coherent configuration
(Ω, Sα) is semiregular on Ω \ {α} and its fibers are αs, s ∈ S. Then (Ω, S) is a regular or
Frobenius scheme.
Proof. Let α ∈ Ω. Then by Theorem 2.1 the coherent configuration (Ω, Sα) is schurian,
and hence due to (2.3) any set αs, s ∈ S, is the orbit of the group Gα where G =
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 21
Aut(Ω, S). Since obviously Gα,β = idΩ for all α 6= β, it suffices to verify that the
group G is transitive. To do this we note that semiregularity of Gα on Ω \ {α} implies that
k := |Gα| = |αs|, α ∈ Ω, s ∈ S#. (7.1)
Let ∆ ∈ Orb(G,Ω). Since any orbit of G is a disjoint union of some orbits of the group
Gα, the number |∆| is divided by k if and only if α 6∈ ∆. However, this is impossible if
∆ 6= Ω. Thus G is transitive.
Let (Ω, S) be the scheme of an affine spaceA. Then from (4.3) it follows thatD(u, v) =
S# \ uv for all u, v ∈ S#. Therefore conditions (5.6) and (5.9) are satisfied whenever the
dimension ofA is at least 3. Thus in this case by Theorems 5.4 and 7.1 the scheme (Ω, S) is
schurian. Since the scheme is imprimitive, its automorphism group is a Frobenius group in
its natural permutation representation. Using properties of Frobenius groups one can prove,
without using the Veblen-Young Theorem, that the scheme (Ω, S) is an affine scheme of a
Desarguesian affine space.
7.2 Separability
Similarly to the previous subsection the conclusion of Theorem 6.2 gives a sufficient con-
dition for a scheme to be separable.
Theorem 7.2. In the condition of Theorem 7.1 the scheme (Ω, S) is separable.
Proof. From Theorem 6.2 it follows that any algebraic isomorphism ϕ : (Ω, S)→ (Ω, S′)
has the (α, α′)-extension
ϕα,α′ : (Ω, Sα)→ (Ω′, S′α′)
for all (α, α′) ∈ Ω×Ω′. By Theorem 5.4 the coherent configuration (Ω, Sα) is semiregular
on Ω \ {α}, and hence is separable (Theorem 2.1). This implies that the algebraic isomor-
phism ϕα,α′ is induced by an isomorphism. Due to the right-hand side of (2.4) this shows
that the same isomorphism induces the algebraic isomorphism ϕ. Thus any algebraic iso-
morphism of the scheme (Ω, S) is induced by an isomorphism and hence this scheme is
separable.
7.3 Pseudocyclic schemes
Let (Ω, S) be an equivalenced scheme of valency k and indistinguishing number c.
Lemma 7.3. |D(u, v)| < ck3, u, v ∈ S# where D(u, v) = S# \D(u, v).
Proof. Let u, v ∈ S#. Then it is easily seen that |uu∗ vv∗| ≤ k3. Besides, given t ∈
uu∗ vv∗, t ∈ S#, there exist at most c(t) − 1 ≤ c relations w ∈ S# such that t ∈ ww∗.
Thus for at most ck3 relations w the set (uu∗ vv∗) ∩ ww∗ contains an element t ∈ S#.
This means that |D(u, v)| < ck3.
Suppose that the scheme (Ω, S) is pseudocyclic. Then by Theorem 3.2 we have c =
k − 1. If, in addition, |S| ≥ 4ck3, then by Lemma 7.3 conditions (5.6) and (5.9) are
satisfied for all u, v ∈ S#. By Theorem 5.4 this implies that given α ∈ Ω the α-fission of
the scheme (Ω, S) is a semiregular coherent configuration on Ω \ {α} the fibers of which
are αu, u ∈ S. So by Theorems 7.1 and 7.2 we obtain the following statement.
Theorem 7.4. Any pseudocyclic scheme of valency k > 1 and rank at least 4(k − 1)k3 is
a separable Frobenius scheme.
22 Ars Math. Contemp. 5 (2012) 1–25
8 Miscellaneous
8.1 2-designs
Any commutative pseudocyclic scheme of of valency k on n points produces a 2−(n, k, k−
1)-design [4, Corollary 2.2.8]. The same is also true in the non-commutative case (Theo-
rem 8.1). It would be interesting to study these designs in detail.
Theorem 8.1. A scheme (Ω, S) on n points is pseudocyclic of valency k if and only if the
pair (Ω, B) with B = {αs : α ∈ Ω, s ∈ S#} is a 2− (n, k, k − 1)-design.
Proof. The pair (Ω, B) is an 2− (n, k, k − 1)-design if and only if |αs| = k for all α ∈ Ω
and s ∈ S#, and the number of blocks αs ∈ B containing two distinct points β, γ ∈ Ω
coincides with k− 1. However, the number of these blocks is obviously equals c(s) where
s = r(β, γ). Thus the required statement follows from Theorem 3.2.
8.2 Point fission
It was proved in [11, Lemma 5.13] that a one point fission of an imprimitive equivalenced
scheme is close to be semiregular. The following statement shows that the imprimitivity
condition can be removed for pseudocyclic schemes the rank of which is much more than
the valency.
Theorem 8.2. Let (Ω, S) be a pseudocyclic scheme of valency k. Suppose that |S| >
2k(k − 1) + 2. Then given α ∈ Ω the coherent configuration (Ω, Sα) is semiregular on
Ω \ {α}.
Proof. For a relation u ∈ S# set E(u) = {v ∈ S# : |u∗v| = k}. Since by Theorem 3.2
the indistinguishing number c of the scheme (Ω, S) is k − 1, we have
|S \ E(u)| =
∑
b∈uu∗\{1Ω}
|{v ∈ S : b ∈ vv∗}| ≤ |uu∗|c ≤ k(k − 1).
By the theorem hypothesis this implies that
|E(u) ∩ E(v)| ≥ |S| − 2(k − 1)k − 2 > 0 (8.1)
for all non-equal u, v ∈ S#. Set S0 = {s ∈ Sα : s ⊂ Ω0 ×Ω0} where Ω0 = Ω \ {α}. To
complete the proof it suffices to verify that each s0 ∈ S0 is contained in some s ∈ S∪0 for
which |βs| ≤ 1 for all β ∈ Ω. However, it is easy to see that given s0 ∈ S0 one can find
u, v ∈ S# such that
s0 ⊂ αu× αv.
Due to (8.1) there exists w ∈ E(u) ∩ E(v). Since Sα(u,w), Sα(w, v) ⊂ S∪0 , we have
Sα(u, v;w) ⊂ S∪0 . Thus s0 ⊂ s for some s ∈ Sα(u, v;w). To complete the proof it
suffices to note that |βs| ≤ 1 for β ∈ Ω.
By the assumptions of Theorem 8.2 we have |βs| ≤ 1 for all β ∈ Ω \ {α} and s ∈ Sα.
Therefore by [13, Theorem 9.3] we obtain the following statement.
Corollary 8.3. In the condition of Theorem 8.2 any one point fission of the scheme (Ω, S)
is schurian and separable.
We complete the subsection by making a remark that Corollary 8.3 together with [12,
Theorem 4.6] shows that any pseudocyclic scheme of valency k and rank O(k2) is 2-
schurian and 2-separable in the sense of [14].
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 23
8.3 Affine schemes
The following characterization of the affine schemes is known in commutative case (see [9]).
Theorem 8.4. Let (Ω, S) be a scheme with ns ≥ 3 for each s ∈ S#. Then it is the scheme
of an affine space if and only if ctrs ≤ 1 for all r, s, t ∈ S such that r 6= s∗.
Proof. The necessity follows from (4.3). To prove the sufficiency let s ∈ S#. Then
|ss∗| > 1 because ns > 1, and ss∗ ∩ rr∗ = {1Ω} for all r 6= s (Lemma 2.3). Thus
|S#| ≥ |
⋃
s∈S#
ss∗ \ {1Ω}| =
∑
s∈S#
|ss∗ \ {1Ω}| ≥ |S#|.
This implies that there exists a bijection s 7→ s′ from S# to itself such that ss∗ = {1Ω, s′}.
In particular, the scheme (Ω, S) is symmetric and css′s = ns − 1 ≥ 2. Therefore s′ = s for
each s ∈ S#. Thus each relation from S is an equivalence relation minus a diagonal. All
such schemes were classified in [9] where it was proved that each of them is the scheme of
an affine space.
8.4 QI-groups
A permutation groupG ≤ Sym(Ω) is called QI [7] if its permutation module QΩ is a direct
sum of a one dimensional module and an irreducible one, say (QΩ)0. Notice that (QΩ)0
consists of all vectors with zero sum of coordinates.
Let K be the splitting field of the group algebra Q[G]. Denote by X a full set of
irreducible K-representations appearing in the decomposition of (KΩ)0. Then the Galois
group of the extension K/Q acts transitively on X . This implies that the pair (nχ,mχ)
does not depend on χ ∈ X where nχ and mχ are respectively the degree and multiplicity
of χ. From this one can deduce that the scheme of the group G is pseudocyclic. Moreover,
by the second part of Theorem 3.2 this scheme is also commutative.
8.5 The Terwilliger algebra of a pseudocyclic scheme
Let (Ω, S) be an arbitrary scheme and let Tα(Ω, S) be the Terwilliger algebra of it at point
α ∈ Ω, i.e. the subalgebra of MΩ(C) generated by CS and the set of matrices A(1αs),
s ∈ S. It immediately follows that
Tα(Ω, S) ⊆ CSα
where CSα is the adjacency algebra of the scheme (Ω, Sα) (see Subsection 2.6), and that
equality holds exactly when the algebra in the left-hand side is closed with respect to the
Hadamard product.
Let G = Aut(Ω, S). As it was observed in [21] it is true that Tα(Ω, S) is always
contained in the centralizer algebra CGα of the one-point stabilizer Gα. However, even for
cyclotomic schemes this inclusion can be strict. On the other hand, due to (2.3) we have
CSα ⊆ CGα.
Thus from Theorem 7.4 and the above two inclusions it follows that the Terwilliger algebra
of the cyclotomic scheme of valency k and rank at least 4(k−1)k3 is coherent and coincides
with CGα.
24 Ars Math. Contemp. 5 (2012) 1–25
8.6 Equivalenced schemes with bounded indistinguishing number
Theorem 7.4 may be strengthened if we replace the condition of being pseudocyclic by
bounding of the indistinguishing number of a scheme. Indeed, the argument used in the
proof of Theorem 7.4 yields us that a k-valenced scheme with indistinguishing number c
of rank at least ck3 is a separable Frobenius scheme.
9 Acknowledgments
The authors are very grateful to P.-H. Zieschang who proposed an alternative proof of
Theorem 3.2. The first author would like to thank M.Klin for fruitful conversations. The
authors are thankful to an anonymous referee for valuable remarks.
References
[1] L. Babai, On the order of uniprimitive permutation groups, Annals of Math. 113 (1981), 553–
568.
[2] J. Bagherian and I. Ponomarenko, A. Rahnamai Barghi, On cyclotomic schemes over finite
near-fields, Journal of Algebraic Combinatorics 27 (2008), 173-185.
[3] J. L. Berggren, An algebraic characterization of finite symmetric tournaments, Bull. Austral.
Math. Soc. 6 (1972), 53–59.
[4] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-regular graphs, Ergebnisse der Math-
ematik und ihrer Grenzgebiete, 3. Folge, 18, Springer-Verlag, Berlin, 1989.
[5] F. Buekenhout and P. Cameron, Projective and affine geometry over division rings, in: F.
Buekenhout (ed.), Handbook of Incidence Geometry, Elsevier, Amsterdam, 1995, 27–62.
[6] P. J. Cameron, Permutation groups whose non-identity elements have k fixed points, J. Group
Theory 4 (2001), 45–51.
[7] P. Cameron, Synchronization and homomorphisms, http://www.maths.qmul.ac.uk/
˜pjc/slides/beamer/perthtalk1.pdf.
[8] C. W. Curtis and I. Reiner, Representation theory of finite groups and associative algebras, Pure
and Applied Mathematics 11 (1962), New York-London: Interscience Publishers, a division of
John Wiley & Sons.
[9] E. R. van Dam, A Characterization of Association Schemes from Affine Spaces, Designs,
Codes and Cryptography 21 (2000), 83-86.
[10] S. Evdokimov and I. Ponomarenko, Two inequalities for the parameters of a cellular algebra,
Zapiski Nauchnykh Seminarov POMI 240 (1997), 82–95, English translation in J. Math. Sci.,
New York 96 (1999), 3496–3504.
[11] S. Evdokimov and I. Ponomarenko, On primitive cellular algebras, Zapiski Nauchnykh Sem-
inarov POMI 256 (1999), 38–68, English translation in J. Math. Sci., New York 107 (2001),
4172–4191.
[12] S. Evdokimov and I. Ponomarenko, Separability Number and Schurity Number of Coherent
Configurations, Electronic J. Combin. 7 (2000), #R31.
[13] S. Evdokimov and I. Ponomarenko, Characterization of cyclotomic schemes and normal Schur
rings over a cyclic group, Algebra and Analysis 14 (2002), 11–55, English translation in St.
Petersburg Math. J. 14 (2003), 189–221.
[14] S. Evdokimov and I. Ponomarenko, Permutation group approach to association schemes, Eu-
ropean J. Combin. 30 (2009), 1456–1476.
M. Muzychuk and I. Ponomarenko: On pseudocyclic association schemes 25
[15] I. A. Faradžev, M. H. Klin, M. E. Muzychuk, Cellular rings and groups of automorphisms
of graphs, in: I.A. Faradžev et al. (eds): Investigations in algebraic theory of combinatorial
objects, Kluwer Acad. Publ., Dordrecht, 1994, 1–152 (translation from Russian edition 1985).
[16] Ja. Ju. Gol’fand, A. V. Ivanov and M. H. Klin, Amorphic cellular rings, in: I. A. Faradžev et al.
(eds.), Investigations in Algebraic Theory of Combinatorial Objects, Kluwer, Dordrecht, 1994,
167–186 (translation from Russian edition 1985).
[17] M. Hall, Jr., The theory of groups, The Macmillan Company, New York, 1959 (Russian trans-
lation, 1962).
[18] A. Hanaki and K. Uno, Algebraic structure of association schemes of prime order, J. Algebraic
Combin 23 (2006), 189–195.
[19] H. D. L. Hollmann, Q. Xiang, Pseudocyclic association schemes arising from the actions of
PGL(2, 2m) and PΓL(2, 2m), J. Combin. Theory, A113 (2006), 1008–1018.
[20] T. Ikuta, T. Ito and A. Munemasa, On pseudo-automorphisms and fusions of association
schemes, European J. Combin. 12 (1991), 317–325.
[21] H. Ishibashi, T. Ito and M. Yamada, Terwilliger Algebras of Cyclotomic Schemes and Jacobi
Sums, European J. Combin. 20 (1999), 397–410.
[22] M. Klin, M. Muzychuk, C. Pech, A. Woldar and P.-H. Zieschang, Association schemes on
28 points as mergings of a half-homogeneous coherent configuration, European J. of Combin.
28 (2007), 1994–2025.
[23] B. R. McDonald, Finite rings with identity, Pure and Applied Mathematics, Vol. 28, Marcel
Dekker Inc., New York, 1974.
[24] M. Muzychuk, I. Ponomarenko, On Pseudocyclic Association Schemes, arXiv:0910.0682v1
[math.CO] (2009), 1–23.
[25] D. V. Pasechnik, Skew-symmetric association schemes with two classes and strongly regular
graphs of type L2n−1(4n− 1), Acta Appl. Math. 29 (1992), 129–138.
[26] D. S. Passman, Solvable 3
2
-transitive permutation groups, J. Algebra 7 (1967), 192–207.
[27] D. Passman, Permutation groups, Benjamin, New York, 1968.
[28] B. Weisfeiler (Ed.), On the Construction and Identification of Graphs, in: Lect. Notes in Math.,
vol. 558, 1976.
[29] H. Wielandt, Finite permutation groups, Academic press, New York - London, 1964.
[30] P.-H. Zieschang, Theory of Association Schemes, Springer, Berlin & Heidelberg, 2005.