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

I've been trying to find a definition of an infinite permutation on-line without much success. Does there exist a canonical definition or are there various ways one might go about defining this?

The obvious candidate I guess would be a bijection p : {1,2,...} -> {1,2,...} between the natural numbers. One might also try to use the Robinson-Schensted correspondence between permutations of length n and pairs of standard Young tableaux of size n. Then one would need a definition of infinite Young tableaux.

Another correspondence that might be used is between permutations and permutation matrices.

share|improve this question

5 Answers 5

up vote 7 down vote accepted

There are two closely related definitions which satisfy the properties you want.

First, consider the group $\Sigma_k$ of all bijections $\pi: \Bbb Z \to \Bbb Z$ such that $\pi(x+k) = \pi(x)+k$ for all $x$. Note that $S_k$ is a subgroup in $\Sigma_k$ - simply take any permutation of $\{1,\ldots,k\}$ and extend it periodically to all $x$. This group (introduced by Lusztig) is finitely generated and is closely related to affine Lie algebra $\widehat A_k$. The RSK algorithm does not exactly work here, but Lusztig does study the shape of Young diagrams (of what would be resulting two tableaux). The shape is a partition of $k$, and can be described using decreasing subsequences, extending Curtis Greene's theorem (I forgot if this is in Lusztig's paper or my own easy observation).

Second, a somewhat related definition is the group $\Phi_k$ of bijections $\pi: \Bbb N \to \Bbb N$ such that $\pi(x+k) = \pi(x)+k$ for all $x$ large enough. I studied this definition in this paper. This group $\Phi_k$ is also finitely generated. It is very suitable for RSK, which is not always, but sometimes invertible. The asymptotic shape I defined is essentially the same as Lusztig's. Neither I nor anyone else studied the infinite matrix extension. The infinite permutation version is already difficult enough.

share|improve this answer

The bijection definition is fine, although it's not a very nice group. One might also consider the group generated by all transpositions on {1, 2, ...}, which is the subgroup of all bijections that fix all but finitely many elements, and this group is likely to be much nicer; it's countable, for one thing.

Edit: I guess it's worth noting that as far as I can tell the term infinite symmetric group is used by mathematicians to refer to the subgroup I described.

share|improve this answer
It also still has a sign homomorphism to Z/2Z. –  Reid Barton Oct 18 '09 at 21:06
As well as a nice presentation, a good notion of cycle decomposition, and so forth. The set of all bijections from a countable set to itself, on the other hand, is terrible; one can imagine a bijection which, for example, encodes Chaitin's constant. –  Qiaochu Yuan Oct 18 '09 at 21:10
Thanks for your answer! –  Henning Arnór Úlfarsson Oct 18 '09 at 21:37
The full set of bijections on Z is quite a zoo, but it's still occasionally useful (e. g., for finding explicit constructions). Also, the concept of cycle decomposition is fine as long as you allow infinite cycles (which admittedly don't look very round). –  Darsh Ranjan Oct 29 '09 at 4:12
@Qiaochu: uncountably generated is the same as uncountable, since the free group on a countable set is countable. There are interesting groups out there without reasonable presentations, e.g. Lie groups. –  Pete L. Clark Jan 12 '10 at 11:25

A permutation on a set A (which need not be countable) is just a bijective map A -> A.

share|improve this answer

Fon-Der-Flaass and Frid have recently introduced and studied infinite permutations as linear orderings of countable sets with respect to a given "natural" linear ordering. That is, given a countable set X (usually ℕ or ℤ), an infinite permutation π of X is a linear ordering ≤π of X that may differ from the "natural" linear ordering of X. If we take X to be finite, then this definition coincides with usual definition of a finite permutation as a bijective map from X to itself.

share|improve this answer

You might also be interested in the "juggling patterns" of Knutson, Lam, and Speyer, defined here: http://arxiv.org/abs/1111.3660.

Also known as bounded affine permutations, these are a subset of the affine permutations that Lusztig introduced mentioned by Igor Pak. Namely, they are the affine permutations $\Sigma_n$ (so $\pi$ a permutation $\mathbb{Z} \to \mathbb{Z}$ with $\pi(i+n) = \pi(i)+n$) that also satisfy $i \leq \pi(i) \leq i + n$. They are related to total positivity and the positroid stratification. There is a nice way to visualize them as juggling patterns, where the number of balls being juggled is equal to the average $\frac{1}{n}\sum_{i=1}^{n}(f(i) -i)$.

share|improve this answer

Your Answer


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.