# Functions which are the identity when applied repeatedly

Clearly the identity function $f =\text{id}$ satisfies $f^n = \text{id}$ for any $n \in \mathbb{N}$. However, there are also other functions with this property. For instance, with $n=2$ we have self-inverse functions like $x \mapsto 1-x$. For functions $f:\mathbb{R}\rightarrow\mathbb{R}$, we can use roots of unity e.g. $f(x) = \exp({\frac{2\pi i}{n}})\times x$.

I am interested in functions $f:\mathbb{N} \rightarrow \mathbb{N}$, and in particular $n=3$. Are there non-identity functions such that $f \;\circ f \;\circ f =\text{id}$? If so, how many functions of this type? Can you give an example, or an infinite family of examples?

I am not looking for rigorous proofs here, but just examples. Probably there is a name for functions of this type but I have searched and cannot find anything. This is not part of any formal teaching, but just an interesting question I came up with.

• You could consider permutations, since these are precisely bijections from a subset $\Omega$ of $\mathbb{N}$, and defining a permutation of a particular order in this case is easy. They can be extended to all of $\mathbb{N}$ by sending each value in $\mathbb{N}\backslash\Omega$ to itself, or by adding more $n$-cycles to the permutation if you want a permutation of order $n$. – Bill Wallis Apr 30 '18 at 13:39

## 2 Answers

Any partition of $\mathbb{N}$ into ordered triples gives a function $f$ that acts on each triple by cycling $(x, y, z) \mapsto (y, z, x)$ (and conversely, every function $f$ can be described fully by such a list of triples) This gives you an uncountably infinite family of functions. If you want an explicit function of this type, consider $$f(n) = \begin{cases} n - 2 & \text{n is a multiple of 3} \\ n+1 & \text{otherwise} \end{cases}$$

Such things are called functional $n^{th}$ roots (of the identity) which perhaps you already knew. I believe it's possible to show there are infinitely many such things and of fairly bizarre nature using Zorn's lemma (actually I guess you don't even need this).

One example is

$f(1) = 2, f(2) = 3, f(3) = 1$,

$f(4) = 5, f(5) = 6, f(6) = 4$

etc.