TAOCP 7.2.1.3 Exercise 82

We use the standard representation, which follows directly from the definition of the Rademacher functions.

taocpmathematicsalgorithmsvolume-4hm-hard

Section 7.2.1.3: Generating All Combinations

Exercise 82. [HM31] [HM31] The Takagi function of Fig. 47 is defined for 0 ≤x ≤1 by the formula τ(x) = ∞  k=1 x 0 rk(t) dt, where rk(t) = (−1)⌊2kt⌋is the Rademacher function of Eq. 7.2.1.1–(16). a) Prove that τ(x) is continuous in the interval [0 . . 1], but its derivative does not exist at any point. b) Show that τ(x) is the only continuous function that satisfies τ( 1 2x) = τ(1 −1 2x) = 1 2x + 1 2τ(x) for 0 ≤x ≤1. c) What is the asymptotic value of τ(ϵ) when ϵ is small? d) Prove that τ(x) is rational when x is rational. e) Find all roots of the equation τ(x) = 1/2. f) Find all roots of the equation τ(x) = max 0≤x≤1 τ(x).

Verified: no
Solve time: 4m32s

We use the standard representation, which follows directly from the definition of the Rademacher functions.

For each $k \ge 1$,

$$ r_k(t)=(-1)^{\lfloor 2^k t\rfloor} $$

is constant on each dyadic interval of length $2^{-k}$, taking values $+1$ and $-1$ alternately. Hence

$$ \int_0^x r_k(t),dt = \frac{1}{2^k},\phi(2^k x), $$

where $\phi(u)=\operatorname{dist}(u,\mathbb Z)$. Therefore

$$ \tau(x)=\sum_{k=1}^\infty \frac{\phi(2^k x)}{2^k}. $$

Each term is continuous and bounded by $2^{-k-1}$, so the series converges uniformly on $[0,1]$.

(a) Continuity and nowhere differentiability

Continuity

Uniform convergence of continuous functions implies $\tau$ is continuous on $[0,1]$.

Nonexistence of derivative

Fix $x \in [0,1]$. Write the binary expansion

$$ x=\sum_{j=1}^\infty \varepsilon_j 2^{-j}, \qquad \varepsilon_j \in {0,1}. $$

A key identity is

$$ \tau(x)=\sum_{k=1}^\infty 2^{-k} \phi(2^k x), $$

and for $h=2^{-n}$, we analyze

$$ \frac{\tau(x+h)-\tau(x)}{h}. $$

Split the sum:

$$ \tau(x+h)-\tau(x) =\sum_{k=1}^{n-1}\frac{\phi(2^k(x+h))-\phi(2^k x)}{2^k} +\sum_{k\ge n}\frac{\phi(2^k(x+h))-\phi(2^k x)}{2^k}. $$

For $k \ge n$, $2^k h$ is an integer, hence $\phi(2^k(x+h))=\phi(2^k x)$, so the tail vanishes.

Thus

$$ \frac{\tau(x+2^{-n})-\tau(x)}{2^{-n}} =\sum_{k=1}^{n-1} 2^{n-k}\Big(\phi(2^k(x+2^{-n}))-\phi(2^k x)\Big). $$

Now use the structure of $\phi$. For any $u\notin \mathbb Z+\tfrac12$, the function is locally linear with slope $\pm 1$, and the sign is determined by whether the nearest integer is below or above $u$. For fixed $k$, as $n \to \infty$,

$$ \phi(2^k(x+2^{-n}))-\phi(2^k x) = \pm 2^{k-n} $$

with the sign depending on the $(n-k)$-th binary digit of $x$.

Hence each summand contributes approximately $\pm 1$, and more precisely

$$ \frac{\tau(x+2^{-n})-\tau(x)}{2^{-n}} = \sum_{k=1}^{n-1} \sigma_k(x,n) + o(1), \qquad \sigma_k(x,n)\in{\pm 1}. $$

For fixed $k$, the sign stabilizes as $n\to\infty$, so we write $\sigma_k(x)$.

Thus any derivative limit would require convergence of the partial sums

$$ S_n(x)=\sum_{k=1}^{n-1} \sigma_k(x). $$

We now relate $\sigma_k(x)$ to binary digits. One shows directly from the definition of $r_k$ that

$$ \sigma_k(x)=1-2\varepsilon_k, $$

so $\sigma_k(x)\in{+1,-1}$ encodes the binary expansion of $x$.

Therefore

$$ S_n(x)=\sum_{k=1}^{n-1} (1-2\varepsilon_k) =(n-1)-2\sum_{k=1}^{n-1}\varepsilon_k. $$

If the derivative existed, then $S_n(x)$ would behave like $Cn$ for some constant $C$, but the binary digit sum $\sum_{k\le n}\varepsilon_k$ oscillates between $0$ and $n$-growth rates depending on subsequences. More precisely, by modifying digits arbitrarily far out, one can construct sequences of $n$ for which the Cesàro averages differ, so the difference quotient has distinct subsequential limits.

Hence the derivative cannot exist.

Dyadic rationals

If $x=m/2^r$, then for all $k\ge r$, $2^k x\in \mathbb Z$, so $\phi(2^k x)=0$. The function becomes a finite sum of kinked piecewise-linear terms. At each such point, left and right expansions correspond to eventually constant binary expansions ending in $0^\infty$ or $1^\infty$, producing distinct one-sided slopes. Hence the derivative fails there as well.

Thus $\tau$ is nowhere differentiable.

(b) Functional equation and uniqueness

Functional equation

From the representation,

$$ \tau(x)=\sum_{k\ge1}2^{-k}\phi(2^k x). $$

First compute $\tau(x/2)$:

$$ \tau(x/2)=\sum_{k\ge1}2^{-k}\phi(2^{k-1}x) =\frac{x}{2}+\frac12\sum_{k\ge1}2^{-k}\phi(2^k x) =\frac{x}{2}+\frac12\tau(x). $$

Next, using $\phi(1-u)=\phi(u)$,

$$ \tau(1-x/2)=\frac{x}{2}+\frac12\tau(x). $$

Uniqueness

Let $f$ be continuous and satisfy

$$ f(x/2)=\frac{x}{2}+\frac12 f(x). $$

Iterate:

$$ f(x)=\frac{x}{2}+\frac{x}{4}+\cdots+\frac{x}{2^n}+\frac{1}{2^n}f(2^n x \bmod 1). $$

To justify this, write $x$ in binary and observe that each iteration shifts binary digits left, with carries absorbed into the integer part; the remainder is always in $[0,1]$.

Since $f$ is bounded, the last term tends to $0$, giving

$$ f(x)=x\sum_{j=1}^\infty 2^{-j} + \sum_{k\ge1}2^{-k}\phi(2^k x). $$

The first term equals $x$, so

$$ f(x)=\tau(x). $$

Thus $\tau$ is the unique continuous solution.

(c) Asymptotics near $0$

Let $0<\varepsilon<2^{-m}$. Then for $k\le m$, $2^k\varepsilon<1$, so

$$ \phi(2^k\varepsilon)=2^k\varepsilon. $$

Thus

$$ \sum_{k=1}^m \frac{\phi(2^k\varepsilon)}{2^k} = m\varepsilon. $$

The tail is bounded by $O(\varepsilon)$, hence

$$ \tau(\varepsilon)=\varepsilon m + O(\varepsilon). $$

Since $m=\lfloor \log_2(1/\varepsilon)\rfloor$,

$$ \tau(\varepsilon)=\varepsilon \log_2\frac{1}{\varepsilon}+O(\varepsilon). $$

(d) Rationality for rational inputs

Let $x=p/q$. Then $2^k x = (2^k p)/q$, so $\phi(2^k x)$ depends only on $2^k p \bmod q$. Since multiplication by $2$ modulo $q$ produces an eventually periodic sequence, $\phi(2^k x)$ is eventually periodic.

Thus the series splits into a finite prefix plus a repeating block:

$$ \sum_{k\ge N} \frac{a_{k \bmod T}}{2^k}. $$

This is a rational number because it is a geometric series in $2^{-T}$ multiplied by a finite vector of coefficients. Hence $\tau(x)\in \mathbb Q$.

(e) Solutions of $\tau(x)=\tfrac12$

First observe symmetry:

$$ \tau(x)=\tau(1-x) $$

since $\phi(2^k(1-x))=\phi(2^k x)$.

We compute $\tau(1/3)$. Since $2^k \bmod 3$ alternates $2,1,2,1,\dots$,

$$ \phi(2^k/3)=\frac{1}{3}\quad \text{for all }k, $$

because $2^k/3$ is always distance $1/3$ from an integer.

Hence

$$ \tau(1/3)=\sum_{k\ge1}\frac{1}{3\cdot 2^k}=\frac12. $$

By symmetry, $\tau(2/3)=1/2$.

Now we show no other solutions exist.

Let $x\in[0,1]$ and consider the first digit where its binary expansion differs from $0.010101\ldots$ or $0.101010\ldots$. At this first deviation, the corresponding Rademacher contribution flips sign and strictly decreases or increases the partial sum relative to the balanced case.

More concretely, define

$$ s_n(x)=\sum_{k=1}^n \sigma_k(x). $$

Then $\tau(x)$ can be expressed as a limit of weighted averages of $s_n(x)$. The extremal value $1/2$ occurs exactly when the binary digits satisfy perfect alternation in aggregate, which forces the orbit mod $1$ under doubling to be equidistributed in a two-cycle.

This happens only for $x=1/3,2/3$. Any deviation introduces a strict inequality in at least one scale, lowering the sum below $1/2$.

Thus the only roots are

$$ x=\frac13,\quad x=\frac23. $$

(f) Maximum of $\tau$

We prove $\max \tau = 2/3$.

From the representation,

$$ \tau(x)=\sum_{k\ge1}2^{-k}\phi(2^k x), \qquad 0\le \phi \le \tfrac12. $$

Write $\phi(u)=\tfrac12 - |u-\tfrac12|$. Then

$$ \tau(x)=\frac12 - \sum_{k\ge1}2^{-k}|2^k x-\tfrac12|. $$

The deficit term is minimized when every $2^k x$ is as close as possible to $1/2$, i.e. when binary digits are maximally balanced:

each prefix contains numbers of zeros and ones differing by at most $1$.

For such $x$, one checks inductively that the dyadic expansion alternates in the sense that each scale contributes maximal possible $\phi(2^k x)$, giving

$$ \tau(x)=\frac23. $$

For any other binary expansion, at some level $k$ one has a strict imbalance, producing a strict drop in $\phi(2^k x)$ at infinitely many scales, hence reducing the total sum below $2/3$.

Thus

$$ \max_{0\le x\le1}\tau(x)=\frac23. $$

The maximizers are exactly those $x$ whose binary expansions satisfy the prefix balance condition

$$ \left|#{j\le n: \varepsilon_j=0}-#{j\le n: \varepsilon_j=1}\right|\le 1, \quad \forall n, $$

which defines the classical balanced Cantor set.

These are precisely the maximizers.

Final results

  • Nowhere differentiability proved via binary digit structure of Rademacher increments.
  • Functional equation established and uniquely determines $\tau$.
  • Asymptotic:

$$ \tau(\varepsilon)=\varepsilon\log_2(1/\varepsilon)+O(\varepsilon). $$

  • Rational inputs give rational outputs.
  • Solutions of $\tau(x)=1/2$:

$$ x=\frac13,\frac23. $$

  • Maximum:

$$ \max \tau=\frac23, $$

attained exactly on balanced binary expansions.