Skip to main content

auslander/ext/
space.rs

1//! Explicit Ext-space construction and class-coordinate reduction.
2
3use std::sync::Arc;
4
5use crate::field::Fp;
6use crate::hom::Morphism;
7use crate::homspace::{deterministic_complement, rref_coords_many, stack_rows};
8use crate::linalg::DenseMat;
9use crate::module::{Module, same_morphism_data, same_representation, same_slice};
10use crate::resolution::{ProjectiveResolution, resolve};
11
12use super::foundation::{
13    ExtError, check_pair, cochain_from_coordinates, coordinates, delta_matrix, hom_space_dim,
14    layout,
15};
16use super::product::ExtClass;
17
18/// Rejected Ext class input.
19#[derive(Clone, Debug, PartialEq, Eq)]
20pub enum ExtClassError {
21    /// The operands' spaces are not compatible: compatibility needs
22    /// pointer-equal sources, pointer-equal targets, and equal degrees.
23    IncompatibleSpaces,
24    /// The left class's target module is not the right class's source module
25    /// (by [`Module::ptr_eq`]), so the Yoneda product is undefined.
26    MiddleMismatch,
27    /// The sum of the two class degrees is not representable.
28    DegreeOverflow { left: usize, right: usize },
29    /// The cochain's source is not the space's cochain term (by
30    /// [`Module::ptr_eq`]).
31    SourceMismatch,
32    /// The cochain's target is not the space's target module (by
33    /// [`Module::ptr_eq`]).
34    TargetMismatch,
35    /// The cochain is not a cocycle: `d_{k+1}.then(f)` is nonzero. The field
36    /// holds the composite's coordinates in the degree `k + 1` cochain basis.
37    NotCocycle { composite: Vec<Fp> },
38    /// The coordinate vector's length is not the space's dimension.
39    CoordinateCountMismatch { expected: usize, got: usize },
40    /// The coordinate at this index is not a canonical element of the
41    /// modules' field.
42    NonCanonicalCoordinate { index: usize },
43    /// The identity class lives only in `Ext^0(M, M)`: degree 0 with
44    /// pointer-equal endpoints.
45    NotDegreeZeroEndo,
46    /// The left class's resolution prefix and the product space's prefix
47    /// disagree at this degree, in the term or in the differential into it.
48    /// Both come from [`resolve`] on the same module, so a disagreement is a
49    /// crate defect, not bad input.
50    ResolutionDisagreement { degree: usize },
51}
52
53display_error! { error ExtClassError {
54    Self::IncompatibleSpaces => "the classes live in incompatible Ext spaces";
55    Self::MiddleMismatch => "the left class's target module is not the right class's source module";
56    Self::DegreeOverflow { left, right } => "Ext degree sum {left} + {right} is not representable";
57    Self::SourceMismatch => "the cochain's source is not the space's cochain term";
58    Self::TargetMismatch => "the cochain's target is not the space's target module";
59    Self::NotCocycle { .. } => "the cochain is not a cocycle";
60    Self::CoordinateCountMismatch { expected, got } => "coordinate vector has {got} entries, the space has dimension {expected}";
61    Self::NonCanonicalCoordinate { index } => "coordinate {index} is not a canonical element of the modules' field";
62    Self::NotDegreeZeroEndo => "the identity class lives only in Ext^0(M, M)";
63    Self::ResolutionDisagreement { degree } => "two resolutions of one module disagree at degree {degree}; crate defect";
64} }
65
66pub(super) fn product_degree(left: usize, right: usize) -> Result<usize, ExtClassError> {
67    left.checked_add(right)
68        .filter(|&degree| degree != usize::MAX)
69        .ok_or(ExtClassError::DegreeOverflow { left, right })
70}
71
72pub(super) struct ExtSpaceInner {
73    pub(super) source: Module,
74    pub(super) target: Module,
75    pub(super) degree: usize,
76    // resolve(source, degree + 1); minimal, so recomputation gives the same
77    // matrices.
78    pub(super) resolution: ProjectiveResolution,
79    // P_k, or the zero module when the finite resolution ends before k.
80    pub(super) term: Module,
81    // RREF basis of Z^k = ker delta^k in generator-block coordinates.
82    pub(super) cocycles: DenseMat,
83    // RREF basis of B^k = im delta^{k-1}; zero rows at degree 0.
84    pub(super) coboundaries: DenseMat,
85    // Deterministic complement of B^k in Z^k.
86    pub(super) complement: DenseMat,
87    // One cocycle morphism P_k -> N per complement row.
88    pub(super) reps: Vec<Morphism>,
89}
90
91/// `Ext^k(M, N)` as an explicit vector space: the resolution prefix, RREF
92/// cocycle and coboundary bases in generator-block coordinates, the
93/// deterministic complement of the coboundaries inside the cocycles, and one
94/// representative cocycle per complement row.
95///
96/// Two spaces are compatible when their sources are [`Module::ptr_eq`], their
97/// targets are [`Module::ptr_eq`], and their degrees are equal. Every stored
98/// matrix is deterministic, so recomputed compatible spaces carry identical
99/// bases and class coordinates transport verbatim.
100///
101/// Cloning is cheap (a reference count bump).
102#[derive(Clone)]
103pub struct ExtSpace(pub(super) Arc<ExtSpaceInner>);
104
105debug_fields!(ExtSpace |this| {
106    "source_dim" => this.0.source.dim_vector();
107    "target_dim" => this.0.target.dim_vector();
108    "degree" => this.0.degree;
109    "dim" => this.dim();
110});
111
112impl ExtSpace {
113    /// Builds `Ext^k(m, n)` from the minimal resolution prefix
114    /// `resolve(m, k + 1)`. Zero modules give zero spaces. A finite resolution
115    /// that ends before degree `k` gives the zero space with the zero module
116    /// as cochain term. Errors when the modules do not share one algebra or
117    /// `k + 1` is not representable.
118    pub fn new(m: &Module, n: &Module, k: usize) -> Result<ExtSpace, ExtError> {
119        check_pair(m, n)?;
120        let field = m.field();
121        let steps = k
122            .checked_add(1)
123            .ok_or(ExtError::DegreeOverflow { degree: k })?;
124        let resolution = resolve(m, steps);
125        let (term, cocycles, coboundaries) = if k < resolution.terms.len() {
126            let term = resolution.terms[k].clone();
127            let lay = layout(&term);
128            let width = hom_space_dim(&lay, n);
129            let cocycles = if k + 1 < resolution.terms.len() {
130                let next_lay = layout(&resolution.terms[k + 1]);
131                let delta = delta_matrix(&resolution.maps[k], &term, &lay, &next_lay, n);
132                delta.left_kernel_basis(&field).into_row_space_basis(&field)
133            } else {
134                DenseMat::identity(width)
135            };
136            let coboundaries = if k == 0 {
137                DenseMat::zero(0, width)
138            } else {
139                let prev = &resolution.terms[k - 1];
140                let prev_lay = layout(prev);
141                delta_matrix(&resolution.maps[k - 1], prev, &prev_lay, &lay, n)
142                    .into_row_space_basis(&field)
143            };
144            (term, cocycles, coboundaries)
145        } else {
146            (
147                Module::zero(m.algebra()),
148                DenseMat::zero(0, 0),
149                DenseMat::zero(0, 0),
150            )
151        };
152        assert!(
153            rref_coords_many(&cocycles, &coboundaries, &field).is_some(),
154            "im delta^{} is not contained in ker delta^{k}; this is a bug in auslander",
155            k.wrapping_sub(1)
156        );
157        let complement = deterministic_complement(&cocycles, &coboundaries, &field);
158        let lay = layout(&term);
159        let reps = (0..complement.rows())
160            .map(|r| cochain_from_coordinates(&term, &lay, n, complement.row(r)))
161            .collect();
162        Ok(ExtSpace(Arc::new(ExtSpaceInner {
163            source: m.clone(),
164            target: n.clone(),
165            degree: k,
166            resolution,
167            term,
168            cocycles,
169            coboundaries,
170            complement,
171            reps,
172        })))
173    }
174
175    accessor_methods! {
176        /// `dim_Fp Ext^k(M, N)`: the number of complement rows. Equals
177        /// [`crate::ext::ext_dim`](m, n, k).
178        pub dim() -> usize = |this| this.0.complement.rows();
179        /// The source module `M`.
180        pub source() -> &Module = |this| &this.0.source;
181        /// The target module `N`.
182        pub target() -> &Module = |this| &this.0.target;
183        /// The cohomological degree `k`.
184        pub degree() -> usize = |this| this.0.degree;
185        /// The source of degree-`k` cochains: `P_k` of the minimal resolution, or
186        /// the zero module when the finite resolution ends before `k`.
187        pub cochain_term() -> &Module = |this| &this.0.term;
188        /// One representative cocycle `P_k -> N` per complement row, in row order.
189        pub representatives() -> &[Morphism] = |this| &this.0.reps;
190        /// The RREF basis of `Z^k = ker delta^k` in generator-block coordinates,
191        /// one vector per row.
192        pub cocycle_basis() -> &DenseMat = |this| &this.0.cocycles;
193        /// The RREF basis of `B^k = im delta^{k-1}` in generator-block
194        /// coordinates, one vector per row; no rows at degree 0.
195        pub coboundary_basis() -> &DenseMat = |this| &this.0.coboundaries;
196        /// The complement of `B^k` in `Z^k`, in scan order. Class coordinates
197        /// index these rows.
198        pub complement_basis() -> &DenseMat = |this| &this.0.complement;
199        /// The stored resolution prefix `resolve(source, degree + 1)`.
200        pub(crate) resolution() -> &ProjectiveResolution = |this| &this.0.resolution;
201    }
202
203    /// Whether class coordinates transport verbatim between the two spaces:
204    /// sources pointer-equal, targets pointer-equal, degrees equal.
205    pub fn is_compatible(&self, other: &ExtSpace) -> bool {
206        self.0.source.ptr_eq(&other.0.source)
207            && self.0.target.ptr_eq(&other.0.target)
208            && self.0.degree == other.0.degree
209    }
210
211    /// Whether the two compatible spaces carry the same stored data: the
212    /// resolution prefix term by term and differential by differential, the
213    /// cochain term, the cocycle, coboundary and complement bases, and the
214    /// representatives.
215    ///
216    /// Incompatible spaces are never equal. Terms and representatives are
217    /// compared entry by entry, because a recomputed space owns fresh module
218    /// values that no pointer test can match.
219    pub fn matches(&self, other: &ExtSpace) -> bool {
220        let (a, b) = (&*self.0, &*other.0);
221        self.is_compatible(other)
222            && a.resolution.agrees_with(&b.resolution)
223            && same_representation(&a.term, &b.term)
224            && a.cocycles == b.cocycles
225            && a.coboundaries == b.coboundaries
226            && a.complement == b.complement
227            && same_slice(&a.reps, &b.reps, same_morphism_data)
228    }
229
230    /// Whether every stored matrix equals a fresh [`ExtSpace::new`] over the
231    /// live endpoint modules, by [`ExtSpace::matches`].
232    ///
233    /// Rechecks that read this space (action matrices, socle, cocycle
234    /// reduction) use the stored resolution and bases, so a tampered space
235    /// would otherwise certify itself.
236    pub fn matches_recomputation(&self) -> bool {
237        let_or_false!(Ok(fresh) = ExtSpace::new(&self.0.source, &self.0.target, self.0.degree));
238        self.matches(&fresh)
239    }
240
241    /// The zero class of this space.
242    pub fn zero_class(&self) -> ExtClass {
243        ExtClass {
244            space: self.clone(),
245            coords: vec![Fp::ZERO; self.dim()],
246        }
247    }
248
249    /// The Yoneda unit: the class of the augmentation in `Ext^0(M, M)`.
250    /// Errors unless the space has degree 0 and pointer-equal endpoints.
251    pub fn identity_class(&self) -> Result<ExtClass, ExtClassError> {
252        if self.0.degree != 0 || !self.0.source.ptr_eq(&self.0.target) {
253            return Err(ExtClassError::NotDegreeZeroEndo);
254        }
255        self.class_from_cocycle(&self.0.resolution.augmentation)
256    }
257
258    /// The class of the cocycle `f: P_k -> N`: checks both endpoints by
259    /// [`Module::ptr_eq`], checks `d_{k+1}.then(f) = 0`, then reduces modulo
260    /// `B^k` by solving `f` against the complement rows stacked above the
261    /// coboundary basis and keeping the complement part.
262    pub fn class_from_cocycle(&self, f: &Morphism) -> Result<ExtClass, ExtClassError> {
263        let inner = &self.0;
264        if !f.source().ptr_eq(&inner.term) {
265            return Err(ExtClassError::SourceMismatch);
266        }
267        if !f.target().ptr_eq(&inner.target) {
268            return Err(ExtClassError::TargetMismatch);
269        }
270        let field = inner.source.field();
271        if inner.degree + 1 < inner.resolution.terms.len() {
272            let composite = inner.resolution.maps[inner.degree]
273                .then(f)
274                .expect("d_{k+1} targets the cochain term");
275            if !composite.is_zero() {
276                let next_lay = layout(&inner.resolution.terms[inner.degree + 1]);
277                return Err(ExtClassError::NotCocycle {
278                    composite: coordinates(&composite, &next_lay, &inner.target),
279                });
280            }
281        }
282        let lay = layout(&inner.term);
283        let f_coords = coordinates(f, &lay, &inner.target);
284        let stacked = stack_rows(
285            &[&inner.complement, &inner.coboundaries],
286            inner.complement.cols(),
287        );
288        let x = stacked
289            .transpose()
290            .solve(&f_coords, &field)
291            .expect("a cocycle lies in the span of the complement plus the coboundaries; this is a bug in auslander");
292        Ok(ExtClass {
293            space: self.clone(),
294            coords: x[..inner.complement.rows()].to_vec(),
295        })
296    }
297
298    /// A copy of the space with the three stored bases replaced and the
299    /// representatives rebuilt from the new complement.
300    ///
301    /// Test helper for the mutation corpus: the result is an `ExtSpace` value
302    /// that no constructor would produce, so [`ExtSpace::matches_recomputation`]
303    /// must reject it.
304    #[cfg(test)]
305    pub(crate) fn with_bases(
306        &self,
307        cocycles: DenseMat,
308        coboundaries: DenseMat,
309        complement: DenseMat,
310    ) -> ExtSpace {
311        let inner = &self.0;
312        let lay = layout(&inner.term);
313        let reps = (0..complement.rows())
314            .map(|r| cochain_from_coordinates(&inner.term, &lay, &inner.target, complement.row(r)))
315            .collect();
316        self.with_parts(cocycles, coboundaries, complement, reps)
317    }
318
319    /// A copy of the space with the representatives replaced and every basis
320    /// kept. Test helper for the mutation corpus, as [`ExtSpace::with_bases`].
321    #[cfg(test)]
322    pub(crate) fn with_representatives(&self, reps: Vec<Morphism>) -> ExtSpace {
323        let inner = &self.0;
324        self.with_parts(
325            inner.cocycles.clone(),
326            inner.coboundaries.clone(),
327            inner.complement.clone(),
328            reps,
329        )
330    }
331
332    #[cfg(test)]
333    fn with_parts(
334        &self,
335        cocycles: DenseMat,
336        coboundaries: DenseMat,
337        complement: DenseMat,
338        reps: Vec<Morphism>,
339    ) -> ExtSpace {
340        let inner = &self.0;
341        ExtSpace(Arc::new(ExtSpaceInner {
342            source: inner.source.clone(),
343            target: inner.target.clone(),
344            degree: inner.degree,
345            resolution: ProjectiveResolution {
346                terms: inner.resolution.terms.clone(),
347                maps: inner.resolution.maps.clone(),
348                augmentation: inner.resolution.augmentation.clone(),
349                end: inner.resolution.end,
350            },
351            term: inner.term.clone(),
352            cocycles,
353            coboundaries,
354            complement,
355            reps,
356        }))
357    }
358
359    /// The class with the given coordinates over the complement basis.
360    /// Errors on a wrong length and on entries that are not canonical
361    /// elements of the modules' field.
362    pub fn class_from_coordinates(&self, coords: &[Fp]) -> Result<ExtClass, ExtClassError> {
363        if coords.len() != self.dim() {
364            return Err(ExtClassError::CoordinateCountMismatch {
365                expected: self.dim(),
366                got: coords.len(),
367            });
368        }
369        let modulus = self.0.source.field().modulus();
370        if let Some(index) = coords.iter().position(|c| c.raw() >= modulus) {
371            return Err(ExtClassError::NonCanonicalCoordinate { index });
372        }
373        Ok(ExtClass {
374            space: self.clone(),
375            coords: coords.to_vec(),
376        })
377    }
378}