auslander 0.7.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
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
//! 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.

use crate::decompose::add_morphisms;
use crate::ext::{ExtClass, ExtSpace, lift_through};
use crate::field::{Fp, PrimeField};
use crate::hom::{
    Morphism, cokernel, express_in_row_basis, identity, image, matrix_is_zero, zero_morphism,
};
use crate::homspace::scale_morphism;
use crate::linalg::DenseMat;
use crate::module::{Module, direct_sum};
use crate::quiver::ArrowId;

/// 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";
} }

/// The morphism with every entry negated.
fn negate(f: &Morphism) -> Morphism {
    let field = f.source().field();
    scale_morphism(f, field.neg(field.one()))
}

/// The factorization `f: B -> C` with `epi.then(f) = map`, for `epi: A -> B`
/// and `map: A -> C` where `map` kills the kernel of `epi`. Every column
/// solves with free variables zeroed, so the result is deterministic; it is
/// unique when the vertex matrices of `epi` have full column rank.
///
/// One [`DenseMat::solve_many`] per vertex, not one `solve` per column: a
/// per-column solve repeats the elimination of the same `epi` matrix.
///
/// # Panics
/// Panics when a column of `map` lies outside the column space of the
/// matching `epi` matrix; callers only factor maps that kill the kernel.
fn factor_through_epi(epi: &Morphism, map: &Morphism) -> Morphism {
    debug_assert!(epi.source().ptr_eq(map.source()));
    let field = epi.source().field();
    let nv = epi.source().algebra().quiver().num_vertices();
    let maps = (0..nv)
        .map(|v| {
            let (e, m) = (epi.map_at(v), map.map_at(v));
            // With no right-hand side there is nothing to eliminate for.
            if m.cols() == 0 {
                return DenseMat::zero(e.cols(), 0);
            }
            e.solve_many(m, &field)
                .expect("factor_through_epi: the map kills the kernel of the epimorphism")
        })
        .collect();
    Morphism::new(epi.target(), map.target(), maps)
        .expect("a factorization through an epimorphism is A-linear")
}

/// The factorization `f: A -> N` with `f.then(mono) = map`, for
/// `mono: N -> B` and `map: A -> B` where `map` lands in the image of `mono`.
/// The vertex matrices of `mono` have full row rank, so `f` is unique.
///
/// One [`DenseMat::solve_many`] per vertex, not one `solve` per row: a
/// per-row solve repeats the elimination of the same `mono` matrix.
///
/// # Panics
/// Panics when a row of `map` lies outside the row space of the matching
/// `mono` matrix; callers only factor maps that land in the image.
fn factor_through_mono(mono: &Morphism, map: &Morphism) -> Morphism {
    debug_assert!(mono.target().ptr_eq(map.target()));
    let field = mono.source().field();
    let nv = mono.source().algebra().quiver().num_vertices();
    let maps = (0..nv)
        .map(|v| {
            let mo = mono.map_at(v).transpose();
            let m = map.map_at(v);
            if m.rows() == 0 {
                return DenseMat::zero(0, mo.cols());
            }
            mo.solve_many(&m.transpose(), &field)
                .expect("factor_through_mono: the map lands in the image of the mono")
                .transpose()
        })
        .collect();
    Morphism::new(map.source(), mono.source(), maps)
        .expect("a factorization through a monomorphism is A-linear")
}

/// 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 extension realizing a class in `Ext^1(M, N)`, built as a pushout.
    ///
    /// Take `K = im d_1` with its inclusion `kappa: K -> P_0` and the
    /// surjection `s: P_1 -> K`, then factor the representative cocycle as
    /// `c = s.then(c_bar)`. The middle term is the cokernel of
    /// `(c_bar, -kappa): K -> N (+) P_0`. The zero class gives the split
    /// sequence. The result passes through [`ShortExactSequence::new`], so it
    /// is exact by construction.
    ///
    /// # Errors
    /// [`SequenceError::WrongDegree`] when the class degree is not 1.
    pub fn from_ext1(class: &ExtClass) -> Result<ShortExactSequence, SequenceError> {
        let space = class.space();
        if space.degree() != 1 {
            return Err(SequenceError::WrongDegree {
                expected: 1,
                got: space.degree(),
            });
        }
        let m = space.source();
        let n = space.target();
        let res = space.resolution();
        let field = m.field();
        let nv = m.algebra().quiver().num_vertices();
        let p0 = &res.terms[0];
        let c = class.representative();
        let (kappa, c_bar) = match res.maps.first() {
            Some(d1) => {
                let (k_mod, kappa) = image(d1);
                let s_maps = (0..nv)
                    .map(|v| express_in_row_basis(kappa.map_at(v), d1.map_at(v), &field))
                    .collect();
                let s = Morphism::new(d1.source(), &k_mod, s_maps)
                    .expect("the corestriction of d_1 to its image is A-linear");
                let c_bar = factor_through_epi(&s, &c);
                (kappa, c_bar)
            }
            None => {
                // A projective quotient has no d_1, so K is the zero module.
                let k_mod = Module::zero(m.algebra());
                let kappa =
                    zero_morphism(&k_mod, p0).expect("the zero module is built over m's algebra");
                let c_bar =
                    zero_morphism(&k_mod, n).expect("the zero module is built over m's algebra");
                (kappa, c_bar)
            }
        };
        let (_sum, inclusions, projections) = direct_sum(&[n, p0]);
        let mu = add_morphisms(
            &c_bar
                .then(&inclusions[0])
                .expect("the sum inclusion starts at N"),
            &negate(&kappa)
                .then(&inclusions[1])
                .expect("the sum inclusion starts at P_0"),
        );
        let (_e, q) = cokernel(&mu);
        let iota = inclusions[0]
            .then(&q)
            .expect("the cokernel projection starts at the sum");
        let w = projections[1]
            .then(&res.augmentation)
            .expect("the augmentation starts at P_0");
        let pi = factor_through_epi(&q, &w);
        ShortExactSequence::new(iota, pi)
    }

    /// The class of this extension in `space = Ext^1(quotient, sub)`.
    ///
    /// The recovery lifts the augmentation through the projection, pulls
    /// `d_1.then(lift)` back through the inclusion, and reduces the resulting
    /// cocycle.
    ///
    /// # Errors
    /// [`SequenceError::WrongDegree`] when the space's degree is not 1, and
    /// [`SequenceError::SpaceSourceMismatch`] or
    /// [`SequenceError::SpaceTargetMismatch`] when the space's endpoints are
    /// not this sequence's quotient and sub (by [`Module::ptr_eq`]).
    pub fn ext1_class(&self, space: &ExtSpace) -> Result<ExtClass, SequenceError> {
        if space.degree() != 1 {
            return Err(SequenceError::WrongDegree {
                expected: 1,
                got: space.degree(),
            });
        }
        if !space.source().ptr_eq(&self.quotient) {
            return Err(SequenceError::SpaceSourceMismatch);
        }
        if !space.target().ptr_eq(&self.sub) {
            return Err(SequenceError::SpaceTargetMismatch);
        }
        let res = space.resolution();
        let Some(d1) = res.maps.first() else {
            return Ok(space
                .class_from_coordinates(&[])
                .expect("a projective quotient has the zero Ext^1 space"));
        };
        let h = lift_through(&res.terms[0], &self.projection, &res.augmentation);
        let d1h = d1.then(&h).expect("d_1 targets P_0");
        let c = factor_through_mono(&self.inclusion, &d1h);
        Ok(space
            .class_from_cocycle(&c)
            .expect("the recovered cochain is a cocycle; failure is a bug in auslander"))
    }

    /// Solves the retraction system in the fixed order stated in the module
    /// docs. Both outcomes carry their proof: a retraction and a section that
    /// recheck by multiplication, or a dual vector proving the system
    /// inconsistent.
    ///
    /// A split sequence costs one reduction of `[A | b]`, a non-split one a
    /// second of `[A | b | I]`. The crate-private `split_status_one_pass`
    /// trades that around for callers that expect the non-split answer.
    pub fn split_status(&self) -> SplitStatus {
        let field = self.middle.field();
        let (a, b) = retraction_system(self);
        match a.solve(&b, &field) {
            Some(x) => SplitStatus::Split(self.split_witness(&x)),
            None => {
                let (reduced, pivots) = augmented_with_dual(&a, &b, &field);
                let cols = a.cols();
                let pivot_row = pivots
                    .iter()
                    .position(|&c| c == cols)
                    .expect("an unsolvable system pivots in the right-side column");
                SplitStatus::NonSplit(non_split_witness(&reduced, pivot_row, cols, a.rows()))
            }
        }
    }

    /// [`ShortExactSequence::split_status`] from one reduction of
    /// `[A | b | I]`, which carries the dual vector along.
    ///
    /// The two routes return the same value. This one saves the second
    /// elimination on a non-split sequence and pays for the identity block on
    /// a split one, so the almost-split construction takes it and the general
    /// entry point does not.
    ///
    /// Same value, because the identity block only adds pivots to the right of
    /// column `cols`, and eliminating those touches rows already zero in the
    /// first `cols + 1` columns. Pivots, entries, and the
    /// free-variables-zeroed solution in those columns are therefore the ones
    /// [`DenseMat::solve`] reads off `[A | b]`.
    pub(crate) fn split_status_one_pass(&self) -> SplitStatus {
        let field = self.middle.field();
        let (a, b) = retraction_system(self);
        let (rows, cols) = (a.rows(), a.cols());
        let (reduced, pivots) = augmented_with_dual(&a, &b, &field);
        if let Some(pivot_row) = pivots.iter().position(|&c| c == cols) {
            return SplitStatus::NonSplit(non_split_witness(&reduced, pivot_row, cols, rows));
        }
        let mut x = vec![Fp::ZERO; cols];
        for (i, &pc) in pivots.iter().enumerate().filter(|&(_, &c)| c < cols) {
            x[pc] = reduced.get(i, cols);
        }
        SplitStatus::Split(self.split_witness(&x))
    }

    /// The retraction of a solution vector and the section it induces.
    fn split_witness(&self, x: &[Fp]) -> SplitWitness {
        let retraction = self.retraction_from_solution(x);
        let e_idem = retraction
            .then(&self.inclusion)
            .expect("the retraction ends at the sub");
        // For p = id - r.then(iota) the composite iota.then(p) is zero, so p
        // kills ker pi and factors through pi. The factor s obeys
        // pi.then(s.then(pi)) = p.then(pi) = pi, and pi is epi, so s.then(pi)
        // is the identity: s is a section.
        let p = add_morphisms(&identity(&self.middle), &negate(&e_idem));
        SplitWitness {
            section: factor_through_epi(&self.projection, &p),
            retraction,
        }
    }

    /// The retraction `E -> N` read off a solution vector of the retraction
    /// system, in the fixed unknown order.
    fn retraction_from_solution(&self, x: &[Fp]) -> Morphism {
        let nv = self.middle.algebra().quiver().num_vertices();
        let mut maps = Vec::with_capacity(nv as usize);
        let mut offset = 0;
        for v in 0..nv {
            let (de, dn) = (self.middle.dim_at(v), self.sub.dim_at(v));
            let block = DenseMat::from_flat(de, dn, &x[offset..offset + de * dn]);
            offset += de * dn;
            maps.push(block);
        }
        Morphism::new(&self.middle, &self.sub, maps)
            .expect("the solved system contains every commuting square")
    }
}

fn non_split_witness(
    reduced: &DenseMat,
    pivot_row: usize,
    cols: usize,
    rows: usize,
) -> NonSplitWitness {
    NonSplitWitness {
        dual: (0..rows)
            .map(|r| reduced.get(pivot_row, cols + 1 + r))
            .collect(),
    }
}

/// The reduced row echelon form of `[A | b | I]` and its pivot columns. A
/// pivot in column `A.cols()` proves the system inconsistent, and that row's
/// identity tail is the dual vector `y` with `y A = 0` and `y b = 1`.
fn augmented_with_dual(a: &DenseMat, b: &[Fp], field: &PrimeField) -> (DenseMat, Vec<usize>) {
    let (rows, cols) = (a.rows(), a.cols());
    let mut aug = DenseMat::zero(rows, cols + 1 + rows);
    for (r, &rhs) in b.iter().enumerate() {
        for c in 0..cols {
            aug.set(r, c, a.get(r, c));
        }
        aug.set(r, cols, rhs);
        aug.set(r, cols + 1 + r, field.one());
    }
    aug.into_rref(field)
}

/// The retraction system for `r: E -> N` in the fixed crate order: unknowns
/// vertex-major then row-major; equations are the commuting squares in
/// (arrow, row, column) lexicographic order, then `iota.then(r) = id`
/// vertex-major then row-major.
fn retraction_system(sequence: &ShortExactSequence) -> (DenseMat, Vec<Fp>) {
    let e = &sequence.middle;
    let n = &sequence.sub;
    let field: PrimeField = e.field();
    let quiver = e.algebra().quiver();
    let nv = quiver.num_vertices();
    let mut offsets = vec![0usize; nv as usize];
    let mut total = 0usize;
    for v in 0..nv {
        offsets[v as usize] = total;
        total += e.dim_at(v) * n.dim_at(v);
    }
    let mut rows: Vec<Vec<Fp>> = Vec::new();
    let mut rhs: Vec<Fp> = Vec::new();
    for idx in 0..quiver.num_arrows() {
        let a = ArrowId(idx as u32);
        let (s, t) = (quiver.source(a), quiver.target(a));
        let ea = e.map(a);
        let na = n.map(a);
        for i in 0..e.dim_at(s) {
            for j in 0..n.dim_at(t) {
                let mut row = vec![Fp::ZERO; total];
                for c in 0..n.dim_at(s) {
                    let col = offsets[s as usize] + i * n.dim_at(s) + c;
                    row[col] = field.add(row[col], na.get(c, j));
                }
                for k in 0..e.dim_at(t) {
                    let col = offsets[t as usize] + k * n.dim_at(t) + j;
                    row[col] = field.sub(row[col], ea.get(i, k));
                }
                rows.push(row);
                rhs.push(Fp::ZERO);
            }
        }
    }
    let iota = &sequence.inclusion;
    for v in 0..nv {
        let iv = iota.map_at(v);
        let dn = n.dim_at(v);
        for i in 0..dn {
            for j in 0..dn {
                let mut row = vec![Fp::ZERO; total];
                for k in 0..e.dim_at(v) {
                    let col = offsets[v as usize] + k * dn + j;
                    row[col] = field.add(row[col], iv.get(i, k));
                }
                rows.push(row);
                rhs.push(if i == j { field.one() } else { field.zero() });
            }
        }
    }
    let a = DenseMat::from_rows_with_cols(&rows, total);
    (a, rhs)
}

/// 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;
    }

    /// Rechecks both identities against the sequence: `iota.then(r) = id` on
    /// the sub and `s.then(projection) = id` on the quotient.
    pub fn verify(&self, sequence: &ShortExactSequence) -> bool {
        let_or_false!(Ok(left) = sequence.inclusion.then(&self.retraction));
        let_or_false!(Ok(right) = self.section.then(&sequence.projection));
        left == identity(&sequence.sub) && right == identity(&sequence.quotient)
    }
}

/// 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;
    }

    /// Rebuilds the retraction system in the fixed order and checks
    /// `y A = 0` and `y b = 1` by multiplication.
    pub fn verify(&self, sequence: &ShortExactSequence) -> bool {
        let (a, b) = retraction_system(sequence);
        verify_guard!(self.dual.len() == a.rows());
        let field = sequence.middle.field();
        let y = DenseMat::from_flat(1, self.dual.len(), &self.dual);
        let left = y.mul(&a, &field);
        let right = y
            .mul(&DenseMat::from_flat(b.len(), 1, &b), &field)
            .get(0, 0);
        left.row(0).iter().all(|value| value.is_zero()) && right == field.one()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::algebra::{an_with_relations, linear_an, truncated_poly};
    use crate::field::PrimeField;

    fn f5() -> PrimeField {
        PrimeField::new(5).unwrap()
    }

    fn f2() -> PrimeField {
        PrimeField::new(2).unwrap()
    }

    fn one_class(space: &ExtSpace) -> ExtClass {
        let field = space.source().field();
        let mut coords = vec![field.zero(); space.dim()];
        coords[0] = field.one();
        space.class_from_coordinates(&coords).unwrap()
    }

    #[test]
    fn new_accepts_a_direct_sum_and_split_status_verifies() {
        let algebra = linear_an(3, f5());
        let s = Module::simple(&algebra, 0);
        let p = Module::projective(&algebra, 1);
        let (sum, inclusions, projections) = direct_sum(&[&s, &p]);
        let ses = ShortExactSequence::new(inclusions[0].clone(), projections[1].clone()).unwrap();
        assert!(ses.sub().ptr_eq(&s));
        assert!(ses.middle().ptr_eq(&sum));
        assert!(ses.quotient().ptr_eq(&p));
        match ses.split_status() {
            SplitStatus::Split(witness) => {
                assert!(witness.verify(&ses));
                assert!(witness.retraction().source().ptr_eq(&sum));
                assert!(witness.retraction().target().ptr_eq(&s));
                assert!(witness.section().source().ptr_eq(&p));
                assert!(witness.section().target().ptr_eq(&sum));
            }
            SplitStatus::NonSplit(_) => panic!("a direct sum sequence splits"),
        }
    }

    #[test]
    fn new_rejects_each_defect_with_a_typed_error() {
        let algebra = linear_an(3, f5());
        let s = Module::simple(&algebra, 0);
        let p = Module::projective(&algebra, 1);
        let (sum, inclusions, projections) = direct_sum(&[&s, &p]);
        let (_, _, other_projections) = direct_sum(&[&s, &p]);
        assert_eq!(
            ShortExactSequence::new(inclusions[0].clone(), other_projections[1].clone())
                .unwrap_err(),
            SequenceError::EndpointMismatch
        );
        let zero_inclusion = zero_morphism(&s, &sum).unwrap();
        assert_eq!(
            ShortExactSequence::new(zero_inclusion, projections[1].clone()).unwrap_err(),
            SequenceError::NotMono { vertex: 0 }
        );
        let zero_projection = zero_morphism(&sum, &p).unwrap();
        assert_eq!(
            ShortExactSequence::new(inclusions[0].clone(), zero_projection).unwrap_err(),
            SequenceError::NotEpi { vertex: 1 }
        );
        assert_eq!(
            ShortExactSequence::new(inclusions[0].clone(), projections[0].clone()).unwrap_err(),
            SequenceError::CompositeNonzero { vertex: 0 }
        );
        let (_, triple_inclusions, triple_projections) = direct_sum(&[&s, &p, &s]);
        assert_eq!(
            ShortExactSequence::new(triple_inclusions[0].clone(), triple_projections[1].clone())
                .unwrap_err(),
            SequenceError::DimensionMismatch { vertex: 0 }
        );
    }

    #[test]
    fn from_ext1_of_a_nonzero_class_is_non_split_and_round_trips() {
        for field in [f5(), f2()] {
            let algebra = truncated_poly(3, field).unwrap();
            let s = Module::simple(&algebra, 0);
            let space = ExtSpace::new(&s, &s, 1).unwrap();
            assert_eq!(space.dim(), 1);
            let xi = one_class(&space);
            let ses = ShortExactSequence::from_ext1(&xi).unwrap();
            assert_eq!(ses.sub().dim_vector(), &[1]);
            assert_eq!(ses.middle().dim_vector(), &[2]);
            assert_eq!(ses.quotient().dim_vector(), &[1]);
            let recovered = ses.ext1_class(&space).unwrap();
            assert!(
                recovered.equals(&xi).unwrap(),
                "round trip over F_{}",
                field.modulus()
            );
            match ses.split_status() {
                SplitStatus::NonSplit(witness) => {
                    assert!(witness.verify(&ses));
                    let mut bad = witness.dual().to_vec();
                    bad[0] = field.add(bad[0], field.one());
                    assert!(!NonSplitWitness { dual: bad }.verify(&ses));
                    let zeros = vec![field.zero(); witness.dual().len()];
                    assert!(!NonSplitWitness { dual: zeros }.verify(&ses));
                    assert!(!NonSplitWitness { dual: Vec::new() }.verify(&ses));
                }
                SplitStatus::Split(_) => panic!("a nonzero Ext^1 class gives a non-split sequence"),
            }
        }
    }

    #[test]
    fn from_ext1_of_the_zero_class_splits_with_a_verifying_witness() {
        let algebra = truncated_poly(3, f5()).unwrap();
        let s = Module::simple(&algebra, 0);
        let space = ExtSpace::new(&s, &s, 1).unwrap();
        let ses = ShortExactSequence::from_ext1(&space.zero_class()).unwrap();
        assert_eq!(ses.middle().dim_vector(), &[2]);
        match ses.split_status() {
            SplitStatus::Split(witness) => assert!(witness.verify(&ses)),
            SplitStatus::NonSplit(_) => panic!("the zero class gives a split sequence"),
        }
        let recovered = ses.ext1_class(&space).unwrap();
        assert!(recovered.is_zero());
    }

    #[test]
    fn from_ext1_over_a_projective_quotient_uses_the_empty_presentation() {
        // S_2 is projective over linear A_3, so Ext^1(S_2, S_0) = 0 and the
        // resolution of S_2 has no differential.
        let algebra = linear_an(3, f5());
        let s0 = Module::simple(&algebra, 0);
        let s2 = Module::simple(&algebra, 2);
        let space = ExtSpace::new(&s2, &s0, 1).unwrap();
        assert_eq!(space.dim(), 0);
        let ses = ShortExactSequence::from_ext1(&space.zero_class()).unwrap();
        assert_eq!(ses.sub().dim_vector(), &[1, 0, 0]);
        assert_eq!(ses.quotient().dim_vector(), &[0, 0, 1]);
        match ses.split_status() {
            SplitStatus::Split(witness) => assert!(witness.verify(&ses)),
            SplitStatus::NonSplit(_) => panic!("the zero class gives a split sequence"),
        }
        assert!(ses.ext1_class(&space).unwrap().is_zero());
    }

    // Over kA_3/(ab) the extension of S_0 by S_1 with class the Ext^1
    // generator is P_0 (dimension vector (1, 1, 0)), and the extension of
    // S_1 by S_2 is P_1 (dimension vector (0, 1, 1)); both are non-split.
    // Splicing them realizes the Yoneda product, which is the Ext^2
    // generator detected by the relation: the product of the recovered
    // classes is nonzero in the one-dimensional Ext^2(S_0, S_2).
    #[test]
    fn round_trip_and_splicing_agreement_over_a3_mod_ab() {
        let field = f5();
        let algebra = an_with_relations(3, &[(0, 2)], field).unwrap();
        let s0 = Module::simple(&algebra, 0);
        let s1 = Module::simple(&algebra, 1);
        let s2 = Module::simple(&algebra, 2);
        let space_a = ExtSpace::new(&s0, &s1, 1).unwrap();
        let space_b = ExtSpace::new(&s1, &s2, 1).unwrap();
        let alpha = one_class(&space_a);
        let beta = one_class(&space_b);
        let ses_a = ShortExactSequence::from_ext1(&alpha).unwrap();
        let ses_b = ShortExactSequence::from_ext1(&beta).unwrap();
        assert_eq!(ses_a.middle().dim_vector(), &[1, 1, 0]);
        assert_eq!(ses_b.middle().dim_vector(), &[0, 1, 1]);
        let recovered_a = ses_a.ext1_class(&space_a).unwrap();
        let recovered_b = ses_b.ext1_class(&space_b).unwrap();
        assert!(recovered_a.equals(&alpha).unwrap());
        assert!(recovered_b.equals(&beta).unwrap());
        for ses in [&ses_a, &ses_b] {
            match ses.split_status() {
                SplitStatus::NonSplit(witness) => assert!(witness.verify(ses)),
                SplitStatus::Split(_) => panic!("the generator classes are non-split"),
            }
        }
        let spliced = recovered_a.then(&recovered_b).unwrap();
        let direct = alpha.then(&beta).unwrap();
        assert_eq!(spliced.space().dim(), 1);
        assert!(
            !spliced.is_zero(),
            "the spliced 2-extension class is nonzero"
        );
        assert!(spliced.equals(&direct).unwrap());
    }

    #[test]
    fn split_witness_rejects_a_tampered_retraction_or_section() {
        let algebra = linear_an(3, f5());
        let field = f5();
        let s = Module::simple(&algebra, 0);
        let p = Module::projective(&algebra, 1);
        let (_, inclusions, projections) = direct_sum(&[&s, &p]);
        let ses = ShortExactSequence::new(inclusions[0].clone(), projections[1].clone()).unwrap();
        let SplitStatus::Split(witness) = ses.split_status() else {
            panic!("a direct sum sequence splits");
        };
        let scale = |f: &Morphism| scale_morphism(f, field.elem(2));
        let bad_retraction = SplitWitness {
            retraction: scale(witness.retraction()),
            section: witness.section().clone(),
        };
        assert!(!bad_retraction.verify(&ses));
        let bad_section = SplitWitness {
            retraction: witness.retraction().clone(),
            section: scale(witness.section()),
        };
        assert!(!bad_section.verify(&ses));
    }

    // Section 15 of the design: a dual vector with y A != 0, and a dual
    // vector with y b = 0. Adding a unit vector at a nonzero row of A
    // moves y A off zero; the zero vector and the doubled vector keep
    // y A = 0 and fail y b = 1.
    #[test]
    fn a_tampered_or_zero_dual_vector_fails_verification() {
        let field = f5();
        let algebra = truncated_poly(3, field).unwrap();
        let s = Module::simple(&algebra, 0);
        let space = ExtSpace::new(&s, &s, 1).unwrap();
        let ses = ShortExactSequence::from_ext1(&one_class(&space)).unwrap();
        let SplitStatus::NonSplit(witness) = ses.split_status() else {
            panic!("the generator class does not split");
        };
        assert!(witness.verify(&ses));
        let (a, _) = retraction_system(&ses);
        let r = (0..a.rows())
            .find(|&r| a.row(r).iter().any(|v| !v.is_zero()))
            .expect("the retraction system has a nonzero row");
        let mut dual = witness.dual().to_vec();
        dual[r] = field.add(dual[r], field.one());
        let off_kernel = NonSplitWitness { dual };
        assert!(!off_kernel.verify(&ses), "y A is nonzero");
        let zero = NonSplitWitness {
            dual: vec![field.zero(); witness.dual().len()],
        };
        assert!(!zero.verify(&ses), "y b is zero");
        let doubled = NonSplitWitness {
            dual: witness
                .dual()
                .iter()
                .map(|&y| field.mul(field.elem(2), y))
                .collect(),
        };
        assert!(!doubled.verify(&ses), "y b is two");
    }

    #[test]
    fn ext1_class_rejects_a_space_with_wrong_degree_or_endpoints() {
        let field = f5();
        let algebra = truncated_poly(3, field).unwrap();
        let s = Module::simple(&algebra, 0);
        let space = ExtSpace::new(&s, &s, 1).unwrap();
        let ses = ShortExactSequence::from_ext1(&one_class(&space)).unwrap();
        let deg2 = ExtSpace::new(&s, &s, 2).unwrap();
        assert_eq!(
            ses.ext1_class(&deg2).unwrap_err(),
            SequenceError::WrongDegree {
                expected: 1,
                got: 2
            }
        );
        let s_copy = Module::simple(&algebra, 0);
        let wrong_source = ExtSpace::new(&s_copy, &s, 1).unwrap();
        assert_eq!(
            ses.ext1_class(&wrong_source).unwrap_err(),
            SequenceError::SpaceSourceMismatch
        );
        let wrong_target = ExtSpace::new(&s, &s_copy, 1).unwrap();
        assert_eq!(
            ses.ext1_class(&wrong_target).unwrap_err(),
            SequenceError::SpaceTargetMismatch
        );
    }

    #[test]
    fn from_ext1_rejects_a_class_of_the_wrong_degree() {
        let field = f5();
        let algebra = truncated_poly(3, field).unwrap();
        let s = Module::simple(&algebra, 0);
        let deg0 = ExtSpace::new(&s, &s, 0).unwrap().identity_class().unwrap();
        assert_eq!(
            ShortExactSequence::from_ext1(&deg0).unwrap_err(),
            SequenceError::WrongDegree {
                expected: 1,
                got: 0
            }
        );
        let deg2 = one_class(&ExtSpace::new(&s, &s, 2).unwrap());
        assert_eq!(
            ShortExactSequence::from_ext1(&deg2).unwrap_err(),
            SequenceError::WrongDegree {
                expected: 1,
                got: 2
            }
        );
    }

    #[test]
    fn a_zero_sub_gives_an_isomorphism_like_split_sequence() {
        let algebra = linear_an(3, f5());
        let p = Module::projective(&algebra, 0);
        let z = Module::zero(&algebra);
        let inclusion = zero_morphism(&z, &p).unwrap();
        let ses = ShortExactSequence::new(inclusion, identity(&p)).unwrap();
        match ses.split_status() {
            SplitStatus::Split(witness) => assert!(witness.verify(&ses)),
            SplitStatus::NonSplit(_) => panic!("a zero-sub sequence splits"),
        }
    }

    #[test]
    fn from_ext1_and_split_status_are_deterministic_across_recomputation() {
        let field = f5();
        let algebra = truncated_poly(3, field).unwrap();
        let s = Module::simple(&algebra, 0);
        let space = ExtSpace::new(&s, &s, 1).unwrap();
        let xi = one_class(&space);
        let first = ShortExactSequence::from_ext1(&xi).unwrap();
        let second = ShortExactSequence::from_ext1(&xi).unwrap();
        for v in 0..algebra.quiver().num_vertices() {
            assert_eq!(
                first.inclusion().map_at(v).entries_u64(),
                second.inclusion().map_at(v).entries_u64()
            );
            assert_eq!(
                first.projection().map_at(v).entries_u64(),
                second.projection().map_at(v).entries_u64()
            );
        }
        let (SplitStatus::NonSplit(a), SplitStatus::NonSplit(b)) =
            (first.split_status(), second.split_status())
        else {
            panic!("the generator class is non-split");
        };
        assert_eq!(
            a.dual().iter().map(|c| c.raw()).collect::<Vec<_>>(),
            b.dual().iter().map(|c| c.raw()).collect::<Vec<_>>()
        );
    }

    // The one-pass route saves an elimination on a non-split sequence and must
    // return exactly what the two-pass route returns, on both outcomes.
    #[test]
    fn the_one_pass_split_status_agrees_with_the_two_pass_one() {
        let field = f5();
        let algebra = truncated_poly(3, field).unwrap();
        let s = Module::simple(&algebra, 0);
        let p = Module::projective(&algebra, 0);
        let (_, inclusions, projections) = direct_sum(&[&s, &p]);
        let split = ShortExactSequence::new(inclusions[0].clone(), projections[1].clone()).unwrap();
        let space = ExtSpace::new(&s, &s, 1).unwrap();
        let nonsplit = ShortExactSequence::from_ext1(&one_class(&space)).unwrap();
        for sequence in [&split, &nonsplit] {
            match (sequence.split_status(), sequence.split_status_one_pass()) {
                (SplitStatus::Split(a), SplitStatus::Split(b)) => {
                    assert_eq!(a.retraction(), b.retraction());
                    assert_eq!(a.section(), b.section());
                    assert!(b.verify(sequence));
                }
                (SplitStatus::NonSplit(a), SplitStatus::NonSplit(b)) => {
                    assert_eq!(a.dual(), b.dual());
                    assert!(b.verify(sequence));
                }
                _ => panic!("the two routes disagree on the outcome"),
            }
        }
    }
}