El teorema de Sylvester-Gallai es un resultado geométrico que establece que cada conjunto finito de puntos en el plano tiene una línea recta que pasa por exactamente por dos de ellos o por todos. Recibe su nombre de James Joseph Sylvester, quien lo planteó como problema en 1893, y de Tibor Gallai, quien publicó una de las primeras demostraciones de este teorema en 1944.

Una línea recta que contiene exactamente dos puntos de un conjunto se conoce como línea ordinaria. Otra forma de expresar el teorema es que todo conjunto finito de puntos no colineales tiene una línea recta ordinaria. Según un reforzamiento del teorema, todo conjunto finito de puntos (no todos en una línea recta) tiene al menos un número lineal de líneas rectas ordinarias. Un algoritmo puede encontrar una línea recta ordinaria en un conjunto de puntos en el tiempo .

Historia El teorema de Sylvester-Gallai fue planteado como un problema por . sugiere que Sylvester pudo haber estado motivado por un fenómeno relacionado en geometría algebraica, en el que los puntos de inflexión de una curva cúbica plana en el plano proyectivo complejo forman una configuración de nueve puntos y doce líneas rectas (la configuración de Hesse), en el que cada línea recta determinada por dos de los puntos contiene un tercer punto. El teorema de Sylvester-Gallai implica que es imposible que estos nueve puntos tengan coordenadas reales.

afirmó tener una demostración breve del teorema de Sylvester-Gallai, pero ya se había señalado que estaba incompleta en el momento de su publicación. demostró el teorema (y, de hecho, un resultado ligeramente más sólido) en una formulación equivalente, su proyectivo dual. Desconociendo la demostración de Melchior, volvió a formular la conjetura, que fue demostrada posteriormente por Tibor Gallai y, poco después, por otros autores.; .

En una revisión de 1951, Erdős denominó el resultado como "teorema de Gallai",MR 0041447 pero ya se le denominaba teorema de Sylvester-Gallai en una revisión de Leonard Blumenthal de 1954.MR 0056941 Es uno de los muchos resultados que han recibido el nombre del matemático James Joseph Sylvester.

Versiones equivalentes La cuestión de la existencia de una recta ordinaria también puede plantearse para puntos en el plano proyectivo real RP2 en lugar del plano euclídeo. El plano proyectivo puede formarse a partir del plano euclídeo añadiéndole puntos adicionales "en el infinito" donde se intersecan rectas paralelas en el plano euclídeo, y añadiendo una única recta "en el infinito" que contenga todos los puntos añadidos. Sin embargo, los puntos adicionales del plano proyectivo no pueden contribuir a la creación de conjuntos de puntos finitos no euclídeos sin una recta ordinaria, ya que cualquier conjunto de puntos finitos en el plano proyectivo puede transformarse en un conjunto de puntos euclídeo con el mismo patrón combinatorio de incidencias punto-recta. Por lo tanto, cualquier patrón de un número finito de puntos y rectas que se intersecan en uno de estos dos tipos de plano también existe en el otro. Sin embargo, el punto de vista proyectivo permite describir ciertas configuraciones con mayor facilidad. En particular, permite el uso de la dualidad, en el que los roles de puntos y rectas en enunciados de geometría proyectiva pueden intercambiarse. Bajo la dualidad proyectiva, la existencia de una recta ordinaria para un conjunto de puntos no colineales en RP2 es equivalente a la existencia de un "punto ordinario" en una disposición no trivial de un número finito de rectas. Se dice que una disposición es trivial cuando todas sus rectas pasan por un punto común, y no trivial en caso contrario. Un punto ordinario es un punto que pertenece exactamente a dos rectas.

Las disposiciones de rectas tienen una estructura combinatoria estrechamente relacionada con los zonoedros, poliedros formados como la suma de Minkowski de un conjunto finito de segmentos, llamados generadores. En este sentido, cada par de caras opuestas de un zonoedro corresponde a un punto de intersección de una disposición de rectas en el plano proyectivo, con una recta por cada generador. El número de lados de cada cara es el doble del número de rectas que se cruzan en la disposición. Por ejemplo, el dodecaedro elongado mostrado es un zonoedro con cinco generadores, dos pares de caras hexagonales opuestas y cuatro pares de caras opuestas con forma de paralelogramos.

En la disposición de cinco rectas correspondiente, dos ternas de rectas se cruzan (correspondientes a los dos pares de hexágonos opuestos) y los cuatro pares de rectas restantes se cruzan en puntos ordinarios (correspondientes a los cuatro pares de paralelogramos opuestos). Un enunciado equivalente del teorema de Sylvester-Gallai, en términos de zonoedros, es que todo zonoedro tiene al menos una cara con forma de paralelogramo (contando rectángulos, rombos y cuadrados como casos especiales de paralelogramos). Más firmemente, siempre que se pueda garantizar que los conjuntos de puntos en el plano tengan al menos líneas rectas ordinarias, se puede garantizar que los zonoedros con generadores tengan al menos caras con forma de paralelogramo.

Demostraciones El teorema de Sylvester-Gallai se ha demostrado de muchas maneras diferentes. La demostración de Gallai de 1944 alterna entre la geometría euclídea y la proyectiva para transformar los puntos en una configuración equivalente en la que una línea recta ordinaria se puede encontrar como una recta de pendiente más cercana a cero. Para más detalles, véase . La demostración de Melchior de 1941 utiliza la dualidad proyectiva para convertir el problema en una pregunta equivalente sobre disposición de rectas, que pueden resolverse mediante la característica de Euler. Otro resultado debido a Leroy Milton Kelly demuestra por contradicción que la recta de conexión con la menor distancia distinta de cero a otro punto debe ser ordinaria. Y, siguiendo una demostración anterior de Steinberg, H. S. M. Coxeter demostró que los conceptos métricos de pendiente y distancia que aparecen en las demostraciones de Gallai y Kelly son innecesariamente potentes, demostrando en su lugar el teorema utilizando únicamente los axiomas de geometría ordenada.

Demostración de Kelly

Esta demostración fue ideada por Leroy Milton Kelly. la considera "simplemente la mejor" de las muchas demostraciones de este teorema.

Supóngase que un conjunto finito de puntos no es colineal. Entonces, se define una recta de conexión como una recta que contiene al menos dos puntos en el conjunto. Por finitud, debe tener un punto y una recta de conexión separados por una distancia positiva, de modo que ningún otro par punto-recta tenga una distancia positiva menor. Kelly demostró que es ordinaria, por contradicción.

Supóngase que no es ordinaria. Entonces, pasa por al menos tres puntos de . Al menos dos de ellos están en el mismo lado de , la proyección perpendicular de sobre . Llámense y , siendo el más cercano a (y posiblemente coincidiendo con él). Dibujar ahora la línea recta de conexión que pase por y , y la perpendicular de a sobre . Entonces, es más corta que . Esto se deduce del hecho de que y son semejantes, una contenida dentro de la otra.

Sin embargo, esto contradice la definición original de y de como el par punto-línea recta con la menor distancia positiva. Por lo tanto, la suposición de que no es ordinaria no puede ser cierta, como se quría demostrar.

Demostración de Melchior En 1941 (es decir, antes de que Erdős publicara la pregunta y la posterior demostración de Gallai), Melchior demostró que cualquier disposición finita no trivial de rectas en el plano proyectivo tiene al menos tres puntos ordinarios. Por dualidad, este resultado también indica que cualquier conjunto finito no trivial de puntos en el plano tiene al menos tres rectas ordinarias.

Melchior observó que, para cualquier grafo embebido en el plano proyectivo real, la fórmula debe ser igual a , la característica de Euler del plano proyectivo. Aquí, , y son el número de vértices, aristas y caras del grafo, respectivamente. Cualquier disposición no trivial de rectas en el plano proyectivo define un grafo en el que cada cara está limitada por al menos tres aristas, y cada arista limita dos caras; por lo tanto, el doble conteo produce la desigualdad adicional . Utilizar esta desigualdad para eliminar de la característica de Euler conduce a la desigualdad . Pero si cada vértice de la disposición fuera el punto de intersección de tres o más rectas, entonces el número total de aristas sería al menos , lo que contradice esta desigualdad. Por lo tanto, algunos vértices deben ser el punto de intersección de solo dos rectas, y como muestra el análisis más minucioso de Melchior, se necesitan al menos tres vértices ordinarios para satisfacer la desigualdad .

Como señala , el mismo argumento para la existencia de un vértice ordinario fue presentado en 1944 por Norman Steenrod, quien lo aplicó explícitamente al problema de la recta ordinaria dual.; Steenrod's proof was briefly summarized in .

Desigualdad de Melchior Mediante un argumento similar, Melchior pudo demostrar un resultado más general. Para cada , sea el número de puntos en los que inciden rectas. Entonces,

o, equivalentemente,

Axiomática escribió sobre la demostración de Kelly, afirmando que su uso de la distancia euclídea era innecesariamente poderoso, "como usar un mazo para romper una almendra". En cambio, Coxeter presentó otra demostración del teorema de Sylvester-Gallai dentro de la geometría ordenada, una axiomatización de la geometría en términos de intermediación que incluye no solo la geometría euclídea, sino también varias otras geometrías relacionadas. La demostración de Coxeter es una variación de una demostración anterior presentada por Steinberg en 1944. El problema de encontrar el conjunto mínimo de axiomas necesarios para demostrar el teorema pertenece a Ziegler.; . Véase a Coxeter; . For Steinberg's proof see . para un estudio de esta cuestión.

El enunciado habitual del teorema de Sylvester-Gallai no es válido en constructive analysis, ya que implica lesser limited principle of omniscience, una forma debilitada de principio del tercero excluido que se rechaza como axioma de las matemáticas constructivas. Sin embargo, es posible formular una versión del teorema de Sylvester-Gallai válida dentro de los axiomas del análisis constructivo y adaptar la demostración de Kelly para que sea válida bajo estos axiomas.

Hallazgo de una recta ordinaria La demostración de Kelly de la existencia de una recta ordinaria puede convertirse en un algoritmo que encuentra una recta ordinaria buscando el par más cercano de un punto y una recta que pase por otros dos puntos. indica el tiempo para esta búsqueda del par más cercano como , basándose en una búsqueda de fuerza bruta de todos los tripletes de puntos. Sin embargo, un algoritmo para encontrar el punto dado más cercano a cada recta que pase por dos puntos dados, en un tiempo , fue propuesto anteriormente por como una subrutina para encontrar el triángulo de área mínima determinado por tres puntos de un conjunto dado. El mismo artículo de también muestra cómo construir la disposición dual de rectas hacia los puntos dados (como se utiliza en la demostración de Melchior y Steenrod) en el mismo tiempo, , a partir del cual es posible identificar todos los vértices y rectas ordinarias. mostraron inicialmente cómo encontrar una sola recta ordinaria (no necesariamente la de la demostración de Kelly) en un tiempo , y describió un algoritmo más simple con el mismo límite temporal.

El algoritmo de se basa en la demostración de Coxeter mediante geometría ordenada. Realiza los siguientes pasos: Seleccionar un punto que sea un vértice de la envolvente convexa de los puntos dados. Construir una recta que pase por y que, de lo contrario, permanezca fuera de la envolvente convexa.