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
//! Checked short exact sequences: construction from an `Ext^1` class, recovery
//! of that class, and split status with a proof either way.
//!
//! [`ShortExactSequence::new`] checks exactness one vertex at a time. The
//! inclusion is mono by rank, the projection is epi by rank, the composite is
//! zero, and the dimensions add. Those four facts together force image equals
//! kernel, so nothing else is computed.
//!
//! [`ShortExactSequence::split_status`] solves the retraction system in a fixed
//! order. The unknowns are the entries of `r: E -> N`, vertex-major then
//! row-major. The equations are the commuting squares in (arrow, row, column)
//! lexicographic order, then the `iota.then(r) = id` constraints, again
//! vertex-major then row-major. A solution gives a [`SplitWitness`]. An
//! inconsistent system gives a [`NonSplitWitness`] holding a dual vector `y`
//! with `y A = 0` and `y b = 1`. That `y` is the identity block of the pivot
//! row of the RREF of the augmented system `[A | b | I]`. The pivot of that row
//! sits in the `b` column, and RREF makes it 1, so `y b = 1` holds and fixes
//! the scale of `y`. No further normalization is needed. Either witness
//! rechecks by multiplication alone.
mod construction;
mod helpers;
mod splitting;
use crate::field::Fp;
use crate::hom::{Morphism, matrix_is_zero};
use crate::module::Module;
/// Rejected short exact sequence input.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum SequenceError {
/// The inclusion's target is not the projection's source (by
/// [`Module::ptr_eq`]).
EndpointMismatch,
/// The inclusion's rank at this vertex is below the sub dimension, so the
/// inclusion is not mono.
NotMono { vertex: u32 },
/// The projection's rank at this vertex is below the quotient dimension,
/// so the projection is not epi.
NotEpi { vertex: u32 },
/// The composite inclusion-then-projection is nonzero at this vertex.
CompositeNonzero { vertex: u32 },
/// `dim middle != dim sub + dim quotient` at this vertex.
DimensionMismatch { vertex: u32 },
/// The class or space has the wrong cohomological degree.
WrongDegree { expected: usize, got: usize },
/// The space's source module is not this sequence's quotient (by
/// [`Module::ptr_eq`]).
SpaceSourceMismatch,
/// The space's target module is not this sequence's sub (by
/// [`Module::ptr_eq`]).
SpaceTargetMismatch,
}
display_error! { error SequenceError {
Self::EndpointMismatch => "the inclusion's target is not the projection's source";
Self::NotMono { vertex } => "the inclusion is not mono at vertex {vertex}";
Self::NotEpi { vertex } => "the projection is not epi at vertex {vertex}";
Self::CompositeNonzero { vertex } => "the composite is nonzero at vertex {vertex}";
Self::DimensionMismatch { vertex } => "the middle dimension is not sub plus quotient at vertex {vertex}";
Self::WrongDegree { expected, got } => "degree is {got}, this operation needs degree {expected}";
Self::SpaceSourceMismatch => "the space's source module is not the sequence's quotient";
Self::SpaceTargetMismatch => "the space's target module is not the sequence's sub";
} }
/// A short exact sequence `0 -> sub -> middle -> quotient -> 0`, exact per
/// vertex by construction.
///
/// Fields are private; construction goes through [`ShortExactSequence::new`]
/// or [`ShortExactSequence::from_ext1`], so every value is exact.
#[derive(Clone, Debug)]
pub struct ShortExactSequence {
sub: Module,
middle: Module,
quotient: Module,
inclusion: Morphism,
projection: Morphism,
}
impl ShortExactSequence {
/// Builds the sequence after checking, one vertex at a time: the inclusion
/// is mono by rank, the projection is epi by rank, the composite is zero,
/// and `dim middle = dim sub + dim quotient`. Those four force exactness.
///
/// # Errors
/// [`SequenceError::EndpointMismatch`] when the inclusion's target is not
/// the projection's source, otherwise the per-vertex variant naming the
/// first vertex that fails.
pub fn new(
inclusion: Morphism,
projection: Morphism,
) -> Result<ShortExactSequence, SequenceError> {
if !inclusion.target().ptr_eq(projection.source()) {
return Err(SequenceError::EndpointMismatch);
}
let sub = inclusion.source().clone();
let middle = inclusion.target().clone();
let quotient = projection.target().clone();
let field = sub.field();
let nv = sub.algebra().quiver().num_vertices();
for v in 0..nv {
if inclusion.map_at(v).rank(&field) < sub.dim_at(v) {
return Err(SequenceError::NotMono { vertex: v });
}
}
for v in 0..nv {
if projection.map_at(v).rank(&field) < quotient.dim_at(v) {
return Err(SequenceError::NotEpi { vertex: v });
}
}
let composite = inclusion.then(&projection).expect("endpoints were checked");
for v in 0..nv {
if !matrix_is_zero(composite.map_at(v)) {
return Err(SequenceError::CompositeNonzero { vertex: v });
}
}
for v in 0..nv {
if middle.dim_at(v) != sub.dim_at(v) + quotient.dim_at(v) {
return Err(SequenceError::DimensionMismatch { vertex: v });
}
}
Ok(ShortExactSequence {
sub,
middle,
quotient,
inclusion,
projection,
})
}
accessor_methods! {
/// The sub module `N`.
pub sub() -> &Module = |this| &this.sub;
/// The middle module `E`.
pub middle() -> &Module = |this| &this.middle;
/// The quotient module `M`.
pub quotient() -> &Module = |this| &this.quotient;
/// The inclusion `N -> E`.
pub inclusion() -> &Morphism = |this| &this.inclusion;
/// The projection `E -> M`.
pub projection() -> &Morphism = |this| &this.projection;
}
}
/// The outcome of [`ShortExactSequence::split_status`]; each variant carries
/// its proof.
#[derive(Clone, Debug)]
pub enum SplitStatus {
/// The sequence splits, with the retraction and section that prove it.
Split(SplitWitness),
/// The sequence does not split, with the dual vector that proves the
/// retraction system inconsistent.
NonSplit(NonSplitWitness),
}
/// A retraction and section proving a sequence split.
#[derive(Clone, Debug)]
pub struct SplitWitness {
retraction: Morphism,
section: Morphism,
}
impl SplitWitness {
accessor_methods! {
/// The retraction `r: E -> N` with `iota.then(r) = id`.
pub retraction() -> &Morphism = |this| &this.retraction;
/// The section `s: M -> E` with `s.then(projection) = id`.
pub section() -> &Morphism = |this| &this.section;
}
}
/// A dual vector proving the retraction system inconsistent: `y A = 0` and
/// `y b = 1` for the system built in the fixed order.
#[derive(Clone, Debug)]
pub struct NonSplitWitness {
dual: Vec<Fp>,
}
impl NonSplitWitness {
accessor_methods! {
/// The dual vector, one entry per equation of the retraction system.
pub dual() -> &[Fp] = |this| &this.dual;
}
}
#[cfg(test)]
mod tests;