Irreducible and linearly primitive actions on subquotients of
DefinitionGroupIsoPoly_Supplement_LinPrimOngroup-cohomologygroup-isomorphismgroup-theorymatrix-groupsp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a set of matrices in and subspaces of , both invariant under ; consider the induced action on . Subspaces of are written as subspaces with .
- The action on is irreducible if and the only -invariant with are and .
- A block decomposition of is a family () with , whose images form a direct sum , such that every maps each onto some . A linear imprimitivity system is a block decomposition with .
- The action is linearly primitive if it is irreducible and has no linear imprimitivity system.
These are the paper's notions of §5.1 applied to induced actions on invariant subquotients, as Theorem 5.1 uses them for composition factors and their blocks.
Formalization Note is the image of under the matrix (gmap). The direct-sum condition is together with ; for subspaces containing this is independence in .
Definition code
import Mathlib
set_option autoImplicit false
namespace GroupIsoPoly
namespace Supplement
variable {p d : ℕ}
/-- The image `h(U)` of a subspace `U ≤ F_p^d` under a matrix `h ∈ GL(d, p)`. -/
noncomputable def gmap [Fact p.Prime] (h : GL (Fin d) (ZMod p)) (U : Submodule (ZMod p) (Fin d → ZMod p)) :
Submodule (ZMod p) (Fin d → ZMod p) :=
U.map (Matrix.mulVecLin (h : Matrix (Fin d) (Fin d) (ZMod p)))
/-- **Irreducibility on a subquotient.** For subspaces `L ≤ U` of `F_p^d` invariant under a set `S` of
matrices, `IrredOn S L U` says that the induced action of `S` on `U/L` is irreducible: `U/L ≠ 0` and
the only `S`-invariant subspaces `W` with `L ≤ W ≤ U` are `L` and `U`.
Qiao, Zhang, *Testing isomorphism of finite groups in time polynomial in the group order*, preprint,
Nov. 3, 2026 (held version sha256 eb9a3355…), §5.1, p.41 (PDF p.45): "We say that H is irreducible if
there are no non-trivial invariant subspaces of H."
**Formalization Note.** Subspaces of `U/L` are represented by the subspaces `W` with `L ≤ W ≤ U`
(the correspondence theorem), and `W` is `S`-invariant when `h(W) ≤ W` for `h ∈ S`. -/
def IrredOn [Fact p.Prime] (S : Set (GL (Fin d) (ZMod p)))
(L U : Submodule (ZMod p) (Fin d → ZMod p)) : Prop :=
L < U ∧ ∀ W : Submodule (ZMod p) (Fin d → ZMod p), L ≤ W → W ≤ U →
(∀ h ∈ S, gmap h W ≤ W) → W = L ∨ W = U
/-- **A block decomposition of a subquotient.** `IsBlockDecomp S L U W` says that the subspaces
`W 0, …, W (k-1)`, each with `L < W c ≤ U`, have images in `U/L` that form a direct-sum decomposition
`U/L = W₀/L ⊕ ⋯ ⊕ W_{k-1}/L` (each `W c / L ≠ 0`), and that every `h ∈ S` maps each `W c` onto some
`W c'`.
Qiao, Zhang, preprint, Nov. 3, 2026 (held version sha256 eb9a3355…), §5.1, p.41 (PDF p.45): "A linear
imprimitivity system of H ≤ GL(d, p) is a direct sum decomposition F_p^d = U1 ⊕ · · · ⊕ Uk, with k ≥ 2
and Ui ≠ 0 for all i, such that for any h ∈ H and i ∈ [k], h(Ui) = Uj for some j ∈ [k]."
**Formalization Note.** Here `k ≥ 1` is allowed (a single block); a linear imprimitivity system is
the case `k ≥ 2`. Independence of the images in `U/L` is `W c ⊓ (L ⊔ ⨆_{c' ≠ c} W c') = L`, which for
subspaces containing `L` is the direct-sum condition in the quotient (for `k = 1` it is automatic). -/
def IsBlockDecomp [Fact p.Prime] (S : Set (GL (Fin d) (ZMod p)))
(L U : Submodule (ZMod p) (Fin d → ZMod p)) {k : ℕ}
(W : Fin k → Submodule (ZMod p) (Fin d → ZMod p)) : Prop :=
1 ≤ k ∧ (∀ c, L < W c ∧ W c ≤ U) ∧ (⨆ c, W c) = U ∧
(∀ c, W c ⊓ (L ⊔ ⨆ c' ∈ {c' : Fin k | c' ≠ c}, W c') = L) ∧
∀ h ∈ S, ∀ c, ∃ c', gmap h (W c) = W c'
/-- **Linear primitivity on a subquotient.** `LinPrimOn S L U` says that the action of `S` on `U/L`
is irreducible and has no linear imprimitivity system: there is no block decomposition of `U/L`
into `k ≥ 2` nonzero summands permuted by `S`.
Qiao, Zhang, preprint, Nov. 3, 2026 (held version sha256 eb9a3355…), §5.1, p.41 (PDF p.45): "An
irreducible action is linearly primitive if no such decomposition exists. We use “primitive” in this
linear sense for matrix actions." -/
def LinPrimOn [Fact p.Prime] (S : Set (GL (Fin d) (ZMod p)))
(L U : Submodule (ZMod p) (Fin d → ZMod p)) : Prop :=
IrredOn S L U ∧
¬ ∃ (k : ℕ) (W : Fin k → Submodule (ZMod p) (Fin d → ZMod p)), 2 ≤ k ∧ IsBlockDecomp S L U W
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…), §5.1, p.41 (PDF p.45): irreducible, linear imprimitivity system, linearly primitive