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 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_pforp < 2^31, with primality checked at construction. Dense and sparse exact linear algebra over them. RelationandPresentation: 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.MonomialPresentationfor monomial ideals, with the certified finite standard-path basis. Named constructors, each taking a field:linear_an,kronecker,dual_numbers,truncated_poly,linear_nakayamaandcyclic_nakayama(validated Kupisch series),radical_square_zero_cycle,an_with_relations, andcommutative_square(the relationab - cd).linear_an,kronecker,truncated_poly,linear_nakayama,cyclic_nakayama,radical_square_zero_cycle, andan_with_relationseach also have a_presentationform that stops at the field-freeMonomialPresentation.- Validated right modules; simples, indecomposable projectives and injectives;
direct sums with inclusions and projections.
Module::newverifies that every element of the reduced Groebner basis acts as zero. - 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. The opposite algebra reverses every relation word and then runs the pipeline again, so it is verified in its own right. 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.
Certificates:
Algebra::certificatereturns the verified certificate, andCertificate::to_canonical_jsonserializes 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.verifytakes untrusted bytes and returns aVerifiedCompletion, the only way to reachAlgebra::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_dimgives dimensions, not classes, and no extension is constructed. - 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.
- 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·bmeans "firsta, thenb" and requirestarget(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
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 basis of
Algebrais the normal words:basis[v]is the trivial pathe_vforv < 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_indexreturnsOk(None)for it, andnf_wordgives its normal form as a combination of normal words. Over a monomial ideal the two notions agree andOk(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 andJ^{k+1}is the span ofx·aoverxspanningJ^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.Dis applied throughOppositeMap, 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 Algebra;
use ;
use CompletionLimits;
use PrimeField;
use Module;
use ;
use ;
use ;
let field = new.unwrap;
// Arrows a: 0 → 1, b: 1 → 3, c: 0 → 2, d: 2 → 3.
let quiver = new.unwrap;
// The relation ab - cd. Terms may be listed in any order.
let relation = new
.unwrap;
let presentation = new.unwrap;
// Completion, certificate emission, and verification of the bytes.
let algebra = new.unwrap;
assert_eq!;
let s0 = simple;
let resolution = resolve;
let terms: = resolution.terms.iter.map.collect;
// 0 → P_3 → P_1 ⊕ P_2 → P_0 → S_0 → 0.
assert_eq!;
assert_eq!;
// τ S_0, computed by two independent routes and cross-checked.
match tau.unwrap
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 an_with_relations;
use ext_table;
use PrimeField;
use Module;
let field = new.unwrap;
let algebra = an_with_relations.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 field = new.unwrap;
let algebra = truncated_poly.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!;
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:
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.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).crates/auslander/tests/acceptance_nonmonomial.rsruns the high-level operations over three non-monomial quotients: the commutative squarekQ/(ab - cd)over F_5, the preprojective algebra of A_3 over F_2, and the inhomogeneouskQ/(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 ⊕ 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. 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.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.