If $n>1$, are there $f_1,\dots,f_k\in\mathbb{Z}[x]$ of degree $n$ such that, for any prime $p$, some $f_i$ is irreducible and of degree $n$, mod $p$?

Question

In the comments section of this question, the original poster raised an interesting variation on the problem, which I will state as follows:

Let $n>1\in\mathbb{N}$. Do there exist $f_1,\dots,f_k\in\mathbb{Z}[x]$ of degree $n$ such that, for any $p$ prime, there exists $i(p)\leqslant k$ with $f_{i(p)}$ irreducible and of degree $n$, mod $p$?

I am nearly certain that, for any $n\in\mathbb{N}$, the answer to this question is no, and I suspect there is probably a solution to this using Dedekind's theorem or some similar tool. However, off the top of my head I am not able to see how such an argument might go in the general case. Can anyone give a proof?

To get the ball rolling, I have written up an elementary proof for the case $n=2$ below. Other proofs for specific values of $n$ are very welcome as well.

---

Theorem: Let $f_1,\dots,f_k\in\mathbb{Z}[x]$ be polynomials of degree at most $2$. Then there exists a prime $p$ such that each $f_i$ is either reducible or of degree $\leqslant 1$, mod $p$.

Proof: Suppose that $f_i=a_ix^2+b_ix+c_i$ for each $i$. By the quadratic formula, if $a_i$ does not vanish mod $p$, then $f_i$ will have a root mod $p$ ($p>2$) if and only if $b_i^2-4a_ic_i$ is a quadratic residue mod $p$. Thus let $\delta_i=b_i^2-4a_ic_i$ for each $i$. It will suffice to find a prime $p$ such that $\delta_i$ is a quadratic residue mod $p$, for every $i$.

Let $p_1,\dots,p_l$ be all of the odd prime divisors of each $\delta_i$, and consider the system of congruences \begin{align} p\equiv 1&\mod 4 \\ p\equiv 1&\mod p_1 \\ p\equiv 1&\mod p_2 \\ &\vdots \\ p\equiv 1&\mod p_l. \end{align} The collection $\{4,p_1,\dots,p_l\}$ is pairwise coprime by construction, so Sun Zi's theorem tells us that the above system of congruences is equivalent to $p\equiv m\text{ }(\operatorname{mod} 4p_1\dots p_l)$ for some $m\in\mathbb{N}$. Now, $m$ is certainly coprime with $4p_1\dots p_l$, since $m$ is congruent to $1$ mod $4$ and $1$ mod $p_i$, for each $i$. Thus, by Dirichlet's theorem, there exists some $\lambda\in\mathbb{N}$ such that $m+\lambda\cdot 4p_1\dots p_l$ is prime; let $p=m+\lambda\cdot 4p_1\dots p_l$.

By construction, $p$ is congruent to $1$ mod $4$ and $1$ mod $p_i$, for each $i$. In particular, $p$ is a quadratic residue mod $2$ and mod each $p_i$, so, by quadratic reciprocity, $2$ and each $p_i$ are all quadratic residues mod $p$. Similarly, since $p$ is equivalent to $1$ mod $4$, we have that $-1$ is also a quadratic residue mod $p$. By construction, every $\delta_i$ is plus-or-minus a product of powers of $\{2,p_1,\dots,p_l\}$, and so – since products of quadratic residues are quadratic residues – every $\delta_i$ is a quadratic residue mod $p$. This means that each $\overline f_i$ is either linear or reducible, mod $p$, as desired.

Answer 1

You're correct. A negative answer follows from the Frobenius density theorem (a slightly weaker and easier-to-prove version of the Chebotarev density theorem), which is a sort of converse to Dedekind's theorem and which says the following:

Theorem (Frobenius): Let $f(x) \in \mathbb{Z}[x]$ be a monic polynomial. The density of primes $p$ such that the factorization of $f(x) \bmod p$ into irreducible polynomials over $\mathbb{F}_p[x]$ has $c_i$ factors of degree $i$ is equal to the density of elements of the Galois group $\text{Gal}(f)$ acting with $c_i$ cycles of length $i$ on the roots of $f$ in a splitting field of $f$.

Corollary: If $f(x) \in \mathbb{Z}[x]$ is a monic polynomial with Galois group $G$, then the density of primes $p$ such that $f(x) \bmod p$ splits completely is $\frac{1}{|G|} \ge \frac{1}{(\deg f)!}$. In particular, there is at least one such prime.

Now apply this result to $f = \prod f_i$.

Edit: Several sources you can find by googling only state the Frobenius density theorem for the case that $f$ is irreducible, and for this application we really need the general case; it is stated without the irreducibility assumption, for example, in Lenstra and Stevenhagen's Chebotarev and his density theorem, which I believe is where I first learned about it. I don't think we really need the hypothesis that $f$ is monic either, since the result is really about the splitting field of $f$ anyway; we can just ignore the finitely many primes dividing the leading term since they have density $0$. Similarly here we're ignoring the finitely many primes dividing the discriminant to avoid dealing with the possibility of repeated roots, since they also have density $0$.

Edit #2: I have been very silly. There's an elementary proof of a weaker version of the corollary, totally avoiding any analytic number theory, which suffices for this purpose. I learned this argument from an MO answer by Bjorn Poonen and forgot about it until just now.

Proposition: If $f(x) \in \mathbb{Z}[x]$, then there are infinitely many primes $p$ such that $f(x) \bmod p$ splits completely.

Proof. Let $K$ be a splitting field for $f$ over $\mathbb{Q}$, let $\alpha \in \mathcal{O}_K$ be a primitive element for $K$ (so that $K = \mathbb{Q}(\alpha)$), and let $g \in \mathbb{Z}[x]$ be the minimal polynomial of $\alpha$. Then, ignoring finitely many primes dividing any denominators that show up, $f(x)$ splits completely $\bmod p$ iff $g(x)$ has a root $\bmod p$ (since by hypothesis every root of $f$ is a polynomial in $\alpha$) iff there exists an integer $k$ such that $p \mid g(k)$.

But the values of every non-constant polynomial in $\mathbb{Z}[x]$ are divisible by infinitely many primes; this can be proven using a Euclid-style argument but see also this blog post for a counting argument. (In one sentence: an eventually monotonically increasing sequence of integers divisible by only finitely many primes must grow faster than polynomially.) $\Box$

Answer 2

Let $f_1, \dots, f_n \in \Bbb Z[x]$ be irreducible polynomials with no condition on the degrees. We claim that there exist infinitely many primes $p$ such that $f_i$ splits completely into linear factors mod $p$. By applying this to the irreducible factors of the polynomials $f_1, \dots, f_k$ in the question, we get that there are no such $f_1, \dots, f_k$.

Let $\alpha_i$ be a root of $f_i$ for all $i$. For each $i$, write $\alpha_i=\frac{\beta_i}{n_i}$, where $n_i \in \Bbb Z$ and $\beta_i$ is integral over $\Bbb Z$. Note that if $g_i$ is the minimal polynomial of $\beta_i$, then we have $g_i(x)=\pm f_i(n_ix)$. Now if $p$ is any prime not dividing any of the $n_i$, then we see that a splitting of $g_i$ into linear factors mod $p$ also gives a splitting of $f_i$ into linear factors mod $p$, so we replace $f_i$ with $g_i$ and assume wlog that all $f_i$ are monic and hence all the $\alpha_i$ are integral.

Consider the number field $K=\Bbb Q(\alpha_1, \dots, \alpha_n)$ and the order $\mathcal{O}:=\Bbb Z[\alpha_1, \dots, \alpha_n] \subset \mathcal{O}_K$. This order has a conductor $\mathfrak{c}$. It's well-known that in every number field, there are infinitely many primes that split completely, this follows e.g. by applying the Cebotarev density theorem after passing to the normal closure. Of those infintely many primes $p$ that split completely in $K$, only finitely many are not coprime to the conductor $\mathfrak{c}$. For those that are coprime to the conductor, the factorization of $(p)$ in $\mathcal{O}_K$ and in $\mathcal O$ will have the same form. Thus for $p$ coprime to the conductor such that $(p)$ splits completely in $\mathcal{O}_K$, $p\mathcal{O}$ factors as $p\mathcal{O}=\mathfrak{p}_1 \cdot \ldots \cdot \mathfrak{p}_l$ for distinct prime ideals $\mathfrak{p}_1, \dots, \mathfrak{p}_l$. Thus the quotient is $\mathcal{O}/p\mathcal{O} \cong (\Bbb F_p)^l$ but we also have $\mathcal{O}/p\mathcal{O}=\Bbb Z[x_1, \dots, x_n]/(p,f_1(x_1), \dots, f_n(x_n))\cong \Bbb F_p[x_1, \dots, x_n]/(f_1(x_1), \dots, f_n(x_n)$, we see that this is only possible if all $f_i$ split completely in $\Bbb F_p$.