Tag: permutation representation

Galois’ last letter

Published June 12, 2008 by lieven

“Ne pleure pas, Alfred ! J’ai besoin de tout mon courage pour mourir à vingt ans!”

We all remember the last words of Evariste Galois to his brother Alfred. Lesser known are the mathematical results contained in his last letter, written to his friend Auguste Chevalier, on the eve of his fatal duel. Here the final sentences :

Tu prieras publiquement Jacobi ou Gauss de donner leur avis non sur la verite, mais sur l’importance des theoremes.
Apres cela il se trouvera, j’espere, des gens qui trouvent leur profis a dechiffrer tout ce gachis.
Je t’embrasse avec effusion.
E. Galois, le 29 Mai 1832

A major result contained in this letter concerns the groups $L_{2} (p) = P S L_{2} (F_{p})$ , that is the group of $2 \times 2$ matrices with determinant equal to one over the finite field $F_{p}$ modulo its center. $L_{2} (p)$ is known to be simple whenever $p \geq 5$ . Galois writes that $L_{2} (p)$ cannot have a non-trivial permutation representation on fewer than $p + 1$ symbols whenever $p > 11$ and indicates the transitive permutation representation on exactly $p$ symbols in the three ‘exceptional’ cases $p = 5, 7, 11$ .

Let $α = [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}]$ and consider for $p = 5, 7, 11$ the involutions on $P_{F_{p}}^{1} = F_{p} \cup \infty$ (on which $L_{2} (p)$ acts via Moebius transformations)

$π_{5} = (0, \infty) (1, 4) (2, 3) π_{7} = (0, \infty) (1, 3) (2, 6) (4, 5) π_{11} = (0, \infty) (1, 6) (3, 7) (9, 10) (5, 8) (4, 2)$

(in fact, Galois uses the involution $(0, \infty) (1, 2) (3, 6) (4, 8) (5, 10) (9, 7)$ for $p = 11$ ), then $L_{2} (p)$ leaves invariant the set consisting of the $p$ involutions $Π = α^{- i} π_{p} α^{i} : 1 \leq i \leq p$ . After mentioning these involutions Galois merely writes :

Ainsi pour le cas de $p = 5, 7, 11$ , l’equation modulaire s’abaisse au degre p.
En toute rigueur, cette reduction n’est pas possible dans les cas plus eleves.

Alternatively, one can deduce these permutation representation representations from group isomorphisms. As $L_{2} (5) ≃ A_{5}$ , the alternating group on 5 symbols, $L_{2} (5)$ clearly acts transitively on 5 symbols.

Similarly, for $p = 7$ we have $L_{2} (7) ≃ L_{3} (2)$ and so the group acts as automorphisms on the projective plane over the field on two elements $P_{F_{2}}^{2}$ aka the Fano plane, as depicted on the left.

This finite projective plane has 7 points and 7 lines and $L_{3} (2)$ acts transitively on them.

For $p = 11$ the geometrical object is a bit more involved. The set of non-squares in $F_{11}$ is

$1, 3, 4, 5, 9$

and if we translate this set using the additive structure in $F_{11}$ one obtains the following 11 five-element sets

$1, 3, 4, 5, 9, 2, 4, 5, 6, 10, 3, 5, 6, 7, 11, 1, 4, 6, 7, 8, 2, 5, 7, 8, 9, 3, 6, 8, 9, 10,$

$4, 7, 9, 10, 11, 1, 5, 8, 10, 11, 1, 2, 6, 9, 11, 1, 2, 3, 7, 10, 2, 3, 4, 8, 11$

and if we regard these sets as ‘lines’ we see that two distinct lines intersect in exactly 2 points and that any two distinct points lie on exactly two ‘lines’. That is, intersection sets up a bijection between the 55-element set of all pairs of distinct points and the 55-element set of all pairs of distinct ‘lines’. This is called the biplane geometry.

The subgroup of $S_{11}$ (acting on the eleven elements of $F_{11}$ ) stabilizing this set of 11 5-element sets is precisely the group $L_{2} (11)$ giving the permutation representation on 11 objects.

An alternative statement of Galois’ result is that for $p > 11$ there is no subgroup of $L_{2} (p)$ complementary to the cyclic subgroup

$C_{p} = [\begin{matrix} 1 & x \\ 0 & 1 \end{matrix}] : x \in F_{p}$

That is, there is no subgroup such that set-theoretically $L_{2} (p) = F \times C_{p}$ (note this is of courese not a group-product, all it says is that any element can be written as $g = f . c$ with $f \in F, c \in C_{p}$ .

However, in the three exceptional cases we do have complementary subgroups. In fact, set-theoretically we have

$L_{2} (5) = A_{4} \times C_{5} L_{2} (7) = S_{4} \times C_{7} L_{2} (11) = A_{5} \times C_{11}$

and it is a truly amazing fact that the three groups appearing are precisely the three Platonic groups!

Recall that here are 5 Platonic (or Scottish) solids coming in three sorts when it comes to rotation-automorphism groups : the tetrahedron (group $A_{4}$ ), the cube and octahedron (group $S_{4}$ ) and the dodecahedron and icosahedron (group $A_{5}$ ). The “4” in the cube are the four body diagonals and the “5” in the dodecahedron are the five inscribed cubes.

That is, our three ‘exceptional’ Galois-groups correspond to the three Platonic groups, which in turn correspond to the three exceptional Lie algebras $E_{6}, E_{7}, E_{8}$ via McKay correspondence (wrt. their 2-fold covers). Maybe I’ll detail this latter connection another time. It sure seems that surprises often come in triples…

Finally, it is well known that $L_{2} (5) ≃ A_{5}$ is the automorphism group of the icosahedron (or dodecahedron) and that $L_{2} (7)$ is the automorphism group of the Klein quartic.

So, one might ask : is there also a nice curve connected with the third group $L_{2} (11)$ ? Rumour has it that this is indeed the case and that the curve in question has genus 70… (to be continued).

Reference

Bertram Kostant, “The graph of the truncated icosahedron and the last letter of Galois”

Farey symbols of sporadic groups

Published March 20, 2008 by lieven

John Conway once wrote :

There are almost as many different constructions of $M_{24}$ as there have been mathematicians interested in that most remarkable of all finite groups.

In the inguanodon post Ive added yet another construction of the Mathieu groups $M_{12}$ and $M_{24}$ starting from (half of) the Farey sequences and the associated cuboid tree diagram obtained by demanding that all edges are odd. In this way the Mathieu groups turned out to be part of a (conjecturally) infinite sequence of simple groups, starting as follows :

$L_{2} (7), M_{12}, A_{16}, M_{24}, A_{28}, A_{40}, A_{48}, A_{60}, A_{68}, A_{88}, A_{96}, A_{120}, A_{132}, A_{148}, A_{164}, A_{196}, \dots$

It is quite easy to show that none of the other sporadics will appear in this sequence via their known permutation representations. Still, several of the sporadic simple groups are generated by an element of order two and one of order three, so they are determined by a finite dimensional permutation representation of the modular group $P S L_{2} (Z)$ and hence are hiding in a special polygonal region of the Dedekind’s tessellation

Let us try to figure out where the sporadic with the next simplest permutation representation is hiding : the second Janko group $J_{2}$ , via its 100-dimensional permutation representation. The Atlas tells us that the order two and three generators act as

e:= (1,84)(2,20)(3,48)(4,56)(5,82)(6,67)(7,55)(8,41)(9,35)(10,40)(11,78)(12, 100)(13,49)(14,37)(15,94)(16,76)(17,19)(18,44)(21,34)(22,85)(23,92)(24, 57)(25,75)(26,28)(27,64)(29,90)(30,97)(31,38)(32,68)(33,69)(36,53)(39,61) (42,73)(43,91)(45,86)(46,81)(47,89)(50,93)(51,96)(52,72)(54,74)(58,99) (59,95)(60,63)(62,83)(65,70)(66,88)(71,87)(77,98)(79,80);

v:= (1,80,22)(2,9,11)(3,53,87)(4,23,78)(5,51,18)(6,37,24)(8,27,60)(10,62,47) (12,65,31)(13,64,19)(14,61,52)(15,98,25)(16,73,32)(17,39,33)(20,97,58) (21,96,67)(26,93,99)(28,57,35)(29,71,55)(30,69,45)(34,86,82)(38,59,94) (40,43,91)(42,68,44)(46,85,89)(48,76,90)(49,92,77)(50,66,88)(54,95,56) (63,74,72)(70,81,75)(79,100,83);

But as the kfarey.sage package written by Chris Kurth calculates the Farey symbol using the L-R generators, we use GAP to find those

L = e*v^-1  and  R=e*v^-2 so

L=(1,84,22,46,70,12,79)(2,58,93,88,50,26,35)(3,90,55,7,71,53,36)(4,95,38,65,75,98,92)(5,86,69,39,14,6,96)(8,41,60,72,61,17, 64)(9,57,37,52,74,56,78)(10,91,40,47,85,80,83)(11,23,49,19,33,30,20)(13,77,15,59,54,63,27)(16,48,87,29,76,32,42)(18,68, 73,44,51,21,82)(24,28,99,97,45,34,67)(25,81,89,62,100,31,94)

R=(1,84,80,100,65,81,85)(2,97,69,17,13,92,78)(3,76,73,68,16,90,71)(4,54,72,14,24,35,11)(5,34,96,18,42,32,44)(6,21,86,30,58, 26,57)(7,29,48,53,36,87,55)(8,41,27,19,39,52,63)(9,28,93,66,50,99,20)(10,43,40,62,79,22,89)(12,83,47,46,75,15,38)(23,77, 25,70,31,59,56)(33,45,82,51,67,37,61)(49,64,60,74,95,94,98)

Defining these permutations in sage and using kfarey, this gives us the Farey-symbol of the associated permutation representation

L=SymmetricGroup(Integer(100))("(1,84,22,46,70,12,79)(2,58,93,88,50,26,35)(3,90,55,7,71,53,36)(4,95,38,65,75,98,92)(5,86,69,39,14,6,96)(8,41,60,72,61,17, 64)(9,57,37,52,74,56,78)(10,91,40,47,85,80,83)(11,23,49,19,33,30,20)(13,77,15,59,54,63,27)(16,48,87,29,76,32,42)(18,68, 73,44,51,21,82)(24,28,99,97,45,34,67)(25,81,89,62,100,31,94)")

R=SymmetricGroup(Integer(100))("(1,84,80,100,65,81,85)(2,97,69,17,13,92,78)(3,76,73,68,16,90,71)(4,54,72,14,24,35,11)(5,34,96,18,42,32,44)(6,21,86,30,58, 26,57)(7,29,48,53,36,87,55)(8,41,27,19,39,52,63)(9,28,93,66,50,99,20)(10,43,40,62,79,22,89)(12,83,47,46,75,15,38)(23,77, 25,70,31,59,56)(33,45,82,51,67,37,61)(49,64,60,74,95,94,98)")

sage: FareySymbol("Perm",[L,R])

[[0, 1, 4, 3, 2, 5, 18, 13, 21, 71, 121, 413, 292, 463, 171, 50, 29, 8, 27, 46, 65, 19, 30, 11, 3, 10, 37, 64, 27, 17, 7, 4, 5], [1, 1, 3, 2, 1, 2, 7, 5, 8, 27, 46, 157, 111, 176, 65, 19, 11, 3, 10, 17, 24, 7, 11, 4, 1, 3, 11, 19, 8, 5, 2, 1, 1], [-3, 1, 4, 4, 2, 3, 6, -3, 7, 13, 14, 15, -3, -3, 15, 14, 11, 8, 8, 10, 12, 12, 10, 9, 5, 5, 9, 11, 13, 7, 6, 3, 2, 1]]

Here, the first string gives the numerators of the cusps, the second the denominators and the third gives the pairing information (where [tex[-2 $d e n o t e s a n e v e n e d g e a n d$ -3 $ an odd edge. Fortunately, kfarey also allows us to draw the special polygonal region determined by a Farey-symbol. So, here it is (without the pairing data) :

the hiding place of $J_{2}$ …

It would be nice to have (a) other Farey-symbols associated to the second Janko group, hopefully showing a pattern that one can extend into an infinite family as in the inguanodon series and (b) to determine Farey-symbols of more sporadic groups.

Quiver-superpotentials

Published January 14, 2008 by lieven

It’s been a while, so let’s include a recap : a (transitive) permutation representation of the modular group $Γ = P S L_{2} (Z)$ is determined by the conjugacy class of a cofinite subgroup $Λ \subset Γ$ , or equivalently, to a dessin d’enfant. We have introduced a quiver (aka an oriented graph) which comes from a triangulation of the compactification of $H / Λ$ where $H$ is the hyperbolic upper half-plane. This quiver is independent of the chosen embedding of the dessin in the Dedeking tessellation. (For more on these terms and constructions, please consult the series Modular subgroups and Dessins d’enfants).

Why are quivers useful? To start, any quiver $Q$ defines a noncommutative algebra, the path algebra $C Q$ , which has as a $C$ -basis all oriented paths in the quiver and multiplication is induced by concatenation of paths (when possible, or zero otherwise). Usually, it is quite hard to make actual computations in noncommutative algebras, but in the case of path algebras you can just see what happens.

Moreover, we can also see the finite dimensional representations of this algebra $C Q$ . Up to isomorphism they are all of the following form : at each vertex $v_{i}$ of the quiver one places a finite dimensional vectorspace $C^{d_{i}}$ and any arrow in the quiver
[tex]\xymatrix{\vtx{v_i} \ar[r]^a & \vtx{v_j}}[/tex] determines a linear map between these vertex spaces, that is, to $a$ corresponds a matrix in $M_{d_{j} \times d_{i}} (C)$ . These matrices determine how the paths of length one act on the representation, longer paths act via multiplcation of matrices along the oriented path.

A necklace in the quiver is a closed oriented path in the quiver up to cyclic permutation of the arrows making up the cycle. That is, we are free to choose the start (and end) point of the cycle. For example, in the one-cycle quiver

[tex]\xymatrix{\vtx{} \ar[rr]^a & & \vtx{} \ar[ld]^b \ & \vtx{} \ar[lu]^c &}[/tex]

the basic necklace can be represented as $a b c$ or $b c a$ or $c a b$ . How does a necklace act on a representation? Well, the matrix-multiplication of the matrices corresponding to the arrows gives a square matrix in each of the vertices in the cycle. Though the dimensions of this matrix may vary from vertex to vertex, what does not change (and hence is a property of the necklace rather than of the particular choice of cycle) is the trace of this matrix. That is, necklaces give complex-valued functions on representations of $C Q$ and by a result of Artin and Procesi there are enough of them to distinguish isoclasses of (semi)simple representations! That is, linear combinations a necklaces (aka super-potentials) can be viewed, after taking traces, as complex-valued functions on all representations (similar to character-functions).

In physics, one views these functions as potentials and it then interested in the points (representations) where this function is extremal (minimal) : the vacua. Clearly, this does not make much sense in the complex-case but is relevant when we look at the real-case (where we look at skew-Hermitian matrices rather than all matrices). A motivating example (the Yang-Mills potential) is given in Example 2.3.2 of Victor Ginzburg’s paper Calabi-Yau algebras.

Let $Φ$ be a super-potential (again, a linear combination of necklaces) then our commutative intuition tells us that extrema correspond to zeroes of all partial differentials $\frac{\partial Φ}{\partial a}$ where $a$ runs over all coordinates (in our case, the arrows of the quiver). One can make sense of differentials of necklaces (and super-potentials) as follows : the partial differential with respect to an arrow $a$ occurring in a term of $Φ$ is defined to be the path in the quiver one obtains by removing all 1-occurrences of $a$ in the necklaces (defining $Φ$ ) and rearranging terms to get a maximal broken necklace (using the cyclic property of necklaces). An example, for the cyclic quiver above let us take as super-potential $a b c a b c$ (2 cyclic turns), then for example

$\frac{\partial Φ}{\partial b} = c a b c a + c a b c a = 2 c a b c a$

(the first term corresponds to the first occurrence of $b$ , the second to the second). Okay, but then the vacua-representations will be the representations of the quotient-algebra (which I like to call the vacualgebra)

$U (Q, Φ) = \frac{C Q}{(\partial Φ / \partial a, \forall a)}$

which in ‘physical relevant settings’ (whatever that means…) turn out to be Calabi-Yau algebras.

But, let us return to the case of subgroups of the modular group and their quivers. Do we have a natural super-potential in this case? Well yes, the quiver encoded a triangulation of the compactification of $H / Λ$ and if we choose an orientation it turns out that all ‘black’ triangles (with respect to the Dedekind tessellation) have their arrow-sides defining a necklace, whereas for the ‘white’ triangles the reverse orientation makes the arrow-sides into a necklace. Hence, it makes sense to look at the cubic superpotential $Φ$ being the sum over all triangle-sides-necklaces with a +1-coefficient for the black triangles and a -1-coefficient for the white ones. Let’s consider an index three example from a previous post

[tex]\xymatrix{& & \rho \ar[lld]_d \ar[ld]^f \ar[rd]^e & \
i \ar[rrd]_a & i+1 \ar[rd]^b & & \omega \ar[ld]^c \
& & 0 \ar[uu]^h \ar@/^/[uu]^g \ar@/_/[uu]_i &}[/tex]

In this case the super-potential coming from the triangulation is

$Φ = - a i d + a g d - c g e + c h e - b h f + b i f$

and therefore we have a noncommutative algebra $U (Q, Φ)$ associated to this index 3 subgroup. Contrary to what I believed at the start of this series, the algebras one obtains in this way from dessins d’enfants are far from being Calabi-Yau (in whatever definition). For example, using a GAP-program written by Raf Bocklandt Ive checked that the growth rate of the above algebra is similar to that of $C [x]$ , so in this case $U (Q, Φ)$ can be viewed as a noncommutative curve (with singularities).

However, this is not the case for all such algebras. For example, the vacualgebra associated to the second index three subgroup (whose fundamental domain and quiver were depicted at the end of this post) has growth rate similar to that of $C ⟨ x, y ⟩$ …

I have an outlandish conjecture about the growth-behavior of all algebras $U (Q, Φ)$ coming from dessins d’enfants : the algebra sees what the monodromy representation of the dessin sees of the modular group (or of the third braid group).
I can make this more precise, but perhaps it is wiser to calculate one or two further examples…