Coeficientes de $p\circ p$ para el polinomio $p(x)=\sum_{k=0}^d a_kx^k$

Question

Sea $p(x)=\sum_{k=0}^d a_kx^k$ sea un polinomio de grado $d$ . Entonces \begin{align*} (p\circ p)(x) &= \sum_{k=0}^da_k\left(\sum_{j=0}^da_j x^j\right)^k\\[3pt] &=\sum_{k=0}^d \sum_{\substack{k_0+\cdots+k_d=k\\[3pt]k_0,\dots,k_d\geqslant0}}a_k\frac{k!}{k_0!k_1!\cdots k_d!} x^{k_1+2k_2+3k_3+\cdots+d k_d}\prod_{t=0}^da_t^{k_t} \end{align*} por el teorema multinomial .

¿Hay alguna forma más agradable de expresar los coeficientes de $p\circ p$ ? ¿Dónde puedo leer más sobre este polinomio y estudiar sus propiedades?

Answer 1

TL;DR: Hay varias formas de organizar el cálculo de estos coeficientes. Ninguna de ellas da una expresión de forma totalmente cerrada (como era de esperar), por lo que cuál sea la mejor depende de la aplicación. El más eficiente para la implementación en un ordenador es el método de Fourier que se explica a continuación.

---

Permítanme aportar múltiples enfoques a este problema.

Enfoque 1: Asalto directo.

Veamos qué ocurre si sólo intentamos evaluar el coeficiente de $x^m$ en $\sum_k a_k \left(\sum_j a_j x^j\right)^k$ directamente, empezando con valores pequeños de $m$ .

• Para $m=0$ sólo el $j=0$ de la suma interna, por lo que el coeficiente de $x^m$ es $\sum_k a_k (a_0)^k = p(a_0) = p(p(0))$ .
• Para $m=1$ en cada término de la suma exterior buscamos tener una potencia de $x$ . Al ampliar $\left(\sum_j a_j x^j\right)^k$ hay $k$ formas de elegir un término $a_1 x^1$ y el otro $k-1$ factores de la potencia deben ser $a_0 x^0$ . Por lo tanto, el coeficiente de $x^1$ es $\sum_k a_k \left(k a_1 a_0^{k-1}\right)$ . Esto puede simplificarse observando que $\sum_k k a_k y^{k-1}$ es precisamente $p'(y)$ de modo que el coeficiente de $x^1$ se convierte en $a_1 p'(a_0)$ . Desde $a_1=p'(0)$ que, a su vez, puede escribirse como $p'(p(0)) p'(0)$ .

¿Ves ya el patrón? Todo lo que estamos haciendo es calcular los coeficientes de la serie de Taylor. En general, el coeficiente de $x^m$ será $$\left.\frac{1}{m!} \frac{d^m p(p(x))}{dx^m}\right|_{x=0}$$ Así, por ejemplo, para $m=2$ tendremos $\frac{1}{2}\left(p''(p(0)) p'(0)^2 + p'(p(0)) p''(0)\right)$ .

Enfoque 2: métodos de Fourier.

(Nota: Esta es una recapitulación de esta entrada (también enlazado en los comentarios anteriores).

Cuando multiplicas dos polinomios, sus coeficientes se " convolucionado ". Así que si $c_p(j)$ denota el $j^{th}$ coeficiente del polinomio $p$ entonces el coeficiente de un producto $pq$ viene dada por $c_{pq}(j) = \sum_k c_p(k) c_q(j-k) = (c_p * c_q)(j)$ donde $*$ denota convolución. Si se toma una potencia de un polinomio, como $p^k$ entonces sus coeficientes se convuelven consigo mismos $k$ veces, que se denota $c_p^{*k}$ . Con esta notación podemos escribir $c_{p\circ p}(j) = \sum_k c_p(k) c_p^{*k}(j)$ .

La forma más eficaz de tratar las convoluciones es mediante la transformada de Fourier. Si no estás familiarizado con el análisis de Fourier, esto puede parecer misterioso, pero si realmente quieres calcular los coeficientes de un polinomio iterado, por ejemplo, en un ordenador, ésta es casi con toda seguridad la mejor manera. El resultado principal es (como se muestra en el enlace anterior) que $$c_{p\circ p} (j) = \mathcal{F}^{-1} \left[ p\circ p\left(e^{-2\pi i k/N}\right)\right](j)$$ donde $\mathcal{F}^{-1}$ es una transformada discreta de Fourier inversa de longitud $N$ . Esto proporciona una forma eficaz y fácil de aplicar para calcular los coeficientes de polinomios iterados.

Una receta de pseudocódigo para implementar esto sería algo como lo siguiente:

m = ... # set this to the degree of polynomial p
N = m^2 + 1 # chosen to be total number of coefficients of p(p(x))
y = [p(p(exp(-2*pi*i*k/N))) for k=0:(N-1)]
coefficients = InverseDFT(y) # these are the coefficients of p(p(x))

(Tenga en cuenta que esto supone una normalización convencional de su DFT, por lo que puede que necesite, por ejemplo, dividir por $\sqrt{N}$ si su software utiliza una normalización diferente).

Enfoque 3: fórmula de Cauchy.

Escribiendo el método de Fourier de forma más explícita se obtiene una fórmula más fácil de entender. Sea $\omega$ sea una primitiva $N^{th}$ raíz de la unidad, con $N \ge \deg(p\circ p)$ . Entonces el coeficiente $c_{p\circ p}(j)$ se puede escribir $$c_{p\circ p}(j) = \frac{1}{N} \sum_{k=0}^{N-1} \omega^{-jk} p(p(\omega^k))$$ Se trata esencialmente de la fórmula integral de Cauchy especializada para el caso que nos ocupa. Se deduce directamente de la fórmula de Fourier anterior (cf. este post de MO relacionado ).

Answer 2

No es exactamente la respuesta que buscas, pero para divertirse tomando un cúbico $p(z) = a_0 + a_1 z + a_2 z^2 + a_3 z^3$ , $p(p(z)) = c_0 + \cdots + c_9 z^9$ donde: \begin{align} c_0 &= a_{0}^{3} a_{3} + a_{0}^{2} a_{2} + a_{0} a_{1} + a_{0} \\ c_1 &= 3 \, a_{0}^{2} a_{1} a_{3} + 2 \, a_{0} a_{1} a_{2} + a_{1}^{2} \\ c_2 &= 3 \, a_{0} a_{1}^{2} a_{3} + 3 \, a_{0}^{2} a_{2} a_{3} + a_{1}^{2} a_{2} + 2 \, a_{0} a_{2}^{2} + a_{1} a_{2} \\ c_3 &= a_{1}^{3} a_{3} + 6 \, a_{0} a_{1} a_{2} a_{3} + 3 \, a_{0}^{2} a_{3}^{2} + 2 \, a_{1} a_{2}^{2} + 2 \, a_{0} a_{2} a_{3} + a_{1} a_{3} \\ c_4 &= 3 \, a_{1}^{2} a_{2} a_{3} + 3 \, a_{0} a_{2}^{2} a_{3} + 6 \, a_{0} a_{1} a_{3}^{2} + a_{2}^{3} + 2 \, a_{1} a_{2} a_{3} \\ c_5 &= 3 \, a_{1} a_{2}^{2} a_{3} + 3 \, a_{1}^{2} a_{3}^{2} + 6 \, a_{0} a_{2} a_{3}^{2} + 2 \, a_{2}^{2} a_{3} \\ c_6 &= a_{2}^{3} a_{3} + 6 \, a_{1} a_{2} a_{3}^{2} + 3 \, a_{0} a_{3}^{3} + a_{2} a_{3}^{2} \\ c_7 &= 3 \, a_{2}^{2} a_{3}^{2} + 3 \, a_{1} a_{3}^{3} \\ c_8 &= 3 \, a_{2} a_{3}^{3} \\ c_9 &= a_{3}^{4} \\ \end{align}