0

We say that the order of a permutation $\sigma$ is the smallest integer $k$ such that $\sigma^k$ is the identity permutation. That is, we repeatedly apply $\sigma$ until we get the identity permutation.

Suppose I have a set $S$ of permutations, all on the integers $[0, n)$. I am wondering what the minimal order possible for such a set is. By that I mean the smallest $k$ such that there exists a composition of $k$ permutations (allowing duplicates) from $S$ which forms the identity permutation.

An upper bound on this property is $\min_i \operatorname{order}(S_i)$. However, we can do much better. Consider $S = \{\sigma, \sigma^{-1}\}$, which would have $k = 2$ even if $\sigma$ and $\sigma^{-1}$ themselves have a much larger order.

Is there a well-known name for this property of a set of permutations? An algorithm for computing it? Better known bounds?

orlp
  • 10,508
  • 1
    The identity permutation has order $1$ which is minimal. – CyclotomicField Mar 11 '23 at 15:49
  • @CyclotomicField Yes, if the identity permutation is in $S$ we trivially have that the minimal order of the set is $1$. But the identity permutation might not be in $S$. – orlp Mar 11 '23 at 16:05
  • If $S$ is a generating set then this is the word problem for groups and is undecidable even if we only consider finite $S$. – CyclotomicField Mar 11 '23 at 16:19
  • @CyclotomicField I fail to see how it is undecidable. It is certainly decidable to see whether a permutation of $[0, n)$ is the identity: try all $n!$ inputs. We know the upper bound on k is $\min_i \operatorname{order}(S_i)$. Thus we can enumerate all $k$-products of $S$ for all $k$ up to that upper bound, and for each check if it's the identity permutation, giving a guaranteed terminating correct algorithm. – orlp Mar 11 '23 at 16:51
  • You should clarify that you mean $[0,n)$ to be natural number as it's different than the symmetric group on the real interval $[0,n)$. – CyclotomicField Mar 11 '23 at 17:06
  • @CyclotomicField My bad, I have edited that in. – orlp Mar 11 '23 at 17:55

0 Answers0