Citation

## Material Information

Title:
On some new examples of Cameron-Liebler line classes
Creator:
Rodgers, Morgan J.
Place of Publication:
Denver, CO
Publisher:
Publication Date:
Language:
English

## Thesis/Dissertation Information

Degree:
Doctorate ( Doctor of philosophy)
Degree Grantor:
Degree Divisions:
Department of Mathematical and Statistical Sciences, CU Denver
Degree Disciplines:
Applied mathematics
Committee Chair:
Payne, Stanley E.
Committee Members:
Cherowitzo, William
Penttila, Timothy
White, Diana
Williford, Jason

## Record Information

Source Institution:
Holding Location:
Auraria Library
Rights Management:
Copyright Morgan J. Rodgers. Permission granted to University of Colorado Denver to digitize and display this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.

Full Text
ON SOME NEW EXAMPLES OF CAMERON-LIEBLER LINE CLASSES
by
Morgan J. Rodgers
B.S., Humboldt State University, 2005 M.S., University of Colorado Denver, 2011
A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics
2012

This thesis for the Doctor of Philosophy degree by Morgan J. Rodgers has been approved by
Stanley E. Payne, Advisor and Chair William Cherowitzo Timothy Penttila Diana White Jason Williford
Date
n

Rodgers, Morgan J. (Ph.D., Applied Mathematics)
On some new examples of Cameron-Liebler line classes Thesis directed by Professor Stanley E. Payne
ABSTRACT
Cameron-Liebler line classes are sets of lines in PG(3,q) having many nice combinatorial properties; among them, a Cameron-Liebler line class Â£ shares precisely x lines with any spread of the space for some non-negative integer x, called the parameter of the set. These objects were originally studied as generalizations of symmetric tactical decompositions of PG(3,q), as well as of subgroups of PTL(4,g) having equally many orbits on points and lines of PG(3, q). They have connections to many other combinatorial objects, including blocking sets in PG(2,g), certain error-correcting codes, and strongly regular graphs.
We construct many new examples of Cameron-Liebler line classes, each stabilized by a cyclic group of order q2 + q + 1 having a semi-regular action on the lines. In particular, new examples are constructed in PG(3,q) having parameter |(g2 â€” 1) for all values of q = 5 or 9 mod 12 with q < 200; with parameter |(q + l)2 (found in collaboration with Jan de Beule, Klaus Metsch, and Jeroen Schillewaert) for all values of q = 2 mod 3 with 2 < q < 128; with parameter 336 in PG(3, 27); and with parameter 495 in PG(3,32). The new examples with parameter |(q2 â€” 1) when q = 9 mod 12 are of particular interest. These induce a symmetric tactical decomposition of PG(3, q) having four classes on points and lines, one of the line classes being the set of lines in a common plane. This decomposition can be used to construct examples of two-intersection sets in the affine plane AG(2, q). Since the only previously known examples of two-intersection sets in affine planes of odd order are in planes of order 9, our example in AG(2,81) is new.
m

The form and content of this abstract are approved. I recommend its publication.
Approved: Stanley E. Payne
IV

ACKNOWLEDGMENTS
This thesis would not have been possible without the help of many people. I owe part of my success as a graduate student to every member of my committee, and I would like to thank them all for their time and support. In particular, I would like to thank my advisor Stan Payne, whose dedication to mathematics has truly been inspiring, and Tim Penttila, who generously suggested this problem to work on. Timâ€™s help in learning to program with Magma was truly indispensible in conducting this research, and he also brought a few key articles to my attention that were instrumental in filling in some details of this work. Bill Cherowitzo has also offered constant support and assistance; most notably, he convinced the department to give me an office to work in when I was a first year student with no other form of departmental support. Much of the computational work involved in this thesis was done on the University of Wyoming cluster, and I thank Jason Williford for going out of his way to set me up with this access. My survival in academia would have been much more difficult without the help and advice of these people and many others, especially Diana White, Mike Ferrara, and Oscar Vega.
I also would like to thank the Bateman family for their financial support of the mathematics department; I have been fortunate to receive three semesters of support from the Lynn Bateman Memorial Fellowship, and the completion of this research would have been much more difficult without the relief from teaching duties this provided. I would like to extend thanks to Jan de Beule and the Universiteit Gent as well for supporting me as a visiting researcher. Part of the work of this thesis was conducted during that trip, in collaboration with Jan, Klaus Metsch, and Jeroen Schillewaert.
Most importantly, I thank my loving wife who has never lost faith in my ability to succeed, even when I questioned it myself. She helped more than she knows; I definitely would not have finished this thesis without her support.
v

Tables.................................................................... viii
Chapter
1. Introduction............................................................... 1
1.1 Overview............................................................. 1
1.2 Finite fields........................................................ 2
1.3 The projective geometry PG(n, q) ................................... 4
1.4 Collineations and dualities ......................................... 5
1.5 Combinatorics of PG(n, q) ........................................... 7
1.6 Bilinear and quadratic forms......................................... 9
1.7 Orthogonality and totally isotropic subspaces....................... 10
1.8 Orthogonal polar spaces in PG(n, q)................................. 11
1-9 Q+(5,q) and the Klein correspondence................................ 14
2. Cameron-Liebler line classes.............................................. 18
2.1 Definitions and history ............................................ 18
2.2 Tight sets of Q+ (5, q)............................................. 19
2.3 Two-intersection sets, two-weight codes, and strongly regular graphs 21
2.4 Trivial examples.................................................... 23
2.5 Non-existence results .............................................. 24
2.6 Known examples...................................................... 26
2.6.1 Bruen and Drudge examples................................. 26
2.6.2 Penttila and Govaerts example in PG(3,4).................. 27
3. Methodology............................................................... 30
3.1 An eigenvector method for tight sets................................ 30
3.2 Tactical Decompositions............................................. 31
3.3 A model of Q+ (5, q)................................................ 33
3.4 The general method.................................................. 34
vi

4. New examples......................................................... 36
4.1 New examples with parameter |(g2 â€” 1)................... 37
4.1.1 The construction......................................... 37
4.1.2 Some details of these examples........................... 41
4.2 New examples with parameter |(g + l)2................. 43
4.3 Some other new examples....................................... 44
5. Planar two-intersection sets ........................................ 46
5.1 Projective examples........................................... 46
5.2 Affine examples............................................... 48
5.3 Constructions from Cameron-Liebler line classes............. 50
5.3.1 A two-intersection set in AG(2, 9)...................... 50
5.3.2 A new two-intersection set in AG(2, 81) ................ 52
5.3.3 A family of examples in AG(2, 32e)? 53
Appendix
A. Algorithms.......................................................... 56
A. l CLaut Matrix.................................................. 56
B. Programs ........................................................... 58
B. l CLshell.mgm................................................... 58
B.2 CLpreamble.mgm................................................ 60
B.3 CLaut.mgm .................................................... 62
B.4 CLbcirc.mgm................................................... 65
B.5 CLvspace.mgm.................................................. 68
B.6 CLpg3q.mgm.................................................... 70
B.7 CLint.mgm..................................................... 71
B.8 CL81int.mgm .................................................. 72
B.9 MNset.mgm..................................................... 73
References.............................................................. 76
vii

TABLES
Table
4.1 Parameters and automorphism groups of the new examples of Cameron-
Liebler line classes constructed....................................... 36
4.2 Intersection numbers of line classes with parameter |(g2 â€” 1) with the
planes of PG(3, q)..................................................... 42
4.3 Intersection numbers of line classes with parameter + l)2 with the
planes ofPG(3,q)....................................................... 44
4.4 Intersection numbers of some other new line classes.................. 45
5.1 Lines per point for the symmetric tactical decomposition induced on
PG(3,9) by a Cameron-Liebler line class of parameter AO............. 51
5.2 Points per line for the symmetric tactical decomposition induced on PG(3, 9)
by a Cameron-Liebler line class of parameter AO..................... 51
5.3 Lines per point for the symmetric tactical decomposition induced on
PG(3,81) by a Cameron-Liebler line class of parameter 3280.......... 53
5.4 Points per line for the symmetric tactical decomposition induced on PG(3, 81)
by a Cameron-Liebler line class of parameter 3280................... 53
viii

1. Introduction
1.1 Overview
The focus of this dissertation is to construct new examples of Cameron-Liebler line classes admitting a certain cyclic automorphism group. These line classes have many different characterizations. Most notably, a Cameron-Liebler line class C, has the property that, for some integer x called the parameter, C, shares precisely x lines with every spread of the space. Cameron-Liebler line classes are also of interest to other areas of mathematics including group theory and coding theory. These sets of lines were originally studied in relation to a group theory problem regarding collineation groups of PG(3,q) having the same number of orbits on points and on lines. They also serve as generalizations of the notion of a symmetric tactical decomposition of PG(3,q); i.e., a tactical decomposition having the same number of point classes and line classes. Through the Klein correspondence, a Cameron-Liebler line class is equivalent to a set of points of the hyperbolic quadric Q+(5, q) called a tight set. Tight sets of this quadric often determine two-intersection sets of the underlying projective space PG(5,g), that is, sets of points having two intersection numbers with respect to hyperplanes. Two-intersection sets can then be used to construct error correcting codes with codewords having precisely two nonzero weights which, in turn, give rise to examples of strongly regular graphs.
After reviewing the geometry of PG(3, q) and Q+(5, q), as well as their relationship through the Klein correspondence, we survey the known results on Cameron-Liebler line classes, including the known examples as well as some non-existence results. We show the equivalence of these objects with tight sets of Q+(5, q) and give results on when these sets determine two-intersection sets of the underlying PG(5, q). We also look at the construction of two-weight codes and strongly regular graphs from these two-intersection sets. Once we have developed this background material, we develop tools which are used to construct new examples. The main tools are
1

an eigenvector method for finding tight sets and results on tactical decompositions which facilitate this method. Since we are primarily working from the point of view of Q+ifi,q), an algebraic model for this space is introduced. This allows us to give a concise notation for a cyclic group of order q2 + q + 1 acting semi-regularly on the space, which is contained in the stabilizer of each new example constructed.
We use the tools we develop to construct several new examples of Cameron-Liebler line classes in PG(3,q), including many having parameters \{q2 â€” 1) and |(g+l)2. We also describe other examples in PG(3, 27) and PG(3, 32). For all of these new examples, we detail structural information such as automorphism groups and intersection numbers with planes of PG(3,q), as well as the related two-intersection sets of PG(5,g), two-weight codes, and strongly regular graphs. Furthermore, when q = 9 or 81, the new examples with parameter |(g2 â€” 1) are line partitions of a symmetric tactical decomposition of PG(3, q) having four parts on points and on lines; we give a construction from this decomposition of two-intersection sets in AG(2,g). Few examples of two-intersection sets of odd order affine planes are known; in fact, the only previously known examples are in planes of order 9. Thus, our example in AG(2, 81) is new.
1.2 Finite fields
A finite held always has order q = pe, where p is a prime. This held, which is unique up to isomorphism, will be denoted Fg and has characteristic p; i.e., Ym=i x = 0 for every xeF, (and p is the smallest integer for which this is true). The multiplicative group F* of nonzero elements of Fg is a cyclic group of order q â€” 1; an element a G F* having order g â€” 1 is called a primitive element, and (a) = F* for such an element.
Let K = Fq, where q = ph. A subset F of K which is also a held under the
same operations is called a subfield of K; we write F < K. K contains a unique
subheld isomorphic to Fpe for each e dividing h, consisting of {a E K : apÂ£ = a}. The
2

intersection of all subfields of K is called the prime subfield of K and is isomorphic to Fp. We can construct a larger held E = from K by considering an irreducible polynomial f(x) in K[x\ of degree d; in this case
E = K[x\/(f(x)) = {a0 + a\x + ... + ad-ixd~l\ cp e K, f(x) = 0}
is a hnite held of order qd containing K as a subheld. We say that E is an extension field of K.
A map a : Fg â€”>â€¢ Fg is called an automorphism of Fg if a is a permutation of the elements such that (x + y)a = xa + ya, and (xy)a = {xa){ya) for all x, y in Fg. We write Aut(Fg) for the group of automorphisms of Fg. If q = pe, p prime, then Aut(Fg) is cyclic, isomorphic to Ze, and is generated by the Frobenius automorphism (p : x i y .
Let q = pe, F = Fg, and K = Fg/> with F < K; then Au.t(K/F), the group of automorphisms of K hxing every element of F, has order h and is generated by (f)e : x i y xpÂ£ = xq. We dehne the relatiue trace map from K to F, TK/F : K iâ€”>â€¢ F, by
Tk/f(o) = aa = a + aq + af + ... + aq(h X).
aÂ£Aut(K / F)
This map has the following properties:
1. TK/F(a + b) = Tk/f(o) + TK/F(b) for all a, b E K.
2. TK/F(ca) = cTK/F(a) for all c E F, a E K.
3. Tk/f(o) = ha for all a E F.
4. Tk/f{(F) = T^/j?(a) for all a E K and for all a E Aut(K/F).
Notice that the hrst two items imply that, if K is viewed as a vector space over F, then TK/F is a linear transformation from K to F. We actually have more; the map TK/F maps K onto F, and in fact, every linear map from K into F takes the form Lb(a) = TK/F(ba) for some b E K.
3

1.3 The projective geometry PG(n,g)
Much of this material is treated thoroughly in [25] or in [18]. There are also
examples of projective planes which are not of the form PG(2, q); for details on these examples, see [19].
Definition 1.1 Let F = Fq be a finite field of order q and V be a vector space of dimension n+ 1 over F. We define the geometry PG(n,q) as follows:
â€¢ The one-dimensional vector subspaces of V are the points of PG(n, q).
â€¢ The (d+ l)-dimensional vector subspaces ofV are the d-dimensional subspaces ofPG(n,q).
â€¢ Incidence is defined in terms of containment of the corresponding vector subspaces.
The word â€œdimensionâ€ is used in two ways with a different meaning; when it is not clear which we mean from context, we will specify projective dimension when we are talking about the dimension in PG(n,q), or vector space dimension when we are talking about a subspace of V. This definition of a projective space allows us to associate vectors in V with points of PG(n, 5); namely, a nonzero vector v e V represents a point of PG(n, q), with nonzero vectors v, w representing the same point if and only if v = cw for some c G F*.
We will call a subspace of PG(n, 5) having dimension n â€” la hyperplane; the set of points on a hyperplane can be described as those satisfying a homogeneous linear equation. We write the coefficients the equation describing a hyperplane H as h = [xo, â€¢ â€¢ â€¢ , xfi, with the convention that a point u is in H if and only if uhT = 0. We will speak of a set of points or of hyperplanes as being linearly independent if the corresponding vectors are linearly independent in the vector space.
It is frequently useful to describe a subspace U of PG(n, q) as either the intersection or the span of other subspaces. Given two subspaces U\ and U2 of PG(n, q), the
4

intersection U\ fl U2 is again a subspace of PG(n, q). We define the span of U\ and U2 to be the smallest subspace of PG(n, 5) containing both U\ and U2; we denote this by (U\, U2). In general, the projective dimension of (U\, U2) is given by
dim {Ui, U2) = dim LA + dim U2 â€” dim (LA fl U2).
The span of two distinct points, for example, is the line containing both of them. Given a subspace U of dimension d and a hyperplane id, we have that U fl H is either equal to U, or has dimension d â€” 1. Thus we can describe a d-dimensional subspace U of PG(n, q) as either the span of d + 1 linearly independent points, or as the intersection of n â€” d linearly independent hyperplanes. If hi,..., \vn-d are the vectors containing the coefficients of the equations for these hyperplanes, then we can associate U with the left null space of the matrix
hT hT
nl â€¢ â€¢ â€¢ nn-d
1.4 Collineations and dualities
A bijection on the points of PG(n,g) which preserves the lines is called a collineation; that is, a map 6 : PG(n, 5) â€”> PG(n,q) such that for all lines Â£ of PG(n,q), the image 8(Â£) is also a line of PG(n, 5). This necessarily implies that any d-dimensional subspace of PG(n, q) gets mapped by 6 to another d-dimensional subspace. Since we view the subspaces of PG(n, 5) as corresponding to subspaces of an (n +1)-dimensional vector space V over Fg, we can describe a collineation of PG(n, q) in terms of its action on V. In particular, any matrix A E GL(n + 1, q) can be used to define a collineation : x 1â€”> xA of PG(n, q). Collineations of this type are called
homographies. Note that, for any A G F*, the matrices A and A A define the same map on PG(n, 5); we say these two maps are projectively equivalent. The group
PGL(n+ 1, q) = GL(n+ 1, q)/Z(GL(n + l,q))
5

is called the projective linear group, and acts faithfully on PG(n, q). It is worth noting that, for a hyperplane H represented by h and a matrix A E PGL(n + 1, q), we have that x G If if and only if (xA)(A_1hT) = 0, so the hyperplane H gets mapped by La to a new hyperplane defined by A-1 hT. Automorphisms of Fg also give examples of collineations of PG(n, q). Given a E Aut(Fg), the map on PG(n, q) induced by
a : V ->â–  V : (x0, â–  â–  â–  , xn) ^ (x%,..., xjj)
is called an automorphic collineation.
The Fundamental Theorem of Projective Geometry tells us that any collineation of PG(n,g) can be obtained by composing an automorphic collineation with a ho-mography. Such a map is of the form
La o a : x 1â€”> La{?G) = xCTA,
where a E Aut(Fg) and A E PGL(n+ 1 ,q), and is called a projective semilinear map. The group of these maps is denoted
PTL(n +1, q) = PGL(n + 1, q) x Aut(Fg).
Associated with a projective geometry S is the so-called dual geometry S*-, this geometryâ€™s points and hyperplanes are, respectively, the hyperplanes and points of
S. A projective geometry of the form PG(n, 5) is isomorphic to its dual geometry, and we call an isomorphism from the points of PG(n, 5) onto the hyperplanes a reciprocity. One important example is the map sending a point x to the hyperplane determined by xT. By our earlier comments about the Fundamental Theorem of Projective Geometry, any reciprocity can be written in the form x â€”> (x.aA)T, where a E Aut(Fg) and A E PGL(n + 1, q). If we have a reciprocity 6 that is an involution, that is, if 92 = 1, then we call 6 a polarity.
1.5 Combinatorics of PG(n, q)
6

Theorem 1.2 [18] In PG (n,q), there are
{q"q-i)1) Points, lines, (
d-dimensional subspaces.
(gn+1-1)(g"-1) iines an(i
nGb'-i)
Given d < s, the number of s dimensional subspaces containing a fixed d-dimensional subspace is given by
nâ€”d
n tf-1)
i=sâ€”d-\-1
i= 1
It is useful to note that, since PG(u,g) is self dual, the number of d-dimensional subspaces is the same as the number of (n â€” d)-dimensional subspaces. In particular, there are the same number of hyperplanes as there are points. Also, the number of hyperplanes through a fixed point is the same as the number of points in a fixed hyperplane.
We now give some consideration to the orders of various groups associated with
PGM [16].
Theorem 1.3 If q = pe, then
ra+l
GL(n+l,q) has order q\nG+l) â€” 1);
k=1
ra+l
PGL(n+l,q) has order qhnG+l) â€” 1), and
k=2
ra+l
PTL(n+ 1 ,q) has order eq^n(-n+ ^ â€” !)â€¢
k=2
The projective space we will be primarily interested in will be PG(3, q). Specializing the above results to this specific case, we see that PG(3, q) contains q3 + q2 + q-f 1 points as well as planes, and (q2 + q + 1 )(q2 + 1) lines. Through each point there are q2 + q + 1 lines and cj2 + q + 1 planes; also, given a line, there are q + 1 planes containing that line.
7

The groups acting on PG(3, q) are PGL(4, q) and PTL(4, q); if q = pe, the orders of these are
PGL{A,q) has order Q6(q2 â€” l)(g3 â€” l)(g4 â€” 1) and PTL(A,q) has order eq6(q2 â€” l)(g3 â€” f){qA â€” f) .
A set 7Z of q + f mutually skew lines in PG(3, q) is called a regulus provided
1. through every point of every line of 7Z there is a transversal of the lines of 7Z (that is, a line meeting each of the lines of 1Z); and,
2. through every point of every transversal there is a line of 1Z.
It is clear that the set of transversals of 7Z is also a regulus which we call 7Â£0pp> the opposite regulus of 1Z. Any three skew lines in PG(3,q) determine a unique regulus. A spread of PG(3, q) is a set of cj2 + 1 lines of the space that partitions the points. A spread S is called regular if, given any three skew lines in S, the regulus determined by those three lines is also contained in S. Spreads can be defined in higher dimensional spaces as well, and are of considerable interest, as they can be used to construct examples of projective planes. Their classification is an important problem in finite geometry that is beyond the scope of this thesis.
A k-arc K of PG(2, q) (or any projective plane of order q) is a set of k points such that no three are collinear. Thus any line Â£ of PG(2, q) meets K in 0, 1, or 2 points; we call these lines external, tangent, or secant to K respectively. A k-arc must have k < q + 2. A k-arc K which is not contained in any (k + l)-arc is called maximal. A (q + l)-arc is called an oval, and if q is odd, any (q + l)-arc is maximal. However, if q is even, every tangent line to an oval K passes through a common point N which we call the nucleus of 1C. In this situation, K U {N} is a (q + 2)-arc, which we call a hyperoval. Given a plane tt embedded in PG(3,q) containing an oval or hyperoval O, and a point p not in tt, we define a cone over O to be the set of points on the
8

lines joining p to points of O. The lines are called the generators of the cone, and p is called the vertex of the cone.
Let V be a vector space of dimension n + 1 over F = Â¥q A bilinear form on V is a function B : V x V F that is linear in each argument; that is,
B(au + v, w) = aB(u, w) + B(v, w) and B(u, av + w) = aB(u, v) + B(u, w)
for all u, v, w G V and all a E F.
A bilinear form B is said to be symmetric if B(u, v) = B(v, u) for all u, v e V, and alternating if B(u,u) = 0 for all u e V. We are strictly interested in reflexive bilinear forms, that is, those for which B(u,v) = 0 implies B(v, u) = 0. Every reflexive bilinear form is either symmetric or alternating.
A quadratic form on a vector space V is a map Q : V -E F defined by a homogeneous degree 2 polynomial in the coordinates of V relative to some basis. Equivalently, we call Q : V F a quadratic form if
Q(au) = a2Q( u) for all a E F and uef and B : (u, v) i y Q(u + v) â€” Q(u) â€” Q(v) gives a bilinear form on V.
It is clear that B is symmetric if q is odd and alternating if q is even. This associated bilinear form, B, is called the polar form of Q. A vector space equipped with a quadratic form is called an orthogonal space.
Given a bilinear form B and an ordered basis B = {v0,..., vra} for V, we put bij = B(vj,Vj). The Gram matrix relative to B is then defined by B = [bifl. This matrix has the property that, if [u]b and [v]g are coordinate vectors of u and v relative to B, then B(u,v) = [u]sB[v]g. Any two Gram matrices of a bilinear form B have the same rank, which we define to be the rank of B. If Q is a quadratic form
9

on V, we define the upper triangular matrix
A = (a,ij), where
B(vi, vj), i < j; < Q(vi), i = j;
0 * > j.
V
We then have that Q(u) = [u]ed[u]g, and the Gram matrix for the polar form of Q with respect to B is then B = A + AT.
1.7 Orthogonality and totally isotropic subspaces
Let B be a reflexive bilinear form on PG(n,g). We define an orthogonality relationship on the points of PG(n, 5) by u _L v if B(u,v) = 0. If S C V, we define S â€œperpâ€ to be
S1 = {v G P| v 1 s Vs e S}.
A point v of PG(n, q) is called singular with respect to a bilinear form B if v1 = V; it is called singular with respect to a quadratic form Q if it is singular with respect to the associated bilinear form and Q(v) = 0. We say B or Q is degenerate if there is a singular point, and nondegenerate otherwise.
We place a special significance on points v for which B(v,v) = 0 or Q(v) = 0. Such a point v is called isotropic with respect to to bilinear form B or the quadratic form Q, respectively. We call a subspace W of V isotropic if it contains an isotropic point, anisotropic otherwise, and totally isotropic if B(u, v) = 0 for all u,v G W (for a bilinear form), or if Q(v) = 0 for all v e W (for a quadratic form). If a subspace is totally isotropic with respect to a quadratic form Q, then it is also totally isotropic with respect to the associated bilinear form, though the converse only holds if q is odd. The set of isotropic points in PG(n, q) with respect to a nondegenerate quadratic form is called a quadric, and has the property that any line of PG(n, 5) containing more than two points of a quadric must be completely contained in the quadric.
If B is nondegenerate form, the orthogonality relation can be used to define a
polarity a : U 1â€”> U1- of PG(n, 5). In this case, if U and W are subspaces of V with
10

U < W, then W1- < U-1; furthermore, for any subspace U of V, dim 17 + dimf/-1 = dimVh A point x is said to be isotropic with respect to the polarity if x C x-1, and a subspace U is said to be totally isotropic with respect to the polarity if U < UA This is in agreement with the notions of being isotropic or totally isotropic with respect to the bilinear form. When q is odd, the polar form of a nondegenerate quadratic form is necessarily nondegenerate. Thus in this case the notions of being (totally) isotropic with respect to the quadratic form, the bilinear form, and the associated polarity all agree.
The situation is more complicated when q is even, since it is possible for the polar form of Q to be degenerate even when Q is nondegenerate. In this case, we do not have a polarity associated with the quadratic form. Even if the polar form B of Q is nondegenerate, we have B(u,u) = 0 for every u e PG(n,q), so every point of PG(n,g) is incident with its image under the induced polarity (such a polarity is called a null polarity). Thus the set of points which are isotropic with respect to this polarity does not agree with the set of points which are isotropic with respect to the quadratic form.
1.8 Orthogonal polar spaces in PG(n,q)
Definition 1.4 A polar space of rank r is an incidence geometry consisting of a set of points, lines, projective planes, ..., (r â€” l)-dimensional projective spaces called subspaces such that
1. Any two subspaces intersect in a subspace.
2. IfU is a subspace of dimension r â€” 1 and p is a point not in U, there is a unique subspace W containing p with U fl W having dimension r â€” 2; it consists of all points of U which are joined to p by some line.
3. There are two disjoint subspaces of dimension r â€” 1.
11

The (r â€” l)-dimensional subspaces are called maximals of the polar space.
The finite classical polar spaces are the examples naturally embedded in a projective space PG(n,g); they are defined by a nondegenerate quadratic or sesquilinear form on the space. A result of Tits [33] proved that any polar space with rank at least 3 is classical. Rank 2 polar spaces are a special case. They are called generalized quadrangles, and there are nonclassical examples of these; see [26] for a detailed treatment.
Let F = Fg, and k be a (n + 1)-dimensional vector space over F. Take Q to be a nondegenerate quadratic form on V with polar form B. The geometry consisting of the totally isotropic subspaces of PG(n,g) with respect to Q is an example of a classical polar space; we call an example arising in this way an orthogonal polar space.
Note: We have now introduced three very closely related terms, an orthogonal space, a quadric, and an orthogonal polar space.
â€¢ The vector space V along with a nondegenerate quadratic form is an orthogonal space.
â€¢ The set of isotropic points of PG(n,g) with respect to the quadratic form is called a quadric.
â€¢ The geometry of totally isotropic subspaces with respect to the quadratic form is called an orthogonal polar space, in this context the polar space can either be considered as embedded in PG(n, q) or as a geometry in its own right.
The most general collineation of PG(n,g) preserving a quadric is called a semisimilarity, this is a map a such that, for some a G F* and some r G Aut(Fg),
Q((?(x)) = a(Q(x))T-
We call a a similarity if r = 1, and we call a an isometry if a = 1 and r = 1. The following important theorem is known as Wittâ€™s Extension Theorem:
12

Theorem 1.5 IfU,W< V, and a : U â€”>â€¢ W an isometry, then there is an isometry r : V â€”> V such that r\u = o.
Corollary 1.6 Any two maximals ofV have the same dimension.
The vector space dimension of a maximal is called the Witt index of the polar space. The Witt index of a nondegenerate form is less than or equal to \ dim V, since a totally isotropic subspace W is contained in W^.
We define two distinct points u, v of the quadric to be a hyperbolic pair if B(u, v) = 1. We then call (u, v) a hyperbolic line. Note that this is a line of PG(n, q) containing precisely two points of the quadric.
Theorem 1.7 Any nondegenerate orthogonal space of Witt index r over Fg is isometric to one of the following:
1. A hyperbolic quadric Q+{2r â€” 1 ,q) is the orthogonal direct sum of r hyperbolic lines.
2. A parabolic quadric Q(2r, q) is the orthogonal direct sum of r hyperbolic lines and a one-dimensional anisotropic space. These fall into two isometry classes and one similarity class when q is odd, and one isometry class when q is even.
3. An elliptic quadric Q~(2r + 1 ,q) is the orthogonal direct sum of r hyperbolic lines and a two-dimensional anisotropic space.
The group of isometries of Q+(2râ€”1, q), Q(2r, q), or Q_(2r+1, q) is denoted 0+(2r, q), 0(2r + l,q), or 0~{2r + 2,q), respectively. For the projective versions of these groups, we prefix this with P, PG, or PT depending on whether we want the group of isometries, similarities, or semi-similarities, respectively.
If we have a set of points O in a polar space such that every maximal of the polar space meets O in a unique point, then we call O an ovoid of the polar space. The
13

classification of ovoids in classical polar spaces is an important open problem in finite geometry; we are primarily interested in these objects because of how they interact with other objects in the space.
1.9 Q+(5,q) and the Klein correspondence
The 5-dimensional hyperbolic orthogonal space Q+(5, q) plays an important role, as this geometry is closely related to PG(3,q). This quadric is made up of the orthogonal direct sum of three hyperbolic lines, and the standard associated quadratic form is given by
Q â–  {%0, Xi,X2, Xs, X4, X5) 1â€”> X0X1 + X2X3 + X4X5, which is described by the matrix
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 0
The Gram matrix for the polar form B with respect to the standard basis is then
B = A + At.
Another way to think of the structure of this polar space is given by taking one point from each of the three hyperbolic pairs. Since the hyperbolic lines they determine are pairwise orthogonal, these three points are also pairwise orthogonal and so span a totally isotropic plane tti, necessarily a maximal of the polar space. The three remaining points from the hyperbolic pairs then span a totally isotropic plane 7r2 which is disjoint from tti-
The geometries PG(3,q) and Q+(5,q) are closely related through a mapping
known as the Klein correspondence. This refers to a bijection from the lines of PG(3, q)
14

to the points of Q+(5,q) such that two lines of PG(3,q) intersect if and only if their images are collinear in Q+(5,q). To define the bijection, we will first establish a way to describe lines of PG(3,q) using Plucker coordinates. Let x = (To, an, x2, x3) and y = (yo, Vi, y2, 2/3) be distinct points on a line Â£ of PG(3,q). Dehne G(Â£) = (P01 > P23, P02, P31, P03, P12), where
Pa
Xf ^ Xj
for 0 < i < j < 3.
Vi Vj
If we consider G(Â£) E PG(5,g), any choice of two points on Â£ determine the same point. Furthermore, it can be seen that P01P23 +P02P31 +P03P12 = 0. Thus, G takes lines of PG(3, q) to points of Q+(5, q).
Now, given a point a = (a0, Â«i, a2) a3, a^, a5) G Q+(5, q), so a0Â«i +^2^3 + Â«4Â«5 = 0, the matrix
0 a\ a3 0>5
â€”a\ 0 a4 â€”a2
-a3 â€”a 4 0 a0
â€” 0-5 a 2 â€”ao 0
has rank two. Therefore the map
H (a) = row
0 a\ a.3 (15
â€”a\ 0 a4 â€”a 2
â€”CL3 â€”Op 0 ao
â€” 0-5 a2 â€”ao 0
takes the point a to a line of PG(3, q). It can be verified that H(G(Â£)) = l. Thus G and H give a bijection between the lines of PG(3, q) and the points of Q+(5, q). We refer to this bijection as the Klein correspondence.
Here we detail some important properties of the Klein correspondence.
Theorem 1.8 Two lines Â£ and Â£! of PG(3,q) are concurrent if and only if their corresponding points L and L' are collinear in Q+(5,g).
15

Corollary 1.9 The set of lines in a spread of PG(3, q) correspond to an ovoid of
Q+(5,g).
Corollary 1.10 Let Â£ and Â£' be two concurrent lines in PG(3, q) with corresponding points L and L' in Q+(5, q). Then the lines of the fiat pencil of lines in PG(3, q) determined by Â£ and Â£' correspond to the line of Q+(5, q) through L and L'. Conversely, each line of Q+(5, q) corresponds to a set of lines in PG(3, q) lying in a fiat pencil.
Corollary 1.11 The set of points in a totally isotropic plane of Q+ (5, q) corresponds to a set of cj2 + q + 1 lines in PG(3, q), any two of which are concurrent. Thus, they correspond to either the set of lines through a common point p, denoted star(p), or the set of lines in a common plane ir, denoted lineijr).
We call a totally isotropic plane of Q+(5, q) a Latin plane if it corresponds to star(p) for some point p E PG(3, q), and a Greek plane if it corresponds to line(7r) for some plane tt of PG(3, q).
Corollary 1.12 Any two distinct planes of the same type in Q+(5,q) intersect in a 0-dimensional subspace (a single point). Any two planes of different types are either disjoint, or meet in a line of Q+(5,q). Thus two planes are of the same type if and only if their intersection has even dimension.
These correspondences allow us to count the following:
Corollary 1.13 Q+(5,q) contains
1. (q2 + 1 )(q2 + q + 1) points;
2. (q3 + q2 + q + 1 )(q2 + q + 1) lines;
3. 2(q3 + q2 + q + 1) planes;
4â–  q(q + l)2 points collinear to a given point;
16

5. (q + l)2 lines containing a given point;
6. 2(q + 1) planes containing a given point;
7. 2 planes containing a given line.
The Klein correspondence also gives us a connection between the groups PTL(4, q) acting on PG(3,q) and PTO+(6,q) acting on Q+(5,q). Specihcally, any element of PTL(4:,q) induces an action on the points of Q+(5,q) preserving collinearity, and so PTO+(6,q) has a subgroup isomorphic to PTL(4:,q). Any map on Q+(5,q) arising in this fashion maps Greek planes to Greek planes and Latin planes to Latin planes. Any correlation of PG(3, q) sends lines to lines, and so also induces an action on the points of Q+(5,q) preserving collinearity. A map arising in this fashion interchanges the Greek and Latin planes. These are known to be the only automorphisms of
Q+(5,g).
Theorem 1.14 The structure of the projective similarity and semi-similarity groups ofQ+(5,q) are as follows:
â€¢ PGO+(6,q) ~ PGL(4,q) x Z2.
â€¢ PTO+(6,q) ~ PTL(4,q) x Z2.
Using this connection between the lines of PG(3,q) and the points of Q+(5,q) can be helpful, especially when dealing with combinatorics of sets of lines in PG(3, q). In addition to having many theoretical results to apply, it is more computationally convenient to deal with sets of points. For this reason, much of our work in this thesis is done in the context of Q+(5, q).
17

2. Cameron-Liebler line classes
In this chapter, we will survey many of the known results on Cameron-Liebler line classes. This includes non-existence results, known constructions, and a discussion of the images of these line sets in Q+(5,q) under the Klein correspondence.
2.1 Definitions and history
Here we detail sets of lines in PG(3,q) having some special combinatorial properties. These sets of lines were originally studied by Cameron and Liebler [8], who called them â€œspecialâ€ line classes, in connection with the study of collineation groups of PG(3,q) having the same number of orbits on points and lines. Such a group induces a symmetric tactical decomposition of the incidence structure of points and lines in PG(3,q), and they showed that a line class from such a decomposition has nice intersection properties with respect to reguli and spreads of the space. They abstracted the concept of sets of lines with these properties, hoping it would lead to the classification of symmetric tactical decompositions and collineation groups of PG(3,q) with this orbit structure. However, this problem proved interesting in a more general setting than originally envisioned.
Definition 2.1 Let A be the point-line incidence matrix ofPG(3,q) with respect to some ordering of the points and lines, and let Â£ be a set of lines in PG(3,q) with characteristic vector x = Xc- We will write (x)e for the entry of x corresponding to the line l. The following statements are all equivalent; if they hold, Â£ is called a Cameron-Liebler line class [8], [27].
1. xc G row(A).
2. xc Â£ {null{AT))-L
3. \R fl Â£\ = \Ropp H Â£| for every regulus 7Z and its opposite Ropp-
4â€¢ There exists x G TA such that \Â£ fl S\ = x for every spread S.
18

5. There exists x G Z+ such that \C fl S\ = x for every regular spread S.
6. There exists x G Z+ such that, for every incident point-plane pair (p, tt),
|star{p) fl C\ + \ line(7r) fl C\ = x + (q + l)\pencil(p,7r) fl C\.
7. There exists x G Z+ such that, for every line l in PG(3, q),
| {lines m G C meeting | = + 1) + (q2 + l)(x)r-
5. T/iere exists x G Z+ skc/i that, for every pair l, m of skew lines in PG(3, q), \{n G Â£ : n is a transversal to l, m}\ = x + q[(x)t + (x)m\ â–
The value x must satisfy 0 < x < q2 + 1, and will necessarily be the same in each instance; we call x the parameter of the line class. If Â£ is a Cameron-Liebler line class with parameter x, then \C\ = x(q2 + q+ 1). The complement Â£ of a Cameron-Liebler line class C, with parameter x is also a Cameron-Liebler line class having parameter cj2 + 1 â€” x, and the union of two disjoint Cameron-Liebler line classes with parameters x\ and X2 is a Cameron-Liebler line class with parameter x\ + X2â–  A Cameron-Liebler line class is said to be irreducible if it does not properly contain any other line class as a subset.
2.2 Tight sets of Q+(5,q)
To investigate the existence of Cameron-Liebler line classes, it is frequently useful to translate their definition to the setting of Q+(5, q) using the Klein correspondence. In this context, part 7 of Definition 2.1 has an especially interesting interpretation; C, is a Cameron-Liebler line class if and only if its image M in Q+(5, q) has the following property:
There exists x G Z+ such that, for every point p in Q+(5, q),
Ip^nMl = x(q+ 1) + q2(x)p, where x = Xm is the characteristic vector of M.
19

Definition 2.2 Let S be a polar space of rank r > 3 over Fg. Then a set T of points in S is an x-tight set if for all points p E S
n T |
+ qr 1 if p eT
ifp i r
Adapting this definition for the rank 3 polar space Q+(5, q), we see that a Cameron-Liebler line class with parameter x is equivalent to an x-tight set of Q+(5, q).
Point sets in polar spaces having precisely two intersection numbers with respect to perps of points are called intriguing by Bamberg, Kelly, Law and Penttila [2]. There are two types of intriguing sets in finite polar spaces, and they can be characterized in terms of their intersection numbers. If X is an intriguing set of a polar space having intersection numbers h\ for perps of points inside X and h2 for perps of points outside X, then X is a tight set if h\ > h2. A tight set of points in a finite polar space can also be defined as a set of points T such that each point of the space is, on average, collinear with as many points in T as possible. These sets were originally studied in generalized quadrangles by Payne [24] and their definition was later extended to more general polar spaces by Drudge [12], An intriguing set with h\ < h2 is called an m-ovoid for some m. These are generalizations of the concept of an ovoid in a polar space. The study of intriguing sets in finite polar spaces is an active area of research with many open problems; for details, see [2],
In addition to the equivalent characterizations of Cameron-Liebler line classes carrying over under the Klein correspondence, we have a few additional properties in this context that do not have a good interpretation in PG(3, q).
Theorem 2.3 Let M be a set of points in Q+(5,q) C PG(5,g). The following are equivalent [22].
1. M corresponds to a Cameron-Liebler line class ofPG(3,q) with parameter x.
2. M is an x-tight set ofQ+(5,q).
20

3. There exists x G Z+ such that \M\ = x(q2 + q + 1), every tangent hyperplane to <2+(5, q) at a point of M meets M in q2 + x(q + 1) points, and every other hyperplane ofPG(5,q) meets M in x(q + 1) points.
4. There exists x G Z+ such that \Â£L fl M\ = q\Â£ fl M\ + x for every line Â£ of
PGM.
5. There exists x G Z+ such that l-G1 fl M\ = q\Â£ fl M\ + x for every line Â£ of one of the four line types in PG(3,q) (external, tangent, secant, totally isotropic).
It is important to note that the last three characterizations are stronger than their related versions in PG(3,q). Part 3 in particular states that, in addition to knowing the intersection numbers for tangent hyperplanes of Q+(5, q), we also know that every nontangent hyperplane section of Q+(5,q) meets an x-tight set in x(q + I) points. This property is important enough that we state it on its own, as it will be used in the next section to construct related combinatorial objects.
Theorem 2.4 Let T be a proper x-tight set of Q+(5, q) that spans the ambient projective space. Then the set of points covered by T has two intersection numbers with respect to hyperplanes o/PG(5,g). These numbers are
hi = (q2 + 1) + x(q + I) and h2 = x(q + I).
2.3 Two-intersection sets, two-weight codes, and strongly regular graphs
Tight sets of Q+(5,q) are related to many other combinatorial objects; here we investigate some properties of these objects.
Definition 2.5 A set of points S of PG(n, q) is called a two-intersection set with intersection numbers h\ and h2 if every hyperplane of PG(n, q) intersects S in either h\ or h2 points. Such a set is also sometimes called a set of type (hi, h2).
21

From the previous theorem, an x-tight set of Q+(5,q) whose points span PG(5,g) is a two-intersection set of PG(5,g). These sets are related to a wide range of other combinatorial objects. We begin by detailing results on an important class of linear codes.
An [n, k]q code C is a fc-dimensional subspace of the vector space V = Fâ„¢. Vectors in C are called codewords, and the vjeight wt(v) of a codeword v is the number of nonzero entries of v. A two-weight code C is a code whose codewords have precisely two nonzero weights. Given a code C, we define the dual code
C1- = {v G V\ vcT = 0 Vc G C}.
We have that C1- is an [n, n â€” k\q code.
Let C be an [n, k]q code; there exist linear functionals f : â€”>â€¢ Fg such that
C = {(/i(v), â€¢ â€¢ â€¢, /n(v)) : v ^ F^}. Since (u, v) uvT is a nondegenerate bilinear form, there exist u1; ..., ura G F^ such that fiiy) = vuf for all v G F^. Thus, we have that C = {(vu[, ..., vu^)| v G V}, and since dim(G) = k, the ip span F^. We say C is projective if no two of the ip represent the same point in PG(k â€” 1, q).
Let G C V \ {0}. We say G is a {Ai, A2} difference set if, for every v G V \ {0}, the number of pairs (x, y) G G2 such that x â€” y = v is Ai if v G G, and A2 if v ^ G. If â€”G = G, we dehne a graph G(Q) whose vertices are the vectors in V, with u and v adjacent if and only if u â€” v G Q.
Definition 2.6 A strongly regular graph vnth parameters (v, k, A, p) is a connected k-regular (simple, undirected) graph on v vertices, not null or complete, such that any two adjacent vertices share A common neighbors, and any two nonadjacent vertices share p common neighbors.
We now give a result connecting the concepts of two intersection sets, two-weight codes, {Ai,A2} difference sets, and strongly regular graphs due to Calderbank and Kantor [7].
22

Theorem 2.7 Let V = Fâ„¢+1; O = {yi \ 1 < i < r} be a set of vectors which span V (so r > n + 1) and are pairwise independent, and let Q = {cyi \ c E F*} be the set of nonzero scalar multiples of the yi; then the following statements are equivalent:
1. O is a set of type (r â€” w\,r â€” u>2) in PG(n, q) for some w\, W2;
2. C = {(x â–  yi, ..., x â–  yk)\ x E V} is a projective two-weight [r, n+ l]q code with nonzero weights W\ and u>2;
3. Q is a {Ai, A2} difference set for some X\, A2;
4- G(Q) is a strongly regular graph with parameters (qn+1, r(q â€”l),X,y), where for some w\, W2 we have
X = r2(q â€” l)2 + 3r(q â€” 1) â€” qw\W2 â€” r(q â€” l)(wi + w2) + q2(w\ + u>2) and
_ q2wiÂ«i2 t1 qn+1 '
This means that if Â£ = {yi,..., yx(q2+q+i)} is an x-tight set of Q+{3,q) which spans PG(5,g), then
f. C is a set of type {{q2 + 1) + x(q + 1 ),x(q + f)) in PG(5, q);
2. the points of Â£ define a projective two-weight [x(q2+q+ f), 6\q code with weights (q â€” 1 ) 3. Q = {cyi | c E F*} is a {Ai, A2} difference set for some Ai, A2; and
4. G(Q) is strongly regular with parameters
(q6, x(q3 â€” 1), x(x â€” 3) + q3, x(x â€” 1)).
2.4 Trivial examples
There are a few examples which trivially satisfy the necessary requirements to be a Cameron-Liebler line class.
23

1. The empty set 0 is a Cameron-Liebler line class with parameter 0.
2. The set star(p) of lines through a common point p of PG(3,q) is a Cameron-Liebler line class with parameter 1 corresponding to a 1-tight set of Q+(5,q) consisting of the set of points in a (Latin) plane.
3. The set line(7r) of lines in a plane tt of PG(3, q) is a Cameron-Liebler line class with parameter 1 corresponding to a 1-tight set of Q+(5,q) consisting of the set of points in a (Greek) plane (this is equivalent to the previous example in
Q+M).
4. The set star(p) Uline(7r), where tt is a plane of PG(3, q) and p is a point not in tt, is a Cameron-Liebler line class with parameter 2 corresponding to a 2-tight set of Q+(5, q) which is a union of two disjoint planes (one Latin and one Greek).
5. The complements of the above sets are Cameron-Liebler line classes with parameters q2 + 1, q2, q2, q2 â€” 1 respectively.
We call the Cameron-Liebler line classes in this list trivial.
2.5 Non-existence results
Cameron and Liebler conjectured that there were no nontrivial examples of these line classes, and proved this conjecture for classes with parameter < 2. Many other results followed, leading to some interesting connections with various geometric objects.
Many of the early non-existence results relied strictly on counting arguments;
specifically, we can think of sets of the type star(p) or line(7r) for a point p or a
line 7r as being essentially the same, and refer to these as cliques. The equivalent
definitions for a Cameron-Liebler line class allow us to perform some analysis on the
potential intersection numbers with respect to cliques of a hypothetical line class
with a given parameter x. Using these arguments, Penttila [27] was able to rule out
24

several parameters in specific cases, and Bruen and Drudge [5] were able to rule out the existence of line classes with parameter 2 < x < y/q.
These methods were greatly improved in 1999 by Drudge [13] when he showed that if the intersection of an indecomposable Cameron-Liebler line class Â£ with parameter x > 2 and some clique C has x < |Â£ fl C| < x + q then Â£ n C forms a blocking set in C (in this context, a set of lines not containing any pencil, such that every point is on at least one of the lines; the normal definition is dual to this). Blocking sets are well studied, and there are many results on their minimum possible size. This gives a powerful tool for investigating the feasibility of certain parameters for Cameron-Liebler line classes. Drudge used this method to rule out the case where 2 < x < \{q + 1) when q is prime, and also gave the first nontrivial example of a Cameron-Liebler line class having parameter 5 in PG(3, 3). Soon after, he and Bruen [6] constructed an infinite family of examples of line classes having parameter \{ In 2004, Govaerts and Storme [15] used these blocking set techniques to improve the nonexistence result, eliminating the possibility of 2 < x < q when q was an odd prime. Soon after, Govaerts and Penttila [14] were able to rule out a few parameters in PG(3,4) by considering intersections with multiple blocking sets. In this same paper, they constructed the first example of a Cameron-Liebler line class for even q, an example with parameter 7 in PG(3, q). Multiple blocking sets can also be viewed as a special case of a more general class of combinatorial objects called minihypers. De Beule, Hallez, and Storme [10] used known results on these objects in Q+(5, q) to show that, when q is not prime, we cannot have 2 < x < |.
While the previous results are of considerable interest, in that they relate Cameron-Liebler line classes to other well-studied objects, the most recent and strongest nonexistence result is notable in that it uses primarily geometric arguments. In 2010, Metsch [22] looked at how an x-tight set of Q+(5,q) could potentially inter-
25

sect a parabolic Q(4, q) embedded in the quadric. He was able to use this technique to show the following:
Theorem 2.8 A Cameron-Liebler line class C, with parameter x < q exists only for x <2, and corresponds in Q+(5,q) to the union of x skew planes.
This shows that any nontrivial example must have parameter q < x < q2 â€” q.
2.6 Known examples
We now give constructions for the known examples of Cameron-Liebler line classes.
2.6.1 Bruen and Drudge examples
Drudge constructed the first known nontrivial example of a Cameron-Liebler line class in his 1998 doctoral dissertation [12]. His original example was in PG(3, 3) and had parameter x = 5. Not long after, he and Bruen [6] generalized this construction to an infinite family of examples in PG(3, q) having parameter x = \{q2 + 1) for every odd q. Here we describe their construction.
Let q be odd, and O = Q~(3, q) C PG(3, q) be an elliptic quadric with quadratic form Q. The rank 1 geometry O has q2 + 1 isotropic points and no totally isotropic lines, so no three points of the quadric are collinear; therefore every line of PG(3,q) contains 0, 1, or 2 points of O. These lines are called external, tangent, or secant, respectively. Each point p G O lies on q2 secants to O, and so lies on q + 1 tangent lines. Let Cp be a set of \{q + 1) of the tangent lines to O through p, and let S be the set of secant lines to O; then
Â£ = (UpeoTp) U S
is a set of
l(q2 + i)(? + i) + l(q2 +1 )(q2) = \(q2 +1 )(q2 + q +1)
26

lines of PG(3,q), which is the number of lines in a Cameron-Liebler line class with parameter \{q2 + 1). The goal is to select the sets Â£p in such a way that C, is in fact a Cameron-Liebler line class.
Every plane of PG(3, q) is either tangent to O, and so contains a unique point of O, or else intersects O in a conic. The nontangent plane sections of O can be used to associate the points and nontangent plane sections of O with points and circles of the inversive plane IP (5) [23], so that each circle of IP (5) corresponds to a section of O by a nontangent plane 7r containing q + 1 tangent lines to O. An intersecting pencil of circles is the set of (q + 1) circles through two common points of IP (q), and a tangent pencil of circles is a (maximal) set of q mutually tangent circles on a given point of IP (q).
An equivalence relation ~ can be defined on the circles of IP (q) by
Ci ~ C2 -<=/- 3C such that C is tangent to both C\ and C2.
The circles of IP (5) fall into precisely two equivalence classes under this relation according to whether is a square or nonsquare, where 7r is the plane containing
the circle in question. Let A be one of these equivalence classes; A contains exactly \ of the circles in each intersecting pencil and either all or none of the circles in each tangent pencil. Thus if we define Â£p to be the set of tangent lines at p contained in a plane section which corresponds to a circle in A, Â£p contains \(q + 1) of the tangent lines to O at p.
Bruen and Drudge show that C, is a Cameron-Liebler line class with parameter + 1) by showing the set of lines in C, has a certain â€œmatchingâ€ property with respect to the external lines to O which are the intersection of two tangent planes.
2.6.2 Penttila and Govaerts example in PG(3,4)
Another known example of a nontrivial Cameron-Liebler was constructed by Penttila and Govaerts [14]. This is an example in PG(3,4) with parameter x = 7, and
27

was the first known nontrivial example when q is even. So far there has not been a generalization of this construction.
Let 7T be a plane in PG(3, 4) containing a hyperoval O and let p be a point not in 7r. Define C to be the cone with base O and vertex p, with G the set of generators of C, S' the set of secants to C which do not contain a point of O, and E the set of lines in n which are external to O.
Theorem 2.9 The set C = GUSUE is a Garner on-Liebler line class with parameter 7.
Proof: There are seven types of lines in PG(3,4) with respect to the cone C and the distinguished plane tt containing O.
1. Generators of C; this is the set G C C.
2. Secants to C which are skew to O; this is the set S C C.
3. Lines in tt which are skew to O; this is the set E C C.
4. Lines through p not contained in C.
5. Secants to C which meet a single point of O.
6. Secants to O.
7. Lines skew to C which are not contained in tt.
The points are of 5 types. Here we count the number of lines of each type through a point of each type.
1. {p}; of the 21 lines through p, 6 are of type 1, and 15 are of type 4.
2. Points on C \ ({p} U 7r); of the 21 lines through such a point, 1 is of type 1, 15 are of type 2, and 5 are of type 5.
28

3. Points on 0\ of the 21 lines through such a point, 1 is of type 1, 15 are of type 5, and 5 are of type 6.
4. Points on tt \ 0\ of the 21 lines through such a point, 9 are of type 2, 2 are of
type 3, 1 is of type 4, 3 are of type 6, and 6 are of type 7.
5. Points on PG(3,4) \ (C U tt); of the 21 lines on such a point, 9 are of type 2, 1
is of type 4, 6 are of type 5, and 5 are of type 7.
From this, we can count that a line in Â£ meets 50 other lines of Â£, and a line not in
Â£ meets 35 lines of Â£. Thus Â£ is a Cameron-Liebler line class with parameter 7. â–
Unfortunately this construction does not generalize to other values of q in any obvious way, as we do not get the correct number of lines for a Cameron-Liebler line class unless q = 4.
29

3. Methodology
Here we describe some algebraic techniques which we will use to search for new examples of Cameron-Liebler line classes of PG(3,q). We will search for these as tight sets of Q+(5, q); as such, we will develop a model of this quadric which will be convenient for our computational work.
3.1 An eigenvector method for tight sets
Our search for new Cameron-Liebler line classes will be conducted in the context of searching for new x-tight sets of Q+(5, q). An eigenvector method will be used to search for these objects, which is due to the following result of Bamberg, Kelly, Law and Penttila [2].
Theorem 3.1 Let Â£ be a set of points in Q+(5,q) with characteristic vector x and let A be the collinearity matrix of Q+(5,q). Then Â£ is an x-tight set if and only if
(x ~
x
q2 + 1
where j is the all-ones vector.
S)A = (q2-l)(x~
x
q2 + 1
j),
Proof: By definition, Â£ is an x-tight set if and only if, for p G Â£, p is collinear with (q2 â€” 1) + (q + l)x other points of Q+(5, q) and, for p ^ Â£, p is collinear with (q + l)x points of Q+(5, q). Thus Â£ is an x-tight set if and only if
XA= (q2 - l)x + x(q + l)j.
Since j A = q(q + l)2j, the above formula follows immediately. â–
In Q+(5,q), there exist two disjoint totally isotropic planes tv\ and 7^; our goal is to find tight sets which are disjoint from [jii U 772). The above method will be slightly modified to account for this. We will let A1 be the submatrix of A obtained by throwing away the rows and columns corresponding to points in (771 U 772).
Theorem 3.2 Let Â£ be a set of points of Q+(5,q) disjoint from 7Ti and 1r2 and let
xf be the vector obtained from the characteristic vector of Â£ by removing entries
30

corresponding to points of tt\ and 7t2. Then Â£ is an x-tight set of Q+(5, q) if and only
if
(x'~

rJM = {q - i)(x -
rJ)-
q2 â€” 1 q2 â€” r
Proof: Denote the eigenspace of A corresponding to the eigenvalue (q2 â€” 1) by E, and the eigenspace of A1 corresponding to the eigenvalue (q2 â€” 1) by E'. Since U 7r2
is a 2-tight set,
2 . ^
T â€” X(7riU7T2) â€” ^2 _|_ ^ E-
Let C be a set of points of Q+(5, q) disjoint from 7Ti and tt2 with characteristic vector X; then Â£ is a x-tight set if and only if
x
X
rj e E
V = (x - -^rj) + ~Y~-T e E.
q2 â€” q
q2 + 1 q2 + f
The entries of v corresponding to points of (7riU7r2) are 0, and the entry corresponding to a point p ^ fni U 7t2) is given by
2
(x)P -
x
x
(x)P -
X
q2 + 1 q2 â€” 1 q2 + 1 q2 â€” 1
Thus if we obtain a new vector v' from v by throwing away entries corresponding to points in [jii U 7t2), and a new vector yf from x in the same manner,
v' = xf
x
q2 â€” 1
j eE'
X
x
q2 + 1
j eE
Â£ is an x-tight set.
3.2 Tactical Decompositions
For any incidence structure, a tactical decomposition is a partition of the points into point classes and the blocks into block classes such that the number of points in a point class which lie on a block depends only on the class in which the block lies, and similarly with points and blocks interchanged. Examples can be obtained by taking as point and block classes the orbits of some collineation group acting on the structure.
31

The idea of a tactical decomposition can also be extended to matrices. Let A = [a,ij\ be a matrix, along with a partition of the row indices into subsets R\, ..., Rt and a partition of the column indices into subsets C\, ..., Ctj. We will call this a tactical decomposition of A if for every (i, j), 1 < i < t, 1 < j < t', the submatrix [ah,e] (h G Ri, Â£ Â£ Cj) has constant column sums and row sums r^. A tactical decomposition of an incidence structure corresponds to a tactical decomposition of its incidence matrix. The row and column sum matrices of A are defined to to be Ra = Vij\ and Ca = [cp] respectively.
Utilizing a tactical decomposition makes finding eigenvectors corresponding to x-tight sets easier, as an eigenvector of the column sum matrix Ca obtained from the decomposition can be used to recover an eigenvector of A. The following result comes from the theory of the interlacing of eigenvalues, which was introduced by Higman and Sims, used by Payne in the study of generalized quadrangles, and further developed by Haemers; see [17] for a detailed survey.
Theorem 3.3 Suppose the matrix A can be partitioned as
A
An â–  â–  â–  An
(3.1)
Aki â–  â–  â–  Akk
vnth each An square, 1 < i < k, and each Aij having constant column sum Cij; then any eigenvalue of the column sum matrix Ca = [cp] is also an eigenvalue of A.
Proof: An eigenvector of Ca can be expanded according to the partition of A (by duplicating the entries corresponding to each part) to construct an eigenvector of A.
To apply this theorem to the task of finding eigenvectors of the collinearity matrix of Q+(5, q), we define an incidence structure R with both â€œpointsâ€ and â€œblocksâ€ being given by the points of Q+(5,q), and incidence being given by collinearity. Thus the
32

incidence matrix A of LL is given by the collinearity matrix of Q+(5, q). Furthermore, any automorphism of Q+(5, q) determines an automorphism of % in an obvious way. The matrix A is symmetric, and any tactical decomposition arising from an automorphism group of Q+(5, q) will induce the same partition on the rows of A and the columns of A. The following theorem gives us a nice relationship between the row and column sums in arising from such a tactical decomposition.
Theorem 3.4 Let A be a symmetric matrix and let Oi, Ok be the parts of a tactical decomposition of A (so the row and column partition is the same) with \Oi\ = Oi; then rij = Cji, and Oirij = OjCij.
Proof: If Aij is the submatrix associated with the row part corresponding to Oi and the column part corresponding to Oj, then Aiq = Aj^ thus for all i, j. Also,
each of the o* rows of Aiq has row sum r^, and each of the Oj columns has column sum dj. Summing over all entries of A^ in two ways gives tyry,- = OjC^. m
Corollary 3.5 Let A be a symmetric matrix with a tactical decomposition having the same parts for rows and columns, with part i containing Oi rows/columns; then we have the following relationship between the row and column sum matrices:
Rl = M = M = [%Â«} = cA.
Â°j
3.3 A model of Q+(5,q)
We now describe a model for Q+(5,q) which gives us a range of algebraic tools to use in searching for tight sets. Let F = Fg, E = Â¥q3, and
T = Te/f : x iâ€”> xq2 + xq + x.
We consider Q+(5, q) to have V = E2 as its underlying vector space, considered over F and equipped with the quadratic form
Q â–  (x,y) ^ T(xy).
33

The polar form B of Q is then given by
B((ui,u2), (vi,v2)) = T(uiv2) + T(u2vi).
This form is nondegenerate, since if (vi,v2) E V has B((ui,w2), (x,y)) = 0 for all (x,y) E V, then T(v\y) + T(v2x) = 0 for all (x,y) E V. Setting x = 0 forces
T(v\y) = v\y + v\yq + v\ yq2 = 0 for all y E E*,
thus v\ = 0. Likewise, setting y = 0 can be seen to force v2 = 0, and so (wi,w2) =
(0,0).
It can be also be seen that
7Ti = {(x} 0) : x E E*} and vr2 = {(0,y) : y E E*}
are totally isotropic planes with respect to this form. This shows that the quadric defined by Q has Witt index 3, and so is hyperbolic.
3.4 The general method
Theorem 3.6 Let q ^ 1 mod 3. Take y E E* with \y\ = q2 + q + 1, and define the map g on Q+(5,q) by
9 â–  (x,y) ^ {iax,ia~ly)-
then the group C = (g) < PGO+(6, q) and has \C\ = q2 + q + 1. This group acts semi-regularly on the points of Q+(5,q) and stabilizes the totally isotropic planes and 7t2 â€¢
Proof: It is clear that g is an isometry of Q+(5, q) having order cj2 + q + 1. To see that C acts semi-regularly on the points of Q+(5,q), notice that gl((x,y)) = (x,y) implies that jT E F. But
(q2 + q + l,q- 1) = (q - 1,3) = 1,
34

since q ^ 1 mod 3. Thus this can only happen when fil = 1, and so the identity is the only element of this group fixing a point. â–
If a is a primitive element of if, we can without loss of generality assume that fj, = aq~l. The semi-regular action of C on Q+(5, q) gives us the following result.
Theorem 3.7 Let A be the collinearity matrix of Q+(5, q), q ^ 1 mod 3, vrith a tactical decomposition induced by the action of the cyclic group C defined aboue; then the row of each submatrix of the decomposition is the same as the column sum. Thus the decomposition matrix (which is the same for row sums and column sums) is symmetric.
Proof: This follows directly from 3.4 since all orbits have the same size. â–
Since each orbit has size q2 + q + 1, a union of x orbits contains the right number of points to be an x-tight set of Q+(5, q). Our goal will be to find ways of combining these orbits which will result in an x-tight set. We accomplish this by considering large subgroups G < NPro+(6,q)(C) having relatively few orbits on the points of Q+(5,q). The orbits of such a group are unions of orbits of C. We use such a group G to induce a tactical decomposition on the points of Q+(5, q), and then use this decomposition to form the column sum matrix B of the collinearity matrix A, after throwing away the entries corresponding to points in 7Ti and 7r2. The eigenspace of B for the eigenvalue g2 â€” 1 is then searched for eigenvectors having a form corresponding to an x-tight set of Q+(5,q). Whenever new examples show a pattern, e.g. a common formula for x in terms of q or a similar stabilizing group, algebraic, geometric, and combinatorial details are analyzed in an attempt to find a construction for a new infinite family of tight sets.
35

4. New examples
Throughout this chapter, we let q ^ 1 mod 3, E = Â¥q3 with E* = (a), and F = Fq < E with F* = (uj) where uj = aq2+q+1. The hyperbolic quadric Q+(5,q) is defined over the vector space V = E2 (considered over F) and has quadratic form Q((x,y)) = T(xy), where T = Tf/e, and polar form B(u,v) = T(uiu2) + T(u2ui) as described in Chapter 3. Put y = cC_1, and define the cyclic group C = (g), where
9 â–  (x,y) ^ {yx,y~ly)-
then C acts semi-regularly on the points of Q+(5, q) and stabilizes the disjoint totally isotropic planes tv\ = {(aqO) : x E E*} and 7r2 = {(0,y) : y E E*}.
Below is a summary of the new examples of Cameron-Liebler line classes which are described in this chapter. Notice that here we consider the parameter of the line class to be smaller than that of its complement, and we take the line class to be disjoint from [fi U 7t2); thus a new example with parameter x described below also gives new line classes with parameter x + 1, x + 2, (g2 +1) â€” x, q2 â€” x, and (q2 â€” 1) â€” x.
X 9 Aut(Â£)
W-i) q = 5 or 9 mod 12 and q < 200 (Zg2+g+i x Zi(ff_1}) xi Z3
W + if q = 2 mod 3 and q < 150 ^ 336 q = 27 (Zg2_|_g_|_i X Z2) X Zg
495 q = 32 ^q2-\-q-\-1 ^ ^15
Table 4.1: Parameters and automorphism groups of the new examples of Cameron-Liebler line classes constructed.
36

4.1 New examples with parameter |(g2 â€” 1)
Here we describe a construction giving many new examples of tight sets in Q+(5,q) having parameter |(g2 â€” 1). This construction requires us to have q = 5 or 9 mod 12, and has resulted in new tight sets for all such q < 200.
4.1.1 The construction
Let S = {x : x G E*\ T(x) = 0}; then the orbits of C on the points of Q+(5,q) are tv\ = (l,0)c, tt2 = (0, l)c, and (l,x)c for each x E S. We also let the group H = (h), where
h : (x,y) ^ (x,u4y), act on the space, and put G = (C,H).
Lemma 4.1 The group H defined above centralizes C, and intersects C trivially.
Proof: To show that H centralizes C, we only need to show that g and h commute; we have that
%((T V))) = H(/ax, ia~ly)) = (yx, y~lu4y) and g(h((x, y))) = g((x, u4y)) = (yx, y~lu4y).
Since the powers of y are pairwise independent over F, it is clear that HC\C contains only the identity. â–
Corollary 4.2 The group G defined above is equal to C x H, and so |G| = \{qâ€” l)(q2 + q+l).
Furthermore, it can be seen that G acts semiregularly on the points of Q+(5, q) \ ijii U 7t2), as H acts semi-regularly on those points, and induces a semi-regular action on those orbits of C as well.
37

Let Sk be the subset of S containing the elements with loga(x) = k mod 4 for 0 < k < 3. For x G S, put x = {u)Atx : 0 < t < (q â€” l)/4}; for shorthand we will write (1,4:) = {{l,x') : x' G x}. Now we define
Â«(z,y) := |(f,^)Â± n (i,y)c\.
In terms of the tactical decomposition induced by G on Q+(5, q), n(x, y) is the number of points in (l,t/)c collinear with any given point of {l,x)G. Thus k(x' ,y') = n(x,y) for all i'gi and y' G y.
Let A be the matrix obtained from the tactical decomposition induced by G on the collinearity matrix of Q+(5,q) after throwing away the entries corresponding to points in 7Ti U 7t2. We use a specific ordering of the orbits of G to define A. Notice that S0 contains \( (1,X0)C, (l,Xg)C, (1,UJX0)C, . . . , (l,lVXg)C,
(l,UJ2Xo)C, (1 ,U2Xg)C, (1,U3X0)C, , (1 ,U)3Xg)C.
Now A can be described as follows:
Aq Ai A2 As
As Aq Ai A2
41 =
A2 As Aq Ai A\ A2 As Aq
where Ak = (n(xi, ujkXj))0<. for 0 < k < 3. This matrix is block-circulant, which allows us to apply the following result on eigenvectors of block-circulant matrices due to Garry Tee [30].
Theorem 4.3 Let ( be any fourth root of unity, and A be a block-circulant matrix as defined aboue, with blocks Aq, A\, A2, As each hauing size nj4. Take a uector v G IR?. Then the uector
w = [v(v(2v(3v]
38

is an eigenvector of A for X if and only i/v is an eigenvector of A0 + (Ai + (2A2 + C3Â«3 for X.
We now investigate some properties of k in order to better understand the structure of A.
Lemma 4.4 For x,y E S (not necessarily distinct), n(x,y) = n(y,x).
Proof: This follows directly from Theorem 3.4, along with the fact that (l,x)c and (1 ,y)c are the same size. â–
Corollary 4.5 A is symmetric; thus A0 and A2 are symmetric, and Ai = Aff.
Lemma 4.6 For x,y E So (not necessarily distinct), n(x,ujky) = n(y,ojkx) for 0 < k< 3.
Proof: First we notice that (y) contains q2 + q + 1 distinct elements of E*, no
two differing by a multiple in F. Thus, for any z E E*, there exists an integer 0 logÂ« Asz) = loga (y3) = loga (aj{q~1)) = 0 mod 4.
Now take x, y in So] we have that
K(x,ujky) = |{z : 0 < i < cf2 + q + 1| T(ylx + y~lA1 ujky) = 0}|.
0 There exists (a unique) j with 0 yi+jx + y-{l+3)oj4tojky = ylAsy +
39

From this we can see (by relabeling indices) that
n(x,u}ky) = |{z : 0 < i < q2 + q + 1| T(fAx + y loj4tojky) = 0}|
0 = | {z : 0 0 = n{u)4sy,u)kx) = n(y,u}kx).
Lemma 4.7 For x,y E S0 (not necessarily distinct), n(x,ujy) = /i(x,uj3y).
Proof: We have that n(x,u}3y) = n{u)x,u)4y) = n{u)x,y) = n(y,ujx) = n(x,ujy). â–
Corollary 4.8 Ai = A3, and so all blocks of A are symmetric.
The following two lemmas have been verified computationally. It seems reasonable to attempt to prove that they will hold true for all values of q = 5 or 9 mod 12, although it is not clear why this would occur.
Lemma 4.9 If q < 200, then for all x E So, n(x,x) â€” k(x,ou2x) = â€” 1.
Proof: Computed with Magma, see Appendix B. â–
Lemma 4.10 If x < 200, then for all x,y E S0 vnth x/y, n(x, y) â€” n(x, u2y) = Â±q. Proof: Computed with Magma, see Appendix B. â–
Lemma 4.11 If x < 200, then for x,y,z E So, distinct, n(x,y) â€” n{x,uj2y) = k(x, z) â€” k(x, oj2z) if and only if n(y, z) â€” n(y, oj2z) = q.
Proof: Computed with Magma, see Appendix B. â–
Theorem 4.12 If q < 200 is a prime povjer congruent to either 5 or 9 mod 12, then there exists an x-tight set C, in Q+(5,q) vnth x = \{q2 â€” 1) in PG(3,q) stabilized by a cyclic group of order q2 + q + 1 acting semi-regularly on the points. We also have
40

that C is disjoint from a trivial 2-tight set consisting of a union of two skew totally isotropic planes.
Proof: We have that i is a fourth root of unity. The matrix
H = Aq + iA\ + ff A2 + i3A3 = Aq + iA\ â€” A2 â€” iA3 = Aq â€” A2
has a nice form; all of the diagonal entries are â€”1, and all other entries are +q. Furthermore, there is some partition of {xo, ..., xq}, into parts L\ and L2 such that Hij = q if and only if i yt j and ay, ay are in the same part; say \Lf = a and |L2| = b, with a + b = q + 1. If we take K to be the adjacency matrix of the graph KLl Â© KL2 (where KLl and KL2 are the complete graphs on the sets L1 and L2, respectively) and K' be the adjacency matrix of the complement of this graph, then H = qK â€” qK' â€” I. We will form the vector v = xm â€” ~ \xl2- Notice that = \ if we let
x = Now we have that
(XÂ© - Xl2)H=(xl1 ~ XL2){qK - qK1 - I)
= ((a - l)qxia ~ aqxL2 ~ XÂ©) - ((& - 1 )qXL2 ~ bqxr2 ~ Xl2)
= {{a + b â€” 1 )q - 1) x+ - {{a + b- 1 )q - 1) xl2
= (q2 - 1 )(xÂ© - x+),
thus v is an eigenvector of H having the desired form. We can use v to construct an eigenvector of A in four different ways, namely
Â±[ v â€”v â€”v V ]
Â±[ V v â€”v â€”v ]
each of which in turn can be used to construct an eigenvector of the collinearity matrix M of Q+{5,q) corresponding to a \{q2 â€” l)-tight set. â–
4.1.2 Some details of these examples
Our examples with parameter |(g2 â€” 1) have a group isomorphic to Zg2+g+1 x
acting on them, by construction. By observing details about the orbits used
41

in the construction, we notice that these examples are also stabilized by Aut(Fg3), thus they are stabilized by a group isomorphic to (Zq2+q+i x Zi(^q_1~)) x Z3. For those examples small enough to compute their full stabilizer in PrL(4, q), which are those with q < 41, this is in fact the full group.
We can also compute intersection numbers of these line classes in PG(3,q) with respect to planes and point stars of PG(3,q); this becomes prohibitively expensive, computationally, when q > 32. Plere we include details for some small values of q, as well as q = 81; this special case was of particular interest, see Chapter 5, so a considerable amount of time was dedicated to computing these values.
In this table, we include the intersection numbers with respect to planes of PG(3,q)-, the examples considered here are all isomorphic to their dual, and so have the same intersection numbers with the same multiplicities with respect to the point stars of PG(3, q).
q X Intersection numbers, with multiplicity; we have r = q2 + q + 1
5 12 0(b, 6^, 12(2r), 18^, 24^
9 40 0(0, 30(4r),40(r), 60(4r)
17 144 0(0, 108^, 126(4r), 144^, 180(4r), 198(4r)
29 420 0(0, 330(7r)) 39o(7b; 420^, 480(7r), 540^
81 3280 0W, 29 52(40r), 3280(r), 369Q(40r)
Table 4.2: Intersection numbers of line classes vrith parameter â€” 1) vrith the planes of PG(3, q).
The numbers in bold represent the intersection numbers for the plane corresponding to 7Ti in Q+(5,q), which is disjoint from our line class, and the planes through the point which corresponds to 7T2 in Q+(5, q), which shares \{q2 â€” 1) lines with our line class. It is worth noting that the number of lines shared by each plane with the line
42

class is divisible by (q + 1). The multiplicities being divisible by q2 + q + 1 is a side effect of C acting semi-regularly on the planes of PG(3, q) not corresponding to 7Ti.
The new examples of tight sets in Q+(5, q) give examples of two-intersection sets, two-weight codes, and strongly regular graphs, as detailed in Chapter 2. While there are tables of known strongly regular graphs, these examples on q6 vertices are too large to appear. Furthermore, if there were known examples, checking isomorphism would most likely be unreasonable.
4.2 New examples with parameter |(g + l)2
Here we give details on many new examples which have been constructed in joint work with Jan De Beule, Klaus Metsch, and Jeroen Schillewaert, having parameter |(q + l)2. These examples have been constructed for all values of q = 2 mod 3 which are computationally feasible. Unfortunately, in general these examples do not exhibit much symmetry; all of the examples found have C x Aut(Fg3) as their full stabilizing group. When q is prime, this does not give much to work with. These are found through more of a search than a construction; first we put together the tactical decomposition matrix for Q+(5, q) \ [jii U^) with respect to the group, then we search over the eigenspace for appropriate eigenvectors (see Appendix A for details about the algorithms used). With a small stabilizer, there are lots of orbits; for example, if q is prime, there are |(g2 â€” 1) orbits to consider. As such, forming the matrix for the tactical decomposition is a large task. Furthermore, we do not currently have a good method for reducing the size of the eigenspace to search over, so finding these examples is computationally infeasible if the eigenspace of the tactical decomposition matrix is too large (12 dimensions starts to push the limits of our computing power).
An important subcase of these examples occurs when q = 2e, where e > 1 and
odd. In this case, we have a slightly larger stabilizing group to work with. These
examples are also of particular interest since there is only one previously known
Cameron-Liebler line class in PG(3,q) for q even (see Chapter 2 for this construc-
43

tion). New examples with this parameter have been found for q e {8,32,128}, as well as for odd primes q < 100 which are congruent to 2 mod 3, and for q = 125. In all of the cases where it is feasible to compute the stabilizer group (q < 32), we have that C xi Aut(Fg3) is the full group. Below, we describe how some of these line classes intersect planes of PG(3,q). All of the examples considered below are isomorphic to their dual, and so have the same intersection numbers with the same multiplicities with respect to point stars of PG(3, q).
Q X Intersection numbers, with multiplicity; we have r = q2 + q + 1
5 12 0(b, 6^, 12Gb, 18 8 27 0(0, 18Gb, 27w, 36Gb, 54Gb
11 48 0Â«, 24G), 36Gb, 48Gb, 60GG, 72 17 108 OG), 72Gb, 90GG, 108(4G, 126Gb, 144Gb, 216
23 192 0(0, 120G), 144Gb, 168Gb, 192Gb; 216Gb, 240Gb, 264 32 363 OG), 264Gb, 33QGÂ°b, 363(r), 396GÂ°b, 462Gb, 726G)
Table 4.3: Intersection numbers of line classes with parameter |(g + l)2 with the planes of PG(3, q).
4.3 Some other new examples
We also have a couple of other new examples which do not currently seem to fit into a nice grouping. These examples have been found by assuming a group acting on the points of Q+(5,q) (usually a subgroup of N0+(etq)(C)), forming the orbits of Q+(5,q) \ ("7Ti U 7r2) and the associated matrix for the tactical decomposition, and searching over all possible parameters. The number of possible parameters can be very large, especially if the orbits are not all the same size. It was computationally feasible when q < 23 to assume that the examples we were looking for admitted the
44

group C x Aut(Fg3/Fg) as a stabilizer, though these searches did not yield any new examples.
For q = 27, the variation in the orbit sizes gives a large number of possible parameters, and there is a relatively large eigenspace to consider. Thus, considering a small stabilizing group was not feasible. By assuming the group C x Aut(Fg3) stabilized the examples, we were able to find a new tight set with parameter 336. This example is also stabilized by the map (x, y) iâ€”> (x, â€”y), and so has full stabilizer isomorphic to (Zq2+q+1 x Z2) x Z9. Restricting our first search with C x Aut(Fg3/Fg) by assuming our parameter was divisible by q + 1, we found no other new examples.
With q = 32, all of the point orbits of the group C x Aut(Fg3) on Q+(5, q) have the same size, so the search is feasible assuming this stabilizer. We are able to find two new examples having parameter 495, each having C x Aut(F323/F2) as their full stabilizer. In this case, these two examples are isomorphic as tight sets, but not as Cameron-Liebler line classes. In PG(3,q), they are dual to one another.
Below we detail how these examples intersect the planes of PG(3,q). Note that only the first example is self-dual; in this case, the intersection numbers and multiplicities for point stars of PG(3, q) are the same as for planes. For the two examples with q = 32, the plane intersection numbers of one example are the point star intersection numbers for the other, and vice-versa.
Q X Intersection numbers, with multiplicity; we have r = cj2 + q + 1
27 336 Od), 252(-6r\ 336(13b; 420^ 504<2r)
32 495 Od), 330d), 396dd, 462dÂ°d; 495w, 528^ 594W)
32 495 Qd), 396dÂ°d, 495w, 528d5r), 660<6r>
Table 4.4: Intersection numbers of some other new line classes.
45

5. Planar two-intersection sets
A set of type (m, n) in a projective or affine plane is a set K of points such that every line of the plane contains either morn points of /C; we require that m < n, and we want both values to occur. For projective planes, there are many examples of these types of sets with q both even and odd, however the situation is quite different for affine planes. When q is even, we obtain a set of type (0,2) in AG(2,g) from a hyperoval of the corresponding projective plane, and similarly a set of type (0, n) from a maximal arc of degree n. Examples of sets of type (m, n) in affine planes of odd order, on the other hand, are extremely scarce; the only previously known examples exist in affine planes of order 9 [28].
Here we examine some combinatorial properties of these point sets in both affine and projective planes, and review the current state of the art for the affine situation. We then look at how affine sets of type (m, n) can be constructed from some of the Cameron-Liebler line classes found in Chapter 3.
5.1 Projective examples
We can deduce some information about sets of type (m, n) in projective planes through elementary counting.
Lemma 5.1 Let K be a set of type (m, n) in a projective plane ir of order q. Let tm and tn be the number of m-secants and n-secants to 1C, and let k = \1C\; then
tm + tn = q2 + Q + 1, (5-1)
mtm + ntn = k(q + 1), and (5.2)
m(m â€” 1 )tm + n(n â€” 1 )tn = k{k â€” 1). (5.3)
Proof: Each of the q2 + q + 1 lines in tt is either a m-secant or an n-secant, giving us (5.1). Counting over all secants, tm meet m points of /C, and tn meet n points of
/C; this counts each of the k points of K q + 1 times, giving (5.2). To obtain (5.3),
we notice that each of the tm m-secants contains m(m â€” 1) ordered pairs of points in
46

/C, and each of the tn n-secants contains n(n â€” 1) such pairs. Each of the k(k â€” f) ordered pairs of points in /C is counted once in this manner. â–
Corollary 5.2 If we have a set K of type (m,n) in a projective plane of order q, then k = \1C\ must satisfy
k2 â€” k(q(n + m â€” l) + n + m) + mn(q2 + q + 1) = 0. (5.4)
If we take a fixed point p G 1C, and let pm and pn be the number of m-secants and n-secants through p, respectively, we see that
Pm + Pn = q + 1 and (m - 1 )pm + (n - 1 )pn = k - 1.
From this, we see that
Pm = (n(q + 1) â€” k â€” q)/(n â€” m) and Pn = (k + q - m(q + 1 ))/{n - m),
and so pm and pn do not depend on our choice of p. Likewise, if we take a fixed point q ^ /C, and let am and an be the number of m-secants and n-secants through q, we see that
Cm + Again, these values can be seen to be independent of our choice of q; we have that
Vm = (n(q + 1) â€” k)/(n â€” m) and crn= {k - m(q + 1))/(n â€” m).
From these numbers we see that, given a set of type (m,n) in a projective plane of order q, we can construct three other related sets with two intersection numbers (for a proof, see [18]).
47

Theorem 5.3 Let K be a set of type (m, n) in a projective plane ir of order q, with \1C\ = k.
1. The complement of K, is a set of type (q + 1 â€” n, q + 1 â€” m) in tt containing 2. The set of m-secants to 1C is a set of type (pm, am) in the dual plane to ir containing tm points.
3. The set of n-secants to 1C is a set of type (pm,crm) in the dual plane to ir containing tn points.
Notice that pn â€” an = q/(n â€” m) and so it is necessary for n â€” m to divide q. If n â€” m = q, then /C can be seen to be either the set of points on a common line, or the complement of this; the examples having n â€” m = 1 are dual to these, and we consider the examples in either of these situations to be trivial.
One major class of examples are the sets of type (0,n). These examples are also known as maximal arcs of degree n, or as (qn â€” q + n, n)-arcs (as they necessarily contain qn â€” q + n points). The prototypical examples are given by hyperovals, which are sets of type (0,2); other families of maximal arcs of degree larger than 2 have been described by Denniston [11], Thas [31] [32], and Mathon [21]. Maximal arcs of degree 2â€œ are known to exist in PG(2,2e) for all pairs (a,e) with 0 < a < e, and it was proven by Ball, Blokhuis and Mazzoca [1] that there are no examples in PG(2, q) for odd q.
5.2 Affine examples
We will be concerned with sets of type (m, n) in affine planes. Through elementary counting, we get formulas very similar to those in Lemma 5.1, but giving different results.
48

Lemma 5.4 Let K be a set of type (m,n) in an affine plane ir of order q. Let tm and tn be the number or m-secants and n-secants to 1C, and let k = \1C \; then
tm + tn = q2 + q, (5.5)
mtm + ntn = k(q + 1), and (5.6)
m(m â€” 1 )tm + n(n â€” 1 )tn = k(k â€” 1). (5.7)
These modified formulas lead to the following alternate version of Corollary 5.2.
Corollary 5.5 If we have a set K of type (m,n) in an affine plane of order q, then k = \1C\ must satisfy
k2 â€” k(q(n + m â€” 1) + n + m) + mnq(q + 1) = 0.
We again get constant values pm and pn for the number of m-secants and n-secants through a point in /C, and am and an for the number of m-secants and n-secants through a point not in /C, given by the formulas
pm = (n(q + 1) - k - q)/(n - m),
Pn = (k + q - m(q + l))/(n - m),
= (n(q + 1) â€” k)/(n â€” m), and an= {k - m(q + 1))/(n - m).
This tells us that, as for the projective case, we must have n â€” m dividing q. However, since the dual of an affine plane is not again an affine plane, we do not have results about the m-secants or n-secants forming another planar set with two intersection numbers.
There are very few known examples of sets of type (m, n) in affine planes. For
planes of even order, we can obtain an example from a set of type (0, n) in a projective
plane, by choosing an external line to the set as the line at infinity to form the affine
plane. However, sets of this type do not exist in projective planes of odd order.
49

In affine planes of odd order, the only previously known examples of sets of type (m, n) are sets of type (3, 6) in planes of order 9. These sets were found through an exhaustive computer search, see [28], and examples were found in each of the four projective planes of order 9.
The size k of a set of type (3, 6) in a plane of order 9 must satisfy
k2 - 81 A: + 1620 = 0
which has solutions k\ = 36 and fc2 = 45. The complement of a set of type (3, 6) in a plane of order 9 will again be a set of type (3, 6), and the complement of a set of size k\ will contain fc2 points. The 45-sets of type (3, 6) have p3 = 2, p6 = 8, 5.3 Constructions from Cameron-Liebler line classes
We now describe a method of constructing some of the known sets of type (3, 6) in AG(2,9) starting with a Cameron-Liebler line class with parameter 40 in PG(3, 9). We then generalize this method to give a new example in AG(2, 81).
5.3.1 A two-intersection set in AG(2,9)
Take a Cameron-Liebler line class C\ of parameter 40 in PG(3, 9), as constructed in the Chapter 4. This set of lines is disjoint from a trivial Cameron-Liebler line class with parameter 2, which we will consider to be star(p) U line(7r), where p is a point in PG(3,q) and tt is a plane not containing p. This line class induces a symmetric tactical decomposition on PG(3, 9) having four classes of points and lines, as follows: the four line classes are
1. star(p),
2. line(7r),
3. Ci, and
4. Â£2 = line(PG(3, q)) \ (line(7r) U star(p) U C\).
50

Each point of PG(3, q) \ ({p} U tt) lies on either 30 or 60 lines of C\ (see Table 4.2) and so the four point classes of the tactical decomposition are
!â€¢ {p}>
2. TT,
3. V\ = {u G PG(3,q) : star(u) fl C\ = 30}, and
4. V2 = {v â‚¬ PG(3, q) : star(v) fl C\ = 60}.
The numbers of lines in each given line class through a fixed point in each given point class can be found in Table 5.1, and the numbers of points in each given point class on a fixed line in each given line class can be found in Table 5.2.
star(p) line(7r) Ci c2
{p} 91 0 0 0
7r 1 10 40 40
Vi 1 0 30 60
v2 1 0 60 30
Table 5.1: Lines per point for the symmetric tactical decomposition induced on PG(3,9) by a Cameron-Liebler line class of parameter 40.
star(p) line(7r) A c2
{p} 1 0 0 0
7r 1 10 l 1
v1 4 0 3 6
v2 4 0 6 3
Table 5.2: Points per line for the symmetric tactical decomposition induced on PG(3,9) by a Cameron-Liebler line class of parameter 40.
51

Now, if we take a plane tt' of PG(3,9) not equal to tt and not containing p, tt' contains precisely one line of line(7r) and no lines of star(p). Furthermore, tt' will contain either 30 or 60 lines of Â£\, and so 60 or 30 lines of Â£2 (see Table 4.2). Without loss of generality, we may assume that 7b contains 30 lines of Â£\ and 60 lines of Â£2. As for the various point classes, 7b does not contain p, and contains 10 points of tt, all on a common line. Under our assumptions, 7b also contains 30 points of V\ and 60 points of TV In fact, we have a symmetric tactical decomposition of 7b having 3 classes on points and lines induced by our tactical decomposition of the larger space. By taking 7b fl tt to be the line at infinity and removing it (along with all of its points) from 7b, we obtain an affine plane AG(2, 9). All of the points of this affine plane are in Vi or TV and all of the lines are in Â£\ or Â£2. It can be easily verified that tt fl V\ is a set of type (3, 6) in this plane containing 30 points. This set admits a stabilizer isomorphic to Z3. As the sets of type (m, n) in AG(2, 9) were completely classified in [28], this set is not new.
5.3.2 A new two-intersection set in AG(2,81)
We are also able to follow the above procedure with a Cameron-Liebler line class Â£\ of parameter 3280 in PG(3,81) constructed as in Chapter 4. In this case, the line classes are formed as before. As for the point classes, each point of PG(3,81) is on either 2952 lines of Â£1, or on 3690 points of Â£\. We define V\ to be the set of points on 2952 lines of Â£\. These point and line classes give a symmetric tactical decomposition of PG(3,81); the numbers of lines in each given line class through a fixed point in each given point class can be found in Table 5.3, and the numbers of points in each given point class on a fixed line in each given line class can be found in Table 5.4.
We let 7b be a plane of PG(3,81) not equal to 7r, and not containing p. Then 7b
contains one line of line(7r) and no lines of star(p). Also, 7b will contain either 2952
lines of Â£\ or 3690 lines of Â£\ (see Table 4.2); without loss of generality, assume 7b
52

star(p) line(7r) Cl c2
{p} 6643 0 0 0
7r 1 82 3280 3280
Vi 1 0 2952 3690
v2 1 0 3690 2952
Table 5.3: Lines per point for the symmetric tactical decomposition induced on PG(3,81) by a Cameron-Liebler line class of parameter 3280.
star(p) line (77) Ci c2
{P} 1 0 0 0
7r 1 82 1 1
v1 40 0 36 45
v2 40 0 45 36
Table 5.4: Points per line for the symmetric tactical decomposition induced on PG(3,81) by a Cameron-Liebler line class of parameter 3280.
contains 2952 lines of C\. The point set of tt' is again disjoint from {p}, and contains 82 points of tt, all on a common line. By taking this line, which is tt' fl tt, to be the line at infinity and removing it along with all of its points from tt', we obtain an affine plane AG(2,81). All of the points of this affine plane are in V\ or V2, and all of the lines are in or C2. If is clear that V\ is a set of type (36,45) containing 2952 points. There are no previously known examples of sets of type (m,n) in AG(2,81), so this example is new. Using Magma, the stabilizer of this set is computed and is isomorphic to Z6.
5.3.3 A family of examples in AG(2,32e)?
The combinatorics of our Cameron-Liebler line classes of parameter |(g2 â€” 1) seem to be especially nice over fields of order 32e, inducing a symmetric tactical decomposition on the space having four classes of lines and of points. A future
53

direction of research related to this observation is to focus on proving the existence of an infinite family of Cameron-Liebler line classes having this parameter in the specific case where q = 32e, and examining the intersection numbers with respect to the planes and point stars of PG(3,q). If these line classes always induce such a tactical decomposition, with one of the classes being a plane and another a point star, then we will be able to construct an infinite family of sets of type (m, n) in AG(2, 32e).
Assume we have a Cameron-Liebler line class C\ with parameter ^(36e â€” 1) in PG(3, 32e) which is disjoint from a trivial Cameron-Liebler line class star(p) Uline(7r) with parameter 2 (so p ^ tt), and that this line class induces a symmetric tactical decomposition of PG(3,q) as above having point classes {p}, tt, V\, V2, and line
classes star(p), line(7r), Â£1, Â£2. Take a plane tt' distinct from 7r and not containing p.
The points in the affine plane tt' \ (7b fl 7r) are all in V\ or V2, and the lines are all in Â£1 or Â£2- If we let K = V\ fl tt', then the lines of the affine plane have precisely two intersection numbers with K depending on whether they are in C\ or Â£2. Without loss of generality we will assume that each line of C\ fl star(7r/) meets m points of 1C. Let A and B be such that each point in V\ is on A lines of C\ and B lines of Â£2; thus each point in V2 is on B lines of C\ and A lines of Â£2.
The most likely possibility for n â€” m, and the situation for our earlier examples, is that n â€” m = 3e. Assume that this is the case, so that n = m + 3e. By Definition 2.1, we have
^(36e - 1) + (32e + 1 )pm = |Â£i n tt'I + A and
-(36e â€” 1) + (32e + l)crm = (Â£2 fl n'\ + A,
by applying the result to C\ using the incident point-plane pair (u^') with u e V\, and to Â£2 using the incident point-plane pair (v, 7b) with v e TV Since am â€” pm = 3e, we see that
|Â£2 n tt'I - |Â£i n tt'I = (32e + 1)( 54

which, along with the fact that
|C2 n tt'I + |Â£i n tt'I = 34e + 32e = (32e + l)32e
, tells us that
|Â£i n tt'I = ^(32e - 3e)(32e + 1) and IAHtt'I = ^(32e + 3e)(32e + l).
This allows us to solve for
m = ^(32e â€” 3e) and n = t(32' + 3').
Conjecture 5.6 For any e > l, there exist sets of type (Â§(32e â€” 3e), |(32e + 3e)) in AG(2, 32e).
Our hope is that, in the future, we will be able to prove that we have an infinite family of Cameron-Liebler line classes in PG(3, 32e which induce tactical decompositions of the space, allowing us to show the existence of these two-intersection sets.
55

APPENDIX A. Algorithms
Here we detail some of the algorithms that facilitate our findings.
A.l CLaut Matrix
â€¢ We have
â€” C is our cyclic group of order q2 + q + 1 whose orbits on Q+(5, q) \ {jii U 7t2) are represented by elements of ORep= {x : x G F*3 | T(x) = 0} (considered as an ordered set for consistency).
â€” Z\ = Aut(Fg3/Fp) and Z2 = F*; these groups, considered on Q+(5,q), normalize C, so we only consider their action on ORep). Z\ is assumed to stabilize our tight set but Z2 is not.
â€” XBLOCK and XO are the orbits of Z\ and Z2, respectively; the elements of each orbit are also ordered.
â€¢ Want to store, for each x gORep, indexed pairs and so that X =Xblock[/1] [/1]=XO[/2] [y2].
â€¢ We now form a set R such that, for each x gORep, we have a unique r eR such
k
that uolrp = x for some i, k.
â€¢ Form the structure S= [sr], where sr = [|(1, r)-1 fl (l,x)c| : x gORep].
â€¢ Form the array 01P, where 07P[/][y] =k, where k is such that gXblock[/c].
â€¢ Each row and column of our matrix A corresponds to an orbit on Q+(5,q) \ (iti U 7r2) under G =. We consider them to be ordered according to the ordering of the orbits XBLOCK of Z\. We find Aij as follows:
56

â€” Let a, b be such that (Wry EZi[i].
â€” Then Aij is formed by summing over sn[k\ as k ranges over the values satisfying 01P[a][k\=j.
In other words, for each Zi[i], we can find an x in Zi[i], an r in R, and an integer a such that x = u)ar. We know how many elements of (1, y)G are collinear with (1, r), so we consider how the map y iâ€”> ujay on ORep permutes the associated orbits of C, and consider which of these orbits have their representatives in Zi\j\, and add them up.
57

APPENDIX B. Programs
We have structured the code to examine tight sets of Q+(5,q) in a modular fashion. That is, we have a shell program that contains the parameters we may wish to modify, and from there we load the hies containing specific methods, and then call the specific functions we are interested in. Here is the code for our basic shell program; we comment out any parts we are not interested in before submitting the job to the cluster. Any restrictions for the parameters, either from the requirements of the algorithms or for the sake of computational speed, will be mentioned when we discuss the individual pieces of the code.
B.l CLshell.mgm
We have variables p, h, and t which can be modified; p does not need to be prime. The idea is that we will have q = ph, and / Au{Fpah/Fp) will be assumed to act on a f-tight set found by the search. We usually define t in terms of q, but we must take care that t is an integer, p := 81 ;
h ;= 1;
CLpreamble .mgm sets up our basic infrastructure, load â€œCLpreamble .mgmâ€; t := RationalsQ ! (1/2)*(g2 -1);
CLaut. mgm holds the basic search algorithm; when h = 1, it will find any of our examples having parameter t, although it is very slow. Using larger values of h (while leaving q fixed) makes things much faster, but will only find examples stabilized by this larger group.
Findl_(f, ~Z_);
58

CLbcirc.mgm is specialized for h = 1, p = 1 mod 4, and t = (1/2)(g2 â€” 1). It is very fast and memory efficient.
We have that L contains the set of orbit representatives for each tight set found, print â€œThere wereâ€, #L,
â€œline classes found with parameterâ€, f;
CLvspace.mgm contains definitions for the vector spaces V = E2, W = F6, and the map (f) : V â€”> W. This map uses a basis for W which gives the standard orthogonal form. The vector space U = FA is also defined, along with maps 5 : U â€”> W and 7 : W â€”> U which map a point to a line of PG(3, q) via the Klein correspondence, load â€œCLvspace.mgmâ€;
CLpg3q.mgm defines the function LU(), which maps a set of trace zero elements of E* to the set of lines of PG(3, q) corresponding to their orbits under C. Also defines the groups GL = PrL(4, q) and CU ~ C acting on lines of PG(3, q). load â€œCLpg3q.mgmâ€;
S := Stabilizer(GZ-, LU(L[1]));
print â€œThe stabilizer of L is as follows :\nâ€, S;
CLint.mgm is used to compute intersection numbers. The orbit representatives are expanded to the full pointset throuth LW(), and intersection numbers with stars and planes are computed using intPlane() and intStar(), respectively, load â€œCLint.mgmâ€;
LL := LW(L[1]);
print â€œThe intersection numbers (with multiplicity) of L with point stars of the space are as follows :\nâ€, intStar (Z_Z_);
print â€œThe intersection numbers with respect to
59

planes of the space are as follows :\nâ€, intPlane(LL);
CLint81.mgm gives an alternate way to compute intersection numbers. It is much slower, but more memory efficient. We use it for the case where p = 81, since the computations are impossible otherwise, load â€œCL8lint .mgmâ€;
print â€œThe intersection numbers (with multiplicity) of L with point stars of the space are as follows :\nâ€, i ntStar (LW (Z_ [1 ]));
print â€œThe intersection numbers with respect to planes of the space are as follows :\nâ€, intStar(LWd(L[1]));
MNset.mgm will give the intersection of the set in PG(3,q) with a plane piPrime as described in Chapter 5. The set K will also be given, which should be a two-intersection set of AG(2, q) when q = 32e. load â€œMNsetTH2 .mgmâ€;
K := MN(L[1]);
S := KStab(K');
print â€œThe stabilizer of K is as follows :\nâ€, S;
B.2 CLpreamble.mgm
This code is required for everything that follows.
We let F = Â¥q and E = Fg3, with primitive elements oj and a, respectively, and view V as E2, with bilinear form (x,y) T(xy), where T = Tr(E/F).
q := Ph\
A := (q2-1);
60

F := FiniteField(q) ; if not IsPrimitive(u;) then
uj := PrimitiveElement(F) ;
end if;
E := exf;
T := func;
It is useful to have these ordered. This ordering makes Fstar[i]= likewise
Estar[i]= aA+b
Fstar := {@ uj1 : i in [0.. q-2]@};
Estar := {@ a1 : i in [0. . q3-2]@};
H is a element of E with order r = q2 + q + I. jj, := a 1); r := q2 +q +1 ;
ORep is the set of nonzero elements with trace 0; fills the role of S in the thesis. ORep := {@ x: x in Estar\ T(x) eq 0
L is a placeholder sequence; it will contain subsets of ORep corresponding to f-tight sets of the quadric.
L := [POWERSET(OFep)|];
Instead of defining our cyclic group acting onk = E2, we define C to be a permutation group on Estar, generated by C.1: x e-> p * x.
C := PermutationGroup;
We define the group Z\= Aut(Â£,/Fp); to save memory, we define this group acting on just the trace zero elements ORep C Estar. This requires some consideration to the order in which we apply groups to look at orbits.
Gr := Sym(ORep);
Zi := sub;
61

0 := Zi.1;
The group Z2 generated by z : x e-> uj * x permutes the orbits of C; the orbits of this group on the trace zero elements of Estar are used to efficiently form the tactical decomposition.
Z2 := sub-, z := Z2.1 ;
B.3 CLaut.mgm
The method used here is the most general search technique. Forming the matrix for the tactical decomposition can be very computationally expensive.
Xblock â– = Orb its (Zi);
XO := Orbits(Z2) ; n := #Xblock]
The following record format is used to keep track of important information about the trace zero elements of Estar, such as their location in the cycles induced by specific group elements on representative trace zero elements. See Appendix A for details. TZero := recformat
01 : car<{i: i in [1 ..#Xblock]}, {/: j in [1.. (3*/))]}>,
02 : car<{i: i in [1..#XO]}, {/ : j in [1.. (qfâ€”1 )]}>>;
TZ := [rec : / in [1 ..#ORep]\;
for / in \t..#Xblock\ do
for j in \1 ,.#Xblock\i\\ do
7Z[lNDEx(0/:?ep, Xblock[i]\j])]'Oi := ; end for; end for;
for / in [1..#XO] do
62

for j in [1 ,.#XO[i]\ do
TZ[\NDEx(ORep, X0[i][j])]'02 := \ end for; end for;
It is efficient to sort the records according to the size of the orbit of the trace zero element under Zq we maintain separate sequences of the trace zero elements, and the records associated with them, each in the same order. The memory used to store this redundant information is made up for in the time saved accessing the information, forward m;
Sort(~7Z, func, ~m);
ORep := {@ ORep[im] : i in [1 ..#ORep\@};
For details on the formation of A, see Appendix A.
02block := {@{@ 7Z[/]'Oi[1]
: j in [Index(ORep, x) : x in XO[TZ[i\02[ 1]]]@}
: / in [1..#ORep] @};
R := {@ Index(ORep, Xblock]02block\i11111111) : / in [1 ..#02block]@};
Cy := [[Trace(E ! x, F) : x in Cycle(C.1, XO[i][ 1])] : / in [1..#XO]]; yC := [RoTATE(REVERSE(Cy[/]), 1): / in [1..#Cy]];
002 := [[Fsfar[x[2]]*yC[x[1]][/] : j in [1..#Cy[x[1]]]] where x := TZ[R[i]]'02 : / in [1..#/?]];
M2 := func | 002[i][k] + Fstar{x[2]\*Cy{x[\}\{k) eq 0 where x := TZ[y]'02}>;
S := [PowerSequence(Rationals())| ]; for / in [1 ..#R] do
s := [M2(/,_/) : j in [1 ..#ORep]]\
Append(~S, s);
63

end for;
01P := [ [TZ[\HDEx(ORep, x*0f?ep[/])]'0i[1]: j in [1 ..#ORep]]: x in Fstar]]
M := function(/,y)
d := exists(/c,s)
{ : m in [1..#R], n in [1 ..#Fstar]
| TZ[\NDEx(ORep, ORep[R[m]]*Fstar[n])]'Oi[1] eq i }; return &+[ S[/c][x] : x in [1 ..#01P[s]] \ 01P[s][x] eq j]; end function;
A := SymmetricMatrix(Rationals(), &caf[[M(/',y) :/' in [1..y]] : y in [1.. /?]])
- ScalarMatrix(Rationals(), n, 1);
This loop adjusts the values of the matrix if the orbits are not all the same size, which occurs when q = 0 mod 3 or when 3 divides h. s := [#Xblock[i] : i in \1..#Xblock\ \; for / in [1.. (nâ€” 1)] do
for y in [(/+1).. n\ do
A[i,j\ := A[i,j\/(s\j\/s[i})] end for; end for;
We now find the eigenspace for A, and define a function FindL() which will search for a tight set with a given parameter t and return the sets of orbit representatives (trace zero elements of Estar) corresponding to any tight sets found.
Ba := Basis(Eigenspace(/\, A));
FindL := procedure^, ~Z.)
p := RationalsQ ! t/(q2 -1); e := (1 â€”p); f := -p;
64

Since the basis vectors for the eigenspace for A are normalized, a vector with all entries equal to e or / must be a linear combination of these basis vectors with all weights equal to e or /; we search over all such linear combinations for tight sets, for c in CartesianPower({0, 1}, #Ba) do
s := [ (c[i] eq 1) select e else f . i in [1..#6a]]; v := &+[s[/'] * Ba[i] : i in [1..#6a]]; if forall{/:/ in [1.. n\ \ v[i] in {e, f}} then
Append(~Z_, &join{Xblock[i]: i in [1.. n] \ v[i] eq e}); print v\
end if; end for; end procedure;
B.4 CLbcirc.mgm
This code searches for tight sets of Q+(5,q) as described in Chapter 4 when q = 1 mod 4, by forming a block circulant matrix for the tactical decomposition. The requirements for the parameters in the shell are as follows:
p= 1 mod 4,
e = 1, and
t = Rationals((l/2) * (q2 â€” 1)).
We must also have loaded the CLpreamble.mgm hie.
We define the subgroup Z3= (z4) Z3 := sub;
Xblock contains the orbits on the trace zero elements under ( Z\, Z3 ). We order these orbits according to whether loga x = 0,1, 2, 3 mod 4, as described in Chapter 4.
65

This way, XO[/][/c] is the orbit given by u/fc ^ * X0[/][1] for 1 < k < 4, where X0[/][1] is an orbit containing elements with loga x = 0 mod 4.
Xblock := ORB\Js(sub); n := #Xblock]
Sort Xblock, func);
SoRT(~Xb/oc/c, func);
XO := {@ Xblock[i]Z2 : i in [1.. n]@}; n := n div 4;
The following algorithm is used to generate the matrix corresponding to the tactical decomposition of Q+(5,q) induced by the group ( C, Zl5 Z3 ); see the details in Appendix A.
Cy := [[[Trace(E ! x, F) : x in Cycle(C.1, y)\ : y in XO[/'][1]] : / in [1..#XO]];
002 := [R0TATE(REVERSE(Cy[/'][1]), 1) : / in [1../?]];
M := func | 002[/] [z] + Fsfar[/f]*Cy[/][x][z] eq 0}
: x in [l..#Cy[/]] ] >;
Ablock â– = [ SymmetricMatrix
(RationalsQ, &caf[[M(/,y,/c): / in [1..y]] : y in [1.. /?]])
: k in [1.. 3] ]; if ((q mod 3) eq 0) then
s := 3;
for / in [1.. 3] do
for j in [2.. n\ do
Abiock[i)[\, j) := Ab/oc/c[/][1,y']/s; end for; end for;
66

end if;
Ab!ock[\] := Ab!ock[\] - ScalarMatrix(Rationals(), n, 1);
Ablock[4] := Ablock[2];
The eigenvectors of the block symmetric matrix are now constructed over the cy-clotomic held R[(\ :=Q[z]. We are only interested in real valued eigenvectors. For these examples, for all values of q which are feasible computationally, we get a onedimensional eigenspace of H[1] = Ablock[]]â€”Ablock[3], giving eigenvectors which correspond to (1/2)(g2 â€” l)-tight sets (in essentially four equivalent ways).
R<(> := CyclotomicField(4) ;
H := [&+[( h[ 1];
v := Basis(Eigenspace(H[1], (q2 â€”1 )))[1];
A := HORIZONTALjOIN([VERTICALjOIN([/4b/OC/c[1 + ((/-_/) mod 4)]
: / in [0.. 3]]) : j in [0.. 3]]);
This loop puts together a set of the orbit representatives for each of the four f-tight sets. (Need some explanation of the method, which is based on conjecture.) The sequence L consists of a sequence of sets of orbit representatives, each corresponding to a f-tight set.
p â– = RationalsQ ! t/(q2 -1); e := (1 â€”p); f := -p;
Sp := &.cat([[ : k in [1../7]]: j in [1..4]]); v := Vector([Rationals() | (IntegersQ ! Ablock[2] [/, 1 ] mod 2) - p
: / in [1.. n]]);
for c in CartesianPower({1,2}, 2) do
u := Vector(&caf([ Eltseq(((-1)c[1])*i/),
67

ELTSEQ(((-1)c[2])*l/),
ELTSEQ(((-1) (c[1]+1))*i/),
Eltseq(((-1 ) (c[2]+1))*i/)]));
if (u*A eq A*u) then
Append(~Z_, &join{XO[Sp[i] [2]] [Sp[/] [1 ]]
: i in \1..#Xblock\ \ u[i] eq e});
print u\
end if; end for;
B.5 CLvspace.mgm
This code includes definitions of various vector spaces, as well as maps to implement the Klein correspondence. It is required for all of the code in the proceeding sections.
We begin by defining our vector spaces V and W, and our bilinear form.
V := VectorSpace(E, 2);
1/1/, (p := VectorSpace(V, F);
B := func;
Q := func;
BW := func\
QW := func;
OForm := Matrix(F, [[BW(Basis(I/I/)[/], Basis(I/I/)[/])
: / in [1 â€¢ â€¢ 6]]: j in [1..6]]);
We now find a basis for W under which we can use the standard Plucker coordinates for the Klein correspondence.
Ba := [Basis(l/l/)[1 ]];
68

Ba := AppEND(Ba,a) where a := rep{x. x in W
| QW(x) eq 0 and BW(Ba[1], x) ne 0};
for / in [1.. 3] do
Ba[2*/'â€”1] := (BW(Ba[2*/â€”1], Ba[2*/]))(_1)*8a[2*/-1];
8a[2*/] := QW(Ba[2*/'])*Ba[2*/'-1] + Ba[2*/']; if (/' ne 3) then
Ba := AppEND(Ba, a)
where a := rep{x : x in Nullspace
(OForm*TRANSPOSE(MATRix([Ba[/c] : k in [1--2 */]])))
| x ne 0 and QW(x) eq 0};
Ba := AppEND(Ba, a)
where a := rep{x : x in Nullspace
(OForm*TRANSPOSE(MATRix([Ba[/c] : k in [1--2 */]])))
| x ne 0 and QW(x) eq 0
and BW(Ba[2*/'+1],x) ne 0};
end if; end for;
Ba := [Ba[1], Ba[3], Ba[5], Ba[6], Ba[4], Ba[2]];
WBa := (Matrix(F, 6, 6, Ba))(â€œ1);
We redefine to map V â€”> W in such a way that we can use the standard orthogonal form for the quadric.
(f) := map(v)*WBa, w ((f)~ 1)(w*l/l/Baâ€”1)>;
WForm â– = Matrix(F, [[BW(Ba[/], Ba[/]): / in [1..6]] : y in [1.. 6]]);
BW := func;
QW := func;
We now define the vector space U which will underlie PG(3,q); 5 : U â€”>â–  W and 7 : W U give the Klein correspondence.
69

U := VectorSpace(F, 4);
8 := func [â€”x[1], 0, x[4], â€”x[5]],
[â€”x[2], â€”x[4], 0, x[6]],
[â€”x[3], x[5], â€”x[6], 0]]))>;
pK := func [[Basis (//ne) [1 ] [/+1 ], BASis(//ne) [1 ] [/c+1 ]], [Basis (//ne) [2] [y+1 ], Basis (line) [2] [/c+1 ]]]))>;
7 := func [pK(line, 0, 1), pK(line, 0, 2), pK(line, 0, 3), pK(line, 1, 2), pK(line, 3, 1), pK(line, 2, 3)]>)[1]>;
B.6 CLpg3q.mgm
This code requires CLvspace.mgm in order to run.
We set up the group acting on PG(3, q), and itâ€™s action on the lines.
G, P := PGammaL(L/) ;
PointsU := func {Index(P, N0RMALiZE(BASis(//'ne)[2]))} join {Index(P, N0RMALiZE(BASis(//'ne)[1] + x* Basis (line) [2])) : x in F}>;
Lines := PointsU(sub)G;
Lines := GSet(G, Lines)-, p, GL := Action(G, Lines)]
Here we define the action of our cyclic group on PG(3, q).
CU := (p~'[)(sub [ y[1] ne 0 select i/[1]c-1 else 0, v[2] ne 0 select i/[2]c-_1 else 0])))
70

where v is (4>~'[){rj{sub)) where / is rep{ : a, b in Lines[i] \ a ne b}
: i in [1 ..#Lines]]>)m,
The function LU() maps our orbit representatives to a set of lines in PG(3,q).
LU := func; B.7 CLint.mgm
This code requires CLvspace.mgm in order to run.
H, N := PG0Plus(I/1/) ;
Hprime := Subgroups(H : IndexEqual := 2)[1 ]'subgroup-,
CW := sub where z is (4>~ 1)(x) : x in A/]>;
LW := func< L | &y'o//7{ Index(/V, Normalize(0(1/ ! [1,x])))cw : x in L} intStar := function(l/1/CZ.)
7ti := { Index(/V, Normalize(0(1/ ! [x,0]))) : x in Estar };
Stars := TTi HPrime ;
return {* #(WCL meet tt) : ir in Stars*}-, end function;
intPlane := function(l/l/C/.)
7t2 := { Index(/V, Normalize(0(1/ ! [0,y]))) : y in Estar };
Planes := 7r2HPrime;
return {* #(WCL meet ir) : ir in Planes*}-, end function;
B.8 CL81int.mgm

This code requires CLvspace.mgm in order to run.
G, P := PGammaL(LZ) ;
aC := \pLk : k in [1.. r]];
Ca := FtEVERSE(aC);
ROTATE(~aC, 1);
CW := func;
ULines := Parent(^(0(1/ ! [1, ORep[\]])*WBa))m,
LW := function(/./:?ep)
/./.:=[ ULines |]; for x in LRep do
for v in CW(x) do
Append(~LL, 5(4>(v)))m, end for; end for; return /_/_;
end function;
LWd := function(LRep)
/./.:=[ ULines |]; for x in LRep do
for v in CW(x) do
Append(~LL, \[v[2], i^[1 ]])));
end for; end for; return /_/_;
end function;
72

intStar := function(UCL)
INT := {* IntegersQ| *}; for x in P do
xINT := #{v : v in UCL \ x in v}]
Include(~/A/7, xINT) ; end for; return !NT\ end function;
intPlane := function (UCL)
INT := {* Integers()| *};
Nv := [Nullspace(Transpose(Matrix([Basis(i/)[1], Basis(ix)[2]]))) : v in UCL];
for x in P do
xINT := #{/' : / in [1..#Nv] | x in Nv[/']};
Include(~/A/7, xINT) ; end for; return INT] end function;
B.9 MNset.mgm
This code requires CLvspace.mgm in order to run. aC := \p,k : k in [1.. r]];
Ca := FtEVERSE(aC);
RoTATE(~aC, 1);
CW := func;
ULines := Parent(5((V ! [1, ORep[\]])*WBa))i
73

7r := Nullspace(Transpose(Matrix(L/ ! [1,0,0,0]))); piW â– = sub),
â€/(sub),
â€/(sub)>;
LWpi := function(Z-Bep)
/./.:=[ ULines |]; for x in LRep do
for v in CW(x) do
if v in piW then
Append(~Z_Z_, 8(v))m,
end if; end for; end for; return /_/_; end function;
MN := function(UCL)
UCLpi := LWpi (UCL)]
I := {x : x in 7T |
#{v : v in UCLpi \ x in v} eq (#UCLpi div (g+1))};
/ := sub< 7T | / >;
Bp := ExtendBasis(/, 7r);
Bp := [Bp[3], Bp[1], Bp[2]];
H,N := PGL(3, q);
mn â– = {* #{v : v in UCLpi \ x in v} : x in ir*}; m := MiN(mn);
74

K := {NORMALIZE(
Vector(F, Coordinates(VectorSpaceWith Basis (Bp), x))) : x in 7r \#{v : v in UCLpi \ x in v} eq m};
K := {[x [2], x[3]] : x in K}\ return K ; end function;
KStab := function(mnSef)
H, J := AGammaL(2,q) ;
K := {Index(J, x) : x in mnSet}]
S := Stabilizer(/-/, K); return S; end function;
75

REFERENCES
[1] S. Ball, A. Blokhuis, and F. Mazzocca. Maximal arcs in desarguesian planes of odd order do not exist. Combinatorica, 17:31-41, 1997. 10.1007/BF01196129.
[2] J. Bamberg, S. Kelly, M. Law, and T. Penttila. Tight sets and m-ovoids of finite polar spaces. Journal of Combinatorial Theory, Series A, 114(7): 1293â€”1314, 2007.
[3] J. Bamberg, M. Law, and T. Penttila. Tight sets and m-ovoids of generalised quadrangles. Combinatorica, 29(1):1â€”17, 2009.
[4] W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput., 24(3-4):235-265, 1997. Computational algebra and number theory (London, 1993).
[5] A.A. Bruen and K. Drudge. On the non-existence of certain Cameron-Liebler line classes in PG(3,q). Designs, Codes and Cryptography, 14(2): 127â€”132, 1998.
[6] A.A. Bruen and K. Drudge. The construction of Cameron-Liebler line classes in PG(3,q). Finite Fields and Their Applications, 5(1):35â€”45, 1999.
[7] R. Calderbank and W. M. Kantor. The geometry of two-weight codes. Bulletin of the London Mathematical Society, 18(2):97â€”122, 1986.
[8] P.J. Cameron and R.A. Liebler. Tactical decompositions and orbits of projective groups. Linear Algebra and its Applications, 46:91-102, 1982.
[9] J. De Beule, P. Govaerts, A. Hallez, and L. Storme. Tight sets, weighted recovers, weighted m-ovoids, and minihypers. Designs, Codes and Cryptography, 50(2): 187â€”201, 2009.
[10] J. De Beule, A. Hallez, and L. Storme. A non-existence result on Cameron-Liebler line classes. Journal of Combinatorial Designs, 16(4):342 349, 2008.
[11] R.H.F. Denniston. Some maximal arcs in finite projective planes. Journal of Combinatorial Theory, 6(3):317 â€” 319, 1969.
[12] K. Drudge. Extremal sets in projective and polar spaces. PhD thesis, University of Western Ontario, 1998.
[13] K. Drudge. On a conjecture of Cameron and Liebler. European Journal of Combinatorics, 20(4):263-269, 1999.
[14] P. Govaerts and T. Penttila. Cameron-Liebler line classes in PG(3,4). Bulletin of the Belgian Mathematical Society - Simon Stevin, 12(5):793â€”804, 2005.
76

[15] P. Govaerts and L. Storme. On Cameron-Liebler line classes. Advances in Geometry, 4(3):279-286, 2004.
[16] L.C. Grove. Classical Groups and Geometric Algebra. American Mathematical Society, 2002.
[17] W.H. Haemers. Interlacing eigenvalues and graphs. Linear Algebra and its Applications, 226-228(0):593 - 616, 1995.
[18] J. Hirschfeld. Projective Geometries over Finite Fields (Oxford Mathematical Monographs). Oxford University Press, USA, 2 edition, 1998.
[19] D. R. Hughes and F. C. Piper. Projective Planes. Springer-Verlag New York,, 1973.
[20] R. Lidl and H. Niederreiter. Finite Fields (Encyclopedia of Mathematics and its Applications). Cambridge University Press, 1996.
[21] R. Mathon. New maximal arcs in desarguesian planes. Journal of Combinatorial Theory, Series A, 97(2):353 - 368, 2002.
[22] K. Metsch. The non-existence of Cameron-Liebler line classes with parameter 2 < x < q. Bulletin of the London Mathematical Society, 42(6):991-996, 2010.
[23] W.F. Orr. The Miquelian inversive plane IP(g) and the associated projective planes. PhD thesis, University of Wisconsin, 1973.
[24] S. Payne. Tight pointsets in finite generalized quadrangles. Congressus Numer-antiurn, 60:243-260, 1987.
[25] S. Payne. Topics in Finite Geometry: Ovals, Ovoids, and Generalized Quadrangles. UC Denver Course Notes, 2009. For a draft version, see http://math.ucdenver.edu/~spayne/classnotes/topics.pdf.
[26] S. Payne and J. Thas. Finite Generalized Quadrangles. European Mathematical Society, 2nd edition, 2009.
[27] T. Penttila. Cameron-Liebler line classes in PG(3,q). Geometriae Dedicata, 37(3):245-252, 1991.
[28] T. Penttila and G.F. Royle. Sets of type (m, n) in the affine and projective planes of order nine. Designs, Codes and Cryptography, 6(3) :229â€”245, 1995.
[29] T. Penttila and B. Williams. Regular packings of PG(3,g). European Journal of Combinatorics, 19(6):713 - 720, 1998.
[30] G. Tee. Eigenvectors of block circulant and alternating circulant matrices. New Zealand Journal of Mathematics, 36:195-211, 2007.
77

[31] J. Thas. Construction of maximal arcs and partial geometries. Geornetriae Dedicata, 3:61-64, 1974.
[32] J. Thas. Construction of maximal arcs and dual ovals in translation planes. European Journal of Combinatorics, 1:189-192, 1980.
[33] J. Tits. Buildings of Spherical Type and Finite BN-pairs. Springer-Verlag, 1974.
78

Full Text

PAGE 1

PAGE 2

ThisthesisfortheDoctorofPhilosophydegreeby MorganJ.Rodgers hasbeenapproved by StanleyE.Payne,AdvisorandChair WilliamCherowitzo TimothyPenttila DianaWhite JasonWilliford Date ii

PAGE 3

Rodgers,MorganJ.Ph.D.,AppliedMathematics OnsomenewexamplesofCameron-Lieblerlineclasses ThesisdirectedbyProfessorStanleyE.Payne ABSTRACT Cameron-LieblerlineclassesaresetsoflinesinPG ;q havingmanynicecombinatorialproperties;amongthem,aCameron-Lieblerlineclass L sharesprecisely x lineswithanyspreadofthespaceforsomenon-negativeinteger x ,calledthe parameteroftheset.Theseobjectswereoriginallystudiedasgeneralizationsof symmetrictacticaldecompositionsofPG ;q ,aswellasofsubgroupsofPL ;q havingequallymanyorbitsonpointsandlinesofPG ;q .Theyhaveconnectionsto manyothercombinatorialobjects,includingblockingsetsinPG ;q ,certainerrorcorrectingcodes,andstronglyregulargraphs. WeconstructmanynewexamplesofCameron-Lieblerlineclasses,eachstabilized byacyclicgroupoforder q 2 + q +1havingasemi-regularactiononthelines.In particular,newexamplesareconstructedinPG ;q havingparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 13.037 0 Td [(1 forallvaluesof q 5or9mod12with q< 200;withparameter 1 3 q +1 2 found incollaborationwithJandeBeule,KlausMetsch,andJeroenSchillewaertforall valuesof q 2mod3with2
PAGE 4

Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:StanleyE.Payne iv

PAGE 5

ACKNOWLEDGMENTS Thisthesiswouldnothavebeenpossiblewithoutthehelpofmanypeople.I owepartofmysuccessasagraduatestudenttoeverymemberofmycommittee, andIwouldliketothankthemallfortheirtimeandsupport.Inparticular,I wouldliketothankmyadvisorStanPayne,whosededicationtomathematicshas trulybeeninspiring,andTimPenttila,whogenerouslysuggestedthisproblemto workon.Tim'shelpinlearningtoprogramwithMagmawastrulyindispensiblein conductingthisresearch,andhealsobroughtafewkeyarticlestomyattentionthat wereinstrumentalinllinginsomedetailsofthiswork.BillCherowitzohasalso oeredconstantsupportandassistance;mostnotably,heconvincedthedepartment togivemeanocetoworkinwhenIwasarstyearstudentwithnootherformof departmentalsupport.Muchofthecomputationalworkinvolvedinthisthesiswas doneontheUniversityofWyomingcluster,andIthankJasonWillifordforgoingout ofhiswaytosetmeupwiththisaccess.Mysurvivalinacademiawouldhavebeen muchmoredicultwithoutthehelpandadviceofthesepeopleandmanyothers, especiallyDianaWhite,MikeFerrara,andOscarVega. IalsowouldliketothanktheBatemanfamilyfortheirnancialsupportofthe mathematicsdepartment;Ihavebeenfortunatetoreceivethreesemestersofsupport fromtheLynnBatemanMemorialFellowship,andthecompletionofthisresearch wouldhavebeenmuchmoredicultwithouttherelieffromteachingdutiesthis provided.IwouldliketoextendthankstoJandeBeuleandtheUniversiteitGent aswellforsupportingmeasavisitingresearcher.Partoftheworkofthisthesis wasconductedduringthattrip,incollaborationwithJan,KlausMetsch,andJeroen Schillewaert. Mostimportantly,Ithankmylovingwifewhohasneverlostfaithinmyability tosucceed,evenwhenIquestioneditmyself.Shehelpedmorethansheknows;I denitelywouldnothavenishedthisthesiswithouthersupport. v

PAGE 6

TABLEOFCONTENTS Tables........................................viii Chapter 1.Introduction...................................1 1.1Overview.................................1 1.2Finiteelds................................2 1.3TheprojectivegeometryPG n;q ...................4 1.4Collineationsanddualities.......................5 1.5CombinatoricsofPG n;q .......................7 1.6Bilinearandquadraticforms......................9 1.7Orthogonalityandtotallyisotropicsubspaces.............10 1.8OrthogonalpolarspacesinPG n;q ..................11 1.9 Q + ;q andtheKleincorrespondence.................14 2.Cameron-Lieblerlineclasses..........................18 2.1Denitionsandhistory.........................18 2.2Tightsetsof Q + ;q ..........................19 2.3Two-intersectionsets,two-weightcodes,andstronglyregulargraphs21 2.4Trivialexamples.............................23 2.5Non-existenceresults..........................24 2.6Knownexamples.............................26 2.6.1BruenandDrudgeexamples...................26 2.6.2PenttilaandGovaertsexampleinPG ; 4...........27 3.Methodology...................................30 3.1Aneigenvectormethodfortightsets..................30 3.2TacticalDecompositions.........................31 3.3Amodelof Q + ;q ...........................33 3.4Thegeneralmethod...........................34 vi

PAGE 7

4.Newexamples..................................36 4.1Newexampleswithparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1................37 4.1.1Theconstruction.........................37 4.1.2Somedetailsoftheseexamples.................41 4.2Newexampleswithparameter 1 3 q +1 2 ................43 4.3Someothernewexamples........................44 5.Planartwo-intersectionsets..........................46 5.1Projectiveexamples...........................46 5.2Aneexamples.............................48 5.3ConstructionsfromCameron-Lieblerlineclasses...........50 5.3.1Atwo-intersectionsetinAG ; 9................50 5.3.2Anewtwo-intersectionsetinAG ; 81............52 5.3.3AfamilyofexamplesinAG ; 3 2 e ?..............53 Appendix A.Algorithms....................................56 A.1CLautMatrix..............................56 B.Programs....................................58 B.1CLshell.mgm...............................58 B.2CLpreamble.mgm............................60 B.3CLaut.mgm...............................62 B.4CLbcirc.mgm...............................65 B.5CLvspace.mgm..............................68 B.6CLpg3q.mgm...............................70 B.7CLint.mgm................................71 B.8CL81int.mgm..............................72 B.9MNset.mgm...............................73 References ......................................76 vii

PAGE 8

TABLES Table 4.1 ParametersandautomorphismgroupsofthenewexamplesofCameronLieblerlineclassesconstructed. .......................36 4.2 Intersectionnumbersoflineclasseswithparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 13.132 0 Td [(1 withthe planesof PG ;q . ..............................42 4.3 Intersectionnumbersoflineclasseswithparameter 1 3 q +1 2 withthe planesof PG ;q . ..............................44 4.4 Intersectionnumbersofsomeothernewlineclasses. ...........45 5.1 Linesperpointforthesymmetrictacticaldecompositioninducedon PG ; 9 byaCameron-Lieblerlineclassofparameter 40 . ........51 5.2 Pointsperlineforthesymmetrictacticaldecompositioninducedon PG ; 9 byaCameron-Lieblerlineclassofparameter 40 . .............51 5.3 Linesperpointforthesymmetrictacticaldecompositioninducedon PG ; 81 byaCameron-Lieblerlineclassofparameter 3280 . ......53 5.4 Pointsperlineforthesymmetrictacticaldecompositioninducedon PG ; 81 byaCameron-Lieblerlineclassofparameter 3280 . ............53 viii

PAGE 9

1.Introduction 1.1Overview ThefocusofthisdissertationistoconstructnewexamplesofCameron-Liebler lineclassesadmittingacertaincyclicautomorphismgroup.Theselineclasseshave manydierentcharacterizations.Mostnotably,aCameron-Lieblerlineclass L hasthe propertythat,forsomeinteger x calledthe parameter , L sharesprecisely x lineswith everyspreadofthespace.Cameron-Lieblerlineclassesarealsoofinteresttoother areasofmathematicsincludinggrouptheoryandcodingtheory.Thesesetsoflines wereoriginallystudiedinrelationtoagrouptheoryproblemregardingcollineation groupsofPG ;q havingthesamenumberoforbitsonpointsandonlines.They alsoserveasgeneralizationsofthenotionofasymmetrictacticaldecomposition ofPG ;q ;i.e.,atacticaldecompositionhavingthesamenumberofpointclasses andlineclasses.ThroughtheKleincorrespondence,aCameron-Lieblerlineclassis equivalenttoasetofpointsofthehyperbolicquadric Q + ;q calleda tightset .Tight setsofthisquadricoftendeterminetwo-intersectionsetsoftheunderlyingprojective spacePG ;q ,thatis,setsofpointshavingtwointersectionnumberswithrespect tohyperplanes.Two-intersectionsetscanthenbeusedtoconstructerrorcorrecting codeswithcodewordshavingpreciselytwononzeroweightswhich,inturn,giverise toexamplesofstronglyregulargraphs. AfterreviewingthegeometryofPG ;q and Q + ;q ,aswellastheirrelationshipthroughtheKleincorrespondence,wesurveytheknownresultsonCameronLieblerlineclasses,includingtheknownexamplesaswellassomenon-existence results.Weshowtheequivalenceoftheseobjectswithtightsetsof Q + ;q andgive resultsonwhenthesesetsdeterminetwo-intersectionsetsoftheunderlyingPG ;q . Wealsolookattheconstructionoftwo-weightcodesandstronglyregulargraphs fromthesetwo-intersectionsets.Oncewehavedevelopedthisbackgroundmaterial, wedeveloptoolswhichareusedtoconstructnewexamples.Themaintoolsare 1

PAGE 10

aneigenvectormethodforndingtightsetsandresultsontacticaldecompositions whichfacilitatethismethod.Sinceweareprimarilyworkingfromthepointofview of Q + ;q ,analgebraicmodelforthisspaceisintroduced.Thisallowsustogive aconcisenotationforacyclicgroupoforder q 2 + q +1actingsemi-regularlyonthe space,whichiscontainedinthestabilizerofeachnewexampleconstructed. WeusethetoolswedeveloptoconstructseveralnewexamplesofCameronLieblerlineclassesinPG ;q ,includingmanyhavingparameters 1 2 q 2 )]TJ/F15 11.9552 Tf 13.099 0 Td [(1and 1 3 q +1 2 .WealsodescribeotherexamplesinPG ; 27andPG ; 32.Forallofthese newexamples,wedetailstructuralinformationsuchasautomorphismgroupsand intersectionnumberswithplanesofPG ;q ,aswellastherelatedtwo-intersection setsofPG ;q ,two-weightcodes,andstronglyregulargraphs.Furthermore,when q =9or81,thenewexampleswithparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 12.93 0 Td [(1arelinepartitionsofa symmetrictacticaldecompositionofPG ;q havingfourpartsonpointsandonlines; wegiveaconstructionfromthisdecompositionoftwo-intersectionsetsinAG ;q . Fewexamplesoftwo-intersectionsetsofoddorderaneplanesareknown;infact, theonlypreviouslyknownexamplesareinplanesoforder9.Thus,ourexamplein AG ; 81isnew. 1.2Finiteelds Aniteeldalwayshasorder q = p e ,where p isaprime.Thiseld,whichis uniqueuptoisomorphism,willbedenoted F q andhas characteristic p ;i.e., P p i =1 x =0 forevery x 2 F q and p isthesmallestintegerforwhichthisistrue.Themultiplicativegroup F q ofnonzeroelementsof F q isacyclicgroupoforder q )]TJ/F15 11.9552 Tf 12.208 0 Td [(1;anelement 2 F q havingorder q )]TJ/F15 11.9552 Tf 12.487 0 Td [(1iscalleda primitiveelement ,and h i = F q forsuchan element. Let K = F q ,where q = p h .Asubset F of K whichisalsoaeldunderthe sameoperationsiscalleda subeld of K ;wewrite F K . K containsaunique subeldisomorphicto F p e foreach e dividing h ,consistingof f a 2 K : a p e = a g .The 2

PAGE 11

intersectionofallsubeldsof K iscalledthe primesubeld of K andisisomorphic to F p .Wecanconstructalargereld E = F q d from K byconsideringanirreducible polynomial f x in K [ x ]ofdegree d ;inthiscase E = K [ x ] = f x = f a 0 + a 1 x + ::: + a d )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 x d )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 j a i 2 K;f x =0 g isaniteeldoforder q d containing K asasubeld.Wesaythat E isan extension eld of K . Amap : F q ! F q iscalledan automorphism of F q if isapermutationof theelementssuchthat x + y = x + y ,and xy = x y forall x , y in F q . WewriteAut F q forthegroupofautomorphismsof F q .If q = p e , p prime,then Aut F q iscyclic,isomorphicto Z e ,andisgeneratedbythe Frobeniusautomorphism : x 7! x p . Let q = p e , F = F q ,and K = F q h with F K ;thenAut K=F ,thegroup ofautomorphismsof K xingeveryelementof F ,hasorder h andisgeneratedby e : x 7! x p e = x q .Wedenethe relativetracemapfrom K to F ,T K=F : K 7! F ,by T K=F a = X 2 Aut K=F a = a + a q + a q 2 + ::: + a q h )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 . Thismaphasthefollowingproperties: 1.T K=F a + b =T K=F a +T K=F b forall a;b 2 K . 2.T K=F ca = c T K=F a forall c 2 F , a 2 K . 3.T K=F a = ha forall a 2 F . 4.T K=F a =T K=F a forall a 2 K andforall 2 Aut K=F . Noticethatthersttwoitemsimplythat,if K isviewedasavectorspaceover F ,thenT K=F isalineartransformationfrom K to F .Weactuallyhavemore;the mapT K=F maps K onto F ,andinfact,everylinearmapfrom K into F takesthe form L b a =T K=F ba forsome b 2 K . 3

PAGE 12

1.3Theprojectivegeometry PG n;q Muchofthismaterialistreatedthoroughlyin[25]orin[18].Therearealso examplesofprojectiveplaneswhicharenotoftheformPG ;q ;fordetailsonthese examples,see[19]. Denition1.1 Let F = F q beaniteeldoforder q and V beavectorspaceof dimension n +1 over F .Wedenethegeometry PG n;q asfollows: Theone-dimensionalvectorsubspacesof V arethepointsof PG n;q . The d +1 -dimensionalvectorsubspacesof V arethe d -dimensionalsubspaces of PG n;q . Incidenceisdenedintermsofcontainmentofthecorrespondingvectorsubspaces. Theworddimension"isusedintwowayswithadierentmeaning;whenitisnot clearwhichwemeanfromcontext,wewillspecify projective dimensionwhenwe aretalkingaboutthedimensioninPG n;q ,or vectorspace dimensionwhenwe aretalkingaboutasubspaceof V .Thisdenitionofaprojectivespaceallowsus toassociatevectorsin V withpointsofPG n;q ;namely,anonzerovector v 2 V representsapointofPG n;q ,withnonzerovectors v , w representingthesamepoint ifandonlyif v = c w forsome c 2 F . WewillcallasubspaceofPG n;q havingdimension n )]TJ/F15 11.9552 Tf 12.69 0 Td [(1a hyperplane ;the setofpointsonahyperplanecanbedescribedasthosesatisfyingahomogeneous linearequation.Wewritethecoecientstheequationdescribingahyperplane H as h =[ x 0 ;:::;x n ],withtheconventionthatapoint u isin H ifandonlyif uh T =0. Wewillspeakofasetofpointsorofhyperplanesasbeing linearlyindependent ifthe correspondingvectorsarelinearlyindependentinthevectorspace. Itisfrequentlyusefultodescribeasubspace U ofPG n;q aseithertheintersectionorthespanofothersubspaces.Giventwosubspaces U 1 and U 2 ofPG n;q ,the 4

PAGE 13

intersection U 1 U 2 isagainasubspaceofPG n;q .Wedenethe span of U 1 and U 2 tobethesmallestsubspaceofPG n;q containingboth U 1 and U 2 ;wedenotethis by h U 1 ;U 2 i .Ingeneral,theprojectivedimensionof h U 1 ;U 2 i isgivenby dim h U 1 ;U 2 i =dim U 1 +dim U 2 )]TJ/F15 11.9552 Tf 11.956 0 Td [(dim U 1 U 2 . Thespanoftwodistinctpoints,forexample,isthelinecontainingbothofthem. Givenasubspace U ofdimension d andahyperplane H ,wehavethat U H is eitherequalto U ,orhasdimension d )]TJ/F15 11.9552 Tf 12.687 0 Td [(1.Thuswecandescribea d -dimensional subspace U ofPG n;q aseitherthespanof d +1linearlyindependentpoints,oras theintersectionof n )]TJ/F19 11.9552 Tf 12.369 0 Td [(d linearlyindependenthyperplanes.If h 1 ;:::; h n )]TJ/F20 7.9701 Tf 6.587 0 Td [(d arethe vectorscontainingthecoecientsoftheequationsforthesehyperplanes,thenwecan associate U withtheleftnullspaceofthematrix h T 1 ::: h T n )]TJ/F20 7.9701 Tf 6.586 0 Td [(d . 1.4Collineationsanddualities AbijectiononthepointsofPG n;q whichpreservesthelinesiscalleda collineation ;thatis,amap :PG n;q ! PG n;q suchthatforalllines ` of PG n;q ,theimage ` isalsoalineofPG n;q .Thisnecessarilyimpliesthatany d -dimensionalsubspaceofPG n;q getsmappedby toanother d -dimensionalsubspace.SinceweviewthesubspacesofPG n;q ascorrespondingtosubspacesofan n +1-dimensionalvectorspace V over F q ,wecandescribeacollineationofPG n;q intermsofitsactionon V .Inparticular,anymatrix A 2 GL n +1 ;q canbeused todeneacollineation L A : x 7! x A ofPG n;q .Collineationsofthistypearecalled homographies .Notethat,forany 2 F q ,thematrices A and A denethesame maponPG n;q ;wesaythesetwomapsare projectivelyequivalent .Thegroup PGL n +1 ;q = GL n +1 ;q =Z GL n +1 ;q 5

PAGE 14

iscalledthe projectivelineargroup ,andactsfaithfullyonPG n;q .Itisworthnoting that,forahyperplane H representedby h andamatrix A 2 PGL n +1 ;q ,wehave that x 2 H ifandonlyif x A A )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 h T =0 ; sothehyperplane H getsmappedby L A toanewhyperplanedenedby A )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 h T .Automorphismsof F q alsogiveexamplesof collineationsofPG n;q .Given 2 Aut F q ,themaponPG n;q inducedby : V ! V : x 0 ;:::;x n 7! x 0 ;:::;x n iscalledan automorphiccollineation . TheFundamentalTheoremofProjectiveGeometrytellsusthatanycollineation ofPG n;q canbeobtainedbycomposinganautomorphiccollineationwithahomography.Suchamapisoftheform L A : x 7! L A x = x A; where 2 Aut F q and A 2 PGL n +1 ;q ,andiscalleda projectivesemilinear map. Thegroupofthesemapsisdenoted P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L n +1 ;q = PGL n +1 ;q o Aut F q : Associatedwithaprojectivegeometry S istheso-called dualgeometry S ;this geometry'spointsandhyperplanesare,respectively,thehyperplanesandpointsof S .AprojectivegeometryoftheformPG n;q isisomorphictoitsdualgeometry, andwecallanisomorphismfromthepointsofPG n;q ontothehyperplanesa reciprocity .Oneimportantexampleisthemapsendingapoint x tothehyperplane determinedby x T .ByourearliercommentsabouttheFundamentalTheoremof ProjectiveGeometry,anyreciprocitycanbewrittenintheform x ! x A T ,where 2 Aut F q and A 2 PGL n +1 ;q .Ifwehaveareciprocity thatisaninvolution, thatis,if 2 =1,thenwecall a polarity . 1.5Combinatoricsof PG n;q 6

PAGE 15

Theorem1.2 [18]In PG n;q ,thereare q n +1 )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 points, q n +1 )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 q n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 2 q +1 lines,and Q n +1 i = n )]TJ/F21 5.9776 Tf 5.756 0 Td [(d +1 q i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 Q r +1 i =1 q i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 d -dimensionalsubspaces. Given d
PAGE 16

ThegroupsactingonPG ;q are PGL ;q and P )]TJ/F19 11.9552 Tf 7.315 0 Td [(L ;q ;if q = p e ,theorders oftheseare PGL ;q hasorder q 6 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q 4 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1and P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L ;q hasorder eq 6 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q 4 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1. Aset R of q +1mutuallyskewlinesinPG ;q iscalleda regulus provided 1.througheverypointofeverylineof R thereisatransversalofthelinesof R thatis,alinemeetingeachofthelinesof R ;and, 2.througheverypointofeverytransversalthereisalineof R . Itisclearthatthesetoftransversalsof R isalsoareguluswhichwecall R opp ,the opposite regulusof R .AnythreeskewlinesinPG ;q determineauniqueregulus. A spread ofPG ;q isasetof q 2 +1linesofthespacethatpartitionsthepoints.A spread S iscalled regular if,givenanythreeskewlinesin S ,theregulusdeterminedby thosethreelinesisalsocontainedin S .Spreadscanbedenedinhigherdimensional spacesaswell,andareofconsiderableinterest,astheycanbeusedtoconstruct examplesofprojectiveplanes.Theirclassicationisanimportantprobleminnite geometrythatisbeyondthescopeofthisthesis. A k -arc K ofPG ;q oranyprojectiveplaneoforder q isasetof k pointssuch thatnothreearecollinear.Thusanyline ` ofPG ;q meets K in0,1,or2points; wecalltheselines external , tangent ,or secant to K respectively.A k -arcmusthave k q +2.A k -arc K whichisnotcontainedinany k +1-arciscalled maximal .A q +1-arciscalledan oval ,andif q isodd,any q +1-arcismaximal.However,if q iseven,everytangentlinetoanoval K passesthroughacommonpoint N which wecallthe nucleus of K .Inthissituation, K[f N g isa q +2-arc,whichwecall a hyperoval .Givenaplane embeddedinPG ;q containinganovalorhyperoval O ,andapoint p notin ,wedenea cone over O tobethesetofpointsonthe 8

PAGE 17

linesjoining p topointsof O .Thelinesarecalledthe generators ofthecone,and p iscalledthe vertex ofthecone. 1.6Bilinearandquadraticforms Let V beavectorspaceofdimension n +1over F = F q A bilinearform on V is afunctionB: V V ! F thatislinearineachargument;thatis, B a u + v ; w = a B u ; w +B v ; w and B u ;a v + w = a B u ; v +B u ; w forall u ; v ; w 2 V andall a 2 F . AbilinearformBissaidtobe symmetric ifB u ; v =B v ; u forall u ; v 2 V , and alternating ifB u ; u =0forall u 2 V .Wearestrictlyinterestedin reexive bilinearforms,thatis,thoseforwhichB u ; v =0impliesB v ; u =0.Every reexivebilinearformiseithersymmetricoralternating. A quadraticform onavectorspace V isamap Q : V ! F denedbyahomogeneousdegree2polynomialinthecoordinatesof V relativetosomebasis.Equivalently, wecall Q : V ! F aquadraticformif Q a u = a 2 Q u forall a 2 F and u 2 V and B: u ; v 7! Q u + v )]TJ/F19 11.9552 Tf 11.955 0 Td [(Q u )]TJ/F19 11.9552 Tf 11.955 0 Td [(Q v givesabilinearformon V . ItisclearthatBissymmetricif q isoddandalternatingif q iseven.Thisassociated bilinearform,B,iscalledthe polarform of Q .Avectorspaceequippedwitha quadraticformiscalledan orthogonalspace . GivenabilinearformBandanorderedbasis B = f v 0 ;:::; v n g for V ,weput b ij =B v i ; v j .The Grammatrixrelativeto B isthendenedby ^ B =[ b ij ].This matrixhasthepropertythat,if[ u ] B and[ v ] B arecoordinatevectorsof u and v relativeto B ,thenB u ; v =[ u ] B ^ B[ v ] T B .AnytwoGrammatricesofabilinearform Bhavethesamerank,whichwedenetobethe rank ofB.If Q isaquadraticform 9

PAGE 18

on V ,wedenetheuppertriangularmatrix A = a ij ,where a ij = 8 > > > > < > > > > : B v i ; v j , ij . Wethenhavethat Q u =[ u ] B A [ u ] T B ,andtheGrammatrixforthepolarformof Q withrespectto B isthen ^ B = A + A T . 1.7Orthogonalityandtotallyisotropicsubspaces LetBbeareexivebilinearformonPG n;q .Wedenean orthogonality relationshiponthepointsofPG n;q by u ? v ifB u ; v =0.If S V ,wedene S perp"tobe S ? = f v 2 V j v ? s 8 s 2 S g : Apoint v ofPG n;q iscalled singular withrespecttoabilinearformBif v ? = V ; itiscalled singular withrespecttoaquadraticform Q ifitissingularwithrespect totheassociatedbilinearformand Q v =0.WesayBor Q is degenerate ifthereis asingularpoint,and nondegenerate otherwise. Weplaceaspecialsignicanceonpoints v forwhichB v ; v = 0 or Q v =0. Suchapoint v iscalled isotropic withrespecttotobilinearformBorthequadratic form Q ,respectively.Wecallasubspace W of V isotropicifitcontainsanisotropic point, anisotropic otherwise,and totallyisotropic ifB u ; v =0forall u ; v 2 W for abilinearform,orif Q v =0forall v 2 W foraquadraticform.Ifasubspaceis totallyisotropicwithrespecttoaquadraticform Q ,thenitisalsototallyisotropic withrespecttotheassociatedbilinearform,thoughtheconverseonlyholdsif q is odd.ThesetofisotropicpointsinPG n;q withrespecttoanondegeneratequadratic formiscalleda quadric ,andhasthepropertythatanylineofPG n;q containing morethantwopointsofaquadricmustbecompletelycontainedinthequadric. IfBisnondegenerateform,theorthogonalityrelationcanbeusedtodenea polarity : U 7! U ? ofPG n;q .Inthiscase,if U and W aresubspacesof V with 10

PAGE 19

U W ,then W ? U ? ;furthermore,foranysubspace U of V ,dim U +dim U ? = dim V .Apoint x issaidtobe isotropic withrespecttothepolarityif x x ? ,anda subspace U issaidtobe totallyisotropic withrespecttothepolarityif U U ? .This isinagreementwiththenotionsofbeingisotropicortotallyisotropicwithrespectto thebilinearform.When q isodd,thepolarformofanondegeneratequadraticform isnecessarilynondegenerate.Thusinthiscasethenotionsofbeingtotallyisotropic withrespecttothequadraticform,thebilinearform,andtheassociatedpolarityall agree. Thesituationismorecomplicatedwhen q iseven,sinceitispossibleforthe polarformof Q tobedegenerateevenwhen Q isnondegenerate.Inthiscase,we donothaveapolarityassociatedwiththequadraticform.EvenifthepolarformB of Q isnondegenerate,wehaveB u ; u =0forevery u 2 PG n;q ,so every point ofPG n;q isincidentwithitsimageundertheinducedpolaritysuchapolarityis calleda nullpolarity .Thusthesetofpointswhichareisotropicwithrespecttothis polaritydoesnotagreewiththesetofpointswhichareisotropicwithrespecttothe quadraticform. 1.8Orthogonalpolarspacesin PG n;q Denition1.4 A polarspaceofrank r isanincidencegeometryconsistingofaset ofpoints,lines,projectiveplanes,..., r )]TJ/F15 11.9552 Tf 12.798 0 Td [(1 -dimensionalprojectivespacescalled subspaces suchthat 1.Anytwosubspacesintersectinasubspace. 2.If U isasubspaceofdimension r )]TJ/F15 11.9552 Tf 10.359 0 Td [(1 and p isapointnotin U ,thereisaunique subspace W containing p with U W havingdimension r )]TJ/F15 11.9552 Tf 11.639 0 Td [(2 ;itconsistsofall pointsof U whicharejoinedto p bysomeline. 3.Therearetwodisjointsubspacesofdimension r )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 . 11

PAGE 20

The r )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 -dimensionalsubspacesarecalled maximals ofthepolarspace. The niteclassicalpolarspaces aretheexamplesnaturallyembeddedinaprojective spacePG n;q ;theyaredenedbyanondegeneratequadraticorsesquilinearform onthespace.AresultofTits[33]provedthatanypolarspacewithrankatleast 3isclassical.Rank2polarspacesareaspecialcase.Theyarecalledgeneralized quadrangles,andtherearenonclassicalexamplesofthese;see[26]foradetailed treatment. Let F = F q ,and V bea n +1-dimensionalvectorspaceover F .Take Q tobe anondegeneratequadraticformon V withpolarformB.Thegeometryconsisting ofthetotallyisotropicsubspacesofPG n;q withrespectto Q isanexampleofa classicalpolarspace;wecallanexamplearisinginthiswayan orthogonalpolarspace . Note: Wehavenowintroducedthreeverycloselyrelatedterms,an orthogonal space ,a quadric ,andan orthogonalpolarspace . Thevectorspace V alongwithanondegeneratequadraticformisan orthogonalspace . ThesetofisotropicpointsofPG n;q withrespecttothequadraticformis calleda quadric . Thegeometryoftotallyisotropicsubspaceswithrespecttothequadraticform iscalledan orthogonalpolarspace ,inthiscontextthepolarspacecaneither beconsideredasembeddedinPG n;q orasageometryinitsownright. ThemostgeneralcollineationofPG n;q preservingaquadriciscalleda semisimilarity ;thisisamap suchthat,forsome a 2 F q andsome 2 Aut F q , Q x = a Q x . Wecall a similarity if =1,andwecall an isometry if a =1and =1.The followingimportanttheoremisknownasWitt'sExtensionTheorem: 12

PAGE 21

Theorem1.5 If U , W V ,and : U ! W anisometry,thenthereisanisometry : V ! V suchthat j U = . Corollary1.6 Anytwomaximalsof V havethesamedimension. Thevectorspacedimensionofamaximaliscalledthe Wittindex ofthepolarspace. TheWittindexofanondegenerateformislessthanorequalto 1 2 dim V ,sincea totallyisotropicsubspace W iscontainedin W ? . Wedenetwodistinctpoints u , v ofthequadrictobea hyperbolicpair if B u ; v =1.Wethencall h u ; v i a hyperbolicline .NotethatthisisalineofPG n;q containingpreciselytwopointsofthequadric. Theorem1.7 AnynondegenerateorthogonalspaceofWittindex r over F q isisometrictooneofthefollowing: 1.Ahyperbolicquadric Q + r )]TJ/F15 11.9552 Tf 12.029 0 Td [(1 ;q istheorthogonaldirectsumof r hyperbolic lines. 2.Aparabolicquadric Q r;q istheorthogonaldirectsumof r hyperboliclines andaone-dimensionalanisotropicspace.Thesefallintotwoisometryclasses andonesimilarityclasswhen q isodd,andoneisometryclasswhen q iseven. 3.Anellipticquadric Q )]TJ/F15 11.9552 Tf 7.085 -4.339 Td [( r +1 ;q istheorthogonaldirectsumof r hyperbolic linesandatwo-dimensionalanisotropicspace. Thegroupofisometriesof Q + r )]TJ/F15 11.9552 Tf 9.414 0 Td [(1 ;q , Q r;q ,or Q )]TJ/F15 11.9552 Tf 7.085 -4.339 Td [( r +1 ;q isdenoted O + r;q , O r +1 ;q ,or O )]TJ/F15 11.9552 Tf 7.085 -4.339 Td [( r +2 ;q ,respectively.Fortheprojectiveversionsofthesegroups, weprexthiswith P , PG ,or P )-488(dependingonwhetherwewantthegroupof isometries,similarities,orsemi-similarities,respectively. Ifwehaveasetofpoints O inapolarspacesuchthateverymaximalofthepolar spacemeets O inauniquepoint,thenwecall O an ovoid ofthepolarspace.The 13

PAGE 22

classicationofovoidsinclassicalpolarspacesisanimportantopenprobleminnite geometry;weareprimarilyinterestedintheseobjectsbecauseofhowtheyinteract withotherobjectsinthespace. 1.9 Q + ;q andtheKleincorrespondence The5-dimensionalhyperbolicorthogonalspace Q + ;q playsanimportantrole, asthisgeometryiscloselyrelatedtoPG ;q .Thisquadricismadeupoftheorthogonaldirectsumofthreehyperboliclines,andthestandardassociatedquadratic formisgivenby Q : x 0 ;x 1 ;x 2 ;x 3 ;x 4 ;x 5 7! x 0 x 1 + x 2 x 3 + x 4 x 5 ; whichisdescribedbythematrix A = 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 010000 000000 000100 000000 000001 000000 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 . TheGrammatrixforthepolarformBwithrespecttothestandardbasisisthen ^ B = A + A T . Anotherwaytothinkofthestructureofthispolarspaceisgivenbytaking onepointfromeachofthethreehyperbolicpairs.Sincethehyperboliclinesthey determinearepairwiseorthogonal,thesethreepointsarealsopairwiseorthogonal andsospanatotallyisotropicplane 1 ,necessarilyamaximalofthepolarspace. Thethreeremainingpointsfromthehyperbolicpairsthenspanatotallyisotropic plane 2 whichisdisjointfrom 1 . ThegeometriesPG ;q and Q + ;q arecloselyrelatedthroughamapping knownasthe Kleincorrespondence .ThisreferstoabijectionfromthelinesofPG ;q 14

PAGE 23

tothepointsof Q + ;q suchthattwolinesofPG ;q intersectifandonlyiftheir imagesarecollinearin Q + ;q .Todenethebijection,wewillrstestablishaway todescribelinesofPG ;q using Pluckercoordinates .Let x = x 0 ;x 1 ;x 2 ;x 3 and y = y 0 ;y 1 ;y 2 ;y 3 bedistinctpointsonaline ` ofPG ;q .Dene G ` = p 01 ;p 23 ;p 02 ;p 31 ;p 03 ;p 12 ,where p ij = x i x j y i y j for0 i
PAGE 24

Corollary1.9 Thesetoflinesinaspreadof PG ;q correspondtoanovoidof Q + ;q . Corollary1.10 Let ` and ` 0 betwoconcurrentlinesin PG ;q withcorresponding points L and L 0 in Q + ;q .Thenthelinesoftheatpenciloflinesin PG ;q determinedby ` and ` 0 correspondtothelineof Q + ;q through L and L 0 .Conversely, eachlineof Q + ;q correspondstoasetoflinesin PG ;q lyinginaatpencil. Corollary1.11 Thesetofpointsinatotallyisotropicplaneof Q + ;q corresponds toasetof q 2 + q +1 linesin PG ;q ,anytwoofwhichareconcurrent.Thus,they correspondtoeitherthesetoflinesthroughacommonpoint p ,denotedstar p ,or thesetoflinesinacommonplane ,denotedline . Wecallatotallyisotropicplaneof Q + ;q a Latinplane ifitcorrespondstostar p forsomepoint p 2 PG ;q ,anda Greekplane ifitcorrespondstoline forsome plane ofPG ;q . Corollary1.12 Anytwodistinctplanesofthesametypein Q + ;q intersectina 0 -dimensionalsubspaceasinglepoint.Anytwoplanesofdierenttypesareeither disjoint,ormeetinalineof Q + ;q .Thustwoplanesareofthesametypeifand onlyiftheirintersectionhasevendimension. Thesecorrespondencesallowustocountthefollowing: Corollary1.13 Q + ;q contains 1. q 2 +1 q 2 + q +1 points; 2. q 3 + q 2 + q +1 q 2 + q +1 lines; 3. 2 q 3 + q 2 + q +1 planes; 4. q q +1 2 pointscollineartoagivenpoint; 16

PAGE 25

5. q +1 2 linescontainingagivenpoint; 6. 2 q +1 planescontainingagivenpoint; 7. 2 planescontainingagivenline. TheKleincorrespondencealsogivesusaconnectionbetweenthegroups P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L ;q actingonPG ;q and P )]TJ/F19 11.9552 Tf 7.314 0 Td [(O + ;q actingon Q + ;q .Specically,anyelementof P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L ;q inducesanactiononthepointsof Q + ;q preservingcollinearity,andso P )]TJ/F19 11.9552 Tf 7.314 0 Td [(O + ;q hasasubgroupisomorphicto P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L ;q .Anymapon Q + ;q arising inthisfashionmapsGreekplanestoGreekplanesandLatinplanestoLatinplanes. AnycorrelationofPG ;q sendslinestolines,andsoalsoinducesanactiononthe pointsof Q + ;q preservingcollinearity.Amaparisinginthisfashioninterchanges theGreekandLatinplanes.Theseareknowntobetheonlyautomorphismsof Q + ;q . Theorem1.14 Thestructureoftheprojectivesimilarityandsemi-similaritygroups of Q + ;q areasfollows: PGO + ;q ' PGL ;q oZ 2 . P )]TJ/F19 11.9552 Tf 7.314 0 Td [(O + ;q ' P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L ;q oZ 2 . UsingthisconnectionbetweenthelinesofPG ;q andthepointsof Q + ;q canbehelpful,especiallywhendealingwithcombinatoricsofsetsoflinesinPG ;q . Inadditiontohavingmanytheoreticalresultstoapply,itismorecomputationally convenienttodealwithsetsofpoints.Forthisreason,muchofourworkinthisthesis isdoneinthecontextof Q + ;q . 17

PAGE 26

2.Cameron-Lieblerlineclasses Inthischapter,wewillsurveymanyoftheknownresultsonCameron-Lieblerline classes.Thisincludesnon-existenceresults,knownconstructions,andadiscussionof theimagesoftheselinesetsin Q + ;q undertheKleincorrespondence. 2.1Denitionsandhistory HerewedetailsetsoflinesinPG ;q havingsomespecialcombinatorialproperties.ThesesetsoflineswereoriginallystudiedbyCameronandLiebler[8],who calledthemspecial"lineclasses,inconnectionwiththestudyofcollineationgroups ofPG ;q havingthesamenumberoforbitsonpointsandlines.Suchagroup inducesasymmetrictacticaldecompositionoftheincidencestructureofpointsand linesinPG ;q ,andtheyshowedthatalineclassfromsuchadecompositionhas niceintersectionpropertieswithrespecttoreguliandspreadsofthespace.They abstractedtheconceptofsetsoflineswiththeseproperties,hopingitwouldlead totheclassicationofsymmetrictacticaldecompositionsandcollineationgroupsof PG ;q withthisorbitstructure.However,thisproblemprovedinterestingina moregeneralsettingthanoriginallyenvisioned. Denition2.1 Let A bethepoint-lineincidencematrixof PG ;q withrespectto someorderingofthepointsandlines,andlet L beasetoflinesin PG ;q with characteristicvector = L .Wewillwrite ` fortheentryof corresponding totheline ` .Thefollowingstatementsareallequivalent;iftheyhold, L iscalleda Cameron-Lieblerlineclass[8],[27]. 1. L 2 row A . 2. L 2 null A T ? 3. jRLj = jR opp Lj foreveryregulus R anditsopposite R opp . 4.Thereexists x 2 Z + suchthat jLSj = x foreveryspread S . 18

PAGE 27

5.Thereexists x 2 Z + suchthat jLSj = x forevery regular spread S . 6.Thereexists x 2 Z + suchthat,foreveryincidentpoint-planepair p; , j star p Lj + j line Lj = x + q +1 j pencil p; Lj . 7.Thereexists x 2 Z + suchthat,foreveryline ` in PG ;q , jf lines m 2L meeting `;m 6 = ` gj = x q +1+ q 2 +1 ` . 8.Thereexists x 2 Z + suchthat,foreverypair ` , m ofskewlinesin PG ;q , jf n 2L : n isatransversalto `;m gj = x + q [ ` + m ] . Thevalue x mustsatisfy0 x q 2 +1,andwillnecessarilybethesameineach instance;wecall x the parameter ofthelineclass.If L isaCameron-Lieblerlineclass withparameter x ,then jLj = x q 2 + q +1.Thecomplement L 0 ofaCameron-Liebler lineclass L withparameter x isalsoaCameron-Lieblerlineclasshavingparameter q 2 +1 )]TJ/F19 11.9552 Tf 10.711 0 Td [(x ,andtheunionoftwodisjointCameron-Lieblerlineclasseswithparameters x 1 and x 2 isaCameron-Lieblerlineclasswithparameter x 1 + x 2 .ACameron-Liebler lineclassissaidtobe irreducible ifitdoesnotproperlycontainanyotherlineclass asasubset. 2.2Tightsetsof Q + ;q ToinvestigatetheexistenceofCameron-Lieblerlineclasses,itisfrequentlyuseful totranslatetheirdenitiontothesettingof Q + ;q usingtheKleincorrespondence. Inthiscontext,part7ofDenition2.1hasanespeciallyinterestinginterpretation; L isaCameron-Lieblerlineclassifandonlyifitsimage M in Q + ;q hasthefollowing property: Thereexists x 2 Z + suchthat,foreverypoint p in Q + ;q , j p ? M j = x q +1+ q 2 p , where = M isthecharacteristicvectorof M . 19

PAGE 28

Denition2.2 Let S beapolarspaceofrank r 3 over F q .Thenaset T ofpoints in S isan x -tightset ifforallpoints p 2S j p ? Tj = 8 > < > : x q r )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 + q r )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 if p 2T x q r )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 if p 62T Adaptingthisdenitionfortherank3polarspace Q + ;q ,weseethataCameronLieblerlineclasswithparameter x isequivalenttoan x -tightsetof Q + ;q . Pointsetsinpolarspaceshavingpreciselytwointersectionnumberswithrespect toperpsofpointsarecalled intriguing byBamberg,Kelly,LawandPenttila[2].There aretwotypesofintriguingsetsinnitepolarspaces,andtheycanbecharacterizedin termsoftheirintersectionnumbers.If I isanintriguingsetofapolarspacehaving intersectionnumbers h 1 forperpsofpointsinside I and h 2 forperpsofpointsoutside I ,then I isatightsetif h 1 >h 2 .Atightsetofpointsinanitepolarspacecan alsobedenedasasetofpoints T suchthateachpointofthespaceis,onaverage, collinearwithasmanypointsin T aspossible.Thesesetswereoriginallystudied ingeneralizedquadranglesbyPayne[24]andtheirdenitionwaslaterextendedto moregeneralpolarspacesbyDrudge[12].Anintriguingsetwith h 1
PAGE 29

3.Thereexists x 2 Z + suchthat j M j = x q 2 + q +1 ,everytangenthyperplane to Q + ;q atapointof M meets M in q 2 + x q +1 points,andeveryother hyperplaneof PG ;q meets M in x q +1 points. 4.Thereexists x 2 Z + suchthat j ` ? M j = q j ` M j + x foreveryline ` of PG ;q . 5.Thereexists x 2 Z + suchthat j ` ? M j = q j ` M j + x foreveryline ` ofone ofthefourlinetypesin PG ;q external,tangent,secant,totallyisotropic. Itisimportanttonotethatthelastthreecharacterizationsarestrongerthantheir relatedversionsinPG ;q .Part3inparticularstatesthat,inadditiontoknowing theintersectionnumbersfortangenthyperplanesof Q + ;q ,wealsoknowthatevery nontangenthyperplanesectionof Q + ;q meetsan x -tightsetin x q +1points. Thispropertyisimportantenoughthatwestateitonitsown,asitwillbeusedin thenextsectiontoconstructrelatedcombinatorialobjects. Theorem2.4 Let T beaproper x -tightsetof Q + ;q thatspanstheambientprojectivespace.Thenthesetofpointscoveredby T hastwointersectionnumberswith respecttohyperplanesof PG ;q .Thesenumbersare h 1 = q 2 +1+ x q +1 and h 2 = x q +1 : 2.3Two-intersectionsets,two-weightcodes,andstronglyregulargraphs Tightsetsof Q + ;q arerelatedtomanyothercombinatorialobjects;herewe investigatesomepropertiesoftheseobjects. Denition2.5 Asetofpoints S of PG n;q iscalleda two-intersectionset with intersectionnumbers h 1 and h 2 ifeveryhyperplaneof PG n;q intersects S ineither h 1 or h 2 points.Suchasetisalsosometimescalleda setoftype h 1 ;h 2 . 21

PAGE 30

Fromtheprevioustheorem,an x -tightsetof Q + ;q whosepointsspanPG ;q is atwo-intersectionsetofPG ;q .Thesesetsarerelatedtoawiderangeofother combinatorialobjects.Webeginbydetailingresultsonanimportantclassoflinear codes. An[ n;k ] q code C isa k -dimensionalsubspaceofthevectorspace V = F n q .Vectors in C arecalled codewords ,andthe weight wt v ofacodeword v isthenumberof nonzeroentriesof v .A two-weightcode C isacodewhosecodewordshaveprecisely twononzeroweights.Givenacode C ,wedenethe dualcode C ? = f v 2 V j vc T =0 8 c 2 C g : Wehavethat C ? isan[ n;n )]TJ/F19 11.9552 Tf 11.955 0 Td [(k ] q code. Let C bean[ n;k ] q code;thereexistlinearfunctionals f i : F k q ! F q suchthat C = f f 1 v ;:::;f n v : v 2 F k q g .Since u ; v 7! uv T isanondegeneratebilinear form,thereexist u 1 , ::: , u n 2 F k q suchthat f i v = vu T i forall v 2 F k q .Thus,we havethat C = f vu T 1 ;:::; vu T n j v 2 V g ,andsincedim C = k ,the u i span F k q . Wesay C is projective ifnotwoofthe u i representthesamepointinPG k )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 ;q . Let V nf 0 g .Wesayisa f 1 ; 2 g dierenceset if,forevery v 2 V nf 0 g , thenumberofpairs x ; y 2 2 suchthat x )]TJ/F34 11.9552 Tf 11.979 0 Td [(y = v is 1 if v 2 ,and 2 if v 62 . If )]TJ/F15 11.9552 Tf 9.299 0 Td [(=,wedeneagraph G whoseverticesarethevectorsin V ,with u and v adjacentifandonlyif u )]TJ/F34 11.9552 Tf 11.955 0 Td [(v 2 . Denition2.6 A stronglyregulargraph withparameters v;k;; isaconnected k -regularsimple,undirectedgraphon v vertices,notnullorcomplete,suchthatany twoadjacentverticesshare commonneighbors,andanytwononadjacentvertices share commonneighbors. Wenowgivearesultconnectingtheconceptsoftwointersectionsets,two-weight codes, f 1 ; 2 g dierencesets,andstronglyregulargraphsduetoCalderbankand Kantor[7]. 22

PAGE 31

Theorem2.7 Let V = F n +1 q , O = f y i j 1 i r g beasetofvectorswhichspan V so r n +1 andarepairwiseindependent,andlet = f cy i j c 2 F q g bethesetof nonzeroscalarmultiplesofthe y i ;thenthefollowingstatementsareequivalent: 1. O isasetoftype r )]TJ/F19 11.9552 Tf 11.955 0 Td [(w 1 ;r )]TJ/F19 11.9552 Tf 11.955 0 Td [(w 2 in PG n;q forsome w 1 , w 2 ; 2. C = f x y 1 ;:::;x y k j x 2 V g isaprojectivetwo-weight [ r;n +1] q codewith nonzeroweights w 1 and w 2 ; 3. isa f 1 ; 2 g dierencesetforsome 1 , 2 ; 4. G isastronglyregulargraphwithparameters q n +1 ;r q )]TJ/F15 11.9552 Tf 10.788 0 Td [(1 ;; ,wherefor some w 1 , w 2 wehave = r 2 q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 2 +3 r q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(qw 1 w 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(r q )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 w 1 + w 2 + q 2 w 1 + w 2 and = q 2 w 1 w 2 q n +1 : Thismeansthatif L = f y 1 ;:::;y x q 2 + q +1 g isan x -tightsetof Q + ;q which spansPG ;q ,then 1. L isasetoftype q 2 +1+ x q +1 ;x q +1inPG ;q ; 2.thepointsof L deneaprojectivetwo-weight[ x q 2 + q +1 ; 6] q codewithweights q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1and xq 2 ; 3.= f cy i j c 2 F q g isa f 1 ; 2 g dierencesetforsome 1 , 2 ;and 4. G isstronglyregularwithparameters q 6 ;x q 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ;x x )]TJ/F15 11.9552 Tf 11.955 0 Td [(3+ q 3 ;x x )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : 2.4Trivialexamples Thereareafewexampleswhichtriviallysatisfythenecessaryrequirementstobe aCameron-Lieblerlineclass. 23

PAGE 32

1.Theemptyset ; isaCameron-Lieblerlineclasswithparameter0. 2.Thesetstar p oflinesthroughacommonpoint p ofPG ;q isaCameronLieblerlineclasswithparameter1correspondingtoa1-tightsetof Q + ;q consistingofthesetofpointsinaLatinplane. 3.Thesetline oflinesinaplane ofPG ;q isaCameron-Lieblerlineclass withparameter1correspondingtoa1-tightsetof Q + ;q consistingofthe setofpointsinaGreekplanethisisequivalenttothepreviousexamplein Q + ;q . 4.Thesetstar p [ line ,where isaplaneofPG ;q and p isapointnotin , isaCameron-Lieblerlineclasswithparameter2correspondingtoa2-tightset of Q + ;q whichisaunionoftwodisjointplanesoneLatinandoneGreek. 5.ThecomplementsoftheabovesetsareCameron-Lieblerlineclasseswithparameters q 2 +1, q 2 , q 2 , q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1respectively. WecalltheCameron-Lieblerlineclassesinthislist trivial . 2.5Non-existenceresults CameronandLieblerconjecturedthattherewerenonontrivialexamplesofthese lineclasses,andprovedthisconjectureforclasseswithparameter 2.Manyother resultsfollowed,leadingtosomeinterestingconnectionswithvariousgeometricobjects. Manyoftheearlynon-existenceresultsreliedstrictlyoncountingarguments; specically,wecanthinkofsetsofthetypestar p orline forapoint p ora line asbeingessentiallythesame,andrefertotheseas cliques .Theequivalent denitionsforaCameron-Lieblerlineclassallowustoperformsomeanalysisonthe potentialintersectionnumberswithrespecttocliquesofahypotheticallineclass withagivenparameter x .Usingthesearguments,Penttila[27]wasabletoruleout 24

PAGE 33

severalparametersinspeciccases,andBruenandDrudge[5]wereabletoruleout theexistenceoflineclasseswithparameter2 2andsomeclique C has x< jLCj x + q then LC formsa blocking set in C inthiscontext,asetoflinesnotcontaininganypencil,suchthatevery pointisonatleastoneofthelines;thenormaldenitionisdualtothis.Blocking setsarewellstudied,andtherearemanyresultsontheirminimumpossiblesize. Thisgivesapowerfultoolforinvestigatingthefeasibilityofcertainparametersfor Cameron-Lieblerlineclasses.Drudgeusedthismethodtoruleoutthecasewhere 2
PAGE 34

sectaparabolic Q ;q embeddedinthequadric.Hewasabletousethistechnique toshowthefollowing: Theorem2.8 ACameron-Lieblerlineclass L withparameter x q existsonlyfor x 2 ,andcorrespondsin Q + ;q totheunionof x skewplanes. Thisshowsthatanynontrivialexamplemusthaveparameter q
PAGE 35

linesofPG ;q ,whichisthenumberoflinesinaCameron-Lieblerlineclasswith parameter 1 2 q 2 +1.Thegoalistoselectthesets L p insuchawaythat L isinfact aCameron-Lieblerlineclass. EveryplaneofPG ;q iseithertangentto O ,andsocontainsauniquepointof O ,orelseintersects O inaconic.Thenontangentplanesectionsof O canbeused toassociatethepointsandnontangentplanesectionsof O withpointsandcirclesof theinversiveplaneIP q [23],sothateachcircleofIP q correspondstoasection of O byanontangentplane containing q +1tangentlinesto O .An intersecting pencil ofcirclesisthesetof q +1circlesthroughtwocommonpointsofIP q ,and a tangentpencil ofcirclesisamaximalsetof q mutuallytangentcirclesonagiven pointofIP q . Anequivalencerelation canbedenedonthecirclesofIP q by C 1 C 2 9C suchthat C istangenttoboth C 1 and C 2 . ThecirclesofIP q fallintopreciselytwoequivalenceclassesunderthisrelation accordingtowhether Q ? isasquareornonsquare,where istheplanecontaining thecircleinquestion.Let A beoneoftheseequivalenceclasses; A containsexactly 1 2 ofthecirclesineachintersectingpencilandeitherallornoneofthecirclesineach tangentpencil.Thusifwedene L p tobethesetoftangentlinesat p containedina planesectionwhichcorrespondstoacirclein A , L p contains 1 2 q +1ofthetangent linesto O at p . BruenandDrudgeshowthat L isaCameron-Lieblerlineclasswithparameter 1 2 q 2 +1byshowingthesetoflinesin L hasacertainmatching"propertywith respecttotheexternallinesto O whicharetheintersectionoftwotangentplanes. 2.6.2PenttilaandGovaertsexamplein PG ; 4 AnotherknownexampleofanontrivialCameron-LieblerwasconstructedbyPenttilaandGovaerts[14].ThisisanexampleinPG ; 4withparameter x =7,and 27

PAGE 36

wastherstknownnontrivialexamplewhen q iseven.Sofartherehasnotbeena generalizationofthisconstruction. Let beaplaneinPG ; 4containingahyperoval O andlet p beapointnot in .Dene C tobetheconewithbase O andvertex p ,with G thesetofgenerators of C , S thesetofsecantsto C whichdonotcontainapointof O ,and E thesetof linesin whichareexternalto O . Theorem2.9 Theset L = G [ S [ E isaCameron-Lieblerlineclasswithparameter 7 . Proof: ThereareseventypesoflinesinPG ; 4withrespecttothecone C and thedistinguishedplane containing O . 1.Generatorsof C ;thisistheset G L . 2.Secantsto C whichareskewto O ;thisistheset S L . 3.Linesin whichareskewto O ;thisistheset E L . 4.Linesthrough p notcontainedin C . 5.Secantsto C whichmeetasinglepointof O . 6.Secantsto O . 7.Linesskewto C whicharenotcontainedin . Thepointsareof5types.Herewecountthenumberoflinesofeachtypethrougha pointofeachtype. 1. f p g ;ofthe21linesthrough p ,6areoftype1,and15areoftype4. 2.Pointson Cn f p g[ ;ofthe21linesthroughsuchapoint,1isoftype1,15 areoftype2,and5areoftype5. 28

PAGE 37

3.Pointson O ;ofthe21linesthroughsuchapoint,1isoftype1,15areoftype 5,and5areoftype6. 4.Pointson nO ;ofthe21linesthroughsuchapoint,9areoftype2,2areof type3,1isoftype4,3areoftype6,and6areoftype7. 5.PointsonPG ; 4 n C[ ;ofthe21linesonsuchapoint,9areoftype2,1 isoftype4,6areoftype5,and5areoftype7. Fromthis,wecancountthatalinein L meets50otherlinesof L ,andalinenotin L meets35linesof L .Thus L isaCameron-Lieblerlineclasswithparameter7. Unfortunatelythisconstructiondoesnotgeneralizetoothervaluesof q inany obviousway,aswedonotgetthecorrectnumberoflinesforaCameron-Lieblerline classunless q =4. 29

PAGE 38

3.Methodology Herewedescribesomealgebraictechniqueswhichwewillusetosearchfornew examplesofCameron-LieblerlineclassesofPG ;q .Wewillsearchfortheseas tightsetsof Q + ;q ;assuch,wewilldevelopamodelofthisquadricwhichwillbe convenientforourcomputationalwork. 3.1Aneigenvectormethodfortightsets OursearchfornewCameron-Lieblerlineclasseswillbeconductedinthecontext ofsearchingfornew x -tightsetsof Q + ;q .Aneigenvectormethodwillbeusedto searchfortheseobjects,whichisduetothefollowingresultofBamberg,Kelly,Law andPenttila[2]. Theorem3.1 Let L beasetofpointsin Q + ;q withcharacteristicvector and let A bethecollinearitymatrixof Q + ;q .Then L isan x -tightsetifandonlyif )]TJ/F19 11.9552 Tf 25.136 8.088 Td [(x q 2 +1 j A = q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F19 11.9552 Tf 25.135 8.088 Td [(x q 2 +1 j , where j istheall-onesvector. Proof: Bydenition, L isan x -tightsetifandonlyif,for p 2L , p iscollinearwith q 2 )]TJ/F15 11.9552 Tf 10.99 0 Td [(1+ q +1 x otherpointsof Q + ;q and,for p 62L , p iscollinearwith q +1 x pointsof Q + ;q .Thus L isan x -tightsetifandonlyif A = q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 + x q +1 j : Since j A = q q +1 2 j ,theaboveformulafollowsimmediately. In Q + ;q ,thereexisttwodisjointtotallyisotropicplanes 1 and 2 ;ourgoal istondtightsetswhicharedisjointfrom 1 [ 2 .Theabovemethodwillbe slightlymodiedtoaccountforthis.Wewilllet A 0 bethesubmatrixof A obtained bythrowingawaytherowsandcolumnscorrespondingtopointsin 1 [ 2 . Theorem3.2 Let L beasetofpointsof Q + ;q disjointfrom 1 and 2 andlet 0 bethevectorobtainedfromthecharacteristicvectorof L byremovingentries 30

PAGE 39

correspondingtopointsof 1 and 2 .Then L isan x -tightsetof Q + ;q ifandonly if 0 )]TJ/F19 11.9552 Tf 25.233 8.087 Td [(x q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 j A 0 = q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 )]TJ/F19 11.9552 Tf 25.232 8.087 Td [(x q 2 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 j . Proof: Denotetheeigenspaceof A correspondingtotheeigenvalue q 2 )]TJ/F15 11.9552 Tf 12.095 0 Td [(1by E , andtheeigenspaceof A 0 correspondingtotheeigenvalue q 2 )]TJ/F15 11.9552 Tf 10.97 0 Td [(1by E 0 .Since 1 [ 2 isa2-tightset, = 1 [ 2 )]TJ/F15 11.9552 Tf 25.535 8.088 Td [(2 q 2 +1 j 2 E: Let L beasetofpointsof Q + ;q disjointfrom 1 and 2 withcharacteristicvector ;then L isa x -tightsetifandonlyif )]TJ/F19 11.9552 Tf 25.136 8.088 Td [(x q 2 +1 j 2 E v = )]TJ/F19 11.9552 Tf 25.135 8.088 Td [(x q 2 +1 j + x q 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(q 2 E: Theentriesof v correspondingtopointsof 1 [ 2 are0,andtheentrycorresponding toapoint p 62 1 [ 2 isgivenby p )]TJ/F19 11.9552 Tf 25.136 8.087 Td [(x q 2 +1 )]TJ/F19 11.9552 Tf 25.233 8.087 Td [(x q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 2 q 2 +1 = p )]TJ/F19 11.9552 Tf 25.233 8.087 Td [(x q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : Thusifweobtainanewvector v 0 from v bythrowingawayentriescorrespondingto pointsin 1 [ 2 ,andanewvector 0 from inthesamemanner, v 0 = 0 )]TJ/F19 11.9552 Tf 25.232 8.088 Td [(x q 2 )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 j 2 E 0 )]TJ/F19 11.9552 Tf 25.136 8.088 Td [(x q 2 +1 j 2 E L isan x -tightset. 3.2TacticalDecompositions Foranyincidencestructure,a tacticaldecomposition isapartitionofthepoints intopointclassesandtheblocksintoblockclassessuchthatthenumberofpoints inapointclasswhichlieonablockdependsonlyontheclassinwhichtheblock lies,andsimilarlywithpointsandblocksinterchanged.Examplescanbeobtained bytakingaspointandblockclassestheorbitsofsomecollineationgroupactingon thestructure. 31

PAGE 40

Theideaofatacticaldecompositioncanalsobeextendedtomatrices.Let A =[ a ij ]beamatrix,alongwithapartitionoftherowindicesintosubsets R 1 , ::: , R t andapartitionofthecolumnindicesintosubsets C 1 , ::: , C t 0 .Wewillcallthis a tacticaldecomposition of A ifforevery i;j ,1 i t ,1 j t 0 ,thesubmatrix [ a h;` ] h 2 R i , ` 2 C j hasconstantcolumnsums c ij androwsums r ij .Atactical decompositionofanincidencestructurecorrespondstoatacticaldecompositionof itsincidencematrix.Therowandcolumnsummatricesof A aredenedtotobe R A =[ r ij ]and C A =[ c ij ]respectively. Utilizingatacticaldecompositionmakesndingeigenvectorscorrespondingto x -tightsetseasier,asaneigenvectorofthecolumnsummatrix C A obtainedfromthe decompositioncanbeusedtorecoveraneigenvectorof A .Thefollowingresultcomes fromthetheoryoftheinterlacingofeigenvalues,whichwasintroducedbyHigmanand Sims,usedbyPayneinthestudyofgeneralizedquadrangles,andfurtherdeveloped byHaemers;see[17]foradetailedsurvey. Theorem3.3 Supposethematrix A canbepartitionedas A = 2 6 6 6 6 4 A 11 A 1 k . . . . . . . . . A k 1 A kk 3 7 7 7 7 5 .1 witheach A ii square, 1 i k ,andeach A ij havingconstantcolumnsum c ij ;then anyeigenvalueofthecolumnsummatrix C A =[ c ij ] isalsoaneigenvalueof A . Proof: Aneigenvectorof C A canbeexpandedaccordingtothepartitionof A by duplicatingtheentriescorrespondingtoeachparttoconstructaneigenvectorof A . Toapplythistheoremtothetaskofndingeigenvectorsofthecollinearitymatrix of Q + ;q ,wedeneanincidencestructure H withbothpoints"andblocks"being givenbythepointsof Q + ;q ,andincidencebeinggivenbycollinearity.Thusthe 32

PAGE 41

incidencematrix A of H isgivenbythecollinearitymatrixof Q + ;q .Furthermore, anyautomorphismof Q + ;q determinesanautomorphismof H inanobviousway. Thematrix A issymmetric,andanytacticaldecompositionarisingfromanautomorphismgroupof Q + ;q willinducethesamepartitionontherowsof A andthe columnsof A .Thefollowingtheoremgivesusanicerelationshipbetweentherow andcolumnsumsinarisingfromsuchatacticaldecomposition. Theorem3.4 Let A beasymmetricmatrixandlet O 1 , ::: , O k bethepartsofa tacticaldecompositionof A sotherowandcolumnpartitionisthesamewith j O i j = o i ;then r ij = c ji ,and o i r ij = o j c ij . Proof: If A ij isthesubmatrixassociatedwiththerowpartcorrespondingto O i and thecolumnpartcorrespondingto O j ,then A ij = A T ji ,thus r ij = c ji forall i , j .Also, eachofthe o i rowsof A ij hasrowsum r ij ,andeachofthe o j columnshascolumn sum c ij .Summingoverallentriesof A ij intwowaysgives o i r ij = o j c ij . Corollary3.5 Let A beasymmetricmatrixwithatacticaldecompositionhavingthe samepartsforrowsandcolumns,withpart i containing o i rows/columns;thenwe havethefollowingrelationshipbetweentherowandcolumnsummatrices: R T A =[ r ji ]=[ c ij ]=[ o i o j r ij ]= C A : 3.3Amodelof Q + ;q Wenowdescribeamodelfor Q + ;q whichgivesusarangeofalgebraictools touseinsearchingfortightsets.Let F = F q , E = F q 3 ,and T=T E=F : x 7! x q 2 + x q + x: Weconsider Q + ;q tohave V = E 2 asitsunderlyingvectorspace,consideredover F andequippedwiththequadraticform Q : x;y 7! T xy : 33

PAGE 42

ThepolarformBof Q isthengivenby B u 1 ;u 2 ; v 1 ;v 2 =T u 1 v 2 +T u 2 v 1 : Thisformisnondegenerate,sinceif v 1 ;v 2 2 V hasB v 1 ;v 2 ; x;y =0forall x;y 2 V ,thenT v 1 y +T v 2 x =0forall x;y 2 V .Setting x =0forces T v 1 y = v 1 y + v q 1 y q + v q 2 1 y q 2 =0forall y 2 E , thus v 1 =0.Likewise,setting y =0canbeseentoforce v 2 =0,andso v 1 ;v 2 = ; 0. Itcanbealsobeseenthat 1 = f x; 0: x 2 E g and 2 = f ;y : y 2 E g aretotallyisotropicplaneswithrespecttothisform.Thisshowsthatthequadric denedby Q hasWittindex3,andsoishyperbolic. 3.4Thegeneralmethod Theorem3.6 Let q 6 1mod3 .Take 2 E with j j = q 2 + q +1 ,anddenethe map g on Q + ;q by g : x;y 7! x; )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 y ; thenthegroup C = h g i PGO + ;q andhas j C j = q 2 + q +1 .Thisgroupacts semi-regularlyonthepointsof Q + ;q andstabilizesthetotallyisotropicplanes 1 and 2 . Proof: Itisclearthat g isanisometryof Q + ;q havingorder q 2 + q +1.Tosee that C actssemi-regularlyonthepointsof Q + ;q ,noticethat g i x;y = x;y impliesthat i 2 F .But q 2 + q +1 ;q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1= q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; 3=1 ; 34

PAGE 43

since q 6 1mod3.Thusthiscanonlyhappenwhen i =1,andsotheidentityis theonlyelementofthisgroupxingapoint. If isaprimitiveelementof E ,wecanwithoutlossofgeneralityassumethat = q )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 .Thesemi-regularactionof C on Q + ;q givesusthefollowingresult. Theorem3.7 Let A bethecollinearitymatrixof Q + ;q , q 6 1mod3 ,withatacticaldecompositioninducedbytheactionofthecyclicgroup C denedabove;then therowofeachsubmatrixofthedecompositionisthesameasthecolumnsum.Thus thedecompositionmatrixwhichisthesameforrowsumsandcolumnsumsissymmetric. Proof: Thisfollowsdirectlyfrom3.4sinceallorbitshavethesamesize. Sinceeachorbithassize q 2 + q +1,aunionof x orbitscontainstherightnumber ofpointstobean x -tightsetof Q + ;q .Ourgoalwillbetondwaysofcombining theseorbitswhichwillresultinan x -tightset.Weaccomplishthisbyconsideringlarge subgroups G N P )]TJ/F20 7.9701 Tf 5.289 0 Td [(O + ;q C havingrelativelyfeworbitsonthepointsof Q + ;q . Theorbitsofsuchagroupareunionsoforbitsof C .Weusesuchagroup G toinduce atacticaldecompositiononthepointsof Q + ;q ,andthenusethisdecompositionto formthecolumnsummatrix B ofthecollinearitymatrix A ,afterthrowingawaythe entriescorrespondingtopointsin 1 and 2 .Theeigenspaceof B fortheeigenvalue q 2 )]TJ/F15 11.9552 Tf 11.268 0 Td [(1isthensearchedforeigenvectorshavingaformcorrespondingtoan x -tightset of Q + ;q .Whenevernewexamplesshowapattern,e.g.acommonformulafor x intermsof q orasimilarstabilizinggroup,algebraic,geometric,andcombinatorial detailsareanalyzedinanattempttondaconstructionforanewinnitefamilyof tightsets. 35

PAGE 44

4.Newexamples Throughoutthischapter,welet q 6 1mod3, E = F q 3 with E = h i ,and F = F q E with F = h ! i where ! = q 2 + q +1 .Thehyperbolicquadric Q + ;q is denedoverthevectorspace V = E 2 consideredover F andhasquadraticform Q x;y = T xy ,where T = T F=E ,andpolarformB u ; v = T u 1 v 2 + T u 2 v 1 as describedinChapter3.Put = q )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ,anddenethecyclicgroup C = h g i ,where g : x;y 7! x; )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 y ; then C actssemi-regularlyonthepointsof Q + ;q andstabilizesthedisjointtotally isotropicplanes 1 = f x; 0: x 2 E g and 2 = f ;y : y 2 E g . BelowisasummaryofthenewexamplesofCameron-Lieblerlineclasseswhich aredescribedinthischapter.Noticethathereweconsidertheparameteroftheline classtobesmallerthanthatofitscomplement,andwetakethelineclasstobe disjointfrom 1 [ 2 ;thusanewexamplewithparameter x describedbelowalso givesnewlineclasseswithparameter x +1, x +2, q 2 +1 )]TJ/F19 11.9552 Tf 10.64 0 Td [(x , q 2 )]TJ/F19 11.9552 Tf 10.64 0 Td [(x ,and q 2 )]TJ/F15 11.9552 Tf 10.641 0 Td [(1 )]TJ/F19 11.9552 Tf 10.64 0 Td [(x . x q Aut L 1 2 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q 5or9mod12 Z q 2 + q +1 Z 1 4 q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 oZ 3 and q< 200 1 3 q +1 2 q 2mod3 Z q 2 + q +1 oZ 3 and q< 150 336 q =27 Z q 2 + q +1 Z 2 oZ 9 495 q =32 Z q 2 + q +1 oZ 15 Table4.1: ParametersandautomorphismgroupsofthenewexamplesofCameronLieblerlineclassesconstructed. 36

PAGE 45

4.1Newexampleswithparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 Herewedescribeaconstructiongivingmanynewexamplesoftightsetsin Q + ;q havingparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 13.062 0 Td [(1.Thisconstructionrequiresustohave q 5or9mod12,andhasresultedinnewtightsetsforallsuch q< 200. 4.1.1Theconstruction Let S = f x : x 2 E j T x =0 g ;thentheorbitsof C onthepointsof Q + ;q are 1 = ; 0 C , 2 = ; 1 C ,and ;x C foreach x 2S .Wealsoletthegroup H = h h i ,where h : x;y 7! x;! 4 y ; actonthespace,andput G = h C;H i . Lemma4.1 Thegroup H denedabovecentralizes C ,andintersects C trivially. Proof: Toshowthat H centralizes C ,weonlyneedtoshowthat g and h commute; wehavethat h g x;y = h x; )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 y = x; )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ! 4 y and g h x;y = g x;! 4 y = x; )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ! 4 y : Sincethepowersof arepairwiseindependentover F ,itisclearthat H C contains onlytheidentity. Corollary4.2 Thegroup G denedaboveisequalto C H ,andso j G j = 1 4 q )]TJ/F15 11.9552 Tf -422.702 -23.98 Td [(1 q 2 + q +1 . Furthermore,itcanbeseenthat G actssemiregularlyonthepointsof Q + ;q n 1 [ 2 ,as H actssemi-regularlyonthosepoints,andinducesasemi-regularactionon thoseorbitsof C aswell. 37

PAGE 46

Let S k bethesubsetof S containingtheelementswithlog x k mod4for 0 k 3.For x 2S ,put x = f ! 4 t x :0 t< q )]TJ/F15 11.9552 Tf 12.318 0 Td [(1 = 4 g ;forshorthandwewill write ; x = f ;x 0 : x 0 2 x g .Nowwedene x;y := ;x ? ; y C : Intermsofthetacticaldecompositioninducedby G on Q + ;q , x;y isthenumber ofpointsin ; y C collinearwithanygivenpointof ; x C .Thus x 0 ;y 0 = x;y forall x 0 2 x and y 0 2 y . Let A bethematrixobtainedfromthetacticaldecompositioninducedby G on thecollinearitymatrixof Q + ;q afterthrowingawaytheentriescorrespondingto pointsin 1 [ 2 .Weuseaspecicorderingoftheorbitsof G todene A .Notice that S 0 contains 1 4 q 2 )]TJ/F15 11.9552 Tf 12.137 0 Td [(1elementsof E ,andsocontains q +1equivalenceclasses oftheform x .Let x 0 , ::: , x q berepresentativesfromthese q +1orbits.Weorderthe orbitsas ; x 0 C ;:::; ; x q C ; ;! x 0 C ;:::; ;! x q C ; ;! 2 x 0 C ;:::; ;! 2 x q C ; ;! 3 x 0 C ;:::; ;! 3 x q C : Now A canbedescribedasfollows: A = 2 6 6 6 6 6 6 6 4 A 0 A 1 A 2 A 3 A 3 A 0 A 1 A 2 A 2 A 3 A 0 A 1 A 1 A 2 A 3 A 0 3 7 7 7 7 7 7 7 5 , where A k = )]TJ/F19 11.9552 Tf 5.48 -9.683 Td [( x i ;! k x j 0 i;j q for0 k 3.Thismatrixisblock-circulant,which allowsustoapplythefollowingresultoneigenvectorsofblock-circulantmatricesdue toGarryTee[30]. Theorem4.3 Let beanyfourthrootofunity,and A beablock-circulantmatrix asdenedabove,withblocks A 0 , A 1 , A 2 , A 3 eachhavingsize n= 4 .Takeavector v 2 R n 4 .Thenthevector w =[ v v 2 v 3 v ] 38

PAGE 47

isaneigenvectorof A for ifandonlyif v isaneigenvectorof A 0 + A 1 + 2 A 2 + 3 a 3 for . Wenowinvestigatesomepropertiesof inordertobetterunderstandthestructureof A . Lemma4.4 For x;y 2S notnecessarilydistinct, x;y = y;x . Proof: ThisfollowsdirectlyfromTheorem3.4,alongwiththefactthat ; x C and ; y C arethesamesize. Corollary4.5 A issymmetric;thus A 0 and A 2 aresymmetric,and A 1 = A T 3 . Lemma4.6 For x;y 2 S 0 notnecessarilydistinct, x;! k y = y;! k x for 0 k 3 . Proof: Firstwenoticethat h i contains q 2 + q +1distinctelementsof E ,no twodieringbyamultiplein F .Thus,forany z 2 E ,thereexistsaninteger 0 j
PAGE 48

Fromthiswecanseebyrelabelingindicesthat x;! k y = X 0 t< q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 = 4 jf i :0 i
PAGE 49

that L isdisjointfromatrivial 2 -tightsetconsistingofaunionoftwoskewtotally isotropicplanes. Proof: Wehavethat i isafourthrootofunity.Thematrix H = A 0 + iA 1 + i 2 A 2 + i 3 A 3 = A 0 + iA 1 )]TJ/F19 11.9552 Tf 11.956 0 Td [(A 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(iA 3 = A 0 )]TJ/F19 11.9552 Tf 11.955 0 Td [(A 2 hasaniceform;allofthediagonalentriesare )]TJ/F15 11.9552 Tf 9.298 0 Td [(1,andallotherentriesare q . Furthermore,thereissomepartitionof f x 0 ;:::;x q g ,intoparts L 1 and L 2 suchthat H ij = q ifandonlyif i 6 = j and x i , x j areinthesamepart;say j L 1 j = a and j L 2 j = b , with a + b = q +1.Ifwetake K tobetheadjacencymatrixofthegraph K L 1 K L 2 where K L 1 and K L 2 arethecompletegraphsonthesets L 1 and L 2 ,respectivelyand K 0 betheadjacencymatrixofthecomplementofthisgraph,then H = qK )]TJ/F19 11.9552 Tf 10.694 0 Td [(qK 0 )]TJ/F19 11.9552 Tf 10.694 0 Td [(I . Wewillformthevector v = L 1 )]TJ/F17 7.9701 Tf 12.685 4.707 Td [(1 2 j = 1 2 L 1 )]TJ/F17 7.9701 Tf 12.686 4.707 Td [(1 2 L 2 .Noticethat x q 2 )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 = 1 2 ifwelet x = q 2 )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 2 .Nowwehavethat L 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [( L 2 H = L 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [( L 2 qK )]TJ/F19 11.9552 Tf 11.955 0 Td [(qK 0 )]TJ/F19 11.9552 Tf 11.955 0 Td [(I = a )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q L 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(aq L 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [( L 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [( b )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 q L 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(bq L 1 )]TJ/F19 11.9552 Tf 11.956 0 Td [( L 2 = a + b )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 L 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [( a + b )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 L 2 = q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 L 1 )]TJ/F19 11.9552 Tf 11.955 0 Td [( L 2 , thus v isaneigenvectorof H havingthedesiredform.Wecanuse v toconstructan eigenvectorof A infourdierentways,namely [ v )]TJ/F34 11.9552 Tf 9.299 0 Td [(v )]TJ/F34 11.9552 Tf 9.299 0 Td [(vv ] [ vv )]TJ/F34 11.9552 Tf 9.299 0 Td [(v )]TJ/F34 11.9552 Tf 9.298 0 Td [(v ] eachofwhichinturncanbeusedtoconstructaneigenvectorofthecollinearitymatrix M of Q + ;q correspondingtoa 1 2 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1-tightset. 4.1.2Somedetailsoftheseexamples Ourexampleswithparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 12.535 0 Td [(1haveagroupisomorphicto Z q 2 + q +1 Z 1 4 q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 actingonthem,byconstruction.Byobservingdetailsabouttheorbitsused 41

PAGE 50

intheconstruction,wenoticethattheseexamplesarealsostabilizedbyAut F q 3 , thustheyarestabilizedbyagroupisomorphicto Z q 2 + q +1 Z 1 4 q )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 oZ 3 .Forthose examplessmallenoughtocomputetheirfullstabilizerin P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L ;q ,whicharethose with q 41,thisisinfactthefullgroup. WecanalsocomputeintersectionnumbersoftheselineclassesinPG ;q with respecttoplanesandpointstarsofPG ;q ;thisbecomesprohibitivelyexpensive, computationally,when q> 32.Hereweincludedetailsforsomesmallvaluesof q , aswellas q =81;thisspecialcasewasofparticularinterest,seeChapter5,soa considerableamountoftimewasdedicatedtocomputingthesevalues. Inthistable,weincludetheintersectionnumberswithrespecttoplanesof PG ;q ;theexamplesconsideredhereareallisomorphictotheirdual,andsohave thesameintersectionnumberswiththesamemultiplicitieswithrespecttothepoint starsofPG ;q . q x Intersectionnumbers,withmultiplicity;wehave r = q 2 + q +1 5 12 0 ; 6 r ; 12 r ; 18 r ; 24 r 9 40 0 ; 30 r ; 40 r ; 60 r 17 144 0 ; 108 r ; 126 r ; 144 r ; 180 r ; 198 r 29 420 0 ; 330 r ; 390 r ; 420 r ; 480 r ; 540 r 81 3280 0 ; 2952 r ; 3280 r ; 3690 r Table4.2: Intersectionnumbersoflineclasseswithparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 12.377 0 Td [(1 withthe planesof PG ;q . Thenumbersinboldrepresenttheintersectionnumbersfortheplanecorresponding to 1 in Q + ;q ,whichisdisjointfromourlineclass,andtheplanesthroughthe pointwhichcorrespondsto 2 in Q + ;q ,whichshares 1 2 q 2 )]TJ/F15 11.9552 Tf 11.845 0 Td [(1lineswithourline class.Itisworthnotingthatthenumberoflinessharedbyeachplanewiththeline 42

PAGE 51

classisdivisibleby q +1.Themultiplicitiesbeingdivisibleby q 2 + q +1isaside eectof C actingsemi-regularlyontheplanesofPG ;q notcorrespondingto 1 . Thenewexamplesoftightsetsin Q + ;q giveexamplesoftwo-intersectionsets, two-weightcodes,andstronglyregulargraphs,asdetailedinChapter2.Whilethere aretablesofknownstronglyregulargraphs,theseexampleson q 6 verticesaretoo largetoappear.Furthermore,iftherewereknownexamples,checkingisomorphism wouldmostlikelybeunreasonable. 4.2Newexampleswithparameter 1 3 q +1 2 Herewegivedetailsonmanynewexampleswhichhavebeenconstructedinjoint workwithJanDeBeule,KlausMetsch,andJeroenSchillewaert,havingparameter 1 3 q +1 2 .Theseexampleshavebeenconstructedforallvaluesof q 2mod3 whicharecomputationallyfeasible.Unfortunately,ingeneraltheseexamplesdonot exhibitmuchsymmetry;alloftheexamplesfoundhave C o Aut F q 3 astheirfull stabilizinggroup.When q isprime,thisdoesnotgivemuchtoworkwith.Theseare foundthroughmoreofasearchthanaconstruction;rstweputtogetherthetactical decompositionmatrixfor Q + ;q n 1 [ 2 withrespecttothegroup,thenwesearch overtheeigenspaceforappropriateeigenvectorsseeAppendixAfordetailsabout thealgorithmsused.Withasmallstabilizer,therearelotsoforbits;forexample, if q isprime,thereare 1 3 q 2 )]TJ/F15 11.9552 Tf 12.086 0 Td [(1orbitstoconsider.Assuch,formingthematrixfor thetacticaldecompositionisalargetask.Furthermore,wedonotcurrentlyhavea goodmethodforreducingthesizeoftheeigenspacetosearchover,sondingthese examplesiscomputationallyinfeasibleiftheeigenspaceofthetacticaldecomposition matrixistoolargedimensionsstartstopushthelimitsofourcomputingpower. Animportantsubcaseoftheseexamplesoccurswhen q =2 e ,where e> 1and odd.Inthiscase,wehaveaslightlylargerstabilizinggrouptoworkwith.These examplesarealsoofparticularinterestsincethereisonlyonepreviouslyknown Cameron-LieblerlineclassinPG ;q for q evenseeChapter2forthisconstruc43

PAGE 52

tion.Newexampleswiththisparameterhavebeenfoundfor q 2f 8 ; 32 ; 128 g ,as wellasforoddprimes q 100whicharecongruentto2mod3,andfor q =125.In allofthecaseswhereitisfeasibletocomputethestabilizergroup q 32,wehave that C o Aut F q 3 isthefullgroup.Below,wedescribehowsomeoftheselineclasses intersectplanesofPG ;q .Alloftheexamplesconsideredbelowareisomorphicto theirdual,andsohavethesameintersectionnumberswiththesamemultiplicities withrespecttopointstarsofPG ;q . q x Intersectionnumbers,withmultiplicity;wehave r = q 2 + q +1 5 12 0 ; 6 r ; 12 r ; 18 r ; 24 r 8 27 0 ; 18 r ; 27 r ; 36 r ; 54 r 11 48 0 ; 24 r ; 36 r ; 48 r ; 60 r ; 72 r ; 96 r 17 108 0 ; 72 r ; 90 r ; 108 r ; 126 r ; 144 r ; 216 r 23 192 0 ; 120 r ; 144 r ; 168 r ; 192 r ; 216 r ; 240 r ; 264 r ; 384 r 32 363 0 ; 264 r ; 330 r ; 363 r ; 396 r ; 462 r ; 726 r Table4.3: Intersectionnumbersoflineclasseswithparameter 1 3 q +1 2 withthe planesof PG ;q . 4.3Someothernewexamples Wealsohaveacoupleofothernewexampleswhichdonotcurrentlyseemtot intoanicegrouping.Theseexampleshavebeenfoundbyassumingagroupacting onthepointsof Q + ;q usuallyasubgroupof N O + ;q C ,formingtheorbitsof Q + ;q n 1 [ 2 andtheassociatedmatrixforthetacticaldecomposition,and searchingoverallpossibleparameters.Thenumberofpossibleparameterscanbe verylarge,especiallyiftheorbitsarenotallthesamesize.Itwascomputationally feasiblewhen q 23toassumethattheexampleswewerelookingforadmittedthe 44

PAGE 53

group C o Aut F q 3 = F q asastabilizer,thoughthesesearchesdidnotyieldanynew examples. For q =27,thevariationintheorbitsizesgivesalargenumberofpossible parameters,andthereisarelativelylargeeigenspacetoconsider.Thus,considering asmallstabilizinggroupwasnotfeasible.Byassumingthegroup C o Aut F q 3 stabilizedtheexamples,wewereabletondanewtightsetwithparameter336. Thisexampleisalsostabilizedbythemap x;y 7! x; )]TJ/F19 11.9552 Tf 9.298 0 Td [(y ,andsohasfullstabilizer isomorphicto Z q 2 + q +1 Z 2 oZ 9 .Restrictingourrstsearchwith C o Aut F q 3 = F q byassumingourparameterwasdivisibleby q +1,wefoundnoothernewexamples. With q =32,allofthepointorbitsofthegroup C o Aut F q 3 on Q + ;q have thesamesize,sothesearchisfeasibleassumingthisstabilizer.Weareabletond twonewexampleshavingparameter495,eachhaving C o Aut F 32 3 = F 2 astheirfull stabilizer.Inthiscase,thesetwoexamplesareisomorphicastightsets,butnotas Cameron-Lieblerlineclasses.InPG ;q ,theyaredualtooneanother. BelowwedetailhowtheseexamplesintersecttheplanesofPG ;q .Notethat onlytherstexampleisself-dual;inthiscase,theintersectionnumbersandmultiplicitiesforpointstarsofPG ;q arethesameasforplanes.Forthetwoexamples with q =32,theplaneintersectionnumbersofoneexamplearethepointstarintersectionnumbersfortheother,andvice-versa. q x Intersectionnumbers,withmultiplicity;wehave r = q 2 + q +1 27 336 0 ; 252 r ; 336 r ; 420 r ; 504 r 32 495 0 ; 330 r ; 396 r ; 462 r ; 495 r ; 528 r ; 594 r 32 495 0 ; 396 r ; 495 r ; 528 r ; 660 r Table4.4: Intersectionnumbersofsomeothernewlineclasses. 45

PAGE 54

5.Planartwo-intersectionsets Asetoftype m;n inaprojectiveoraneplaneisaset K ofpointssuchthat everylineoftheplanecontainseither m or n pointsof K ;werequirethat m
PAGE 55

K ,andeachofthe t n n -secantscontains n n )]TJ/F15 11.9552 Tf 12.316 0 Td [(1suchpairs.Eachofthe k k )]TJ/F15 11.9552 Tf 12.316 0 Td [(1 orderedpairsofpointsin K iscountedonceinthismanner. Corollary5.2 Ifwehaveaset K oftype m;n inaprojectiveplaneoforder q , then k = jKj mustsatisfy k 2 )]TJ/F19 11.9552 Tf 11.956 0 Td [(k q n + m )]TJ/F15 11.9552 Tf 11.956 0 Td [(1+ n + m + mn q 2 + q +1=0 : .4 Ifwetakeaxedpoint p 2K ,andlet m and n bethenumberof m -secants and n -secantsthrough p ,respectively,weseethat m + n = q +1and m )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 m + n )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 n = k )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 : Fromthis,weseethat m = n q +1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k )]TJ/F19 11.9552 Tf 11.956 0 Td [(q = n )]TJ/F19 11.9552 Tf 11.955 0 Td [(m and n = k + q )]TJ/F19 11.9552 Tf 11.955 0 Td [(m q +1 = n )]TJ/F19 11.9552 Tf 11.956 0 Td [(m ; andso m and n donotdependonourchoiceof p .Likewise,ifwetakeaxedpoint q 62K ,andlet m and n bethenumberof m -secantsand n -secantsthrough q ,we seethat m + n = q +1and m m + n n = k: Again,thesevaluescanbeseentobeindependentofourchoiceof q ;wehavethat m = n q +1 )]TJ/F19 11.9552 Tf 11.956 0 Td [(k = n )]TJ/F19 11.9552 Tf 11.955 0 Td [(m and n = k )]TJ/F19 11.9552 Tf 11.956 0 Td [(m q +1 = n )]TJ/F19 11.9552 Tf 11.955 0 Td [(m : Fromthesenumbersweseethat,givenasetoftype m;n inaprojectiveplaneof order q ,wecanconstructthreeotherrelatedsetswithtwointersectionnumbersfor aproof,see[18]. 47

PAGE 56

Theorem5.3 Let K beasetoftype m;n inaprojectiveplane oforder q ,with jKj = k . 1.Thecomplementof K isasetoftype q +1 )]TJ/F19 11.9552 Tf 12.488 0 Td [(n;q +1 )]TJ/F19 11.9552 Tf 12.487 0 Td [(m in containing q 2 + q +1 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k points. 2.Thesetof m -secantsto K isasetoftype m ; m inthedualplaneto containing t m points. 3.Thesetof n -secantsto K isasetoftype m ; m inthedualplaneto containing t n points. Noticethat n )]TJ/F19 11.9552 Tf 12.004 0 Td [( n = q= n )]TJ/F19 11.9552 Tf 12.004 0 Td [(m andsoitisnecessaryfor n )]TJ/F19 11.9552 Tf 12.004 0 Td [(m todivide q .If n )]TJ/F19 11.9552 Tf 12.262 0 Td [(m = q ,then K canbeseentobeeitherthesetofpointsonacommonline,or thecomplementofthis;theexampleshaving n )]TJ/F19 11.9552 Tf 12.405 0 Td [(m =1aredualtothese,andwe considertheexamplesineitherofthesesituationstobetrivial. Onemajorclassofexamplesarethesetsoftype ;n .Theseexamplesarealso knownasmaximalarcsofdegree n ,oras qn )]TJ/F19 11.9552 Tf 12.535 0 Td [(q + n;n -arcsastheynecessarily contain qn )]TJ/F19 11.9552 Tf 10.924 0 Td [(q + n points.Theprototypicalexamplesaregivenbyhyperovals,which aresetsoftype ; 2;otherfamiliesofmaximalarcsofdegreelargerthan2have beendescribedbyDenniston[11],Thas[31][32],andMathon[21].Maximalarcsof degree2 a areknowntoexistinPG ; 2 e forallpairs a;e with0
PAGE 57

Lemma5.4 Let K beasetoftype m;n inananeplane oforder q .Let t m and t n bethenumberor m -secantsand n -secantsto K ,andlet k = jKj ;then t m + t n = q 2 + q; .5 mt m + nt n = k q +1 ; and .6 m m )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 t m + n n )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 t n = k k )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 : .7 ThesemodiedformulasleadtothefollowingalternateversionofCorollary5.2. Corollary5.5 Ifwehaveaset K oftype m;n inananeplaneoforder q ,then k = jKj mustsatisfy k 2 )]TJ/F19 11.9552 Tf 11.955 0 Td [(k q n + m )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ n + m + mnq q +1=0 : Weagaingetconstantvalues m and n forthenumberof m -secantsand n -secants throughapointin K ,and m and n forthenumberof m -secantsand n -secants throughapointnotin K ,givenbytheformulas m = n q +1 )]TJ/F19 11.9552 Tf 11.956 0 Td [(k )]TJ/F19 11.9552 Tf 11.955 0 Td [(q = n )]TJ/F19 11.9552 Tf 11.955 0 Td [(m ; n = k + q )]TJ/F19 11.9552 Tf 11.955 0 Td [(m q +1 = n )]TJ/F19 11.9552 Tf 11.955 0 Td [(m ; m = n q +1 )]TJ/F19 11.9552 Tf 11.956 0 Td [(k = n )]TJ/F19 11.9552 Tf 11.955 0 Td [(m ; and n = k )]TJ/F19 11.9552 Tf 11.955 0 Td [(m q +1 = n )]TJ/F19 11.9552 Tf 11.955 0 Td [(m : Thistellsusthat,asfortheprojectivecase,wemusthave n )]TJ/F19 11.9552 Tf 10.524 0 Td [(m dividing q .However, sincethedualofananeplaneisnotagainananeplane,wedonothaveresults aboutthe m -secantsor n -secantsforminganotherplanarsetwithtwointersection numbers. Thereareveryfewknownexamplesofsetsoftype m;n inaneplanes.For planesofevenorder,wecanobtainanexamplefromasetoftype ;n inaprojective plane,bychoosinganexternallinetothesetasthelineatinnitytoformtheane plane.However,setsofthistypedonotexistinprojectiveplanesofoddorder. 49

PAGE 58

Inaneplanesofoddorder,theonlypreviouslyknownexamplesofsetsoftype m;n aresetsoftype ; 6inplanesoforder9.Thesesetswerefoundthroughan exhaustivecomputersearch,see[28],andexampleswerefoundineachofthefour projectiveplanesoforder9. Thesize k ofasetoftype ; 6inaplaneoforder9mustsatisfy k 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(81 k +1620=0 whichhassolutions k 1 =36and k 2 =45.Thecomplementofasetoftype ; 6ina planeoforder9willagainbeasetoftype ; 6,andthecomplementofasetofsize k 1 willcontain k 2 points.The45-setsoftype ; 6have 3 =2, 6 =8, 3 =5,and 6 =5. 5.3ConstructionsfromCameron-Lieblerlineclasses Wenowdescribeamethodofconstructingsomeoftheknownsetsoftype ; 6 inAG ; 9startingwithaCameron-Lieblerlineclasswithparameter40inPG ; 9. WethengeneralizethismethodtogiveanewexampleinAG ; 81. 5.3.1Atwo-intersectionsetin AG ; 9 TakeaCameron-Lieblerlineclass L 1 ofparameter40inPG ; 9,asconstructed intheChapter4.ThissetoflinesisdisjointfromatrivialCameron-Lieblerlineclass withparameter2,whichwewillconsidertobestar p [ line ,where p isapoint inPG ;q and isaplanenotcontaining p .Thislineclassinducesasymmetric tacticaldecompositiononPG ; 9havingfourclassesofpointsandlines,asfollows: thefourlineclassesare 1.star p , 2.line , 3. L 1 ,and 4. L 2 =linePG ;q n line [ star p [L 1 . 50

PAGE 59

EachpointofPG ;q n f p g[ liesoneither30or60linesof L 1 seeTable4.2, andsothefourpointclassesofthetacticaldecompositionare 1. f p g , 2. , 3. P 1 = f u 2 PG ;q :star u L 1 =30 g ,and 4. P 2 = f v 2 PG ;q :star v L 1 =60 g . Thenumbersoflinesineachgivenlineclassthroughaxedpointineachgivenpoint classcanbefoundinTable5.1,andthenumbersofpointsineachgivenpointclass onaxedlineineachgivenlineclasscanbefoundinTable5.2. star p line L 1 L 2 f p g 91000 1104040 P 1 103060 P 2 106030 Table5.1: Linesperpointforthesymmetrictacticaldecompositioninducedon PG ; 9 byaCameron-Lieblerlineclassofparameter 40 . star p line L 1 L 2 f p g 1000 11011 P 1 4036 P 2 4063 Table5.2: Pointsperlineforthesymmetrictacticaldecompositioninducedon PG ; 9 byaCameron-Lieblerlineclassofparameter 40 . 51

PAGE 60

Now,ifwetakeaplane 0 ofPG ; 9notequalto andnotcontaining p , 0 containspreciselyonelineofline andnolinesofstar p .Furthermore, 0 will containeither30or60linesof L 1 ,andso60or30linesof L 2 seeTable4.2.Without lossofgenerality,wemayassumethat 0 contains30linesof L 1 and60linesof L 2 . Asforthevariouspointclasses, 0 doesnotcontain p ,andcontains10pointsof , allonacommonline.Underourassumptions, 0 alsocontains30pointsof P 1 and 60pointsof P 2 .Infact,wehaveasymmetrictacticaldecompositionof 0 having3 classesonpointsandlinesinducedbyourtacticaldecompositionofthelargerspace. Bytaking 0 tobethelineatinnityandremovingitalongwithallofitspoints from 0 ,weobtainananeplaneAG ; 9.Allofthepointsofthisaneplaneare in P 1 or P 2 ,andallofthelinesarein L 1 or L 2 .Itcanbeeasilyveriedthat P 1 isasetoftype ; 6inthisplanecontaining30points.Thissetadmitsastabilizer isomorphicto Z 3 .Asthesetsoftype m;n inAG ; 9werecompletelyclassiedin [28],thissetisnotnew. 5.3.2Anewtwo-intersectionsetin AG ; 81 WearealsoabletofollowtheaboveprocedurewithaCameron-Lieblerlineclass L 1 ofparameter3280inPG ; 81constructedasinChapter4.Inthiscase,the lineclassesareformedasbefore.Asforthepointclasses,eachpointofPG ; 81 isoneither2952linesof L 1 ,oron3690pointsof L 1 .Wedene P 1 tobetheset ofpointson2952linesof L 1 .Thesepointandlineclassesgiveasymmetrictactical decompositionofPG ; 81;thenumbersoflinesineachgivenlineclassthrougha xedpointineachgivenpointclasscanbefoundinTable5.3,andthenumbersof pointsineachgivenpointclassonaxedlineineachgivenlineclasscanbefound inTable5.4. Welet 0 beaplaneofPG ; 81notequalto ,andnotcontaining p .Then 0 containsonelineofline andnolinesofstar p .Also, 0 willcontaineither2952 linesof L 1 or3690linesof L 1 seeTable4.2;withoutlossofgenerality,assume 0 52

PAGE 61

star p line L 1 L 2 f p g 6643000 18232803280 P 1 1029523690 P 2 1036902952 Table5.3: Linesperpointforthesymmetrictacticaldecompositioninducedon PG ; 81 byaCameron-Lieblerlineclassofparameter 3280 . star p line L 1 L 2 f p g 1000 18211 P 1 4003645 P 2 4004536 Table5.4: Pointsperlineforthesymmetrictacticaldecompositioninducedon PG ; 81 byaCameron-Lieblerlineclassofparameter 3280 . contains2952linesof L 1 .Thepointsetof 0 isagaindisjointfrom f p g ,andcontains 82pointsof ,allonacommonline.Bytakingthisline,whichis 0 ,tobethe lineatinnityandremovingitalongwithallofitspointsfrom 0 ,weobtainanane planeAG ; 81.Allofthepointsofthisaneplanearein P 1 or P 2 ,andallofthe linesarein L 1 or L 2 .Itisclearthat P 1 isasetoftype ; 45containing2952 points.Therearenopreviouslyknownexamplesofsetsoftype m;n inAG ; 81, sothisexampleisnew.UsingMagma,thestabilizerofthissetiscomputedandis isomorphicto Z 6 . 5.3.3Afamilyofexamplesin AG ; 3 2 e ? ThecombinatoricsofourCameron-Lieblerlineclassesofparameter 1 2 q 2 )]TJ/F15 11.9552 Tf 12.891 0 Td [(1 seemtobeespeciallyniceovereldsoforder3 2 e ,inducingasymmetrictactical decompositiononthespacehavingfourclassesoflinesandofpoints.Afuture 53

PAGE 62

directionofresearchrelatedtothisobservationistofocusonprovingtheexistence ofaninnitefamilyofCameron-Lieblerlineclasseshavingthisparameterinthe speciccasewhere q =3 2 e ,andexaminingtheintersectionnumberswithrespect totheplanesandpointstarsofPG ;q .Iftheselineclassesalwaysinducesucha tacticaldecomposition,withoneoftheclassesbeingaplaneandanotherapointstar, thenwewillbeabletoconstructaninnitefamilyofsetsoftype m;n inAG ; 3 2 e . AssumewehaveaCameron-Lieblerlineclass L 1 withparameter 1 2 6 e )]TJ/F15 11.9552 Tf 12.584 0 Td [(1in PG ; 3 2 e whichisdisjointfromatrivialCameron-Lieblerlineclassstar p [ line withparameter2so p 62 ,andthatthislineclassinducesasymmetrictactical decompositionofPG ;q asabovehavingpointclasses f p g , , P 1 , P 2 ,andline classesstar p ,line , L 1 , L 2 .Takeaplane 0 distinctfrom andnotcontaining p . Thepointsintheaneplane 0 n 0 areallin P 1 or P 2 ,andthelinesareallin L 1 or L 2 .Ifwelet K = P 1 0 ,thenthelinesoftheaneplanehavepreciselytwo intersectionnumberswith K dependingonwhethertheyarein L 1 or L 2 .Without lossofgeneralitywewillassumethateachlineof L 1 star 0 meets m pointsof K . Let A and B besuchthateachpointin P 1 ison A linesof L 1 and B linesof L 2 ;thus eachpointin P 2 ison B linesof L 1 and A linesof L 2 . Themostlikelypossibilityfor n )]TJ/F19 11.9552 Tf 11.843 0 Td [(m ,andthesituationforourearlierexamples, isthat n )]TJ/F19 11.9552 Tf 12.012 0 Td [(m =3 e .Assumethatthisisthecase,sothat n = m +3 e .ByDenition 2.1,wehave 1 2 6 e )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ 2 e +1 m = jL 1 0 j + A and 1 2 6 e )]TJ/F15 11.9552 Tf 11.955 0 Td [(1+ 2 e +1 m = jL 2 0 j + A; byapplyingtheresultto L 1 usingtheincidentpoint-planepair u ; 0 with u 2P 1 , andto L 2 usingtheincidentpoint-planepair v ; 0 with v 2P 2 .Since m )]TJ/F19 11.9552 Tf 10.403 0 Td [( m =3 e , weseethat jL 2 0 j)-222(jL 1 0 j = 2 e +1 )]TJ/F19 11.9552 Tf 11.955 0 Td [( = 2 e +1 e 54

PAGE 63

which,alongwiththefactthat jL 2 0 j + jL 1 0 j =3 4 e +3 2 e = 2 e +1 2 e ,tellsusthat jL 1 0 j = 1 2 2 e )]TJ/F15 11.9552 Tf 11.956 0 Td [(3 e 2 e +1and jL 2 0 j = 1 2 2 e +3 e 2 e +1 : Thisallowsustosolvefor m = 1 2 2 e )]TJ/F15 11.9552 Tf 11.955 0 Td [(3 e and n = 1 2 2 e +3 e : Conjecture5.6 Forany e 1 ,thereexistsetsoftype 1 2 2 e )]TJ/F15 11.9552 Tf 12.16 0 Td [(3 e ; 1 2 2 e +3 e in AG ; 3 2 e . Ourhopeisthat,inthefuture,wewillbeabletoprovethatwehaveaninnite familyofCameron-LieblerlineclassesinPG ; 3 2 e whichinducetacticaldecompositionsofthespace,allowingustoshowtheexistenceofthesetwo-intersectionsets. 55

PAGE 64

APPENDIXA.Algorithms Herewedetailsomeofthealgorithmsthatfacilitateourndings. A.1CLautMatrix Wehave { C isourcyclicgroupoforder q 2 + q +1whoseorbitson Q + ;q n 1 [ 2 arerepresentedbyelementsof OR EP = f x : x 2 F q 3 j T x =0 g considered asanorderedsetforconsistency. { Z 1 =Aut F q 3 = F p and Z 2 = F q ;thesegroups,consideredon Q + ;q , normalize C ,soweonlyconsidertheiractionon OR EP . Z 1 isassumedto stabilizeourtightsetbut Z 2 isnot. { X BLOCK and XO aretheorbitsof Z 1 and Z 2 ,respectively;theelementsof eachorbitarealsoordered. Wanttostore,foreach x 2 OR EP ,indexedpairs < i 1 , j 1 > and < i 2 , j 2 > sothat x = X BLOCK [ i 1 ][ j 1 ]= XO [ i 2 ][ j 2 ]. Wenowformaset R suchthat,foreach x 2 OR EP ,wehaveaunique r 2 R such that ! i r p k = x forsome i;k . Formthestructure S =[ s r ],where s r =[ j ;r ? ;x C j : x 2 OR EP ]. Formthearray O1P ,where O1P [ i ][ j ]= k ,where k issuchthat ! j r i 2 X BLOCK [ k ]. Eachrowandcolumnofourmatrix A correspondstoanorbiton Q + ;q n 1 [ 2 under G = < C , Z 1 > .Weconsiderthemtobeorderedaccordingto theorderingoftheorbits X BLOCK of Z 1 .Wend A ij asfollows: 56

PAGE 65

{ Let a;b besuchthat ! a r b 2 Z 1 [ i ]. { Then A ij isformedbysummingover s r b [ k ]as k rangesoverthevalues satisfying O1P [ a ][ k ]= j . Inotherwords,foreach Z 1 [ i ],wecanndan x in Z 1 [ i ],an r in R ,andaninteger a suchthat x = ! a r .Weknowhowmanyelementsof ;y C arecollinearwith ;r , soweconsiderhowthemap y 7! ! a y on OR EP permutestheassociatedorbitsof C , andconsiderwhichoftheseorbitshavetheirrepresentativesin Z 1 [ j ],andaddthem up. 57

PAGE 66

APPENDIXB.Programs Wehavestructuredthecodetoexaminetightsetsof Q + ;q inamodular fashion.Thatis,wehaveashellprogramthatcontainstheparameterswemaywish tomodify,andfromthereweloadthelescontainingspecicmethods,andthen callthespecicfunctionsweareinterestedin.Hereisthecodeforourbasicshell program;wecommentoutanypartswearenotinterestedinbeforesubmittingthe jobtothecluster.Anyrestrictionsfortheparameters,eitherfromtherequirements ofthealgorithmsorforthesakeofcomputationalspeed,willbementionedwhenwe discusstheindividualpiecesofthecode. B.1CLshell.mgm Wehavevariables p , h ,and t whichcanbemodied; p doesnotneedtobeprime. Theideaisthatwewillhave q = p h ,and =Au F p 3 h =F p willbeassumedtoactona t -tightsetfoundbythesearch.Weusuallydene t intermsof q ,butwemusttake carethat t isaninteger. p := 81; h := 1; CLpreamble.mgm setsupourbasicinfrastructure. load â€œ CLpreamble.mgm â€; t := R ATIONALS ! 1 / 2 q 2 )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 ; CLaut.mgm holdsthebasicsearchalgorithm;when h =1,itwillndanyofour exampleshavingparameter t ,althoughitisveryslow.Usinglargervaluesof h while leaving q xedmakesthingsmuchfaster,butwillonlyndexamplesstabilizedby thislargergroup. load â€œ CLaut.mgm â€; FindL t , L ; 58

PAGE 67

CLbcirc.mgm isspecializedfor h =1, p 1mod4,and t = = 2 q 2 )]TJ/F15 11.9552 Tf 12.047 0 Td [(1.Itisvery fastandmemoryecient. load â€œ CLbcirc.mgm â€; WehavethatLcontainsthesetoforbitrepresentativesforeachtightsetfound. print â€œ Therewere â€,# L , â€œ lineclassesfoundwithparameter â€, t ; CLvspace.mgm containsdenitionsforthevectorspaces V = E 2 , W = F 6 ,andthe map : V ! W .Thismapusesabasisfor W whichgivesthestandardorthogonal form.Thevectorspace U = F 4 isalsodened,alongwithmaps : U ! W and : W ! U whichmapapointtoalineofPG ;q viatheKleincorrespondence. load â€œ CLvspace.mgm â€; CLpg3q.mgm denesthefunction LU ,whichmapsasetoftracezeroelementsof E tothesetoflinesofPG ;q correspondingtotheirorbitsunder C .Alsodenesthe groups GL = P )]TJ/F19 11.9552 Tf 7.314 0 Td [(L ;q and CU ' C actingonlinesofPG ;q . load â€œ CLpg3q.mgm â€; S := S TABILIZER GL ,LU L [ 1 ] ; print â€œ ThestabilizerofLisasfollows:n â€, S ; CLint.mgm isusedtocomputeintersectionnumbers.Theorbitrepresentativesare expandedtothefullpointsetthrouth LW ,andintersectionnumberswithstarsand planesarecomputedusing intPlane and intStar ,respectively. load â€œ CLint.mgm â€; LL := LW L [ 1 ] ; print â€œ TheintersectionnumberswithmultiplicityofL withpointstarsofthespaceareasfollows:n â€, intStar LL ; print â€œ Theintersectionnumberswithrespectto 59

PAGE 68

planesofthespaceareasfollows:n â€, intPlane LL ; CLint81.mgm givesanalternatewaytocomputeintersectionnumbers.Itismuch slower,butmorememoryecient.Weuseitforthecasewhere p =81,sincethe computationsareimpossibleotherwise. load â€œ CL81int.mgm â€; print â€œ TheintersectionnumberswithmultiplicityofL withpointstarsofthespaceareasfollows:n â€, intStar LW L [ 1 ] ; print â€œ Theintersectionnumberswithrespectto planesofthespaceareasfollows:n â€, intStar LWd L [ 1 ] ; MNset.mgm willgivetheintersectionofthesetinPG ;q withaplanepiPrime asdescribedinChapter5.Theset K willalsobegiven,whichshouldbeatwointersectionsetofAG2 ;q when q =3 2 e . load â€œ MNsetTH2.mgm â€; K := MN L [ 1 ] ; S := KStab K ; print â€œ ThestabilizerofKisasfollows:n â€, S ; B.2CLpreamble.mgm Thiscodeisrequiredforeverythingthatfollows. Welet F = F q and E = F q 3 ,withprimitiveelements ! and ,respectively,and view V as E 2 ,withbilinearform x;y 7! T xy ,where T =Tr E=F . q := p h ; := q 2 )]TJ/F41 10.8792 Tf 9.298 0 Td [(1 ; 60

PAGE 69

F := F INITE F IELD q ; if not I S P RIMITIVE ! then ! := P RIMITIVE E LEMENT F ; endif ; E <> := ext < F j 3 > ; T := func < x j T RACE E ! x , F > ; Itisusefultohavetheseordered.Thisorderingmakes Fstar [ i ]= ! i +1 ,likewise Estar [ i ]= i +1 Fstar := f @ ! i : i in [ 0 :: q )]TJ/F41 10.8792 Tf 9.298 0 Td [(2 ] @ g ; Estar := f @ i : i in [ 0 :: q 3 )]TJ/F41 10.8792 Tf 9.298 0 Td [(2 ] @ g ; isaelementof E withorder r = q 2 + q +1. := q )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 ; r := q 2 + q + 1; ORep isthesetofnonzeroelementswithtrace0;llstheroleof S inthethesis. ORep := f @ x : x in Estar j T x eq 0@ g ; L isaplaceholdersequence;itwillcontainsubsetsof ORep correspondingto t -tight setsofthequadric. L :=[ P OWER S ET ORep j ] ; Insteadofdeningourcyclicgroupactingon V = E 2 ,wedene C tobeapermutation groupon Estar ,generatedby C : 1 : x 7! x . C := P ERMUTATION G ROUP < Estar j [ x : x in Estar ] > ; Wedenethegroup Z 1 =Aut E= F p ;tosavememory,wedenethisgroupactingon justthetracezeroelements ORep Estar .Thisrequiressomeconsiderationtothe orderinwhichweapplygroupstolookatorbits. Gr := S YM ORep ; Z 1 := sub < Gr j [ x p : x in ORep ] > ; 61

PAGE 70

o := Z 1 : 1; Thegroup Z 2 generatedby z : x 7! ! x permutestheorbitsof C ;theorbitsof thisgrouponthetracezeroelementsof Estar areusedtoecientlyformthetactical decomposition. Z 2 := sub < Gr j [ ! x : x in ORep ] > ; z := Z 2 : 1; B.3CLaut.mgm Themethodusedhereisthemostgeneralsearchtechnique.Formingthematrix forthetacticaldecompositioncanbeverycomputationallyexpensive. Xblock := O RBITS Z 1 ; XO := O RBITS Z 2 ; n := # Xblock ; Thefollowingrecordformatisusedtokeeptrackofimportantinformationaboutthe tracezeroelementsof Estar ,suchastheirlocationinthecyclesinducedbyspecic groupelementsonrepresentativetracezeroelements.SeeAppendixAfordetails. TZ ERO := recformat < rep : ORep , O 1 : car < f i : i in [ 1 :: # Xblock ] g , f j : j in [ 1 :: 3 h ] g > , O 2 : car < f i : i in [ 1 :: # XO ] g , f j : j in [ 1 :: q )]TJ/F41 10.8792 Tf 9.298 0 Td [(1 ] g >> ; TZ :=[ rec < TZ ERO j rep := ORep [ i ] > : i in [ 1 :: # ORep ]] ; for i in [ 1 :: # Xblock ] do for j in [ 1 :: # Xblock [ i ]] do TZ [ I NDEX ORep , Xblock [ i ][ j ]] O 1 := < i , j > ; endfor ; endfor ; for i in [ 1 :: # XO ] do 62

PAGE 71

for j in [ 1 :: # XO [ i ]] do TZ [ I NDEX ORep , XO [ i ][ j ]] O 2 := < i , j > ; endfor ; endfor ; Itisecienttosorttherecordsaccordingtothesizeoftheorbitofthetracezero elementunder Z 1 ;wemaintainseparatesequencesofthetracezeroelements,andthe recordsassociatedwiththem,eachinthesameorder.Thememoryusedtostorethis redundantinformationismadeupforinthetimesavedaccessingtheinformation. forward m ; S ORT TZ , func < x , y j # Xblock [ x O 1 [ 1 ]] )]TJ/F41 10.8792 Tf 13.686 0 Td [(# Xblock [ y O 1 [ 1 ]] > , m ; ORep := f @ ORep [ i m ]: i in [ 1 :: # ORep ] @ g ; Fordetailsontheformationof A ,seeAppendixA. O2block := f @ f @ TZ [ j ] O 1 [ 1 ] : j in [ I NDEX ORep , x : x in XO [ TZ [ i ] O 2 [ 1 ]]] @ g : i in [ 1 :: # ORep ] @ g ; R := f @I NDEX ORep , Xblock [ O2block [ i ][ 1 ]][ 1 ]: i in [ 1 :: # O2block ] @ g ; Cy :=[[ T RACE E ! x , F : x in C YCLE C : 1, XO [ i ][ 1 ]]: i in [ 1 :: # XO ]] ; yC :=[ R OTATE R EVERSE Cy [ i ] ,1 : i in [ 1 :: # Cy ]] ; OO2 :=[[ Fstar [ x [ 2 ]] yC [ x [ 1 ]][ j ]: j in [ 1 :: # Cy [ x [ 1 ]]]] where x := TZ [ R [ i ]] O 2 : i in [ 1 :: # R ]] ; M 2 := func < i , j j # f k : k in [ 1 :: r ] j OO2 [ i ][ k ]+ Fstar [ x [ 2 ]] Cy [ x [ 1 ]][ k ] eq 0 where x := TZ [ j ] O 2 g > ; S :=[ P OWER S EQUENCE R ATIONALS j ] ; for i in [ 1 :: # R ] do s :=[ M 2 i , j : j in [ 1 :: # ORep ]] ; A PPEND S , s ; 63

PAGE 72

endfor ; O1P :=[[ TZ [ I NDEX ORep , x ORep [ j ]] O 1 [ 1 ]: j in [ 1 :: # ORep ]]: x in Fstar ] ; M := function i , j d := exists k , s f < m , n > : m in [ 1 :: # R ] , n in [ 1 :: # Fstar ] j TZ [ I NDEX ORep , ORep [ R [ m ]] Fstar [ n ]] O 1 [ 1 ] eq i g ; return & +[ S [ k ][ x ]: x in [ 1 :: # O1P [ s ]] j O1P [ s ][ x ] eq j ] ; endfunction ; A := S YMMETRIC M ATRIX R ATIONALS ,& cat [[ M i , j : i in [ 1 :: j ]]: j in [ 1 :: n ]] )]TJ/F41 10.8792 Tf 13.686 0 Td [(S CALAR M ATRIX R ATIONALS , n ,1 ; Thisloopadjuststhevaluesofthematrixiftheorbitsarenotallthesamesize,which occurswhen q 0mod3orwhen3divides h . s :=[ # Xblock [ i ]: i in [ 1 :: # Xblock ]] ; for i in [ 1 :: n )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 ] do for j in [ i + 1 :: n ] do A [ i , j ]:= A [ i , j ]/ s [ j ]/ s [ i ] ; endfor ; endfor ; Wenowndtheeigenspacefor ,anddeneafunction FindL whichwillsearchfor atightsetwithagivenparameter t andreturnthesetsoforbitrepresentativestrace zeroelementsof Estar correspondingtoanytightsetsfound. Ba := B ASIS E IGENSPACE A , ; FindL := procedure t , L := R ATIONALS ! t / q 2 )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 ; e := 1 )]TJ/F19 11.9552 Tf 9.298 0 Td [( ; f := )]TJ/F19 11.9552 Tf 9.298 0 Td [( ; 64

PAGE 73

Sincethebasisvectorsfortheeigenspacefor arenormalized,avectorwithallentries equalto e or f mustbealinearcombinationofthesebasisvectorswithallweights equalto e or f ;wesearchoverallsuchlinearcombinationsfortightsets. for c in C ARTESIAN P OWER f 0,1 g ,# Ba do s :=[ c [ i ] eq 1 select e else f : i in [ 1 :: # Ba ]] ; v := & +[ s [ i ] Ba [ i ]: i in [ 1 :: # Ba ]] ; ifforall f i : i in [ 1 :: n ] j v [ i ] in f e , f gg then A PPEND L ,& join f Xblock [ i ]: i in [ 1 :: n ] j v [ i ] eq e g ; print v ; endif ; endfor ; endprocedure ; B.4CLbcirc.mgm Thiscodesearchesfortightsetsof Q + ;q asdescribedinChapter4when q 1mod4,byformingablockcirculantmatrixforthetacticaldecomposition.The requirementsfortheparametersintheshellareasfollows: p 1mod4 ; e =1 ; and t =Rationals = 2 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 : WemustalsohaveloadedtheCLpreamble.mgmle. Wedenethesubgroup Z 3 = h z 4 i Z 2 ;groupsaredenedtoactonthetrace zeroelementsof E tosavememory. Z 3 := sub < Z 2 j z 4 > ; Xblock containstheorbitsonthetracezeroelementsunder h Z 1 , Z 3 i .Weorder theseorbitsaccordingtowhetherlog x 0 ; 1 ; 2 ; 3mod4,asdescribedinChapter4. 65

PAGE 74

Thisway, XO [ i ][ k ]istheorbitgivenby ! k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 XO [ i ][ 1 ]for1 k 4,where XO [ i ][ 1 ] isanorbitcontainingelementswithlog x 0mod4. Xblock := O RBITS sub < Gr j Z 1 , Z 3 > ; n := # Xblock ; S ORT Xblock , func < x , y j # x )]TJ/F41 10.8792 Tf 13.686 0 Td [(# y > ; S ORT Xblock , func < x , y j L OG x [ 1 ] mod 4 )]TJ/F15 11.9552 Tf 13.686 0 Td [( L OG y [ 1 ] mod 4 > ; XO := f @ Xblock [ i ] Z 2 : i in [ 1 :: n ] @ g ; n := n div 4; Thefollowingalgorithmisusedtogeneratethematrixcorrespondingtothetactical decompositionof Q + ;q inducedbythegroup h C , Z 1 , Z 3 i ;seethedetailsin AppendixA. Cy :=[[[ T RACE E ! x , F : x in C YCLE C : 1, y ]: y in XO [ i ][ 1 ]]: i in [ 1 :: # XO ]] ; OO2 :=[ R OTATE R EVERSE Cy [ i ][ 1 ] ,1 : i in [ 1 :: n ]] ; M := func < i , j , k j & +[ # f z : z in [ 1 :: r ] j OO2 [ i ][ z ]+ Fstar [ k ] Cy [ j ][ x ][ z ] eq 0 g : x in [ 1 :: # Cy [ j ]]] > ; Ablock :=[ S YMMETRIC M ATRIX R ATIONALS ,& cat [[ M i , j , k : i in [ 1 :: j ]]: j in [ 1 :: n ]] : k in [ 1 :: 3 ]] ; if q mod 3 eq 0 then s := 3; for i in [ 1 :: 3 ] do for j in [ 2 :: n ] do Ablock [ i ][ 1, j ]:= Ablock [ i ][ 1, j ]/ s ; endfor ; endfor ; 66

PAGE 75

endif ; Ablock [ 1 ]:= Ablock [ 1 ] )]TJ/F41 10.8792 Tf 13.686 0 Td [(S CALAR M ATRIX R ATIONALS , n ,1 ; Ablock [ 4 ]:= Ablock [ 2 ] ; Theeigenvectorsoftheblocksymmetricmatrixarenowconstructedoverthecyclotomiceld R [ ]:= Q [ i ].Weareonlyinterestedinrealvaluedeigenvectors.For theseexamples,forallvaluesof q whicharefeasiblecomputationally,wegetaonedimensionaleigenspaceof H [ 1 ]= Ablock [ 1 ] )]TJ/F40 10.8792 Tf 9.299 0 Td [(Ablock [ 3 ],givingeigenvectorswhichcorrespondto = 2 q 2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1-tightsetsinessentiallyfourequivalentways. R <> := C YCLOTOMIC F IELD 4 ; H :=[ & +[ j i )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 Ablock [ i ]: i in [ 1 :: 4 ]]: j in [ 1 :: 4 ]] ; H [ 1 ] ; v := B ASIS E IGENSPACE H [ 1 ] , q 2 )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 [ 1 ] ; A := H ORIZONTAL J OIN [ V ERTICAL J OIN [ Ablock [ 1 + i )]TJ/F40 10.8792 Tf 9.299 0 Td [(j mod 4 ] : i in [ 0 :: 3 ]]: j in [ 0 :: 3 ]] ; Thisloopputstogetherasetoftheorbitrepresentativesforeachofthefour t -tight sets.Needsomeexplanationofthemethod,whichisbasedonconjecture.The sequence L consistsofasequenceofsetsoforbitrepresentatives,eachcorresponding toa t -tightset. := R ATIONALS ! t / q 2 )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 ; e := 1 )]TJ/F19 11.9552 Tf 9.298 0 Td [( ; f := )]TJ/F19 11.9552 Tf 9.298 0 Td [( ; Sp := & cat [[ < j , k > : k in [ 1 :: n ]]: j in [ 1 :: 4 ]] ; v := V ECTOR [ R ATIONALS j I NTEGERS ! Ablock [ 2 ][ i ,1 ] mod 2 )]TJ/F19 11.9552 Tf 13.686 0 Td [( : i in [ 1 :: n ]] ; for c in C ARTESIAN P OWER f 1,2 g ,2 do u := V ECTOR & cat [ E LTSEQ )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 c [ 1 ] v , 67

PAGE 76

E LTSEQ )]TJ/F41 10.8792 Tf 9.298 0 Td [(1 c [ 2 ] v , E LTSEQ )]TJ/F41 10.8792 Tf 9.298 0 Td [(1 c [ 1 ]+ 1 v , E LTSEQ )]TJ/F41 10.8792 Tf 9.298 0 Td [(1 c [ 2 ]+ 1 v ] ; if u A eq u then A PPEND L ,& join f XO [ Sp [ i ][ 2 ]][ Sp [ i ][ 1 ]] : i in [ 1 :: # Xblock ] j u [ i ] eq e g ; print u ; endif ; endfor ; B.5CLvspace.mgm Thiscodeincludesdenitionsofvariousvectorspaces,aswellasmapstoimplementtheKleincorrespondence.Itisrequiredforallofthecodeintheproceeding sections. Webeginbydeningourvectorspaces V and W ,andourbilinearform. V := V ECTOR S PACE E ,2 ; W , := V ECTOR S PACE V , F ; B := func < u , v j T u [ 1 ] v [ 2 ]+ T u [ 2 ] v [ 1 ] > ; Q := func < v j T v [ 1 ] v [ 2 ] > ; BW := func < u , v j B )]TJ/F41 8.7034 Tf 9.298 0 Td [(1 u , )]TJ/F41 8.7034 Tf 9.298 0 Td [(1 v > ; QW := func < v j Q )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 v > ; OForm := M ATRIX F , [[ BW B ASIS W [ i ] ,B ASIS W [ j ] : i in [ 1 :: 6 ]]: j in [ 1 :: 6 ]] ; Wenowndabasisfor W underwhichwecanusethestandardPluckercoordinates fortheKleincorrespondence. Ba :=[ B ASIS W [ 1 ]] ; 68

PAGE 77

Ba := A PPEND Ba , a where a := rep f x : x in W j QW x eq 0 and BW Ba [ 1 ] , x ne 0 g ; for i in [ 1 :: 3 ] do Ba [ 2 i )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 ]:= BW Ba [ 2 i )]TJ/F41 10.8792 Tf 9.299 0 Td [(1 ] , Ba [ 2 i ] )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 Ba [ 2 i )]TJ/F41 10.8792 Tf 9.298 0 Td [(1 ] ; Ba [ 2 i ]:= QW Ba [ 2 i ] Ba [ 2 i )]TJ/F41 10.8792 Tf 9.298 0 Td [(1 ]+ Ba [ 2 i ] ; if i ne 3 then Ba := A PPEND Ba , a where a := rep f x : x in N ULLSPACE OForm T RANSPOSE M ATRIX [ Ba [ k ]: k in [ 1 :: 2 i ]] j x ne 0 and QW x eq 0 g ; Ba := A PPEND Ba , a where a := rep f x : x in N ULLSPACE OForm T RANSPOSE M ATRIX [ Ba [ k ]: k in [ 1 :: 2 i ]] j x ne 0 and QW x eq 0 and BW Ba [ 2 i + 1 ] , x ne 0 g ; endif ; endfor ; Ba :=[ Ba [ 1 ] , Ba [ 3 ] , Ba [ 5 ] , Ba [ 6 ] , Ba [ 4 ] , Ba [ 2 ]] ; WBa := M ATRIX F ,6,6, Ba )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 ; Weredene tomap V ! W insuchawaythatwecanusethestandardorthogonal formforthequadric. := map < V ! W j v 7! v WBa , w 7! )]TJ/F41 8.7034 Tf 9.298 0 Td [(1 w WBa )]TJ/F41 8.7034 Tf 9.298 0 Td [(1 > ; WForm := M ATRIX F , [[ BW Ba [ i ] , Ba [ j ]: i in [ 1 :: 6 ]]: j in [ 1 :: 6 ]] ; BW := func < u , v j B )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 u , )]TJ/F41 8.7034 Tf 9.298 0 Td [(1 v > ; QW := func < v j Q )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 v > ; Wenowdenethevectorspace U whichwillunderliePG3 ;q ; : U ! W and : W ! U givetheKleincorrespondence. 69

PAGE 78

U := V ECTOR S PACE F ,4 ; := func < x j R OWSPACE M ATRIX F ,4,4, [[ 0, x [ 1 ] , x [ 2 ] , x [ 3 ]] , [ )]TJ/F40 10.8792 Tf 9.299 0 Td [(x [ 1 ] ,0, x [ 4 ] , )]TJ/F40 10.8792 Tf 9.299 0 Td [(x [ 5 ]] , [ )]TJ/F40 10.8792 Tf 9.299 0 Td [(x [ 2 ] , )]TJ/F40 10.8792 Tf 9.298 0 Td [(x [ 4 ] ,0, x [ 6 ]] , [ )]TJ/F40 10.8792 Tf 9.299 0 Td [(x [ 3 ] , x [ 5 ] , )]TJ/F40 10.8792 Tf 9.298 0 Td [(x [ 6 ] ,0 ]] > ; p K := func < line , j , k j D ETERMINANT M ATRIX F ,2,2, [[ B ASIS line [ 1 ][ j + 1 ] ,B ASIS line [ 1 ][ k + 1 ]] , [ B ASIS line [ 2 ][ j + 1 ] ,B ASIS line [ 2 ][ k + 1 ]]] > ; := func < line j B ASIS sub < W j [ p K line ,0,1 , p K line ,0,2 , p K line ,0,3 , p K line ,1,2 , p K line ,3,1 , p K line ,2,3 ] > [ 1 ] > ; B.6CLpg3q.mgm Thiscoderequires CLvspace.mgm inordertorun. WesetupthegroupactingonPG ;q ,andit'sactiononthelines. G , P := PG AMMA L U ; PointsU := func < line j f I NDEX P ,N ORMALIZE B ASIS line [ 2 ] g join f I NDEX P ,N ORMALIZE B ASIS line [ 1 ]+ x B ASIS line [ 2 ] : x in F g > ; Lines := PointsU sub < U j P [ 1 ] , P [ 2 ] > G ; Lines := GS ET G , Lines ; , GL := A CTION G , Lines ; HerewedenetheactionofourcyclicgrouponPG ;q . CU := )]TJ/F41 8.7034 Tf 9.298 0 Td [(1 sub < GL j [ PointsU V ! [ v [ 1 ] ne 0 select v [ 1 ] C : 1 else 0, v [ 2 ] ne 0 select v [ 2 ] C : )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 else 0 ] 70

PAGE 79

where v is )]TJ/F41 8.7034 Tf 9.298 0 Td [(1 sub < U j P [ l [ 1 ]] , P [ l [ 2 ]] > where l isrep f < a , b > : a , b in Lines [ i ] j a ne b g : i in [ 1 :: # Lines ]] > ; Thefunction LU mapsourorbitrepresentativestoasetoflinesinPG ;q . LU := func < L j & join f @ PointsU V ! [ 1, x ] CU : x in L @ g > ; B.7CLint.mgm Thiscoderequires CLvspace.mgm inordertorun. H , N := PGOP LUS W ; Hprime := S UBGROUPS H : I NDEX E QUAL := 2 [ 1 ] subgroup ; CW := sub < H j [ I NDEX N ,N ORMALIZE V ! [ z [ 1 ] , )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 z [ 2 ]] where z is )]TJ/F41 8.7034 Tf 9.299 0 Td [(1 x : x in N ] > ; LW := func < L j & join f I NDEX N ,N ORMALIZE V ! [ 1, x ] CW : x in L g > ; intStar := function WCL 1 := f I NDEX N ,N ORMALIZE V ! [ x ,0 ]: x in Estar g ; Stars := 1 Hprime ; return f # WCL meet : in Stars g ; endfunction ; intPlane := function WCL 2 := f I NDEX N ,N ORMALIZE V ! [ 0, y ]: y in Estar g ; Planes := 2 Hprime ; return f # WCL meet : in Planes g ; endfunction ; B.8CL81int.mgm 71

PAGE 80

Thiscoderequires CLvspace.mgm inordertorun. G , P := PG AMMA L U ; aC :=[ k : k in [ 1 :: r ]] ; Ca := R EVERSE aC ; R OTATE aC ,1 ; CW := func < x jf @ V ! [ aC [ i ] , Ca [ i ] x ]: i in [ 1 :: r ] @ g > ; ULines := P ARENT V ! [ 1, ORep [ 1 ]] WBa ; LW := function LRep LL :=[ ULines j ] ; for x in LRep do for v in CW x do A PPEND LL , v ; endfor ; endfor ; return LL ; endfunction ; LWd := function LRep LL :=[ ULines j ] ; for x in LRep do for v in CW x do A PPEND LL , V ! [ v [ 2 ] , v [ 1 ]] ; endfor ; endfor ; return LL ; endfunction ; 72

PAGE 81

intStar := function UCL INT := f I NTEGERS jg ; for x in P do xINT := # f v : v in UCL j x in v g ; I NCLUDE INT , xINT ; endfor ; return INT ; endfunction ; intPlane := function UCL INT := f I NTEGERS jg ; N V :=[ N ULLSPACE T RANSPOSE M ATRIX [ B ASIS v [ 1 ] ,B ASIS v [ 2 ]] : v in UCL ] ; for x in P do xINT := # f i : i in [ 1 :: #N V ] j x in N V [ i ] g ; I NCLUDE INT , xINT ; endfor ; return INT ; endfunction ; B.9MNset.mgm Thiscoderequires CLvspace.mgm inordertorun. aC :=[ k : k in [ 1 :: r ]] ; Ca := R EVERSE aC ; R OTATE aC ,1 ; CW := func < x jf @ V ! [ aC [ i ] , Ca [ i ] x ]: i in [ 1 :: r ] @ g > ; ULines := P ARENT V ! [ 1, ORep [ 1 ]] WBa ; 73

PAGE 82

:= N ULLSPACE T RANSPOSE M ATRIX U ! [ 1,0,0,0 ] ; piW := sub < W j sub < U j B ASIS [ 1 ] ,B ASIS [ 2 ] > , sub < U j B ASIS [ 1 ] ,B ASIS [ 3 ] > , sub < U j B ASIS [ 2 ] ,B ASIS [ 3 ] > > ; LWpi := function LRep LL :=[ ULines j ] ; for x in LRep do for v in CW x do if v in piW then A PPEND LL , v ; endif ; endfor ; endfor ; return LL ; endfunction ; MN := function UCL UCLpi := LWpi UCL ; l := f x : x in j # f v : v in UCLpi j x in v g eq # UCLpi div q + 1 g ; l := sub < j l > ; Bp := E XTEND B ASIS l , ; Bp :=[ Bp [ 3 ] , Bp [ 1 ] , Bp [ 2 ]] ; H , N := PGL 3, q ; mn := f # f v : v in UCLpi j x in v g : x in g ; m := M IN mn ; 74

PAGE 83

K := f N ORMALIZE V ECTOR F ,C OORDINATES V ECTOR S PACE W ITH B ASIS Bp , x : x in j # f v : v in UCLpi j x in v g eq m g ; K := f [ x [ 2 ] , x [ 3 ]]: x in K g ; return K ; endfunction ; KStab := function mnSet H , J := AG AMMA L 2, q ; K := f I NDEX J , x : x in mnSet g ; S := S TABILIZER H , K ; return S ; endfunction ; 75

PAGE 84

REFERENCES [1]S.Ball,A.Blokhuis,andF.Mazzocca.Maximalarcsindesarguesianplanesof oddorderdonotexist. Combinatorica ,17:31{41,1997.10.1007/BF01196129. [2]J.Bamberg,S.Kelly,M.Law,andT.Penttila.Tightsetsand m -ovoidsofnite polarspaces. JournalofCombinatorialTheory,SeriesA ,114:1293{1314, 2007. [3]J.Bamberg,M.Law,andT.Penttila.Tightsetsand m -ovoidsofgeneralised quadrangles. Combinatorica ,29:1{17,2009. [4]W.Bosma,J.Cannon,andC.Playoust.TheMagmaalgebrasystem.I.Theuser language. J.SymbolicComput. ,24-4:235{265,1997.Computationalalgebra andnumbertheoryLondon,1993. [5]A.A.BruenandK.Drudge.Onthenon-existenceofcertainCameron{Liebler lineclassesinPG ;q . Designs,CodesandCryptography ,14:127{132,1998. [6]A.A.BruenandK.Drudge.TheconstructionofCameron{Lieblerlineclassesin PG ;q . FiniteFieldsandTheirApplications ,5:35{45,1999. [7]R.CalderbankandW.M.Kantor.Thegeometryoftwo-weightcodes. Bulletin oftheLondonMathematicalSociety ,18:97{122,1986. [8]P.J.CameronandR.A.Liebler.Tacticaldecompositionsandorbitsofprojective groups. LinearAlgebraanditsApplications ,46:91{102,1982. [9]J.DeBeule,P.Govaerts,A.Hallez,andL.Storme.Tightsets,weighted m covers,weighted m -ovoids,andminihypers. Designs,CodesandCryptography , 50:187{201,2009. [10]J.DeBeule,A.Hallez,andL.Storme.Anon-existenceresultonCameron{ Lieblerlineclasses. JournalofCombinatorialDesigns ,16:342{349,2008. [11]R.H.F.Denniston.Somemaximalarcsinniteprojectiveplanes. Journalof CombinatorialTheory ,6:317{319,1969. [12]K.Drudge. Extremalsetsinprojectiveandpolarspaces .PhDthesis,University ofWesternOntario,1998. [13]K.Drudge.OnaconjectureofCameronandLiebler. EuropeanJournalof Combinatorics ,20:263{269,1999. [14]P.GovaertsandT.Penttila.Cameron{LieblerlineclassesinPG ; 4. Bulletin oftheBelgianMathematicalSociety{SimonStevin ,12:793{804,2005. 76

PAGE 85

[15]P.GovaertsandL.Storme.OnCameron{Lieblerlineclasses. Advancesin Geometry ,4:279{286,2004. [16]L.C.Grove. ClassicalGroupsandGeometricAlgebra .AmericanMathematical Society,2002. [17]W.H.Haemers.Interlacingeigenvaluesandgraphs. LinearAlgebraanditsApplications ,226{228:593{616,1995. [18]J.Hirschfeld. ProjectiveGeometriesoverFiniteFieldsOxfordMathematical Monographs .OxfordUniversityPress,USA,2edition,1998. [19]D.R.HughesandF.C.Piper. ProjectivePlanes .Springer-VerlagNewYork,, 1973. [20]R.LidlandH.Niederreiter. FiniteFieldsEncyclopediaofMathematicsandits Applications .CambridgeUniversityPress,1996. [21]R.Mathon.Newmaximalarcsindesarguesianplanes. JournalofCombinatorial Theory,SeriesA ,97:353{368,2002. [22]K.Metsch.Thenon-existenceofCameron{Lieblerlineclasseswithparameter 2
PAGE 86

[31]J.Thas.Constructionofmaximalarcsandpartialgeometries. Geometriae Dedicata ,3:61{64,1974. [32]J.Thas.Constructionofmaximalarcsanddualovalsintranslationplanes. EuropeanJournalofCombinatorics ,1:189{192,1980. [33]J.Tits. BuildingsofSphericalTypeandFinite BN -pairs .Springer-Verlag,1974. 78