use std::fmt;
use std::sync::Arc;
use rustc_hash::{FxHashMap, FxHashSet};
use crate::certificate::Certificate;
use crate::completion::{CompletionLimits, Outcome, TruncationDiagnostics, complete};
use crate::field::{Fp, PrimeField};
use crate::linalg::DenseMat;
use crate::order::word_cmp;
use crate::quiver::{ArrowId, PathWord, Quiver, QuiverError};
use crate::relation::{Presentation, Relation, RelationError};
use crate::verify::{CycleWitness, VerifiedCompletion, VerifyError, verify};
pub type BasisIdx = usize;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AlgebraError {
ForbiddenWordTooShort { index: usize, len: usize },
ForbiddenWordInvalid { index: usize, error: QuiverError },
InfiniteDimensional,
InvalidKupisch { reason: String },
ZeroPathOutOfRange { start: usize, len: usize },
}
impl fmt::Display for AlgebraError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::ForbiddenWordTooShort { index, len } => write!(
f,
"forbidden word {index} has length {len}; admissibility needs length >= 2"
),
Self::ForbiddenWordInvalid { index, error } => {
write!(f, "forbidden word {index} is not a path: {error}")
}
Self::InfiniteDimensional => f.write_str(
"the standard-path language is infinite; this crate supports finite-dimensional algebras only",
),
Self::InvalidKupisch { reason } => write!(f, "invalid Kupisch series: {reason}"),
Self::ZeroPathOutOfRange { start, len } => write!(
f,
"no path of length {len} starting at vertex {start} in the linear quiver"
),
}
}
}
impl std::error::Error for AlgebraError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::ForbiddenWordInvalid { error, .. } => Some(error),
_ => None,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AlgebraBuildError {
Monomial(AlgebraError),
Relation(RelationError),
InfiniteDimensional {
certificate: Box<Certificate>,
witness: CycleWitness,
},
Truncated(TruncationDiagnostics),
Verification(VerifyError),
}
impl fmt::Display for AlgebraBuildError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Monomial(error) => write!(f, "monomial presentation rejected: {error}"),
Self::Relation(error) => write!(f, "relation rejected: {error}"),
Self::InfiniteDimensional { witness, .. } => write!(
f,
"the quotient is infinite dimensional: prefix {:?}, cycle {:?}",
witness.prefix, witness.cycle
),
Self::Truncated(diagnostics) => write!(
f,
"completion ran out of budget ({:?}): basis {}, pending ambiguities {}, steps {}",
diagnostics.reason,
diagnostics.basis_len,
diagnostics.pending_ambiguities,
diagnostics.steps_used
),
Self::Verification(error) => {
write!(f, "the engine's certificate failed verification: {error}")
}
}
}
}
impl std::error::Error for AlgebraBuildError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::Monomial(error) => Some(error),
Self::Relation(error) => Some(error),
Self::Verification(error) => Some(error),
_ => None,
}
}
}
#[derive(Debug)]
pub struct MonomialPresentation {
quiver: Quiver,
forbidden: Vec<Vec<ArrowId>>,
basis: Vec<PathWord>,
index_of: FxHashMap<Vec<ArrowId>, BasisIdx>,
from: Vec<Vec<BasisIdx>>,
to: Vec<Vec<BasisIdx>>,
between: Vec<Vec<Vec<BasisIdx>>>,
}
impl MonomialPresentation {
pub fn new(
quiver: Quiver,
forbidden: Vec<Vec<ArrowId>>,
) -> Result<MonomialPresentation, AlgebraError> {
for (index, word) in forbidden.iter().enumerate() {
if word.len() < 2 {
return Err(AlgebraError::ForbiddenWordTooShort {
index,
len: word.len(),
});
}
if let Err(error) = PathWord::from_arrows(&quiver, word) {
return Err(AlgebraError::ForbiddenWordInvalid { index, error });
}
}
let forbidden = minimal_words(forbidden);
let automaton = Automaton::build(&quiver, &forbidden);
if automaton.has_cycle() {
return Err(AlgebraError::InfiniteDimensional);
}
let n = quiver.num_vertices() as usize;
let mut basis: Vec<PathWord> = (0..quiver.num_vertices())
.map(PathWord::trivial_unchecked)
.collect();
let mut state: Vec<usize> = (0..n).collect();
let mut level_start = 0;
while level_start < basis.len() {
let level_end = basis.len();
for i in level_start..level_end {
let word = basis[i].arrows().to_vec();
let target = basis[i].target();
let s = state[i];
for &a in quiver.arrows_from(target) {
if let Some(next) = automaton.step(s, a) {
let mut extended = word.clone();
extended.push(a);
basis.push(PathWord::from_arrows_unchecked(&quiver, extended));
state.push(next);
}
}
}
level_start = level_end;
}
let (index_of, from, to, between) = index_basis(&quiver, &basis);
Ok(MonomialPresentation {
quiver,
forbidden,
basis,
index_of,
from,
to,
between,
})
}
#[inline]
pub fn dim(&self) -> usize {
self.basis.len()
}
#[inline]
pub fn quiver(&self) -> &Quiver {
&self.quiver
}
#[inline]
pub fn basis(&self) -> &[PathWord] {
&self.basis
}
#[inline]
pub fn forbidden(&self) -> &[Vec<ArrowId>] {
&self.forbidden
}
pub fn path_index(&self, path: &PathWord) -> Result<Option<BasisIdx>, QuiverError> {
path.validate_in(&self.quiver)?;
if path.is_trivial() {
Ok(Some(path.source() as usize))
} else {
Ok(self.index_of.get(path.arrows()).copied())
}
}
pub fn vertex_idempotent(&self, v: u32) -> BasisIdx {
assert!(v < self.quiver.num_vertices());
v as usize
}
#[inline]
pub fn paths_from(&self, v: u32) -> &[BasisIdx] {
&self.from[v as usize]
}
#[inline]
pub fn paths_to(&self, v: u32) -> &[BasisIdx] {
&self.to[v as usize]
}
#[inline]
pub fn paths_between(&self, u: u32, v: u32) -> &[BasisIdx] {
&self.between[u as usize][v as usize]
}
pub fn cartan_matrix(&self) -> Vec<Vec<usize>> {
self.between
.iter()
.map(|row| row.iter().map(Vec::len).collect())
.collect()
}
}
type BasisIndexes = (
FxHashMap<Vec<ArrowId>, BasisIdx>,
Vec<Vec<BasisIdx>>,
Vec<Vec<BasisIdx>>,
Vec<Vec<Vec<BasisIdx>>>,
);
fn index_basis(quiver: &Quiver, basis: &[PathWord]) -> BasisIndexes {
let n = quiver.num_vertices() as usize;
let mut index_of = FxHashMap::default();
for (i, p) in basis.iter().enumerate() {
if !p.is_trivial() {
index_of.insert(p.arrows().to_vec(), i);
}
}
let mut from = vec![Vec::new(); n];
let mut to = vec![Vec::new(); n];
let mut between = vec![vec![Vec::new(); n]; n];
for (i, p) in basis.iter().enumerate() {
from[p.source() as usize].push(i);
to[p.target() as usize].push(i);
between[p.source() as usize][p.target() as usize].push(i);
}
(index_of, from, to, between)
}
#[derive(Debug)]
pub struct Algebra {
quiver: Quiver,
field: PrimeField,
relations: Vec<Relation>,
certificate: Certificate,
limits: CompletionLimits,
basis: Vec<PathWord>,
index_of: FxHashMap<Vec<ArrowId>, BasisIdx>,
from: Vec<Vec<BasisIdx>>,
to: Vec<Vec<BasisIdx>>,
between: Vec<Vec<Vec<BasisIdx>>>,
right_mul: Vec<Vec<Vec<(BasisIdx, Fp)>>>,
left_mul: Vec<Vec<Vec<(BasisIdx, Fp)>>>,
}
impl Algebra {
pub fn new(
presentation: Presentation,
limits: &CompletionLimits,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let certificate = match complete(&presentation, limits) {
Outcome::Complete(certificate) => certificate,
Outcome::Truncated(diagnostics) => {
return Err(AlgebraBuildError::Truncated(diagnostics));
}
};
match verify(&certificate.to_canonical_json()) {
Ok(verified) => Ok(Algebra::from_verified_with_limits(verified, limits)),
Err(VerifyError::InfiniteDimensional { witness }) => {
Err(AlgebraBuildError::InfiniteDimensional {
certificate: Box::new(certificate),
witness,
})
}
Err(error) => Err(AlgebraBuildError::Verification(error)),
}
}
pub fn from_verified(verified: VerifiedCompletion) -> Arc<Algebra> {
Algebra::from_verified_with_limits(verified, &CompletionLimits::default())
}
pub fn from_verified_with_limits(
verified: VerifiedCompletion,
limits: &CompletionLimits,
) -> Arc<Algebra> {
let quiver = verified.quiver().clone();
let field = verified.field();
let relations: Vec<Relation> = verified
.basis()
.iter()
.map(|element| {
let terms = element
.iter()
.map(|(coeff, word)| (*coeff, word.arrows().to_vec()))
.collect();
Relation::new(&quiver, field, terms)
.expect("a verified basis element is a valid relation")
})
.collect();
let basis = verified.normal_words().to_vec();
let (index_of, from, to, between) = index_basis(&quiver, &basis);
let mut algebra = Algebra {
quiver,
field,
relations,
certificate: verified.certificate().clone(),
limits: limits.clone(),
basis,
index_of,
from,
to,
between,
right_mul: Vec::new(),
left_mul: Vec::new(),
};
let num_arrows = algebra.quiver.num_arrows();
let mut right_mul = vec![vec![Vec::new(); num_arrows]; algebra.basis.len()];
let mut left_mul = vec![vec![Vec::new(); algebra.basis.len()]; num_arrows];
for (i, p) in algebra.basis.iter().enumerate() {
for &a in algebra.quiver.arrows_from(p.target()) {
let mut word = p.arrows().to_vec();
word.push(a);
right_mul[i][a.index()] = algebra.nf_arrow_word(word);
}
for &a in algebra.quiver.arrows_to(p.source()) {
let mut word = vec![a];
word.extend_from_slice(p.arrows());
left_mul[a.index()][i] = algebra.nf_arrow_word(word);
}
}
algebra.right_mul = right_mul;
algebra.left_mul = left_mul;
Arc::new(algebra)
}
pub fn from_monomial(
field: PrimeField,
presentation: &MonomialPresentation,
limits: &CompletionLimits,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let quiver = presentation.quiver().clone();
let relations = presentation
.forbidden()
.iter()
.map(|word| Relation::new(&quiver, field, vec![(field.one(), word.clone())]))
.collect::<Result<Vec<Relation>, RelationError>>()
.map_err(AlgebraBuildError::Relation)?;
let bundled =
Presentation::new(quiver, field, relations).map_err(AlgebraBuildError::Relation)?;
let algebra = Algebra::new(bundled, limits)?;
debug_assert_eq!(
algebra.basis(),
presentation.basis(),
"the normal words of a monomial ideal are its standard paths"
);
Ok(algebra)
}
#[inline]
pub fn certificate(&self) -> &Certificate {
&self.certificate
}
#[inline]
pub fn completion_limits(&self) -> &CompletionLimits {
&self.limits
}
#[inline]
pub fn dim(&self) -> usize {
self.basis.len()
}
#[inline]
pub fn quiver(&self) -> &Quiver {
&self.quiver
}
#[inline]
pub fn field(&self) -> PrimeField {
self.field
}
#[inline]
pub fn basis(&self) -> &[PathWord] {
&self.basis
}
#[inline]
pub fn relations(&self) -> &[Relation] {
&self.relations
}
pub fn path_index(&self, path: &PathWord) -> Result<Option<BasisIdx>, QuiverError> {
path.validate_in(&self.quiver)?;
if path.is_trivial() {
Ok(Some(path.source() as usize))
} else {
Ok(self.index_of.get(path.arrows()).copied())
}
}
pub fn vertex_idempotent(&self, v: u32) -> BasisIdx {
assert!(v < self.quiver.num_vertices());
v as usize
}
#[inline]
pub fn paths_from(&self, v: u32) -> &[BasisIdx] {
&self.from[v as usize]
}
#[inline]
pub fn paths_to(&self, v: u32) -> &[BasisIdx] {
&self.to[v as usize]
}
#[inline]
pub fn paths_between(&self, u: u32, v: u32) -> &[BasisIdx] {
&self.between[u as usize][v as usize]
}
pub fn cartan_matrix(&self) -> Vec<Vec<usize>> {
self.between
.iter()
.map(|row| row.iter().map(Vec::len).collect())
.collect()
}
#[inline]
pub fn right_mul(&self, i: BasisIdx, a: ArrowId) -> &[(BasisIdx, Fp)] {
&self.right_mul[i][a.index()]
}
#[inline]
pub fn left_mul(&self, a: ArrowId, i: BasisIdx) -> &[(BasisIdx, Fp)] {
&self.left_mul[a.index()][i]
}
pub fn nf_word(&self, word: &PathWord) -> Result<Vec<(BasisIdx, Fp)>, QuiverError> {
word.validate_in(&self.quiver)?;
if word.is_trivial() {
return Ok(vec![(word.source() as usize, self.field.one())]);
}
Ok(self.nf_arrow_word(word.arrows().to_vec()))
}
pub fn mul_basis(&self, p: BasisIdx, q: BasisIdx) -> Vec<(BasisIdx, Fp)> {
let (left, right) = (&self.basis[p], &self.basis[q]);
if left.target() != right.source() {
return Vec::new();
}
if left.is_trivial() {
return vec![(q, self.field.one())];
}
if right.is_trivial() {
return vec![(p, self.field.one())];
}
let mut word = left.arrows().to_vec();
word.extend_from_slice(right.arrows());
self.nf_arrow_word(word)
}
fn nf_arrow_word(&self, word: Vec<ArrowId>) -> Vec<(BasisIdx, Fp)> {
let mut poly: Vec<(Fp, Vec<ArrowId>)> = vec![(self.field.one(), word)];
let mut out: Vec<(BasisIdx, Fp)> = Vec::new();
while let Some((coeff, word)) = poly.first().cloned() {
match self.leftmost_reduction(&word) {
None => {
let index = *self
.index_of
.get(&word)
.expect("the verifier enumerated every irreducible word");
out.push((index, coeff));
poly.remove(0);
}
Some((relation, position)) => {
let lead_len = relation.leading().1.len();
let left = &word[..position];
let right = &word[position + lead_len..];
let scale = self.field.neg(coeff);
poly = add_scaled(self.field, &poly, scale, left, relation.terms(), right);
}
}
}
out.sort_unstable_by_key(|&(index, _)| index);
out
}
fn leftmost_reduction(&self, word: &[ArrowId]) -> Option<(&Relation, usize)> {
self.relations.iter().find_map(|relation| {
let lead = relation.leading().1.arrows();
if lead.len() > word.len() {
return None;
}
(0..=word.len() - lead.len())
.find(|&at| &word[at..at + lead.len()] == lead)
.map(|at| (relation, at))
})
}
pub fn radical_power_component(&self, u: u32, v: u32, k: usize) -> Vec<Vec<Fp>> {
assert!(u < self.quiver.num_vertices() && v < self.quiver.num_vertices());
let power = self.radical_power(k);
let component = &power[u as usize][v as usize];
(0..component.rows())
.map(|r| component.row(r).to_vec())
.collect()
}
pub fn nilpotency_degree(&self) -> usize {
let mut k = 0;
let mut power = self.radical_power(0);
loop {
let total: usize = power.iter().flatten().map(DenseMat::rows).sum();
if total == 0 {
return k;
}
let next = self.radical_step(&power);
let next_total: usize = next.iter().flatten().map(DenseMat::rows).sum();
assert!(
next_total < total,
"radical iteration stalled on a nonzero power; this is a bug in auslander"
);
power = next;
k += 1;
}
}
fn radical_power(&self, k: usize) -> Vec<Vec<DenseMat>> {
let n = self.quiver.num_vertices() as usize;
let mut power: Vec<Vec<DenseMat>> = (0..n)
.map(|u| {
(0..n)
.map(|v| DenseMat::identity(self.between[u][v].len()))
.collect()
})
.collect();
for _ in 0..k {
power = self.radical_step(&power);
}
power
}
fn radical_step(&self, power: &[Vec<DenseMat>]) -> Vec<Vec<DenseMat>> {
let n = self.quiver.num_vertices() as usize;
let positions = self.component_positions();
let mut rows: Vec<Vec<Vec<Vec<Fp>>>> = vec![vec![Vec::new(); n]; n];
for u in 0..n {
for (w, component) in power[u].iter().enumerate() {
let word_indices = &self.between[u][w];
for r in 0..component.rows() {
let row = component.row(r);
for &a in self.quiver.arrows_from(w as u32) {
let v = self.quiver.target(a) as usize;
let mut image = vec![self.field.zero(); self.between[u][v].len()];
for (pos, &c) in row.iter().enumerate() {
if c.is_zero() {
continue;
}
for &(q, qc) in self.right_mul(word_indices[pos], a) {
let slot = &mut image[positions[q]];
*slot = self.field.add(*slot, self.field.mul(c, qc));
}
}
if image.iter().any(|c| !c.is_zero()) {
rows[u][v].push(image);
}
}
}
}
}
(0..n)
.map(|u| {
(0..n)
.map(|v| {
let cols = self.between[u][v].len();
let mut mat = DenseMat::zero(rows[u][v].len(), cols);
for (r, row) in rows[u][v].iter().enumerate() {
for (c, &value) in row.iter().enumerate() {
mat.set(r, c, value);
}
}
mat.row_space_basis(&self.field)
})
.collect()
})
.collect()
}
fn component_positions(&self) -> Vec<usize> {
let mut positions = vec![usize::MAX; self.basis.len()];
for row in &self.between {
for component in row {
for (i, &b) in component.iter().enumerate() {
positions[b] = i;
}
}
}
positions
}
}
fn add_scaled(
field: PrimeField,
poly: &[(Fp, Vec<ArrowId>)],
scale: Fp,
left: &[ArrowId],
terms: &[(Fp, PathWord)],
right: &[ArrowId],
) -> Vec<(Fp, Vec<ArrowId>)> {
let addend: Vec<(Fp, Vec<ArrowId>)> = terms
.iter()
.map(|(c, w)| {
let mut word = left.to_vec();
word.extend_from_slice(w.arrows());
word.extend_from_slice(right);
(field.mul(scale, *c), word)
})
.collect();
let mut merged = Vec::with_capacity(poly.len() + addend.len());
let mut i = 0;
let mut j = 0;
while i < poly.len() && j < addend.len() {
match word_cmp(&poly[i].1, &addend[j].1) {
std::cmp::Ordering::Greater => {
merged.push(poly[i].clone());
i += 1;
}
std::cmp::Ordering::Less => {
merged.push(addend[j].clone());
j += 1;
}
std::cmp::Ordering::Equal => {
let sum = field.add(poly[i].0, addend[j].0);
if !sum.is_zero() {
merged.push((sum, poly[i].1.clone()));
}
i += 1;
j += 1;
}
}
}
merged.extend_from_slice(&poly[i..]);
merged.extend(addend.into_iter().skip(j));
merged
}
fn minimal_words(mut words: Vec<Vec<ArrowId>>) -> Vec<Vec<ArrowId>> {
words.sort();
words.dedup();
words.sort_by_key(Vec::len);
let mut minimal: Vec<Vec<ArrowId>> = Vec::new();
for word in words {
let contains_kept = minimal
.iter()
.any(|v| word.windows(v.len()).any(|w| w == v.as_slice()));
if !contains_kept {
minimal.push(word);
}
}
minimal
}
struct Automaton {
trans: Vec<Vec<Option<usize>>>,
}
impl Automaton {
fn build(quiver: &Quiver, forbidden: &[Vec<ArrowId>]) -> Automaton {
let n = quiver.num_vertices() as usize;
let mut prefixes: Vec<Vec<ArrowId>> = Vec::new();
let mut prefix_index: FxHashMap<Vec<ArrowId>, usize> = FxHashMap::default();
for word in forbidden {
for len in 1..word.len() {
let prefix = word[..len].to_vec();
if !prefix_index.contains_key(&prefix) {
prefix_index.insert(prefix.clone(), prefixes.len());
prefixes.push(prefix);
}
}
}
let forbidden_set: FxHashSet<&[ArrowId]> = forbidden.iter().map(Vec::as_slice).collect();
let num_states = n + prefixes.len();
let mut trans = vec![vec![None; quiver.num_arrows()]; num_states];
for (s, row) in trans.iter_mut().enumerate() {
let (word, vertex): (&[ArrowId], u32) = if s < n {
(&[], s as u32)
} else {
let w = prefixes[s - n].as_slice();
(w, quiver.target(w[w.len() - 1]))
};
for &a in quiver.arrows_from(vertex) {
let mut extended = word.to_vec();
extended.push(a);
let mut next = Some(quiver.target(a) as usize);
for start in 0..extended.len() {
let suffix = &extended[start..];
if forbidden_set.contains(suffix) {
next = None;
break;
}
if let Some(&k) = prefix_index.get(suffix) {
next = Some(n + k);
break;
}
}
row[a.index()] = next;
}
}
Automaton { trans }
}
fn has_cycle(&self) -> bool {
let m = self.trans.len();
let mut indegree = vec![0usize; m];
for row in &self.trans {
for &t in row.iter().flatten() {
indegree[t] += 1;
}
}
let mut stack: Vec<usize> = (0..m).filter(|&s| indegree[s] == 0).collect();
let mut visited = 0;
while let Some(s) = stack.pop() {
visited += 1;
for &t in self.trans[s].iter().flatten() {
indegree[t] -= 1;
if indegree[t] == 0 {
stack.push(t);
}
}
}
visited < m
}
#[inline]
fn step(&self, s: usize, a: ArrowId) -> Option<usize> {
self.trans[s][a.index()]
}
}
pub fn monomial_completion_limits(presentation: &MonomialPresentation) -> CompletionLimits {
let defaults = CompletionLimits::default();
let longest = presentation
.forbidden()
.iter()
.map(Vec::len)
.max()
.unwrap_or(0);
CompletionLimits {
max_basis: defaults.max_basis.max(presentation.forbidden().len()),
max_word_len: defaults
.max_word_len
.max(longest.saturating_mul(2).saturating_sub(1)),
max_steps: defaults.max_steps.max(
presentation
.dim()
.saturating_add(presentation.forbidden().len()),
),
}
}
fn from_monomial_derived(
field: PrimeField,
presentation: &MonomialPresentation,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
Algebra::from_monomial(
field,
presentation,
&monomial_completion_limits(presentation),
)
}
fn linear_quiver(n: usize) -> Quiver {
let n = u32::try_from(n).expect("vertex count fits in u32");
let arrows: Vec<(u32, u32)> = (0..n.saturating_sub(1)).map(|i| (i, i + 1)).collect();
Quiver::new(n, &arrows).expect("endpoints in range by construction")
}
fn cyclic_quiver(n: usize) -> Quiver {
let arrows: Vec<(u32, u32)> = (0..n).map(|i| (i as u32, ((i + 1) % n) as u32)).collect();
Quiver::new(u32::try_from(n).expect("vertex count fits in u32"), &arrows)
.expect("endpoints in range by construction")
}
pub fn linear_an_presentation(n: usize) -> MonomialPresentation {
MonomialPresentation::new(linear_quiver(n), Vec::new())
.expect("acyclic quiver without relations is finite-dimensional")
}
pub fn linear_an(n: usize, field: PrimeField) -> Arc<Algebra> {
from_monomial_derived(field, &linear_an_presentation(n))
.expect("the zero ideal over an acyclic quiver completes")
}
pub fn kronecker_presentation(m: usize) -> MonomialPresentation {
let arrows = vec![(0u32, 1u32); m];
let quiver = Quiver::new(2, &arrows).expect("endpoints in range by construction");
MonomialPresentation::new(quiver, Vec::new())
.expect("acyclic quiver without relations is finite-dimensional")
}
pub fn kronecker(m: usize, field: PrimeField) -> Arc<Algebra> {
from_monomial_derived(field, &kronecker_presentation(m))
.expect("the zero ideal over an acyclic quiver completes")
}
pub fn dual_numbers(field: PrimeField) -> Arc<Algebra> {
truncated_poly(2, field).expect("x² is an admissible relation")
}
pub fn truncated_poly_presentation(n: usize) -> Result<MonomialPresentation, AlgebraError> {
let quiver = Quiver::new(1, &[(0, 0)]).expect("endpoints in range by construction");
MonomialPresentation::new(quiver, vec![vec![ArrowId(0); n]])
}
pub fn truncated_poly(n: usize, field: PrimeField) -> Result<Arc<Algebra>, AlgebraBuildError> {
let presentation = truncated_poly_presentation(n).map_err(AlgebraBuildError::Monomial)?;
from_monomial_derived(field, &presentation)
}
pub fn linear_nakayama_presentation(
kupisch: &[usize],
) -> Result<MonomialPresentation, AlgebraError> {
let n = kupisch.len();
if n == 0 {
return Err(AlgebraError::InvalidKupisch {
reason: "series is empty".to_string(),
});
}
if kupisch[n - 1] != 1 {
return Err(AlgebraError::InvalidKupisch {
reason: format!(
"linear series must end with 1, got c[{}] = {}",
n - 1,
kupisch[n - 1]
),
});
}
for i in 0..n - 1 {
if kupisch[i] < 2 {
return Err(AlgebraError::InvalidKupisch {
reason: format!("c[{i}] = {} but interior entries need c >= 2", kupisch[i]),
});
}
if kupisch[i + 1] < kupisch[i] - 1 {
return Err(AlgebraError::InvalidKupisch {
reason: format!(
"c[{}] = {} violates c[i+1] >= c[i] - 1 = {}",
i + 1,
kupisch[i + 1],
kupisch[i] - 1
),
});
}
}
let mut forbidden = Vec::new();
for (i, &c) in kupisch.iter().enumerate() {
if i + c <= n - 1 {
forbidden.push((i..i + c).map(|j| ArrowId(j as u32)).collect());
}
}
MonomialPresentation::new(linear_quiver(n), forbidden)
}
pub fn linear_nakayama(
kupisch: &[usize],
field: PrimeField,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let presentation =
linear_nakayama_presentation(kupisch).map_err(AlgebraBuildError::Monomial)?;
from_monomial_derived(field, &presentation)
}
pub fn cyclic_nakayama_presentation(
kupisch: &[usize],
) -> Result<MonomialPresentation, AlgebraError> {
let n = kupisch.len();
if n == 0 {
return Err(AlgebraError::InvalidKupisch {
reason: "series is empty".to_string(),
});
}
for (i, &c) in kupisch.iter().enumerate() {
if c < 2 {
return Err(AlgebraError::InvalidKupisch {
reason: format!("c[{i}] = {c} but cyclic entries need c >= 2"),
});
}
if kupisch[(i + 1) % n] < c - 1 {
return Err(AlgebraError::InvalidKupisch {
reason: format!(
"c[{}] = {} violates cyclic c[i+1] >= c[i] - 1 = {}",
(i + 1) % n,
kupisch[(i + 1) % n],
c - 1
),
});
}
}
let forbidden: Vec<Vec<ArrowId>> = (0..n)
.map(|i| {
(0..kupisch[i])
.map(|j| ArrowId(((i + j) % n) as u32))
.collect()
})
.collect();
MonomialPresentation::new(cyclic_quiver(n), forbidden)
}
pub fn cyclic_nakayama(
kupisch: &[usize],
field: PrimeField,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let presentation =
cyclic_nakayama_presentation(kupisch).map_err(AlgebraBuildError::Monomial)?;
from_monomial_derived(field, &presentation)
}
pub fn radical_square_zero_cycle_presentation(n: usize) -> MonomialPresentation {
let forbidden: Vec<Vec<ArrowId>> = (0..n)
.map(|i| vec![ArrowId(i as u32), ArrowId(((i + 1) % n) as u32)])
.collect();
MonomialPresentation::new(cyclic_quiver(n), forbidden)
.expect("rad² = 0 leaves only vertices and arrows")
}
pub fn radical_square_zero_cycle(n: usize, field: PrimeField) -> Arc<Algebra> {
from_monomial_derived(field, &radical_square_zero_cycle_presentation(n))
.expect("rad² = 0 leaves only vertices and arrows")
}
pub fn an_with_relations_presentation(
n: usize,
zero_paths: &[(usize, usize)],
) -> Result<MonomialPresentation, AlgebraError> {
for &(start, len) in zero_paths {
if n == 0 || start + len > n - 1 {
return Err(AlgebraError::ZeroPathOutOfRange { start, len });
}
}
let forbidden = zero_paths
.iter()
.map(|&(start, len)| (start..start + len).map(|j| ArrowId(j as u32)).collect())
.collect();
MonomialPresentation::new(linear_quiver(n), forbidden)
}
pub fn an_with_relations(
n: usize,
zero_paths: &[(usize, usize)],
field: PrimeField,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let presentation =
an_with_relations_presentation(n, zero_paths).map_err(AlgebraBuildError::Monomial)?;
from_monomial_derived(field, &presentation)
}
pub fn commutative_square(field: PrimeField) -> Arc<Algebra> {
let quiver = Quiver::new(4, &[(0, 1), (1, 3), (0, 2), (2, 3)]).expect("endpoints in range");
let relation = Relation::new(
&quiver,
field,
vec![
(field.one(), vec![ArrowId(0), ArrowId(1)]),
(field.elem(-1), vec![ArrowId(2), ArrowId(3)]),
],
)
.expect("ab - cd is a valid uniform relation");
let presentation = Presentation::new(quiver, field, vec![relation])
.expect("the relation was built over this quiver and field");
Algebra::new(presentation, &CompletionLimits::default())
.expect("the commutative square is finite dimensional")
}
#[cfg(test)]
mod tests {
use super::*;
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn word(algebra: &Algebra, arrows: &[u32]) -> PathWord {
let ids: Vec<ArrowId> = arrows.iter().copied().map(ArrowId).collect();
PathWord::from_arrows(algebra.quiver(), &ids).unwrap()
}
#[test]
fn dual_numbers_has_basis_e_x() {
let a = dual_numbers(f5());
assert_eq!(a.dim(), 2);
assert!(a.basis()[0].is_trivial());
assert_eq!(a.basis()[1].arrows(), &[ArrowId(0)]);
}
#[test]
fn truncated_poly_3_has_dim_3() {
let a = truncated_poly(3, f5()).unwrap();
assert_eq!(a.dim(), 3);
assert_eq!(a.basis()[2].len(), 2);
}
#[test]
fn truncated_poly_65_succeeds_with_derived_limits() {
let a = truncated_poly(65, f5()).unwrap();
assert_eq!(a.dim(), 65);
assert_eq!(a.completion_limits().max_word_len, 129);
let presentation = truncated_poly_presentation(65).unwrap();
assert!(matches!(
Algebra::from_monomial(f5(), &presentation, &CompletionLimits::default()),
Err(AlgebraBuildError::Truncated(diagnostics))
if diagnostics.reason == crate::completion::TruncationReason::WordLenBudget
));
}
#[test]
fn monomial_completion_limits_never_fall_below_the_defaults() {
let presentation = truncated_poly_presentation(3).unwrap();
assert_eq!(
monomial_completion_limits(&presentation),
CompletionLimits::default()
);
let long = truncated_poly_presentation(100).unwrap();
let limits = monomial_completion_limits(&long);
assert_eq!(limits.max_word_len, 199);
assert_eq!(limits.max_basis, CompletionLimits::default().max_basis);
assert_eq!(limits.max_steps, CompletionLimits::default().max_steps);
}
#[test]
fn from_verified_keeps_default_limits_and_with_limits_stores_them() {
let a = truncated_poly(65, f5()).unwrap();
let bytes = a.certificate().to_canonical_json();
let reloaded = Algebra::from_verified(verify(&bytes).unwrap());
assert_eq!(reloaded.completion_limits(), &CompletionLimits::default());
let raised = CompletionLimits {
max_word_len: 129,
..CompletionLimits::default()
};
let preserved = Algebra::from_verified_with_limits(verify(&bytes).unwrap(), &raised);
assert_eq!(preserved.completion_limits(), &raised);
}
#[test]
fn truncated_poly_rejects_n_below_2() {
assert!(matches!(
truncated_poly(1, f5()),
Err(AlgebraBuildError::Monomial(
AlgebraError::ForbiddenWordTooShort { index: 0, len: 1 }
))
));
}
#[test]
fn linear_a3_dim_and_cartan() {
let a = linear_an(3, f5());
assert_eq!(a.dim(), 6);
assert_eq!(
a.cartan_matrix(),
vec![vec![1, 1, 1], vec![0, 1, 1], vec![0, 0, 1]]
);
}
#[test]
fn linear_a3_paths_between_counts() {
let a = linear_an(3, f5());
for u in 0..3 {
for v in 0..3 {
let expected = usize::from(u <= v);
assert_eq!(a.paths_between(u, v).len(), expected, "({u}, {v})");
}
}
}
#[test]
fn a3_mod_ab_has_basis_without_ab() {
let a = an_with_relations(3, &[(0, 2)], f5()).unwrap();
assert_eq!(a.dim(), 5);
for v in 0..3 {
assert!(a.basis()[v as usize].is_trivial());
}
assert_eq!(a.path_index(&word(&a, &[0])), Ok(Some(3)));
assert_eq!(a.path_index(&word(&a, &[1])), Ok(Some(4)));
assert_eq!(a.path_index(&word(&a, &[0, 1])), Ok(None));
assert_eq!(a.nf_word(&word(&a, &[0, 1])), Ok(Vec::new()));
}
#[test]
fn kronecker_2_has_dim_4() {
let a = kronecker(2, f5());
assert_eq!(a.dim(), 4);
assert_eq!(a.cartan_matrix(), vec![vec![1, 2], vec![0, 1]]);
}
#[test]
fn linear_nakayama_3_2_1_is_path_algebra_a3() {
let a = linear_nakayama(&[3, 2, 1], f5()).unwrap();
assert_eq!(a.dim(), 6);
assert!(a.relations().is_empty());
}
#[test]
fn linear_nakayama_2_2_1_is_a3_mod_ab() {
let a = linear_nakayama(&[2, 2, 1], f5()).unwrap();
assert_eq!(a.dim(), 5);
assert_eq!(a.relations().len(), 1);
assert_eq!(a.relations()[0].terms(), &[(f5().one(), word(&a, &[0, 1]))]);
}
#[test]
fn cyclic_nakayama_2_2_2_has_dim_6() {
let a = cyclic_nakayama(&[2, 2, 2], f5()).unwrap();
assert_eq!(a.dim(), 6);
}
#[test]
fn cyclic_nakayama_3_3_3_has_dim_9() {
let a = cyclic_nakayama(&[3, 3, 3], f5()).unwrap();
assert_eq!(a.dim(), 9);
}
#[test]
fn linear_kupisch_3_3_2_rejected() {
assert!(matches!(
linear_nakayama(&[3, 3, 2], f5()),
Err(AlgebraBuildError::Monomial(
AlgebraError::InvalidKupisch { .. }
))
));
}
#[test]
fn linear_kupisch_drop_violation_rejected() {
assert!(matches!(
linear_nakayama(&[4, 2, 1], f5()),
Err(AlgebraBuildError::Monomial(
AlgebraError::InvalidKupisch { .. }
))
));
}
#[test]
fn cyclic_kupisch_entry_below_2_rejected() {
assert!(matches!(
cyclic_nakayama(&[2, 1, 2], f5()),
Err(AlgebraBuildError::Monomial(
AlgebraError::InvalidKupisch { .. }
))
));
}
#[test]
fn cyclic_kupisch_drop_violation_rejected() {
assert!(matches!(
cyclic_nakayama(&[4, 2, 2], f5()),
Err(AlgebraBuildError::Monomial(
AlgebraError::InvalidKupisch { .. }
))
));
}
#[test]
fn loop_without_relations_is_infinite_dimensional() {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
assert_eq!(
MonomialPresentation::new(quiver, Vec::new()).unwrap_err(),
AlgebraError::InfiniteDimensional
);
}
#[test]
fn cycle_without_relations_is_infinite_dimensional() {
let quiver = Quiver::new(3, &[(0, 1), (1, 2), (2, 0)]).unwrap();
assert_eq!(
MonomialPresentation::new(quiver, Vec::new()).unwrap_err(),
AlgebraError::InfiniteDimensional
);
}
#[test]
fn pipeline_reports_infinite_dimension_with_a_witness() {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
let presentation = Presentation::new(quiver, f5(), Vec::new()).unwrap();
match Algebra::new(presentation, &CompletionLimits::default()) {
Err(AlgebraBuildError::InfiniteDimensional { witness, .. }) => {
assert!(!witness.cycle.is_empty());
}
other => panic!("expected InfiniteDimensional, got {other:?}"),
}
}
#[test]
fn forbidden_words_reduced_to_minimal() {
let quiver = Quiver::new(4, &[(0, 1), (1, 2), (2, 3)]).unwrap();
let m = MonomialPresentation::new(
quiver,
vec![
vec![ArrowId(0), ArrowId(1), ArrowId(2)],
vec![ArrowId(0), ArrowId(1)],
],
)
.unwrap();
assert_eq!(m.forbidden(), &[vec![ArrowId(0), ArrowId(1)]]);
assert_eq!(m.dim(), 8); }
#[test]
fn loop_with_x_cubed_forbidden_is_finite() {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
let m = MonomialPresentation::new(quiver, vec![vec![ArrowId(0); 3]]).unwrap();
assert_eq!(m.dim(), 3);
let a = Algebra::from_monomial(f5(), &m, &CompletionLimits::default()).unwrap();
assert_eq!(a.dim(), 3);
}
#[test]
fn two_loops_with_xx_yy_forbidden_is_infinite() {
let quiver = Quiver::new(1, &[(0, 0), (0, 0)]).unwrap();
let result = MonomialPresentation::new(
quiver,
vec![vec![ArrowId(0), ArrowId(0)], vec![ArrowId(1), ArrowId(1)]],
);
assert_eq!(result.unwrap_err(), AlgebraError::InfiniteDimensional);
}
#[test]
fn two_loops_with_rad_square_zero_has_dim_3() {
let quiver = Quiver::new(1, &[(0, 0), (0, 0)]).unwrap();
let forbidden = vec![
vec![ArrowId(0), ArrowId(0)],
vec![ArrowId(0), ArrowId(1)],
vec![ArrowId(1), ArrowId(0)],
vec![ArrowId(1), ArrowId(1)],
];
let m = MonomialPresentation::new(quiver, forbidden).unwrap();
assert_eq!(m.dim(), 3);
}
#[test]
fn radical_square_zero_cycle_3_has_dim_6() {
let a = radical_square_zero_cycle(3, f5());
assert_eq!(a.dim(), 6);
assert_eq!(a.paths_from(0).len(), 2); }
#[test]
fn multiplication_tables_match_path_composition() {
let a = linear_an(3, f5());
let one = f5().one();
let (ia, ib) = (ArrowId(0), ArrowId(1));
let a_idx = a.path_index(&word(&a, &[0])).unwrap().unwrap();
let ab_idx = a.path_index(&word(&a, &[0, 1])).unwrap().unwrap();
assert_eq!(a.right_mul(a.vertex_idempotent(0), ia), &[(a_idx, one)]);
assert_eq!(a.right_mul(a_idx, ib), &[(ab_idx, one)]);
assert_eq!(
a.left_mul(ia, a.path_index(&word(&a, &[1])).unwrap().unwrap()),
&[(ab_idx, one)]
);
assert!(a.right_mul(a_idx, ia).is_empty()); }
#[test]
fn multiplication_by_forbidden_extension_is_zero() {
let a = an_with_relations(3, &[(0, 2)], f5()).unwrap();
let a_idx = a.path_index(&word(&a, &[0])).unwrap().unwrap();
assert!(a.right_mul(a_idx, ArrowId(1)).is_empty());
let b_idx = a.path_index(&word(&a, &[1])).unwrap().unwrap();
assert!(a.left_mul(ArrowId(0), b_idx).is_empty());
}
#[test]
fn basis_starts_with_trivial_paths_then_lengths_ascend() {
let a = linear_an(3, f5());
for v in 0..3u32 {
let p = &a.basis()[a.vertex_idempotent(v)];
assert!(p.is_trivial());
assert_eq!(p.source(), v);
}
let lengths: Vec<usize> = a.basis().iter().map(PathWord::len).collect();
assert_eq!(lengths, vec![0, 0, 0, 1, 1, 2]);
}
#[test]
fn forbidden_word_too_short_rejected() {
let quiver = Quiver::new(2, &[(0, 1)]).unwrap();
assert!(matches!(
MonomialPresentation::new(quiver, vec![vec![ArrowId(0)]]),
Err(AlgebraError::ForbiddenWordTooShort { index: 0, len: 1 })
));
}
#[test]
fn forbidden_word_not_composable_rejected() {
let quiver = Quiver::new(3, &[(0, 1), (1, 2)]).unwrap();
assert!(matches!(
MonomialPresentation::new(quiver, vec![vec![ArrowId(1), ArrowId(0)]]),
Err(AlgebraError::ForbiddenWordInvalid {
index: 0,
error: QuiverError::NotComposable { position: 0 },
})
));
}
#[test]
fn an_zero_path_out_of_range_rejected() {
assert!(matches!(
an_with_relations(3, &[(1, 2)], f5()),
Err(AlgebraBuildError::Monomial(
AlgebraError::ZeroPathOutOfRange { start: 1, len: 2 }
))
));
}
#[test]
fn paths_from_lists_projective_basis() {
let a = an_with_relations(3, &[(0, 2)], f5()).unwrap();
assert_eq!(a.paths_from(0), &[0, 3]); assert_eq!(a.paths_from(1), &[1, 4]); assert_eq!(a.paths_from(2), &[2]); assert_eq!(a.paths_to(2), &[2, 4]); }
#[test]
fn from_monomial_basis_equals_the_standard_path_basis() {
let quiver = Quiver::new(4, &[(0, 1), (1, 2), (1, 3)]).unwrap();
let m = MonomialPresentation::new(quiver, vec![vec![ArrowId(0), ArrowId(1)]]).unwrap();
let a = Algebra::from_monomial(f5(), &m, &CompletionLimits::default()).unwrap();
assert_eq!(a.basis(), m.basis());
assert_eq!(a.cartan_matrix(), m.cartan_matrix());
}
#[test]
fn commutative_square_identifies_the_two_diagonals() {
let a = commutative_square(f5());
assert_eq!(a.dim(), 9);
let ab = a.path_index(&word(&a, &[0, 1])).unwrap().unwrap();
assert_eq!(a.path_index(&word(&a, &[2, 3])), Ok(None));
assert_eq!(a.nf_word(&word(&a, &[2, 3])), Ok(vec![(ab, f5().one())]));
let c_idx = a.path_index(&word(&a, &[2])).unwrap().unwrap();
assert_eq!(a.right_mul(c_idx, ArrowId(3)), &[(ab, f5().one())]);
}
#[test]
fn mul_basis_composes_and_respects_endpoints() {
let a = commutative_square(f5());
let c_idx = a.path_index(&word(&a, &[2])).unwrap().unwrap();
let d_idx = a.path_index(&word(&a, &[3])).unwrap().unwrap();
let ab = a.path_index(&word(&a, &[0, 1])).unwrap().unwrap();
assert_eq!(a.mul_basis(c_idx, d_idx), vec![(ab, f5().one())]);
assert_eq!(a.mul_basis(d_idx, c_idx), Vec::new());
assert_eq!(
a.mul_basis(a.vertex_idempotent(0), c_idx),
vec![(c_idx, f5().one())]
);
assert_eq!(a.mul_basis(c_idx, a.vertex_idempotent(3)), Vec::new());
}
#[test]
fn certificate_round_trips_through_verify() {
let a = commutative_square(f5());
let bytes = a.certificate().to_canonical_json();
let verified = verify(&bytes).expect("the stored certificate verifies");
let rebuilt = Algebra::from_verified(verified);
assert_eq!(rebuilt.dim(), a.dim());
assert_eq!(rebuilt.basis(), a.basis());
assert_eq!(rebuilt.relations(), a.relations());
}
#[test]
fn nilpotency_degree_matches_loewy_structure() {
let f = f5();
assert_eq!(linear_an(3, f).nilpotency_degree(), 3);
assert_eq!(dual_numbers(f).nilpotency_degree(), 2);
assert_eq!(truncated_poly(4, f).unwrap().nilpotency_degree(), 4);
assert_eq!(radical_square_zero_cycle(3, f).nilpotency_degree(), 2);
assert_eq!(commutative_square(f).nilpotency_degree(), 3);
}
#[test]
fn radical_power_components_descend_by_row_space_iteration() {
let f = f5();
let a = linear_an(3, f);
assert_eq!(a.radical_power_component(0, 2, 0).len(), 1);
assert_eq!(a.radical_power_component(0, 2, 1).len(), 1);
assert_eq!(a.radical_power_component(0, 2, 2).len(), 1);
assert_eq!(a.radical_power_component(0, 2, 3).len(), 0);
assert_eq!(a.radical_power_component(0, 1, 1).len(), 1);
assert_eq!(a.radical_power_component(0, 1, 2).len(), 0);
assert_eq!(a.radical_power_component(0, 0, 0).len(), 1);
assert_eq!(a.radical_power_component(0, 0, 1).len(), 0);
}
}