use std::sync::Arc;
use crate::algebra::{Algebra, BasisIdx};
use crate::field::{Fp, PrimeField};
use crate::hom::{Morphism, matrix_is_zero};
use crate::linalg::DenseMat;
use crate::profile::{Site, hit};
use crate::quiver::{ArrowId, PathWord, QuiverError};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ModuleError {
DimsLengthMismatch { expected: usize, got: usize },
MapCountMismatch { expected: usize, got: usize },
MapShapeMismatch {
arrow: ArrowId,
expected: (usize, usize),
got: (usize, usize),
},
NonCanonicalEntry {
arrow: ArrowId,
row: usize,
col: usize,
},
RelationActsNonzero { index: usize },
}
display_error! { error ModuleError {
Self::DimsLengthMismatch { expected, got } => "dims has {got} entries, quiver has {expected} vertices";
Self::MapCountMismatch { expected, got } => "maps has {got} matrices, quiver has {expected} arrows";
Self::MapShapeMismatch { arrow, expected, got } => "map for arrow {} is {}x{}, expected {}x{}", arrow.0, got.0, got.1, expected.0, expected.1;
Self::NonCanonicalEntry { arrow, row, col } => "map for arrow {} has a non-canonical entry at ({row}, {col}) for the algebra's field", arrow.0;
Self::RelationActsNonzero { index } => "relation {index} acts as a nonzero matrix";
} }
#[derive(Clone, Debug)]
pub struct Module(Arc<ModuleInner>);
#[derive(Debug)]
struct ModuleInner {
algebra: Arc<Algebra>,
dims: Vec<usize>,
maps: Vec<DenseMat>,
}
fn zero_maps(algebra: &Algebra, dims: &[usize]) -> Vec<DenseMat> {
let quiver = algebra.quiver();
(0..quiver.num_arrows())
.map(|i| {
let arrow = ArrowId(i as u32);
DenseMat::zero(
dims[quiver.source(arrow) as usize],
dims[quiver.target(arrow) as usize],
)
})
.collect()
}
fn basis_data(
algebra: &Arc<Algebra>,
vertex: u32,
incoming: bool,
kind: &str,
) -> (Vec<usize>, Vec<usize>) {
let quiver = algebra.quiver();
assert!(
vertex < quiver.num_vertices(),
"{kind}: vertex {vertex} out of range"
);
let mut positions = vec![usize::MAX; algebra.dim()];
let mut dims = vec![0usize; quiver.num_vertices() as usize];
for w in 0..quiver.num_vertices() {
let component = if incoming {
algebra.paths_between(w, vertex)
} else {
algebra.paths_between(vertex, w)
};
dims[w as usize] = component.len();
for (index, &basis) in component.iter().enumerate() {
positions[basis] = index;
}
}
(dims, positions)
}
pub(crate) fn same_representation(a: &Module, b: &Module) -> bool {
Arc::ptr_eq(a.algebra(), b.algebra())
&& a.dim_vector() == b.dim_vector()
&& a.0.maps == b.0.maps
}
pub(crate) fn same_morphism_data(a: &Morphism, b: &Morphism) -> bool {
same_representation(a.source(), b.source())
&& same_representation(a.target(), b.target())
&& (0..a.source().algebra().quiver().num_vertices()).all(|v| a.map_at(v) == b.map_at(v))
}
pub(crate) fn same_slice<T>(left: &[T], right: &[T], same: impl Fn(&T, &T) -> bool) -> bool {
left.len() == right.len() && left.iter().zip(right).all(|(a, b)| same(a, b))
}
impl Module {
pub fn new(
algebra: Arc<Algebra>,
dims: Vec<usize>,
maps: Vec<DenseMat>,
) -> Result<Module, ModuleError> {
hit(Site::ModuleNew);
let field = algebra.field();
let quiver = algebra.quiver();
let num_vertices = quiver.num_vertices() as usize;
if dims.len() != num_vertices {
return Err(ModuleError::DimsLengthMismatch {
expected: num_vertices,
got: dims.len(),
});
}
if maps.len() != quiver.num_arrows() {
return Err(ModuleError::MapCountMismatch {
expected: quiver.num_arrows(),
got: maps.len(),
});
}
for (i, map) in maps.iter().enumerate() {
let arrow = ArrowId(i as u32);
let expected = (
dims[quiver.source(arrow) as usize],
dims[quiver.target(arrow) as usize],
);
let got = (map.rows(), map.cols());
if got != expected {
return Err(ModuleError::MapShapeMismatch {
arrow,
expected,
got,
});
}
if let Some((row, col)) = map.first_noncanonical(&field) {
return Err(ModuleError::NonCanonicalEntry { arrow, row, col });
}
}
for (index, relation) in algebra.relations().iter().enumerate() {
hit(Site::ModuleRelationCheck);
let source = relation.source() as usize;
let target = relation.target() as usize;
let mut acc = DenseMat::zero(dims[source], dims[target]);
for (coeff, word) in relation.terms() {
let mut action = DenseMat::identity(dims[source]);
for &a in word.arrows() {
action = action.mul(&maps[a.index()], &field);
}
acc.add_scaled_assign(&action, *coeff, &field);
}
if !matrix_is_zero(&acc) {
return Err(ModuleError::RelationActsNonzero { index });
}
}
Ok(Module(Arc::new(ModuleInner {
algebra,
dims,
maps,
})))
}
accessor_methods! {
pub ptr_eq(other: &Module) -> bool = |this| Arc::ptr_eq(&this.0, &other.0);
pub(crate) addr() -> usize = |this| Arc::as_ptr(&this.0) as usize;
}
pub fn zero(algebra: &Arc<Algebra>) -> Module {
let dims = vec![0; algebra.quiver().num_vertices() as usize];
let maps = zero_maps(algebra, &dims);
Module::new(algebra.clone(), dims, maps).expect("the zero module is a module")
}
pub fn simple(algebra: &Arc<Algebra>, v: u32) -> Module {
let quiver = algebra.quiver();
assert!(v < quiver.num_vertices(), "simple: vertex {v} out of range");
let dims: Vec<usize> = (0..quiver.num_vertices())
.map(|w| usize::from(w == v))
.collect();
let maps = zero_maps(algebra, &dims);
Module::new(algebra.clone(), dims, maps).expect("S_v is a module")
}
pub fn projective(algebra: &Arc<Algebra>, v: u32) -> Module {
hit(Site::ModuleProjective);
let quiver = algebra.quiver();
let (dims, pos) = basis_data(algebra, v, false, "projective");
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (s, t) = (quiver.source(a), quiver.target(a));
let mut mat = DenseMat::zero(dims[s as usize], dims[t as usize]);
for (row, &p) in algebra.paths_between(v, s).iter().enumerate() {
for &(q, c) in algebra.right_mul(p, a) {
mat.set(row, pos[q], c);
}
}
mat
})
.collect();
Module::new(algebra.clone(), dims, maps).expect("P_v is a module")
}
pub fn injective(algebra: &Arc<Algebra>, v: u32) -> Module {
hit(Site::ModuleInjective);
let quiver = algebra.quiver();
let (dims, pos) = basis_data(algebra, v, true, "injective");
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (s, t) = (quiver.source(a), quiver.target(a));
let mut mat = DenseMat::zero(dims[s as usize], dims[t as usize]);
for (col, &p) in algebra.paths_between(t, v).iter().enumerate() {
for &(q, c) in algebra.left_mul(a, p) {
mat.set(pos[q], col, c);
}
}
mat
})
.collect();
Module::new(algebra.clone(), dims, maps).expect("I_v is a module")
}
accessor_methods! {
pub algebra() -> &Arc<Algebra> = |this| &this.0.algebra;
pub field() -> PrimeField = |this| this.0.algebra.field();
pub dim_vector() -> &[usize] = |this| &this.0.dims;
pub dim_at(v: u32) -> usize = |this| this.0.dims[v as usize];
pub total_dim() -> usize = |this| this.0.dims.iter().sum();
pub is_zero() -> bool = |this| this.0.dims.iter().all(|&d| d == 0);
pub map(a: ArrowId) -> &DenseMat = |this| &this.0.maps[a.index()];
}
pub fn word_action(&self, word: &PathWord) -> Result<DenseMat, QuiverError> {
hit(Site::WordAction);
word.validate_in(self.0.algebra.quiver())?;
let field = self.field();
let mut acc = DenseMat::identity(self.0.dims[word.source() as usize]);
for &a in word.arrows() {
acc = acc.mul(&self.0.maps[a.index()], &field);
}
Ok(acc)
}
pub fn element_action(&self, terms: &[(BasisIdx, Fp)]) -> DenseMat {
hit(Site::ElementAction);
assert!(!terms.is_empty(), "element_action: terms are empty");
let basis = self.0.algebra.basis();
let source = basis[terms[0].0].source();
let target = basis[terms[0].0].target();
let field = self.field();
let mut acc = DenseMat::zero(self.0.dims[source as usize], self.0.dims[target as usize]);
for &(index, coeff) in terms {
let word = &basis[index];
assert!(
word.source() == source && word.target() == target,
"element_action: terms mix sources or targets"
);
let action = self
.word_action(word)
.expect("algebra basis words are valid in their own quiver");
acc.add_scaled_assign(&action, coeff, &field);
}
acc
}
}
pub fn direct_sum(summands: &[&Module]) -> (Module, Vec<Morphism>, Vec<Morphism>) {
hit(Site::DirectSum);
assert!(!summands.is_empty(), "direct_sum: needs a summand");
let first = summands[0];
assert!(
summands[1..]
.iter()
.all(|s| Arc::ptr_eq(first.algebra(), s.algebra())),
"direct_sum: mixed algebras"
);
let quiver = first.algebra().quiver();
let n = quiver.num_vertices() as usize;
let field = first.field();
let mut offsets = vec![vec![0usize; n]; summands.len()];
let mut dims = vec![0usize; n];
for (k, s) in summands.iter().enumerate() {
for (v, dim) in dims.iter_mut().enumerate() {
offsets[k][v] = *dim;
*dim += s.dim_vector()[v];
}
}
let maps = (0..quiver.num_arrows())
.map(|i| {
let a = ArrowId(i as u32);
let (u, w) = (quiver.source(a) as usize, quiver.target(a) as usize);
let mut mat = DenseMat::zero(dims[u], dims[w]);
for (k, s) in summands.iter().enumerate() {
let block = s.map(a);
for r in 0..block.rows() {
for c in 0..block.cols() {
mat.set(offsets[k][u] + r, offsets[k][w] + c, block.get(r, c));
}
}
}
mat
})
.collect();
let sum = Module::new(first.algebra().clone(), dims, maps)
.expect("a direct sum of modules is a module");
let mut inclusions = Vec::with_capacity(summands.len());
let mut projections = Vec::with_capacity(summands.len());
for (k, s) in summands.iter().enumerate() {
let mut incl = Vec::with_capacity(n);
let mut proj = Vec::with_capacity(n);
for (v, &offset) in offsets[k].iter().enumerate() {
let mut inc = DenseMat::zero(s.dim_vector()[v], sum.dim_vector()[v]);
let mut prj = DenseMat::zero(sum.dim_vector()[v], s.dim_vector()[v]);
for i in 0..s.dim_vector()[v] {
inc.set(i, offset + i, field.one());
prj.set(offset + i, i, field.one());
}
incl.push(inc);
proj.push(prj);
}
inclusions.push(Morphism::new_unchecked(s, &sum, incl));
projections.push(Morphism::new_unchecked(&sum, s, proj));
}
(sum, inclusions, projections)
}
pub(crate) fn summand_sum(
algebra: &Arc<Algebra>,
vertices: &[u32],
build: fn(&Arc<Algebra>, u32) -> Module,
) -> Module {
match vertices {
[] => Module::zero(algebra),
[vertex] => build(algebra, *vertex),
_ => {
let parts: Vec<Module> = vertices.iter().map(|&v| build(algebra, v)).collect();
direct_sum(&parts.iter().collect::<Vec<_>>()).0
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algebra::{
an_with_relations, commutative_square, cyclic_nakayama, dual_numbers, linear_an,
};
use crate::hom::{identity, zero_morphism};
fn f5() -> PrimeField {
PrimeField::new(5).unwrap()
}
fn mat(field: &PrimeField, rows: &[&[i64]]) -> DenseMat {
let rows: Vec<Vec<Fp>> = rows
.iter()
.map(|r| r.iter().map(|&v| field.elem(v)).collect())
.collect();
DenseMat::from_rows(&rows)
}
#[test]
fn invertible_loop_action_is_rejected() {
let a = dual_numbers(f5());
let result = Module::new(a, vec![1], vec![mat(&f5(), &[&[1]])]);
assert_eq!(
result.unwrap_err(),
ModuleError::RelationActsNonzero { index: 0 }
);
}
#[test]
fn nilpotent_loop_action_is_accepted() {
let a = dual_numbers(f5());
let m = Module::new(a, vec![2], vec![mat(&f5(), &[&[0, 1], &[0, 0]])]).unwrap();
assert_eq!(m.total_dim(), 2);
assert!(!m.is_zero());
}
#[test]
fn commutative_square_relation_is_enforced() {
let a = commutative_square(f5());
let one = mat(&f5(), &[&[1]]);
let zero = mat(&f5(), &[&[0]]);
let rejected = Module::new(
a.clone(),
vec![1, 1, 1, 1],
vec![one.clone(), one.clone(), one.clone(), zero],
);
assert_eq!(
rejected.unwrap_err(),
ModuleError::RelationActsNonzero { index: 0 }
);
let accepted = Module::new(
a,
vec![1, 1, 1, 1],
vec![one.clone(), one.clone(), one.clone(), one],
);
assert!(accepted.is_ok());
}
#[test]
fn wrong_dims_length_is_rejected() {
let a = linear_an(3, f5());
let result = Module::new(a, vec![1, 1], vec![DenseMat::zero(1, 1); 2]);
assert_eq!(
result.unwrap_err(),
ModuleError::DimsLengthMismatch {
expected: 3,
got: 2
}
);
}
#[test]
fn wrong_map_shape_is_rejected() {
let a = linear_an(3, f5());
let maps = vec![DenseMat::zero(1, 1), DenseMat::zero(2, 1)];
let result = Module::new(a, vec![1, 1, 1], maps);
assert_eq!(
result.unwrap_err(),
ModuleError::MapShapeMismatch {
arrow: ArrowId(1),
expected: (1, 1),
got: (2, 1)
}
);
}
#[test]
fn zero_module_has_dimension_zero() {
let a = linear_an(3, f5());
let z = Module::zero(&a);
assert!(z.is_zero());
assert_eq!(z.total_dim(), 0);
assert_eq!(z.dim_vector(), &[0, 0, 0]);
}
#[test]
fn word_action_multiplies_arrow_matrices_in_word_order() {
let a = linear_an(3, f5());
let field = f5();
let p0 = Module::projective(&a, 0);
let word =
PathWord::from_arrows(a.quiver(), &[ArrowId(0), ArrowId(1)]).expect("path a·b in A_3");
let expected = p0.map(ArrowId(0)).mul(p0.map(ArrowId(1)), &field);
assert_eq!(p0.word_action(&word), Ok(expected));
let trivial = PathWord::trivial(a.quiver(), 0).unwrap();
assert_eq!(p0.word_action(&trivial), Ok(DenseMat::identity(1)));
}
#[test]
fn word_action_rejects_a_word_from_another_quiver() {
let a = linear_an(3, f5());
let other = dual_numbers(f5());
let p0 = Module::projective(&a, 0);
let word = PathWord::from_arrows(other.quiver(), &[ArrowId(0)]).unwrap();
assert_eq!(
p0.word_action(&word),
Err(QuiverError::EndpointsDisagree {
stored: (0, 0),
computed: (0, 1),
})
);
}
#[test]
fn element_action_sums_scaled_word_actions() {
let field = f5();
let a = commutative_square(field);
let p0 = Module::projective(&a, 0);
let ab = a
.path_index(&PathWord::from_arrows(a.quiver(), &[ArrowId(0), ArrowId(1)]).unwrap())
.unwrap()
.unwrap();
let action = p0.element_action(&[(ab, field.elem(3))]);
let word_mat = p0.word_action(&a.basis()[ab]).expect("basis word is valid");
for r in 0..action.rows() {
for c in 0..action.cols() {
assert_eq!(
action.get(r, c),
field.mul(field.elem(3), word_mat.get(r, c))
);
}
}
}
#[test]
#[should_panic(expected = "mix sources")]
fn element_action_rejects_mixed_endpoints() {
let a = linear_an(3, f5());
let p0 = Module::projective(&a, 0);
p0.element_action(&[(0, f5().one()), (1, f5().one())]);
}
#[test]
fn non_canonical_entry_is_rejected_before_relation_checks() {
let a = dual_numbers(PrimeField::new(2).unwrap());
let maps = vec![mat(&f5(), &[&[3]])];
assert_eq!(
Module::new(a, vec![1], maps).unwrap_err(),
ModuleError::NonCanonicalEntry {
arrow: ArrowId(0),
row: 0,
col: 0,
}
);
}
#[test]
fn simple_is_one_dimensional_at_its_vertex() {
let a = an_with_relations(3, &[(0, 2)], f5()).unwrap();
for v in 0..3 {
let s = Module::simple(&a, v);
let expected: Vec<usize> = (0..3).map(|w| usize::from(w == v as usize)).collect();
assert_eq!(s.dim_vector(), expected.as_slice());
}
}
#[test]
fn projective_dim_vectors_are_cartan_rows() {
for algebra in [
linear_an(3, f5()),
an_with_relations(3, &[(0, 2)], f5()).unwrap(),
cyclic_nakayama(&[2, 2, 2], f5()).unwrap(),
commutative_square(f5()),
] {
let cartan = algebra.cartan_matrix();
for v in 0..algebra.quiver().num_vertices() {
let p = Module::projective(&algebra, v);
assert_eq!(p.dim_vector(), cartan[v as usize].as_slice(), "P_{v}");
}
}
}
#[test]
fn injective_dim_vectors_are_cartan_columns() {
for algebra in [
linear_an(3, f5()),
an_with_relations(3, &[(0, 2)], f5()).unwrap(),
cyclic_nakayama(&[2, 2, 2], f5()).unwrap(),
commutative_square(f5()),
] {
let cartan = algebra.cartan_matrix();
for v in 0..algebra.quiver().num_vertices() {
let i = Module::injective(&algebra, v);
let column: Vec<usize> = cartan.iter().map(|row| row[v as usize]).collect();
assert_eq!(i.dim_vector(), column.as_slice(), "I_{v}");
}
}
}
#[test]
fn a3_mod_ab_projective_p0_has_dimension_vector_1_1_0() {
let a = an_with_relations(3, &[(0, 2)], f5()).unwrap();
let p0 = Module::projective(&a, 0);
assert_eq!(p0.dim_vector(), &[1, 1, 0]);
}
#[test]
fn direct_sum_projections_split_inclusions() {
let a = linear_an(3, f5());
let p0 = Module::projective(&a, 0);
let p1 = Module::projective(&a, 1);
let s2 = Module::simple(&a, 2);
let parts = [&p0, &p1, &s2];
let (sum, inclusions, projections) = direct_sum(&parts);
for v in 0..3 {
assert_eq!(
sum.dim_at(v),
parts.iter().map(|m| m.dim_at(v)).sum::<usize>()
);
}
for (k, part) in parts.iter().enumerate() {
assert_eq!(
inclusions[k].then(&projections[k]).unwrap(),
identity(part),
"π_{k} ∘ ι_{k}"
);
for (j, other) in parts.iter().enumerate() {
if j != k {
assert_eq!(
inclusions[j].then(&projections[k]).unwrap(),
zero_morphism(other, part).unwrap(),
"π_{k} ∘ ι_{j}"
);
}
}
}
}
}