Decide whether or not there exists $f(f(x))=5x-\lfloor 5x\rfloor$

Question

Decide whether or not there exists $f;[0,1)\to [0,1)$ such $$f(f(x))=5x-\lfloor 5x\rfloor=\{5x\}$$

Today I suddenly thought of an interesting question, but I have not found any function of symbolic conditions so far.

Answer 1

Yes, there is such a function. (But I'm going to use the Axiom of Choice to show that, so I don't have any easy formula to offer - but I'm also going to use a general method that solves other problems too)

An easy way to see this is to throw out all the structure that is irrelevant to whether or not a functional square root exists. In particular, let us make the following definitions (which are not a standard definition or names):

A system is a pair $(S,f)$, where $S$ is a set and $f:S\rightarrow S$ is a function.

A system is square if it is of the form $(S,f\circ f)$, where $f:S\rightarrow S$ is a function.

Two systems $(S,f)$ and $(T,g)$ are isomorphic if there exists a bijection $\pi:S\rightarrow T$ such that $\pi\circ f = g\circ \pi$.

If we have two systems $(S,f)$ and $(T,g)$ with disjoint domains $S$ and $T$, we can define their union $(S,f)\cup (T,g)$ as a pair $(S\cup T,f\cup g)$, where $f\cup g$ is the function taking the values of $f$ in the component of $S$ and the values of $g$ in the component of $T$. Arbitrary unions can be defined similarly.

These definitions tell us to think about functions $S\rightarrow S$ as directed graphs with vertices $S$ and an edge $(x,f(x))$ for every $x\in S$ and to consider isomorphisms of those graphs. Here four examples, showing this graph for some functions with $S=\{0,1,2\}$, namely $f(x)=\max(x-1,0)$ and $f(x)=\min(x+1,2)$ and $f(x)=2$ and $f(x)=x+1\text{ mod }3$:

Note that the first two are basically mirror images of one another. The notion of isomorphism captures how these functions have the same structure, whereas the other two functions are different.

Now, we can show a lemma:

Let $(S,f)$ and $(T,g)$ be isomorphic by some map $\pi:S\rightarrow T$. Assume $S$ and $T$ are disjoint. Then, $(S,f)\cup (T,g)$ is square.

This is because we can define $h:S\cup T\rightarrow S\cup T$: $$h(x)=\begin{cases}\pi(f(x)) & \text{if }x\in S\\ \pi^{-1}(x) & \text{if }x\in T \end{cases}.$$ Then, for $x\in S$, we have that $$h(h(x))=h(\pi(f(x))=\pi^{-1}(\pi(f(x))=f(x).$$ For $x\in T$ we have $$h(h(x))=h(h(x))=h(\pi^{-1}(x))=\pi(f(\pi^{-1}(x)))=g(\pi(\pi^{-1}(x)))=g(x).$$ Thus, $h$ is a functional square root of $f\cup g$.

Pictorally, we can do an example. We could take a pair of isomorphic functions like the following, where the isomorphism is shown:

Then, we essentially weave back and forth between the isomorphic parts, in such a way that we take a step "forwards" each time. The result is a functional square root that looks like the following:

Let $\{(S_i,f_i\circ f_i)\}_{i\in I}$ be a collection of square systems with the $S_i$ pairwise disjoint. Then, $\bigcup_{i\in I}(S_i,f_i\circ f_i)$ is square.

This follows by noting that the functional square root of this system is $\bigcup( S_i,f_i)$.

Now, we can apply this to our given function $f(x)=5x-\lfloor 5x\rfloor$ by writing $f$ as the union of other functions. In particular, we define the following:

A component of a system $(S,f)$ is a set of the following form, for some $x\in S$: $$\langle x\rangle=\{y\in S:f^n(y)=f^m(x)\text{ for some }n,m\}.$$

These are exactly the components of the underlying directed graph. A system is always the union of its restrictions to each component. Moreover, each component is a directed graph with either zero or one directed cycles.

Now, we can finish by considering what the components of the given $f$ are. Note that every point in $[0,1)$ has exactly $5$ preimages under $f$. First, there are uncountably many components of the form $\langle x\rangle$ for irrational $x$, and none of these may contain a cycle, since $x,\,f(x),\,f^2(x),\ldots$ is not eventually periodic for irrational $x$. These components all consists of isomorphic systems corresponding to infinite bidirectional trees where every vertex has $5$ predecessors. We may use the axiom of choice to pair them up, and take the square root of every pair.

Then, for rational $x$, the component $\langle x\rangle$ must have a cycle, since $f$ never increases the denominator of a value. The component must therefore consist of an $n$-cycle, where each element of the cycle has $4$ preimages outside of the cycle, then everything outside of the cycle has $5$ preimages. The isomorphism class of this component only depends on $n$. Example components of this form are shown below:

Now, to finish, we just show that there are an even number of components with an $n$-cycle, since then we can pair these up and take their square root individually, then piece all the pairs back together to get a functional square root of the whole thing.

To see this, note that there are $5^n-1$ elements $x$ satisfying $f^n(x)=x$ - these are just those numbers of the form $\frac{c}{5^n-1}$ for $0\leq c < 5^{n}-1$. Then, we can use the Mobius inversion formula to get that there are $$\sum_{d|n}\mu(d/n)(5^d-1)$$ elements that are members of an $n$-cycle (and no smaller cycle), where $\mu(x)$ is the Mobius function, equalling $0$ if $x$ is not square-free, otherwise equalling $1$ if $x$ is a product of an even number of primes and $-1$ if it is a product of an odd number of primes.

The number of $n$ cycles is just this quantity over $n$, thus we can do our pairing argument exactly if $2n$ divides $\sum_{d|n}\mu(d/n)(5^d-1)$ for all $n$. Note that, except for $n=1$, this sum can also be written as $\sum_{d|n}\mu(d/n)\cdot 5^d$, since the constant terms will cancel.

Showing this final step is basically an exercise in number theory. If you look mod each prime power and group the given sum by pairs of the form $\{n/d,n/(pd)\}$ where $p$ does not divide $d$, the result falls out fairly easily by noting the exponent of the multiplicative group mod $p^n$. Then, we can repeat this trick on mod powers of $2$, noting that the multiplicative group mod $2^n$ only has exponent $2^{n-2}$ for $n\geq 2$, which let us get the result we want.

Answer 2

Yes, it it exists as the following example shows.The function $\{5x\}$ in the interval $[0,1)$ is explicitly defined by $$\begin{equation}\{5x\}=\begin{cases}5x\space \text{ for }0\le x\lt 0.2\\5x-1\space \text{ for }0.2\le x\lt 0.4\\5x-2\space \text{ for }0.4\le x\lt 0.6\\{5x-3}\space \text{ for }0.6\le x\lt 0.8\\5x-4\space \text{ for }0.8\le x\lt 1\end{cases}\end{equation}$$ so we can calculate an example of $f(x)=\sqrt5\space x+b$ such that $f(f(x))$ coincides with the funcion above. Calculation gives

$$\begin{equation}f(x)=\begin{cases} \sqrt 5\space x\quad\text{ for }0\le x\lt 0.2\\\\\sqrt 5\space x-\dfrac{\sqrt5-1}{4} \text{ for }0.2\le x\lt 0.4\\\\\sqrt 5\space x-\dfrac{(\sqrt5-1)}{2}\space \text{ for }0.4\le x\lt 0.6\\\\\sqrt 5\space x-\dfrac{3(\sqrt5-1)}{4}\space \text{ for }0.6\le x\lt 0.8\\\\\sqrt 5\space x-(\sqrt5-1)\space \text{ for }0.8\le x\lt 1\end{cases}\end{equation}$$ It follows $$\color{red}{f(f(x))=\{5x\}}$$ as it is easy to verify.