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

`annealed_influence`(f, i, rho)	Compute the annealed (noisy) influence of variable i.
`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 Fourier coefficients of the convolution of two Boolean functions.
`convolution_values`(f, g)	Compute the time-domain values of the convolution of two Boolean functions.
`correlation`(f, g)	Compute the correlation between 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_level_lp_norm`(f, k[, p])	Compute the L_p norm of Fourier coefficients at degree k.
`fourier_sparsity`(f[, threshold])	Count the number of non-zero Fourier coefficients.
`fourier_tail_profile`(f[, p])	Compute the Fourier tail profile: L_{p,k}(f) for all k.
`fourier_weight_distribution`(f)	Compute the distribution of Fourier weight by degree.
`min_fourier_coefficient_size`(f[, threshold])	Find the minimum subset size \|S\| with non-zero f̂(S).
`negate_inputs`(f)	Compute g(x) = f(-x) where -x flips all bits.
`normalized_influence`(f, i)	Compute the normalized influence of variable i.
`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₂).
`truncate_to_degree`(f, d)	Truncate the Fourier expansion of f to degree at most d.

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) → np.ndarray[source]

Compute the Fourier coefficients of the convolution of two Boolean functions.

The convolution is defined as:: (f * g)(x) = E_y[f(y)g(x ⊕ y)]

By the Convolution Theorem, in the Fourier domain this becomes pointwise multiplication:

(f * g)^(S) = f̂(S) · ĝ(S)

Parameters:

f – BooleanFunctions to convolve
g – BooleanFunctions to convolve

Returns:

numpy array of Fourier coefficients (f * g)^(S) indexed by S

Raises:

ValueError – If f and g have different number of variables

Note

The convolution of two Boolean functions is generally NOT a Boolean function - it’s a real-valued function with values in [-1, 1]. This function returns the exact Fourier coefficients without any loss of information.

Example

>>> f = bf.majority(3)
>>> g = bf.parity(3)
>>> conv_coeffs = convolution(f, g)
>>> # Verify: (f*g)^(S) = f̂(S) · ĝ(S)
>>> assert np.allclose(conv_coeffs, f.fourier() * g.fourier())

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

Compute the time-domain values of the convolution of two Boolean functions.

The convolution is defined as:: (f * g)(x) = E_y[f(y)g(x ⊕ y)]

This function computes (f * g)(x) for all x via inverse Fourier transform.

Parameters:

f – BooleanFunctions to convolve
g – BooleanFunctions to convolve

Returns:

numpy array of real values (f * g)(x) indexed by x

Note

The values are in [-1, 1], NOT {0, 1} or {-1, 1}. This is the correlation between f and g shifted by x.

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.correlation(f: BooleanFunction, g: BooleanFunction) → float[source]

Compute the correlation between two Boolean functions.

The correlation is defined as:: Corr(f, g) = E[f(x)g(x)] = ⟨f, g⟩

where the expectation is over the uniform distribution on {-1,+1}^n.

For ±1-valued functions, Corr(f,f) = 1, and Corr(f,g) ∈ [-1,1].

This is mathematically equivalent to plancherel_inner_product but provided as a more intuitive interface from Tal’s library.

Parameters:

f – First BooleanFunction
g – Second BooleanFunction

Returns:

Correlation ⟨f, g⟩ in [-1, 1]

Raises:

ValueError – If f and g have different number of variables

References

Tal’s BooleanFunc.py: correlation
O’Donnell Definition 1.6

boofun.analysis.fourier.truncate_to_degree(f: BooleanFunction, d: int) → np.ndarray[source]

Truncate the Fourier expansion of f to degree at most d.

Returns the function:: f^{≤d}(x) = Σ_{|S| ≤ d} f̂(S) χ_S(x)

This is useful for approximating functions by their low-degree parts. The truncated function is generally not Boolean-valued.

Parameters:

f – BooleanFunction to truncate
d – Maximum degree to keep

Returns:

Array of function values for f^{≤d} (real-valued, not necessarily Boolean)

References

Tal’s BooleanFunc.py: truncated_degree_d
O’Donnell Definition 1.14 (degree-d part)

boofun.analysis.fourier.annealed_influence(f: BooleanFunction, i: int, rho: float) → float[source]

Compute the annealed (noisy) influence of variable i.

The annealed influence at correlation ρ is:: Inf_i^{(ρ)}[f] = Σ_{S∋i} ρ^{|S|-1} f̂(S)²

This interpolates between: - ρ = 1: Standard influence Inf_i[f] = Σ_{S∋i} f̂(S)² - ρ → 0: Only degree-1 contributions

The annealed influence measures how sensitive f is to variable i after noise has been applied.

Parameters:

f – BooleanFunction to analyze
i – Variable index (0-indexed)
rho – Noise correlation parameter in (0, 1]

Returns:

Annealed influence of variable i

References

Tal’s BooleanFunc.py: ann_influence
O’Donnell Chapter 2 (noise sensitivity)

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

Compute the distribution of Fourier weight by degree.

Returns W^k[f] = Σ_{|S|=k} f̂(S)² for each k.

By Parseval’s identity: Σ_k W^k[f] = 1 for ±1-valued functions.

This is useful for understanding the “spectral profile” of a function: - Low-degree weight → function is “simple” - High-degree weight → function is “complex”

Parameters:: f – BooleanFunction to analyze
Returns:: Dictionary mapping degree k to W^k[f]

References

Tal’s BooleanFunc.py: fourier_weights
O’Donnell Definition 1.14 (spectral sample)

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

Find the minimum subset size |S| with non-zero f̂(S).

Returns min { |S| : f̂(S) ≠ 0 }.

This is 0 if f has non-zero bias (f̂(∅) ≠ 0), otherwise it’s the minimum degree of a non-zero Fourier coefficient.

Parameters:

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

Returns:

Minimum subset size with non-zero coefficient

References

Tal’s BooleanFunc.py: min_size_fourier_coef

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