Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I have a problem with calculating a strange limes:

Let $ m \in \mathbb{N}$ be fixed and $q=p^n$ (a variabel prime power) for $n \in \mathbb{N}$ and $p$ prime. We define $$c_m=|\left\lbrace f \in \mathbb{F}_q[X]; f \ \text{irreducible, monic, deg}(f)=m \right\rbrace|. $$

Now I have to calculate $\lim_{q \to \infty} \frac{c_m}{q^m}$. And motivated from this limes the question is: Which magnitude has $$c_m=|\left\lbrace f \in \mathbb{F}_q[X]; f \ \text{irreducible, monic, deg}(f)=m \right\rbrace|$$ for large $q$?

share|cite|improve this question
Calculating $\lim_{q \to \infty} \frac{c_m}{q^m}$ means to solve $\lim_{q \to \infty} \frac{\frac{1}{m} \sum_{d|m}\mu(d)q^{\frac{m}{d}}}{q^m}$ because $c_m=\frac{1}{m} \sum_{d|m}\mu(d)q^{\frac{m}{d}}$. I think the result must be either $0$ or $1$. Otherwise I would be surprised. But I don't know how to handle such a limes. My idea was to find an upper and lower bound and then to argue with the sandwich theorem, but maybe there is a shorter solution. – math_space Apr 5 '14 at 13:45
up vote 5 down vote accepted

$$\lim_{q \to \infty}\frac{c_m}{q^m} = \frac{1}{m}$$

The reason is that $$\begin{eqnarray}\frac{c_m}{q^m} &=& \frac{1}{q^m}\frac{1}{m}\sum_{d\mid m}\mu(d) q^{m/d} \\&=& \frac{1}{m}\left(1+\sum_{1<d\mid m}\mu(d)q^{m/d-m}\right).\end{eqnarray}$$ Now for $q\to \infty$ the sum has a constant number of summands, therefore $$\begin{eqnarray}\lim_{q\to\infty}\frac{c_m}{q^m} &=& \frac{1}{m}+ \frac{1}{m} \sum_{1<d\mid m}\mu(d)\lim_{q\to\infty}q^{m/d-m} \\&=&\frac{1}{m}.\end{eqnarray}$$

Concerning the magnitude of $c_m$ we can see from the above that for $q \to \infty$ $$c_m = \frac{1}{m}q^m-O(q^\frac{m}{2})$$.

share|cite|improve this answer
Very nice! Could you explain how you get $c_m = \frac{1}{m}q^m-O(q^\frac{m}{2})$ from $\lim_{q \to \infty}\frac{c_m}{q^m} = \frac{1}{m}$ for a constant $C$? Is $c_m = \frac{1}{m}q^m-O(q^\frac{m}{2})$ equivalent to $\frac{1}{m}q^m-c_m \leq C q^\frac{m}{2}$? – math_space Apr 5 '14 at 16:56
The claim of the $O$-statement is that there is $C$ independent from $q$ such that $|\frac{q^m}{m}-c_m| \leq Cq^\frac{m}{2}$ for all $q$. We can see this as follows: We know that $$c_m = \frac{q^m}{m}+\frac{1}{m}\sum_{1<d\mid m}\mu(d)q^{m/d}$$ Now as $$\frac{1}{m}\sum_{1<d\mid m}\mu(d)q^{m/d} \leq \frac{m-1}{m}q^{m/2}$$ we know that $|\frac{q^m}{m}-c_m| \leq q^{m/2}$. – benh Apr 5 '14 at 17:06
I think I got it. So we can say $$ c_m \leq \frac{q^m}{m}+q^{\frac{m}{2}}.$$ If I try to interpret this reslut in words: For large $q$ we have also a large number of irreducible polynomials and as higher the grade $m$ gets as larger $c_m$ gets. Well - this is not really surprising. Perhaps I have overlooked something? – math_space Apr 5 '14 at 17:58
@math_space Well, of course we expect some term increasing in $q$ and $m$, but the question is how this behavior looks like exactly. The statement $c_m = \frac{1}{m}q^m-O(q^\frac{m}{2})$ does not only give you the answer to your question on $c_m/q^m$ but also an explanation for how fast this convergence actually is. I mentioned it because results similar to the above (but WAY harder to prove) play a role in the theory of function fields over finite fields, for example in Bombieri's proof of the "Riemann Hypothesis of function fields over finite fields". – benh Apr 5 '14 at 18:57

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.