Theorem 2 (Two sectors) — unipotent and quasi-unipotent CCRA characterizations
OpenCopylessCRA.Supplement.theorem_2algebraic-groupscost-register-automatap2o-gran-per-chapterp2o-plan-paperp2o-v1rational-seriesweighted-automata
Let be a rational series, represented by an arbitrary minimal representation over a finite alphabet.
- If every word matrix is unipotent, then the following are equivalent: is CCRA-computable; all minimal letter matrices commute; is invariant under permutations of input positions; and there is a rational polynomial such that
- If every eigenvalue of every word matrix is a root of unity, then the following are equivalent: is CCRA-computable; any two unipotent word matrices commute; is virtually abelian; and there exist a finite group , a morphism , and polynomials such that
for every word , where uses the group state before reading the counted position.
This gives exact concrete forms for the two sectors of the main characterization.
Differences from the source:
- encoding: the source refers to the minimal representation intrinsically and describes unipotence, roots of unity and finite-group transition counts in prose → Lean takes an arbitrary supplied minimal representation, expresses unipotence as nilpotence of , tests roots of its characteristic polynomials over for quasi-unipotence, and bundles the finite group and word morphism; reason: minimal representations are unique up to conjugacy, nilpotence of is equivalent to every eigenvalue being , characteristic-polynomial roots are exactly the eigenvalues with algebraic multiplicity, and the bundled data preserve the same instances
Preamble
import Mathlib import Definitions.Def_CopylessCRA_Supplement_IsUnipotentSeries open Matrix
Formal statement
namespace CopylessCRA
namespace Supplement
/-- Zeng--Cao--Dai--Wang--Ding, *Copyless Cost Register Automata and Algebraic Groups*, STOC
2027 submission (manuscript sha256 434d3094...), Theorem 2 (Two sectors), p.3 (PDF p.5),
proved in Appendix A, p.13 (PDF p.15).
For a unipotent rational series, CCRA-computability, commutation of the minimal letter matrices,
permutation invariance, and a rational polynomial in the letter counts are equivalent. For a
quasi-unipotent rational series, CCRA-computability, commutation of all unipotent word matrices,
virtual abelianness of the generated group, and the finite-group transition-count normal form are
equivalent.
**Formalization Note** `M` is an arbitrary supplied minimal representation of `f`, matching the
paper's intrinsic minimal representation up to conjugacy. Both chains retain all four clauses.
The root-of-unity condition ranges over every word matrix. In `transitionCount`, the group state
is measured before the current letter, and the chosen polynomial depends on the final state
`phi(w)`. -/
theorem theorem_2 {alpha iota : Type*} [Fintype alpha] [DecidableEq alpha]
[Fintype iota] [DecidableEq iota] (f : List alpha -> ℚ) (lam : iota -> ℚ)
(M : alpha -> Matrix iota iota ℚ) (gamma : iota -> ℚ)
(hrep : IsRep f lam M gamma) (hmin : IsMinimalRep lam M gamma) :
(IsUnipotentSeries M -> List.TFAE
[C1 f,
forall a b, Commute (M a) (M b),
IsPermutationInvariant f,
HasLetterCountPolynomial f]) ∧
(IsQuasiUnipotentSeries M -> List.TFAE
[C1 f,
UnipotentWordMatricesCommute M,
IsLetterGroupVirtuallyAbelian M,
HasTransitionCountNormalForm f]) := by sorry
end Supplement
end CopylessCRA
Source
Zeng–Cao–Dai–Wang–Ding, Copyless Cost Register Automata and Algebraic Groups, STOC 2027 submission (manuscript sha256 434d3094df2665371c402d5b5291b3c7f3a27a0d79384e4a8ec3ca3a46a92543), Theorem 2, p.3 (PDF p.5); proof p.13 (PDF p.15)