Group Theoretic Correspondence: A Subtle Discussion on Function Composition Among Bijections

Question

How is the following problem to be interpreted via the purview of group theory:

Let $f$ be a one-to-one function from $X=\{1,2,\dots,n\}$ onto $X$. Let $f^k=f\circ f\circ \cdots \circ f$ denote the $k$-fold composition of $f$ with itself.

1. Show that there are distinct positive integers $i$ and $j$ such that $f^i(x)=f^j(x)$ for all $x\in X$.
2. Show that for some positive integer $k$, $f^k(x)=x$ for all $x\in X$.

Answer 1

This sounds like homework, so I give just a hint for 1: you can consider the set of functions $\lbrace f^k \mid k=1,2,\dots\rbrace$. There are only finitely many functions from a finite set to itself. Now apply the Pigeonhole Principle. Part 2 should follow from 1.

Edit: I see that you are asking how to interpret this via group theory. The set of bijections of $X$ with itself is a group under composition.

Answer 2

Here is an answer from the point of view of group actions.

Let $G$ be a group and $X$ be a set. A left group action of $G$ on the set $X$ is an homomorphism of groups from $G$ to $S_X$, where $S_X$ is the set of all bijections from $X$ to itself where the group operation is $f_1 \circ f_2$, function composition, given two bijections $f_1$ and $f_2$. If $g \in G$ and $\varphi$ is the homomorphism, since $\varphi(g)$ is a bijection of $X$ to itself, we can consider $\varphi(g)(x)$. We usually denote this in a simpler manner by $g \cdot x$. This makes look the group action as some sort of left-$G$-multiplication on $X$. Because we require $\varphi$ to be an homomorphism, a left group action is also characterized in terms of this multiplication notation in a way that if $1$ is the identity of $G$,

• $\forall g,h \in G, \forall x \in X, \quad g \cdot (h \cdot x) = (gh) \cdot x$
• $\forall x \in X, \quad 1 \cdot x = x$.

(If we wanted a right group action, we would have requested instead $(x \cdot h) \cdot g = x \cdot (hg)$. Note that it is not just "putting the group element on the right" that changes, but more importantly that in both cases I apply $h$ first, then $g$ ; in a left group action this is the same as multiplying by $gh$, whereas in a right group action this is the same as multiplying by $hg$, hence there is a difference.)

I will consider only left group actions today ; right group actions have similar results and I wanna stick to one side.

The group $\mathbb Z$ acts on $S_n$ (which is the group of all permutations of $\{1,\dots,n\}$ and has size $n!$) by $k \cdot f = f^k$. (Note that this means the homomorphism $\varphi$ is $\varphi : \mathbb Z \to S_{S_n}$.) Since the order of $\varphi(k)$ divides the order of $S_{S_n} = n!!$, we know that $f^{n!!}(x) = x$ because $n!! \cdot f = 1$, where $1$ is the identity element in $S_{S_n}$. Therefore we also have $f^{2(n!!)} = 1 = f^{n!!}$ for any $f$.

Note that the 'bound' on the order $n!!$ is really ugly, but I used literally no theorems concerning group actions, so of course, if you don't think, the results are quite crude. In fact, we can think a bit more and reduce this bound by quite a lot.

Let $f \in S_n$ and $x \in X$. Look at the sequence $x = f^0(x),f(x) = f^1(x), f^2(x), \dots, f^k(x)$. By 1. (which we have proved without using the pigeonhole principle, but I guess the fact that I used the 'finite-order-ness' theorem uses it implicitly), choose $i,j$ such that $f^i(x) = f^j(x)$ and the distance $|i-j|$ is minimal. Assuming $i < j$, then $f^{j-i}(x) = x$ and $j-i$ is the smallest positive integer for which $f^k(x) = x$. Consider the subset of $\{1,\dots,n\}$ defined by $\{x,f(x),\dots,f^{k-1}(x)\} \overset{def}= Y_x$. For each $x \in X$, we can define such a set $Y_x$ ; it can be shown that $Y_{x_1} = Y_{x_2}$ if and only if $x_2 = f^m(x_1)$ for some $0 \le m < |Y_{x_1}|$, so that we have a partition of $X$ into those disjoint subsets $Y_x$. These sets $Y_x$ are called the orbits of the action of $f$, and $Y_x$ is called the orbit of $x$ by the action of $f$. (I mention 'of $f$' because there is a more general notion of orbit.)

This notion goes as follows : if $G$ acts on $X$, then we define the orbit of $x \in X$ by $$ \mathrm{Orb}_G(x) = \{ y \in X \, | \, \exists g \in G \text{ with } y = g \cdot x \}. $$ In some sense, this set explains 'where $x$ can go under the action of $G$'. The name 'orbit' should remind you of something like 'where does the earth go under the action of the sun, well, it travels on its orbit', hence the name. (I wouldn't say the name comes from this analogy, but I sure like it.)

Now there is another notion which is very related to that of an orbit, which is the stabilizer of an action on an element. Again, if $G$ acts on $X$, for every $x \in G$, define $$ \mathrm{Stab}_G(x) = \{ g \in G \, | \, g \cdot x = x \}. $$ It is not hard to show that $\mathrm{Stab}_G(x)$ is a subgroup of $G$, so that we can consider the set of equivalences classes (in general not a group) $G/\mathrm{Stab}_G(x)$. Note how $\mathrm{Stab}_G(x)$ measures how $G$ "does nothing to $x$" whereas the orbit measures "how much $G$ moves $x$". There is a beautiful duality given by those two notions and this is given by the formula called the orbit-stabilizer theorem, which says that $$ |\mathrm{Orb}_G(x)| \cdot |\mathrm{Stab}_G(x)| = |G|. $$ Using this relation, you can see that the size of the orbits always divide the order of the group $G$. In the case we had before, if we look at a particular permutation $f$, then since $f^{n!!} = 1$, we can consider the least positive integer $k$ such that $f^k = 1$ and look at the set $\langle f \rangle = \{ 1,f,\dots, f^{k-1}\} \subseteq S_n$. Note that $\langle f \rangle$ is actually a subgroup of $S_n$, hence is also a group itself, so we can speak of the action of $\langle f \rangle$ on $\{1,\dots, n\}$ given by $f \cdot i = f(i)$. (The corresponding homomorphism from $\langle f \rangle$ to $S_{\{1,\dots,n\}}$ is just the injection given by the inclusion of $\langle f \rangle$ into $S_n$.)

Now this means that by looking at the group $G = \langle f \rangle$, if we use the orbit-stabilizer theorem, for every $1 \le x \le n$, the orbit of $x$ divides the order of the group $\langle f \rangle$, which is precisely the order of $f$ ; hence the order of the orbits divide the order of $f$, hence so do their least common multiple. But if $d$ denotes this least common multiple, then $f^d$ must be the identity permutation, because $d$ is a multiple of each of the size of the orbits, and so must bring every point of each orbit back to itself, thus fixing every $x$ between $1$ and $n$. Therefore, the order of $f$ is the least common multiple of the size of its orbits, and that, in general, gives us a really, really sharper bound on the order of $f$ than the very crude $n!!$ bound.

Hope that helps,