1fn 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
40pub 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
54pub fn total_square(poly: &[u8]) -> Vec<u8> {
57 let x_plus_x2 = [0u8, 1, 1]; let mut result = vec![0u8];
59 let mut power = vec![1u8]; 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
69pub 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
75fn 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
92pub 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
103fn 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
119pub 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
124pub 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); }
147 }
148 }
149 result
150}
151
152fn 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
188fn 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
221pub 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
239pub 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
257pub 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#[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 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
322fn 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
349fn 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
366fn 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
380fn 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); 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
407pub 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
440fn 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#[derive(Clone)]
461struct ResGen {
462 degree: usize,
463 boundary: Vec<(usize, Vec<usize>)>,
464}
465
466trait Algebra {
470 fn basis(&self, degree: usize) -> Vec<Vec<usize>>;
473 fn multiply(&self, a: &[usize], b: &[usize]) -> std::collections::HashSet<Vec<usize>>;
475 fn generators(&self, max_degree: usize) -> Vec<(usize, Vec<usize>)>;
480}
481
482struct 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])); d <<= 1;
499 }
500 out
501 }
502}
503
504type Combo = std::collections::BTreeSet<Vec<usize>>;
507
508fn 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
525type PivotIndex = std::collections::HashMap<Vec<usize>, usize>;
528
529fn 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, }
547 }
548 used.sort_unstable();
549 used
550}
551
552struct 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
568fn 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
587fn 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
611fn 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 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 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
683fn 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
701fn 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
715fn 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
723fn module_basis(gens: &[ResGen], t: usize) -> Vec<(usize, Vec<usize>)> {
725 module_basis_over(&SteenrodAlgebra, gens, t)
726}
727
728fn minimal_resolution(max_s: usize, max_t: usize) -> Vec<Vec<ResGen>> {
731 minimal_resolution_over(&SteenrodAlgebra, max_s, max_t)
732}
733
734fn 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 }]]; for s in 1..=max_s {
744 let mut new_gens: Vec<ResGen> = Vec::new();
745 for t in 1..=max_t {
746 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 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 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 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
841fn kernel_at(res: &[Vec<ResGen>], s: usize, t: usize) -> (Vec<Bits>, ()) {
844 kernel_at_over(&SteenrodAlgebra, res, s, t)
845}
846
847fn 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
873pub fn ext(max_s: usize, max_t: usize) -> Vec<Vec<usize>> {
875 ext_over(&SteenrodAlgebra, max_s, max_t)
876}
877
878fn 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
891fn 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
910fn 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 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 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
957pub 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
966fn 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
977fn 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(); 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
1011type Chain = std::collections::HashSet<(usize, Vec<usize>)>;
1014
1015fn 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
1024fn 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
1030fn 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 let mut elim: Vec<(usize, Bits, Bits)> = Vec::new(); 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
1080pub 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 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 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()); continue;
1114 }
1115 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 (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
1138type TensorTerm = (usize, usize, Vec<usize>, usize, usize, Vec<usize>);
1141type Tensor = std::collections::HashSet<TensorTerm>;
1142
1143fn 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
1152fn 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
1162fn 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
1186fn 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
1209fn 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
1229fn 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(); 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
1277fn 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(); 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
1305fn 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
1312fn 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()); 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(); 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
1342fn 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
1352fn 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
1368fn 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
1384fn 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
1399fn 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]; (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#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
1422pub enum AdamsFact {
1423 Dimension { s: usize, t: usize, dim: usize },
1425 Product {
1427 lhs: String,
1428 rhs: String,
1429 result: String,
1430 },
1431 Vanishing { lhs: String, rhs: String },
1433 Relation { a: String, b: String },
1435 Doubling { from: String, to: String },
1437 StableGroup {
1441 stem: usize,
1442 tower_lengths: Vec<usize>,
1443 truncated: bool,
1444 },
1445 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
1486fn 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 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
1579fn 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
1595pub 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
1633pub 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 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 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 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 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;