What is the Galois group of Conway's Look-and-say polynomial?

Question

A fun result of Conway shows that the length of terms in the Look-and-say sequence approach a constant ratio which is the root of a certain degree 71 polynomial, which can be found at that link.

What is the Galois group generated by the roots of this polynomial? One would expect it is $S_{71}$; is this tractable with computer algebra systems, or any other techniques?

Answer 1

Write the polynomial as $C(x)$. It is irreducible mod $5$, so it's irreducible over $\mathbf Q$. Therefore the Galois group of $C(x)$ over $\mathbf Q$ is a transitive subgroup of $S_{71}$. Since $71$ is prime, we will use the following result: for prime $p$, a transitive subgroup of $S_p$ containing some $p$-cycle and some transposition must be $S_p$.

A theorem of Dedekind says that if a monic irreducible polynomial $f(x)$ in $\mathbf Z[x]$ factors modulo some prime $p$ as $\pi_1(x)\cdots \pi_r(x)$ for distinct monic irreducibles $\pi_i(x)$, then the Galois group of $f(x)$ over $\mathbf Q$ contains a permutation on the roots with cycle type $(d_1, \ldots, d_r)$, where $d_i = \deg \pi_i(x)$.

So from $C(x) \bmod 5$ being irreducible, the Galois group of $C(x)$ over $\mathbf Q$ contains a $71$-cycle.

The monic irreducible factorization of $C(x) \bmod 43$ has distinct factors with degrees
$1, 1, 2, 5, 17$, and $45$, so the Galois group contains an element $\sigma$ that permutes the roots with cycle type $(1,1,2,5,17,45)$. Therefore $\sigma^{17\cdot 45}$ is a $2$-cycle (transposition). So the Galois group contains a $71$-cycle and transposition, proving the group is $S_{71}$.

Answer 2

A computer can check that $C(x)$ is irreducible modulo $5$ (which implies that $C(x)$ is irreducible over the integers as well, if we didn't already know that). By a famous theorem of Dedekind, this means that the Galois group of $C(x)$ contains a $71$-cycle. (Since $71$ is prime I think this fact also follows from the general transitivity of Galois groups.)

If we (get our computer to) factor $C(x)$ modulo $43$, the result is $(x-5)(x+4)p_2(x)q_5(x)r_{17}(x)s_{45}(x)$, where the subscript of each polynomial indicates the degree of that polynomial. Consequently by Dedekind's theorem again, the Galois group of $C(x)$ contains a permutation $\sigma\in S_{71}$ that (has two fixed points and) is the product of a $2$-cycle, a $5$-cycle, a $17$-cycle, and a $45$-cycle that are all disjoint. It follows that $\sigma^{17\cdot45}$, which is also in the Galois group of $C(x)$, is simply a $2$-cycle, that is, a transposition.

We are now done, since any subgroup of $S_{71}$ that contains both a $71$-cycle and a transposition must be all of $S_{71}$ (again since $71$ is prime).