The maximum period of dancing program

Question

Sixteen people named A, B, ..., P are standing in line in the order ABC...P. They "dance", or swap places, according to some predefined instructions. There are two kinds of instructions called Exchange and Partner:

• Exchange(m,n): The two people standing at m-th and n-th positions swap places.
• Partner(x,y): The two people named x and y swap places.

For example, if there are only five people ABCDE and they are given instructions E(2,3) and P(C,E) in order, the following happens:

• E(2,3): The 2nd and 3rd people swap places, so the line becomes ACBDE.
• P(C,E): The people named C and E swap places, so the line becomes AEBDC.

Let's define a program as a fixed sequence of such instructions. You can put as many instructions as you want in a program.

Regardless of the length of your program, if the whole program is repeated a sufficient number of times, the line of people will eventually return to the initial state ABC.... Let's define the program's period as the smallest such number (i.e. the smallest positive integer n where running the program n times resets the line of people to the initial position). The states in the middle of a program are not considered.

For example, a program E(2,3); P(C,E); E(3,4) has the period of 6:

       E(2,3)   P(C,E)   E(3,4)
1. ABCDE -> ACBDE -> AEBDC -> AEDBC
2. AEDBC -> ADEBC -> ADCBE -> ADBCE
3. ADBCE -> ABDCE -> ABDEC -> ABEDC
4. ABEDC -> AEBDC -> ACBDE -> ACDBE
5. ACDBE -> ADCBE -> ADEBC -> ADBEC
6. ADBEC -> ABDEC -> ABDCE -> ABCDE

What is the maximum period of a program for 16 people?

---

Inspired by: Advent of Code 2017, Day 16

Answer 1

The maximum period is

5460

Warm-up

An exchange instruction swaps two positions in line. Any permutation of the 16 positions can be achieved by a dance program with only exchange instructions, by decomposing the permutation into swaps.

To find the period of a dance program with only exchange instruction, note that it breaks down into cycles that split up the 16 positions. Repeating the program some number of times returns us to the original dance line only when each cycle has returned to the start, and so after a number of steps that's a multiple of all these cycle sizes. The period is therefore the least common multiple of the cycle sizes, which form a partition of 16. The largest possible period for 16 is 140 according to this OEIS sequence, achieved as $\textrm{LCM}(4,5,7)$.

Combining instructions

But, we can do better with a dance program with both exchange and partner instructions.

Note that any partner instruction commutes with any exchange instruction -- swapping positions and swapping dancer names acts independently, and you can think of them as left- and right- compositions on the mapping given by the line.

So, we can simplify any dance program to group all exchange instructions together, followed by all partner instructions. Likewise, repeating this program $k$ times is the same as first doing all of its exchange instructions $k$ times, then its partner operations $k$ times.

We will choose the exchange permutation and the partner permutation to have individually large periods that are relatively prime to each other.

No short-circuiting

We show that the overall period of the dance program is then the product of these two periods. One might worry the overall period is smaller, since it's possible to "short-circuit" and return to the initial state without the exchange permutation or the partner permutation being the identity, but acting on the dance line as the identity in combination. But, we show this won't happen here.

Suppose that after $k$ repetitions of the dance program, the dance line is back as it started. Then, this is also the case after $ka$ repetitions, where $a$ is the period of the exchange permutation. Since $ka$ is a multiple of $a$, after $ka$ repetitions the exchange permutation is the identity. But this means the partner permutation must also be the identity since the whole dance line is back to where it started. Naming its period $b$, this means $ka$ is a multiple of $b$. But since $a$ and $b$ are relatively prime, this means the period $k$ is a multiple of $b$. A similar argument shows that it's a multiple of $b$, and therefore of $ab$. So, $k$ must be at least $ab$, and therefore the period is $ab$.

Largest overall period

So, we want to find two permutations of 16 elements, so that the product of their periods is as large as possible, and these periods are relatively prime. Recalling that the period of a permutation is the LCM of its cycle lengths, which are a partition of its 16 elements, we want to split two copies of 16 into relatively prime values whose product is as large as possible.

We can consider just cycle lengths that are powers of a prime, since any cycle length $xy$ with relatively prime $x$ can be split into two cycles $x$ and $y$, using up $x+y$ elements which is less than the $xy$ before. Note that we can always "pad" to a higher value by putting unused elements into their own cycles of length 1.

The usable powers of a prime that are at most 16 are: $2, 4, 8, 16, 3, 9, 5, 7, 11, 13$. We're allowed 32 in total, and want a product as big as possible. We can only pick one power of 2 and one power of 3.

In general, picking small numbers is more efficient than picking large ones -- if we think of additive contributions to the log of the product, the cost-benefit ratio of $n$ as $\frac{\log n}{n}$. We can similarly consider the marginal contribution of, say, changing 4 to 8 as doubling for the cost of 4. We can then sort the prime powers starting from the most f efficiency, treating powers of 2 and 3 as the marginal benefit over the previous power:

$2, 4, 3, 5, 7, 11, 13, 9, 8, 16$

A good heuristic here is taking the best ones from the start until we run out of total value of 32, giving $4,3,5,7,11$ for a total of 30. With 2 left we can do no better than bump up 11 to 13, giving $4,3,5,7,13$. I think one can prove this is optimal since it uses the most efficient possible values except for replacing 11 with 13 which is unavoidable.

We also need to make sure the total of 32 can be split into two groups adding to 16, and indeed it can: $(4,5,7)$ and $(3,13)$. (In fact, $(4,5,7)$ was the optimal single-permutation split from the warm-up.) These have products of 140 and 39, for an overall period of 5460

Creating the dance programs

To finish, let's step back and see how one would create a dance program with this period. We want our exchange instructions to split into cycles of $(4,5,7)$. We could do this, say, but having the first 4 positions rotate in a cycle, then the next 5, and then the next 7.

We can split a cycle up into a sequence of swaps that moves the first position down the line. For instance, the swaps $1\leftrightarrow 2, 2\leftrightarrow 3, 3\leftrightarrow 4$ in that order serve to ferry position 1 to the end of the four, while moving each other position one step left.

Doing this for each cycle of lengths $(4,5,7)$ gives us our exchange instructions. Then do the same for partner instructions to create cycles of $(3,13)$. Note that it doesn't matter which positions and dancers are chosen for the respective cycles.

Answer 2

If my calculations are correct (it's a bit fiddly), then I believe the answer is

5460.

When we do a "partner" operation,

instead of switching the places of the people involved let us switch their names. With this perspective, note that "swaps" and "partners" are independent of one another, so a program is simply defined by the effect of all its "swaps" and the effect of all its "partners"; that is, by two permutations which we may call $S,P$. (And since every permutation is a product of transpositions, for any permutations $S,P$ there is such a program.) The period is then the smallest $n$ for which the combined effect of $S^n$ and $P^n$ is to restore the original order. If instead of $S$ we use its inverse $Q$, the period is the smallest $n$ such that $P^n=Q^n$.

So, an equivalent way to state the problem is this:

suppose we pick two permutations and call their "mutual period" the smallest $n$ for which their $n$th powers are equal; how large can the mutual period of two permutations be?

Well,

suppose the two permutations have (on their own) periods $p,q$, and let $r$ be the least common multiple of $p,q$. Then $P^r=Q^r=1$ and therefore $r$ is a mutual period of $P,Q$. Is it possible that some smaller $r$ also has this property? Yes, obviously; e.g., take $P=Q\ne1$ and $r=1$! That's a shame. But we have, at any rate, established that the biggest we could hope to make the mutual period is whatever the LCM of the periods of two permutations is. And -- this will be useful -- note that $P^r$ has period dividing $p$ and $Q^r$ has period dividing $q$, so if these are equal but not equal to the identity then $p,q$ must have a common factor $>1$. So if it turns out that the biggest LCM we get is in fact achieved by a pair of permutations whose periods are coprime, then we'll be done.

Suppose we are interested in

making one permutation have large period. Every permutation is a product of disjoint cycles (where a cycle is something that sends, e.g., $a\rightarrow b\rightarrow c\rightarrow d\rightarrow a$) and its period is the LCM of the lengths of the cycles. If we ever have a cycle of length $ab$ where $a,b$ are coprime then we can do just as well with two cycles of lengths $a,b$, which use fewer objects. So the biggest periods of permutations of 16 elements will be LCMs of prime powers adding up to 16. The prime powers available are 1, 2,4,8, 3,9, 5, 7, 11, 13. Let's enumerate the best we can do for a given choice of largest prime power used. If we use 13 then the best we can do is 13,3 for period 39. Otherwise, if we use 11 then the best we can do is 11,5 for period 55. Otherwise, if we use 9 then the best we can do is 9,5,2 for period 90. Otherwise, if we use 8 then the best we can do is 8,5,3 for period 120. Otherwise, if we use 7 then the best we can do is 7,5,4 for period 140. Otherwise, if we use 5 then the best we can do is 5,4,3 for period 60. For biggest prime power 4 or less, we can't get a period bigger than 12. (There are some other biggish periods available that we shouldn't forget, like 9,7 giving 63.)

So what's the biggest

LCM we can get from two of these? We can get $140\cdot39=5460$. Can we do better? The larger of the two periods will have to be at least $\sqrt{5460}>73$; the only periods that big are 90 (9,5,2), 120 (8,5,3), 140 (7,5,4), 105 (7,5,3), 84 (7,4,3). We can fairly easily check that for none of these can we find another possible period yielding an LCM bigger than 5460. So (unless I have goofed) 5460 is the best we can hope for.

But this means we are done! Because

if we take $P$ a permutation of period 140 and $Q$ a permutation of period 39 -- say (abcdefg)(hijkl)(mnop) and (abcdefghijklm)(nop) -- then they definitely have mutual period 5460, because if $P^r=Q^r=S$, say, then $S^{140}=S^{39}=1$, and since 140,39 have no common factor $S$ must be the identity so that both 140 and 39 divide $r$.

Answer 3

Partial Answer

This mostly a partial answer because I haven't proven to myself for sure that this is the maximum. The answer I'm giving now will give a theoretical maximum. If I feel I can tackle a more concrete answer, I might update this answer later.

So, my answer for the moment is:

20,922,789,888,000

My reasoning of why this is the maximum is as follows:

Take any program A() which accepts some combination of partners (ACB...P) x and outputs some other combination y

So, A(x) = y

Now, suppose x = y. That means we would have a period of 1. Applying A() to x already gives us x.

To get a period larger than 1, x must be different from y. And, in fact, any time we apply A(), we must get a unique combination of partners that we've never seen before as a result for the period be of any length (I'll justify this statement more later).

All of this means that our cycle is defined by how many unique outputs any program A() can give, which is the same of asking how many ways can we arrange 16 objects. More mathematically speaking, this is how many permutations we can have of 16 objects. Using this formula, we get:

16!/(16-16)! = 16!/0! = 16!/1 = 16! = 20,922,789,888,000

I'm not sure this is the real maximum, but it certainly won't be more than that.

---

Now to justify my statement earlier:

Suppose this statement about uniqueness is not true. Let's suppose we have some program A() which has the following sequence of results:

x => y => z => y

What comes next? Well, we know from before that A(y) = z, so z is next:

x => y => z => y => z => y => z => y => z...

Hopefully it's easy to see that this will repeat forever and never reach x again. This means that such a program will not have a well-defined period. From what you already stated above, we know this is impossible.

Even if this were possible, there are a couple of things to note. The first being that even though this hypothetical program does not have a well-defined period starting from x, it does starting from y. In this case, his period is two. But whatever it is, notice that this period must also have unique outputs after each application of A(), or else it will have the same problem: it will create another smaller, infinite loop. So even if this hypothetical program existed, if would create another loop bounded by this rule.

Thus, no program can get a bigger period than 16! by including repeated combinations. Any program that includes repeats will instead just create another smaller, infinite loop with a period smaller than 16!.

However, the biggest possible period is the one that visits all of these combinations.

---

So, in summary:

I'm not sure if the true biggest is less than this, but whatever the true answer is, it will certainly be no bigger than:

16! = 20,922,789,888,000