Partición de polinomios en $\mathbb{Z}[x,y]$ por los primos que representan

Question

Suponga que tiene un conjunto $S\subset\mathbb{Z}[x,y].$ ¿Cómo se pueden dividir eficazmente los polinomios en conjuntos de manera que los primos representados por los polinomios en cualquier conjunto sean idénticos? A estos efectos, "eficiente" puede interpretarse como "subcuadrático", aunque me interesa tanto el caso práctico como el teórico/peor.

Un caso especial de especial interés: las formas cuadráticas binarias $ax^2+bxy+cy^2.$

Para cualquier par de polinomios, es posible comprobar si los dos son formas equivalentes. Por supuesto, esto requiere comprobar cuadráticamente muchos pares. Una forma práctica de acelerar el proceso sería dividir primero los polinomios por discriminante, en el caso de las formas cuadráticas binarias, $b^2-4ac.$ Esto sólo requiere un tiempo (esencialmente) lineal, y da lugar a una aceleración por un factor de $k$ si hay $k$ discriminantes con un número aproximadamente igual de polinomios para cada uno (tiempo $n^2/k^2$ para cada discriminante, $k$ discriminantes). ¿Existen otros invariantes que puedan utilizarse de forma similar?

Answer 1

Abordaré el caso especial de las formas cuadráticas binarias. Algo de esto se aplica de forma más general.

En primer lugar, dividir los polinomios $ax^2+bxy+cy^2$ por su discriminante $\Delta=b^2-4ac$ como se menciona en la pregunta. Polinomios con $\Delta>0$ tienen una forma reducida única, es decir, pueden representarse de forma única como $ax^2+bxy+cy^2$ con $$\left|\sqrt\Delta-2|c|\right|<b<\sqrt\Delta$$

Así, dentro de un discriminante positivo dado, se pueden recoger inmediatamente formas equivalentes.

Los polinomios con discriminante negativo sólo tienen un número finito de formas con $$|b|\le a\le c$$ (A reducir, $b\ge0$ si $a\in\{|b|,c\},$ pero, por supuesto, la finitud no depende de esto). No está claro que esto sea práctico a la hora de comparar formas; depende del tamaño de los coeficientes y del número de formas de un determinado discriminante.

Por supuesto, dado que sólo se desean los primos de esos discriminantes, se pueden hacer ciertas transformaciones que de otro modo serían inadmisibles. Por ejemplo, los polinomios con contenido no unitario $c$ puede reducirse a $\{c\}$ o $\emptyset$ según corresponda. Ampliando ligeramente a los polinomios cuadráticos binarios, se pueden hacer sustituciones de paridad: $$x^2+2y^2\mapsto (2x+1)^2+2y^2$$