Lema de Schwartz-Zippel

Herramienta utilizada en pruebas de identidad polinomial probabilística

En matemáticas, el lema de Schwartz-Zippel (también llamado lema de DeMillo-Lipton-Schwartz-Zippel ) es una herramienta que se utiliza habitualmente en las pruebas de identidad polinómica probabilísticas . La prueba de identidad es el problema de determinar si un polinomio multivariado dado es el polinomio 0, el polinomio que ignora todas sus variables y siempre devuelve cero. El lema establece que es probable que al evaluar un polinomio distinto de cero sobre entradas elegidas aleatoriamente de un conjunto lo suficientemente grande se encuentre una entrada que produzca una salida distinta de cero.

Fue descubierto independientemente por Jack Schwartz , ^[1] Richard Zippel, ^[2] y Richard DeMillo y Richard J. Lipton , aunque la versión de DeMillo y Lipton se mostró un año antes del resultado de Schwartz y Zippel. ^[3] La versión de campo finito de este límite fue demostrada por Øystein Ore en 1922. ^[4]

Enunciado y demostración del lema

Teorema 1 (Schwartz, Zippel). Sea

${\displaystyle P\in R[x_{1},x_{2},\ldots ,x_{n}]}$

sea ​​un polinomio distinto de cero de grado total d  ≥ 0 sobre un dominio integral  R. Sea S un subconjunto finito de R y sean r ₁ ,  r ₂ , ...,  r _n seleccionados al azar de forma independiente y uniforme de S. Entonces

${\displaystyle \Pr[P(r_{1},r_{2},\ldots ,r_{n})=0]\leq {\frac {d}{|S|}}.}$

De manera equivalente, el Lema establece que para cualquier subconjunto finito S de R, si Z(P) es el conjunto cero de P, entonces

${\displaystyle |Z(P)\cap S^{n}|\leq d\cdot |S|^{n-1}.}$

Demostración. La demostración se realiza por inducción matemática sobre n . Para n  = 1 , P puede tener como máximo d raíces según el teorema fundamental del álgebra . Esto nos da el caso base. Ahora, supongamos que el teorema se cumple para todos los polinomios en n  − 1 variables. Podemos entonces considerar que P es un polinomio en x ₁ escribiéndolo como

${\displaystyle P(x_{1},\dots ,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\dots ,x_{n}).}$

Como P no es idénticamente 0, existe algún i tal que no es idénticamente 0. Tómese el mayor tal que i . Entonces , ya que el grado de es como máximo d. ${\displaystyle P_{i}}$ ${\displaystyle \deg P_{i}\leq d-i}$ ${\displaystyle x_{1}^{i}P_{i}}$

Ahora elegimos aleatoriamente de S. Por la hipótesis de inducción, ${\displaystyle r_{2},\dots ,r_{n}}$ ${\displaystyle \Pr[P_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {d-i}{|S|}}.}$

Si , entonces es de grado i (y por lo tanto no idénticamente cero) por lo que ${\displaystyle P_{i}(r_{2},\ldots ,r_{n})\neq 0}$ ${\displaystyle P(x_{1},r_{2},\ldots ,r_{n})}$

${\displaystyle \Pr[P(r_{1},r_{2},\ldots ,r_{n})=0|P_{i}(r_{2},\ldots ,r_{n})\neq 0]\leq {\frac {i}{|S|}}.}$

Si denotamos el evento por A , el evento por B y el complemento de B por , tenemos ${\displaystyle P(r_{1},r_{2},\ldots ,r_{n})=0}$ ${\displaystyle P_{i}(r_{2},\ldots ,r_{n})=0}$ ${\displaystyle B^{c}}$

${\displaystyle {\begin{aligned}\Pr[A]&=\Pr[A\cap B]+\Pr[A\cap B^{c}]\\&=\Pr[B]\Pr[A|B]+\Pr[B^{c}]\Pr[A|B^{c}]\\&\leq \Pr[B]+\Pr[A|B^{c}]\\&\leq {\frac {d-i}{|S|}}+{\frac {i}{|S|}}={\frac {d}{|S|}}\end{aligned}}}$

Aplicaciones

La importancia del teorema de Schwartz-Zippel y la prueba de identidades polinomiales se desprende de los algoritmos que se obtienen para problemas que pueden reducirse al problema de la prueba de identidad polinomial .

Pruebas cero

Por ejemplo, es

${\displaystyle (x_{1}+3x_{2}-x_{3})(3x_{1}+x_{4}-1)\cdots (x_{7}-x_{2})\equiv 0\ ?}$

Para resolverlo, podemos multiplicarlo y comprobar que todos los coeficientes son 0. Sin embargo, esto lleva tiempo exponencial . En general, un polinomio se puede representar algebraicamente mediante una fórmula aritmética o un circuito .

Comparación de dos polinomios

Dado un par de polinomios y , es ${\displaystyle p_{1}(x)}$ ${\displaystyle p_{2}(x)}$

${\displaystyle p_{1}(x)\equiv p_{2}(x)}$?

Este problema se puede resolver reduciéndolo al problema de la prueba de identidad polinómica. Es equivalente a comprobar si

${\displaystyle [p_{1}(x)-p_{2}(x)]\equiv 0.}$

Por lo tanto, si podemos determinar que

${\displaystyle p(x)\equiv 0,}$

dónde

${\displaystyle p(x)=p_{1}(x)\;-\;p_{2}(x),}$

Entonces podemos determinar si los dos polinomios son equivalentes.

La comparación de polinomios tiene aplicaciones para programas de ramificación (también llamados diagramas de decisión binaria ). Un programa de ramificación de lectura única se puede representar mediante un polinomio multilineal que calcula (sobre cualquier campo) en entradas {0,1} la misma función booleana que el programa de ramificación, y dos programas de ramificación calculan la misma función si y solo si los polinomios correspondientes son iguales. Por lo tanto, la identidad de las funciones booleanas calculadas por programas de ramificación de lectura única se puede reducir a la prueba de identidad polinómica.

La comparación de dos polinomios (y por lo tanto la prueba de identidades polinomiales) también tiene aplicaciones en la compresión 2D, donde el problema de encontrar la igualdad de dos textos 2D A y B se reduce al problema de comparar la igualdad de dos polinomios y . ${\displaystyle p_{A}(x,y)}$ ${\displaystyle p_{B}(x,y)}$

Prueba de primalidad

Dado , ¿es un número primo ? ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n}$

Un algoritmo aleatorio simple desarrollado por Manindra Agrawal y Somenath Biswas puede determinar probabilísticamente si es primo y utiliza pruebas de identidad polinomial para hacerlo. ${\displaystyle n}$

Proponen que todos los números primos n (y sólo los números primos) satisfacen la siguiente identidad polinomial:

${\displaystyle (1+z)^{n}=1+z^{n}({\mbox{mod}}\;n).}$

Esto es una consecuencia del endomorfismo de Frobenius .

Dejar

${\displaystyle {\mathcal {P}}_{n}(z)=(1+z)^{n}-1-z^{n}.}$

Entonces, si y solo si n es primo . La prueba se puede encontrar en [4]. Sin embargo, dado que este polinomio tiene grado , donde puede ser primo o no, el método de Schwartz-Zippel no funcionaría. Agrawal y Biswas utilizan una técnica más sofisticada, que divide por un polinomio mónico aleatorio de grado pequeño. ${\displaystyle {\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {P}}_{n}}$

Los números primos se utilizan en diversas aplicaciones, como el dimensionamiento de tablas hash, los generadores de números pseudoaleatorios y la generación de claves para criptografía . Por lo tanto, encontrar números primos muy grandes (del orden de (al menos) ) se vuelve muy importante y se requieren algoritmos de prueba de primalidad eficientes. ${\displaystyle 10^{350}\approx 2^{1024}}$

Combinación perfecta

Sea un grafo de n vértices donde n es par. ¿ G contiene una correspondencia perfecta ? ${\displaystyle G=(V,E)}$

Teorema 2 (Tutte 1947): Un determinante matricial de Tutte no es un polinomio 0 si y sólo si existe una correspondencia perfecta.

Un subconjunto D de E se denomina coincidente si cada vértice de V incide con, como máximo, una arista de D. Un emparejamiento es perfecto si cada vértice de V tiene exactamente una arista que le incide en D. Cree una matriz de Tutte A de la siguiente manera:

${\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1{\mathit {n}}}\\a_{21}&a_{22}&\cdots &a_{2{\mathit {n}}}\\\vdots &\vdots &\ddots &\vdots \\a_{{\mathit {n}}1}&a_{{\mathit {n}}2}&\ldots &a_{\mathit {nn}}\end{bmatrix}}}$

dónde

${\displaystyle a_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i>j\\0\;\;\;\;{\mbox{otherwise}}.\end{cases}}}$

El determinante de la matriz de Tutte (en las variables x _ij , ⁠ ⁠ ${\displaystyle i<j}$ ) se define entonces como el determinante de esta matriz antisimétrica que coincide con el cuadrado del pfaffiano de la matriz A y es distinto de cero (como polinomio) si y solo si existe una correspondencia perfecta. Se puede entonces utilizar la prueba de identidad polinómica para encontrar si G contiene una correspondencia perfecta. Existe un algoritmo de caja negra determinista para grafos con permanentes acotados polinómicamente (Grigoriev & Karpinski 1987). ^[5]

En el caso especial de un gráfico bipartito balanceado en vértices, esta matriz toma la forma de una matriz de bloques. ${\displaystyle n=m+m}$

${\displaystyle A={\begin{pmatrix}0&X\\-X^{t}&0\end{pmatrix}}}$

si las primeras m filas (o columnas) están indexadas con el primer subconjunto de la bipartición y las últimas m filas con el subconjunto complementario. En este caso, el pfaffiano coincide con el determinante habitual de la matriz m × m X (hasta el signo). Aquí X es la matriz de Edmonds .

Determinante de una matriz con entradas polinómicas

Dejar

${\displaystyle p(x_{1},x_{2},\ldots ,x_{n})}$

sea ​​el determinante de la matriz polinómica .

Actualmente, no se conoce ningún algoritmo de tiempo subexponencial que pueda resolver este problema de manera determinista. Sin embargo, existen algoritmos polinómicos aleatorios cuyo análisis requiere un límite en la probabilidad de que un polinomio distinto de cero tenga raíces en puntos de prueba seleccionados aleatoriamente.

Notas

1. Schwartz 1980.
2. Zipper 1979.
3. DeMillo y Lipton 1978.
4. O. Ore, Über höhere Kongruenzen. Estera norsk. Forenings Skrifter Ser. Yo (1922), núm. 7, 15 páginas.
5. Grigoriev y Karpinski 1987.

Referencias

• Agrawal, Manindra; Biswas, Somenath (21 de febrero de 2003). "Primalidad y prueba de identidad mediante el resto chino". Revista de la ACM . 50 (4): 429–443. doi :10.1145/792538.792540. S2CID  13145079 . Consultado el 15 de junio de 2008 .
• Berman, Piotr; Karpinski, Marek ; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech (2002). "Sobre la complejidad de la correspondencia de patrones para textos bidimensionales altamente comprimidos" (ps) . Journal of Computer and System Sciences . 65 (2): 332–350. doi : 10.1006/jcss.2002.1852 . Consultado el 15 de junio de 2008 .
• Grigoriev, Dima; Karpinski, Marek (1987). "El problema de emparejamiento para grafos bipartitos con permanentes acotados polinomialmente está en NC". Actas del 28.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS 1987), Los Ángeles, California, EE. UU., 27-29 de octubre de 1987. IEEE Computer Society. págs. 166–172. doi :10.1109/SFCS.1987.56. ISBN . 978-0-8186-0807-0.S2CID14476361  .​
• Moshkovitz, Dana (2010). Una demostración alternativa del lema de Schwartz-Zippel. ECCC  TR10-096
• DeMillo, Richard A. ; Lipton, Richard J. (1978). "Una observación probabilística sobre la prueba de programas algebraicos". Information Processing Letters . 7 (4): 193–195. doi :10.1016/0020-0190(78)90067-4.
• Rudich, Steven (2004). AMS (ed.). Teoría de la complejidad computacional . IAS/Park City Mathematics Series. Vol. 10. ISBN 978-0-8218-2872-4.
• Schwartz, Jacob T. (octubre de 1980). "Algoritmos probabilísticos rápidos para la verificación de identidades polinomiales" (PDF) . Journal of the ACM . 27 (4): 701–717. CiteSeerX  10.1.1.391.1254 . doi :10.1145/322217.322225. S2CID  8314102. Consultado el 15 de junio de 2008 .
• Tutte, WT (abril de 1947). "La factorización de grafos lineales". J. London Math. Soc . 22 (2): 107–111. doi :10.1112/jlms/s1-22.2.107. hdl :10338.dmlcz/128215.
• Zippel, Richard (1979). "Algoritmos probabilísticos para polinomios dispersos". En Ng, Edward W. (ed.). Computación simbólica y algebraica, EUROSAM '79, Simposio internacional sobre computación simbólica y algebraica, Marsella, Francia, junio de 1979, Actas . Apuntes de clase en informática. Vol. 72. Springer. págs. 216–226. doi :10.1007/3-540-09519-5_73. ISBN 978-3-540-09519-4.
• Zippel, Richard (febrero de 1989). "Una separación explícita del tiempo polinomial aleatorio relativizado y del tiempo polinomial determinista relativizado" (ps) . Consultado el 15 de junio de 2008 .
• Zippel, Richard (1993). Springer (ed.). Cálculo polinomial efectivo. Serie internacional Springer en ingeniería y ciencias de la computación. Vol. 241. ISBN 978-0-7923-9375-7.

Enlaces externos

• La curiosa historia del lema de Schwartz-Zippel, por Richard J. Lipton