logicaffeine_proof/gf2.rs
1//! The general linear group **GL(n,2)** and the invertibility constant — where the reciprocal
2//! SAT-threshold sum comes home.
3//!
4//! A uniformly random n×n matrix over GF(2) is invertible with probability `Π_{j=1}^n (1 − 2⁻ʲ)`, which
5//! → `φ(½) = 0.2887880951`. The reciprocal first-moment SAT-threshold sum is `−log₂ φ(½)` exactly, so the
6//! two meet at this one constant. And it is *not* a coincidence — it is a **symmetry break**:
7//!
8//! - The invertible matrices are exactly the group `GL(n,2)`.
9//! - `GL(n,2)` acts **simply transitively on ordered bases** of `GF(2)ⁿ` (a matrix is invertible iff its
10//! rows are a basis). So by orbit–stabilizer with a *trivial* stabilizer, `|GL(n,2)|` = the number of
11//! ordered bases = `Π_{i=0}^{n-1} (2ⁿ − 2ⁱ)` — each factor counting the vectors that *avoid the span
12//! built so far*. That step-by-step quotient is the symmetry-broken enumeration; dividing by `2^{n²}`
13//! gives the Euler partial product.
14
15/// `|GL(n,2)|` via the orbit–stabilizer (ordered-basis) factorization `Π_{i=0}^{n-1}(2ⁿ − 2ⁱ)`. Each
16/// factor `2ⁿ − 2ⁱ` is the count of vectors outside the i-dimensional span of the basis chosen so far —
17/// the symmetry-broken enumeration of the bases on which `GL(n,2)` acts simply transitively. Valid up to
18/// `n = 10` before the `u128` product overflows.
19pub fn gl_order(n: u32) -> u128 {
20 let full = 1u128 << n;
21 (0..n).map(|i| full - (1u128 << i)).product()
22}
23
24/// Is an n×n GF(2) matrix (each row packed as the low `n` bits of a `u64`) invertible? Gaussian
25/// elimination over GF(2): invertible iff it reduces to full rank `n`.
26pub fn is_invertible_gf2(n: u32, rows: &[u64]) -> bool {
27 let mut rows = rows.to_vec();
28 let mut rank = 0usize;
29 for col in 0..n {
30 if let Some(p) = (rank..rows.len()).find(|&r| (rows[r] >> col) & 1 == 1) {
31 rows.swap(rank, p);
32 for r in 0..rows.len() {
33 if r != rank && (rows[r] >> col) & 1 == 1 {
34 rows[r] ^= rows[rank];
35 }
36 }
37 rank += 1;
38 }
39 }
40 rank == n as usize
41}
42
43/// Brute-force count of invertible n×n GF(2) matrices, over all `2^{n²}` of them. Feasible for `n ≤ 4`.
44pub fn count_invertible_gf2_bruteforce(n: u32) -> u128 {
45 let cells = n * n;
46 let mask = (1u64 << n) - 1;
47 let mut count = 0u128;
48 for bits in 0u64..(1u64 << cells) {
49 let rows: Vec<u64> = (0..n).map(|r| (bits >> (r * n)) & mask).collect();
50 if is_invertible_gf2(n, &rows) {
51 count += 1;
52 }
53 }
54 count
55}
56
57/// The Euler partial product `Π_{j=1}^n (1 − 2⁻ʲ)` — the exact invertibility *density* `|GL(n,2)| / 2^{n²}`.
58pub fn invertibility_density(n: u32) -> f64 {
59 (1..=n).map(|j| 1.0 - 2f64.powi(-(j as i32))).product()
60}
61
62/// The **complete solution space** of a GF(2) linear system `A x = b`, in *symmetry-broken* form: one
63/// particular solution `x₀` plus a basis of the kernel. Every solution is `x₀ ⊕ (a GF(2) combination of
64/// the kernel basis)`, so the entire affine coset — all `2^{n−rank}` solutions — is generated from this
65/// compressed witness. The kernel is the **symmetry group** of the solution set (the translations that
66/// preserve `Ax`), `x₀` is one witness, and the basis are its generators: this is the exact, polynomial,
67/// linear analog of `hypercube::model_orbit`. The harder the break (the bigger the kernel), the more
68/// solutions; an *invertible* system has a trivial kernel — no symmetry, a unique witness.
69#[derive(Clone, Debug, PartialEq, Eq)]
70pub struct SolutionSpace {
71 pub num_vars: usize,
72 pub particular: Vec<bool>,
73 pub kernel_basis: Vec<Vec<bool>>,
74}
75
76impl SolutionSpace {
77 /// The number of solutions: `2^{dim kernel}` (rank–nullity) — the orbit size of the solution coset.
78 pub fn count(&self) -> u128 {
79 1u128 << self.kernel_basis.len()
80 }
81
82 /// Generate **every** solution by XORing the particular solution with each subset of the kernel basis
83 /// — the orbit of `x₀` under the kernel's translation symmetry.
84 pub fn enumerate(&self) -> Vec<Vec<bool>> {
85 let k = self.kernel_basis.len();
86 (0u64..(1u64 << k))
87 .map(|mask| {
88 let mut x = self.particular.clone();
89 for b in 0..k {
90 if (mask >> b) & 1 == 1 {
91 for v in 0..self.num_vars {
92 x[v] ^= self.kernel_basis[b][v];
93 }
94 }
95 }
96 x
97 })
98 .collect()
99 }
100}
101
102/// Solve a GF(2) system `A x = b` (each row a coefficient bit-vector in the low `n` bits, `rhs` the
103/// right-hand sides) for its **entire** solution space via Gaussian elimination to reduced row echelon
104/// form. Returns the symmetry-broken [`SolutionSpace`] (particular solution + kernel basis), or `None`
105/// iff the system is inconsistent. Generalizes [`crate::xorsat::solve`], which returns just one witness.
106pub fn solve_gf2(n: usize, rows: &[u64], rhs: &[bool]) -> Option<SolutionSpace> {
107 let coeff_mask = if n == 64 { u64::MAX } else { (1u64 << n) - 1 };
108 let mut aug: Vec<u64> = rows
109 .iter()
110 .zip(rhs)
111 .map(|(&c, &b)| (c & coeff_mask) | ((b as u64) << n))
112 .collect();
113 let mut pivot_col_of_row: Vec<usize> = Vec::new();
114 let mut rank = 0usize;
115 for col in 0..n {
116 if let Some(p) = (rank..aug.len()).find(|&r| (aug[r] >> col) & 1 == 1) {
117 aug.swap(rank, p);
118 for r in 0..aug.len() {
119 if r != rank && (aug[r] >> col) & 1 == 1 {
120 aug[r] ^= aug[rank];
121 }
122 }
123 pivot_col_of_row.push(col);
124 rank += 1;
125 }
126 }
127 // Inconsistent: a fully-reduced row with no coefficients but a 1 on the right (0 = 1).
128 for r in 0..aug.len() {
129 if aug[r] & coeff_mask == 0 && (aug[r] >> n) & 1 == 1 {
130 return None;
131 }
132 }
133 let mut is_pivot = vec![false; n];
134 for &c in &pivot_col_of_row {
135 is_pivot[c] = true;
136 }
137 // Particular solution: free variables 0, each pivot variable = its row's right-hand side.
138 let mut particular = vec![false; n];
139 for (r, &pc) in pivot_col_of_row.iter().enumerate() {
140 particular[pc] = (aug[r] >> n) & 1 == 1;
141 }
142 // Kernel basis: one vector per free column f — set x_f = 1, each pivot var = its row's f-coefficient.
143 let mut kernel_basis = Vec::new();
144 for f in 0..n {
145 if is_pivot[f] {
146 continue;
147 }
148 let mut kv = vec![false; n];
149 kv[f] = true;
150 for (r, &pc) in pivot_col_of_row.iter().enumerate() {
151 if (aug[r] >> f) & 1 == 1 {
152 kv[pc] = true;
153 }
154 }
155 kernel_basis.push(kv);
156 }
157 Some(SolutionSpace {
158 num_vars: n,
159 particular,
160 kernel_basis,
161 })
162}
163
164#[cfg(test)]
165#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/gf2/tests.rs"]
166mod tests;