Lemma 5.10 — over there are at least matrices of size and rank exactly
ProvedGroupIsoDepth.LowerBounds.lemma_5_10countingfinite-fieldslinear-algebrap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite field with elements and . Then there are at least matrices of size over of rank exactly .
Differences from the source:
- encoding: k × k matrices of rank exactly r → hypothesis r ≤ k; reason: a k × k matrix has rank ≤ k; for r > k the count is 0 and the statement has no content in the paper
- encoding: F_q → any finite field F with q = Fintype.card F; reason: every finite field is some F_q
- encoding: q^{r(2k−r)−2k} → real zpow with exponent r(2k − r) − 2k computed in ℤ; reason: the exponent can be negative
Preamble
import Mathlib
Formal statement
namespace GroupIsoDepth.LowerBounds
/-- Lemma 5.10 (printed p. 39, PDF 40). Over a finite field `F_q`, there are at least
`q^{r(2k−r)−2k}` matrices of size `k × k` and rank exactly `r` (for every rank `0 ≤ r ≤ k`). -/
theorem lemma_5_10 {F : Type*} [Field F] [Fintype F] (k r : ℕ) (hr : r ≤ k) :
(Fintype.card F : ℝ) ^ ((r : ℤ) * (2 * k - r) - 2 * k) ≤
(Nat.card {M : Matrix (Fin k) (Fin k) F // M.rank = r} : ℝ) := by sorry
end GroupIsoDepth.LowerBounds
Source
Grochow, Kardeş, Levet, Group Isomorphism: Depth-2½ Circuits and Lower Bounds, STOC 2027 submission (manuscript sha256 cd6cacd4…), Lemma 5.10 (p. 39, PDF 40)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.