auslander
Computational representation theory of finite-dimensional bound quiver algebras.
Scope: finite-dimensional basic algebras kQ/I over a checked prime field, where I is an admissible monomial ideal, and finite-dimensional right modules. Correct before general.
Every construction is certified up front. MonomialAlgebra::new decides
finiteness of the standard-path basis exactly, by cycle detection on the
forbidden-subword automaton, and rejects infinite-dimensional input. Dimension,
Cartan data, and multiplication tables are therefore exact, and nothing in the
crate truncates. Module::new verifies that every forbidden word acts as zero.
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_pforp < 2^31, with primality checked at construction. Dense and sparse exact linear algebra over them. - Quivers, path words, and monomial bound quiver algebras with certified finite
standard-path bases. Named constructors:
linear_an,kronecker,dual_numbers,truncated_poly,linear_nakayamaandcyclic_nakayama(validated Kupisch series),radical_square_zero_cycle,an_with_relations. - Validated right modules; simples, indecomposable projectives and injectives; direct sums with inclusions and projections.
- Morphisms with checked commuting squares,
hombases, kernels, images, cokernels; radical, top, socle, and Loewy series.
Homological algebra:
- Minimal projective resolutions via projective covers, projective dimension,
ext_dimandext_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^opand 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. taucomputes the translate two ways on every call: the Nakayama kernelker ν(d₁)and the transpose-then-dualD(Tr M)overA^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 overF_pin every characteristic. The radical computation uses the Friedl-Rónyai chain, which never trusts the trace form in small characteristic.decomposeandkrull_schmidt: verified splittings. Each summand carries aCertificate:Indecomposablemeans its endomorphism algebra was proved local;Undeterminedmeans no splitting route succeeded, and the summand may or may not be indecomposable.is_isomorphicreturns one of three outcomes: an isomorphism verified by a checked two-sided inverse; a proof of non-isomorphism as one of fiveObstructionkinds (differing dimension vectors, differing Loewy series, Hom-dimension asymmetry, the radical criterion, or an unmatched Krull-Schmidt summand); orUnknown, 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.
Not included
Deferred on purpose:
- Non-monomial relations. These wait for the planned noncommutative Gröbner
engine (admissible orders, full remainder division, overlap and inclusion
compositions). The commutative-square algebra is excluded for exactly this
reason: its relation
ab − cdis not monomial. - Almost-split sequences, AR quivers, and bounded AR component exploration. The
crate provides
tauitself, not the meshes around it; the meshes will come with universal-property verification. - Derived categories, tilting, and Hochschild cohomology.
- Characteristic 0.
Conventions
Fixed crate-wide and documented on the types:
- Paths compose left to right: the word
a·bmeans "firsta, thenb" and requirestarget(a) == source(b). - Modules are right modules. A module assigns to each vertex
vthe row-vector spacek^{dims[v]}, and to each arrowaadims[source(a)] × dims[target(a)]matrix. A path acts by the product of its arrow matrices in word order, soM(p·q) = M(p) M(q). - A morphism
f: M → Nstores onedim M_v × dim N_vmatrix per vertex, acting on row vectors (x ↦ x f_v). A-linearity is the commuting squaref_{s(a)} · N(a) = M(a) · f_{t(a)}for every arrowa. - Composition is
f.then(g), "firstf, theng": at each vertex the matrix isf_v · g_v. - Cartan matrix:
c[i][j] = dim e_i A e_j. Rowiis the dimension vector of the projectiveP_i = e_i A; columnjis the dimension vector of the injectiveI_j = D(A e_j). - The opposite algebra reverses path words, so a right A-module dualises to a
right
A^op-module.Dis applied throughOppositeMap, which carries the arrow and word translation in both directions.
Quick start
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 an_with_relations;
use ext_table;
use PrimeField;
use Module;
let algebra = an_with_relations.unwrap;
let field = new.unwrap;
let s0 = simple;
let s2 = simple;
// [dim Ext^0, ..., dim Ext^4]: the relation from 0 to 2 sits in Ext^2.
assert_eq!;
Decomposing a module and reading the certificates:
use truncated_poly;
use ;
use PrimeField;
use ;
let algebra = truncated_poly.unwrap;
let field = new.unwrap;
let p = projective;
let s = simple;
let = direct_sum;
let d = decompose;
assert_eq!;
// Every summand was proved indecomposable, not merely left unsplit.
assert!;
Both examples run as tests in crates/auslander/tests/.
Python
Python bindings live in crates/auslander-py; the PyPI package is auslander.
With maturin installed:
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.rsholds 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).- 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 ⊕ Pis a non-unit often enough to split by luck. crates/auslander/tests/qpa-oracle/is a differential harness against QPA under GAP. The committedqpa_expected.jsonwas produced by a real GAP+QPA run (provenance incrates/auslander/tests/qpa-oracle/README.md), and an always-on test compares the library against it. A missing or corrupted file is a hard failure, and regression tests pin the corruption checks.native_snapshot.jsonis a drift snapshot of the library's own output, not an oracle. SettingQPA_ORACLE=1invokes 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.