Skip to main content

exactly_one_linear_generators

Function exactly_one_linear_generators 

Source
pub fn exactly_one_linear_generators(groups: &[Vec<u32>]) -> Vec<Poly> 
Expand description

The linear encoding of exactly-one constraints: for each group G the degree-1 generator 1 + Σ_{v∈G} x_v (the GF(2) form of Σ x = 1) plus the pairwise products x_u·x_v over each group, deduplicated. This is the encoding under which the modular-counting and pigeonhole degree lower bounds are stated in the literature — the wide at-least-one clause is recovered from it modulo the pairs (the interreduction test pins the identity, and the clause→linear direction is degree-preserving, so bounds against this encoding are the stronger statements). The linear generators come first (one per group, in group order), then the pairs.