Evaluación de funciones multivaluadas mediante expansión de raíz cuadrada

Last updated on Nov 12, 2025

En el capítulo anterior sobre Preservación de la Imagen de Funciones Multivaluadas vimos que en lugar de evaluar $f(x)$ en las raíces $k$ -ésimas de la unidad, podemos transformar $f(x)$ en una función multivaluada y evaluarla en el dominio $\set{1}$ .

Desenvolviendo raíces cuadradas

Es mucho más fácil pensar en la raíz octava de 1 como raíces cuadradas anidadas:

\sqrt[8]{x}=\sqrt{\sqrt{\sqrt{x}}}

Ahora mostramos cómo evaluar:

\sqrt{\sqrt{\sqrt{1}}}

utilizando la expansión de raíz cuadrada.

Sabemos que $\sqrt{1}$ se evalúa como $\set{1,-1}$ , por lo que reemplazamos la raíz cuadrada más interna de 1 con sus evaluaciones:

Esto “elimina” una capa de raíces cuadradas. A continuación, evaluamos $\sqrt{1}$ y $\sqrt{-1}$ . Dado que estamos trabajando con las raíces octavas de la unidad, $-1\equiv\omega^4$ por lo que $\sqrt{-1}=\{\omega^2,-\omega^2\}$

Luego, evaluamos cada una de las raíces cuadradas restantes:

Observa que las “hojas” del árbol de evaluación son exactamente $f$ evaluada en una raíz octava de la unidad.

Evaluando $f(x)=x^2$ en las raíces octavas de la unidad

Lo bueno de la expansión de raíz cuadrada es que para la mayoría de las potencias de $x$ , las raíces cuadradas “desaparecen temprano” como muestra este ejemplo. Reemplazamos $x$ con $\sqrt[8]{x}$ , pero dado que $x$ está al cuadrado, terminamos con $\sqrt[4]{x}$ o

\sqrt{\sqrt{x}}

Aquí está el árbol de evaluación al expandir repetidamente las raíces cuadradas hasta tener ocho evaluaciones. En la fila final, cuando ya no hay raíces cuadradas, simplemente copiamos los valores hacia abajo.

Ahora observa qué sucede si evaluamos las raíces octavas de la unidad $\set{1,...,\omega^7}$ directamente en $f(x)=x^2$ — el resultado es exactamente el mismo.

\begin{align*} f(1)&=(1)^2&=1\\ f(-1)&=(-1)^2&=1\\ f(\omega^2)&=(\omega^2)^2&=-1\\ f(-\omega^2)&=(-\omega^2)^2&=-1\\ f(\omega)&=(\omega)^2&=\omega^2\\ f(-\omega)&=(-\omega)^2&=\omega^2\\ f(\omega^3)&=(\omega^3)^2&=-\omega^2\\ f(-\omega^3)&=(-\omega^3)^2&=-\omega^2\\ \end{align*}

Evaluando $f(x)=x^4$ en las raíces octavas

Nuevamente, reemplazamos $x$ con $\sqrt[8]{x}$ , lo cual nos da $\sqrt{x}$ . Dado que solo tenemos una raíz cuadrada, solo expandiremos la raíz cuadrada una vez, y luego simplemente copiaremos los resultados hacia abajo.

Vimos en un capítulo anterior que $x^{k/2}$ es 1 si se evalúa en una potencia par de $\omega$ y -1 en caso contrario. El resultado aquí coincide con el resultado esperado.

Evaluando $f(x)=ax+bx^5$ en las raíces octavas de la unidad

Si reemplazamos $x$ con $\sqrt[8]{x}$ , obtenemos un resultado un poco incómodo:

f(x)=a\sqrt[8]{x}+bx^{5/8}

Sin embargo, si factorizamos $x$ primero para convertir $f(x)$ en $f(x)=x(a+bx^4)$ , la nueva forma se vuelve mucho más manejable cuando sustituimos $x$ por $\sqrt[8]{x}$ :

g(x)=\sqrt[8]{x}(a+b\sqrt{x})

La primera raíz cuadrada desaparecerá después de la primera evaluación y $(a+b\sqrt{x})$ se convertirá en una constante durante la mayor parte del árbol.

A continuación se muestra un diagrama de la expansión de las raíces cuadradas. En cada nivel, desenvolvemos (evaluamos) una raíz cuadrada. Las raíces cuadradas en azul representan las evaluadas en cada paso. Como regla general, evalúa la raíz cuadrada más interna si está anidada:

Ahora comparemos el resultado con evaluar $f(x)=ax+bx^5$ en las raíces octavas de la unidad una por una:

\begin{array}{rcll} f(1) &=& a(1) + b(1)^5 &= a + b\\[4pt] f(-1\equiv\omega^4) &=& a\omega^4 + b\omega^{20} = a(-1) + b(-1) &= -a - b\\[4pt] f(\omega^2) &=& a\omega^2 + b\omega^{10} = a\omega^2 + b\omega^2 &= (a + b)\omega^2\\[4pt] f(-\omega^{2}\equiv\omega^6) &=& a\omega^6 + b\omega^{30} = a(-\omega^2) + b(-\omega^2) &= -(a + b)\omega^2\\[4pt] f(\omega) &=& a\omega + b\omega^5 &= a\omega - b\omega \\[4pt] f(-\omega\equiv\omega^5) &=& a\omega^5 + b\omega^{25} = a(-\omega) + b\omega &= -a\omega + b\omega = (b - a)\omega\\[4pt] f(\omega^3) &=& a\omega^3 + b\omega^{15} = a\omega^3 + b\omega^7 &= a\omega^3 - b\omega^3 = (a - b)\omega^3\\[4pt] f(-\omega^3\equiv\omega^7) &=& a\omega^7 + b\omega^{35} = a(-\omega^3) + b(-\omega^3) &= -(a + b)\omega^3 \end{array}

Evaluar los términos usando el método anterior requiere 8 sumas y 16 multiplicaciones.

Sin embargo, usando la expansión de raíz cuadrada, solo necesitamos 2 sumas y 10 multiplicaciones. Cada vez que una raíz cuadrada se expande en sus dos soluciones, la multiplicamos por el término adyacente. Así que, siempre que la raíz cuadrada “final” se desenvuelve, el resultado son dos multiplicaciones. Estas se resaltan en rojo a continuación. Las sumas se resaltan en azul.

Ten en cuenta que “calcular la raíz cuadrada” es completamente determinista. Sabemos que siempre sigue el patrón de $\set{1}$ , raíces cuadradas de la unidad, raíces cuartas de la unidad, raíces octavas de la unidad, y así sucesivamente. Por lo tanto, no hay necesidad de calcular explícitamente las raíces cuadradas.

Términos fáciles y términos difíciles

Podemos ver que los términos $x^{k/2}$ son los más fáciles de evaluar porque solo requieren 1 evaluación, y el resto es simplemente copiar valores hacia abajo en el árbol.

Por otro lado, $x$ sin potencia es el “más difícil” de evaluar porque necesitamos hacer una expansión de raíz cuadrada en cada paso descendente en el árbol.

Lo bueno de la función $f(x)=a+bx^{k/2}$ , que se convierte en la función multivaluada $g(x)=(a+b\sqrt{x})$ en las raíces $k$ -ésimas de la unidad, es que evaluamos completamente la raíz cuadrada en el segundo nivel del árbol y simplemente copiamos la suma de $a+b$ para el resto de la evaluación.

De hecho, cualquier polinomio puede escribirse para “maximizar” la cantidad de términos $a+bx^{k/2}$ y “minimizar” la cantidad de términos $x$ .

Supongamos que tenemos un polinomio de grado 7 que queremos evaluar en las raíces octavas de la unidad.

f(x)= a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 + a_6x^6 + a_7x^7

Para maximizar el número de términos $x^4$ y tener solo un término $x$ , lo factorizamos de la siguiente manera:

f(x)= a_0 + a_2x^2 + a_4x^4 + a_6x^6 + a_1x + a_5x^5 + a_3x^3+ a_7x^7

f(x)= a_0 + a_4x^4 + (a_2x^2 + a_6x^6) + (a_1x + a_5x^5) + (a_3x^3+ a_7x^7)

f(x)= a_0 + a_4x^4 + x^2(a_2 + a_6x^4) + x(a_1 + a_5x^4) + x^3(a_3x+ a_7x^4)

f(x)= a_0 + a_4x^4 + x^2(a_2 + a_6x^4) + x((a_1 + a_5x^4) + x^2(a_3x+ a_7x^4))

Ejercicio: ¿Cómo debería factorizarse el polinomio $f(x)=a_0+a_1x+a_2x^2+a_3x^3$ evaluado en las raíces cuartas de la unidad para tener solo un término $x$ y tantos términos $x^2$ como sea posible? Recuerda, $x^{k/2}$ es $x^2$ en este caso.

En el siguiente capítulo, mostraremos cómo evaluar un polinomio general de grado 4 y grado 8 usando la expansión de raíz cuadrada, que además resulta ser exactamente el algoritmo NTT.