Solving Permutation-Based Puzzles

Introduction

In the previous article, we described the Schreier-Sims algorithm. Given a small subset A\subseteq S_n which generates the permutation group G, the algorithm constructs a sequence k_1, k_2, \ldots, k_m \in [n] = \{1, 2, \ldots, n\} such that for:

G = G^{(0)} \ge G^{(1)} \ge \ldots \ge G^{(m)} = 1, \\ G^{(i)} := \{g \in G : g(k_1) = k_1, g(k_2) = k_2 \ldots, g(k_m) = k_m\}.

we have a small generating set A^{(i)} for each G^{(i)}. Specifically, via the Sims filter, we can restrict |A^{(i)}| \le \frac{n(n-1)}2 for each i.

In this article, we will answer the following question.

Factorization Problem.

How do we represent an arbitrary representation g\in G as a product of elements of A and their inverses?

If we can solve this problem in general, we would be able to solve a rather large class of puzzles based on permutations, e.g. Rubik’s cube and the Topdown puzzle. First, let’s look at the straightforward approach from the Schreier-Sims method.

Attempt

Recall that the Schreier-Sims method starts with A^{(0)} := A. At each step it picks a base element k_i \in [n], computes a generating set for G^{(i)} from A^{(i-1)} then pares down this set with the Sims filter so that |A^{(i)}| \le \frac{n(n-1)}2. Thus one can, in theory, keep track of the elements of A^{(i)} by expressing them as words in A.

The problem with this approach is that since A^{(i)} is obtained from A^{(i-1)}, the length of words for A^{(i)} would be a constant factor of those for A^{(i-1)}. Thus by the time we reach A^{(m)}, their lengths would be exponential in m. 😦

blue-lin

Minkwitz’s Algorithm

As far as we know, the first paper to solve the factorization problem is by T. Minkwitz in “An Algorithm for Solving the Factorization Problem in Permutation Groups” (1998). The idea is elegant. First, we replace the generating sets A^{(i)} with the following tables.

Main Goal.

For each 0\le i \le m-1, let O_i be the orbit G^{(i)}\cdot k_{i+1}. We wish to obtain a set B_i\subseteq G^{(i)}, indexed by x\in O_i, such that

  • B_i(x) \in G^{(i)} takes the base element k_{i+1} \mapsto x.

In other words, the element g = B_i(x) is any element of G satisfying:

g(k_1) = k_1, g(k_2) = k_2, \qquad, g(k_i) = k_i, g(k_{i+1}) = x.

Minkwitz’s method replaces the sequence of sets A_0, \ldots, A_{m-1} with B_0, \ldots, B_{m-1}; furthermore, the elements of the latter sets are stored as words in A\cup A^{-1} instead of mere permutations.

To begin, we initialize B_i(k_{i+1}) to be the empty word for i = 0, …, m-1.

Next we run through words in A \cup A^{-1}, starting from those of length 1, then those of length 2, etc. For each word w, compute the corresponding element g\in G and do the following:

  1. Start with i = 0.
  2. Let x = g(k_{i+1}) \in O_i. Do we have an entry for B_i(x)?
    • If not, we let B_i(x) be the word w and quit.
    • If yes, and w is shorter than the current word in B_i(x), we replace it with w and quit.
    • Otherwise, let w' = B_i(x). Replace w with w'^{-1}w and increment i then repeat step 2.

blue-lin

Example

Let us take the example from the previous article, with G\le S_8 generated by:

a = (1, 5, 7)(2, 6, 8), \qquad b = (1, 5)(3, 4, 8, 2).

Applying the Schreier-Sims algorithm, we obtain the following base and orbits:

\begin{aligned} k_1 &= 3 \implies \text{ orbit } O_0 = \{2, 3, 4, 6, 8\}, \\ k_2 &= 6 \implies \text{ orbit } O_1 = \{2, 4, 6, 8\},\\ k_3 &= 4 \implies \text{ orbit } O_2 = \{2, 4, 8\}, \\ k_4 &= 5 \implies \text{ orbit } O_3 = \{1, 5, 7\}, \\ k_5 &= 1 \implies \text{ orbit } O_4 = \{1, 7\}.\end{aligned}

From this, we deduce that the order of G is 5 × 4 × 3 × 3 × 2 = 360. Applying Minkwitz’s algorithm, we first initialize the table as follows:

orbits_and_words_1

Now consider the word ‘a’, which corresponds to g = (1, 5, 7)(2, 6, 8). This has no effect on k_1 = 3. On the other hand, it takes k_2 = 6\mapsto 8. Thus, we write the word ‘a’ into the last entry of the second row:

orbits_and_words_2

After running through all words of length 1, we arrive at the following table:

orbits_and_words_3

The first word of length 2 is ‘aa’, which corresponds to (1, 7, 5)(2, 8, 6), but this is just a-1, and we have already processed it.

The next word of length 2 is ‘ab’, which gives g = ab = (1, 7)(2, 3, 4)(6, 8). This takes k_1 = 3 \mapsto 4. However, the corresponding entry is already filled with ‘b’. Since this new word does not improve upon the old one, we replace the word with b-1ab. Now we have

g = b^{-1}ab = (1,7,5)(4,8,6).

and proceed on to k_2. This element takes k_2 = 6 \mapsto 4 so we fill in the corresponding entry on the second row:

orbits_and_words_4

blue-lin

Further Improvements

The above method is quite effective for most random groups. However, the last few entries of the table may take a really long time to fill up. E.g. on the set:

A = \{ (1, 2), (2, 3), (3, 4), \ldots, (n-1, n)\}, \quad \left<A\right> = S_n

the shortest word which takes 1 to n is given by (n-1, n)(n-2, n-1) \ldots (1, 2). Intuitively, the table fills up slowly because the elements {1, …, n} diffuse slowly via the generators.

One possible way out of this rut is to fill in entries of the table by looking at the group elements below the current row. To be specific, suppose the row for k_{i+1} has quite a few empty entries. We look at those existing entries, say x_1, x_2, \ldots and consider all words w found below the row. Their group elements g\in G are guaranteed to lie in G^{(i+1)}\le G^{(i)}. If the entry for g(x_j) is currently empty, we fill it in with the concatenation of w and the corresponding word for k_{i+1} \mapsto x_j. [Of course we need to perform reduction after concatenating the two words.]

Optimization

To further optimize, note that sometimes a table entry gets replaced with a nice shorter word – it would be desirable to use this short word to update the other table entries.

Hence, we perform the following. For each row i, consider any two words w’w” on that row. We take their concatenation w := w’w” and use it to update the entire table from row i onwards (by update, we mean: compute x = w(k_{i}) and check if w is shorter than the table entry at x. If it is, we update; otherwise we let w1 be this entry and replace w with w_1^{-1}w and repeat the whole process).

As this process is rather slow, we only update the table if either w’ or w” are of shorter length, compared to the last time we did this optimization.

Summary

Minkwitz’s paper suggests the following iterative procedure.

  • Set a maximum word length l.
  • For each word of short length, update the table as described earlier.
    • If, at a certain row, the word length exceeds l, we bail out.
  • For every s steps, do the following.
    • Perform the above two enhancements: filling up and optimizing.
    • Increase l, say, to (5/4)l.

Setting the word length is optional, but can speed things up quite a bit in practice. It prevents the initial s steps from filling up the table with overly long words, otherwise optimizing them will be costly. For further details, the diligent reader may refer to Minkwitz’s original paper, available freely on the web.

Outcome.

We applied this to the study of the Rubik’s cube group, and obtained a representation with maximum word length of 184 over all elements of the group. This is slightly worse than the result of 144-165 quoted in Minkwitz’s paper.

blue-lin

Case Study: Topspin Puzzle

The Topspin puzzle is a toy which consists of a loop with 20 labeled counters in it. In the middle of the loop lies a turntable which reverts the order of any four consecutive counters. This is what the puzzle looks like.

topspin_amazon

[ Photo from product page on Amazon. ]

Thus the group of permutations of the counters is generated by

a = (1, 2, 3, …, 20),   b = (1, 4)(2, 3)

From the Schreier-Sims algorithm, we see that these two elements generate the full symmetric group S_{20} so Topspin achieves all possible permutations of the 20 counters. Minkwitz’s algorithm gives us a practical way to solve the puzzle given any initial configuration. Our program gave us a full table with a maximum word length of 824.

To search for short words representing a given g\in S_{20},

  • let w be a short word in \{a, b, a^{-1}, b^{-1}\};
  • let h\in S_{20} be the permutation for w;
  • find the word w’ for h^{-1}g;
  • thus ww’ is a word representing g.

We iterate over about 1000 instances of w and pick the shortest representation among all choices.

Example

Consider the transposition (1, 2). We obtain the following word:

a-1a-1b-1a-1b-1ab-1a-1b-1abab-1a-1a-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1b

of length 43 (to be applied from right to left). This is a remarkably short word – for  most random configurations we tried, the length of the word is >200.

blue-lin

Posted in Uncategorized | Tagged , , , , , | Leave a comment

Schreier-Sims Algorithm

Introduction

Throughout this article, we let G be a subgroup of S_n generated by a subset A\subseteq S_n. We wish to consider the following questions.

  • Given A, how do we compute the order of G?
  • How do we determine if an element g\in S_n lies in G?
  • Assuming g\in G, how do we represent g as a product of elements of A and their inverses?

In general, the order of G is comparable to |S_n| = n! even for moderately-sized A so brute force is not a good solution.

We will answer the first two questions in this article. The third is trickier, but there is a nice algorithm by Minkwitz which works for most practical instances.

Application

We can represent the group of transformations of the Rubik’s cube as a subgroup of S_{48} generated by a set S of 6 permutations. The idea is to label each non-central unit square of each face by a number; a transformation of the Rubik’s cube then corresponds to a permutation of these 6 × 8 = 48 unit squares.

rubik_cube

[Image from official Rubik’s cube website.]

Our link above gives the exact order of the Rubik’s cube group (43252003274489856000), as computed by the open source algebra package GAP 4. How does it do that, without enumerating all the elements of the group? The answer will be given below.

blue-lin

Schreier-Sims Algorithm

To describe the Schreier-Sims algorithm, we use the following notations:

  • A\subseteq S_n is some subset represented in the computer’s memory;
  • G = \left< A\right> is a subgroup of S_n;
  • G acts on the set [n] := \{1, 2, \ldots, n\}.

Let us pick some random element k\in [n] and consider its orbit O_k under G. From the theory of group actions, we have

|O_k| = \frac{|G|}{|G_k|}

where G_k = \{g \in G: g(k) = k\} is the isotropy group of k. Now it is easy to compute the orbit of k: we start by setting the orbit to be the singleton {k}, then expand it by letting elements of A act on elements of this set. The process stops if we can’t add any more elements via this iteration. A more detailed algorithm will be provided later.

Thus, if we could effectively obtain a set of generators for G_k, our task would be complete since we could recursively apply the process to G_k. [Or so it seems: there’ll be a slight complication.]

For that, we pick a set U of representatives for the left cosets \{gG_k : g\in G\} as follows. For each j\in O_k, we pick some element g\in G_k which maps k\mapsto j, and for jk we pick the identity. To facilitate this process, we use a data structure called a Schreier vector.

blue-lin

Schreier Vector for Computing Orbits

Warning: our description of the Schreier vector differs slightly from the usual implementation, since we admit the inverse of a generator.

Let us label the elements of the generating set A = \{g_1, g_2, \ldots, g_m\}.

  • Initialize an array (v[1], v[2], …, v[n]) of integers to -1.
  • Set v[k] := 0.
  • For each i = 1, 2, …, n:
    • If v[i] = -1 we ignore the next step.
    • For each r = 1, 2, …, m, we set ggr:
      • set j := g(i); if v[j] = -1, then set v[j] = 2r-1;
      • set j := g-1(i): if v[j] = -1, then set v[j] = 2r.
  • Repeat the previous step until no more changes were made to v.

The idea is that v contains a “pointer” to an element of A (or its inverse) which brings it one step closer to k.

Example

Suppose we have elements

a = (1, 5, 3, 2)(4, 7, 9), \quad b = (1, 6, 7).

Labelling a = g_1 and b = g_2, we obtain the following Schreier vector for k=1:

schreier_vector_example

Thus the orbit of 1 is {1, 2, 3, 4, 5, 6, 7, 9}. To compute an element which maps 1 to, say, 9, the vector gives us ab^{-1}(1) = 9. Hence we can pick the following for U

U = \{e, a^{-1}, a^{-2}, a^{-1}b^{-1}, a, b, b^{-1}, ab^{-1}\}.

blue-lin

Key Lemma

Next, we define the map \phi : G\to U which takes g\in G to the unique u\in U such that gG_k = uG_k (i.e. u is the unique element of U satisfying u(k) = g(k)). Our main result is:

Schreier’s Lemma.

The subgroup G_k is generated by the following set

B := \{ \phi(au)^{-1} au : a\in A, u\in U\}.

Proof

First note that \phi(au)^{-1} au takes k to itself: indeed \phi(au) by definition takes k to au(k). Thus we see that each \phi(au)^{-1} au\in G_k as desired so \left<B\right>\le G_k.

Next, observe that B is precisely the set of all u'^{-1}au for u, u'\in U and a\in A which lies in G_k. Indeed for such an element, u’ must be the unique element of U which maps k to au(k) and so u = \phi(au).

Now suppose h\in G_k; we write it as a product of elements of A and their inverses:

h = a_1^{\epsilon_1} a_2^{\epsilon_2} \ldots a_m^{\epsilon_m}, \quad \epsilon_i = \pm 1.

We will write

u_0^{-1}hu_m = (u_0^{-1} a_1^{\epsilon_1} u_1)\cdot (u_1^{-1} a_2^{\epsilon_2} u_2)\ldots (u_{m-1}^{-1} a_m^{\epsilon_m} u_m),

where u_0, u_1, \ldots, u_m\in U are elements to be recursively chosen. Specifically we start with u_m := e\in U, and for each u_{i+1}\in U we set u_i := \phi(a_{i+1}u_{i+1}). Note that each term in parentheses is an element of B\cup B^{-1}. Thus, the expression lies in G_k.

So we have u_0 = \phi(hu_m) = \phi(h). Since h\in G_k, this gives u_0=e as well so we have obtained h as a product of elements of B and their inverses. ♦

blue-lin

Example

Consider the subgroup G\le S_{8} generated by

a = (1, 5, 7)(2, 6, 8), \quad b = (1, 5)(3, 4, 8, 2).

If we pick k = 1, its orbit is O_k = \{1, 5, 7\}. For the coset representatives U, we take:

1 \mapsto g_1 = e, \quad 5 \mapsto g_5 = b, \quad 7\mapsto g_7 =a^{-1}.

Now the subgroup G_k is generated by the following 6 elements:

\begin{matrix}g_5^{-1}ag_1 = (2, 6, 4, 3)(5, 7), & g_7^{-1}ag_5 = (2, 3, 4, 6)(5, 7), & g_1^{-1}ag_7 = e, \\ g_5^{-1} b g_1 = e, &g_1^{-1}bg_5 = (2, 4)(3, 8),& g_7^{-1}bg_7 = (2, 6, 3, 4)(5, 7).\end{matrix}

Let H\le S_8 be the subgroup generated by these 6 elements; after removing the identity elements we are left with 4. Now if we pick k = 2 next, we obtain 5 representatives for the next U and thus, we obtain up to 20 generators for the stabilizer of {1, 2} in G.

Problem

The number of generators for the stabilizer groups seems to be ballooning: we started off with 2 examples, then expanded to 6 (but trimmed down to 4), then blew up to 20 after the second iteration.

Indeed, if we naively pick \{\phi(au)^{-1}au\} over all (a,u) \in A\times U, then the number of generator increases |U| = |O_k| times, while the order of the group decreases |O_k| times as well. Thus, at worst, the number of generators is comparable to the order of the group, which is unmanageable.

Thankfully, we have a way to pare down the number of generators.

blue-lin

Sims Filter

Sims Filter achieves the following.

Task.

Given a set A \subseteq S_n, there is an effective algorithm to replace A by some B\subseteq S_n satisfying \left<A\right> = \left<B\right> and

|B| \le \min\{|A|, \frac{n(n-1)}2\}.

Let us explain the filter now. For any non-identity permutation g\in S_n, let J(g) be the pair (ij) with 1 \le i < j\le n such that g(a) = a for all 1\le a < i and \pi(i) = j.

sims_function

Now we will construct a set B such that \left<A\right> = \left<B\right> and the elements \pi\in B all have distinct J(\pi). It thus follows that |B| \le \frac{n(n-1)}2.

  1. Label A = \{g_1, g_2, \ldots, g_m\}.
  2. Prepare a table indexed by (ij) for all 1\le i<j\le n. Initially this table is empty.
  3. For each g_k \in A, if g_k = e we drop it.
  4. Otherwise, consider J(g_k) = (i, j). If the table entry at (ij) is empty, we fill g_k in. Otherwise, if the entry is h\in S_n, we replace g_k with g_k' := g_k^{-1}h and repeat step 3.
    • Note that this new group element takes i to i so if it is non-identity, we have J(g_k') = (i', j') with i' > i

After the whole process, the entries in the table give us the new set B. Clearly, we have |B| \le \min\{|A|, \frac{n(n-1)}2\}.

Example

As above, let us take A = {ab} with

a = (1, 5, 7)(2, 6, 8), b = (1, 5)(3, 4, 8, 2) \in S_8.

First step: since J(a) = (1, 5) we fill the element a in the table at (1, 5).

Second step: we also have J(b) = (1, 5), so now we have to replace b with

b' := b^{-1}a = (2, 6, 4, 3)(5, 7).

Now we have J(b’) = (2, 6) so this is allowed.

blue-lin

Summary and Applications

In summary, we denote G^{(0)} = G and A^{(0)} = A.

  • For i = 1, 2, …
    • Pick a point k_i \in [n] not picked earlier.
    • Let G^{(i)} be the stabilizer group for k_i under the action of G^{(i-1)}. From A^{(i-1)}, we use Schreier’s lemma to obtain a generating set for G^{(i)}.
    • Use Sims filter to reduce this set to obtain A^{(i)} of at most \frac{n(n-1)}2 elements.
    • If A^{(i)} is empty, quit.

Thus k_1, k_2, \ldots, k_m \in [n] = \{1, 2, \ldots, n\} are distinct such that each of the groups

G = G^{(0)} \ge G^{(1)} \ge \ldots \ge G^{(m)} = 1, \\ G^{(i)} := \{g \in G : g(k_1) = k_1, \ldots, g(k_i) = k_i\}

has an explicit set of generators of at most \frac{n(n-1)}2 elements. Here are some applications of having this data.

1. Computing |G|.

It suffices to compute \frac{|G^{(i)}|}{|G^{(i+1)}|} for each i. Since G^{(i+1)} is the stabilizer group for the action of G^{(i)} on k_{i+1} we need to compute the size of the orbit G^{(i)}\cdot k_{i+1} for each i. Since we have a generating set for each G^{(i)}, this is easy.

2. Determining if a given g\in S_n lies in G.

To check if g\in G we first check whether g(k_1) lies in the orbit G\cdot k_1. If it weren’t, g\not\in G. Otherwise we pick some h\in G such that h(k_1) = g(k_1). Replacing g with h^{-1}g, we may thus assume that g(k_1) = k_1, and it follows that g\in G= G^{(0)} if and only if g\in G^{(1)}. Thus we can solve the problem inductively.

Generalizing, we can determine if H\le S_n is a subgroup of G\le S_n, when H and G are given by explicit sets of generators.

3. Checking if H\le S_n is a normal subgroup of G\le S_n.

Writing G = \left<A\right> and H = \left<B\right>, we claim that H is normal in G if and only if:

g\in A, h\in B \implies ghg^{-1} \in H.

First we fix g\in G. Since (ghg^{-1})(gh'g^{-1}) = ghh'g^{-1} and (ghg^{-1})^{-1} = gh^{-1}g^{-1}, we see that gHg^{-1} \subseteq H. But both groups are of the same finite cardinality so equality holds. Thus g^{-1}Hg = H as well. It follows that gHg^{-1} = H for all g\in G.

blue-lin

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Primality Tests III

Solovay-Strassen Test

This is an enhancement of the Euler test. Be forewarned that it is in fact weaker than the Rabin-Miller test so it may not be of much practical interest. Nevertheless, it’s included here for completeness.

Recall that to perform the Euler test on an odd n, we pick a base a and check if a^{(n-1)/2} \equiv \pm 1 \pmod n.

To enhance this, we note that if p > 2 is prime, the value a^{\frac{p-1}2} modulo p tells us whether a is a square modulo p. We had written extensively on this before – in short, the Legendre symbol (\frac a p) := a^{\frac{p-1} 2} \mod p satisfies:

\left( \frac a p\right) = \begin{cases} +1, \quad &\text{if } a \text{ is a quadratic residue modulo } p\\ -1, \quad &\text{if } a \text{ is a non-quadratic residue modulo } p\\0, \quad &\text{if } a \text{ is divisible by } p\end{cases}

\left( \frac {-1} p\right) = \begin{cases} 1,\quad&\text{if } p\equiv 1 \pmod 4,\\ -1,\quad &\text{if }p \equiv -1\pmod 4.\end{cases}

\left( \frac 2 p\right) = \begin{cases} 1,\quad &\text{if } p\equiv 1, 7\pmod 8,\\ -1, \quad &\text{if } p \equiv 3, 5\pmod 8.\end{cases}

\left( \frac{ab} p\right) = \left( \frac a p\right) \left( \frac b p\right).

a \equiv b \pmod p \implies \left( \frac a p\right) = \left( \frac b p\right).

p, q \text{ odd prime} \implies \left( \frac q p\right) = (-1)^{\frac{p-1}2 \frac{q-1} 2}\left( \frac p q\right).

Observe that the second, fourth and fifth properties follow easily from the definition of the Legendre symbol. The last property, known as the quadratic reciprocity law, is highly non-trivial and is the seed of an extremely deep area of algebraic number theory, called class field theory. But that’s a story for another day.

Now, if we had another way to compute the Legendre symbol (\frac a p) and extend its definition to (\frac a n), we could compute a^{\frac {n-1}2} \mod n and compare the two.

blue-lin

Jacobi Symbol

Let us extend the Legendre symbol to the Jacobi symbol.

Definition.

Let a be any integer and n be an odd positive integer. Write

n = p_1^{r_1} p_2^{r_2} \ldots p_d^{r_d}

be its prime factorization. The Jacobi symbol is defined via:

\left(\frac a n\right) := \left(\frac a {p_1}\right)^{r_1} \left(\frac a {p_2}\right)^{r_2} \ldots \left(\frac a {p_d}\right)^{r_d}

where each term \left(\frac a {p_i}\right) is the Legendre symbol.

The Jacobi symbol inherits most properties of the Legendre symbol.

Exercise

Prove the following properties of the Jacobi symbol.

\left( \frac {-1} n\right) = \begin{cases} 1,\quad&\text{if } n\equiv 1 \pmod 4,\\ -1,\quad &\text{if }n \equiv -1\pmod 4.\end{cases}

\left( \frac 2 n\right) = \begin{cases} 1,\quad &\text{if } n\equiv 1, 7\pmod 8,\\ -1, \quad &\text{if } n \equiv 3, 5\pmod 8.\end{cases}

\left( \frac{ab} n\right) = \left( \frac a n\right) \left( \frac b n\right).

a \equiv b \pmod n \implies \left(\frac a n\right) = \left(\frac b n\right).

m, n \text{ odd positive} \implies \left( \frac n m\right) = (-1)^{\frac{m-1}2 \frac{n-1} 2}\left( \frac m n\right).

Proof

We will only prove the last property as an example. First note that when m and n are odd primes, the result is just the quadratic reciprocity theorem. Since we have (\frac a n)(\frac b n) = (\frac {ab} n) and (\frac a {mn}) = (\frac a m)(\frac a n) it suffices to define, for positive odd m and n,

D(m, n) = (-1)^{\frac {m-1}2\frac {n-1}2}

and prove D(mm', n) = D(m, n)D(m',n) and D(m, nn') = D(m,n) D(m,n'). The two claims are identical, so let’s just show the first, which is equivalent to:

\frac{mm' - 1}2 \frac{n-1}2 \equiv \frac {m-1}2 \frac{n-1}2 + \frac{m'-1}2 \frac{n-1}2 \pmod 2.

But this is obvious: the difference between the two sides is \frac{(m-1)(m'-1)}2 \frac{n-1}2 which is clearly even. ♦

blue-lin

Computing the Jacobi Symbol

We thus have a computationally feasible way to compute the Jacobi symbol recursively for extremely large integers. E.g. to compute (\frac {69}{133}) we repeatedly apply the above properties to obtain:

(\frac{33}{89}) = (\frac{89}{33}) = (\frac{23}{33}) = (\frac{33}{23}) = (\frac{10}{23}) = (\frac 2 {23})(\frac 5 {23}) = (\frac 5 {23}) = (\frac {23} 5) = (\frac 3 5) = (\frac 5 3) = (\frac 2 3) = -1.

In Python code, we have:

def jacobi(m, n):
   if m == 0:
      return 0

   if m == 1:
      return 1

   if m < 0:
      if (n%4 == 3):
         return -jacobi(-m, n)
      else:
         return +jacobi(-m, n)

   if (m >= n):
      return jacobi(m%n, n)

   if m % 2 == 0:
      if (n%8 == 3 or n%8 == 5):
         return -jacobi(m/2, n)
      else:
         return +jacobi(m/2, n)

   if m % 4 == 3 and n % 4 == 3:
      return -jacobi(n, m)
   else:
      return jacobi(n, m)

Now we can describe our main objective.

blue-lin

Description of Test

Solovay-Strassen Test.

Given an odd n and base a, compute the Jacobi symbol (\frac a n). Now check that

a^{\frac{n-1} 2} \equiv (\frac a n) \pmod n

and that both sides are non-zero.

Example

Let n = 10261 and a = 2. Immediately the Jacobi symbol gives (\frac a n) = -1. On the other hand, a^{\frac {n-1}2}\equiv 1 \pmod n. Thus even though n passes the Euler test for base 2, it fails the Solovay-Strassen test for the same base.

Notice that this also fails the Rabin-Miller test for the same base since

2^{(n-1)/4} \equiv 1985 \not\equiv \pm 1 \pmod n but 2^{(n-1)/2} \equiv 1 \pmod n.

In fact, the following is true in general.

Theorem.

If odd n passes the Rabin-Miller test to base a, then it also passes the Solovay-Strassen test to the same base.

For a proof of the result, see theorem 3 of this paper. This is why we said there’s not much practical application for this test.

blue-lin

 

Posted in Uncategorized | Tagged , , , , , , , | Leave a comment

Primality Tests II

In this article, we discuss some ways of improving the basic Fermat test. Recall that for Fermat test, to test if n is prime, one picks a base an and checks if a^{n-1} \equiv 1 \pmod n. We also saw that this method would utterly fail when we throw a Carmichael number at it.

Euler Test

The basic enhancement is as follows.

Lemma.

If p is prime and m^2 \equiv  1 \pmod p, then m \equiv \pm 1 \pmod p.

The lemma is quite easy to proof. By the given condition m^2 - 1 = (m-1)(m+1) is a multiple of p and since p is prime either (m – 1) or (m + 1) is a multiple of p and the result follows.

In particular, if p is an odd prime and a is not divisible by p, then by Fermat’s theorem we have:

\left(a^{\frac{p-1} 2}\right)^2 = a^{p-1} \equiv 1 \pmod p \implies a^{\frac{p-1}2} \equiv \pm 1\pmod p.

In other words, to test if an odd n is prime, we pick a base an and check if a^{\frac{n-1}2}\equiv \pm 1\pmod n. If it is not, then n is not prime. This is called the Euler test with base a.

Note that the Euler test is necessarily stronger than the Fermat test since if a^{\frac{n-1}2} \equiv \pm 1\pmod n, then we must have a^{n-1}\equiv 1\pmod n.

Example 1

Consider n = 11305. We pick the smallest base a = 2. This gives us:

a^{\frac{n-1}2} = 2^{5652} \equiv 10641 \not\equiv \pm 1 \pmod {n}.

Notice that the Fermat with the same base would give a^{n-1} \equiv 10641^2 \equiv 1  \pmod n. Hence a pseudoprime can be picked up by the Euler test.

Example 2

Suppose we pick n = 10585 as before. We obtain:

2^{\frac{n-1}2} \equiv 3^{\frac{n-1}2} \equiv 1 \pmod n

so Euler test is not more effective than Fermat test in this case.

Example 3

Let’s pick the smallest Carmichael number n = 561. We have:

5^{\frac {n-1} 2} = 5^{280} \equiv 67 \pmod {561}

so there are Carmichael numbers which succumb to the Euler test.

In conclusion, the Euler test is strictly stronger than the Fermat test. Furthermore, it’s a little faster since we only need to compute a^{\frac {n-1} 2} \mod n instead of a^{n-1} \mod n.

blue-lin

Euler Pseudoprimes

As we saw above, even composite n can pass the Euler test for some bases.

Definition.

If n is odd composite and a\ne 1 is such that a^{\frac{n-1}2} \equiv 1 \pmod n, then we say n is an Euler pseudoprime to base a.

Thus from our above example, 10585 is an Euler pseudoprime to bases 2 and 3.

Clearly, if n is an Euler pseudoprime to base a, then it is also a pseudoprime to base a. However, as example 1 above shows, there are pseudoprimes which are not Euler pseudoprimes (for a fixed given base). As example 3 shows, some Carmichael numbers can fail the Euler test, which spells good news for us.

Unfortunately, not all Carmichael numbers can be identified composite by the Euler test. Specifically, there are odd composite n which is an Euler pseudoprime for all a which are coprime to n. Such numbers are known as absolute Euler pseudoprimes. It turns out Chernick’s construction for Carmichael numbers also gives us absolute Euler pseudoprimes.

Exercise

Suppose k is a positive integer such that 6k + 1, 12k + 1 and 18k + 1 are prime. Prove that n := (6k + 1)(12k + 1)(18k + 1) is an absolute Euler pseudoprime.

Thus, we are not quite out of the woods yet.

blue-lin

Rabin-Miller Test

As we noted above, if p is prime then whenever m^2\equiv 1\pmod p we have m \equiv \pm 1 \pmod p. This observation helps us to identify the pseudoprime n = 10585 in example 2.

Indeed, we have 2^{\frac {n-1}2} \equiv 1 \pmod  n. However, since \frac {n-1}2 is even, we can go one step further and check if 2^{\frac {n-1}4} \equiv \pm 1 \pmod n. In our case, we obtain 2^{\frac {n-1}4} \equiv 10294 \not\equiv \pm1 \pmod n and thus we see that n is composite.

This is the gist of the Rabin-Miller test. The idea is that if a^{(n-1)/2^k} \equiv 1 \pmod n and the exponent {\frac {n-1} {2^k}} is even, then we check whether

a^{(n-1)/2^{k+1}} \equiv \pm 1 \pmod n.

If it is not, n must be composite.

Rabin-Miller Test.

Suppose a\ne 1 is a given base and n is odd. Let 2^k be the highest power of 2 dividing n-1 and compute

r := a^{(n-1)/2^k} \mod n.

Perform the following for k-1 iterations.

  1. If r \equiv \pm 1 \pmod n, output PASS.
  2. Let r \leftarrow r^2 \mod n.
  3. If  r \equiv +1 \pmod n, output FAIL.
  4. Go back to step 1.

Example

If we set n = 10585 and a = 2 as above, then k = 3 and \frac{n-1} {2^k} = 1323. Thus we have r = 2^{1323} \mod n = 7958.

During the first iteration, we skip through step 1, set r\leftarrow r^2 \mod n = 10294. Thus we skip step 3 as well.

During the second iteration, we skip through step 1, set r\leftarrow r^2\mod n = 1. Thus step 3 says n fails the test.

blue-lin

Effectiveness of Rabin-Miller

Clearly the Rabin-Miller test is stronger than the Euler test, but just how much stronger is it? There are indeed composite numbers which pass the Rabin-Miller test for specific bases. These are called strong pseudoprimes.

Example

Suppose n = 8321 and a = 2. The highest power of 2 dividing n-1 is 27. Hence we have r = 2^{8320/128} \equiv 8192 \pmod n. The next iteration then gives r \equiv 8192^2 \equiv -1 \pmod n so n passes the Rabin-Miller test to base 2.

On the other hand, one easily checks that n fails the Fermat test for base 3 so it is composite.

Thankfully, we do not have the case of Carmichael numbers here.

Theorem.

If n is odd composite, it will fail the Rabin-Miller test for 75% of a within the range 1 < a < n.

Thus, for a given odd n we randomly pick 1 < a < n for about 20 trials. If n passes all trials, we report that it is most likely prime. Otherwise, if it fails even a single trial, then it is composite. Heuristically, one imagines that the probability of n being composite and passing all trials to be about (\frac 1 4)^{20} = 2^{-40}. In practice 75% is a gross underestimate since for most randomly chosen large n, the Rabin-Miller test will fail for >99% of the bases.

We have here a probabilistic primality testing method, in the sense that if n passes the test, it is overwhelmingly likely to be prime; on the other hand, any failure immediately implies n is composite.

Our confidence in the Rabin-Miller test is further enhanced by the following result.

Theorem (Miller).

Assuming the Generalized Riemann Hypothesis (GRH), if n passes the Rabin-Miller test for all 1 < a < 2(\log n)^2, then it is prime.

Miller noted that the multiplicative group (\mathbb Z/n\mathbb Z)^* is generated by elements bounded by 2(\log n)^2 and thus it suffices to check for all bases in that bound. The conjecture remains open to this day – if you can prove it, you stand to win a million dollars. We will not delve into this topic since the GRH is an extremely deep result. However, we do note that there is overwhelming computational evidence in support of the conjecture and in practice it is reasonable to run the Rabin-Miller test within the above specified bound.

blue-lin

Summary

The Rabin-Miller test is a highly efficient and reliable, albeit probabilistic, primality test. In general, we would like our primality tests to satisfy the following conditions.

  • Deterministic: it can tell with absolute certainty if n is prime.
  • Efficient: its runtime is polynomial in the length of n (i.e. O((log n)d) for some d.
  • Unconditional: it does not assume any open conjecture.

If we run, say, 20 iterations of Rabin-Miller we obtain a probabilistic efficient test, i.e. the second and third conditions are satisfied but not the first. Assuming the GRH, we could test for all bases less than 2(log n)2 and obtain a primality test satisfying the first and second conditions but not the third.

In addition there’s a primality test by Adleman, Pomerance and Rumely which is based on the elliptic curve group. This test is deterministic and unconditional, but its runtime complexity is slightly worse than polynomial time (in log n). Thus, it satisfies the first and third properties but not the second. We may describe this test in a later article.

For years, computer scientists wondered if there is a deterministic, polynomial-time and unconditional primality test. This was finally answered in the affirmative in 2002 by Agrawal, Kayal and Saxena who found a test which satisfied all three conditions. Unfortunately, despite being polynomial in the size of n, the algorithm can only be used on very modestly sized numbers.

blue-lin

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Primality Tests I

Description of Problem

The main problem we wish to discuss is as follows.

Question. Given n, how do we determine if  it is prime?

Prime numbers have opened up huge avenues in theoretical research – the renowned Riemann Hypothesis, for example, is really a statement about the distribution of primes. On the other hand, it was only in the late 70s that people have found applications for them in computer science. Specifically, the RSA asymmetric encryption system requires the software to quickly generate huge prime numbers of several hundred digits. Hence, primality testing is of huge practical importance as well – in fact, without fast primality testing algorithms, asymmetric encryption systems would be totally absent.

[ Current state-of-the-art asymmetric encryption systems include RSA, Diffie-Hellman and elliptic curve cryptography, all of which rely heavily on the ability to generate huge primes quickly, among other things. ]

Curiously, primality testing turns out to be a much simpler problem than the task of factoring, where one needs to factor a given large integer. The current best algorithm for  the latter task, general number field sieve, is extremely involved and requires an understanding of algebraic number theory. In contrast, most primality testing algorithms require only elementary number theory (except for the elliptic curve primality proving method, which I’ve yet to decide if I will cover).

Trial Division

One obvious way to test if a number is prime is trial division. Thus, given n, we iteratively test whether n is divisible by k, for all k\le [\sqrt n].

Why [\sqrt n]? Because if n is divisible by some k, it is also divisible by n/k. Thus we may assume one of the factors to be at most \sqrt n. For example, given 103, we quickly find that it is prime since it is not divisible by 2, 3, …, 10.

In fact, if n is composite, then it is divisible by some prime number less than \sqrt n. However, iterating through prime numbers is computationally difficult so one usually doesn’t bother with that. On the other hand, this gives us a quick way to mentally test if n is prime for n < 400, since we only need to test for possible factors 2, 3, 5, 7, 11, 13, 17, 19.

Trial division is impractical for large numbers, but don’t knock it! When you need to code a quick function to test if a 32-bit number is prime, trial division is the way to go.

blue-lin

Fermat Test

The primary observation comes from the following number-theoretic result:

Fermat’s (Little) Theorem.

If p is prime and a is an integer not divisible by p, then

a^{p-1} \equiv 1 \pmod p.

Thus the contrapositive statement says: if a is an integer not divisible by p and a^{p-1} \not\equiv 1 \pmod p, then p is not prime. This is called the Fermat test with base a. As example 2 below shows, it has its flaws.

Example 1

Consider the integer n = 15943. Picking a = 2, we have:

2^{15942} \equiv 5086 \not\equiv 1\pmod {15943}.

Hence n is composite.

Example 2

Consider the integer n = 10585. Fermat test then gives us

\begin{aligned} 2^{10584} &\equiv 1 \pmod {10585},\\ 3^{10584} &\equiv 1 \pmod {10585}, \\ 5^{10584} &\equiv 4235 \not\equiv 1 \pmod {10585}.\end{aligned}

Hence we see that n is composite. More importantly, this shows that Fermat test can fail for some bases.

Example 3

Let n = 10891. We see that:

2^{10890} \equiv 3^{10890} \equiv 5^{10890} \equiv 7^{10890} \equiv 1 \pmod {10891}.

Hence n appears to be prime. Indeed it is, as you can easily verify.

In summary, we have the following:

Fermat Test for n.

For various positive bases a<n, we check if a^{n-1} \equiv 1 \pmod n. If this fails for any a, we know that n is composite. Otherwise, n is most probably prime.

Exercise

Explain why, in the Fermat test, if we wish to test for all bases < A, it suffices to test for all prime bases < A.

blue-lin

Pseudoprimes

Example 2 above teaches us an important lesson: there are composite n and numbers a≠1 for which a^{n-1}\equiv 1 \pmod n.  Hence we have:

Definition.

If n is composite and a\ne 1 is such that a^{n-1} \equiv 1 \pmod n, then we say n is a pseudoprime with base a.

For a fixed base, pseudoprimes are rather rare. For example, the list of pseudoprimes with base 2 can be obtained on https://oeis.org/A001567 and there are only 22 of them below 10000 and 5597 of them below 10^9 (see http://oeis.org/A055550). Hence given a random huge composite number, chances are high that the first Fermat test will expose it. Put in another way, given a huge random number that passes the first Fermat test, chances are high it’s prime.

This seems to imply that if a large integer n passes (say) 30 Fermat tests, then it’s guaranteed to be prime.

Not really, for we have the following.

Definition.

If n is composite such that for all a coprime to n we have a^{n-1} \equiv 1 \pmod n, then we say n is a Carmichael number.

The smallest Carmichael number is 561 = 3 × 11 × 17.

While such numbers are rare, there are infinitely many of them. [ Fun fact: this conjecture remained open for a long time and was finally proven in 1994, by Alford, Granville and Pomerance. ] Note, however, that among the list of Carmichael numbers, each term seems to have a small prime factor; for instance, 561 is divisible by 3. So maybe we can combine Fermat test with trial division (by small primes) in order to weed out such cases?

No such luck, however. Chernick discovered in 1931 that if k is a positive integer such that 6k+1, 12k+1 and 18k+1 are all prime, then

n = (6+ 1)(12+ 1)(18+ 1)

is a Carmichael number. Now, it remains an open question whether there are infinitely many Carmichael numbers of this form, but in practice (from what we know of density of primes), it is quite easy to construct extremely large Carmichael numbers of this form. For instance, it takes only a few seconds for a Python script to give us the following 301-digit Carmichael number with three 100-digit prime factors:

3678977776333017616618572124346263612335718264220592681275
4323375966931049703503059541656515082721932203861403966236
1707445079748715571482964640305403211055421233151364221297
3982555078692571752850813633662021955795733617868645037712
1505333087445948159695018394505386803232557678106811464742
96899444481

Such a case would have no hope of getting picked up by a combination of Fermat test and trial division. But don’t give up yet, for the story is not over.

Exercises

Prove Chernick’s result. [This is one of those results which are easy to prove, but hard to obtain.]

Extend Chernick’s result to obtain a Carmichael number of >400 digits which has four prime divisors. What about five?

blue-lin

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Polynomials and Representations XXXIX

Some Invariant Theory

We continue the previous discussion. Recall that for \mu = \overline\lambda we have a GL_n\mathbb{C}-equivariant map

\displaystyle \bigotimes_j \text{Alt}^{\mu_j} \mathbb{C}^n \to \bigotimes_i \text{Sym}^{\lambda_i} \mathbb{C}^n \subset\mathbb{C}[z_{i,j}]^{(\lambda_i)}, \quad e_T^\circ \mapsto D_T

which induces an isomorphism between the unique copies of V(\lambda) in both spaces. The kernel Q of this map is spanned by e_T^\circ - \sum_S e_S^\circ for various fillings T with shape \lambda and entries in [n].

E.g. suppose \lambda = (4, 3, 1) and n=5; then \mu = (3, 2, 2,1) and the map induces:

\displaystyle \text{Alt}^3 \mathbb{C}^5 \otimes \text{Alt}^2 \mathbb{C}^5 \otimes \text{Alt}^2 \mathbb{C}^5\otimes \mathbb{C}^5 \longrightarrow \mathbb{C}[z_{1,j}]^{(4)} \otimes \mathbb{C}[z_{2,j}]^{(3)}\otimes \mathbb{C}[z_{3,j}]^{(1)}, \ 1\le j \le 5,

with kernel Q. For the following filling T, we have the correspondence:

example_determinant_and_alt

Lemma. If \mu_j = \mu_{j+1} = \ldots = \mu_{j+m-1}, then the above map factors through

\displaystyle \text{Alt}^{\mu_j}\mathbb{C}^n \otimes \ldots \otimes \text{Alt}^{\mu_{j+m-1}}\mathbb{C}^n\longrightarrow \text{Sym}^m \left(\text{Alt}^{\mu_j} \mathbb{C}^n\right).

E.g. in our example above, the map factors through \text{Alt}^3 \mathbb{C}^5 \otimes \text{Sym}^2 \left(\text{Alt}^2 \mathbb{C}^5 \right)\otimes \mathbb{C}^5.

Proof

Indeed if \mu_j = \mu_{j+1}, then swapping columns j and j+1 of T gives us the same D_T. ♦

blue-lin

Now suppose 0\le a\le n and m\ge 0; pick \lambda = (m, \ldots, m) with length a. Now \mu comprises of m copies of a so by the above lemma, we have a map:

\displaystyle \text{Sym}^m \left(\text{Alt}^a \mathbb{C}^n\right) \longrightarrow \mathbb{C}[z_{1,j}]^{(m)} \otimes \ldots \otimes \mathbb{C}[z_{a,j}]^{(m)} \cong \mathbb{C}[z_{i,j}]^{(m,\ldots,m)}

where 1 \le i \le a and 1 \le j \le n. Taking the direct sum over all m we have:

\displaystyle \text{Sym}^* \left(\text{Alt}^a \mathbb{C}^n\right) := \bigoplus_{m\ge 0} \text{Sym}^m \left(\text{Alt}^a \mathbb{C}^n\right)\longrightarrow \bigoplus_{m\ge 0}\mathbb{C}[z_{i,j}]^{(m,\ldots,m)} \subset \mathbb{C}[z_{i,j}]

which is a homomorphism of GL_n\mathbb{C}-representations. Furthermore, \text{Sym}^* V for any vector space V has an algebra structure via \text{Sym}^m V \times \text{Sym}^n V \to \text{Sym}^{m+n}V. The above map clearly preserves multiplication since multiplying e_T^\circ e_{T'}^\circ and D_T D_{T'} both correspond to concatenation of T and T’. So it is also a homomorphism of \mathbb{C}-algebras.

Question. A basis of \text{Alt}^a\mathbb{C}^n is given by

\displaystyle e_{i_1, \ldots, i_a} := e_{i_1} \wedge \ldots \wedge e_{i_a}

for 1 \le i_1 < \ldots < i_a \le n. Hence \text{Sym}^*\left(\text{Alt}^a \mathbb{C}^n\right) \cong \mathbb{C}[e_{i_1,\ldots,i_a}], the ring of polynomials in n\choose a variables. What is the kernel P of the induced map:

\mathbb{C}[e_{i_1, \ldots, i_a}] \longrightarrow \mathbb{C}[z_{1,1}, \ldots, z_{a,n}]?

Answer

We have seen that for any 1 \le i_1 < \ldots < i_a \le n and 1 \le j_1 < \ldots < j_a \le n we have:

\displaystyle e_{i_1, \ldots, i_a} e_{j_1, \ldots, j_a} = \sum e_{i_1', \ldots, i_a'} e_{j_1', \ldots, j_k', j_{k+1},\ldots, j_a}

where we swap j_1, \ldots, j_k with various sets of k indices in i_1, \ldots, i_a while preserving the order to give (i_1', \ldots, i_a') and (j_1', \ldots, j_k'). Hence, P contains the ideal generated by all such quadratic relations.

On the other hand, any relation e_T = \sum_S e_S is a multiple of such a quadratic equation with a polynomial. This is clear by taking the two columns used in swapping; the remaining columns simply multiply the quadratic relation with a polynomial. Hence P is the ideal generated by these quadratic equations. ♦

Since the quotient of \mathbb{C}[e_{i_1, \ldots, i_a}] by P is a subring of \mathbb{C}[z_{i,j}], we have:

Corollary. The ideal generated by the above quadratic equations is prime.

blue-lin

Fundamental Theorems of Invariant Theory

Recall that g = (g_{i,j}) \in GL_n\mathbb{C} takes z_{i,j} \mapsto \sum_k z_{i,k} g_{k,j}, which is a left action; here 1\le i\le a, 1\le j\le n. We also let GL_a\mathbb{C} act on the right via:

\displaystyle g=(g_{i,j}) \in GL_a\mathbb{C} :z_{i,j} \mapsto \sum_k g_{i,k}z_{k,j}

so that \mathbb{C}[z_{i,j}] becomes a (GL_n\mathbb{C}, GL_a\mathbb{C})-bimodule. A basic problem in invariant theory is to describe the ring \mathbb{C}[z_{i,j}]^{SL_a\mathbb{C}} comprising of all f such that g\cdot f = f for all g\in SL_a\mathbb{C}.

Theorem. The ring \mathbb{C}[z_{i,j}]^{SL_a\mathbb{C}} is the image of:

\displaystyle \mathbb{C}[D_{i_1, \ldots, i_a}] \cong \mathbb{C}[e_{i_1, \ldots, i_a}]/P \hookrightarrow \mathbb{C}[z_{i,j}]

where (i_1, \ldots, i_a) runs over all 1 \le i_1 < \ldots < i_a \le n.

In other words, we have:

  • First Fundamental Theorem : the ring of SL_a\mathbb{C}-invariants in \mathbb{C}[z_{i,j}] is generated by \{D_{i_1, \ldots, i_a}: 1 \le i_1 < \ldots < i_a \le n\}.
  • Second Fundamental Theorem : the relations satisfied by these polynomials are generated by the above quadratic relations.

blue-lin

Proof of Fundamental Theorems

Note that g takes D_{i_1, \ldots, i_a} to:

\displaystyle \det{\small \begin{pmatrix} z_{1, i_1} & z_{1, i_2} & \ldots & z_{1, i_a} \\ z_{2, i_1} & z_{2, i_2} & \ldots & z_{2, i_a} \\ \vdots & \vdots & \ddots & \vdots \\ z_{a, i_1} & z_{a, i_2} & \ldots & z_{a, i_a}\end{pmatrix}} \mapsto \det {\small \begin{pmatrix}\sum_{j_1} g_{1,j_1} z_{j_1, i_1} & \ldots & \sum_{j_a} g_{1,j_a} z_{j_a, i_a} \\ \sum_{j_1} g_{2,j_1} z_{j_1, i_1} & \ldots & \sum_{j_a} g_{2,j_a} z_{j_a, i_a} \\ \vdots & \ddots & \vdots \\ \sum_{j_1} g_{a,j_1} z_{j_1, i_1} & \ldots & \sum_{j_a} g_{a,j_a} z_{j_a, i_a} \end{pmatrix}} = \det(g) D_{i_1, \ldots, i_a}

which is D_{i_1, \ldots, i_a} if g \in SL_a\mathbb{C}. Hence we have \mathbb{C}[D_{i_1, \ldots, i_a}] \subseteq \mathbb{C}[z_{i,j}]^{SL_a\mathbb{C}}. To prove equality, we show that their dimensions in degree d agree. By the previous article, the degree-d component of \mathbb{C}[e_{i_1, \ldots, i_a}]/P has a basis indexed by SSYT of type \lambda = (\frac d a, \ldots, \frac d a) and entries in [n]; if d is not a multiple of a, the component is 0.

Next we check the degree-d component of \mathbb{C}[z_{i,j}]^{SL_a\mathbb{C} }. As GL_a\mathbb{C}-representations, we have

\displaystyle \mathbb{C}[z_{i,j}] \cong \text{Sym}^*\left( (\mathbb{C}^a)^{\oplus n}\right)

where GL_a\mathbb{C} acts on \mathbb{C}^a canonically. Taking the degree-d component, once again this component is 0 if d is not a multiple of a. If a|d, it is the direct sum of \text{Sym}^{d_1} \mathbb{C}^a \otimes \ldots \otimes \text{Sym}^{d_n}\mathbb{C}^a over all d_1 + \ldots + d_n = \frac d a. The \psi of this submodule is h_{\lambda'} = \sum_{\mu'\vdash \frac d a} K_{\mu'\lambda'} s_{\mu'} where \lambda' is the sequence (d_1, \ldots, d_n). Hence

\displaystyle \text{Sym}^{d_1} \mathbb{C}^a \otimes \ldots \otimes \text{Sym}^{d_n}\mathbb{C}^a \cong \bigoplus_{\mu'\vdash \frac d a} V(\mu')^{\oplus K_{\mu'\lambda'}}.

Fix \mu' and sum over all (d_1, \ldots, d_n); we see that the number of copies of V(\mu') is the number of SSYT with shape \mu' and entries in [n]. The key observation is that each V(\mu') is an SL_a\mathbb{C}-irrep.

  • Indeed, \mathbb{C}^* \subset GL_a\mathbb{C} acts as a constant scalar on the whole of V(\mu') since \psi_{V(\mu')} = s_{\mu'} is homogeneous. Hence any SL_a\mathbb{C}-invariant subspace of V(\mu') is also GL_a\mathbb{C}-invariant.

Hence V(\mu')^{SL_a\mathbb{C}} is either the whole space or 0. From the proposition here, it is the whole space if and only if \mu' = (\frac d a, \ldots, \frac d a) with a terms (which corresponds to \det^{d/a}). Hence, the required dimension is the number of SSYT with shape (\frac d a, \ldots) and entries in [n]. ♦

blue-lin

Posted in Uncategorized | Tagged , , , , , | Leave a comment

Polynomials and Representations XXXVIII

Determinant Modules

We will describe another construction for the Schur module.

Introduce variables z_{i,j} for i\ge 1, j\ge 1. For each sequence i_1, \ldots, i_p\ge 1 we define the following polynomials in z_{i,j}:

D_{i_1, \ldots, i_p} := \det{\small \begin{pmatrix} z_{1, i_1} & z_{1, i_2} & \ldots & z_{1, i_p} \\ z_{2, i_1} & z_{2, i_2} & \ldots & z_{2, i_p} \\ \vdots & \vdots & \ddots & \vdots \\ z_{p, i_1} & z_{p, i_2} & \ldots & z_{p, i_p}\end{pmatrix}}.

Now given a filling T of shape λ, we define:

D_T := D_{\text{col}(T, 1)} D_{\text{col}(T, 2)} \ldots

where \text{col}(T, i) is the sequence of entries from the i-th column of T. E.g.

determinant_products_and_filling

Let \mathbb{C}[z_{i,j}] be the ring of polynomials in z_{ij} with complex coefficients. Since we usually take entries of T from [n], we only need to consider the subring \mathbb{C}[z_{i,1}, \ldots, z_{i,n}].

blue-lin

Let \mu = \overline \lambda. Recall from earlier that any non-zero GL_n\mathbb{C}-equivariant map

\displaystyle \bigotimes_j \left(\text{Alt}^{\mu_j} \mathbb{C}^n\right) \longrightarrow \bigotimes_i \left(\text{Sym}^{\lambda_i} \mathbb{C}^n \right)

must induce an isomorphism between the unique copies of V(\lambda) in the source and target spaces. Given any filling T of shape \lambda, we let e^\circ_T be the element of \otimes_j \text{Alt}^{\mu_j} \mathbb{C}^n obtained by replacing each entry k in T by e_k, then taking the wedge of elements in each column, followed by the tensor product across columns:

basis_element_of_alt_tensor_module

Note that the image of e^\circ_T in F(V) is precisely e_T as defined in the last article.

Definition. We take the map

\displaystyle \bigotimes_j \left(\text{Alt}^{\mu_j} \mathbb{C}^n\right) \longrightarrow \bigotimes_i \left(\text{Sym}^{\lambda_i} \mathbb{C}^n \right), \quad e_T^\circ \mapsto D_T

where z_{i,j} belongs to component \text{Sym}^{\lambda_i}.

E.g. in our example above, D_T is homogeneous in z_{1,j} of degree 5, z_{2,j} of degree 4 and z_{3,j} of degree 3. We let g \in GL_n\mathbb{C} act on \mathbb{C}[z_{i,j}] via:

g = (g_{i,j}) : z_{i,j} \mapsto \sum_k z_{i,k}g_{k,j}.

Thus if we fix i and consider the variables \mathbf z_i := \{z_{i,j}\}_j as a row vector, then g: \mathbf z_i \mapsto \mathbf z_i g^t. From another point of view, if we take z_{i,1}, z_{i,2},\ldots as a basis, then the action is represented by matrix g since it takes the standard basis to the column vectors of g.

Proposition. The map is GL_n\mathbb{C}-equivariant.

Proof

The element g = (g_{i,j}) takes e_i \mapsto \sum_j g_{j,i} e_j by taking the column vectors of g; so

\displaystyle e_T \mapsto \sum_{j_1, \ldots, j_d} g_{j_1, i_1} g_{j_2, i_2} \ldots g_{j_d, i_d} e_{T'}

where T’ is the filling obtained from T by replacing its entries i_1, \ldots, i_d with j_1, \ldots, j_d correspondingly.

On the other hand, the determinant D_{i_1, \ldots, i_p} gets mapped to:

\det{\small \begin{pmatrix} z_{1, i_1} & z_{1, i_2} & \ldots & z_{1, i_p} \\ z_{2, i_1} & z_{2, i_2} & \ldots & z_{2, i_p} \\ \vdots & \vdots & \ddots & \vdots \\ z_{p, i_1} & z_{p, i_2} & \ldots & z_{p, i_p}\end{pmatrix}} \mapsto \det{\small \begin{pmatrix} \sum_{j_1} z_{1,j_1} g_{j_1, i_1} & \ldots & \sum_{j_p} z_{1, j_p}g_{j_p i_p}\\ \sum_{j_1}z_{2, j_1} g_{j_1, i_1} & \ldots & \sum_{j_p} z_{2, j_p}g_{j_p, i_p}  \\ \vdots & \ddots & \vdots \\ \sum_{j_1} z_{p, j_1} g_{j_1, i_1} & \ldots & \sum_{j_p} z_{p, j_p} g_{j_p, i_p} \end{pmatrix}}

which is \sum_{j_1, \ldots, j_d} g_{j_1, i_1} \ldots g_{j_d, i_d} D_{T'}. ♦

blue-lin

Since \otimes_j \text{Alt}^{\mu_j} \mathbb{C}^n contains exactly one copy of V(\lambda), it has a unique GL_n\mathbb{C}-submodule Q such that the quotient is isomorphic to V(\lambda). The resulting quotient is thus identical to the Schur module F(V), and the above map factors through

F(V) \to \otimes_i \text{Sym}^{\lambda_i} \mathbb{C}^n, \quad e_T \mapsto D_T.

Now we can apply results from the last article:

Corollary 1. The polynomials D_T satisfy the following:

  • D_T = 0 if T has two identical entries in the same column.
  • D_T + D_{T'} = 0 if T’ is obtained from T by swapping two entries in the same column.
  • D_T = \sum_S D_S, where S takes the set of all fillings obtained from T by swapping a fixed set of k entries in column j’ with arbitrary sets of k entries in column j (for fixed j < j’) while preserving the order.

Proof

Indeed, the above hold when we replace D_T by e_T. Now apply the above linear map. ♦

Corollary 2. The set of D_T, for all SSYT T with shape λ and entries in [n], is linearly independent over \mathbb{C}.

Proof

Indeed, the set of these e_T is linearly independent over \mathbb{C} and the above map is injective. ♦

Example 1.

Consider any bijective filling T for \lambda = (2, 1). Writing out the third relation in corollary 1 gives:

\left[\det\begin{pmatrix} a & c \\ b & d\end{pmatrix}\right] x = \left[\det\begin{pmatrix} x & c \\ y & d\end{pmatrix}\right] a + \left[ \det\begin{pmatrix} a & x \\ b & y\end{pmatrix}\right] c.

More generally, if \lambda satisfies \lambda_j = 2 and \lambda_{j'} = 1, the corresponding third relation is obtained by multiplying the above by a polynomial on both sides.

Example 2: Sylvester’s Identity

Take the 2 \times n SYT by writing 1,\ldots, n in the left column and n+1, \ldots, 2n in the right. Now D_T = D_{1,\ldots, n}D_{n+1, \ldots, 2n} is the product:

\det \overbrace{\begin{pmatrix} z_{1,1} & z_{1,2} & \ldots & z_{1,n} \\ z_{2,1} & z_{2,2} &\ldots & z_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ z_{n,1} & z_{n,2} & \ldots & z_{n,n} \end{pmatrix}}^M \det \overbrace{\begin{pmatrix} z_{1,n+1} & z_{1,n+2} & \ldots & z_{1,2n} \\ z_{2,n+1} & z_{2,n+2} &\ldots & z_{2,2n} \\ \vdots & \vdots & \ddots & \vdots \\ z_{n,n+1} & z_{n,n+2} & \ldots & z_{n,2n} \end{pmatrix}}^N.

In the sum D_T = \sum_S D_S, each summand is of the form D_S= \det M' \det N', where matrices M’N’ are obtained from MN respectively by swapping a fixed set of k columns in N with arbitrary sets of k columns in M while preserving the column order. E.g. for n=3 and k=2, picking the first two columns of N gives:

\begin{aligned} \det ( M_1 | M_2 | M_3) \det(N_1 | N_2| N_3) &= \det(N_1 | N_2 | M_3) \det(M_1 | M_2 | N_3) \\ +\det(N_1 | M_2 | N_2) \det(M_1 | M_3 | N_3) &+ \det(M_1 | N_1 | N_2) \det(M_2 | M_3 | N_3).\end{aligned}

blue-lin

Posted in Uncategorized | Tagged , , , , , , | Leave a comment