Preliminaries: Planes, Duality, Arcs, and Kakeya Sets

2.1 The planes

$PG(2,q)$ has $q^2+q+1$ points and as many lines; every line has $q+1$ points, every point is on $q+1$ lines, two points lie on exactly one line, and two lines meet in exactly one point. Removing the line $\ell_\infty=[0:0:1]$ and its points leaves $AG(2,q)$: $q^2$ points $(x,y)=(x:y:1)$, and $q^2+q$ lines, each with $q$ points, falling into $q+1$ parallel classes of $q$ lines, one class for each point of $\ell_\infty$. The line $[u:v:w]$ with $(u,v)\ne(0,0)$ meets $\ell_\infty$ in the point $(v:-u:0)$, its direction. Concretely, the lines of direction $(1:s:0)$ are $y=sx+b$, $b\in\mathbb F_q$, and the lines of direction $(0:1:0)$ are $x=b$.

Two affine lines in different directions meet in exactly one affine point; two lines in the same direction are disjoint. These two facts, and the count of $q$ points per line, are all that Chapter 3 uses.

2.2 Duality

Lemma 2.1 (The standard correlation). The map $\delta$ that sends the point $(a:b:c)$ to the line $[a:b:c]$ and the line $[u:v:w]$ to the point $(u:v:w)$ is a bijection of the points of $PG(2,q)$ onto its lines and of its lines onto its points, and it reverses incidence: $P\in L$ if and only if $\delta(L)\in\delta(P)$.

Proof. The point $(a:b:c)$ lies on $[u:v:w]$ iff $au+bv+cw=0$, a condition symmetric in the two triples. ∎

Fix $O=(0:0:1)=\delta(\ell_\infty)$. Under $\delta$:

• the $q+1$ directions (points of $\ell_\infty$) become the $q+1$ lines through $O$;
• the $q$ affine lines of a direction $d$ become the $q$ points of the line $\delta(d)$ other than $O$;
• the $q^2$ affine points become the $q^2$ lines not through $O$;
• an affine point $P$ lies on an affine line $L$ iff the point $\delta(L)$ lies on the line $\delta(P)$.

Consequently an $r$-fold configuration $\mathcal L$ corresponds to a set $S=\delta(\mathcal L)$ of $r(q+1)$ points with $O\notin S$ and exactly $r$ points of $S$ on every line through $O$, and conversely. The multiplicity $m_P$ of an affine point is $|\delta(P)\cap S|$, and the union $U(\mathcal L)$ corresponds to the set of lines not through $O$ that meet $S$:

$$|U(\mathcal L)|=\#\{\text{lines }L\not\ni O:\ L\cap S\ne\emptyset\}.\tag{2.1}$$

I shall move freely between the two pictures, calling $\mathcal L$ and $S$ dual to each other.

2.3 Arcs and maximal arcs

Definition 2.2. A nonempty set $M$ of points of $PG(2,q)$ is a maximal arc of degree $n$ if every line meets $M$ in $0$ or $n$ points.

The whole plane is a maximal arc of degree $q+1$; a single point, of degree $1$; the affine plane $AG(2,q)$ (the complement of a line), of degree $q$. These are the trivial maximal arcs. A maximal arc of degree $2$ is a set of $q+2$ points no three collinear, a hyperoval, and these exist iff $q$ is even (a conic together with its nucleus). The name comes from Barlotti (1955), who showed that a set of $k$ points meeting every line in at most $n$ points has $k\le(n-1)q+n$, with equality iff every line meets it in $0$ or $n$ points.

Lemma 2.3. Let $M$ be a maximal arc of degree $n\le q$ in $PG(2,q)$. Then $|M|=(n-1)q+n$, and if $n>1$ then $n\mid q$.

Proof. Take $P\in M$. The $q+1$ lines through $P$ each contain $n-1$ further points of $M$ and together cover $M\setminus\{P\}$, so $|M|=1+(q+1)(n-1)=(n-1)q+n$. Since $n\le q$, $M$ is not the whole plane; take $R\notin M$. The lines through $R$ that meet $M$ partition $M$ into sets of size $n$, so $n\mid(n-1)q+n$, i.e. $n\mid(n-1)q$, and since $\gcd(n,n-1)=1$, $n\mid q$. ∎

For $q$ even the divisibility condition is sufficient.

Theorem 2.4 (Denniston 1969). Let $q=2^h$ and let $n$ divide $q$. Then $PG(2,q)$ contains a maximal arc of degree $n$.

The proof uses three facts about $\mathbb F_q$, $q=2^h$, which I recall. The absolute trace $\operatorname{Tr}:\mathbb F_q\to\mathbb F_2$, $\operatorname{Tr}(a)=a+a^2+\dots+a^{2^{h-1}}$, is $\mathbb F_2$-linear, surjective, and satisfies $\operatorname{Tr}(a^2)=\operatorname{Tr}(a)$; its kernel $T_0$ is an additive subgroup of index $2$. Squaring is a bijection of $\mathbb F_q$. And for $\beta\in\mathbb F_q$ the polynomial $t^2+t+\beta$ is irreducible over $\mathbb F_q$ iff $\operatorname{Tr}(\beta)=1$ (Lidl and Niederreiter 1997, Thm 2.25 and Cor. 3.79; Hirschfeld 1998, §1.4).

Proof. Fix $\beta$ with $\operatorname{Tr}(\beta)=1$ and put $Q(x,y)=x^2+xy+\beta y^2$. Then $Q(x,y)=0$ only for $(x,y)=(0,0)$: if $y\ne0$ then $(x/y)^2+(x/y)+\beta=0$ contradicts irreducibility, and if $y=0$ then $x^2=0$. Let $\omega$ be a root of $t^2+t+\beta$ in $\mathbb F_{q^2}$; then $\omega+\omega^q=1$ and $\omega\omega^q=\beta$, so $Q(x,y)=(x+y\omega)(x+y\omega^q)=N(x+y\omega)$ is the norm from $\mathbb F_{q^2}$ to $\mathbb F_q$. The norm is a surjective homomorphism $\mathbb F_{q^2}^\times\to\mathbb F_q^\times$ with kernel of order $q+1$, so for each $\lambda\ne0$ the conic $C_\lambda=\{(x,y):Q(x,y)=\lambda\}$ has exactly $q+1$ points, and the $C_\lambda$ partition $AG(2,q)\setminus\{(0,0)\}$.

Let $A$ be an additive subgroup of $\mathbb F_q$ of order $n$ (an $\mathbb F_2$-subspace of dimension $\log_2n$) and define

$$K=\{(x,y)\in AG(2,q):Q(x,y)\in A\}=\{(0,0)\}\cup\bigcup_{\lambda\in A\setminus\{0\}}C_\lambda,$$

so $|K|=1+(n-1)(q+1)=(n-1)q+n$. I claim every line of $PG(2,q)$ meets $K$ in $0$ or $n$ points.

The line at infinity meets $K$ in $0$ points.

Lines through the origin. On $y=mx$ we have $Q(x,mx)=c_mx^2$ with $c_m=Q(1,m)\ne0$. Since $x\mapsto c_mx^2$ is a bijection of $\mathbb F_q$, the number of $x$ with $c_mx^2\in A$ is $|A|=n$. On $x=0$, $Q(0,y)=\beta y^2$, and likewise $n$ points.

Lines not through the origin. Consider $y=mx+c$ with $c\ne0$. Then

$$Q(x,mx+c)=x^2+x(mx+c)+\beta(mx+c)^2=c_mx^2+cx+\beta c^2=\varphi(x)+\beta c^2,$$

where $\varphi(x)=c_mx^2+cx$ is $\mathbb F_2$-linear with kernel $\{0,c/c_m\}$ of order $2$; so its image $H$ is an additive subgroup of index $2$ and every element of $H$ has exactly two preimages. Moreover $\beta c^2\notin H$: if $\varphi(x)=\beta c^2$ then $Q(x,mx+c)=0$, forcing $(x,mx+c)=(0,0)$ and $c=0$. Now the number of points of $K$ on the line is

$$\#\{x:\varphi(x)+\beta c^2\in A\}=\#\{x:\varphi(x)\in A+\beta c^2\}=2\,|H\cap(A+\beta c^2)|,$$

where $A+\beta c^2$ is the coset $\{a+\beta c^2:a\in A\}$. If $A\subseteq H$, then since $\beta c^2\notin H$ the coset $A+\beta c^2$ lies in the complement of $H$ and the count is $0$. If $A\not\subseteq H$, then $A\cap H$ has index $2$ in $A$, and $H\cap(A+\beta c^2)=\{a+\beta c^2:a\in A,\ a\in H+\beta c^2\}$ has $|A\setminus H|=n/2$ elements, because $H+\beta c^2$ is the complement of $H$; the count is $n$. The vertical lines $x=c\ne0$ are handled identically with $Q(c,y)=\beta y^2+cy+c^2$, $\varphi(y)=\beta y^2+cy$, and $c^2\notin\operatorname{im}\varphi$ because $Q(c,y)\ne0$.

So $K$ is a maximal arc of degree $n$. ∎

Remark 2.5. The proof shows more: for $n'\mid n$ one may take a subgroup $A'\le A$ of order $n'$, and then $K'=\{Q\in A'\}\subseteq K$ is a maximal arc of degree $n'$ contained in $K$. In particular every Denniston arc of degree $n\ge2$ contains a hyperoval $\{(0,0)\}\cup C_\lambda$ through the origin. This nesting is used in §7.2.

Denniston's are not the only maximal arcs in planes of even order: Thas (1974) and Mathon (2002) gave further constructions, and Hamilton and Mathon (2004) used Mathon's method to produce maximal arcs not of Denniston type for every degree $n\mid q$ with $4<n<q/2$. Only Denniston arcs are used here.

For $q$ odd the situation is the opposite.

Theorem 2.6 (Ball, Blokhuis, and Mazzocca 1997). If $q$ is odd, $PG(2,q)$ contains no maximal arc of degree $n$ with $1<n<q$.

The proof, and the shorter one of Ball and Blokhuis (1998), associates to a putative arc a polynomial over $\mathbb F_q$ and derives a contradiction from its degree and its vanishing; it is a polynomial-method argument in the sense of the companion dissertation, and I do not reproduce it. Lemma 2.3, Theorem 2.4, and Theorem 2.6 together give the complete existence theory: a maximal arc of degree $n$, $1<n<q$, exists in $PG(2,q)$ if and only if $q$ is even and $n\mid q$.

2.4 Kakeya sets

A Kakeya set in $AG(2,q)$ is a set containing a line in every direction; it is what I call a $1$-fold Kakeya set. Dvir (2009) proved that a Kakeya set in $\mathbb F_q^n$ has at least $\binom{q+n-1}{n}$ points, so at least $\binom{q+1}2$ in the plane. The exact value is due to Blokhuis and Mazzocca (2008):

$$\kappa_1(q)=\begin{cases}\dfrac{q(q+1)}2+\dfrac{q-1}2&q\text{ odd},\\[6pt]\dfrac{q(q+1)}2&q\text{ even},\end{cases}$$

the even case being attained exactly by the duals of hyperovals through $O$ and the odd case by a construction from a conic, which Blokhuis and Mazzocca also showed to be the only one (they state the classification for a dual oval, which for odd $q$ is a dual conic by Segre's theorem (1955)). The even case is the first instance of Theorem B: a hyperoval is a maximal arc of degree $2=r+1$. Blokhuis, De Boeck, Mazzocca, and Storme (2014) study the spectrum of sizes above the minimum and classify the smallest examples; Dover, Mellinger, and Scott (2014) consider Kakeya sets minimal under inclusion, which need not have minimum size.

The quantity $\kappa_r(q)$ is a minimum over configurations: every $r$-fold Kakeya set contains an $r$-fold configuration's union, and every such union is an $r$-fold Kakeya set. So

$$\kappa_r(q)=\min\{|U(\mathcal L)|:\mathcal L\text{ an }r\text{-fold configuration}\},$$

and I work with configurations throughout.

2.5 The polynomial method

The polynomial method proves lower bounds on $|U|$ by finding a nonzero polynomial of low degree vanishing on $U$ (by linear algebra, if $|U|$ is small) and showing that the structure of $U$ forces the degree to be large. Dvir's argument for Kakeya sets is the model (Guth 2016 is the general reference for the method; the companion dissertation develops it from three lemmas), and I state the form of it that will be needed. Say that a polynomial in $\mathbb F_q[x,y]$ is reduced if every exponent is at most $q-1$; every function $\mathbb F_q^2\to\mathbb F_q$ is represented by exactly one reduced polynomial, and the reduced polynomials of degree at most $d$ form a space of dimension

$$m_d=\#\{(i,j):0\le i,j\le q-1,\ i+j\le d\}.$$

Proposition 2.7 (Dvir's argument for $r$-fold sets). Let $K$ be an $r$-fold Kakeya set in $AG(2,q)$, $r\ge1$. No nonzero polynomial of degree at most $q-1$ vanishes on $K$. Hence $|K|\ge\binom{q+1}2$.

Proof. Suppose $P\ne0$ of degree $d\le q-1$ vanishes on $K$, and let $P_d$ be its homogeneous part of degree $d$; $d\ge1$ since $K\ne\emptyset$. For each direction $\mathbf b\ne\mathbf0$ choose a line $\{\mathbf a+t\mathbf b\}\subseteq K$; the univariate polynomial $P(\mathbf a+t\mathbf b)$ has degree at most $d<q$ and $q$ roots, so is zero, and its coefficient of $t^d$, which is $P_d(\mathbf b)$, vanishes. Thus $P_d$ vanishes at every point of $\mathbb F_q^2$ (at $\mathbf 0$ by homogeneity). A nonzero polynomial of degree $d<q$ has at most $dq<q^2$ zeros in $\mathbb F_q^2$, a contradiction. The bound follows because a set of fewer than $\binom{q+1}2$ points is the zero set of a nonzero polynomial of degree at most $q-1$, there being $\binom{q+1}2$ monomials of that degree. ∎

The argument uses one line per direction and nothing else, so it cannot distinguish $r=2$ from $r=1$. Chapter 7 (§7.4) shows that this is not an artefact of the proof: for the minimal configurations found by computation, the least degree of a nonzero reduced polynomial vanishing on $U$ is exactly the least $d$ with $m_d>|U|$, the degree at which such a polynomial exists for trivial reasons. Any improvement must therefore come from an argument that sees several lines per direction at once. The next chapter gives one, and it is not a polynomial argument.