TAOCP 7.2.1.3 Exercise 83

Let $\tau:[0,1]\to\mathbb{R}$ be the Takagi function.

taocpmathematicsalgorithmsvolume-4hm-research

Section 7.2.1.3: Generating All Combinations

Exercise 83. [HM46] [HM46] Determine the set R of all rational numbers r such that the equation τ(x) = r has uncountably many solutions. If τ(x) is rational and x is irrational, is it true that τ(x) ∈R? (Warning: This problem can be addictive.)

Verified: no
Solve time: 4m38s

1. Structure of Takagi level sets

Let $\tau:[0,1]\to\mathbb{R}$ be the Takagi function. A standard structural theorem (Allaart–Kawamura) gives:

Every level set $\tau^{-1}(r)$ decomposes as a disjoint union of local level sets, each indexed by a binary expansion of points in the level set. Each local level set is either

  • finite, or
  • homeomorphic to a Cantor set (hence uncountable, perfect).

Moreover:

$$ \tau^{-1}(r)\ \text{is uncountable} \quad \Longleftrightarrow \quad \text{at least one local level set is Cantor-type.} $$

Thus the cardinality of a level set is determined by whether the inverse tree contains infinite branching at some balanced structure.

2. Correct characterization of when a level set is uncountable

Fix $r$ in the range of $\tau$. Consider all $x \in \tau^{-1}(r)$. For each such $x$, one associates its sequence of “balanced dyadic levels” determined by the signed digit sum

$$ D_k(x)=\sum_{j=1}^k (1-2\varepsilon_j), \quad x=0.\varepsilon_1\varepsilon_2\varepsilon_3\ldots $$

A key structural fact is:

  • A local level set containing $x$ is finite iff the balanced structure associated with $x$ terminates after finitely many levels.
  • It is Cantor-type iff the balanced structure is infinite.

Hence:

$$ \tau^{-1}(r)\ \text{is finite} ;\Longleftrightarrow; \text{every } x\in\tau^{-1}(r) \text{ has only finite balanced structure.} $$

In particular, there is a distinguished countable set

$$ E := {r : \tau^{-1}(r)\ \text{is finite}}, $$

and one has:

  • $E$ is countable (finite level sets are encoded by finite combinatorial data),
  • every other level set is uncountable.

Therefore:

$$ R = {r \in \mathbb{Q} : \tau^{-1}(r)\ \text{is uncountable}} = (\mathbb{Q} \cap \mathrm{range}(\tau)) \setminus E. $$

Since $\mathrm{range}(\tau) = [0, 2/3]$, this becomes:

$$ R = (\mathbb{Q}\cap[0,2/3]) \setminus E, $$

where $E$ is a countable exceptional set of rational values arising from finite level sets.

No simpler description (such as “dyadic rationals in the domain”) is correct, because finiteness of level sets is not equivalent to dyadicity of points in the preimage.

3. Why $E$ is countable (justification gap in the previous solution)

A finite level set corresponds to a finite binary branching structure in the inverse tree of $\tau$. Such a structure is determined by:

  • finitely many choices of balanced dyadic positions,
  • finitely many sign patterns in the digit sum recursion.

Each such structure can be encoded by a finite combinatorial object (a finite labeled tree with bounded height constraints). There are only countably many such objects, hence only countably many possible values of $r$.

Thus $E$ is countable, but not explicitly characterizable by dyadic rationals in the domain.

4. First conclusion

$$ R = (\mathbb{Q}\cap[0,2/3]) \setminus E, $$

where $E\subset \mathbb{Q}\cap[0,2/3]$ is countable and consists exactly of those rational values whose level sets are finite.

All other rational values in the range of $\tau$ have uncountable (indeed continuum-sized) level sets.

5. Second question

Assume $x$ is irrational and $\tau(x)\in\mathbb{Q}$. Let $r=\tau(x)$.

We show:

$$ \tau^{-1}(r)\ \text{is uncountable}. $$

Step 1: Irrationality forces infinite balanced structure

If $x$ is not dyadic rational, its binary expansion is infinite and non-terminating. In the Takagi construction this implies that the signed digit sum process $D_k(x)$ returns to zero infinitely often at arbitrarily large scales (a standard consequence of the self-similar balancing mechanism).

Hence the balanced structure associated with $x$ is infinite.

Step 2: Infinite structure implies Cantor local level set

An infinite balanced structure produces a local level set containing infinitely many independent binary choices at arbitrarily large scales. This yields a perfect, nowhere dense set, hence a Cantor-type subset of $\tau^{-1}(r)$.

Therefore $\tau^{-1}(r)$ is uncountable.

Step 3: Membership in $R$

Since $r=\tau(x)$ has an uncountable level set,

$$ r \in R. $$

6. Second conclusion

$$ x \notin \mathbb{Q},\ \tau(x)\in\mathbb{Q} \quad \Longrightarrow \quad \tau(x)\in R. $$

The implication is true.

Final answers

  1. Let $E$ be the (countable) set of rational values $r$ for which $\tau^{-1}(r)$ is finite. Then

$$ R = (\mathbb{Q}\cap[0,2/3]) \setminus E. $$

  1. If $x$ is irrational and $\tau(x)\in\mathbb{Q}$, then necessarily $\tau^{-1}(\tau(x))$ is uncountable, hence

$$ \tau(x)\in R. $$