IMC 2025 · Day 1 · P5

For every $\tau \in T_n$ we need to prove that $\operatorname{ord}(\tau) \leqslant f(n) + n^{0.501}$ (if $n$ is large enough). Denote by $C(\tau)$ the set of elements $x \in [n]$ for which $\tau^k(x) = \underbrace{\tau(\dots\tau}_{k}(x)\dots) = x$ for some $k > 0$. It is immediate that $C(\tau)$ is a $\tau$-invariant set; let $\tau_c = \tau|_{C(\tau)}$, that is a permutation on $C(\tau)$.

Let $N$ be the order of this permutation $\tau_c$, clearly $N \leqslant g(n)$. Consider an arbitrary element $x \in [n] \setminus C(\tau)$. The sequence $x, \tau(x), \tau^2(x), \dots$ is eventually periodic, but not from the beginning, because $x \notin C(\tau)$.

Let $h(x) > 0$ be the minimal number for which $\tau^{h(x)}(x)$ is in the period; equivalently, this is the minimal number for which $\tau^{h(x)}(x) \in C(\tau)$. Let $R = \max\limits_{x \in [n] \setminus C(\tau)} h(x)$. Note that $\tau^R(x) = \tau^{R+N}(x)$ for all $x \in [n]$, since $\tau^R(x) \in C(\tau)$ for all $x \in [n]$. Therefore, $\operatorname{ord}(\tau) \leqslant N + R$. Thus, if $R < n^{0.501}$, we are done.

Now assume that $R \geqslant n^{0.501}$, that is, $h(x) \geqslant n^{0.501}$ for some $x \notin C(\tau)$. It yields $|C(\tau)| \leqslant n - n^{0.501}$. Consider the cycle lengths of the permutation $\tau_c$. We claim that there exists a prime number $p < n^{0.501}$ which does not divide any of these lengths. Indeed, otherwise the sum of cycle lengths of $\tau_c$ is not less than the sum of all prime numbers not exceeding $n^{0.501}$ (because each positive integer is not less than the sum of its prime divisors, that in turn follows from $ab \geqslant a + b$ for $a, b \geqslant 2$). But for large $n$, the number of prime numbers less than $n^{0.501}$ is at least $n^{0.5009}$ by some weak version of Prime Number Theorem (that also has many short proofs). Therefore, their sum exceeds $n$, contradiction.

Now we may consider the permutation $\tau_0 \in S_n$ which acts as $\tau_c$ on $C(\tau)$ and has a cycle of length $p$ on $[n] \setminus C(\tau)$. The order of $\tau_0$ is not less than $p \cdot N$, therefore $N \leqslant f(n)/p \leqslant f(n)/2$, and by the above argument we get $\operatorname{ord}(\tau) \leqslant N + R \leqslant f(n)/2 + n < f(n)$ for large $n$.