Skip to main content

logicaffeine_proof/
steenrod.rs

1//! The **Steenrod algebra** acting on `H*(BZ/2; Z/2) = Z/2[x]` — the deepest layer of cohomology
2//! operations, and a place where homotopy theory turns out to *be* number theory.
3//!
4//! The total Steenrod square `Sq = Σᵢ Sqⁱ` is the ring endomorphism of `Z/2[x]` determined by
5//! `Sq(x) = x + x²` (`Sq⁰x = x`, `Sq¹x = x²` since `|x| = 1`, `Sqⁱx = 0` for `i > 1`) extended
6//! multiplicatively by the **Cartan formula** `Sq(ab) = Sq(a)Sq(b)`. Computing it is then pure
7//! polynomial arithmetic over `Z/2`, and the answer is striking:
8//!
9//! ```text
10//!   Sqⁱ(xᵏ) = coefficient of x^{k+i} in (x + x²)ᵏ = C(k, i) mod 2
11//! ```
12//!
13//! — the binomial coefficients mod 2, i.e. **Lucas' theorem** (`C(k,i) ≡ 1 ⟺ i AND k = i` bit-wise).
14//! The top square `Sqᵏ(xᵏ) = x^{2k}` agrees with the cup-square ([`crate::postnikov::cup_square`]); the
15//! whole infinite family of operations is governed by one binomial law.
16
17/// A polynomial over `Z/2`: `p[d]` is the coefficient of `xᵈ` (each `0` or `1`).
18fn add(a: &[u8], b: &[u8]) -> Vec<u8> {
19    let n = a.len().max(b.len());
20    (0..n)
21        .map(|i| (a.get(i).copied().unwrap_or(0) + b.get(i).copied().unwrap_or(0)) % 2)
22        .collect()
23}
24
25fn mul(a: &[u8], b: &[u8]) -> Vec<u8> {
26    if a.is_empty() || b.is_empty() {
27        return vec![];
28    }
29    let mut out = vec![0u8; a.len() + b.len() - 1];
30    for (i, &ai) in a.iter().enumerate() {
31        if ai == 1 {
32            for (j, &bj) in b.iter().enumerate() {
33                out[i + j] = (out[i + j] + bj) % 2;
34            }
35        }
36    }
37    out
38}
39
40/// The monomial `xᵏ`.
41pub fn monomial(k: usize) -> Vec<u8> {
42    let mut p = vec![0u8; k + 1];
43    p[k] = 1;
44    p
45}
46
47fn trim(mut p: Vec<u8>) -> Vec<u8> {
48    while p.len() > 1 && *p.last().unwrap() == 0 {
49        p.pop();
50    }
51    p
52}
53
54/// The **total Steenrod square** `Sq`, as the ring endomorphism of `Z/2[x]` sending `x ↦ x + x²`
55/// (Cartan formula). Returns `Sq(p)` as a polynomial.
56pub fn total_square(poly: &[u8]) -> Vec<u8> {
57    let x_plus_x2 = [0u8, 1, 1]; // x + x²
58    let mut result = vec![0u8];
59    let mut power = vec![1u8]; // (x + x²)^0
60    for &c in poly {
61        if c == 1 {
62            result = add(&result, &power);
63        }
64        power = mul(&power, &x_plus_x2);
65    }
66    trim(result)
67}
68
69/// `Sqⁱ(xᵏ)` on `H*(BZ/2; Z/2)` — the coefficient of `x^{k+i}` in `Sq(xᵏ) = (x + x²)ᵏ`.
70pub fn sq(i: usize, k: usize) -> u8 {
71    let s = total_square(&monomial(k));
72    s.get(k + i).copied().unwrap_or(0)
73}
74
75/// `C(k, i)` (binomial coefficient), computed by Pascal's recurrence — independent of the topology, so
76/// matching it against [`sq`] is a genuine theorem, not a definition.
77fn binom(k: usize, i: usize) -> u64 {
78    if i > k {
79        return 0;
80    }
81    let mut row = vec![1u64; 1];
82    for r in 1..=k {
83        let mut next = vec![1u64; r + 1];
84        for c in 1..r {
85            next[c] = row[c - 1] + row[c];
86        }
87        row = next;
88    }
89    row[i]
90}
91
92/// Apply a single `Sqⁱ` to a class in `H*(BZ/2; Z/2) = Z/2[x]`: `Sqⁱ(Σ aₖ xᵏ) = Σ aₖ C(k,i) x^{k+i}`.
93pub fn apply_sq(i: usize, poly: &[u8]) -> Vec<u8> {
94    let mut out = vec![0u8; poly.len() + i];
95    for (k, &a) in poly.iter().enumerate() {
96        if a == 1 && binom(k, i) % 2 == 1 {
97            out[k + i] ^= 1;
98        }
99    }
100    trim(out)
101}
102
103/// The Adem relation applied to `SqᵃSqᵇ` (`a < 2b`): `Σ_c C(b-c-1, a-2c) Sq^{a+b-c} Sq^c` over `Z/2`,
104/// returned as a list of monomials (`Sq⁰` = identity is dropped).
105fn adem(a: usize, b: usize) -> Vec<Vec<usize>> {
106    let mut terms = Vec::new();
107    for c in 0..=(a / 2) {
108        if binom(b - c - 1, a - 2 * c) % 2 == 1 {
109            let mut m = vec![a + b - c];
110            if c > 0 {
111                m.push(c);
112            }
113            terms.push(m);
114        }
115    }
116    terms
117}
118
119/// Is a monomial `Sq^{i₁}…Sq^{iₖ}` **admissible**? (`i_j ≥ 2 i_{j+1}` for all adjacent pairs.)
120pub fn is_admissible(m: &[usize]) -> bool {
121    m.iter().all(|&i| i >= 1) && m.windows(2).all(|w| w[0] >= 2 * w[1])
122}
123
124/// Reduce a Steenrod monomial to its `Z/2` sum of **admissible** monomials via the Adem relations — the
125/// canonical form in the Steenrod algebra. A `HashSet` models the `Z/2` linear combination (present =
126/// coefficient 1; re-insertion cancels).
127pub fn adem_reduce(m: &[usize]) -> std::collections::HashSet<Vec<usize>> {
128    let m: Vec<usize> = m.iter().copied().filter(|&i| i > 0).collect();
129    if is_admissible(&m) {
130        let mut s = std::collections::HashSet::new();
131        if !m.is_empty() {
132            s.insert(m);
133        }
134        return s;
135    }
136    let j = m.windows(2).position(|w| w[0] < 2 * w[1]).unwrap();
137    let (a, b) = (m[j], m[j + 1]);
138    let mut result: std::collections::HashSet<Vec<usize>> = std::collections::HashSet::new();
139    for term in adem(a, b) {
140        let mut spliced = m[..j].to_vec();
141        spliced.extend_from_slice(&term);
142        spliced.extend_from_slice(&m[j + 2..]);
143        for adm in adem_reduce(&spliced) {
144            if !result.insert(adm.clone()) {
145                result.remove(&adm); // XOR over Z/2
146            }
147        }
148    }
149    result
150}
151
152/// Over `Z/2`, is `target` in the linear span of `generators`? Each "vector" is a set of admissible
153/// monomials (its `Z/2` support); XOR is symmetric difference; the pivot is the largest monomial.
154fn z2_span_contains(
155    generators: Vec<std::collections::HashSet<Vec<usize>>>,
156    target: std::collections::HashSet<Vec<usize>>,
157) -> bool {
158    type Vec2 = std::collections::HashSet<Vec<usize>>;
159    fn reduce(mut v: Vec2, basis: &[(Vec<usize>, Vec2)]) -> Vec2 {
160        loop {
161            if v.is_empty() {
162                return v;
163            }
164            let piv = v.iter().max().unwrap().clone();
165            match basis.iter().find(|(p, _)| *p == piv) {
166                Some((_, bset)) => {
167                    for x in bset {
168                        if !v.insert(x.clone()) {
169                            v.remove(x);
170                        }
171                    }
172                }
173                None => return v,
174            }
175        }
176    }
177    let mut basis: Vec<(Vec<usize>, Vec2)> = Vec::new();
178    for g in generators {
179        let r = reduce(g, &basis);
180        if !r.is_empty() {
181            let piv = r.iter().max().unwrap().clone();
182            basis.push((piv, r));
183        }
184    }
185    reduce(target, &basis).is_empty()
186}
187
188/// The `Z/2` rank of a set of "vectors" (sets of admissible monomials) — Gaussian elimination, pivot =
189/// largest monomial.
190fn z2_rank(generators: Vec<std::collections::HashSet<Vec<usize>>>) -> usize {
191    type Vec2 = std::collections::HashSet<Vec<usize>>;
192    fn reduce(mut v: Vec2, basis: &[(Vec<usize>, Vec2)]) -> Vec2 {
193        loop {
194            if v.is_empty() {
195                return v;
196            }
197            let piv = v.iter().max().unwrap().clone();
198            match basis.iter().find(|(p, _)| *p == piv) {
199                Some((_, bset)) => {
200                    for x in bset {
201                        if !v.insert(x.clone()) {
202                            v.remove(x);
203                        }
204                    }
205                }
206                None => return v,
207            }
208        }
209    }
210    let mut basis: Vec<(Vec<usize>, Vec2)> = Vec::new();
211    for g in generators {
212        let r = reduce(g, &basis);
213        if !r.is_empty() {
214            let piv = r.iter().max().unwrap().clone();
215            basis.push((piv, r));
216        }
217    }
218    basis.len()
219}
220
221/// The **admissible monomials** of total degree `t` — a basis of the Steenrod algebra `𝒜_t`.
222pub fn admissibles_of_degree(t: usize) -> Vec<Vec<usize>> {
223    fn rec(remaining: usize, min_left: usize, suffix: &mut Vec<usize>, out: &mut Vec<Vec<usize>>) {
224        if remaining == 0 {
225            out.push(suffix.clone());
226            return;
227        }
228        for i in min_left.max(1)..=remaining {
229            suffix.insert(0, i);
230            rec(remaining - i, 2 * i, suffix, out);
231            suffix.remove(0);
232        }
233    }
234    let mut out = Vec::new();
235    rec(t, 1, &mut Vec::new(), &mut out);
236    out
237}
238
239/// `dim Ext^{1,t}_𝒜(Z/2, Z/2)` — the first line of the Adams `E₂` page = the **indecomposables** of the
240/// Steenrod algebra in degree `t`. Equals `dim 𝒜_t − dim(𝒜⁺·𝒜⁺)_t`. By Milnor it is `1` exactly when
241/// `t` is a power of 2 (the `h_i = Sq^{2ⁱ}`), and `0` otherwise.
242pub fn adams_one_line(t: usize) -> usize {
243    let dim_at = admissibles_of_degree(t).len();
244    let mut decomposables: Vec<std::collections::HashSet<Vec<usize>>> = Vec::new();
245    for d in 1..t {
246        for a in admissibles_of_degree(d) {
247            for b in admissibles_of_degree(t - d) {
248                let mut prod = a.clone();
249                prod.extend_from_slice(&b);
250                decomposables.push(adem_reduce(&prod));
251            }
252        }
253    }
254    dim_at - z2_rank(decomposables)
255}
256
257/// Is `Sqⁿ` **decomposable** — a `Z/2` combination of products `SqᵃSqᵇ` (`a, b ≥ 1`) — in the Steenrod
258/// algebra? Decided by reducing every such product to the admissible basis (Adem) and testing whether
259/// `Sqⁿ` lies in their span.
260pub fn is_decomposable_sq(n: usize) -> bool {
261    let generators: Vec<_> = (1..n).map(|a| adem_reduce(&[a, n - a])).collect();
262    let target: std::collections::HashSet<Vec<usize>> = [vec![n]].into_iter().collect();
263    z2_span_contains(generators, target)
264}
265
266/// An unbounded `Z/2` bit-vector (the resolution outgrows `u128` once the Steenrod algebra's degree-wise
267/// dimension exceeds 128). Word-packed; the pivot is always the lowest set bit.
268#[derive(Clone, PartialEq, Eq)]
269struct Bits(Vec<u64>);
270
271impl Bits {
272    fn new() -> Self {
273        Bits(Vec::new())
274    }
275    fn bit(i: usize) -> Self {
276        let mut b = Bits::new();
277        b.toggle(i);
278        b
279    }
280    fn from_indices(it: impl Iterator<Item = usize>) -> Self {
281        let mut b = Bits::new();
282        for i in it {
283            b.toggle(i);
284        }
285        b
286    }
287    fn toggle(&mut self, i: usize) {
288        let w = i / 64;
289        if w >= self.0.len() {
290            self.0.resize(w + 1, 0);
291        }
292        self.0[w] ^= 1u64 << (i % 64);
293    }
294    fn get(&self, i: usize) -> bool {
295        let w = i / 64;
296        w < self.0.len() && (self.0[w] >> (i % 64)) & 1 == 1
297    }
298    fn is_zero(&self) -> bool {
299        self.0.iter().all(|&w| w == 0)
300    }
301    /// The lowest set bit — the Gaussian-elimination pivot.
302    fn lowest(&self) -> Option<usize> {
303        self.0
304            .iter()
305            .enumerate()
306            .find(|(_, &w)| w != 0)
307            .map(|(wi, &w)| wi * 64 + w.trailing_zeros() as usize)
308    }
309}
310
311impl std::ops::BitXorAssign<&Bits> for Bits {
312    fn bitxor_assign(&mut self, o: &Bits) {
313        if o.0.len() > self.0.len() {
314            self.0.resize(o.0.len(), 0);
315        }
316        for (a, b) in self.0.iter_mut().zip(&o.0) {
317            *a ^= b;
318        }
319    }
320}
321
322/// Basis of the `Z/2` nullspace of the linear map whose `j`-th column is `cols[j]` (a bitmask over the
323/// codomain): each returned `Bits` is a mask over the *domain* indices summing the columns to zero.
324fn z2_nullspace(cols: &[Bits]) -> Vec<Bits> {
325    let mut pivots: std::collections::HashMap<usize, (Bits, Bits)> =
326        std::collections::HashMap::new();
327    let mut kernel = Vec::new();
328    for (j, col) in cols.iter().enumerate() {
329        let (mut cod, mut trk) = (col.clone(), Bits::bit(j));
330        while let Some(lead) = cod.lowest() {
331            match pivots.get(&lead) {
332                Some((pcod, ptrk)) => {
333                    cod ^= pcod;
334                    trk ^= ptrk;
335                }
336                None => break,
337            }
338        }
339        match cod.lowest() {
340            None => kernel.push(trk),
341            Some(lead) => {
342                pivots.insert(lead, (cod, trk));
343            }
344        }
345    }
346    kernel
347}
348
349/// `Z/2` rank of a set of `Bits` row vectors.
350fn z2_rank_u128(rows: Vec<Bits>) -> usize {
351    let mut pivots: std::collections::HashMap<usize, Bits> = std::collections::HashMap::new();
352    for mut v in rows {
353        while let Some(lead) = v.lowest() {
354            match pivots.get(&lead) {
355                Some(p) => v ^= p,
356                None => {
357                    pivots.insert(lead, v);
358                    break;
359                }
360            }
361        }
362    }
363    pivots.len()
364}
365
366/// Basis of the degree-`s` part of `C₁ = ⊕ᵢ 𝒜·hᵢ` in the minimal resolution: `(i, m)` with `2ⁱ ≤ s` and
367/// `m` an admissible of degree `s − 2ⁱ` (the element `m·hᵢ`).
368fn c1_basis(s: usize) -> Vec<(usize, Vec<usize>)> {
369    let mut out = Vec::new();
370    let mut i = 0;
371    while (1usize << i) <= s {
372        for m in admissibles_of_degree(s - (1 << i)) {
373            out.push((i, m));
374        }
375        i += 1;
376    }
377    out
378}
379
380/// `(basis, kernel)` of `d₁ : C₁ → 𝒜` in degree `s`, where `d₁(m·hᵢ) = m·Sq^{2ⁱ}`. Kernel vectors are
381/// masks over the returned `c1_basis(s)`.
382fn ker_d1(s: usize) -> (Vec<(usize, Vec<usize>)>, Vec<Bits>) {
383    let basis = c1_basis(s);
384    let cod_idx: std::collections::HashMap<Vec<usize>, usize> = admissibles_of_degree(s)
385        .into_iter()
386        .enumerate()
387        .map(|(i, m)| (m, i))
388        .collect();
389    let cols: Vec<Bits> = basis
390        .iter()
391        .map(|(i, m)| {
392            let mut prod = m.clone();
393            prod.push(1 << i); // m · Sq^{2^i}
394            let mut mask = Bits::new();
395            for adm in adem_reduce(&prod) {
396                if let Some(&idx) = cod_idx.get(&adm) {
397                    mask.toggle(idx);
398                }
399            }
400            mask
401        })
402        .collect();
403    let kernel = z2_nullspace(&cols);
404    (basis, kernel)
405}
406
407/// `dim Ext^{2,t}_𝒜(Z/2, Z/2)` — the second line of the Adams `E₂` page: the minimal generators of
408/// `ker(d₁)` in degree `t`, i.e. `dim ker(d₁)_t − dim(𝒜⁺·ker(d₁))_t`. The relations among the `Sq^{2ⁱ}`.
409pub fn adams_two_line(t: usize) -> usize {
410    let (_basis_t, ker_t) = ker_d1(t);
411    let c1_idx_t: std::collections::HashMap<(usize, Vec<usize>), usize> = c1_basis(t)
412        .into_iter()
413        .enumerate()
414        .map(|(i, b)| (b, i))
415        .collect();
416    let mut decomposables: Vec<Bits> = Vec::new();
417    for k in 1..t {
418        let (basis_s, ker_s) = ker_d1(t - k);
419        for zmask in &ker_s {
420            let mut result = Bits::new();
421            for (b, (i, m)) in basis_s.iter().enumerate() {
422                if zmask.get(b) {
423                    let mut prod = vec![k];
424                    prod.extend_from_slice(m);
425                    for mprime in adem_reduce(&prod) {
426                        if let Some(&idx) = c1_idx_t.get(&(*i, mprime)) {
427                            result.toggle(idx);
428                        }
429                    }
430                }
431            }
432            if !result.is_zero() {
433                decomposables.push(result);
434            }
435        }
436    }
437    ker_t.len() - z2_rank_u128(decomposables)
438}
439
440/// The known `dim Ext^{2,t}` from the chart: `#{(i,j) : i ≤ j, j ≠ i+1, 2ⁱ + 2ʲ = t}` (the `h_i h_j`
441/// with the adjacency relation `h_i h_{i+1} = 0`).
442fn known_ext2(t: usize) -> usize {
443    let mut count = 0;
444    let mut i = 0;
445    while (1usize << i) <= t {
446        let mut j = i;
447        while (1usize << i) + (1usize << j) <= t {
448            if (1 << i) + (1 << j) == t && j != i + 1 {
449                count += 1;
450            }
451            j += 1;
452        }
453        i += 1;
454    }
455    count
456}
457
458/// A generator of the minimal free resolution: its internal degree and its boundary `d(g) ∈ C_{s-1}`,
459/// a `Z/2` set of `(previous-generator-index, admissible monomial)` pairs (the element `Σ a·g'`).
460#[derive(Clone)]
461struct ResGen {
462    degree: usize,
463    boundary: Vec<(usize, Vec<usize>)>,
464}
465
466/// An **augmented graded `Z/2`-algebra**, given by its degree-wise basis and product. The minimal-resolution
467/// engine (and hence the whole `Ext`/Adams machine) is generic over this — the Steenrod algebra is just one
468/// instance. Point it at a different algebra and the same machine computes a different spectrum's Adams chart.
469trait Algebra {
470    /// The `Z/2`-basis of the algebra in internal degree `degree` (each element encoded as a monomial). For a
471    /// finite algebra this is empty above the top degree.
472    fn basis(&self, degree: usize) -> Vec<Vec<usize>>;
473    /// The product `a · b`, reduced to the basis, as a `Z/2` support set. The unit is the empty monomial.
474    fn multiply(&self, a: &[usize], b: &[usize]) -> std::collections::HashSet<Vec<usize>>;
475    /// The **algebra generators** (indecomposables) of positive degree up to `max_degree`, as `(degree, key)`.
476    /// Multiplying a kernel by just these spans `A⁺·ker` (the kernel is a submodule), so the resolution's
477    /// decomposables loop needs only the generators — the key speed symmetry: a handful instead of the whole
478    /// algebra per degree.
479    fn generators(&self, max_degree: usize) -> Vec<(usize, Vec<usize>)>;
480}
481
482/// The full mod-2 Steenrod algebra `𝒜`: basis = admissible monomials, product = concatenate then Adem-reduce.
483struct SteenrodAlgebra;
484impl Algebra for SteenrodAlgebra {
485    fn basis(&self, degree: usize) -> Vec<Vec<usize>> {
486        admissibles_of_degree(degree)
487    }
488    fn multiply(&self, a: &[usize], b: &[usize]) -> std::collections::HashSet<Vec<usize>> {
489        let mut prod = a.to_vec();
490        prod.extend_from_slice(b);
491        reduce_unit(&prod)
492    }
493    fn generators(&self, max_degree: usize) -> Vec<(usize, Vec<usize>)> {
494        let mut out = Vec::new();
495        let mut d = 1usize;
496        while d <= max_degree {
497            out.push((d, vec![d])); // Sq^{2ⁱ}, the indecomposables of 𝒜
498            d <<= 1;
499        }
500        out
501    }
502}
503
504/// A `Z/2`-element of the Steenrod algebra as the support set of admissible monomials it sums (e.g. the
505/// `A(1)` element `Sq²Sq³ = Sq⁵ + Sq⁴Sq¹` is `{[5], [4,1]}`).
506type Combo = std::collections::BTreeSet<Vec<usize>>;
507
508/// `Z/2` product of two combinations: `(Σ mᵢ)(Σ nⱼ) = Σ adem_reduce(mᵢ·nⱼ)`.
509fn combo_mul(a: &Combo, b: &Combo) -> Combo {
510    let mut out = Combo::new();
511    for ma in a {
512        for mb in b {
513            let mut prod = ma.clone();
514            prod.extend_from_slice(mb);
515            for r in reduce_unit(&prod) {
516                if !out.insert(r.clone()) {
517                    out.remove(&r);
518                }
519            }
520        }
521    }
522    out
523}
524
525/// A per-degree map from a basis element's **pivot monomial** (its largest monomial) to its index — turns the
526/// echelon reduction's inner lookup from an O(basis) scan into O(1).
527type PivotIndex = std::collections::HashMap<Vec<usize>, usize>;
528
529/// Express a combination in a degree's **echelon basis** (each basis element pivoted on its largest
530/// monomial): returns the indices whose `Z/2` sum is `target`. `target` must lie in the span (always true for
531/// products inside a subalgebra). Pivot lookups are O(1) via `pivots`.
532fn express_in_basis(target: &Combo, basis: &[Combo], pivots: &PivotIndex) -> Vec<usize> {
533    let mut r = target.clone();
534    let mut used = Vec::new();
535    while let Some(piv) = r.iter().next_back().cloned() {
536        match pivots.get(&piv) {
537            Some(&idx) => {
538                used.push(idx);
539                for m in &basis[idx] {
540                    if !r.insert(m.clone()) {
541                        r.remove(m);
542                    }
543                }
544            }
545            None => break, // not in span — only on a closure bug
546        }
547    }
548    used.sort_unstable();
549    used
550}
551
552/// A **finite subalgebra** of `𝒜`, given a `Z/2`-basis of *combinations* per degree (a subalgebra need not be
553/// spanned by single admissibles — e.g. `Sq²Sq³ = Sq⁵+Sq⁴Sq¹ ∈ A(1)`). Basis elements are addressed by the
554/// opaque key `[degree, index]`. `A(1) = ⟨Sq¹, Sq²⟩` is the headline instance — its `Ext` is the Adams `E₂`
555/// for `ko` (connective real K-theory).
556struct SubAlgebra {
557    by_degree: Vec<Vec<Combo>>,
558    pivots: Vec<PivotIndex>,
559    gen_keys: Vec<(usize, Vec<usize>)>,
560}
561
562impl SubAlgebra {
563    fn dimension(&self) -> usize {
564        self.by_degree.iter().map(|v| v.len()).sum()
565    }
566}
567
568/// Reduce a combination against a degree's echelon basis (pivot = largest monomial), using the O(1) pivot
569/// index; returns the residual.
570fn reduce_combo(basis: &[Combo], pivots: &PivotIndex, c: &Combo) -> Combo {
571    let mut r = c.clone();
572    while let Some(piv) = r.iter().next_back().cloned() {
573        match pivots.get(&piv) {
574            Some(&idx) => {
575                for m in &basis[idx] {
576                    if !r.insert(m.clone()) {
577                        r.remove(m);
578                    }
579                }
580            }
581            None => break,
582        }
583    }
584    r
585}
586
587/// Reduce `c` against its degree's basis; if it is a NEW independent direction, append the residual to the
588/// echelon basis, register its pivot, and queue it. The heart of the fast build: only the basis is ever stored.
589fn subalg_add(
590    by_degree: &mut [Vec<Combo>],
591    pivots: &mut [PivotIndex],
592    worklist: &mut Vec<Combo>,
593    max_degree: usize,
594    c: Combo,
595) {
596    let d = match c.iter().next() {
597        Some(m) => m.iter().sum::<usize>(),
598        None => return,
599    };
600    if d > max_degree {
601        return;
602    }
603    let r = reduce_combo(&by_degree[d], &pivots[d], &c);
604    if let Some(piv) = r.iter().next_back().cloned() {
605        pivots[d].insert(piv, by_degree[d].len());
606        by_degree[d].push(r.clone());
607        worklist.push(r);
608    }
609}
610
611/// Build the subalgebra generated by `gens` (each a single square), by closing under the Adem product up to
612/// `max_degree` and extracting an echelon basis of combinations per degree.
613fn build_subalgebra(gens: &[Vec<usize>], max_degree: usize) -> SubAlgebra {
614    let unit: Combo = std::iter::once(vec![]).collect();
615    let gen_combos: Vec<Combo> = gens
616        .iter()
617        .map(|g| std::iter::once(g.clone()).collect())
618        .collect();
619    let mut by_degree: Vec<Vec<Combo>> = vec![Vec::new(); max_degree + 1];
620    let mut pivots: Vec<PivotIndex> = vec![PivotIndex::new(); max_degree + 1];
621    let mut worklist: Vec<Combo> = Vec::new();
622    // Seed with the unit and the generators, then BFS: multiply each new basis element by the generators.
623    // Every A-element is a word in the generators, so right-multiplying the basis by them reaches all of A —
624    // O(dim · #gens) products with O(1) pivot lookups, instead of O(span²) re-scans.
625    subalg_add(&mut by_degree, &mut pivots, &mut worklist, max_degree, unit);
626    for g in &gen_combos {
627        subalg_add(
628            &mut by_degree,
629            &mut pivots,
630            &mut worklist,
631            max_degree,
632            g.clone(),
633        );
634    }
635    while let Some(b) = worklist.pop() {
636        for g in &gen_combos {
637            let p = combo_mul(&b, g);
638            subalg_add(&mut by_degree, &mut pivots, &mut worklist, max_degree, p);
639        }
640    }
641    // Record the algebra-generator keys: each `Sq^{2ⁱ}` is the largest monomial in its degree, so it is its
642    // own pivot and sits as a single basis element addressed by `[degree, index]`.
643    let gen_keys: Vec<(usize, Vec<usize>)> = gens
644        .iter()
645        .map(|g| {
646            let d: usize = g.iter().sum();
647            (d, vec![d, pivots[d][g]])
648        })
649        .collect();
650    SubAlgebra {
651        by_degree,
652        pivots,
653        gen_keys,
654    }
655}
656
657impl Algebra for SubAlgebra {
658    fn basis(&self, degree: usize) -> Vec<Vec<usize>> {
659        (0..self.by_degree.get(degree).map_or(0, |v| v.len()))
660            .map(|i| vec![degree, i])
661            .collect()
662    }
663    fn multiply(&self, a: &[usize], b: &[usize]) -> std::collections::HashSet<Vec<usize>> {
664        let prod = combo_mul(&self.by_degree[a[0]][a[1]], &self.by_degree[b[0]][b[1]]);
665        let pd = a[0] + b[0];
666        match self.by_degree.get(pd) {
667            Some(basis) if !prod.is_empty() => express_in_basis(&prod, basis, &self.pivots[pd])
668                .into_iter()
669                .map(|i| vec![pd, i])
670                .collect(),
671            _ => std::collections::HashSet::new(),
672        }
673    }
674    fn generators(&self, max_degree: usize) -> Vec<(usize, Vec<usize>)> {
675        self.gen_keys
676            .iter()
677            .filter(|(d, _)| *d <= max_degree)
678            .cloned()
679            .collect()
680    }
681}
682
683/// Left-multiply a boundary by a monomial over an arbitrary algebra: `m · Σ(g', a) = Σ(g', m·a)` over `Z/2`.
684fn act_boundary_over(
685    alg: &dyn Algebra,
686    m: &[usize],
687    boundary: &[(usize, Vec<usize>)],
688) -> std::collections::HashSet<(usize, Vec<usize>)> {
689    let mut acc: std::collections::HashSet<(usize, Vec<usize>)> = std::collections::HashSet::new();
690    for (g, a) in boundary {
691        for ap in alg.multiply(m, a) {
692            let key = (*g, ap);
693            if !acc.insert(key.clone()) {
694                acc.remove(&key);
695            }
696        }
697    }
698    acc
699}
700
701/// The degree-`t` basis of `C_s = ⊕ A·g` over an arbitrary algebra: `(generator index, basis element of
702/// degree t−deg(g))`.
703fn module_basis_over(alg: &dyn Algebra, gens: &[ResGen], t: usize) -> Vec<(usize, Vec<usize>)> {
704    let mut out = Vec::new();
705    for (gi, g) in gens.iter().enumerate() {
706        if g.degree <= t {
707            for m in alg.basis(t - g.degree) {
708                out.push((gi, m));
709            }
710        }
711    }
712    out
713}
714
715/// Left-multiply a boundary by a Steenrod monomial: `m · Σ(g', a) = Σ(g', adem_reduce(m·a))`, over `Z/2`.
716fn act_boundary(
717    m: &[usize],
718    boundary: &[(usize, Vec<usize>)],
719) -> std::collections::HashSet<(usize, Vec<usize>)> {
720    act_boundary_over(&SteenrodAlgebra, m, boundary)
721}
722
723/// The degree-`t` basis of `C_s = ⊕ 𝒜·g`: pairs `(generator index, admissible monomial of degree t−deg(g))`.
724fn module_basis(gens: &[ResGen], t: usize) -> Vec<(usize, Vec<usize>)> {
725    module_basis_over(&SteenrodAlgebra, gens, t)
726}
727
728/// Build the minimal free resolution of `Z/2` over the Steenrod algebra up to homological degree `max_s`
729/// and internal degree `max_t`. `Ext^{s,t} = #(generators of C_s in degree t)`.
730fn minimal_resolution(max_s: usize, max_t: usize) -> Vec<Vec<ResGen>> {
731    minimal_resolution_over(&SteenrodAlgebra, max_s, max_t)
732}
733
734/// Build the minimal free resolution of `Z/2` over an **arbitrary augmented algebra** up to homological
735/// degree `max_s` and internal degree `max_t`. `Ext^{s,t} = #(generators of C_s in degree t)`. The algorithm
736/// is unchanged from the Steenrod case — only the basis and product come from `alg` — which is the whole
737/// point: one resolution engine, every algebra.
738fn minimal_resolution_over(alg: &dyn Algebra, max_s: usize, max_t: usize) -> Vec<Vec<ResGen>> {
739    let mut res: Vec<Vec<ResGen>> = vec![vec![ResGen {
740        degree: 0,
741        boundary: vec![],
742    }]]; // C_0 = A·g₀
743    for s in 1..=max_s {
744        let mut new_gens: Vec<ResGen> = Vec::new();
745        for t in 1..=max_t {
746            // Basis of C_{s-1}(t) and an index for it.
747            let prev_basis = module_basis_over(alg, &res[s - 1], t);
748            let prev_idx: std::collections::HashMap<(usize, Vec<usize>), usize> = prev_basis
749                .iter()
750                .cloned()
751                .enumerate()
752                .map(|(i, b)| (b, i))
753                .collect();
754
755            // Kernel of d_{s-1} : C_{s-1}(t) → C_{s-2}(t).  (For s=1, d_0 is the augmentation: every
756            // positive-degree element is in the kernel, so ker = the whole basis.)
757            let kernel: Vec<Bits> = if s == 1 {
758                (0..prev_basis.len()).map(Bits::bit).collect()
759            } else {
760                let cc_basis = module_basis_over(alg, &res[s - 2], t);
761                let cc_idx: std::collections::HashMap<(usize, Vec<usize>), usize> = cc_basis
762                    .iter()
763                    .cloned()
764                    .enumerate()
765                    .map(|(i, b)| (b, i))
766                    .collect();
767                let cols: Vec<Bits> = prev_basis
768                    .iter()
769                    .map(|(gi, m)| {
770                        let img = act_boundary_over(alg, m, &res[s - 1][*gi].boundary);
771                        Bits::from_indices(img.into_iter().map(|e| cc_idx[&e]))
772                    })
773                    .collect();
774                z2_nullspace(&cols)
775            };
776
777            // Decomposables A⁺·ker = span{ g · z : g a GENERATOR, z ∈ ker(d_{s-1})(t-deg g) }. Because ker is
778            // an A-submodule, multiplying by the generators alone spans A⁺·ker — so we loop the handful of
779            // generators (Sq^{2ⁱ}) instead of the whole algebra. This is the speed symmetry break.
780            let mut decomp: Vec<Bits> = Vec::new();
781            for (gdeg, gkey) in alg.generators(t - 1) {
782                let lower = kernel_at_over(alg, &res, s - 1, t - gdeg);
783                let lower_basis = module_basis_over(alg, &res[s - 1], t - gdeg);
784                for z in &lower.0 {
785                    let mut v = Bits::new();
786                    for (b, (gi, m)) in lower_basis.iter().enumerate() {
787                        if z.get(b) {
788                            for mp in alg.multiply(&gkey, m) {
789                                if let Some(&idx) = prev_idx.get(&(*gi, mp)) {
790                                    v.toggle(idx);
791                                }
792                            }
793                        }
794                    }
795                    if !v.is_zero() {
796                        decomp.push(v);
797                    }
798                }
799            }
800
801            // New generators = kernel vectors independent modulo the decomposables.
802            let mut pivots: std::collections::HashMap<usize, Bits> =
803                std::collections::HashMap::new();
804            for mut d in decomp {
805                while let Some(lead) = d.lowest() {
806                    match pivots.get(&lead) {
807                        Some(p) => d ^= p,
808                        None => {
809                            pivots.insert(lead, d);
810                            break;
811                        }
812                    }
813                }
814            }
815            for kv in &kernel {
816                let mut r = kv.clone();
817                while let Some(lead) = r.lowest() {
818                    match pivots.get(&lead) {
819                        Some(p) => r ^= p,
820                        None => break,
821                    }
822                }
823                if let Some(lead) = r.lowest() {
824                    pivots.insert(lead, r);
825                    let boundary: Vec<(usize, Vec<usize>)> = (0..prev_basis.len())
826                        .filter(|&b| kv.get(b))
827                        .map(|b| prev_basis[b].clone())
828                        .collect();
829                    new_gens.push(ResGen {
830                        degree: t,
831                        boundary,
832                    });
833                }
834            }
835        }
836        res.push(new_gens);
837    }
838    res
839}
840
841/// `(kernel vectors, _)` of `d_{s} : C_{s}(t) → C_{s-1}(t)` — small helper used during decomposable
842/// computation. Returns kernel masks over `module_basis(C_s, t)`.
843fn kernel_at(res: &[Vec<ResGen>], s: usize, t: usize) -> (Vec<Bits>, ()) {
844    kernel_at_over(&SteenrodAlgebra, res, s, t)
845}
846
847/// `kernel_at` over an arbitrary algebra.
848fn kernel_at_over(alg: &dyn Algebra, res: &[Vec<ResGen>], s: usize, t: usize) -> (Vec<Bits>, ()) {
849    let basis = module_basis_over(alg, &res[s], t);
850    if s == 0 {
851        return ((0..basis.len()).map(Bits::bit).collect(), ());
852    }
853    let cc_basis = module_basis_over(alg, &res[s - 1], t);
854    let cc_idx: std::collections::HashMap<(usize, Vec<usize>), usize> = cc_basis
855        .iter()
856        .cloned()
857        .enumerate()
858        .map(|(i, b)| (b, i))
859        .collect();
860    let cols: Vec<Bits> = basis
861        .iter()
862        .map(|(gi, m)| {
863            Bits::from_indices(
864                act_boundary_over(alg, m, &res[s][*gi].boundary)
865                    .into_iter()
866                    .map(|e| cc_idx[&e]),
867            )
868        })
869        .collect();
870    (z2_nullspace(&cols), ())
871}
872
873/// `dim Ext^{s,t}_𝒜(Z/2, Z/2)` — the full Adams `E₂` page from the minimal resolution.
874pub fn ext(max_s: usize, max_t: usize) -> Vec<Vec<usize>> {
875    ext_over(&SteenrodAlgebra, max_s, max_t)
876}
877
878/// `dim Ext^{s,t}_A(Z/2, Z/2)` over an arbitrary algebra `A` — the Adams `E₂` page for whatever spectrum `A`
879/// resolves. `A = 𝒜` gives the sphere; `A = A(1)` gives `ko`.
880fn ext_over(alg: &dyn Algebra, max_s: usize, max_t: usize) -> Vec<Vec<usize>> {
881    let res = minimal_resolution_over(alg, max_s, max_t);
882    (0..=max_s)
883        .map(|s| {
884            (0..=max_t)
885                .map(|t| res[s].iter().filter(|g| g.degree == t).count())
886                .collect()
887        })
888        .collect()
889}
890
891/// `h₀`-multiplication read straight off the resolution boundaries: generator `g` at stage `s` is sent by
892/// `h₀ = Sq¹` to the stage-`(s+1)` generators `g'` whose boundary contains `Sq¹·g` (the term `(gi, [1])`).
893/// The symmetry is already in the resolution — no Yoneda lifting needed.
894fn h0_targets(res: &[Vec<ResGen>], s: usize, gi: usize) -> Vec<usize> {
895    if s + 1 >= res.len() {
896        return vec![];
897    }
898    res[s + 1]
899        .iter()
900        .enumerate()
901        .filter(|(_, g)| {
902            g.boundary
903                .iter()
904                .any(|(j, m)| *j == gi && m.as_slice() == [1])
905        })
906        .map(|(idx, _)| idx)
907        .collect()
908}
909
910/// The EXACT 2-local stable group of stem `n`, as the sorted multiset of `h₀`-tower lengths (a tower of
911/// length `L` is a summand `Z/2^L`). Read from the resolution's `h₀`-structure — the symmetry a dim count
912/// ignores. `[3] = Z/8`, `[1,1] = (Z/2)²`, etc.
913fn stem_2local_tower_lengths(res: &[Vec<ResGen>], n: usize) -> Vec<usize> {
914    let in_stem =
915        |s: usize, gi: usize| s < res.len() && gi < res[s].len() && res[s][gi].degree == n + s;
916    // every (s+1,t) that is an h₀-image of a stem-n generator
917    let mut is_target: std::collections::HashSet<(usize, usize)> = std::collections::HashSet::new();
918    for s in 0..res.len() {
919        for gi in 0..res[s].len() {
920            if in_stem(s, gi) {
921                for t in h0_targets(res, s, gi) {
922                    if in_stem(s + 1, t) {
923                        is_target.insert((s + 1, t));
924                    }
925                }
926            }
927        }
928    }
929    let mut lengths = Vec::new();
930    for s in 0..res.len() {
931        for gi in 0..res[s].len() {
932            if in_stem(s, gi) && !is_target.contains(&(s, gi)) {
933                // tower bottom: walk h₀ upward, counting the height
934                let mut len = 1;
935                let (mut cs, mut cgi) = (s, gi);
936                loop {
937                    let ups: Vec<usize> = h0_targets(res, cs, cgi)
938                        .into_iter()
939                        .filter(|&t| in_stem(cs + 1, t))
940                        .collect();
941                    if let Some(&t) = ups.first() {
942                        len += 1;
943                        cs += 1;
944                        cgi = t;
945                    } else {
946                        break;
947                    }
948                }
949                lengths.push(len);
950            }
951        }
952    }
953    lengths.sort_unstable();
954    lengths
955}
956
957/// The action of a Steenrod monomial on a class in `H*(BZ/2) = Z/2[x]` (apply the squares right-to-left).
958pub fn act_monomial(m: &[usize], poly: &[u8]) -> Vec<u8> {
959    let mut p = poly.to_vec();
960    for &i in m.iter().rev() {
961        p = apply_sq(i, &p);
962    }
963    trim(p)
964}
965
966/// Adem-reduce a monomial to the admissible basis, but keep the **unit** `Sq⁰ = 1` (the empty monomial) as
967/// `[]` rather than dropping it — `adem_reduce` treats `[]` as zero, which is wrong inside the algebra's
968/// product/coproduct where `1` must survive.
969fn reduce_unit(m: &[usize]) -> std::collections::HashSet<Vec<usize>> {
970    let filtered: Vec<usize> = m.iter().copied().filter(|&i| i > 0).collect();
971    if filtered.is_empty() {
972        return std::iter::once(vec![]).collect();
973    }
974    adem_reduce(&filtered)
975}
976
977/// The **coproduct** on the Steenrod algebra: `ψ(Sqⁿ) = Σ_{a+b=n} Sqᵃ ⊗ Sqᵇ` (the Cartan diagonal),
978/// extended as an algebra map `ψ(xy) = ψ(x)ψ(y)` with `(a⊗b)(c⊗d) = ac⊗bd`, each tensor leg reduced to the
979/// admissible basis. Returns the `Z/2` support as a set of `(admissible, admissible)` pairs. This is the
980/// structure that makes `C ⊗ C` an 𝒜-module and powers the chain-level diagonal.
981fn coproduct(m: &[usize]) -> std::collections::HashSet<(Vec<usize>, Vec<usize>)> {
982    let mut acc: std::collections::HashSet<(Vec<usize>, Vec<usize>)> =
983        std::iter::once((vec![], vec![])).collect(); // ψ(1) = 1⊗1
984    for &n in m {
985        let mut next: std::collections::HashSet<(Vec<usize>, Vec<usize>)> =
986            std::collections::HashSet::new();
987        for (lacc, racc) in &acc {
988            for a in 0..=n {
989                let (mut ll, mut rr) = (lacc.clone(), racc.clone());
990                if a > 0 {
991                    ll.push(a);
992                }
993                if n - a > 0 {
994                    rr.push(n - a);
995                }
996                for la in reduce_unit(&ll) {
997                    for ra in reduce_unit(&rr) {
998                        let key = (la.clone(), ra);
999                        if !next.insert(key.clone()) {
1000                            next.remove(&key);
1001                        }
1002                    }
1003                }
1004            }
1005        }
1006        acc = next;
1007    }
1008    acc
1009}
1010
1011/// A chain element of `C_s = ⊕ 𝒜·g`: its `Z/2` support, a set of terms `(generator index, admissible
1012/// Steenrod monomial)` standing for `Σ m·g`.
1013type Chain = std::collections::HashSet<(usize, Vec<usize>)>;
1014
1015/// `Z/2`-add `b` into `a` (re-insertion cancels).
1016fn chain_add(a: &mut Chain, b: Chain) {
1017    for e in b {
1018        if !a.insert(e.clone()) {
1019            a.remove(&e);
1020        }
1021    }
1022}
1023
1024/// Left-act a Steenrod monomial on a chain element: `m·Σ(g,n) = Σ(g, adem_reduce(m·n))`.
1025fn act_chain(m: &[usize], elem: &Chain) -> Chain {
1026    let v: Vec<(usize, Vec<usize>)> = elem.iter().cloned().collect();
1027    act_boundary(m, &v)
1028}
1029
1030/// Solve `∂x = target` for a chain element `x ∈ (C_s)_deg`, given `target ∈ (C_{s-1})_deg`. The minimal
1031/// resolution is exact, so `target ∈ im ∂` whenever it is a cycle; we pick one preimage by `Z/2` Gaussian
1032/// elimination — a chosen contracting homotopy. `None` only if `target ∉ im ∂` (a resolution-exactness bug,
1033/// surfaced rather than papered over).
1034fn solve_boundary(res: &[Vec<ResGen>], s: usize, deg: usize, target: &Chain) -> Option<Chain> {
1035    let src_basis = module_basis(&res[s], deg);
1036    let tgt_basis = module_basis(&res[s - 1], deg);
1037    let tgt_idx: std::collections::HashMap<(usize, Vec<usize>), usize> = tgt_basis
1038        .iter()
1039        .cloned()
1040        .enumerate()
1041        .map(|(i, b)| (b, i))
1042        .collect();
1043    let mask = |c: &Chain| -> Bits { Bits::from_indices(c.iter().map(|e| tgt_idx[e])) };
1044    let cols: Vec<Bits> = src_basis
1045        .iter()
1046        .map(|(gi, m)| mask(&act_boundary(m, &res[s][*gi].boundary)))
1047        .collect();
1048    // Row-reduce the columns, tracking which source columns XOR to each pivot row.
1049    let mut elim: Vec<(usize, Bits, Bits)> = Vec::new(); // (pivot bit, reduced column, source combination)
1050    for (j, c) in cols.iter().enumerate() {
1051        let (mut r, mut src) = (c.clone(), Bits::bit(j));
1052        for (piv, rc, sm) in &elim {
1053            if r.get(*piv) {
1054                r ^= rc;
1055                src ^= sm;
1056            }
1057        }
1058        if let Some(lead) = r.lowest() {
1059            elim.push((lead, r, src));
1060        }
1061    }
1062    let (mut tr, mut tsrc) = (mask(target), Bits::new());
1063    for (piv, rc, sm) in &elim {
1064        if tr.get(*piv) {
1065            tr ^= rc;
1066            tsrc ^= sm;
1067        }
1068    }
1069    if !tr.is_zero() {
1070        return None;
1071    }
1072    Some(
1073        (0..src_basis.len())
1074            .filter(|&j| tsrc.get(j))
1075            .map(|j| src_basis[j].clone())
1076            .collect(),
1077    )
1078}
1079
1080/// The **Yoneda product** `Ext^{a_s,t_a} ⊗ Ext^{b_s,t_b} → Ext^{a_s+b_s, t_a+t_b}` on the cohomology of the
1081/// Steenrod algebra, computed from the resolution itself. The cocycle dual to generator `(a_s, a_gi)` is
1082/// lifted to a comparison chain map `φ_•: C_{a_s+•} → C_•` (`ε·φ_0 = dual`, `∂φ_k = φ_{k-1}∂`, each step a
1083/// `Z/2` boundary solve), and the product is `dual_b ∘ φ_{b_s}` — read off as the `(b_gi, identity)`
1084/// coefficient. The comparison map is the diagonal `X → X×X` dualized onto the resolution: the geometric
1085/// symmetry made algebra. Returns the product's `Z/2` support among the `C_{a_s+b_s}` generators.
1086pub fn yoneda_product(
1087    res: &[Vec<ResGen>],
1088    a_s: usize,
1089    a_gi: usize,
1090    b_s: usize,
1091    b_gi: usize,
1092) -> Vec<usize> {
1093    let t_a = res[a_s][a_gi].degree;
1094    let t_b = res[b_s][b_gi].degree;
1095    // φ_0 : C_{a_s} → C_0, the cocycle dual to generator a: g_{a_s,i} ↦ δ_{i,a}·g₀.
1096    let mut phi: Vec<std::collections::HashMap<usize, Chain>> = Vec::new();
1097    let mut p0 = std::collections::HashMap::new();
1098    for i in 0..res[a_s].len() {
1099        let mut c = Chain::new();
1100        if i == a_gi {
1101            c.insert((0, vec![]));
1102        }
1103        p0.insert(i, c);
1104    }
1105    phi.push(p0);
1106    // Lift along the resolution up to φ_{b_s}.
1107    for k in 1..=b_s {
1108        let mut pk: std::collections::HashMap<usize, Chain> = std::collections::HashMap::new();
1109        for i in 0..res[a_s + k].len() {
1110            let d_i = res[a_s + k][i].degree;
1111            if d_i < t_a {
1112                pk.insert(i, Chain::new()); // below the cocycle's degree φ vanishes; avoids a degree underflow
1113                continue;
1114            }
1115            // r = φ_{k-1}(∂ g_{a_s+k, i})  ∈ C_{k-1}
1116            let mut r = Chain::new();
1117            for (j, m) in &res[a_s + k][i].boundary {
1118                chain_add(&mut r, act_chain(m, &phi[k - 1][j]));
1119            }
1120            let x = if r.is_empty() {
1121                Chain::new()
1122            } else {
1123                solve_boundary(res, k, d_i - t_a, &r)
1124                    .expect("minimal resolution is exact: ∂x = r is solvable")
1125            };
1126            pk.insert(i, x);
1127        }
1128        phi.push(pk);
1129    }
1130    // Pair with dual_b: the (b_gi, identity) coefficient of φ_{b_s}(g) over the (t_a+t_b)-generators.
1131    (0..res[a_s + b_s].len())
1132        .filter(|&i| {
1133            res[a_s + b_s][i].degree == t_a + t_b && phi[b_s][&i].contains(&(b_gi, vec![]))
1134        })
1135        .collect()
1136}
1137
1138/// A basis term of `C ⊗ C`: `(p, i, m1, q, j, m2)` standing for `(m1·g_{p,i}) ⊗ (m2·g_{q,j})`, with `p`/`q`
1139/// the homological degrees of the two legs. An element is the `Z/2` support set of such terms.
1140type TensorTerm = (usize, usize, Vec<usize>, usize, usize, Vec<usize>);
1141type Tensor = std::collections::HashSet<TensorTerm>;
1142
1143/// `Z/2`-add `b` into `a`.
1144fn tensor_add(a: &mut Tensor, b: Tensor) {
1145    for e in b {
1146        if !a.insert(e.clone()) {
1147            a.remove(&e);
1148        }
1149    }
1150}
1151
1152/// Internal degree of a homogeneous tensor element.
1153fn tensor_degree(res: &[Vec<ResGen>], t: &Tensor) -> Option<usize> {
1154    t.iter().next().map(|(p, i, m1, q, j, m2)| {
1155        res[*p][*i].degree
1156            + m1.iter().sum::<usize>()
1157            + res[*q][*j].degree
1158            + m2.iter().sum::<usize>()
1159    })
1160}
1161
1162/// The boundary on `C ⊗ C`: `∂(a⊗b) = ∂a⊗b + a⊗∂b` (over `Z/2` the Koszul signs vanish).
1163fn tensor_boundary(res: &[Vec<ResGen>], elem: &Tensor) -> Tensor {
1164    let mut out = Tensor::new();
1165    for (p, i, m1, q, j, m2) in elem {
1166        if *p >= 1 {
1167            for (i2, m1b) in act_boundary(m1, &res[*p][*i].boundary) {
1168                let term = (*p - 1, i2, m1b, *q, *j, m2.clone());
1169                if !out.insert(term.clone()) {
1170                    out.remove(&term);
1171                }
1172            }
1173        }
1174        if *q >= 1 {
1175            for (j2, m2b) in act_boundary(m2, &res[*q][*j].boundary) {
1176                let term = (*p, *i, m1.clone(), *q - 1, j2, m2b);
1177                if !out.insert(term.clone()) {
1178                    out.remove(&term);
1179                }
1180            }
1181        }
1182    }
1183    out
1184}
1185
1186/// The diagonal 𝒜-action on `C ⊗ C`: `m·(a⊗b) = Σ_{ψ(m)=Σ m'⊗m''} (m'·a) ⊗ (m''·b)`. This is what makes
1187/// `C ⊗ C` a Steenrod-module and lets the diagonal be lifted 𝒜-linearly.
1188fn act_tensor(m: &[usize], elem: &Tensor) -> Tensor {
1189    let psi = coproduct(m);
1190    let mut out = Tensor::new();
1191    for (p, i, m1, q, j, m2) in elem {
1192        for (ml, mr) in &psi {
1193            let (mut left, mut right) = (ml.clone(), mr.clone());
1194            left.extend_from_slice(m1);
1195            right.extend_from_slice(m2);
1196            for a in reduce_unit(&left) {
1197                for b in reduce_unit(&right) {
1198                    let term = (*p, *i, a.clone(), *q, *j, b);
1199                    if !out.insert(term.clone()) {
1200                        out.remove(&term);
1201                    }
1202                }
1203            }
1204        }
1205    }
1206    out
1207}
1208
1209/// The `Z/2`-basis of `(C ⊗ C)_n` in internal degree `t` — every leg-split `p+q=n`, `t_l+t_r=t`.
1210fn tensor_basis(res: &[Vec<ResGen>], n: usize, t: usize) -> Vec<TensorTerm> {
1211    let mut out = Vec::new();
1212    for p in 0..=n {
1213        let q = n - p;
1214        if p >= res.len() || q >= res.len() {
1215            continue;
1216        }
1217        for tl in 0..=t {
1218            let tr = t - tl;
1219            for (i, m1) in module_basis(&res[p], tl) {
1220                for (j, m2) in module_basis(&res[q], tr) {
1221                    out.push((p, i, m1.clone(), q, j, m2.clone()));
1222                }
1223            }
1224        }
1225    }
1226    out
1227}
1228
1229/// Solve `∂_{C⊗C} x = target` for `x ∈ (C⊗C)_n` — cap-free `Z/2` Gaussian elimination over tensor basis
1230/// elements (pivot = the largest term), tracking which source basis elements combine. `None` only if
1231/// `target ∉ im ∂` (a coherence bug, surfaced not hidden).
1232fn solve_tensor_boundary(res: &[Vec<ResGen>], n: usize, target: &Tensor) -> Option<Tensor> {
1233    fn reduce(
1234        mut col: Tensor,
1235        mut src: Tensor,
1236        elim: &[(TensorTerm, Tensor, Tensor)],
1237    ) -> (Tensor, Tensor) {
1238        loop {
1239            let piv = match col.iter().max() {
1240                Some(p) => p.clone(),
1241                None => return (col, src),
1242            };
1243            match elim.iter().find(|(p, _, _)| *p == piv) {
1244                Some((_, rc, sm)) => {
1245                    for x in rc {
1246                        if !col.insert(x.clone()) {
1247                            col.remove(x);
1248                        }
1249                    }
1250                    for x in sm {
1251                        if !src.insert(x.clone()) {
1252                            src.remove(x);
1253                        }
1254                    }
1255                }
1256                None => return (col, src),
1257            }
1258        }
1259    }
1260    let t = match tensor_degree(res, target) {
1261        Some(t) => t,
1262        None => return Some(Tensor::new()),
1263    };
1264    let mut elim: Vec<(TensorTerm, Tensor, Tensor)> = Vec::new(); // (pivot, reduced column, source combination)
1265    for b in tensor_basis(res, n, t) {
1266        let col = tensor_boundary(res, &std::iter::once(b.clone()).collect());
1267        let src: Tensor = std::iter::once(b).collect();
1268        let (rc, sm) = reduce(col, src, &elim);
1269        if let Some(piv) = rc.iter().max().cloned() {
1270            elim.push((piv, rc, sm));
1271        }
1272    }
1273    let (rc, sm) = reduce(target.clone(), Tensor::new(), &elim);
1274    rc.is_empty().then_some(sm)
1275}
1276
1277/// The chain-level **diagonal** `Δ₀: C → C ⊗ C` — an 𝒜-linear chain map with `Δ₀(g₀) = g₀ ⊗ g₀`, built by
1278/// lifting up the resolution (`∂_{C⊗C} Δ₀(g) = Δ₀(∂g)`, solved leg-aware). It is the topological diagonal
1279/// `X → X×X` transported onto the algebraic resolution; its cup-`i` refinements carry the Steenrod
1280/// operations on Ext. `delta[n][&k] = Δ₀(g_{n,k})`.
1281fn diagonal(res: &[Vec<ResGen>], max_n: usize) -> Vec<std::collections::HashMap<usize, Tensor>> {
1282    let mut delta: Vec<std::collections::HashMap<usize, Tensor>> = Vec::new();
1283    let mut d0 = std::collections::HashMap::new();
1284    d0.insert(
1285        0usize,
1286        std::iter::once((0, 0, vec![], 0, 0, vec![])).collect::<Tensor>(),
1287    );
1288    delta.push(d0);
1289    for n in 1..=max_n {
1290        let mut dn: std::collections::HashMap<usize, Tensor> = std::collections::HashMap::new();
1291        for k in 0..res[n].len() {
1292            let mut rhs = Tensor::new(); // Δ₀(∂ g_{n,k}) = Σ_{(j,mb)∈∂} mb·Δ₀(g_{n-1,j})
1293            for (j, mb) in &res[n][k].boundary {
1294                tensor_add(&mut rhs, act_tensor(mb, &delta[n - 1][j]));
1295            }
1296            let x = solve_tensor_boundary(res, n, &rhs)
1297                .expect("diagonal lifts: ∂x = Δ₀(∂g) is solvable");
1298            dn.insert(k, x);
1299        }
1300        delta.push(dn);
1301    }
1302    delta
1303}
1304
1305/// The leg-swap `T` on `C ⊗ C`: `(a⊗b) ↦ (b⊗a)`.
1306fn tensor_swap(t: &Tensor) -> Tensor {
1307    t.iter()
1308        .map(|(p, i, m1, q, j, m2)| (*q, *j, m2.clone(), *p, *i, m1.clone()))
1309        .collect()
1310}
1311
1312/// The next **cup-`i` coherence homotopy** from the previous one: `Δ_i: C_n → (C⊗C)_{n+i}` satisfying
1313/// `∂Δ_i + Δ_i∂ = Δ_{i-1} + TΔ_{i-1}`, with `Δ_i(g₀) = 0`. `shift = i` is the homological shift `Δ_i`
1314/// carries. This single recursion is the whole `E_∞`/`H_∞` ladder: `Δ₀` (the diagonal, `shift 0`) gives the
1315/// cup product, `Δ₁` (`shift 1`) the `Sq⁰` doubling, `Δ₂` (`shift 2`) the doubling of Ext² classes, and so
1316/// on up — each measuring the failure of the previous to be symmetric.
1317fn cup_homotopy(
1318    res: &[Vec<ResGen>],
1319    max_n: usize,
1320    shift: usize,
1321    prev: &[std::collections::HashMap<usize, Tensor>],
1322) -> Vec<std::collections::HashMap<usize, Tensor>> {
1323    let mut d: Vec<std::collections::HashMap<usize, Tensor>> = Vec::new();
1324    d.push(std::iter::once((0usize, Tensor::new())).collect()); // Δ_i(g₀) = 0
1325    for n in 1..=max_n {
1326        let mut dn: std::collections::HashMap<usize, Tensor> = std::collections::HashMap::new();
1327        for k in 0..res[n].len() {
1328            let mut rhs = prev[n][&k].clone(); // Δ_{i-1}(g) + TΔ_{i-1}(g) + Δ_i(∂g)
1329            tensor_add(&mut rhs, tensor_swap(&prev[n][&k]));
1330            for (j, mb) in &res[n][k].boundary {
1331                tensor_add(&mut rhs, act_tensor(mb, &d[n - 1][j]));
1332            }
1333            let x = solve_tensor_boundary(res, n + shift, &rhs)
1334                .expect("cup-i homotopy lifts: ∂x = Δ+TΔ+Δ∂");
1335            dn.insert(k, x);
1336        }
1337        d.push(dn);
1338    }
1339    d
1340}
1341
1342/// The cup-1 homotopy `Δ₁` — the first coherence homotopy of cocommutativity. Pairing a class with itself
1343/// through `Δ₁` is the `Sq⁰` doubling operation on Ext.
1344fn diagonal_1(
1345    res: &[Vec<ResGen>],
1346    max_n: usize,
1347    delta: &[std::collections::HashMap<usize, Tensor>],
1348) -> Vec<std::collections::HashMap<usize, Tensor>> {
1349    cup_homotopy(res, max_n, 1, delta)
1350}
1351
1352/// The algebraic **`Sq⁰` (doubling) operation** on the one-line classes of Ext, computed from the cup-1
1353/// homotopy: `Sq⁰(h_i) = h_i ⌣_1 h_i = (dual ⊗ dual) ∘ Δ₁` on `C_1`. Returns its `Z/2` support among the
1354/// degree-`2^{i+1}` generators of `C_1`. The Adams doubling `Sq⁰(h_i) = h_{i+1}` is then a derived fact.
1355fn sq0_on_h(
1356    res: &[Vec<ResGen>],
1357    delta1: &[std::collections::HashMap<usize, Tensor>],
1358    gi: usize,
1359) -> Vec<usize> {
1360    let want = 2 * res[1][gi].degree;
1361    (0..res[1].len())
1362        .filter(|&k| {
1363            res[1][k].degree == want && delta1[1][&k].contains(&(1, gi, vec![], 1, gi, vec![]))
1364        })
1365        .collect()
1366}
1367
1368/// `Sq⁰` on a single Ext² generator class `gx` (e.g. `h_i²`), via the cup-2 homotopy: `Sq⁰(x) = x ⌣_2 x =
1369/// (dual ⊗ dual) ∘ Δ₂` on `C_2`, read as the `((2,gx,1),(2,gx,1))` coefficient over the degree-`2t`
1370/// generators of `C_2`. Used to show the doubling is a ring endomorphism (`Sq⁰(h_i²) = h_{i+1}²`).
1371fn sq0_on_ext2(
1372    res: &[Vec<ResGen>],
1373    delta2: &[std::collections::HashMap<usize, Tensor>],
1374    gx: usize,
1375) -> Vec<usize> {
1376    let want = 2 * res[2][gx].degree;
1377    (0..res[2].len())
1378        .filter(|&k| {
1379            res[2][k].degree == want && delta2[2][&k].contains(&(2, gx, vec![], 2, gx, vec![]))
1380        })
1381        .collect()
1382}
1383
1384/// The whole tower of cup-`i` diagonals `[Δ₀, Δ₁, …, Δ_max_shift]` built off one resolution, each lifted up
1385/// to homological degree `max_n`. `Δ₀` is the diagonal; `Δ_i = cup_homotopy(Δ_{i-1})`.
1386fn cup_diagonals(
1387    res: &[Vec<ResGen>],
1388    max_shift: usize,
1389    max_n: usize,
1390) -> Vec<Vec<std::collections::HashMap<usize, Tensor>>> {
1391    let mut out = vec![diagonal(res, max_n)];
1392    for i in 1..=max_shift {
1393        let prev = out[i - 1].clone();
1394        out.push(cup_homotopy(res, max_n, i, &prev));
1395    }
1396    out
1397}
1398
1399/// The algebraic **`Sq⁰` doubling** applied to *any* Ext class — a single generator `gx ∈ Ext^{s,t}` — via
1400/// the cup-`s` homotopy: `Sq⁰(x) = x ⌣_s x = (dual ⊗ dual) ∘ Δ_s` on `C_s`, read as the
1401/// `((s,gx,1),(s,gx,1))` coefficient over the degree-`2t` generators of `C_s`. One uniform operator across
1402/// the whole chart; `deltas[i]` must be `Δ_i`. This is the automation of the doubling symmetry: feed it any
1403/// class, harvest `Sq⁰` of it.
1404fn sq0(
1405    res: &[Vec<ResGen>],
1406    deltas: &[Vec<std::collections::HashMap<usize, Tensor>>],
1407    s: usize,
1408    gx: usize,
1409) -> Vec<usize> {
1410    let want = 2 * res[s][gx].degree;
1411    let ds = &deltas[s]; // Δ_s
1412    (0..res[s].len())
1413        .filter(|&k| {
1414            res[s][k].degree == want && ds[s][&k].contains(&(s, gx, vec![], s, gx, vec![]))
1415        })
1416        .collect()
1417}
1418
1419/// One machine-derived fact about the Adams `E₂` chart of the sphere. Every variant is *computed* from the
1420/// minimal resolution and its chain-level diagonal — none is asserted.
1421#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
1422pub enum AdamsFact {
1423    /// `dim Ext^{s,t}_𝒜(Z/2, Z/2) = dim` — a point of the chart.
1424    Dimension { s: usize, t: usize, dim: usize },
1425    /// `lhs · rhs = result` in the cohomology ring of the Steenrod algebra (a named product).
1426    Product {
1427        lhs: String,
1428        rhs: String,
1429        result: String,
1430    },
1431    /// `lhs · rhs = 0` — an Adem-adjacency / ring vanishing.
1432    Vanishing { lhs: String, rhs: String },
1433    /// `a = b`: two product-paths landed on the same generator. The ring relation, discovered by collision.
1434    Relation { a: String, b: String },
1435    /// `Sq⁰(from) = to` — the algebraic doubling operation on the chart.
1436    Doubling { from: String, to: String },
1437    /// `π_n^s ⊗ Z₍₂₎ = ⊕ Z/2^Lᵢ` — the exact 2-local stable stem, as the `h₀`-tower-length multiset. When
1438    /// `truncated`, an `h₀`-tower runs into the resolution's filtration ceiling, so the group is only a lower
1439    /// bound (e.g. `π_0 = Z₍₂₎`, an infinite tower the finite resolution cannot close).
1440    StableGroup {
1441        stem: usize,
1442        tower_lengths: Vec<usize>,
1443        truncated: bool,
1444    },
1445    /// `Ext^{s,t}` carries a class that is **not a product of the indecomposables `h_i`** — the product-sweep
1446    /// cannot name it. It is the shadow of an Adams differential / a Massey product: the first place the
1447    /// primary (auto-able) structure runs out, and the secondary structure begins.
1448    Secondary { s: usize, t: usize },
1449}
1450
1451impl std::fmt::Display for AdamsFact {
1452    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1453        match self {
1454            AdamsFact::Dimension { s, t, dim } => write!(f, "dim Ext^{{{s},{t}}} = {dim}"),
1455            AdamsFact::Product { lhs, rhs, result } => write!(f, "{lhs} · {rhs} = {result}"),
1456            AdamsFact::Vanishing { lhs, rhs } => write!(f, "{lhs} · {rhs} = 0"),
1457            AdamsFact::Relation { a, b } => write!(f, "{a} = {b}"),
1458            AdamsFact::Doubling { from, to } => write!(f, "Sq⁰({from}) = {to}"),
1459            AdamsFact::StableGroup {
1460                stem,
1461                tower_lengths,
1462                truncated,
1463            } => {
1464                let group = if tower_lengths.is_empty() {
1465                    "0".to_string()
1466                } else {
1467                    tower_lengths
1468                        .iter()
1469                        .map(|l| format!("Z/2^{l}"))
1470                        .collect::<Vec<_>>()
1471                        .join(" ⊕ ")
1472                };
1473                if *truncated {
1474                    write!(f, "π_{stem}^s ⊗ Z₍₂₎ ⊇ {group} (h₀-tower hits the resolution ceiling — infinite/truncated)")
1475                } else {
1476                    write!(f, "π_{stem}^s ⊗ Z₍₂₎ = {group}")
1477                }
1478            }
1479            AdamsFact::Secondary { s, t } => {
1480                write!(f, "Ext^{{{s},{t}}} has a non-product (secondary/Massey) class — un-auto-able by the product sweep")
1481            }
1482        }
1483    }
1484}
1485
1486/// Name every Ext class reachable as a **product of the indecomposables `h_i`**, by multiplying named
1487/// classes on the right by the `h_i` to a fixpoint. Returns the name map keyed by `(s, generator index)`
1488/// together with the product / vanishing / relation facts discovered along the way (a relation surfaces
1489/// whenever two product-paths collide on one generator). Pure ring structure — no chain-level diagonal
1490/// needed, so it is cheap and runs to high internal degree.
1491fn name_by_products(
1492    res: &[Vec<ResGen>],
1493    max_s: usize,
1494    max_t: usize,
1495) -> (
1496    std::collections::HashMap<(usize, usize), String>,
1497    Vec<AdamsFact>,
1498    Vec<(usize, usize)>,
1499) {
1500    let mut names: std::collections::HashMap<(usize, usize), String> =
1501        std::collections::HashMap::new();
1502    let mut facts: Vec<AdamsFact> = Vec::new();
1503    let mut secondary: Vec<(usize, usize)> = Vec::new();
1504    let mut worklist: Vec<(usize, usize)> = Vec::new();
1505    for gi in 0..res[1].len() {
1506        let i = res[1][gi].degree.trailing_zeros();
1507        names.insert((1, gi), format!("h{i}"));
1508        worklist.push((1, gi));
1509    }
1510    worklist.sort_by_key(|&(_, gi)| res[1][gi].degree);
1511    let h_gens: Vec<usize> = (0..res[1].len()).collect();
1512
1513    // Drain the worklist (multiply each named class by the indecomposables); when it empties, name the
1514    // lowest un-named generator as a fresh **secondary generator** `c_k` and keep sweeping. This is how the
1515    // engine "breaks to the next group": it does not prove what `c_k` is, it recognises a detected
1516    // indecomposable and lets the verified product symmetry carry on from it. A product landing on another
1517    // detected secondary class is self-consistent validation — no Massey computation required.
1518    let mut qi = 0;
1519    let mut sec = 0;
1520    loop {
1521        while qi < worklist.len() {
1522            let (s, gi) = worklist[qi];
1523            qi += 1;
1524            let lname = names[&(s, gi)].clone();
1525            for &hgi in &h_gens {
1526                if s + 1 > max_s || res[s][gi].degree + res[1][hgi].degree > max_t {
1527                    continue;
1528                }
1529                let hname = names[&(1, hgi)].clone();
1530                let prod = yoneda_product(res, s, gi, 1, hgi);
1531                if prod.is_empty() {
1532                    facts.push(AdamsFact::Vanishing {
1533                        lhs: lname.clone(),
1534                        rhs: hname,
1535                    });
1536                } else if prod.len() == 1 {
1537                    let key = (s + 1, prod[0]);
1538                    let newname = format!("{lname}{hname}");
1539                    match names.get(&key) {
1540                        Some(existing) if *existing != newname => {
1541                            let (a, b) = if newname < *existing {
1542                                (newname, existing.clone())
1543                            } else {
1544                                (existing.clone(), newname)
1545                            };
1546                            facts.push(AdamsFact::Relation { a, b });
1547                        }
1548                        Some(_) => {}
1549                        None => {
1550                            names.insert(key, newname.clone());
1551                            worklist.push(key);
1552                            facts.push(AdamsFact::Product {
1553                                lhs: lname.clone(),
1554                                rhs: hname,
1555                                result: newname,
1556                            });
1557                        }
1558                    }
1559                }
1560            }
1561        }
1562        let next = (1..=max_s)
1563            .flat_map(|s| (0..res[s].len()).map(move |gi| (s, gi)))
1564            .filter(|&(s, gi)| res[s][gi].degree <= max_t && !names.contains_key(&(s, gi)))
1565            .min_by_key(|&(s, gi)| (res[s][gi].degree, s));
1566        match next {
1567            Some((s, gi)) => {
1568                names.insert((s, gi), format!("c{sec}"));
1569                sec += 1;
1570                secondary.push((s, gi));
1571                worklist.push((s, gi));
1572            }
1573            None => break,
1574        }
1575    }
1576    (names, facts, secondary)
1577}
1578
1579/// The **un-auto-able classes**: every `(s, t)` in range carrying an Ext generator that the product-sweep
1580/// cannot name — i.e. not a product of the indecomposables. These are exactly where the secondary (Massey)
1581/// structure / the Adams differentials live. Cheap (product structure only); the first one is `c₀` at
1582/// `Ext^{3,11}`, stem 8.
1583fn secondary_classes(max_s: usize, max_t: usize) -> Vec<(usize, usize)> {
1584    let res = minimal_resolution(max_s, max_t);
1585    let (_names, _facts, secondary) = name_by_products(&res, max_s, max_t);
1586    let mut out: Vec<(usize, usize)> = secondary
1587        .iter()
1588        .map(|&(s, gi)| (s, res[s][gi].degree))
1589        .collect();
1590    out.sort();
1591    out.dedup();
1592    out
1593}
1594
1595/// Auto-collect the **primary chart** from a resolution by pure symmetry-breaking — no proving, no
1596/// chain-level diagonal, so it is cheap and runs to a wide range. Gathers chart dimensions, ring products
1597/// and the relations that surface by collision, the un-auto-able (secondary/Massey) generators the product
1598/// sweep cannot name, and the exact 2-local stable stems from the `h₀`-towers. The sorted/deduped catalog.
1599pub fn harvest_secondary_facts(max_s: usize, max_t: usize) -> Vec<AdamsFact> {
1600    let res = minimal_resolution(max_s, max_t);
1601    let (_names, ring_facts, secondary) = name_by_products(&res, max_s, max_t);
1602    let mut facts = ring_facts;
1603    for s in 0..=max_s {
1604        for t in 0..=max_t {
1605            let dim = res[s].iter().filter(|g| g.degree == t).count();
1606            if dim > 0 {
1607                facts.push(AdamsFact::Dimension { s, t, dim });
1608            }
1609        }
1610    }
1611    for &(s, gi) in &secondary {
1612        facts.push(AdamsFact::Secondary {
1613            s,
1614            t: res[s][gi].degree,
1615        });
1616    }
1617    for stem in 0..=max_t.saturating_sub(max_s) {
1618        let lengths = stem_2local_tower_lengths(&res, stem);
1619        if !lengths.is_empty() {
1620            let truncated = res[max_s].iter().any(|g| g.degree == stem + max_s);
1621            facts.push(AdamsFact::StableGroup {
1622                stem,
1623                tower_lengths: lengths,
1624                truncated,
1625            });
1626        }
1627    }
1628    facts.sort();
1629    facts.dedup();
1630    facts
1631}
1632
1633/// The **self-igniting fact engine**: from a single minimal resolution it auto-collects everything the
1634/// symmetry breaking nets — the chart dimensions, the ring products (multiplying named classes by the
1635/// indecomposables to a fixpoint, so ring *relations* surface automatically when two product-paths collide
1636/// on one generator), the `Sq⁰` doubling across the chart, and the exact 2-local stable stems from the
1637/// `h₀`-towers. Returns the deduplicated, sorted catalog. Bounded by `(max_s, max_t)`; the doubling reaches
1638/// through filtration 2 (cup-homotopies `Δ₀..Δ₂`).
1639pub fn harvest_adams_facts(max_s: usize, max_t: usize) -> Vec<AdamsFact> {
1640    let res = minimal_resolution(max_s, max_t);
1641    let dbl_shift = max_s.min(2);
1642    let deltas = cup_diagonals(&res, dbl_shift, dbl_shift);
1643    let mut facts: Vec<AdamsFact> = Vec::new();
1644
1645    // 1. Chart dimensions, straight off the resolution.
1646    for s in 0..=max_s {
1647        for t in 0..=max_t {
1648            let dim = res[s].iter().filter(|g| g.degree == t).count();
1649            if dim > 0 {
1650                facts.push(AdamsFact::Dimension { s, t, dim });
1651            }
1652        }
1653    }
1654
1655    // 2. Name every class reachable as a product of the indecomposables (fixpoint sweep); relations surface
1656    //    by collision. Then flag every Ext generator the sweep CANNOT name — the secondary/Massey classes.
1657    let (names, ring_facts, secondary) = name_by_products(&res, max_s, max_t);
1658    facts.extend(ring_facts);
1659    for &(s, gi) in &secondary {
1660        facts.push(AdamsFact::Secondary {
1661            s,
1662            t: res[s][gi].degree,
1663        });
1664    }
1665
1666    // 3. The Sq⁰ doubling on every named class (through filtration `dbl_shift`).
1667    let mut named: Vec<((usize, usize), String)> =
1668        names.iter().map(|(k, v)| (*k, v.clone())).collect();
1669    named.sort();
1670    for ((s, gi), name) in &named {
1671        if *s == 0 || *s > dbl_shift || 2 * res[*s][*gi].degree > max_t {
1672            continue;
1673        }
1674        let img = sq0(&res, &deltas, *s, *gi);
1675        if img.len() == 1 {
1676            let to = names
1677                .get(&(*s, img[0]))
1678                .cloned()
1679                .unwrap_or_else(|| format!("Sq⁰({name})"));
1680            facts.push(AdamsFact::Doubling {
1681                from: name.clone(),
1682                to,
1683            });
1684        }
1685    }
1686
1687    // 4. The exact 2-local stable stems from the h₀-tower filtration. A stem whose chart reaches the
1688    //    resolution's top filtration is flagged truncated — its h₀-tower may continue past what we computed
1689    //    (this is exactly π_0 = Z₍₂₎, an infinite tower the finite resolution cannot close honestly).
1690    for stem in 0..=max_t.saturating_sub(max_s) {
1691        let lengths = stem_2local_tower_lengths(&res, stem);
1692        if !lengths.is_empty() {
1693            let truncated = res[max_s].iter().any(|g| g.degree == stem + max_s);
1694            facts.push(AdamsFact::StableGroup {
1695                stem,
1696                tower_lengths: lengths,
1697                truncated,
1698            });
1699        }
1700    }
1701
1702    facts.sort();
1703    facts.dedup();
1704    facts
1705}
1706
1707#[cfg(test)]
1708#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/tests.rs"]
1709mod tests;
1710
1711#[cfg(test)]
1712#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/adams_differential_onset.rs"]
1713mod adams_differential_onset;
1714
1715#[cfg(test)]
1716#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/ext_ring_from_the_resolution.rs"]
1717mod ext_ring_from_the_resolution;
1718
1719#[cfg(test)]
1720#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/steenrod_coproduct.rs"]
1721mod steenrod_coproduct;
1722
1723#[cfg(test)]
1724#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/chain_level_diagonal.rs"]
1725mod chain_level_diagonal;
1726
1727#[cfg(test)]
1728#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/adams_fact_engine.rs"]
1729mod adams_fact_engine;
1730
1731#[cfg(test)]
1732#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/algebra_generic_engine.rs"]
1733mod algebra_generic_engine;
1734
1735#[cfg(test)]
1736#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/steenrod/adams_differential_family.rs"]
1737mod adams_differential_family;