La Transformada Teórica de Números Inversa

Last updated on Apr 29, 2026

En los capítulos anteriores, estudiamos la Transformada de Teoría de Números (NTT), que evalúa un polinomio en sus $k$ -ésimas raíces de la unidad. Puede entenderse como la transformación de un polinomio de su forma de coeficientes a su forma de punto-valor.

La NTT se puede realizar multiplicando el vector de coeficientes de un polinomio de grado $(k-1)$ por una matriz de Vandermonde, con una complejidad temporal de $\mathcal{O}(k^2)$ . También es posible, y más interesante, usar una versión rápida y recursiva de la transformación, que reduce la complejidad temporal a $\mathcal{O}(k \log k)$ .

En este capítulo, comenzamos el estudio de la transformación inversa de la NTT, llamada Transformada Inversa de Teoría de Números, o INTT. Se puede usar para convertir un polinomio de su forma de punto-valor de vuelta a su forma de coeficientes. Este proceso se llama interpolación.

En nuestro artículo sobre interpolación de Lagrange, ya hemos visto un método para realizar la interpolación. La diferencia entre usar la interpolación de Lagrange y la Transformada Inversa de Teoría de Números es doble: la interpolación de Lagrange se puede realizar a partir de cualquier conjunto de puntos, mientras que la INTT solo se puede realizar en el conjunto de las $k$ -ésimas raíces de la unidad. Por el contrario, la interpolación de Lagrange siempre tiene una complejidad temporal de $\mathcal{O}(k^2)$ , mientras que la INTT se puede realizar en una complejidad temporal de $\mathcal{O}(k \log k)$ .

En este capítulo, vamos a:

Recordar cómo se puede realizar la evaluación utilizando una matriz de Vandermonde;
Proponer una transformación inversa que también se realiza utilizando una matriz de Vandermonde;
Demostrar que esta transformación inversa deshace la transformación original. En otras palabras, mostraremos que la evaluación a través de NTT, seguida de la interpolación a través de INTT, devuelve el polinomio a su forma de coeficientes original.

Por ahora, trabajaremos con la INTT para un polinomio de grado $3$ de modo que el lector pueda seguir más fácilmente los cálculos.

En un capítulo posterior, demostraremos que la transformación inversa propuesta se aplica a polinomios de cualquier grado.

Resumen: De la forma de coeficientes a la forma de puntos

Consideremos el polinomio

f(x)=a_0+a_1x+a_2x^2+a_3x^3

Para convertir este polinomio de la forma de coeficientes a la forma de punto-valor, es necesario evaluarlo en al menos $4$ puntos.

Por ejemplo, si el conjunto $S=\{1,\omega, \omega^2, \omega^3\}$ representa los puntos de evaluación, donde $\omega$ es una $4$ ta raíz primitiva de la unidad, las evaluaciones en estos puntos están dadas por:

\begin{aligned} f(1) &= a_0 &+& a_1 &+& a_2 &+& a_3 \\ f(\omega) &= a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\ f(\omega^2) &= a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\ f(\omega^3) &= a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9 \end{aligned}

Esto se puede expresar mediante la siguiente multiplicación de matrices:

\begin{aligned}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}&=\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega & \omega^2 & \omega^3 \\1 & \omega^2 & \omega^4 & \omega^6 \\1 & \omega^3 & \omega^6 & \omega^9\end{bmatrix}\begin{bmatrix}a_0 \\a_1 \\a_2 \\a_3\end{bmatrix} \\ \mathbf{y} &=V(\omega) \cdot \ \mathbf{a} \\ \end{aligned}

donde $V(\omega)$ se llama matriz de Vandermonde, y $\mathbf{a}$ es el vector columna que representa los coeficientes. Puedes consultar el artículo sobre matrices de Vandermonde para aprender sobre ellas en detalle. Una matriz de Vandermonde tiene la propiedad de que cada una de sus filas forma una progresión geométrica, que es una secuencia de números en la que cada término se obtiene multiplicando el anterior por una razón constante.

En la matriz $V(\omega)$ anterior, podemos notar que:

1ra fila: $[1 \ \ 1\ \ 1\ \ 1]$ $\rightarrow$ primer término: $1$ , razón común: $1$
2da fila: $[1 \ \omega\ \omega^2\ \omega^3]$ $\rightarrow$ primer término: $1$ , razón común: $\omega$
3ra fila: $[1 \ \omega^2\ \omega^4\ \omega^6]$ $\rightarrow$ primer término: $1$ , razón común: $\omega^2$
4ta fila: $[1 \ \omega^3\ \omega^6\ \omega^9]$ $\rightarrow$ primer término: $1$ , razón común: $\omega^3$

Recordemos cómo la multiplicación $\mathbf{y} =V(\omega) \cdot \ \mathbf{a}$ nos da las evaluaciones de $f(x)$ :

\mathbf{y}=\begin{bmatrix}f(1)\\[4pt]f(\omega)\\[4pt]f(\omega^2)\\[4pt]f(\omega^3)\end{bmatrix}=\begin{bmatrix}1 & 1 & 1 & 1\\[4pt]1 & \omega & \omega^2 & \omega^3\\[4pt]1 & \omega^2 & \omega^4 & \omega^6\\[4pt]1 & \omega^3 & \omega^6 & \omega^9\end{bmatrix}\begin{bmatrix} a_0\\ a_1\\ a_2\\ a_3 \end{bmatrix}

Si llevamos a cabo la multiplicación de la matriz $V(\omega)$ fila por fila, obtenemos:

\begin{aligned}f(1) = [1\ 1\ 1\ 1]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1\cdot a_0 + 1 \cdot a_1 + 1\cdot a_2 + 1\cdot a_3\\ &= a_0 + a_1 + a_2 + a_3\\[6pt]f(\omega) = [1\ \omega\ \omega^2\ \omega^3]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1 \cdot a_0 + \omega \cdot a_1 + \omega^2 \cdot a_2 + \omega^3 \cdot a_3 \\ &= a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3\\[6pt]f(\omega^2) = [1\ \omega^2\ \omega^4\ \omega^6]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1 \cdot a_0 + \omega^2 \cdot a_1 + \omega^4 \cdot a_2 + \omega^6 \cdot a_3\\ &= a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6 \\[6pt]f(\omega^3) = [1\ \omega^3\ \omega^6\ \omega^9]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1 \cdot a_0 + \omega^3 \cdot a_1 + \omega^6 \cdot a_2 + \omega^9 \cdot a_3 \\ &= a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9 \end{aligned}

Por lo tanto, obtenemos:

\begin{aligned}\mathbf{y}=\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}&=\begin{bmatrix}a_0 &+& a_1 &+& a_2 &+& a_3\\a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9\end{bmatrix} \end{aligned}

Por lo tanto, si nos dan la forma de coeficientes de un polinomio, representada por el vector $\mathbf{a}$ , podemos obtener su forma de punto-valor, representada por el vector $\mathbf{y}$ , multiplicando $\mathbf{a}$ por la izquierda por la matriz de Vandermonde $V(\omega)$ .

Pero, ¿qué pasa si en su lugar nos dan las evaluaciones, es decir, el vector $\mathbf{y}$ , y se nos pide calcular los coeficientes, es decir, el vector $\mathbf{a}$ ?

Esto se puede hacer utilizando la inversa de la matriz de Vandermonde $V(\omega)$ , denotada por $V^{-1}(\omega)$ , a través de la siguiente operación:

\mathbf{a} = V(\omega)^{-1}\cdot \mathbf{y}

Nuestra afirmación es que la matriz $V(\omega)^{-1}$ está dada por

V(\omega)^{-1} =\frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}

Observa que $V(\omega)^{-1}$ también tiene la propiedad de que cada una de sus filas forma una progresión geométrica:

1ra fila: $[1 \ \ 1\ \ 1\ \ 1]$ $\rightarrow$ primer término: $1$ , razón común: $1$
2da fila: $[1 \ \omega^{-1}\ \omega^{-2}\ \omega^{-3}]$ $\rightarrow$ primer término: $1$ , razón común: $\omega^{-1}$
3ra fila: $[1 \ \omega^{-2}\ \omega^{-4}\ \omega^{-6}]$ $\rightarrow$ primer término: $1$ , razón común: $\omega^{-2}$
4ta fila: $[1 \ \omega^{-3}\ \omega^{-6}\ \omega^{-9}]$ $\rightarrow$ primer término: $1$ , razón común: $\omega^{-3}$

Por lo tanto, la inversa de la matriz de Vandermonde en este caso es en sí misma otra matriz de Vandermonde.

En las siguientes secciones, demostraremos que nuestra afirmación es cierta en este ejemplo utilizando las $4$ -tas raíces de la unidad. En el capítulo posterior, lo demostraremos en general.

Demostraremos que, en el caso de las $k$ -ésimas raíces de la unidad, cuando la NTT se realiza utilizando la siguiente matriz de Vandermonde,

V(\omega)=\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{k-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(k-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{k-1} & \omega^{2(k-1)} & \cdots & \omega^{(k-1)(k-1)}\end{bmatrix},

la matriz inversa $V(\omega)^{-1}$ se puede obtener reemplazando cada potencia de $\omega$ con $\frac{1}{\omega}$ y dividiendo por un factor de $k$ , de la siguiente manera

V(\omega)^{-1}=\frac{1}{k}\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(k-1)} \\1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(k-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{-(k-1)} & \omega^{-2(k-1)} & \cdots & \omega^{-(k-1)(k-1)}\end{bmatrix}.

La matriz inversa de Vandermonde, cuando se multiplica por el vector de evaluaciones de un polinomio dado en las raíces de la unidad, devuelve el vector de coeficientes de ese polinomio.

Evaluando $V(\omega)^{-1} \cdot \mathbf{y}$

Para demostrar que la multiplicación de la matriz entre $V(\omega)^{-1}$ e $\mathbf{y}$ nos devuelve el vector de coeficientes $\mathbf{a}$ , usemos nuestro ejemplo anterior, donde $f(x)=a_0+a_1x+a_2x^2+a_3x^3$ , $S=\{1,\omega,\omega^2,\omega^3\}$ y $k=4$ .

Recordemos que $\mathbf{y}$ , el vector de evaluaciones de $f(x)$ en los puntos en $S$ , está dado por:

\begin{aligned}\mathbf{y}=\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}&=\begin{bmatrix}a_0 &+& a_1 &+& a_2 &+& a_3\\a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9\end{bmatrix} \end{aligned}

Realicemos la multiplicación de matrices entre $V(\omega)^{-1}$ e $\mathbf{y}$ :

\begin{aligned} \tilde{\mathbf{a}} &= V(\omega)^{-1}\cdot \mathbf{y} \\ \begin{bmatrix}\tilde{a_0} \\\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix}&= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix} \end{aligned}

Nuestro objetivo es demostrar que el vector $\tilde{\mathbf{a}}$ obtenido de la multiplicación de matrices anterior es igual al vector de coeficientes $\mathbf{a}$ de $f(x)$ .

Sustituyendo las evaluaciones $f(1),f(\omega),f(\omega^2)$ y $f(\omega^3)$ del vector $\mathbf{y}$ , podemos calcular los coeficientes $\tilde{\mathbf{a}}$ como:

\begin{aligned} \tilde{\mathbf{a}} &= V(\omega)^{-1}\cdot \mathbf{y} \\ \begin{bmatrix}\tilde{a_0} \\\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix} &= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}a_0 &+& a_1 &+& a_2 &+& a_3\\a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9\end{bmatrix} \end{aligned}

Ahora demostramos que los vectores $\tilde{\mathbf{a}}$ y ${\mathbf{a}}$ son iguales. En otras palabras, queremos mostrar que

\begin{aligned} \tilde{a_0} &= a_0, \\ \tilde{a_1} &= a_1, \\ \tilde{a_2} &= a_2, \\ \tilde{a_3} &= a_3. \\ \end{aligned}

Calculando los coeficientes $\tilde{a_0},\tilde{a_1},\tilde{a_2}$ y $\tilde{a_3}$

Llevemos a cabo la multiplicación de matrices fila por fila en el lado derecho (RHS) para ver cómo se obtienen los coeficientes correspondientes en el lado izquierdo (LHS). Para el coeficiente $\tilde{a_0}$ , tomamos el producto punto de la primera fila de $V(\omega)^{-1}$ con el vector $\mathbf{y}$ :

\begin{aligned} \begin{bmatrix}\color{red}\tilde{a_0} \\\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix} &= \frac{1}{4}\begin{bmatrix}\color{red}1 & \color{red}1 & \color{red}1 & \color{red}1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}\color{red}f(1) \\ \color{red}f(\omega) \\\color{red}f(\omega^2) \\\color{red}f(\omega^3)\end{bmatrix} \\ \end{aligned}

\begin{aligned} &\quad \quad\text{ \ \ Producto punto de la primera fila de } V(\omega)^{-1} \text{ con } \mathbf{y}\\ \tilde{a_0}&= \frac{1}{4}\big(1\cdot f(1)+1\cdot f(\omega)+1\cdot f(\omega^2)+1\cdot f(\omega^3)\big) \\[6pt] &=\frac{1}{4}\Big(1\cdot \underbrace{(a_0+a_1+a_2+a_3)}_{f(1)} \\ &\qquad\; + 1\cdot \underbrace{(a_0+a_1\omega+a_2\omega^2+a_3\omega^3)}_{f(\omega)}\\ &\qquad\; + 1\cdot \underbrace{(a_0+a_1\omega^2+a_2\omega^4+a_3\omega^6)}_{f(\omega^2)}\\ &\qquad\; + 1\cdot \underbrace{(a_0+a_1\omega^3+a_2\omega^6+a_3\omega^9)}_{f(\omega^3)}\Big)\\[6pt] &=\frac{1}{4}\Big(4a_0 \;+\; a_1(1+\omega+\omega^2+\omega^3) \\ &\qquad\; +\; a_2(1+\omega^2+\omega^4+\omega^6) \\ &\qquad\; +\; a_3(1+\omega^3+\omega^6+\omega^9)\Big) \end{aligned}

Recordemos del capítulo anterior que, dado que $\omega$ es una $4$ -ta raíz primitiva de la unidad, la suma

\sum_{k=0}^3 \omega^{mk}

es igual a cero siempre que $m$ no sea un múltiplo de $4$ . Explícitamente,

\sum_{k=0}^3 \omega^{mk} = \omega^{m\cdot 0} + \omega^{m\cdot 1} + \omega^{m\cdot 2} + \omega^{m\cdot 3} \\= 1 + \omega^m + \omega^{2m} + \omega^{3m}=0\\

Para un análisis detallado de este concepto, por favor consulta el artículo sobre Ortogonalidad de las Raíces de la Unidad.
Al sustituir valores de $m$ que no son múltiplos de $4$ , obtenemos las siguientes identidades:

\begin{aligned} \text{para } m&=1 &\rightarrow& 1+\omega+\omega^2+\omega^3=0, \quad \\\text{para }m&=2&\rightarrow&1+\omega^2+\omega^4+\omega^6=0 , \quad \\\text{para }m&=3&\rightarrow&1+\omega^3+\omega^6+\omega^9=0, \quad \\ \text{para }m&=-1&\rightarrow&1+\omega^{-1}+\omega^{-2}+\omega^{-3}=0, \quad \\\text{para }m&=-2&\rightarrow&1+\omega^{-2}+\omega^{-4}+\omega^{-6}=0, \quad \\\text{para }m&=-3&\rightarrow&1+\omega^{-3}+\omega^{-6}+\omega^{-9}=0, \quad \end{aligned}

Por lo tanto, todos los términos que multiplican a $a_1$ , $a_2$ y $a_3$ se anulan, dejando

\begin{aligned} \tilde{a_0}&=\frac{1}{4}\Big(4a_0 \;&+&\; a_1\underbrace{(1+\omega+\omega^2+\omega^3)}_{=\,0} \\ &\qquad\; &+&\; a_2\underbrace{(1+\omega^2+\omega^4+\omega^6)}_{=\,0} \\ &\qquad\; &+&\; a_3\underbrace{(1+\omega^3+\omega^6+\omega^9)}_{=\,0}\Big) \\ \tilde{a_0}&=\frac{1}{4}\cdot 4a_0 \\ &= a_0\\ \end{aligned}

De manera similar, para calcular
$\tilde{a_1}$ , tomamos el producto punto de la segunda fila de $V(\omega)^{-1}$ con $\mathbf{y}$ :

\begin{aligned} \begin{bmatrix}\tilde{a_0} \\\color{red}\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix} &= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\\color{red}1 & \color{red}\omega^{-1} & \color{red}\omega^{-2} & \color{red}\omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}\color{red}f(1) \\ \color{red}f(\omega) \\\color{red}f(\omega^2) \\\color{red}f(\omega^3)\end{bmatrix} \\ \end{aligned}

\begin{aligned} &\qquad \text{Producto punto de la 2da fila de } V(\omega)^{-1} \text{ con } \mathbf{y} \\ \tilde{a_1} &= \frac{1}{4}\big(1\cdot f(1) + \omega^{-1}f(\omega) + \omega^{-2}f(\omega^2) + \omega^{-3}f(\omega^3)\big) \\[6pt] \end{aligned}

Sustituyendo las expresiones para las evaluaciones $f(1), f(\omega), f(\omega^2)$ y $f(\omega^3)$ , obtenemos,

\begin{aligned} \tilde{a_1} &= \frac{1}{4}\Big( 1(a_0+a_1+a_2+a_3) \\ &\qquad + \omega^{-1}(a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3) \\ &\qquad + \omega^{-2}(a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6) \\ &\qquad + \omega^{-3}(a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9) \Big) \\[6pt] \end{aligned}

Agrupar los términos para obtener los factores de $a_0,a_1,a_2$ y $a_3$ da como resultado

\begin{aligned} \tilde{a_1} &= \frac{1}{4}\Big( a_0(1+\omega^{-1}+\omega^{-2}+\omega^{-3}) \\ &\qquad + a_1(1+\omega^{-1}\omega+\omega^{-2}\omega^2+\omega^{-3}\omega^3) \\ &\qquad + a_2(1+\omega^{-1}\omega^2+\omega^{-2}\omega^4+\omega^{-3}\omega^6) \\ &\qquad + a_3(1+\omega^{-1}\omega^3+\omega^{-2}\omega^6+\omega^{-3}\omega^9) \Big) \\[6pt] &= \frac{1}{4}\Big( a_0(1+\omega^{-1}+\omega^{-2}+\omega^{-3}) + 4a_1 \\ &\qquad + a_2(1+\omega^{1}+\omega^{2}+\omega^{3}) \\ &\qquad + a_3(1+\omega^{2}+\omega^{4}+\omega^{6}) \Big) \end{aligned}

Nuevamente, los términos dentro de los paréntesis asociados con los factores de $a_0,a_2,a_3$ se anulan, dejando

\begin{aligned} \tilde{a_1}&=\frac{1}{4}\cdot 4a_1 = a_1\\ \end{aligned}

Intenta expandir la multiplicación para $\tilde{a_2}$ y $\tilde{a_3}$ por tu cuenta y observa cómo se simplifican de acuerdo con la misma lógica que hemos usado anteriormente. Encontrarás que $\tilde{a_2}=a_2$ y $\tilde{a_3} = a_3$ , como se esperaba.

Esto completa la demostración de que $V(\omega)^{-1} \cdot \mathbf{y} = \mathbf{a}$ . Con esto, hemos demostrado que la inversa de la matriz de Vandermonde para el caso $k=4$ es también una matriz de Vandermonde. El caso para un valor general de $k$ se demostrará en el capítulo posterior.

Este artículo es parte de una serie sobre la Transformada de Teoría de Números en nuestro ZK Book