Suppose that $f(x) \in \mathbb{Z}[x]$ is an irreducible polynomial over $\mathbb{Q}$. Nevertheless, it may be the case that $f(x)$ is reducible modulo $p$ for some prime $p$. What is the density of primes $p$ for which $f(x)$ splits completely into linear factors over $\mathbb{F}_p$?


The density is $\frac{1}{|G|}$ where $G$ is the Galois group of $f$. In particular it is at least $\frac{1}{(\deg f)!}$. This is a corollary of the Frobenius density theorem, a slightly weaker but (apparently; I don't know this first-hand) considerably easier version of the Chebotarev density theorem.

For example, let $f(x) = \Phi_n(x)$ be the $n^{th}$ cyclotomic polynomial. The primes for which $f(x)$ splits are precisely the primes congruent to $1 \bmod n$; the density of these is $\frac{1}{\varphi(n)}$ by Dirichlet's theorem on arithmetic progressions. And indeed the Galois group is $(\mathbb{Z}/n\mathbb{Z})^{\times}$, which has size $\varphi(n)$.

  • 1
    $\begingroup$ Hi Qiaochu, one Frobenius density on MO, mathoverflow.net/questions/136025/frobenius-density-theorem I think there have been others on both sites. The phrase seems quite familiar to me, I think I was part of some discussion with it. I remember a statement that every pattern of factoring (partition of the degree) occurs with a natural density of primes. $\endgroup$ – Will Jagy Nov 4 '14 at 18:21
  • $\begingroup$ David's answer here mathoverflow.net/questions/16271/… contradicts my memory about all partitions, something interesting I can fiddle with, at least check on computer. $\endgroup$ – Will Jagy Nov 4 '14 at 18:35
  • $\begingroup$ @Will: each partition occurs with density proportional to the number of elements of $G$ with that cycle type (acting on the roots of $f$). The issue is that if $G$ is not all of $S_n$ (where $n = \deg f$) then not all cycle types necessarily appear. $\endgroup$ – Qiaochu Yuan Nov 4 '14 at 18:42
  • $\begingroup$ Qiaochu, thanks. Types of cycles, good. I checked David's example, he was right, of course. News to me. $\endgroup$ – Will Jagy Nov 4 '14 at 19:08
  • 1
    $\begingroup$ @Will: the significance of David's example is that the cubic he wrote down has Galois group $A_3 \cong C_3$ (in fact I think its splitting field embeds into $\mathbb{Q}(\zeta_7)$ or something like that), which only has one nontrivial cycle type in it. More generally the Galois group of an irreducible cubic is $A_3$ or $S_3$ depending on whether or not its discriminant is a square, and in the former case there is again only one nontrivial cycle type (and also, by Kronecker-Weber, the splitting field embeds into some cyclotomic field). $\endgroup$ – Qiaochu Yuan Nov 5 '14 at 5:18

A full answer would be Chebotarev density for, well, anything. What I do know are some examples; if $$ f(x) = x^3 - x + 1, $$ the density is $(1/6).$ The primes are those which can be expressed as $$ p = u^2 + uv + 6 v^2. $$ Plenty more where that came from. Quoting from page 188 of Cox, Theorem 9.12, as well as a 1991(?) paper by Williams and Hudson.

EDIT, Monday Nov. 10; I got very interested in the history of this for my own reasons. One direction about different cycle partitions in the Galois group, considered as a permutation group, is attributed entirely to Dedekind, see COX. So, if, for any prime not dividing the discriminant, the polynomial factors with a certain partition of irreducible factor degrees, then there is at least one element in the Galois group whose cycle description is the same.

The Frobenius direction, about the same time (1880-1900) is that, once the Galois group has an element with a certain cycle decomposition, then infinitely many primes cause the polynomial to factor with that pattern, this set of primes has both a Dirichlet density and a natural density, and the density is the number of Galois group elements with that pattern divided by the size of the full Galois group. Note that, as Qiaochu mentions, there is only one element (the identity) that has all cycles of length $1,$ the identity element.

Oh; most people seem to quote one source about Frobenius Density, a survey by Lenstra and Stevenhagen, especially pages 10-12 in the preprint linked.

The theorem of Frobenius ...deserves to be better known than it is. For many applications...it suffices to have Frobenius's theorem, which is both older (1880) and easier to prove..

I think this is lovely. Proof in an undergraduate course would be another matter, showing there is a natural density came later.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.