MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So let $f(x)\in\mathbf{Z}[x]$ be a monic polynomial of degree $d$ and let $K$ be the splitting field of $f$. Let us define the "heigt of $f$" $:=||f||$ to be the maximum of the abolute values of the coefficients of $f$. (Instead of the height it might be better to work with the abolute value of the discriminant of $K$).

Let us denote the Galois group of $f$ over $\mathbf{Q}$ by $G$. For each prime number for which the roots of $f$ modulo $p$ are distinct we denote by $G_p$ the Galois group of $f\pmod{p}$. A cute result that may be found for example in Van der Waerden first algebra book says that there exists an (non-canonical but well defined up to conjugation in $G$) injection of $G_p$ in $G$. By elementary group theory, if we take the group generated by a set of representatives of the conjugacy classes of $G$ then it generates $G$. Thus by Chebotarev density theorem, we know that there exists a finite set of prime numbers $S$ of $\mathbf{Q}$ such that $$ G_S:=\langle G_p| p\in S\rangle=G. $$ In particular, we may always choose a set $S$ with $G_S=G$ and $|S|\leq r$ where $r$ is the number of conjugacy classes of $G$.

Q: So let $S_x$ be the set of all prime numbers less than $x$. Is it possible to find explicitly a lower bound for $x$ in terms $||f||$ (or $|disc(K)|$) and $d$ such that $$ G_{S_x}=G? $$

added: So basically, I'm just asking for an effective version of the Chebotarev density theorem for the splitting field of $f$, this is probably well known to the expert. So probably one should consider $|disc(K)|$ rather than $||f||$ which can be arbitrary large for a fixed $K$ (even though $f$ may have bad reduction for many primes $p$ which do not divide $|disc(K)|$)

share|cite|improve this question
I removed some of the tags which seemed unnecessary to me. – Yemon Choi Jun 29 '11 at 1:02
Five. One to hold the light bulb, four to turn the ladder. $$ $$ I was able to hold off for an hour from posting this, but sometimes one must give in to temptation. – Will Jagy Jun 29 '11 at 2:05
Hi @Will, well my Q1 was kind of stupid. I realized it. If you take one representative in $G$ for every conjugacy class then it generates $G$, so this gives some easy lower bound. In any case, thanks for your comment. – Hugo Chapdelaine Jun 29 '11 at 2:57
I am about as far from being an expert as is possible. So please excuse what might be a trivial comment. But it seems that if for each prime you only know that there exists a non-canonical injection $G_p \to G$, then even knowing a bunch of $G_p$s by no means is enough to determine the group $G$. Ok, fine, but it's worse: it seems perfectly possible that depending on the choice of injections $G_p \to G$, the set of necessary $p$s can vary vastly. Now, maybe there's more structure that I'm not aware of? – Theo Johnson-Freyd Jun 29 '11 at 3:06
up vote 10 down vote accepted

You are looking for the very useful paper

Effective versions of the Chebotarev density theorem, J. C. Lagarias and A. M. Odlyzko, pp. 409-464 in Algebraic Number Fields, A. Frohlich (ed.), Academic Press, 1977.

The bounds there are quite large, as I recall, especially if you don't want to assume GRH. There is very nice recent work of Jouve, Kowalski, and Zywina that give a lot of insight into how to do this in practice and how many prime numbers you shoudl expect to have to use: see Kowalski's blog post about this and work cited there.

share|cite|improve this answer
Thanks JSE for the reference – Hugo Chapdelaine Jun 29 '11 at 3:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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