Theorem 5.1, p.42 — invariant composition flags with kernel and linearly primitive blocks in time
OpenGroupIsoPoly.Supplement.theorem_5_1Let be a prime and let be given by a list of generators; let be the length of the input. There is a deterministic algorithm that computes, in time :
- an invariant composition flag
of -invariant subspaces, each irreducible under , such that the kernel of the action of on the associated graded space is exactly the -core (the largest normal -subgroup); 2. for each , a direct-sum decomposition into blocks permuted transitively by , such that the stabiliser of each block acts on it irreducibly and linearly primitively.
Here one algorithm works for all primes , all dimensions and all generating lists, and the constant in and the polynomial are fixed.
This is the first step of the paper's structural analysis of matrix groups: it reduces the action of to linearly primitive pieces, on which the later steps (large classical components, alternating-dominant actions) operate.
Formalization Note The machine is the base mission's HMBinPacking.OutputsWithin; the bound is with one constant . The output is valid data in the sense of FlagValid (bases of the and of the block subspaces).
Differences from the source:
- reading: "can be computed in time p^O(d) · poly(InSize)" (no machine named) → one deterministic machine M (HMBinPacking.OutputsWithin) and one constant C, time C·p^(C·d)·(L+2)^C on every input, L the input code length; reason: the paper fixes no machine; the base mission's reading (Theorem 8.1)
- encoding: H ≤ GL(d, p) "given by generators" → the code of p, d, the number of generators and their matrices row by row (encodeNat); reason: the paper names no input format; same layout as the base mission's codes
- encoding: the flag and the block decompositions are "computed" → bases of V_0, …, V_ℓ and, for each block, a basis of its subspace U with V_{i−1} ≤ U ≤ V_i; any valid data may be output; reason: subspaces are output by bases; the output is not unique
- encoding: blocks permuted transitively by G = H/O_p(H); block stabilisers in G → transitivity and stabilisers stated for H; reason: O_p(H) acts trivially on every factor (item 1), so H and G induce the same actions
- encoding: factors V_i/V_{i−1}, i ∈ [ℓ] → factors V_{i+1}/V_i, i : Fin ℓ; reason: index base only
import Mathlib import Definitions.Def_HMBinPacking_OutputsWithin import Definitions.Def_GroupIsoPoly_Supplement_encFlagData set_option autoImplicit false
namespace GroupIsoPoly
namespace Supplement
/-- **Theorem 5.1 (Invariant composition flags and linear primitive systems).**
Qiao, Zhang, *Testing isomorphism of finite groups in time polynomial in the group order*, preprint,
Nov. 3, 2026 (held version sha256 eb9a3355…), Theorem 5.1, p.42 (PDF p.46): "Let H ≤ GL(d, p) be
given by generators. The following can be computed in time p^O(d) · poly(InSize). 1. An invariant
composition flag 0 = V0 < V1 < · · · < Vℓ = F_p^d, such that the action of H on the associated graded
space has kernel Op(H). 2. For each Vi/Vi−1, a direct-sum decomposition into blocks permuted
transitively by G = H/Op(H), with each block stabiliser acting irreducibly and linearly primitively
on its block."
There are one deterministic machine `M` and one constant `C` such that for every prime `p`, every `d`
and every list of generators of a subgroup `H ≤ GL(d, p)`, `M` on the code of the instance (length
`L = InSize`) halts within `C · p^(C·d) · (L + 2)^C` steps and outputs the code of a flag with blocks
satisfying `FlagValid H` (items 1 and 2 at full strength).
**Formalization Note.** The machine model is the base mission's `HMBinPacking.OutputsWithin`;
`p^O(d) · poly(InSize)` is read as `C · p^(C·d) · (L + 2)^C` with one constant (the base mission's
reading for Theorem 8.1). The output is not unique: some valid data is output. `H` is the subgroup
generated by the list (the trivial group for the empty list; `d = 0` is allowed). -/
theorem theorem_5_1 :
∃ M : Turing.TM2ComputableAux Bool Bool, ∃ C : ℕ,
∀ (p : ℕ) [Fact p.Prime] (d : ℕ) (gens : List (GL (Fin d) (ZMod p))),
∃ D : FlagData p d,
FlagValid (Subgroup.closure {g | g ∈ gens}) D ∧
HMBinPacking.OutputsWithin M (encMatGroupInst p d gens) (encFlagData D)
(C * p ^ (C * d) * ((encMatGroupInst p d gens).length + 2) ^ C) := by sorry
end Supplement
end GroupIsoPoly