use std::sync::Arc;
use crate::approx::{ApproxError, MinimalLeftApproximation, left_approximation};
use crate::basic::{
AddClosureWitness, BasicDecomposition, BasicError, ProjectiveSupport, SupportPairIsoOutcome,
SupportPairObstruction, pair_iso,
};
use crate::context::VerificationContext;
use crate::decompose::{Certificate, decompose, direct_sum_or_zero};
use crate::field::Fp;
use crate::hom::{HomError, Morphism, cokernel, hom};
use crate::indec::{IndecError, IndecomposableModule};
use crate::iso::indecomposable_iso;
use crate::linalg::DenseMat;
use crate::module::{Module, same_representation};
use crate::profile::{Site, hit};
use crate::supporttau::{
AlmostCompleteClassification, AlmostCompletePair, PairRejection, SupportTauError,
SupportTauTiltingClassification, SupportTauTiltingPair,
};
use crate::taurigid::TauCache;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Endpoint {
Source,
Target,
}
display_error! { Endpoint {
Self::Source => "source";
Self::Target => "target";
} }
#[derive(Clone, Debug)]
pub enum MutationDefect {
AlmostCompleteRejected(PairRejection),
TargetRejected(PairRejection),
DroppedVertexCount {
dropped: Vec<u32>,
},
CokernelNonzero {
dim_vector: Vec<usize>,
},
CokernelZero,
CokernelSummandsDiffer {
summand: usize,
},
ReplacementRepeatsSummand {
summand: usize,
},
AddClosureMissing {
endpoint: Endpoint,
},
ProjectiveSupportNotExtended {
endpoint: Endpoint,
},
EndpointsIsomorphic,
}
display_error! { error MutationDefect {
Self::AlmostCompleteRejected(rejection) => "dropping the slot summand left condition {} unmet: {rejection}; crate defect", rejection.condition();
Self::TargetRejected(rejection) => "the built pair left condition {} unmet: {rejection}; crate defect", rejection.condition();
Self::DroppedVertexCount { dropped } => "dropping the slot summand lost {} vertices, not one; crate defect", dropped.len();
Self::CokernelNonzero { dim_vector } => "the approximation has cokernel of dimension vector {dim_vector:?} where the \
support test says zero; crate defect";
Self::CokernelZero => "the approximation has zero cokernel where the support test says nonzero; \
crate defect";
Self::CokernelSummandsDiffer { summand } => "cokernel summand {summand} is not isomorphic to the first one; crate defect";
Self::ReplacementRepeatsSummand { summand } => "the cokernel summand repeats summand {summand} of the module part; crate defect";
Self::AddClosureMissing { endpoint } => "the {endpoint} pair does not contain U; crate defect";
Self::ProjectiveSupportNotExtended { endpoint } => "the {endpoint} projective support does not contain Q; crate defect";
Self::EndpointsIsomorphic => "the two completions are isomorphic; crate defect";
} }
#[derive(Clone, Debug)]
pub enum MutationError {
SlotOutOfRange {
slot: usize,
summands: usize,
},
SummandIndexCount {
indices: usize,
summands: usize,
},
Basic(BasicError),
SupportTau(SupportTauError),
Approx(ApproxError),
Hom(HomError),
Indec(IndecError),
Defect(MutationDefect),
}
display_error! { MutationError {
Self::SlotOutOfRange { slot, summands } => "slot {slot} is out of range, the module part has {summands} summands";
Self::SummandIndexCount { indices, summands } => "{indices} summand indices for {summands} summands";
Self::Basic(error) => "basic layer: {error}";
Self::SupportTau(error) => "support tau-tilting layer: {error}";
Self::Approx(error) => "approximation layer: {error}";
Self::Hom(error) => "hom: {error}";
Self::Indec(error) => "cokernel summand: {error}";
Self::Defect(defect) => "{defect}";
} }
error_source!(MutationError {
Self::Basic(error) => Some(error),
Self::SupportTau(error) => Some(error),
Self::Approx(error) => Some(error),
Self::Hom(error) => Some(error),
Self::Indec(error) => Some(error),
Self::Defect(defect) => Some(defect),
Self::SlotOutOfRange { .. } | Self::SummandIndexCount { .. } => None,
});
from_variants!(MutationError {
BasicError => Basic,
SupportTauError => SupportTau,
HomError => Hom,
});
fn defect(defect: MutationDefect) -> MutationError {
MutationError::Defect(defect)
}
fn support(m: &Module) -> Vec<u32> {
m.dim_vector()
.iter()
.enumerate()
.filter_map(|(v, &d)| (d > 0).then_some(v as u32))
.collect()
}
fn is_direct_sum(m: &Module, parts: &[Module]) -> bool {
same_representation(&direct_sum_or_zero(m.algebra(), parts).0, m)
}
fn trace_dims(maps: &[Morphism], x: &Module) -> Vec<usize> {
let field = x.field();
(0..x.algebra().quiver().num_vertices())
.map(|v| {
if x.dim_at(v) == 0 {
return 0;
}
let rows: Vec<Vec<Fp>> = maps
.iter()
.flat_map(|f| {
let block = f.map_at(v);
(0..block.rows()).map(move |r| block.row(r).to_vec())
})
.collect();
DenseMat::from_rows(&rows).rank(&field)
})
.collect()
}
fn is_cokernel(f: &Morphism, g: &Morphism) -> bool {
verify_guard!(g.source().ptr_eq(f.target()));
let_or_false!(Ok(composite) = f.then(g));
verify_guard!(composite.is_zero());
let field = f.source().field();
(0..f.source().algebra().quiver().num_vertices()).all(|v| {
let dim_y = g.target().dim_at(v);
g.map_at(v).rank(&field) == dim_y
&& dim_y + f.map_at(v).rank(&field) == f.target().dim_at(v)
})
}
#[derive(Clone, Debug)]
pub struct FacWitness {
module: Module,
summands: Vec<Module>,
summand: Module,
maps: Vec<Morphism>,
}
impl FacWitness {
accessor_methods! {
pub module() -> &Module = |this| &this.module;
pub summands() -> &[Module] = |this| &this.summands;
pub summand() -> &Module = |this| &this.summand;
pub maps() -> &[Morphism] = |this| &this.maps;
pub image_dims() -> Vec<usize> = |this| trace_dims(&this.maps, &this.summand);
}
pub fn verify(&self) -> bool {
hit(Site::FacWitnessVerify);
is_direct_sum(&self.module, &self.summands)
&& self
.maps
.iter()
.all(|f| f.source().ptr_eq(&self.module) && f.target().ptr_eq(&self.summand))
&& trace_dims(&self.maps, &self.summand) == self.summand.dim_vector()
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ExchangeShape {
MovesToProjective {
vertex: u32,
},
ReplacedByModule {
multiplicity: usize,
},
}
#[derive(Debug)]
pub struct MutationWitness {
slot: usize,
exchanged: Module,
almost_complete: AlmostCompletePair,
source_module: Module,
source_projective: Vec<u32>,
source_extension: AddClosureWitness,
target_module: Module,
target_projective: Vec<u32>,
target_extension: AddClosureWitness,
distinct: SupportPairObstruction,
approximation: MinimalLeftApproximation,
exchange: Morphism,
shape: ExchangeShape,
replacement: Option<Module>,
}
impl MutationWitness {
accessor_methods! {
pub slot() -> usize = |this| this.slot;
pub exchanged() -> &Module = |this| &this.exchanged;
pub almost_complete() -> &AlmostCompletePair = |this| &this.almost_complete;
pub source_extension() -> &AddClosureWitness = |this| &this.source_extension;
pub target_extension() -> &AddClosureWitness = |this| &this.target_extension;
pub distinct() -> &SupportPairObstruction = |this| &this.distinct;
pub approximation() -> &MinimalLeftApproximation = |this| &this.approximation;
pub exchange() -> &Morphism = |this| &this.exchange;
pub shape() -> &ExchangeShape = |this| &this.shape;
pub replacement() -> Option<&Module> = |this| this.replacement.as_ref();
pub source_module() -> &Module = |this| &this.source_module;
pub source_projective() -> &[u32] = |this| &this.source_projective;
pub target_module() -> &Module = |this| &this.target_module;
pub target_projective() -> &[u32] = |this| &this.target_projective;
}
verify_methods!(pub(crate), { hit(Site::MutationWitnessVerify); },
|self, context| {
verify_guard!(self.almost_complete.verify_with_context(context));
let u = self.almost_complete.module();
let algebra = u.module().algebra();
verify_guard!(Arc::ptr_eq(algebra, self.source_module.algebra())
&& Arc::ptr_eq(algebra, self.target_module.algebra()));
let_or_false!((Ok(source_dec), Ok(target_dec)) = (
BasicDecomposition::new_with_context(&self.source_module, context),
BasicDecomposition::new_with_context(&self.target_module, context),
));
let_or_false!((Ok(source_proj), Ok(target_proj)) = (
ProjectiveSupport::new(algebra, &self.source_projective),
ProjectiveSupport::new(algebra, &self.target_projective),
));
verify_guard!(self.almost_complete.projective().vertices() == source_proj.vertices()
&& extends(u, &source_dec, &self.source_extension));
verify_guard!(self
.almost_complete
.projective()
.vertices()
.iter()
.all(|&v| target_proj.contains(v))
&& extends(u, &target_dec, &self.target_extension));
verify_guard!(matches!(
context.pair_iso_for(&source_dec, &source_proj, &target_dec, &target_proj),
Ok(outcome)
if matches!(outcome.as_ref(), SupportPairIsoOutcome::NotIsomorphic(found) if found == &self.distinct)
));
let_or_false!((Ok(fresh_dec), Ok(fresh_proj)) = (
BasicDecomposition::new_with_context(&self.target_module, context),
ProjectiveSupport::new(algebra, &self.target_projective),
));
matches!(
SupportTauTiltingPair::classify_with_context(fresh_dec, fresh_proj, context),
Ok(classification) if classification.is_pair()
) && self.exchange_holds(
u,
&source_dec,
&target_dec,
&source_proj,
&target_proj,
context,
)
});
fn exchange_holds(
&self,
u: &BasicDecomposition,
source_dec: &BasicDecomposition,
target_dec: &BasicDecomposition,
source_proj: &ProjectiveSupport,
target_proj: &ProjectiveSupport,
context: &VerificationContext,
) -> bool {
let f = self.approximation.map();
verify_guard!(f.source().ptr_eq(&self.exchanged));
verify_guard!(
self.approximation.summands().len() == u.len()
&& self
.approximation
.summands()
.iter()
.zip(u.summands())
.all(|(a, b)| a.module().ptr_eq(b.module()))
);
verify_guard!(
self.approximation.verify_with_context(context) && is_cokernel(f, &self.exchange)
);
let_or_false!(Some(slot_summand) = source_dec.summands().get(self.slot));
verify_guard!(
indecomposable_iso(slot_summand.module(), &self.exchanged, slot_summand.endo())
.is_some()
);
let y = self.exchange.target();
match &self.shape {
ExchangeShape::MovesToProjective { vertex } => {
let mut expected = source_proj.vertices().to_vec();
expected.push(*vertex);
expected.sort_unstable();
y.is_zero()
&& self.replacement.is_none()
&& !source_proj.contains(*vertex)
&& target_proj.contains(*vertex)
&& expected == target_proj.vertices()
&& target_dec.len() == u.len()
}
ExchangeShape::ReplacedByModule { multiplicity } => {
let_or_false!(Some(replacement) = &self.replacement);
verify_guard!(!y.is_zero() && source_proj.vertices() == target_proj.vertices());
verify_guard!(target_dec.len() == u.len() + 1);
let split = context.decompose_for(y);
verify_guard!(
split.summands().len() == *multiplicity
&& !split
.certificates()
.iter()
.any(|c| *c != Certificate::Indecomposable)
);
let_or_false!(
Ok(y1) = IndecomposableModule::new_with_context(replacement, context)
);
verify_guard!(
split
.summands()
.iter()
.all(|s| indecomposable_iso(y1.module(), s, y1.endo()).is_some())
);
verify_guard!(
!source_dec.summands().iter().any(|s| indecomposable_iso(
y1.module(),
s.module(),
y1.endo()
)
.is_some())
);
target_dec
.summands()
.iter()
.any(|s| indecomposable_iso(y1.module(), s.module(), y1.endo()).is_some())
}
}
}
}
fn extends(u: &BasicDecomposition, whole: &BasicDecomposition, stored: &AddClosureWitness) -> bool {
let_or_false!(Ok(Some(live)) = AddClosureWitness::new(u, whole));
verify_guard!(
live.matches().len() == stored.matches().len()
&& stored.module().ptr_eq(u.module())
&& stored.target().ptr_eq(whole.module())
);
let mut seen: Vec<usize> = stored.matches().iter().map(|m| m.target_index()).collect();
seen.sort_unstable();
let distinct = seen.windows(2).all(|w| w[0] != w[1]);
distinct && stored.verify()
}
#[derive(Debug)]
pub struct Mutation {
slot: usize,
target: SupportTauTiltingPair,
witness: MutationWitness,
}
impl Mutation {
accessor_methods! {
pub slot() -> usize = |this| this.slot;
pub target() -> &SupportTauTiltingPair = |this| &this.target;
}
#[inline]
pub fn into_target(self) -> SupportTauTiltingPair {
self.target
}
accessor_methods! {
pub witness() -> &MutationWitness = |this| &this.witness;
pub shape() -> &ExchangeShape = |this| this.witness.shape();
}
verify_methods!(pub(crate), { hit(Site::MutationVerify); },
|self, context| {
self.slot == self.witness.slot()
&& self
.target
.module()
.module()
.ptr_eq(self.witness.target_module())
&& self.target.projective().vertices() == self.witness.target_projective()
&& self.witness.verify_with_context(context)
&& self.target.verify_with_context(context)
});
}
#[derive(Debug)]
pub enum SlotOutcome {
NoLeftMutation(FacWitness),
LeftMutation(Box<Mutation>),
}
impl SlotOutcome {
binary_outcome_accessors!(
LeftMutation,
NoLeftMutation,
mutation -> Mutation = |value| value.as_ref(),
fac_witness -> FacWitness = |value| value,
is_left_mutation,
into_mutation -> Mutation = |value| *value;
flag = "Whether the slot admits a left mutation.";
positive = "The mutation, or `None` when the slot admits no left mutation.";
negative = "The `Fac` witness, or `None` when the slot admits a left mutation.";
into = "The mutation by value, or `None` when the slot admits no left mutation.";
);
}
struct BuiltTarget {
decomposition: BasicDecomposition,
vertices: Vec<u32>,
shape: ExchangeShape,
replacement: Option<Module>,
}
fn build_target(
pair: &SupportTauTiltingPair,
u_dec: &BasicDecomposition,
y: &Module,
dropped: &[u32],
) -> Result<BuiltTarget, MutationError> {
if let Some((&vertex, rest)) = dropped.split_first() {
if !rest.is_empty() {
return Err(defect(MutationDefect::DroppedVertexCount {
dropped: dropped.to_vec(),
}));
}
if !y.is_zero() {
return Err(defect(MutationDefect::CokernelNonzero {
dim_vector: y.dim_vector().to_vec(),
}));
}
let mut vertices = pair.projective().vertices().to_vec();
vertices.push(vertex);
vertices.sort_unstable();
return Ok(BuiltTarget {
decomposition: u_dec.clone(),
vertices,
shape: ExchangeShape::MovesToProjective { vertex },
replacement: None,
});
}
if y.is_zero() {
return Err(defect(MutationDefect::CokernelZero));
}
let split = decompose(y);
for certificate in split.certificates() {
if let Certificate::Undetermined { attempts } = certificate {
return Err(MutationError::Basic(BasicError::CertificationBlocked {
reason: format!(
"a cokernel summand stayed undetermined after {attempts} split attempts"
),
}));
}
}
let y1 =
IndecomposableModule::from_endo(split.endos()[0].clone()).map_err(MutationError::Indec)?;
for (position, other) in split.summands().iter().enumerate().skip(1) {
if indecomposable_iso(y1.module(), other, y1.endo()).is_none() {
return Err(defect(MutationDefect::CokernelSummandsDiffer {
summand: position,
}));
}
}
for (position, other) in pair.module().summands().iter().enumerate() {
if indecomposable_iso(y1.module(), other.module(), y1.endo()).is_some() {
return Err(defect(MutationDefect::ReplacementRepeatsSummand {
summand: position,
}));
}
}
let replacement = y1.module().clone();
Ok(BuiltTarget {
decomposition: u_dec.with_new_summand(&y1).map_err(MutationError::Basic)?,
vertices: pair.projective().vertices().to_vec(),
shape: ExchangeShape::ReplacedByModule {
multiplicity: split.summands().len(),
},
replacement: Some(replacement),
})
}
pub fn mutate_at(pair: &SupportTauTiltingPair, slot: usize) -> Result<SlotOutcome, MutationError> {
let count = pair.module().len();
let indices: Vec<usize> = (0..count).collect();
mutate_at_with_cache(pair, slot, &indices, count, None)
}
pub fn mutate_at_with_cache(
pair: &SupportTauTiltingPair,
slot: usize,
summand_indices: &[usize],
fresh_index: usize,
cache: Option<&mut TauCache>,
) -> Result<SlotOutcome, MutationError> {
let m = pair.module();
if slot >= m.len() {
return Err(MutationError::SlotOutOfRange {
slot,
summands: m.len(),
});
}
if summand_indices.len() != m.len() {
return Err(MutationError::SummandIndexCount {
indices: summand_indices.len(),
summands: m.len(),
});
}
let algebra = m.module().algebra().clone();
let x = m.summands()[slot].module().clone();
let u_dec = m.without(slot).expect("the slot is a summand position");
let u = u_dec.module().clone();
let maps = hom(&u, &x)?;
if trace_dims(&maps, &x) == x.dim_vector() {
return Ok(SlotOutcome::NoLeftMutation(FacWitness {
module: u,
summands: u_dec
.summands()
.iter()
.map(|s| s.module().clone())
.collect(),
summand: x,
maps,
}));
}
let u_indices: Vec<usize> = summand_indices
.iter()
.enumerate()
.filter(|(i, _)| *i != slot)
.map(|(_, &index)| index)
.collect();
let u_summands: Vec<Module> = u_dec
.summands()
.iter()
.map(|s| s.module().clone())
.collect();
let mut owned = TauCache::new();
let cache = cache.unwrap_or(&mut owned);
let q = ProjectiveSupport::new(&algebra, pair.projective().vertices())?;
let almost_complete = match AlmostCompletePair::classify_with_cache(
u_dec.clone(),
q,
&u_indices,
Some(&mut *cache),
)? {
AlmostCompleteClassification::Pair(almost) => almost,
AlmostCompleteClassification::Rejected(rejection) => {
return Err(defect(MutationDefect::AlmostCompleteRejected(rejection)));
}
};
let approximation = left_approximation(&x, &u_summands).map_err(MutationError::Approx)?;
let (y, exchange) = cokernel(approximation.map());
let dropped: Vec<u32> = support(m.module())
.into_iter()
.filter(|&v| u.dim_at(v) == 0)
.collect();
let built = build_target(pair, &u_dec, &y, &dropped)?;
let mut target_indices = u_indices.clone();
target_indices.extend(built.replacement.is_some().then_some(fresh_index));
let target_proj = ProjectiveSupport::new(&algebra, &built.vertices)?;
let target = match SupportTauTiltingPair::classify_with_cache(
built.decomposition,
target_proj,
&target_indices,
Some(&mut *cache),
)? {
SupportTauTiltingClassification::Pair(target) => target,
SupportTauTiltingClassification::Rejected(rejection) => {
return Err(defect(MutationDefect::TargetRejected(rejection)));
}
};
let Some(source_extension) = AddClosureWitness::new(almost_complete.module(), m)? else {
return Err(defect(MutationDefect::AddClosureMissing {
endpoint: Endpoint::Source,
}));
};
let Some(target_extension) = AddClosureWitness::new(almost_complete.module(), target.module())?
else {
return Err(defect(MutationDefect::AddClosureMissing {
endpoint: Endpoint::Target,
}));
};
if almost_complete.projective().vertices() != pair.projective().vertices() {
return Err(defect(MutationDefect::ProjectiveSupportNotExtended {
endpoint: Endpoint::Source,
}));
}
if !almost_complete
.projective()
.vertices()
.iter()
.all(|&v| target.projective().contains(v))
{
return Err(defect(MutationDefect::ProjectiveSupportNotExtended {
endpoint: Endpoint::Target,
}));
}
let distinct = match pair_iso(m, &pair.projective(), target.module(), &target.projective())? {
SupportPairIsoOutcome::NotIsomorphic(obstruction) => obstruction,
SupportPairIsoOutcome::Isomorphic(_) => {
return Err(defect(MutationDefect::EndpointsIsomorphic));
}
};
let witness = MutationWitness {
slot,
exchanged: x,
almost_complete,
source_module: m.module().clone(),
source_projective: pair.projective().vertices().to_vec(),
source_extension,
target_module: target.module().module().clone(),
target_projective: target.projective().vertices().to_vec(),
target_extension,
distinct,
approximation,
exchange,
shape: built.shape,
replacement: built.replacement,
};
Ok(SlotOutcome::LeftMutation(Box::new(Mutation {
slot,
target,
witness,
})))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{Algebra, linear_an, truncated_poly};
use crate::dynkin::{DynkinType, dynkin_quiver};
use crate::field::PrimeField;
use crate::quiver::Quiver;
fn assemble(algebra: &Arc<Algebra>, parts: &[&Module]) -> Module {
direct_sum_or_zero(algebra, parts.iter().copied()).0
}
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 semisimple(n: u32, field: PrimeField) -> Arc<Algebra> {
path_algebra(
Quiver::new(n, &[]).expect("no arrow is out of range"),
field,
)
}
fn d4(field: PrimeField) -> Arc<Algebra> {
path_algebra(
dynkin_quiver(DynkinType::D(4)).expect("D_4 has a quiver"),
field,
)
}
fn pair_of(
algebra: &Arc<Algebra>,
parts: &[&Module],
projective: &[u32],
) -> SupportTauTiltingPair {
let module = assemble(algebra, parts);
let decomposition =
BasicDecomposition::new(&module).expect("the fixture module part is basic");
let support =
ProjectiveSupport::new(algebra, projective).expect("the fixture vertices are in range");
match SupportTauTiltingPair::classify(decomposition, support)
.expect("the fixture parts share one algebra")
{
SupportTauTiltingClassification::Pair(pair) => pair,
SupportTauTiltingClassification::Rejected(rejection) => panic!(
"the fixture is a pair, condition {} says otherwise: {rejection}",
rejection.condition()
),
}
}
fn regular_pair(algebra: &Arc<Algebra>) -> SupportTauTiltingPair {
let parts: Vec<Module> = (0..algebra.quiver().num_vertices())
.map(|v| Module::projective(algebra, v))
.collect();
let refs: Vec<&Module> = parts.iter().collect();
pair_of(algebra, &refs, &[])
}
fn slot_of(pair: &SupportTauTiltingPair, dim: &[usize]) -> usize {
let hits: Vec<usize> = pair
.module()
.summands()
.iter()
.enumerate()
.filter(|(_, s)| s.module().dim_vector() == dim)
.map(|(i, _)| i)
.collect();
assert_eq!(hits.len(), 1, "one summand of dimension vector {dim:?}");
hits[0]
}
fn sorted_dims(pair: &SupportTauTiltingPair) -> Vec<Vec<usize>> {
let mut dims = pair.module().dim_vectors();
dims.sort();
dims
}
fn left(pair: &SupportTauTiltingPair, dim: &[usize]) -> Mutation {
let slot = slot_of(pair, dim);
let outcome = mutate_at(pair, slot).expect("the fixture slot mutates");
let mutation = match outcome {
SlotOutcome::LeftMutation(mutation) => *mutation,
SlotOutcome::NoLeftMutation(_) => {
panic!("slot {slot} of dimension vector {dim:?} has a left mutation")
}
};
assert!(mutation.witness().verify(), "the witness recomputes");
assert!(mutation.verify(), "the mutation recomputes");
mutation
}
#[test]
fn mutation_witness_reuses_context_for_nested_approximation() {
let algebra = linear_an(2, f5());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let pair = pair_of(&algebra, &[&p0, &p1], &[]);
let mutation = left(&pair, &[1, 1]);
let context = VerificationContext::new();
assert!(mutation.witness().verify_with_context(&context));
let first_memo = context.memo_stats();
assert!(first_memo.1 > 0, "the first verification has memo misses");
assert!(mutation.witness().verify_with_context(&context));
let second_memo = context.memo_stats();
assert_eq!(second_memo.1, first_memo.1);
assert!(
second_memo.0 > first_memo.0,
"the second verification has memo hits"
);
}
fn no_left(pair: &SupportTauTiltingPair, dim: &[usize]) -> FacWitness {
let slot = slot_of(pair, dim);
match mutate_at(pair, slot).expect("the fixture slot classifies") {
SlotOutcome::NoLeftMutation(witness) => {
assert!(witness.verify(), "the Fac witness recomputes");
witness
}
SlotOutcome::LeftMutation(_) => {
panic!("slot {slot} of dimension vector {dim:?} has no left mutation")
}
}
}
fn assert_target(mutation: &Mutation, dims: &[&[usize]], projective: &[u32]) {
let mut expected: Vec<Vec<usize>> = dims.iter().map(|d| d.to_vec()).collect();
expected.sort();
assert_eq!(sorted_dims(mutation.target()), expected);
assert_eq!(mutation.target().projective().vertices(), projective);
}
#[test]
fn a2_pentagon_slot_by_slot() {
for field in fields() {
let algebra = linear_an(2, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let s0 = Module::simple(&algebra, 0);
let v1 = pair_of(&algebra, &[&p0, &p1], &[]);
let v2 = pair_of(&algebra, &[&p0, &s0], &[]);
let v3 = pair_of(&algebra, &[&s0], &[1]);
let v4 = pair_of(&algebra, &[&p1], &[0]);
let v5 = pair_of(&algebra, &[], &[0, 1]);
let at_p0 = left(&v1, &[1, 1]);
assert_target(&at_p0, &[&[0, 1]], &[0]);
assert_eq!(
*at_p0.shape(),
ExchangeShape::MovesToProjective { vertex: 0 }
);
assert!(at_p0.witness().approximation().map().target().is_zero());
let at_p1 = left(&v1, &[0, 1]);
assert_target(&at_p1, &[&[1, 1], &[1, 0]], &[]);
assert_eq!(
*at_p1.shape(),
ExchangeShape::ReplacedByModule { multiplicity: 1 }
);
assert_eq!(
at_p1.witness().replacement().map(|y| y.dim_vector()),
Some([1, 0].as_slice())
);
let v2_at_p0 = left(&v2, &[1, 1]);
assert_target(&v2_at_p0, &[&[1, 0]], &[1]);
assert_eq!(
*v2_at_p0.shape(),
ExchangeShape::MovesToProjective { vertex: 1 }
);
let fac = no_left(&v2, &[1, 0]);
assert_eq!(fac.image_dims(), [1, 0]);
assert_eq!(fac.maps().len(), 1);
let v3_at_s0 = left(&v3, &[1, 0]);
assert_target(&v3_at_s0, &[], &[0, 1]);
assert_eq!(
*v3_at_s0.shape(),
ExchangeShape::MovesToProjective { vertex: 0 }
);
let v4_at_p1 = left(&v4, &[0, 1]);
assert_target(&v4_at_p1, &[], &[0, 1]);
assert_eq!(
*v4_at_p1.shape(),
ExchangeShape::MovesToProjective { vertex: 1 }
);
assert_eq!(v5.module().len(), 0);
assert!(matches!(
mutate_at(&v5, 0),
Err(MutationError::SlotOutOfRange {
slot: 0,
summands: 0
})
));
}
}
#[test]
fn semisimple_two_vertex_cube() {
for field in fields() {
let algebra = semisimple(2, field);
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let top = pair_of(&algebra, &[&p0, &p1], &[]);
let left_side = pair_of(&algebra, &[&p1], &[0]);
let right_side = pair_of(&algebra, &[&p0], &[1]);
let bottom = pair_of(&algebra, &[], &[0, 1]);
let drop_p0 = left(&top, &[1, 0]);
assert_target(&drop_p0, &[&[0, 1]], &[0]);
assert_eq!(
*drop_p0.shape(),
ExchangeShape::MovesToProjective { vertex: 0 }
);
let drop_p1 = left(&top, &[0, 1]);
assert_target(&drop_p1, &[&[1, 0]], &[1]);
let down_left = left(&left_side, &[0, 1]);
assert_target(&down_left, &[], &[0, 1]);
let down_right = left(&right_side, &[1, 0]);
assert_target(&down_right, &[], &[0, 1]);
assert_eq!(bottom.module().len(), 0);
}
}
#[test]
fn linear_an_3_pinned_edges() {
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 s0 = Module::simple(&algebra, 0);
assert_eq!(Module::injective(&algebra, 1).dim_vector(), [1, 1, 0]);
let vertex_a = pair_of(&algebra, &[&p0, &s0, &p2], &[]);
let vertex_b = pair_of(&algebra, &[&p0, &p1, &p2], &[]);
let vertex_h = pair_of(&algebra, &[&s0, &p2], &[1]);
let vertex_k = pair_of(&algebra, &[&p2], &[0, 1]);
let vertex_m = pair_of(&algebra, &[&s0], &[1, 2]);
let b_at_p2 = left(&vertex_b, &[0, 0, 1]);
assert_target(&b_at_p2, &[&[1, 1, 1], &[0, 1, 1], &[0, 1, 0]], &[]);
assert_eq!(
*b_at_p2.shape(),
ExchangeShape::ReplacedByModule { multiplicity: 1 }
);
let b_at_p1 = left(&vertex_b, &[0, 1, 1]);
assert_target(&b_at_p1, &[&[1, 1, 1], &[0, 0, 1], &[1, 0, 0]], &[]);
let b_at_p0 = left(&vertex_b, &[1, 1, 1]);
assert_target(&b_at_p0, &[&[0, 1, 1], &[0, 0, 1]], &[0]);
assert_eq!(
*b_at_p0.shape(),
ExchangeShape::MovesToProjective { vertex: 0 }
);
let a_at_p2 = left(&vertex_a, &[0, 0, 1]);
assert_target(&a_at_p2, &[&[1, 1, 1], &[1, 0, 0], &[1, 1, 0]], &[]);
let fac = no_left(&vertex_a, &[1, 0, 0]);
assert_eq!(fac.image_dims(), [1, 0, 0]);
let a_at_p0 = left(&vertex_a, &[1, 1, 1]);
assert_target(&a_at_p0, &[&[1, 0, 0], &[0, 0, 1]], &[1]);
assert_eq!(
*a_at_p0.shape(),
ExchangeShape::MovesToProjective { vertex: 1 }
);
let h_at_p2 = left(&vertex_h, &[0, 0, 1]);
assert_target(&h_at_p2, &[&[1, 0, 0]], &[1, 2]);
let h_at_s0 = left(&vertex_h, &[1, 0, 0]);
assert_target(&h_at_s0, &[&[0, 0, 1]], &[0, 1]);
let k_at_p2 = left(&vertex_k, &[0, 0, 1]);
assert_target(&k_at_p2, &[], &[0, 1, 2]);
let m_at_s0 = left(&vertex_m, &[1, 0, 0]);
assert_target(&m_at_s0, &[], &[0, 1, 2]);
}
}
#[test]
fn every_slot_of_the_regular_pair_mutates() {
for field in fields() {
for algebra in [linear_an(3, field), d4(field)] {
let pair = regular_pair(&algebra);
assert_eq!(pair.module().len(), pair.summand_count());
for slot in 0..pair.module().len() {
let outcome = mutate_at(&pair, slot).expect("the regular pair mutates");
let mutation = match outcome {
SlotOutcome::LeftMutation(mutation) => *mutation,
SlotOutcome::NoLeftMutation(_) => {
panic!("slot {slot} of the regular pair has a left mutation")
}
};
assert!(mutation.witness().verify());
assert!(mutation.target().verify());
}
}
}
}
#[test]
fn truncated_poly_3_has_one_slot_to_the_zero_pair() {
for field in fields() {
let algebra = truncated_poly(3, field).expect("x^3 is admissible");
let pair = regular_pair(&algebra);
assert_eq!(pair.module().len(), 1);
let mutation = left(&pair, &[3]);
assert_target(&mutation, &[], &[0]);
assert_eq!(
*mutation.shape(),
ExchangeShape::MovesToProjective { vertex: 0 }
);
assert!(mutation.target().module().is_empty());
}
}
#[test]
fn one_cache_serves_several_mutations() {
let algebra = linear_an(3, f5());
let pair = regular_pair(&algebra);
let indices: Vec<usize> = (0..pair.module().len()).collect();
let mut cache = TauCache::new();
let mut hits = Vec::new();
for slot in 0..pair.module().len() {
let outcome = mutate_at_with_cache(
&pair,
slot,
&indices,
indices.len() + slot,
Some(&mut cache),
)
.expect("the regular pair mutates");
assert!(outcome.is_left_mutation());
hits.push(cache.hits());
}
assert!(hits[0] > 0, "the first call already reuses a translate");
assert!(
hits[2] > hits[0],
"later calls keep hitting the shared store, got {hits:?}"
);
assert!(cache.misses() > 0);
}
#[test]
fn a_swapped_target_fails_verification() {
let algebra = linear_an(2, f2());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let pair = pair_of(&algebra, &[&p0, &p1], &[]);
let at_p0 = left(&pair, &[1, 1]);
let at_p1 = left(&pair, &[0, 1]);
let mut tampered = at_p0.witness;
tampered.target_module = at_p1.witness.target_module.clone();
tampered.target_projective = at_p1.witness.target_projective.clone();
assert!(!tampered.verify());
}
#[test]
fn a_borrowed_approximation_fails_verification() {
let algebra = linear_an(2, f2());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let pair = pair_of(&algebra, &[&p0, &p1], &[]);
let at_p0 = left(&pair, &[1, 1]);
let at_p1 = left(&pair, &[0, 1]);
let mut tampered = at_p1.witness;
tampered.approximation = at_p0.witness.approximation;
assert!(!tampered.verify());
}
#[test]
fn a_target_equal_to_the_source_fails_verification() {
let algebra = linear_an(2, f2());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let pair = pair_of(&algebra, &[&p0, &p1], &[]);
let mut tampered = left(&pair, &[0, 1]).witness;
tampered.target_module = tampered.source_module.clone();
tampered.target_projective = tampered.source_projective.clone();
tampered.target_extension = tampered.source_extension.clone();
assert!(!tampered.verify());
}
#[test]
fn a_truncated_fac_witness_fails_verification() {
let algebra = linear_an(2, f2());
let p0 = Module::projective(&algebra, 0);
let s0 = Module::simple(&algebra, 0);
let pair = pair_of(&algebra, &[&p0, &s0], &[]);
let mut witness = no_left(&pair, &[1, 0]);
assert!(witness.verify());
witness.maps.pop();
assert!(!witness.verify());
}
#[test]
fn a_fac_witness_whose_summands_miss_u_fails_verification() {
let algebra = linear_an(3, f2());
let p0 = Module::projective(&algebra, 0);
let p2 = Module::projective(&algebra, 2);
let s0 = Module::simple(&algebra, 0);
let pair = pair_of(&algebra, &[&p0, &s0, &p2], &[]);
let mut witness = no_left(&pair, &[1, 0, 0]);
assert_eq!(witness.summands().len(), 2);
witness.summands.pop();
assert!(!witness.verify());
}
#[test]
fn a_mutation_with_another_slot_target_fails_verification() {
let algebra = linear_an(2, f2());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let pair = pair_of(&algebra, &[&p0, &p1], &[]);
let mut at_p0 = left(&pair, &[1, 1]);
let at_p1 = left(&pair, &[0, 1]);
at_p0.target = at_p1.target;
assert!(at_p0.witness.verify());
assert!(at_p0.target.verify());
assert!(!at_p0.verify());
}
#[test]
fn a_mutation_relabelled_to_another_slot_fails_verification() {
let algebra = linear_an(2, f2());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let pair = pair_of(&algebra, &[&p0, &p1], &[]);
let mut at_p0 = left(&pair, &[1, 1]);
let other = left(&pair, &[0, 1]);
assert_ne!(at_p0.slot, other.slot, "the two slots must differ");
at_p0.slot = other.slot;
assert!(at_p0.witness.verify());
assert!(at_p0.target.verify());
assert!(!at_p0.verify());
}
#[test]
fn the_source_pair_survives_a_mutation() {
let algebra = linear_an(2, f5());
let p0 = Module::projective(&algebra, 0);
let p1 = Module::projective(&algebra, 1);
let pair = pair_of(&algebra, &[&p0, &p1], &[]);
let _ = left(&pair, &[1, 1]);
assert!(pair.verify());
}
}