use crate::field::Fp;
use crate::hom::{Morphism, kernel, zero_morphism};
use crate::linalg::DenseMat;
use crate::module::{Module, direct_sum, same_morphism_data, same_representation, same_slice};
use crate::opposite::ElementMatrix;
use crate::profile::{Site, hit};
use crate::radical::top;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum ResolutionEnd {
Finite,
Cut { at: usize },
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Bounded<T> {
Exact(T),
AtLeast(T),
}
pub struct ProjectiveResolution {
pub terms: Vec<Module>,
pub maps: Vec<Morphism>,
pub augmentation: Morphism,
pub end: ResolutionEnd,
}
impl ProjectiveResolution {
pub(crate) fn agrees_with(&self, other: &ProjectiveResolution) -> bool {
self.end == other.end
&& same_slice(&self.terms, &other.terms, same_representation)
&& same_slice(&self.maps, &other.maps, same_morphism_data)
&& same_morphism_data(&self.augmentation, &other.augmentation)
}
}
pub fn projective_cover(m: &Module) -> (Module, Morphism) {
let field = m.field();
let algebra = m.algebra().clone();
if m.is_zero() {
let p = Module::zero(&algebra);
let cover = zero_morphism(&p, m).expect("zero module shares its algebra with m");
return (p, cover);
}
let quiver = algebra.quiver();
let n = quiver.num_vertices();
let (top_m, projection) = top(m);
let mut generators: Vec<(u32, Vec<Fp>)> = Vec::new();
for v in 0..n {
if top_m.dim_at(v) == 0 {
continue;
}
let lifts = projection
.map_at(v)
.transpose()
.solve_many(&DenseMat::identity(top_m.dim_at(v)), &field)
.expect("top projection is surjective, so every unit vector lifts");
for j in 0..top_m.dim_at(v) {
generators.push((v, (0..lifts.rows()).map(|i| lifts.get(i, j)).collect()));
}
}
let projectives: Vec<Module> = (0..n).map(|v| Module::projective(&algebra, v)).collect();
let parts: Vec<&Module> = generators
.iter()
.map(|&(v, _)| &projectives[v as usize])
.collect();
let (p, _, _) = direct_sum(&parts);
let mut maps: Vec<DenseMat> = (0..n)
.map(|w| DenseMat::zero(p.dim_at(w), m.dim_at(w)))
.collect();
let mut cursor = vec![0usize; n as usize];
for (v, lift) in &generators {
for w in 0..n {
for &b in algebra.paths_between(*v, w) {
let row = m
.word_action(&algebra.basis()[b])
.expect("algebra basis words are valid in their own quiver")
.transpose()
.mul_vec(lift, &field);
for (c, &val) in row.iter().enumerate() {
maps[w as usize].set(cursor[w as usize], c, val);
}
cursor[w as usize] += 1;
}
}
}
for w in 0..n {
assert_eq!(
maps[w as usize].rank(&field),
m.dim_at(w),
"projective_cover: cover map fails to surject at vertex {w}; \
this is a bug in auslander"
);
}
let cover = Morphism::new(&p, m, maps).expect("cover map satisfies the commuting squares");
(p, cover)
}
pub fn resolve(m: &Module, steps: usize) -> ProjectiveResolution {
let (p0, augmentation) = projective_cover(m);
let mut terms = vec![p0];
let mut maps: Vec<Morphism> = Vec::new();
let (mut syzygy, mut inclusion) = kernel(&augmentation);
let end = loop {
if syzygy.is_zero() {
break ResolutionEnd::Finite;
}
if maps.len() == steps {
break ResolutionEnd::Cut { at: steps };
}
let (p, cover) = projective_cover(&syzygy);
let differential = cover
.then(&inclusion)
.expect("internal endpoint invariant: cover targets the syzygy the inclusion leaves");
let (next_syzygy, next_inclusion) = kernel(&cover);
terms.push(p);
maps.push(differential);
syzygy = next_syzygy;
inclusion = next_inclusion;
};
ProjectiveResolution {
terms,
maps,
augmentation,
end,
}
}
pub fn projective_dimension(m: &Module, bound: usize) -> Bounded<usize> {
let resolution = resolve(m, bound);
bounded_dimension(resolution.end, resolution.terms.len())
}
pub(crate) fn bounded_dimension(end: ResolutionEnd, terms: usize) -> Bounded<usize> {
match end {
ResolutionEnd::Finite => Bounded::Exact(terms - 1),
ResolutionEnd::Cut { at } => Bounded::AtLeast(at + 1),
}
}
pub fn minimal_presentation_matrix(m: &Module) -> ElementMatrix {
hit(Site::MinimalPresentation);
let resolution = resolve(m, 1);
let targets = cover_summands(m);
match resolution.maps.first() {
None => ElementMatrix::new(m.algebra().clone(), Vec::new(), targets, Vec::new())
.expect("cover summand vertices are in range"),
Some(d1) => {
let sources = cover_summands(&resolution.terms[1]);
ElementMatrix::of_morphism(d1, &sources, &targets)
.expect("covers are laid out as the standard direct sums")
}
}
}
fn cover_summands(m: &Module) -> Vec<u32> {
let (top_m, _) = top(m);
(0..m.algebra().quiver().num_vertices())
.flat_map(|v| std::iter::repeat_n(v, top_m.dim_at(v)))
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{
an_with_relations, dual_numbers, linear_an, radical_square_zero_cycle, truncated_poly,
};
use crate::field::PrimeField;
use crate::hom::image;
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
#[test]
fn cover_of_a_simple_is_the_indecomposable_projective() {
let field = f5();
for algebra in [
linear_an(3, field),
an_with_relations(3, &[(0, 2)], field).unwrap(),
] {
for v in 0..algebra.quiver().num_vertices() {
let s = Module::simple(&algebra, v);
let (p, cover) = projective_cover(&s);
let pv = Module::projective(&algebra, v);
assert_eq!(p.dim_vector(), pv.dim_vector(), "cover of S_{v}");
assert!(!cover.is_zero());
}
}
}
#[test]
fn cover_of_the_zero_module_is_zero() {
let algebra = linear_an(3, f5());
let z = Module::zero(&algebra);
let (p, cover) = projective_cover(&z);
assert!(p.is_zero());
assert!(cover.is_zero());
let res = resolve(&z, 4);
assert_eq!(res.end, ResolutionEnd::Finite);
assert_eq!(res.terms.len(), 1);
assert_eq!(projective_dimension(&z, 4), Bounded::Exact(0));
}
#[test]
fn a3_simples_have_pd_1_1_0() {
let field = f5();
let algebra = linear_an(3, field);
let expected = [1usize, 1, 0];
for v in 0..3u32 {
let s = Module::simple(&algebra, v);
assert_eq!(
projective_dimension(&s, 5),
Bounded::Exact(expected[v as usize]),
"pd S_{v}"
);
}
}
#[test]
fn a3_projectives_resolve_finitely_in_one_term() {
let field = f5();
let algebra = linear_an(3, field);
for v in 0..3u32 {
let p = Module::projective(&algebra, v);
let res = resolve(&p, 5);
assert_eq!(res.end, ResolutionEnd::Finite, "P_{v}");
assert_eq!(res.terms.len(), 1, "P_{v}");
assert!(res.maps.is_empty());
}
}
#[test]
fn a3_mod_ab_simple_0_has_pd_2_with_terms_p0_p1_p2() {
let field = f5();
let algebra = an_with_relations(3, &[(0, 2)], field).unwrap();
let s0 = Module::simple(&algebra, 0);
let res = resolve(&s0, 5);
assert_eq!(res.end, ResolutionEnd::Finite);
let dims: Vec<&[usize]> = res.terms.iter().map(Module::dim_vector).collect();
assert_eq!(dims, vec![&[1, 1, 0][..], &[0, 1, 1], &[0, 0, 1]]);
assert_eq!(projective_dimension(&s0, 5), Bounded::Exact(2));
let s1 = Module::simple(&algebra, 1);
let s2 = Module::simple(&algebra, 2);
assert_eq!(projective_dimension(&s1, 5), Bounded::Exact(1));
assert_eq!(projective_dimension(&s2, 5), Bounded::Exact(0));
}
#[test]
fn dual_numbers_simple_resolves_periodically_and_pd_is_at_least_bound_plus_1() {
let field = f5();
let algebra = dual_numbers(field);
let s = Module::simple(&algebra, 0);
let res = resolve(&s, 6);
assert_eq!(res.end, ResolutionEnd::Cut { at: 6 });
assert_eq!(res.terms.len(), 7);
for term in &res.terms {
assert_eq!(term.dim_vector(), &[2]);
}
assert_eq!(projective_dimension(&s, 10), Bounded::AtLeast(11));
}
#[test]
fn resolve_with_zero_steps_reports_cut_for_a_nonprojective_module() {
let field = f5();
let algebra = dual_numbers(field);
let s = Module::simple(&algebra, 0);
let res = resolve(&s, 0);
assert_eq!(res.end, ResolutionEnd::Cut { at: 0 });
assert_eq!(res.terms.len(), 1);
let p = Module::projective(&algebra, 0);
assert_eq!(resolve(&p, 0).end, ResolutionEnd::Finite);
}
#[test]
fn radical_square_zero_cycle_simples_have_unbounded_pd() {
let field = f5();
let algebra = radical_square_zero_cycle(3, field);
for v in 0..3u32 {
let s = Module::simple(&algebra, v);
assert_eq!(projective_dimension(&s, 7), Bounded::AtLeast(8), "pd S_{v}");
}
}
fn assorted_modules() -> Vec<Module> {
let field = f5();
let mut modules = Vec::new();
for algebra in [
linear_an(3, field),
an_with_relations(3, &[(0, 2)], field).unwrap(),
dual_numbers(field),
truncated_poly(3, field).unwrap(),
radical_square_zero_cycle(3, field),
] {
for v in 0..algebra.quiver().num_vertices() {
modules.push(Module::simple(&algebra, v));
modules.push(Module::injective(&algebra, v));
}
let s0 = Module::simple(&algebra, 0);
let i_last = Module::injective(&algebra, algebra.quiver().num_vertices() - 1);
let (sum, _, _) = direct_sum(&[&s0, &i_last]);
modules.push(sum);
}
modules
}
#[test]
fn resolution_prefixes_are_complexes_and_exact() {
let field = f5();
for m in assorted_modules() {
let res = resolve(&m, 4);
for v in 0..m.algebra().quiver().num_vertices() {
assert_eq!(
res.augmentation.map_at(v).rank(&field),
m.dim_at(v),
"augmentation surjective at vertex {v}"
);
}
for pair in res.maps.windows(2) {
assert!(pair[1].then(&pair[0]).unwrap().is_zero(), "d² = 0");
}
if let Some(d1) = res.maps.first() {
assert!(
d1.then(&res.augmentation).unwrap().is_zero(),
"aug ∘ d_1 = 0"
);
}
for k in 0..res.terms.len() {
let (ker, _) = if k == 0 {
kernel(&res.augmentation)
} else {
kernel(&res.maps[k - 1])
};
if k + 1 < res.terms.len() {
let (im, _) = image(&res.maps[k]);
assert_eq!(ker.dim_vector(), im.dim_vector(), "exactness at P_{k}");
} else if res.end == ResolutionEnd::Finite {
assert!(ker.is_zero(), "finite resolution ends exactly");
}
}
}
}
#[test]
fn minimal_presentation_matrix_realizes_the_first_differential() {
for m in assorted_modules() {
let res = resolve(&m, 1);
let matrix = minimal_presentation_matrix(&m);
let f = matrix.morphism();
let (p0, _) = projective_cover(&m);
assert_eq!(f.target().dim_vector(), p0.dim_vector());
match res.maps.first() {
None => {
assert!(matrix.sources().is_empty());
assert!(f.source().is_zero());
}
Some(d1) => {
for v in 0..m.algebra().quiver().num_vertices() {
assert_eq!(f.map_at(v), d1.map_at(v), "d_1 at vertex {v}");
}
}
}
}
}
#[test]
fn minimal_presentation_matrix_of_a_projective_has_no_source_summands() {
let algebra = linear_an(3, f5());
let p1 = Module::projective(&algebra, 1);
let matrix = minimal_presentation_matrix(&p1);
assert!(matrix.sources().is_empty());
assert_eq!(matrix.targets(), &[1]);
}
#[test]
fn differentials_induce_zero_on_tops() {
for m in assorted_modules() {
let res = resolve(&m, 4);
for (k, d) in res.maps.iter().enumerate() {
let (_, projection) = top(&res.terms[k]);
assert!(
d.then(&projection).unwrap().is_zero(),
"d_{} lands in the radical",
k + 1
);
}
}
}
}