Skip to main content

symplectic_transvection_generators

Function symplectic_transvection_generators 

Source
pub fn symplectic_transvection_generators(
    num_vars: usize,
    clauses: &[Vec<Lit>],
    max_weight: usize,
) -> Vec<u64>
Expand description

The symplectic-transvection symmetry finder — one rung above affine shears. An affine shear is a rank-1 map whose right factor is a unit vector (v = e_j); dropping that restriction to a general v gives the full rank-1 group, whose bijective involutions are the symplectic transvections T_w = I ⊕ w wᵀ (even weight w). Where the affine dichotomy of §4 found permutation-symmetric families (PHP, mod-counting) to be affine-shear-rigid, this finder can still see their higher symmetry: it enumerates every even-weight w with 2 ≤ |w| ≤ max_weight and returns those whose T_w permutes the clause set (verified via [rank1_image_clause]). Cost O(Σ_{k≤W even} C(n,k) · |clauses|) — polynomial for fixed weight. Sound (every returned w is a checked automorphism); complete only up to the chosen weight. The weight of the smallest such symmetry is the graded invariant we track against NS degree.