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$?
Do bounded permutations of N leave an initial segment invariant?
5
$\begingroup$
combinatorics
group-theory
permutations
2 Answers
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.