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. In 2010 Kopparty, Lev, Saraf and Sudan asked how fast the smallest such sets grow with n for a fixed field, for any pair (q, r) other than (2, 1), and noted that even q = r = 2 seemed non-trivial. Below, a short entropy argument answers this for q = 2 and every r: the growth base is exactly 2^(1 - 2^(-r)), and every rank-2 Kakeya set in F_2^n has at least 2^(3n/4) points. References to other theorems and sections point to the README in the repository, which also has the code and the tests that check every number here, and a short LaTeX note with the proof. The note and code were researched and written with AI agents working in MV2's name. The second part shows that the same argument works in every finite group: a set containing a translate of every r-dimensional cube of a group of order N needs at least N^(1 - 2^(-r)) elements.
11. Kakeya sets of rank r over F_2: the exact growth base (new in 1.5)
In their closing section KLSS write that "even the case q = r = 2 seems non-trivial": they knew no rank-2 Kakeya set in F_2^n smaller than the O(2^(3n/4)) given by 4-universal sets (sets containing a translate of every 4-point set), and they asked for lim K_r(n, q)^(1/n) "even for just one particular pair (q, r) != (2, 1)". For q = 2 the answer is the universal-set bound, for every r.
Theorem 7. Let n >= r >= 1. Every Kakeya set K of rank r in F_2^n has
|K| >= 2^((1 - 2^(-r)) n).
Corollary 6. beta_(2,r) = 2^(1 - 2^(-r)) for every r >= 1. More precisely, for all n >= r,
2^((1 - 2^(-r)) n) <= K_r(n, 2) < 2^((1 - 2^(-r)) n + r + 1),
where the upper bound is KLSS Corollary 11. In particular every rank-2 Kakeya set in F_2^n has at least 2^(3n/4) points, so the 4-universal sets are optimal up to a factor 8. In Theorem 6, g_(r,k) = (1 - 2^(-r)) k for q = 2: over F_2, blocks never help.
The proof is one entropy inequality.
Lemma 5. Let d_1, ..., d_r be independent and uniform on F_2^n, and let A be any random point of F_2^n (with any joint law with the d_i). For t in F_2^r put Y_t = A + t_1 d_1 + ... + t_r d_r. Then
sum over t in F_2^r of H(Y_t) >= (2^r - 1) n.
Proof. Induction on r; for r = 0 the claim is H(A) >= 0. Let r >= 1 and pair each t with t_1 = 0 with t + e_1. Since Y_(t + e_1) = Y_t + d_1, the pair (Y_t, Y_(t + e_1)) determines and is determined by (Y_t, d_1), so
H(Y_t) + H(Y_(t + e_1)) >= H(Y_t, d_1) = n + H(Y_t | d_1).
Adding over the 2^(r-1) pairs, the sum is at least 2^(r-1) n plus the sum over t with t_1 = 0 of H(Y_t | d_1). Given d_1 = delta, the vectors d_2, ..., d_r are still independent and uniform, and these Y_t are A + t_2 d_2 + ... + t_r d_r, so by induction that sum is at least (2^(r-1) - 1) n for every delta. In total the sum is at least (2^r - 1) n. QED
Proof of Theorem 7. For each tuple d = (d_1, ..., d_r) the span of the d_i has dimension at most r <= n, so it lies in an r-dimensional subspace, a translate of which lies in K. Let A = A(d) be a point with A + span(d_1, ..., d_r) inside K. Then every Y_t lies in K, so H(Y_t) <= log2 |K|, and Lemma 5 gives 2^r log2 |K| >= (2^r - 1) n. QED
Proof of Corollary 6. Theorem 7 and KLSS Corollary 11. For Theorem 6, apply Lemma 5 with n = k, the d_i the rows of U and A = P(U): this gives g_(r,k) >= (1 - 2^(-r)) k, and P = 0 attains it. QED
| r | KLSS lower bound 2^(r+1)/(2^r + 1) | beta_(2,r) = 2^(1 - 2^(-r)) |
|---|---|---|
| 1 | 1.3333 | 1.4142 (known: difference bases) |
| 2 | 1.6000 | 1.6818 |
| 3 | 1.7778 | 1.8340 |
| 4 | 1.8824 | 1.9152 |
(python f2_rank.py table prints this table.) For r = 1 Theorem 7 is the classical bound |K| >= 2^(n/2) for difference bases of F_2^n.
Why counting is not enough. A 2^r-universal set needs |K|^(2^r) >= (2^n - 1)(2^n - 2) ... (2^n - 2^r + 1), about 2^((2^r - 1) n), by counting: each of the C(2^n - 1, 2^r - 1) sets of 2^r points containing 0 has a translate in K, and a 2^r-point subset of K is a translate of at most 2^r of them. A rank-r Kakeya set has to contain far fewer configurations, and counting the tuples a, a + w_1, ..., a + w_r gives only base 2^(r/(r+1)) (1.5874 for r = 2, below the 1.6 of KLSS Theorem 1). Lemma 5 shows that over F_2 a rank-r Kakeya set must nevertheless be as large as a 2^r-universal set, up to the factor 2^(r+1). Section 12 shows that the same holds in every finite group.
Why only q = 2. Over F_q the same pairing, using one pair on each line in direction d_1 and keeping the other q - 2 points, gives sum over t of H(Y_t) >= (q^r - (q - 1)^r) n log2 q, so base q^(1 - (1 - 1/q)^r). For q >= 3 this is weaker than KLSS Theorem 1, because (q - 1)^(r-1) ln q >= 1. Over F_2 the lines have only two points, and nothing is lost.
Proposition 3 (small cases). K_(n-1)(n, 2) = 2^n - 1 for n >= 2, and K_(n-2)(n, 2) = 2^n - 3 for n >= 3.
Proof. Write K = F_2^n minus C. K has rank r exactly when, for every r-dimensional subspace W, C misses a coset of W, that is, the quotient map from F_2^n onto F_2^n / W is not onto on C. For r = n - 1 the quotient has two points: a set C = {x, y} maps onto it whenever x + y is not in W, which happens for some hyperplane W, and a single point never does. For r = n - 2 the quotient F_2^n / W has four points, so a C with at most 3 points is always fine. A C with 4 points, translated to {0, a, b, c}, maps onto F_2^2 under every linear map with a -> (1, 0), b -> (0, 1), c -> (1, 1); such a map exists whether a, b, c are independent or c = a + b, and its kernel has dimension n - 2. QED
So the smallest sets are far above the bound in small dimensions (K_2(4, 2) = 13 against 2^3 = 8): Theorem 7 is about the growth rate.
Checks. test_f2_rank.py checks: the subspace counts and coset partitions of F_2^n for n <= 5; the exact values K_r(n, 2) for every n <= 4 by exhaustive search (2, 3, 4, 5, 7, 8, 6, 13, 15 and 16 for (n, r) = (1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (4, 4)), each above the bound of Theorem 7 and below KLSS Corollary 11; Proposition 3 in F_2^5 for r = 4 and r = 3 (every complement of 1 or 3 points containing 0 is Kakeya, no complement of 2 or 4 points is); Lemma 5 for every deterministic A when (n, r) = (1, 1), (1, 2), (1, 3), (2, 1), and at the local minima of 128 descents from random starts for (2, 2), (1, 4), (2, 3), (3, 2), and on random laws of A; that A = 0 attains it; that the witnesses of the smallest sets put every Y_t in K; and every number quoted in this section. The case (n, r) = (2, 2) of Lemma 5 is the block question of Theorem 6 for q = r = 2 and k = 2: no map P on 2 x 2 matrices over F_2 has slice entropies adding up to less than 6.
Prior work. We searched (2026-10-15) for lower bounds on rank-r Kakeya sets over F_2 after KLSS: the papers citing it, Ellenberg-Oberlin-Tao, Dhar-Dvir-Lund (whose entropy formulation uses min-entropy and large q), and the universal-set paper of Alon, Bukh and Sudakov. KLSS prove their Theorem 1 with the polynomial method, and we found no better lower bound for q = 2 and r >= 2. If Theorem 7 is known, please open an issue and we will cite it.
12. Translates of cubes in any finite group (new in 1.6)
The proof of Lemma 5 uses one fact about F_2: the two points of a line differ by its direction. In any group the two ends of an edge of a cube differ by one generator, and the proof carries over. Alon, Bukh and Sudakov (ABS, 2009) posed the "universal set problem": given a family of finite sets, find the least size of a set that contains a translate of each of them. They call it "certainly hard in general" and ask for general conditions under which it can be solved. This section solves it, up to a logarithmic factor, for every family built from 0/1 combinations.
Let G be a finite group of order N, written multiplicatively (in an abelian group read a w as a + w). A pattern is a nonempty set T of 0/1 vectors of length r; m = |T| is its number of points. For d = (d_1, ..., d_r) in G^r put
w_t(d) = d_1^(t_1) d_2^(t_2) ... d_r^(t_r) (abelian: t_1 d_1 + ... + t_r d_r).
A set K in G is T-universal if for every d in G^r some left translate {a w_t(d) : t in T} lies in K. Let U_T(G) be the least size of a T-universal set. Examples:
- T = {0,1}^r: the images are the r-dimensional cubes {a + sum of d_i over i in S : S a subset of {1, ..., r}} (Hilbert cubes, when the d_i are nonzero). In F_2^n with n >= r the subset sums of d_1, ..., d_r are their span, so the T-universal sets are exactly the Kakeya sets of rank r.
- T = {0, e_1, ..., e_(m-1)}: the images are all sets {e, d_1, ..., d_(m-1)}, so the T-universal sets are the m-universal sets of ABS (a translate of every set of m elements).
- In F_2^n every set T of vectors of F_2^r is a pattern, so every linear configuration {t_1 d_1 + ... + t_r d_r : t in T} is covered.
Lemma 6. Let d_1, ..., d_r be independent and uniform on G, let A be any random element of G (with any joint law with the d_i), and put Y_t = A w_t(d). Then for every pattern T of length r,
sum over t in T of H(Y_t) >= (|T| - 1) log2 N.
Proof. Induction on r; for r = 0 the pattern has one point and the claim is H(A) >= 0. Let r >= 1. Call t in T paired if t_r = 0 and t + e_r is in T too, and let p be the number of paired t. For paired t, Y_(t + e_r) = Y_t d_r, so (Y_t, Y_(t + e_r)) and (Y_t, d_r) determine each other and
H(Y_t) + H(Y_(t + e_r)) >= H(Y_t, d_r) = log2 N + H(Y_t | d_r).
Every other t in T has H(Y_t) >= H(Y_t | d_r). Let R be T without the vectors t + e_r of the pairs. Then
sum over t in T of H(Y_t) >= p log2 N + sum over t in R of H(Y_t | d_r),
and dropping the last coordinate maps R one-to-one onto a pattern T' of length r - 1 with |T| - p points. Condition on d_r = delta. For t in R, Y_t = A w_(t')(d') delta^(t_r), where t' and d' drop the last coordinate. Right multiplication by the fixed element delta^(t_r) is a bijection of G, so H(Y_t | d_r = delta) = H(A w_(t')(d') | d_r = delta). Given d_r = delta, d_1, ..., d_(r-1) are still independent and uniform, so by induction these terms add up to at least (|T| - p - 1) log2 N for every delta. In total the sum is at least (|T| - 1) log2 N. QED
Equality holds, for example, for A = w_s(d)^(-1) with s in T: then Y_s is the identity, and for t != s, Y_t = w_s(d)^(-1) w_t(d) is uniform (given the other d_i, it is a bijective function of d_j for the last j with s_j != t_j). For G = F_2^n and T = F_2^r, Lemma 6 is Lemma 5.
Theorem 8. For every finite group G of order N and every pattern T with m points,
N^(1 - 1/m) <= U_T(G) <= min( N, 2 N^(1 - 1/m) (m^2 (m ln N + 1))^(1/m) ).
So U_T(G) = N^(1 - 1/m + o(1)) as N grows: the answer depends only on the number of points of the pattern, not on the relations between them.
Proof of the lower bound. Take d uniform on G^r and let A(d) be an element with A(d) w_t(d) in K for every t in T. Every Y_t lies in K, so H(Y_t) <= log2 |K|, and Lemma 6 gives m log2 |K| >= (m - 1) log2 N. QED
Proposition 4 (upper bound). If m <= N, some set of fewer than 2 N^(1 - 1/m) (m^2 (m ln N + 1))^(1/m) elements contains a left translate of every m-element subset of G, and so of every image of every pattern with m points.
Proof. The standard random construction (ABS give sharper ones for many groups). Put each element in K independently with probability p, where p^m = m^2 (m ln N + 1)/N; if p >= 1 take K = G. Fix a set S of m elements. Two left translates g S and h S meet only if g^(-1) h lies in S S^(-1), which has at most m^2 elements, so we can pick at least N/m^2 pairwise disjoint translates. Each lies in K with probability p^m, independently, so S has no translate in K with probability at most exp(-p^m N/m^2) = e^(-1) N^(-m). There are at most N^m sets S, so with probability at least 1 - e^(-1) all of them have a translate in K. By Markov's inequality |K| < 2 p N with probability greater than 1/2, and 1 - e^(-1) + 1/2 > 1. Every image of a pattern with m points has at most m elements, so it lies in an m-element set. QED
Corollary 7 (cubes). Every set containing a left translate of every r-dimensional cube {d_1^(t_1) ... d_r^(t_r) : t in {0,1}^r} of G has at least N^(1 - 2^(-r)) elements, and if 2^r <= N some such set has fewer than 2 N^(1 - 2^(-r)) (4^r (2^r ln N + 1))^(2^(-r)). For G = Z_N and r = 2: a set containing a translate of every {a, a + x, a + y, a + x + y} has at least N^(3/4) elements, and N^(3/4 + o(1)) elements suffice. For G = F_2^n this is Theorem 7 again.
Corollary 8 (every linear pattern over F_2). For every set T of m vectors of F_2^r, the least set in F_2^n containing a translate of {t_1 d_1 + ... + t_r d_r : t in T} for every d_1, ..., d_r has between 2^((1 - 1/m) n) and 2^((1 - 1/m) n + O_m(log n)) points; its growth base is 2^(1 - 1/m). Linear relations among the points of a configuration never make it cheaper to contain a translate of every copy.
Why this beats counting. A set K containing a translate of every r-cube contains at least N^r cubes (one for each d), and a cube inside K is determined by its elements a, a d_1, ..., a d_r, so N^r <= |K|^(r+1) and |K| >= N^(r/(r+1)). A subgroup of order N^(r/(r+1)) (when there is one) contains exactly N^r cubes, so no argument that only counts cubes can do better. Lemma 6 also uses that the d whose cubes K must contain are all of G^r, each once. The exponents of N:
| r | counting cubes: r/(r+1) | Theorem 8: 1 - 2^(-r) |
|---|---|---|
| 1 | 0.5 | 0.5 |
| 2 | 0.6667 | 0.75 |
| 3 | 0.75 | 0.875 |
| 4 | 0.8 | 0.9375 |
(python cubes.py table prints this table.) For m-universal sets the counting bound of ABS, |U| >= (1/2) N^(1 - 1/m), is already of the right order; there Theorem 8 only removes the factor 1/2. Its gain is for patterns with linear relations, such as cubes and subspaces, where counting fails.
Where the method stops. The proof needs coefficients 0 and 1: the two points of each pair must differ by a single d_r. For a progression {a, a + d, a + 2d} it gives only |K| >= N^(1/3). For k-term progressions in Z_p this is a Kakeya-type problem; ABS recall Bourgain's observation that strong lower bounds there would imply the Euclidean Kakeya conjecture, and it stays open. Over F_q with q >= 3, a Kakeya set of rank r must contain the images of all of F_q^r, and section 11 shows that the pairing is weaker than KLSS there.
Checks. test_cubes.py builds 25 groups of order at most 16: the cyclic groups Z_2, ..., Z_16; F_2^2, F_2^3, F_2^4, Z_3 x Z_3, Z_2 x Z_4, Z_4 x Z_4, Z_2 x Z_8 and Z_2 x Z_2 x Z_4; and the non-abelian S_3 and S_3 x Z_2. It checks: the group axioms; Lemma 6 for every deterministic base point and every pattern in {0,1}^r when (G, r) is (Z_3, 2), (Z_2, 3) or (Z_2, 2), and for r = 1 in Z_4, Z_5, S_3 and F_2^2, where the minimum is exactly (|T| - 1) log2 N; the equality case; local minima from random starts for patterns in Z_4, Z_5, S_3 and F_2^2 with r = 2 and in Z_3 with r = 3; Theorem 8 for 2-cubes, by an exhaustive search for the least cube-universal set in all 25 groups, and for 3-point sets in the groups of order at most 12; that the least 2-cube-universal sets of F_2^2, F_2^3 and F_2^4 have 4, 7 and 13 elements, the values K_2(n, 2) of section 11; that the search's tester agrees with the definition on random sets; and every number quoted here.
Prior work. We searched (2026-10-15) for lower bounds on sets containing a translate of every Hilbert cube, or of every copy of another configuration with linear relations, and found none. The work on Hilbert cubes we found (for example Cilleruelo, arXiv 1310.1646) is about sets that contain no cube, and ABS bound k-universal sets by counting. The argument is elementary, so it may be known; if so, please open an issue and we will cite it.
Licence
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.
Top comments (0)