Chebotarev Density Theorem answers to factorization of polynomials I've read of Chebotarev Density Theorem. The statement over $\mathbb{Q}$ is:
Let $K$ be Galois over $\mathbb{Q}$ with Galois group $G$. Let $C$ be a conjugacy class of $G$. Let $S$ be the set of (rational) primes $p$ such that the set of $\{\text{Frob}_{} |  \ \text{above } p\}$ is the conjugacy class $C$. The set $S$ has density $\frac{|C|}{|G|}$.
I understand the statement, and my question is not about that, but the relation of this statement with facts about polynomials. There is the following fact, which tells that there is a correspondence:
Let $K = \mathbb{Q}(\alpha)$, where $\alpha$ is an algebraic integer. Let $f$ be the minimal polynomial of $\alpha$, and let $L$ be the Galois closure of $K$ with Galois group $G$. Let $p$ be a (rational) prime which does not ramify. The factorization of $f$ modulo $p$, that is, $f \equiv f_1f_2 \ldots f_k \pmod{p}$, is the same as the cycle type $(f_1, f_2, \ldots, f_k)$ of the $Frob_ \in G$ permuting $f$'s roots, where $ \in L$ is a prime ideal above $p$.
(I would also be happy to see a reference/proof to this theorem, but that's not the main issue. I'm also interested to know if there is some other way to motivate the connection between Frobenius maps and polynomials)
Now, for the questions.


*

*Can we apply the Chebotarev Density Theorem for determining the density of a given factorization type for a given polynomial? For example, if we have the polynomial $x^4 + x + 1$, can we calculate how often we have the factorization type $(1, 3)$. This seems possible to me using the other fact I wrote, but I am not able to fill in the details.

*Moreover, can this factorization type be reached from more than one conjugacy class? That is, can there be two (or more) conjugacy classes $C_1, C_2$ such that the $p$ with $\sigma_p = \{\text{Frob}_ |  \text{ above } p\} \in C_1, C_2$ have the cycle type $(1, 3)$? 

*Does the situation in 1. change for reducible polynomials - is the calculation still possible?
I also have a loosely-related question about applying the density theorem to obtain some other results:
4.
In http://websites.math.leidenuniv.nl/algebra/Lenstra-Chebotarev.pdf there is an example application of the Chebotarev density theorem for proving the Dirichlet's theorem on arithmetical progressions at page 4 in the paragraph starting with "If you apply this theorem in the abelian case, ..."
In general, I'm very confused about the proof. For me the most intuitive way to approach the problem would be looking at the cycle types of $\sigma_p$, but the proof seems to "cheat" by looking at $\sigma_p$ as integers modulo $m$. There seems not to be a polynomial whose factorization we would inspect, which confuses me - how does this other method precisely work, what happens in the step $\sigma_p \longleftrightarrow (p \text{ mod } m)$? I kind of feel like I've answered my own question already, but if someone has some clarifying ideas, please share.
 A: Anything but a complete answer. More like a list of related points too long to fit into a comment.
The general result you mentioned is due to Dedekind. Locally a proof is discussed here. Google points at this on-line resource. I first learned about it from chapter 4 in Jacobson's Basic Algebra I. It is probably best phrased using the language of algebraic number fields, splitting of prime ideals in particular. The key assumption is that after reduction modulo $p$ the polynomial should not have factors with multiplicities $>1$. This allows us to write the quotient ring $\Bbb{Z}_p[x]/\langle f(x)\rangle$ as a direct sum of the finite fields $\Bbb{Z}_p[x]/\langle p_i(x)\rangle$, where $p_i(x)$ are the irreducible factors of $f(x)$ modulo $p$. So, Chinese remainder theorem again!


*

*The extra piece of information you need is the Galois group of your polynomial viewed as a group of permutations of its zeros. Dedekind's theorem is actually a very useful tool in figuring out the Galois group. The quartic $p(x)=x^4+x+1$ is a case in point. Its Galois group $G$ is a subgroup of $S_4$. It is irreducible modulo two, so there is a 4-cycle $\alpha\in G$. Modulo three it factors as follows
$$p(x)=(x-1)(x^3+x^2+x-1).$$ The first factor is there because $p(1)=3\equiv0$, and that cubic is irreducible because it has no zeros in $\Bbb{Z}_3$. Therefore there is a 3-cycle $\beta\in G$. This actually already implies that $G=S_4$. The presence of $\alpha$ says that $G$ is transitive. The presence of $\beta$ says $G$ is 2-transitive (a point stabilizer is transitive). The only 2-transitive subgroups of $S_4$ are $S_4$ itself and $A_4$. But $\alpha\notin A_4$. At this point all you need to do is the bit of combinatorics telling that there are eight $3$-cycles in $G=S_4$ (well known to form a single conjugacy class). $8/|G|=1/3$ so this tells that, asymptotically, $p(x)$ splits into a product of a linear factor and an irreducible cubic modulo one third of the primes.

*It is definitely possible that there are several conjugacy classes of elements with the same cycle structure. The simplest cases are the small abelian groups. For example, the splitting field of $q(x)=x^4+1$ is $\Bbb{Q}(i,\sqrt2)$. As a group of permutations the Galois group is the copy of Klein four, $G=\{1,(12)(34),(13)(24),(14)(23)\}$. So, unless $q(x)$ splits completely modulo a prime $p\neq2$, it is the product of two irredudible quadratics. See this thread for a different elementary look at this polynomial. Even though they are singletons as conjugacy classes, three quarters of the elements of the Galois group have the cycle type $(2,2)$, so modulo $3/4$ of the primes we get the factorization into two irreducible quadratics. In the remaining quarter of cases $q(x)$ splits completely, and checking the linked thread you quickly realize that $q(x)$ splits completely modulo $p$ if and only if $p\equiv1\pmod8$. Warning: splitting type is determined by the residue class of $p$ (modulo some integer) only when $G$ is abelian (this result comes from class field theory, and I'm the wrong person to attempt to communicate that).

A: Now that I have learnt more about algebraic number theory and such, I decided to answer my own question. We work with $\mathbb{Q}$ all the way, though the general case is not very different.
First a remark on the Frobenius symbol. Let $P \in \mathbb{Z}[x]$. For each prime $p$ there is a field automorphism of the algebraic closure of $F_p$ [one could work with $\mathbb{F}_{p^k}$ 
for $k = \deg(P)!$ -- the point is that we take some field which contains the roots of $P$ modulo $p$], called the Frobenius endomorphism, which maps $x$ to $x^p$. Denote this by $\sigma_p$.
It is an easy exercise to prove that the only elements fixed by this map are those in $F_p$. We see, in particular, that the Frobenius endomorphism $\sigma_p$ fixes a root of $P$ in the closure $F_{p^{\infty}}$ if and only if this root is in $F_p$, i.e. this root is indeed a root modulo $p$. In general one can prove that if $\alpha$ is a root of $P$ in $F_{p^{\infty}}$ with $[F_p(\alpha) : F_p] = d$, then the sequence
$$\alpha, \sigma_p(\alpha), \sigma_p(\sigma_p(\alpha)), \ldots$$
is periodic with period equal to the degree $d$. 
For example, if $P(x) = x^2 + 1$ and $p \equiv 3 \pmod{4}$, then the roots of $P$ in $F_{p^{\infty}}$ are not in $F_p$. One may think of the roots of $P$ as $i$ and $-i$, and now $i$ maps to $-i$ and $-i$ maps to $i$ (but keep in mind that here $i$ and $-i$ are not complex numbers, even though they have the property that $i^2 = (-i)^2 = -1$) . The cycle length in this case is $2$, corresponding to the fact that we "picked a root out of a quadratic irreducible factor of $P$ modulo $p$".
We thus see that the orbits of the roots under the Frobenius symbol contain all of the information on the factorization of $P$ modulo $p$.
Recall that the Frobenius symbol (also called the Artin symbol - I'll use this term to not mix it up with Frobenius endomorphism) of a prime $p$ with respect to the splitting field $F_P$ of $P$ is a conjugacy class $C \subset \text{Gal}(F_P/\mathbb{Q})$ which "mimics" the behaviour of the Frobenius endomorphism $\sigma_p$. (Remember that we have to pick a conjugacy class instead of a single element, but elements in the same conjugacy class are quite similar, so this doesn't really bother us.) More precisely, when we view the Artin symbol as a (conjugacy class of) permutation(s) of the roots of $P$ in $F_P$, it has the same cycle pattern as $\sigma_P$ on the roots of $P$ in $\mathbb{F}_{p^{\infty}}$.
We are now ready to answer the questions.


*

*This indeed is possible. Consider the case $P(x) = x^4 + x + 1$. There is some set of conjugacy classes in $\text{Gal}(F_P/\mathbb{Q})$ such that the elements in those conjugacy classes permute the roots of $P$ with cycle pattern $(1, 3)$. Now those $p$ for which the Artin symbol of $p$ with respect to $F_P$ belongs to some of these conjugacy classes are exactly the primes for which $P$ splits into factors of degrees $1$ and $3$ modulo $p$ due to the connection with the Frobenius endomorphism, Artin symbol and the degrees of the irreducible factors of $P$ modulo $p$. Note, however, that it is not easy to determine the Galois group of a given polynomial - thus, it could be that the number of desired conjugacy classes in this case is $0$. (For the polynomial $x^4 + x + 1$ this is not the case - see the answer of Jyrki Lahtonen for the calculation of the Galois group.)

*In general, yes. If there was a bijection between factorization types and conjugacy classes, it would be that the Frobenius density theorem was no weaker than Chebotarev's. This, however, is not the case. For example, we know that Chebotarev implies Dirichlet's theorem while Frobenius does not. In the exposition linked in the question there is more about this aplication.

*Reducible polynomials are no problem. It is convenient to formulate the Frobenius and Chebotarev density theorems for irreducible polynomials (if one wants to formulate them in terms of polynomials), as in the irreducible case the Galois group of the polynomial is transitive. The general case follows follows from the irreducible case. Consider, for example, the case of $P(x) = P_1(x)P_2(x)$, where $P_1$ and $P_2$ are irreducible. One may now take the compositum of the splitting fields of $P_1$ and $P_2$ and work in there. The extra ingredient one needs is the following natural property of the Artin symbol: Let $\mathbb{Q} \subset K \subset L$ is a chain of fields. The restriction of the Artin symbol of $p$ w.r.t. $L$ to $K$ is the Artin symbol of $p$ w.r.t. $K$. So, for example, if $p$ is such that the Artin symbol of $p$ w.r.t. the compositum $F_{P_1}F_{P_2}$ is the identity, then the Artin symbol of $p$ w.r.t. $F_{P_1}$ is the identity, and we then know that $P_1$ splits completely modulo $p$.

*As commented by reuns, it turns out that the Artin symbol of a prime $p$ with respect to the cyclotomic field $\mathbb{Q}(\zeta_m)$ depends on what $p$ is modulo $m$ and only on that. This is non-trivial. Here's one reference (Lemma 2.4.1). This is precisely the reason why cyclotomic fields correspond to congruence conditions. (In many cases the converse is true too: congruence conditions imply cyclotomic fields. This, apparently, is one of the main philosophies in class field theory.) Application: It is true that $\mathbb{Q}(\sqrt{n})$ is a subfield of a cyclotomic extension. (For an overkill proof, use the Kronecker-Weber theorem.) It does not come as a surprise that the set of primes $p$ for which a given integer $n$ is a quadratic residue is determined by congruence conditions.
