A function $g:A\to A$ is called a $k$-th iterative root of another function $f:A\to A$ ($A$ an arbitrary set and $k\in\mathbb{N}$) iff $f=g^k$, where $g^k(x)=g\circ g\circ\ldots\circ g(x)=g(g(\ldots g(x)\ldots))$ means $k$-fold iterative application of $g$ to $x\in A$. There are dozens of papers on the existence and characterization of such iterative roots if $A=\mathbb{R}$ (http://www.reglos.de/lars/ffx.html) but hardly any for the case $A=\mathbb{Z}$ (at least I couldn't find much). Some results do exist though, but before I give a list let me formulate my question:
Let $f:\mathbb{Z}\to\mathbb{Z}$ and $k\in\mathbb{N}$.
1) Under which conditions does $f$ have $k$-th iterative roots?
2) If $f$ does have $k$-th iterative roots, how can the set of all of its $k$-th iterative roots be characterized/constructed?
Here are the things I found so far:
A) If $A$ is a finite set and $f$ is bijective (finite permutation) then both of the above questions are answered:
A practical attack on the root problem in braid groups - A. Groch, D. Hofheinz, R. Steinwandt, Section 3.3
On the number of mth roots of permutations - J. Leanos, R. Moreno, L. M. Rivera-Martinez, Section 3
B) If $A$ is an arbitrary set and $f$ is bijective at least question 1) is answered by a theorem of S. Lojasiewicz:
Iterative roots with big graph - L. Bartlomiejczyk, Section 2
So at least for bijective functions $f:\mathbb{Z}\to\mathbb{Z}$ one can decide if $k$-th iterative roots do exist.