Third SAIR competition: inverse Galois challenge

I am happy to announce the third SAIR challenge, which is focused on obtaining numerical data for the infamous inverse Galois problem. This is a collaborative project with the L-functions and modular forms database (LMFDB), and is organized by John Jones, Jen Paulhus, David Roe, Andrew Sutherland, and myself. The challenge is somewhat similar to my own Equational Theories Project, in that one is trying to complete a large mathematical data set in a verified fashion, except that the target data set had an existing mathematical interest. Also, the verification will be done by MAGMA (as well as PARI/GP) rather than Lean.

Let me first quickly review the inverse Galois problem. Suppose one has an irreducible polynomial ${P(z)}$ of one variable of some degree ${n}$ and integer coefficients; take for instance ${P(z) = z^3 - 3z + 1}$ . Then ${P}$ will have ${n}$ distinct roots ${\alpha_1,\dots,\alpha_n}$ ; in this case the roots happen to be

$\displaystyle \alpha_1 = 2 \cos \frac{2\pi}{9}, \quad \alpha_2 = 2 \cos \frac{8\pi}{9}, \quad \alpha_3 = 2 \cos \frac{14 \pi}{9}.$ The roots generate a splitting field ${\mathbb{Q}(\alpha_1,\dots,\alpha_n)}$ over the rational numbers ${\mathbb{Q}}$ . Any automorphism of this splitting field must permute the roots ${\alpha_1,\dots,\alpha_n}$ , and thus generates a subgroup of the permutation group ${S_n}$ (defined up to relabeling of the roots), which we call the Galois group of ${P}$ . This is some subgroup of ${S_n}$ that acts transitively on the ${n}$ roots (because each root generates the field). Typically, it is all of ${S_n}$ ; but occasionally it is smaller. For example, the particular cubic polynomial ${P}$ above has the special property that each root ${\alpha_1,\alpha_2,\alpha_3}$ individually generates the entire field ${\mathbb{Q}(\alpha_1,\alpha_2,\alpha_3)}$ , thanks to the identities

$\displaystyle \alpha_2 = \alpha_1^2 - 2; \quad \alpha_3 = \alpha_2^2 - 2; \quad \alpha_1 = \alpha_3^2 - 2.$
Because of this, the Galois group of ${P}$ is the cyclic group ${C_3}$ (or equivalently, the alternating group ${A_3}$ ), rather than the full symmetric group ${S_3}$ . (This is in contrast to, say, ${P(z) = z^3 - 2}$ , whose roots ${\alpha_1 = 2^{1/3}}$ , ${\alpha_2 = 2^{1/3} \omega}$ , ${\alpha_3 = 2^{1/3} \omega^2}$ cannot be expressed as rational polynomials of each other, and whose Galois group is all of ${S_3}$ .) In fact, in the cubic case, it turns out that the Galois group is ${A_3}$ when the discriminant is a perfect square, and ${S_3}$ otherwise.

More generally, we have

Problem 1 (Inverse Galois Problem) Let ${G}$ be a transitive permutation group on ${n}$ letters. Can ${G}$ be realized as the Galois group of some degree ${n}$ irreducible polynomial ${P(z)}$ with integer coefficients (after identifying the ${n}$ roots of ${P}$ suitably with the ${n}$ letters)?

The answer to this problem is known to be positive for ${n \leq 23}$ , with the single possible exception of the sporadic Mathieu group ${M_{23}}$ : there are ${4953}$ transitive permutation groups on ${n \leq 23}$ letters (cf. OEIS A002106), and for ${4952}$ of them, a polynomial has been located with that Galois group; see this database of Klüners and Malle. The problem of locating a polynomial with Galois group ${M_{23}}$ is a notorious open problem, though this is likely to be quite a difficult problem, and not the objective of the SAIR challenge.

Instead, we will focus on “breadth” rather than “depth”, in order to leverage the power of crowdsourcing and modern AI technologies. It turns out that there are ${25000}$ distinct transitive permutation groups on ${n=24}$ letters, which are conventionally labeled from ${24T1}$ (the cyclic group ${C_{24}}$ ) to ${24T25000}$ (the permutation group ${S_{24}}$ ). The first stage of the challenge will be:

Problem 2 (First stage of SAIR challenge) For as many of the groups ${24Tt}$ , ${t = 1,\dots,25000}$ , locate an integer polynomial with that Galois group (up to isomorphism). (Also of interest is to specify the number of real roots, and to keep the discriminant low; more on this later.)

The verification side of this problem is essentially solved: the MAGMA computer algebra system can take any candidate polynomial and locate its Galois group within seconds. The MAGMA team has kindly granted SAIR a limited license to provide an API for contestants to calculate a certain number of Galois groups per day without needing to purchase their own license, though of course they are free to use their other computational tools to also perform these calculations outside of the competition.

The LMFDB already has polynomials for 286 of the 25000 groups, so there is plenty of remaining polynomials to claim in the challenge.

For applications, it is of interest to track some other statistics of a polynomial besides its Galois group. One of these is the number ${r}$ of real roots, which is a number between ${0}$ and ${n}$ of the same parity as ${n}$ (and which has to be achievable as the number of fixed points of one of the permutations in the Galois group, namely the one corresponding to complex conjugation); in particular, this number must be even in the degree ${24}$ case. Combining the label ${t}$ of the Galois group with the number of roots ${r}$ turns out to generate ${165836}$ ${(t,r)}$ pairs in degree ${24}$ , and the challenge is actually to attach polynomials to as many of these pairs as possible. (The LMFDB has already done so for just ${622}$ of these.)

Of course, there are infinitely many polynomials of degree ${24}$ , and any Galois group that is representable by one polynomial, will be representable by infinitely many others (e.g., one could simply translate the polynomial by an arbitrary integer shift). To avoid creating an unusable database filled with uninteresting polynomials, we will prioritize polynomials whose (absolute) discriminant is as small as possible. (There are some technical details as to how this discriminant is defined and computed; see this page for details). The way we have set things up, each ${(t,r)}$ pair will come with a leaderboard for the polynomials with the smallest discriminants that have been located so far by contestants, removing duplicates arising from trivial operations such as translating the polynomial. Contestant team will be awarded a score between ${0}$ and ${1}$ for each submitted polynomial based on how small their discriminant is compared to the best known discriminant, and how many other teams were also able to find a polynomial with that ${(t,r)}$ pair. Thus, pairs that are extremely easy to generate (such as those associated to the full permutation group ${S_{24}}$ ) will be worth only a negligible score (as every contestant will be able to submit a polynomial for that pair), while pairs which are difficult to locate a polynomial for will be worth more points.

For this competition, the unrestricted use of any sort of computational tool, including AI, to locate the polynomials, are expressly permitted; this first stage of the competition is a “black box” challenge where we are not directly interested in obtaining insights as to how the polynomials are located, but the sole objective is to resolve as much of the inverse Galois challenge as possible. As such, the notorious uninterpretability of modern AI is not a concern for this stage. However, we will encourage contestants to share techniques with each other in order to cover more ground, through the Zulip channel for this challenge.

This first stage of the competition will close on August 15. After this, we will launch a second stage (with details to be determined) to focus on some set of candidate Galois groups that could not be resolved by the first stage. Here we envisage a more collaborative, conceptual, and human-driven effort in which the role of AI tools may be more secondary, and with more of a focus on creating mathematically interesting results rather than simply trying to saturate a given benchmark. Stay tuned for more details!

Source link