infinite permutations

Question

This question is related to this one: Continued fractions using all natural integers. Suppose we have the set of natural numbers $N$ with order and we perform permutation on it. So we obtain the same elements with different order. Suppose we describe such permutations by usual notation when (1,2,3,4,5...) means identity permutation. Then lets say that permutation denoted by (1,3,2,4,5,6...) ( from the 4th place there is list of natural numbers in usual order) is finite because it only mixes numbers 1,2,3 -> 1,3,2 and for remaining elements it is identity permutation. As I find here there is definition of such objects, namely a few possibilities as states the answer of Qiaochu Yuan.

Questions:

1. Are infinite permutation decomposable into cycles? Transpositions?
2. Is possible to find such permutation of natural numbers that it cannot be a limit of finite permutations?

Answer 1

The first thing to notice is that infinite permutations may have infinite support, that is, they may move infinitely many elements. Therefore, we cannot expect to express them as finite compositions of permutations having only finite support.

But if we allow (well-defined) infinite compositions, then the answer is that every permutation can be expressed as a composition of disjoint cycles and also expressed as a composition of transpositions. So the answer to question 1 is yes, and the answer to question 2 is no.

To see this, suppose that f is a permutation of ω. First, we may divide f into its disjoint orbits, where the orbit of n is defined as all the numbers of the form f^k(n) for any integer k. The action of f on each of these orbits commute with each other, because the orbits are disjoint. And the action of f on each such orbit is a cycle (possibly infinite). So f can be represented as a product of disjoint cycles. For the transposition representation, it suffices to represent each such orbit as a suitable product of transpositions. The finite orbits are just finite cycles, which can be expressed as a product of transpositions in the usual way. An infinite orbit looks exactly like a copy of the integers, with the shift map. This can be represented in cycle notation as (... -2 -1 0 1 2 ...). This permutation is equal to the following product of transpositions:

• (... -2 -1 0 1 2 ...) = [(0 -1)(0 -2)(0 -3)...][...(0 3)(0 2)(0 1)]

I claim that every natural number is moved by at most two of these transpositions, and that the resulting product is well-defined. On the right hand side of the equality, I have two infinite products of transpositions. Using the usual order of product of permutations, the right-most factor is first to be applied. Thus, we see that 0 gets sent to 1, and subsequently fixed by all later transpositions. So the product sends 0 to 1. Similarly, 1 gets sent to 0 and then to 2, and then unchanged. Similarly, it is easy to see that every non-negative integer n is sent to 0 and then to n+1 as desired. Now, the right-hand factor fixes all negative integers, which then pass to the left factor, and it is easy to see that again -n is sent to 0 and then to -n+1, as desired. So altogether, this product is operating correctly. An isomorphic version of this idea can be used to represent the action of any infinite orbit, and so every permutation is a suitable well-defined product of transpositions, as desired.

Thus, the answers to the questions in (1) are yes, and the answer to question (2) is no.

Answer 2

Every permutation decomposes $\mathbb N$ into orbits. You can arrange these into a cycle decomposition if you allow infinite cycles.

I'm not comfortable with all infinite products, particularly ones which do not define permutations at all times.

One notion of an infinite product of transpositions is a limit under pointwise convergence. That is, say $\pi$ is an infinite product of transpositions if there is a sequence of permutations $e=\pi_0, \pi_1, \pi_2...$ which converges pointwise to $\pi$ so that $\pi_{n+1} \pi_n^{-1}$ is a transposition.

Every permutation is an infinite product of transpositions: Define $\pi_n = \bigg(\pi(n) ~~ \pi_{n-1}(n)\bigg)\pi_{n-1}.$ Then $\pi_n$ agrees with $\pi$ on $\{1,...,n\}$, so $\pi_0, \pi_1, \pi_2, ... \to \pi$.

Therefore, every permutation is a pointwise limit of what you called finite permutations.

Answer 3

G. Olshanski calls the harmonic analysis of noncommutative groups with infinite dimensional dual space an important "chapter of representation theory". And some of the main objects you see in this chapter are the infinite symmetric group $S(\infty)$, the infinite bisymmetric group $G=S(\infty)\times S(\infty)$ and the space of virtual permutations $\mathfrak{S}$, which is a compactification of $S(\infty)$ (It is not a group but it is a $G$-space).

$S(\infty)$ is the group of all finite permutations of $\mathbb N$. In other words, since each finite symmetric group $S_n$ acts on $[n]=\{1,2,\dots,n\}$, and the stabilizer of $n$ is canonically isomorphic to $S_{n-1}$ you get an embedding $S_{n-1}\to S_n$ and define $S(\infty)$ as the direct limit with respect to these embeddings.

Similarly you can define projections $S_n\to S_{n-1}$ by removing $n$ from the cycle that contains it and take the projective limit. This will give you $\mathfrak S$, which is equipped with the projective limit topology, and is a totally disconnected compact topological space. The Haar measure of $S_n$ passes on to $\mathfrak S$ and is the unique measure invariant under the action of $G$. This is just an introduction to what you can find in this survey.

I felt like mentioning this because you didn't define what you meant by limit or permutation in your question, and I am giving a possible answer in terms of objects that appear frequently in literature. If this is satisfactory to you then the answer to your second question is no, because the image of $S(\infty)$ is dense in $\mathfrak S$. Note that one can still talk about properties of "permutations" in $\mathfrak S$, such as the distribution of cycle lengths etc.

Answer 4

The permutation $\sigma$ with $\sigma(n) = n+1$ if $n$ is odd and $\sigma(n) = n-1$ if $n$ is even -- which you could represent as the infinite sequence of integers $(2,1,4,3,6,5,\ldots)$ -- is not a limit of finite permutations.

Added after the first two comments: it's been asked what I meant. I was thinking something like this: there does not exist a sequence $\sigma_1, \sigma_2, \sigma_3, \ldots$ with $\sigma_k \in S_k$, such that $\sigma_k$ is the restriction of $\sigma$ to $\{1, 2, \ldots, k \}$ for all but finitely many $k$. This notion of "limit" is not useful in any obvious way, though.

Answer 5

For (1), the answer for finite permutations (as defined by the OP) is clearly yes. This of course is a characterization of finite permutations. A permutation is finite if and only if it is the product of a finite number of cycles.

For non-finite permutations, we'll have to use an infinite product of cycles or transpositions to make sense of (1). So we'll need to define what we mean by this. A reasonable definition of an infinite product of cycles is that the product should be well-defined if we read it from right to left.

Let me explain what this means. By reading an infinite product from right to left we may regard the set of cycles in the product to have a certain order type $\alpha$. Note that $\alpha = \prod_{i=1}^\beta \alpha_i$, where each $\alpha_i \leq \omega$ and $\beta \leq \omega$.

So, for each $\alpha_i$ in $\alpha$ and for each $n \in \mathbb{N}$ we first insist that the sequence $f_1(n), f_2(n), \dots $ is eventually constant where $f_i$ is the product of the first $i$ cycles which appear in $\alpha_i$. By convention this is satisfied if $\alpha_i$ is finite. With this condition, each $\alpha_i$ induces a function $g_i: \mathbb{N} \to \mathbb{N}$. The final condition is that for each $n$ the sequence $g_1(n), g_2g_1(n), g_3g_2g_1(n), \dots, $ is eventually constant.

With this definition the permutation $\sigma$ given by Michael can be written as $...(78)(56)(34)(12)$ which is well-defined, with $\alpha=\omega$. Indeed, Douglas' excellent answer shows that any permutation can be written in this way (with $\alpha=\omega$).