A New Result: Punctured Kakeya Sets in the Plane

This chapter contains the dissertation's one claim to new mathematics. It determines, for every odd prime power $q$, the minimum size of a subset of $\mathbb F_q^2$ that contains all but at most one point of some line in every direction, and it determines the same quantity for even $q$ up to an additive constant, exactly for $q\le8$. The answer is $\lfloor q^2/2\rfloor$ for odd $q$ and $q^2/2-1$ for $q=4$ and $q=8$; the polynomial method (Corollary 4.3) gives $\binom{q}{2}=q^2/2-q/2$, so the chapter also measures precisely how far the polynomial bound is from the truth for this variant of the Kakeya problem: by $(q-1)/2$.

I have searched the literature and have not found this quantity studied before; the closest relatives are the exact solution of the unpunctured problem by Blokhuis and Mazzocca (2008), the finite-field Furstenberg sets of Ellenberg and Erman (2016), of which the sets studied here are the special case $(k,m)=(1,q-1)$ in the plane, the fixed-line-set variant of Ball, Blokhuis, and Domenzain (2016), and the inclusion-minimal Kakeya sets of Dover, Mellinger, and Scott (2014), which need not have minimum size. The proofs below depend on one classical theorem, the Blokhuis–Mazzocca classification of minimal Kakeya sets for odd $q$, which I cite and do not reprove; the statements that depend on it are marked. Everything else is proved in full, and every statement has been checked by exhaustive computation for $q\le9$ (§7.6 and Appendix A.6).

7.1 Definitions and results

Blokhuis and Mazzocca define a Kakeya set in $AG(2,q)$ as the union of $q+1$ lines, one in each direction; a Kakeya set in the sense of Definition 4.1 contains such a union, so the minimum size $\kappa(q)$ of a Kakeya set is the minimum size of such a union. Their theorem, which the computations of §4.5 confirmed for $q\le7$, is:

Theorem 7.A (Blokhuis and Mazzocca 2008). For $q$ odd, $\kappa(q)=\binom{q+1}{2}+\frac{q-1}{2}$; for $q$ even, $\kappa(q)=\binom{q+1}{2}$. For $q$ odd, every Kakeya set of size $\kappa(q)$ arises from the conic construction of Lemma 7.8 below.

The classification statement is Blokhuis and Mazzocca's; for $q$ even, the sets of size $\binom{q+1}{2}$ are the unions of $q+1$ lines of a dual hyperoval.

Definition 7.1. A punctured Kakeya set in $\mathbb F_q^2$ is a set $K$ such that for every direction $\mathbf b\ne\mathbf 0$ there is a line $\ell$ in direction $\mathbf b$ with $|\ell\setminus K|\le1$. Let $\kappa^-(q)$ be the minimum size of a punctured Kakeya set.

In the terminology of Ellenberg and Erman (2016), a punctured Kakeya set is a $(1,q-1)$-Furstenberg set in $\mathbb F_q^2$. Corollary 4.3 with $k=q-1$ gives $\kappa^-(q)\ge\binom{q}{2}$. The results of this chapter are the following.

Theorem 7.2. For every odd prime power $q\ge3$,

$$\kappa^-(q)=\frac{q^2-1}{2}.$$

Theorem 7.3. For every even prime power $q\ge4$,

$$\frac{q^2}{2}-\Big\lceil\frac{q+1}{6}\Big\rceil\ \le\ \kappa^-(q)\ \le\ \frac{q^2}{2}-1,$$

with equality on the right for $q=4$ and $q=8$. If every union of $q+1$ lines in distinct directions that is not of minimum size has at least $\binom{q+1}{2}+\frac q2$ points (the gap property, discussed in §7.5), then $\kappa^-(q)=q^2/2-1$ for every even $q\ge4$.

The exact values for small $q$ are:

The proof of Theorem 7.2 uses Theorem 7.A, including the classification; the proof of the upper bound in Theorem 7.3 uses only the existence of ovals; the proof of the lower bound in Theorem 7.3 uses nothing beyond counting. The method is not the polynomial method. It is inclusion–exclusion, sharpened by a matching argument, and its interest for this dissertation is exactly that it shows what the polynomial method leaves on the table in the plane.

7.2 Unions of lines in distinct directions

Fix $q+1$ lines $\ell_b$, one in each direction $b$, and let $U=\bigcup_b\ell_b$. For a point $P\in\mathbb F_q^2$ let $m_P$ be the number of the lines $\ell_b$ through $P$, and let $n_k=\#\{P:m_P=k\}$. Call $P$ simple if $m_P=1$, double if $m_P=2$, and multiple if $m_P\ge3$.

Lemma 7.4 (Exact size). With $E=\sum_P\binom{m_P-1}{2}=\sum_{k\ge3}\binom{k-1}{2}n_k$,

$$|U|=\binom{q+1}{2}+E.$$

Proof. Two lines in distinct directions meet in exactly one point, so $\sum_P\binom{m_P}{2}=\binom{q+1}{2}$; and $\sum_Pm_P=q(q+1)$ since each line has $q$ points. Hence

$$|U|=\sum_{P\in U}1=\sum_{P\in U}\Big[m_P-\binom{m_P}{2}+\binom{m_P-1}{2}\Big]=q(q+1)-\binom{q+1}{2}+E=\binom{q+1}{2}+E,$$

using the identity $1=m-\binom m2+\binom{m-1}{2}$ for $m\ge1$. ∎

The inequality $|U|\ge\binom{q+1}{2}$ is Bonferroni's inequality $|\bigcup A_i|\ge\sum|A_i|-\sum_{i<j}|A_i\cap A_j|$, and it coincides with Dvir's bound $\binom{q+n-1}{n}$ for $n=2$. Theorem 7.A says that $E\ge(q-1)/2$ for odd $q$, and that $E=0$ is attained for even $q$.

Lemma 7.5 (Line identities). For each line $\ell=\ell_b$, let $t_\ell$ be the number of simple points on $\ell$. Then

$$\sum_{P\in\ell}(m_P-1)=q,\qquad t_\ell=\sum_{P\in\ell,\ m_P\ge2}(m_P-2).$$

Consequently: (a) a line carrying a simple point passes through a multiple point; (b) a line carrying no simple point consists of double points only; (c) $n_1=\sum_{k\ge3}k(k-2)\,n_k$; (d) for every line $M$ that is not one of the $\ell_b$, $\sum_{P\in M}m_P=q$.

Proof. Each of the other $q$ lines meets $\ell$ in exactly one point, which gives the first identity. In it, the $t_\ell$ simple points contribute $0$ and the remaining $q-t_\ell$ points contribute $m_P-1\ge1$ each, so $\sum_{P\in\ell,m_P\ge2}(m_P-2)=q-(q-t_\ell)=t_\ell$, the second identity. (a) and (b) are immediate from the second identity. (c) follows by summing the second identity over all lines: the left side gives $n_1$, and a point of multiplicity $k\ge2$ is counted on $k$ lines with weight $k-2$. (d) holds because $M$ is parallel to exactly one $\ell_b$ and meets the other $q$ lines once each. ∎

7.3 Reduction to a matching problem

Lemma 7.6. Let $K$ be a punctured Kakeya set. Then there are lines $\ell_b$, one per direction, and a set $X$ of points of $U=\bigcup\ell_b$ such that no two points of $X$ lie on a common line $\ell_b$, and $|K|\ge|U|-|X|$. Conversely, for any such $U$ and $X$, $U\setminus X$ is a punctured Kakeya set. Hence

$$\kappa^-(q)=\min\big(|U|-\nu\big),$$

where the minimum is over all choices of one line per direction and $\nu=\nu(U)$ is the largest size of a set of points of $U$ no two of which lie on a common line $\ell_b$.

Proof. For each direction choose a line $\ell_b$ with $|\ell_b\setminus K|\le1$, and a point $x_b\in\ell_b$ with $\ell_b\setminus\{x_b\}\subseteq K$ (any point of $\ell_b$ if $\ell_b\subseteq K$). Then $K\supseteq\bigcup_b(\ell_b\setminus\{x_b\})=U\setminus X$, where $X$ is the set of points $x$ such that $x=x_b$ for every $b$ with $x\in\ell_b$: a point of $U$ is omitted only if it is the chosen puncture of each line through it. Each line has one puncture, so two points of $X$ cannot share a line. Conversely, given $X$ with no two points on a common line, puncture each line at its point of $X$ if it has one, and anywhere otherwise; then $U\setminus X$ contains $q$ points of each line. ∎

In the language of hypergraphs, $\nu$ is the matching number of the hypergraph whose vertices are the $q+1$ lines and whose edges are the points of $U$, each point being the set of lines through it. Every pair of vertices lies in exactly one edge.

Lemma 7.7 (Matching bound). Let $s$ be the number of lines $\ell_b$ that carry at least one simple point. Then

$$\nu\le\Big\lfloor\frac{q+1+s}{2}\Big\rfloor.$$

Proof. Let $X$ be a set of points of $U$ no two on a common line, and let $x_k$ be the number of points of $X$ of multiplicity $k$. Two simple points on the same line would share it, so $x_1\le s$. Each point of multiplicity $k$ uses $k$ lines and the line sets are disjoint, so $x_1+\sum_{k\ge2}kx_k\le q+1$, whence $\sum_{k\ge2}x_k\le(q+1-x_1)/2$ and

$$|X|=x_1+\sum_{k\ge2}x_k\le x_1+\frac{q+1-x_1}{2}=\frac{q+1+x_1}{2}\le\frac{q+1+s}{2}.\qquad∎$$

Lemmas 7.4, 7.6, and 7.7 give, for every configuration,

$$|U|-\nu\ \ge\ \binom{q+1}{2}+E-\Big\lfloor\frac{q+1+s}{2}\Big\rfloor,\tag{7.1}$$

and everything that follows is an analysis of the right-hand side.

7.4 Odd $q$

Lemma 7.8 (The conic configuration). Let $q$ be odd, let $C$ be a conic in $PG(2,q)$, let $T\in C$, and take the tangent line $L$ at $T$ as the line at infinity. Let the chosen lines be the $q$ tangent lines $\ell_R$ at the points $R\in C\setminus\{T\}$, together with one line $m$ through $T$ other than $L$, which meets $C$ again at a point $T'$. Then:

(i) the $q+1$ lines have distinct directions; (ii) $E=(q-1)/2$, the multiple points being the $(q-1)/2$ external points of $C$ on $m$, each of multiplicity $3$; (iii) for $R\ne T'$ the line $\ell_R$ carries exactly one simple point, namely $R$; the line $m$ carries $(q-1)/2$ simple points, the internal points of $C$ on $m$; and the line $\ell_{T'}$ carries no simple point; (iv) puncturing $\ell_R$ at $R$ for each $R\ne T'$ and $m$ at one internal point yields a punctured Kakeya set of size $(q^2-1)/2$.

Proof. We use the standard facts about conics for $q$ odd (Hirschfeld 1998, ch. 8): every point not on $C$ lies on either $0$ tangents (an internal point) or $2$ tangents (an external point); every point of a tangent line other than its point of contact is external; and a secant line contains, besides its two points of $C$, exactly $(q-1)/2$ external and $(q-1)/2$ internal points.

(i) Each $\ell_R$ meets $L$ in an external point of $L$, and each external point of $L$ lies on exactly one tangent other than $L$; so $R\mapsto\ell_R\cap L$ is a bijection from $C\setminus\{T\}$ onto $L\setminus\{T\}$, and the $q$ tangents have $q$ distinct directions, none of them $T$; the line $m$ has direction $T$.

(ii) A point of $\mathbb F_q^2=PG(2,q)\setminus L$ lies on $\ell_R$ iff it is $R$ or an external point on $\ell_R$. So the affine points of $C$ have $m_P=1$ from the tangents, the affine external points have $m_P=2$ from the tangents, and the affine internal points have $m_P=0$ from the tangents; the line $m$ adds $1$ to each of its affine points. The affine points of $m$ are $T'$, $(q-1)/2$ external points, and $(q-1)/2$ internal points. Hence the multiplicities are: $T'$ and the external points off $m$ have $m_P=2$; the external points on $m$ have $m_P=3$; the affine points of $C$ other than $T'$ and the internal points on $m$ have $m_P=1$. So $E=\binom{2}{2}\cdot\frac{q-1}{2}=\frac{q-1}{2}$.

(iii) follows from the list in (ii): the simple points are the $q-1$ points $R\in C\setminus\{T,T'\}$, each on its own tangent, and the $(q-1)/2$ internal points of $m$. The line $\ell_{T'}$ consists of $T'$ and external points, all of multiplicity $2$.

(iv) The $q$ punctures are simple points on $q$ distinct lines, so by Lemma 7.6 the result is a punctured Kakeya set of size $|U|-q=\binom{q+1}{2}+\frac{q-1}{2}-q=\frac{q^2-1}{2}$. ∎

Proof of Theorem 7.2. The upper bound is Lemma 7.8(iv). For the lower bound let $K$ be a punctured Kakeya set and let $U$, $X$, $E$, $s$ be as in §7.3, so that $|K|\ge|U|-\nu$ and (7.1) applies. By Theorem 7.A, $E\ge(q-1)/2$.

If $E\ge(q+1)/2$, then, using only $\nu\le q+1$,

$$|K|\ge\binom{q+1}{2}+\frac{q+1}{2}-(q+1)=\frac{q^2-1}{2}.$$

If $E=(q-1)/2$, then by the classification in Theorem 7.A the configuration is the conic configuration of Lemma 7.8, in which by (iii) the line $\ell_{T'}$ carries no simple point, so $s\le q$ and Lemma 7.7 gives $\nu\le\lfloor(2q+1)/2\rfloor=q$. Hence

$$|K|\ge\binom{q+1}{2}+\frac{q-1}{2}-q=\frac{q^2-1}{2}.\qquad∎$$

Remark 7.9. The classification is used only to gain one point. Without it, Theorem 7.A's bound $E\ge(q-1)/2$ together with $\nu\le q+1$ gives $\kappa^-(q)\ge(q^2-3)/2$ for odd $q\ge5$. Since the computations of §7.6 show that for $q\in\{3,5,7,9\}$ every configuration with $E=(q-1)/2$ has a line without simple points, Theorem 7.2 holds for those $q$ independently of the classification.

Remark 7.10. For $q=5$ and $q=7$ the minimum $(q^2-1)/2$ is also attained by a second family of configurations, with $E=(q+1)/2$, all $(q+1)/2$ multiple points triple, not all on one line, and every line carrying a simple point, so that $\nu=q+1$ (§7.6). For $q=9$ no configuration with $E=5$ exists at all: the values of $E$ that occur are $4$ and then $6$ upward.

7.5 Even $q$

Lemma 7.11 (The dual oval configuration). Let $q\ge4$ be even and let $\mathcal D$ be a dual oval in $PG(2,q)$: a set of $q+1$ lines no three of which are concurrent (for instance the lines $R^\ast$ dual to the points $R$ of a conic). Let $N^\ast$ be its nucleus line, the line consisting of the points that lie on exactly one line of $\mathcal D$. Choose a line $O^\ast\in\mathcal D$ as the line at infinity, let $Z=O^\ast\cap N^\ast$, and let $m$ be any line through $Z$ other than $O^\ast$ and $N^\ast$. Let the chosen lines be the $q$ lines of $\mathcal D\setminus\{O^\ast\}$ together with $m$. Then the lines have distinct directions, $E=q/2$ with all multiple points triple and on $m$, and every line carries a simple point. Consequently $\nu=q+1$ and

$$\kappa^-(q)\le\binom{q+1}{2}+\frac q2-(q+1)=\frac{q^2}{2}-1.$$

Proof. The facts used are the duals of the standard facts about ovals for $q$ even (Hirschfeld 1998, ch. 8): the $q+1$ tangents of an oval $\mathcal O$ are concurrent at its nucleus $N$, every line through $N$ is a tangent, and every line not through $N$ meets $\mathcal O$ in $0$ or $2$ points. Dualising, the points on exactly one line of $\mathcal D$ are exactly the points of a line $N^\ast$, and every point not on $N^\ast$ lies on $0$ or $2$ lines of $\mathcal D$.

Directions. Two lines of $\mathcal D$ meet in a point on no third line of $\mathcal D$; in particular the $q$ lines of $\mathcal D\setminus\{O^\ast\}$ meet $O^\ast$ in $q$ distinct points, so they are affine lines in $q$ distinct directions, and their pairwise intersections are affine. The point $Z\in O^\ast$ lies on $N^\ast$, hence on exactly one line of $\mathcal D$, which is $O^\ast$; so no line of $\mathcal D\setminus\{O^\ast\}$ has direction $Z$, and $m$, which has direction $Z$, supplies the missing direction.

Multiplicities. The $q$ affine lines of $\mathcal D$ pairwise meet in $\binom q2$ distinct affine points, each of multiplicity $2$ among them. The line $m$ is parallel to $N^\ast$ and distinct from it, so its affine points lie off $N^\ast$ and each lies on $0$ or $2$ of the $q$ lines; since $m$ meets each of the $q$ lines once, exactly $q/2$ points of $m$ lie on two of them and $q/2$ on none. Thus $m$ raises $q/2$ double points to triple points and contributes $q/2$ simple points, and $E=q/2$.

Simple points on every line. For a line $R^\ast\in\mathcal D\setminus\{O^\ast\}$, the point $R^\ast\cap N^\ast$ is affine (it is not $Z$, since $Z$ is on $O^\ast$ only), lies on exactly one line of $\mathcal D$, and is not on $m$ (which meets $N^\ast$ only at $Z$); so it is a simple point of $R^\ast$. The line $m$ carries its $q/2$ simple points. So $s=q+1$, and choosing one simple point on each line gives $\nu=q+1$. The size follows from Lemma 7.4. ∎

Lemma 7.12. In every configuration, $s\le3E$.

Proof. By Lemma 7.5(a), every line carrying a simple point passes through a multiple point; a point of multiplicity $k\ge3$ lies on $k$ lines; and $k\le3\binom{k-1}{2}$ for $k\ge3$. Hence $s\le\sum_{k\ge3}kn_k\le3\sum_{k\ge3}\binom{k-1}{2}n_k=3E$. ∎

Proof of Theorem 7.3. The upper bound is Lemma 7.11. For the lower bound, apply (7.1) with Lemma 7.12; write $q+1$ odd. If $E=0$ then $s=0$, $\nu\le q/2$, and $|U|-\nu\ge\binom{q+1}{2}-q/2=q^2/2$. If $1\le E$ and $3E\le q+1$, then

$$|U|-\nu\ \ge\ \binom{q+1}{2}+E-\frac{q+1+3E}{2}=\frac{q^2-1}{2}-\frac E2,$$

so, the left side being an integer, $|U|-\nu\ge q^2/2-\lceil E/2\rceil\ge q^2/2-\lceil(q+1)/6\rceil$. If $3E\ge q+1$, then with $\nu\le q+1$,

$$|U|-\nu\ \ge\ \binom{q+1}{2}-(q+1)+E\ \ge\ \frac{q^2-q-2}{2}+\frac{q+1}{3}=\frac{q^2}{2}-\frac{q+4}{6},$$

so $|U|-\nu\ge q^2/2-\lfloor(q+4)/6\rfloor$, and $\lfloor(q+4)/6\rfloor=\lceil(q+1)/6\rceil$ because $q$, a power of $2$, is $2$ or $4$ modulo $6$. The values for $q=4$ and $q=8$ are from the exhaustive computation of §7.6; note that for $q=4$ the lower bound $8-1=7$ already matches.

For the conditional statement: if every configuration with $E>0$ has $E\ge q/2$, then in the case $E>0$ we have $3E\ge q+1$ and $|U|-\nu\ge\binom{q+1}{2}-(q+1)+\frac q2=\frac{q^2}{2}-1$, while $E=0$ gives $q^2/2$. ∎

The gap property. The hypothesis of the conditional statement is that the sizes of unions of $q+1$ lines in distinct directions, for $q$ even, have a gap: $\binom{q+1}{2}$ occurs, and nothing else below $\binom{q+1}{2}+q/2$. The computations of §7.6 verify this for $q=4$ (the values of $E$ that occur begin $0,2,3,\dots$) and $q=8$ (they begin $0,4,6,\dots$). Blokhuis, De Boeck, Mazzocca, and Storme (2014) study exactly the spectrum of sizes of Kakeya sets for even $q$, prove a gap above the minimum, and classify the smallest examples; I have not been able to consult their paper and cannot quote the precise threshold, so I state the result of this chapter for even $q$ as conditional on the gap property rather than as a theorem. If their gap is the one the computations suggest, Theorem 7.3 gives $\kappa^-(q)=q^2/2-1$ for all even $q\ge4$.

Conjecture 7.13. $\kappa^-(q)=q^2/2-1$ for every even $q\ge4$.

7.6 Computations

All configurations of $q+1$ lines, one per direction, were enumerated for $q\le9$, up to translation (the lines in directions $(1,0)$ and $(0,1)$ can be fixed), and for each the multiplicities, $E$, $s$, and the matching number $\nu$ (by dynamic programming over subsets of the $q+1$ lines) were computed. The program is listed in Appendix A.6. The findings:

Three things in the table are the facts the proofs use. The column $E_{\min}$ is Theorem 7.A. The column "max $s$ at $E_{\min}$" equals $q$ for every odd $q\le9$, which is the consequence of the classification used in the proof of Theorem 7.2, verified directly. And for $q=4,8$ the second value of $E$ is $q/2$, which is the gap property.

The extremal configurations have the following multiplicity distributions $(n_1,n_2,n_3)$, with all multiple points triple:

The rows with "yes" are the conic configuration (odd $q$) and the dual oval configuration (even $q$) of Lemmas 7.8 and 7.11: $(q\mp1)/2$ or $q/2$ triple points on one line, $q-1$ simple points on the other lines and the rest on that line. The rows with "no" are the second odd family of Remark 7.10.

7.7 Discussion

What is new. The quantity $\kappa^-(q)$, the reduction of Lemma 7.6, the matching bound of Lemma 7.7, Theorem 7.2, and Theorem 7.3 with its constructions are, to the best of my knowledge, new. The ingredients are not: Lemma 7.4 is inclusion–exclusion, the conic and dual oval configurations are the classical objects of finite geometry, and the decisive input for odd $q$ is the Blokhuis–Mazzocca classification. What the chapter adds is the observation that puncturing turns the Kakeya problem into a matching problem on the line hypergraph, and that the structure theorems for the unpunctured problem then determine the punctured one.

What it says about the polynomial method. Corollary 4.3 gives $\kappa^-(q)\ge\binom q2$, and the truth is $\binom q2+\frac{q-1}{2}$ for odd $q$. The polynomial method loses exactly $(q-1)/2$, the same amount it loses for the unpunctured problem (§4.5). The loss has a definite source: Dvir's argument sees a punctured Kakeya set only as a set on which a polynomial of degree $q-2$ must vanish, and it cannot see that the missing points of the different lines cannot all be "used twice". The matching argument sees exactly that.

Open questions. (1) Prove the gap property for even $q$, or find it in Blokhuis, De Boeck, Mazzocca, and Storme (2014), and thereby settle Conjecture 7.13. (2) Determine the minimum size of a set containing $q-t$ points of a line in every direction for $2\le t\le q-2$; for $t$ close to $q$ the problem becomes that of sets determining all directions, a classical problem of a different character. (3) Determine the analogue in $\mathbb F_q^3$, where no exact result is known even for the unpunctured problem. (4) Explain the second odd family of Remark 7.10 and its absence for $q=9$.