## Divisibility property of the number of permutations realized by a shift

Our summer Mathematica workshop met after Math 117, which featured the research of one faculty member each week. During the first week, we decided to do programming exercises inspired by Sergi’s talks on permutation patterns. This post is about one of the problems he mentioned.

To start with, here is the basic definition from the abstract of the preprint I refer to below:

A permutation is realized by a shift on symbols if there is an infinite word on an -letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as .

For example, let be our 4-letter alphabet equipped with the usual order. Now consider an infinite word on those 4 letters, such as . By successively shifting the infinite word to the left, we produce a new sequence of infinite words whose relative lexicographic orders are indicated on the right column:

In this case, we say that the permutation can be realized by a shift on 4 symbols.

Exercise.Show that the permutation can be realized by a shift on 2 symbols.

For a non-example, we can check that there is no infinite word on whose first 4 shifts correspond to the permutation . In this case, we say that cannot be realized as a shift on 2 symbols.

Let be the number of permutations of length that require symbols in the alphabet in order to be realized by a shift. In his arXiv preprint, Sergi proved that

where denotes the number of primitive words of length over an -letter alphabet. It is well known that

where denotes the Möbius function. Based on experimental evidence, Sergi conjectured that is divisible by 6 for all .

The expression for is quite complicated, and I did not think that the conjecture was tractable. Not to be deterred, Peter insisted that we use Mathematica to generate terms of the summation for various values of and check if each of them is divisible by 6. To our delight, Dan soon found that we could strip away both the summation sign and the binomial coefficient and still retain the divisibility property. By the end of our meeting, we were convinced that we could prove Sergi’s conjecture.

Jeff and I worked to fill in the gaps during the evening and the following day. We took many false steps along the way, but the end was never in doubt. The following is a sanitized version of our work based on the note Jeff wrote up afterwards.

Theorem.For all , is divisible by 6.

*Proof.* It suffices to verify that the terms

is divisible by 6. According to lemma 2 below, we can disregard all but the first two terms of the summation. After a change of variables , we are left with the following expression modulo 6:

which simplifies to

Now we simply check that divisibility by 2 and 3 holds in the five cases corresponding to and respectively.

Lemma 1.For all , we have

*Proof.* Our starting point is the identity

and the fact that the whenever is not square-free. We consider three cases, depending on the highest power of 2 dividing .

If is an odd integer,

If is divisible by 4, then exponent of -1 is odd only if is not square-free, and thus . So in this case,

The remaining case is when is even but not divisible by 4. We observe that the even divisors of are precisely the odd divisors of multiplied by 2. We can thus write as

Since is multiplicative, we have and so

Lemma 2.For all and , is divisible by 6.

*Proof.* We go through the five cases and to show that is divisible by 2 and 3 respectively. Lemma 1 is useful for the case :

As Sergi pointed out afterwards, divisibility by 2 is clear because if a word on letters realizes a permutation , then the word realizes the complement of the permutation . It will be interesting to see a combinatorial argument for divisibility by 3, not least because our number-theoretic approach is rather tedious.