Sesión Álgebra Computacional y Conmutativa

Diciembre 14, 11:20 ~ 11:40

Subresultantes de $(x-\alpha)^m$ y $(x-\beta)^n$: polinomios de Jacobi y complejidad.

Valdettaro, Marcelo Alejandro

Las {\em subresultantes} de dos polinomios univariados fueron introducidas por C.G. Jacobi y J.J. Sylvester. Éstas son polinomios que determinan no solamente quién es exactamente el máximo común divisor de los dos polinomios, sino que además describen toda la sucesión de restos en el algoritmo de Euclides extendido, al dividir un polinomio por el otro. \\ Dado un cuerpo $K$ y $f=\sum_{i=0}^m a_i x^i$, $g=\sum_{i=0}^n b_i x^i \in K[x]$ de grados $m$ y $n$, y dado $0\le d<\min\{m,n\}$ o $d=\min\{m,n\}$ si $m\ne n$, la subresultante de orden $d$ entre $f$ y $g$ se define como \[Sres_d(f,g)(x):= \det \begin{array}{|cccccc|c} \multicolumn{6}{c}{\scriptstyle{m+n-2d}}&\\ \cline{1-6} a_{m} & \cdots & &\cdots &a_{d+1-(n-d-1)} &x^{n-d-1}f(x)& \\ & \ddots & &&\vdots & \vdots& \scriptstyle{n-d}\\ & & a_m& \dots &a_{d+1}&f(x)& \\ \cline{1-6} b_{n} &\cdots & &\cdots &b_{d+1-(m-d-1)} &x^{m-d-1}g(x)&\\ &\ddots && &\vdots &\vdots &\scriptstyle{m-d}\\ &&b_{n} & \cdots & b_{d+1} &g(x)&\\ \cline{1-6} \multicolumn{2}{c}{} \end{array}\ \in K[x],\] que resulta ser, cuando no es nula, un polinomio de grado menor o igual que $d$. El caso $d=0$ se corresponde con la resultante $Res(f,g)$.\\ Estudiamos aquí el caso extremal en que los dos polinomios tienen una sola raíz múltiple cada uno. Obtenemos la expresión: { \small \[Sres_d((x-\alpha)^m,(x-\beta)^n)(x)={(-1)}^{\binom{d}{2}}(\alpha-\beta)^{(m-d)(n-d)} \sum_{j=0}^d q_j(m,n,d)(x-\alpha)^j(x-\beta)^{d-j},\]} donde los coeficientes $q_0(m,n,d), \ldots, q_d(m,n,d)$ satisfacen \begin{align*} q_0(m,n,d)&=(-1)^{\binom{d}{2}} \displaystyle{\prod_{i=1}^{d}}\dfrac{(i-1)!\,(m+n-2d+i-2)!}{(m-i-1)!(n-i)!},\\ q_j(m,n,d)&= \frac{\binom{d}{j}\binom{n-d+j-1}{j}}{\binom{m-1}{j}} \, q_0(m,n,d) \quad \text{para} \quad 1\le j\le d.\end{align*} Más aún, probamos que las subresultantes en este caso son un múltiplo escalar de un polinomio de Jacobi, salvo un cambio de variables afín. Esto implica, dada la ecuación diferencial satisfecha por los polinomios de Jacobi, que los coeficientes de $Sres_d((x-\alpha)^m,(x-\beta)^n)(x)$ en la base monomial satisfacen una recurrencia lineal de segundo orden. Este hecho permite deducir que, para un cuerpo de característica 0 o suficientemente grande, se pueden determinar con complejidad aritmética lineal dichos coeficientes de una de estas subresultantes. Esto siginifica una complejidad óptima para el cálculo de las subresultantes de esta familia estructurada de polinomios, más eficiente que el cálculo de las subresultantes de polinomios arbitrarios.

Autores: Valdettaro, Marcelo Alejandro / Bostan, Alin / D Andrea, Carlos / Krick, Teresa / Szanto, Agnes.