\newaliascnt

proposition@alttheorem \newaliascntlemma@alttheorem \newaliascntcorollary@alttheorem \newaliascntquestion@alttheorem \newaliascntdefinition@alttheorem \newaliascntremark@alttheorem \newaliascntconstruction@alttheorem

On an infinite family of generalized PBIBDs

Daniel Kalmanovich Einstein Institute of Mathematics
The Hebrew University of Jerusalem [email protected]

(Date: August 13, 2015)

Abstract.

We consider a generalization of the notion of partially balanced incomplete block designs (PBIBDs), by relaxing the requirement that the underlying association scheme be commutative. An infinite family of such generalizations is constructed, one for each prime power $q$ congruent to $1$ modulo $4$ .

1. Introduction and Preliminaries

Combinatorial designs are fascinating objects which have been studied for centuries, and have origins in diverse areas (cf. the introduction of [5] for a brief historical account). This paper focuses on a particular kind of combinatorial design, originating in the theory of the design of experiments, called partially balanced incomplete block design (PBIBD). Formally introduced by Bose and Nair in [2], a PBIBD is a certain incidence structure together with an underlying symmetric association scheme¹¹1There are longstanding terminology disagreements in this area. In this paper association scheme means homogeneous coherent configuration. which provides many regularity properties to the whole structure. We refer to Bailey’s book [1] which gives a statistician-friendly account of association schemes and their use in the design of experiments.

Association schemes arose naturally in algebraic combinatorics, independent of any applications to statistics, in works pertaining to permutation groups and, independently, to the graph isomorphism problem. We refer to Cameron’s survey [4] for a brief overview of the permutation groups aspect, and the celebrated monograph [3] for the many graph theoretic aspects of association schemes.

Natural generalizations of the notion of a PBIBD were suggested and studied over the years. Among these, notions that take a more general underlying structure by relaxing the various requirements in the definition of an association scheme were introduced and studied in [9] and in [10]. In [7], Nair suggested a generalization of PBIBDs to incidence structures with underlying association schemes which are not necessarily commutative.

In this paper we present a construction of an infinite family of such generalizations of PBIBDs, one for each prime power $q$ congruent to $1$ modulo $4$ . This construction stemmed from the analysis of designs constructed by Nevo in [8].

We assume that the reader is familiar with basics of association scheme theory, but for notational purposes we recall the definitions of an association scheme and a $\mathrm{PBIBD}$ .

Definition \thedefinition@alt.

An association scheme with $m$ associate classes is a finite set $X$ together with $m+1$ binary relations $R_{i}\subseteq X^{2}$ , $0\leq i\leq m$ , such that:

•

$R_{0}=\left\{(x,x)\ \middle|\ x\in X\right\}$ ,
•

for each relation $R_{i}$ , the inverse relation $R_{i}^{-1}=\left\{(y,x)\ \middle|\ (x,y)\in R_{i}\right\}$ is also an associate class,
•

$\bigcup\limits_{i=0}^{d}R_{i}=X^{2}$ , and $R_{i}\cap R_{j}=\emptyset$ whenever $i\neq j$ ,
•

for any pair $(x,z)\in R_{k}$ , the number of elements $y\in X$ such that $(x,y)\in R_{i}$ and $(y,z)\in R_{j}$ depends only on $i,j,k$ . This number is denoted by $p_{ij}^{k}$ .

The numbers in the last item above are called the intersection numbers of the association scheme. We will also use the term $i$ -associates when referring to a pair $(x,y)\in R_{i}$ .

A symmetric association scheme is one in which all the binary relations are symmetric.

Definition \thedefinition@alt.

A partially balanced incomplete block design with $m$ associate classes denoted $\mathrm{PBIBD}(m)$ is a block design $D=(P,B)$ with $|P|=v$ points, $|B|=b$ blocks, where each block has size $k$ , each point lies on $r$ blocks, and such that there is a symmetric association scheme defined on $P$ where, if $(x,y)$ are $j$ -th associates then they occur together in precisely $\lambda_{j}$ blocks for $1\leq j\leq m$ . The numbers $v,b,r,k,\lambda_{j}(1\leq j\leq m)$ are called the parameters of the $\mathrm{PBIBD}(m)$ .

Our definition of a generalized PBIBD is verbatim section 1 dropping the word symmetric. It follows that if $R_{j}$ is the inverse relation of $R_{i}$ then $\lambda_{j}=\lambda_{i}$ .

A special feature of our family of $\mathrm{GPBIBD}$ s is that the number of non-vanishing values of the $\lambda_{j}$ s is constant: we have just the value $5$ when $q=5^{\alpha}$ , and the values $4$ and $1$ when $q$ is not a power of $5$ . Moreover, there is exactly one class for each non-zero value.

2. The construction

Let $q=p^{\alpha}$ be a prime power congruent to $1$ modulo $4$ , and consider the vector space $V={{\mathbbm{F}}_{q}}^{2}$ , where ${\mathbbm{F}}_{q}$ denotes the finite field with $q$ elements. Let $\omega$ be a generator of ${{\mathbbm{F}}_{q}}^{\times}$ , and denote $i=\omega^{\frac{q-1}{4}}$ . Our set of points is $P={\raisebox{1.99997pt}{$V\setminus\{0\}$}\left/\raisebox{-1.99997pt}{$\langle i\rangle$}\right.}$ , that is, we identify the four vectors $\pi$ , $-\pi$ , $i\pi$ and $-i\pi$ , for all non-zero vectors $\pi\in V$ , to obtain the set $P$ of $\frac{q^{2}-1}{4}$ points. Let $G=\operatorname{PSL}(2,q)$ , the quotient group of the matrix group $\operatorname{SL}(2,q)=\left\{\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\ \middle|\ ad-bc=1\right\}$ by its center $Z(\operatorname{SL}(2,q))=\left\{\scriptsize\begin{pmatrix}1&0\\ 0&1\end{pmatrix},\scriptsize\begin{pmatrix}-1&0\\ 0&-1\end{pmatrix}\right\}$ . Each element of $G$ is a set of $2$ matrices, and consider the natural action of $G$ on $P$ via multiplication (of representatives):

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}x\\ y\end{pmatrix}=\scriptsize\begin{pmatrix}ax+by\\ cx+dy\end{pmatrix},

here $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}$ is a representative of the element $\left\{\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix},\scriptsize\begin{pmatrix}-a&-b\\ -c&-d\end{pmatrix}\right\}\in G$ , and $\scriptsize\begin{pmatrix}x\\ y\end{pmatrix}$ is a representative of the element $\left\{\scriptsize\begin{pmatrix}x\\ y\end{pmatrix},\scriptsize\begin{pmatrix}-x\\ -y\end{pmatrix},\scriptsize\begin{pmatrix}ix\\ iy\end{pmatrix},\scriptsize\begin{pmatrix}-ix\\ -iy\end{pmatrix}\right\}\in P$ . Define

T=\left\{\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix},\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}1\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}1+i\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}i\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}\right\},

and denote $B=T^{G}$ , the orbit of $T$ under the natural action of $G$ (the induced action on $6$ -sets). We have thus defined an incidence structure $D=(P,B)$ on which $G$ acts transitively both on the points and on the blocks. In fact, if we analyse the action of $G$ on pairs of points $P$ we can give a geometric interpretation to the basic block $T$ , and thus to all blocks of $B$ . Consider the points of $T$ as the vertices of a regular octahedron, with edges as depicted in the following figure:

Figure 1. The basic octahedron

T

With this description at hand we will freely switch between the terms block and octahedron when we refer to elements of $B$ . Also, we will use the terms edges and diagonals for pairs of points of $D$ which form an edge in an octahedron, and pairs of points of $D$ which form a diagonal in an octahedron (a pair of antipodal points), respectively. Of course, any other pair of points do not lie in a block together.

Lemma \thelemma@alt.

(1)

$G$ acts transitively on the edges of $D$ .
(2)

$G$ acts transitively on the diagonals of $D$ .

Let us denote by ${\mathcal{S}}$ the Schurian association scheme of the action of $G$ on $P$ . Then we have

Corollary \thecorollary@alt.

The block design $D=(P,B)$ is a $\mathrm{GPBIBD}$ with underlying association scheme ${\mathcal{S}}$ .

Lemma \thelemma@alt.

The stabilizer $G_{\pi}$ of a point $\pi\in P$ in $G$ is isomorphic to ${C_{p}}^{\alpha}\rtimes C_{2}$ , where $q=p^{\alpha}$ .

Proof.

Since $G$ acts transitively on $P$ it suffices to consider the stabilizer $G_{\binom{1}{0}}$ of $\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}$ . So let $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\in G_{\binom{1}{0}}$ , that is

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}=\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}.

It follows that $a=1$ or $i$ , and $c=0$ , thus

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}1&b\\ 0&d\end{pmatrix}\quad\text{or}\quad\scriptsize\begin{pmatrix}i&b\\ 0&d\end{pmatrix}

the determinant $=1$ condition implies that $d=1$ in the first case, and $d=-i$ in the second case, so we have

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}1&b\\ 0&1\end{pmatrix}\quad\text{or}\quad\scriptsize\begin{pmatrix}i&b\\ 0&-i\end{pmatrix}.

Therefore

G_{\binom{1}{0}}=\left\{\scriptsize\begin{pmatrix}u&x\\ 0&u^{-1}\end{pmatrix}\ \middle|\ u\in\{1,i\},x\in{\mathbbm{F}}_{q}\right\}.

∎

The cases $q=5^{\alpha}$ and $q=p^{\alpha}$ , $p\neq 5$ are different in an essential way, so we analyse them separately. The reason for the difference between the case of characteristic $5$ and other characteristics is the fact that in the case of characteristic $5$ , the subgroup $\{1,-1,i,-i\}$ forms the multiplicative group of the prime subfield ${\mathbbm{F}}_{5}$ (and not just a subgroup of the multiplicative group of the field). A manifestation of this fact that will be useful for our purposes later is formulated in the following lemma.

Lemma \thelemma@alt.

$1+i=-i$ if and only if $q=5^{\alpha}$ .

Proof.

1+i=-i\qquad\Longleftrightarrow\qquad 2i=-1\qquad\Longleftrightarrow\qquad 2i=i^{2}\qquad\Longleftrightarrow\qquad i=2

so we have $-1=i^{2}=2^{2}=4$ , that is, ${\mathbbm{F}}_{q}$ is a field of characteristic $5$ . ∎

The case $p\neq 5$

In this case the stabilizer $G_{T}$ of the basic block $T$ in $G$ is a group of rotations of the regular octahedron. It is in fact half of the full group of rotations of the regular octahedron. There are two types of rotations of a regular octahedron:

(a)

rotation about the axis defined by a pair of antipodal points, and
(b)

rotation about the axis formed by connecting the centers of a pair of opposite faces.

In the full group of rotations of the octahedron, the rotations of type (a) are of order $4$ , and the rotations of type (b) are of order $3$ thus producing a group of order $24$ . In our group $G_{T}$ we take the square of rotations of type (a) and all rotations of type (b), obtaining a group of order $12$ . In this description $G_{T}=\langle g,f\rangle$ where

•

$g=\scriptsize\begin{pmatrix}-i&-1+i\\ 0&i\end{pmatrix}$ is the $180^{\circ}$ rotation around the axis defined by the antipodal points $\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}$ and $\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}$ , and
•

$f=\scriptsize\begin{pmatrix}i&1\\ i&1-i\end{pmatrix}$ is the rotation around the axis formed by connecting the centers of the opposite faces $\left\{\scriptsize\begin{pmatrix}1\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}1+i\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}\right\}$ and $\left\{\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix},\scriptsize\begin{pmatrix}i\\ 1\end{pmatrix}\right\}$ .

Lemma \thelemma@alt.

The stabilizer $G_{\beta}$ of a block $\beta\in B$ in $G$ is isomorphic to the alternating group $A_{4}$ .

Proof.

First, since $G$ acts transitively on the block set $B$ it is enough to consider $G_{T}$ , the stabilizer of the basic block $T$ . In fact, we will explicitly write representatives for the elements of $G_{T}$ . We will first show that $|G_{T}|=12$ , and then one can verify that

\left\{{\scriptsize\begin{aligned} &\begin{pmatrix}1&0\\ 0&1\\ \end{pmatrix},\begin{pmatrix}0&-i\\ -i&-1\\ \end{pmatrix},\begin{pmatrix}-1&i\\ i&0\\ \end{pmatrix},\begin{pmatrix}-i&0\\ -1-i&i\\ \end{pmatrix},\begin{pmatrix}-1+i&1\\ i&-i\\ \end{pmatrix},\begin{pmatrix}1&-1\\ 1&0\\ \end{pmatrix},\\ &\begin{pmatrix}1&-1-i\\ 1-i&-1\\ \end{pmatrix},\begin{pmatrix}-1-i&i\\ -1&i\\ \end{pmatrix},\begin{pmatrix}i&1\\ i&1-i\\ \end{pmatrix},\begin{pmatrix}-i&-1+i\\ 0&i\\ \end{pmatrix},\begin{pmatrix}0&1\\ -1&1\\ \end{pmatrix},\begin{pmatrix}i&-i\\ 1&-1-i\\ \end{pmatrix}\end{aligned}}\right\}

is a set of $12$ representatives of distinct elements of $G_{T}$ . We use the orbit-stabilizer theorem:

\left|G_{T}\right|=\left|{G_{T}}_{\binom{1}{0}}\right|\cdot\left|\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}^{G_{T}}\right|.

One can check directly that the elements in the above list leave $T$ fixed, and that there are elements in that list that take $\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}$ to each of the points in $T$ , so $\left|\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}^{G_{T}}\right|=6$ . To compute ${G_{T}}_{\binom{1}{0}}=G_{T}\cap G_{\binom{1}{0}}$ we recall that by section 2

G_{\binom{1}{0}}=\left\{\scriptsize\begin{pmatrix}u&x\\ 0&u^{-1}\end{pmatrix}\ \middle|\ u\in\{1,i\},x\in{\mathbbm{F}}_{q}\right\},

now it is enough to show that the only elements in $G_{\binom{1}{0}}$ that fix $T$ are $\scriptsize\begin{pmatrix}1&0\\ 0&1\end{pmatrix}$ and $\scriptsize\begin{pmatrix}i&1-i\\ 0&-i\end{pmatrix}$ . So let $\scriptsize\begin{pmatrix}u&x\\ 0&u^{-1}\end{pmatrix}$ be an element that stabilizes $T$ , since $p\neq 5$ it follows from section 2 that $\scriptsize\begin{pmatrix}u&x\\ 0&u^{-1}\end{pmatrix}\cdot\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}=\scriptsize\begin{pmatrix}x\\ u^{-1}\end{pmatrix}$ is either $\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}$ , $\scriptsize\begin{pmatrix}i\\ 1\end{pmatrix}$ , $\scriptsize\begin{pmatrix}1\\ 1\end{pmatrix}$ or $\scriptsize\begin{pmatrix}1+i\\ 1\end{pmatrix}$ . Each of the above four cases gives $2$ options for $\scriptsize\begin{pmatrix}u&x\\ 0&u^{-1}\end{pmatrix}$ , and out of these eight options the only elements that indeed fix $T$ are $\scriptsize\begin{pmatrix}1&0\\ 0&1\end{pmatrix}$ and $\scriptsize\begin{pmatrix}i&1-i\\ 0&-i\end{pmatrix}$ , so $\left|{G_{T}}_{\binom{1}{0}}\right|=2$ and $\left|G_{T}\right|=2\cdot 6=12$ . The isomorphism $G_{T}\cong A_{4}$ can now be deduced by noticing that $G_{T}$ has no element of order $6$ , and the only non-abelian group of order $12$ which has no elements of order $6$ is the alternating group $A_{4}$ . ∎

Lemma \thelemma@alt.

(a)

The group $G$ acts transitively on the edges of $D$ .
(b)

Every edge of $D$ is contained in $4$ ocathedra.

Proof.

(a)

Since $G$ acts transitively on the octahedra, it suffices to show that $G_{T}$ acts transitively on the $12$ edges of $T$ . This will follow from the orbit-stabilizer theorem once we show that stabilizer ${G_{T}}_{e}$ of the edge $e=\left\{\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix},\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}\right\}$ (in $G_{T}$ ) is trivial. So let $g\in{G_{T}}_{e}$ , first we will show that $g$ must fix both vertices $\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}$ and $\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}$ . Write $g=\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}$ , and assume that

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}=\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}\quad\text{and}\quad\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}=\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}

then from the first equality it follows that $a=0$ and $c=1,i,-1$ or $-i$ , from the second equality if follows that $d=0$ and $b=1,i,-1$ or $-i$ , and by the determinant $=1$ condition we have

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}0&-1\\ 1&0\end{pmatrix}\quad\text{or}\quad\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}0&i\\ i&0\end{pmatrix}.

Both elements above are not in $G_{T}$ , thus $g$ must fix each of the vertices of $e$ . It follows that $g\in{G_{T}}_{\binom{1}{0}}$ , thus $g=\scriptsize\begin{pmatrix}1&0\\ 0&1\end{pmatrix}$ or $g=\scriptsize\begin{pmatrix}-i&-1+i\\ 0&i\end{pmatrix}$ , but $\scriptsize\begin{pmatrix}-i&-1+i\\ 0&i\end{pmatrix}$ does not fix $\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}$ so we must have $g=\scriptsize\begin{pmatrix}1&0\\ 0&1\end{pmatrix}$ and so ${G_{T}}_{e}$ is trivial.

(b)
From the calculation in the proof of $(a)$ it follows that

$G_{e}=\left\langle\scriptsize\begin{pmatrix}0&-1\\ 1&0\end{pmatrix},\scriptsize\begin{pmatrix}0&i\\ i&0\end{pmatrix}\right\rangle$

thus $\left|G_{e}\right|=4$ . Using the orbit-stabilizer theorem we can now compute the total number of edges of $D$ , that is, the size of the orbit of $e$ under the action of $G$ :

$\left|e^{G}\right|=\frac{\left|G\right|}{\left|G_{e}\right|}=\frac{\frac{q(q^{2}-1)}{2}}{4}=\frac{q(q^{2}-1)}{8}.$

Let $E$ denote the set of edges of $D$ . Now we apply a standard double-counting argument, we count the size of the set

$S=\left\{(\epsilon,\beta)\ \middle|\ \epsilon\in E,\beta\in B,\epsilon\text{ is an edge of }\beta\right\}$

in two ways:
- •
  
  $\left|S\right|=12\cdot\left|B\right|$ because every block has $12$ edges, and
- •
  
  $\left|S\right|=\left|E\right|\cdot x$ , where $x$ is the number of blocks that contain a given edge.
Therefore, we have

$x=\frac{12\cdot\left|B\right|}{\left|E\right|}=\frac{12\cdot\frac{q(q^{2}-1)}{24}}{\frac{q(q^{2}-1)}{8}}=4.$

∎

Lemma \thelemma@alt.

(a)

The group $G$ acts transitively on the diagonals of $D$ .
(b)

Every diagonal of $D$ is contained in $1$ ocathedron.

Proof.

(a)

As in the previous proofs, since $G$ acts transitively on the octahedra, it suffices to show that $G_{T}$ acts transitively on the $3$ diagonals of $T$ . To see that, it is enough to consider just the rotation $f$ :

\left\{\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix},\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}\right\}\overset{f}{\mapsto}\left\{\scriptsize\begin{pmatrix}1\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}i\\ 1\end{pmatrix}\right\}\overset{f}{\mapsto}\left\{\scriptsize\begin{pmatrix}1+i\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}\right\}.

(b)

The following arguments are similar to those given in the proof of The case $p\neq 5$ , we will compute the stabilizer $G_{d}$ of the diagonal $d=\left\{\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix},\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}\right\}$ in order to obtain the total number of diagonals in $D$ via the orbit-stabilizer theorem, and then use a double-counting argument to compute the number of octahedra that contain a given diagonal. So let $g=\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\in G_{d}$ , then we have either

(I)\quad\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}=\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}\quad\text{and}\quad\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}=\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}

(II)\quad\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}=\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}\quad\text{and}\quad\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}\cdot\scriptsize\begin{pmatrix}1\\ 1-i\end{pmatrix}=\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}.

In case $(I)$ , the first equality implies $a=1$ or $i$ , and $c=0$ , thus $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}1&b\\ 0&1\end{pmatrix}$ or $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}i&b\\ 0&-i\end{pmatrix}$ , plugging this into the second equation we get $b=0$ in the first case and $b=1-i$ in the second case, so

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}1&0\\ 0&1\end{pmatrix}\text{ or }\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}i&1-i\\ 0&-i\end{pmatrix}.

In case $(II)$ , the first equality implies $a=1$ or $i$ , and $c=1-i$ or $1+i$ (respectively), thus $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}1&b\\ 1-i&d\end{pmatrix}$ or $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}i&b\\ 1+i&d\end{pmatrix}$ , plugging this into the second equation we get $d=-1$ in the first case, and $d=-i$ in the second, so $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}1&b\\ 1-i&-1\end{pmatrix}$ or $\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}i&b\\ 1+i&-i\end{pmatrix}$ , now the determinant $=1$ condition determines $b$ and we get

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}1&-1-i\\ 1-i&-1\end{pmatrix}\text{ or }\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}=\scriptsize\begin{pmatrix}i&0\\ 1+i&-i\end{pmatrix}.

It is now easy to check that the four representative matrices we found form a group, thus $\left|G_{d}\right|=4$ . Again, the orbit-stabilizer theorem allows us to compute the total number of diagonals of $D$ , that is, the size of the orbit of $d$ under the action of $G$ :

\left|d^{G}\right|=\frac{\left|G\right|}{\left|G_{d}\right|}=\frac{\frac{q(q^{2}-1)}{2}}{4}=\frac{q(q^{2}-1)}{8}.

Let $\Delta$ denote the set of diagonals of $D$ . Yet again we apply a double-counting argument, we count the size of the set

S=\left\{(\delta,\beta)\ \middle|\ \delta\in\Delta,\beta\in B,\delta\text{ is a diagonal of }\beta\right\}

in two ways:

•

$\left|S\right|=3\cdot\left|B\right|$ because every block has $3$ diagonals, and
•

$\left|S\right|=\left|\Delta\right|\cdot x$ , where $x$ is the number of blocks that contain a given diagonal.

Therefore, we have

x=\frac{3\cdot\left|B\right|}{\left|\Delta\right|}=\frac{3\cdot\frac{q(q^{2}-1)}{24}}{\frac{q(q^{2}-1)}{8}}=1.

∎

Theorem 1.

The block design $D$ is a $\mathrm{GPBIBD}(m)$ with parameters

v=\frac{q^{2}-1}{4},\quad b=\frac{q(q^{2}-1)}{24},\quad k=6,\quad r=q,\quad\lambda_{1}=4,\quad\lambda_{2}=1,\quad\lambda_{3}=\dots=\lambda_{m}=0.

The underlying association scheme is the Schurian scheme ${\mathcal{S}}(G,P)$ of $(G,P)$ , and the number of associate classes is

m=\frac{q-3}{2}.

Proof.

The number of points is clear from the construction. The number of blocks can be calculated by using the orbit-stabilizer theorem and the fact that, by The case $p\neq 5$ , $\left|G_{T}\right|=12$ :

b=\left|B\right|=\left|T^{G}\right|=\frac{\left|G\right|}{\left|G_{T}\right|}=\frac{\frac{q(q^{2}-1)}{2}}{12}=\frac{q(q^{2}-1)}{24}.

The fact that each block has size $k=6$ follows from the fact that the basic block $T$ has size $6$ , and that the set of blocks is the orbit $T^{G}$ of $T$ under the action of $G$ . To prove that each point lies on $r=q$ blocks it suffices to show that $\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}$ lies on $q$ blocks, because $G$ acts transitively on $P$ . For that purpose we will show that $\left|T^{G_{\binom{1}{0}}}\right|=q$ . Again, the orbit-stabilizer theorem applied to $G_{\binom{1}{0}}$ will do the job:

2q=\left|G_{\binom{1}{0}}\right|=\left|{G_{\binom{1}{0}}}_{T}\right|\cdot\left|T^{G_{\binom{1}{0}}}\right|=2\cdot\left|T^{G_{\binom{1}{0}}}\right|,

thus $\left|T^{G_{\binom{1}{0}}}\right|=q$ . A pair of points of $P$ is either an edge of $D$ , a diagonal of $D$ or neither (that is a pair that does not lie in a block together), it follows from The case $p\neq 5$ that an edge lies on $\lambda_{1}=4$ blocks, from The case $p\neq 5$ that a diagonal lies on $\lambda_{2}=1$ block, and any other pair lies on $\lambda_{j}=0$ ( $3\leq j\leq m$ ) blocks. Next, the fact that the Schurian scheme of the action $(G,P)$ is the underlying association scheme follows from the fact that $G$ acts transitively on the edges of $D$ (proved in The case $p\neq 5$ ), and on the diagonals of $D$ (proved in The case $p\neq 5$ ).

Finally, we compute the number of associate classes, that is, the number of classes of ${\mathcal{S}}(G,P)$ , or in other words, the rank of the transitive permutation group $(G,P)$ minus $1$ . The rank of a transitive permutation group is equal to number of orbits of the stabilizer of a point, so we compute the number of orbits of $\left(G_{\binom{1}{0}},P\right)$ . Recall that

G_{\binom{1}{0}}=\left\{\scriptsize\begin{pmatrix}u&x\\ 0&u^{-1}\end{pmatrix}\ \middle|\ u\in\{1,i\},x\in{\mathbbm{F}}_{q}\right\},

so for each point of the form $\scriptsize\begin{pmatrix}a\\ 0\end{pmatrix}\in P$ we have $\scriptsize\begin{pmatrix}a\\ 0\end{pmatrix}^{G_{\binom{1}{0}}}=\left\{\scriptsize\begin{pmatrix}a\\ 0\end{pmatrix}\right\}$ , these are $\frac{q-1}{4}$ orbits. For points of the form $\scriptsize\begin{pmatrix}a\\ b\end{pmatrix}\in P$ , with $b\neq 0$ , we have

\scriptsize\begin{pmatrix}a\\ b\end{pmatrix}^{G_{\binom{1}{0}}}=\left\{\scriptsize\begin{pmatrix}y\\ b\end{pmatrix}\ \middle|\ y\in{\mathbbm{F}}_{q}\right\},

because $\scriptsize\begin{pmatrix}1&\frac{y-a}{b}\\ 0&1\end{pmatrix}$ takes $\scriptsize\begin{pmatrix}a\\ b\end{pmatrix}$ to $\scriptsize\begin{pmatrix}y\\ b\end{pmatrix}$ , so we get $\frac{q-1}{4}$ more orbits. Altogether we counted the $\frac{q-1}{2}$ orbits of $G_{\binom{1}{0}}$ , thus the number of associate classes is $m=\frac{q-3}{2}$ . ∎

The case $p=5$

Let $q=5^{\alpha}$ . In this case the basic block $T$ is in fact just the projective line over ${\mathbbm{F}}_{5}$ , and we have

Lemma \thelemma@alt.

The stabilizer $G_{\beta}$ of a block $\beta\in B$ in $G$ is isomorphic to $\operatorname{PSL}(2,5)$ .

Proof.

As before, by the transitive action of $G$ on $B$ it is enough to consider $G_{T}$ . By section 2, since $q=5^{\alpha}$ , we have that $1+i=-i$ . It follows that $1-i=-1$ and thus we have

T=\left\{\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix},\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}1\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}-i\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}i\\ 1\end{pmatrix},\scriptsize\begin{pmatrix}-1\\ 1\end{pmatrix}\right\},

that is, $T$ is the projective line over ${\mathbbm{F}}_{5}$ , and it follows that subgroup of $\operatorname{PSL}(2,q)$ that fixes the projective line over ${\mathbbm{F}}_{5}$ is $\operatorname{PSL}(2,5)$ . ∎

Corollary \thecorollary@alt.

$G$ acts transitively on pairs of points that lie together in a block.

We will refer to pairs of points that lie together on a block adjacent points, and correspondingly to pairs of points that do not lie together on a block as non-adjacent points.

Theorem 2.

The block design $D$ is a $\mathrm{GPBIBD}(m)$ with parameters

v=\frac{q^{2}-1}{4},\quad b=\frac{q(q^{2}-1)}{120},\quad k=6,\quad r=\frac{q}{5}=5^{\alpha-1},\quad\lambda_{1}=1,\quad\lambda_{2}=\dots=\lambda_{m}=0.

The underlying association scheme is the Schurian scheme ${\mathcal{S}}(G,P)$ of $(G,P)$ , and the number of associate classes is

m=\frac{q-3}{2}.

Proof.

The number of points is clear from the construction. The number of blocks can be calculated by using the orbit-stabilizer theorem and the fact that, by The case $p=5$ , $\left|G_{T}\right|=60$ :

b=\left|B\right|=\left|T^{G}\right|=\frac{\left|G\right|}{\left|G_{T}\right|}=\frac{\frac{q(q^{2}-1)}{2}}{60}=\frac{q(q^{2}-1)}{120}.

The fact that each block has size $k=6$ follows from the fact that the basic block $T$ has size $6$ , and that the set of blocks is the orbit $T^{G}$ of $T$ under the action of $G$ . To prove that each point lies on $r=\frac{q}{5}=5^{\alpha-1}$ blocks it suffices to show that $\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix}$ lies on $5^{\alpha-1}$ blocks, because $G$ acts transitively on $P$ . For that purpose we will show that $\left|T^{G_{\binom{1}{0}}}\right|=5^{\alpha-1}$ . Again, the orbit-stabilizer theorem applied to $G_{\binom{1}{0}}$ will do the job:

2q=\left|G_{\binom{1}{0}}\right|=\left|{G_{\binom{1}{0}}}_{T}\right|\cdot\left|T^{G_{\binom{1}{0}}}\right|.

By The case $p=5$ we have

{G_{\binom{1}{0}}}_{T}=G_{T}\cap G_{\binom{1}{0}}=\operatorname{PSL}(2,5)\cap G_{\binom{1}{0}},

that is, ${G_{\binom{1}{0}}}_{T}=\left\{\scriptsize\begin{pmatrix}u&x\\ 0&u^{-1}\end{pmatrix}\ \middle|\ u\in\{1,i\},x\in{\mathbbm{F}}_{5}\right\}$ and $\left|{G_{\binom{1}{0}}}_{T}\right|=10$ , thus $2q=10\cdot\left|T^{G_{\binom{1}{0}}}\right|$ and therefore $\left|T^{G_{\binom{1}{0}}}\right|=\frac{2q}{10}=\frac{2\cdot 5^{\alpha}}{2\cdot 5}=5^{\alpha-1}$ . The number of pairs of adjacent points is

\binom{6}{2}\cdot\left|B\right|=15\cdot\frac{q(q^{2}-1)}{120}=\frac{q(q^{2}-1)}{8}.

To show that each pair of adjacent points determines a unique block it is enough to show that the stabilizer of a pair of adjacent points stabilizes that whole block. So by The case $p=5$ we may assume that $e=\left\{\scriptsize\begin{pmatrix}1\\ 0\end{pmatrix},\scriptsize\begin{pmatrix}0\\ 1\end{pmatrix}\right\}$ is our pair of adjacent points on the block $T$ . We need to show that $G_{e}\leq G_{T}$ . Recall that the calculation in The case $p\neq 5$ showed that

G_{e}=\left\langle\scriptsize\begin{pmatrix}0&-1\\ 1&0\end{pmatrix},\scriptsize\begin{pmatrix}0&i\\ i&0\end{pmatrix}\right\rangle,

in this case, clearly $G_{e}\leq\operatorname{PSL}(2,5)=G_{T}$ . Finally, the fact that the Schurian scheme of the action $(G,P)$ is the underlying association scheme follows from the fact that $G$ acts transitively on the pairs of adjacent points $D$ (stated in The case $p=5$ ), the computation of the number of associate classes is identical to that given in Theorem 1. ∎

At this point it seems interesting to ask:

Question \thequestion@alt.

Can we find an underlying association scheme for $D$ with less vanishing classes?

The following two sections deal with this question. In section 3 we find the largest (in a certain natural sense) group acting on $D$ producing an underlying Schurian association scheme with less vanishing classes. In section 4 we compute the underlying association scheme with the smallest possible number of vanishing classes for all $\mathrm{GPBIBD}$ s with $q\leq 169$ , and propose a general conjecture about the minimal association schemes.

3. A smaller rank underlying association scheme

In this section we prove that in fact we have a larger group acting on $D$ . Let $\phi$ be the Frobenius automorphism of ${\mathbbm{F}}_{q}$ , that is, the map that takes each element $a\in{\mathbbm{F}}_{q}$ to its $p$ -th power $a^{p}\in{\mathbbm{F}}_{q}$ . We denote by $F=\langle\phi\rangle$ the automorphism group $\operatorname{Aut}({\mathbbm{F}}_{q})$ . The projective special semilinear group, commonly denoted by $\operatorname{P\Sigma L}(2,q)$ , is the semidirect product $\operatorname{PSL}(2,q)\rtimes F$ , where the cyclic group $F$ is acting on $\operatorname{PSL}(2,q)$ in the natural way:

\scriptsize\begin{pmatrix}a&b\\ c&d\end{pmatrix}^{\phi}=\scriptsize\begin{pmatrix}a^{p}&b^{p}\\ c^{p}&d^{p}\end{pmatrix}.

Theorem 3.

The largest automorphism group ${\mathcal{G}}$ of $D$ that preserves the octahedral structure is isomorphic to $\operatorname{P\Sigma L}(2,q)\times C_{2}$ .

Proof.

Clearly $\operatorname{P\Sigma L}(2,q)$ acts on $D$ . The additional involution $C_{2}=\langle\sigma\rangle$ is the missing $90^{\circ}$ rotation about the axis formed by two antipodal vertices of the octahedron. ∎

Computing the number of orbits of $F$ on $P$

We use Burnside’s lemma and standard Galois cohomology tools to compute the number of orbits ${\raisebox{1.99997pt}{$P$}\left/\raisebox{-1.99997pt}{$F$}\right.}$ of $F$ on $P={\raisebox{1.99997pt}{${{\mathbbm{F}}_{q}}^{\times}$}\left/\raisebox{-1.99997pt}{$\mu_{4}$}\right.}$ and $q=p^{n}$ . As usual we denote by $P^{g}$ the fixed points of $P$ under the action of $g$ . Burnside’s lemma establishes that

\left|{\raisebox{1.99997pt}{$P$}\left/\raisebox{-1.99997pt}{$F$}\right.}\right|=\frac{1}{|F|}\sum_{g\in F}\left|P^{g}\right|.

For each divisor $d$ of $n$ we have a subfield ${\mathbbm{F}}_{p^{d}}$ of ${\mathbbm{F}}_{p^{n}}$ , the elements of ${\mathbbm{F}}_{p^{d}}$ are precisely the fixed points of $\phi^{d}$ . Moreover, if $k$ is a multiple of $d$ that does not divide $n$ then the fixed points of $\phi^{k}$ are again the elements of ${\mathbbm{F}}_{p^{d}}$ , thus we can rewrite the above sum as follows:

\left|{\raisebox{1.99997pt}{$P$}\left/\raisebox{-1.99997pt}{$F$}\right.}\right|=\frac{1}{|F|}\sum_{g\in F}\left|P^{g}\right|=\frac{1}{|F|}\sum_{d|n}\varphi\left(\frac{n}{d}\right)\left|P^{\phi^{d}}\right|

where $\varphi$ is Euler totient function. To compute $\left|P^{\phi^{d}}\right|$ we use Galois cohomology. For clearer notation we denote $K:=\phi^{d}$ . The short exact sequence

1\longrightarrow\mu_{4}\longrightarrow{{\mathbbm{F}}_{q}}^{\times}\longrightarrow{\raisebox{1.99997pt}{${{\mathbbm{F}}_{q}}^{\times}$}\left/\raisebox{-1.99997pt}{$\mu_{4}$}\right.}\longrightarrow 1

provides a long exact sequence in group cohomology

1\longrightarrow{\mu_{4}}^{K}\longrightarrow\left({{\mathbbm{F}}_{q}}^{\times}\right)^{K}\longrightarrow\left({\raisebox{1.99997pt}{${{\mathbbm{F}}_{q}}^{\times}$}\left/\raisebox{-1.99997pt}{$\mu_{4}$}\right.}\right)^{K}\longrightarrow H^{1}(K,\mu_{4})\longrightarrow H^{1}(K,{{\mathbbm{F}}_{q}}^{\times})\longrightarrow\dots

By Hilbert’s Theorem 90 we have

H^{1}(K,{{\mathbbm{F}}_{q}}^{\times})=1

so we get the following exact sequence

1\longrightarrow{\mu_{4}}^{K}\longrightarrow\left({{\mathbbm{F}}_{q}}^{\times}\right)^{K}\longrightarrow\left({\raisebox{1.99997pt}{${{\mathbbm{F}}_{q}}^{\times}$}\left/\raisebox{-1.99997pt}{$\mu_{4}$}\right.}\right)^{K}\longrightarrow H^{1}(K,\mu_{4})\longrightarrow 1

and we are interested in

\left|\left({\raisebox{1.99997pt}{${{\mathbbm{F}}_{q}}^{\times}$}\left/\raisebox{-1.99997pt}{$\mu_{4}$}\right.}\right)^{K}\right|=\frac{\left|H^{1}(K,\mu_{4})\right|\cdot\left|\left({{\mathbbm{F}}_{q}}^{\times}\right)^{K}\right|}{\left|{\mu_{4}}^{K}\right|}.

Clearly, we have $\left|\left({{\mathbbm{F}}_{q}}^{\times}\right)^{K}\right|=p^{d}-1$ . We deal with cases $p\equiv 1\pmod{4}$ and $p\equiv 3\pmod{4}$ separately.

The case $p\equiv 1\pmod{4}$

In this case $\mu_{4}$ is already contained in ${\mathbbm{F}}_{p}$ and thus is fixed by $K$ so $\left|{\mu_{4}}^{K}\right|=4$ and we have

\left|\left({\raisebox{1.99997pt}{${{\mathbbm{F}}_{q}}^{\times}$}\left/\raisebox{-1.99997pt}{$\mu_{4}$}\right.}\right)^{K}\right|=\left|H^{1}(K,\mu_{4})\right|\cdot\frac{p^{d}-1}{4}.

Now, since $\mu_{4}$ is a trivial $K$ -module we have

H^{1}(K,\mu_{4})=\operatorname{Hom}(K,\mu_{4})\cong\begin{cases}C_{4}&|K|\equiv 0\pmod{4}\\ C_{2}&|K|\equiv 2\pmod{4}\\ 1&\text{otherwise}\end{cases}

so if we denote $h(d):=|H^{1}(K,\mu_{4})|$ (this number depends on the residue of $\frac{n}{d}$ modulo $4$ ) we have

\left|{\raisebox{1.99997pt}{$P$}\left/\raisebox{-1.99997pt}{$F$}\right.}\right|=\frac{1}{\left|F\right|}\sum_{d|n}\varphi\left(\frac{n}{d}\right)\cdot h(d)\cdot\frac{p^{d}-1}{4}.

The case $p\equiv 3\pmod{4}$

In this case $\mu_{4}$ is contained in ${\mathbbm{F}}_{p^{2}}$ but not in ${\mathbbm{F}}_{P}$ so for every odd power of $\phi$ there are just $2$ fixed points, and for every even power of $\phi$ there are $4$ fixed points, that is:

\left|{\mu_{4}}^{K}\right|=\begin{cases}2&d\text{ odd}\\ 4&d\text{ even}\end{cases}.

The computation of $\left|H^{1}(K,\mu_{4})\right|$ in this case is a bit more involved. If $\frac{n}{d}$ is even then $\mu_{4}$ is again a trivial $K$ -module and we have

H^{1}(K,\mu_{4})=\operatorname{Hom}(K,\mu_{4})\cong\begin{cases}C_{4}&|K|\equiv 0\pmod{4}\\ C_{2}&|K|\equiv 2\pmod{4}\\ \end{cases}.

For $d$ odd, $\mu_{4}$ is no longer a trivial $K$ -module. There are two cyclic groups here, and an action of one of them on the other, considered as a module, so we will use additive notation for $\mu_{4}$ (that is, the group of integers modulo $4$ ), and write $a\cdot m$ to denote the action of $a$ on $m$ , where $a\in K$ and $m\in\mu_{4}$ , the operation in $K$ will be denoted simply $ab$ for $a,b\in K$ . Fix a generator $\alpha$ of $K$ , the the action of $K$ on $\mu_{4}$ is

\alpha\cdot 0=0,\quad\alpha\cdot 1=3,\quad\alpha\cdot 2=2,\quad\alpha\cdot 3=1.

The $1$ -cocycles $Z^{1}(K,\mu_{4})$ are thus the functions $f:K\longrightarrow\mu_{4}$ satisfying

f(ab)=f(a)+a\cdot f(b)

and the $1$ -coboundaries $B^{1}(K,\mu_{4})$ are those satisfying

f(a)=a\cdot m-m\qquad\text{for some}\quad m\in\mu_{4}.

A $1$ -cocycle is determined by its value on $\alpha$ . So let $f\in B^{1}(K,\mu_{4})$ , one can verify that out of the $4$ options (one option for each $m\in\mu_{4}$ ) there are just $2$ elements in $B^{1}(K,\mu_{4})$ , explicitly, these are the functions

f(\alpha)=\alpha\cdot 0-0\quad\text{and}\quad f(\alpha)=\alpha\cdot 1-1.

Consider now $Z^{1}(K,\mu_{4})$ . Let $f\in Z^{1}(K,\mu_{4})$ then out of the $4$ options

f(\alpha)=0,\quad f(\alpha)=1,\quad f(\alpha)=2,\quad f(\alpha)=3,

it is easy to verify that $f(\alpha)=0$ and $f(\alpha)=2$ are both in $B^{1}(K,\mu_{4})$ . Also, $f(\alpha)=1$ and $f(\alpha)=3$ are cohomologous (their difference is in $B^{1}(K,\mu_{4})$ ), so altogether we get

H^{1}(K,\mu_{4})={\raisebox{1.99997pt}{$Z^{1}(K,\mu_{4})$}\left/\raisebox{-1.99997pt}{$B^{1}(K,\mu_{4})$}\right.}\cong C_{2}.

Denote $h(d):=\frac{\left|H^{1}(K,\mu_{4})\right|}{\left|{\mu_{4}}^{K}\right|}$ summarizing the above we have

h(d)=\begin{cases}1&\text{$d$ odd; or $d$ even and $\frac{n}{d}\equiv 0\pmod{4}$}\\ \frac{1}{2}&\text{$d$ even and $\frac{n}{d}\equiv 2\pmod{4}$}\\ \frac{1}{4}&\text{$d$ even and $\frac{n}{d}$ odd}\end{cases}

and

\left|{\raisebox{1.99997pt}{$P$}\left/\raisebox{-1.99997pt}{$F$}\right.}\right|=\frac{1}{\left|F\right|}\sum_{d|n}\varphi\left(\frac{n}{d}\right)\cdot h(d)\cdot(p^{d}-1).

Corollary \thecorollary@alt.

$D$ is a $\mathrm{GPBIBD}(m)$ with $m=2\cdot\left|{\raisebox{1.99997pt}{$P$}\left/\raisebox{-1.99997pt}{$F$}\right.}\right|-1$ associate classes.

4. The smallest rank underlying association scheme

We have constructed all the $\mathrm{GPBIBD}$ s with $q\leq 169$ on GAP [6], we used the program stabil2 to perform WL-stabilization on the partition of $P\times P$ into $\lambda$ -classes (a $\lambda$ -class consists of all pairs in $P\times P$ that lie on $\lambda$ blocks) in order to obtain an underlying association scheme with the smallest number of classes possible for each incidence structure. It turns out that in a considerable number of cases we in fact obtain an underlying scheme of smaller rank than what is provided by section 3. It follows from Theorem 3 that in those cases the underlying scheme is non-Schurian.

$q$	Class Number in section 3	Smallest Class Number	Parameters $(v,b,r,k;\lambda_{1},\dots,\lambda_{m})$	Remarks
$9$	$3$	$3$	$(20,30,6,9;4,1,0)$
$13$	$5$	$5$	$(42,91,6,13;4,1,0,0,0)$
$17$	$7$	$7$	$(72,204,6,17;4,1,0,\dots,0)$
$25$	$7$	$3$	$(156,130,6,5;1,0,0)$	Non-Schurian. This is an antipodal distance regular graph of diameter $3$ , a $6$ -fold cover of $K_{4}$ .
$29$	$13$	$13$	$(210,1015,6,29;4,1,0,\dots,0)$
$37$	$17$	$17$	$(342,2109,6,37;4,1,0,\dots,0)$
$41$	$19$	$11$	$(420,2870,6,41;4,1,0,\dots,0)$	Non-Schurian. Non-commutative.
$49$	$17$	$13$	$(600,4900,6,49;4,1,0,\dots,0)$	Non-Schurian. Non-commutative.
$53$	$25$	$25$	$(702,6201,6,53;4,1,0,\dots,0)$
$61$	$29$	$29$	$(930,9455,6,61;4,1,0,\dots,0)$
$73$	$35$	$35$	$(1332,16206,6,73;4,1,0,\dots,0)$
$81$	$13$	$5$	$(1640,22140,6,81;4,1,0,0,0)$	non-Schurian.
$89$	$43$	$43$	$(1980,29370,6,89;4,1,0,\dots,0)$
$97$	$47$	$47$	$(2352,38024,6,97;4,1,0,\dots,0)$
$101$	$49$	$49$	$(2550,42925,6,101;4,1,0,\dots,0)$
$109$	$53$	$19$	$(2970,53955,6,109;4,1,0,\dots,0)$	Non-Schurian. Non-commutative.
$113$	$55$	$15$	$(3192,60116,6,113;4,1,0,\dots,0)$	Non-Schurian. Non-commutative.
$121$	$39$	$21$	$(3660,73810,6,121;4,1,0,\dots,0)$	non-Schurian.
$125$		$3$	$(3906,16275,6,25;1,0,\dots,0)$	non-Schurian. This is an antipodal distance regular graph of diameter $3$ , a $31$ -fold cover of $K_{4}$ .
$137$
$149$
$157$
$169$	$47$	$7$	$(7140,201110,6,169;4,1,0,\dots,0)$	non-Schurian.

Acknowledgements

I thank Rosemary Bailey and Eran Nevo for helpful comments on earlier versions of this text.

References

[1] R. A. Bailey. Association schemes, volume 84 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2004. Designed experiments, algebra and combinatorics.
[2] R. C. Bose and K. R. Nair. Partially balanced incomplete block designs. Sankhyā: The Indian Journal of Statistics (1933-1960), 4(3):337–372, 1939.
[3] A. E. Brouwer, A. M. Cohen, and A. Neumaier. Distance-regular graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1989.
[4] Peter J. Cameron. Coherent configurations, association schemes and permutation groups. In Groups, combinatorics & geometry (Durham, 2001), pages 55–71. World Sci. Publ., River Edge, NJ, 2003.
[5] Charles J. Colbourn and Jeffrey H. Dinitz, editors. Handbook of combinatorial designs. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, second edition, 2007.
[6] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.11.1, 2021.
[7] C. Ramankutty Nair. A new class of designs. J. Amer. Statist. Assoc., 59:817–833, 1964.
[8] Eran Nevo. Polyhedrons and PBIBDs from hyperbolic manifolds. Geometriae Dedicata, pages 1–8, 2015.
[9] B. V. Shah. A generalisation of partially balanced incomplete block designs. Ann. Math. Statist., 30:1041–1050, 1959.
[10] Bikas Kumar Sinha. Some aspects of simplicity in the analysis of block designs. J. Statist. Plann. Inference, 6(2):165–172, 1982.

On an infinite family of generalized PBIBDs

Abstract.

1. Introduction and Preliminaries

Definition \thedefinition@alt.

Definition \thedefinition@alt.

2. The construction

Lemma \thelemma@alt.

Corollary \thecorollary@alt.

Lemma \thelemma@alt.

Proof.

Lemma \thelemma@alt.

Proof.

The case p≠5p\neq 5

Lemma \thelemma@alt.

Proof.

Lemma \thelemma@alt.

Proof.

Lemma \thelemma@alt.

Proof.

Theorem 1.

Proof.

The case p=5p=5

Lemma \thelemma@alt.

Proof.

Corollary \thecorollary@alt.

Theorem 2.

Proof.

Question \thequestion@alt.

3. A smaller rank underlying association scheme

Theorem 3.

Proof.

Computing the number of orbits of FF on PP

The case p≡1(mod4)p\equiv 1\pmod{4}

The case p≡3(mod4)p\equiv 3\pmod{4}

Corollary \thecorollary@alt.

4. The smallest rank underlying association scheme

Acknowledgements

References

The case $p\neq 5$

The case $p=5$

Computing the number of orbits of $F$ on $P$

The case $p\equiv 1\pmod{4}$

The case $p\equiv 3\pmod{4}$