Increasing the "shuffling distance" by iterating a permutation $\varphi: \omega \to \omega$

Question

Motivation. I was wondering about the following when playing a card-shuffling game with my elder son.

If $\varphi: \omega \to \omega$ is a bijection, we define the shuffling distance of $\varphi$ by $$sh(\varphi) = \min\{|n-\varphi(n)| : n \in \omega\}.$$ Let $\varphi^{(1)}=\varphi$ and $\varphi^{(k+1)} = \varphi\circ\varphi^{(k)}$ for all integers $k \geq 1$.

What is an example of a bijection $\varphi: \omega \to \omega$ such that $sh(\varphi^{(k+1)}) > sh(\varphi^{(k)})$ for all integers $k\geq 1$?

Answer 1

There's indeed an example of such a function.

Given a an infinite subset $I\subset\omega$, call indexation of $I$ the unique increasing bijection $\omega\to I$. If $(x_n)$ is its indexation, define $f_I$ the permutation of $I$, mapping $x_1\mapsto x_0$, $x_{2n+1}\mapsto x_{2n-1}$ ($n\ge 1$), $x_{2n}\mapsto x_{2n+1}$ ($n\ge 0$). Hence $f_I^k$ maps $f_{2n+1}\mapsto f_{2n+1-2k}$ for $n\ge k$, maps $f_{2n+1}\mapsto f_{2k-2n-2}$ for $0\le n\le k-1$, and maps $f_{2n}\mapsto f_{2n+2k}$.

Say that a subset $I$ of $\omega$ is "good" if it is infinite, and, $(x_n)$ being its indexation, it satisfies $x_n>2x_{n-1}$ for all $n\ge 1$. If $I$ is good, then $\min_n|x_n-f_I^k(x_n)|=x_{k+1}-x_k$, and $(x_{k+1}-x_k)$ is strictly increasing.

Given a partition $\mathcal{P}$ of $\omega$ into good subsets, let $f$ be the permutation of $\omega$ whose restriction to $I$ is $f_I$ for every $I\in\mathcal{P}$. Then $(\min_n|x_n-f^{k}(x_n)|)_k$ is strictly increasing. The existence of such a partition is obtained by a straightforward induction.