boofun.analysis.gf2

GF(2) analysis for Boolean functions (XOR/Algebraic Normal Form).

This module provides analysis tools based on the polynomial representation of Boolean functions over the field GF(2) = {0, 1}.

Every Boolean function f: {0,1}^n -> {0,1} can be uniquely represented as:: f(x) = ⊕_{S ⊆ [n]} c_S * ∏_{i∈S} x_i

where c_S ∈ {0,1} are the GF(2) Fourier coefficients (ANF coefficients).

Key concepts: - GF(2) degree (algebraic degree): max |S| where c_S ≠ 0 - Real degree: max |S| where f̂(S) ≠ 0 (Walsh-Hadamard) - GF(2) Fourier coefficients: obtained via Möbius transform

Relationships (from O’Donnell Chapter 1): - GF(2) degree ≤ n for any function on n variables - Linear functions have GF(2) degree ≤ 1 - The XOR function x₁ ⊕ x₂ ⊕ … ⊕ xₙ has GF(2) degree 1 - Majority function has GF(2) degree n

Functions

`connected_variables`(f, var_set)	Check if all variables in var_set appear together in some monomial.
`correlation_with_parity`(f, subset)	Compute the correlation of f with the parity function on a subset.
`fourier_weight_by_degree`(f)	Compute the GF(2) Fourier weight at each degree level.
`gf2_degree`(f)	Compute the GF(2) degree (algebraic degree) of f.
`gf2_fourier_transform`(f)	Compute the GF(2) Fourier transform (Möbius transform) of f.
`gf2_monomials`(f)	Get all monomials with non-zero coefficients in the ANF of f.
`gf2_to_string`(f[, var_prefix])	Get a string representation of the ANF of f.
`is_linear_over_gf2`(f)	Check if f is linear over GF(2) (i.e., degree ≤ 1).
`variable_degree`(f, var)	Compute the degree of variable var in the ANF of f.

boofun.analysis.gf2.gf2_fourier_transform(f: BooleanFunction) → np.ndarray[source]

Compute the GF(2) Fourier transform (Möbius transform) of f.

The result is an array where result[S] = 1 if the monomial corresponding to subset S appears in the ANF of f, and 0 otherwise.

Parameters:: f – BooleanFunction to analyze
Returns:: numpy array of length 2^n where result[S] ∈ {0,1} is the coefficient of monomial S in the ANF representation.

Note

The index S encodes a subset: bit i is set iff variable i is in the monomial. E.g., S=3 (binary 11) represents the monomial x₀*x₁.

Example

>>> xor = bf.create([0, 1, 1, 0])
>>> coeffs = gf2_fourier_transform(xor)
>>> # coeffs[0]=0 (no constant), coeffs[1]=1 (x0), coeffs[2]=1 (x1), coeffs[3]=0 (no x0*x1)

boofun.analysis.gf2.gf2_degree(f: BooleanFunction) → int[source]

Compute the GF(2) degree (algebraic degree) of f.

The GF(2) degree is the size of the largest monomial in the ANF:: deg_2(f) = max{|S| : c_S ≠ 0}

This is different from the “real” Fourier degree which uses Walsh coefficients.

Parameters:: f – BooleanFunction to analyze
Returns:: The algebraic degree of f over GF(2)

Note

Constant functions have degree 0
Linear functions have degree ≤ 1
XOR(x₁,…,xₙ) has degree 1
AND(x₁,…,xₙ) has degree n
Majority_n has degree n

boofun.analysis.gf2.gf2_monomials(f: BooleanFunction) → List[Set[int]][source]

Get all monomials with non-zero coefficients in the ANF of f.

Parameters:: f – BooleanFunction to analyze
Returns:: List of sets, where each set contains the variable indices in a monomial. E.g., [{0}, {1}, {0,2}] represents x₀ ⊕ x₁ ⊕ x₀*x₂

boofun.analysis.gf2.gf2_to_string(f: BooleanFunction, var_prefix: str = 'x') → str[source]

Get a string representation of the ANF of f.

Parameters:

f – BooleanFunction to analyze
var_prefix – Prefix for variable names (default: “x”)

Returns:

String like “1 ⊕ x0 ⊕ x1 ⊕ x0*x1”

boofun.analysis.gf2.is_linear_over_gf2(f: BooleanFunction) → bool[source]

Check if f is linear over GF(2) (i.e., degree ≤ 1).

A function is linear over GF(2) if it can be written as:: f(x) = c ⊕ a₁x₁ ⊕ a₂x₂ ⊕ … ⊕ aₙxₙ

for some constants c, a₁, …, aₙ ∈ {0,1}.

Note: This is different from being linear over ℝ (which would require all variables to have the same influence and specific Fourier structure).

boofun.analysis.gf2.correlation_with_parity(f: BooleanFunction, subset: Set[int]) → float[source]

Compute the correlation of f with the parity function on a subset.

The correlation is:: corr(f, χ_S) = E[(-1)^(f(x) ⊕ ⊕_{i∈S} x_i)]

This equals the (normalized) Walsh-Hadamard coefficient f̂(S).

Parameters:

f – BooleanFunction to analyze
subset – Set of variable indices for the parity function

Returns:

Correlation in [-1, 1]