logicaffeine_proof/
kan_complex.rs1use crate::two_group::FiniteGroup;
19
20fn face(g: &FiniteGroup, s: &[usize], i: usize) -> Vec<usize> {
23 let n = s.len();
24 if i == 0 {
25 return s[1..].to_vec();
26 }
27 if i == n {
28 return s[..n - 1].to_vec();
29 }
30 let mut out = s.to_vec();
31 out[i - 1] = g.mul[s[i - 1]][s[i]];
32 out.remove(i);
33 out
34}
35
36fn all_simplices(g: &FiniteGroup, n: usize) -> Vec<Vec<usize>> {
38 let mut out: Vec<Vec<usize>> = vec![vec![]];
39 for _ in 0..n {
40 let mut next = Vec::with_capacity(out.len() * g.order());
41 for s in &out {
42 for e in 0..g.order() {
43 let mut t = s.clone();
44 t.push(e);
45 next.push(t);
46 }
47 }
48 out = next;
49 }
50 out
51}
52
53fn for_each_horn(g: &FiniteGroup, n: usize, k: usize, mut each: impl FnMut(usize)) {
57 let lower = all_simplices(g, n - 1);
58 let tops = all_simplices(g, n);
59 let positions: Vec<usize> = (0..=n).filter(|&i| i != k).collect();
60 let base = lower.len();
61 let total: u128 = (base as u128).pow(positions.len() as u32);
62 for idx in 0..total {
63 let mut x = idx;
65 let horn: Vec<(usize, &Vec<usize>)> = positions
66 .iter()
67 .map(|&p| {
68 let a = (x % base as u128) as usize;
69 x /= base as u128;
70 (p, &lower[a])
71 })
72 .collect();
73 let compatible = horn.iter().enumerate().all(|(a, &(i, xi))| {
75 horn[a + 1..]
76 .iter()
77 .all(|&(j, xj)| face(g, xj, i) == face(g, xi, j - 1))
78 });
79 if !compatible {
80 continue;
81 }
82 let fillers = tops
83 .iter()
84 .filter(|y| horn.iter().all(|&(p, xp)| &face(g, y, p) == xp))
85 .count();
86 each(fillers);
87 }
88}
89
90pub fn kan_fills(g: &FiniteGroup, n: usize, k: usize) -> bool {
92 let mut ok = true;
93 for_each_horn(g, n, k, |fillers| ok &= fillers >= 1);
94 ok
95}
96
97pub fn inner_horns_fill_uniquely(g: &FiniteGroup, n: usize, k: usize) -> bool {
100 assert!(0 < k && k < n, "inner horns only");
101 let mut unique = true;
102 for_each_horn(g, n, k, |fillers| unique &= fillers == 1);
103 unique
104}
105
106fn nerve_cochains(g: &FiniteGroup, modulus: usize, k: usize) -> Vec<Vec<usize>> {
108 let size = all_simplices(g, k).len();
109 let mut out: Vec<Vec<usize>> = vec![vec![]];
110 for _ in 0..size {
111 let mut next = Vec::with_capacity(out.len() * modulus);
112 for t in &out {
113 for v in 0..modulus {
114 let mut u = t.clone();
115 u.push(v);
116 next.push(u);
117 }
118 }
119 out = next;
120 }
121 out
122}
123
124fn nerve_coboundary(g: &FiniteGroup, modulus: usize, k: usize, phi: &[usize]) -> Vec<usize> {
127 let sk = all_simplices(g, k);
128 let idx: std::collections::HashMap<Vec<usize>, usize> = sk
129 .iter()
130 .cloned()
131 .enumerate()
132 .map(|(i, s)| (s, i))
133 .collect();
134 let skp1 = all_simplices(g, k + 1);
135 let mut out = vec![0usize; skp1.len()];
136 for (j, sigma) in skp1.iter().enumerate() {
137 let mut val = 0i64;
138 for i in 0..=(k + 1) {
139 let f = face(g, sigma, i);
140 let s = if i % 2 == 0 { 1 } else { -1 };
141 val += s * phi[idx[&f]] as i64;
142 }
143 out[j] = val.rem_euclid(modulus as i64) as usize;
144 }
145 out
146}
147
148pub fn nerve_cohomology_size(g: &FiniteGroup, modulus: usize, n: usize) -> usize {
153 let cocycles = nerve_cochains(g, modulus, n)
154 .into_iter()
155 .filter(|phi| nerve_coboundary(g, modulus, n, phi).iter().all(|&x| x == 0))
156 .count();
157 let mut coboundaries: std::collections::HashSet<Vec<usize>> = std::collections::HashSet::new();
158 for psi in nerve_cochains(g, modulus, n - 1) {
159 coboundaries.insert(nerve_coboundary(g, modulus, n - 1, &psi));
160 }
161 cocycles / coboundaries.len()
162}
163
164#[cfg(test)]
165#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/kan_complex/tests.rs"]
166mod tests;