Lema de Schwartz-Zippel

Herramienta utilizada en pruebas probabilísticas de identidad polinomial.

En matemáticas, el lema de Schwartz-Zippel (también llamado lema de DeMillo-Lipton-Schwartz-Zippel ) es una herramienta comúnmente utilizada en las pruebas probabilísticas de identidad polinomial . 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 al evaluar un polinomio distinto de cero en entradas elegidas al azar de un conjunto suficientemente grande es probable que se encuentre una entrada que produzca una salida distinta de cero.

fue descubierto de forma independiente 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 probada por Øystein Ore en 1922. ^[4]

Declaración y prueba del lema.

Teorema 1 (Schwartz, Zippel). Dejar

${\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 deje que r ₁ ,  r ₂ , ...,  r _n se seleccionen 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}.}$

Prueba. La prueba es por inducción matemática en n . Para n  = 1 , como se mencionó anteriormente, P puede tener como máximo d raíces. Esto nos da el caso base. Ahora, supongamos que el teorema se cumple para todos los polinomios en n  − 1 variables. Entonces podemos 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}).}$

Dado que P no es idénticamente 0, hay alguna i tal que no es idénticamente 0. Tome la i más grande . Entonces , dado 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 es idénticamente cero), entonces ${\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 polinómicas se deriva de los algoritmos que se obtienen para problemas que pueden reducirse al problema de la prueba de identidad polinómica .

Prueba cero

Por ejemplo, es

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

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

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 puede resolverse reduciéndolo al problema de la prueba de identidad polinómica. Equivale 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 binarios ). Un programa de ramificación de una sola lectura 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 sólo si el los polinomios correspondientes son iguales. Por lo tanto, la identidad de funciones booleanas calculadas por programas de ramificación de una sola lectura se puede reducir a pruebas de identidad polinómica.

La comparación de dos polinomios (y por lo tanto la prueba de identidades polinómicas) también tiene aplicaciones en 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)}$

Pruebas 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 polinómica para hacerlo. ${\displaystyle n}$

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

${\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 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 pequeño grado. ${\displaystyle {\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {P}}_{n}}$

Los números primos se utilizan en una serie de aplicaciones, como el tamaño de tablas hash, generadores de números pseudoaleatorios y en 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 una gráfica de n vértices donde n es par. ¿ G contiene una combinación perfecta ? ${\displaystyle G=(V,E)}$

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

Un subconjunto D de E se llama coincidencia si cada vértice en V incide como máximo con una arista en D. Una coincidencia es perfecta si cada vértice en V tiene exactamente una arista incidente en D. Cree una matriz 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 , ) se define entonces como el determinante de esta matriz asimétrica que coincide con el cuadrado del pfaffiano de la matriz A y es distinto de cero (como polinomio) si y sólo si a existe una combinación perfecta. Luego se pueden utilizar pruebas de identidad polinomial para encontrar si G contiene una coincidencia perfecta. Existe un algoritmo determinista de caja negra para gráficos con permanentes acotados polinomialmente (Grigoriev y Karpinski 1987). ^[5] ${\displaystyle i<j}$

En el caso especial de un gráfico bipartito equilibrado 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 (respectivamente 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 X m × m (hasta el signo). Aquí X es la matriz de Edmonds .

Determinante de una matriz con entradas polinomiales

Dejar

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

ser el determinante de la matriz polinómica .

Actualmente, no se conoce ningún algoritmo de tiempo subexponencial que pueda resolver este problema de forma determinista. Sin embargo, existen algoritmos polinomiales 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 al azar.

Notas

1. Schwartz 1980.
2. Zippel 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). "Pruebas de identidad y primalidad a través del 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 coincidencia de patrones para textos bidimensionales altamente comprimidos" (ps) . Revista de Ciencias de la Computación y de Sistemas . 65 (2): 332–350. doi : 10.1006/jcss.2002.1852 . Consultado el 15 de junio de 2008 .
• Grigóriev, Dima; Karpinski, Marek (1987). "El problema de coincidencia para gráficos bipartitos con permanentes acotados polinomialmente está en NC". Actas del 28º Simposio anual sobre fundamentos de la informática (FOCS 1987), Los Ángeles, California, EE. UU., 27 al 29 de octubre de 1987 . Sociedad de Computación IEEE. págs. 166-172. doi :10.1109/SFCS.1987.56. ISBN 978-0-8186-0807-0. S2CID  14476361.
• Moshkovitz, Dana (2010). Una prueba alternativa del lema de Schwartz-Zippel. ECCC  TR10-096
• DeMillo, Richard A .; Lipton, Richard J. (1978). "Una observación probabilística sobre las pruebas de programas algebraicos". Cartas de procesamiento de información . 7 (4): 193-195. doi :10.1016/0020-0190(78)90067-4.
• Rudich, Steven (2004). AMS (ed.). Teoría de la complejidad computacional . Serie de Matemáticas IAS/Park City. 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 polinómicas" (PDF) . Revista de la 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 gráficas lineales". J. Matemáticas de Londres. 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 conferencias sobre informática. vol. 72. Saltador. 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 el tiempo polinomial determinista relativizado" (ps) . Consultado el 15 de junio de 2008 .
• Zippel, Richard (1993). Springer (ed.). Cálculo polinómico efectivo. La Serie Internacional Springer en Ingeniería e Informática. vol. 241.ISBN​ 978-0-7923-9375-7.

enlaces externos

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