use std::sync::Arc;
use crate::ar::{TauError, tau};
use crate::arquiver::{ArQuiverError, IndecomposableCatalog, category_radical};
use crate::decompose::add_morphisms;
use crate::ext::{ExtClass, ExtClassError, ExtSpace, lift_through};
use crate::field::{Fp, PrimeField};
use crate::hom::{HomError, Morphism, hom, zero_morphism};
use crate::homspace::{
HomQuotient, HomSpace, HomSpaceError, HomSubspace, row_times, scale_morphism,
};
use crate::indec::{IndecError, IndecomposableModule};
use crate::iso::{IsoOutcome, is_isomorphic};
use crate::linalg::DenseMat;
use crate::module::Module;
use crate::resolution::projective_cover;
use crate::sequence::{NonSplitWitness, SequenceError, ShortExactSequence, SplitStatus};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum DefectKind {
DualityDimensionMismatch {
ext_dim: usize,
stable_end_dim: usize,
},
SocleDimensionMismatch {
socle_dim: usize,
residue_degree: usize,
},
ProjectivityDisagreement {
resolution_projective: bool,
tau_zero: bool,
},
NonzeroClassSplit,
RightFactorizationMismatch {
entry: usize,
},
LeftFactorizationMismatch {
entry: usize,
},
}
display_error! { DefectKind {
Self::DualityDimensionMismatch { ext_dim, stable_end_dim } => "Ext^1(M, tau M) has dimension {ext_dim}, stable End(M) has dimension {stable_end_dim}; crate defect";
Self::SocleDimensionMismatch { socle_dim, residue_degree } => "the Ext socle has dimension {socle_dim}, the residue degree is {residue_degree}; crate defect";
Self::ProjectivityDisagreement { resolution_projective, tau_zero } => "the resolution route reports projective = {resolution_projective}, tau reports zero = {tau_zero}; crate defect";
Self::NonzeroClassSplit => "the sequence of a nonzero chosen class splits; crate defect";
Self::RightFactorizationMismatch { entry } => "the image of Hom(X, E) in Hom(X, M) differs from rad(X, M) at catalog entry {entry}; crate defect";
Self::LeftFactorizationMismatch { entry } => "the image of Hom(E, X) in Hom(tau M, X) differs from rad(tau M, X) at catalog entry {entry}; crate defect";
} }
#[derive(Clone, Debug)]
pub enum AlmostSplitError {
Tau(TauError),
TauIndecomposability(IndecError),
Hom(HomError),
Space(HomSpaceError),
Ext(ExtClassError),
Sequence(SequenceError),
Radical(ArQuiverError),
Defect(DefectKind),
}
display_error! { error AlmostSplitError {
Self::Tau(error) => "the AR translate failed: {error}";
Self::TauIndecomposability(error) => "the translate failed the indecomposability gate: {error}";
Self::Hom(error) => "morphism rejected: {error}";
Self::Space(error) => "hom space rejected the input: {error}";
Self::Ext(error) => "Ext class rejected the input: {error}";
Self::Sequence(error) => "short exact sequence rejected: {error}";
Self::Radical(error) => "category radical failed: {error}";
Self::Defect(kind) => "internal cross-check failed: {kind}";
} }
from_variants!(AlmostSplitError {
TauError => Tau,
IndecError => TauIndecomposability,
HomError => Hom,
HomSpaceError => Space,
ExtClassError => Ext,
SequenceError => Sequence,
ArQuiverError => Radical,
});
fn defect(kind: DefectKind) -> AlmostSplitError {
AlmostSplitError::Defect(kind)
}
pub fn projectively_trivial(space: &HomSpace) -> Result<HomSubspace, AlmostSplitError> {
let (cover, pi) = projective_cover(space.target());
let through = hom(space.source(), &cover)?;
let composites: Vec<Morphism> = through
.iter()
.map(|h| h.then(&pi))
.collect::<Result<_, _>>()?;
Ok(space.subspace(&composites)?)
}
pub fn stable_hom(m: &Module, n: &Module) -> Result<HomQuotient, AlmostSplitError> {
let space = HomSpace::new(m, n)?;
let trivial = projectively_trivial(&space)?;
Ok(space.full_subspace().quotient_by(&trivial)?)
}
pub fn stable_end(m: &Module) -> Result<HomQuotient, AlmostSplitError> {
stable_hom(m, m)
}
fn action_matrix(space: &ExtSpace, phi: &Morphism) -> Result<DenseMat, AlmostSplitError> {
let d = space.dim();
if d == 0 {
return Ok(DenseMat::zero(0, 0));
}
let res = space.resolution();
let rhs0 = res.augmentation.then(phi)?;
let phi0 = lift_through(&res.terms[0], &res.augmentation, &rhs0);
let d1 = &res.maps[0];
let rhs1 = d1.then(&phi0)?;
let phi1 = lift_through(&res.terms[1], d1, &rhs1);
let rows: Vec<Vec<Fp>> = space
.representatives()
.iter()
.map(|rep| {
let moved = phi1.then(rep)?;
Ok(space.class_from_cocycle(&moved)?.coordinates().to_vec())
})
.collect::<Result<_, AlmostSplitError>>()?;
Ok(DenseMat::from_rows(&rows))
}
fn action_matrices(
m: &IndecomposableModule,
space: &ExtSpace,
) -> Result<Vec<DenseMat>, AlmostSplitError> {
let endo = m.endo();
let radical = endo.radical_basis();
(0..radical.rows())
.map(|j| action_matrix(space, &endo.morphism(radical.row(j))))
.collect()
}
fn ext_sequence_holds(
m: &IndecomposableModule,
sequence: &ShortExactSequence,
class: &ExtClass,
) -> bool {
let space = class.space();
space.degree() == 1
&& space.source().ptr_eq(m.module())
&& sequence.quotient().ptr_eq(space.source())
&& sequence.sub().ptr_eq(space.target())
&& space.matches_recomputation()
&& ShortExactSequence::new(sequence.inclusion().clone(), sequence.projection().clone())
.is_ok()
&& matches!(sequence.ext1_class(space), Ok(recovered) if recovered.equals(class) == Ok(true))
}
fn socle_kernel(action: &[DenseMat], dim: usize, field: &PrimeField) -> DenseMat {
let mut stacked = DenseMat::zero(dim, dim * action.len());
for (j, a) in action.iter().enumerate() {
for r in 0..dim {
for c in 0..dim {
stacked.set(r, j * dim + c, a.get(r, c));
}
}
}
stacked.left_kernel_basis(field).into_row_space_basis(field)
}
fn subspace_combination(sub: &HomSubspace, coords: &[Fp]) -> Option<Morphism> {
if coords.len() != sub.dim() {
return None;
}
let mut acc = zero_morphism(sub.source(), sub.target())
.expect("a subspace's endpoints share one algebra");
for (k, &c) in coords.iter().enumerate().filter(|(_, c)| !c.is_zero()) {
acc = add_morphisms(&acc, &scale_morphism(&sub.basis_morphism(k), c));
}
Some(acc)
}
#[derive(Clone, Debug)]
#[allow(clippy::large_enum_variant)]
pub enum AlmostSplitOutcome {
Projective,
Sequence(AlmostSplitSequence),
}
#[derive(Clone, Debug)]
pub struct AlmostSplitSequence {
sequence: ShortExactSequence,
class: ExtClass,
witness: AlmostSplitWitness,
}
impl AlmostSplitSequence {
accessor_methods! {
pub sequence() -> &ShortExactSequence = |this| &this.sequence;
pub chosen_ar_class() -> &ExtClass = |this| &this.class;
pub witness() -> &AlmostSplitWitness = |this| &this.witness;
}
pub fn verify(&self, m: &IndecomposableModule) -> bool {
match &self.witness {
AlmostSplitWitness::ArDuality(witness) => {
witness.verify(m, &self.sequence, &self.class)
}
AlmostSplitWitness::ExhaustiveCatalog(_) => false,
}
}
pub fn verify_with_catalog(
&self,
m: &IndecomposableModule,
catalog: &IndecomposableCatalog,
) -> bool {
match &self.witness {
AlmostSplitWitness::ExhaustiveCatalog(witness) => {
witness.verify(m, catalog, &self.sequence, &self.class)
}
AlmostSplitWitness::ArDuality(_) => false,
}
}
}
#[derive(Clone, Debug)]
pub enum AlmostSplitWitness {
ArDuality(ArDualityWitness),
ExhaustiveCatalog(CatalogWitness),
}
#[derive(Clone, Debug)]
pub struct ArDualityWitness {
radical_coords: DenseMat,
action_traces: Vec<Vec<Fp>>,
socle_rref: DenseMat,
chosen_row: usize,
ext_dim: usize,
stable_end_dim: usize,
socle_dim: usize,
residue_degree: usize,
non_split: NonSplitWitness,
}
impl ArDualityWitness {
accessor_methods! {
pub radical_basis_coords() -> &DenseMat = |this| &this.radical_coords;
pub action_traces() -> &[Vec<Fp>] = |this| &this.action_traces;
pub socle_rref() -> &DenseMat = |this| &this.socle_rref;
pub chosen_row() -> usize = |this| this.chosen_row;
pub ext_dim() -> usize = |this| this.ext_dim;
pub stable_end_dim() -> usize = |this| this.stable_end_dim;
pub socle_dim() -> usize = |this| this.socle_dim;
pub residue_degree() -> usize = |this| this.residue_degree;
pub non_split() -> &NonSplitWitness = |this| &this.non_split;
}
pub fn verify(
&self,
m: &IndecomposableModule,
sequence: &ShortExactSequence,
class: &ExtClass,
) -> bool {
let space = class.space();
verify_guard!(ext_sequence_holds(m, sequence, class));
let_or_false!(Ok(translate) = tau(m.module()));
verify_guard!(IndecomposableModule::new(&translate).is_ok());
verify_guard!(matches!(
is_isomorphic(&translate, space.target()),
Ok(IsoOutcome::Isomorphic(_))
));
let field = m.module().field();
verify_guard!(self.radical_coords == *m.endo().radical_basis());
let d = space.dim();
verify_guard!(self.ext_dim == d && self.ext_dim == self.stable_end_dim);
let_or_false!(Ok(stable) = stable_end(m.module()));
verify_guard!(stable.dim() == self.stable_end_dim);
verify_guard!(
self.socle_dim == self.socle_rref.rows()
&& self.residue_degree == m.residue_degree()
&& self.socle_dim == self.residue_degree
);
let_or_false!(Ok(action) = action_matrices(m, space));
verify_guard!(socle_kernel(&action, d, &field) == self.socle_rref);
verify_guard!(!(0..self.socle_rref.rows()).any(|r| {
action.iter().any(|a| {
row_times(self.socle_rref.row(r), a, &field)
.iter()
.any(|v| !v.is_zero())
})
}));
verify_guard!(
self.chosen_row == 0
&& self.socle_rref.rows() > 0
&& class.coordinates() == self.socle_rref.row(0)
&& !class.is_zero()
);
verify_guard!(
self.action_traces.len() == action.len()
&& !self.action_traces.iter().zip(&action).any(|(trace, a)| {
*trace != row_times(class.coordinates(), a, &field)
|| trace.iter().any(|v| !v.is_zero())
})
);
self.non_split.verify(sequence)
}
}
#[derive(Clone, Debug)]
pub struct CatalogEntryCheck {
right_factorizations: Vec<Vec<Fp>>,
right_memberships: Vec<Vec<Fp>>,
left_factorizations: Vec<Vec<Fp>>,
left_memberships: Vec<Vec<Fp>>,
}
impl CatalogEntryCheck {
accessor_methods! {
pub right_factorizations() -> &[Vec<Fp>] = |this| &this.right_factorizations;
pub right_memberships() -> &[Vec<Fp>] = |this| &this.right_memberships;
pub left_factorizations() -> &[Vec<Fp>] = |this| &this.left_factorizations;
pub left_memberships() -> &[Vec<Fp>] = |this| &this.left_memberships;
}
}
#[derive(Clone, Debug)]
pub struct CatalogWitness {
entries: Vec<CatalogEntryCheck>,
}
struct EntryRecompute {
image: HomSubspace,
rad: HomSubspace,
composites: Vec<Morphism>,
left_image: HomSubspace,
left_rad: HomSubspace,
left_composites: Vec<Morphism>,
}
fn radical_maps(radical: &HomSubspace) -> Vec<Morphism> {
(0..radical.dim())
.map(|i| radical.basis_morphism(i))
.collect()
}
fn express(over: &HomSubspace, maps: &[Morphism]) -> Result<Vec<Vec<Fp>>, AlmostSplitError> {
maps.iter()
.map(|map| {
Ok(over.witness_contains(map)?.expect(
"the subspaces were just proved equal, so every map solves; this is a bug in \
auslander",
))
})
.collect()
}
impl EntryRecompute {
fn verifies(&self, check: &CatalogEntryCheck) -> bool {
self.image == self.rad
&& self.left_image == self.left_rad
&& family_solves(
&check.right_factorizations,
&self.image,
&radical_maps(&self.rad),
)
&& family_solves(&check.right_memberships, &self.rad, &self.composites)
&& family_solves(
&check.left_factorizations,
&self.left_image,
&radical_maps(&self.left_rad),
)
&& family_solves(
&check.left_memberships,
&self.left_rad,
&self.left_composites,
)
}
fn into_check(self) -> Result<CatalogEntryCheck, AlmostSplitError> {
Ok(CatalogEntryCheck {
right_factorizations: express(&self.image, &radical_maps(&self.rad))?,
right_memberships: express(&self.rad, &self.composites)?,
left_factorizations: express(&self.left_image, &radical_maps(&self.left_rad))?,
left_memberships: express(&self.left_rad, &self.left_composites)?,
})
}
}
fn recompute_entry(
m: &IndecomposableModule,
tau_ind: &IndecomposableModule,
sequence: &ShortExactSequence,
x: &IndecomposableModule,
) -> Result<EntryRecompute, AlmostSplitError> {
let g = sequence.projection();
let f = sequence.inclusion();
let hom_xe = hom(x.module(), sequence.middle())?;
let composites: Vec<Morphism> = hom_xe.iter().map(|h| h.then(g)).collect::<Result<_, _>>()?;
let space_xm = HomSpace::new(x.module(), m.module())?;
let image = space_xm.subspace(&composites)?;
let rad = category_radical(x, m)?;
let hom_ex = hom(sequence.middle(), x.module())?;
let left_composites: Vec<Morphism> =
hom_ex.iter().map(|h| f.then(h)).collect::<Result<_, _>>()?;
let space_tx = HomSpace::new(sequence.sub(), x.module())?;
let left_image = space_tx.subspace(&left_composites)?;
let left_rad = category_radical(tau_ind, x)?;
Ok(EntryRecompute {
image,
rad,
composites,
left_image,
left_rad,
left_composites,
})
}
impl CatalogWitness {
accessor_methods! {
pub entry_checks() -> &[CatalogEntryCheck] = |this| &this.entries;
}
pub fn verify(
&self,
m: &IndecomposableModule,
catalog: &IndecomposableCatalog,
sequence: &ShortExactSequence,
class: &ExtClass,
) -> bool {
verify_guard!(
Arc::ptr_eq(m.module().algebra(), catalog.algebra())
&& self.entries.len() == catalog.len()
);
verify_guard!(!class.is_zero() && ext_sequence_holds(m, sequence, class));
let_or_false!(Ok(tau_ind) = IndecomposableModule::new(sequence.sub()));
for (check, x) in self.entries.iter().zip(catalog.entries()) {
let_or_false!(Ok(entry) = recompute_entry(m, &tau_ind, sequence, x));
verify_guard!(entry.verifies(check));
}
true
}
}
fn family_solves(stored: &[Vec<Fp>], over: &HomSubspace, expected: &[Morphism]) -> bool {
stored.len() == expected.len()
&& stored.iter().zip(expected).all(|(coords, target)| {
matches!(subspace_combination(over, coords), Some(rebuilt) if rebuilt == *target)
})
}
struct SocleConstruction {
tau_ind: IndecomposableModule,
class: ExtClass,
socle: DenseMat,
traces: Vec<Vec<Fp>>,
stable_end_dim: usize,
sequence: ShortExactSequence,
non_split: NonSplitWitness,
}
enum Construction {
Projective,
Built(Box<SocleConstruction>),
}
fn construct(m: &IndecomposableModule) -> Result<Construction, AlmostSplitError> {
let projective = m.is_projective();
let tau_module = tau(m.module())?;
if tau_module.is_zero() != projective {
return Err(defect(DefectKind::ProjectivityDisagreement {
resolution_projective: projective,
tau_zero: tau_module.is_zero(),
}));
}
if projective {
return Ok(Construction::Projective);
}
let tau_ind = IndecomposableModule::new(&tau_module)?;
let space = ExtSpace::new(m.module(), tau_ind.module(), 1)
.expect("the translate lives over the module's algebra Arc");
let stable = stable_end(m.module())?;
if space.dim() != stable.dim() {
return Err(defect(DefectKind::DualityDimensionMismatch {
ext_dim: space.dim(),
stable_end_dim: stable.dim(),
}));
}
let field = m.module().field();
let action = action_matrices(m, &space)?;
let socle = socle_kernel(&action, space.dim(), &field);
if socle.rows() != m.residue_degree() {
return Err(defect(DefectKind::SocleDimensionMismatch {
socle_dim: socle.rows(),
residue_degree: m.residue_degree(),
}));
}
let class = space.class_from_coordinates(socle.row(0))?;
let traces: Vec<Vec<Fp>> = action
.iter()
.map(|a| row_times(class.coordinates(), a, &field))
.collect();
let sequence = ShortExactSequence::from_ext1(&class)?;
let non_split = match sequence.split_status_one_pass() {
SplitStatus::NonSplit(witness) => witness,
SplitStatus::Split(_) => {
return Err(defect(DefectKind::NonzeroClassSplit));
}
};
Ok(Construction::Built(Box::new(SocleConstruction {
tau_ind,
class,
socle,
traces,
stable_end_dim: stable.dim(),
sequence,
non_split,
})))
}
pub fn almost_split(m: &IndecomposableModule) -> Result<AlmostSplitOutcome, AlmostSplitError> {
let built = match construct(m)? {
Construction::Projective => return Ok(AlmostSplitOutcome::Projective),
Construction::Built(built) => built,
};
let SocleConstruction {
tau_ind: _,
class,
socle,
traces,
stable_end_dim,
sequence,
non_split,
} = *built;
let witness = ArDualityWitness {
radical_coords: m.endo().radical_basis().clone(),
action_traces: traces,
socle_dim: socle.rows(),
socle_rref: socle,
chosen_row: 0,
ext_dim: class.space().dim(),
stable_end_dim,
residue_degree: m.residue_degree(),
non_split,
};
Ok(AlmostSplitOutcome::Sequence(AlmostSplitSequence {
sequence,
class,
witness: AlmostSplitWitness::ArDuality(witness),
}))
}
pub fn almost_split_via_catalog(
m: &IndecomposableModule,
catalog: &IndecomposableCatalog,
) -> Result<AlmostSplitOutcome, AlmostSplitError> {
Arc::ptr_eq(m.module().algebra(), catalog.algebra())
.then_some(())
.ok_or(AlmostSplitError::Hom(HomError::DifferentAlgebras))?;
let built = match construct(m)? {
Construction::Projective => return Ok(AlmostSplitOutcome::Projective),
Construction::Built(built) => built,
};
let SocleConstruction {
tau_ind,
class,
sequence,
..
} = *built;
let mut entries = Vec::with_capacity(catalog.len());
for (entry, x) in catalog.entries().iter().enumerate() {
let recomputed = recompute_entry(m, &tau_ind, &sequence, x)?;
if recomputed.image != recomputed.rad {
return Err(defect(DefectKind::RightFactorizationMismatch { entry }));
}
if recomputed.left_image != recomputed.left_rad {
return Err(defect(DefectKind::LeftFactorizationMismatch { entry }));
}
entries.push(recomputed.into_check()?);
}
Ok(AlmostSplitOutcome::Sequence(AlmostSplitSequence {
sequence,
class,
witness: AlmostSplitWitness::ExhaustiveCatalog(CatalogWitness { entries }),
}))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{Algebra, commutative_square, kronecker, linear_an, truncated_poly};
use crate::completion::CompletionLimits;
use crate::decompose::{KrullSchmidtOutcome, krull_schmidt};
use crate::field::PrimeField;
use crate::linalg::RowReducer;
use crate::module::direct_sum;
use crate::quiver::{ArrowId, Quiver};
use crate::radical::radical;
use crate::relation::{Presentation, Relation};
fn f2() -> PrimeField {
PrimeField::new(2).unwrap()
}
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn indec(m: &Module) -> IndecomposableModule {
IndecomposableModule::new(m).unwrap()
}
fn sequence_of(m: &IndecomposableModule) -> AlmostSplitSequence {
match almost_split(m).unwrap() {
AlmostSplitOutcome::Sequence(sequence) => sequence,
AlmostSplitOutcome::Projective => panic!("expected a sequence, got Projective"),
}
}
fn catalog_sequence_of(
m: &IndecomposableModule,
catalog: &IndecomposableCatalog,
) -> AlmostSplitSequence {
match almost_split_via_catalog(m, catalog).unwrap() {
AlmostSplitOutcome::Sequence(sequence) => sequence,
AlmostSplitOutcome::Projective => panic!("expected a sequence, got Projective"),
}
}
fn duality_witness(sequence: &AlmostSplitSequence) -> &ArDualityWitness {
match sequence.witness() {
AlmostSplitWitness::ArDuality(witness) => witness,
AlmostSplitWitness::ExhaustiveCatalog(_) => panic!("expected the AR duality witness"),
}
}
fn catalog_witness(sequence: &AlmostSplitSequence) -> &CatalogWitness {
match sequence.witness() {
AlmostSplitWitness::ExhaustiveCatalog(witness) => witness,
AlmostSplitWitness::ArDuality(_) => panic!("expected the catalog witness"),
}
}
fn middle_classes(middle: &Module) -> Vec<(Vec<usize>, usize)> {
match krull_schmidt(middle) {
KrullSchmidtOutcome::Classes(classes) => {
let mut dims: Vec<(Vec<usize>, usize)> = classes
.iter()
.map(|c| (c.representative.dim_vector().to_vec(), c.multiplicity))
.collect();
dims.sort();
dims
}
KrullSchmidtOutcome::Unknown { reason } => panic!("krull_schmidt failed: {reason}"),
}
}
fn ids(raw: &[u32]) -> Vec<ArrowId> {
raw.iter().copied().map(ArrowId).collect()
}
fn preprojective_a3() -> Arc<Algebra> {
let field = f2();
let quiver = Quiver::new(3, &[(0, 1), (1, 2), (1, 0), (2, 1)]).unwrap();
let relations = vec![
Relation::new(&quiver, field, vec![(field.one(), ids(&[0, 2]))]).unwrap(),
Relation::new(
&quiver,
field,
vec![(field.one(), ids(&[2, 0])), (field.elem(-1), ids(&[1, 3]))],
)
.unwrap(),
Relation::new(&quiver, field, vec![(field.one(), ids(&[3, 1]))]).unwrap(),
];
let presentation = Presentation::new(quiver, field, relations).unwrap();
Algebra::new(presentation, &CompletionLimits::default()).unwrap()
}
#[test]
fn truncated_poly_3_simple_has_the_uniserial_almost_split_sequence() {
for field in [f5(), f2()] {
let algebra = truncated_poly(3, field).unwrap();
let s = indec(&Module::simple(&algebra, 0));
let sequence = sequence_of(&s);
assert_eq!(sequence.sequence().sub().dim_vector(), &[1]);
assert_eq!(sequence.sequence().middle().dim_vector(), &[2]);
assert_eq!(sequence.sequence().quotient().dim_vector(), &[1]);
assert_eq!(
middle_classes(sequence.sequence().middle()),
vec![(vec![2], 1)]
);
let witness = duality_witness(&sequence);
assert_eq!(witness.ext_dim(), 1);
assert_eq!(witness.stable_end_dim(), 1);
assert_eq!(witness.socle_dim(), 1);
assert_eq!(witness.residue_degree(), 1);
assert_eq!(witness.chosen_row(), 0);
assert!(witness.action_traces().is_empty(), "rad End(S) = 0");
assert!(witness.verify(&s, sequence.sequence(), sequence.chosen_ar_class()));
}
}
#[test]
fn truncated_poly_3_rad_p_has_middle_simple_plus_projective() {
for field in [f5(), f2()] {
let algebra = truncated_poly(3, field).unwrap();
let p = Module::projective(&algebra, 0);
let r = indec(&radical(&p).0);
let sequence = sequence_of(&r);
assert_eq!(sequence.sequence().sub().dim_vector(), &[2]);
assert_eq!(sequence.sequence().middle().dim_vector(), &[4]);
assert_eq!(sequence.sequence().quotient().dim_vector(), &[2]);
assert_eq!(
middle_classes(sequence.sequence().middle()),
vec![(vec![1], 1), (vec![3], 1)]
);
let witness = duality_witness(&sequence);
assert_eq!(witness.ext_dim(), 1);
assert_eq!(witness.stable_end_dim(), 1);
assert_eq!(witness.socle_dim(), 1);
assert_eq!(
witness.action_traces().len(),
1,
"rad End(R) has dimension 1"
);
assert!(
witness
.action_traces()
.iter()
.all(|trace| trace.iter().all(|v| v.is_zero()))
);
assert!(witness.verify(&r, sequence.sequence(), sequence.chosen_ar_class()));
}
}
#[test]
fn linear_a3_sequence_ending_at_s1_has_middle_p1() {
let algebra = linear_an(3, f5());
let s1 = indec(&Module::simple(&algebra, 1));
let sequence = sequence_of(&s1);
assert_eq!(sequence.sequence().sub().dim_vector(), &[0, 0, 1]);
assert_eq!(sequence.sequence().middle().dim_vector(), &[0, 1, 1]);
assert_eq!(sequence.sequence().quotient().dim_vector(), &[0, 1, 0]);
assert_eq!(
middle_classes(sequence.sequence().middle()),
vec![(vec![0, 1, 1], 1)]
);
let witness = duality_witness(&sequence);
assert_eq!(witness.socle_dim(), 1);
assert_eq!(witness.residue_degree(), 1);
assert!(witness.verify(&s1, sequence.sequence(), sequence.chosen_ar_class()));
}
#[test]
fn linear_a3_sequence_ending_at_i1_matches_the_mesh() {
let algebra = linear_an(3, f5());
let i1 = indec(&Module::injective(&algebra, 1));
assert_eq!(i1.module().dim_vector(), &[1, 1, 0]);
let sequence = sequence_of(&i1);
assert_eq!(sequence.sequence().sub().dim_vector(), &[0, 1, 1]);
assert_eq!(sequence.sequence().middle().dim_vector(), &[1, 2, 1]);
assert_eq!(
middle_classes(sequence.sequence().middle()),
vec![(vec![0, 1, 0], 1), (vec![1, 1, 1], 1)]
);
let witness = duality_witness(&sequence);
assert_eq!(witness.socle_dim(), 1);
assert!(witness.verify(&i1, sequence.sequence(), sequence.chosen_ar_class()));
}
#[test]
fn commutative_square_s1_sequence_invariants_hold() {
let algebra = commutative_square(f5());
let s1 = indec(&Module::simple(&algebra, 1));
let sequence = sequence_of(&s1);
assert_eq!(sequence.sequence().quotient().dim_vector(), &[0, 1, 0, 0]);
assert_eq!(
sequence.sequence().sub().total_dim() + sequence.sequence().quotient().total_dim(),
sequence.sequence().middle().total_dim()
);
let witness = duality_witness(&sequence);
assert_eq!(witness.ext_dim(), witness.stable_end_dim());
assert_eq!(witness.socle_dim(), 1);
assert_eq!(witness.residue_degree(), 1);
assert!(witness.verify(&s1, sequence.sequence(), sequence.chosen_ar_class()));
}
#[test]
fn preprojective_a3_simple_sequence_invariants_hold() {
let algebra = preprojective_a3();
let s0 = indec(&Module::simple(&algebra, 0));
assert!(!s0.is_projective());
let sequence = sequence_of(&s0);
assert_eq!(
sequence.sequence().sub().total_dim() + sequence.sequence().quotient().total_dim(),
sequence.sequence().middle().total_dim()
);
let witness = duality_witness(&sequence);
assert_eq!(witness.ext_dim(), witness.stable_end_dim());
assert_eq!(witness.socle_dim(), 1);
assert_eq!(witness.residue_degree(), 1);
assert!(witness.verify(&s0, sequence.sequence(), sequence.chosen_ar_class()));
}
#[test]
fn truncated_poly_4_interval_module_has_a_proper_socle() {
let field = f5();
let algebra = truncated_poly(4, field).unwrap();
let p = Module::projective(&algebra, 0);
let m = indec(&radical(&radical(&p).0).0);
assert_eq!(m.module().dim_vector(), &[2]);
let sequence = sequence_of(&m);
assert_eq!(sequence.sequence().sub().dim_vector(), &[2]);
assert_eq!(sequence.sequence().middle().dim_vector(), &[4]);
assert_eq!(
middle_classes(sequence.sequence().middle()),
vec![(vec![1], 1), (vec![3], 1)]
);
let witness = duality_witness(&sequence);
assert_eq!(witness.ext_dim(), 2);
assert_eq!(witness.stable_end_dim(), 2);
assert_eq!(witness.socle_dim(), 1);
assert_eq!(witness.residue_degree(), 1);
assert_eq!(witness.action_traces().len(), 1);
assert_eq!(witness.action_traces()[0].len(), 2);
assert!(witness.action_traces()[0].iter().all(|v| v.is_zero()));
assert!(witness.verify(&m, sequence.sequence(), sequence.chosen_ar_class()));
}
#[test]
fn stable_hom_dimensions_match_hand_counts() {
let a3 = linear_an(3, f5());
let s2 = Module::simple(&a3, 2);
assert_eq!(stable_end(&s2).unwrap().dim(), 0);
let s1 = Module::simple(&a3, 1);
assert_eq!(stable_end(&s1).unwrap().dim(), 1);
for field in [f5(), f2()] {
let algebra = truncated_poly(3, field).unwrap();
let p = Module::projective(&algebra, 0);
let r = radical(&p).0;
let space = HomSpace::new(&r, &r).unwrap();
assert_eq!(space.dim(), 2);
assert_eq!(projectively_trivial(&space).unwrap().dim(), 1);
assert_eq!(stable_end(&r).unwrap().dim(), 1);
}
}
#[test]
fn projective_inputs_return_the_projective_outcome() {
let a3 = linear_an(3, f5());
for v in 0..3 {
let p = indec(&Module::projective(&a3, v));
assert!(matches!(
almost_split(&p).unwrap(),
AlmostSplitOutcome::Projective
));
}
let algebra = truncated_poly(3, f2()).unwrap();
let p = indec(&Module::projective(&algebra, 0));
assert!(matches!(
almost_split(&p).unwrap(),
AlmostSplitOutcome::Projective
));
let catalog = IndecomposableCatalog::nakayama(&algebra).unwrap();
assert!(matches!(
almost_split_via_catalog(&p, &catalog).unwrap(),
AlmostSplitOutcome::Projective
));
}
#[test]
fn via_catalog_agrees_with_the_ar_duality_route() {
let x3 = truncated_poly(3, f2()).unwrap();
let x3_catalog = IndecomposableCatalog::nakayama(&x3).unwrap();
let a3 = linear_an(3, f5());
let a3_catalog = IndecomposableCatalog::dynkin(&a3).unwrap();
let cases = [
(indec(&Module::simple(&x3, 0)), x3_catalog),
(indec(&Module::simple(&a3, 1)), a3_catalog),
];
for (m, catalog) in &cases {
let duality = sequence_of(m);
let through_catalog = catalog_sequence_of(m, catalog);
assert_eq!(
duality.sequence().middle().dim_vector(),
through_catalog.sequence().middle().dim_vector()
);
let left = duality.sequence().sub();
let right = through_catalog.sequence().sub();
assert_eq!(left.dim_vector(), right.dim_vector());
for a in 0..left.algebra().quiver().num_arrows() {
let arrow = ArrowId(a as u32);
assert_eq!(
left.map(arrow).entries_u64(),
right.map(arrow).entries_u64()
);
}
let transported = duality
.chosen_ar_class()
.space()
.class_from_coordinates(through_catalog.chosen_ar_class().coordinates())
.unwrap();
assert!(transported.equals(duality.chosen_ar_class()).unwrap());
let witness = catalog_witness(&through_catalog);
assert!(witness.verify(
m,
catalog,
through_catalog.sequence(),
through_catalog.chosen_ar_class()
));
}
}
#[test]
fn via_catalog_rejects_a_catalog_over_another_algebra() {
let x3 = truncated_poly(3, f2()).unwrap();
let m = indec(&Module::simple(&x3, 0));
let a3 = linear_an(3, f5());
let catalog = IndecomposableCatalog::dynkin(&a3).unwrap();
assert!(matches!(
almost_split_via_catalog(&m, &catalog),
Err(AlmostSplitError::Hom(HomError::DifferentAlgebras))
));
}
#[test]
fn a_tampered_action_trace_fails_verification() {
let algebra = truncated_poly(3, f5()).unwrap();
let p = Module::projective(&algebra, 0);
let r = indec(&radical(&p).0);
let sequence = sequence_of(&r);
let mut bad = duality_witness(&sequence).clone();
assert_eq!(bad.action_traces.len(), 1);
bad.action_traces[0][0] = f5().one();
assert!(!bad.verify(&r, sequence.sequence(), sequence.chosen_ar_class()));
}
#[test]
fn a_swapped_socle_row_fails_verification() {
let field = f5();
let algebra = truncated_poly(4, field).unwrap();
let p = Module::projective(&algebra, 0);
let m = indec(&radical(&radical(&p).0).0);
let sequence = sequence_of(&m);
let witness = duality_witness(&sequence);
let socle = witness.socle_rref().clone();
let dim = witness.ext_dim();
let mut reducer = RowReducer::new(dim);
for r in 0..socle.rows() {
reducer.push(socle.row(r), &field);
}
let candidate = (0..dim)
.map(|k| {
let mut row = vec![field.zero(); dim];
row[k] = field.one();
row
})
.find(|row| reducer.push(row, &field))
.expect("the socle is proper, so some unit vector lies outside it");
let action = action_matrices(&m, sequence.chosen_ar_class().space()).unwrap();
assert!(
action.iter().any(|a| row_times(&candidate, a, &field)
.iter()
.any(|v| !v.is_zero())),
"the replacement vector is not annihilated, so it is not in the socle"
);
let mut bad = witness.clone();
bad.socle_rref = DenseMat::from_rows(&[candidate]);
assert!(!bad.verify(&m, sequence.sequence(), sequence.chosen_ar_class()));
}
#[test]
fn a_tampered_dual_vector_fails_verification() {
let algebra = truncated_poly(3, f5()).unwrap();
let s = indec(&Module::simple(&algebra, 0));
let p = Module::projective(&algebra, 0);
let r = indec(&radical(&p).0);
let s_sequence = sequence_of(&s);
let r_sequence = sequence_of(&r);
let s_witness = duality_witness(&s_sequence);
let r_witness = duality_witness(&r_sequence);
assert_ne!(
s_witness.non_split().dual().len(),
r_witness.non_split().dual().len()
);
let mut bad = s_witness.clone();
bad.non_split = r_witness.non_split().clone();
assert!(!bad.verify(&s, s_sequence.sequence(), s_sequence.chosen_ar_class()));
}
#[test]
fn a_tampered_catalog_factorization_coordinate_fails_verification() {
let field = f2();
let algebra = truncated_poly(3, field).unwrap();
let catalog = IndecomposableCatalog::nakayama(&algebra).unwrap();
let m = indec(&Module::simple(&algebra, 0));
let sequence = catalog_sequence_of(&m, &catalog);
let witness = catalog_witness(&sequence);
assert!(witness.verify(
&m,
&catalog,
sequence.sequence(),
sequence.chosen_ar_class()
));
let entry = witness
.entries
.iter()
.position(|check| {
check
.right_factorizations
.first()
.is_some_and(|row| !row.is_empty())
})
.expect("some catalog entry has a nonzero radical into M");
let mut bad = witness.clone();
let old = bad.entries[entry].right_factorizations[0][0];
bad.entries[entry].right_factorizations[0][0] = field.add(old, field.one());
assert!(!bad.verify(
&m,
&catalog,
sequence.sequence(),
sequence.chosen_ar_class()
));
let mut missing = witness.clone();
missing.entries[entry].right_factorizations.pop();
assert!(!missing.verify(
&m,
&catalog,
sequence.sequence(),
sequence.chosen_ar_class()
));
}
#[test]
fn a_scaled_class_fails_catalog_verification() {
let field = f5();
let algebra = truncated_poly(3, field).unwrap();
let catalog = IndecomposableCatalog::nakayama(&algebra).unwrap();
let m = indec(&Module::simple(&algebra, 0));
let sequence = catalog_sequence_of(&m, &catalog);
let witness = catalog_witness(&sequence);
assert!(witness.verify(
&m,
&catalog,
sequence.sequence(),
sequence.chosen_ar_class()
));
let scaled = sequence.chosen_ar_class().scale(field.elem(2));
assert!(!scaled.is_zero());
assert!(!witness.verify(&m, &catalog, sequence.sequence(), &scaled));
}
#[test]
fn a_space_with_the_wrong_target_fails_duality_verification() {
let field = f5();
let algebra = truncated_poly(3, field).unwrap();
let s = indec(&Module::simple(&algebra, 0));
let genuine = sequence_of(&s);
let witness = duality_witness(&genuine);
let r = radical(&Module::projective(&algebra, 0)).0;
let wrong_space = ExtSpace::new(s.module(), &r, 1).unwrap();
assert_eq!(wrong_space.dim(), 1);
let class = wrong_space.class_from_coordinates(&[field.one()]).unwrap();
let sequence = ShortExactSequence::from_ext1(&class).unwrap();
let SplitStatus::NonSplit(non_split) = sequence.split_status() else {
panic!("the nonzero class does not split");
};
let mut bad = witness.clone();
bad.non_split = non_split;
assert!(!bad.verify(&s, &sequence, &class));
}
#[test]
fn a_dimension_field_altered_in_either_direction_fails_verification() {
let algebra = truncated_poly(3, f5()).unwrap();
let p = Module::projective(&algebra, 0);
let r = indec(&radical(&p).0);
let sequence = sequence_of(&r);
let witness = duality_witness(&sequence);
assert!(witness.verify(&r, sequence.sequence(), sequence.chosen_ar_class()));
for delta in [1isize, -1] {
let shift = |v: usize| (v as isize + delta) as usize;
let mut bad = witness.clone();
bad.ext_dim = shift(bad.ext_dim);
assert!(!bad.verify(&r, sequence.sequence(), sequence.chosen_ar_class()));
let mut bad = witness.clone();
bad.stable_end_dim = shift(bad.stable_end_dim);
assert!(!bad.verify(&r, sequence.sequence(), sequence.chosen_ar_class()));
let mut bad = witness.clone();
bad.socle_dim = shift(bad.socle_dim);
assert!(!bad.verify(&r, sequence.sequence(), sequence.chosen_ar_class()));
let mut bad = witness.clone();
bad.residue_degree = shift(bad.residue_degree);
assert!(!bad.verify(&r, sequence.sequence(), sequence.chosen_ar_class()));
}
}
#[test]
fn defect_kind_display_is_stable() {
assert_eq!(
DefectKind::DualityDimensionMismatch {
ext_dim: 2,
stable_end_dim: 1
}
.to_string(),
"Ext^1(M, tau M) has dimension 2, stable End(M) has dimension 1; crate defect"
);
assert_eq!(
DefectKind::SocleDimensionMismatch {
socle_dim: 0,
residue_degree: 1
}
.to_string(),
"the Ext socle has dimension 0, the residue degree is 1; crate defect"
);
assert_eq!(
DefectKind::ProjectivityDisagreement {
resolution_projective: true,
tau_zero: false
}
.to_string(),
"the resolution route reports projective = true, tau reports zero = false; \
crate defect"
);
assert_eq!(
DefectKind::NonzeroClassSplit.to_string(),
"the sequence of a nonzero chosen class splits; crate defect"
);
assert_eq!(
DefectKind::RightFactorizationMismatch { entry: 3 }.to_string(),
"the image of Hom(X, E) in Hom(X, M) differs from rad(X, M) at catalog entry 3; \
crate defect"
);
assert_eq!(
DefectKind::LeftFactorizationMismatch { entry: 0 }.to_string(),
"the image of Hom(E, X) in Hom(tau M, X) differs from rad(tau M, X) at catalog \
entry 0; crate defect"
);
}
#[test]
fn catalog_domains_have_one_dimensional_socles() {
let x3 = truncated_poly(3, f2()).unwrap();
let a3 = linear_an(3, f5());
let catalogs = [
IndecomposableCatalog::nakayama(&x3).unwrap(),
IndecomposableCatalog::dynkin(&a3).unwrap(),
];
for catalog in &catalogs {
for entry in catalog.entries() {
assert_eq!(entry.residue_degree(), 1);
if entry.is_projective() {
continue;
}
let sequence = sequence_of(entry);
let witness = duality_witness(&sequence);
assert_eq!(witness.socle_dim(), 1);
assert_eq!(witness.residue_degree(), 1);
}
}
}
fn quasi_length_two_in_the_f8_tube() -> Module {
let field = f2();
let algebra = kronecker(2, field);
let mut j = DenseMat::zero(6, 6);
for (r, c) in [(0, 1), (1, 2), (2, 0), (2, 1)] {
j.set(r, c, field.one());
j.set(3 + r, 3 + c, field.one());
}
for r in 0..3 {
j.set(r, 3 + r, field.one());
}
Module::new(algebra, vec![6, 6], vec![DenseMat::identity(6), j])
.expect("the Kronecker representation is a module")
}
#[test]
fn the_quasi_length_two_module_has_a_three_dimensional_socle_in_a_six_dimensional_ext_space() {
let w = indec(&quasi_length_two_in_the_f8_tube());
assert_eq!(w.endo().dim(), 6);
assert_eq!(w.endo().radical_dim(), 3);
assert_eq!(w.residue_degree(), 3);
let sequence = sequence_of(&w);
let witness = duality_witness(&sequence);
assert_eq!(witness.ext_dim(), 6);
assert_eq!(witness.stable_end_dim(), 6);
assert_eq!(witness.socle_dim(), 3);
assert_eq!(sequence.chosen_ar_class().space().dim(), 6);
assert_eq!(witness.chosen_row(), 0);
assert!(sequence.verify(&w));
assert_eq!(sequence.sequence().sub().dim_vector(), &[6, 6]);
assert_eq!(sequence.sequence().middle().dim_vector(), &[12, 12]);
}
#[test]
fn a_chosen_row_other_than_zero_fails_duality_verification() {
let w = indec(&quasi_length_two_in_the_f8_tube());
let sequence = sequence_of(&w);
let witness = duality_witness(&sequence);
let space = sequence.chosen_ar_class().space();
let socle = witness.socle_rref();
assert!(socle.rows() >= 2, "the socle has a row other than 0");
let field = w.module().field();
let other = space.class_from_coordinates(socle.row(1)).unwrap();
let action = action_matrices(&w, space).unwrap();
let traces: Vec<Vec<Fp>> = action
.iter()
.map(|a| row_times(other.coordinates(), a, &field))
.collect();
assert!(
traces.iter().flatten().all(|v| v.is_zero()),
"socle row 1 annihilates rad End(M)"
);
let other_sequence = ShortExactSequence::from_ext1(&other).unwrap();
let SplitStatus::NonSplit(non_split) = other_sequence.split_status() else {
panic!("a nonzero socle class gives a non-split sequence");
};
assert!(non_split.verify(&other_sequence));
let row_one = ArDualityWitness {
radical_coords: witness.radical_basis_coords().clone(),
action_traces: traces,
socle_rref: socle.clone(),
chosen_row: 1,
ext_dim: witness.ext_dim(),
stable_end_dim: witness.stable_end_dim(),
socle_dim: witness.socle_dim(),
residue_degree: witness.residue_degree(),
non_split,
};
assert!(!row_one.verify(&w, &other_sequence, &other));
}
fn simple_over_truncated_poly_3() -> IndecomposableModule {
let algebra = truncated_poly(3, f5()).unwrap();
indec(&Module::simple(&algebra, 0))
}
#[test]
fn a_coboundary_basis_forged_from_the_complement_fails_duality_verification() {
let s = simple_over_truncated_poly_3();
let sequence = sequence_of(&s);
let witness = duality_witness(&sequence);
let class = sequence.chosen_ar_class();
assert!(witness.verify(&s, sequence.sequence(), class));
let space = class.space();
assert_eq!(space.coboundary_basis().rows(), 0);
assert_eq!(space.complement_basis().rows(), 1);
let forged = space.with_bases(
space.cocycle_basis().clone(),
space.complement_basis().clone(),
space.complement_basis().clone(),
);
let bad = forged.class_from_coordinates(class.coordinates()).unwrap();
assert_eq!(bad.coordinates(), class.coordinates());
assert!(!witness.verify(&s, sequence.sequence(), &bad));
}
#[test]
fn an_emptied_cocycle_basis_fails_duality_verification() {
let s = simple_over_truncated_poly_3();
let sequence = sequence_of(&s);
let witness = duality_witness(&sequence);
let class = sequence.chosen_ar_class();
let space = class.space();
let width = space.cocycle_basis().cols();
let forged = space.with_bases(
DenseMat::zero(0, width),
space.coboundary_basis().clone(),
space.complement_basis().clone(),
);
let bad = forged.class_from_coordinates(class.coordinates()).unwrap();
assert!(!witness.verify(&s, sequence.sequence(), &bad));
}
#[test]
fn a_scaled_representative_fails_duality_verification() {
let s = simple_over_truncated_poly_3();
let sequence = sequence_of(&s);
let witness = duality_witness(&sequence);
let class = sequence.chosen_ar_class();
let space = class.space();
assert_eq!(witness.radical_basis_coords().rows(), 0);
let scaled = space
.representatives()
.iter()
.map(|rep| scale_morphism(rep, f5().elem(2)))
.collect();
let forged = space.with_representatives(scaled);
let bad = forged.class_from_coordinates(class.coordinates()).unwrap();
assert!(!witness.verify(&s, sequence.sequence(), &bad));
}
#[test]
fn the_action_matrices_reverse_composition() {
let field = f5();
let algebra = truncated_poly(3, field).unwrap();
let s = Module::simple(&algebra, 0);
let (m, _, _) = direct_sum(&[&s, &s]);
let space = ExtSpace::new(&m, &s, 1).unwrap();
assert_eq!(space.dim(), 2);
let end = hom(&m, &m).unwrap();
let mut saw_noncommuting = false;
for phi in &end {
for psi in &end {
let a_phi = action_matrix(&space, phi).unwrap();
let a_psi = action_matrix(&space, psi).unwrap();
let composite = action_matrix(&space, &phi.then(psi).unwrap()).unwrap();
assert_eq!(composite, a_psi.mul(&a_phi, &field));
if a_psi.mul(&a_phi, &field) != a_phi.mul(&a_psi, &field) {
saw_noncommuting = true;
}
}
}
assert!(
saw_noncommuting,
"the fixture exercises a noncommutative End"
);
}
#[test]
fn the_sequence_verifies_through_its_own_witness_and_rejects_the_other_route() {
let algebra = truncated_poly(3, f5()).unwrap();
let catalog = IndecomposableCatalog::nakayama(&algebra).unwrap();
let s = indec(&Module::simple(&algebra, 0));
let duality = sequence_of(&s);
assert!(duality.verify(&s));
assert!(!duality.verify_with_catalog(&s, &catalog));
let through_catalog = catalog_sequence_of(&s, &catalog);
assert!(through_catalog.verify_with_catalog(&s, &catalog));
assert!(!through_catalog.verify(&s));
}
}