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:
- For $4 = 4$, the number of irreducible polynomial of degree 4 is $$\frac{p^4-p^2}{4}.$$
- 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})$.
- 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})$.
- For $4 = 2 + 1 + 1$, the number is $$\frac{p^2-p}{2}\cdot\binom{p}2.$$
- 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.
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} $$