use std::fmt;
use std::sync::Arc;
use crate::algebra::Algebra;
use crate::field::Fp;
use crate::hom::Morphism;
use crate::linalg::DenseMat;
use crate::module::Module;
use crate::radical::top;
use crate::resolution::{Bounded, projective_dimension, resolve};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ExtError {
DifferentAlgebras,
}
impl fmt::Display for ExtError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::DifferentAlgebras => f.write_str("modules live over different algebras"),
}
}
}
impl std::error::Error for ExtError {}
struct Layout {
gen_vertex: Vec<u32>,
offsets: Vec<Vec<usize>>,
}
fn layout(term: &Module) -> Layout {
let algebra = term.algebra();
let n = algebra.quiver().num_vertices();
let (t, _) = top(term);
let mut gen_vertex = Vec::new();
for v in 0..n {
for _ in 0..t.dim_at(v) {
gen_vertex.push(v);
}
}
let mut offsets = vec![Vec::with_capacity(gen_vertex.len()); n as usize];
for w in 0..n {
let mut off = 0;
for &v in &gen_vertex {
offsets[w as usize].push(off);
off += algebra.paths_between(v, w).len();
}
assert_eq!(
off,
term.dim_at(w),
"resolution term is not a canonical projective sum at vertex {w}; \
this is a bug in auslander"
);
}
Layout {
gen_vertex,
offsets,
}
}
fn hom_space_dim(lay: &Layout, n: &Module) -> usize {
lay.gen_vertex.iter().map(|&v| n.dim_at(v)).sum()
}
fn yoneda_basis(term: &Module, lay: &Layout, n: &Module) -> Vec<Morphism> {
let algebra = term.algebra();
let nv = algebra.quiver().num_vertices();
let mut basis = Vec::new();
for (g, &v) in lay.gen_vertex.iter().enumerate() {
for j in 0..n.dim_at(v) {
let mut maps: Vec<DenseMat> = (0..nv)
.map(|w| DenseMat::zero(term.dim_at(w), n.dim_at(w)))
.collect();
for w in 0..nv {
for (r, &b) in algebra.paths_between(v, w).iter().enumerate() {
let action = n
.word_action(&algebra.basis()[b])
.expect("algebra basis words are valid in their own quiver");
for c in 0..n.dim_at(w) {
maps[w as usize].set(lay.offsets[w as usize][g] + r, c, action.get(j, c));
}
}
}
basis.push(Morphism::new(term, n, maps).expect("Yoneda basis element is A-linear"));
}
}
basis
}
fn coordinates(f: &Morphism, lay: &Layout, n: &Module) -> Vec<Fp> {
let mut coords = Vec::new();
for (g, &v) in lay.gen_vertex.iter().enumerate() {
let row = lay.offsets[v as usize][g];
for j in 0..n.dim_at(v) {
coords.push(f.map_at(v).get(row, j));
}
}
coords
}
fn delta_rank(d: &Morphism, term: &Module, lay: &Layout, next_lay: &Layout, n: &Module) -> usize {
let field = term.field();
if hom_space_dim(next_lay, n) == 0 {
return 0;
}
let rows: Vec<Vec<Fp>> = yoneda_basis(term, lay, n)
.iter()
.map(|f| {
let composite = d
.then(f)
.expect("internal endpoint invariant: d targets the term f leaves");
coordinates(&composite, next_lay, n)
})
.collect();
if rows.is_empty() {
return 0;
}
DenseMat::from_rows(&rows).rank(&field)
}
fn check_pair(m: &Module, n: &Module) -> Result<(), ExtError> {
if !Arc::ptr_eq(m.algebra(), n.algebra()) {
return Err(ExtError::DifferentAlgebras);
}
Ok(())
}
pub fn ext_table(m: &Module, n: &Module, max_k: usize) -> Result<Vec<usize>, ExtError> {
check_pair(m, n)?;
let res = resolve(m, max_k + 1);
let layouts: Vec<Layout> = res.terms.iter().map(layout).collect();
let h: Vec<usize> = (0..=max_k)
.map(|i| layouts.get(i).map_or(0, |lay| hom_space_dim(lay, n)))
.collect();
let ranks: Vec<usize> = (0..=max_k)
.map(|i| {
if i + 1 < res.terms.len() {
delta_rank(&res.maps[i], &res.terms[i], &layouts[i], &layouts[i + 1], n)
} else {
0
}
})
.collect();
Ok((0..=max_k)
.map(|k| {
let kernel_dim = h[k] - ranks[k];
let boundary = if k == 0 { 0 } else { ranks[k - 1] };
assert!(
kernel_dim >= boundary,
"im δ^{} ⊄ ker δ^{k}; this is a bug in auslander",
k.wrapping_sub(1)
);
kernel_dim - boundary
})
.collect())
}
pub fn ext_dim(m: &Module, n: &Module, k: usize) -> Result<usize, ExtError> {
Ok(ext_table(m, n, k)?[k])
}
pub fn global_dimension(algebra: &Arc<Algebra>, bound: usize) -> Bounded<usize> {
let mut max = 0usize;
let mut cut = false;
for v in 0..algebra.quiver().num_vertices() {
match projective_dimension(&Module::simple(algebra, v), bound) {
Bounded::Exact(d) => max = max.max(d),
Bounded::AtLeast(_) => cut = true,
}
}
if cut {
Bounded::AtLeast(bound + 1)
} else {
Bounded::Exact(max)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{
an_with_relations, dual_numbers, kronecker, linear_an, radical_square_zero_cycle,
truncated_poly,
};
use crate::field::PrimeField;
use crate::hom::hom_dim;
use crate::module::direct_sum;
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
#[test]
fn a3_ext_1_between_simples_counts_arrows_source_to_target() {
let field = f5();
let algebra = linear_an(3, field);
let simples: Vec<Module> = (0..3).map(|v| Module::simple(&algebra, v)).collect();
for i in 0..3 {
for j in 0..3 {
let expected = usize::from(j == i + 1);
assert_eq!(
ext_dim(&simples[i], &simples[j], 1).unwrap(),
expected,
"Ext¹(S_{i}, S_{j})"
);
for k in 2..=4 {
assert_eq!(
ext_dim(&simples[i], &simples[j], k).unwrap(),
0,
"Ext^{k}(S_{i}, S_{j}) over a gldim-1 algebra"
);
}
}
}
assert_eq!(ext_dim(&simples[1], &simples[0], 1).unwrap(), 0);
assert_eq!(global_dimension(&algebra, 5), Bounded::Exact(1));
}
#[test]
fn a3_mod_ab_ext_1_and_2_among_simples() {
let field = f5();
let algebra = an_with_relations(3, &[(0, 2)], field).unwrap();
let simples: Vec<Module> = (0..3).map(|v| Module::simple(&algebra, v)).collect();
for i in 0..3 {
for j in 0..3 {
let ext1 = usize::from(j == i + 1);
let ext2 = usize::from(i == 0 && j == 2);
assert_eq!(
ext_dim(&simples[i], &simples[j], 1).unwrap(),
ext1,
"Ext¹(S_{i}, S_{j})"
);
assert_eq!(
ext_dim(&simples[i], &simples[j], 2).unwrap(),
ext2,
"Ext²(S_{i}, S_{j})"
);
assert_eq!(ext_dim(&simples[i], &simples[j], 3).unwrap(), 0);
}
}
assert_eq!(global_dimension(&algebra, 5), Bounded::Exact(2));
}
#[test]
fn dual_numbers_ext_table_of_the_simple_is_all_ones() {
let field = f5();
let algebra = dual_numbers(field);
let s = Module::simple(&algebra, 0);
assert_eq!(ext_table(&s, &s, 4).unwrap(), vec![1, 1, 1, 1, 1]);
assert_eq!(global_dimension(&algebra, 6), Bounded::AtLeast(7));
}
#[test]
fn truncated_poly_3_ext_table_of_the_simple_is_all_ones() {
let field = PrimeField::new(3).unwrap();
let algebra = truncated_poly(3, field).unwrap();
let s = Module::simple(&algebra, 0);
let res = resolve(&s, 5);
for term in &res.terms {
assert_eq!(term.dim_vector(), &[3]);
}
assert_eq!(ext_table(&s, &s, 4).unwrap(), vec![1, 1, 1, 1, 1]);
}
#[test]
fn radical_square_zero_cycle_ext_1_follows_the_arrows() {
let field = f5();
let algebra = radical_square_zero_cycle(3, field);
let simples: Vec<Module> = (0..3).map(|v| Module::simple(&algebra, v)).collect();
for i in 0..3 {
for j in 0..3 {
let expected = usize::from(j == (i + 1) % 3);
assert_eq!(
ext_dim(&simples[i], &simples[j], 1).unwrap(),
expected,
"Ext¹(S_{i}, S_{j})"
);
}
}
assert_eq!(global_dimension(&algebra, 4), Bounded::AtLeast(5));
}
#[test]
fn kronecker_2_is_hereditary_with_global_dimension_1() {
let algebra = kronecker(2, f5());
assert_eq!(global_dimension(&algebra, 5), Bounded::Exact(1));
}
fn assorted_pairs() -> Vec<(Module, Module)> {
let field = f5();
let mut pairs = Vec::new();
for algebra in [
linear_an(3, field),
an_with_relations(3, &[(0, 2)], field).unwrap(),
dual_numbers(field),
radical_square_zero_cycle(3, field),
] {
let n = algebra.quiver().num_vertices();
for v in 0..n {
let s = Module::simple(&algebra, v);
let p = Module::projective(&algebra, v);
let i = Module::injective(&algebra, v);
pairs.push((s.clone(), i.clone()));
pairs.push((i, s.clone()));
pairs.push((s.clone(), p.clone()));
pairs.push((p, s));
}
let s0 = Module::simple(&algebra, 0);
let i_last = Module::injective(&algebra, n - 1);
let (sum, _, _) = direct_sum(&[&s0, &i_last]);
pairs.push((sum.clone(), s0));
pairs.push((sum.clone(), sum));
}
pairs
}
#[test]
fn ext_0_equals_hom_dim() {
for (m, n) in assorted_pairs() {
assert_eq!(
ext_dim(&m, &n, 0).unwrap(),
hom_dim(&m, &n).unwrap(),
"Ext⁰ with dim m = {:?}, dim n = {:?}",
m.dim_vector(),
n.dim_vector()
);
}
}
#[test]
fn yoneda_basis_agrees_with_generic_hom_on_resolution_terms() {
let field = f5();
for (m, n) in assorted_pairs() {
let res = resolve(&m, 2);
for term in &res.terms {
let lay = layout(term);
assert_eq!(hom_space_dim(&lay, &n), hom_dim(term, &n).unwrap());
let basis = yoneda_basis(term, &lay, &n);
for (i, f) in basis.iter().enumerate() {
let coords = coordinates(f, &lay, &n);
for (c, &val) in coords.iter().enumerate() {
let expected = if c == i { field.one() } else { field.zero() };
assert_eq!(val, expected, "coordinate {c} of basis element {i}");
}
}
}
}
}
#[test]
fn ext_beyond_a_finite_resolution_is_zero() {
let field = f5();
let algebra = an_with_relations(3, &[(0, 2)], field).unwrap();
let s0 = Module::simple(&algebra, 0);
let s2 = Module::simple(&algebra, 2);
assert_eq!(ext_table(&s0, &s2, 6).unwrap(), vec![0, 0, 1, 0, 0, 0, 0]);
}
}