use std::sync::Arc;
use crate::algebra::Algebra;
use crate::ar::TauError;
use crate::arquiver::{CatalogProvenance, IndecomposableCatalog};
use crate::basic::{
BasicDecomposition, BasicError, PairFingerprint, ProjectiveSupport, SupportPairIsoOutcome,
pair_iso, pairwise_distinct_by,
};
use crate::context::VerificationContext;
use crate::hom::{HomError, hom_dim};
use crate::module::Module;
use crate::profile::{Site, hit};
use crate::taurigid::{
NonTauRigidWitness, TauCache, TauRigidError, TauRigidModule, TauRigidityOutcome,
is_tau_rigid_summandwise, is_tau_rigid_summandwise_with_context,
};
#[derive(Clone, Debug)]
pub enum SupportTauError {
Basic(BasicError),
TauRigid(TauRigidError),
Hom(HomError),
SummandIndexCount {
indices: usize,
summands: usize,
},
Defect {
reason: String,
},
}
display_error! { error SupportTauError {
Self::Basic(error) => "the basic layer rejected an input: {error}";
Self::TauRigid(error) => "tau-rigidity stayed undecided: {error}";
Self::Hom(error) => "a Hom space failed: {error}";
Self::SummandIndexCount { indices, summands } => "{indices} summand indices for {summands} summands; one index per summand";
Self::Defect { reason } => "internal cross-check failed: {reason}";
} }
from_variants!(SupportTauError {
BasicError => Basic,
TauRigidError => TauRigid,
});
impl From<TauError> for SupportTauError {
fn from(error: TauError) -> SupportTauError {
SupportTauError::TauRigid(TauRigidError::Tau(error))
}
}
from_variants!(SupportTauError { HomError => Hom });
#[derive(Clone, Debug)]
pub enum PairRejection {
DifferentAlgebras,
HomFromProjectiveNonzero {
vertex: u32,
dim: usize,
},
NotTauRigid(NonTauRigidWitness),
SummandCount {
module: usize,
projective: usize,
expected: usize,
},
}
impl PairRejection {
accessor_methods! {
pub condition() -> u32 = |this| match this {
Self::DifferentAlgebras => 1,
Self::HomFromProjectiveNonzero { .. } => 2,
Self::NotTauRigid(_) => 3,
Self::SummandCount { .. } => 4,
};
}
}
display_error! { PairRejection {
Self::DifferentAlgebras => "the two parts do not share one algebra";
Self::HomFromProjectiveNonzero { vertex, dim } => "Hom(P, M) is not zero: dim Hom(P_{vertex}, M) = dim M_{vertex} = {dim}";
Self::NotTauRigid(_) => "M is not tau-rigid";
Self::SummandCount { module, projective, expected } => "|M| + |P| = {module} + {projective}, and the pair needs {expected}";
} }
enum Checked {
Accepted(TauRigidModule),
Rejected(PairRejection),
}
fn check_conditions(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
expected: usize,
summand_indices: &[usize],
cache: Option<&mut TauCache>,
) -> Result<Checked, SupportTauError> {
let mut owned = TauCache::new();
let cache = cache.unwrap_or(&mut owned);
check_conditions_with(module, projective, expected, summand_indices, |summands| {
is_tau_rigid_summandwise(summands, cache)
})
}
fn check_conditions_with_context(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
expected: usize,
summand_indices: &[usize],
context: &VerificationContext,
) -> Result<Checked, SupportTauError> {
check_conditions_with(module, projective, expected, summand_indices, |summands| {
is_tau_rigid_summandwise_with_context(summands, context)
})
}
fn check_conditions_with(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
expected: usize,
summand_indices: &[usize],
mut rigidity: impl FnMut(&[(usize, Module)]) -> Result<TauRigidityOutcome, TauRigidError>,
) -> Result<Checked, SupportTauError> {
if summand_indices.len() != module.len() {
return Err(SupportTauError::SummandIndexCount {
indices: summand_indices.len(),
summands: module.len(),
});
}
if !Arc::ptr_eq(module.module().algebra(), projective.algebra()) {
return Ok(Checked::Rejected(PairRejection::DifferentAlgebras));
}
let dims = module.module().dim_vector();
if let Some(&vertex) = projective
.vertices()
.iter()
.find(|&&v| dims[v as usize] != 0)
{
return Ok(Checked::Rejected(PairRejection::HomFromProjectiveNonzero {
vertex,
dim: dims[vertex as usize],
}));
}
let summands: Vec<(usize, Module)> = summand_indices
.iter()
.zip(module.summands())
.map(|(&index, x)| (index, x.module().clone()))
.collect();
let rigid = match rigidity(&summands)? {
TauRigidityOutcome::TauRigid(rigid) => rigid,
TauRigidityOutcome::NotTauRigid(witness) => {
return Ok(Checked::Rejected(PairRejection::NotTauRigid(witness)));
}
};
if module.len() + projective.len() != expected {
return Ok(Checked::Rejected(PairRejection::SummandCount {
module: module.len(),
projective: projective.len(),
expected,
}));
}
Ok(Checked::Accepted(rigid))
}
fn vertex_count(module: &BasicDecomposition) -> usize {
module.module().algebra().quiver().num_vertices() as usize
}
fn positional(module: &BasicDecomposition) -> Vec<usize> {
(0..module.len()).collect()
}
fn support_complement(module: &BasicDecomposition) -> Vec<u32> {
module
.module()
.dim_vector()
.iter()
.enumerate()
.filter(|&(_, &dim)| dim == 0)
.map(|(vertex, _)| vertex as u32)
.collect()
}
fn as_support(module: &BasicDecomposition, vertices: &[u32]) -> ProjectiveSupport {
ProjectiveSupport::new(module.module().algebra(), vertices)
.expect("the support complement lists vertices of the module's own algebra")
}
fn omitted_vertices(module: &BasicDecomposition, projective: &ProjectiveSupport) -> Vec<u32> {
support_complement(module)
.into_iter()
.filter(|&v| !projective.contains(v))
.collect()
}
fn checked_omissions(
module: &BasicDecomposition,
projective: &ProjectiveSupport,
limit: usize,
subject: &str,
) -> Result<Vec<u32>, SupportTauError> {
let omitted = omitted_vertices(module, projective);
if omitted.len() > limit {
return Err(SupportTauError::Defect {
reason: format!(
"{subject} with module dimension vectors {:?} and support {:?} left the vertices \
{omitted:?} out of the support complement",
module.dim_vectors(),
projective.vertices()
),
});
}
Ok(omitted)
}
fn recheck_shared(
module: &BasicDecomposition,
projective_len: usize,
rigid: &TauRigidModule,
expected: usize,
) -> bool {
verify_guard!(module.len() + projective_len == expected);
verify_guard!(rigid.summands().len() == module.len());
rigid
.summands()
.iter()
.zip(module.summands())
.all(|((_, stored), x)| stored.ptr_eq(x.module()))
}
pub struct SupportTauTiltingPair {
module: BasicDecomposition,
rigid: TauRigidModule,
}
debug_fields!(SupportTauTiltingPair |this| {
"module_dim_vectors" => this.module.dim_vectors();
"projective_support" => support_complement(&this.module);
});
#[derive(Debug)]
pub enum SupportTauTiltingClassification {
Pair(SupportTauTiltingPair),
Rejected(PairRejection),
}
impl SupportTauTiltingClassification {
binary_outcome_accessors!(
Pair,
Rejected,
pair -> SupportTauTiltingPair = |value| value,
rejection -> PairRejection = |value| value,
is_pair,
into_pair -> SupportTauTiltingPair = |value| value;
flag = "Whether the candidate is a pair.";
positive = "The pair, or `None` for a rejection.";
negative = "The rejection, or `None` for a pair.";
into = "Takes the pair out, or `None` for a rejection.";
);
}
impl SupportTauTiltingPair {
pub fn classify_with_cache(
module: BasicDecomposition,
projective: ProjectiveSupport,
summand_indices: &[usize],
cache: Option<&mut TauCache>,
) -> Result<SupportTauTiltingClassification, SupportTauError> {
hit(Site::SupportPairClassify);
let expected = vertex_count(&module);
let checked = check_conditions(&module, &projective, expected, summand_indices, cache)?;
Self::from_checked(module, projective, checked)
}
pub(crate) fn classify_with_context(
module: BasicDecomposition,
projective: ProjectiveSupport,
context: &VerificationContext,
) -> Result<SupportTauTiltingClassification, SupportTauError> {
hit(Site::SupportPairClassify);
let expected = vertex_count(&module);
let checked = check_conditions_with_context(
&module,
&projective,
expected,
&positional(&module),
context,
)?;
Self::from_checked(module, projective, checked)
}
fn from_checked(
module: BasicDecomposition,
projective: ProjectiveSupport,
checked: Checked,
) -> Result<SupportTauTiltingClassification, SupportTauError> {
match checked {
Checked::Accepted(rigid) => {
checked_omissions(&module, &projective, 0, "a pair")?;
Ok(SupportTauTiltingClassification::Pair(
SupportTauTiltingPair { module, rigid },
))
}
Checked::Rejected(rejection) => {
Ok(SupportTauTiltingClassification::Rejected(rejection))
}
}
}
pub fn classify(
module: BasicDecomposition,
projective: ProjectiveSupport,
) -> Result<SupportTauTiltingClassification, SupportTauError> {
let indices = positional(&module);
Self::classify_with_cache(module, projective, &indices, None)
}
pub fn new(
module: BasicDecomposition,
projective: ProjectiveSupport,
) -> Result<Option<SupportTauTiltingPair>, SupportTauError> {
Ok(Self::classify(module, projective)?.into_pair())
}
accessor_methods! {
pub module() -> &BasicDecomposition = |this| &this.module;
pub rigid() -> &TauRigidModule = |this| &this.rigid;
pub projective() -> ProjectiveSupport = |this|
as_support(&this.module, &support_complement(&this.module));
pub is_tau_tilting() -> bool = |this|
this.module.module().dim_vector().iter().all(|&d| d > 0);
pub summand_count() -> usize = |this|
this.module.len() + support_complement(&this.module).len();
}
verify_methods!(pub(crate), { hit(Site::SupportPairVerify); },
|self, context| {
recheck_shared(
&self.module,
support_complement(&self.module).len(),
&self.rigid,
vertex_count(&self.module),
) && self.rigid.verify_with_context(context)
});
}
pub struct AlmostCompletePair {
module: BasicDecomposition,
rigid: TauRigidModule,
omitted: Option<u32>,
}
debug_fields!(AlmostCompletePair |this| {
"module_dim_vectors" => this.module.dim_vectors();
"projective_support" => this.support();
"omitted_vertex" => this.omitted;
});
#[derive(Debug)]
pub enum AlmostCompleteClassification {
Pair(AlmostCompletePair),
Rejected(PairRejection),
}
impl AlmostCompleteClassification {
binary_outcome_accessors!(
Pair,
Rejected,
pair -> AlmostCompletePair = |value| value,
rejection -> PairRejection = |value| value,
is_pair,
into_pair -> AlmostCompletePair = |value| value;
flag = "Whether the candidate is an almost complete pair.";
positive = "The pair, or `None` for a rejection.";
negative = "The rejection, or `None` for a pair.";
into = "Takes the pair out, or `None` for a rejection.";
);
}
impl AlmostCompletePair {
pub fn classify_with_cache(
module: BasicDecomposition,
projective: ProjectiveSupport,
summand_indices: &[usize],
cache: Option<&mut TauCache>,
) -> Result<AlmostCompleteClassification, SupportTauError> {
hit(Site::AlmostCompleteClassify);
let expected = vertex_count(&module).saturating_sub(1);
match check_conditions(&module, &projective, expected, summand_indices, cache)? {
Checked::Accepted(rigid) => {
let omitted =
checked_omissions(&module, &projective, 1, "an almost complete pair")?;
Ok(AlmostCompleteClassification::Pair(AlmostCompletePair {
module,
rigid,
omitted: omitted.first().copied(),
}))
}
Checked::Rejected(rejection) => Ok(AlmostCompleteClassification::Rejected(rejection)),
}
}
pub fn classify(
module: BasicDecomposition,
projective: ProjectiveSupport,
) -> Result<AlmostCompleteClassification, SupportTauError> {
let indices = positional(&module);
Self::classify_with_cache(module, projective, &indices, None)
}
pub fn new(
module: BasicDecomposition,
projective: ProjectiveSupport,
) -> Result<Option<AlmostCompletePair>, SupportTauError> {
Ok(Self::classify(module, projective)?.into_pair())
}
accessor_methods! {
pub module() -> &BasicDecomposition = |this| &this.module;
pub omitted_vertex() -> Option<u32> = |this| this.omitted;
pub rigid() -> &TauRigidModule = |this| &this.rigid;
}
fn support(&self) -> Vec<u32> {
support_complement(&self.module)
.into_iter()
.filter(|vertex| Some(*vertex) != self.omitted)
.collect()
}
accessor_methods! {
pub projective() -> ProjectiveSupport = |this|
as_support(&this.module, &this.support());
pub summand_count() -> usize = |this| this.module.len() + this.support().len();
}
verify_methods!(pub(crate), { hit(Site::AlmostCompleteVerify); },
|self, context| {
let complement = support_complement(&self.module);
verify_guard!(self.omitted.is_none_or(|omitted| complement.contains(&omitted)));
recheck_shared(
&self.module,
self.support().len(),
&self.rigid,
vertex_count(&self.module).saturating_sub(1),
) && self.rigid.verify_with_context(context)
});
}
struct CatalogWalk<'a> {
catalog: &'a IndecomposableCatalog,
algebra: Arc<Algebra>,
vertices: usize,
tau_hom: Vec<Vec<usize>>,
cache: TauCache,
pairs: Vec<SupportTauTiltingPair>,
nodes: usize,
}
impl CatalogWalk<'_> {
fn extends_tau_rigid(&self, chosen: &[usize], i: usize) -> bool {
self.tau_hom[i][i] == 0
&& chosen
.iter()
.all(|&j| self.tau_hom[i][j] == 0 && self.tau_hom[j][i] == 0)
}
fn walk(&mut self, chosen: &mut Vec<usize>, start: usize) -> Result<(), SupportTauError> {
self.emit(chosen)?;
if chosen.len() == self.vertices {
return Ok(());
}
for i in start..self.catalog.len() {
if self.extends_tau_rigid(chosen, i) {
chosen.push(i);
self.nodes += 1;
self.walk(chosen, i + 1)?;
chosen.pop();
}
}
Ok(())
}
fn emit(&mut self, chosen: &[usize]) -> Result<(), SupportTauError> {
let support: Vec<u32> = (0..self.vertices as u32)
.filter(|&v| self.vanishes_at(chosen, v))
.collect();
if support.len() + chosen.len() != self.vertices {
return Ok(());
}
let module = BasicDecomposition::from_catalog(self.catalog, chosen)?;
let indices = chosen.to_vec();
let projective = ProjectiveSupport::new(&self.algebra, &support)?;
let classification = SupportTauTiltingPair::classify_with_cache(
module,
projective,
&indices,
Some(&mut self.cache),
)?;
match classification {
SupportTauTiltingClassification::Pair(pair) => {
self.pairs.push(pair);
Ok(())
}
SupportTauTiltingClassification::Rejected(rejection) => Err(SupportTauError::Defect {
reason: format!(
"the tables admitted the subset {chosen:?} with support {support:?} and the \
certified route rejected it: {rejection}"
),
}),
}
}
fn vanishes_at(&self, chosen: &[usize], vertex: u32) -> bool {
chosen
.iter()
.all(|&i| self.catalog.entries()[i].module().dim_vector()[vertex as usize] == 0)
}
}
pub struct CatalogEnumeration {
algebra: Arc<Algebra>,
provenance: CatalogProvenance,
catalog_len: usize,
pairs: Vec<SupportTauTiltingPair>,
nodes_visited: usize,
}
debug_fields!(CatalogEnumeration |this| {
"provenance" => this.provenance;
"catalog_len" => this.catalog_len;
"pairs" => this.pairs.len();
"nodes_visited" => this.nodes_visited;
});
impl CatalogEnumeration {
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.algebra;
pub provenance() -> CatalogProvenance = |this| this.provenance;
pub catalog_len() -> usize = |this| this.catalog_len;
pub pairs() -> &[SupportTauTiltingPair] = |this| &this.pairs;
pub len() -> usize = |this| this.pairs.len();
pub is_empty() -> bool = |this| this.pairs.is_empty();
pub nodes_visited() -> usize = |this| this.nodes_visited;
}
pub fn histogram(&self) -> Vec<usize> {
let vertices = self.algebra.quiver().num_vertices() as usize;
let mut out = vec![0; vertices + 1];
for pair in &self.pairs {
out[pair.module().len()] += 1;
}
out
}
pub fn verify(&self) -> bool {
pairwise_distinct_by(
&self.pairs,
|pair| {
(Arc::ptr_eq(pair.module().module().algebra(), &self.algebra) && pair.verify())
.then(|| PairFingerprint::new(pair.module(), &pair.projective()).ok())
.flatten()
},
|left, right| {
matches!(
pair_iso(
left.module(),
&left.projective(),
right.module(),
&right.projective(),
),
Ok(SupportPairIsoOutcome::NotIsomorphic(_))
)
},
)
}
}
pub fn enumerate_over_catalog(
catalog: &IndecomposableCatalog,
) -> Result<CatalogEnumeration, SupportTauError> {
let algebra = catalog.algebra().clone();
let vertices = algebra.quiver().num_vertices() as usize;
let mut cache = TauCache::new();
let mut translates = Vec::with_capacity(catalog.len());
for entry in catalog.entries() {
translates.push(cache.tau_of(entry.module())?.clone());
}
let mut tau_hom = vec![vec![0usize; catalog.len()]; catalog.len()];
for (i, x) in catalog.entries().iter().enumerate() {
for (j, translate) in translates.iter().enumerate() {
if !translate.is_zero() {
tau_hom[i][j] = hom_dim(x.module(), translate)?;
}
}
}
let mut walk = CatalogWalk {
catalog,
algebra: algebra.clone(),
vertices,
tau_hom,
cache,
pairs: Vec::new(),
nodes: 1,
};
walk.walk(&mut Vec::with_capacity(vertices), 0)?;
Ok(CatalogEnumeration {
algebra,
provenance: catalog.provenance(),
catalog_len: catalog.len(),
pairs: walk.pairs,
nodes_visited: walk.nodes,
})
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{
commutative_square, kronecker, linear_an, linear_nakayama, radical_square_zero_cycle,
truncated_poly,
};
use crate::ar::tau;
use crate::dynkin::{DynkinError, DynkinType, dynkin_quiver};
use crate::enumerate::EnumerateError;
use crate::field::PrimeField;
use crate::iso::{IsoOutcome, is_isomorphic};
use crate::linalg::DenseMat;
use crate::quiver::Quiver;
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 semisimple(n: u32, field: PrimeField) -> Arc<Algebra> {
path_algebra(
Quiver::new(n, &[]).expect("no arrow is out of range"),
field,
)
}
fn basic(m: &Module) -> BasicDecomposition {
BasicDecomposition::new(m).expect("the fixture module is basic")
}
fn support(algebra: &Arc<Algebra>, vertices: &[u32]) -> ProjectiveSupport {
ProjectiveSupport::new(algebra, vertices).expect("the fixture vertices are in range")
}
fn all_vertices(algebra: &Arc<Algebra>) -> Vec<u32> {
(0..algebra.quiver().num_vertices()).collect()
}
fn regular(algebra: &Arc<Algebra>) -> Module {
let parts: Vec<Module> = all_vertices(algebra)
.iter()
.map(|&v| Module::projective(algebra, v))
.collect();
let refs: Vec<&Module> = parts.iter().collect();
sum(algebra, &refs)
}
fn sum(algebra: &Arc<Algebra>, parts: &[&Module]) -> Module {
if parts.is_empty() {
Module::zero(algebra)
} else {
crate::module::direct_sum(parts).0
}
}
fn expect_pair(classification: SupportTauTiltingClassification) -> SupportTauTiltingPair {
match classification {
SupportTauTiltingClassification::Pair(pair) => pair,
SupportTauTiltingClassification::Rejected(rejection) => {
panic!(
"expected a pair, got condition {} : {rejection}",
rejection.condition()
)
}
}
}
fn expect_rejection(classification: SupportTauTiltingClassification) -> PairRejection {
match classification {
SupportTauTiltingClassification::Rejected(rejection) => rejection,
SupportTauTiltingClassification::Pair(pair) => {
panic!("expected a rejection, got {pair:?}")
}
}
}
fn catalog_fixtures(field: PrimeField) -> Vec<(String, IndecomposableCatalog)> {
let modulus = field.modulus();
let mut out = Vec::new();
for n in [2u32, 3, 4] {
let algebra = semisimple(n, field);
out.push((
format!("semisimple({n}) over F_{modulus}"),
IndecomposableCatalog::nakayama(&algebra).expect("no arrow means Nakayama"),
));
}
for n in [2usize, 3] {
let algebra = linear_an(n, field);
out.push((
format!("linear_an({n}) over F_{modulus}"),
IndecomposableCatalog::dynkin(&algebra).expect("A_n is Dynkin"),
));
}
let tp = truncated_poly(3, field).expect("k[x]/(x^3) is admissible");
out.push((
format!("truncated_poly(3) over F_{modulus}"),
IndecomposableCatalog::nakayama(&tp).expect("one loop is Nakayama"),
));
let cycle = radical_square_zero_cycle(3, field);
out.push((
format!("radical_square_zero_cycle(3) over F_{modulus}"),
IndecomposableCatalog::nakayama(&cycle).expect("a cycle is Nakayama"),
));
let nakayama = linear_nakayama(&[2, 2, 1], field).expect("[2, 2, 1] is a Kupisch series");
out.push((
format!("linear_nakayama([2, 2, 1]) over F_{modulus}"),
IndecomposableCatalog::nakayama(&nakayama).expect("a linear quiver is Nakayama"),
));
out
}
fn brute_force(catalog: &IndecomposableCatalog) -> (usize, Vec<usize>, usize) {
let algebra = catalog.algebra();
let vertices = algebra.quiver().num_vertices() as usize;
let k = catalog.len();
assert!(k < 20, "the bitmask walk needs a small catalog");
let translates: Vec<Module> = catalog
.entries()
.iter()
.map(|x| tau(x.module()).expect("the fixture translates"))
.collect();
let mut tau_hom = vec![vec![0usize; k]; k];
for (i, x) in catalog.entries().iter().enumerate() {
for (j, translate) in translates.iter().enumerate() {
if !translate.is_zero() {
tau_hom[i][j] = hom_dim(x.module(), translate).expect("one algebra");
}
}
}
let mut pairs = 0;
let mut histogram = vec![0usize; vertices + 1];
let mut nodes = 0;
for mask in 0..(1u32 << k) {
let chosen: Vec<usize> = (0..k).filter(|&i| mask & (1 << i) != 0).collect();
let rigid = chosen
.iter()
.all(|&i| chosen.iter().all(|&j| tau_hom[i][j] == 0));
if !rigid {
continue;
}
if chosen.len() <= vertices {
nodes += 1;
}
if chosen.len() > vertices {
continue;
}
let zero_support = (0..vertices)
.filter(|&v| {
chosen
.iter()
.all(|&i| catalog.entries()[i].module().dim_vector()[v] == 0)
})
.count();
let want = vertices - chosen.len();
if zero_support < want {
continue;
}
let choices = (0..want).fold(1usize, |acc, t| acc * (zero_support - t) / (t + 1));
pairs += choices;
histogram[chosen.len()] += choices;
}
(pairs, histogram, nodes)
}
#[test]
fn the_regular_pair_is_a_support_tau_tilting_pair() {
for field in fields() {
for algebra in [
linear_an(2, field),
linear_an(3, field),
d4(field),
truncated_poly(3, field).unwrap(),
linear_nakayama(&[2, 2, 1], field).unwrap(),
radical_square_zero_cycle(3, field),
commutative_square(field),
kronecker(2, field),
semisimple(3, field),
] {
let n = algebra.quiver().num_vertices() as usize;
let pair = expect_pair(
SupportTauTiltingPair::classify(
basic(®ular(&algebra)),
support(&algebra, &[]),
)
.expect("the fixture translates"),
);
assert_eq!(pair.module().len(), n);
assert_eq!(pair.summand_count(), n);
assert!(pair.is_tau_tilting(), "the projective part is empty");
assert!(pair.projective().is_empty());
assert!(pair.rigid().vanishing_pairs().is_empty(), "tau A is zero");
assert!(pair.verify(), "over F_{}", field.modulus());
}
}
}
#[test]
fn the_zero_module_over_the_full_support_is_a_support_tau_tilting_pair() {
for field in fields() {
for algebra in [
linear_an(2, field),
d4(field),
truncated_poly(3, field).unwrap(),
kronecker(2, field),
] {
let n = algebra.quiver().num_vertices() as usize;
let pair = expect_pair(
SupportTauTiltingPair::classify(
basic(&Module::zero(&algebra)),
support(&algebra, &all_vertices(&algebra)),
)
.expect("the zero module needs no translate"),
);
assert!(pair.module().is_empty());
assert_eq!(pair.projective().len(), n);
assert_eq!(pair.summand_count(), n);
assert!(!pair.is_tau_tilting(), "the projective part is all of A");
assert!(pair.rigid().is_zero_module());
assert!(pair.verify(), "over F_{}", field.modulus());
}
}
}
#[test]
fn each_condition_has_its_own_rejection() {
for field in fields() {
let algebra = linear_an(2, field);
let other = linear_an(2, field);
let s0 = Module::simple(&algebra, 0);
let s1 = Module::simple(&algebra, 1);
let p0 = Module::projective(&algebra, 0);
let mismatched = expect_rejection(
SupportTauTiltingPair::classify(basic(&p0), support(&other, &[]))
.expect("the algebra check runs before any Hom space"),
);
assert_eq!(mismatched.condition(), 1);
assert!(matches!(mismatched, PairRejection::DifferentAlgebras));
let hom = expect_rejection(
SupportTauTiltingPair::classify(basic(&p0), support(&algebra, &[1]))
.expect("A_2 translates"),
);
assert_eq!(hom.condition(), 2);
assert!(matches!(
hom,
PairRejection::HomFromProjectiveNonzero { vertex: 1, dim: 1 }
));
let rigid = expect_rejection(
SupportTauTiltingPair::classify(
basic(&sum(&algebra, &[&s0, &s1])),
support(&algebra, &[]),
)
.expect("A_2 translates"),
);
assert_eq!(rigid.condition(), 3);
match &rigid {
PairRejection::NotTauRigid(witness) => {
assert_eq!(witness.translate().dim_vector(), &[0, 1]);
assert!(witness.verify());
}
other => panic!("expected a tau-rigidity failure, got {other}"),
}
let count = expect_rejection(
SupportTauTiltingPair::classify(
basic(&Module::zero(&algebra)),
support(&algebra, &[]),
)
.expect("the zero module needs no translate"),
);
assert_eq!(count.condition(), 4);
assert!(matches!(
count,
PairRejection::SummandCount {
module: 0,
projective: 0,
expected: 2
}
));
}
}
#[test]
fn the_a2_near_miss_is_rejected_by_the_right_module_hom_condition() {
for field in fields() {
let algebra = linear_an(2, field);
let p0 = Module::projective(&algebra, 0);
assert_eq!(basic(&p0).len() + support(&algebra, &[1]).len(), 2);
let alone = expect_pair(
SupportTauTiltingPair::classify(
basic(&sum(&algebra, &[&p0, &Module::simple(&algebra, 0)])),
support(&algebra, &[]),
)
.expect("A_2 translates"),
);
assert!(alone.verify());
let rejection = expect_rejection(
SupportTauTiltingPair::classify(basic(&p0), support(&algebra, &[1]))
.expect("A_2 translates"),
);
assert_eq!(rejection.condition(), 2);
match rejection {
PairRejection::HomFromProjectiveNonzero { vertex, dim } => {
assert_eq!((vertex, dim), (1, 1));
assert_eq!(
hom_dim(&Module::projective(&algebra, vertex), &p0).unwrap(),
dim,
"over F_{}",
field.modulus()
);
}
other => panic!("the right-module condition must fire here, got {other}"),
}
}
}
#[test]
fn the_a2_pentagon_lists_five_pairs_by_dimension_vector() {
for field in fields() {
let algebra = linear_an(2, field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("A_2 is Dynkin");
let enumeration = enumerate_over_catalog(&catalog).expect("A_2 enumerates");
let mut listed: Vec<(Vec<Vec<usize>>, Vec<u32>)> = enumeration
.pairs()
.iter()
.map(|pair| {
(
pair.module().dim_vectors(),
pair.projective().vertices().to_vec(),
)
})
.collect();
listed.sort();
assert_eq!(
listed,
vec![
(vec![], vec![0, 1]),
(vec![vec![0, 1]], vec![0]),
(vec![vec![0, 1], vec![1, 1]], vec![]),
(vec![vec![1, 0]], vec![1]),
(vec![vec![1, 0], vec![1, 1]], vec![]),
],
"over F_{}",
field.modulus()
);
assert_eq!(enumeration.len(), 5);
assert_eq!(enumeration.histogram(), vec![1, 2, 2]);
assert_eq!(
enumeration
.pairs()
.iter()
.filter(|pair| pair.is_tau_tilting())
.count(),
2
);
assert!(enumeration.verify());
}
}
#[test]
fn the_enumerated_counts_are_pinned() {
let expected: Vec<(&str, usize, Vec<usize>)> = vec![
("semisimple(2)", 4, vec![1, 2, 1]),
("semisimple(3)", 8, vec![1, 3, 3, 1]),
("semisimple(4)", 16, vec![1, 4, 6, 4, 1]),
("linear_an(2)", 5, vec![1, 2, 2]),
("linear_an(3)", 14, vec![1, 3, 5, 5]),
("truncated_poly(3)", 2, vec![1, 1]),
("radical_square_zero_cycle(3)", 14, vec![1, 3, 6, 4]),
("linear_nakayama([2, 2, 1])", 12, vec![1, 3, 5, 3]),
];
for field in fields() {
let fixtures = catalog_fixtures(field);
assert_eq!(fixtures.len(), expected.len());
for ((name, catalog), (short, count, histogram)) in fixtures.iter().zip(&expected) {
assert!(name.starts_with(short), "{name} is not {short}");
let enumeration = enumerate_over_catalog(catalog).expect("the fixture enumerates");
assert_eq!(enumeration.len(), *count, "{name}");
assert_eq!(&enumeration.histogram(), histogram, "{name}");
assert_eq!(enumeration.provenance(), catalog.provenance());
assert_eq!(enumeration.catalog_len(), catalog.len());
assert!(!enumeration.is_empty());
assert!(enumeration.verify(), "{name}");
}
}
}
#[test]
fn the_dfs_node_count_is_the_number_of_tau_rigid_subsets() {
let expected = [
("semisimple(2)", 4usize),
("semisimple(3)", 8),
("semisimple(4)", 16),
("linear_an(2)", 6),
("linear_an(3)", 22),
("truncated_poly(3)", 2),
("radical_square_zero_cycle(3)", 20),
("linear_nakayama([2, 2, 1])", 16),
];
for field in fields() {
for ((name, catalog), (short, nodes)) in catalog_fixtures(field).iter().zip(&expected) {
assert!(name.starts_with(short), "{name} is not {short}");
let enumeration = enumerate_over_catalog(catalog).expect("the fixture enumerates");
let (count, histogram, brute_nodes) = brute_force(catalog);
assert_eq!(enumeration.nodes_visited(), *nodes, "{name}");
assert_eq!(enumeration.nodes_visited(), brute_nodes, "{name}");
assert_eq!(enumeration.len(), count, "{name}");
assert_eq!(enumeration.histogram(), histogram, "{name}");
}
}
}
#[test]
fn the_d4_enumeration_has_fifty_pairs() {
for field in fields() {
let algebra = d4(field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("D_4 is Dynkin");
assert_eq!(catalog.len(), 12);
let enumeration = enumerate_over_catalog(&catalog).expect("D_4 enumerates");
assert_eq!(enumeration.len(), 50, "over F_{}", field.modulus());
assert_eq!(enumeration.histogram(), vec![1, 4, 9, 16, 20]);
let (count, histogram, nodes) = brute_force(&catalog);
assert_eq!(count, 50);
assert_eq!(histogram, vec![1, 4, 9, 16, 20]);
assert_eq!(enumeration.nodes_visited(), 120);
assert_eq!(enumeration.nodes_visited(), nodes);
assert_eq!(enumeration.provenance(), CatalogProvenance::DynkinZeroIdeal);
assert!(enumeration.verify(), "over F_{}", field.modulus());
}
}
#[test]
fn the_kronecker_algebra_has_no_catalog() {
for field in fields() {
let algebra = kronecker(2, field);
assert_eq!(
IndecomposableCatalog::nakayama(&algebra).unwrap_err(),
EnumerateError::NotNakayama {
vertex: 0,
incoming: 0,
outgoing: 2
}
);
assert!(matches!(
IndecomposableCatalog::dynkin(&algebra).unwrap_err(),
DynkinError::NotDynkin { .. }
));
}
}
#[test]
fn the_a2_almost_complete_pairs_are_the_five_edges() {
for field in fields() {
let algebra = linear_an(2, field);
let modules = [
Module::simple(&algebra, 0),
Module::simple(&algebra, 1),
Module::projective(&algebra, 0),
];
let mut found = 0;
for m in &modules {
let pair = AlmostCompletePair::new(basic(m), support(&algebra, &[]))
.expect("A_2 translates")
.expect("a tau-rigid indecomposable with no support is almost complete");
assert_eq!(pair.summand_count(), 1);
assert!(pair.verify());
found += 1;
}
for v in [0u32, 1] {
let pair = AlmostCompletePair::new(
basic(&Module::zero(&algebra)),
support(&algebra, &[v]),
)
.expect("the zero module needs no translate")
.expect("(0, P_v) is almost complete");
assert!(pair.module().is_empty());
assert_eq!(pair.projective().len(), 1);
assert!(pair.verify());
found += 1;
}
assert_eq!(found, 5, "over F_{}", field.modulus());
}
}
#[test]
fn the_two_pair_types_reject_each_other_on_the_count() {
for field in fields() {
let algebra = linear_an(3, field);
let a = regular(&algebra);
let full = SupportTauTiltingPair::new(basic(&a), support(&algebra, &[]))
.expect("A_3 translates")
.expect("(A, 0) is a pair");
assert_eq!(full.summand_count(), 3);
let as_almost = AlmostCompletePair::classify(basic(&a), support(&algebra, &[]))
.expect("A_3 translates");
match as_almost {
AlmostCompleteClassification::Rejected(PairRejection::SummandCount {
module,
projective,
expected,
}) => assert_eq!((module, projective, expected), (3, 0, 2)),
other => panic!("expected a count rejection, got {other:?}"),
}
let two = sum(
&algebra,
&[
&Module::projective(&algebra, 0),
&Module::projective(&algebra, 1),
],
);
let almost = AlmostCompletePair::new(basic(&two), support(&algebra, &[]))
.expect("A_3 translates")
.expect("(P_0 + P_1, 0) is almost complete");
assert_eq!(almost.summand_count(), 2);
assert!(almost.verify());
let as_full = SupportTauTiltingPair::classify(basic(&two), support(&algebra, &[]))
.expect("A_3 translates");
assert_eq!(
expect_rejection(as_full).condition(),
4,
"over F_{}",
field.modulus()
);
}
}
#[test]
fn a_tampered_pair_fails_verification() {
for field in fields() {
let algebra = linear_an(3, field);
let a = regular(&algebra);
let pair = SupportTauTiltingPair::new(basic(&a), support(&algebra, &[]))
.expect("A_3 translates")
.expect("(A, 0) is a pair");
assert!(pair.verify());
assert!(pair.projective().is_empty(), "A is sincere");
let s1 = Module::simple(&algebra, 1);
let p1 = Module::projective(&algebra, 1);
let mut forged = SupportTauTiltingPair::new(basic(&a), support(&algebra, &[]))
.expect("A_3 translates")
.expect("(A, 0) is a pair");
let donor = SupportTauTiltingPair::new(
basic(&sum(
&algebra,
&[&s1, &p1, &Module::projective(&algebra, 0)],
)),
support(&algebra, &[]),
)
.expect("A_3 translates")
.expect("(S_1 + P_1 + P_0, 0) is a pair");
assert!(donor.rigid().verify(), "the donor witness is honest");
assert_eq!(
donor.rigid().summands().len(),
forged.rigid.summands().len()
);
forged.rigid = donor.rigid().clone();
assert!(!forged.verify(), "over F_{}", field.modulus());
}
}
#[test]
fn the_projective_part_of_a_pair_is_the_whole_support_complement() {
for field in fields() {
let algebra = linear_an(3, field);
let m = sum(
&algebra,
&[
&Module::simple(&algebra, 1),
&Module::projective(&algebra, 1),
],
);
assert_eq!(basic(&m).module().dim_vector(), &[0, 2, 1]);
let pair = SupportTauTiltingPair::new(basic(&m), support(&algebra, &[0]))
.expect("A_3 translates")
.expect("(S_1 + P_1, P_0) is a pair");
assert_eq!(pair.projective().vertices(), [0]);
let short = expect_rejection(
SupportTauTiltingPair::classify(basic(&m), support(&algebra, &[]))
.expect("A_3 translates"),
);
assert_eq!(short.condition(), 4, "over F_{}", field.modulus());
}
}
#[test]
fn a_shared_cache_serves_a_whole_enumeration() {
let field = f5();
let algebra = linear_an(3, field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("A_3 is Dynkin");
let mut cache = TauCache::new();
for (i, entry) in catalog.entries().iter().enumerate() {
let pair = SupportTauTiltingPair::classify_with_cache(
basic(entry.module()),
support(&algebra, &[]),
&[i],
Some(&mut cache),
)
.expect("A_3 translates");
assert_eq!(expect_rejection(pair).condition(), 4);
}
assert_eq!(cache.len(), catalog.len());
assert_eq!(cache.misses(), catalog.len() as u64);
}
#[test]
fn a_wrong_index_count_is_rejected() {
let algebra = linear_an(3, f5());
let error = SupportTauTiltingPair::classify_with_cache(
basic(®ular(&algebra)),
support(&algebra, &[]),
&[0, 1],
None,
)
.unwrap_err();
assert!(matches!(
error,
SupportTauError::SummandIndexCount {
indices: 2,
summands: 3
}
));
}
fn f8_module(algebra: &Arc<Algebra>, field: PrimeField) -> Module {
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());
Module::new(
algebra.clone(),
vec![3, 3],
vec![DenseMat::identity(3), companion],
)
.expect("a Kronecker representation is a module")
}
#[test]
fn the_f8_module_reaches_the_tau_rigidity_condition() {
let field = f2();
let algebra = kronecker(2, field);
let w = f8_module(&algebra, field);
let decomposition = basic(&w);
assert_eq!(decomposition.len(), 1);
assert_eq!(decomposition.summands()[0].residue_degree(), 3);
assert_eq!(decomposition.summands()[0].endo().dim(), 3);
let translate = tau(&w).expect("kronecker translates");
assert!(!translate.is_zero(), "W is not projective");
assert_eq!(translate.dim_vector(), &[3, 3]);
assert!(matches!(
is_isomorphic(&w, &translate),
Ok(IsoOutcome::Isomorphic(_))
));
assert_eq!(hom_dim(&w, &translate).unwrap(), 3);
let alone = expect_rejection(
SupportTauTiltingPair::classify(basic(&w), support(&algebra, &[]))
.expect("kronecker translates"),
);
assert_eq!(alone.condition(), 3);
match &alone {
PairRejection::NotTauRigid(witness) => {
assert_eq!(witness.source().dim_vector(), &[3, 3]);
assert_eq!(witness.translate().dim_vector(), &[3, 3]);
assert!(witness.verify());
}
other => panic!("expected a tau-rigidity failure, got {other}"),
}
let p0 = Module::projective(&algebra, 0);
let candidate = sum(&algebra, &[&w, &p0]);
assert_eq!(basic(&candidate).len() + support(&algebra, &[]).len(), 2);
let rejection = expect_rejection(
SupportTauTiltingPair::classify(basic(&candidate), support(&algebra, &[]))
.expect("kronecker translates"),
);
assert_eq!(rejection.condition(), 3);
match &rejection {
PairRejection::NotTauRigid(witness) => {
assert_eq!(witness.translate().dim_vector(), &[3, 3]);
assert!(witness.verify());
}
other => panic!("expected a tau-rigidity failure, got {other}"),
}
}
#[test]
fn a_duplicated_pair_fails_verification() {
let field = f5();
let algebra = linear_an(2, field);
let catalog = IndecomposableCatalog::dynkin(&algebra).expect("A_2 is Dynkin");
for (index, dim_vectors, vertices) in [
(0usize, Vec::new(), vec![0u32, 1]),
(4, vec![vec![1, 0], vec![1, 1]], Vec::new()),
] {
let mut enumeration = enumerate_over_catalog(&catalog).expect("A_2 enumerates");
assert_eq!(enumeration.len(), 5);
assert!(enumeration.verify());
let duplicate = {
let pair = &enumeration.pairs()[index];
assert_eq!(pair.module().dim_vectors(), dim_vectors);
assert_eq!(pair.projective().vertices(), vertices);
let module = BasicDecomposition::new(pair.module().module())
.expect("the module part of a pair is basic");
let projective = ProjectiveSupport::new(&algebra, pair.projective().vertices())
.expect("the support of a pair is in range");
SupportTauTiltingPair::new(module, projective)
.expect("A_2 translates")
.expect("a rebuilt pair is a pair")
};
assert!(duplicate.verify(), "the duplicate is honest on its own");
enumeration.pairs.push(duplicate);
assert_eq!(enumeration.len(), 6);
assert!(!enumeration.verify(), "a duplicate of pair {index} passed");
}
}
#[test]
fn a_tampered_almost_complete_pair_fails_verification() {
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 two = sum(&algebra, &[&p0, &p1]);
let almost = |m: &Module| {
AlmostCompletePair::new(basic(m), support(&algebra, &[]))
.expect("A_3 translates")
.expect("a sum of two projectives is almost complete")
};
let pair = almost(&two);
assert!(pair.verify());
assert_eq!(pair.module().module().dim_vector(), &[1, 2, 2]);
assert_eq!(pair.omitted_vertex(), None);
assert!(pair.projective().is_empty());
let donor = almost(&sum(&algebra, &[&p1, &p2]));
assert!(donor.verify(), "the donor is honest");
assert_eq!(donor.module().module().dim_vector(), &[0, 1, 2]);
assert_eq!(donor.omitted_vertex(), Some(0));
assert!(donor.projective().is_empty());
let mut moved = almost(&sum(&algebra, &[&p1, &p2]));
moved.omitted = Some(1);
assert!(!moved.verify());
let mut forged = almost(&two);
assert_eq!(
donor.rigid().summands().len(),
forged.rigid.summands().len()
);
forged.rigid = donor.rigid().clone();
assert!(!forged.verify(), "over F_{}", field.modulus());
}
}
}