# Is there a name for the fact that an automorphism of a finite set produces periodical trajectories?

Let S be a finite set. f a bijection over S. If p is a point of S, I call "trajectory" of p the list ($$f^0(p)$$, $$f^1(p)$$, $$f^2(p)$$, $$f^3(p)$$... etc).

It appears obvious to me that under such conditions any trajectory would be periodical. Is that correct? Is there a name for this property?

• This is definitely correct, and if i had to give it a name I would call it the pigeonhole principle (en.wikipedia.org/wiki/Pigeonhole_principle) Oct 1 at 14:41
• @SamBallas: I had not seen your comment while writing an answer. If you want to post it as an answer then I'll delete mine. Oct 1 at 14:52
• @MartinR, don't worry, your answer is more detailed anyway Oct 1 at 14:58
• If you remove the assumption that $f$ is a bijection, then the trajectory would still become periodical eventually, albeit with possibly a finite number of steps before reaching the period. For instance a -> b -> c -> d -> e -> c -> d -> e -> c -> d ->...
– Stef
Oct 2 at 8:52
• @Stef: yes, but here I need "true" periodicity, not "eventual" periodicity. Oct 2 at 11:26

Let $$S$$ be a finite set and $$f$$ a permutation of $$S$$. The stated property (every trajectory under $$f$$ is periodic) is true. One proof is to show every permutation of a finite set has a decomposition into (a product of) disjoint cycles.

The term cycle decomposition (of a permutation) sometimes connotes this.

• "Cycle decomposition" is the term I'm familiar with, and is used in several texts (e.g. Dummit and Foote's Abstract Algebra) Oct 2 at 1:37

If $$n$$ is the cardinality of the finite set $$S$$ then among the $$n+1$$ elements $$f^0(p),f^1(p), f^2(p), \ldots,f^n(p)$$ there must be at least two which are equal, this is known as the pigeonhole principle.

So there are $$k, l$$ with $$0 \le k < l \le n$$ such that $$f^k(p) = f^l(p)$$, and since $$f$$ is an automorphism, it follows that $$p = f^{l-k}(p)$$, i.e. the trajectory is periodic.

• From what I read, this principle and the property I am talking about aren't exactly synonymous, although it can be derived from it. I'll let some time in case someone finds a specific name for the exact property, but if there isn't I am going to accept this answer. Oct 1 at 15:20
• This doesn't really seem to answer the question. The pigeonhole principle is certainly useful in showing that a permutation has a cycle decomposition, but arguably naming/describing the concepts of cycles and cycle decomposition is more useful for anyone asking this question. Oct 1 at 22:43

In general, for a function $$f$$ from a set $$S$$ to itself, we call the sets $$\{ x, f(x), f^{2}(x), f^{3}(x), \dots \}$$ orbits. In this special case, where $$S$$ is finite and $$f$$ is a bijection, we call them cycles. The idea is that if $$A \subseteq S$$ is a cycle of $$f$$, then $$f$$ permutes $$A$$ in a "cyclic" way -- if we were to put the elements of $$A$$ on a circle, evenly spaced an in the right order, the effect of applying $$f$$ would be to rotate the circle so that each element in $$A$$ went to the next one.

Now, it turns out that any finite permutation can be "decomposed into cycles" in a specific sense. If $$A_{1}, A_{2}, A_{3}, \dots A_{k}$$ are the cycles of $$f$$, we can factor $$f$$ into the form $$f_{1} \circ f_{2} \circ \dots f_{k}$$ where the $$f_{j}$$ are permutations on $$S$$ such that $$f_{j}(x) = \begin{cases} f(x) \ &\mathrm{if} \ x \in A_{j} \\ x \ &\mathrm{otherwise} \end{cases}.$$ That is to say, $$f_{j}$$ permutes the set $$A_{j}$$ just like $$f$$ does, and leaves everything else fixed.

This factoring is called the cycle decomposition of $$f$$. Pretty much any introductory book on abstract algebra will have a section on permutation groups / the symmetric group including a discussion of the cycle decomposition (e.g. Herstein's Abstract Algebra). As pointed out, the use of the pigeonhole principle is often used.

I would not know a name for this phenomenon, but it is a fundamental fact about actions of monogenous (i.e., generated by a single element) groups. A monogenous group is the set of integral powers $$g^i$$ of some element $$g$$, written $$\def\g{\langle g \rangle}\g$$; since in a group all elements must be invertible, there is no difficulty in defining $$g^i$$ for negative integral$$~i$$. Such a monogenous group is determined either by specifying an element $$g$$ of a (possibly much larger) group $$G$$, or directly by specifying an invertible operation (i.e., a bijection) $$g$$ on some set $$X$$. In the latter case, $$\g$$ comes with an action on $$X$$ (so $$h\cdot x$$ is a well defined element of $$X$$ for any $$h\in\g$$), while in the former case any action of $$G$$ restricts to an action of$$~\g$$.

The fundamental fact is that in this situation, and for any chosen $$x\in{X}$$, the orbit $$\{\,h\cdot x\mid h\in\g\,\}$$ is either infinite, in which case one has $$g^i\cdot x\neq g^j\cdot x$$ whenever $$i\neq j$$, or it has some finite positive number $$n$$ of elements, in which case $$g^i\cdot x=g^j\cdot x$$ if and only if $$i\equiv{j}\pmod{n}$$; in the latter case, the action of $$g$$ on the orbit of $$x$$ can be said to be purely periodic of period $$n$$.

The fact can be proved by studying the correspondence $$i\mapsto g^i\cdot x$$, which is an action of the (additive) group $$\Bbb Z$$, using the classification of the subgroups of $$\Bbb Z$$ (which are $$\{0\}$$ and the infinite subgroups $$n\Bbb Z$$ of all mulitples of $$n$$, for any integer $$n\geq1$$), by applying this classification to the stabiliser subgroup $$\{\,i\in\Bbb Z\mid g^i\cdot x=x\,\}$$ of$$~x$$.

This fact can be applied to $$\g$$ itself, which is equal to its orbit of the neutral element $$g^0$$ of the group; therefore either all powers of $$g$$ are distinct, or there is some positive integer$$~k$$, called the order of$$~g$$, such that $$g^i=g^j$$ if and only if $$i\equiv{j}\pmod{k}$$. In the latter case the powers of $$g$$ "cycle" around with period $$k$$, and the group $$\g$$ is called cyclic of order$$~k$$; in English parlance the term cyclic is also used in the former case (so cyclic is synonymous with monogenous, and the latter case needs "finite cyclic" to be singled out). An infinite monogenous group can have orbits of any finite size, as well as infinite orbits, but a cyclic group of order$$~k$$ can only have orbits of size dividing$$~k$$. If (as in your case) $$X$$ is a finite set, then any orbit by a monogenous group of course has to be finite, and is therefore periodic.