Kakeya sets of higher rank over a fixed finite field: the second-order term

This is a new result from MV2's open notebook on Kakeya sets over small finite fields (https://github.com/munimtechnologies/kakeya-small-fields). A Kakeya set of rank r in F_q^n contains a translate of every r-dimensional subspace. For a fixed field and growing n the smallest such sets grow like beta(q,r)^n, and Kopparty, Lev, Saraf and Sudan asked in 2010 for this growth base. Below we show that beta(q,r) = q - q^(2-r) + O(q^(1-r) log q), with constructions smaller than theirs for every q >= 3 and r >= 2. References to other sections, lemmas and theorems point to the README in the repository, which also has the code and the tests that check every number here. The note and code were researched and written with AI agents working in MV2's name.

A Kakeya set of rank r in F_q^n contains a translate of every r-dimensional subspace; rank 1 is the usual Kakeya set. Let K_r(n, q) be the least size of one (n >= r). If K1 and K2 have rank r, so does K1 x K2: the projection of an r-dimensional subspace D of F_q^(n1+n2) to each factor lies in an r-dimensional subspace of that factor, whose translate the factor contains, and the product of the two translates contains a translate of D. So

beta_(q,r) = lim K_r(n, q)^(1/n)

exists. KLSS (section 6 of their paper) note that for r >= 2 "there is no reason to believe" their bounds are sharp, and ask for this limit for any single pair (q, r) other than (2, 1). Their bounds for fixed q and growing n are

In this section R is the number of blocks (it was called r in sections 3 and 6).

Theorem 5. For a function f : F_q^r -> F_q let

Phi(f) = (1/q^r) * sum over t in F_q^r of H(f(U) + <t, U>),    U uniform on F_q^r.

Then beta_(q,r) <= 2^Phi(f).

Proof. Section 3 with columns in place of symbols. Let n = R m, cut F_q^n into R blocks of m coordinates, and let K = { x : sum over j of log2 N(x^(j)) <= T } with T = R m Phi(f) + m log2(q) sqrt(R r ln q). Let D be an r-dimensional subspace with basis d_1, ..., d_r, and for each coordinate c let u_c = (d_1c, ..., d_rc) in F_q^r be its column. For b_j and s_j in F_q^r, let a have coordinate f(u_c - b_j) + <s_j, u_c> for c in block j. The point a + t_1 d_1 + ... + t_r d_r has coordinate f(u_c - b_j) + <s_j + t, u_c>, so the symbol distribution of its block j is the law of f(Y - b_j) + <s_j + t, Y>, where Y is a uniformly chosen column of block j. Write Phi_f(tau) for Phi computed with U ~ tau. Then f(Y - b) + <s, Y> is a translate of f(Z) + <s, Z> with Z = Y - b, and the laws of Y - b average, over the q^r values of b, to the uniform law. Phi_f is concave in tau, so some b_j makes the average over s of H(f(Y - b_j) + <s, Y>) at most Phi(f). With that b_j, the cost log2 N of block j is at most m times this entropy (Lemma 1), so its mean over a uniform shift s_j is at most m Phi(f). Hoeffding's inequality with M = m log2 q and a union bound over the q^r points t, as in Lemma 3, give shifts that put all of a + D in K. Finally |K| <= C(m + q - 1, q - 1)^R 2^T, and m about n^(1/3) gives beta_(q,r) <= 2^Phi(f). QED

Corollary 4 (three witnesses).

  beta_(q,r) <= q * 2^(-(q-1)/q^r).
Phi = log2 q - D(q)/q^r,    D(q) = q^2 log2(1 + 1/q) - log2(q + 1).

The square wins for q = 3, 4, 5 (deficit q - 1 against D(3) = 1.735, D(4) = 2.83, D(5) = 3.99), and the norm form wins for every q >= 7 (D(7) = 6.440 against 6). Both beat KLSS for every q >= 3 and r >= 2: (b) because q - 1 > log2 q, and Theorem 4 of KLSS is weaker still. For q = 2 all three give at best 2^(3/4) at r = 2, the value KLSS already had, and section 11 shows that no construction does better.

For rank 3 over F_3 the three numbers are 2.7931, 2.8804 and 2.8499. python higher_rank.py table prints these for r = 2, 3, 4.

Corollary 5 (the second-order term). For every q and every r >= 2,

q - q^(2-r) + q^(1-r)  <=  beta_(q,r)  <=  q - q^(2-r) + (1 + ln(q + 1)) q^(1-r).

So beta_(q,r) = q - q^(2-r) + O(q^(1-r) log q), and in particular beta_(q,2) = q - 1 + O((log q)/q). Before, the best upper bound was q^(1 - q^(-r)) = q - (ln q) q^(1-r) + ..., which does not show the term -q^(2-r) at all.

Proof. Lower: q / (1 + x) >= q (1 - x) with x = (q - 1)/q^r. Upper: by Corollary 4(c), beta_(q,r) <= q e^(-y) with y = (ln 2) D(q)/q^r = (q^2 ln(1 + 1/q) - ln(q + 1))/q^r, and q e^(-y) <= q (1 - y + y^2/2). Since ln(1 + 1/q) >= 1/q - 1/(2q^2), q y >= (q - 1/2 - ln(q + 1)) q^(1-r); since y <= q^(1-r), q y^2/2 <= q^(3-2r)/2 <= q^(1-r)/2. QED

Proposition 1 (the limit of one-coordinate witnesses). Every f has Phi(f) >= log2 q - log2(1 + (q - 1)/q^r), which is the logarithm of the KLSS lower bound.

Proof. Two different columns u, v collide in slice t exactly when <t, u - v> = f(v) - f(u), which holds for exactly q^(r-1) values of t. So the collision probabilities of the q^r slices add up to 1 + q^(r-1) - 1/q, and their average is (1 + (q - 1)/q^r)/q. Each slice has entropy at least minus the log of its collision probability, and -log2 is convex. QED

So one-coordinate witnesses cannot go below the known lower bound, and Corollary 5 shows they come within O(q^(1-r) log q) of it. Narrowing the rest of the gap needs blocks, by the next theorem.

Theorem 6 (exact formula). Let g_(r,k) be the least value of (1/q^r) sum over t in F_q^r of H(P(U) + t U) over maps P : F_q^(r x k) -> F_q^k, where U is a uniform r x k matrix and t a row vector. Then beta_(q,r) = inf over k of 2^(g_(r,k)/k), and g_(r,1) is the least Phi.

Proof. As for Theorem 2. Putting maps side by side gives g_(r,k+l) <= g_(r,k) + g_(r,l). The construction of Theorem 5 over the alphabet F_q^k (letters are r x k blocks of columns) gives beta_(q,r) <= 2^(g_(r,k)/k). For k >= r, a rank-r Kakeya set K0 in F_q^k gives a map with every P(U) + t U in K0: the row space of U lies in some r-dimensional subspace, and P(U) is a point of a translate of that subspace inside K0. So g_(r,k) <= log2 K_r(k, q), and the infimum is at most beta_(q,r) by Fekete's lemma. QED

Proposition 2 (q = 3, r = 2). The least Phi over all f : F_3^2 -> F_3 is log2 3 - 2/9, attained by u_1^2. So 2.5717 is the best that one-coordinate witnesses give for rank-2 Kakeya sets over F_3, and going lower needs blocks (k >= 2 in Theorem 6). Among the f whose nine slices all take all three values, the norm form is best.

Proof. Write Delta_t = log2 3 - H(slice t); we show sum over t of Delta_t <= 2. A slice has counts (s_0, s_1, s_2) adding up to 9, and by the proof of Proposition 1 its pair count C_t = sum of C(s_i, 2) satisfies sum over t of (C_t - 9) = 3 * 36 - 81 = 27. A slice t misses a value if f(u) != c_t - <t, u> for all u.

(i) If three slices t_1, t_2, t_3 miss values, then at every u at most two of the three forbidden values c_i - <t_i, u> differ. Two of them agree on a line of F_3^2, so the three lines of agreement cover all nine points, are parallel, and the t_i lie on a line t_0 + F_3 v. Then f(u) + <t_0, u> is the value not forbidden at u, which depends only on <v, u>, and the slices are those of a one-variable map plus a uniform part, so the sum is at most 2 by section 4. A fourth such slice is impossible, since a line of F_3^2 has three points.

(ii) If exactly two slices miss values, a change of variables (adding a linear function and a constant to f, translating u, a linear map) makes them t = (0, 0) and (1, 0), both missing 0. Then f(u) = u_1 whenever u_1 != 0, and f(0, u_2) = g(u_2) in {1, 2} with g not constant (otherwise a third slice misses a value). The slices (0, 0) and (1, 0) have counts {5, 4, 0} (Delta = 0.5939 each), (2, 0) has {6, 2, 1} (Delta = 0.3606), and the six slices with t_2 != 0 have {4, 3, 2} or {3, 3, 3} (Delta <= 0.0545). The sum is at most 1.8752.

(iii) If at most one slice misses a value: among count patterns with all three values present, Delta_t / (C_t - 9) is largest for {4, 4, 1} (0.1928/3 = 0.0643), so with no missing value the sum is at most 27 * 0.0643 = 1.7353, which the norm form attains with nine {4, 4, 1} slices. With one missing slice the sum is at most Delta + 0.0643 (27 - (C - 9)) over the patterns {5, 4, 0}, {6, 3, 0}, {7, 2, 0}, {8, 1, 0}, {9, 0, 0}, and the largest of these is 1.8793. QED

For q = 2 the same question has the answer 3/4 (eight of the 16 functions are affine and give 3/4, the other eight give H(1/4) = 0.8113), so for q = r = 2, the case KLSS single out, one-coordinate witnesses give nothing beyond their 2^(3n/4). By section 11, neither does anything else.

Checks. test_higher_rank.py builds the fields F_q for q <= 16 and checks: the slice laws of the norm form; the closed forms of Corollary 4 against direct computation for r = 1, 2 (all ten fields) and r = 3 (q <= 5); the collision count and the floor of Proposition 1 on the witnesses and on random f; the translation step of Theorem 5 on random column laws; Theorem 5 with one block on every plane of F_3^4, F_2^5 and F_4^3 (130, 155 and 21 planes): some translate of the witness gives a flat whose points have average log2 N at most n Phi(f); Corollary 5 and the comparison with KLSS for q up to 64 and r = 2, 3, 4; and every number quoted in this section.

Prior work. We searched (2026-10-15) for constructions of rank-r Kakeya sets over a fixed field after KLSS. Dhar, Dvir and Lund (2019) still cite KLSS Theorem 4 as the construction for this case, and we found nothing better. We could not read K. Cong's 2021 MIT RSI report on Furstenberg sets over finite fields, which includes constructions. If any of this is known, please open an issue.

Text CC BY 4.0; code Apache-2.0 (see LICENSE). By MV2 of Munim, Inc.; researched and written with AI agents working in his name.