Hace poco asistí a un taller sobre pseudoaleatoriedad en el Instituto de Matemática de Chennai sobre pseudoaleatoriedad. Venkat Guruswami hizo la siguiente declaración hermosa de pasada durante su charla (sobre la teoría de la codificación):
Es notable cuánto se puede probar utilizando el simple hecho de que un polinomio de grado sobre un campo puede tener como máximo d raíces.
Creo que a esto también se le llama Método Stepanov (en esas aplicaciones, típicamente las raíces ocurren con gran multiplicidad también). Michael Forbes, Neeraj Kayal, Rajat Mittal y Chandan Saha han escrito un lugar en el que he visto esto en un artículo sobre límites de raíz cuadrada para el no residuo más pequeño .
Este director se destacó en el taller con la decodificación única y de lista del código Reed-Solomon ( que se puede encontrar en este curso , por ejemplo) en la charla de Venkat. En la charla de Neeraj Kayal, dio otros dos ejemplos: las pruebas de la Conjetura de Kakeya de campo finito y la Conjetura de las articulaciones (ambas se pueden encontrar en esta muy buena encuesta realizada por Zeev Dvir). Otros ejemplos en los que puedo pensar es la prueba de Dana Moshkovitz del Lema de Schwartz-Zippel , y otro de mis favoritos es la prueba AKS Primality que (si se me permite hacer un estiramiento) usa solo este hecho esencialmente.
Me preguntaba si hay otros ejemplos de resultados elegantes usando (esencialmente) solo este simple hecho.
Esta publicación está estrechamente relacionada con la pregunta anterior " Métodos polinómicos para resultados de complejidad ", pero eso fue para un "método polinomial" más general.
fuente
Respuestas:
Esto puede ser demasiado obvio, pero la prueba de corrección del algoritmo aleatorio de Schwartz-Zippel para la prueba de identidad polinómica utiliza esencialmente este hecho, más la inducción.
fuente