auslander 0.8.0

Computational representation theory of finite-dimensional bound quiver algebras
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
//! Chain Hom spaces and homotopy quotients.

use crate::complex::CheckedComplex;
use crate::field::Fp;
use crate::homspace::{HomSpace, deterministic_complement, row_times, scale_morphism, stack_rows};
use crate::linalg::DenseMat;

use super::chain::{
    ChainHomotopy, ChainMap, ChainMapError, agrees_after_padding, checked_union_range, padded_pair,
    rebase_morphism, same_complex_data, shifted_complex,
};
use super::complex::{BoundedComplex, BoundedComplexError, zero_between};

/// A deterministic basis of chain maps between two bounded complexes.
#[derive(Clone, Debug)]
pub struct ChainHomSpace {
    source: BoundedComplex,
    target: BoundedComplex,
    components: Vec<HomSpace>,
    flat: DenseMat,
}

fn chain_flat(map: &ChainMap, spaces: &[HomSpace]) -> Vec<Fp> {
    let mut row = Vec::with_capacity(spaces.iter().map(HomSpace::dim).sum());
    for (component, space) in map.components.iter().zip(spaces) {
        let component = if component.source().ptr_eq(space.source())
            && component.target().ptr_eq(space.target())
        {
            component.clone()
        } else {
            rebase_morphism(component, space.source(), space.target())
        };
        row.extend(
            space
                .coords(&component)
                .expect("chain map component has matching endpoints"),
        );
    }
    row
}

fn chain_map_from_flat(
    source: &BoundedComplex,
    target: &BoundedComplex,
    spaces: &[HomSpace],
    row: &[Fp],
) -> ChainMap {
    let mut components = Vec::with_capacity(spaces.len());
    let mut offset = 0;
    for space in spaces {
        let end = offset + space.dim();
        components.push(space.morphism(&row[offset..end]));
        offset = end;
    }
    ChainMap::new(source, target, components)
        .expect("chain Hom kernel rows satisfy the chain equations")
}

fn chain_constraints(
    source: &BoundedComplex,
    target: &BoundedComplex,
    spaces: &[HomSpace],
) -> DenseMat {
    let width: usize = spaces.iter().map(HomSpace::dim).sum();
    let mut offsets = Vec::with_capacity(spaces.len());
    let mut cursor = 0;
    for space in spaces {
        offsets.push(cursor);
        cursor += space.dim();
    }
    let mut rows: Vec<Vec<Fp>> = Vec::new();
    for index in 1..source.len() {
        let equation = HomSpace::new(&source.terms[index], &target.terms[index - 1])
            .expect("chain equation endpoints share the algebra");
        let equation_dim = equation.dim();
        let mut contributions: Vec<Vec<Fp>> =
            vec![vec![source.terms[0].field().zero(); width]; equation_dim];
        for (variable_index, space) in spaces.iter().enumerate() {
            for basis_index in 0..space.dim() {
                let basis = space.basis_morphism(basis_index);
                let contribution = if variable_index == index - 1 {
                    source.differentials[index - 1]
                        .then(&basis)
                        .expect("source differential and component endpoints match")
                } else if variable_index == index {
                    scale_morphism(
                        &basis
                            .then(&target.differentials[index - 1])
                            .expect("component and target differential endpoints match"),
                        source.terms[0].field().neg(source.terms[0].field().one()),
                    )
                } else {
                    continue;
                };
                let coordinates = equation
                    .coords(&contribution)
                    .expect("a composite of module morphisms lies in the equation Hom space");
                for (row, value) in coordinates.into_iter().enumerate() {
                    contributions[row][offsets[variable_index] + basis_index] = value;
                }
            }
        }
        rows.extend(contributions);
    }
    DenseMat::from_rows_with_cols(&rows, width)
}

fn homotopy_rows(
    source: &BoundedComplex,
    target: &BoundedComplex,
    spaces: &[HomSpace],
    ambient: &DenseMat,
) -> DenseMat {
    let field = source.terms[0].field();
    let mut rows = Vec::new();
    for index in 0..source.len().saturating_sub(1) {
        let space = HomSpace::new(&source.terms[index], &target.terms[index + 1])
            .expect("homotopy endpoints share the algebra");
        for basis_index in 0..space.dim() {
            let mut components = Vec::with_capacity(source.len().saturating_sub(1));
            for j in 0..source.len().saturating_sub(1) {
                let source_term = &source.terms[j];
                let target_term = &target.terms[j + 1];
                components.push(if j == index {
                    space.basis_morphism(basis_index)
                } else {
                    zero_between(source_term, target_term)
                });
            }
            let homotopy = ChainHomotopy::new(source, target, components)
                .expect("homotopy basis components have matching endpoints");
            let boundary = homotopy
                .boundary()
                .expect("homotopy boundary is a chain map");
            rows.push(chain_flat(&boundary, spaces));
        }
    }
    let inner = DenseMat::from_rows_with_cols(&rows, ambient.cols());
    inner.row_space_basis(&field)
}

impl ChainHomSpace {
    /// Builds the chain-map Hom space by solving the chain equations.
    pub fn new(
        source: &BoundedComplex,
        target: &BoundedComplex,
    ) -> Result<ChainHomSpace, ChainMapError> {
        let range = checked_union_range(source, target)?;
        let (source, target) = padded_pair(source, target, range)?;
        let components: Vec<HomSpace> = source
            .terms
            .iter()
            .zip(&target.terms)
            .map(|(source, target)| HomSpace::new(source, target).expect("algebras were checked"))
            .collect();
        let constraints = chain_constraints(&source, &target, &components);
        let flat = constraints.kernel_basis(&source.terms[0].field());
        Ok(ChainHomSpace {
            source: source.clone(),
            target: target.clone(),
            components,
            flat,
        })
    }

    accessor_methods! {
        /// The source complex.
        pub source() -> &BoundedComplex = |this| &this.source;
        /// The target complex.
        pub target() -> &BoundedComplex = |this| &this.target;
        /// The dimension of the chain-map space.
        pub dim() -> usize = |this| this.flat.rows();
        /// The chain-map basis in deterministic kernel order.
        pub basis_rows() -> &DenseMat = |this| &this.flat;
    }

    /// The basis chain map at `index`.
    pub fn basis_morphism(&self, index: usize) -> ChainMap {
        chain_map_from_flat(
            &self.source,
            &self.target,
            &self.components,
            self.flat.row(index),
        )
    }

    /// All basis chain maps in deterministic order.
    pub fn basis_iter(&self) -> impl Iterator<Item = ChainMap> + '_ {
        (0..self.dim()).map(|index| self.basis_morphism(index))
    }

    /// Rebuilds a chain map from coordinates in the chain-map basis.
    pub fn morphism(&self, coordinates: &[Fp]) -> ChainMap {
        assert_eq!(coordinates.len(), self.dim());
        let row = row_times(coordinates, &self.flat, &self.source.terms[0].field());
        chain_map_from_flat(&self.source, &self.target, &self.components, &row)
    }

    /// Coordinates of a chain map in the deterministic basis.
    pub fn coords(&self, map: &ChainMap) -> Result<Vec<Fp>, ChainMapError> {
        if !same_complex_data(&self.source, &map.source)
            || !same_complex_data(&self.target, &map.target)
        {
            return Err(ChainMapError::OutsideHomSpace);
        }
        let row = chain_flat(map, &self.components);
        self.flat
            .transpose()
            .solve(&row, &self.source.terms[0].field())
            .ok_or(ChainMapError::OutsideHomSpace)
    }

    /// Recomputes the chain-map equations and compares their deterministic basis.
    pub fn verify(&self) -> bool {
        let Ok(rebuilt) = ChainHomSpace::new(&self.source, &self.target) else {
            return false;
        };
        rebuilt.flat == self.flat
    }

    /// The quotient by null-homotopic chain maps.
    pub fn quotient(&self) -> Result<ChainHomQuotient, ChainMapError> {
        let null = homotopy_rows(&self.source, &self.target, &self.components, &self.flat);
        for row in 0..null.rows() {
            if self
                .flat
                .transpose()
                .solve(null.row(row), &self.source.terms[0].field())
                .is_none()
            {
                return Err(ChainMapError::OutsideHomSpace);
            }
        }
        let complement = deterministic_complement(&self.flat, &null, &self.source.terms[0].field());
        Ok(ChainHomQuotient {
            space: self.clone(),
            null,
            complement,
        })
    }
}

impl CheckedComplex {
    /// Converts a display-order checked complex to homological degree order.
    pub fn bounded(&self, lower: i32) -> Result<BoundedComplex, BoundedComplexError> {
        BoundedComplex::from_checked(self, lower)
    }
}

/// Hom chain maps modulo null-homotopic maps.
#[derive(Clone, Debug)]
pub struct ChainHomQuotient {
    space: ChainHomSpace,
    null: DenseMat,
    complement: DenseMat,
}

impl ChainHomQuotient {
    accessor_methods! {
        /// The source complex.
        pub source() -> &BoundedComplex = |this| this.space.source();
        /// The target complex.
        pub target() -> &BoundedComplex = |this| this.space.target();
        /// The quotient dimension.
        pub dim() -> usize = |this| this.complement.rows();
        /// The null-homotopic subspace in component coordinates.
        pub null_homotopic_basis() -> &DenseMat = |this| &this.null;
        /// The deterministic quotient complement in component coordinates.
        pub complement_basis() -> &DenseMat = |this| &this.complement;
    }

    /// Recomputes the ambient space, null-homotopic subspace, and complement.
    pub fn verify(&self) -> bool {
        self.space.verify()
            && self.space.quotient().is_ok_and(|rebuilt| {
                rebuilt.null == self.null && rebuilt.complement == self.complement
            })
    }

    /// Rebuilds a quotient representative from complement coordinates.
    pub fn representative(&self, coordinates: &[Fp]) -> ChainMap {
        assert_eq!(coordinates.len(), self.dim());
        let row = row_times(
            coordinates,
            &self.complement,
            &self.space.source.terms[0].field(),
        );
        chain_map_from_flat(
            &self.space.source,
            &self.space.target,
            &self.space.components,
            &row,
        )
    }

    /// Reduces a chain map to quotient coordinates and a null-homotopic remainder.
    pub fn reduce(&self, map: &ChainMap) -> Result<(Vec<Fp>, ChainMap), ChainMapError> {
        if !same_complex_data(&self.space.source, &map.source)
            || !same_complex_data(&self.space.target, &map.target)
        {
            return Err(ChainMapError::OutsideHomSpace);
        }
        let field = self.space.source.terms[0].field();
        let row = chain_flat(map, &self.space.components);
        let stacked = stack_rows(&[&self.complement, &self.null], self.complement.cols());
        let Some(coordinates) = stacked.transpose().solve(&row, &field) else {
            return Err(ChainMapError::OutsideHomSpace);
        };
        let quotient_coordinates = coordinates[..self.complement.rows()].to_vec();
        let null_row = row_times(&coordinates[self.complement.rows()..], &self.null, &field);
        Ok((
            quotient_coordinates,
            chain_map_from_flat(
                &self.space.source,
                &self.space.target,
                &self.space.components,
                &null_row,
            ),
        ))
    }
}

/// The degree-`q` chain Hom space obtained from `target.shift(q)`.
#[derive(Clone, Debug)]
pub struct HomotopyHom {
    degree: i32,
    source: BoundedComplex,
    target: BoundedComplex,
    shifted_target: BoundedComplex,
    space: ChainHomSpace,
}

impl HomotopyHom {
    /// Builds degree-`q` chain maps and retains the unshifted target.
    pub fn new(
        source: &BoundedComplex,
        target: &BoundedComplex,
        degree: i32,
    ) -> Result<HomotopyHom, ChainMapError> {
        let shifted_target = shifted_complex(target, degree)?;
        let space = ChainHomSpace::new(source, &shifted_target)?;
        Ok(HomotopyHom {
            degree,
            source: source.clone(),
            target: target.clone(),
            shifted_target,
            space,
        })
    }

    accessor_methods! {
        /// The retained degree `q`.
        pub degree() -> i32 = |this| this.degree;
        /// The unshifted source complex.
        pub source() -> &BoundedComplex = |this| &this.source;
        /// The unshifted target complex.
        pub target() -> &BoundedComplex = |this| &this.target;
        /// The target complex used by the degree-zero chain-map solver.
        pub shifted_target() -> &BoundedComplex = |this| &this.shifted_target;
        /// The normalized degree-zero chain Hom space.
        pub chain_space() -> &ChainHomSpace = |this| &this.space;
        /// The dimension of the degree-`q` chain-map space.
        pub dim() -> usize = |this| this.space.dim();
        /// The deterministic cycle basis in component coordinates.
        pub basis_rows() -> &DenseMat = |this| this.space.basis_rows();
    }

    /// The basis degree-`q` chain map at `index`.
    pub fn basis_morphism(&self, index: usize) -> ChainMap {
        self.space.basis_morphism(index)
    }

    /// All basis degree-`q` chain maps in deterministic order.
    pub fn basis_iter(&self) -> impl Iterator<Item = ChainMap> + '_ {
        self.space.basis_iter()
    }

    /// Rebuilds a degree-`q` chain map from deterministic coordinates.
    pub fn morphism(&self, coordinates: &[Fp]) -> ChainMap {
        self.space.morphism(coordinates)
    }

    /// Coordinates of a degree-`q` chain map in the deterministic basis.
    pub fn coords(&self, map: &ChainMap) -> Result<Vec<Fp>, ChainMapError> {
        self.space.coords(map)
    }

    /// Recomputes the shift and cycle basis stored by this value.
    pub fn verify(&self) -> bool {
        let Ok(shifted_target) = shifted_complex(&self.target, self.degree) else {
            return false;
        };
        agrees_after_padding(&self.source, self.space.source())
            && self.shifted_target.agrees_with(&shifted_target)
            && agrees_after_padding(&self.shifted_target, self.space.target())
            && self.space.verify()
    }

    /// Returns the quotient by null-homotopic degree-`q` maps.
    pub fn quotient(&self) -> Result<HomotopyHomQuotient, ChainMapError> {
        Ok(HomotopyHomQuotient {
            hom: self.clone(),
            quotient: self.space.quotient()?,
        })
    }
}

/// Degree-`q` chain Hom modulo null-homotopic maps.
#[derive(Clone, Debug)]
pub struct HomotopyHomQuotient {
    hom: HomotopyHom,
    quotient: ChainHomQuotient,
}

impl HomotopyHomQuotient {
    accessor_methods! {
        /// The degree-`q` Hom value behind this quotient.
        pub hom() -> &HomotopyHom = |this| &this.hom;
        /// The retained degree `q`.
        pub degree() -> i32 = |this| this.hom.degree();
        /// The unshifted source complex.
        pub source() -> &BoundedComplex = |this| this.hom.source();
        /// The unshifted target complex.
        pub target() -> &BoundedComplex = |this| this.hom.target();
        /// The shifted target used by the chain-map solver.
        pub shifted_target() -> &BoundedComplex = |this| this.hom.shifted_target();
        /// The quotient dimension.
        pub dim() -> usize = |this| this.quotient.dim();
        /// The null-homotopic basis in component coordinates.
        pub null_homotopic_basis() -> &DenseMat = |this| this.quotient.null_homotopic_basis();
        /// The deterministic quotient complement in component coordinates.
        pub complement_basis() -> &DenseMat = |this| this.quotient.complement_basis();
    }

    /// Recomputes the shift, cycle basis, boundary basis, and complement.
    pub fn verify(&self) -> bool {
        self.hom.verify()
            && self.quotient.verify()
            && agrees_after_padding(self.hom.source(), self.quotient.source())
            && agrees_after_padding(self.hom.shifted_target(), self.quotient.target())
    }

    /// Rebuilds a quotient representative from complement coordinates.
    pub fn representative(&self, coordinates: &[Fp]) -> ChainMap {
        self.quotient.representative(coordinates)
    }

    /// Reduces a degree-`q` chain map to class coordinates and a null map.
    pub fn reduce(&self, map: &ChainMap) -> Result<(Vec<Fp>, ChainMap), ChainMapError> {
        self.quotient.reduce(map)
    }
}

impl ChainMap {
    /// Whether this map represents zero modulo chain homotopy.
    pub fn is_null_homotopic(&self) -> Result<bool, ChainMapError> {
        let quotient = ChainHomSpace::new(&self.source, &self.target)
            .map_err(|_| ChainMapError::OutsideHomSpace)?
            .quotient()?;
        Ok(quotient.reduce(self)?.0.iter().all(|x| x.is_zero()))
    }
}

/// A short name for the bounded homological complex type.
pub type DegreeComplex = BoundedComplex;

/// A short name for a chain homotopy.
pub type Homotopy = ChainHomotopy;