T1: Mathematical Foundation of Boolean Function Analysis

April 18, 2025

• Definitions.
  • Rademacher Function
• Walsh Function
  • Examples

This post shows the basic math required to understand the boolean function analysis.

Definitions.

Rademacher Function

The n-th Rademacher function $r_n(t)$ is defined on the interval [0, 1] as follows. $r_n(t) = \operatorname{sign}\left( \sin(2^n \pi t) \right)$ or equivalently,

$$r_n(t) = (-1)^{\lfloor 2^n t \rfloor}$$

where $n \in \mathbb{N}$.

Or,

$r_i(x) = (-1)^{x_i}$ where $x_i$ satisfying the following expansion.

$$x = \sum_{i=0}^{+\infty} \frac{x_i}{2^n}$$ $$0\leq x <1/2^n; x_1 = 0;\\ 1/2^n \leq 2/2^n; x_{1} = 1;\\ ....\\$$

It is easy to see that $x_i$ differs with (odd) even number of bits with $x_{i+1}$ alternatively.

Walsh Function

The Walsh function is very similar to Rademacher function, but it has more interesting properties. The motivation of creating Walsh function is that to represent a periodic function by simple components like Fourier expansions.

It needs to satisfy some properties, like orthogonality basis.

Let $n = a_0 + 2 a_1 + \cdots + 2^k a_k \quad \text{where } a_i \in \{0,1\}$

Then, we have $w_n(x) = \Pi_{i=1}^k r_i(x)^{a_i}$

where $a_i$ is the indicator of the $i$-th bit of $n$.

To be more clearly, we have

$$w_n(x) =\Pi_{i=0}^k (-1)^{a_i x_i} = (-1)^{\sum_{i=0}^k a_ix_i}$$

Examples

n	Binary	Walsh Function Expression
0	000	$w_0(x) = 1$
1	001	$w_1(x) = r_0(x)$
2	010	$w_2(x) = r_1(x)$
3	011	$w_3(x) = r_0(x) \cdot r_1(x)$

$$w_0(x) = 1; \\w_1(x) = (-1)^{x_1};\\ w_2(x) = (-1)^{x_2}; \\w_3(x) = (-1)^{x_1+x_2}$$

where $0\leq x< 1/4, x_1 = 0, x_2 = 0$; $0\leq x < 1/4; x_1 = 0, x_2 = 0;\\ 1/4 \leq x < 1/2; x_1 = 0, x_2 = 1;\\ 1/2\leq x < 3/4; x_1 = 1, x_2 =0;\\ 3/4\leq x < 1; x_1 = 1, x_2 = 1;$

Then, it is easy to check the following.

• $$w_a(x) \cdot w_b(x) = w_{a \oplus b}(x)$$
• $\langle w_i, w_j\rangle =\int_0^1 w_i(x)w_j(x) dx= 0$ for any $i\neq j$.