Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?
share|improve this question
2  
I feel like the answers to question 2. are not yet complete, because of the following point: can the notion of limit of finite permutations be construed with respect to a natural topology on $\operatorname{Sym}(X)$? One natural topology on this set is the subset of the compact-open function space topology on all functions from $X$ to $X$, with $X$ given the discrete topology. I believe that this is also the topology of "pointwise convergence", i.e., such that a sequence of permutations $\sigma_n$ converges iff for all $x \in X$, $\sigma_n(x)$ is eventually constant. –  Pete L. Clark Mar 10 '10 at 0:26
    
Is the subset of permutations with finite support dense in $\operatorname{Sym}(X)$ in this topology? (I have to go to dinner, or I would think about this myself.) Note that Gjergi comes at the problem in a different way, essentially forcing this to be the case by taking the profinite completion. –  Pete L. Clark Mar 10 '10 at 0:28
    
Pete, I don't quite understand your worry. Am I missing something? The basic open sets in this topology are determined by the action of a permutation on a finite set, and clearly any such action that is compatible with a permutation is compatible with a finite permutation, so the finite permuations are dense. Also, the finite approximations of the product of transpositions in my answer clearly converge to the whole permutation, so one can see that every permutation is a limit of finite permutations this way. From my perspective, this question has been answered now several times over. –  Joel David Hamkins Mar 10 '10 at 1:24
    
@JDH: no, you are not missing anything. As I said, I was missing the explicit connection between the OP's "limit" and a topology on the set of permutations, which did not appear in your answer. As you say, a few minutes' thought shows that the permutations with finite support are dense in $\operatorname{Sym}(X)$. Because I was meeting a friend for dinner, I didn't want to be a few minutes late, so the comment I posted was not very insightful. It happens... –  Pete L. Clark Mar 10 '10 at 8:53
add comment

5 Answers

up vote 7 down vote accepted

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 fk(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.

share|improve this answer
    
This argument applies to permutations on any set X, not just on the natural numbers. You divide into disjoint cycles, and then represent each cycle as a product of transpositions as above. So altogether, you get an infinite well-defined product of transpositions which is equal to the given permutation. –  Joel David Hamkins Mar 9 '10 at 22:33
    
Note that if one takes only the outermost n terms in each factor of the product, then the resulting finite permutation has the right answer on all integers in (-n,n). Thus, the infinite cycle is the limit of the finite approximations to it. It follows that every permutation is the pointwise limit of a sequence of finite permutations. –  Joel David Hamkins Mar 10 '10 at 1:29
1  
[...(0 3)(0 2)(0 1)] is not a bijection! –  Guntram Mar 10 '10 at 14:11
    
Reiner, you correctly point out that not all infinite products of permutations give rise to infinite permutations. This is why I took pains in my answer to explain that my full product was well-defined and does define a permutation on the integers. (You have taken only part of my expression, and this part by itself does not define a permutation of the integers.) Nevertheless, that part of the expression is a bijection of the natural numbers with the positive integers, and the other factor is a bijection of the negative integers with the non-positive integers. Together, they make a permutation. –  Joel David Hamkins Mar 10 '10 at 18:24
add comment

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.

share|improve this answer
    
I am not sure if direct limit fully agree with naive one I was trying describe above. As I understand it is mainly a matter of embedding $S_{n-1}−>S_n$ You mention, and I presume this embedding may be called natural one. Are there any other embeddings which are interesting? –  kakaz Mar 10 '10 at 8:43
add comment

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.

share|improve this answer
    
Great answer. +1 –  Tony Huynh Mar 10 '10 at 14:57
add comment

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.

share|improve this answer
    
What does "limit" mean? –  aorq Mar 9 '10 at 20:56
    
No! I was wrong and accept it too fast! Suppose we define finite permutation that we have a1=(2,1,3,4,5,6...), a2 = (2,1,4,3,5,6...), a3 = (2,1,4,3,6,5,...) so obviously Your permutation is a limit of such sequence... –  kakaz Mar 9 '10 at 21:01
1  
A more interesting permutation than sigma would be the permuation tau such that tau(n) = n+2 if n is odd, and tau(n) = n-2 if n is even, except when n=2, where we have t(2) = 1. Thus, tau slides the odd numbers up, the even numbers down, and slips 2 into place at 1 to fill the hole. –  Joel David Hamkins Mar 9 '10 at 21:50
add comment

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$).

share|improve this answer
    
You need another condition to make an infinite product of transpositions a well-defined permutation. Consider $(1~2)(2~3)(3~4)(4~5)...$ What is sent to $1$? –  Douglas Zare Mar 9 '10 at 23:10
    
Thanks Douglas, I edited my answer. –  Tony Huynh Mar 10 '10 at 0:06
    
I guess 2 is sent to 1, but the pertinent question is what is 1 sent to? –  Tony Huynh Mar 10 '10 at 6:39
    
I read the permutations as acting on the other side. –  Douglas Zare Mar 10 '10 at 10:50
add comment

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.