Introduction

1.1 The problem

Wolff (1999) proposed the finite-field Kakeya problem as a model for the Euclidean one: how small can a subset of $\mathbb F_q^n$ be if it contains a line in every direction? Dvir (2009) answered it up to a constant with a two-page polynomial argument, and in the plane Blokhuis and Mazzocca (2008) found the exact answer: a Kakeya set in $AG(2,q)$ has at least $\frac{q(q+1)}2+\frac{q-1}2$ points when $q$ is odd and at least $\frac{q(q+1)}2$ when $q$ is even, both bounds being attained.

This dissertation asks what happens when the set is required to contain not one but $r$ distinct lines in every direction. Call such a set an $r$-fold Kakeya set and write $\kappa_r(q)$ for its least possible size. For $r=1$ this is the Kakeya problem; for $r=q$ the only $q$-fold set is the whole plane. In between, the question turns out to have a structure that neither the Kakeya problem nor its polynomial-method treatment prepares one for.

Two remarks motivate the question. First, the requirement "at least $r$ lines in every direction" is the natural way to make a Kakeya set robust: a $1$-fold set can be destroyed by deleting one point from each of $q+1$ lines, while an $r$-fold set survives the deletion of $r-1$ lines' worth. Second, and more consequentially, the dual of an $r$-fold configuration is a classical object. Under the point–line duality of $PG(2,q)$ the $r(q+1)$ lines become $r(q+1)$ points, exactly $r$ on each line through a fixed point $O$, and the size of the union becomes the number of lines not through $O$ that meet this point set. When every point of the union lies on exactly $r+1$ of the lines, the dual point set together with $O$ is a set meeting every line in $0$ or $r+1$ points: a maximal arc. Maximal arcs are among the most studied objects of finite geometry, and their existence question was settled by Denniston (1969), who constructed them for every even $q$ and every degree dividing $q$, and by Ball, Blokhuis, and Mazzocca (1997), who proved that for odd $q$ they do not exist in any nontrivial degree. The second of these theorems is itself a polynomial-method result. So the polynomial method, which as I show cannot see past $r=1$ when applied directly, governs the answer for every $r$ once the problem is turned around.

1.2 Main results

Throughout, $\mathcal L$ is an $r$-fold configuration in $AG(2,q)$, $U=U(\mathcal L)$ its union, and $m_P$ the number of lines of $\mathcal L$ through $P$.

Theorem A (Variance identity). For every $r$-fold configuration,

$$|U|=\frac{r}{r+1}\,q(q+1)+\frac{1}{(r+1)^2}\sum_{P\in U}\big(m_P-(r+1)\big)^2.$$

Consequently $\kappa_r(q)\ge\frac{r}{r+1}q(q+1)$, with equality for a configuration if and only if every point of its union has multiplicity exactly $r+1$.

Theorem B (Equality and maximal arcs). A configuration attains the bound of Theorem A if and only if its dual point set, together with the distinguished point $O$, is a maximal arc of degree $r+1$ in $PG(2,q)$. Consequently $\kappa_r(q)=\frac{r}{r+1}q(q+1)$ holds exactly in the following cases: $r\in\{q-1,q\}$; or $q$ even and $(r+1)\mid q$. In every other case, in particular for every odd $q$ and every $1\le r\le q-2$, the inequality is strict.

Theorem C (Many lines per direction). Let $D(q)$ be the least size of a set of points of $AG(2,q)$ that determines all $q+1$ directions. Then for $1\le s\le D(q)-2$,

$$\kappa_{q-s}(q)=q^2-s,$$

and this fails for $s=D(q)-1$. Moreover $D(q)\ge t_0(q):=\min\{t:\binom t2\ge q+1\}$, so the formula holds in particular whenever $s(s+1)<2(q+1)$. The values of $D(q)$ for $q\le16$ are

Theorem D (The polynomial method). No nonzero polynomial of degree less than $q$ vanishes on an $r$-fold Kakeya set, for any $r\ge1$; hence $\kappa_r(q)\ge\binom{q+1}2$. The argument sees one line per direction, and in the cases computed in Chapter 7 ($q=5$, $r=2$; $q=7$, $1\le r\le4$) it has nothing more to give: reduced polynomials of degree $q$ vanishing on a $1$-fold union exist, and the least degree of a nonzero reduced polynomial vanishing on a minimal $r$-fold union equals the trivial counting threshold, so any improvement on $\binom{q+1}2$ needs an ingredient the argument does not contain.

Theorem E (Constructions). (i) For $1\le s\le q$, the lines avoiding $s$ collinear points form a $(q-s)$-fold Kakeya set of size $q^2-s$. (ii) For $q$ even and $n\mid q$, the dual of a Denniston arc of degree $n$ is an $(n-1)$-fold configuration attaining Theorem A, and for every divisor $n'$ of $n$ it contains an $(n'-1)$-fold sub-configuration attaining Theorem A. (iii) For $q$ odd and $r$ even, the union of $r/2$ conics of square parameter and $r/2$ conics of non-square parameter in the pencil $x^2-\beta y^2=\lambda$ ($\beta$ a non-square) dualises to an $r$-fold configuration.

Together with exhaustive search, these give the following table of exact values; a range gives the best bounds known.

The lower bound of Theorem A is attained exactly at the entries $(3,2)$, $(4,1)$, $(4,3)$, $(5,4)$, $(7,6)$, $(8,1)$, $(8,3)$, $(8,7)$, $(9,8)$, and at no others, as Theorem B predicts.

1.3 Provenance

I have tried to be exact about what is new. The definition of $r$-fold Kakeya sets, the variance identity of Theorem A, the equality characterisation and its consequences in Theorem B, the reduction of the problem near $r=q$ to the direction-determination number $D(q)$ in Theorem C, the observation in Theorem D that the polynomial method is stuck at $r=1$, the constructions (ii) and (iii) of Theorem E as $r$-fold Kakeya sets, and all the computations are, to the best of my knowledge, new. A literature search found no treatment of Kakeya sets with a multiplicity requirement and no mention of the duality with maximal arcs in that context. On the other side of the duality everything is classical: maximal arcs go back to Barlotti (1955) and Cossu (1961), Denniston's construction is from 1969, the divisibility condition is folklore, and the non-existence theorem for odd $q$ is due to Ball, Blokhuis, and Mazzocca (1997), with a shorter proof by Ball and Blokhuis (1998). A specialist in finite geometry will recognise Theorem B as a translation; I claim only that the translation is worth making, because it exhibits an extremal problem of Kakeya type whose answer, in the equality case, is decided by a theorem proved with polynomials after the direct polynomial approach has failed. The quantity $D(q)$ of Theorem C, the smallest set determining all directions, is a natural cousin of the well-studied problem of the fewest directions determined by a set of $q$ points (Rédei 1970; Szőnyi 1996; Ball, Blokhuis, Brouwer, Storme, and Szőnyi 1999); I have not found it in the literature and treat it as new, with the same caveat.

The dissertation is a companion to the author's Three Lemmas, which develops the polynomial method in combinatorics and includes, in its Chapter 7, the case of punctured Kakeya sets (all but one point of a line in every direction). The present work uses the Dvir argument from there and nothing else from it.

1.4 Outline

Chapter 2 sets up the plane, the duality, and the theory of maximal arcs, and proves Denniston's theorem in full, since the equality case of the main problem rests on it. Chapter 3 proves Theorem A and the incidence identities behind it. Chapter 4 proves Theorem B. Chapter 5 proves Theorem C and computes $D(q)$. Chapter 6 treats odd $q$: the strict inequality, the deficiency in the range covered by Theorem C, and the data for the range not covered. Chapter 7 gives the constructions of Theorem E, proves Theorem D, and assembles the table of exact values. Chapter 8 concludes with open problems. Appendix A describes the computations.