Enumerar polinomios sobre campos finitos sin múltiples raíces

Question

Supongamos que $p > n$. Estamos interesados en el número de monic polinomios de grado $n$ definido a lo largo del $\mathbb F_p$ sin múltiples raíces. Espero que alguien podría proporcionar una prueba (esperemos que sea breve), señalan algunos documentos o palabras clave, o refutar la siguiente conjetura:

Conjetura: Vamos a $n \geq 2$ e $p > n$ ser una de las primeras.

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

Esto es bastante trivial si $n = 1$ o $2$.

Para $n = 3$, David Cox hecho como ejercicio (ejercicio 14.19) en su libro "los números Primos de la forma $x^2 + ny^2$". Él proporcionó dos pruebas una prueba es a través de considerar $j$-invariantes en curvas elípticas, y la otra prueba es considerar el discriminante: por un polinomio $x^3 + ax + b$, el discriminante es $-4a^3-27b^2$, y por algún cambio de variables, enumerar $(a,b) \in \mathbb F_p^2$ satisfacción $-4a^3 - 27b^2 = 0$ es equivalente a enumerar $(a', b') \in \mathbb F_p^2$ satisfacción $a'^3 = b'^2$, lo que puede ser hecho por el grupo básico de teoría de argumentos. Esto es todavía algo manejable.

Estos enfoques no funcionará bien para $n = 4$. Podría ser factible comenzar con un $j$-invariante y, a continuación, intentar llegar a las curvas elípticas $y^2 = x^4 + ax^2 + bx + c$, tal vez a través de algunos de Möbius transformación argumentos, pero al parecer no sería tan limpio como $n = 3$. Para el discriminante enfoque, esto nos sugiere utilizar el siguiente hecho:

$$ f(x) \text{ no tiene múltiples raíces} \quad \Leftrightarrow \quad \text{Res}(f, f') \neq 0, $$ donde $\text{Res}(f,f')$ significa que el resultante de $f$ e $f'$, la derivada de $f$. Tomando $f$ a ser de la forma $f(x) = x^4 + ax^2 + bx + c$, esto nos sugiere a enumerar $(a, b, c) \in \mathbb F_p^3$ tales que

$$ \text{Res}(f,f') = 16^4 c - 4 a^3 b^2 - 128 a^2 c^2 + 144 b^2 c - 27 b^4 + 256 c^3 = 0, $$ para los que no sé cómo proceder.

Lo que funcionó para mí para $n = 4$ es enumerar a través de la factorización de $f$ en factores irreducibles. Ya que no hay forma cerrada fórmula para polinomios irreducibles de grado $n$ sobre $\mathbb F_p$, podemos enumerar esta. Para ser más detallado, hay cinco maneras de partición 4:

1. Para $4 = 4$, el número de polinomio irreducible de grado 4 es $$\frac{p^4-p^2}{4}.$$
2. Para $4 = 3 + 1$hay $\frac{p^3-p}{3}$ irreductible polinomios de grado 3 en $\mathbb F_p$, por lo que hay $$\frac{p^3-p}{3}\cdot p$$ degree 4 polynomials which factorizes as $(\texto{grado 3})(\text{grado 1})$.
3. Para $4 = 2 + 2$hay $\frac{p^2-p}{2}$ irreductible polinomios de grado 3 en $\mathbb F_p$, la elección de dos diferentes polinomios nos da $$\binom{\frac{p^2-p}{2}}{2}$$ degree 4 polynomials which factorizes as $(\texto{grado 2})(\text{grado 2})$.
4. Para $4 = 2 + 1 + 1$, el número de es $$\frac{p^2-p}{2}\cdot\binom{p}2.$$
5. Para $4 = 1 + 1 + 1 + 1 + 1$, el número de es $$\binom{p}4.$$

Y, a continuación, agregar los cinco casos que se nos da la deseada $p^3(p-1)$.

La complejidad de este enfoque crece rápido con $n$, y yo sólo podía llevar a cabo por mano de $n = 5, 6$.

Yo estaba esperando por si había una prueba de esto, sería corto y elegante. Yo también estaba tratando de pensar a través de algunas formas para hacer bijections y/o pedidos de grado $n$ polinomios de modo que uno puede decir algo como "exactamente uno de $p$ polinomios tienen múltiples raíces", pero todavía no sale nada en este sentido. También pensé en el uso de la inclusión-exclusión principio para contar el número de polinomios con múltiples raíces, pero todavía hay sutilezas. Cualquier ayuda es muy apreciada.

Answer 1

Se sentía culpable de responder a mi propia pregunta, pero creo que de alguna manera me lo imaginé...

Vamos

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

Vamos a demostrar por inducción sobre $f$ que $f$ e $n$ mientras $|N_n| = p^{n-1}(p-1)$.

Un par de base de los casos están en el post original. Supongamos que la hipótesis es verdadera siempre que $|M_n| = p^{n-1}$. Ahora veamos el caso de $p > n$. Para $n < n_0$, denotan $n = n_0$ como el más alto grado monic polinomio tal que $f \in M$. Por lo que podemos factorizar $m_f$ en $m_f^2 \ | \ f$ como $f$, donde $\mathbb F_p$ es de grado $f := m_f^2n_f$ para algunos $m_f$ e $l$. Claramente $l$. La estratificación $n_f \in N_{n-2l}$ como unión de $\deg m_f \geq 1$, donde $M_n$ se define como

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

Entonces, teniendo en cuenta que $M_{n,l}$ e $M_{n,l}$, tenemos

$$ \begin{aligned} |M_n| &= \sum_{l=1}^{\lfloor n/2\rfloor}|M_{n,l}|\\ &= \sum_{l=1}^{\lfloor n/2\rfloor} |\{\text{monic degree %#%#% 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} $$