Dejemos que $p$ sea una permutación de $\mathbb{N}$ . Decimos que $p$ está acotado si existe $k$ para que $|p(i)-i| \le k$ para todos $i$ . Si $p$ está acotado, debe existir $M>0$ tal que $p(\{1,2,\ldots, M\}) = \{1,2,\ldots, M\}$ ? En caso afirmativo, ¿podemos vincular $M$ por una función de $k$ ?
Respuestas
¿Demasiados anuncios?
No. Define $p$ de la siguiente manera:
- $p(2i-1) = 2i+1$ para $i\ge1$ ,
- $p(2) = 1$ ,
- $p(2i+2) = 2i$ para $i\ge1$ .
Para un intervalo $[1, M]$ o bien $M$ o $M-1$ es impar, así que $p$ no conserva ningún intervalo. Pero $|p(i) - i| \le 2$ .
Tenga en cuenta que cuando $k = 1$ , ya sea $p(1) = 1$ o $p(1) = 2, p(2) = 1$ . Obsérvese también que la salida de un segmento inicial requiere que existan ciclos finitos, por lo que el ejemplo anterior muestra que la acotación no es una suposición lo suficientemente fuerte como para garantizar que existan ciclos finitos.
user8269
Puntos
46
El ejemplo de Qiaochu, como se ha señalado, no tiene ciclos finitos. En el otro extremo, he aquí una involución, es decir, un producto de transposiciones disjuntas: $$(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)$$ Nada se desplaza más de 4, y ningún segmento inicial se fija.
