Mixing
Chebotarev Density Theorem answers to factorization of polynomials
$begingroup$
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.
polynomials galois-theory algebraic-number-theory
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
$endgroup$
add a comment |
$begingroup$
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.
polynomials galois-theory algebraic-number-theory
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
$endgroup$
1
$begingroup$
$G$ is a subgroup of $S_n,n=deg(f)$ and $g,g_2$ have the same permutation type iff $g=h g_2h^{-1}$ for some $hin S_n$. The functions on $G$ that are restrictions of class functions on $S_n$ are a smaller set than the class functions on $G$ (see how it works with abelian extensions). It is in the latter that the characters of irreducible representations of $G$ form an orthonormal basis, and Chebotarev theorem (the PNT for Artin L-functions) is $sum_{N(mathfrak{p}^k)le x} log(N(mathfrak{p})) , psi(Frob_{mathfrak{p}}^k)sim frac{x}{|G|}sum_{gin G}psi(g)$ as $xtoinfty$
$endgroup$
– reuns
Jan 5 at 3:41
2
$begingroup$
In $mathbb{Q}(zeta_m)$ then $Frob_mathfrak{p}$ depends only on $p bmod m$ where $p mathbb{Z} = mathfrak{p} cap mathbb{Z}$, so that's not cheating. The Frobenius only depending on some congruences (and ideal class) in the base field is the key idea of class field theory from which representations of abelian extension are well-understood. In non abelian extensions, things are much more complicated.
$endgroup$
– reuns
Jan 5 at 3:51
$begingroup$
No reason not to flesh out those comments to an answer @reuns? I realize that the connection with the primes in an arithmetic progression is standard, but it deserves to be spelled out on this site at least once. So, unless you find a duplicate you could do the honors :-)
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:30
add a comment |
$begingroup$
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.
polynomials galois-theory algebraic-number-theory
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
$endgroup$
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.
polynomials galois-theory algebraic-number-theory
polynomials galois-theory algebraic-number-theory
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
asked Jan 5 at 2:46
LoppukilpailijaLoppukilpailija
655
655
1
$begingroup$
$G$ is a subgroup of $S_n,n=deg(f)$ and $g,g_2$ have the same permutation type iff $g=h g_2h^{-1}$ for some $hin S_n$. The functions on $G$ that are restrictions of class functions on $S_n$ are a smaller set than the class functions on $G$ (see how it works with abelian extensions). It is in the latter that the characters of irreducible representations of $G$ form an orthonormal basis, and Chebotarev theorem (the PNT for Artin L-functions) is $sum_{N(mathfrak{p}^k)le x} log(N(mathfrak{p})) , psi(Frob_{mathfrak{p}}^k)sim frac{x}{|G|}sum_{gin G}psi(g)$ as $xtoinfty$
$endgroup$
– reuns
Jan 5 at 3:41
2
$begingroup$
In $mathbb{Q}(zeta_m)$ then $Frob_mathfrak{p}$ depends only on $p bmod m$ where $p mathbb{Z} = mathfrak{p} cap mathbb{Z}$, so that's not cheating. The Frobenius only depending on some congruences (and ideal class) in the base field is the key idea of class field theory from which representations of abelian extension are well-understood. In non abelian extensions, things are much more complicated.
$endgroup$
– reuns
Jan 5 at 3:51
$begingroup$
No reason not to flesh out those comments to an answer @reuns? I realize that the connection with the primes in an arithmetic progression is standard, but it deserves to be spelled out on this site at least once. So, unless you find a duplicate you could do the honors :-)
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:30
add a comment |
1
$begingroup$
$G$ is a subgroup of $S_n,n=deg(f)$ and $g,g_2$ have the same permutation type iff $g=h g_2h^{-1}$ for some $hin S_n$. The functions on $G$ that are restrictions of class functions on $S_n$ are a smaller set than the class functions on $G$ (see how it works with abelian extensions). It is in the latter that the characters of irreducible representations of $G$ form an orthonormal basis, and Chebotarev theorem (the PNT for Artin L-functions) is $sum_{N(mathfrak{p}^k)le x} log(N(mathfrak{p})) , psi(Frob_{mathfrak{p}}^k)sim frac{x}{|G|}sum_{gin G}psi(g)$ as $xtoinfty$
$endgroup$
– reuns
Jan 5 at 3:41
2
$begingroup$
In $mathbb{Q}(zeta_m)$ then $Frob_mathfrak{p}$ depends only on $p bmod m$ where $p mathbb{Z} = mathfrak{p} cap mathbb{Z}$, so that's not cheating. The Frobenius only depending on some congruences (and ideal class) in the base field is the key idea of class field theory from which representations of abelian extension are well-understood. In non abelian extensions, things are much more complicated.
$endgroup$
– reuns
Jan 5 at 3:51
$begingroup$
No reason not to flesh out those comments to an answer @reuns? I realize that the connection with the primes in an arithmetic progression is standard, but it deserves to be spelled out on this site at least once. So, unless you find a duplicate you could do the honors :-)
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:30
1
1
$begingroup$
$G$ is a subgroup of $S_n,n=deg(f)$ and $g,g_2$ have the same permutation type iff $g=h g_2h^{-1}$ for some $hin S_n$. The functions on $G$ that are restrictions of class functions on $S_n$ are a smaller set than the class functions on $G$ (see how it works with abelian extensions). It is in the latter that the characters of irreducible representations of $G$ form an orthonormal basis, and Chebotarev theorem (the PNT for Artin L-functions) is $sum_{N(mathfrak{p}^k)le x} log(N(mathfrak{p})) , psi(Frob_{mathfrak{p}}^k)sim frac{x}{|G|}sum_{gin G}psi(g)$ as $xtoinfty$
$endgroup$
– reuns
Jan 5 at 3:41
$begingroup$
$G$ is a subgroup of $S_n,n=deg(f)$ and $g,g_2$ have the same permutation type iff $g=h g_2h^{-1}$ for some $hin S_n$. The functions on $G$ that are restrictions of class functions on $S_n$ are a smaller set than the class functions on $G$ (see how it works with abelian extensions). It is in the latter that the characters of irreducible representations of $G$ form an orthonormal basis, and Chebotarev theorem (the PNT for Artin L-functions) is $sum_{N(mathfrak{p}^k)le x} log(N(mathfrak{p})) , psi(Frob_{mathfrak{p}}^k)sim frac{x}{|G|}sum_{gin G}psi(g)$ as $xtoinfty$
$endgroup$
– reuns
Jan 5 at 3:41
2
2
$begingroup$
In $mathbb{Q}(zeta_m)$ then $Frob_mathfrak{p}$ depends only on $p bmod m$ where $p mathbb{Z} = mathfrak{p} cap mathbb{Z}$, so that's not cheating. The Frobenius only depending on some congruences (and ideal class) in the base field is the key idea of class field theory from which representations of abelian extension are well-understood. In non abelian extensions, things are much more complicated.
$endgroup$
– reuns
Jan 5 at 3:51
$begingroup$
In $mathbb{Q}(zeta_m)$ then $Frob_mathfrak{p}$ depends only on $p bmod m$ where $p mathbb{Z} = mathfrak{p} cap mathbb{Z}$, so that's not cheating. The Frobenius only depending on some congruences (and ideal class) in the base field is the key idea of class field theory from which representations of abelian extension are well-understood. In non abelian extensions, things are much more complicated.
$endgroup$
– reuns
Jan 5 at 3:51
$begingroup$
No reason not to flesh out those comments to an answer @reuns? I realize that the connection with the primes in an arithmetic progression is standard, but it deserves to be spelled out on this site at least once. So, unless you find a duplicate you could do the honors :-)
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:30
$begingroup$
No reason not to flesh out those comments to an answer @reuns? I realize that the connection with the primes in an arithmetic progression is standard, but it deserves to be spelled out on this site at least once. So, unless you find a duplicate you could do the honors :-)
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:30
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 $alphain 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)=3equiv0$, and that cubic is irreducible because it has no zeros in $Bbb{Z}_3$. Therefore there is a 3-cycle $betain 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 $alphanotin 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 $pneq2$, 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 $pequiv1pmod8$. 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).
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
$endgroup$
$begingroup$
Recently I was amused by this straightforward application of Chebotarev density theorem. Sorry about blowing my own trumpet to this extent. Trust me, that is pretty straight forward, and we have several users who know this stuff better than I do.
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:25
$begingroup$
So in general the steps to determining the density of a factorization type are: 1. Determine the Galois group 2. Determine which conjugacy classes correspond to the splitting type 3. Calculate the density by summing up the "density of each conjugacy class"
$endgroup$
– Loppukilpailija
Jan 5 at 15:32
$begingroup$
In fact, we do not even need to calculate the conjugacy classes, we can just look at the cycle types as in a weaker theorem of Frobenius. Chebotarev gives us more information than Frobenius, but we do not have to use it, as determining the conjugacy classes may be tedious.
$endgroup$
– Loppukilpailija
Jan 5 at 15:42
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062353%2fchebotarev-density-theorem-answers-to-factorization-of-polynomials%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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 $alphain 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)=3equiv0$, and that cubic is irreducible because it has no zeros in $Bbb{Z}_3$. Therefore there is a 3-cycle $betain 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 $alphanotin 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 $pneq2$, 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 $pequiv1pmod8$. 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).
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
$endgroup$
$begingroup$
Recently I was amused by this straightforward application of Chebotarev density theorem. Sorry about blowing my own trumpet to this extent. Trust me, that is pretty straight forward, and we have several users who know this stuff better than I do.
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:25
$begingroup$
So in general the steps to determining the density of a factorization type are: 1. Determine the Galois group 2. Determine which conjugacy classes correspond to the splitting type 3. Calculate the density by summing up the "density of each conjugacy class"
$endgroup$
– Loppukilpailija
Jan 5 at 15:32
$begingroup$
In fact, we do not even need to calculate the conjugacy classes, we can just look at the cycle types as in a weaker theorem of Frobenius. Chebotarev gives us more information than Frobenius, but we do not have to use it, as determining the conjugacy classes may be tedious.
$endgroup$
– Loppukilpailija
Jan 5 at 15:42
add a comment |
$begingroup$
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 $alphain 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)=3equiv0$, and that cubic is irreducible because it has no zeros in $Bbb{Z}_3$. Therefore there is a 3-cycle $betain 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 $alphanotin 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 $pneq2$, 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 $pequiv1pmod8$. 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).
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
$endgroup$
$begingroup$
Recently I was amused by this straightforward application of Chebotarev density theorem. Sorry about blowing my own trumpet to this extent. Trust me, that is pretty straight forward, and we have several users who know this stuff better than I do.
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:25
$begingroup$
So in general the steps to determining the density of a factorization type are: 1. Determine the Galois group 2. Determine which conjugacy classes correspond to the splitting type 3. Calculate the density by summing up the "density of each conjugacy class"
$endgroup$
– Loppukilpailija
Jan 5 at 15:32
$begingroup$
In fact, we do not even need to calculate the conjugacy classes, we can just look at the cycle types as in a weaker theorem of Frobenius. Chebotarev gives us more information than Frobenius, but we do not have to use it, as determining the conjugacy classes may be tedious.
$endgroup$
– Loppukilpailija
Jan 5 at 15:42
add a comment |
$begingroup$
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 $alphain 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)=3equiv0$, and that cubic is irreducible because it has no zeros in $Bbb{Z}_3$. Therefore there is a 3-cycle $betain 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 $alphanotin 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 $pneq2$, 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 $pequiv1pmod8$. 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).
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
$endgroup$
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 $alphain 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)=3equiv0$, and that cubic is irreducible because it has no zeros in $Bbb{Z}_3$. Therefore there is a 3-cycle $betain 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 $alphanotin 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 $pneq2$, 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 $pequiv1pmod8$. 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).
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
edited Jan 5 at 6:19
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
answered Jan 5 at 6:13
Jyrki LahtonenJyrki Lahtonen
108k13168371
108k13168371
$begingroup$
Recently I was amused by this straightforward application of Chebotarev density theorem. Sorry about blowing my own trumpet to this extent. Trust me, that is pretty straight forward, and we have several users who know this stuff better than I do.
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:25
$begingroup$
So in general the steps to determining the density of a factorization type are: 1. Determine the Galois group 2. Determine which conjugacy classes correspond to the splitting type 3. Calculate the density by summing up the "density of each conjugacy class"
$endgroup$
– Loppukilpailija
Jan 5 at 15:32
$begingroup$
In fact, we do not even need to calculate the conjugacy classes, we can just look at the cycle types as in a weaker theorem of Frobenius. Chebotarev gives us more information than Frobenius, but we do not have to use it, as determining the conjugacy classes may be tedious.
$endgroup$
– Loppukilpailija
Jan 5 at 15:42
add a comment |
$begingroup$
Recently I was amused by this straightforward application of Chebotarev density theorem. Sorry about blowing my own trumpet to this extent. Trust me, that is pretty straight forward, and we have several users who know this stuff better than I do.
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:25
$begingroup$
So in general the steps to determining the density of a factorization type are: 1. Determine the Galois group 2. Determine which conjugacy classes correspond to the splitting type 3. Calculate the density by summing up the "density of each conjugacy class"
$endgroup$
– Loppukilpailija
Jan 5 at 15:32
$begingroup$
In fact, we do not even need to calculate the conjugacy classes, we can just look at the cycle types as in a weaker theorem of Frobenius. Chebotarev gives us more information than Frobenius, but we do not have to use it, as determining the conjugacy classes may be tedious.
$endgroup$
– Loppukilpailija
Jan 5 at 15:42
$begingroup$
Recently I was amused by this straightforward application of Chebotarev density theorem. Sorry about blowing my own trumpet to this extent. Trust me, that is pretty straight forward, and we have several users who know this stuff better than I do.
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:25
$begingroup$
Recently I was amused by this straightforward application of Chebotarev density theorem. Sorry about blowing my own trumpet to this extent. Trust me, that is pretty straight forward, and we have several users who know this stuff better than I do.
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:25
$begingroup$
So in general the steps to determining the density of a factorization type are: 1. Determine the Galois group 2. Determine which conjugacy classes correspond to the splitting type 3. Calculate the density by summing up the "density of each conjugacy class"
$endgroup$
– Loppukilpailija
Jan 5 at 15:32
$begingroup$
So in general the steps to determining the density of a factorization type are: 1. Determine the Galois group 2. Determine which conjugacy classes correspond to the splitting type 3. Calculate the density by summing up the "density of each conjugacy class"
$endgroup$
– Loppukilpailija
Jan 5 at 15:32
$begingroup$
In fact, we do not even need to calculate the conjugacy classes, we can just look at the cycle types as in a weaker theorem of Frobenius. Chebotarev gives us more information than Frobenius, but we do not have to use it, as determining the conjugacy classes may be tedious.
$endgroup$
– Loppukilpailija
Jan 5 at 15:42
$begingroup$
In fact, we do not even need to calculate the conjugacy classes, we can just look at the cycle types as in a weaker theorem of Frobenius. Chebotarev gives us more information than Frobenius, but we do not have to use it, as determining the conjugacy classes may be tedious.
$endgroup$
– Loppukilpailija
Jan 5 at 15:42
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062353%2fchebotarev-density-theorem-answers-to-factorization-of-polynomials%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
$G$ is a subgroup of $S_n,n=deg(f)$ and $g,g_2$ have the same permutation type iff $g=h g_2h^{-1}$ for some $hin S_n$. The functions on $G$ that are restrictions of class functions on $S_n$ are a smaller set than the class functions on $G$ (see how it works with abelian extensions). It is in the latter that the characters of irreducible representations of $G$ form an orthonormal basis, and Chebotarev theorem (the PNT for Artin L-functions) is $sum_{N(mathfrak{p}^k)le x} log(N(mathfrak{p})) , psi(Frob_{mathfrak{p}}^k)sim frac{x}{|G|}sum_{gin G}psi(g)$ as $xtoinfty$
$endgroup$
– reuns
Jan 5 at 3:41
2
$begingroup$
In $mathbb{Q}(zeta_m)$ then $Frob_mathfrak{p}$ depends only on $p bmod m$ where $p mathbb{Z} = mathfrak{p} cap mathbb{Z}$, so that's not cheating. The Frobenius only depending on some congruences (and ideal class) in the base field is the key idea of class field theory from which representations of abelian extension are well-understood. In non abelian extensions, things are much more complicated.
$endgroup$
– reuns
Jan 5 at 3:51
$begingroup$
No reason not to flesh out those comments to an answer @reuns? I realize that the connection with the primes in an arithmetic progression is standard, but it deserves to be spelled out on this site at least once. So, unless you find a duplicate you could do the honors :-)
$endgroup$
– Jyrki Lahtonen
Jan 5 at 6:30