Intereting Posts

Prove that $2n-3\leq 2^{n-2}$ , for all $n \geq 5$ by mathematical induction
Ease-in-out function
Adding equations in Triangle Inequality Proof
cardinality of a set of natural lattice points versus natural numbers
How can I calculate a $4\times 4$ rotation matrix to match a 4d direction vector?
Proving $n\sin(\frac{\pi}{n})<\pi<n\tan(\frac{\pi}{n})$ ; obtaining results from it.
$\int { (x^{3m}+x^{2m}+x^{m})(2x^{2m}+3x^{m}+6)^{1/m}}dx$ if $x>0$
Simplify $\int_{0}^{1}\ln(x-a)\ln x\,\mathrm{d}x$, for $a<0$
Meaning of the Axiom of regularity (foundation)
Why do people all the time exploiting almost sure properties of a stochastic process as if they were sure properties?
Equation of ellipse tangent to axes
Please integrate $\int \frac{\sqrt{x}}{\sqrt{x} + \sqrt{a-x}} \, dx$
What exactly are the curves that are a best fit to the Harmonic Cantilever?
Quarter circle train tracks
Show that $ \Lambda:a\mapsto \Lambda_a $ defines a linear map from $ l^1(\mathbb{N}) $ to $ c^0(\mathbb{N})^* $

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?

- How many countable graphs are there?
- Roots of polynomials over finite fields
- Generating function with Stirling's numbers of the second kind
- Number of irreducible polynomials with degree $6$ in $\mathbb{F}_2$
- Permutations with a cycle $>\frac{n}{2}$
- Solutions to $\binom{n}{5} = 2 \binom{m}{5}$
- number of combination in which no two red balls are adjacent.
- Application of PIE
- Using Pigeonhole Principle to prove two numbers in a subset of $$ divide each other
- board game: 10 by 10 light bulbs, minimum switches to get all off?

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.)

I am five years late, but I had the same question. While Qiaochu’s solution is neat and introduces interesting tools like zeta functions, the answer $q^d-q^{d-1}$ somehow seems teasingly combinatorial. Like Ofir pointed out, it almost seems magical.

I have an attempt at a more intuitive combinatorial solution without using zeta functions and cyclotomic identities. Please do check it out and tell me if there is any mistake. At some level, it might be a restatement of Qiaochu’s proof, but in simpler language.

So we want to count the number of square free monic polynomials in $\mathbb{F}_q[X]$ of degree $d$. Denote this number by $S_{q}(d)$. The only important fact we shall use is that every monic polynomial $f(X) \in \mathbb{F}_q[X]$ can be $uniquely$ expressed as

$$f(X)=r(X)^2.s(X)$$

where $r(X),s(X)$ are monic, and $s(X)$ is square-free. This result is folklore, but quite intuitive. The uniqueness here is essential to our counting.

Now we can build monic polynomials of degree $d$ by picking an arbitrary monic polynomial of degree $k$ for $0 \leq k \leq \lfloor d/2 \rfloor$ and a square-free polynomial of degree $d-2k$ and multiplying the square of the former with the latter (the uniqueness of the expression comes into play here in counting the possibilities). At this juncture, we would have to take cases based on whether $d$ is even or odd, and count accordingly. I’ll explore the case of $d$ being even (the other case is conceptually the same).

Since $d$ is even, fix an even $k$ at most $d$. Then we have a recurrence

$$S_{q}(d) + S_{q}(d-2) q^{1} + S_{q}(d-4)q^{2}+ \dots + q^{\frac{d}{2}}=\sum \limits_{k=0}^{d/2} S_{q}(d-2k) q^k = q^d$$

Note that $S_{q}(0)=1$ (that is, the only square-free monic polynomial of degree $0$ is the constant polynomial $1$).

A simple induction can now be used to construct $S_{q}(d)$ from $S_{q}(d-2),S_{q}(d-4),\dots,1$. In fact, one can observe that with the induction hypothesis that $S_{q}(d-2k)=q^{d-2k}-q^{d-2k-1}$ for every $0 \leq k \leq d/2$ every summand in the above recurrence is of the form $q^{d-k}-q^{d-k-1}$ and so the sum above is telescopic and simplifies to

$$S_{q}(d) + q^{d-1}=q^d$$

- A pencil approach to find $\sum \limits_{i=1}^{69} \sqrt{\left( 1+\frac{1}{i^2}+\frac{1}{(i+1)^2}\right)}$
- If $X \sim N(0,1)$, why is $E(X^2)=1$?
- Continued fraction of $e^{-2\pi n}$
- How to resolve this absolute value inequality $|1+x^2|>|x|$?
- Show that $A_n=\sum\limits_{k=1}^n \sin k $ is bounded?
- Idempotent Modules and Ideals
- Analytical Expression to find the Shortest Distance between Two Ellipses?
- How to solve $100x +19 =0 \pmod{23}$
- Tips for an adult to learn math — from the beginning.
- What is (a) geometry?
- When a semigroup can be embedded into a group
- When is the union of a family of subspaces of a vector space also a subspace?
- Socle of submodule relative to the module
- Books with more problems on card/urn and ball problems
- Why does “the probability of a random natural number being prime” make no sense?