Permutation roots

Let σ be a permutation on n elements. If there is a permutation τ such that applying τ twice has the same effect on the list of elements as applying σ once, we say σ = τ² and τ is a square root of σ. If we let our n elements be the integers 0 through n − 1, then we can represent permutations by what they do to this list of numbers. In Python as a tuple of length n and compose permutations with the following function: import itertools def compose(sigma, tau): "Return the composition σ ∘ τ (apply τ first, then σ)." return tuple(sigma[j] for j in tau) We can always construct permutations that have square roots by squaring a permutation. If we run the following code tau = (3, 1, 4, 5, 2, 0) sigma = compose(tau, tau) we find σ = (5, 1, 2, 0, 4, 3), and by construction (3, 1, 4, 5, 2, 0) is a square root of &sigma, though it’s not the only one. The following code shows that σ has four square roots. import itertools def numroots(sigma): n = len(sigma) c = 0 for tau in…