El lema es básicamente una de las generalizaciones * del hecho de que un polinomio univariado de grado d tiene como máximo d ceros a polinomios multivariados.
Sea [math] F [/ math] un campo finito de tamaño [math] q [/ math], sea [math] n \ geq 1 [/ math], y sea [math] P \ in F [x_1, \ ldots, x_n] [/ math] será un polinomio de grado como máximo [math] d <q [/ math]. Si [matemática] P [/ matemática] no es cero, entonces el número de ceros de [matemática] P [/ matemática] en [matemática] F ^ n [/ matemática] es como máximo [matemática] dq ^ {n-1 }[/mates]. (O deje que [math] S [/ math] sea un subconjunto finito de un campo arbitrario [math] F [/ math], entonces P tiene como máximo [math] d | S | ^ {n-1} [/ math] ceros en [matemática] S ^ n \ subconjunto F ^ n [/ matemática].)
Entonces, por ejemplo, el polinomio [matemático] xy + x ^ 2 [/ matemático] tiene cinco ceros (0, 0), (0, 1), (0, 2), (1, 2) y (2, 2) sobre el campo [math] \ mathbb {F} _3 [/ math], que es solo uno menos que el límite [math] 2 \ cdot3 [/ math]. El primer uso de este resultado (se llama lema por alguna razón) fue en pruebas de identidad polinomiales, y luego encontró aplicación en muchos otros algoritmos informáticos. También calcula la distancia mínima de Hamming de los códigos Reed-Muller en ciertos casos (aunque esta distancia mínima ya se conocía en los años 60).
- ¿Dónde y cómo se superponen la programación y las matemáticas?
- ¿Existe alguna analogía en la vida real con el concepto de expresiones regulares?
- ¿Cuál es la prueba de primitiva determinista más rápida?
- ¿Puedo convertirme en un buen científico de datos con programación pero no con habilidades matemáticas?
- ¿Qué significa el símbolo # en esta pregunta matemática?
Más recientemente, este lema se utilizó en la solución de la conjetura de Kakeya de campo finito por Zeev Dvir, donde también dio una nueva prueba del lema. La idea básica es que si un conjunto de Kakeya dado es más pequeño que un límite particular, entonces existe un polinomio distinto de cero de un pequeño grado que desaparece en el conjunto (por interpolación), que luego se demuestra que es cero en todos los puntos, por lo tanto dándonos una contradicción (por el lema de Schwartz-Zippel), y el límite inferior requerido en el conjunto de Kakeya.
Lecturas adicionales: La curiosa historia del lema de Schwartz-Zippel, sobre ceros de un polinomio en una cuadrícula finita, el método polinomial de Terence Tao, una prueba alternativa del lema de Schwartz-Zippel, dos pruebas del lema de Schwartz-Zippel
* Hay muchas otras generalizaciones como nullstellensatz combinatorio, el teorema de Chevalley-Advertencia y el límite de Lang-Weil.
