Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1, p.42 — invariant composition flags with kernel Op(H)O_p(H)Op​(H) and linearly primitive blocks in time pO(d)⋅poly(InSize)p^{O(d)}\cdot\mathrm{poly}(\mathrm{InSize})pO(d)⋅poly(InSize)

Open
GroupIsoPoly.Supplement.theorem_5_1

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsgroup-cohomologygroup-isomorphismgroup-theorymatrix-group-algorithmsmatrix-groupsp2o-gran-per-chapterp2o-plan-bookp2o-v1

Let ppp be a prime and let H≤GL(d,p)H\le\mathrm{GL}(d,p)H≤GL(d,p) be given by a list of generators; let InSize\mathrm{InSize}InSize be the length of the input. There is a deterministic algorithm that computes, in time pO(d)⋅poly(InSize)p^{O(d)}\cdot\mathrm{poly}(\mathrm{InSize})pO(d)⋅poly(InSize):

  1. an invariant composition flag
0=V0<V1<⋯<Vℓ=Fpd0=V_0<V_1<\cdots<V_\ell=\mathbb F_p^d0=V0​<V1​<⋯<Vℓ​=Fpd​

of HHH-invariant subspaces, each Vi/Vi−1V_i/V_{i-1}Vi​/Vi−1​ irreducible under HHH, such that the kernel of the action of HHH on the associated graded space ⨁iVi/Vi−1\bigoplus_i V_i/V_{i-1}⨁i​Vi​/Vi−1​ is exactly the ppp-core Op(H)O_p(H)Op​(H) (the largest normal ppp-subgroup); 2. for each Vi/Vi−1V_i/V_{i-1}Vi​/Vi−1​, a direct-sum decomposition into blocks permuted transitively by G=H/Op(H)G=H/O_p(H)G=H/Op​(H), such that the stabiliser of each block acts on it irreducibly and linearly primitively.

Here one algorithm works for all primes ppp, all dimensions ddd and all generating lists, and the constant in O(d)O(d)O(d) and the polynomial are fixed.

This is the first step of the paper's structural analysis of matrix groups: it reduces the action of HHH 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 C⋅pCd⋅(L+2)CC\cdot p^{Cd}\cdot(L+2)^CC⋅pCd⋅(L+2)C with one constant CCC. The output is valid data in the sense of FlagValid (bases of the VjV_jVj​ 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
Preamble
import Mathlib
import Definitions.Def_HMBinPacking_OutputsWithin
import Definitions.Def_GroupIsoPoly_Supplement_encFlagData

set_option autoImplicit false
Formal statement
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
Source
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); definitions §5.1, p.41 (PDF p.45)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me