Appendix A. Computations

All computations were performed in JavaScript (Node.js 22) on a laptop. The fields $\mathbb F_4,\mathbb F_8,\mathbb F_9,\mathbb F_{16}$ were represented as $\mathbb F_2[x]/(x^2+x+1)$, $\mathbb F_2[x]/(x^3+x+1)$, $\mathbb F_3[x]/(x^2+1)$, $\mathbb F_2[x]/(x^4+x+1)$, with an element $\sum a_ix^i$ encoded as the integer $\sum a_ip^i$; the witnesses in §5.4 use this encoding. Lines of direction $(1:s:0)$ are $\{(t,\,b+st):t\in\mathbb F_q\}$ and lines of direction $(0:1:0)$ are $\{(b,t)\}$.

A.1 Exhaustive search for $\kappa_r(q)$

The program enumerates $r$-fold configurations direction by direction, choosing an $r$-subset of the $q$ lines of each direction, maintaining the multiplicity of every point and the current union size, and abandoning a branch as soon as the union is at least the best size found (the union can only grow). Symmetry is used in the two coordinate directions: the maps $(x,y)\mapsto(\lambda x+\mu,\ \nu y+\rho)$, $\lambda\nu\ne0$, permute the parallel classes and preserve union sizes, and they act on the lines $y=b$ of direction $(1:0:0)$ through the affine group of $\mathbb F_q$, which is transitive on ordered pairs of distinct elements; so for $r\ge2$ the chosen lines in that direction may be assumed to include $y=0$ and $y=1$, and independently those in direction $(0:1:0)$ may be assumed to include $x=0$ and $x=1$; for $r=1$, translations give $y=0$ and $x=0$. The number of configurations examined is therefore $\binom{q-2}{r-2}^2\binom qr^{q-1}$ before pruning.

The pruning is effective when $r$ is small relative to $q$; for $q=8$, $r=4$ the $\binom84=70$ subsets per direction defeat it. The extremal configurations reported in Chapter 7 are, in the notation "$b_1b_2\cdots\mid\cdots$" listing the chosen $b$-values per direction $(1:0:0),(1:1:0),\dots,(1:q-1:0),(0:1:0)$:

• $q=5$, $r=2$: $01\mid01\mid23\mid24\mid34\mid01$;
• $q=7$, $r=2$: $01\mid01\mid03\mid12\mid23\mid56\mid45\mid01$;
• $q=7$, $r=3$: $012\mid012\mid034\mid123\mid236\mid056\mid456\mid013$;
• $q=7$, $r=4$: $0123\mid0123\mid0345\mid1245\mid0234\mid1456\mid0456\mid0134$;
• $q=8$, $r=2$: $01\mid02\mid05\mid34\mid17\mid34\mid26\mid15\mid01$;
• $q=9$, $r=2$ (65 points): $01\mid01\mid34\mid35\mid45\mid67\mid78\mid68\mid01\mid01$.

A.2 Denniston arcs and their duals

For $q=2^h$ and $n\mid q$ the program finds $\beta$ with $\operatorname{Tr}(\beta)=1$, takes $A$ to be the span of $1,x,\dots$ (as $\mathbb F_2$-subspace of dimension $\log_2n$), forms $K=\{(x,y):x^2+xy+\beta y^2\in A\}$, and checks $|K|=(n-1)q+n$ and that every affine line meets $K$ in $0$ or $n$ points. It then forms the dual lines $xX+yY+1=0$ for $(x,y)\in K\setminus\{(0,0)\}$, whose direction is $(y:x:0)$ in characteristic $2$, verifies that there are $n-1$ per direction, and computes the union and its multiplicities. Results: $(q,n)=(4,2)$: $|K|=6$, dual union $10$, all multiplicities $2$. $(8,2)$: $10$, $36$, all $2$. $(8,4)$: $\beta=1$, $|K|=28$, line intersections $\{0{:}9,\ 4{:}63\}$, dual union $54$, all multiplicities $4$. $(16,4)$: $\beta=8$ (i.e. $x^3$), $|K|=52$, intersections $\{0{:}51,\ 4{:}221\}$, dual union $204$, all multiplicities $4$. Sub-configurations with $r$ lines per direction chosen inside the dual arc were minimised exhaustively over $\binom{n-1}r^{q+1}$ choices: $(8,4)$: $r=1$: $36$; $r=2$: $51$. $(16,4)$: $r=1$: $136$; $r=2$: $194$.

A.3 Pencils of conics

For odd $q$ the program takes the least non-square $\beta$, the conics $C_\lambda=\{x^2-\beta y^2=\lambda\}$, and, for even $r$, every choice of $r/2$ squares and $r/2$ non-squares as $\Lambda$; it forms the dual lines of the points of $\bigcup_{\lambda\in\Lambda}C_\lambda$, checks that there are $r$ per direction, and records the smallest union. The values are in §7.3.

A.4 The direction-determination number $D(q)$

Since the affine group is transitive on ordered pairs of distinct points, a determining set may be assumed to contain $(0,0)$ and $(1,0)$. For $t=2,3,\dots$ the program searches depth-first for $t$-sets containing these two points that determine all $q+1$ directions, maintaining a count of determined directions and pruning a branch when the remaining points cannot determine enough new directions (a $k$-th point adds at most $k-1$). All runs took under a second; $D(q)$ is the least $t$ for which a set is found, and its non-existence for smaller $t$ is exhaustive.

A.5 Vanishing degrees

For the prime fields $\mathbb F_5$ and $\mathbb F_7$ and a configuration given by its choice string, the program lists the reduced monomials $x^iy^j$ ($0\le i,j\le q-1$, $i+j\le d$), forms the evaluation matrix at the points of $U$, and computes its rank by Gaussian elimination modulo $q$. A nonzero reduced polynomial of degree $\le d$ vanishing on $U$ exists iff the rank is less than the number of monomials, and the kernel dimension is the difference. The results are in §7.4.

A.6 Program (core of the search)

// r-fold Kakeya sets in AG(2,q): minimum union of r lines per direction (core; field tables omitted)
const q = Number(process.argv[2]), r = Number(process.argv[3]);
// lines[d][b]: point indices of the b-th line in direction d (d = 0..q-1 slopes, d = q vertical)
function subsets(mustContain) {            // r-subsets of {0..q-1}, optionally forced to contain 0 and 1
  const out = [], fixed = mustContain ? (r === 1 ? [0] : [0, 1]) : [];
  (function rec(start, cur) {
    if (cur.length === r) { out.push(cur.slice()); return; }
    for (let b = start; b < q; b++) { cur.push(b); rec(b + 1, cur); cur.pop(); }
  })(fixed.length, fixed.slice());
  return out;
}
const allSubs = subsets(false), fixedSubs = subsets(true);
const cnt = new Int32Array(q * q); let size = 0, best = Infinity;
(function rec(d) {
  if (size >= best) return;                  // the union only grows
  if (d === q + 1) { best = size; return; }
  const subs = (d === 0 || d === q) ? fixedSubs : allSubs;   // symmetry in the two axis directions
  for (const S of subs) {
    for (const b of S) for (const P of lines[d][b]) if (cnt[P]++ === 0) size++;
    rec(d + 1);
    for (const b of S) for (const P of lines[d][b]) if (--cnt[P] === 0) size--;
  }
})(0);
console.log(q, r, best);