TAOCP 7.2.1.1 Exercise 34

Let $x \in [0,1)$ and write its dyadic expansion x = 0.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.1: Generating All n-Tuples

Exercise 34. [M21] [M21] The Paley functions pk(x) are defined by p0(x) = 1 and pk(x) = (−1)⌊2x⌋kp⌊k/2⌋(2x). Show that pk(x) has a simple expression in terms of Rademacher functions, analogous to (17), and relate Paley functions to Walsh functions.

Verified: no
Solve time: 6m20s

Solution

Let $x \in [0,1)$ and write its dyadic expansion

$$ x = 0.x_1 x_2 x_3 \ldots,\qquad x_j \in {0,1}. $$

Let $r_j(x)$ denote the $j$-th Rademacher function,

$$ r_j(x) = (-1)^{x_j}. $$

Let $k$ have binary expansion

$$ k = (b_m \cdots b_1 b_0)_2,\qquad b_j \in {0,1}, $$

and let the Walsh function be defined by

$$ w_k(x) = \prod_{j \ge 0} r_{j+1}(x)^{b_j}. $$

Transformation under $x \mapsto 1-x$

For dyadic expansions, replacing $x$ by $1-x$ flips every binary digit in the sense that each Rademacher function changes sign:

$$ r_j(1-x) = -r_j(x), $$

since the $j$-th binary digit is complemented under $x \mapsto 1-x$ in the dyadic system, hence $(-1)^{(1-x_j)} = -(-1)^{x_j}$.

Applying this to $w_k$,

$$ w_k(1-x) = \prod_{j \ge 0} r_{j+1}(1-x)^{b_j} = \prod_{j \ge 0} (-r_{j+1}(x))^{b_j}. $$

Each factor contributes a sign $-1$ exactly when $b_j = 1$, hence

$$ w_k(1-x) = (-1)^{\sum_{j \ge 0} b_j} \prod_{j \ge 0} r_{j+1}(x)^{b_j}. $$

Let $\nu(k) = \sum_{j \ge 0} b_j$ be the number of $1$-bits in the binary expansion of $k$. Then

$$ w_k(1-x) = (-1)^{\nu(k)} w_k(x). $$

Comparison with the claimed identity

The statement to test is

$$ w_k(-x) = (-1)^k w_k(x). $$

Since Walsh functions are typically defined on $[0,1)$ and extended periodically, $-x$ corresponds to $1-x$ in this setting. The derived identity shows that the correct exponent depends on the Hamming weight $\nu(k)$, not on $k$ itself.

To disprove the claim, take $k=2$. Then $k=(10)_2$, so $\nu(k)=1$. The identity above gives

$$ w_2(1-x) = -w_2(x), $$

while

$$ (-1)^k = (-1)^2 = 1. $$

Hence

$$ w_2(1-x) \ne (-1)^k w_2(x) $$

for all $x$ where $w_2(x) \ne 0$.

The claimed identity fails.

$$ \boxed{\text{False}} $$