Archive for the ‘Math’ Category

Divisibility property of the number of permutations realized by a shift

September 17, 2012 Leave a comment

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 \pi is realized by a shift on N symbols if there is an infinite word on an N-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as \pi.

For example, let \{ 0, 1, 2, 3 \} be our 4-letter alphabet equipped with the usual order.  Now consider an infinite word on those 4 letters, such as 221302333200222\ldots.  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:

\begin{tabular}{rcl} 221302333200222 \ldots & \quad & 4 \\ 21302333200222 \ldots & \quad & 3 \\ 1302333200222 \ldots & \quad & 2 \\ 302333200222 \ldots & \quad & 6 \\ 02333200222 \ldots & \quad & 1 \\ 2333200222 \ldots & \quad & 5 \end{tabular}

In this case, we say that the permutation \pi = [4, 3, 2, 6, 1, 5] can be realized by a shift on 4 symbols.

Exercise.  Show that the permutation \pi = [1, 3, 4, 2] can be realized by a shift on 2 symbols.

For a non-example, we can check that there is no infinite word on \{0, 1\} whose first 4 shifts correspond to the permutation \pi = [2, 1, 3, 4].  In this case, we say that \pi cannot be realized as a shift on 2 symbols.

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

\displaystyle a_{n,N} = \sum_{i=0}^{N-2} (-1)^i \binom{n}{i} \left( (N-i-2)(N-i)^{n-2} + \sum_{t=1}^{n-1} \psi_{N-i}(t)(N-i)^{n-t-1} \right),

where \psi_N(k) denotes the number of primitive words of length k over an N-letter alphabet.  It is well known that

\displaystyle \psi_N(k) = \sum_{d\mid k} \mu(d) N^{k/d},

where \mu denotes the Möbius function.  Based on experimental evidence, Sergi conjectured that a_{n,N} is divisible by 6 for all n, N \geq 3.

The expression for a_{n,N} 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 n, m 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 n, N \geq 3, a_{n,N} is divisible by 6.

Proof.  It suffices to verify that the terms

\displaystyle (N-i-2)(N-i)^{n-2} + \sum_{t=1}^{n-1} \psi_{N-i}(t)(N-i)^{n-t-1}

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 M = N - i, we are left with the following expression modulo 6:

\displaystyle (M-2)M^{n-2} + \psi_M(1) M^{n-2} + \psi_M(2) M^{n-3},

which simplifies to

\displaystyle (M-2)M^{n-2} + M^{n-1} + (M^2 - M)M^{n-3}.

Now we simply check that divisibility by 2 and 3 holds in the five cases corresponding to M \equiv 0, 1 \pmod{2} and M \equiv 0, 1, 2 \pmod{3} respectively. \ \square

Lemma 1.  For all t \geq 3, we have

\displaystyle \psi_{-1}(t) = \sum_{d \mid t} \mu(d) (-1)^{t/d} = 0.

Proof.  Our starting point is the identity

\displaystyle \sum_{d \mid t} \mu(d) = \begin{cases}1&\mbox{ if } t=1\\ 0&\mbox{ if } t >1\end{cases}

and the fact that the \mu(d) = 0 whenever d is not square-free.  We consider three cases, depending on the highest power of 2 dividing t.

If t is an odd integer,

\displaystyle \psi_{-1}(t) = \sum_{d \mid t} \mu(d) (-1)^{t/d} = - \sum_{d \mid t} \mu(d) = 0.

If t is divisible by 4, then exponent t/d of -1 is odd only if d is not square-free, and thus \mu(d) = 0.  So in this case,

\displaystyle \psi_{-1}(t) = \sum_{d \mid t} \mu(d) (-1)^{t/d} = \sum_{d \mid t} \mu(d) = 0.

The remaining case is when t is even but not divisible by 4.  We observe that the even divisors of t are precisely the odd divisors of t multiplied by 2.  We can thus write \psi_{-1}(t) as

\displaystyle \sum_{\substack{d \mid t \\ d \ \text{odd}}} \mu(d) (-1)^{t/d} + \sum_{\substack{d \mid t \\ d \ \text{even}}} \mu(d) (-1)^{t/d} = \sum_{\substack{d \mid t \\ d \ \text{odd}}} \mu(d) (-1)^{t/d} + \sum_{\substack{d \mid t \\ d \ \text{odd}}} \mu(2d) (-1)^{t/2d}.

Since \mu is multiplicative, we have \mu(2d) = - \mu(d) and so \psi_{-1}(t) = 0. \ \square

Lemma 2.  For all M \geq 0 and t \geq 3, \psi_M(t) is divisible by 6.

Proof.  We go through the five cases M \equiv 0, 1 \pmod{2} and M \equiv 0, 1, 2 \pmod{3} to show that \psi_{M}(t) is divisible by 2 and 3 respectively.  Lemma 1 is useful for the case M \equiv 2 \equiv -1 \pmod{3}:

\displaystyle \psi_{M}(t) \equiv \sum_{d \mid t} \mu(d) (-1)^{t/d} = 0 \pmod{3}. \ \square

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