# Is there a pattern of the factorization of a polynomial modulo $p$ as $p$ varies

Take $P\in\mathbb{Z}[X]$ and factorize it modulo $p$, where $p$ is a prime.

Modulo different $p$'s the factorization varies. Is there a pattern in this variation? I mean, for example, if $P$ is quartic, it can factorize as "linear*cubic", "quadratic*quadratic", "quadratic*linear*linear" and so on. Does it tend to factorize more in one way than in the other ways?

I came up with this question, because I am calculating these factorizations of a few polynomials, and they tend to "prefer" certain ways of factorization. This is looking curious, though of course, it could just be the odds.

-
Are you assuming $P \in \mathbb{Z}[X]$ irreducible? I think one might as well, since the factors $\mod p$ for sufficiently large primes will reflect factors of the irreducible factors over the integers. –  hardmath Apr 29 '13 at 22:14
Isn't this what the whole theory of arithmetic Zeta functions is all about? –  Martin Brandenburg Apr 30 '13 at 9:04

No, you are onto something. I like to use the variable $z$ for this. I forget what happens if you factor $z^3 - 2 \pmod 3.$ After that, there is one simple pattern when $p \equiv 2 \pmod 3,$ when you factor $z^3 - 2 \pmod p.$ That is, a linear factor times a quadratic.

Here is the cute bit: once $p \equiv 1 \pmod 3,$ and you factor $z^3 - 2 \pmod p,$ you get two wildly different outcomes: if there is an expression $p = x^2 + 27 y^2$ in integers, you get three linear terms, distinct. However, if $p = 4 x^2 + 2 x y + 7 y^2,$ irreducible.

Go Figure.

A similar example, see Numbers represented by a cubic form and factor $$z^3 - z^2 - z - 1$$ separately for primes with Legendre $(p|11) = -1$ and then for $p = x^2 + 11 y^2$ and then for $p = 3 x^2 + 2 x y + 4 y^2.$ As before, when there is an $xy$ term, you need to allow $xy$ both positive and negative to get all possible such primes. For example, with $x=1,y=-1,3 x^2 + 2 x y + 4 y^2 =5.$

Quartic examples: factor $z^4 + 3 \pmod p,$ when (A) $p=2,3$, (B) larger $p \equiv 3 \pmod 4,$ (C) $p = 5 x^2 \pm 4 xy + 8 y^2,$ (D) $p = 4 x^2 + 9 y^2,$ (E) $p = x^2 + 36 y^2$

Factor $z^4 + 2 z^2 - 7 \pmod p,$ when (A) $(-56|p) = -1,$ (B) $p = 3 x^2 \pm 2 xy + 5 y^2,$ (C) $p = 2 x^2 + 7 y^2,$ (D) $p = x^2 + 14 y^2.$ This is the one that is worked out in full in David A. Cox, Primes of the Form $x^2 + n y^2.$ On page 188 of that book, Theorem 9.12 gives the frequencies of the types of primes I have been specifying. This is an application of the Chebotarev Density that Qiaochu mentions.

I LIKE EXAMPLES. SUE ME.

=============================

=================================

-

Good question! This is in fact a fairly deep question in number theory. Statistical patterns are given by Chebotarev's density theorem, which predicts for example that for an irreducible quadratic polynomial you get two linear factors about half the time and a quadratic factor about half the time. In general, Chebotarev tells you that the frequency of each kind of factorization is controlled by the Galois group of the polynomial.

Describing the exact primes at which various factorizations occur is hard. If $P$ has abelian Galois group, then the answer is given by class field theory and can be given in terms of congruence conditions on the primes. This is easiest to see for the cyclotomic polynomials. Already the application to quadratic polynomials is essentially quadratic reciprocity, which is nontrivial.

If $P$ is nonabelian, then the answer is more complicated. Even for simple nonabelian cases the exact description can involve more sophisticated mathematics like modular forms; for example, $P(x) = x^3 - x - 1$ is controlled by the modular form

$$q \prod_{n=1}^{\infty} (1 - q^n)(1 - q^{23n})$$

as described here. In some sense answering this question is the goal of (part of?) the Langlands program.

-
The factorization of an integral polynomial $f(x)$ modulo a prime $p$ is closely related to the decomposition of the prime $p$ in the splitting field of $f(x)$. For quadratic polynomials, the factoring is determined by the congruence class of $p$ modulo the discriminant of $f(x)$. In general, there are more things to consider. However, the answers lie in algebraic number theory.