7
$\begingroup$

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.

$\endgroup$

5 Answers 5

8
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ It also still has a sign homomorphism to Z/2Z. $\endgroup$ Oct 18, 2009 at 21:06
  • $\begingroup$ 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. $\endgroup$ Oct 18, 2009 at 21:10
  • 2
    $\begingroup$ 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). $\endgroup$ Oct 29, 2009 at 4:12
  • 1
    $\begingroup$ It does include an isomorphic copy of every countably generated group, which probably destroys any hope of such. :-) $\endgroup$ Oct 30, 2009 at 0:19
  • 4
    $\begingroup$ @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. $\endgroup$ Jan 12, 2010 at 11:25
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.