Permutation Group Theory Engine for JavaScript

This project provides a high-performance JavaScript library for computational group theory, focusing on permutation groups. It offers efficient data structures and algorithms for handling permutations, performing group operations, analyzing group structure, and generating data for visualization.

Features

  • High-Performance Permutation Handling: Optimized PermutationRepository for efficient storage and retrieval of unique permutations using a Trie-like structure and Int32Array for zero-copy views.
  • Permutation Set Operations: PermutationSet for representing collections of permutations, supporting core algebraic operations (multiplication, inverse) and set operations (union, intersection, difference).
  • Schreier-Sims Algorithm (SSA): Robust implementation for computing Base and Strong Generating Sets (BSGS), membership testing, order calculation, and stabilizer subgroups.
  • Group Structural Analysis: Functions to check subgroup and normality, compute normal closures, commutator subgroups, lower central series, and determine properties like solvability and nilpotency.
  • Standard Group Generators: Factory methods for generating common groups such as Symmetric ($S_n$), Alternating ($A_n$), Cyclic ($C_n$), Dihedral ($D_n$), Klein Four ($V_4$), and Quaternion ($Q_8$) groups.
  • Visualization Utilities: Tools for generating human-readable names for group elements, creating Cayley multiplication tables (with HTML output), and preparing Cayley graph data for 3D plotting (e.g., with Plotly).
  • Memory Efficiency: Designed with Int32Array and optimized algorithms to reduce garbage collection overhead and improve performance.

Installation

Assuming you have Node.js and npm/yarn installed:

npm install groupsjs
# or
yarn add groupsjs

If you are running this project locally, you can clone the repository:

git clone https://github.com/kikoqiu/groups.js.git
cd groups.js
npm install

Usage

HERE are some examples of how to use the library.

API Reference

Detailed API documentation can be generated from the JSDoc comments within the source code. You can use tools like JSDoc to create comprehensive documentation.

Contributing

Contributions are welcome! Please feel free to open issues or submit pull requests.

License

This project is licensed under the MIT License.

group-engine.js

Description:

  • High-Performance Group Theory Engine.

    Provides the core PermutationSet implementation with:

    • Direct memory access to the global repository (Zero-Copy reads).
    • Cache-aware loop tiling for multiplication.
    • Flat TypedArray storage for set elements.
    • Optimized Orbit and Coset algorithms.
Source:

High-Performance Group Theory Engine.

Provides the core PermutationSet implementation with:

  • Direct memory access to the global repository (Zero-Copy reads).
  • Cache-aware loop tiling for multiplication.
  • Flat TypedArray storage for set elements.
  • Optimized Orbit and Coset algorithms.

group-structural-utils.js

Description:

  • Structural Group Theory Utilities.

    Provides advanced algorithms for analyzing group structure:

    • Subgroup/Normality testing
    • Normal Closures & Commutators
    • Solvability & Simplicity testing
    • Quotient Group construction with Representative Lifting
    • Isomorphism heuristics

    DESIGN PRINCIPLE: All functions accept either PermutationSet OR SchreierSimsAlgorithm. We prioritize using SSA to leverage pre-computed chains.

    RETURN VALUE CONVENTION FOR DECISION PROBLEMS: For algorithms where strict deterministic polynomial time proof is difficult (e.g., Isomorphism, Simplicity on large groups), functions return: 1 : Yes (Strictly Proven) 0 : No (Strictly Proven) -1 : Uncertain (Heuristically likely Yes, but not strictly proven)

Source:

Structural Group Theory Utilities.

Provides advanced algorithms for analyzing group structure:

  • Subgroup/Normality testing
  • Normal Closures & Commutators
  • Solvability & Simplicity testing
  • Quotient Group construction with Representative Lifting
  • Isomorphism heuristics

DESIGN PRINCIPLE: All functions accept either PermutationSet OR SchreierSimsAlgorithm. We prioritize using SSA to leverage pre-computed chains.

RETURN VALUE CONVENTION FOR DECISION PROBLEMS: For algorithms where strict deterministic polynomial time proof is difficult (e.g., Isomorphism, Simplicity on large groups), functions return: 1 : Yes (Strictly Proven) 0 : No (Strictly Proven) -1 : Uncertain (Heuristically likely Yes, but not strictly proven)

group-utils-coxeter.js

Description:

  • Heuristic Search for Coxeter-like Generators.

    This module attempts to reconstruct a "beautiful" generating set (Coxeter-like) for a given permutation group. It prioritizes:

    1. Involutions (Order 2 elements).
    2. Sparsity (Low Hamming distance / Minimal support).
    3. Adjacency (Mapping point i to i+1).

    ALGORITHM:

    1. Stabilizer Chain Decomposition: Break down the group into layers.
    2. Frontier Expansion: Greedily find generators to cover each layer's orbit.
    3. Safety Net: Verify if the found generators actually generate the full group.
    4. Minimization: Prune redundant generators, prioritizing the removal of "ugly" (high order) ones.
Source:

Heuristic Search for Coxeter-like Generators.

This module attempts to reconstruct a "beautiful" generating set (Coxeter-like) for a given permutation group. It prioritizes:

  1. Involutions (Order 2 elements).
  2. Sparsity (Low Hamming distance / Minimal support).
  3. Adjacency (Mapping point i to i+1).

ALGORITHM:

  1. Stabilizer Chain Decomposition: Break down the group into layers.
  2. Frontier Expansion: Greedily find generators to cover each layer's orbit.
  3. Safety Net: Verify if the found generators actually generate the full group.
  4. Minimization: Prune redundant generators, prioritizing the removal of "ugly" (high order) ones.

group-utils.js

Description:

  • Global Group Theory Utilities and Generators.

    This module provides a collection of standalone functions to:

    1. Parse and Format permutations (Cycle notation <-> Array/ID).
    2. Generate standard mathematical groups (Symmetric, Alternating, etc.).

    These functions interact directly with the globalRepo to ensure efficient memory usage (Zero-Copy where possible) and return PermutationSet instances ready for algebraic operations.

Source:

Global Group Theory Utilities and Generators.

This module provides a collection of standalone functions to:

  1. Parse and Format permutations (Cycle notation <-> Array/ID).
  2. Generate standard mathematical groups (Symmetric, Alternating, etc.).

These functions interact directly with the globalRepo to ensure efficient memory usage (Zero-Copy where possible) and return PermutationSet instances ready for algebraic operations.

group-visualizer-cayley-graph.js

Description:

  • Cayley Graph Data Generator & 3D Physics Engine.

    Transforms Group Elements into a Graph Structure. Provides a specialized Force Simulator for symmetric 3D layout compatible with Plotly. Supports:

    • Configurable physics parameters.
    • Simulated Annealing (Jitter decay).
    • Planar flattening & Convexity forces for cycles.
    • 3D Arrows (Cones) visualization optimization.
Source:

Cayley Graph Data Generator & 3D Physics Engine.

Transforms Group Elements into a Graph Structure. Provides a specialized Force Simulator for symmetric 3D layout compatible with Plotly. Supports:

  • Configurable physics parameters.
  • Simulated Annealing (Jitter decay).
  • Planar flattening & Convexity forces for cycles.
  • 3D Arrows (Cones) visualization optimization.

group-visualizer.js

Description:

  • Group Visualization & Representation Utilities.

    This module transforms raw permutation data into human-readable structures suitable for UI rendering (GroupExplorer).

    Key Features:

    1. Generator Optimization (Redundancy check via SSA).
    2. Semantic Naming (BFS-based word problem solver: e, a, b, ab...).
    3. Cayley Table Generation (Matrix & HTML with Semantic Coloring & Tooltips).
Source:

Group Visualization & Representation Utilities.

This module transforms raw permutation data into human-readable structures suitable for UI rendering (GroupExplorer).

Key Features:

  1. Generator Optimization (Redundancy check via SSA).
  2. Semantic Naming (BFS-based word problem solver: e, a, b, ab...).
  3. Cayley Table Generation (Matrix & HTML with Semantic Coloring & Tooltips).

int-set-utils.js

Description:

  • High-Performance Set Operations for Sorted Int32Arrays.

    ASSUMPTIONS:

    1. All input arrays are SORTED in ascending order.
    2. All input arrays contain UNIQUE elements (no duplicates).
    3. Designed for zero-GC overhead where possible, though result arrays are allocated.
Source:

High-Performance Set Operations for Sorted Int32Arrays.

ASSUMPTIONS:

  1. All input arrays are SORTED in ascending order.
  2. All input arrays contain UNIQUE elements (no duplicates).
  3. Designed for zero-GC overhead where possible, though result arrays are allocated.

permutation-repository.js

Description:

  • Global Repository for Permutation Data (Memory Arena Optimized).

    ARCHITECTURE:

    1. Data Store: Flat Int32Array storing permutation values.
    2. Trie Store: Flat Int32Array (Memory Arena) managing Trie nodes.
      • Avoids JS Object allocation overhead.
      • Layout per node: [PermID, ChildPtr_0, ChildPtr_1, ..., ChildPtr_N-1]
      • Node Size = Degree + 1.
Source:

Global Repository for Permutation Data (Memory Arena Optimized).

ARCHITECTURE:

  1. Data Store: Flat Int32Array storing permutation values.
  2. Trie Store: Flat Int32Array (Memory Arena) managing Trie nodes.
    • Avoids JS Object allocation overhead.
    • Layout per node: [PermID, ChildPtr_0, ChildPtr_1, ..., ChildPtr_N-1]
    • Node Size = Degree + 1.

schreier-sims.js

Description:

  • Schreier-Sims Algorithm (SSA) Implementation.

    A high-performance engine for computing the Base and Strong Generating Set (BSGS) of a permutation group. This implementation is designed for the group-engine ecosystem, leveraging the global PermutationRepository for efficient memory management.

    KEY FEATURES:

    • Incremental Construction: Dynamically builds the BSGS as generators are added.
    • Memory Optimization: Uses flat Int32Arrays from the repository via direct heap access.
    • Dynamic Degree Handling: Adapts automatically if the underlying repository expands.
    • Transversal Maps: Uses O(1) maps for orbit representatives.

    ALGORITHM: Implements a variant of Knuth's incremental Schreier-Sims algorithm. It maintains a chain of stabilizers: G = G^(0) >= G^(1) >= ... >= G^(k) = {e} where G^(i) stabilizes the first i points of the base.

Source:

Schreier-Sims Algorithm (SSA) Implementation.

A high-performance engine for computing the Base and Strong Generating Set (BSGS) of a permutation group. This implementation is designed for the group-engine ecosystem, leveraging the global PermutationRepository for efficient memory management.

KEY FEATURES:

  • Incremental Construction: Dynamically builds the BSGS as generators are added.
  • Memory Optimization: Uses flat Int32Arrays from the repository via direct heap access.
  • Dynamic Degree Handling: Adapts automatically if the underlying repository expands.
  • Transversal Maps: Uses O(1) maps for orbit representatives.

ALGORITHM: Implements a variant of Knuth's incremental Schreier-Sims algorithm. It maintains a chain of stabilizers: G = G^(0) >= G^(1) >= ... >= G^(k) = {e} where G^(i) stabilizes the first i points of the base.