# Factoring polynomials and the Frobenius

Following Scott’s post, here is another post about some basic number theory that I haven’t seen written well in one place. First, a list of puzzles. In these puzzles, “polynomial” always means “polynomial with integer coefficients”:

• Give an example of a polynomial which has a root modulo every prime, but does not have a rational root.
• Give an example of a polynomial which has a nontrivial factorization modulo every prime, but is irreducible over the integers.
• Prove that, if a polynomial has at least k linear factors for every prime p, then it has at least k irreducible factors over the integers. Furthermore, if the degree of the polynomial is greater than k, then this lower bound can be improved to k+1
• Give an example of two irreducible polynomials f and g so that, modulo every prime, f and g have the same number of factors of the same degrees, but such that $\mathbb{Q}[x]/f(x)$ and $\mathbb{Q}[x]/g(x)$ are not isomorphic as fields.
• Everyone of these sounds like a problem about fields but, with a little bit of knowledge, they are actually problems about finite group actions. By the way, although every problem is solvable as written, they become easier if you allow yourself a finite number of exceptions instead requiring them to actually work for all primes, and I will only explain how to solve them with this proviso. I do assume that you know the basics of Galois theory.

Here is the main idea. Let f be a polynomial with integer coefficients and without repeated roots. To make my life simpler, I’ll assume that f has leading coefficient one, so that the roots of f are algebraic integers, although actually all I need to do in the more general case is to exclude those primes that divide the leading term of f. Let K be the splitting field of f, that is to say, the smallest extension of $\mathbb{Q}$ in which f has all of its roots. Let the roots of f be $\theta_1$, …, $\theta_n$. Define R to be the subring of K generated (over $\mathbf{Z}$) by the roots of f. Let G be the Galois group of K over $\mathbb{Q}$. Then G permutes the $\theta_i$ and hence acts on R. (Note for experts: the standard thing to do is to take the integral closure of $\mathbb{Z}$ inside K, rather than use R. This is undoubtedly the right thing to do, but I can avoid a lot of technical explanation by avoiding it.)

By definition, an $\overline{\mathbb{F}_p}$-point of $\mathrm{Spec} R$ is a ring homomorphism from R to the algebraic closure of $\mathbb{F}_p:=\mathbb{Z}/p$. (Yes, we are fixing an algebraic closure of $\mathbb{F}_p$.) I think that this is far too complicated a name for this idea so, in this blog post, I will call such a homomorphism a $p$-widget. If I really need to be explicit, I’ll call it a $p$-widget of f.

Now, $\Delta:=\prod_{i \neq j} (\theta_i - \theta_j)$ is an integer (since it is Galois invariant) and is nonzero (since we assumed that f doesn’t have repeated roots). There are only finitely many primes which divide $\Delta$; for any prime p which does not divide $\Delta$ we know that f continues to have distinct roots after reduction modulo p. I’ll call the primes dividing $\Delta$ the bad primes, and call all the others the good primes. For those trying to make the translation to standard terminology, “good” implies, but is not implied by, “unramified”.

What’s good about the good primes? Well, for one thing, let $\pi$ be any p-widget. If $\pi$ is good then $\pi(\theta_i) \neq \pi(\theta_j)$ for $i \neq j$. Why is this? Well, $\pi$ is a ring homomorphism, so $\pi(\Delta)=\prod_{i \neq j} (\pi(\theta_i) - \pi(\theta_j))$. But the right hand side is just the image in $\overline{F_p}$ of an integer which we assumed not divisible by p, so every factor on the right must be nonzero. Therefore, if p is a good prime, then G acts faithfully on $p$-widgets. It turns out, although I don’t see an easy proof, that G also acts transitively. I believe that this latter fact is due to Frobenius.

Now, there is also another action on $p$-widgets. Instead of acting on the ring R, we can act on the field $\overline{\mathbb{F}_p}$. Specifically, there is a map $x \mapsto x^p$ from $\overline{\mathbb{F}_p}$ to itself, called the Frobenius and we can turn one $p$-widget into another by post composing with the Frobenius. We’ll denote the Frobenius by $F$. If p is a good prime, and $\pi$ is a $p$-widget, then $F \circ \pi=\pi \circ g$ for some unique g in G, as we saw that G acts transitively and faithfully on the $p$-widgets. If, instead of $\pi$, we chose some other $p$-widget $\pi \circ h$, this would change the resulting value of $g$ to $h^{-1} g h$. In other words, the conjugacy class of g is determined by uniquely by p, and is known as the Frobenius class of p and denoted $Frob(p)$.

Now, here are the parts that I think could be laid out more explicitly in the books I’ve read. As those of you who are familiar with Galois theory know, the irreducible factors of f (over the rationals) correspond (in number and size) to the G-orbits in the set $\{ \theta_1, \ldots, \theta_n \}$. Now, similarly, F generates the Galois group of any finite extension of $\mathbb{F}_p$. Thus, the irreducible factors of f over $\mathbb{F}_p$ correspond to the orbits of $Frob(p)$ on the same set. Note that, although the actual orbits depend on the choice of a representative for $Frob(p)$, their number and size do not.

It shouldn’t be too hard to convince yourself of the following point, as well. If K is both the splitting field for f and for another polynomial g, and p is good with respect to both f and g, then $Frob(p)$ is the same element of G whether it is computed using f or g. (I will concede that this is one thing which is easier when one uses the standard approach in terms of integral closure.)

You now know enough to solve puzzles (1), (2) and (4). For example, puzzle (1) asks us to find a group G acting on a finite set S such that every element of G fixes a point of S, but no point of S is fixed by all of G. The simplest example is $G=\mathbb{Z}/2 \times \mathbb{Z}/2$ where S has three orbits, each stabilized by a different 2-element subgroup of G. Technically, to solve the puzzle we must actually find a field extension with this Galois group — the easiest solution is to take $f(x)=(x^2-2)(x^2-3)(x^2-6)$ so $K=\mathbb{Q}(\sqrt{2}, \sqrt{3})$, which has this Galois group. Puzzle (2) is only a little harder. For puzzle (4), it will help you to have the following hint: f and g should have the same splitting field.

To get puzzle (3), you need some elementary group theory (which I leave to you) plus a result that says that every conjugacy class of G occurs as $Frob(p)$ for some p. This is
Chebotarev’s Density Theorem : Let C be a conjugacy class in G. Then the density of primes p such that $Frob(p)=C$ is $|C|/|G|$.

Finally, let me make one more connection to standard terminology. The ring $R[\Delta^{-1}]$ is a so-called Dedekind domain, so every ideal factors uniquely as a product of prime ideals. (Again, I am inverting $\Delta$ in order to smear over my failure to take integral closures.) For a good prime p, the prime ideal factors of p correspond to the orbits of the $p$-widgets under the action of Frobenius. If $\pi$ is a $p$-widget, the corresponding prime ideal is the kernel of $\pi$. If I had chosen R correctly to begin with, then R itself would be a Dedekind domain and I could define the following standard objects for you: if $\mathfrak{p}$ is the kernel of a $p$-widget $\pi$, then the decomposition group of $\mathfrak{p}$ is the stabilizer of $\mathfrak{p}$ and the inertia group is the stabilizer of $\pi$.

## 12 thoughts on “Factoring polynomials and the Frobenius”

1. There is another way of seeing that $(x^2-2)(x^2-3)(x^2-6)$ has a factor modulo every (good) prime. Namely, at least one of 2,3, or 6 must be a square mod $p$ by quadratic reciprocity. (To avoid problems with $p=2, q=3$ one can instead choose a pair of primes whic are squares modulo each other.)

The group theory related to question 3 is interesting to me. Cannot one use it to say something more specialized: that if an irreducible polynomial has a root modulo every prime, then it has a rational root?

2. Cannot one use it to say something more specialized: that if an irreducible polynomial has a root modulo every prime, then it has a rational root?

By which you mean: any irreducible polynomial with roots mod p for all p is linear?

That’s right, because of an old lemma of Burnside’s, which says that the number of orbits of a G-set is the average over the group of the number of fixed points of each group element on that set. If X is a G-set on which each group element has at least one fixed point, then this average must be strictly larger than 1 (since the identity fixes more than one point, as long as X isn’t a single point).

3. Yes. What you said is equivalent to what I said.

Thanks for reminding me it was Burnside’s Lemma. According to Dummit and Foote (page 843, exercise 8) the result originated with Frobenius–which ties back nicely with the thread!

4. That should be an 8, followed by a parenthesis. Not a smiley face.

5. alex says:

Give an example of a polynomial which has a nontrivial factorization modulo every prime, but is irreducible over the integers.

======================================
I believe that irreducible polynomial

x^9-72*x^8-1056*x^7+13888*x^6+419328*x^5+64512*x^4 +53960704*x^3-190070784*x^2+746913792*x-4954783744

has a nontrivial factorization modulo every prime.

In fact, when prime p==2 mod 3
then factorization pattern is

1+1+1+2+2+2 if p==8 or 20 mod 21,

3+6 , otherwise

6. Jaime Montuerto says:

Dear David,

Your question about polynomials that has roots or factors modulo every prime is somewhat similar vein on my question to you about every prime numbers divides a Mersenne number. The difference is that every Mersenne numbers cannot be expressed by single polynomial. My take on your question is that there are no polynomials of those properties. A polynomial can have an infinite set of primes that divides it but not every primes in that set. The relationship of Mersennes are recurrence M_i+1 = M_i * 2 + 1.

My observation is that every prime numbers has distinct period/cyclic, in fact all integers have period.

Here’s the algorithm on calculating the period of integer N:

1. Start from any integer n < N.
2. double n, then modulo N, take note of the result.
3. If the result is not in the set yet then do process 2,ie double the result modulo N.

Obviously this won’t run forever, the limit will be the totient function of
N (Euler function) = N-1. If N is prime, but not all prime behave this way. Some integers examples: period of 23 is 11, 11 is 10, 15 is 4, 7 is 3.

4. the number of processes or doubling will be the period/cycle of N.

About a^2 + b^2, you asked what form are their factors. It seems that sum of squares are of 1 mod 4 forms and it seems to me that the factors are of the same forms, 1 mod 4, essentially a Proth like primes. What is your observation?

Regards

7. “… is a so-called Dirichlet domain”. That’s a new one for me. I guess the “so-called” allows you to get away with anything, but probably you meant “Dedekind domain”, right?

8. David Speyer says:

Oops! Thanks.

9. One substitution of “Dedekind” for “Dirichlet” down, one to go. (And I remembered what Dirichlet domains are: a certain kind of fundamental domain for the action of a discrete group on a symmetric space.)

10. Pingback: Polynomials ~