Permutation roots
13 hours ago
- A permutation σ has a square root τ if τ² = σ, meaning applying τ twice yields the same effect as applying σ once.
- Permutations can be represented as tuples, and composition is performed using a function that applies the second permutation first.
- A permutation σ always has square roots if it is itself a square of some permutation, but there can be multiple distinct square roots.
- A theorem states that a permutation σ has a square root if and only if every cycle of even length appears an even number of times in its cycle decomposition.
- The concept extends to cube roots and higher k-th roots of permutations.
- The probability that a random permutation of n elements has a k-th root can be computed via the coefficient of x^n in an infinite product involving the Mittag-Leffler function.
- For example, the probability that a permutation of 10 elements has a square root is 29/96.