use std::fmt;
use std::sync::Arc;
use crate::algebra::Algebra;
use crate::arquiver::IndecomposableCatalog;
use crate::decompose::{
Certificate, KrullSchmidtOutcome, decompose, krull_schmidt, matrix_inverse,
};
use crate::endo::EndoAlgebra;
use crate::hom::{HomError, Morphism, hom_dim, identity};
use crate::indec::{IndecError, IndecomposableModule};
use crate::iso::indecomposable_iso;
use crate::module::{Module, direct_sum};
use crate::radical::{loewy_length, socle, top};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum BasicError {
CertificationBlocked {
reason: String,
},
NotBasic {
first: usize,
second: usize,
},
VertexOutOfRange {
vertex: u32,
num_vertices: u32,
},
DifferentAlgebras,
Hom(HomError),
Defect {
reason: String,
},
}
impl fmt::Display for BasicError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::CertificationBlocked { reason } => {
write!(f, "certification blocked: {reason}")
}
Self::NotBasic { first, second } => write!(
f,
"summands {first} and {second} are isomorphic, so the module is not basic"
),
Self::VertexOutOfRange {
vertex,
num_vertices,
} => write!(
f,
"vertex {vertex} is out of range, the quiver has {num_vertices} vertices"
),
Self::DifferentAlgebras => f.write_str("the inputs do not share one algebra"),
Self::Hom(error) => write!(f, "morphism rejected: {error}"),
Self::Defect { reason } => write!(f, "internal cross-check failed: {reason}"),
}
}
}
impl std::error::Error for BasicError {}
impl From<HomError> for BasicError {
fn from(error: HomError) -> BasicError {
BasicError::Hom(error)
}
}
fn certified(endo: EndoAlgebra) -> Result<IndecomposableModule, BasicError> {
IndecomposableModule::from_endo(endo).map_err(|error| match error {
IndecError::Undetermined { attempts } => BasicError::CertificationBlocked {
reason: format!("a summand stayed undetermined after {attempts} split attempts"),
},
other => BasicError::Defect {
reason: format!("a certified summand failed the indecomposability gate: {other}"),
},
})
}
fn inverse_of(f: &Morphism) -> Option<Morphism> {
let field = f.source().field();
let mut maps = Vec::new();
for v in 0..f.source().algebra().quiver().num_vertices() {
maps.push(matrix_inverse(f.map_at(v), &field)?);
}
Morphism::new(f.target(), f.source(), maps).ok()
}
fn defect_non_invertible() -> BasicError {
BasicError::Defect {
reason: "the radical criterion returned a non-invertible map between certified \
indecomposables"
.to_string(),
}
}
#[derive(Clone)]
pub struct BasicDecomposition {
module: Module,
summands: Vec<IndecomposableModule>,
}
fn assemble(algebra: &Arc<Algebra>, summands: &[IndecomposableModule]) -> Module {
let parts: Vec<&Module> = summands.iter().map(|s| s.module()).collect();
if parts.is_empty() {
Module::zero(algebra)
} else {
direct_sum(&parts).0
}
}
impl fmt::Debug for BasicDecomposition {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("BasicDecomposition")
.field("dim_vector", &self.module.dim_vector())
.field("summand_dim_vectors", &self.dim_vectors())
.finish()
}
}
impl BasicDecomposition {
pub fn new(m: &Module) -> Result<BasicDecomposition, BasicError> {
let classes = match krull_schmidt(m) {
KrullSchmidtOutcome::Classes(classes) => classes,
KrullSchmidtOutcome::Unknown { reason } => {
return Err(BasicError::CertificationBlocked { reason });
}
};
let mut summands = Vec::with_capacity(classes.len());
for class in &classes {
if class.multiplicity > 1 {
return Err(BasicError::NotBasic {
first: summands.len(),
second: summands.len() + 1,
});
}
summands.push(certified(class.endo.clone())?);
}
Ok(BasicDecomposition {
module: m.clone(),
summands,
})
}
pub fn without(&self, slot: usize) -> Option<BasicDecomposition> {
if slot >= self.summands.len() {
return None;
}
let summands: Vec<IndecomposableModule> = self
.summands
.iter()
.enumerate()
.filter(|(i, _)| *i != slot)
.map(|(_, x)| x.clone())
.collect();
Some(BasicDecomposition {
module: assemble(self.module.algebra(), &summands),
summands,
})
}
pub fn with_new_summand(
&self,
summand: &IndecomposableModule,
) -> Result<BasicDecomposition, BasicError> {
if !Arc::ptr_eq(self.module.algebra(), summand.module().algebra()) {
return Err(BasicError::DifferentAlgebras);
}
for (first, x) in self.summands.iter().enumerate() {
if indecomposable_iso(summand.module(), x.module(), summand.endo()).is_some() {
return Err(BasicError::NotBasic {
first,
second: self.summands.len(),
});
}
}
let mut summands = self.summands.clone();
summands.push(summand.clone());
Ok(BasicDecomposition {
module: assemble(self.module.algebra(), &summands),
summands,
})
}
pub fn from_catalog(
catalog: &IndecomposableCatalog,
chosen: &[usize],
) -> Result<BasicDecomposition, BasicError> {
for (second, &i) in chosen.iter().enumerate() {
assert!(
i < catalog.len(),
"from_catalog: entry {i} is not one of the {} catalog positions",
catalog.len()
);
if let Some(first) = chosen[..second].iter().position(|&j| j == i) {
return Err(BasicError::NotBasic { first, second });
}
}
let summands: Vec<IndecomposableModule> = chosen
.iter()
.map(|&i| (*catalog.entries()[i]).clone())
.collect();
Ok(BasicDecomposition {
module: assemble(catalog.algebra(), &summands),
summands,
})
}
#[inline]
pub fn module(&self) -> &Module {
&self.module
}
#[inline]
pub fn summands(&self) -> &[IndecomposableModule] {
&self.summands
}
#[inline]
pub fn len(&self) -> usize {
self.summands.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.summands.is_empty()
}
pub fn dim_vectors(&self) -> Vec<Vec<usize>> {
let mut out: Vec<Vec<usize>> = self
.summands
.iter()
.map(|s| s.module().dim_vector().to_vec())
.collect();
out.sort();
out
}
}
pub struct ProjectiveSupport {
algebra: Arc<Algebra>,
vertices: Vec<u32>,
}
impl fmt::Debug for ProjectiveSupport {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("ProjectiveSupport")
.field("vertices", &self.vertices)
.finish()
}
}
impl PartialEq for ProjectiveSupport {
fn eq(&self, other: &ProjectiveSupport) -> bool {
self.vertices == other.vertices
}
}
impl Eq for ProjectiveSupport {}
impl ProjectiveSupport {
pub fn new(algebra: &Arc<Algebra>, vertices: &[u32]) -> Result<ProjectiveSupport, BasicError> {
let num_vertices = algebra.quiver().num_vertices();
for &vertex in vertices {
if vertex >= num_vertices {
return Err(BasicError::VertexOutOfRange {
vertex,
num_vertices,
});
}
}
let mut sorted = vertices.to_vec();
sorted.sort_unstable();
sorted.dedup();
Ok(ProjectiveSupport {
algebra: algebra.clone(),
vertices: sorted,
})
}
#[inline]
pub fn algebra(&self) -> &Arc<Algebra> {
&self.algebra
}
#[inline]
pub fn vertices(&self) -> &[u32] {
&self.vertices
}
#[inline]
pub fn len(&self) -> usize {
self.vertices.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.vertices.is_empty()
}
pub fn contains(&self, v: u32) -> bool {
self.vertices.binary_search(&v).is_ok()
}
pub fn is_compatible(&self, other: &ProjectiveSupport) -> bool {
Arc::ptr_eq(&self.algebra, &other.algebra)
}
pub fn module(&self) -> Module {
if self.vertices.is_empty() {
return Module::zero(&self.algebra);
}
let parts: Vec<Module> = self
.vertices
.iter()
.map(|&v| Module::projective(&self.algebra, v))
.collect();
let refs: Vec<&Module> = parts.iter().collect();
let (sum, _, _) = direct_sum(&refs);
sum
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum SupportPairObstruction {
ProjectiveSupport {
first: Vec<u32>,
second: Vec<u32>,
},
SummandCount {
first: usize,
second: usize,
},
UnmatchedSummand {
index: usize,
dim_vector: Vec<usize>,
},
}
#[derive(Clone)]
pub struct SupportPairIsoWitness {
bijection: Vec<usize>,
forward: Vec<Morphism>,
backward: Vec<Morphism>,
}
impl fmt::Debug for SupportPairIsoWitness {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("SupportPairIsoWitness")
.field("bijection", &self.bijection)
.finish()
}
}
impl SupportPairIsoWitness {
#[inline]
pub fn bijection(&self) -> &[usize] {
&self.bijection
}
#[inline]
pub fn forward(&self) -> &[Morphism] {
&self.forward
}
#[inline]
pub fn backward(&self) -> &[Morphism] {
&self.backward
}
pub fn verify(&self) -> bool {
if self.forward.len() != self.bijection.len() || self.backward.len() != self.bijection.len()
{
return false;
}
let mut seen = vec![false; self.bijection.len()];
for &j in &self.bijection {
if j >= seen.len() || seen[j] {
return false;
}
seen[j] = true;
}
for (f, g) in self.forward.iter().zip(&self.backward) {
let (Ok(round), Ok(round_back)) = (f.then(g), g.then(f)) else {
return false;
};
if round != identity(f.source()) || round_back != identity(g.source()) {
return false;
}
}
true
}
}
#[derive(Clone, Debug)]
pub enum SupportPairIsoOutcome {
Isomorphic(SupportPairIsoWitness),
NotIsomorphic(SupportPairObstruction),
}
pub fn pair_iso(
a_mod: &BasicDecomposition,
a_proj: &ProjectiveSupport,
b_mod: &BasicDecomposition,
b_proj: &ProjectiveSupport,
) -> Result<SupportPairIsoOutcome, BasicError> {
if !a_proj.is_compatible(b_proj)
|| !Arc::ptr_eq(a_mod.module().algebra(), a_proj.algebra())
|| !Arc::ptr_eq(b_mod.module().algebra(), b_proj.algebra())
{
return Err(BasicError::DifferentAlgebras);
}
if a_proj.vertices() != b_proj.vertices() {
return Ok(SupportPairIsoOutcome::NotIsomorphic(
SupportPairObstruction::ProjectiveSupport {
first: a_proj.vertices().to_vec(),
second: b_proj.vertices().to_vec(),
},
));
}
if a_mod.len() != b_mod.len() {
return Ok(SupportPairIsoOutcome::NotIsomorphic(
SupportPairObstruction::SummandCount {
first: a_mod.len(),
second: b_mod.len(),
},
));
}
let mut bijection = Vec::with_capacity(a_mod.len());
let mut forward = Vec::with_capacity(a_mod.len());
let mut backward = Vec::with_capacity(a_mod.len());
let mut used = vec![false; b_mod.len()];
for (i, x) in a_mod.summands().iter().enumerate() {
let mut matched = None;
for (j, y) in b_mod.summands().iter().enumerate() {
if used[j] {
continue;
}
if let Some(f) = indecomposable_iso(x.module(), y.module(), x.endo()) {
matched = Some((j, f));
break;
}
}
let Some((j, f)) = matched else {
return Ok(SupportPairIsoOutcome::NotIsomorphic(
SupportPairObstruction::UnmatchedSummand {
index: i,
dim_vector: x.module().dim_vector().to_vec(),
},
));
};
let Some(g) = inverse_of(&f) else {
return Err(defect_non_invertible());
};
used[j] = true;
bijection.push(j);
forward.push(f);
backward.push(g);
}
Ok(SupportPairIsoOutcome::Isomorphic(SupportPairIsoWitness {
bijection,
forward,
backward,
}))
}
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SummandFingerprint {
dim_vector: Vec<usize>,
loewy_length: usize,
top_dim_vector: Vec<usize>,
socle_dim_vector: Vec<usize>,
end_dim: usize,
residue_degree: usize,
hom_from_simples: Vec<usize>,
hom_to_simples: Vec<usize>,
}
impl SummandFingerprint {
#[inline]
pub fn dim_vector(&self) -> &[usize] {
&self.dim_vector
}
#[inline]
pub fn loewy_length(&self) -> usize {
self.loewy_length
}
#[inline]
pub fn top_dim_vector(&self) -> &[usize] {
&self.top_dim_vector
}
#[inline]
pub fn socle_dim_vector(&self) -> &[usize] {
&self.socle_dim_vector
}
#[inline]
pub fn end_dim(&self) -> usize {
self.end_dim
}
#[inline]
pub fn residue_degree(&self) -> usize {
self.residue_degree
}
#[inline]
pub fn hom_from_simples(&self) -> &[usize] {
&self.hom_from_simples
}
#[inline]
pub fn hom_to_simples(&self) -> &[usize] {
&self.hom_to_simples
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct PairFingerprint {
projective_support: Vec<u32>,
summands: Vec<SummandFingerprint>,
}
impl PairFingerprint {
pub fn new(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
) -> Result<PairFingerprint, BasicError> {
let algebra = module.module().algebra();
if !Arc::ptr_eq(algebra, projective.algebra()) {
return Err(BasicError::DifferentAlgebras);
}
let simples: Vec<Module> = (0..algebra.quiver().num_vertices())
.map(|v| Module::simple(algebra, v))
.collect();
let mut summands = Vec::with_capacity(module.len());
for x in module.summands() {
let m = x.module();
let (top_module, _) = top(m);
let (socle_module, _) = socle(m);
let mut hom_from_simples = Vec::with_capacity(simples.len());
let mut hom_to_simples = Vec::with_capacity(simples.len());
for simple in &simples {
hom_from_simples.push(hom_dim(simple, m)?);
hom_to_simples.push(hom_dim(m, simple)?);
}
summands.push(SummandFingerprint {
dim_vector: m.dim_vector().to_vec(),
loewy_length: loewy_length(m),
top_dim_vector: top_module.dim_vector().to_vec(),
socle_dim_vector: socle_module.dim_vector().to_vec(),
end_dim: x.endo().dim(),
residue_degree: x.residue_degree(),
hom_from_simples,
hom_to_simples,
});
}
summands.sort();
Ok(PairFingerprint {
projective_support: projective.vertices().to_vec(),
summands,
})
}
#[inline]
pub fn projective_support(&self) -> &[u32] {
&self.projective_support
}
#[inline]
pub fn summands(&self) -> &[SummandFingerprint] {
&self.summands
}
}
#[derive(Clone)]
pub struct AddMatch {
target_index: usize,
forward: Morphism,
backward: Morphism,
}
impl fmt::Debug for AddMatch {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("AddMatch")
.field("target_index", &self.target_index)
.finish()
}
}
impl AddMatch {
#[inline]
pub fn target_index(&self) -> usize {
self.target_index
}
#[inline]
pub fn forward(&self) -> &Morphism {
&self.forward
}
#[inline]
pub fn backward(&self) -> &Morphism {
&self.backward
}
}
#[derive(Clone)]
pub struct AddClosureWitness {
module: Module,
summands: Vec<Module>,
target: Module,
target_summands: Vec<Module>,
matches: Vec<AddMatch>,
}
impl fmt::Debug for AddClosureWitness {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("AddClosureWitness")
.field("dim_vector", &self.module.dim_vector())
.field("target_dim_vector", &self.target.dim_vector())
.field("matches", &self.matches.len())
.finish()
}
}
fn match_summands(
summands: &[IndecomposableModule],
t: &BasicDecomposition,
) -> Result<Option<Vec<AddMatch>>, BasicError> {
let mut matches = Vec::with_capacity(summands.len());
for x in summands {
let mut matched = None;
for (j, y) in t.summands().iter().enumerate() {
if let Some(f) = indecomposable_iso(x.module(), y.module(), x.endo()) {
matched = Some((j, f));
break;
}
}
let Some((target_index, forward)) = matched else {
return Ok(None);
};
let Some(backward) = inverse_of(&forward) else {
return Err(defect_non_invertible());
};
matches.push(AddMatch {
target_index,
forward,
backward,
});
}
Ok(Some(matches))
}
fn target_summand_modules(t: &BasicDecomposition) -> Vec<Module> {
t.summands().iter().map(|y| y.module().clone()).collect()
}
impl AddClosureWitness {
pub fn new(
m: &BasicDecomposition,
t: &BasicDecomposition,
) -> Result<Option<AddClosureWitness>, BasicError> {
if !Arc::ptr_eq(m.module().algebra(), t.module().algebra()) {
return Err(BasicError::DifferentAlgebras);
}
let Some(matches) = match_summands(m.summands(), t)? else {
return Ok(None);
};
Ok(Some(AddClosureWitness {
module: m.module().clone(),
summands: m
.summands()
.iter()
.map(|x| x.module().clone())
.collect::<Vec<Module>>(),
target: t.module().clone(),
target_summands: target_summand_modules(t),
matches,
}))
}
pub fn from_module(
m: &Module,
t: &BasicDecomposition,
) -> Result<Option<AddClosureWitness>, BasicError> {
if !Arc::ptr_eq(m.algebra(), t.module().algebra()) {
return Err(BasicError::DifferentAlgebras);
}
let decomposition = decompose(m);
for certificate in decomposition.certificates() {
if let Certificate::Undetermined { attempts } = certificate {
return Err(BasicError::CertificationBlocked {
reason: format!(
"a summand stayed undetermined after {attempts} split attempts"
),
});
}
}
let mut summands = Vec::with_capacity(decomposition.summands().len());
for endo in decomposition.endos() {
summands.push(certified(endo.clone())?);
}
let Some(matches) = match_summands(&summands, t)? else {
return Ok(None);
};
Ok(Some(AddClosureWitness {
module: m.clone(),
summands: summands
.iter()
.map(|x| x.module().clone())
.collect::<Vec<Module>>(),
target: t.module().clone(),
target_summands: target_summand_modules(t),
matches,
}))
}
#[inline]
pub fn module(&self) -> &Module {
&self.module
}
#[inline]
pub fn summands(&self) -> &[Module] {
&self.summands
}
#[inline]
pub fn target(&self) -> &Module {
&self.target
}
#[inline]
pub fn target_summands(&self) -> &[Module] {
&self.target_summands
}
#[inline]
pub fn matches(&self) -> &[AddMatch] {
&self.matches
}
pub fn verify(&self) -> bool {
if self.matches.len() != self.summands.len() {
return false;
}
for (x, entry) in self.summands.iter().zip(&self.matches) {
let Some(y) = self.target_summands.get(entry.target_index) else {
return false;
};
if !entry.forward.source().ptr_eq(x)
|| !entry.forward.target().ptr_eq(y)
|| !entry.backward.source().ptr_eq(y)
|| !entry.backward.target().ptr_eq(x)
{
return false;
}
let (Ok(round), Ok(round_back)) = (
entry.forward.then(&entry.backward),
entry.backward.then(&entry.forward),
) else {
return false;
};
if round != identity(x) || round_back != identity(y) {
return false;
}
}
true
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{commutative_square, kronecker, linear_an, truncated_poly};
use crate::arquiver::IndecomposableCatalog;
use crate::dynkin::{DynkinType, dynkin_quiver};
use crate::field::PrimeField;
use crate::linalg::DenseMat;
use crate::quiver::{ArrowId, Quiver};
use crate::supporttau::enumerate_over_catalog;
fn f2() -> PrimeField {
PrimeField::new(2).unwrap()
}
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn fields() -> [PrimeField; 2] {
[f2(), f5()]
}
fn path_algebra(quiver: Quiver, field: PrimeField) -> Arc<Algebra> {
crate::algebra::path_algebra(quiver, field)
.expect("the zero ideal over an acyclic quiver completes")
}
fn d4(field: PrimeField) -> Arc<Algebra> {
path_algebra(
dynkin_quiver(DynkinType::D(4)).expect("D_4 has a quiver"),
field,
)
}
fn basic(m: &Module) -> BasicDecomposition {
BasicDecomposition::new(m).expect("the fixture module is basic")
}
fn support(algebra: &Arc<Algebra>, vertices: &[u32]) -> ProjectiveSupport {
ProjectiveSupport::new(algebra, vertices).expect("the fixture vertices are in range")
}
fn sum(parts: &[&Module]) -> Module {
let (total, _, _) = direct_sum(parts);
total
}
fn expect_witness(outcome: SupportPairIsoOutcome) -> SupportPairIsoWitness {
match outcome {
SupportPairIsoOutcome::Isomorphic(witness) => witness,
SupportPairIsoOutcome::NotIsomorphic(obstruction) => {
panic!("expected an isomorphism, got {obstruction:?}")
}
}
}
fn expect_obstruction(outcome: SupportPairIsoOutcome) -> SupportPairObstruction {
match outcome {
SupportPairIsoOutcome::NotIsomorphic(obstruction) => obstruction,
SupportPairIsoOutcome::Isomorphic(witness) => {
panic!("expected an obstruction, got {witness:?}")
}
}
}
#[test]
fn without_keeps_the_stored_summand_values() {
for field in fields() {
let algebra = linear_an(3, field);
let parts: Vec<Module> = (0..3).map(|v| Module::projective(&algebra, v)).collect();
let refs: Vec<&Module> = parts.iter().collect();
let whole = basic(&sum(&refs));
assert!(whole.without(3).is_none(), "there is no slot 3");
for slot in 0..3 {
let kept = whole.without(slot).expect("the slot is a summand");
assert_eq!(kept.len(), 2);
let mut expected: Vec<&IndecomposableModule> = Vec::new();
for (i, x) in whole.summands().iter().enumerate() {
if i != slot {
expected.push(x);
}
}
for (a, b) in kept.summands().iter().zip(expected) {
assert!(a.module().ptr_eq(b.module()));
}
assert_eq!(
kept.module().dim_vector(),
BasicDecomposition::new(kept.module())
.expect("a sum of two projectives is basic")
.module()
.dim_vector()
);
}
}
}
#[test]
fn with_new_summand_appends_and_rejects_a_repeat() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let one = basic(&p0);
let other = IndecomposableModule::new(&p1).expect("P_1 is indecomposable");
let two = one
.with_new_summand(&other)
.expect("P_0 and P_1 are not isomorphic");
assert_eq!(two.len(), 2);
assert!(two.summands()[0].module().ptr_eq(&p0));
assert!(two.summands()[1].module().ptr_eq(&p1));
assert_eq!(two.module().dim_vector(), sum(&[&p0, &p1]).dim_vector());
let repeat = IndecomposableModule::new(&Module::projective(&algebra, 0))
.expect("P_0 is indecomposable");
assert_eq!(
two.with_new_summand(&repeat).err(),
Some(BasicError::NotBasic {
first: 0,
second: 2
})
);
let elsewhere = linear_an(3, field);
let outside = IndecomposableModule::new(&Module::simple(&elsewhere, 0))
.expect("a simple is indecomposable");
assert_eq!(
two.with_new_summand(&outside).err(),
Some(BasicError::DifferentAlgebras)
);
}
}
#[test]
fn from_catalog_agrees_with_the_general_constructor() {
for field in fields() {
let algebra = d4(field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("D_4 is Dynkin");
for chosen in [vec![], vec![0], vec![2, 5], vec![1, 3, 7]] {
let from_catalog = BasicDecomposition::from_catalog(&catalog, &chosen)
.expect("distinct catalog entries are pairwise non-isomorphic");
assert_eq!(from_catalog.len(), chosen.len());
for (x, &i) in from_catalog.summands().iter().zip(&chosen) {
assert!(x.module().ptr_eq(catalog.entries()[i].module()));
}
let parts: Vec<&Module> = chosen
.iter()
.map(|&i| catalog.entries()[i].module())
.collect();
let assembled = if parts.is_empty() {
Module::zero(&algebra)
} else {
sum(&parts)
};
let general = basic(&assembled);
assert_eq!(general.dim_vectors(), from_catalog.dim_vectors());
assert_eq!(
general.module().dim_vector(),
from_catalog.module().dim_vector()
);
}
assert_eq!(
BasicDecomposition::from_catalog(&catalog, &[4, 4]).err(),
Some(BasicError::NotBasic {
first: 0,
second: 1
})
);
}
}
fn kronecker_line(algebra: &Arc<Algebra>, field: PrimeField, a: i64, b: i64) -> Module {
Module::new(
algebra.clone(),
vec![1, 1],
vec![
DenseMat::from_rows(&[vec![field.elem(a)]]),
DenseMat::from_rows(&[vec![field.elem(b)]]),
],
)
.expect("a Kronecker representation is a module")
}
#[test]
fn each_projective_gives_one_summand() {
for field in fields() {
for algebra in [
linear_an(3, field),
d4(field),
truncated_poly(3, field).unwrap(),
commutative_square(field),
kronecker(2, field),
] {
for v in 0..algebra.quiver().num_vertices() {
let p = Module::projective(&algebra, v);
let decomposition = basic(&p);
assert_eq!(decomposition.len(), 1, "P_{v} over F_{}", field.modulus());
assert!(!decomposition.is_empty());
assert!(decomposition.module().ptr_eq(&p));
assert_eq!(decomposition.dim_vectors(), vec![p.dim_vector().to_vec()]);
}
}
}
}
#[test]
fn the_sum_of_the_a3_projectives_is_basic() {
for field in fields() {
let algebra = linear_an(3, field);
let parts: Vec<Module> = (0..3).map(|v| Module::projective(&algebra, v)).collect();
let total = sum(&[&parts[0], &parts[1], &parts[2]]);
let decomposition = basic(&total);
assert_eq!(decomposition.len(), 3);
assert_eq!(
decomposition.dim_vectors(),
vec![vec![0, 0, 1], vec![0, 1, 1], vec![1, 1, 1]],
"over F_{}",
field.modulus()
);
}
}
#[test]
fn the_sum_of_the_d4_projectives_is_basic() {
for field in fields() {
let algebra = d4(field);
let parts: Vec<Module> = (0..4).map(|v| Module::projective(&algebra, v)).collect();
let total = sum(&[&parts[0], &parts[1], &parts[2], &parts[3]]);
let decomposition = basic(&total);
assert_eq!(decomposition.len(), 4);
assert_eq!(
decomposition.dim_vectors(),
vec![
vec![0, 0, 0, 1],
vec![0, 0, 1, 0],
vec![0, 1, 0, 0],
vec![1, 1, 1, 1],
],
"over F_{}",
field.modulus()
);
}
}
#[test]
fn truncated_poly_three_gives_summands_of_dimension_one_and_three() {
for field in fields() {
let algebra = truncated_poly(3, field).unwrap();
let regular = Module::projective(&algebra, 0);
let simple = Module::simple(&algebra, 0);
let decomposition = basic(&sum(&[®ular, &simple]));
assert_eq!(decomposition.len(), 2);
assert_eq!(
decomposition.dim_vectors(),
vec![vec![1], vec![3]],
"over F_{}",
field.modulus()
);
}
}
#[test]
fn the_commutative_square_projectives_have_the_expected_dim_vectors() {
for field in fields() {
let algebra = commutative_square(field);
let expected = [
vec![1, 1, 1, 1],
vec![0, 1, 0, 1],
vec![0, 0, 1, 1],
vec![0, 0, 0, 1],
];
for (v, want) in expected.iter().enumerate() {
let p = Module::projective(&algebra, v as u32);
assert_eq!(basic(&p).dim_vectors(), vec![want.clone()]);
}
}
}
#[test]
fn the_zero_module_has_no_summands() {
for field in fields() {
let algebra = linear_an(3, field);
let zero = Module::zero(&algebra);
let decomposition = basic(&zero);
assert_eq!(decomposition.len(), 0);
assert!(decomposition.is_empty());
assert!(decomposition.dim_vectors().is_empty());
assert!(decomposition.module().ptr_eq(&zero));
}
}
#[test]
fn a_repeated_summand_is_rejected() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let doubled = sum(&[&p0, &p0]);
assert_eq!(
BasicDecomposition::new(&doubled).unwrap_err(),
BasicError::NotBasic {
first: 0,
second: 1
},
"P_0 + P_0 over F_{}",
field.modulus()
);
}
}
#[test]
fn a_repeated_summand_from_a_fresh_copy_is_rejected() {
let algebra = linear_an(3, f5());
let first = Module::projective(&algebra, 1);
let second = Module::projective(&algebra, 1);
assert!(matches!(
BasicDecomposition::new(&sum(&[&first, &second])).unwrap_err(),
BasicError::NotBasic { .. }
));
}
#[test]
fn projective_support_sorts_and_deduplicates() {
let algebra = linear_an(3, f5());
let s = support(&algebra, &[2, 0, 2, 1, 0]);
assert_eq!(s.vertices(), &[0, 1, 2]);
assert_eq!(s.len(), 3);
assert!(!s.is_empty());
assert!(s.contains(0) && s.contains(1) && s.contains(2));
assert!(!s.contains(3));
assert_eq!(support(&algebra, &[]).len(), 0);
assert!(support(&algebra, &[]).is_empty());
}
#[test]
fn an_out_of_range_support_vertex_is_rejected() {
let algebra = linear_an(3, f5());
assert_eq!(
ProjectiveSupport::new(&algebra, &[0, 3]).unwrap_err(),
BasicError::VertexOutOfRange {
vertex: 3,
num_vertices: 3
}
);
}
#[test]
fn the_support_module_is_the_sum_of_its_projectives() {
for field in fields() {
let algebra = linear_an(3, field);
let s = support(&algebra, &[2, 0]);
let module = s.module();
assert_eq!(module.dim_vector(), &[1, 1, 2]);
let decomposition = basic(&module);
assert_eq!(
decomposition.dim_vectors(),
vec![vec![0, 0, 1], vec![1, 1, 1]]
);
assert!(support(&algebra, &[]).module().is_zero());
}
}
#[test]
fn support_equality_is_set_equality_and_compatibility_is_separate() {
let algebra = linear_an(3, f5());
let other = linear_an(3, f5());
assert_eq!(support(&algebra, &[1, 0]), support(&algebra, &[0, 1, 0]));
assert_ne!(support(&algebra, &[1]), support(&algebra, &[2]));
assert_eq!(support(&algebra, &[1]), support(&other, &[1]));
assert!(support(&algebra, &[1]).is_compatible(&support(&algebra, &[2])));
assert!(!support(&algebra, &[1]).is_compatible(&support(&other, &[1])));
}
#[test]
fn a_pair_is_isomorphic_to_a_fresh_copy_of_itself() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let first = basic(&sum(&[&p0, &p2]));
let second = basic(&sum(&[&p0, &p2]));
let s = support(&algebra, &[1]);
let witness = expect_witness(pair_iso(&first, &s, &second, &s).unwrap());
assert!(witness.verify());
assert_eq!(witness.bijection(), &[0, 1], "over F_{}", field.modulus());
assert_eq!(witness.forward().len(), 2);
assert_eq!(witness.backward().len(), 2);
}
}
#[test]
fn the_decomposition_order_is_pinned() {
fn order(d: &BasicDecomposition) -> Vec<Vec<usize>> {
d.summands()
.iter()
.map(|x| x.module().dim_vector().to_vec())
.collect()
}
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let p2 = Module::projective(&algebra, 2);
let context = format!("over F_{}", field.modulus());
assert_eq!(
order(&basic(&sum(&[&p0, &p2]))),
vec![vec![0, 0, 1], vec![1, 1, 1]],
"P_0 + P_2 {context}"
);
assert_eq!(
order(&basic(&sum(&[&p2, &p0]))),
vec![vec![1, 1, 1], vec![0, 0, 1]],
"P_2 + P_0 {context}"
);
assert_eq!(
order(&basic(&sum(&[&p0, &p1, &p2]))),
vec![vec![0, 0, 1], vec![0, 1, 1], vec![1, 1, 1]],
"the regular module {context}"
);
assert_eq!(
order(&basic(&sum(&[&p0, &p2]))),
order(&basic(&sum(&[&p0, &p2]))),
"two calls {context}"
);
}
}
#[test]
fn the_pair_iso_bijection_is_pinned() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let s = support(&algebra, &[1]);
let first = basic(&sum(&[&p0, &p2]));
let same = basic(&sum(&[&p0, &p2]));
let reversed = basic(&sum(&[&p2, &p0]));
assert_eq!(first.summands()[0].module().dim_vector(), &[0, 0, 1]);
assert_eq!(reversed.summands()[0].module().dim_vector(), &[1, 1, 1]);
let witness = expect_witness(pair_iso(&first, &s, &same, &s).unwrap());
assert!(witness.verify());
assert_eq!(witness.bijection(), &[0, 1], "over F_{}", field.modulus());
let swapped = expect_witness(pair_iso(&first, &s, &reversed, &s).unwrap());
assert!(swapped.verify());
assert_eq!(swapped.bijection(), &[1, 0], "over F_{}", field.modulus());
}
}
#[test]
fn a_pair_is_isomorphic_to_its_summands_in_the_other_order() {
let algebra = linear_an(3, f5());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let first = basic(&sum(&[&p0, &p1]));
let second = basic(&sum(&[&p1, &p0]));
let s = support(&algebra, &[2]);
let witness = expect_witness(pair_iso(&first, &s, &second, &s).unwrap());
assert!(witness.verify());
}
#[test]
fn a_different_projective_support_is_an_obstruction() {
for field in fields() {
let algebra = linear_an(3, field);
let module = basic(&Module::projective(&algebra, 0));
let other = basic(&Module::projective(&algebra, 0));
let left = support(&algebra, &[1]);
let right = support(&algebra, &[2]);
assert_eq!(
expect_obstruction(pair_iso(&module, &left, &other, &right).unwrap()),
SupportPairObstruction::ProjectiveSupport {
first: vec![1],
second: vec![2]
}
);
}
}
#[test]
fn a_different_summand_count_is_an_obstruction() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let two = basic(&sum(&[&p0, &p2]));
let one = basic(&p0);
let s = support(&algebra, &[1]);
assert_eq!(
expect_obstruction(pair_iso(&two, &s, &one, &s).unwrap()),
SupportPairObstruction::SummandCount {
first: 2,
second: 1
}
);
}
}
#[test]
fn an_unmatched_summand_is_an_obstruction() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let p2 = Module::projective(&algebra, 2);
let left = basic(&sum(&[&p0, &p2]));
let right = basic(&sum(&[&p0, &p1]));
let s = support(&algebra, &[1]);
let obstruction = expect_obstruction(pair_iso(&left, &s, &right, &s).unwrap());
match obstruction {
SupportPairObstruction::UnmatchedSummand { index, dim_vector } => {
assert_eq!(left.summands()[index].module().dim_vector(), &[0, 0, 1]);
assert_eq!(dim_vector, vec![0, 0, 1]);
}
other => panic!("expected an unmatched summand, got {other:?}"),
}
}
}
#[test]
fn a_tampered_bijection_fails_verification() {
let algebra = linear_an(3, f5());
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let first = basic(&sum(&[&p0, &p2]));
let second = basic(&sum(&[&p0, &p2]));
let s = support(&algebra, &[1]);
let mut witness = expect_witness(pair_iso(&first, &s, &second, &s).unwrap());
assert!(witness.verify());
witness.bijection = vec![0, 0];
assert!(!witness.verify());
let mut short = expect_witness(pair_iso(&first, &s, &second, &s).unwrap());
short.forward.pop();
assert!(!short.verify());
}
#[test]
fn a_tampered_isomorphism_fails_verification() {
let algebra = linear_an(3, f5());
let p0 = Module::projective(&algebra, 0);
let first = basic(&p0);
let second = basic(&Module::projective(&algebra, 0));
let s = support(&algebra, &[1]);
let mut witness = expect_witness(pair_iso(&first, &s, &second, &s).unwrap());
witness.backward = witness.forward.clone();
assert!(!witness.verify());
}
#[test]
fn mismatched_algebras_are_rejected() {
let algebra = linear_an(3, f5());
let other = linear_an(3, f5());
let first = basic(&Module::projective(&algebra, 0));
let second = basic(&Module::projective(&other, 0));
let left = support(&algebra, &[1]);
let right = support(&other, &[1]);
assert_eq!(
pair_iso(&first, &left, &second, &right).unwrap_err(),
BasicError::DifferentAlgebras
);
assert_eq!(
PairFingerprint::new(&first, &right).unwrap_err(),
BasicError::DifferentAlgebras
);
assert_eq!(
AddClosureWitness::new(&first, &second).unwrap_err(),
BasicError::DifferentAlgebras
);
}
#[test]
fn isomorphic_pairs_have_equal_fingerprints() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let first = basic(&sum(&[&p0, &p2]));
let second = basic(&sum(&[&p2, &p0]));
let s = support(&algebra, &[1]);
assert_eq!(
PairFingerprint::new(&first, &s).unwrap(),
PairFingerprint::new(&second, &s).unwrap(),
"over F_{}",
field.modulus()
);
}
}
#[test]
fn fingerprints_separate_obviously_different_pairs() {
let algebra = linear_an(3, f5());
let p0 = basic(&Module::projective(&algebra, 0));
let p1 = basic(&Module::projective(&algebra, 1));
let both = basic(&sum(&[
&Module::projective(&algebra, 0),
&Module::projective(&algebra, 2),
]));
let left = support(&algebra, &[1]);
let right = support(&algebra, &[2]);
let base = PairFingerprint::new(&p0, &left).unwrap();
assert_ne!(base, PairFingerprint::new(&p0, &right).unwrap());
assert_ne!(base, PairFingerprint::new(&p1, &left).unwrap());
assert_ne!(base, PairFingerprint::new(&both, &left).unwrap());
assert_eq!(base.projective_support(), &[1]);
assert_eq!(base.summands().len(), 1);
}
#[test]
fn the_a3_regular_projective_fingerprint_is_hand_checkable() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = basic(&Module::projective(&algebra, 0));
let s = support(&algebra, &[]);
let fingerprint = PairFingerprint::new(&p0, &s).unwrap();
let record = &fingerprint.summands()[0];
assert_eq!(record.dim_vector(), &[1, 1, 1]);
assert_eq!(record.loewy_length(), 3);
assert_eq!(record.top_dim_vector(), &[1, 0, 0]);
assert_eq!(record.socle_dim_vector(), &[0, 0, 1]);
assert_eq!(record.end_dim(), 1);
assert_eq!(record.residue_degree(), 1);
assert_eq!(record.hom_from_simples(), &[0, 0, 1]);
assert_eq!(
record.hom_to_simples(),
&[1, 0, 0],
"over F_{}",
field.modulus()
);
assert!(fingerprint.projective_support().is_empty());
}
}
#[test]
fn the_kronecker_line_modules_collide_in_the_fingerprint() {
let field = f2();
let algebra = kronecker(2, field);
let modules = [
kronecker_line(&algebra, field, 1, 0),
kronecker_line(&algebra, field, 0, 1),
kronecker_line(&algebra, field, 1, 1),
];
let empty = support(&algebra, &[]);
let decompositions: Vec<BasicDecomposition> = modules.iter().map(basic).collect();
for decomposition in &decompositions {
assert_eq!(decomposition.len(), 1);
assert_eq!(decomposition.dim_vectors(), vec![vec![1, 1]]);
}
let fingerprints: Vec<PairFingerprint> = decompositions
.iter()
.map(|d| PairFingerprint::new(d, &empty).unwrap())
.collect();
assert_eq!(fingerprints[0], fingerprints[1]);
assert_eq!(fingerprints[0], fingerprints[2]);
let record = &fingerprints[0].summands()[0];
assert_eq!(record.loewy_length(), 2);
assert_eq!(record.top_dim_vector(), &[1, 0]);
assert_eq!(record.socle_dim_vector(), &[0, 1]);
assert_eq!(record.end_dim(), 1);
assert_eq!(record.hom_from_simples(), &[0, 1]);
assert_eq!(record.hom_to_simples(), &[1, 0]);
for i in 0..3 {
for j in 0..3 {
let outcome =
pair_iso(&decompositions[i], &empty, &decompositions[j], &empty).unwrap();
if i == j {
assert!(expect_witness(outcome).verify());
} else {
assert_eq!(
expect_obstruction(outcome),
SupportPairObstruction::UnmatchedSummand {
index: 0,
dim_vector: vec![1, 1]
},
"the [1, 1] modules {i} and {j} are not isomorphic"
);
}
}
}
}
#[test]
fn a_summand_of_t_lies_in_add_t() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let t = basic(&sum(&[&p0, &p2]));
let m = basic(&Module::projective(&algebra, 2));
let witness = AddClosureWitness::new(&m, &t)
.unwrap()
.expect("P_2 is a summand of T");
assert!(witness.verify());
assert_eq!(witness.matches().len(), 1);
let target = witness.matches()[0].target_index();
assert_eq!(
witness.target_summands()[target].dim_vector(),
&[0, 0, 1],
"over F_{}",
field.modulus()
);
assert_eq!(witness.summands().len(), 1);
assert!(witness.target().ptr_eq(t.module()));
}
}
#[test]
fn a_non_summand_is_outside_add_t() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let t = basic(&sum(&[&p0, &p2]));
let m = basic(&Module::simple(&algebra, 1));
assert!(AddClosureWitness::new(&m, &t).unwrap().is_none());
}
}
#[test]
fn t_plus_t_lies_in_add_t_through_from_module() {
for field in fields() {
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let t_module = sum(&[&p0, &p2]);
let t = basic(&t_module);
let doubled = sum(&[&t_module, &t_module]);
assert!(matches!(
BasicDecomposition::new(&doubled).unwrap_err(),
BasicError::NotBasic { .. }
));
let witness = AddClosureWitness::from_module(&doubled, &t)
.unwrap()
.expect("T + T lies in add(T)");
assert!(witness.verify());
assert_eq!(witness.matches().len(), 4);
let mut hits = [0usize; 2];
for entry in witness.matches() {
hits[entry.target_index()] += 1;
}
assert_eq!(hits, [2, 2], "over F_{}", field.modulus());
assert!(witness.module().ptr_eq(&doubled));
}
}
#[test]
fn the_zero_module_lies_in_add_t() {
let algebra = linear_an(3, f5());
let t = basic(&Module::projective(&algebra, 0));
let zero = Module::zero(&algebra);
let witness = AddClosureWitness::from_module(&zero, &t)
.unwrap()
.expect("the zero module lies in add(T)");
assert!(witness.verify());
assert!(witness.matches().is_empty());
let basic_zero = basic(&zero);
let from_basic = AddClosureWitness::new(&basic_zero, &t)
.unwrap()
.expect("the zero module lies in add(T)");
assert!(from_basic.verify());
}
#[test]
fn a_tampered_add_closure_match_fails_verification() {
let algebra = linear_an(3, f5());
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let t = basic(&sum(&[&p0, &p2]));
let m = basic(&Module::projective(&algebra, 2));
let mut witness = AddClosureWitness::new(&m, &t)
.unwrap()
.expect("P_2 is a summand of T");
assert!(witness.verify());
witness.matches[0].target_index = 1 - witness.matches[0].target_index;
assert!(!witness.verify());
}
#[test]
fn add_closure_holds_over_the_commutative_square() {
for field in fields() {
let algebra = commutative_square(field);
let p0 = Module::projective(&algebra, 0);
let p3 = Module::projective(&algebra, 3);
let t = basic(&sum(&[&p0, &p3]));
let inside = basic(&Module::projective(&algebra, 3));
let outside = basic(&Module::projective(&algebra, 1));
assert!(AddClosureWitness::new(&inside, &t).unwrap().is_some());
assert!(AddClosureWitness::new(&outside, &t).unwrap().is_none());
}
}
#[test]
fn add_closure_holds_over_truncated_poly_three() {
for field in fields() {
let algebra = truncated_poly(3, field).unwrap();
let regular = Module::projective(&algebra, 0);
let t = basic(®ular);
let doubled = sum(&[®ular, ®ular]);
let witness = AddClosureWitness::from_module(&doubled, &t)
.unwrap()
.expect("the regular module doubled lies in add(T)");
assert!(witness.verify());
assert_eq!(witness.matches().len(), 2);
let simple = basic(&Module::simple(&algebra, 0));
assert!(AddClosureWitness::new(&simple, &t).unwrap().is_none());
}
}
#[test]
fn pair_identity_works_over_d4() {
for field in fields() {
let algebra = d4(field);
let p0 = Module::projective(&algebra, 0);
let s1 = Module::simple(&algebra, 1);
let first = basic(&sum(&[&p0, &s1]));
let second = basic(&sum(&[&s1, &p0]));
let left = support(&algebra, &[2, 3]);
let right = support(&algebra, &[3]);
assert_eq!(
expect_obstruction(pair_iso(&first, &left, &second, &right).unwrap()),
SupportPairObstruction::ProjectiveSupport {
first: vec![2, 3],
second: vec![3]
}
);
let witness = expect_witness(pair_iso(&first, &left, &second, &left).unwrap());
assert!(witness.verify());
assert_eq!(
PairFingerprint::new(&first, &left).unwrap(),
PairFingerprint::new(&second, &left).unwrap()
);
}
}
struct XorShift64(u64);
impl XorShift64 {
fn next(&mut self) -> u64 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.0 = x;
x
}
fn below(&mut self, n: u64) -> u64 {
if n == 0 { 0 } else { self.next() % n }
}
}
fn invertible(rng: &mut XorShift64, field: &PrimeField, d: usize) -> DenseMat {
let mut g = DenseMat::identity(d);
if d == 0 {
return g;
}
for _ in 0..2 * d + 2 {
let i = rng.below(d as u64) as usize;
if d == 1 || rng.below(3) == 0 {
let c = field.elem(1 + rng.below(field.modulus() - 1) as i64);
for k in 0..d {
g.set(i, k, field.mul(g.get(i, k), c));
}
continue;
}
let j = (i + 1 + rng.below(d as u64 - 1) as usize) % d;
if rng.below(2) == 0 {
for k in 0..d {
let (a, b) = (g.get(i, k), g.get(j, k));
g.set(i, k, b);
g.set(j, k, a);
}
} else {
let c = field.elem(rng.below(field.modulus()) as i64);
for k in 0..d {
g.set(i, k, field.add(g.get(i, k), field.mul(c, g.get(j, k))));
}
}
}
g
}
fn basis_change(rng: &mut XorShift64, m: &Module) -> Module {
let field = m.field();
let quiver = m.algebra().quiver();
let g: Vec<DenseMat> = m
.dim_vector()
.iter()
.map(|&d| invertible(rng, &field, d))
.collect();
let g_inv: Vec<DenseMat> = g
.iter()
.map(|x| {
x.inverse(&field)
.expect("elementary operations stay invertible")
})
.collect();
let maps: Vec<DenseMat> = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (s, t) = (quiver.source(a) as usize, quiver.target(a) as usize);
g[s].mul(m.map(a), &field).mul(&g_inv[t], &field)
})
.collect();
Module::new(m.algebra().clone(), m.dim_vector().to_vec(), maps)
.expect("a vertexwise basis change preserves the relations")
}
#[test]
fn the_fingerprint_is_constant_on_isomorphism_classes() {
let field = f5();
let algebra = d4(field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("D_4 is Dynkin");
let enumeration = enumerate_over_catalog(&catalog).expect("D_4 enumerates");
assert_eq!(enumeration.len(), 50);
let mut rng = XorShift64(0x5eed_0005_0005_0001);
let mut fingerprints = Vec::with_capacity(enumeration.len());
let mut moved = 0;
for pair in enumeration.pairs() {
let before = PairFingerprint::new(pair.module(), &pair.projective()).unwrap();
let module = pair.module().module();
let rebuilt = basis_change(&mut rng, module);
let decomposition =
BasicDecomposition::new(&rebuilt).expect("a basis change keeps the module basic");
let after = PairFingerprint::new(&decomposition, &pair.projective()).unwrap();
assert_eq!(
before,
after,
"the fingerprint moved under a basis change of {:?}",
pair.module().dim_vectors()
);
let arrows = 0..algebra.quiver().num_arrows();
let same: Vec<bool> = arrows
.map(|i| {
let a = ArrowId(i as u32);
rebuilt.map(a) == module.map(a)
})
.collect();
if same.iter().all(|&s| s) {
for i in 0..algebra.quiver().num_arrows() {
let matrix = module.map(ArrowId(i as u32));
assert!(
matrix.rows() == 0 || matrix.cols() == 0,
"a nonempty arrow matrix survived the basis change in {:?}",
pair.module().dim_vectors()
);
}
} else {
moved += 1;
}
fingerprints.push(before);
}
assert_eq!(moved, 41);
let mut admitted = 0;
for (i, left) in fingerprints.iter().enumerate() {
for (j, right) in fingerprints.iter().enumerate() {
if left == right {
admitted += 1;
assert_eq!(i, j, "pairs {i} and {j} share a fingerprint");
}
}
}
assert_eq!(admitted, 50);
}
#[test]
fn the_fingerprint_separates_on_residue_degree() {
let field = f2();
let algebra = kronecker(2, field);
let mut companion = DenseMat::zero(3, 3);
companion.set(0, 1, field.one());
companion.set(1, 2, field.one());
companion.set(2, 0, field.one());
companion.set(2, 1, field.one());
let w = Module::new(
algebra.clone(),
vec![3, 3],
vec![DenseMat::identity(3), companion],
)
.expect("a Kronecker representation is a module");
let mut jordan = DenseMat::zero(3, 3);
jordan.set(0, 1, field.one());
jordan.set(1, 2, field.one());
let j = Module::new(
algebra.clone(),
vec![3, 3],
vec![DenseMat::identity(3), jordan],
)
.expect("a Kronecker representation is a module");
let empty = support(&algebra, &[]);
let f8 = PairFingerprint::new(&basic(&w), &empty).unwrap();
let f2_residue = PairFingerprint::new(&basic(&j), &empty).unwrap();
let (left, right) = (&f8.summands()[0], &f2_residue.summands()[0]);
assert_eq!(left.residue_degree(), 3);
assert_eq!(right.residue_degree(), 1);
assert_ne!(f8, f2_residue, "residue degree is the separating field");
assert_eq!(left.dim_vector(), right.dim_vector());
assert_eq!(left.dim_vector(), &[3, 3]);
assert_eq!(left.loewy_length(), right.loewy_length());
assert_eq!(left.loewy_length(), 2);
assert_eq!(left.top_dim_vector(), right.top_dim_vector());
assert_eq!(left.top_dim_vector(), &[3, 0]);
assert_eq!(left.socle_dim_vector(), right.socle_dim_vector());
assert_eq!(left.socle_dim_vector(), &[0, 3]);
assert_eq!(left.end_dim(), right.end_dim());
assert_eq!(left.end_dim(), 3);
assert_eq!(left.hom_from_simples(), right.hom_from_simples());
assert_eq!(left.hom_from_simples(), &[0, 3]);
assert_eq!(left.hom_to_simples(), right.hom_to_simples());
assert_eq!(left.hom_to_simples(), &[3, 0]);
}
}