4
$\begingroup$

I would like to find ($24\times 24$) matrices representing the various conjugacy classes of Conway's group $\mathrm{Co}_0$ acting on the Leech lattice in the usual coordinate system given by the MOG. Have such matrices been computed and are they somewhere to be found? Or is it somehow possible to perform this computation using GAP?

I believe the following GAP code should, in principle, compute what I want. But in practice, this straightforward approach does not seem to be feasible (i.e., merely asking for Order(dot0_group) seems to take forever):

## The MOG cells are labeled top to bottom and left to right:
## so the leftmost column is 1,2,3,4 and the rightmost is 21,22,23,24,
## whereas the top line is 1,5,9,13,17,21.
rotate_blocks := (1,9,17)(2,10,18)(3,11,19)(4,12,20)(5,13,21)(6,14,22)(7,15,23)(8,16,24);
flip_blocks12 := (1,5)(2,6)(3,7)(4,8)(9,13)(10,14)(11,15)(12,16);
omega_cols := (2,3,4)(6,7,8)(10,11,12)(14,15,16)(18,19,20)(22,23,24);
myflip := (1,8)(2,4)(3,5)(6,7)(9,17)(10,18)(13,21)(14,22);
m24_group := Group([rotate_blocks, flip_blocks12, omega_cols, myflip]);

rotate_blocks_mat := PermutationMat(rotate_blocks, 24);
flip_blocks12_mat := PermutationMat(flip_blocks12, 24);
omega_cols_mat := PermutationMat(omega_cols, 24);
myflip_mat := PermutationMat(myflip, 24);

conway_eta := List([1..24], i->List([1..24], function(j) if QuoInt(i-1,4)=QuoInt(j-1,4) then if i=j then return 1/2; else return -1/2; fi; else return 0; fi; end));
conway_xi := conway_eta * List([1..24], i->List([1..24], function(j) if i=j then if i>=1 and i<=4 then return -1; else return 1; fi; else return 0; fi; end));

dot0_group := Group([rotate_blocks_mat, flip_blocks12_mat, omega_cols_mat, myflip_mat, conway_xi]);
lst := ConjugacyClasses(dot0_group);

I know very little about computational group theory, so I have no idea whether this is simply hopeless or whether a different approach (e.g., representing elements as permutations of length $196\,560$) can succeed.

$\endgroup$
4
  • 1
    $\begingroup$ Computing the order of $G$ and the conjugacy classes is faster for the permutation representation, you can find generators in the online ATLAS. I tried and I was able to use this permutation representation to compute the order and representatives for the conjugacy classes using MAGMA, with a slow computer this took around 10 minutes. Maybe there are better ways to do this, but you could then write the representatives in terms of the generators, and then use the matrix representation from the online ATLAS to get matrices. $\endgroup$
    – spin
    Aug 10, 2019 at 20:24
  • 1
    $\begingroup$ @spin Thanks, I will try that. I have a hard time accepting the fact that permutations so large can be more usable that $24\times 24$ matrices, but I guess permutation group algorithms are truly magical. $\endgroup$
    – Gro-Tsen
    Aug 10, 2019 at 20:31
  • 2
    $\begingroup$ I am not so familiar with how the algorithms work precisely, an expert on computational group theory could explain this better. But here although the permutations are large, there is a small base: for example $B = \{1,2,3,5,6134\}$ for a base. Here $B = \{b_1, \ldots, b_n\}$ is a base if $\cap_{i = 1}^n G_{b_i} = 1$. Then the action of any $g \in G$ is determined by $g(b)$ for $b \in B$, so by action on just five points in this case. Also, you can compute the order as $|G| = \prod_{i = 1}^n[G_{i-1}:G_{i}]$ where $G_0 = G$ and $G_i = \cap_{j = 1}^i G_{b_j}$ for $i > 0$. $\endgroup$
    – spin
    Aug 10, 2019 at 21:27
  • 1
    $\begingroup$ It seems that GAP can indeed handle the group, and compute the conjugacy classes, in its permutation representation. I will answer my own question once I have tidied up the code a little bit. $\endgroup$
    – Gro-Tsen
    Aug 11, 2019 at 1:04

1 Answer 1

2
$\begingroup$

It turns out that, as spin suggested in the comments, representing elements of $\mathrm{Co}_0$ as permutations of $196\,560$ elements (the first shell of the Leech lattice) is computationally feasible and that, with this representation, GAP is able to list the conjugacy classes, which are then easily converted back to matrices. I wrote the following code (expanding on the one given in the question) which computes the list of representative matrices — in less than half an hour on my PC — and dumps it out to a file:

#### Start gap with enough memory (e.g., "gap -o 8g" for 8GB) to run this.

## The MOG cells are labeled top to bottom and left to right:
## so the leftmost column is 1,2,3,4 and the rightmost is 21,22,23,24,
## whereas the top line is 1,5,9,13,17,21.

## Generators of the Mathieu group M_24:
rotate_blocks := (1,9,17)(2,10,18)(3,11,19)(4,12,20)(5,13,21)(6,14,22)(7,15,23)(8,16,24);
flip_blocks12 := (1,5)(2,6)(3,7)(4,8)(9,13)(10,14)(11,15)(12,16);
omega_cols := (2,3,4)(6,7,8)(10,11,12)(14,15,16)(18,19,20)(22,23,24);
myflip := (1,8)(2,4)(3,5)(6,7)(9,17)(10,18)(13,21)(14,22);
m24_group := Group([rotate_blocks, flip_blocks12, omega_cols, myflip]);

## The same permutations as matrices:
rotate_blocks_mat := PermutationMat(rotate_blocks, 24);
flip_blocks12_mat := PermutationMat(flip_blocks12, 24);
omega_cols_mat := PermutationMat(omega_cols, 24);
myflip_mat := PermutationMat(myflip, 24);

## Conway's xi generator first subtracts from each column half the sum
## of all its cells (this is eta), then takes the negative of one block:
conway_eta := List([1..24], i->List([1..24], function(j) if QuoInt(i-1,4)=QuoInt(j-1,4) then if i=j then return 1/2; else return -1/2; fi; else return 0; fi; end));;
conway_xi := conway_eta * List([1..24], i->List([1..24], function(j) if i=j then if i>=1 and i<=4 then return -1; else return 1; fi; else return 0; fi; end));

## Conway's group Co_0 as a group of matrices (too unwieldly for GAP):
co0_mat := Group([rotate_blocks_mat, flip_blocks12_mat, omega_cols_mat, myflip_mat, conway_xi]);

## The orbit of an element of the Leech lattice (this should have size 196560):
orb := Orbit(co0_mat, List([1..24], function(i) if i=1 or i=5 then return 4; else return 0; fi; end));;
Size(orb);  ## Should return 196560

## The action homomorphism (makes elements of Co_0 into permutations):
phi := ActionHomomorphism(co0_mat, orb);

## The five generators, this time as permutations on orb (of size 196560):
rotate_blocks_l := Image(phi, rotate_blocks_mat);;
flip_blocks12_l := Image(phi, flip_blocks12_mat);;
omega_cols_l := Image(phi, omega_cols_mat);;
myflip_l := Image(phi, myflip_mat);;
conway_xi_l := Image(phi, conway_xi);;

## Now Co_0 as a permutation group:
co0 := Group([rotate_blocks_l, flip_blocks12_l, omega_cols_l, myflip_l, conway_xi_l]);

## Check its order and compute its conjugacy classes (this is fairly long):
Order(co0);  ## Should return 8315553613086720000
lst_cl := ConjugacyClasses(co0);;  ## Takes about 35* longer than previous command
lst := List(lst_cl, cl->Representative(cl));;

## Convenience function for cycle structure of permutations:
cycle_struct := function(p) local str, t, i; t := []; if NrMovedPoints(p)<Size(orb) then Append(t,[[1, Size(orb)-NrMovedPoints(p)]]); fi; str := CycleStructurePerm(p); for i in [1..Length(str)] do if IsBound(str[i]) then Append(t,[[i+1, str[i]]]); fi; od; return t; end;

## Morphisms from a free group to our two descriptions of Co_0:
frhom := EpimorphismFromFreeGroup(co0 : names := ["rot","fbl","omg","flp","cxi"]);;
frhom_mat := GroupHomomorphismByImages(Source(frhom), co0_mat, GeneratorsOfGroup(co0_mat));;

## Convert the computed conjugacy classes into representative matrices:
lst_mat := List(lst, x->Image(frhom_mat, PreImagesRepresentative(frhom, x)));;

## Now we try to identify the ATLAS labeling of these classes...

## Identify each class by its order and the traces of some powers:
keylist1 := List(lst_mat, m->[Order(m), Trace(m), Trace(m^2), Trace(m^3), Trace(m^4), Trace(m^6)]);;

## Compute centralizer orders (this is again a bit long):
lst_centralizers := List(lst, x->Order(Centralizer(co0, x)));;

## Get the ATLAS character table from the library:
tbl := CharacterTable("2.Co1");
# ConnectGroupAndCharacterTable(co0, tbl);  ## <- This doesn't work, of course
## Identify the 24-dimensional character
tbl_stdchar := Filtered(Irr(tbl), l->l[1]=24)[1];

## Identify the classes by the same numbers, in the order given by tbl:
keylist2 := List([1..Length(lst_cl)], i->[OrdersClassRepresentatives(tbl)[i], tbl_stdchar[i], tbl_stdchar[PowerMap(tbl,2)[i]], tbl_stdchar[PowerMap(tbl,3)[i]], tbl_stdchar[PowerMap(tbl,4)[i]], tbl_stdchar[PowerMap(tbl,6)[i]]]);;

## Now recover the labeling, insofar as it can be identified:
labeling := [];; revorder := [];; for i in [1..Length(lst_cl)] do tmp := Filtered([1..Length(lst_cl)], j->keylist2[j]=keylist1[i]); if Length(tmp)=1 then labeling[i] := AtlasClassNames(tbl)[tmp[1]]; elif Length(tmp)=2 then labeling[i] := Concatenation(AtlasClassNames(tbl)[tmp[1]],"|",AtlasClassNames(tbl)[tmp[2]]); fi; if IsBound(revorder[tmp[1]]) then revorder[tmp[2]] := i; else revorder[tmp[1]] := i; fi; od;

## Finally, dump it all out il a file called "co0-representative-matrices.dat":
output := OutputTextFile("co0-representative-matrices.dat", false);
PrintTo(output, "lst_mat := [\n\n");
for j in [1..Length(lst_cl)] do i := revorder[j]; WriteAll(output, Concatenation("#### ", String(j), "\n## Label: ", labeling[i], "\n## Order: ", String(keylist1[i][1]), "\n## Centralizer: ", String(lst_centralizers[i]), "\n## Cycles: ", String(cycle_struct(lst[i])), "\n## Trace: ", String(keylist1[i][2]), "\n")); PrintTo(output, lst_mat[i], "\n,\n\n"); od;
PrintTo(output, "];\n\n");
PrintTo(output, "########\n\n");
PrintTo(output, "lst_labels := ", List(revorder, i->labeling[i]), ";\n\n");
PrintTo(output, "lst_orders := ", List(revorder, i->keylist1[i][1]), ";\n\n");
PrintTo(output, "lst_centralizers := ", List(revorder, i->lst_centralizers[i]), ";\n\n");
PrintTo(output, "lst_cycles := ", List(revorder, i->cycle_struct(lst[i])), ";\n\n");
PrintTo(output, "lst_traces := ", List(revorder, i->keylist1[i][2]), ";\n\n");
CloseStream(output);

I also placed the same code on GitHub in case this is more convenient. (And sorry if my identifier names are atrocious.)

The result of the computation can be downloaded here (very slightly hand-edited in comparison to the file output by the above code, so as to make an arbitrary choice of labeling for those classes that cannot be unambiguously identified w.r.t. the ATLAS). It is itself a valid GAP file.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.