Ideología de conjuntos cuestores : Kakeya sets, Nullstellensatz combinatorio y generalizaciones a sucesiones secantes

Abstract

RESUMEN: Algunos de los primeros ejemplos de algoritmos probabilistas fueron los de Solovay-Strassen y Miller-Rabin para el problema de primalidad. Poco después, aparecieron algoritmos probabilistas para testar la nulidad de polinomios dados en evaluación. Dos fueron las ideologías para hacer frente a este problema: los tests de Schwartz-Zippel y los Conjuntos Cuestores (J. Heintz y C.-P. Schnorr). El objetivo de este trabajo es generalizar y comprender mejor la noción de Conjunto Cuestor. Para ello, necesitamos primero una Desigualdad de Bézout para conjuntos constructibles (Capítulo 1). Después, generalizamos la definición de Conjunto Cuestor y vemos que los conjuntos de Kakeya sobre cuerpos finitos y el Nullstellensatz Combinatorio son casos particulares de esta definición (Capítulo 2). Finalmente, generalizamos el resultado principal de J. Heintz y C.-P. Schnorr, estudiando una forma de testar si una lista de polinomios es sucesión secante (Capítulo 3).

ABSTRACT: Some of the first examples of probabilistic algorithms were those of Solovay-Strassen and Miller-Rabin for testing primality. Soon afterwards, probabilistic algorithms appeared for testing nulity of polynomials given by evaluation. Two were the ideologies for facing this problem: Schwartz-Zippel tests and Correct Tests Sequences (J. Heintz, C.-P. Schnorr). The aim of this project is to generalize and better comprehend this notion of Correct Test Sequence. In order to do that, we first need a Bézout's Inequality for constructible sets (Chapter 1). Then, we generalize the definition of Correct Test Sequence and show that Kakeya sets over finite fields and the Combinatorial Nullstellensatz are particular cases of this definition (Chapter 2). Finally, we generalize the main result of J. Heintz and C.-P. Schnorr, studying a way to test whether a list of polynomials forms a secant sequence (Chapter 3).