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

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

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Dillon Levy
Nope. Define 𝑝 as follows:
$p\left(2i-1\right)=2i+1$ for $i\ge 1$,
$p\left(2\right)=1$,
$p\left(2i+2\right)=2i$ for $i\ge 1$.
For an interval $\left[1,M\right]$ either $M$ or $M-1$ is odd, so $p$ preserves no interval. But $|p\left(i\right)-i|\le 2$.
Note that when $k=1$, either $p\left(1\right)=1$ or $p\left(1\right)=2,p\left(2\right)=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.
###### Not exactly what you’re looking for?
Linda Peters
Here's an involution, that is, a product of disjoint transpositions:
$\left(1,5\right)\left(2,4\right)\left(3,7\right)\prod _{k=1}^{\mathrm{\infty }}\left(8k-2,8k+2\right)\left(8k,8k+4\right)\left(8k+1,8k+5\right)\left(8k+3,8k+7\right)$
Nothing gets moved by more than $4$, and no initial segment is fixed.