ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 103–127
https://doi.org/10.26493/1855-3974.2101.b76
(Also available at http://amc-journal.eu)
On few-class Q-polynomial association schemes:
feasible parameters and nonexistence results
Alexander L. Gavrilyuk *
Center for Math Research and Education, Pusan National University,
2, Busandaehak-ro 63beon-gil, Geumjeong-gu, Busan, 46241, Republic of Korea
Janoš Vidali †
Faculty of Mathematics and Physics, University of Ljubljana,
Jadranska ulica 21, 1000 Ljubljana, Slovenia, and
Institute of Mathematics, Physics and Mechanics,
Jadranska ulica 19, 1000 Ljubljana, Slovenia
Jason S. Williford ‡
Department of Mathematics and Statistics, University of Wyoming,
1000 E. University Ave., Laramie, WY 82071, United States of America
Received 28 August 2019, accepted 28 August 2020, published online 19 August 2021
Abstract
We present the tables of feasible parameters of primitive 3-class Q-polynomial associ-
ation schemes and 4- and 5-class Q-bipartite association schemes (on up to 2800, 10000,
and 50000 vertices, respectively), accompanied by a number of nonexistence results for
such schemes obtained by analysing triple intersection numbers of putative open cases.
Keywords: Association scheme, Q-polynomial, feasible parameters, distance-regular graph.
Math. Subj. Class. (2020): 05E30
*The author is supported by BK21plus Center for Math Research and Education at Pusan National University,
by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the
Ministry of Education (grant number NRF-2018R1D1A1B07047427) and by the Slovenian Research Agency
(Slovenia-Russia bilateral grant number BI-RU/19-20-007).
†The author is supported by the Slovenian Research Agency (research program P1-0285, research projects
J1-8130, J1-1691, J1-1692 and Slovenia-Russia bilateral grant (number BI-RU/19-20-007)).
‡The author was supported by National Science Foundation (NSF) grant DMS-1400281.
E-mail addresses: gavrilyuk@riko.shimane-u.ac.jp (Alexander L. Gavrilyuk), janos.vidali@fmf.uni-lj.si
(Janoš Vidali), jwillif1@uwyo.edu (Jason S. Williford)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
104 Ars Math. Contemp. 20 (2021) 103–127
1 Introduction
Much attention in literature on association schemes has been paid to distance-regular graphs,
in particular to those of diameter 2, also known as strongly regular graphs – however, their
complete classification is still a widely open problem. The tables of their feasible parame-
ters, maintained by A. E. Brouwer [4, 5], are very helpful for the algebraic combinatorics
community, in particular when one wants to check whether a certain example has already
been proven (not) to exist, to be unique, etc. Compiling such a table can be a challeng-
ing problem, as, for example, some feasibility conditions require calculating roots of high
degree polynomials.
The goal of this work is to present the tables of feasible parameters of Q-polynomial
association schemes, compiled by the third author, and accompanied by a number of nonex-
istence results obtained by the first two authors.
Recall that Q-polynomial association schemes can be seen as a counterpart of distance-
regular graphs, which, however, remains much less explored, although they have received
considerable attention in the last few years [11, 25, 27, 28] due to their connection with
some objects in quantum information theory such as equiangular lines and real mutually
unbiased bases [24].
More precisely, let A0, . . . , AD and E0, . . . , ED denote the adjacency matrices and the
primitive idempotents of an association scheme, respectively. An association scheme is
P -polynomial (or metric) if, after suitably reordering the relations, there exist polynomials
vi of degree i such that Ai = vi(A1) (0 ≤ i ≤ D). If this is the case, the matrix Ai can be
seen as the distance-i adjacency matrix of a distance-regular graph and vice-versa. Simi-
larly, an association scheme is Q-polynomial (or cometric) if, after suitably reordering the
eigenspaces, there exist polynomials v∗j of degree j such that Ej = v
∗
j (E1) (0 ≤ j ≤ D),
where the matrix multiplication is entrywise. These notions are due to Delsarte [15], who
introduced the P -polynomial property as an algebraic definition of association schemes
generated by distance-regular graphs, and then defined Q-polynomial association schemes
as the dual concept to P -polynomial association schemes.
Many important examples of P -polynomial association schemes, which arise from clas-
sical algebraic objects such as dual polar spaces and forms over finite fields, also possess
the Q-polynomial property. Bannai and Ito [1] posed the following conjecture.
Conjecture 1.1. For D large enough, a primitive association scheme of D classes is P -
polynomial if and only if it is Q-polynomial.
We are not aware of any progress towards its proof. The discovery of a feasible set of
parameters of hypothetical counter-examples (see [30]) casts some doubt on the conjecture,
and in the very least shows that this will likely be difficult to prove (see the next section
for the definition of feasible parameter sets). Moreover, the problem of classification of
association schemes which are both P - and Q-polynomial (i.e., Q-polynomial distance-
regular graphs) is still open. We refer the reader to [13] for its current state.
Recall that, for a P -polynomial association scheme defined on a set X , its intersection
numbers pkij satisfy the triangle inequality: p
k
ij = 0 if |i − j| > k or i + j < k, which
naturally gives rise to a graph structure on X . Perhaps, due to the lack of such an intu-
itive combinatorial characterization, much less is known about Q-polynomial association
schemes when the P -polynomial property is absent (which also indicates that there should
be much more left to discover). To date, only few examples of Q-polynomial schemes are
known which are neither P -polynomial nor duals of P -polynomial schemes [28] – most
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 105
of them are imprimitive and related to combinatorial designs. The first infinite family of
primitive Q-polynomial schemes that are not also P -polynomial was recently constructed
in [31]. Due to Conjecture 1.1, it seems that the most promising area for constructing new
examples of Q-polynomial association schemes which are not P -polynomial includes those
with few classes, say, in the range 3 ≤ D ≤ 6. The tables of feasible parameters of prim-
itive 3-class Q-polynomial association schemes and 4- and 5-class Q-bipartite association
schemes presented in Section 3 may serve as a source for new constructions.
We note that imprimitive Q-polynomial 3-class schemes are either Taylor graphs (see
[5, pp. 4–6]) or linked systems of symmetric designs (see [27]). For current research on Q-
antipodal 4- and 5-class association schemes, see [24, 25] and [11]. Due to this recent work
on Q-antipodal schemes, the third author has focused only on the less studied primitive
and Q-bipartite cases in his tables. We note the primitive case is far more computationally
demanding than the Q-bipartite case, and this is the reason the class number in the tables
does not go to 4 or 5.
The parameters of P -polynomial association schemes are restricted by a number of
conditions implied by the triangle inequality. On the other hand, the Q-polynomial prop-
erty allows us to consider triple intersection numbers with respect to some triples of ver-
tices, which can be thought of as a generalization of intersection numbers to triples of
starting vertices instead of pairs. This technique has been previously used by various re-
searchers [8, 10, 17, 21, 22, 23, 36, 37], mostly to prove nonexistence of some strongly reg-
ular and distance-regular graphs with equality in the so-called Krein conditions, in which
case combining the restrictions implied by the triangle inequality with triple intersection
numbers seems the most fruitful. Yet, while calculating triple intersection numbers when
the P -polynomial property is absent is harder, we managed to rule out a number of open
cases from the tables. This includes a putative Q-polynomial association scheme on 91
vertices whose existence has been open since 1999 [12].
The paper is organized as follows. In Section 2, we recall the basic theory of association
schemes and their triple intersection numbers. In Section 3, we comment on the tables of
feasible parameters of Q-polynomial association schemes and how they were generated. In
Section 4, we explain in detail the analysis of triple intersection numbers of Q-polynomial
association schemes and prove nonexistence for many open cases from the tables. Finally,
in Section 5, we discuss the generalization of triple intersection numbers to quadruples of
vertices.
2 Preliminaries
In this section we prepare the notions needed in subsequent sections.
2.1 Association schemes
Let X be a finite set of vertices and {R0, R1, . . . , RD} be a set of non-empty subsets of
X ×X . Let Ai denote the adjacency matrix of the (di-)graph (X,Ri) (0 ≤ i ≤ D). The
pair (X, {Ri}Di=0) is called a (symmetric) association scheme of D classes (or a D-class
scheme for short) if the following conditions hold:
(1) A0 = I|X|, which is the identity matrix of size |X|,
(2)
∑D
i=0 Ai = J|X|, which is the square all-one matrix of size |X|,
(3) A⊤i = Ai (1 ≤ i ≤ D),
106 Ars Math. Contemp. 20 (2021) 103–127
(4) AiAj =
∑D
k=0 p
k
ijAk, where p
k
ij are nonnegative integers (0 ≤ i, j ≤ D).
The nonnegative integers pkij are called intersection numbers: for a pair of vertices x, y ∈ X
with (x, y) ∈ Rk and integers i, j (0 ≤ i, j, k ≤ D), pkij equals the number of vertices
z ∈ X such that (x, z) ∈ Ri, (y, z) ∈ Rj .
The vector space A over R spanned by the matrices Ai forms an algebra. Since A is
commutative and semisimple, there exists a unique basis of A consisting of primitive idem-
potents E0 = 1|X|J|X|, E1, . . . , ED (i.e., projectors onto the maximal common eigenspaces
of A0, . . . , AD). Since the algebra A is closed under the entry-wise multiplication denoted
by ◦, we define the Krein parameters qkij (0 ≤ i, j, k ≤ D) by
Ei ◦ Ej =
1
|X|
D∑
k=0
qkijEk. (2.1)
It is known that the Krein parameters are nonnegative real numbers (see [15, Lem-
ma 2.4]). Since both {A0, A1, . . . , AD} and {E0, E1, . . . , ED} form bases of A, there
exists matrices P = (Pij)Di,j=0 and Q = (Qij)
D
i,j=0 defined by
Ai =
D∑
j=0
PjiEj and Ei =
1
|X|
D∑
j=0
QjiAj . (2.2)
The matrices P and Q are called the first and second eigenmatrix of (X, {Ri}Di=0).
Let ni, 0 ≤ i ≤ D, denote the valency of the graph (X,Ri), and mj , 0 ≤ j ≤ D,
denote the multiplicity of the eigenspace of A0, . . . , AD corresponding to Ej . Note that
ni = p
0
ii, while mj = q
0
jj .
For an association scheme (X, {Ri}Di=0), an ordering of A1, . . . , AD such that for each
i (0 ≤ i ≤ D), there exists a polynomial vi(x) of degree i with Pji = vi(Pj1) (0 ≤ j ≤ D),
is called a P -polynomial ordering of relations. An association scheme is said to be P -
polynomial if it admits a P -polynomial ordering of relations. The notion of an association
scheme together with a P -polynomial ordering of relations is equivalent to the notion of
a distance-regular graph – such a graph has adjacency matrix A1, and Ai (0 ≤ i ≤ D)
is the adjacency matrix of its distance-i graph (i.e., (x, y) ∈ Ri precisely when x and y
are at distance i in the graph), and the number of classes equals the diameter of the graph.
It is also known that an ordering of relations is P -polynomial if and only if the matrix of
intersection numbers L1, where Li := (pkij)
D
k,j=0 (0 ≤ i ≤ D), is a tridiagonal matrix with
nonzero superdiagonal and subdiagonal [1, p. 189] – then pkij = 0 holds whenever the triple
(i, j, k) does not satisfy the triangle inequality (i.e., when |i − j| < k or i + j > k). For
a P -polynomial ordering of relations of an association scheme, set ai = pi1,i, bi = p
i
1,i+1,
and ci = pi1,i−1. These intersection numbers are usually gathered in the intersection array
{b0, b1, . . . , bD−1; c1, c2, . . . , cD}, as the remaining intersection numbers can be computed
from them (in particular, ai = b0−bi−ci for all i, where bD = c0 = 0). For an association
scheme with a P -polynomial ordering of relations, the ordering E1, . . . , ED is called the
natural ordering of eigenspaces if (Pi1)Di=0 is a decreasing sequence.
Dually, for an association scheme (X, {Ri}Di=0), an ordering of E1, . . . , ED such that
for each i (0 ≤ i ≤ D), there exists a polynomial v∗i (x) of degree i with Qji = v∗i (Qj1)
(0 ≤ j ≤ D), is called a Q-polynomial ordering of eigenspaces. An association scheme
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 107
is said to be Q-polynomial if it admits a Q-polynomial ordering of eigenspaces. Similarly
as before, it is known that an ordering of eigenspaces is Q-polynomial if and only if the
matrix of Krein parameters L∗1, where L
∗
i := (q
k
ij)
D
k,j=0 (0 ≤ i ≤ D), is a tridiagonal ma-
trix with nonzero superdiagonal and subdiagonal [1, p. 193] – then qkij = 0 holds whenever
the triple (i, j, k) does not satisfy the triangle inequality. For a Q-polynomial ordering of
eigenspaces, set a∗i = q
i
1,i, b
∗
i = q
i
1,i+1, and c
∗
i = q
i
1,i−1. Again, these Krein parameters
are usually gathered in the Krein array {b∗0, b∗1, . . . , b∗D−1; c∗1, c∗2, . . . , c∗D} containing all
the information needed to compute the remaining Krein parameters (in particular, we have
a∗i = b
∗
0 − b∗i − c∗i for all i, where b∗D = c∗0 = 0). For an association scheme with a Q-
polynomial ordering of eigenspaces, the ordering A1, . . . , AD is called the natural ordering
of relations if (Qi1)Di=0 is a decreasing sequence. Unlike for the P -polynomial association
schemes, there is no known general combinatorial characterization of Q-polynomial asso-
ciation schemes.
An association scheme is called primitive if all of A1, . . . , AD are adjacency matrices
of connected graphs. It is known that a distance-regular graph is imprimitive precisely
when it is a cycle of composite length, an antipodal graph, or a bipartite graph (possibly
more than one of these), see [5, Thm. 4.2.1]. The last two properties can be recognised from
the intersection array as bi = cD−i (0 ≤ i ≤ D, i ̸= ⌊D/2⌋) and ai = 0 (0 ≤ i ≤ D),
respectively. We may define dual properties for a Q-polynomial association scheme – we
say that it is Q-antipodal if b∗i = c
∗
D−i (0 ≤ i ≤ D, i ̸= ⌊D/2⌋), and Q-bipartite if
a∗i = 0 (0 ≤ i ≤ D). All imprimitive Q-polynomial association schemes are schemes of
cycles of composite length, Q-antipodal or Q-bipartite (again, possibly more than one of
these). The original classification theorem by Suzuki [34] allowed two more cases, which
have however been ruled out later [9, 35]. An association scheme that is both P - and Q-
polynomial is Q-antipodal if and only if it is bipartite, and is Q-bipartite if and only if it is
antipodal.
A formal dual of an association scheme with first and second eigenmatrices P and Q
is an association scheme such that, for some orderings of its relations and eigenspaces, its
first and second eigenmatrices are Q and P , respectively. Note that this duality occurs on
the level of parameters – an association scheme might have several formal duals, or none
at all (we can speak of duality when there exists a regular abelian group of automorphisms,
see [5, §2.10B]). An association scheme with P = Q for some orderings of its relations and
eigenspaces is called formally self-dual. For such orderings, pkij = q
k
ij (0 ≤ i, j, k ≤ D)
holds – in particular, a formally self-dual association scheme is P -polynomial if and only
if it is Q-polynomial, and then its intersection array matches its Krein array.
Any imprimitive association scheme with two classes is both P - and Q-polynomial for
either of the two orderings of relations and eigenspaces. The graph with adjacency matrix
A1 of such a scheme is said to be strongly regular (an SRG for short) with parameters
(n, k, λ, µ), where n = |X| is the number of vertices, k = p011 is the valency of each
vertex, and each two distinct vertices have precisely λ = p111 common neighbours if they
are adjacent, and µ = p211 common neighbours if they are not adjacent. In the sequel, we
will identify P -polynomial association schemes with their corresponding strongly regular
or distance-regular graphs.
By a parameter set of an association scheme, we mean the full set of pkij , q
k
ij , Pij
and Qij described in this section, which are real numbers satisfying the identities in [5,
Lemma 2.2.1, Lemma 2.3.1]. We say that a parameter set for an association scheme is
feasible if it passes all known conditions for the existence of a corresponding association
108 Ars Math. Contemp. 20 (2021) 103–127
scheme. For distance-regular graphs, there are many known feasibility conditions, see [5,
13, 37]. For Q-polynomial association schemes, much less is known – see Section 3 for
the feasibility conditions we have used.
2.2 Triple intersection numbers
For a triple of vertices x, y, z ∈ X and integers i, j, k (0 ≤ i, j, k ≤ D) we denote by[
x y z
i j k
]
(or simply [i j k] when it is clear which triple (x, y, z) we have in mind) the
number of vertices w ∈ X such that (x,w) ∈ Ri, (y, w) ∈ Rj and (z, w) ∈ Rk. We call
these numbers triple intersection numbers.
Unlike the intersection numbers, the triple intersection numbers depend, in general, on
the particular choice of (x, y, z). Nevertheless, for a fixed triple (x, y, z), we may write
down a system of 3D2 linear Diophantine equations with D3 triple intersection numbers as
variables taking nonnegative values, thus relating them to the intersection numbers, cf. [22]:
D∑
ℓ=0
[ℓ j k] = ptjk,
D∑
ℓ=0
[i ℓ k] = psik,
D∑
ℓ=0
[i j ℓ] = prij , (1 ≤ i, j, k ≤ D) (2.3)
where (x, y) ∈ Rr, (x, z) ∈ Rs, (y, z) ∈ Rt, and
[0 j k] = δjrδks, [i 0 k] = δirδkt, [i j 0] = δisδjt (0 ≤ i, j, k ≤ D)
are constants. Note that the equations (2.3) are not all linearly independent, so the system
is underdetermined in general when D ≥ 3. Moreover, the following theorem sometimes
gives additional equations.
Theorem 2.1 ([10, Theorem 3], cf. [7], [5, Theorem 2.3.2]). Let (X, {Ri}Di=0) be an
association scheme of D classes with second eigenmatrix Q and Krein parameters qtrs
(0 ≤ r, s, t ≤ D). Then,
qtrs = 0 ⇐⇒
D∑
i,j,k=0
QirQjsQkt
[
x y z
i j k
]
= 0 for all x, y, z ∈ X.
Note that in a Q-polynomial association scheme, many Krein parameters are zero, and
we can use Theorem 2.1 to obtain an equation for each of them.
3 Tables of feasible parameters for Q-polynomial association schemes
In this section we will describe the tables of feasible parameter sets for primitive 3-class
Q-polynomial schemes and 4- and 5-class Q-bipartite schemes.
These tables were all completed using the MAGMA programming language (see [2]).
Any parameter set meeting the following conditions was included in the table:
(1) The parameters satisfy the Q-polynomial condition.
(2) All pkij are nonnegative integers, all valencies p
0
jj are positive.
(3) For each j > 0 we have np0jj is even (the handshaking lemma applied to the graph
(X,Rj)).
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 109
(4) For each j, k > 0 we have p0jjp
j
jk is even (the handshaking lemma applied to the
subconstituent (Y, {(y, z) ∈ Y × Y | (y, z) ∈ Rk}), where x ∈ X and Y = {y ∈
X | (x, y) ∈ Rj}).
(5) For each j > 0 we have np0jjp
j
jj is divisible by 6 (the number of triangles in each
graph (X,Rj) is integral).
(6) All qkij are nonnegative and for each j the multiplicity q
0
jj (i.e., the dimension of the
Ej-eigenspace) is a positive integer (see [5, Proposition 2.2.2]).
(7) For all i, j we have
∑
qkij ̸=0
mk ≤ mimj if i ̸= j and
∑
qkii ̸=0
mk ≤ mi(mi−1)2 (the
absolute bound, see [5, Theorem 2.3.3] and the references therein).
(8) The splitting field is at most a degree 2 extension of the rationals (see [29]).
We note that there are many other conditions known for the special case of distance-
regular graphs. It was decided to apply these conditions after the construction of the table,
and those not meeting these extra conditions were labelled as nonexistent with a note as
to the condition not met. We leave as an open question whether if any of these conditions
could be generalized to any cases beyond distance-regular graphs; this (perhaps faint) hope
is the main reason that they are included in the table.
We begin with the tables for Q-bipartite schemes, since this case is somewhat sim-
pler than the primitive case. Schemes which are Q-bipartite are formally dual to bipartite
distance-regular graphs. As a consequence, the formal dual to [5, Theorem 4.2.2(i)] gives
the Krein array for the quotient scheme of a Q-bipartite scheme (see [27]). Namely, if the
scheme has Krein array {b∗0, b∗1, . . . , b∗D−1; c∗1, . . . , c∗D} and q211 = µ∗, then the Krein array
of the quotient is{
b∗0b
∗
1
µ∗
,
b∗2b
∗
3
µ∗
, . . . ,
b∗2t−2b
∗
2t−1
µ∗
;
c∗1c
∗
2
µ∗
,
c∗3c
∗
4
µ∗
, . . . ,
c∗2t−1c
∗
2t
µ∗
}
,
where t = ⌊D2 ⌋. Note that the quotient scheme has multiplicities 1,m2,m4, . . . ,m2t,
from which it follows that the condition
∑t
i=0 m2i =
∑D−t
i=1 m2i−1 must be satisfied for a
D-class Q-bipartite scheme.
When D = 4, 5 we obtain t = 2, so the quotient structure is a strongly regular graph.
A database of strongly regular graph parameters up to 5000 vertices can be generated very
quickly. From there, we can use the above condition on the multiplicities. The following
proposition shows that the multiplicities determine all the parameters of the scheme.
Proposition 3.1. A D-class Q-bipartite Q-polynomial association scheme with D ∈ {4, 5}
and multiplicities 1,m1,m2, . . . ,mD has the Krein array{
m1,m1 − 1,
m1(m2 −m1 + 1)
m2
,
m1(m3 −m2 +m1 − 1)
m3
;
1,
m1(m1 − 1)
m2
,
m1(m2 −m1 + 1)
m3
,m1
} (D = 4)
or {
m1,m1−1,
m1(m2−m1+1)
m2
,
m1(m3−m2+m1−1)
m3
,
m1(m4−m3+m2−m1+1)
m4
;
1,
m1(m1−1)
m2
,
m1(m2−m1+1)
m3
,
m1(m3−m2+m1−1)
m4
,m1
}
(D = 5).
110 Ars Math. Contemp. 20 (2021) 103–127
Proof. Follows easily from the identities of [5, Lemma 2.3.1].
In the 4-class case, the parameters are entirely determined by the quotient’s multiplici-
ties (with a chosen Q-polynomial ordering) and m1. To search, we take a strongly regular
graph parameter set, choose one of two possible orderings for its multiplicities, calling its
multiplicities m0 = 1, m2, m4. From the absolute bound, we have 1 +m2 ≤ m1(m1+1)2 ,
and from the positivity of c∗2 we have
(m2−m1+1)m1
m2
≥ 0. We then search over all√
2(1 +m2) − 12 ≤ m1 ≤ m2, checking the conditions above. Given that we are iter-
ating over SRG parameters together with two orderings and one integer, this search is very
fast. The limitation of the table to 10000 vertices is mainly readability and practicality. The
third author has unpublished tables (without comments or details) to 100000 vertices.
We note that Q-bipartite schemes with 5 classes are very similar, except we must iterate
over both m1 and m3. Again, this is a very quick search, but the relative scarcity of 5-class
parameter sets makes listing up to 50000 vertices, with annotation, manageable. The table
actually goes slightly higher, to 50520 vertices, because of the existence of an example on
that number of vertices.
The trickiest search was the primitive 3-class Q-polynomial parameter sets. In this
case, there is no non-trivial quotient scheme to build on.
We use the following observation.
Theorem 3.2. A primitive Q-polynomial association scheme of 3 classes must have a ma-
trix Li with 4 distinct eigenvalues.
Proof. Assume not. If a matrix Ai has only two distinct eigenvalues, it is either complete,
contradicting the fact that it is a 3-class scheme, or a disjoint union of more than one
complete graph, contradicting the fact the scheme is primitive. Therefore, the only case left
to consider is when A1, A2, A3 all have three distinct eigenvalues, meaning the graphs are
all strongly regular. A 3-class scheme where every non-trivial relation is strongly-regular
is amorphic, see [19] and [14] for a definition and details on amorphic schemes. It was
shown in [20] that amorphic schemes are formally self-dual. This implies that no column
of Q has 4 distinct entries. Therefore, the second eigenmatrix Q cannot be generated by
one column via polynomials, thus the scheme cannot be Q-polynomial.
We note that, in fact, all Q-polynomial D-class schemes must have a relation with D+1
distinct eigenvalues. However, the above theorem and its proof is sufficient for our needs.
From this we conclude that each 3-class primitive Q-polynomial scheme has an ad-
jacency matrix, which we label A1, which has four distinct eigenvalues. Then the corre-
sponding 4 × 4 intersection matrix L1 has four distinct eigenvalues. From this matrix, all
of the other parameters may be determined. In particular, from [5, Proposition 2.2.2], the
left-eigenvectors of L1, normalized so their leftmost entry is 1, must be the rows of P .
The rest of the parameters can be derived from the equations:
Lj = P
−1 diag(P0j , P1j , . . . , PDj)P,
L∗j = Q
−1 diag(Q0j , Q1j , . . . , QDj)Q.
However, checking the Q-polynomial condition is done before the computation of all
parameters. We use the following theorem, a proof of which can be found in [30].
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 111
Theorem 3.3. Let Li be an intersection matrix of a D-class association scheme, where Li
has exactly D + 1 distinct eigenvalues. Then the scheme is Q-polynomial if and only if
there is a Vandermonde matrix U such that U−1LiU = T where T is upper triangular.
It is not hard to show that, without loss of generality, we can take T01 to be 0, implying
that the first column of U is an eigenvector of L1. We only then need to iterate over the
three (nontrivial) eigenvectors of L1 to check this condition. If the Q-polynomial condition
is met, the rest of the parameters are computed and checked for the above conditions.
The schemes are then split into types depending on whether there is a strongly regular
graph as a relation, and whether the splitting field is rational or not. These are split in this
manner to aid in computation (following the list of types we give details on how these were
used):
(1) Diameter 3 distance-regular graphs (DRG for short).
(2) No diameter 3 DRG, there is a strongly regular graph as a relation, the splitting field
is the rational field.
(3) No diameter 3 DRG, there is a strongly regular graph as a relation, the splitting field
is a degree-2 extension of the rational field.
(4) No diameter 3 DRG, there is no strongly regular graph as a relation, the splitting field
is the rational field.
(5) No diameter 3 DRG, there is no strongly regular graph as a relation, the splitting field
is a degree-2 extension of the rational field.
We note that we do not have any examples of primitive 3-class Q-polynomial schemes
with an irrational splitting field, but there are open parameter sets of such (for example, see
entry ⟨216, 20⟩ in the third author’s primitive 3-class table at [39]). It would be interesting
to determine if these exist. We also point out that all the feasible parameter sets known to
us have rational Krein parameters.
Type 1. For DRG’s, we iterated over the number of vertices, intersection array and valen-
cies. The order was n, b0 = n1, b1, n2 (noting n2 is a divisor of n1b1), then b2 (noting b2
must be a multiple of n3gcd(n2,n3) , where n3 = n− n1 − n2), from which the rest could be
determined.
When there is no DRG, it is tempting to try to formally dualize the above process.
However, the Krein parameters of a scheme do not have to be integral, or even rational.
For this reason, it seemed more advantageous to iterate over parameters that needed to be
integral, namely the parameters pkij . All arithmetic was done in MAGMA using the rational
field, or a splitting field of a degree two irreducible polynomial over the rationals. Floating
point arithmetic was avoided to minimize numerical errors.
For the rest of the types, L1 and the valencies were iterated over. In particular, the
parameters a = p112, b = p
1
13 and c = p
2
13, together with n, n1, n2 determine the rest of L1,
noting that a + b ≤ n1 − 1 and c ≤ n1 − n1an2 . Any matrix without 4 distinct eigenvalues
or with an irreducible cubic factor in its characteristic polynomial was discarded.
Types 2 and 3. For these types, we iterate over strongly regular graphs first, with param-
eters (n, k, λ, µ). We choose A3 to be the adjacency matrix of the strongly regular graph
relation, and L1, L2 to be fissions of the complement. Given this, the choice of n1 will
112 Ars Math. Contemp. 20 (2021) 103–127
determine n2. The possibilities for n1 can be narrowed by observing that p133 = µ, n3 = k
and p133n1 = p
3
13n3, implying that n1 is divisible by
n3
gcd(n3,µ)
.
Using similar identities, we find b is divisible by n3gcd(n1,n3) , a is divisible by
n2
gcd(n1,n2)
,
and c = n1(n3−b−µ)n2 . After choosing these parameters all of L1 follows.
Types 4 and 5. For these types, we know L1, L2 and L3 all have 4 distinct eigenvalues.
Therefore, we can assume n1 is the smallest valency, and that a ≤ b. Using a is divisible
by n2gcd(n1,n2) , b is divisible by
n3
gcd(n1,n3)
, and n2 divides an1, we choose n1, a, n2, b, c,
from which the rest is determined. This is the slowest part of the search, and the reason the
primitive table goes to 2800 vertices.
We close this section with some comments on the irrational splitting field types. The
2-class primitive Q-polynomial association schemes are equivalent to complementary pairs
of primitive strongly regular graphs. The only case where strongly regular graphs have an
irrational splitting field is the so-called “half-case”, when the graph has valency n−12 . Such
graphs do exist, for example the Paley graphs for non-square prime powers q with q ≡ 1
(mod 4). We note that no primitive Q-polynomial schemes with more than 2 classes and a
quadratic splitting field are known. All feasible parameter sets we know of are 3-class and
have a strongly regular graph relation (type 3). The corresponding strongly regular graphs
are also all unknown (see [4]). We have no feasible parameter set for type 5. However, one
type 5 parameter set satisfied all criteria except the handshaking lemma. Given this, we
expect feasible parameter sets for type 5 to exist, but may be quite large. This parameter
set is listed below (including L∗1, so it can be seen it is Q-polynomial, but not including the
other L∗i matrices), though this set is not included in the online table:
P =

1 285 285 405
1 19+8
√
19 −38+1
√
19 18−9
√
19
1 −3 5 −3
1 19−8
√
19 −38−1
√
19 18+9
√
19
, Q=

1 60 855 60
1 76+32
√
19
19
−9 76−32
√
19
19
1 −152+4
√
19
19
15 −152−4
√
19
19
1 8−4
√
19
3
−19
3
8+4
√
19
3
,
L1=

0 285 0 0
1 116 60 108
0 60 90 135
0 76 95 114
 , L2=

0 0 285 0
0 60 90 135
1 90 59 135
0 95 95 95
 , L3=

0 0 0 405
0 108 135 162
0 135 135 135
1 114 95 195
 ,
L∗1 =

0 60 0 0
1 400+32
√
19
61
3199−32
√
19
61
0
0 12796−128
√
19
3477
181184+128
√
19
3477
80
19
0 0 60 0
 .
While feasible parameters may exist, the complete lack of examples elicits the follow-
ing question:
Question 3.4. Do all 3-class primitive Q-polynomial schemes have a rational splitting
field?
This is a special case of the so-called “Sensible Caveman” conjecture of William J. Mar-
tin:
Conjecture 3.5. For Q-polynomial schemes of 3 or more classes that is not a polygon, if
the scheme is primitive then its splitting field is rational.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 113
4 Nonexistence results
We derived our nonexistence results by analyzing triple intersection numbers of Q-poly-
nomial association schemes. For some choice of relations Rr, Rs, Rt, the system of Dio-
phantine equations derived from (2.3) and Theorem 2.1 may have multiple nonnegative
solutions, each giving the possible values of the triple intersection numbers with respect to
a triple (x, y, z) with (x, y) ∈ Rr, (x, z) ∈ Rs and (y, z) ∈ Rt. However, in certain cases,
there might be no nonnegative solutions – in this case, we may conclude that an association
scheme with the given parameters does not exist.
Even when there are solutions for all choices of Rr, Rs, Rt such that ptrs ̸= 0, some-
times nonexistence can be derived by other means. We may, for example, employ double
counting.
Proposition 4.1. Let x and y be vertices of an association scheme with (x, y) ∈ Rr.
Suppose that α1, α2, . . . , αm are distinct integers such that there are precisely κℓ vertices
z with (x, z) ∈ Rs, (y, z) ∈ Rt and
[
x y z
i j k
]
= αℓ (1 ≤ ℓ ≤ m,
∑m
ℓ=1 κℓ = p
r
st),
and β1, β2, . . . , βn are distinct integers such that there are precisely λℓ vertices w with
(w, x) ∈ Ri, (w, y) ∈ Rj and
[
w x y
k s t
]
= βℓ (1 ≤ ℓ ≤ n,
∑n
ℓ=1 λℓ = p
r
ij). Then,
m∑
ℓ=1
κℓαℓ =
n∑
ℓ=1
λℓβℓ.
Proof. Count the number of pairs (w, z) with (x, z) ∈ Rs, (y, z) ∈ Rt, (w, x) ∈ Ri,
(w, y) ∈ Rj and (w, z) ∈ Rk.
We consider the special case of Proposition 4.1 when a triple intersection number is
zero for all triples of vertices in some given relations.
Corollary 4.2. Suppose that for all vertices x, y, z of an association scheme with (x, y) ∈
Rr, (x, z) ∈ Rs, (y, z) ∈ Rt,
[
x y z
i j k
]
= 0 holds. Then,
[
w x y
k s t
]
= 0 holds for all
vertices w, x, y with (w, x) ∈ Ri, (w, y) ∈ Rj and (x, y) ∈ Rr.
Proof. Apply Proposition 4.1 to all (x, y) ∈ Rr, with m ≤ 1 and α1 = 0. Since βℓ and λℓ
(1 ≤ ℓ ≤ n) must be nonnegative, it follows that n ≤ 1 and β1 = 0.
4.1 Computer search
The sage-drg package [38, 37] by the second author for the SageMath computer al-
gebra system [32] has been used to perform computations of triple intersection numbers
of Q-polynomial association schemes with Krein arrays that were marked as open in the
tables of feasible parameter sets by the third author [39], see Section 3. The package
was originally developed for the purposes of feasibility checking for intersection arrays of
distance-regular graphs and included a routine to find general solutions to the system of
equations for computing triple intersection numbers.
For the purposes of the current research, the package has been extended to support
parameters of general association schemes, in particular, given as Krein arrays of Q-poly-
nomial association schemes. Additionally, the package now supports generating integral
solutions for systems of equations with constraints on the solutions (e.g., nonnegativity of
114 Ars Math. Contemp. 20 (2021) 103–127
triple intersection numbers) – these can also be added on-the-fly. The routine uses Sage-
Math’s mixed integer linear programming facilities, which support multiple solvers. We
have used SageMath’s default GLPK solver [26] and the CBC solver [16] in our computa-
tions – however, other solvers can also be used if they are available.
We have thus been able to implement an algorithm which tries to narrow down the
possible solutions of the systems of equations for determining triple intersection numbers
of an association scheme such that they satisfy Corollary 4.2, and conclude inequality if
any of the systems of equations has no such feasible solutions.
(1) For each triple of relations (Rr, Rs, Rt) such that ptrs > 0, initialize an empty
set of solutions, obtain a general (i.e., parametric) solution to the system of equa-
tions derived from (2.3) and Theorem 2.1, and initialize a generator of solutions
with the constraint that the intersection numbers be integral and nonnegative. All
generators (r, s, t) are initially marked as active, and all triple intersection num-
bers (r, s, t; i, j, k) (representing
[
x y z
i j k
]
with (x, y) ∈ Rr, (x, z) ∈ Rs and
(y, z) ∈ Rt) are initially marked as unknown.
(2) For each active generator, generate one solution and add it to the corresponding set
of solutions. If a generator does not return a new solution (i.e., it has exhausted all
of them), then mark it as inactive.
(3) For each inactive generator, verify that the corresponding set of solutions is non-
empty – otherwise, terminate and conclude nonexistence.
(4) Initialize an empty set Z.
(5) For each unknown triple intersection number (r, s, t; i, j, k), mark it as nonzero if a
solution has been found in which its value is not zero. If such a solution has not been
found yet, make a copy of the generator (r, s, t) with the constraint that (r, s, t; i, j, k)
be nonzero, and generate one solution. If such a solution exists, add it to the set of
solutions and mark (r, s, t; i, j, k) as nonzero, otherwise mark (r, s, t; i, j, k) as zero
and add it to Z.
(6) If Z is empty, terminate without concluding nonexistence.
(7) For each triple intersection number (r, s, t; i, j, k) ∈ Z and for each nonzero (a, b, c;
d, e, f) ∈ {(r, i, j; s, t, k), (s, i, k; r, t, j), (t, j, k; r, s, i)}, remove all solutions from
the corresponding set in which the value of the latter is nonzero, mark (a, b, c; d, e, f)
as zero, mark all nonzero (a, b, c; ℓ,m, n) with (ℓ,m, n) ̸= (d, e, f) as unknown, and
add a constraint that (a, b, c; d, e, f) be zero to the generator (a, b, c) if it is active.
(8) Go to (2).
Note that generators and triple intersection numbers are considered equivalent under
permutation of vertices, i.e., under actions (r, s, t) 7→ (r, s, t)π and (r, s, t; i, j, k) 7→
((r, s, t)π; (i, j, k)π
(1 3)
) for π ∈ S3.
The above algorithm is available as the check_quadruples method of sage-drg’s
ASParameters class. We ran it for all open cases in the tables from Section 3, and ob-
tained 29 nonexistence results for primitive 3-class schemes, 92 nonexistence results for
Q-bipartite 4-class schemes, and 11 nonexistence results for Q-bipartite 5-class schemes.
The results are summarized in the following theorem and in the tables in Appendix A.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 115
Theorem 4.3. A Q-polynomial association scheme with Krein array listed in one of Ta-
bles 1, 2 and 3 does not exist.
Proof. In all but two cases, it suffices to observe that for some triple of relations Rr, Rs, Rt,
the system of equations derived from (2.3) and Theorem 2.1 has no integral nonnegative
solutions – Tables 1 and 2 list the triple (r, s, t), while for all examples in Table 3, this is
true for (r, s, t) = (1, 1, 1). Note that the natural ordering of the relations is used.
Let us now consider the cases ⟨225, 24⟩ and ⟨1470, 104⟩ from Table 1. In the first case,
the Krein array is {24, 20, 36/11; 1, 30/11, 24}. Such an association scheme has two Q-
polynomial orderings, so we can augment the system of equations (2.3) with six equations
derived from Theorem 2.1. Let w, x, y, z be vertices such that (x, z), (y, z) ∈ R1 and
(w, x), (w, y), (x, y) ∈ R3. Since p311 = 22 and p333 = 3, such vertices must exist. We
first compute the triple intersection numbers with respect to x, y, z. There are two integral
nonnegative solutions, both having [3 3 1] = 0. On the other hand, there is a single solution
for the triple intersection numbers with respect to w, x, y, giving [1 1 1] = 3. However, this
contradicts Corollary 4.2, so such an association scheme does not exist.
In the second case, the Krein array is {104, 70, 25; 1, 7, 80}. Let w, x, y, z be vertices
such that (x, y), (x, z) ∈ R1, (w, y), (y, z) ∈ R2 and (w, x) ∈ R3. Since p112 = 70 and
p132 = 250, such vertices must exist. There is a single solution for the triple intersection
numbers with respect to x, y, z, giving [3 2 3] = 0. On the other hand, there are four
solutions for the triple intersection numbers with respect to w, x, y, from which we obtain
[3 1 2] ∈ {15, 16, 17, 18}. Again, this contradicts Corollary 4.2, so such an association
scheme does not exist. This completes the proof.
Remark 4.4. The sage-drg package repository provides two Jupyter notebooks con-
taining the computation details in the proofs of nonexistence of two cases from Table 1:
• QPoly-24-20-36_11-1-30_11-24.ipynb for the case ⟨225, 24⟩, and
• DRG-104-70-25-1-7-80.ipynb for the case ⟨1470, 104⟩.
Remark 4.5. The parameter set ⟨91, 12⟩ from Table 1 was listed by Van Dam [12] as the
smallest feasible Q-polynomial parameter set for which no scheme is known. The next
such open case is now the Krein array {14, 108/11, 15/4; 1, 24/11, 45/4} for a primitive
3-class Q-polynomial association scheme with 99 vertices, which was also listed by Van
Dam.
Since some of the parameters from Table 1 also admit a P -polynomial ordering, we
can derive nonexistence of distance-regular graphs with certain intersection arrays. We
have also found an intersection array for a primitive Q-polynomial distance-regular graph
of diameter 4, which is listed in [5] and [3], and for which, to the best of our knowledge,
nonexistence has not been previously known.
Theorem 4.6. There is no distance-regular graph with intersection array
{83, 54, 21; 1, 6, 63},
{104, 70, 25; 1, 7, 80},
{195, 160, 28; 1, 20, 168},
{125, 108, 24; 1, 9, 75},
{126, 90, 10; 1, 6, 105}, or
{203, 160, 34; 1, 16, 170}.
116 Ars Math. Contemp. 20 (2021) 103–127
Proof. The cases ⟨1080, 83⟩, ⟨1470, 104⟩, ⟨2016, 195⟩ and ⟨2640, 203⟩ from Table 1 are
formally self-dual for the natural ordering of relations, while ⟨2197, 126⟩ is formally self-
dual with ordering of relations A2, A3, A1 relative to the natural ordering. In each case,
the corresponding association scheme is P -polynomial with intersection array equal to
the Krein array. The case ⟨2106, 65⟩ is not formally self-dual, yet the natural ordering
of relations is P -polynomial with intersection array {125, 108, 24; 1, 9, 75}. In all of the
above cases, Theorem 4.3 implies nonexistence of the corresponding association scheme,
so a distance-regular graph with such an intersection array does not exist.
Theorem 4.7. There is no distance-regular graph with intersection array
{53, 40, 28, 16; 1, 4, 10, 28}.
Proof. Consider a distance-regular graph with intersection array {53, 40, 28, 16; 1, 4, 10,
28}. Such a graph is formally self-dual for the natural ordering of eigenspaces and there-
fore also Q-polynomial. Augmenting the system of equations (2.3) with twelve equations
derived from Theorem 2.1 gives a two parameter solution for triple intersection numbers
with respect to three vertices mutually at distances 1, 3, 3. However, it turns out that there
is no integral solution, leading to nonexistence of the graph.
Remark 4.8. The non-existence of a distance-regular graph with intersection array {53, 40,
28, 16; 1, 4, 10, 28} also follows by applying the Terwilliger polynomial [17]. Recall that
this polynomial, say TΓ(x), which depends only on the intersection numbers of a Q-
polynomial distance-regular graph Γ and its Q-polynomial ordering, satisfies:
TΓ(η) ≥ 0, (4.1)
where η is any non-principal eigenvalue of the local graph of an arbitrary vertex x of Γ.
Furthermore, by [5, Theorem 4.4.3(i)], η satisfies
−1− b1
θ1 + 1
≤ η ≤ −1− b1
θD + 1
, (4.2)
where b0 = θ0 > θ1 > · · · > θD are the D + 1 distinct eigenvalues of Γ.
For the above-mentioned intersection array, TΓ(x) is a polynomial of degree 4 with a
negative leading term and the following roots: − 73 (= −1−
b1
θ1+1
), 9−
√
249
4 ≈ −1.695,
17
3
(= −1− b1θD+1 ),
9+
√
249
9 ≈ 6.195.
Thus, combining (4.1) and (4.2), we obtain
−7
3
≤ η ≤ 9−
√
249
4
or η =
17
3
,
and one can finally obtain a contradiction as in [18, Claim 4.3].
4.2 Infinite families
The data from Tables 1, 2 and 3 allows us to look for infinite families of Krein arrays for
which we can show nonexistence of corresponding Q-polynomial association schemes. We
find three families, one for each number of classes.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 117
The first family of Krein arrays is given by
{2r2 − 1, 2r2 − 2, r2 + 1; 1, 2, r2 − 1}. (4.3)
This Krein array is feasible for all integers r ≥ 2. A Q-polynomial association scheme
with Krein array (4.3) has 3 classes and 4r4 vertices. Examples exist when r is a power of
2 – they are realized by duals of Kasami codes with minimum distance 5, see [5, §11.2].
Theorem 4.9. A Q-polynomial association scheme with Krein array (4.3) and r odd does
not exist.
Proof. Consider a Q-polynomial association scheme with Krein array (4.3). Besides the
Krein parameters failing the triangle inequality, q111 is also zero. Therefore, in order to
compute triple intersection numbers, the system of equations (2.3) can be augmented with
four equations derived from Theorem 2.1. We compute triple intersection numbers with
respect to vertices x, y, z such that (x, y), (x, z) ∈ R1 and (y, z) ∈ R2. Since p211 =
r(r+2)(r2 − 1)/4 > 0, such vertices must exist. We obtain a four parameter solution (see
the notebook QPoly-d3-1param-odd.ipynb on the sage-drg package repository
for computation details). Then we may express
[1 2 3] = −r
4
2
+ 2r2 + [1 3 1] + 3 · [2 3 3]− [3 1 1] + 4 · [3 3 3].
Clearly, the above triple intersection number can only be integral when r is even. Therefore,
we conclude that a Q-polynomial association scheme with Krein array (4.3) and r odd does
not exist.
The next family is a two parameter family of Krein arrays
{m,m− 1,m(r2 − 1)/r2,m− r2 + 1; 1,m/r2, r2 − 1,m}. (4.4)
This Krein array is feasible for all integers m and r such that 0 < 2(r2 − 1) ≤ m ≤
r(r − 1)(r + 2) and m(r + 1) is even. A Q-polynomial association scheme with Krein
array (4.4) is Q-bipartite with 4 classes and 2m2 vertices. One may take the Q-bipartite
quotient of such a scheme (i.e., identify vertices in relation R4) to obtain a strongly regular
graph with parameters (n, k, λ, µ) = (m2, (m − 1)r2,m + r2(r2 − 3), r2(r2 − 1)), i.e.,
a pseudo-Latin square graph. Therefore, we say that a scheme with Krein array (4.4) is of
Latin square type.
There are several examples of Q-polynomial association schemes with Krein array (4.4)
for some r and m. For (r,m) = (2, 6) and (r,m) = (3, 16), this Krein array is realized
by the schemes of shortest vectors of the E6 lattice and an overlattice of the Barnes-Wall
lattice in R16 [28], respectively. For (r,m) = (2ij , 2i(2j+1)), there are examples arising
from duals of extended Kasami codes [5, §11.2] for each choice of positive integers i and
j. In particular, the Krein array obtained by setting i = j = 1 uniquely determines the
halved 8-cube.
In the case when r is a prime power and m = r3, the formal dual of this parameter
set (i.e., a distance-regular graph with the corresponding intersection array) is realized by
a Pasechnik graph [6].
Theorem 4.10. A Q-polynomial association scheme with Krein array (4.4) and m odd
does not exist.
118 Ars Math. Contemp. 20 (2021) 103–127
Proof. Consider a Q-polynomial association scheme with Krein array (4.4). Since the
scheme is Q-bipartite, we have qkij = 0 whenever i+ j+k is odd or the triple (i, j, k) does
not satisfy the triangle inequality. This allows us to augment the system of equations (2.3)
with many equations derived from Theorem 2.1. We compute triple intersection numbers
with respect to vertices x, y, z such that (x, y), (x, z) ∈ R1 and (y, z) ∈ R2. Since p211 =
r2(r2 − 1)/2 > 0, such vertices must exist. We obtain a one parameter solution (see
the notebook QPoly-d4-LS-odd.ipynb on the sage-drg package repository for
computation details) which allows us to express
[1 1 3] = r +
r2(1− r)
2
− m
2
+ [1 1 1].
Clearly, the above triple intersection number can only be integral when m is even. There-
fore, we conclude that a Q-polynomial association scheme with Krein array (4.4) and m
odd does not exist.
The last family is given by the Krein array{
r2 + 1
2
,
r2 − 1
2
,
(r2 + 1)2
2r(r + 1)
,
(r − 1)(r2 + 1)
4r
,
r2 + 1
2r
;
1,
(r − 1)(r2 + 1)
2r(r + 1)
,
(r + 1)(r2 + 1)
4r
,
(r − 1)(r2 + 1)
2r
,
r2 + 1
2
}
.
(4.5)
This Krein array is feasible for all odd r ≥ 5. A Q-polynomial association scheme with
Krein array (4.5) is Q-bipartite with 5 classes and 2(r+1)(r2 +1) vertices. One may take
the Q-bipartite quotient of such a scheme to obtain a strongly regular graph with parameters
(n, k, λ, µ) = ((r+1)(r2 +1), r(r+1), r− 1, r+1) – these are precisely the parameters
of collinearity graphs of generalized quadrangles GQ(r, r). The scheme also has a second
Q-polynomial ordering of eigenspaces, namely the ordering E5, E2, E3, E4, E1 relative to
the ordering implied by the Krein array. For r ≡ 1 (mod 4) a prime power, the Krein
array (4.5) is realized by a scheme derived by Moorhouse and Williford [30] from a double
cover of the C2(r) dual polar graph.
Theorem 4.11. A Q-polynomial association scheme with Krein array (4.5) and r ≡ 3
(mod 4) does not exist.
Proof. Consider a Q-polynomial association scheme with Krein array (4.5). Since the
scheme is Q-bipartite, we have qkij = 0 whenever i + j + k is odd or the triple (i, j, k)
does not satisfy the triangle inequality. This allows us to augment the system of equa-
tions (2.3) with many equations derived from Theorem 2.1. We compute triple inter-
section numbers with respect to vertices x, y, z that are mutually in relation R1. Since
p111 = (r − 1)/2 > 0, such vertices must exist. We obtain a single solution (see the note-
book QPoly-d5-1param-3mod4.ipynb on the sage-drg package repository for
computation details) with
[1 1 1] =
r − 5
4
.
Clearly, the above triple intersection number can only be integral when r ≡ 1 (mod 4).
Therefore, we conclude that a Q-polynomial association scheme with Krein array (4.5) and
r ≡ 3 (mod 4) does not exist.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 119
5 Quadruple intersection numbers
The argument of the proof of Theorem 2.1 ([5, Theorem 2.3.2]) can be further extended
to s-tuples of vertices (see Remark (iii) in [5, §2.3]; cf. [34, Lemma 4(2)]). In particular,
we may consider quadruple intersection numbers with respect to a quadruple of vertices
w, x, y, z ∈ X . For integers h, i, j, k (0 ≤ h, i, j, k ≤ D), denote by
[
w x y z
h i j k
]
(or
simply [h i j k] when it is clear which quadruple (w, x, y, z) we have in mind) the number
of vertices u ∈ X such that (u,w) ∈ Rh, (u, x) ∈ Ri, (u, y) ∈ Rj , and (u, z) ∈ Rk.
For a fixed quadruple (w, x, y, z), one can obtain a system of linear Diophantine equa-
tions with quadruple intersection numbers as variables which relates them to the intersec-
tion numbers (or to the triple intersection numbers).
The following analogue of Theorem 2.1 allows us to obtain some additional equations.
Theorem 5.1. Let (X, {Ri}Di=0) be an association scheme of D classes with second eigen-
matrix Q and Krein parameters qkij (0 ≤ i, j, k ≤ D). Then, for fixed indices ι1, ι2, ι3, ι4
(0 ≤ ι1, ι2, ι3, ι4 ≤ D) and any permutation p, r, s, t of ι1, ι2, ι3, ι4,
D∑
ℓ=0
qℓprq
ℓ
st = 0 ⇐⇒
D∑
h,i,j,k=0
QhpQirQjsQkt
[
w x y z
h i j k
]
= 0 for all w, x, y, z ∈ X .
Proof. Since Ei is a symmetric idempotent matrix, one has∑
w∈X
Ei(u,w)Ei(v, w) = Ei(u, v). (5.1)
Let Σ(M) denote the sum of all entries of a matrix M . Then, by (5.1),
Σ(Ep ◦ Er ◦ Es ◦ Et) =
∑
u,v∈X
Ep(u, v)Er(u, v)Es(u, v)Et(u, v)
=
∑
w,x,y,z∈X
(∑
u∈X
Ep(u,w)Er(u, x)Es(u, y)Et(u, z)
)
·
(∑
v∈X
Ep(v, w)Er(v, x)Es(v, y)Et(v, z)
)
=
∑
w,x,y,z∈X
σ(w, x, y, z)2 ≥ 0, (5.2)
where σ(w, x, y, z) =
∑
u∈X Ep(u,w)Er(u, x)Es(u, y)Et(u, z).
On the other hand, by (2.1),
|X|2 Σ(Ep ◦ Er ◦ Es ◦ Et) = |X|2 Tr((Ep ◦ Er) · (Es ◦ Et))
= Tr
((
D∑
ℓ=0
qℓprEℓ
)
·
(
D∑
ℓ=0
qℓstEℓ
))
=
D∑
ℓ=0
mℓq
ℓ
prq
ℓ
st, (5.3)
120 Ars Math. Contemp. 20 (2021) 103–127
where mℓ is the rank of Eℓ (i.e., the multiplicity of the corresponding eigenspace), and by
(2.2),
|X|3 Σ(Ep ◦ Er ◦ Es ◦ Et) =
1
|X|
D∑
ℓ=0
QℓpQℓrQℓsQℓtΣ(Aℓ)
=
D∑
ℓ=0
nℓQℓpQℓrQℓsQℓt, (5.4)
where nℓ is the valency of (X,Rℓ).
Since the multiplicities mℓ are positive numbers and the Krein parameters are non-
negative numbers, by (5.2), (5.3), (5.4), we have Σ(Ep ◦ Er ◦ Es ◦ Et) = 0 if and only if
qℓprq
ℓ
st = 0 (with fixed p, r, s, t) for all ℓ = 0, . . . , D. In this case, we have σ(w, x, y, z) = 0
for all quadruples (w, x, y, z), which implies
0 = |X|4 σ(w, x, y, z) = |X|4
∑
u∈X
Ep(u,w)Er(u, x)Es(u, y)Et(u, z)
=
D∑
h,i,j,k=0
QhpQirQjsQkt
[
w x y z
h i j k
]
,
which completes the proof.
The condition of Theorem 5.1 is satisfied when, for example, an association scheme is
Q-bipartite, i.e., qkij = 0 whenever i+ j+k is odd (take p+ r and s+ t of different parity).
Suda [33] lists several families of association schemes which are known to be triply reg-
ular, i.e., their triple intersection numbers
[
x y z
i j k
]
only depend on i, j, k and the mutual
distances between x, y, z, and not on the choices of the vertices themselves:
• strongly regular graphs with q111 = 0 (cf. [8]),
• Taylor graphs (antipodal Q-bipartite schemes of 3 classes),
• linked systems of symmetric designs (certain Q-antipodal schemes of 3 classes) with
a∗1 = 0,
• tight spherical 7-designs (certain Q-bipartite schemes of 4 classes), and
• collections of real mutually unbiased bases (Q-antipodal Q-bipartite schemes of 4
classes).
Schemes belonging to the above families seem natural candidates for the computations of
their quadruple intersection numbers. However, the condition of Theorem 5.1 is never sat-
isfied for primitive strongly regular graphs, while for Taylor graphs the obtained equations
do not give any information that could not be obtained through relating the quadruple inter-
section numbers to the triple intersection numbers. This was also the case for the examples
of triply regular linked systems of symmetric designs that we have checked. However, in
the cases of tight spherical 7-designs and mutually unbiased bases, we do get new restric-
tions on quadruple intersection numbers. So far, we have not succeeded in using this new
information for either new constructions or proofs of nonexistence.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 121
ORCID iDs
Alexander L. Gavrilyuk https://orcid.org/0000-0001-9296-0313
Janoš Vidali https://orcid.org/0000-0001-8061-9169
Jason S. Williford https://orcid.org/0000-0002-8697-5997
References
[1] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, The Benjamin/Cum-
mings Publishing, Menlo Park, CA, 1984.
[2] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J.
Symbolic Comput. 24 (1997), 235–265, doi:10.1006/jsco.1996.0125.
[3] A. E. Brouwer, Parameters of distance-regular graphs, 2011, http://www.win.tue.nl/
~aeb/drg/drgtables.html.
[4] A. E. Brouwer, Strongly regular graphs, 2013, http://www.win.tue.nl/~aeb/
graphs/srg/srgtab.html.
[5] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, volume 18 of
Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin, 1989, doi:
10.1007/978-3-642-74341-2.
[6] A. E. Brouwer and D. V. Pasechnik, Two distance-regular graphs, J. Algebraic Combin. 36
(2012), 403–407, doi:10.1007/s10801-011-0341-1.
[7] P. J. Cameron, J.-M. Goethals and J. J. Seidel, The Krein condition, spherical designs, Norton
algebras and permutation groups, Nederl. Akad. Wetensch. Indag. Math. 40 (1978), 196–206,
doi:10.1016/1385-7258(78)90037-9.
[8] P. J. Cameron, J.-M. Goethals and J. J. Seidel, Strongly regular graphs having strongly regular
subconstituents, J. Algebra 55 (1978), 257–280, doi:10.1016/0021-8693(78)90220-x.
[9] D. R. Cerzo and H. Suzuki, Non-existence of imprimitive Q-polynomial schemes of excep-
tional type with d = 4, European J. Combin. 30 (2009), 674–681, doi:10.1016/j.ejc.2008.07.
014.
[10] K. Coolsaet and A. Jurišić, Using equality in the Krein conditions to prove nonexistence of
certain distance-regular graphs, J. Comb. Theory Ser. A 115 (2008), 1086–1095, doi:10.1016/j.
jcta.2007.12.001.
[11] E. van Dam, W. Martin and M. Muzychuk, Uniformity in association schemes and coherent
configurations: cometric Q-antipodal schemes and linked systems, J. Comb. Theory Ser. A 120
(2013), 1401–1439, doi:10.1016/j.jcta.2013.04.004.
[12] E. R. van Dam, Three-class association schemes, J. Algebraic Combin. 10 (1999), 69–107,
doi:10.1023/a:1018628204156.
[13] E. R. van Dam, J. H. Koolen and H. Tanaka, Distance-regular graphs, Electron. J. Combin.
(2016), #DS22, doi:10.37236/4925.
[14] E. R. van Dam and M. Muzychuk, Some implications on amorphic association schemes, J.
Comb. Theory Ser. A 117 (2010), 111–127, doi:10.1016/j.jcta.2009.03.018.
[15] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res.
Rep. Suppl. 10, Philips Research Laboratories, 1973.
[16] J. Forrest, T. Ralphs, S. Vigerske, L. Hafer, B. Kristjansson, J. P. Fasano, E. Straver, M. Lu-
bin, H. G. Santos, R. Lougee and M. Saltzman, coin-or/Cbc (COIN-OR Branch-and-
Cut MIP Solver), Version 2.9.4, 2015, doi:10.5281/zenodo.1317566, https://projects.
coin-or.org/Cbc.
122 Ars Math. Contemp. 20 (2021) 103–127
[17] A. L. Gavrilyuk and J. H. Koolen, The Terwilliger polynomial of a Q-polynomial distance-
regular graph and its application to pseudo-partition graphs, Linear Algebra Appl. 466 (2015),
117–140, doi:10.1016/j.laa.2014.09.048.
[18] A. L. Gavrilyuk and J. H. Koolen, A characterization of the graphs of bilinear (d × d)-forms
over F2, Combinatorica 39 (2019), 289–321, doi:10.1007/s00493-017-3573-4.
[19] T. Ikuta, T. Ito and A. Munemasa, On pseudo-automorphisms and fusions of an association
scheme, European J. Combin. 12 (1991), 317–325, doi:10.1016/s0195-6698(13)80114-x.
[20] T. Ito, A. Munemasa and M. Yamada, Amorphous association schemes over the Galois rings
of characteristic 4, European J. Combin. 12 (1991), 513–526, doi:10.1016/s0195-6698(13)
80102-3.
[21] A. Jurišić, J. Koolen and P. Terwilliger, Tight distance-regular graphs, J. Algebraic Combin. 12
(2000), 163–197, doi:10.1023/a:1026544111089.
[22] A. Jurišić and J. Vidali, Extremal 1-codes in distance-regular graphs of diameter 3, Des. Codes
Cryptogr. 65 (2012), 29–47, doi:10.1007/s10623-012-9651-0.
[23] A. Jurišić and J. Vidali, Restrictions on classical distance-regular graphs, J. Algebraic Combin.
46 (2017), 571–588, doi:10.1007/s10801-017-0765-3.
[24] B. G. Kodalen, Cometric Association Schemes, Ph.D. thesis, Worcester Polytechnic Institute,
2019, arXiv:1905.06959 [math.CO].
[25] B. G. Kodalen, Linked systems of symmetric designs, Algebr. Comb. 2 (2019), 119–147, doi:
10.5802/alco.22.
[26] A. Makhorin, GLPK (GNU Linear Programming Kit), Version 4.63.p2, 2012, http://www.
gnu.org/software/glpk/.
[27] W. J. Martin, M. Muzychuk and J. Williford, Imprimitive cometric association schemes:
constructions and analysis, J. Algebraic Combin. 25 (2007), 399–415, doi:10.1007/
s10801-006-0043-2.
[28] W. J. Martin and H. Tanaka, Commutative association schemes, European J. Combin. 30
(2009), 1497–1525, doi:10.1016/j.ejc.2008.11.001.
[29] W. J. Martin and J. Williford, There are finitely many Q-polynomial association schemes with
given first multiplicity at least three, European J. Combin. 30 (2009), 698–704, doi:10.1016/j.
ejc.2008.07.009.
[30] G. E. Moorhouse and J. Williford, Double covers of symplectic dual polar graphs, Discrete
Math. 339 (2016), 571–588, doi:10.1016/j.disc.2015.09.015.
[31] T. Penttila and J. Williford, New families of Q-polynomial association schemes, J. Comb. The-
ory Ser. A 118 (2011), 502–509, doi:10.1016/j.jcta.2010.08.001.
[32] The Sage Developers, Sagemath, the Sage Mathematics Software System (Version 7.6), 2017,
http://www.sagemath.org.
[33] S. Suda, Coherent configurations and triply regular association schemes obtained from spheri-
cal designs, J. Comb. Theory Ser. A 117 (2010), 1178–1194, doi:10.1016/j.jcta.2010.03.016.
[34] H. Suzuki, Imprimitive Q-polynomial association schemes, J. Algebraic Combin. 7 (1998),
165–180, doi:10.1023/a:1008660421667.
[35] H. Tanaka and R. Tanaka, Nonexistence of exceptional imprimitive Q-polynomial association
schemes with six classes, European J. Combin. 32 (2011), 155–161, doi:10.1016/j.ejc.2010.09.
006.
[36] M. Urlep, Triple intersection numbers of Q-polynomial distance-regular graphs, European J.
Combin. 33 (2012), 1246–1252, doi:10.1016/j.ejc.2012.02.005.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 123
[37] J. Vidali, Using symbolic computation to prove nonexistence of distance-regular graphs, Elec-
tron. J. Combin. 25 (2018), #P4.21, doi:10.37236/7763.
[38] J. Vidali, jaanos/sage-drg: sage-drg Sage Package, Version 0.9, 2019, doi:10.5281/
zenodo.3350856.
[39] J. S. Williford, Homepage, 2018, http://www.uwyo.edu/jwilliford/.
124 Ars Math. Contemp. 20 (2021) 103–127
Appendix A Tables of nonexistence results
Here, we give the tables of nonexistence results obtained by running the algorithm from
Subsection 4.1 on the open cases in the tables from Section 3. Tables 1, 2 and 3 give
nonexistence results for Q-polynomial schemes which are primitive of 3 classes, and Q-
bipartite (but not Q-antipodal) of 4 and 5 classes, respectively.
Label Krein array DRG Nonexistence Family
⟨91, 12⟩ {12, 338
35
, 39
25
; 1, 312
175
, 39
5
} (3, 3, 3)
⟨225, 24⟩ {24, 20, 36
11
; 1, 30
11
, 24} (3, 1, 1; 3, 3, 1)
⟨324, 17⟩ {17, 16, 10; 1, 2, 8} (1, 1, 2) (4.3)
⟨324, 19⟩ {19, 128
9
, 10; 1, 16
9
, 10} (1, 1, 3)
⟨441, 20⟩ {20, 378
25
, 12; 1, 42
25
, 9} (1, 1, 3)
⟨540, 33⟩ {33, 20, 63
5
; 1, 12
5
, 15} (1, 1, 3)
⟨540, 35⟩ {35, 243
10
, 27
2
; 1, 27
10
, 45
2
} (1, 1, 3)
⟨576, 23⟩ {23, 432
25
, 15; 1, 48
25
, 9} (1, 1, 3)
⟨729, 26⟩ {26, 486
25
, 18; 1, 54
25
, 9} (1, 1, 3)
⟨1000, 37⟩ {37, 24, 14; 1, 2, 12} (1, 1, 3)
⟨1015, 28⟩ {28, 2523
130
, 4263
338
; 1, 1218
845
, 203
26
} (1, 1, 3)
⟨1080, 83⟩ {83, 54, 21; 1, 6, 63} FSD (1, 1, 2)
⟨1134, 49⟩ {49, 48, 644
75
; 1, 196
75
, 42} (1, 1, 1)
⟨1189, 40⟩ {40, 5043
203
, 123
7
; 1, 615
406
, 164
7
} (1, 1, 2)
⟨1470, 104⟩ {104, 70, 25; 1, 7, 80} FSD (1, 1, 2; 3, 2, 3)
⟨1548, 35⟩ {35, 2187
86
, 45
2
; 1, 135
86
, 27
2
} (1, 1, 3)
⟨1680, 69⟩a {69, 42, 7; 1, 2, 63} (1, 1, 2)
⟨1702, 45⟩ {45, 4761
148
, 115
4
; 1, 345
148
, 69
4
} (1, 1, 2)
⟨1944, 29⟩ {29, 22, 25; 1, 2, 5} (1, 1, 2)
⟨2016, 195⟩ {195, 160, 28; 1, 20, 168} FSD (1, 2, 2)
⟨2106, 65⟩ {65, 64, 676
25
; 1, 104
25
, 26} {125, 108, 24; 1, 9, 75} (1, 1, 1)
⟨2185, 114⟩ {114, 4761
65
, 58121
1521
; 1, 11799
1690
, 6118
117
} (1, 1, 3)
⟨2197, 36⟩ {36, 45
2
, 45
2
; 1, 3
2
, 15
2
} (1, 1, 3)
⟨2197, 126⟩ {126, 90, 10; 1, 6, 105} FSD (0231) (2, 2, 3)
⟨2304, 47⟩ {47, 135
4
, 33; 1, 9
4
, 15} (1, 1, 3)
⟨2376, 95⟩ {95, 63, 12; 1, 3, 84} (1, 1, 3)
⟨2401, 48⟩ {48, 30, 29; 1, 3
2
, 20} (1, 1, 2)
⟨2500, 49⟩a {49, 48, 26; 1, 2, 24} (1, 1, 2) (4.3)
⟨2640, 203⟩ {203, 160, 34; 1, 16, 170} FSD (1, 2, 2)
Table 1: Nonexistence results for feasible Krein arrays of primitive 3-class Q-polynomial
association schemes on up to 2800 vertices. For P -polynomial parameters (for the natural
ordering of relations, unless otherwise indicated), the DRG column indicates whether the
parameters are formally self-dual (FSD), or the intersection array is given. The Nonex-
istence column gives either the triple of relation indices for which there is no solution
for triple intersection numbers, or the 6-tuple of relation indices (r, s, t; i, j, k) for which
Corollary 4.2 is not satisfied. The Family column specifies the infinite family from Subsec-
tion 4.2 that the parameter set is part of.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 125
Label Krein array Nonexistence Family
⟨200, 12⟩ {12, 11, 256
25
, 36
11
; 1, 44
25
, 96
11
, 12} (1, 1, 2)
⟨462, 21⟩ {21, 20, 196
11
, 49
5
; 1, 35
11
, 56
5
, 21} (1, 1, 2)
⟨486, 45⟩ {45, 44, 36, 5; 1, 9, 40, 45} (1, 1, 2)
⟨578, 17⟩ {17, 16, 136
9
, 9; 1, 17
9
, 8, 17} (1, 1, 2) (4.4)
⟨686, 28⟩ {28, 27, 25, 8; 1, 3, 20, 28} (1, 2, 2)
⟨702, 36⟩ {36, 35, 405
13
, 72
7
; 1, 63
13
, 180
7
, 36} (1, 2, 2)
⟨722, 19⟩ {19, 18, 152
9
, 11; 1, 19
9
, 8, 19} (1, 1, 2) (4.4)
⟨882, 21⟩ {21, 20, 56
3
, 13; 1, 7
3
, 8, 21} (1, 1, 2) (4.4)
⟨990, 66⟩ {66, 65, 847
15
, 88
13
; 1, 143
15
, 770
13
, 66} (1, 2, 2)
⟨1014, 78⟩ {78, 77, 65, 8; 1, 13, 70, 78} (1, 2, 2)
⟨1058, 23⟩ {23, 22, 184
9
, 15; 1, 23
9
, 8, 23} (1, 1, 2) (4.4)
⟨1250, 25⟩ {25, 24, 200
9
, 17; 1, 25
9
, 8, 25} (1, 1, 2) (4.4)
⟨1458, 27⟩ {27, 26, 24, 19; 1, 3, 8, 27} (1, 1, 2) (4.4)
⟨1458, 36⟩ {36, 35, 33, 16; 1, 3, 20, 36} (1, 2, 2)
⟨1482, 38⟩ {38, 37, 12635
351
, 76
37
; 1, 703
351
, 1330
37
, 38} (1, 2, 2)
⟨1674, 45⟩ {45, 44, 1296
31
, 135
11
; 1, 99
31
, 360
11
, 45} (1, 1, 2)
⟨1682, 29⟩ {29, 28, 232
9
, 21; 1, 29
9
, 8, 29} (1, 1, 2) (4.4)
⟨1694, 55⟩ {55, 54, 352
7
, 15; 1, 33
7
, 40, 55} (1, 1, 2)
⟨1862, 21⟩ {21, 20, 364
19
, 81
5
; 1, 35
19
, 24
5
, 21} (1, 1, 2)
⟨2058, 49⟩ {49, 48, 686
15
, 77
5
; 1, 49
15
, 168
5
, 49} (1, 1, 2)
⟨2060, 50⟩ {50, 49, 4800
103
, 110
7
; 1, 350
103
, 240
7
, 50} (1, 1, 2)
⟨2394, 27⟩ {27, 26, 3240
133
, 279
13
; 1, 351
133
, 72
13
, 27} (1, 1, 2)
⟨2466, 36⟩ {36, 35, 4617
137
, 144
7
; 1, 315
137
, 108
7
, 36} (1, 2, 2)
⟨2550, 85⟩ {85, 84, 1156
15
, 187
7
; 1, 119
15
, 408
7
, 85} (1, 1, 2)
⟨2662, 121⟩ {121, 120, 5324
49
, 77
5
; 1, 605
49
, 528
5
, 121} (1, 1, 2)
⟨2706, 66⟩ {66, 65, 2541
41
, 44
3
; 1, 165
41
, 154
3
, 66} (1, 2, 2)
⟨2730, 78⟩ {78, 77, 507
7
, 52
3
; 1, 39
7
, 182
3
, 78} (1, 2, 2)
⟨2750, 25⟩ {25, 24, 250
11
, 185
9
; 1, 25
11
, 40
9
, 25} (1, 1, 2)
⟨2862, 53⟩ {53, 52, 11236
225
, 265
13
; 1, 689
225
, 424
13
, 53} (1, 1, 2)
⟨2890, 153⟩ {153, 152, 136, 9; 1, 17, 144, 153} (1, 1, 2)
⟨2926, 171⟩ {171, 170, 11552
77
, 171
17
; 1, 1615
77
, 2736
17
, 171} (1, 1, 2)
⟨2970, 54⟩ {54, 53, 567
11
, 12; 1, 27
11
, 42, 54} (1, 2, 2)
⟨3042, 65⟩ {65, 64, 182
3
, 25; 1, 13
3
, 40, 65} (1, 1, 2)
⟨3074, 106⟩ {106, 105, 2809
29
, 212
9
; 1, 265
29
, 742
9
, 106} (1, 2, 2)
⟨3174, 184⟩ {184, 183, 161, 16; 1, 23, 168, 184} (1, 2, 2)
⟨3250, 50⟩ {50, 49, 625
13
, 100
9
; 1, 25
13
, 350
9
, 50} (1, 2, 2)
⟨3402, 126⟩ {126, 125, 343
3
, 28; 1, 35
3
, 98, 126} (1, 2, 2)
⟨3498, 77⟩ {77, 76, 3872
53
, 231
19
; 1, 209
53
, 1232
19
, 77} (1, 1, 2)
⟨3610, 133⟩ {133, 132, 608
5
, 21; 1, 57
5
, 112, 133} (1, 1, 2)
⟨3726, 36⟩ {36, 35, 783
23
, 24; 1, 45
23
, 12, 36} (1, 2, 2)
⟨4070, 55⟩ {55, 54, 1936
37
, 77
3
; 1, 99
37
, 88
3
, 55} (1, 1, 2)
⟨4250, 119⟩ {119, 118, 13872
125
, 1309
59
; 1, 1003
125
, 5712
59
, 119} (1, 1, 2)
⟨4370, 190⟩ {190, 189, 3971
23
, 76
7
; 1, 399
23
, 1254
7
, 190} (1, 2, 2)
⟨4410, 210⟩ {210, 209, 189, 12; 1, 21, 198, 210} (1, 2, 2)
⟨4464, 24⟩ {24, 23, 2048
93
, 488
23
; 1, 184
93
, 64
23
, 24} (1, 1, 2)
⟨4526, 73⟩ {73, 72, 10658
155
, 511
15
; 1, 657
155
, 584
15
, 73} (1, 1, 2)
⟨4558, 86⟩ {86, 85, 12943
159
, 1376
51
; 1, 731
159
, 3010
51
, 86} (1, 2, 2)
⟨4590, 75⟩ {75, 74, 1200
17
, 35; 1, 75
17
, 40, 75} (1, 1, 2)
(Continued on next page.)
126 Ars Math. Contemp. 20 (2021) 103–127
(Continued.)
Label Krein array Nonexistence Family
⟨4758, 117⟩ {117, 116, 6760
61
, 273
29
; 1, 377
61
, 3120
29
, 117} (1, 1, 2)
⟨4802, 49⟩ {49, 48, 1176
25
, 25; 1, 49
25
, 24, 49} (1, 1, 2) (4.4)
⟨5046, 261⟩ {261, 260, 232, 21; 1, 29, 240, 261} (1, 1, 2)
⟨5202, 51⟩ {51, 50, 1224
25
, 27; 1, 51
25
, 24, 51} (1, 1, 2) (4.4)
⟨5480, 100⟩ {100, 99, 12800
137
, 140
3
; 1, 900
137
, 160
3
, 100} (1, 1, 2)
⟨5566, 66⟩ {66, 65, 1463
23
, 24; 1, 55
23
, 42, 66} (1, 2, 2)
⟨5590, 78⟩ {78, 77, 3211
43
, 312
11
; 1, 143
43
, 546
11
, 78} (1, 2, 2)
⟨5618, 53⟩ {53, 52, 1272
25
, 29; 1, 53
25
, 24, 53} (1, 1, 2) (4.4)
⟨5618, 106⟩ {106, 105, 901
9
, 36; 1, 53
9
, 70, 106} (1, 2, 2)
⟨5642, 91⟩ {91, 90, 2704
31
, 65
3
; 1, 117
31
, 208
3
, 91} (1, 1, 2)
⟨5670, 105⟩ {105, 104, 98, 49; 1, 7, 56, 105} (1, 1, 2)
⟨5670, 105⟩a {105, 104, 100, 25; 1, 5, 80, 105} (1, 1, 2)
⟨6050, 55⟩ {55, 54, 264
5
, 31; 1, 11
5
, 24, 55} (1, 1, 2) (4.4)
⟨6278, 73⟩ {73, 72, 21316
301
, 365
21
; 1, 657
301
, 1168
21
, 73} (1, 1, 2)
⟨6358, 85⟩ {85, 84, 884
11
, 45; 1, 51
11
, 40, 85} (1, 1, 2)
⟨6422, 91⟩ {91, 90, 1664
19
, 119
5
; 1, 65
19
, 336
5
, 91} (1, 1, 2)
⟨6426, 147⟩ {147, 146, 2352
17
, 35; 1, 147
17
, 112, 147} (1, 1, 2)
⟨6450, 105⟩ {105, 104, 4320
43
, 357
13
; 1, 195
43
, 1008
13
, 105} (1, 1, 2)
⟨6498, 57⟩ {57, 56, 1368
25
, 33; 1, 57
25
, 24, 57} (1, 1, 2) (4.4)
⟨6962, 59⟩ {59, 58, 1416
25
, 35; 1, 59
25
, 24, 59} (1, 1, 2) (4.4)
⟨7210, 103⟩ {103, 102, 84872
875
, 927
17
; 1, 5253
875
, 824
17
, 103} (1, 1, 2)
⟨7442, 61⟩ {61, 60, 1464
25
, 37; 1, 61
25
, 24, 61} (1, 1, 2) (4.4)
⟨7854, 66⟩ {66, 65, 1089
17
, 88
3
; 1, 33
17
, 110
3
, 66} (1, 2, 2)
⟨7878, 78⟩ {78, 77, 7605
101
, 104
3
; 1, 273
101
, 130
3
, 78} (1, 2, 2)
⟨7906, 134⟩ {134, 133, 22445
177
, 2948
57
; 1, 1273
177
, 4690
57
, 134} (1, 2, 2)
⟨7938, 63⟩ {63, 62, 1512
25
, 39; 1, 63
25
, 24, 63} (1, 1, 2) (4.4)
⟨8120, 100⟩ {100, 99, 19200
203
, 620
11
; 1, 1100
203
, 480
11
, 100} (1, 1, 2)
⟨8190, 90⟩ {90, 89, 1125
13
, 40; 1, 45
13
, 50, 90} (1, 2, 2)
⟨8246, 217⟩ {217, 216, 3844
19
, 155
3
; 1, 279
19
, 496
3
, 217} (1, 1, 2)
⟨8450, 65⟩ {65, 64, 312
5
, 41; 1, 13
5
, 24, 65} (1, 1, 2) (4.4)
⟨8450, 78⟩ {78, 77, 377
5
, 36; 1, 13
5
, 42, 78} (1, 2, 2)
⟨8470, 88⟩ {88, 87, 429
5
, 16; 1, 11
5
, 72, 88} (1, 2, 2)
⟨8478, 27⟩ {27, 26, 3888
157
, 327
13
; 1, 351
157
, 24
13
, 27} (1, 1, 2)
⟨8750, 325⟩ {325, 324, 300, 13; 1, 25, 312, 325} (1, 1, 2)
⟨8758, 232⟩ {232, 231, 32799
151
, 464
11
; 1, 2233
151
, 2088
11
, 232} (1, 2, 2)
⟨8798, 106⟩ {106, 105, 8427
83
, 424
9
; 1, 371
83
, 530
9
, 106} (1, 2, 2)
⟨8802, 351⟩ {351, 350, 52488
163
, 351
25
; 1, 4725
163
, 8424
25
, 351} (1, 1, 2)
⟨8978, 67⟩ {67, 66, 1608
25
, 43; 1, 67
25
, 24, 67} (1, 1, 2) (4.4)
⟨9310, 105⟩ {105, 104, 17500
171
, 165
13
; 1, 455
171
, 1200
13
, 105} (1, 1, 2)
⟨9350, 153⟩ {153, 152, 8092
55
, 459
19
; 1, 323
55
, 2448
19
, 153} (1, 1, 2)
⟨9386, 171⟩ {171, 170, 2128
13
, 27; 1, 95
13
, 144, 171} (1, 1, 2)
⟨9522, 69⟩ {69, 68, 1656
25
, 45; 1, 69
25
, 24, 69} (1, 1, 2) (4.4)
⟨9522, 161⟩ {161, 160, 460
3
, 49; 1, 23
3
, 112, 161} (1, 1, 2)
⟨9702, 126⟩ {126, 125, 1323
11
, 56; 1, 63
11
, 70, 126} (1, 2, 2)
Table 2: Nonexistence results for feasible Krein arrays of Q-bipartite (but not Q-antipodal)
4-class Q-polynomial association schemes on up to 10000 vertices. The Nonexistence
column gives either the triple of relation indices for which there is no solution for triple
intersection numbers. The Family column specifies the infinite family from Subsection 4.2
that the parameter set is part of.
A. L. Gavrilyuk et al.: On few-class Q-polynomial association schemes: feasible . . . 127
Label Krein array Family
⟨576, 21⟩ {21, 20, 18, 21
2
, 27
7
; 1, 3, 21
2
, 120
7
, 21}
⟨800, 25⟩ {25, 24, 625
28
, 75
7
, 25
7
; 1, 75
28
, 100
7
, 150
7
, 25} (4.5)
⟨2000, 25⟩ {25, 24, 625
27
, 50
3
, 25
9
; 1, 50
27
, 25
3
, 200
9
, 25}
⟨2400, 22⟩ {22, 21, 20, 88
5
, 32
11
; 1, 2, 22
5
, 210
11
, 22}
⟨2928, 61⟩ {61, 60, 3721
66
, 305
11
, 61
11
; 1, 305
66
, 366
11
, 610
11
, 61} (4.5)
⟨7232, 113⟩ {113, 112, 12769
120
, 791
15
, 113
15
; 1, 791
120
, 904
15
, 1582
15
, 113} (4.5)
⟨14480, 181⟩ {181, 180, 32761
190
, 1629
19
, 181
19
; 1, 1629
190
, 1810
19
, 3258
19
, 181} (4.5)
⟨25440, 265⟩ {265, 264, 70225
276
, 2915
23
, 265
23
; 1, 2915
276
, 3180
23
, 5830
23
, 265} (4.5)
⟨37752, 121⟩ {121, 120, 14641
125
, 484
5
, 121
25
; 1, 484
125
, 121
5
, 2904
25
, 121}
⟨40880, 365⟩ {365, 364, 133225
378
, 4745
27
, 365
27
; 1, 4745
378
, 5110
27
, 9490
27
, 365} (4.5)
⟨47040, 116⟩ {116, 115, 112, 696
7
, 144
29
; 1, 4, 116
7
, 3220
29
, 116}
Table 3: Nonexistence results for feasible Krein arrays of Q-bipartite (but not Q-antipodal)
5-class Q-polynomial association schemes on up to 50000 vertices. In all cases, there is no
solution for triple intersection numbers for a triple of vertices mutually in relation R1. The
Family column specifies the infinite family from Subsection 4.2 that the parameter set is
part of.