# Do bounded permutations of N leave an initial segment invariant?

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 you mean |p(i) - i|? – Qiaochu Yuan Jan 20 '11 at 0:39
Yes I did, thanks. – Dave Radcliffe Jan 20 '11 at 0:40

## 2 Answers

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.

-
Sorry, could you verify your formulas for $p$? I guess you intend $p(2i + 2) = 2i$ for $i \geq 1$, $p(2) = 1$ and $p(2i - 1) = 2i + 1$ for $i \geq 1$ [shifting everything even back by two (except two) and shifting everything odd forward by two]. – t.b. Jan 20 '11 at 0:55
@Theo: yes, sorry, just caught that mistake. – Qiaochu Yuan Jan 20 '11 at 0:56

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.

-