use std::fmt;
use std::sync::Arc;
use rustc_hash::FxHashMap;
use crate::certificate::{Certificate, FinitenessData, RelationData};
use crate::completion::{CompletionLimits, Outcome, TruncationDiagnostics, complete};
use crate::field::{Fp, PrimeField};
use crate::linalg::DenseMat;
use crate::monomial::{
MonomialError, MonomialIdeal, an_with_relations_ideal, cyclic_nakayama_ideal, kronecker_ideal,
linear_an_ideal, linear_nakayama_ideal, radical_square_zero_cycle_ideal, truncated_poly_ideal,
};
use crate::order::word_cmp;
use crate::profile::{Site, hit};
use crate::quiver::{ArrowId, PathWord, Quiver, QuiverError};
use crate::relation::{Presentation, Relation, RelationError};
use crate::verify::{CycleWitness, VerifiedCompletion, VerifyError, verify_certificate};
pub type BasisIdx = usize;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AlgebraBuildError {
Monomial(MonomialError),
Relation(RelationError),
NonAdmissible {
stable_power: usize,
dimension: usize,
},
InputRelationsMismatch { index: usize },
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 input rejected: {error}"),
Self::Relation(error) => write!(f, "relation rejected: {error}"),
Self::NonAdmissible {
stable_power,
dimension,
} => write!(
f,
"the ideal is not admissible: J^{stable_power} has dimension {dimension} \
and equals every higher power, so J is not nilpotent"
),
Self::InputRelationsMismatch { index } => write!(
f,
"the certificate's input relations differ from the presentation at index {index}"
),
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,
}
}
}
fn check_input_relations(
presentation: &Presentation,
certificate: &Certificate,
) -> Result<(), AlgebraBuildError> {
let asked = presentation.relations();
let found = &certificate.input_relations;
let differs =
|index: &usize| asked.get(*index).map(relation_data).as_ref() != found.get(*index);
match (0..asked.len().max(found.len())).find(differs) {
Some(index) => Err(AlgebraBuildError::InputRelationsMismatch { index }),
None => Ok(()),
}
}
fn relation_data(relation: &Relation) -> RelationData {
relation
.terms()
.iter()
.map(|(coeff, word)| (coeff.raw(), word.arrows().iter().map(|a| a.0).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)>>>,
radical_powers: Vec<Vec<Vec<DenseMat>>>,
}
impl Algebra {
pub fn new(
presentation: Presentation,
limits: &CompletionLimits,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
hit(Site::AlgebraNew);
let certificate = match complete(&presentation, limits) {
Outcome::Complete(certificate) => certificate,
Outcome::Truncated(diagnostics) => {
return Err(AlgebraBuildError::Truncated(diagnostics));
}
};
let spare = match certificate.finiteness {
FinitenessData::Infinite { .. } => Some(certificate.clone()),
FinitenessData::Finite => None,
};
match verify_certificate(certificate) {
Ok(verified) => {
check_input_relations(&presentation, verified.certificate())?;
Algebra::from_verified_with_limits(verified, limits)
}
Err(VerifyError::InfiniteDimensional { witness }) => {
Err(AlgebraBuildError::InfiniteDimensional {
certificate: Box::new(
spare.expect("only an infinite finiteness claim yields this error"),
),
witness,
})
}
Err(error) => Err(AlgebraBuildError::Verification(error)),
}
}
pub fn from_verified(verified: VerifiedCompletion) -> Result<Arc<Algebra>, AlgebraBuildError> {
Algebra::from_verified_with_limits(verified, &CompletionLimits::default())
}
pub fn from_verified_with_limits(
verified: VerifiedCompletion,
limits: &CompletionLimits,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
hit(Site::AlgebraFromVerified);
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(),
radical_powers: 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;
algebra.radical_powers = algebra.radical_chain()?;
Ok(Arc::new(algebra))
}
fn radical_chain(&self) -> Result<Vec<Vec<Vec<DenseMat>>>, AlgebraBuildError> {
let total =
|power: &[Vec<DenseMat>]| -> usize { power.iter().flatten().map(DenseMat::rows).sum() };
let n = self.quiver.num_vertices() as usize;
let identity: Vec<Vec<DenseMat>> = (0..n)
.map(|u| {
(0..n)
.map(|v| DenseMat::identity(self.between[u][v].len()))
.collect()
})
.collect();
let mut chain = vec![identity];
for _ in 0..=self.dim() {
let dimension = total(chain.last().expect("the chain starts at J^0"));
if dimension == 0 {
return Ok(chain);
}
let next = self.radical_step(chain.last().expect("the chain starts at J^0"));
let next_dimension = total(&next);
debug_assert!(next_dimension <= dimension, "J^{{k+1}} is contained in J^k");
if next_dimension == dimension {
return Err(AlgebraBuildError::NonAdmissible {
stable_power: chain.len() - 1,
dimension,
});
}
chain.push(next);
}
unreachable!("a strictly descending chain of subspaces of A reaches zero within dim steps")
}
#[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> {
hit(Site::NfWord);
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)> {
hit(Site::MulBasis);
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_matrix(&self, u: u32, v: u32, k: usize) -> &DenseMat {
assert!(u < self.quiver.num_vertices() && v < self.quiver.num_vertices());
&self.radical_power(k)[u as usize][v as usize]
}
#[inline]
pub fn nilpotency_degree(&self) -> usize {
self.radical_powers.len() - 1
}
fn radical_power(&self, k: usize) -> &[Vec<DenseMat>] {
&self.radical_powers[k.min(self.nilpotency_degree())]
}
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.into_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
}
pub fn monomial_presentation(ideal: &MonomialIdeal, field: PrimeField) -> Presentation {
let quiver = ideal.quiver().clone();
let relations = ideal
.forbidden()
.iter()
.map(|word| {
Relation::new(&quiver, field, vec![(field.one(), word.clone())])
.expect("a forbidden word is a path of length >= 2")
})
.collect();
Presentation::new(quiver, field, relations).expect("the relations were built over this quiver")
}
pub fn monomial_limits(ideal: &MonomialIdeal) -> CompletionLimits {
let defaults = CompletionLimits::default();
let words = ideal.forbidden().len();
let longest = ideal.forbidden().iter().map(Vec::len).max().unwrap_or(0);
CompletionLimits {
max_basis: defaults.max_basis.max(words),
max_word_len: defaults
.max_word_len
.max(longest.saturating_mul(2).saturating_sub(1)),
max_steps: defaults.max_steps,
max_origin_terms: defaults.max_origin_terms,
max_ambiguities: defaults.max_ambiguities.max(
words
.saturating_mul(words)
.saturating_mul(longest.saturating_mul(2)),
),
}
}
pub fn monomial_algebra(
ideal: &MonomialIdeal,
field: PrimeField,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
Algebra::new(monomial_presentation(ideal, field), &monomial_limits(ideal))
}
pub fn path_algebra(quiver: Quiver, field: PrimeField) -> Result<Arc<Algebra>, AlgebraBuildError> {
let presentation =
Presentation::new(quiver, field, Vec::new()).expect("there is no relation to reject");
Algebra::new(presentation, &CompletionLimits::default())
}
pub fn linear_an(n: usize, field: PrimeField) -> Arc<Algebra> {
monomial_algebra(&linear_an_ideal(n), field)
.expect("the zero ideal over an acyclic quiver completes")
}
pub fn kronecker(m: usize, field: PrimeField) -> Arc<Algebra> {
monomial_algebra(&kronecker_ideal(m), field)
.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(n: usize, field: PrimeField) -> Result<Arc<Algebra>, AlgebraBuildError> {
let ideal = truncated_poly_ideal(n).map_err(AlgebraBuildError::Monomial)?;
monomial_algebra(&ideal, field)
}
pub fn linear_nakayama(
kupisch: &[usize],
field: PrimeField,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let ideal = linear_nakayama_ideal(kupisch).map_err(AlgebraBuildError::Monomial)?;
monomial_algebra(&ideal, field)
}
pub fn cyclic_nakayama(
kupisch: &[usize],
field: PrimeField,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let ideal = cyclic_nakayama_ideal(kupisch).map_err(AlgebraBuildError::Monomial)?;
monomial_algebra(&ideal, field)
}
pub fn radical_square_zero_cycle(n: usize, field: PrimeField) -> Arc<Algebra> {
monomial_algebra(&radical_square_zero_cycle_ideal(n), field)
.expect("rad² = 0 leaves only vertices and arrows")
}
pub fn an_with_relations(
n: usize,
zero_paths: &[(usize, usize)],
field: PrimeField,
) -> Result<Arc<Algebra>, AlgebraBuildError> {
let ideal = an_with_relations_ideal(n, zero_paths).map_err(AlgebraBuildError::Monomial)?;
monomial_algebra(&ideal, field)
}
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::*;
use crate::monomial::MonomialPresentation;
use crate::verify::verify;
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()
}
fn loop_presentation(field: PrimeField, terms: &[(i64, usize)]) -> Presentation {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
let relation = Relation::new(
&quiver,
field,
terms
.iter()
.map(|&(c, n)| (field.elem(c), vec![ArrowId(0); n]))
.collect(),
)
.expect("the terms are parallel words of length >= 2");
Presentation::new(quiver, field, vec![relation]).expect("built over this quiver and field")
}
#[test]
fn a_stable_nonzero_arrow_ideal_is_rejected_as_non_admissible() {
let presentation = loop_presentation(f5(), &[(1, 3), (-1, 2)]);
assert_eq!(
Algebra::new(presentation.clone(), &CompletionLimits::default()).unwrap_err(),
AlgebraBuildError::NonAdmissible {
stable_power: 2,
dimension: 1,
}
);
let certificate = match complete(&presentation, &CompletionLimits::default()) {
Outcome::Complete(certificate) => certificate,
Outcome::Truncated(diagnostics) => panic!("unexpected truncation: {diagnostics:?}"),
};
let verified = verify(&certificate.to_canonical_json()).expect("the certificate verifies");
assert_eq!(verified.normal_words().len(), 3);
assert_eq!(
Algebra::from_verified(verified).unwrap_err(),
AlgebraBuildError::NonAdmissible {
stable_power: 2,
dimension: 1,
}
);
}
#[test]
fn an_admissible_inhomogeneous_presentation_builds() {
let field = f5();
let quiver = Quiver::new(5, &[(0, 1), (1, 3), (0, 2), (2, 4), (4, 3)]).unwrap();
let relation = Relation::new(
&quiver,
field,
vec![
(field.one(), vec![ArrowId(2), ArrowId(3), ArrowId(4)]),
(field.elem(-1), vec![ArrowId(0), ArrowId(1)]),
],
)
.unwrap();
let presentation = Presentation::new(quiver, field, vec![relation]).unwrap();
let a = Algebra::new(presentation, &CompletionLimits::default()).unwrap();
assert_eq!(a.dim(), 13);
assert_eq!(a.basis().iter().map(PathWord::len).max(), Some(2));
assert_eq!(a.nilpotency_degree(), 4);
}
#[test]
fn a_certificate_about_another_presentation_is_rejected() {
let field = f5();
let a = loop_presentation(field, &[(1, 3)]);
let b = loop_presentation(field, &[(1, 4)]);
let built = Algebra::new(a.clone(), &CompletionLimits::default()).unwrap();
assert_eq!(check_input_relations(&a, built.certificate()), Ok(()));
assert_eq!(
check_input_relations(&b, built.certificate()),
Err(AlgebraBuildError::InputRelationsMismatch { index: 0 })
);
let empty =
Presentation::new(Quiver::new(1, &[(0, 0)]).unwrap(), field, Vec::new()).unwrap();
assert_eq!(
check_input_relations(&empty, built.certificate()),
Err(AlgebraBuildError::InputRelationsMismatch { index: 0 })
);
}
#[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 ideal = truncated_poly_ideal(65).unwrap();
assert!(matches!(
Algebra::new(
monomial_presentation(&ideal, f5()),
&CompletionLimits::default()
),
Err(AlgebraBuildError::Truncated(diagnostics))
if diagnostics.reason == crate::completion::TruncationReason::WordLenBudget
));
}
#[test]
fn monomial_limits_never_fall_below_the_defaults() {
let ideal = truncated_poly_ideal(3).unwrap();
assert_eq!(monomial_limits(&ideal), CompletionLimits::default());
let long = truncated_poly_ideal(100).unwrap();
let limits = monomial_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()).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).unwrap();
assert_eq!(preserved.completion_limits(), &raised);
}
#[test]
fn truncated_poly_rejects_n_below_2() {
assert!(matches!(
truncated_poly(1, f5()),
Err(AlgebraBuildError::Monomial(
MonomialError::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(
MonomialError::InvalidKupisch { .. }
))
));
}
#[test]
fn linear_kupisch_drop_violation_rejected() {
assert!(matches!(
linear_nakayama(&[4, 2, 1], f5()),
Err(AlgebraBuildError::Monomial(
MonomialError::InvalidKupisch { .. }
))
));
}
#[test]
fn cyclic_kupisch_entry_below_2_rejected() {
assert!(matches!(
cyclic_nakayama(&[2, 1, 2], f5()),
Err(AlgebraBuildError::Monomial(
MonomialError::InvalidKupisch { .. }
))
));
}
#[test]
fn cyclic_kupisch_drop_violation_rejected() {
assert!(matches!(
cyclic_nakayama(&[4, 2, 2], f5()),
Err(AlgebraBuildError::Monomial(
MonomialError::InvalidKupisch { .. }
))
));
}
#[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 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 an_zero_path_out_of_range_rejected() {
assert!(matches!(
an_with_relations(3, &[(1, 2)], f5()),
Err(AlgebraBuildError::Monomial(
MonomialError::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 normal_words_equal_the_standard_paths() {
let quiver = Quiver::new(4, &[(0, 1), (1, 2), (1, 3)]).unwrap();
let ideal = MonomialIdeal::new(quiver, vec![vec![ArrowId(0), ArrowId(1)]]).unwrap();
let m = MonomialPresentation::new(ideal.clone()).unwrap();
let a = monomial_algebra(&ideal, f5()).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).expect("the ideal is admissible");
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_matrices_descend_by_row_space_iteration() {
let f = f5();
let a = linear_an(3, f);
let rank = |u, v, k| a.radical_power_matrix(u, v, k).rows();
assert_eq!(rank(0, 2, 0), 1);
assert_eq!(rank(0, 2, 1), 1);
assert_eq!(rank(0, 2, 2), 1);
assert_eq!(rank(0, 2, 3), 0);
assert_eq!(rank(0, 1, 1), 1);
assert_eq!(rank(0, 1, 2), 0);
assert_eq!(rank(0, 0, 0), 1);
assert_eq!(rank(0, 0, 1), 0);
}
}