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.



Definition of infinite permutations
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](http://www.ams.org/journals/tran/1983-277-02/S0002-9947-1983-0694380-4/)) 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](http://www.math.ucla.edu/~pak/papers/inf2.pdf). 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. 


