auslander 0.3.0

Computational representation theory of finite-dimensional bound quiver algebras
Documentation

auslander

CI crates.io docs.rs PyPI

Computational representation theory of finite-dimensional bound quiver algebras.

Scope: finite-dimensional basic algebras kQ/I over a checked prime field, where I is a general admissible ideal, and finite-dimensional right modules. Correct before general.

A relation is a k-combination of paths of length at least 2 that all share one source and one target. ab - cd is a relation, and so is the inhomogeneous ab - cde. A monomial ideal is the case where every relation has one term. Non-uniform input is rejected, not decomposed.

Every algebra comes from one pipeline. Completion turns the relations into the reduced Groebner basis of the ideal and emits a serializable certificate. An independent verifier reads that certificate back from bytes and re-checks the whole claim. It checks both ideal inclusions: each basis element expands to a two-sided combination of the input relations, and each input relation reduces to zero over the basis. It re-enumerates every overlap and inclusion ambiguity itself, rejects a missing entry and an extra one alike, and replays every reduction trace to zero in strict order descent. It rebuilds the normal-word automaton from the leading words with its own construction, requires the certificate's automaton and finiteness claim to match it, and decides finiteness by acyclicity; an infinite claim needs a (prefix, cycle) witness the verifier replays in full. The verifier shares no completion, ambiguity enumeration, or reduction code with the engine. An Algebra value exists only after verification passes, and the engine's own output goes through the verifier like any other bytes. Dimension, the Cartan matrix, and every multiplication table are therefore exact, and nothing in the crate truncates silently.

Two types split the work. Algebra is the runtime algebra and owns its prime field. The dimension and the structure constants of a general quotient depend on the field: the ideal generated by ab - 2cd on the square quiver is the monomial ideal (ab) over F_2 and a non-monomial ideal over F_3, and the two sides differ in tau and in how rad P_0 decomposes. MonomialPresentation stays field-free and carries the combinatorics that needs no field: forbidden words, the standard-path automaton, the exact finiteness decision, dimension, and Cartan data. It is an input and analysis type; Algebra::from_monomial runs it through the same pipeline to get a runtime algebra.

Rejected input and exhausted budgets are typed and carry evidence. AlgebraBuildError::Truncated names the budget that ran out and reports the basis size, the pending ambiguity count, and the steps consumed; InfiniteDimensional carries the certificate and a (prefix, cycle) word witness, so no infinite-dimensional algebra value ever exists; RelationError names the offending term and what is wrong with it; Verification reports a verifier rejection of the engine's own certificate, an engine defect that stays a typed value rather than a panic.

Partial computations say so in their types: projective_dimension returns Bounded::Exact(n) or Bounded::AtLeast(n), a resolution prefix ends with ResolutionEnd::Finite or ResolutionEnd::Cut { at }, and no None-means-infinite convention exists anywhere.

Answers that are harder to certify follow the same discipline. Decomposition, isomorphism, and indecomposability each return a machine-checkable witness or an explicit statement that no witness was found. None of them returns a bare yes.

Contents

Algebras and modules:

  • Prime fields F_p for p < 2^31, with primality checked at construction. Dense and sparse exact linear algebra over them.
  • Relation and Presentation: validated uniform relations over a quiver and a field. Algebra: the certificate-verified runtime algebra, with the normal-word basis, the reduced Groebner basis (relations), normal forms of arbitrary paths (nf_word), sparse multiplication rows (right_mul, left_mul, mul_basis), and radical powers by row-space iteration.
  • MonomialPresentation for monomial ideals, with the certified finite standard-path basis. Named constructors, each taking a field: linear_an, kronecker, dual_numbers, truncated_poly, linear_nakayama and cyclic_nakayama (validated Kupisch series), radical_square_zero_cycle, an_with_relations, and commutative_square (the relation ab - cd). linear_an, kronecker, truncated_poly, linear_nakayama, cyclic_nakayama, radical_square_zero_cycle, and an_with_relations each also have a _presentation form that stops at the field-free MonomialPresentation.
  • Validated right modules; simples, indecomposable projectives and injectives; direct sums with inclusions and projections. Module::new verifies that every element of the reduced Groebner basis acts as zero.
  • Morphisms with checked commuting squares, hom bases, kernels, images, cokernels; radical, top, socle, and Loewy series.

Homological algebra:

  • Minimal projective resolutions via projective covers, projective dimension, ext_dim and ext_table (exact in every degree, even when the projective dimension is unknown), and global dimension.
  • Minimal injective coresolutions via injective envelopes, and injective dimension. These are the k-duals of the projective constructions over A^op and carry the same typed partiality.

Duality and the Auslander-Reiten translate:

  • The opposite algebra, the k-dual D, and the Nakayama functor ν = D ∘ Hom(−, A) applied to presentation maps, with matrices over the algebra rather than over the field (ElementMatrix). ν is exposed on maps between projective sums, which is what the translate needs, not as a functor on arbitrary modules. The opposite algebra reverses every relation word and then runs the pipeline again, so it is verified in its own right.
  • tau computes the translate two ways on every call: the Nakayama kernel ker ν(d₁) and the transpose-then-dual D(Tr M) over A^op. The results are cross-checked. The two routes share the minimal presentation and the element-matrix encoding; their back ends are independent, so agreement checks everything downstream of the shared encoding. A certified disagreement and an undecided cross-check are distinct typed errors.

Decomposition and isomorphism:

  • EndoAlgebra: End(M) as a structure-constant algebra with an exact Jacobson radical over F_p in every characteristic. The radical computation uses the Friedl-Rónyai chain, which never trusts the trace form in small characteristic.
  • decompose and krull_schmidt: verified splittings. Each summand carries a Certificate: Indecomposable means its endomorphism algebra was proved local; Undetermined means no splitting route succeeded, and the summand may or may not be indecomposable.
  • is_isomorphic returns one of three outcomes: an isomorphism verified by a checked two-sided inverse; a proof of non-isomorphism as one of five Obstruction kinds (differing dimension vectors, differing Loewy series, Hom-dimension asymmetry, the radical criterion, or an unmatched Krull-Schmidt summand); or Unknown, which means undetermined rather than "no".

Classification and enumeration:

  • Exact recognition of Dynkin and Euclidean type from the underlying graph, the generalized Cartan matrix, and the positive roots. Recognition is combinatorial; nothing in the crate decides a type numerically.
  • dynkin_indecomposables: every indecomposable of a hereditary path algebra of Dynkin type, one per positive root, constructed through BGP reflection functors (Gabriel's theorem) rather than enumerated and filtered. Preconditions are typed errors: a nonzero ideal or a non-Dynkin graph is reported as such, and a Euclidean quiver is named as Euclidean rather than merely rejected.
  • nakayama_indecomposables: every indecomposable of a Nakayama algebra, each with its certificate.

Certificates:

  • Algebra::certificate returns the verified certificate, and Certificate::to_canonical_json serializes it. The encoding is canonical and carries no timestamps and no machine data, so identical input and identical limits produce identical bytes; the decoder rejects duplicate keys, unknown keys, missing keys, and non-canonical numbers.
  • verify takes untrusted bytes and returns a VerifiedCompletion, the only way to reach Algebra::from_verified. Dump, reload, verify, rebuild is a supported workflow.

Capability matrix

What each operation can return, read off its signature. "Bounded" means the result may be a lower bound tied to a caller-supplied bound. "Undetermined possible" means the operation can end without deciding, and says so.

Operation Exact Bounded Undetermined possible
construction (Algebra::new, from_monomial, from_verified) yes, after verification no no; rejection is AlgebraBuildError
dim, cartan_matrix, nf_word, radical_power_component yes no no
resolve, coresolve the prefix, exact and minimal ResolutionEnd::Cut { at } no
projective_dimension, global_dimension, injective_dimension Bounded::Exact Bounded::AtLeast no
hom_dim, ext_dim, ext_table yes, Ext in every degree no no
injective_envelope, injective yes no no
opposite, dual, nu_of_presentation_map yes no no
tau Tau::Module or Tau::Zero, both routes cross-checked no yes: TauError::AgreementUnknown
decompose, krull_schmidt Certificate::Indecomposable, KrullSchmidtOutcome::Classes no yes: Certificate::Undetermined, KrullSchmidtOutcome::Unknown
is_isomorphic Isomorphic with a witness, NotIsomorphic with an obstruction no yes: IsoOutcome::Unknown
nakayama_indecomposables yes, every certificate is Indecomposable no no
dynkin_indecomposables one module per positive root, each with the certificate decompose produced no yes, through that certificate

tau, the injective constructions, and opposite build the opposite algebra, so each can also fail with an AlgebraBuildError from that build.

Not included

  • Ext representatives and Yoneda products. ext_dim gives dimensions, not classes, and no extension is constructed.
  • Almost-split sequences, AR quivers, and bounded AR component exploration. The crate provides tau itself, not the meshes around it; the meshes will come with universal-property verification.
  • Derived categories, tilting, and Hochschild cohomology.
  • User-defined admissible orders and one-sided Groebner bases. The order is sealed.
  • Characteristic 0.
  • Infinite-dimensional quotients. These are rejected with a proof, not supported: the verifier finds a cycle in the normal-word automaton and returns the cyclic word witness.

Conventions

Fixed crate-wide and documented on the types:

  • Paths compose left to right: the word a·b means "first a, then b" and requires target(a) == source(b).
  • The admissible order is sealed: degree-lexicographic over the arrow order, identified in every certificate as deglex-arrowid-v1. The longer word is the larger word; equal-length words compare lexicographically by arrow id. There are no user-supplied comparators.
  • Modules are right modules. A module assigns to each vertex v the row-vector space k^{dims[v]}, and to each arrow a a dims[source(a)] × dims[target(a)] matrix. A path acts by the product of its arrow matrices in word order, so M(p·q) = M(p) M(q).
  • A morphism f: M → N stores one dim M_v × dim N_v matrix per vertex, acting on row vectors (x ↦ x f_v). A-linearity is the commuting square f_{s(a)} · N(a) = M(a) · f_{t(a)} for every arrow a.
  • Composition is f.then(g), "first f, then g": at each vertex the matrix is f_v · g_v.
  • Cartan matrix: c[i][j] = dim e_i A e_j. Row i is the dimension vector of the projective P_i = e_i A; column j is the dimension vector of the injective I_j = D(A e_j).
  • The basis of Algebra is the normal words: basis[v] is the trivial path e_v for v < num_vertices, and the rest are sorted by length, then source, then lexicographic arrow word.
  • A path that is not a normal word is not zero in general. path_index returns Ok(None) for it, and nf_word gives its normal form as a combination of normal words. Over a monomial ideal the two notions agree and Ok(None) does mean zero.
  • Radical powers are computed as iterated row spaces, never by word length: J¹ is the span of the non-trivial basis words and J^{k+1} is the span of x·a over x spanning J^k. An inhomogeneous relation puts short normal words into deep radical powers.
  • The opposite algebra reverses path words, so a right A-module dualises to a right A^op-module. D is applied through OppositeMap, which carries the arrow and word translation in both directions. The reversal of a normal word need not be normal on the other side, so every reversed word is expanded to its normal form there.

Quick start

The commutative square kQ/(ab - cd), end to end: build it from a relation, resolve a simple module, and compute the translate.

use auslander::algebra::Algebra;
use auslander::ar::{Tau, tau};
use auslander::completion::CompletionLimits;
use auslander::field::PrimeField;
use auslander::module::Module;
use auslander::quiver::{ArrowId, Quiver};
use auslander::relation::{Presentation, Relation};
use auslander::resolution::{Bounded, projective_dimension, resolve};

let field = PrimeField::new(5).unwrap();
// Arrows a: 0 → 1, b: 1 → 3, c: 0 → 2, d: 2 → 3.
let quiver = Quiver::new(4, &[(0, 1), (1, 3), (0, 2), (2, 3)]).unwrap();
// The relation ab - cd. Terms may be listed in any order.
let relation = Relation::new(
    &quiver,
    field,
    vec![
        (field.one(), vec![ArrowId(0), ArrowId(1)]),
        (field.elem(-1), vec![ArrowId(2), ArrowId(3)]),
    ],
)
.unwrap();
let presentation = Presentation::new(quiver, field, vec![relation]).unwrap();
// Completion, certificate emission, and verification of the bytes.
let algebra = Algebra::new(presentation, &CompletionLimits::default()).unwrap();
assert_eq!(algebra.dim(), 9);

let s0 = Module::simple(&algebra, 0);
let resolution = resolve(&s0, 5);
let terms: Vec<&[usize]> = resolution.terms.iter().map(Module::dim_vector).collect();
// 0 → P_3 → P_1 ⊕ P_2 → P_0 → S_0 → 0.
assert_eq!(terms, vec![[1, 1, 1, 1], [0, 1, 1, 2], [0, 0, 0, 1]]);
assert_eq!(projective_dimension(&s0, 5), Bounded::Exact(2));

// τ S_0, computed by two independent routes and cross-checked.
match tau(&s0).unwrap() {
    Tau::Module(t) => assert_eq!(t.dim_vector(), [1, 1, 1, 0]),
    Tau::Zero => panic!("S_0 is not projective"),
}

The same algebra is available as commutative_square(field).

The Ext table of the simples of kA_3/(ab), the algebra of the linearly oriented quiver 0 → 1 → 2 with the composite path set to zero:

use auslander::algebra::an_with_relations;
use auslander::ext::ext_table;
use auslander::field::PrimeField;
use auslander::module::Module;

let field = PrimeField::new(5).unwrap();
let algebra = an_with_relations(3, &[(0, 2)], field).unwrap();
let s0 = Module::simple(&algebra, 0);
let s2 = Module::simple(&algebra, 2);
// [dim Ext^0, ..., dim Ext^4]: the relation from 0 to 2 sits in Ext^2.
assert_eq!(ext_table(&s0, &s2, 4).unwrap(), vec![0, 0, 1, 0, 0]);

Decomposing a module and reading the certificates:

use auslander::algebra::truncated_poly;
use auslander::decompose::{Certificate, decompose};
use auslander::field::PrimeField;
use auslander::module::{Module, direct_sum};

let field = PrimeField::new(32003).unwrap();
let algebra = truncated_poly(3, field).unwrap();
let p = Module::projective(&algebra, 0);
let s = Module::simple(&algebra, 0);
let (m, _, _) = direct_sum(&[&p, &p, &s]);
let d = decompose(&m);
assert_eq!(d.summands().len(), 3);
// Every summand was proved indecomposable, not merely left unsplit.
assert!(d.certificates().iter().all(|c| *c == Certificate::Indecomposable));

The last two examples run as tests in crates/auslander/tests/fixtures.rs. Every value in the first one is pinned by crates/auslander/tests/acceptance_nonmonomial.rs.

Python

Python bindings live in crates/auslander-py; the PyPI package is auslander. With maturin installed:

cd crates/auslander-py
maturin develop --release   # install into the active virtualenv
maturin build --release     # or build an abi3 wheel for CPython >= 3.10

The Python surface covers general relations (Algebra.from_relations(quiver, relations, field)), the certificate workflow (algebra.certificate_json() and Algebra.from_certificate(json)), and the same decision surface as the Rust crate. See crates/auslander-py/README.md.

Migrating

docs/migrating-to-0.3.md lists every breaking change with before and after code.

Building and testing

MSRV 1.88; development is pinned to Rust 1.92 via rust-toolchain.toml:

cargo test

Correctness protocol

  • Unit tests live in every module and are named after the fact they check. They include randomized dense-vs-sparse solver agreement and structural properties of resolutions: d² = 0, exactness of computed prefixes, and minimality.
  • crates/auslander/tests/fixtures.rs holds twelve textbook fixtures (A_2, A_3, D_4, k[x]/(x²), k[x]/(x³), kA_3/(ab), Kronecker-2, a radical-square-zero cycle, three Nakayama algebras, a gentle tree algebra) with hand-derived dimensions, Cartan matrices, radical series, Ext tables, and projective and global dimensions. Each fixture runs over both F_2 and F_5. Two entries are regressions from an earlier in-house prototype: hereditary Kronecker has global dimension exactly 1 (the prototype's examples database claimed infinite), and Kupisch series [2, 2, 1] runs to completion (the prototype hung on it).
  • crates/auslander/tests/acceptance_nonmonomial.rs runs the high-level operations over three non-monomial quotients: the commutative square kQ/(ab - cd) over F_5, the preprojective algebra of A_3 over F_2, and the inhomogeneous kQ/(ab - cde) over F_5. Each pinned value is hand-derived on the test that uses it, and the values that the oracle also stores agree with it.
  • The verifier is tested against a tamper corpus: a wrong schema string, a composite field, an out-of-range arrow, a non-canonical coefficient, a non-monic or non-reduced basis, an origin expansion that gives the wrong value, membership traces with dropped steps, forged contexts, absent words and non-eliminating coefficients, missing, extra, duplicated and misplaced ambiguities, and normal-word lists with a missing word, an extra word, or the wrong order. Every one is rejected with its own error.
  • Certificate bytes are byte-identical across two constructions in one process and across two fresh processes.
  • Facts that are characteristic-free are checked over a large prime as well as over F_2 and F_5. Small fields hide failure modes that depend on how rare units are: a decomposition defect survived the suite because every test ran at F_2 and F_5, where a random endomorphism of P ⊕ P is a non-unit often enough to split by luck.
  • crates/auslander/tests/qpa-oracle/ is a differential harness against QPA under GAP. The committed qpa_expected.json was produced by a real GAP+QPA run (provenance in crates/auslander/tests/qpa-oracle/README.md), and an always-on test compares the library against it. Every fixture carries its own prime field and its coefficient-bearing relations, so the non-monomial cases are compared like the monomial ones. A missing or corrupted file is a hard failure, and regression tests pin the corruption checks. native_snapshot.json is a drift snapshot of the library's own output, not an oracle. Setting QPA_ORACLE=1 invokes GAP itself and fails hard if GAP or QPA is unavailable or any value disagrees.

License

Licensed under either of the MIT license (LICENSE-MIT) or the Apache License, Version 2.0 (LICENSE-APACHE), at your option.