# Enumerating polynomials over finite fields without multiple roots

Suppose that $$p > n$$. We are interested in the number of monic polynomials of degree $$n$$ defined over $$\mathbb F_p$$ without multiple roots. I hope someone could provide a proof (hopefully to be short), point to some papers or key words, or disprove the following conjecture:

Conjecture: Let $$n \geq 2$$ and $$p > n$$ be a prime.

$$\big|\{f(x) \in \mathbb F_p(x) \ | \ \deg(f) = n \text{ and f has no multiple roots}\}\big| = p^{n-1}(p-1).$$

This is quite trivial when $$n = 1$$ or $$2$$.

For $$n = 3$$, David Cox made it as an exercise (exercise 14.19) in his book "Primes of the form $$x^2 + ny^2$$". He provided two proofs - one proof is via considering $$j$$-invariants on elliptic curves, and the other proof is by considering the discriminant: for a polynomial $$x^3 + ax + b$$, the discriminant is $$-4a^3-27b^2$$, and by some change of variables, enumerating $$(a,b) \in \mathbb F_p^2$$ satisfying $$-4a^3 - 27b^2 = 0$$ is equivalent to enumerating $$(a', b') \in \mathbb F_p^2$$ satisfying $$a'^3 = b'^2$$, which can be done by basic group theoretic arguments. This is still somewhat manageable.

These approaches will not work well for $$n = 4$$. It might be still doable to start with a $$j$$-invariant and then try to get to elliptic curves $$y^2 = x^4 + ax^2 + bx + c$$, maybe via some Mobius transformation arguments, but apparently it would not be as neat as $$n = 3$$. For the discriminant approach, this suggests us to use the following fact:

$$f(x) \text{ has no multiple roots} \quad \Leftrightarrow \quad \text{Res}(f, f') \neq 0,$$ where $$\text{Res}(f,f')$$ means the resultant of $$f$$ and $$f'$$, the derivative of $$f$$. Taking $$f$$ to be of the form $$f(x) = x^4 + ax^2 + bx + c$$, this suggests us to enumerate $$(a, b, c) \in \mathbb F_p^3$$ such that

$$\text{Res}(f,f') = 16 a^4 c - 4 a^3 b^2 - 128 a^2 c^2 + 144 a b^2 c - 27 b^4 + 256 c^3 = 0,$$ for which I do not know how to proceed.

What worked for me for $$n = 4$$ is to enumerate via the factorization of $$f$$ into irreducible factors. Since there are closed form formula for irreducible polynomials of degree $$n$$ over $$\mathbb F_p$$, we can enumerate this. To be more detailed, there are five ways to partition 4:

1. For $$4 = 4$$, the number of irreducible polynomial of degree 4 is $$\frac{p^4-p^2}{4}.$$
2. For $$4 = 3 + 1$$, there are $$\frac{p^3-p}{3}$$ irreducible polynomials of degree 3 over $$\mathbb F_p$$, so there are $$\frac{p^3-p}{3}\cdot p$$ degree 4 polynomials which factorizes as $$(\text{degree 3})(\text{degree 1})$$.
3. For $$4 = 2 + 2$$, there are $$\frac{p^2-p}{2}$$ irreducible polynomials of degree 3 over $$\mathbb F_p$$, choosing two different polynomials gives us $$\binom{\frac{p^2-p}{2}}{2}$$ degree 4 polynomials which factorizes as $$(\text{degree 2})(\text{degree 2})$$.
4. For $$4 = 2 + 1 + 1$$, the number is $$\frac{p^2-p}{2}\cdot\binom{p}2.$$
5. For $$4 = 1 + 1 + 1 + 1 + 1$$, the number is $$\binom{p}4.$$

And then adding the five cases gives us the desired $$p^3(p-1)$$.

The complexity of this approach grows fast with $$n$$, and I could only carry this out by hand for $$n = 5, 6$$.

I was expecting if there were a proof for this, it would be short and elegant. I was also trying to think via some ways for doing bijections and/or ordering for degree $$n$$ polynomials so that one can say something like "exactly one out of $$p$$ polynomials have multiple roots", but still nothing comes out in this direction. I also thought about using inclusion-exclusion principle to count the number of polynomials with multiple roots, but there are still subtleties. Any help is appreciated.

• Just wondering whether it might be possible to use an averaging argument (haven't made it work) - with $p(x)=xq(x)+r$ and the average number of options for $r$ to make this have one or more multiple roots is $1$ (over the choices for $q(x)$). – Mark Bennet Jun 2 at 15:52
• @MarkBennet: Not sure if I am understanding your correctly, but I guess you want some induction arguments, and when proceeding from $n$ to $n+1$, you want to say some thing like varying the constant term, in average $1$ out of the $p$ polynomials have multiple roots? Thought of this very briefly, but not sure if it works. Fixing $xq(x)$, $\text{Res}(xq(x) + r, (xq(x)+r)')$ is a degree $n$ polynomial in $r$, so it sound like a certain family degree $n$ polynomial has 1 root in $\mathbb F_p$ in average. This should be asymptotically true, but we are expecting exact statements... – Hw Chu Jun 2 at 16:04
• If you count $p^n$ polynomials and lose one for each of the $p^{n-1}$ possibilities for $g(x)$ you get an exact answer. Some polynomials $g(x)$ will exclude several possible values of $r$ - but then there ought to be an equivalent number which give no multiple root for any value of $r$. That was the thought, anyway. [Whatever method is used must surely have some issue to resolve for $n=p$] – Mark Bennet Jun 2 at 16:13

Felt guilty to answer my own question, but I think I somehow figured it out...

Let

\begin{aligned} N_n &:= \{f(x)\in \mathbb F_p \ | \ \deg f(x) = n \text{ and f has no multiple roots}\}\\ M_n &:= \{f(x)\in \mathbb F_p \ | \ \deg f(x) = n \text{ and f has multiple roots}\}. \end{aligned}

We will prove by induction on $$n$$ that $$|N_n| = p^{n-1}(p-1)$$ and $$|M_n| = p^{n-1}$$ while $$p > n$$.

A few base cases are in the original post. Suppose that the hypothesis is true whenever $$n < n_0$$. Now look at the case $$n = n_0$$. For $$f \in M$$, denote $$m_f$$ as the highest degree monic polynomial such that $$m_f^2 \ | \ f$$. So we can factorize $$f$$ in $$\mathbb F_p$$ as $$f := m_f^2n_f$$, where $$m_f$$ is of degree $$l$$ for some $$l$$ and $$n_f \in N_{n-2l}$$. Clearly $$\deg m_f \geq 1$$. Stratifying $$M_n$$ as union of $$M_{n,l}$$, where $$M_{n,l}$$ is defined as

$$M_{n,l} := \{f(x) \in M_n \ | \ \deg m_f = l\}.$$

Then, keeping in mind that $$|N_0| = 1$$ and $$|N_1| = p$$, we have

\begin{aligned} |M_n| &= \sum_{l=1}^{\lfloor n/2\rfloor}|M_{n,l}|\\ &= \sum_{l=1}^{\lfloor n/2\rfloor} |\{\text{monic degree l polynomials}\}|\cdot|N_{n-2l}|\\ &= \left(\sum_{l=1}^{\lfloor (n-2)/2\rfloor} p^l\cdot p^{n-2l-1}(p-1)\right) + p^{\lfloor n/2\rfloor}\cdot p^{n - 2\lfloor n/2\rfloor}\\ &= p^{n-1} - p^{n-\lfloor n/2\rfloor} + p^{n-\lfloor n/2\rfloor} = p^{n-1}. \end{aligned}