5
$\begingroup$

Let $p$ be a permutation of $\mathbb{N}$. We say that $p$ is bounded if there exists $k$ so that $|p(i)-i| \le k$ for all $i$. If $p$ is bounded, must there exist $M>0$ such that $p(\{1,2,\ldots, M\}) = \{1,2,\ldots, M\}$? If so, can we bound $M$ by a function of $k$?

2 Answers 2

8

Nope. Define $p$ as follows:

  • $p(2i-1) = 2i+1$ for $i\ge1$,
  • $p(2) = 1$,
  • $p(2i+2) = 2i$ for $i\ge1$.

For an interval $[1, M]$ either $M$ or $M-1$ is odd, so $p$ preserves no interval. But $|p(i) - i| \le 2$.

Note that when $k = 1$, either $p(1) = 1$ or $p(1) = 2, p(2) = 1$. Note also that leaving an initial segment requires that there exist finite cycles, so the example above shows that boundedness is not a strong enough assumption to guarantee that finite cycles exist.

3

Qiaochu's example, as noted, has no finite cycles. At the other extreme, here's an involution, that is, a product of disjoint transpositions: $(1,5)(2,4)(3,7)\prod_{k=1}^{\infty}(8k-2,8k+2)(8k,8k+4)(8k+1,8k+5)(8k+3,8k+7)$ Nothing gets moved by more than 4, and no initial segment is fixed.