Appendix A. Computations

// one line per direction; lines[d][b] = point indices of the b-th line in direction d
function matchingNumber(edgeMasks) {          // edges = points, as bitmasks of the lines through them
  const full = (1 << D) - 1, byLow = Array.from({ length: D }, () => []);
  for (const e of edgeMasks) { let v = 0; while (!((e >> v) & 1)) v++; byLow[v].push(e); }
  const dp = new Int8Array(1 << D);
  for (let mask = 1; mask <= full; mask++) {
    let v = 0; while (!((mask >> v) & 1)) v++;
    let best = dp[mask & ~(1 << v)];
    for (const e of byLow[v]) if ((e & mask) === e) best = Math.max(best, 1 + dp[mask & ~e]);
    dp[mask] = best;
  }
  return dp[full];
}
function evaluate() {                          // called once per configuration
  let E = 0, edges = [], lineHasSimple = Array(D).fill(false);
  for (let P = 0; P < N; P++) {
    const m = cnt[P]; if (m === 0) continue;
    if (m >= 3) E += ((m - 1) * (m - 2)) / 2;
    if (m === 1) lineHasSimple[lowestBit(pmask[P])] = true;
    edges.push(pmask[P]);
  }
  const s = lineHasSimple.filter(Boolean).length, nu = matchingNumber(edges);
  record(size, E, s, nu);                       // |U| = size; |K'| = size - nu
}
function rec(d) {                              // depth-first over directions, maintaining cnt[] and pmask[]
  if (d === D) { evaluate(); return; }
  for (const b of (d === 0 || d === D - 1) ? [0] : [...Array(q).keys()]) {
    for (const P of lines[d][b]) { if (cnt[P]++ === 0) size++; pmask[P] |= 1 << d; }
    rec(d + 1);
    for (const P of lines[d][b]) { if (--cnt[P] === 0) size--; pmask[P] &= ~(1 << d); }
  }
}

// compute.js — computational checks (Node.js). Prints the tables of Appendix A.
const fs = require("fs");

// A.1 Sumsets in Z_p
function sumsetStats(p) {
  const N = 1 << p, minPlain = Array(p + 1).fill(Infinity), minRestr = Array(p + 1).fill(Infinity);
  const pc = (x) => { let c = 0; while (x) { c += x & 1; x >>= 1; } return c; };
  for (let m = 1; m < N; m++) {
    const A = []; for (let i = 0; i < p; i++) if (m >> i & 1) A.push(i);
    let plain = 0, restr = 0;
    for (const a of A) for (const b of A) { plain |= 1 << ((a + b) % p); if (a !== b) restr |= 1 << ((a + b) % p); }
    minPlain[A.length] = Math.min(minPlain[A.length], pc(plain));
    minRestr[A.length] = Math.min(minRestr[A.length], pc(restr));
  }
  return { minPlain, minRestr };
}

// A.2 Erdős–Ginzburg–Ziv: all multisets of 2n-1 residues mod n
function egz(n) {
  let total = 0, good = 0; const c = Array(n).fill(0);
  function check() {
    total++;
    let dp = Array.from({ length: n + 1 }, () => Array(n).fill(false)); dp[0][0] = true;
    for (let r = 0; r < n; r++) for (let t = 0; t < c[r]; t++)
      for (let j = n - 1; j >= 0; j--) for (let s = 0; s < n; s++) if (dp[j][s]) dp[j + 1][(s + r) % n] = true;
    if (dp[n][0]) good++;
  }
  (function rec(i, left) {
    if (i === n - 1) { c[i] = left; check(); return; }
    for (let v = 0; v <= left; v++) { c[i] = v; rec(i + 1, left - v); }
  })(0, 2 * n - 1);
  return { total, good };
}

// A.3 Cap sets in F_3^n: branch and bound
function capMax(n, timeLimitMs) {
  const N = 3 ** n, pts = [];
  for (let i = 0; i < N; i++) { const v = []; let x = i; for (let j = 0; j < n; j++) { v.push(x % 3); x = Math.floor(x / 3); } pts.push(v); }
  const idx = (v) => v.reduce((a, d, j) => a + d * 3 ** j, 0);
  const third = (i, j) => idx(pts[i].map((d, t) => (6 - d - pts[j][t]) % 3));
  let bestSize = 0, timedOut = false; const t0 = Date.now(), forb = new Int32Array(N), cur = [];
  function dfs(start) {
    if (Date.now() - t0 > timeLimitMs) { timedOut = true; return; }
    let cand = 0; for (let i = start; i < N; i++) if (forb[i] === 0) cand++;
    if (cur.length + cand <= bestSize) return;
    for (let i = start; i < N; i++) {
      if (forb[i] !== 0) continue;
      const added = []; for (const c of cur) { const t = third(i, c); forb[t]++; added.push(t); }
      cur.push(i); if (cur.length > bestSize) bestSize = cur.length;
      dfs(i + 1); cur.pop(); for (const t of added) forb[t]--;
      if (timedOut) return;
    }
  }
  dfs(0); return { bestSize, timedOut, ms: Date.now() - t0 };
}

// A.4 m_d and the constant c
function m3(n, d) {
  if (d < 0) return 0;
  let dp = Array(2 * n + 1).fill(0); dp[0] = 1;
  for (let i = 0; i < n; i++) { const nd = Array(2 * n + 1).fill(0);
    for (let s = 0; s <= 2 * n; s++) if (dp[s]) for (let a = 0; a <= 2; a++) if (s + a <= 2 * n) nd[s + a] += dp[s]; dp = nd; }
  let tot = 0; for (let s = 0; s <= Math.min(d, 2 * n); s++) tot += dp[s]; return tot;
}
const t0 = (Math.sqrt(33) - 1) / 8, c0 = (1 + t0 + t0 * t0) * Math.pow(t0, -2 / 3);

// A.5 Kakeya sets in F_q^2: one line per direction
function kakeya2(q) {
  const lines = [];
  for (let s = 0; s < q; s++) lines.push([...Array(q)].map((_, b) => [...Array(q)].map((_, t) => t * q + ((b + s * t) % q))));
  lines.push([...Array(q)].map((_, b) => [...Array(q)].map((_, t) => b * q + t)));
  let best = Infinity; const cnt = new Int32Array(q * q); let size = 0;
  (function rec(d) {
    if (d === lines.length) { best = Math.min(best, size); return; }
    if (size >= best) return;
    for (const pts of lines[d]) { for (const p of pts) if (cnt[p]++ === 0) size++; rec(d + 1); for (const p of pts) if (--cnt[p] === 0) size--; }
  })(0);
  return best;
}

for (const p of [5, 7, 11, 13, 17]) console.log(p, sumsetStats(p));
for (let n = 2; n <= 9; n++) console.log(n, egz(n));
for (let n = 1; n <= 4; n++) console.log(n, capMax(n, n === 4 ? 240000 : 60000));
for (let n = 1; n <= 12; n++) console.log(n, m3(n, Math.floor(2 * n / 3)), 3 * c0 ** n);
for (const q of [3, 5, 7]) console.log(q, kakeya2(q), (q * q + 2 * q - 1) / 2);