Elevar un polinomio a una potencia

Question

Sea $f$ ser un grado $n$ polinomio univariado en $Z[x]$ definido como $f = \sum\limits_{i=0}^{i=n} f_i x^i$ . Sea $$g = f^2 = f \cdot f = \sum\limits_{k=0}^{k=2n} g_k x^k$$ sea el cuadrado de $f$ . Intento encontrar una expresión para los coeficientes $g_k$ . Hasta ahora, tengo la expresión estándar: $$g_k = \sum\limits_{i+j=k,0 \le i,j \le n} f_i f_j.$$ Pero mientras jugaba con polinomios en Maple, me di cuenta de que (aparentemente) hay más estructura en los coeficientes. ¿Existe una fórmula más agradable para elevar un polinomio a potencias arbitrarias? (¿y más concretamente a la potencia 2?)

Answer 1

Al menos puedes hacerlo más rápido, utilizando la transformada discreta de Fourier.

Sea $a$ sea un vector con $2n$ elementos cuyo primer $n$ son los coeficientes del polinomio $f$ el resto cero. Sea $c$ sea el vector con los coeficientes de $g$ . Entonces $c$ es la convolución cíclica de $a$ consigo misma:

$$c = a * a$$

Pero la convolución se convierte en multiplicación bajo la transformada de Fourier $\mathcal F$ :

$$\mathcal F (c) = \mathcal F(a) \mathcal F(a)$$

utilizando la transformada inversa de Fourier se obtiene:

$$c = \mathcal F^{-1} \left( \mathcal F(a) \mathcal F(a) \right)$$

Por supuesto, esto puede generalizarse a potencias arbitrarias y polinomios que no sean iguales.

Answer 2

He escrito esto para el caso más general de la p'ª potencia de una serie de potencias $ f(x)=1+ax+bx^2+... $ Basta con poner a cero todos los coeficientes no deseados. He aquí una captura de pantalla: Los coeficientes numéricos en algún término $ a^{e_1}*b^{e_2}*c^{e_3} $ depende de las ocurrencias de los exponentes y del número de factores (multinomios)