## Introduction

Consider the following simple problem.

Prove that the shape on the left cannot be completely tiled by 20 polygons of the types shown on the right.

The solution is rather simple: colour the shape in the following manner.

This gives 18 green hexagons, 21 orange hexagons and 21 blue hexagons. On the other hand, each triangular piece must cover three hexagons of distinct colours. Hence, if we could tile the figure completely with 20 pieces, we would have 20 hexagons of each colour, which is a contradiction. Thus such a tiling is impossible. ♦

### Harder Variation

Now suppose we replace the above shape with the following.

It is still impossible to tile it with the two types of pieces as above. However, the colouring method fails to prove it since we would obtain an equal number of hexagons of each colour. Thus we need a better method.

The following technique can be generalized to prove that a similar shape of size N is tileable if and only if

$N \equiv 0, 2, 9, 11 \pmod{12}.$

## Conway-Lagarias Method

Here, we will present the solution by John H. Conway and Jeffrey C. Lagarias in their paper “Tiling with polyominoes and combinatorial group theory” (1990). First we convert the problem to an equivalent one with polyominoes. We need to show that it is impossible to tile the left polyomino with the two triangular ones on the right (no rotation allowed).

### Free Group on Two Generators

Let F be the free group on the two-element set {xy}. To describe it concretely, we consider the set of all words in $\{x, y, x^{-1}, y^{-1}\}.$ Reduction in a word occurs when we remove two neighbouring occurrences of $\{x, x^{-1}\}$ and $\{y, y^{-1}\}.$ E.g.

$xyyx^{-1}y^{-1}\overbrace{xx^{-1}}yy \mapsto xyyx^{-1}\overbrace{y^{-1}y}y \mapsto xyyx^{-1}y.$

A word is said to be reduced if no further reduction is possible. Now we can write F as the set of all reduced words in $\{x, y, x^{-1}, y^{-1}\}.$

• Group composition in F corresponds to concatenation of words with reduction. For instance,

$g = x^{-1}y xx y^{-1}, g' = yx^{-1}yy x \implies gg' = (x^{-1}y xx y^{-1})(yx^{-1}yy x) = x^{-1}yxyy x.$

• The group identity is the empty word.
• To obtain the inverse of a word, we reverse the order and replace each $x$ (resp. $y$) by $x^{-1}$ (resp. $y^{-1}$) and vice versa. E.g. $(xyxx y^{-1})^{-1} = yx^{-1}x^{-1}y^{-1}x^{-1}.$

For convenience, we write $x^m$ for m neighbouring copies of x and $x^{-m}$ for m neighbouring copies of $x^{-1},$ and similarly for $y^m, y^{-m}.$ Thus $x^2 y^{-3} x$ is shorthand for $xxy^{-1}y^{-1}y^{-1}x.$

## Polyominoes and Words

Now for each polyomino above, we obtain an element of F as follows. Start with a base point on the perimeter. We trace around the perimeter in a counter-clockwise direction, write $x, x^{-1}, y, y^{-1}$ for the directions of right, left, up, down respectively, and record the loop as a word upon returning to the base point.

For the large triangular figure, we pick the bottom-left corner as the base point and obtain the following word:

$c := x^{8} (y x^{-1})^{8}y^{-8}.$

### Change of Base Points

Now our definition of $a, b, c\in F$ depends on our choice of base points. Let’s see what happens to $a\in F$ when we switch to a different point on the perimeter. Let $g\in F$ correspond to the path from the old base point to the new along the perimeter, and let $a' \in F$ be the new loop. Then from the diagram:

we have $a' = g^{-1}ag$ in the group F.

In other words, if we change the base point, the new loop is a conjugate of the old one.

## Tiling

The process of tiling can be converted to a statement about group product. Suppose we place the two figures together as follows:

The perimeter for A is represented by $ag$ (or a conjugate) while that for B is represented by $g^{-1}b.$ Hence the resulting diagram has perimeter $ab$ which is the product of the words for A and B in the group F.

Summary.

Suppose polygons $P_1, P_2, \ldots$ are represented by words $w_1, w_2, \ldots$. Upon tiling $P_1, P_2, \ldots$, the resulting perimeter is represented by a word which can be obtained from $w_1, w_2, \ldots$ via conjugation and composition.

### Example

Thus, if our large triangular polyomino can be tiled by the smaller pieces, then $c = x^{8} (y x^{-1})^{8}y^{-8} \in F$ lies in the normal subgroup N generated by a and b. This will be exploited in our proof.

## Proving Our Main Result

We will construct a normal subgroup K of F such that $N\le K \le F$.

### Step 1: Map each word in F to a computer program.

Suppose we have a robot which starts by facing a certain direction (e.g. north). For each element in F, we turn it into a computer program by reading the word from left to right:

• $x$: turn right 60°, walk forward 1m, then turn right 60° again.
• $x^{-1}$: turn left 60°, walk backward 1m, then turn left 60° again.
• $y$: turn left 60°, walk forward 1m, then turn left 60° again.
• $y^{-1}$: turn right 60°, walk backward 1m, then turn right 60° again.

Let K be the set of all words in F which bring the robot back to its original position and orientation. Note that K is closed under composition and inverse so it is a subgroup of F.  Furthermore, it is a normal subgroup since if $g\in F$ and $h\in K$, then $ghg^{-1}$ is the program which does g, then (which has no nett effect on the robot), then the reverse of g.

### Step 2: Show that a, b and c are in K.

Indeed, for a and b we have:

Likewise it is easy to verify that $x^3, y^3, (yx^{-1})^3 \in K.$

For c, we let $\pi : F \to F/K$ be the canonical homomorphism. Since $\pi(x^3) = \pi(y^3) = \pi(yx^{-1})^3= \pi(a) = \pi(b) = e$ we have:

\begin{aligned}\pi(c) &= \pi(x)^{8}\left(\pi(yx^{-1})\right)^{8}\pi(y)^{-8}\\ &= \pi(x)^2 \pi(yx^{-1})^2\pi(y)^{-2}\\ &= \pi(a) = e.\end{aligned}

In particular, we have $N\le K$.

### Step 3: Plot possible paths for the robot.

One easily sees that the robot must travel along the following lines:

The robot’s direction is indicated by the arrow in each disc; thus, it can only face in at most one direction at any spot. If the next instruction is x, the robot travels on the perimeter of a yellow triangle, along the given x orientation. If it is x-1, the robot travels along the perimeter of a yellow triangle, counter to the given x orientation. The same holds for y and y-1, but with the blue triangle.

### Step 4: Define a homomorphism $\Phi : K \to \mathbb{Z}.$

Since each $g\in K$ is a closed path, we may define $\Phi(g)$ to be the number of hexagons enclosed by the path. Here, the counting is oriented counter-clockwise – a loop which encloses a hexagon is counted +1 if the loop is counter-clockwise and -1 otherwise. This gives the desired homomorphism $\Phi : K \to \mathbb{Z}.$ We have

$\Phi(x^3) = \Phi(y^3) = 0,\quad \Phi((yx^{-1})^3) =-1,$

$\Phi(a) = -1,\quad \Phi(b) = +1,$

and thus we have

\begin{aligned}\Phi(c) &= \overbrace{\Phi(x^6)}^0 + \Phi(x^2 (yx^{-1})^8 y^{-2}) +\overbrace{\Phi(y^{-6})}^0 = \Phi(y^{-2}x^2(yx^{-1})^8) \\ &= \Phi(y^{-2} x^2 (yx^{-1})^2) - 2= -3\end{aligned}.

Now if the original tiling were possible, we would require $\frac 1 3 \frac{8 \times 9}2 = 12$ pieces. Hence c is obtained from the product of 12 conjugates of a and b (in F). Since K is normal in F, each conjugate a’ of a lies in K and furthermore $\Phi(a') = \Phi(a) = -1.$ Likewise $\Phi(b') = \Phi(b) = +1$ for any conjugate b’ of b in F. From this, it follows that $\Phi(c)$ is even, which contradicts $\Phi(c) = -3$.

Thus our proof is complete. ♦

## 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.

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 Topspin 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. 😦

## 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:

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.

## 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:

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:

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

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:

## 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 = 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 the filled entries on that row, 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.

## 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.

[ 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.

## 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.

[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.

## 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.

## 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:

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}\}.$

## 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\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. ♦

## 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.

## Sims Filter

Sims Filter achieves the following.

Given a set $A \subseteq S_n$, there is an effective algorithm to replace $A$ by some $B\subseteq S_n$ satisfying $\left = \left$ 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.$

Now we will construct a set B such that $\left = \left$ 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. 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.

## 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$ and $H = \left$, 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.$

## 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.

## 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. ♦

## 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.

## 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.

## 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$.

## 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.

## 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.

## 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.

## 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.

## 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.

## 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, 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.

## 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?

## 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:

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$. ♦

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}]?$

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.

## 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.

## 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]. ♦