
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00001895/00001
Material Information
 Title:
 Hyperovals and cyclotomic sets in AG(2,q)
 Creator:
 DeOrsey, Philip A. ( author )
 Place of Publication:
 Denver, CO
 Publisher:
 University of Colorado Denver
 Publication Date:
 2015
 Language:
 English
 Physical Description:
 1 electronic file (94 pages). : ;
Thesis/Dissertation Information
 Degree:
 Master's ( Master of Science)
 Degree Grantor:
 University of Colorado Denver
 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 ) nonfiction ( marcgt )
Notes
 Review:
 In this dissertation we introduce a new polynomial representation of hyperovals called a ppolynomial. The ppolynomial 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 ppolynomial linking properties of their coefficients to specific maps that stabilize the represented hypervoval. Additionally, we provide a connection between ppolynomials and opolynomials, and give nice ppolynomial 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 ppolynomial 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:
 University of Colorado Denver
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 910743439 ( OCLC )
ocn910743439

Downloads 
This item has the following downloads:

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 ppolynomial. The ppolynomial 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 ppolynomials linking properties of their coefficients to specific maps that stabilize the represented hyperoval. Additionally, we provide a connection between ppolynomials and opolynomials, and give nice ppolynomial 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 ppolynomials 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 levelheaded 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
TABLE OF CONTENTS
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 ppolynomial Representation.......................................... 14
2.1 A Description of the Polar Model .................................. 14
2.2 Collineations in the Polar Model................................... 18
2.3 Using ppolynomials to Represent Hyperovals........................ 21
2.4 Structural Properties of ppolynomials............................. 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 opolynomials.................................. 30
2.6 The ppolynomials for Known Hyperovals............................. 33
2.6.1 Hyperconic................................................... 33
2.6.2 Translation Hyperovals....................................... 41
2.6.3 The Segre Hyperoval.......................................... 45
2.6.4 The Adelaide Hyperoval....................................... 47
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 ppolynomials 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 MobiusKantor configuration found in AG(2,16)............ 80
4.4 Configurations found as cyclotomic sets in AG(2,64) 81
vii
TABLES
Table
1.1 opolynomials 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 ppolynomials for hyperovals in AG(2,16) ............................... 61
3.4 ppolynomials for hyperovals in AG(2, 32) 62
3.5 ppolynomials for hyperovals in AG(2, 64) .............................. 63
3.6 ppolynomials for hyperovals in AG(2,128)............................... 65
3.7 ppolynomials for hyperovals in AG(2,128) (2)........................... 66
3.8 ppolynomials 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 ppolynomial. The ppolynomial 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 opolynomials 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 ppolynomials.
We study the structural properties of ppolynomials 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 ppolynomials 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 ppolynomial representations for all of the known families of hyperovals in these planes. Further, we give ppolynomial 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.
We refer to [29] for more information on finite fields.
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 2dimensional projective space called a projective plane. A projective plane is a pointline 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 nonprime power order exist.
A projective plane of order q can be constructed as a 3dimensional vector space over GF(q), the finite field with q elements. The points are the 1dimensional subspaces, and the lines are the 2dimensional subspaces. Incidence is settheoretical 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 onetoone 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 nonsingular 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 karc 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 projectively 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 opolynomial. The use of opolynomials gives a compact and usable form for hyperovals, so they have been the traditional way of describing hyperovals. A representative list of opolynomials 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 LunelliSce hyperoval and can be described by the opolynomial
fit) = t12 + t10 + qllt8 + f + ift4 + ift2, where q is a primitive element of GF(16) satisfying if = ?/ + !.
Table 1.1: opolynomials for known hyperovals
Name opolynomial 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
OKeefePenttila [31] See Below y4 =
Subiaco An opolynomial 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 opolynomial
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 opolynomial 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 = ^OKeefePenttila An opolynomial for the OKeefePenttila 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 LunelliSce 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 LunelliSce 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 opolynomials. 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 gclan which has since been used often in the study of hyperovals. We will not discuss gclans here, but we refer the reader to [8] for information on gclans. 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 OKeefePenttila 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 kbit monomial hyperoval if an opolynomial for 77 is f(t) = tn and there are k ls in the binary representation for n. The 1bit monomial hyperovals are precisely the translation hyperovals. The 2bit monomial hyperovals were classified in 1998 [16], and the 3bit 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 opolynomial 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 + yyqpp, 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 opolynomial 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 onetoone 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 opolynomial 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 ppolynornial.
2.6 The ppolynomials for Known Hyperovals
While Theorem 2.24 gives a general method for finding ppolynomials 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 ppolynomial 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 ppolynomial that produces this hyperconic.
This, our first example of a ppolynomial for a hyperoval, may clearly be called elegant. Additionally, Theorem 2.25 shows that the domain of a ppolynomial is this hyperconic. Since any hyperoval has a ppolynomial representation this implies that any hyperoval is simply a perturbation of a hyperconic, where the ppolynomial describes that perturbation.
Observation 2.26 Every hyperoval is a perturbation of a hyperconic, where the perturbation is described by its ppolynomial.
We will now look at another nice representation of the hyperconic in the ppolynomial 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 ppolynomial for the hyperconic.
Theorem 2.27 In AG(2,q) the polynomial p(x) = 1 + 'ZZ'jZl is a ppolynomial 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
q1
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
TL = {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 ppolynomial 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 ppolynomial that describes a hyperconic.
The above forms describe hyperconics in AG(2, 2h) for all h. There are additional ppolynomials for hyperconics that are specific to the case when h is even. We present several different ppolynomials 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,
q1
p(x) = 1 + xj
3=2
q3
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 ppolynomial 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 ppolynomials as rational functions. The following theorems give additional ppolynomials for a hyperconic in AG(2, 2h) when h is even.
Theorem 2.29 In AG(2,2h), h even, the function
gl
3
p(x) = 1 + (x + 1)
3 = 1
X
X2 + X + 1
is a ppolynomial describing a hyperconic.
36
Proof: We begin by showing the rational function shown above is equivalent to the polynomial.
gl
3
p(x) = 1 + (x + 1) ^ ;r3t_1
i= 1
2=11 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 ppolynomicil describing a hyperconic.
Proof: Similar to the previous proof we will begin by providing a rational function equivalent to the polynomial.
q4
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(^94 + 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) = ;i3~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 ppolynomial 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 (x2 + 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 ppolynomial 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 ppolynomial 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 opolynomial 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 opolynomial 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 ) 4h (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 ppolynornial describing the translation hyperoval with opolynomial 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 ppolynomial depend on a but also the choice of 8. We give a simpler form for the ppolynomial when h is odd and also give a specific ppolynomial for the translation hyperoval with opolynomial f(t) = tA.
Corollary 2.33 In AG(2,q), with q = 2h, h odd, the following are ppolynomials that produce the translation hyperoval with opolynomial 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 ppolynomial
p(x) = xio + 1 >P(1) = 1
describes the translation hyperoval with opolynornial 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 ppolynornials that produce that translation hyperoval with opolynornial 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 ppolynomial 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 ppolynomial describing a translation hyperoval with opolynornial 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 ppolynomials that produce the translation hyperoval with opolynornial 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 opolynomial / 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 ppolynomial 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 ppolynomial 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
2.6.4 The Adelaide Hyperoval
We now present a compact ppolynomial for the Adelaide hyperoval. We generated ppolynomials 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 ppolynomial
V
Ail
where s = 2h~2 1 is a ppolynomial 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+Ds5g + 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 ppolynomial 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. (213)
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 ppolynomial 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 ppolynomial representing a Subiaco hyperoval in AG(2, q), q = 2h for all h > 1. Observe that this ppolynomial 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 opolynomial 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
=( + jz + 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 opolynomial 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 opolynomial 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 opolynomial 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 opolynomial 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 ppolynomial for a Subiaco hyperoval whose automorphism group has order divisible by 2h.
This ppolynomial 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 ppolynomial. A ppolynomial 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 ppolynomial could exist. A ppolynomial 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 ppolynomial representations. The general conversion from their opolynomial 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 opolynomials. 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 ppolynomials for hyperovals in these families, but our work up to this point has not been fruitful.
Through studying the ppolynomial representation it has become clear that some
hyperovals will be better represented as opolynomials. Many of the monomials, with
exception of the hyperconic, are more elegantly represented as opolynomials. In
fact, as we saw in Theorem 2.40 the Segre hyperoval has its simplest ppolynomial
54
representation over GF(4)! In contrast the Subiaco and Adelaide hyperovals have ppolynomial representations over GF(2), where there opolynomial counterparts do not. Additionally, we will see nice structure represented by the ppolynomial of the OKeefePenttila hyperoval that is not represented by its opolynomial. As such, the intention of the ppolynomial method is not to replace opolynomials, 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 ppolynomial 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 ppolynomials 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 ppolynomials 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 ppolynomial representation we noticed a nice property of the hyperovals that have their ppolynomials represented over subfields of GF(q2). In order to describe the structure of hyperovals whose ppolynomials 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 ppolynomial 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 ppolynomials 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 1L 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 OKeefePenttila hyperoval in [31], the first examples of the Subiaco hyperoval in [40], and helped classify hyperovals with nontrivial 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 LunelliSce 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 LunelliSce
60
ppolynomials 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 ppolynomials with coefficients over GF(2) where their opolynomial counterparts do not. The LunelliSce ppolynomial p(x) = xlA + ;r13 + ;r4 + ;r3 +1 satishes the general form for the Adelaide ppolynomial 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 ppolynomial we list all of them in their entirety.
Table 3.3: ppolynomials for hyperovals in AG(2,16)
Hyperoval ppolynomial
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
LunelliSce 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 OKeefePenttila hyperovals. These are all of the hyperovals in AG(2,32) so this list adds a complete set of ppolynomials 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 ppolynomials to show here. For the OKeefePenttila ppolynomial, b is a primitive element of GF(1024) satisfying 610 = b6 + 65 + b3 + b2 + b + 1.
Table 3.4: ppolynomials for hyperovals in AG(2,32)
Flyperoval ppolynomial
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 KeefePenttila 651W30 + b924x2 + b230x24 + b55 X21 + b3x18 +696a:15 + b433x12 + b199x9 + b924x6 + b100 x3 + 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 ppolynomials to present. For Subiaco 15 we let q be a primitive element of GF(16) satisfying if = q + 1. Since Subiaco 15 has a ppolynomial 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: ppolynomials for hyperovals in AG(2,64)
Hyperoval ppolynomial
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 + X30 + 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 ppolynomials 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: ppolynomials for hyperovals in AG(2,128)
65
Table 3.7: ppolynomials for hyperovals in AG(2,128) (2)
66
Table 3.8: ppolynomials for hyperovals in AG(2,256)
Hyperoval ppolynomial
Hyperconic 1
Translation t8 (x + l)16
;r(;r14 + 1)
Adelaide ^(T1/3 + l)3
(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 ppolynomials as it is the only family above for which we have not yet provided an nice ppolynomial 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 ppolynomial representation of hyperovals we observed that several nonarc 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
siik 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 nonisomorphic 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 siik 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, 01 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 J2 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 J2 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 nonzero 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 J2
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 nonisomorphic 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 mregular 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, ,Ã‚Â£mi 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 1regular line segments is just a single line segment. The structures currently known to be represented by cyclotomic sets are sets of regular line segments, siik 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 ?nregular 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 ?nregular 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")91 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 mregular 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 = maxjT : 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 siik configuration. Observe that [0, UU2, , Ui] 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 siik 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 sn,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 siik 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 siik configuration.
Corollary 4.8 Ca(fi) is an sn.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 MobiusKantor 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
MobiusKantor 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 MobiusKantor configuration in Figure 4.3 has points labeled with these roots, showing the appropriate collinearities.
Figure 4.3: C3[8,1,3]: A MobiusKantor 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 cyclotomic 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 4regular 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 4regular 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 sn3 configuration for s > 1. There are 16 instances of cyclotomic sets that are a 2163 configuration. We construct GF(216) with the minimal polynomial rr16 + x5 + x3 + x2 + 1.
81
The roots of the polynomial
;r16 + ;r10 + j9 + x1 + ;r6 + x + 1
are a 2163 configuration. It decomposes into a C3 [16,1,5] and a C3 [16, 3,10]. In larger planes we also find sn3 configurations, including some with an additional parallelism. In AG(2,512) there are cyclotomic sets that are (187, 423) configurations. This configuration has a 6regular parallelism, and removing it produces a 2183 configuration. In AG(2,1024) there are 64 cyclotomic sets that are 2203 configurations, and 4 cyclotomic sets that are 203 configurations. In AG(2,2048) there are 12 cyclotomic sets that are 3223 configurations, and in AG(2,4096) there are cyclotomic sets that are ??4 configurations, some with a parallelism.
4.4 Open Questions
In addition to the questions already mentioned, this work leads us to the following open problems about cyclotomic sets.
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), 1735, 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: 423449.
[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, 431457.
[6] Wieb Bosnia, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235265.
171 Brown, J., Cherowitzo, W. The LunelliSce hyveroval in PG(2,16). J. Geom. 69 (2000), no. 12, 1536.
[8] Cardinali, I., Payne, S. E. qclan 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. aflocks and hyperovals. Geom. Dedicata 72, (1998), (3): 221 246.
[11] Cherowtizo, W. Hyperovals in Desarguesian planes of even order Annals Disc. Math. 37 (1986) 8794.
[12] Cherowitzo, W. Hyperovals in Desarguesian planes: an update. Combinatorics (Acireale, 1992). Discrete Math. 155 (1996), no. 13, 3138.
[13] Cherowitzo, W.E., Payne, S.E. The cyclic qclans with q = 2e Advances in Geometry, Special Issue (2003) S158S185.
[14] Cherowitzo, W.E., OKeefe C.M., Penttila, T. A unified construction of finite geometries associated with qclans in characteristic 2 Adv. Geom. 3 (2003), 121.
83
[15] Cherowitzo, W., Penttila, T., Pinneri, L, Royle, G. F. Flocks and ovals. Geom. Dedicata 60 (1996), no. 1, 1737.
[16] Cherowtizo, W.E., Storme, L. aFlocks with Oval Herds and Monomial Hyperovals Finite Fields and their Applications 4, (1998) 185199.
[17] Fisher, J. C., Schmidt, B. Finite Fourier series and ovals in PG(2,2h). J. Aust. Math. Soc. 81 (2006), no. 1, 2134.
[18] Glynn, D. A condition for the existence of ovals in PG(2, q), q even. Geometria Dedicata 32 (1989), 247252.
[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. 217229.
[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), 159176.
[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, 275289.
[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. SpringerVerlag New York, 1973.
[26] Jamison, R. Covering finite fields with cosets of subspaces, Journal of Combinatorial Theory, Series A, 22 (1977), 253266.
[27] Koike, H., Kovacs, I. Pisanski, T. The number of cyclic configurations of type (vi) 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. karchi 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) 117139.
84
[32] OKeefe, C. M., Penttila, T. Hyperovals in PG(2,16). European J. Combin. 12 (1991), no. 1, 5159.
[33] OKeefe, C. M., Penttila, T. Symmetries of Arcs. J. Combin. Th. Ser. A 66, (1994) 5367.
[34] OKeefe, Christine M., Thas, J. A. Collineations of Subiaco and Chewwitzo hyperovals. Bull. Belg. Math. Soc. Simon Stevin 3 (1996), no. 2, 177192.
[35] Payne, S. E. A new infinite family of generalized quadrangles. Congressus Numerantium, (1985), 49: 115128.
[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, 5074.
[38] Payne, S.E., Thas, J.A. The Stabilizer of the Adelaide Oval Discrete Mathematics 294 (2005) 161173.
[39] Payne, S. E., Penttila, T., Pinneri, I. Isomorphisms between Subiaco qclan geometries. Bull. Belg. Math. Soc. Simon Stevin 2 (1995), no. 2, 197222.
[40] Penttila, T., Pinneri, I. Irregular hyperovals in PG(2,64). J. Geom. 51 (1994), no. 12, 89100.
[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) 91104.
[43] Penttila, T., Storme, L. Monomial Flocks and Herds Containing a Monomial Oval Journal of Combinatorial Theory, Series A, 83 (1998), 2141.
[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: 785790.
[47] Segre, B. Ovals in a finite projective plane. Canadian Journal of Mathematics 7 (1955), (0): 414416.
[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, 377385.
[50] Thas, J. A., Payne, S. E., Gevaert, H. A family of ovals with few collineations. European J. Combin. 9 (1988), no. 4, 353362.
[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 opolynomials of the most recently discovered hyperovals makes us expect that new hyperovals will have increasingly complicated opolynomials, 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 LunelliSce 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 OKeefePenttila 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
d1
*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,
d1 /dl \
^ 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 opolynomials
We can now give a method for turning known opolynomials into ppolynomials,
and viceversa. We wish to note that this general conversion formula will not always give the most elegant ppolynomials, 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
HYPEROVALSANDCYCLOTOMICSETSINAG ;q by PHILIPA.DEORSEY DoctorofPhilosophy,UniversityofColoradoDenver,2015 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof DoctorofPhilosophy AppliedMathematics 2015
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 andopolynomials,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
ACKNOWLEDGMENT FirstandforemostIwouldliketothankmywifeTianyforsupportingmethroughoutthisprocess.Completingmydegreetookmanyyearsofeortandstruggle.You arealwaystheretosupportandencourageme,keepingmelevelheadedandmyeyes ontheprize.ThankyouTianyforyourunconditionalsupportandlove,Icouldnot havedoneanyofthiswithoutyou. ImustthankmyadvisorBillCherowitzoforstickingwithmethroughtheyears. IknowIamnottheeasiestPh.D.studenttoadvisebutyoustuckwithmethrough itall.Yourcalmdemeanorwasanicecomplementtomyanxiousness,andhelped keepmefocusedandlessworried.Youalwayskeptmemovingintherightdirection withguidanceandsuggestionsforwhattodonext.Youhaveadvisedmeinmore thanjustmyresearch,youhaveguidedmeinteaching,life,andmore.Thankyou foreverything,Bill. ThankstotherestofmycommitteeJason,Mike,Stan,andTimwhogaveme manyguidingremarksandideasthathelpedmenisheverything.Ihavehadmany discussionswitheachofyouovertheyearsandItrulyvalueeachandeveryminute. SpecicallyIwanttothankMikeFerrarawhohadtodealwithmemorethanmost. Thanksforguidingmeandalwaysbeingtheretodiscussanything. IwouldliketoacknowledgeAntonBettenwhocollaboratedwithmeonmuchof thecomputationalsideofthisresearch.Thankyoufortakingtimeoutofyourbusy scheduletoworkwithme. IwouldberemissifIdidnotmentionmyundergraduateadvisorandfriendMark Millerwhointroducedmetonitegeometry.ThankyouMarkforyoursupportand theintroductiontosuchabeautifulsideofmathematics. Finally,thankstomyfamily,myparentsKenandEllie,andmysiblingsMike, Dave,Michelle,Paul,Maureen,andLee.Youallprovidedmewithmotivationwithout evenknowingit.Ialwaysstrivetomakeyouallproud. iv
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]:AMobiusKantorcongurationfoundinAG,16.......80 4.4CongurationsfoundascyclotomicsetsinAG,64...........81 vii
PAGE 8
TABLES Table 1.1opolynomialsforknownhyperovals.....................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. Hyperovalshavetraditionallybeenrepresentedbypolynomialscalledopolynomials 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 thisworkwillbeonthe2dimensionalprojectivespacecalledaprojectiveplane.A projectiveplane isapointlineincidencestructurethatisdenedbythefollowing 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 anopenquestionastowhetherprojectiveplanesofnonprimepowerorderexist. Aprojectiveplaneoforder q canbeconstructedasa3dimensionalvectorspace overGF q ,theniteeldwith q elements.Thepointsarethe1dimensionalsubspaces,andthelinesarethe2dimensionalsubspaces.Incidenceissettheoretical 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 isaonetoonemapfromaprojectiveplaneontoitselfthatmaps collinearpointstocollinearpoints.Thesetofallcollineationsofaplaneisknown asthe collineationgroup oftheplane.ThecollineationgroupofPG ;q isdenotedPL ;q .TherearetwotypesofcollineationsinPG ;q ,homographiesand automorphiccollineations. If A isanonsingular3 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 karc inaprojectiveplaneisasetof k points,nothreeof whicharecollinear.Itcanbeshownthat k q +2when q iseven,and k q +1 when q isodd.A q +1arciscalleda oval anda q +2arciscalleda 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 opolynomial Theuseofopolynomialsgivesacompactandusableformforhyperovals,sothey havebeenthetraditionalwayofdescribinghyperovals.ArepresentativelistofopolynomialsforknownfamiliesofhyperovalsisgiveninTable1.1. 8
PAGE 17
1.5AHistoryofHyperovals Signcantstudyofhyperovalsdatesbacktothelate1950'stoapaperbyLunelli andSce[30]inwhichtheyuseacomputertosearchforcompletearcsinPG,16as suggestedbyB.Segre.Theirsearchyieldedonehyperoval,uptoprojectiveequivalence,thatwasnotaconic.ThishyperovalisnowknownastheLunelliScehyperoval andcanbedescribedbytheopolynomial f t = t 12 + t 10 + 11 t 8 + t 6 + 2 t 4 + 9 t 2 ; where isaprimitiveelementofGFsatisfying 4 = +1. Table1.1:opolynomialsforknownhyperovals Name opolynomial 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'KeefePenttila[31] SeeBelow PG,32 4 2 2mod2 h )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 Subiaco AnopolynomialforsomeoftheSubiacohyperovalsis 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 representedwithopolynomial 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 AnopolynomialfortheAdelaidehyperovalis 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'KeefePenttila AnopolynomialfortheO'KeefePenttilahyperovalis 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. TheLunelliScehyperovaldoesnotappearinTable1.1asitwasshowntobein theSubiacofamilyin[15]andintheAdelaidefamilyin[14].Formoreinformation ontheLunelliScehyperovalsee[7]. In1962,shortlyaftertheworkbyLunelliandSce,B.Segregavethetranslation andSegrehyperovalsin[46].Thesehyperovalsremainedtheonlyknownhyperovals forover20yearsuntilGlynngavetwonewfamiliesin[19].TheGlynnhyperovals wereyetmoreexamplesofwhatarecalled monomialhyperovals ,thatishyperovals thatcanberepresentedbymonomialopolynomials.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'KeefePenttilahyperoval,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 kbitmonomialhyperoval ifanopolynomial for H is f t = t n andthereare k 1'sinthebinaryrepresentationfor n .The1bit monomialhyperovalsarepreciselythetranslationhyperovals.The2bitmonomial hyperovalswereclassiedin1998[16],andthe3bitmonomialhyperovalswereclassiedin2010[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.Combiningthisinformationwiththeopolynomialsofthemostrecently discoveredhyperovalsmakesusexpectthatnewhyperovalswillhaveincreasingly complicatedopolynomials,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 theLunelliScehyperovaldescribedabove.Inordertoclassifyhyperovalsinthis planeHallneededthehelpofacomputer,howeverin1991O'KeefeandPenttila[32] classiedthehyperovalsinPG,16withouttheaidofacomputer. In1994thehyperovalsinPG,32wereclassiedbyPenttilaandRoylebyexhaustivecomputersearch[41].EveryhyperovalinPG,32isprojectivelyequivalent toeitherthehyperconic,translation,Segre,Payne,Cherowitzo,orO'KeefePenttila 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 LunelliSce[37] q +2 h q =16 O'KeefePenttila[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, theirrelationshiptoopolynomials,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 wellknownlemmaisofconsiderableuse. 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 Everynonzeroelement ofGF q 2 canbedecomposeduniquelyasthe productofa q +1 st rootofunitytimesanonzeroelementofGF 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 everynonzeroelement ofGF q 2 canbedecomposeduniquelyastheproductofa q +1 st rootofunityandanonzeroelementofGF 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 : Thepreimage 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 nondegenerate conics. O'KeefeandPenttilaalsogiveaspecicsubgroupthatxesthepoint ; 0 ; 1 andtheline z =0andhas q )]TJ/F15 11.9552 Tf 12.056 0 Td [(1nondegenerateconicsasorbits.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 conicsofthepencilarenondegenerate.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 representationismuchmorecompactthanthantheopolynomialrepresentation. 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, andviceversa.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. Inordertodeterminetheopolynomialformofthishyperovalwemapthesepoints 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 satisfyanopolynomialft,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 isclearlyonetooneandsoGF 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 Givenanopolynomial 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 + isexternaltothetranslationhyperovalwithopolynomial 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 polynomialdescribingthetranslationhyperovalwithopolynomial 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 polynomialforthetranslationhyperovalwithopolynomial f t = t 4 Corollary2.33 InAG,q,with q =2 h h odd,thefollowingare polynomialsthat producethetranslationhyperovalwithopolynomial 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 describesthetranslationhyperovalwithopolynomial 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 thatproducethattranslationhyperovalwithopolynomial 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 polynomialdescribingatranslationhyperovalwithopolynomial 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 thetranslationhyperovalwithopolynomial 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 opolynomial 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 representsanopolynomialforaSubiacohyperovalinvariable 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 : WeclaimthatthisisanopolynomialforaSubiacohyperoval. 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 isanopolynomialforaSubiacohyperoval. 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
isanopolynomialforaSubiacohyperoval,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 isanopolynomialforaSubiacohyperoval. 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.Thegeneralconversionfromtheiropolynomial formsasgiveninTheorem2.24arecurrentlythemostappealing.Thedicultyin conversionstemsfromthefactthatthesehyperovalsarealreadyquiteelegantlyrepresentedasopolynomials.Theexponentsonthepolynomialtermsarevariablebased ontheplanetheylivein,ratherthanaxedinteger.Thisinitselfpresentsdiculty insimplication.Itmaybepossibletousecaseanalysis,similartothatinCorollary 2.33,tofurthersimplifythe polynomialsforhyperovalsinthesefamilies,butour workuptothispointhasnotbeenfruitful. Throughstudyingthe polynomialrepresentationithasbecomeclearthatsome hyperovalswillbebetterrepresentedasopolynomials.Manyofthemonomials,with exceptionofthehyperconic,aremoreelegantlyrepresentedasopolynomials.In fact,aswesawinTheorem2.40theSegrehyperovalhasitssimplest polynomial 54
PAGE 63
representationoverGF!IncontrasttheSubiacoandAdelaidehyperovalshave polynomialrepresentationsoverGF,wherethereopolynomialcounterpartsdo not.Additionally,wewillseenicestructurerepresentedbythe polynomialofthe O'KeefePenttilahyperovalthatisnotrepresentedbyitsopolynomial.Assuch,the intentionofthe polynomialmethodisnottoreplaceopolynomials,butratherto complementthem.Combiningthetworepresentationswillhelpusstudyhyperovals andrevealinformationabouttheirstructurethatwouldlikelybeoverlookedifstudy wasrestrictedtoonerepresentation. 55
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'KeefePenttilahyperovalin [31],therstexamplesoftheSubiacohyperovalin[40],andhelpedclassifyhyperovals withnontrivialautomorphismgroupinPG,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 thesearchrevealedboththehyperconicandLunelliScehyperovals.Theseare theonlyhyperovalsthatarecontainedinthisplanesowedidnotdoanyfurther searches.Intotaleighthyperovalswerefound,fourofeachtype.TheLunelliSce 60
PAGE 69
polynomialsareofparticularinteresthereastheyhavebeenshowntobemembersoftheAdelaideandSubiacofamilies.Sincethesehyperovalsarestabilizedby thesquaringautomorphismtheynecessarilyhave polynomialswithcoecientsover GFwheretheiropolynomialcounterpartsdonot.TheLunelliSce 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 LunelliSce 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'KeefePenttilahyperovals.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'KeefePenttila 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 nonarcstructuresappearedascyclotomicsetsincludinglines,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 numberofnonisomorphiccyclic 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,01matriceswithcolumns 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,1matrixgeneratedby 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,withthesumofthenonzeropositionsequivalentto0mod 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,16thataretheMobiusKantorconguration.ThesearetheonlycongurationsfoundascyclotomicsetsinAG,16.The congurationpolynomial, N 3 x ,forthesecongurationsisshownbelowwherewe constructGFwithminimalpolynomial x 8 + x 4 + x 3 + x 2 +1.Eachfactorin thegivenfactorizationbelowisapolynomialwhoserootsarethepointsofasingle 79
PAGE 88
MobiusKantorconguration. 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 : TheMobiusKantorcongurationinFigure4.3haspointslabeledwiththeseroots, showingtheappropriatecollinearities. 97 11 88 22 176 133 194 44 Figure4.3: C 3 [8 ; 1 ; 3]:AMobiusKantorcongurationfoundinAG,16 4.3.2AG,64 InAG,64wendinstancesofcyclotomicsetsthataregrids,aswellascyclotomicsetsthatareacongurationwithaparallelism.Thereare8instancesof the4 3grid,36cyclic12 3 congurations,and12instancesof 4 ; 16 3 congurationsthatconsistofa12 3 congurationwitha4regularparallelism.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.Thereare16instancesofcyclotomicsetsthatarea216 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 area216 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.Thiscongurationhasa6regularparallelism,andremovingitproducesa218 3 conguration. InAG,1024thereare64cyclotomicsetsthatare220 3 congurations,and4cyclotomicsetsthatare20 4 congurations.InAG,2048thereare12cyclotomicsets thatare322 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. OrbiterAProgramtoClassifyDiscreteObjects. 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. TheLunelliScehyperovalinPG,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.13,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 .SpringerVerlagNewYork,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. karchicompletineipianiproiettividesarguesianidirango8 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. IsomorphismsbetweenSubiacoqclangeometries. 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

