use std::fmt;
use std::sync::Arc;
use crate::approx::{ApproxError, MinimalLeftApproximation, left_approximation};
use crate::basic::{
AddClosureWitness, BasicDecomposition, BasicError, ProjectiveSupport, SupportPairIsoOutcome,
SupportPairObstruction, pair_iso,
};
use crate::decompose::{Certificate, decompose};
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, direct_sum};
use crate::quiver::ArrowId;
use crate::supporttau::{
AlmostCompleteClassification, AlmostCompletePair, PairRejection, SupportTauError,
SupportTauTiltingClassification, SupportTauTiltingPair,
};
use crate::taurigid::TauCache;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Endpoint {
Source,
Target,
}
impl fmt::Display for Endpoint {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Source => f.write_str("source"),
Self::Target => f.write_str("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,
}
impl fmt::Display for MutationDefect {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::AlmostCompleteRejected(rejection) => write!(
f,
"dropping the slot summand left condition {} unmet: {rejection}; crate defect",
rejection.condition()
),
Self::TargetRejected(rejection) => write!(
f,
"the built pair left condition {} unmet: {rejection}; crate defect",
rejection.condition()
),
Self::DroppedVertexCount { dropped } => write!(
f,
"dropping the slot summand lost {} vertices, not one; crate defect",
dropped.len()
),
Self::CokernelNonzero { dim_vector } => write!(
f,
"the approximation has cokernel of dimension vector {dim_vector:?} where the \
support test says zero; crate defect"
),
Self::CokernelZero => f.write_str(
"the approximation has zero cokernel where the support test says nonzero; \
crate defect",
),
Self::CokernelSummandsDiffer { summand } => write!(
f,
"cokernel summand {summand} is not isomorphic to the first one; crate defect"
),
Self::ReplacementRepeatsSummand { summand } => write!(
f,
"the cokernel summand repeats summand {summand} of the module part; crate defect"
),
Self::AddClosureMissing { endpoint } => {
write!(f, "the {endpoint} pair does not contain U; crate defect")
}
Self::ProjectiveSupportNotExtended { endpoint } => write!(
f,
"the {endpoint} projective support does not contain Q; crate defect"
),
Self::EndpointsIsomorphic => {
f.write_str("the two completions are isomorphic; crate defect")
}
}
}
}
impl std::error::Error for MutationDefect {}
#[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),
}
impl fmt::Display for MutationError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::SlotOutOfRange { slot, summands } => write!(
f,
"slot {slot} is out of range, the module part has {summands} summands"
),
Self::SummandIndexCount { indices, summands } => {
write!(f, "{indices} summand indices for {summands} summands")
}
Self::Basic(error) => write!(f, "basic layer: {error}"),
Self::SupportTau(error) => write!(f, "support tau-tilting layer: {error}"),
Self::Approx(error) => write!(f, "approximation layer: {error}"),
Self::Hom(error) => write!(f, "hom: {error}"),
Self::Indec(error) => write!(f, "cokernel summand: {error}"),
Self::Defect(defect) => write!(f, "{defect}"),
}
}
}
impl std::error::Error for MutationError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
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,
}
}
}
impl From<BasicError> for MutationError {
fn from(error: BasicError) -> MutationError {
MutationError::Basic(error)
}
}
impl From<SupportTauError> for MutationError {
fn from(error: SupportTauError) -> MutationError {
MutationError::SupportTau(error)
}
}
impl From<HomError> for MutationError {
fn from(error: HomError) -> MutationError {
MutationError::Hom(error)
}
}
fn defect(defect: MutationDefect) -> MutationError {
MutationError::Defect(defect)
}
fn support(m: &Module) -> Vec<u32> {
m.dim_vector()
.iter()
.enumerate()
.filter(|&(_, &d)| d > 0)
.map(|(v, _)| v as u32)
.collect()
}
fn is_direct_sum(m: &Module, parts: &[Module]) -> bool {
let refs: Vec<&Module> = parts.iter().collect();
let rebuilt = if refs.is_empty() {
Module::zero(m.algebra())
} else {
direct_sum(&refs).0
};
rebuilt.dim_vector() == m.dim_vector()
&& (0..m.algebra().quiver().num_arrows())
.all(|i| rebuilt.map(ArrowId(i as u32)) == m.map(ArrowId(i as u32)))
}
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 mut rows: Vec<Vec<Fp>> = Vec::new();
for f in maps {
let block = f.map_at(v);
for r in 0..block.rows() {
rows.push(block.row(r).to_vec());
}
}
if rows.is_empty() {
0
} else {
DenseMat::from_rows(&rows).rank(&field)
}
})
.collect()
}
fn is_cokernel(f: &Morphism, g: &Morphism) -> bool {
if !g.source().ptr_eq(f.target()) {
return false;
}
let Ok(composite) = f.then(g) else {
return false;
};
if !composite.is_zero() {
return false;
}
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 {
#[inline]
pub fn module(&self) -> &Module {
&self.module
}
#[inline]
pub fn summands(&self) -> &[Module] {
&self.summands
}
#[inline]
pub fn summand(&self) -> &Module {
&self.summand
}
#[inline]
pub fn maps(&self) -> &[Morphism] {
&self.maps
}
pub fn image_dims(&self) -> Vec<usize> {
trace_dims(&self.maps, &self.summand)
}
pub fn verify(&self) -> bool {
if !is_direct_sum(&self.module, &self.summands) {
return false;
}
for f in &self.maps {
if !f.source().ptr_eq(&self.module) || !f.target().ptr_eq(&self.summand) {
return false;
}
}
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 {
#[inline]
pub fn slot(&self) -> usize {
self.slot
}
#[inline]
pub fn exchanged(&self) -> &Module {
&self.exchanged
}
#[inline]
pub fn almost_complete(&self) -> &AlmostCompletePair {
&self.almost_complete
}
#[inline]
pub fn source_extension(&self) -> &AddClosureWitness {
&self.source_extension
}
#[inline]
pub fn target_extension(&self) -> &AddClosureWitness {
&self.target_extension
}
#[inline]
pub fn distinct(&self) -> &SupportPairObstruction {
&self.distinct
}
#[inline]
pub fn approximation(&self) -> &MinimalLeftApproximation {
&self.approximation
}
#[inline]
pub fn exchange(&self) -> &Morphism {
&self.exchange
}
#[inline]
pub fn shape(&self) -> &ExchangeShape {
&self.shape
}
#[inline]
pub fn replacement(&self) -> Option<&Module> {
self.replacement.as_ref()
}
#[inline]
pub fn source_module(&self) -> &Module {
&self.source_module
}
#[inline]
pub fn source_projective(&self) -> &[u32] {
&self.source_projective
}
#[inline]
pub fn target_module(&self) -> &Module {
&self.target_module
}
#[inline]
pub fn target_projective(&self) -> &[u32] {
&self.target_projective
}
pub fn verify(&self) -> bool {
if !self.almost_complete.verify() {
return false;
}
let u = self.almost_complete.module();
let algebra = u.module().algebra();
if !Arc::ptr_eq(algebra, self.source_module.algebra())
|| !Arc::ptr_eq(algebra, self.target_module.algebra())
{
return false;
}
let (Ok(source_dec), Ok(target_dec)) = (
BasicDecomposition::new(&self.source_module),
BasicDecomposition::new(&self.target_module),
) else {
return false;
};
let (Ok(source_proj), Ok(target_proj)) = (
ProjectiveSupport::new(algebra, &self.source_projective),
ProjectiveSupport::new(algebra, &self.target_projective),
) else {
return false;
};
if self.almost_complete.projective().vertices() != source_proj.vertices() {
return false;
}
if !extends(u, &source_dec, &self.source_extension) {
return false;
}
if !self
.almost_complete
.projective()
.vertices()
.iter()
.all(|&v| target_proj.contains(v))
{
return false;
}
if !extends(u, &target_dec, &self.target_extension) {
return false;
}
match pair_iso(&source_dec, &source_proj, &target_dec, &target_proj) {
Ok(SupportPairIsoOutcome::NotIsomorphic(_)) => {}
_ => return false,
}
let (Ok(fresh_dec), Ok(fresh_proj)) = (
BasicDecomposition::new(&self.target_module),
ProjectiveSupport::new(algebra, &self.target_projective),
) else {
return false;
};
match SupportTauTiltingPair::classify(fresh_dec, fresh_proj) {
Ok(classification) if classification.is_pair() => {}
_ => return false,
}
self.exchange_holds(u, &source_dec, &target_dec, &source_proj, &target_proj)
}
fn exchange_holds(
&self,
u: &BasicDecomposition,
source_dec: &BasicDecomposition,
target_dec: &BasicDecomposition,
source_proj: &ProjectiveSupport,
target_proj: &ProjectiveSupport,
) -> bool {
let f = self.approximation.map();
if !f.source().ptr_eq(&self.exchanged) {
return false;
}
if self.approximation.summands().len() != u.len()
|| !self
.approximation
.summands()
.iter()
.zip(u.summands())
.all(|(a, b)| a.module().ptr_eq(b.module()))
{
return false;
}
if !self.approximation.verify() || !is_cokernel(f, &self.exchange) {
return false;
}
let Some(slot_summand) = source_dec.summands().get(self.slot) else {
return false;
};
if indecomposable_iso(slot_summand.module(), &self.exchanged, slot_summand.endo()).is_none()
{
return false;
}
let y = self.exchange.target();
match &self.shape {
ExchangeShape::MovesToProjective { vertex } => {
if !y.is_zero() || self.replacement.is_some() {
return false;
}
if source_proj.contains(*vertex) || !target_proj.contains(*vertex) {
return false;
}
let mut expected = source_proj.vertices().to_vec();
expected.push(*vertex);
expected.sort_unstable();
expected == target_proj.vertices() && target_dec.len() == u.len()
}
ExchangeShape::ReplacedByModule { multiplicity } => {
let Some(replacement) = &self.replacement else {
return false;
};
if y.is_zero() || source_proj.vertices() != target_proj.vertices() {
return false;
}
if target_dec.len() != u.len() + 1 {
return false;
}
let split = decompose(y);
if split.summands().len() != *multiplicity
|| split
.certificates()
.iter()
.any(|c| *c != Certificate::Indecomposable)
{
return false;
}
let Ok(y1) = IndecomposableModule::new(replacement) else {
return false;
};
if !split
.summands()
.iter()
.all(|s| indecomposable_iso(y1.module(), s, y1.endo()).is_some())
{
return false;
}
if source_dec
.summands()
.iter()
.any(|s| indecomposable_iso(y1.module(), s.module(), y1.endo()).is_some())
{
return false;
}
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 Ok(Some(live)) = AddClosureWitness::new(u, whole) else {
return false;
};
if live.matches().len() != stored.matches().len() {
return false;
}
if !stored.module().ptr_eq(u.module()) || !stored.target().ptr_eq(whole.module()) {
return false;
}
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 {
#[inline]
pub fn slot(&self) -> usize {
self.slot
}
#[inline]
pub fn target(&self) -> &SupportTauTiltingPair {
&self.target
}
#[inline]
pub fn into_target(self) -> SupportTauTiltingPair {
self.target
}
#[inline]
pub fn witness(&self) -> &MutationWitness {
&self.witness
}
#[inline]
pub fn shape(&self) -> &ExchangeShape {
self.witness.shape()
}
pub fn verify(&self) -> bool {
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()
&& self.target.verify()
}
}
#[derive(Debug)]
pub enum SlotOutcome {
NoLeftMutation(FacWitness),
LeftMutation(Box<Mutation>),
}
impl SlotOutcome {
#[inline]
pub fn is_left_mutation(&self) -> bool {
matches!(self, Self::LeftMutation(_))
}
#[inline]
pub fn mutation(&self) -> Option<&Mutation> {
match self {
Self::LeftMutation(mutation) => Some(mutation),
Self::NoLeftMutation(_) => None,
}
}
#[inline]
pub fn fac_witness(&self) -> Option<&FacWitness> {
match self {
Self::NoLeftMutation(witness) => Some(witness),
Self::LeftMutation(_) => None,
}
}
#[inline]
pub fn into_mutation(self) -> Option<Mutation> {
match self {
Self::LeftMutation(mutation) => Some(*mutation),
Self::NoLeftMutation(_) => None,
}
}
}
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 !dropped.is_empty() {
if dropped.len() != 1 {
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 vertex = dropped[0];
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();
if built.replacement.is_some() {
target_indices.push(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 {
if parts.is_empty() {
Module::zero(algebra)
} else {
direct_sum(parts).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
}
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());
}
}