Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to figure out how many squarefree polynomials there are of a fixed degree over $\mathbb{F}_2$ specifically (and in general, over any finite field). Looking at some low-degree examples seems to suggest that half of the polynomials of any given degree are squarefree, but I'm not sure how to prove this, or whether the pattern continues at all. I'm considering the possibility of using the formal derivative, and the fact that a polynomial is relatively prime to its formal derivative iff it is squarefree, but I don't see how to proceed with this. So is there a known formula?

share|improve this question
2  
Aren't there are 32 quintics in F_2[x]? –  William D. Dec 22 '11 at 20:33
    
Sure. Sorry! And to boot I neglected to count those with irreducible quartic factors in a comment that is best forgotten ;-) –  Jyrki Lahtonen Dec 22 '11 at 20:36
add comment

1 Answer

up vote 14 down vote accepted

Recall that $$M(n, q) = \frac{1}{n} \sum_{d | n} \mu(d) q^{n/d}$$

is the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$. The statement that there are $q^n$ monic polynomials of degree $n$ over $\mathbb{F}_q$ can then be written as the generating function identity $$\zeta(t) = \prod_{n \ge 1} \frac{1}{(1 - t^n)^{M(n, q)}} = \sum_{n \ge 0} q^n t^n = \frac{1}{1 - qt}$$

which is known as the cyclotomic identity and is the analogue for $\mathbb{F}_q[t]$ of the Euler product of the Riemann zeta function. If we instead want to count the number $s_n$ of squarefree monic polynomials of degree $n$ over $\mathbb{F}_q$, we want to work out the generating function $$\sum s_n t^n = \prod_{n \ge 1} (1 + t^n)^{M(n, q)}.$$

But by inspection this is just $$\frac{\zeta(t)}{\zeta(t^2)} = \frac{1 - qt^2}{1 - qt} = 1 + \sum_{n \ge 1} (q^n - q^{n-1}) t^n.$$

(The generating function identity $\zeta(t) = \zeta(t^2) \sum s_n t^n$ merely expresses the fact that every monic polynomial can be uniquely factored into its largest square factor and its squarefree part.)

Hence for $n \ge 1$ there are $q^n - q^{n-1} = \left( 1 - \frac{1}{q} \right) q^n$ monic squarefree polynomials of degree $n$ over $\mathbb{F}_q$. Jordan Ellenberg wrote a great blog post over at Quomodocumque explaining how this is related to the braid group and the analogous question about squarefree integers here.

(Note that you don't actually have to know the closed form of $M(n, q)$ for the above argument to work; I included it for the sake of concreteness.)

share|improve this answer
    
Amazing! Thank you very much. –  William D. Dec 22 '11 at 20:32
    
+1: Very nice, indeed! –  Jyrki Lahtonen Dec 22 '11 at 20:39
    
Could you care explaining the closed form of $M(n,q)$? I'm not really seeing it. And I think the $\mu(n)$ in the sum is actually a $\mu(d)$? –  Patrick Da Silva Dec 22 '11 at 20:54
1  
@Patrick: as I said, it doesn't actually matter for this problem, but it falls out of the cyclotomic identity after Mobius inversion; more concretely, counting the number of elements of $\mathbb{F}_{q^n}$ according to the degree of their minimal polynomial over $\mathbb{F}_q$ gives $q^n = \sum_{d | n} d M(d, q)$ and Mobius inversion gives the result. See also en.wikipedia.org/wiki/Necklace_polynomial . –  Qiaochu Yuan Dec 22 '11 at 20:58
    
Hm. I didn't even think about working it out. Thanks. The sum wasn't useful for this problem but I liked the sum so I asked =P –  Patrick Da Silva Dec 22 '11 at 21:00
show 4 more comments

Your Answer

 
discard

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.