ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.02
https://doi.org/10.26493/1855-3974.2724.83d
(Also available at http://amc-journal.eu)
The search for small association schemes with
noncyclotomic eigenvalues*
Allen Herman † , Roghayeh Maleki ‡
Department of Mathematics and Statistics, University of Regina,
Regina Saskatchewan S4S 0A2, Canada
Received 9 November 2021, accepted 4 November 2022, published online 11 January 2023
Abstract
In this article we determine feasible parameter sets for (what could potentially be) com-
mutative association schemes with noncyclotomic eigenvalues that are of smallest possible
rank and order. A feasible parameter set for a commutative association scheme corresponds
to a standard integral table algebra with integral multiplicities that satisfies all of the pa-
rameter restrictions known to hold for association schemes. For each rank and involution
type, we generate an algebraic set for which any suitable integral solution corresponds to
a standard integral table algebra with integral multiplicities, and then try to find the small-
est suitable solution. The main results of this paper show the eigenvalues of association
schemes of rank 4 and nonsymmetric association schemes of rank 5 will always be cyclo-
tomic. In the rank 5 cases, the results rely on calculations done by computer for Gröbner
bases or for bases of rational vector spaces spanned by polynomials. We give several ex-
amples of feasible parameter sets for small symmetric association schemes of rank 5 that
have noncyclotomic eigenvalues.
Keywords: Association schemes, table algebras, character tables.
Math. Subj. Class. (2020): 05E30, 13P15
1 Introduction
This paper investigates the Cyclotomic Eigenvalue Question for commutative association
schemes that was posed by Simon Norton at Oberwolfach in 1980 [3]. This question asks if
*We would like to thank anonymous referees for carefully reading the manuscript and for their insightful
comments
†This author’s work was supported by an NSERC Discovery Grant.
‡Corresponding author.
E-mail addresses: allen.herman@uregina.ca (Allen Herman), rmaleki@uregina.ca (Roghayeh Maleki)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P3.02
the eigenvalues of all the adjacency matrices of relations in the scheme lie in a cyclotomic
number field, or equivalently if every entry of the character table (i.e., first eigenmatrix) of a
commutative association scheme is cyclotomic. Showing this is a straightforward exercise
for association schemes of rank 2 and 3. For commutative Schurian association schemes,
this property is a consequence of the character theory of Hecke algebras and the fact that
Morita equivalent algebras have isomorphic centers (see [9]). For commutative association
schemes that are both P - and Q-polynomial, it follows from the fact that the splitting field
of the scheme is quadratic extension of the rationals, a key ingredient of Bang, Dubickas,
Koolen, and Moulten’s proof of the Bannai-Ito conjecture ([2], see also [14]). Herman
and Rahnamai Barghi proved it for commutative quasi-thin schemes [12], which were later
shown by Muzychuk and Ponomarenko to always be Schurian [16]. Herman and Rahnamai
Barghi also showed the cyclotomic eigenvalue property holds for commutative association
schemes whose elements have valency ≤ 2 except for possibly one element of valency 3
and/or one element of valency > 4 [12, Theorem 3.3].
For association schemes in general we do not know if the character values have to be
cyclotomic, but we do have noncommutative examples for which the eigenvalues are not
cyclotomic – the smallest examples are two noncommutative Schurian association schemes
of order 26, and three noncommutative Schur rings of order 32 (in the latter case the corre-
sponding graphs are Cayley graphs on a nonabelian group of order 32).
In this article we investigate the cyclotomic eigenvalue question from a smallest coun-
terexample perspective. For a given rank and involution type, our approach will be to gen-
erate an algebraic set in a multivariate polynomial ring in variables corresponding to the
intersection numbers and character table parameters of such an association scheme. Each
suitable integer point in this algebraic set corresponds to a standard integral table algebra
with integral multiplicities (SITAwIM) that has the corresponding intersection matrices and
character table via its regular representation. We use the algebraic set to search for small
SITAwIMs of the given type that have some noncyclotomic eigenvalues.
The algebraic sets themselves are not easy to work with, as they are not monomial
and the number of variables and polynomial generators is too large for available computer
algebra systems to do efficient Gröbner basis calculations. After manually reducing the
algebraic sets with all available linear substitutions, we search for solutions by specifying
values for sufficiently many remaining parameters that the resulting algebraic set can be
resolved with a Gröbner basis calculation. Using this approach, we are able to show the an-
swer to the cyclotomic eigenvalue question is yes for all association schemes of rank 4 and
for both involution types of nonsymmetric association schemes of rank 5. For commutative
association schemes, the noncyclotomic eigenvalue property implies the Galois group of
the splitting field will be non-Abelian, and so there must be an orbit of size at least 3 in
its action on irreducible characters. We will say the Galois group acts k-point transitively
if the size of its largest orbit on irreducible characters is k. So for symmetric association
schemes of rank 5, noncylotomic eigenvalues can only occur when the Galois group of the
splitting field is 3- or 4-point transitive. When this action is 4-point transitive, the associ-
ation scheme will be pseudocyclic. This greatly reduces the number of cases we need to
consider, and our searches have been able to produce six feasible examples of orders less
than 1000, the smallest having order 249. When the action is 3-point transitive, the scheme
is not pseudocyclic, so the search space is much larger. We have been able to generate all
examples of order less than 100 and a few more with order less than 250, ten of which
satisfy all available feasibility criteria. The smallest of these feasible examples have order
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 3
35, 45, 76, and 93. From the partial classification of association schemes of order 35, we
know the order 35 example cannot be realized. The status of the larger feasible examples
is open.
2 Preliminaries
In this section, we review some background results that are needed in this work. Recall that
an involution ϕ of a finite-dimensional algebra A is a map ϕ : A → A such that ϕ◦ϕ = idA.
2.1 SITA parameters
An integral table algebra (A,B) is a finite-dimensional complex algebra A with distin-
guished basis B = {bi | i ∈ I = {0, 1, . . . , r − 1}} such that
(i) 1 ∈ B,
(ii) A has an involution ∗ : A → A that is additive, reverses multiplication, and acts as
complex conjugation on scalars,
(iii) B is ∗−invariant,
(iv) B produces non-negative integer structure constants (see 2.2),
(v) B satisfies the pseudo-inverse condition: for all bi, bj ∈ B, the coefficient of 1 in
bib
∗
j is positive if and only if bj = b
∗
i .
Note that since B∗ = B, the involution ∗ is a permutation of {0, 1, . . . , r − 1}. There-
fore, the action of the involution ∗ can be defined by (bi)∗ = bi∗ for all bi ∈ B.
In order to consider A as an algebra of square matrices over C, we identify the elements
of B with their left regular matrices in the basis B. The basis B is called standard when,
for all bi ∈ B, the coefficient of 1 in bib∗i is equal to the maximal eigenvalue of the regular
matrix bi. We refer to r = |B| as the rank of the table algebra, when the basis B is standard
we say that (A,B) is a standard integral table algebra, or SITA. The action of the involution
∗ on the basis B determines the involution type of the table algebra of a given rank.
The adjacency algebra of an association scheme is the prototypical example of a SITA,
as the defining basis of adjacency matrices is a standard basis. Conversely, the structure
constants determined by the basis of adjacency matrices of an association scheme deter-
mine a standard integral table algebra that is realizable as an association scheme. Many
open problems concerning missing combinatorial objects correspond to standard integral
table algebras that satisfy all the known conditions on their parameters for being realized
by an association scheme, but are yet to be actually constructed. We call such standard
integral table algebras (or their parameter sets) feasible.
Let P = (χi(bj))i,j be the character table of A with respect to the distinguished basis
B, whose rows are indexed by the irreducible characters of A and columns are indexed
by the basis B. As we can restrict ourselves to the commutative table algebras in this
paper, P will be an r × r matrix. We order the irreducible characters so that the entries
P0,j = χ0(bj) = δj , j = 0, 1, . . . , r − 1 are equal to the Perron-Frobenius eigenvalues of
the basis matrices (i.e., the degrees of standard basis elements, or in the association scheme
case, the valencies of the scheme relations). The order of a standard integral table algebra
4 Ars Math. Contemp. 23 (2023) #P3.02
is the sum of its degrees; that is, n =
∑r−1
j=0 δj . The multiplicity mi of each irreducible
character χi can be computed by the following formula [4]
r−1∑
j=0
|Pij |2
δj
=
n
mi
, for i = 0, 1, . . . , r − 1.
For table algebras, the multiplicity mi corresponds to the coefficient of χi when the stan-
dard feasible trace map ρ(
∑r−1
j=0 αjbj) = nα0 is expressed as a (positive) linear combina-
tion of the irreducible characters of A. We always have m0 = 1, but the other multiplicities
mi for i = 1, . . . , r−1 are only required to be positive real numbers. When the SITA is re-
alized by an association scheme, the standard feasible trace is the character corresponding
to the standard representation of the SITA, so the mi’s will be positive integers. This is just
one of the feasibility conditions for the parameters of an association scheme. In this way,
each feasible parameter set for association schemes determines a standard integral table
algebra with integral multiplicities, i.e., a SITAwIM.
A SITA is called pseudocyclic if its multiplicities mi for i > 0 are all equal to the
same positive constant m. By a result of Blau and Xu [18], pseudocyclic SITAs are also
homogeneous, that is, all degrees δi for i > 0 are equal to the same positive constant.
2.2 General conditions on SITA parameters
Let B = {b0, b1, ..., br−1} be the standard basis of a SITA (A,B). Denote the structure
constants relative to the basis B by (λijk)r−1i,j,k=0, so
bibj =
r−1∑
k=0
λijkbk, for all i, j ∈ {0, 1, . . . , r − 1}.
Let χ0(bi) = δi be the degree (or valency) of the basis element bi ∈ B, for all i ∈
{0, 1, . . . , r − 1}. When the algebra has a standard basis, we have δi = δi∗ = λi∗i0 (see
[5, Definition 1.3]).
Associativity of A and the pseudo-inverse condition on the standard basis can be used
to prove two general properties of the structure constants relative to B.
Lemma 2.1. For all i, j, k ∈ {0, 1, . . . , r − 1},
(i) λjki∗δi = λkij∗δj = λijk∗δk, and
(ii)
∑r−1
k=0 λjki = δj .
Proof. (i) By the associativity of multiplication we have the following condition on the
structure constants for all i, j, k, ℓ,m ∈ {0, 1, . . . , r − 1},∑
ℓ
λijℓλℓkm =
∑
ℓ
λiℓmλjkℓ
Now, fix k and let m = 0. Using the pseudo-inverse condition on B we have
λjki∗δi = λkij∗δj = λijk∗δk.
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 5
For (ii), we have that for all i, j ∈ {0, 1, . . . , r − 1}, bj∗bi =
∑r−1
k=0 λj∗ikbk =∑r−1
k=0 λi∗jk∗bk. Since χ0(b
∗
j ) = χ0(bj) and the degree map is an algebra homomorphism
from A to C, we have
δjδi = χ0(bj∗bi) =
r−1∑
k=0
λi∗jk∗δk,
which is equal by (i) to
∑r−1
k=0 λjkiδi. So, (ii) follows.
Note that Lemma 2.1(ii) tells us that every row sum of the left regular matrix of bj ∈ B
is equal to the constant δj .
Next, we consider restrictions on the parameters of a SITA imposed by its fusions. If
I ⊆ {1, . . . , r − 1}, we let bI =
∑
i∈I bi. When Λ = {{0}, I1, . . . , Is−1} is a partition of
{0, 1, . . . , r−1} for which BΛ = {b0, bI1 , . . . , bIs−1} is the basis of a table algebra (which
will automatically be the standard basis of a SITA in this case), then we say that BΛ is a
fusion of B, and conversely say that B is a fission of BΛ. The next lemma shows that every
SITA admits a rank 2 fusion.
Lemma 2.2. Every table algebra (A,B) with standard basis B = {b0, b1, . . . , br−1} of
rank r ≥ 3 has the trivial rank 2 fusion B{{0},{1,...,r−1}} = {b0, b1 + · · ·+ br−1}.
Proof. Let B+ =
∑r−1
j=0 bj . By [1] we have (B
+)2 = χ0(B
+)B+ = nB+. It follows that
((B−{b0})+)2 = nB+−2B++b0 = (n−2)B++b0 = (n−2)(B+−{b0})+(n−1)b0.
This implies {b0,B+ − b0} is a ∗-invariant subset of B that generates a 2-dimensional
subalgebra of A. The lemma follows.
The conditions imposed by fusion on the parameters of a commutative association
scheme were studied by Bannai and Song in [4]. For structure constants the conditions
are straightforward, for character table parameters the existence of a fusion imposes cer-
tain identities on partial row and column sums of P . Let Λ = {{0}, J1, . . . , Jd−1} be
the partition inducing the fusion BΛ = {b̃0, b̃J1 , . . . , b̃Jd−1} of our standard integral table
algebra basis B. If E = {e0, e1, . . . , er−1} is the basis of primitive idempotents of A,
then there is a (dual) partition Λ∗ = {{0},K1, . . . ,Kd−1} of {0, 1, . . . , r − 1}, unique
to the fusion, such that, if ẽ0 = e0 and ẽKi =
∑
k∈Ki ek for i = 1, . . . , d − 1, then
Ẽ = {ẽ0, ẽK1 , . . . , ẽKd−1} is the basis of primitive idempotents of the algebra CBΛ.
Let P̃ be the character table of the fusion BΛ, so the rows of P̃ are indexed by the
irreducible characters χ̃I for I ∈ Λ∗, and the columns of P̃ are indexed by the basis
elements bJ for J ∈ Λ. Let δ̃ = χ̃0 and δ = χ0 be the respective degree maps. Let
δ̃(bJ) = k̃J for all J ∈ Λ, and δ(bj) = kj for all j ∈ {1, . . . , r − 1}. Let m̃I and mi
denote the multiplicities of χ̃I and χi, respectively. Then we have the following identities
on partial row and column sums.
Theorem 2.3 (Theorem 1.4, [4]). Let J ∈ Λ and I ∈ Λ∗.
(i) For all j ∈ J ,
∑
i∈I miPi,j =
kjm̃I
k̃J
P̃I,J .
(ii) For all i ∈ I , then P̃I,J =
∑
j∈J Pi,j .
6 Ars Math. Contemp. 23 (2023) #P3.02
Proof. (i) We are assuming ẽI =
∑
i∈I ei. Using the formula for primitive idempotents in
a standard table algebra [1],
ẽI =
m̃I
n
∑
J
P̃I,J
k̃J
b̃∗J =
∑
J
∑
j∈J
m̃I P̃I,J
nk̃J
b∗j .
On the other hand,
ẽI =
∑
i∈I
ei =
∑
i∈I
mi
n
∑
j
Pi,j
kj
b∗j
=
∑
J
∑
j∈J
∑
i∈I
miPi,j
nkj
b∗j .
Therefore, for all j ∈ J ,
∑
i∈I miPi,j =
kjm̃I
k̃J
P̃I,J , as required.
(ii) When χi(b0) = 1, we have bjei = Pi,jei for all bj ∈ B. On the one hand,
b̃J ẽI = P̃I,J ẽI =
∑
i∈I
P̃I,Jei,
and on the other hand, assuming χi(b0) = 1 for all i ∈ I ,
b̃J ẽI =
∑
j∈J
∑
i∈I
bjei =
∑
i∈I
∑
j∈J
Pi,jei.
Therefore, P̃I,J =
∑
j∈J Pi,j for all i ∈ I .
We remark that the fusion condition (i) on partial column sums holds without change
for noncommutative table algebras. Note that standard character considerations tell us∑
j∈J mjχj(b0) = m̃J . Condition (ii) on partial row sums holds for the rows of P̃ indexed
by the χ̃I for which χi(b0) = 1 for all i ∈ I .
2.3 The splitting field and its Galois group
If (A,B) is a commutative integral table algebra with standard basis B = {b0, b1, . . . , br−1}
then the splitting field of (A,B) is the field K obtained by adjoining all the eigenvalues of
the regular matrices of elements of B to the rational field Q, or equivalently, the smallest
field K for which the character table P lies in Mr(K), the algebra of r × r matrices over
the field K. As each bj in B is a nonnegative integer matrix, K is also the unique mini-
mal Galois extension of Q that splits the characteristic polynomials of every bj ∈ B. Let
G = Gal(K/Q) be the Galois group of this splitting field. Since the irreducible characters
of A are also irreducible representations of A in the commutative case, G will act faithfully
on the set of irreducible characters of A via χσi (bj) = (χi(bj))
σ , for all χi ∈ Irr(A),
bj ∈ B, and σ ∈ G. In this way G permutes the rows of the character table P , as well
as the corresponding multiplicities. For SITAwIMs this means G can only permute sets of
irreducible characters with the same multiplicity.
By the Kronecker-Weber theorem, a necessary and sufficient condition for (A,B) to
be a standard integral table algebra with noncyclotomic character values is for this Galois
group G to be non-abelian. If G is non-abelian, the fact that the action of G on irreducible
characters of A is faithful forces there to be at least one orbit of size 3 or more.
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 7
Theorem 2.4 ([15]). Let (A,B) be an integral table algebra (possibly noncommutative).
Let H be the subset of G = Gal(K/Q) consisting of elements σ ∈ G whose action on the
character table P = (χ(b))χ,b can be realized by a permutation of the basis, that is, for all
b ∈ B there exists bσ ∈ B such that for all χ ∈ Irr(A), (Pχ,b)σ = χ(bσ) = Pχ,bσ . Then
H is a central subgroup of G.
Proof. To see that H is a subgroup of G, let σ, τ ∈ H , χ ∈ Irr(A), and b ∈ B. Then,
(Pχ,b)
στ = ((Pχ,b)
σ)τ = (Pχ,bσ )
τ = (Pχ,bστ ).
Therefore, στ ∈ H . Since G is finite, H is a subgroup. To see that H is central, let τ ∈ H ,
σ ∈ G, χ ∈ Irr(A), and b ∈ B. Then,
(Pχ,b)
στ = (Pχσ,b)
τ = (Pχσ,bτ ) = (Pχ,bτ )
σ = ((Pχb)
τ )σ = (Pχ,b)
τσ.
As the action of G on the rows of P is faithful, this implies στ = τσ, so H is contained in
Z(G).
Note that the above theorem always applies to commutative table algebras that are not
symmetric.
Corollary 2.5. Suppose (A,B) is a commutative table algebra that is not symmetric. Then
the restriction of complex conjugation to K is a nonidentity element of the center of G.
Proof. Commutative table algebras that are not symmetric always have at least one irre-
ducible character that is not real-valued. If otherwise, the identity χi(b∗j ) = χi(bj), for all
χi ∈ Irr(A) and bj ∈ B, would imply the character table P would not be invertible. For the
irreducible characters that are not real-valued, the restriction of complex conjugation to K
will be a non-identity element of G that is realized by the permutation of B corresponding
to the involution. By Theorem 2.4, this element lies in the center of G.
2.4 Algebraic sets for SITAwIMs of a given rank and involution type.
As indicated in the introduction, we will obtain our results by searching for suitable non-
negative integer points in an algebraic set (i.e., the solution set to a system of polynomial
equations) that is determined by the parameters of SITAwIMs of a given rank and invo-
lution type. To illustrate how the generating sets for the ideals corresponding to these
algebraic sets are produced, we give the type 4A1 case as an example. This is the algebraic
set corresponding to rank 4 SITAwIMs whose basis B contains one asymmetric pair, i.e.,
B = {b0, b1, b2, b∗2}. Using the properties of the involution, the row sum property, com-
mutativity of the algebra, and the fact that bibj =
∑3
k=0 λijkbk, the general form of the
regular matrices for the nontrivial elements of this basis is
8 Ars Math. Contemp. 23 (2023) #P3.02
b1 =

0 k1 0 0
1 k1 − 2x1 − 1 x1 x1
0 k1 − x2 − x3 x2 x3
0 k1 − x2 − x3 x3 x2
 ,
b2 =

0 0 0 k2
0 x1 k2 − x1 − x4 x4
1 x2 k2 − x2 − x5 − 1 x5
0 x3 k2 − x3 − x5 x5
 ,
b∗2 =

0 0 k2 0
0 x1 x4 k2 − x1 − x4
0 x3 x5 k2 − x3 − x5
1 x2 x5 k2 − x2 − x5 − 1
 .
Identifying entries in the matrix equations resulting from the identities that define the regu-
lar representation gives several linear and quadratic identities in the variables x1, . . . , x5, k1,
k2, each of which corresponds to a multivariate polynomial equaling 0. For example, iden-
tifying entries on both sides of the matrix equation
b1b2 = x1b1 + x2b2 + x3b
∗
2
gives a list of 8 polynomials:
−x2k2 + x4k1,
−x1k1 − x3k2 − x4k1 + k1k2,
−x1x3 − x2x4 + x23 − x3x4 + 2x3x5 − x3k2 + x4k1,
x1x3 − x1k1 + x2x4 − x2k2 − x23 + x3x4 − 2x3x5 − x4k1 + k1k2,
−x1x2 + x2x3 − x2x4 − x3x4 + 2x3x5 − x3k2 + x4k1 + x3,
x1x2 − x1k1 − x2x3 + x2x4 − x2k2 + x3x4 − 2x3x5 − x4k1 + k1k2 − x3,
−x21 + x1x3 − 2x1x4 + 2x1x5 − x2x4 + x3x4 − x3k2 + x4k1 − x4 + k2, and
x21 − x1x3 + 2x1x4 − 2x1x5 − x1k1 + x2x4 − x2k2 − x3x4 − x4k1 + k1k2 + x4 − k2.
We get similar lists of polynomials from the defining identities for b21, b1b
∗
2, b
2
2, b2b
∗
2, and
(b∗2)
2, and possibly still more from the commuting identities b1b2 = b2b1, b1b∗2 = b
∗
2b1,
and b2b∗2 = b
∗
2b2. In the type 4A1 case, up to sign, this process produces 16 distinct
polynomials.
When we add the integral multiplicities condition, it leads to extra trace identities that
can be added to our list. For each choice of multiplicities mi ∈ Z+, i = 1, . . . , r − 1, we
have an identity satisfied by our character table P resulting from the column orthogonality
relation:
kj +
r−1∑
i=1
miPi,j = 0.
In light of assumptions we can make regarding the Galois group, certain rows of P
will be Galois conjugate, and the sums of Pi,j’s corresponding to these rows have to be
rational algebraic integers, and thus integers. The multiplicities corresponding to Galois
conjugate rows are the same. Summing these rows of P gives the rational character table,
an integer matrix satisfying certain column and row orthogonality conditions. The entries
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 9
in each column of this matrix are bounded in terms of the first entry kj of the column, so
we can search for the possible rational character tables for a given choice of multiplicities.
For each possible rational character table, we can add linear trace identities
tr(bj) = kj +
r−1∑
i=1
Pi,j , j = 1, . . . , r − 1,
to our list of polynomials.
Let S be the set of polynomials produced by this process. Let I be the ideal gener-
ated by S, and let V(I) be the corresponding algebraic set. The regular matrices of any
SITAwIM of type 4A1 with the given choice of multiplicities corresponds naturally to a
point in V(I) with x1, . . . , x5 ∈ N and k1, k2 ∈ Z+. We will refer to this as a suitable in-
tegral point in the algebraic set. Conversely, any suitable integral point in V(I) corresponds
to a SITAwIM of this rank, involution type, and choice of multiplicities.
For example, if we assume m1 = m2 = m3 in the type 4A1 case, it adds the trace
identities tr(bj) = kj − 1 for j = 1, 2, 3, all of which reduce to x1 = x2. Since this pseu-
docyclic assumption implies the SITA is homogeneous, we also get m1 = k1 = k2. Other
linear identities, or ones that become linear after cancelling one of our nonzero degrees kj ,
can also be used to reduce the number of variables we need to consider. For example, in
the type 4A1 case, one of the elements of S is k2(k2 − 1− x2 − 2x5), so we can substitute
x2 = k2 − 1 − 2x5 and reduce the number of variables by one. After we reduce by all
available linear substitutions in the type 4A1 case, only one polynomial remains:
f(x5, k1) = 36x
2
5 − 24x5k1 + 4k21 + 32x5 − 11k1 + 7.
Putting this together with our linear substitutions, we can conclude that any pseudocyclic
SITAwIM of type 4A1 corresponds, via the above regular matrices, to an integer point
(x1, x2, x3, x4, x5, k1, k2) for which f(x5, k2) = 0, x5 ≥ 0, k1 = k2 > 0, x1 = x2 =
x4 = k1 − 2x5 − 1 ≥ 0, and x3 = 4x5 − k1 + 2 ≥ 0. This is an effective formula to
generate pseudocyclic SITAwIMs of type 4A1.
We refer the readers to [10] for the GAP implementation that produces the defining list
of polynomials for rank 4 and 5 SITAwIMs of each involution type.
3 Rank 4 SITAwIMs have cyclotomic eigenvalues
In this section we show that rank 4 SITAwIMs have cyclotomic eigenvalues. In this case
there are two involution types to consider: type 4A1 and type 4S.
Proposition 3.1. Rank 4 SITAwIMs with one asymmetric pair of standard basis elements
have cyclotomic eigenvalues. In fact, their eigenvalues lie in quadratic number fields.
Proof. Suppose (A,B) is a SITAwIM of rank 4 with B = {b0, b1, b2, b∗2}. If there were
nonidentity elements of B with noncyclotomic eigenvalues, the Galois group G of the
splitting field K would have to be 3-point transitive; i.e., a transitive subgroup of the group
Sym({χ1, χ2, χ3}). Since G would have to be non-abelian, it would have to be isomorphic
to S3. But |Z(G)| > 1 by Corollary 2.5, so this is a contradiction.
Since there are no 3-transitive groups with a central element of order 2, we can conclude
that G is cyclic of order 2, and therefore K is a quadratic extension of Q.
Theorem 3.2. Symmetric rank 4 SITAwIMs have cyclotomic eigenvalues.
10 Ars Math. Contemp. 23 (2023) #P3.02
Proof. Suppose (A,B) is a symmetric SITAwIM of rank 4 that has noncyclotomic eigen-
values. If G is the Galois group of its splitting field K, then as in the rank 4 one asymmetric
pair case, G must act as the full symmetric group on the set {χ1, χ2, χ3}. In particular, this
implies these three characters have the same multiplicity m. Therefore, n = 1 + 3m and
the character table P of (A,B) has the form
b0 b1 b2 b3 multiplicities
χ0 1 δ1 δ2 δ3 1
χ1 1 α1 β1 γ1 m
χ2 1 α2 β2 γ2 m
χ3 1 α3 β3 γ3 m
where {δ1, α1, α2, α3}, {δ2, β1, β2, β3}, and {δ3, γ1, γ2, γ3} are the eigenvalues of b1, b2,
and b3, respectively. If we apply Theorem 2.3(i) to the column of P labeled by b1, we get
m(α1 + α2 + α3) =
δ1
n− 1
(n− 1)(−1), so α1 + α2 + α3 =
−δ1
m
.
Since α1 + α2 + α3 is an algebraic integer, we must have that m divides δ1. Similarly m
divides δ2 and δ3. Since δ1 + δ2 + δ3 = n− 1 = 3m we must have δ1 = δ2 = δ3 = m.
Assume α1 is a noncyclotomic eigenvalue of b1. Since δ1 is an integral eigenvalue of b1,
the minimal polynomial µα1(x) of α1 in Q[x] will be a divisor of (x−α1)(x−α2)(x−α3).
If the degree of µα1(x) is 1 or 2, it would follow that α1 is rational or lies in a quadratic
extension of Q, which runs contrary to our assumption that it is not cyclotomic. So (x −
α1)(x−α2)(x−α3) is the minimal polynomial of α1 in Q[x]. This implies Q(α1, α2, α3)
is the splitting field of α1 over Q. Since α1 is not cyclotomic, this has to be an extension
of Q with [Q(α1, α2, α3) : Q] = 6. Since Q(α1, α2, α3) ⊆ K and [K : Q] = |G| = 6, we
must have K = Q(α1, α2, α3).
Now consider the left regular matrices of b1, b2, b3 in the basis B. For convenience we
write these in this form:
b1 =

0 m 0 0
1 u x1 x4
0 v x2 x5
0 w x3 x6
 , b2 =

0 0 m 0
0 x1 u
′ x7
1 x2 v
′ x8
0 x3 w
′ x9
 , b3 =

0 0 0 m
0 x4 x7 u
′′
0 x5 x8 v
′′
1 x6 x9 w
′′
 ,
where the u, v, and w entries are determined by the row sum criterion. Applying the
structure constant identities which define the left regular matrices produces one polynomial
identity in the variables x1, . . . , x9,m for each entry of the product bibj for i, j ∈ {1, 2, 3}.
Since B is pseudocyclic, we have three more trace identities. On the one hand, we
have tr(b1) = u + x2 + x6 = (m − 1 − x1 − x4) + x2 + x6, and on the other, tr(b1) =
δ1 + α1 + α2 + α3 = m + α1 + α2 + α3 = m − 1, so we can restrict our algebraic set
by adding the polynomial x2 + x6 − x1 − x4 to our list. Similar identities coming from
tr(b2) = m− 1 and tr(b3) = m− 1 show we can add the polynomials x1 + x9 − x2 − x8
and x4 + x8 − x6 − x9 to our list.
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 11
Next, we reduce our list of polynomials using all available linear substitutions and
obtain
x1 = v = m− x2 − x5 x6 = u′′ = m− x4 − x7
x2 = u
′ = m− x1 − x7 x8 = w′ = m− x3 − x9
x3 = x5 = x7 x9 = v
′′ = m− x5 − x8.
x4 = w = m− x3 − x6
This implies the matrix of b1 is
b1 =

0 m 0 0
1 u x1 x4
0 x1 x2 x3
0 x4 x3 x6
 ,
so by the row sum criterion x1 + x2 + x3 = x4 + x3 + x6 = m, which implies x1 + x2 =
x4 + x6. Since the identity we obtained by considering tr(b1) was x1 + x4 = x2 + x6, we
must conclude that x4 = x2 and hence x6 = x1. Similarly, we see that the matrix of b2 is
b2 =

0 0 m 0
0 x1 x2 x3
1 x2 v
′ x8
0 x3 x8 x9
 ,
therefore, x3 + x8 + x9 = m and we must have x1 + x2 = x8 + x9. Comparing this to
the identity x1 + x9 = x2 + x8 obtained by considering tr(b2), we see that x9 = x2 and it
then follows that x8 = x1.
Therefore, we have
b1 =

0 m 0 0
1 x3 − 1 x1 x2
0 x1 x2 x3
0 x2 x3 x1
 , b2 =

0 0 m 0
0 x1 x2 x3
1 x2 x3 − 1 x1
0 x3 x1 x2
 , and
b3 =

0 0 0 m
0 x2 x3 x1
0 x3 x1 x2
1 x1 x2 x3 − 1
 .
If we take Q to be the permutation matrix
Q =

1 0 0 0
0 0 1 0
0 0 0 1
0 1 0 0
 ,
then we have Q−1b1Q = b2, Q−1b2Q = b3, and Q−1b3Q = b1. It follows that the regular
matrices of b1, b2, and b3 have the same characteristic polynomial, and that the Galois group
G has a nontrivial central element of order 3 that permutes the corresponding columns in
the character table. But this is contrary to G being isomorphic to S3. We conclude that for
symmetric SITAwIMs of rank 4, the eigenvalues of basis elements must be cyclotomic.
Corollary 3.3. All association schemes of rank 4 have cyclotomic eigenvalues.
12 Ars Math. Contemp. 23 (2023) #P3.02
4 Rank 5 SITAwIMs
For rank 5 SITAwIMs we have three involution types to consider: type 5S, type 5A1, and
type 5A2.
4.1 Type 5A2
Theorem 4.1. Every rank 5 SITAwIM (A,B) with B = {b0, b1, b∗1, b3, b∗3} has cyclotomic
eigenvalues.
Proof. Let B = {b0, b1, b∗1, b3, b∗3} be the standard basis of a SITAwIM of rank 5, with
character table P , splitting field K, and Galois group G = Gal(K/Q). As the table
algebra is not symmetric, we know by Corollary 2.5 that G has a central element of order
2. If the character table P has a noncyclotomic entry, then G must also be a 3- or 4-point
transitive non-Abelian subgroup of Sym({χ1, χ2, χ3, χ4}), so the only possibility is for
G ≃ D4, the dihedral group of order 8. This implies the action of G on the last 4 rows of
P is 4-transitive, and so we must have that the multiplicities m1, m2, m3, and m4 are all
equal to the same positive integer m. So as in the symmetric rank 4 case, this implies the
table algebra is homogeneous: δ1 = δ2 = δ3 = δ4 = m.
This implies our regular matrices of B will have this pattern:
b1 =

0 0 m 0 0
1 x1 m− 1− x1 − x5 − x9 x5 x9
0 x2 m− x2 − x6 − x10 x6 x10
0 x3 m− x3 − x7 − x11 x7 x11
0 x4 m− x4 − x8 − x12 x8 x12
 ,
b∗1 =

0 m 0 0 0
0 m− x2 − x6 − x10 x2 x10 x6
1 m− 1− x1 − x5 − x9 x1 x9 x5
0 m− x4 − x8 − x12 x4 x12 x8
0 m− x3 − x7 − x11 x3 x11 x7
 ,
b3 =

0 0 0 0 m
0 x5 x10 x13 m− x5 − x10 − x13
0 x6 x9 x14 m− x6 − x9 − x14
1 x7 x12 x15 m− 1− x7 − x12 − x15
0 x8 x11 x16 m− x8 − x11 − x16
 ,
b∗3 =

0 0 0 m 0
0 x9 x6 m− x6 − x9 − x14 x14
0 x10 x5 m− x5 − x10 − x13 x13
0 x11 x8 m− x8 − x11 − x16 x16
1 x12 x7 m− 1− x7 − x12 − x15 x15
 .
In addition to the set of polynomial identities in the variables x1, . . . , x16,m we obtain
by applying the structure constant identities to these regular matrices, we again have the ad-
ditional trace identities coming from tr(b1) = tr(b3) = m− 1, which adds the polynomial
identities
x1 + x7 + x12 + 1 = x2 + x6 + x10 and x5 + x9 + x15 + 1 = x8 + x11 + x16
to our list. The result is a list of 13 distinct polynomial generators, up to sign, for an ideal
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 13
of Q[x1, . . . , x16,m]. The available linear substitutions are:

x16 = 2m− 6x1 − x2 − 2,
x15 = x1,
x14 = x8 = 3x1 + x2 + x3 + 1−m,
x13 = x11 = 2x1 − x3 + 1,
x12 = x9 = x7 = x5 =
m− 1
2
− x1,
x10 = x3,
x6 = x4 = m− x1 − x2 − x3,
(4.1)
so the reduced ideal now lies in Q[x1, x2, x3, x4,m]. With the above substitutions, the
regular matrices have this pattern:
b1 =

0 0 m 0 0
1 x1 x1 x5 x5
0 x2 x1 x4 x3
0 x3 x5 x5 x11
0 x4 x5 x8 x5
 , b3 =

0 0 0 0 m
0 x5 x3 x11 x5
0 x4 x5 x8 x5
1 x5 x5 x1 x1
0 x8 x11 x16 x1
 .
When we substitute x16 = x2 + y for an extra variable y, then reduce using the identities
in (4.1) and calculate the Gröbner basis for the resulting ideal with respect to an ordering
of variables with y maximal, we find that y2 is one of the elements of the basis.
Therefore, x16 must be equal to x2 for all points in our algebraic set. Substituting x2
for x16 in the first equation of (4.1) gives x2 = m− 3x1 − 1, substituting this into the last
equation makes x4 = 2x1 − x3 + 1 = x11, and substituting x2 = m − 3x1 − 1 into the
third equation gives us x8 = x3. Hence b1 and b3 have the same characteristic polynomial,
so they have the same eigenvalues. Consequently, b∗1 and b
∗
3 have the same four eigenvalues
as b1. This implies the Galois group of the splitting field will act transitively on the last
four columns of the character table, hence the Galois group will be Abelian. It follows that
any rank 5 SITAwIM whose standard basis has two distinct asymmetric pairs must have
cyclotomic eigenvalues.
4.2 Type 5A1
Theorem 4.2. Every SITAwIM (A,B) of involution type 5A1 has cyclotomic eigenvalues.
Proof. Let B = {b0, b1, b2, b3, b∗3} be the basis of a SITAwIM of type 5A1. By Corol-
lary 2.5, complex conjugation will be realized by a central element of the Galois group G
of the splitting field K of QB. If the character table P has an entry which is not cyclo-
tomic, then as in the type 5A2 case, we must have that G ≃ D4 and acts 4-transitively on
{χ1, χ2, χ3, χ4}. It follows that our SITAwIM (A,B) is both pseudocyclic and homoge-
neous.
14 Ars Math. Contemp. 23 (2023) #P3.02
This implies that the pattern for our regular matrices in this case will be:
b1 =

0 m 0 0 0
1 m− 1− x1 − 2x5 x1 x5 x5
0 m− x2 − 2x6 x2 x6 x6
0 m− x3 − x7 − x8 x3 x7 x8
0 m− x4 − x8 − x7 x4 x8 x7
 ,
b2 =

0 0 m 0 0
0 x1 m− x1 − 2x9 x9 x9
1 x2 m− 1− x2 − 2x10 x10 x10
0 x3 m− x3 − x11 − x12 x11 x12
0 x4 m− x4 − x11 − x12 x12 x11
 ,
b3 =

0 0 0 0 m
0 x5 x9 x13 m− x5 − x9 − x13
0 x6 x10 x14 m− x6 − x10 − x14
1 x7 x11 x15 m− 1− x7 − x11 − x15
0 x8 x12 x16 m− x8 − x12 − x16
 ,
b∗3 =

0 0 0 m 0
0 x5 x9 m− x5 − x9 − x13 x13
0 x6 x10 m− x6 − x10 − x14 x14
0 x8 x12 m− x8 − x12 − x16 x16
1 x7 x11 m− 1− x7 − x11 − x15 x15
 .
In addition to the polynomial identities obtained by applying the structure constant iden-
tities to these regular matrices, we again have three extra trace identities coming from
tr(b1) = tr(b2) = tr(b3) = m− 1:
x1+2x5 = x2+2x7, x1+2x11 = x2+2x10, and x5+x10+x15+1 = x8+x12+x16.
In addition to these, the other available linear substitutions, including those that become
linear after we cancel m > 0, are:
x16 = m− x8 − x12 − x15
x14 = x12 = m− x6 − x10 − x11
x13 = x8 = m− x5 − x6 − x7
x9 = x6 = x4 = x3 =
m
2
− x1
x2 = x1.
Since we have the identity x3 = m2 − x1, integrality of x3 and x1 implies m = 2k is
even. Making as many substitutions as possible, we can leave ourselves with a set of 11
nonlinear polynomials in Q[x1, x5, x15,m]. Using a computer, we calculate the Gröbner
basis of the ideal generated by these 11 polynomials, with m and x15 of highest weight.
If we set y = x15, the first polynomial in this Gröbner basis is the following element of
Q[m, y]:
W (y,m) =
1
5184
(5184y4 − 5184y3m+ 1944y2m2 − 324ym3 + 81
4
m4 + 7776y3
− 6160y2m+ 1622ym2 − 142m3 + 4292y2 − 2392ym+ 330m2
+ 1032y − 304m+ 91).
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 15
This means 5184 ·W (y,m) is an integer polynomial that must have a nonnegative solution
with y an integer and m an even integer. But when we substitute m = 2k, 5184 ·W (y, 2k)
has the form 2Q(y, k) + 1 for some polynomial Q(y, k) ∈ Z[y, k], and it is impossible
for Q(y, k) = − 12 to have an integral solution. This implies there are no pseudocyclic
SITAwIMs of involution type 5A1. In particular this means we can conclude that all rank
5 SITAwIMs whose standard basis has exactly one asymmetric pair will have cyclotomic
eigenvalues.
Corollary 4.3. The cyclotomic eigenvalue property holds for every nonsymmetric rank 5
association scheme.
4.3 Type 5S
If (A,B) is a symmetric rank 5 SITAwIM with noncyclotomic eigenvalues, the action of
the Galois group G = Gal(K/Q) of the splitting field K on the irreducible characters of
A will either be 3- or 4-point transitive. We begin with the 4-point transitive case.
4.3.1 Type 5S with 4-point transitive Galois group
Again in this case we deduce that (A,B) is pseudocyclic and homogeneous from G being
4-point transitive. In addition to the polynomial identities obtained by applying the struc-
ture constant identities to our regular matrices, we also have four trace identities coming
from tr(b1) = tr(b2) = tr(b3) = tr(b4) = m − 1. Altogether our initial list consists
of 124 polynomials in 25 variables. By applying all available linear substitutions, we can
reduce to a list of 21 polynomials in Q[x1, x2, x3, x5, x7, x14, x15,m]. Along the way our
first trace identity reduces to
2(x3 + x5 + x14 − x23) = m,
so we can conclude that m must be even. The Gröbner basis of this ideal generated by these
21 polynomials can be calculated in a few hours on our desktop implementation of GAP
[6], but is too complicated for any easy interpretation. Instead, reducing to a basis of the
rational span of these 21 polynomials leaves us with just 6 polynomials. Using these, we
run a search for suitable nonnegative integer solutions, letting m run over increasing even
integers and x1, x2, and x3 over the sets of three nonnegative integers that sum to at most
m. With these specifications, a Gröbner basis calculation solves for the possible values of
the four remaining variables efficiently. When a suitable nonnegative integer solution is
identified, we substitute its values back into our regular matrices and compute the factors
of their characteristic polynomials. Noncyclotomic eigenvalues are detected by applying
GAP’s GaloisType command [6] to irreducible factors of degree 3 or 4. Our searches
have found there is only one example with noncyclotomic eigenvalues with m ≤ 62. We
found more examples by carrying out a narrow search with the values of x1, x2, and x3
set to within a 10% error of m4 for 64 ≤ m ≤ 250. Up to permutation equivalence, we
have found six symmetric rank 5 SITAwIMs with 4-point transitive Galois group that have
noncyclotomic eigenvalues. In all of these cases the Galois group is isomorphic to S4.
(Here we give the factorizations of the characteristic polynomials of their basis elements,
from these it is possible to recover the character table P numerically, and from that their
other parameters.)
16 Ars Math. Contemp. 23 (2023) #P3.02
Noncyclotomic SITAwIMs of type 5S: 4-point transitive examples
n = 249 : (x− 62)(x4 + x3 − 93x2 − 57x+ 12),
(x− 62)(x4 + x3 − 93x2 − 306x+ 261),
(x− 62)(x4 + x3 − 93x2 − 306x− 237),
(x− 62)(x4 + x3 − 93x2 − 140x+ 925)
n = 321 : (x− 80)(x4 + x3 − 120x2 − 341x− 242),
(x− 80)(x4 + x3 − 120x2 − 20x+ 2968),
(x− 80)(x4 + x3 − 120x2 − 301x− 400),
(x− 80)(x4 + x3 − 120x2 + 301x+ 1042)
n = 473 : (x− 118)(x4 + x3 − 177x2 − 266x+ 279),
(x− 118)(x4 + x3 − 177x2 − 266x+ 3117),
(x− 118)(x4 + x3 − 177x2 + 680x− 667),
(x− 118)(x4 + x3 − 177x2 + 207x+ 4536)
n = 633 : (x− 158)(x4 + x3 − 237x2 − 356x+ 10897),
(x− 158)(x4 + x3 − 237x2 − 145x+ 11108),
(x− 158)(x4 + x3 − 237x2 + 1754x− 3451),
(x− 158)(x4 + x3 − 237x2 − 778x+ 5411)
n = 785 : (x− 196)(x4 + x3 − 294x2 − 1619x− 1524),
(x− 196)(x4 + x3 − 294x2 − 49x+ 20456),
(x− 196)(x4 + x3 − 294x2 + 1521x+ 3186),
(x− 196)(x4 + x3 − 294x2 + 736x+ 7896)
n = 993 : (x− 248)(x4 + x3 − 372x2 + 931x− 128),
(x− 248)(x4 + x3 − 372x2 + 931x+ 9802),
(x− 248)(x4 + x3 − 372x2 + 2917x− 6086),
(x− 248)(x4 + x3 − 372x2 + 1924x+ 7816).
For all of these examples, the noncyclotomic character table demands a certain alge-
braic structure of the Wedderburn decomposition of QB. If the character table of (A,B) is
P = (Pi,j)
4
i,j=0 = (χi(bj))
4
i,j=0, then
• for all j ∈ {1, 2, 3, 4}, the four 4-dimensional primitive extension fields Q(P1,j),
Q(P2,j), Q(P3,j), and Q(P4,j) are pairwise distinct and Galois conjugate over Q;
• for all i ∈ {1, 2, 3, 4}, the four primitive extension fields Q(Pi,1), Q(Pi,2), Q(Pi,3),
and Q(Pi,4) are equal; and
• for all i, j ∈ {1, 2, 3, 4}, QB ≃ Q⊕Q(Pi,j) as Q-algebras.
Another interesting fact is that the field of Krein parameters will be equal to the splitting
field K, this is the minimal field of realization for the dual intersection matrices.
In the last section we explain how to verify that these six SITAwIMs satisfy all the
known feasibility conditions for being an association scheme. The first one is the smallest
rank 5 example with 4-point transitive Galois group, we present its parameters in detail
here.
Theorem 4.4. The smallest symmetric rank 5 SITAwIM with noncyclotomic eigenvalues
for which the Galois group of the splitting field is 4-point transitive has order 249. Up to
permutation equivalence, its standard basis is given by:
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 17
B =
b0, b1 =

0 62 0 0 0
1 15 14 12 20
0 14 16 17 15
0 12 17 18 15
0 20 15 15 12
 , b2 =

0 0 62 0 0
0 14 16 17 15
1 16 18 16 11
0 17 16 11 18
0 15 11 18 18
 ,
b3 =

0 0 0 62 0
0 12 17 18 15
0 17 16 11 18
1 18 11 18 14
0 15 18 14 15
 , b4 =

0 0 0 0 62
0 20 15 15 12
0 15 11 18 18
0 15 18 14 15
1 12 18 15 16

 .
The character table of (A,B) is shown below. The roots of the degree 4 polynomials
above have been approximated to six significant digits using Wolfram|Alpha [17].
P =

1 62 62 62 62
1 9.45706 −4.83450 −8.21429 2.59173
1 0.165779 −7.32957 10.6401 −4.47634
1 −0.777430 10.45989 −2.18457 −8.49789
1 −9.84541 0.704180 −1.24127 9.38250
 .
Since this algebra is self-dual, the second eigenmatrix is obtained by setting Qi,j = Pj,i for
i = 1, 2, 3, 4 and leaving the first row and column alone. The nontrivial dual intersection
matrices are as follows, with irrational entries approximated to six significant digits:
L∗1 =

0 62 0 0 0
1 16.2247 17.5718 15.3191 11.8843
0 17.5718 10.8695 18.0841 15.4745
0 15.3191 18.0841 13.9307 14.6661
0 11.8843 15.4745 14.6661 19.9751
 ,
L∗2 =

0 0 62 0 0
0 17.5718 10.8695 18.0841 15.4745
1 10.8695 18.3339 16.0173 15.7793
0 18.0841 16.0173 11.1233 16.7753
0 15.4745 15.7793 16.7753 13.9710
 ,
L∗3 =

0 0 0 62 0
0 15.3191 18.0841 13.9307 14.6661
0 18.0841 16.0173 11.1233 16.7753
1 13.9307 11.1233 17.5255 18.4206
0 14.6661 16.7753 18.4206 12.1381
 ,
L∗4 =

0 0 0 0 62
0 11.8843 15.4745 14.6661 19.9751
0 15.4745 15.7793 16.7753 13.9710
0 14.6661 16.7753 18.4206 12.1381
1 19.9751 13.9710 12.1381 14.9159
 .
Remark 4.5. One might ask if there are metric association schemes of rank 5 with noncy-
clotomic splitting fields that have 4-point transitive Galois groups. With our method, this
can be resolved by setting x4, x5, x9, x10, x17 = 0, calculating the Gröbner basis, and us-
ing known intersection array restrictions to bound tridiagonal entries of b1. This approach
allows one to make the same conclusion as Blau and Xu obtain for pseudocyclic metric
association schemes in general, that the intersection array has to be [2, 1, 1, 1; 1, 1, 1, 1]
[18, Theorem 5.4]. But the splitting field of this association scheme has a 3-point transitive
abelian Galois group, so the answer is no.
18 Ars Math. Contemp. 23 (2023) #P3.02
4.3.2 Type 5S with 3-point transitive Galois group
The other possibility for a symmetric SITAwIM of rank 5 with noncyclotomic eigenvalues
is the case where the Galois group of the splitting field is non-abelian and acts 3-point
transitively, so must be isomorphic to S3. Let (A,B) be such a SITAwIM, with splitting
field K and Galois group G, and suppose the orbits of G on the irreducible characters of
A are {χ0}, {χ1}, and {χ2, χ3, χ4}. In this situation the table algebra is not necessarily
pseudocyclic, nor does it have to be homogeneous, so we do not have as many linear
substitutions available to reduce our algebraic set initially. Instead, to find the SITAwIMs of
a given order, we can first make a list of possible rationalized character tables for SITAwIMs
of that order. The rationalized character table is an integer matrix with columns indexed by
B and rows are indexed by the sums of irreducible characters of A up to Galois conjugacy
over Q. In our 3-point transitive case, it takes this form:
b0 b1 b2 b3 b4 multiplicities
χ0 1 δ1 δ2 δ3 δ4 1
χ1 1 a1 a2 a3 a4 m1
χ2 + χ3 + χ4 3 t1 t2 t3 t4 3m2
The rows and columns of the rationalized character table satisfy orthogonality relations
induced by those of the usual character table. In our case the orthogonality relations give
the following identities:
• δ1 + δ2 + δ3 + δ4 = m1 + 3m2 = n− 1;
• a1 + a2 + a3 + a4 = −1;
• t1 + t2 + t3 + t4 = −3;
• 1 + a
2
1
δ1
+
a22
δ2
+
a23
δ3
+
a24
δ4
= nm1 ;
• 3 + a1t1δ1 +
a2t2
δ2
+ a3t3δ3 +
a4t4
δ4
= 0;
• δ1 +m1a1 +m2t1 = 0;
• δ2 +m1a2 +m2t2 = 0;
• δ3 +m1a3 +m2t3 = 0; and
• δ4 +m1a4 +m2t4 = 0.
These identities are subject to the restrictions 1 ≤ m1,m2, δ1, δ2, δ3, δ4, and −δi ≤
ai ≤ δi for i = 1, 2, 3, 4, and −3δi ≤ ti ≤ 3δi for i = 1, 2, 3, 4. So a straightfor-
ward search will produce all the rationalized character tables possible whose associated
SITAwIM would have degree n.
Given a rationalized character table, we get four linear trace identities tr(bi) = δi +
ai + ti, i = 1, 2, 3, 4 that can be added to our list of polynomial generators. This helps
us to reduce our search space enough to allow the search and Gröbner basis calculations
techniques to uncover suitable nonnegative solutions to the system and produce regular
matrices for a SITAwIM with this rationalized character table. This approach has two
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 19
computational barriers, which have limited our ability to guarantee a complete account
only for orders up to 100. First, since we must consider every possibility for m1 and m2
with 1 +m1 + 3m2 = n, the number of possible rational character tables of a given order
can be very large and time-consuming to generate, and for almost all of these we find no
SITAwIM. Secondly, the values of the xi’s are not as limited as they are in the homogeneous
case, so when the minimum δi is large, the search space for all the values of x1, x2, and x3
we need to check grows in size exponentially.
Our complete search for orders up to 100 found six examples. Their multiplicities and
factorizations of the characteristic polynomials of their basis elements are as follows:
Noncyclotomic SITAwIMs of type 5S: 3-point transitive examples
n = 35 : m1 = 4,m2 = 10, µbi (x) = (x− 4)(x+ 1)(x
3 − 6x+ 2), (x− 6)2(x+ 1)3,
(x− 12)(x+ 3)(x3 − 12x− 2), (x− 12)(x+ 3)(x3 − 12x+ 12);
n = 45 : m1 = 8,m2 = 12, µbi (x) = (x− 4)
2(x+ 1)3, (x− 8)(x+ 1)(x3 − 12x+ 14),
(x− 8)(x+ 1)(x3 − 12x+ 4), (x− 24)(x+ 3)(x3 − 18x+ 18);
n = 76 : m1 = 18,m2 = 19, µbi (x) = (x− 3)
2(x+ 1)3, (x− 18)(x+ 1)(x3 − 27x− 18),
(x− 18)(x+ 1)(x3 − 27x− 42), (x− 36)(x+ 2)(x3 − 36x− 48);
n = 88a : m1 = 66,m2 = 7, µbi (x) = (x− 3)
4(x+ 1), (x− 14)(x)(x3 + 2x2 − 72x− 16),
(x− 35)(x)(x3 + 5x2 − 120x− 360), (x− 35)(x)(x3 + 5x2 − 120x+ 80);
n = 88b : m1 = 66,m2 = 7, µbi (x) = (x− 3)
4(x+ 1), (x− 21)(x)(x3 + 3x2 − 96x− 384),
(x− 21)(x)(x3 + 3x2 − 96x− 472), (x− 42)(x)(x3 + 6x2 − 120x− 784); and
n = 93 : m1 = 2,m2 = 30, µbi (x) = (x− 12)(x+ 6)(x
3 − 15x+ 2), (x− 20)(x+ 10)
(x3 − 21x− 16), (x− 30)(x+ 15)(x3 − 24x+ 8), (x− 30)2(x+ 1)3.
Narrow searches of orders 101 to 250, the first with δ1 ≤ 4 and at least two of δ2, δ3,
and δ4 equal, and the second with δ1 ≤ 12, a1 = k1, and at least two of δ2, δ3, and δ4 equal
produced a few more examples:
n = 116 : m1 = 58,m2 = 19, µbi (x) = (x− 1)
4(x+ 1), (x− 19)(x)(x3 + x2 − 48x+ 72)
(x− 19)(x)(x3 + x2 − 48x− 44), (x− 76)(x)(x3 + 4x2 − 72x− 32);
n = 129 : m1 = 86,m2 = 14, µbi (x) = (x− 2)
4(x+ 1), (x− 28)(x)(x3 + 2x2 − 99x+ 150)
(x− 28)(x)(x3 + 2x2 − 99x− 108), (x− 70)(x)(x3 + 5x2 − 135x− 75);
n = 165 : m1 = 32,m2 = 44, µbi (x) = (x− 4)
2(x+ 1)3, (x− 32)(x+ 1)(x3 − 48x− 32),
(x− 32)(x+ 1)(x3 − 48x− 112), (x− 96)(x+ 3)(x3 − 72x− 144);
n = 189 : m1 = 20,m2 = 56, µbi (x) = (x− 8)
2(x+ 1)3, (x− 20)(x+ 1)(x3 − 30x− 20),
(x− 80)(x+ 4)(x3 − 75x+ 70), (x− 80)(x+ 4)(x3 − 75x− 200);
n = 190 : m1 = 18,m2 = 57, µbi (x) = (x− 9)
2(x+ 1)3, (x− 36)(x+ 2)(x3 − 48x+ 32),
(x− 36)(x+ 2)(x3 − 48x+ 112), (x− 108)(x+ 6)(x3 − 72x+ 144);
n = 217 : m1 = 30,m2 = 62, µbi (x) = (x− 6)
2(x+ 1)3, (x− 60)(x+ 2)(x3 − 75x− 100),
(x− 60)(x+ 2)(x3 − 75x− 170), (x− 90)(x+ 3)(x3 − 90x− 180);
n = 231a : m1 = 32,m2 = 66, µbi (x) = (x− 6)
2(x+ 1)3, (x− 32)(x+ 1)(x3 − 48x− 96),
(x− 96)(x+ 3)(x3 − 96x− 352), (x− 96)(x+ 3)(x3 − 96x− 128);
n = 231b : m1 = 32,m2 = 66, µbi (x) = (x− 6)
2(x+ 1)3, (x− 32)(x+ 1)(x3 − 48x+ 16),
(x− 96)(x+ 3)(x3 − 96x− 128), (x− 96)(x+ 3)(x3 − 96x+ 208).
20 Ars Math. Contemp. 23 (2023) #P3.02
Example 4.6. The smallest noncyclotomic symmetric rank 5 SITAwIM with order n = 35
has regular matrices b0,
b1 =

0 4 0 0 0
1 0 0 0 3
0 0 0 2 2
0 0 1 2 1
0 1 1 1 1
 , b2 =

0 0 6 0 0
0 0 0 3 3
1 0 5 0 0
0 1 0 2 3
0 1 0 3 2
 , b3 =

0 0 0 12 0
0 0 3 6 3
0 2 0 4 6
1 2 2 4 3
0 1 3 3 5
 , and
b4 =

0 0 0 0 12
0 3 3 3 3
0 2 0 6 4
0 1 3 3 5
1 1 2 5 3
 .
Its first and second eigenmatrices (with irrationals approximated to six significant dig-
its) are as follows:
P =

1 4 6 12 12
1 −1 6 −3 −3
1 −2.60168 −1 −0.167055 2.768734
1 0.339877 −1 3.54461 −3.88448
1 2.26180 −1 −3.37755 1.11575
 , and
Q =

1 4 10 10 10
1 −1 −6.50420 0.849692 5.65451
1 4 −5/3 −5/3 −5/3
1 −1 −0.139212 2.95384 −2.81463
1 −1 2.30728 −3.23707 0.929791
 .
Its dual intersection matrices, again with irrational entries approximated to six signifi-
cant digits, are: L∗0 = b0,
L∗1 =

0 4 0 0 0
1 3 0 0 0
0 0 2/3 5/3 5/3
0 0 5/3 2/3 5/3
0 0 5/3 5/3 2/3
 ,
L∗2 =

0 0 10 0 0
0 0 5/3 25/6 25/6
1 2/3 0.0541562 2.59972 5.67949
0 5/3 2.59972 3.51139 20/9
0 5/3 5.67946 20/9 0.431651
 ,
L∗3 =

0 0 0 10 0
0 0 25/6 5/3 25/6
0 5/3 2.59972 3.51139 20/9
1 2/3 3.51139 2.50545 2.31644
0 5/3 20/9 2.31169 3.79463
 ,
L∗4 =

0 0 0 0 10
0 0 25/6 25/6 5/3
0 5/3 5.67946 20/9 0.431651
0 5/3 20/9 2.31649 3.79463
1 2/3 0.431651 3.79463 4.10706
 .
5 Checking feasibility
In this section we review the feasibility checks we have applied to the parameters of the
noncyclotomic symmetric rank 5 SITAwIMs identified in the previous section. The pa-
rameters include the regular (a.k.a. intersection) matrices bi (i ∈ {0, 1, . . . , r − 1}), the
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 21
character table (first eigenmatrix) P , the dual character table (second eigenmatrix) Q, and
the dual intersection matrices (Krein parameters) L∗i = (κijk)
r−1
k,j=0 (i ∈ {0, 1, . . . , r−1}).
For commutative association schemes, we consider these to be equivalent since knowledge
of any one of these determines the other.
We have tested our examples on the following feasibility conditions, which apply to
general symmetric association schemes:
• the handshaking lemma: for i, j ∈ {1, . . . , r − 1}, if i ̸= j, then (bi)i,jkj must be
even (see [11, Lemma 7]);
• realizability of all closed subsets and quotients;
• the triangle count condition: for j = 1, . . . , r − 1, 1
6
r−1∑
i=0
miP
3
i,j = t ∈ N;
• the absolute bound condition: for i ∈ {0, . . . , r − 1}
∑
k;qijk ̸=0
mk ≤
{
mimj i ̸= j(
mi+1
2
)
i = j;
• nonnegativity of Krein parameters: (L∗i )j,k ≥ 0 for i, j, k ∈ {0, . . . , r − 1}; and
• Martin and Kodalen’s Gegenbauer polynomial criterion (see [13, Theorem 3.7 and
Corollary 3.8]).
We are aware of one more feasibility condition for symmetric association schemes, the for-
bidden quadruple condition described in [7, Corollary 4.2]. Our 4-point transitive examples
do not have any nontrivial Krein parameters equal to zero, so they satisfy this condition vac-
uously. This is not the case for our 3-point transitive examples, to date these have not been
tested for this condition.
We have ordered these feasibility conditions according to the ease we are able to check
them. Since our algorithms require the multiplicities as part of the input and produce the
intersection matrices, we have to compute P , then Q, then the dual intersection matrices in
order from there. As our objective is only to report the examples that pass all conditions,
once an example fails one of our conditions below it is removed and its status for subsequent
conditions is not reported.
We will indicate our examples from the previous section by Galois group action and
order: 3pt35, 3pt45, etc. Recall that 3pt35 means the 3-point transitive example of order
35.
5.1 Handshaking lemma condition:
Only five of our examples have nontrivial basis elements of odd degree, of these five, three
of them fail the handshaking lemma condition: 3pt88a, 3pt88b, and 3pt116. 3pt76 and
3pt190 pass despite having a nontrivial basis element of odd degree.
22 Ars Math. Contemp. 23 (2023) #P3.02
5.2 Realizability of closed subsets and quotients:
All of our 4-point transitive examples are primitive, so there are no closed subsets or quo-
tients to consider. On the other hand, all of the remaining 3-point transitive examples have
a unique nontrivial closed subset of rank 2. For all but one of these, the quotient also has
rank 2. The exception is 3pt129, for which the quotient has rank 4. Since this quotient
table algebra has an element of non-integral degree, it is not realizable as an association
scheme.
5.3 Triangle count condition.
All of our examples pass.
5.4 Absolute bound condition.
All of our 4-point transitive examples pass. We can see from the multiplicities that 3pt45,
3pt76, and 3pt165 will pass. 3pt35 could potentially fail for i = j = 1 but passes because
κ1,1,k = 0 for k = 2, 3, 4. 3pt93 and 3pt129 also pass because enough nontrivial Krein
parameters are 0.
5.5 Nonnegative Krein parameter condition.
For all of our 3- and 4-point transitive examples, we have calculated the dual intersection
matrices and found them to be nonnegative.
5.6 Gegenbauer polynomial condition.
We check that Gmiℓ (
1
mi
L∗i ) is a nonnegative matrix for all ℓ ≥ 1 and i = 1, . . . , 4 using the
approach of [13, §3.3].
We illustrate the process of checking this condition with 3pt35. In the case m1 = 4, it
is not possible to find an ℓ∗ satisfying the conditions of [13, Corollary 3.16]. However, L∗1
is a block matrix, and the upper left 2× 2 block
[
0 4
1 3
]
is the dual intersection matrix cor-
responding to the association scheme generated by the complete graph of order 5, in which
it also occurs with nontrivial multiplicity 4. It follows that the first column of Gmiℓ (
1
mi
L∗i )
will always be nonnegative for all ℓ ≥ 1, so the result follows by [13, Corollary 3.8] and
the remark following it.
In the cases m2 = m3 = m4 = 10, we find that the minimum ℓ∗ required for [13,
Corollary 3.16] is ℓ∗ = 6, and we can check that G10ℓ (
1
10L
∗
i ) has nonnegative entries for
all ℓ ∈ {1, . . . , 7} and all i = 2, 3, 4. So, 3pt35 passes all the feasibility conditions, with
the possible exception of the forbidden quadruple condition.
In all of the remaining 3-transitive examples, B∗ contains a rank 2 closed subset of
order mi + 1 for one i. So, a similar argument as in the 3pt35 case applies for this mi.
For the other mi a suitable ℓ∗ can be found. After evaluating the appropriate Gegenbauer
polynomials at 1miL
∗
i , we found the result to be a nonnegative matrix.
All of our 4-point transitive examples pass the Gegenbauer polynomial test. In each
case we have found a value of ℓ∗ and shown all of the required evaluations result in non-
negative matrices.
A. Herman et al.: The search for small association schemes with noncyclotomic eigenvalues 23
In summary, we have verified that the six 4-point transitive examples pass all of the
feasibility conditions, and ten of the 3-point transitive examples pass them: 3pt35, 3pt45,
3pt76, 3pt93, 3pt165, 3pt189, 3pt190, 3pt217, 3pt231a, and 3pt231b. Note that by the
partial classification of association schemes of order 35 and rank 5 in [8], we know 3pt35
cannot be realized.
ORCID iDs
Allen Herman https://orcid.org/0000-0001-9841-636X
Roghayeh Maleki https://orcid.org/0000-0003-1803-4316
References
[1] Z. Arad, E. Fisman and M. Muzychuk, Generalized table algebras, Israel J. Math. 114 (1999),
29–60, doi:10.1007/bf02785571, https://doi.org/10.1007/bf02785571.
[2] S. Bang, A. Dubickas, J. H. Koolen and V. Moulton, There are only finitely many distance-
regular graphs of fixed valency greater than two, Adv. Math. 269 (2015), 1–55, doi:10.1016/j.
aim.2014.09.025, https://doi.org/10.1016/j.aim.2014.09.025.
[3] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjaming/Cummings,
London, 1984 .
[4] E. Bannai and S.-Y. Song, Character tables of fission schemes and fusion schemes, volume 14,
pp. 385–396, 1993, doi:10.1006/eujc.1993.1043, https://doi.org/10.1006/eujc.
1993.1043.
[5] H. I. Blau, Table algebras, Eur. J. Comb. 30 (2009), 1426–1455, doi:10.1016/j.ejc.2008.11.008,
https://doi.org/10.1016/j.ejc.2008.11.008.
[6] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.11.1, 2021,
https://www.gap-system.org.
[7] A. L. Gavrilyuk, J. Vidali and J. S. Williford, On few-class Q-polynomial association schemes:
feasible parameters and nonexistence results, Ars Math. Contemp. 20 (2021), 103–127, doi:10.
26493/1855-3974.2101.b76, https://doi.org/10.26493/1855-3974.2101.b76.
[8] A. Hanaki and I. Miyamoto, Classification of association schemes, accessed October 2021,
http://math.shinshu-u.ac.jp/˜hanaki/as/.
[9] A. Herman and A. R. Barghi, Schur indices of association schemes, J. Pure Appl. Algebra
215 (2011), 1015–1023, doi:10.1016/j.jpaa.2010.07.007, https://doi.org/10.1016/
j.jpaa.2010.07.007.
[10] A. Herman and R. Maleki, PolynomialsDefiningCAlgebras, updated September 2022, https:
//github.com/RoghayehMaleki/PolynomialsDefiningCAlgebras.
[11] A. Herman, M. Muzychuk and B. Xu, Noncommutative reality-based algebras of rank 6,
Comm. Algebra 46 (2018), 90–113, doi:10.1080/00927872.2017.1355372, https://doi.
org/10.1080/00927872.2017.1355372.
[12] A. Herman and A. Rahnamai Barghi, The character values of commutative quasi-thin schemes,
Linear Algebra Appl. 429 (2008), 2663–2669, doi:10.1016/j.laa.2007.08.023, https://
doi.org/10.1016/j.laa.2007.08.023.
[13] B. Kodalen, Cometric Association Schemes, 2019, arXiv:1905.06959 [math.CO].
[14] W. J. Martin and H. Tanaka, Commutative association schemes, Eur. J. Comb. 30 (2009), 1497–
1525, doi:10.1016/j.ejc.2008.11.001, https://doi.org/10.1016/j.ejc.2008.11.
001.
24 Ars Math. Contemp. 23 (2023) #P3.02
[15] A. Munemasa, Splitting fields of association schemes, J. Comb. Theory Ser. A 57
(1991), 157–161, doi:10.1016/0097-3165(91)90014-8, https://doi.org/10.1016/
0097-3165(91)90014-8.
[16] M. Muzychuk and I. Ponomarenko, On quasi-thin association schemes, J. Algebra 351
(2012), 467–489, doi:10.1016/j.jalgebra.2011.11.012, https://doi.org/10.1016/j.
jalgebra.2011.11.012.
[17] Wolfram|Alpha, Wolfram Alpha LLC, accessed September 25, 2021, http://www.
wolframalpha.com/input/?i=2%2B2.
[18] B. Xu and H. I. Blau, On pseudocyclic table algebras and applications to pseudocyclic as-
sociation schemes, Israel J. Math. 183 (2011), 347–379, doi:10.1007/s11856-011-0052-2,
https://doi.org/10.1007/s11856-011-0052-2.