Recentemente, participei de um workshop sobre pseudo-aleatoriedade no Instituto de Matemática de Chennai sobre pseudo-aleatoriedade. Venkat Guruswami fez a seguinte declaração bonita durante sua palestra (sobre a teoria da codificação):
É notável o quanto se pode provar usando o simples fato de que um grau polinomial sobre um campo pode ter no máximo d raízes.
Acredito que isso também seja chamado de Método Stepanov (nessas aplicações, normalmente as raízes também ocorrem com grande multiplicidade). Um lugar em que eu já vi isso é em um artigo sobre limites de raiz quadrada para o menor não resíduo de Michael Forbes, Neeraj Kayal, Rajat Mittal e Chandan Saha.
Esse princípio foi destacado no workshop com a decodificação exclusiva e listada do código Reed-Solomon ( que pode ser encontrado neste curso , por exemplo) na palestra de Venkat. Na palestra de Neeraj Kayal, ele deu outros dois exemplos - as provas da Conjectura de Campo Finito de Kakeya e a Conjectura de Articulações (as quais podem ser encontradas nesta pesquisa muito agradável de Zeev Dvir). Outros exemplos em que consigo pensar são a prova de Dana Moshkovitz do Lema de Schwartz-Zippel , e outro dos meus favoritos é o teste AKS Primality, que (se me permitem fazer um alongamento), usa apenas esse fato essencialmente.
Fiquei me perguntando se existem outros exemplos de resultados elegantes usando (essencialmente) apenas esse fato simples.
Este post está intimamente relacionado à pergunta anterior " Métodos polinomiais para resultados de complexidade ", mas foi para um 'método polinomial' mais geral.
fonte
Respostas:
Isso pode ser óbvio demais, mas a prova de correção do algoritmo aleatório de Schwartz-Zippel para teste de identidade polinomial usa essencialmente exatamente esse fato, além de indução.
fonte