use std::sync::Arc;
use auslander::algebra::{
Algebra, an_with_relations, commutative_square, cyclic_nakayama, dual_numbers, linear_an,
monomial_algebra,
};
use auslander::ext::ext_table;
use auslander::field::{Fp, PrimeField};
use auslander::hom::{Morphism, hom, hom_dim, kernel};
use auslander::linalg::DenseMat;
use auslander::module::Module;
use auslander::monomial::MonomialIdeal;
use auslander::quiver::{ArrowId, Quiver};
use auslander::radical::radical;
use auslander::resolution::{ResolutionEnd, projective_cover, resolve};
mod common;
use common::{XorShift64, case_seed, rand_elem, random_basis_change};
const MAX_TOTAL_DIM: usize = 12;
const CASES: usize = 8;
const SEED_BASE: u64 = 0x0005_eed0_fa05_1a4d;
fn fields() -> [PrimeField; 2] {
[PrimeField::new(2).unwrap(), PrimeField::new(3).unwrap()]
}
fn gentle_tree(field: PrimeField) -> Arc<Algebra> {
let quiver = Quiver::new(4, &[(0, 1), (1, 2), (1, 3)]).unwrap();
let ideal = MonomialIdeal::new(quiver, vec![vec![ArrowId(0), ArrowId(1)]]).unwrap();
monomial_algebra(&ideal, field).unwrap()
}
fn algebras(field: PrimeField) -> Vec<(&'static str, Arc<Algebra>)> {
vec![
("linear_an_3", linear_an(3, field)),
("a3_mod_ab", an_with_relations(3, &[(0, 2)], field).unwrap()),
("gentle_tree", gentle_tree(field)),
(
"cyclic_nakayama_3_3_3",
cyclic_nakayama(&[3, 3, 3], field).unwrap(),
),
("dual_numbers", dual_numbers(field)),
("commutative_square", commutative_square(field)),
]
}
fn stacked(rows: &[Vec<Fp>], cols: usize) -> DenseMat {
let mut out = DenseMat::zero(rows.len(), cols);
for (r, row) in rows.iter().enumerate() {
for (c, &v) in row.iter().enumerate() {
out.set(r, c, v);
}
}
out
}
fn vstack(a: &DenseMat, b: &DenseMat) -> DenseMat {
let rows: Vec<Vec<Fp>> = (0..a.rows())
.map(|r| a.row(r).to_vec())
.chain((0..b.rows()).map(|r| b.row(r).to_vec()))
.collect();
stacked(&rows, a.cols())
}
fn random_closed_submodule_bases(rng: &mut XorShift64, m: &Module) -> Vec<DenseMat> {
let field = m.field();
let quiver = m.algebra().quiver();
let n = quiver.num_vertices();
let mut bases: Vec<DenseMat> = (0..n)
.map(|v| {
let d = m.dim_at(v);
let rows: Vec<Vec<Fp>> = (0..rng.below(3))
.map(|_| (0..d).map(|_| rand_elem(rng, &field)).collect())
.collect();
stacked(&rows, d).row_space_basis(&field)
})
.collect();
loop {
let mut changed = false;
for i in 0..quiver.num_arrows() {
let a = ArrowId(i as u32);
let (u, v) = (quiver.source(a) as usize, quiver.target(a) as usize);
let image = bases[u].mul(m.map(a), &field);
let closed = vstack(&bases[v], &image).row_space_basis(&field);
if closed.rows() != bases[v].rows() {
bases[v] = closed;
changed = true;
}
}
if !changed {
return bases;
}
}
}
fn rows_in_basis(basis: &DenseMat, vectors: &DenseMat, field: &PrimeField) -> DenseMat {
let bt = basis.transpose();
let mut out = DenseMat::zero(vectors.rows(), basis.rows());
for r in 0..vectors.rows() {
let x = bt
.solve(vectors.row(r), field)
.expect("the closure is arrow-invariant, so images lie in the span");
for (c, &v) in x.iter().enumerate() {
out.set(r, c, v);
}
}
out
}
fn submodule_from_closure(m: &Module, bases: &[DenseMat]) -> (Module, Morphism) {
let field = m.field();
let quiver = m.algebra().quiver();
let dims: Vec<usize> = bases.iter().map(DenseMat::rows).collect();
let maps: Vec<DenseMat> = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (u, v) = (quiver.source(a) as usize, quiver.target(a) as usize);
rows_in_basis(&bases[v], &bases[u].mul(m.map(a), &field), &field)
})
.collect();
let sub = Module::new(m.algebra().clone(), dims, maps)
.expect("the arrow closure carries a submodule");
let inclusion =
Morphism::new(&sub, m, bases.to_vec()).expect("the closure inclusion is A-linear");
(sub, inclusion)
}
fn quotient_from_closure(m: &Module, bases: &[DenseMat]) -> (Module, Morphism) {
let field = m.field();
let quiver = m.algebra().quiver();
let projections: Vec<DenseMat> = bases
.iter()
.map(|b| b.kernel_basis(&field).transpose())
.collect();
let dims: Vec<usize> = projections.iter().map(DenseMat::cols).collect();
let maps: Vec<DenseMat> = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (u, v) = (quiver.source(a) as usize, quiver.target(a) as usize);
let rhs = m.map(a).mul(&projections[v], &field);
let rhs_t = rhs.transpose();
let mut c = DenseMat::zero(projections[u].cols(), rhs.cols());
for j in 0..rhs.cols() {
let x = projections[u]
.solve(rhs_t.row(j), &field)
.expect("invariance puts each column in the projection's column space");
for (r, &val) in x.iter().enumerate() {
c.set(r, j, val);
}
}
c
})
.collect();
let quotient = Module::new(m.algebra().clone(), dims, maps)
.expect("the quotient by a closed submodule is a module");
let projection =
Morphism::new(m, "ient, projections).expect("the quotient projection is A-linear");
(quotient, projection)
}
fn rows_lie_in_row_space(basis: &DenseMat, rows: &DenseMat, field: &PrimeField) -> bool {
let base_rank = basis.rank(field);
vstack(basis, rows).rank(field) == base_rank
}
fn ext_table_via_generic_hom(m: &Module, n: &Module, max_k: usize) -> Vec<usize> {
let field = m.field();
let nv = m.algebra().quiver().num_vertices();
let res = resolve(m, max_k + 1);
let bases: Vec<Vec<Morphism>> = res
.terms
.iter()
.map(|t| hom(t, n).expect("resolution terms share their algebra with n"))
.collect();
let flatten = |f: &Morphism| -> Vec<Fp> {
let mut out = Vec::new();
for v in 0..nv {
let map = f.map_at(v);
for r in 0..map.rows() {
out.extend_from_slice(map.row(r));
}
}
out
};
let h: Vec<usize> = (0..=max_k)
.map(|i| bases.get(i).map_or(0, Vec::len))
.collect();
let ranks: Vec<usize> = (0..=max_k)
.map(|i| {
if i + 1 >= res.terms.len() || bases[i].is_empty() {
return 0;
}
let rows: Vec<Vec<Fp>> = bases[i]
.iter()
.map(|f| flatten(&res.maps[i].then(f).expect("d targets the term f leaves")))
.collect();
DenseMat::from_rows(&rows).rank(&field)
})
.collect();
(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,
"δ² != 0 in the generic recomputation"
);
kernel_dim - boundary
})
.collect()
}
fn for_each_case(
test: u64,
mut body: impl FnMut(&mut XorShift64, &Arc<Algebra>, PrimeField, &str),
) {
for field in fields() {
for (algebra_idx, (name, algebra)) in algebras(field).iter().enumerate() {
for case in 0..CASES {
let seed = case_seed(SEED_BASE, test, field.modulus(), algebra_idx, case);
println!(
"{name} over F_{} case {case}: seed {seed:#018x}",
field.modulus()
);
let mut rng = XorShift64(seed);
body(&mut rng, algebra, field, name);
}
}
}
}
#[test]
fn basis_changed_sums_stay_valid_isomorphic_and_hom_ext_invariant() {
for_each_case(1, |rng, algebra, _field, name| {
let m = common::random_sum_module(rng, algebra, MAX_TOTAL_DIM);
let (t, g) = random_basis_change(rng, &m);
assert_eq!(t.dim_vector(), m.dim_vector(), "{name}");
let iso = Morphism::new(&t, &m, g).expect("the G_v matrices form a morphism M' -> M");
assert!(
iso.is_isomorphism(),
"{name}: G_v must be invertible at every vertex"
);
let n = algebra.quiver().num_vertices();
for v in 0..n {
let s = Module::simple(algebra, v);
assert_eq!(
hom_dim(&t, &s).unwrap(),
hom_dim(&m, &s).unwrap(),
"{name}: dim Hom(-, S_{v}) changed under basis change"
);
assert_eq!(
hom_dim(&s, &t).unwrap(),
hom_dim(&s, &m).unwrap(),
"{name}: dim Hom(S_{v}, -) changed under basis change"
);
}
assert_eq!(
hom_dim(&t, &t).unwrap(),
hom_dim(&m, &m).unwrap(),
"{name}: dim End changed under basis change"
);
let v = rng.below(u64::from(n)) as u32;
let s = Module::simple(algebra, v);
assert_eq!(
ext_table(&t, &s, 2).unwrap(),
ext_table(&m, &s, 2).unwrap(),
"{name}: Ext table against S_{v} changed under basis change"
);
});
}
#[test]
fn closed_submodules_and_quotients_are_modules_with_exact_dimensions() {
for_each_case(2, |rng, algebra, _field, name| {
let m = common::random_sum_module(rng, algebra, MAX_TOTAL_DIM);
let bases = random_closed_submodule_bases(rng, &m);
let (sub, inclusion) = submodule_from_closure(&m, &bases);
let (quotient, projection) = quotient_from_closure(&m, &bases);
for v in 0..algebra.quiver().num_vertices() {
assert_eq!(
sub.dim_at(v) + quotient.dim_at(v),
m.dim_at(v),
"{name}: dimensions at vertex {v}"
);
}
let composite = inclusion.then(&projection).expect("shared middle module");
assert!(composite.is_zero(), "{name}: sub -> m -> m/sub must vanish");
});
}
#[test]
fn covers_of_random_modules_are_surjective_with_syzygy_in_the_radical() {
for_each_case(3, |rng, algebra, field, name| {
let base = common::random_sum_module(rng, algebra, MAX_TOTAL_DIM);
let (transformed, _) = random_basis_change(rng, &base);
let bases = random_closed_submodule_bases(rng, &base);
let (sub, _) = submodule_from_closure(&base, &bases);
for m in [&base, &transformed, &sub] {
let (p, cover) = projective_cover(m);
let (syzygy, syzygy_inclusion) = kernel(&cover);
let (_, radical_inclusion) = radical(&p);
for v in 0..algebra.quiver().num_vertices() {
assert_eq!(
cover.map_at(v).rank(&field),
m.dim_at(v),
"{name}: cover not surjective at vertex {v}"
);
assert!(
rows_lie_in_row_space(
radical_inclusion.map_at(v),
syzygy_inclusion.map_at(v),
&field
),
"{name}: syzygy escapes rad P at vertex {v} (dim syzygy {})",
syzygy.total_dim()
);
}
}
});
}
#[test]
fn resolution_prefixes_of_random_modules_are_exact_complexes() {
for_each_case(4, |rng, algebra, field, name| {
let base = common::random_sum_module(rng, algebra, MAX_TOTAL_DIM);
let (transformed, _) = random_basis_change(rng, &base);
let bases = random_closed_submodule_bases(rng, &base);
let (sub, _) = submodule_from_closure(&base, &bases);
let (quotient, _) = quotient_from_closure(&base, &bases);
for m in [&transformed, &sub, "ient] {
let res = resolve(m, 3);
for v in 0..algebra.quiver().num_vertices() {
assert_eq!(
res.augmentation.map_at(v).rank(&field),
m.dim_at(v),
"{name}: augmentation not surjective at vertex {v}"
);
}
if let Some(d1) = res.maps.first() {
assert!(
d1.then(&res.augmentation).unwrap().is_zero(),
"{name}: aug ∘ d_1 != 0"
);
}
for pair in res.maps.windows(2) {
assert!(pair[1].then(&pair[0]).unwrap().is_zero(), "{name}: d² != 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() {
for v in 0..algebra.quiver().num_vertices() {
assert_eq!(
ker.dim_at(v),
res.maps[k].map_at(v).rank(&field),
"{name}: exactness fails at P_{k}, vertex {v}"
);
}
} else if res.end == ResolutionEnd::Finite {
assert!(ker.is_zero(), "{name}: finite resolution must end exactly");
}
}
}
});
}
#[test]
fn yoneda_ext_agrees_with_generic_hom_cochain_ext() {
for_each_case(5, |rng, algebra, _field, name| {
let base = common::random_sum_module(rng, algebra, MAX_TOTAL_DIM);
let (m, _) = random_basis_change(rng, &base);
let nv = algebra.quiver().num_vertices();
let v = rng.below(u64::from(nv)) as u32;
let targets = [Module::simple(algebra, v), Module::injective(algebra, v)];
for n in &targets {
assert_eq!(
ext_table(&m, n, 2).unwrap(),
ext_table_via_generic_hom(&m, n, 2),
"{name}: Yoneda and generic-cochain Ext disagree against vertex {v}"
);
}
});
}
#[test]
fn hom_into_an_injective_has_the_dimension_of_the_module_at_its_vertex() {
for_each_case(6, |rng, algebra, _field, name| {
let base = common::random_sum_module(rng, algebra, MAX_TOTAL_DIM);
let (transformed, _) = random_basis_change(rng, &base);
let bases = random_closed_submodule_bases(rng, &base);
let (sub, _) = submodule_from_closure(&base, &bases);
let (quotient, _) = quotient_from_closure(&base, &bases);
for m in [&base, &transformed, &sub, "ient] {
for v in 0..algebra.quiver().num_vertices() {
let injective = Module::injective(algebra, v);
assert_eq!(
hom_dim(m, &injective).unwrap(),
m.dim_at(v),
"{name}: dim Hom(M, I_{v}) != dim M_{v}"
);
}
}
});
}