Theorem 4: the exact dimension theorem,
ProvedBlockSSM.theorem_4group-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1representation-theorystate-space-models
For every finite group and every block bound ,
Here is the minimum hidden dimension of a finite-state one-layer block-diagonal affine tracker of with blocks of size at most , and is the minimum dimension of a faithful complex representation, with all irreducible degrees at most , of a finite group surjecting onto . Both sides are when no feasible object exists, so the equality includes the statement that a tracker exists exactly when an admissible cover does.
This identifies an architectural quantity with a purely group-theoretic invariant; it is the main theorem of the paper.
Differences from the source:
- generalization: an integer block bound → (
ℕ∞) with ; reason: every integer bound is a case through the cast, and is the unbounded case of Definition 2; the proof is the same - encoding: hidden state space with block-diagonal → the product with one matrix per block; reason: the same space split along the partition; the linear part is block-diagonal by construction
- encoding: a word → a list with at the head; reason: the same words; the empty list is the empty word
- encoding: a finite group and a finite-dimensional complex representation in the minimum defining → in the lowest universe and as
Fin d → ℂ; reason: every finite group has an isomorphic copy inTypeand every -dimensional representation is isomorphic to one on , so the set of dimensions is unchanged - encoding: all irreducible degrees in at most → every irreducible subrepresentation of has dimension at most ; reason: by Maschke every irreducible constituent is isomorphic to an irreducible subrepresentation
- encoding: a minimum, with value on an empty feasible set →
sInfinℕ∞; reason:sInf ∅ = ⊤, and on a nonempty set of naturalssInfis the minimum
Preamble
import Mathlib import Definitions.Def_BlockSSM_trackerDim import Definitions.Def_BlockSSM_coverDim universe u
Formal statement
namespace BlockSSM
/-- **Theorem 4 (the exact dimension theorem).** Geng, *The State Complexity of Block-Diagonal State Space Models*, STOC 2027 submission manuscript (sha256 f9071794…), Theorem 4, p.2 (PDF p.3): "For every finite
group G and every b ≥ 1, n_b(G) = D_b(G)."
**Formalization Note.** Both sides live in `ℕ∞` and are `⊤` when no feasible object exists, so the
equality includes "no tracker exists iff no admissible cover exists". `b : ℕ∞` with `1 ≤ b` covers
every finite `b ≥ 1`, through the cast, and also the unbounded case `D_∞`, which the paper's proof
handles the same way. -/
theorem theorem_4 (G : Type u) [Group G] [Finite G] (b : ℕ∞) (hb : 1 ≤ b) :
trackerDim G b = coverDim G b := by sorry
end BlockSSM
Source
C. Geng, The State Complexity of Block-Diagonal State Space Models, STOC 2027 submission manuscript (sha256 f9071794…), Theorem 4, p.2 (PDF p.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.