Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
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 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.