# How to define rational composition of functions, appropriately?

Let $f: X \rightarrow X$ and $f^{1/n}:X \rightarrow X$ such that $f$ is equal to $n$ times composition of $f^{1/n}$, i.e. $$f^{1/n} \circ f^{1/n}\circ \cdots \circ f^{1/n} = f$$ then $f^{1/n}$ is an $n$-th root of $f$.

Such a function may well not exist in general, and if it does, might not be unique. But is there a universal way to construct unique n-th roots for arbitrary $f$?

-
Just observe that it is even in general impossible to construct such a function for a linear map $f(z) = \alpha z$ from $\mathbb{C}$ to itself. This amounts to find an $n$-th root of $\alpha$, and except for special cases it is impossible to impose precedence to those roots. But sometimes we can define the unique $n$-th root of an operator. For example, if $A$ is a positive-definite $n\times n$ matrix, then we can define a unique square root of $A$, denoted as $\sqrt{A}$ such that it is again positive-definite. –  sos440 Jun 27 '12 at 22:42
Consider the logic behind your question: you know that such function need not exist or be unique; if we could construct an $n$th root for an arbitrary $f$ we could have constructed one for a function which does not have an $n$th root! –  Asaf Karagila Jun 27 '12 at 23:29
@Asaf: even if such a function need not exist or be unique, one can hope that in the cases where it does exist there might be a "functorial" choice in some appropriate sense. –  Qiaochu Yuan Jun 28 '12 at 0:31

No. For a complex number $a$, let $f_a : \mathbb{C} \to \mathbb{C}$ be defined by $z \mapsto az$. Then the nice $n^{th}$ roots of $f_a$ are given by $f_b$ where $b^n = a$ and there's no canonical way to choose a root of this polynomial.
You can ask your question more generally: if $M$ is a monoid, when is it possible to define rational powers of elements of $M$ in a nice way? Depending on what you mean by "nice way" this is equivalent to $M$ being a vector space over $\mathbb{Q}$ (switching to additive notation). If you only want to demand that $n^{th}$ roots are unique and in addition $M$ is an abelian group, this is equivalent to $M$ being torsion-free, and if you only want to demand that $n^{th}$ roots exist (and in addition $M$ is an abelian group), this is equivalent to $M$ being divisible.
All the previous answers dealt with uniqueness, and in general if such a map $f^{1/n}$ exists it need not be unique. It should be mentioned that existence can also fail. Consider $X=\{0,1\}$ and $f(x)=1-x$ with $n=2$. Since $f$ is surjective, so must be $f^{1/2}$. There are thus 2 possibilities for $f^{1/2}$, namely $f^{1/2}(x)=x$ or $1-x$. Neither of these work since either way $f^{1/2}(f^{1/2}(0))=0$.
Of course, for finite sets $X$, $|X| \ge 3$ or $|X|=2$ and $n$ even, a counting argument also works, namely that there are $|X|^{|X|}$ functions $f$, and exactly as many choices for $f^{1/n}$, and at least some of the functions that are not equal become equal after n-fold composition, so at least some of the functions can't have $n$th roots. –  Logan Maingi Jun 27 '12 at 23:20