Constructing a polynomial given the Galois Group of it's splitting field

Let $$red_p : \mathbb{Z}[x]\to\mathbb{Z}/(p)[x]$$ be the canonical ring morphism sending a polynomial with integer coefficients to a polynomial with integer coefficients modulo $$p$$, with $$p$$ a prime, by taking modulo to each coefficient. My objective is to find a polynomial $$f\in\mathbb{Z}[x]$$ of degree $$8$$ such that $$\mathrm{Gal}(F/\mathbb{Q})\cong S_8$$, where $$F$$ denotes the splitting field of $$f$$ over $$\mathbb{Q}$$, and such that $$red_7(f)$$ is irreducible in $$\mathbb{Z}/(7)[x]$$. I don't even know how to begin. Any help would be greatly appreciated.

I've made some attemps to construct an 8 degree polynomial such that $$\mathrm{Gal}(F/\mathbb{Q})\cong S_8$$ but I can't seem to solve that problem either. I think that would be a great starting point.

• Replace $S_8$ by $S_3$. Take $f \in \mathbb{Z}[x], \deg(f) = 3$ with $f \in \mathbb{Z}/(p)[x]$ irreducible. Thus $f \in \mathbb{Z}[x]$ is irreducible and $R = \mathbb{Z}[x]/(f(x))$ is an integral domain. Then let $g(y) = \frac{f(y)}{y-x} \in R[y]$ and assume $g(y) \in R/(q)[y]$ is irreducible (note we can change $g\bmod q$ without changing $f \bmod p$), thus $g(y) \in R[y]$ is irreducible and $R[y]/(g(y))$ is an integral domain. Whence $F = Frac(R[y]/(g(y)))$ is the splitting field of $f(x) \in \mathbb{Q}[x]$ and $[F:\mathbb{Q}] = 6$ implies $Gal(F/\mathbb{Q}) = S_3$. – reuns Nov 19 '18 at 15:47
• Are you familiar with Dedekind's theorem on the relation between irreducible factors of $f$ mod primes and cycle types of the elements of $\operatorname{Gal}(f)$? This would suggest to start with an irreducible polynomial in $\Bbb{Z}/7\Bbb{Z}[X]$ and lift it to $\Bbb{Z}[X]$; this will give you a Galois group with a $7$-cycle. Then it does not take much to get all of $S_8$, e.g. a transposition will do. – Servaes Nov 19 '18 at 15:48
• *In the above it should say $8$-cycle in stead of $7$-cycle. – Servaes Nov 19 '18 at 16:12

This is not a complete answer, just a start as you indicate that you don't even know where to begin.

Let $$f\in\Bbb{Z}[x]$$ monic. If its image $$f_p$$ in $$\Bbb{F}_p[x]$$ is separable and factors as $$f_p=\prod_{i=1}^kg_k$$, then $$\operatorname{Gal}(f)$$ contains an element of cycle type $$(\deg g_1,\ldots,\deg g_k)$$. So it makes sense to start from an irreducibe polynomial $$h\in\Bbb{F}_7[x]$$ as then any lift $$\tilde{h}\in\Bbb{Z}[x]$$ already has an element of order $$8$$ in $$\operatorname{Gal}(\tilde{h})$$. An easy first candidate is $$h_7=x^8+x+3\in\Bbb{F}_7[x].$$ To make sure we also have a transpotion in $$\operatorname{Gal}(f)$$, we choose a lift $$\tilde{h}\in\Bbb{Z}[x]$$ that factors into one quadratic and six linear factors mod $$2$$. A bit of fiddling around yields, for example $$\tilde{h}=x^8+x+3+7(x^7+x^6+x+1)\in\Bbb{Z}[x],$$ so that $$h_2=x^8+x^7+x^6=x^6(x^2+x+1)\in\Bbb{F}_2[x].$$ which shows that $$\operatorname{Gal}(\tilde{h})$$ contains a transposition. This doesn't quite give you that $$\operatorname{Gal}(\tilde{h})\cong S_8$$, but gets you on the right track.

EDIT: As pointed out in the comments below $$h_2$$ is not separable, so this choice of $$\tilde{h}$$ doesn't quite work. I have no doubt the argument can be salvaged, but the result will likely not be as pretty. I'll give it some thought tomorrow.

UPDATE: One way to salvage the argument is to take a larger prime $$p$$, so that a lift $$\tilde{h}$$ splits into six distinct linear factors and one irreducible quadratic factor. As $$\deg\tilde{h}=8$$ this requires $$p\geq6$$, hence $$p=11$$ is the smallest prime that might work. And indeed, surprisingly little fiddling around shows that the lift $$\tilde{h}=x^8+x+3+7(x+8)\big((x+3)(x+4)+6(x+1)(x+2)(x+5)(x+10)\big)\in\Bbb{Z}[x],$$ satisfies $$h_p=(x+1)(x+2)(x+3)(x+5)(x+8)(x+10)(x^2+4x+5)\in\Bbb{F}_p[x],$$ which shows that $$\operatorname{Gal}(\tilde{h})$$ contains a transposition.

• How did you find $h_7$? – Ray Bern Nov 19 '18 at 17:19
• An educated guess; there is quite often a $c\in\Bbb{F}_p$ such that $x^n+x+c$ is irreducible. – Servaes Nov 19 '18 at 17:53
• @Jyrki You're absolutely right. It seems the argument needs a bigger prime, the computations will likely not be so clean. I'll give it some thought tomorrow. – Servaes Nov 19 '18 at 19:08

This example was produced in the first place by randomly generating polynomials and checking the factorizations with computer help (it only took a modest number of polynomials before finding a satisfactory one), so one might (reasonably) object that this answer isn't actually a "construction". But any method is going to have to show somehow that $$\operatorname{red}_7 f$$ is irreducible, and doing this naively is labor-intensive, as here are $$588 + 112 + 24 + 7 = 631$$ irreducible polynomials over $$\Bbb F_7$$ of degree $$1 \leq d \leq 4$$. If one has a faster way of generating irreducible polynomials over $$\Bbb F_7$$ of degree $$8$$ that we can then factor over $$\Bbb F_2, \Bbb F_3$$ (which is much faster to do manually, see below), one might be able to optimize considerably here.

Like Servaes' approach, the method here uses Dedekind's Theorem to show that $$\operatorname{Gal}(F / \Bbb Q)$$ contains certain cycle types. In particular, we'll use that a transitive subgroup of $$S_n$$ that contains an $$(n - 1)$$-cycle and a transposition is $$S_n$$ itself.

Take

$$f(x) := x^8 + 4 x^7 + 3 x^6 + 3 x^5 + 3 x^4 + 5 x^3 + x^2 + 4 x + 5 .$$

Factoring $$\operatorname{red}_p f$$ over $$\Bbb F_p$$ for the below $$p$$ gives:

• $$\operatorname{red}_7 f$$ is irreducible over $$f$$, so $$f$$ satisfies the given hypothesis and by Dedekind's Theorem $$\operatorname{Gal}(F / \Bbb Q)$$ acts transitively on the roots of $$f$$.
• $$\operatorname{red}_{2} f = p_3 \hat p_3 p_2$$ for irreducible (and distinct) polynomials of respective degrees $$3, 3, 2$$. Again by Dedekind's Theorem $$\operatorname{Gal}(F / \Bbb Q)$$ contains a product $$\sigma$$ of cycle type $$(3, 3, 2)$$, so $$\sigma^3 \in \operatorname{Gal}(F / \Bbb Q)$$ is a transposition.
• $$\operatorname{red}_{3} f = q_7 q_1$$ for irreducible polynomials $$q_d$$, so Dedekind's Theorem this time gives us that $$\operatorname{Gal}(F / \Bbb Q)$$ contains a $$7$$-cycle.

After checking the irreducibility of $$\operatorname{red}_7 f$$ as discussed above, the most intensive verification is checking that $$q_7$$ is irreducible over $$\Bbb F_3$$, but there are only $$8 + 3 + 3 = 14$$ irreducible polynomials of degree $$1 \leq d \leq 3$$ irreducible over $$\Bbb F_3$$.

• +1 Nice alternative. However, I don't agree that showing that $\operatorname{red}_7f$ is irreducible is necessarily labor-intensive. I agree that general approaches that work for any random $f$ are labor-intensive, but choosing $f$ wisely can make things a lot easier. My example quickly reduces to a system of $4$ quadratic forms in four variables over $\Bbb{F}_7$ to find an appropriate constant term, which is only takes a few minutes, at most 10 if you've done this before. – Servaes Nov 21 '18 at 11:26
• Thank you. I'm not sure I understand the comment, though---how exactly do you show that $x^8 + x + 3 \in \Bbb F_7[x]$ is irreducible? – Travis Willse Nov 21 '18 at 11:59
• If $f=x^8+x+C$ is reducible it either has either a zero (clearly not if $C\in\{3,4,6\}$) or a factor of degree $2$ or $4$, so it suffices to check that $f$ has no zero in $\Bbb{F}_{7^4}=\Bbb{F}[\zeta_5]$. In computing $f(a+b\zeta_5+c\zeta_5^2+d\zeta_5^3)$ almost all binomial coefficients involved vanish mod $7$, and because $x^7\equiv x\pmod{7}$ this reduces to \begin{eqnarray*} a^2+a+bc+bd+C&=&d^2+ac+bc\\ &=&c^2+b+ab+ad\\ &=&b^2+c+ad+cd\\ &=&c+ab+ac+bd+cd, \end{eqnarray*} a system of four equations in $a,b,c,d\in\Bbb{F}_7$ of total degree $2$, which isn't hard to solve by hand. – Servaes Nov 21 '18 at 14:53
• That's quite nice, thanks for the explanation. Why isn't it possible a priori, though, for $f$ to factor into an irreducible cubic and an irreducible quintic? – Travis Willse Nov 21 '18 at 15:25
• In any case, we can use your observation to produce a much faster variation of my solution: Taking $f := x^8 + x + 3 + 7(x^2 + 3) \in \Bbb Z[x]$ gives us irreducible $\operatorname{red}_7 f$ by your argument, and we can quickly factor into irreducibles $\operatorname{red}_2 f = x (x^7 + x + 1)$ and $\operatorname{red}_3 f = x (x - 1) [(x^6 + \cdots + x + 1) + 1]$, so $\operatorname{Gal}(F / \Bbb Q)$ is transitive and contains a $7$-cycle and a $6$-cycle, and the cube of the latter is a transposition. – Travis Willse Nov 21 '18 at 15:36