mod cache;
mod decision;
mod types;
pub use cache::TauCache;
pub(crate) use decision::is_tau_rigid_summandwise_with_context;
pub use decision::{is_tau_rigid, is_tau_rigid_summandwise};
pub use types::{NonTauRigidWitness, TauRigidError, TauRigidModule, TauRigidityOutcome};
#[cfg(test)]
mod tests {
use std::sync::Arc;
use super::*;
use crate::algebra::{Algebra, commutative_square, linear_an, truncated_poly};
use crate::ar::tau;
use crate::arquiver::IndecomposableCatalog;
use crate::dynkin::{DynkinType, dynkin_quiver};
use crate::field::PrimeField;
use crate::hom::{hom_dim, zero_morphism};
use crate::iso::{IsoOutcome, is_isomorphic};
use crate::linalg::DenseMat;
use crate::module::Module;
use crate::module::direct_sum;
fn fields() -> [PrimeField; 2] {
[PrimeField::new(2).unwrap(), PrimeField::new(5).unwrap()]
}
fn d4(field: PrimeField) -> Arc<Algebra> {
let quiver = dynkin_quiver(DynkinType::D(4)).expect("D_4 has a quiver");
crate::algebra::path_algebra(quiver, field)
.expect("the zero ideal over an acyclic quiver completes")
}
fn tp3(field: PrimeField) -> Arc<Algebra> {
truncated_poly(3, field).expect("k[x]/(x^3) is admissible")
}
fn uniserial(algebra: &Arc<Algebra>, m: usize) -> Module {
let field = algebra.field();
let mut action = DenseMat::zero(m, m);
for i in 0..m.saturating_sub(1) {
action.set(i, i + 1, field.one());
}
Module::new(algebra.clone(), vec![m], vec![action]).expect("a Jordan block is a module")
}
fn fixtures(field: PrimeField) -> Vec<(String, Vec<Module>)> {
let mut out = Vec::new();
for n in [2usize, 3] {
let algebra = linear_an(n, field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("A_n is Dynkin");
let modules = catalog
.entries()
.iter()
.map(|e| e.module().clone())
.collect();
out.push((format!("A_{n} over F_{}", field.modulus()), modules));
}
let tp = tp3(field);
out.push((
format!("truncated_poly(3) over F_{}", field.modulus()),
(1..=3).map(|m| uniserial(&tp, m)).collect(),
));
let cs = commutative_square(field);
let mut square = Vec::new();
for v in 0..cs.quiver().num_vertices() {
square.push(Module::simple(&cs, v));
square.push(Module::projective(&cs, v));
square.push(Module::injective(&cs, v));
}
out.push((
format!("commutative_square over F_{}", field.modulus()),
square,
));
out
}
fn subsets_up_to_three(n: usize) -> Vec<Vec<usize>> {
let mut out = vec![Vec::new()];
for i in 0..n {
out.push(vec![i]);
for j in i + 1..n {
out.push(vec![i, j]);
for k in j + 1..n {
out.push(vec![i, j, k]);
}
}
}
out
}
fn indexed(modules: &[Module], subset: &[usize]) -> Vec<(usize, Module)> {
subset.iter().map(|&i| (i, modules[i].clone())).collect()
}
fn summandwise_dim(summands: &[(usize, Module)], cache: &mut TauCache) -> usize {
let translates: Vec<Module> = summands
.iter()
.map(|(_, x)| cache.tau_of(x).expect("the fixture translates").clone())
.collect();
let mut total = 0;
for (_, x) in summands {
for translate in &translates {
if !translate.is_zero() {
total += hom_dim(x, translate).expect("one algebra");
}
}
}
total
}
fn assembled_dim(modules: &[&Module]) -> usize {
if modules.is_empty() {
return 0;
}
let (m, _, _) = direct_sum(modules);
let t = tau(&m).expect("the fixture translates");
if t.is_zero() {
0
} else {
hom_dim(&m, &t).expect("one algebra")
}
}
fn expect_rigid(outcome: TauRigidityOutcome) -> TauRigidModule {
match outcome {
TauRigidityOutcome::TauRigid(rigid) => rigid,
TauRigidityOutcome::NotTauRigid(witness) => {
panic!(
"expected tau-rigid, got a witness at {:?}",
(witness.source_index(), witness.target_index())
)
}
}
}
fn expect_not_rigid(outcome: TauRigidityOutcome) -> NonTauRigidWitness {
match outcome {
TauRigidityOutcome::NotTauRigid(witness) => witness,
TauRigidityOutcome::TauRigid(_) => panic!("expected a nonzero witness"),
}
}
#[test]
fn the_cached_double_route_matches_the_uncached_one() {
for field in fields() {
for (name, modules) in fixtures(field) {
let mut cache = TauCache::new();
for (index, x) in modules.iter().enumerate() {
let cached = cache.tau_of(x).expect("the fixture translates").clone();
let plain = tau(x).expect("the fixture translates");
assert_eq!(
cached.is_zero(),
plain.is_zero(),
"{name}: one route called module {index} projective"
);
assert!(
cached.is_zero()
|| matches!(
is_isomorphic(&cached, &plain),
Ok(IsoOutcome::Isomorphic(_))
),
"{name}: cached and plain translates of module {index} differ"
);
}
}
}
}
#[test]
fn cache_counters_are_exact_and_a_hit_repeats_the_miss_value() {
let algebra = linear_an(3, PrimeField::new(5).unwrap());
let s0 = Module::simple(&algebra, 0);
let s1 = Module::simple(&algebra, 1);
let mut cache = TauCache::new();
assert!(cache.is_empty());
let first = cache.tau_of(&s0).expect("A_3 translates").clone();
assert_eq!((cache.len(), cache.hits(), cache.misses()), (1, 0, 1));
let again = cache.tau_of(&s0).expect("A_3 translates").clone();
assert_eq!((cache.len(), cache.hits(), cache.misses()), (1, 1, 1));
assert!(first.ptr_eq(&again));
assert_eq!(first.dim_vector(), &[0, 1, 0]);
cache.tau_of(&s1).expect("A_3 translates");
assert_eq!((cache.len(), cache.hits(), cache.misses()), (2, 1, 2));
for _ in 0..3 {
cache.tau_of(&s1.clone()).expect("A_3 translates");
}
assert_eq!((cache.len(), cache.hits(), cache.misses()), (2, 4, 2));
cache
.tau_of(&Module::simple(&algebra, 0))
.expect("A_3 translates");
assert_eq!((cache.len(), cache.hits(), cache.misses()), (3, 4, 3));
}
#[test]
fn every_projective_is_tau_rigid() {
for field in fields() {
for algebra in [
linear_an(2, field),
linear_an(3, field),
tp3(field),
commutative_square(field),
d4(field),
] {
let projectives: Vec<(usize, Module)> = (0..algebra.quiver().num_vertices())
.map(|v| (v as usize, Module::projective(&algebra, v)))
.collect();
let mut cache = TauCache::new();
for single in &projectives {
let rigid = expect_rigid(
is_tau_rigid_summandwise(std::slice::from_ref(single), &mut cache)
.expect("the fixture translates"),
);
assert!(rigid.translates()[0].is_zero());
assert!(rigid.vanishing_pairs().is_empty());
assert!(rigid.verify());
}
let rigid = expect_rigid(
is_tau_rigid_summandwise(&projectives, &mut cache)
.expect("the fixture translates"),
);
assert!(rigid.vanishing_pairs().is_empty());
assert_eq!(rigid.summands().len(), projectives.len());
assert!(rigid.verify());
}
}
}
#[test]
fn the_zero_module_is_tau_rigid() {
for field in fields() {
let algebra = linear_an(3, field);
let rigid = expect_rigid(
is_tau_rigid_summandwise(&[], &mut TauCache::new()).expect("no summand, no work"),
);
assert!(rigid.is_zero_module());
assert!(rigid.vanishing_pairs().is_empty());
assert!(rigid.translates().is_empty());
assert!(rigid.verify());
let through_decompose = expect_rigid(
is_tau_rigid(&Module::zero(&algebra)).expect("the zero module needs no translate"),
);
assert!(through_decompose.is_zero_module());
assert!(through_decompose.verify());
}
}
#[test]
fn the_a2_subsets_match_the_hand_table() {
for field in fields() {
let algebra = linear_an(2, field);
let modules = [
Module::simple(&algebra, 0),
Module::simple(&algebra, 1),
Module::projective(&algebra, 0),
];
let mut cache = TauCache::new();
assert_eq!(
cache
.tau_of(&modules[0])
.expect("A_2 translates")
.dim_vector()
.to_vec(),
vec![0, 1]
);
let mut rigid_count = 0;
for subset in subsets_up_to_three(3) {
let summands = indexed(&modules, &subset);
let both = subset.contains(&0) && subset.contains(&1);
let outcome =
is_tau_rigid_summandwise(&summands, &mut cache).expect("A_2 translates");
assert_eq!(
outcome.is_tau_rigid(),
!both,
"subset {subset:?} over F_{}",
field.modulus()
);
match outcome {
TauRigidityOutcome::TauRigid(r) => {
rigid_count += 1;
assert!(r.verify());
}
TauRigidityOutcome::NotTauRigid(w) => {
assert_eq!((w.source_index(), w.target_index()), (1, 0));
assert!(w.verify());
}
}
}
assert_eq!(rigid_count, 6);
}
}
#[test]
fn the_a3_pair_of_simples_fails_at_the_first_nonzero_pair_in_order() {
for field in fields() {
let algebra = linear_an(3, field);
let s0 = Module::simple(&algebra, 0);
let s1 = Module::simple(&algebra, 1);
let summands = vec![(0, s0.clone()), (1, s1.clone())];
let witness = expect_not_rigid(
is_tau_rigid_summandwise(&summands, &mut TauCache::new()).expect("A_3 translates"),
);
assert_eq!(witness.source_index(), 1);
assert_eq!(witness.target_index(), 0);
assert!(witness.source().ptr_eq(&s1));
assert!(witness.target_summand().ptr_eq(&s0));
assert_eq!(witness.translate().dim_vector(), &[0, 1, 0]);
assert!(!witness.morphism().is_zero());
assert!(witness.verify());
let reversed = vec![(1, s1), (0, s0)];
let other = expect_not_rigid(
is_tau_rigid_summandwise(&reversed, &mut TauCache::new()).expect("A_3 translates"),
);
assert_eq!((other.source_index(), other.target_index()), (1, 0));
assert!(other.verify());
}
}
#[test]
fn the_truncated_poly_uniserials_are_not_tau_rigid() {
for field in fields() {
let algebra = tp3(field);
for m in [1usize, 2] {
let u = uniserial(&algebra, m);
let mut cache = TauCache::new();
let translate = cache.tau_of(&u).expect("k[x]/(x^3) translates").clone();
assert!(!translate.is_zero(), "U_{m} is not projective");
assert_eq!(translate.dim_vector(), &[m]);
assert_eq!(hom_dim(&u, &translate).expect("one algebra"), m);
let witness = expect_not_rigid(
is_tau_rigid_summandwise(&[(0, u.clone())], &mut cache)
.expect("k[x]/(x^3) translates"),
);
assert_eq!((witness.source_index(), witness.target_index()), (0, 0));
assert!(!witness.morphism().is_zero());
assert!(witness.verify());
assert!(!is_tau_rigid(&u).expect("k[x]/(x^3)").is_tau_rigid());
}
let regular = uniserial(&algebra, 3);
let rigid = expect_rigid(is_tau_rigid(®ular).expect("A is projective"));
assert!(rigid.translates()[0].is_zero());
assert!(rigid.verify());
}
}
#[test]
fn summandwise_agrees_with_the_assembled_route_on_every_small_d4_subset() {
for field in fields() {
let algebra = d4(field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("D_4 is Dynkin");
let modules: Vec<Module> = catalog
.entries()
.iter()
.map(|e| e.module().clone())
.collect();
assert_eq!(modules.len(), 12, "D_4 has 12 indecomposables");
let subsets = subsets_up_to_three(modules.len());
assert_eq!(subsets.len(), 299);
let mut cache = TauCache::new();
for subset in &subsets {
let summands = indexed(&modules, subset);
let refs: Vec<&Module> = subset.iter().map(|&i| &modules[i]).collect();
let split = summandwise_dim(&summands, &mut cache);
assert_eq!(
split,
assembled_dim(&refs),
"subset {subset:?} over F_{}",
field.modulus()
);
let outcome = is_tau_rigid_summandwise(&summands, &mut cache)
.expect("the D_4 catalog translates");
assert_eq!(outcome.is_tau_rigid(), split == 0, "subset {subset:?}");
match outcome {
TauRigidityOutcome::TauRigid(rigid) => assert!(rigid.verify()),
TauRigidityOutcome::NotTauRigid(witness) => assert!(witness.verify()),
}
}
assert_eq!(cache.len(), modules.len());
assert_eq!(cache.misses(), modules.len() as u64);
}
}
#[test]
fn summandwise_agrees_with_the_assembled_route_on_the_small_fixtures() {
for field in fields() {
for (name, modules) in fixtures(field) {
let mut cache = TauCache::new();
for subset in subsets_up_to_three(modules.len()) {
let summands = indexed(&modules, &subset);
let refs: Vec<&Module> = subset.iter().map(|&i| &modules[i]).collect();
let split = summandwise_dim(&summands, &mut cache);
assert_eq!(split, assembled_dim(&refs), "{name}: subset {subset:?}");
let outcome = is_tau_rigid_summandwise(&summands, &mut cache)
.expect("the fixture translates");
assert_eq!(
outcome.is_tau_rigid(),
split == 0,
"{name}: subset {subset:?}"
);
}
}
}
}
#[test]
fn the_convenience_entry_point_agrees_with_the_summandwise_one() {
for field in fields() {
for (name, modules) in fixtures(field) {
let mut cache = TauCache::new();
for subset in subsets_up_to_three(modules.len()) {
if subset.is_empty() {
continue;
}
let refs: Vec<&Module> = subset.iter().map(|&i| &modules[i]).collect();
let (assembled, _, _) = direct_sum(&refs);
let summands = indexed(&modules, &subset);
let split = is_tau_rigid_summandwise(&summands, &mut cache)
.expect("the fixture translates");
let whole = is_tau_rigid(&assembled).expect("the fixture translates");
assert_eq!(
split.is_tau_rigid(),
whole.is_tau_rigid(),
"{name}: subset {subset:?}"
);
}
}
}
}
#[test]
fn a_tampered_non_tau_rigid_witness_fails_verification() {
for field in fields() {
let algebra = tp3(field);
let u2 = uniserial(&algebra, 2);
let witness = expect_not_rigid(
is_tau_rigid_summandwise(&[(0, u2.clone())], &mut TauCache::new())
.expect("k[x]/(x^3) translates"),
);
assert!(witness.verify());
let mut zeroed = witness.clone();
zeroed.morphism =
zero_morphism(witness.source(), witness.translate()).expect("one algebra");
assert!(!zeroed.verify(), "a zero morphism proves nothing");
let mut wrong_summand = witness.clone();
wrong_summand.target_summand = uniserial(&algebra, 1);
assert!(!wrong_summand.verify());
let mut wrong_translate = witness.clone();
wrong_translate.translate = uniserial(&algebra, 2);
assert!(!wrong_translate.verify());
}
}
#[test]
fn a_tampered_tau_rigid_module_fails_verification() {
for field in fields() {
let algebra = linear_an(3, field);
let s0 = Module::simple(&algebra, 0);
let s1 = Module::simple(&algebra, 1);
let rigid = expect_rigid(
is_tau_rigid_summandwise(&[(0, s0.clone())], &mut TauCache::new())
.expect("A_3 translates"),
);
assert!(rigid.verify());
assert_eq!(rigid.vanishing_pairs(), vec![(0, 0)]);
let mut truncated = rigid.clone();
truncated.translates.clear();
assert!(!truncated.verify(), "one translate per summand or nothing");
let mut claimed_projective = rigid.clone();
claimed_projective.translates[0] = Module::zero(&algebra);
assert!(!claimed_projective.verify(), "S_0 is not projective");
let mut swapped_target = rigid.clone();
swapped_target.translates[0] = s0.clone();
assert!(
!swapped_target.verify(),
"S_0 is not the translate of S_0 over A_3"
);
let mut forged = rigid.clone();
forged.summands.push((1, s1));
forged.translates.push(
is_tau_rigid_summandwise(&[(1, Module::simple(&algebra, 1))], &mut TauCache::new())
.map(|outcome| match outcome {
TauRigidityOutcome::TauRigid(r) => r.translates()[0].clone(),
TauRigidityOutcome::NotTauRigid(_) => panic!("S_1 is tau-rigid alone"),
})
.expect("A_3 translates"),
);
assert!(!forged.verify());
}
}
fn kronecker_pair(field: PrimeField) -> (Module, Module) {
let algebra = crate::algebra::kronecker(2, field);
let one = DenseMat::from_rows(&[vec![field.one()]]);
let zero = DenseMat::zero(1, 1);
let build = |maps: Vec<DenseMat>| {
Module::new(algebra.clone(), vec![1, 1], maps).expect("a kronecker representation")
};
(
build(vec![one.clone(), zero.clone()]),
build(vec![zero, one]),
)
}
#[test]
fn a_shared_cache_separates_two_modules_with_one_dimension_vector() {
for field in fields() {
let (x, y) = kronecker_pair(field);
let mut cache = TauCache::new();
let tau_x = cache.tau_of(&x).expect("kronecker translates").clone();
let tau_y = cache.tau_of(&y).expect("kronecker translates").clone();
assert_eq!(hom_dim(&x, &tau_x).expect("one algebra"), 1);
assert_eq!(hom_dim(&y, &tau_y).expect("one algebra"), 1);
let outcome = is_tau_rigid_summandwise(&[(0, y.clone())], &mut cache)
.expect("kronecker translates");
assert!(
!outcome.is_tau_rigid(),
"Hom(Y, tau Y) has dimension 1, so Y is not tau-rigid"
);
}
}
}