On Pseudocyclic Association Schemes

Introduction

A commutative association scheme is called pseudocyclic if the multiplicity of its non-principal irreducible character does not depend on the choice of the character (for a background on theory of association schemes and coherent configurations we refer to and Section 8). It can be proved that such a scheme is equivalenced, i.e. the valencies of its non-reflexive basis relations are pairwise equal. A classical example of a commutative pseudocyclic scheme is a cyclotomic scheme over a finite field; two other series of such schemes were constructed in . A motivation to study pseudocyclic schemes is that any of them produces special $2$-designs.

In this paper we define an association scheme (not necessary commutative) to be pseudocyclic if the ratio of the multiplicity and degree of its non-principal irreducible character does not depend on the choice of the character. Clearly, in the commutative case both definitions give the same concept. To formulate one of the main results of this paper (which, in particular, shows that non-commutative pseudocyclic schemes do exist) we make two remarks. First, as in the commutative case we can prove (Theorem 2.2) that any pseudocyclic scheme is equivalenced; the valency of its non-reflexive basis relation is called the valency of the scheme. Secondly, under a Frobenius scheme we mean the scheme of a Frobenius group (in its standard permutation representation in which the one point stabilizer coincides with the Frobenius complement). Our first result is an immediate consequence of Theorems 2.1 and 6.4.

Any Frobenius scheme is pseudocyclic. Conversely, there exists a function $f(k)$ such that any pseudocyclic scheme of valency $k>1$ and rank at least $f(k)$ is a Frobenius scheme.

The rough upper bound on the function $f(k)$ obtained in the proof is $O(k^{4})$. On the other hand, the scheme of a non-Desarguesian affine plane of order $q$ is non-schurian (see Subsection 3.5), and hence can not be a Frobenius scheme. Besides, it is pseudocyclic of valency $q-1$ and rank $q+2$. Thus $f(k)\geq k+3$.

The proof of the second part of Theorem 1.1 is based on Theorem 4.4 giving together with Theorem 6.1 a sufficient condition for an equivalenced scheme to be schurian.

The celebrated Hanaki-Uno theorem states that any scheme of prime degree is pseudocyclic . Therefore as an immediate consequence of Theorem 1.1 we have the following result.

Any scheme of prime degree, valency $k$ and rank at least $f(k)$ is schurian.

One of the most important problems in association scheme theory is to determine a scheme up to isomorphism by means of the intersection number array. For example, the intersection number array of the scheme of a distance-regular graph is uniquely determined by the parameters of the graph. Therefore the most part of characterizations of the classical distance-regular graphs given in are in fact the characterizations of their schemes in the above sense (we refer to for a survey of relevant results). In this paper we prove the following theorem.

Any Frobenius scheme of valency $k$ and rank at least $f(k)$ is determined up to isomorphism by its intersection number array.

All undefined terms and results concerning permutation groups can be found in monographs . To make the paper as self-contained as possible we cite the background on association schemes and coherent configurations in Section 8. Section 2 contains the definition of a pseudocyclic scheme, several useful results on these schemes and the proof of the first part of Theorem 1.1 (Theorem 2.1). In Section 3 we give a brief exposition of known families of pseudocyclic schemes. In Sections 4 and 5 under a special assumption we explicitly find a one point extension of a pseudocyclic scheme and a one point extension of any algebraic isomorphism from it to another scheme (Theorems 4.4 and 5.2). Based on these results we prove our main theorems in Section 6. Section 7 includes some concluding remarks and special results concerning pseudocyclic schemes.

Notation. Throughout the paper $\Omega$ denotes a finite set. Set $1_{\Omega}=\{(\alpha,\alpha):\ \alpha\in\Omega\}$ and $1_{\alpha}=1_{\{\alpha\}}$ for all $\alpha\in\Omega$. For a relation $r\subset\Omega\times\Omega$ we set $r^{*}=\{(\beta,\alpha):\ (\alpha,\beta)\in r\}$ and $\alpha r=\{\beta\in\Omega:\ (\alpha,\beta)\in r\}$ for all $\alpha\in\Omega$. The adjacency matrix of $r$ is denoted by $A(r)$. For $s\subset\Omega\times\Omega$ we set $r\cdot s=\{(\alpha,\gamma):\ (\alpha,\beta)\in r,\ (\beta,\gamma)\in s$ for some $\beta\in\Omega\}$. If $S$ and $T$ are sets of relations, we set $S\cdot T=\{s\cdot t:\ s\in S,\,t\in T\}$. For a permutation group $G\leq\operatorname{Sym}(\Omega)$ we denote by $\operatorname{Orb}(G)=\operatorname{Orb}(G,\Omega)$ the set of $G$-orbits.

Pseudocyclic schemes

A scheme $(\Omega,S)$ is called pseudocyclic if the number $m_{\scriptscriptstyle P}/n_{\scriptscriptstyle P}$ does not depend on the choice of the central primitive idempotent $P\in{\cal P}^{\#}$ (see Subsection 8.9). In the commutative case $n_{\scriptscriptstyle P}=1$ for all $P\in{\cal P}$, and our definition is compatible with that from . Any regular scheme (not necessarily commutative) is pseudocyclic because in this case $m_{\scriptscriptstyle P}=n_{\scriptscriptstyle P}$ for all $P$. More elaborated example of a non-commutative pseudocyclic scheme arises from a Frobenius group with non-abelian kernel. In what follows we use the family of such groups given in [26, pp.187-189].

Example. Let $q$ be a prime power and $n>1$ an odd integer. Set $H$ to be a subgroup of $\operatorname{GL}(3,q^{n})$ that consists of all matrices of the form

Then the mapping $\sigma:A(a,b)\mapsto A(ca,c^{1+q}b)$ is a fixed point free automorphism of $H$ whenever the multiplicative order of $c$ equals $(q^{n}-1)/(q-1)$. So the semidirect product $G=HK$ where $K=\langle\sigma\rangle$, is a Frobenius group with non-abelian kernel $H$ and complement $K$. The natural action of $G$ on $H$ produces an equivalenced scheme of degree $|H|=q^{2n}$, rank $q^{n+1}-q^{n}+q$ and valency $(q^{n}-1)/(q-1)$. A straightforward calculation for $(q,n)=(2,3)$ shows that the adjacency algebra of the corresponding scheme has exactly four irreducible characters the multiplicities and degrees of which are as follows:

In particular, the scheme is not commutative but is pseudocyclic because $m_{\scriptscriptstyle P}/n_{\scriptscriptstyle P}=7$ for all $P\in{\cal P}^{\#}$. In fact, this example is a special case of the following theorem.

Any Frobenius scheme is pseudocyclic. Moreover, it is commutative if and only if the kernel of the associated Frobenius group is abelian.

Proof. Let $(\Omega,S)$ be a Frobenius scheme, $G\leq\operatorname{Sym}(\Omega)$ the corresponding Frobenius group and the mapping

and hence the same set of central primitive idempotents, say ${\cal P}$. Moreover, one can see that $n_{{\scriptscriptstyle P}}=m_{\chi_{\scriptscriptstyle P}}$ and $m_{{\scriptscriptstyle P}}=\chi_{{\scriptscriptstyle P}}(1)$ for all $P\in{\cal P}$ where $\chi_{P}$ is the irreducible character of $G$ corresponding to the central primitive idempotent $P$. Since $G$ is a Frobenius group, by Theorem 8.4 this implies that

where $K$ is the complement of $G$. Thus $(\Omega,S)$ is a pseudocyclic scheme.

(Indeed, $C$ contains $a^{-1}ca=a^{-1}a^{c}c$ for all $a\in A$ and $c\in C$. On the other hand, since $c\not\in A$, the mapping $a\mapsto a^{-1}a^{c}$, $a\in A$, is a bijection. Thus $CA=C$. Taking into account that $\pi(A^{+})=J_{\Omega}$, we conclude that $\pi(C^{+})$ is a scalar multiple of $J_{\Omega}$.) This implies that

Next, the group $K$ acts semiregularly on the set of non-trivial conjugacy classes of $A$. So any set $C\in\operatorname{Cla}_{G}(A)$ other than $\{1\}$ is a disjoint union of exactly $k=|K|$ of these classes. This shows that

By (2) and (3) this is true if and only if $|\operatorname{Cla}(A)|=|A|$, i.e. the group $A$ is commutative.

We would like to have a characterization of a pseudocyclic scheme in terms of its intersection number array. For commutative case it was done in [5, Proposition 2.2.7].

The following two statements are equivalent:

$(\Omega,S)$ is a pseudocyclic scheme with $m_{\scriptscriptstyle P}/n_{\scriptscriptstyle P}=k$ for all $P\in{\cal P}^{\#}$,

$(\Omega,S)$ is an equivalenced scheme of valency $k$ with $c(r)=k-1$ for all $r\in S^{\#}$.

Moreover, any pseudocyclic scheme with pairwise equal non-principal dimensions of irreducible representations is commutative.

Proof. Set $n=|\Omega|$ and $r=|S|$. We will use the following identity proved in Proposition 3.4 and Lemma 3.8(i) of :

where $\operatorname{reg}(s^{*})=\sum_{t\in S}c_{s^{*}t}^{t}$. Suppose that $m_{\scriptscriptstyle P}/n_{\scriptscriptstyle P}=k$ for all $P\in{\cal P}^{\#}$. Then taking into account that $I=J/n+\sum_{P\in{\cal P}^{\#}}P$ where $I$ is the identity matrix, from (4) we obtain

By comparison of the diagonal and non-diagonal entries of the matrices in both sides of this equality we conclude (after rearrangements) that

This implies that $n_{s}=f=(n-1)/(r-1)$ for all $s\in S^{\#}$. Due to (6) this means that $(\Omega,S)$ is an equivalenced scheme of valency $k$ with $c(r)=\operatorname{reg}(r)=k-1$ for all $r\in S^{\#}$.

Assume now that $(\Omega,S)$ is an equivalenced scheme of valency $k$ with $c(r)=k-1$ for all $r\in S^{\#}$. Then $\operatorname{reg}(s)=c(r)$ for all $r$. So the left side of (4) is a linear combination of the matrices $I$ and $J$. After multiplying both sides of that equality by $P\in{\cal P}^{\#}$ we see that $m_{P}/n_{P}=k$. Thus the scheme $(\Omega,S)$ is pseudocyclic with $m_{P}/n_{P}=k$ for all $P\in{\cal P}^{\#}$.

Let now $(\Omega,S)$ be a pseudocyclic scheme such that $n_{P}$ does not depend on $P\in{\cal P}^{\#}$. Denote this number by $a$. Then by the first part of the proof the scheme is equivalenced of valency $k$ where $ka=m_{P}$ for each $P\in{\cal P}^{\#}$. So from (31) it follows that $|{\cal P}^{\#}|a^{2}=r-1=(n-1)/k$. Therefore $a$ is coprime to $n$. Taking into account that $n_{s}=k$ for all $s\in S^{\#}$, the Frame number of the scheme $(\Omega,S)$ can be computed as follows

Since this number is an integer and $r>1$, we conclude that $a=1$. Thus $n_{P}=1$ for all $P$ and the scheme is commutative.

There is a lot of equivalenced schemes $(\Omega,S)$ for which the group of algebraic isomorphisms acts transitively on $S^{\#}$. These schemes were first studied by Ikuta, Ito and Munemasa , and include the cyclotomic schemes over finite fields and the schemes of affine planes (see Section 3). The following statement shows that all of them are pseudocyclic.

Let $(\Omega,S)$ be an equivalenced scheme. Suppose that a group of its algebraic isomorphisms acts transitively on $S^{\#}$. Then $(\Omega,S)$ is a pseudocyclic scheme.

Proof. From the hypothesis it follows that the number $c(s)$ does not depend on $s\in S^{\#}$. So by Lemma 8.2 this number equals $k-1$ and we are done by Theorem 2.2.

Sometimes one can construct a new pseudocyclic scheme by means of an appropriate algebraic fusion defined as follows. Let $G$ be a group of algebraic isomorphisms of a coherent configuration $(\Omega,S)$. Set

where $s^{G}$ is the union of the relations $s^{g}$, $g\in G$. It is easily seen that the pair $(\Omega,S^{G})$ is a coherent configuration. Moreover, if the group $G$ is half-transitive on $S^{\#}$ and the coherent configuration $(\Omega,S)$ is equivalenced, then $(\Omega,S^{G})$ is an equivalenced scheme. An analog of this statement holds for commutative pseudocyclic schemes.Using Theorem 2.4 enables us to reduce substantially the proofs in [20, Section 3].

Let $(\Omega,S)$ be a commutative pseudocyclic scheme of valency $k$ and $G$ a group of algebraic isomorphisms of it. Suppose that $G$ acts semiregularly on $S^{\#}$. Then $(\Omega,S^{G})$ is a commutative pseudocyclic scheme of valency $km$ where $m=|G|$.

Proof. We observe that $(\Omega,S^{G})$ being a fusion of a commutative scheme is also commutative. Since it is equivalenced of valency $km$ (see above), we have

Finally, any $G$-orbit in ${\cal P}$ is of cardinality at most $m$. Since $P_{0}$ leaved fixed under $G$ and $|{\cal P}|=|S|$, this implies that

and the equality holds exactly when any $G$-orbit in ${\cal P}^{\#}$ is of size $m$. Together with (7) and (8) this shows that $|{\cal P}^{G}|=|{\cal P}^{\prime}|$. Therefore $m_{\scriptscriptstyle P^{G}}=mm_{P}=mk$ and $n_{\scriptscriptstyle P^{G}}=1$ for all $P\in{\cal P}^{\#}$. Thus the scheme $(\Omega,S^{G})$ is pseudocyclic.

A schurian equivalenced non-regular scheme is nothing but the scheme of $3/2$-transitive group. In general, the latter is not a Frobenius group. However, the following statement holds.

A schurian pseudocyclic scheme of valency $k>1$ and rank greater than $2(k-1)$ is a Frobenius scheme the automorphism group of which is a Frobenius group.

Proof. Let $(\Omega,S)$ be a schurian pseudocyclic scheme of valency $k>1$ and $G=\operatorname{Aut}(\Omega,S)$. Then the set $\operatorname{Fix}(g)$ of points left fixed by a nonidentity permutation $g\in G$ does not coincide with $\Omega$. So there exists $\alpha\in\Omega$ such that $\alpha^{g}\neq\alpha$. Since $r(\alpha,\beta)=r(\alpha^{g},\beta)$ for all $\beta\in\operatorname{Fix}(g)$, Theorem 2.2 implies that

where $s=r(\alpha,\alpha^{g})$. Thus the permutation character of $G$ takes the value in the set $\{0,\ldots,k-1\}$ on all nonidentity elements. Therefore by [7, Prop.1] a point stabilizer $G_{\alpha}$ has at most $2(k-1)-1$ non-regular orbits. If $|S|>2(k-1)$, then at least one orbit of $G_{\alpha}$ is regular. This implies that so are all non-trivial orbits. Thus $G$ is a Frobenius group.

Known examples of pseudocyclic schemes

Any pseudocyclic scheme of rank $3$ arises from either a conference matrix (symmetric case) or from a skew Hadamard matrix (antisymmetric case) . In any case the intersection number array is uniquely determined by the degree of the scheme. In particular, two such schemes are algebraically isomorphic if and only if they have the same degree. Since there is an infinite number of $n$ for which there are at least two non-equivalent conference matrices or non-equivalent skew Hadamard matrices of order $n$, in general pseudocyclic schemes of rank $3$ are not separable. Similarly, one can see that most of them are non-schurian. For instance, it follows from that an antisymmetric pseudocyclic scheme of rank $3$ is schurian if and only if it is a scheme of a Paley tournament. Moreover, in [16, p.75] one can find an infinite family of non-schurian pseudocyclic schemes of rank $3$ satisfying the $4$-condition.

2. The Hollman schemes [5, p.390].

Let $q>4$ be a power of $2$. Denote by $\Omega$ the set of cyclic groups of order $q+1$ in the group $\operatorname{PSL}(2,q)$. The latter acts transitively on $\Omega$ by conjugation and hence produces the scheme of degree $(q^{2}-q)/2$. One can prove that this scheme is symmetric and pseudocyclic of valency $q+1$. Some algebraic fusions of the Hollman scheme that are also pseudocyclic were studied in .

3. The Passman schemes [25].

Let $q$ be an odd prime power and $G$ the group consisting the transformations

where $a,b,c\in\operatorname{GF}(q)$, and $a\neq 0$. Then $G$ is a $3/2$-transitive group acting on a $2$-dimensional space over $\operatorname{GF}(q)$. The scheme of this group is equivalenced of degree $q^{2}$ and valency $2(q-1)$. In fact, the Passman scheme is the algebraic fusion of the Frobenius scheme of valency $q-1$ corresponding to the subgroup of $G$ of order $(q-1)q^{2}$ consisting of the first family of permutations from (9). Thus by Theorems 2.1 and 2.4 the Passman scheme is pseudocyclic.

4. Cyclotomic schemes.

Let $R$ be a finite local commutative ring with identity. Then its multiplicative group $R^{\times}$ is the direct product of the Teichmüller group ${\cal T}$ and the group of principal units . The Teichmüller group is isomorphic to the multiplicative group of the residue field of $R$, and acts as a fixed point free automorphism group of the additive group $R^{+}$ of $R$. Therefore for a given $K\leq{\cal T}$, the scheme $\operatorname{Cyc}(K,R)$ of the group $(R^{+}\rtimes K,R^{+})$ is a Frobenius scheme and hence pseudocyclic by Theorem 2.1. This example is a special case of a cyclotomic scheme over a finite commutative ring . In almost the same way one can construct a class of pseudocyclic schemes where the ground ring $R$ is replaced by a near-field , or even a near-ring.

5. Affine schemes.

Let $\Omega$ be a point set of a finite affine space ${\cal A}$ (see ). Denote by $S$ the partition of $\Omega\times\Omega$ containing $1_{\Omega}$ and such that two pairs $(\alpha,\beta),(\alpha^{\prime},\beta^{\prime})\in\Omega\times\Omega$, $\alpha\neq\beta$, $\alpha^{\prime}\neq\beta^{\prime}$, belong to the same class if and only if the lines $\alpha\beta$ and $\alpha^{\prime}\beta^{\prime}$ are equal or parallel. Then the pair $(\Omega,S)$ is a symmetric scheme and nonzero intersection numbers $c_{rs}^{t}$ with $1_{\Omega}\not\in\{r,s\}$ are as follows:

where $q$ is the size of a line in ${\cal A}$ (called the order of ${\cal A}$). It follows that it is a pseudocyclic scheme of valency $q-1$. Each relation of an affine scheme is an involution in a sense of . It was shown in that a scheme whose relations are involutions is an affine scheme. Thus there is one-to-one correspondence between affine schemes and affine spaces. It is straightforward to prove that the schemes of affine spaces are isomorphic (resp. algebraically isomorphic) if and only if the affine spaces are isomorphic (resp. have the same order).

The scheme of a finite affine space ${\cal A}$ is schurian if and only if ${\cal A}$ is Desarguesian.

Proof. By the Veblen-Young theorem (cf. ) a finite affine space ${\cal A}$ is either a non-Desarguesian affine plane, or the $n$-dimensional affine geometry $\operatorname{AG}(n,q)$ over $\operatorname{GF}(q)$. In the latter case the scheme of ${\cal A}$ coincides with the scheme of the group

where $T$ is the translation group and $C$ is the centre of $\operatorname{GL}(n,q)$. This proves the sufficiency part of the theorem. To prove the necessity assume that the scheme of ${\cal A}$ is schurian. Then it satisfies the $4$-condition and the required statement immediately follows from the lemma below.

Suppose that the scheme of an affine space ${\cal A}$ satisfies the $4$-condition. Then ${\cal A}$ is Desarguesian.

Proof. Let $(\Omega,S)$ be the scheme of ${\cal A}$. It suffices to verify that given seven distinct points $\alpha,\alpha^{\prime}$, $\beta,\beta^{\prime}$, $\gamma,\gamma^{\prime}$ and $\delta$, such that $\alpha\alpha^{\prime}$, $\beta\beta^{\prime}$, and $\gamma\gamma^{\prime}$ are distinct lines through $\delta$ and $\alpha\gamma$ is parallel to $\alpha^{\prime}\gamma^{\prime}$ and $\beta\gamma$ is parallel to $\beta^{\prime}\gamma^{\prime}$, then $\alpha\beta$ is parallel to $\alpha^{\prime}\beta^{\prime}$ (see Fig 1).

However, since $\delta\gamma=\delta\gamma^{\prime}$, we have $r(\delta,\gamma)=r(\delta,\gamma^{\prime})$. Due to the $4$-condition there exist points $\alpha^{\prime\prime},\beta^{\prime\prime}$ such that the $4$-sets $\Delta=\{\delta,\gamma,\alpha,\beta\}$ and $\Delta^{\prime}=\{\delta,\gamma^{\prime},\alpha^{\prime\prime},\beta^{\prime\prime}\}$ have the same type with respect to the pairs $(\delta,\gamma)$ and $(\delta,\gamma^{\prime})$ respectively. So $r(\alpha,\delta)=r(\alpha^{\prime\prime},\delta)$ and $r(\beta,\delta)=r(\beta^{\prime\prime},\delta)$. This implies that

On the other hand, $r(\alpha,\gamma)=r(\alpha^{\prime\prime},\gamma^{\prime})$ and $r(\beta,\gamma)=r(\beta^{\prime\prime},\gamma^{\prime})$. Therefore $\alpha\gamma$ is parallel to $\alpha^{\prime\prime}\gamma^{\prime}$, and $\beta\gamma$ is parallel to $\beta^{\prime\prime}\gamma^{\prime}$. Thus from (11) we conclude that $\alpha^{\prime\prime}=\alpha^{\prime}$ and $\beta^{\prime\prime}=\beta^{\prime}$. Since also $r(\alpha,\beta)=r(\alpha^{\prime\prime},\beta^{\prime\prime})$, the line $\alpha\beta$ is parallel to $\alpha^{\prime\prime}\beta^{\prime\prime}=\alpha^{\prime}\beta^{\prime}$, and we are done.

6. Amorphic schemes.

A scheme $(\Omega,S)$ is called amorphic if any its fusion is a scheme. It was shown in that all basis graphs of an amorphic scheme of rank at least four are strongly regular either of Latin square type or of negative Latin square type. If an amorphic scheme is equivalenced, then its group of algebraic automorphisms is $\operatorname{Sym}(S^{\#})$. This implies (Corollary 2.3) that $(\Omega,S)$ is pseudocyclic. A scheme of an affine plane of order $q$ is an amorphic $(q-1)$-valenced scheme of rank $q+2$. This yields us the following statement.

Let $q$ be the order of an affine plane. Then given a divisor $m$ of $q+1$ and a partition of $\{1,\ldots,q+1\}$ in $m$ classes of cardinality $(q+1)/m$, there exists an amorphic pseudocyclic scheme of degree $q^{2}$, valency $(q^{2}-1)/m$ and rank $m+1$.

One point extension of an equivalenced scheme.

Let $(\Omega,S)$ be an equivalenced scheme of valency $k$. For each (possibly equal) basis relations $u,v\in S^{\#}$ we define the splitting set of them as follows:

It is easily seen that $D(u,v)=D(v,u)$ and $uu^{*}\cap ww^{*}=vv^{*}\cap ww^{*}=\{1_{\Omega}\}$ for all $w\in D(u,v)$. Therefore from Lemma 8.3 it follows that

for all $s\in S$. In particular, $|u^{*}w|=|w^{*}v|=k$.

Given $w\in D(u,v)$ the following statements hold:

$|u^{*}v|=k\ \Leftrightarrow\ u\in D(v,w)\ \Leftrightarrow\ v\in D(w,u)$,

$|ab\cap u^{*}v|=1$ for all $a\in u^{*}w$ and $b\in w^{*}v$.

Proof. To prove statement (1) suppose that $|u^{*}v|=k$. Then $c_{u^{*}v}^{t}\leq 1$ for all $t\in S$. So from Lemma 8.3 it follows that $uu^{*}\cap vv^{*}=\{1_{\Omega}\}$. On the other hand, given a relation $s\in(vv^{*}\,ww^{*})\cap uu^{*}$ one can find points $\alpha,\beta\in\Omega$ to have the configuration at Fig. 2.

So $r(\alpha,\beta)\in(uu^{*}\,vv^{*})\cap ww^{*}=\{1_{\Omega}\}$ whence it follows that $\alpha=\beta$. Therefore $s\in vv^{*}\cap uu^{*}=\{1_{\Omega}\}$. Thus $s=1_{\Omega}$, and hence $u\in D(v,w)$. Conversely, if $u\in D(v,w)$, then $(vv^{*}\,ww^{*})\cap uu^{*}=\{1_{\Omega}\}$. So $vv^{*}\cap uu^{*}=\{1_{\Omega}\}$, and hence $|u^{*}v|=k$ by Lemma 8.3. This completes the proof of the first equivalence in statement (1). The second equivalence immediately follows from the first one by interchanging $u$ and $v$ because $D(u,v)=D(v,u)$.

To prove statement (2) let $a\in u^{*}w$ and $b\in w^{*}v$. Then $w\in ua\cap vb^{*}$. This implies that $|ua\cap vb^{*}|\geq 1$, and hence $|ab\cap u^{*}v|\geq 1$. Thus it suffices to verify that $|ab\cap u^{*}v|\leq 1$. To do this we need the following auxiliary statement.

Given a relation $s\in ab\cap u^{*}v$ and points $\alpha,\beta,\gamma\in\Omega$ such that $r(\alpha,\beta)=s$, $r(\alpha,\gamma)=a$ and $r(\gamma,\beta)=b$ there exists a unique point $\delta\in\Omega$ for which $r(\delta,\alpha)=u$, $r(\delta,\beta)=v$ and $r(\delta,\gamma)=w$ (see Fig. 3)

Proof. Since $a\in u^{*}w$ and $b\in w^{*}v$, there exist points $\lambda$, $\mu$, $\nu$ such that $r(\lambda,\alpha)=u$, $r(\lambda,\beta)=v$, $r(\mu,\alpha)=u$, $r(\mu,\gamma)=w$ and $r(\nu,\gamma)=w$, $r(\nu,\beta)=v$ (see Fig. 4).

Now $r(\mu,\nu)\in(uu^{*}\,vv^{*})\cap ww^{*}=\{1_{\Omega}\}$. Thus $\mu=\nu$. Denote this point by $\delta$. Then for $\delta$ the statement of the lemma holds. To prove the uniqueness we note if $\delta_{1}$ and $\delta_{2}$ are two points forming Fig. 3, then the relation $r(\delta_{1},\delta_{2})$ belongs to the set $ww^{*}\cap uu^{*}\cap vv^{*}=\{1_{\Omega}\}$, and hence $\delta_{1}=\delta_{2}$.

To complete the proof of Theorem 4.1 suppose that $ab\cap u^{*}v\supset\{s_{1},s_{2}\}$ with $s_{1}\neq s_{2}$. Then there exist points $\alpha,\gamma,\beta_{1},\beta_{2}\in\Omega$, such that $\beta_{1}\neq\beta_{2}$, $r(\alpha,\gamma)=a$ and $r(\gamma,\beta_{i})=b$, $r(\alpha,\beta_{i})=s_{i}$ for $i=1,2$. By Lemma 4.2 with $s=s_{i}$ one can find a point $\delta_{i}$ for which $r(\delta_{i},\alpha)=u$, $r(\delta_{i},\beta)=v$ and $r(\delta_{i},\gamma)=w$ (see Fig. 5).

Since the relation $r(\delta_{1},\delta_{2})$ belongs to the set $ww^{*}\cap uu^{*}=\{1_{\Omega}\}$, we have $\delta_{1}=\delta_{2}$. Denote this point by $\delta$. Then $r(\delta,\beta_{i})=v$. Since $r(\beta_{i},\gamma)=b^{*}$, $r(\delta,\gamma)=w$ and $\beta_{1}\neq\beta_{2}$, this implies that $c_{vb^{*}}^{w}\geq 2$. So by equivalencity $(X,\Omega)$ and (33) we conclude that $c_{w^{*}v}^{b}\geq 2$ which contradicts to (13).

2. A one point extension.

By means of splitting sets we are going to find explicitly the $\alpha_{0}$-extension of the scheme $(\Omega,S)$ for any point $\alpha_{0}\in\Omega$. To do this for any relations $u,v\in S$ set

It is easily seen that the union of relations from $S(u,v)$ coincides with the set $\alpha_{0}u\times\alpha_{0}v$. Suppose that $w\in D(u,v)$. Then from statement (2) of Theorem 4.1 it follows that

where $S(u,v;w)=S_{\alpha_{0}}(u,v;w)=S(u,w)\cdot S(w,v)$. Suppose, in addition, that $|u^{*}v|=k$. Then any relation in $S(u,v)$ is of cardinality $k$. Since the same is true for the relations in $S(u,v;w)$, we conclude that

In particular, in this case the relations from $S(u,v;w)$ form a partition of the set $\alpha_{0}u\times\alpha_{0}v$. For arbitrary $u$ and $v$ we will prove the latter only under the following additional assumption:

In this case obviously $D(u,v)\neq\emptyset$.

Let $u,v\in S^{\#}$ be such that (17) holds. Then the set $S(u,v;w)$ forms a partition of the set $\alpha_{0}u\times\alpha_{0}v$, and this partition does not depend on the choice of the relation $w\in D(u,v)$.

Proof. Let $w,w^{\prime}\in D(u,v)$. Then $|u^{*}w|=|u^{*}w^{\prime}|=|v^{*}w|=|v^{*}w^{\prime}|=k$. On the other hand, due to (17) one can find a relation

Let $a\in S(u,t)$ and $b\in S(t,v)$. Since obviously $b^{*}\in S(v,t)$ by (18) with $(x,y)=(u,w)$ and $(x,y)=(v,w)$ we obtain

So the element $a\cdot b\in S(u,v;w)$ has at least $k$ different representations (one for each choice of $c$) of the form $a\cdot b=(a\cdot c)(c^{*}\cdot b)$ with $c^{*}\cdot b\in S(w,v)$. Since $|S(u,w)|=|S(w,v)|=k$ this implies that $|S(u,v;w)|=k$. Thus $S(u,v;w)$ is a partition of $\alpha_{0}u\times\alpha_{0}v$ and $S(u,v;w)=S(u,v;t)$. Similarly, using equalities (18) with $(x,y)=(u,w^{\prime})$ and $(x,y)=(v,w^{\prime})$ one can prove that $S(u,v;w^{\prime})$ is a partition of $\alpha_{0}u\times\alpha_{0}v$ and that $S(u,v;w^{\prime})=S(u,v;t)$. Thus

By Lemma 4.3 we can define a uniquely determined partition of the set $\Omega_{0}\times\Omega_{0}$ where $\Omega_{0}=\Omega\setminus\{\alpha_{0}\}$, as follows

It is easily seen that $1_{\alpha_{0}u}\in S_{0}$ for all $u\in S^{\#}$. Therefore $1_{\Omega_{0}}\in S_{0}^{\cup}$. Besides, since obviously $S(u,v;w)^{*}=S(v,u;w)$ for all $u,v,w$, the partition $S_{0}$ is closed with respect to $*$. Finally, the condition (27) is satisfied for $S=S_{0}$. Therefore if $(\Omega_{0},S_{0})$ is a coherent configuration, then it is semiregular. We will prove the former under the following assumption:

Let $(\Omega,S)$ be an equivalenced scheme satisfying conditions (17) and (20) for all $u,v\in S^{\#}$. Then

In particular, the $\alpha_{0}$-extension of $(\Omega,S)$ is a semiregular coherent configuration on $\Omega_{0}$ the fibers of which are $\alpha_{0}u$, $u\in S$.

Proof. It suffices to verify that $(\Omega_{0},S_{0})$ is a coherent configuration. Indeed, if it is so and $S^{\prime}=S_{0}(\alpha_{0})\cup S_{1}(\alpha_{0})$, then obviously $(\Omega,S^{\prime})$ is a semiregular coherent configuration the fibers of which are $\alpha_{0}u$, $u\in S$. Therefore due to (15) we have $1_{\alpha_{0}}\in S^{\prime}$ and $S\subset(S^{\prime})^{\cup}$. By the minimality of the $\alpha_{0}$-extension this implies that

On the other hand, it is easily seen that the set $S(u,v)$, and hence the set $S(u,v;w)=S(u,w)\cdot S(w,v)$ is contained in $(S_{\alpha_{0}})^{\cup}$ for all $u,v,w\in S$. Therefore $S^{\prime}\subset(S_{\alpha_{0}})^{\cup}$. Together with (21) this shows that $(S_{\alpha_{0}})^{\cup}=(S^{\prime})^{\cup}$. Thus $S_{\alpha_{0}}=S^{\prime}$ and we are done.

Let us prove that $(\Omega_{0},S_{0})$ is a coherent configuration. We observe that due to (17) Lemma 4.3 implies that $S_{0}$ is a partition of $\Omega_{0}\times\Omega_{0}$. Thus it suffices to verify that if $b,c\in S_{0}$ with $b\cdot c\neq\emptyset$, then $b\cdot c\in S_{0}$ (see the remarks after (19)). However, for such $b$ and $c$ we have

for appropriate $u,v,w\in S^{\#}$. By condition (20) one can find

Since $b=a_{1}\cdot a_{2}$ for some $a_{1}\in S(u,v;t)$ and $a_{2}\in S(v,w;t)$, this implies that $|S(v,t)|=|S(w,t)|=k$ where $k$ is the valency of $(\Omega,S)$. So by statement (1) of Theorem 4.1 we have $w\in D(v,t)$. Therefore $a_{2}^{*}\in S(v,t;w)$ and hence there exists $a_{3}\in S(t,w)$ such that $c=a_{2}^{*}\cdot a_{3}$. Thus

This means that $b\cdot c\in S_{0}$ which completes the proof.

One point extension of an algebraic isomorphism

We keep the notation of Section 4. Let $(\Omega^{\prime},S^{\prime})$ be a scheme and let

be an algebraic isomorphism. Then obviously $(\Omega^{\prime},S^{\prime})$ is an equivalenced scheme of valency $k$, and

Let us fix a point $\alpha^{\prime}_{0}\in\Omega^{\prime}$. Take $u,v\in S$. Since $c_{uv}^{w}=c_{u^{\prime}v^{\prime}}^{w^{\prime}}$ for all $w\in S$, the mapping $\varphi$ induces a bijection

where $a=s\cap(\alpha_{0}u\times\alpha_{0}v)$ and $a^{\prime}=s^{\prime}\cap(\alpha^{\prime}_{0}u^{\prime}\times\alpha^{\prime}_{0}v^{\prime})$. Below we set $S^{\prime}(u^{\prime},v^{\prime})=S_{\alpha^{\prime}_{0}}(u^{\prime},v^{\prime})$.

Let $u,v\in S^{\#}$ be such that (17) holds. Then for any relations $w_{1},w_{2}\in D(u,v)$ we have

for all $b_{i}\in S(u,w_{i})$ and $c_{i}\in S(w_{i},v)$, $i=1,2$.

Proof. Suppose that $b_{1}\cdot c_{1}=b_{2}\cdot c_{2}$ where $b_{i}\in S(u,w_{i})$ and $c_{i}\in S(w_{i},v)$, $i=1,2$. Then $|u^{*}w_{1}|=|u^{*}w_{2}|=|v^{*}w_{1}|=|v^{*}w_{2}|=k$. Besides, by (17) one can find a relation

Take any $a_{1}\in S(u,t)$. By (22) we have $d_{1}:=a_{1}^{*}b_{1}\in S(t,w_{1})$ and $d_{2}:=a_{1}^{*}\cdot b_{2}\in S(t,w_{2})$. Since $w_{1}\in D(t,v)$, we also have $a_{2}:=d_{1}\cdot c_{1}\in S(t,v)$. Thus

whence it follows that $c_{2}=d_{2}^{*}\cdot a_{2}$ (Figure 6).

Let us define a mapping $\varphi_{0}:S_{0}\to S^{\prime}_{0}$ where $S_{0}=S_{\alpha_{0}}$ and $S^{\prime}_{0}=S^{\prime}_{\alpha^{\prime}_{0}}$, as follows. Take $s\in S_{0}$. Then $s\subset\alpha_{0}u\times\alpha_{0}v$ for some $u,v\in S$. Set

where $w\in D(u,v)$ and $s_{1}\in S(u,w)$, $s_{2}\in S(w,v)$ are such that $s_{1}\cdot s_{2}=s$. By Theorem 4.4 and Lemma 5.1 the mapping $\varphi_{0}$ is a correctly defined bijection.

Let $(\Omega,S)$ be an equivalenced scheme satisfying conditions (17) and (20) for all $u,v\in S^{\#}$, and $\varphi:(\Omega,S)\to(\Omega^{\prime},S^{\prime})$ an algebraic isomorphism. Then $\varphi_{0}$ is the $(\alpha_{0},\alpha^{\prime}_{0})$-extension of $\varphi$.

Proof. We observe that relations (29) hold by statement (2) of Theorem 4.1. Therefore it suffices to verify that

To do this take such relations $b$ and $c$. Then there exist $u,v,w\in S^{\#}$ such that

By condition (20) one can find $t\in D(u,v)\cap D(v,w)\cap D(w,u)$. Since $b\in S_{0}$, there exist $a_{1}\in S(u,t)$ and $a_{2}\in S(t,v)$ such that $b=a_{1}\cdot a_{2}$. However, $|S(u,t)|=|S(t,v)|=k$. Therefore $b^{\varphi_{0}}=a_{1}^{\varphi_{0}}\cdot a_{2}^{\varphi_{0}}$ (if $|u^{*}v|=k$, then this follows from statement (2) of Theorem 4.1; otherwise this immediately follows from the definition of $\varphi_{0}$). On the other hand, we have $|S(v,t)|=|S(w,t)|=k$. Therefore $a_{2}^{*}\in S(v,t)$ and there exists $a_{3}\in S(t,w)$ such that $c=a_{2}^{*}\cdot a_{3}$ (see Figure 7).

As above one can see that $c^{\varphi_{0}}=(a_{2}^{*})^{\varphi_{0}}\cdot a_{3}^{\varphi_{0}}$ and that $(a_{1}\cdot a_{3})^{\varphi_{0}}=(a_{1})^{\varphi_{0}}\cdot a_{3}^{\varphi_{0}}$. Thus

Schurity and separability of equivalenced schemes

The conclusion of Theorem 4.4 gives a sufficient condition for a scheme to be schurian.

Let $(\Omega,S)$ be a scheme such that for each $\alpha\in\Omega$ the coherent configuration $(\Omega,S_{\alpha})$ is semiregular on $\Omega\setminus\{\alpha\}$ and its fibers are $\alpha s$, $s\in S$. Then $(\Omega,S)$ is a regular or Frobenius scheme.

Proof. Let $\alpha\in\Omega$. Then by Theorem 8.1 the coherent configuration $(\Omega,S_{\alpha})$ is schurian, and hence due to (28) any set $\alpha s$, $s\in S$, is the orbit of the group $G_{\alpha}$ where $G=\operatorname{Aut}(\Omega,S)$. Since obviously $G_{\alpha,\beta}=\operatorname{id}_{\Omega}$ for all $\alpha\neq\beta$, it suffices to verify that the group $G$ is transitive. To do this we note that semiregularity of $G_{\alpha}$ on $\Omega\setminus\{\alpha\}$ implies that

Let $\Delta\in\operatorname{Orb}(G,\Omega)$. Since any orbit of $G$ is a disjoint union of some orbits of the group $G_{\alpha}$, the number $|\Delta|$ is divided by $k$ if and only if $\alpha\not\in\Delta$. However, this is impossible if $\Delta\neq\Omega$. Thus $G$ is transitive.

Let $(\Omega,S)$ be the scheme of an affine space ${\cal A}$. Then from (10) it follows that $D(u,v)=S^{\#}\setminus uv$ for all $u,v\in S^{\#}$. Therefore conditions (17) and (20) are satisfied whenever the dimension of ${\cal A}$ is at least $3$. Thus in this case by Theorems 4.4 and 6.1 the scheme $(\Omega,S)$ is schurian. Since the scheme is imprimitive, its automorphism group is a Frobenius group in its natural permutation representation. Using properties of Frobenius groups one can prove, without using Veblen-Young Theorem, that the scheme $(\Omega,S)$ is an affine scheme of a Desarguesian affine space.

2. Separability.

Similarly to the previous subsection the conclusion of Theorem 5.2 gives a sufficient condition for a scheme to be separable.

In the condition of Theorem 6.1 the scheme $(\Omega,S)$ is separable.

Proof. From Theorem 5.2 it follows that any algebraic isomorphism $\varphi:(\Omega,S)\to(\Omega,S^{\prime})$ has the $(\alpha,\alpha^{\prime})$-extension

for all $(\alpha,\alpha^{\prime})\in\Omega\times\Omega^{\prime}$. By Theorem 4.4 the coherent configuration $(\Omega,S_{\alpha})$ is semiregular on $\Omega\setminus\{\alpha\}$, and hence is separable (Theorem 8.1). This implies that the algebraic isomorphism $\varphi_{\alpha,\alpha^{\prime}}$ is induced by an isomorphism. Due to the right-hand side of (29) this shows that the same isomorphism induces the algebraic isomorphism $\varphi$. Thus any algebraic isomorphism of the scheme $(\Omega,S)$ is induced by an isomorphism and hence this scheme is separable.