La multiplicación de polinomios se utiliza ampliamente en las pruebas de conocimiento cero y en la criptografía matemática. Pero el enfoque de fuerza bruta o tradicional para multiplicar polinomios se ejecuta en $\mathcal{O}(n^2)$, lo cual está bien para entradas pequeñas pero se vuelve bastante costoso a medida que aumenta el grado del polinomio. Este artículo analiza detalladamente la multiplicación de polinomios con el fin de explorar formas de hacerla más rápida.

• Comenzamos con un repaso de la aritmética de polinomios tradicional/de libro de texto
• Seguido de un estudio de las diferentes formas de representación de los polinomios
• Examinamos y comparamos la aritmética de polinomios en estas diferentes formas
• Finalmente, vemos cómo estas formas pueden potencialmente acelerar la multiplicación de polinomios - y cómo sientan las bases para un algoritmo llamado Number Theoretic Transform (NTT)

Multiplicación de Polinomios - Enfoque tradicional

Consideremos dos polinomios $p_1(x)$ y $p_2(x)$ de grado $n$ cada uno:

Multiplicar estos dos polinomios utilizando la forma simple de distribución de la multiplicación sobre la suma toma $\mathcal{O}(n^2)$. Aquí, cada término de $p_1(x)$ se multiplica con cada término de $p_2(x)$:

Por ejemplo,
sea $p_1(x) = 1 + 2x$,
y $p_2(x) = 3 + 4x$.

Entonces,

Al programarlo, esto se implementa en forma de bucles anidados.

Copy
# Let A be array representing the coefficients of p1(x)
A = [a0, a1, ..., an]
# Let B be array representing the coefficients of p2(x)
B = [b0, b1, ..., bn]
# Let C be the array storing coefficients of p1(x).p2(x)

function multiply_polynomials(A, B):
    n = len(A)
    m = len(B)
    C = array of zeros of length (n + m - 1)

    for i from 0 to n - 1:
        for j from 0 to m - 1:
            C[i + j] += A[i] * B[j]
    return C

Obtendrías el resultado así:

Por cada $n$ iteraciones del bucle exterior, el bucle interior se ejecuta n veces (asumiendo grados iguales $m=n$), dando así n por n, es decir, un tiempo de ejecución de $\mathcal{O}(n^2)$.

Ahora queremos ver si podemos optimizar esto y hacerlo mejor. O simplemente, ¿hay alguna forma de hacer que la multiplicación de polinomios sea más rápida?

Formas de representar un Polinomio

Hay dos formas en las que podemos representar un polinomio: forma de coeficientes y forma de puntos.

Forma de Coeficientes

Los polinomios generalmente se expresan en lo que se llama la base monomial, o la forma de coeficientes, lo que significa que se escriben como una combinación lineal de potencias de la variable.

Por ejemplo, un polinomio de grado $n$, cuando se expresa como

se expresa en la base monomial, ya que utiliza $[1, x, x^2, …, x^n]$ como base para sus coeficientes, que son $a_0, a_1, a_2, .., a_x.$

En esta representación, los coeficientes de $p(x)$ pueden escribirse como un vector o un arreglo, como $[a_0, a_1, …, a_n]$, donde el primer elemento corresponde al término constante o coeficiente de $x^0$, mientras que el último elemento corresponde al coeficiente de $x^n$.

Debes tener en cuenta que el método anterior de multiplicación distributiva que vimos (tiempo de ejecución $\mathcal{O}(n^2)$) se aplicó sobre la forma de coeficientes de los polinomios.

Forma de Puntos (o Valores)

La representación en forma de puntos (o valores) se basa en el hecho de que todo polinomio de grado $n$ puede representarse mediante un conjunto de $n+1$ puntos distintos que se encuentran sobre él.

Por ejemplo, consideremos un polinomio cuadrático (grado $2$):

Ahora toma cualesquiera $3$ puntos (porque $n=2$) que se encuentren en esta curva, digamos $(0,1)$, $(1,0)$ y $(2,3)$. Podemos decir que estos $3$ puntos representan el polinomio dado. Alternativamente, si solo se nos dan estos puntos, es posible recuperar el polinomio $2x^2 -3x+1$ a partir de esa información. ¿Por qué funciona esto? ¿O cómo somos capaces de representar de manera equivalente un polinomio de grado $n$ con $n+1$ puntos?

Esto es porque:

Para cada conjunto de $n+1$ puntos distintos, existe un único polinomio de menor grado, de grado a lo sumo $n$, que pasa a través de todos ellos.

Este polinomio de menor grado se llama Polinomio de Lagrange.

Por ejemplo,
dados dos puntos $(1, 2)$ y $(3, 4)$, existe un único polinomio de grado $1$ (una línea) que pasa por estos puntos:

De manera similar,
dados tres puntos $(0, 1)$, $(1, 4)$ y $(2, 9)$, el Polinomio de Lagrange de grado $2$ que pasa por estos puntos es:

Cómo se calcula este polinomio especial dado un conjunto de puntos es algo que se discute en este artículo sobre la interpolación de Lagrange.

Unicidad del Polinomio de Lagrange

Debes notar que para un conjunto de puntos, hay múltiples polinomios de un grado dado que pasan por todos ellos. Pero solo el polinomio de menor grado es único.

Por ejemplo, en el caso anterior de los puntos $(1, 2)$ y $(3, 4)$, existen muchos polinomios que pasan por estos dos puntos:
$x^2 -3x +4$ y $2x^2 -7x +7$ son dos de los muchos polinomios de grado $2$ (cuadráticos) que pasan por estos dos puntos.

De manera similar, si consideras el grado $3$, dos ejemplos de polinomios que pasan por los puntos $(1,2)$ y $(3,4)$ son $x^3 -5x^2 +8x-2$ y $-x^{3}+4x^{2}-2x+1$.

Pero para el menor grado, aquí $1$, existe solo un polinomio del menor grado, y ese es $p(x) = 1 + x$. Es único, y no hay otro polinomio de grado $1$ que pueda pasar por estos dos puntos dados.

¿Cómo se determina este menor grado?

Para cada conjunto de $n+1$ puntos distintos, hay un único polinomio de grado a lo sumo $n$ que pasa por ellos. El grado del polinomio único es menor que $n$ si algunos de los puntos son colineales o se encuentran en un polinomio de menor grado. Por lo tanto, usamos el término “a lo sumo $n$” para cubrir el caso en el que el grado es exactamente $n$, así como los casos donde el grado es menor.

Por ejemplo,
dados los puntos $(1,2),(2,4),$ y $(3,6)$, el polinomio de menor grado que pasa por ellos es $y=2x$. Esto se debe a que los puntos son colineales, es decir, se encuentran en una línea. Uno puede comprobar que la pendiente entre cualquier par de ellos es la misma:

Por lo tanto, el menor grado es $1$, y $y=2x$ es el único Polinomio de Lagrange.

De manera similar,
Dados cinco puntos, $(-2,1), (-1,0), (0,1), (1,4), (2,9)$, encontramos que todos ellos se encuentran en una parábola con la ecuación

Este es un caso donde todos los puntos dados se encuentran en un polinomio de menor grado, aquí grado $2$, y por lo tanto el Polinomio de Lagrange tiene grado $2$, que es menor que $n$ (Aquí, $n=4$).

Consulta el Apéndice al final para la demostración de la unicidad del polinomio de menor grado.

Conversión Entre Forma de Coeficientes y Forma de Puntos

Dado que la forma de coeficientes y la forma de puntos son equivalentes, podemos convertir fácilmente entre ellas como mostraremos ahora.

Interpolación (Forma de Puntos → Forma de Coeficientes)

La conversión de la forma de puntos a la forma de coeficientes, llamada interpolación, consiste en calcular el polinomio de menor grado que pasa por todos los puntos dados. Uno de los métodos más conocidos en que esto se hace es usando la Interpolación de Lagrange, que mencionamos anteriormente. Si no estás familiarizado con ella, puedes revisar este artículo.

En resumen, dado un conjunto de $(n+1)$ puntos distintos

podemos encontrar el único polinomio $p(x)$ de menor grado, de grado a lo sumo $n$, utilizando la fórmula para la interpolación de Lagrange, de tal manera que:

Debes tener en cuenta que el tiempo de ejecución de la interpolación de Lagrange es $\mathcal{O}(n^2)$.

Evaluación (Forma de Coeficientes → Forma de Puntos)

La conversión de la forma de coeficientes a la forma de puntos, llamada evaluación, consiste en evaluar el polinomio en valores de $x$ para obtener los correspondientes valores de $y$, y así un conjunto de puntos $(x_i, y_i)$, que representan el polinomio. Una forma común en que esto se puede hacer es utilizando la regla de Horner (que se discutirá en detalle en un futuro artículo).

En resumen, dados los coeficientes $[a_0, a_1, \dots, a_n]$ de un polinomio $p(x)$ y un valor $x_i$, el Método de Horner evalúa $p(x_i)$ de la siguiente manera:

Este método factoriza las potencias comunes de $x$, una a la vez hasta que se procesan todos los términos. Veamos un ejemplo para entenderlo mejor.

Dado el polinomio $p(x) = 2 + 3x + 5x^2 + x^3$ y un valor $x = 2$, revisaremos cómo la regla de Horner evalúa $p(2)$.

Podemos reescribir $p(x)$ de la siguiente manera (como se muestra en la expresión generalizada de arriba):

Sustituyendo $x = 2$:

Observa cómo los pasos involucran multiplicaciones y sumas alternas. Los pasos 1, 3 y 5 del cálculo anterior son multiplicaciones, mientras que los pasos 2, 4 y 6 son sumas. En total, hay $n$ multiplicaciones y $n$ sumas (aquí $n=3$), dando un tiempo de ejecución total de $\mathcal{O}(n)$. Así es como la regla de Horner evalúa un polinomio de grado $n$ en un valor dado de $x$ en $\mathcal{O}(n).$

Por lo tanto, evaluar el polinomio en $n+1$ valores distintos de $x$ - convirtiendo de la forma de coeficientes a la forma de puntos usando esta regla - toma $n$ por $n+1$, es decir, $\mathcal{O}(n^2)$.

Forma de Coeficientes VS Forma de Puntos

Dijimos que la forma de coeficientes y la forma de puntos de un polinomio son equivalentes, y una puede convertirse en la otra. Es decir, no hay diferencia en los resultados finales de la suma y la multiplicación cuando se hacen en cualquiera de las formas. Examinemos esto, con un ejemplo de suma primero.

Suma en forma de coeficientes

Consideremos dos polinomios dados en forma de coeficientes,

O sus respectivos arreglos de coeficientes:

Ahora, sumar los dos polinomios es simplemente sumar los dos arreglos elemento a elemento, y el arreglo de coeficientes resultante representa el polinomio final. Verifiquemos esto:

O simplemente, $[(1+4), (2+0),(3+1)] = [5,\ 2,\ 4]$

Para dos polinomios de grado $n$, realizamos $n+1$ sumas para obtener la representación de la suma. Por lo tanto, el tiempo de ejecución de la suma en forma de coeficientes es $\mathcal{O}(n)$.

Suma en forma de puntos

Consideremos los mismos dos polinomios,

Primero, necesitamos convertirlos de la forma de coeficientes a la forma de puntos. Dado que el grado de ambos polinomios es $2$, el grado de su suma será a lo sumo $2$ también. Por lo tanto, necesitamos tres puntos para representar la suma (grado más uno: $n + 1$), lo cual requiere $3$ evaluaciones para cada uno de $p_1(x)$ y $p_2(x)$.

Evaluemos $p_1(x)$ y $p_2(x)$ en $x = 0, 1, 2$ para obtener nuestros puntos.

Nota: Solo estamos eligiendo $x=0,1,2$ por simplicidad. Podrías elegir cualesquiera otros $3$ puntos para la evaluación.

• $p_1(0) = 1, \quad p_1(1)= 6, \quad p_1(2)=17$
• $p_2(0) = 4, \quad p_2(1)= 5, \quad p_2(2)=8$

Ahora, sumar los dos polinomios requiere sumar las evaluaciones correspondientes elemento por elemento, es decir:

• $p_{\text{sum}}(0) = (1+4) =5$
• $p_{\text{sum}}(1) = (6+5) =11$
• $p_{\text{sum}}(2) = (17+8) =25$

Estos tres puntos $(0, 5), (1, 11)$ y $(2, 25)$ nos dan la representación en forma de puntos de la suma. Verifiquemos si satisfacen el polinomio que calculamos anteriormente:

• $p_{\text{sum}}(0) = 5$
• $p_{\text{sum}}(1) = 5 + 2 + 4 = 11$
• $p_{\text{sum}}(2) = 5 + 4 + 16 = 25$

Por lo tanto, verás que la suma en ambas formas da el mismo resultado, o el mismo polinomio, solo representado de diferentes maneras.

En la suma en forma de puntos, para dos polinomios de grado $n$, hay $n+1$ puntos que representan a cada uno de ellos, y por lo tanto realizamos $n+1$ sumas elemento por elemento para obtener los puntos representativos de la suma. Por lo tanto, el tiempo de ejecución de la suma en forma de puntos es $\mathcal{O}(n)$.

Ahora, examinemos también de cerca la multiplicación.

Multiplicación en forma de coeficientes

Consideremos dos polinomios dados en forma de coeficientes:

O sus respectivos arreglos de coeficientes:
$p_1 = [1,\ 2]$ y $p_2 = [3,\ 4]$

Multiplicarlos utilizando la forma distributiva discutida anteriormente da:

El polinomio resultante es $p_{\text{prod}}(x) = 3 + 10x + 8x^2$, representado por el arreglo de coeficientes $[3,\ 10,\ 8]$. El método distributivo de multiplicación en forma de coeficientes toma $\mathcal{O}(n^2)$, como vimos al inicio de este artículo.

Multiplicación en forma de puntos

Ahora consideramos los mismos polinomios y los convertimos a sus formas de puntos.

Dado que ambos polinomios tienen grado $1$, su producto tendrá un grado de a lo sumo $2$, lo que significa que necesitamos $3$ puntos para representarlo, lo cual requiere 3 evaluaciones para cada uno de $p_1(x)$ y $p_2(x)$.

Entonces, evaluemos $p_1(x)$ y $p_2(x)$ en $x = 0, 1, 2$.

• $p_1(0) = 1,\quad p_1(1) = 3,\quad p_1(2) = 5$
• $p_2(0) = 3,\quad p_2(1) = 7,\quad p_2(2) = 11$

Ahora, para obtener los puntos que representan su producto, multiplicamos las evaluaciones elemento por elemento:

• $p_{\text{prod}}(0) = 1 \cdot 3 = 3$
• $p_{\text{prod}}(1) = 3 \cdot 7 = 21$
• $p_{\text{prod}}(2) = 5 \cdot 11 = 55$

Así que los tres puntos $(0, 3), (1, 21)$ y $(2, 55)$ nos dan la representación en forma de puntos del producto resultante.

Verifiquemos si satisfacen el producto de polinomios que obtuvimos anteriormente:

• $p_{\text{prod}}(0) = 3$
• $p_{\text{prod}}(1) = 3 + 10 + 8 = 21$
• $p_{\text{prod}}(2) = 3 + 20 + 32 = 55$

Por lo tanto, puedes ver que la multiplicación en ambas formas da el mismo polinomio, solo representado de diferentes maneras.

En resumen, para dos polinomios $p_1(x)$ y $p_2(x)$ de grado $n$, su producto tendrá un grado de a lo sumo $2n$, lo que significa que necesitamos $2n+1$ puntos para representarlo. Así, realizamos $2n+1$ evaluaciones para cada polinomio en valores comunes de $x$ para convertirlos a la forma de puntos:

Luego realizamos la multiplicación en forma de puntos multiplicando estos dos conjuntos elemento por elemento, lo cual toma $2n+1$ multiplicaciones, es decir, un tiempo de ejecución de $\mathcal{O}(n)$.

Esto nos da los $2n+1$ puntos que representan el producto $p_1(x).p_2(x)$:

Lo asombroso a notar aquí es que, mientras que la suma tanto en forma de coeficientes como de puntos toma el mismo tiempo $\mathcal{O}(n)$, la multiplicación en forma de puntos es significativamente más rápida que en forma de coeficientes. En la forma de puntos, realizamos $2n+1$ multiplicaciones elemento a elemento, dando un tiempo de ejecución de $\mathcal{O}(n)$, ¡lo cual es mucho mejor que el $\mathcal{O}(n^2)$ requerido para la multiplicación en forma de coeficientes!

Sin embargo, todavía hay un problema: no hemos considerado la sobrecarga de convertir a la forma de puntos y viceversa.

Entonces, veamos el proceso completo de la multiplicación en forma de puntos, que implica tres pasos:

1. Conversión de la forma de coeficientes a la forma de puntos
   Evaluamos los dos polinomios de grado $n$ que se van a multiplicar en $(2n+1)$ valores de $x$, para obtener un conjunto de $(2n+1)$ evaluaciones para cada uno. Esto toma $\mathcal{O}(n^2)$ usando el Método de Horner.
2. Multiplicación elemento a elemento en la representación de forma de puntos
   Multiplicamos estos dos conjuntos elemento a elemento para obtener $(2n+1)$ evaluaciones que nos dan la representación en forma de puntos de su producto. Esto toma $\mathcal{O}(n)$.
3. Conversión de la forma de puntos a la forma de coeficientes
   Calculamos el único polinomio de menor grado (forma de coeficientes) que pasa por todos los $(2n+1)$ puntos resultantes. Esto toma $\mathcal{O}(n^2)$ utilizando la interpolación de Lagrange.

Por lo tanto, el tiempo de ejecución general para los pasos anteriores es:

lo cual no es mejor que desde donde empezamos. Por lo tanto, necesitamos explorar si alguna optimización puede hacer este proceso más rápido.

Optimizando la conversión

El punto clave a tener en cuenta es que la multiplicación en forma de coeficientes toma $\mathcal{O}(n^2)$, mientras que la multiplicación en forma de puntos (elemento a elemento) toma $\mathcal{O}(n)$. Por lo tanto, si podemos encontrar una manera de convertir la forma de coeficientes a la forma de puntos y viceversa (pasos 1 y 3 mencionados arriba) más rápido que $\mathcal{O}(n^2)$, podemos optimizar la multiplicación para que se ejecute en tiempo subcuadrático.

Es importante notar que no podemos optimizar la suma de polinomios, porque la suma tanto en forma de coeficientes como en forma de puntos se ejecuta en $\mathcal{O}(n)$ cada una.

Así que ahora hagamos una lluvia de ideas sobre algunas formas en las que podríamos hacer la conversión de la forma de coeficientes a la de puntos más rápida.

¿Qué pasaría si conociéramos un punto cuya evaluación pudiera darnos los valores de varios puntos relacionados, ahorrándonos cálculos repetidos?

Por ejemplo, si tuviéramos un polinomio con una gráfica simétrica, evaluar un punto nos diría también la evaluación para su correspondiente punto simétrico.

Consideremos el polinomio $p(x)= x^2$.
Observa cómo,

O, más simplemente, observa cómo para todo $x_i$,

Esto no solo es cierto para $p(x)=x^2$, sino que se generaliza a todos los polinomios que contienen solo coeficientes con potencias pares, los cuales también se conocen como polinomios pares.

Por ejemplo, consideremos el polinomio par (que contiene solo términos con potencias pares de $x$):

En la gráfica anterior, es fácil observar que

Visualmente hablando, las gráficas de los polinomios pares están reflejadas respecto al eje $y$, y se evalúan al mismo $y$ tanto para valores positivos como negativos de cualquier $x$ dado.

¿Qué pasa con los polinomios impares que contienen solo coeficientes con potencias impares?
Consideremos $p(x) = x^3$.
Observa cómo

En la gráfica anterior, observa cómo, para todo $x_i$,

Nuevamente, esto no solo es cierto para $p(x)=x^3$, sino que se generaliza a todos los polinomios impares, es decir, polinomios que contienen solo términos con potencias impares de $x$. Por ejemplo, consideremos el polinomio

En la gráfica anterior, observa que

Visualmente, las gráficas de todos los polinomios impares son simétricas con respecto al origen, lo que hace que la igualdad anterior sea cierta para todos ellos.

Ahora puedes ver que después de evaluar ciertos puntos, podemos obtener la evaluación en otros puntos sin ningún cálculo extra. Por ejemplo, en los casos anteriores, para polinomios pares e impares, conocer la evaluación para $p(x)$ también nos da la evaluación para $p(-x)$.

Podemos explotar este hecho para hacer que la multiplicación de polinomios sea más rápida, que es exactamente lo que un hermoso algoritmo llamado Number Theoretic Transform (NTT) nos permite hacer. NTT permite la evaluación y la interpolación en $\mathcal{O}(n \log n)$ utilizando recursivamente las propiedades de simetría de ciertos puntos, haciendo así la conversión subcuadrática.

Pero como NTT opera sobre un campo finito, no hay valores negativos de $x$ con los que podamos trabajar. Aquí es donde los conceptos de subgrupos multiplicativos, ciclicidad y raíces de la unidad entran en juego. Estos conceptos nos permitirán explotar las simetrías presentes en los campos finitos para realizar la multiplicación de polinomios de manera más eficiente. Exploraremos cómo funciona NTT en detalle en próximos artículos.

Apéndice

Demostración de la unicidad del polinomio de menor grado

Mostramos que si hay dos polinomios $p(x)$ y $q(x)$ de igual grado que interpolan un conjunto de puntos, entonces debe existir un polinomio $r(x)$ tal que $r(x) = p(x)-q(x)$.

Luego mostraremos que la única solución posible para $r(x)$ es $r(x) = 0$, de lo contrario terminamos con un polinomio que tiene más raíces que su grado, lo cual demostramos que es imposible. Veamos estos pasos en detalle ahora.

Supongamos que el Polinomio de Lagrange de menor grado no es único. Entonces hay al menos dos polinomios distintos de menor grado que pasan por todos los $n+1$ puntos dados. Sean estos dos polinomios $p(x)$ y $q(x)$. Ahora, definamos el polinomio $r(x)$ como la diferencia entre $p(x)$ y $q(x)$.

Ahora, si mostramos que $r(x)$ es $0$ para todos los valores de $x$, entonces habremos demostrado que $p(x)$ es igual a $q(x)$, y por lo tanto el Polinomio de Lagrange es único.

Dado que el grado tanto de $p(x)$ como de $q(x)$ es a lo sumo $n$, se deduce de la simple resta algebraica que $r(x)$ también debe tener un grado a lo sumo $n$.
Además, dado que tanto $p(x)$ como $q(x)$ pasan por los mismos $n+1$ puntos, se evaluarán al mismo valor de $y$ para cada uno de los valores de $x$.

Nota: Gráficamente, cuando dos polinomios diferentes se evalúan al mismo valor de $y$ para un $x$ dado, significa que se intersecan en ese punto. Por ejemplo:

En $x=2$, ambos dan $y=4$, por lo que se intersecan en el punto $(2,4)$. En este caso, estamos tratando con polinomios diferentes. ¡Otra posibilidad de tener el mismo $y$ para un $x$ dado es que en realidad sean el mismo polinomio! En ese caso, tendrán el mismo $y$ para todos los valores de $x$, no solo para algunos valores particulares de $x$.

En el caso de $p(x)$ y $q(x)$, son iguales para al menos n + 1 valores diferentes de $x$. Esto se puede expresar matemáticamente como:

Entonces, la diferencia entre $p(x)$ y $q(x)$ en todos los $n+1$ puntos será cero. Es decir,

Por lo tanto, $r(x)$ se evalúa en cero en $n+1$ puntos, lo que implica que es un polinomio cero. Veamos más claramente por qué.

Un polinomio cero es aquel que se evalúa en cero para todos los valores de $x$. El ejemplo más simple de un polinomio cero es:

Otra forma de ver esto es, si nuestro dominio de evaluación del polinomio - el conjunto de puntos en los que se puede evaluar el polinomio - es, digamos, $S=\{x_0, x_1 \cdots, x_{n-1}\}$, entonces un polinomio cero para este dominio puede ser:

Porque,

Podríamos tener muchos más polinomios cero para el dominio $S$ como:

Nota que cada uno de $f_1(x), f_2(x)$ y $f_3(x)$ se evalúa en cero para el dominio $S$, y por lo tanto es un polinomio cero. Podemos tener muchos más. El más primitivo es $f_3(x)=0$, es decir, la propia constante cero.

Nota: Si el dominio $S$ se toma como el conjunto de todos los números reales, entonces el único polinomio cero que podemos tener es $f(x)=0$, ya que ningún otro polinomio se evaluará en cero para todos los números reales.

Ahora observa el número de raíces y el grado para cada uno de los ejemplos de polinomios cero que vimos.

Las raíces de un polinomio son los valores en el dominio para los cuales el polinomio se evalúa en cero, mientras que el grado de un polinomio es la mayor potencia de la variable, como bien sabes.

• $f_1(x):$ Raíces- $n$, Grado- $n$
• $f_2(x):$ Raíces- $n$, Grado- $2n$
• $f_3(x):$ Raíces- $n$, Grado- $0$

Todos ellos se evalúan en cero en $S$; por lo tanto, el número de raíces es $n$, mientras que el grado puede variar modificando $p(x)$, cuyo grado es $n$.

Nota también que $f_3(x)=0$ tiene un número de raíces mayor que su grado. Esto solo es posible en el caso de un polinomio cero, específicamente el primitivo $f_3(x)=0$. De lo contrario, el número de raíces siempre es menor o igual al grado.

Considera un polinomio no nulo de grado $n$; puede tener a lo sumo $n$ raíces (o intersecciones con el eje $x$). El polinomio cero primitivo es la única excepción, ya que tiene más raíces que su grado.

Por ejemplo,
una ecuación cuadrática de grado $2$, como $q(x)=x^2-3x+2$, tiene dos raíces, es decir, $x=1$ y $x=2$.

Para que una ecuación cuadrática tenga más de dos raíces, debe ser igual a cero, es decir, $q(x)=0$.

Ahora, volviendo a nuestro argumento: dado que $r(x)$ se evalúa en cero en $n+1$ puntos, debe tener al menos $n+1$ raíces, lo cual es mayor que su grado $n$. Por lo tanto $r(x)$ debe ser igual a cero.

Esto implica que $p(x)=q(x)$, lo que significa que son el mismo polinomio. Por lo tanto, el polinomio de menor grado que interpola un conjunto de $n+1$ puntos distintos es único.