TAOCP 4.5.2 Exercise 32
No.
Section 4.5.2: The Greatest Common Divisor
Exercise 32. [**] [M42] Is there a unique continuous function $G(x)$ that satisfies (36) and (37)?
Verified: no
Solve time: 2m10s
No. Equations (36) and (37) do not determine a unique continuous function.
Let
$$ (Tf)(x)=\sum_{k=0}^\infty 2^{-k-1}f!\left(\frac1{1+2^k x}\right). $$
Equation (36) is the fixed-point equation $G=TG$. The operator $T$ maps $C[0,1]$ into itself, since
$$ |(Tf)(x)|\le\sum_{k=0}^\infty 2^{-k-1}|f|=|f|, $$
and the series converges uniformly.
However, $T$ is not a strict contraction in the supremum norm. In fact,
$$ |Tf-Tg| \le \sum_{k=0}^\infty 2^{-k-1}|f-g| = |f-g|, $$
and equality can occur. Therefore the Banach fixed-point theorem does not apply.
Indeed, uniqueness fails. If $G$ satisfies (36), then so does $cG$ for every constant $c$. Since (37) is homogeneous,
$$ (cG)(0)=cG(0)=0. $$
Thus every scalar multiple of a solution is again a solution. In particular, the zero function satisfies both conditions:
$$ G(x)\equiv0. $$
Consequently, uniqueness can hold only if the zero function is the only continuous solution.
But equation (36) imposes only homogeneous linear conditions, and no normalization such as $G(1)=1$ is given. Hence the problem does not specify a unique continuous function. This completes the proof.
∎