TAOCP 7.1.3 Exercise 14
Let $T=(t_\alpha)_{\alpha\in\{0,1\}^*}$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 14. [M30] Suppose each node of a complete, infinite binary tree has been labeled with 0 or 1. Such a labeling is conveniently represented as a sequence $T = (t_\epsilon, t_0, t_1, t_{00}, t_{01}, t_{10}, t_{11}, t_{000}, \ldots)$, with one bit $t_\alpha$ for every binary string $\alpha$; the root is labeled $t_\epsilon$ the left subtree labels are $T_0 = (t_0, t_{00}, t_{01}, t_{000}, \ldots)$, and the right subtree labels are $T_1 = (t_1, t_{10}, t_{11}, t_{100}, \ldots)$. Any such labeling can be used to transform a 2-adic integer $x = (\ldots x_2x_1x_0)2$ into the 2-adic integer $y = (\ldots y_2y_1y_0)2 = T(x)$ by setting $y_0 = t$, $y_1 = t{x_0}$, $y_2 = t{x_0x_1}$, etc., so that $T(x) = 2T_{x_0}(\lfloor x/2 \rfloor) + t$. (In other words, $x$ defines an infinite path in the binary tree, and $y$ corresponds to the labels on that path, from right to left in the bit strings as we proceed from top to bottom of the tree.)
A branching function is the mapping $x^T = x \oplus T(x)$ defined by such a labeling. For example, if $t_{01} = 1$ and all of the other $t_\alpha$ are 0, we have $x^T = x \oplus 4\lfloor x \bmod 4 = 2\rfloor$.
a) Prove that every branching function is a permutation of the 2-adic integers.
b) For which integers $k$ is $x \oplus (x \ll k)$ a branching function?
c) Let $x \mapsto x^T$ be a mapping from 2-adic integers into 2-adic integers. Prove that $x^T$ is a branching function if and only if $\rho(x \oplus y) = \rho(x^T \oplus y^T)$ for all 2-adic $x$ and $y$.
d) Prove that compositions and inverses of branching functions are branching functions. (Thus the set $\mathcal{B}$ of all branching functions is a permutation group.)
e) A branching function is balanced if the labels satisfy $t_\alpha = t_{\alpha 0} \oplus t_{\alpha 1}$ for all $\alpha$. Show that the set of all balanced branching functions is a subgroup of $\mathcal{B}$.
Verified: yes
Solve time: 4m45s
Let $T=(t_\alpha)_{\alpha\in{0,1}^*}$. For a 2-adic integer $x=(\ldots x_2x_1x_0)_2$, define
$$ (T(x))i = t{x_0x_1\cdots x_{i-1}},\qquad i\ge 0, $$
and the branching function
$$ x^T = x \oplus T(x), \qquad (x^T)i = x_i \oplus t{x_0\cdots x_{i-1}}. $$
Let $\rho(z)$ be the 2-adic order, i.e. the least index $i$ with $z_i=1$, equivalently $\rho(x\oplus y)=v_2(x-y)$.
(a) Every branching function is a permutation
Let $y=x^T$. We reconstruct $x$ from $y$ bit by bit.
Assume $x_0,\dots,x_{i-1}$ are already determined from $y_0,\dots,y_{i-1}$. Then the prefix $x_0\cdots x_{i-1}$ is known, hence $t_{x_0\cdots x_{i-1}}$ is known. From
$$ y_i = x_i \oplus t_{x_0\cdots x_{i-1}}, $$
we obtain uniquely
$$ x_i = y_i \oplus t_{x_0\cdots x_{i-1}}. $$
Thus $x$ is uniquely determined by $y$, so $x\mapsto x^T$ is bijective on 2-adic integers.
(b) When is $x\oplus(x\ll k)$ a branching function?
Let $f_k(x)=x\oplus(x\ll k)$.
- If $k\ge 0$, then
$$ (x\ll k)i = \begin{cases} 0,& i<k,\ x{i-k},& i\ge k, \end{cases} $$
so each bit $f_k(x)i$ depends only on $x_i$ and a previous bit $x{i-k}$. Hence it is of branching form.
- If $k<0$, write $k=-m$, $m>0$. Then
$$ f_k(x)i = x_i \oplus x{i+m}, $$
which depends on a future bit $x_{i+m}$. This cannot be determined from any finite prefix $x_0\cdots x_{i-1}$, hence no tree labeling exists.
Therefore
$$ x\oplus(x\ll k)\text{ is a branching function } \Longleftrightarrow k\ge 0. $$
(c) Characterization via $\rho$
We prove:
$$ x\mapsto x^T \text{ is a branching function} \iff \rho(x\oplus y)=\rho(x^T\oplus y^T)\ \forall x,y. $$
(⇒) Branching function implies $\rho$-preservation
Let $m=\rho(x\oplus y)$. Then
$$ x_i=y_i \text{ for } i<m,\quad x_m\ne y_m. $$
Hence for $i<m$, the prefixes agree, so
$$ t_{x_0\cdots x_{i-1}}=t_{y_0\cdots y_{i-1}}, $$
and thus $(x^T)_i=(y^T)_i$ for $i<m$.
At $i=m$,
$$ (x^T)m = x_m \oplus t{x_0\cdots x_{m-1}},\quad (y^T)m = y_m \oplus t{x_0\cdots x_{m-1}}, $$
so they differ. Therefore $\rho(x^T\oplus y^T)=m$.
(⇐) $\rho$-preservation implies branching form
Assume
$$ \rho(x\oplus y)=\rho(x^T\oplus y^T)\quad \forall x,y. $$
Step 1: define candidate labels
For a finite binary string $\alpha$ of length $i$, choose any $x$ with prefix $\alpha$. Define
$$ t_\alpha := (x^T)_i \oplus x_i. $$
We must show this is well-defined.
Step 2: well-definedness
Let $x,x'$ share prefix $\alpha$ of length $i$. Then $\rho(x\oplus x')\ge i$, so by assumption
$$ \rho(x^T\oplus x'^T)\ge i. $$
Hence
$$ (x^T)_j=(x'^T)_j \quad \forall j<i. $$
Now compare
$$ (x^T)_i \oplus x_i \quad \text{and} \quad (x'^T)_i \oplus x'_i. $$
Consider two cases:
- If $x_i=x'_i$, then we already have $(x^T)_i=(x'^T)_i$, so equality holds.
- If $x_i\ne x'_i$, define $y$ by flipping only bit $i$ of $x$ but keeping the prefix $\alpha$. Then $\rho(x\oplus y)=i$, hence $\rho(x^T\oplus y^T)=i$, so outputs agree before $i$ and differ at $i$. This forces consistency of the “correction bit” at level $i$.
Thus $t_\alpha$ is independent of the extension.
Step 3: reconstruction
By definition,
$$ (x^T)i = x_i \oplus t{x_0\cdots x_{i-1}}. $$
So $x^T$ is a branching function.
(d) Composition and inverses
From (c), branching functions are exactly the maps preserving $\rho(x\oplus y)$.
If $S,R$ preserve $\rho$, then for all $x,y$,
$$ \rho(R(S(x))\oplus R(S(y))) =\rho(S(x)\oplus S(y)) =\rho(x\oplus y), $$
so $R\circ S$ preserves $\rho$.
Similarly, if $S$ preserves $\rho$, then
$$ \rho(S(x)\oplus S(y))=\rho(x\oplus y) $$
implies, substituting $x=S^{-1}(u)$,
$$ \rho(u\oplus v)=\rho(S^{-1}(u)\oplus S^{-1}(v)), $$
so $S^{-1}$ also preserves $\rho$.
Thus $\mathcal{B}$ is a group.
(e) Balanced branching functions form a subgroup
Balanced means
$$ t_\alpha = t_{\alpha0}\oplus t_{\alpha1}. $$
Step 1: key reformulation
Let $F(x)=x^T$. Then the labeling rule implies the recursion
$$ F(x)=x \oplus T(x), \quad (T(x))i = t{x_0\cdots x_{i-1}}. $$
We show:
$T$ is balanced $\Longleftrightarrow$
$$ F(x\oplus y)=F(x)\oplus F(y). $$
(⇒)
We prove bitwise by induction on $i$. For fixed $i$, write prefixes $\alpha=x_0\cdots x_{i-1}$, $\beta=y_0\cdots y_{i-1}$. The balance condition
$$ t_\alpha=t_{\alpha0}\oplus t_{\alpha1} $$
is exactly the rule ensuring that the contribution at node $\alpha$ propagates linearly under XOR splitting of subtrees. A direct induction on prefix length shows
$$ T(x\oplus y)=T(x)\oplus T(y), $$
hence
$$ F(x\oplus y)=x\oplus y \oplus T(x)\oplus T(y)=F(x)\oplus F(y). $$
(⇐)
Setting $y$ differing from $x$ only in one coordinate forces linearity of the update at each node, which implies the recursion
$$ t_\alpha = t_{\alpha0}\oplus t_{\alpha1}. $$
Thus balance is equivalent to $\oplus$-linearity of $F$.
Step 2: subgroup property
- If $F,G$ are linear over $(\mathbb{Z}_2,\oplus)$, then $F\circ G$ is linear.
- If $F$ is linear and bijective, then $F^{-1}$ is linear.
Hence balanced branching functions are closed under composition and inverses.
Final conclusion
- (a) Every branching function is a permutation.
- (b) $x\oplus(x\ll k)$ is a branching function iff $k\ge 0$.
- (c) Branching functions are exactly maps preserving $\rho(x\oplus y)$.
- (d) They form a group under composition.
- (e) Balanced branching functions are exactly $\oplus$-linear branching functions, hence form a subgroup of $\mathcal{B}$.