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 This thesis for the Doctor of Philosophy

degree by Leanne D. Holder has been approved

by

William E. Cherowitzo

Sylvia Lu J. Richard Lundgren Stanley E. Payne Laurel A. Rogers

Date 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 Desarguesian 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 non-trivial constructions of CBSs that rely heavily 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 candidate’s thesis. I recommend its publication.

Signed William E. Cherowitzo

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 can’t 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 wouldn’t. 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, I’d 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 hi-ways, 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 X-Files. I couldn’t 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 can’t 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 didn’t 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 X-Files, 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 \underline{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 Three-Space . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3 Blocking Sets of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.3.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . 46 2.3.2 Bounds on the Size of Irreducible Blocking Sets . . . . . . . . . . . 48 2.3.3 Rédei 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 Trace-Flock Construction . . . . . . . . . . . . . . . . . . . . . . 55 3.3 Irreducible CBSs in PG(2, 2^{h}), 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 Trace-Flock 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 Restricted-Dual Model Summary . . . . . . . . . . . . . . . 104 4.3.1.5 Finding the CBSs in the Set Covering Setting . . . . . . . . . . . 105 4.3.2 Secant-Tangent Mapping Model . . . . . . . . . . . . . . . . . . . . 108 4.4 Small Conic Blocking Sets in PG(2, q^{2}) . . . . . . . . . . . . . . . . . 112 4.5 Bounds on the Sizes of Minimum Conic Blocking Sets . . . . . . . . . 128 4.6 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 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 \underline{Appendix} A. CBS Parameters for q Even . . . . . . . . . . . . . . . . . . . . . . . . 158 B. CBS Parameters for q Odd . . . . . . . . . . . . . . . . . . . . . . . . . 160 C. The Branch and Bound Algorithm . . . . . . . . . . . . . . . . . . . . . 163

\underline{References} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

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 E . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.1 A partitioning of E . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.2 A Collection of Values Q ((λ + k)n) . . . . . . . . . . . . . . . . . . . 124 4.3 The Union of 3-Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4.4 The 3-Cycles for Q(x) = x^{2} + α^{10}x + 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 5.6 Dual Proper Star Flock in PG(3, q) . . . . . . . . . . . . . . . . . . . 150 C.1 A Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

TABLES

Table 3.1 CBS Sizes Given by the Trace-Flock 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 Trace-Flock 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.1 CBSs in Planes of Even Order . . . . . . . . . . . . . . . . . . . . . . 158 B.1 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 1. Projective Geometry Applications

Projective geometry has applications in modern information and communication 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 cryptography, 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 consist 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 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 requirement 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.

(L1) Any two distinct points of L are incident with precisely one line.

(L2) On any line of L there are at least two points.

(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 description. 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.

By designating the ‘outer’ points to represent switches (lines) and the ‘inner’ points to represent users (points), we see that the picture on the right-hand 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 error-correcting aspect of coding theory. 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 transmission 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 insure that the intended message is obtainable from whatever is actually received. One simple approach to this problem is to code the message so that the original content is easily obtainable, even if the coded message received is full of errors.

Figure 1.2: Atmospheric Noise

A basic error-correcting 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 error-correcting 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 Reed-Muller codes. The Reed-Muller code is one of the most studied codes and has been used by NASA for transmission of data.

To examine one of the applications of codes, consider NASA’s 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 Reed-Muller 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 Reed-Muller 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 information. 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 communicate 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 information 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 cryptosystem. 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

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 κ is the number of possible keys to an authentication system, then an attacker could deceive with probability at least 1/\sqrt{κ}. A authentication system with κ keys is called perfect, if the probability that an attacker will be able to insert or substitute a message is only 1/\sqrt{κ}. 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 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 four-space to represent the secret and the shares.

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 problems. In this thesis, we are working out the basic properties of a new concept in projective geometry.

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 +, × such that

1. (K, +) is an abelian group with identity 0;

2. (K^{∗}, ·) is an abelian group with identity 1, 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.1], and the reader is referred to [48] for an in-depth 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.

4. A finite field K of characteristic p has a subfield isomorphic to GF(p) and has p^{h} elements for some h in ℕ.

5. If f(t) is an irreducible polynomial of degree h over GF(p), then

GF(p^{h}) = GF(p)[t]/(f)
= {a_{0} + a_{1}t + … + a_{h−1}t^{h−1} | a_{i} ∈ GF(p), f(t) = 0}.

6. The elements x of GF(q), q = p^{h}, satisfy

x^{q} − x = 0,

and there exists s in GF(q) such that

GF(q) = {0, 1, s, …, s^{q−2} | s^{q−1} = 1};

such an s is called a primitive element of GF(q) or generator of GF(q)^{∗}.

7. Any field of q elements, q = p^{h} is isomorphic to GF(q), which is called the Galois field of order q.

By Property 6, we have that every element in E = GF(2^{n}) satisfies x^{2^{n}} = x, so that x is the square of the element x^{2^{n−1}}. We also remark that every element in E has exactly one square root, since −1 = 1 in E.

Unlike the situation in GF(2^{n}), if E = GF(p^{n}) with p an odd prime, then not every element in E is a square. Those that are not squares are called nonsquares. If λ is a primitive element of E, so that λ^{p^{n}−1} = 1 and λ^{(p^{n}−1)/2} = −1, the even powers of λ are squares; while the odd powers are nonsquares. The element 0 is not considered a square or a nonsquare. Hence, there are \frac{p^{n}−1}{2} squares and the 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 symbol_{}. The following theorem will prove to be useful when we obtain counts of various sums in E.

Theorem 2.2 [24, Thm.67] If S denotes the number of squares σ^{2} in E for which σ^{2} + 1 = and N denotes the number of squares τ^{2} for which τ^{2} + 1 =_{}, we have

\begin{matrix}S = \frac{1}{4}(p^{n} − 5), & N = \frac{1}{4}(p^{n} − 1), & if − 1 = ; \\ S = \frac{1}{4}(p^{n} − 3), & N = \frac{1}{4}(p^{n} + 1), & if − 1 =_{}. \end{matrix}

2.1.1 Polynomials over Finite Fields

Polynomials for which the associated polynomial functions are permutations of a given finite field GF(q) are called permutation polynomials. These polynomials exist over any GF(q) since every mapping of GF(q) into itself can be expressed by a polynomial function. We remind the reader of the obvious, that if the function f is a permutation polynomial of GF(q), then f is one-to-one and onto. Other criteria and properties of permutation polynomials can be found in [48, ch.7]. Definition 2.3 [48] Let GF(q^{m}) be an extension of GF(q) and let α ∈ GF(q^{m}). Then the elements α, α^{q}, α^{q^{2}}, ⋯, α^{q^{m−1}} are called the conjugates of α with respect to GF(q).

Let E = GF(q^{m}) be an extension of K = GF(q^{d}), where d is any divisor of m. An automorphism σ of E over K is a mapping of E onto itself that fixes the elements of K point-wise. Thus, σ is required to be a one-to-one mapping from E onto itself with σ(α + β) = σ(α) + σ(β) and σ(αβ) = σ(α)σ(β) for all α, β ∈ E and σ(a) = a for all a ∈ K. 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 E = GF(q^{m}) over K = GF(q) are exactly the mappings σ_{0}, σ_{1}, ⋯, σ_{m−1}, defined by σ_{i}(t) = t^{p^{i}} for t ∈ F and 0 ≤ i ≤ m − 1.

For example, the automorphisms of GF(2^{4}) are

σ_{0}(t) = t,
σ_{1}(t) = t^{2},
σ_{2}(t) = t^{4},
σ_{3}(t) = t^{8}.

It is clear, from the previous theorem, that the conjugates of α ∈ E with respect to K are obtained by applying all automorphisms of E over K to the element α. The next map we examine is a linear map from E to K, and it is important in the construction of conic blocking sets.

Definition 2.5 [48] For α ∈ E, the trace Tr_{E/K}(α) of α is an additive homomorphism of E into K is defined by

Tr_{E/K}(α) = α + α^{q} + α^{q^{2}} + ⋯ + α^{q^{m−1}}.

If K is the prime subfield of E, then Tr_{E/K}(α) is called the absolute trace of α. Otherwise, Tr_{E/K}(α) is called a relative trace of α over K.

We see that the trace of α over K is the sum of the conjugates of α with respect to K. For example,

Tr_{GF(16)/GF(2)}(t) = t + t^{2} + t^{4} + t^{8},

and

Tr_{GF(16)/GF(4)}(t) = t + t^{4}.

Moreover, Tr_{E/K}(α) is always an element of K.

The following theorem gives several useful properties of the trace function, most notably that the trace function is linear.

Theorem 2.6 [48] Let E = GF(q^{m}) and K = GF(q). Then the trace function Tr_{E/K} satisfies the following properties:

1. Tr_{E/K}(α + β) = Tr_{E/K}(α) + Tr_{E/K}(β) for all α, β ∈ E;

2. Tr_{E/K}(cα) = cTr_{E/K}(α) for all c ∈ K, α ∈ E;

3. Tr_{E/K} is a linear transformation from E onto K, where both E and K are viewed as vector spaces over K;

4. Tr_{E/K}(a) = ma for all a ∈ K;

5. Tr_{E/K}(α^{q}) = Tr_{E/K}(α) for all α ∈ E.

Often it is more convenient for us to denote Tr_{E/K} by tr or Tr when the fields in question are understood. Other properties of the trace function can be found in the first chapter of [35]. When q is even, we may express E = Υ_{0} ∪Υ_{1} where Υ_{0} is the set of elements of absolute trace 0, and Υ_{1} is the set of elements of absolute trace 1. Then, we have the additional properties:

(a) 0 ∈ Υ_{0};

(b) q = 2^{2m} ⟺ 1 ∈ Υ_{0};

(c) q = 2^{2m+1} ⟺ 1 ∈ Υ_{1};

(d) t ∈ Υ_{i} ⟺ σ(t) ∈ Υ_{i} for all automorphisms σ;

(e) s ∈ Υ_{i}, t ∈ Υ_{j} ⟹ \begin{cases}s + t ∈ Υ_{0} if i = j, \\ s + t ∈ Υ_{1} if i ≠ j. \end{cases}

(f) |Υ_{0}| = |Υ_{1}| = q/2.

It is easy to show that Tr(t^{2}) + Tr(t) = 0 for all t ∈ E. 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 equations in a finite field of order q. We can determine the number of irreducible factors of a quadratic equation,

ax^{2} + 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 insufficient 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

Δ = b^{2} − 4ac.

There are three cases:

1. if Δ = 0, then (2.1) has the unique solution x = −b/(2a);

2. if Δ is a nonsquare in GF(q), then (2.1) has no solutions in GF(q);

3. if Δ is a square in GF(q), then (2.1) has two solutions x = (−b ± \sqrt{Δ})/(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 δ.

(a) First, if b = 0, then (2.1) becomes ax^{2} + c = 0, and the unique solution to (2.1) is given by x = \sqrt{c/a}.

(b) If b ≠ 0, we can multiply (2.1) by a/b^{2} to obtain the equation \frac{a^{2}x^{2}}{b^{2}} + \frac{ax}{b} + \frac{ac}{b^{2}} = 0. Let y = ax/b and δ = ac/b^{2}, so that (2.1) becomes

y^{2} + y + δ = 0.  (2.2)

Then, δ is the invariant of equation (2.1) and also of (2.2).

As mentioned in the previous section, Tr is a homomorphism into K = GF(2), i.e., Tr(δ) = 0 or 1.

1. If Tr(δ) = 1, then (2.2) and so (2.1) have no solutions.

2. If Tr(δ) = 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 cursory 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 obtaining 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 + 1, q) be an (n + 1)-rank vector space over the field GF(q) with zero element 0. We view the elements of V (n + 1, q) as the (n + 1)-tuples of the form (x_{0}, x_{1}, ⋯, x_{n}) where the x_{i} are in GF(q). 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 ∈ V \ {0}, then X is equivalent to Y if Y = tX for some t ∈ GF(q)^{∗} = GF(q) \ {0}. With this equivalence relation in mind, we can form the n-dimensional projective space over GF (q), denoted P G(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 (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 ∩ T) + rk(S ∪ 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 Ω = 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 Ω.

First, the relationship between two distinct planes, π_{1} and π_{2}, in Ω is examined. If π_{1} and π_{2} lie in a common 3-dimensional 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 π_{1} and π_{2} do not lie in a common 3-dimensional subspace of Ω, π_{1} and π_{2} must intersect in a point, because their union (span) would have rank four. Let P, Q, and R be three noncollinear points in Ω. 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 Ω, which is a projective plane.

Second consider the incidence relationship between a line l and a plane π, both in Ω. If l meets π, l either meets π in a point or is entirely contained within π. Suppose two points of l are in π. Then since π is a vector subspace, the span of any two points that lie in π also lies in π. In this case, it must be that l is entirely contained in π.

If Π_{1} and Π_{2} are two spaces PG(n, q) with n ≥ 2, then a collineation Γ : Π_{1} → Π_{2} is a bijection which preserves incidence; that is if Π_{r} ⊂ Π_{s}, then Π_{r}Γ ⊂ Π_{s}Γ, where Π_{r} and Π_{s} are subspaces of Π_{1}. For instance, Γ maps collinear points to collinear points and concurrent lines to concurrent lines. If S is a set of points in PG(2, q) with the property that no three are collinear, Γ 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)] Suppose {P_{0}, …, P_{n+1}} and {P′_{0}, …, P′_{n+1}} are both ordered subsets of PG(n, q) of cardinality n + 2 such that no n + 1 points chosen from the same set lie in a hyperplane. Then, there exists a unique projectivity T such that P′_{i} = P_{i}T , 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, q) [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 theorem true in PG(n, q), there is an equivalent theorem true in PG(n, q)^{∗}. That is, 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 r-space in PG(n, q) is an (n − r − 1)-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, q), 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,

Q = n ; ∑ ; \begin{matrix}i, j = 0 \\ i ≤ j \end{matrix} a_{ij}X_{i}X_{j}
= a_{00}X_{0}^{2} + a_{01}X_{0}X_{1} + ⋯,

then the set of points satisfying Q = 0 is a quadric in PG(n, q). For instance, a quadric in PG(2, q) is the set of points whose coordinates (X_{0}, X_{1}, X_{2}) satisfy the homogeneous quadratic equation a_{00}X_{0}^{2}+a_{01}X_{0}X_{1}+a_{11}X_{1}^{2}+a_{02}X_{0}X_{2}+a_{12}X_{1}X_{2}+ a_{22}X_{2}^{2} = 0.

In Sections 2.2.1 and 2.2.3, we further examine the projective line and projective 3-space. Since the bulk of the results pertain to projective planes, emphasis is placed on background material in Section 2.2.2.

2.2.1 The Projective Line

The projective line, PG(1, q), is important for the results developed in Chapters 3 and 4. There are q +1 points of PG(1, q) and they are {(1, 0)}∪{(x, 1) | x ∈ GF(q)}. Each point (x, 1) of PG(1, q) can be represented by the nonhomogeneous coordinate x in GF(q) and the coordinate for (1, 0) is ∞. In the remainder of this dissertation, these points of PG(1, q) are often referred to in terms of the parameters t ∈ GF(q) ∪ {∞}.

A projectivity T of PG(1, q) is given by Y = XT, where X = (x_{0}, x_{1}), Y = (y_{0}, y_{1}) and T = [ \begin{matrix}a & b \\ c & d \end{matrix} ], T ∈ PGL(2, q). The Fundamental Theorem of Projective Geometry states that any three points of PG(1, q) 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), (3, 1), (4, 1), and (1, 0). The projectivity T = [ \begin{matrix}2 & 1 \\ 1 & 1 \end{matrix} ] 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 S_{a,b,c} = {(x, y) ∈ PG(1, q) | ax^{2} + bxy + cy^{2} = 0 for a, b, c ∈ GF(q)}. Then,

Q(1, q) = {S_{a,b,c} | a, b, c ∈ GF(q)}.

There are q^{2} + q + 1 quadrics in Q(1, q), and each quadric is classifiable by examining 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 projective 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 construction 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.

(P1) 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 π be a finite projective plane. Then there is an integer q such that

1. Every point of π is incident with exactly q + 1 lines;

2. Every line of π is incident with exactly q + 1 points; 3. π contains exactly q^{2} + q + 1 points;

4. π contains exactly q^{2} + 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 q^{2} + 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, AF B, CGF, CEB, DGB, and DEF.

Figure 2.1: The Fano Plane

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 1 or 2 mod 4, then there cannot be a projective plane of order q unless q = a^{2} + b^{2} 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 XY Z 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 ∩ XY, AC ∩ XZ, and BC ∩ 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 non-Desarguesian.

Theorem 2.11 If two triangles are perspective from a point, they are perspective from a line.

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(p^{h})

Figure 2.2: Desargues’ Configuration

and coordinatized in the standard way. Such a plane is denoted PG(2, q). 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 definition of a quadratic form over a vector space. Let E = GF(q) and V = E^{3}, viewed as a vector space.

Definition 2.12 A map Q : V → E is called a quadratic form of V provided

(i) Q(cw) = c^{2}Q(w) for all c ∈ E, w ∈ V, and

(ii) for every u, v ∈ 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.

If Q is a quadratic form of V, then Q(v) = 0 implies that Q(cv) = 0 for all c ∈ E. 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 = [ \begin{matrix}ā & b̄ & d̄ \\ 0 & c̄ & ē \\ 0 & 0 & f̄ \end{matrix} ]

is a given upper triangular matrix, then B = A + A^{T} is symmetric. A quadratic form is given by Q(X) = XAX^{T}. The quadratic form Q is nonsingular and its polar form f(u, v) is nondegenerate provided (ē, d̄, b̄)^{T} ∈ Null(B) and not on Q, in other words, 4āc̄f̄− āē^{2} − b̄^{2}f̄+ b̄ēd̄− c̄d̄^{2} ≠ 0. A quadric is

{X ∈ PG(2, q) | Q(X) = XAX^{T} = 0}

or equivalently,

{(x, y, z) ∈ PG(2, q) | āx^{2} + b̄xy + c̄y^{2} + d̄xz + ēyz + f̄z^{2} = 0}.

Moreover, the quadric is a conic provided 4āc̄f̄− āē^{2} − b̄^{2}f̄+ b̄ēd̄− c̄d̄^{2} ≠ 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 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) = XAX^{T} be a quadric and let B ∈ PGL(3, q). Observe that

Q(X) = XAX^{T} = X(BB^{−1}AB^{−T} B^{T})X^{T}
= (XB)(B^{−1}AB^{−T})(XB)^{T}
= Y (B^{−1}AB^{−T})Y^{T}
= Q′(Y),

where Y = XB. Then Q′(X) = (XB)(B^{−1}AB^{−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.4] PGL(3, q) acts transitively on the set of conics of PG(2, q).

We now examine the subgroup of PGL(3, q) leaving a nonsingular quadric in the plane invariant, denoted by PGO(3, q), which can be represented by,

PGO(3, q) = \{A = ( \begin{matrix}a^{2} & ab & b^{2} \\ 2ac & ad + bc & 2bd \\ c^{2} & cd & d^{2} \end{matrix} ) : ad ≠ bc and a, b, c, d ∈ GF(q)\}.

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, q) to the conic C with equation y^{2} = xz. That is, C = {(t^{2}, t, 1) | t ∈ GF(q)} ∪ {(1, 0, 0)}. We show PGO(3, q) is sharply triply transitive on the points of C by first showing that PGO(3, q) 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, q) fixes three points of C.

Let H_{1} = \{( \begin{matrix}a^{2} & ab & b^{2} \\ 0 & ad + bc & 0 \\ c^{2} & cd & d^{2} \end{matrix} ) : a, b, c, d ∈ GF(q)\} ∈ PGO(3, q). For A ∈

H_{1}, observe that (1, 0, 0) · A = (a^{2}, ab, b^{2}) is a conic point. Moreover, the orbit of (1, 0, 0) under H_{1} contains every point of the conic, since a and b cannot both be simultaneously 0. So, PGO(3, q) is transitive on the points of C.

Let H_{2} = \{( \begin{matrix}a^{2} & ab & b^{2} \\ 0 & ad & 0 \\ 0 & 0 & d^{2} \end{matrix} ) : a, b, c, d ∈ GF(q)\} ∈ PGO(3, q) where a, d ≠

0. For B ∈ H_{2}, observe that (0, 0, 1) · B = (0, 0, 1) and so B fixes the conic point (0, 0, 1). Now, (1, 0, 0) · B = (a^{2}, ab, b^{2}) is a conic point. Moreover, the orbit of (1, 0, 0) under H_{2} 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.

Let H_{3} = \{( \begin{matrix}a^{2} & 0 & 0 \\ 0 & ad & 0 \\ 0 & 0 & d^{2} \end{matrix} ) : a, b, c, d ∈ GF(q)\} ∈ PGO(3, q) where a, d ≠

0. For C ∈ H_{3} 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 = (a^{2}, ad, d^{2}) which is a point of the conic. Moreover, the orbit of (1, 1, 1) under H_{3} 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, q) 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

M = ( \begin{matrix}a^{2} & ab & b^{2} \\ 2ac & ad + bc & 2bd \\ c^{2} & cd & d^{2} \end{matrix} ) ∈ PGO(3, q)

fixes the three points (1, 0, 0), (0, 0, 1), and (1, 1, 1) of C. Now, (1, 0, 0) · M = (a^{2}, ab, b^{2}) = (1, 0, 0) implies that b = 0 and (0, 0, 1) · M = (c^{2}, cd, d^{2}) = (0, 0, 1) implies that c = 0, so that

M = (\begin{matrix}a^{2} & 0 & 0 \\ 0 & ad & 0 \\ 0 & 0 & d^{2} \end{matrix} ).

Now, (1, 1, 1) · M = (a^{2}, ad, d^{2}) = (1, 1, 1), and we have that a = d. Hence,

M = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )

which is the identity element in PGO(3, q). Thus, there is a unique collineation that fixes three points of the conic, and so PGO(3, q) is sharply triply transitive on the points of the conic in PG(2, q).

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 relationships 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 π 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 ∩ C| = 1,

• l is a secant line to C provided |l ∩ C| = 2,

• l is an exterior line to C provided |l ∩ C| = 0.

There are q + 1 tangent lines, \frac{q(q+1)}{2} secant lines, and \frac{q(q−1)}{2} 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:

• 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, \frac{q}{2} secant and \frac{q}{2} 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 determining 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 E of even characteristic of the form

ax^{2} + bx + c = 0 with a ≠ 0,  (2.3)

the number of solutions to this equation is determined by computing the absolute trace of ac/b^{2}, if b ≠ 0. That is,

1. if Tr(ac/b^{2}) = 1, then there are no solutions, and

2. if Tr(ac/b^{2}) = 0, then there are two solutions.

Let Π be a projective plane of even order and C′ some conic in Π with nucleus N′. The Fundamental Theorem allows us to select any three points of C′ and the nucleus, {P′_{0}, P′_{1}, P′_{2}, 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 y^{2} + 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 y^{2} + 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) · [\begin{matrix}m \\ n \\ p \end{matrix}] = 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 non-tangential 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

m^{2}x^{2} + xz + p^{2}z^{2} = 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 other-hand, 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 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, m^{2}x). 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, m^{2}) lie on both l and C. Assume now that x ≠ 0 and p ≠ 0. We divide both sides of (2.4) by x^{2} to obtain

m^{2} + (\frac{z}{x}) + p^{2} (\frac{z}{x})^{2} = 0

or, rather

p^{2} (\frac{z}{x})^{2} + 1 (\frac{z}{x}) + m^{2} = 0.  (2.5)

If we let \frac{z}{x} = \frac{t}{p^{2}} and δ = m^{2}p^{2}, (2.5) becomes

t^{2} + t + δ = 0.  (2.6)

From the previous section, we can determine how many solutions there are to (2.6) and so (2.5). If Tr(δ) = 1, (2.6) and so (2.5) have no solutions, and therefore l is an exterior line to C. If Tr(δ) = 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

Tr (\frac{ac}{b^{2}}) = \begin{cases}1, & there are no solutions, and the line is exterior \\ 0, & there are two solutions, and the line is secant. \end{cases}  (2.7)

If b = 0, there is one solution and the line is tangent.

Example 6.

Consider the conic with equation C : xy+xz+z^{2} = 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 ∈ GF(q). 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

Ax^{2} + Bxy + Cy^{2} + Dxz + Eyz + Fz^{2} = 0.  (2.8)

If P = (x̄, ȳ, 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̄, ȳ, z̄) ≠ 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.

Example 7.

Let C be a conic in the projective plane PG(2, q), q ≥ 8 and even, and let N be the nucleus of C. Let H 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 H. Any line in the plane must be either a secant line or an exterior line. Let O be the oval which consists of N 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 N 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 H = C ∪ {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.

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 C_{x} and C_{y} be the corresponding conic points on these tangent lines. Let Z be an arbitrary conic point not N, C_{x}, or C_{y}. Let XZ ∩ C = X′ and Y Z ∩ C = Y′. Since PGO(3, q) is sharply triply transitive, there is a unique collineation, Γ, such that ZΓ = Z, C_{x}Γ = C_{y}, and X′Γ = Y′. And so, XΓ = (NC_{x} ∩ X′Z) Γ = (NC_{y} ∩ 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.

Figure 2.3: X and Y Not on a Common Tangent Line Figure 2.4: X and Y on a Common Tangent Line

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 ∩ C and Y′ = Y Z ∩ C. Since PGO(3, q) is sharply triply transitive, there is a unique collineation, Γ, such that ZΓ = Z, T Γ = T, and X′Γ = Y′. Thus, XΓ = (NT ∩ X′Z) Γ = (NT ∩ Y′Z) = Y.

Combining these two cases, we have that there exists a collineation that stabilizes 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.

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 relationships 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 π 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 ∩ C| = 1,

• l is a secant line to C provided |l ∩ C| = 2,

• l is an exterior line to C provided |l ∩ C| = 0.

There are q + 1 tangent lines, \frac{q(q+1)}{2} secant lines, and \frac{q(q−1)}{2} exterior lines with respect to C.

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 \frac{q+1}{2} secants and \frac{q+1}{2} exterior lines through it, an exterior point has exactly two tangents, \frac{q−1}{2} secant and \frac{q−1}{2} 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 + c′z,  (2.9)

where a′ = a/b and c′ = c/b. Substitute (2.9) into (2.3) to obtain the quadratic equation

A′x^{2} + B′xz + C′z^{2} = 0  (2.10)

where A′ = A + Ba′ + Ca′^{2}, B′ = Bc′ + 2Ca′c′ + Ea′ + D, and C′ = c′^{2} + Ec′ + F. If z = 0, there is one solution to (2.10) provided A′ ≠ 0, and y = a′x + c′z is a tangent line. If z ≠ 0, we may divide (2.10) through by z^{2} 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 3 × 3 matrix representing the quadratic form is nonsingular, then the zeros of the quadratic form a conic.

Theorem 2.21 If F = ∑_{i≤j} a_{ij}X_{i}X_{j}, then F is singular if and only if δ = 0, where δ = 4a_{00}a_{11}a_{22} + a_{01}a_{02}a_{12} − a_{00}a_{12}^{2} − a_{11}a_{02}^{2} − a_{22}a_{01}^{2}.

Definition 2.22 [43] 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 point P ∉ C. We call l the polar of P and P the pole of l. The polars of X and Y are the tangent lines to X and Y 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 one-to-one 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 collineations 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

O_{1} = points on Q,
O_{2} = points off Q,

O_{3} = tangents to Q,
O_{4} = secants of Q,
O_{5} = external lines of Q.

Since PGO(3, q) is sharply triply transitive on conics, G(Q) acts triply transitively on O_{1} and O_{3}. For q odd, we have that

O_{2} = O_{2}^{+} ∩ O_{2}^{−},

where

O_{2}^{+} = {external points of Q}, O_{2}^{−} = {internal points of Q}.

Lemma 2.23 [36]

(i) G(Q) act transitively on O_{4} and O_{5};

(ii) G(Q) has two orbits on O_{2}, namely O_{2}^{+} and O_{2}^{−}.

Proof:

Let Q be the set of points that satisfy x^{2} + yz = 0. Consider the action of G(Q) on O_{2}, the points off Q. Since each point of O_{2}^{+} is the intersection of two tangents, Q is transitive on O_{2}^{+}, the external points, and by the polarity on O_{4}, the secants.

Any external line contains an external point. So, to show the transitivity of G(Q) on O_{5}, and by polarity on O_{2}^{−}, it suffices to show the transitivity on the external lines through a particular external point. Let U_{0} = (1, 0, 0) be this point. Then the line l_{t} given by the equation y + tz = 0 is a secant or external line if t is a nonzero square or nonsquare respectively. The projectivity Γ_{c}, c ≠ 0, given by (x, y, z)Γ_{c} = (cx, y, c^{2}z) fixes Q and transforms l_{t} to l_{\frac{t}{c^{2}}} . So, we can pass from any secant through U_{0} to any other secant through U_{0} and any external line through U_{0} to any other external line through U_{0}. So, G(Q) is transitive on O_{5}, the external lines, and by the polarity on O_{2}^{−}, 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 Three-Space

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 threespace that is relevant to the work presented in Chapters 3 and 4. We forego an in-depth 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 three-space.

A plethora of geometrical objects exist in projective three-space; such as ovoids, generalized quadrangles, k-caps, spreads, and flocks. Of these, we are most interested in flocks.

Assume PG(2, q) is a subspace of PG(3, q), and let C be a conic in PG(2, q) with V (the vertex) a point in PG(3, q) \ PG(2, q). 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 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 f, g ∈ GF(q)[x] with f(0) = g(0) = 0. If f 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 f and g are additive.

The Knuth-Kantor semifield flock [44] is one of the three classes of nonlinear semifield flocks known. For q odd and t ∈ GF(q), the planes π_{t} are defined to be:

π_{t} : tx − mt^{σ}y + w = 0,

where m is a fixed nonsquare and σ is an automorphism of the field. These planes define a semifield flock of the cone K. This flock is linear if and only if σ = 1.

Theorem 2.24 [69, 70] In PG(3, p^{2}), for any prime p, the semifield flocks are linear or else they are Knuth-Kantor semifield flocks.

More will be said about the Knuth-Kantor flocks in Chapter 4.

In the past few years, W. Cherowitzo has made significant strides in generalizing 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 coalitions. A blocking coalition is a set of points containing no line but intersecting every line. A minimum blocking coalition is a blocking coalition of smallest cardinality. 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 Π = PG(2, q) is a subset of points of Π which meets every line but contains no line completely; that is, 1 ≤ |B ∩ l| ≤ q for every line l in Π. If |B| = k, B is called a blocking k-set. It follows immediately from the definition that the complement of a blocking set, Π \ B, is also a blocking set.

A blocking set is irreducible if B \ {P } is not a blocking set for any P ∈ B. A blocking set of Rédei type in PG(2, q) is a blocking set of size q + m for which there is some line l ∈ Π for which |l ∩ B| = m. Lemma 2.25 A blocking set B exists in Π if and only if q > 2.

Lemma 2.26 The following are irreducible blocking sets in Π = PG(2, q), when q > 2:

(i) the set B_{1} = {P_{1}P_{2}∪P_{1}P_{3}∪P }\{P_{2}, P_{3}} of 2q points consisting of the points on two sides of a triangle with vertices {P_{1}, P_{2}, P_{3}} and a point P on P_{2}P_{3}, minus the two vertices {P_{2}, P_{3}} of the triangle; (ii) the set B_{3} = (C ∪ l ∪ {P }) \ {P_{1}, P_{2}} of 2q − 1 points, where C is the set

of points of a conic, l is a secant meeting C in P_{1} and P_{2}, and P is the intersection of the tangents to C at P_{1} and P_{2};

(iii) the set B_{2} = (l \ {P }) ∪ {P_{1}, …, P_{q}} of 2q points consisting of a line l minus a point P plus a set P_{1}, …, P_{q} of q points, one on each of the q lines through P other than l, but with P_{1}, …, P_{q} not all collinear; (iv) a Baer subplane PG(2, \sqrt{q}) of PG(2, q) consisting of q +\sqrt{q} +1 points, when

q is a square;

(v) the set of q\sqrt{q} + 1 points of a unital in PG(2, q^{2}).

Of the irreducible blocking sets listed in Lemma 2.26, all are Rédei 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 [14]

(i) If B is a blocking k-set in PG(2, q), then

q + \sqrt{q} + 1 ≤ k ≤ q^{2} − \sqrt{q}.

(ii) A blocking k-set in PG(2, q) with k = q^{2} − \sqrt{q} is the complement of a subgeometry PG(2, \sqrt{q}).

The next result is due to Bruen and Thas [15].

Theorem 2.28

(i) If B is an irreducible blocking k-set in PG(2, q), then k ≤ q\sqrt{q} + 1.

(ii) Equality holds in (i) if and only if B is a Hermitian arc (unital) and q is a square.

2.3.3 Rédei Blocking Sets

From Section 2.3.1, B is a blocking set of Rédei type if B is a blocking set with q + m points containing an m-secant. For any function f : GF(q) → GF(q), let

D_{f} = \{\frac{f(x) − f(y)}{x − y} | x, y ∈ GF(q); x ≠ y\},

be the set of directions determined by f. Lemma 2.29 [35] A blocking set of Rédei 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 k-set consisting of {(t, f(t), 1) | t ∈ GF(q)} ∪ {(1, d, 0) | d ∈ D_{f}}. Consider the lines through a point P on the the line z = 0. Either P is a point of the form (1, d_{1}, 0) for some d_{1} ∈ D_{f} 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 f determines every direction, in which case B contains the line z = 0, or f is linear, in which case B contains the line with equation tx + f(t)y + z = 0. Hence, the line z = 0 is a |D_{f}|-secant and so B is a blocking set of Rédei 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^{(q+1)/2}; then f determines \frac{1}{2}(q + 3) directions and B is an irreducible blocking set of size \frac{3}{2}(q + 1).

2. Let f be the trace function from GF(q) to a subfield GF(q′); then f determines q/q′ + 1 directions, and hence B is a blocking set of size q + q/q′ + 1.

3. If q′ | q, let f(x) = x^{q′}; then f determines (q − 1)/(q′ − 1) directions, and hence B is a blocking set of size q + (q − 1)/(q′ − 1).

Choosing the m-secant to be the line at infinity l_{∞}, we consider the set of directions determined by the set S = B \ l_{∞} of size q. Let S be a set of q points in AG(2, q) = PG(2, q) \ l_{∞} and, with u = (u_{1}, u_{2}), v = (v_{1}, v_{2}), let

D = \{\frac{u_{2} − v_{2}}{u_{1} − v_{1}} | u ≠ v′u, v ∈ S\} ⊂ GF(q) ∪ \{∞\}

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 ⊂ AG(2, q) be a point set of size q = p^{h}, let D be the set of slopes of secants of S, and put m = |D|. Let e, with 0 ≤ e ≤ h, be the largest integer such that each line with slope in D meets S in a multiple of p^{e} 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. p^{e} > 2, where e divides h, and q/p^{e} + 1 ≤ m ≤ (q − 1)/(p^{e} − 1);

4. e = h and m = 1.

For more results on blocking sets of Rédei 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.

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 q-clans, 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 π which meets every conic in π. If every conic in π 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 \ {l} 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 π is a projective plane, then π contains a CBS.

Proof: Let B consist of the q + 1 lines through any point P in π. Clearly, B contains all the points in π. Since every conic in π 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 point, P. The complement of a CBS, B^{c}, consists of the remaining lines through the point P. We say a CBS B is projectively equivalent to another CBS B′ if

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 | m ∈ GF(q)} through (0, 1, 1). Consider the element

A = [ \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & − 1 & 1 \end{matrix} ]

in PGL(3, q). Observe that (0, 1, 1) · A = (0, 0, 1) and

A · [\begin{matrix}m \\ 1 \\ 1 \end{matrix}] = [\begin{matrix}m \\ 1 \\ 0 \end{matrix}].

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 equivalent to a CBS consisting of the lines of the form y = mx, since the projectivity maps conics to conics.

Non-trivial constructions for finding conic blocking sets and upper and lower bounds on minimum CBSs are discussed below. The theoretical and computer 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.

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^{h}). 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 E = GF(2^{h}) = GF(q), K = GF(2^{d}), F = GF(2), and π = PG(2, q), where h > 1 and d|h such that d ≠ h. Certainly, K = F if d = 1. Let tr(t) denote the relative trace function, Tr_{E/K}(t) = t + t^{2^{d}} + ⋯ + t^{2^{d}^{h−1}}.

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 \frac{q}{2} + 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 \frac{q}{2} lines of B^{c}. Since each line of B^{c} contains at most two points of C, we account for at most 2 · (\frac{q}{2}) = q points of C. But, as C contains q + 1 points, C cannot be contained in B^{c} 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, 2^{h}), with h > 1, using more sophisticated techniques than those of Lemma 3.1.

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 = \frac{q}{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 Trace-Flock Construction

Finding CBSs consists of identifying a set of lines through a point such that all conics in π have at least one secant or tangent line in this set. For the CBS construction given in this section, π 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 for m ∈ GF(q). We are able to insure that x = 0 is not a line of the CBS, so an equivalent problem statement is to identify the slopes of the lines of the form y = mx + z such that every conic in π meets these lines. We begin by examining the size of the range of a specific function in GF(q); for this function will determine the slopes of the CBS lines. Lemma 3.3 If g : E^{∗} → E is given by g(t) = \frac{tr(t)+t}{t} for t ≠ 0, then |Range(g)| = 2^{h−d} + 1.

Proof: To show that the size of the range of g is 2^{h−d} + 1, we show that E

can be partitioned into 2^{h−d} + 1 blocks: one of size 2^{h−d} and 2^{h−d} blocks of size 2^{d} − 1.

Let t ∈ E^{∗}, then

g(t) = 1 ⇔ \frac{tr(t) + t}{t} = 1
⇔ tr(t) + t = t
⇔ tr(t) = 0.

Since the trace function is an additive homomorphism from E onto K, ker(tr) is a normal subgroup of E. We have that |ker(tr)| = |E|/|K| = \frac{2^{h}}{2^{d}} = 2^{h−d}. So, g(t) = 1 ⇔ t is one of the 2^{h−d} − 1 nonzero elements in E with trace 0. Hence, there is one block of E that contains the 2^{h−d} elements with trace 0.

Now, we show that the remaining elements in E are partitioned into blocks of size 2^{d} − 1, giving 2^{h−d} blocks. To do this, we first determine when g(t) = g(λt) for λ ∈ E \ K.

g(t) = g(λt) ⇔ \frac{tr(t) + t}{t} = \frac{tr(λt) + λt}{λt}
⇔ λtr(t) + λt = tr(λt) + λt
⇔ λtr(t) = tr(λt).

As tr : E → K, we have that tr(λt), tr(t) ∈ K. But, since λ ∈ E \ K, λtr(t) ∈ K ⇔ tr(t) = 0. We see that g(t) = g(λt) for some λ ∈ E \ K iff t is a nonzero element with trace 0. That is, t ∈ ker(tr).

Observe that g(t) = g(λt) for t ∉ ker(tr) for any λ ∈ K^{∗}. Let T_{0} = {x ∈ E^{∗} | tr(x) = 0}. Then t ∈ T_{0} ⇔ g(t) = 1. Now, |E \ T_{0}| = 2^{h} − 2^{h−d} = 2^{h−d}(2^{d} − 1) and we see that g partitions E into 2^{h−d} + 1 blocks. There is one block containing 2^{h−d} elements with trace 0, and the remaining elements of E are split into 2^{h−d} blocks of size 2^{d} − 1 one for each value of g that is not equal to 1. Thus, |Range(g)| = 2^{h−d} + 1.

Figure 3.1: A partitioning of E

If h is prime, then tr(t) is the absolute trace of t and |Range(g)| = 2^{h−1} + 1. If h is composite, then there exists a g, as in Lemma 3.3, such that |Range(g)| < 2^{h−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, 2^{h}), if the planes π_{1}, π_{2}, ⋯, π_{q}, of a flock of a quadratic cone contain a common point, then F is linear.

We now prove the main result of this section.

Theorem 3.5 In PG(2, 2^{h}) with h ≥ 2, if d | h then there is a CBS of size 2^{h−d} + 1.

Proof:

Consider the additive function f(t) = Tr_{E/K}(t) + t = tr(t) + t, which we use to form the function g(t) = \frac{f(t)}{t} = \frac{tr(t)+t}{t}, t ≠ 0. As shown in Lemma 3.3, |Range(g)| = 2^{h−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:

π_{t} : f(t)x + ty + tz + w = 0 with t ∈ E^{∗}.

There are 2^{h} − 1 planes of this type since t ∈ E^{∗}. 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 π_{s} and π_{t} (s ≠ t) meet in a line which projects from (0, 0, 0, 1) to the line y = \frac{f(s−t)}{s−t}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 2^{h} 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 2^{h} 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| = 2^{h−d} + 1 > 1, so C does not exist and B is a CBS.

In the trace-flock construction, the specific function g(t) = \frac{tr(t)+t}{t} was used to give the slopes of the lines in the CBS. Since g is an additive function divided by t and the size of its image set is known, we used g to form a CBS of size 2^{h−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 trace-flock construction does not give CBSs when q = 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 trace-flock construction described in Theorem 3.5, for small q.

q Guaranteed CBS Sizes

2^{2}  3
2^{3}  5
2^{4}  9, 5
2^{5}  17
2^{6}  33, 17, 9
2^{7}  65
2^{8}  129, 65, 17
2^{9}  257, 65
2^{10}  513, 257, 33

Table 3.1: CBS Sizes Given by the Trace-Flock Construction

For a fixed q, the largest size of a CBS guaranteed by the trace-flock construction is the same size as those CBSs constructed in Lemma 3.1. When h is prime, the trace-flock 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 trace-flock construction gives a CBS of size 33 that blocks the (over 1.12 × 10^{15}) conics in the plane PG(2, 2^{10}), whereas by Lemma 3.1, 513 lines were needed to form a CBS.

3.3 Irreducible CBSs in PG(2, 2^{h}), h even

In this section, we focus on proving that the CBSs given by the trace-flock 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 trace-flock construction, for h even, is irreducible.

Throughout the remainder of this section, let h = 2n, n ≥ 2, d = n, so that E = GF(2^{2n}), K = GF(2^{n}), and F = GF(2). Then g(t) = \frac{Tr_{E/K}(t)+t}{t} = \frac{t+t^{2^{n}}+t}{t} = t^{2^{n}−1}. Let α be a generator of E. Then Range(g) = {1, α^{2^{n}−1}, α^{2(2^{n}−1)}, ⋯, α^{2^{n}(2^{n}−1)}} is a cyclic subgroup of E^{∗} of order 2^{n} + 1. Observe that any element in Range(g) is expressible as α^{(2^{n}−1)k} where k ∈ ℤ_{2^{n}+1}.

In Section 3.2, we showed that the set of lines {y = g(t)x + z} 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 = 2^{2n}. Example 8.

Let h = 4, n = 2, and α be a generator of E. Observe that Range(g) = {t^{3}|t ∈ E^{∗}} = {1, α^{3}, α^{6}, α^{9}, α^{12}} = {α^{3k} | k ∈ ℤ_{5}}. To show that the CBS B = {y = α^{3k} | k ∈ ℤ_{5}} 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 Q_{m} : {(x, y, z) | x^{2} + α^{−3m}yz + z^{2} = 0} where m ∈ ℤ_{5}. Since the nucleus, (α^{−3m}, 0, 0), does not lie on Q_{m}, this quadric is nondegenerate. We show that B is irreducible by showing that the line y = α^{3m}x is a secant line to Q_{m} while all other lines, y = α^{3k}x with k ≠ m, are exterior to Q_{m}.

To determine how the line y = α^{3k}x meets Q_{m}, we examine

x^{2} + α^{−3m}α^{3k}xz + z^{2} = 0
⇔ x^{2} + α^{3(k−m)}xz + z^{2} = 0.

This equation has two solutions if Tr (\frac{ac}{b^{2}}) = Tr (\frac{1·1}{α^{6(k−m)}} ) = Tr(α^{9(k−m)}) = 0. Let k − m = j. Then

Tr (α^{9(k−m)}) = Tr (α^{9j}) = α^{9j} + (α^{9j})^{2} + (α^{9j})^{4} + (α^{9j})^{8}
= α^{9j} + α^{18j} + α^{36j} + α^{72j}
= α^{9j} + α^{3j} + α^{6j} + α^{12j}.

If j = 0, then k = m and Tr(α^{9j}) = Tr(1) = 0 in GF(16). Therefore, when k = m, the line y = α^{m}x is secant to Q_{m}. When j is a fixed element in Z_{5}^{∗}, α^{9j}, α^{3j}, α^{6j}, α^{12j} are distinct. More importantly, α^{9j}, α^{3j}, α^{6j}, α^{12j} are four of the five 5th roots of unity over E^{∗}, with 1 the remaining 5th root of unity. Thus, α^{9j} + α^{3j} + α^{6j} + α^{12j} = 1 and Tr (α^{9j}) = Tr (α^{9(k−m)}) = 1. Since the absolute trace is 1, there are no solutions to this quadratic equation. Therefore, when k ≠ m, the line y = α^{3k}x is exterior to Q_{m}.

Since the removal of any line l from B results in B \ {l} no longer being a CBS, B is irreducible.

Since (0, 0, 1) is on all lines of the CBS, we only need to block conics with equations Ax^{2} + Bxy + Cy^{2} + Dxz + Eyz + F z^{2} = 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 = t^{2^{n}−1}x | t ≠ 0} blocks all of these conics in the plane PG(2, 2^{2n}). 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 β in K with Tr_{K/F} (β) = 1. Since β ∈ K ⊂ E, β = β^{2^{n}}. This implies that for 0 ≤ i ≤ n − 1,

β^{2^{i}} = (β^{2^{n}})^{2^{i}} = β^{2^{n+i}}.  (3.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.6 Let j be a positive integer. Then α^{(2^{n}−1)j+2^{n}(2^{n}−1)j} = 1.

Proof:

α^{(2^{n}−1)j+2^{n}(2^{n}−1)j} = [α^{(2^{n}+1)(2^{n}−1)j}] = [α^{q^{2}−1}]^{j} = 1, ∀α ∈ E^{∗}.

Lemma 3.7 Let j be a positive integer. Then \frac{1}{(α^{(2^{n}−1)j})^{2^{i}}} + \frac{1}{(α^{(2^{n}−1)j})^{2^{n+i}}} = 1.

Proof: Let s = (2^{n} − 1)j. Recall from Lemma 3.6, α^{s2^{i}+s2^{n+i}} = 1. Then

\frac{1}{(1 + α^{s})^{2^{i}}} + \frac{1}{(1 + α^{s})^{2^{n+i}}} = \frac{(1 + α^{s})^{2^{n+i}} + (1 + α^{s})^{2^{i}}}{(1 + α^{s})^{2^{i}}(1 + α^{s})^{2^{n+i}}}

= \frac{(1 + α^{s})^{2^{n+i}} + (1 + α^{s})^{2^{i}}}{(1 + α^{s2^{i}})(1 + α^{s2^{n+i}})}
= \frac{1 + α^{s2^{n+i}} + 1 + α^{s2^{i}}}{1 + α^{s2^{n+i}} + α^{s2^{i}} + α^{s2^{i}+s2^{n+i}}}
= \frac{α^{s2^{n+i}} + α^{s2^{i}}}{1 + α^{s2^{n+i}} + α^{s2^{i}} + 1}
= \frac{α^{s2^{n+i}} + α^{s2^{i}}}{α^{s2^{n+i}} + α^{s2^{i}}}
= 1.

Theorem 3.8 The CBS, B = {y = t^{2^{n}−1}x | t ≠ 0}, is irreducible in PG(2, 2^{2n}).

Proof: Let β ∈ K such that Tr_{E/K}(β) = 1. Consider the conics Q_{m} with equations:

Q_{m}(x, y, z) = x^{2} + α^{(1−2^{n})m}xy + \frac{1}{β^{1/2}} xz + \frac{α^{(1−2^{n})m}}{β^{1/2}} yz + z^{2} = 0,

where m ∈ Z_{2^{n}+1}. The nucleus of Q_{m} is (\frac{α^{(1−2^{n})m}}{β^{1/2}} , \frac{1}{β^{1/2}} , α^{(1−2^{n})m}) and observe that Q_{m}(\frac{α^{(1−2^{n})m}}{β^{1/2}} , \frac{1}{β^{1/2}} , α^{(1−2^{n})m}) = α^{(1−2^{n})2m} ≠ 0, hence Q_{m} is nondegenerate. Express B as the set of lines of the form {y = α^{(2^{n}−1)k}x | k ∈ ℤ_{2^{n}+1}}. We show that when k = m, the line y = α^{(2^{n}−1)m}x is a tangent line to Q_{m}, and when k ≠ m, the line y = α^{(2^{n}−1)k}x is exterior to Q_{m}, for all k ∈ Z_{2^{n}+1}^{∗}.

For a line in B to meet Q_{m}, we must have that

x^{2} + α^{(1−2^{n})m+(2^{n}−1)k}x^{2} + \frac{1}{β^{1/2}} xz + \frac{α^{(1−2^{n})m+(2^{n}−1)k}}{β^{1/2}} xz + z^{2} = 0,

has a solution. This can be rewritten as

(1 + α^{(2^{n}−1)(k−m)}) x^{2} + (\frac{1}{β^{1/2}} + \frac{α^{(1−2^{n})m+(2^{n}−1)k}}{β^{1/2}} ) xz + z^{2} = 0.  (3.2)

When k = m, (3.2) becomes z^{2} = 0. Since there is only one solution to this equation, the line y = α^{(2^{n}−1)m}x is a tangent line to Q_{m}.

Let k − m = j ≠ 0. To show that the line y = α^{(2^{n}−1)k}x does not meet Q_{m}, examine the absolute trace of

\frac{(1 + α^{(2^{n}−1)j})}{(\frac{1}{β^{1/2}} + \frac{1+α^{(2^{n}−1)2j}}{β^{1/2}} )^{2}} = \frac{(1 + α^{(2^{n}−1)j})}{\frac{1}{β} + \frac{1+α^{(2^{n}−1)2j}}{β}}
= \frac{(1 + α^{(2^{n}−1)j})}{\frac{1}{β} (1 + +α^{(2^{n}−1)2j})}
= \frac{(1 + α^{(2^{n}−1)j})}{\frac{1}{β} (1 + α^{(2^{n}−1)j})^{2}}
= \frac{β}{(1 + α^{(2^{n}−1)j})}.

As we now show, these lines are exterior to Q_{m}. Assume, for the sake of attaining a contradiction, that Tr (\frac{β}{(1+α^{(2^{n}−1)j})}) = 0. Then,

Tr (\frac{β}{(1+α^{(2^{n}−1)j})}) = 0

⇒ \frac{β}{(1+α^{(2^{n}−1)j})} + \frac{β^{2}}{(1+α^{(2^{n}−1)j})^{2}} + \frac{β^{4}}{(1+α^{(2^{n}−1)j})^{4}} + ⋯

+\frac{β^{2^{n−1}}}{(1+α^{(2^{n}−1)j})^{2^{n−1}}} + \frac{β^{2^{n}}}{(1+α^{(2^{n}−1)j})^{2^{n}}} + \frac{β^{2^{n+1}}}{(1+α^{(2^{n}−1)j})^{2^{n+1}}} + ⋯

+\frac{β^{2^{2n−1}}}{(1+α^{(2^{n}−1)j})^{2^{2n−1}}} = 0

⇒ β [\frac{1}{(1+α^{(2^{n}−1)j})} + _{\frac{1}{(1+α^{(2^{n}−1)j})^{2^{n}}}} ] + β^{2} [\frac{1}{(1+α^{(2^{n}−1)j})^{2}} + _{\frac{1}{(1+α^{(2^{n}−1)j})^{2^{n+1}}}} ] + ⋯

+β^{2^{n−1}} [_{\frac{1}{(1+α^{(2^{n}−1)j})^{2^{n−1}}}} + _{\frac{1}{(1+α^{(2^{n}−1)j})^{2^{2n−1}}}} ] = 0 (by equation 3.1)

⇒ β + β^{2} + β^{4} + ⋯ + β^{2^{n}−2} + β^{2^{n}−1} = 0  (by Lemma 3.7)
⇒ Tr_{K/F} (β) = 0.

However, β was chosen such that Tr_{K/F} (β) = 1. Thus, Tr (\frac{β}{(1+α^{(2^{n}−1)j})}) = 1 and all lines of the form y = α^{(2^{n}−1)k}x, k ≠ m, are exterior to Q_{m}.

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 \ {l} no longer being a CBS. Thus, B is irreducible.

Observe that |B| = |{y = t^{2^{n}−1}x | t ≠ 0}| = 2^{n} + 1 which is the number of lines of a Baer subplane through a point in a Baer subplane of PG(2, 2^{2n}). 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 β = α^{2^{n}−1}. The element

X = \frac{(β^{j} + β)(1 + β^{2})}{(1 + β)(β^{j} + β^{2})} ∈ E^{∗},

with j ≠ 1, 2, lies in the subfield K^{∗}.

Proof:

We show that X lies in K by showing that X^{2^{n}−1} = 1. First, observe that with β = α^{2^{n}−1},

[β^{k}]^{2^{n}} = \frac{1}{β^{k}},

for any k. Now,

X^{2^{n}−1} = [\frac{(β^{j}+β)(1+β^{2})}{(1+β)(β^{j}+β^{2})}]^{2^{n}−1}
= \frac{(β^{j}+β)^{2^{n}}(1+β^{2})^{2^{n}}}{(1+β)^{2^{n}}(β^{j}+β^{2})^{2^{n}}} · \frac{(1+β)(β^{j}+β^{2})}{(β^{j}+β)(1+β^{2})}
= \frac{(β^{j}+β)^{2^{n}}(β^{j}+β^{2})}{(β^{j}+β^{2})^{2^{n}}(β^{j}+β)} · \frac{(1+β^{2})^{2^{n}}(1+β)}{(1+β)^{2^{n}}(1+β^{2})}
= \begin{matrix}([β^{j}]^{2^{n}}+β^{2^{n}}) & (β^{j}+β^{2}) \\ ([β^{j}]^{2^{n}}+[β^{2}]^{2^{n}}) & (β^{j}+β) \end{matrix} · \begin{matrix}(1+[β^{2}]^{2^{n}}) & (1+β) \\ (1+[β]^{2^{n}}) & (1+β^{2}) \end{matrix}
= \begin{matrix}( \frac{1}{β^{j}} + \frac{1}{β} ) & (β^{j}+β^{2}) \\ ( \frac{1}{β^{j}} + \frac{1}{β^{2}} ) & (β^{j}+β) \end{matrix} · ^{\begin{matrix}(1+ \frac{1}{β^{2}} ) & (1+β) \\ (1+ \frac{1}{β}) & (1+β^{2}) \end{matrix}}
= \frac{\frac{1}{β^{j+1}} (β+β^{j})(β^{j}+β^{2})}{\frac{1}{β^{j+2}} (β^{j}+β^{2})(β+β^{j})} · \frac{\frac{1}{β^{2}} (β^{2}+1)(1+β)}{\frac{1}{β} (1+β)(β^{2}+1)}
= β · \frac{1}{β} = 1.

Since X^{2^{n}−1} = 1 and X ≠ 0, X lies in K^{∗}.

Theorem 3.10 The lines B′ = {y = mx | m ∈ K} ∪ {x = 0} form an irreducible CBS in PG(2, 2^{2n}).

Proof:

We show that B′ is an irreducible CBS in PG(2, 2^{2n}) by finding a projectivity in PGL(3, 2^{2n}) that maps the irreducible CBS B given in Theorem 3.8 to B′. Let β be as defined in Lemma 3.9. Consider the element

A = [ \begin{matrix}\frac{1}{1+β} & \frac{β}{1+β} & 0 \\ \frac{1}{1+β^{2}} & \frac{β^{2}}{1+β^{2}} & 0 \\ 0 & 0 & 1 \end{matrix} ]

in PGL(3, 2^{2n}). 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 = t^{2^{n}−1}x | t ≠ 0} into the lines in B′ = {y = mx | m ∈ K} ∪ {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 = βx in B to the line y = 0 in B′, and the line y = β^{2}x 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 [\begin{matrix}β^{j} \\ 1 \\ 0 \end{matrix} ]. Now,

[ \begin{matrix}\frac{1}{1+β} & \frac{β}{1+β} & 0 \\ \frac{1}{1+β^{2}} & \frac{β^{2}}{1+β^{2}} & 0 \\ 0 & 0 & 1 \end{matrix} ] · [\begin{matrix}β^{j} \\ 1 \\ 0 \end{matrix} ] = [ \frac{(β^{j}+β)(1+β^{2})}{(1+β)(β^{j}+β^{2})} ; 1 ; 0 ] = [\begin{matrix}X \\ 1 \\ 0 \end{matrix} ].

From Lemma 3.9, X lies in K^{∗}, therefore X is of the form α^{(2^{n}+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, 2^{n}). Thus, B′ is projectively equivalent to B, and B′ is an irreducible CBS in PG(2, 2^{2n}).

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, q) form a group where the group operation is the composition of maps. A projectivity is a collineation which can be represented by a 3 × 3 nonsingular matrix. Projectivities of the line PG(1, q) can be represented by 2×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, q) is transitive on the points and lines of PG(2, q), just as PGL(2, q) 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, any map that sends a conic, \overline{C}, to itself will fix the nucleus. Since \overline{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 \overline{C} has three orbits in the plane:

1. the points of \overline{C};

2. the nucleus of \overline{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 \overline{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 [t], if the line is non-vertical, and [∞], for the vertical line through P, and denote the lines through a point Q with nonhomogeneous coordinates [u], if the line is nonvertical, and [∞], for the vertical line through Q. Now, if an element g ∈ PGL(3, q) maps the point P to the point Q, then there is an element

h = [ \begin{matrix}a & b \\ c & d \end{matrix} ] ∈ PGL(2, q)

with the property that for any line l through P with coordinate [t] or [∞], the coordinate of the image of l under g is given by

u = \frac{at+c}{bt+d}, if bt + d ≠ 0
∞,  otherwise.

The following example illustrates this concept.

Example 9. [55]

Let P = (0, 0, 1) and Q = (0, 1, 0). The line [t] through P (and not Q) containing the points (1, t, z) for all z ∈ GF(q) is [t] = [ \begin{matrix}t \\ 1 \\ 0 \end{matrix} ] and the line [u]

through Q (and not P) containing (1, y, u) for all y ∈ GF(q) is [u] = [ \begin{matrix}u \\ 0 \\ 1 \end{matrix} ]. We

wish to send P to Q, fix the line \overline{P Q}, and send the remaining lines through P to the remaining lines through Q. Let A ∈ PGL(3, q) be given by

A = [ \begin{matrix}a_{11} & a_{12} & a_{13} \\ 0 & a_{22} & a_{23} \\ 0 & 1 & 0 \end{matrix} ].

Since A ∈ PGL(3, q), det(A) ≠ 0 implying that both a_{11} and a_{23} are nonzero. Observe that \overline{P Q} is stabilized by A, but, more importantly, P is mapped to Q. A line [t] through P consists of the points {(1, t, z) | z ∈ GF(q)} ∪ {P }, and a line [u] through Q consists of the points {(1, y, u) | y ∈ GF(q)} ∪ {Q}. Because A maps P to Q, if A maps the set {(1, t, z) | z ∈ GF(q)} to {(1, y, u) | y ∈ GF(q)}, then A maps the lines [t] through P to the lines [u] through Q. This implies that

(1, t, z) · A = (a_{11} + 0t, a_{12} + a_{22}t + z, a_{13} + a_{23}t) .

Now,

(1, t, z) · A = (a_{11}, a_{12} + a_{22}t + z, a_{13} + a_{23}t)
=  (1, \frac{a_{12}+a_{22}t+z}{a_{11}}, \frac{a_{13}+a_{23}t}{a_{11}})
= (1, ∗, \frac{a_{23}t+a_{13}}{0t+a_{11}} ) = (1, ∗, u).

In this situation, the element h ∈ PGL(2, q) is given by

[ \begin{matrix}a_{23} & a_{13} \\ 0 & a_{11} \end{matrix} ] = [ \begin{matrix}a & b \\ c & d \end{matrix} ] ∈ 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 C_{1}, the tangent and secant lines of C are mapped respectively to tangent and secantlines of C_{1}. Thus, for each element in PGL(3, q) that maps C to C_{1}, there is an element in PGL(2, q) that sends the tangent and secant lines of C through P to the tangent and secant lines of C_{1} through P.

Consider the conic C with equation xy +xz +z^{2} = 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 ∈ 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 + 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) ∪ {∞} by

\begin{aligned}mx + y = 0 & → & (m), \\ x = 0 & → & (∞). \end{aligned}

Let S_{P} = {(m) | Tr(m) = 0} ∪ {(∞)} 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.

That is,

\begin{aligned}(m) & : & mx + y = 0 & ↦ & (m, 1, 0), \\ (∞) & : & x = 0 & ↦ & (0, 0, 1). \end{aligned}

Note, the set S_{P} = {(m) | Tr(m) = 0} ∪ {(∞)} can still be used to identify the points in the dual plane that correspond to tangent and secant lines in the original plane.

Let [\begin{matrix}a & b \\ c & d \end{matrix}] ∈ PGL(2, q) and consider the following calculations:

(m, 1) [ \begin{matrix}a & b \\ c & d \end{matrix} ] = (am + c, bm + d) = \begin{cases}(\frac{am+c}{bm+d}, 1) , & if bm + d ≠ 0 \\ (1, 0), & if bm + d = 0, \end{cases}

(1, 0) [ \begin{matrix}a & b \\ c & d \end{matrix} ] = (a, b) = \begin{cases}(\frac{a}{b}, 1) , & if b ≠ 0 \\ (1, 0), & if b = 0. \end{cases}

The image of S_{P} under PGL(2, q) is \{\{\frac{ax+c}{bx+d} | Tr(x) = 0\} ∪ \{\frac{a}{b}\}\} where it is understood that if bx + d = 0, then \frac{ax+c}{bx+d} = ∞, and if b = 0, then \frac{a}{b} = ∞.

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(1, q), map this set of parameters to another set of parameters representing tangent and secant lines of another conic in PG(2, q). 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.

Example 10.

Consider this situation in PG(2, 4) with GF(4) = {0, 1, α, α^{2}} such that α^{2} = α + 1. Observe that S_{P} = {0, 1, ∞} and the distinct images sets of S_{P} under PGL(2, q) are {0, 1, ∞}, {0, α, α^{2}}, {0, α, ∞}, {0, 1, α^{2}}, {0, α^{2}, ∞}, {0, 1, α}, {α, α^{2}, ∞}, {1, α, ∞}, {1, α^{2}, ∞}, and {1, α, α^{2}}.

Scanning this list of image sets shows that at least one of the elements 0, 1, ∞ 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 S_{P} = {(m) | Tr(m) = 0} ∪ {(∞)} which represents a set of concurrent tangent and secant lines of a specific conic. And, we use the collineations in PGL(2, q) to generate the image sets of S_{P}. 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 S_{P}, • 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

min ∑_{i=1}^{q+1} x(i)

such that

∑_{i=1}^{q+1} A(k, i)x(i) ≥ 1.

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 0’s and 1’s. If for some row of A, a 0 is 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 3-transitive, 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 0’s in the columns of the three chosen points. Since the remaining image sets have 0’s 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 IP-problem is

min ∑_{i=1}^{q−2} x(i)

such that

∑_{i=1}^{q−2} A(k, i)x(i) ≥ 1.

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 optimality. 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 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
2^{2}  3
2^{3}  5
2^{4}  5
2^{5}  8
2^{6}  9
2^{7}  9

Table 3.5: Minimum CBS Sizes

A complete search for minimum CBSs by Cplex in PG(2, 2^{h}), h ≥ 8, was not feasible. As h increases, the size of the array surpasses the built-in 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, 2^{8}), 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, 2^{8}). 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.

For the purposes of obtaining a lower bound, let q = 2^{h}, tr(x) denote the absolute trace of an element x ∈ E = GF(q), and let V = AG(h, 2) be the vector space over GF(2) represented by E under addition. For 0 ≠ a ∈ E, let f_{a} : E → GF(2) be given by x ↦ tr(ax). Let H_{a} = ker(f_{a}). Clearly, f_{a} is additive. This implies that f_{a} is a group homomorphism from E to GF(2). Hence, ker(f_{a}) is a normal subgroup. Since ker(f_{a}) is a subgroup of E, it is a subspace of V. The rank of the image space of f_{a} is 1. Hence, the rank of the overlying vector space minus 1 equals the rank of the kernel of f_{a}, that is,

rank(V) − 1 = rank(ker(f_{a})).

Hence, H_{a} = ker(f_{a}) is a hyperplane in AG(h, 2). Lemma 3.11 [55] There are precisely q − 1 subgroups of AG(h, 2) = E(+) of index 2. They are the H_{a}, for a ≠ 0 ∈ E.

Proof: Suppose H_{a} = H_{b} with a, b ≠ 0. This implies that tr(ax) = 0 ⇔ tr(bx) = 0 ∀x ∈ E

⇔ tr(ax) = tr(bx) ∀x ∈ E
⇔ tr(ax − bx) = 0 ∀x ∈ E
⇔ tr((a − b)x) = 0 ∀x ∈ E.

This is a contradiction, since x ranges over E, (a − b)x is a linear function and therefore, there is some x for which tr((a−b)x) = 1. Hence, all the H_{a} are distinct.

From the paragraph proceeding Lemma 3.11, H_{a} is a hyperplane in AG(h, 2). As there are q−1 choices for nonzero a, there are q−1 subgroups H_{a}. 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(h−1, 2).

So, there are \frac{2^{h}−1}{2−1} = 2^{h} − 1 = q − 1 hyperplanes in AG(h, 2). Hence, the H_{a} are all the hyperplanes of AG(h, 2).

Observation 3.12 Consider the conic y^{2} = \frac{1}{a}xz, a ≠ 0, with nucleus (0, 1, 0). This conic can also be written as {(a, t, t^{2}) | t ∈ GF(q)} ∪ {(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 Tr ( \frac{b^{2}}{\frac{1}{a^{2}}} ) = 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 y^{2} + \frac{c^{2}}{a^{2}} x^{2} + \frac{1}{a}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, t^{2}) | t ∈ GF(q)} ∪ {(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 [\frac{b^{2} + \frac{c^{2}}{a^{2}}}{\frac{1}{a^{2}}} ] = 1 ⇔ Tr(b^{2}a^{2} + c^{2}) = 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, 2^{h}), then |B| ≥ h.

Proof:

Let B be a CBS which consists of a set of concurrent lines through the point P in PG(2, q). There exists a line l through P and not in B, else |B| = q + 1 and we are done. We may choose coordinates in such a way that l is assigned the nonhomogeneous parameter ∞. 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(ab) = 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(h, 2). As B is contained in no hyperplane of AG(h, 2), B contains a linearly independent set of vectors whose span is AG(h, 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, 2^{h}), then |B| ≤ 2h + 1.

Proof:

As shown in Section 3.4, the sets for which we have to find a set of representatives are the images of S_{P} = {m | Tr(m) = 0} ∪ {∞} under PGL(2, q). Consider the function τ_{b} : x ↦ x + b where Tr(b) = 0. It is clear that τ_{b} maps the set S_{P} to itself. Since there are q/2 elements of trace 0 in E, the size of the stabilizer of S_{P}, |PGL(2, q)_{S_{P}} |, is at least q/2. By the Orbit-Stabilizer theorem,

|orbit of S_{P} | = |PGL(2, q) : PGL(2, q)_{S_{P}} |
≤ q(q^{2} − 1)/(q/2) = 2(q^{2} − 1).

There are at most 2(q^{2}−1) distinct image sets of S_{P} of size (q+2)/2. These image sets give rise to at most 2(q^{2}−1) complementary sets of size q+1−(q+2)/2 = q/2. So there are 2(q^{2} − 1)\binom{q/2}{n} subsets of size n that miss some conic, and there are \binom{q+1}{n} subsets of size n. If

\binom{q + 1}{n} ≥ 2(q^{2} − 1)\binom{q/2}{n},

then there is a CBS of size n. Now, suppose n − 1 > 2 log_{2}(q), then we have that

n − 1  >  log_{2}(q^{2})
⇒  2^{n−1}  >  q^{2}
⇒  2^{n−3}  >  \frac{q^{2}−6q+8}{4}, since q ≥ 2
⇒  2^{n−3}(q + 1)q(q − 1)  > 2(q + 1)(q − 1) (\frac{q}{2}) (\frac{q−2}{2}) (\frac{q−4}{2})
⇒ (q + 1)q(q − 1)(q − 2) ⋯ (q + 1 − (n − 1)) > 2(q^{2} − 1)(\frac{q}{2})(\frac{q−2}{2}) ⋯ (\frac{q−2(n−1)}{2})
⇒ \binom{q+1}{n} ≥ 2(q^{2} − 1)\binom{q/2}{n}.

So \binom{q+1}{n} ≥ 2(q^{2} − 1)\binom{q/2}{n} when n > 2 log_{2}(q) + 1 = 2h + 1. Thus, |B| ≤ 2h + 1.

Thus, we have shown that if B is a minimum CBS in PG(2, 2^{h}), then h ≤ |B| ≤ 2h + 1.

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^{h}), 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 Trace-Flock 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 computer 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 ad-hoc method of selecting potential CBSs and checking, or we employed a greedy-based 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, q).

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 branch-and-bound algorithm contained in Cplex; a surrogate-based heuristic algorithm, written by G. Kochenberger [47], based on a greedy algorithm; or an ad-hoc method of selecting points and checking if these points form a CBS. A ^{∗} indicates that the smallest CBS found is not a minimum CBS.

\begin{matrix}q & L.B. & S.S.F. & U.B. \\ 2^{2} & 2 & 3 & 5 \\ 2^{3} & 3 & 5 & 7 \\ 2^{4} & 4 & 5 & 9 \\ 2^{5} & 5 & 8 & 11 \\ 2^{6} & 6 & 9 & 13 \\ 2^{7} & 7 & 9 & 15 \\ 2^{8} & 8 & 13^{∗} & 17 \\ 2^{9} & 9 & 15^{∗} & 19 \\ 2^{10} & 10 & 23^{∗} & 21 \end{matrix}

Table 3.7: CBS Bounds and Sizes

Appendix A contains a listing of the parameters for CBSs with sizes in Table 3.7.

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^{h}). We give theoretical lower and upper bounds on the sizes of minimum CBSs. Two models 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 E = GF(p^{h}) = GF(q), K = GF(p^{d}), F = GF(p), and π = PG(2, q), where p is an odd prime, h ≥ 1 and d|h such that d ≠ h. Clearly, K = F if d = 1. Let tr(t) denote the relative trace function, Tr_{E/K}(t) = t + t^{p^{d}} + ⋯ + t^{p^{d}^{h−1}}.

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 \frac{q+1}{2} + 1 concurrent lines in PG(2, q) form a CBS.

Proof: Let B be a set of \frac{q+1}{2} + 1 concurrent lines. For the sake of obtaining a contradiction, assume that there is a conic C contained in the \frac{q−1}{2} lines of B^{c}. Since each line of B^{c} contains at most two points of C, we account for at most 2·(\frac{q−1}{2}) = q−1 points of C. But, as C contains q+1 points, C cannot be contained in B^{c} and thus, B is a CBS.

We now consider CBSs in PG(2, 3), so that the remainder of the chapter can be devoted to finding small CBSs in PG(2, p^{h}), p^{h} > 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 Trace-Flock Construction

The process of finding a CBS consists of identifying a set of lines through a point such that all conics in π have at least one secant or tangent line in this set. For the CBS construction given in this section, π 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 ∈ 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 π meets these lines. We begin by examining the size of the range of a specific function in GF(q).

Lemma 4.3 If g : E^{∗} → E is given by g(t) = \frac{tr(t)−t}{t} for t ≠ 0, then |Range(g)| = p^{h−d} + 1.

Proof: To show that the size of the range of g is p^{h−d} + 1, we show that E can be partitioned into p^{h−d} + 1 blocks: one of size p^{h−d} and p^{h−d} blocks of size p^{d} − 1.

Let t ∈ E^{∗}, then

h(t) = −1 ⇔ \frac{tr(t) − t}{t} = −1
⇔ tr(t) − t = −t
⇔ tr(t) = 0.

Since the trace function is an additive homomorphism from E onto K, ker(tr) is a normal subgroup of E. We have that |ker(tr)| = |E|/|K| = \frac{p^{h}}{p^{d}} = p^{h−d}. So, g(t) = −1 ⇔ t is one of the p^{h−d} − 1 nonzero elements in E with trace 0. Hence, there is one block of E that contains the p^{h−d} elements with trace 0.

Now, we show that the remaining elements in E are partitioned into blocks of size p^{d} − 1, giving p^{h−d} blocks. To do this, we first determine when g(t) = g(λt) for λ ∈ E \ K.

g(t) = g(λt) ⇔ \frac{tr(t) − t}{t} = \frac{tr(λt) − λt}{λt}
⇔ λtr(t) − λt = tr(λt) − λt
⇔ λtr(t) = tr(λt).

As tr : E → K, we have that tr(λt), tr(t) ∈ K. But, since λ ∈ E \ K, λtr(t) ∈ K ⇔ tr(t) = 0. We see that g(t) = g(λt) for some λ ∈ E \ K iff t is a nonzero element with trace 0. That is, t ∈ ker(tr).

Observe that g(t) = g(λt) for t ∉ ker(tr) for any λ ∈ K^{∗}. Let T_{0} = {x ∈ E^{∗} | tr(x) = 0}. Then t ∈ T_{0} ⇔ g(t) = −1. Now, |E \T_{0}| = p^{h}−p^{h−d} = p^{h−d}(p^{d}−1) and we see that g partitions E into p^{h−d} + 1 blocks. There is one block containing p^{h−d} elements with trace 0, and the remaining elements of E are split into p^{h−d} blocks of size p^{d} − 1, one for each value of g ≠ −1. Thus, |Range(g)| = p^{h−d} + 1.

Figure 4.1: A partitioning of E

If h is prime, then tr(t) is the absolute trace of t and |Range(g)| = p^{h−1} + 1. If h is composite, then there exist a g such that |Range(g)| < p^{h−1} + 1. In other 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, q) 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.

The q planes of a Knuth-Kantor flock (for which we use the abbreviation KK-flock) have the form

π_{t} : xt − mt^{σ}z + w = 0,

where m is a fixed_{}∈ E and σ a non-identity automorphism of E. Any two distinct planes of the KK-flock, π_{s} and π_{t}, meet in a line, and when this line is projected to the plane w = 0, the line has equation

x = m(t − s)^{σ−1}z.

The size of the set of KK-lines, {x = m(t − s)^{σ−1}z}, is determined by the automorphism minus one, σ − 1. Multiplying by a nonzero constant will not affect the size of the set of KK-lines. By Theorem 2.4, we have that any non-identity automorphism in E has the form t → t^{p^{k}}, where 1 ≤ k ≤ h − 1. Any image set of a function of the form t^{p^{k}−1} has the same size as the set of slopes of the KK-lines, 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 t^{p^{k}−1}, where 1 ≤ k ≤ h − 1, has the potential to be projectively equivalent to the slopes corresponding to KK-lines.

Lemma 4.4 In E, the size of the image set of g(t) = t^{p^{k}−1}, 1 ≤ k ≤ h − 1, is \frac{p^{h}−1}{p^{d}−1}, where d = gcd(k, h).

Proof: For 1 ≤ k ≤ h − 1, define f_{K}(t) = t^{p^{k}} and g_{K}(t) = \frac{f_{K}(t)}{t} = t^{p^{k}−1}, for t ≠ 0. Let d = gcd(k, h). Since f_{K} is an automorphism of E, f_{K} has a fixed field K = GF(p^{d}). For λ ≠ 0,

g_{K}(t) = g_{K}(λt) ⇔ t^{p^{k}−1} = λ^{p^{k}−1}t^{p^{k}−1}
⇔ 1 = λ^{p^{k}−1}
⇔ λ = λ^{p^{k}}
⇔ λ ∈ K.

So, g_{K}(t) = g_{K}(λt) ⇔ λ is in the fixed field of f_{K}(t). Since there are p^{h} −1 nonzero elements in E, for each g_{K}, E is partitioned into blocks of size p^{d} − 1. Therefore, there are \frac{p^{h}−1}{p^{d}−1} different values in the image of g_{K}.

The previous lemma states that the set of slopes corresponding to nonlinear KK-flocks have size \frac{p^{h}−1}{p^{d}−1} where d | h and d < h. We determine when the size of the slopes of the KK-lines, |KK|, of a nonlinear KK-flock are the same as the |Range(g_{K})| for the g_{K} that were defined previously. The case of g_{K} being defined by the absolute trace function is examined first. That is, we determine when \frac{p^{h}−1}{p^{d}−1} = p^{h−1} +1 for h ≥ 3. After that, the necessary conditions for \frac{p^{h}−1}{p^{d}−1} = p^{h−d} +1 are determined.

Lemma 4.5 If h ≥ 3 and p is an odd prime, \frac{p^{h}−1}{p^{d}−1} ≠ p^{h−1} + 1.

Proof: Assume \frac{p^{h}−1}{p^{d}−1} = p^{h−1} + 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 \frac{p^{h}−1}{p^{d}−1} = 1 ≠ p^{h−1} + 1 since p is an odd prime. So, d ≠ h. If d = 1, \frac{p^{h}−1}{p^{d}−1} = ∑_{i=0}^{h−1} p^{i} ≠ p^{h−1} + 1 unless h = 2. But, as h ≥ 3, d ≠ 1. Now, d ≠ h − 1 as this would imply that (h − 1) | h, which can only be true if h < 3.

So, assume that 1 < d < h − 1. Then,

\frac{p^{h} − 1}{p^{d} − 1} = p^{h−1} + 1 ⇔ p^{h} − 1 = (p^{d} − 1)(p^{h−1} + 1)
⇔ p^{h} = p^{d+h−1} + p^{d} − p^{h−1}
⇔ p^{h} + p^{h−1} = p^{d+h−1} + p^{d}
⇔ p^{h−d} + p^{h−d−1} − p^{h−1} = 1.

Since d ≤ h − 2, p | LHS which implies that p | 1, a contradiction. Thus, for 1 ≤ d ≤ h − 1, \frac{p^{h}−1}{p^{d}−1} ≠ p^{h−1} + 1.

Lemma 4.6 Let E = GF(p^{h}), h composite and d such that 1 < d < h with d | h. Then \frac{p^{h}−1}{p^{d}−1} = p^{h−d} + 1 if and only if d = \frac{h}{2}.

Proof: (⇐) Trivial. (⇒)

\frac{p^{h} − 1}{p^{d} − 1} = p^{h−d} + 1 ⇔ p^{h} − 1 = (p^{d} − 1)(p^{h−d} + 1)
⇔ p^{h} = p^{d+h−d} + p^{d} − p^{h−d}
⇔ p^{h−d} = p^{d}
⇔ h − d = d
⇔ d = \frac{h}{2}.

If K = GF(p^{d}) is any subfield of E = GF(p^{h}), define tr(t) = Tr_{E/K}(t) and g(t) = \frac{tr(t)−t}{t}, for t ≠ 0. Now, if d ≠ 1, h, or \frac{h}{2}, we can construct a function g such that |Range(g)| = \frac{p^{h}−1}{p^{d}−1}. As stated above, this value is smaller than p^{h−1} + 1.

So, when h is composite, a function with smaller size range than p^{h−1} + 1 can always be found unless d is prime and h = 2d.

The following theorems, due to Thas, are instrumental in the construction of the CBS.

Theorem 4.7 [69] If the planes π_{1}, π_{2}, ⋯, π_{q}, of a flock F of cone K contain a common interior point P of K, then F is a linear flock.

Theorem 4.8 [69] If the planes π_{1}, π_{2}, ⋯, π_{q}, of a flock F of cone K contain a common exterior point of K, then F is either a linear or a Knuth-Kantor Flock.

We have all the tools necessary to prove the main result of this section.

Theorem 4.9 In PG(2, p^{h}), with h ≥ 3, if d ≠ \frac{h}{2} and d | h, then there is a CBS of size p^{h−d} + 1.

Proof: Consider the additive function f(t) = Tr_{E/K}(t) − t = tr(t) − t, which we use to form the function g(t) = \frac{f(t)}{t} = \frac{tr(t)−t}{t}, for t ≠ 0. As shown in Lemma 4.3, |Range(g)| = p^{h−d} + 1 and by Lemmas 4.4 and 4.5, this size does not correspond to the size of a set of KK-lines.

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 Range(g). Consider the planes of the form:

π_{t} : −f(t)x + ty − tz + w = 0 with t ∈ E^{∗}.

There are p^{h} − 1 planes of this type, since t ∈ E^{∗}. 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, π_{s} and π_{t}, (s ≠ t) meet in a line which projects from (0, 0, 0, 1) to the line y = \frac{f(s−t)}{s−t}x + z = g(s − t)x + z in the plane w = 0. This line is in the set B. Together with the plane w = 0, we have a set of q = p^{h} 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 p^{h} planes form a flock of K and the planes all contain the common point (0, 1, 1, 0). To show that B is a CBS, the two cases, where (0, 1, 1, 0) is an interior point and (0, 1, 1, 0) is an exterior point, are handled separately.

If (0, 1, 1, 0) is an interior point to C, then Theorem 4.7 implies that this flock is linear, contradicting |Range(g)| = p^{h−d} + 1. Thus, this conic does not exist and B blocks all conics with (0, 1, 1, 0) as an interior point.

If (0, 1, 1, 0) is an exterior point to C, then Theorem 4.8 implies this flock is projectively equivalent to a KK-flock. But, any flock equivalent to a KKflock in a plane of order p^{h} has size one (linear) or size \frac{p^{h}−1}{p^{d}−1} (nonlinear). Since p^{h−d} + 1 ≠ 1 or \frac{p^{h}−1}{p^{d}−1} for any d such that d | h, C does not exist and B blocks all conics with (0, 1, 1, 0) as an exterior point.

Thus, the set of lines \{y = \frac{tr(t)−t}{t}x + z | t ≠ 0\} form a CBS of size p^{h−d} + 1 in the plane PG(2, p^{h}), when h ≠ 2d and h > 3.

In the trace-flock construction, the specific function g(t) = \frac{tr(t)−t}{t} was used to give the slopes of the lines in the CBS. Since g is an additive function divided by t and the size of its image set is known, we used g to form a CBS of size p^{h−d} + 1. Any function of this form can be used to construct a CBS, as long as the image contains more than one element.

The trace-flock construction does not give CBSs when q is prime, since the only additive function, up to scalar multiplication, is the identity.

As t and t^{q} are the only two automorphisms in GF(q^{2}) over GF(q), any additive function in GF(q^{2}) has the form αt+βt^{q}, where α, β ∈ GF(q^{2}), β ≠ 0. The image set of the function \frac{αt+βt^{q}}{t} = α + βt^{q−1} is the same size as the set of KK-lines. Using the projectivity

[ \begin{matrix}\frac{−1}{β} & \frac{α}{β} & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] ∈ PGL(3, q^{2}),

we find that the set of lines {y = (α + βt^{q−1})x + z} is projectively equivalent to the set of lines {y = g(t)x + z | t ∈ GF(q^{2})^{∗}} = {y = t^{q−1}x + z | t ∈ GF(q^{2})^{∗}}. When g(t) = t^{q−1} and α is a generator of GF(q^{2}), we have that Range(g) = {1, α^{q−1}, α^{2(q−1)}, …, α^{q(q−1)}} which is a cyclic subgroup of GF(q^{2}) of order q + 1. Moreover, we have that when x ∈ Range(g), then x^{−1} ∈ Range(g).

In Section 2.4, we showed that the set of lines {y = g(t)x+z | t ∈ GF(q^{2})^{∗}} = {y = t^{q−1}x + z | t ∈ GF(q^{2})^{∗}} through (0, 1, 1) was projectively equivalent to the set of lines

T = \{[\begin{matrix}−t^{q−1} \\ 1 \\ 0 \end{matrix} ] | t ∈ GF(q^{2})\}

through (0, 0, 1). The KK-lines through (0, 1, 0) are given by

S = \{[\begin{matrix}1 \\ 0 \\ −mt^{q−1} \end{matrix} ] | m = fixed_{}, t ∈ GF(q^{2})\}.

Consider the projectivity

M = [ \begin{matrix}\frac{1}{m} & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ] ∈ PGL(3, q^{2}).

Observe that (0, 0, 1) · M = (0, 1, 0) and

[ \begin{matrix}\frac{1}{m} & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ] · [\begin{matrix}−t^{q−1} \\ 1 \\ 0 \end{matrix} ] = [\begin{matrix}−\frac{1}{m}t^{q−1} \\ 0 \\ 1 \end{matrix} ] = [\begin{matrix}1 \\ 0 \\ −m\frac{1}{t^{q−1}} \end{matrix} ] = [\begin{matrix}1 \\ 0 \\ −ms^{q−1} \end{matrix} ] ∈ S.

Hence, T is projectively equivalent to the KK-lines in PG(2, q^{2}). So, the set of lines through (0, 1, 1) generated by functions of the form α + βt^{q−1}, β ≠ 0 is projectively equivalent to the lines through (0, 1, 0) corresponding to KK-lines. Therefore, the trace-flock construction does not yield a CBS in PG(2, q^{2}).

Table 4.1 lists the sizes of CBSs obtained by the trace-flock construction described in Theorem 4.9.

q Guaranteed CBS Sizes

p^{3}  p^{2} + 1
p^{4}  p^{3} + 1
p^{5}  p^{4} + 1
p^{6}  p^{5} + 1, p^{4} + 1
p^{7}  p^{6} + 1
p^{8}  p^{7} + 1, p^{6} + 1
p^{9}  p^{8} + 1, p^{6} + 1
p^{10}  p^{9} + 1, p^{8} + 1

Table 4.1: CBS Sizes Given by the Trace-Flock Construction

For a fixed q, even the largest size of a CBS obtained by this construction is always smaller than those CBSs constructed in Lemma 4.1. When h is prime, the trace-flock construction yields exactly one CBS. When h is composite, a variety of CBSs are obtained. To emphasize the significance of this fact, the trace-flock construction gives a CBS of size 26 that blocks the (over 3.05 × 10^{10}) conics in the plane PG(2, 125), whereas by Lemma 4.1, 64 lines were needed to form a CBS.

4.3 Searching for Minimum CBSs

Having established that CBSs exist and having provided a construction of CBSs, we now focus on finding minimum CBSs and obtaining bounds on the sizes of these CBSs. Two different models that permit efficient computer searches for minimum CBSs are developed. The first model developed is later used in finding CBSs in PG(2, q^{2}). The second model is similar to the one developed in Chapter 3. Both models are developed in the dual plane. The results of the searches are located at the end of this chapter.

Currently, finding a CBS consists of finding a set of concurrent lines such that the lines in this set have certain properties with respect to all conics in the plane. Namely, every conic in the plane must have at least one secant or tangent in that set. Dualizing, this set of concurrent lines becomes a set of points on a line, and these points all have special properties with respect to the dual conics. When we dualize by using the standard polarity, we transform each point (or line) into the line (or point) with the same coordinates. The conics in π are the zeros of nondegenerate quadratic forms. After dualizing, these line conics are associated with the same nondegenerate quadratic forms, which can be represented by 3 × 3 nonsingular matrices. Since we are free to coordinatize π in any manner, we can insure that the point of concurrency in the plane π for the two models below will be the point (0, 0, 1). This point becomes the line z = 0 in the dual plane π^{∗}. In π, the lines through (0, 0, 1) have equations x = 0 and mx + y = 0, m ∈ GF(q). After dualizing, these lines become the points (1, 0, 0) and (m, 1, 0), m ∈ GF(q), on the line z = 0 in π^{∗}. In π, a CBS consists of a set of concurrent lines through the point (0, 0, 1) that satisfy a certain property. In π^{∗}, a CBS consists of a set of points on the line z = 0 that also satisfy some property. In these models, we identify the property that the points on the line z = 0 must satisfy in order to be a CBS. For notational simplicity, we make the identification between the points of z = 0 in π^{∗}, and hence, the lines through (0, 0, 1) in π, and the elements of GF(q) ∪ {∞} by

\begin{matrix}mx + y = 0 & ↔ & (m), \\ x = 0 & ↔ & (∞). \end{matrix}

This allows us to refer to the points of the CBS in terms of the parameters. 4.3.1 Restricted Quadratic Form Model

Before this model is developed, a review of linear algebra and quadratic forms is provided. 4.3.1.1 Review of Linear Algebra and Quadratic Forms

The material presented in this section is found in greater detail in [54]. Throughout this section and model development, we work over the Galois field E = GF(q), q = p^{h}, p an odd prime. Let V = E^{3} be the vector space over which we are working. Definition 4.10 A function Q : V ↦ E is a quadratic form on V provided

1. Q(cw) = c^{2}Q(w) for all c ∈ E, w ∈ V, and 2. for every u, v ∈ 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. If A is a given upper triangular matrix, then B = A + A^{T} is symmetric. A quadratic form is given by Q(X) = XAX^{T}. Two distinct points, X = ⟨v⟩ and Y = ⟨w⟩, are orthogonal (or perpendicular) if and only if XBY^{T} = 0, which is equivalent to f(v, w) = Q(v + w) − Q(v) − Q(w) = 0. The polar of X is the line BX^{T}. The quadratic form Q is nonsingular and its polar form f is nondegenerate provided |B| = det(B) ≠ 0. The discriminant of Q (or of f or of B) is defined to be disc(B) = |B| modulo the group of squares in E^{∗} = E \ {0}.

As above, let Q : V ↦ E be a nonsingular quadratic form on V with polar form f. Since Q(v) = 0 if and only if Q(cv) = c^{2}Q(v) = 0 for all c ∈ E^{∗}, the quadric Q(n − 1, q) = {v ∈ P (V) : Q(v) = 0} is a well-defined set of points of the projective space P (V) associated with V. If W is a subspace of V, define W^{⊥} = {v ∈ V : f(v, w) = 0 for all w ∈ W }. If W ∩ W^{⊥} = {0}, it is possible to show that V = W ⊕ W^{⊥}. Moreover, if B_{1} is a basis of W and B_{2} is a basis of W^{⊥}, then B_{1} ∪ B_{2} is a basis of V, and the matrix B that is the Gram matrix of Q with respect to the basis B_{1} ∪ B_{2} is the direct sum of the matrices of B_{1}, B_{2} that are the Gram matrices of Q restricted to W, W^{⊥}, respectively. Hence,

disc(Q) = disc(Q|_{W}) · disc(Q|_{W^{⊥}}). Now suppose W = ⟨x, y⟩ is a line, that is, a rank two subspace of V. Put

f(x, x) = a, f(x, y) = f(y, x) = b, f(y, y) = c. Then disc(Q|_{W}) = |\begin{matrix}a & b \\ b & c \end{matrix}| = ac − b^{2}.

So Q(dx + ey) = 0 if and only if 0 = f(dx + ey, dx + ey) = d^{2}a + 2deb + e^{2}c has no solutions (d, e) ≠ (0, 0) if and only if 4b^{2} − 4ac = −4(b^{2} − ac) ≡ −disc(Q|_{W}) = ∈ E. This proves the following theorem.

Theorem 4.11 The line W is anisotropic (or elliptic), that is, contains no nonzero vector v with Q(v) = 0, if and only if −disc(Q|_{W}) =_{}.

This result may be used to develop a formula to classify a point with respect to a conic C given by the quadratic form Q as being either interior or exterior. If W is a subspace for which W ∩W^{⊥} = 0, then disc(Q) = disc(Q|_{W})·disc(Q|_{W^{⊥}}). If P is a point, then P^{⊥} is a line. Put W = P^{⊥}, so W^{⊥} = P. Then P is an internal point of the quadric given by Q if and only if W = P^{⊥} is anisotropic, that is, if and only if −disc(Q|_{W}) =_{}. Hence, P is an internal point if and only if

disc(Q) = disc(Q|_{W}) · disc(Q|_{W^{⊥}})
disc(Q) = −_{}· disc(Q|_{W^{⊥}})
disc(Q) = −_{}· f(P, P)
disc(Q) = −_{}· 2Q(P)
disc(Q) = −2Q(P)
(disc(Q))^{2} = −2 Q(P)disc(Q)
= −2Q(P)disc(Q).

Thus, P is an internal point of C if and only if −2Q(P)disc(Q) =_{}and P is an external point of C if and only if −2Q(P)disc(Q) = . Example 11. In this example, the points on the line z = 0 are classified with respect to the conic C given by the quadratic form Q : x^{2}+y^{2}−xz+z^{2} in PG(2, 5).

The points of C are {(1, 2, 0), (1, 3, 0), (0, 2, 1), (0, 3, 1), (1, 2, 1), (1, 3, 1)}, and the points of z = 0 are {(1, 0, 0), (0, 1, 0), (1, 1, 0), (1, 2, 0), (1, 3, 0), (1, 4, 0)}. The tangent lines, along with the points contained in them, are listed below.

y = 3x + z : {(1, 3, 0), (0, 1, 1), (1, 4, 1), (2, 2, 1), (3, 0, 1), (4, 3, 1)}^{y = x + z : {(1, 1, 0), (0, 1, 1), (1, 2, 1), (2, 3, 1), (3, 4, 1), (4, 0, 1)}}^{y = 4x + 2z : {(1, 4, 0), (0, 2, 1), (1, 1, 1), (2, 0, 1), (3, 4, 1), (4, 3, 1)}}^{y = x + 3z : {(1, 1, 0), (0, 3, 1), (1, 4, 1), (2, 0, 1), (3, 1, 1), (4, 2, 1)}}^{y = 4x + 4z : {(1, 4, 0), (0, 4, 1), (1, 3, 1), (2, 2, 1), (3, 1, 1), (4, 0, 1)}} y = 2x + 4z : {(1, 2, 0), (0, 4, 1), (1, 1, 1), (2, 3, 1), (3, 0, 1), (4, 2, 1)}

Clearly, the points (1, 1, 0) and (1, 4, 0) are exterior points because these points lie on two tangents. The points (0, 1, 0) and (1, 0, 0) do not lie on any tangent lines and therefore must be interior points. Finally, the points (1, 1, 0) and (1, 3, 0) are conic points.

The disc(Q) = which implies that −2disc(Q) = _{}. The following chart shows the classification of each point on z = 0, using the formula provided in this section.

P  Q(P) −2disc(Q)Q(P) Classification
(1, 0, 0) 1 =  _{}=_{}internal
(0, 1, 0) 1 =  _{}=_{}internal
(1, 1, 0) 2 =_{}_{}_{}=  external
(1, 2, 0)  0  _{}0 = 0  on
(1, 3, 0)  0  _{}0 = 0  on
(1, 4, 0) 2 =_{}_{}_{}=  external

4.3.1.2 Restricting Nondegenerate Quadrics to a Line

W = ⟨(1, 0, 0), (0, 1, 0)⟩ is a line, namely, the line z = 0. Consider the conic given by the nondegenerate quadratic form Q(X) = XAX^{T} on E^{3} = GF(q)^{3} where

A = [ \begin{matrix}a & b & d \\ 0 & c & e \\ 0 & 0 & f \end{matrix} ]

and

B = A + A^{T} = [ \begin{matrix}2a & b & d \\ b & 2c & e \\ d & e & 2f \end{matrix} ].

It is not difficult to show that the pole of z = 0 is the point (\frac{be−2cd}{det(B)}, \frac{bd−2ae}{det(B)}, \frac{4ac−b^{2}}{det(B)} ) or equivalently (be − 2cd, bd − 2ae, 4ac − b^{2}). If 4ac = b^{2}, then the pole of z = 0 lies on z = 0 and W ∩ W^{⊥} ≠ {0}. If 4ac ≠ b^{2}, then the pole of z = 0 does not lie on z = 0 and W ∩ W^{⊥} = {0}. Thus, if W ∩ W^{⊥} = {0} then 4ac ≠ b^{2}, and if W ∩ W^{⊥} ≠ {0} then 4ac = b^{2}; as these statements are the contrapositives of the previous statements.

The structure of Q|_{W} is now reviewed. Assume that 4ac ≠ b^{2}, W = ⟨(1, 0, 0), (0, 1, 0)⟩ = ⟨x̄, ȳ⟩ and W^{⊥} = ⟨(j, k, 1)⟩ = ⟨z̄⟩. Clearly, W ∩ W^{⊥} = {0}. Write V = W ⊕ W^{⊥} and compute the Gram matrix for the quadratic form Q given by Q(X) = XAX^{T} = ax^{2} + bxy + cy^{2} + dxz + eyz + fz^{2} where A and B are given above. Now,

f(x̄, x̄) = 2Q(x̄) = 2a

f(x̄, ȳ) = a + b + c − a − c = b^{f(ȳ, x̄) = f(x̄, ȳ)}^{f(ȳ, ȳ) = 2Q(ȳ) = 2c} f(z̄, z̄) = 2Q(z̄).

The Gram matrix of f is given by

[ \begin{matrix}2a & b & 0 \\ b & 2c & 0 \\ 0 & 0 & 2Q(z̄) \end{matrix} ] = [ \begin{matrix}B_{1} & 0 \\ 0 & B_{2} \end{matrix} ].

Recall that in Section 4.3.1.1, it was shown that 0 ≠ det(B) = det(B_{1}) · det(B_{2}), and we have that det(B_{1}) = 4ac − b^{2} ≠ 0 and det(B_{2}) = 2Q(z̄). Now, Q|_{W} is given by X̃A′X̃^{T} = ax^{2} + bxy + cy^{2} where

A′ = [ \begin{matrix}2a & b \\ b & 2c \end{matrix} ].

Let P̄ denote P |_{W}, that is, if P = (m, n, 0), then P̄ = (m, n). For any point P̄ ∈ W, we have that Q|_{W} (P̄) = am^{2} + bmn + cn^{2} = Q(P).

Under the specified conditions, this restriction of the quadratic form to the line z = 0 is what enables the model for finding small CBSs to be efficient. Effectively, the problem drops from six variables (the coefficients in the quadratic form) to three variables (the coefficients in the quadratic form restricted to the line z = 0).

As mentioned earlier, the point (0, 0, 1) becomes the line z = 0 in the dual plane. In π, a quadric is a set of points satisfying a quadratic equation. In π^{∗}, the dual line quadric is the set of lines whose line coordinates satisfy the same quadratic equation. If the pole of z = 0 is a point on the line z = 0, then this implies that z = 0 is a line of the line quadric. Thus in π, the point (0, 0, 1) is on the quadric and therefore, this quadric is blocked. To clarify this idea, we offer the following example. Example 12.

Let E = GF(5) and consider the conic with equation y^{2} − xz = 0 in PG(2, 5). This conic is given by the quadratic form Q(X) = XAX^{T} where

A = [ \begin{matrix}0 & 0 & −1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}]

and

B = A + A^{T} = [\begin{matrix}0 & 0 & −1 \\ 0 & 2 & 0 \\ −1 & 0 & 0 \end{matrix}].

Now, det(B) = 3 so that disc(Q) =_{}. In π, the points on the conic are {(0, 0, 1), (1, 0, 0), (1, 1, 1), (1, 4, 1), (4, 2, 1), (4, 3, 1)}, and clearly, the line z = 0 is a tangent line to C. The pole of z = 0 with respect to this conic is the point (1, 0, 0) which, coincidentally, is also a point of the conic. If W = ⟨(1, 0, 0), (0, 1, 0)⟩ then W^{⊥} = ⟨(1, 0, 0)⟩ and W ∩ W^{⊥} ≠ {0}, so V cannot be written as W ⊕ W^{⊥}. Notice that the point (0, 0, 1) is on the conic and this conic will be blocked in π by any non-empty set of lines through (0, 0, 1). 4.3.1.3 Classifying Points in the Dual Setting

In Section 4.3.1.1, an explanation of how to classify a point with respect to a conic as being interior or exterior was given. To summarize, let P be a point in the plane and C a conic given by the quadratic form Q. If

−2Q(P)disc(Q) = \{ 0^{}then P is \begin{cases}internal to \\ external to \\ on \end{cases}

the conic. We have shown that if W = ⟨(1, 0, 0), (0, 1, 0)⟩ and W ∩ W^{⊥} = {0}, then for all P ∈ W, we have Q(P) = Q|_{W} (P). This implies that if

−2Q(P)disc(Q) = −2Q|_{W} (P)disc(Q) = \{ 0^{}then P is \begin{cases}internal to \\ external to \\ on \end{cases}

the conic. Since we are dealing with quadratic forms restricted to the line, we cannot say for certain whether disc(Q|_{W}) is a or a_{}, as is illustrated by the following example. Example 13. Let E = GF(5) and consider the conic with equation x^{2} + xy + y^{2} + fz^{2} = 0, f ≠ 0, in PG(2, 5). This conic is given by the quadratic form Q(X) = XAX^{T} where

A = [ \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & f \end{matrix} ]

and

B = A + A^{T} = [ \begin{matrix}2 & 1 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & 2f \end{matrix} ].

We have shown that Q|_{W} = x^{2} + xy + y^{2}, where W = ⟨(1, 0, 0), (0, 1, 0)⟩ = ⟨x̄, ȳ⟩. The polar of (0, 0, 1) is W, since

[ \begin{matrix}2 & 1 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & 2f \end{matrix} ] (\begin{matrix}0 \\ 0 \\ 1 \end{matrix}) = [\begin{matrix}0 \\ 0 \\ 1 \end{matrix}].

So, W^{⊥} = ⟨(0, 0, 1)⟩ = ⟨z̄⟩ and W ∩ W^{⊥} = {0}. Also, det(B) = f.

Assume f = 1, so that disc(Q) = . We now classify the points in W with respect to Q.

P − 2disc(Q)Q(P) Classification

(1, 0, 0)  internal
(0, 1, 0)  internal
(1, 1, 0)  external
(2, 1, 0)  0  on
(3, 1, 0)  0  on
(4, 1, 0)  external

Assume f = 2, so that disc(Q) =_{}. We now classify the points in W with respect to Q.

P − 2disc(Q)Q(P) Classification

(1, 0, 0)  external
(0, 1, 0)  external
(1, 1, 0)  internal
(2, 1, 0)  0  on
(3, 1, 0)  0  on
(4, 1, 0)  internal

This example shows that when the quadratic form is restricted to the line z = 0, the information about the discriminant of Q is lost.

Since disc(Q) = disc(Q|_{W}) · (2f mod ), by varying the choices of f, disc(Q) varies. Therefore the external points to the dual conic on the line z = 0 are either

{(x, y, 0) | Q(x, y, 0) = Q|_{W} (x, y) = } or

{(x, y, 0) | Q(x, y, 0) = Q|_{W} (x, y) =_{}}.

Now, as there are conics in the original plane for which the external points on z = 0 to the dual conic are {(x, y, 0) | Q(x, y, 0) = Q|_{W} (x, y) = } and there are conics in the original plane for which the external points on z = 0 are {(x, y, 0) | Q(x, y, 0) = Q|_{W} (x, y) =_{}}, both these situations must be taken into account in the model development. 4.3.1.4 The Restricted-Dual Model Summary

By dualizing, the problem is transformed from finding a set of concurrent lines that satisfy a certain property to finding a set of collinear points that satisfy some property. Define the subspace W of V to be ⟨(1, 0, 0), (0, 1, 0)⟩. If W ∩W^{⊥} = {0}, then we may write V = W ⊕ W^{⊥} and Q|_{W} is nondegenerate. Let B be the set of points on z = 0 corresponding to a specific set of concurrent lines in the original plane. In order for B to be a CBS, one of the following must be satisfied.

1. There exists a point u ∈ B such that Q|_{W} (u) = 0. (u corresponds to a tangent line in the original plane.)

2. There exists at least two distinct points u and v in B such that Q|_{W} (u) = and Q|_{W} (v) =_{}. (Q|_{W} (u) ≠ 0 and Q|_{W} (v) ≠ 0.) (u and v correspond to one secant line and one exterior line in the original plane.)

Now, if W ∩ W^{⊥} ≠ {0}, then we may not write V = W ⊕ W^{⊥}. This will not affect the CBS problem. When W ∩ W^{⊥} ≠ {0} with respect to some quadratic form Q, then Q is already blocked in π.

4.3.1.5 Finding the CBSs in the Set Covering Setting We now discuss how the computer is used in the search for minimum CBSs. We examine each of the conics of the form ax^{2} + bxy + cy^{2} = 0 and store the

classification of the points of z = 0 in an array B, such that:

• the columns of B are the points of the line z = 0,

• the rows of B are the dual conics,

• the entries are the classification of a point with respect to a conic, that is, 1 is stored if the point is exterior (secant line), −1 is stored if the point is interior (exterior line), and 0 is stored if the point is on the conic (tangent line).

To obtain a CBS, we find a set of columns such that each row of B has a 0 or 1 in at least one column of this set. This set of columns corresponds to a set of points in π^{∗} which, in turn, corresponds to a set of lines in π. To find a minimum CBS, we want to obtain the smallest such set of columns. This is a set covering problem which can be efficiently solved using a commercial solver such as Cplex.

We create a new array A from B by the mapping

a_{ij} = \begin{cases}1 & if b_{ij} = 0, \\ 1 & if b_{ij} = 1, \\ 0 & if b_{ij} = −1. \end{cases}

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, then the point represented by column j has not been selected to be in the CBS. Then the optimization problem is to find an x⃗ with

min ∑_{i=1}^{q+1} x(i)

such that for all rows, k of the array A

∑_{i=1}^{q+1} A(k, i)x(i) ≥ 1.

If any row of A is picked and multiplied by x⃗, a nonnegative integer is obtained, for we are only multiplying 0’s and 1’s. If for some row of A, a 0 is obtained by multiplying by x⃗, then there is not a representative in that image set. Hence, x⃗ cannot represent a CBS. Example 14.

There are nine conics given by the quadratic forms, up to scalar multiplication, of the type ax^{2} + bxy + cy^{2} in PG(2, 3). They are xy, xy + y^{2}, 2xy + y^{2}, x^{2} + xy, x^{2} + 2xy, x^{2} + y^{2}, x^{2} + 2y^{2}, x^{2} + xy + y^{2}, and x^{2} + 2xy + 2y^{2}. The array B with the point classification and the corresponding array A are given in Table 4.5.

\begin{matrix}B = & & A = \\ [\begin{matrix}0 & −1 & 1 & 0 \\ 0 & 1 & −1 & 0 \\ 0 & 1 & 0 & −1 \\ 0 & −1 & 0 & 1 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & −1 & 1 \\ −1 & 1 & 0 & 0 \\ 1 & −1 & 0 & 0 \\ −1 & 0 & 1 & 0 \\ 1 & 0 & −1 & 0 \\ 1 & −1 & −1 & 1 \\ −1 & 1 & 1 & −1 \\ −1 & 0 & 0 & 1 \\ 1 & 0 & 0 & −1 \\ 1 & 1 & −1 & −1 \\ −1 & −1 & 1 & 1 \\ 1 & −1 & 1 & −1 \\ −1 & 1 & −1 & 1 \end{matrix}] & ⟷ & [ \begin{matrix}1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} ] \end{matrix}

Table 4.5: Array B to Array A Conversion in PG(2, 3)

It is not difficult to see that the selection of any two columns is not sufficient to form a CBS, but the selection of any three columns (points) is sufficient to form a CBS. This is consistent with the results of Theorem 4.2.

4.3.2 Secant-Tangent Mapping Model

The restricted-dual model allowed us to efficiently find a minimum CBS for planes of small order. These CBSs can be found in parameter form in Appendix B. We now make minor modifications to the model developed in Chapter 3, to obtain a similar model for finding minimum CBSs when q is odd. Since most of the details for this model are provided in Chapter 3, only the changes that are necessary to make the corresponding model work in odd characteristic are mentioned.

When the characteristic of the plane is even, every conic has a unique nucleus. When the characteristic of the plane is odd, there is no nucleus of a conic and so the orbits of a stabilizer of a conic in a plane of odd characteristic will not be the same as a conic in a plane of even characteristic. As shown in Chapter 2, in a plane of odd characteristic, the stabilizer of a conic has the three orbits:

1. the points of the conic;

2. the external points with respect to the conic;

3. the internal points with respect to the conic.

That is, the stabilizer of a conic is transitive on the set of internal points of a conic and is transitive on the set of external points of a conic.

Since PGL(3, q) acts transitively on the set of conics of PG(2, q), and the stabilizer of a conic acts transitively on the set of internal points and the set of external points, for any point P, the stabilizer of P ∈ PGL(3, q) acts transitively on the sets of conics for which P is an internal or external point. This implies that when P is stabilized and C is mapped to another conic C_{1}, the secant and tangent lines of C are mapped to secant and tangent lines of C_{1}. Just as in the model developed in Chapter 3, denote the lines through a point P with nonhomogeneous coordinates [t], if the line is non-vertical, and [∞], 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 [∞], for the vertical line through Q. Now, if an element g ∈ PGL(3, q) maps the point P to the point Q, then there is an element h = [ \begin{matrix}a & b \\ c & d \end{matrix} ] ∈ PGL(2, q) with the property that for any line l through P with coordinate [t] or [∞], the coordinate of the image of l under g is given by

u = \frac{at+c}{bt+d}, if bt + d ≠ 0
∞, otherwise.

Thus, for each element in PGL(3, q) that maps C to C_{1}, there is an element in PGL(2, q) that sends the secant and tangent lines of C through P to the secant and tangent lines of C_{1} through P.

When the order of the plane was even, one conic was used to generate an initial set of tangent and secant lines. Since the order of the plane is odd, the cases of P being an internal and external point must be dealt with separately when generating the sets of initial secant and tangent lines. The first case handled is when P is an internal point.

Consider the conic Q whose points satisfy −xy + y^{2} + 2yz + z^{2} = 0. The lines x = 0 and y = 0 are tangent lines to Q. Since (0, 0, 1) lies on both of these tangent lines, (0, 0, 1) is an external point with respect to Q. The lines through (0, 0, 1) are x = 0 and y = mx, for m ∈ E. It is not difficult to show that y = mx is a secant line when m = ≠ 0. For this conic, the set of parameters {m | m = } ∪ {∞}, represent the secant and tangent lines of Q.

Now, consider the conic Q, whose points satisfy ny^{2} + xz + z^{2} = 0, where n is a fixed_{}. In order for a line with equation y = mx to be a tangent line to Q, we must have that \frac{1}{4n} = m^{2}, which cannot occur. Thus, there are no lines through (0, 0, 1) that are tangent to Q, and (0, 0, 1) is an internal point to Q. The line y = mx is a secant line to Q provided that m is such that 1 − 4nm^{2} = . If −1 = , then x = 0 is an exterior line to Q. If −1 =_{}, then x = 0 is a secant line to Q. When q ≡ 1 mod 4, the set of parameters for the secant lines of Q through (0, 0, 1) is {m | 1 − 4nm^{2} = } ∪ {∞}. When q ≡ 3 mod 4, the set of parameters for the secant lines of Q through (0, 0, 1) is {m | 1 − 4nm^{2} = }.

Once these sets of secant and tangent lines are identified, the development of the model is nearly identical to the even characteristic model. 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 (m, 1, 0), m ∈ GF(q) and (0, 0, 1). Note that we can still use the specified parameter sets to to identify the points in the dual plane that correspond to tangent and secant lines in the original plane.

Let [ \begin{matrix}a & b \\ c & d \end{matrix} ] ∈ PGL(2, q) and consider the following calculations:

(x, 1) [ \begin{matrix}a & b \\ c & d \end{matrix} ] = (ax + c, bx + d) = \begin{cases}(\frac{ax+c}{bx+d}, 1) , & if bx + d ≠ 0 \\ (1, 0), & if bx + d = 0, \end{cases}

(1, 0) [ \begin{matrix}a & b \\ c & d \end{matrix} ] = (a, b) = \begin{cases}(\frac{a}{b}, 1) , & if b ≠ 0 \\ (1, 0), & if b = 0. \end{cases}

For q ≡ 1 mod 4, the image sets of {m | m = , 0} ∪ {∞} and {m | 1 − 4nm^{2} = } ∪ {∞} are

\{\frac{am + c}{bm + d} | m = , 0\} ∪ \{\frac{a}{b}\} and \{\frac{am + c}{bm + d} | 1 − 4m^{2}n = \} ∪ \{\frac{a}{b}\},

respectively. For q ≡ 3 mod 4, the image sets of {m | m = , 0} ∪ {∞} and {m | 1 − 4nm^{2} = } are

\{\frac{am + c}{bm + d} | m = , 0\} ∪ \{\frac{a}{b}\} and \{\frac{am + c}{bm + d} | 1 − 4m^{2}n = \},

respectively. It is understood that if bm + d = 0, \frac{am+c}{bm+d} = ∞, and if b = 0, \frac{a}{b} = ∞.

To summarize the procedure, we find two conics C_{1} and C_{2}, and then we fix a point P ∉ C_{1} or C_{2}, such that P is external to C_{1} and internal to C_{2}. After identifying the secant and tangent lines through P to the respective conics, we obtain two parameter sets of points in the dual plane that correspond to tangent and secant lines of these conics in the original plane. Using collineations of the line PG(1, q), these sets of parameters are mapped to two more sets of parameters representing tangent and secant lines of another conic in PG(2, q). Once all possible parameter sets corresponding to tangent and secant lines have been generated, a minimum CBS can be found by selecting a representative from each of these sets in such a way as to get the smallest number of distinct representatives.

Since the resulting computer and optimization model are nearly identical to the models developed above and in Chapter 3, we do not develop them again. Listed in Table 4.6 are the sizes of the minimum CBSs found. The points that comprise the minimum conic blocking set found by either model are located in Appendix B.

m = size of minimum CBS in PG(2, q)

\begin{matrix}q & m & q & m & q & m & q & m & q & m \\ 3 & 3 & 19 & 6 & 41 & 8 & 67 & 9 & 97 & 10 \\ 5 & 4 & 23 & 7 & 43 & 8 & 71 & 9 & 101 & 10 \\ 7 & 4 & 25 & 8 & 47 & 8 & 73 & 9 & 103 & 10 \\ 9 & 5 & 27 & 8 & 49 & 9 & 79 & 8 & 107 & 10 \\ 11 & 6 & 29 & 8 & 53 & 9 & 81 & 10 & 109 & 10 \\ 13 & 6 & 31 & 8 & 59 & 9 & 83 & 10 & 113 & 10 \\ 17 & 6 & 37 & 8 & 61 & 9 & 89 & 10 & 125 & 11 \end{matrix}

Table 4.6: Values for Minimum CBSs

A complete search for minimum CBSs by Cplex in PG(2, 121) and PG(2, 169) was not feasible. Although a CBS of size 11 in PG(2, 121) and a CBS of size 12 in PG(2, 169) were located, due to memory constraints, Cplex was unable to verify that these CBSs are of minimum size.

4.4 Small Conic Blocking Sets in PG(2, q^{2})

The trace-flock construction is a method which produces CBSs in PG(2, p^{h}), h > 2. In this section, we present a construction derived from a model involving restricting quadratic forms to the line z = 0, which gives CBSs of size 2q − 1 in PG(2, q^{2}). Let E = GF(q^{2}), K = GF(q), and F = GF(p) for p an odd prime, q = p^{h}. Let tr(x) = x + x^{q} denote the relative trace of an element x of E into K.

While working with the model described in Section 4.3.1, we were working with conics in the restricted dual setting. A CBS is identified with a set of points on the line z = 0. A conic given by the quadratic form Q, in this setting, is blocked by a set of points (CBS) if

1. ∃ P ∈ CBS ∋ Q(P) = 0, or

2. ∃ P, R ∈ CBS , P ≠ R ∋ Q(P) = and Q(R) =_{}.

The line z = 0 consists of the points {(1, n, 0) |n ∈ E} ∪ {(0, 1, 0)}. For simplicity’s sake, we drop the third coordinate, which is always 0, and denote the points on z = 0 by {(1, n) | n ∈ E} ∪ {(0, 1)}. The conics that are to be blocked have the quadratic form Q(x, y) = Ax^{2} + Dxy + By^{2} with the additional property that D^{2} − 4AB ≠ 0. Because of the equivalence of points written in homogeneous coordinates, for n ≠ 0 the point (1, n) may be written as (m, 1) for some nonzero m ∈ E. These points are rewritten in order to simplify the notation that is used in the proofs of Lemma 4.15 and Theorem 4.23. Next, we assign to each of the points on z = 0 a parameter in E ∪ {∞}. We make the assignments of the points on z = 0 with the elements of E ∪ {∞} as follows: assign to the point (0, 1) the parameter ∞, assign to the point (1, 0) the parameter 0, and to the remaining points (1, n), or equivalently (m, 1), assign the parameter m for all m ∈ E^{∗}.

By transitivity of PGL(2, q) on the points of PG(1, q), we can assume the point given by the parameter 0 is in the CBS. Now, Q(1, 0) = A. This implies that if A = 0, the conic is blocked. Hence, we may assume A is nonzero and divide through by A to obtain the quadratic form Q′(x, y) = x^{2} + dxy + ay^{2}. Since the remaining points to be chosen for the CBS are of the form (x, 1), throughout the rest of this section we will work with the quadratic form Q given by

Q′(x, 1) = Q(x) = x^{2} + dx + a,  (4.1)

and we identify the points of z = 0 with their assigned parameters in E. Observe that for any point m chosen for the CBS,

Q(m) = m^{2} + dm + a.  (4.2)

We also have that

Q′(1, 0) = 1.  (4.3)

For Q not to be blocked by a set S, the “squarity” (being a square or a nonsquare) of (4.2) has to be the same as (4.3), for all x ∈ S. Now, as 1 = , the only conics that are not blocked by 0 are those for which Q(x) = for all points x ∈ S.

Before the main result of this section is given, several algebraic observations will be made.

Lemma 4.12 E is partitioned into cosets of ker(tr) and each coset has size q.

Proof: The relative trace function is a homomorphism from E onto K. Now, tr(x) = x + x^{q} = 0 if and only if x = 0 or 1 + x^{q−1} = 0. Define f(x) = x^{q−1} for all x ∈ E. We show that f(x) = −1 has q − 1 solutions. Let α be a primitive element of E. Then x = α^{(q+1)/2} satisfies x^{q−1} = −1. So, −1 is in the image of f. Now, f is a multiplicative homomorphism and q − 1 divides the order q^{2} − 1 of the multiplicative (cyclic) group, E^{∗}. Thus, since −1 is in the image of f, there are exactly q − 1 solutions. This shows that the kernel of tr has size q. Hence, the image of tr has size q^{2}/q = q. Finally, the domain of a homomorphism is partitioned into cosets of the kernel, so E is partitioned into cosets of the kernel of tr.

The previous lemma tells us that there are q elements in E of relative trace k for any k ∈ K. This fact is used in the proof of Theorem 4.23, as well as several of the observations preceding Theorem 4.23.

Lemma 4.13 There are exactly \frac{q−1}{2} squares of E in every proper coset of K in E.

Proof: There are \frac{q^{2}−1}{2} squares in E^{∗} and q − 1 squares in K^{∗}. So, we have \frac{q^{2}−1}{2} − (q − 1) = (q − 1) (\frac{q−1}{2}) squares in E \ K. We show that there are q − 1 additive cosets of K, and each coset contains exactly \frac{q−1}{2} squares in E \ K.

Since E is a quadratic extension over K (|E : K| = 2), every element η ∈ E can be uniquely expressed as an element of the form η = aλ + b where a,b ∈ K and λ is a primitive element of E over K. Consider the additive cosets of K distinct from K. These cosets are expressible as η + K. But, as η = aλ + b, we have that η + K is equivalent to the coset aλ + K, for any a ∈ K^{∗}.

Assume the coset λ + K has exactly x squares of E \ K in it. When a ≠ 0, each of the cosets a(λ + K) ≡ aλ + K also contains exactly x squares of E \ K, since a is a square in E. There are q − 1 nonzero choices for a, so we have q − 1 cosets of K. Now, these q − 1 cosets must contain the same number of squares of E \ K, therefore, x = \frac{q−1}{2}.

Observation 4.14 Let Q(x) = x^{2} + dx + a where a, d ∈ E. If Q(x) = Q(y) with x ≠ y, then x = −d − y.

Proof: Suppose Q(x) = Q(y). Then x^{2} + dx + a = y^{2} + dy + a ⇒ (x^{2} − y^{2}) + d(x − y) = 0, and so, x = −d − y.

Lemma 4.15 Q(x) = x^{2} + dx + a = ∈ E^{∗} for all x ∈ K, where a ≠ d^{2}/4, if and only if a,d ∈ K.

Proof: Clearly, if a and d are in K, x^{2} + dx + a = for all valid choices of a and d.

Assume d ∈ K. In Observation 4.14, we showed that Q(x) = Q(−d − x), so each value Q(x) appears twice, except for Q(\frac{−d}{2}) which appears only once. This implies that Q takes on exactly \frac{q−1}{2} + 1 = \frac{q+1}{2} distinct values. If for some x ∈ K, Q(x) ∈ K, there exists an s ∈ E such that x^{2} + dx + a = s^{2} ∈ K. This implies that a = s^{2} − x^{2} − dx ∈ K, and we are done. Thus, we may assume that none of the values Q(x) are in K.

Observe that Q(x_{i}) − Q(x_{j}) ∈ K ∀i, j, since (x_{i}^{2} − x_{j}^{2}) + d(x_{i} − x_{j}) ∈ K. So, the set of Q(x_{i}) is contained in one coset of K, that is, a + K. By Lemma 4.13, there are only \frac{q−1}{2} squares in each coset of K. Therefore, there are not enough squares in a coset of K, for all x ∈ K to yield a square. This contradiction implies that we need only consider the case where d ∉ K.

Suppose a = 0. Then, Q(0) = 0 which is not a square in E^{∗}. Therefore, for the remainder of the proof, we assume a ≠ 0.

Since E is a quadratic extension over K, there exists a primitive irreducible polynomial

f(x) = x^{2} + ex + b

with e, b ∈ K, both nonzero, and let λ be a root of this polynomial. That is, λ is a primitive element of E over K. Then,

\begin{aligned}f(λ) & = & λ^{2} + eλ + b = 0 \\ & ⇒ & λ^{2} = −eλ − b. \end{aligned}

We also have that every element of E can be expressed uniquely in the form

ωλ + ρ

where ω, ρ ∈ K. Let d = δλ + β, with δ, β ∈ K and, by assumption, δ ≠ 0.

Now, Q(x) = x^{2} + dx + a = (μ_{x}λ + ν_{x})^{2} = (−μ_{x}λ − ν_{x})^{2} with μ_{x}, ν_{x} ∈ K and μ_{x} ≠ 0. By associating either μ_{x} or −μ_{x} with each x ∈ K we can define a function β_{1} : K ↦ K. Q and β_{1} implicitly define β_{2} : K ↦ K, so that Q(x) = x^{2} + dx + a = (β_{1}(x)λ + β_{2}(x))^{2}. We then have:

Q(x) = x^{2} + dx + a = x^{2} + (δλ + β)x + a
= (δx)λ + (x^{2} + βx + a)
= (β_{1}(x)λ + β_{2}(x))^{2}
= β_{1}^{2}(x)λ^{2} + 2β_{1}(x)β_{2}(x)λ + β_{2}^{2}(x)
= β_{1}^{2}(x)[−eλ − b] + 2β_{1}(x)β_{2}(x)λ + β_{2}^{2}(x)
= [2β_{1}(x)β_{2}(x) − eβ_{1}^{2}(x)]λ + [β_{2}^{2}(x) − bβ_{1}^{2}(x)].

Thus,

δx = 2β_{1}(x)β_{2}(x) − eβ_{1}^{2}(x)  (4.4)

and

x^{2} + βx + a = β_{2}^{2}(x) − bβ_{1}^{2}(x).  (4.5)

Since every function over a finite field, more specifically K, can be represented as a polynomial of degree ≤ q − 1, we can view the functions β_{i}(x) as polynomials of x. Moreover, if need be, β_{1}(x) can be chosen so that deg(β_{1}(x)) is as small as possible.

Assume that in (4.4) deg(RHS) ≤ q−1. This implies that δx = β_{1}(x)[2β_{2}(x)− eβ_{1}(x)] in K[x]. Now assume that β_{1}(x) has degree less than or equal to one. If β_{1}(x) is not constant, then 2β_{2}(x) − eβ_{1}(x) must be constant. Thus, since β_{1}(x) is linear, we see that β_{2}(x) must also be linear. Let β_{1}(x) = Ax + B and β_{2}(x) = Cx + D, with A ≠ 0, so that 2β_{2}(x) − eβ_{1}(x) = k, for some constant k.

2(Cx + D) − e(Ax + B) = k
⇒ (2C − eA)x + (2D − eB) = k
⇒ 2C − eA = 0
⇒ C = \frac{eA}{2}.

We now have

x^{2} + βx + a = (\frac{Ae}{2}x + D)^{2} − b(Ax + B)^{2}
= (\frac{A^{2}e^{2}}{4} − A^{2}b) x^{2} + (ADe − 2ABb)x + (D^{2} − bB^{2}),

implying that

\frac{A^{2}e^{2}}{4} − A^{2}b = 1, β = ADe − 2ABb, a = D^{2} − bB^{2}.

Now, \frac{A^{2}e^{2}}{4} − A^{2}b = 1 implies that

A^{2}e^{2} − 4A^{2}b = 4
⇒ A^{2}(e^{2} − 4b) = 4
⇒  e^{2} − 4b = \frac{4}{A^{2}}
⇒  e^{2} − 4b = .

But, f(x) = x^{2} + ex + b is a monic irreducible polynomial of degree two over K[x]. If e^{2} − 4b = , then f(x) factors, a contradiction. Thus, β_{1}(x) and β_{2}(x) cannot both be linear functions.

Still under the assumption that deg(RHS) ≤ q − 1, if β_{1}(x) is constant, we see that β_{2}(x) must be linear. Let β_{1}(x) = B and β_{2}(x) = Cx + D. Then

\begin{aligned}δx & = & 2B(Cx + D) − eB^{2} \\ & = & 2BCx + (2BD − eB^{2}) \end{aligned}

implying that

δ = 2BC.  (4.6)

Similarly,

\begin{aligned}x^{2} + βx + a & = & (Cx + D)^{2} − bB^{2} \\ & = & C^{2}x^{2} + 2CDx + (D^{2} − bB^{2}) \end{aligned}

implying that

1 = C^{2}  (4.7)
β = 2CD  (4.8)
a = D^{2} − bB^{2}.  (4.9)

Now, (4.7) ⇒ C = ±1. With C = 1, (4.6) implies that δ = 2B ⇒ B = \frac{δ}{2}. Also, (4.8) implies that D = \frac{β}{2} . Using these relations,

β_{1}(x) = B = \frac{δ}{2} and β_{2}(x) = (x + \frac{β}{2} ).

Thus,

x^{2} + dx + a = (β_{1}(x)λ + β_{2}(x))^{2}
= (\frac{δ}{2}λ + (\frac{β}{2} + x))^{2}
= (\frac{δλ+β}{2} + x)^{2}
= (x + \frac{d}{2})^{2}
⇒ a = \frac{d^{2}}{4} .→←

In other words, the conic is degenerate. The same contradiction is obtained when C = −1. So, β_{1}(x) cannot be constant.

Assume that deg(β_{1}(x)) ≥ 2. Since δx = β_{1}(x) [2β_{2}(x) − eβ_{1}(x)], with deg(β_{1}(x)) ≥ 2, we must have [2β_{2}(x) − eβ_{1}(x)] = 0. But, if [2β_{2}(x) − eβ_{1}(x)] = 0, then necessarily δ = 0. →←

We are now left to consider that (4.4) is an equality in K[x] with

δx^{q} = β_{1}(x) [(2β_{2}(x) − eβ_{1}(x))] .

This implies that β_{1}(x) | x^{q}, more precisely β_{1}(x) = x^{j} for some j ≤ q − 1 and x^{q−j} = \frac{1}{δ} (2β_{2}(x) − eβ_{1}(x)). Solving explicitly for β_{2}(x), we find that β_{2}(x) = \frac{δx^{q−j}+ex^{j}}{2} . Then from (4.5),

x^{2} + βx + a = [β_{2}^{2}(x) − bβ_{1}^{2}(x)]
= \frac{δ^{2}}{4} x^{2q−2j} + \frac{eδ}{2} x^{q} + \frac{e^{2} − 4b}{4}x^{2j}.

This cannot occur since when x = 0, this implies a = 0. →← Thus, when δ ≠ 0, there does not exist a polynomial β_{1}(x). Hence, δ = 0, that is, the case d ∉ K does not arise.

This lemma also aids in showing that, unlike the situation in planes of even order, the set of lines through a point in a Baer subplane do not form a CBS. The following observations aid in the proof of Theorem 4.23.

Observation 4.16 Let α be a generator of E^{∗}. The q trace 0 elements of E are N = \{ λα^{\frac{q+1}{2}} | λ ∈ K\}.

Proof: Since λ ∈ K, λ^{q} = λ. Recall that α^{( \frac{q+1}{2} )q} = α^{\frac{q^{2}+q}{2}} = α^{\frac{q^{2}−1+1+q}{2}} = α^{\frac{q^{2}−1}{2} + \frac{q+1}{2}} = (α^{\frac{q^{2}−1}{2}} ) (α^{\frac{q+1}{2}} ) = −1α^{\frac{q+1}{2}} , since α^{\frac{q^{2}−1}{2}} = −1. Now, tr(λα^{\frac{q+1}{2}} ) = λα^{\frac{q+1}{2}} +λ^{q}α^{\frac{q+1}{2} q} = λα^{\frac{q+1}{2}} −λα^{\frac{q+1}{2}} = 0. For any λ ∈ K, we have that tr(λα^{\frac{q+1}{2}} ) = 0, and so there are q elements in E of trace 0. By Lemma 4.12, this accounts for all of the trace 0 elements of E.

Observation 4.17 For all n ∈ N^{∗} = N \ {0}, n^{2} is a nonsquare within K.

Proof: Since n ∈ N^{∗}, n = λα^{\frac{q+1}{2}} , for some λ ∈ K^{∗}. With λ ∈ K^{∗} and α a generator of E^{∗}, we may express λ as α^{k(q+1)}, for some k. Now, n = α^{k(q+1)}α^{\frac{q+1}{2}} = α^{(2k+1)(q+1)/2}, and since α^{q+1} is a primitive element of K, we have that n^{2} = (α^{q+1})^{2k+1} =_{}within K.

Observation 4.18 For all n ∈ N, λ, d ∈ K, and k ∈ F, we have that tr (λn + \frac{d+kn}{2}) = d.

Proof: Since \frac{d}{2} ∈ K, (\frac{d}{2})^{q} = \frac{d}{2} and tr (\frac{d}{2}) = \frac{d}{2} + (\frac{d}{2})^{q} = d. Also, as tr(sn) = str(n) ∀s ∈ K, we have that tr(λn) = λtr(n) = 0 and tr (\frac{kn}{2}) = \frac{k}{2}tr(n) = 0. Hence, tr (λn + \frac{d+kn}{2}) = tr(λn) + tr (\frac{d}{2}) + tr (\frac{kn}{2}) = tr (\frac{d}{2}) = d.

Observation 4.19 For q ≡ 1 mod 4, all nonzero trace 0 elements are nonsquares in E. For q ≡ 3 mod 4, all nonzero trace 0 elements are squares in E.

Proof: If q = 4m + 1, then \frac{q+1}{2} = 2m + 1, which is odd. Since λ ∈ K^{∗}, λ is a square in E. The product of a square (λ) and a nonsquare (α^{\frac{q+1}{2}} ) is a nonsquare. Hence, when q ≡ 1 mod 4, all nonzero trace 0 elements in E are nonsquares.

A similar argument gives the desired result for q ≡ 3 mod 4.

Observation 4.20 For q ≡ 1 mod 4, there are \frac{q+1}{2} square elements in E of trace d. For q ≡ 3 mod 4, there are \frac{q−1}{2} square elements in E of trace d.

Proof: Let x denote the number of square trace 1 elements in E. Then, there are x square elements in E with trace k, k ∈ K^{∗}. So, there are x(q − 1) square elements with nonzero trace. Because there are \frac{q^{2}−1}{2} nonzero squares in E, we have that (# of square nonzero trace 0 elements) +x(q − 1) = \frac{q^{2}−1}{2}.

By Observation 4.19, when q ≡ 1 mod 4, there are no nonzero square trace 0 elements in E, so x = \frac{q+1}{2}; and when q ≡ 3 mod 4, all nonzero trace 0 elements in E are squares, giving x = \frac{q−1}{2}.

Observation 4.21 Let λ, λ′, d ∈ K, k ∈ F, and n ∈ N^{∗}. Then, λn + \frac{d+kn}{2} = λ′n + \frac{d−kn}{2} only when λ′ = λ + k.

Proof:

λn + \frac{d+kn}{2} = λ′n + \frac{d−kn}{2}
⇔ λn + kn = λ′n
⇔ λ + k = λ′.

Observation 4.22 For p an odd prime, p |̸\frac{p^{m}+1}{2} and p |̸\frac{p^{m}−1}{2}, m ≥ 1. Proof: Trivial.

Theorem 4.23 In PG(2, q^{2}), q = p^{h} an odd prime power, the 2q − 1 points on the line z = 0 with parameters that either have trace 0 or are in the subfield K form a CBS.

Proof:

By Lemma 4.15, the conics that are not blocked by the points with parameters in the subfield are those with coefficients in the subfield. So, assume that d, a ∈ K, with a ≠ 0, and let Q(x) = x^{2} + dx + a.

If d^{2} − 4a = within K, Q(x) factors. That is, if d^{2} − 4a = s^{2}, s ∈ K, then Q(x) = (x + \frac{d+s}{2})(x + \frac{d−s}{2}). Clearly, Q has roots in K, therefore, Q is blocked by K.

If d^{2} − 4a = 0, Q is degenerate.

Since the conics with square or zero discriminant are blocked, we need only examine the case where the discriminant is a nonsquare within K. Assume d^{2} − 4a =_{}within K. Then, by Observation 4.17, there is some n ∈ N^{∗} such that n^{2} = d^{2} − 4a and Q(x) = (x + \frac{d+n}{2})(x + \frac{d−n}{2}).

Define the graph G by

V (G) = {(λ, m) | λ ∈ K, m ∈ F},

where two vertices (λ, m) and (λ′, m′) are adjacent if λ = λ′ and ∃ k ∈ F such that Q ((λ + k)) = (λn + \frac{d+mn}{2}) (λn + \frac{d+m′n}{2}). By Observation 4.21, exactly two values of Q share a common factor. So, G must be a regular graph of degree two, and hence, a union of cycles.

Let λ ∈ K and λn ∈ N, where n is fixed in N^{∗}. Observe that

Q ((λ + 1)n) = (λn + \frac{d+3n}{2}) (λn + \frac{d+n}{2})
Q (λn)  = (λn + \frac{d+n}{2}) (λn + \frac{d−n}{2})
Q ((λ − 1)n) = (λn + \frac{d−n}{2}) (λn + \frac{d−3n}{2}).

More generally, for any k in the prime subfield F = GF(p), we have that the value of Q ((λ + k)n) is (λn + \frac{d+(2k+1)n}{2}) (λn + \frac{d+(2k−1)n}{2}). For fixed λ ∈ K, we obtain a collection of p distinct values Q ((λ + k)n) such that, by Observation 4.21, exactly two of the values in this collection share a common factor of this form. Moreover, if λ′ ≠ λ + k for some λ, λ′ ∈ K and all k ∈ F, the two values Q ((λ + k)n) and Q (λ′n) do not share a common factor. So, G is a union of p^{h−1} p-cycles such that every value Q(λn) for all λ ∈ K appears as an edge in some p-cycle. Figure 4.2 illustrates this idea. Combining Observation 4.18 and

Figure 4.2: A Collection of Values Q ((λ + k)n)

Observation 4.20, we have that all the factors of Q have the same trace, and we know exactly how many of these factors are squares and nonsquares.

When q ≡ 1 mod 4 (resp. 3 mod 4), \frac{q+1}{2} (resp. \frac{q−1}{2}) of the factors must be squares in E. But, by Observation 4.22, these \frac{q+1}{2} (resp. \frac{q−1}{2}) square factors cannot be distributed over the p-cycles in such a way that the p-cycles consist only of squares or nonsquares. Hence, there must exist a p-cycle in which adjacent vertices have different squarity, so there exists a value Q(λn) that is a nonsquare, and Q is blocked.

Thus, we have that the q points with parameters in the subfield K and the q − 1 points in the set of nonzero trace 0 elements N^{∗} form a CBS of size 2q − 1 in PG(2, q^{2}).

To illustrate the proof of Theorem 4.23, consider the following example. Example 15.

Let q^{2} = 81, so that q = 9 and p = 3. For the results given in this example, we will be using the primitive polynomial f(x) = x^{4} − x^{2} − x − 1 for E = GF(81). Now, K^{∗} = {α^{10k} | 0 ≤ k ≤ 8} and N = {λα^{5} | λ ∈ K}. It can be shown that

\begin{matrix}1 + 1 = −1 & α^{30} + 1 = α^{50} & α^{60} + 1 = α^{10} \\ α^{10} + 1 = α^{70} & −1 + 1 = 0 & α^{70} + 1 = α^{60} \\ α^{20} + 1 = α^{30} & α^{50} + 1 = α^{20} & 0 + 1 = 1 \end{matrix} .

We illustrate how the conics not blocked by points with subfield parameters are blocked by points with parameters that have relative trace 0. The conics that remain to be blocked by points with parameters that have relative trace 0 are those of the form Q(x) = x^{2} + dx + a where d, a ∈ K and d^{2} − 4a = n^{2} for some n ∈ N^{∗}. Observe that Q ((λ + k)n) = (λn + \frac{d+(2k+1)n}{2}) (λn + \frac{d+(2k−1)n}{2}) for any λ ∈ K and k ∈ F. We examine the values of Q.

Q (α^{70}n) = Q ((α^{10} + 1)n) = (α^{10}n + \frac{d}{2}) (α^{10}n + \frac{d+n}{2})
Q (α^{10}n) = Q ((α^{10}n + 0)) = (α^{10}n + \frac{d+n}{2}) (α^{10}n + \frac{d−n}{2})
Q (α^{60}n) = Q ((α^{10} − 1)n) = (α^{10}n + \frac{d−n}{2}) (α^{10}n + \frac{d}{2})

Q (α^{30}n) = Q ((α^{20} + 1)n) = (α^{20}n + \frac{d}{2}) (α^{20}n + \frac{d+n}{2})^{Q (α^{20}n) = Q ((α^{20}n + 0)) = (α^{20}n + \frac{d+n}{2}) (α^{20}n + \frac{d−n}{2})}^{Q (α^{50}n) = Q ((α^{20} − 1)n) = (α^{20}n + \frac{d−n}{2}) (α^{20}n + \frac{d}{2})}^{Q (−n) = Q ((1 + 1)n) =  (1n + \frac{d}{2}) (1n + \frac{d+n}{2})}^{Q (n) = Q ((1 + 0)n) = (1n + \frac{d+n}{2}) (1n + \frac{d−n}{2})} Q (0n) = Q ((1 − 1)n) =  (1n + \frac{d−n}{2}) (1n + \frac{d}{2}).

It is easy to see that any given factor appears in exactly two values of Q. The following union of 3-cycles represents the distribution of the factors of Q(λn), as λ varies through K.

Figure 4.3: The Union of 3-Cycles

Since 9 ≡ 1 mod 4, five of the factors given as the vertex labels in Figure 4.3 must be squares and the remaining factors must be nonsquares. This implies that there must exist a 3-cycle that contains both and squares and nonsquares. So, there is a λ ∈ K such that Q(λn) =_{}, and we have that these conics, which are not blocked by points with subfield parameters, are blocked by points with trace 0 parameters.

For instance, consider the specific conic Q(x) = x^{2} + α^{10}x + 1 whose discriminant, α^{20} − 1 = α^{50} = (α^{25})^{2}, is a nonsquare with K and is an element of N. With n = α^{25}, we can factor Q so that Q(x) = (x + \frac{α^{10}+α^{25}}{2} ) (x + \frac{α^{10}−α^{25}}{2} ) = (x + α^{48}) (x + α^{32}). We have that the values of Q are

Q (α^{70}α^{25}) = Q (α^{15}) = (α^{15} + α^{48}) (α^{15} + α^{32}) = α^{33} ∗ α^{79} = α^{32} =
Q (α^{10}α^{25}) = Q (α^{35}) = (α^{35} + α^{48}) (α^{35} + α^{32}) = α^{79} ∗ α^{44} = α^{43} =_{}
Q (α^{60}α^{25}) = Q (α^{5}) = (α^{5} + α^{48}) (α^{5} + α^{32}) = α^{44} ∗ α^{33} = α^{77} =_{}
Q (α^{30}α^{25}) = Q (α^{55}) = (α^{55} + α^{48}) (α^{55} + α^{32}) = α^{71} ∗ α^{57} = α^{48} =
Q (α^{20}α^{25}) = Q (α^{45}) = (α^{45} + α^{48}) (α^{45} + α^{32}) = α^{57} ∗ α^{76} = α^{53} =_{}
Q (α^{50}α^{25}) = Q (α^{75}) = (α^{75} + α^{48}) (α^{75} + α^{32}) = α^{76} ∗ α^{71} = α^{67} =_{}
Q (α^{40}α^{25}) = Q (α^{65}) = (α^{65} + α^{48}) (α^{65} + α^{32}) = α^{32} ∗ α^{50} = α^{2} =
Q (α^{0}α^{25}) = Q (α^{25}) = (α^{25} + α^{48}) (α^{25} + α^{32}) = α^{50} ∗ α^{48} = α^{18} =
Q (0) = Q (0)  = (α^{48}) (α^{32})  = α^{48} ∗ α^{32} = 1 = .

Figure 4.4 represents the graph of the factors of Q over N.

Figure 4.4: The 3-Cycles for Q(x) = x^{2} + α^{10}x + 1

For this choice of conic, we see that there are two 3-cycles that hold a combination of squares and nonsquares. More importantly, we see that Q (α^{35}), Q (α^{5}), Q (α^{45}), and Q (α^{75}) are all nonsquares. This conic is clearly blocked by four elements of N.

4.5 Bounds on the Sizes of Minimum Conic Blocking Sets

In this section, bounds are given for the size of a minimum conic blocking set in PG(2, q). For the purposes of obtaining these bounds, we use the restricteddual model developed in Section 4.3.1. We also assume that the points identified with parameters 0, 1, and ∞ are in the CBS. We begin by examining the upper bound for minimum CBSs.

Based on [24, Thm.67], the following table gives the counts on the number of nonsquares (nonzero squares) in a finite field, which when subtracted from the

\begin{matrix}q ≡ 3 mod 4 & q ≡ 1 mod 4 \\ 1 −_{}1 −_{\begin{matrix}\frac{q−3}{4} & \frac{q−3}{4} \\ \frac{q+1}{4} & \frac{q−3}{4} \end{matrix}} & 1 −_{}1 −_{\begin{matrix}\frac{q−1}{4} & \frac{q−5}{4} \\ \frac{q−1}{4} & \frac{q−1}{4} \end{matrix}} \end{matrix}

Table 4.14: Squarity Subtraction Tables

element 1 give a square (nonzero) or nonsquare. Lemma 4.24 There are (\frac{q−3}{2})^{2} nondegenerate quadrics of the form Q(x) = x^{2} + dx + a with the properties

1. Q(0) = a = ≠ 0, and

2. Q(1) = 1 + d + a = ≠ 0.

Of these, \frac{(q−3)(q−5)}{8} are reducible and \frac{(q−3)(q−1)}{8} are irreducible.

Proof: There are \frac{q−1}{2} nonzero choices for a. For a fixed a, as d varies through the field, d + a also varies. So, there are \frac{q−1}{2} (d + a)’s that are ’s such that 1 + d + a = ≠ 0. When d = ±2\sqrt{a}, we have that 1 + d + a = (1 ± \sqrt{a})^{2}, and when a = 1 and d = −2, we have (1 − \sqrt{1})^{2} = 0. Although the choices of d = ±2\sqrt{a} satisfy 1+d+a = ≠ 0 for a ≠ 1, these choices of d yield a degenerate quadric. Thus, these choices are removed from the count of the eligible ones. This leaves \frac{q−1}{2} − 2 = \frac{q−5}{2} possible choices for d for each a. When a = 1 and d = −2, Q is a degenerate quadric and 1 + d + a = 0. This choice of a and d was subtracted twice, and hence, we must add one back in. There are \frac{q−1}{2} choices for a and \frac{q−5}{2} choices for d, and so there are

(\frac{q − 1}{2}) (\frac{q − 5}{2}) + 1 = (\frac{q − 3}{2})^{2}

quadratic forms with the specified properties.

If x^{2} + dx + a is reducible, then we may write this quadric as

x^{2} + dx + a = (x − β)(x − α)
= x^{2} − (α + β)x + αβ,

for some α, β ∈ E, with α ≠ β. To count the number of reducible quadrics, we determine how many α’s and β’s satisfy αβ = , 1 − (α + β) + αβ = , and (α − β)^{2} ≠ 0. As we want to count the number of quadrics such that Q(1) = (1 − α)(1 − β) = , we must consider two cases. The first case is when (1 − α) and (1 − β) are both squares and the second case is when (1 − α) and (1 − β) are both nonsquares. To complete this count, consider the cases of q ≡ ±1 mod 4 separately. Case q ≡ 3 mod 4

Suppose α = . Then by Table 4.14, there are \frac{q−3}{4} choices for α such that 1−α = ≠ 0, and so, there are \frac{q−3}{4}−1 = \frac{q−7}{4} choices for β such that 1−β = ≠ 0. Similarly, there are \frac{q−3}{4} choices for α such that 1 − α = _{}, and so, there are \frac{q−3}{4} − 1 = \frac{q−7}{4} choices for β such that 1 − β =_{}.

Now, suppose α =_{}. Then by Table 4.14, there are \frac{q−3}{4} choices for α such that 1 − α = ≠ 0, and so, there are \frac{q−3}{4} − 1 = \frac{q−7}{4} choices for β such that 1 − β = ≠ 0. Similarly, there are \frac{q+1}{4} choices for α such that 1 − α =_{}, and so, there are \frac{q+1}{4} − 1 = \frac{q−3}{4} choices for β such that 1 − β =_{}.

So, when q ≡ 3 mod 4, we have \frac{1}{2} [3 (\frac{q−3}{4}) (\frac{q−7}{4}) + (\frac{q+1}{4}) (\frac{q−3}{4})] = \frac{(q−3)(q−5)}{8}

and there are \frac{(q−3)(q−5)}{8} reducible quadrics. Case q ≡ 1 mod 4

Suppose α = . Then by Table 4.14, there are \frac{q−5}{4} choices for α such that 1−α = ≠ 0, and so, there are \frac{q−5}{4}−1 = \frac{q−9}{4} choices for β such that 1−β = ≠ 0. Similarly, there are \frac{q−1}{4} choices for α such that 1 − α = _{}, and so, there are \frac{q−1}{4} − 1 = \frac{q−5}{4} choices for β such that 1 − β =_{}.

Suppose α =_{}. Then by Table 4.14, there are \frac{q−1}{4} choices for α such that 1−α = ≠ 0, and so, there are \frac{q−1}{4}−1 = \frac{q−5}{4} choices for β such that 1−β = ≠ 0. Similarly, there are \frac{q−1}{4} choices for α such that 1 − α = _{}, and so, there are \frac{q−1}{4} − 1 = \frac{q−5}{4} choices for β such that 1 − β =_{}.

So, when q ≡ 1 mod 4, we have \frac{1}{2} [3 (\frac{q−1}{4}) (\frac{q−5}{4}) + (\frac{q−5}{4}) (\frac{q−9}{4})] = \frac{(q−3)(q−5)}{8}, and so, there are \frac{(q−3)(q−5)}{8} reducible quadrics.

Hence, the number of reducible quadrics with the specified properties is \frac{(q−3)(q−5)}{8}. Subtracting this from the total number of quadrics with the specified properties gives \frac{(q−3)(q−1)}{8} irreducible quadrics.

Theorem 4.25 If B is a minimum CBS in PG(2, q), q odd, then |B| ≤ 2 log_{2}(q − 5) + 1.

Proof: We obtain an upper bound for the size of a minimum CBS by comparing the total number of k-sets in a pencil with the appropriate number of quadrics, of the form described in Lemma 4.24.

Let Q(x) = x^{2} + dx + a and note that Q(s) = Q(−d − s). Now, Q(\frac{−d}{2}) = (−1)\frac{1}{4}(d^{2} − 4a) = when −1 =_{}and d^{2} − 4a =_{}, and also when −1 = and d^{2} − 4a = . So, every value Q(x) appears twice, with the exception of Q(\frac{−d}{2}) which appears only once.

For q ≡ 3 mod 4, Q(\frac{−d}{2}) = when Q is irreducible. Thus, the irreducible quadrics will always yield an odd number of squares. Since \frac{q−1}{2} is odd, there will be \frac{q−1}{2} squares for the irreducible quadrics and \frac{q+1}{2} squares for the reducible quadrics.

For q ≡ 1 mod 4, Q(\frac{−d}{2}) = when Q is reducible. Thus, the reducible quadrics will always yield an odd number of squares. Since \frac{q+1}{2} is odd, there will be \frac{q+1}{2} squares for the reducibles and \frac{q−1}{2} squares for the irreducibles.

If Q is irreducible, then there are \frac{q−1}{2} elements x ∈ GF(q) that give a square value for Q(x). Since these \frac{q−1}{2} elements include 0 and 1, we have \frac{q−1}{2} − 2 = \frac{q−5}{2} elements in GF(q) \ {0, 1} such that Q(x) = .

If Q is reducible, then there are \frac{q+1}{2} elements x ∈ GF(q) that give a square value for Q(x). Since these \frac{q+1}{2} elements include 0, 1, and the two roots of Q, we have \frac{q+1}{2} − 4 = \frac{q−7}{2} elements in GF(q) \ \{0, 1, \frac{−d±\sqrt{d^{2}−4a}}{2a}\} such that Q(x) = .

There are \binom{q−2}{k} sets of size k of elements of GF(q) that do not include 0 and 1. As there are \frac{(q−3)(q−1)}{8} irreducible quadrics and \frac{(q−3)(q−5)}{8} reducible quadrics, we have that there are \binom{\frac{q−1}{2} −2}{k} \frac{(q−3)(q−1)}{8} + \binom{\frac{q+1}{2} −4}{k} \frac{(q−3)(q−5)}{8} k-sets of points contained in nondegenerate quadrics which give only squares in the image of the quadrics. That is, for which Q(x) = for all x in the set of k points. As long as,

\binom{q − 2}{k} > \binom{\frac{q−5}{2}}{k}\frac{(q − 3)(q − 1)}{8} + \binom{\frac{q−7}{2}}{k}\frac{(q − 3)(q − 5)}{8},

there must be a CBS of size k+3 (which includes 0, 1, ∞). In other words, if there are more sets on the left, then some set of size k + 3 cannot give all squares for any of the conics and therefore is a CBS. Now, suppose k + 3 > 2 log_{2}(q − 5) + 1, then we have that

k + 2 > 2 log_{2}(q − 5)
⇒ 2^{k+2} >  (q − 5)^{2}
⇒ 2^{k} > \frac{1}{2^{2}} (q − 3)(q − 5).

Since q − k > \frac{q−(2k+3)}{2} for all k > 0, (or equivalently 2(q − k) > q − (2k + 3) for all k > 0), we have

2^{k}(q − 2)(q − 3) ⋯ ((q − 2) − (k − 1)) > (\frac{q−3}{2}) (\frac{q−5}{2}) (q − 7) ⋯
(q − 3 − 2k) (q − 3 − k)
⇒ (q − 2)(q − 3) ⋯ ((q − 2) − (k − 1)) > (\frac{q−3}{2}) (\frac{q−5}{2}) (\frac{q−7}{2}) ⋯
(\frac{q−3−2k}{2}) (\frac{q−3−k}{2})
⇒  \binom{q−2}{k}  > (\frac{q−3}{4}) (q − 3 − k)\binom{\frac{q−5}{2}}{k}
=  \binom{\frac{q−5}{2}}{k} \frac{(q−3)(q−1)}{8}
+\binom{\frac{q−7}{2}}{k} \frac{(q−3)(q−5)}{8}.

So, \binom{q−2}{k} > \binom{\frac{q−5}{2}}{k} \frac{(q−3)(q−1)}{8} + \binom{\frac{q−7}{2}}{k} \frac{(q−3)(q−5)}{8} when k + 3 > 2 log_{2}(q − 5) + 1. Thus, |B| ≤ 2 log_{2}(q − 5) + 1.

The following theorem is obtained from Theorem 2.2.

Theorem 4.26 If S denotes the number of nonsquares n in E for which n+1 = and N denotes the number of nonsquares m for which m + 1 =_{}, we have

\begin{matrix}S = \frac{1}{4}(p^{n} − 1), & N = \frac{1}{4}(p^{n} − 5), & if − 1 = ; \\ S = \frac{1}{4}(p^{n} + 1), & N = \frac{1}{4}(p^{n} − 3), & if − 1 =_{}. \end{matrix}

Theorem 4.27 If B is a minimum CBS in PG(2, q), q ≥ 9, then |B| ≥ 5.

Proof: Let Q(x) = x^{2} + dx + a be defined as in Lemma 4.24. Since 0, 1, and ∞ are already in the CBS, we have that a = ≠ 0 and 1 + d + a = ≠ 0. Suppose that B = {0, 1, ∞, t} is a CBS in PG(2, q).

Let d = −t so that Q_{t}(x) = x^{2} − tx + a. Now,

Q_{t}(0) = a
Q_{t}(1) = 1 − t + a
Q_{t}(t) = t^{2} − t^{2} + a = a.

For every fixed t ≠ 0, 1, we exhibit an a such that Q_{t}(1) = . Then, for this value of t, we find a nondegenerate quadric that is not blocked by B. Assume q ≡ 3 mod 4.

Suppose t is such that 1 − t = . By Theorem 2.2, there are \frac{q−3}{4} nonzero square values σ^{2} for which σ^{2} + 1 = . Let a = \frac{1−t}{σ^{2}} so that σ^{2} = \frac{1−t}{a}. Then, 1 + σ^{2} = 1 + \frac{1−t}{a} = implying that Q_{t}(1) = .

Suppose t is such that 1 − t =_{}. By Theorem 4.26, there are \frac{q+1}{4} nonsquare values n for which n + 1 = . Let a = \frac{1−t}{n} so that n = \frac{1−t}{a}. Then, 1 + n = 1 + \frac{1−t}{a} = implying that Q_{t}(1) = . Assume q ≡ 1 mod 4.

Suppose t is such that 1 − t = . By Theorem 2.2, there are \frac{q−5}{4} nonzero square values σ^{2} for which σ^{2} + 1 = . Let a = \frac{1−t}{σ^{2}} so that σ^{2} = \frac{1−t}{a}. Then, 1 + σ^{2} = 1 + \frac{1−t}{a} = implying that Q_{t}(1) = .

Suppose t is such that 1 − t =_{}. By Theorem 4.26, there are \frac{q−1}{4} nonsquare values n for which n + 1 = . Let a = \frac{1−t}{n} so that n = \frac{1−t}{a}. Then, 1 + n = 1 + \frac{1−t}{a} = implying that Q_{t}(1) = .

So, for every choice of t ∈ GF(q)\{0, 1}, there exists a nondegenerate quadric that is not blocked by the set B. Hence, for q ≥ 9 any CBS in PG(2, q) of minimum size must consist of at least five points.

Note that in the previous theorem, the case of q = 7 was excluded. If q = 7, q ≡ 3 mod 4 and \frac{7−3}{4} = 1. In GF(7), 1 is the only square such that 1 + 1 = . Then, a = 1 − t must be a square, and the only choices for t that satisfy this condition are t = 2, 4, 6. These choices for t give rise to the following quadrics: x^{2} − 2x + 1, x^{2} − 4x + 4, x^{2} − 6x + 2; all of which are degenerate. Hence, when q ≡ 3 mod 4, q must be greater than 7 in order for there to exist a nondegenerate conic that is not blocked by B.

This bound, although it is low, is in fact, an improvement over several variations of the bound given by counting intersections of lines with conics in the plane. We give one of these variations now.

Let π be a projective plane of order q. Let S be a set of concurrent lines, at the point O, with the property that all conics in π meet S. Assume |S| = q − λ and λ ≥ 0.

Let x_{i}, 1 ≤ i ≤ q − λ, denote the number of conics of π meeting S in exactly i lines. For these counts, we will not include conics that contain the point O. Then

∑_{i=1}^{q−λ} x_{i} = q^{5} − q^{4}.  (4.10)

Next, we count incidences of a line in S with the conics and then with pairs of lines in S.

• |{(Q, l) | l ∈ S, Q ∩ l ≠ ∅}|

– For a (fixed) line l ∈ S, l has \frac{q^{5}−q^{3}}{2} conics on it and there are q − λ lines in S.

– For a conic Q, Q meets x_{i} lines. There are i ways to pick one of these lines. Summing gives

∑_{i=1}^{q−λ} ix_{i} = (q − λ) [\frac{q^{5} − q^{3}}{2} ].  (4.11)

• |{(l_{1}, l_{2}, Q) | l_{1}, l_{2} ∈ S, l_{1} ≠ l_{2}, Q ∩ l_{1} ≠ ∅, Q ∩ l_{2} ≠ ∅}|

– For a pair of lines in S, there are \frac{q^{5}+q^{3}−2q^{2}}{4} conics that meet both lines of this pair. There are \binom{q−λ}{2} ways of picking two lines of S to meet Q.

– For a given conic Q, it lies on i lines of S. There are \binom{i}{2} ways of picking two lines of S. Summing gives

∑_{i=1}^{q−λ} i(i − 1)x_{i} = (q − λ)(q − λ − 1) [\frac{q^{5} + q^{3} − 2q^{2}}{4} ].  (4.12)

Consider the sum

(λ − q) · (4.10) + (q − λ) · (4.11) − (4.12).

Then we have that

∑_{i=1}^{q−λ}(q − λ − i)(i − 1)x_{i} = (λ − q)(q^{5} − q^{4})\frac{q^{5} + q^{3} − 2q^{2}}{4} + (q − λ)^{2} \frac{q^{5} − q^{3}}{2}
−(q − λ)(q − 1 − λ)\frac{q^{5} + q^{3} − 2q^{2}}{4} .  (4.13)

Since the LHS is non-negative, the RHS must also be non-negative. This implies that

(λ − q) (λ − \frac{q^{2} − q − 2}{q + 2}) ≥ 0.

Hence, λ < q and λ ≤ \frac{q^{2}−q−2}{q+2}. This implies that |S| ≥ q − \frac{q^{2}−q−2}{q+2} = \frac{3q+2}{q+2}. That is, |S| ≥ 3.

This approach gives a lower bound of three on the size of a minimum CBS for all q. By modifying |S|, the overall argument is the same, as well as the result. This same type of counting technique was applied to the dual model, which also gave a bound of three. It is possible that by adding additional constraints to the count, a bound better than three can be obtained.

Since the problem of finding minimum CBSs tends to be naturally related to set covering problems (SCPs), we tried several approaches from an optimization viewpoint. Working with the array A, given in Sections 4.3 and 3.4, containing the set covering information, we explored finding a bound by using a lazy greedy set covering approach. That is, we determined the maximum number of rows covered by the selection of a column and calculated the minimum number of columns necessary to cover all rows. This approach did not yield results any better than those given in the previous counting argument.

During this process of exploring a greedy approach to finding a minimum, we observed that often a greedy covering would give the minimum CBS sizes (as found by Cplex). For combinatorial optimization, a matroid is a problem structure where the greedy algorithm gives an optimal answer [32]. But, NP-hard problems, like the set covering problem, cannot have matroidal structure. So, this approach to finding a lower bound will not produce a result.

The SCP is notoriously hard to solve and is, in fact, NP-complete ([46], [49], [41], [27], [19]). Because the SCP is NP-hard, much research has been devoted to developing good heuristic algorithms that give close approximation to the optimum. In [19], Chvátal found the tight worst case bound of the greedy heuristic commonly considered in the set covering literature. The worst case behavior of the greedy heuristic for the (unweighted) SCP was shown by Johnson [41] and Lovász [49] to be given by the relation

\frac{z_{G}}{z_{F}} ≤ H(d) (< 1 + ln d),  (4.14)

where z_{G} is the value of a greedy cover, z_{F} is the value of a fractional cover, d is the largest column sum of the 0-1 matrix A, and H(d) = ∑_{j=1}^{d} 1/j. Chvátal [19] has shown that the worst case bound given by (4.14) is also valid for the greedy heuristic when applied to the weighted SCP with arbitrary, but positive, cost coefficients. Ho [37] has shown that the bound on the ratio \frac{Z_{h}}{Z_{o}}, where Z_{h} and Z_{o} are the values of the heuristic and optimal solutions respectively, is also H(d) for a more general setting of SCP’s. In terms of the minimum CBS problem, d is the largest number of conics blocked by a line. Since the number of conics blocked by a line is \frac{q^{5}+2q^{4}−q^{3}−2q^{2}}{2} , this ratio gives

|B| > \frac{z_{G}}{1 + ln (\frac{q^{5}+2q^{4}−q^{3}−2q^{2}}{2} )},

where z_{G} is the solution to the problem given by the greedy algorithm. This bound is not practical for us, since it relies on finding a greedy solution before we can calculate the bound.

4.6 Chapter Summary

As in Chapter 3, we have produced CBSs using the trace function and the method used to generate these CBSs can be applied to any additive function in place of the trace function. Since nonlinear Knuth-Kantor flocks exist when the characteristic is odd, the trace-flock construction did not yield CBSs in PG(2, q^{2}). To compensate for the KK-flocks, a CBS for PG(2, q^{2}) was developed from one of the models used to search for minimum CBSs. Table 4.16 illustrates the sizes of the CBSs obtained from the constructions described in this chapter.

q Trivial Trace-Flock Subfield-Trace 0
p (p + 3)/2
p^{2} (p^{2} + 3)/2  2p − 1
p^{3} (p^{3} + 3)/2  p^{2} + 1
p^{4} (p^{4} + 3)/2 p^{3} + 1 2p^{2} − 1
p^{5} (p^{5} + 3)/2  p^{4} + 1
p^{6} (p^{6} + 3)/2 p^{5} + 1, p^{4} + 1  2p^{3} − 1
p^{7} (p^{7} + 3)/2  p^{6} + 1
p^{8} (p^{8} + 3)/2 p^{7} + 1, p^{6} + 1  2p^{4} − 1
p^{9} (p^{9} + 3)/2 p^{8} + 1, p^{6} + 1
p^{10} (p^{10} + 3)/2 p^{9} + 1, p^{8} + 1  2p^{5} − 1

Table 4.16: Construction Sizes

We developed two models to aid in the search for minimum CBSs. One of these models is directly related to the model developed for planes of even order.

Due to computer, software, and time limitations, we were only able to perform a complete search for minimum CBSs for q ≤ 113 and q = 125. Table 4.17 illustrates the orders of the planes and the sizes (m) of the minimum CBSs in those planes.

m = size of minimum CBS in PG(2, q)

\begin{matrix}q & m & q & m & q & m & q & m & q & m & q & m & q & m \\ 3 & 3 & 13 & 6 & 27 & 8 & 43 & 8 & 61 & 9 & 81 & 10 & 103 & 10 \\ 5 & 4 & 17 & 6 & 29 & 8 & 47 & 8 & 67 & 9 & 83 & 10 & 107 & 10 \\ 7 & 4 & 19 & 6 & 31 & 8 & 49 & 9 & 71 & 9 & 89 & 10 & 109 & 10 \\ 9 & 5 & 23 & 7 & 37 & 8 & 53 & 9 & 73 & 9 & 97 & 10 & 113 & 10 \\ 11 & 6 & 25 & 8 & 41 & 8 & 59 & 9 & 79 & 8 & 101 & 10 & 125 & 11 \end{matrix}

Table 4.17: Minimum Values and Bounds on Minimum Values

To obtain small CBSs for q > 113, we used either an ad-hoc method of selecting potential CBSs and checking or we employed a greedy-based algorithm to search for small CBSs. Table 4.18 contains the sizes of the smallest CBSs found by one of these methods.

s = size of the smallest CBS found in PG(2, q)

\begin{matrix}q & s & q & s & q & s & q & s & q & s & q & s \\ 121 & 11 & 137 & 12 & 151 & 12 & 167 & 12 & 179 & 12 & 193 & 12 \\ 127 & 11 & 139 & 11 & 157 & 12 & 169 & 12 & 181 & 12 & 197 & 12 \\ 131 & 11 & 149 & 12 & 163 & 12 & 173 & 12 & 191 & 12 & 199 & 12 \end{matrix}

Table 4.18: Bounds on Minimum Values 5. Conic Blocking Sets and Flocks

All work presented in this chapter as an application of conic blocking sets is found in [18] unless otherwise denoted. 5.1 General Terminology and Background Material

In Section 2.2.3, flocks of quadratic cones were introduced. We begin this section by defining a flock in terms of an arbitrary cone. The definition of flock for the results presented in this chapter is consistent with that given in Section 2.2.3, but we define the cone of the flock in a more general setting.

Let π be a projective plane which is embedded in PG(3, q). Let S be an arbitrary set of points in π and V be a point of PG(3, q) \ π. The cone, denoted C = C(V, S), with vertex V and carrier S is the union of the points on the lines joining V to the points of S. We call π the carrier plane of the cone C, and the lines joining V to S the generator lines of the cone.

Figure 5.1: An Arbitrary Cone

A flock F of a cone C is a set of q planes which do not contain V such that no two planes of F meet at a point of C. The intersections of the planes of the flock with the cone partition the points of the cone except for the vertex V. Given a cone C(V, S) and line l of PG(3, q) which does not intersect C(V, S), the q planes which pass through l and do not contain the point V form a linear flock of C(V, S). Note that both of these definitions are consistent with those given in Section 2.2.3.

Figure 5.2: Linear Flock

There are cones which admit only linear flocks. For example,

Proposition 5.1 [18] A flock of any cone in PG(3, 2) which has a flock, is linear.

Proof: A flock of a cone in PG(3, 2) consists of just two planes. As these two planes must meet in a line which does not intersect the cone, the flock is a linear flock.

Flocks that are not linear are called nonlinear flocks, and the results given in this chapter are concentrated on nonlinear flocks. We introduce coordinates and certain normalizations in order to simplify notation in the following sections.

Let C = C(V, S) be a cone in PG(3, q) with a flock F. We will assume that one of the planes of F, denoted π_{0}, is chosen as the carrier plane of the cone. In other words, S is contained in π_{0}. We can introduce projective coordinates, (x, y, z, w), in PG(3, q) so that V has coordinates (0, 0, 0, 1) and the plane π_{0} has equation W = 0. Furthermore, if the points of S are not all collinear, then we can, without loss of generality, assume that S contains the points A = (1, 0, 0, 0), B = (0, 1, 0, 0), and C = (0, 0, 1, 0). For our purposes, S will always contain at least three points.

To each plane of the flock F, we associate a unique element of the field GF(q), subject only to the restriction that 0 is associated to the plane π_{0}. With this indexing of the planes of F, and since the planes do not pass through V, there exist functions f, g, and h : GF(q) → GF(q), so that the planes π_{t}, with t running through GF(q), have equations:

π_{t} : f(t)X + g(t)Y + h(t)Z + W = 0.

We call these three functions the coordinate functions of the flock. Since π_{0} is the plane with equation W = 0, we have that the coordinate functions must satisfy f(0) = g(0) = h(0) = 0. We will use the notation F = F (f, g, h) to denote the flock F with coordinate functions f, g, and h.

Many of the results in this chapter are centered around arbitrary cones, therefore, it is convenient to classify cones based on their carrier sets. We begin with the trivial cones.

The cone C(V, S) is said to be a flat cone if either it is the empty cone (S = ∅) or the points of S are collinear. C(V, S) is a thin cone if the points of S are contained in some set of fewer than ⌊\frac{q+2}{2}⌋ concurrent lines. So, we see that every flat cone is a thin cone. A non-thin cone is referred to as a wide cone, that is, the points of S are not contained in any set of fewer than ⌊\frac{q+2}{2}⌋ concurrent lines. Finally, a wide cone whose carrier contains at least q + 1 points is a thick cone.

Let S ∈ π_{0} be the carrier of cone with vertex V and F be a flock with cone C(V, S). The lines of π_{0} which are the projections from V of the lines of intersection of pairs of planes of F into π_{0} are called the baselines of F (in π_{0}). We distinguish two types of baselines. Those which are the intersections of π_{0} with the other planes of F are called the primary baselines, while the others are called the secondary baselines.

Figure 5.3: Primary and Secondary Baselines

Given a set F of q planes, if S′ is the complement of the union of the baselines of F, then the cone C(V, S′) is called the critical cone of F. Any subset of S′ is the carrier of a cone that has F as a flock. Proposition 5.2 introduces limitations on possible baseline configurations for a flock.

Proposition 5.2 [18] At the intersection of two distinct primary baselines there is a secondary baseline which cannot coincide with either of these primary baselines.

Proof: Let π_{1} and π_{2} be two planes which intersect the carrier plane π in distinct primary baselines. Let P be the point of intersection of these baselines. Now, the intersection of π_{1} and π_{2} is a line l which does not lie in π_{0} (otherwise the baselines would not be distinct). The projection of l from V into π_{0} is a secondary baseline which passes through P. Suppose, without loss of generality, that this secondary baseline coincided with the primary baseline of π_{1}. The plane containing the primary baseline and l is clearly π_{1}, but because l projects to the baseline, V must also be in this plane. This contradiction shows that the secondary baseline must be distinct from both primary baselines.

5.2 The Dual Setting and Star Flocks

Viewing flocks in the dual setting has been an effective technique in the classical quadratic cone situation. For instance in [22], DeClerk and Herssens used the dual setting to aid in the search used to find and classify flocks of quadratic cones for small values of q . It is also convenient for us to use the dual setting to illustrate the application of conic blocking sets to finding flocks.

Let F be a flock of the cone C(V, S) in PG(3, q). By passing to the dual space, F becomes a set of q points in PG(3, q) and the cone is the set of all planes passing through a set of lines in the plane corresponding to V with the property that no line determined by a pair of the q points lies in any of these planes.

We set up some notation for the dual setting. Let F be a flock of the cone C(V, S) with V = (0, 0, 0, 1) where the planes of F are given by f(t)X + g(t)Y + h(t)Z + W = 0. Using the standard duality, the flock becomes a set of points D_{F} = {(f(t), g(t), h(t), 1) | t ∈ GF(q)}. The vertex V becomes a plane with equation W′ = 0. The points on a generator of the cone C(V, S) become the set of all planes passing through a line in W′ = 0. The set of all lines in the plane W′ = 0, corresponding to generators of C(V, S) will be denoted by D_{G}, and the set of all planes passing through the lines of D_{G} will be denoted by D_{C}. The carrier S becomes the set of planes, denoted by D_{S}, passing through the point (0, 0, 0, 1) which intersect W′ = 0 in a line of D_{G}. The condition that the lines formed by pairs of points of D_{F} do not lie in the planes of D_{C} is equivalent to the condition that these lines do not intersect the lines of D_{G}.

Figure 5.4: Dual Flock Setting

Next we consider how primary and secondary baselines are represented in the dual setting. A primary baseline is the intersection of the plane W = 0 with one of the other planes of the flock, so in the dual setting this is a line joining the point (0, 0, 0, 1) with one of the other points of D_{F}. A secondary baseline is the projection into W = 0 of the line of intersection of two flock planes (which does not lie in W = 0) from the vertex V. Thus, it is the intersection of the plane determined by V and the intersection line, with W = 0. This plane in the dual setting is a point in W′ = 0 which is on a line determined by two points of D_{F} which does not pass through (0, 0, 0, 1), and the secondary baseline is therefore the line joining this point with (0, 0, 0, 1).

Figure 5.5: Dual Baseline Setting

A star flock is a flock of a cone whose planes share a common point and a proper star flock is one for which this common point is unique. Linear flocks are clearly star flocks, but not proper star flocks. If F is a star flock, then the corresponding q points in the dual are coplanar. Moreover, if the points of D_{F} are collinear, then the planes of F must intersect in a common line. So the star flock is linear and therefore is not a proper star flock.

By examining baseline configurations, we can show that

Proposition 5.3 [18] The flocks of all non-flat cones in PG(3, 3) that have flocks are linear.

Proof: There are only two planes other than the carrier plane in a flock of PG(3, 3). Thus, there are only two primary baselines. These may coincide, in which case the flock is linear, or not, in which case their point of intersection is in all three planes and the flock is a proper star flock. Thus, any flock of any cone admitting a flock is a star flock.

Now, suppose that the two primary baselines are distinct (that is, the flock is a proper star flock). By Proposition 5.2 there is a secondary baseline through the point of intersection. These three baselines form the entire baseline configuration. The complement of the union of the baselines thus consists of the points on the remaining line through this point of intersection (not including that point). Thus, the critical cone is flat. So, a non-flat cone in PG(3, 3) cannot admit a proper star flock.

In great detail, we examine the dual of a proper star flock of a non-empty cone. Let F be a star flock of a non-empty cone, we can coordinatize F so that the flock has the form F (t, g(t), 0). Let the vertex of the cone be given by V = (0, 0, 0, 1), and observe that the point R = (0, 0, 1, 0) is in all the planes of F. We build the dual star flock model piece-by-piece.

As mentioned earlier, the dual of the vertex V becomes the plane W′ = 0. The dual of the common point R becomes the plane Z′ = 0. Since R and V are distinct points in the original plane, we have that in the dual, the planes W′ = 0 and Z′ = 0 intersect in a line, m. Observe that any point on m has coordinates (x, y, 0, 0).

Since every plane of the flock F (t, g(t), 0) contains the point R, the dual flock, D_{F} is a set of q points (t, g(t), 0, 1) all contained in the plane Z′ = 0. Note that none of the points of D_{F} lie on the line m, for if a point of D_{F} were on the line m, then this point is in the plane W′ = 0, implying that one of the planes of the flock would contain the vertex, which cannot happen. So, the q dual flock points all lie in the plane Z′ = 0, and none of these points lie on the line m which is the intersection of W′ = 0 and Z′ = 0. Take m as the line at infinity of the plane Z′ = 0 and use affine coordinates in the affine plane obtained by removing m from Z′ = 0. The point in this affine plane with coordinates (x, y) is the point (x, y, 0, 1) of (the plane Z′ = 0 in) PG(3, q). Hence, the q points of D_{F} in this affine plane have coordinates (t, g(t)) for t ∈ GF(q).

The points comprising a generator line g of the flock F become a set of planes, in the dual setting, that intersect in a common line. This line of intersection must lie in the plane W′ = 0, since g contains V. Let D_{G} denote the set of dual generator lines in the plane W′ = 0. We get one D_{G} line for every point in the carrier set, and each of the lines of D_{G} must meet m in a point. We remark that it is possible for two dual generator lines to meet at the same point on m. But, if the carrier set for the flock is a conic, only two lines of D_{G} can meet at the same point on m.

The line joining any two points of D_{F} must meet m in a point, say X. If a line of D_{G} also met m at the point X, we would have two planes of the flock meeting on the cone. So, this situation cannot arise.

Figure 5.6: Dual Proper Star Flock in PG(3, q)

Let M be the set of all “slopes” determined by pairs of the points of D_{F}. That is,

M = \{\frac{g(t) − g(s)}{t − s} | t ≠ s and t, s ∈ GF(q)\}

and let |M| = N. Each slope in M corresponds to a point of m through which passes at least one line of Z′ = 0 containing at least two points of D_{F}. In fact, M is the collection of slopes of the dual baselines in the plane Z′ = 0. Consider the set of free points on the line m. These are the points on m that do not have slope in M. Now, to satisfy the flock condition, no line of D_{G} can pass through a point on m that is also on a line that contains at least two points of D_{F}. Thus, in order for F to be a proper star flock of a wide cone, we must have that N ≤ q + 1 − ⌊(q + 2)/2⌋ = ⌊(q + 1)/2⌋.

The problem of determining the number of slopes determined by q points in an affine plane has been well studied due to a connection with blocking sets (of lines) of Rédei type. Recall from Chapter 2, a blocking set of Rédei type in PG(2, q) is a blocking set of size q + k for which there is some line l ∈ Π for which |l ∩ B| = k. Determining the number of slopes of a set of points with the specified property is almost completely settled. We restate Theorem 2.31 by Ball, Blokhuis, Brouwer, Storme, and Szönyi, using our terminology.

Theorem 5.4 [5] If q = p^{n} for some prime p, let e be the largest integer so that any line of the affine plane containing at least two points of D_{F} contains a multiple of p^{e} points of D_{F}. Then we have one of the following:

(i) e = 0 and (q + 3)/2 ≤ N ≤ q + 1,

(ii) p = 2 and e = 1, and (q + 5)/3 ≤ N ≤ q − 1,

(iii) p^{e} > 2, e | n, and p^{n−e} + 1 ≤ N ≤ (q − 1)/(p^{e} − 1),

(iv) e = n and N = 1. Moreover, if p^{e} > 3 or (p^{e} = 3 and N = q/3 + 1), then g is a p^{e} linearized polynomial.

Definition 5.5 A p^{e}-linearized polynomial is one of the form:

g(t) = ∑_{i=0}^{k−1} α_{i}t^{p^{ie}},

where α_{i} ∈ GF(p^{n}) and n = ke.

All bounds given for N are sharp, in the sense that there are examples with equality, except for the lower bound in case (ii). In case (ii), there is no known example with N < q/2 + 1. It is conjectured that in this case, N = \frac{q}{2} + 1, and this is true for q ≤ 16.

We will discover that if we have a set of q points, not all collinear, in a plane that is embedded in projective 3-space, then after dualizing, this set of q points form a proper star flock of a cone. If q points in a plane produce a set M of size N of slopes, then we are able to determine the size of the free set. The free set consists of the points of m that do not lie on a line of Z′ = 0 that also contains at least two of the q points. These points of m in the free set are free to have dual generator lines through them. These dual generator lines lie in W′ = 0, but meet the plane Z′ = 0 at the line m. The more free points, the more dual generator lines can be created, and so the larger the critical carrier set will be in the original space. With this large critical set, we can construct a cone that has those q points as a dual star flock.

The next theorems and corollary illustrate the consequences of Theorem 5.4 as related to star flocks of cones.

Theorem 5.6 [18] If q = p^{n} with p > 3 a prime, then a proper star flock of any wide cone is given by F (t, g(t), 0) if and only if g is a nonlinear p^{e}-linearized polynomial for some e | n with e < n.

Proof: For a star flock to be a flock of a wide cone, we must have that N ≤ ⌊\frac{q+1}{2}⌋ and so, we may rule out Case (i) in Theorem 5.4. Also, for a star flock to be proper, we must have N > 1 and so, we may rule out Case (iv) in the same theorem. Since p is a prime greater than 3, we may rule out Case (ii). Thus, all except Case (iii) of Theorem 5.4 is eliminated, and we have that g is a p^{e}-linearized polynomial.

Suppose g is a p^{e}-linearized polynomial for some e | n with e < n. Such functions are additive, so to calculate N we need only to calculate the number of distinct values of \frac{g(t)}{t}, for t ≠ 0. Let K = GF(p^{e}) be a proper subfield of GF(p^{n}). For each c ∈ K we have g(ct) = cg(t). Thus, for c ∈ K^{∗}, \frac{g(ct)}{t} = \frac{g(t)}{t} and the number of distinct nonzero values of \frac{g(t)}{t} is at most |GF(p^{n})^{∗}|/|GF(p^{e})^{∗}| = \frac{q−1}{p^{e}−1}. Therefore, N ≤ \frac{q−1}{p^{e}−1} + 1 < \frac{q+1}{2} since p^{e} > 3.

Corollary 5.7 [18] If q is prime, then all star flocks of wide cones are linear.

Proof: The cases of q = 2 (Proposition 5.1) and q = 3 (Proposition 5.3) have already been dealt with. So, we may assume that q > 3 is prime. Since a prime field has no proper subfields, there are no p^{e}-linearized polynomials other than the linear ones, so by Theorem 5.4 there are no proper star flocks.

As a restatement of the open cases in the classification given by Theorem 5.4, we have the following theorem.

Theorem 5.8 [18] If q = p^{n}, with p = 2 or 3, then a proper star flock of a wide cone is given by F (t, g(t), 0) where g is a p^{e}-linearized polynomial for some e | n with e < n, or every line of Z′ = 0 which contains at least two points of the dual flock D_{F} contains a multiple of p, but not a multiple of p^{2} points of D_{F} and, in characteristic 3, N > \frac{q}{3} + 1.

For flocks of quadratic cones, we have two classes of examples which correspond to the extreme values of N. Example 16 illustrates how we can construct the Knuth-Kantor flock described in Section 2.2.3. Example 16. Let E = GF(p^{n}) with a subfield K = GF(p^{e}). The function g(t) = t^{p^{e}} gives N = \frac{q−1}{p^{e}−1} (Lemma 4.4). For p^{e} > 2, we have N ≤ ⌊\frac{q+1}{2}⌋, and so, we can construct a star flock of a wide cone, more specifically, a proper star flock of a quadratic cone. This particular construction leads to the Knuth-Kantor flock that was described in Section 2.2.3.

Example 17 illustrates how we can construct a proper star flock using the relative trace function. Example 17. Let E = GF(p^{n}) with a subfield K = GF(p^{e}). Consider the function g(t) = Tr_{E/K}(t), the relative trace function from E onto K. Similar to the proofs given in Lemmas 4.3 and 3.3, we find that N = p^{n−e} + 1. If p^{e} > 3, then N < ⌊\frac{q+1}{2}⌋, and so, we can construct a proper star flock of a wide (quadratic) cone.

In the case where the wide cone is a quadratic cone, we can restate the theorems of Thas (3.4, 4.7, 4.8) in star flock terminology.

Theorem 5.9 [69] In even characteristic, all star flocks of quadratic cones are linear.

Theorem 5.10 [69] In odd characteristic, a star flock of a quadratic cone is either linear or a Knuth-Kantor flock.

Suppose F is a proper star flock of a cone C(V, S) and the carrier set S′ of the critical cone C(V, S′) contains a conic. Then by Theorems 5.9 and 5.10, F is either linear or Knuth-Kantor. Since F is a proper star flock, F cannot be linear. If N ≠ (q − 1)/(p^{e} − 1), then F is not Knuth-Kantor. Since F is a proper star flock that cannot be linear or Knuth-Kantor, the critical carrier set of F cannot contain a conic. Hence, the baselines of the flock form a conic blocking set in W = 0. In other words, all proper star flocks of cones give conic blocking sets, except for the Knuth-Kantor flock described in Example 16.

These theorems prove that the baselines of a proper star flock of a wide cone, which is not of Knuth-Kantor type, form a conic blocking set. In this setting, since N < ⌊\frac{q+1}{2}⌋, the conic blocking sets which arise have the property that no conic is completely contained in the set of lines.

6. Avenues of Further Research In this thesis we examined constructions for finding conic blocking sets and

we studied bounds on the size of minimum conic blocking sets. In this chapter, we mention open problems and questions that have not been solved. These remain to be studied further.

In planes of odd characteristic every conic is an oval. The concept of an oval blocking set is no different than that of a conic blocking set. In planes of even characteristic, these two concepts do not coincide as there are examples of ovals that are not conics. A computer search by W. Cherowitzo has shown that the conic blocking set, {y = t^{3}x + z | t ≠ 0}, does not block the Subiaco ovals [17]. Similar to the work presented in this dissertation, there is research to be done with oval blocking sets.

All of the material on CBSs given here is centered around CBSs consisting of concurrent lines. A natural direction to pursue is to examine conic blocking sets of nonconcurrent lines. S. Ball, A. Blokhuis, and M. Lavrauw [6] have preliminary results about semifield flocks that can be used to find conic blocking sets of nonconcurrent lines for planes of odd order.

We were able to use the structure of the image set of an additive function to obtain many of the CBSs presented in this dissertation. Since planes of prime order lack interesting additive functions, no CBS constructions were found for these planes. Finding CBS constructions for planes of prime order remains an open problem.

For q odd, preliminary computer computations show that there are several construction ideas worth further examination. For q = p^{2}, the set of lines through the point (0, 0, 1) with absolute trace 1 or absolute trace 0 slope seem to form a conic blocking set of size 2p in PG(2, p^{2}). Also, there is preliminary work showing that we can add relatively few lines to the set of lines that correspond to the KK-lines and form a CBS in PG(2, p^{h}), h even and p odd.

In Section 4.4, we exhibited a CBS construction for PG(2, q^{2}) using points with parameters in GF(q) and with parameters with relative trace 0. This CBS should be examined to determine if it is irreducible.

There is work to be done with oval blocking sets in non-Desarguesian projective planes.

The minimum sizes of CBSs in planes of odd order exhibited a mostly monotonic behavior as the size of the plane increased. There are two examples where this behavior was not monotonic; q = 79 and q = 137 or 139. There is further work to be done in explaining the dip in sizes at these values of q.

For q even, computer computations show that in PG(2, 2^{h}), h an odd prime, the set of lines with slope in a nontrivial cyclotomic coset along with the three lines x = 0, y = 0, and y = x through the point (0, 0, 1) form a CBS of size h + 3.

There is more work to be done in strengthening the lower bounds on the sizes of minimum CBSs.

A. CBS Parameters for q Even

This appendix contains the parameters for the minimum conic blocking sets and the smallest conic blocking sets found in PG(2, q), q even. We indicate the minimum CBS found with an M and the smallest CBS found with an S in the size column. The Method column denotes which method was used to find the CBS. An ST denotes the model developed in Section 3.4 was used, an SBH denotes that the modified greedy algorithm (surrogate-based heuristic) developed by Gary Kochenberger [47] was used, and finally an AH denotes that an ad-hoc method of searching for CBSs was used. The fourth column contains the primitive polynomial used to generate GF(q). The last column contains the parameters for the points (in the dual setting) that form a CBS.

q Size Method Primitive Polynomials Parameters
2^{2} M  ST  x^{2} = x + 1  0, 1, ∞
2^{3} M  ST  x^{3} = x^{2} + 1  0, 1, ∞, α, α^{2}
2^{4} M  ST  x^{4} = x + 1  0, 1, ∞, α^{5}, α^{10}
2^{5} M  ST  x^{5} = x^{2} + 1  0, 1, ∞, α^{6}, α^{8}, α^{23}, α^{24}, α^{25}
2^{6} M  ST  x^{6} = x + 1  0, 1, ∞, α, α^{5}, α^{6}, α^{37},
α^{44}, α^{62}
2^{7} M ST x^{7} = x + 1 0, 1, ∞, α, α^{2}, α^{29}, α^{49},
α^{80}, α^{100}

Table A.1: CBSs in Planes of Even Order

q Size Method Primitive Polynomials Parameters
2^{8} S SBH x^{8} = x^{5} + x^{4} 0, 1, ∞, α, α^{2}, α^{3}, α^{6}, α^{17},
+ x^{3} + 1  α^{52}, α^{54}, α^{60}, α^{119}, α^{168}
2^{9} S SBH x^{9} = x^{4} + 1 0, 1, ∞, α, α^{2}, α^{3}, α^{4}, α^{25},

α^{59}, α^{80}, α^{147}, α^{269}, α^{283}, α^{385}, α^{433}

AH  0, 1, ∞, α^{1}, α^{2}, α^{4}, α^{8}, α^{16},
2^{10} S & x^{10} = x^{3} + 1 α^{32}, α^{64}, α^{128}, α^{256}, α^{512}, α^{93},
ST  α^{186}, α^{279}, α^{372}, α^{465}, α^{558},

α^{651}, α^{744}, α^{837}, α^{930}

Table A.1: (Cont.)

B. CBS Parameters for q Odd

This appendix contains the parameters for the minimum conic blocking sets in PG(2, q), q odd. Although there were two models developed for finding minimum CBSs, we used the restricted-dual model (RD) for our searches. The modified greedy algorithm (surrogate-based heuristic) developed by Gary Kochenberger [47] is denoted SBH. Tables B.1 and B.2 contains the parameter sets of minimum conic blocking sets in planes of prime and nonprime order, respectively. Tables B.3 and B.4 contains the parameter sets for the smallest conic blocking set found, but not verified as a CBS of minimum size, in planes of prime and nonprime order.

Order Model Parameters
3  RD 0, 1, ∞
5  RD 0, 1, ∞, 3
7  RD 0, 1, ∞, 5
11  RD 0, 1, ∞, 5, 7, 9
13  RD 0, 1, ∞, 5, 6, 10
17  RD 0, 1, ∞, 4, 6, 14
19  RD 0, 1, ∞, 4, 8, 13
23  RD 0, 1, ∞, 12, 13, 15, 17
29  RD 0, 1, ∞, 3, 8, 19, 23, 26
31  RD 0, 1, ∞, 4, 5, 11, 13, 26
37  RD 0, 1, ∞, 13, 23, 24, 25, 29
41  RD 0, 1, ∞, 4, 10, 21, 32, 37
43  RD 0, 1, ∞, 8, 18, 23, 27, 41
47  RD 0, 1, ∞, 2, 4, 6, 34, 43
53  RD 0, 1, ∞, 13, 31, 37, 44, 47, 52

Table B.1: Minimum CBSs in Planes of Prime Order

Order Model Parameters
59  RD 0, 1, ∞, 12, 40, 41, 43, 48, 57
61  RD 0, 1, ∞, 7, 9, 14, 21, 45, 60
67  RD 0, 1, ∞, 17, 34, 35, 45, 50, 53
71  RD 0, 1, ∞, 10, 23, 24, 30, 64, 69
73  RD 0, 1, ∞, 9, 12, 25, 36, 51, 60
79  RD 0, 1, ∞, 12, 24, 40, 52, 61
83  RD 0, 1, ∞, 15, 21, 24, 28, 42, 53, 73
89  RD 0, 1, ∞, 9, 22, 30, 31, 45, 73, 85
97  RD 0, 1, ∞, 27, 44, 47, 49, 65, 70, 93
101  RD 0, 1, ∞, 20, 32, 34, 51, 76, 85, 90
103  RD 0, 1, ∞, 5, 39, 52, 62, 65, 69, 91
107  RD 0, 1, ∞, 17, 31, 32, 54, 58, 62, 93
109  RD 0, 1, ∞, 9, 15, 19, 39, 55, 73, 85
113  RD 0, 1, ∞, 11, 13, 31, 38, 54, 57, 65, 84

Table B.1: (Cont.)

Order Model Primitive Polynomials Parameters
9  RD  x^{2} = x + 1  0, 1, ∞, α^{2}, α^{3}
25  RD  x^{2} = x + 3  0, 1, ∞, α, α^{2}, α^{10}, α^{16}, α^{17}
27  RD  x^{3} = x + 2  0, 1, ∞, α^{2}, α^{3}, α^{9}, α^{21}, α^{25}
49  RD  x^{2} = x + 4  0, 1, ∞, α, α^{6}, α^{25}, α^{30}, α^{34}, α^{42}
81  RD  x^{4} = x + 1  0, 1, ∞, α^{3}, α^{9}, α^{14}, α^{33}, α^{38},
α^{64}, α^{68}
125 RD x^{3} = x + 2 0, 1, ∞, α^{8}, α^{11}, α^{25}, α^{33}, α^{52},
α^{121}, α^{122}, α^{123}

Table B.2: Minimum CBSs in Planes of Nonprime Order

Order Model Parameters
127 SBH 0, 1, ∞, 2, 3, 7, 24, 53, 65, 115, 118
131 SBH 0, 1, ∞, 2, 18, 50, 78, 88, 111, 127, 128
137 SBH 0, 1, ∞, 2, 3, 4, 8, 35, 90, 103, 130, 132
139 SBH 0, 1, ∞, 10, 12, 35, 41, 42, 44, 62, 79
149 SBH 0, 1, ∞, 2, 5, 9, 18, 45, 49, 70, 106, 109
151 SBH 0, 1, ∞, 3, 5, 11, 13, 15, 31, 33, 49, 79
157 SBH 0, 1, ∞, 2, 7, 10, 15, 16, 24, 89, 93, 102
163 SBH 0, 1, ∞, 2, 8, 22, 25, 29, 34, 53, 63, 103
167 SBH 0, 1, ∞, 5, 6, 14, 20, 36, 37, 114, 118, 159
173 SBH 0, 1, ∞, 2, 11, 13, 14, 15, 45, 72, 81, 94
179 SBH 0, 1, ∞, 2, 10, 32, 36, 53, 74, 113, 141, 167
181 SBH 0, 1, ∞, 2, 9, 11, 39, 69, 114, 129, 132, 150
191 SBH 0, 1, ∞, 5, 7, 15, 32, 33, 43, 49, 83, 117
193 SBH 0, 1, ∞, 5, 11, 12, 49, 68, 72, 79, 106, 118
197 SBH 0, 1, ∞, 2, 6, 14, 55, 57, 62, 110, 116, 193
199 SBH 0, 1, ∞, 3, 13, 17, 71, 139, 147, 157, 164, 173

Table B.3: Smallest Known CBSs for q an Odd Prime

Order Model Primitive Polynomials Parameters
121 RD x^{2} = 10x + 4 0, 1, ∞, α^{9}, α^{21}, α^{30}, α^{38}, α^{78},
α^{113}, α^{118}, α^{119}
169 RD x^{2} = 12x + 11 0, 1, ∞, α^{18}, α^{32}, α^{47}, α^{59}, α^{61},
α^{67}, α^{124}, α^{163}, α^{167}

Table B.4: Smallest Known CBSs for q an Odd Nonprime C. The Branch and Bound Algorithm

As shown in Chapters 3 and 4, the problem of finding minimum conic blocking sets is directly related to the set covering problem. In this appendix, we introduce the set covering problem (SCP) as an optimization problem and briefly discuss several aspects of the solvers used.

Let S be a set of objects which are numbered {1, 2, …, m} and F be a collection of subsets of S. Furthermore, assume that each of the elements of S has a cost associated with it. The SCP is to ‘cover’ all members of F at minimum cost using elements of S. That is, to find a subset P of S such that P ∩ C_{i} ≠ ∅ for all C_{i} ∈ F at a minimum cost.

For example, suppose S = {1, 2, 3, 4} and F = {C_{1} = {1, 2}, C_{2} = {2, 3}, C_{3} = {1, 4}}. One cover for S would be P_{1} = {1, 3}, since P_{1} ∩C_{1} = {1}, P_{1} ∩C_{2} = {3}, and P_{1} ∩ C_{3} = {1}. Another cover would be P_{2} = {1, 2, 4}, as P_{2} ∩ C_{1} = {1}, P_{2} ∩ C_{2} = {2}, and P_{2} ∩ C_{3} = {1, 4}. Suppose that the element 1 has a cost of 10, the elements 2 and 3 both have a cost of 2, and the element 4 has a cost of 1. Then the cost of the covering P_{1} is 12 and the cost of the covering P_{2} is 13. A minimum cover for this problem is P = {2, 4}, which has an associated cost of 3.

One method for finding a minimum cover is to build a 0-1 pure integer programming (PIP) model. Constraints are introduced to ensure that each member (set) of F is covered. If the objective is to minimize the cost of a cover of F, the resultant model is,

Minimize 10x_{1} + 2x_{2} + 2x_{3} + 1x_{4}
subject to x_{1} + x_{2} ≥ 1,
x_{2} + x_{3}  ≥ 1,
x_{1}  + x_{4} ≥ 1,

or

min c^{T} x
subject to  Ax ≥ b
x ∈ {0, 1},

where

A = [\begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{matrix}], b = [\begin{matrix}1 \\ 1 \\ 1 \end{matrix}], and c^{T} = [10 2 2 1].

There are many applications for the SCP other than searching for minimum CBSs. A comprehensive list of applications is found in [3] by Balas and Padberg. There are also many algorithms that exist for integer problems. Two standard algorithms are the branch and bound algorithm and the cutting-plane algorithm, which are described in Chapter 4 of Garfinkle and Nemhauser [28]. We provide a brief explanation of the branch and bound algorithm shortly. The difficulty of solving set covering problems usually arises not from their structure, but from their size. This fact became more apparent to us as the order of the projective plane increased.

SCP’s are comparatively easy to solve with the branch and bound algorithm, and this algorithm guarantees an optimal solution. So, for our problems, we are guaranteed that the conic blocking set found by the branch and bound algorithm is indeed a minimum conic blocking set.

The branch and bound (B&B) algorithm is an optimization technique that enumerates a tree to find an optimal solution. By calculating upper and lower bounds on the objective function, the B&B algorithm accelerates the fathoming process and thereby shortens the enumeration. A node is fathomed if it is determined that no completion from this point could produce a better solution than one already obtained. This could happen by bounding the objective, or it can happen by determining there is no feasible solution with the partial specifications corresponding to the node.

Commercial solvers invoke a heuristic before starting the fathoming process to obtain an initial “good” solution. Thus, the process begins with a feasible solution, but there is no guarantee of optimality. Enumerative algorithms invariably benefit from starting with a good feasible solution. And so, by beginning the tree search with a feasible solution, a lower bound on the optimal objective function is provided. This bound is used for fathoming in the algorithm, resulting in a pruning of the enumeration tree.

The following typical integer linear program (ILP)

min c^{T} x
subject to  Ax ≥ b
x ∈ {0, 1}

has the corresponding LP relaxation (RLP)

min c^{T} x
subject to  Ax ≥ b
0 ≤ x ≤ 1,

where c^{T} x is the objective function, the components of c are the cost coefficients, A is called the coefficient matrix, b is the right-hand side, and x is a vector of decision variables. Notice that in the LP relaxation there are no more integrality constraints, but rather the decision variables are restricted to the interval [0, 1].

To explain the B&B process, we focus on the set covering problem given earlier. Since the decision variable is binary, we use the tree given in Figure C.1 to help illustrate the algorithm.

Figure C.1: A Tree

Suppose the heuristic algorithm obtains the feasible solution z_{0} = c^{T} x = 14 at vertex (1, 1, 1, 0). The B&B algorithm begins the process of fathoming (investigating) the enumeration tree. If the algorithm tested vertex (1, 1, 1, 1), it would find that the cost c^{T} x = 15 > z_{0}, so this vertex is pruned. Continuing with its branching process, the algorithm examines the RLP at the vertex (1, 1, 0, d_{4}). The RLP is given by

min 12 + d_{4}
s.t. 2 + d_{4} ≥ 1
1 + d_{4} ≥ 1
0 ≤ d_{4} ≤ 1.

The optimal solution to this relaxation is 12 < 14, so further exploration below vertex (1, 1, 0, d_{4}) is warranted. At vertex (1, 1, 0, 0), we obtain an update for the objective value since z_{1} = c^{T} x = 12. The vertex (1, 1, 0, 1) yields a feasible solution of 13, but is no longer a candidate for an optimal solution, since we have a feasible solution with an objective value of z_{1} = 12.

Having completed a search from vertex (1, 1, d_{3}, d_{4}), the algorithm now considers the RLP at vertex (1, 0, d_{3}, d_{4}).

min 10 + 2d_{3} + d_{4}
s.t. 1 + d_{3} ≥ 1
1 + d_{4} ≥ 1
0 ≤ d_{i} ≤ 1, i = 3, 4.

In this RLP, the optimal solution is 10 < 12 = z_{1}, so no decision can be made at this vertex. The RLP is examined at vertex (1, 0, 0, d_{4}) and we discover that no feasible solution can be obtained, since one of the constraints becomes 0 ≥ 1. Hence, the branch from vertex (1, 0, 0, d_{4}) is pruned. No decision by the RLP is made at vertex (1, 0, 1, d_{4}), so we explore further down the branch. Vertex (1, 0, 1, 0) yields an alternative optimal solution of 12. Since vertex (1, 0, 1, 1) does not yield a better optimal solution, this vertex is pruned.

At this point, the algorithm has (nearly) exhaustively searched the branch beginning with vertex (1, d_{2}, d_{3}, d_{4}) and examines the branch beginning with (0, d_{2}, d_{3}, d_{4}). Notice that there is no feasible solution to the RLP at vertex (0, 0, d_{3}, d_{4}), and the tree may be pruned at this vertex. Solving the RLP at the vertex (0, 1, d_{3}, d_{4}),

min 2 + 2d_{3} + d_{4}
s.t. 1 + d_{3} + d_{4} ≥ 1
d_{4} ≥ 1
0 ≤ d_{i} ≤ 1, i = 3, 4,

gives a minimum value of 3, and further exploration is warranted. Exploring the rest of the tree, from vertex (0, 1, 0, d_{4}), using this LP relaxation leads to the new optimal solution z_{2} = c^{T} x = 3 at vertex (0, 1, 0, 1). At vertex (0, 1, 1, d_{4}), the cost value is at least 4 > 3 = z_{2}, so this vertex is pruned. Hence, when the B&B algorithm terminates, we have an optimal solution of 3 given by x = [0, 1, 0, 1,]^{T}.

Observe that if the heuristic had found an initial feasible solution in the tree that branches from vertex (0, d_{2}, d_{3}, d_{4}), then after branching through this tree we would have obtained the optimal solution. Then, the entire subtree that branches from vertex (1, d_{2}, d_{3}, d_{4}) would have been pruned since any feasible solution will have a cost of at least 10, which is greater than any cost given from the other tree. This observation illustrates the benefits of using a good heuristic to find an initial feasible solution.

This simple example illustrates how the B&B algorithm essentially performs an intelligent exhaustive search that guarantees optimality. For a formal proof that the algorithm finds an optimal solution see [28] or [52].

For the problem of finding minimum conic blocking sets, we chose to use the General Algebraic Modeling System (GAMS) which is a modeling system for mathematical programming problems [20]. GAMS lets the user concentrate on modeling. GAMS eliminates the need of the user to think about purely technical machine-specific problems, and instead allows the user to focus on conceptualizing and running the model, and then analyzing the results. After GAMS builds the model from a simple language, it then sends the model to a solver. We chose the solver Cplex [39], which touts itself as being the “World’s Leading Mathematical Programming Optimizers”. Cplex is a good solver and is used to solve a wide range of models in the corporate community. To illustrate the simplicity of using this modeler and solver to find a solution to the set covering problem, we give a sample of the code used to model this problem.

[h]
sets i/1*4/;
sets k/1*3/;
table a(k,i)
      1 2 3 4
    1 1 1 0 0
    2 0 1 1 0
    3 1 0 0 1
;
binary variable x(i);
variable z;
parameter c(i);
      /1 10
        2 2
        3 2
        4 1 /;
equations obj, cover(k);
obj .. z =e= sum(i,c(i)*x(i));
cover(k)..sum(i,a(k,i)*x(i)) =g= 1;
model Sample /all/;
solve Sample using mip minimizing z;

The code for the conic blocking set problem is similar to this set covering

code. In the CBS problem, all cost coefficients of the objective function are 1 and

so in the GAMS code for the CBS problem, there is no parameter c(i).

References

[1] A. Albert and R. Sandler. An Introduction to Finite Projective Planes. Holt, Rinehart, and Winston, Inc., 1968.

[2] E. F. Assmus and T. D. Key. Designs and their Codes, volume 103 of Cambridge Tracts in Math. Cambridge University Press, 1992.

[3] E. Balas and W. Padberg. On the set covering problem II. Ops Res., 23:74 – 90, 1975.

[4] E. Balas and W. Padberg. Set Partitioning: A Survey. SIAM Review, 18:710 – 760, 1976.

[5] S. Ball, A. Blokhuis, A. Brouwer, L. Storme, and T. Szőnyi. On the number of slopes of the graph of a function defined on a finite field. J. C. T., 86(A):187 – 196, 1999.

[6] S. Ball, A. Blokhuis, and M Lavrauw. Private communications, 2000.

[7] Elwyn R. Berlekamp. Algebraic Coding Theory. McGraw-Hill Inc., 1968.

[8] Albrecht Beutelspacher and Ute Rosenbaum. Projective Geometry. Cambridge University Press, 1998.

[9] Norman Biggs. Permutation Groups and Combinatorial Structures. Cambridge Univeristy Press, 1979.

[10] A. Blokhuis. Polynomials in finite geometries and combinatorics. In Surveys in Combinatorics, volume 187 of London Math. Soc. Lecture Note Series, pages 35 – 52, Cambridge, 1993. Cambridge University Press.

[11] A. Blokhuis, A. E. Brouwer, and T. Szőnyi. The Number of Directions Determined by a Function f on a Finite Field. Jounral of Combinatorial Theory, 70:349 – 353, 1995.

[12] Ernest F. Brickell. Some Ideal Secret Sharing Schemes. In J.J. Quizquater and J. Vandewalle, editors, Lecture Notes in Computer Science, Advances in Cryptology- EUROCRYPTO ’89, volume 434, pages 468–490. Springer-Verlag, April 1989.

[13] R. H. Bruck and H. J. Ryser. The non-existence of certain finite projective planes. Canadian Journal of Mathematics, 1:88 – 93, 1949.

[14] A. A. Bruen. Blocking sets in finite projective planes. SIAM J. Appl. Math., 21:380 – 392, 1971.

[15] A. A. Bruen and J. A. Thas. Partial spreads, packings and hermitian manifolds in PG(3,q). Math Z., 151:207 – 214, 1976.

[16] P. J. Cameron and J. H. Van Lint. Designs, Graphs, Codes, and their Links. Cambridge University Press, 1991.

[17] W. Cherowitzo, T. Penttila, I. Pinneri, and G. F. Royle. Flocks and Ovals. Geometriae Dedicata, 60:17 – 37, 1996.

[18] W. E. Cherowitzo. Flocks of Cones. World Wide Web, http://www-math.

    cudenver.edu/~wcherowi/research/flocks.html, 1998 - 2001.

[19] V. Chvátal. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 4:233 – 235, 1979.

[20] GAMS Development Corporation. Gams. World Wide Web, http://www. gams.com, 1987 - 1999.

[21] H. S. M. Coxeter. Projective Geometry. Blaisdell Publishing Company, 1964.

[22] F. DeClerck and C. Herssens. Flocks of the quadratic cone in PG(3,q), for q small, volume 8, pages 1 – 75. Ghent University, 1993.

[23] Peter Dembowski. Finite Geometries. Springer-Verlag, 1968.

[24] Leonard Eugene Dickson. Linear Groups with an Exposition of the Galois Field Theory. Dover Publications Inc., 1958.

[25] Jane W. DiPaola. On Minimum Blocking Coalitions in Small Projective Plane Games. SIAM J. Appl. Math., 17(2):378 – 392, March 1969.

[26] Joseph A. Gallian. Contemporary Abstract Algebra. Houghton Mifflin Company, 1998.

[27] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, NY, 1979.

[28] R. Garfinkle and G. Nemhauser. Integer Programming. John Wiley & Sons, 1972.

[29] H. Gevaert and N. L. Johnson. Flocks of quadratic cones, generalized quadrangles and translation planes. Geom. Ded., 27:301 – 317, Dec. 1988.

[30] E. N. Gilbert, F. J. MacWilliams, and N. J. A. Sloane. Codes which detect deception. Bell System Tech. J., 53:405 – 425, 1974.

[31] H. Greenberg. Mathematical Programming Glossary. World Wide

Web, http://www-math.cudenver.edu/~hgreenbe/glossary/glossary.

html, 1996 - 1998.

[32] H. Greenberg. Mixed Integer Programming and Combinatorial Optimization.

World Wide Web, http://www-math.cudenver.edu/~hgreenbe/courses/
mip/7594_S01.html, 2001.

[33] R. W. Hamming. Error detecting and error correcting codes. Bell System Tech. J., 29:147 – 160, 1950.

[34] J. W. P. Hirschfeld. Finite Projective Spaces of Three Dimensions. Oxford University Press, 1985.

[35] J. W. P. Hirschfeld. Projective Geometries over Finite Fields. Oxford University Press, 1998.

[36] J. W. P. Hirschfeld and J. A. Thas. General Galois Geometries. Oxford University Press, 1991.

[37] A. Ho. Worst Case Analysis of a Class of Set Covering Heuristics. Math. Programming, 23:170 – 181, 1982.

[38] L. D. Holder. The Construction of Geometric Threshold Schemes with Projective Geometry. Master’s thesis, Univeristy of Colorado at Denver, 1997.

[39] ILOG. Cplex. World Wide Web, http://www.ilog.com/products/cplex/,

2000.

[40] J. R. Isbell. A Class of Simple Games. Duke Mathematical Journal, 25:425 – 436, 1958.

[41] D. S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, 9:256 – 278, 1974.

[42] N. L. Johnson. Semifield flocks of quadratic cones. Simon Steven, 61:313 – 326, 1987.

[43] Lars Kadison and Matthias T. Kromann. Projective Geometry and Modern Algebra. Birkäuser, 1996.

[44] W. M. Kantor. Some generalized quadrangles with parameters (q^{2}, q). Math. Z., 192:45 – 50, 1986.

[45] Irving Kaplansky. Linear Algebra and Geometry. Chelsea Publishing Company, 1974.

[46] R. M. Karp. Reducibility among Combinatorial Problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85 – 103. Plenum Press, New York, NY, 1972.

[47] Gary Kochenberger. Private communications, 2001.

[48] Rudolf Lidl and Harald Niederreiter. Finite Fields. Cambridge University Press, 1997.

[49] L. Lovász. On the Ratio of Optimal Integral and Fractional Covers. Discrete Mathematics, 13:383 – 390, 1975.

[50] L. Lovász and A. Schrijver. Remarks on a Theorem of Rédei. Studia Scientiarum mathematicarum Hungarica, 16:449 – 454, 1981.

[51] James A. Murtha and Earl R. Willard. Linear Algebra and Geometry. Holt, Rinehart, and Winston Inc., 1969.

[52] G. Nemhauser and L. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, 1988.

[53] Ben Noble and James W. Daniel. Applied Linear Algebra. Prentice-Hall, 1988.

[54] S. E. Payne. Quadratic Forms, BLT-Sets and q-Clans. 1998.

[55] S. E. Payne. Private communications, 2000.

[56] E. C. Posner. Combinatorial Structures in Planetary Reconnaissance. In H. B. Mann, editor, Error Correcting Codes. Wiley, New York, 1968.

[57] L. Rédei. Lacunary polynomials over finite fields. American Elsevier Publishing Co., Inc., New York, N.Y., 1973.

[58] Moses Richardson. On Finite Projective Games. Proceedings Amer. Math. Society, 7:458 – 465, June 1956.

[59] Pierre Samuel. Projective Geometry. Springer-Verlag, 1988.

[60] B. Segre. Sulle ovali nei piani lineari finite. Rend. Accad. Naz. Lincei, 17:141 – 142, 1954.

[61] B. Segre. Ovals in a finite projective plane. Canad. J. Math., 7:414 – 416, 1955.

[62] B. Segre and U. Bartocci. Ovali ed altre curve nei piani di galois di caratteristica due. Acta Arith., 8:423 – 449, 1971.

[63] A. Shamir. How to share a secret. Commun. ACM, 22:612 – 613, 1979.

[64] C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379 – 423, 623 – 656, 1948.

[65] G. J. Simmons. A game theoretical model of digital message authentication. Congressus Numerantium, 34:413 – 424, 1982.

[66] G. J. Simmons. An introduction to shared secret/shared control schemes. In G. J. Simmons, editor, Contemproary Cryptology, pages 441 – 497. IEEE Press, New York, 1992.

[67] Gustavus Simmons. Sharply Focused Sets of Lines on a Conic in PG(2,q). In Congressus Numerantium, volume 73, pages 181–204, January 1990.

[68] D. R. Stinson. Cryptography, Theory and Practice. CRC Press, 1995.

[69] J. A. Thas. Generalized Quadrangles and Flocks of Cones. Europ. J. Combinatorics, 8:441 – 452, 1987.

[70] J. A. Thas. Generalized quadrangles of order (s, s^{2}). J. Comb. Theory (A), 79:223 – 254, 1997.

[71] J. H. Van Lint. Coding, decoding, and combinatorics. In R. J. Wilson, editor, Applications of Combinatorics. Shiva, 1982.

[72] W. D. Wallis. Combinatorial Designs. Marcel Dekker, Inc., 1988.

[73] H. P. Williams. Model Solving in Mathematical Programming. Wiley, Chichester, 1993.