This is from MV2's open notebook on Kakeya-type problems (https://github.com/munimtechnologies/kakeya-small-fields). An earlier post showed that a set in a finite group of order N that contains a translate of every r-dimensional cube needs at least N^(1 - 2^(-r)) elements. Here the set only has to serve a family D of r-tuples. In abelian groups it still needs |D|^((1 - 2^(-r))/r) elements, and that is sharp. In non-abelian groups this can fail, and the loss can be measured exactly, by a fibre count that is at most the largest conjugacy class. References to theorems point to finite-groups.md in the repository, which also lists the exact computer checks. The note and code were researched and written with AI agents working in MV2's name, and no human mathematician has checked the proofs.
A. Abelian groups
Theorem 9. Let G be a finite abelian group, r >= 1, d any random element of G^r and A any random element of G (with any joint law), and Y_t = A + t_1 d_1 + ... + t_r d_r. Then
sum over t of H(Y_t) >= ((2^r - 1)/r) H(d).
Corollary 9. If K contains a translate of the cube of every d in D, then |K| >= |D|^(e_r). With |D| = delta N^r this is |K| >= delta^(e_r) N^(1 - 2^(-r)).
Proof. Step 1 (peeling in any order sigma): sum_t H(Y_t) >= sum_i 2^(i-1) H(d_sigma(i) | d_sigma(i+1), ..., d_sigma(r)). To see this, peel j = sigma(r) first: the pairs (t, t + e_j) give H(d_j) + H(Y_t | d_j), and then induct on the face t_j = 0 given d_j. Step 2: the right-hand side equals H(d) + sum_(i=2..r) 2^(i-2) H(d_(S_i)) with S_i = {sigma(i), ..., sigma(r)}. Step 3: average over sigma. Han's inequality gives E H(d_(S_i)) >= (|S_i|/r) H(d), and r + sum_(j=0..r-2) 2^j (r - 1 - j) = 2^r - 1. For the corollary, take d uniform on D; every Y_t lies in K. QED
Sharpness: equality holds for d uniform on G^r. D = H^r for a subgroup H shows that the exponent of |D| is best possible, and D = {0} shows that the power of delta is best possible. The Kakeya form over F_2: a set containing a translate of every subspace in a family F of r-dimensional subspaces has at least (|F| |GL_r(F_2)|)^(e_r) points.
B. Every finite group: the counting bound
Proposition 5. (a) In every finite group, if K serves every d in D then |D| <= |K|^(r+1), so |K| >= |D|^(1/(r+1)). (b) This is sharp up to a factor 2: in G = AGL(1, q) = {x -> a x + b}, with H = {x -> a x} and K = H u tH (t: x -> x + 1), |K| = 2(q - 1) and K serves D = G x H^(r-1), so |D| = q (q - 1)^r.
Proof. (a) d -> (A, A d_1, A d_1 d_2, ..., A d_1 ... d_r) maps D one-to-one into K^(r+1), since d_i is the quotient of consecutive entries. (b) KH = K. Also K^(-1) K = G: given (u, v), if v = 0 take b = e = 0 and c = a u; if v != 0 take b = 0, e = 1, a = 1/v and c = u/v. So for d = (g, h_2, ..., h_r) pick k, k' in K with k^(-1) k' = g and put A = k. QED
So Theorem 9 fails in AGL(1, q). The failure condition is 2^(r 2^r) (q - 1)^r < q^(2^r - 1), and the least primes where it holds are q = 257 (r = 2), 67 (r = 3), 59 (r = 4), 73 (r = 5) and 107 (r = 6). For example, at q = 257, |K| = 512 < |D|^(3/8) = 512.75.
| r | abelian groups (Theorem 9) | every finite group (Proposition 5) |
|---|---|---|
| 1 | 1/2 | 1/2 |
| 2 | 3/8 = 0.375 | 1/3 |
| 3 | 7/24 = 0.2917 | 1/4 |
| 4 | 15/64 = 0.2344 | 1/5 |
C. Nilpotent groups also fall below the abelian exponent
Proposition 6. (a) Let L <= G, y in G with yLy^(-1) != L, and I = L n yLy^(-1). Then K = L u yL serves D = LyL x L^(r-1), with |K| = 2|L| and |D| = |L|^(r+1)/|I|. (b) (Class 2.) Let G(p, k) be the set of triples (e, h, z), with e in Z_p and h, z in F_p^k, under (e, h, z)(e', h', z') = (e + e', h + h', z + z' + e h'). This group has order p^(2k+1), its centre equals G' = {(0, 0, z)}, and so it has class 2 (G(2, 1) = D_4). Let H = {(0, h, 0)}, choose S in Z_p with S - S = Z_p (|S| = 2 for p = 2, 3; 3 for p = 5, 7), and let K = {(t, h, t h) : t in S}. Then K serves D = (G minus HZ) x H^(r-1), with |K| = |S| p^k and |D| = (p - 1) p^(k(r+1)). (c) (Direct powers.) In G^m take L^m and the diagonal y. With lambda = log|I| / log|L|, the abelian bound fails for large m if and only if lambda < t_r := (2^r - 1 - r)/(2^r - 1) (t_2 = 1/3, t_3 = 4/7, t_4 = 11/15).
Proof. (a) Write d_1 = l y l' with l, l' in L and take A = l^(-1). Then A d_1 = y l' is in yL, and every cube point is A h or A d_1 h with h in L. Also |LyL| = |L|^2/|I|. (b) KH = K, and (t, h, th)^(-1)(t', h', t'h') = (t' - t, h' - h, (t' - t) h'), so K^(-1) K contains every (j, *, *) with j != 0. (c) |K| = 2|L|^m and |D| = (|L|^(r+1)/|I|)^m, so |K| / |D|^(e_r) -> 0 if and only if e_r (r + 1 - lambda) > 1. QED
In (b), Theorem 9 asks for |S|^(r 2^r) >= (p - 1)^(2^r - 1) p^(k(2^r - r - 1)), which fails for large k. The least k where it fails:
r = 2: k = 9, 4, 3, 2 for p = 2, 3, 5, 7 (p = 7, k = 2: |K| = 147 < |D|^(3/8) ~ 156.0)
r = 3: k = 7, 3, 3, 2 for p = 2, 3, 5, 7 (3^7 = 2187 is the smallest group in the family)
r = 4: k = 6 for p = 2
For fixed p, |K| ~ |S| |D|^(1/(r+1)) in this family, so the exponent 1/(r+1) of Proposition 5 is reached up to a constant in nilpotent groups too. In (c), S_3 with L = <(12)> and y = (13) has lambda = 0 and fails for r = 2 from S_3^9 on.
Corollary 10. For a finite group G the following are equivalent: (i) G is abelian; (ii) for every r and m, all K, D in G^m satisfy |K| >= |D|^(e_r); (iii) for every r there is a C_r > 0 such that all K, D in every G^m satisfy |K| >= C_r |D|^(e_r).
Proof. (i) => (ii) is Theorem 9, and (ii) => (iii) is trivial. For (iii) => (i), suppose G is not abelian. A non-abelian Dedekind group is Q_8 x E x A, and its square contains Q_8 x Q_8, where <(i, j)> is not normal; so G or G^2 has a non-normal subgroup L, and then lambda < 1. Choose r with t_r > lambda and apply Proposition 6(c). QED
D. How much non-commutativity costs
The proof of Theorem 9 pairs Y_t with Y_(t + e_j). In a non-abelian group the partner is Y_t c, where c = s^(-1) d_j s is the conjugate of d_j by the product s of the later factors that are "on". Such a pair is exact when [d_j, s] = 1 and otherwise loses a little. For an index j, a set T of indices > j and a tuple d, put s_T = prod_(i in T) d_i (in increasing order) and c_(j,T) = s_T^(-1) d_j s_T. The fibre count of a family D is
beta_(j,T)(D) = max over c of |{d_j : d in D, c_(j,T)(d) = c}|.
Given c, the map d_j -> [d_j, s_T] = d_j^(-1) c is one-to-one, and d_j lies in the conjugacy class of c. So
beta_(j,T) <= min( |{[d_j, s_T] : d in D}|, |pi_j(D)| ) <= b(G) <= |G'|.
Multiplying G by an abelian group (and D by any family there) does not change beta.
Theorem 10 (peeling with fibre losses). For every finite group G, every random (A, d) and every order sigma of {1, ..., r},
sum_t H(Y_t) >= H(A, d) + sum_(m<r) (2^(r-m) - 1) H(x_m | x_1, ..., x_(m-1))
- sum over the lossy pairs of H(d_j | c_(j,T)),
where x_m = d_(sigma(m)) is the m-th generator peeled. A pair is lossy when j is peeled while some unpeeled i > j is on (T is the set of those i). For r = 3 the orders 321, 312, 231, 213, 132 and 123 have 0, 1, 2, 3, 3 and 4 lossy pairs. Here "321" peels d_3 first and is lossless.
Proof. At a stage conditioned on the generators F already peeled, a pair (Y, Yc) satisfies H(Y|F) + H(Yc|F) >= H(Y, c|F) >= H(Y, d_j|F) - H(d_j | Y, c, F) >= H(Y, d_j|F) - H(d_j | c), and H(Y, d_j|F) = H(d_j|F) + H(Y | d_j, F) is the lossless term. Continue on the face t_j = 0 given (F, d_j). The last step gives H(A, x_r | x_1..x_(r-1)), so the total starts with H(A, d). QED
With d uniform on D, H(d_j | c_(j,T)) <= log beta_(j,T). Bounding every loss by log|G'| gives the crude form |K| >= (|D|^(1/r)/|G'|)^(1 - 2^(-r)).
Lemma 7 (the cube is two-sided). Put w_i = A d_i A^(-1). Then A d_1^(t_1) ... d_r^(t_r) = w_1^(t_1) ... w_r^(t_r) A, so flipping t_r is right multiplication by d_r and flipping t_1 is left multiplication by w_1. Peeling "outside in" (at each step either the last remaining d on the right or the first remaining w on the left) loses nothing. For every random (A, d) in every finite group,
sum_t H(Y_t) >= H(A, d) + sum_(i=1..r-1) (2^(r-i) - 1) H(x_i | x_1, ..., x_(i-1))
for each of the 2^(r-1) outside-in sequences x. For r = 2 this reads sum >= H(A, d) + max(H(d_2), H(w_1)). Proof. All faces used contain the base point, so the word stays valid. The last pair gives H(A, x_r | x_<r), and (A, x_1, ..., x_r) determines (A, d). QED
Theorem 11 (r = 2). For every finite group G and random (A, d_1, d_2), with c = d_2^(-1) d_1 d_2,
sum_t H(Y_t) >= H(d) + max( H(d_2), H(d_1) - H(d_1 | c) ) >= (3/2) H(d) - (1/2) H(d_1 | c).
So if K serves every pair in D, then
|K|^8 beta_(1,2)(D) >= |D|^3, and in particular |K|^8 b(G) >= |D|^3, |K|^8 |G'| >= |D|^3.
The exponent 1/8 of the loss cannot be lowered: in G(p, k) (Proposition 6(b)) with b = |G'| = p^k, |K| / (|D|^(3/8) |G'|^(-1/8)) = |S| / (p - 1)^(3/8) for every k (exactly 2 for p = 2). In AGL(1, q), b = |G'| = q and the ratio tends to 2.
Proof. Theorem 10 with the orders 21 (lossless: H(d) + H(d_2)) and 12 (one lossy pair, which loses H(d_1 | c)). Average the two and use H(d_1) + H(d_2) >= H(d). A second proof uses Lemma 7: H(w_1) >= H(d_1) - log b, because d_1 = A^(-1) w_1 A is conjugate to w_1. QED
Theorem 12 (r = 3). For every finite group G,
|K|^24 beta_(1,2) beta_(1,3)^2 beta_(1,23) beta_(2,3)^2 >= |D|^7,
so |K|^24 b(G)^6 >= |D|^7, i.e. |K| >= |D|^(7/24) b(G)^(-1/4). Within "mix peeling orders and charge each lossy pair at most log b", the loss exponent 1/4 is optimal.
Proof. Average the orders 321, 213 and 132 with weight 1/3 each. They form a Latin square: each index appears once in each position. Weighted Shearer gives a main term of (7/3) H(d). The losses are 2 H(d_2|c_(2,3)) + H(d_1|c_(1,3)) for 213 and H(d_1|c_(1,2)) + H(d_1|c_(1,3)) + H(d_1|c_(1,23)) for 132. Optimality is a linear program over the six orders. Shearer's main term for all laws needs coverage 3 p_i + q_i = 4/3 for each index, and the dual vector y = (15/14, 9/14, -3/14) satisfies 3 y_(s1) + y_(s2) <= L(sigma) for all six orders, with value 2. QED
General r: the same LP gives the least average number lam_r of lossy pairs, so |K| >= |D|^(e_r) b(G)^(-lam_r / 2^r). Solved exactly with dual certificates:
| r | lam_r | loss exponent lam_r / 2^r | uniform order l_r / 2^r | lower limit (r+1) e_r - 1 |
|---|---|---|---|---|
| 2 | 1/2 | 1/8 | 1/8 | 1/8 |
| 3 | 2 | 1/4 | 13/48 | 1/6 |
| 4 | 23/4 | 23/64 | 77/192 | 11/64 |
| 5 | 72/5 | 9/20 | 973/1920 | 13/80 |
| 6 | 67/2 | 67/128 | 2263/3840 | 19/128 |
| 7 | 522/7 | 261/448 | 35101/53760 | 15/112 |
Here l_r = 2^r - 1 - sum_(k=1..r) (2^k - 1)/k is the uniform average over orders. For a uniform order the Lehmer-code entries X_j are independent and uniform on {0..j-1}, so E 2^(X_j) = (2^j - 1)/j. The last column comes from Theorem 13's examples: no bound with a smaller loss exponent can hold.
Theorem 13 (when the later generators commute). If d_2, ..., d_r commute pairwise for every d in D, then
sum_t H(Y_t) >= ((2^r - 1)/r) H(d) - ((2^r - 1 - r)/r) log b(G),
so |K| >= |D|^(e_r) b(G)^(-((r+1) e_r - 1)). For r = 3 this is |K|^24 b^4 >= |D|^7 (exponent 1/6). The exponent (r+1) e_r - 1 is sharp for every r: in G(p, k) with D as in Proposition 6(b), |K| / bound = |S| / (p - 1)^(e_r) for every k. In AGL(1, q) with D = G x H^(r-1), the ratio tends to 2.
Proof. Only pairs that peel d_1 can lose. If d_1 is peeled at position pos, there are 2^(r - pos) - 1 of them. Averaging over all r! orders (pos is uniform) gives (2^r - 1 - r)/r lossy pairs. The main term is Han's inequality as in Theorem 9. QED
In G(p, k) every order's inequality is tight, and every pair whose commutator can be non-trivial loses the full log|G'|. For r = 3 the excesses over 8 log|K| are (0, k, 0, k, 3k, 3k) for (321, 312, 231, 213, 132, 123), in units of log p. So losses cannot be charged per distinct commutator. In order 132 the three stage-1 pairs lose k each, although the two commutators [d_1, d_2] and [d_1, d_3] carry only 2k together.
Proposition 7 (coset designs). Let L be any subgroup, K = S L a union of |S| left cosets, and D a subset of (K^(-1) K) x L^(r-1). Every such d is served. Then |K|^(r 2^r) b(G)^(2^r - 1 - r) >= |D|^(2^r - 1). Since G(p, k) and AGL(1, q) are coset designs, this is sharp.
Proof. For l in L, l g L = (l g l^(-1)) L, so L g L is a union of at most |g^G| <= b left L-cosets, and |L g L| <= |L| min(|L|, b). So |D| <= |S|^2 |L|^r m with m = min(|L|, b), and m^(2^r - 1) <= |L|^r b^(2^r - 1 - r). QED
Proposition 8 (b(G) is sharp where |G'| is not). Let Gamma(p; j, k) be F_p^j x F_p^k x (F_p^j (x) F_p^k) with (e, h, z)(e', h', z') = (e + e', h + h', z + z' + e (x) h'). Then |G'| = p^(jk) and b = p^(j+k-1). For j = 2, S = {0, e_1, e_2}, H = {(0, h, 0)}, K = {(t, h, t (x) h) : t in S} and D = (K^(-1) K) x H^(r-1), we get |K| = 3 p^k and |K^(-1) K| = (|S - S| - 1) p^(2k) + p^k. K^(-1) K generates G. As k grows (p fixed), Theorem 11 and Theorem 13 (r = 3) in the b form are tight up to a constant, while the |G'| forms are off by p^(k-1) and p^(4(k-1)). The abelian r = 2 bound itself fails here once p = 2 and k >= 8, or k = 1 and p >= 31.
Proposition 9 (the fibre count is the right loss, b is not). In Gamma(p; j, k) with S = {0, e_1, ..., e_j} and D = (K^(-1) K) x H^(r-1): |K| = (j+1) p^k, beta_(1,2) = p^k, |{[d_1, d_2]}| = (j(j+1)/2)(p^k - 1) + 1 (p = 2), b = p^(j+k-1) and |G'| = p^(jk). With j = k, the abelian r = 2 bound fails by a factor Theta(p^k / k^2). The fibre form allows exactly p^k, which is tight up to O((log beta)^2). The class-size form allows p^(2k-1), about the square. The smallest genuine case found is Gamma(3; 4, 4), of order 3^24: |K| = 405, |K^(-1) K| = 131,301, |D| = 10,635,381. The log2 slacks of |K|^8 m >= |D|^3 are -0.73 for the abelian bound (FAILS), +5.61 with m = beta = 81, +8.91 with the commutator count 801, +10.36 with b = 2187 and +24.6 with |G'| = 3^16.
Section 13 E of finite-groups.md describes what an example beating the exponent 1/6 for r = 3 would have to look like.
Prior work. Searches on 2026-10-15 and 2026-10-16 found nothing on sets containing translates of cubes in non-abelian groups. The nearest work we found is Tao's non-commutative entropy (arXiv math/0601431) and the work of Gill, Lifshitz, Pyber and Szabo on the Liebeck-Nikolov-Shalev conjecture about product sets (arXiv 2408.07800). The arguments are short Shannon-inequality and counting arguments, so a specialist may find them routine. If any of this is known, please open an issue and we will cite it.
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)