Two Cyclic Arrangement Problems in Finite Projective Geometry: Parallelisms and Two-Intersection Sets Citation White, Clinton Thomas (2002) Two Cyclic Arrangement Problems in Finite Projective Geometry: Parallelisms and Two-Intersection Sets. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/edj1-d674. https://resolver.caltech.edu/CaltechETD:etd-06052006-143933 Abstract Two arrangement problems in projective geometries over finite fields are studied, each by imposing the condition that solutions be generated by some cyclic automorphism group. Part I investigates cyclic parallelisms of the lines of PG(2n - 1,q). Properties of a collineation which can act transitively on the spreads of a parallelism are determined, and these are used to show nonexistence of cyclic parallelisms in the cases of PG(2n - 1,q) with gcd(2n - 1,q - 1) > 1 and PG(3, q) with q = 0 (mod 3). Along with the result first established by Pentilla and Williams that PG (3, q) admits cyclic (and regular) parallelisms if q = 2 (mod 3), this completes the existence problem in dimension 3. Cyclic regular parallelisms of PG(3, q) are considered from the point of view of linear transversal mappings, leading to a conjectured classification. Finally, some partial results and open problems relating to cyclic parallelisms in odd dimensions greater than 3 are discussed. Part II is joint work with B. Schmidt, investigating which subgroups of Singer cycles of PG(n - 1,q) have orbits which are two-intersection sets. This problem is essentially equivalent to investigating which irreducible cyclic codes have at most two non-zero weights. The main results are necessary and sufficient conditions on the parameters for a Singer subgroup orbit to be a two-intersection set. These conditions allow a computer search which revealed two previously known families and eleven sporadic examples, four of which are believed to be new. It is conjectured that there are no further examples. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) 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) Aschbacher, Michael Wales, David B. Defense Date: 5 September 2001 Record Number: CaltechETD:etd-06052006-143933 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-06052006-143933 DOI: 10.7907/edj1-d674 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 2463 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 05 Jun 2006 Last Modified: 06 Nov 2021 00:13 Thesis Files Preview PDF - Final Version See Usage Policy. 3MB Repository Staff Only: item control page

Two Cyclic Arrangement Problems In Finite Projective Geometry: Parallelisms And Two-Intersection Sets Thesis by Clinton T. White In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California. 2002 (Submitted the 5‘ of September 2001) ii (© 2002 Clinton T. White All Rights Reserved ili To my parents. iv Acknowledgements I gratefully acknowledge the assistance of my advisor, Richard M. Wilson. In addition to many helpful discussions, I am indebted to him for both his patience and his encouragement as I completed this work. Part II of this thesis is based on joint work with Bernhard Schmidt. I would like to thank him for granting his permission to include our results. Abstract Two arrangement problems in projective geometries over finite fields are studied, each by imposing the condition that solutions be generated by some cyclic automorphism group. Part I investigates cyclic parallelisms of the lines of PG(2n — 1,q). Properties of a collineation which can act transitively on the spreads of a parallelism are deter- mined, and these are used to show nonexistence of cyclic parallelisms in the cases of PG(2n — 1,q) with ged(2n — 1,qg — 1) > 1 and PG(3,q) with g = 0 (mod 3). Along with the result first established by Pentilla and Williams that PG(3, q) admits cyclic (and regular) parallelisms if g = 2 (mod 3), this completes the existence problem in dimension 3. Cyclic regular parallelisms of PG(3,q) are considered from the point of view of linear transversal mappings, leading to a conjectured classification. Fi- nally, some partial results and open problems relating to cyclic parallelisms in odd dimensions greater than 3 are discussed. Part II is joint work with B. Schmidt, investigating which subgroups of Singer cycles of PG(n — 1,q) have orbits which are two-intersection sets. This problem is essentially equivalent to investigating which irreducible cyclic codes have at most two non-zero weights. The main results are necessary and sufficient conditions on the parameters for a Singer subgroup orbit to be a two-intersection set. These conditions allow a computer search which revealed two previously known families and eleven sporadic examples, four of which are believed to be new. It is conjectured that there are no further examples. vi Contents Acknowledgements Abstract 1 Introduction and Summary 1.1 1.2 Overview... 0 1.1.1 Parallelisms .........0002020202.200..0.00000048. 1.1.2 Two-intersection sets .......0.000. 00. eee te es I Cyclic Parallelisms 2 Some Nonexistence Results 2.1 2.2 2.3 2.4 Singer cycles. 2... Characterization of the automorphism ................. Line orbits vs. point orbits... 2... 2. ee A line-orbit correspondence .......... 00000 eee ene 3 Cyclic Regular Parallelisms 3.1 3.2 3.3 3.4 3.9 3.6 Spreads and transversal mappings. ................008. Regular spreads . 2... 1. The construction 2... 0. The proof of Theorem 3.238 ........0..0.0.. 00000000084 Other examples... 2... Appendix: calculating ft 2... 0... iv on wo => 11 12 12 16 21 29 vil 4 Beyond Dimension Three 4.1 Partial solutions. ........20...00..002. 00000800. eae 4.2 Openproblems ........... 0.2.00 0 eee ee ee eee II Singer Subgroup Orbits As Two-Intersection Sets 5 Background 5.1 Definitions and equivalent problems ................+.. 5.1.1 Two-weight irreducible cyclic codes ............... 5.1.2 Sub-difference sets ..........-0. 000004 ee eee 5.2 Therole of Gausssums.........0.. 0.0000 eee eee ee 5.3 Appendix: Fourier analysis... ..........-..000+00 004 6 Necessary and Sufficient Conditions 6.1 The mainresult..........0. 00000 2 eee ee 6.2 Onthe classification .........0. 00.00.0000 eee ee 6.2.1 Subspaces and semiprimitive sets ...............-. 6.2.2 The exceptional sets .........0.2. 022.000 eee 6.3 Partial proof of the classification. ..............2.0204. A Notation Bibliography 64 65 69 72 73 73 76 77 78 82 84 84 88 88 89 91 95 96 viii List of Tables 2.1 Decomposition of PG(8,2) .. 2... 0.02.00... 0.200000. 25 2.2 Decomposition of PG(3,3) ............ 00202022 2 eee 26 2.3 Decomposition of PG(3,5) .. 2... 0.2... 20002 ee ee 27 2.4 Cyclic parallelisms of PG(3,2)......0....... 20.02.20 004 30 2.5 Cyclically resolvable S(2,4,40) .........2 00000200 eu 34 6.1 The exceptional solutions. .................02.-2000. 90 Chapter 1 Introduction and Summary 1.1 Overview The setting for these investigations will be projective geometries over finite fields. Let F = GF(q) be the finite field of order g and let V be an F-vector space of dimension n. The projective geometry of V, denoted PG(V), is the poset. whose elements are the proper nontrivial subspaces of V with U < W if and only if U is a subspace of W. PG(V) is ranked poset, where the rank of U is dim U —1. Sometimes the term dimension will be used in place of rank; every effort will be made to avoid confusion between linear and projective dimensions. Typically, subspaces of rank 0,1,2 are called points, lines, planes, respectively. Hyperplanes are subspaces of rank one less than the rank of A. Given subspaces U, W < V, UV W denotes the subspace of V generated by U and W, while U AW denotes the subspace intersection of U and W. IfV =W, ®---@ W, then homogeneous coordinates will sometimes be used to specify points of PG(V). The notation (2, : --- : 2) denotes the projective point that is the one-dimensional subspace spanned by the vector (21,... , Zz). The general linear group of V, denoted GL(V), is the group of nonsingular lin- ear transformations of V. The semilinear group of V, denoted T'L(V), is the group of invertible semilinear transformations of V. A function a : V + V is semilin- ear if a is an abelian group homomorphism and there exists f € Aut(F) such that (Ax)a = f(A)(xa) for every x € V and every \ € F. The projective general linear group and the projective semilinear group, denoted PGL(V) and PIL(V), are the quotients GL(V)/Z and TL(V)/Z, where Z = {x ++ Ax | \ € F*} & F*. In geomet- ric terminology, elements of PGL(V) and PIL(V) are called, respectively, projectiv- ities and collineations of PG(V). The following result is known as the Fundamental Theorem of Projective Geometry; see [1], [19], for example. 2 Theorem 1.1. [fdimV > 3, the automorphism group of the geometry PG(V) is the projective semilinear group PIL(V). As each of the objects discussed above is determined up to isomorphism by the dimension of the vector space and the order of the field, one may write X(n,q) for X(V), where X is one of GL, PL, PGL, PIL; write PG(n, q) for PG(V(n + 1,q)). Often, PG (n,q) (or, when there is no ambiguity as to the order of the field, ») will be used to denote the set of rank k subspaces of PG(n,q). The number of k-spaces of PG(n, q) is given by (q” —1)(qr* — 1)--- (get - 1) Two important combinatorial designs obtained from PG(n — 1,q) are the point- line design and the point-hyperplane design. A 2-(v, k, \) design is a triple (P, B,Z), where P is a set of v points, B is a set of blocks, and Z is an incident relation on P UB so that each block is incident with k points and any two points are coincident with exactly A blocks. A design is called symmetric if |P| = |B]. The points and lines of PG(n — 1,q) form a design with parameters nm 2 2— (! bgat i), q-1l1 q-1 The points and hyperplanes form a symmetric design with parameters q-l’ q-1? q-1 J’ see [1, 19, 43]. The proof of the following fundamental result on symmetric designs can be found in [43, Theorem 27.1]. Theorem 1.2. Let S be a symmetric design and let a be an automorphism of S. ‘Then the type of the cycle decomposition of a on the points of S is the same as the type of the cycle decomposition on the blocks of S. An important class of automorphisms of PG(n, gq) are the Singer cycles. A gener- 3 ator of a cyclic group of automorphisms acting regularly on the points of PG(n, q) is called a Singer cycle. By Theorem 1.2, Singer cycles generate groups which also act regularly on the set of hyperplanes. Singer cycles are often useful for combinatorial problems in projective spaces, as will be the case with the problems considered here. Each of the next two subsections introduces an arrangement problem in finite projective spaces. One may seek solutions to each of these problems by imposing some cyclic automorphism structure on the problem. Section 1.2 summarizes the results of investigations of these problems. A list of some essential notation is included as an appendix at the end of the thesis. 1.1.1 Parallelisms One of the oldest problems in combinatorial design theory is the famous Kirkman schoolgirl problem: arrange a class of 15 schoolgirls in five rows of three for each of seven days so that any two girls appear in the same row on exactly one day. A solution was known to Kirkman in the mid-nineteenth century. Yet, this problem has given rise to a number of very interesting generalizations. It will appear as a special case of the problem investigated in Part I. Another scheduling problem to have in mind is that of 1-factorizations of the complete graph Ky,. Given a finite set X, the complete graph on X, denoted K(X), consists of a set of vertices and edges; the vertices of K(X) are the elements of X and the edges are the unordered pairs of elements of X. Incidence is given by inclusion. Write K,, for K(X) if |X| =n. Now suppose |X| = 2n. A 1-factor of Ko, is a set of n pairwise nonintersecting edges of Ko,; that is, a partition of X by 2-subsets. A 1-factorization of Kop, is a partition of the set of edges into 1-factors. Ko, consists of (“") edges; thus, a 1-factorization would contain (2n — 1) 1-factors. It is easy to see that K2, admits 1-factorizations. For a nonzero integer m, Zm denotes the cyclic group of integers modulo m. Take X = Zon; U {oo}. As the edges of a 1-factor F’, take the edge {0,00} and all edges of the form {z,—x} for & € Zon—1 \ {0}. To obtain the remaining 1-factors of a 1-factorization, take the 4 translates of F’ by the elements of Z2,_1, with the convention that oo is a fixed point of this action. Below is the example for K4. {0, co} {1, co} {2, co} {1, 2} {0, 2} {0, 1} This construction is actually cyclic. The 1-factors of this 1-factorization are permuted in a single cycle by the cyclic automorphism group generated by 71> 2+ 1. It is sometimes interesting to view PG(n — 1,q) as the so-called g-analog of the Boolean lattice on the n-set {1,... ,}. One is then interested in which combinatorial results for the Boolean lattice have analogs in the projective geometries. From this point of view, edges of K2, would correspond to lines of PG(2n — 1,q). The 1- factorization problem has the following analog. Two lines of PG(n,q) are said to be skew if there is no point coincident with both lines. A spread of PG(n, q) is a collection S of pairwise skew lines such that each point of PG(n, q) is incident with a line of . (In general, one may consider spreads of k-spaces of PG(n, q), with the obvious definition. However, the only kinds of spreads which will be considered here are spreads consisting of lines, and thus the convention will be that spread always refers to spreads of lines. No qualification will be given.) As PG(n, q) has (q”t! —1)/(q—1) points and each line is incident with (q?—1)/(q—1) points, it is necessary for the existence of spreads that (q? — 1)|(q"t+ — 1). This in turn requires that n be odd. It turns out that the condition n odd is sufficient to ensure that spreads exist in PG(n, q); see [19] for details. A parallelism (also called a packing) of PG(2n — 1,q) is a partition of the set of lines into spreads. As PG(2n — 1, g) contains (q?" — 1)(q?r! — 1) (? —V(q-1) lines and spreads consist of (q’" — 1)/(q? — 1) lines each, then a parallelism consists of (q?"-! — 1)/(q— 1) spreads. Note that this number is precisely the number of points on a hyperplane of PG(2n — 1, q). 5 The existence of parallelisms of PG(2n — 1,q) is a much more difficult problem than was the existence of 1-factorizations of the complete graph. It was not until the early 1970’s that PG(3, g) was shown to admit parallelisms. This result was obtained by Denniston [13] and independently by Beutelspacher [9]. In the same paper, Beu- telspacher also proved the existence of parallelisms of PG(2' — 1,q). However, these results do not answer questions about the existence of parallelisms with certain extra structure. A parallelism is cyclic if there is a collineation acting transitively on its spreads. Considering that the complete graphs Ke, admit cyclic 1-factorizations, it would be of interest to determine if the projective spaces PG(2n — 1, q) similarly admit cyclic parallelisms. Secondly, a parallelism of PG(3,q) is regular if it consists entirely of regular spreads. Regular spreads are discussed in some detail in Section 3.2; this use of regular should not be confused with meaning of the term in the context of group actions. Interest in regular spreads stems in part from a construction originally due to M. Walker of a translation plane of order g* with kernel GF(q) from a regular parallelism of PG(3, ¢). See [28], [23], and [36] for more on this correspondence. In [2], Baker constructed a cyclic parallelism of PG(2n — 1,2) for every n > 2. Denniston [14] claimed that there are no cyclic parallelisms of PG(3, 3) or PG(3, 4). In [15], he finds six inequivalent cyclic parallelisms of PG(3, 8), two of which are regular. In [37], Prince shows that there are no parallelisms of PG(3,3) such that any two of the constituent spreads are projectively equivalent. In particular, there are no regular parallelisms of PG(3, 3), as any two regular spreads are equivalent. Recently, Prince used a computer search to compile a list of equivalence classes of cyclic parallelisms of PG(3,5) [38]. There are forty-five of these, two of which are regular. Finally, another recent result was obtained by Pentilla and Williams [36], who construct two inequivalent cyclic regular parallelisms of PG(3, q) if g = 2 (mod 38). Currently, almost nothing is known about parallelisms of projective spaces of dimension greater than 3, beyond Baker’s and Beutelspacher’s results. In particular, there are no known parallelisms of PG(5, q) with q > 2, 1.1.2 Two-intersection sets An easy counting argument shows that there can be no set of points of PG(n — 1, q) which is met by each hyperplane in the same number of points, except for the set of all points of PG(n — 1,q). A set of points of PG(n — 1, q) is called a two-intersection set if each hyperplane meets the set in one of two numbers of points. This is as close as nontrivial point-sets can come to being evenly distributed over the hyperplane sections. Two-intersection sets in the plane have drawn the most interest. There are a number of configurations of points in planes which give two-intersection sections; the following are just a few of the more commonly known. A hyperoval of PG(2, q), q even, is a set of g +2 points met by each line in 0 or 2 points. A Baer subplane of PG(2, q*) is a set. of g?-+q+1 points met by each line in 1 or (¢+1) points. These points, together with the lines meeting the set in g+1 points, form an embedded PG(2,q). A unital is a set of g? +1 points of PG(2, q?) which, like a Baer subplane, is met by each line in 1 or (¢+1) points. Each of these arrangements of points, hyperovals, Baer subplanes, and unitals, have received a great amount of attention from finite geometers. Consider the example of a hyperoval for a moment. Let & = PG(2,q) where q = 2° and suppose © is a hyperoval of ©. Given any point p ¢ O, the nonempty intersections of the lines on p with the point-set O give a partition of O into pairs of points. In this way, each point not in O determines a 1-factor of the complete graph K(Q). Now suppose / is any line of © which does not meet ©. As each pair of points of O determines a unique line of 4, which in turn meets / in a unique point, it follows that every edge of K(Q) occurs in a 1-factor determined by a point of J. In this way, each line not meeting O determines a 1-factorization of K(O). Thus, the plane ¥ can be viewed as an extension of the complete graph K(O), for which the additional points and lines correspond to special collections of 1-factors and 1-factorizations of K(O), respectively. An idea due to Bruck for a possible construction of a projective plane of order a(q + 1) is similar to the above, only replacing the complete graph on g + 2 vertices 7 with the design of points and lines of PG(3,q). To extend this design to a projective plane of order g(g+1) requires a very special collection of g? parallelisms of PG(3, q), which will serve as the lines of the new plane which do not meet the points of PG(3, q). The Bruck-Reyer-Chowla Theorem rules out the possibility of this construction for certain, but not all, values of g. Were it possible, the construction would yield a plane in which PG(3,q) is embedded as a set of type (0,q? +q+ 1); the lines external to the embedded PG(3, q) would correspond to parallelisms. This idea contains at once both arrangement problems under consideration, parallelisms and two-intersection sets, and for this reason it seems appropriate to mention it here. Returning to the background discussion of two-intersection sets, one curious fact stands out. Until recently, all known two-intersection sets in planes of odd order, except the trivial examples of a point and a line, occurred in planes whose orders were also squares. Furthermore, the difference of the intersections numbers was the square root of the order of the plane. While it can be shown that the difference of the intersection numbers must divide the order of the plane, it was not clear if it must be the case that the difference was always the square root of the order. Note that in planes of even order, hyperovals provide examples not exhibiting this behavior. It has long been known that two-intersection sets in PG(n—1, q) are equivalent to a certain class of codes called projective two-weight codes. A linear code C C GF(q)” is a projective code if its dual C+, with respect to the usual dot product, has minimum distance at least 3. See the survey of Calderbank and Kantor [12] for a thorough treatment of the correspondence between two-intersection sets, two-weight projective codes, and certain strongly regular graphs. A coding-theoretic problem that has received a great deal of attention is the problem of determining the weight enumerators of irreducible cyclic codes; see [5, 7, 24, 31], for example. This problem is equivalent to trying to determine the intersection numbers of hyperplanes of PG(n—1, q) with orbits under a subgroup of a Singer cycle and in general these are very difficult problems. There has been some recent progress, however, in areas relating to two-weight codes and two-intersection sets. Langevin [24] finds several cases of two-weight irreducible cyclic codes (thus giving certain 8 two-intersection sets as orbits under subgroups of Singer cycles). His proof relies on evaluating certain Gauss sums in this special case. Also, a recent paper of Dover and Batten [4] exhibits, in geometric language, two intersection sets in PG(35°) and PG(3, 7*) as orbits under subgroups of Singer cycles of index 19 and 37, respectively. These examples are exciting because they occur in planes of odd, nonsquare order. 1.2 Summary of results In these investigations, the aforementioned arrangement problems, parallelisms and two-intersection sets, are studied by insisting that the solutions arise as orbits of some cyclic group of collineations. Thus, Singer cycles appear in the problems, affording the opportunity to state the problems in terms of some quotient of the multiplicative group of a finite field by a subgroup. Subspaces of projective spaces are linear objects and thus will correspond to certain additive subgroups of finite fields. Each of these problems can thus be restated directly in terms of the interaction between the two group structures, addition and multiplication, of a finite field. Part I is an investigation of cyclic parallelisms of PG(2n — 1,q). The point of view of Chapter 2 is to study cyclic parallelisms by studying the point and line orbit structure under a collineation which acts transitively on the spreads of a parallelism. It is first shown (Theorem 2.10) that any such collineation must in fact be a pro- jectivity which fixes a point and acts on a hyperplane. Furthermore, all line-orbits under this projectivity have the same length, (q?"~! — 1)/(q — 1), and any spread of the parallelism is a set of orbit representatives. If gcd(2n —1,q—1) > 1, no element of PGL(2n, q) has these properties (Lemma 2.9) and thus there are no cyclic parallelisms in this case. This result extends a result of Denniston [14] that PG(3, 4) admits no cyclic parallelism. Continuing with the study of the orbit structure of a projectivity with the neces- sary properties to cyclically permute the spreads of a parallelism leads to a restate- ment of the cyclic parallelism problem. The problem is cast in terms of a decompo- sition of the nonzero elements of a finite field in terms of cosets of an additive and a 9 multiplicative subgroup. In this case it is not difficult to see from this decomposition that there are no cyclic parallelisms of PG(3,q) if g = 0 (mod 3) (Corollary 2.26 to Theorem 2.25). This extends an earlier result of Denniston [14] which treated only the case g = 3. The results of this chapter also complete the existence problem for cyclic parallelisms of PG(3, q): they exist if and only if g = 2 (mod 3). Chapter 3 is devoted to the construction and classification of cyclic regular paral- lelisms of PG(3, q) if g = 2 (mod 3). The construction is in terms of linear transversal mappings, which are introduced in Section 3.1. A construction of cyclic regular par- allelisms was given initially by Pentilla and Williams in [36]. The results of this chapter were discovered independently from their work. The chapter concludes with the conjecture that up to projective equivalence, there are precisely two cyclic regular parallelisms of PG(3, q) if g = 2 (mod 3). An exhaustive search of linear transversal mappings verifies the conjecture for all such q < 32. Part I concludes with a discussion of the cyclic parallelism problem in odd dimen- sions greater than 3. Two partial solutions are presented, which, however, cannot be merged into a full solution. Some open problems relating to cyclic parallelisms in higher dimensions are discussed, with emphasis on the case of PG(5, q). Part II is the result of joint work with B. Schmidt and will appear in slightly different form in [40]. Here, the problem is to understand which subgroups of Singer cycles of PG(n — 1,q) have orbits which are two-intersection sets. The paper [40] is written from the point of view of irreducible cyclic codes; it is an essentially equivalent problem to determine when these codes have at most two weights. Investigations of the weight distribution of irreducible cyclic codes is not a new problem; it has been understood for some time how these weight enumerators are related to certain Gauss sums. The new result offered here is that in order to determine when at most two weights (or hyperplane intersection numbers, in the geometric language) arise, one need not evaluate the relevant Gauss sums. Enough information can be obtained from Stickelberger’s result on their prime ideal factorization, together with Parseval’s identity. The main result (Theorem 6.1) is a set of three conditions on the parameters 10 of a Singer subgroup orbit which are necessary and sufficient for that orbit to be a two intersection set. There are two known families of two-intersection sets arising in this way and a computer search reveals 11 sporadic examples. It is believed that four of these were previously unknown. It is conjectured that there are no further examples and this conjecture is proved in a special case (Theorem 6.12), subject to the generalized Riemann hypothesis. 11 Part I Cyclic Parallelisms 12 Chapter 2 Some Nonexistence Results A parallelism of PG(2n — 1,q) is called cyclic if its stabilizer in PT'L(2n, q) contains an element a acting transitively on its spreads. The main results of this chapter are the nonexistences of cyclic parallelisms in the following cases: e PG(2n — 1,q), ifn > 2 and gced(2n —1,q—1) > 1; e PG(3,q), if g=0 (mod 3). These results are obtained by analyzing the necessary orbit structure of a collineation a which acts transitively on the spreads of a parallelism. The chapter begins with some basic and most likely well-known facts about Singer cycles, which are then used in the later sections to more carefully describe the orbit structure of a. 2.1 Singer cycles This section is primarily concerned with collineations of PG(n — 1,q) having large order and, more specifically, with a particular kind of collineation called a Singer cycle. The main result characterizes Singer cycles as projectivities. This result is put to use in the next section to characterize collineations which cyclically permute the spreads of a parallelism. Lemma 2.1. Let F be a finite field and let K be a subfield of F. If A € GL(n,F) and its minimal polynomial has degree d and coefficients in K, then the order of A in PGL(n, F) is at most (|K|? — 1)/(|K| — 1). Proof. Every power of A is a K-linear combination of J, A,... , AX. There are at most (|K|¢ — 1)/(|K] — 1) d-tuples from K, no two of which are K* multiples of each 13 Definition 2.2. For n > 3, a Singer cycle of PG(n — 1, q) is a generator of a cyclic group of collineations which acts regularly on the set of points. Remark 2.3. As gq’ —1 PGO(n—1,q)| = | (n—1,9)| qo’ a Singer cycle has order (q” — 1)/(q — 1) in the group PI'L(n,q). As the points and hyperplanes of PG(n — 1, q) form a symmetric design, then Theorem 1.2 implies that a collineation a is a Singer cycle if and only if (a) acts regularly on the set of hyperplanes of PG(n — 1, q). Example 2.4. Let L = GF(q”) and let F be the subfield of L of order g. View L as an F-vector space. For a primitive element w of L, let o € PGL(L) be determined by the linear map «++ wa on L. For « € L*, wz € Fx if and only if w' €¢ F. Any such ¢ must be a multiple of (g” — 1)/(q¢— 1) as wW@"-Y/G-Y generates F*. Thus, o permutes the points of PG(L) in a cycle of length (¢” — 1)/(q — 1). It is next shown that, like the above example, all Singer cycles are projectivities. Thus, Singer cycles are represented by linear transformations of the underlying vector space. Theorem 2.5. For n > 3 and q a prime power, Singer cycles of PG(n — 1,q) are projectivities. Proof. Let q¢ = p™ with m > 1 and let F = GF(q). PI'L(n,q) is isomorphic to a semidirect product of PGL(n, q) by Zn; PGL(n, q) is a normal subgroup of PrL(n, q) and a complement is {¢° | 0 < i < m}, where (xo,... ,2n—1)@ = (a3,... ,2®_,). Given a € PI'L(n, q) there exist A € GL(n,q) and 0 < k < m such that a is represented in TL(n, q) by A. Assume a ¢ PGL(n, q); that is, assume k > 0. Note that Ad* = RAP"), where A®) = (aP.). In general for t > 1, at = gh APP)... 4) 4. 14 Let d= gced(k,m) and choose t = m/d. Let 8 = a’. As ¢* = 1, then G € PGL(n,q) and is represented in GL(n,q) by the matrix B = A®“-””)... A") 4. Using the fact that the map “) is an endomorphism of the ring of square matrices over a field of characteristic p, it follows that Be) = Ae) Ae)... AP) = ABAM!, (2.1) Suppose f(x) = S5,a:z° € F[z]. Now f(B) = 0 if and only if f(B)®) = 0. Furthermore, F(BY) = YaB\ = Saf (BOY)’ Letting 4y7(x) denote the minimal polynomial of a square matrix M, it follows that p(x) = 0, a:" if and only if page (z) = DY, a?’ a. That is, a coefficient of Lacpry (2) is obtained by raising the coefficient of jzp(x) of the same degree to the power p*. On the other hand, B®") and B have the same minimal polynomials since they are conjugate by equation (2.1). Hence, the coefficients of yg(z) are fixed by the field automorphism x > z?". Let E denote the subfield of F fixed by this automorphism. Note that |E| =p’, where d = (k,m). By Lemma 2.1, the order of @ in PGL(n, F) is at most (p”4 — 1)/(p* — 1). Therefore, the order of a in PI'L(n,q) is at most m(p4 — 1) d(p? —1) ’ which can be shown to be less than (p”” — 1)/(p™ — 1). Therefore, no element of PIL (n, g) \ PGL(n, q) is a Singer cycle of PG(n — 1, q). Oo Lemma 2.6. (i) If Aj, A, € GL(n,q) have the same order in GL(n,q) and each represent Singer cycles of PG(n — 1,q), then A, and A» generate conjugate subgroups of GL(n, q). (ii) If there exists A € GL(n, q) of order (g”—1)/(q—1) in GL(n, q) which represents a Singer cycle of PG(n —1,q), then (n,qg—1) = 1. Proof. By Lemma 2.1, matrices representing Singer cycles of PG(n — 1, q) have min- 15 imal polynomials of degree n and hence have irreducible characteristic polynomials. As A; is conjugate to the companion matrix of its minimal polynomial, it may be as- sumed without loss of generality that A; is a companion matrix. Let L = GF(q”) and let F be the subfield of L of order g. For i = 1,2, let A; € L be an eigenvalue of A;. Regarding L as an F-vector space of dimension n, define p; € GL(L) by xy, = Az. Let B; denote the ordered basis (A? | 0 < j < n) of L. Using the notation Mx(a) to denote the matrix of a linear transformation a with respect to the ordered basis X, one has Mg, (ju) = Aj. As A; is conjugate to the diagonal matrix A; = diag|),, 7,... Ay, it follows that the order of A; in GL(n,gq) is equal to the order of \; in the group L*. If A, and A» have the same order, then A; and A, have the same order in L*. Since L* is a cyclic group, it has at most one subgroup of any given order. Thus (A1) = (A2) in L* and Ag is a power of Aj, so (41) = (U2). Let C be the matrix representing the change of basis from 5B, to By. Then, (Ai) = Mp, ((H4)) = Mp, ((H2)) = C™' Mp, ((tt2))C = C7" Ad) C. In part (#2), as in part (2), the characteristic polynomial of A is irreducible and A is conjugate to the diagonal matrix A = diag[A, A?,... ,A"~1], where A is an eigenvalue of A in L. Write ord(A) to denote the order of \ € F*. As A is conjugate to A, the order of A in GL(n, qg) is equal to ord(A). Also, the order of A in PGL(n, q) is equal to Under the assumption that each order is equal to (g” — 1)/(q — 1), one has m4 lom(! q=1) =a" =1 q-1 n—-2 Pt =D ant-) ln i- De q—1 0 i=0 Note that 16 Hence, ae | Thus, if A has order (¢” — 1)/(q— 1) in GL(n, q) and represents a Singer cycle of PG(n — 1,q), then gq” —1 gq’ —1 "1 =lom( +——,¢-1) = —4—__. 2.2 q om (2 4 ) gcd(n, q — 1) (2.2) Equation (2.2) implies that gcd(n,q — 1) = 1, which gives statement (ii) of the Lemma. C] 2.2 Characterization of the automorphism The topic of this section is the characterization of collineations which act transitively on the spreads of a parallelism of PG(2n — 1,q). It is of course assumed throughout that n is at least 2, and this assumption will not always be repeated in each result. Recall the adopted convention that the term parallelism will always refer to a par- allelism of lines. Also recall the notation 5“ used to denote the set of k-dimensional subspaces of the n-dimensional projective space. Finally, let grtt —] the number of points of the geometry PG(n,q). Simply write 9(n) where there is no ambiguity as to the order of the field. Definition 2.7. A parallelism P of PG(2n — 1,q) is said to be cyclic if there is a collineation acting transitively on the spreads of P. Lemma 2.8. If a collineation a € PIL(2n,q) permutes the spreads of a parallelism of PG(2n —1,q) in a single cycle, then a stabilizes a unique hyperplane and a unique point of PG(2n—1,¢). This point and this hyperplane are not incident. Furthermore, each orbit of lines under a and each orbit of points, aside from the fixed point, has length 0(2n — 2). In particular, a has order 6(2n — 2). 17 Proof. Let P be a parallelism whose spreads are cyclically permuted by a; let S € P. As P = {Sa‘ | 0 <i < 0(2n — 2)} is a partition of DS?_, and Sa%@"-?) = S, then $ contains a set of orbit representatives of the lines of X2,-1 under the action of (a). Let le S. As la’ € S if and only if 6(2n — 2) divides t, it follows that the length of the orbit of [ is divisible by 0(2n — 2). The line J was chosen arbitrarily from S and S contains a set of orbit representatives; therefore, the length of each orbit of lines under a is a multiple of 6(2n — 2). Now suppose a point x is not a fixed point of a. Let J be the line determined by x and xa. Let t¢) denote the length of the orbit of x under a; similarly, let t; denote the length of the orbit of | under a. By definition, the stabilizer of / in the group (a) is generated by a”. On the other hand, xa‘ = x and (xa)a” = xa; hence, la* = I. Thus, a” € (a!) so t, divides to. Combining this result with the above fact that 0(2n — 2) divides t, it follows that the length of an orbit of points under a is either 1 or else is divisible by 6(2n — 2). As nO | = 6(2n — 1) = 1+ q0(2n — 2), then a must have a fixed point. Then the automorphism a stabilizes some hyperplane by Theorem 1.2. Necessarily this hyperplane is not incident with the fixed point, for else a acts on the pencil of lines incident with both the fixed point and the invariant hyperplane. There are only 6(2n — 3) such lines, contradicting the result that all orbits have length at least 6(2n — 2). Now let p and IT denote a fixed point and an invariant hyperplane of PG(2n—1, q) under the action of a. Since two points determine a line, if there were a second point p’ # p fixed by a then the line p V p’ is fixed by a, a contradiction. So p is unique. Therefore, II is unique by Theorem 1.2. The 0(2n — 2) lines incident with p are permuted by a; therefore, they form a single orbit. As each line incident with p meets II in a unique point, and each point of II is incident with some line on p, it follows that a has a single orbit of length 0(2n — 2) on the points of II. That is, @ acts as a Singer cycle on II. Therefore, af@n-2) fixes every point of II and hence every line of II. Combining this with the earlier result that all orbits of lines have length at least 6(2n — 2), it follows that each 18 orbit of lines in II has length exactly 6(2n — 2). Now suppose / is any line of PG(2n — 1, q) which is neither a line of IT nor incident with p. Let x denote the point of II which is incident with 1. Notice that Iq9@"-2) meets IT in the point x, as xa°@"-?) = x. Furthermore, la®@"-) and I are either the same line or else are skew lines, as they belong to the same spread of the parallelism P. Since they have a common point, then it must be that la%@"-) = 1. Hence, every orbit of lines under a has length 6(2n — 2). It remains to show that orbits of points, other than the fixed point, have length 6(2n — 2). It has already been shown that a has a single orbit of length 6(2n — 2) on the points of II. Let x 4 p be any point not incident with I]. As x ¥ p, it was shown earlier in the proof that the length of the orbit of x under a is a multiple of 6(2n — 2). Pick any two distinct lines / and m which are incident with x. As x = 1A it follows that xo 2r-2) — (1o9?"-2)) A (ma??r-?)) =IlAm=x. Thus, the orbit of x has length equal to @(2n — 2). Finally, as a%@"~*) fixes each point, a must have order 6(2n — 2). Oo Lemma 2.9. Suppose a is a collineation of PG(2n — 1,q) each of whose orbits of lines has length 0(2n — 2). It then follows that gcd(2n —1,q-—1) = 1 anda is a projectivity. Furthermore, if B is another projectivity each of whose orbits of lines has length 6(2n — 2), then (a) and (8) are conjugate in PGL(2n, q). Proof. Let V = V(2n,q) and suppose that the action of a € PIL(2n,q) partitions the set of lines of PG(2n, q) into orbits of length 0(2n — 2). Arguing as in the proof of Lemma 2.8, it can be shown that a stabilizes a point and a hyperplane of PG(2n—1, q) and that these subspaces are not incident. Thus, there exist subspaces U,W < V with UN W = {0}, dimg U = 1, dimp W = 2n—-1, Ua =U, and Wa = W. That is, a stabilizes the direct sum decomposition V = U@W. Again arguing as in the proof of Lemma 2.8, it can be shown that the orbit of a on any point of PG(V) other than U has length @(2n — 2). In particular, aly is a Singer cycle on the projective plane PG(W). Thus alw € PGL(W) by Theorem 2.5. It follows that a € PGL(V). 19 Now choose a representative @ € GL(V) of a such that Gy is the identity map on U. Pick an ordered basis B of V consisting of a union of bases of U and W. Recall that Mg(&) denotes the matrix of a with respect to B. Then A where A € GL(2n—1,q). For any vector of the form x = (1,21,... ,Z2n-1) € V(2n, q) with some 2; # 0, note that xM,(@)* € xF if and only if (a1,... ,22_1)A*® = (11,--- ;Zan—1). It was argued in the previous paragraph that the orbits under Mg(d) of projective points of the form (1: @ :--+: Za,-1), with some x; 4 0, have length 6(2n — 2). Thus, for nonzero vectors x! = (2,...,Zen—1), x/A* = x’ if and only k is a multiple of 6(2n — 2). Therefore, the matrix A has order 6(2n — 2). Then (2n —1,q—1) =1 by part (ii) of Lemma 2.6. Finally, suppose @ is another projectivity of PG(V) each of whose line-orbits has length 6(2n — 2). As with a, there exists subspaces U', W' of V of dimensions 1 and 2n — 1, respectively, such that @ stabilizes the decomposition V = U’ @ W’ and Bly: is a Singer cycle of PG(W’). As above, choose a representative 3 € GL(V) of @ such that 6 lv is the identity and choose a basis B’ of V consisting of a union of bases of U’ and W’. Then Mp() = B where B € GL(2n — 1,q) has order 0(2n — 2). Now A and B each represent Singer cycles of PG(n — 1, q) and each have order 6(n — 1). By part (i) of Lemma 2.6, there exists C’ € GL(2n—1, q) such that C~'(B)C = (A). Extending C linearly to V(2n, q) by setting (1,0,... ,0)C = (1,0,... ,0) results in C-!(My(B))C = (Mg(@)). Note that Mg(G) and Mg(f) are conjugate via the matrix representing the change of basis from B to B’. It then follows that Mg(@) and Mg(@) generate conjugate subgroups of 20 GL(V); hence, & and @ generate conjugate subgroups of GL(V) and a and £ generate conjugate subgroups of PGL(V). O Theorem 2.10. There exists a cyclic parallelism P of PG(2n — 1,q) only if there exists a projectivity a € PGL(2n, q) each of whose line-orbits has length 0(2n — 2). If P is a cyclic parallelism and @ is such a projectivity, then P is projectively equivalent to a parallelism whose spreads are cyclically permuted by a. Proof. Suppose @ € PI'L(2n,q) cyclically permutes the spreads of some parallelism P = {SG' |0 <i < 0(2n—2)}. By Lemma 2.9, each orbit of the lines of PG(2n — 1, q) under @ has length 0(2n — 2), giving the first statement of the Theorem. Suppose a: is any collineation of PG(2n — 1,q) each of whose orbits of lines has length 0(2n — 2). By Lemma 2.9, a and @ are projectivities and generate conjugate subgroups of PGL(2n — 1,¢q). Hence, a is conjugate to a generator of (3), which in turn also cyclically permutes the spreads of P. Without loss of generality, there exists y € PGL(2n — 1,q) such that a = y1!6y. Let P’ = Py, by definition projectively equivalent to P. Note that P’ = {S6"y | 0 <i < 0(2n—2)} and SB'y = Syy71 By = (Sy)(y 1 By)' = (Sy)at. So P! = {S'at | 0 < i < A(2n — 2)}, where S’ = Sy. Hence, P is projectively equivalent to a parallelism, P’, whose spreads are cyclically permuted by a. | Theorem 2.10 generalizes an observation of Denniston that there are no cyclic parallelisms of PG(3,4). He writes, “There is no cyclic packing of PG(3, 4) because any collineation of period 21 has some line-orbits of length less than 21; and I should expect the same difficulty to arise whenever g? + q¢ +1 is not a prime,” [13]. His observation concerning the orbits of lines under collineations of PG(3, 4) is accurate; however, its accuracy rests not on the fact that 21 is not prime but instead on the more specific fact that 21 is divisible by 3. Corollary 2.11. If gcd(2n — 1,q¢—1) > 1 then PG(2n — 1, q) admits no cyclic par- allelism. 21 2.3 Line orbits vs. point orbits The rest of this chapter specializes to the problem in three dimensions. The results of the previous section have established that the primary components of a cyclic parallelism of PG(38, q) are a projectivity 0, which partitions the lines into q?+1 orbits of size q? + q+ 1, and a spread consisting of one line representing each of the orbits of o. Furthermore, given any such projectivity 0, every projective equivalence class of cyclic parallelisms has at least one representative each of whose spreads represent the orbits of a. This section begins with a presentation of such a projectivity if ¢g 41 (mod 3). The question arises as to whether the existence of this automorphism, which is necessary for the existence of a cyclic parallelism, is also sufficient. It is to be emphasized that this question is equivalent to asking whether there exists a set of pairwise skew representatives of the line-orbits of this particular projectivity o. The approach to this question will be through a more careful study of the interaction between lines and the point-orbits of o. With the case g = 1 (mod 3) out of the way, assume for the rest of this chapter that q is a prime power which is not congruent to 1 modulo 3. It was seen in the last section that an automorphism of © whose line-orbits all have length g? + q+ 1 must have a unique fixed point and a unique invariant plane. The choice of the following coordinates is motivated by the earlier analysis of such automorphisms; these coordinates provide the framework for much of the subsequent discussion of cyclic parallelisms. Let F = GF(q) and let L be the extension of F of degree 3. The ambient four- dimensional F-vector space for the three-dimensional projective geometry will be V=FOL. Let w € L be a primitive (q7 + q+ 1)st root of unity and define o : V - V to be the linear transformation o : (t,z) 4 (¢,wx) fort € F and x € L. Let II. denote the subspace {0} @ L. Note that o fixes the projective point (1 : 0) and acts on the plane I. As a matter of convenience, write N and Tr, without the usual subscripts, to denote the norm and trace functions, respectively, of the extension L/F. Let G = ker N. Note 22 that G is generated by w. It is straightforward to check that L* is the internal direct sum of F* and G since q # 1 (mod 3). Now pick an element € € L such that Tr(€) = 1 and set H = {x € L | Tr(€x) = 0}. That is, H = €+ with respect to the symmetric bilinear form (z,y) +» Tr(zy). It is also straightforward to check that the additive group of the field L is the internal direct sum of F and H. Note that if (q,3) = 1, then one may choose € = §, in which case H = ker Tr. It will be good to give names to the following few lines and point-sets of PG(V). For x € H, L, =(0:1)V (1:2); Loo = {0} @ ker Tr; for \€ F*, O, = {(1: y) | y € AG}; Ox = {(0: 9) | 9 © Gh. Note that y € AG if and only if N(y) = A°. Since (q — 1,3) = 1 then the map A ++ »? is a permutation of F* and the sets O) partition the points of the form (1 : y), y € F’, according to the value of N(y). Proposition 2.12. The q? + 1 lines {L, | « € H}U{L.} comprise a complete system of representatives for the orbits of o on the lines of PG(V); each orbit has length q +q+1. The singleton {(1 : 0)} together with the sets of points Oy, for A € F*U {oo}, are the orbits of o on the points of PG(V). Proof. Since of +4+! = 1, then all orbits have length at most g?+q+ 1. Recall that L* = FG. It follows that the set O,, consists of all the points of II,,; ¢ is transitive on O,, because w is a generator of G. Therefore, o is a Singer cycle on II, and is transitive on its g?+q+1 lines. The line L,, may be taken as a representative of this orbit. Note that F © H is a projective plane of PG(V) which is not incident with the point (0: 1). Thus, each of the q? lines on (0 : 1) which are not contained in II,, meets exactly one point of the form (1: y) for y €¢ H. Thus, the lines {L, | x € H} are distinct. They belong to different o-orbits, and these orbits have length q?+q+1, 23 by the previous remark that o is a Singer cycle on II... Finally, the sets O,. are clearly o-invariant. Again, as w generates G, o is transi- tive on each such set. oO Remark 2.13. The orbit O,. is the point-set of a plane, so lines meet it in 1 or g+1 points. In how many points do various lines meet the other nontrivial point-orbits? The answer is simple if g = 2. In this case, there are precisely three point orbits: the fixed point (1 : 0); Ooo, consisting of the points of the plane II,,; and Oi, consisting of the remaining points. The lines meet Q, in 0, 1, or 2 points: the lines of II,, meet O, in zero points; the lines incident with the fixed point meet OQ, in exactly one point; and the remaining lines meet ©, in exactly two points. Suppose now that gq > 2. A set of points of PG(3,q) with no three collinear is called a cap. It is well-known that the maximum size of a cap in PG(3, q), with g > 2, is g’ + 1; such sets are called ovoids. Since the orbits O, contain q? + q+ 1 points, then they cannot be caps and some line must meet each set in at least three points. What is the maximum number of points of an orbit QO, which are collinear? This question will be answered shortly. The data concerning the intersections of lines with point-orbits can be recorded in an array which gives a decomposition of the elements of the field L with respect to a subgroup of its additive group and a subgroup of its multiplicative group. Define A:H x F* + 2© by A(z, A) = (2 + F) NAG. The set-valued array A is somewhat like a double coset decomposition of L*. However, instead of describing the intersection of the cosets of two subgroups of L*, A describes the intersection of the additive cosets of F < L and the multiplicative cosets of G < L*. Note that L/F = H and L*/G & F*. The relevance of A is explained by the following simple observation. Claim 2.14. Letx € H, \€ F*, andk € Z. The line L,o* meets the orbit Oy in the points {(1:y) | ye w*A(z, A)}. 24 Proof. As QO) is a o-orbit, then L,o* NO, = (LzNO,)o* and it suffices to show that the claim holds for k = 0. The set. of points incident with L, is The result is now immediate from the definition of Oy. C] To complete the correspondence between A and the interaction of the line-orbits and point-orbits of o, the array should be extended by adding another row and column, each indexed by the symbol oo, say, so that A(oo,A) =@ for \ € F’*, A(a,coo) = {1} for z € H, A(oo, 00) = GN ker Tr. Now, L,o* meets QO, in the single point (0: w*), for € H. L.,o* meets O,. in the set GN ((ker Tr)w*). Let 7: L* — G be the homomorphism x rH a Note that keram = F* and zx = & for every r € G. Let p: G + Zgayq4i be the isomorphism determined by w ++ 1. Finally, define A(a,) := A(z, A)m and A(x, ) = A(z, A)mp. | Remark 2.15. By Claim 2.14, Lzo* NO) = {(1: y) | y € w*A(a, A)}. Note that (w*A(a, A))@ = w* (A(z, A)r) = w*A(a, A). Therefore, L,o* meets the orbit ©) in the points {(1 : y) | y € Aw*A(a,d)}. The upshot is that the G-translates of a row A(a, -) completely describe the intersections of the (o)-translates of the line Lz with the point-orbits. The arrays A and A completely 25 describe the incidence of points and lines of PG(V) and the orbit structure of the collineation o on these sets. It should be said that moving the cyclic parallelism problem in a sense out of the geometric language and into this table A doesn’t necessarily make it any easier. However, the table contains all of the necessary data for the problem in a compact form. In fact, it will soon be seen that A contains certain redundancies and can be completely specified by an even smaller set of data. This compact description of the problem in terms of special subsets of, and arithmetic in, Z,24,41 is a computer- friendly presentation. Probabilistic searches for solutions, using a method such as simulated annealing, are particularly appropriate with this presentation. The following examples concern the arrays A for gq = 2,3,5. The indices for the rows and columns are not shown, but the last row and last column are those pertaining to L,.. and O., respectively. Braces have been omitted from the subsets in the cells of the array. In each case, w = a?!, where a is a primitive element of the field L = GF(q’) satisfying the given primitive polynomial. For g = 2 and g = 5, f= $ and H = ker Tr. The entries of the tables are subsets of the indicated group G. Example 2.16. ¢ = 2, a® +a+1=0, G= Zr. The first column of Table 2.1 0] 0 13] 0 2,61 0 45/0 1,2,4 Table 2.1: A for gq = 2 represents the 7 points of Q,; the second column represents the 7 points of the plane O... Together they account for 14 of the 15 points of PG(3, 2); the table does not represent the fixed point (1:0). The Z7-translates of the five rows together give the 35 lines of PG(3, 2). Example 2.17. ¢g=3, a®+a*—-1=0, €=a’*, G= Zi. 26 0 0 0 1 | 810/ 0 411) 3 0 2,5,6 0 9 |7,12| 0 8,10} 1 0 3 |4i1| O 25,61 0 7,121 9 0 0,2,5,6 Table 2.2: A for g = 3 Example 2.18. ¢ = 5, a? + 2a?+1=0, G = Zs. Notice that each column of Table 2.3 contains a subset of size at least 3, as was explained in Remark 2.13. Also note that aside from the orbit O,,., no point-orbit is met by any line in more than three points. Definition 2.19. A collection of subsets {8; C G | i € I} of an abelian group G is called a hyperstarter for G if, as multisets, (1) Us; =G, iel (it) {e-y | a A#y € Si} =G \ {0}. ael The following is a list of some of the properties of the tables A and A. Analogous statements for A are easily obtained by applying the automorphism p. Proposition 2.20. (i) |A(z, A)| < 3 for all (x,) € H x F*. (it) The row A(0,-) contains a total of q elements; every other row contains a total of q+1 elements. (iti) For X € F*, the column AC, A) is a hyperstarter for G. Furthermore, for any 27 0 0 0 0 0 8,15 17 21, 20 0 5, 24, 2 16 6 0 25, 27, 10 18 30 0 26 11, 1, 19 28 0 14,3 29 29, 4 0 9, 13 23 12,7 0 17 21, 20 15, 8 0 16 6 24, 5, 2 0 25, 27, 10 18 30 0 1, 11, 19 28 26 0 22 29, 4 3, 14 0 23 12,7 13, 9 0 17 21, 20 8, 15 0 6 24, 5, 2 16 0 18 30 27, 25, 10 0 1, 11, 19 28 26 0 22 29, 4 14,3 0 23 12,7 9, 13 0 20, 21 8, 15 17 0 5, 24, 2 16 6 0 30 27, 25, 10 18 0 28 26 11, 1, 19 0 4, 29 14,3 22 0 7, 12 9, 13 33 0 2,10,17,19,22,23 Table 2.3: A for g = 5 A# uw € F* U {oo}, tt holds that U A(z, \)A(a, 1)! = G, xCHUf{oo} as multisets. (iv) For X € F*, the column A(-,A) is a permutation of the column A(.,1). For s€F* andze€ G8, the row A(sz,-) is a permutation of the row A(z,-). (u) The image of any row of A under the map y + y? is again a row of A. Proof. (i) A(@,A)={e#+s|s EF, +s €rAG} ={xe+s8|seEF, Nw+s)=3}. 28 Note that N(x +s) = (@+)(a%+ s)(x¥ + s) = s° + Tr(x)s? + Tr(x?*")s + N(a). So N(x + s) = 4? if and only if s € F is a root of the cubic polynomial t? + Tr(x)t? + Tr(x?*)t + N(x) — d° € Fi]. (it) This statement follows from the fact that lines are incident with q+ 1 points. The “missing point” from the row A(0,-) is the fixed point (1 : 0), the only point of the geometry which is not in one of the orbits O,, \ € F* U {oo}. (iti) These statements follow from the fact that the points and lines of PG(V) form a 2— aa eae, 1) design, together with the fact that the lines of the geometry arise from taking G-translates of the rows of the table A. (iv) For AE F*, A(a, d) = (2 + F)N (AG) = MF +F)NG) = AS, 1). As F* = ker and |g = 1, it follows that A(z, A) = A(£, 1) for every « € HU {oo}. (v) The Frobenius automorphism of the extension L/F acts on the subgroups F < Land G < L*. Thus A(2!,d) = («2 + F)N (AG) = ((« + F) N(AG))? = A(a, d)*. Note that (a7)? = 247 to obtain the analogous result for A. 0 Remark 2.21. The proof of Proposition 2.20 (iv) shows that the column A(., A) is a reordering of the column A(-,1)induced by the permutation z > \ of HU {oo}. If A is a primitive element of F, then this permutation has two fixed points, 0 and oo, and q+ 1 orbits of length g— 1. Accordingly, a column with A € F* is a shift of the column with A = 1, where the shift is some cyclic shift of the rows with x 4 0,00. 29 That is to say, in some ordering of the elements of H and F*, the subarray of A on just the rows and columns of H \ {0} x F* is a (¢ — 1) x (q¢ — 1) block array with blocks of size (q+ 1) x 1. Furthermore, it can be arranged that the columns (rows) are cyclic shifts of the first column (row). The full array A is obtained by bordering this subarray with the z = 0 and x = oo rows and the A = oo column. Take for example the specific case g = 5. The array A which was presented in Example 2.3 already appears with this cyclic block structure. Indeed, notice that the subarray obtained by deleting the first and last rows and the last column of A has the following structure, ABCD BCODA C DAB DABC where A, B, C’, and D are 6 x 1 arrays. 2.4 A line-orbit correspondence The notation of the previous section is continued. By Theorem 2.10, there exists a cyclic parallelism of PG(V) if and only if there exists a spread of PG(V) which contains one line from each orbit of o. It has been shown that the array A gives a representation of the points and lines of PG(V) in a format which conveniently describes the orbits under o as well as the incidence in the geometry. Choosing a collection of line-orbit representatives corresponds to choosing a G-translate of each row of A; two such lines are skew in PG(V) if and only if the entries in each column of the corresponding shifted rows of A are disjoint subsets of G. The notion of choosing shifts of the rows of A leads to the following notation. Given a function » : H —+ G, write JA to denote the array which arises by 30 translating the elements of the row A(z,-) of A by v(x); that is, (pA)(z,r) = p(z)A(a, d) for « € H, X € F*U {oo}, Similarly, for ~ : H + Z24q11, WA will be used to denote the array arising from additive shifts of the rows of A by the elements (x) in the group Zg24941- Lemma 2.22. There exists a cyclic parallelism of PG(V) if and only if there exists a function : H > G such that each column of the array WA is a partition of G. An equivalent condition is obtained by replacing G with Zg+q41 and A with A. Proof. Combine Theorem 2.10, Proposition 2.12, and Remark 2.15. O Example 2.23. g = 2. The table A appears as Example 2.1. It is not hard in this small case to find ways to shift the rows of the table by elements of Z7 so that the columns of the resulting array are partitions of Z7. In fact, Table 2.4 presents the only solutions to this problem which leave the last row of A unshifted. It is worth noting 07 0 07 0 46] 3 16/5 15/6 251 3 231 5 3,4] 6 1,2,4 1,2,4 Table 2.4: Cyclic parallelisms of PG(3, 2) that these examples furnish solutions to the original problem of Kirkman. Identify the 15 schoolgirls with the 15 points of PG(3, 2). An arrangement of the 15 girls into five rows of three girls each corresponds to a spread of PG(3, 2). As any two points of PG(3, 2) are incident with a unique line (which is incident with a total of three points), the final condition of the Kirkman problem corresponds to a set of 7 spreads which partition the lines; ie, a parallelism. It is worth noting that both arrays in Table 2.4 contain the same first and last rows. An examination of Prince’s [38] exhaustive list of forty equivalence classes of 31 cyclic parallelisms of PG(8,5) reveals that the base spreads of all those examples contain the same pair of lines from the orbit of lines incident with the fixed point and the orbit of lines in the invariant plane. The same can been seen in the six inequivalent examples found by Denniston [15] for PG(3, 8). Theorem 2.25 offers an explanation for this phenomenon. For convenience, introduce the notation H = H U {oo} and F = F* U {oo}. In the following results, all arithmetic takes place in the group Z,24941. Lemma 2.24. For every A € F* U {oo}, SS S° u = 0. xeH uGA(a,d) Proof. By Proposition 2.20 (iii), each column of A with X € F* is a partition of Zo24q+1. Therefore, summing the elements of such a column amounts to summing the elements of Z24941- Since g? + q+ 1 is odd, then 2 KQ + ray k=0 (mod q’+q+1). 0 i Now suppose A = oo. Note that SY uw= Mu= SYS w= ( II v)p 2€H u€A(a,00) u€A(oo,00) veEGnker Tr v€Gnker Tr Now v € Gnker Tr if and only if {v, v4, vt } C GNker Tr. Also, v = v? if and only if v€F. As FNG = {1}, it follows that Il U= Il pitt? — 4, veGnker Tr {v,v9,07" } CGNker Tr The claim follows as 1p = 0. O Theorem 2.25. Let i: H > Zg24qi1. If each column of pA is a partition Of Zer+g+i then (0) = 0. 32 Proof. For simplicity, set 7(oo) = 0; recall that (#A)(a, A) = w(x) + A(z, 2). As- suming that each column of wA is a partition of Zq2+9+1; it follows from Lemma 2.24 that 0= S> S> ( (x) + u) 2¢H ucA(a,r) =i v@IA@AI+3> SO u aeH x€H uéA(z,d) =) ¥@)|AC,»)|- «eH Therefore, 0=S°S > v(2)IAG,»)| ACF 2€H = 3) ¥(2) SAG, A): «xeH ACF By Proposition 2.20 (ii), Ela vi=| 7 Beso, eF q+1_ otherwise. Furthermore, substituting 4 = co into equation (2.3) implies So va) = 0. 2eH (2.3a) (2.3b) (2.3c) (2.4a) (2.4b) (2.5) (2.6) 33 Therefore, 0= S- S> v(a)|A(a, A)| by equation (2.4), = gv(0) + (¢+ 1) S > v(2) by equation (2.5), 240 = 7b(0)—(q+1)d(0) —_ by equation (2.6), = —y(0). C] Corollary 2.26. [fq =0 (mod 3) then PG(3, q) does not admit a cyclic parallelism. Proof. If q = 0 (mod 3) then F Cc kerTr. In particular, 1 € GM ker Tr; hence 0 € A(co, 00). Suppose that there exists a cyclic parallelism of PG(3,q). By Lemma 2.22, there exists w : H 4 Zig41 such that each column of WA is a partition of Z 2+q+1- Theorem 2.25 implies that ~(0) = 0. Therefore, (wA)(0, 00) = W(0) + A(O, 00) = {0} C A(oo, 00), contradicting the deduction that the column A(-, 00) is a partition of Zgyqiu1. O Remark 2.27. In [13], Denniston claimed that an exhaustive search revealed that there are no cyclic parallelisms of PG(3,3), although he does not give any details of his search. He then makes the interesting remark that there is a design with the parameters of the points and lines of PG(3, 3), that is, an S(2,4, 40), which admits a cyclic resolution. He finds reference to this design in a paper of E. H. Moore [33] from the late nineteenth century. Moore specifies the following as the blocks of a spread on the point-set Z39 U {oo}: {0,13,26,co} {1,5,8,25} {2,10,11,16} {4,20, 22, 32} {14, 18, 21,38} {15, 23, 24,29} {17,33, 35,6} {27, 31, 34,12} {28,36,37,3} {30,7,9, 19} 34 Developed by the group Zzg, this spread generates a resolution of an S(2, 4,40). Notice that the design automorphism z ++ ¢ + 13 stabilizes the above base spread, fixing one of its blocks and permuting the other nine blocks in three orbits of length 3. Thus, the automorphism z ++ ++ 1 cyclically permutes the 13 spreads of a resolution of the design. This automorphism has order 39, fixes one point, is transitive on the remaining 39 points, has one line-orbit of length 13 and three line-orbits of length 39. Contrast this behavior with that found in the geometries. By Lemma 2.8, an automorphism cyclically permuting the spreads of a parallelism of PG(3, q) has order g@t+qH#l. The automorphism z +> 2+3 has order 13 and also cyclically permutes the spreads of the above resolution. It has a fixed point, three point-orbits of length 13, and ten line-orbits of length 13. Table 2.5 is the decomposition of Moore’s design into point- orbits and line-orbits under this automorphism. The three nontrivial point-orbits are O; = 137 + 3Z39, 7 = 0,1,2. Each point-orbit is projected onto 3Z39 by x + 27-2. Under the isomorphism Z 3 = 3Z39 given by 1+> 3, the decomposition is as follows. | Oo | % | O | 010! 0 4,9 | 6,7 1,12 | 5,8 3,10 | 2,11 6,7 4,9 5,8 1,12 2,11 3,10 4,9 | 6,7 1,12 | 5,8 3,10 | 2,11 Table 2.5: S(2, 4, 40) 30 Chapter 3 Cyclic Regular Parallelisms This chapter begins with an overview of a connection between spreads of projective spaces of dimension three and a special class of functions on affine spaces of dimension two, called transversal mappings. The idea to study spreads through these functions is originally due to Ostrom [35]. His interest in spreads stemmed from an interest in studying the associated translation planes and their duals; the transversal mappings provided a means to study the spreads. Here, the use of transversal mappings provides a method for representing spreads which will turn out to be very convenient for purposes searching for cyclic regular parallelisms, as regular spreads correspond to linear transversal mappings. Using these linear transversal mappings, it is shown that there exists a cyclic regular parallelism of PG(3, q) if g = 2 (mod 3). A second example is obtained from the first by the application of a polarity of the geometry, and these examples are shown to be inequivalent under PI'L(4, g). A similar result had been obtained by Pentilla and Williams in [36]. Finally, a computer search for linear transversal mappings which generate cyclic regular parallelisms of PG(3,q), ¢g = 2 (mod 3), reveals no further inequivalent examples for several small values of g. It is conjectured that the same holds for all g = 2 (mod 3). 3.1 Spreads and transversal mappings The following definition is a generalization of Ostrom’s definition of transversal map- pings to vector spaces of arbitrary dimension. Definition 3.1. Let V be a vector space of dimension n over the field F. A function f:V—-V iscalled a transversal mapping or transversal function if for each A € F the map v +> f(v) + Av is a permutation of V. Denote the set of transversal mappings of V by TM(V). 36 Remark 3.2. Vector space isomorphisms induce bijections of the corresponding sets of transversal mappings. Suppose a : W — V is an isomorphism of GF(q) vector spaces. Then a induces a bijection TM(W) + TM(V) by f 6 afag. Indeed, using the linearity of a, one has afa~!'v+Av = a(f(a7!v)+Aa™!v). Since a is a bijection, then the latter is a permutation of V if and only if wH fw-+ Aw is a permutation of W. It is straightforward to check that the map f + afa™ is a bijection. Thus, one may refer to TM(n, q) when dim W = n. The term transversal mapping, due to Ostrom, is derived from the notion of transversals in partial geometries. The particular partial geometry here is the net N defined to have as points the elements of V x V, where V = V(n,q), and to have as lines the sets {(b, x) | x € V}, {(x,Ax+b) |x € V}, forA € F and be V. Given f :V + V, define the graph of f to be the set of points ['(f) = { (x, f(x)) |xe V3. One can check that f € TM(V) if and only if [(f) meets every line of NV in exactly one point; that is, if and only if '(f) is a transversal of NV’. It can also be shown that any transversal of NV is the graph of a transversal mapping of V. It is worth noting that the definition of transversal mapping is similar to those of orthomorphism and complete mapping. Given a group G, a permutation f:G—->G is called an orthomorphism of G if the function z +> x2~1f(z) is also a permutation (where the group operation is written multiplicatively). A permutation f is called a complete mapping if the function z +> «xf(x) is a permutation. Let G = V(n,q) and f:V—-V such that 2 f(x)+Az is a permutation of V for every X € QC F. Then f is an orthomorphism if {0,-—1} C Q and f is a complete mapping if {0,1} C 2. Notice that all three concepts coincide if g = 2. In general, transversal mappings are orthomorphisms as well as complete mappings, but not conversely. Orthomorphisms arise in the constructions of, among others, triple systems, Mendelsohn designs, Room squares, and group sequencings. See [16] for some background and a survey of many results on orthomorphisms and complete mappings. Example 3.3. Transversal mappings with q = n = 2. In this case, transversal mappings, orthomorphisms, and complete mappings are the same. It is simple to 37 check that there are precisely two transversal mappings of GF(4) sending 0 to 0; they are listed in the following table. The elements of GF(4) are denoted by 0,1,w,w? where w* +w+1=0. zx 10 1 w w? fi(z) |}0 w w? 1 fo(xz) |}0 w? 1 w Example 3.4. Let L be a field extension of F = GF(q). For any 7 € L \ F, the function f(z) = Tx is a transversal mapping of L as a vector space over F. Notice that the functions in the previous example are both of this form. Indeed, fi (2) = wx and fo(r) = wz. Of greatest interest in this chapter will be transversal mappings of two-dimensional vector spaces, as these are closely connected to spreads of three-dimensional projective spaces. In order to make this clear, recall some notation introduced in the previous chapter. Let q be a prime power. Let F = GF(q) and let L be the extension of F of degree 3. The ambient vector space is V = F @L; let © denote the geometry PG(V). Pick an element € € L such that Tr(€) = 1 and set H = {x € L | Tr(€éz) = 0}. It will be particularly useful to distinguish a certain collection of planes of ©. Let Too = {(0,2) | x € L}; II, = {(t,z) | Tr(€x) = At}, for A € F. Note that these q+ 1 planes are incident with a common line {(0,x) | « € H}, which will be denoted by /,.. Furthermore, each point of II, is represented by a unique vector of the form (0,x +1), with « € H. Indeed, given y € L \ H, let y Tr(€y) Then z € A and (0:2+1)=(0: me) = (0: y), so at least one such representation always exists. On the other hand, if (0: 2+1) = (0: 2'4+1) with z,2’ € H, then x = sz’ for some s € F*. Apply Tr(€-) to the latter equation to obtain 1 = s, hence 38 x = 2’. Ina similar manner, it may be shown that each point of Ip \l.. is represented by a unique vector of the form (1,2) with z € H. The first lemma of this section establishes the equivalence between spreads which contain the line /,. and transversal mappings of H. The result is due to Ostrom, [35]. For the convenience of the reader, a short proof is included here in the notation of this work. Proposition 3.5. There is a one-to-one correspondence between the set of spreads of & which contain the line 1. and the set TM(H). Proof. Given f : H — H, define S(f) = {l;(x) | c € H}U {lo} where I;(z) is the projective line (0: 2+1)V (1: f(z)). As (0: 241) 4 (0: y) for any z,y € H, then J;(x) and J. are skew for every x € H. Now suppose z,y € H anda fy. As every point of II. \ loo. is represented by a unique vector of the form (0,z +1) with z € H, then I(x) and Ir(y) do not intersect in a point of II. Furthermore, the set of planes {II, | 4 € F} partitions the complement of II, in &. Thus, l(x) and l;(y) intersect only if they intersect in some point on a plane II). The line /;(a) meets the plane I], in the point (1: f(x) + Av +A). If l;(x) intersects I;(y) at the plane II), it follows that f(x) + Az = f(y) + Ay. Thus, if f € TM(H), then I(x) and I;(y) are skew. Therefore, S(f) is a set of g? + 1 pairwise skew lines and hence is a spread of » containing [,,. It is straightforward to see that the map f ++ S(f) is injective. To check surjec- tivity, let S be any spread of & and suppose J, € S. Recall that each point of II. \loo is represented by a unique vector of the form (0,2 +1), « € H, and each point of TIp \ loo is represented by a unique vector of the form (1,y), y € H. Furthermore, each point of & \ l.. is incident with a unique line of S \ {1,.}. Now define a map f:H — A by f(x) = y if there is a line of S which is incident with the points (0: 2+1) and (1: y). That f is well defined follows from the comments immediately above. Since S is a spread, it follows as in the previous paragraph that f € TM(H) and it is straightforward to check that S = S(f). Therefore, S is a bijection. O It would be very desirable to count the number of spreads of PG(3,q). This is 39 currently an open problem and believed to be quite difficult. A corollary of Proposi- tion 3.5 is that counting spreads is equivalent to counting transversal mappings. Let n(q) denote the number of spreads of PG(3, q). As PI'L(4, q) is transitive on ») and maps spreads to spreads, it follows that the number of spreads containing a specific line does not depend on the choice of this line. Denote by 7'(q) the number of spreads containing a certain distinguished line. Corollary 3.6. n(q) = (@+¢+ DITM(2,q)|. Proof. In two ways, count the number of ordered pairs (1,5), where S is a spread containing the line /. One obtains n(a)(a + 1) = [E§" In"). Note that |=0| = (@ +1)(? +¢+ 1), and 7'(q) = |[M(2,q)| by Proposition 3.5. The desired result now follows by substitution. | The next lemma concerns some groups acting on TM(n,q); the simple proof is omitted. Lemma 3.7. The set TM(n,q) is invariant under the following transformations: (i)f > f+ pl, where uw € F and 1 is the identity on V(n, q); (ii)f + Af +c, where \ € F* ande € V(n,q); (itt) f ++ a7 fa, where a is a permutation of V(n,q). Remark 3.8. For the purposes of counting transversal maps, it suffices, in light of Lemma 3.7 (ii), to count the number of f € TM(n, g) for which f(0) = 0. In Example 3.3 it is remarked that there are exactly two transversal maps of V (2, 2) fixing 0. Thus, there are a total of 8 transversal maps of V(2,2), leading to the well known result that there are 56 spreads of PG(3, 2). 40 To close this section, some further basic results on transversal mappings are pre- sented. While the number of transversal mappings of V(2,q) is unknown and prob- ably very difficult to determine, the same cannot be said for the number of linear transversal mappings, which is given by the first of these results. Proposition 3.9. There are $q*(q — 1)? linear transversal mappings of V (2, q). Proof. A linear transversal mapping is an endomorphism of V = V(2,q) having no eigenvalues in GF(q). Thus, it suffices to count the number of linear transformations a:V — V which do have eigenvalues in GF(q). There are three mutually exclusive and exhaustive cases: (i) a has two distinct eigenvalues in GF(q); (ii) a has one eigenvalue in GF(q) of algebraic and geometric multiplicity 2; (iii) vw has one eigenvalue in GF(q) of algebraic multiplicity 2 and geometric multiplicity 1. One can check that the number of invertible a in each of these cases is as follows: (i) $¢(q? — 1)(q — 2); (ii) ¢g — 1; (iii) (¢? — 1)(q— 1). The result follows by subtracting these totals from aq — 1)(q-1) = |GL(2, 4)]. 0 The final result concerns the representation of transversal maps as polynomials. Let F = GF(q). For any function ¢ : F — F there is a polynomial f(X) € F[X] of degree at most q — 1 for which f(x) = ¢(x) for every x € F. If f is in fact a permutation polynomial, then deg f < q — 2 by Hermite’s Criterion [25]. It was shown by Niederreiter and Robinson [34] that orthomorphisms of F have degree at most g — 3 in the case q is odd. The proof is also based on Hermite’s Criterion. The same result for gq even is due to Wan [44]. Proofs of each case may also be found in [16]. Wan’s proof is easily modified to prove the following more general result. Proposition 3.10. Let F = GF(q). Let f(x) € Flx] have degree less than q and suppose that f(#)+ 6x is a permutation polynomial for every 9 in some subset © C F. Then deg f < q— |9|. Proof. Let q = p* where p is prime. Let 1 < m < || and suppose p°||m, where 0 <e <d. It will be shown that the coefficient of the term of f(x) of degree g —m is Zero. 41 Let O be the ring of algebraic integers of some number field such that O/pO = F. Let z : O > F be the canonical surjective homomorphism and extend 7 to a homomorphism of polynomial rings O[z] > F[z] by a(x) = z. Let w be a primitive element of F and choose a € O such that 1(a) = w. Note that a?! =1 mod pO. If a?! = 1+ pp’ for some p € O and some 1 < i < e, then qd (a?) = (1+ pp')?=14+ 50 ()) ’p’ =1 mod p"O, j=l as q > p’. Since 7(a2) = w! = w, then without loss of generality it may be assumed that at !=1 mod p*tO. Let S = fa? |i = 1,...,¢-—1}U {0}. Suppose » : F > F is a permutation polynomial and VW : O + O is any polynomial with coefficients in O such that n(W(x)) = p(x). Note that {m(s) | s € S} = {7(U(s)) | s € S}. Thus, S- W(s)" = S-(s + pls)”, ses ses for some y.: S — O. Furthermore, (s + puu(s))” = s™ mod p*t'O. Thus, Sous” = So 5" (3.1a) séEs ses q-1 = S> a (3.1b) i=l a (ala) — 1) am — 1 =0 mod p70. (3.1d) (3.1c) Ill Now suppose f € F{z] is a polynomial of degree less than g such that f(x) + 0x is a permutation polynomial for every 6 € © C F. Without loss of generality, assume 0€ 0. Let F(x) € O[z] such that 7(F(x)) = f(x) and let T = {t € S | a(t) € O}. 42 It follows from equation (3.1) that S-(F(s) +ts)"=0 mod p*t'O seES for every t € T. Note that m—-1 (F(s) + ts)” =t"s™ + F(s)" + S° (") tis'F(s)"—. i=1 Since Ss” = S” F(s)™ =0 mod p**!O ses ses and p® divides (") in Z for 1 <i <m—1, then m—l SS Sop (") t's'F(s)""*=0 mod pO. seES i=1 As s?=s mod pO for all s € S, then there exist ol € O such that q-1 s'F(s\"*= So cl si mod pO. j=0 Furthermore, Sos! =0Q mod pO, ses for 1 <j <q -2, and So st =-—1 mod pO. ses Therefore, for every t € T’. Thus, the polynomial has degree m — 1 and has |T| = |Q| > m — 1 roots in O/pO & F. Thus, it must be the case that for every 7 € {1,... ,m—1}, - (4) p (™)e Co-1 =0 mod pO. In particular, noting that p*||m, it follows that Clee Y=0 mod pO. From the definition of the cl ) ’s, one has s°1F(s) =" 53 mod pO. Cj Let q-1 q-l f(z) = Ss) az’, F(x) = So bia. i=0 i=0 Then bm = ee" = = 0 mod pO, asm < gq. Finally, ag-m = 1(bg-m) = 0 as claimed. O The following corollary is immediate from the definition of transversal mapping. 44 Corollary 3.11. Let L be a finite extension of a finite field F. If f € L{z] is a transversal mapping polynomial of L as a vector space over F and deg f < |L|, then deg f < |L| — |F. Example 3.12. The above result says that all transversal mapping polynomials of GF(9) over GF(3) have degree at most 9-3 —1 = 5. The result here is sharp _ as indeed there are transversal mapping polynomials of degree 5. An example is f(x) = wa? + 24 + we? + 2? + wee, where w?+w+2=0. 3.2 Regular spreads Definition 3.13. A regulus R of © is a set of ¢ +1 pairwise skew lines with the property that any line meeting three lines of R meets every line of R. Such a line is called a transversal of FR. A line of PG(8, q) meeting a nondegenerate hyperbolic quadric in three points must be contained in the quadric. Each hyperbolic quadric admits two ruling families of q+ 1 pairwise skew lines each. As the lines of such a family partition the points of the quadric, any line on the surface is either a member of the family or meets each member in a point. These families thus form regulii. In fact, any regulus arises as the ruling family of lines of a hyperbolic quadric. The following Lemma lists some more basic facts about regulii. See [11] for proofs of these and other facts concerning regulii. Lemma 3.14. Any three mutually skew lines 1,m,n determine a unique regulus which will be denoted R(l,m,n). There are q+ 1 transversals to a regulus R, they are patr- wise skew and themselves form another regulus which will be denoted R°”?. Further- more, (RPP)? = R. Definition 3.15. A spread is called regular if it contains the regulus determined by any three of its lines. _ The proof of the following proposition can be found in [11]. 45 Proposition 3.16. [f a line | is skew to each line of a regulus R then there is a unique regular spread containing | and R. It turns out that if a spread is not regular, then it must be missing quite a few regulii. As the next lemma shows, a spread which contains every possible regulus on a given line must already contain too many regulii to avoid being regular. Lemma 3.17. Let q > 2 and let S be a spread of PG(3,q). If there exists some line lo of S such that the regulus R(lo,l1,l2) is contained in S for every pair of distinct lines ly,lg € S \ {lo}, then S is regular. Proof. Let R be any regulus of S' which contains Jp) and let m € S\R. By Lemma 3.16 there exists a unique regular spread T containing R and m. For each 1 € R\ {lo}, the regulus R(lo,/,m) is contained in ST by hypotheses on S and T. Note that RO Rlo,t,m) = {lo,U} and Ro, i,m) A Ro, l2,m) = {lo,m} for distinct 1, € R \ {lo}. Thus, for each of the q lines of R \ {lo} we find q — 2 distinct lines of (SNT)\ (RU {m}). Together with m this accounts for (¢— 1)? lines of (SNT)\ R. Suppose S # T. Let m' € S\T and let T" be the unique regular spread containing R and m’. As above, |(SMT") \ R| > (q—1)?. Furthermore, by Proposition 3.16, TOT’ =R. Therefore g(q—1) =|S\ Riz SNT)\ RI + [(SNT)\ Rl 2 Aq- 1)’, a contradiction if g > 2. Hence S = T and S is regular. CJ In the notation of the previous section, the next result’ characterizes regular spreads in terms of their associated transversal mappings. Recall L = GF(q°), F = GF(q), € € L such that Tr(é) = 1 and H = {x € L | Tr(éx) = 0}. Furthermore, V=FOL, Io = {0} OL, Ib =F OH, andl. = {0} OH. Proposition 3.18. Given f € TM(H), the spread S(f) is a regular spread if and only if f is an affine map over F. 46 Proof. By Lemma 3.17, it is enough to show that S(f) contains each regulus of the form R(lo0,l;(x),l¢(y)) if and only if f is affine. Let x,y € H with « # y. Let R = Rilo, l (x), l¢(y)). For A € F let my = (1, f(z) + At + A) V (1, f(y) Ay +A) and let Mo =(L:¢+1)V(1:y4+1). It is simple to check that RP = {m) | A € F°}. The points of m,. have as representatives the vectors (0,rz+(1—r)y+1), where r € F° and the usual conventions regarding co are adopted. The points of m) have as representatives the vectors (1, r(f(z) + Ax) + (1 —r)(F(y) + Ay) + d). For each fixed r, there exist unique s,t € F such that the following three projective points are collinear: (O:ra+(l—rjy+1), (1: sf(x)+(1—s)f(y) ), (1: (f(a) +2) +(1-t)(fY)+y) +1). Furthermore, this line is an element of F, as it is a transversal of R°PP. Note that with r = s =t, the sum of the first two of these vectors equals the third and hence these projective points are collinear. This line meets II. in the point (0, rz +(1—r)y +1) and meets IIp in the point (1,rf(z)+(1—r)f(y)). Hence, it is an element of S(f) if and only if f(re + (1—r)y)=rf(x4)+(—r)f(y). oO Remark 3.19. Together, Lemma 3.7, Proposition 3.9, and Proposition 3.18 count the number of regular spreads of & which contain the line J... Indeed, by Proposition 3.9 there are 5q°(q— 1) linear transversal mappings of H. Thus, there are 4q*(q—1)? AT affine transversal mappings by applying Lemma 3.7 part (ii). By Proposition 3.18, there are the same number of regular spreads containing |... This gives the well known result that there are $q*(q — 1)?(q? +. q+ 1) regular spreads of ©, arguing as in Corollary 3.6. One great benefit of the representation of spreads by their transversal mappings is that it is extremely easy to restrict one’s attention solely to regular spreads. This feature allows a convenient computer search for regular spreads which would generate cyclic parallelisms under the application of a certain automorphism. Indeed, choosing a basis for H, one need only run through the 2 x 2 matrices over GF(q), omitting those with eigenvalues in GF(q), and allowing arbitrary affine translations. This search revealed a family of cyclic regular parallelisms when g = 2 (mod 3) which is the subject of the remaining sections of this chapter. 3.3. The construction It was shown in Chapter 2 that if ¢ = 0,1 (mod 3) then PG(3,q) admits no cyclic parallelisms. Thus, a standing assumption for the rest of this chapter is that ¢ = 2 (mod 3). In [36], Pentilla and Williams give a construction of two inequivalent cyclic regular parallelisms of PG(3,q) when g = 2 (mod 3). Their construction is given in terms of the hyperbolic polar space Ot(6,q) via the Klein correspondence between the lines of PG(3,q) and the singular points of this quadric. This section presents a construction of a cyclic regular parallelism of PG(3, q) which was discovered independently of the result of Pentilla and Williams. The question of the equivalence of this construction with those of [36] is not addressed here. However, in Section 3.5 it is conjectured that there are exactly two equivalence classes of cyclic regular parallelisms of PG(3, q) when g = 2 (mod 3). This conjecture of course implies the equivalence of the example here with one of those of [36]. The construction presented here is given in terms of a linear transversal mapping with the notation introduced in Chapter 2. Since ¢ # 0 (mod 3), one may take €= $ and thus it will be the case that H = ker Tr. As before, let w be a primitive 48 (q7 +q+ 1)st root of unity in L. Note that w generates G. Let o : V 3 V be the linear transformation o : (¢,r) +> (t,wax). Recall Proposition 2.12, which shows that o partitions the set of lines of PG(V) into q? + 1 orbits of length g? + q+ 1. Lemma 3.20. As a projectivity of X, the map o has a unique fited point and a unique invariant plane. Furthermore, all orbits of o on the lines of © have length q?+q+1. Proof. It is straightforward to see that o fixes the projective point (1 : 0) and acts on the projective plane I. = {0} @ L. As w has order g? +q+1 in L’, it follows that o has order gq? +q+1 in PGL(V). Thus, the orbits of lines have length at most q’+q+1. Next, note that o|n,, is a Singer cycle of PG(II..), since GN F* = {1}. Therefore, all line orbits of o must have length exactly g?-+q+1. It is now trivial that there are no further fixed points or invariant planes. O Given f € TM(#), it is natural to ask whether the spread S(f) consists of a full set of orbit representatives under (co) and thus generates a cyclic parallelism under the action of (c). Let P(f) = {S(f)o* | i = 0,...,q° + ¢q} be the set of spreads generated by S(f) and o. Proposition 3.21. P(f) is a parallelism of = if and only if 3+ Dy 1) = py), - BUCO _/, f Gass 1) =I YW Bet Dy? * DY (3.2) has no solutions (x,y) € H x G \ {1} with Tr((x + 1)y) 4 0. Proof. Since o acts as a Singer cycle on the plane II,,, the orbit of the line J,, is precisely the set of lines of II... A parallelism results from the action of o on S(f) if and only if the orbits of the lines I;(x), x € H, are disjoint. It suffices to check whether or not the orbit of each I(x) meets S(f). Suppose I(x)o* = 1p(zx’) for some pair z,2' € H and0 <i < q’?+q+l1. With y =u it then follows that Tr((z+1)y) 4 0 and 3(a + 1)y Poy o> R(t Dy) 49 Furthermore, 3(a@ + 1)y ~ tle + (ay -1) = f(x)y+ A(x + ly for some A € F. Take the trace of each side of the above equation to see that _ _Tr(f(x)y) Tr((a@ + 1)y)’ yielding the desired result. Oo The following will be used as the base spread to generate a cyclic regular paral- lelism. Define 6: H + H by @(x) = «4-2. Lemma 3.22. S(@) is a regular spread of X. Proof. Note that A(x) — Oy) ALAS = (g — 971. Toy (x —y) If z,y € A and x # y, then the above expression cannot lie in F. Indeed, z?-! € F implies z € F as (¢—1,¢°+q+1) =1 when g 41 (mod 8). Further, x—y € F implies c = y as H MF = {0}. Now the above condition on the slopes of secants to the graph of 6 is easily seen to be equivalent to the condition that @ is a transversal mapping of H. Therefore, S(@) is a spread of © by Proposition 3.5. Regularity follows from Proposition 3.18 and the fact that 6 is a linear map. C] Substituting f(x) = x4 — x into equation (3.2) and collecting the resulting terms in powers of y, it follows that P(6) is a parallelism if and only if the equation (cerry yer (ce+1y*-(eH) ytt! —3(a+1)%y7+3(24+1)y = 0 has no solutions (x,y) € H x G\ {1} with Tr((z + 1)y) # 0. Applying the Frobenius automorphism of the extension L/F to the above equation results in the equation V(x,y) = 0, where W(z,y) = 6(z,y) — d(x, y)? and A(e.0) = ((e+ DP = 4 1)) yh + 3G + IY 50 Thus, P(@) is a parallelism if and only if the bivariate polynomial V(z, y) has no zeros with (x,y) € H x G \ {1} and Tr((x + 1)y) # 0. The following characterization of the zeros of W will be more than sufficient to establish that P(@) is a parallelism of &. Its proof will occupy the next section of this chapter. Theorem 3.23. For each x € L\ {—1}, if U(az,y1) = V(a, yo) = 0 and y, F yo, then N(1) # N(yo)- Corollary 3.24. P(@) is a parallelism of . Proof. Suppose x € H. Expand the polynomial U(x, 1) in powers of x and reduce modulo 2% + x? + x to obtain W(a, 1) = (@ + 1)P 4? — (@ + 1)4 — (2 +1) + (2 +1)" — 3(a +1) + 3(a + 1)9 satya? +e 41-27-24 -—1—att!— ot 2-1 + 0° 42x? 41-327 —3+4307+3 = gt tt gd ttl 4 20° = —2(x?+a2)— 27% — xt! + (27+ 2)? = 0. Thus, U(r, 1) = 0 whenever x € H, so Theorem 3.23 implies that W(z,y) 4 0 for (z,y) € Hx G\ {1}. Therefore, P(A) is a cyclic parallelism. Regularity was shown in Lemma 3.22. O 3.4 The proof of Theorem 3.23 This section contains two technical lemmas needed to prove Theorem 3.23. Lemma 3.25. Ifa €L\ {1} then the polynomial z9*! + z1+ has at most two roots in LL. Moreover, these roots are of the form _ tat Cee 51 where u € F and p? — (1 — Tr(a))u + N(a) = 0. Proof. If a= 0 then the roots of the polynomial are 0,1 and the given formula holds. So assume a € L \ {0,1}. Note that (¢+1)(q¢?-q+1)=2+4(q?—1). Thus, 2 ( githye-at — zit (2? + at) at = 2th] — — 4 at)r! z = 2? ((e 1 0) Since z cannot equal 0, it must be that (a — 1)%z— a? = pw for some p € F*. 2 Thus, z = cme Now substitute this expression for z into the original equation zit + 294 @=0 to obtain the desired quadratic satisfied by pu. O Recall that U(x, y) = ¢(2, y) — d(z,y)%. Let a(x) = (x +1)%*! — (a +1)4 B(x) = 8(@ + 1) so that ¢(z, y) = a(x)ytt! + B(x)y?. The first case for the proof of Theorem 3.23 is to assume z € F \ {—1}. In this case, a(z) = 0 and G(x) € F*. Thus, U(z,y) = B(x)(y? — y?) = 0 if and only if y € F. Distinct elements of F have distinct norms relative to the extension L/F, as (q¢— 1,3) = 1. Thus, the claimed characterization of the zeros of V holds if For the remainder of this section assume x € L\ F. Note that a(x) 4 0 in this case. Indeed, a(x) = 0 if and only if (x + 1)@-)” = 1. Using the fact that u?-! € F* if and only if u?~’ = 1, it follows that a(x) = 0 if and only if x € F. 52 Thus, it is the case that a(x), G(x) #0. For the sake of notational simplicity, the arguments to a and @ will, where reasonable, be omitted. As U(z,y) = (x,y) — d(z,y)%, it follows that U(z, y) = 0 if and only if (x,y) € F. Suppose that aytt! 4+ Byi+rX=0, (3.3) for some A € F. Let z= 3. Multiplying equation (3.3) by Batt results in gly iy = 0, (3.4) where (ad) = Aa(x)? a y= (2,2) = eer (3.58) = 3 (e+ nM —@ rye), (3.5) Note that expression (3.5b) implies that Tr() = 0; in particular, y 4 —1. Therefore, Lemma 3.25 applies to equation (3.4), yielding pty Z= (y= 1 (3.6) where ps € F and uw — w+N(q) =0. (3.7) Lemma 3.26. With z and yu as in equations (3.6) and (3.7), N(z) = —-p. Proof. Note that _ N+) 53 Furthermore, as Tr(y) = 0 and yu? — + N(y) =0, one has N+ y) = (Ht YH+MH+7) = p+ we Tey) + wT(y7**) + N(y) = (14 Tet) NG) = -N(y- De. The result is now immediate. oO To complete the proof of Theorem 3.23, suppose x € L\ F and W(z,y,) = W(x, y2) = 0. It has been shown that then there exist 1, 42 € F such that a(z)y?™* + B(a)yZ + rx = 0, fori = 1,2. Let z = woke and y% = (2,1) = pace Then there also exist [41, [ta € F such that 2 bin tf qj = (y — 1) and pu? — py, + N(%) = 0 Suppose N(y;) = N(y2). By definition of z;, one has N(z1) = N(z). By Lemma 3.26, one has N(z;) = —y;. Thus, jz, = pla. Therefore, N(q1) = Ha — Ht = be — wy = N(-p). Furthermore, by definition of 7;, one has A3N(a) N(6)? N(%i) = Hence, N(y,) = N(y2) implies that 4? = A} from which it follows, since (3,¢—1) = 1, that Ay = Ag. But then y, = y2 and hence py, = pe. Now it follows that z,; = 2a, hence y; = Yo. 54 In summary, if U(z,y,) = U(x, yo) = 0 and N(y,) = N(y), then y; = yo and the proof is complete. oO 3.5 Other examples This section concerns the investigation of further examples of cyclic regular paral- lelisms. Of course, it is easy to see that there are at least. gq — 1 additional cyclic regular parallelisms, given by F* multiples of the transversal mapping 6. However, these examples are equivalent under the group of projectivities PGL(V) of ©. An inequivalent example is produced by applying a polarity of © to the original example. This idea for producing a new example was also used in [36]. It is conjectured that there are no further examples of cyclic regular parallelisms, up to projective equiva- lence. Some reductions are offered which slightly simplify the scope of work remaining to prove such a, classification. To obtain some additional cyclic regular parallelisms, note that f : H > H is a transversal mapping if and only if Af is a transversal mapping for every € F*. Furthermore, combining Proposition 3.21 with the fact that the trace function of the extension L/F is F-linear, it follows that P(f) is a parallelism if and only if P(A) is a parallelism for every \ € F*. Thus, one obtains a family of cyclic regular parallelisms P(AO), A € F*, from the single example constructed in the previous sections. However, as mentioned above, these new parallelisms are essentially the same as ' the original example, in that they are equivalent under the group of projectivities of the geometry. Indeed, for A € F* define 7, : V -+ V by (¢,2)7) = (¢,Azx). Note that (0: uw) = (0: Au) = (0: u)7 for every u € L*. That is, 7) fixes each point of Igo. Therefore, for f € TM(A), Since 17, = loo then S(Af) = S(f)m for every € F* and every f € TM(H). 59 Finally, the projectivities o and 7, commute. Therefore, for f € TM(A), P(Af) = {SAf)o |O<i<s@ tq} = {S(f)no' |0<i< +a} = {S(flo'm |O<i<a’ +a} = P(f)n. Thus, P(f) and P(Af) are projectively equivalent. One is a parallelism if and only if the other is. Hence, the members of the family {P(A9) | A € F*} of cyclic regular parallelisms mentioned above belong to the same equivalence class under the action of PGL(V). An inequivalent example can be obtained by considering the following polarity of &. Let (-,-):V x V > F be the symmetric bilinear form 1 ((t1, £1), (to, Z2)) = tht, — 3 H(2122). That this is indeed a symmetric bilinear form is straightforward to check and merely makes uses of the F-linearity of the trace map Tr. It is also straightforward to see that this inner product is nondegenerate. Define the polarity 1: V > F by v~ = (v,v). An important property of this particular polarity is that it interchanges the point, (1: 0), and the plane, II,., which are stabilized under the action of 0. Furthermore, IL = (0: 1)V (1: 0). Since polarities send the points, lines, and planes of © to the planes, lines, and points, respectively, and preserve incidence in %, it follows that the dual of any spread which contains the lines J,, and [+ is itself another spread containing these two lines. Thus, if f is a transversal mapping of H and f(0) = 0 then there exists a unique transversal mapping of H, call it f+, such that S(f)+ = S(f+). Proposition 3.27. Let f © TM(H) and suppose f(0) = 0. Then P(f) is a paral- lelism if and only if P(f+) is a parallelism. Proof. It is straightforward to check that (vo)+ = vto7! for every v € V. Thus 56 (S(f)o*)* = S(f)-o* = S(f*)o™. Hence, P(f)” ={(S(f)o’)" |O<i<’?+q} ={S(fi)o* |0<i</+q ={S(fr)o' |0<i<?+q = P(f*), As the notation suggests, it happens that P(f) and P(f+) are duals of each other under the polarity |. Therefore, one of them is a parallelism if and only if both of them are parallelisms. Oo Thus, P(0)+ = P(@+) is a cyclic regular parallelism. It turns out that it is not equivalent to P(@); establishing this fact is the subject of the next proposition. The proof will use the fact that 0+(x) = —4(27+2z). The details of the calculation of f+ from a transversal mapping f with f(0) = 0 will be given in an appendix following this section. Proposition 3.28. P(#) and P(0+) are not projectively equivalent. Proof. For notational simplicity, let P denote the parallelism P(@). Suppose to the contrary that P+; = P for some tr € PIL(V). Let Stab(P) denote the group of collineations of © which act on the set of spreads of P. It follows that (co) and t~'(c)r are subgroups of Stab(P) M9 PGL(V). Note that q? + q +1 is relatively prime to |PGL(V)|/(? +¢4+1) = (@ + Diqt+ D(q— 1)’, since (q — 1,3) = 1. It follows that any two subgroups of Stab(P) M PGL(V) with the same maximal prime-power order dividing q? + q+ 1 are Sylow subgroups and hence are conjugate. Therefore, for some 1 < r < q?+q +1, there exists h € Stab(P) M PGL(V) such that (07) = h-'7-l(o")rh. Note that th € Npriwv((o")) and P+trh = Ph = P. Furthermore, tho‘ shares these two properties. Without loss of generality it thus may be assumed that + € Npriv)((o”)) and S(6+)r = S(9). Note that o” has a unique fixed point (1: 0) and a unique invariant plane, Io. Since 7 normalizes (0°) it follows that 7 fixes the point (1:0) and acts on the plane 57 II... Define f € PIL(L) so that (0: z)r = (0: f(x)) for x € L*. Note that (0: 2)o” = (0: ax) where a= wt, Since 7 normalizes (o”), it follows that there exists k > 0 such that f(az) = a* f(z) for all x € L. (3.8) Let q = p”. All functions from L to L are polynomials and the F-linear polynomials are those of the form g(x) = )4-++€,29+€,x% , with coefficients €; € L. The semilinear polynomials all have the form g(x?” ) for some linear polynomial g(x) and 0 <m <n. From equation (3.8), it can be seen that at most one coefficient of f(x) is nonzero; hence, f(v) = £2” for some i € {0, 1, 2}. (3.9) Recall that S(6+)r = S(@). Since 7 fixes the projective point (1 : 0) and stabilizes the plane II,,, it must be the case that 7 fixes the lines /,. and Igi (0) = Jg(0). Hence, € = f(1) € F* and f(#) = A. Furthermore, for x € H, loi (x)r = (0 :f(@+1))V(: f(0"(2))) = (0: f(z) +é)v (4 F(a!) — 3/()). This line meets II. in the point (0: ne +1). Therefore Igi(x)7 = 1o( 2) for each x € H, from which it follows that f(x) +2f(@) _ f(z) — f(z)! 5 = Z Va € H. (3.10) Since f is a permutation of H, introduce the new variable y = f(x). Note that f(a1) = f(x)! = y’, as € € F. Substituting equation (3.9) into equation (3.10) and changing variables yields (E+ 3)y7 + (26 —3)y=0 Vy € HT. (3.11) 58 Since q = 2 (mod 3), it cannot be that both coefficients of the above polynomial are zero. Thus, equation (3.11) gives a nonzero polynomial of degree less than q? vanishing everywhere on H, a contradiction as |H| = q?. Therefore no such 7 exists. Oo For g = 2 (mod 3), there are thus at least two projective equivalence classes of cyclic regular parallelisms of PG(3,q). The question arises whether there are any more. The characterization of regular spreads by affine transversal mappings gives an efficient way to answer this question by computer search for sufficiently small values of gq. This section concludes with some remarks about this search and its results. The search for cyclic regular parallelisms is based on Propositions 3.18 and 3.21. Recall that Proposition 3.18 says that regular spreads are of the form S(f) for some affine f € TM(H). Proposition 3.21 gives a necessary and sufficient condition for the set of spreads P(f) to be a parallelism. The problem is thus to determine which affine transversal mappings satisfy the condition of Proposition 3.21. The place to start is to give a description of affine transversal mappings in terms of polynomials. Proposition 3.29. Every affine transversal mapping of H is uniquely of the form (ax)? + br +c, for a,b,c € L, where (i) a+beF, (ii) c € H, and (itt) the polynomial * + Tr(a)A + Tr(a") has no roots in F. Proof. Homy(H,L) is an L-vector space of dimension 2 spanned by {z, x7}. Given an affine map f : H — L, there exist unique a, b,c € D such that f(x) = (ax)?+br+c for all « € H. Conditions (i) and (ti) of the Proposition arise from requiring that f(A) CH. As f(0) =c, it follows that c € H. In general, Tr(f(x)) = Tr((ax)*) + Tr(bx) + Tr(c) = Tr(azx) + Tr(br) + 0 = Tr((a + d)z). 59 The condition Tr(f(z)) = 0 for all z € H implies that a +b € H+ = F under the trace inner product. Thus, f : H — # if and only if conditions (i) and (ii) are met. Finally, condition (iii) arises from the requirement that f be a transversal mapping of H. As f(x) — fly) ry anda+beéF, then f € TM(#) if and only if =a(r—y)T +b atzt | —adFV 2 H\ {0}. Furthermore, for any x € L*, aizt|—_a= EF if and only if Tr(x) =c4+a%+2% =f + a gi} 4 LT: oi} . (at *)4 q =240(22*) +2(“5*) (+ ) ad ade at at = Na) (a? 74a? (X40) + (A+ a)(A+ at)) a 2 a r(at*t)) . N(a) (A + Tr(a)d\ + Tr( )) Therefore, there exists « € H \ {0} such that a?z?~' —a € F if and only if there exists € F such that A? + Tr(a)A + Tr(a?*1) = 0. Thus, f € TM(#) if and only if the quadratic polynomial X? + Tr(a)X + Tr(a%*) € FLX] has no roots in F. O Theorem 2.25 limits the search for transversal mappings f generating a cyclic parallelism P(f). With the choice 1, = {0} @ kerTr, Theorem 2.25 implies that a necessary condition for P(f) to be a parallelism is that f(0) = 0. That is, one need only consider linear transversal mappings when searching for cyclic regular par- allelisms. An exhaustive computer search over all linear transversal mappings, using 60 the characterization of Proposition 3.29, for those which generate cyclic parallelisms revealed only the two examples 0(xr) and 6+(z), along with their F*-multiples, for q € {2, 5, 8, 11, 17, 23, 29,32}. Thus, the following conjecture has been verified for all prime powers gq < 32. Conjecture 3.30. If q = 2 (mod 3), there are exactly two projective equivalence classes of cyclic regular parallelisms of PG(3, q). 3.6 Appendix: calculating f- Recall from the previous section the inner product (-,-): V x V — F given by 1 ((t1, 21), (te, Z2)) = tite — 3 t(t122) and the polarity L: V — F given by vt = (v,v). Since L maps lines of PG(V) to lines of PG(V), interchanges the lines /,, = {0} © H and F @ F, and preserves incidence, it follows that L acts on the set of spreads containing F @ F and /,,. By extension, one can define an action of | on the set of transversal mappings of H which fix 0; namely, set f+ to be the transversal mapping such that S(f+) = S(f)+. This section contains the details for calculating f~. Let f € TM(A) with f(0) = 0. Since IE = (0:1) V (1: 0) then f+(0) = 0. Let z € H anda #0. Note that I;(z)+ is skew to 1;(0) = I; therefore, I+(x)+ is skew to ons loo. So Iy(x)+ meets the plane II, in a unique point, and this point is not incident with the line I... Let u = u(x) = 2f (x)? + f(x). Note that u € H and Tr(uf(x)) = Tr(2f(x)** + f(x)’) = Tr(f(zx))? = 0. Therefore, ((0, cu + 1), (1, f(x))) = 0 for every cE F. 61 Suppose Tr(uxz) = 0. Then 1 Since 1 this assumption implies that the point (0 : u) is incident with the line /;(x)+. However, this is impossible as (0: u) is a point of J... Therefore, Tr(ur) #4 0 and Ly(z)+ NT = (0: a +1). Now let y = y(x) = 224+. Arguing as above, it can be shown that Tr(yf(x)) 4 0 I(x)" A Hy = (: Rt): and Thus, for every x € H \ {0}, je ( —3(2f(2)* + f(x) 3(227 + 2) Tr(Qxf(a)?+af(a)))} Tr(202f(x) + xf(x)) If it is further assumed that f is linear, then a more explicit expression for {+ may be given. Indeed, if f is linear then S(f) is a regular spread. Hence, S(f+) = S(f)+ is a regular spread, as it is easily seen that polarities preserve the regularity property of spreads. Thus, f+ is an affine transversal mapping. But f+(0) = 0, so f+ is also linear. Therefore, Tr (2x f(x)? + af(x)) Tr (227 f(x) + xf (z)) (227+ 2) Va € H \ {0}. f> (2f(#)! + f(z)) =- 62 Note that for each x € H, Tr (2a f(x)? + xf(x)) + Tr(2e7f(x) + xf(zx)) = 2Tr(xf(x) + xf(x)* + x7 f(x)) = 2Tr(xf(x) + af (x)? + 2f(x)”) = 2Tr(eTr(f(z))) = 2Tr(z)Tr(f(2)) = 0. Therefore, Tr (22 f(x)? + xf(z)) = —]1 for every x Tr(22%f(x) + af(x)) - veces Let 6(x) = 227+ x. Then f* (6(f(2))) = 6(x) Va € H. (3.12) Since f and 6 are permutations of H, equation (3.12) can be rewritten as f(z) =dof tod (a) Vz € H. (3.13) It remains to calculate the inverse of linear transversal mappings of H. By Proposition 3.29 a linear transversal mapping of H has the form f(x) = (ax)?+ (A — a)x, where \ € F and the polynomial X? + Tr(a)X + Tr(a?**) has no roots in F. Write f-'(x) = (bx)! + (uw — b)x for some b € L and \ € F. The equations (fo f-)(2) = (f-to f)(x) =z yield b= Sa De) (3.14) A — Tr(a) pO Tr(a)A + Tr(as*1) (3.15) Note that \? —Tr(a)A+Tr(a**") ¥ 0 by Proposition 3.29 (ti). In particular, 6~'(x) = 63 —46(x). Finally, one obtains f* (x) = —36 0 f~1 0 6(x) = (cx)* + (4 —c)x where ps is given by equation (3.14b) and _ 3a — 2Tr(a) 3002 — Tr(a)\ + Tr(ag*?))” Cc Note that for 6(x) = «1—«, one has a= 1 and A= 0. Thus, 6+ (x) = —}(x7+2z) as claimed in the previous section. 64 Chapter 4 Beyond Dimension Three As always, parallelism refers to a parallelism of the lines of PG(2n + 1,¢q). Projective spaces of dimensions greater than three may admit spreads of subspaces of dimensions greater than 1; one may wish to consider parallelisms consisting of these subspaces. However, the concern here will be confined to parallelisms of lines and thus the term parallelism will remain unqualified. Surprisingly little is known about parallelisms of projective spaces of odd dimen- sion greater than 3. Despite being among the most well-known designs, and possessing the basic numerical parameters necessary to admit resolutions, the design of points and lines of PG(2n + 1, q) is only known to be resolvable in the following cases: e PG(2n — 1,2) is resolvable for all n > 2, due to Baker [2]; e PG(2' — 1,¢q) is resolvable for all i > 2 and any prime power q, due to Beu- telspacher [9]. There is no instance for which it is known that PG(2n—1, q) fails to admit parallelisms. In particular, the question of resolvability for PG(5, q) is open for every prime power q > 2. Beutelspacher’s construction [9] does not result in cyclic parallelisms. On the other hand, Baker’s constructions of parallelisms of PG(2n — 1, 2) are cyclic. In fact, in [3], a variant of his construction of [2] yields a pair of orthogonal cyclic parallelisms of PG(2n — 1,2) ifn #2 (mod 3). Two parallelisms P and P’ are said to be orthogonal if |S..S’| < 1 for any pair of spreads S € P and S’ € P’. These examples of Baker appear to be the only examples of cyclic parallelisms in dimensions greater than 3. Section 4.1 contains a construction of a set of skew line-orbit representatives un- der the action of a Singer cycle on projective spaces of even dimension. A second construction, this time in PG(2n — 1, 2), gives a partial spread consisting of represen- tatives of all line-orbits not contained in the invariant hyperplane of an automorphism 65 of order 6(2n—2, 2). Section 4.2 concludes the chapter with a discussion of some open problems relating to parallelisms in dimensions greater than three. 4.1 Partial solutions Suppose a € PI'L(2n, q) acts transitively on the spreads of a parallelism of PG(2n — 1,q). By Lemma 2.8 and Theorem 2.10, g # 1 (mod 2n — 1), a is a projectivity, 2n—L 4 “i + Furthermore, a fixes a and all line-orbits under a have length 6(2n — 2,q) = point and acts as a Singer cycle on some hyperplane II. As there are (g?" — (g"" — 1) ( —-I@-1) lines of PG(2n — 1,q), then there are orbits of lines under a. The number of orbits of lines which are not lines of IT is A(2n — 2,q) — (2n — 3,q) = 9g". The number of orbits of lines of II is then ger? —] Constructing a parallelism of PG(2n — 1,q) with n > 3 involves a new problem which did not arise in the construction of parallelisms of PG(3, q). Essentially, there are two kinds of line-orbits under a: orbits of lines of II and orbits of lines which are not lines of II. In dimension 3, there is only one of the former. It is thus trivial to select a collection of pairwise skew representatives of the orbits in the invariant plane; any line of the plane will do. However, in the case n > 2, the automorphism now has a plurality of line-orbits in the invariant hyperplane and the selection of pairwise 66 skew representatives is no longer trivial. What follows are two partial solutions, one for each of the two types of line-orbits. Unfortunately, the two solutions together do not form a spread and hence do not furnish a construction of a cyclic parallelism. Let F = GF(q) and let L be the extension of F of degree 2n — 1. Regarding L as an F-vector space, the geometry © = PG(L) will serve as the model of PG(2n — 1, q). The elements of L represent the points of the geometry, with z,y € L* representing the same point if and only if 4 ¢ F*. As usual, let N and Tr denote the norm and trace functions of the extension L/F. Let G = ker N and note that |G] = 0(2n—1,4). Let w be a primitive element of L and define ¢o € PGL(L) to be determined by the linear map z+ wa. Note that o is a Singer cycle of ©. Lemma 4.1. The automorphism o partitions the lines of %: into cot orbits each of g?@?-1-1 length qi ger-1-1 Proof. As the order of o is 6(2n — 1,q) = ai it suffices to show that there are no short orbits of lines. Suppose x,y € L* represent distinct projective points; that is, “ ¢ F. Suppose further that o* fixes the line x V y of ©. With a = w%, it follows that for some a,b,c,d € F, one has ax = ax + by (4.1a) ay = cx + dy. (4.1b) As x # 0, dividing by x results in a = a+ 6%. Substituting this expression into equation (4.1b) and again dividing by z results in the equation y\* y b{ = —d)—~—c=0. 4.2 (4) +@-a—c (4.2) Since # is a root of this quadratic polynomial, * ¢ F, and L is an extension of F of odd degree, it must be that each of the coefficients of the polynomial in equation (4.2) is 0. Therefore, b =c=0 anda=a=de€F. The result follows as a € F if and only if 6(2n — 2, q)|k. O 67 Remark 4.2. If it is further assumed that (2n —1,q—1) = 1, then it is the case that gr se orbits each of length ee All that is used to show this fact is that (w?') 7 F* = {1} under this the automorphism oc! also partitions the set of lines of © into assumption. The following construction reduces, upon restriction to the case q = 2, to that given by Baker for a partial spread of PG(2n — 2, 2) representing each orbit. under the action of a Singer cycle [2]. Define v : L x L + L by (x,y) = xy — xy? Let S={zVy|v(x,y) € F*}. Proposition 4.3. S is a partial spread of PG(L) containing exactly one line from each orbit under o. Proof. Let x,y € L* such that 4 ¢ F. It holds that v(z,y) =¢ € F if and only if qd _ @ = treo), (4.3) x The equation z — z? = u has solutions in L if and only if Tr(u) = 0, in which case the solutions are given by 2n—3 k z=s+ Soe Sout, for s EF, (4.4) k=0 = é=0 where € is an element of L such that Tr(é) = 1; see [21, Theorem V 7.6]. Hence, v(x, y) € F* if and only if Tr(z~%+) = 0 and y = sr+tf(x) for some s,t € F, where 2n—3 k f(z) = S- er Soa arn, k=0 i=0 That is to say, v(z,y) € F* if and only if Tr(a~“)) = 0 and y € spanp{z, f(x)}. Now suppose S contains two lines, J; and /., with a common point x. Choose a point 68 y; on J; so that 1; = spang{z,y;}. By the above, y; € spanp{z, f(x)}, for i = 1,2. But then 1; = ly, proving that S is indeed a partial spread. It remains to show that for each line PG(L) there is some power of o which maps that line to a line of S. Note that (2Vy)o* = (w*x)V(w*y). Thus, given any x,y € L* with ¥ ¢ F, it suffices to show that there exists a € L* such that v(az,ay) € F*. But v(ar,ay) = atty(x,y). Also, v(z,y) # 0 as x,y # 0 and 4 ¢ F. Setting a =v(z,y)%"2), one checks that at y(x,y) = v(x, y) Cr = N(v(a,y)) € F*, as desired. O Remark 4.4. If v(z,y) € F*, then the points of the line xz V y are represented by {a +Ay|A€F°}. Thus ]] @+y) =2y [] @ +9) = 2%y - ay? eF*. EFS \eF* Under the isomorphism L*/F* = Zog2,_2) determined by wF* +> 1, the lines of Theorem 4.3 are thus the so-called zero-sum base blocks of the associated cyclic aviiler difference family in Zg(2n—2). For the next construction, one must return to odd dimensional projective spaces. The construction applies only to PG(2n — 1,2), however. Again, let F = GF(2), L = GF(2?""'), and let w be a primitive element of L. As in the previous chapters, set V =F @L and define 0: V > V by (t,x) + (¢,wa). Let H = ker Try,p and let I= {0} OL. Given a transversal mapping f of H, let S(f) = {l(z) | x € F} where Ip(x) = (0:24+1)V(1: f(x)), as in Chapter 3. 69 Proposition 4.5. Let f(z) = x*+2. Then f € TM(H) and S(f) is a set of orbit representatives under (o) of the lines of PG(V) which are not contained in II. Proof. It is straightforward to check that f is a transversal mapping of H. Note that [L : F] odd implies that 1 ¢ H; this is needed in order that f(z) itself is a permutation. To see that lines of S are from different orbits of (o), note that {(0:1)V(1:2)|2¢€H} is a set of representatives of the orbits under o which are not contained in II. Finally, if2+1=w*, then l;(z)o-* = (0:1) V(1: 2), completing the proof. O It was shown in the proof of Theorem 4.3 that a point of 5 = PG(L) represented by x € L* is on a line of S if and only if Tr(a~“+) = 0. Note that Tr(a? to +49") Tr(altat +") Ny) NG@) Tr(a @t)) = Thus, the set of points of L* covered by lines of S is Hr~1, where 7 is the automor- phism of L* given by 2 H altat-+9"""" Note that Hr # H. In particular, it is not possible to combine the constructions in Proposition 4.3 and Proposition 4.5 to obtain a spread of V = F @ L generating a cyclic parallelism of PG(V). 4.2 Open problems The following example can be combined with the construction in Proposition 4.3 to obtain a cyclic parallelism of PG(5, 2). Example 4.6. Let L = GF(32), F = GF(2) and let w be a primitive element of L satisfying w° + w* + 1 = 0. Work in Zs; rather than L*, under the isomorphism 70 p:wt>1. Then (ker Tr)p = {1, 2, 3, 4,6, 8, 12, 15, 16, 17, 23, 24, 27, 29, 30}. The following sets are obtained from a spread of ker Tr containing one line from each of the five orbits of lines under the Singer cycle 7 > wz: {1,3, 29}, {2,6, 27}, {4, 12, 23}, {8, 24, 15}, {16, 17, 30}. This motivates the following interesting question, which was raised by Fuji-Hara, Jimbo, and Vanstone in [18]. Problem 4.7. Is it possible to partition the lines of PG(2n, q) into sets each of which is a spread of some hyperplane and so that each hyperplane is partitioned by one of these sets? Example 4.6 gives a cyclic solution of this problem in PG(4, 2) and is among those presented in [18]. These authors, with the help of a computer search, find solutions to this problem for PG(2n, q) with e g=2 and né€ {1, 2,3, 4, 5}, e g=3and ne {1,2,3}. The examples with g = 2 can be combined with the construction in Proposition 4.5 to obtain cyclic parallelisms of PG(2n,2), 1 <n < 5, which are not equivalent to those constructed by Baker. Trying to complete the other partial solution of Section 4.1 to a cyclic parallelism raises the next question. Problem 4.8. Can the construction given in Proposition 4.3 be extended to a cyclic parallelism of PG(2n — 1, q) for any values of g > 2 and n > 2? The smallest case for Problem 4.8 is PG(5,3). In this case, one might also try to extend the example of [18] for PG(4, 3) to a parallelism of PG(5, 3) by finding an 71 appropriate transversal mapping of ker Trgp(35)/qrr3)- As there are 81 orbits of lines which are not contained in the invariant hyperplane of an automorphism with line- orbits of length 121, an exhaustive search is not feasible. A random search based on the method of simulated annealing produced no examples extending either of these sets of lines. 72 Part II Singer Subgroup Orbits As Two-Intersection Sets 73 Chapter 5 Background The material in this part is based on a joint paper with B. Schmidt, [40]. That paper presents most of these results from the point of view of irreducible cyclic codes; here the presentation is in terms of two-intersection sets. While the problems are essentially equivalent, the geometric language seems more appropriate in light of Part I. A two-intersection set of PG(n — 1,q¢) is a set of points which is met by every hyperplane in one of two numbers of points. The aim of these investigations is the classification of subgroups of Singer cycles whose point-orbits are two-intersection sets. A basic identity due to McEliece relates the sizes of the hyperplane intersections with Singer subgroup orbits to certain linear combinations of Gauss sums via the Fourier transform. Parseval’s identity for Fourier transforms and Stickelberger’s Theorem on the prime ideal factorization of Gauss sums suffice to establish “simple” numerical conditions on the parameters of these orbits which are necessary and sufficient for the orbits to be two-intersection sets. Finally, a classification of two-intersection sets which are orbits of subgroups of Singer cycles is conjectured; the classification is based upon classifying the corresponding solutions to the necessary numerical conditions. 5.1 Definitions and equivalent problems Definition 5.1. A subset X consisting of h points of PG(m — 1,q) such that every hyperplane meets X in h, or he points is called a projective (h,m, hi, hz) set. Other common terms for X are a set of type (hi, hz) or projective two-intersection set. Here are several common examples of two-intersection sets in projective planes. Example 5.2. Any subspace of PG(m — 1, q) is a two-intersection set. Indeed, a di- mension k subspace is either contained in a hyperplane, or else is met by a hyperplane 74 in a dimension k — 1 subspace. Thus, a dimension k subspace is a set of type q®—1 ge '-1 q-1’ q-1 / Example 5.3. A Baer subplane of PG(2, q’) is a set of g?-+q+1 points met by each line in 1 or q+ 1 points. This set of points, together with the lines incident with q+1 of its points, forms a projective plane of order g. One obtains an example of such a set by considering the GF(q)-subspace of V (3, q’) consisting of vectors whose coordinates each live in GF(q). Example 5.4. The singular points of a nondegenerate Hermitian form on PG(2, gq’) is an example of a set of g? +1 points met by each line in either 1 or q + 1 points. Such sets are called unitals; those arising in this manner from a Hermitian form are called Hermitian, or classical, unitals. Example 5.5. An oval of PG(2,q) is a set of g +1 points, no three of which are collinear. An example of an oval is a nondegenerate quadric. If q is even, then the tangents to an oval are coincident with a point called the nucleus of the oval. Together, an oval and its nucleus form a (q + 2)-set of type (0,2) called a hyperoval. Let o be a Singer cycle of PG(m — 1,q). It turns out that the sets described in Examples 5.2 and 5.3 can sometimes arise as an orbit under a subgroup of (c). It will shortly been seen that orbits of subgroups of Singer cycles are good candidates for examples of sets with few intersection numbers. The idea to consider these Singer subgroup orbits as a source of such examples for isn’t particularly new; see [4], for example. What is new is the main result of the next chapter which characterize the parameters of those Singer subgroup orbits which are two-intersection sets. Before proceeding further, some notation is needed. Let g = p’ for some prime p and some t € Z,. Let F = GF(q) and let L = GF(q”). Let © denote the geometry PG(L), which will serve as the model of PG(m—1, q). The points of & are then of the form «F, for x € L*. Two elements x,y € L* represent 79 the same projective point if and only if y € F*. For a € L* let Ay = {x eL | Trpr(az) = O}. The collection {H, | a € L*} is then the set of hyperplanes of ©. Note that if z = Ay with A € F* then H, = H,. Finally, let o € PGL(L) be determined by the linear map % +> wx, where w is a primitive element of L. Thus o is a Singer cycle of ™. The order of o is (¢” — 1)/(q — 1). The main problem is the determination of conditions on the parameters q,m,u so that the orbits under the subgroup (c“) of index wu in (o) are two-intersection sets. Suppose u divides (g™ — 1)/(q — 1) and let U be the subgroup of L* of index u. Set s(q,m,u) = {F | 2 € U}, a collection of points of &. Note that w% generates U and that F* < U. Thus, s(q,m, u) is an orbit under the action of (0%). Let h(a) = |{xF | c € H,NU}|, the number of points of s(q,m, u) incident with the hyperplane Hy. Proposition 5.6. h(a) = 7|HiN (aV)|. Proof. Simply note that H,M (aU) = H,NU. Also, « € H, OU if and only if At € H, OU for 4 € F*, as H, is an F-subspace of L and U < L*. Cl Here is a simple but important corollary. It explains why the sets s(q,m,u) are good candidates for sets with few intersection numbers, motivating in part these investigations. Corollary 5.7. The number of distinct values of the hyperplane intersection function h is at most the number of orbits of x > px on Z,. Proof. The field automorphism x +> z? acts on each subgroup of L*, hence U? = U. 76 Also, Trpr(2?) = Tryr(x)?, so H? = Hy. Therefore, 1 1 P\ — PU | — ——_— = h(a?) 7 [Hane U| 7 ja Nad] h(a). As h(a) = h(ax) for every x € U, it follows that A can be regarded as a function on L*/U = Z,. O The rest of this section is devoted to a brief description of two problems which are equivalent to the one considered so far. 5.1.1 Two-weight irreducible cyclic codes For the necessary terminology from coding theory, see [42]. Definition 5.8. Let f be an irreducible divisor of r”—1 over GF(q) where (q,n) = 1. The cyclic code of length n over GF(q) generated by (2” — 1)/f is called a minimal cyclic code or an irreducible cyclic code. The following definition is narrower, but essentially equivalent to Definition 5.8, see Remark 5.10 below. It will prove to be more useful in understanding the corre- spondence between these codes and projective two-intersection sets. Definition 5.9. Let L/F be an extension of finite fields of degree m where F has order q. Let n be a divisor of g™” — 1, write u = (¢” — 1)/n, and let w be a primitive yeh. nth root of unity in L. Define n-1 elas u) = { e(y) = (Truye(oe")) c(q,m, u) is called an irreducible cyclic code over F. It can be shown that the dimension of c(q,m, u) is ordn(q), cf. [42, Thm. 6.3.1]. Remark 5.10. If w is allowed to be an arbitrary nth root of unity in Definition 5.9, then by the argument of [42, Thm. 6.5.1], the two definitions above would be equivalent. However, in the case where w is a non-primitive nth root of unity, the 77 codewords of c(q,m, u) are periodic with period ord(w). Thus it suffices to consider the case where w is a primitive nth root of unity. Definition 5.11. Let w(y) denote the Hamming weight, or number of nonzero co- ordinates, of c(y) € c(q,m,u). If w takes at most two nonzero values, c(g,m, u) is called a two-weight irreducible cyclic code. Important contributions to the determination of the weight distributions of irre- ducible cyclic codes can be found in [5, 7, 24, 31]. In general, this is a very difficult problem. Even the two-weight irreducible cyclic codes have not yet been classified. The following simple fact establishes the equivalence of two-weight irreducible cyclic codes and cyclic two-intersection sets. Proposition 5.12. Let o be a Singer cycle of PG(m — 1,q) and suppose u divides (qg™ —1)/(q-—1). Then the irreducible cyclic code c(q,m,u) has at most two nonzero weights if and only if each orbit under (o“) on the points of PG(m — 1,q) is a two- intersection set. Proof. The definitions of the functions w and h immediately imply that q™ 1 w(a) = — (q~- 1h). 5.1.2 Sub-difference sets Recall that a (vu, k, A)-difference set in a finite group G of order v is a k-subset D of G such that every element g # 1 of G has exactly » representations g = d,dz' with d,,d_, € D. The parameter k — A is called the order of D. For a detailed treatment of difference sets, see [8]. Let L and F be as before and let G = L*/F*. It is a well-known fact that Ly = {xF* € G | Tryr(x) = 0} is a difference set in G with parameters q-1* q-1? q-l1 jp’ (v, k, A) = ( 78 called the Singer or trace zero difference set. The following observation is basically due to McFarland [32]. Proposition 5.13. Let D be a (v,k, )-difference set in a group G, and let N be a normal subgroup of G. If |DNNg| © {a,b} for some nonnegative integers a, b and allg € G, then E:={Ng:|DNNg| =a} is a difference set in G/N. In the situation of Proposition 5.13, call Ea sub-difference set of Din G/N. It is straightforward to prove the following. Corollary 5.14. Let q be a power of a prime p, let F = GF(q) and let L = GF(q™). Let U < L* of inderu. Finally, let Lo be the Singer difference set of G = L*/F*. The set s(q,m, u) is a two-intersection set in PG(L) if and only if Lo has a sub-difference set EF in G/(U/F*) = L*/U. Furthermore, p is a multiplier of E. 5.2 The role of Gauss sums An identity of McEliece [31] expresses the weights of irreducible cyclic codes as linear combinations of Gauss sums. Under the correspondence discussed in Section 5.1.1, an analogous result holds for orbits of powers of Singer cycles and their hyperplane intersection numbers. Before stating the result, the definition of a Gauss sum is recalled, along with one very basic fact. For a proof, see [26, Thm. 5.11]. The notation ¢ = e?7/* will be used. Definition 5.15. Let r = p* be a prime power, F = GF(r), and let x be a character of F*. We define Gr(x) = So x(a) cer where Tr denotes the absolute trace map from F' to GF(p). 79 Lemma 5.16. If y is nontrivial, then IGr(x)? =r. The following is essentially McEliece’s identity from [31]. Here it has been trans- lated into the geometric language from the language of irreducible cyclic codes. For the convenience of the reader, a proof is included. Lemma 5.17 (McEliece). Let L/F be an extension of finite fields of degree m where F = GF(q). Let u be a divisor of (¢” — 1)/(q—1). Let U be the subgroup of L* of index u and let Tl be the subgroup of characters of L* which are trivial on U. For a € L*, the number of points of s(q,m,u) incident with H,, is given by Ma) == (“42 > CuK) (5.1) UX qa xeP\{1} forx €P\ {1}, Gr(x)=¢ >> h(a)x(a). (5.2) acL*/U 1 ray Proof. Note that (5.1) follows from (5.2) by Fourier inversion, see Lemma 5.27 of the Section 5.3, and the fact that 80 Using Lemma 5.25 of Section 5.3, one obtains Gr(x) = So xg xeéL* = Yox@vge acL*/U zeU = YF x So r+ YO gre) ac€L* /U 2eUnHa x€U\ Ha = SY x@ (vow - UA Rel) acéL*/U = YS x(a)(ah(a) - + —) acL*/U ulg 7 1) = q >> h(a)x(a) acL*/U O Remark 5.18. With U = F* above, one has h(a) = 1 if a € Ay and h(a) = 0 otherwise. Hence, Gi(x) = ¢x(Z), where L is the Singer difference set in L*/F*. This result, relating character values of the Singer difference set to Gauss sums, is due to Yamamoto [46],[17]. Corollary 5.19. Suppose p is prime and u divides (p™—1)/(p—1). Then s(p', m, u) is a two-intersection set in PG(m—1,q) if and only if s(p, mt, u) is a two-intersection set in PG(mt — 1,p). Proof. By equation (5.1), there are exactly two distinct hyperplane intersection num- bers if and only if the map ary So Gr(X)x(a) xel\{1} is two-valued. Simply note that this sum depends only on the field L and u, parame- ters which are the same for s(p‘,m,u) and s(p, mt, u). 0 81 Remark 5.20. In view of Corollary 5.19, for the classification of which sets s(q, m, u) are two-intersection sets, it is enough to consider the case where q is prime. Of course, it is always assumed that wu divides (g” — 1)/(q — 1). The following are some facts concerning Gauss sums which will be needed later. A well known result of Stickelberger [41] completely determines the factorization of Gauss sums into prime ideals. As a preparation for the formulation of Stickelberger’s theorem, it is worth recalling the factorization of rational primes in certain cyclotomic fields. A proof of this result can be found in [22, pp. 196-198]. Let » denote the Euler totient function. Result 5.21. Let p be a prime and q =p’. Then p factors in Q(Eq-1) as (p) = I]. where t = p(q —1)/f and the 7; are prime ideals. Furthermore, in Q(&j-1, &)), each m7; 18 the (p — 1)th power of a prime ideal. The next result is known as Stickelberger’s theorem. For a proof, see [45, Prop. 6.13]. For a positive integer z, let S,(x) denote the sum of the p-digits of «. Result 5.22. Let p be a prime, and q = p* be a power of p. Let m be a prime ideal of Q(E,-1) above p, let * be the prime ideal of Q(E-1,€)) above 7. Let vz denote the 7- adic evaluation. Let w = w(m) be the Teichmiiller character of GF(q)* corresponding to m (see [45, p. 96] for the definition of w). Then Vi(G(w")) = S(9) forl<j<q-l. The final background result is the Daveport-Hasse Theorem, see [26, Thm. 5.14], concerning values of Gauss sums relative to field extensions. 82 Result 5.23. Let r be a prime power and let E be an extension field of F = GF(r) of degree s. Let x be a character of F* and define a character x’ of E* by x'(x) = x(Nuyr(z)) where Ngyp denotes the norm function of E relative to F. Then Ga(x’) = (-1)°"Ge(x)°. The above results yield the following corollary which will prove to be quite useful in later analysis. Corollary 5.24. Let p be a prime wu be a positive integer with (u,p) = 1. Write f := ord,(p). Define O(u, p) = ——qnin{ s,(#2=2) [l<j< uw}. Let s be a positive integer. If u divides (psf — 1)/(p — 1), then p°™») is the largest p-power dividing G(x) for every nontrivial character x of GF(p*!)* such that x“ is trivial. Proof. By (5.2), G(y) € Z|&]. Thus Stickelberger’s theorem and Result 5.21 imply that @(u,p) is an integer. Now the assertion follows from Stickelberger’s theorem together with the Davenport-Hasse theorem. CO 5.3 Appendix: Fourier analysis This appendix lists some very basic facts about Fourier analysis on finite abelian groups. See [29] for proofs. For an abelian group G,, let G denote its character group, and for a subgroup W of G, write W+ for the subgroup of all characters which are trivial on W. Identify G with fe by g «+ 7, where 7, is the character of G with T(x) = x(g). The following orthogonality relations are extremely useful. Lemma 5.25. Let G be an abelian group, let U be a subgroup of G, and let W be a subgroup of G. Then 83 (a) Vrgev X(g) = 0 for all x € G\U+; and (b) yew X(g) = 0 for allg eG\ W". As a consequence of the orthogonality relations, one gets the so-called Fourier inversion formula. Lemma 5.26. Let G be an abelian group, and let A= 7 cq dg € ZG]. Then Og = a >> x(Ag™) xEG for all g EG. Sometimes it is convenient to express Lemma, 5.26 in terms of Fourier transforms. Let G be an abelian group, and let f : G + C be a function, where C is the field of complex numbers. The Fourier transform of f is a function f :G > C defined by fod = 14-2 * F@)x(9). gE&G Lemma 5.27. Let G be an abelian group, and let f: G— C. Then f =f. One consequence of Lemma 5.26, is Parseval’s identity. Note that )7 <q |f(9)/? is the coefficient of 1 in AAW” if we let A = dca f(g9)9- Lemma 5.28. Let G be an abelian group, and let f :G— C be a function. Then SIF? = So 1fOOP. geG xEG 84 Chapter 6 Necessary and Sufficient Conditions The main result of this chapter gives necessary and sufficient conditions in order that orbits under a subgroup of a Singer cycle are two-intersection sets. In addition to furnishing a computationally more efficient method to determine if an orbit s(q, m, u) is a two-intersection set, these conditions also furnish a method for classifying the resulting two-intersection sets according to properties of the corresponding solutions to the necessary equations. The two known infinite families of two-intersection sets which are of the form s(q,m, u) can be identified among all solutions to the necessary equations, leaving what is conjectured to be a small list of exceptions. 6.1 The main result In light of Remark 5.20, it suffices to consider the sets s(p,m,u), where p is prime. Theorem 6.1. Let p be a prime, and let u, m be positive integers such that u divides (p™ — 1)/(p — 1). Let @ denote 6(u,p), let f = ord,(p), and let fs = m. Then s(p,m, u) is a two-intersection set in % if and only if there exists a positive integer k satisfying k|u-1 (6.1a) kp =+1 (mod u) (6.1b) k(u — k) = (u— 1)p°F-?9), (6.1c) Proof. As usual, L denotes GF(p™). Let U be the subgroup of L* of index u and let I’ be the subgroup of characters of L* which are trivial on U. Let G = L*/U. 85 Necessity. Define v(a) = p(h(a) — h(1)). Note that v, like h, may be considered as a function on G. Also note that [ & G. As ; SMa) = = aéG it holds that w(x) = a —pu2h(1), by Lemma 5.25 (6.2a) =u 2Gz(x); by Lemma 5.17. (6.2b) Now suppose s(p,m, wu) is a two-intersection set. Then there exists some nonzero integer 6 such that v(a) € {0,6} for alla € G. For y ET \ {1}, it was just seen that Gi(x) = Do v(@)x(a). (6.3) acG As 6 divides v(a) for each a € G, then 6 divides the right side of equation (6.3) in the ring Z[€,]. Thus, 6 divides Gy(x) in Z[€,] for each y €T \ {1}. By Lemma 5.16 and Corollary 5.24, 6=p* for some e < sé. (6.4) On the other hand, equation (5.1) of Lemma 5.17 implies that for each a € G, wa)= S> Gr0d(x(a) 1). (6.5) xeP\{1} Recall that p°’|Gy(x) in Z[£,] for every y € T \ {1}, by Corollary 5.24. Therefore, as (u, p) = 1, it follows that p*’|v(a) in Z[E,] for every a € G. Hence, p® divides 6. Combine this fact with equation (6.4) to obtain 6 = +p”. 86 Next, define D = {a € G | v(a) = 6}; d= |D|. Thus, d(1) =u? > v(a) = tdpu-2. acG Comparing this with the previous expression for D(1) given in equation (6.2), one obtains dp? =+1 (mod u). Finally, Parseval’s identity applied to the function v yields d 280 u—-1 sf U U by Lemma 5.16. This expression simplifies to d(u — d) = (u — 1)p*F-?®), If f = 260, take k = u—1. Otherwise, p divides exactly one of d and u — d; the other must divide u— 1. Take k equal to the latter. Sufficiency. Suppose conditions (6.1) hold. Let pf —] pl (ps(f—%) _ ek) v= pa) — a ; (6.6) where e € {+} is determined by (6.1b) so that ekp® =1 (mod u). (6.7) Define h(a) -—2x y(a) = ~ peel It is claimed that y(a) € Z for every a € G. Note that uh(a) — 2} s(f-0) _ ok y(o) = Oe, eek (6.8) up? 1 au 87 By equation (6.7) and the fact that pf = 1 (modu), it follows that u divides (p°F-9 — ek). Next, note that by equation (5.1) sf sf-1 _ ur(a) 2 —* =F 42 Geox) -Z=* 00) p-l pol xel\{1} = —pft 4+ SS) Gu) X(a). (6.9b) xeT\{1} = 1, it remains only to show that p*—! divides Since u divides os ula) ~ uh(a) — fact. that - divides Gy(x) for every y € T \ 1. by Corollary 5.24. Hence, the function y is integer-valued. Since 37 -¢ h(a) = (p¥ — 1)/(p — 1) then = i a) S/7(a) = oa — “1 pI + p ek (6.10a) = —ek. (6.10b) acG Hence, 4(1) = —eku72. For y ET \ {1}, ery) — BOX) _ G20 WOO = Fee=t = yt Applying Parseval’s identity results in , w= vpr™ SS 9(a) = 7 acG As it is assumed that k(u — k) = (u — 1)p*-?®, it follows that Yo 7a) =k. acéG Since y is integer-valued, then y(a) € {0,—e} for every a € G. Thus, s(p,m,u) is met by hyperplanes of © in one of two numbers of points. O 88 Corollary 6.2. Suppose the set s(p,m, u) is a two-intersection set of &. With k and € as in Theorem 6.1, the hyperplanes meet s(p,m,u) in one of the following numbers of points: pt —1 7 p- (pI) — ek) u(p — 1) u hg = hy — ep}. ? 6.2 On the classification Theorem 6.1 can be used to classify those two-intersections sets arising as orbits under subgroups of Singer cycles by classifying the corresponding solutions of (6.1). In the following, only the sets s(p,m,u) with p prime are considered; see Remark 5.20. 6.2.1 Subspaces and semiprimitive sets There are two known infinite families of two-intersection arising as orbits under sub- groups of Singer cycles: the subspaces and the semiprimitive sets. The corresponding solutions of (6.1) are described in this section. The most obvious two-intersection sets of the form s(p,m,u) arise if the index u subgroup of L* is the multiplicative group a subfield of L, see Example 5.2. U is the multiplicative group of a subfield K 2 GF(p*) of L = GF(p™) if and only if u = (p™ — 1)/(p* — 1) for some alm. From the proof of Theorem 6.1, one can see that k = (p™~* — 1)/(p* — 1) in (6.1) and thus 6(u, p) = a for a subspace of the form s(p,m, u). Proposition 6.3. The subspaces which arise as s(p,m,u) exactly correspond to the solutions of (6.1) of the form u= (p™ — 1)/(p* — 1) k = (p™™* — 1)/(p* — 1) s=l. 89 The next class of two-intersection sets arising as orbits under subgroups of Singer cycles is the class of semiprimitive sets. A prime p is called semiprimitive modulo u if —1 is power of p modulo wu. The orbit s(p,m,u) will be called a semiprimitive set if p is semiprimitive modulo wu. Note that (6.1) has a solution with k € {1,u— 1} if and only if 0(u,p) = f/2. By [6, Thms. 1,4], @(u,p) = f/2 if and only if p is semiprimitive modulo wu, giving the following result. Proposition 6.4. There is a solution of (6.1) with k € {1,u — 1} if and only if p is semiprimitive modulo u. Remark 6.5. If p is semiprimitive modulo u, then it follows from Corollary 6.2 that the difference of the intersection numbers for the set s(p,m, u) is equal to per}, the square root of the order of the geometry. In particular, these examples occur only in geometries whose order is a square. Until recently, and aside from the subspace examples, all known two-intersection sets in geometries over fields of odd order shared this property. 6.2.2 The exceptional sets Those sets s(p,m,u) which are two-intersection sets but do not fall into either the family of subspace sets or the family of semiprimitive sets will be called exceptional. The corresponding solutions of (6.1) will also be called exceptional. Theorem 6.1 makes possible a computer search for exceptional sets. A search can be conducted as follows. For every proper divisor k > 1 of u—1, compute k(u — k)/(u— 1). If it isa prime power, say p", check whether f — 26 divides r. If so and the quotient is s, then as long as condition (6.1b) of Theorem 6.1 holds, s(p, fs, wu) is a two-intersection set. Table 6.1 lists all exceptional solutions of (6.1) with u < 100, 000. The two-intersection sets from corresponding to the parameters in Table 6.1 with u € {11, 19, 67, 107, 163, 499} were already found by Langevin [24], although his re- sult is stated in terms of the corresponding irreducible cyclic codes c(p,m,u). His proof relies on the fact that the Gauss sums in McEliece’s identity can be evaluated if u is prime and f = (u—1)/2. Batten and Dover [4] verified by direct calcu- 90 Lueltp|s|flealkfe| 1[3fij5 ]2/5 [41 i9{slij9/4f9 {A 35/3 il 12] 5 | i7|+i a7 [7 [1/9 | 4]|9 [+H a filjil7 | 3 |2i [+ 67 [17/1] 33 | 16 | 33 | 41 i07/ 3 [1 | 53 | 25 | 53 [+1 33/5 [il is] 8 | 33/1 163/41] 1| 81 | 40 | 81 [+i 323| 8 [1|[144| 70 | 161 | +1 499| 5 | 1) 249 | 123 | 249 | +1 Table 6.1: Exceptional solutions lation that s(5,9,19) and s(7,9,37) are two-intersection sets. The author believes that s(3, 12,35), s(11, 7, 43), s(5, 18, 133) and s(3, 144, 323) are new examples of two- intersection sets. By Remark 5.20, it was enough to classify two intersection sets in geometries over fields of prime order. However, one can see many more examples from the data in Table 6.1. Indeed, for any parameters (u,p,s, f) in the table, s(p’,d,u) is a two- intersection set in PG(d — 1,p*) where td = sf and u divides (p°f — 1)/(p’ — 1). Example 6.6. As 5° = 27-19-31 - 829, then s(5°, 3,19) is an 829-set of type (4,9) in PG(2, 5°) and s(5,9, 19) is a 25,699-set of type (5074, 5199) in PG(8, 5). The fact that there are no exceptional solutions with 500 < u < 100,000 and the results of the next section provide evidence for the following. Conjecture 6.7. An orbit under a subgroup of a Singer cycle, s(p,m,u), is a two- intersection set of PG(m —1,p) if and only if it is a subspace set, a semiprimitive set, or appears in the above table of exceptional sets. Remark 6.8. All exceptional sets s(p,m,u) share the interesting property that the difference of the intersection numbers is strictly less than the order of the geometry in which they arise. It is worth noting that s(5%, 3,19) and s(7?, 3,37) were the first 91 known examples of two-intersections sets of any kind, not just those arising as orbits under Singer subgroups, in planes whose orders are odd and not square. Finally, see [40] for a short discussion of the classification in terms of sub-difference sets, as well as for a list of the sub-difference sets arising in L*/U for each of the exceptional solutions to the necessary equations. The language of difference sets is perhaps the most satisfying in which to state the classification. 6.3. Partial proof of the classification This section gives a partial proof of Conjecture 6.7, conditionally on the general- ized Riemann hypothesis (GRH). As usual, only the sets s(p,m,u) with p prime are considered; see Remark 5.20. One of the tools that will be used is a bound on class numbers of imaginary quadratic fields due to Louboutin [27]. Let K be an imaginary quadratic number field, and let ¢x(s) denote its Dedekind zeta function; see [10, p. 309]. Recall that the generalized Riemann hypothesis for K asserts that Rs = 1/2 for all zeros s of ¢x(s) with 0 < Rs < 1. Result 6.9 (Louboutin [27]). Let d be a square-free positive integer and let h(—d) denote the class number of K = Q(./—d). Assuming GRH for K, then avd 3e log d’ h(—d) > To prove the following Theorem, Louboutin’s bound is combined with work of Baumert and Mykkelveit [7] and recent work of Mbodj [30] on Gauss sums. Theorem 6.10. Conditionally on GRH, no two-intersection set in & is of the form s(p,m,u) for which the triple (p,m, u) satisfies any of the following conditions. (a) u=0 (mod 3), u 43, p=1 (mod 3) and 3log((u + 1)/4) m> oep (6.11) 92 (b) There is a prime divisor r = 3 (mod 4) of u with r > 3, ord,(p) = (r — 1)/2 (6.12) and | 3e(r=1) grog +1)/4) 6.13) (c) There are two odd prime divisors r, s > 3 of u such that ord,(p) =r — 1, ord,s(p) = (r — 1)(s — 1)/2 (6.14) and ny Ber = W(s = Vlog rsiog (w+ 1)/4) 6.15) 274/78 log p Proof. (b) Assume that s(p,m,u) is a two-intersection set. Write f = ord,(p), m = ft, 9 = (r—1)/2, and let x be a character of GF(p) of order r. By [7], the exact power of p dividing the Gauss sum G(x) is p9—”/? where h is the class number of Q(./—r). Thus, by the Davenport-Hasse theorem and Corollary 5.24, 26(u,p) < f — hf/g. Recall that k(u—k) = (u— 1)p'¥-?8)) for some divisor k of u— 1 by Theorem 6.1. Note that k(u ~ k)/(u—1) < (u+1)/4. Putting this together, one obtains BOE > pit 200e0)) > pra Now assertion (b) follows by taking logarithms and using Result 6.9. The proof of part (c) is similar. If s = 3 (mod 4) and ord,(p) = (s — 1)/2 then the bound from part (b), with s in place of r, implies the bound in (c). Otherwise, we may use Proposition 3.8 of [30] applied to a character of GF(p’) of order rs in the estimation of 0(u,p). Here g = (r — 1)(s — 1)/2. Proceed as in part (b). To prove (a), note that sp(2=4) = f(p—1)/3. By Corollary 5.24, t0(u, p) < m/3. 93 As in part (b), the result follows by Theorem 6.1. Oo Following Mbodj [80], the pair (u, p) is said to fall under the index 2 case if u is odd and ord,,(p) = y(u)/2. Note that u can have at most two distinct prime divisors in this case. The corresponding sets s(p,m,u) will be called index 2 sets. Index 2 sets are promising candidates for two-intersection sets because of the following. Proposition 6.11. The number of different hyperplane intersection numbers for a set s(p,m,u) is at most the number of orbits of x x? on Z*. In particular, an index 2 set with u prime has at most three different nonzero weights. Note that eight of the eleven exceptional two-intersection sets listed in Section 6.2.2 are index 2 sets. Thus it is desirable to verify Conjecture 6.7 for index 2 sets. Theorem 6.12. Conditionally on GRH, Conjecture 6.7 is true for all index 2 sets. Proof. Let S = s(p,m,u) and suppose that S is a two-intersection index 2 set. If S is a semiprimitive set, then there is nothing to show. Thus assume that p is not semiprimitive modulo u. First suppose 3 divides u and p=1 (mod 3). If u = 3¢s?, for a prime s > 3, then Theorem 6.10 (a) implies 37-15 — 1)s?- < POBWU TT A/) ~ log p Hence, ulog 7 u+l <] ny a a contradiction. The case u is a power of 3 is similar and once again there are no admissible values of u by Theorem 6.10(a). Next suppose that (u, 3) = 1. It is claimed that tr/u log p util == < log ——. 6.16 3selogu — ° 4 (6.16) The proof of equation (6.16) will be carried out only for the case where u has two distinct prime divisors r, s. The case where u is a prime power is similar. Write 94 u = r¢s’ where a,b > 1. As ord,(p) = (u)/2, equation (6.12) or equation (6.14) holds for the pair (u, p). If (6.12) holds, then rai gb-lig _ 1) ec 3elogr log (u+1)/4 2 — 2r4/r log p by Theorem 6.10. If (6.14) holds, then poll 3elogrs log (ut 1)/4 < 2 - 274/rs log p by Theorem 6.10. Each of these implies (6.16). Note that equation (6.16) implies u < 86,909 if p > 2. Since the table in Section 6.2 contains all exceptional sets with u < 100,000, this shows that Theorem 6.12 is true for p > 2. If p = 2, then (6.16) implies u < 125,383. A computer search shows that there are no exceptional sets with p = 2 in this range. O 95 Appendix A Notation V(n,F) V(n,q) PG(V) PG(n,q), En PG“ (n,Q), 5) O(n, q) GL(V) rL(V) PGL(V) PIL(V) the integers the rationals the complex numbers the cyclic group of order n Galois field of order q the multiplicative group of nonzero elements of the field F vector space of dimension n over the field F V(n,F) with F = GF(q) the classical projective geometry of the vector space V PG(V(n + 1,q)) the set of k-dimensional subspaces of PG(n, q) the number of points of PG(n, ¢) the group of nonsingular linear transformations of V the group of invertible semilinear transformations of V the projective general linear group of V the projective semilinear group of V 96 Bibliography [1] E. F. Assmus, J. D. Key, Designs and Their Codes, Cambridge Tracts in Mathe- matics, 103, Cambridge University Press, 1992. [2] R. D. Baker, Partitioning the planes of AG(2m, 2) into 2-designs, Discrete Math- ematics 15 (1976), 205-211. [3] R. D. Baker, Orthogonal line packings of PG(2m—1, 2), Journal of Combinatorial Theory, Series A 36 (1984), 245-248. [4] L. Batten, J.M. Dover, Some sets of type (m,n) in cubic order planes, Designs, Codes and Cryptography 16 (1999), 211-213. [5] L. D. Baumert, R. J. McEliece, Weights of irreducible cyclic codes, Information and Control 20 (1972), 158-175. [6] L. D. Baumert, W.H. Mills, R.L. Ward, Uniform cyclotomy, J. Number Theory 14 (1982), 67-82. [7] L. D. Baumert, J. Mykkelveit, Weight Distribution of Some Irreducible Cyclic Codes, D.S.N. report, vol. 11 (1973), 128-131. [8] T. Beth, D. Jungnickel, H. Lenz, Design Theory, Cambridge University Press, Cambridge (1986). [9] A. Beutelspacher, On parallelisms in finite projective spaces, Geometriae Dedicata 3 (1974), 35-40. [10] Z.I. Borevich, IR. Shafarevich, Number Theory, Academic Press, New York/San Francisco/London, 1966. 97 [11] R. H. Bruck, Construction problems of finite projective planes, Combinatorial Mathematics and its Applications, The University of North Carolina Press, 1967, 426-514. [12] R. Calderbank, W.M. Kantor, The geometry of two-weight codes, Bull. London Math. Soc. 18 (1986), 97-122. [13] R. H. F. Denniston, Packings of PG(3, q), Finite Geometric Structures and their Applications (Bressanone, 1972), Cremonese, 1973, 195-199. (14] R. H. F. Denniston, Some packings of projective spaces, Rend. Accad. Naz. Lincei 52 (1972), 36-40. [15] R. H. F. Denniston, Cyclic Packings of the projective space of order 8, Rend. Accad. Naz. Lincei 54 (1973), 373-377. [16] A. B. Evans, Orthomorphism Graphs of Groups, Lecture Notes in Mathematics 1535, Springer-Verlag, 1992. [17] R. Evans, H. Hollman, C. Krattenthaler, Q. Xiang, Gauss sums, Jacobi sums, and p-ranks of cyclic difference sets, J. Combin. Theory Ser. A 87 (1999), 74-119. [18] R. Fuji-Hara, M. Jimbo, 5. Vanstone, Some results on the line partioning problem in PG(2k, q), Utilitas Mathematica 30 (1986), 235-241. [19] J. W. P. Hirschfeld, Projective Geometries Over Finite Fields, Oxford University Press, Oxford, 1979. [20] J. W. P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Oxford Uni- versity Press, Oxford, 1985. [21] T. W. Hungerford, Algebra, Springer-Verlag, 1974. [22] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, Grad- uate Texts in Math. No. 84. Springer Verlag, Berlin/New York/Heidelberg, 1990. 98 [23] V. Jha, N. L. Johnson, Regular parallelisms from translation planes, Discrete Math. 59 (1986), 91-97. [24] P. Langevin, A new class of two weight codes, Finite fields and their applica- tions(Glasgow, 1995), 181-187, London Math. Soc. Lecture Note Ser., 233, Cam- bridge Univ. Press, Cambridge, 1996. [25] R. Lidl, H. Niederreiter, Finite Fields: Encyclopedia of Mathematics and Its Applications Vol. 20, Addison-Wesley, 1983. [26] R. Lidl, H. Niederreiter, Introduction to finite fields and their applications, Re- vision of the 1986 first edition. Cambridge University Press, Cambridge, 1994. [27] S. Louboutin: Minorations (sous l’hypothése de Riemann généralisée) des nom- bres de classes des corps quadratiques imaginaires. Application. C.R. Acad. Sci. Paris Sr. I Math. 310 (1990), no. 12, 795-800. [28] G. Lunardon, On regular parallelisms of PG(3,q), Discrete Math. 51 (1984), 229-235. [29] H.B. Mann, Addition Theorems, Wiley, New York (1965). [30] O.D. Mbodj, Quadratic Gauss Sums, Finite Fields and Their Applications 4 (1998), 347-361. [31] R. J. McEliece, Irreducible cyclic codes and Gauss sums. Combinatorics (Proc. NATO Advanced Study Inst., Breukelen, 1974), Part 1: Theory of designs, finite geometry and coding theory, pp. 179-196. Math. Centre Tracts, No. 55, Math. Centrum, Amsterdam, 1974. [32] R.L. McFarland, Sub-Difference Sets of Hadamard Difference Sets, J. Combin. Theory A 54 (1990), 112-122. [33] E. H. Moore, Tactical Memoranda LIII, American Journal of Mathematics 18 (1896), 264-303. 99 [34] H. Niederreiter, K. H. Robinson, Complete mappings of finite fields, J. Austral. Math. Soc. Ser. A. 33 (1982), 197-212. [35] T. Ostrom, Derivable Nets, Canadian Mathematical Bulletin 8 (1965), 601-13. [36] T. Pentilla and B. Williams, Regular Packings of PG3q, Euro. J. Comb. 19,713- 720. [37| A. R. Prince, Uniform parallelisms of PG(3, 3), Geometry, Combinatorial Designs and Related Structures, London Mathematical Society Lecture Note Series 245, Cambridge University Press, 1996, 193-200. [38] A. R. Prince, The Cyclic Parallelisms of PG(3,5), Euro. J. Comb. 19 (1998), 613-616. [39] A. R. Prince, Parallelisms of PG(3, 3) Invariant Under a Collineation of Order 5, Mostly Finite Geometries, Lecture Notes in Pure and Applied Mathematics, Marcel Dekker, 1997, 383-390. [40] B. Schmidt, C. White, All two-weight irreducible cyclic codes’, Finite Fields and Their Applications, to appear. [41] L. Stickelberger, Uber eine Verallgemeinerung der Kreistheilung, Math. Annalen 37 (1890), 321-367. [42] J. H. van Lint, Coding Theory, Lecture Notes in Mathematics, No. 201. Springer- Verlag, Berlin/Heidelberg/New York, 1971. [43] J. H. van Lint, R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992. [44] D. Wan, On a problem of Niederreiter and Robinson, J. Austral. Math. Soc. Ser. A. Al (1986), 336-38. [45] L.C. Washington, Introduction to Cyclotomic Fields, Graduate Texts in Math. No. 83. Springer Verlag, Berlin/New York/Heidelberg, 1997. 100 [46] K. Yamamoto, On congruences arising from relative Gauss sums, Number Theory and Combinatorics, Japan 1984, World Scientific Publ., 1985, 423-446.