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?

misyjny76

misyjny76

Answered question

2022-09-20

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?

Answer & Explanation

Dillon Levy

Dillon Levy

Beginner2022-09-21Added 12 answers

Nope. Define 𝑝 as follows:
p ( 2 i 1 ) = 2 i + 1 for i 1,
p ( 2 ) = 1,
p ( 2 i + 2 ) = 2 i for i 1.
For an interval [ 1 , M ] either M or M 1 is odd, so p preserves no interval. But | p ( i ) i | 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.
Linda Peters

Linda Peters

Beginner2022-09-22Added 3 answers

Here's an involution, that is, a product of disjoint transpositions:
( 1 , 5 ) ( 2 , 4 ) ( 3 , 7 ) k = 1 ( 8 k 2 , 8 k + 2 ) ( 8 k , 8 k + 4 ) ( 8 k + 1 , 8 k + 5 ) ( 8 k + 3 , 8 k + 7 )
Nothing gets moved by more than 4, and no initial segment is fixed.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?