# Do there exist functions $f$ such that $f(f(x))=x^2-x+1$ for every $x$?

My question is on the existence (or not) of a function $f:\mathbb{R}\to\mathbb{R}$ which satisfy the equation: $$f(f(x))=x^2-x+1 \text{ for every }x\in\mathbb{R}$$

Supposing that such a map do exist I was able to prove until now that:

$f(x)=1$ iff $x=0$ or $x=1$

$f(x)\ne 0$ for every $x$

$f(x^2-x+1)=f^2(x)-f(x)+1$ for every $x$

$f(x)\ge\frac{3}{4}$ if $x\ge\frac{3}{4}$

For each $x$ it holds that $f(x)=f(1-x)$ or $f(x)+f(1-x)=1$

$f(x)<f(x^2-x+1)$ for all $x\in\mathbb{R}\setminus\{0,1\}$

• Nice observations. – Samrat Mukhopadhyay Feb 21 '15 at 9:13
• Why $f(x^2-x+1)=f^2(x)-f(x)+1$ for every $x$? In generally $f(x)$ is not linear function. – Leox Feb 21 '15 at 9:16
• @Leox, that is because $f(f(f(x)))=f^{2}(x)-f(x)+1$ – Samrat Mukhopadhyay Feb 21 '15 at 9:18
• For large $x$, $f(x)\approx x^{\sqrt2}$. – Yves Daoust Feb 21 '15 at 14:04
• @abel Please explain why $f(\frac{1}{2})=\frac{3}{4}$. Also, I am not very sure about the range observation (it is the reverse inclusion). – aly Feb 21 '15 at 14:17

There are infinitely many solutions to $f(f(x))=x^2-x+1$ for $f\colon\mathbb{R}\to\mathbb{R}$ and, in fact, infinitely many differentiable solutions. However, there is only one continuously differentiable solution.

First, let's start with the case where $f$ is assumed to be continuous. Then, we can say the following. I will write $g(x)=x^2-x+1$.

1. $f(1)=1$
2. $f$ is strictly increasing over $x\ge1/2$.
3. $x\le f(x)\le g(x)$ for all $x$.
4. $f(x)=f(1-x)$ for all $x$.
5. $f^\prime(1)=1$.

The first property is noted in the question, and does not require continuity. If $f(1)=a$ then we have $f(a)=f(f(1))=g(1)=1$. So, $g(a)=f(f(a))=a$ and, the only fixed point of $g$ is $a=1$.

Next, if $a\not=b\in[1/2,\infty)$ and $f(a)=f(b)$ then, $g(a)=f(f(a))=f(f(b))=g(b)$, so $a=b$. So, $f$ is one-to-one and continuous on this range, implying that it is either strictly increasing or strictly decreasing. We can rule out the decreasing case - as noted in the question, $f(x)\ge3/4$ for $x\ge3/4$. If $f$ was decreasing over $x\ge1/2$ then, as it is bounded below, it would be bounded. So, $g(x)=f(f(x))$ would be bounded, which it isn't. This proves the second statement.

Over $x > 1$ we have $f(x)\not=x$ (otherwise, $x$ would have to be a fixed point of $g$). Then, we either have $f(x) > x$ or $f(x) < x$ for all such $x$. We can rule out the second case, as it would imply that $g(x)=f(f(x))<x$ which is false. By a similar argument, $f(x) > x$ for all $x < 1$. Also, if $f(x) > g(x)$ for any $x$, then we would have $g(x)=f(f(x))\ge f(x) > g(x)$, which is a contradiction. This proves statement 3.

As noted in the question, $f(x)=f(1-x)$ or $f(x)=1-f(1-x)$ for all $x$. In particular, for $x < 1/2$, we can use the inequality $f(1-x) > f(1/2)\ge1/2$ to see that $f(1-x) > 1 - f(1-x)$. So, by continuity we either have $f(x)=f(1-x)$ for all $x\le 1/2$ or $f(x)=1-f(1-x)$ for all such $x$. We can rule out the second case, as it implies that $f(x) < 1/2$ for all $x < 1/2$, which would give the contradiction $g(x)=f(f(x))<1/2$. We have proved statement 4 for all $x\le 1/2$. For $x\ge1/2$ we can replace $x$ by $1-x$ to prove the statement.

Finally, for statement (4) we can apply (3) to get, $$\frac{(1+h)-1}{h}\le\frac{f(1+h)-f(1)}{h}\le \frac{g(1+h)-1}{h}$$ for all $h>0$. Both sides of this inequality tend to $1$ as $h\to0$. The same argument applies for $h < 0$, except that the inequalities are the other way round. So, $f^\prime(1)=1$.

We can now construct continuous solutions as follows. Pick any $a>1$ and set $b=g(a) > a$. Then, choose any $c\in(a,b)$. On the range $[a,c]$ we take $f$ to be any strictly increasing function with $f(a)=c$, $f(c)=b$. Extend to $(c,b]$ by taking $f(f(x))=g(x)$ for $x\in(a,c]$. The intervals $g^r([a,b])$ cover $(1,\infty)$ as $r$ runs through $\mathbb{Z}$, and we define $f(g^r(x))=g^r(f(x))$ to extend $f$ to all of $(1,\infty)$.

For differentiable $f$, we need to ensure that we choose differentiable $f\colon[a,c]\to[c,b]$ and line up the derivatives at the end points. Using $g^\prime(x)=f^\prime(f(x))f^\prime(x)$ at $x=a$, we require $g^\prime(a)=f^\prime(c)f^\prime(a)$.

We can construct $f$ on $[1/2,1)$ similarly. Set $a=1/2$ and $b=g(a) > a$. Choose any $c\in(a,b)$ and choose $f$ on $[a,c]$ to be strictly increasing with $f(a)=c$ and $f(c)=b$. We extend to $(c,b]$ as above, then use $f(g^r(x))=g^r(f(x))$ to extend to all of $[1/2,1)$.

Finally, we use (4) to extend to $x < 1/2$ and set $f(1)=1$ to complete the construction of $f$ on $\mathbb{R}$. The construction above can be done choosing $f$ to be differentiable in each of $[0,1/2)$ and $(1/2,\infty)$. As long as we choose the right-derivative of $f$ at $1/2$ to be $0$, then the extension to $x\le1/2$ satisfies $f^\prime(1/2)=0$. Finally, (5) implies that $f$ is differentiable at 1. However, in general $f$ will not be continuously differentiable at $1$.

Let me now show that there is a unique continuously differentiable solution. I'll concentrate on $x\ge1$, on which $g$ is strictly increasing. A similar argument applies to $x\in[1/2,1]$, and extends to all of $\mathbb{R}$ by (4).

First, we have $g^\prime(x)=f^\prime(f(x))f^\prime(x)$. Replacing $x$ by $f^{-1}(x)$ and $g^{-1}(x)$ gives \begin{align} f^\prime(x)&=\frac{g^\prime(f^{-1}(x))}{f^\prime(f^{-1}(x))},\\ f^\prime(f^{-1}(x))&=\frac{g^\prime(f^{-2}(x))}{f^\prime(f^{-2}(x))}. \end{align} Plugging the second equality into the first and using $g^{-1}=f^{-2}$ gives, $$f^\prime(x)=\frac{g^\prime(f^{-1}(x))}{g^\prime(f^{-2}(x))}f^\prime(f^{-2}(x))=\frac{g^\prime(g^{-1}(f(x)))}{g^\prime(g^{-1}(x))}f^\prime(g^{-1}(x)).$$ Iterating this identity gives, $$f^\prime(x)=f^\prime(g^{-r}(x))\prod_{k=1}^r\frac{g^\prime(g^{-k}(f(x))}{g^\prime(g^{-k}(x))}$$ for all $r\ge1$. If we now let $r$ go to infinity, then $g^{-r}(x)\to1$. If $f^\prime$ is continuous at $1$, then we can impose $f^\prime(g^{-r}(x))\to f^\prime(1)=1$ as $r\to\infty$. So, we get a differentiable equation for $f$, \begin{align} f^\prime(x)&=F(x,f(x)),\\ F(x,y)&=\prod_{k=1}^\infty\frac{g^\prime(g^{-k}(y))}{g^\prime(g^{-k}(x))}. \end{align} It can be seen that $F(x,y)$ is increasing in $y$. So, if $f$, $\tilde f$ were two continuously differentiable solutions and $\tilde f(x) > f(x)$ for some $x > 1/2$, then we see that $\tilde f^\prime(x) > f^\prime(x)$. It follows that $\tilde f(y) > f(y)$ for all $y > x$ and, therefore, $$g(x)=\tilde f(\tilde f(x)) > \tilde f(f(x)) > f(f(x))=g(x)$$ which is a contradiction, so there is at most 1 continuously differentiable solution.

This paper shows that in general your functional equation has no solution for all $x\in\mathbb{C}$.

• If I am computing correctly $\Delta(g)=0<1$, where $g(x)=x^2-x+1$. As a conclusion there are continuous solutions on $\mathbb{R}$. Am I right? – aly Feb 25 '15 at 19:05
• There are continuous solutions on $\mathbb{R}$. There are infinitely many of them. There are also infinitely many differentiable solution on $\mathbb{R}$. However, there is, I think, exactly one twice differentiable solution (I think - I'm just working out the details, and I'll post the answer). – George Lowther Feb 25 '15 at 22:17
• @GeorgeLowther Great. Thank you very much for the information. – aly Feb 25 '15 at 23:10
• Is this supposed to be an actual answer to the question ? – Gabriel Romon Mar 7 '15 at 17:43

Methods due to Jean Ecalle in the 1970's give the following: there is a real analytic solution for $x > 1.$ What makes it so hard is that the derivative at the fixpoint is exactly $1.$

There is also a real analytic solution for $0< x < 1.$

Where the two meet, the resulting joined function is continuous, differentiable, $C^1$ and actually $C^\infty,$ of Gevrey class.

The solution for $x > 1$ can be reflected across for $x < 0.$ Thus the curve is not $C^\omega$ at $0,$ either.

Carrying out the method is a big job. I did it for $f(f(x)) = \sin x.$ See my answer to my own question at https://mathoverflow.net/questions/45608/formal-power-series-convergence