TAOCP 7.2.1.1 Exercise 24
The flaw in the previous solution is the attempt to treat an infinite XOR as a topological limit inside the product space.
Section 7.2.1.1: Generating All n-Tuples
Exercise 24. [M21] [M21] Consider extending the Gray binary function g to all 2-adic integers (see Section 7.1.3). What is the corresponding inverse function g[−1]?
Verified: no
Solve time: 4m32s
The flaw in the previous solution is the attempt to treat an infinite XOR as a topological limit inside the product space. The correct way to make the argument rigorous is to avoid infinite limits entirely and instead work at the finite level $\mathbb{Z}/2^n\mathbb{Z}$, where everything is genuinely finite and compatible with inverse limits.
1. Gray map on finite 2-adic truncations
Every element $x \in \mathbb{Z}_2$ corresponds to a compatible system
$$ x \bmod 2^n \in \mathbb{Z}/2^n\mathbb{Z}. $$
Write the binary expansion of $x \bmod 2^n$ as
$$ x = \sum_{j=0}^{n-1} x_j 2^j, \quad x_j \in {0,1}. $$
The Gray map is defined digitwise by
$$ y_j = x_j \oplus x_{j+1}, $$
with the convention $x_n = 0$ in $\mathbb{Z}/2^n\mathbb{Z}$.
Thus, at level $n$, the map
$$ g_n : \mathbb{Z}/2^n\mathbb{Z} \to \mathbb{Z}/2^n\mathbb{Z} $$
is given by a triangular linear transformation over $\mathbb{F}_2$.
Explicitly,
$$ y_j = x_j \oplus x_{j+1}, \quad 0 \le j \le n-2, \qquad y_{n-1} = x_{n-1}. $$
This system can be uniquely solved backwards:
$$ x_{n-1} = y_{n-1}, $$
and for $j = n-2, \dots, 0$,
$$ x_j = y_j \oplus x_{j+1}. $$
Hence $g_n$ is a bijection for every $n$, and therefore induces a bijection on the inverse limit $\mathbb{Z}_2$.
2. Inverse at finite level
Unwinding the recursion gives, for $0 \le j \le n-1$,
$$ x_j = y_j \oplus y_{j+1} \oplus \cdots \oplus y_{n-1}. $$
This is a finite XOR, so it is completely well-defined in $\mathbb{Z}/2^n\mathbb{Z}$.
Thus the inverse map $g_n^{-1}$ is explicitly given by
$$ (g_n^{-1}(y))j = \bigoplus{k=j}^{n-1} y_k. $$
No infinite expressions appear at this stage.
3. Passage to $\mathbb{Z}_2$
The systems $(g_n)_n$ are compatible with reduction modulo $2^n$, hence define a continuous bijection
$$ g : \mathbb{Z}_2 \to \mathbb{Z}_2. $$
Its inverse is determined coordinatewise as follows.
Fix $j$. For any $n > j$, the $j$-th digit of $x \bmod 2^n$ is
$$ x_j^{(n)} = \bigoplus_{k=j}^{n-1} y_k. $$
Now observe the key point:
If $m > n > j$, then both expressions compute the same element $x \bmod 2^{n}$, so their $j$-th digits must agree. Hence the sequence
$$ \bigoplus_{k=j}^{n-1} y_k $$
is eventually constant as an element of the inverse system at coordinate $j$. This stabilization happens because changing $n$ only alters digits above position $n-1$, which do not affect lower truncations.
Therefore the $j$-th digit of the inverse is well-defined by this stable value.
We may write it formally as
$$ x_j = \bigoplus_{k=j}^{\infty} y_k, $$
with the precise meaning:
$$ x_j = \bigoplus_{k=j}^{n-1} y_k \quad \text{for any } n>j. $$
This is not an analytic limit, but a statement about stabilization in the inverse system.
4. Explicit inverse of the Gray map on $\mathbb{Z}_2$
We obtain the inverse function $g^{-1} : \mathbb{Z}_2 \to \mathbb{Z}_2$ in digit form:
$$ (g^{-1}(y))j = \bigoplus{k=j}^{n-1} y_k \quad \text{for any } n>j. $$
Equivalently, in shift notation,
$$ g^{-1}(y) = y \oplus (y \gg 1) \oplus (y \gg 2) \oplus \cdots, $$
where the expression is interpreted coordinatewise, and for each fixed digit only finitely many truncations are needed to determine its value.
5. Continuity and well-definedness
For a fixed $j$, the value $x_j$ depends only on the finite set of digits $y_j, y_{j+1}, \dots, y_{n-1}$ for any $n>j$. Hence each coordinate function of $g^{-1}$ factors through a finite quotient $\mathbb{Z}_2 \to \mathbb{Z}/2^n\mathbb{Z}$, which proves continuity in the product topology.
No infinite XOR is taken as a topological limit; all computations reduce to finite XORs at finite levels of the inverse system.
Conclusion
The Gray map extends to a bijection $g : \mathbb{Z}_2 \to \mathbb{Z}_2$, and its inverse is given by the finite-prefix XOR rule at each truncation level:
$$ (g^{-1}(y))j = \bigoplus{k=j}^{n-1} y_k \quad (n>j). $$
This defines a well-posed, continuous inverse on $\mathbb{Z}_2$, and the apparent “infinite XOR” is only shorthand for these stable finite computations.