On Elliptic Semiplanes, an Algebraic Problem in Matrix Theory, and Weight Enumeration of Certain Binary Cyclic Codes Citation Schroeder, Brian Leroy (2010) On Elliptic Semiplanes, an Algebraic Problem in Matrix Theory, and Weight Enumeration of Certain Binary Cyclic Codes. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/84VV-S966. https://resolver.caltech.edu/CaltechTHESIS:10262009-141148765 Abstract An elliptic semiplane is a λ-fold of a symmetric 2-(v,k,λ) design, where parallelism is transitive. We prove existence and uniqueness of a 3-fold cover of a 2-(15,7,3) design, and give several constructions. Then we prove that the automorphism group is 3.Alt(7). The corresponding bipartite graph is a minimal graph with valency 7 and girth 6, which has automorphism group 3.Sym(7). A polynomial with real coefficients is called formally positive if all of the coefficients are positive. We conjecture that the determinant of a matrix appearing in the proof of the van der Waerden conjecture due to Egorychev is formally positive in all cases, and we prove a restricted version of this conjecture. This is closely related to a problem concerning a certain generalization of Latin rectangles. Let ω be a primitive nth root of unity over GF(2), and let m i (x) be the minimal polynomial of ω i . The code of length n = 2 r -1 generated by m 1 (x)m t (x) is denoted C r t . We give a recursive formula for the number of codewords of weight 4 in C r 11 r for each r. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: elliptic,semiplane,design,graph,matrix,cage,code,error,correcting,cyclic Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Wilson, Richard M. Thesis Committee: Wilson, Richard M. (chair) Ramakrishnan, Dinakar Wales, David B. Defense Date: 24 September 2009 Non-Caltech Author Email: schroederb (AT) gmail.com Record Number: CaltechTHESIS:10262009-141148765 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:10262009-141148765 DOI: 10.7907/84VV-S966 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 5330 Collection: CaltechTHESIS Deposited By: Brian Schroeder Deposited On: 21 Dec 2009 18:46 Last Modified: 08 Nov 2019 18:07 Thesis Files Preview PDF - Final Version See Usage Policy. 337kB Repository Staff Only: item control page

On elliptic semiplanes, an algebraic problem in matrix theory, and weight enumeration of certain binary cyclic codes Thesis by Brian Schroeder In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 2010 (Defended September 24, 2009) ii c 2010 Brian Schroeder All Rights Reserved iii Acknowledgements I could never have finished this work without the advice and support of so many amazing people. I wrote this alone, but the writing was only the final step. Most of all, I would like to thank my parents, Duff and Vicki Schroeder. I could never have done this without you. Thank you for everything. You were right all along, Mom. I would like to thank my adviser at Caltech for the past four years, Dr. Rick Wilson. Thank you for your advice and patience, working with me for all this time. I really appreciate everything you have done for me. My mentor from Michigan State University (MSU), Dr. Jon Hall, helped me with the chapter on elliptic semiplanes, which was based on work we did while I was an undergraduate at MSU. Thank you, Dr. Hall. My family, including my sisters Ashlee and Kenzee, my brother-in-law Loren, my grandparents Jo Bancroft, Keith Schroeder, Bev Schroeder, and everyone in my extended family, all offered me encouragement while I was working on this thesis. It was worth more than you know. Thank you all for believing in me. iv Abstract An elliptic semiplane is a λ-fold of a symmetric 2-(v, k, λ) design, where parallelism is transitive. We prove existence and uniqueness of a 3-fold cover of a 2-(15, 7, 3) design, and give several constructions. Then we prove that the automorphism group is 3 · Alt(7). The corresponding bipartite graph is a minimal graph with valency 7 and girth 6, which has automorphism group 3 · Sym(7). A polynomial with real coefficients is called formally positive if all of the coefficients are positive. We conjecture that the determinant of a matrix appearing in the proof of the van der Waerden conjecture due to Egorychev [5] is formally positive in all cases, and we prove a restricted version of this conjecture. This is closely related to a problem concerning a certain generalization of Latin rectangles. Let ω be a primitive nth root of unity over GF (2), and let mi (x) be the minimal polynomial of ω i . The code of length n = 2r − 1 generated by m1 (x)mt (x) is denoted Crt . We give a recursive formula for the number of codewords of weight 4 in Cr11 for each r. v Contents Acknowledgements iii Abstract iv Contents v List of Tables vii List of Figures viii 1 Introduction 1 2 Formal Positivity of Eigenvalues of a Matrix 3 2.1 2.2 2.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Conjecture of van der Waerden concerning permanents . . . . 3 2.1.2 Generalized Latin rectangles . . . . . . . . . . . . . . . . . . . 4 2.1.3 Formally positive polynomials . . . . . . . . . . . . . . . . . . 5 2.1.4 Interlacing of eigenvalues . . . . . . . . . . . . . . . . . . . . . 6 Problems Concerning Column-subLatin Rectangles and Eigenvalues of Q. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 The case P (n, m, 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Weights of codewords in cyclic binary codes 22 3.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 The Codes Crt which are 2-error correcting . . . . . . . . . . . . . . . 23 3.3 Codewords of weight 4 in Crt . . . . . . . . . . . . . . . . . . . . . . . 24 vi 3.3.1 The codes Cs7 and Cs11 . . . . . . . . . . . . . . . . . . . . . . 4 Elliptic Semiplanes 27 31 4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Existence and uniqueness of an elliptic semiplane with 45 points . . . 42 4.3 Automorphisms and dualities . . . . . . . . . . . . . . . . . . . . . . 63 4.4 Cage graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Bibliography 74 vii List of Tables 3.1 j 2 +1 Weight enumerator for the dual of Cm with m odd and s = (j, m) (MacWilliams and Sloane). . . . . . . . . . . . . . . . . . . . . . . . . 3.2 j 2 +1 , 1 < i < 12 m, (m, 2j) = Weight enumerator for the dual of Cm 2(m, j) = 2s (MacWilliams and Sloane). . . . . . . . . . . . . . . . . . 4.1 25 25 Correspondence between distance from g and order of |gh| in the Petersen line graph, where g = (12)(34). . . . . . . . . . . . . . . . . . . 67 viii List of Figures 3.1 Computations for the number of codewords of weight 4 in Cs11 for small values of s. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1 The first of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. . 42 4.2 The second of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. 43 4.3 The third of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. . 43 4.4 The fourth of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. 44 4.5 The fifth of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. . 44 4.6 Action of row permutations on the six 3 × 3 permutation matrices. . . 65 4.7 Action of column permutations on the six 3 × 3 permutation matrices. 65 1 Chapter 1 Introduction In this thesis, we examine three separate topics in combinatorics. The topics covered range from Latin rectangles and more general objects, polynomial eigenvalues of matrices, binary cyclic codes, and design and graph theory. In Chapter 2 we consider a matrix found in the first proofs of the van der Waerden conjecture about permanents of doubly stochastic matrices. The original proofs consider the signs of the eigenvalues of a certain n × n matrix, using analysis to show that the number of positive and negative eigenvalues does not change under certain continuous operations on the entries of the matrix. The eigenvalues are shown to satisfy the desired conditions when all variables lie on the unit interval. We aim towards a proof that does not use analysis, but instead uses an algebraic and combinatorial approach. In a restricted setting we show the stronger result that the determinant is a polynomial in the variables with all positive coefficients. Our approach relates this problem to a problem about generalized Latin rectangles. More specifically, we consider m×n arrays with entries from {1, . . . , n}, first row 1, 2, . . . , n, second row a permutation of the set {1, . . . , n}, and arbitrary later rows that satisfy the condition that no entry is repeated in any column. We are interested in counting the difference between the number of those arrays with odd and even permutations in the second row. In Chapter 3 we consider a generalization of binary BCH codes. In particular we consider those codes generated by the minimal polynomials of two roots of unity over GF (2). A recent result of Hernando and McGuire [8] gives a solution to the problem 2 of which families of two root codes have an infinite family of 2-error correcting codes of increasing lengths. We consider the problem of enumerating the number of codewords of weight 4 for those two root codes which are not 2-error correcting. In particular, we find a formula for the number of codewords of weight 4 in the code generated by the first and 11th powers of a primitive root of unity over GF (2) with length 2r − 1, in terms of r. Finally, in Chapter 4, we give a proof of the existence and uniqueness of an elliptic semiplane on 45 points. We give an algebraic construction of the associated graph using the line graph of the Petersen graph. Then we use these two constructions to give a proof that the automorphism group of the elliptic semiplane is 3 · Alt7 , the nonsplit central extension of Alt7 , and the automorphism group of the bipartite graph is 3 · Sym7 . We then briefly turn to the subject of cages. It is known that the cage with valency 7 and girth 6 has 90 vertices, and it was constructed by O’Keefe and Wong [18]. Our construction of the cage is simpler and does not appeal to a computer search. But we are only able to show uniqueness of the cage under the condition that the cage is also a 3-cover. A computer search is still required to to show uniqueness of the cage in general. 3 Chapter 2 Formal Positivity of Eigenvalues of a Matrix 2.1 Preliminaries 2.1.1 Conjecture of van der Waerden concerning permanents The determinant of a square matrix is a well-known function, in which the sum depends on the sign of the permutations. If we remove the sign of the permutation, we get another function, the permanent, which has also been the object of much study. Definition 2.1.1. Let A be an n × n matrix with entries aij for i = 1, . . . , n and j = 1, . . . , n. Then the permanent of A, denoted per A, is defined as per A = X a1σ(1) a2σ(2) · · · anσ(n) , σ∈Sn where Sn is the symmetric group on {1, . . . , n}. The main conjecture about the permanent, which is now a theorem, is the socalled van der Waerden’s permanent conjecture. The conjecture concerns the value of the permanent of doubly stochastic matrices. Definition 2.1.2. Let A be an n × n matrix. Then A is called doubly stochastic if and only if the following conditions hold: 4 (i) each entry of A is a real number in the closed interval [0, 1], (ii) for each row, the sum of the entries in that row is 1, and (iii) for each column, the sum of the entries in that column is 1. The long standing conjecture, which was proven in 1981 is the following theorem. Theorem 2.1.3 (van der Waerden’s permanent conjecture). Let A be an n×n doubly stochastic matrix. Then per A ≥ n!/nn , and equality holds if and only if every entry of A is 1/n. Proof. See [5] and [6] for the two original proofs. The results in the next section are related to a conjecture which would generalize part of the proof given in [5]. 2.1.2 Generalized Latin rectangles In this paper, we will consider a type of generalization of Latin rectangles for which there does not appear to be consistent terminology in the literature. For reference, we will define most of the terms here. We will be using somewhat nonstandard terminology. A column-subLatin rectangle does not necessarily satisfy the condition that each row contains each symbol exactly once. Definition 2.1.4. Let M be an r × n matrix with r ≥ 2. Then M is a reduced column-subLatin rectangle if and only if the following conditions hold: (i) each entry of M is in the set {1, . . . , n}, (ii) the first row of M is (1, 2, . . .), the identity permutation on {1, . . . , n}, (iii) the second row of M is a permutation of {1, . . . , n}, and (iv) the matrix M satisfies the column subLatin condition, that is, no symbol occurs more than once in any column. 5 Definition 2.1.5. A reduced column-subLatin rectangle M is called second-even or second-odd as the second row is an even or odd permutation, respectively. A Latin rectangle is called even or odd as the product of the row permutations is an even or odd permutation. 2.1.3 Formally positive polynomials We call a polynomial formally positive if each of its coefficients is positive. To be precise, we give the following definition. Definition 2.1.6. Let f be a polynomial with real coefficients and commutative variables taken from the set S. Write f as a sum of monomials, in reduced form, that is, such that no two monomials have the same product of variables. For a finite product p of positive integral powers of variables from S, let fp denote the coefficient on p in f . If for every p, fp = 0, then f is called formally zero. If for every p, fp ≥ 0, and f is not formally zero, then f is called formally positive. If for every p, fp ≤ 0, and f is not formally zero, then f is called formally negative. There are a few facts about formally positive polynomials which are easily seen to be true. Proposition 2.1.7. Let M be the set of formally positive polynomials with variable set S. Then the following are true: (a) Let f, g ∈ M . Then f +g ∈ M . That is, M is closed under polynomial addition. (b) Let f, g ∈ M . Then f g ∈ M . That is, M is closed under polynomial multiplication. (c) Let f ∈ M , c ∈ R, c > 0. Then cf ∈ M . That is, M is closed under scalar multiplication. (d) Let f ∈ M , and let g : S → R be a function such that g(s) > 0 for each s ∈ S. Let f (g) represent the evaluation of f with s = g(s) for each s ∈ S. Then f (g) > 0. 6 2.1.4 Interlacing of eigenvalues The general interlacing of eigenvalues Lemma proven in [24] is the following. Lemma 2.1.8. Let A be a symmetric matrix of order n with eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn . Suppose N is an m×n real matrix such that N N T = Im , so m ≤ n. Let B := N AN T , and let µ1 ≥ µ2 ≥ · · · ≥ µm be the eigenvalues of B. Then the eigenvalues of B interlace those of A, in the sense that λi ≥ µi ≥ λn−m+i for i = 1, 2, . . . , m. In our situation, the matrices are upper left principal submatrices, and we apply Lemma 2.1.8 repeatedly to examine the signs of the eigenvalues of the full matrix. Lemma 2.1.9. Let A be a symmetric matrix of order n and for each r = 2, . . . , n let Ar be the upper left r × r principal submatrix of A. Suppose that det Ar is negative for each even r and positive for each odd r. Then A has n − 1 negative eigenvalues and one positive eigenvalue. Proof. For each r = 2, . . . , n, let the eigenvalues of Ar be λr1 ≥ λr2 ≥ · · · ≥ λrr. For each n > r ≥ 2, let Nr be the r × (r + 1) matrix given by Nr = (Ir |or ), where or is the r-dimensional column zero vector. We have Ar = Nr Ar+1 NrT . So by 7 Lemma 2.1.8, we have λr+1,i ≥ λr,i ≥ λr+1,i+1 for i = 1, . . . , r. Now λ21 λ22 < 0 since det A2 < 0, so λ21 > 0 > λ22 . By way of induction, suppose that for some 2 ≤ r < n we know that λr,1 > 0 > λr,2 ≥ · · · ≥ λr,r . Then we have λr+1,1 ≥ λr,1 > 0, and 0 > λr,i ≥ λr + 1, i + 1 for each i = 2, . . . , r. So the product λr+1,1 λr+1,3 · · · λr+1,r+1 has the same sign as det Ar . But det Ar+1 has the opposite sign of det Ar , so λr+1,2 < 0, and we have λr+1,1 ≥ λr,1 > 0 > λr+1,2 ≥ λr,2 ≥ · · · ≥ λr,r ≥ λr+1,r+1 . This completes the proof. Note that, in the case of Lemma 2.1.9, the determinant of A1 is not relevant to determining the signs of the eigenvalues of A. In our later application, we will in fact have det A1 = 0. Let n ≥ 2 and let Q be the matrix such that xQy T = per (a1 , . . . , an−2 , x, y), 8 where ai = (ai1 , ai2 , . . . , ain ) and per (a1 , . . . , an−2 , x, y) denotes the permanent of the n × n matrix with row vectors given by the parameters, as defined in Definition 2.1.1. In Egorychev’s proof of the van der Waerden conjecture, and in related proofs, an important step is equivalent to showing that when each of the aij are positive, n − 1 of the eigenvalues of Q are negative, and the other is positive. 2.2 Problems Concerning Column-subLatin Rectangles and Eigenvalues of Q We conjecture that the following statement is true. Conjecture 2.2.1 (Determinant Form). Let m ≥ 2 and let A be the upper left m × m submatrix of Q. Then (−1)m−1 det A is formally positive and not formally zero as a polynomial in the n(n − 2) variables aij , i = 1, . . . , n − 2, j = 1, . . . , n. We can apply Lemma 2.1.9 to Conjecture 2.2.1 to show the same result from Egorychev’s proof, under less restrictive conditions and without using complex analysis. We first make an observation which relates Conjecture 2.2.1 to reduced columnsubLatin rectangles. Let v i = (vi1 , vi2 , . . . , vin ) for each i = 1, . . . , n − 2 be a vector of nonnegative integers. Let o and e be the number of second-odd and second-even, respectively, reduced column-subLatin n × n rectangles with m(2 + i, j) = vij , where m(r, j) denotes the multiplicity of j in row r for each 1 ≤ r, j ≤ n. Then e − o is the coefficient on n−2 n YY v aijij i=1 j=1 in det Q. So we have the following, which is equivalent to the case of Conjecture 2.2.1 where m = n. 9 Conjecture 2.2.2 (Rectangle Form). Let n ≥ 2 and for each i = 1, . . . , n − 2, and each j = 1, . . . , n, let vij be a nonnegative integer. Let o and e, respectively, be the number of odd and even reduced column-subLatin n × n rectangles, with vij the multiplicity of j in row 2 + i. Then e − o ≥ 0 if n is odd, and e − o ≤ 0 if n is even. It is natural to consider a modification of the problem of Conjecture 2.2.2 to column-subLatin rectangles with a smaller number of rows. For k + 2 rows, this is equivalent to the problem of Conjecture 2.2.1 where for each i > k, we set ai = (1, 1, . . . , 1). We make clear the relationship between the two conjectures by separating the two statements. In each we have n ≥ m ≥ 2, and 1 ≤ k ≤ n − 2. Statement 2.2.3 (Statement P (n, m, k)). Let Q be the matrix such that xQy T = per (a1 , . . . , bf an−2 , x, y), where ai = (ai1 , ai2 , . . . , ain ), for each i = 1, . . . , k, and ai = (1, 1, . . . , 1) for each i = k + 1, . . . , n − 2. Let A be the upper left principal m × m submatrix of Q. Then (−1)m−1 det A is formally positive. Statement 2.2.4 (Statement R(n, k)). Suppose V1 , . . . , Vk are multisets of size n with elements from {1, . . . , n}. Consider all (k + 2) × n reduced column-subLatin rectangles with row 2 + i a permutation of Vi for each i = 1, . . . , k. Let e be the number of such rectangles which are row-even and let o be the number of them which are second-odd. Then (−1)n−1 (e − o) ≥ 0, and further, for some choice of multisets V1 , . . . , Vk , we have (−1)n−1 (e − o) > 0. By our discussion, we know that P (n, n, k) is true if and only if R(n, k) is true. Conjecture 2.2.2 is equivalent to the statement that for all n, R(n, n − 2) is true, and Conjecture 2.2.1 is equivalent to the statement that for all n and for all m, P (n, m, n − 2) is true. 10 2.3 The case P (n, m, 1) We consider Conjecture 2.2.1 in the case where ai = (1, 1, . . . , 1) for each i = 2, . . . , n − 2. We let a1 = (a1 , . . . , an ) to simplify the notation. Let s = a1 + · · · + an . In this case we have  0 s − a1 − a2 s − a1 − a3 ··· s − a1 − an       s − a2 − a1 0 s − a2 − a3 ··· s − a2 − an   . Q=  .. .. .. .   . .   s − an − a1 s − an − a2 ··· s − an − an−1 0 In this section we will prove the Conjecture 2.2.1 in this special case. Our main theorem is the following. Theorem 2.3.1. The statement P (n, m, 1) is true for all n ≥ m ≥ 3. This Theorem will follow from the special case n = m, by the following Lemma, because in this case there is a simple relationship between the entries of the upper left principal submatrices. Lemma 2.3.2. For each n ≥ m ≥ 3, the statement P (m, m, 1) implies P (n, m, 1). Proof. For 1 ≤ i, j ≤ m, let c be the (i, j) entry of the m × m matrix Q and d be the upper left m × m submatrix of the n × n matrix Q (which is in fact the same as the (i, j) entry of the n × n matrix). If i = j then c = d = 0, and otherwise c+ n X ai = d, i=m+1 where c is a linear combination of exactly m − 2 of the ai . Perform the substitution b ` = a` + n X 1 ai , m − 2 i=m+1 for each ` = 1, . . . , m on d. Then c is just d with each variable a` replaced by b` for each ` = 1, . . . , m. This substitution does not depend on the choice of (i, j), so it can 11 be performed simultaneously on all entries. It is also a formally positive substitution, and reduces P (n, m, 1) to P (m, m, 1). Theorem 2.3.3. The statement P (n, n, 1) is true for all n ≥ 3. We now immediately have the following Corollary. Corollary 2.3.4. Let v = (v1 , . . . , vn ) be a vector of nonnegative integers. Let o and e be the number of odd and even, respectively, reduced column-subLatin 3 × n rectangles with symbol j appearing vj times in row 3 for each j = 1, . . . , n. Then e − o ≥ 0 if n is odd and e − o ≤ 0 if n is even. In fact, e − o in Corollary 2.3.4 is the coefficient on vj j=1 aj in det Q. Qn So this is equivalent to P (n, n, 1). The case of v = (1, 1, . . . , 1) corresponds to the difference between the number of even and odd 3 × n reduced row Latin rectangles, by this Proposition 2.3.5. For each n, let do (n) and de (n) be the number of 3×n reduced row Latin rectangles with odd and even second row, respectively. Also let co (n) and ce (n) be the number of 3 × n reduced row Latin rectangles with the product of the second and third row permutations even and odd, respectively. Then de (n)−do (n) = ce (n)−co (n). To prove this proposition, we require the following Lemma. Lemma 2.3.6. The number of reduced 3 × n Latin rectangles with odd second row and even third row is the same as the number of those with odd second row and odd third row. Proof. Let σ ∈ Sn be an odd derangement, and let Pσ be the permutation matrix corresponding to σ. Let Mσ = J − I − Pσ . Then Mσ is a 0-1 matrix and det Mσ is the difference between the number of even derangements disjoint from σ and the number of odd derangements disjoint from σ. It will suffice to show that det Mσ = 0. 12 Let me11 · · · mekk be the cycle type of σ. A cycle of length m can be written as a P product of m − 1 transpositions. So σ can be written as a product of ki=1 ei (mi − 1) transpositions. Since σ is odd, at least one mi must be even. Let (a1 , . . . , am ) be an even cycle in the disjoint cycle decomposition of σ. Consider the rows corresponding to a1 , . . . , an in the matrix Mσ . Row ai contains a 1 in every position, except ai and ai+1 (where we allow that n + 1 = 1), and a 0 in positions ai and ai+1 . Consider the sum of all odd terms in this cycle, that is rows a1 , a3 , a5 , . . . , an−1 . Among these, each row contains a 1 in all positions disjoint from a1 , a2 , . . . , an and for every position among the a1 , . . . , an , exactly one row contains a 0 and the rest contain 1. Therefore, the sum of these rows contains n/2 in each position disjoint from the n-cycle and n/2 − 1 in each position among the n-cycle. Similarly, the sum of the rows corresponding to even positions in the n-cycle is the same. That is, we have established a non-trivial linear dependence among the rows of Mσ . Therefore, det Mσ = 0. Proof of Proposition 2.3.5. Let bee (n), beo (n), boe (n), and boo (n) be the number of 3×n reduced row Latin rectangles where the second row is even or odd as the first subscript is e or o, and the third row is even or odd as the second subscript is e or o. We have de (n) = bee (n) + beo (n), do (n) = boe (n) + boo (n), ce (n) = bee (n) + boo (n), co (n) = boe (n) + beo (n). Also it is clear that boe (n) = beo (n), since the second and third rows can be swapped. So we have de (n) − do (n) = bee (n) − boo (n), and ce (n) − co (n) = bee (n) − 2boe (n) + boo (n). 13 The proposition is therefore equivalent to boe (n) = boo (n). Therefore it follows from Lemma 2.3.6 In the special case where the third row is a permutation, Corollary 2.3.4 follows from a result of Zeng [26]: Proposition 2.3.7. [26] Let Sk,n denote the difference between the number of even reduced Latin rectangles of size k × n and the number of odd ones. We have   2 tn t 2t (1 − t) 1+ S3,n = e + . 2 n! 1 + t (1 + t) n≥1 X In fact, (1 − t)2 = 1 − 3t + 4t2 − 4t3 + 4t4 − 4t5 + · · · , 1+t t = t − 2t2 + 3t3 − 4t4 + 5t5 − 6t6 + 7t7 − · · · . (1 + t)2 So the coefficient on tm in tn S3,n n! n≥1 X is (−1)m−1 (m − 4) for m ≥ 2. In particular the coefficient is 2, m = 2, −1, m = 3, 0, m = 4, (m − 4), m ≥ 5 odd, −(m − 4), m ≥ 5 even. This proves the conjecture in the case where the third row is a permutation. Now we turn to the polynomial determinant interpretation of the problem to prove the other cases. 14 Adding each of rows 1, . . . , n − 1 to row n, and factoring (n − 2) from row n, we have det Q = (n − 2) det Q0 where   0 s − a1 − a2 s − a1 − a3 ··· s − a1 − an      s − a − a 0 s − a − a · · · s − a − a 2 1 2 3 2 n  0 .  Q =  .. .. ...   . .   s − a1 s − a2 ··· s − an−1 s − an Now subtracting row n from each of rows 1, . . . , n − 1, row i becomes a constant −ai except in the ith coordinate, where it is ai − s, for each i = 1, . . . , n − 1. So, factoring −1 from each of rows 1, . . . , n − 1, we have det Q = (−1)n−1 (n − 2) det Q00 , where  s − a1 a1 a1    a2 s − a2 a2    a3 a3 s − a3 Q00 =   ..  .    an−1 an−1 an−1  s − a1 s − a2 s − a3 ··· a1 a1 ··· a2 a2 ··· .. . a3 .. . a3 .. . ··· s − an−1 an−1 ··· s − an−1 s − an        .       Lemma 2.3.8. The determinant det Q and therefore also, det Q00 is a symmetric polynomial of degree n in the variables a1 , . . . , an . Proof. Consider a transposition of the variables ai and aj , 1 ≤ i, j ≤ n in the matrix Q. Call the new matrix Q{i, j}. Swapping rows i and j, and columns i and j in Q{i, j}, gives the matrix Q. Since each column or row swap inverts the sign of the determinant, we have det Q = (−1)2 det(Q{i, j}) = det(Q{i, j}). Since det Q = (n − 2) det Q00 , both determinants are symmetric polynomials. 15 Each product in the determinant of Q has n factors, each of degree 1. Therefore, each product has degree n, and det Q has degree n. To show that det Q00 is formally positive, by Lemma 2.3.8, it suffices to show that det Q00 is formally positive (mod an ) and that the coefficient on a1 · · · an is positive. By symmetry, formal positivity (mod an ) shows formal positivity (mod ai ) for each 1 ≤ i ≤ n, so the coefficient on every term not divisible by a1 · · · an is positive. Then because the degree of det Q is n, the only term divisible by a1 · · · an is a1 · · · an itself. We will show det Q00 (mod an ) is a formally positive polynomial by considering the cofactor expansion on row n. For each k = 1, . . . , n − 1, let Rk be the (n − 1) × (n − 1) matrix defined by    a,   i (Rk )ij = s − ai ,     a , i 6= j, i = j 6= k, i = j = k. k Then det Rk = (−1)n−1−k det Q00n,k , since Rk is the cofactor Q00n,k with n−1 −k column transpositions. So we have det Q00 = (s − an ) det Q00n,n + = (s − an ) det Q00n,n − n−1 X (−1)k (s − an−k ) det Q00n,n−k k=1 n−1 X (s − ak ) det Rk . k=1 Consider the matrix Q00n,n . We have     00 Qn,n =     s − a1 a1 a1 ··· a1 a2 .. . s − a2 a2 ... ··· a2 .. . an−1 an−1 an−1 · · · s − an−1     .    16 Let σ ∈ Sn−1 have fixed point set X. Then n−1 Y aiσ(i) = i=1 Y Y (s − ai ) i∈X aj . j∈{1,...,n−1}\X For a given fixed point set X, the permutations which have fixed point set X are the derangements of {1, . . . , n − 1} \ X, and the signature is the signature of the derangement. We use the following Lemma 2.3.9. Lemma 2.3.9. Let f (k) be the difference of the number of even derangements of k and the number of odd derangements of k. Then f (k) = (−1)k−1 (k − 1). Proof. In fact, we have f (k) = det(J − I). Subtracting row 1 from each of the other rows, and then adding each of the other rows to row 1, we have       f (k) = det(J − I) = det      (k − 1) 0 1 −1 1 .. . 0 1 0 ··· 0 0    0    k−1 −1 · · · 0  = (k − 1)(−1) .  . . . ..  .   0 · · · −1 0 ··· (−1)|X|−1 (|X| − 1) Y By Lemma 2.3.9, we have X det Q00n,n = i∈X X⊆{1,...,n−1} Y ai (s − aj ). j∈{1,...,n−1}\X Let t = a1 + · · · + an−1 . Then the terms of det Q00n,n which do not contain a factor of an are obtained by replacing s with t in the above expression. The expression X (−1)|X|−1 (|X| − 1) X⊆{1,...,n−1} Y i∈X ai Y j∈{1,...,n−1}\X (t − aj ) 17 is formally positive if n−1 Y X i=1 ∅6=X⊆{1,...,n−1} (t − ai ) = (|X| − 1) Since n−1 t = Y i∈X n−1 Y Y ai (t − aj ). j∈{1,...,n−1}\X ((t − ai ) + ai ), i=1 this is equivalent to the following identity, which we state as Lemma 2.3.10. Lemma 2.3.10. Let t = a1 + a2 + · · · + an and N = {1, 2, . . . , n}. Then tn = X |X| Y i∈X X⊆N Y ai (t − aj ). j∈N \X Proof. On the right hand side above, consider t as a formal variable. Since tn occurs only when X = ∅, in which case |X| = 0, the highest degree term of t is at most degree n − 1. A term with factor tn−1 occurs only for |X| = 1. In the case X = {i}, the product is Y ai (t − aj ), j∈N \{i} so the coefficient on tn−1 is a1 + a2 + · · · + an . We claim that the coefficient on tk for each k = 0, . . . , n − 2 is 0. In fact, a term divisible by tk occurs in the product for X only when |N \ X| ≥ k. Suppose |N \ X| = k + ` for some ` ≥ 0. Then the coefficient on t in the product for the set X is (−1)` Y i∈X ai X Y aj . Y ⊂N \X,|Y |=` j∈Y In particular, each coefficient on tk is a squarefree homogeneous polynomial of degree n − k. Fix a set Z ⊆ N with |Z| = n − k for some k ≥ 2. Then the coefficient on Q tk i∈Z ai is X X⊆Z (−1) |Z|−|X|  n−k  X n−k = (−1)n−k+i = (1 − 1)n−k = 0. i i=0 18 So the identity reduces to tn = (a1 + · · · + an )tn−1 , which is true. Therefore the minor determinant det Q00n,n is formally positive (mod an ). We give the exact expression as Lemma 2.3.11. Lemma 2.3.11. Let M = {1, . . . , n − 1}. Then det Q00n,n = 2s X (|X| − 1) Y ai i∈X ∅6=X⊆M |X| odd Y (s − aj ) (mod an ), j∈M \X and Q00n,n is formally positive (mod an ). Proof. This follows immediately by canceling the negative terms in the above expression, and using the identity of Lemma 2.3.10. Now consider the matrix        Rk =        s − a1 a1 a1 ··· a1 a2 .. . s − a2 a2 ... ··· a2 .. . ak .. . ak ··· ak .. . ak .. . an−1 an−1 an−1 · · · s − an−1        .       Let σ ∈ Sn−1 . Then n−1 Y Y i=1 i∈X\{k} (Rk )iσ(i) = ak (s − ai ) Y j∈{1,...,n−1}\(X∪{k}) aj . 19 Letting Mk = {1, . . . , n − 1} \ {k}, where M is as above, we have Y Y X n−1 X n−1 (Rk )iσ(i) (Rk )iσ(i) + det Rk = σ∈Sn−1 i=1 σ(k)6=k σ∈Sn−1 i=1 σ(k)=k X = ak (|X| − 1)(−1)|X|−1 Y i∈X X⊆Mk + ak X = ak X |X|(−1)|X| Y = ak (s − aj ) j∈Mk \X (−1)|X| (|X| − (|X| − 1)) X⊆Mk X Y ai i∈X (−1)|X| X⊆Mk Y Y ai i∈X (s − aj ) j∈Mk \X Y ai i∈X X⊆Mk Y ai Y (s − aj ) j∈Mk \X (s − aj ). j∈Mk \X We now have an expression for det Q00 (mod an ) which we can easily reduce to a form where it can be seen to be formally positive. First we look at Lemma 2.3.12. Lemma 2.3.12. The determinant det Q00 is formally positive (mod an ). Proof. In this proof, everything is (mod an ). We have det Q00 = 2s X (|X| − 1) Y i∈X ∅6=X⊆M |X| odd − n−1 X k=1 ak (s − ak ) Y (s − aj ) j∈M \X X X⊆Mk (−1)|X| Y i∈X ai Y j∈Mk \X (s − aj ). 20 Working with the second line, we have − n−1 X =− ak =− =− i∈X j∈Mk \X Y (s − aj ) (s − aj ) j∈M \X X X ai n−1 X Y i∈X X Y ak ak Y Y (s − aj ) j∈M \X Y ai X⊆Mk i∈X |X| odd k=1 − Y ai X⊆Mk i∈X |X| odd n−1 X (s − aj ) (s − aj ) k=1 ak Y ai j∈M \X X Y ak Y j∈M \X Y ai X⊆Mk i∈X |X| even n−1 X ai i∈X X⊆M k∈M \X |X| odd + Y (−1)|X| X Y ak k=1 + X X⊆Mk k=1 n−1 X (−1)|X| X⊆Mk k=1 n−1 X X ak (s − ak ) (s − aj ) j∈M \X (s − aj ). j∈M k=1 Then, combining the above two equations, we get   X det Q00 = 2s(|X| − 1) − X⊆M |X| odd + n−1 X k=1 ak X k∈M \X X Y Y ai X⊆Mk i∈X |X| odd ak  Y ai i∈X (t − aj ) − j∈M \X n−1 X k=1 Y (s − aj ) j∈M \X ak Y (t − aj ), j∈M where the first line is formally positive, and the second line can be seen to be formally positive by separating out the part where |X| = 1 from the first summation. In fact, this part of the summation is n−1 X k=1 ak X i∈Mk ai Y j∈Mi (s − aj ), 21 and the second summation can be expanded as n−1 X ak k=1 X Y ai i∈Mk (s − aj ), j∈Mk but these two expressions are equal by reversing the order of i and k. So we have  X det Q00 =  2s(|X| − 1) − X⊆M |X| odd + n−1 X k=1 ak X ak  k∈M \X X Y X⊆Mk i∈X |X|≥3 odd ai Y Y i∈X ai Y (s − aj ) j∈M \X (t − aj ), j∈M \X which is clearly formally positive. Now we can give the proof of Theorem 2.3.3. Proof of Theorem 2.3.3. By the remarks following Lemma 2.3.8 and by the statement of Lemma 2.3.12, it remains to show only that the coefficient on a1 · · · an in det Q00 is positive. So the Theorem follows from Proposition 2.3.7. 22 Chapter 3 Weights of codewords in cyclic binary codes 3.1 Basic definitions There are two equivalent definitions of cyclic binary codes, one from a vector space viewpoint and one from a ring theory viewpoint. Definition 3.1.1 (Vector space definition). A cyclic code of length n is a vector subspace of Zn2 which is closed under cyclic translations. Where {e0 , . . . , en−1 } is the standard basis, a cyclic translation is a linear function f : Zn2 → Zn2 such that there exists some integer j for which f (ei ) = f (ei+j ) for each i = 1, . . . , n (subscripts taken mod n). Definition 3.1.2 (Ring theoretic definition). A cyclic code of length n, is an ideal in the principal ideal ring Z2 [x]/(xn − 1). We identify the element (a0 , . . . , an−1 ) ∈ Z2n with the element a0 + a1 x + . . . an−1 xn−1 ∈ Z2 [x]/(xn − 1). Then cyclic shifts correspond to multiplication by powers of x, and the ideal condition corresponds to the subspace closed under cyclic shifts condition. Therefore these two definitions are equivalent. 23 In the ring theoretic viewpoint, the generating polynomial of a cyclic code C is a polynomial g(x) such that C = (g(x)), and g(x) divides xn − 1. In the vector space viewpoint, if deg g(x) = d, then the dimension of C is n − d. For any two elements v, x of a code C, the Hamming distance d(v, x) is the number of coordinates in which they differ under the standard basis. The weight of an element v ∈ C is w(v) = d(v, 0), and the minimum weight of C is the minimum over all v ∈ C of w(v). Suppose the minimum weight d of a code C satisfies d ≥ 2e + 1. In this case, let v ∈ C and let e ∈ Z2n be any vector such that w(e) ≤ d. Let f (x) = d(v + e, x). Then v is the unique element of C that satisfies the inequality f (v) ≤ d. The code C is said to be e-error correcting. 3.2 The Codes Crt which are 2-error correcting Let ω be a primitive nth root of unity over GF (2). The minimal polynomial of ω i over GF (2) will be denoted as mi (x) for each integer i. Theorem 3.2.1 (BCH Bound). Let f (x) ∈ GF (2)[x], and suppose for some i, each of ω i , ω i+1 , . . . , ω i+t−1 are all roots of f (x). Then the minimum weight of the code generated by f (x) is ≥ t + 1. The classic 2-error correcting BCH code is the code of length n generated by m1 (x)m3 (x). Considering the field automorphism of GF (2n ) given by x 7→ x2 , we have that in addition to ω and ω 3 , also ω 2 and (ω 2 )2 = ω 4 are roots of m1 (x)m3 (x). So the first 4 consecutive powers of ω are roots, and by the BCH bound this code has minimum distance ≥ 5. In general, the BCH code of designed minimum distance d = 2s + 1 is the code generated by m1 (x)m3 (x) · · · m2s−1 (x). Each consecutive even power of ω between ω 2 and ω 2s is a root of this polynomial by applying the field automorphism x 7→ x2 . 24 We now turn to a particular type of generalization of the 2-error correcting BCH code. Let n = 2r − 1, and let Crt be the cyclic code of length n generated by m1 (x)mt (x). The codes Cr3 are the 2-error correcting BCH codes. Two families of t values which give infinitely many 2-error correcting codes have been known since 1971. In 1968, Gold [7] showed that for t = 2s + 1, the code Crt is 2-error correcting if (s, r) = 1. The numbers t = 2s + 1 are known as the Gold numbers. In 1971, Kasami [13] showed that for t = 4s − 2s + 1, the code Crt is 2-error correcting if (s, r) = 1. The numbers t = 4s − 2s + 1 are known as the Kasami-Welch numbers. In this case, if (s, r) > 1 then the code has words of weight 3. Recent results of Hernando and McGuire [8] state that the only values of t for which the code Crt is 2-error correcting for infinitely many values of r are the Gold and Kasami-Welch numbers. That is, for any t which is not of one of these two forms, there are only finitely many 2-error correcting codes Crt . 3.3 Codewords of weight 4 in Crt We investigate the number of codewords of weight 4 in the codes Crt . In particular, we are interested in finding formulas for the number of codewords of weight 4 for families of these codes when t is fixed and r varies. In some cases, the weights of all codewords for dual codes in some family are known. In these cases, the MacWilliams identity gives a relationship between the weights of codewords in a binary linear code C and its dual code C ⊥ . Theorem 3.3.1 (MacWilliams identity). If C is a k-dimensional linear binary code of length n, and Ai is the number of words of weight i in C and A0i is the number of words of weight i in the dual C ⊥ , then n X k=0 n A0k xn−k y k = 1 X Ai (x + y)n−i (x − y)i . |C| i=0 The number of codewords for each different weight are known for the dual codes of Crt for each of the Gold numbers. These are given in Tables 3.1 and 3.2. Applying 25 i Ai 0 1 m−1 (m+s−2)/2 m m−s−1 2 −2 (2 − 1)(2 + 2(m−s−2)/2 ) (2m − 1)(2m − 2m−s + 1) 2m−1 2m−1 + 2(m+s−2)/2 (2m − 1)(2m−s−1 − 2(m−s−2)/2 ) j 2 +1 Table 3.1: Weight enumerator for the dual of Cm with m odd and s = (j, m) (MacWilliams and Sloane). i 0 2m−1 2 ± 2(m+2s−2)/2 2m−1 ± 2m/2−1 m−1 Ai 1 m s (2 − 1)[(2 − 1)2m−2s + 1] (m−2s−2)/2 m 2 (2 − 1)(2(m−2s)/2 ∓ 1)/(2s + 1) 2(m+2s−2)/2 (2m − 1)(2m/2 ∓ 1)/(2s + 1) j 2 +1 Table 3.2: Weight enumerator for the dual of Cm , 1 < i < 21 m, (m, 2j) = 2(m, j) = 2s (MacWilliams and Sloane). the MacWilliams identity, we can determine the number of codewords of weight 4 in these codes. For other values of t where explicit formulas for weights of the dual code are not as easily calculated, we use an approach from algebraic geometry to determine formulas for the number of words of weight 4. Let gt (X, Y, Z) = X t + Y t + Z t + (X + Y + Z)t . (X + Y )(X + Z)(Y + Z) We establish a connection between certain zeroes of gt and words of weight 4 in the codes Crt . Suppose a word of weight 4 in Crt has 1’s in positions i, j, k, `. Then ω i + ω j + ω k + ω ` = 0 and ω it + ω jt + ω kt + ω `t = 0. Letting X = ω i , Y = ω j , Z = ω k , W = ω ` we have the system X +Y +Z +W =0 X t + Y t + Z t + W t = 0. 26 Since this is a system over a field of characteristic 2, we have W = X + Y + Z and so X t + Y t + Z t + (X + Y + Z)t = 0. This is clearly divisible by X + Y , X + Z, and Y + Z. We can also go in the other direction. If (X, Y, Z) is a solution of gt (X, Y, Z) = 0 where X, Y, Z are distinct and nonzero, this gives a solution to the above system. Each solution of the above system has 4! = 24 permutations corresponding to the same word of weight 4. Definition 3.3.2. Let Nr be the number of projective points on a curve over GF (q r ). Then the zeta function of the curve is ζ(t) = exp ∞ X tr Nr r r=1 ! . Hartshorne [9] gives the following formula for the zeta function, which is applicable to gt . If X is a smooth variety of dimension n, then ζ(t) = P1 (t)P3 (t) · · · P2n−1 (t) , P0 (t)P2 (t) · · · P2n (t) where P0 (t) = 1−t, P2n (t) = 1−q n t, and for each 1 ≤ i ≤ 2n−1, Pi (t) is a polynomial with integer coefficients which can be written Pi (t) = Y (1 − αij t), where the αij are algebraic integers with |αij | = q i/2 . Further, in the case of gt , the polynomial P1 (t) has degree 2g, where g = (d − 1)(d − 2)/2, and where d is the degree of the polynomial gt . This implies that the coefficients ai 27 on ti satisfy a2g−i = q g−i ai . For some values of t where gt is absolutely irreducible, we can compute the zeta function of gt . 3.3.1 The codes Cs7 and Cs11 For t = 7, Wilson and Janwa compute the zeta function of gt . By computer or by hand, it is straightforward to find that N1 = 0, N2 = 14, and N3 = 24, which is enough to determine the zeta function: ∞ X Ns ζ(x) = exp s=1  =1+ s ! x s 14 2 24 3 x + x + ··· 2 3  1 + 2  14 2 24 3 x + x + ··· 2 3 2 = 1 + 0x + 7x2 + 8x3 + · · · so we get P1 (x) = (1 − x)(1 − 2x)ζ(x) = 1 − 3x + 9x2 − 13x3 + · · · . And this implies that P1 (x) = 1 − 3x + 9x2 − 13x3 + 18x4 − 12x5 + 8x6 . So we have ζ(x) = exp ∞ X Ns s=1 s ! xs = P1 (x) , (1 − x)(1 − 2x) and we can recursively compute the coefficients Ns using this formula. In this case, when s is even, we have exceptional solutions which do not correspond to codewords of weight 4 in Cs7 . These are solutions where two of X, Y, Z are equal or one of X,Y ,Z, or X + Y + Z is zero. In fact for each even s, there are always 14 28 exceptional solutions. So we have the following formula for the number of words of weight 4: w4 (Cs7 ) =   nN /24 if s is odd, s  n(N − 14)/24 if s is even. s Now we consider the case t = 11. The genus g = 21, so to compute the zeta function of g11 using Hartshorne’s formula, we must know the number of projective solutions of g11 over GF (2s ) for each s = 1, . . . , 21. Using a computer, we directly compute the number of projective solutions of g11 over GF (2s ) in these cases. The computations are listed in Figure 3.1. Here Ns is the number of projective solutions of g11 (X, Y, Z) = X 11 + Y 11 + Z 11 + (X + Y + Z)11 (X + Y )(X + Z)(Y + Z) and Es is the number of exceptional solutions (note that the number of exceptional solutions is periodic in s with period 12). In general, we have w4 (Cs(11) ) = (2s − 1)(Ns − Es )/24. The zeta function is ζ(x) = exp ∞ X Ns s=1 s ! xs = p(x) , (1 − x)(1 − 2x) 29 s Ns Es w4 (Cs11 ) 1 0 0 0 2 8 8 0 48 24 7 3 4 20 20 0 0 0 0 5 128 32 252 6 7 0 0 0 500 20 5100 8 9 480 24 9709 10 1568 8 66495 2112 0 180136 11 12 3956 44 667485 13 8736 0 2981524 8 10894695 14 15968 45578897 15 33408 24 16 58868 20 160691820 721939068 17 132192 0 18 261920 32 2860504416 19 521664 0 11395902232 20 1035380 20 45235525500 21 2089632 24 182592646117 Figure 3.1: Computations for the number of codewords of weight 4 in Cs11 for small values of s. 30 where p(x) = 1 − 3x + 6x2 + 4x3 − 27x4 + 57x5 + 14x6 − 204x7 + 459x8 − 185x9 − 798x10 + 2268x11 − 1545x12 − 2445x13 + 9594x14 − 10020x15 − 1128x16 + 27504x17 − 39408x18 + 17616x19 + 64320x20 − 133984x21 + 128640x22 + 70464x23 − 315264x24 + 440064x25 − 36096x26 − 641280x27 + 1228032x28 − 625920x29 − 791040x30 + 2322432x31 − 1634304x32 − 757760x33 + 3760128x34 − 3342336x35 + 458752x36 + 3735552x37 − 3538944x38 + 1048576x39 + 3145728x40 − 3145728x41 + 2097152x42 . This ζ function can be used to compute a recurrence relation to determine the number of codewords of weight 4 in Cs11 for any value of s. 31 Chapter 4 Elliptic Semiplanes 4.1 Preliminaries We begin by defining terms from design theory, as we will use them here. As defined in [24], an incidence structure is a triple S = (P, B, I), such that: (1) P is a set, the elements of which are called points; (2) B is a set, the elements of which are called blocks; (3) S is an incidence relation between P and B (i.e., I ⊆ P × B). The elements of I are called flags. The incidence matrix for an incidence structure is a 0-1 matrix with |P| columns corresponding to the elements of P, |B| rows corresponding to the elements of B, such that the entry in row B ∈ B, column p ∈ P is a 1 if and only if (p, B) ∈ I. The blocks of an incidence structure are also often called lines in some contexts. We will use the terms interchangeably. Given integers v, k, t, λ with v ≥ k ≥ t ≥ 0 and λ ≥ 1, a t-(v, k, λ) design is an incidence structure such that: (i) |P| = v, (ii) |B| = k for each B ∈ B, (iii) for any set T of t points, there are exactly λ blocks incident with all points in T. 32 A symmetric design is a t-(v, k, λ) design such that the number of points is equal to the number of blocks. More generally, an incidence structure is called square if the number of points is equal to the number of blocks. For our purposes, we are interested only in the case where t = 2. For λ ≥ 1 we will call an incidence structure a λ-design if it is a 2-(v, k, λ) design for some integers v, k. For any set S of nonnegative integers, we will call an incidence structure a regular S-design if it satisfies conditions (i) and (ii) of the definition of a 2-(v, k, λ) design, and also the modified condition (iii0 ): (iii0 ) any two distinct points are incident in a number of blocks which is in the set S. Let p, q be two points in a {0, 1}-design. We call the points parallel if p = q or if p and q are not incident with any common block. Similarly, let B, C be two blocks in a {0, 1}-design. We call the blocks parallel if B = C or if B and C are not incident with any common point. Clearly the relations of parallelism are symmetric and reflexive for both points and lines. We are interested in a certain type of {0, 1}-design, where parallelism is transitive and therefore an equivalence relation. More specifically, we are interested in those designs where the quotient under the equivalence relation also is a design. Definition 4.1.1. An elliptic semiplane is a λ-fold cover of a symmetric λ-design. That is: 1. it is a square regular {0, 1}-design, with n points, n lines, k + 1 points per line, and k + 1 lines per point; 2. no two lines share two points; 3. parallelism is a transitive relation for lines and also for points; 4. the quotient under the equivalence relation of parallelism is a symmetric λdesign. 33 Baker [1] gives an example of an elliptic semiplane with 45 points, 45 lines, and 7 points per line. We show directly that an elliptic semiplane with these parameters is unique up to isomorphism. First we establish a way in which the incidence matrix for a λ-design can be made into an incidence matrix for an elliptic semiplane. Proposition 4.1.2. Let A be the incidence matrix of a λ-cover of a symmetric design. Let m0 , . . . , mλ−1 be formal symbols such that mi × mj = mk where [k] = [i − j], where [n] represents congruence class modulo λ. A λ-cover of A exists if there is a way to replace each nonzero entry of A with some mi in such a way that the resulting matrix B satisfies BB T = (m0 + m1 + · · · + mλ−1 )(J − I) + (k + 1)I. Proof. Let A be the incidence matrix of a symmetric λ-design with n points, n lines, and block size k + 1. Suppose there exists a matrix B such that B is A with each 1 replaced by some mi in such a way that the condition on BB T is satisfied. Now let M be the λ × λ permutation matrix of the cycle (1, 2, . . . , λ), and let Mi = M i for each i = 0, . . . , λ − 1, and let C be the (λn) × (λn) matrix formed by replacing mi by Mi for each i = 0, . . . , λ − 1 and 0 by the λ × λ zero matrix. We claim that C is an incidence matrix for an elliptic semiplane. Each of the matrices Mi contains exactly one 1 in each row and column (i = 1 . . . , λ − 1), and each row and column of B contains k + 1 nonzero entries, each of which is some mi . Therefore each row and column of C, each of which contains k + 1 rows or columns of matrices Mi , respectively, contains exactly k + 1 1s. The matrix C is also square and λn × λn, so has λn points and lines. This shows condition 1 of Definition 4.1.1. Consider two distinct rows of C which cover the same row of B. Since each of the matrices Mi has only one 1 in each column, for each column at most one of these two rows has a 1. Therefore, the lines do not share any points in common; they are parallel. Now consider two distinct rows of C which cover distinct rows of B. More specif- 34 ically, consider the rows λ(c1 − 1) + d1 and λ(c2 − 1) + d2 where 1 ≤ di ≤ λ for (i = 1, 2) and c1 6= c2 , 1 ≤ ci ≤ n for (i = 1, 2). Consider row d of the matrix Mj for j = 0, . . . , λ − 1. Since Mj = M j and M is a permutation sending d to d + 1 (modulo n), the matrix M j has a 1 in position (d, d + j) (modulo lambda). So row d1 of matrix Mj1 has a 1 in the same column as row d2 of matrix Mj2 if and only if d1 + j1 = d2 + j2 (mod λ). That is, if and only if d2 − d1 = j1 − j2 (mod λ). Since the standard coordinate wise product of rows c1 − 1 and c2 − 1 of B is m0 + m1 + · · · mλ−1 , and the value of the product mj1 mj2 is mk such that [k] = [j1 − j2 ], there is exactly one column of B such that the product of the entry in row c1 − 1 and the entry in row c2 − 1 is mk with [k] = [d2 − d1 ]. Therefore two rows of C which cover distinct rows of B have intersection size 1. Combining these results, we see that two rows of C are parallel if and only if they cover the same row of B, and two intersecting rows intersect in a set of size 1. Therefore conditions 2 and 3 hold. Modulo the equivalence relation of parallelism, the incidence matrix C becomes the incidence matrix A of a symmetric λ-design, so condition 4 also holds. Corollary 4.1.3. Let λ be a prime number. A λ-cover of a symmetric design with block size k + 1 exists if there is a way to take the incidence matrix A of the design and replace each 1 of the matrix with a λ root of unity in such a way that the resulting matrix B satisfies BB ∗ = (k + 1)I. Proof. Let A be an incidence matrix of a symmetric λ-design for some prime λ. Let ω be a primitive λ root of unity, and suppose it is possible to replace each 1 in A with a power of ω such that the resulting matrix B satisfies BB ∗ = (k + 1)I. Any two distinct rows of A intersect in exactly λ columns. So the (i, j) entry of BB ∗ for i 6= j is a sum of λ powers of ω. That is, it is a polynomial in ω with nonnegative integer coefficients which sum to λ. But since λ is a prime, the minimal polynomial of ω is 1 + x + x2 + · · · + xλ−1 , and any nonnegative linear combination of powers of ω which is zero must be a multiple of this polynomial. Therefore, for any two distinct rows i1 and i2 of B and for each ` = 0, . . . , λ − 1 35 there is exactly one column j such that Bi1 ,j Bi2 ,j = ω ` . That is, letting m` = ω ` for each ` = 0, . . . , λ − 1, we have the condition in Proposition 4.1.2. We will be concerned primarily with λ-covers of symmetric designs with λ = 2, 3. We show that these covers can be built from incidence matrices of the base design in a certain way, and that all covers can be realized this way, by proving the converse of Corollary 4.1.3 in these cases. Proposition 4.1.4. A 2-cover of a symmetric design with block size k + 1 and λ = 2 is equivalent to taking the incidence matrix A of the design and replacing each 1 of the matrix with a +1 or −1 in such a way that the resulting matrix has BB T = (k + 1)I. Proof. Let C be the 2n × 2n incidence matrix of a 2-cover of a 2-design with block size k + 1, and the rows and columns ordered so that for any m = 1, . . . , n, rows 2m − 1 and 2m are parallel and columns 2m − 1 and 2m are parallel. Let A be the incidence matrix of the 2-design which is the quotient of C by parallelism, and let B be the matrix A with 1 replaced by +1 if the corresponding 2 × 2 submatrix of C is the identity, and −1 if the corresponding submatrix of C is not the identity. That is, if it is the permutation matrix of the cycle (1, 2), call it I 0 . Consider a pair of distinct rows i1 and i2 in A. We say that rows i1 and i2 have intersection of type M in column j if M is a 2×2 0-1 matrix such that the (x, y) entry of M is 1 if and only if the xth row corresponding to row i1 in C (row 2(i1 − 1) + x in C) and the yth row corresponding to row i2 in C (row 2(i2 − 1) + y in C) intersect within the columns of C corresponding to column j of A. Let M (i1 , i2 ; j) be the intersection type of rows i1 and i2 in column j. For any distinct rows i1 and i2 , we define N (i1 , i2 ) = n X M (i1 , i2 ; j) = J, j=1 because none of the lines corresponding to i1 are parallel to lines corresponding to i2 , and each pair of lines intersects in, at most, one point. Now for each i, j ∈ {1, 2, . . . , n}, let Cij be the 2 × 2 submatrix of C corresponding 36 to position (i, j) of A. Then M (i1 , i2 ; j) = Ci1 ,j (Ci2 ,j )T = Ci1 ,j Ci−1 , 2 ,j since the matrices Cij are orthonormal. Now N (i1 , i2 ) is the sum of exactly two nonzero orthonormal 0-1 matrices, so it must be the sum of I and I 0 . So any two distinct rows of B intersect in two columns, one of which has the same entry in the two rows, and one of which has the opposite entry in the two rows. So the for i1 and i2 distinct, we have (BB T )i1 ,i2 = 1 + (−1) = 0. Clearly since A is a design with block size k + 1, we have (BB T )ii = k + 1 for any i. Therefore we have BB T = (k + 1)I. In what follows we will let ω be a primitive cube root of unity. There are 6 different 3 × 3 permutation matrices, which we will denote as             0 0 1 1 0 0 0 1 0            2  1 =  0 1 0 ω =  0 0 1 ω =  1 0 0        0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0             α =  1 0 0 β =  0 0 1 γ =  0 1 0 .       1 0 0 0 1 0 0 0 1 As permutations these are I = e, ω = (1, 2, 3), ω 2 = (1, 3, 2), α = (1, 2), β = (2, 3), γ = (1, 3). So in particular, ω −1 = ω 2 and the other four matrices are self-inverse. When considering 3-covers of symmetric designs, we will be most interested in covers of (15, 7, 3) designs, because these are the only ones known to exist. We prove the following Lemma, which applies to this case, but the conclusions of which may not apply to 3-designs on a larger number of points. 37 Lemma 4.1.5. Suppose M is a 4 × n 0-1 matrix such that (1) the 4 × 4 left submatrix of M is  0 1 1 1       1 0 0 0   ,    1 0 0 0    1 0 0 0 (2) all rows of M have exactly 7 ones, and (3) any two rows of M have common ones in exactly 3 columns. Then n ≥ 17. Proof. Let N be the right 4 × (n − 4) submatrix of M , and for each i = 1, 2, 3, 4, let Ai be the set of column numbers of N such that row i of N has a 1. Without loss of generality, assume that A1 = {1, 2, 3, 4} by (1) and (2). We also have |A2 | = |A3 | = |A4 | = 6 by (1) and (2). For each i = 2, 3, 4, let A0i = A1 ∩ Ai . Then we have |A0i | = 3 for i = 2, 3, 4 and for i, j ∈ {2, 3, 4} with i 6= j, we have |A0i ∩ A0j | ≤ 2 by (1) and (3). But any distinct 3 element subsets of a set of size 4 intersect in 2 points, so we have equality. Let A00i = Ai ∩ {5, 6, 7, . . . , n − 4} for each i = 1, 2, 3, 4. Then |A001 | = 0, and |A00i | = 3 for each i = 2, 3, 4. Also for any distinct i, j ∈ {1, 2, 3, 4}, rows i and j of M have common ones in 3 of the leftmost 8 columns, so |A00i ∩ A00j | = 0. So we have |A002 ∪ A003 ∪ A004 | = 9, and therefore N has at least 4 + 9 = 13 columns, so n − 4 ≥ 13 and n ≥ 17. We use this to prove Proposition 4.1.6, which will enable us to enumerate the 3-covers of (15, 7, 3) designs, ultimately showing that such a cover is unique. Proposition 4.1.6. A 3-cover of a symmetric design with n points, n lines, block size k + 1, and λ = 3, with n < 17 is equivalent to taking the incidence matrix A of the design and replacing each 1 of the matrix with a 1 or ω or ω 2 in such a way that the resulting matrix has BB ∗ = (k + 1)I. 38 Proof. Let C be the 3n × 3n incidence matrix of a 3-cover of a 3-design with block size k + 1, and the rows and columns ordered so that for any m = 1, . . . , n, rows 2m − 2,2m − 1,2m form a parallel class, and columns 2m − 2,2m − 1,2m form a parallel class. Let A be the incidence matrix of the 3-design which is the quotient of C by parallelism, and let B be the n × n matrix A with each 1 replaced by the symbol of the corresponding 3 × 3 submatrix of C, that is, by one of the six symbols 1, ω, ω 2 , α, β, γ. Analogous with the proof of Proposition 4.1.4, for any two distinct rows i1 and i2 of A, and a column j of A, we let M (i1 , i2 ; j) be the 3 × 3 matrix with a 1 in position (x, y) if the xth row of C corresponding with row i1 and the yth row of C corresponding with row i2 intersect in a column corresponding to column j. We again define N (i1 , i2 ) = n X M (i1 , i2 ), j=1 and note that for any distinct i1 and i2 we always have N (i1 , i2 ) = J, since none of the lines of C corresponding to i1 are parallel to any of the lines corresponding to i2 , and each pair of distinct lines intersects in, at most, one point. For each i, j ∈ {1, 2, . . . , n}, let Cij be the 3 × 3 submatrix of C corresponding to position (i, j) of A. We again have M (i1 , i2 ; j) = Ci1 ,j CiT2 ,j . Also N (i1 , i2 ) = J is a sum of 3 of the six matrices I, ω, ω 2 , A, B, C. The matrices I, ω, ω 2 are pairwise orthogonal, as are α, β, γ, and of any two matrices, one from each of the two groupings, none are orthogonal. So the only sums of three nonzero permutation matrices which sum to J are I + ω + ω 2 and α + β + γ. We will show that by reordering the rows and columns of C, and still preserving the condition that parallel classes of rows and columns are adjacent, we can ensure that B contains only the symbols 0, 1, ω, ω 2 . First we choose a row i0 and a column j0 of A such that Aij = 0, and perform row permutations and column permutations 39 on A so that row i0 is moved to row 1 and column j0 is moved to column 1. Then we perform column permutations on A so that the 1s in row 1 are in positions 2 through k +2 and row permutations on A so that the 1s in column 1 are in positions 2 through k + 2. By performing row permutations on a 3×3 permutation matrix, we can transform any matrix into 1 (or any other permutation matrix). The same is true for column operations. So considering each of the nonzero entries in the first row of B, we perform column permutations in the 3 corresponding columns of C to make the entry 1. And we perform row permutations within each set of 3 rows of C corresponding to nonzero entries of the first column of B to make all of these entries also 1. Now the upper left (k + 2) × (k + 2) submatrix of B looks like  0 1 ···    1   ..  . D  1 1     ,    where each row and column of D contains 3 nonzero entries. Consider the first row of D. Since N (1, 2) = J, and all the first row entries are 1, we must have the nonzero entries of the first row of D be either 1, ω, ω 2 or α, β, γ. Suppose they are α, β, γ. Within each set of 3 columns of C corresponding to a column of B numbered from 2 through k + 2, swap the first and second columns. This transformation exchanges 1 ↔ α, ω ↔ β, ω 2 ↔ γ. Then in the rows of C corresponding to the first row of B, swap the first and second rows. This transformation exchanges 1 ↔ α, ω ↔ γ, ω 2 ↔ β. After these two transformations, the first row of D contains nonzero entries 1, ω, ω 2 40 and row 1 of B still contains 1s in positions 2 through k + 2. Consider the column variant of the function M , which given two distinct columns j1 and j2 and a row i gives a matrix showing the positions where corresponding columns of C intersect, just as M does for rows. Then call this function M 0 (i; j1 , j2 ), and let N 0 (j1 , j2 ) = n X M 0 (i; j1 , j2 ). i=1 By duality we have N 0 (j1 , j2 ) = J, so the sum must be of 1, ω, ω 2 or α, β, γ. Therefore, if Bij ∈ {1, ω, ω 2 } for some i, j ∈ {2, 3, . . . , k + 2}, it follows that Bij ∈ {0, 1, ω, ω 2 } for each entry in the same row or column in that submatrix. Suppose there are proper nonempty subsets X, Y ⊂ {2, 3, . . . , k + 2} such that for each x ∈ X, row x of A contains 3 nonzero entries in columns from Y , and for each y ∈ Y , row y of A contains 3 nonzero entries in columns from X. Clearly we must have |X| = |Y |, and |X| ≥ 3. Also, letting X 0 = {2, 3, . . . , k + 2} \ X, Y 0 = {2, 3, . . . , k + 2} \ Y, we see that X 0 and Y 0 must satisfy the same conditions as X and Y . We claim that |X| > 3. In fact, if |X| = 3, then the submatrix with rows X and columns Y 0 is a 3 × 4 zero matrix, and the matrix with rows 1 ∪ X and columns 1 ∪ Y 0 gives a contradiction to Lemma 4.1.5. Therefore |X| > 3, and since X 0 satisfies the same conditions, |X 0 | > 3. But X and X 0 are disjoint subsets of a set of size at most 7, since n < 17 implies k ≤ 7. This is a contradiction, so X and Y do not exist. So the nonzero entries in the matrix D are all 1, ω, ω 2 . Consider now the upper right (k + 2) × (n − k − 2) submatrix. Each column has three nonzero entries, which are either 1, ω, and ω 2 or α, β, and γ. If a column has entries α, β, and γ, then a swap of the first and second corresponding column of C makes these 1, ω, and ω 2 , without altering the upper left submatrix of B. Similarly the lower left (n − k − 2) × (k + 2) submatrix of B can be changed by row operations 41 to contain only entries from 1, ω, and ω 2 without altering the first k + 2 rows of B. It remains to show that the lower right (n − k − 2) × (n − k − 2) submatrix of B contains only entries from 0, 1, ω, and ω 2 . Consider a nonzero entry in the lower right submatrix of B, with coordinates (x, y) in B. Since every line of A intersects every other line of A in 3 points, there are 3 columns among 2 through k + 2 which contain a nonzero entry in row x by considering the intersection of column y with column 1. Call these columns y1 , y2 , and y3 . Also since every pair of distinct points of A have 3 lines in common, there are 3 rows among 2 through k + 2 which contain a nonzero entry in column y by considering the intersection of row x with row 1. Call these rows x1 , x2 , and x3 . Now consider the 4 × 4 matrix formed by rows 1, x1 , x2 , and x3 , and columns 1, y1 , y2 , and y3 , of matrix A. Suppose the entry in position (xi , yj ) is zero for each i, j ∈ {1, 2, 3}. Then the 4 × n matrix formed from rows 1, x1 , x2 , and x3 , contradicts Lemma 4.1.5. Therefore there must be some i, j such that Axi ,yj = 1. Now Bxi ,yj , Bx,yj and Bxi ,y are all nonzero and contained in the set {1, ω, ω 2 }. Therefore, so is Bx,y . This completes the proof. The proof of Proposition 4.1.6 depends on Lemma 4.1.5, and therefore on the condition n < 17. No counterexamples are known for any value of n, and we conjecture that this result is true in general. This could be true if a type of connectivity result can be proven for 3-covers, or perhaps if no more such covers exist with n > 17. This appears to be an open question. Conjecture 4.1.7. A 3-cover of a symmetric design with block size k + 1 and λ = 3 is equivalent to taking the incidence matrix A of the design and replacing each 1 of the matrix with a 1, ω, or ω 2 in such a way that the resulting matrix has BB ∗ = (k + 1)I. This conjecture appears as Theorem 4 in Biggs and Ito [3], but the proof is lacking. At the crucial step it appeals to “similar arguments.” The similar arguments would suffer from the same sort of deficiency addressed by Lemma 4.1.5, and so would only work for small values of k. 42 1 2 3 4 5 6 7 D1 = 8 9 10 11 12 13 14 15 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 3 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 4 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 5 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 6 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 7 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 8 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 9 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 10 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 11 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 12 0 1 0 1 1 0 0 0 0 1 1 0 1 0 1 13 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 14 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 15 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 Figure 4.1: The first of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. 4.2 Existence and uniqueness of an elliptic semiplane with 45 points In this section, we will show that there is a unique elliptic semiplane on 45 points, realized as the 3-fold cover of a (15, 7, 3) design. Nandi [17] classifies all (15, 7, 3) designs up to isomorphism. There are five isomorphism classes, which we will call D1 , D2 , . . . , D5 . The incidence matrices of a representative of each isomorphism class are given in Figures 4.1–4.5 both for completeness, and because they are used extensively in the uniqueness proof for the covering design. To prove uniqueness, we will use the following technical lemma in several places. Lemma 4.2.1. Suppose   0 1 1     M = 1 a b    1 c d is a submatrix in an incidence matrix of a 3-design, where the 1s have been replaced by cube roots of unity as described in Proposition 4.1.6, and each of a, b, c, and d is 43 1 2 3 4 5 6 7 D2 = 8 9 10 11 12 13 14 15 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 3 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 4 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 5 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 6 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 7 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 8 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 9 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 10 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 11 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 12 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 13 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 14 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 15 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 Figure 4.2: The second of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. 1 2 3 4 5 6 7 D3 = 8 9 10 11 12 13 14 15 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 3 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 4 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 5 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 6 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 7 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 8 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 9 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 10 1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 11 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 12 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 13 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 14 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 15 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 Figure 4.3: The third of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. 44 1 2 3 4 5 6 7 D4 = 8 9 10 11 12 13 14 15 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 3 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 4 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 5 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 6 0 0 1 1 1 0 0 0 0 1 1 0 1 1 0 7 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 8 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 9 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 10 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 11 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 12 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 13 0 1 1 0 0 1 0 0 0 1 0 1 0 1 1 14 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 15 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 Figure 4.4: The fourth of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. 1 2 3 4 5 6 7 D5 = 8 9 10 11 12 13 14 15 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 3 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 4 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 6 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 7 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 8 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 9 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 10 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 11 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 12 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 13 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 14 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 15 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 Figure 4.5: The fifth of five nonisomorphic (15, 7, 3) designs given by Nandi [17]. 45 nonzero. Then a = d, b = c, and a 6= b. Proof. Considering the second and third rows, we must have {1, ab, cd} = {1, ω, ω 2 }. In particular, ab 6= 1, so a 6= b, and cd 6= 1, so c 6= d. Suppose b 6= c. Then {a, b, c} = {d, b, c} = {1, ω, ω 2 }. So a = d. We have ab = ca, so ba = ca, and b = c, a contradiction. So we have b = c, and ab = bd, so ba = bd, and a = d. Theorem 4.2.2. There is a unique elliptic semiplane on 45 points and lines with 7 points on a line. Proof. Suppose that such an elliptic semiplane exists. Then it must be a 3-fold cover of a (15, 7, 3) design. Nandi [17] gives a classification of (15, 7, 3) designs up to isomorphism, of which there are five, given in Figures 4.1–4.5. We will show that each of the designs D1 , D2 , D3 , and D4 do not admit a 3-cover. Suppose that a 3-fold cover of the design D1 in Figure 4.1 exists. Consider the line given by row 1 and the non-incident point given by column 5. We isolate the 46 rows and columns corresponding to this line and point as 5 1 2 3 4 9 10 11 1 0 1 1 1 1 1 1 1 2 1 1 1 1 0 0 0 0 5 1 1 0 0 1 0 0 1 7 1 1 0 0 0 0 1 1 9 1 0 1 0 1 1 0 0 11 1 0 1 0 0 1 1 0 12 1 0 0 1 1 0 1 0 14 1 0 0 1 0 1 0 1 We proceed using Proposition 4.1.6 to replace each 1 with 1, ω, or ω 2 . We may assume that the first row and column here have 1s. Then each other row and column must contain one each of 1, ω, and ω 2 . Without loss of generality, assume that those entries in row 2 are 1, ω, and ω 2 , in that order. Let A, B, C, and D be the entries in positions (9, 2), (9, 9), (11, 2), and (11, 9) respectively. We must have C = B and D = A, by Lemma 4.2.1. Also, neither of A andB can be ω because ω is in position (1, 2). Therefore, any row or column that contains A and B must contain ω as the third entry. This implies that (9, 4), (11, 10), and (14, 9) all contain ω. Columns 4 and 10 both contain an ω, so the third entry in row 12, (12, 3) must be ω. Now (14, 3) must be 1, and (14, 11) must be ω 2 . But now consider the 2 × 2 submatrix given by (5, 1), (5, 11), (7, 1), and (7, 11). Column 1 contains a 1 and column 11 contains an ω 2 , which means there is no way to fill in this 2 × 2 matrix consistent with Lemma 4.2.1. We have the following, with undetermined entries blank, and the 2 × 2 matrix which leads to a contradiction 47 marked by X 5 1 2 3 4 9 10 11 1 0 1 1 1 1 1 1 1 2 1 1 ω ω2 0 0 0 0 5 1 X 0 0 0 0 X 7 1 X 0 0 0 0 9 1 0 A 0 ω B 0 0 11 1 0 B 0 0 A ω 0 12 1 0 0 ω 14 1 0 0 1 X 0 0 0 ω ω2 0 Suppose that a 3-fold cover of the design D2 in Figure 4.2 exists. Consider the line given by row 1 and the non-incident point given by column 7. We isolate the rows and columns corresponding to this line and point as 7 1 2 3 4 9 10 11 1 0 1 1 1 1 1 1 1 3 1 1 1 0 0 0 1 0 4 1 1 0 1 0 0 0 1 7 1 1 0 0 0 1 1 0 9 1 0 1 0 1 1 0 0 10 1 0 1 0 1 0 0 1 13 1 0 0 1 1 0 1 0 14 1 0 0 1 0 1 0 1 We proceed using Proposition 4.1.6 to replace each 1 with 1, ω, or ω 2 . We may assume that the first row and column here have 1s. Then each other row and column must contain one each of 1, ω, and ω 2 . Without loss of generality, assume that those entries in row 3 are 1, ω, and ω 2 , in that order. Consider the 2 × 2 nonzero matrix formed by entries (3, 1), (3, 10), (7, 1), and (7, 10). By Lemma 4.2.1 we have that (7, 1) is ω 2 and (7, 10) is 1. 48 Now consider the 2 × 2 submatrix given by (9, 2), (9, 4), (10, 2), and (10, 4). Following Lemma 4.2.1, label these entries as A, B, B, and A respectively. Column 2 contains an ω outside of this 2 × 2 submatrix, so {A, B, ω} = {1, ω, ω 2 }. This means that (13, 4) must be ω, yet this makes (13, 10) have no possible entry, a contradiction, which we mark by X in the table shown here for clarity. 7 1 2 3 4 9 10 11 1 0 1 1 1 1 1 1 1 3 1 1 ω 0 0 0 ω2 0 4 1 ω 0 0 0 0 7 1 ω2 0 0 0 1 0 9 1 0 A 0 B 0 0 10 1 0 B 0 A 0 0 13 1 0 0 ω 0 X 14 1 0 0 0 0 0 Suppose that a 3-fold cover of the design D3 in Figure 4.3 exists. Consider the line given by row 1 and the non-incident point given by column 6. We isolate the rows and columns corresponding to this line and point as 6 1 2 3 4 9 10 11 1 0 1 1 1 1 1 1 1 3 1 1 1 0 0 1 0 0 5 1 1 0 0 1 0 0 1 6 1 1 0 0 1 0 1 0 8 1 0 1 1 0 0 1 0 11 1 0 1 0 0 0 1 1 13 1 0 0 1 1 1 0 0 14 1 0 0 1 0 1 0 1 We proceed using Proposition 4.1.6 to replace each 1 with 1, ω, or ω 2 . We may 49 assume that the first row and column here have 1s. Then each other row and column must contain one each of 1, ω, and ω 2 . Without loss of generality, assume that those entries in row 3 are 1, ω, ω 2 , in that order. Now the entries (5, 1), (5, 4), (6, 1), and (6, 4) form a 2 × 2 nonzero submatrix. By Lemma 4.2.1, label these as A, B, B, and A respectively. We have {A, B} = {ω, ω 2 }, so entry (6, 10) must be 1. Consider now the nonzero 2 × 2 matrix given by (8, 2), (8, 10), (11, 2), and (11, 10). There is no consistent way to fill in this matrix according to Lemma 4.2.1, since column 2 already contains ω and column 10 already contains 1. So this gives a contradiction. For clarity, here is the partially completed matrix, with incomplete entries blank and the contradiction marked by X. 6 1 2 3 4 9 10 11 1 0 1 1 1 1 1 1 1 3 1 1 ω 0 0 ω2 0 0 5 1 A 0 0 B 0 0 6 1 B 0 0 A 0 1 0 8 1 0 X 0 0 X 0 11 1 0 X 0 0 X 13 1 0 0 14 1 0 0 0 0 0 0 0 Suppose that a 3-fold cover of the design D4 in Figure 4.4 exists. Consider the line given by row 2 and the non-incident point given by column 6. We isolate the 50 rows and columns corresponding to this line and point as 6 1 2 3 5 12 13 14 2 0 1 1 1 1 1 1 1 3 1 1 1 0 0 0 1 0 4 1 1 0 1 0 1 0 0 5 1 1 0 0 1 0 0 1 10 1 0 1 0 0 0 1 1 11 1 0 1 0 1 1 0 0 13 1 0 0 1 0 1 0 1 14 1 0 0 1 1 0 1 0 We proceed using Proposition 4.1.6 to replace each 1 with 1, ω, or ω 2 . We may assume that the first row and column here have 1s. Then each other row and column must contain one each of 1, ω, and ω 2 . Without loss of generality, assume that those entries in column 1 are 1, ω, and ω 2 , in that order. There is a nonzero 2 × 2 matrix formed by (4, 3), (4, 12), (13, 3), and (13, 12). By Lemma 4.2.1 label these entries as A, B, B, and A respectively. Then since row 4 also contains ω, we have that {A, B} = {1, ω 2 }, and any row or column with A and B must contain ω as the third nonzero entry. This implies that (13, 14), (14, 3), and (11, 12) are all ω. There is also another 2 × 2 nonzero submatrix, formed by (3, 2), (3, 13), (10, 2), and (10, 13). Label these entries as C, D, D, and C respectively. Since row 3 already contains a 1, we must have {C, D} = {ω, ω 2 }, and any row or column which contains C and D must contain 1 as its third nonzero entry. This implies that (10, 14), (11, 2), and (14, 13) are all 1. Entry (5, 14) now gives a contradiction, because row 5 contains an ω 2 , but column 14 contains 1 and ω. For clarity, we show the partially completed 51 matrix below, with incomplete entries blank and the contradiction shown as X. 6 1 2 3 5 12 13 14 2 0 1 1 1 1 1 1 1 3 1 1 C 0 0 0 D 0 4 1 ω 0 A 0 B 0 0 5 1 ω2 0 0 0 0 X 10 1 0 D 0 0 C 1 11 1 0 1 0 ω 0 0 13 1 0 0 B A 0 ω 14 1 0 0 ω 0 1 0 0 0 So far we have shown that there are no 3-covers of the designs D1 through D4 . It remains to show that there is a unique 3-cover of the design D5 . We also proceed here by using Proposition 4.1.6. So if there is a 3-cover of a (15, 7, 3)-design, then it is a cover of Nandi’s design D5 , from Figure 4.5. This design is isomorphic to the incidence matrix for lines of the 3-dimensional projective geometry over GF (2), P G(3, 2). By Proposition 4.1.6, if there is a 3-cover then it is possible to replace each 1 in D5 with a cube root of unity, such that the resulting matrix B satisfies BB ∗ = 7I. Consider a line and a point not incident with the line. There are 7 points on the line and 7 lines incident with the point. Consider the 7×7 incidence matrix formed by these lines and points. Since the full design is P G(3, 2), this is the incidence matrix of a P G(2, 2). The projective plane P G(3, 2) is unique up to isomorphism, and is isomorphic to the cyclic design generated by {1, 2, 4} over Z7 . For example, in our 52 case, we choose the row 1 and the column 6 from D5 , and obtain 6 1 2 10 9 4 11 3 1 0 1 1 1 1 1 1 1 2 1 1 1 0 1 0 0 0 11 1 0 1 1 0 1 0 0 14 1 0 0 1 1 0 1 0 12 1 0 0 0 1 1 0 1 7 1 1 0 0 0 1 1 0 9 1 0 1 0 0 0 1 1 5 1 1 0 1 0 0 0 1 Let the lower right 7 × 7 submatrix of this 8 × 8 matrix be R. Then we can permute the columns and rows of the matrix D5 to make the matrix be of the form  0 1 ···    1   ..  .    1    0   ..  .  0 1 0 ··· R R R X 0          ,        where X is a cyclic 7 × 7 matrix. The row ordering is {1, 2, 11, 14, 12, 7, 9, 5, 3, 10, 15, 13, 6, 8, 4}, and the column ordering is {6, 1, 2, 10, 9, 4, 11, 3, 13, 12, 8, 5, 14, 7, 15}. 53 The matrix X is  0    1    1   X= 1    0    1  0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1    1    1    0 ,   1    0   0 which is a cyclic matrix. Suppose that there is a 3-cover, and the matrix B is the matrix D5 with each 1 replaced by a root of unity, 1, ω or ω 2 . Without loss of generality, we may assume that each 1 in row 1 or column 6 is replaced by 1 (multiply each row i with a nonzero entry in column 6 by Bi6 and each column j with a nonzero entry in row 1 by B1j ). Each row and each column of the 7 × 7 submatrix above, bordered by column 6 and row 1, must contain a 1, a ω and a ω 2 to satisfy the condition BB ∗ = 7I, specifically that the off diagonal entries are 0. Now consider the upper left R. Without loss of generality, we may assume that the nonzero entries in the first row are 1, ω and ω 2 in that order. When we perform a row permutation operation between columns in this matrix R, we simultaneously perform the corresponding column operation on the upper right matrix R, so that at every step, all 3 matrices R have corresponding nonnegative entries. That is, at any step, (i, j) is nonzero for i, j ∈ {2, . . . , 8} if and only if (i + 7, j) and (i, j + 7) are nonzero. Also, since Xij is nonzero if and only if Rij is zero, at every step it remains the case that (i + 7, j + 7) is nonzero if and only if (i, j) is nonzero. We do the same for column permutation operations. If the second row of the upper right matrix R now does not contain first nonzero entry 1, then the sixth row does (rows 1, 2, and 6 being the rows of R with nonzero entries in column 2, and R12 = ω, R22 = ω 2 ). In that case, perform the row and column operations swapping rows 2 and 6, and making the nonzero entries of the matrix be those of R once again, without moving the the nonzero entries in row 1 or 54 the entry in position (2, 2) at any step. Now suppose the entry in position (2, 3) is not ω. Then it must be ω 2 and position (2, 5) is ω. Swap columns 3 and 5, and then perform more row and column operations without moving columns 1, 2, 3, and 5 and without moving rows 1 and 2 so that the nonzero entries of the matrix are again those of R. Suppose that the entry in position (3, 3) is not 1. Then it must be ω 2 , since (2, 3) is already ω. We now make a sequence of simple deductions which lead to a unique matrix. Column 2 contains 1 and ω, so the last unknown entry, in positions (2, 6) must be ω 2 . Columns 4 and 5 both contain ω 2 , and row 4 has nonzero positions in columns 4, 5, and 7, so (5, 7) is ω 2 . Column 3 contains ω and ω 2 , so (7, 3) is 1. Row 7 contains 1 and column 7 contains ω 2 , so (7, 7) is ω, and the final nonzero entry in row 7, (7, 1) is ω 2 . This makes the final nonzero entry in column 1, (1, 5) a ω, the final entry in column 7, (7, 6) is 1, the final entry in row 6, (6, 6) is ω. Then column 5 contains ω 2 and row 5 contains ω, so (5, 5) is 1. Now the rest of the deductions are rows which contain only one unresolved nonzero entry. Finally, we obtain the matrix  1    0    0   R1 =  0    ω    0  ω2 ω 0 ω 2 0 2 0 0 1 ω 0 ω 0 ω2 ω 0 1 0 0 1 ω 0 0 0 0 1 ω2 ω2 0 0 0 ω 0 1 0 0 0 0    0    0   2  ω .   0    1   ω If instead we suppose position (3, 3) contains 1, then row 3 and column 4 contain 1 and ω 2 respectively, so (3, 4) contains ω. Then (3, 6) must be ω 2 , since row 3 contains 55 1 and ω. The same deductions follow until we get the matrix  1    0    0   R2 =  0   2  ω    0  ω ω 0 ω2 0 2 0 0 1 ω 0 ω 0 1 ω 0 ω2 0 0 1 ω 0 0 0 0 1 ω ω2 0 0 0 1 0 ω2 0 0 0 0    0    0   2  ω .   0    ω   1 The matrix R1 can be obtained from R2 by performing the operation ω ↔ ω 2 and performing column and row permutations. So these two types of covers are isomorphic. So up to isomorphism there is a unique way to fill in the upper left 8×8 submatrix. Assume that the upper left R is filled in as R2 , and consider a column numbered between j + 8 for some j ∈ {1, . . . , 7}. This column shares 3 nonzero entries with columns 1 and j + 1. These 3 corresponding rows of column j + 8 must therefore contain 1, ω, and ω 2 in some order, so that columns 1 and j +8 satisfy the requirement in BB ∗ = 7I. Multiply column j + 8 by a cube root of unity, so that the 1 from column j + 1 is in the same row as the 1 from column j + 8. This multiplication is an isomorphism, so we now must have the ω from column j + 1 in the same row as the ω 2 from column j + 8, and the ω 2 from column j + 1 in the same row as the ω from column j + 1. The same can be done for rows 9–15, so that the cover is isomorphic 56 to one with matrix  0 1    1 1    1 0    1 0    1 0    1 ω2    1 0    1 ω    0 1    0 0    0 0    0 0    0 ω    0 0  0 ω2 1 1 1 1 1 1 0 0 0 0 0 0 ω 0 ω2 0 0 0 1 ω2 0 ω 0 0 1 ω 0 ω2 0 0 0 1 ω2 0 ω 0 0 1 ω 0 ω2 0 0 0 1 ω2 0 ω 0 0 1 ω 0 ω2 0 0 0 1 ω2 0 0 0 0 1 ω 0 ω 0 0 0 1 ω2 ω2 0 0 0 1 ω 0 ω 0 0 0 1 0 ω2 0 0 0 1 ω2 0 ω 0 0 0 ω2 0 ω 0 0 0 0 0 1 ω2 0 ω 0 0 0 1 ω2 0 ω 0 0 0 1 ω2 0 ω 0 0 0 1 ω2 0 ω 0 0 0 1 ω2 0 ω 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0    0    0    0    ω    0    ω2    1 .            0       0   0 Consider the blank entry in position (9, 11). Call this entry x. Consider the product of row 3 with the conjugate of row 9. In column 3, the product is 1ω 2 = ω. In column 11, this product is ω 2 x. So x 6= ω 2 , which means x 6= ω. Consider the product of row 8 with the conjugate of row 9. In column 2, the product is ω1 = ω, and in column 11, this product is ωx, so x 6= 1. This means x = ω 2 . Now consider the blank entry in position (9, 13), and call this entry x. The product of row 3 with the conjugate of row 9 shows that the product in column 2, ω 2 1 = ω 2 , is distinct from the product in column 13, 1x = x, so x 6= ω. The product of row 3 with the conjugate of row 9 shows that the product in column 3, 1ω 2 = ω, is distinct from the product in column 13, ωx, so x 6= 1. This means x = ω 2 . Similarly, consider the blank entry in position (9, 14), and call this entry x. We look at the product of row 7 with the conjugate of row 9 to see that the product in column 3, ω 2 ω 2 = 1, is distinct from the product in column 14, 1x. So x 6= 1. We 57 look at the product of row 4 with the conjugate of row 9 to see that the product in column 5, ωω = 1, is distinct from the product in column 14, ωx. So x 6= ω and x = ω2. Now consider the blank entry in position (9, 15). Call it x. Look at the product of row 7 with row 9. From column 3 we have ω 2 ω 2 = 1, from column 14 we have 1ω 2 = ω, and from column 15 we have ω 2 x. So we have {1, ω, ω 2 } = {1, ω, ω 2 x}. So ω 2 x = ω 2 and x = 1. Altogether, the first row of the lower right 7 × 7 submatrix is (0, 0, ω 2 , 0, ω 2 , ω 2 , 1). Now consider a cyclic rotation of each of the four major 7 × 7 submatrices, by rotating the rows one position to the right, and then the columns one position to the bottom, within each of the four 7 × 7 submatrices. That is, the product of the row permutation (2, 3, 4, 5, 6, 7, 8)(9, 10, 11, 12, 13, 14, 15) and the same column permutation. The three major 7 × 7 submatrices (other than the lower right one) are invariant under this operation, since they are cyclic. The arguments above now apply to the new lower right matrix, showing that the first row is again (0, 0, ω 2 , 0, ω 2 , ω 2 , 1). Applying this operation repeatedly, we see that the lower right 7 × 7 submatrix must also be cyclic. So the cover is unique up to isomorphism, if it exists. Checking 58 that BB ∗ = 7I is now straightforward. We have  0 1    1 1    1 0    1 0    1 0    1 ω2    1 0   B= 1 ω    0 1    0 0    0 0    0 0    0 ω    0 0  0 ω2 1 1 1 1 1 ω 0 ω 2 0 0 1 ω 0 ω2 0 1 ω 0 0 0 1 0 0 0 0 0 0 0 1 ω 2 0 ω 0 0 0 0 0 1 ω2 0 ω 0 0 ω2 0 0 0 1 ω2 0 ω 1 ω 0 ω2 0 0 0 1 ω2 0 0 0 1 ω 0 ω 0 0 0 1 ω2 ω2 0 0 0 1 ω 0 ω 0 0 0 1 0 ω2 0 0 0 1 ω2 0 ω 0 0 0 ω2 0 ω 0 0 0 0 0 ω2 0 ω2 ω2 1 ω2 0 ω 0 0 1 0 0 ω2 0 ω2 0 1 ω2 0 ω 0 ω2 1 0 0 ω2 0 0 0 1 ω2 0 ω ω2 ω2 1 0 0 ω2 0 0 0 1 ω2 0 0 ω2 ω2 1 0 0 ω 0 0 0 1 ω2 ω2 0 ω2 ω2 1 0 0 ω 0 0 0 1 0 ω2 0 ω2 ω2 1 0    0    0    0    ω    0   2  ω    1 .   1   2  ω    2  ω   0    ω2    0   0 The original construction of this elliptic semiplane is due to Baker [1]. In Baker’s construction, there are four types of 3 × 3 submatrices, corresponding to our 1, α, β, and γ. By uniqueness, Baker’s elliptic semiplane is isomorphic to B. Ito [10] states this same uniqueness result in the context of the corresponding bipartite graph, but only gives the proof beginning with the P G(3, 2), Nandi’s design D5 . We now give an alternative construction of the elliptic semiplane in terms of the Petersen graph. For each i = 1, 2, 3, let Ai be the set of elements of the form (S, i)A , where S is a set of two disjoint pairs in {1, 2, 3, 4, 5}, that is, an edge in the Petersen graph, and let Bi be the set of elements of the form (S, i)B with the same condition on S. 59 Let G be a bipartite graph with vertex set (A1 ∪ A2 ∪ A3 ) ∪ (B1 ∪ B2 ∪ B3 ). Let d(x, y) denote the distance between x and y in the line graph of the Petersen graph. Then in G, (S, i)A is adjacent to (T, j)B if and only if one of the following conditions is true (i) i ≡ j(mod 3) and d(S, T ) = 0, (ii) i ≡ j − 1(mod 3) and d(S, T ) = 3, or (iii) i ≡ j − 2(mod 3) and d(S, T ) = 1. The following proposition shows that the configuration represented by the bipartite graph G with blocks A1 ∪ A2 ∪ A3 and points B1 ∪ B2 ∪ B3 satisfies conditions 1 and 2 of Definition 4.1.1. Proposition 4.2.3. The graph G has valency 7 and girth 6. Proof. Considering the line graph of the Petersen graph, because Sym(5) acts as graph automorphisms, we need only consider the vertex {{1, 2}, {3, 4}}. For simplified notation, we will write (ij)(k`) for {{i, j}, {k, `}}. The vertices at distance 1 are (12)(35), (12)(45), (15)(34), (25)(34). The vertices at distance 2 are (14)(35), (24)(35), (13)(45), (23)(45), (15)(23), (15)(24), (13)(25), (14)(25). The vertices at distance 3 are (13)(24), (14)(23). In particular, there are 2 vertices at distance 3 and 4 vertices at distance 1, so the 60 degree of the vertex ((12)(34), 1)A is 1 + 2 + 4 = 7, and by symmetry G is regular of valency 7. Now to see G has girth 6 we must show that there are no 4 cycles in G. Suppose there is a 4 cycle. Then without loss of generality, it contains ((12)(34), 1)A . In fact, suppose the cycle is ((12)(34), 1)A , (Sx , x)B , (Sy , y)A , (Sz , z)B , ((12)(34), 1)A . Consider the possible triples (x, y, z). Let q be the sum of the distances q = d((12)(34), Sx ) + d(Sx , Sy ) + d(Sy , Sz ) + d(Sz , (12)(34)). In order for this to be a cycle, q must be even. Each of the terms in the sum is 1, 3, or 0, so each term is even if and only if it is 0. So in the sequence (1, x, y, z, 1) the number of elements which are equal to the next element must be even. We will call this the q even rule. Clearly (x, y, z) is equivalent to (z, y, x) by reversing the order of the cycle. We break down the cases as follows, where for those cases with x 6= z, we always consider the case where z < x. There are 18 possible triples (x, y, z) with z ≤ x. Case (x, y, z) = (1, 1, 1), (2, 1, 1), (3, 1, 1), (2, 2, 2) or (3, 3, 3). Since there is only one edge between Ai and Bi for each i, these cases each contain a backtrack, so they do not exist. Case (x, y, z) = (1, 2, 1) or (1, 3, 1). In this case Sx = (12)(34) and Sz 6= (12)(34), because otherwise this would be a backtrack, so this case also does not exist. Case (x, y, z) = (2, 2, 1) or (3, 3, 1). In either case, we have Sx = Sy and Sz = (12)(34), but d((12)(34), Sx ) 6= d(Sy , Sz ), a contradiction. Case (x, y, z) = (3, 3, 2), (3, 2, 1), (2, 3, 1), or (3, 2, 2). These cases violate the q even rule. Case (x, y, z) = (2, 1, 2). Each step is a step of distance 3 in the projection onto the line graph of the Petersen graph. But the set of vertices at distance 0 or 3 from 61 (12)(34) has size 3. Considering this set of 3 vertices as a triangle, any path of length 4 must contain backtracks (which correspond to backtracks in the path on the full graph G, since we are alternating between A1 and B2 ), or not end at the same vertex it began. Either way, this is a contradiction. Case (x, y, z) = (3, 1, 3). Similar to the previous case, we consider the projection onto the underlying line graph of the Petersen graph. Each step is a step of distance 1. The line graph of the Petersen graph contains triangles, but no cycles of length 4, so this case also cannot happen. Case (x, y, z) = (3, 1, 2), (3, 2, 3), or (2, 3, 2). Each of these cases corresponds to two steps of distance 1 followed by two steps of distance 3, by symmetry and rotating the cycles. So, in the projection onto the line graph of the Petersen graph, these cycles correspond to successive steps of distance 1, 1, 3, 3. After the first two steps of length 1, we end up at vertex Sy 6= (12)(34), and d((12)(34), Sy ) < 3. This is a contradiction, since Sy , Sz , (12)(34) form a triangle with steps of distance 3. We claim that this is isomorphic to our construction G, and we complete the argument by showing that the Petersen construction represents an elliptic semiplane and then applying our uniqueness result, Theorem 4.2.2. Proposition 4.2.4. The graph G corresponds to an elliptic semiplane on 45 points. Proof. To see that conditions 3 and 4 of Definition 4.1.1 apply, let S be an edge of the Petersen graph and consider the three blocks corresponding to (S, 1)A , (S, 2)A , and (S, 3)A . The union of the points contained in these lines are all those points of the form (T, j)B , where d(S, T ) ∈ {0, 1, 3} and j ∈ {1, 2, 3}. So the union of these three blocks contains 21 distinct points. Therefore these three blocks are parallel. Since each block is parallel to exactly two other blocks, parallelism is transitive. The parallelism quotient graph of G is the bipartite graph with vertex set consisting of all vertices of the form SA or SB , where S is a union of two disjoint pairs from {1, 2, 3, 4, 5}. In other words, a vertex of G with projection onto the first coordinate. A vertex SA is adjacent to a vertex TB if and only if d(S, T ) ∈ {0, 1, 3}, where d 62 represents distance in the Petersen line graph. We need to show that in the block design corresponding to this quotient graph, each pair of blocks intersects in 3 points. Let (S1 )A and (S2 )A be vertices in the quotient graph, with S1 6= S2 . Let Γi = {T : d(Si , T ) ∈ {0, 1, 3}} for i = 1, 2. We must show that |Γ1 ∩ Γ2 | = 3. There are three cases. Suppose d(S1 , S2 ) = 1. Then S1 , S2 ∈ Γ1 ∩ Γ2 . Distance 3 or 0 is an equivalence relation on vertices in the Petersen line graph, so S ∈ (Γ1 ∩ Γ2 ) \ {S1 , S2 } is true if and only if d(S1 , S) = 1 and d(S2 , S) = 1. The Petersen graph has valency 3, so there is exactly one such S, and |Γ1 ∩ Γ2 | = 3. Now suppose d(S1 , S2 ) = 2. Without loss of generality, suppose S1 = {12, 34}. Then the vertices at distance 3 from S1 are {13, 24} and {14, 23}. Each has valency 4, and the distance between them is 3, so there are at least 8 vertices Y at distance 2 from S1 such that there is a vertex Z with d(Y, Z) = 1 and d(S1 , Z) = 3. One of these vertices Y must be S2 , so there is exactly one vertex in Γ1 ∩ Γ2 at distance 3 from S1 . Similarly, there is exactly one vertex in Γ1 ∩ Γ2 at distance 3 from S2 . Also for any pair of vertices at distance 2 in the Petersen line graph, there is a unique vertex at distance 1 from both of them (since the Petersen graph has no triangles or 4-cycles). So |Γ1 ∩ Γ2 | = 3. Now suppose d(S1 , S2 ) = 3. Then the equivalence class of vertices at distance 3 is exactly Γ1 ∩ Γ2 . This completes the proof of our isomorphism result. We also state the following Proposition, for which the proof is a direct consequence of the uniqueness result. Proposition 4.2.5. As block designs, the graph G constructed from the Petersen line graphs is isomorphic to the incidence matrix given by B in the proof of Theorem 4.2.2. Proof. This follows immediately from Theorem 4.2.2. 63 4.3 Automorphisms and dualities Let (P, L) be the Baker elliptic semiplane with point set P and line set L. As proven in the previous section, the Baker semiplane is the unique 3-cover of a (15, 7, 3) design, up to isomorphism. An automorphism is a pair of permutations σ ∈ SymP and τ ∈ SymL such that any p ∈ P is incident to l ∈ L if and only if σ(p) is incident to τ (l). Let A be the set of automorphisms of the Baker semiplane. The set A forms a group. A duality is a pair of bijections α : P → L and β : L → P such that each p ∈ P is incident to l ∈ L if and only if β(l) is incident to α(p). The product of two dualities is an automorphism. Let A+ be the set of all dualities and automorphisms. Then A+ is a group with [A+ : A] either 1 or 2. Let F be the subgroup of A which takes points to parallel points and lines to parallel lines. We call F the fiber stabilizer of A, and we let Ā = A/F , Ā+ = A+ /F . Our main theorem is the following: Theorem 4.3.1. (a) F is isomorphic to Z3 , (b) A is isomorphic to 3 · Alt7 , and (c) A+ is isomorphic to 3 · Sym7 . A result given by Ito [10] states that A+ = A. There seems to be a subtle mistake in the proof, as it contradicts Theorem 4.3.1. First, we prove Theorem 4.3.1(a) directly by considering row and column operations on 3 × 3 submatrices of the 45 × 45 incidence matrix given in Theorem 4.2.2. Proof of Theorem 4.3.1(a). As in the previous section, we label the different 3 × 3 permutation matrices as 1, ω, ω 2 , α, β, and γ. Row and column permutations act on the set of six permutation matrices according to Figures 4.6 and 4.7. An element of f ∈ F acts by permuting the rows and columns of the 45 × 45 incidence matrix such that parallel lines are sent to parallel lines and parallel columns 64 are sent to parallel columns. This means that the set of columns or rows numbered {1 + 3n, 2 + 3n, 3 + 3n} is fixed globally for each n = 0, 1, . . . , 14. Let rn be the row operation on rows 1 + 3n, 2 + 3n, 3 + 3n, and cn be the column operation on columns 1 + 3n, 2 + 3n, 3 + 3n for each n = 0, . . . , 14. Then f is determined by choices of each rn and cn . We will show that r0 = r1 = · · · = r14 = c0 = c1 = · · · = c14 , and that r0 ∈ Alt3 ∼ = Z3 . Further, each of the three choices of permutation is an automorphism, so F ∼ = Z3 . Suppose that r0 = 1 ∈ Sym(3). Then in order to preserve the entries in the first row of the matrix B, we must have c1 = c2 = · · · = c7 = 1. Each row has a nonzero entry in one of these 7 columns, and that entry is unchanged, so we have r0 = r1 = · · · = r14 = 1. Each column has a nonzero entry, so we have c0 = c1 = · · · = c14 = 1. Clearly this gives the identity automorphism. Now suppose r0 ∈ Alt(3)\{1}. Then, according to Figures 4.6 and 4.7, in order to preserve the nonzero entries in the first row of B, we must have c1 = c2 = · · · = c7 = r0 . Each row has a nonzero entry in one of these 7 columns, which has been acted upon by the column operation r0 . The row operation r0 acting on the set {1, ω, ω 2 } is the inverse to the column operation r0 . Therefore r0 = r1 = r2 = · · · = r14 . Similarly c0 = c1 = · · · = c1 4 = r0 , since every column has a nonzero entry in some row. This gives an automorphism of the incidence matrix of order 3. Finally suppose r0 ∈ Sym(3) \ Alt(3). Then in order to preserve the entries in the first row of B, we must have c1 = c2 = · · · = c7 = r0 . Now consider the entries in positions (2, 2) and (2, 3) in the matrix B. These are both acted on by the column permutation r0 . But considering the odd permutations in Figures 4.6 and 4.7, there is no row permutation r1 such that the row operation r1 composed with the column operation r0 would fix both 1 and ω. This is a contradiction. Therefore r0 ∈ Alt(3), each such choice giving exactly one automorphism. So F is isomorphic to Alt(3) = Z3 . 65 Row operation 1 (1,2) (1,3) (2,3) (1,2,3) (1,3,2) Permutation on the set of 3 × 3 permutation matrices 1 (1, α)(ω, γ)(ω 2 , β) (1, γ)(ω, β)(ω 2 , α) (1, β)(ω, α)(ω 2 , γ) (1, ω 2 , ω)(α, γ, β) (1, ω, ω 2 )(α, β, γ) Figure 4.6: Action of row permutations on the six 3 × 3 permutation matrices. Column operation 1 (1,2) (1,3) (2,3) (1,2,3) (1,3,2) Permutation on the set of 3 × 3 permutation matrices 1 (1, α)(ω, β)(ω 2 , γ) (1, γ)(ω, α)(ω 2 , β) (1, β)(ω, γ)(ω 2 , α) (1, ω, ω 2 )(α, γ, β) (1, ω 2 , ω)(α, β, γ) Figure 4.7: Action of column permutations on the six 3 × 3 permutation matrices. In order to prove the rest of Theorem 4.3.1, we set aside some intermediate results as Lemmas. First, we use a group construction of the graph G from Proposition 4.2.3. In fact, let S be the elements of Sym3 and let H be the conjugacy class in Alt5 of elements of order 2 (of which there are 15, corresponding to the vertices of the Petersen line graph). Let G0 be the graph with vertices S × H and (s, g), (t, h) ∈ G0 adjacent if and only if one of the following is true: (i) st−1 = (1, 2) and |gh| = 1, (ii) st−1 = (1, 3) and |gh| = 2, or (iii) st−1 = (2, 3) and |gh| = 3 This adjacency condition is symmetric, since whenever st−1 ∈ {(1, 2), (1, 3), (2, 3)}, 66 we have |st−1 | = 2, so that st−1 = ts−1 . Proposition 4.3.2. The graph G is isomorphic to the graph G0 . Proof. Identify the elements in the 6 copies of the Petersen line graphs of G and G0 by identifying each of the copies of the Petersen line graph in G with one in G0 in the following way: A1 ∼ 1, A2 ∼ (1, 2, 3), A3 ∼ (1, 3, 2), B1 ∼ (1, 2), B2 ∼ (1, 3), B3 ∼ (2, 3). Now, suppose (s, g) and (t, h) are adjacent. Then st−1 ∈ / Alt3 , so one of s, t corresponds to an Ai and the other to a Bj for some i, j ∈ {1, 2, 3}. It is now easy to check given the correspondence above, that (i) st−1 = (1, 2) if and only if i ≡ j(mod 3), i ≡ j(mod 3) and d(S, T ) = 0, (ii) st−1 = (1, 3) if and only if i ≡ j − 1(mod 3), and (iii) st−1 = (2, 3) if and only if i ≡ j − 2(mod 3). It remains to show that |gh| determines the distance between g and h in the Petersen line graph. In fact, it suffices to consider g = (1, 2)(3, 4), and to consider Table 4.1. This group theoretic construction can be immediately used to establish a few properties of the automorphism group of the Baker elliptic semiplane, which we set aside as Lemma 4.3.3. These properties will combine with observations about the incidence matrix given in Theorem 4.2.2 to give more information about the automorphism group A+ , since Theorem 4.2.2 proves that these two objects are isomorphic as graphs. Lemma 4.3.3. (a) The fiber stabilizer F ∼ = Z3 is inverted by A+ /A of order 2. (b) A+ has a subgroup B + isomorphic to Sym3 ×Sym5 whose image in Ā+ ≤ Sym8 is isomorphic to Z3 × Sym5 . 67 h gh |gh| d(g, h) (12)(34) 1 1 0 (12)(35) (345) 3 1 (354) 3 1 (12)(45) (13)(24) (14)(23) 2 3 5 2 (13)(25) (15234) (13)(45) (12354) 5 2 (14)(23) (13)(24) 2 3 5 2 (14)(25) (15243) (14)(35) (12453) 5 2 5 2 (15)(23) (13425) (15)(24) (14325) 5 2 (125) 3 1 (15)(34) (23)(45) (13542) 5 2 (24)(35) (14532) 5 2 (25)(34) (152) 3 1 Table 4.1: Correspondence between distance from g and order of |gh| in the Petersen line graph, where g = (12)(34). (c) B = B + ∩ A has index 2 in B + . Proof. The group Sym3 × Sym5 acts faithfully as a group of automorphisms on the vertices of G0 by (z, a) : (s, g) 7→ (sz, a−1 ga). Let B + be this subgroup of A+ . The subgroup Alt3 × 1 ≤ B + is a subgroup of the fiber stabilizer F . By Theorem 4.3.1(a), we have Alt3 × 1 = F . Consider the element h = ((12), 1) ∈ B + . This element h swaps the two parts of the bipartite graph G0 , so is a duality. Let B = B + ∩ A. Then we have [A : B] = [A+ : B + ], and [A+ : A] = 2, so [B + : B] = 2. Let k ∈ F be the element ((123), 1) in B + . Then hkh−1 = ((132), 1) = k −1 . So F is inverted by B + /B, and therefore by A+ /A. Lemma 4.3.4. (a) Ā is isomorphic to a subgroup of GL4 (2) ∼ = Alt8 . (b) Ā+ is isomorphic to a subgroup of GL4 (2).2 ∼ = Sym8 . 68 (c) A contains an element of order 7. Proof. By Theorem 4.2.2, we know that the elliptic semiplane is unique and that its quotient by parallelism is isomorphic to P G(3, 2). The automorphism group of P G(3, 2) is GL4 (2), because P G(3, 2) can be considered as GL(2)4 , where each 1dimensional subspace is a point and each 3-dimensional subspace is a line. It is well known that GL4 (2) ∼ = Alt8 . This proves (a). Since [A+ : A] ≤ 2, we know that A is a normal subgroup of A+ . A duality of order 2 necessarily generates a subgroup Z2 , such that Z2 ∩ A = 1. By Lemma 4.3.3(a), such a duality exists, and it does not commute with A. This shows that A+ 6= A × Z2 , and therefore A+ is a subgroup of an indirect extension of Alt8 of degree 2, which must be Sym8 . Part (c) follows because the product of the row permutation (2, 3, 4, 5, 6, 7, 8)(9, 10, 11, 12, 13, 14, 15) and the same column permutation on the matrix representing the elliptic semiplane in the proof of Theorem 4.2.2, leaves the matrix invariant. These permutations have order 7. Lemma 4.3.5. (a) Ā+ is isomorphic to Sym7 or Sym8 . (b) Ā is isomorphic to Alt7 or Alt8 . Proof. By Lemma 4.3.3(b), Ā+ contains an element of order 2 which commutes with a subgroup isomorphic to Sym5 . In particular, Ā+ ≤ Sym8 contains commuting elements of order 2 and 5. Let g ∈ Sym8 be an element of order 5, and let h ∈ Sym8 be a commuting element of order 2. Then g must consist of cycles of length dividing 5, so g is a 5-cycle. Similarly, h is a product of disjoint transpositions. Without loss of generality, let g = (12345) and consider hgh−1 . We have hgh−1 = (h(1), h(2), h(3), h(4), h(5)), 69 so h(1) ∈ {1, 2, 3, 4, 5}. The value of h(1) determines the value of h(2), h(3), h(4), and h(5), and clearly powers of g commute with g, so the only elements commuting with g are powers of g. No power of g has order 2, so h must fix the set {1, 2, 3, 4, 5}. Therefore h ∈ Sym{6, 7, 8}, and h is a 2-cycle. Also, by Lemma 4.3.4(c), Ā+ contains an element of order 7. It is well known that in Symp for a prime p, a p-cycle and a transposition generate all of Symp . Let h ∈ Sym8 be a transposition and let k ∈ Sym8 be a 7-cycle. If the support of h is contained in the support of k, then the elements generate Sym7 . Otherwise, the support of h is contained in the support of hkh−1 , and the elements h and hkh−1 generate a subgroup isomorphic to Sym7 . In this case, let H = hh, ki. We have [Sym8 : H] ≤ 4, and H 6≤ Alt8 . But there are no subgroups of index 4 in Sym8 (otherwise there would be a normal subgroup N of Sym8 with index 4 ≤ [Sym8 : N ] ≤ 4! = 24, but Alt8 is the only proper normal subgroup). Therefore H = Sym8 . This proves part (a). Part (b) follows since the only subgroups of index 2 are Alt7 and Alt8 , respectively. Corollary 4.3.6. (a) A is isomorphic to 3 · Alt7 , Z3 × Alt7 , or Z3 × Alt8 . (b) A+ is isomorphic to 3 · Sym7 , (Z3 × Alt7 ).2, or (Z3 × Alt8 ).2. Proof. The fiber stabilizer F of order 3 is centralized by the perfect group Ā. In [20], Schur proves that the only possible extensions are those given in the statement of the Corollary. Lemma 4.3.7. A is isomorphic to 3 · Alt7 , and A+ is isomorphic to 3 · Sym7 . Proof. Suppose to the contrary that A is not isomorphic to 3 · Alt7 . Let A0 = (A+ )00 . By Corollary 4.3.6, we have A0 = A00 , and A0 is Alt7 or Alt8 . We claim that A0 has six orbits of length 15 on the vertices of G0 . Notice that A0 ∩ F = 1, and A0 is a quotient by duality, so A0 acts faithfully on the set of 15 point fibers and also the set of 15 line fibers. Consider the action on 70 the set of point fibers as a subgroup of GL4 (2), where the point fibers are points of P G(3, 2). A point of P G(3, 2) is a 1-dimensional subspace, so up to change of basis, the global stabilizer of a fiber in GL4 (2) = Alt8 is represented by the set of invertible matrices which fix the vector (1, 0, 0, 0)T . This is the set of all invertible matrices of the form   1 x y z      0   ,    0  M   0 where x, y, z ∈ GF (2) and M ∈ GL3 (2). This is a split extension of GL3 (2) by the elementary abelian group 23 , which we denote 23 : GL3 (2). This subgroup has index 15 in A0 . The global fiber stabilizer in Alt7 must then be a subgroup of index 8 in the group 23 : GL3 (2) above. The only possibilities are GL3 (2) and 2m : H where 1 ≤ m ≤ 3 and H ≤ GL3 (2) with [GL3 (2) : H] = 23−m . But GL3 (2) is a simple group, and if a group has a subgroup of index 4 then it has a normal subgroup of index ≤ 4! = 24, which is a contradiction. Therefore m = 3. Every subgroup of index 8 in GL3 (2) must contain a 7-Sylow subgroup. Let n7 be the number of 7-Sylow subgroups of GL3 (2). We have n7 |24, 7|(n7 − 1), and n7 6= 1, since that would mean the 7-Sylow subgroup is normal, contradicting the simplicity of GL3 (2). Therefore n7 = 8, and the normalizer of a 7-Sylow subgroup has index 8 in GL3 (2). So every index 8 subgroup of GL3 (2) is of the form Z7 : Z3 . So the global stabilizer of a fiber in Alt7 is either GL3 (2) or 23 : Z7 : Z3 . But Alt7 does not contain a subgroup 23 : Z7 : Z3 , because in particular, the 2-Sylow subgroups of Alt7 have order 8, and are self normalized. So if A0 is Alt8 then the fiber stabilizer is 23 : GL3 (2), and if A0 is Alt7 then the fiber stabilizer is GL3 (2). Both of these groups are perfect, so they have no abelian quotients, and therefore they have no quotient which is a subgroup of Sym3 . Therefore the global stabilizer of a fiber must actually be the stabilizer of each of the 71 three points in that fiber. Thus every point stabilizer in A0 has index 15, and A0 has six orbits of length 15. These six orbits are, therefore, the same as the six orbits of length 15 of (Sym3 × Sym5 )00 = Alt5 in the construction of the graph G0 in Proposition 4.3.2. Let X = (S, i)C ∈ G, where G is the graph in Proposition 4.2.3. We let x = 12, 34 and consider the point stabilizer H = (A0 )(x,1)A of x in the group A0 . We have [A0 : H] = 15, so |H| = 168 = 7 · 6 · 4. We will show that H has no element of order 7, and thereby a contradiction, which will prove the Lemma. Clearly we have (x, 1)B fixed, and in fact for any set of points from the same orbit of size 15 which is globally fixed, the corresponding set swapping A for B is also fixed globally. Consider the two points at distance 3 in the Petersen line graph from 12, 34. Call them y and z. Then the pair of points {(y, 2)B , (z, 2)B } is fixed globally, because there are edges to these points from (x, 1)A . Since being at distance 3 or distance 0 is an equivalence relation in the Petersen line graph, the set {(x, 1)A , (y, 1)A , (z, 1)A } is also fixed globally, and the set {(x, 2)B , (y, 2)B , (z, 2)B } is also fixed globally. Therefore the point (x, 2)B is fixed. Repeating this argument for (x, 2)A which is a fixed point, we can see that (x, i)C is fixed for any i = 1, 2, 3, and any C ∈ {A, B}. Also, the set {(y, i)C , (z, i)C } is fixed globally for any i = 1, 2, 3, and any C ∈ {A, B}. Similarly, we know that the points at distance 1 from x in each of the Petersen line graphs corresponding to the orbits of size 15 are globally fixed sets of size 4. For each i = 1, 2, 3, and for each C ∈ {A, B}, let (X, i)C denote that set of 4 points which is fixed globally in Ci . For each i = 1, 2, 3, and for each C ∈ {A, B}, let (Y, i)C denote the set of points at distance 1 from y in the Petersen line graph Ci , and (Z, i)C the set of points at distance 1 from z in same. We always have (Y, i)C ∪ (Z, i)C fixed globally for each i = 1, 2, 3, and for each C ∈ {A, B}. In any case, the two indicated subsets of size 4 in this union are either each fixed globally, which happens whenever y and z are fixed pointwise, or they are swapped globally which happens whenever y and z are swapped. 72 Therefore, in the point stabilizer H, the orbits are of maximum lengths 1, 2, 4, 8. For each group element, each of the length 8 orbits is either split into two orbits of size 4 or the two sets of size 4 in the orbit are swapped, giving only even length cycles. In any case, there cannot be a cycle of length 7, proving the Lemma. 4.4 Cage graphs Definition 4.4.1. Let f (v, g) be the minimum number of vertices such that a regular graph of valency v and girth g exists. A graph of order f (v, g) with valency v and girth g is called a (v, g) cage. For every v and g, the value f (v, g) has been proven to exist by Erdös and Sachs [21], but only a few cases have been completely solved. Let g be an even number g = 2r ≥ 4 and v ≥ 3. Then we have f (v, g) ≥ 2{1 + (k − 1) + (k − 1)2 + · · · + (k − 1)r−1 }. For any graph G with valency v and girth g, let e = f (v, g) − |G|. This e is called the excess of G. If a graph with girth 6 has excess e = 0, then it is the incidence graph of a projective plane. For an edge {σ, τ } in a graph G of girth 6, let Xστ be the set of vertices which are at distance ≥ 3 from both τ and σ. Xστ is called the excess of the edge {σ, τ }. The next theorem shows that a graph with small excess is bipartite, and if it satisfies another condition on the excess of each edge, then it is the incidence graph of an elliptic semiplane. Theorem 4.4.2. [2] Let G be regular with valency k ≥ 3, girth 6, e ≤ k − 2. Then G is bipartite. Further suppose that for each edge {σ, τ } of G the excess set Xστ induces a subgraph with just 21 e edges. Then G is a λ-fold cover of a graph representing a λ-design with λ = 12 e + 1, and so is an elliptic semiplane. In the case of excess e = 2, the excess Xστ of every edge has at most 1 edge since Xστ has only two vertices. So Theorem 4.4.2 applies, and shows that there must exist 73 a certain design with λ = 2, also known as a biplane, in order for the graph with excess e = 2 to exist. Furthermore it must have a 2-fold cover, an elliptic semiplane. In the particular case of k = 7, there is no biplane of the appropriate parameters, as shown in [4]. So a (7, 6) cage graph has excess of at least 4. In fact, we have constructed a graph with valency 7, girth 6 and e = 4, by Proposition 4.2.3. A (7, 6) cage graph with 90 vertices is also given by O’Keefe and Wong [18] [19], using a computer construction. Their computations further show that the (7, 6) cage is unique up to isomorphism. With a better understanding of the excess of an edge in a (7, 6) graph on 90 vertices, or in general for excess e = 4 and valency k, we may be able to use Theorem 4.4.2 to show that the (7, 6) cage, or perhaps a girth 6 cage with some other valency, is an elliptic semiplane without the use of a computer. Thus far, efforts in this direction have been unsuccessful. In the previous section we gave a simple construction using the line graph of the Petersen graph. These two constructions are both 3-fold covers, that is, elliptic semiplanes, so are isomorphic by Theorem 4.2.2, which we have proven without appealing to computer results. The computer results of O’Keefe and Wong further prove the following Theorem, which we have been unable to prove without the use of a computer. Theorem 4.4.3. [18] A (7, 6)-cage is the incidence graph of an elliptic semiplane, a 3-fold cover of a symmetric 2-(15, 7, 3) design. 74 Bibliography [1] Baker, R. D., Note: an elliptic semiplane, J. Combin. Theory (Ser. A) 25 (1978), 193–195. [2] Biggs, N. L.; Ito, T., Graphs with even girth and small excess, Math. Proc. Camb. Phil. Soc. 88 (1980), 1–10. [3] Biggs, N. L.; Ito, T., Covering graphs and symmetric designs, “Finite geometries and designs (Proc. Conf. Chelwood Gate, 1980),” 40–51, London Math. Soc. Lecture Note Ser., 49, Cambridge Univ. Press, Cambridge-New York, 1981. [4] Cameron, P. J., Biplanes, Math Z. 131 (1973), 85–101. [5] Egorychev, G. P., The Solution of van der Waerden’s Problem for Permanents, Adv Math 42 (1981), 299–305. [6] Falikman, D. I., Proof of the van der Waerden Conjecture Regarding the Permanent of a Doubly Stochastic Matrix, Math Notes 29 1981, 475–479. [7] Gold, R., Maximal recursive sequences with 3-valued recursive crosscorrelation functions, Information Theory, IEEE Transactions on 14 (1968), 154–156. [8] Hernando, Fernando; McGuire, Gary, Proof of a Conjecture on the Sequence of Exceptional Numbers, Classifying Cyclic Codes and APN functions. [9] Hartshorne, Robin, Algbebraic Geometry, Springer (1977). [10] Ito, T., On a graph of O’Keefe and Wong, J. Graph Th. 5 (1981), 87–94. 75 [11] Janwa, H.; McGuire, G.; Wilson, R. M., Double-error-correcting cyclic codes and absolutely irreducible polynomials over GF(2), J. Algebra 178 (1995), no. 2, 665-676. [12] Janwa, H.; Wilson, R. M., Hyperplane sections of Fermat varieties in P3 in char. 2 and some applications to cyclic codes, Applied algebra, algebraic algorithms and error-correcting codes (San Juan, PR, 1993), 180-194, Lecture Notes in Comput. Sci., 673, Springer, Berlin, 1993. [13] Kasami, T., The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes, Information and Control 18 (1971), 369-394. [14] Knuth, Donald E., A Permanent Inequality, Am Math Mon 88 (1981), 731–740. [15] Lagarias, J. C., The van der Waerden Conjecture: Two Soviet Solutions, Some journal, 130–133. [16] Minc, Henryk, A Note on Egorycev’s Proof of the van der Waerden Conjecture, Linear Multilinear A 11 (1982), 367–371. [17] Nandi, H., A further note on non-isomorphic solutions of incomplete block designs, Sankya 7 (1946), 313–316. [18] O’Keefe, M.; Wong, P. K., The smallest graph of girth 6 and valency 7, J. of Graph Th. 5 (1981), 79–85. [19] O’Keefe, M.; Wong, P. K., On certain regular graphs of girth six, Ars Comb. 17 (1984), 113–116. [20] Schur, I., Über die Darstellungen der symmetrischen und der alternierenden Gruppen durch gebrochene lineare Substitution, J. Rein Angew. Math. 139 (1911), 155–250. [21] Tutte, W. T., Connectivity in Graphs, University Toronto Press, Toronto (1966). 76 [22] van Lint, J. H.; Wilson, R. M., The van der Waerden Conjecture: Two Proofs in One Year, Math Intell 4 (1982), 72–77. [23] van Lint, J. H., Notes on Egoritsjev’s Proof of the van der Waerden Conjecture, Linear Algebra Appl 39 (1981), 1–8. [24] van Lint, J. H.; Wilson, R. M., A Course in Combinatorics, Second Edition, Cambridge University Press (1992, 2001). [25] Wong, P. K., Cages—a survey, J. of Graph Th. 6 (1982), 1–22. [26] Zeng, J., The generating function for the difference in even and odd three-line latin rectangles, Ann. Sci. Math. Quebec 20/1 (1996), 105–108.