Skip to main content

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;