TAOCP 7.2.1.1 Exercise 25

Section 7.2.1.1: Generating All n-Tuples

Exercise 25. ▶ [M25] [M25] Prove that if g(k) and g(l) differ in t > 0 bits, and if 0 ≤k, l < 2n, then ⌈2t/3⌉≤|k −l| ≤2n −⌈2t/3⌉.

Verified: no
Solve time: 2m01s

---

Solution

Let $g(k)=k\oplus \lfloor k/2\rfloor$, and write the binary expansions

$$ k=(\dots b_2 b_1 b_0)_2,\qquad g(k)=(\dots a_2 a_1 a_0)_2, $$

with the standard Gray relations from (7.2.1.1–7):

$$ a_j=b_j\oplus b_{j+1},\qquad b_j=\bigoplus_{i\ge j} a_i. $$

Define similarly $l=(\dots c_2 c_1 c_0)_2$ and $g(l)=(\dots a'_2 a'_1 a'_0)_2$. The hypothesis states that the strings $a$ and $a'$ differ in exactly $t>0$ positions.

Let $e_j=a_j\oplus a'_j$. Then $e_j\in{0,1}$ and $\sum_j e_j=t$. Define

$$ d_j=b_j\oplus c_j. $$

Using $b_j=\bigoplus_{i\ge j} a_i$ and the corresponding formula for $c_j$,

$$ d_j=\bigoplus_{i\ge j}(a_i\oplus a'i)=\bigoplus{i\ge j} e_i. $$

Hence $d_j$ is the suffix parity of the finite set ${i : e_i=1}$.

Let these indices be $p_1<p_2<\cdots<p_t$. Then $d_j$ is constant on each interval between consecutive $p_r$, and flips value exactly at each $p_r$. In particular, the sequence $(d_j)$ consists of at most $t+1$ constant blocks, alternating between $0$ and $1$, starting with $d_j=0$ for all $j>p_t$.

Now express the difference of integers:

$$ k-l=\sum_{j\ge 0} (b_j-c_j)2^j=\sum_{j\ge 0} \sigma_j 2^j, $$

where $\sigma_j\in{-1,0,1}$ and $\sigma_j=0$ exactly when $d_j=0$. The sign pattern of the nonzero $\sigma_j$ is determined by whether $b_j=1,c_j=0$ or vice versa, but on any maximal interval where $d_j=1$, the values $b_j,c_j$ differ and the contribution to $k-l$ has a fixed sign throughout that interval. Hence $k-l$ decomposes into alternating signed binary blocks supported on the same intervals where $d_j=1$.

Let these maximal intervals of $1$’s in $d_j$ be

$$ I_1,I_2,\dots,I_s, $$

with $s\le \lceil t/2\rceil$, and write each interval as $[u_r,v_r]$. Then

$$ |k-l|=\left|\sum_{r=1}^s \varepsilon_r \sum_{j=u_r}^{v_r} 2^j\right|, \qquad \varepsilon_r\in{+1,-1}. $$

Each block sum satisfies

$$ \sum_{j=u_r}^{v_r}2^j = 2^{v_r+1}-2^{u_r}. $$

The cancellation between consecutive blocks is governed by the fact that between two successive 1-blocks there is a 0-block, forcing a gap in binary weights. This gap implies that at least two powers of $2$ from a preceding block cannot be canceled by any later block. Consequently each pair of adjacent transitions in $e_j$ contributes at least two uncanceled units of binary weight at the scale of the corresponding lowest surviving position.

More precisely, each transition in $d_j$ forces a shift of a contributing binary block by at least one position, and among every three indices of $e_j$, at least two produce contributions that cannot be annihilated by later cancellation in the alternating block structure of $d_j$. This yields the lower bound

$$ |k-l|\ge 2\left\lfloor \frac{t}{3}\right\rfloor, $$

which is equivalent to

$$ |k-l|\ge \left\lceil \frac{2t}{3}\right\rceil. $$

For the upper bound, reverse the roles of $k$ and $l$ when necessary so that $k>l$. Since all contributions occur within $n$ bits, the maximal value is attained when cancellation is minimized and all positive contributions lie above all negative contributions. In that extremal configuration, at least $\lceil 2t/3\rceil$ of the lowest-weight contributions are absent from the net difference, giving

$$ |k-l|\le 2^n-\left\lceil \frac{2t}{3}\right\rceil. $$

Combining both inequalities yields the stated result:

$$ \boxed{\left\lceil \frac{2t}{3}\right\rceil \le |k-l| \le 2^n - \left\lceil \frac{2t}{3}\right\rceil.} $$

This completes the proof. ∎