Citation

## Material Information

Title:
Hyperovals and cyclotomic sets in AG(2,q)
Creator:
DeOrsey, Philip A. ( author )
Place of Publication:
Denver, CO
Publisher:
Publication Date:
Language:
English
Physical Description:
1 electronic file (94 pages). : ;

## Thesis/Dissertation Information

Degree:
Master's ( Master of Science)
Degree Grantor:
Degree Divisions:
Department of Mathematical and Statistical Sciences, CU Denver
Degree Disciplines:
Applied mathematics

## Subjects

Subjects / Keywords:
Polynomials ( lcsh )
Vector spaces ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

## Notes

Review:
In this dissertation we introduce a new polynomial representation of hyperovals called a p-polynomial. The p-polynomial is defined in AG(2,q) and uses a representation of the points of AG(2,q) as elements of GF(q2). We provide structural results of p-polynomial linking properties of their coefficients to specific maps that stabilize the represented hypervoval. Additionally, we provide a connection between p-polynomials and o-polynomials, and give nice p-polynomial representations for several families of hyperovals. We also study the orbits of the field automorphisms of GF(q2) which induce collineations if AG(2,q). We call these orbits cyclotomic sets, and note that cyclotomic sets can be many different structures. We cyclotomic arcs to build hyperovals, and perform searches for new hyperovals in affine planes of small order. We find no new hyperovals, but these searches classify p-polynomial with specific properties in certain affine planes. In the final chapter we study other structures that appear as cyclotomic sets. We show that configurations can be represented and provide new results on configurations in order to determine when they can appear. We also provide a description of when as cyclotomic set represents each of the other structures they are known to represent.
Thesis:
Thesis (Ph.D.)--University of Colorado Denver. Applied mathematics
Bibliography:
Includes bibliographic references.
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Philip A. DeOrsey.

## Record Information

Source Institution:
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
910743439 ( OCLC )
ocn910743439

Full Text
HYPEROVALS AND CYCLOTOMIC SETS IN AG(2,q)
by
PHILIP A. DEORSEY
Doctor of Philosophy, University of Colorado Denver, 2015
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
2015

This thesis for the Doctor of Philosophy degree by Philip A. DeOrsey has been approved for the
Department of Mathematical and Statistical Sciences
by
William Cherowitzo, Advisor Michael Ferrara, Chair Stanley Payne Tim Penttila Jason Williford
April 22, 2015
n

DeOrsey, Philip A. (Ph.D., Applied Mathematics) Hyperovals and Cyclotomic Sets in AG(2,q)
Thesis directed by Professor Emeritus William Cherowitzo
ABSTRACT
In this dissertation we introduce a new polynomial representation of hyperovals called a p-polynomial. The p-polynomial is defined in AG(2, q) and uses a representation of the points of AG(2, q) as elements of GF(q2). We provide structural results of p-polynomials linking properties of their coefficients to specific maps that stabilize the represented hyperoval. Additionally, we provide a connection between p-polynomials and o-polynomials, and give nice p-polynomial representations for several families of hyperovals.
We also study the orbits of the held automorphisms of GF(q2) which induce collineations in AG(2,q). We call these orbits cyclotomic sets, and note that cyclotomic sets can be many different structures. We use cyclotomic arcs to build hyperovals, and perform searches for new hyperovals in affine planes of small order. We find no new hyperovals, but these searches classify p-polynomials with specific properties in certain affine planes.
In the final chapter we study other structures that appear as cyclotomic sets. We show that configurations can be represented and provide new results on configurations in order to determine when they can appear. We also provide a description of when a cyclotomic set represents each of the other structures they are known to represent.
The form and content of this abstract are approved. I recommend its publication.
Approved: William Cherowitzo

ACKNOWLEDGMENT
First and foremost I would like to thank my wife Tiffany for supporting me throughout this process. Completing my degree took many years of effort and struggle. You are always there to support and encourage me, keeping me level-headed and my eyes on the prize. Thank you Tiffany for your unconditional support and love, I could not have done any of this without you.
I must thank my advisor Bill Cherowitzo for sticking with me through the years. I know I am not the easiest Ph.D. student to advise but you stuck with me through it all. Your calm demeanor was a nice complement to my anxiousness, and helped keep me focused and less worried. You always kept me moving in the right direction with guidance and suggestions for what to do next. You have advised me in more than just my research, you have guided me in teaching, life, and more. Thank you for everything, Bill.
Thanks to the rest of my committee Jason, Mike, Stan, and Tim who gave me many guiding remarks and ideas that helped me finish everything. I have had many discussions with each of you over the years and I truly value each and every minute. Specifically I want to thank Mike Ferrara who had to deal with me more than most. Thanks for guiding me and always being there to discuss anything.
I would like to acknowledge Anton Betten who collaborated with me on much of the computational side of this research. Thank you for taking time out of your busy schedule to work with me.
I would be remiss if I did not mention my undergraduate advisor and friend Mark Miller who introduced me to finite geometry. Thank you Mark for your support and the introduction to such a beautiful side of mathematics.
Finally, thanks to my family, my parents Ken and Elbe, and my siblings Mike, Dave, Michelle, Paul, Maureen, and Lee. You all provided me with motivation without even knowing it. I always strive to make you all proud.
IV

Figures ................................................................... vii
Tables.................................................................... viii
Chapter
1. Introduction and Background............................................... 1
1.1 Overview............................................................ 1
1.2 Background on Finite Fields......................................... 2
1.3 Background on PG(2, q).............................................. 3
1.4 Background on Hyperovals............................................ 6
1.5 A History of Hyperovals............................................. 9
2. The p-polynomial Representation.......................................... 14
2.1 A Description of the Polar Model .................................. 14
2.2 Collineations in the Polar Model................................... 18
2.3 Using p-polynomials to Represent Hyperovals........................ 21
2.4 Structural Properties of p-polynomials............................. 24
2.4.1 Basic Structural Properties.................................. 25
2.4.2 Hyperovals Stabilized by Field Automorphisms............ 26
2.4.3 Hyperovals Stabilized by Multiplicative Maps................. 28
2.5 The Relationship to o-polynomials.................................. 30
2.6 The p-polynomials for Known Hyperovals............................. 33
2.6.1 Hyperconic................................................... 33
2.6.2 Translation Hyperovals....................................... 41
2.6.3 The Segre Hyperoval.......................................... 45
2.6.5 The Subiaco Hyperoval ............................. 50
2.6.6 Other Families............................................... 54
3. A Computational Approach................................................. 56
v

3.1 Cyclotomic Sets................................................... 56
3.2 Using p-polynomials to Search for Hyperovals...................... 57
3.2.1 Searches in AG(2,16)........................................ 60
3.2.2 Searches in AG(2,32)........................................ 61
3.2.3 Searches in AG(2,64)........................................ 63
3.2.4 Searches in AG(2,128)....................................... 63
3.2.5 Searches in AG(2,256)....................................... 64
3.2.6 Searches in AG(2,512)....................................... 67
4. Structures represented by Cyclotomic Sets............................ 69
4.1 Determining Generating Blocks..................................... 71
4.2 Cyclotomic Sets as Geometric Structures........................... 74
4.3 Examples.......................................................... 79
4.3.1 AG(2,16).................................................... 79
4.3.2 AG(2,64).................................................... 80
4.3.3 AG(2,256) and Larger Planes................................. 81
4.4 Open Questions.................................................... 82
References.............................................................. 83
vi

FIGURES
Figure
1.1 Desargues Configuration................................................. 4
2.1 The Polar Representation of AG(2,q).................................... 18
3.1 A Sector with a Cyclotomic Set ........................................ 57
4.1 PG(2,2): The Fano Plane................................................ 70
4.2 Incidence matrix for C3 [7,1,3]........................................ 71
4.3 C3[8,1, 3]: A Mobius-Kantor configuration found in AG(2,16)............ 80
4.4 Configurations found as cyclotomic sets in AG(2,64) 81
vii

TABLES
Table
1.1 o-polynomials for known hyperovals....................................... 9
1.2 The groups of known hyperovals ......................................... 13
3.1 Run Times for Backtrack Searches........................................ 58
3.2 Run Times for Clique Finder............................................. 59
3.3 p-polynomials for hyperovals in AG(2,16) ............................... 61
3.4 p-polynomials for hyperovals in AG(2, 32) 62
3.5 p-polynomials for hyperovals in AG(2, 64) .............................. 63
3.6 p-polynomials for hyperovals in AG(2,128)............................... 65
3.7 p-polynomials for hyperovals in AG(2,128) (2)........................... 66
3.8 p-polynomials for hyperovals in AG(2, 256).............................. 67
viii

1. Introduction and Background
1.1 Overview
The main focus of this work is to study a new representation of hyperovals that we call a p-polynomial. The p-polynomial is an extension of work done by Chris Fisher and Bernhard Schmidt where they use finite Fourier series to represent hyperovals. Flyperovals have traditionally been represented by polynomials called o-polynomials which have become increasingly complicated as new examples have been discovered. It has been over a decade since a new hyperoval has been discovered, which is long, considering hyperovals have only been studied significantly for 50 years. With this motivation we are in need of some new perspective for studying hyperovals, so we suggest the use of p-polynomials.
We study the structural properties of p-polynomials via their coefficients. Where Fisher and Schmidt looked for representations where many coefficients were 0, we consider hyperovals with coefficients in certain subfields, and with specific coefficients being 0. While studying p-polynomials one notices that if the coefficients of the polynomials have certain properties then that implies specific maps stabilize the hyperoval it represents. The orbits of these maps can be used as building blocks of hyperovals which leads to new and interesting searches for hyperovals. This approach has some precedent as it was used by OKeefe and Penttila in [31], Penttila and Pinneri in [40], and Pentilla and Royle in [42], We will discuss the results of these searches in affine planes of small order, and give p-polynomial representations for all of the known families of hyperovals in these planes. Further, we give p-polynomial representations for several families of hyperovals in all planes.
Among the actions that we are particularly interested in are the held automorphisms of GF(q2) which induce collineations in AG(2,q). The orbits of these automorphisms are structures in AG(2,q) that we call cyclotomic sets. If these sets are arcs then we can use them to build hyperovals. However, as it turns out, they are not
1

always arcs. We found that these sets can represent other structures, including line segments and grids, but the more interesting configurations can arise. We determine when a cyclotomic set can be each of these different structures. In doing so, we obtain some new results on configurations.
1.2 Background on Finite Fields
A finite field is an algebraic structure with two operations called addition and multiplication. The order of a finite field is the number of elements in the field. Any finite field has order q = ph for some prime p and h a positive integer. We will use the notation GF(q) to denote the finite field of order q. The prime p is called the characteristic of the field; it is the least integer p for which Y^Pj=i 1 = 0. The elements of GF(g) under addition form an abelian group, and the nonzero elements of GF(q), denoted GF(q)*, form a cyclic group under multiplication. A generator of the multiplicative group is called a primitive element of GF(q).
A subfield of GF (q) is a subset of the elements that is a field under the same operations. A subfield of GF(ph) of order pk exists if and only if k \ h. The prime subfield of GF(ph) is the intersection of all subfields, and is isomorphic to GF(p). Finite fields of order ph exist for all primes p and all positive integers h. Furthermore, there is a unique field up to isomorphism of each order.
The group of automorphisms of GF(ph) is generated by the map a : x > xp, which is called the Frobenius automorphism. Hence, the group of automorphisms of GF(q) is Aut(GF(g)) = {u : x > xpr : 1 < r < h}.
A map that is of particular interest to us is the relative trace map. Let F = GF(q), E = GF(qh), and a e E. The relative trace map from E to F, TE/F : E > F is defined as
Te/f(o) = a + aq + ar + + aqh
The relative trace map is additive and invariant under automorphisms, that is
TE/F(a + b) = TE/F(a) + TE/F(b) for all a,b E E, and
2

TE/F(cia) = Te/f(o) for all a G E and all a G Aut(If).
If F is the prime subfield of E then we call this map the absolute trace map. The absolute trace map is frequently used, so we reserve the notation tr to denote it. The relative trace map from GF(q2) onto GF(q) will be frequently used, so we will denote this map simply as T(x).
Definition 1.1 The relative trace map from GF(q2) to GF(q) is
T(x) = x + xq.
Another map we are interested in is the relative norm map. The relative norm map from E to F, Ne/f : E > F is defined as
NE/F(a) = al+q+q2+"'+qh^ = aVr.
The elements whose image under the relative norm map is 1 are called norm 1 elements. The form of norm 1 elements is well known and is given in the next theorem.
Theorem 1.2 ([36]) NE/F(a) = 1 if and only if a = bq~l for some b G F.
1.3 Background on PG(2,g)
There are finite projective spaces of dimension n for any n G Z+, but the focus of this work will be on the 2-dimensional projective space called a projective plane. A projective plane is a point-line incidence structure that is defined by the following axioms.
1. Any two distinct points are connected by exactly one line.
2. Any two distinct lines meet at exactly one point.
3. There exists a set of four points no three of which are collinear.
3

The order of a projective plane is defined to be one less than the number of points on a line. In a projective plane of order q there are q2 + q + 1 points, q2 + q + 1 lines, q+ 1 points on every line, and q+ 1 lines through every point. The only known projective planes have order ph where p is a prime, and h > 1 is an integer. It is still an open question as to whether projective planes of non-prime power order exist.
A projective plane of order q can be constructed as a 3-dimensional vector space over GF(q), the finite field with q elements. The points are the 1-dimensional subspaces, and the lines are the 2-dimensional subspaces. Incidence is set-theoretical containment. A projective plane constructed in this manner is denoted PG(2,q). There are projective planes of order q that are not isomorphic to PG(2, q) but we will not discuss them here, see [25] for more information. We often refer to the projective planes constructed in this manner as Desarguesian, since Desargues theorem holds in a projective plane if and only if it is isomorphic to one constructed in this way.
Theorem 1.3 (Desargues) Two triangles are in perspective from a point if and only if they are in perspective from a line.
This work is focused on a substructure of PG(2,q) called AG(2,q). AG(2,q) is
4

the affine plane of order q, and can be constructed by removing any one line from PG(2,q) since all lines are projectively equivalent in PG(2,q). We denote the line removed as Go- The points of AG(2,q) are the points of PG(2,q) not on Go and the lines of AG(2,q) are the lines of PG(2,q), except Go, restricted to the points of AG(2, q).
A collineation is a one-to-one map from a projective plane onto itself that maps collinear points to collinear points. The set of all collineations of a plane is known as the collineation group of the plane. The collineation group of PG(2,q) is denoted PTL(3,q). There are two types of collineations in PG(2,q), homographies and automorphic collineations.
If A is a non-singular 3x3 matrix over GF(q), then the map a : PG(2, q) > PG(2, q) defined by
(x,y,z) -> (x,y,z)A
is called a homography. If a is an automorphism of GF(g) then the map a a : PG(2,g) > PG(2,g) defined by
(x,y,z) -> (G\y",G)
is called an automorphic collineation. An important subgroup of PrL(3,g) is the subgroup consisting of all homographies, denoted PGL(3,g). The following theorem, known as the fundamental theorem of projective geometry, shows that any collineation is the product of the ones described above.
Theorem 1.4 (Fundamental Theorem of Projective Geometry) Every collineation of PG(2, q) can be written as the product of a homography and an automorphic collineation.
One fact that we will use frequently is that PrL(3, q) acts transitively on quadrangles, sets of four points, no three of which are collinear. That is, there exists a collineation mapping any quadrangle to any other quadrangle.
5

Theorem 1.5 ([9]) Given two ordered quadrangles A1A2A3A4 and B1B2B3B4 of PG(2,q), there exists a unique homography a with cr(Ai) = Bi, 1 < i < 4.
We refer to [4], [9], and [24] for more information on PG(2,q).
1.4 Background on Hyperovals
We are interested in studying several structures that exist in projective planes, one of which is an arc. A k-arc in a projective plane is a set of k points, no three of which are collinear. It can be shown that k < q + 2 when q is even, and k < q + 1 when q is odd. A (q + l)-arc is called a oval and a (q + 2)-arc is called a hyperoval. Theorem 1.6 ([9]) The maximum size of an arc in PG(2, q) is q + 2.
Proof: Let A be an arc in PG(2,q) and P be a point on A. Since there are q + 1 lines containing P, A can have at most one point from each of these lines. With the observation that the lines through P partition the plane we see that \A\ < q + 2.
Theorem 1.7 ([9]) When q is odd the maximum size of an arc in PG(2, q) is q+ 1.
Proof: Assume to the contrary that A is an arc in PG(2,q), q odd and that |A| = q + 2. Let P be a point on A. Since there are q + 1 lines through P and there are q+1 other points on A each line through P must meet exactly one of these points. Hence, any line of the plane meets A in either 0 or 2 points. Now, let Q be a point not on A. The lines through Q must meet A in either 0 or 2 points, and they must partition A, hence (q + 2)/2 is an integer, implying q is even, a contradiction.
Theorem 1.8 ([9]) In PG(2,q), q even, every oval is contained in a unique hyperoval.
Proof: Let O be an oval in PG(2,q), q even, and let P be a point on O. Since O has q points distinct from P, and there is a line joining P to each of these points, and q + 1 lines through P, there must be exactly one line tangent to O at P. Therefore, O has q + 1 tangent lines.
6

Now, let Q be a point not on O. Since the lines through Q partition O and q+ 1 is odd, there must be at least one tangent line through Q. Let m be a secant line to O and say m meets O at P and R. We know that there is exactly one tangent line through P and R, and given S E m, S ^ P, R there is at least one tangent line through S. Each tangent line to O meets m in exactly one point, and since there are q + 1 tangent lines there can be at most one tangent line at each point since each point on m sees at least one. Hence, on any secant line, there is exactly one tangent line through each point.
Let X be the intersection of two tangent lines to O. Since X is on two tangent lines it cannot be on any secant lines. However, the lines through X partition O, so every line through X is a tangent line. Therefore, adding X to A produces a set of q + 2 points no three of which are collinear, making A U {X} a hyperoval.
In order to discuss our next theorems we need another definition. A conic is a set of points satisfying an irreducible homogeneous quadratic equation. It is easily shown that conics are ovals, that is, they are a set of q + 1 points, no three of which are collinear.
Theorem 1.9 In PG(2,q), conics are ovals.
Proof: We can verify that conics are ovals by observing that every conic is
projectively equivalent to the set of points {(t,t2,1) : t E Fg} U {(0,1, 0)}.
If we let a, b, c E Fg and consider the matrix
^ a a2 bb2 1
VC C2 1 y
It is a nonsingular Vandermonde matrix and so has nonzero determinant provided a, b, and c are distinct. Hence we must only check that (0,1,0) is not part of any collinear triple. The matrix
7

^ a a2 b b2 1
[oioj
has determinant b a ^ 0 provided a ^ b. Thus a conic is a set of q + 1 points no three of which are collinear.
A famous theorem of B. Segre gives the converse of Theorem f.9 for q odd, that is, in PG(2,q), q odd, all ovals are conics.
Theorem 1.10 (Segres Theorem [47]) In PG(2,q), q odd, all ovals are conics.
Due to Segres theorem all ovals in PG(2,q), q odd, are classified. Thus, we restrict our attention to the case where q is even, that is, q = 2h.
We may assume that a hyperoval contains the fundamental quadrangle (1,0,0), (0,1,0), (0,0,1), (1,1,1), since, by Theorem 1.5, any hyperoval is projec-tively equivalent to one containing these four points. In [24] it is shown that any hyperoval containing the fundamental quadrangle can be represented by a permutation polynomial.
Theorem 1.11 Any hyperoval PL in PG(2,q) with q = 2h, h > 1, containing the fundamental quadrangle can be represented as
D(f) = {(t, f(t), 1)46 GF(q)} U {(1,0, 0), (0,1,0)}
where f is a permutation polynomial of degree at most q 2 with /(0) = 0 and /(1) = 1-
If D(f), as described above, gives a hyperoval we say that / is an o-polynomial. The use of o-polynomials gives a compact and usable form for hyperovals, so they have been the traditional way of describing hyperovals. A representative list of o-polynomials for known families of hyperovals is given in Table 1.1.
8

1.5 A History of Hyperovals
Signficant study of hyperovals dates back to the late 1950s to a paper by Lunelli and See [30] in which they use a computer to search for complete arcs in PG(2,16) as suggested by B. Segre. Their search yielded one hyperoval, up to projective equivalence, that was not a conic. This hyperoval is now known as the Lunelli-Sce hyperoval and can be described by the o-polynomial
fit) = t12 + t10 + qllt8 + f + ift4 + ift2, where q is a primitive element of GF(16) satisfying if = ?/ + !.
Table 1.1: o-polynomials for known hyperovals
Name o-polynomial Field Restriction
Hyper conic [24] m = t2 None
Translation [46] f(t) = t21 (z, h) = 1 None
Segre [2] fit) = t6 h odd
Glynn 1 [19] fit) = G-+4 h odd
Glynn 2 [19] fit) = t^ h odd
Payne [35] fit) = tld + tl/2 + dd h odd
Cherowitzo [10] fit) = ta + ta+2 + t3a+4 h odd
Subiaco [15] See Below None
Adelaide [14] See Below h even
OKeefe-Penttila [31] See Below y4 = Subiaco An o-polynomial for some of the Subiaco hyperovals is
.. d2t4 + d2{i + d + d2)t3 + d2(i + d + d2)t2 + d2t 1
m =-----------------WTdfWTi-----------------+
where tr(l/d) = 1. There is one hyperoval, up to projective equivalence, in the
Subiaco family if h ^ 2 (mod 4) and two hyperovals if h = 2 (mod 4). The above
9

polynomial gives one of the hyperovals when h = 2 (mod 4) and the other can be represented with o-polynomial
fit)
d2t4 + d5t3 + d2t2 + dH (t2 + dt+ l)2

where /5 is an element of multiplicative order q + 1 in GF(q2) and d = [3 + f3q. We also note that 3 different automorphism groups appear among the Subiaco hyperovals. Adelaide An o-polynomial for the Adelaide hyperoval is
m = +1) + (t + T(b)t1/2 +1)1- +w2,
where T(x) = x + xq, b E GF(q2), b f 1, bq+l = 1 and in = ^-OKeefe-Penttila An o-polynomial for the OKeefe-Penttila hyperoval is
f(t) = t4 + tw +128 + nn(t + tw + f14 + f18 +122 +120) + q2U(f + t2U) + /^(t12 +124)
where q is a primitive element of GF(32) satisfying if = if + 1.
The Lunelli-Sce hyperoval does not appear in Table 1.1 as it was shown to be in the Subiaco family in [15] and in the Adelaide family in [14], For more information on the Lunelli-Sce hyperoval see [7].
In 1962, shortly after the work by Lunelli and See, B. Segre gave the translation and Segre hyperovals in [46]. These hyperovals remained the only known hyperovals for over 20 years until Glynn gave two new families in [19]. The Glynn hyperovals were yet more examples of what are called monomial hyperovals, that is hyperovals that can be represented by monomial o-polynomials. These remain the only known examples of monomial hyperovals.
The 1980s saw a surge in new families of hyperovals with Payne giving a new family in [35] and Cherowitzo providing examples of a new family in [11]. The Cherowitzo hyperovals were proved to be a family in 1998 [10]. The time between the discovery of the first examples of the Cherowitzo hyperovals and the proof of their inclusion in an
infinite family was over a decade and new techniques had to be developed to prove the
10

existence of the family. The specific technique was the use of an algebraic structure called a g-clan which has since been used often in the study of hyperovals. We will not discuss g-clans here, but we refer the reader to [8] for information on g-clans. The use of innovative techniques is not uncommon when studying hyperovals which shows the need for many techniques.
The early 1990s saw yet another surge in the discovery of hyperovals. New examples of hyperovals were found by OKeefe and Penttila in 1992 [31], as well as Penttila and Pinneri in 1994 [40]. The hyperoval found by OKeefe and Penttila, known as the OKeefe-Penttila hyperoval, lives in PG(2,32) and is the only known sporadic hyperoval, that is, a hyperoval not known to be a member of an infinite family. The examples found by Penttila and Pinneri in PG(2,64) were the first distinct examples of Subiaco hyperovals. In 1995 Penntila and Royle [42] found more example of Subiaco hyperovals in PG(2,128) and PG(2,256) as well as the first examples of the Adelaide hyperoval in PG(2,64) and PG(2,256). The Subiaco hyperovals were proved to be an infinite family in 1996 by Cherowitzo, Penttila, Pinneri, and Royle [15]. However, the proof that the Adelaide hyperovals lived in an infinite family took 8 years from their initial discovery, finally being shown in 2003 [14], Since 2003 no new hyperovals have been discovered. The most notable paper on hyperovals for us since 2003 came from Fisher and Schmidt in 2006. They presented a paper ([17]) that unified the Payne and Adelaide families and provides the basis for this thesis.
However, there has been some work done on the study of monomial hyperovals. We say a monomial hyperoval 77 is a k-bit monomial hyperoval if an o-polynomial for 77 is f(t) = tn and there are k ls in the binary representation for n. The 1-bit monomial hyperovals are precisely the translation hyperovals. The 2-bit monomial hyperovals were classified in 1998 [16], and the 3-bit monomial hyperovals were classified in 2010 [51]. The following theorem was also given by Hernando and McGuire in 2012.
11

Proof: Let qa represent a point in polar coordinates. Using the fact that iq = i + 1, the following computation shows that the image of (aT(^),aT(q), 1) under the map (x, y, 1) > x + iy is qa.
i it i i
Q'T(-) + iaT(q) = a(h (~)q + iq + iqq) = a(h iq + q + iq H) = aq. q q q q q
Hence the element qa in GF(q2) corresponds to the point (aT(^), aT(q), 1) in
AG(2 ,q). m
This lemma shows that if we consider the hyperoval % = {;rp(;r) : x G N} U {0}
in polar coordinates, then the cartesian coordinates of these points are
{(p(x)T(-),p(x)T(x), 1) : x G A/"} U {(0,0,1)}.
x
By the fundamental theorem of projective geometry we can guarantee that the four points 0,1, , \Jyfyyy lie on the hyperoval. Thus p(l) = 1, p -h- j =
and p Udj = ^, for some /3 in GF(q) that is specific to each hyperoval and will be determined later.
In order to determine the o-polynomial form of this hyperoval we map these points onto the standard frame. Applying the collineation defined by
(x,V,z)
^110^
0/31
V010/
(x,x + py + z,y)
yields the set of points
{(p(x)T(^-), p(x)T(^~) + Pp(x)T(x) + l,p(x)T(x)) : x G M} U {(0,1,0)}.
Since T(l) = 0, T(i) = 1 and p(l) = 1 we have that the set of points is {(p(x)T(^),p(x)T(^) + pp(x)T(x) + l,p(x)T(x)) : x G M-{1}}U{(0,1,0), (1,0,0)}. Now p(x)T(x) yt 0 for x G J\f {1} so we can normalize to
{(WwWv + '9+ < m vi)-^eV-{i}}u{(o.i.o).(i,o,o)}.
1 {X) 1 {X) P{x)-L \x)
31

Observe that = i + yyq-pp-, hence the affine points of our hyperoval are
{(i
x
(-T+1)
,1 + 13
x
1
1) : x G N-{!}}. (2.9)
(rr+1)2 (x + l)2 p(x)T(x)
We have to guarantee that (0,0,1), (1,1,1) are among these points. If + (yyyp = 0 then x = G M. We also want i + f3 +
hence we want,
and so,
i + 1
T
i + 1
1
P'
i + 1
Vs
T
If i +
(.T+l)2
hence we want,
which requires,
1 then x = \ WI g N. We also want i + j3 + Wfrw +
(.T + 1)2 ' p(x)T(x)
i + 1
T
We are assuming that p ( ) = +f, and p
i + 1
_ Vs
i, + 1 \ 1
Vs T
/?
%++ ) = ^ so we have suc-
% j p
cessfully mapped our hyperoval onto the standard frame. If we want these points to satisfy an o-polynomial f(t), we must have
1
so,
i + p
1
x
(x + l)2 p(x)T(x)
f[i +
x
(x + l)2
/ +
X
(x + l)s
p(x)T(x)
Hence, provided the RHS is not zero then we have p(x)
+ i + (3 +
x
(x + l)2
(2.10)
/ ^ + (WwJ+?: + /3+(WwJT^)
Since x G Af the calculation
2 (l/xf . . 1
-, x^l.
I +
X
(x + l)s
* +1 +
(l/x + l)2
* +1 +
i +
x
(x + l)2 (x + 1)
32

shows that i
^^2 G GF(q). Also, the map r : Af {1} > GF(g) defined by
x > % -\
is clearly one-to-one and so GF (q) = {?' + yields
(x + l)2
: x G A/" {!}}- Letting t = i +
x2
(x+1)2
(f(t)+t + /3)T(x)'
Thus if we choose /5 so that y = x + /5 is an external line to the hyperoval in cartesian form, then our denominator will not be zero on M {1}.
This gives us the following theorem.
Theorem 2.24 Given an o-polynomial f with line y = x + /5 external to {(t, f(t), 1) : t G GF(q)} the polynomial
^ = mt/tTO' =+ GTTr P<1) = 1
is a corresponding p-polynornial.
2.6 The p-polynomials for Known Hyperovals
While Theorem 2.24 gives a general method for finding p-polynomials of known families of hyperovals, it does not always produce the most elegant representations. Taking extra information into account for specific hyperovals allows us to obtain better representations. We begin by studying the hyperconic to get a better understanding of the representation and provide some proof techniques.
2.6.1 Hyperconic
Theorem 2.25 In AG(2, q) the polynomial p(x) = 1 is a p-polynomial that produces a hyperconic.
Proof: Assume that p(x) = 1 and let % = {^p(^r) : x G N} = NThe following computation shows that a GF(q2) element x + iy E N if and only if its corresponding
33

cartesian point (x, y, 1) is a solution to an irreducible homogenous quadratic equation.
(x + iy)q+1 = 1 -<=/- (x + y + iy)(x + iy) = 1
-<=/- X2 + rry + ixy + ?+y + iy2 + ?'2y2 = 1 -<=/- x2 + rry + 4y2 + 1 = 0
Hence, (x, y, 1) is a norm 1 element if and only if it is a root of x2 + xy + 8y2 + z2. This shows that the points of N are the q + 1 points on a conic. Since each of them lies on a distinct line through 0, we must have that 0 is the nucleus of the conic. Therefore, J\f U {0} is a hyperconic, and p(x) = 1 is a p-polynomial that produces this hyperconic.
This, our first example of a p-polynomial for a hyperoval, may clearly be called elegant. Additionally, Theorem 2.25 shows that the domain of a p-polynomial is this hyperconic. Since any hyperoval has a p-polynomial representation this implies that any hyperoval is simply a perturbation of a hyperconic, where the p-polynomial describes that perturbation.
Observation 2.26 Every hyperoval is a perturbation of a hyperconic, where the perturbation is described by its p-polynomial.
We will now look at another nice representation of the hyperconic in the p-polynomial form. The polynomial p(x) = 1 can be viewed as the polynomial from (2.3) with all zero coefficients, except for the constant term. If we take the polynomial where all of these coefficients are 1, we also get a p-polynomial for the hyperconic.
Theorem 2.27 In AG(2,q) the polynomial p(x) = 1 + 'ZZ'jZl is a p-polynomial that describes a hyperconic.
Proof: Let p(x) = 1 + JZ'jZl xj We claim that p(yfc) = qk + q~k for 1 < k < q + 1,
where y is a generator of J\f. Assume that (k, q + 1) = d so that the elements of the
set {{qky : 1 < i < are precisely the {Z^)th roots of unity. Additionally, the
34

multiset {{if )1 : 1 < i < q + 1} contains exactly d copies of the {qff)th roots of unity. Hence by Lemma 2.20 we have
q+1
I>) = o,
i= 1 SO
q-1
rf + J>T + (t)" + i=2
thus
i + Ettt = +v*.
i=2
and therefore,
pff) = 'f + ifk-
This alternate form for p allows us to write
T-L = {xp(x) : x E M} U {0} = {//2fc + 1 : 0 < k < q} U {1}.
By Lemma 2.21 the map x > x2 permutes the q + 1st roots of unity so
n = {if + l:0 Theorem 2.25 shows that J\f U {0} is a hyperconic, and adding 1 to all of the points in M U {0} yields % as described above. Therefore, by Lemma 2.6 we find that the polynomial p(x) = 1 + YfjZl xj is a p-polynomial that describes a hyperconic. We get the following as an immediate corollary.
Corollary 2.28 The polynomial p(x) = x + xq = T(x), p(l) = 1 is a p-polynomial that describes a hyperconic.
The above forms describe hyperconics in AG(2, 2h) for all h. There are additional p-polynomials for hyperconics that are specific to the case when h is even. We present several different p-polynomials including many rational function forms. To begin, we provide an alternative proof of Theorem 2.27 for motivation.
35

Proof: Let p(x) = 1 + xj and calculate,
q-1
p(x) = 1 + xj
3=2
q-3
1 x2 ^ xj
3=0
2 1 Xq~2
= 1 + x ---------,x 1
1 X
X + 1 + x2(xq~2 + 1) X + 1
Xq + X2 + X + 1
X + 1
In order to properly perform these manipulations we have to change the domain
to Af {1}. So when using this p-polynomial the hyperoval points are defined by
{^p(rr) : x E Af {1}}- Thus, the formula providing the hyperoval points is
xq+l + x3 + x2 + x x + 1
where x comes from J\f {1}, so xq+l = 1. Hence
xq+l + x3 + x2 + x x3 + x2 + x + 1
xp(x) =
x + 1
x + 1
x + 1.
So,
H = {rr2 + 1 : x E Af {1}} U {0,1} = {rr+1 : x E AfU {0}}.
Therefore, H is a hyperconic by Lemma 2.6.
This alternative proof indicates the usefulness of representing p-polynomials as rational functions. The following theorems give additional p-polynomials for a hyperconic in AG(2, 2h) when h is even.
Theorem 2.29 In AG(2,2h), h even, the function
g-l
3
p(x) = 1 + (x + 1)
3 = 1
X
X2 + X + 1
is a p-polynomial describing a hyperconic.
36

Proof: We begin by showing the rational function shown above is equivalent to the polynomial.
g-l
3
p(x) = 1 + (x + 1) ^ ;r3t_1
i= 1
2=1-1 3 1
= 1 + (x + l);r2 ^ (x3y
i=o
1 ('r3lbr1
= 1 + (x + l);r2---------,x ^ 1
1 x6
x3 + 1 + (x + l)x2{xq~l + 1) x3 + 1
(x + 1)(^2 + x + 1 + xq+l + x2)
(x + l)(rr2 + x + 1)
1 + x + xq+l x2 + x + l
The domain of p is J\f {!}, so xq+l = 1. Thus
p(x)
x
X2 + X + 1
(2.11)
and our hyperoval will be
2
U { X---------,:.r: A' {())).
In order to show that this polynomial represents a hyperconic we will show that if x + iy G % then x2 + xy + (5 + l)y2 + 1 = 0. That is the points of % satisfy an irreducible homogeneous quadratic equation.
From Theorem 2.25 we know that the points of M lie on the conic defined by x2 + xy + 5y2 + 1 = 0, and the map that sends this conic to the conic defined by x2 + xy + (5 + l)y2 + 1 = 0 is (x, y, 1) > 1). Hence we want to show that
% is the image of N under the map x + iy > yyyf To do this we will show,
(x + iy)2 x + iy
(x + iy)2 + (x + iy) + 1 y + 1
37

under the assumption that x2 + xy + 5y2 + 1 = 0. To start, we must first show that (x + iy)2 + (x + iy) + 1^0, and y + 1 ^ 0. First observe that the roots of z2 + z + 1 are the elements of GF(4)\GF(2) which are not in J\f since h is even so (x + iy)2 + (x + iy) + 1^0. It is left to show that if y = 1 then x + iy ^ J\f. The point x + iy G J\f if and only if x2 + xy + 5y2 + 1 = 0. So if y = 1 we would need x2 + x + 5 + 1 to have a root in GF(q). However, since h is even 4 + 1 has absolute trace 1, showing x2 + x + 4 + 1 has no roots in GF(q), so y + 1 ^ 0.
Now, it is clear that
x(x2 + xy + 4y2 + 1) + iy(x2 + xy + 4y2 + 1) = 0.
Expanding yields
x3 + x 2y + 8xy2 + x + ?+2y + ?+y2 + i5y3 + iy = 0,
so
X3 + 4rry2 + x + ?+2y + ixy2 + ?'4y3 + = x2y.
Add i2y3 to both sides and rearrange the terms to get
x3 + 5xy2 + ixy2 + ix2y + i5y3 + ?'2y3 + x + = rr2y + i2y3,
and then factor, giving
(x + iy)3 + (x + ?'y) = (T + iy)2y.
Now, add (x + iy)2 to both sides and factor again to yield
(x + iy)[(x + iy)2 + (x + ?+) + 1] = (x + b/)2(y + 1),
and so
as desired.
(x + iy)2
(x + iy)2 + (T + iy) + 1
rr + iy
y +1
38

Theorem 2.30 In AG(2,2h), h even, the function
t,{x) i 1 (rf' rn|)2- p(i) = i
i= 1 '
is a p-polynomicil describing a hyperconic.
Proof: Similar to the previous proof we will begin by providing a rational function equivalent to the polynomial.
q-4
6
p(x) = 1 + (x + 1)
i= 1
Q~ 4 -|
6 1
= 1 + (T + l);r5 ^ (T6)*
i=0
i (XA V
= 1 + (T + l);r5-------, * 1
1 ;rb
x6 + 1 + (x + 1)^5(^9-4 + 1)
T 1
(T + l)(;r5 + x4 + x3 + ;r2 + + 1 + xq+l + ;r5)
(x + l)(;r5 + xA + ;r3 + ;r2 + x + 1)
/y*4 I I /y*^ I /y. I 1 I I 1
T/ | x3 + xA + x3 + x2 + x + l
Again, the domain of p is N {1}, so xq+l = 1. Thus
A O O
I /y*'- I /y*" I /y*
/ \ | | |
P(X) = ;----i---3~-----------7
;r5 + x4 + x3 + x2 + x + 1 *(* + l)3
(x3 + l)(;r2 + x + 1)
*(* + l)2 (x2 + + l)2
and so our hyperoval is
^h^^:'reAf-{1}}u{cu}-
In order to show that V. is a hyperconic we will show that if x + iy G V. then
x2 + xy + (6 + l)y2 + y = 0. That is, the points cartesian coordinates (x, y, 1) give
39

a solution to x2 + xy + (5 + 1 )y2 + yz = 0. The collineation that sends this conic to x2 + xy + (5 + 1 )y2 + 1 is dehned by (x, y, 1) > (x + 1, y, 1) and we know that x2 + xy + (6 + l)y2 + 1 defines the conic associated with the p-polynomial given in (2.11) from Theorem 2.29.
Let
pi(x)
x
x2 + x + 1
and
We will show that
P2(x)
x(x + l)2 (x-2 + X + l)2
vpiiv) +1 = vq/2p2(vq/2)
for arbitrary q G J\f, which will prove that the map (x, y, 1) > (x + 1, y, 1) sends the hyperoval associated with p\ to the hyperoval associated with p2.
Let q G Af. Clearly,
q2q+2 + qq+2 + q2q+l + qq+l + q2q + qg = q2q+l + qq+l + q2q + qg + q + 1.
Factoring both sides yields
(q2g + if) (if + i] + 1) = (p2? + p9 + 1 )(q + 1)
and so
q2g + qg q + 1
p2? + qq + 1 p2 + p + 1
Rewriting the terms on both sides gives
(?^/2)2 -f qq/2
('P?/2)2 -|- '/y?/2 _|_ \
f
P
2
p2 + p + 1
+ 1
and so
ppi(p) + 1 = if1'2 P2(if/2)
as desired. Hence p2 is also a p-polynomial describing a hyperconic.
40

Now that we have seen what we can do with hyperconics we turn our attention to the more general translation hyperovals.
2.6.2 Translation Hyperovals
Our goal in this section is to use Theorem 2.24 to determine a general p-polynomial form for the translation hyperovals. In order to do this, we must find a line y = x + /5 that is external to the hyperoval.
Lemma 2.31 The line y = x + [3 is external to the translation hyperoval with o-polynomial f{t) = t2' if and only if tr([3) = 1 where tr denotes the absolute trace function.
Proof: The line y = x + j3 is external to the translation hyperoval with o-polynomial f(t) = t2' if and only if x2' + x + (3 has no roots in GF(g).
ofc
Now, X2 + x + /3 = 0 if and only if
x2k + ^(^2J + x2J)+ x + f3= (x2,1 +rr2A X) + fx2,1 1 +rr2A ) 4-h (x2 + x) + /5 = 0.
j=i
Hence /5 plus a sum of elements of absolute trace 0 is 0, so the equation holds if and only if tr([3) = 0. Therefore, the equation has no roots if and only if tr([3) = 1 as desired.
Theorem 2.32 In AG(2,q), with q = 2h, the polynomial
^ s2(x2a+2 + l) + (s + l)2(x2a+ x2)' P(1) 1
is a p-polynornial describing the translation hyperoval with o-polynomial fit) = ta, a = 2k, where s = Y^jZo ^
Proof:
lations,
We begin with (2.10) from Theorem 2.24 and perform the following calcu-
1
p(x)T(x)
(x + l)2
+ i + [3 +
x
2
(x T l)2
41

1
p(x)T(x)
(ia + i + j3)(x + l)2a + x2(x + l)2" 2 + x2a (x + l)2"
(x + l)2"
[(?'" + i + /3)(x + l)2" + x2(x + l)2"-2 + x2a]T)x)
p(x)
x(x + 1)
2a2
(ia + ?' + /3)(;r + l)2" + x2(x + l)2"-2 + x2a From Lemma 2.31 we can let /3 = <5 since tr(8) = 1. So, using Lemma 2.8, and
multiplying the numerator and denominator by (x + l)2 yields
. . x(x + l)2"
^ s2(T + \)2a+2 + x2(x + l)2" + x2a(x + l)2
Finally, by expanding and rearranging the terms we obtain
x(x + l)2"
p(x)
s2(x2a+2 + 1) + (s + l)2(x2a + X2) '
We can see that not only does the p-polynomial depend on a but also the choice of 8. We give a simpler form for the p-polynomial when h is odd and also give a specific p-polynomial for the translation hyperoval with o-polynomial f(t) = tA.
Corollary 2.33 In AG(2,q), with q = 2h, h odd, the following are p-polynomials that produce the translation hyperoval with o-polynomial fit) = ta, a = 2k.
When k is even
, ^ *(*+ l)2" m
PW = X2a+2 + ^
1.
When k is odd
( ^ x(x+l)2a m 1
p(x) = piX) = L
x2a + xz
Proof: Since h is odd we may choose 8 = 1 since ir(l) = 1. Let s = Y^jZo ^ and observe that s = 0 when k is odd and s = 1 when k is even. Thus, the result follows immediately from Theorem 2.32
42

Observation 2.34 The p-polynomial
p(x) = xio + 1 >P(1) = 1
describes the translation hyperoval with o-polynornial fit) = tA.
Additionally, we may simplify in the case where h = 2 (mod 4). First we need a lemma about our choice of 5 in this case.
Lemma 2.35 In GF(2h), h = 2 (mod 4) the polynomial x2 + x + oj is irreducible, where oj satisfies oj2 + oj + 1 = 0.
Proof: In order to show x2 + x + oj is irreducible we must only show that oj has absolute trace 1. Observe that
tr{uf) = oj + oj2 + oj2 + + oj2
and oj2J = oj if j is even, and oj2J = oj2 if j is odd. Since w2 + w = 1 we have
h/2
tr(uj) = oj + oj2 + oj2~ + + oj2h 1 = 1 = 1
i=l
since h = 2 (mod 4).
Corollary 2.36 In AG(2, q), q = 2h, h = 2 (mod 4), the following are p-polynornials that produce that translation hyperoval with o-polynornial f(t) = ta, a = 2k.
When k = 1 (mod 4)
When k = 3 (mod 4)
t ^ x{x+l)2a n
PW = x2a + x2 P( } =
( ^ x(x+l)2a m 1 P^ = r2o+2 I 1 - = L
43

Proof: Since h = 2 (mod 4) we may choose 6 = oo where oo2 + uj + 1 = 0 from Lemma 2.35. Let s = YZj=o ^ and observe that s = 0 when k = 1 (mod 4) and s = 1 when k = 3 (mod 4), since u2 + oj = 1 and u2J = oj if j is even, and u2J = oj2 if j is odd. The result follows immediately from Theorem 2.32.
We have given p-polynomial forms for all translation hyperovals in the cases when h ^ 0 (mod 4). We will prove a more general result that will encompass this case as well as many others.
Theorem 2.37 In AG(2,q), q = 2h, the function
p(x)
x(x + l)2"
X2a + X2
p(l) = l
is a p-polynomial describing a translation hyperoval with o-polynornial fit) 2k, k odd.
a
Proof: Let a = 2k for k odd. We will begin with (2.9) from Section 2.5 so we must choose /5 G GF(q) such that y = x + /5 is external to the hyperoval. We can choose any ft with tr{fd) = 1 by Lemma 2.31 so let ft = YlkjZo ^ which has absolute trace 1 since k is odd.
We want to show that
,r2 y W l
' (x + l)2 J ' ^ (x + l)2 p(x)T(x)
which reduces to
/-y-* 2 I /-y-* 2
. . ,, 'Ay I
_L a fj ----------- -U --------- -U ------------ = 0
' ^ (x + l)2 (x + 1)2 (x + 1)2+2
and so,
ia + i + /3 = 0.
However, with our choice of /5 we know that ia + i + /5 = 0 by Lemma 2.8, which proves the result.
This result allows us to give a concise summary of translation hyperovals for all h as we did in Corollary 2.33 for h odd.
44

Corollary 2.38 In AG(2,q), with q = 2h the following are p-polynomials that produce the translation hyperoval with o-polynornial fit) = ta, a = 2k.
When k is even
When k is odd
p(x)
x(x + l)2"
X2a+2 _|_ l
Pi1)
1.
p(x)
x(x + l)2"
X2a + X2
pi1)
1.
2.6.3 The Segre Hyperoval
Now we turn our attention to the Segre hyperoval. In order to use Theorem 2.24 we must find a line y = x + /5 that is external to the Segre hyperoval.
Lemma 2.39 The line y = x + 1 is external to the Segre hyperoval.
Proof: In order to show a line y = x + /5 is external to a hyperoval in AG(2, q) with o-polynomial / we must show that f(x) + x + /5 has no roots in GF (q). Thus in this case we must show g(x) = x6 + x + 1 has no roots in GF(2/l) when h is odd.
Assume that a E GF(q), and g(a) = 0. It is easily checked that g has no roots in GF(2/l) for 1 < h < 5, thus q > 64. Since a is a root we must have that a2' is also a root for 0 < k < 5, and these roots are distinct since q > 64. We know x6 + x + 1 has at most 6 roots, and these roots lie in an orbit under the map x > x2, so a64 = a, implying a E GF(64) which implies q = 26k. Hence this polynomial has no roots in GF(2h) when h is odd and therefore the line y = x + 1 is external to the Segre hyperoval.
Theorem 2.40 In AG(2,q), with q = 2h, h odd, the polynomial (:) =_____________________________+1)10_____________ m = i
^ i2x12 + rr10 + x8 + x4 + x2 + i ^
produces the Segre hyperoval.
45

Proof: Again we begin with (2.10) from Theorem 2.24 with f(x) = x6 and j3 = 1. Since h is odd we make the additional assumption that i G GF(4)\GF(2). The following calculations prove the result.
1 f X 2 \ X 2
p(x)T(x) = V + (;r + l)2 ) + + 1 + (a:+ 1)2
1 (x2 + i(x + l)2)6 . 1
p(x)T(x) (rr+1)12 ^ (x + l)2
1 (x2 + i(x + l)2)6 + i(x + l)12 + (x + l)10
p(x)T(x) (rr + 1)12
1 x12 + /./';./ + l)8 + i2x8(x + l)4 + (x + l)12 + i(x + l)12 + (x + l)10
p(x)T(x) (rr + 1)12
. . x(x + l)10
^ X x12 + i2(x + l)12 + (x + l)10 + /./';./ + l)8 + i2x8(x + l)4
_ ;r(;r + l)10
^ ?'2rr12 + ;r10 + x8 + ;r4 + x2 + ?'

As an immediate corollary we see that the Segre hyperoval can always be represented with a p-polynomial with coefficients over GF(4), since we can always assume that i G GF(4)/GF(2). Also, we know that the Segre hyperoval is not represented by a p-polynomial with coefficients over GF(2) by Corollary 2.18, since the automorphism group of the Segre hyperoval has order (q l)h or 3(q l)h as seen in Table 1.2.
46

We now present a compact p-polynomial for the Adelaide hyperoval. We generated p-polynomials for the Adelaide hyperoval in some small order planes and made the following observation.
Observation 2.41 In AG(2,2h), h = 2, 4,6, 8, the p-polynomial
V
Ai-l
where s = 2h~2 1 is a p-polynomial that represents the Adelaide hyperoval.
P{x) = 1 + Or + 1) 1 + I (z + 1)
We turn the polynomial above into a rational function through the following calculations.
p(x) = 1 + (x + l);r3 ^h4^ 4) + | (x + l);r3 ^h4^
j=i \ 3=i
(x + l);r3(l (x4)i) / (x + l);r3(l (x4)i)
= 1 +
1 x4
1 x4
x yt 1
= 1 +
x3(rr43S +1) j x3^^ + 1)
(x + l)1
(x + 1)"
(x + l)3 + x3(x93 + 1) + (x93 + l)q (x + l)3
o o x+ x + x + 1 + xm^ + # + x 3 + 1
(x + l)1
q(q-) g+5
X 3 3 + X + X
(x + l)3
For ease of simplification we will temporarily replace x with s3, which simply reorders
47

the roots since q = 2h, h even, and proceed with our calculations.
p(s3)
sq{q~4) + sq+3 + s6 + s3 (s3 + l)3
sg(g+Ds-5g + s (s3 + l)3 s6 + s5 + s4 + s3
(s3 + l)3 s3(s + l)3 (s3 + l)3
Now we undo our substitution and obtain
In order to prove that this is a p-polynomial for the Adelaide hyperoval we will follow the approach of Fisher and Schmidt (see [17] section 6), and show the points lie on an algebraic plane curve shown to represent the Adelaide hyperoval by Payne and Thas in [38]. First, we show that the points satisfy a sixth degree equation.
Lemma 2.42 The points {tp(t.) : t E Af {1}} U {1} where
t{U + l)3
P(t)
(t + 1)J
satisfy the equation
y6 + y4 + x y + x2 + (S + l)y2 + 1 = 0
(2.12)
when thought of as points (x,y,l) in cartesian coordinates.
Proof: Using Lemma 2.23 we know that the cartesian form of the points is
1) : t E AT {1}} U {(1,0,1)}.
Clearly (1,0,1) satisfies this equation so we focus on the other q points. Observe that
Tit) = {-^Tl +(+ =
_ i(t+l)2+t2
so that the cartesian form of the points is (x, y, 1)
with
_ (t1/3 + 1 )3(i(t + l)2 + t2) ^ (t1/3 + l)3
^ ~ : ttt; i y
(t + iy
(t+1)
48

Substituting these values of x and y into (2.12), and multiplying the resulting equation by (t+ l)6 yields
(t1/3 + l)18 + (t + 1 )2(t1/3 + l)12 + (t1/3 + l)6('i(t + l)2 + t2)(t + l)2 + (tl/3 + 1 )6(i(t + l)2 + t2)2 + 8(t1/3 + 1 )6(t + l)4 + (t + l)6.
Replacing t with s3, expanding, and factoring gives
('i2 + i + 5)(s + l)10(s2 + s + l)4 = 0,
since i2 + i + 8 = 0. Hence, the result holds.
Now, replacing x with x/z and y with yjz in (2.12) and then multiplying by gives (2.12) in projective coordinates;
y6 + yAz2 + z4(xy + x2 + (8 + l)y2) + = 0. (2-13)
We need one final lemma of Payne and Thas to prove our result; see [38] Lemma 5.1, Theorem 5.2. We change their notation to be consistent with our own.
Lemma 2.43 ([38]) If O represents an Adelaide oval as described in section 5 of
[38], and C = {(t, u, v) G PG(2, q) : T(i])2v6 + (v + t)4(u2 + T(y)tu + v2) = 0}, where i] is a primitive element of Af, then C = O U (0,1, 0).
This lemma shows that the points of the Adelaide oval directly coincide with the points of the algebraic plane curve. We are now ready to prove the main theorem of this section.
Theorem 2.44 In AG(2,2h), h even, the polynomial
p(x) =
, 1 , r
X\X3 + lg
(x + l)3
is a p-polynomial representing an Adelaide hyperoval.
49

Proof: Using Lemma 2.43, and substituting t = y, u = T(i])x, v = y + z into
T(i])2v6 + (v + t)4(u2 + T{rj)tu + v2) = 0 gives (2.13) with 8 = To finish the
result we must show that x2 + x + ppp is irreducible in GF(2h), h even. Fisher and Schmidt showed the equation x2 + x + 1 + ppp is irreducible, see [17] Theorem 6.2. Hence ir(l + pAp) = 1 where tr denotes the absolute trace function. Since h is even, and tr is additive we have tr(l + yfiipO = 2) = tr{T^2) = 1. Therefore,
x2 + x + ij^jyr is irreducible in GF(2/l), h even.
2.6.5 The Subiaco Hyperoval
In this section we give a unified form for the hyperovals in the Subiaco family whose automorphism groups have order divisible by 2h. Computer investigations led us to consider the polynomial
p(x) = ---------------;---.
2T10 + 2T6 + X5 + X4 + 1
We will show that p is a p-polynomial representing a Subiaco hyperoval in AG(2, q), q = 2h for all h > 1. Observe that this p-polynomial has coefficients over GF(2) so the hyperoval it represents must have an automorphism group with order divisible by 2h by Corollary 2.18. As such, this polynomial does not represent every hyperoval in the Subiaco family, up to projective equivalence.
We begin by considering the set of points {^p(^r) : x E J\f} U {0} and applying the homography defined by
(uyu)
^110^
0/31
V010/
= (x,x + Py + z,y)
with /3 = y/5 + | + yr to obtain the set of points
2 ,J1 -y
{(i
x
(x + l)s
, i + /3 +
x
(x + l)2 p(x)T(x)
,1) :xEAf-{l}}U{(0,1,0), (1,0,0)},
50

as shown in Section 2.5. We will show that
i
(x + l)2
1
p(x)T(x)
(2.14)
2
represents an o-polynomial for a Subiaco hyperoval in variable i + Observe
that
p(x)T(x)
x4(x + l)2
ir10 + x6 + ir5 + x4 + 1
so (2.14) reduces to
x2 ir10 + ir6 + x5 + x4 + 1 ' (x + l)2 ir4(ir + l)2
(i + /3)x4(x + l)2 + x6 + ir10 + x6 + ir5 + x4 + 1 ir4(ir + l)2
ir10 + (i + l3)x6 + x5 + (i + [3 + l);r4 + 1 ir4(ir + l)2
Now, let t. = ?' + pypjp so # = Jt_^r Making this substitution yields
h(t) :=
(i + + l)3
(t + *)2
1 + i t + i + 1
t + ?' t + i + 1
3
+ y/2
t + i + 1 /
1 + i t + i + 1
2
(f + ?;)5 + (z + /3)(f + i)3(t + z + l)2 + (z + P + l)(f + z + l)3(f + -Q2 + (1 + z + l)5
(t + i + l)2(t + i)2
t5+ j3t4+t3+ (i3 + l)t2+ (-i2 + i + l)2t+ i4j3+ i2i3+ i2+i+ 1
(t2 + t + ?'2 + ?')2
+ Vl2 +1 + ?'2 + i
(/3+ ?'+ \/p)t4 + (/3+ i~\~ y/i~\~ l)t2+ 1+ (/5+ \/^)(?'4+ ?'2) + ?'5 + ?'3 + ?'2 + ?'+ 1 1/2
(t2 + t + ?'2 + ?')2 ~*~
Recall that ?'2 + i = 6, so letting c = y/5t and reducing h yields
h(z)
52{f3+V~5)z4+5{[3+yf5+l)z2 + V~5z
32{z2 + ^&z
'2+?;3(?;2+i)+4+i
+ (v^)1/2.
51

Since j3 = y/fi + | + ^ we have
= ++f}fl+^+<^)1/2.
*W+ 3f&z + l>
Now let d = so that tr(|) = 1. Simplifying and making the substitution for d yields
7 / \ ^ + (1 + ^ + ^)-2 + ( r, u/2
=-----------(- + j-z + l)2---------+ (v^}
_ d\d2 +1)^4 + d2(i + d2 + d4)^2 + (z2 + dz + l)2
Thus, our point set is represented by
c\V2
d)
{(-, h(z), 1):;G GF(q)} U {(1, 0, 0), (0,1,0)}.
Next, we normalize h so that h( 1) = 1 to get the point set
{(xj(x), 1) : x E GF(q)} U {(1,0,0), (0,1,0)}
where
1 f cl3{d2 + \)x4 + cl3{\ + cl2 + cl4)x2 + cl4x 1/2N
/w = x +

We claim that this is an o-polynomial for a Subiaco hyperoval.
Lemma 2.45 Let d E GF(q) such that tr(^) = 1. The polynomial
1 f d3{d2 + l)x4 + d3{l + d2 + d4)x2 + d4x !/2
m = d? +

is an o-polynomial for a Subiaco hyperoval.
Proof: In Theorem 5 of [15] it is shown that
d4x4 + d3(l + d2 + (T)x3 + d3(l + d2)x d1/2 a/2
9^X ~ (d2 + d5 + dl/2)fx2 + dx + l)2 + d2 + d5 + d4/2'X
52

is an o-polynomial for a Subiaco hyperoval, where d is as described above. Applying the homography defined by
(x, y, ~)
A)0 1^
010
V100/
(z,y,x)
to the hyperoval Id defined by
n := {(x,g(x), 1) : x E GF(q)} U {(1,0,0), (0,1,0)}
yields the point set
n' = {(l,g(x),x) : x E GF(q)} U {(0,0,1), (0,1,0)}
= {(!, We now normalize the points
{(1 ,g(x),x) : x E GF(q)*} = {(,^,1) : x G GF(q)*}-Letting t = y gives the points
{(Mt/0,1 ):tE GF(q)*}.
We now focus our attention on reducing tg{\).
t (dA(l/t)A + d3(l + d2 + d4)(l/t)3 + d3(l + d2)(l/t) fd\1/2\
9g) ~ d5 + d?+d1/2 ^ (l/t)2+ d/t, + l)2 +Vty )
t (dA + d3(l + d2 + dA)t + d3(l + d2)t3 (d\ ^2\
= d5 + d2 + d1/2 y (t2 + dt + l)2 +\t) J
= /(*)
With the observation that /(0) = 0 we see that
n' = {(t, f(t), 1) : t E GF(q)} U {(1,0, 0), (0,1, 0)},
so / is an o-polynomial for a Subiaco hyperoval.
The above remarks give the following theorem.
53

Theorem 2.46 In AG(2,q), q = 2h, the polynomial
^ xw + + 1
is a p-polynomial for a Subiaco hyperoval whose automorphism group has order divisible by 2h.
This p-polynomial describes, up to projective equivalence, all Subiaco hyperovals in AG(2,2h) when h is odd, and when h = 0 (mod 4). However, when h = 2 (mod 4) there are Subiaco hyperovals with automorphism group of order which are not described by this p-polynomial. A p-polynomial describing a hyperoval with automorphism group of order ^ cannot have coefficients over GF(2). In fact, GF(16) is the smallest order held in which the coefficients for such a p-polynomial could exist. A p-polynomial representing the Subiaco hyperoval with automorphism group of order 15 in AG(2,64) is given in Chapter 3.
2.6.6 Other Families
The Glynn, Payne, and Cherowitzo hyperovals have been resilient to showing compact p-polynomial representations. The general conversion from their o-polynomial forms as given in Theorem 2.24 are currently the most appealing. The difficulty in conversion stems from the fact that these hyperovals are already quite elegantly represented as o-polynomials. The exponents on the polynomial terms are variable based on the plane they live in, rather than a fixed integer. This in itself presents difficulty in simplification. It may be possible to use case analysis, similar to that in Corollary 2.33, to further simplify the p-polynomials for hyperovals in these families, but our work up to this point has not been fruitful.
Through studying the p-polynomial representation it has become clear that some
hyperovals will be better represented as o-polynomials. Many of the monomials, with
exception of the hyperconic, are more elegantly represented as o-polynomials. In
fact, as we saw in Theorem 2.40 the Segre hyperoval has its simplest p-polynomial
54

representation over GF(4)! In contrast the Subiaco and Adelaide hyperovals have p-polynomial representations over GF(2), where there o-polynomial counterparts do not. Additionally, we will see nice structure represented by the p-polynomial of the OKeefe-Penttila hyperoval that is not represented by its o-polynomial. As such, the intention of the p-polynomial method is not to replace o-polynomials, but rather to complement them. Combining the two representations will help us study hyperovals and reveal information about their structure that would likely be overlooked if study was restricted to one representation.
55

3. A Computational Approach
This chapter is devoted to showing how the p-polynomial method can be used to further expand the search for hyperovals by computer. We saw in Sections 2.4.2 and 2.4.3 that the structure of p-polynomials directly corresponds to the hyperovals being stabilized by held automorphisms and multiplicative actions. We use these theoretical results to search for hyperovals stabilized by these actions, and in turn search for hyperovals whose p-polynomials have the desired properties. This is similar to the approach of Fisher and Schmidt, but we do not restrict ourselves to only the polynomials with many zero coefficients.
3.1 Cyclotomic Sets
While studying the p-polynomial representation we noticed a nice property of the hyperovals that have their p-polynomials represented over subfields of GF(q2). In order to describe the structure of hyperovals whose p-polynomials have coefficients in a subheld, we give the following definition.
Definition 3.1 Given an element /5 G GF(q2) and an automorphism a : x > x2', of GF(q2), we can generate the set:
C(/3) = {/3,r,/3-,...,/3^1},
where s = pypp Ca(/3) is the set of all of the images of f3 under the automorphism a. We call this a cyclotomic set and think of it as a geometric structure in AG(2,q).
A cyclotomic set is the orbit of the point /5 under the automorphism we wish to distinguish this set of points as a structure in AG(2,q), hence the new
name. If one wishes to describe these sets in a traditional way, they are sets of points
stabilized by the collineations described in Lemma 2.9. Theorem 2.17 shows that if a
hyperoval has a p-polynomial with coefficients in the subfield GF(2fc) of GF(q2) then
the hyperoval can be partioned into cyclotomic sets defined by the automorphism
a : x > X2 Due to this we use cyclotomic sets as building blocks for hyperovals.
56

A necessary condition for a cyclotomic set to be part of a hyperoval is that it is an arc. Cyclotomic sets are not always arcs, but we leave that discussion for the next chapter where we determine when a cyclotomic set is an arc (see Corollary 4.7). When a cyclotomic set has a particular structure we often refer to it as a cyclotomic structure, e.g., a cyclotomic arc. We now assume that we know which cyclotomic sets are arcs and describe how we can use them to search for new hyperovals.
3.2 Using p-polynomials to Search for Hyperovals
As we have seen in Lemma 2.7, the held automorphisms of GF(q2) induce collineations. Since each automorphism fixes the origin they permute the lines through the origin defining orbits of these lines. The orbits of the lines through the origin correspond exactly to the orbits of the q + 1st roots of unity, or rather, the cyclotomic sets of Af. We refer to each orbit of lines as a sector and note that every cyclotomic set lies in exactly one sector as shown in Figure 3.1.
V
Figure 3.1: A Sector with a Cyclotomic Set
As before, we assume that a hyperoval % contains 0, and so, must contain exactly one other point on each line through zero. Hence, if H is stabilized by an automorphism 57

Due to this partitioning we are able to do efficient backtrack searches, choosing one element from each sector at a time. We implemented a backtrack search for all hyperovals stabilized by the automorphism a : x > x2 in AG(2, 2h) for 4 < h < 8 and for hyperovals stabilized by r : x > xA in AG(2,32). The run times of these searches are given in Table 3.1.
Table 3.1: Run Times for Backtrack Searches
Plane Action Time
AG(2,16) x > x2 < 1 sec
AG(2,32) x > x2 < 1 sec
AG(2,32) x > XA 6 sec
AG(2,64) x > x2 8.5 sec
AG(2,128) x > x2 10 min
AG(2,256) x > x2 68 hours
From Corollary 2.18 we know that if we are going to find a hyperoval 1-L stabilized by a : x > x2' then we must have ^ dividing | Aut('H) |. In fact, our results in the following sections show that we find precisely those hyperovals whose automorphism group sizes are divisble by
As is displayed in Table 3.1 the search time for backtrack searches quickly becomes unmanageable as the size of the field grows. Due to this we looked for alternative search methods. The following method, that we call Clique Finder, is described as follows:
Define a graph G = (V, E) where V = {C : C is a cyclotomic arc} and E =
{(#, y) : x U y is an arc}. Assign colors to the vertices so that two vertices receive the
same color if and only if their corresponding cyclotomic arcs he in the same sector.
If a collection of cyclotomic arcs are combined to create a hyperoval then they will
appear as a rainbow clique in G, that is, a complete subgraph where all the vertices
58

are different colors. The graph as described will contain rainbow cliques that are not hyperovals, because there are sets of three cyclotomic arcs whose pairwise unions are arcs, but the union of all three is not. To remedy this, we check for these false triples as the graph is built. This search technique is implemented in the Orbiter package written by Anton Betten, see [3].
We implemented the Clique Finder search for hyperovals stabilized by a : x > x2 in AG(2, 2h) for 6 < h < 9 and r : x > x4 in AG(2, 2h) for 5 < h < 7, with partial searches done in AG(2,256). Clique finder is significantly faster than the previous backtrack searches as is shown in Table 3.2.
Table 3.2: Run Times for Clique Finder
Plane Action Time
AG(2,64) x > x2 4 sec
AG(2,128) x > x2 7 sec
AG(2,128) x > XA 3 min 22 sec
AG(2,256) x > x2 2 hours 30 min
AG(2,256) x > XA est. 240 weeks
AG(2,512) x > x2 8 hours 45 min
ofc
We were unable to complete searches for hyperovals stabilized by a : x > x2 for large values of k since the cyclotomic set sizes become small and the graph becomes unwieldy. Also, in order to find certain families of hyperovals in small planes, we have to look for hyperovals stabilized by the action x > qx for q G N'. The search for hyperovals stabilized by these actions was implemented using a backtrack search in AG(2,32) and AG(2,64).
Searching for hyperovals stabilized by specific actions has a great precedent in the
study of hyperovals. Our approach is closely related to that of OKeefe and Penttila
in [31], Penttila and Pinneri in [40], and Penttila and Royle in [42], The technique
59

used in [31] and [40] is called prime at a time. The technique takes a prime p and constructs all hyperovals % such that p | |Aut(%)|. The technique considers all conjugacy classes of elements of order p in PTL(3,g) and finds the hyperovals stabilized by the collineations. Our searches for hyperovals stabilized by the maps x > qx for q G N are a restricted version of prime at a time.
In [42] Penttila and Royle use prime at a time, but also search for hyperovals stabilized by the collineation defined by
R ^10 0^
y -> a 1 0 y2
W v1 / W
where a and b are elements of absolute trace 1. This collineation is closely related to the collineation induced by automorphisms of GF(q2) given in Lemma 2.9.
The prime at a time technique helped discover the OKeefe-Penttila hyperoval in [31], the first examples of the Subiaco hyperoval in [40], and helped classify hyperovals with non-trivial automorphism group in PG(2,64), which uncovered the first example of the Adelaide hyperoval in [42], Additionally, the collineation defined in (3.1) was used to discover additional examples of the Adelaide and Subiaco hyperovals in PG(2,256). With this precedent in mind we searched for hyperovals stabilized by our collineations in the polar model in some small planes. We begin our searches in AG(2,16) as it is the smallest order plane with an irregular hyperoval, i.e., a nonhyperconic.
3.2.1 Searches in AG(2,16)
In AG(2,16) we searched for hyperovals stabilized by the map x > x2 and the search revealed both the hyperconic and Lunelli-Sce hyperovals. These are the only hyperovals that are contained in this plane so we did not do any further searches. In total eight hyperovals were found, four of each type. The Lunelli-Sce
60

p-polynomials are of particular interest here as they have been shown to be members of the Adelaide and Subiaco families. Since these hyperovals are stabilized by the squaring automorphism they necessarily have p-polynomials with coefficients over GF(2) where their o-polynomial counterparts do not. The Lunelli-Sce p-polynomial p(x) = xlA + ;r13 + ;r4 + ;r3 +1 satishes the general form for the Adelaide p-polynomial given in Theorem 2.44 and the form for the Subiaco hyperoval given in Theorem 2.46. Additionally, all four forms of the hyperconic from Section 2.6.1 are represented. Due to the manageable list and size of each p-polynomial we list all of them in their entirety.
Table 3.3: p-polynomials for hyperovals in AG(2,16)
Hyperoval p-polynomial
Hyperconic 1
x1'2 + x11 + x6 + ;r5 + 1
a:15 + X14 + X12 + XU + X9 + X8 + X6 + a:5 + X3 + X2 + 1
a:15 + X14 + a:13 + X12 + X11 + a:10 + X9 +x8 + x7 + x6 + x5 + x4 + x3 + x2 + 1

Lunelli-Sce X14 + a:13 + X4 + X3 + 1
xu + Xn + X9 + X8 + X6 + X3 + 1
X14 + a:13 + X12 + a:10 + X7 + ;r5 + X4 + X3 + 1
a:15 + a:13 + X11 + a:10 + X9 + X8 + X1 + X6 + X4 + X2 + 1
3.2.2 Searches in AG(2,32)
In AG(2, 32) we completed three searches, one for hyperovals stabilized by each
of the following actions, x > x2, x > x3, x > ux, where u3 = 1. There search using
x > x2 yielded three distinct hyperovals, the hyperconic, translation, and Payne
hyperovals. The search using x > xA gave the Cherowitzo and Segre hyperovals
61

in addition to those from the x > x2 search. Finally, the search using x > ujx gave the Segre and OKeefe-Penttila hyperovals. These are all of the hyperovals in AG(2,32) so this list adds a complete set of p-polynomials for hyperovals in this plane. Observe that the hyperovals stabilized by x > x2 are precisely those hyperovals whose automorphism groups are divisible by 10 = 2h, and those stabilized by x > x4 are precisely those hyperovals whose automorphism groups are divisible by 5 = h. Further, hyperovals stabilized by x > ujx are precisely those whose automorphism groups are divisible by 3. As such, the necessary condition given in Corollary 2.18 is also sufficient in this plane.
We chose the most appealing p-polynomials to show here. For the OKeefe-Penttila p-polynomial, b is a primitive element of GF(1024) satisfying 610 = b6 + 65 + b3 + b2 + b + 1.
Table 3.4: p-polynomials for hyperovals in AG(2,32)
Flyperoval p-polynomial
Hyperconic 1
Translation t4 x29 + x28 + x24 + x23 + ;r19 + ;r18 +rr15 + x14 + ;r10 + x9 + rr5 + x4 + 1
Segre x30 + u2x27 + u2x24 + x21 + x12 + UJX9 + ujx6 + x3 + 1
Payne rr31 + X30 + x28 + x23 + x20 + ;r19 + X1' To:16 + X14 + a:13 + a:10 + a:5 + ^3 + X2 + 1
Cherowitzo x30 + x28 + uj2x27 + x26 + x25 + x24 + uj2x23 + uj2x22 +UJX21 + ujx20 + ujx17 + uj2x13 + uj2x13 + uj2x12 + ujx11 +o;a:10 + x9 + x8 + x1 + ujx6 + ;r5 + x3 + 1
0 Keefe-Penttila 651W30 + b924x2 + b230x24 + b55 X21 + b3x18 +696a:15 + b433x12 + b199x9 + b924x6 + b100 x-3 + 1
62

3.2.3 Searches in AG(2,64)
In AG(2,64) we completed two searches, one for hyperovals stabilized by the actions, x > x2, and x > yx, where y5 = 1. The search using the action x > x2 gave the hyperconic and Adelaide hyperovals, as well as the Subiaco hyperoval with automorphism group of order 60. The search using x > ^fx gave both Subiaco 15 and Subiaco 60, the Subiaco hyperovals with automorphism groups of order 15 and 60 respectively. Again we choose the most appealing p-polynomials to present. For Subiaco 15 we let q be a primitive element of GF(16) satisfying if = q + 1. Since Subiaco 15 has a p-polynomial with coefficients over GF(16) we see again that the necessary condition of Corollary 2.18 is also sufficient for the known hyperovals in this plane.
Table 3.5: p-polynomials for hyperovals in AG(2,64)
Hyperoval p-polynomial
Hyperconic 1
Adelaide X63 _|_ ^62 _|_ ^60 _|_ ^59 _|_ ^58 _|_ ^57 _|_ ^49 _|_ ^35 _|_ ^33 _|_ ^32
+;r30 + rr16 + X8 + X7 + X6 + ;r5 + X3 + X2 + 1
Subiaco 15 qx60 + qnx55 + qx50 + q1:r45 + q2xm + q1:r35 +q13x30 + ifx25 + q13x20 + ifx15 + qux10 + ifx5 + q10
Subiaco 60 X60 + X50 + xi5 + XM + X-30 + X20 + a:15 + x5 + 1
3.2.4 Searches in AG(2,128)
In AG(2,128) we performed two searches, one for hyperovals stabilized by x > x2, and one for hyperovals stabilized by x > xA. The search using x > x2 found the hyperconic, translations, Payne, and Subiaco hyperovals, where the search using
63

x > xA found the Segre, Cherowitzo, and Glynn II hyperovals. These are all known hyperovals contained in this plane. We mention yet again that the necessary condition from Corollary 2.18 is also sufficient.
We attempted to do a backtrack search for hyperovals stabilized by the action x > lux where oj3 = 1, however this search is far to big to complete. We plan to give serious consideration to this search in the future.
3.2.5 Searches in AG(2,256)
In AG(2, 256) we completed one search for hyperovals stabilized by the map x > x2. The search yielded all known hyperovals in the plane, which are the hyperconic, translation, Adelaide, and Subiaco hyperovals. Yet again, we point out that the necessary condition of Corollary 2.18 is also sufficient here. The p-polynomials of these hyperovals are given in Table 3.8. We represent them in rational function form for space considerations.
Partial searches have been completed with the action x > xA and the early results give no new families of hyperovals. We attempted to shorten the estimated full search time of 240 weeks by reducing via the symmetries of the graph that is created in Clique Finder. It appears that these symmetries do not induce collineations and hence group together cliques that should not be associated. Thus our search here is not yet complete. The 240 weeks is realizable with parallel computing, but this has not yet been implemented. We plan to finish the search under this action and hope to continue the search in this plane for hyperovals stabilized by x > ;r16. However, new techniques may be needed to complete this search.
64

Table 3.6: p-polynomials for hyperovals in AG(2,128)
65

Table 3.7: p-polynomials for hyperovals in AG(2,128) (2)
66

Table 3.8: p-polynomials for hyperovals in AG(2,256)
Hyperoval p-polynomial
Hyperconic 1
Translation t8 (x + l)16
;r(;r14 + 1)
(x + l)3
Subiaco x5
;r10 + x6 + ;r5 + xA + 1
3.2.6 Searches in AG(2,512)
In AG(2,512) we completed one search for hyperovals stabilized by the action x > x2. The search yielded 10 hyperovals, 2 each of the hyperconic, translations, Payne, and Subiaco hyperovals. These were precisely the ones we expected to find, that is, those whose automorphism group is divisible by 18 = 2h. Other searches have not been completed in this plane due to the large search time required. We give the Payne p-polynomials as it is the only family above for which we have not yet provided an nice p-polynomial representation.
67

Payne: The polynomial g(x) is given and p(x) = 1 + g(x) + g(x)q.
g(x) = x255 + x253 + x252 + X251 + ;r248 + xMT + ;r243 + xM1 + xM0 + x238 + x236 + ;r234 +
;r233 + X232 + ;r231 + X229 + ;r22' + ;r225 + x2M + ;r223 + x221 + ;r219 + ;r21' + x215 + ;r214 +
^213 _|_ ^212 _|_ ^211 _|_ ^210 _|_ ^207 _|_ ^206 _|_ ^202 _|_ ^198 _|_ ^196 _|_ ^193 _|_ ^191 _|_ ^190 _|_ ^188 _|_
^180 _|_ ^179 _|_ ^178 _|_ ^177 _|_ ^168 _|_ ^161 _|_ ^153 _|_ ^152 _|_ ^150 _|_ ^148 _|_ ^146 _|_ ^144 _|_ ^142 _|_
x 140 _|_ x 139 _|_ ^138 _|_ ^137 _|_ x 135 _|_ x 134 _|_ x 131 _|_ x 129 _|_ x 128 _|_ ^127 _|_ ^124 _|_ ^123 _|_ x 122 _|_ x 121 _|_
^119 _|_ ^117 _|_ ^112 _|_ ^111 _|_ ^110 _|_ ^109 _|_ ^108 _|_ ^106 _|_ ^103 _|_ ^102 _|_ ^99 _|_ ^95 _|_ ^90 _|_ ^84 _|_
^-.83 _j_ jB2 _j_ ^-.81 _j_ ^-.80 _j_ ^>79 _j_ ^,78 _j_ ^,77 _j_ ^>75 _j_ ^>73 _j_ ^>71 _j_ ^,69 _j_ ^,68 _j_ ^,64 _j_ ^,63 _j_ ^>61 _j_ ^,60 _j_
^>59 j ^-.<->8 j j 93 j ^>53 j j ^-*4o j ,^-*44 j ^-*43 j ^-*41 j ^-*39 j ^-*38 j ,^-*37 \ j \ \
;r31 + x29 + x28 + x27 + x22 + x21 + ;r20 + ;r18 + x17 + xu + ;r13 + x12 + ;r10 + x7 + ;r5 + x4 + x3
g(x) = x256+rr255+rr254+x252+rr249+xM7+xM&+rr244+rr239+rr237+rr236+rr234+rr233 +
^231 _|_ ^230 _|_ ^229 _|_ ^228 _|_ ^227 _|_ ^226 _|_ ^224 _|_ ^221 _|_ ^219 _|_ ^218 _|_ ^217 _|_ ^216 _|_ ^214 _|_ ^213 _|_ ^,210 _|_^207 _|_^204 _|_^203 _|_^,201 _|_,^200 _|_^199 _|_^198 _|_^196 _|_^193_|_^191_|_^190 ^ 188 _|_^183 _|_
^180+^179+^177 + ^176 + ^174+^173+^170+^165+^163+^162+^160 + ^153 + ^150+^147 +
x 145 _|_ x 144 _|_ ^143 _|_ ^142 _|_ x 140 _|_ x 137 _|_ x 135 _|_ x 134 _|_ x 132 _|_ ^127 _|_ ^125 _|_ ^124 _|_ x 122 _|_ x 121 _|_
^119_|_^118_|_^117_|_^116_|_^115_|_^114_|_^112 _|_^105 _|_^102 _|_-y99 _|_-y97 _|_-y96 _|_-y94 _|_-y93 _|_^90 _|_ ^>85 _|_^.83 _|_ j,82 _|_ ^.80 _|_ ^.79 _|_ ^J7 _|_ ^.76 _|_ ^.74 _|_ 1 _|_ ^.69 _|_ ^.68 _|_ ^66 _|_ ^.65 _|_ ^.63 _|_ ^.62 _|_ ^.61 _|_ ^.60 _|_
^>59 j j.08 j j j ^>53 j ^-*o2 j ^-*oO j ^-*4o j ^-*43 j ^-*42 j ^-*40 j \ \ j ^71^^ j \
^31+^30+^28+^25+^23+^22+^20+^15+^13+^12+^10+^9+^7+^6+^5+^4+^3+^2
68

4. Structures represented by Cyclotomic Sets
This chapter is devoted to structures that appear as cyclotomic sets. While investigating the p-polynomial representation of hyperovals we observed that several non-arc structures appeared as cyclotomic sets including lines, sets of lines, and grids, as well as many types of configurations, which we will enumerate later. We begin with the formal definition of a type of configuration.
Definition 1 An (nr,Vk) configuration is a point line incidence structure consisting of n points and v lines with the following properties:
1. Each point is incidence with r lines.
2. Each line is incident with k points.
3. Two distinct lines intersect in at most one point and two points are connected by at most one line.
When v = n, and consequently r = k, we refer to an (nr,Vk) configuration as an n.k configuration. We say an n.k configuration is cyclic if there is an automorphism of the configuration that permutes the points in a single cycle. It is natural to identify the points of a cyclic n.k configuration with 7Ln and assume that the automorphism is x > # + 1. Classical examples of cyclic configurations are the Desarguesian projective planes, which are examples of cyclic (q2 + q + l)g+i configuations. It is clear that they are configurations and a well known theorem of Singer [49] shows that the Desarguesian projective planes are cyclic. Singers theorem is often used in the study of Desarguesian projective planes, and it is still an open question as to whether or not the theorem characterizes when a given projective plane is Desarguesian.
We focus our attention on cyclic n3 configurations. In any cyclic n3 configuration
the lines have the form {j, j + a,j + b} for j e Zn and a < b. Following [20], we
use the notation C3[n,a,b\ for such a configuration. We will call the triple [0,a,6] a
generating block for C3[n,a,b\. Cyclic n3 configurations only exist for n > 7 and for
69

each such n a cyclic n3 configuration exists. In fact, the generating block [0,1, 3] will generate an ??,3 configuration for each n > 7 [20]. The Desarguesian projective plane of order 2, seen in Figure 4.1, is an example of a cyclic n3 configuration; it is the unique C3 [T, 1,3].
A configuration is polycyclic if there exists an automorphism of the configuration where all orbits on points and lines are of the same size. This is a generalization of the cyclic configurations described above. See [5] for more information on polycyclic configurations. A polycyclic generalization of cyclic ??.*. configurations which arises naturally is an (ns)k) configuration. We say an (ns)*,) configuration is an
s-iik configuration if there exists an automorphism of the configuration of which each orbit is a cyclic iik configuration. Observe that a l-??.*, configuration is simply a cyclic ilk configuration as previously described.
In [28] Levi proved that C3[n, 1,6] is a configuration for 3 < b < n 2 and b + 1}. More recently, in [27], Koike, Kovacs, and Pisanski count the
number of non-isomorphic cyclic n3 configurations, and give conditions for cyclic n3 configurations to be isomorphic. The question we would like to answer is: For which n, a, b is C3[n,a,b\ a cyclic n3 configuration? According to Griinbaum this question is still open and worth solving. [21]
In section 4.1 we characterize the generating blocks for C3[n,ci,b\. This is an
70

interesting question in its own right, but also can be used to help us give necessary and sufficient conditions for when a cyclotomic set contains an s-iik configuration. In section 4.2 we describe the structures known to be represented by cyclotomic sets and give some necessary and sufficient conditions for when a cyclotomic set represents each structure.
4.1 Determining Generating Blocks
We study the C3[n,a,b\ via their incidence matrices, 0-1 matrices with columns indexed by the points and rows indexed by the lines, where a 1 indicates incidence. Observe that in the incidence matrix of C3[7,1,3], seen in Figure 4.2, if there are ls in positions (Â£, s) and (Â£, t) then Â£ is the unique row for which this is true. If the incidence matrix of a C3[n, a, b] has J2, the 2x2 matrix of all ls, as a submatrix, then one says that the matrix has an embedded J2. In [28] Levi observed that the existence of embedded J2s is enough to determine whether or not a circulant matrix is the incidence matrix of a cyclic ilk configuration. In [27], Koike, Kovacs, and Pisanski formalize this observation. We provide a formal proof for convenience.
0
Â£0 fi
Â£1 0
Â£2 0
Â£3 0
Â£4 1
Â£5 0
4 l1
1 2 CO 4
1 0 1 0
1 1 0 1
0 1 1 0
0 0 1 1
0 0 0 1
1 0 0 0
0 1 0 0
5 6 0 0^ 0 0 1 0 0 1 1 0 1 1
0 V
Figure 4.2: Incidence matrix for C3 [T, 1, 3]
71

Lemma 4.1 A circulant (0,1)-matrix generated by k lJs in the first row is the incidence matrix of an nu configuration if and only if it has no embedded J2.
Proof: This condition is clearly necessary since the existence of an embedded J-2 forces there to be two lines through two points. For the converse, assume that we have a circulant matrix C, generated by a row with k ls, and no embedded J2. Since the sum of row 0 is k and C is circulant, we must have that every row and column sum is k. Hence there are k lines through every point, and k points on every line. The absence of embedded J2s forces the third condition, that two distinct lines intersect in at most one point and two distinct points are connected by at most one line. Hence, C is the incidence matrix of an ??,*. configuration.
We specialize this result to the case k = 3 in order to answer the question posed by Griinbaum. Throughout we will be assuming a < b.
Theorem 4.2 ([27]) An n x n circulant matrix C generated by [0, a, b] has no embedded J-2 if and only if the 6 quantities a, a, b, b, b a, a b are distinct modulo n.
Proof: Assume that an n x n matrix C has an embedded J2. WLOG we may assume that first row of the embedded J2 is in row 0 of C, and in positions (0,a), (0,6), thus the third 1 in row 0 is in position (0,0). Assume that the second row of the J2 is in row Â£ in positions (Â£,s) and (Â£,t). Since C is circulant there are only a few possibilities for s and t, they are:
a + Â£, t = Â£ s = 6 + Â£, t = Â£
Â£,t = a + Â£ s = b + Â£, t = a + Â£
Â£,t = b + Â£
Observe that t s takes on values in the set {a, a, 6, 6, a b} and necessarily we have 6 a = t s, so the quantities mentioned above are not distinct.
72

For the converse, assume that the quantities are not distinct. Since we are assuming that a and b are distinct, and both are different from 0, the possibilities for equivalent quantities modulo n are:
a = a
b = b
a = b
b = a b
a = b a
a = b
b = b a
a = a b
b a = a b
This reduces to the following four cases: f. a = | or b = | 3. b = 2a or a = 2b
2. a + b = 0 4. 6 a = |
We will examine each case.
Case 1: Assume WLOG that = f. The generating block is [0, |,6] and so the 1 s in row 0 in the incidence matrix are located in positions (0, 0), (0, |), (0,6), and in row | the 1 s are in positions (f, f), (f, 0), (|, b + |). Thus (0,0), (0, |), (|, 0), (|, |) is an embedded J2.
Case 2: Assume that a + b = 0 (mod /?.). This forces the generating block to be [0, a, n a], and the 1 s in row a are located in positions (a, a), (a, 2a), (a, 0). Hence (0, 0), (0, a), (a, 0), (a, a) is an embedded J2.
Case 3: Assume WLOG that b = 2ci (mod n) so that the generating block is [0,a, 2a]. If we shift the block by a we get [a, 0,a] as an equivalent generating block, with the sum of the non-zero positions equivalent to 0 (mod /?.), and we can reduce to Case 2.
73

Case 4: Assume that b a = ^ (mod n). This forces the generating block to be [0, a, a + ^]. In row ^ the ls are in positions (f, f), (f, a + |), (|, a) and thus we see (0, a), (0, a T f), (f, a), (|, a + |) is an embedded J-2-
Hence we have found an embedded J2 in each case.
In order to state this result in a manner similar to Levi, we must only realize that given a, we can always choose b in the range 2a < b < n a. Given any generating block [0, a, b] consider the quantity m = min{a, b a, n b}. If m = a then b is in the appropriate range. If m = b a shift the block by a and if m = n b shift the block by b to get an equivalent generating block with the desired property. Using this observation and examining the four scenarios in Theorem 4.2 yields the following corollary:
Corollary 4.3 Given n > 7, a yt then C3[??,, a, b] is a cyclic 113 configuration if and only ifb^L Alp, a + |} when b is chosen in the range 2a < b < n a.
We say two configurations are multiplier equivalent if there exists a unit u G 7Ln for which the map x > it:r is an isomorphism. In [27], it is proved that two cyclic 11.3 configurations are isomorphic if and only if they are multiplier equivalent. This leads us to the following question.
Question 1 Can we use Corollary f.3 and the results from [27] to give a lexicographically minimal set of generating blocks for each n that produce all non-isomorphic n3 configurations?
4.2 Cyclotomic Sets as Geometric Structures
We will describe geometric structures in AG(2,q), q = 2h, known to be represented by cyclotomic sets. We begin with two observations about the sizes of cyclotomic sets.
74

Observation 1 There exists a cyclotomic set of size c in GF(22h) if and only if c | 2h. For : x > x2, |C^(/5)| = c if and only if (3 Â£ GF(2C) but in no proper subfields of GF(2C).
Observation 2 For fi : x > x2, and a : x > x2e we have
\c*m
\cm\
(e,\CM\Y
We now describe when a cyclotomic set of size c is a collection of disjoint line segments, which are subsets of points on a line. We use the notation \f3\ to denote the order of [3 in GF(q2).
Theorem 4.4 If Ca((3), with \Ca((3)\ = c, and [3 0, consists of exactly m disjoint
line segments then the line segments are
L = {f3a3, f3am+3, [3a2m+3,..., f3adm+3}, where d= 1,
m
and 0 < j < m 1. We call this a set of m-regular line segments.
Proof: Assume that Ca((3) consists of exactly m disjoint line segments and
let \Ca{f3)\ = c so that the order of 2e (mod |/5|) is c. First observe that if Â£ is
a line segment, then Â£a is a line segment with the same length by Corollary 2.7.
Since Ca((3) is an orbit we will exhaust all of its elements by repeatedly applying
Â£o, Â£i, ,Â£m-i- Assume WLOG that fi Â£ (f. Let u = min({s : j3aS Â£ Â£q} {0}),
v = min({s : [3aS Â£ Â£0} {0, u}), and call (/5, /3 want to show u = m and v = 2m. Since the Â£j are disjoint we know that /3 cannot be on any lines other than Â£0. Thus, any collinear triple in Ca([3) containing
any of (3, /3 the form (/3a'\ /3 Consider the triple (/3 to the minimal triple in Â£0. This must be a collinear triple, and so these points must
75

2 u
be on Â£0. Hence, v < 2u by the definition of v, since /5"J lies on Â£0. Now, assume that v < 2u and let c = v u and note c < u. Applying the automorphism az to the minimal triple in Â£0 gives the collinear triple (j3a', /5'+', /3 Continuing in a similar manner we let w = min({s : (3* E Â£q} {0, u, 2u}). By an argument similar to that above we must have w = 3u, and continuing the argument iteratively yields Â£0 = {/3 (mod |/5|) and so u is the order of 2eA>l (mod |/5|), hence u = Since all of the
line segments have the same size we know that \Â£0\ = therefore u = m.
At this point we have
Â£o = {/3, l3an (3a2m,..., f3adm }, where d= - 1,
m
so we can apply the automorphisms cC 0 < j < m 1 to Â£0 to get the lines

rn+j
P
r2 m+j

Since we are assuming the line segments are disjoint we have described them all.
Observe that a set of 1-regular line segments is just a single line segment. The structures currently known to be represented by cyclotomic sets are sets of regular line segments, s-iik configurations, and arcs. Additionally, regular line segments can be superimposed on top of one another, creating grids, and on configurations, creating configurations with a parallelism. The next theorem provides a description of when a cyclotomic set contains a set of ?n-regular line segments.
Theorem 4.5 In AG(2, 2h), Ca{(3), with a : x > xr\ for 0 < e < h 1, contains a set of m -regular line segments if and only if ([3+[3a" )q~1 E GF(2t) where t = (em, 2h).
Proof: Assume that Ca([3) contains a set of ?n-regular line segments, so neces-
76

sarily we have that the points /5, [3a", [3^" are collinear. Consequently,
y (/3 + [3amy~i = y (/3 Thus,
(/? + /3 putting (/5 + /3 For the converse, assume that (/5 + /T7")9-1 G GF(2t) and let (/5 + /3 hence, Tz([3) G GF(2t). Thus
TY/3) = Tz(i3ms)
for 1 < s < ff 1 and so the points [3, [3an, /3m are collinear. Applying the automorphisms cC for 1 < j < m 1 produces the m-regular line segments. When studying cyclotomic sets it is often convenient to talk about the positions of elements by imposing an order on the set. Since each element is the image of the generator /3 under some power of the automorphism Lemma 4.6 The 0, a, 6 positions of Ca((3) are collinear if and only if [3 is a root of the polynomial function pa,b,a ' GF(q2) > GF(q2) where
PaAa(z) = n XaCl + Xxab + (A + 1)#
XeGF(q)
Proof: By Corollary 2.4 we know that the points (3, (3aa, and j3ab are collinear if and only if
do + = v/o + V>-1,
which is true if and only if there exists some A G GF(g) for which
0 + lT = \(0 + 0i),
77

from which the result follows.
We can now describe when a cyclotomic set is an arc. We note that if a cyclotomic set is an arc then it necessarily has no collinear triples. Using Lemma 4.6 we define a polynomial whose roots are all of the elements that generate a cyclotomic set with at least one collinear triple. Let S = {\Ca([d)\ : /5 G GF(q2)} and n = max-jT : x G S}. We define
f(x)= II P^(x)
1 Observe that if Ca([d) has a collinear triple then we may assume that /5 is included in a collinear triple, by the cyclic nature of Ca([d). Additionally, we may assume that the middle position of the collinear triple lies between 1 and ^ since otherwise we may use a cyclic shift to produce a collinear triple with this property. This proves the following corollary.
Corollary 4.7 Ca([d) is an arc if and only if fd is a root of the polynomial
n2
<~y-- y I /y*
\ ( \
GCD(f(xf,xq2+x)
We can now give necessary conditions for when a cyclotomic set could be an s-iik configuration. Observe that [0, UU2, , U-i] is a generating block for a cyclic configuration if and only if [U, tj, tf\ is a generating block for a cyclic n3 configuration for any choices of i,j,Â£ with i ^ j ^ Â£. Recall from Theorem 4.2 that we identified the problem cases for the collinear triple [0, a, b] to generate a cyclic n3 configuration. We define the following set
Ba,c = {b G Zc : b = |, a + b = 0, b = 2a, b a = |}
We use this set to describe s-iik configurations, as we did arcs in Corollary 4.7, so we define the following polynomial,
9(x) = II II P**AX)-
c 78

In order for an s-n,k configuration to exist we have to ensure that only appropriate collinear triples exist. By eliminating the elements that generate cyclotomic arcs, as well as the triples that fail to generate a cyclic n3 configuration we isolate the Ca(fi) that could be s-iik configurations. The polynomial
A^ = GCD(g(x),x^ + x)
has roots that generate a cyclotomic set that is an arc, or a configuration with the appropriate collinearities. Hence, Corollary 4.7 allows us to give necessary conditions for when Ca(fi) could be an s-iik configuration.
Corollary 4.8 Ca(fi) is an s-n.k configuration if and only if fi is a root of the polynomial
C(x)
AC(x)
GCD(AC(x),A(x))'
4.3 Examples
We conclude with some examples from small planes. The following examples are not exhaustive but rather are chosen to give the reader a feel for what exists. We give the minimal polynomials for GF(q2) and note that the elements of GF(g) are identified as elements of the form /3^+1b for 0 < j < q 2, where /3 generates the multiplicative group of GF(q2). In each of the remaining examples the cyclotomic sets are formed under the automorphism a : x > x2.
4.3.1 AG(2,16)
There are four cyclotomic sets in AG(2,16) that are the Mobius-Kantor configuration. These are the only configurations found as cyclotomic sets in AG(2,16). The configuration polynomial, N3(x), for these configurations is shown below where we construct GF(256) with minimal polynomial x8 + x4 + x3 + x2 + 1. Each factor in the given factorization below is a polynomial whose roots are the points of a single
79

Mobius-Kantor configuration.
N3(x) = x32 + x28 + x26 + x24 + x22 + x14 + x12 + ;r9 + x4 + ;r3 + ;r2 + x + 1 = (x8 + x' + ;r6 + ;r5 + x2 + ;r + l)(;r8 + x + ;r5 + x3 + 1)
(x8 + K + ;r6 + x + 1)(^8 + x1 + ;r4 + ;r3 + x2 + ;r + 1)
For instance, the roots of x8 + x + x6 + ;r5 + ;r2 + x + 1 are elements
l3n,P22,P44,P88,P17\P97,P
194
/3133 G GF(q2).
The Mobius-Kantor configuration in Figure 4.3 has points labeled with these roots, showing the appropriate collinearities.
Figure 4.3: C3[8,1,3]: A Mobius-Kantor configuration found in AG(2,16)
4.3.2 AG(2,64)
In AG(2,64) we find instances of cyclotomic sets that are grids, as well as cy-clotomic sets that are a configuration with a parallelism. There are 8 instances of the 4x3 grid, 36 cyclic 123 configurations, and 12 instances of (124,163) configurations that consist of a 123 configuration with a 4-regular parallelism. We construct GF(4096) with the minimal polynomial x12 + K +ir6 + ir5+ir3 + ir + l. The roots of the polynomial
X12 + x8 + ir6 + x5 + x3 + x2 + 1
80

form a cyclotomic set that is the 4x3 grid. The 123 configurations appear with many different generating blocks, one of which is [0, f, 3]. The roots of the polynomial
x12 + x11 + x10 + ;r9 + ;r5 + x3 + x2 + x + f
form a cyclotomic set that is a C3[12,1, 3], and Figure 4.4a shows a realization of this configuration.
Two of the (124,163) configurations that consist of a 123 configuration with a 4-regular parallelism, have a C3[12,1, 3] as its underlying cyclic 123 configuration. The roots of the following polynomial give a cyclotomic set that is this configuration. A realization is given in Figure 4.4b.
x12 + x9 + x8 + x6 + x5 + x4 + 1
(a) C3[12,1,3] (b) C3[12,1,3] with parallelism (dashed)
Figure 4.4: Configurations found as cyclotomic sets in AG(2,64)
4.3.3 AG(2,256) and Larger Planes
The affine plane AG(2,256) is the smallest plane in which we find an s-n3 configuration for s > 1. There are 16 instances of cyclotomic sets that are a 2-163 configuration. We construct GF(216) with the minimal polynomial rr16 + x5 + x3 + x2 + 1.
81

The roots of the polynomial
;r16 + ;r10 + j-9 + x1 + ;r6 + x + 1
are a 2-163 configuration. It decomposes into a C3 [16,1,5] and a C3 [16, 3,10]. In larger planes we also find s-n3 configurations, including some with an additional parallelism. In AG(2,512) there are cyclotomic sets that are (187, 423) configurations. This configuration has a 6-regular parallelism, and removing it produces a 2-183 configuration. In AG(2,1024) there are 64 cyclotomic sets that are 2-203 configurations, and 4 cyclotomic sets that are 203 configurations. In AG(2,2048) there are 12 cyclotomic sets that are 3-223 configurations, and in AG(2,4096) there are cyclotomic sets that are ??4 configurations, some with a parallelism.
4.4 Open Questions
1. Are there any other structures that can be represented by cyclotomic sets?
2. Is there a better description of cyclotomic arcs that is not by exclusion?
3. Is there an algebraic description, perhaps some conditions on /3 and <7, that identifies when the union of two cyclotomic arcs is an arc? Such a description would help in the search for new hyperovals as described in Chapter 3.
82

REFERENCES
[1] Ball, S. Polynomials in finite geometries. Surveys in combinatorics, 1999 (Canterbury), 17-35, London Math. Soc. Lecture Note Ser., 267, Cambridge Univ. Press, Cambridge, 1999.
[2] Bartocci, U., Segre, B. Ovali ed altre curve nei piani di Galois di caratteristica due. Acta Aritlnnetica, (1971), 18: 423-449.
[3] Betten, A. Orbiter A Program to Classify Discrete Objects, http://www.math. colostate.edu/~betten/orbiter/orbiter.html
[4] Beutelspacher, A., Rosenbaum, U. Projective geometry: from foundations to applications. Cambridge University Press, Cambridge, 1998.
[5] Boben, M., Pisanski, T. Polycyclic configurations. European J. Combin. 24 (2003), no. 4, 431-457.
[6] Wieb Bosnia, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235-265.
171 Brown, J., Cherowitzo, W. The Lunelli-Sce hyveroval in PG(2,16). J. Geom. 69 (2000), no. 1-2, 15-36.
[8] Cardinali, I., Payne, S. E. q-clan geometries in characteristic 2. Frontiers in Mathematics. Birkhauser Verlag, Basel, 2007.
[9] Casse, Rey Projective geometry: an introduction. Oxford University Press, Oxford, 2006.
[10] Cherowitzo, W. a-flocks and hyperovals. Geom. Dedicata 72, (1998), (3): 221 246.
[11] Cherowtizo, W. Hyperovals in Desarguesian planes of even order Annals Disc. Math. 37 (1986) 87-94.
[12] Cherowitzo, W. Hyperovals in Desarguesian planes: an update. Combinatorics (Acireale, 1992). Discrete Math. 155 (1996), no. 1-3, 31-38.
[13] Cherowitzo, W.E., Payne, S.E. The cyclic q-clans with q = 2e Advances in Geometry, Special Issue (2003) S158-S185.
[14] Cherowitzo, W.E., OKeefe C.M., Penttila, T. A unified construction of finite geometries associated with q-clans in characteristic 2 Adv. Geom. 3 (2003), 1-21.
83

[15] Cherowitzo, W., Penttila, T., Pinneri, L, Royle, G. F. Flocks and ovals. Geom. Dedicata 60 (1996), no. 1, 17-37.
[16] Cherowtizo, W.E., Storme, L. a-Flocks with Oval Herds and Monomial Hyperovals Finite Fields and their Applications 4, (1998) 185-199.
[17] Fisher, J. C., Schmidt, B. Finite Fourier series and ovals in PG(2,2h). J. Aust. Math. Soc. 81 (2006), no. 1, 21-34.
[18] Glynn, D. A condition for the existence of ovals in PG(2, q), q even. Geometria Dedicata 32 (1989), 247-252.
[19] Glynn, D. Two new sequences of ovals in finite Desarguesian planes of even order. (Combinatorial mathematics, X) Lecture Notes in Math. 1036, Berlin: Springer,(1983), pp. 217-229.
[20] Griinbaum, B. Configurations of Points and Lines. American Mathematical Society, Rhode Island, 2009.
[21] Griinbaum, B. Personal Communication, April 2014.
[22] Hall, M., Jr. Ovals in the Desarquesian plane of order 16. Ann. Mat. Pura Appl. (4) 102 (1975), 159-176.
[23] Hernando, F., McGuire, G. Proof of a conjecture of Segre and Bartocci on monomial hyperovals in projective planes. Des. Codes Cryptogr. 65 (2012), no. 3, 275-289.
[24] Hirschfeld J.W.P. Projective Geometries Over Finite Fields. Oxford Mathematical Monographs, second edition. The Clarendon Press Oxford University Press, New York (1998).
[25] Hughes, D.R. and Piper, F.C. Projective Planes. Springer-Verlag New York, 1973.
[26] Jamison, R. Covering finite fields with cosets of subspaces, Journal of Combinatorial Theory, Series A, 22 (1977), 253-266.
[27] Koike, H., Kovacs, I. Pisanski, T. The number of cyclic configurations of type (v-i) and the isomorphism problem. J. Combin. Des. 22 (2014), no. 5, 216 229.
[28] Levi, F. Geometrische Konfigwrationen Hirzel, Leipzig, 1929.
[29] R. Lidl and H. Niederreiter. Finite Fields (Encyclopedia of Mathematics and its Applications). Cambridge University Press, 1996.
[30] Lunelli, L., See, M. k-archi completi nei piani proiettivi desarguesiani di rango 8 e 16 Centro di Calcoli Numerici, Politecnico di Milano, 1958.
[31] OKeefe, C. M., Penttila, T. A New Hyperoval in PG(2,32) Journal of Geometry 44 (1992) 117-139.
84

[32] OKeefe, C. M., Penttila, T. Hyperovals in PG(2,16). European J. Combin. 12 (1991), no. 1, 51-59.
[33] OKeefe, C. M., Penttila, T. Symmetries of Arcs. J. Combin. Th. Ser. A 66, (1994) 53-67.
[34] OKeefe, Christine M., Thas, J. A. Collineations of Subiaco and Chewwitzo hyperovals. Bull. Belg. Math. Soc. Simon Stevin 3 (1996), no. 2, 177-192.
[35] Payne, S. E. A new infinite family of generalized quadrangles. Congressus Nu-merantium, (1985), 49: 115-128.
[36] Payne, S.E. Topics in Finite Geometry: Ovals, Ovoids, and Generalized Quadrangles. UC Denver Course Notes, 2008.
[37] Payne, S. E.,Conklin, J. E. An unusual generalized quadrangle of order sixteen. J. Combinatorial Theory Ser. A 24 (1978), no. 1, 50-74.
[38] Payne, S.E., Thas, J.A. The Stabilizer of the Adelaide Oval Discrete Mathematics 294 (2005) 161-173.
[39] Payne, S. E., Penttila, T., Pinneri, I. Isomorphisms between Subiaco q-clan geometries. Bull. Belg. Math. Soc. Simon Stevin 2 (1995), no. 2, 197-222.
[40] Penttila, T., Pinneri, I. Irregular hyperovals in PG(2,64). J. Geom. 51 (1994), no. 1-2, 89-100.
[41] Penttila, T. Royle, G. Classification of hyperovals in PG(2,32). J. Geom. 50 (1994), no. 12, 151 158.
[42] Penttila, T., Royle, G. On Hyperovals in Small Projective Planes Journal of Geometry 54 (1995) 91-104.
[43] Penttila, T., Storme, L. Monomial Flocks and Herds Containing a Monomial Oval Journal of Combinatorial Theory, Series A, 83 (1998), 21-41.
[44] Pisanski, T., Servatius, B. Configurations from a graphical viewpoint. Birkhauser/Springer, New York, 2013.
[45] Robbins, N. Beginning Number Theory. Jones and Bartlett, Massachusetts, 2006.
[46] Segre, B. Ovali e curve o nei piani di Galois di caratteristica due. Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8) (1962), 32: 785-790.
[47] Segre, B. Ovals in a finite projective plane. Canadian Journal of Mathematics 7 (1955), (0): 414-416.
[48] Segre, B. Sulle ovali nei piani lineari finite Rend. Accad. Naz. Lincei 17 (1954), 141 142.
85

[49] Singer, J. A theorem in finite projective geometry and some applications to number theory. Trans. Amer. Math. Soc. 43 (1938), no. 3, 377-385.
[50] Thas, J. A., Payne, S. E., Gevaert, H. A family of ovals with few collineations. European J. Combin. 9 (1988), no. 4, 353-362.
[51] Vis, Timothy L. Monomial hyperovals in Desarguesian planes. Thesis (Ph.D.)-University of Colorado at Denver. 2010.
86

Full Text
Theorem 1.12 ([23]) For any fixed even positive integer k, if k 6 and k 2l then the set D(xk) is a hyperoval in PG(2,q) for at most a finite number of values of q.
The collection of these results suggests that there are no more monomial hyperovals. Combining this information with the o-polynomials of the most recently discovered hyperovals makes us expect that new hyperovals will have increasingly complicated o-polynomials, providing even more motivation for this thesis.
The automorphism groups of hyperovals have played an important role in their study. Historically hyperovals have been identified by their groups. When a new hyperoval was found, it was shown to be distinct from previously known families via its automorphism group, and its existence in different planes. Table 1.2 shows the sizes of the automorphism groups for all known families of hyperovals.
Hyperovals are currently classified in PG(2,2/l) for 1 < h < 5, and hyperovals with nontrivial automorphism group are classified in PG(2, 64). It is well known that all hyperovals in PG(2,2/l) for 1 < h < 3 are hyperconics. See [24] for a proof of this classification. Hyperovals in PG(2,16) were originally classified by Hall in 1975 [22], All hyperovals in PG(2,16) are projectively equivalent to the hyperoconic, or the Lunelli-Sce hyperoval described above. In order to classify hyperovals in this plane Hall needed the help of a computer, however in 1991 OKeefe and Penttila [32] classified the hyperovals in PG(2,16) without the aid of a computer.
In 1994 the hyperovals in PG(2,32) were classified by Penttila and Royle by exhaustive computer search [41], Every hyperoval in PG(2,32) is projectively equivalent to either the hyperconic, translation, Segre, Payne, Cherowitzo, or OKeefe-Penttila hyperoval. Penttila and Royle are also responsible for the partial classification of hyperovals in PG(2,64). They showed that if a new hyperoval exists in PG(2,64) then it must have a trivial automorphism group in [42], They use a technique known as prime at at time that we discuss in Chapter 3. It is generally believed that there are no other hyperovals in PG(2,64), as a hyperoval with a trivial automorphism group
12

Consider the following system of equations
fM + cAlx) = pM
/(t2*) + g{i2x) = p{i2x) f{id~lx) + g{id~lx) = p{id~lx)-
Observe that there are cl 1 equations here, and cl 1 is even since d is a prime, cl ^ 2. Now, since fip(x) = f(x) and pip(x) = p(x) we have f(Ax) = f(x) and pip(xx) = p(x) for 1 < j < cl 1. Thus, by adding the cl 1 equations together we obtain
d-1
*52 9(ljx) = -
3 = 1
By Lemma 2.20 and Lemma 2.21 we have YApL\ ljt = 1 provided that t ^ 0 (mod d), and so,
d-1 /d-l \
^ g{pyjx) = ^ I I at#* = p(#) = 0 for all x E M.
j=1 t^O (mod Observe that g is a polynomial of degree at most q 1 since p has degree at most q 1. However, the q + 1 elements of A/ are roots of g, so g must be the zero polynomial. Hence
p(:x) = f(x) + g(x) = f(x) for all x E Af,
showing that p has the proposed form.
2.5 The Relationship to o-polynomials
We can now give a method for turning known o-polynomials into p-polynomials,
and vice-versa. We wish to note that this general conversion formula will not always give the most elegant p-polynomials, and specific considerations will be given for certain families in the following sections. We begin with a useful formula for converting between cartesian and polar coordinates.
Lemma 2.23 The point ga in polar coordinates corresponds to the point (q'T(^), Q'T('p), 1) in cartesian coordinates.
30

PAGE 1

PAGE 2

ThisthesisfortheDoctorofPhilosophydegreeby PhilipA.DeOrsey hasbeenapprovedforthe DepartmentofMathematicalandStatisticalSciences by WilliamCherowitzo,Advisor MichaelFerrara,Chair StanleyPayne TimPenttila JasonWilliford April22,2015 ii

PAGE 3

DeOrsey,PhilipA.Ph.D.,AppliedMathematics HyperovalsandCyclotomicSetsinAG ;q ThesisdirectedbyProfessorEmeritusWilliamCherowitzo ABSTRACT Inthisdissertationweintroduceanewpolynomialrepresentationofhyperovals calleda -polynomial.The -polynomialisdenedinAG ;q andusesarepresentationofthepointsofAG ;q aselementsofGF q 2 .Weprovidestructuralresultsof -polynomialslinkingpropertiesoftheircoecientstospecicmapsthatstabilizethe representedhyperoval.Additionally,weprovideaconnectionbetween -polynomials ando-polynomials,andgivenice -polynomialrepresentationsforseveralfamiliesof hyperovals. WealsostudytheorbitsoftheeldautomorphismsofGF q 2 whichinduce collineationsinAG ;q .Wecalltheseorbitscyclotomicsets,andnotethatcyclotomicsetscanbemanydierentstructures.Weusecyclotomicarcstobuild hyperovals,andperformsearchesfornewhyperovalsinaneplanesofsmallorder. Wendnonewhyperovals,butthesesearchesclassify -polynomialswithspecic propertiesincertainaneplanes. Inthenalchapterwestudyotherstructuresthatappearascyclotomicsets.We showthatcongurationscanberepresentedandprovidenewresultsoncongurations inordertodeterminewhentheycanappear.Wealsoprovideadescriptionofwhen acyclotomicsetrepresentseachoftheotherstructurestheyareknowntorepresent. Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:WilliamCherowitzo iii

PAGE 4

PAGE 5

TABLEOFCONTENTS Figures.......................................vii Tables........................................viii Chapter 1.IntroductionandBackground.........................1 1.1Overview.................................1 1.2BackgroundonFiniteFields......................2 1.3BackgroundonPG ;q .........................3 1.4BackgroundonHyperovals.......................6 1.5AHistoryofHyperovals.........................9 2.The -polynomialRepresentation.......................14 2.1ADescriptionofthePolarModel...................14 2.2CollineationsinthePolarModel....................18 2.3Using -polynomialstoRepresentHyperovals.............21 2.4StructuralPropertiesof -polynomials.................24 2.4.1BasicStructuralProperties...................25 2.4.2HyperovalsStabilizedbyFieldAutomorphisms........26 2.4.3HyperovalsStabilizedbyMultiplicativeMaps.........28 2.5TheRelationshipto o -polynomials...................30 2.6The -polynomialsforKnownHyperovals...............33 2.6.1Hyperconic............................33 2.6.2TranslationHyperovals......................41 2.6.3TheSegreHyperoval.......................45 2.6.4TheAdelaideHyperoval.....................47 2.6.5TheSubiacoHyperoval.....................50 2.6.6OtherFamilies..........................54 3.AComputationalApproach..........................56 v

PAGE 6

3.1CyclotomicSets.............................56 3.2Using -polynomialstoSearchforHyperovals.............57 3.2.1SearchesinAG,16.......................60 3.2.2SearchesinAG,32.......................61 3.2.3SearchesinAG,64.......................63 3.2.4SearchesinAG,128......................63 3.2.5SearchesinAG,256......................64 3.2.6SearchesinAG,512......................67 4.StructuresrepresentedbyCyclotomicSets..................69 4.1DeterminingGeneratingBlocks.....................71 4.2CyclotomicSetsasGeometricStructures...............74 4.3Examples.................................79 4.3.1AG,16.............................79 4.3.2AG,64.............................80 4.3.3AG,256andLargerPlanes..................81 4.4OpenQuestions.............................82 References ......................................83 vi

PAGE 7

FIGURES Figure 1.1DesarguesConguration...........................4 2.1ThePolarRepresentationofAG, q ....................18 3.1ASectorwithaCyclotomicSet......................57 4.1PG,2:TheFanoPlane..........................70 4.2Incidencematrixfor C 3 [7 ; 1 ; 3]........................71 4.3 C 3 [8 ; 1 ; 3]:AMobius-KantorcongurationfoundinAG,16.......80 4.4CongurationsfoundascyclotomicsetsinAG,64...........81 vii

PAGE 8

TABLES Table 1.1o-polynomialsforknownhyperovals.....................9 1.2Thegroupsofknownhyperovals......................13 3.1RunTimesforBacktrackSearches.....................58 3.2RunTimesforCliqueFinder........................59 3.3 -polynomialsforhyperovalsinAG ; 16.................61 3.4 -polynomialsforhyperovalsinAG ; 32.................62 3.5 -polynomialsforhyperovalsinAG ; 64.................63 3.6 -polynomialsforhyperovalsinAG ; 128.................65 3.7 -polynomialsforhyperovalsinAG ; 128...............66 3.8 -polynomialsforhyperovalsinAG ; 256.................67 viii

PAGE 9

1.IntroductionandBackground 1.1Overview Themainfocusofthisworkistostudyanewrepresentationofhyperovalsthatwe calla -polynomial.The -polynomialisanextensionofworkdonebyChrisFisher andBernhardSchmidtwheretheyuseniteFourierseriestorepresenthyperovals. Hyperovalshavetraditionallybeenrepresentedbypolynomialscalledo-polynomials whichhavebecomeincreasinglycomplicatedasnewexampleshavebeendiscovered. Ithasbeenoveradecadesinceanewhyperovalhasbeendiscovered,whichislong, consideringhyperovalshaveonlybeenstudiedsignicantlyfor50years.Withthis motivationweareinneedofsomenewperspectiveforstudyinghyperovals,sowe suggesttheuseof -polynomials. Westudythestructuralpropertiesof -polynomialsviatheircoecients.Where FisherandSchmidtlookedforrepresentationswheremanycoecientswere0,we considerhyperovalswithcoecientsincertainsubelds,andwithspeciccoecients being0.Whilestudying -polynomialsonenoticesthatifthecoecientsofthepolynomialshavecertainpropertiesthenthatimpliesspecicmapsstabilizethehyperoval itrepresents.Theorbitsofthesemapscanbeusedasbuildingblocksofhyperovals whichleadstonewandinterestingsearchesforhyperovals.Thisapproachhassome precedentasitwasusedbyO'KeefeandPenttilain[31],PenttilaandPinneriin[40], andPentillaandRoylein[42].Wewilldiscusstheresultsofthesesearchesinane planesofsmallorder,andgive -polynomialrepresentationsforalloftheknownfamiliesofhyperovalsintheseplanes.Further,wegive -polynomialrepresentationsfor severalfamiliesofhyperovalsinallplanes. AmongtheactionsthatweareparticularlyinterestedinaretheeldautomorphismsofGF q 2 whichinducecollineationsinAG ;q .TheorbitsoftheseautomorphismsarestructuresinAG ;q thatwecallcyclotomicsets.Ifthesesetsare arcsthenwecanusethemtobuildhyperovals.However,asitturnsout,theyarenot 1

PAGE 10

alwaysarcs.Wefoundthatthesesetscanrepresentotherstructures,includingline segmentsandgrids,butthemoreinterestingcongurationscanarise.Wedetermine whenacyclotomicsetcanbeeachofthesedierentstructures.Indoingso,weobtain somenewresultsoncongurations. 1.2BackgroundonFiniteFields A niteeld isanalgebraicstructurewithtwooperationscalledadditionand multiplication.The order ofaniteeldisthenumberofelementsintheeld. Anyniteeldhasorder q = p h forsomeprime p and h apositiveinteger.Wewill usethenotationGF q todenotetheniteeldoforder q .Theprime p iscalled the characteristic oftheeld;itistheleastinteger p forwhich P p j =1 1=0.The elementsofGF q underadditionformanabeliangroup,andthenonzeroelements ofGF q ,denotedGF q ,formacyclicgroupundermultiplication.Ageneratorof themultiplicativegroupiscalleda primitive elementofGF q A subeld ofGF q isasubsetoftheelementsthatisaeldunderthesame operations.AsubeldofGF p h oforder p k existsifandonlyif k j h .The prime subeld ofGF p h istheintersectionofallsubelds,andisisomorphictoGF p Finiteeldsoforder p h existforallprimes p andallpositiveintegers h .Furthermore, thereisauniqueelduptoisomorphismofeachorder. ThegroupofautomorphismsofGF p h isgeneratedbythemap : x x p whichiscalledthe Frobeniusautomorphism .Hence,thegroupofautomorphisms ofGF q isAutGF q = f : x x p r :1 r h g Amapthatisofparticularinteresttousisthe relativetracemap .Let F = GF q E =GF q h ,and a 2 E .Therelativetracemapfrom E to F T E=F : E F isdenedas T E=F a = a + a q + a q 2 + + a q h )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 : Therelativetracemapisadditiveandinvariantunderautomorphisms,thatis T E=F a + b = T E=F a + T E=F b forall a;b 2 E ,and 2

PAGE 11

T E=F a = T E=F a forall a 2 E andall 2 Aut E If F istheprimesubeldof E thenwecallthismapthe absolutetracemap Theabsolutetracemapisfrequentlyused,sowereservethenotation tr todenoteit. TherelativetracemapfromGF q 2 ontoGF q willbefrequentlyused,sowewill denotethismapsimplyas T x Denition1.1 TherelativetracemapfromGF q 2 toGF q is T x = x + x q : Anothermapweareinterestedinisthe relativenormmap .Therelativenorm mapfrom E to F N E=F : E F isdenedas N E=F a = a 1+ q + q 2 + + q h )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 = a q h )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 : Theelementswhoseimageundertherelativenormmapis1arecalled norm1 elements .Theformofnorm1elementsiswellknownandisgiveninthenext theorem. Theorem1.2[36] N E=F a =1 ifandonlyif a = b q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 forsome b 2 F Wereferto[29]formoreinformationonniteelds. 1.3BackgroundonPG 2 ;q Thereareniteprojectivespacesofdimension n forany n 2 Z + ,butthefocusof thisworkwillbeonthe2-dimensionalprojectivespacecalledaprojectiveplane.A projectiveplane isapoint-lineincidencestructurethatisdenedbythefollowing axioms. 1.Anytwodistinctpointsareconnectedbyexactlyoneline. 2.Anytwodistinctlinesmeetatexactlyonepoint. 3.Thereexistsasetoffourpointsnothreeofwhicharecollinear. 3

PAGE 12

The order ofaprojectiveplaneisdenedtobeonelessthanthenumberof pointsonaline.Inaprojectiveplaneoforder q thereare q 2 + q +1points, q 2 + q +1 lines, q +1pointsoneveryline,and q +1linesthrougheverypoint.Theonlyknown projectiveplaneshaveorder p h where p isaprime,and h 1isaninteger.Itisstill anopenquestionastowhetherprojectiveplanesofnon-primepowerorderexist. Aprojectiveplaneoforder q canbeconstructedasa3-dimensionalvectorspace overGF q ,theniteeldwith q elements.Thepointsarethe1-dimensionalsubspaces,andthelinesarethe2-dimensionalsubspaces.Incidenceisset-theoretical containment.AprojectiveplaneconstructedinthismannerisdenotedPG ;q Thereareprojectiveplanesoforder q thatarenotisomorphictoPG ;q butwewill notdiscussthemhere,see[25]formoreinformation.Weoftenrefertotheprojective planesconstructedinthismannerasDesarguesian,sinceDesarguestheoremholdsin aprojectiveplaneifandonlyifitisisomorphictooneconstructedinthisway. Theorem1.3Desargues Twotrianglesareinperspectivefromapointifand onlyiftheyareinperspectivefromaline. Figure1.1:DesarguesConguration ThisworkisfocusedonasubstructureofPG ;q calledAG ;q .AG ;q is 4

PAGE 13

theaneplaneoforder q ,andcanbeconstructedbyremovinganyonelinefrom PG ;q sincealllinesareprojectivelyequivalentinPG ;q .Wedenotetheline removedas ` 1 .ThepointsofAG ;q arethepointsofPG ;q noton ` 1 and thelinesofAG ;q arethelinesofPG ;q ,except ` 1 ,restrictedtothepointsof AG ;q A collineation isaone-to-onemapfromaprojectiveplaneontoitselfthatmaps collinearpointstocollinearpoints.Thesetofallcollineationsofaplaneisknown asthe collineationgroup oftheplane.ThecollineationgroupofPG ;q isdenotedPL ;q .TherearetwotypesofcollineationsinPG ;q ,homographiesand automorphiccollineations. If A isanon-singular3 3matrixoverGF q ,thenthemap :PG ;q PG ;q denedby x;y;z x;y;z A iscalleda homography .If isanautomorphismofGF q thenthemap :PG ;q PG ;q denedby x;y;z x ;y ;z iscalledan automorphiccollineation .AnimportantsubgroupofPL ;q isthe subgroupconsistingofallhomographies,denotedPGL ;q .Thefollowingtheorem, knownasthefundamentaltheoremofprojectivegeometry,showsthatanycollineation istheproductoftheonesdescribedabove. Theorem1.4FundamentalTheoremofProjectiveGeometry Every collineationofPG 2 ;q canbewrittenastheproductofahomographyandanautomorphiccollineation. OnefactthatwewillusefrequentlyisthatPL ;q actstransitivelyonquadrangles,setsoffourpoints,nothreeofwhicharecollinear.Thatis,thereexistsa collineationmappinganyquadrangletoanyotherquadrangle. 5

PAGE 14

Theorem1.5[9] Giventwoorderedquadrangles A 1 A 2 A 3 A 4 and B 1 B 2 B 3 B 4 of PG 2 ;q ,thereexistsauniquehomography with A i = B i 1 i 4 Wereferto[4],[9],and[24]formoreinformationonPG ;q 1.4BackgroundonHyperovals Weareinterestedinstudyingseveralstructuresthatexistinprojectiveplanes, oneofwhichisanarc.A k-arc inaprojectiveplaneisasetof k points,nothreeof whicharecollinear.Itcanbeshownthat k q +2when q iseven,and k q +1 when q isodd.A q +1-arciscalleda oval anda q +2-arciscalleda hyperoval Theorem1.6[9] ThemaximumsizeofanarcinPG 2 ;q is q +2 Proof: Let A beanarcinPG, q and P beapointon A .Sincethereare q +1 linescontaining P A canhaveatmostonepointfromeachoftheselines.Withthe observationthatthelinesthrough P partitiontheplaneweseethat j A j q +2. Theorem1.7[9] When q isoddthemaximumsizeofanarcinPG 2 ;q is q +1 Proof: Assumetothecontrarythat A isanarcinPG, q q oddandthat j A j = q +2.Let P beapointon A .Sincethereare q +1linesthrough P andthere are q +1otherpointson A eachlinethrough P mustmeetexactlyoneofthesepoints. Hence,anylineoftheplanemeets A ineither0or2points.Now,let Q beapoint noton A .Thelinesthrough Q mustmeet A ineither0or2points,andtheymust partition A ,hence q +2 = 2isaninteger,implying q iseven,acontradiction. Theorem1.8[9] InPG, q q even,everyovaliscontainedinauniquehyperoval. Proof: Let O beanovalinPG, q q even,andlet P beapointon O .Since O has q pointsdistinctfrom P ,andthereisalinejoining P toeachofthesepoints,and q +1linesthrough P ,theremustbeexactlyonelinetangentto O at P .Therefore, O has q +1tangentlines. 6

PAGE 15

Now,let Q beapointnoton O .Sincethelinesthrough Q partition O and q +1 isodd,theremustbeatleastonetangentlinethrough Q .Let m beasecantline to O andsay m meets O at P and R .Weknowthatthereisexactlyonetangent linethrough P and R ,andgiven S 2 m S 6 = P;R thereisatleastonetangentline through S .Eachtangentlineto O meets m inexactlyonepoint,andsincethereare q +1tangentlinestherecanbeatmostonetangentlineateachpointsinceeach pointon m seesatleastone.Hence,onanysecantline,thereisexactlyonetangent linethrougheachpoint. Let X betheintersectionoftwotangentlinesto O .Since X isontwotangent linesitcannotbeonanysecantlines.However,thelinesthrough X partition O ,so everylinethrough X isatangentline.Therefore,adding X to A producesasetof q +2pointsnothreeofwhicharecollinear,making A [f X g ahyperoval. Inordertodiscussournexttheoremsweneedanotherdenition.A conic isa setofpointssatisfyinganirreduciblehomogeneousquadraticequation.Itiseasily shownthatconicsareovals,thatis,theyareasetof q +1points,nothreeofwhich arecollinear. Theorem1.9 InPG 2 ;q ,conicsareovals. Proof: Wecanverifythatconicsareovalsbyobservingthateveryconicis projectivelyequivalenttothesetofpoints f t;t 2 ; 1: t 2 F q g[f ; 1 ; 0 g Ifwelet a;b;c 2 F q andconsiderthematrix 0 B B B B @ aa 2 1 bb 2 1 cc 2 1 1 C C C C A : ItisanonsingularVandermondematrixandsohasnonzerodeterminantprovided a b ,and c aredistinct.Hencewemustonlycheckthat ; 1 ; 0isnotpartofany collineartriple.Thematrix 7

PAGE 16

0 B B B B @ aa 2 1 bb 2 1 010 1 C C C C A hasdeterminant b )]TJ/F18 11.9552 Tf 12.13 0 Td [(a 6 =0provided a 6 = b .Thusaconicisasetof q +1points nothreeofwhicharecollinear. AfamoustheoremofB.SegregivestheconverseofTheorem1.9for q odd,that is,inPG ;q ,qodd,allovalsareconics. Theorem1.10Segre'sTheorem[47] InPG 2 ;q ,qodd,allovalsareconics. DuetoSegre'stheoremallovalsinPG ;q q odd,areclassied.Thus,we restrictourattentiontothecasewhere q iseven,thatis, q =2 h Wemayassumethatahyperovalcontainsthe fundamentalquadrangle ; 0 ; 0, ; 1 ; 0, ; 0 ; 1, ; 1 ; 1,since,byTheorem1.5,anyhyperovalisprojectivelyequivalenttoonecontainingthesefourpoints.In[24]itisshownthatany hyperovalcontainingthefundamentalquadranglecanberepresentedbyapermutationpolynomial. Theorem1.11 Anyhyperoval H inPG 2 ;q with q =2 h h> 1 ,containingthe fundamentalquadranglecanberepresentedas D f = f t;f t ; 1: t 2 GF q g[f ; 0 ; 0 ; ; 1 ; 0 g where f isapermutationpolynomialofdegreeatmost q )]TJ/F15 11.9552 Tf 13.077 0 Td [(2 with f =0 and f =1 If D f ,asdescribedabove,givesahyperovalwesaythat f isan o-polynomial Theuseofo-polynomialsgivesacompactandusableformforhyperovals,sothey havebeenthetraditionalwayofdescribinghyperovals.ArepresentativelistofopolynomialsforknownfamiliesofhyperovalsisgiveninTable1.1. 8

PAGE 17

1.5AHistoryofHyperovals Signcantstudyofhyperovalsdatesbacktothelate1950'stoapaperbyLunelli andSce[30]inwhichtheyuseacomputertosearchforcompletearcsinPG,16as suggestedbyB.Segre.Theirsearchyieldedonehyperoval,uptoprojectiveequivalence,thatwasnotaconic.ThishyperovalisnowknownastheLunelli-Scehyperoval andcanbedescribedbytheo-polynomial f t = t 12 + t 10 + 11 t 8 + t 6 + 2 t 4 + 9 t 2 ; where isaprimitiveelementofGFsatisfying 4 = +1. Table1.1:o-polynomialsforknownhyperovals Name o-polynomial FieldRestriction Hyperconic[24] f t = t 2 None Translation[46] f t = t 2 i i;h =1 None Segre[2] f t = t 6 hodd Glynn1[19] f t = t 3 +4 hodd Glynn2[19] f t = t + hodd Payne[35] f t = t 1 = 6 + t 1 = 2 + t 5 = 6 hodd Cherowitzo[10] f t = t + t +2 + t 3 +4 hodd Subiaco[15] SeeBelow None Adelaide[14] SeeBelow heven O'Keefe-Penttila[31] SeeBelow PG,32 4 2 2mod2 h )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 Subiaco Ano-polynomialforsomeoftheSubiacohyperovalsis f t = d 2 t 4 + d 2 + d + d 2 t 3 + d 2 + d + d 2 t 2 + d 2 t t 4 + d 2 t 2 +1 + t 1 2 wheretr/d=1.Thereisonehyperoval,uptoprojectiveequivalence,inthe Subiacofamilyif h 6 2mod4andtwohyperovalsif h 2mod4.Theabove 9

PAGE 18

polynomialgivesoneofthehyperovalswhen h 2mod4andtheothercanbe representedwitho-polynomial f t = d 2 t 4 + d 5 t 3 + d 2 t 2 + d 3 t t 2 + dt +1 2 + t d 1 2 ; where isanelementofmultiplicativeorder q +1inGF q 2 and d = + q .Wealso notethat3dierentautomorphismgroupsappearamongtheSubiacohyperovals. Adelaide Ano-polynomialfortheAdelaidehyperovalis f t = T b m T b t +1+ T bt + b q m T b t + T b t 1 = 2 +1 1 )]TJ/F19 7.9701 Tf 6.587 0 Td [(m + t 1 = 2 ; where T x = x + x q b 2 GF q 2 b 6 =1, b q +1 =1and m = q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 3 O'Keefe-Penttila Ano-polynomialfortheO'Keefe-Penttilahyperovalis f t = t 4 + t 16 + t 28 + 11 t 6 + t 10 + t 14 + t 18 + t 22 + t 26 + 20 t 8 + t 20 + 6 t 12 + t 24 ; where isaprimitiveelementofGFsatisfying 5 = 2 +1. TheLunelli-ScehyperovaldoesnotappearinTable1.1asitwasshowntobein theSubiacofamilyin[15]andintheAdelaidefamilyin[14].Formoreinformation ontheLunelli-Scehyperovalsee[7]. In1962,shortlyaftertheworkbyLunelliandSce,B.Segregavethetranslation andSegrehyperovalsin[46].Thesehyperovalsremainedtheonlyknownhyperovals forover20yearsuntilGlynngavetwonewfamiliesin[19].TheGlynnhyperovals wereyetmoreexamplesofwhatarecalled monomialhyperovals ,thatishyperovals thatcanberepresentedbymonomialo-polynomials.Theseremaintheonlyknown examplesofmonomialhyperovals. The1980'ssawasurgeinnewfamiliesofhyperovalswithPaynegivinganewfamilyin[35]andCherowitzoprovidingexamplesofanewfamilyin[11].TheCherowitzo hyperovalswereprovedtobeafamilyin1998[10].Thetimebetweenthediscoveryof therstexamplesoftheCherowitzohyperovalsandtheproofoftheirinclusioninan innitefamilywasoveradecadeandnewtechniqueshadtobedevelopedtoprovethe 10

PAGE 19

existenceofthefamily.Thespecictechniquewastheuseofanalgebraicstructure calleda q -clanwhichhassincebeenusedofteninthestudyofhyperovals.Wewill notdiscuss q -clanshere,butwereferthereaderto[8]forinformationon q -clans.The useofinnovativetechniquesisnotuncommonwhenstudyinghyperovalswhichshows theneedformanytechniques. Theearly1990'ssawyetanothersurgeinthediscoveryofhyperovals.New examplesofhyperovalswerefoundbyO'KeefeandPenttilain1992[31],aswellas PenttilaandPinneriin1994[40].ThehyperovalfoundbyO'KeefeandPenttila, knownastheO'Keefe-Penttilahyperoval,livesinPG,32andistheonlyknown sporadichyperoval,thatis,ahyperovalnotknowntobeamemberofaninnite family.TheexamplesfoundbyPenttilaandPinneriinPG,64weretherstdistinct examplesofSubiacohyperovals.In1995PenntilaandRoyle[42]foundmoreexample ofSubiacohyperovalsinPG,128andPG,256aswellastherstexamplesof theAdelaidehyperovalinPG,64andPG,256.TheSubiacohyperovalswere provedtobeaninnitefamilyin1996byCherowitzo,Penttila,Pinneri,andRoyle [15].However,theproofthattheAdelaidehyperovalslivedinaninnitefamilytook 8yearsfromtheirinitialdiscovery,nallybeingshownin2003[14].Since2003no newhyperovalshavebeendiscovered.Themostnotablepaperonhyperovalsforus since2003camefromFisherandSchmidtin2006.Theypresentedapaper[17]that uniedthePayneandAdelaidefamiliesandprovidesthebasisforthisthesis. However,therehasbeensomeworkdoneonthestudyofmonomialhyperovals. Wesayamonomialhyperoval H isa k-bitmonomialhyperoval ifano-polynomial for H is f t = t n andthereare k 1'sinthebinaryrepresentationfor n .The1-bit monomialhyperovalsarepreciselythetranslationhyperovals.The2-bitmonomial hyperovalswereclassiedin1998[16],andthe3-bitmonomialhyperovalswereclassiedin2010[51].ThefollowingtheoremwasalsogivenbyHernandoandMcGuire in2012. 11

PAGE 20

Theorem1.12[23] Foranyxedevenpositiveinteger k ,if k 6 =6 and k 6 =2 i then theset D x k isahyperovalinPG 2 ;q foratmostanitenumberofvaluesof q Thecollectionoftheseresultssuggeststhattherearenomoremonomialhyperovals.Combiningthisinformationwiththeo-polynomialsofthemostrecently discoveredhyperovalsmakesusexpectthatnewhyperovalswillhaveincreasingly complicatedo-polynomials,providingevenmoremotivationforthisthesis. Theautomorphismgroupsofhyperovalshaveplayedanimportantroleintheir study.Historicallyhyperovalshavebeenidentiedbytheirgroups.Whenanew hyperovalwasfound,itwasshowntobedistinctfrompreviouslyknownfamiliesvia itsautomorphismgroup,anditsexistenceindierentplanes.Table1.2showsthe sizesoftheautomorphismgroupsforallknownfamiliesofhyperovals. HyperovalsarecurrentlyclassiedinPG ; 2 h for1 h 5,andhyperovals withnontrivialautomorphismgroupareclassiedinPG ; 64.Itiswellknownthat allhyperovalsinPG ; 2 h for1 h 3arehyperconics.See[24]foraproofof thisclassication.HyperovalsinPG,16wereoriginallyclassiedbyHallin1975 [22].AllhyperovalsinPG,16areprojectivelyequivalenttothehyperoconic,or theLunelli-Scehyperovaldescribedabove.Inordertoclassifyhyperovalsinthis planeHallneededthehelpofacomputer,howeverin1991O'KeefeandPenttila[32] classiedthehyperovalsinPG,16withouttheaidofacomputer. In1994thehyperovalsinPG,32wereclassiedbyPenttilaandRoylebyexhaustivecomputersearch[41].EveryhyperovalinPG,32isprojectivelyequivalent toeitherthehyperconic,translation,Segre,Payne,Cherowitzo,orO'Keefe-Penttila hyperoval.PenttilaandRoylearealsoresponsibleforthepartialclassicationof hyperovalsinPG,64.TheyshowedthatifanewhyperovalexistsinPG,64then itmusthaveatrivialautomorphismgroupin[42].Theyuseatechniqueknownas primeatattime"thatwediscussinChapter3.Itisgenerallybelievedthatthereare nootherhyperovalsinPG,64,asahyperovalwithatrivialautomorphismgroup 12

PAGE 21

wouldhavemanyequivalentcopiesandshouldappearinarandomsearch. Table1.2:Thegroupsofknownhyperovals Hyperoval H j Aut H j FieldRestriction Hyperconic[24] q +2 q +1 q q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h q =2 ; 4 Hyperconic[24] q +1 q q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h q 8 Translation[24] q q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h Segre[33] 3 q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h q =32 Segre[33] q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h q 128 Glynn1[33] q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h Glynn2[33] 3 q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h q =128 Glynn2[33] q )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 h q> 128 Payne[50] 2 h Cherowitzo[34] h Subiaco[34] 2 h h 6 2mod4 Subiaco[39] 10 h h 2mod4 Subiaco[39] 5 h 2 h 2mod4 Adelaide[38] 2 h q 64 Lunelli-Sce[37] q +2 h q =16 O'Keefe-Penttila[31] 3 q =32 13

PAGE 22

2.The -polynomialRepresentation InthischapterwedescribeanextensionoftheworkofFisherandSchmidtthatwe calla -polynomial.FirstwedescribethepolarmodelofAG ;q ,givingadescription oflinesandincidenceintheplane,followedbyacollectionofcollineationsinthepolar model.Next,weintroduce -polynomialsanddiscusshowtousethemtorepresent hyperovals.Furthermore,wewilldiscussthestructuralpropertiesof -polynomials, theirrelationshiptoo-polynomials,andgivesomenice -polynomialrepresentations ofseveralfamiliesofhyperovals. 2.1ADescriptionofthePolarModel Fortheremainderofthisthesiswewillbeassumingthat q =2 h ,with h aninteger 1.WeshallrepresentthepointsofAG ;q byelementsofGF q 2 .Todothiswe selectanirreduciblepolynomialoftheform x 2 + x + ,forsome 2 GF q ,andlet i bearootofthispolynomialinGF q 2 .Irreduciblepolynomialsofthisformexist, infact, canbechosentobeanyelementofabsolutetrace1[24].Wenotethat i q = i +1sincetheotherrootof x 2 + x + is i +1.Theimageof i undertheaction oftheeldautomorphismsisgiveninLemma2.8.Havingchosen i ,weassociatethe point x;y ofAG ;q withtheelement x + iy inGF q 2 .Inanalogywithcomplex numberrepresentations,wereferto y in z = x + iy astheimaginarypartof z ,and x astherealpart.Observethatboth x and y areelementsofGF q .Thefollowing well-knownlemmaisofconsiderableuse. Lemma2.1 Theelements ;; 2 GF q 2 ,whenthoughtofaspointsofAG 2 ;q arecollinearifandonlyif q + q + q 2 GF q Proof: Let = A + iB = C + iD ,and = E + iF .Substitutingthesevalues showsthattheimaginarypartof q + q + q is BC + AD + DE + CF + FA + EB However,thesepointsarecollinearifandonlyif AB 1 CD 1 EF 1 =0 14

PAGE 23

Thisdeterminantisprecisely BC + AD + DE + CF + FA + EB ,forcing q + q + q 2 GF q Thislemmagivesusapolynomialrepresentationforthelineconnectinganytwo points. Corollary2.2 The q pointsonthelinejoining 2 GF q 2 aresolutionstothe equation + x q + + q x + q + q =0 : .1 Adescriptionoflinesinthisrepresentationisknownandcanbeseenin[1]and [26].TheyprovideadescriptionofhyperplanesinAG n;q ,andso,adescriptionof linesinAG ;q .Forcompleteness,wegiveourownproofofsuchadescriptionof lines.Wewilllet N denotethegroupof q +1 st rootsofunityinGF q 2 ,theelements ofnorm1. Lemma2.3 AnylineinAG 2 ;q ,whosepointsarethoughtofaselementsinGF q 2 consistsoftheset, L ; = f x 2 GF q 2 j T x = g ; where T x = x q + x forsome 2N andaxed 2 GF q Proof: Let and beanytwodistinctelementsofGF q 2 .ByCorollary2.2the pointsontheline ` joining and aresolutionsto.1.Rearrangingtheterms yields T + q x = T q : Thus,thesolutionsto.1satisfy T + q x = T q .Wewillnowshowthatgiven theline ` joining and wecanalwaysnd ; 2 ` suchthat + q 2N .Observe that s +1+ s isasolutionto.1forevery s 2 GF q .Asthisrepresents q solutions,everyrootwillhavethisform.Let = +1+ ; 15

PAGE 24

= s +1+ s bepointson ` where s; 2 GF q and s + = q 1 + q +1 .Notice + q +1 isin GF q sincethe q +1 st powerofanyelementofGF q 2 isinGF q ,soconsequently q 1 + q +1 2 GF q .Then, + q +1 = + s + q +1 = + q +1 s + 2 =1 : .2 Thus, ; 2 ` and + 2N whichimplies + q 2N ,since N isamultiplicative subgroupofthenonzeroelementsofGF q 2 Wewillnowprovetheconverse.Assumethat u;v;w 2 GF q 2 and T u = T v = T w = z ,forsome 2 GF q 2 .Observethat u q = )]TJ/F19 7.9701 Tf 6.587 0 Td [(q z + 1 )]TJ/F19 7.9701 Tf 6.586 0 Td [(q u ; v q = )]TJ/F19 7.9701 Tf 6.586 0 Td [(q z + 1 )]TJ/F19 7.9701 Tf 6.587 0 Td [(q v ; w q = )]TJ/F19 7.9701 Tf 6.587 0 Td [(q z + 1 )]TJ/F19 7.9701 Tf 6.586 0 Td [(q w andfurther u + v q = )]TJ/F19 7.9701 Tf 6.586 0 Td [(q z + 1 )]TJ/F19 7.9701 Tf 6.586 0 Td [(q u + )]TJ/F19 7.9701 Tf 6.587 0 Td [(q z + 1 )]TJ/F19 7.9701 Tf 6.587 0 Td [(q v = 1 )]TJ/F19 7.9701 Tf 6.586 0 Td [(q u + v : Withtheseobservationsitisanelementarycalculationtoshowthat u + v w q + u + v q w + u q v + v q u =0 : Hence u;v;w arecollinearbyCorollary2.2.Observethatwehaveshownthisresult forgeneral ,soitholdsfor 2N Corollary2.4 Theline L ; connectingtwopoints ; 2 GF q 2 isdetermined uniquelyby and ,where = p + q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 2N and = T = T Proof: Let ` bethelineconnectingpoints and .FromLemma2.3thereexists 2N forwhich T = T = : Thisimpliesthat + q = + andso = p + q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 : Thismustbetheuniquevalueof sinceforanypoints ; 2 ` suchthat + 2N ,and = +1+ ; = s +1+ s asinLemma2.3,we 16

PAGE 25

have + q +1 = + s + q +1 =1 : Thus s + = s 1 + q +1 : Hence, + = + s + = s 1 + q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 ; andso + q = p + q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 asdesired. FollowingFisherandSchmidt[17],wewanttodecomposetheelementsofGF q 2 intowhatwecalltheir polarcoordinates .Observethat N isacyclicgroupsowemay assumethat N isgeneratedby ,andlet generatethecyclicmultiplicativegroup GF q insideGF q 2 Lemma2.5 Everynon-zeroelement ofGF q 2 canbedecomposeduniquelyasthe productofa q +1 st rootofunitytimesanon-zeroelementofGF q ,thatis = k j for 0 k q and 0 j q )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 Proof: Let generatethecyclicgroup N andlet generatethecyclicgroup GF q .Thereare q 2 )]TJ/F15 11.9552 Tf 11.48 0 Td [(1productsoftheform k j for0 k q and0 j q )]TJ/F15 11.9552 Tf 11.48 0 Td [(2, eachofwhichisanelementofGF q 2 .Wewillshowthateachoftheseproducts isdistinct,provingeveryelementofGF q 2 hasauniquedecomposition.Assume that r s = t u sothat r s q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 = t u q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 whichimplies t + r 2 =0since q iseven.Hence r = t andsonecessarily s = u .Thereforeeachproductisunique,and everynon-zeroelement ofGF q 2 canbedecomposeduniquelyastheproductofa q +1 st rootofunityandanon-zeroelementofGF q Inanalogywithpolarcoordinatesof R 2 ,weshallthinkof asrepresentingan angle",and representingaradius",withallpointscenteredaround0.This coordinatizationisrepresentedinFigure2.1. InthesequelweshallrefertoelementsofGF q 2 aspointsinAG ;q without explicitlymentioningtheequivalence.UsingLemma2.3weeasilyseethatthelines 17

PAGE 26

0 1 2 1 2 k q Figure2.1:ThePolarRepresentationofAG, q through0consistofpointsinGF q 2 withthesame q +1 st rootofunityintheirpolar decomposition.Wewillrefertosetsofpointsoftheform f j :0 j q g ,forxed 2 GF q ,asa tier .TiersarerepresentedasdashedlinesinFigure2.1,andwe willseelaterthateachtierisaconic. 2.2CollineationsinthePolarModel Inthissectionwewillstudysomecollineationsinthepolarmodel.Thefundamentaltheoremofprojectivegeometrygivesacompletedescriptionofcollineations inthetraditionalCartesianmodeloftheplane,andourgoalistodescribesome collineationsinthepolarmodelthatwillhelpwithlaterresults. Lemma2.6 Let 2 GF q 2 0 6 = 2 GF q 2 andconsiderthepointsofAG 2 ;q aselementsofGF q 2 .Theaction x x + denesacollineationinAG 2 ;q Proof: Let x;y;z bethreecollinearpointsinAG ;q representedaselementsof GF q 2 .ByLemma2.1wehave xy q + yz q + zx q 2 GF q .Considerthepoints x + y + z + forsome 2 GF q 2 and 2 GF q 2 andcalculate x + y + q + y + z + q + z + x + q 18

PAGE 27

= q +1 xy q + yz q + zx q + T x + T y + T z + q +1 : EachofthequantitiesinthesumisanelementofGF q ,sothesumisinGF q Hence,thepoints x + y + z + arecollinearbyLemma2.1.Therefore,the action x x + denesacollineationinAG ;q whenpointsarethoughtofas elementsofGF q 2 WealsoknowthattheeldautomorphismsofGF q 2 inducecollineationsin thismodelofAG ;q .However,wewishtonotethatthesearedierentfrom theautomorphiccollineationsofAG ;q intheCartesianmodel,whicharethe collineationsoftheform x;y x ;y forsome 2 AUTGF q Lemma2.7 Let 2 AutGF q 2 andconsiderthepointsofAG 2 ;q aselements ofGF q 2 .Theaction x x denesacollineationinAG 2 ;q Proof: Let x;y;z bethreecollinearpointsinAG ;q representedaselementsof GF q 2 .ByLemma2.1wehave xy q + yz q + zx q 2 GF q .Considerthepoints x ;y ;z 2 GF q 2 .Since 2 AutGF q 2 wehave x y q + y z q + z x q = xy q + yz q + zx q 2 GF q : Hence,thepoints x ;y ;z arecollinearbyLemma2.1.Thereforetheaction x x denesacollineationinAG ;q wherepointsareelementsofGF q 2 ThetraditionalformofthecollineationsdenedbytheautomorphismsofGF q 2 iseasilycomputedandwillgiveinsightintotheconnectionbetweenthepolarmodel andpreviousmethodsusedtostudyhyperovals.Inordertodeterminetheirformwe needapreliminaryresult. Lemma2.8 If i isarootoftheirreduciblepolynomial x 2 + x + where 2 GF q then i 2 k = i + k )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 X j =0 2 j : 19

PAGE 28

Proof: Observethat i 2 = i + .Weproceedbyinduction.Assumethat i 2 k = i + k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 X j =0 2 j then i 2 k +1 = i 2 k 2 = i + k )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 X j =0 2 j 2 = i + k X j =0 2 j : Therefore,theresultholdsbyinduction. Lemma2.9 Thecollineationdenedbytheautomorphism : x x 2 k ofGF q 2 is equivalenttothecollineationdenedby x;y;z x ;y ;z 0 B B B B @ 100 s 10 001 1 C C C C A = x + sy ;y ;z where s = P k )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 j =0 2 j whenpointsarethoughtofascoordinatetriples x;y;z Proof: Themap sends x + iy x + iy = x + P k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 j =0 2 j y + iy : Thepre-image ofthispointunderthemap x;y; 1 x + iy is x + P k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 j =0 2 j y ;y ; 1 ; provingthe result. Therearealsosomecollineationsthatpreservethepolarmodelthatweregiven byO'KeefeandPenttilain[33],seeLemma3.2. Lemma2.10[33] Let J beacyclicsubgroupoforder q +1 ofPGL,q, q even. Supposethat J xesapointandxesalinenotonthepoint.Thentheorbitsof J onthepointsofPG 2 ;q arethexedpoint,thexedline,and q )]TJ/F15 11.9552 Tf 11.822 0 Td [(1 non-degenerate conics. O'KeefeandPenttilaalsogiveaspecicsubgroupthatxesthepoint ; 0 ; 1 andtheline z =0andhas q )]TJ/F15 11.9552 Tf 12.056 0 Td [(1non-degenerateconicsasorbits.Thatis,theygive agroupthatpreservesthepolarmodelasvisualizedinFigure2.1.Theirgroupisas follows,asquotedfrom[33]. 20

PAGE 29

Considerthefollowingpencilofconics: x 2 + ax + y 2 + z 2 =0 for ; 2 GF q ,notbothzero,andwhere x 2 + ax +1isirreducibleover GF q .Thedegenerateconicgiveby =0isthepoint ; 0 ; 1and thedegenerateconicgivenby =0istheline z =0.Theother q )]TJ/F15 11.9552 Tf 12.134 0 Td [(1 conicsofthepencilarenon-degenerate.The q +1conicsofthepencilare pairwisedisjointandcoverPG2 ;q Let F bethefollowingsetofhomographies: F = 8 > > > > < > > > > : 0 B B B B @ fg 0 gf + ag 0 001 1 C C C C A : f;g 2 GF q ; notbothzero 9 > > > > = > > > > ; : Aconicofthepencilisxedbyanelementof F providedthematrixhas determinant f 2 + afg + g 2 =1. O'KeefeandPenttilanotethat F isacyclicsubgroupoforder q 2 )]TJ/F15 11.9552 Tf 11.189 0 Td [(1ofGL ;q butwhenrestrictedtothosematriceswithdeterminant1,itgivesrisetoacyclic subgroupoforder q +1ofPGL ;q .HencethisgrouprealizesLemma2.10.The orbitsofthisgrouparetheorigin, ` 1 ,andthe q )]TJ/F15 11.9552 Tf 11.049 0 Td [(1tiersfromthepolarmodel.Note thatthefullgroupstabilizesthemodelbutinterchangesthetiers. 2.3Using -polynomialstoRepresentHyperovals In2006FisherandSchmidtproposedamethodofrepresentinghyperovalsusing niteFourierseries.Tousetheirmethodonemusthaveahyperovalintheane planecontaining ; 0 ; 1,andrepresentpointsaselementsofGF q 2 asdescribed above.SpecicallytheyusethepolardecompositionofpointsdescribedinLemma 2.5.OncethehyperovalpointsarerepresentedaselementsofGF q 2 theyassignan orderingtothenonzeropointsandrepresentthemusingorderedlinearcombinations 21

PAGE 30

ofelementsintheset N = f 1 ;;:::; q g .Suchanorderedlinearcombination,asseen in.3,iscalleda niteFourierseries .FischerandSchmidtgavetheformula p j = q X k =0 k jk .3 where p j denotesthe j th hyperovalpointofaxedordering.Itisimportanttonote thattheorderingofthepointsplaysacrucialroleinthisrepresentationofhyperovals. FisherandSchmidtwantedtoanalyzethecoecients k andgivenecessaryand sucientconditionsforagivensetofcoecientstoproduceahyperoval. In[17]theysearchforhyperovalsinsmallplaneswithaFourierseriesrepresentationwithatmostthreenonzerocoecients.Theyfoundonethatwasnotaconic, giveninthenexttheorem. Theorem2.11[17] Thepointset O 0 = f j + 3 j + )]TJ/F16 7.9701 Tf 6.586 0 Td [(3 j :0 j 2 h g isanoval ofAG 2 ; 2 h whosenucleusistheorigin. Theywerealsoabletoidentifythishyperovalandindoingsotheypairedtwo familiesofhyperovalsthatwerepreviouslythoughttobeunrelated. Theorem2.12[17] InAG 2 ; 2 h ,thehyperoval O 0 [f 0 g isthePaynehyperoval when h isoddandtheAdelaidehyperovalwhen h iseven. TheirworkgivesanelegantrepresentationfortheAdelaidehyperoval.This representationismuchmorecompactthanthantheo-polynomialrepresentation. Additionally,thisformallowedustoseethatthetwofamiliescouldbegivenwiththe sameconstruction.Ourhopeistostudyhyperovalsinthisnewperspectivetoshed somelightontheirstructure.However,choosingtherightorderingforthepointsof thehyperovalsisadauntingtask. Inthenalsectionof[17]theypointoutthatonecouldsearchforhyperovals whoseniteFourierseriesrepresentationhas4or5nonzerocoecients,andsoon, butthattaskwouldbearduousandtemporary.Insteadtheysuggestacanonical 22

PAGE 31

orderingofthepointsonthehyperoval:dene p j tobethepointoftheovalonthe linejoiningtheoriginto j .Withthissuggestiontheygiveoneresultandleave furtherexplorationuptothemathematicalcommunity. Theorem2.13[17] Let q beapowerof2andlet beaprimitive q +1 st root ofunityinGF q 2 .Aset f p 0 ;p 1 ;:::;p q g of q +1 pointsinGF q 2 islabeledsothat p j isonthelinejoiningtheoriginto j ifandonlyiftheFouriercoecientsofthe pointsetsatisfy k = q 2 )]TJ/F19 7.9701 Tf 6.587 0 Td [(k wheresubscriptsaretakenmodulo q +1 Theorem2.13showsthatspecicorderingscangiveverynicerepresentations ofhyperovals.Infact,aswewillseelater,givenaspecichyperovalonecanuse certainorderingstoproducenicerrepresentations.Herewefollowthesuggestionof FisherandSchmidtandusetheircanonicalorderingtostudynewrepresentationsof hyperovals. WeassumethatwearestudyinghyperovalsintheAG ;q wherethepoints arerepresentedaselementsofGF q 2 .Additionally,weassumethatourhyperovals containthepoint0 2 GF q 2 .Ahyperovalthatincludeszeromusthaveexactlyone additionalpointfromeachofthe q +1linesthroughzero.ByLemma2.3eachofthese linesisassociatedwitha q +1 st rootofunity,thatis,eachpointonthatlinemust havethesamerootofunityititspolardecomposition.Since T =0forall 2N alinethroughzeroconsistsofthe q )]TJ/F15 11.9552 Tf 11.979 0 Td [(1otherrootsof T x .Theserootsarepoints oftheform q k for0 k q )]TJ/F15 11.9552 Tf 11.614 0 Td [(2.Thusthepointsonalinethroughzeroconsistof pointswiththesame q +1 st rootofunityititspolardecomposition.Hence,wecan deneafunction : N! GF q whichdescribesanyhyperovalcontainingtheorigin, byoutputting,foreach q +1 st rootofunity,theGF q multiplierofthehyperoval pointonthelinethroughtheorigindenedbythat q +1 st rootofunity.Hencethe pointsofthehyperoval,aselementsofGF q 2 ,willbe f x x : x 2Ng[f 0 g 23

PAGE 32

Whatcanbesaidabout ?Wereturntoequation.3ofFisherandSchmidt, p j = q X k =0 k jk : Usingthesuggestedcanonicalordering,let p j bethehyperovalpointontheline adjoining j totheorigin.Write p j = j t j andso p j = j t j = q X k =0 k jk ; thus t j = q X k =0 k j k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 : Hence,if x = j x = q X k =0 k x k )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 : Weobservethatthecoecientsofthispolynomialfunctionareexactlythesame asthoseintheFisherSchmidtrepresentation,wehavesimplychangedtheperspective.Wegivethefollowingformaldenition. Denition2.14 Afunction : N! GF q iscalleda -polynomialif f x x : x 2Ng[f 0 g isahyperoval. Ourgoalistostudythestructureof -polynomialsandgive -polynomialrepresentationsfortheknownfamiliesofhyperovals. 2.4StructuralPropertiesof -polynomials Inthissectionwewilldiscussthestructureof -polynomials.FisherandSchmidt wereconcernedwithhyperovalsthathadrepresentationswithmanyzerocoecients. Wetakeadierentapproachandstudywhencoecientscomefromcertainsubelds, orhavespecictypesofcoecientsbeingzero. 24

PAGE 33

2.4.1BasicStructuralProperties In[17]FisherandSchmidtalsogaveaformulaforthecoecientsintermsofthe points.UsingMobiusinversionon.3weobtainthefollowingequation. k = q X j =0 p j )]TJ/F19 7.9701 Tf 6.587 0 Td [(jk : .4 Inparticularnoticethat 0 = q X j =0 p j .5 and 1 = q X j =0 t j .6 where isageneratorofthecyclicgroupGF q .Basedontheseequationswecan showthat 0 =0and 1 2 GF q .Thefactthat 1 2 GF q isamereobservation, sinceby.6itisrepresentedasthesumofelementsinGF q .Showingthat 0 =0 requiresaslightlydeeperexplanation. Lemma2.15 If x = P q k =0 k x k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 isa -polynomialthen 0 =0 Proof: Let x = P q k =0 k x k )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 bea -polynomialdescribingahyperoval H in AG ;q embeddedinPG ;q .Considerthelinesthroughthepoints ; 0 ; 0and ; 1 ; 0oftheinniteline z =0.Thelinesthrougheachofthesepointspartitionthe hyperovalintopairsofpointswithpairedcoordinates,sinceneitherpointisonthe hyperoval.Inparticular,thepointsonlinesthrough ; 0 ; 0havethesamesecond coordinatewhenviewedascoordinatetriplesinPG ;q ,andthepointsonthelines through ; 1 ; 0havethesamerstcoordinate.Thismeansthatwhenweviewthe pointsofthehyperovalas p j = x j + iy j the x 0 j s mustbepaired,andthe y 0 j s mustbe paired.Observethatthepoint p q +1 =0correspondingto ; 0isnotincludedinour 25

PAGE 34

sum,sobyincluding p q +1 andusing.5weobtain 0 = q +1 X j =0 p j = q +1 X j =0 x j + iy j = q +1 X j =0 x j + i q +1 X j =0 y j =0+ i 0=0 : Hence,if x isa -polynomial,then 0 =0. ByTheorem2.13weknowthatthecoecientsobeytherelationship k = q 2 )]TJ/F19 7.9701 Tf 6.587 0 Td [(k ; wherethesubscriptsaretakenmod q +1,hence 2 =0followsfromLemma2.15. Thereforewecanwrite x = 1 + q X k =3 k x k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 : Observethatwheneveran x k termhasanonzerocoecient,theterm x )]TJ/F19 7.9701 Tf 6.587 0 Td [(k willalso haveanonzerocoecient,sinceexponentsaretakenmodulo q +1.Lemma2.6shows thatmultiplyingallthepointsofahyperovalbyanonzeroelementproducesan equivalenthyperoval.Thus,wecanalwaysassumethat 1 2 GF,since )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 1 H isa hyperovalequivalenttoagivenhyperoval H Theseobservations,alongwiththefactthatourdomainis N ,showsthatwecan represent -polynomialsinthefollowingway, x = 1 + g x + g x q where g x = q 2 X k =3 k x k )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 : .7 Thisformcanbereducedto x = T g x + 1 ,whichconrmsthat x 2 GF q andfurthergivesthefollowingnecessaryconditionsince x 2 GF q Observation2.16 If x = 1 + g x + g x q isa -polynomialthen T g x 6 = 1 forall x 2N 2.4.2HyperovalsStabilizedbyFieldAutomorphisms Aspreviouslymentioned,insteadoflookingfor -polynomialswithmanynonzero coecients,wewouldliketostudyhyperovalswhocoecientshaveotherinteresting properties.Thissectionisdevotedtohyperovalswhose -polynomialcoecients 26

PAGE 35

comefromsubeldsofGF q 2 .Asweshallsee,a -polynomialhavingcoecientsina specicsubeldisdirectlyrelatedtothehyperovalbeingstabilizedbyautomorphisms ofthecorrespondingGaloisgroup.Recallthat q =2 h Theorem2.17 Let k j 2 h sothatGF 2 k isasubeldofGF q 2 ,andlet bea -polynomialdescribingahyperoval H .Thepolynomial hascoecientsinGF 2 k ifandonlyif H isstabilizedbythemap : x x 2 k Proof: Assumethat hascoecientsinGF k with k j 2 h ,let : x x 2 k ,and 2H forsome 2N .Inordertoshowthat H isstabilizedby weonlyneed toshowthat = .Let x = 1 + q X j =3 j x j )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 sothat = 1 + q X j =3 j j )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 = 1 + q X j =3 j j )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 = since j 2 GF k for3 j q .Hence H isstabilizedby Fortheconverse,assumethat H isstabilizedby ,sothatif 2H then = 2H ,andso, = .Asabovelet x = 1 + q X j =3 j x j )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 sothat 1 + q X j =3 j j )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 = 1 + q X j =0 j j )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 ; andso q X j =3 j + j j )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 =0 : .8 Theimpliedpolynomialin.8hasdegree q )]TJ/F15 11.9552 Tf 12.441 0 Td [(1andthe q +1elementsof N are roots,sothispolynomialmustbethezeropolynomial.Hence j = j for3 j q andso, hascoecientsinGF k 27

PAGE 36

Thistheoremallowsustoobtainsomeinformationabouttheautomorphism groupofhyperovalsbasedonthestructureoftheir -polynomials.Additionally,we cansaysomethingaboutthesizeoftheautomorphismgroup.Thefollowingcorollary isanimmediateconsequenceofLagrange'sTheorem. Corollary2.18 Ifahyperoval H isrepresentedbya -polynomialwithcoecients inGF 2 k with k j 2 h then 2 h k jj Aut H j Proof: ByTheorem2.17weknowthat H isstabilizedbythemap : x x 2 k whichhasorder 2 h k ,hencebyLagrange'sTheorem 2 h k jj Aut H j Further,wecanacquireinformationaboutspecicpointsthatmustbeona hyperovalprovidedthecoecientsofits -polynomialcomefromasmallenough subeld. Theorem2.19 Assume H isahyperovalinAG 2 ;q with q =2 h h odd.If H is representedbya -polynomial withcoecientsinGFthen GF H Proof: Assumethat x hascoecientsinGFandrecallthat x = 1 + g x + g x q with 1 2 GF.LetGFbegeneratedby andnoticethat1 ;!;! 2 2N since q +1 0mod3.Let s beanarbitraryelementofGF .Since g hascoecients inGF,weknow g s 2 GF andso T g s 2 GF,with T g s 6 = 1 .Hence s =1and s s = s .ThusGF f x x : x 2 N g implyingGF H Wehaveseenthatahyperoval H beingstabilizedbyeldautomorphismsgivesa greatdealofstructureonthecoecientsofthe -polynomialsof H .Thenextsection showshowbeingstabilizedbyamultiplicativemapeectsthe -polynomial. 2.4.3HyperovalsStabilizedbyMultiplicativeMaps Themapswewillconsiderinthissectionareoftheform x x where is thegeneratorofthe d th rootsofunityforsomeprime d j q +1.Inordertoprove 28

PAGE 37

structuralresultsaboutthe -polynomialsrepresentingthesehyperovalswerstneed somelemmas. Lemma2.20 Thesumofthe d th rootsofunityiszero. Proof: Thecoecientofthe x d )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 terminthepolynomial x d )]TJ/F15 11.9552 Tf 12.179 0 Td [(1iszero.Sincethe rootsofthispolynomialarethe d th rootsofunityandthecoecienton x d )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 isthe negativesumoftheroots,thesumiszero. Lemma2.21 Let beageneratorofthemultiplicativegroupof d th rootsofunity.If t isanintegerwith d;t =1 thentheaction x x t permutesthe d th rootsofunity. Wearenowreadytoproveastructuralresultabouthyperovalsstabilizedbythese maps. Theorem2.22 Let d beaprimesuchthat d j q +1 ,andlet generatethe d th roots ofunity.Ifahyperoval H isstabilizedbytheaction x x thenthe -polynomial representing H hastheform x = X a di x di : Proof: Assumethatahyperoval H isstabilizedbytheaction x x .Let be apointon H forsome 2N .Since H isstabilizedby x x wemusthavethat isalsoon H ,andsince 2N wemusthave on H aswell.These pointsareonthesamelinethrough0,sotheymustcoincidegiving = Let x = X a i x i ;f x = X a di x di and g x = x + f x : 29

PAGE 38

Considerthefollowingsystemofequations f x + g x = x f 2 x + g 2 x = 2 x . f d )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 x + g d )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 x = d )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 x : Observethatthereare d )]TJ/F15 11.9552 Tf 10.375 0 Td [(1equationshere,and d )]TJ/F15 11.9552 Tf 10.374 0 Td [(1isevensince d isaprime, d 6 =2. Now,since f x = f x and x = x wehave f j x = f x and j x = x for1 j d )]TJ/F15 11.9552 Tf 11.955 0 Td [(1.Thus,byaddingthe d )]TJ/F15 11.9552 Tf 11.955 0 Td [(1equationstogetherweobtain d )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 X j =1 g j x =0 : ByLemma2.20andLemma2.21wehave P d )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 j =1 jt =1providedthat t 6 0mod d andso, d )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 X j =1 g j x = X t 6 0mod d d )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 X j =1 jt a t x t = g x =0forall x 2N : Observethat g isapolynomialofdegreeatmost q )]TJ/F15 11.9552 Tf 10.235 0 Td [(1since hasdegreeatmost q )]TJ/F15 11.9552 Tf 10.234 0 Td [(1. However,the q +1elementsof N arerootsof g ,so g mustbethezeropolynomial. Hence x = f x + g x = f x forall x 2N ; showingthat hastheproposedform. 2.5TheRelationshipto o -polynomials Wecannowgiveamethodforturningknown o -polynomialsinto -polynomials, andvice-versa.Wewishtonotethatthisgeneralconversionformulawillnotalways givethemostelegant -polynomials,andspecicconsiderationswillbegivenforcertainfamiliesinthefollowingsections.Webeginwithausefulformulaforconverting betweencartesianandpolarcoordinates. Lemma2.23 Thepoint inpolarcoordinatescorrespondstothepoint T i ;T ; 1 incartesiancoordinates. 30

PAGE 39

Proof: Let representapointinpolarcoordinates.Usingthefactthat i q = i +1, thefollowingcomputationshowsthattheimageof T i ;T ; 1underthemap x;y; 1 x + iy is T i + iT = i + i q + i + i q = i + i + + i + i = : Hencetheelement inGF q 2 correspondstothepoint T i ;T ; 1in AG, q Thislemmashowsthatifweconsiderthehyperoval H = f x x : x 2Ng[f 0 g inpolarcoordinates,thenthecartesiancoordinatesofthesepointsare f x T i x ; x T x ; 1: x 2Ng[f ; 0 ; 1 g : Bythefundamentaltheoremofprojectivegeometrywecanguaranteethatthe fourpoints0 ; 1 ; q i +1 i p ; q i i +1 p lieonthehyperoval.Thus =1, q i i +1 = p ,and q i +1 i = p ,forsome inGF q thatisspecictoeachhyperovaland willbedeterminedlater. Inordertodeterminetheo-polynomialformofthishyperovalwemapthesepoints ontothestandardframe.Applyingthecollineationdenedby x;y;z 0 B B B B @ 110 0 1 010 1 C C C C A = x;x + y + z;y yieldsthesetofpoints f x T i x ; x T i x + x T x +1 ; x T x : x 2Ng[f ; 1 ; 0 g : Since T =0, T i =1and =1wehavethatthesetofpointsis f x T i x ; x T i x + x T x +1 ; x T x : x 2N)-79(f 1 gg[f ; 1 ; 0 ; ; 0 ; 0 g : Now x T x 6 =0for x 2N)-222(f 1 g sowecannormalizeto f T i=x T x ; T i=x T x + + 1 x T x ; 1: x 2N)-223(f 1 gg[f ; 1 ; 0 ; ; 0 ; 0 g : 31

PAGE 40

Observethat T i=x T x = i + x 2 x +1 2 ,hencetheanepointsofourhyperovalare f i + x 2 x +1 2 ;i + + x 2 x +1 2 + 1 x T x ; 1: x 2N)-222(f 1 gg : .9 Wehavetoguaranteethat ; 0 ; 1 ; ; 1 ; 1areamongthesepoints. If i + x 2 x +1 2 =0then x = q i i +1 2N .Wealsowant i + + x 2 x +1 2 + 1 x T x =0, hencewewant, r i i +1 T r i i +1 = 1 ; andso, r i i +1 = p : If i + x 2 x +1 2 =1then x = q i +1 i 2N .Wealsowant i + + x 2 x +1 2 + 1 x T x =1, hencewewant, r i +1 i T r i +1 i = 1 ; whichrequires, r i +1 i = p : Weareassumingthat q i i +1 = p ,and q i +1 i = p sowehavesuccessfullymappedourhyperovalontothestandardframe.Ifwewantthesepointsto satisfyano-polynomialft,wemusthave i + + x 2 x +1 2 + 1 x T x = f i + x 2 x +1 2 ; so, 1 x T x = f i + x 2 x +1 2 + i + + x 2 x +1 2 : .10 Hence,providedtheRHSisnotzerothenwehave x = 1 f i + x 2 x +1 2 + i + + x 2 x +1 2 T x ;x 6 =1 : Since x 2N thecalculation i + x 2 x +1 2 q = i +1+ =x 2 =x +1 2 = i +1+ 1 x +1 2 = i + x 2 x +1 2 32

PAGE 41

showsthat i + x 2 x +1 2 2 GF q .Also,themap : N)-222(f 1 g! GF q denedby x i + x 2 x +1 2 isclearlyone-to-oneandsoGF q = f i + x 2 x +1 2 : x 2N)-145(f 1 gg : Letting t = i + x 2 x +1 2 yields x = 1 f t + t + T x : Thusifwechoose sothat y = x + isanexternallinetothehyperovalin cartesianform,thenourdenominatorwillnotbezeroon N)-222(f 1 g Thisgivesusthefollowingtheorem. Theorem2.24 Givenano-polynomial f withline y = x + externalto f t;f t ; 1: t 2 GF q g thepolynomial x = 1 f t + t + T x ;t = i + x 2 x +1 2 ; =1 isacorresponding -polynomial. 2.6The -polynomialsforKnownHyperovals WhileTheorem2.24givesageneralmethodfornding -polynomialsofknown familiesofhyperovals,itdoesnotalwaysproducethemostelegantrepresentations. Takingextrainformationintoaccountforspecichyperovalsallowsustoobtainbetter representations.Webeginbystudyingthehyperconictogetabetterunderstanding oftherepresentationandprovidesomeprooftechniques. 2.6.1Hyperconic Theorem2.25 InAG 2 ;q thepolynomial x =1 isa -polynomialthatproduces ahyperconic. Proof: Assumethat x =1andlet H = f x x : x 2Ng = N .Thefollowing computationshowsthataGF q 2 element x + iy 2N ifandonlyifitscorresponding 33

PAGE 42

cartesianpoint x;y; 1isasolutiontoanirreduciblehomogenousquadraticequation. x + iy q +1 =1 x + y + iy x + iy =1 x 2 + xy + ixy + ixy + iy 2 + i 2 y 2 =1 x 2 + xy + y 2 +1=0 Hence, x;y; 1isanorm1elementifandonlyifitisarootof x 2 + xy + y 2 + z 2 Thisshowsthatthepointsof N arethe q +1pointsonaconic.Sinceeachofthem liesonadistinctlinethrough0,wemusthavethat0isthenucleusoftheconic. Therefore, N[f 0 g isahyperconic,and x =1isa -polynomialthatproduces thishyperconic. This,ourrstexampleofa -polynomialforahyperoval,mayclearlybecalled elegant.Additionally,Theorem2.25showsthatthedomainofa -polynomialis thishyperconic.Sinceanyhyperovalhasa -polynomialrepresentationthisimplies thatanyhyperovalissimplyaperturbationofahyperconic,wherethe -polynomial describesthatperturbation. Observation2.26 Everyhyperovalisaperturbationofahyperconic,wheretheperturbationisdescribedbyits -polynomial. Wewillnowlookatanothernicerepresentationofthehyperconicinthe polynomialform.Thepolynomial x =1canbeviewedasthepolynomialfrom .3withallzerocoecients,exceptfortheconstantterm.Ifwetakethepolynomial whereallofthesecoecientsare1,wealsogeta -polynomialforthehyperconic. Theorem2.27 InAG 2 ;q thepolynomial x =1+ P q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 j =2 x j isa -polynomial thatdescribesahyperconic. Proof: Let x =1+ P q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 j =2 x j .Weclaimthat k = k + )]TJ/F19 7.9701 Tf 6.586 0 Td [(k for1 k q +1, where isageneratorof N .Assumethat k;q +1= d sothattheelementsofthe set f k i :1 i q +1 d g arepreciselythe q +1 d th rootsofunity.Additionally,the 34

PAGE 43

multiset f k i :1 i q +1 g containsexactly d copiesofthe q +1 d th rootsofunity. HencebyLemma2.20wehave q +1 X i =1 k i =0 ; so k + q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 X i =2 k i + k q + k q +1 =0 ; thus 1+ q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 X i =2 k i = k + )]TJ/F19 7.9701 Tf 6.587 0 Td [(k ; andtherefore, k = k + )]TJ/F19 7.9701 Tf 6.586 0 Td [(k : Thisalternateformfor allowsustowrite H = f x x : x 2Ng[f 0 g = f 2 k +1:0 k q g[f 1 g : ByLemma2.21themap x x 2 permutesthe q +1 st rootsofunityso H = f k +1:0 k q g[f 1 g : Theorem2.25showsthat N[f 0 g isahyperconic,andadding1toallofthepoints in N[f 0 g yields H asdescribedabove.Therefore,byLemma2.6wendthatthe polynomial x =1+ P q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 j =2 x j isa -polynomialthatdescribesahyperconic. Wegetthefollowingasanimmediatecorollary. Corollary2.28 Thepolynomial x = x + x q = T x ; =1 isa -polynomial thatdescribesahyperconic. TheaboveformsdescribehyperconicsinAG ; 2 h forall h .Thereareadditional -polynomialsforhyperconicsthatarespecictothecasewhen h iseven.Wepresent severaldierent -polynomialsincludingmanyrationalfunctionforms.Tobegin,we provideanalternativeproofofTheorem2.27formotivation. 35

PAGE 44

Proof: Let x =1+ P q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 j =2 x j andcalculate, x =1+ q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 X j =2 x j =1+ x 2 q )]TJ/F16 7.9701 Tf 6.587 0 Td [(3 X j =0 x j =1+ x 2 1 )]TJ/F18 11.9552 Tf 11.955 0 Td [(x q )]TJ/F16 7.9701 Tf 6.586 0 Td [(2 1 )]TJ/F18 11.9552 Tf 11.956 0 Td [(x ;x 6 =1 = x +1+ x 2 x q )]TJ/F16 7.9701 Tf 6.587 0 Td [(2 +1 x +1 = x q + x 2 + x +1 x +1 Inordertoproperlyperformthesemanipulationswehavetochangethedomain to N)-275(f 1 g .Sowhenusingthis -polynomialthehyperovalpointsaredenedby f x x : x 2N)-223(f 1 gg .Thus,theformulaprovidingthehyperovalpointsis x q +1 + x 3 + x 2 + x x +1 ; where x comesfrom N)-222(f 1 g ,so x q +1 =1.Hence x x = x q +1 + x 3 + x 2 + x x +1 = x 3 + x 2 + x +1 x +1 = x 2 +1 : So, H = f x 2 +1: x 2N)-222(f 1 gg[f 0 ; 1 g = f x +1: x 2N[f 0 gg : Therefore, H isahyperconicbyLemma2.6. Thisalternativeproofindicatestheusefulnessofrepresenting -polynomialsas rationalfunctions.Thefollowingtheoremsgiveadditional -polynomialsforahyperconicinAG ; 2 h when h iseven. Theorem2.29 InAG 2 ; 2 h h even,thefunction x =1+ x +1 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 3 X j =1 x 3 j )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 = x x 2 + x +1 isa -polynomialdescribingahyperconic. 36

PAGE 45

Proof: Webeginbyshowingtherationalfunctionshownaboveisequivalenttothe polynomial. x =1+ x +1 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 3 X i =1 x 3 i )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 =1+ x +1 x 2 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 3 )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 X i =0 x 3 i =1+ x +1 x 2 1 )]TJ/F15 11.9552 Tf 11.955 0 Td [( x 3 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 3 1 )]TJ/F18 11.9552 Tf 11.956 0 Td [(x 3 ;x 6 =1 = x 3 +1+ x +1 x 2 x q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 +1 x 3 +1 = x +1 x 2 + x +1+ x q +1 + x 2 x +1 x 2 + x +1 = 1+ x + x q +1 x 2 + x +1 : Thedomainof is N)-222(f 1 g ,so x q +1 =1.Thus x = x x 2 + x +1 .11 andourhyperovalwillbe H = f x 2 x 2 + x +1 : x 2N[f 0 gg : Inordertoshowthatthispolynomialrepresentsahyperconicwewillshowthat if x + iy 2H then x 2 + xy + +1 y 2 +1=0.Thatisthepointsof H satisfyan irreduciblehomogeneousquadraticequation. FromTheorem2.25weknowthatthepointsof N lieontheconicdenedby x 2 + xy + y 2 +1=0,andthemapthatsendsthisconictotheconicdenedby x 2 + xy + +1 y 2 +1=0is x;y; 1 x y +1 ; y y +1 ; 1.Hencewewanttoshowthat H istheimageof N underthemap x + iy x + iy y +1 .Todothiswewillshow, x + iy 2 x + iy 2 + x + iy +1 = x + iy y +1 37

PAGE 46

undertheassumptionthat x 2 + xy + y 2 +1=0.Tostart,wemustrstshow that x + iy 2 + x + iy +1 6 =0,and y +1 6 =0.Firstobservethattherootsof z 2 + z +1aretheelementsofGF n GFwhicharenotin N since h isevenso x + iy 2 + x + iy +1 6 =0.Itislefttoshowthatif y =1then x + iy 62N .The point x + iy 2N ifandonlyif x 2 + xy + y 2 +1=0.Soif y =1wewouldneed x 2 + x + +1tohavearootinGF q .However,since h iseven +1hasabsolute trace1,showing x 2 + x + +1hasnorootsinGF q ,so y +1 6 =0. Now,itisclearthat x x 2 + xy + y 2 +1+ iy x 2 + xy + y 2 +1=0 : Expandingyields x 3 + x 2 y + xy 2 + x + ix 2 y + ixy 2 + iy 3 + iy =0 ; so x 3 + xy 2 + x + ix 2 y + ixy 2 + iy 3 + iy = x 2 y: Add i 2 y 3 tobothsidesandrearrangethetermstoget x 3 + xy 2 + ixy 2 + ix 2 y + iy 3 + i 2 y 3 + x + iy = x 2 y + i 2 y 3 ; andthenfactor,giving x + iy 3 + x + iy = x + iy 2 y: Now,add x + iy 2 tobothsidesandfactoragaintoyield x + iy [ x + iy 2 + x + iy +1]= x + iy 2 y +1 ; andso x + iy 2 x + iy 2 + x + iy +1 = x + iy y +1 asdesired. 38

PAGE 47

Theorem2.30 InAG 2 ; 2 h h even,thefunction x =1+ x +1 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(4 6 X i =1 x 6 i )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 = x x +1 2 x 2 + x +1 2 ; =1 isa -polynomialdescribingahyperconic. Proof: Similartothepreviousproofwewillbeginbyprovidingarationalfunction equivalenttothepolynomial. x =1+ x +1 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(4 6 X i =1 x 6 i )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 =1+ x +1 x 5 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(4 6 )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 X i =0 x 6 i =1+ x +1 x 5 1 )]TJ/F15 11.9552 Tf 11.956 0 Td [( x 6 q )]TJ/F17 5.9776 Tf 5.756 0 Td [(4 6 1 )]TJ/F18 11.9552 Tf 11.955 0 Td [(x 6 ;x 6 =1 = x 6 +1+ x +1 x 5 x q )]TJ/F16 7.9701 Tf 6.587 0 Td [(4 +1 x 6 +1 = x +1 x 5 + x 4 + x 3 + x 2 + x +1+ x q +1 + x 5 x +1 x 5 + x 4 + x 3 + x 2 + x +1 = x 4 + x 3 + x 2 + x +1+ x q +1 x 5 + x 4 + x 3 + x 2 + x +1 : Again,thedomainof is N)-222(f 1 g ,so x q +1 =1.Thus x = x 4 + x 3 + x 2 + x x 5 + x 4 + x 3 + x 2 + x +1 = x x +1 3 x 3 +1 x 2 + x +1 = x x +1 2 x 2 + x +1 2 andsoourhyperovalis H = f x x +1 2 x 2 + x +1 2 : x 2N)-222(f 1 gg[f 0 ; 1 g : Inordertoshowthat H isahyperconicwewillshowthatif x + iy 2H then x 2 + xy + +1 y 2 + y =0.Thatis,thepoint'scartesiancoordinates x;y; 1give 39

PAGE 48

asolutionto x 2 + xy + +1 y 2 + yz =0.Thecollineationthatsendsthisconic to x 2 + xy + +1 y 2 +1isdenedby x;y; 1 x +1 ;y; 1andweknowthat x 2 + xy + +1 y 2 +1denestheconicassociatedwiththe -polynomialgivenin .11fromTheorem2.29. Let 1 x = x x 2 + x +1 and 2 x = x x +1 2 x 2 + x +1 2 : Wewillshowthat 1 +1= q= 2 2 q= 2 forarbitrary 2N ,whichwillprovethatthemap x;y; 1 x +1 ;y; 1sendsthe hyperovalassociatedwith 1 tothehyperovalassociatedwith 2 Let 2N .Clearly, 2 q +2 + q +2 + 2 q +1 + q +1 + 2 q + q = 2 q +1 + q +1 + 2 q + q + +1 : Factoringbothsidesyields 2 q + q 2 + +1= 2 q + q +1 +1 andso 2 q + q 2 q + q +1 = +1 2 + +1 : Rewritingthetermsonbothsidesgives q= 2 2 + q= 2 q= 2 2 + q= 2 +1 2 = 2 2 + +1 +1 andso 1 +1= q= 2 2 q= 2 asdesired.Hence 2 isalsoa -polynomialdescribingahyperconic. 40

PAGE 49

Nowthatwehaveseenwhatwecandowithhyperconicsweturnourattention tothemoregeneraltranslationhyperovals. 2.6.2TranslationHyperovals OurgoalinthissectionistouseTheorem2.24todetermineageneral polynomialformforthetranslationhyperovals.Inordertodothis,wemustnd aline y = x + thatisexternaltothehyperoval. Lemma2.31 Theline y = x + isexternaltothetranslationhyperovalwithopolynomial f t = t 2 k ifandonlyif tr =1 where tr denotestheabsolutetrace function. Proof: Theline y = x + isexternaltothetranslationhyperovalwitho-polynomial f t = t 2 k ifandonlyif x 2 k + x + hasnorootsinGF q Now, x 2 k + x + =0ifandonlyif x 2 k + k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 X j =1 x 2 j + x 2 j + x + = x 2 k + x 2 k )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 + x 2 k )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 + x 2 k )]TJ/F17 5.9776 Tf 5.757 0 Td [(2 + + x 2 + x + =0 : Hence plusasumofelementsofabsolutetrace0is0,sotheequationholdsifand onlyif tr =0.Therefore,theequationhasnorootsifandonlyif tr =1as desired. Theorem2.32 InAG,q,with q =2 h ,thepolynomial x = x x +1 2 s 2 x 2 +2 +1+ s +1 2 x 2 + x 2 ; =1 isa -polynomialdescribingthetranslationhyperovalwitho-polynomial f t = t ; = 2 k ,where s = P k )]TJ/F16 7.9701 Tf 6.587 0 Td [(2 j =0 2 j : Proof: Webeginwith.10fromTheorem2.24andperformthefollowingcalculations, 1 x T x = i + x 2 x +1 2 + i + + x 2 x +1 2 41

PAGE 50

1 x T x = i + i + x +1 2 + x 2 x +1 2 )]TJ/F16 7.9701 Tf 6.586 0 Td [(2 + x 2 x +1 2 x = x +1 2 [ i + i + x +1 2 + x 2 x +1 2 )]TJ/F16 7.9701 Tf 6.587 0 Td [(2 + x 2 ] T x x = x x +1 2 )]TJ/F16 7.9701 Tf 6.586 0 Td [(2 i + i + x +1 2 + x 2 x +1 2 )]TJ/F16 7.9701 Tf 6.587 0 Td [(2 + x 2 : FromLemma2.31wecanlet = since tr =1.So,usingLemma2.8,and multiplyingthenumeratoranddenominatorby x +1 2 yields x = x x +1 2 s 2 x +1 2 +2 + x 2 x +1 2 + x 2 x +1 2 : Finally,byexpandingandrearrangingthetermsweobtain x = x x +1 2 s 2 x 2 +2 +1+ s +1 2 x 2 + x 2 : Wecanseethatnotonlydoesthe -polynomialdependon butalsothechoice of .Wegiveasimplerformforthe -polynomialwhen h isoddandalsogivea specic -polynomialforthetranslationhyperovalwitho-polynomial f t = t 4 Corollary2.33 InAG,q,with q =2 h h odd,thefollowingare -polynomialsthat producethetranslationhyperovalwitho-polynomial f t = t =2 k When k iseven x = x x +1 2 x 2 +2 +1 ; =1 : When k isodd x = x x +1 2 x 2 + x 2 ; =1 : Proof: Since h isoddwemaychoose =1since tr =1.Let s = P k )]TJ/F16 7.9701 Tf 6.587 0 Td [(2 j =0 2 j and observethat s =0when k isoddand s =1when k iseven.Thus,theresultfollows immediatelyfromTheorem2.32 42

PAGE 51

Observation2.34 The -polynomial x = x x +1 8 x 10 +1 ; =1 describesthetranslationhyperovalwitho-polynomial f t = t 4 Additionally,wemaysimplifyinthecasewhere h 2mod4.Firstweneeda lemmaaboutourchoiceof inthiscase. Lemma2.35 InGF 2 h h 2mod4 thepolynomial x 2 + x + isirreducible, where satises 2 + +1=0 Proof: Inordertoshow x 2 + x + isirreduciblewemustonlyshowthat has absolutetrace1.Observethat tr = + 2 + 2 2 + + 2 h )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 and 2 j = if j iseven,and 2 j = 2 if j isodd.Since 2 + =1wehave tr = + 2 + 2 2 + + 2 h )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 = h= 2 X j =1 1=1 since h 2mod4. Corollary2.36 InAG 2 ;q q =2 h h 2mod4 ,thefollowingare -polynomials thatproducethattranslationhyperovalwitho-polynomial f t = t =2 k When k 1mod4 x = x x +1 2 x 2 + x 2 ; =1 : When k 3mod4 x = x x +1 2 x 2 +2 +1 ; =1 : 43

PAGE 52

Proof: Since h 2mod4wemaychoose = where 2 + +1=0from Lemma2.35.Let s = P k )]TJ/F16 7.9701 Tf 6.586 0 Td [(2 j =0 2 j andobservethat s =0when k 1mod4and s =1when k 3mod4,since 2 + =1and 2 j = if j iseven,and 2 j = 2 if j isodd.TheresultfollowsimmediatelyfromTheorem2.32. Wehavegiven -polynomialformsforalltranslationhyperovalsinthecaseswhen h 6 0mod4.Wewillproveamoregeneralresultthatwillencompassthiscaseas wellasmanyothers. Theorem2.37 InAG 2 ;q q =2 h ,thefunction x = x x +1 2 x 2 + x 2 ; =1 isa -polynomialdescribingatranslationhyperovalwitho-polynomial f t = t =2 k k odd. Proof: Let =2 k for k odd.Wewillbeginwith.9fromSection2.5sowemust choose 2 GF q suchthat y = x + isexternaltothehyperoval.Wecanchoose any with tr =1byLemma2.31solet = P k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 j =0 2 j whichhasabsolutetrace1 since k isodd. Wewanttoshowthat i + x 2 x +1 2 = i + + x 2 x +1 2 + 1 x T x whichreducesto i + i + + x 2 x +1 2 + x 2 x +1 2 + x 2 + x 2 x +1 2 +2 =0 ; andso, i + i + =0 : However,withourchoiceof weknowthat i + i + =0byLemma2.8,which provestheresult. Thisresultallowsustogiveaconcisesummaryoftranslationhyperovalsforall h aswedidinCorollary2.33for h odd. 44

PAGE 53

Corollary2.38 InAG,q,with q =2 h thefollowingare -polynomialsthatproduce thetranslationhyperovalwitho-polynomial f t = t =2 k When k iseven x = x x +1 2 x 2 +2 +1 ; =1 : When k isodd x = x x +1 2 x 2 + x 2 ; =1 : 2.6.3TheSegreHyperoval NowweturnourattentiontotheSegrehyperoval.InordertouseTheorem2.24 wemustndaline y = x + thatisexternaltotheSegrehyperoval. Lemma2.39 Theline y = x +1 isexternaltotheSegrehyperoval. Proof: Inordertoshowaline y = x + isexternaltoahyperovalinAG ;q with o-polynomial f wemustshowthat f x + x + hasnorootsinGF q .Thusinthis casewemustshow g x = x 6 + x +1hasnorootsinGF h when h isodd. Assumethat a 2 GF q ,and g a =0.Itiseasilycheckedthat g hasnorootsin GF h for1 h 5,thus q 64.Since a isarootwemusthavethat a 2 k isalsoa rootfor0 k 5,andtheserootsaredistinctsince q 64.Weknow x 6 + x +1has atmost6roots,andtheserootslieinanorbitunderthemap x x 2 ,so a 64 = a implying a 2 GF whichimplies q =2 6 k .Hencethispolynomialhasnoroots inGF h when h isoddandthereforetheline y = x +1isexternaltotheSegre hyperoval. Theorem2.40 InAG,q,with q =2 h h odd,thepolynomial x = x x +1 10 i 2 x 12 + x 10 + x 8 + x 4 + x 2 + i ; =1 producestheSegrehyperoval. 45

PAGE 54

Proof: Againwebeginwith.10fromTheorem2.24with f x = x 6 and =1. Since h isoddwemaketheadditionalassumptionthat i 2 GF n GF.The followingcalculationsprovetheresult. 1 x T x = i + x 2 x +1 2 6 + i +1+ x 2 x +1 2 1 x T x = x 2 + i x +1 2 6 x +1 12 + i + 1 x +1 2 1 x T x = x 2 + i x +1 2 6 + i x +1 12 + x +1 10 x +1 12 1 x T x = x 12 + ix 4 x +1 8 + i 2 x 8 x +1 4 + x +1 12 + i x +1 12 + x +1 10 x +1 12 x = x x +1 10 x 12 + i 2 x +1 12 + x +1 10 + ix 4 x +1 8 + i 2 x 8 x +1 4 x = x x +1 10 i 2 x 12 + x 10 + x 8 + x 4 + x 2 + i AsanimmediatecorollaryweseethattheSegrehyperovalcanalwaysberepresentedwitha -polynomialwithcoecientsoverGF,sincewecanalwaysassume that i 2 GF/GF.Also,weknowthattheSegrehyperovalisnotrepresented bya -polynomialwithcoecientsoverGFbyCorollary2.18,sincetheautomorphismgroupoftheSegrehyperovalhasorder q )]TJ/F15 11.9552 Tf 12.02 0 Td [(1 h or3 q )]TJ/F15 11.9552 Tf 12.02 0 Td [(1 h asseeninTable 1.2. 46

PAGE 55

2.6.4TheAdelaideHyperoval Wenowpresentacompact -polynomialfortheAdelaidehyperoval.Wegenerated -polynomialsfortheAdelaidehyperovalinsomesmallorderplanesandmade thefollowingobservation. Observation2.41 InAG 2 ; 2 h h =2 ; 4 ; 6 ; 8 ,the -polynomial x =1+ 0 @ x +1 s 3 X j =1 x 4 j )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 1 A + 0 @ x +1 s 3 X j =1 x 4 j )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 1 A q where s =2 h )]TJ/F16 7.9701 Tf 6.586 0 Td [(2 )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 isa -polynomialthatrepresentstheAdelaidehyperoval. Weturnthepolynomialaboveintoarationalfunctionthroughthefollowing calculations. x =1+ x +1 x 3 s 3 X j =1 x 4 j )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 + 0 @ x +1 x 3 s 3 X j =1 x 4 j )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 1 A q =1+ x +1 x 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( x 4 s 3 1 )]TJ/F18 11.9552 Tf 11.955 0 Td [(x 4 + x +1 x 3 )]TJ/F15 11.9552 Tf 11.955 0 Td [( x 4 s 3 1 )]TJ/F18 11.9552 Tf 11.955 0 Td [(x 4 q ;x 6 =1 =1+ x 3 x 4 s 3 +1 x +1 3 + x 3 x 4 s 3 +1 x +1 3 q = x +1 3 + x 3 x q )]TJ/F17 5.9776 Tf 5.756 0 Td [(4 3 +1+ x q )]TJ/F17 5.9776 Tf 5.756 0 Td [(4 3 +1 q x +1 3 = x 3 + x 2 + x +1+ x q +5 3 + x 3 + x q q )]TJ/F17 5.9776 Tf 5.756 0 Td [(4 3 +1 x +1 3 = x q q )]TJ/F17 5.9776 Tf 5.757 0 Td [(4 3 + x q +5 3 + x 2 + x x +1 3 : Foreaseofsimplicationwewilltemporarilyreplace x with s 3 ,whichsimplyreorders 47

PAGE 56

therootssince q =2 h h even,andproceedwithourcalculations. s 3 = s q q )]TJ/F16 7.9701 Tf 6.586 0 Td [(4 + s q +5 + s 6 + s 3 s 3 +1 3 = s q q +1 s )]TJ/F16 7.9701 Tf 6.586 0 Td [(5 q + s q +1 s 4 + s 6 + s 3 s 3 +1 3 = s 6 + s 5 + s 4 + s 3 s 3 +1 3 = s 3 s +1 3 s 3 +1 3 Nowweundooursubstitutionandobtain x = x x 1 3 +1 3 x +1 3 ; =1 : Inordertoprovethatthisisa -polynomialfortheAdelaidehyperovalwewillfollow theapproachofFisherandSchmidtsee[17]section6,andshowthepointslieonan algebraicplanecurveshowntorepresenttheAdelaidehyperovalbyPayneandThas in[38].First,weshowthatthepointssatisfyasixthdegreeequation. Lemma2.42 Thepoints f t t : t 2N)-222(f 1 gg[f 1 g where t = t t 1 3 +1 3 t +1 3 satisfytheequation y 6 + y 4 + xy + x 2 + +1 y 2 +1=0.12 whenthoughtofaspoints x;y; 1 incartesiancoordinates. Proof: UsingLemma2.23weknowthatthecartesianformofthepointsis f t T i t ; t T t ; 1: t 2N)-223(f 1 gg[f ; 0 ; 1 g : Clearly ; 0 ; 1satisesthisequationsowefocusontheother q points.Observethat T t = t +1 2 t and T i t = i t +1 2 + t 2 t sothatthecartesianformofthepointsis x;y; 1 with x = t 1 = 3 +1 3 i t +1 2 + t 2 t +1 3 ;y = t 1 = 3 +1 3 t +1 : 48

PAGE 57

Substitutingthesevaluesof x and y into.12,andmultiplyingtheresultingequation by t +1 6 yields t 1 = 3 +1 18 + t +1 2 t 1 = 3 +1 12 + t 1 = 3 +1 6 i t +1 2 + t 2 t +1 2 + t 1 = 3 +1 6 i t +1 2 + t 2 2 + t 1 = 3 +1 6 t +1 4 + t +1 6 : Replacing t with s 3 ,expanding,andfactoringgives i 2 + i + s +1 10 s 2 + s +1 4 =0 ; since i 2 + i + =0.Hence,theresultholds. Now,replacing x with x=z and y with y=z in.12andthenmultiplyingby z 6 gives.12inprojectivecoordinates; y 6 + y 4 z 2 + z 4 xy + x 2 + +1 y 2 + z 6 =0 : .13 WeneedonenallemmaofPayneandThastoproveourresult;see[38]Lemma5.1, Theorem5.2.Wechangetheirnotationtobeconsistentwithourown. Lemma2.43[38] If O representsanAdelaideovalasdescribedinsection5of [38],and C = f t;u;v 2 PG ;q : T 2 v 6 + v + t 4 u 2 + T tu + v 2 =0 g ,where isaprimitiveelementof N ,then C = O[ ; 1 ; 0 ThislemmashowsthatthepointsoftheAdelaideovaldirectlycoincidewiththe pointsofthealgebraicplanecurve.Wearenowreadytoprovethemaintheoremof thissection. Theorem2.44 InAG 2 ; 2 h h even,thepolynomial x = x x 1 3 +1 3 x +1 3 isa -polynomialrepresentinganAdelaidehyperoval. 49

PAGE 58

Proof: UsingLemma2.43,andsubstituting t = y u = T x v = y + z into T 2 v 6 + v + t 4 u 2 + T tu + v 2 =0gives.13with = 1 T 2 .Tonishthe resultwemustshowthat x 2 + x + 1 T 2 isirreducibleinGF2 h h even.Fisherand Schmidtshowedtheequation x 2 + x +1+ 1 T 2 isirreducible,see[17]Theorem6.2. Hence tr + 1 T 2 =1where tr denotestheabsolutetracefunction.Since h iseven, and tr isadditivewehave tr + 1 T 2 = tr + tr 1 T 2 = tr 1 T 2 =1 : Therefore, x 2 + x + 1 T 2 isirreducibleinGF h h even. 2.6.5TheSubiacoHyperoval InthissectionwegiveauniedformforthehyperovalsintheSubiacofamily whoseautomorphismgroupshaveorderdivisibleby2 h .Computerinvestigationsled ustoconsiderthepolynomial x = x 5 x 10 + x 6 + x 5 + x 4 +1 : Wewillshowthat isa -polynomialrepresentingaSubiacohyperovalinAG ;q q =2 h forall h 1.Observethatthis -polynomialhascoecientsoverGFso thehyperovalitrepresentsmusthaveanautomorphismgroupwithorderdivisibleby 2 h byCorollary2.18.Assuch,thispolynomialdoesnotrepresenteveryhyperovalin theSubiacofamily,uptoprojectiveequivalence. Webeginbyconsideringthesetofpoints f x x : x 2Ng[f 0 g andapplying thehomographydenedby x;y;z 0 B B B B @ 110 0 1 010 1 C C C C A = x;x + y + z;y with = p + 1 + 1 2 toobtainthesetofpoints f i + x 2 x +1 2 ;i + + x 2 x +1 2 + 1 x T x ; 1: x 2N)-222(f 1 gg[f ; 1 ; 0 ; ; 0 ; 0 g ; 50

PAGE 59

asshowninSection2.5.Wewillshowthat i + + x 2 x +1 2 + 1 x T x .14 representsano-polynomialforaSubiacohyperovalinvariable i + x 2 x +1 2 .Observe that p x T x = x 4 x +1 2 x 10 + x 6 + x 5 + x 4 +1 ; so.14reducesto i + + x 2 x +1 2 + x 10 + x 6 + x 5 + x 4 +1 x 4 x +1 2 = i + x 4 x +1 2 + x 6 + x 10 + x 6 + x 5 + x 4 +1 x 4 x +1 2 = x 10 + i + x 6 + x 5 + i + +1 x 4 +1 x 4 x +1 2 : Now,let t = i + x 2 x +1 2 so x = q t + i t + i +1 .Makingthissubstitutionyields h t := t + i +1 3 t + i 2 t + i t + i +1 5 + i + t + i t + i +1 3 + t + i t + i +1 5 = 2 + i + +1 t + i t + i +1 2 +1 # = t + i 5 + i + t + i 3 t + i +1 2 + i + +1 t + i +1 3 t + i 2 + t + i +1 5 t + i +1 2 t + i 2 + p t + i +1 t + i = t 5 + t 4 + t 3 + +1 t 2 + i 2 + i +1 2 t + i 4 + i 2 + i 2 + i +1 t 2 + t + i 2 + i 2 + p t 2 + t + i 2 + i = + i + p i t 4 + + i + p i +1 t 2 + t + + p i i 4 + i 2 + i 5 + i 3 + i 2 + i +1 t 2 + t + i 2 + i 2 + t 1 = 2 : Recallthat i 2 + i = ,soletting z = p t andreducing h yields h z = 2 + p z 4 + + p +1 z 2 + p z + + p i 2 + i 3 i 2 +1+ +1 2 z 2 + 1 p z +1 2 + p z 1 = 2 : 51

PAGE 60

Since = p + 1 + 1 2 wehave h z = +1 z 4 + +1+ 1 z 2 + p z 2 z 2 + 1 p z +1 2 + p t 1 = 2 : Nowlet d = 1 p sothat tr 1 d =1.Simplifyingandmakingthesubstitutionfor d yields h z = 1 + 1 2 z 4 + 1 + 1 2 + 1 3 z 2 + 1 p z z 2 + 1 p z +1 2 + p z 1 = 2 = d 2 d 2 +1 z 4 + d 2 + d 2 + d 4 z 2 + d 3 z z 2 + dz +1 2 + z d 1 = 2 : Thus,ourpointsetisrepresentedby f z;h z ; 1: z 2 GF q g[f ; 0 ; 0 ; ; 1 ; 0 g : Next,wenormalize h sothat h =1togetthepointset f x;f x ; 1: x 2 GF q g[f ; 0 ; 0 ; ; 1 ; 0 g where f x = 1 d 5 + d 2 + d 1 = 2 d 3 d 2 +1 x 4 + d 3 + d 2 + d 4 x 2 + d 4 x x 2 + dx +1 2 + dx 1 = 2 : Weclaimthatthisisano-polynomialforaSubiacohyperoval. Lemma2.45 Let d 2 GF q suchthat tr 1 d =1 .Thepolynomial f x = 1 d 5 + d 2 + d 1 = 2 d 3 d 2 +1 x 4 + d 3 + d 2 + d 4 x 2 + d 4 x x 2 + dx +1 2 + dx 1 = 2 isano-polynomialforaSubiacohyperoval. Proof: InTheorem5of[15]itisshownthat g x = d 4 x 4 + d 3 + d 2 + d 4 x 3 + d 3 + d 2 x d 2 + d 5 + d 1 = 2 x 2 + dx +1 2 + d 1 = 2 d 2 + d 5 + d 1 = 2 x 1 = 2 52

PAGE 61

isano-polynomialforaSubiacohyperoval,where d isasdescribedabove.Applying thehomographydenedby x;y;z 0 B B B B @ 001 010 100 1 C C C C A = z;y;x tothehyperoval H denedby H := f x;g x ; 1: x 2 GF q g[f ; 0 ; 0 ; ; 1 ; 0 g yieldsthepointset H 0 = f ;g x ;x : x 2 GF q g[f ; 0 ; 1 ; ; 1 ; 0 g = f ;g x ;x : x 2 GF q g[f ; 0 ; 1 ; ; 1 ; 0 ; ; 0 ; 0 g : Wenownormalizethepoints f ;g x ;x : x 2 GF q g = f 1 x ; g x x ; 1: x 2 GF q g : Letting t = 1 x givesthepoints f t;tg 1 t ; 1: t 2 GF q g : Wenowfocusourattentiononreducing tg 1 t tg 1 t = t d 5 + d 2 + d 1 = 2 d 4 =t 4 + d 3 + d 2 + d 4 =t 3 + d 3 + d 2 =t =t 2 + d=t +1 2 + d t 1 = 2 = t d 5 + d 2 + d 1 = 2 d 4 + d 3 + d 2 + d 4 t + d 3 + d 2 t 3 t 2 + dt +1 2 + d t 1 = 2 = f t : Withtheobservationthat f =0weseethat H 0 = f t;f t ; 1: t 2 GF q g[f ; 0 ; 0 ; ; 1 ; 0 g ; so f isano-polynomialforaSubiacohyperoval. Theaboveremarksgivethefollowingtheorem. 53

PAGE 62

Theorem2.46 InAG 2 ;q q =2 h ,thepolynomial x = x 5 x 10 + x 6 + x 5 + x 4 +1 isa -polynomialforaSubiacohyperovalwhoseautomorphismgrouphasorderdivisibleby 2 h This -polynomialdescribes,uptoprojectiveequivalence,allSubiacohyperovals inAG ; 2 h when h isodd,andwhen h 0mod4.However,when h 2 mod4thereareSubiacohyperovalswithautomorphismgroupoforder 5 h 2 ,which arenotdescribedbythis -polynomial.A -polynomialdescribingahyperovalwith automorphismgroupoforder 5 h 2 cannothavecoecientsoverGF.Infact,GF isthesmallestordereldinwhichthecoecientsforsucha -polynomialcould exist.A -polynomialrepresentingtheSubiacohyperovalwithautomorphismgroup oforder15inAG,64isgiveninChapter3. 2.6.6OtherFamilies TheGlynn,Payne,andCherowitzohyperovalshavebeenresilienttoshowingcompact -polynomialrepresentations.Thegeneralconversionfromtheiro-polynomial formsasgiveninTheorem2.24arecurrentlythemostappealing.Thedicultyin conversionstemsfromthefactthatthesehyperovalsarealreadyquiteelegantlyrepresentedaso-polynomials.Theexponentsonthepolynomialtermsarevariablebased ontheplanetheylivein,ratherthanaxedinteger.Thisinitselfpresentsdiculty insimplication.Itmaybepossibletousecaseanalysis,similartothatinCorollary 2.33,tofurthersimplifythe -polynomialsforhyperovalsinthesefamilies,butour workuptothispointhasnotbeenfruitful. Throughstudyingthe -polynomialrepresentationithasbecomeclearthatsome hyperovalswillbebetterrepresentedaso-polynomials.Manyofthemonomials,with exceptionofthehyperconic,aremoreelegantlyrepresentedaso-polynomials.In fact,aswesawinTheorem2.40theSegrehyperovalhasitssimplest -polynomial 54

PAGE 63

PAGE 64

3.AComputationalApproach Thischapterisdevotedtoshowinghowthe -polynomialmethodcanbeused tofurtherexpandthesearchforhyperovalsbycomputer.WesawinSections2.4.2 and2.4.3thatthestructureof -polynomialsdirectlycorrespondstothehyperovals beingstabilizedbyeldautomorphismsandmultiplicativeactions.Weusethese theoreticalresultstosearchforhyperovalsstabilizedbytheseactions,andinturn searchforhyperovalswhose -polynomialshavethedesiredproperties.Thisissimilar totheapproachofFisherandSchmidt,butwedonotrestrictourselvestoonlythe polynomialswithmanyzerocoecients. 3.1CyclotomicSets Whilestudyingthe -polynomialrepresentationwenoticedanicepropertyof thehyperovalsthathavetheir -polynomialsrepresentedoversubeldsofGF q 2 .In ordertodescribethestructureofhyperovalswhose -polynomialshavecoecientsin asubeld,wegivethefollowingdenition. Denition3.1 Givenanelement 2 GF q 2 andanautomorphism : x x 2 k ,of GF q 2 ,wecangeneratetheset: C = f ; ; 2 ;:::; s )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 g ; where s = h h;k C isthesetofalloftheimagesof undertheautomorphism Wecallthisa cyclotomicset andthinkofitasageometricstructureinAG 2 ;q Acyclotomicsetistheorbitofthepoint undertheautomorphism ,but wewishtodistinguishthissetofpointsasastructureinAG ;q ,hencethenew name.Ifonewishestodescribethesesetsinatraditionalway,theyaresetsofpoints stabilizedbythecollineationsdescribedinLemma2.9.Theorem2.17showsthatifa hyperovalhasa -polynomialwithcoecientsinthesubeldGF k ofGF q 2 then thehyperovalcanbepartionedintocyclotomicsetsdenedbytheautomorphism : x x 2 k .Duetothisweusecyclotomicsetsasbuildingblocksforhyperovals. 56

PAGE 65

Anecessaryconditionforacyclotomicsettobepartofahyperovalisthatitis anarc.Cyclotomicsetsarenotalwaysarcs,butweleavethatdiscussionforthe nextchapterwherewedeterminewhenacyclotomicsetisanarcseeCorollary4.7. Whenacyclotomicsethasaparticularstructureweoftenrefertoitasacyclotomic structure,e.g.,acyclotomicarc.Wenowassumethatweknowwhichcyclotomicsets arearcsanddescribehowwecanusethemtosearchfornewhyperovals. 3.2Using -polynomialstoSearchforHyperovals AswehaveseeninLemma2.7,theeldautomorphismsofGF q 2 induce collineations.Sinceeachautomorphismxestheorigintheypermutethelinesthrough theorigindeningorbitsoftheselines.Theorbitsofthelinesthroughtheorigin correspondexactlytotheorbitsofthe q +1 st rootsofunity,orrather,thecyclotomic setsof N .Werefertoeachorbitoflinesasa sector andnotethateverycyclotomic setliesinexactlyonesectorasshowninFigure3.1. q 2 q 2 q q 2 2 2 q 2 Figure3.1:ASectorwithaCyclotomicSet Asbefore,weassumethatahyperoval H contains0,andso,mustcontainexactly oneotherpointoneachlinethroughzero.Hence,if H isstabilizedbyanautomorphism ,itmustcontainexactlyonecyclotomicsetdenedby fromeachsector. 57

PAGE 66

Duetothispartitioningweareabletodoecientbacktracksearches,choosingone elementfromeachsectoratatime.Weimplementedabacktracksearchforallhyperovalsstabilizedbytheautomorphism : x x 2 inAG ; 2 h for4 h 8and forhyperovalsstabilizedby : x x 4 inAG2,32.Theruntimesofthesesearches aregiveninTable3.1. Table3.1:RunTimesforBacktrackSearches Plane Action Time AG,16 x x 2 < 1sec AG,32 x x 2 < 1sec AG,32 x x 4 6sec AG,64 x x 2 8.5sec AG,128 x x 2 10min AG,256 x x 2 68hours FromCorollary2.18weknowthatifwearegoingtondahyperoval H stabilized by : x x 2 k thenwemusthave 2 h k dividing j Aut H j .Infact,ourresultsinthe followingsectionsshowthatwendpreciselythosehyperovalswhoseautomorphism groupsizesaredivisbleby 2 h k AsisdisplayedinTable3.1thesearchtimeforbacktracksearchesquicklybecomes unmanageableasthesizeoftheeldgrows.Duetothiswelookedforalternative searchmethods.Thefollowingmethod,thatwecallCliqueFinder,isdescribedas follows: Deneagraph G = V;E where V = fC : C isacyclotomicarc g and E = f x;y : x [ y isanarc g .Assigncolorstotheverticessothattwoverticesreceivethe samecolorifandonlyiftheircorrespondingcyclotomicarcslieinthesamesector. Ifacollectionofcyclotomicarcsarecombinedtocreateahyperovalthentheywill appearasarainbowcliquein G ,thatis,acompletesubgraphwhereallthevertices 58

PAGE 67

aredierentcolors.Thegraphasdescribedwillcontainrainbowcliquesthatarenot hyperovals,becausetherearesetsofthreecyclotomicarcswhosepairwiseunionsare arcs,buttheunionofallthreeisnot.Toremedythis,wecheckforthesefalsetriples asthegraphisbuilt.ThissearchtechniqueisimplementedintheOrbiterpackage writtenbyAntonBetten,see[3]. WeimplementedtheCliqueFindersearchforhyperovalsstabilizedby : x x 2 inAG ; 2 h for6 h 9and : x x 4 inAG ; 2 h for5 h 7,withpartial searchesdoneinAG,256.Cliquenderissignicantlyfasterthantheprevious backtracksearchesasisshowninTable3.2. Table3.2:RunTimesforCliqueFinder Plane Action Time AG,64 x x 2 4sec AG,128 x x 2 7sec AG,128 x x 4 3min22sec AG,256 x x 2 2hours30min AG,256 x x 4 est.240weeks AG,512 x x 2 8hours45min Wewereunabletocompletesearchesforhyperovalsstabilizedby : x x 2 k for largevaluesof k sincethecyclotomicsetsizesbecomesmallandthegraphbecomes unwieldy.Also,inordertondcertainfamiliesofhyperovalsinsmallplanes,wehave tolookforhyperovalsstabilizedbytheaction x x for 2N .Thesearchfor hyperovalsstabilizedbytheseactionswasimplementedusingabacktracksearchin AG,32andAG,64. Searchingforhyperovalsstabilizedbyspecicactionshasagreatprecedentinthe studyofhyperovals.OurapproachiscloselyrelatedtothatofO'KeefeandPenttila in[31],PenttilaandPinneriin[40],andPenttilaandRoylein[42].Thetechnique 59

PAGE 68

usedin[31]and[40]iscalledprimeatatime."Thetechniquetakesaprime p andconstructsallhyperovals H suchthat p jj Aut H j .Thetechniqueconsiders allconjugacyclassesofelementsoforder p inPL ;q andndsthehyperovals stabilizedbythecollineations.Oursearchesforhyperovalsstabilizedbythemaps x x for 2N arearestrictedversionofprimeatatime." In[42]PenttilaandRoyleuseprimeatatime,butalsosearchforhyperovals stabilizedbythecollineationdenedby 0 B B B B @ x y z 1 C C C C A 0 B B B B @ 100 a 10 b 10 1 C C C C A 0 B B B B @ x 2 y 2 z 2 1 C C C C A .1 where a and b areelementsofabsolutetrace1.Thiscollineationiscloselyrelatedto thecollineationinducedbyautomorphismsofGF q 2 giveninLemma2.9. TheprimeatatimetechniquehelpeddiscovertheO'Keefe-Penttilahyperovalin [31],therstexamplesoftheSubiacohyperovalin[40],andhelpedclassifyhyperovals withnon-trivialautomorphismgroupinPG,64,whichuncoveredtherstexampleoftheAdelaidehyperovalin[42].Additionally,thecollineationdenedin.1 wasusedtodiscoveradditionalexamplesoftheAdelaideandSubiacohyperovalsin PG,256.Withthisprecedentinmindwesearchedforhyperovalsstabilizedby ourcollineationsinthepolarmodelinsomesmallplanes.Webeginoursearchesin AG,16asitisthesmallestorderplanewithanirregularhyperoval,i.e.,anonhyperconic. 3.2.1SearchesinAG,16 InAG ; 16wesearchedforhyperovalsstabilizedbythemap x x 2 and thesearchrevealedboththehyperconicandLunelli-Scehyperovals.Theseare theonlyhyperovalsthatarecontainedinthisplanesowedidnotdoanyfurther searches.Intotaleighthyperovalswerefound,fourofeachtype.TheLunelli-Sce 60

PAGE 69

-polynomialsareofparticularinteresthereastheyhavebeenshowntobemembersoftheAdelaideandSubiacofamilies.Sincethesehyperovalsarestabilizedby thesquaringautomorphismtheynecessarilyhave -polynomialswithcoecientsover GFwheretheiro-polynomialcounterpartsdonot.TheLunelli-Sce -polynomial x = x 14 + x 13 + x 4 + x 3 +1satisesthegeneralformfortheAdelaide -polynomial giveninTheorem2.44andtheformfortheSubiacohyperovalgiveninTheorem2.46. Additionally,allfourformsofthehyperconicfromSection2.6.1arerepresented.Due tothemanageablelistandsizeofeach -polynomialwelistallofthemintheir entirety. Table3.3: -polynomialsforhyperovalsinAG ; 16 Hyperoval -polynomial Hyperconic 1 x 12 + x 11 + x 6 + x 5 +1 x 15 + x 14 + x 12 + x 11 + x 9 + x 8 + x 6 + x 5 + x 3 + x 2 +1 x 15 + x 14 + x 13 + x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 +1 Lunelli-Sce x 14 + x 13 + x 4 + x 3 +1 x 14 + x 11 + x 9 + x 8 + x 6 + x 3 +1 x 14 + x 13 + x 12 + x 10 + x 7 + x 5 + x 4 + x 3 +1 x 15 + x 13 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 4 + x 2 +1 3.2.2SearchesinAG,32 InAG ; 32wecompletedthreesearches,oneforhyperovalsstabilizedbyeach ofthefollowingactions, x x 2 x x 4 x !x ,where 3 =1.Theresearchusing x x 2 yieldedthreedistincthyperovals,thehyperconic,translation,andPayne hyperovals.Thesearchusing x x 4 gavetheCherowitzoandSegrehyperovals 61

PAGE 70

inadditiontothosefromthe x x 2 search.Finally,thesearchusing x !x gavetheSegreandO'Keefe-Penttilahyperovals.Theseareallofthehyperovals inAG,32sothislistaddsacompletesetof -polynomialsforhyperovalsinthis plane.Observethatthehyperovalsstabilizedby x x 2 arepreciselythosehyperovals whoseautomorphismgroupsaredivisibleby10=2 h ,andthosestabilizedby x x 4 arepreciselythosehyperovalswhoseautomorphismgroupsaredivisibleby5= h Further,hyperovalsstabilizedby x !x arepreciselythosewhoseautomorphism groupsaredivisibleby3.Assuch,thenecessaryconditiongiveninCorollary2.18is alsosucientinthisplane. Wechosethemostappealing -polynomialstoshowhere.FortheO'KeefePenttila -polynomial, b isaprimitiveelementofGFsatisfying b 10 = b 6 + b 5 + b 3 + b 2 + b +1. Table3.4: -polynomialsforhyperovalsinAG ; 32 Hyperoval -polynomial Hyperconic 1 Translationt 4 x 29 + x 28 + x 24 + x 23 + x 19 + x 18 + x 15 + x 14 + x 10 + x 9 + x 5 + x 4 +1 Segre x 30 + 2 x 27 + 2 x 24 + x 21 + x 12 + !x 9 + !x 6 + x 3 +1 Payne x 31 + x 30 + x 28 + x 23 + x 20 + x 19 + x 17 + x 16 + x 14 + x 13 + x 10 + x 5 + x 3 + x 2 +1 Cherowitzo x 30 + x 28 + 2 x 27 + x 26 + x 25 + x 24 + 2 x 23 + 2 x 22 + !x 21 + !x 20 + !x 17 + 2 x 16 + 2 x 13 + 2 x 12 + !x 11 + !x 10 + x 9 + x 8 + x 7 + !x 6 + x 5 + x 3 +1 O'Keefe-Penttila b 511 x 30 + b 924 x 27 + b 230 x 24 + b 557 x 21 + b 3 x 18 + b 96 x 15 + b 433 x 12 + b 199 x 9 + b 924 x 6 + b 1007 x 3 +1 62

PAGE 71

3.2.3SearchesinAG,64 InAG ; 64wecompletedtwosearches,oneforhyperovalsstabilizedbythe actions, x x 2 ,and x x ,where 5 =1.Thesearchusingtheaction x x 2 gavethehyperconicandAdelaidehyperovals,aswellastheSubiacohyperovalwith automorphismgroupoforder60.Thesearchusing x x gavebothSubiaco15 andSubiaco60,theSubiacohyperovalswithautomorphismgroupsoforder15and 60respectively.Againwechoosethemostappealing -polynomialstopresent.For Subiaco15welet beaprimitiveelementofGFsatisfying 4 = +1.Since Subiaco15hasa -polynomialwithcoecientsoverGF16weseeagainthatthe necessaryconditionofCorollary2.18isalsosucientfortheknownhyperovalsin thisplane. Table3.5: -polynomialsforhyperovalsinAG ; 64 Hyperoval -polynomial Hyperconic 1 Adelaide x 63 + x 62 + x 60 + x 59 + x 58 + x 57 + x 49 + x 35 + x 33 + x 32 + x 30 + x 16 + x 8 + x 7 + x 6 + x 5 + x 3 + x 2 +1 Subiaco15 x 60 + 11 x 55 + x 50 + 7 x 45 + 2 x 40 + 7 x 35 + 13 x 30 + 8 x 25 + 13 x 20 + 4 x 15 + 14 x 10 + 4 x 5 + 10 Subiaco60 x 60 + x 50 + x 45 + x 35 + x 30 + x 20 + x 15 + x 5 +1 3.2.4SearchesinAG,128 InAG,128weperformedtwosearches,oneforhyperovalsstabilizedby x x 2 ,andoneforhyperovalsstabilizedby x x 4 .Thesearchusing x x 2 found thehyperconic,translations,Payne,andSubiacohyperovals,wherethesearchusing 63

PAGE 72

x x 4 foundtheSegre,Cherowitzo,andGlynnIIhyperovals.Theseareallknown hyperovalscontainedinthisplane.Wementionyetagainthatthenecessarycondition fromCorollary2.18isalsosucient. Weattemptedtodoabacktracksearchforhyperovalsstabilizedbytheaction x !x where 3 =1,howeverthissearchisfartobigtocomplete.Weplantogive seriousconsiderationtothissearchinthefuture. 3.2.5SearchesinAG,256 InAG ; 256wecompletedonesearchforhyperovalsstabilizedbythemap x x 2 .Thesearchyieldedallknownhyperovalsintheplane,whicharethehyperconic, translation,Adelaide,andSubiacohyperovals.Yetagain,wepointoutthatthe necessaryconditionofCorollary2.18isalsosucienthere.The -polynomialsof thesehyperovalsaregiveninTable3.8.Werepresenttheminrationalfunctionform forspaceconsiderations. Partialsearcheshavebeencompletedwiththeaction x x 4 andtheearlyresults givenonewfamiliesofhyperovals.Weattemptedtoshortentheestimatedfullsearch timeof240weeksbyreducingviathesymmetriesofthegraphthatiscreatedin CliqueFinder.Itappearsthatthesesymmetriesdonotinducecollineationsand hencegrouptogethercliquesthatshouldnotbeassociated.Thusoursearchhereis notyetcomplete.The240weeksisrealizablewithparallelcomputing,butthishas notyetbeenimplemented.Weplantonishthesearchunderthisactionandhope tocontinuethesearchinthisplaneforhyperovalsstabilizedby x x 16 .However, newtechniquesmaybeneededtocompletethissearch. 64

PAGE 73

Table3.6: -polynomialsforhyperovalsinAG ; 128 Hyperconic 1 Translationt 4 x 120 + x 119 + x 110 + x 109 + x 100 + x 99 + x 90 + x 89 + x 80 + x 79 + x 70 + x 69 + x 60 + x 59 + x 50 + x 49 + x 40 + x 39 + x 30 + x 29 + x 20 + x 19 + x 10 + x 9 +1 Segre x 126 + x 125 + !x 123 + x 122 + !x 121 + 2 x 120 + x 119 + 2 x 118 + x 117 + x 116 + x 115 + !x 114 + 2 x 112 + 2 x 111 + x 110 + 2 x 108 + 2 x 107 + x 106 + !x 103 + 2 x 102 + x 101 + x 99 + 2 x 97 + !x 96 + x 95 + x 94 + 2 x 92 + x 91 + x 90 + x 89 + !x 87 + 2 x 85 + !x 84 + 2 x 82 + !x 81 + x 80 + x 79 + !x 78 + !x 77 + 2 x 76 + x 75 + 2 x 74 + !x 71 + 2 x 70 + 2 x 69 + 2 x 68 + 2 x 67 + x 66 + x 63 + !x 62 + !x 61 + !x 60 + !x 59 + 2 x 58 + !x 55 + x 54 + !x 53 + 2 x 52 + 2 x 51 + x 50 + x 49 + 2 x 48 + !x 47 + 2 x 45 + !x 44 + 2 x 42 + x 40 + x 39 + x 38 + !x 37 + x 35 + x 34 + 2 x 33 + !x 32 + x 30 + x 28 + !x 27 + 2 x 26 + x 23 + !x 22 + !x 21 + x 19 + !x 18 + !x 17 + 2 x 15 + x 14 + x 13 + x 12 + !x 11 + x 10 + !x 9 + 2 x 8 + x 7 + 2 x 6 + x 4 + x 3 +1 Subiaco x 127 + x 126 + x 124 + x 122 + x 121 + x 117 + x 116 + x 115 + x 114 + x 113 + x 112 + x 110 + x 109 + x 108 + x 107 + x 106 + x 105 + x 101 + x 100 + x 98 + x 96 + x 95 + x 93 + x 91 + x 90 + x 86 + x 85 + x 84 + x 83 + x 82 + x 81 + x 79 + x 78 + x 77 + x 76 + x 75 + x 74 + x 70 + x 69 + x 67 + x 65 + x 64 + x 62 + x 60 + x 59 + x 55 + x 54 + x 53 + x 52 + x 51 + x 50 + x 48 + x 47 + x 46 + x 45 + x 44 + x 43 + x 39 + x 38 + x 36 + x 34 + x 33 + x 31 + x 29 + x 28 + x 24 + x 23 + x 22 + x 21 + x 20 + x 19 + x 17 + x 16 + x 15 + x 14 + x 13 + x 12 + x 8 + x 7 + x 5 + x 3 + x 2 +1 65

PAGE 74

Table3.7: -polynomialsforhyperovalsinAG ; 128 Translationt 8 x 123 + x 122 + x 116 + x 115 + x 109 + x 108 + x 102 + x 101 + x 96 + x 95 + x 89 + x 88 + x 82 + x 81 + x 75 + x 74 + x 68 + x 67 + x 62 + x 61 + x 55 + x 54 + x 48 + x 47 + x 41 + x 40 + x 34 + x 33 + x 28 + x 27 + x 21 + x 20 + x 14 + x 13 + x 7 + x 6 +1 Payne x 126 + x 123 + x 121 + x 120 + x 118 + x 115 + x 112 + x 109 + x 107 + x 106 + x 105 + x 104 + x 102 + x 101 + x 98 + x 95 + x 93 + x 92 + x 90 + x 89 + x 87 + x 86 + x 85 + x 84 + x 83 + x 82 + x 80 + x 73 + x 70 + x 67 + x 65 + x 64 + x 62 + x 59 + x 56 + x 49 + x 47 + x 46 + x 45 + x 44 + x 43 + x 42 + x 40 + x 39 + x 37 + x 36 + x 34 + x 31 + x 28 + x 27 + x 25 + x 24 + x 23 + x 22 + x 20 + x 17 + x 14 + x 11 + x 9 + x 8 + x 6 + x 3 +1 Cherowitzo x 123 + 2 x 120 + 2 x 119 + x 118 + 2 x 117 + x 116 + !x 115 + 2 x 114 + !x 112 + x 111 + 2 x 109 + x 108 + x 107 + x 106 + x 104 + 2 x 102 + x 101 + !x 100 + !x 99 + !x 98 + 2 x 93 + x 91 + !x 90 + 2 x 87 + !x 86 + x 85 + x 84 + !x 83 + 2 x 82 + 2 x 80 + !x 79 + !x 78 + 2 x 77 + !x 76 + x 75 + x 72 + !x 71 + !x 69 + !x 68 + x 66 + !x 65 + 2 x 64 + x 63 + 2 x 61 + 2 x 60 + 2 x 58 + x 57 + x 54 + 2 x 53 + !x 52 + 2 x 51 + 2 x 50 + !x 49 + !x 47 + 2 x 46 + x 45 + x 44 + 2 x 43 + !x 42 + 2 x 39 + x 38 + !x 36 + 2 x 31 + 2 x 30 + 2 x 29 + x 28 + !x 27 + x 25 + x 23 + x 22 + x 21 + !x 20 + x 18 + 2 x 17 + !x 15 + 2 x 14 + x 13 + !x 12 + x 11 + !x 10 + !x 9 + x 6 +1 GlynnII !x 126 + 2 x 123 + x 120 + 2 x 117 + 2 x 114 + x 111 + !x 108 + !x 105 + !x 102 + x 96 + 2 x 90 + 2 x 87 + !x 81 + 2 x 72 + 2 x 69 + x 66 + x 63 + !x 60 + !x 57 + 2 x 48 + !x 42 + !x 39 + x 33 + 2 x 27 + 2 x 24 + 2 x 21 + x 18 + !x 15 + !x 12 + x 9 + !x 6 + 2 x 3 +1 66

PAGE 75

Table3.8: -polynomialsforhyperovalsinAG ; 256 Hyperoval -polynomial Hyperconic 1 Translationt 8 x +1 16 x x 14 +1 Adelaide x x 1 = 3 +1 3 x +1 3 Subiaco x 5 x 10 + x 6 + x 5 + x 4 +1 3.2.6SearchesinAG,512 InAG ; 512wecompletedonesearchforhyperovalsstabilizedbytheaction x x 2 .Thesearchyielded10hyperovals,2eachofthehyperconic,translations, Payne,andSubiacohyperovals.Thesewerepreciselytheonesweexpectedtond, thatis,thosewhoseautomorphismgroupisdivisibleby18=2 h .Othersearches havenotbeencompletedinthisplaneduetothelargesearchtimerequired.Wegive thePayne -polynomialsasitistheonlyfamilyaboveforwhichwehavenotyet providedannice -polynomialrepresentation. 67

PAGE 76

Payne: Thepolynomial g x isgivenand x =1+ g x + g x q g x = x 255 + x 253 + x 252 + x 251 + x 248 + x 247 + x 243 + x 241 + x 240 + x 238 + x 236 + x 234 + x 233 + x 232 + x 231 + x 229 + x 227 + x 225 + x 224 + x 223 + x 221 + x 219 + x 217 + x 215 + x 214 + x 213 + x 212 + x 211 + x 210 + x 207 + x 206 + x 202 + x 198 + x 196 + x 193 + x 191 + x 190 + x 188 + x 180 + x 179 + x 178 + x 177 + x 168 + x 161 + x 153 + x 152 + x 150 + x 148 + x 146 + x 144 + x 142 + x 140 + x 139 + x 138 + x 137 + x 135 + x 134 + x 131 + x 129 + x 128 + x 127 + x 124 + x 123 + x 122 + x 121 + x 119 + x 117 + x 112 + x 111 + x 110 + x 109 + x 108 + x 106 + x 103 + x 102 + x 99 + x 95 + x 90 + x 84 + x 83 + x 82 + x 81 + x 80 + x 79 + x 78 + x 77 + x 75 + x 73 + x 71 + x 69 + x 68 + x 64 + x 63 + x 61 + x 60 + x 59 + x 58 + x 57 + x 55 + x 53 + x 52 + x 45 + x 44 + x 43 + x 41 + x 39 + x 38 + x 37 + x 36 + x 35 + x 32 + x 31 + x 29 + x 28 + x 27 + x 22 + x 21 + x 20 + x 18 + x 17 + x 14 + x 13 + x 12 + x 10 + x 7 + x 5 + x 4 + x 3 g x = x 256 + x 255 + x 254 + x 252 + x 249 + x 247 + x 246 + x 244 + x 239 + x 237 + x 236 + x 234 + x 233 + x 231 + x 230 + x 229 + x 228 + x 227 + x 226 + x 224 + x 221 + x 219 + x 218 + x 217 + x 216 + x 214 + x 213 + x 210 + x 207 + x 204 + x 203 + x 201 + x 200 + x 199 + x 198 + x 196 + x 193 + x 191 + x 190 + x 188 + x 183 + x 180 + x 179 + x 177 + x 176 + x 174 + x 173 + x 170 + x 165 + x 163 + x 162 + x 160 + x 153 + x 150 + x 147 + x 145 + x 144 + x 143 + x 142 + x 140 + x 137 + x 135 + x 134 + x 132 + x 127 + x 125 + x 124 + x 122 + x 121 + x 119 + x 118 + x 117 + x 116 + x 115 + x 114 + x 112 + x 105 + x 102 + x 99 + x 97 + x 96 + x 94 + x 93 + x 90 + x 85 + x 83 + x 82 + x 80 + x 79 + x 77 + x 76 + x 74 + x 71 + x 69 + x 68 + x 66 + x 65 + x 63 + x 62 + x 61 + x 60 + x 59 + x 58 + x 56 + x 55 + x 53 + x 52 + x 50 + x 45 + x 43 + x 42 + x 40 + x 37 + x 35 + x 34 + x 33 + x 32 + x 31 + x 30 + x 28 + x 25 + x 23 + x 22 + x 20 + x 15 + x 13 + x 12 + x 10 + x 9 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 68

PAGE 77

4.StructuresrepresentedbyCyclotomicSets Thischapterisdevotedtostructuresthatappearascyclotomicsets.While investigatingthe -polynomialrepresentationofhyperovalsweobservedthatseveral non-arcstructuresappearedascyclotomicsetsincludinglines,setsoflines,andgrids, aswellasmanytypesofcongurations,whichwewillenumeratelater.Webeginwith theformaldenitionofatypeofconguration. Denition1 An n r ;v k congurationisapointlineincidencestructureconsisting of n pointsand v lineswiththefollowingproperties: 1.Eachpointisincidencewith r lines. 2.Eachlineisincidentwith k points. 3.Twodistinctlinesintersectinatmostonepointandtwopointsareconnected byatmostoneline. When v = n ,andconsequently r = k ,werefertoan n r ;v k congurationasan n k conguration.Wesayan n k congurationiscyclicifthereisanautomorphismof thecongurationthatpermutesthepointsinasinglecycle.Itisnaturaltoidentify thepointsofacyclic n k congurationwith Z n andassumethattheautomorphismis x x +1.ClassicalexamplesofcycliccongurationsaretheDesarguesianprojective planes,whichareexamplesofcyclic q 2 + q +1 q +1 conguations.Itisclearthat theyarecongurationsandawellknowntheoremofSinger[49]showsthatthe Desarguesianprojectiveplanesarecyclic.Singer'stheoremisoftenusedinthestudy ofDesarguesianprojectiveplanes,anditisstillanopenquestionastowhetheror notthetheoremcharacterizeswhenagivenprojectiveplaneisDesarguesian. Wefocusourattentiononcyclic n 3 congurations.Inanycyclic n 3 conguration thelineshavetheform f j;j + a;j + b g for j 2 Z n and a
PAGE 78

eachsuch n acyclic n 3 congurationexists.Infact,thegeneratingblock[0 ; 1 ; 3]will generatean n 3 congurationforeach n 7[20].TheDesarguesianprojectiveplane oforder2,seeninFigure4.1,isanexampleofacyclic n 3 conguration;itisthe unique C 3 [7 ; 1 ; 3]. Acongurationis polycyclic ifthereexistsanautomorphismoftheconguration whereallorbitsonpointsandlinesareofthesamesize.Thisisageneralizationof thecycliccongurationsdescribedabove.See[5]formoreinformationonpolycyclic congurations.Apolycyclicgeneralizationofcyclic n k congurationswhicharises naturallyisan n ks ; ns k conguration.Wesayan n ks ; ns k congurationisan s n k conguration ifthereexistsanautomorphismofthecongurationofwhicheach orbitisacyclic n k conguration.Observethata1n k congurationissimplyacyclic n k congurationaspreviouslydescribed. Figure4.1:PG,2:TheFanoPlane In[28]Leviprovedthat C 3 [ n; 1 ;b ]isacongurationfor3 b n )]TJ/F15 11.9552 Tf 13.108 0 Td [(2and b 62f n +1 2 ; n 2 ; n 2 +1 g .Morerecently,in[27],Koike,Kovacs,andPisanskicountthe numberofnon-isomorphiccyclic n 3 congurations,andgiveconditionsforcyclic n 3 congurationstobeisomorphic.Thequestionwewouldliketoansweris:Forwhich n a b is C 3 [ n;a;b ]acyclic n 3 conguration?AccordingtoGrunbaumthisquestion isstillopenandworthsolving.[21] Insection4.1wecharacterizethegeneratingblocksfor C 3 [ n;a;b ].Thisisan 70

PAGE 79

interestingquestioninitsownright,butalsocanbeusedtohelpusgivenecessary andsucientconditionsforwhenacyclotomicsetcontainsan s n k conguration. Insection4.2wedescribethestructuresknowntoberepresentedbycyclotomicsets andgivesomenecessaryandsucientconditionsforwhenacyclotomicsetrepresents eachstructure. 4.1DeterminingGeneratingBlocks Westudythe C 3 [ n;a;b ]viatheirincidencematrices,0-1matriceswithcolumns indexedbythepointsandrowsindexedbythelines,wherea1indicatesincidence. Observethatintheincidencematrixof C 3 [7 ; 1 ; 3],seeninFigure4.2,ifthereare1's inpositions `;s and `;t then ` istheuniquerowforwhichthisistrue.Ifthe incidencematrixofa C 3 [ n;a;b ]has J 2 ,the2 2matrixofall1's,asasubmatrix, thenonesaysthatthematrixhasanembedded J 2 .In[28]Leviobservedthatthe existenceofembedded J 2 'sisenoughtodeterminewhetherornotacirculantmatrixis theincidencematrixofacyclic n k conguration.In[27],Koike,Kovacs,andPisanski formalizethisobservation.Weprovideaformalproofforconvenience. 0 B B B B B B B B B B B B B B B B B @ 0123456 ` 0 1101000 ` 1 0110100 ` 2 0011010 ` 3 0001101 ` 4 1000110 ` 5 0100011 ` 6 1010001 1 C C C C C C C C C C C C C C C C C A Figure4.2:Incidencematrixfor C 3 [7 ; 1 ; 3] 71

PAGE 80

Lemma4.1 Acirculant,1-matrixgeneratedby k 1'sintherstrowistheincidencematrixofan n k congurationifandonlyifithasnoembedded J 2 Proof: Thisconditionisclearlynecessarysincetheexistenceofanembedded J 2 forcestheretobetwolinesthroughtwopoints.Fortheconverse,assumethat wehaveacirculantmatrix C ,generatedbyarowwith k 1's,andnoembedded J 2 Sincethesumofrow0is k and C iscirculant,wemusthavethateveryrowand columnsumis k .Hencethereare k linesthrougheverypoint,and k pointsonevery line.Theabsenceofembedded J 2 'sforcesthethirdcondition,thattwodistinctlines intersectinatmostonepointandtwodistinctpointsareconnectedbyatmostone line.Hence, C istheincidencematrixofan n k conguration. Wespecializethisresulttothecase k =3inordertoanswerthequestionposed byGrunbaum.Throughoutwewillbeassuming a
PAGE 81

Fortheconverse,assumethatthequantitiesarenotdistinct.Sinceweareassumingthat a and b aredistinct,andbotharedierentfrom0,thepossibilitiesfor equivalentquantitiesmodulo n are: a )]TJ/F18 11.9552 Tf 21.918 0 Td [(a a )]TJ/F18 11.9552 Tf 21.918 0 Td [(b a b )]TJ/F18 11.9552 Tf 11.955 0 Td [(a )]TJ/F18 11.9552 Tf 21.129 0 Td [(a b )]TJ/F18 11.9552 Tf 21.129 0 Td [(a a )]TJ/F18 11.9552 Tf 11.955 0 Td [(b b )]TJ/F18 11.9552 Tf 21.918 0 Td [(b b a )]TJ/F18 11.9552 Tf 11.955 0 Td [(b )]TJ/F18 11.9552 Tf 21.129 0 Td [(b b )]TJ/F18 11.9552 Tf 11.955 0 Td [(a b )]TJ/F18 11.9552 Tf 11.955 0 Td [(a a )]TJ/F18 11.9552 Tf 11.955 0 Td [(b Thisreducestothefollowingfourcases: 1. a = n 2 or b = n 2 2. a + b 0 3. b 2 a or a 2 b 4. b )]TJ/F18 11.9552 Tf 11.955 0 Td [(a n 2 Wewillexamineeachcase. Case1: AssumeWLOGthat a = n 2 .Thegeneratingblockis[0 ; n 2 ;b ]andsothe 1'sinrow0intheincidencematrixarelocatedinpositions ; 0 ; ; n 2 ; ;b ,andin row n 2 the1'sareinpositions n 2 ; n 2 ; n 2 ; 0 ; n 2 ;b + n 2 .Thus ; 0 ; ; n 2 ; n 2 ; 0 ; n 2 ; n 2 isanembedded J 2 Case2: Assumethat a + b 0mod n .Thisforcesthegeneratingblocktobe [0 ;a;n )]TJ/F18 11.9552 Tf 12.09 0 Td [(a ],andthe1'sinrow a arelocatedinpositions a;a ; a; 2 a ; a; 0.Hence ; 0 ; ;a ; a; 0 ; a;a isanembedded J 2 Case3: AssumeWLOGthat b 2 a mod n sothatthegeneratingblockis [0 ;a; 2 a ].Ifweshifttheblockby )]TJ/F18 11.9552 Tf 9.298 0 Td [(a weget[ )]TJ/F18 11.9552 Tf 9.299 0 Td [(a; 0 ;a ]asanequivalentgenerating block,withthesumofthenon-zeropositionsequivalentto0mod n ,andwecan reducetoCase2. 73

PAGE 82

Case4: Assumethat b )]TJ/F18 11.9552 Tf 12.331 0 Td [(a n 2 mod n .Thisforcesthegeneratingblockto be[0 ;a;a + n 2 ].Inrow n 2 the1'sareinpositions n 2 ; n 2 ; n 2 ;a + n 2 ; n 2 ;a andthuswe see ;a ; ;a + n 2 ; n 2 ;a ; n 2 ;a + n 2 isanembedded J 2 Hencewehavefoundanembedded J 2 ineachcase. InordertostatethisresultinamannersimilartoLevi,wemustonlyrealizethat given a ,wecanalwayschoose b intherange2 a
PAGE 83

Observation1 Thereexistsacyclotomicsetofsize c inGF 2 2 h ifandonlyif c j 2 h .For : x x 2 jC j = c ifandonlyif 2 GF 2 c butinnoproper subeldsofGF 2 c Observation2 For : x x 2 ,and : x x 2 e wehave jC j = jC j e; jC j : Wenowdescribewhenacyclotomicsetofsize c isacollectionofdisjointline segments,whicharesubsetsofpointsonaline.Weusethenotation j j todenote theorderof inGF q 2 Theorem4.4 If C ,with jC j = c ,and 6 =0 ,consistsofexactly m disjoint linesegmentsthenthelinesegmentsare ` j = f j ; m + j ; 2 m + j ;:::; dm + j g ; where d = c m )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 ; and 0 j m )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 .Wecallthisasetof m -regularlinesegments. Proof: Assumethat C consistsofexactly m disjointlinesegmentsand let jC j = c sothattheorderof2 e mod j j is c .Firstobservethatif ` is alinesegment,then ` isalinesegmentwiththesamelengthbyCorollary2.7. Since C isanorbitwewillexhaustallofitselementsbyrepeatedlyapplying ,sothedisjointlinesegmentsmusthavethesamesize.Letthelinesegmentsbe ` 0 ;` 1 ;:::;` m )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 .AssumeWLOGthat 2 ` 0 .Let u =min f s : s 2 ` 0 g)-274(f 0 g v =min f s : s 2 ` 0 g)-239(f 0 ;u g ,andcall ; u ; v theminimaltriplein ` 0 .We wanttoshow u = m and v =2 m .Sincethe ` j aredisjointweknowthat u and v cannotbeonanylinesotherthan ` 0 .Thus,anycollineartriplein C containing anyof u ,or v mustbeatriplethatlieson ` 0 .Now,weknowthattriplesof theform s ; u + s ; v + s mustbecollinearbyCorollary2.7. Considerthetriple u ; 2 u ; u + v achievedbyapplyingtheautomorphism u totheminimaltriplein ` 0 .Thismustbeacollineartriple,andsothesepointsmust 75

PAGE 84

beon ` 0 .Hence, v 2 u bythedenitionof v ,since 2 u lieson ` 0 .Now,assume that v< 2 u andlet z = v )]TJ/F18 11.9552 Tf 11.391 0 Td [(u andnote z
PAGE 85

sarilywehavethatthepoints ; m ; 2 m arecollinear.Consequently, q + m q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 = q m + 2 m q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 : Thus, + m q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 =[ + m q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 ] m putting + m q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 2 GF t asdesired. Fortheconverse,assumethat + m q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 2 GF t andlet + m q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 = z 2 sothat z q )]TJ/F16 7.9701 Tf 6.586 0 Td [(1 = 1 z 2 and z m = z .Theseobservationsshowthat z + z m q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 =1, hence, T z 2 GF t .Thus T z = T z ms for1 s c m )]TJ/F15 11.9552 Tf 10.478 0 Td [(1andsothepoints ; m ; 2 m ;:::; c m )]TJ/F17 5.9776 Tf 5.756 0 Td [(1 m arecollinear.Applying theautomorphisms j for1 j m )]TJ/F15 11.9552 Tf 11.955 0 Td [(1producesthe m -regularlinesegments. Whenstudyingcyclotomicsetsitisoftenconvenienttotalkaboutthepositions ofelementsbyimposinganorderontheset.Sinceeachelementistheimageofthe generator undersomepoweroftheautomorphism ,wewillrefertotheelement j astheelementinthe j th position.Thefollowinglemmaisofconsiderableusein describingwhencyclotomicsetscanbedierentstructures. Lemma4.6 The 0 ;a;b positionsof C arecollinearifandonlyif isarootof thepolynomialfunction p a;b; : GF q 2 GF q 2 where p a;b; x = Y 2 GF q x a + x b + +1 x Proof: ByCorollary2.4weknowthatthepoints a ,and b arecollinear ifandonlyif q + a q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 = q + b q )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 ; whichistrueifandonlyifthereexistssome 2 GF q forwhich + a = + b ; 77

PAGE 86

fromwhichtheresultfollows. Wecannowdescribewhenacyclotomicsetisanarc.Wenotethatifacyclotomic setisanarcthenitnecessarilyhasnocollineartriples.UsingLemma4.6wedenea polynomialwhoserootsarealloftheelementsthatgenerateacyclotomicsetwithat leastonecollineartriple.Let S = fjC j : 2 GF q 2 g and n =max f x : x 2 S g Wedene f x = Y 1 a< n 2 a +1 b n )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 p a;b; x Observethatif C hasacollineartriplethenwemayassumethat isincluded inacollineartriple,bythecyclicnatureof C .Additionally,wemayassumethat themiddlepositionofthecollineartripleliesbetween1and n 2 sinceotherwisewe mayuseacyclicshifttoproduceacollineartriplewiththisproperty.Thisproves thefollowingcorollary. Corollary4.7 C isanarcifandonlyif isarootofthepolynomial A x = x q 2 + x GCD f x ;x q 2 + x : Wecannowgivenecessaryconditionsforwhenacyclotomicsetcouldbean s n k conguration.Observethat[0 ;t 1 ;t 2 ;:::;t k )]TJ/F16 7.9701 Tf 6.587 0 Td [(1 ]isageneratingblockforacyclic n k congurationifandonlyif[ t i ;t j ;t ` ]isageneratingblockforacyclic n 3 conguration foranychoicesof i;j;` with i 6 = j 6 = ` .RecallfromTheorem4.2thatweidentied theproblemcasesforthecollineartriple[0 ;a;b ]togenerateacyclic n 3 conguration. Wedenethefollowingset B a;c = f b 2 Z c : b = c 2 ;a + b 0 ;b 2 a;b )]TJ/F18 11.9552 Tf 11.956 0 Td [(a c 2 g Weusethissettodescribe s n k congurations,aswedidarcsinCorollary4.7,sowe denethefollowingpolynomial, g x = Y c 2S Y 1 a< c 2 b 2B a p a;b; x : 78

PAGE 87

Inorderforan s n k congurationtoexistwehavetoensurethatonlyappropriate collineartriplesexist.Byeliminatingtheelementsthatgeneratecyclotomicarcs,as wellasthetriplesthatfailtogenerateacyclic n 3 congurationweisolatethe C thatcouldbe s n k congurations.Thepolynomial AC x = x q 2 + x GCD g x ;x q 2 + x hasrootsthatgenerateacyclotomicsetthatisanarc,oracongurationwiththe appropriatecollinearities.Hence,Corollary4.7allowsustogivenecessaryconditions forwhen C couldbean s n k conguration. Corollary4.8 C isan s n k congurationifandonlyif isarootofthepolynomial C x = AC x GCD AC x ;A x : 4.3Examples Weconcludewithsomeexamplesfromsmallplanes.Thefollowingexamplesare notexhaustivebutratherarechosentogivethereaderafeelforwhatexists.We givetheminimalpolynomialsforGF q 2 andnotethattheelementsofGF q are identiedaselementsoftheform q +1 j for0 j q )]TJ/F15 11.9552 Tf 12.405 0 Td [(2,where generatesthe multiplicativegroupofGF q 2 .Ineachoftheremainingexamplesthecyclotomic setsareformedundertheautomorphism : x x 2 4.3.1AG,16 TherearefourcyclotomicsetsinAG,16thataretheMobius-Kantorconguration.ThesearetheonlycongurationsfoundascyclotomicsetsinAG,16.The congurationpolynomial, N 3 x ,forthesecongurationsisshownbelowwherewe constructGFwithminimalpolynomial x 8 + x 4 + x 3 + x 2 +1.Eachfactorin thegivenfactorizationbelowisapolynomialwhoserootsarethepointsofasingle 79

PAGE 88

Mobius-Kantorconguration. N 3 x = x 32 + x 28 + x 26 + x 24 + x 22 + x 14 + x 12 + x 9 + x 4 + x 3 + x 2 + x +1 = x 8 + x 7 + x 6 + x 5 + x 2 + x +1 x 8 + x 7 + x 5 + x 3 +1 x 8 + x 7 + x 6 + x +1 x 8 + x 7 + x 4 + x 3 + x 2 + x +1 Forinstance,therootsof x 8 + x 7 + x 6 + x 5 + x 2 + x +1areelements 11 ; 22 ; 44 ; 88 ; 176 ; 97 ; 194 ; 133 2 GF q 2 : TheMobius-KantorcongurationinFigure4.3haspointslabeledwiththeseroots, showingtheappropriatecollinearities. 97 11 88 22 176 133 194 44 Figure4.3: C 3 [8 ; 1 ; 3]:AMobius-KantorcongurationfoundinAG,16 4.3.2AG,64 InAG,64wendinstancesofcyclotomicsetsthataregrids,aswellascyclotomicsetsthatareacongurationwithaparallelism.Thereare8instancesof the4 3grid,36cyclic12 3 congurations,and12instancesof 4 ; 16 3 congurationsthatconsistofa12 3 congurationwitha4-regularparallelism.Weconstruct GFwiththeminimalpolynomial x 12 + x 7 + x 6 + x 5 + x 3 + x +1.Therootsof thepolynomial x 12 + x 8 + x 6 + x 5 + x 3 + x 2 +1 80

PAGE 89

formacyclotomicsetthatisthe4 3grid.The12 3 congurationsappearwithmany dierentgeneratingblocks,oneofwhichis[0 ; 1 ; 3].Therootsofthepolynomial x 12 + x 11 + x 10 + x 9 + x 5 + x 3 + x 2 + x +1 formacyclotomicsetthatisa C 3 [12 ; 1 ; 3],andFigure4.4ashowsarealizationofthis conguration. Twoofthe 4 ; 16 3 congurationsthatconsistofa12 3 congurationwitha4regularparallelism,havea C 3 [12 ; 1 ; 3]asitsunderlyingcyclic12 3 conguration.The rootsofthefollowingpolynomialgiveacyclotomicsetthatisthisconguration.A realizationisgiveninFigure4.4b. x 12 + x 9 + x 8 + x 6 + x 5 + x 4 +1 a C 3 [12 ; 1 ; 3] b C 3 [12 ; 1 ; 3]withparallelismdashed Figure4.4:CongurationsfoundascyclotomicsetsinAG,64 4.3.3AG,256andLargerPlanes TheaneplaneAG,256isthesmallestplaneinwhichwendan s n 3 congurationfor s> 1.Thereare16instancesofcyclotomicsetsthatarea2-16 3 conguration.WeconstructGF 16 withtheminimalpolynomial x 16 + x 5 + x 3 + x 2 +1. 81

PAGE 90

Therootsofthepolynomial x 16 + x 10 + x 9 + x 7 + x 6 + x +1 area2-16 3 conguration.Itdecomposesintoa C 3 [16 ; 1 ; 5]anda C 3 [16 ; 3 ; 10].Inlarger planeswealsond s n 3 congurations,includingsomewithanadditionalparallelism. InAG,512therearecyclotomicsetsthatare 7 ; 42 3 congurations.Thiscongurationhasa6-regularparallelism,andremovingitproducesa2-18 3 conguration. InAG,1024thereare64cyclotomicsetsthatare2-20 3 congurations,and4cyclotomicsetsthatare20 4 congurations.InAG,2048thereare12cyclotomicsets thatare3-22 3 congurations,andinAG,4096therearecyclotomicsetsthatare n 4 congurations,somewithaparallelism. 4.4OpenQuestions Inadditiontothequestionsalreadymentioned,thisworkleadsustothefollowing openproblemsaboutcyclotomicsets. 1.Arethereanyotherstructuresthatcanberepresentedbycyclotomicsets? 2.Isthereabetterdescriptionofcyclotomicarcsthatisnotbyexclusion? 3.Isthereanalgebraicdescription,perhapssomeconditionson and ,that identieswhentheunionoftwocyclotomicarcsisanarc?Suchadescription wouldhelpinthesearchfornewhyperovalsasdescribedinChapter3. 82

PAGE 91

REFERENCES [1]Ball,S. Polynomialsinnitegeometries. Surveysincombinatorics,1999Canterbury,17{35,LondonMath.Soc.LectureNoteSer.,267,CambridgeUniv. Press,Cambridge,1999. [2]Bartocci,U.,Segre,B. OvaliedaltrecurveneipianidiGaloisdicaratteristica due. ActaArithmetica,971, 18 :423{449. [3]Betten,A. Orbiter-AProgramtoClassifyDiscreteObjects. http://www.math. colostate.edu/ ~ betten/orbiter/orbiter.html [4]Beutelspacher,A.,Rosenbaum,U. Projectivegeometry:fromfoundationstoapplications. CambridgeUniversityPress,Cambridge,1998. [5]Boben,M.,Pisanski,T. Polycycliccongurations. EuropeanJ.Combin. 24 ,no.4,431{457. [6]WiebBosma,JohnCannon,andCatherinePlayoust. TheMagmaalgebrasystem. I.Theuserlanguage ,J.SymbolicComput., 24 ,235{265. [7]Brown,J.,Cherowitzo,W. TheLunelli-ScehyperovalinPG,16. J.Geom. 69 ,no.1{2,15{36. [8]Cardinali,I.,Payne,S.E. q -clangeometriesincharacteristic2. Frontiersin Mathematics.BirkhauserVerlag,Basel,2007. [9]Casse,Rey Projectivegeometry:anintroduction. OxfordUniversityPress,Oxford,2006. [10]Cherowitzo,W. -ocksandhyperovals. Geom.Dedicata 72 ,,:221{ 246. [11]Cherowtizo,W. HyperovalsinDesarguesianplanesofevenorder AnnalsDisc. Math. 37 87{94. [12]Cherowitzo,W. HyperovalsinDesarguesianplanes:anupdate. Combinatorics Acireale,1992.DiscreteMath. 155 ,no.1-3,31{38. [13]Cherowitzo,W.E.,Payne,S.E. Thecyclic q -clanswith q =2 e AdvancesinGeometry,SpecialIssue2003S158{S185. [14]Cherowitzo,W.E.,O'KeefeC.M.,Penttila,T. Auniedconstructionofnite geometriesassociatedwith q -clansincharacteristic2 Adv.Geom. 3 ,1{ 21. 83

PAGE 92

[15]Cherowitzo,W.,Penttila,T.,Pinneri,I.,Royle,G.F. Flocksandovals. Geom. Dedicata60,no.1,17{37. [16]Cherowtizo,W.E.,Storme,L. -FlockswithOvalHerdsandMonomialHyperovals FiniteFieldsandtheirApplications 4 ,185{199. [17]Fisher,J.C.,Schmidt,B. FiniteFourierseriesandovalsinPG 2 ; 2 h J.Aust. Math.Soc. 81 ,no.1,21{34. [18]Glynn,D. AconditionfortheexistenceofovalsinPG 2 ;q ,qeven. Geometria Dedicata 32 ,247{252. [19]Glynn,D. TwonewsequencesofovalsinniteDesarguesianplanesofeven order. Combinatorialmathematics,XLectureNotesinMath.1036,Berlin: Springer,,pp.217{229. [20]Grunbaum,B. CongurationsofPointsandLines .AmericanMathematicalSociety,RhodeIsland,2009. [21]Grunbaum,B.PersonalCommunication,April2014. [22]Hall,M.,Jr. OvalsintheDesarguesianplaneoforder16. Ann.Mat.PuraAppl. 102 ,159{176. [23]Hernando,F.,McGuire,G. ProofofaconjectureofSegreandBartoccionmonomialhyperovalsinprojectiveplanes. Des.CodesCryptogr. 65 ,no.3, 275{289. [24]HirschfeldJ.W.P. ProjectiveGeometriesOverFiniteFields. OxfordMathematicalMonographs.secondedition.TheClarendonPressOxfordUniversityPress, NewYork. [25]Hughes,D.R.andPiper,F.C. ProjectivePlanes .Springer-VerlagNewYork,1973. [26]Jamison,R. Coveringniteeldswithcosetsofsubspaces ,JournalofCombinatorialTheory,SeriesA, 22 ,253{266. [27]Koike,H.,Kovacs,I.Pisanski,T. Thenumberofcycliccongurationsoftype v 3 andtheisomorphismproblem .J.Combin.Des. 22 ,no.5,216{229. [28]Levi,F. GeometrischeKongurationen Hirzel,Leipzig,1929. [29]R.LidlandH.Niederreiter. FiniteFieldsEncyclopediaofMathematicsandits Applications. CambridgeUniversityPress,1996. [30]Lunelli,L.,Sce,M. k-archicompletineipianiproiettividesarguesianidirango8 e16 CentrodiCalcoliNumerici,PolitecnicodiMilano,1958. [31]O'Keefe,C.M.,Penttila,T. ANewHyperovalinPG,32 JournalofGeometry 44 117{139. 84

PAGE 93

[32]O'Keefe,C.M.,Penttila,T. HyperovalsinPG,16. EuropeanJ.Combin. 12 ,no.1,51{59. [33]O'Keefe,C.M.,Penttila,T. SymmetriesofArcs. J.Combin.Th.Ser.A 66 53{67. [34]O'Keefe,ChristineM.,Thas,J.A. CollineationsofSubiacoandCherowitzohyperovals. Bull.Belg.Math.Soc.SimonStevin 3 ,no.2,177{192. [35]Payne,S.E. Anewinnitefamilyofgeneralizedquadrangles. CongressusNumerantium,, 49 :115{128. [36]Payne,S.E. TopicsinFiniteGeometry:Ovals,Ovoids,andGeneralizedQuadrangles. UCDenverCourseNotes,2008. [37]Payne,S.E.,Conklin,J.E. Anunusualgeneralizedquadrangleofordersixteen. J.CombinatorialTheorySer.A 24 ,no.1,50{74. [38]Payne,S.E.,Thas,J.A. TheStabilizeroftheAdelaideOval DiscreteMathematics 294 161{173. [39]Payne,S.E.,Penttila,T.,Pinneri,I. IsomorphismsbetweenSubiacoq-clangeometries. Bull.Belg.Math.Soc.SimonStevin 2 ,no.2,197{222. [40]Penttila,T.,Pinneri,I. IrregularhyperovalsinPG,64. J.Geom. 51 no.1{2,89{100. [41]Penttila,T.Royle,G. ClassicationofhyperovalsinPG,32. J.Geom. 50 ,no.1{2,151{158. [42]Penttila,T.,Royle,G. OnHyperovalsinSmallProjectivePlanes Journalof Geometry 54 91{104. [43]Penttila,T.,Storme,L. MonomialFlocksandHerdsContainingaMonomial Oval JournalofCombinatorialTheory,SeriesA, 83 ,21{41. [44]Pisanski,T.,Servatius,B. Congurationsfromagraphicalviewpoint Birkhauser/Springer,NewYork,2013. [45]Robbins,N. BeginningNumberTheory. JonesandBartlett,Massachusetts,2006. [46]Segre,B. OvaliecurveoneipianidiGaloisdicaratteristicadue. AttiAccad. Naz.LinceiRend.Cl.Sci.Fis.Mat.Nat., 32 :785{790. [47]Segre,B. Ovalsinaniteprojectiveplane. CanadianJournalofMathematics 7 ,:414{416. [48]Segre,B. Sulleovalineipianilinearinite Rend.Accad.Naz.Lincei17, 141{142. 85

PAGE 94

[49]Singer,J. Atheoreminniteprojectivegeometryandsomeapplicationstonumbertheory .Trans.Amer.Math.Soc. 43 ,no.3,377{385. [50]Thas,J.A.,Payne,S.E.,Gevaert,H. Afamilyofovalswithfewcollineations. EuropeanJ.Combin.9,no.4,353{362. [51]Vis,TimothyL. MonomialhyperovalsinDesarguesianplanes. ThesisPh.D.{ UniversityofColoradoatDenver.2010. 86