use std::fmt;
use crate::decompose::add_morphisms;
use crate::endo::EndoAlgebra;
use crate::field::{Fp, PrimeField};
use crate::hom::{HomError, Morphism, hom, identity, zero_morphism};
use crate::homspace::{HomSpace, HomSpaceError};
use crate::indec::{IndecError, IndecomposableModule};
use crate::iso::indecomposable_iso;
use crate::linalg::{DenseMat, RowReducer};
use crate::module::{Module, direct_sum};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ApproxDefect {
GeneratorGrowth {
summand: usize,
growth: usize,
residue_degree: usize,
},
FactorizationMissing {
summand: usize,
basis_index: usize,
},
KernelOutsideRadical {
row: usize,
kernel_dim: usize,
radical_dim: usize,
},
}
impl fmt::Display for ApproxDefect {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::GeneratorGrowth {
summand,
growth,
residue_degree,
} => write!(
f,
"a generator for summand {summand} raised the span by {growth}, not by the \
residue degree {residue_degree}; crate defect"
),
Self::FactorizationMissing {
summand,
basis_index,
} => write!(
f,
"basis map {basis_index} for summand {summand} does not factor through the \
built map; crate defect"
),
Self::KernelOutsideRadical {
row,
kernel_dim,
radical_dim,
} => write!(
f,
"row {row} of the {kernel_dim}-dimensional kernel lies outside the \
{radical_dim}-dimensional radical; crate defect"
),
}
}
}
impl std::error::Error for ApproxDefect {}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ApproxError {
SummandNotIndecomposable {
index: usize,
reason: IndecError,
},
RepeatedSummand {
first: usize,
second: usize,
},
Hom(HomError),
HomSpace(HomSpaceError),
Defect(ApproxDefect),
}
impl fmt::Display for ApproxError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::SummandNotIndecomposable { index, reason } => {
write!(f, "add-generator {index} is not indecomposable: {reason}")
}
Self::RepeatedSummand { first, second } => write!(
f,
"add-generators {first} and {second} are isomorphic; give one module per class"
),
Self::Hom(error) => write!(f, "hom: {error}"),
Self::HomSpace(error) => write!(f, "hom space: {error}"),
Self::Defect(defect) => write!(f, "{defect}"),
}
}
}
impl std::error::Error for ApproxError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::SummandNotIndecomposable { reason, .. } => Some(reason),
Self::Hom(error) => Some(error),
Self::HomSpace(error) => Some(error),
Self::Defect(defect) => Some(defect),
Self::RepeatedSummand { .. } => None,
}
}
}
fn unit(dim: usize, k: usize, field: &PrimeField) -> Vec<Fp> {
let mut v = vec![Fp::ZERO; dim];
v[k] = field.one();
v
}
fn certify(n_summands: &[Module]) -> Result<Vec<IndecomposableModule>, ApproxError> {
let mut certified = Vec::with_capacity(n_summands.len());
for (index, n) in n_summands.iter().enumerate() {
let ind = IndecomposableModule::new(n)
.map_err(|reason| ApproxError::SummandNotIndecomposable { index, reason })?;
certified.push(ind);
}
for second in 0..certified.len() {
for first in 0..second {
let iso = indecomposable_iso(
certified[first].module(),
certified[second].module(),
certified[first].endo(),
);
if iso.is_some() {
return Err(ApproxError::RepeatedSummand { first, second });
}
}
}
Ok(certified)
}
fn slot_sum(
algebra_source: &Module,
summands: &[IndecomposableModule],
slots: &[usize],
) -> (Module, Vec<Morphism>, Vec<Morphism>) {
if slots.is_empty() {
return (
Module::zero(algebra_source.algebra()),
Vec::new(),
Vec::new(),
);
}
let parts: Vec<&Module> = slots.iter().map(|&i| summands[i].module()).collect();
direct_sum(&parts)
}
fn row_relations(rows: &[Vec<Fp>], width: usize, field: &PrimeField) -> DenseMat {
if rows.is_empty() {
return DenseMat::zero(0, 0);
}
let stacked = if width == 0 {
DenseMat::zero(rows.len(), 0)
} else {
DenseMat::from_rows(rows)
};
stacked
.transpose()
.into_kernel_basis(field)
.into_row_space_basis(field)
}
fn radical_coordinates(endo: &EndoAlgebra, kernel: &DenseMat) -> Result<Vec<Vec<Fp>>, usize> {
let field = endo.field();
if kernel.rows() == 0 {
return Ok(Vec::new());
}
let radical = endo.radical_basis().transpose();
let Some(x) = radical.solve_many(&kernel.transpose(), &field) else {
return Err((0..kernel.rows())
.position(|r| radical.solve(kernel.row(r), &field).is_none())
.expect("solve_many rejects only when some row lies outside"));
};
Ok(columns_of(&x))
}
fn columns_of(x: &DenseMat) -> Vec<Vec<Fp>> {
(0..x.cols())
.map(|j| (0..x.rows()).map(|i| x.get(i, j)).collect())
.collect()
}
fn unit_factorizations(system: &DenseMat, field: &PrimeField) -> Result<Vec<Vec<Fp>>, usize> {
let dim = system.rows();
if dim == 0 {
return Ok(Vec::new());
}
let Some(x) = system.solve_many(&DenseMat::identity(dim), field) else {
return Err((0..dim)
.position(|j| system.solve(&unit(dim, j, field), field).is_none())
.expect("solve_many rejects only when some unit lies outside"));
};
Ok(columns_of(&x))
}
fn radical_combination_matches(endo: &EndoAlgebra, coords: &[Fp], row: &[Fp]) -> bool {
let field = endo.field();
let radical = endo.radical_basis();
if coords.len() != radical.rows() || row.len() != endo.dim() {
return false;
}
for (c, &want) in row.iter().enumerate() {
let mut acc = Fp::ZERO;
for (t, &x) in coords.iter().enumerate() {
acc = field.add(acc, field.mul(x, radical.get(t, c)));
}
if acc != want {
return false;
}
}
true
}
fn decomposition_holds(
total: &Module,
summands: &[IndecomposableModule],
slots: &[usize],
inclusions: &[Morphism],
projections: &[Morphism],
) -> bool {
if inclusions.len() != slots.len() || projections.len() != slots.len() {
return false;
}
let mut sum = match zero_morphism(total, total) {
Ok(z) => z,
Err(_) => return false,
};
for (c, &i) in slots.iter().enumerate() {
let part = summands[i].module();
if !inclusions[c].source().ptr_eq(part) || !inclusions[c].target().ptr_eq(total) {
return false;
}
if !projections[c].source().ptr_eq(total) || !projections[c].target().ptr_eq(part) {
return false;
}
for (d, incl) in inclusions.iter().enumerate() {
let Ok(composite) = incl.then(&projections[c]) else {
return false;
};
if c == d {
if composite != identity(part) {
return false;
}
} else if !composite.is_zero() {
return false;
}
}
let Ok(idempotent) = projections[c].then(&inclusions[c]) else {
return false;
};
sum = add_morphisms(&sum, &idempotent);
}
sum == identity(total)
}
#[derive(Debug)]
pub struct MinimalLeftApproximation {
map: Morphism,
summands: Vec<IndecomposableModule>,
slots: Vec<usize>,
inclusions: Vec<Morphism>,
projections: Vec<Morphism>,
factorizations: Vec<Vec<Vec<Fp>>>,
kernel: DenseMat,
radical: Vec<Vec<Fp>>,
}
impl MinimalLeftApproximation {
#[inline]
pub fn map(&self) -> &Morphism {
&self.map
}
#[inline]
pub fn summands(&self) -> &[IndecomposableModule] {
&self.summands
}
#[inline]
pub fn slots(&self) -> &[usize] {
&self.slots
}
#[inline]
pub fn inclusions(&self) -> &[Morphism] {
&self.inclusions
}
#[inline]
pub fn projections(&self) -> &[Morphism] {
&self.projections
}
pub fn multiplicity(&self, summand: usize) -> usize {
self.slots.iter().filter(|&&i| i == summand).count()
}
pub fn factorization(&self, summand: usize, basis_index: usize) -> &[Fp] {
&self.factorizations[summand][basis_index]
}
#[inline]
pub fn kernel_basis(&self) -> &DenseMat {
&self.kernel
}
pub fn radical_coordinates(&self, row: usize) -> &[Fp] {
&self.radical[row]
}
pub fn verify(&self) -> bool {
let x = self.map.source();
let b = self.map.target();
if self.factorizations.len() != self.summands.len() {
return false;
}
if self.slots.iter().any(|&i| i >= self.summands.len()) {
return false;
}
if !decomposition_holds(
b,
&self.summands,
&self.slots,
&self.inclusions,
&self.projections,
) {
return false;
}
for (i, n) in self.summands.iter().enumerate() {
let (Ok(target_space), Ok(source_space)) =
(HomSpace::new(x, n.module()), HomSpace::new(b, n.module()))
else {
return false;
};
if self.factorizations[i].len() != target_space.dim() {
return false;
}
for (j, coords) in self.factorizations[i].iter().enumerate() {
if coords.len() != source_space.dim() {
return false;
}
let Ok(composite) = self.map.then(&source_space.morphism(coords)) else {
return false;
};
if composite != target_space.basis()[j] {
return false;
}
}
}
let endo = EndoAlgebra::new(b);
let Ok(space) = HomSpace::new(x, b) else {
return false;
};
let field = x.field();
let mut rows = Vec::with_capacity(endo.dim());
for e in endo.basis() {
let Ok(composite) = self.map.then(e) else {
return false;
};
match space.coords(&composite) {
Ok(c) => rows.push(c),
Err(_) => return false,
}
}
let kernel = row_relations(&rows, space.dim(), &field);
if kernel != self.kernel || self.radical.len() != kernel.rows() {
return false;
}
(0..kernel.rows())
.all(|r| radical_combination_matches(&endo, &self.radical[r], kernel.row(r)))
}
}
pub fn left_approximation(
x: &Module,
n_summands: &[Module],
) -> Result<MinimalLeftApproximation, ApproxError> {
let summands = certify(n_summands)?;
let field = x.field();
let mut spaces = Vec::with_capacity(summands.len());
for n in &summands {
spaces.push(HomSpace::new(x, n.module()).map_err(ApproxError::Hom)?);
}
let mut slots: Vec<usize> = Vec::new();
let mut components: Vec<Morphism> = Vec::new();
for (i, n) in summands.iter().enumerate() {
let width = spaces[i].dim();
let mut rows: Vec<Vec<Fp>> = Vec::new();
for (j, other) in summands.iter().enumerate() {
if j == i {
let radical = n.endo().radical_basis();
for r in 0..radical.rows() {
let step = n.endo().morphism(radical.row(r));
for g in spaces[i].basis() {
rows.push(compose_into(&spaces[i], g, &step)?);
}
}
} else {
let between = hom(other.module(), n.module()).map_err(ApproxError::Hom)?;
for step in &between {
for g in spaces[j].basis() {
rows.push(compose_into(&spaces[i], g, step)?);
}
}
}
}
let mut span = RowReducer::new(width);
for row in &rows {
span.push(row, &field);
}
for t in 0..width {
if !span.push(&unit(width, t, &field), &field) {
continue;
}
let before = span.rank() - 1;
let g = &spaces[i].basis()[t];
for e in n.endo().basis() {
span.push(&compose_into(&spaces[i], g, e)?, &field);
}
let growth = span.rank() - before;
if growth != n.residue_degree() {
return Err(ApproxError::Defect(ApproxDefect::GeneratorGrowth {
summand: i,
growth,
residue_degree: n.residue_degree(),
}));
}
slots.push(i);
components.push(g.clone());
}
}
let (b, inclusions, projections) = slot_sum(x, &summands, &slots);
let mut map = zero_morphism(x, &b).map_err(ApproxError::Hom)?;
for (c, component) in components.iter().enumerate() {
let block = component
.then(&inclusions[c])
.expect("a component lands in its own block");
map = add_morphisms(&map, &block);
}
let mut factorizations = Vec::with_capacity(summands.len());
for (i, n) in summands.iter().enumerate() {
let source_space = HomSpace::new(&b, n.module()).map_err(ApproxError::Hom)?;
let mut images = Vec::with_capacity(source_space.dim());
for h in source_space.basis() {
let composite = map.then(h).expect("f composes with a map out of B");
images.push(
spaces[i]
.coords(&composite)
.map_err(ApproxError::HomSpace)?,
);
}
let system = if images.is_empty() {
DenseMat::zero(spaces[i].dim(), 0)
} else {
DenseMat::from_rows(&images).transpose()
};
factorizations.push(unit_factorizations(&system, &field).map_err(|basis_index| {
ApproxError::Defect(ApproxDefect::FactorizationMissing {
summand: i,
basis_index,
})
})?);
}
let endo = EndoAlgebra::new(&b);
let space = HomSpace::new(x, &b).map_err(ApproxError::Hom)?;
let mut rows = Vec::with_capacity(endo.dim());
for e in endo.basis() {
let composite = map.then(e).expect("f composes with an endomorphism of B");
rows.push(space.coords(&composite).map_err(ApproxError::HomSpace)?);
}
let kernel = row_relations(&rows, space.dim(), &field);
let radical = radical_coordinates(&endo, &kernel).map_err(|row| {
ApproxError::Defect(ApproxDefect::KernelOutsideRadical {
row,
kernel_dim: kernel.rows(),
radical_dim: endo.radical_dim(),
})
})?;
Ok(MinimalLeftApproximation {
map,
summands,
slots,
inclusions,
projections,
factorizations,
kernel,
radical,
})
}
fn compose_into(
space: &HomSpace,
first: &Morphism,
second: &Morphism,
) -> Result<Vec<Fp>, ApproxError> {
let composite = first.then(second).map_err(ApproxError::Hom)?;
space.coords(&composite).map_err(ApproxError::HomSpace)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{Algebra, commutative_square, kronecker, linear_an, truncated_poly};
use crate::dynkin::{DynkinType, dynkin_quiver};
use crate::field::PrimeField;
use crate::hom::kernel;
use crate::quiver::Quiver;
use std::sync::Arc;
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 fixtures(field: PrimeField) -> Vec<(&'static str, Arc<Algebra>)> {
vec![
("A_2", linear_an(2, field)),
("A_3", linear_an(3, field)),
("k[x]/x^3", truncated_poly(3, field).unwrap()),
("D_4", d4(field)),
("commutative square", commutative_square(field)),
]
}
fn projectives(algebra: &Arc<Algebra>) -> Vec<Module> {
(0..algebra.quiver().num_vertices())
.map(|v| Module::projective(algebra, v))
.collect()
}
fn injectives(algebra: &Arc<Algebra>) -> Vec<Module> {
(0..algebra.quiver().num_vertices())
.map(|v| Module::injective(algebra, v))
.collect()
}
fn test_modules(algebra: &Arc<Algebra>) -> Vec<Module> {
let mut out: Vec<Module> = (0..algebra.quiver().num_vertices())
.map(|v| Module::simple(algebra, v))
.collect();
out.extend(projectives(algebra));
out.extend(injectives(algebra));
out
}
fn left_property_holds(a: &MinimalLeftApproximation) -> bool {
let x = a.map().source();
let b = a.map().target();
let field = x.field();
for n in a.summands() {
let target_space = HomSpace::new(x, n.module()).unwrap();
let source_space = HomSpace::new(b, n.module()).unwrap();
let images: Vec<Vec<Fp>> = source_space
.basis()
.iter()
.map(|h| target_space.coords(&a.map().then(h).unwrap()).unwrap())
.collect();
let system = if images.is_empty() {
DenseMat::zero(target_space.dim(), 0)
} else {
DenseMat::from_rows(&images).transpose()
};
if unit_factorizations(&system, &field).is_err() {
return false;
}
}
true
}
fn left_factorizations(f: &Morphism, summands: &[IndecomposableModule]) -> Vec<Vec<Vec<Fp>>> {
let field = f.source().field();
summands
.iter()
.map(|n| {
let target_space = HomSpace::new(f.source(), n.module()).unwrap();
let source_space = HomSpace::new(f.target(), n.module()).unwrap();
let images: Vec<Vec<Fp>> = source_space
.basis()
.iter()
.map(|h| target_space.coords(&f.then(h).unwrap()).unwrap())
.collect();
let system = if images.is_empty() {
DenseMat::zero(target_space.dim(), 0)
} else {
DenseMat::from_rows(&images).transpose()
};
unit_factorizations(&system, &field).expect("the map approximates")
})
.collect()
}
fn left_kernel_of(f: &Morphism, endo: &EndoAlgebra) -> DenseMat {
let space = HomSpace::new(f.source(), f.target()).unwrap();
let field = f.source().field();
let rows: Vec<Vec<Fp>> = endo
.basis()
.iter()
.map(|e| space.coords(&f.then(e).unwrap()).unwrap())
.collect();
row_relations(&rows, space.dim(), &field)
}
#[test]
fn left_approximations_by_the_projectives_verify_on_every_fixture() {
let mut checked = 0;
for field in fields() {
for (name, algebra) in fixtures(field) {
let generators = projectives(&algebra);
for x in test_modules(&algebra) {
let context = format!("{name} over F_{}", field.modulus());
let left = left_approximation(&x, &generators)
.unwrap_or_else(|e| panic!("{context}: left: {e}"));
assert!(left.verify(), "{context}: left verify");
assert!(left_property_holds(&left), "{context}: left property");
checked += 1;
}
}
}
assert_eq!(checked, 84);
}
#[test]
fn left_approximations_by_the_injectives_verify_on_every_fixture() {
for field in fields() {
for (name, algebra) in fixtures(field) {
let generators = injectives(&algebra);
for x in test_modules(&algebra) {
let context = format!("{name} over F_{}", field.modulus());
let left = left_approximation(&x, &generators)
.unwrap_or_else(|e| panic!("{context}: left: {e}"));
assert!(left.verify(), "{context}: left verify");
assert!(left_property_holds(&left), "{context}: left property");
}
}
}
}
#[test]
fn every_kernel_row_sits_inside_the_radical_of_the_endomorphism_algebra() {
for field in fields() {
for (name, algebra) in fixtures(field) {
let generators = projectives(&algebra);
for x in test_modules(&algebra) {
let left = left_approximation(&x, &generators).unwrap();
let endo = EndoAlgebra::new(left.map().target());
let kernel = left_kernel_of(left.map(), &endo);
assert_eq!(&kernel, left.kernel_basis(), "{name}: recomputed K_f");
for r in 0..kernel.rows() {
assert!(
endo.in_radical(kernel.row(r)),
"{name} over F_{}: row {r} outside rad End(B)",
field.modulus()
);
}
}
}
}
}
#[test]
fn a_left_approximation_with_no_maps_available_is_the_zero_map_into_zero() {
for field in fields() {
let algebra = linear_an(2, field);
let s0 = Module::simple(&algebra, 0);
let generators = projectives(&algebra);
for n in &generators {
assert_eq!(HomSpace::new(&s0, n).unwrap().dim(), 0);
}
let a = left_approximation(&s0, &generators).unwrap();
assert!(a.slots().is_empty());
assert!(a.map().target().is_zero());
assert!(a.map().is_zero());
assert_eq!(a.kernel_basis().rows(), 0);
assert!(a.verify());
assert!(left_property_holds(&a));
}
}
#[test]
fn a_module_inside_add_n_gets_a_split_monomorphism() {
for field in fields() {
let algebra = linear_an(2, field);
let generators = projectives(&algebra);
let x = generators[1].clone();
assert_eq!(HomSpace::new(&x, &generators[0]).unwrap().dim(), 1);
let a = left_approximation(&x, &generators).unwrap();
assert_eq!(a.multiplicity(0), 0, "P_0 is redundant here");
assert_eq!(a.slots(), &[1]);
assert!(a.map().is_isomorphism());
assert_eq!(kernel(a.map()).0.total_dim(), 0);
for (i, n) in generators.iter().enumerate() {
assert_eq!(HomSpace::new(&x, n).unwrap().dim(), 1);
assert_eq!(HomSpace::new(a.map().target(), n).unwrap().dim(), 1);
assert_eq!(a.factorization(i, 0), &[field.one()], "summand {i}");
}
assert!(a.verify());
assert!(left_property_holds(&a));
}
}
#[test]
fn an_empty_add_generator_list_gives_the_zero_map_into_zero() {
for field in fields() {
for (name, algebra) in fixtures(field) {
let x = Module::projective(&algebra, 0);
let left = left_approximation(&x, &[]).unwrap();
assert!(left.summands().is_empty(), "{name}");
assert!(left.slots().is_empty(), "{name}");
assert!(left.map().target().is_zero(), "{name}");
assert!(left.verify(), "{name}");
}
}
}
#[test]
fn a_truncated_polynomial_module_needs_one_copy_where_the_fp_count_says_two() {
for field in fields() {
let algebra = truncated_poly(3, field).unwrap();
let p = Module::projective(&algebra, 0);
let mut action = DenseMat::zero(2, 2);
action.set(0, 1, field.one());
let m = Module::new(algebra.clone(), vec![2], vec![action]).unwrap();
assert_eq!(HomSpace::new(&m, &p).unwrap().dim(), 2);
let a = left_approximation(&m, std::slice::from_ref(&p)).unwrap();
assert_eq!(a.slots(), &[0], "one copy of P, not two");
assert_eq!(a.map().target().dim_vector(), &[3]);
assert_eq!(
kernel(a.map()).0.total_dim(),
0,
"the envelope is injective"
);
let endo = EndoAlgebra::new(a.map().target());
assert_eq!(endo.dim(), 3);
assert_eq!(endo.radical_dim(), 2);
assert_eq!(a.kernel_basis().rows(), 1);
assert_eq!(a.kernel_basis().row(0), endo.radical_basis().row(0));
assert_eq!(a.radical_coordinates(0), &[field.one(), Fp::ZERO]);
assert!(a.verify());
assert!(left_property_holds(&a));
}
}
#[test]
fn a_residue_degree_three_summand_gets_one_copy_where_an_fp_basis_gives_three() {
let field = f2();
let algebra = kronecker(2, field);
let identity3 = DenseMat::identity(3);
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, vec![3, 3], vec![identity3, companion]).unwrap();
let certified = IndecomposableModule::new(&w).unwrap();
assert_eq!(certified.residue_degree(), 3, "the fixture must have d = 3");
let fp_dim = HomSpace::new(&w, &w).unwrap().dim();
assert_eq!(fp_dim, 3);
let left = left_approximation(&w, std::slice::from_ref(&w)).unwrap();
assert_eq!(left.multiplicity(0), fp_dim / 3);
assert_eq!(left.multiplicity(0), 1);
assert_eq!(left.map().target().dim_vector(), &[3, 3]);
assert!(left.map().is_isomorphism());
assert!(left.verify());
assert!(left_property_holds(&left));
}
#[test]
fn a_padded_approximation_is_rejected_by_the_minimality_check() {
let mut cases = 0;
for field in fields() {
for (name, algebra) in fixtures(field) {
let generators = projectives(&algebra);
for x in test_modules(&algebra) {
let a = left_approximation(&x, &generators).unwrap();
let context = format!("{name} over F_{}", field.modulus());
let endo = EndoAlgebra::new(a.map().target());
assert!(
radical_coordinates(&endo, a.kernel_basis()).is_ok(),
"{context}: the genuine approximation must be minimal"
);
let extra = &generators[0];
let mut parts: Vec<&Module> = a
.slots()
.iter()
.map(|&i| a.summands()[i].module())
.collect();
parts.push(extra);
let (padded, inclusions, projections) = direct_sum(&parts);
let mut padded_map = zero_morphism(&x, &padded).unwrap();
for (c, &i) in a.slots().iter().enumerate() {
let component = a
.map()
.then(&a.projections()[c])
.expect("the block projection follows f");
assert_eq!(
component.target().dim_vector(),
a.summands()[i].module().dim_vector()
);
let block = component.then(&inclusions[c]).unwrap();
padded_map = add_morphisms(&padded_map, &block);
}
let padded_endo = EndoAlgebra::new(&padded);
let padded_kernel = left_kernel_of(&padded_map, &padded_endo);
assert!(
radical_coordinates(&padded_endo, &padded_kernel).is_err(),
"{context}: the padded approximation must fail minimality"
);
let last = projections.len() - 1;
assert!(
padded_map.then(&projections[last]).unwrap().is_zero(),
"{context}: the extra component is zero"
);
cases += 1;
}
}
}
assert_eq!(cases, 84);
}
#[test]
fn a_padded_approximation_reports_the_kernel_row_outside_the_radical() {
for field in fields() {
let algebra = linear_an(2, field);
let x = Module::projective(&algebra, 0);
let generators = projectives(&algebra);
let a = left_approximation(&x, &generators).unwrap();
assert_eq!(a.slots(), &[0], "the fixture uses one copy of P_0");
let summands = certify(&generators).unwrap();
let mut slots = a.slots().to_vec();
slots.push(a.slots()[0]);
let (padded, inclusions, _) = slot_sum(&x, &summands, &slots);
let mut padded_map = zero_morphism(&x, &padded).unwrap();
for (c, block) in inclusions.iter().enumerate().take(a.slots().len()) {
let component = a.map().then(&a.projections()[c]).unwrap();
padded_map = add_morphisms(&padded_map, &component.then(block).unwrap());
}
let endo = EndoAlgebra::new(&padded);
assert_eq!(endo.dim(), 4);
assert_eq!(endo.radical_dim(), 0);
let kernel = left_kernel_of(&padded_map, &endo);
assert_eq!(kernel.rows(), 2);
let defect = radical_coordinates(&endo, &kernel)
.map_err(|row| ApproxDefect::KernelOutsideRadical {
row,
kernel_dim: kernel.rows(),
radical_dim: endo.radical_dim(),
})
.unwrap_err();
assert_eq!(
defect,
ApproxDefect::KernelOutsideRadical {
row: 0,
kernel_dim: 2,
radical_dim: 0,
},
"over F_{}",
field.modulus()
);
}
}
#[test]
fn verify_rejects_a_witness_built_around_a_padded_map() {
let field = f5();
let algebra = linear_an(3, field);
let x = Module::projective(&algebra, 0);
let generators = projectives(&algebra);
let a = left_approximation(&x, &generators).unwrap();
assert_eq!(a.slots(), &[0], "the fixture uses one copy of P_0");
let summands = certify(&generators).unwrap();
let mut slots = a.slots().to_vec();
slots.push(a.slots()[0]);
let (padded, inclusions, projections) = slot_sum(&x, &summands, &slots);
let mut padded_map = zero_morphism(&x, &padded).unwrap();
for (c, block) in inclusions.iter().enumerate().take(a.slots().len()) {
let component = a.map().then(&a.projections()[c]).unwrap();
padded_map = add_morphisms(&padded_map, &component.then(block).unwrap());
}
let factorizations = left_factorizations(&padded_map, &summands);
let endo = EndoAlgebra::new(&padded);
let kernel = left_kernel_of(&padded_map, &endo);
let radical: Vec<Vec<Fp>> = (0..kernel.rows())
.map(|r| {
endo.radical_basis()
.transpose()
.solve(kernel.row(r), &field)
.unwrap_or_else(|| vec![Fp::ZERO; endo.radical_dim()])
})
.collect();
let witness = MinimalLeftApproximation {
map: padded_map,
summands,
slots,
inclusions,
projections,
factorizations,
kernel,
radical,
};
assert!(!witness.verify(), "a padded map must not verify");
}
#[test]
fn a_decomposable_add_generator_is_rejected_with_its_position() {
let field = f5();
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let (sum, _, _) = direct_sum(&[&p0, &p0]);
let x = Module::simple(&algebra, 0);
assert_eq!(
left_approximation(&x, &[p0.clone(), sum]).unwrap_err(),
ApproxError::SummandNotIndecomposable {
index: 1,
reason: IndecError::Decomposable { summands: 2 },
}
);
assert_eq!(
left_approximation(&x, &[Module::zero(&algebra)]).unwrap_err(),
ApproxError::SummandNotIndecomposable {
index: 0,
reason: IndecError::Zero,
}
);
}
#[test]
fn an_isomorphic_repeat_in_the_generator_list_is_rejected() {
let field = f2();
let algebra = linear_an(3, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let x = Module::simple(&algebra, 2);
assert_eq!(
left_approximation(&x, &[p0.clone(), p1, p0]).unwrap_err(),
ApproxError::RepeatedSummand {
first: 0,
second: 2
}
);
}
#[test]
fn a_generator_from_another_algebra_is_a_typed_hom_error() {
let x = Module::simple(&linear_an(2, f5()), 0);
let other = Module::simple(&linear_an(2, f5()), 0);
assert_eq!(
left_approximation(&x, std::slice::from_ref(&other)).unwrap_err(),
ApproxError::Hom(HomError::DifferentAlgebras)
);
}
#[test]
fn error_display_names_the_position_and_the_reason() {
assert_eq!(
ApproxError::RepeatedSummand {
first: 0,
second: 2
}
.to_string(),
"add-generators 0 and 2 are isomorphic; give one module per class"
);
assert_eq!(
ApproxError::Defect(ApproxDefect::GeneratorGrowth {
summand: 1,
growth: 2,
residue_degree: 3,
})
.to_string(),
"a generator for summand 1 raised the span by 2, not by the residue degree 3; \
crate defect"
);
}
#[test]
fn a_projective_approximated_by_the_projectives_gets_the_identity() {
for field in fields() {
let algebra = commutative_square(field);
let p0 = Module::projective(&algebra, 0);
let a = left_approximation(&p0, &projectives(&algebra)).unwrap();
assert_eq!(a.slots(), &[0]);
assert!(a.map().is_isomorphism());
assert_eq!(a.kernel_basis().rows(), 0);
assert!(a.verify());
}
}
}