Abstract:
{\bf Abstract} Isometries on formal power series over the finite field $\ff_2$ or on $2$--adic integers can be computed by invertible transducers on inputs from $\{0,1\}^\infty$. We consider the structural complexity of an isometry $f$, measured as {\it tree complexity} $T(f,h)$, $h$ the tree height [H.~Niederreiter, M.~Vielhaber, {\it J.~Cpx.}, 12 (1996)] and the computational complexity, as {\it number of bit operations} $B(f,n)$ needed for the first $n$ input / output symbols. We introduce the shift commutator $\SC(f) := \sigma^{-1}\circ f^{-1}\circ \sigma\circ f$ ($\sigma$ the shift on $\{0,1\}^\infty$) and show\ \ that $f\mapsto \SC(f)$ is a selfmap on the set of all isometries. We obtain the polynomial bounds $T(\SC(f),h) \leq T(f,h)^2 - T(f,h) + 2$ and $B(f,n) \leq n\cdot B(\SC(f),n))$, by simulating $f$ by $n$ copies of $\SC$. On the other hand, trying to bound $T(f,h)$ by $T(\SC(f),h)$ it turns out that {\it e.g.} for the isometries connected to the continued fraction expansion and to Collatz' 3N+1 conjecture, the function $f$ itself is structurally {\it exponentially} more complex than its $\SC(f)$. Hence simulating $f$ by $\SC(f)$ may yield sharper upper bounds for the bit complexity as can be inferred from $f$ alone. We finish with some dynamical aspects of isometries like orbits, ergodicity, preservation of measure.