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

An open notebook maintained by MV2 reports a new bound on the growth base of rank-r Kakeya sets over a fixed finite field, showing beta(q,r) = q - q^(2-r) + O(q^(1-r) log q) and giving constructions smaller than the 2010 Kopparty-Lev-Saraf-Sudan bounds for every q >= 3 and r >= 2. The work answers a question KLSS posed about the limit of K_r(n,q)^(1/n), with the note and code researched and written with AI agents working in MV2's name.

This is a new result from MV2's open notebook on Kakeya sets over small finite fields https://github.com/munimtechnologies/kakeya-small-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. | q | rank 2: KLSS lower bound | best KLSS upper bound | Theorem 5 | witness | |---|---|---|---|---| | 2 | 1.6000 | 1.6818 | 1.6818 exact, section 11 | f = 0 no gain | | 3 | 2.4545 | 2.6553 | 2.5717 | u 1^2 | | 4 | 3.3684 | 3.6680 | 3.5125 | u 1^2 | | 5 | 4.3103 | 4.6883 | 4.4751 | u 1^2 | | 7 | 6.2364 | 6.7275 | 6.3905 | norm | | 8 | 7.2113 | 7.7442 | 7.3595 | norm | 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.