Kakeya Sets with Multiplicity

A Kakeya set in the affine plane $AG(2,q)$ over the field with $q$ elements is a set containing a line in every direction. Its minimum size was determined by Blokhuis and Mazzocca in 2008, after Dvir's polynomial-method bound of 2008 had settled the order of magnitude in every dimension. This dissertation studies the natural generalisation in which $r$ distinct lines are required in every direction: an $r$-fold Kakeya set. Let $\kappa_r(q)$ be the least size of such a set.

The polynomial method, applied to $r$-fold sets, returns exactly what it returns for $r=1$: no polynomial of degree less than $q$ vanishes on the set, hence $\kappa_r(q)\ge\binom{q+1}{2}$, and in every case computed here that is all the restriction-to-lines argument can give. An elementary count does better. Writing $m_P$ for the number of chosen lines through a point $P$, the union $U$ of the lines satisfies the exact identity

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

so that $\kappa_r(q)\ge\frac{r}{r+1}q(q+1)$, with equality if and only if every point of the union lies on exactly $r+1$ of the lines. Under the standard point–line duality of the projective plane this equality case is precisely a maximal arc of degree $r+1$, and two classical theorems then decide the matter: Denniston's construction (1969) shows that the bound is attained for every even $q$ and every $r+1$ dividing $q$, and the theorem of Ball, Blokhuis, and Mazzocca (1997), itself a polynomial-method result, shows that for odd $q$ it is never attained when $2\le r+1\le q-1$. Thus the polynomial method, shut out at the front door, returns through the back.

Near the other end of the range the problem is solved exactly. It is shown that $\kappa_{q-s}(q)=q^2-s$ whenever $s\le D(q)-2$, where $D(q)$ is the least number of points of $AG(2,q)$ that determine all $q+1$ directions; $D(q)$ is at least the least $t$ with $\binom t2\ge q+1$, and is computed exactly for $q\le16$. Exhaustive computation gives $\kappa_r(q)$ for all $r$ when $q\le7$ and for most $r$ when $q\in\{8,9\}$; explicit constructions from Denniston arcs, from pencils of conics, and from pencils of lines account for the values found. The deficiency $\kappa_r(q)-\frac{r}{r+1}q(q+1)$ for odd $q$ is tabulated and its growth is posed as the main open problem.