6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$). $\endgroup$ – Mark Bennet Jun 2 at 15:52
  • $\begingroup$ @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... $\endgroup$ – Hw Chu Jun 2 at 16:04
  • $\begingroup$ 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$] $\endgroup$ – Mark Bennet Jun 2 at 16:13
1
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.