Bounded-displacement permutation of the natural numbers (source code)

= Bounded-displacement permutation of the natural numbers

A <permutation> $\sigma$ of $\mathbb N=\{1,2,\ldots\}$ has bounded displacement if some <nonnegative integer> $D$ satisfies
$$
|\sigma(j)-j|\leq D\qquad\text{for every }j\in\mathbb N.
$$
The same bound works at every position; each individual difference being finite would impose no restriction. Displacement zero gives the <identity permutation>.

For displacement at most one, every <permutation> is a collection of disjoint adjacent <transpositions> and fixed <points>. To prove this, inspect the smallest position $j$ not yet fixed or paired. Its image must be $j+1$, and the only still available possible preimage of $j$ is $j+1$. Thus these two positions are exchanged; continue inductively. Conversely, any such disjoint collection satisfies the bound. Independently choosing whether to exchange each pair $(2m-1,2m)$ gives an <uncountable set> of examples.

The <inverse function> has the same displacement bound: if $y=\sigma(j)$, then $|\sigma^{-1}(y)-y|=|j-\sigma(j)|$. If two <permutations> have bounds $D,E$, their <function composition> has bound $D+E$ by the <triangle inequality>. Thus bounded-displacement <permutations> form a <group> under <function composition>.