I’m trying to solve the following problem:
Let $C_1, \ldots, C_m \subseteq S_n$ be conjugacy classes of elements
in $S_n$. Show that there exists a monic irreducible polynomial $f \in
\mathbb{Z}[x]$ of degree $n$ such that, for any numbering of the roots
of $f$, we have $\operatorname{Gal}(f) \cap C_j \neq \emptyset$ for
all $j = 1, \ldots, m$. (Here $\operatorname{Gal}(f)$ is the Galois
group of $f$).
First of all, I should say that I’m not exactly sure what the “for any numbering of the roots of $f$“ part means.
My next thought was that since each conjugacy class corresponds to the orbit of an element $\in S_n$, then the roots of $f$ that the orbit of that element would permute (transitively, of course), would also be roots of an irreducible polynomial $f_i$ such that $f_i | f$, but this doesn’t seem to work since that polynomial could possibly have degree $< n$, and then $f$ wouldn’t be irreducible.
I was then thinking of using the following result, that I have proved previously: for every partition $n_1 \leq n_2 \leq \ldots \leq n_r$ of the integer $n$ ($\sum_{i=1}^r n_i=n$), there’s a polynomial $f=\prod_{i=1}^r f_i \in \mathbb{F}_p[x]$ where the polynomials $f_i$ are irreducible and such that $\deg(f_i)=n_i$ $\forall i\in \{1,\ldots, r\}$. I know conjugacy classes in $S_n$ are determined entirely by the cycle type of an element pertaining to it, so for all $j\in \{1,\ldots,m\}$ there is $f\in \mathbb{F}_p[x]$ such that the degrees of the irreducible polynomials in it’s decomposition correspond to the cycle type associated to $C_j$.
That’s pretty much as far as I could get… I know that I should probably be using this theorem somewhere:
Let $f\in \mathbb{Z}[x]$ of degree $n$ and $p$ a prime number such that $\bar{f}\in \mathbb{F}_p[x]$ is separable and decomposes in irreducible polynomials as $\bar{f}=\prod_{i=1}^r \bar{f_i}$. Then $\operatorname{Gal}(f) (\leq S_n)$ contains a product $\prod_{i=1}^r c_i$ of disjoint cycles whose respective lengths are $\deg(\bar{f}_i)$.
…but I couldn’t make everything fit all the pieces together yet. Any help would be appreciated.
Best Answer
Pick distinct primes numbers $p_1,\dots,p_m$. Then for each $i$ there is a monic separable polynomial $\overline f_i=\prod_{j=1}^r\overline f_{i,j}$ in $\mathbb F_{p_i}[x]$ such that the degrees of the $\overline f_{i,j}$ is the cycle type of the conjugacy class $C_i$.
Now, use the Chinese Remainder Theorem to lift the monic polynomials $\overline f_i$ to a single monic polynomial $f\in\mathbb Z[x]$. Now all that we need to worry about is to insure that $f$ is irreducible.
There are probably many ways to do this, but here is one way: Pick some large integer $N>0$ and consider $f+Np_1\cdots p_nx^{n-1}$. Then by Perron's irreducibility criterion eventually these polynomials must become irreducible. Moreover, adding the term $Np_1\cdots p_n x^{n-1}$ does not affect the reduction of $f$ modulo the primes $p_i$!
P.S. On second thought, here is an easier way to prove that an irreducible lift exists. Take $p_i$ and $\overline f_i\in\mathbb F_{p^i}[x]$ as above, but also take another prime $p$ and an irreducible polynomial $\overline f\in\mathbb F_p[x]$. Then by the Chinese Remainder Theorem the polynomials $\overline f_1,\dots,\overline f_m$ and $\overline f$ can all be lifted to a single monic $f\in\mathbb Z[x]$. If $f$ were reducible then $\overline f\in\mathbb F_p[x]$ would reduce as well, a contradiction.