use std::sync::OnceLock;
use crate::decompose::{Certificate, Decomposition, add_morphisms, decompose, mutually_inverse};
use crate::endo::EndoAlgebra;
use crate::hom::{HomError, Morphism, hom_dim, identity, zero_morphism};
use crate::homspace::HomSpace;
use crate::module::Module;
use crate::profile::{Site, hit};
use crate::radical::radical_series as module_radical_series;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Obstruction {
DimensionVector {
source: Vec<usize>,
target: Vec<usize>,
},
LoewySeries {
source: Vec<Vec<usize>>,
target: Vec<Vec<usize>>,
},
HomDimension {
end_source: usize,
end_target: usize,
forward: usize,
backward: usize,
},
RadicalCriterion,
UnmatchedSummand {
dim_vector: Vec<usize>,
},
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum IsoOutcome {
Isomorphic(Morphism),
NotIsomorphic(Obstruction),
Unknown {
reason: String,
},
}
#[derive(Clone, Debug)]
pub(crate) struct Fingerprint {
module: Module,
endo_dim: usize,
residue_degree: usize,
loewy: OnceLock<Loewy>,
}
#[derive(Clone, Debug, PartialEq, Eq)]
struct Loewy {
radical: Vec<Vec<usize>>,
socle: Vec<Vec<usize>>,
}
impl PartialEq for Fingerprint {
fn eq(&self, other: &Fingerprint) -> bool {
self.endo_dim == other.endo_dim
&& self.residue_degree == other.residue_degree
&& self.module.dim_vector() == other.module.dim_vector()
&& self.loewy() == other.loewy()
}
}
impl Eq for Fingerprint {}
impl Fingerprint {
pub(crate) fn of(m: &Module, endo: &EndoAlgebra) -> Fingerprint {
hit(Site::FingerprintOf);
Fingerprint {
module: m.clone(),
endo_dim: endo.dim(),
residue_degree: endo.quotient_dim(),
loewy: OnceLock::new(),
}
}
fn loewy(&self) -> &Loewy {
self.loewy.get_or_init(|| Loewy {
radical: radical_series(&self.module),
socle: socle_series(&self.module),
})
}
}
pub(crate) fn indecomposable_iso(m: &Module, n: &Module, endo_m: &EndoAlgebra) -> Option<Morphism> {
hit(Site::IndecomposableIso);
if !std::sync::Arc::ptr_eq(m.algebra(), n.algebra()) || m.dim_vector() != n.dim_vector() {
return None;
}
let forward = HomSpace::new(m, n).expect("the algebras were compared above");
if forward.dim() != endo_m.dim() {
return None;
}
let backward = HomSpace::new(n, m).expect("the algebras were compared above");
if backward.dim() != endo_m.dim() {
return None;
}
for h in forward.basis_iter() {
for k in backward.basis() {
let u = h.then(k).expect("endpoints agree");
if !endo_m.in_radical(&endo_m.coords(&u)) {
return Some(h);
}
}
}
None
}
fn undetermined_reason(d: &Decomposition) -> Option<String> {
d.certificates().iter().find_map(|c| match c {
Certificate::Undetermined { attempts } => Some(format!(
"a summand stayed undetermined after {attempts} split attempts"
)),
Certificate::Indecomposable => None,
})
}
fn dimension_vectors<'a>(modules: impl Iterator<Item = &'a Module>) -> Vec<Vec<usize>> {
modules.map(|module| module.dim_vector().to_vec()).collect()
}
fn radical_series(m: &Module) -> Vec<Vec<usize>> {
let series = module_radical_series(m);
dimension_vectors(series.iter().skip(1).take_while(|layer| !layer.is_zero()))
}
fn socle_series(m: &Module) -> Vec<Vec<usize>> {
let series = crate::radical::socle_series(m);
dimension_vectors(series.iter().skip(1))
}
fn certified_single(d: &Decomposition) -> bool {
d.certificates() == [Certificate::Indecomposable]
}
fn structural_outcome(m: &Module, n: &Module, zero: &Morphism) -> Option<IsoOutcome> {
if m.dim_vector() != n.dim_vector() {
return Some(IsoOutcome::NotIsomorphic(Obstruction::DimensionVector {
source: m.dim_vector().to_vec(),
target: n.dim_vector().to_vec(),
}));
}
if m.is_zero() {
return Some(IsoOutcome::Isomorphic(zero.clone()));
}
if Module::ptr_eq(m, n) {
return Some(IsoOutcome::Isomorphic(identity(m)));
}
let source = radical_series(m);
let target = radical_series(n);
(source != target).then_some(IsoOutcome::NotIsomorphic(Obstruction::LoewySeries {
source,
target,
}))
}
fn hom_dimensions(m: &Module, n: &Module) -> Result<[usize; 4], HomError> {
Ok([
hom_dim(m, m)?,
hom_dim(n, n)?,
hom_dim(m, n)?,
hom_dim(n, m)?,
])
}
fn hom_dimension_obstruction(dimensions: [usize; 4]) -> Option<Obstruction> {
let [end_source, end_target, forward, backward] = dimensions;
(end_source != end_target || forward != backward).then_some(Obstruction::HomDimension {
end_source,
end_target,
forward,
backward,
})
}
fn decomposition_outcome(
m: &Module,
n: &Module,
source: &Decomposition,
target: &Decomposition,
) -> Result<Option<IsoOutcome>, HomError> {
if certified_single(source) && certified_single(target) {
return Ok(None);
}
if let Some(obstruction) = hom_dimension_obstruction(hom_dimensions(m, n)?) {
return Ok(Some(IsoOutcome::NotIsomorphic(obstruction)));
}
Ok(undetermined_reason(source)
.or_else(|| undetermined_reason(target))
.map(|reason| IsoOutcome::Unknown { reason }))
}
fn matching_summand(
module: &Module,
endo: &EndoAlgebra,
target: &Decomposition,
used: &[bool],
) -> Option<(usize, Morphism)> {
for (index, candidate) in target.summands().iter().enumerate() {
if used[index] {
continue;
}
if let Some(witness) = indecomposable_iso(module, candidate, endo) {
return Some((index, witness));
}
}
None
}
fn match_decompositions(
m: &Module,
n: &Module,
source: &Decomposition,
target: &Decomposition,
mut witness: Morphism,
) -> IsoOutcome {
let mut used = vec![false; target.summands().len()];
for (source_index, module) in source.summands().iter().enumerate() {
let Some((target_index, isomorphism)) =
matching_summand(module, &source.endos()[source_index], target, &used)
else {
return if source.summands().len() == 1 && target.summands().len() == 1 {
IsoOutcome::NotIsomorphic(Obstruction::RadicalCriterion)
} else {
IsoOutcome::NotIsomorphic(Obstruction::UnmatchedSummand {
dim_vector: module.dim_vector().to_vec(),
})
};
};
used[target_index] = true;
let term = source.split().projections()[source_index]
.then(&isomorphism)
.expect("endpoints agree")
.then(&target.split().inclusions()[target_index])
.expect("endpoints agree");
witness = add_morphisms(&witness, &term);
}
verified(m, n, witness)
}
pub fn is_isomorphic(m: &Module, n: &Module) -> Result<IsoOutcome, HomError> {
hit(Site::IsIsomorphic);
let zero = zero_morphism(m, n)?;
if let Some(outcome) = structural_outcome(m, n, &zero) {
return Ok(outcome);
}
let dm = decompose(m);
let dn = decompose(n);
if let Some(outcome) = decomposition_outcome(m, n, &dm, &dn)? {
return Ok(outcome);
}
Ok(match_decompositions(m, n, &dm, &dn, zero))
}
fn verified(m: &Module, n: &Module, witness: Morphism) -> IsoOutcome {
let field = m.field();
let unknown = |reason: &str| IsoOutcome::Unknown {
reason: reason.to_string(),
};
let Some(inverse_maps) = (0..m.algebra().quiver().num_vertices())
.map(|v| witness.map_at(v).inverse(&field))
.collect::<Option<Vec<_>>>()
else {
return unknown("assembled witness is singular at a vertex");
};
match Morphism::new(n, m, inverse_maps) {
Ok(inverse) => {
if mutually_inverse(&witness, &inverse) {
IsoOutcome::Isomorphic(witness)
} else {
unknown("assembled witness has no two-sided inverse")
}
}
Err(_) => unknown("inverse of the assembled witness is not A-linear"),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{dual_numbers, kronecker, linear_an};
use crate::field::PrimeField;
use crate::linalg::DenseMat;
use crate::module::direct_sum;
fn fields() -> [PrimeField; 2] {
[PrimeField::new(2).unwrap(), PrimeField::new(5).unwrap()]
}
fn expect_witness(outcome: IsoOutcome, m: &Module, n: &Module) -> Morphism {
match outcome {
IsoOutcome::Isomorphic(w) => {
assert!(w.source().ptr_eq(m) && w.target().ptr_eq(n));
assert!(w.is_isomorphism());
w
}
other => panic!("expected an isomorphism, got {other:?}"),
}
}
#[test]
fn a_module_is_isomorphic_to_itself_and_to_a_fresh_copy() {
for field in fields() {
let a = linear_an(3, field);
let p0 = Module::projective(&a, 0);
expect_witness(is_isomorphic(&p0, &p0).unwrap(), &p0, &p0);
let copy = Module::projective(&a, 0);
expect_witness(is_isomorphic(&p0, ©).unwrap(), &p0, ©);
let s1 = Module::simple(&a, 1);
let (sum, _, _) = direct_sum(&[&p0, &s1]);
let (sum2, _, _) = direct_sum(&[&s1, &p0]);
expect_witness(is_isomorphic(&sum, &sum).unwrap(), &sum, &sum);
expect_witness(is_isomorphic(&sum, &sum2).unwrap(), &sum, &sum2);
}
}
#[test]
fn p0_and_i2_over_a3_are_isomorphic() {
for field in fields() {
let a = linear_an(3, field);
let p0 = Module::projective(&a, 0);
let i2 = Module::injective(&a, 2);
expect_witness(is_isomorphic(&p0, &i2).unwrap(), &p0, &i2);
}
}
#[test]
fn a_conjugated_module_is_isomorphic_to_the_original() {
for field in fields() {
let a = dual_numbers(field);
let x = DenseMat::from_rows(&[
vec![field.zero(), field.one()],
vec![field.zero(), field.zero()],
]);
let m = Module::new(a.clone(), vec![2], vec![x]).unwrap();
let conjugated = DenseMat::from_rows(&[
vec![field.zero(), field.one()],
vec![field.zero(), field.zero()],
]);
let conjugated = {
let t = DenseMat::from_rows(&[
vec![field.one(), field.one()],
vec![field.zero(), field.one()],
]);
let t_inv = t.inverse(&field).unwrap();
t_inv.mul(&conjugated, &field).mul(&t, &field)
};
let n = Module::new(a, vec![2], vec![conjugated]).unwrap();
expect_witness(is_isomorphic(&m, &n).unwrap(), &m, &n);
}
}
#[test]
fn modules_with_different_dimension_vectors_are_distinguished() {
for field in fields() {
let a = linear_an(3, field);
let s0 = Module::simple(&a, 0);
let s1 = Module::simple(&a, 1);
assert_eq!(
is_isomorphic(&s0, &s1).unwrap(),
IsoOutcome::NotIsomorphic(Obstruction::DimensionVector {
source: vec![1, 0, 0],
target: vec![0, 1, 0],
})
);
}
}
#[test]
fn nonisomorphic_kronecker_modules_hit_the_radical_criterion() {
for field in fields() {
let a = kronecker(2, field);
let m = Module::new(
a.clone(),
vec![1, 1],
vec![
DenseMat::from_rows(&[vec![field.one()]]),
DenseMat::from_rows(&[vec![field.zero()]]),
],
)
.unwrap();
let n = Module::new(
a,
vec![1, 1],
vec![
DenseMat::from_rows(&[vec![field.zero()]]),
DenseMat::from_rows(&[vec![field.one()]]),
],
)
.unwrap();
assert_eq!(
is_isomorphic(&m, &n).unwrap(),
IsoOutcome::NotIsomorphic(Obstruction::RadicalCriterion)
);
expect_witness(is_isomorphic(&m, &m).unwrap(), &m, &m);
}
}
#[test]
fn an_indecomposable_and_a_semisimple_sum_differ_by_loewy_series() {
for field in fields() {
let a = linear_an(2, field);
let p0 = Module::projective(&a, 0);
let s0 = Module::simple(&a, 0);
let s1 = Module::simple(&a, 1);
let (sum, _, _) = direct_sum(&[&s0, &s1]);
assert_eq!(
is_isomorphic(&p0, &sum).unwrap(),
IsoOutcome::NotIsomorphic(Obstruction::LoewySeries {
source: vec![vec![0, 1]],
target: vec![],
})
);
assert_eq!(
is_isomorphic(&sum, &p0).unwrap(),
IsoOutcome::NotIsomorphic(Obstruction::LoewySeries {
source: vec![],
target: vec![vec![0, 1]],
})
);
}
}
fn kronecker_regular(
a: &std::sync::Arc<crate::algebra::Algebra>,
field: PrimeField,
lambda: i64,
) -> Module {
Module::new(
a.clone(),
vec![1, 1],
vec![
DenseMat::from_rows(&[vec![field.one()]]),
DenseMat::from_rows(&[vec![field.elem(lambda)]]),
],
)
.unwrap()
}
#[test]
fn endomorphism_dimension_asymmetry_is_a_typed_obstruction() {
for field in fields() {
let a = kronecker(2, field);
let m = kronecker_regular(&a, field, 0);
let n = kronecker_regular(&a, field, 1);
let (mm, _, _) = direct_sum(&[&m, &m]);
let (nm, _, _) = direct_sum(&[&n, &m]);
assert_eq!(
is_isomorphic(&mm, &nm).unwrap(),
IsoOutcome::NotIsomorphic(Obstruction::HomDimension {
end_source: 4,
end_target: 2,
forward: 2,
backward: 2,
})
);
}
}
#[test]
fn hom_symmetric_sums_are_distinguished_by_summand_matching() {
for field in fields() {
let a = kronecker(2, field);
let m0 = kronecker_regular(&a, field, 0);
let m1 = kronecker_regular(&a, field, 1);
let minf = Module::new(
a.clone(),
vec![1, 1],
vec![
DenseMat::from_rows(&[vec![field.zero()]]),
DenseMat::from_rows(&[vec![field.one()]]),
],
)
.unwrap();
let (sum_a, _, _) = direct_sum(&[&m0, &m1]);
let (sum_b, _, _) = direct_sum(&[&m0, &minf]);
assert_eq!(
is_isomorphic(&sum_a, &sum_b).unwrap(),
IsoOutcome::NotIsomorphic(Obstruction::UnmatchedSummand {
dim_vector: vec![1, 1],
})
);
}
}
#[test]
fn zero_modules_are_isomorphic() {
let field = PrimeField::new(5).unwrap();
let a = linear_an(3, field);
let z1 = Module::zero(&a);
let z2 = Module::zero(&a);
expect_witness(is_isomorphic(&z1, &z2).unwrap(), &z1, &z2);
}
#[test]
fn the_radical_criterion_declines_modules_over_separately_built_algebras() {
let field = PrimeField::new(5).unwrap();
let a = linear_an(3, field);
let b = linear_an(3, field);
let m = Module::simple(&a, 0);
let n = Module::simple(&b, 0);
assert_eq!(m.dim_vector(), n.dim_vector());
let endo = EndoAlgebra::new(&m);
assert!(indecomposable_iso(&m, &n, &endo).is_none());
assert!(indecomposable_iso(&m, &m, &endo).is_some());
}
#[test]
fn the_criterion_declines_a_decomposable_module_of_the_same_dimension_vector() {
for field in fields() {
let a = kronecker(2, field);
let m = Module::new(
a.clone(),
vec![1, 1],
vec![
DenseMat::from_rows(&[vec![field.one()]]),
DenseMat::from_rows(&[vec![field.zero()]]),
],
)
.unwrap();
let (semisimple, _, _) = direct_sum(&[&Module::simple(&a, 0), &Module::simple(&a, 1)]);
assert_eq!(m.dim_vector(), semisimple.dim_vector());
let endo = EndoAlgebra::new(&m);
assert!(indecomposable_iso(&m, &semisimple, &endo).is_none());
}
}
#[test]
fn mismatched_algebras_and_fields_are_rejected() {
let field = PrimeField::new(5).unwrap();
let a = linear_an(3, field);
let b = linear_an(3, field);
let m = Module::simple(&a, 0);
let n = Module::simple(&b, 0);
assert_eq!(
is_isomorphic(&m, &n).unwrap_err(),
HomError::DifferentAlgebras
);
let over_f7 = linear_an(3, PrimeField::new(7).unwrap());
let other = Module::simple(&over_f7, 0);
assert_eq!(
is_isomorphic(&m, &other).unwrap_err(),
HomError::DifferentAlgebras
);
}
}