boofun.analysis.fourier

Fourier analysis utilities for Boolean functions.

This module provides core Fourier analysis tools as described in Chapter 1 of O’Donnell’s “Analysis of Boolean Functions”, including:

Parseval’s identity: ‖f‖² = Σ_S f̂(S)²
Plancherel’s theorem: ⟨f,g⟩ = Σ_S f̂(S)ĝ(S)
Convolution: (f * g)(x) = E_y[f(y)g(x⊕y)]
Function transformations (negation, odd/even parts)
Restriction operators

Mathematical Background (O’Donnell Chapter 1):

Every function f: {-1,1}^n → ℝ has a unique Fourier expansion:: f(x) = Σ_{S⊆[n]} f̂(S) χ_S(x)

where χ_S(x) = ∏_{i∈S} x_i are the Fourier characters.

Key identities: - Parseval: E[f(x)²] = Σ_S f̂(S)² (L2 norm preservation) - Plancherel: E[f(x)g(x)] = Σ_S f̂(S)ĝ(S) (inner product) - Convolution: (f*g)^(S) = f̂(S) · ĝ(S) (pointwise in Fourier domain)

Functions

`compute_and_fourier`(n)	Compute Fourier expansion of AND_n: {-1,1}^n → {-1,1}.
`compute_mux3_fourier`()	Compute Fourier expansion of MUX₃: {-1,1}³ → {-1,1}.
`compute_nae3_fourier`()	Compute Fourier expansion of NAE₃: {-1,1}³ → {0,1}.
`convolution`(f, g)	Compute the convolution of two Boolean functions.
`dominant_coefficients`(f[, top_k, threshold])	Find the dominant (largest magnitude) Fourier coefficients.
`even_part`(f)	Compute the even part of f: f^even(x) = (f(x) + f(-x)) / 2.
`fourier_degree`(f)	Compute the Fourier degree (real degree) of f.
`fourier_sparsity`(f[, threshold])	Count the number of non-zero Fourier coefficients.
`negate_inputs`(f)	Compute g(x) = f(-x) where -x flips all bits.
`odd_part`(f)	Compute the odd part of f: f^odd(x) = (f(x) - f(-x)) / 2.
`parseval_verify`(f[, tolerance])	Verify Parseval's identity for a Boolean function.
`plancherel_inner_product`(f, g)	Compute inner product using Plancherel's theorem.
`restriction`(f, fixed_vars)	Compute restriction of f by fixing some variables.
`spectral_norm`(f[, p])	Compute the L_p spectral norm of f.
`tensor_product`(f, g)	Compute tensor product: h(x₁, x₂) = f(x₁) · g(x₂).

boofun.analysis.fourier.parseval_verify(f: BooleanFunction, tolerance: float = 1e-10) → Tuple[bool, float, float][source]

Verify Parseval’s identity for a Boolean function.

Parseval’s identity states that for f: {-1,1}^n → ℝ:: E[f(x)²] = Σ_S f̂(S)²
For Boolean functions f: {-1,1}^n → {-1,1}, this gives:: 1 = Σ_S f̂(S)² (since f(x)² = 1 always)

Parameters:

f – BooleanFunction to verify
tolerance – Maximum allowed deviation from expected value

Returns:

passes: True if |lhs - rhs| < tolerance
lhs_value: E[f(x)²] computed directly
rhs_value: Σ_S f̂(S)² from Fourier coefficients

Return type:

Tuple of (passes, lhs_value, rhs_value) where

Example

>>> xor = bf.create([0, 1, 1, 0])
>>> passes, lhs, rhs = parseval_verify(xor)
>>> passes  # Should be True
True

boofun.analysis.fourier.plancherel_inner_product(f: BooleanFunction, g: BooleanFunction) → float[source]

Compute inner product using Plancherel’s theorem.

Plancherel’s theorem (generalization of Parseval):: ⟨f, g⟩ = E[f(x)g(x)] = Σ_S f̂(S)ĝ(S)

Parameters:

f – BooleanFunctions to compute inner product of
g – BooleanFunctions to compute inner product of

Returns:

Inner product ⟨f, g⟩

Raises:

ValueError – If f and g have different number of variables

boofun.analysis.fourier.convolution(f: BooleanFunction, g: BooleanFunction) → BooleanFunction[source]

Compute the convolution of two Boolean functions.

The convolution is defined as:: (f * g)(x) = E_y[f(y)g(x ⊕ y)]
In the Fourier domain, convolution becomes pointwise multiplication:: (f * g)^(S) = f̂(S) · ĝ(S)

Parameters:

f – BooleanFunctions to convolve
g – BooleanFunctions to convolve

Returns:

New BooleanFunction representing f * g

Raises:

ValueError – If f and g have different number of variables

Note

The result is a real-valued function, represented by its truth table of real values. For Boolean functions, this represents the correlation.

boofun.analysis.fourier.negate_inputs(f: BooleanFunction) → BooleanFunction[source]

Compute g(x) = f(-x) where -x flips all bits.

From HW1 Problem 1: If f(x) = Σ_S f̂(S) χ_S(x), then: g(x) = f(-x) = Σ_S (-1)^|S| f̂(S) χ_S(x)

This flips the sign of odd-degree Fourier coefficients.

Parameters:: f – BooleanFunction to transform
Returns:: New BooleanFunction g where g(x) = f(-x)

boofun.analysis.fourier.odd_part(f: BooleanFunction) → np.ndarray[source]

Compute the odd part of f: f^odd(x) = (f(x) - f(-x)) / 2.

From HW1 Problem 1: The odd part contains only odd-degree Fourier coefficients.: f^odd(x) = Σ_{|S| odd} f̂(S) χ_S(x)

Parameters:: f – BooleanFunction to analyze
Returns:: Array of function values for f^odd (real-valued, not Boolean)

Note

The result is real-valued, not necessarily Boolean.

boofun.analysis.fourier.even_part(f: BooleanFunction) → np.ndarray[source]

Compute the even part of f: f^even(x) = (f(x) + f(-x)) / 2.

From HW1 Problem 1: The even part contains only even-degree Fourier coefficients.: f^even(x) = Σ_{|S| even} f̂(S) χ_S(x)

Parameters:: f – BooleanFunction to analyze
Returns:: Array of function values for f^even (real-valued)

boofun.analysis.fourier.tensor_product(f: BooleanFunction, g: BooleanFunction) → BooleanFunction[source]

Compute tensor product: h(x₁, x₂) = f(x₁) · g(x₂).

From HW1 Problem 1: If f: {-1,1}^n → ℝ and g: {-1,1}^m → ℝ, then: h: {-1,1}^{n+m} → ℝ with h(x₁, x₂) = f(x₁) · g(x₂)
has Fourier expansion:: ĥ(S₁ ∪ S₂) = f̂(S₁) · ĝ(S₂)

where S₁ ⊆ [n] and S₂ ⊆ [m] (shifted to [n+1, n+m]).

Parameters:

f – First BooleanFunction on n variables
g – Second BooleanFunction on m variables

Returns:

Tensor product on n+m variables

boofun.analysis.fourier.restriction(f: BooleanFunction, fixed_vars: Dict[int, int]) → BooleanFunction[source]

Compute restriction of f by fixing some variables.

From HW1 Problem 1: If we fix the last (n-k) variables to -1:: g(x₁,…,x_k) = f(x₁,…,x_k, -1, -1, …, -1)
The Fourier coefficients satisfy:: ĝ(T) = Σ_{S⊇T, S⊆[k]} f̂(S ∪ {fixed vars where fixed = -1})

Parameters:

f – BooleanFunction to restrict
fixed_vars – Dictionary mapping variable indices to fixed values (0 or 1)

Returns:

Restricted BooleanFunction on remaining variables

Example

>>> f = bf.create([0, 1, 1, 0])  # XOR
>>> g = restriction(f, {0: 1})   # Fix x0 = 1
>>> # g is now NOT(x1) on 1 variable

boofun.analysis.fourier.fourier_degree(f: BooleanFunction) → int[source]

Compute the Fourier degree (real degree) of f.

The Fourier degree is the maximum |S| such that f̂(S) ≠ 0.

Parameters:: f – BooleanFunction to analyze
Returns:: Maximum degree of non-zero Fourier coefficient

Note

This is different from the GF(2) degree (algebraic degree). For f(x) = x₁x₂ (AND), both degrees are 2. For f(x) = x₁ ⊕ x₂ (XOR), real degree is 2 but GF(2) degree is 1.

boofun.analysis.fourier.spectral_norm(f: BooleanFunction, p: int = 2) → float[source]

Compute the L_p spectral norm of f.

Parameters:

f – BooleanFunction to analyze
p – Norm parameter (1, 2, or inf)

Returns:

‖f̂‖_p = (Σ_S |f̂(S)|^p)^{1/p}

boofun.analysis.fourier.fourier_sparsity(f: BooleanFunction, threshold: float = 1e-10) → int[source]

Count the number of non-zero Fourier coefficients.

From HW1 Problem 7: Functions of degree k have at most 4^k non-zero Fourier coefficients.

Parameters:

f – BooleanFunction to analyze
threshold – Minimum absolute value to count as non-zero

Returns:

Number of Fourier coefficients with |f̂(S)| > threshold

boofun.analysis.fourier.dominant_coefficients(f: BooleanFunction, top_k: int = 10, threshold: float = 0.01) → List[Tuple[int, float]][source]

Find the dominant (largest magnitude) Fourier coefficients.

Parameters:

f – BooleanFunction to analyze
top_k – Maximum number of coefficients to return
threshold – Minimum magnitude to include

Returns:

List of (subset_mask, coefficient) pairs, sorted by magnitude

boofun.analysis.fourier.compute_mux3_fourier() → Dict[int, float][source]

Compute Fourier expansion of MUX₃: {-1,1}³ → {-1,1}.

From HW1 Problem 2a: MUX₃(x₁, x₂, x₃) outputs x₂ if x₁ = 1, and x₃ if x₁ = -1.

Returns:: Dictionary mapping subset masks to Fourier coefficients

Mathematical derivation:

MUX₃(x) = (1+x₁)/2 · x₂ + (1-x₁)/2 · x₃: = x₂/2 + x₁x₂/2 + x₃/2 - x₁x₃/2

So: f̂({2}) = 1/2, f̂({1,2}) = 1/2, f̂({3}) = 1/2, f̂({1,3}) = -1/2

boofun.analysis.fourier.compute_nae3_fourier() → Dict[int, float][source]

Compute Fourier expansion of NAE₃: {-1,1}³ → {0,1}.

From HW1 Problem 2b: NAE₃(x₁, x₂, x₃) = 1 iff not all bits are equal.

Returns:: Dictionary mapping subset masks to Fourier coefficients

boofun.analysis.fourier.compute_and_fourier(n: int) → Dict[int, float][source]

Compute Fourier expansion of AND_n: {-1,1}^n → {-1,1}.

From HW1 Problem 2c: AND_n(x) = 1 iff all x_i = 1.

The Fourier expansion is:: AND_n(x) = (1/2^n) Σ_{S⊆[n]} (-1)^{n-|S|} ∏_{i∈S} x_i

So f̂(S) = (-1)^{n-|S|} / 2^n for all S.

Returns:: Dictionary mapping subset masks to Fourier coefficients