Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
