2
$\begingroup$

I recently had as an assignment, to find cycles $\sigma,\tau\in S_{\mathbb{N}}$ (i.e. permutations over the naturals) such that $ord(\sigma)=ord(\tau)=2$ and $\tau\circ\sigma$ has order infinity. This is just a background; my question here is not to find the answer to this question, but rather a notational question (see bottom).

By intuition I was able to guess $\sigma=(0,1)\circ(2,3)\circ(4,5)\circ\ldots$ , $\tau=(1,2)\circ(3,4)\circ\ldots$, which, each being the composition of an arbitrary number of disjoint transpositions, have order 2.

To show that their composition is of order infinity (calling it $\rho$:
$\rho=\tau\circ\sigma=((1,2)\circ(3,4)\circ\ldots)\circ((0,1)\circ(2,3)\circ\ldots)$

Writing tau backwards (because composition commutes over disjoint cycles) gives
$\rho=\ldots\circ(3,4)\circ[(1,2)\circ(0,1)\circ(2,3)]\circ(4,5)\circ\ldots$ (note brackets)

Now noting that given a cycle of order $n$, which can be written as $X=(X_1,X_2,\ldots,X_n)$, and a transposition which is disjoint to X, say $A=(a,b)$, and taking a transposition containing one element of X and one element of A, e.g. $J=(X_1,a)$, and composing them all, the resulting cycle $J\circ X\circ A=(a,b,X_1,X_2,\ldots,X_n)$ which is of order $n+2$.

The bracketed expression above, $(1,2)\circ(0,1)\circ(2,3)$, is exactly such a collection of cycles, $(0,1)$ being disjoint from $(2,3)$ and $(1,2)$ containing one element of each, and thus $(1,2)\circ(0,1)\circ(2,3)$ is of order 4.

Calling $\sigma_n=(2n-2,2n-1)$, we can say that $\sigma=\sigma_1\circ\sigma_2\circ\sigma_3\circ\ldots$
$\tau_n=(2n-1,2n)$, we can call $\tau=\tau_1\circ\tau_2\circ\ldots$
Now call $\rho_1=\sigma_1=(0,1)$, and recursively $\rho_{n+1}=\tau_{n}\circ\rho_n\circ\sigma_{n+1}$

So $\sigma_1=(0,1)$, order 2.
$sigma_2=(1,2)\circ(0,1)\circ(2,3)$, order $ord((0,1))+2=4$.
In general, $ord(\sigma_n)=ord(\sigma_{n-1})+2=2n$.

In my proof for the assignment, I concluded with "Because $\rho$ is the result of infinitely many of these iterations which increase the order by 2 each time, we can conclude that the order of rho is infinity." I feel that the answer is here, but I have not expressed it in an adequate manner. How could I more formally express the notion that my sequence, $\rho_n$, does indeed "approach" or "converge" to the actual (infinite) cycle $\rho$ ?

$\endgroup$
  • $\begingroup$ Have you examined what iterations of $\rho$ do to some specific element, such as $1$? If you can show where it is after $n$ iterations, and it's not back at $1$ for any $n$, then the order of $\rho$ is infinite. $\endgroup$ – G Tony Jacobs Mar 14 '14 at 17:13
  • $\begingroup$ @GTonyJacobs Yes, I could; however I'm not so much interested in answering the original question using a different mehod, as correcting the notation/explanation of the method I constructed. $\endgroup$ – JustAskin Mar 14 '14 at 17:18
3
$\begingroup$

It's not really a good argument, because permutation groups have no well-behaved notion of convergence in general.

Hmm, scratch that. On further thought it seems perfectly well-behaved to say that $\sigma_1, \sigma_2, \sigma_3,\ldots$ converges iff for every $x$ there is an $N$ such that $\sigma_N(x)=\sigma_{N+1}(x)=\sigma_{N+2}(x)=\cdots$.

With this definition limits distribute over composition, but I don't think this is a standard notion, so you may have to include definitions and lemmas in your argument.

It's more of a problem that you seem to assume that limits commute with taking the order of a permutation. Consider the sequence $(\sigma_n)_n$ where $\sigma_n$ is a cyclic permutation of the elements $n$ through $2n-1$. Then $\sigma_n$ has order $n$, but the limit of the sequence is the identity permutation, which has order $1$! So the limit of a sequence of permutations of high order doesn't necessarily have high order itself.


It's better to look at $\tau\sigma$ as a finished whole and consider what it does to individual elements: Every even number $n$ is mapped to $n+2$, and every odd number $n$ is mapped to $n-2$, except that $1$ maps to $0$.

Since no amount of iterations of $\tau\sigma$ can make, say, 0, return to its original position, the permutation has infinite order.

$\endgroup$
  • $\begingroup$ Hm. What if I constructed some argument such as "For any natural number $m$, there exists a $\rho_n$ which has order greater than $m$." Then showed that the order of the real $\rho$ is always greater than the order of $\rho_n$ for any $n$. That would establish that the order of $\rho$ is greater than all natural numbers, without having to use "convergence" of $\rho_n$ to $\rho$ at all, just comparing orders. $\endgroup$ – JustAskin Mar 14 '14 at 17:24
  • 1
    $\begingroup$ @Justaskin: I was a bit too quick in rejecting your approach (see edit), but I don't think that particular suggestion will work. (See further edit). $\endgroup$ – Henning Makholm Mar 14 '14 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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