alkahest-cas 3.12.0

//! Computational group theory: **permutation groups**.
//!
//! A [`Permutation`] is a bijection of the point set `{0, 1, …, n−1}` stored as
//! an images array; a [`PermutationGroup`] is the subgroup of `S_n` generated by
//! a list of them. From a list of generators this module computes orbits with
//! Schreier vectors, a base and strong generating set by the Schreier–Sims
//! algorithm, and from that BSGS the exact group order as an arbitrary-precision
//! [`rug::Integer`], membership testing by sifting, uniform random elements, and
//! (below a hard cap) full element enumeration.
//!
//! # Two conventions to read before anything else
//!
//! **Points are 0-based.** `Permutation::from_images(vec![1, 0, 2])` is the
//! transposition swapping points `0` and `1`. Group-theory literature, GAP and
//! the ATLAS are all 1-based, so transcribing a generator by hand is the most
//! likely way to get a wrong answer here;
//! [`Permutation::from_cycles_one_based`] exists so that a cycle copied out of a
//! paper can be typed in unchanged.
//!
//! **Composition is left-to-right.** `p.compose(&q)` applies `p` *first* and `q`
//! *second*:
//!
//! ```text
//!     (p ∘ q)(i)  =  q(p(i))            equivalently   i^(p·q) = (i^p)^q
//! ```
//!
//! This is GAP's convention and the one that makes the exponential notation
//! `i^g` used throughout the stabilizer-chain literature read left to right. It
//! is the **opposite** of the `f ∘ g = f(g(x))` convention used for functions in
//! analysis, and the opposite of what `nalgebra`-style matrix code would do.
//! Every product in this module — Schreier generators `u_β · x · u_{β^x}^{-1}`,
//! the coset factorisation of an element, the transversal walk — is written in
//! that order, and [`Permutation::compose`] is the only place the order is
//! decided. If you mix conventions you get a group of the right *order* whose
//! elements are the inverses of the ones you wanted, which is exactly the kind
//! of bug the Mathieu-group order tests in this module exist to catch.
//!
//! # What is here
//!
//! * [`Permutation`] — images array, [`compose`](Permutation::compose),
//!   [`inverse`](Permutation::inverse), [`identity`](Permutation::identity),
//!   [`order`](Permutation::order) (arbitrary precision — Landau's function
//!   outruns `u64` by degree ≈ 180), [`cycles`](Permutation::cycles),
//!   [`cycle_type`](Permutation::cycle_type), [`sign`](Permutation::sign),
//!   [`degree`](Permutation::degree).
//! * [`PermutationGroup`] — built from generators; [`orbit`](PermutationGroup::orbit)
//!   and [`orbits`](PermutationGroup::orbits), [`stabilizer_chain`](PermutationGroup::stabilizer_chain),
//!   [`order`](PermutationGroup::order), [`contains`](PermutationGroup::contains),
//!   [`sift`](PermutationGroup::sift), [`random_element`](PermutationGroup::random_element),
//!   [`elements`](PermutationGroup::elements).
//! * [`Orbit`] — the orbit of a point together with its **Schreier vector** and
//!   the transversal derived from it.
//! * [`StabilizerChain`] — the base, the strong generators at each level, and
//!   each level's basic orbit, all exposed rather than hidden behind `order()`.
//! * Standard constructors: [`symmetric`], [`alternating`], [`cyclic`],
//!   [`dihedral`], [`trivial`].
//!
//! # What is *not* here, and why
//!
//! This pass is deliberately the permutation-group foundation and nothing else.
//! None of the following are implemented, and no entry point silently
//! approximates them:
//!
//! * **Finitely-presented groups and Todd–Coxeter coset enumeration.** A
//!   presentation `⟨X | R⟩` is a different object with different algorithms
//!   (and no termination guarantee); there is no `FpGroup` type here at all.
//! * **Ordinary character tables** are no longer absent, but they are not
//!   *here*: conjugacy classes and the Dixon–Schneider table live in
//!   [`crate::character`], which takes a [`PermutationGroup`] as its input and
//!   caps `|G|` because it enumerates. Modular representation theory and Brauer
//!   characters remain unimplemented.
//! * **Matrix groups over `GF(q)`** are no longer absent either, and likewise
//!   not *here*: [`crate::matgroup`] builds a subgroup of `GL(d, q)` from
//!   arbitrary generators over [`crate::ffield::FiniteField`], with its own
//!   Schreier–Sims on the action on vectors. This module stays permutation-only,
//!   and the two agree where both can answer — `MatGroup`'s tests check its order
//!   against `permutation_action_on_vectors().order()` computed here.
//! * **Group cohomology** in degrees 0, 1 and 2 is implemented, in
//!   [`crate::fpgroup`], for a finite group with coefficients in a finitely
//!   generated abelian module — not here, and not in higher degrees. Group
//!   extensions beyond what `H²` classifies, and the solvable/polycyclic
//!   machinery (`PcGroup`), remain unimplemented.
//! * **Group-theoretic structure beyond the chain**: no Sylow subgroups, no
//!   normal-closure/derived-series/composition-series computations, no subgroup
//!   lattice, no automorphism groups, no backtrack search (set/partition
//!   stabilizers, centralizers, intersections). `contains` and `order` come
//!   from the chain; everything that needs backtracking is absent. Conjugacy
//!   classes are in [`crate::character`] and are found by enumerating the
//!   group, not by backtrack search, which is why they are capped there.
//! * **Randomised (Monte-Carlo) Schreier–Sims.** The implementation here is the
//!   deterministic Schreier-generator algorithm: always correct, and
//!   comfortably fast at the degrees this module admits, but not the
//!   near-linear-time algorithm used for degrees in the millions.
//!
//! # Scope limits that are enforced rather than documented
//!
//! * The stabilizer chain stores an **explicit transversal permutation per
//!   orbit point**, so its memory is `O(Σ_i |Δ_i| · n)` words — for `S_n` that
//!   is about `4n³` bytes. Degrees above [`MAX_BSGS_DEGREE`] are therefore
//!   refused ([`GroupError::DegreeTooLargeForBsgs`]) rather than allowed to
//!   exhaust memory. Orbit computation itself has no such limit; only the chain
//!   does. Lifting the cap means storing Schreier vectors alone and
//!   reconstructing `u_β` on demand, which trades the memory for a factor of
//!   `|Δ_i|` in time.
//! * Element enumeration refuses above [`DEFAULT_ELEMENT_CAP`] (and at all
//!   above [`MAX_ELEMENT_CAP`]) with [`GroupError::EnumerationTooLarge`]. A
//!   group of order `10^20` has a perfectly computable order and no listable
//!   element set, and those two facts must not be confused.

mod constructors;
mod perm_group;
mod permutation;

#[cfg(test)]
mod tests;

#[cfg(test)]
mod proptests;

pub use constructors::{alternating, cyclic, dihedral, symmetric, trivial};
pub use perm_group::{
    Orbit, PermutationGroup, SchreierEntry, SiftResult, StabilizerChain, StabilizerLevel,
    DEFAULT_ELEMENT_CAP, MAX_BSGS_DEGREE, MAX_ELEMENT_CAP,
};
pub use permutation::Permutation;

use std::fmt;

// ---------------------------------------------------------------------------
// Errors
// ---------------------------------------------------------------------------

/// Why a permutation-group operation refused.
///
/// Every variant is a refusal, never a degraded answer: this module has no
/// "best effort" path. See the module docs for the standing scope limits that
/// produce [`GroupError::DegreeTooLargeForBsgs`] and
/// [`GroupError::EnumerationTooLarge`].
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum GroupError {
    /// An images array is not a bijection of `{0, …, n−1}`: some entry is out
    /// of range, or two points share an image.
    NotAPermutation {
        /// The degree the array claimed.
        degree: usize,
        /// What is wrong, concretely.
        reason: String,
    },
    /// Two permutations, or a permutation and a group, disagree on the degree.
    ///
    /// Degrees are **not** silently widened by padding with fixed points. `S_3`
    /// embedded in `S_5` is a different subgroup of a different symmetric group
    /// from `S_3` itself, and which one a caller meant is not recoverable from
    /// the arguments; use [`Permutation::extend_degree`] to say so explicitly.
    DegreeMismatch {
        /// Degree of the left/receiving operand.
        left: usize,
        /// Degree of the right/supplied operand.
        right: usize,
    },
    /// A point outside `{0, …, n−1}` was named.
    PointOutOfRange {
        /// The offending point.
        point: usize,
        /// The degree it had to be below.
        degree: usize,
    },
    /// The group is too large to enumerate element by element.
    ///
    /// The order is still available from [`PermutationGroup::order`]; it is the
    /// *list* that is refused.
    EnumerationTooLarge {
        /// Decimal rendering of `|G|` (it may not fit a `u64`).
        order: String,
        /// The cap that was in force.
        cap: u64,
    },
    /// The degree exceeds [`MAX_BSGS_DEGREE`], above which the explicit
    /// transversals this chain stores would exhaust memory.
    DegreeTooLargeForBsgs {
        /// The degree asked for.
        degree: usize,
        /// The largest degree this implementation accepts.
        max: usize,
    },
    /// A standard constructor was called outside the range where its degree-`n`
    /// action is defined and faithful.
    UnsupportedDegree {
        /// Which family: `"symmetric"`, `"dihedral"`, …
        family: &'static str,
        /// The `n` that was asked for.
        requested: usize,
        /// Why that `n` has no such group in this representation.
        reason: &'static str,
    },
}

impl fmt::Display for GroupError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            GroupError::NotAPermutation { degree, reason } => write!(
                f,
                "not a permutation of {{0, …, {}}}: {reason}",
                degree.saturating_sub(1)
            ),
            GroupError::DegreeMismatch { left, right } => write!(
                f,
                "permutation degrees disagree: {left} and {right}. Degrees are not padded \
                 automatically; use `Permutation::extend_degree` to embed the smaller one"
            ),
            GroupError::PointOutOfRange { point, degree } => write!(
                f,
                "point {point} is outside {{0, …, {}}} (degree {degree}); note that points \
                 are 0-based here",
                degree.saturating_sub(1)
            ),
            GroupError::EnumerationTooLarge { order, cap } => write!(
                f,
                "the group has order {order}, above the enumeration cap of {cap}; its order \
                 is known exactly but its elements will not be listed"
            ),
            GroupError::DegreeTooLargeForBsgs { degree, max } => write!(
                f,
                "degree {degree} exceeds the Schreier–Sims limit of {max}: this chain stores \
                 an explicit transversal permutation per orbit point"
            ),
            GroupError::UnsupportedDegree {
                family,
                requested,
                reason,
            } => write!(f, "{family}({requested}) is not available: {reason}"),
        }
    }
}

impl std::error::Error for GroupError {}

impl crate::errors::AlkahestError for GroupError {
    fn code(&self) -> &'static str {
        match self {
            GroupError::NotAPermutation { .. } => "E-GRP-001",
            GroupError::DegreeMismatch { .. } => "E-GRP-002",
            GroupError::PointOutOfRange { .. } => "E-GRP-003",
            GroupError::EnumerationTooLarge { .. } => "E-GRP-004",
            GroupError::DegreeTooLargeForBsgs { .. } => "E-GRP-005",
            GroupError::UnsupportedDegree { .. } => "E-GRP-006",
        }
    }

    fn remediation(&self) -> Option<&'static str> {
        match self {
            GroupError::NotAPermutation { .. } => Some(
                "supply each of 0..n exactly once as an image; points are 0-based, so a cycle \
                 copied from GAP or the ATLAS needs `Permutation::from_cycles_one_based`",
            ),
            GroupError::DegreeMismatch { .. } => Some(
                "embed the smaller permutation with `Permutation::extend_degree(n)` before \
                 composing, or rebuild both at the common degree",
            ),
            GroupError::PointOutOfRange { .. } => {
                Some("points are 0-based: the valid range is 0..degree")
            }
            GroupError::EnumerationTooLarge { .. } => Some(
                "use `order()`, `contains()` or `random_element()` instead of listing the \
                 elements, or raise the cap with `elements_with_cap` if the list really fits \
                 in memory",
            ),
            GroupError::DegreeTooLargeForBsgs { .. } => Some(
                "orbits and orbit representatives are available at any degree; only the \
                 stabilizer chain (and therefore `order`, `contains` and `elements`) is capped",
            ),
            GroupError::UnsupportedDegree { .. } => Some(
                "these constructors build the natural degree-n action; below the stated \
                 minimum that action is not faithful, so build the group by hand on the \
                 point set you actually mean",
            ),
        }
    }
}