I learnt a few days ago about the following AI challenge: find polynomials with Galois group \(G\) for each of the transitive subgroups of \(S_{24}\), with each of the possible signatures \((r_1,r_2)\) with \(r_1 + 2r_2 = 24\) where \(r_1\) is the number of fixed points for some (possibly trivial) involution \(c \in G\). (See the remark at the end about the formulation of this problem.)
I first heard about it at afternoon tea at SMRI. I had an interesting discussion (with Raymond van Bommel and others) on the merits of such a challenge. I was a bit confused to be honest. It seems as though the challenge has been “gamified” to some extent by awarding \(1\) point for each possible group and signature (with some additional points for small discriminants). The scoring system seems peculiar to me as well. I was challenged to commit to paper my thoughts on what the result would be, what examples I imagined were challenging and what would be easy.
The problem itself breaks up naturally into two subproblems: existence and construction. Now these are certainly different problems, and while the former is more interesting to me, the second can certainly also be challenging even when one has a positive answer to the first question. But that is also colouring my response here.
The case of solvable groups is more or less trivial and not so interesting. Certainly
existence is known, and the existence proof is more or less constructive, although there
is (potentially) going to be some issue of computational feasibility. That’s the aspect
of the problem on which I am the least informed. But I certainly don’t think the solvable
case is that interesting here from a theoretical point of view, unless one takes into account the additional problem of finding fields with small discriminants. From a computational point of view, I think one of the issues is identifying the most practical way of choosing the filtration of \(G\) in order to constructively set up the most efficient algorithm. As an example of what I mean, the efficient way to construct \(S_4\)-extensions is not to start with a quadratic extension! Of course, from a computational point of view, even constructing cyclic extensions of sufficiently high degree explicitly (say with some Galois structure to avoid trivialities with cyclotomic extensions) which might theoretically be trivial using class field theory becomes quite tricky, and Henri Cohen has written books about how to do this sort of thing. Perhaps these sort of questions are more to the heart of what this challenge is about. Another type of problem is to construct the \(S_n\) extension of \(\mathbf{Q}\) with smallest discriminant; obviously this is a much more subtle computational question than constructing a single example! Since John Jones (half of the team behind the database of local fields and the database of global fields now folded into the LMFDB) is one of the people behind this challenge this may indeed be more the spirit of this problem. That starts to touch on problems of Malle’s conjecture in very small ranges of discriminants which is definitely interesting, and certainly this blog post addresses quite different aspects of the problem related purely to the vanilla inverse Galois problem.
There are 25,000 transitive subgroups; 24193 are solvable and 807 are not.
In the remaining cases, you can bucket the groups by their (simple) composition
factors to get the following:
Non-solvable buckets by non-abelian composition factors:
{A_12}: 8
{A_12, A_12}: 4
{A_24}: 2
{A_5}: 267
{A_5, A_5}: 55
{A_5, A_5, A_5, A_5}: 45
{A_6}: 204
{A_6, A_6}: 64
{A_6, A_6, A_6, A_6}: 45
{A_8}: 20
{A_8, A_8, A_8}: 10
{LieA(1,11)}: 10
{LieA(1,11), LieA(1,11)}: 4
{LieA(1,23)}: 2
{LieA(1,7)}: 44
{LieA(1,7), LieA(1,7), LieA(1,7)}: 12
{M_11}: 3
{M_11, M_11}: 1
{M_12}: 5
{M_12, M_12}: 1
{M_24}: 1
While there may be subtleties, the examples involving \(A_n\) do not strike me as ones which would theoretically present that much difficulty. The general shape of these groups is presumably going to be something like \(A \subset H \subset G\), where \(\Gamma = H/A\) is the (direct product) of the non-simple groups in the bucket, and \(A\) and \(G/A\) will be solvable and quite small. So you are constructing \(\Gamma\) extensions over some small solvable field \(K\) with compatible \(\mathrm{Gal}(K/\mathbf{Q})\) action in a way that one can then solve some central extension problems, which is going to be a question of ensuring that the ramification in your \(\Gamma\) extensions is liftable. When you have an easy source of such \(\Gamma\) extensions, say when \(\Gamma = A_n\), this seems very manageable. When \(\Gamma\) is a product of some \(A_n\) then it is probably actually coming from \(A_n \wr C\) for some small group \(C\) which is equally easy.
That leaves the 83 remaining groups.
The group that first came to mind immediately upon hearing about this challenge as something that would be difficult was a totally real extension with Galois group \(G = \mathrm{PSL}_2(\mathbf{F}_{23})\). If I was to put money on one pair (group and involution) which would still be missing after this project, then this would be one. Moreover, I don’t really see how having every single other possible pair in the table computed would be helpful in understanding this last case. For example, if you choose the other conjugacy class in this case, even the computational problem is reduced to finding explicit Galois representations coming from mod \(p\) representations of modular forms.
Apparently the case of \(M_{23}\) as an explicit Galois group has been touted as a possible “super hard” problem for AIs to work on. I’m not super excited by this problem, since there are a number of places one could look and then randomly get lucky; my version of this problem would be \(\mathrm{SL}_2(\mathbf{F}_p)\) for all primes \(p\) (the case \(p=23\) related to the example above). The advantage of this example is that one clearly cannot “accidentally” find a solution for all \(p\) at once. (I’ve mentioned this example before at this blog.)
As for other difficult cases, it’s possible that some of the cases related to \(\mathrm{PSL}_2(\mathbf{F}_{11})\) could cause similar issues with difficult choices of involution. My impression is that one knows that \(M_{24}\) occurs as a regular extension, but I’m not sure which involutions one sees over this family, and that could also cause issues (e.g. my guess might be that the rigidity method produces/forces a particular choice of \(c\)).
Remark: Actually I’m not sure if the challenge requires one to find all pairs \((G,c)\) where \(c\) is a conjugacy class of involutions (which would be the most sensible choice) or all \(G\) with a possible pair \((r_1,r_2)\); while the former determines the latter the converse is not true.