use crate::completion::normal_word_transitions;
use crate::quiver::{ArrowId, PathWord, Quiver, QuiverError};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum MonomialError {
ForbiddenWordTooShort { index: usize, len: usize },
ForbiddenWordInvalid { index: usize, error: QuiverError },
InfiniteDimensional,
InvalidKupisch { reason: String },
ZeroPathOutOfRange { start: usize, len: usize },
}
display_error! { MonomialError {
Self::ForbiddenWordTooShort { index, len } => "forbidden word {index} has length {len}; admissibility needs length >= 2";
Self::ForbiddenWordInvalid { index, error } => "forbidden word {index} is not a path: {error}";
Self::InfiniteDimensional => "the standard-path language is infinite; this crate supports finite-dimensional algebras only";
Self::InvalidKupisch { reason } => "invalid Kupisch series: {reason}";
Self::ZeroPathOutOfRange { start, len } => "no path of length {len} starting at vertex {start} in the linear quiver";
} }
error_source! { MonomialError {
Self::ForbiddenWordInvalid { error, .. } => Some(error),
_ => None,
} }
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct MonomialIdeal {
quiver: Quiver,
forbidden: Vec<Vec<ArrowId>>,
}
impl MonomialIdeal {
pub fn new(
quiver: Quiver,
forbidden: Vec<Vec<ArrowId>>,
) -> Result<MonomialIdeal, MonomialError> {
for (index, word) in forbidden.iter().enumerate() {
if word.len() < 2 {
return Err(MonomialError::ForbiddenWordTooShort {
index,
len: word.len(),
});
}
PathWord::from_arrows(&quiver, word)
.map_err(|error| MonomialError::ForbiddenWordInvalid { index, error })?;
}
Ok(MonomialIdeal {
quiver,
forbidden: minimal_words(forbidden),
})
}
accessor_methods! {
pub quiver() -> &Quiver = |this| &this.quiver;
pub forbidden() -> &[Vec<ArrowId>] = |this| &this.forbidden;
}
}
#[derive(Clone, Debug)]
pub struct MonomialPresentation {
ideal: MonomialIdeal,
basis: Vec<PathWord>,
}
impl MonomialPresentation {
pub fn new(ideal: MonomialIdeal) -> Result<MonomialPresentation, MonomialError> {
let automaton = Automaton::build(&ideal.quiver, &ideal.forbidden);
if automaton.has_cycle() {
return Err(MonomialError::InfiniteDimensional);
}
let quiver = &ideal.quiver;
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;
}
Ok(MonomialPresentation { ideal, basis })
}
accessor_methods! {
pub ideal() -> &MonomialIdeal = |this| &this.ideal;
pub quiver() -> &Quiver = |this| this.ideal.quiver();
pub forbidden() -> &[Vec<ArrowId>] = |this| this.ideal.forbidden();
pub dim() -> usize = |this| this.basis.len();
pub basis() -> &[PathWord] = |this| &this.basis;
}
pub fn cartan_matrix(&self) -> Vec<Vec<usize>> {
let n = self.quiver().num_vertices() as usize;
let mut cartan = vec![vec![0usize; n]; n];
for path in &self.basis {
cartan[path.source() as usize][path.target() as usize] += 1;
}
cartan
}
}
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 (_, trans) = normal_word_transitions(quiver, forbidden);
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 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")
}
pub 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_ideal(n: usize) -> MonomialIdeal {
MonomialIdeal::new(linear_quiver(n), Vec::new()).expect("there is no forbidden word to reject")
}
pub fn kronecker_ideal(m: usize) -> MonomialIdeal {
let arrows = vec![(0u32, 1u32); m];
let quiver = Quiver::new(2, &arrows).expect("endpoints in range by construction");
MonomialIdeal::new(quiver, Vec::new()).expect("there is no forbidden word to reject")
}
pub fn truncated_poly_ideal(n: usize) -> Result<MonomialIdeal, MonomialError> {
let quiver = Quiver::new(1, &[(0, 0)]).expect("endpoints in range by construction");
MonomialIdeal::new(quiver, vec![vec![ArrowId(0); n]])
}
fn invalid_kupisch(reason: impl Into<String>) -> MonomialError {
MonomialError::InvalidKupisch {
reason: reason.into(),
}
}
pub fn linear_nakayama_ideal(kupisch: &[usize]) -> Result<MonomialIdeal, MonomialError> {
let n = kupisch.len();
if n == 0 {
return Err(invalid_kupisch("series is empty"));
}
if kupisch[n - 1] != 1 {
return Err(invalid_kupisch(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(invalid_kupisch(format!(
"c[{i}] = {} but interior entries need c >= 2",
kupisch[i]
)));
}
if kupisch[i + 1] < kupisch[i] - 1 {
return Err(invalid_kupisch(format!(
"c[{}] = {} violates c[i+1] >= c[i] - 1 = {}",
i + 1,
kupisch[i + 1],
kupisch[i] - 1
)));
}
}
let forbidden = kupisch
.iter()
.enumerate()
.filter(|&(i, &c)| i + c <= n - 1)
.map(|(i, &c)| (i..i + c).map(|j| ArrowId(j as u32)).collect())
.collect();
MonomialIdeal::new(linear_quiver(n), forbidden)
}
pub fn cyclic_nakayama_ideal(kupisch: &[usize]) -> Result<MonomialIdeal, MonomialError> {
let n = kupisch.len();
if n == 0 {
return Err(invalid_kupisch("series is empty"));
}
for (i, &c) in kupisch.iter().enumerate() {
if c < 2 {
return Err(invalid_kupisch(format!(
"c[{i}] = {c} but cyclic entries need c >= 2"
)));
}
if kupisch[(i + 1) % n] < c - 1 {
return Err(invalid_kupisch(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();
MonomialIdeal::new(cyclic_quiver(n), forbidden)
}
pub fn radical_square_zero_cycle_ideal(n: usize) -> MonomialIdeal {
let forbidden: Vec<Vec<ArrowId>> = (0..n)
.map(|i| vec![ArrowId(i as u32), ArrowId(((i + 1) % n) as u32)])
.collect();
MonomialIdeal::new(cyclic_quiver(n), forbidden).expect("a length-2 path is a valid word")
}
pub fn an_with_relations_ideal(
n: usize,
zero_paths: &[(usize, usize)],
) -> Result<MonomialIdeal, MonomialError> {
for &(start, len) in zero_paths {
if n == 0 || start + len > n - 1 {
return Err(MonomialError::ZeroPathOutOfRange { start, len });
}
}
let forbidden = zero_paths
.iter()
.map(|&(start, len)| (start..start + len).map(|j| ArrowId(j as u32)).collect())
.collect();
MonomialIdeal::new(linear_quiver(n), forbidden)
}
#[cfg(test)]
mod tests {
use super::*;
fn present(quiver: Quiver, forbidden: Vec<Vec<ArrowId>>) -> MonomialPresentation {
MonomialPresentation::new(MonomialIdeal::new(quiver, forbidden).unwrap()).unwrap()
}
#[test]
fn loop_without_relations_is_infinite_dimensional() {
let quiver = Quiver::new(1, &[(0, 0)]).unwrap();
let ideal = MonomialIdeal::new(quiver, Vec::new()).unwrap();
assert_eq!(
MonomialPresentation::new(ideal).unwrap_err(),
MonomialError::InfiniteDimensional
);
}
#[test]
fn cycle_without_relations_is_infinite_dimensional() {
let quiver = Quiver::new(3, &[(0, 1), (1, 2), (2, 0)]).unwrap();
let ideal = MonomialIdeal::new(quiver, Vec::new()).unwrap();
assert_eq!(
MonomialPresentation::new(ideal).unwrap_err(),
MonomialError::InfiniteDimensional
);
}
#[test]
fn two_loops_with_xx_yy_forbidden_is_infinite() {
let quiver = Quiver::new(1, &[(0, 0), (0, 0)]).unwrap();
let ideal = MonomialIdeal::new(
quiver,
vec![vec![ArrowId(0), ArrowId(0)], vec![ArrowId(1), ArrowId(1)]],
)
.unwrap();
assert_eq!(
MonomialPresentation::new(ideal).unwrap_err(),
MonomialError::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)],
];
assert_eq!(present(quiver, forbidden).dim(), 3);
}
#[test]
fn forbidden_words_reduced_to_minimal() {
let quiver = Quiver::new(4, &[(0, 1), (1, 2), (2, 3)]).unwrap();
let m = present(
quiver,
vec![
vec![ArrowId(0), ArrowId(1), ArrowId(2)],
vec![ArrowId(0), ArrowId(1)],
],
);
assert_eq!(m.forbidden(), &[vec![ArrowId(0), ArrowId(1)]]);
assert_eq!(m.dim(), 8); }
#[test]
fn forbidden_word_too_short_rejected() {
let quiver = Quiver::new(2, &[(0, 1)]).unwrap();
assert_eq!(
MonomialIdeal::new(quiver, vec![vec![ArrowId(0)]]).unwrap_err(),
MonomialError::ForbiddenWordTooShort { index: 0, len: 1 }
);
}
#[test]
fn forbidden_word_not_composable_rejected() {
let quiver = Quiver::new(3, &[(0, 1), (1, 2)]).unwrap();
assert_eq!(
MonomialIdeal::new(quiver, vec![vec![ArrowId(1), ArrowId(0)]]).unwrap_err(),
MonomialError::ForbiddenWordInvalid {
index: 0,
error: QuiverError::NotComposable { position: 0 },
}
);
}
#[test]
fn linear_a3_basis_and_cartan() {
let m = MonomialPresentation::new(linear_an_ideal(3)).unwrap();
assert_eq!(m.dim(), 6);
assert_eq!(
m.cartan_matrix(),
vec![vec![1, 1, 1], vec![0, 1, 1], vec![0, 0, 1]]
);
let lengths: Vec<usize> = m.basis().iter().map(PathWord::len).collect();
assert_eq!(lengths, vec![0, 0, 0, 1, 1, 2]);
}
#[test]
fn named_family_dimensions() {
let dim = |ideal| MonomialPresentation::new(ideal).unwrap().dim();
assert_eq!(dim(kronecker_ideal(2)), 4);
assert_eq!(dim(truncated_poly_ideal(3).unwrap()), 3);
assert_eq!(dim(linear_nakayama_ideal(&[2, 2, 1]).unwrap()), 5);
assert_eq!(dim(cyclic_nakayama_ideal(&[3, 3, 3]).unwrap()), 9);
assert_eq!(dim(radical_square_zero_cycle_ideal(3)), 6);
assert_eq!(dim(an_with_relations_ideal(3, &[(0, 2)]).unwrap()), 5);
}
#[test]
fn invalid_family_parameters_rejected() {
assert!(matches!(
truncated_poly_ideal(1),
Err(MonomialError::ForbiddenWordTooShort { index: 0, len: 1 })
));
for kupisch in [&[3, 3, 2][..], &[4, 2, 1][..]] {
assert!(matches!(
linear_nakayama_ideal(kupisch),
Err(MonomialError::InvalidKupisch { .. })
));
}
for kupisch in [&[2, 1, 2][..], &[4, 2, 2][..]] {
assert!(matches!(
cyclic_nakayama_ideal(kupisch),
Err(MonomialError::InvalidKupisch { .. })
));
}
assert_eq!(
an_with_relations_ideal(3, &[(1, 2)]).unwrap_err(),
MonomialError::ZeroPathOutOfRange { start: 1, len: 2 }
);
}
}