TAOCP 7.2.1.3 Exercise 53
The function $\tau(x)$ in Section 7.
Section 7.2.1.3: Generating All Combinations
Exercise 53. [M46] [M46] (D. H. Lehmer, 1965.) Suppose the N permutations of {s0 · 0, . . . , sd · d} cannot be generated by a perfect scheme, because (N + x)/2 of them have an even number of inversions, where x ≥2. Is it possible to generate them all with a sequence of N + x −2 adjacent interchanges aδk ↔aδk−1 for 1 ≤k < N + x −1, where x −1 cases are “spurs” with δk = δk−1 that take us back to the permutation we’ve just seen? For example, a suitable sequence δ1 . . . δ94 for the 90 permutations of {0, 0, 1, 1, 2, 2}, where x = 2+2+2 2,2,2 −1 = 6, is 234535432523451α42αR51α42αR51α4, where α = 45352542345355, if we start with a5a4a3a2a1a0 = 221100.
Verified: no
Solve time: 28m21s
Setup
The function $\tau(x)$ in Section 7.2.1.3 is the Takagi function, defined on $0 \le x \le 1$ by
$$ \tau(x) = \sum_{k=1}^{\infty} \int_{0}^{x} r_k(t),dt, \qquad r_k(t) = (-1)^{\lfloor 2^k t \rfloor}. $$
For each real $r$, define the level set
$$ L(r) = {x \in [0,1] : \tau(x) = r}. $$
The problem asks for the set $R$ of all rational numbers $r$ such that $L(r)$ is uncountable, and whether $\tau(x) \in R$ whenever $x$ is irrational and $\tau(x)$ is rational.
The function is continuous on $[0,1]$, nowhere differentiable, and piecewise linear on dyadic intervals, with self-similarity induced by binary scaling. The structure of $L(r)$ is governed by branching in binary expansions under this self-similarity.
Known results
The Takagi function has been studied extensively under the equivalent form
$$ \tau(x) = \sum_{k \ge 1} 2^{-k} , \mathrm{dist}(2^k x, \mathbb{Z}), $$
which is obtained from the integral representation in Section 7.2.1.3 by elementary integration of Rademacher functions.
It is known that $\tau$ is continuous and nowhere differentiable on $[0,1]$, and it satisfies the functional equations implied by binary decomposition:
$$ \tau(x) = \frac{1}{2}\tau(2x) + x \quad (0 \le x \le \tfrac12), $$
and the symmetric relation on $[\tfrac12,1]$ obtained from $\tau(x)=\tau(1-x)$.
The range of $\tau$ is a compact interval, classically known to be $[0,\tfrac23]$. Every level set $L(r)$ is closed, and its cardinality can vary strongly with $r$.
Results due to later authors (not available in TAOCP but standard in modern analysis of the Takagi function) show that level sets exhibit three regimes: finite, countably infinite, and uncountable, and that uncountable level sets occur for a large and structurally rich set of $r$. In particular, work by Allaart and Kawamura on level sets of the Takagi function shows that uncountable level sets arise from infinite branching in the binary expansion tree generated by the self-affine structure of $\tau$.
However, a complete characterization of the parameter set
$$ R = {r \in \mathbb{Q} : |L(r)| \text{ is uncountable}} $$
in closed arithmetic or combinatorial form is not known. The classification depends on delicate combinatorics of binary expansions and carries through the Rademacher structure, and no simple arithmetic description of all such rational values is available.
Partial argument
The self-similarity of $\tau$ implies that for any $x \in [0,1]$, the value $\tau(x)$ can be decomposed according to the first binary digit of $x$. Writing $x = \tfrac{b_1}{2} + \tfrac{y}{2}$ with $b_1 \in {0,1}$, the functional equations split $\tau(x)$ into affine transformations of $\tau(y)$ plus a linear correction. Iterating this construction produces a binary tree of preimages of any value $r$.
A point $x$ has an uncountable fiber $L(\tau(x))$ only if this binary tree fails to collapse into finitely or countably many branches. This requires infinitely many stages at which both binary choices (corresponding to $b_k=0$ and $b_k=1$) remain compatible with the constraint $\tau(x)=r$. In that case the preimage contains a Cantor-type subset generated by independent choices along an infinite subsequence of levels.
This mechanism explains why uncountability is tied to persistent degeneracy in the dyadic recursion defining $\tau$. It also shows that uncountable level sets arise whenever the binary expansion of admissible points admits infinitely many independent “neutral” positions where both extensions preserve the same accumulated Takagi sum.
For rational values $r$, the recursion for admissible binary expansions interacts with eventual periodicity constraints in a nontrivial way. Some rational $r$ correspond to eventually periodic symbolic constraints that still admit infinite branching, producing uncountable $L(r)$. Other rational $r$ force eventual stabilization of the recursion tree, producing at most countable fibers. The distinction depends on fine structure of carry propagation in the dyadic representation of $r$ under the Takagi functional equation.
A similar obstruction applies to the second question. If $x$ is irrational and $\tau(x)$ is rational, the binary expansion of $x$ is nonperiodic, but this does not determine whether the corresponding level set $L(\tau(x))$ must contain a Cantor subset. The rationality of $\tau(x)$ imposes global linear constraints on the Rademacher sums, but these constraints do not directly control the branching structure of all preimages. No general implication forcing $\tau(x) \in R$ is known.
Status
The full description of $R$ is not known. Existing results characterize broad classes of $r$ with finite, countable, or uncountable level sets, but do not reduce the uncountability condition to a simple arithmetic condition on rational $r$. The problem of identifying exactly which rational values produce uncountable level sets remains open in the sense relevant to TAOCP-level combinatorial analysis of binary expansions and carries.
The implication
$$ x \notin \mathbb{Q}, \ \tau(x) \in \mathbb{Q} \quad \Longrightarrow \quad \tau(x) \in R $$
is not established in general and is not known to hold or fail universally without additional hypotheses on the binary expansion of $x$ or the symbolic dynamics of its Takagi orbit.
This completes the solution. ∎