CS 294-92: Analysis of Boolean Functions - Homework 1¶
Fourier Expansion and Properties¶
This notebook accompanies Problem Set 1, exploring the Fourier expansion of Boolean functions.
Instructor: Avishay Tal
Reference: O'Donnell, Analysis of Boolean Functions, Chapters 1-2
Notebook by: Gabriel Taboada
In [1]:
# Install/upgrade boofun (required for Colab)
# This ensures you have the latest version with all features
!pip install --upgrade boofun -q
import boofun as bf
print(f"BooFun version: {bf.__version__}")
[notice] A new release of pip is available: 25.2 -> 26.0 [notice] To update, run: /Library/Developer/CommandLineTools/usr/bin/python3 -m pip install --upgrade pip
/Users/gabrieltaboada/dev/Boofun/boofun/src/boofun/core/errormodels.py:21: UserWarning: uncertainties library not available - some error models disabled
warnings.warn("uncertainties library not available - some error models disabled")
/Users/gabrieltaboada/dev/Boofun/boofun/src/boofun/quantum/__init__.py:22: UserWarning: Qiskit not available - quantum features limited
warnings.warn("Qiskit not available - quantum features limited")
BooFun version: 1.1.1
In [2]:
# Setup
import numpy as np
import matplotlib.pyplot as plt
import sys
sys.path.insert(0, '../src')
import boofun as bf
from boofun.analysis import fourier
# Suppress warnings for cleaner output
import warnings
warnings.filterwarnings('ignore')
print("boofun loaded successfully")
print()
print("Quick API demo:")
print(f" bf.parity(3).degree() = {bf.parity(3).degree()}")
print(f" bf.majority(3).influences() = {bf.majority(3).influences()}")
boofun loaded successfully Quick API demo: bf.parity(3).degree() = 3 bf.majority(3).influences() = [0.5 0.5 0.5]
Background: The Fourier Expansion¶
Every function $f: \{-1, 1\}^n \to \mathbb{R}$ has a unique Fourier expansion:
$$f(x) = \sum_{S \subseteq [n]} \hat{f}(S) \prod_{i \in S} x_i$$
where $\chi_S(x) = \prod_{i \in S} x_i$ are the Fourier characters (Walsh functions).
The Fourier coefficients are: $$\hat{f}(S) = \mathbf{E}_{x \sim \{\pm 1\}^n}[f(x) \chi_S(x)]$$
Key properties:
- Parseval's Identity: $\mathbf{E}[f(x)^2] = \sum_S \hat{f}(S)^2$
- For Boolean functions $f: \{-1,1\}^n \to \{-1,1\}$: $\sum_S \hat{f}(S)^2 = 1$
In [3]:
# Let's explore g(x) = f(-x) using the Majority function
maj3 = bf.majority(3) # Clean API: bf.majority() instead of bf.BooleanFunctionBuiltins.majority()
print("Original function: Majority-3")
print(f"Truth table: {list(maj3.get_representation('truth_table'))}")
# Compute Fourier coefficients directly on the function
coeffs = maj3.fourier() # Clean: f.fourier() instead of SpectralAnalyzer(f).fourier_expansion()
print("\nFourier coefficients of f:")
for s in range(len(coeffs)):
if abs(coeffs[s]) > 1e-10:
subset = [i for i in range(3) if (s >> (2-i)) & 1]
print(f" f̂({subset}): {coeffs[s]:.4f}")
# Now compute g(x) = f(-x) using unary minus!
g = -maj3 # Clean: -f instead of fourier.negate_inputs(f)
coeffs_g = g.fourier()
print("\nFourier coefficients of g(x) = f(-x):")
for s in range(len(coeffs_g)):
if abs(coeffs_g[s]) > 1e-10:
subset = [i for i in range(3) if (s >> (2-i)) & 1]
print(f" ĝ({subset}): {coeffs_g[s]:.4f}")
print("\nObservation: ĝ(S) = (-1)^|S| · f̂(S) (odd-degree coefficients flip sign)")
Original function: Majority-3 Truth table: [False, False, False, True, False, True, True, True] Fourier coefficients of f: f̂([2]): 0.5000 f̂([1]): 0.5000 f̂([0]): 0.5000 f̂([0, 1, 2]): -0.5000 Fourier coefficients of g(x) = f(-x): ĝ([2]): -0.5000 ĝ([1]): -0.5000 ĝ([0]): -0.5000 ĝ([0, 1, 2]): 0.5000 Observation: ĝ(S) = (-1)^|S| · f̂(S) (odd-degree coefficients flip sign)
Parts (b) & (c): $f^{odd}$ and $f^{even}$¶
The homework defines:
- $f^{odd}(x) = \frac{f(x) - f(-x)}{2}$ → contains only odd-degree Fourier coefficients
- $f^{even}(x) = \frac{f(x) + f(-x)}{2}$ → contains only even-degree Fourier coefficients
The library provides these directly via bf.odd_part(f) and bf.even_part(f).
Problem 2: Computing Fourier Expansions¶
The homework asks you to derive these expansions by hand. Here we show how to verify your answers using the library.
Part (a): MUX₃ (Multiplexer on 3 bits)¶
$\text{MUX}_3(x_1, x_2, x_3)$ outputs $x_2$ if $x_1 = 1$, and $x_3$ if $x_1 = -1$.
Hint: Write MUX₃ as a polynomial: $\frac{1+x_1}{2} \cdot x_2 + \frac{1-x_1}{2} \cdot x_3$
In [4]:
# MUX₃: output x₂ if x₁=+1 (i.e., x₁=0 in {0,1}), else x₃
# Create it from truth table - you derive the Fourier expansion by hand!
mux3_tt = [0, 0, 1, 1, 0, 1, 0, 1] # In {0,1} notation
mux3 = bf.create(mux3_tt)
print("MUX₃ Truth Table (verify your understanding):")
print("x₁ x₂ x₃ | MUX₃")
print("-" * 15)
for x in range(8):
x1, x2, x3 = (x >> 2) & 1, (x >> 1) & 1, x & 1
print(f" {x1} {x2} {x3} | {mux3_tt[x]}")
# ========================================================================
# VERIFICATION: Use the library to CHECK your hand-computed answer
# Derive the expansion yourself first, then verify these properties match!
# ========================================================================
print("\nVerify your hand-computed answer:")
print(f" Fourier degree: {mux3.degree()}")
print(f" Number of nonzero coefficients: {sum(1 for c in mux3.fourier() if abs(c) > 1e-10)}")
print(f" Sum of squared coefficients: {sum(c**2 for c in mux3.fourier()):.4f} (should be 1)")
print(f" f̂(∅) (constant term): {mux3.fourier()[0]:.4f}")
print(f" Weight at degree 2: W^{{=2}}[f] = {mux3.W(2):.4f}")
print("\nDerivation hint:")
print(" MUX₃(x) = (1+x₁)/2 · x₂ + (1-x₁)/2 · x₃")
print(" Expand and collect terms to find the 4 nonzero coefficients!")
MUX₃ Truth Table (verify your understanding):
x₁ x₂ x₃ | MUX₃
---------------
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1
Verify your hand-computed answer:
Fourier degree: 2
Number of nonzero coefficients: 4
Sum of squared coefficients: 1.0000 (should be 1)
f̂(∅) (constant term): 0.0000
Weight at degree 2: W^{=2}[f] = 0.5000
Derivation hint:
MUX₃(x) = (1+x₁)/2 · x₂ + (1-x₁)/2 · x₃
Expand and collect terms to find the 4 nonzero coefficients!
Part (b): NAE₃ (Not-All-Equal)¶
$\text{NAE}_3(x_1, x_2, x_3) = 1$ iff $x_1, x_2, x_3$ are not all equal.
In [5]:
# NAE₃: output 1 if not all bits are equal (note: outputs to {0,1}!)
nae3_tt = [0, 1, 1, 1, 1, 1, 1, 0]
nae3 = bf.create(nae3_tt)
print("NAE₃ Truth Table:")
print("x₁ x₂ x₃ | NAE₃")
print("-" * 15)
for x in range(8):
x1, x2, x3 = (x >> 2) & 1, (x >> 1) & 1, x & 1
print(f" {x1} {x2} {x3} | {nae3_tt[x]}")
# ========================================================================
# VERIFICATION: Derive the expansion yourself, then check these properties!
# Note: NAE₃ maps to {0,1} so we work in that domain
# ========================================================================
print("\nVerify your hand-computed answer:")
print(f" Fourier degree: {nae3.degree()}")
print(f" f̂(∅) (constant term): {nae3.fourier()[0]:.4f}")
print(f" Is balanced? {nae3.is_balanced()}")
print(f" Number of nonzero coefficients: {sum(1 for c in nae3.fourier() if abs(c) > 1e-10)}")
print(f" Weight at degree 2: W^{{=2}}[f] = {nae3.W(2):.4f}")
print("\nDerivation approach:")
print(" Method 1: NAE₃ = 1 - (all_0 OR all_1)")
print(" Method 2: NAE₃(x) = 1 iff x₁⊕x₂ = 1 OR x₂⊕x₃ = 1")
print(" Convert to ±1 domain and expand!")
NAE₃ Truth Table:
x₁ x₂ x₃ | NAE₃
---------------
0 0 0 | 0
0 0 1 | 1
0 1 0 | 1
0 1 1 | 1
1 0 0 | 1
1 0 1 | 1
1 1 0 | 1
1 1 1 | 0
Verify your hand-computed answer:
Fourier degree: 2
f̂(∅) (constant term): -0.5000
Is balanced? False
Number of nonzero coefficients: 4
Weight at degree 2: W^{=2}[f] = 0.7500
Derivation approach:
Method 1: NAE₃ = 1 - (all_0 OR all_1)
Method 2: NAE₃(x) = 1 iff x₁⊕x₂ = 1 OR x₂⊕x₃ = 1
Convert to ±1 domain and expand!
Part (c): AND_n¶
$\text{AND}_n(x) = 1$ iff all $x_i = 1$.
For $\text{AND}_n$ in $\{\pm 1\}$ notation, the Fourier coefficient is: $$\hat{f}(S) = \frac{(-1)^{n-|S|}}{2^n}$$
In [6]:
# ========================================================================
# AND_n: Verify the formula you derive by hand
# The HW claims: f̂(S) = (-1)^{n-|S|} / 2^n for all S ⊆ [n]
# ========================================================================
print("AND_n Properties (derive the formula, then verify!):")
print("=" * 60)
print(f"{'n':>3} {'degree':>8} {'# coeffs':>10} {'|f̂(S)|':>12} {'Parseval':>10}")
print("-" * 60)
for n in [2, 3, 4, 5]:
f = bf.AND(n) # Clean API: bf.AND(n)
coeffs = f.fourier()
# Properties to verify against your derivation
deg = f.degree()
num_nonzero = sum(1 for c in coeffs if abs(c) > 1e-10)
expected_mag = 1.0 / (2**n) # All |f̂(S)| should equal this
parseval = sum(c**2 for c in coeffs)
print(f"{n:>3} {deg:>8} {num_nonzero:>10} {expected_mag:>12.6f} {parseval:>10.4f}")
print("\nDerivation hint:")
print(" Write AND_n in ±1 domain: AND_n(x) = 1 iff all x_i = 1")
print(" AND_n(x) = ∏ᵢ (1+xᵢ)/2 in {0,1} output, or...")
print(" Express as product and expand!")
print("\nKey insight: ALL 2^n coefficients are nonzero with same magnitude!")
AND_n Properties (derive the formula, then verify!):
============================================================
n degree # coeffs |f̂(S)| Parseval
------------------------------------------------------------
2 2 4 0.250000 1.0000
3 3 8 0.125000 1.0000
4 4 16 0.062500 1.0000
5 5 32 0.031250 1.0000
Derivation hint:
Write AND_n in ±1 domain: AND_n(x) = 1 iff all x_i = 1
AND_n(x) = ∏ᵢ (1+xᵢ)/2 in {0,1} output, or...
Express as product and expand!
Key insight: ALL 2^n coefficients are nonzero with same magnitude!
Problem 3: Parseval's Identity¶
Statement: For any $f: \{-1,1\}^n \to \mathbb{R}$: $$\mathbf{E}[f(x)^2] = \sum_{S \subseteq [n]} \hat{f}(S)^2$$
For Boolean functions $f: \{-1,1\}^n \to \{-1,1\}$, both sides equal 1.
In [7]:
# Verify Parseval's identity for various functions
# Using the clean API: bf.majority(), bf.parity(), etc.
test_functions = [
("XOR", bf.create([0, 1, 1, 0])),
("AND", bf.AND(2)),
("OR", bf.OR(2)),
("Majority-3", bf.majority(3)),
("Parity-3", bf.parity(3)),
]
print("Parseval's Identity Verification")
print("=" * 60)
print(f"{'Function':<15} {'Σf̂(S)²':>15} {'degree':>10} {'balanced':>10}")
print("-" * 60)
for name, f in test_functions:
sum_sq = sum(c**2 for c in f.fourier()) # Parseval: should equal 1
# Parseval check: should equal 1 for Boolean functions
print(f"{name:<15} {sum_sq:>15.6f} {f.degree():>10} {'yes' if f.is_balanced() else 'no':>10}")
print("\nFor Boolean functions f: {-1,1}^n → {-1,1}, Parseval says Σf̂(S)² = 1")
Parseval's Identity Verification
============================================================
Function Σf̂(S)² degree balanced
------------------------------------------------------------
XOR 1.000000 2 yes
AND 1.000000 2 no
OR 1.000000 2 no
Majority-3 1.000000 3 yes
Parity-3 1.000000 3 yes
For Boolean functions f: {-1,1}^n → {-1,1}, Parseval says Σf̂(S)² = 1
Problem 4: Affine Function Testing¶
Definition: $f: \mathbb{F}_2^n \to \mathbb{F}_2$ is affine iff $f(x) = b + a_1 x_1 + \cdots + a_n x_n$ for some $a \in \mathbb{F}_2^n, b \in \mathbb{F}_2$.
Characterization: $f$ is affine iff $f(x) + f(y) + f(z) = f(x + y + z)$ for all $x, y, z$.
In [8]:
# Test affine property on various functions using clean API
test_functions = [
("XOR (affine)", bf.create([0, 1, 1, 0])),
("x₁ (affine)", bf.dictator(2, 0)),
("AND (not affine)", bf.AND(2)),
("Majority-3", bf.majority(3)),
("Parity-3 (affine)", bf.parity(3)),
]
print("Affine Function Test")
print("=" * 60)
for name, f in test_functions:
# Clean API: f.is_linear() and f.degree(gf2=True)
is_affine = f.is_linear()
gf2_deg = f.degree(gf2=True) # GF(2) degree
fourier_deg = f.degree() # Fourier degree
result = "affine" if is_affine else "not affine"
print(f"{name:<20}: {result}, deg_GF2={gf2_deg}, deg_Fourier={fourier_deg}")
print("\nAffine functions have GF(2) degree ≤ 1")
print("Note: XOR has GF(2) degree 1 but Fourier degree 2!")
Affine Function Test ============================================================ XOR (affine) : affine, deg_GF2=1, deg_Fourier=2 x₁ (affine) : affine, deg_GF2=1, deg_Fourier=1 AND (not affine) : not affine, deg_GF2=2, deg_Fourier=2 Majority-3 : not affine, deg_GF2=2, deg_Fourier=3 Parity-3 (affine) : affine, deg_GF2=1, deg_Fourier=3 Affine functions have GF(2) degree ≤ 1 Note: XOR has GF(2) degree 1 but Fourier degree 2!
Problem 6: Degree-1 Functions¶
Claim: If $f: \{\pm 1\}^n \to \{\pm 1\}$ has Fourier degree at most 1, then $f$ is:
- A constant (f̂(∅) = ±1, all others 0), or
- A dictator (f(x) = x_i for some i), or
- An anti-dictator (f(x) = -x_i for some i)
In [9]:
# ========================================================================
# HW Problem 6: Degree-1 Function Characterization
# PROVE: If f:{±1}ⁿ→{±1} has deg(f)≤1, then f is constant/dictator/anti-dictator
# This cell helps you VERIFY the claim empirically - you still need to prove it!
# ========================================================================
def classify_degree1(f):
"""Classify a degree-1 Boolean function as constant/dictator/anti-dictator."""
deg = f.degree()
if deg == 0:
return "Constant"
if deg > 1:
return f"Higher degree ({deg})"
# Degree 1: must be dictator or anti-dictator (by Problem 6!)
# Find which single variable has the ±1 coefficient
coeffs = f.fourier()
n = f.n_vars
for i in range(n):
# Coefficient index for variable x_i (MSB ordering)
idx = 1 << (n - 1 - i)
coeff = coeffs[idx]
if abs(coeff - 1.0) < 1e-10:
return f"Dictator x_{i}"
if abs(coeff + 1.0) < 1e-10:
return f"Anti-dictator -x_{i}"
return "Degree-1 (unexpected)"
# Test the characterization
functions = [
("Constant 0", bf.constant(False, 3)),
("Constant 1", bf.constant(True, 3)),
("Dictator x₀", bf.dictator(3, 0)),
("Dictator x₂", bf.dictator(3, 2)),
("XOR", bf.parity(3)),
("AND", bf.AND(3)),
("Majority", bf.majority(3)),
]
print("Degree-1 Function Classification (HW Problem 6)")
print("=" * 60)
print("Claim: deg(f)≤1 ⟹ f is constant, dictator, or anti-dictator")
print("-" * 60)
for name, f in functions:
deg = f.degree()
W1 = f.W(1) # Weight at degree 1
classification = classify_degree1(f)
print(f"{name:<12}: degree={deg}, W^{{=1}}={W1:.4f} → {classification}")
print("\nProof approach (hint):")
print(" 1. If deg(f)≤1: f(x) = f̂(∅) + Σᵢ f̂({i})xᵢ")
print(" 2. Apply Parseval: Σₛ f̂(S)² = 1")
print(" 3. Use f:{±1}ⁿ→{±1} constraint...")
print(" 4. What does this force the coefficients to be?")
Degree-1 Function Classification (HW Problem 6)
============================================================
Claim: deg(f)≤1 ⟹ f is constant, dictator, or anti-dictator
------------------------------------------------------------
Constant 0 : degree=0, W^{=1}=0.0000 → Constant
Constant 1 : degree=0, W^{=1}=0.0000 → Constant
Dictator x₀ : degree=1, W^{=1}=1.0000 → Dictator x_2
Dictator x₂ : degree=1, W^{=1}=1.0000 → Dictator x_0
XOR : degree=3, W^{=1}=0.0000 → Higher degree (3)
AND : degree=3, W^{=1}=0.1875 → Higher degree (3)
Majority : degree=3, W^{=1}=0.7500 → Higher degree (3)
Proof approach (hint):
1. If deg(f)≤1: f(x) = f̂(∅) + Σᵢ f̂({i})xᵢ
2. Apply Parseval: Σₛ f̂(S)² = 1
3. Use f:{±1}ⁿ→{±1} constraint...
4. What does this force the coefficients to be?
Summary¶
In this notebook, we explored the problems from HW1:
- Problem 1 - Fourier Transformations: How $f(-x)$, $f^{odd}$, $f^{even}$ relate to Fourier coefficients
- Problem 2 - Computing Expansions: MUX₃, NAE₃, AND_n examples
- Problem 3 - Parseval's Identity: $\mathbf{E}[f^2] = \sum_S \hat{f}(S)^2$
- Problem 4 - Affine Testing: 4-query test based on $f(x) + f(y) + f(z) = f(x+y+z)$
- Problem 6 - Degree-1 Functions: Always constant/dictator/anti-dictator
Key Takeaways¶
- The Fourier expansion represents Boolean functions as multilinear polynomials
- Parseval's identity connects function values to Fourier coefficients
- GF(2) degree (algebraic) and Fourier degree can differ!
- The
boofunlibrary provides tools for all these computations
Next Steps¶
- Try implementing the remaining problems from HW1
- Explore the spectral concentration of decision trees (Lecture 6)
- Investigate the connection to learning theory (LMN Theorem)