4
$\begingroup$

Start with a permutation $s_0$ of the numbers $(1,\ldots,n)$, e.g., for $n=10$, $s_0=(8,2,1,6,9,7,10,5,4,3)$. Form $s_1$ by using the numbers in $s_0$ as indices into $s_0$. So $s_1$ is composed of the $8$-th element of $s_0$, followed the $2$-nd element, followed by the $1$-st element, followed by the $6$-th element, etc., yielding $s_1 = (5,2,8,7,4,10,3,9,6,1)$ Continuing in this manner, $s_{i+1}=s_i[s_i]$, we reach a cycle of length $6$: $s_1 = s_7$: \begin{eqnarray} s_0 &=& (8,2,1,6,9,7,10,5,4,3)\\ s_1 &=& (5,2,8,7,4,10,3,9,6,1)\\ s_2 &=& (4,2,9,3,7,1,8,6,10,5)\\ s_3 &=& (3,2,10,9,8,4,6,1,5,7)\\ s_4 &=& (10,2,7,5,1,9,4,3,8,6)\\ s_5 &=& (6,2,4,1,10,8,5,7,3,9)\\ s_6 &=& (8,2,1,6,9,7,10,5,4,3)\\ s_7 &=& (5,2,8,7,4,10,3,9,6,1) \end{eqnarray} For $n=10$, cycles of lengths $1,2,3,4,6$ occur, but (apparently) no other lengths. Call this list the cycle-length spectrum for $n$. My question is:

Q. What explains the cycle-length spectrum for a given $n$?

Here is a bit of empirical data: $$\left[ \begin{array}{cc} n & \textrm{cycle lengths}\\ - & ------ \\ 2 & (1) \\ 3 & (1,2) \\ 4 & (1,2) \\ 5 & (1,2,4) \\ 6 & (1,2,4) \\ 7 & (1,2,3,4) \\ 8 & (1,2,3,4) \\ 9 & (1,2,3,4,6) \\ 10 & (1,2,3,4,6) \\ 11 & (1,2,3,4,6,10) \\ 12 & (1,2,3,4,6,10,12) \\ 13 & (1,2,3,4,6,10,12) \\ 14 & (1,2,3,4,6,10,12) \\ 15 & (1,2,3,4,6,10,12) \\ 16 & (1,2,3,4,6,10,12,20) \\ 17 & (1,2,3,4,6,8,10,12,20) \\ 18 & (1,2,3,4,6,8,10,12,20,30) \\ 19 & (1,2,3,4,6,8,10,12,18,20,3 0) \\ 20 & (1,2,3,4,6,8,10,12,18,20,3 0) \\ 21 & (1,2,3,4,6,8,10,12,18,20,3 0) \\ 22 & (1,2,3,4,6,8,10,12,18,20,3 0) \\ 23 & (1,2,3,4,6,8,10,11,12,18,2 0,30,60) \end{array} \right]$$ The cycle spectrum for $n$ is a subset of the cycle spectrum of $n+1$. Even cycle lengths dominate, but some cycles have odd length, e.g., $n=8$, $(7,4,8,5,1,6,3,2)$ leads to a cycle of length $3$, and $n=23$ includes cycles of length $11$. So perhaps cycles of length $5$ occur for some $n$...

$\endgroup$
  • 2
    $\begingroup$ Maybe it is related to oeis.org/A067128 ? $\endgroup$ – Per Alexandersson Nov 10 '15 at 15:28
  • $\begingroup$ On another note, it is clear that if $a$ and $b$ appear in some cycle spectrum, so does some number between $gcd(a,b)$ and $lcm(a,b)$. $\endgroup$ – Per Alexandersson Nov 10 '15 at 15:42
6
$\begingroup$

Let's look at your permutation $s_0 = (8, 2, 1, 6, 9, 7, 10, 5, 4, 3)$. We can rewrite this in the cycle notation as (1, 8, 5, 9, 4, 6, 7, 10, 3, 1) (2) and so we can see that it has order 9 - that is, $s_0^9 = 1$.

Now $s_i = (s_0)^{2^i}$, as observed by user78588. In particular $s_6 = (s_0)^{64} = (s_0)^{7\times 9 +1} = s_0$, so 6 is in the cycle spectrum of 10. In general, if there are permutations of order $k$ in $S_n$, then the smallest $j$ such that $k$ divides $2^j-1$ will be in the cycle spectrum of $n$.

To answer your question of "why does iterated indexing avoid cycles of length 5": to get a cycle of length 5 we'd have to have a permutation $s_0$ with order dividing $2^5-1 = 31$, but not dividing $2^k-1$ for any smaller $k$; that must be 31 itself. The reason 5 takes so long to show up in cycle spectra, though, is because $2^5-1$ is a (Mersenne) prime. Similarly 11 appears for the first time when we get down to $n = 23$ because $2^{11}-1 = 2047$ is divisible by 23 (it's $23 \times 89$ and no smaller $2^j-1$ is divisible by 23.)

Along the same lines, the reason that numbers with many factors show up frequently in your data (motivating Per Alexandersson's speculation that this is somehow related to the highly composite numbers) is because when $j$ has a lot of factors, so does $2^j-1$. This is a partial converse to the identity $$ 2^{ab-1} = (2^a-1) (1 + 2^a + 2^{2a} + \cdots + 2^{(b-1)a}) $$ which can be used to show that if $2^p-1$ is prime, then $p$ is prime also.

$\endgroup$
12
$\begingroup$

The mystery is resolved when one notices that $s_{i+1}=s_i^2$ in the symmetric group. Starting with $n=31$, there are cycles of length 5.

$\endgroup$
  • $\begingroup$ Can all primes be produced in this way? It is enough to produce all possible powers of primes to get all natural numbers. $\endgroup$ – Per Alexandersson Nov 10 '15 at 15:43
  • 3
    $\begingroup$ All integers can be produced. Take a permutation $s_0$ whose order is $2^k-1$, and the cycle length is $k$. $\endgroup$ – user78588 Nov 10 '15 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.