betaFeedback

WorksMathematics

On configurations that are nearly generalised polygons

Abstract

Payne (1972) introduced nearly generalised nn-gons as (s+1)(s+1)-regular bipartite graphs of girth 2n2n with small excess over the Moore bound. Biggs and Ito (1980) proved nonexistence of such graphs if s>1s > 1 and n>3n > 3, leaving open the existence of regular antipodal planes. We revisit this problem from several equivalent viewpoints. First we show that a regular antipodal plane of order ss is equivalent to a balanced weighing matrix whose support is the incidence matrix of a biplane with parameters 2−(s2+s+22, s+1, 2). 2-\left(\frac{s^2+s+2}{2},\,s+1,\,2\right). This gives short determinant and local-arithmetic obstructions to existence. We then formulate the question of signing a biplane as an affine linear system over F2\mathbb F_2, and use this formulation to prove that no regular antipodal plane of order ss exists with 4≤s≤144\le s\le 14. Finally, we give further equivalent formulations in terms of sharply deranged families of permutations and mutually orthogonal array-bic squares. These translations provide new computational and structural approaches to Payne's conjecture that regular antipodal planes exist only for s=2,3s=2,3.

Introduction

The cage problem is to determine the minimum number c(k,g)c(k,g) of vertices in a kk-regular graph of girth gg; graphs attaining this bound are called cages. Although cages exist for all integers k≥2k\ge2 and g≥3g\ge3, the exact value of c(k,g)c(k,g) is known only for a small number of parameter pairs, together with three infinite families occurring when g∈{6,8,12}g\in\{6,8,12\} and k−1k-1 is a prime power. These families arise as the incidence graphs of generalised polygons. For the even-girth case, by counting out from a vertex, it is not difficult to see that a simple undirected (s+1)(s+1)-regular bipartite graph of even girth gg has at least

2(1+s+s2+⋯+s(g−2)/2)2\left(1+s+s^2+\cdots+s^{(g-2)/2}\right)

vertices, and those graphs meeting this bound are known as Moore graphs. Interestingly, there are very few Moore graphs. It has been proved that a bipartite Moore graph with k>2k>2 has g∈{4,6,8,12}g\in\{4,6,8,12\} and is the incidence graph of a generalised (g/2)(g/2)-gon of order k−1k-1.

Payne [17] [17] introduced the notion of a nearly generalised nn-gon, by relaxing the condition that the number of vertices meets the Moore bound. These graphs have parameters (n,s)(n,s), and they are (s+1)(s+1)-regular bipartite graphs of girth 2n2n with

2(2+s+s2+⋯+sn−1)2\left(2+s+s^2+\cdots+s^{n-1}\right)

vertices. So for example, if n=3n=3, it is the incidence graph of a regular antipodal plane: a partial linear space of points and lines such that (i) every point is incident with s+1s+1 lines, (ii) every line is incident with s+1s+1 points, and (iii) for every point PP, there is a unique point P∗P^* not collinear with PP, and for every line ℓ\ell, there is a unique line ℓ∗\ell^* not concurrent with ℓ\ell. Antipodal planes were studied by Dembowski [7 Section 7.4] as elliptic semi-planes with parallel classes of size 22, and he observed that they are 22-covers of biplanes. Payne showed that there are examples of nearly 33-gons for s=2,3s=2,3, but

2020 Mathematics Subject Classification. Primary 05B25; Secondary 05B05, 05B15, 51E12.

Key words and phrases. nearly generalised polygon; regular antipodal plane; biplane; balanced weighing matrix; weighing signing; sharply deranged permutations; equidistant permutation array; mutually orthogonal array-bic squares; loops. no examples for s=4s = 4. Indeed, he conjectured that there are no examples for s>3s > 3. He also showed that there are no nearly nn-gons for n∈{4,5,6}n \in\{4, 5, 6\} (with s>1s > 1). A substantial breakthrough was made by Biggs and Ito [4] in 1980: there is no nearly nn-gon (with s>1s > 1) for n>3n > 3. So the problem reduces to the existence of regular antipodal planes. Throughout, we will assume s>1s > 1.

Further work has been done recently by Schleiermacher [21] and De Boeck and Van de Voorde [6]. The latter showed that no antipodal plane of order s>3s > 3 can be embedded in a Desarguesian projective plane. Both papers note that a regular antipodal plane double covers a biplane, but did not note the existence of a weighing matrix, which imposes further restrictions on the possible orders of a regular antipodal plane.

In this paper we draw attention to some objects in graph theory, incidence geometry, and design theory that can be unified. For instance, a balanced weighing matrix with parameters (k,2)(k, 2) is equivalent to a regular antipodal plane of order k−1k - 1 (see Theorem 2.2). Figure 1 gives an example of the three combinatorial objects that we will show are equivalent. Indeed, a regular antipodal plane is equivalent to a sharply deranged set of permutations, and hence gives rise to an equidistant permutation array. Through this connection, a recent result of Tolonen [25] implies that there is no regular antipodal plane of order 8. We show that there are no regular antipodal planes of order ss with 4≤s≤144 \le s \le14 (see § 2).

Three equivalent combinatorial objects: a sharply deranged set, mutually orthogonal array-bic squares, and a balanced weighing matrix

Figure 1. Three equivalent objects.

Declaration of AI use. We used AI (ChatGPT) to find references, such as the important work of Biggs and Ito [4] and the result of Schellenberg [20]. It also gave us the main idea of Proposition 2.12. We used it to write code to search for array-bic squares in Julia [3].

Nearly 3-gons, antipodal planes

Weighing matrices

A regular antipodal plane has the property that the star operation preserves incidence: if PP is a point incident with ℓ\ell, then P∗P^* is incident with ℓ∗\ell^* (see [6 Lemma 2.2]). We can define a biplane, a symmetric 22-((s2+s+2)/2,s+1,2)((s^2+s+2)/2, s+1, 2) design, in the following way: the points are the pairs {P,P∗}\{P, P^*\}, and the blocks are the pairs {ℓ,ℓ∗}\{\ell, \ell^*\}, and a point {P,P∗}\{P, P^*\} is incident with a block {ℓ,ℓ∗}\{\ell, \ell^*\} if PP is incident with ℓ\ell or P∗P^* is incident with ℓ\ell. Payne observes that the Bruck–Ryser–Chowla Theorem for symmetric designs, plus a linear algebraic property of the incidence matrix, give rise to infinitely many forbidden values of ss:

Theorem 2.1 (Payne [17 Theorems 5.1, 5.2]).

(a) If s≡3(mod8)s \equiv3 \pmod{8} and if there is a prime congruent to 7 (mod8)\pmod{8} dividing the square-free part of s−1s - 1, then no nearly 3-gon of order ss exists.

(b) If s≡1(mod8)s \equiv1 \pmod{8} and if there is a prime congruent to 3 (mod8)\pmod{8} dividing the square-free part of s+1s + 1, then no nearly 3-gon of order ss exists.

We observe that part of this result can be proved via the theory of weighing matrices, thus giving an alternative and shorter proof of [17 Theorem 5.2]. A weighing matrix of order tt and weight ww is a matrix WW with entries in {−1,0,1}\{-1, 0, 1\} such that WWT=wItWW^{\mathsf{T}} = wI_t. The absolute matrix abs⁡A\operatorname{abs} A of a {−1,0,1}\{-1, 0, 1\}-matrix A=(ai,j)A = (a_{i,j}) is the matrix (ai,j2)(a_{i,j}^2). A weighing matrix WW is a balanced weighing matrix with parameters (k,λ)(k, \lambda) if

(abs⁡W)(abs⁡W)T=(k−λ)I+λJ.(\operatorname{abs} W)(\operatorname{abs} W)^{\mathsf{T}} = (k - \lambda)I + \lambda J.

Indeed, this is equivalent to abs⁡W\operatorname{abs} W being the incidence matrix of a symmetric balanced incomplete block design.

Theorem 2.2. A regular antipodal plane of order ss is equivalent to a balanced weighing matrix with k=s+1k=s+1 and λ=2\lambda=2.

Proof. First suppose that A\mathcal{A} is a regular antipodal plane of order ss. Let P↦P∗P \mapsto P^* be the antipodal involution on points, and ℓ↦ℓ∗\ell\mapsto\ell^* the antipodal involution on lines. Thus ∣P∣=∣L∣=s2+s+2|\mathcal{P}|=|\mathcal{L}|=s^2+s+2, and every point-pair {P,P∗}\{P,P^*\} and every line-pair {ℓ,ℓ∗}\{\ell,\ell^*\} has size 2. Hence there are v=s2+s+22v=\frac{s^2+s+2}{2} point-pairs and the same number of line-pairs. Choose one representative PiP_i from each point-pair and one representative ℓa\ell_a from each line-pair. Define a v×vv \times v matrix WW, with rows indexed by line-pairs and columns indexed by point-pairs, by

Wai={1,if Pi∈ℓa,−1,if Pi∗∈ℓa,0,if neither Pi nor Pi∗ lies on ℓa.W_{ai} = \begin{cases} 1, & \text{if } P_i \in\ell_a,\\ -1, & \text{if } P_i^* \in\ell_a,\\ 0, & \text{if neither } P_i \text{ nor } P_i^* \text{ lies on } \ell_a. \end{cases}

A line contains exactly s+1s+1 points, no two of which are antipodal, so each row of WW has exactly s+1s+1 nonzero entries.

We claim that distinct rows of WW are orthogonal. Let ℓ\ell and mm be representatives of two distinct line-pairs. By regularity, ℓ\ell meets both mm and m∗m^* in exactly one point. Write ℓ∩m={P}\ell\cap m=\{P\} and ℓ∩m∗={Q}\ell\cap m^*=\{Q\}. Then the corresponding two point-pairs {P,P∗}\{P,P^*\} and {Q,Q∗}\{Q,Q^*\} are distinct. In the column corresponding to {P,P∗}\{P,P^*\}, the two rows have the same sign, since both ℓ\ell and mm contain the same point PP. Hence this column contributes +1+1 to the row inner product. In the column corresponding to {Q,Q∗}\{Q,Q^*\}, the row for ℓ\ell contains QQ, whereas the row for mm contains Q∗Q^*, because m∗m^* contains QQ. Hence this column contributes −1-1. All other columns contribute 0. Therefore the inner product of the two rows is 1−1=01-1=0. Thus

WWT=(s+1)Iv.WW^{\mathsf T}=(s+1)I_v.

Now let B:=abs⁡WB:=\operatorname{abs} W. Each row of BB has size s+1s+1. Moreover, two distinct line-pairs meet in exactly two point-pairs, namely the point-pairs containing ℓ∩m\ell\cap m and ℓ∩m∗\ell\cap m^*. Hence

BBT=(s+1)Iv+2(Jv−Iv)=(s−1)Iv+2Jv.BB^{\mathsf T}=(s+1)I_v+2(J_v-I_v)=(s-1)I_v+2J_v.

Equivalently, BB is the incidence matrix of a symmetric 22-(v,s+1,2)(v,s+1,2) design; a biplane. Therefore WW is a balanced weighing matrix with k=s+1k=s+1 and λ=2\lambda=2.

Conversely, suppose that WW is a balanced weighing matrix with parameters (s+1,2)(s+1,2). Thus WWT=(s+1)IvWW^{\mathsf T}=(s+1)I_v, and B=abs⁡WB=\operatorname{abs} W is the incidence matrix of a biplane. The equation λ(v−1)=k(k−1)\lambda(v-1)=k(k-1) for symmetric designs gives 2(v−1)=(s+1)s2(v-1)=(s+1)s, so 2v=s2+s+22v=s^2+s+2. We construct an antipodal plane. For each column ii of WW, introduce two points Pi+P_i^+ and Pi−P_i^-, and declare them antipodal. For each row aa, introduce two lines ℓa+\ell_a^+ and ℓa−\ell_a^-, and declare them antipodal. Define incidence by

Piϵ∈ℓaδ  ⟺  Wai=δϵ,ϵ,δ∈{±1}.P_i^\epsilon\in\ell_a^\delta\iff W_{ai}=\delta\epsilon,\qquad\epsilon,\delta\in\{\pm1\}.

Thus if Wai=0W_{ai}=0, neither Pi+P_i^+ nor Pi−P_i^- lies on either ℓa+\ell_a^+ or ℓa−\ell_a^-; while if Wai≠0W_{ai}\ne0, each of ℓa+\ell_a^+ and ℓa−\ell_a^- contains exactly one point from the antipodal pair {Pi+,Pi−}\{P_i^+,P_i^-\}. Since each row of WW has exactly s+1s+1 nonzero entries, each line contains s+1s+1 points. Similarly, since WW is square and WWT=(s+1)IvWW^{\mathsf T}=(s+1)I_v, we also have WTW=(s+1)IvW^{\mathsf T}W=(s+1)I_v, so each column has s+1s+1 nonzero entries; hence each point lies on s+1s+1 lines. The total number of points and lines is 2v=s2+s+22v=s^2+s+2. It remains to check the partial linear space condition and the antipodal property. The two points Pi+P_i^+ and Pi−P_i^- are not collinear, because every line contains at most one of them by construction. Now take two non-antipodal points PiϵP_i^\epsilon and PjηP_j^\eta, with i≠ji\ne j. Since BB is a symmetric 22-(v,s+1,2)(v,s+1,2) design, the two columns ii and jj have common support in exactly two rows, say aa and bb. Since WTW=(s+1)IvW^{\mathsf T}W=(s+1)I_v, distinct columns of WW are orthogonal, so

WaiWaj+WbiWbj=0.W_{ai}W_{aj}+W_{bi}W_{bj}=0.

Thus one of these two products is +1+1, and the other is −1-1. Therefore exactly one of the two rows, say aa, satisfies

WaiWaj=ϵη.W_{ai}W_{aj}=\epsilon\eta.

For this row there is a unique choice of sign δ∈{±1}\delta\in\{\pm1\} such that

Wai=δϵ,Waj=δη.W_{ai}=\delta\epsilon,\qquad W_{aj}=\delta\eta.

Hence PiεP_i^\varepsilon and PjηP_j^\eta lie on the unique line ℓaδ\ell_a^\delta. Therefore any two non-antipodal points are joined by exactly one line, while antipodal points are joined by no line. This is precisely a regular antipodal plane of order ss.

Finally, the two constructions are inverse up to the choices of representatives. Changing the representative of a point-pair multiplies the corresponding column of WW by −1-1, and changing the representative of a line-pair multiplies the corresponding row by −1-1. Thus the equivalence is between regular antipodal planes of order ss and balanced weighing matrices with parameters k=s+1k=s+1, λ=2\lambda=2, up to the usual row and column sign changes and permutations.

Corollary 2.3. If a regular antipodal plane exists of order s≡0,3(mod4)s \equiv0,3 \pmod{4}, then s+1s+1 is a square.

Proof. Let v:=12(s2+s+2)v:=\frac{1}{2}(s^2+s+2), the order of WW. Now

det⁡(WWT)=det⁡(W)2=(s+1)v.\det(WW^{\mathsf T})=\det(W)^2=(s+1)^v.

So (s+1)v(s+1)^v is a square. Hence, if vv is odd, then s+1s+1 is a square. Note that vv is odd precisely when s≡0,3(mod4)s\equiv0,3\pmod{4}.

Before we show a unified approach to showing that certain families of weighing matrices do not exist, we address an observation by Mullin [16]. He lists necessary conditions for the existence of a balanced weighing matrix with parameters (k,λ)(k,\lambda). The last one is attributed to Raghavarao [18], which we reproduce below. However, Raghavarao (in Section 4) does not explicitly state Mullin’s general condition (iv). He proves the ‘W(N,N−1)W(N,N-1) case’, and his proof immediately extends to general kk.

Let X:=BWTX:=BW^{\mathsf T} and r=s+1r=s+1. Since det⁡(XXT)=rv+2(r−2)v−1\det(XX^{\mathsf T})=r^{v+2}(r-2)^{v-1} is a square, we recover the biplane and weighing matrix conditions on rr and r−2r-2 in one elegant form. Set G:=XXT=r(r−2)I+2rJG:=XX^{\mathsf T}=r(r-2)I+2rJ. Since XX is an integral nonsingular matrix, det⁡(G)=(det⁡X)2\det(G)=(\det X)^2 is a square. The eigenvalues of GG are r3r^3 with multiplicity 1, and r(r−2)r(r-2) with multiplicity v−1v-1. Hence

det⁡(G)=r3{r(r−2)}v−1=rv+2(r−2)v−1.\det(G)=r^3\{r(r-2)\}^{v-1}=r^{v+2}(r-2)^{v-1}.

Therefore rv+2(r−2)v−1r^{v+2}(r-2)^{v-1} is a square. It follows that

{r is a square,v odd,r−2 is a square,v even.\begin{cases} r\text{ is a square}, & v\text{ odd},\\ r-2\text{ is a square}, & v\text{ even}. \end{cases}

In particular, rr cannot be congruent to 5 or 7 modulo 8.

We now derive Raghavarao’s condition using the Hasse-Minkowski theorem. Let pp be an odd prime, and xx and yy rational numbers. The Hilbert symbol (x,y)p(x,y)_p is defined as follows (see [22 §III.1.2, Theorem 1]). Let α\alpha and β\beta be the pp-adic valuations of xx and yy respectively, and write x=pαux=p^\alpha u and y=pβvy=p^\beta v. Then

(x,y)p=(−1)αβp−12(up)β(vp)α,(x,y)_p=(-1)^{\alpha\beta\frac{p-1}{2}}\left(\frac{u}{p}\right)^\beta\left(\frac{v}{p}\right)^\alpha,

where (up)\left(\frac{u}{p}\right) and (vp)\left(\frac{v}{p}\right) are Legendre symbols. From [22 §IV.3.3], one can derive the following version of the Hasse-Minkowski theorem.

Theorem 2.4 (Hasse-Minkowski). Let A=diag⁡(a1,…,an)A=\operatorname{diag}(a_1,\ldots,a_n) and B=diag⁡(b1,…,bn)B=\operatorname{diag}(b_1,\ldots,b_n) be rational invertible matrices. Then AA and BB are congruent over Q\mathbb{Q} (i.e. B=PAPTB=PAP^{\mathsf T} for some P∈GL⁡(n,Q)P\in\operatorname{GL}(n,\mathbb{Q})) if and only if the following conditions hold:

(1) AA and BB have the same number of positive entries,

(2) the discriminants ∏i=1nai\prod_{i=1}^{n}a_i and ∏i=1nbi\prod_{i=1}^{n}b_i belong to the same coset of Q×/(Q×)2\mathbb{Q}^{\times}/(\mathbb{Q}^{\times})^2,

(3) for each odd prime pp,

∏i<j(ai,aj)p=∏i<j(bi,bj)p.\prod_{i<j}(a_i,a_j)_p=\prod_{i<j}(b_i,b_j)_p.

If a regular antipodal plane of order s=r−1s=r-1 exists, then WIvWT=rIvWI_vW^{\mathsf T}=rI_v, so IvI_v and rIvrI_v must be congruent rational matrices. If we apply the above version of the Hasse-Minkowski theorem with A=IvA=I_v and B=rIvB=rI_v, then (1) trivially holds, (2) requires that rvr^v is square, which holds because either

rr is square or vv is even, and (3) requires that (r,r)p(v2)=1(r,r)_p^{\binom{v}{2}}=1 for all odd primes pp. It is easy to see from the definition of the Hilbert symbol that (r,r)p=(−1)αp2−12(r,r)_p=(-1)^{\alpha\frac{p^2-1}{2}} with α\alpha the pp-adic valuation of rr. Thus, the only new condition on rr that we find, happens when (v2)\binom{v}{2} is odd – that is rr equivalent to 2 or 4 modulo 8 (since we already excluded 5 and 7) – and p≡3p\equiv3 modulo 4. In that case, pp must divide rr an even number of times. If r≡4r\equiv4 modulo 8, then we already know that rr must be square, so this trivially holds. Thus, we obtain the following theorem.

Theorem 2.5. If r≡2r\equiv2 modulo 8, and a regular antipodal plane of order r−1r-1 exists, then the square-free part of rr has no prime divisors congruent to 3 modulo 4.

If s≡1s\equiv1 (mod 8), then v=(s2+s+2)/2≡2v=(s^2+s+2)/2\equiv2 (mod 4). Taking r=s+1r=s+1, the preceding theorem shows that no prime congruent to 3 (mod 8) divides the square-free part of s+1s+1. This recovers [17 Theorem 5.2].

We summarise the above results, including the Bruck-Ryser-Chowla Theorem applied to the biplane arising from a regular antipodal plane of order ss, in the theorem below. Together with the known examples for s=2,3s=2,3, it summarises the classical arithmetic restrictions on the orders of antipodal planes. We point out that s=5s=5 was ruled out in [20], and cyclic1 regular antipodal planes do not exist for 4≤s≤4014\leq s\leq401 (see [17 p. 280]). Indeed, a cyclic antipodal plane is equivalent to a (k2−k+2,k)(k^2-k+2,k)-modular Golomb ruler where k=s+1k=s+1 (see [8 Section III]), and Gordon states that they do not exist for k≤1010k\leq10^{10}.

Theorem 2.6. Let ss be the order of a regular antipodal plane. Then one of the following holds:

  • (i) s≡1s\equiv1 (mod 8), s−1s-1 is a square, no prime congruent to 3 (mod 4) divides the square-free part of s+1s+1;

  • (ii) s≡2,5s\equiv2,5 (mod 8) and s−1s-1 is a square, and s≠5s\ne5;

  • (iii) s≡0,7s\equiv0,7 (mod 8) and s+1s+1 is a square;

  • (iv) s≡3s\equiv3 (mod 8) and s+1s+1 is a square and no prime congruent to 7 (mod 8) divides the square-free part of s−1s-1.

In the next section, we will give new conditions that rule out certain orders, and give some information on the substructure of biplanes that give rise to antipodal planes.

Biplanes

Recall that a biplane is a symmetric 2−(v,k,2)2-(v,k,2) design. There are only finitely many parameters for which we know that a biplane exists, and there are only 17 examples (up to isomorphism) known, including the complete 2−(4,3,2)2-(4,3,2) design, and they have been classified for k≤11k\leq11 [10]. The known biplanes have k∈{3,4,5,6,9,11,13}k\in\{3,4,5,6,9,11,13\}. For the purposes of regular antipodal planes, the possible known biplanes arising can only have k∈{3,4,6,9,11}k\in\{3,4,6,9,11\} (see Corollary 2.3). The cases k=3,4k=3,4 exist, and we can rule out k=5k=5 a number of ways.

A signing of a biplane B\mathcal{B} is a function σ:Flag⁡(B)→{±1}\sigma:\operatorname{Flag}(\mathcal{B})\to\{\pm1\}, extended by σ(L,Q)=0\sigma(L,Q)=0 for non-flags, yielding a matrix Wσ∈{−1,0,1}L×PW_\sigma\in\{-1,0,1\}^{\mathcal{L}\times\mathcal{P}}. The signing is a weighting signing if Wσ(Wσ)T=kIvW_\sigma(W_\sigma)^{\mathsf{T}}=kI_v.

Moorehouse [15] studied the reconstruction of projective planes from homology semiplanes, reducing the choices in the double cover of the nonfixed part to linear equations over F2\mathbb{F}_2. The lemma below applies the same formulation to biplanes.

Lemma 2.7. Write σ=(−1)x\sigma=(-1)^x for x:Flag⁡(B)→F2x:\operatorname{Flag}(\mathcal{B})\to\mathbb{F}_2. Then σ\sigma is a weighing signing if and only if xx satisfies, for every unordered pair {L1,L2}\{L_1,L_2\} of distinct lines, meeting in two points P1P_1 and P2P_2,

x(L1,P1)+x(L2,P1)+x(L1,P2)+x(L2,P2)≡1(mod2).(1)x(L_1,P_1)+x(L_2,P_1)+x(L_1,P_2)+x(L_2,P_2)\equiv1 \pmod2. \tag*{(1)}

Proof. Each row of WσW_\sigma has exactly kk nonzero entries, all ±1\pm1, so each diagonal entry of (Wσ(Wσ)T)(W_\sigma(W_\sigma)^{\mathsf{T}}) is equal to kk. For distinct lines L1,L2L_1,L_2, meeting in points P1P_1 and P2P_2,

(Wσ(Wσ)T)[L1,L2]=∑Q∈L1∩L2σ(L1,Q)σ(L2,Q)=σ(L1,P1)σ(L2,P1)+σ(L1,P2)σ(L2,P2).(W_\sigma(W_\sigma)^{\mathsf{T}})[L_1,L_2]=\sum_{Q\in L_1\cap L_2}\sigma(L_1,Q)\sigma(L_2,Q)=\sigma(L_1,P_1)\sigma(L_2,P_1)+\sigma(L_1,P_2)\sigma(L_2,P_2).

Both summands lie in {±1}\{\pm1\}, so the sum vanishes if and only if the summands are opposite signs, that is,

σ(L1,P1)σ(L2,P1)σ(L1,P2)σ(L2,P2)=−1.\sigma(L_1,P_1)\sigma(L_2,P_1)\sigma(L_1,P_2)\sigma(L_2,P_2)=-1.

Substituting σ=(−1)x\sigma=(-1)^x gives exactly (1). □

It is known via a result of [25] that there is no regular antipodal plane of order 8, but only once we establish a connection to equidistant permutation arrays in the next section. We show that we can use biplanes to establish this result.

Theorem 2.8. There is no regular antipodal plane of order 8 or 10.

Proof. If such a regular antipodal plane exists, then its antipodal quotient is a biplane of order 7 or 9 admitting a weighing signing. Let B\mathcal{B} be such a biplane, and let Γ\Gamma be its bipartite incidence graph. By Lemma 2.7, a weighing signing is equivalent to a function x:Flag⁡(B)→F2x:\operatorname{Flag}(\mathcal{B})\to\mathbb{F}_2 such that, for every pair of distinct lines L1,L2L_1,L_2, meeting in the two points P1,P2P_1,P_2,

x(L1,P1)+x(L2,P1)+x(L1,P2)+x(L2,P2)≡1(mod2).x(L_1,P_1)+x(L_2,P_1)+x(L_1,P_2)+x(L_2,P_2)\equiv1\pmod{2}.

Thus we need to decide whether this affine system over F2\mathbb{F}_2 is soluble.

Take the flags of B\mathcal{B}, equivalently the edges EE of Γ\Gamma, together with a new symbol ∞\infty. Let WW be the F2\mathbb{F}_2-vector space with basis E∪{∞}E\cup\{\infty\}. For each pair of distinct lines L1,L2L_1,L_2, meeting in P1,P2P_1,P_2, let eije_{ij} denote the edge (Li,Pj)(L_i,P_j) of Γ\Gamma, and form the vector

e11+e21+e12+e22+∞.e_{11}+e_{21}+e_{12}+e_{22}+\infty.

Let UU be the subspace of WW generated by all such vectors. The affine system above is soluble if and only if ∞∉U\infty\notin U. Indeed, a solution xx defines a linear functional φ:W→F2\varphi:W\to\mathbb{F}_2 by

φ(e)=x(e)(e∈E),φ(∞)=1,\varphi(e)=x(e)\quad(e\in E),\qquad\varphi(\infty)=1,

and the equations say exactly that φ\varphi vanishes on the generators of UU. Hence φ\varphi vanishes on UU, so ∞∉U\infty\notin U. Conversely, if ∞∉U\infty\notin U, then there is a linear functional φ:W→F2\varphi:W\to\mathbb{F}_2 vanishing on UU but with φ(∞)=1\varphi(\infty)=1; restricting φ\varphi to EE gives a solution of the system.

For each biplane of order 7 and each biplane of order 9, we constructed the corresponding subspace UU and row-reduced over F2\mathbb{F}_2. In every case the vector ∞\infty lies in UU. Therefore the system from Lemma 2.7 has no solution, and hence no such biplane admits a weighing signing. Consequently no regular antipodal plane of order 8 or 10 exists. □

If a regular antipodal plane of order ss exists, where 2≤s≤142\leq s\leq14, then Theorem 2.6 leaves only 2, 3, 8, 10 in that interval; Theorem 2.8 removes 8, 10. So we have:

Corollary 2.9. A regular antipodal plane of order 2≤s≤142\leq s\leq14 exists if and only if s∈{2,3}s\in\{2,3\}.

Question 2.10. Does every finite K2,3K_{2,3}-free bipartite graph occur as a subgraph of the incidence graph of some finite biplane?

All subgraphs of the incidence graph of a biplane are K2,3K_{2,3}-free. As of the writing of this paper, there is no finite K2,3K_{2,3}-free bipartite graph that has been shown to not be a subgraph of any incidence graph of a finite biplane.

However, for a biplane that is the quotient of an antipodal plane, the linear system constraint does forbid many subgraphs. Below we give all of the minimal forbidden K2,3K_{2,3}-free graphs on at most 16 vertices, as well as a picture of the unique smallest one on 11 vertices, with 5 points and 6 lines (Figure 2). For brevity, they are given as sets of lines of an incidence structure with vv points. Note that from the point of view of incidence geometry, both the given configurations and their duals are forbidden.

Figure 2. A minimal forbidden K2,3K_{2,3}-free graph on 11 vertices: 5 points and 6 lines.

The known biplanes up to duality in Table 2.2 are denoted by bib_i where i=k−2i=k-2, also known as the order of the biplane. When there is more than one nonisomorphic example, the letters A,B,C,…A,B,C,\ldots are appended to distinguish them. The correspond in the literature as follows: b4A,b4B,b4Cb4_A,b4_B,b4_C correspond to B6,B7,B8B_6,B_7,B_8 in [2], b7A,b7B,b7Cb7_A,b7_B,b7_C correspond to BH(9),BL(9),Bd(9)B_H(9),B_L(9),B_d(9) in [19], respectively. The biplanes b9A,b9B,b9C,b9D,b9Eb9_A,b9_B,b9_C,b9_D,b9_E correspond to B1,B2,B4,B3,B5B_1,B_2,B_4,B_3,B_5 in [10], respectively. All the planes except order 11 can be downloaded from [9]. The known biplane of order 11 can be found in [1].

vvAut. groupC1C_1C2C_2C3C_3C4C_4C5C_5C6C_6C7C_7C8C_8C9C_9C10C_{10}C11C_{11}C12C_{12}C13C_{13}C14C_{14}C15C_{15}C16C_{16}
b1b_14S4S_4
b2b_27PSL⁡(3,2)\operatorname{PSL}(3,2)
b3b_311PSL⁡(2,11)\operatorname{PSL}(2,11)×××
b4Ab_{4A}1624:S62^4:S_6×
b4Bb_{4B}1625⋅S42^5\cdot S_4××××
b4Cb_{4C}1621+4:A42^{1+4}:A_4××××
b7Ab_{7A}37PΓL⁡(2,8)\operatorname{P\Gamma L}(2,8)××××××××××
b7Bb_{7B}37C32:C6C_3^2:C_6××××××××××××××
b7Cb_{7C}37C37:C9C_{37}:C_9××××××××××
b9Ab_{9A}56PSL⁡(3,4):C22\operatorname{PSL}(3,4):C_2^2×
b9Bb_{9B}56C2×(C32:SD16)C_2\times(C_3^2:SD_{16})×××××××××××××××
b9Cb_{9C}56(C2×SD16):C2(C_2\times SD_{16}):C_2××××××××××××××××
b9Db_{9D}56C32:SD16C_3^2:SD_{16}××××××××××××××
b9Eb_{9E}56C2×A4C_2\times A_4××××××××××××××××
b11b_{11}79AGL⁡(1,11)\operatorname{AGL}(1,11)××××××××××××

Table 1. Each row denotes a known biplane, up to duality. Each CiC_i is a possible minimal obstruction to a signing, and a × denotes an occurrence in the relevant biplane. We have listed the automorphism groups of the biplanes here, for easier identification.

ConfigurationForbidden configurations
C1C_1{1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {2,4,5}, {3,4,5}\{1,2,4\},\ \{1,2,5\},\ \{1,3,4\},\ \{1,3,5\},\ \{2,4,5\},\ \{3,4,5\}
C2C_2{1,2,5}, {1,3,4}, {1,3,5}, {2,3,5}, {2,3,6}, {3,4,6}, {1,2,4,6}\{1,2,5\},\ \{1,3,4\},\ \{1,3,5\},\ \{2,3,5\},\ \{2,3,6\},\ \{3,4,6\},\ \{1,2,4,6\}
C3C_3{1,2,5}, {1,2,6}, {1,3,5}, {1,3,6}, {2,4,5}, {2,4,6}, {3,4,5,6}\{1,2,5\},\ \{1,2,6\},\ \{1,3,5\},\ \{1,3,6\},\ \{2,4,5\},\ \{2,4,6\},\ \{3,4,5,6\}
C4C_4{1,2,4}, {1,3,4}, {4,5,6}, {4,5,7}, {1,2,5,6}, {1,3,5,7}, {2,3,4,6,7}\{1,2,4\},\ \{1,3,4\},\ \{4,5,6\},\ \{4,5,7\},\ \{1,2,5,6\},\ \{1,3,5,7\},\ \{2,3,4,6,7\}
C5C_5{1,4,5}, {1,4,6}, {2,3,4}, {2,3,5}, {2,4,5}, {3,5,7}, {1,5,6,7}, {3,4,6,7}\{1,4,5\},\ \{1,4,6\},\ \{2,3,4\},\ \{2,3,5\},\ \{2,4,5\},\ \{3,5,7\},\ \{1,5,6,7\},\ \{3,4,6,7\}
C6C_6{1,3,4}, {1,4,5}, {2,3,4}, {2,4,5}, {2,5,7}, {5,6,7}, {1,3,5,6}, {2,3,6,7}\{1,3,4\},\ \{1,4,5\},\ \{2,3,4\},\ \{2,4,5\},\ \{2,5,7\},\ \{5,6,7\},\ \{1,3,5,6\},\ \{2,3,6,7\}
C7C_7{1,3,4}, {1,3,5}, {1,4,5}, {2,3,5}, {2,5,7}, {2,6,7}, {2,3,4,6}, {4,5,6,7}\{1,3,4\},\ \{1,3,5\},\ \{1,4,5\},\ \{2,3,5\},\ \{2,5,7\},\ \{2,6,7\},\ \{2,3,4,6\},\ \{4,5,6,7\}
C8C_8{1,2,5}, {1,3,5}, {2,4,5}, {3,4,6}, {4,5,7}, {4,6,7}, {1,2,3,4}, {3,5,6,7}\{1,2,5\},\ \{1,3,5\},\ \{2,4,5\},\ \{3,4,6\},\ \{4,5,7\},\ \{4,6,7\},\ \{1,2,3,4\},\ \{3,5,6,7\}
C9C_9{1,2,5}, {1,4,5}, {2,5,7}, {3,4,5}, {3,4,6}, {3,5,7}, {1,2,4,6}, {2,3,6,7}\{1,2,5\},\ \{1,4,5\},\ \{2,5,7\},\ \{3,4,5\},\ \{3,4,6\},\ \{3,5,7\},\ \{1,2,4,6\},\ \{2,3,6,7\}
C10C_{10}{1,2,5}, {1,3,5}, {2,4,6}, {2,5,6}, {3,4,7}, {3,5,7}, {1,2,3,4}, {4,5,6,7}\{1,2,5\},\ \{1,3,5\},\ \{2,4,6\},\ \{2,5,6\},\ \{3,4,7\},\ \{3,5,7\},\ \{1,2,3,4\},\ \{4,5,6,7\}
C11C_{11}{1,2,3}, {1,2,4}, {1,3,4}, {2,4,6}, {3,4,7}, {4,5,6}, {4,5,7}, {2,3,5,6,7}\{1,2,3\},\ \{1,2,4\},\ \{1,3,4\},\ \{2,4,6\},\ \{3,4,7\},\ \{4,5,6\},\ \{4,5,7\},\ \{2,3,5,6,7\}
C12C_{12}{1,3,4}, {1,3,7}, {1,4,5}, {2,3,4}, {2,3,7}, {2,4,6}, {4,5,6}, {1,2,5,6,7}\{1,3,4\},\ \{1,3,7\},\ \{1,4,5\},\ \{2,3,4\},\ \{2,3,7\},\ \{2,4,6\},\ \{4,5,6\},\ \{1,2,5,6,7\}
C13C_{13}{1,3,4}, {1,3,6}, {1,4,7}, {2,3,4}, {2,4,7}, {2,5,7}, {1,5,6,7}, {2,3,5,6}\{1,3,4\},\ \{1,3,6\},\ \{1,4,7\},\ \{2,3,4\},\ \{2,4,7\},\ \{2,5,7\},\ \{1,5,6,7\},\ \{2,3,5,6\}
C14C_{14}{1,3,5}, {1,6,7}, {2,3,4}, {2,3,5}, {2,4,7}, {4,6,7}, {1,2,5,7}, {1,3,4,6}\{1,3,5\},\ \{1,6,7\},\ \{2,3,4\},\ \{2,3,5\},\ \{2,4,7\},\ \{4,6,7\},\ \{1,2,5,7\},\ \{1,3,4,6\}
C15C_{15}{1,2,5}, {1,3,5}, {2,4,5}, {3,5,6}, {4,5,7}, {5,6,7}, {1,2,3,4}, {3,4,6,7}\{1,2,5\},\ \{1,3,5\},\ \{2,4,5\},\ \{3,5,6\},\ \{4,5,7\},\ \{5,6,7\},\ \{1,2,3,4\},\ \{3,4,6,7\}
C16C_{16}{1,2,3}, {1,2,6}, {1,3,5}, {1,4,5}, {1,4,6}, {2,3,4}, {2,4,5}, {2,5,6}, {3,4,6}, {3,5,6}\{1,2,3\},\ \{1,2,6\},\ \{1,3,5\},\ \{1,4,5\},\ \{1,4,6\},\ \{2,3,4\},\ \{2,4,5\},\ \{2,5,6\},\ \{3,4,6\},\ \{3,5,6\}

Table 2. Forbidden configurations.

This list was found in two ways, by first using Brendan McKay’s graph generation program geng [13] and independently by examining the subconfigurations of the known biplanes using GAP. Both lists were found to be equal. In each configuration, the system described in Lemma 2.7 is inconsistent, in particular the sum of all of the corresponding equations equals 1.

Proposition 2.11. Let BB be a biplane. If Aut⁡(B)\operatorname{Aut}(B) contains a subgroup GG of odd order acting transitively on Flag⁡(B)\operatorname{Flag}(B), then BB admits no weighing signing.

Proof. Consider the F2\mathbb{F}_2-matrix MM of the linear system given by (1), that is the columns of MM are indexed by the flags of BB, and for any pair of lines {L1,L2}\{L_1,L_2\} with common points {P1,P2}\{P_1,P_2\}, MM has a row with ones exactly in positions (P1,L1)(P_1,L_1), (P1,L2)(P_1,L_2), (P2,L1)(P_2,L_1), (P2,L2)(P_2,L_2). A weighing signing of BB corresponds to a vector xx with Mx=1Mx=1. Note that GG naturally acts on F2Flag⁡(B)\mathbb{F}_2^{\operatorname{Flag}(B)}, and Mxg=1Mx^g=1 for each g∈Gg\in G. Define xˉ=∑g∈Gxg\bar{x}=\sum_{g\in G}x^g. Then Mxˉ=∣G∣1=1M\bar{x}=|G|1=1. On the other hand, by the transitivity of GG on Flag⁡(B)\operatorname{Flag}(B), xˉ\bar{x} must be constant, that is xˉ=a1\bar{x}=a1 for some a∈F2a\in\mathbb{F}_2. But then Mxˉ=aM1=0M\bar{x}=aM1=0, because every row of MM has four ones. This yields a contradiction. □

The only known biplanes satisfying the hypothesis of Proposition 2.11 are (i) the unique biplane on 11 points (k=5k=5, s=4s=4) (admitting C11:C5≤PSL⁡(2,11)C_{11}:C_5\leq\operatorname{PSL}(2,11)), and (ii) a biplane on 37 points (k=9k=9, s=8s=8) admitting C37:C9C_{37}:C_9. Another way to constrain the construction of future examples is to use information about the F2\mathbb{F}_2-rank of a putative example:

Proposition 2.12. Let DD be a biplane admitting a weighing signing, with block size kk, and let v=1+(k2)v=1+\binom{k}{2}. If kk is even, then the incidence matrix BB of DD satisfies

rank⁡F2B=⌊v2⌋.(2)\operatorname{rank}_{\mathbb{F}_2} B=\left\lfloor\frac{v}{2}\right\rfloor. \tag*{(2)}

Proof. Let WW be a weighing signing of BB, and let NN be the negative support of WW; thus

Nij=1⟺Wij=−1,W=B−2N.N_{ij}=1\Longleftrightarrow W_{ij}=-1,\qquad W=B-2N.

Expanding WWT=kIWW^{\mathsf{T}}=kI and using BBT=BTB=(k−2)I+2JBB^{\mathsf{T}}=B^{\mathsf{T}}B=(k-2)I+2J, we obtain

BNT+NBT−2NNT=J−I.BN^{\mathsf{T}}+NB^{\mathsf{T}}-2NN^{\mathsf{T}}=J-I.

Reducing modulo 2 gives BNT+NBT=I+JBN^{\mathsf{T}}+NB^{\mathsf{T}}=I+J. All ranks are over F2\mathbb{F}_2. Let r:=rank⁡Br:=\operatorname{rank}B. Then

2⌊v2⌋=rank⁡(I+J)≤rank⁡(BNT)+rank⁡(NBT)≤2r.2\left\lfloor\frac{v}{2}\right\rfloor=\operatorname{rank}(I+J)\leq\operatorname{rank}(BN^{\mathsf{T}})+\operatorname{rank}(NB^{\mathsf{T}})\leq2r.

Since kk is even, the relation BBT=BTB=(k−2)I+2JBB^{\mathsf{T}}=B^{\mathsf{T}}B=(k-2)I+2J gives BTB=BBT=0B^{\mathsf{T}}B=BB^{\mathsf{T}}=0. So the row-space of BB is self-orthogonal and hence r≤⌊v2⌋r\leq\left\lfloor\frac{v}{2}\right\rfloor, and equality follows. □

Proposition 2.12 gives us another method to rule out certain regular antipodal planes, when kk is even. For k=6k=6 there are exactly three biplanes. Assmus and Salwach [2] denote them according to the dimensions of their binary incidence codes; we write D6D_6, D7D_7, D8D_8, with rank⁡2B(Di)=i\operatorname{rank}_2 B(D_i)=i. Proposition 2.12 requires rank⁡2v/2=8\operatorname{rank}_2 v/2=8, and so D6D_6 and D7D_7 are not signable. Using standard representatives of the classified biplanes gives the following exact ranks.

Designkkvvrank⁡2B\operatorname{rank}_2 BRequired rank for a weighing signing
D4D_44733
D6D_661668
D7D_761678
D8D_861688

Table 3. Using Proposition 2.12 on some known biplanes.

Thus the exact-rank theorem eliminates two of the three 22–(16,6,2)(16,6,2) biplanes without solving any signing equations. No other known biplane is eliminated with this method.

Sharply deranged sets of permutations

For integers a≤ba \le b, denote {a,…,b}\{a,\ldots,b\} by [a,b][a,b]. Schleiermacher [21 Corollary 5.3] showed that there exists a finite regular antipodal plane of order s≥2s \ge2 if and only if there exists a set Φ\Phi of permutations in Ss+1S_{s+1} satisfying: (i) every element of Φ\Phi has no cycles of length at most 2; (ii) if (a,b)(a,b) and (c,d)(c,d) are two ordered pairs of elements of [1,s+1][1,s+1] such that a≠ba \ne b, c≠dc \ne d, a≠ca \ne c, b≠db \ne d, and (c,d)≠(b,a)(c,d) \ne(b,a), then there exists a unique element g∈Φg \in\Phi such that b=agb=a^g and d=cgd=c^g. We show here that there is a simpler set of permutations that is equivalent to a regular antipodal plane. We call a family F\mathcal{F} of permutations in Ss+1S_{s+1} sharply deranged if

  1. ∣F∣=s(s−1)|\mathcal{F}|=s(s-1),

  2. no element of F\mathcal{F} stabilises a point or pair setwise,

  3. for every g∈Fg \in\mathcal{F}, it holds that g−1∈Fg^{-1} \in\mathcal{F}, and for every f∈F∖{g,g−1}f \in\mathcal{F} \setminus\{g,g^{-1}\}, gf−1gf^{-1} has a unique fixed point.

Proposition 2.13. A regular antipodal plane of order s≥2s \ge2 exists if and only if Ss+1S_{s+1} has a sharply deranged family.

Proof. Suppose that a regular antipodal plane of order ss exists. Take two points PP and P∗P^*. Let ℓ0,…,ℓs\ell_0,\ldots,\ell_s be the lines incident with PP. Then every point Q≠P,P∗Q \ne P,P^* is on a unique line ℓi\ell_i and a unique line ℓj∗\ell_j^*. Moreover, i≠ji \ne j since ℓi\ell_i and ℓj∗\ell_j^* don't intersect. Vice versa, if i≠ji \ne j, then ℓi\ell_i and ℓj∗\ell_j^* intersect in a unique point. We denote this point by (i,j)(i,j). Thus, the set of points of the plane is

([0,s]2∖{(i,i):i∈[0,s]})∪{P,P∗}.\left([0,s]^2 \setminus\{(i,i):i \in[0,s]\}\right) \cup\{P,P^*\}.

Note that (ℓi∩ℓj∗)∗=ℓj∩ℓi∗(\ell_i \cap\ell_j^{*})^*=\ell_j \cap\ell_i^*, hence (i,j)∗=(j,i)(i,j)^*=(j,i).

Now take a line ℓ\ell of the plane, not incident with PP or P∗P^*. Then ℓ\ell intersects each line ℓi\ell_i and ℓi∗\ell_i^* in exactly one point, hence the points of ℓ\ell are of the form {(i,gℓ(i)):i∈[0,s]}\{(i,g_\ell(i)):i \in[0,s]\} for a permutation gℓg_\ell. Note that gℓg_\ell has no fixed points since (i,i)(i,i) is not a point of the plane, and gℓg_\ell does not stabilise a pair {i,j}\{i,j\}, since (i,j)(i,j) and (j,i)=(i,j)∗(j,i)=(i,j)^* cannot both be incident with ℓ\ell. Furthermore, (i,j)(i,j) is incident with ℓ\ell if and only if (i,j)∗=(j,i)(i,j)^*=(j,i) is incident with ℓ∗\ell^*, hence, gℓ∗=gℓ−1g_{\ell^*}=g_\ell^{-1}. The family of permutations gℓg_\ell on [0,s][0,s] is sharply deranged.

Conversely, suppose that Ss+1S_{s+1} is the symmetric group acting on [0,s][0,s], and that F\mathcal{F} is a sharply deranged family. Make an incidence structure with point set

P={P,P∗}∪{(i,j)∈[0,s]2:i≠j},\mathcal{P}=\{P,P^*\}\cup\{(i,j)\in[0,s]^2:i\ne j\},

and line set

L={ℓi:i∈[0,s]}∪{ℓi∗:i∈[0,s]}∪F.\mathcal{L}=\{\ell_i:i\in[0,s]\}\cup\{\ell_i^*:i\in[0,s]\}\cup\mathcal{F}.

The points incident with line ℓ\ell are (i) if ℓ=ℓi\ell=\ell_i: PP and the points (i,j)(i,j) with j∈[0,s]∖{i}j\in[0,s]\setminus\{i\}, (ii) if ℓ=ℓi∗\ell=\ell_i^*: P∗P^* and the points (j,i)(j,i) with j∈[0,s]∖{i}j\in[0,s]\setminus\{i\}, (iii) if ℓ=g∈F\ell=g\in\mathcal{F}: the points (i,g(i))(i,g(i)) with i∈[0,s]i\in[0,s].

It follows that every line is incident with s+1s+1 points, and two distinct lines intersect in at most one point. We show that every point is incident with s+1s+1 lines. There are equally many lines as points, and every line is incident with s+1s+1 points, so on average a point is incident with s+1s+1 lines. Now suppose that some point QQ is incident with more than s+1s+1 lines. Then these lines pairwise intersect in QQ, hence there are at least 1+(s+2)s>s2+s+21+(s+2)s>s^2+s+2 points, which is a contradiction. Therefore, every point must be incident with s+1s+1 lines. This proves that we have constructed a regular antipodal plane. □\square

Example 2.14. For s=2s=2, {(1,2,3),(1,3,2)}\{(1,2,3),(1,3,2)\} is sharply deranged. Likewise, the set of 4-cycles is sharply deranged for s=3s=3. For s=4s=4, you cannot extend a 5-cycle plus its inverse to anything larger.

Suppose F\mathcal{F} is a sharply deranged family of permutations in Ss+1S_{s+1}. For each inverse pair (g,g−1)(g,g^{-1}) in F\mathcal{F}, throw out one of them, which will in total give us a set F′\mathcal{F}' of half the elements of F\mathcal{F}. Now each pair of distinct permutations agree on precisely one point, and hence F′\mathcal{F}' is an equidistant permutation array (EPA). Table 4 compares the clique number of a graph Ωs+1\Omega_{s+1} which we will define below, and the size R(s+1,1)R(s+1,1) of the largest EPA in Ss+1S_{s+1} (see also OEIS:A005677). In particular, Tolonen [25] showed recently that R(9,1)≤20R(9,1)\le20, from which it follows that there is no sharply deranged family of permutations in S9S_9, and hence no regular antipodal plane of order 8. The graph Ωs+1\Omega_{s+1} has vertices the derangements of Ss+1S_{s+1} that do not have 2-cycles. Two permutations g,hg,h are adjacent in Ωs+1\Omega_{s+1} if g=h−1g=h^{-1} or gh−1gh^{-1} fixes a unique element. We computed clique numbers by computer, using the GAP [24] package GRAPE [23].

sss(s−1)s(s-1)ω(Ωs+1)\omega(\Omega_{s+1})s(s−1)/2s(s-1)/2R(s+1,1)R(s+1,1)
36633
412265
520111010
630101513
742142116
856≥20\ge202820

Table 4. Clique numbers and bounds. If a sharply deranged subset of Ss+1S_{s+1} exists, then s(s−1)≤ω(Ωs+1)s(s-1) \le\omega(\Omega_{s+1}) and s(s−1)/2≤R(s+1,1)s(s-1)/2 \le R(s+1,1).

The data in [11] shows that the known EPAs would easily satisfy an upper bound of 14n2+2\frac{1}{4}n^2+2. So based on the numerical evidence, we propose the following conjecture:

Conjecture 2.15. R(n,1)≤14n2+2R(n,1) \le\frac{1}{4}n^2+2 for all n≥3n \ge3.

The best bound on an EPA is by van Rees [26]: n2−4n+O(n)n^2-4n+O(\sqrt{n}). It was shown in [12] that R(n,1)≥12(n−1)(4n−3−1)R(n,1) \ge\frac{1}{2}(n-1)(\sqrt{4n-3}-1) when n=q2+q+1n=q^2+q+1 for some prime-power qq. If Conjecture 2.15 holds, then so too does Payne’s Conjecture. Choosing one element from each inverse pair in a sharply deranged set of Ss+1S_{s+1} yields an EPA of index 1 of size s(s−1)/2s(s-1)/2. If Conjecture 2.15 holds, then 12s(s−1)≤14(s+1)2+2\frac{1}{2}s(s-1) \le\frac{1}{4}(s+1)^2+2, from which it follows that s≤5s \le5. (We have already excluded the cases s=4,5s=4,5).

Mutually orthogonal array-bic squares

Definition 2.16. An array-bic square of order ss and position ii, with 1≤i≤s1 \le i \le s is an s×ss \times s-array AiA_i with the following properties:

(i) The diagonal of AiA_i is empty, the off-diagonal positions in AiA_i contain entries from [0,s]∖{i}[0,s]\setminus\{i\}.

(ii) The iith column of AiA_i has a 0 entry on all off-diagonal positions,

(iii) The yyth column of AiA_i, with y≠iy \ne i, contains each symbol in [1,s]∖{i}[1,s]\setminus\{i\} exactly once.

(iv) The xxth row of AiA_i contains each symbols of [1,s]∖{i,x}[1,s]\setminus\{i,x\} exactly once, and if i≠xi \ne x, it also contains a 0.

Here is an example of an array-bic square of order 4 and position 1:

(⋅2430⋅3404⋅2032⋅)\begin{pmatrix} \cdot& 2 & 4 & 3 \\ 0 & \cdot& 3 & 4 \\ 0 & 4 & \cdot& 2 \\ 0 & 3 & 2 & \cdot \end{pmatrix}

Definition 2.17. Suppose that AiA_i and AkA_k are array-bic squares of order ss and positions ii and kk, respectively, with i≠ki \ne k. We call AiA_i and AkA_k orthogonal if for every tuple (a,b)∈([0,s]∖{i})×([0,s]∖{k})(a,b) \in([0,s]\setminus\{i\})\times([0,s]\setminus\{k\}) other than

(k,i),(c,c) for c∈[0,s]∖{i,k},(k,i), \qquad(c,c) \text{ for } c \in[0,s]\setminus\{i,k\},

there is a unique off-diagonal position (x,y)(x,y) such that

Ai(x,y)=aandAk(x,y)=b.A_i(x,y)=a \qquad\text{and}\qquad A_k(x,y)=b.

(Equivalently, the pairs which do not occur are precisely (k,i)(k,i) and (c,c)(c,c) for c∈[0,s]∖{i,k}c \in[0,s]\setminus\{i,k\}.) Note that this accounts for all s(s−1)s(s-1) off-diagonal positions. Note that if i=ki=k, then there are positions where we find (a,b)=(0,0)(a,b)=(0,0), so AiA_i and AkA_k cannot be orthogonal.

We call Ai1,…,AitA_{i_1},\ldots,A_{i_t} a set of mutually orthogonal array-bic squares, abbreviated MOAS(s,t)(s,t), if they are array-bic squares of order ss, and any pair of them is orthogonal.

Example 2.18. For order 2, there is a unique example of a MOAS(2,2)(2,2):

[⋅20⋅],[⋅01⋅]\begin{bmatrix} \cdot& 2 \\ 0 & \cdot\end{bmatrix},\quad \begin{bmatrix} \cdot& 0 \\ 1 & \cdot\end{bmatrix}

By computer, it is not difficult to show that the unique MOAS(3,3)(3,3) (up to symmetry) is

[⋅320⋅302⋅],[⋅033⋅110⋅],[⋅201⋅021⋅].\begin{bmatrix} \cdot& 3 & 2 \\ 0 & \cdot& 3 \\ 0 & 2 & \cdot \end{bmatrix},\quad \begin{bmatrix} \cdot& 0 & 3 \\ 3 & \cdot& 1 \\ 1 & 0 & \cdot \end{bmatrix},\quad \begin{bmatrix} \cdot& 2 & 0 \\ 1 & \cdot& 0 \\ 2 & 1 & \cdot \end{bmatrix}.

The proof of the following is straightforward from the definitions, but it helps to know this result in efficient computation and enumeration of examples.

Lemma 2.19. Suppose that AiA_i is an array-bic square of order ss and position ii. Consider the natural action of the symmetric group SsS_s on [1,s][1,s], and stipulate that it fixes the symbol 00. Take g∈Ssg \in S_s. Define AigA_i^g by

Aig(x,y)=(Ai(xg−1,yg−1))g.A_i^g(x,y)=\left(A_i(x^{g^{-1}},y^{g^{-1}})\right)^g.

Then AigA_i^g is an array-bic square of order ss and position igi^g. Moreover, two array-bic squares AiA_i and AkA_k are orthogonal if and only if AigA_i^g and AkgA_k^g are orthogonal.

Proposition 2.20. A regular antipodal plane of order ss is equivalent to a MOAS(s,s)(s,s).

Proof. Suppose that (P,L)(\mathcal{P},\mathcal{L}) is a regular antipodal plane of order ss. Choose a line ℓ0∈L\ell_0 \in\mathcal{L}, and label the points of ℓ0\ell_0 as P0,…,PsP_0,\ldots,P_s. For each (i,j)∈[0,s]2(i,j) \in[0,s]^2 with i≠ji \ne j, let ℓij\ell_{ij} be the line containing PiP_i and Pj∗P_j^*. Note that L={ℓ0,ℓ0∗}∪{ℓij:i,j∈[0,s],i≠j}\mathcal{L}=\{\ell_0,\ell_0^*\}\cup\{\ell_{ij}:i,j\in[0,s],i\ne j\}, and ℓij∗=ℓji\ell_{ij}^*=\ell_{ji}. For each (x,y)∈[1,s]2(x,y)\in[1,s]^2 with x≠yx\ne y, we denote the point ℓ0x∩ℓy0\ell_{0x}\cap\ell_{y0} by PxyP_{xy}. Note that Pxy∗=PyxP_{xy}^*=P_{yx}. Define the s×ss\times s arrays A1,…,AsA_1,\ldots,A_s with empty diagonal by Ai(x,y)=jA_i(x,y)=j if the unique line containing PiP_i and PxyP_{xy} is ℓij\ell_{ij}. Using the properties of regular antipodal planes, it is straightforward to verify that each AiA_i is an array-bic square. Suppose by way of contradiction that AiA_i and AkA_k are not orthogonal. If Ai(x,y)=kA_i(x,y)=k and Ak(x,y)=iA_k(x,y)=i, then PxyP_{xy} lies on both ℓik\ell_{ik} and ℓki=ℓik∗\ell_{ki}=\ell_{ik}^*, contradicting their disjointness. So one of the following must occur:

  1. There exists a off-diagonal position (x,y)(x,y) with Ai(x,y)=Ak(x,y)=jA_i(x,y)=A_k(x,y)=j. This means that the line through Pj∗P_j^* and PxyP_{xy} intersects ℓ0\ell_0 in both PiP_i and PkP_k, a contradiction.

  1. There exists two off-diagonal positions (x,y),(x′,y′)(x,y),(x',y') with Ai(x,y)=Ai(x′,y′)=jA_i(x,y)=A_i(x',y')=j and Ak(x,y)=Ak(x′,y′)=hA_k(x,y)=A_k(x',y')=h for some jj and hh. This would mean that the lines ℓij\ell_{ij} and ℓkh\ell_{kh} share the points PxyP_{xy} and Px′y′P_{x'y'}, a contradiction.

We conclude that a regular antipodal plane gives rise to a MOAS(s,s)(s,s).

Conversely, suppose that A1,…,AsA_1,\ldots,A_s is a MOAS(s,s)(s,s), where AiA_i has position ii. Put

X=[0,s],Ω={(x,y)∈[1,s]2:x≠y},X=[0,s],\qquad\Omega=\{(x,y)\in[1,s]^2:x\ne y\},

and define maps f0(x,y)=xf_0(x,y)=x, fi(x,y)=Ai(x,y)f_i(x,y)=A_i(x,y) (for i∈[1,s]i\in[1,s]). Thus fi:Ω→X∖{i}f_i:\Omega\to X\setminus\{i\}. Every fibre of every fif_i has size s−1s-1. Moreover, for distinct i,k∈Xi,k\in X, and for j≠ij\ne i, h≠kh\ne k,

∣{u∈Ω:fi(u)=j, fk(u)=h}∣={0,(j,h)=(k,i) or j=h,1,otherwise.\left|\{u\in\Omega:f_i(u)=j,\ f_k(u)=h\}\right|= \begin{cases} 0, & (j,h)=(k,i)\text{ or }j=h,\\ 1, & \text{otherwise}. \end{cases}

For i,k≠0i,k\ne0, this is precisely the orthogonality of AiA_i and AkA_k. When one of i,ki,k is 00, it follows from the row conditions for an array-bic square.

Now define

P={Pi,Pi∗:i∈X}∪{Pu:u∈Ω}\mathcal{P}=\{P_i,P_i^*:i\in X\}\cup\{P_u:u\in\Omega\}
L={ℓ0,ℓ0∗}∪{ℓij:i,j∈X, i≠j}.\mathcal{L}=\{\ell_0,\ell_0^*\}\cup\{\ell_{ij}:i,j\in X,\ i\ne j\}.

To streamline our notation, we declare ℓ0:={Pi:i∈X}\ell_0:=\{P_i:i\in X\}, ℓ0∗:={Pi∗:i∈X}\ell_0^*:=\{P_i^*:i\in X\}, and

ℓij:={Pi,Pj∗}∪{Pu:fi(u)=j}.\ell_{ij}:=\{P_i,P_j^*\}\cup\{P_u:f_i(u)=j\}.

Since every fibre of fif_i has size s−1s-1, every line has s+1s+1 points. Also, PiP_i lies on ℓ0\ell_0 and the ss lines ℓij\ell_{ij} with j≠ij\ne i, while Pi∗P_i^* lies on ℓ0∗\ell_0^* and the ss lines ℓji\ell_{ji} with j≠ij\ne i. Finally, PuP_u lies on the s+1s+1 lines ℓi,fi(u)\ell_{i,f_i(u)}, where i∈Xi\in X. Hence every point also lies on s+1s+1 lines. It remains to check intersections. The lines ℓ0\ell_0 and ℓ0∗\ell_0^* are disjoint, while ℓij\ell_{ij} meets them in PiP_i and Pj∗P_j^*, respectively. For two distinct lines ℓij\ell_{ij} and ℓkh\ell_{kh}, we have

ℓij∩ℓkh={{Pi},i=k,{Pj∗},j=h,∅,(k,h)=(j,i),{Pu},otherwise.\ell_{ij} \cap\ell_{kh} = \begin{cases} \{P_i\}, & i = k,\\ \{P_j^*\}, & j = h,\\ \varnothing, & (k,h) = (j,i),\\ \{P_u\}, & \text{otherwise}. \end{cases}

where in the last case uu is the unique element satisfying fj(u)=jf_j(u)=j and fk(u)=hf_k(u)=h.

Thus any two lines meet in at most one point, and every line besides the disjoint line, namely ℓ0∗\ell_0^* for ℓ0\ell_0, ℓij\ell_{ij} for ℓij\ell_{ij}. Hence (P,L)(\mathcal{P},\mathcal{L}) is a partial linear space. Since ∣P∣=2(s+1)+s(s−1)=s2+s+2|\mathcal{P}|=2(s+1)+s(s-1)=s^2+s+2, the s+1s+1 lines through any point contain 1+s(s+1)=s2+s+11+s(s+1)=s^2+s+1 points. Therefore every point has a unique non-collinear point. Consequently, (P,L)(\mathcal{P},\mathcal{L}) is a regular antipodal plane of order ss.

Finally, PiP_i and Pi∗P_i^* are non-collinear, so they are antipodal. Moreover, Pxy=ℓ0x∩ℓy0P_{xy}=\ell_{0x}\cap\ell_{y0}, and the line through PiP_i and PxyP_{xy} is ℓi,Ai(xy)\ell_{i,A_i(xy)}. Thus the construction in the forward direction recovers A1,…,AsA_1,\ldots,A_s, completing the equivalence.

By computational depth-first search, there is no MOAS(4, 2). Similarly, we could find a MOAS(5, 2), but a MOAS(5, 3) does not exist, and we could find a MOAS(6, 2), but there is no MOAS(6, 3). There exists a MOAS(7, 2), but a backtrack search with Julia (273 minutes on a MacBook) shows that there is no MOAS(7, 3). This also shows there are no regular antipodal planes for these small orders, and that in some sense, we do not even get close to such a configuration. The Julia code is available upon request from the first author.

A MOAS(5, 2)

Figure 3. A MOAS(5, 2).

A MOAS(6, 2)

Figure 4. A MOAS(6, 2).

A MOAS(7, 2)

Figure 5. A MOAS(7, 2).

Conclusion

We have shown that there are interesting combinatorial objects associated to regular antipodal planes. The first and most well-known object is a biplane, and the existence of an example with more than 79 points is a long-standing open problem in design theory. We have shown that a regular antipodal plane gives rise to an equidistant permutation array of index 1, and we do not yet have good bounds on the size of such an object. Such a bound would resolve Payne’s Conjecture. We also introduced sharply deranged sets and mutually orthogonal array-bic squares, that in some sense capture how improbable it is for a regular antipodal plane to exist, of order greater than 14. This leads us to the following questions arising from this work:

(Q1) Does there exist a regular antipodal plane of order greater than 14? In particular does there exist one of order 15?

(Q2) Is it true that the maximum size R(n,1)R(n,1) of an equidistant permutation array on nn points, and of index 1, is at most 14n2+2\frac{1}{4}n^2+2 for all n≥3n \ge3?

(Q3) Does there exist a MOAS⁡(s,3)\operatorname{MOAS}(s,3) for s>7s > 7?

Acknowledgements

Sam Adriaensen is supported by grant number 12A3Y25N of Research Foundation - Flanders (FWO). He is grateful to the University of Western Australia and John Bamberg in particular for their hospitality during his stay in Perth. Jason Williford was supported in part by the Simons Foundation Collaboration Grant 711898. He thanks the Department of Mathematics at the University of Western Australia, and John Bamberg in particular, for their warm hospitality and for providing a stimulating research environment during his sabbatical visit.

The authors would like to thank Gordon Royle for sharing his adjacency matrices for the known biplanes.

The computer algebra systems Magma [5], GAP [24] and the programming language Julia [3] were used for computations in this paper. (Adriaensen) Department of Mathematics and Data Science, Vrije Universiteit Brussel, Pleinlaan 2, 1050 Elsene, Belgium. Email address: [email protected]

(Bamberg) Department of Mathematics and Statistics, The University of Western Australia, 35 Stirling Highway, Perth, W.A. 6009, Australia. Email address: [email protected]

(Williford) Department of Mathematics and Statistics, University of Wyoming, 1000 E. University Ave., Laramie, WY 82071 USA Email address: [email protected]

References

  1. [1]M. Aschbacher. On collineation groups of symmetric block designs. Journal of Combinatorial Theory, Series A, 11(3):272–281, Nov. 1971.DOI
  2. [2]E. F. Assmus Jr. and C. J. Salwach. The (16, 6, 2) designs. Int. J. Math. Math. Sci., 2:261–281, 1979.
  3. [3]J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah. Julia: A fresh approach to numerical computing. SIAM Review, 59(1):65–98, 2017.arxiv.org/abs/1411.1607
  4. [4]N. L. Biggs and T. Ito. Graphs with even girth and small excess. Math. Proc. Cambridge Philos. Soc., 88(1):1–10, 1980.DOI
  5. [5]W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system i: The user language. Journal of Symbolic Computation, 24(3–4):235–265, Sept. 1997.DOI
  6. [6]M. De Boeck and G. Van de Voorde. Embedded antipodal planes and the minimum weight of the dual code of points and lines in projective planes of order p². Des. Codes Cryptogr., 91(3):895–920, 2023.arxiv.org/abs/2203.16129
  7. [7]P. Dembowski. Finite geometries. Classics in Mathematics. Springer-Verlag, Berlin, 1997. Reprint of the 1968 original.
  8. [8]D. M. Gordon. Modular Golomb Rulers and Almost Difference Sets. IEEE Trans. Inform. Theory, 71(7):5737–5743, 2025.arxiv.org/abs/2408.16721
  9. [9]D. Heinlein, A. Ivanov, B. McKay, and P. R. J. Östergård. A library of combinatorial 2-designs. Zenodo, Aug. 2023. Dataset, version 1.DOI
  10. [10]P. Kaski and P. R. J. Östergård. There are exactly five biplanes with k = 11. J. Comb. Des., 16(2):117–127, 2008.
  11. [11]A. Mahmoodi and P. J. Schellenberg. Equidistant permutation arrays. In The CRC handbook of combinatorial designs, pages 326–329. Boca Raton, FL: CRC Press, 1996.
  12. [12]R. Mathon and S. A. Vanstone. On the existence of doubly resolvable Kirkman systems and equidistant permutation arrays. Discrete Math., 30:157–172, 1980.DOI
  13. [13]B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symbolic Comput., 60:94–112, 2014.
  14. [14]W. Mielants. On nearly generalized 3-gons. Simon Stevin, 50:87–94, 1976.
  15. [15]G. E. Moorhouse. Reconstructing projective planes from semibiplanes. In Coding theory and design theory, Part II, volume 21 of IMA Vol. Math. Appl., pages 280–285. Springer, New York, 1990.DOI
  16. [16]R. C. Mullin and E. Nemeth. An improved bound for equidistant permutation arrays of index one. Utilitas Math., 13:77–85, 1978.
  17. [17]S. E. Payne. On the non-existence of a class of configurations which are nearly generalized n-gons. Journal of Combinatorial Theory, Series A, 12(2):268–282, Mar. 1972.DOI
  18. [18]D. Raghavarao. Some aspects of weighing designs. Ann. Math. Stat., 31:878–884, 1960.DOI
  19. [19]C. J. Salwach and J. A. Mezzaroba. The four biplanes with k = 9. Journal of Combinatorial Theory, Series A, 24(2):141–145, Mar. 1978.DOI
  20. [20]P. J. Schellenberg. A computer construction for balanced orthogonal matrices. In Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Boca Raton, Florida, 1975), volume 14 of Congressus Numerantium, pages 513–522, Winnipeg, 1975. Utilitas Mathematica.
  21. [21]A. Schleiermacher. On a class of partial planes related to biplanes. J. Geom., 107(2):445–466, 2016.DOI
  22. [22]J.-P. Serre. A course in arithmetic, volume No. 7 of Graduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1973. Translated from the French.DOI
  23. [23]L. H. Soicher. The GRAPE package for GAP, version 4.9.3. https://gap-packages.github.io/grape, 2025.
  24. [24]The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.14.0. https://www.gap-system.org, 2024.
  25. [25]L. Tolonen. Tasaētaisten permutaatiokoodien luokittelu. Bachelor’s thesis, Aalto University, 2026.
  26. [26]G. H. J. Van Rees. Slightly improved upper bounds for equidistant permutation arrays of index one. J. Combin. Math. Combin. Comput., 8:159–160, 1990.

Paper details

vlnc:W_wzf6xa9p
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents