BLOCKING SETS OF CONICS
by
Leanne D. Holder
B.S., University of Southern Mississippi, 1994
M.S., University of Colorado at Denver, 1997
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2001
Ik0,
uTi
This thesis for the Doctor of Philosophy
degree by
Leanne D. Holder
has been approved
by
V.
Q../IA...
Holder, Leanne D. (Ph.D., Applied Mathematics)
Blocking Sets of Conics
Thesis directed by Professor William E. Cherowitzo
ABSTRACT
Traditionally, the study of blocking sets has been devoted to studying sets of
points in a projective plane with the property that every line of the plane contains
at least one point in that set. In this classical situation, we refer to a blocking
set as a line blocking set. A line blocking set is said to be irreducible if no proper
subset is a line blocking set. Although the study of line blocking sets takes its
origins in game theory, many of the results pertaining to blocking sets of lines are
due to finite geometers. Using basic properties of the plane, it is simple to show
that such sets exist. Most of the research pertaining to line blocking sets consists
of examining existence, structure, and obtaining bounds on the sizes of irreducible
blocking sets.
Just as there are sets of points that block lines, there are sets of lines that
block conics. We define a conic blocking set (CBS) to be a set of lines in a Desar
guesian projective plane such that all conics meet these lines. This dissertation
presents a study of conic blocking sets restricted to sets of concurrent lines and is
divided into two parts: CBSs in planes of even characteristic, and CBSs in planes
of odd characteristic. In both settings, there is a trivial proof that guarantees the
existence of CBSs. There are nontrivial constructions of CBSs that rely heav
m
ily on results by J. A. Thas relating to the theory of flocks of quadratic cones.
An efficient algorithm is developed for finding the minimum size of CBSs. This
algorithm requires working with the dualized projective plane and incorporates
optimization techniques. Along with the results of the computer searches, bounds
on the minimum size of CBSs are discussed.
This abstract accurately represents the content of the candidates thesis. I rec
ommend its publication.
IV
ACKNOWLEDGMENT
My great thanks and appreciation go to the following people. This is but
a brief list of those who stuck by me and made obtaining this degree a reality.
In their own special way, they have given me a different perspective on various
aspects of life. I hope I can do the same for someone else one day.
Bill Cherowitzo for his encouragement, guidance, and generosity, for the
years of racquetball. I cant believe you survived six years of my pestering; Allen
Holder for being my best friend, for being my husband, for being my spine, for
believing in me when I wouldnt. You are still the best thing that ever happened
to me; Tim Penttila for sharing your sabbatical and your dinners with me, for
sitting in the car eight hours while I drive you around southern Colorado, but
mostly, for the help you gave me with the work presented in this dissertation.
Without it, Id still be in school; Dianne Daniel for being my mom, which pretty
much covers anything else that might need to be said; Donnie Daniel for being
my dad, whose advice and lectures after all these years are finally making sense.
Now, you can quit bugging me to finish so that I can get a job; Caroline Heberton
 for celery, peppers, black olives, sushi, sleepless nights, artificial hiways, and
peeing dogs. Without you, the start of my evolution may not ever have occurred;
Kathy, Alex, & Maggie Martinez for racquetball, for opening up their home to
me, for racquetball, for the hot tub, for racquetball; Art & Holly Carlson for
Sunday night pizzas and XFiles. I couldnt have adopted better surrogate parents
than the two of you; Renata Heberton for letting me lose to her in cards; Alyssa
Heberton for being an Alyssa and for loaning me clothes on the two occassions
in which I had to dress up; Brendan Heberton for cooking breakfast with me
in the morning. By the way, you still cant knock me down; Harvey Greenberg 
for being my Jewish mother, for letting me cry on your shoulder, and for all the
advice that you offered, even if I never asked for it; Mark & Andrea Miller for
being Mark & Andrea Miller; Stan Payne for answering my Questions of the Day
and for the insightful comments and insight with various parts of my research;
John Wilson for letting me bug him when I didnt want to work, for helping with
my programming, and lately, for the style file that he wrote for this dissertation;
Lexie Taylor and Dave Krutsinger for Sunday dinners and the XFiles, for being
the best dog sitters ever, for Mara, for future Thanksgivings, for being my fashion
coordinator, and most importantly, for not being math geeks; Renee Wisniewski
 for our weekly lunches and walks downtown; Mr. Warren Bateman for the
establishment of the Lynn Bateman Teaching award, which enabled me to attend
Combinatorics 98 so that I could obtain exposure to my future mathematical
community; Debbie Wangerin for looking out for us; Zenas Hartvigson for
supporting me in teaching (in more ways than you can remember); and Chris
Linden for getting me out of the house and for making these last two years more
enjoyable than they could have been. Never Surrender Never Give Up!
Leanne Holder
2001 May
CONTENTS
Figures .................................................................... x
Tables.................................................................... xii
Chapter
1. Projective Geometry Applications....................................... 1
1.1 Applications of Geometry to a Communication System................... 1
1.2 Applications of Geometry to Coding Theory............................ 4
1.3 Applications of Geometry in Cryptography............................. 6
1.3.1 Secret Sharing Schemes ............................................. 8
1.4 Conclusion............................................................ 10
2. Introduction and Review............................................... 11
2.1 Finite Fields........................................................ 11
2.1.1 Polynomials over Finite Fields...................................... 13
2.1.2 Quadratic Equations................................................. 16
2.2 Projective Geometry.................................................. 18
2.2.1 The Projective Line ................................................ 22
2.2.2 The Projective Plane................................................ 23
2.2.2.1 Planes of Even Order ............................................. 31
2.2.2.2 Planes of Odd Order............................................... 38
2.2.3 Projective ThreeSpace.............................................. 43
2.3 Blocking Sets of Lines............................................... 45
2.3.1 Definitions and Examples............................................ 46
vii
2.3.2 Bounds on the Size of Irreducible Blocking Sets................... 48
2.3.3 Redei Blocking Sets .............................................. 49
2.4 Blocking Sets of Conics............................................ 51
3. CBSs in Planes of Even Order......................................... 54
3.1 Introduction......................................................... 54
3.2 The TraceFlock Construction......................................... 55
3.3 Irreducible CBSs in PG(2,2/l), h even.............................. 60
3.4 Searching for Minimum CBSs........................................... 68
3.5 Bounds on the Sizes of Minimum Conic Blocking Sets................. 76
3.6 Chapter Summary ..................................................... 80
4. CBSs in Planes of Odd Order.......................................... 83
4.1 Introduction......................................................... 83
4.2 The TraceFlock Construction......................................... 84
4.3 Searching for Minimum CBSs........................................... 94
4.3.1 Restricted Quadratic Form Model................................... 95
4.3.1.1 Review of Linear Algebra and Quadratic Forms.................... 95
4.3.1.2 Restricting Nondegenerate Quadrics to a Line.................... 99
4.3.1.3 Classifying Points in the Dual Setting.......................... 101
4.3.1.4 The RestrictedDual Model Summary............................... 104
4.3.1.5 Finding the CBSs in the Set Covering Setting.................... 105
4.3.2 SecantTangent Mapping Model..................................... 108
4.4 Small Conic Blocking Sets in PG(2, q2)............................. 112
4.5 Bounds on the Sizes of Minimum Conic Blocking Sets................. 128
4.6 Chapter Summary .................................................... 139
viii
5. Conic Blocking Sets and Flocks................................... 141
5.1 General Terminology and Background Material.................... 141
5.2 The Dual Setting and Star Flocks............................... 145
6. Avenues of Further Research........................................ 156
Appendix
A. CBS Parameters for q Even ....................................... 158
B. CBS Parameters for q Odd......................................... 160
C. The Branch and Bound Algorithm.................................... 163
References............................................................ 171
IX
FIGURES
Figure
1.1 A Communication System with Seven Users and Switches................ 3
1.2 Atmospheric Noise................................................... 5
1.3 A Simple Cryptosystem............................................... 7
2.1 The Fano Plane..................................................... 24
2.2 Desargues Configuration........................................... 26
2.3 X and Y Not on a Common Tangent Line............................... 37
2.4 X and Y on a Common Tangent Line .................................. 37
2.5 Constructing the Polar of a Point with Respect to a Conic.......... 41
2.6 Flock of a Cone.................................................... 44
2.7 The Complement of a CBS ........................................... 52
3.1 A partitioning of Z................................................ 57
4.1 A partitioning of Â£................................................ 86
4.2 A Collection of Values Q ((A + k)n)............................... 124
4.3 The Union of 3Cycles............................................. 126
4.4 The 3Cycles for Q(x) = x2 + otl0x + 1.......................... 128
5.1 An Arbitrary Cone................................................. 141
5.2 Linear Flock ..................................................... 142
5.3 Primary and Secondary Baselines................................... 144
5.4 Dual Flock Setting................................................ 146
5.5 Dual Baseline Setting ............................................ 147
x
5.6 Dual Proper Star Flock in PG(3, q).............................. 150
C.l A Tree........................................................... 166
xi
TABLES
Table
3.1 CBS Sizes Given by the TraceFlock Construction................ 59
3.5 Minimum CBS Sizes.............................................. 76
3.6 Construction Sizes............................................. 81
3.7 CBS Bounds and Sizes........................................... 82
4.1 CBS Sizes Given by the TraceFlock Construction................ 93
4.5 Array B to Array A Conversion in PG(2,3)...................... 107
4.6 Values for Minimum CBSs....................................... 112
4.14 Squarity Subtraction Tables................................... 129
4.16 Construction Sizes............................................ 139
4.17 Minimum Values and Bounds on Minimum Values .................. 140
4.18 Bounds on Minimum Values...................................... 140
A. l CBSs in Planes of Even Order.................................. 158
B. l Minimum CBSs in Planes of Prime Order......................... 160
B.2 Minimum CBSs in Planes of Nonprime Order...................... 161
B.3 Smallest Known CBSs for q an Odd Prime........................ 162
B.4 Smallest Known CBSs for q an Odd Nonprime..................... 162
xii
1. Projective Geometry Applications
Projective geometry has applications in modern information and communi
cation science, more specifically, in coding theory and cryptography. The aim of
coding theory is to develop methods that enable the recipient of a message to
detect or even correct errors that occur while transmitting data. Many problems
of coding theory can be directly translated into geometric problems. As to cryp
tography, one of its tasks is to keep information secret by enciphering it. Another
task is to protect data against alteration. Surprisingly, cryptosystems based on
geometry have excellent properties: in contrast to most systems used in practice
they offer provable security of arbitrarily high level.
1.1 Applications of Geometry to a Communication System
To illustrate how projective geometry can be applied to a communication
problem, we will examine one that is developed in [8]. Consider a scenario where
there is a collection of users who wish to communicate with each other. To make
this scenario more interesting, several conditions are imposed on the participants
and on the communications network.
For the participants of the scenario, two constraints are imposed. First, it is
impossible for any participant to get in direct contact with another participant.
Secondly, each participant must use the communications network which will con
sist of switches. For the communications network, three conditions are imposed.
First, each switch is responsible for a certain number of users. Second, each switch
can connect any two of the users. Third, any connection between two users needs
1
at least one switch. Finally, for economic reasons, the condition that the number
of switches should be as small as possible is imposed.
Now, we examine the requirements for this communication system. The first
requirement is
any two users can be connected using just one switch.
Since any switch should have some use, the second requirement is
each switch connects at least two users.
If all users were connected by only one switch then there would be a substantial
amount of mutual interference; therefore the third requirement is that
there are at least two switches.
Finally, since it should be possible to produce switches cheaply, the final require
ment is
all switches look alike.
We will expound further on this last requirement.
Now that we have formulated the requirements for the communication system,
we translate this into geometrical language using linear spaces.
Definition 1.1 A linear space is a geometry L consisting of points and lines such
that following three axioms hold.
(Ll) Any two distinct points of L are incident with precisely one line.
(L2) On any line of L there are at least two points.
2
(L3) L has at least two lines.
In order to do this translation, the users are called points and the switches
are called lines. Now, the first three requirements of the system translate into
the axioms of a linear space. That is, in order to obtain a good communications
system we have to find a linear space
 that has a number of lines that is as small as possible, and
 in which all lines look alike.
Although the phrase looking alike has not been precisely defined, this phrase can
be taken to mean that any line has the same number of points, or in terms of the
switches, each switch connects the same number of users.
The following example will further clarify this communication network de
scription.
Example 1.
Figure 1.1: A Communication System with Seven Users and Switches
Consider the communications network system that has seven users, 1, 2, 3, 4,
5, 6, 7, and seven switches such that each switch handles three users. Then the
switches would be 123, 145, 167, 246, 257, 347, 356.
3
By designating the outer points to represent switches (lines) and the inner
points to represent users (points), we see that the picture on the righthand side
of Figure 1.1 is a communication system. For further information about this
communications system, see [8, 72],
Most importantly, it can be shown that communication systems with the least
number of switches are obtained from projective planes [8].
1.2 Applications of Geometry to Coding Theory
Coding theory originated with the arrival of computers. Early computers were
huge and their reliability was low compared to the computers of today. These
computers consisted of banks of mechanical relays, and if a single relay failed to
close an entire calculation was in error. The engineers of the time devoted much
energy to finding ways to detect faulty relays so that they could be replaced.
While R. W. Hamming was working for Bell Labs [33], he began to work on the
problem of having the machine not only detect when an error occurred, but correct
the error as well. Hamming devised a way of encoding information so that if an
error was detected it could also be corrected. Based in part on this work, Claude
Shannon [64] developed the theoretical framework for the science of coding theory.
In this section, we briefly examine the errorcorrecting aspect of coding the
ory. The problem that can be answered using projective geometry deals with the
difficulties inherent with the transmission of messages. More particularly, suppose
that we wished to transmit a message and knew that in the process of transmis
sion there would be some sort of noise causing the message to be altered. This
noise could be due to weak signals, sporadic electrical bursts, and other naturally
occurring noise that creeps into the transmission medium. The problem is to in
4
sure that the intended message is obtainable from whatever is actually received.
content is easily obtainable, even if the coded message received is full of errors.
A basic errorcorrecting code consists of transmitting redundant information
together with the message that is to be communicated. That is, the message is
extended so that the sequence of symbols, in the message, is a longer sequence and
this extension is done in a systematic manner. This particular coding method has
many economical drawbacks. There are other errorcorrecting codes, and some
are more economical.
There are many codes for encoding and decoding transmitted data that are
related to projective geometry. For instance, projective geometry has ties to
Hamming codes, linear codes, cyclic codes, MDS codes, and ReedMuller codes.
The ReedMuller code is one of the most studied codes and has been used by
NASA for transmission of data.
One simple approach to this problem is to code the message so that the original
Figure 1.2: Atmospheric Noise
5
To examine one of the applications of codes, consider NASAs Mariner 9
mission in 1971. Mariner 9 was a space probe whose mission was to fly over Mars,
photograph the surface, and then transmit the pictures back to Earth. The black
and white camera aboard the Mariner 9 took the pictures, and a fine grid was then
placed over the picture and for each square of the grid the degree of blackness is
measured on a scale from 0 to 63. These numbers, expressed in binary, are the
data that is transmitted to Earth. By the time the data arrived back at Earth,
the signal was weak and needed to be amplified. Noise from space modified the
signal and thermal noise from the amplifier had the effect that occasionally a
signal transmitted as a 1 was interpreted by the receiver as a 0 and vice versa.
Thus, there was clearly a need to code this information with an error correcting
code. The ReedMuller code was chosen for this task of transmitting pictures.
For more information about the Mariner 9 mission and the coding theory used in
that project, see [71, 56]. For more information on the ReedMuller codes as an
application of projective geometry, see [16, 2].
1.3 Applications of Geometry in Cryptography
As mentioned at the beginning of this chapter, cryptography has two main
purposes. The first is to provide a method that guarantees the privacy of infor
mation. The second is to provide methods that allow the receiver of the message
to determine if the message has been altered and verify that the message came
from the claimed sender. Such systems are often based on secret keys; therefore
the secure distribution and storing of secret keys is a central area of cryptography.
The following illustration of a simple cryptosystem is found in [68]. A simple
cryptosystem usually enables two people, referred to Alice and Bob, to communi
6
cate over an insecure channel in such a way that an opponent, referred to as Oscar,
cannot understand what is being communicated. The channel could be anything
from a telephone line or a CB radio to a computer network. The plaintext infor
mation that Alice sends to Bob is encrypted by Alice using a predetermined key.
This ciphertext is then sent over the channel where Oscar, whose is eavesdropping,
cannot determine what the plaintext was, but Bob who has the encryption key
can decrypt the ciphertext to reconstruct the plaintext.
Figure 1.3: A Simple Cryptosystem
For this illustration, Alice and Bob use the following protocol for their cryp
tosystem. First, in a secure setting, Alice and Bob chose a random key K. When
Alice wants to communicate with Bob, she encrypts the plaintext x using the key
K into the ciphertext y which is sent over the communication channel. When Bob
receives the ciphertext y, he decrypts it using the key.
It is often the case that the authenticity of the plaintext is more important
than the confidentiality of the plaintext. A message is said to be authentic if the
recipient is sure that
1. he receives exactly the data the sender has sent (data integrity) and
7
2. the data really originated from the claimed sender (data authenticity).
We see that there are two types of attacks available to disrupt the authenticity
of a message. One is when an attacker tries to insert a message claiming that
he is the real sender and the other is when an attacker tries to modify the sent
message. As protection against the attacks described, authentication systems have
been invented [65].
In 1974, Gilbert, MacWilliams, and Sloane [30] showed that if k is the number
of possible keys to an authentication system, then an attacker could deceive with
probability at least 1 /A authentication system with k keys is called perfect,
if the probability that an attacker will be able to insert or substitute a message
is only 1 /i/k. Perfect authentication systems exist and can be constructed using
mathematical structures such as projective geometry.
Another aspect of cryptography that can involve projective geometry is the
problem of storing and retrieving secret data. This problem can be solved in an
optimal way by using a secret sharing scheme [63, 66].
1.3.1 Secret Sharing Schemes
In a secret sharing scheme, a dealer has a secret and would like to distribute
to every participant of this scheme a share of the secret. The shares should be
distributed secretly, so that no participant knows the share of another participant.
Also, some time later a subset of the participants could pool their shares in an
attempt to compute the secret. In some situations, the dealer may want some of
the subsets of participants to be able to compute the secret while other subsets
of the participants to be unable to compute the secret [68, 12]. If the dealer is
8
faced with this type of situation, then it is necessary to identify the appropriate
subsets of participants before the shares are distributed.
To better illustrate this concept, consider a generic secret sharing scheme
involving the employees of a bank [38].
Example 2. In a bank, there is a vault that must be opened every day. The
president of the bank employs a number of senior tellers and vice presidents but
does not trust any individual with the combination to the vault. So, a system
needs to be designed in which certain combinations of these employees can open
the vault.
One plan is to design a system, call it Design A, whereby any three senior
tellers can open the vault or any two vice presidents can open the vault. Although
this appears as a practical solution in theory, this system might not work in reality
if only two senior tellers and one vice president show up for work [68]. A more
practical design, Design B, is obtained by adding to Design A the ability for two
tellers and one vice president to open the vault. One must insure that no pair
of senior tellers alone can open the vault while allowing any vice president in
cooperation with a pair of senior tellers the ability to open the vault [67]. If we
can do this, we will have obtained a secret sharing scheme in which the dealer
is the president of the bank, the participants are the vice presidents and senior
tellers, and the secret is the combination to the vault.
A model for both Design A and Design B can be developed by using various
relationships between certain points, lines, and planes of a projective fourspace
to represent the secret and the shares.
9
1.4 Conclusion
For all of the applications presented in this chapter, the basic properties had
to be worked out before projective geometry could be applied to solve such prob
lems. In this thesis, we are working out the basic properties of a new concept in
projective geometry.
10
2. Introduction and Review
This introductory chapter contains a survey of some basic algebraic and ge
ometric concepts that will be employed throughout this dissertation. We begin
with a discussion of finite fields and functions over finite fields, since both are
instrumental to the development of projective geometries. After that, we provide
a detailed overview of projective geometries.
2.1 Finite Fields
Definition 2.1 A field is a set K closed under two operations +, x such that
1. {K,+) is an abelian group with identity 0;
2. (K*, ) is an abelian group with identity l, where K* K \ {0};
3. x(y + z) = xy + xz, (x + y)z xz + yz, for all x, y, z in K;
Below, we list definitions and properties that are useful to the development of the
results given in this paper. These are taken from [35, Ch.l], and the reader is
referred to [48] for an indepth look at finite fields or to [26] for an introduction
to finite fields.
1. A finite field is a field with only a finite number of elements.
2. The characteristic of a finite field K is the smallest positive integer (which
must be a prime) p such that px 0 for all x in K.
3. GF(p), p prime, consists of the residue classes of the integers modulo p under
the natural addition and multiplication and is a finite field of p elements.
11
4. A finite field K of characteristic p has a subfield isomorphic to GF(p) and
has ph elements for some h in N.
5. If f(t) is an irreducible polynomial of degree h over GF(p), then
GF (p") = GF(p)[t]/(f)
= {oo + ait + + ahith 1 
6. The elements x of GF(q), q = ph, satisfy
xq x 0,
and there exists s in GF(
GF(q) = {0,1, s,... sq~2  sq~l = 1};
such an s is called a primitive element of GF(q) or generator of GF(q)*.
7. Any field of q elements, q = ph is isomorphic to GF(q), which is called the
Galois field of order q.
By Property 6, we have that every element in Â£ = GF(2n) satisfies x2" = x,
so that x is the square of the element x2"1. We also remark that every element
in Â£ has exactly one square root, since 1 = 1 in Â£.
Unlike the situation in GF(2n), if Â£ = GF(pn) with p an odd prime, then not
every element in Â£ is a square. Those that are not squares are called nonsquares.
If A is a primitive element of Â£, so that Ap"_1 = 1 and A(pn_1)/2 = 1, the even
powers of A are squares; while the odd powers are nonsquares. The element 0 is
not considered a square or a nonsquare. Hence, there are squares and the
12
same number of nonsquares. Furthermore, it is easy to see that the product or
quotient of two squares or nonsquares is a square; but the product or quotient of
a square and nonsquare is a nonsquare. We often denote a square element with
the symbol and a nonsquare element with the symbol0. The following theorem
will prove to be useful when we obtain counts of various sums in Â£.
Theorem 2.2 [24, Thru. 67] If S denotes the number of squares a2 in Â£ for which
a2 + 1 = and N denotes the number of squares t2 for which r2 + 1 = 0, we
have
S=\{pnb),N = \(pnl),if 1=D;
5 = i(p 3),N= \{pn + 1), if 1 =jZT.
2.1.1 Polynomials over Finite Fields
Polynomials for which the associated polynomial functions are permutations
of a given finite field GF(g) are called permutation polynomials. These polynomials
exist over any GF(g) since every mapping of GF(g) into itself can be expressed by
a polynomial function. We remind the reader of the obvious, that if the function
/ is a permutation polynomial of GF(g), then / is onetoone and onto. Other
criteria and properties of permutation polynomials can be found in [48, ch.7].
Definition 2.3 [48] Let GF(qm) be an extension of GF(q) and let a G GF(qm).
Then the elements a, aq, aq2, aqm are called the conjugates of a with respect
to GF(q).
Let Â£ = GF(gm) be an extension of /C = GF(gd), where d is any divisor of
m. An automorphism a of Â£ over /C is a mapping of Â£ onto itself that fixes the
13
elements of K, pointwise. Thus, a is required to be a onetoone mapping from Â£
onto itself with a(a + /3) = a{a) + a(/3) and cr(a/3) o(a)o((8) for all a, j3 G Â£
and cr(a) = a for all a e 1C. The relationship between conjugate elements and
certain automorphisms of a finite field is explained in the following theorem.
Theorem 2.4 [48] The distinct automorphisms of Â£ = GF(qm) over K = GF(g)
are exactly the mappings cro,<7i, crmi, defined by Oi(t) = tp' for t Â£ F and
0 < i < m 1.
For example, the automorphisms of GF(24) are
&o (t)=t,
ox{t) = t2,
a2{t) = t4,
a3(t)=t*.
It is clear, from the previous theorem, that the conjugates of a Â£ Â£ with
respect to /C are obtained by applying all automorphisms of Â£ over /C to the
element a. The next map we examine is a linear map from Â£ to /C, and it is
important in the construction of conic blocking sets.
Definition 2.5 [48] For a G Â£, the trace TrÂ£/K(a) of a is an additive homomor
phism of Â£ into K. is defined by
TrÂ£/K (a) = a + aq 4 otq2 + + agm 1.
If K, is the prime subfield of Â£, then TV (a) is called the absolute trace of a.
Otherwise, TrÂ£/K{a) is called a relative trace of a over K,.
14
We see that the trace of a over /C is the sum of the conjugates of a with
respect to 1C. For example,
TrGF(16)/GF(2)(0 t + t2jrt4+t8,
and
TrGF(16)/GF(4)(0 t + t4.
Moreover, TrÂ£/K (a) is always an element of 1C.
The following theorem gives several useful properties of the trace function,
most notably that the trace function is linear.
Theorem 2.6 [48] Let Â£ = GF(qm) and K, = GF(q). Then the trace function
TrÂ£/)C satisfies the following properties:
L Tre/Aa + P) = Tre/Aa) + Tre/AP) for ali a P G
2. TrÂ£/K(ca) = cTrÂ£/K(a) for all c G /C, a Â£ Â£;
3. TrÂ£/K is a linear transformation from Â£ onto K, where both Â£ and 1C are
viewed as vector spaces over K;
4 TrÂ£/K(a) = ma for all a K;
5. TrÂ£/K{aq) = TrÂ£/ic(a) for all a G Â£.
Often it is more convenient for us to denote TrÂ£/A; by tr or Tr when the fields
in question are understood. Other properties of the trace function can be found
15
in the first chapter of [35]. When q is even, we may express Â£ = ToUTx where T0
is the set of elements of absolute trace 0, and is the set of elements of absolute
trace 1. Then, we have the additional properties:
(a) 0 G To;
(b) q = 22m^l6 T0;
(c) q = 22m+1 <=> 1 G Ti;
(d) t G Tj <=> a(t) G Tj for all automorphisms
I s + t G T0 if i = j,
(e) s G Ti, f G Tj => <
I s + t G Ti if i ^ j.
(f) T01 = Tx = q/2.
It is easy to show that Tr(f2) + Tr(t) = 0 for all t G Â£. From this it can be shown
that any element that can be expressed as the sum of another element and its
square has trace 0.
In Chapters 3 and 4, the trace function will be used to construct conic blocking
sets. In the next section, we use the trace function to determine the number of
solutions of a quadratic equation in a finite field. This will be useful in later
chapters for determining the relationship between a line of the projective plane
and a quadratic form in the plane.
2.1.2 Quadratic Equations
We are interested in determining the number of solutions to quadratic equa
tions in a finite field of order q. We can determine the number of irreducible
16
factors of a quadratic equation
ax2 + bx + c = 0, a ^ 0, (2.1)
over a field of odd characteristic by examining the discriminant of the quadratic
equation. However, in fields of characteristic two, the discriminant proves insuf
ficient to determine the number of irreducible factors. In this case, the number
of irreducible factors can be determined by using the absolute trace function. We
describe the cases of odd and even characteristic separately.
If the characteristic of the field is not two, the discriminant of the quadratic
equation (2.1) is
A = b2 4 ac.
There are three cases:
1. if A = 0, then (2.1) has the unique solution x = 6/(2a);
2. if A is a nonsquare in GF(q), then (2.1) has no solutions in GF(g);
3. if A is a square in GF(q), then (2.1) has two solutions x (b y/A)/(2a).
For characteristic two, let Tr(t) denote the absolute trace of t over GF(2).
Instead of using the discriminant as our invariant, we use a different invariant
called 6.
(a) First, if b 0, then (2.1) becomes ax2 + c 0, and the unique solution to
(2.1) is given by x = y/c/a.
(b) If b ^ 0, we can multiply (2.1) by a/b2 to obtain the equation 9^ + ^ +
= 0. Let y = ax/b and 5 ac/b2, so that (2.1) becomes
y2 + y + S = 0. (2.2)
17
Then, 5 is the invariant of equation (2.1) and also of (2.2).
As mentioned in the previous section, Tr is a homomorphism into JC = GF(2),
i.e., Tr(Â£) = 0 or 1.
1. If Tr(5) = 1, then (2.2) and so (2.1) have no solutions.
2. If Tr(5) = 0, then (2.2) and so (2.1) have two solutions. If y = s is one
solution of (2.2), then y = s + 1 is the other.
2.2 Projective Geometry
The material presented in the upcoming sections is meant to serve as a cur
sory review of some of the basic ideas from finite projective geometry specifically
related to finite projective lines, planes, and solids. A natural place to begin is
the construction of a projective geometry. A commonly used construction for ob
taining a projective geometry starts with a vector space. For reasons that will
soon be clear, we will use the word rank in lieu of dimension when referring
to vector spaces. Let V = V(n + l,q) be an (n I l)rank vector space over the
field GF(q) with zero element 0. We view the elements of V(n + 1 ,q) as the
(n  l)tuples of the form (x0,Xi, ,xn) where the X{ are in GF(g). Consider
the equivalence relation on the elements of V \ {0} whose equivalence classes are
the rank one subspaces of V with the zero deleted. So, if X, Y G V \ {0}, then
X is equivalent to Y if Y = tX for some t G GF(g)* = GF(q) \ {0}. With this
equivalence relation in mind, we can form the ndimensional projective space over
GF(q), denoted PG(n,q), in the following manner: The points, lines, planes, and
solids of PG(n,q) are defined as the subspaces of rank 1, 2, 3, and 4, respectively.
In keeping with classical geometric terminology, we say that these objects have
18
(projective) dimension 0, 1, 2, and 3, respectively. In general, for 0 < k < n, a
rank k subspace of V is said to have projective dimension k 1. A rank n subspace
of V (i.e. an n 1 dimensional object in PG(n,q)) is often called a hyperplane.
Lines in this setting are regarded as certain sets of points; planes can also be
regarded as certain sets of points. If a point lies on a line or in a plane, the point
is said to be incident with the line or plane. This is equivalent to the notion of a
rank one subspace being contained in a rank two or rank three subspace.
A well known result from linear algebra states that if S and T are vector
spaces,
rk(S) + rk(T) = rk{S n T) + rk(S U T),
where rk denotes the algebraic dimension (rank) of a vector space. This is called
the rank formula. For clarity, consider the following example.
Example 3.
Let f2 = PG(4, q) be derived from a rank 5 vector space. The rank formula is
used to determine all possible incidences of lines and planes in f2.
First, the relationship between two distinct planes, 7Ti and 7T2, in Q. is exam
ined. If 7ri and 7T2 lie in a common 3dimensional subspace of (that is, rank four
vector space), then by the rank formula these two planes intersect in a line (a rank
two vector subspace). But, if 7Ti and 7r2 do not lie in a common 3dimensional
subspace of fl, 7Ti and 7t2 must intersect in a point, because their union (span)
would have rank four. Let P, Q, and R be three noncollinear points in f2. Since
each point has rank one, and two points determine a line, using two of these two
lines, according to the rank formula, the smallest subspace containing these three
points is a rank three subspace of fl, which is a projective plane.
19
Second consider the incidence relationship between a line l and a plane 7r,
both in 0. If l meets 7r, l either meets n in a point or is entirely contained within
7r. Suppose two points of l are in 7r. Then since n is a vector subspace, the span
of any two points that lie in 7r also lies in 7r. In this case, it must be that l is
entirely contained in 7r.
If nx and n2 are two spaces PG(n, q) with n > 2, then a collineation T : III >
n2 is a bijection which preserves incidence; that is if IIr C IIS, then IIrr C IIsr,
where IIr and II s are subspaces of III. For instance, T maps collinear points to
collinear points and concurrent lines to concurrent lines. If S' is a set of points in
PG(2,g) with the property that no three are collinear, T maps S to another set
of points with the same property. A projectivity is a collineation that is induced
by the action of a nonsingular matrix on the underlying vector space.
The Fundamental Theorem of Projective Geometry is vital to the work in
Chapters 3 and 4. Below is the statement as given in [35].
Theorem 2.7 [35, 2.1.2 (b)J Suppose {P0,... ,Pn+\} and {P^,... ,P+1} are
both ordered subsets of PG(n, q) of cardinality n + 2 such that no n f 1 points
chosen from the same set lie in a hyperplane. Then, there exists a unique projec
tivity T such that P[ PiT, for 0 < i < n + 1.
For a projective plane where n = 2, the previous theorem essentially states that
the group of projectivities of the plane, PGL(3,q), acts sharply transitively on
four points (no three collinear) of PG(2,g) [9].
Any projective space PG(n,q), has a dual space PG(n, q)*, whose points and
hyperplanes are respectively the hyperplanes and points of PG(n, q). For any the
orem true in PG(n,q), there is an equivalent theorem true in PG(n,^)*. That is,
20
if T is a theorem in PG(n, q) stated in terms of points, hyperplanes and incidence,
the same theorem is true in PG(n, q)* and gives a dual theorem T* by substituting
hyperplane for point and point for hyperplane. So, we have that the dual of
an rspace in PG(n, q) is an (n r l)space. The fact that we can make such a
replacement is known as the principle of duality, and this principle carries over
into any projective geometry.
For instance, in the plane PG(2,g), every statement about points and lines
can be replaced by a dual statement about lines and points. In PG(3,q), a point
and plane are dual, whereas the dual of a line is a line. In order to simplify
calculations it is often necessary to work in the dual setting.
A quadric in PG(n, q) is a set of points in PG(n, q) whose coordinates satisfy
a homogeneous equation of degree two. If Q is a quadratic form, that is,
n
i,j = 0
* < J
oooAq + a01AVG + j
then the set of points satisfying Q 0 is a quadric in PG(n, q). For instance, a
quadric in PG(2,g) is the set of points whose coordinates (X0, X\,X2) satisfy the
homogeneous quadratic equation a0oXg +a0iA'0A'1+a11A^+ao2AoAr2+ai2A1A2 +
022^2 = 0.
In Sections 2.2.1 and 2.2.3, we further examine the projective line and projec
tive 3space. Since the bulk of the results pertain to projective planes, emphasis
is placed on background material in Section 2.2.2.
21
2.2.1 The Projective Line
The projective line, PG{\,q), is important for the results developed in Chap
ters 3 and 4. There are q + l points of PG(1, q) and they are {(1,0)}u{(x, 1)  x G
GF(<7)}. Each point (x, 1) of PG(l,g) can be represented by the nonhomogeneous
coordinate x in GF(q) and the coordinate for (1,0) is oo. In the remainder of
this dissertation, these points of PG(l,g) are often referred to in terms of the
parameters t G GF(q) U {oo}.
A projectivity T of PG(1 ,q) is given by Y = XT, where X = (Â£0,Â£i),
', T G PGL(2,g). The Fundamental Theorem
y = {yo,yi) and T
r d
of Projective Geometry states that any three points of PG(l,g) can be mapped
to any other three points by a projectivity. Since this property is used in the
upcoming chapters, a small example of how a projectivity of the line maps points
to points is presented below.
Example 4.
There are six points on the line PG(1, 5) which have coordinates (0,1), (1,1),
2 1
(2,1), (3,1), (4,1), and (1,0). The projectivity T =
1 1
maps these points
of PG(1, q) to the points (1,1), (4,1), (0,1), (3,1), (1,0), and (2,1), respectively.
Let Q( 1, q) be the set of quadrics of PG(1, q) and Sa,b,c = {(^, y) Â£ PG(1, q) \
ax2 + bxy + cy2 = 0 for a, b, c G GF(
<3(1,g) = {Sa,b,c  a,b,ce GF(
22
There are q2 + q + 1 quadrics in Q(l,q), and each quadric is classifiable by ex
amining the discriminant of the quadratic form. Quadrics of the projective line
will resurface again in the development of constructions of conic blocking sets in
planes of odd order.
2.2.2 The Projective Plane
Since the majority of results presented in this dissertation deal with the pro
jective plane, a more detailed review is offered. There are a variety of ways to
define or construct a projective plane. One such way is the vector space construc
tion given in Section 2.2. We begin this section by giving an axiomatic definition
of a projective plane. This is followed by definitions, theorems, and properties of
the projective plane that are relevant to the results given in this dissertation.
Definition 2.8 A projective plane is a set of points and a set of lines together
with an incidence relation between them satisfying the following three axioms.
(pi) Any two points are incident with a unique common line.
(P2) Any two lines are incident with a unique common point.
(P3) There are at least four points, no three of which are incident with a common
line.
It can be shown that any finite projective plane must satisfy the following theorem.
Theorem 2.9 [1] Let n be a finite projective plane. Then there is an integer q
such that
1. Every point of 7r is incident with exactly q + 1 lines;
2. Every line of tv is incident with exactly q + 1 points;
23
3. 7r contains exactly q2 + q + 1 points;
4 7r contains exactly q2 + q + 1 lines.
In some treatments the conclusion of Theorem 2.9 is taken as the definition
of a finite projective plane. That is, a finite projective plane can be defined as a
set of q2 + q + 1 points and a set of lines in which each line is incident with q + 1
points in such a way that any two points are incident with a unique line. For an
example of this approach, see [16]. Of course, this combinatorial definition can be
shown to be equivalent to the previous axiomatic definition.
Example 5. The simplest finite projective plane is the one with q = 2. It
consists of seven points and seven lines with three points on every line and three
lines through every point. This projective plane is called the Fano plane and may
be illustrated as shown in Figure 2.1. The points are A, B, C, D, E, F, and G
and the lines are ADC, AGE, AFB, CGF, CEB, DGB, and DEF. m
A
Figure 2.1: The Fano Plane
24
The number q is called the order of the projective plane, and in all known
examples q is prime or a prime power. It is a fact that for any given prime power,
there exists at least one projective plane of that order. It is not known whether
planes of nonprime power order exist, although it is commonly believed that any
finite projective plane must have prime power order. The following theorem,
due to Bruck and Ryser [13], gives some restrictions on the possible existence of
nonprime power order finite projective planes.
Theorem 2.10 If q is congruent to l or 2 mod 4, then there cannot be a pro
jective plane of order q unless q = a2 + b2 for some integers a and b.
All of the projective planes with which we will be working satisfy a property
that is based on a relationship between triangles. Two triangles ABC and XYZ
are said to be perspective from a point P provided the lines AX, BY, and CZ
meet at P. The triangles are said to be perspective from a line l provided that
the points AB D XY, AC D XZ, and BC n XZ all lie on the line l. The planes
that satisfy the following theorem of the real projective plane, due to Desargues,
are called Desarguesian and those that do not are called nonDesarguesian.
Theorem 2.11 If two triangles are perspective from a point, they are perspective
from a line. m
The theorem is illustrated in Figure 2.2; the intersections of corresponding lines, P,
Q, and R, are collinear. There are various equivalent statements of the Theorem
of Desargues, most notably a finite plane is Desarguesian if and only if it can
be coordinatized by a finite field. For the remainder of this dissertation, we
restrict ourselves to the Desarguesian planes defined over the Galois Field GF^)
25
o
Figure 2.2: Desargues Configuration
and coordinatized in the standard way. Such a plane is denoted PG(2,g). This
is consistent with earlier notation since projective geometries of dimension two
constructed from vector spaces over finite fields are Desarguesian.
Some of the most popular objects to study in projective planes are quadrics
and the results given in this dissertation deal heavily with nondegenerate quadrics.
To begin our overview of quadrics in the projective plane, we examine the defini
tion of a quadratic form over a vector space. Let Â£ = GF(g) and V Â£3, viewed
as a vector space.
Definition 2.12 A map Q : V > Â£ is called a quadratic form ofV provided
(i) Q(cw) c2Q(w) for all c E Â£, w G V, and
(ii) for every u, v G V the function f defined by f(u,v) = Q(u+v) Q(u) Q(v)
is a symmetric, bilinear form called the polar form of Q.
Definition 2.13 The quadratic form Q of V with polar form f is said to be
nondegenerate if the following is true: if Q(w) = 0 and f(u, w) = 0 for all u Â£ V
then w = 0.
26
If Q is a quadratic form of V, then Q(v) = 0 implies that Q(cv) = 0 for all
cgf. This is the basis of the next definition.
Definition 2.14 Let Q be a quadratic form of the vector space V. The quadric of
the projective plane PG(2, q) corresponding to Q is the set of all points < v > of
PG(2,q) with Q(v) = 0. A quadric is nondegenerate if its corresponding quadratic
form is nondegenerate.
Definition 2.15 A conic is a nonempty, nondegenerate quadric in the projective
plane.
For the results in this dissertation, we work with a quadratic form of V in the
following context. If
A =
a b d
0 c e
.00 / _
is a given upper triangular matrix, then B = A + AT is symmetric. A quadratic
form is given by Q(X) = XAXT. The quadratic form Q is nonsingular and its
polar form f(u,v) is nondegenerate provided (e,d,b)T Null(B) and not on Q,
in other words, Aacf ae2 b2f + bed cd2 ^ 0. A quadric is
{X e PG(2, q)  Q(X) = XAXt = 0}
or equivalently,
{(x, y, z) PG(2, q) \ ax2 + bxy + cy2 + dxz + eyz + fz2 = 0} .
Moreover, the quadric is a conic provided Aacf ae2 b2f + bed cd2 ^ 0.
Now, an oval is a set of q + 1 points in the projective plane such that no three
are collinear. We point out that a conic is an algebraic concept and an oval is
27
a geometric concept. It can be shown that every conic is an oval, that is every
conic contains q + 1 points, no three collinear. In 1954, Segre [60] proved the
following theorem. (For an English version of this result, see [61].)
Theorem 2.16 Any oval in a finite Desarguesian projective plane of odd order
is a conic.
This result does not extend to projective planes of even order, and in Example 7
of Section 2.2.2.1, we give an example of an oval that is not a conic.
Observation 2.17 The image of a quadric under any projectivity in PGL(3,q)
is a quadric.
Proof: Let Q(X) = XAXT be a quadric and let B Â£ PGL(3,
that
Q{X) = XAXT =
X{BBlAB~TBT)XT
{XB){BlABT){XB)T
Y{BlAB~T)YT
Q\Yl
wherey = X5. Then Q'(X) = (XB)(B lAB T)(XB)T is also a quadric. Hence,
the image of a quadric under PGL(3, q) is also a quadric.
Theorem 2.18 [35, Thm. 7.f] PGL(3,q) acts transitively on the set of conics of
PG(2,q). m
28
We now examine the subgroup of PGL(3, q) leaving a nonsingular quadric in
the plane invariant, denoted by PGO(3,g), which can be represented by,
f (a2 ab b2 \
PGO(3, q) =
A =
2ac ad + be 2bd
: ad ^ be and a, b, c, d G GF(g) > .
\ c2 cd d2 y
Lemma 2.19 PGO(3,q) acts sharply triply transitively on the points of a conic
in the plane PG{2, q).
Proof: By Theorem 2.18, we may map any conic in PG(2,g) to the conic
C with equation y2 = xz. That is, C = {(t2,t, 1)  t G GF(g)} U {(1,0,0)}. We
show PGO(3,g) is sharply triply transitive on the points of C by first showing
that PGO(3,g) acts transitively on the points of C, and then examining one and
two point stabilizers. We follow this by arguing that only the identity element of
PGO(3,g) fixes three points of C.
A \
:a,b,c,de GF{q) \ G PGO(3,q). For A G
Hi, observe that (1,0,0) A (a2,ab,b2) is a conic point. Moreover, the orbit of
(1, 0, 0) under Hi contains every point of the conic, since a and b cannot both be
simultaneously 0. So, PGO(3,g) is transitive on the points of C.
: a,b,c,d G GF(g) > G PGO(3,g) where a, d ^
f ( a2 ab b2 \
Let Hi = l 0 ad + be 0
l \ c2 cd d2 )
\ ( a2 ab b2 \
Let H2 = { 0 ad 0
\ \ 0 0 d2 )
0. For B G H2, observe that (0, 0,1) B = (0, 0,1) and so B fixes the conic point
(0,0,1). Now, (1,0,0) B = (a2,ab,b2) is a conic point. Moreover, the orbit of
(1, 0, 0) under H2 contains every point of the conic except for (0, 0,1), since a / 0.
Thus, PGO(3, q) is doubly transitive on the points of C.
29
a2 0 0 \
Let Hz = (  0 ad 0 : a, 6, c, d G GF(g) ^ G PG0(3,g) where a, d ^
0 0 d2 )
0. For C G Hz observe that (0,0,1) C = (0,0,1) and (1,0,0) C = (1,0,0), and
we have that C fixes both (0,0,1) and (1,0,0). Now, (1,1,1) C = (a2,ad,d2)
which is a point of the conic. Moreover, the orbit of (1,1,1) under Hz contains
every point of the conic except for the two points (0,0,1) and (1,0,0), since a,
d 0. Thus, PGO(3,g) is triply transitive on the points of C.
To show PGO(3, q) is sharply triply transitive, we need to show that the only
element in PGO(3, q) that fixes three points of the conic is the identity element.
We have already shown that PGO(3,q) is triply transitive on C, so suppose
/ a2 ab b2 \
M =
2ac ad + be 2bd
G PGO(3, q)
\ c1
cd
d2 )
fixes the three points (1,0,0), (0,0,1), and (1,1,1) of C. Now, (1,0,0) M =
(a2, ab, b2) = (1, 0, 0) implies that 6 = 0 and (0, 0,1) M = (c2, cd, d2) = (0, 0,1)
implies that c = 0, so that
(a2 0 0 \
M =
0 ad 0
\0 0 d2 J
Now, (1,1,1) M = (a2, ad, d2) = (1,1,1), and we have that a = d. Hence,
/ i 0 0 \
M = 0 1 0
\0 0 l)
which is the identity element in PGO(3,g). Thus, there is a unique collineation
that fixes three points of the conic, and so PGO(3,g) is sharply triply transitive
on the points of the conic in PG(2,qi).
30
Because of the significant variations between the properties of conics in planes
of even order with the properties of conics in planes of odd order, we will discuss
these situations separately.
2.2.2.1 Planes of Even Order
Since the conic blocking set material revolves around points and lines of the
plane and their relationships with conics, it is necessary to discuss these relation
ships in detail. We begin with the classification of lines and points of the plane
with respect to a conic from a geometric viewpoint, and then offer an algebraic
method for classifying points and line with respect to conics. We include relevant
counts pertaining to points, lines, and conics; although, an explanation of how to
derive these counts is not offered.
Since no three points of a conic, denoted C, are collinear, any line l in 7r
can intersect C in at most two points. Hence, l is geometrically classified in the
following way:
/ is a tangent line to C provided \l n C\ 1,
/ is a secant line to C provided / D C\ = 2,
l is an exterior line to C provided \l fl C\ =0.
There are q + 1 tangent lines, secant lines, and exterior lines with
respect to C.
Similarly, the points of the plane are geometrically classified with respect to
a conic. If P is a point in a plane of even order, then P is classified in three ways
with respect to C:
31
if P is on C, P is called a conic point,
if P is the unique point not on C, that lies on all the tangent lines to C, P
is called the nucleus, and
if P is not on C and not the nucleus, then P is often referred to as a regular
point.
Any conic point has one tangent and q secants through it. While the nucleus has
q+1 tangents through it, the remaining points have exactly one tangent,  secant
and  exterior lines through them.
In order to describe algebraically the relationship between points and lines
with respect to conics, we need to recall from Section 2.1, the method for deter
mining the number of solutions to a quadratic equation. Although there are no
new concepts developed here for determining the relationship between lines in the
plane with a conic, we are grateful to S. E. Payne [55] for his help with this review.
Given any quadratic equation over a field Â£ of even characteristic of the form
ax2 + bx + c = 0 with a/0, (2.3)
the number of solutions to this equation is determined by computing the absolute
trace of ac/b2, if b ^ 0. That is,
1. if Tr(ac/52) = 1, then there are no solutions, and
2. if Tr(oc/62) = 0, then there are two solutions.
Let n be a projective plane of even order and C' some conic in II with nu
cleus N'. The Fundamental Theorem allows us to select any three points of C'
32
and the nucleus, {Pq, P[, N'}, and map this ordered set to the ordered set
{(1,0,0), (0,0,1), (1,1,1), (0,1,0)}. There is a unique conic satisfying the given
conditions, and it has equation y2 + xz 0. Note that this is due to the fact that
three points and the nucleus determine a conic in planes of even characteristic.
Since any conic in the plane can be mapped to y2 + xz = 0, we can use
this particular conic to illustrate the algebraic method for determining how a line
meets a conic in a plane of even order. Each line l in the plane has an equation
of the form mx + ny + pz = 0. Every tangent line to C must contain the nucleus
and, therefore, n = 0 for all tangent lines to C.
(0,1,0)
m
n
.P J
= 0 => n = 0.
Thus, the tangent lines to this conic are easily detected.
To classify the remaining lines in the plane with respect to C, assume that
n / 0, so that without loss of generality n = 1. Any nontangential line in the
plane to C has an equation of the form mx + y + pz = 0, and a typical point on
this line is given by T = (x,mx+pz, z). The line with equation mx + y+pz 0 is
either an exterior or a secant line to C, and we must determine how the line meets
C. If T, on the line, is also on the conic, then necessarily (mx +pz)2 + xz = 0, or
rather
m2x2 + xz + p2z2 0. (2.4)
If x 0, then p = 0 or z = 0. In the case that z = 0, we have T = (0,0,0), and
this cannot occur. On the otherhand, if p = 0, the line has equation mx + y 0,
and the point (0,0,1) of the conic also lies on this line. The line y = mx is not
33
a tangent line, so there must be another point of the conic on this line; namely,
a point with coordinates of the form (x,mx,m2x). But, when x = 0, this form
gives (0,0,0), so x ^ 0. If p = 0, but x 0, l is a secant line as the points (0,0,1)
and (1, m, m2) lie on both l and C. Assume now that r / 0 and p ^ 0. We divide
both sides of (2.4) by x2 to obtain
or, rather
p22+1(;)+m2=0' (25)
If we let  ^ and <5 = m2p2, (2.5) becomes
t2 + t + 5 = 0. (2.6)
From the previous section, we can determine how many solutions there are to
(2.6) and so (2.5). If Tr(5) = 1, (2.6) and so (2.5) have no solutions, and therefore
l is an exterior line to C. If Tr(<5) = 0, (2.6) and so (2.5) have two solutions, and
therefore l is a secant line to C.
In conclusion, even though the quadratic formula cannot be used to determine
if a line is a secant or exterior line to a conic, the absolute trace function can be
used to make this distinction. For the quadratic equation given in (2.3), we have
that, when b ^ 0, if
/ac\ there are no solutions, and the line is exterior
Tr = S (27)
0, there are two solutions, and the line is secant.
If b = 0, there is one solution and the line is tangent.
34
Example 6.
Consider the conic with equation C : xy+xz+z2 = 0 and nucleus N (0,1,1).
The point (0,0,1) is not on C and the q + 1 lines through (0,0,1) are x = 0 and
mx + y = 0, m G GF(g). Using the methods previously discussed, the relationship
between the lines through (0,0,1) and the conic C is easily identifiable. The line
with equation mx + y = 0 is a secant line when Tr(m) = 0, and the line x = 0 is
a tangent line to C.
Classifying points in the plane with respect to a fixed conic is a much simpler
task than classifying lines. Let Q(x,y,z) be the quadratic form of the conic
described by the equation
Ax2 + B xy + C y2 + D xz + E yz + F z2 = 0. (2.8)
If P = (x,y,z) satisfies Q(P) = 0, P is a conic point. If P = (E, D,B), then
from [35, Cor. 7.12], P is the nucleus of the conic. Otherwise, it must be that if
Q(x, y, z) 7^ 0 and P ^ (E, D, B), P is neither on the conic nor the nucleus of the
conic.
The nucleus of the quadric is special in the sense that knowing the nucleus
allows us to determine if the quadric is singular. In fact, Hirschfeld [35, Thm.
7.16] shows that if Q(E,D,B) = 0, the quadric is singular and therefore is not a
conic.
In planes of even order, there are examples of ovals which are not conics. In
[35], we find that for q = 2 and 4 every oval is a conic. In the planes of order
> 8, there are ovals which are not conics. The following example illustrates the
situation.
35
Example 7.
Let C be a conic in the projective plane PG(2,q), q > 8 and even, and let M
be the nucleus of C. Let % denote the hyperoval which consists of the q + 1 points
of C and the nucleus of C. So, H is a a set of q + 2 points with the property that
no three are collinear. And by construction, there are no tangent lines to TL. Any
line in the plane must be either a secant line or an exterior line. Let O be the
oval which consists of J\f and any q points of C. Recall that five points, no three
collinear, determine a unique conic. C and O have q points in common and these
q points satisfy a quadratic equation. But, the point M of O does not satisfy this
quadratic equation. Hence, there is no quadratic equation which every point of O
satisfies, so O is not a conic.
Before we develop similar concepts for planes of odd order, we examine the
orbits of points of the plane under the action of a group of collineations which
stabilizes a conic (that is, leaves the set of points of the conic invariant). This
information proves useful in a model used for finding conic blocking sets in Chapter
3.
Lemma 2.20 The group of collineations which stabilize a conic has three orbits
of the points of a plane.
Proof: Let C be a conic, N be the nucleus of this conic, and TL = C U {N}
be the corresponding hyperoval. Any collineation that stabilizes the conic will
also stabilize its nucleus, since every conic has a unique nucleus. We consider two
cases, one where two distinct points off of C do not lie on a common tangent line
and the other where these two points do lie on a common tangent line.
36
Let X and Y be two points off of H. If the tangent line joining X to N is
distinct from the tangent line joining Y to N, let Cx and Cy be the corresponding
conic points on these tangent lines. Let Z be an arbitrary conic point not N, Cx,
or Cy. Let XZ n C = X' and YZ n C = Y'. Since PGO(3,
transitive, there is a unique collineation, T, such that ZT = Z, CXT = Cy, and
XT = Y'. And so, XT = (NCX n X'Z) T = (NCy D Y'Z) = Y, and when X and
Y do not lie on a common tangent line, we have that they are in the same orbit.
If X and Y are on the same tangent line, then let T be the point of the conic
on this tangent line. Let Z be an arbitrary conic point other than T and not N.
Let X' = XZ DC and Y' = YZ nC. Since PGO(3,<7) is sharply triply transitive,
there is a unique collineation, T, such that ZT = Z, TT = T, and XT = Y'.
Thus, XT = (NT n X'Z) T = (NT n Y'Z) = Y.
Combining these two cases, we have that there exists a collineation that sta
bilizes the conic, fixes the nucleus, and maps X to Y for any points X and Y off
of C and not the nucleus of C.
IH
Figure 2.3: X and Y Not on a
Common Tangent Line
Figure 2.4: X and Y on a Common
Tangent Line
37
2.2.2.2 Planes of Odd Order
In planes of odd order, every oval is a conic. That is, the geometric object
we call an oval can be described algebraically as a conic. This was first proved
by Segre in [60]. For a proof that every conic is an oval in English, the reader is
directed to [61]. This fact is occasionally used for conic blocking sets results. As
every conic is an oval and an oval has q + 1 points on it, every conic consists of
q + 1 points that satisfy some nondegenerate quadratic equation.
Since the conic blocking set material revolves around points and lines of the
plane and their relationships with conics, it is necessary to discuss these relation
ships in detail. We begin with the classification of lines and points of the plane
with respect to a conic from a geometric viewpoint, and then offer the algebraic
method for classifying points and line with respect to conics. We summarize
relevant counts pertaining to points, lines, and conics.
Since no three points of a conic C are collinear, any line l in 7r can intersect C
in at most two points. Hence, l is geometrically classified in the following way:
l is a tangent line to C provided \l D C\ = 1,
l is a secant line to C provided \l D C\ = 2,
l is an exterior line to C provided Z Pi C\ =0.
There are q + 1 tangent lines, secant lines, and exterior lines with
respect to C.
38
Similar to geometrically classifying the lines in the plane with respect to a
conic, we geometrically classify the points of the plane with respect to a conic. If
P is a point in the plane then P is classified in three ways with respect to C:
if P is on C, P is called a conic point,
if P is not on C, but on a tangent line to C, P is called an exterior point,
and
if P is neither on C nor on a tangent line to C, P is called an interior point.
Any conic point has one tangent and q secants through it. While an interior point
has ^ secants and exterior lines through it, an exterior point has exactly
two tangents, ^ secant and ^ exterior lines through it.
Algebraically, classifying the lines of the plane with respect to a conic is similar
to the classification method in the Euclidean plane.
Let ax by + cz 0 be the equation of a line in the plane. Since not all of
the coefficients of the line are zero, suppose that b ^ 0 and then solve for y. The
line now has equation
y = a'x + d z, (2.9)
where a' = a/b and d = c/b. Substitute (2.9) into (2.3) to obtain the quadratic
equation
A'x2 + B'xz + C'z2 = 0 (2.10)
where A' = A+ Ba' + Ca'2, B' = Be' + 2Ca'd + Eg' 4 D, and C' = c'2 + Ed + F.
If 2 = 0, there is one solution to (2.10) provided A' / 0, and y a'x + c'z is a
39
tangent line. If z ^ 0, we may divide (2.10) through by z2 to obtain a quadratic
equation in one variable,
A'x'2 + B'x' + C' = 0. (2.11)
If A' = 0 and B' = 0, then necessarily C' 0 implying that C is degenerate,
a contradiction. If A' = 0 and B' ^ 0, there is clearly one solution to (2.11),
and the line is a tangent line. Else, if A' ^ 0, we can use the discriminant of
the quadratic equation to determine how many solutions there are to (2.11) and
thereby determine the type of line with which we are dealing. If B'2 4A'C' = 0,
the line given in (2.9) is a tangent line. If the discriminant is a square, then the
line is a secant line. If the discriminant is a nonsquare, the line is exterior to the
conic.
Algebraically, classifying points with respect to a conic is not as intuitive
as classifying lines with respect to a conic. We defer introducing the algebraic
method for classifying points as introduced to us by S.E. Payne in [54], until
Section 4.3.1.1.
The proof of the following theorem, given in [35, Thm. 7.16], states that if
the symmetric 3x3 matrix representing the quadratic form is nonsingular, then
the zeros of the quadratic form a conic.
Theorem 2.21 If T a^XiXj, then T is singular if and only if 5 = 0, where
i
2 2 2
0 = 4aooOna22 + <201<202<2l2 Q00al2 <2ll<2o2 a22<2oi
Definition 2.22 [4.3] Let C be a conic and l a secant line to C through the points
X and Y of C. The tangent lines to C through both X and Y will intersect at a
40
point P $ C. We call l the polar of P and P the pole of 1. The polars of X and
Y are the tangent lines to X and V respectively.
Figure 2.5: Constructing the Polar of a Point with Respect to a Conic
The assignment of pole to polar and polar to pole with respect to a conic,
is an example of a polarity. A polarity is a onetoone correspondence between
points and lines of a projective plane that preserves the relation of incidence and
is of order two. That is, it sends points into lines, lines into points, ranges into
pencils, pencils into ranges, quadrangles into quadrilaterals, and so forth. One of
the nice properties of polarities is that if a polarity sends A to its polar a, then it
sends a to its pole A. [21]
We examine the orbits of the points of the plane under the group of collin
eations which stabilize a conic. This information proves useful in a model used for
finding conic blocking sets in Chapter 4. Let G(Q) be the subgroup of PGL(3, q)
stabilizing the conic Q. Let
0\ points on Q,
= points off Q,
41
03 = tangents to Q,
04 = secants of Q,
05 = external lines of Q.
Since PGO(3, q) is sharply triply transitive on conics, G(Q) acts triply tran
sitively on 0\ and 03. For q odd, we have that
C?2 = ot n O2,
where
C>2 = {external points of Q}, O2 = {internal points of Q}.
Lemma 2.23 [36]
(i) G(Q) act transitively on O4 and 03;
(ii) G(Q) has two orbits on O2, namely O2 and O2
Proof:
Let Q be the set of points that satisfy x2 + yz 0. Consider the action of
G(Q) on O2, the points off Q. Since each point of O2 is the intersection of two
tangents, Q is transitive on O2, the external points, and by the polarity on O4,
the secants.
Any external line contains an external point. So, to show the transitivity of
G(Q) on 05, and by polarity on 0J, it suffices to show the transitivity on the
external lines through a particular external point. Let Uo = (1, 0, 0) be this point.
Then the line lt given by the equation y f tz = 0 is a secant or external line
if t is a nonzero square or nonsquare respectively. The projectivity Tc, c / 0,
42
given by (x, y, z)Tc (cx, y, c2z) fixes Q and transforms lt to 11 So, we can pass
from any secant through Uq to any other secant through Uo and any external line
through U0 to any other external line through U0. So, G(Q) is transitive on 05,
the external lines, and by the polarity on CAf, the internal points.
Due to Lemma 2.23, we have that the stabilizer of a conic in a plane of odd
order has these three orbits:
1. the conic,
2. the set of external points of the conic, and
3. the set of internal points of the conic.
2.2.3 Projective ThreeSpace
As in the previous sections, the material presented in this section is meant to
serve as a cursory review of some of the basic ideas from finite projective three
space that is relevant to the work presented in Chapters 3 and 4. We forego
an indepth examination of an analogous axiomatic definition, as given in the
previous section, as well as the vector space construction described in Section 2.2,
of projective threespace.
A plethora of geometrical objects exist in projective threespace; such as
ovoids, generalized quadrangles, fccaps, spreads, and flocks. Of these, we are
most interested in flocks.
Assume PG(2,g) is a subspace of PG(3,q), and let C be a conic in PG(2,g)
with V (the vertex) a point in PG(3,g) \ PG(2,g). A quadratic cone K is the
union of the points on the lines joining V to the q + 1 points of C. A flock of a
43
cone K is a set of q planes in PG(3, q) which do not contain V such that no two
planes of the flock meet at a point of K. This definition of flock differs from that
Figure 2.6: Flock of a Cone
found in the majority of papers dealing with flocks. The more common definition
of a flock refers to the conics that partition the cone instead of the planes whose
sections partition the cone. However, the difference is only a matter of viewpoint.
If the q planes of the flock contain a common line, the flock is said to be linear.
Consider the flock F whose planes have equations
xt + f(t)y + g(t)z + w = 0,
where /, g Â£ GF(g)[:r] with /(0) = g(0) = 0. If / and g are additive, we say F is
a semifield flock. When q is even, Johnson [42] has shown that all semifield flocks
are linear. In [29], Gevaert and Johnson have shown that the flock F is a semifield
flock if and only if / and g are additive.
44
The KnuthKantor semifield flock [44] is one of the three classes of nonlinear
semifield flocks known. For q odd and t G GF(<7), the planes 7rf are defined to be:
7rt : tx mtay + w = 0,
where m is a fixed nonsquare and a is an automorphism of the field. These planes
define a semifield flock of the cone K. This flock is linear if and only if a 1.
Theorem 2.24 [69, 70] In PG(3,p2), for any prime p, the semifield flocks are
linear or else they are KnuthKantor semifield flocks. u
More will be said about the KnuthKantor flocks in Chapter 4.
In the past few years, W. Cherowitzo has made significant strides in gener
alizing the theory of flocks of cones by removing the restriction that the flock is
a flock of a cone with a quadratic base. That is, by slightly revising some basic
definitions, it is possible to consider flocks of cones whose base may range over
anything from the empty set, a line, or even a random collection of points in the
carrier plane. To examine his most recent advances in generalizing the theory of
flocks, see [18]. In Chapter 5, we give a conic blocking set application for this
general theory of flocks.
It is worth noting here that it is often more convenient to work with flocks in
the dual setting which we will develop in Chapter 5.
2.3 Blocking Sets of Lines
Line blocking sets originate from game theoretical problems. Richardson [58]
defines a finite projective game, in the plane, by taking as players the points of the
projective plane and specifying the lines of the plane as minimal winning coali
tions. A blocking coalition is a set of points containing no line but intersecting
45
every line. A minimum, blocking coalition is a blocking coalition of smallest cardi
nality. Isbell [40] also examines these games, but not from a geometric viewpoint.
In [25], DiPaola examines minimal blocking coalitions in planes of order < 9 and
makes the note that the blocking coalition concepts provide working material for
game theorists who work with simple games. In recent years, researchers have
made huge strides in studying blocking coalitions. We give a brief introduction to
the results obtained and direct the reader to [35] for more details and references.
2.3.1 Definitions and Examples
A blocking set B in II = PG(2, q) is a subset of points of II which meets every
line but contains no line completely; that is, 1 < \B D l\ < q for every line l in II.
If \B\ = k, B is called a blocking kset. It follows immediately from the definition
that the complement of a blocking set, II \ B, is also a blocking set.
A blocking set is irreducible if B \ {P} is not a blocking set for any P G B.
A blocking set of Redei type in PG(2,
there is some line l G II for which \l D B\ = m.
Lemma 2.25 A blocking set B exists in II if and only if q > 2.
Lemma 2.26 The following are irreducible blocking sets in fl = PG(2,q), when
q > 2:
(i) the set Bi = {PiP2UPiP3UP}\{P2, P3} of2q points consisting of the points
on two sides of a triangle with vertices {Pi, P2, P3} and a point P on P2P3,
minus the two vertices {P2,P3} of the triangle;
46
Pi
(ii) the set B3 = (CUlU {P}) \ {Pi, P2} of 2q 1 points, where C is the set
of points of a conic, l is a secant meeting C in Pi and P2, and P is the
intersection of the tangents to C at Pi and P2;
(Hi) the set B2 (Z\{P})U{Pi,... Pq} of2q points consisting of a line l minus
a point P plus a set Pi,... ,Pq of q points, one on each of the q lines through
P other than l, but with Pi,... Pq not all collinear;
47
(iv) a Baer subplane PG(2,y/q) of PG(2,q) consisting ofq + y/q +1 points, when
q is a square;
(v) the set of q^/q + 1 points of a unital in PG(2,q2). m
Of the irreducible blocking sets listed in Lemma 2.26, all are Redei type blocking
sets except for (v).
2.3.2 Bounds on the Size of Irreducible Blocking Sets
In this section, the upper and lower bounds on the sizes of blocking sets and
irreducible blocking sets are given. As seen in Lemma 2.26, when q is a square,
the points of a Baer subplane form a blocking set.
Lemma 2.27 [14J
(i) If B is a blocking kset in PG(2,q), then
q + \/q + ^
(ii) A blocking kset in PG(2,q) with k = q2 y/q is the complement of a
subgeometry PG(2, y/q).
The next result is due to Bruen and Thas [15].
Theorem 2.28
(i) If B is an irreducible blocking kset in PG(2,q), then k < q^fq + 1.
(ii) Equality holds in (i) if and only if B is a Hermitian arc (unital) and q is a
square.
48
2.3.3 Redei Blocking Sets
From Section 2.3.1, B is a blocking set of Redei type if B is a blocking set
with q + m points containing an msecant. For any function / : GF(g) > GF(q),
be the set of directions determined by /.
Lemma 2.29 [35] A blocking set of Redei type can be constructed in PG(2,q)
from any function f : GF(q) GF(q) unless f is linear or determines every
direction.
Proof: Take B to be the kset consisting of {(t,f(t), 1)  t G GF(^)} U
{(l,d, 0)  d G P/}. Consider the lines through a point P on the the line 2 = 0.
Either P is a point of the form (1, d\, 0) for some d\ G Vj or all the lines through
P meet exactly one of the points of the form (t, f(t), 1). The set B contains a line
if / determines every direction, in which case B contains the line 2 = 0, or / is
linear, in which case B contains the line with equation tx + f(t)y + 2 = 0. Hence,
the line 2 = 0 is a D/secant and so B is a blocking set of Redei type.
Irreducible blocking sets can be constructed using Lemma 2.29.
Lemma 2.30 [10] The following are irreducible blocking sets B in PG(2, q), where
B is constructed as in Lemma 2.29.
1. If q is odd, let f(x) = x^+1^2; then f determines (g + 3) directions and B
is an irreducible blocking set of size Â§(9+ 1).
2. Let f be the trace function from GF(q) to a subfield GF(q'); then f deter
mines q/q' + 1 directions, and hence B is a blocking set of size q + q/q' + 1.
let
49
3. If q'  q, let f(x) = xq>; then f determines (q l)/(q' 1) directions, and
hence B is a blocking set of size q + (q l)/(q' 1). u
Choosing the msecant to be the line at infinity l<*,, we consider the set of
directions determined by the set S = B \ /<*> of size q. Let 5 be a set of q points
in AG(2, q) = PG(2, q) \ l^ and, with u = (ui, u2), v {vi,v2), let
V /  u ^ v'u, v G S'! C GF(q) U {oo}
[UiVx J
be the set of directions determined by the set S. As a converse to the examples
of Lemma 2.30, the following result holds.
Theorem 2.31 [5] Let A C AG(2,q) be a point set of size q = ph, let V be the
set of slopes of secants of S, and put m = \V\. Let e, with 0 < e < h, be the
largest integer such that each line with slope in V meets S in a multiple of pe
points. Then one of the following holds:
1. e = 0 and (q + 3)/2 < m < q + 1;
2. e = 1, p = 2, and (q + 5)/3 < m < q 1;
3. pe > 2, where e divides h, and q/pe + 1 < m < (q l)/(pe 1);
4 e = h and m = 1.
For more results on blocking sets of Redei type, see [50], [5], and [11]. We will
show in Chapter 5 that Theorem 2.31 has application to flocks of a cone.
For a more detailed introduction to blocking sets, see Chapter 13 of [35], which
also contains an extensive list of references for results dealing with blocking sets
from the past 30 years.
50
2.4 Blocking Sets of Conics
Recall, from Section 2.2.3, a flock of a quadratic cone with vertex V in PG(3, q)
is a set of q planes not through V which do not intersect on the cone. There is
a considerable amount of interest in flocks due to their connections with gclans,
spreads, translation planes, and generalized quadrangles. One interesting question
about flocks that deserves further research is, if given a set of q planes in PG(3, q)
and a point V not on any of the planes, does there exist a quadratic cone with
vertex V having these planes as a flock? Using the conic blocking set results that
are developed in this dissertation, we can start on an answer to this question.
A conic blocking set (CBS), B, is a set of lines in a projective plane tt which
meets every conic in tt. If every conic in it has at least one secant or tangent line
in B, then B is a CBS. A CBS is irreducible if no proper subset of B is a CBS.
In other words, B is irreducible if B \ {1} is not a CBS for every line l in B. A
CBS of smallest cardinality is said to be minimum. Clearly, a minimum CBS is
irreducible.
Lemma 2.32 If 7T is a projective plane, then it contains a CBS.
Proof: Let B consist of the q + 1 lines through any point P in tt. Clearly, B
contains all the points in tt. Since every conic in tt is contained in B, every conic
meets B and B is a conic blocking set.
Since the removal of any single line from the conic blocking set described in
Corollary 2.32 is still a CBS, that CBS is neither minimum nor irreducible.
In the next two chapters, conic blocking sets in projective planes are closely
examined. For the remainder of this dissertation, we make the restriction that
all conic blocking sets consist of a set of concurrent lines through a specified
51
point, P. The complement of a CBS, Bc, consists of the remaining lines through
the point P. We say a CBS B is projectively equivalent to another CBS B' if
B
P
Figure 2.7: The Complement of a CBS
there exist an element A in PGL(3, q) such that A maps all the lines in B to the
lines in B'. For instance, suppose B is a CBS consisting of a subset of the lines
{y = mx + z  GF(g)} through (0,1,1). Consider the element
' 1 0 0
A = 0 1 0
. 0 1 1
(0,1,1) A = (0,0,1
m m
A 1 = 1
1 0
The set of lines of the form y = mx + z through the point (0,1,1) are projectively
equivalent to the set of lines of the form y mx through the point (0, 0,1). So, a
CBS consisting of the subset of lines of the form y mx + z is projectively equiv
alent to a CBS consisting of the lines of the form y = mx, since the projectivity
maps conics to conics.
Nontrivial constructions for finding conic blocking sets and upper and lower
bounds on minimum CBSs are discussed below. The theoretical and computer
52
models used to generate minimum CBSs in projective planes are also described.
As planes with even characteristic vary from those of odd characteristic, we discuss
CBSs in these planes separately.
53
3. CBSs in Planes of Even Order
In this chapter, we focus on CBSs in planes of even order. Properties of certain
flocks are used to prove that our constructions give CBSs in PG(2,2/l). When h
is even, we derive irreducible CBSs and also show how Baer lines form CBSs.
Theoretical lower and upper bounds on the sizes of minimum CBSs are given.
A model which allows the search for minimum CBSs to become more efficient is
developed. Examples of minimum CBSs are located in Appendix A.
3.1 Introduction
To set notation, let Â£ = GF(2/l) = GF(q), K, = GF(2d), T = GF(2), and
7r = PG(2, q), where h > 1 and d\h such that d ^ h. Certainly, 1C = T if d = 1.
Let tr(f) denote the relative trace function, TrÂ£/K(t) t + t2d +( t2d
In Chapter 2, we showed that all projective planes have conic blocking sets.
The next theorem sharpens that result by showing that just over half the lines
through a point are enough to form a CBS.
Lemma 3.1 Any set of ^ + 1 concurrent lines in PG(2,q) form a CBS.
Proof: For the sake of obtaining a contradiction, assume that there is a
conic C contained in the  lines of Bc. Since each line of Bc contains at most two
points of C, we account for at most 2 () = q points of C. But, as C contains
q + 1 points, C cannot be contained in Bc and thus, B is a CBS.
We consider CBSs in PG(2, 2) now, so that the remainder of the chapter can be
devoted to finding small CBSs in PG(2,2h), with h > 1, using more sophisticated
techniques than those of Lemma 3.1.
54
Theorem 3.2 A CBS in PG(2, 2) contains at least two lines.
Proof: In PG(2,2), any point P lies on three lines. In Lemma 3.1, we
established that any 2=^ + 1 lines (which must be concurrent) form a CBS in
PG(2,2). We need now only show that one line is not a CBS.
Suppose B is a CBS consisting of the single line l. A conic C in PG(2,2)
consists of three points and of the seven lines of the plane, three are secants, three
are tangents, and one is an exterior line with respect to C. By the Fundamental
Theorem of Projective Geometry, any conic can be mapped to a conic that has l
as an exterior line. Hence, there is some conic in PG(2,2) not blocked by l, and
one line is not enough to form a CBS.
3.2 The TraceFlock Construction
Finding CBSs consists of identifying a set of lines through a point such that
all conics in 7r have at least one secant or tangent line in this set. For the CBS
construction given in this section, n is coordinatized so that P = (0,1,1) is the
point of concurrency. Note that the lines through P are x = 0 and y = mx + 2
for m E GF(
an equivalent problem statement is to identify the slopes of the lines of the form
y = mx + z such that every conic in 7r meets these lines. We begin by examining
the size of the range of a specific function in GF(g); for this function will determine
the slopes of the CBS lines.
Lemma 3.3 If g : Â£* > Â£ is given by g(t) = jor t ^ 0, then \Range(g)\ =
2h~d + 1.
Proof: To show that the size of the range of g is 2h~d + 1, we show that Â£
55
can be partitioned into 2h~d + 1 blocks: one of size 2h~d and 2h~d blocks of
size 2d 1.
Let t G Â£*, then
tr(t) + t
g(t) = 1 ^ = 1
tr(t) +t = t
<=> tr(t)  0.
Since the trace function is an additive homomorphism from Â£ onto /C, ker(tr) is
a normal subgroup of Â£. We have that ker(tr) = Â£//C % = 2h~d. So,
g(t) = 1 t is one of the 2h~d 1 nonzero elements in Â£ with trace 0. Hence,
there is one block of Â£ that contains the 2h~d elements with trace 0.
Now, we show that the remaining elements in Â£ are partitioned into blocks of
size 2d 1, giving 2h~d blocks. To do this, we first determine when g(t) = g(Xt)
for A G Â£ \ K.
/.v tr(f) + t tx(Xt) + Xt
g{t) = g{Xt) ^ 
=> Atr(f) + Xt tx(Xt) + At
=> Atr(f) = tx(Xt).
As tr : Â£ > /C, we have that tr(At), tx(t) G /C. But, since A G Â£ \ /C, Atr(f) G
/C tx(t) = 0. We see that g(t) = g(Xt) for some AG
element with trace 0. That is, t G ker(tr).
Observe that g(t) = g(Xt) for t Â£ ker(tr) for any A G 1C'. Let Tq = {x E
Â£*  tr(ar) = 0}. Then t G T0 ^ g(t) = 1. Now, \Â£\T0\ = 2* 2/ld =
2h~d(2d 1) and we see that g partitions Â£ into 2h~d + 1 blocks. There is one
56
block containing 2h~d elements with trace 0, and the remaining elements of Â£ are
split into 2h~d blocks of size 2d 1 one for each value of g that is not equal to 1.
Thus, Ranged)  = 2h~d + 1.
8
2dl 2d1 2dl 2*1 2dl
2dl 2d1 2dl 2dl 2dl
2dl 2dl 2d, 2dl 2dl
2dl 2dl 2dl 2dl 2dl
2dl 2dI a 2hd ^ 2i : 2
2d1 2dl
Figure 3.1: A partitioning of Â£
If h is prime, then tr(t) is the absolute trace of t and Range(^) = 2h_1 + 1.
If h is composite, then there exists a g, as in Lemma 3.3, such that Range(g) <
2h~1 + 1. In other words, when h is composite, g can be defined using a relative
trace, which allows for a smaller range than the one obtained by using the absolute
trace.
In Section 2.2.3, we defined a flock of a cone K with vertex V to be a set of q
planes not through V which do not intersect on the cone. For the results given in
this section, the base of the cone is contained in the plane w = 0. The following
theorem due to Thas is instrumental in the proof of Theorem 3.5.
Theorem 3.4 [69] In PG(3,2h), if the planes 7Ti, 7t2, 7t9, of a flock of a
quadratic cone contain a common point, then F is linear.
We now prove the main result of this section.
57
Theorem 3.5 In PG(2,2h) with h > 2, if d \ h then there is a CBS of size
2h~d _j_ 1_
Proof:
Consider the additive function f(t) = Tr (i) + t tr(t) + t, which we use
to form the function g(t) = ^ ^ q sjlown jn Lemma 3.3,
Range(g) = 2h~d + 1 and is larger than one.
Let B = {y = g(t)x + z  t ^ 0} be the set of lines in the plane w = 0 through
(0,1,1,0) with slope in the Range(g). Consider the planes of the form:
nt : f(t)x + ty + tz + w = 0 with t G S*.
There are 2h 1 planes of this type since t Â£*. Clearly, the point (0,0,0,1)
does not lie on these planes and the point (0,1,1,0) lies on all these planes. Any
two distinct planes 7rs and 7rt (s ^ t) meet in a line which projects from (0,0,0,1)
to the line y = x + z = g(s t)x + z in the plane w = 0. This line is in
the set B. With the plane w = 0, we have a set of 2h planes all passing through
(0,1,1,0) such that every pair of these planes meet in a line which projects to a
line of B. Suppose there exists a conic C that misses B. Form a cone, K, with
vertex (0,0,0,1) and base C. These 2h planes form a flock of K, and the planes
all contain the common point (0,1,1, 0). Theorem 3.4 implies this flock is linear;
in other words, \B\ 1. But \B\ 2h~d + 1 > 1, so C does not exist and B is a
CBS.
In the traceflock construction, the specific function g(t) = tr(^+ was used to
give the slopes of the lines in the CBS. Since g is an additive function divided by
58
t and the size of its image set is known, we used g to form a CBS of size 2h~d + 1.
Any function of this form can be used to produce a CBS, as long as the image
has more than one element in it. The traceflock construction does not give CBSs
when <7 = 2, since the only additive function, up to scalar multiplication, is the
identity. This is the reason for handling PG(2,2) at the beginning of this chapter.
Table 3.1 lists the sizes of CBSs guaranteed by the traceflock construction
described in Theorem 3.5, for small q.
9 Guaranteed CBS Sizes
22 3
23 5
24 9, 5
25 17
26 33, 17, 9
27 65
28 129, 65, 17
29 257, 65
2i 513, 257, 33
Table 3.1: CBS Sizes Given by the TraceFlock Construction
For a fixed q, the largest size of a CBS guaranteed by the traceflock con
struction is the same size as those CBSs constructed in Lemma 3.1. When h is
prime, the traceflock construction yields exactly one CBS. When h is composite,
a variety of CBSs are obtained and there is always a CBS smaller than the one
given in Lemma 3.1. To emphasize the significance of this fact, the traceflock
59
construction gives a CBS of size 33 that blocks the (over 1.12 x 1015) conics in the
plane PG(2, 210), whereas by Lemma 3.1, 513 lines were needed to form a CBS.
3.3 Irreducible CBSs in PG(2,2/l), h even
In this section, we focus on proving that the CBSs given by the traceflock
construction are irreducible. Recall from Chapter 2, a CBS B is equivalent to
another CBS B' if there exists an element A in PGL(3, q) such that A maps all
the lines in B to the lines in B'. We showed that a CBS consisting of the subset
of lines of the form y = mx + z is projectively equivalent to a CBS consisting of
the lines of the form y = mx. We use this fact to prove that the conic blocking
set given by the traceflock construction, for h even, is irreducible.
Throughout the remainder of this section, let h = 2n, n > 2, d
n, so that E = GF(22n), JC GF(2n), and T GF(2). Then g(t) =
)+ tt1 +t Â£2ni Let a be a generator of E. Then Range(g) =
{1, a2"1, a2(2"_P, a2"(2n_P} is a cyclic subgroup of E* of order 2n + 1. Ob
serve that any element in Range(^) is expressible as c^2"1^ where k G Z2n+i.
In Section 3.2, we showed that the set of lines {y = g{t)x + zj formed a CBS,
and this set of lines is projectively equivalent to the set B = {y = g(t)x}. So, we
have that B is a CBS. It remains to show that B is an irreducible CBS. As an
illustration, we show B is irreducible in PG(2,16) and then present a formal proof
of irreducibility for all q = 22n.
Example 8.
Let h = 4, n = 2, and a be a generator of E. Observe that Range(^) =
{t3f G E*} {1, a3, a6, a9, a12} = {a3k \ k G Z5}. To show that the CBS
60
B {y = a3k  k G Z5} is irreducible, we show that for every line in B, there is a
conic that meets the line but does not meet any other line of B.
Consider the quadric Qm : {(x, y, z)  x2 + a~3myz + z2 = 0} where m G Z5.
Since the nucleus, (a_3m,0,0), does not lie on Qm, this quadric is nondegenerate.
We show that B is irreducible by showing that the line y = a3mx is a secant line
to Qm while all other lines, y a3kx with k ^ m, are exterior to Qm.
To determine how the line y = a3kx meets Qm, we examine
x2 + a~3ma 3kxz + z2 0
x2 + a3{k~m)xz + z2 = 0.
This equation has two solutions if Tr (f) = Tr (a6(Vm)) = Tr(a9(*m)) = 0. Let
k m j. Then
Tr (a9(*m)) = Tr (a9^) = a* + (a97)2 + (a9*)4 + (a97)8
= a9j + a18j + a36j + a72j
= 9j + a37 + a6'7 + a127.
If j 0, then k = m and Tr(a97) = Tr(l) = 0 in GF(16). Therefore, when
k = m, the line y = amx is secant to Qm. When j is a fixed element in Z5, a9'7,
a37, a67, a;127 are distinct. More importantly, a:97, a37, ct67, a127 are four of the
five 5^ roots of unity over Â£*, with 1 the remaining 5^ root of unity. Thus,
a97 + a3'7 + a:67 + a:127 = 1 and Tr(a97) = Tr (a9(fcm)) = 1. Since the absolute
trace is 1, there are no solutions to this quadratic equation. Therefore, when
k ^ m, the line y a3kx is exterior to Qm.
Since the removal of any line l from B results in B \ {1} no longer being a
CBS, B is irreducible.
61
Since (0,0,1) is on all lines of the CBS, we only need to block conics with
equations Ax2 + Bxy + Cy2 f Dxz + Eyz + Fz2 = 0 which do not pass through
the point (0,0,1). For these, F ^ 0 and without loss of generality we may assume
that F 1. The set B = {y = t2n~lx \ t 0} blocks all of these conics in the
plane PG(2,22n). We can show that B is irreducible by showing that for every
line in B, there is a conic that only meets that line. We now provide two lemmas
that aid in proving this result in Theorem 3.8.
When n > 2, \K,\ > 4, and there is an element j3 in /C with TrK/;F(/3) = 1.
Since (3 E K, C Â£, (3 = /?2". This implies that for 0 < i < n 1,
This observation is useful in the proof of Theorem 3.8. Lemmas 3.6 and 3.7 are
used to simplify calculations for Theorem 3.8.
Lemma 3.7 Let j be a positive integer. Then (2^nj { + ^(2n_i1)J^n+j = 1.
Proof: Let s = (2n l)j. Recall from Lemma 3.6, as2'+s2n+' = 1. Then
(3.1)
Lemma 3.6 Let j be a positive integer. Then a^2" 1b'+2n(2" W = \
Proof:
a(2l)j+2(2l)J = [a(2 + l)(2l)J] = = ^ g Â£*_
(1 + as)2' + (1 + as)2n+i
1 1
(1 + asfn+' + (1 + ols)2>
(1 + as)2*(l + as)2n+l
62
_ (1 + as)2"+' + (1 + ols)2'
~ (1 + as2i)(l + as2n+i)
1 + as2n+' + 1 + as2'
= 1 + as2n+i + as2' + as2i+s2n+i
_ a + as
~ 1 + as2n+i + as2i + 1
_ as2n+ + os2
as2n+i + as2i
= 1.
Theorem 3.8 The CBS, B = {y = t2" lx \ t / 0}, is irreducible in PG(2,22").
Proof: Let P G K such that TxÂ£/K{P) = 1. Consider the conics Qm with
equations:
Qm(x, y, z) = x2 + a
(12 n)m
xy +
1
P1/2
xz +
0,(12 ")m
/31/2
?/z + z2 = 0,
where m G Z2n+1. The nucleus of Qm is (a ^1/2 m, ^72, oX12")) and observe that
> ^172, c^12")771) = q/(12n)2m ^ 0, hence Qm is nondegenerate. Express
0 as the set of lines of the form {y = a^2n~^kx \ k G Z2n+1}. We show that when
k = m, the line y = qC2"1)771^ is a tangent line to Qm) and when k ^ m, the line
y z= a^2n~^kx is exterior to Qm, for all k G Z2n+1.
For a line in B to meet Qm, we must have that
1 rv(l2")m+(2*l)fc
x2 + q,(12")m+(2n l)fc^,2 + + Â£+ *2 = 0,
has a solution. This can be rewritten as
(! +
a
(2l)(*m;
}) X2 +
l q,(12n)m+(2n l)fc
pm
+
pm
xz + z2 = 0.
(3.2)
63
When k = m, (3.2) becomes z2 = 0. Since there is only one solution to this
equation, the line y = a^2n~^mx is a tangent line to Qm.
Let k m = j ^ 0. To show that the line y = a^2n~l^kx does not meet Qm,
examine the absolute trace of
(l + c^W)
( 1 , l+qt^lM2
^^172 + jm )
(l + a(2"W)
I ,
(1 + a^2"1^)
L (1 + +a(2i)2j)
(l + q(2"i)j)
1 (1 + a(2l )jf
P
(1 + a(2n1b')'
As we now show, these lines are exterior to Qm. Assume, for the sake of
attaining a contradiction, that Tr ( (i+a(^ni)j) ) = 0 Then,
Tr
(l+af2"1)2)
= 0
(l+a(anW) + (l+oP'iM)* + (l+aC*BiW)4 + '
I P11 , 02n , 02U+1 ,
(lW21^')2" 1 (l+a(2n1W)2 (l+Q(2n1)i)2n+1
J!!
0
. ,2nl 0
1+q(2'*1)j)2
_____i_____ i__________i i a
(l+aC2""1^') (lW2"1^)2"] P
+
(l+a(2"1) (i+q(2"i)j)
. 2n+l
+
64
+fi2
1
1
_ (l+o^2111^')2" + (i+q(2"1)j)22"
= 0 (by equation 3.1)
P + P2 + P4 + + Z?2"2 + /52"1 = 0
(by Lemma 3.7)
=* Tr^(/3) = 
However, p was chosen such that TrK/J:{P) = 1. Thus, Tr = 1
and all lines of the form y = a^2n~^kx, k ^ m, are exterior to Qm.
For every line in B, there is a conic that meets only that line. The removal of
any line l from B results in B \ {1} no longer being a CBS. Thus, B is irreducible.
Observe that \B\ = {y = t2n~lx  t ^ 0} = 2 + 1 which is the number of
lines of a Baer subplane through a point in a Baer subplane of PG(2,22n). A
natural question to ask is whether the lines through a point in a Baer subplane
(Baer lines) are projectively equivalent to the irreducible CBS given in Theorem
3.8? We now show that the answer to that question is yes.
Lemma 3.9 Let ft a2"1. The element
(/^+/?)(! +/32)
' (1 + W + /32)
with j ^ 1,2, lies in the subfield K,*.
Proof:
We show that X lies in K, by showing that AT2"1 = 1. First, observe that
with fi ct2"1,
65
for any k. Now,
X2"1
(ffl+/3)( 1+/92)
{l+P)(0J+02)
_ {f)i +0)2n (l+P2)2" (l+fl)(0J+fl2)
 (i+p)2n(0j+02)2n' (p+m+p2)
_ (p+0)2n(0j+p2) (i+f}2)2"(1+^)
_ (0j+p2)2"(pi+f}) (l+/3)2"(l+/32)
([/P]2n+/32n)(/h+/?2) (l+[/?2]2")(l+/?)
lm2n+[p2]2n){0i+0) (l+[/8]2")(l+/92)
(jj^W+e2) (i+ft)a+fl
fe + ^)(^+^) (l+i)(l+^2)
+f>2) ^(/P+l)(l+/3)
^(pi+PW+JT) i(i+/j)(^+1)
= 0i = L
Since X2"1 = 1 and 1/0,1 lies in /C*.
Theorem 3.10 The lines B' = {y = mx \ m fC} U {x = 0} form an irreducible
CBS in PG{2,22n).
Proof:
We show that B' is an irreducible CBS in PG(2, 22") by finding a projectivity
in PGL(3, 22") that maps the irreducible CBS B given in Theorem 3.8 to B'. Let
66
/3 be as defined in Lemma 3.9. Consider the element
A =
1 0
1+0 1+0
1 1+02 02 1+02 0
0 0 1
in PGL(3,22n). It is a simple argument to show that A is nondegenerate and that
A leaves (0, 0,1) fixed. Next, we show that A maps the lines B {y = t2n~lx \ t ^
0} into the lines in B' {y = mx \ m 6 K,} U {x = 0}.
It is easy to verify that A sends the line y = x in B to the line y = x in B',
the line y = f3x in B to the line y = 0 in B', and the line y = /32x in B to the
line x = 0 in B'. We show now that the remaining lines in B are mapped to the
remaining lines in B'.
For j ^ 0,1, 2, we denote the remaining lines in B' by
1
0
. Now,
1 0 0 (01+0H1+02) X
1+0 1+0 (1+0X0J+02)
1 1+0* 02 1+02 0 1 = 1 = 1
0 0 1 0 0 0
From Lemma 3.9, X lies in 1C*, therefore X is of the form a^2n+1^k, k ^ 0. A
maps the lines in B to distinct lines in B', which are the Baer lines through the
point (0,0,1) in PG(2,2n). Thus, B' is projectively equivalent to B, and B' is an
irreducible CBS in PG(2,22n).
67
3.4 Searching for Minimum CBSs
Having established that CBSs exist and having provided a construction of
CBSs, we devote this section to finding minimum CBSs and obtaining upper and
lower bounds on the sizes of these CBSs. We develop a model that efficiently and
effectively searches for minimum CBSs using optimization software. The results
of the search are given at the end of this chapter.
Due to the combinatorial explosion inherent in exhaustive searches, we develop
a more sophisticated technique to find an efficient algorithm for locating minimum
CBSs. Reducing the size of the problem is vital to the algorithm. For this reason,
we review definitions and properties introduced in Chapter 2 that are relevant to
the algorithm.
A collineation from a projective plane to another one is a bijection of the
points and of the lines which preserves incidence. The set of all collineations of
PG(2,
A projectivity is a collineation which can be represented by a 3 x 3 nonsingular
matrix. Projectivities of the line PG(1, q) can be represented by 2 x 2 nonsingular
matrices. The group of projectivities of the plane is denoted by PGL(3,q), and
the group of projectivities of the line is denoted by PGL(2, q). [35]
PGL(3,g) is transitive on the points and lines of PG(2,
is transitive on the points of PG(1, q). Any map in PGL(3, q) preserves incidences
between points and lines and is also transitive on conics of PG(2, q). So, any map
in PGL(3, q) will map conics to conics. Every conic has a unique nucleus, hence,
68
any map that sends a conic, C, to itself will fix the nucleus. Since C is stabilized
and the nucleus is fixed, the remaining points in the plane are mapped to each
other. In Chapter 2.2.2.1, we showed the stabilizer of C has three orbits in the
plane:
1. the points of C;
2. the nucleus of C;
3. the rest of the points in the plane.
Since the stabilizer of a conic has three orbits in the plane, the stabilizer of a conic
C is transitive on the set of points that are neither on the conic nor equal to the
nucleus.
Denote the lines through a point P with nonhomogeneous coordinates [f], if
the line is nonvertical, and [oo], for the vertical line through P, and denote the
lines through a point Q with nonhomogeneous coordinates [u], if the line is non
vertical, and [oo], for the vertical line through Q. Now, if an element g G PGL(3, q)
maps the point P to the point Q, then there is an element
a b
h =
c d
with the property that for any line l through P with coordinate [t] or [oo], the
coordinate of the image of l under g is given by
u=uTd ifbt + d^O
oo, otherwise.
The following example illustrates this concept.
G PGL(2, q)
69
Example 9. [55]
Let P = (0,0,1) and Q = (0,1,0). The line [t] through P (and not Q)
t
containing the points (1 ,t,z) for all z G GF(g) is [t] =
1
0
and the line [u]
through Q (and not P) containing (l,y,u) for all y G GF(q) is [it] =
u
0
1
. We
wish to send P to Q, fix the line PQ, and send the remaining lines through P to
the remaining lines through Q. Let A G PGL(3,g) be given by
an ai2 ^13
0 a22 23
0 1 0
Since A G PGL(3, g), det(A) ^ 0 implying that both an and a23 are nonzero.
Observe that PQ is stabilized by A, but, more importantly, P is mapped to Q.
A line [f] through P consists of the points {(1 ,t,z) \ z G GF(g)} U {P}, and a
line [it] through Q consists of the points {(1, y, u)  y G GF(g)} U {Q}. Because A
maps P to Q, if A maps the set {(1 ,t,z)  z G GF(g)} to {(1, y, it)  y G GF(g)},
then A maps the lines [t] through P to the lines [a] through Q. This implies that
(1, t, z) A (an + Of, 012 + a22t + z, 013 + a23^).
Now,
(1, t, z) A (an, ai2 + 22^ + z, ai3 + a23t)
__ [1 ai2+a22t+z Qi.2+a2at ]
V an )
70
In this situation, the element h PGL(2, q) is given by
23 ^13 a b '
0 an c d
6 PGL(2,q).
Given a point P and a conic C such that P Â£ C and P is not the nucleus of C,
the absolute trace function is used to classify the lines through P with respect to
C as secant, tangent, or exterior lines. Recall that the stabilizer of P in PGL(3, q)
is transitive on conics that P is not on and for which P is not the nucleus. If
C is mapped to another conic C1} the tangent and secant lines of C are mapped
respectively to tangent and secantlines of C\. Thus, for each element in PGL(3,q)
that maps C to C\, there is an element in PGL(2,g) that sends the tangent and
secant lines of C through P to the tangent and secant lines of C\ through P.
Consider the conic C with equation xy + xz + z2 = 0 and nucleus N = (0,1,1).
The point (0, 0,1) is not on C and the q + 1 lines through (0, 0,1) are x = 0 and
mx + y 0, m e GF(q). Using the methods discussed in Chapter 2, the tangent
and secant lines of C through (0,0,1) are easily identified. The line mx 4 y = 0 is
a secant line to C when Tr(m) = 0 and the line x 0 is a tangent line to C.
We identify the lines through (0,0,1) with the elements of GF(q) U {oo} by
mx + y = 0 * (m),
x = 0 > (oo).
Let Sp = {(m)  Tr(m) = 0} U {(oo)} denote the set of tangent and secant lines
of C through (0,0,1). Using the standard duality, we dualize so that all the lines
through (0,0,1) become points on the line z = 0 with homogeneous coordinates.
71
That is,
(m) : mx + y = 0 i> (m, 1, 0),
(oo) : x = 0 i> (0, 0,1).
Note, the set Sp = {(m)  Tr(m) = 0} U {(oo)} can still be used to identify the
points in the dual plane that correspond to tangent and secant lines in the original
The image of Sp under PGL(2,g) is  Tr(x) = 0} U {f}} where it is un
derstood that if bx + d = 0, then = oo, and if b = 0, then  = oo.
To summarize the procedure, find a conic C and fix a point P $ C such that
P is not the nucleus of C. Identify the tangent line and secant lines through P
with respect to C. Then dualize and parameterize to obtain a set of parameters
for the points in the dual plane that correspond to tangent and secant lines of the
conic in the original plane. Using collineations of the line PG(l,g), map this set
of parameters to another set of parameters representing tangent and secant lines
of another conic in PG(2,g). Once all possible parameter sets corresponding to
tangent and secant lines have been generated, a CBS can be found by selecting a
representative from each of these image parameter sets. A minimum CBS is found
by selecting a representative from each of these parameter sets in such a way as
to get the smallest number of distinct representatives.
plane.
(m, 1)  (am + c,bm + d) =
c d
J
72
Example 10.
Consider this situation in PG(2,4) with GF(4) = {0,1, a, a2} such that
a2 = a + 1. Observe that Sp = {0,1, oo} and the distinct images sets of Sp un
der PGL(2, q) are {0,1, oo}, {0, a, a2}, {0, a, oo}, {0,1, a2}, {0, a2, oo}, {0,1, a;},
{a,a:2,oo}, {l,a,oo}, {1,gi2,oo}, and {l,a,a2}.
Scanning this list of image sets shows that at least one of the elements 0,1, oo
appears in each of the image sets. When this information is translated back to
the original plane, we find that the lines y = 0, y = x, and x = 0 form a conic
blocking set in PG(2,4). As shown earlier, in PG(2, 4) any set of three concurrent
lines will form a CBS. The 10 image sets listed above give all possible parameter
choices for three concurrent lines through the point (0,0,1). In fact, any one of
the 10 image sets is a conic blocking set which is not difficult to verify by hand.
This example is unique, since each one of these parameter sets represents a CBS
and this is the only projective plane of even characteristic with this property.
As the order of the plane increases, it is no longer feasible to do a hand search
for minimum CBSs. For this reason, the computer is used to find the minimum
CBSs. This is what we now discuss.
We start with the set of points Sp = {{m)  Tr(m) = 0} U {(oo)} which
represents a set of concurrent tangent and secant lines of a specific conic. And,
we use the collineations in PGL(2,g) to generate the image sets of Sp. We put
these sets in an array, A, such that
the columns of A are the points of the line z = 0,
the rows of A are the images of the set Sp,
73
the entries are given by standard incidence, that is, a 1 is stored if the point
is in the image set and a 0 is stored otherwise.
To find a CBS, a collection of columns must be obtained such that each row
of A has a 1 in at least one of the columns in this collection. This set of columns
corresponds to a set of points in the dual plane, which corresponds to a set of lines
in the original plane that form a CBS. To find a minimum CBS, the smallest set
of columns must be found such that each row of A has a 1 in the corresponding
column set. Hence, the problem of finding a CBS can now be viewed as a set
covering problem which is easily turned into an optimization problem.
For this particular optimization problem, in the dual plane, the objective is
to minimize the number of points on the line z = 0, subject to the constraint that
every row of the array A has a representative in the collection of points. Let x
be a binary vector of length q + 1. The vector x is used to keep track of which
columns (points) are selected for the CBS. For instance, if x(i) = 1, then the point
represented by column i has been selected to be in the CBS. If x(j) = 0, the point
represented by column j has not been selected to be in the CBS. We write the
integer programming problem as
9+1
min x(i)
i=1
such that
9+1
A(k, i)x(i) > 1.
il
It is not difficult to visualize how stating the problem like this leads to a
solution. If any row of A is picked and multiplied by x, a nonnegative integer is
obtained, for we are only multiplying 0s and ls. If for some row of A, a 0 is
74
obtained by multiplying by x, then there is not a representative in that image set.
Hence, x cannot represent a CBS.
Since the action of PGL(3, q) on the points a projective plane is 3transitive,
it is possible to make the problem of finding minimum CBSs more efficient. By
the Fundamental Theorem, we are free to select any three points to always be
in the CBS. Any image set that has a 1 in the column corresponding to one of
these three chosen points, automatically has a representative in the set. Therefore,
there is no need to store this image set in the array A. It is only necessary to
keep track of the image sets with 0s in the columns of the three chosen points.
Since the remaining image sets have 0s in the columns of the three chosen points,
there is no need to store these columns in A. Hence, the optimization problem
can be restated so that x is a binary vector of length q + 1 3 q 2. Then the
IPproblem is
92
min ^ x{i)
i=i
such that
92
yt A(k, i)x(i) > 1.
21
The optimization software package called Cplex [39] is used to search for the
optimal solution. Cplex uses a branch and bound algorithm to find the optimal
solution. The branch and bound algorithm first solves the integer programming
problem as a linear programming problem by relaxing the integrality conditions.
That is, it allows for fractional solutions. If the resultant solution is integer, the
problem is solved. Otherwise a tree search is performed which guarantees opti
mality. The branch and bound algorithm is an efficient algorithm that guarantees,
in our setting, finding a minimum conic blocking set. For a simple explanation of
75
the branch and bound process, see Appendix C. For full details of the branch and
bound algorithm, see [73].
Table 3.5 lists the size of a minimum CBS and the minimum CBSs as found
by Cplex are found in Appendix A.
Q Minimum CBS Sizes
22 3
23 5
24 5
25 8
26 9
27 9
Table 3.5: Minimum CBS Sizes
A complete search for minimum CBSs by Cplex in PG(2,2h), h > 8, was not
feasible. As h increases, the size of the array surpasses the builtin limitations on
the number of rows in the array. Also, as h increases, a substantial amount of time
is required for Cplex to check all nodes of the tree. For instance, in PG(2,28),
Cplex located a CBS of size 13, and after nearly two months of searching the tree,
it had not located a smaller CBS. The program had to be terminated, due to
overwhelming memory usage on the machine, before it could verify that 13 was
the size of the minimum CBS in PG(2, 28).
3.5 Bounds on the Sizes of Minimum Conic Blocking Sets
In this section, upper and lower bounds are obtained for the size of a minimum
conic blocking set.
76
For the purposes of obtaining a lower bound, let q 2h, tr(x) denote the
absolute trace of an element x G Â£ GF(g), and let V AG(h, 2) be the
vector space over GF(2) represented by Â£ under addition. For 0 ^ a G Â£, let
fa : Â£ y GF(2) be given by x i tr(ax). Let TLa ker(/Q). Clearly, fa is additive.
This implies that fa is a group homomorphism from Â£ to GF(2). Hence, ker(/a)
is a normal subgroup. Since ker(/a) is a subgroup of Â£, it is a subspace of V. The
rank of the image space of fa is 1. Hence, the rank of the overlying vector space
minus 1 equals the rank of the kernel of fa, that is,
rank(H) 1 = rank(ker(/a)).
Hence, TLa = ker(/a) is a hyperplane in AG(h, 2).
Lemma 3.11 [55] There are precisely q 1 subgroups of AG(h, 2) = Â£{+) of
index 2. They are the 1ia, for
Proof: Suppose Ha = 'Ht with a, 6 ^ 0. This implies that tr(aa;) = 0
tr(bx) 0 Vx Â£
^ tr(aa;) = tr(6x) Vx G Â£
tr(ax bx) = 0 Vx Â£ Â£
tr((a b)x) 0 Vx G Â£.
This is a contradiction, since x ranges over Â£, (a b)x is a linear function and
therefore, there is some x for which tr((ab)x) 1. Hence, all the Tta are distinct.
From the paragraph proceeding Lemma 3.11, TLa is a hyperplane in AG(h, 2).
As there are q 1 choices for nonzero a, there are q 1 subgroups TLa. The number
of points of PG(h 1,2) is the number of nonzero vectors in V. By duality, the
number of points in PG(h 1, 2) equals the number of hyperplanes in PG(/i 1, 2).
77
So, there are = 2h 1 = q 1 hyperplanes in AG(h, 2). Hence, the 7ia are
all the hyperplanes of AG(h, 2).
Observation 3.12 Consider the conic y2 = Â£xz, a / 0, with nucleus (0,1,0).
This conic can also be written as {(a,t,t2) \ t Â£ GF(q)} U {(0,0,1)}. Let l be the
line x = 0 and P the point (0,1,1). The remaining lines through P have equations
y = bx + z for b Â£ GF(q). The line y = bx + z is external to the conic if and only
if = 1 <*=> Tr(ab) = 1. So, for fixed nonzero a, the external lines through
P to this conic are those with slope b such that Tr(ab) = 1.
Observation 3.13 Consider the conic y2 + ^x2 + ^xz = 0, with nucleus (0,1,0),
where c is fixed such that Tr(c) = 1, and a / 0 Â£ GF(q). This conic can also be
written as {(a, t + c, t2) \ t Â£ GF(q)} U {(0,0,1)}. Let l be the line x = 0 and let
P be the point (0,1,1). The remaining lines through P have equations y = bx + z
for b Â£ GF(q). The line y = bx + z is external to the conic if and only if
Tr
b2 +
1 ^ Tr{b2a2 + c2) = 1
=> Tr(ba) + Tr(c) = 1
<*=> Tr(ba) 0.
So, for fixed nonzero a, the external lines through P to this conic are those with
slope b such that Tr(ab) = 0.
Theorem 3.14 If B is a minimum CBS in PG(2, 2h), then \B\ > h.
Proof:
Let B be a CBS which consists of a set of concurrent lines through the point
P in PG(2,(/). There exists a line l through P and not in B, else \B\ q + 1
78
and we are done. We may choose coordinates in such a way that l is assigned the
nonhomogeneous parameter oo. The other lines through P are assigned distinct
elements of GF(q). Since B is a CBS, it must block all conics tangent to l.
In the preceding two observations, we showed that the external lines through P
to such a conic have parameter sets of the form {b  Tr(a6) = 0} or {b  Tr(ab) = 1},
for any nonzero a. Moreover, by varying the conic, all such parameter sets arise.
Hence, B lies in no set of this form. (If the parameter set for B was contained in
one of these sets, then a conic would exist outside of the conic blocking set.)
Consider the vector space V over GF(2) represented by GF(q) under addition.
By Lemma 3.11, these parameter sets are all the hyperplanes of the corresponding
affine space AG(/i, 2). As B is contained in no hyperplane of AG(h, 2), B contains
a linearly independent set of vectors whose span is AG(/i, 2). (A set of vectors
not contained in any hyperplane must generate the whole space.) A linearly
independent set of vectors whose span is AG(h, 2) contains h vectors. So, \B\ > h.
Theorem 3.15 If B is a minimum CBS in PG(2,2h), then \B\ < 2h + 1.
Proof:
As shown in Section 3.4, the sets for which we have to find a set of representa
tives are the images of Sp = {m  Tr(m) = 0} U {oo} under PGL(2,
the function : x i> x + b where Tr(6) = 0. It is clear that tj, maps the set Sp
to itself. Since there are q/2 elements of trace 0 in Â£, the size of the stabilizer of
Sp, PGL(2, q^spl, is at least q/2. By the OrbitStabilizer theorem,
79
orbit of 5p = PGL(2, q) : PGL(2,?)5p
There are at most 2(q2 1) distinct image sets of Sp of size (q+2)/2. These image
sets give rise to at most 2{q2 1) complementary sets of size q + l (
So there are 2(q2 1 )(9^2) subsets of size n that miss some conic, and there are
(9^1) subsets of size n. If
q + l
n
> 2(q2 ~ 1)
q/2
n
then there is a CBS of size n. Now, suppose n 1 > 21og2(g), then we have that
n 1 > log 2(q2)
2n1 > q2
2n_3 > ?2~^+8, since q > 2
2n*{q+\)q{q\) V to ST + i)(9 i) ($)(Â¥) (*r)
=> {q + i)q(q  l)(q2){q + l  (nl))>2(q2  l)(i)(li2)... (2z2fezl2)
c:1) > 2(
So (9^1) > 2(q2 1) (9^2) when n > 2 log2{q) + 1 = 2h + 1. Thus, \B\ <2h + l.
Thus, we have shown that if B is a minimum CBS in PG(2,2/l), then h <
\B\ <2h+l.
3.6 Chapter Summary
We have produced CBSs using the trace function and the method used to
generate these CBSs can be mimicked using any additive function. In PG(2,2/l),
80
where h is even, these CBSs are irreducible and projectively equivalent to a set of
lines through the origin in a Baer subplane. Table 3.6 illustrates the sizes of the
CBSs found by methods presented in this chapter.
q Trivial Sizes TraceFlock Sizes Baer Lines Sizes
2 2
4 3 3 3
8 5 5
16 9 9, 5 5
32 17 17
64 33 33, 17, 9 9
128 65 65
256 129 129, 65, 17 17
512 257 257, 65
1024 513 513, 257, 33 33
Table 3.6: Construction Sizes
We developed a model to aid in the search for minimum CBSs. Due to com
puter and software limitations, we were only able to perform a complete search for
minimum CBSs for q < 256. To obtain small CBSs for 256 < q < 1024, we used
either an adhoc method of selecting potential CBSs and checking, or we employed
a greedybased algorithm to search for small CBSs. It is believed that with more
sophisticated programming techniques, finding minimum CBSs in PG(2, 256) and
PG(2, 512) using commercial optimization software should be feasible. Finally, we
gave upper and lower bounds on the sizes of minimum CBSs in PG(2,g).
81
Table 3.7 illustrates the minimum CBSs found and the corresponding bounds.
Let q denote the order of the plane, U.B. denote the upper bound, L.B. denote
the lower bound, and S.S.F. denote the size of the smallest set found by one of
the following methods: the branchandbound algorithm contained in Cplex; a
surrogatebased heuristic algorithm, written by G. Kochenberger [47], based on a
greedy algorithm; or an adhoc method of selecting points and checking if these
points form a CBS. A indicates that the smallest CBS found is not a minimum
CBS.
Q L.B. S.S.F. U.B.
22 2 3 5
23 3 5 7
24 4 5 9
25 5 8 11
26 6 9 13
27 7 9 15
28 8 13* 17
29 9 15* 19
210 10 23* 21
Table 3.7: CBS Bounds and Sizes
Appendix A contains a listing of the parameters for CBSs with sizes in Table
3.7.
82
4. CBSs in Planes of Odd Order
In this chapter, we focus on CBSs in planes of odd order. Properties of semi
field flocks are used to prove that our constructions give CBSs in PG(2,p/l). We
give theoretical lower and upper bounds on the sizes of minimum CBSs. Two mod
els are developed which allow efficient searching for minimum CBSs. Examples of
minimum CBSs are located in Appendix B.
4.1 Introduction
Throughout this chapter, let Â£ GF^*) = GF(g), K = GF(pd), T GF(p),
and 7r = PG(2,<7), where p is an odd prime, h > 1 and d\h such that d ^ h.
Clearly, 1C = T if d = 1. Let tr(t) denote the relative trace function, TrÂ£/lc{t) =
d j/l 1
t + tp +  + tp .
In Chapter 2, we saw that all projective planes have conic blocking sets. The
next theorem sharpens that result by showing that just over half the lines through
a point are enough to form a CBS.
Lemma 4.1 Any set of ^ + 1 concurrent lines in PG(2, q) form, a CBS.
Proof: Let B be a set of ^ + 1 concurrent lines. For the sake of obtaining
a contradiction, assume that there is a conic C contained in the ^ lines of Bc.
Since each line of Bc contains at most two points of C, we account for at most
2 (2^) = q 1 points of C. But, as C contains q\1 points, C cannot be contained
in Bc and thus, B is a CBS.
We now consider CBSs in PG(2, 3), so that the remainder of the chapter can
83
be devoted to finding small CBSs in PG(2,p/l), ph > 3, using more sophisticated
techniques than that of Lemma 4.1.
Theorem 4.2 A CBS in PG(2, 3) contains at least three lines.
Proof: By Lemma 4.1, any set of three concurrent lines form a CBS, so that
any set of concurrent lines with more than three lines in it will also be a CBS. It
remains to show that any pair of concurrent lines do not form a CBS.
Suppose C is a CBS consisting of two concurrent lines. The complement of
C also consists of two lines for which we can pick four points, two on each of the
complement lines, no three collinear. These four points form an oval which is
therefore a conic. Since the complement of C contains a conic, C is not a CBS and
no pair of lines in PG(2,3) can be a CBS.
4.2 The TraceFlock Construction
The process of finding a CBS consists of identifying a set of lines through a
point such that all conics in 7r have at least one secant or tangent line in this
set. For the CBS construction given in this section, n is coordinatized so that
P = (0,1,1) is the point of concurrency. Note that the lines through P are x = 0
and y = mx + z where m 6 GF(q). Since we will insist that x 0 is not a line of
the CBS, an equivalent problem statement is to identify the slopes of the lines of
the form y mx + z such that every conic in 7r meets these lines. We begin by
examining the size of the range of a specific function in GF(q).
Lemma 4.3 If g : Â£* Â£ is given by g(t) = for t ^ 0, then \Range(g) \ =
ph~d + \.
84
Proof: To show that the size of the range of g is ph d + 1, we show that Â£
can be partitioned into ph~d + 1 blocks: one of size ph~d and ph~d blocks of size
pd 1.
Let t Â£ Â£*, then
h(t) = 1 <*=>
tr(t) t
tr (t) t =
& tr(f) = 0.
1
t
Since the trace function is an additive homomorphism from Â£ onto /C, ker(tr) is
a normal subgroup of Â£. We have that ker(tr) = Â£//C = = ph~d. So,
g(t) 1 t is one of the ph~d 1 nonzero elements in Â£ with trace 0. Hence,
there is one block of Â£ that contains the ph~d elements with trace 0.
Now, we show that the remaining elements in Â£ are partitioned into blocks of
size pd 1, giving ph~d blocks. To do this, we first determine when g(t) = g(Xt)
for A G Â£ \ K.
g{t) = g{xt)^Mzl
tr(Af) A t
A t
Atr(f) At = tr(Af) At
<Â£> Atr(f) = tr(At).
As tr : Â£ > /C, we have that tr(Af), tr(t) Â£ JC. But, since A Â£ Â£ \ fC, Atr(t) Â£
K. tr(t) = 0. We see that g(t) = g(Xt) for some A Â£ ^ \ /C iff i is a nonzero
element with trace 0. That is, t Â£ ker(tr).
Observe that g(t) = g(Xt) for t Â£ ker(tr) for any A Â£ 1C*. Let T0 = {x Â£
Â£*  tr(a;) = 0}. Then t Â£ T0 & g(t) = 1. Now, Â£\T0 = phph~d = ph~d{pd1)
85
and we see that g partitions Â£ into ph~d + 1 blocks. There is one block containing
ph~d elements with trace 0, and the remaining elements of Â£ are split into ph~d
blocks of size pd 1, one for each value of g ^ 1. Thus, Range(g) = ph~d + 1.
e
pdl Ci. pdl Pdi
pdl PdJ Pdi Pdi
pdl pdl Pd1 pi Pdi
pdl pdl Pd1 Pdi Pdi
pdl pdl i K Pd1 \ Ph d i j i
pdl Pd1
Figure 4.1: A partitioning of Â£
If h is prime, then tr(f) is the absolute trace of t and Range(^) = ph~l + 1.
If h is composite, then there exist a g such that Range(
words, when h is composite, g can be defined using a relative trace with respect
to some subfield, which allows for a smaller range than the one obtained by using
the absolute trace.
In Section 2.2.3, we defined a flock of a cone K with vertex V to be a set of
q planes in PG(3,g) not through V which do not intersect on the cone. For the
results given in this section, we may assume that the base of the cone is contained
in the plane w 0.
86
The q planes of a KnuthKantor flock (for which we use the abbreviation
KKflock) have the form
7rt : xt mtaz + w = 0,
where m is a fixed JZf G Â£ and a a nonidentity automorphism of Â£. Any two
distinct planes of the KKflock, irs and 7r(, meet in a line, and when this line is
projected to the plane w = 0, the line has equation
x = m(t s)cr~1z.
The size of the set of KKlines, {x = m(t s)c~lz}, is determined by the auto
morphism minus one, o 1. Multiplying by a nonzero constant will not affect
the size of the set of KKlines. By Theorem 2.4, we have that any nonidentity
automorphism in Â£ has the form t > tpk, where 1 < k < h 1. Any image
set of a function of the form tpk~l has the same size as the set of slopes of the
KKlines, since these image sets are generated by the same type of function, that
is, a variable raised to an automorphism minus one. So, we can say that any set
of slopes generated from functions of the form tpk~1, where 1 < k < h 1, has the
potential to be projectively equivalent to the slopes corresponding to KKlines.
Lemma 4.4 In Â£, the size of the image set of g(t) = tpk~l, 1 < k < h 1, is
where d = gcd(/c, h).
Proof: For 1 < k < h 1, define fK(t) = tpk and gK{t) = tpk~l, for
t 0. Let d gcd(k,h). Since fK is an automorphism of Â£, fK has a fixed field
87
K = GF{pd). For A + 0,
9K(t)=9KW^1 = ^1^1
1 = Ap*_1
=> A = Ap*
A e 1C.
So, gK(t) gK{Xt) <=> A is in the fixed field of fK(t). Since there are ph 1 nonzero
elements in 8, for each gK, 8 is partitioned into blocks of size pd 1. Therefore,
there are different values in the image of gK.
The previous lemma states that the set of slopes corresponding to nonlinear
KKflocks have size where d \ h and d < h. We determine when the size
of the slopes of the KKlines, KK, of a nonlinear KKflock are the same as the
Range(^K) for the gK that were defined previously. The case of gK being defined
by the absolute trace function is examined first. That is, we determine when
= ph~l +1 for h > 3. After that, the necessary conditions for = ph~d +1
are determined.
Lemma 4.5 If h > 3 and p is an odd prime, ^ Ph~l + 1
Proof: Assume Ph~l + 1 Since the RHS is an integer, the LHS must
also be an integer and d must divide h. We first obtain bounds on the size of d.
As d  h, clearly d < h. If d h, then = 1 ^ Ph~x + 1 since p is an odd
, h1
prime. So, d ^ h. If d = 1, 2^ = ^ p1 ^ ph~l + 1 unless h = 2. But, as h > 3,
p i=0
d ^ 1. Now, d h 1 as this would imply that (h 1)  h, which can only be
true if h < 3.
88
