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\}$
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$.
- $f(1)=1$
- $f$ is strictly increasing over $x\ge1/2$.
- $x\le f(x)\le g(x)$ for all $x$.
- $f(x)=f(1-x)$ for all $x$.
- $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}$.
See also this, and this. They explain more about functional equations like your one.