Module permgroup 

Schreier–Sims: a base and strong generating set (BSGS) for a permutation group — the non-abelian generalization of Gaussian elimination, and the last rung of the algebra ladder (GF(2)→GF(p)→ℤ/m linear; this is the group level).

Gaussian elimination decides membership/dimension of a vector subspace by a basis under a stabilizer chain of coordinate projections. Schreier–Sims does the same for a permutation group: a base B = (β₁,…,β_k) is a sequence of points whose pointwise stabilizer is trivial, giving the stabilizer chain G = G⁽¹⁾ ≥ G⁽²⁾ ≥ … ≥ G⁽ᵏ⁺¹⁾ = {id} with G⁽ⁱ⁾ fixing β₁…β_{i−1}. A strong generating set generates every stage. The stabilizer chain is the symmetry break — fix a base point, descend to its stabilizer, repeat — and from it, in polynomial time:

• order |G| = Π |Δᵢ| (the product of the basic orbit sizes), and
• membership / coset decision by sifting (stripping g through the chain; it lies in G iff it sifts to the identity), the decision procedure for coset problems over non-abelian groups — exactly the rung the linear engines (abelian only) could not reach.

Permutations act on the right: xᵍ = g[x], so (g·h)[x] = h[g[x]].

Structs

Bsgs

A base and strong generating set, with the per-level basic transversals.

CharacterTable

The character table of ⟨gens⟩, computed exactly by Dixon’s method.

Functions

abelianization

The abelianisation G / [G, G] — the largest abelian quotient — as (order, exponent). The order is |G| / |[G, G]|; the exponent (lcm of coset orders) and whether it equals the order — i.e. whether Gᵃᵇ is cyclic — are the new structural content. None when |G| > cap.

automorphism_group_order

The order of the automorphism group Aut(G) of G = ⟨gens⟩ — the symmetries of the group itself (bijections G → G preserving multiplication, φ(xy) = φ(x)φ(y)). An automorphism is determined by the images of a generating set, so the search ranges over candidate images (each generator must map to an element of the same order, a necessary condition) and accepts those that extend to a consistent, bijective homomorphism. None when |G| > cap or the candidate search would exceed its budget. Classic: |Aut(Cₙ)| = φ(n), |Aut(Sₙ)| = n! (n≠6), |Aut(V₄)| = 6, |Aut(D₄)| = 8, |Aut(Q₈)| = 24.

burnside_ring_product

The Burnside ring multiplication of G = ⟨gens⟩ — the structure constants N[a][b][l] giving the decomposition of the product G-set (G/H_a) × (G/H_b) = ⊔_l N[a][b][l]·(G/H_l) into transitive G-sets, indexed by the conjugacy classes of subgroups (same order as table_of_marks).

center_order

The order of the centre Z(G) — the elements commuting with all of G, which are exactly those in singleton conjugacy classes. None when |G| > cap.

character_table

Compute the full character table via the Burnside–Dixon algorithm: build the commuting class-algebra matrices M_i from the structure constants, choose a Dixon prime p, simultaneously diagonalise the M_i over GF(p) by iterated eigenspace refinement (one common eigenvector per irreducible), then read off each degree d_s (exact integer, via d² = |G|/Σ_r ω_r ω_{r̄}/|C_r|) and the character values χ_s(C_r) = d_s ω_r/|C_r|. Returns None when |G| > cap, the group is too large for the finite-field arithmetic, or — FAIL-CLOSED — the recovered table does not satisfy the row-orthogonality and degree relations (so a returned table is always a verified one). Rows are sorted by (degree, values) for determinism.

class_multiplication_coefficients

The class-algebra structure constants a[i][j][k] = #{ x ∈ Cᵢ : x⁻¹·z ∈ Cⱼ } for z a fixed representative of class Cₖ (independent of the choice of z). These are the multiplication coefficients of the centre of the group algebra — Cᵢ·Cⱼ = Σₖ a[i][j][k]·Cₖ — and the foundation of the Burnside–Dixon character-table algorithm. They satisfy Σₖ a[i][j][k]·|Cₖ| = |Cᵢ|·|Cⱼ|. None when |G| > cap.

composition_factor_orders

The composition factors of the group as the sorted multiset of their orders — the Jordan–Hölder decomposition into simple groups (the “prime factorisation” of the group). Their product is |G|; for a solvable group every factor is a prime (cyclic Cₚ), and a non-abelian simple factor (e.g. A₅, order 60) marks unsolvability. None when the group is out of range.

conjugacy_classes

The conjugacy classes of the group — the partition of its elements by g ~ x⁻¹gx. The number of classes equals the number of irreducible representations (the bridge to character theory); the singleton classes are exactly the centre Z(G). Requires enumerating the group, so it returns None when |G| > cap.

cycle_index

The cycle index data — the distribution of cycle types over the group, mapping each cycle type to the number of elements with it. Dividing by |G| gives the cycle index polynomial, the engine of Pólya enumeration. None when |G| > cap.

derived_length

The derived length (solvability class): the number of steps the derived series G ⊵ G' ⊵ G'' ⊵ … takes to reach the trivial group, or None if it never does (G is unsolvable). 0 is the trivial group, 1 a non-trivial abelian group, 2 for S₃, 3 for S₄.

derived_subgroup

Generators of the derived (commutator) subgroup [G, G] — the normal closure of the commutators of the generators. Always normal; G / [G, G] is the abelianisation, and [G, G] is trivial iff G is abelian.

element_orders

The order spectrum — the set of distinct orders of the group’s elements. None when |G| > cap.

exponent

The exponent of the group — the least common multiple of all element orders, i.e. the smallest e with gᵉ = id for every g. None when |G| > cap.

frobenius_schur_from_table

The Frobenius–Schur indicators ν(χ_s) = (1/|G|) Σ_{g∈G} χ_s(g²) ∈ {+1, 0, −1} read off a character table: +1 if the irreducible is real (orthogonal), 0 if complex (χ ≠ χ̄), −1 if quaternionic (symplectic). Computed exactly over the table’s GF(p): Σ_r |C_r|·χ_s(C_{r²}), scaled by 1/|G|, decoded {0, 1, p−1} → {0, 1, −1}. FAIL-CLOSED: returns None if any value decodes outside {−1,0,1} or the Frobenius–Schur sum rule Σ_s ν(χ_s)·d_s = #{g : g²=1} fails. The indicators distinguish groups with identical character tables (e.g. D₄ all +1 vs Q₈ with a −1).

frobenius_schur_indicators

The Frobenius–Schur indicators of ⟨gens⟩, one per irreducible character (aligned with character_table’s rows). See frobenius_schur_from_table. None when the character table is out of range.

galois_class_orbits

The Galois orbits on conjugacy classes. The Galois group Gal(ℚ(ζ_e)/ℚ) ≅ (ℤ/e)* (e = the group exponent) acts on classes by C ↦ C^t (the class of g^t), for every t coprime to e — this is the action dual to the Galois action σ_t(χ)(g) = χ(g^t) on irreducible characters. Two classes share an orbit iff they are algebraically conjugate (g ~ g^t for some coprime t). None when |G| > cap.

generating_tuple_count

The number of ordered k-tuples of group elements that generate G — the Eulerian function e_k(G) = Σ_{H ≤ G} μ(H, G)·|H|ᵏ (Hall’s formula by Möbius inversion over the subgroup lattice, since |H|ᵏ counts the k-tuples landing in H). Dividing by |G|ᵏ gives the probability that k random elements generate G. None when |G| > cap.

irreducible_degrees

The irreducible-representation degrees χ_s(1) of ⟨gens⟩, sorted ascending (Σ dᵢ² = |G|) — the cheap summary of the character_table. None when the table cannot be computed (|G| > cap or too large for the finite-field diagonalisation).

is_abelian

Is the group abelian? (Its generators pairwise commute.)

is_nilpotent

Is the group nilpotent? (Its lower central series reaches the trivial group.) Strictly stronger than solvability — every p-group is nilpotent, but S₃ (solvable) is not.

is_primitive

Is the group primitive — transitive with no non-trivial block system? Primitive groups are the indecomposable “atoms” of permutation-group structure; imprimitive ones split into blocks (minimal_block_system).

is_primitive_via_orbitals

Primitivity via Higman’s theorem: a transitive group is primitive iff every non-diagonal orbital graph is connected. An independent route to is_primitive; when a non-diagonal orbital graph is disconnected, its connected components are a block system. (Returns false for an intransitive group.)

is_simple

Is the group simple — non-trivial with no normal subgroup but {id} and itself? Tested via conjugacy: every non-trivial normal subgroup contains the whole conjugacy class of any of its elements, hence the normal closure of that element. So G is simple iff the normal closure of every non-identity element is all of G. Simple non-abelian groups (e.g. A₅) are exactly the unsolvable building blocks. None when |G| > cap.

is_solvable

Is the group solvable? (Its derived series reaches the trivial group.)

isotypic_from_table

The isotypic decomposition of the permutation representation: the multiplicity m_s = ⟨π, χ_s⟩ of each irreducible χ_s in the natural action’s character π, i.e. π = Σ_s m_s χ_s. Computed from a character table: m_s = (1/|G|) Σ_r |C_r|·π(C_r)·χ_s(C_{r̄}) over the table’s GF(p). The representation-theoretic spectrum of the symmetry — it ties the linear theory back to the action: m_trivial = #orbits (Burnside), Σ_s m_s² = rank (#orbitals), Σ_s m_s·d_s = degree. FAIL-CLOSED: None if p ≤ degree (then the small non-negative m_s ≤ degree would not decode uniquely) or if any of those three identities fails. Aligned with the table’s rows.

isotypic_multiplicities

The isotypic multiplicities of ⟨gens⟩’s permutation representation, one per irreducible (aligned with character_table’s rows). See isotypic_from_table. None when the character table is out of range or the multiplicities cannot be decoded/verified.

minimal_block_system

The minimal non-trivial block system of a TRANSITIVE permutation group — the finest G-invariant partition into equal-size blocks bigger than a point and smaller than the whole set — or None if the group is primitive (only the trivial partitions are invariant) or not transitive. Imprimitivity is the symmetry’s internal structure: a grid symmetry decomposes into its rows, a cyclic group of composite order into cosets. (Atkinson’s algorithm over each pair {0, β}.)

mobius_number

The Möbius number μ(1, G) of the subgroup lattice of G = ⟨gens⟩ — the value of the lattice’s Möbius function from the trivial subgroup to the whole group. A classical invariant: for a cyclic group μ(1, Cₙ) is the number-theoretic Möbius function μ(n), and in general it drives the group’s Eulerian (probabilistic-zeta) function. None when |G| > cap.

nilpotency_class

The nilpotency class: the number of steps the lower central series γ₁ = G, γ_{k+1} = [G, γ_k] takes to reach the trivial group, or None if it never does (G is not nilpotent). 0 is trivial, 1 abelian, 2 for D₄.

orbitals

The orbitals — the orbits of the group on ORDERED PAIRS (i, j) under the action g·(i,j) = (g[i], g[j]). The diagonal {(i,i)} is always one orbital; for a transitive group the non-diagonal orbitals are its “relation classes” (its association scheme). The count is the group’s rank. One level finer than the point-orbits (orbits).

orbits

The orbits of {0,…,degree−1} under ⟨generators⟩, as a partition (each orbit sorted ascending, orbits ordered by least element). Needs only the generators — a BFS, independent of the BSGS.

orbits_on_tuples

The orbits of the group on ordered k-tuples of distinct points (g·(t₁,…,t_k) = (g[t₁],…,g[t_k])). k = 1 is the point-orbits (orbits); k = 2 (on distinct pairs) refines orbitals; in general the group is k-transitive iff this is a single orbit — the rungs of the transitivity ladder.

outer_automorphism_order

The order of the outer automorphism group Out(G) = Aut(G)/Inn(G), where the inner automorphisms Inn(G) ≅ G/Z(G) are those realised by conjugation. Out(G) counts the “exotic” symmetries of the group not coming from within it. None when out of range.

pattern_inventory

The pattern inventory (weighted Pólya, two colours) — coeff[w] is the number of distinct {0,1} assignments to the points with exactly w ones, up to the group. Obtained by substituting aₖ → (1 + zᵏ) into the cycle index: a k-cycle is either all-0 or all-1, contributing 1 + zᵏ. The coefficients sum to polya_count(…, 2, …). None when |G| > cap.

permutation_character

The permutation character π(g) = #{points fixed by g} of the natural action of ⟨gens⟩ on its degree points, valued per conjugacy class (a class invariant, since conjugate permutations have the same cycle type). The character of the permutation representation ℂ^degree. Aligned with the conjugacy classes (so with CharacterTable’s columns). None when |G| > cap.

permutation_character_decomposition

The permutation-character decomposition — the bridge between the table of marks and the character table. M[i][s] is the multiplicity of the irreducible χ_s in the permutation representation of G on the cosets G/H_i, i.e. M[i][s] = ⟨Ind_{H_i}^G 1, χ_s⟩ = (1/|H_i|)·Σ_{h ∈ H_i} χ_s(h) (Frobenius reciprocity = the dimension of the H_i-fixed subspace of χ_s). Rows are subgroup conjugacy classes (as in table_of_marks), columns are irreducibles (as in character_table). Returns (subgroup_orders, irreducible_degrees, M).

polya_count

Pólya / Burnside count — the number of ways to colour the degree points with m colours up to the group action: (1/|G|) Σ_g m^{#cycles(g)}. With m = 2 this is the number of distinct {0,1} assignments to the points modulo symmetry — the symmetry-reduced size of the assignment space. None when |G| > cap.

rank

The rank of the group: the number of orbitals (orbits on ordered pairs). A transitive group has rank 2 iff it is 2-transitive; a regular group has rank equal to its degree.

rational_class_count

The number of rational conjugacy classes — classes C fixed by the whole Galois group (g ~ g^t for every t coprime to ord(g)), i.e. the singleton galois_class_orbits. By Burnside’s rationality theorem this equals the number of rational-valued irreducible characters. Strictly refines real_class_count (real = closed under the single element t = −1): rational ⟹ real, and the counts differ exactly when a character is real but irrational (e.g. A₅’s golden-ratio degree-3 pair). None when |G| > cap.

real_class_count

The number of real conjugacy classes — those closed under inversion (C = C⁻¹). By Burnside’s theorem this equals the number of real-valued irreducible characters. None when |G| > cap.

schreier_sims

Schreier–Sims. Build a BSGS for the permutation group on degree points generated by generators (each a permutation of {0,…,degree−1}). Deterministic incremental construction: seed the chain with the generators, then repeatedly sift every Schreier generator (u·s divided by its transversal element, Schreier’s lemma) into the chain, adding any non-trivial residue as a new strong generator (extending the base as needed), until every Schreier generator sifts to the identity — the completeness condition.

subgroup_count

sylow_counts

The Sylow structure — for each prime p ∣ |G|, the number n_p of Sylow p-subgroups (the subgroups of maximal p-power order pᵃ ∥ |G|; all such subgroups are conjugate, so counting them counts the Sylow subgroups). Returned as (p, n_p) pairs sorted by p. Sylow’s theorems guarantee n_p ≡ 1 (mod p) and n_p ∣ |G|/pᵃ. None when the subgroup lattice is out of range.

table_of_marks

The table of marks of G = ⟨gens⟩ — the Burnside-ring analogue of the character table. Rows and columns are the conjugacy classes of subgroups (ordered by increasing order); the (i,j) entry is the mark m(H_i, H_j) = the number of H_i-fixed points in the transitive action of G on the cosets G/H_j, computed as (1/|H_j|)·|{g ∈ G : g⁻¹ H_i g ⊆ H_j}|. Returns (subgroup_class_orders, marks).

tensor_decomposition

The tensor (fusion) decomposition of ⟨gens⟩’s irreducibles. See tensor_from_table. None when the character table is out of range or the fusion coefficients fail their structural checks.

tensor_from_table

The tensor (Clebsch–Gordan) decomposition of the irreducibles: N[i][j][k] = ⟨χ_i·χ_j, χ_k⟩, the multiplicity of χ_k in the tensor product χ_i ⊗ χ_j. These are the fusion coefficients — the structure constants of the representation ring R(G) (the multiplication dual to the character table’s addition). Computed from a character table: N[i][j][k] = (1/|G|) Σ_r |C_r|·χ_i(C_r)·χ_j(C_r)·χ_k(C_{r̄}) over the table’s GF(p); each is a small non-negative integer ≤ d_i·d_j ≤ |G| < p, so it decodes uniquely. FAIL-CLOSED: returns None unless every fusion product has the right dimension (Σ_k N[i][j][k]·d_k = d_i·d_j), the trivial character is a unit (χ_triv ⊗ χ_j = χ_j), and the coefficients are symmetric (N[i][j][k] = N[j][i][k]). Indices align with character_table’s rows.

transitivity_degree

The transitivity degree: the largest t ≤ max_t for which the group is transitive on ordered t-tuples of distinct points (1 = transitive, 2 = 2-transitive, …). 0 if intransitive. Capped at max_t because the t-tuple space grows as degree^t. Sₙ is n-transitive; a regular group is only 1-transitive.

upper_central_length

The length of the upper central series when it reaches G (the nilpotency class) — None if it stalls below G (the group is not nilpotent) or |G| > cap. Equals nilpotency_class for nilpotent groups, an independent route to the same number.

upper_central_series

The orders [|Z₀|, |Z₁|, …] of the upper central series, up to the hypercentre. Z₀ = {id} and Z_{i+1} = { g : [g, x] ∈ Z_i for all x } (the preimage of the centre of G/Z_i). The series ascends to |G| iff G is nilpotent. None when |G| > cap.

Type Aliases

Perm

A permutation of {0,…,n−1}: p[x] is the image of point x.