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 = ^2 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 itertoolsdef 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 roots.

import itertoolsdef numroots(sigma): n = len(sigma) c = 0 for tau in itertools.permutations(range(n)): if sigma == compose(tau, tau): c += 1 return cprint( numroots(sigma) )print( numroots( (1, 2, 3, 4, 5, 0) ) )

It also shows that the rotation (1, 2, 3, 4, 5. 0) has no roots.

The function numroots has runtime proportional to n! and so it's not practical for large permutations. There is a theorem that says a permutation has a square root if and only if the number of cycles it has of every even length is even. See [1].

We can also define cubes and cube roots of permutations, and higher powers and roots.

How common is it for permutations to have square roots, or cube roots, etc.? If you pick a random permutation on n elements, what is the probability that it has a kth root?

This is a hard question in general, but it is equivalent to finding the coefficient of x^k in the infinite product

This is theorem 4.8.3 in [1]. This theorem was the motivation for writing about exp_q in the previous post.

Although the product is infinite, there's no need to compute terms in the product that only contribute powers of x higher than you're interested in. The following Mathematica code will compute the probability that a permutation on n elements has a kth root.

expq[x_, q_] := MittagLefflerE[q, x^q] p[n_, k_] := SeriesCoefficient[ Product[expq[x^m/m, GCD[m, k]], {m, 1, n}], {x, 0, n}]

So, for example, the probability that a permutation of 10 elements has a square root is 29/96.

[1] Herbert Wilf. Generatingfunctionology. Available online here.

The post Permutation roots first appeared on John D. Cook.