Constructions and Exact Values

7.1 Pencil complements

Proposition 7.1. Let $T\subseteq AG(2,q)$ be $s$-valid (at most $s$ lines of every direction meet $T$), $1\le s\le q$. Then $\kappa_{q-s}(q)\le q^2-|T|$. In particular, taking $T$ to be $s$ collinear points, $\kappa_{q-s}(q)\le q^2-s$ for $1\le s\le q$.

Proof. In each direction choose $q-s$ lines that miss $T$, which is possible since at most $s$ lines of that direction meet $T$. The chosen lines form a $(q-s)$-fold configuration whose union avoids $T$. ∎

For $s=1$ this is the pencil complement of §4.3, the lines avoiding one point, with union of size $q^2-1$, attaining Theorem A. For $s=q-1$ it is the tautology $\kappa_1(q)\le q^2-|T|$ for $T$ the complement of a Kakeya set. Theorem 5.4 says that for $s\le D(q)-2$ the collinear choice is optimal.

7.2 Dual Denniston arcs and their sub-configurations

Proposition 7.2. Let $q=2^h$ and $n\mid q$, $n\ge2$. The dual of a Denniston arc of degree $n$ (Theorem 2.4) with respect to its origin is an $(n-1)$-fold configuration attaining Theorem A, with all multiplicities $n$. For every $n'\mid n$ it contains an $(n'-1)$-fold sub-configuration attaining Theorem A. Hence $\kappa_{n-1}(q)=\frac{n-1}nq(q+1)$ for all $n\mid q$.

Proof. Theorem 4.2 and Remark 2.5. ∎

The construction was carried out explicitly (Appendix A.2). For $q=8$ and $n=4$ one may take $\beta=1$ (since $\operatorname{Tr}(1)=1$ in $\mathbb F_8$) and $A=\{0,1,x,x+1\}$ in $\mathbb F_8=\mathbb F_2[x]/(x^3+x+1)$. The arc has $28$ points; its $63$ affine secants each carry $4$ points and its other $9$ affine lines none. The dual configuration has $27$ lines, $3$ per direction, union of $54$ points, every one of multiplicity $4$. For $q=16$, $n=4$, with $\beta$ of trace $1$ and $A$ the span of $1$ and $x$: $52$ points, dual union $204$, all multiplicities $4$.

Choosing $r<n-1$ lines per direction inside the dual arc gives an $r$-fold configuration whose union is a subset of the arc's union, and one may minimise over the $\binom{n-1}r^{q+1}$ choices. For $q=8$, $n=4$, $r=2$ the minimum over the $3^9$ choices is $51$, with spectrum $\{2{:}18,\ 3{:}24,\ 4{:}9\}$; the exhaustive search over all $2$-fold configurations of $AG(2,8)$ (Appendix A.1) also gives $51$, with a different spectrum $\{1{:}2,\ 2{:}12,\ 3{:}30,\ 4{:}7\}$. So $\kappa_2(8)=51$, and the dual Denniston arc contains an optimal $2$-fold sub-configuration. For $q=16$, $n=4$, $r=2$ the minimum over $3^{17}$ choices is $194$, against the bound $181\frac13$; whether $\kappa_2(16)=194$ is open.

7.3 Pencils of conics for odd $q$

Theorem 7.3. Let $q$ be odd, $\beta\in\mathbb F_q$ a non-square, $Q(x,y)=x^2-\beta y^2$, and for $\lambda\ne0$ let $C_\lambda=\{(x,y):Q(x,y)=\lambda\}$. Then:

(a) Each $C_\lambda$ has $q+1$ points, and the $C_\lambda$ partition $AG(2,q)\setminus\{O\}$, $O=(0,0)$.

(b) Every line through $O$ meets $C_\lambda$ in $0$ or $2$ points. The set of lines through $O$ that meet $C_\lambda$ depends only on whether $\lambda$ is a square; the two classes give complementary sets of $\frac{q+1}2$ lines each.

(c) Let $r$ be even and let $\Lambda$ consist of $r/2$ non-zero squares and $r/2$ non-squares. Then $S=\bigcup_{\lambda\in\Lambda}C_\lambda$ has exactly $r$ points on every line through $O$, so its dual (with respect to $O$) is an $r$-fold configuration.

Proof. (a) $Q$ is the norm form of $\mathbb F_{q^2}=\mathbb F_q(\sqrt\beta)$ over $\mathbb F_q$: $N(x+y\sqrt\beta)=x^2-\beta y^2$. The norm is a surjective homomorphism $\mathbb F_{q^2}^\times\to\mathbb F_q^\times$ with fibres of size $q+1$, and $Q(x,y)=0$ only at $O$ since $\beta$ is a non-square.

(b) On the line $y=mx$, $Q=x^2(1-\beta m^2)$, and $1-\beta m^2\ne0$ since $\beta$ is a non-square; $x^2(1-\beta m^2)=\lambda$ has two solutions if $\lambda(1-\beta m^2)$ is a non-zero square and none otherwise. On $x=0$, $Q=-\beta y^2=\lambda$ has two solutions iff $-\lambda\beta$ is a square. In both cases the condition is "$\lambda\cdot\gamma\in\square$" for a fixed $\gamma$ depending on the line, and replacing $\lambda$ by $\lambda\nu$ with $\nu$ a non-square negates it. Since $C_\lambda$ has $q+1$ points and each line through $O$ meets it in $0$ or $2$, exactly $\frac{q+1}2$ lines through $O$ meet it.

(c) By (b), each line through $O$ meets every conic of one of the two classes in $2$ points and no conic of the other class; with $r/2$ conics in each class it meets $S$ in $2\cdot\frac r2=r$ points. The conics are disjoint by (a) and $O\notin S$. ∎

Remark 7.4. A line $y=ax+c$ with $c\ne0$ meets $C_\lambda$ iff the quadratic $(1-\beta a^2)x^2-2\beta acx-\beta c^2-\lambda$ has a root, i.e. iff its discriminant $4\big(\beta c^2+\lambda(1-\beta a^2)\big)$ is a square or zero. Writing $u=\beta c^2$ and $v=1-\beta a^2$, the line is skew to all of $S$ iff $u+\lambda v$ is a non-square for every $\lambda\in\Lambda$. For $r$ "random-looking" values of $\lambda$ one expects about a $2^{-r}$ fraction of the $q^2-q$ lines $y=ax+c$, $c\ne0$, to be skew, so $|U|\approx(1-2^{-r})q^2$. For $r=2$ this is $\frac34q^2$, above the bound $\frac23q^2$ by a constant factor: the construction is not asymptotically optimal. It is, however, exactly optimal at $q=7$.

The minimum of $|U|$ over all admissible choices of $\Lambda$ was computed (Appendix A.3):

For $q=7$, $r=2$, the optimal pencil configuration has spectrum $\{2{:}16,\ 3{:}16,\ 4{:}8\}$, different from the spectrum $\{1{:}2,\ 2{:}10,\ 3{:}22,\ 4{:}6\}$ of the search's optimum; both have deficiency $\frac83$. So the $2$-fold extremal problem for $q=7$ has at least two inequivalent solutions.

7.4 The reach of the polynomial method

Proposition 2.7 says that no polynomial of degree less than $q$ vanishes on an $r$-fold Kakeya set. The counting lemma of the polynomial method says that a nonzero reduced polynomial of degree at most $d$ vanishing on $U$ exists as soon as $m_d>|U|$, where $m_d$ is the number of reduced monomials of degree at most $d$; write $d^\ast(U)=\min\{d:m_d>|U|\}$ for this trivial threshold and $\delta(U)$ for the least degree of a nonzero reduced polynomial vanishing on $U$. Then $q\le\delta(U)\le d^\ast(U)$. In this form the method proves $|U|\ge m_d$ for every $d$ with $\delta(U)>d$: Proposition 2.7 gives $\delta(U)\ge q$, hence $|U|\ge m_{q-1}=\binom{q+1}2$, and more would follow only from a proof that $\delta(U)>q$.

Proposition 7.5 (Theorem D). For each minimal configuration in the following table, $\delta(U)=d^\ast(U)$; that is, the points of $U$ impose independent conditions on reduced polynomials of every degree below $d^\ast(U)$.

Proof. Computation (Appendix A.5): for each $d$ the rank of the evaluation matrix of the reduced monomials of degree $\le d$ at the points of $U$ was computed over $\mathbb F_q$; it equals $\min(|U|,m_d)$ in every case, so the kernel is nonzero exactly when $m_d>|U|$, with dimension $m_d-|U|$. ∎

(The $r=1$ row uses a $32$-point $1$-fold configuration, one point above the minimum; the minimal $31$-point configurations behave the same way, with $\delta=7$ and kernel dimension $3$.) The table shows that the "zeros" half of the polynomial method, which must show that $U$ cannot be the zero set of a polynomial of the degree that counting provides, has nothing to work with for $r\ge2$ beyond degree $q$: the polynomials of degree $d^\ast(U)>q$ that vanish on the optimal $r$-fold unions exist for the trivial reason and there are exactly as many of them as counting predicts. To reproduce Theorem A by the polynomial method one would have to prove $\delta(U)\ge d_r(q)$ with $m_{d_r(q)}\approx\frac r{r+1}q^2$. Since $m_d=q^2-\binom{2q-1-d}2$ for $d\ge q-1$, this means $d_r(q)\approx q\big(2-\sqrt{2/(r+1)}\big)$, about $1.18q$ for $r=2$: a statement about polynomials of degree well above $q$ vanishing on unions of lines, which is the territory of Rédei-type and lacunary polynomials (Rédei 1970; Ball, Blokhuis, and Mazzocca 1997) rather than of the restriction-to-lines argument.

7.5 Table of exact values

The following table collects everything known to me about $\kappa_r(q)$ for $q\le9$ and $q=16$. Provenance: A equality in Theorem A (Corollary 4.3); C Theorem 5.4; E exhaustive search (Appendix A.1); BM Blokhuis and Mazzocca (2008); D dual Denniston sub-configuration (§7.2); a range gives the best lower and upper bounds known.

Every equality case of Theorem A in the table is one predicted by Corollary 4.3, and every case predicted by Corollary 4.3 with $q\le9$ or $q=16$ appears as an equality (the trivial case $r=q$, where $U$ is the whole plane, is listed only for $q=16$).