Functional Reverse-Engineering

Define $g : \mathbb R \to \mathbb R$ by $g(x) = x^2 - x + 1 = (x-1/2)^2 + 3/4$ .

Problem 1. Suppose there exists a function $f : \mathbb R \to \mathbb R$ such that $f \circ f = g$ . Evaluate $f(1)$ and $f(0)$ .

(Click for Solution)

Solution. We first observe that $(f \circ f)(1) = g(1) = 1$ . Applying $f$ on both sides,

$\begin{aligned}f((f \circ f)(1)) &= f(1) \\ (f \circ f)(f(1)) &= f(1) \\ f(1)^2 - f(1) + 1 &= f(1) \\ (f(1)-1)^2 &= 0.\end{aligned}$

Hence, $f(1) = 1$ . Similarly, $(f \circ f)(0) = g(0) = 1$ . Applying $f$ on both sides yields

$f(0)^2 - f(0) + 1 = 1 \quad \iff \quad f(0)(f(0) - 1) = 0.$

Hence, $f(0) = 0$ or $f(0) = 1$ . The former yields

$0 = f(0) = f(f(0)) = g(0) = 1,$

a blatant contradiction.

Problem 2. Define the sequence $\{x_n\}$ by $x_0 := 1/2$ , $x_1 := 5/8$ , and $x_{n+2} := g(x_n)$ for integers $n \geq 0$ . Prove that $x_n \to 1$ .

(Click for Solution)

Solution. We first make a few observations:

$g$ is continuous.
$g$ is increasing on $[1/2, \infty)$ .
$g([1/2, 1]) = [3/4, 1]$ .

Thus, $g|_K$ is bijective to its image for any $K \subseteq [1/2, \infty)$ . By construction, $x_0 \leq x_1 \leq 3/4 = g(x_0) = x_2$ . Furthermore, for $n \geq 0$ ,

$x_{n+2} = g(x_n) \leq g(x_{n+1}) = x_{n+3}.$

Thus, by induction, $\{x_n\}$ is an increasing sequence. Since $\{x_n\}$ is bounded above by $1$ , by the monotone convergence theorem, $x_n \to r$ for some $r \in \mathbb R$ . By the continuity of $g$ ,

$\displaystyle r = \lim_{n \to \infty} x_{n+2} = \lim_{n \to \infty}g(x_n) = g \left( \lim_{n \to \infty} x_n \right) = g(r).$

But we have $g(r) = r \iff r = 1$ , so that $x_n \to 1$ , as required.

Problem 3. Construct a continuous function $f: \mathbb R \to \mathbb R$ such that $f \circ f = g$ .

(Click for Solution)

Solution. We follow the construction in this post by user pco. We will construct $f$ on the following subsets of $\mathbb R$ :

$[1/2, 1)$ ,
$\{1\}$ ,
$(1, \infty)$ ,
$(-\infty, 1/2)$ .

For the interval $[1/2, 1)$ , define the sequence $\{x_n\}$ according to Problem 2. Let $p_{a, b} : [0, 1) \to [a, b)$ denote the canonical continuous bijection defined by

$\displaystyle p_{a,b}(t) = a + t \cdot (b-a).$

Then define the sequence $\{h_n\}$ of bijections $h_n : [x_n, x_{n+1}) \to [x_{n+1}, x_{n+2})$ by

$h_0 = p_{x_1, x_2} \circ p_{x_0,x_1}^{-1},\quad h_{n+1} = g|_{[x_n, x_{n+1})} \circ h_n^{-1}.$

Thus, for $x \in [1/2, 1)$ , we define

$f(x) = h_n(x) \quad \iff \quad x \in [x_n, x_{n+1}).$

By construction,

$\begin{aligned} (f \circ f)(x) &= f(f(x)) \\ &= f(h_n(x)) \\ &= h_{n+1}(h_n(x)) \\ &= (h_{n+1} \circ h_n)(x) = g(x).\end{aligned}$

Thus, we have constructed $f$ on $[1/2, 1)$ . Since we require $f$ to satisfy

$f(f(x)) = x^2 - x + 1,$

Problem 1 stipulates that $f(1) = 1$ . Furthermore, this definition allows $f$ to be continuous by Problem 2. To define $f$ on $(1, \infty)$ , we first define $f$ on $[2, \infty)$ . Define the sequence $\{y_n\}$ similarly to $\{x_n\}$ as in Problem 2, except that we now have the initial conditions $y_0 := 2$ and $y_1 := (2+g(2))/2 = 5/2$ .

Just like before, $y_0 \leq y_1 \leq y_2$ and since $g$ is increasing, $\{ y_n \}$ is an increasing sequence by the argument in Problem 2. For divergence to infinity, we recall that

$y_{n+2} = y_n \cdot (y_n - 1) + 1 \geq y_n + 1.$

If $y_n$ converges to a limit, then $0 \geq 1$ , a blatant contradiction. Thus, $\{y_n\}$ diverges. Since $\{y_n\}$ is strictly increasing, it is unbounded. Thus, $y_n \to \infty$ .

Defining $\{ h_n \}$ similarly as in the $[1/2, 1)$ case, we define

$f(x) = h_n(x)\quad \iff \quad x \in [y_n, y_{n+1})$

and deduce $f \circ f = g$ on that domain too.

We next define $f$ on $(1, 2)$ . Define the sequence $\{z_n\}$ by $z_0 := 5/2$ , $z_1 := 2$ , and $z_{n+2} := g|_{(1,5/2)}^{-1}(z_n)$ . By a similar proof as in Problem 2, since $z_2 \leq z_1 \leq z_0$ and $g_{(1,2)}^{-1}$ is decreasing, $z_n$ decreases to $1$ .