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 .
El teorema de Sylvester-Gallai fue planteado como un problema por Sylvester (1893). Kelly (1986) 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.[1]
Woodall (1893A) 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. Melchior (1941) 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,[2] Erdős (1943) volvió a formular la conjetura, que fue demostrada posteriormente por Tibor Gallai y, poco después, por otros autores.[3]
En una revisión de 1951, Erdős denominó el resultado como "teorema de Gallai",[4] pero ya se le denominaba teorema de Sylvester-Gallai en una revisión de Leonard Blumenthal de 1954.[5] Es uno de los muchos resultados que han recibido el nombre del matemático James Joseph Sylvester.
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.[2]
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.[6]
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 Borwein y Moser (1990). 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.
Esta demostración fue ideada por Leroy Milton Kelly. Aigner y Ziegler (2018) la considera "simplemente la mejor" de las muchas demostraciones de este teorema. [7]
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.[7]
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.[7]
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.[7]
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.[8]
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 .[8]
Como señala Aigner y Ziegler (2018), 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.[9]
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, [8]
o, equivalentemente,
Coxeter (1948) 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.[10] Véase a Coxeter[11] 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. [12]
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. Mukhopadhyay y Greene (2012) 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 Edelsbrunner y Guibas (1989) 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 Edelsbrunner y Guibas (1989) 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. Mukhopadhyay, Agrawal y Hosabettu (1997) mostraron inicialmente cómo encontrar una sola recta ordinaria (no necesariamente la de la demostración de Kelly) en un tiempo , y Mukhopadhyay y Greene (2012) describió un algoritmo más simple con el mismo límite temporal.
El algoritmo de Mukhopadhyay y Greene (2012) se basa en la demostración de Coxeter mediante geometría ordenada. Realiza los siguientes pasos:
Como demuestran los autores, la recta devuelta por este algoritmo debe ser ordinaria. La demostración es por construcción si se devuelve en el paso 4, o por contradicción si se devuelve en el paso 7: si la recta devuelta en el paso 7 no fuera ordinaria, los autores demuestran que existiría una recta ordinaria entre uno de sus puntos y , pero esta recta ya debería haberse encontrado y devuelto en el paso 4. [13]
Si bien el teorema de Sylvester-Gallai establece que una disposición de puntos, no todos colineales, debe determinar una recta ordinaria, no especifica cuántas deben determinarse. Sea el número mínimo de rectas ordinarias determinadas sobre cada conjunto de puntos no colineales. Melchior demostró que son . Erdős y de Bruijn (1948) plantearon la cuestión de si tiende al infinito con . Motzkin (1951) confirmó que sí lo hace al demostrar que . Dirac (1951) conjeturó que para todos los valores de . Esto se conoce a menudo como la «conjetura de Dirac-Motzkin»; véase, por ejemplo, Brass, Moser y Pach (2005, p. 304). Kelly y Moser (1958) demostró que .
La cota inferior conjeturada por Dirac es asintóticamente la mejor posible, ya que los números pares mayores que cuatro tienen una cota superior coincidente . La construcción, debida a Károly Böröczky, que logra esta cota consiste en los vértices de un -gono regular en el plano proyectivo real y otros puntos (por lo tanto, ) en la recta en el infinito correspondiente a cada una de las direcciones determinadas por pares de vértices. Aunque existen pares de estos puntos, estos determinan solo direcciones distintas. Esta disposición solo tiene rectas ordinarias, las que conectan un vértice con el punto en el infinito colineal con los dos vecinos de . Como con cualquier configuración finita en el plano proyectivo real, esta construcción puede perturbarse para que todos los puntos sean finitos, sin cambiar el número de rectas ordinarias.[14]
Para impar, solo se conocen dos ejemplos que coinciden con la conjetura de la cota inferior de Dirac, es decir, con . Un ejemplo, según Kelly y Moser (1958), consiste en los vértices, los puntos medios de las aristas y el baricentro de un triángulo equilátero; estos siete puntos determinan solo tres rectas ordinarias. La configuración, en la que estas tres rectas ordinarias se sustituyen por una sola, no puede realizarse en el plano euclídeo, sino que forma un espacio proyectivo finito conocido como plano de Fano. Debido a esta conexión, el ejemplo de Kelly-Moser también se ha denominado configuración no de Fano.[15] El otro contraejemplo, debido a McKee,[14] consiste en dos pentágonos regulares unidos arista con arista, con el punto medio de la arista compartida y cuatro puntos en la recta en el infinito en el plano proyectivo. Estos 13 puntos tienen entre ellos 6 rectas ordinarias. Las modificaciones de la construcción de Böröczky dan lugar a conjuntos de números impares de puntos con rectas ordinarias.[16]
Csima y Sawyer (1993) demostró que , excepto cuando es siete. Asintóticamente, esta fórmula ya es de la cota superior de demostrada. El caso es una excepción porque, de lo contrario, la construcción de Kelly-Moser sería un contraejemplo; su construcción muestra que . Sin embargo, si la cota de Csima-Sawyer fuera válida para , se afirmaría que .
Un resultado estrechamente relacionado es el teorema de Beck, que establece un equilibrio entre el número de líneas con pocos puntos y el número de puntos en una sola línea.[17]
Ben Green y Terence Tao mostraron que para todos los conjuntos de puntos suficientemente grandes (es decir, para alguna elección adecuada de ), el número de líneas rectas ordinarias es de hecho al menos . Además, cuando es impar, el número de líneas rectas ordinarias es al menos , para alguna constante . Por lo tanto, las construcciones de Böröczky para pares e impares (discutidas anteriormente) son las mejores posibles. Minimizar el número de líneas rectas ordinarias está estrechamente relacionado con el problema del huerto de maximizar el número de líneas rectas con tres puntos, que Green y Tao también resolvieron para todos los conjuntos de puntos suficientemente grandes.[18] En el entorno dual, donde se buscan puntos ordinarios, se puede considerar el número mínimo de puntos ordinarios en una disposición de pseudolíneas. En este contexto, el límite inferior de Csima-Sawyer sigue siendo válido,[19], aunque no se sabe si el límite asintótico de Green y Tao todavía se mantiene.
Como observó Paul Erdős, el teorema de Sylvester-Gallai implica inmediatamente que cualquier conjunto de puntos no colineales determina al menos rectas diferentes. Este resultado se conoce como el teorema de De Bruijn-Erdős. Como caso base, el resultado es claramente cierto para . Para cualquier valor mayor de , el resultado puede reducirse de puntos a puntos, eliminando una recta ordinaria y uno de sus dos puntos (teniendo cuidado de no eliminar un punto para el que el subconjunto restante se encontraría en una sola recta). Por lo tanto, se deduce por inducción matemática. El ejemplo de un conjunto de puntos colineales junto con un punto adicional que no está en la misma recta que los demás puntos, muestra que esta cota es ajustada.[16]
El teorema de Sylvester-Gallai se ha generalizado a conjuntos de puntos coloreados en el plano euclídeo y a sistemas de puntos y rectas definidos algebraicamente o por distancias en un espacio métrico. En general, estas variantes del teorema solo consideran conjuntos finitos de puntos, para evitar ejemplos como el conjunto de todos los puntos en el plano euclídeo, que no tiene una recta ordinaria.
Una variación del problema de Sylvester, planteada a mediados de la década de 1960 por Ronald Graham y popularizada por Donald J. Newman, considera conjuntos finitos de puntos en un plano (no todos en una recta) con dos colores, y pregunta si cada uno de estos conjuntos tiene una línea que pasa por dos o más puntos del mismo color. En el lenguaje de los conjuntos y de familias de conjuntos, una afirmación equivalente es que la familia de subconjuntos colineales de un conjunto finito de puntos (no todos en una línea) no puede tener la propiedad B. Theodore Motzkin anunció una demostración de esta variación, pero nunca se publicó. La primera demostración publicada fue realizada por Chakerian (1970).[20]
Así como el plano o el plano proyectivo pueden definirse utilizando números reales como coordenadas de sus puntos (con coordenadas cartesianas para el plano euclídeo y coordenadas homogéneas para el plano proyectivo), sistemas abstractos análogos de puntos y rectas pueden definirse utilizando otros sistemas numéricos como coordenadas. El teorema de Sylvester-Gallai no se cumple para geometrías definidas de esta manera sobre cuerpos finitos: para algunas geometrías finitas definidas de esta manera, como el plano de Fano, el conjunto de todos los puntos de la geometría no tiene rectas ordinarias.[7]
El teorema de Sylvester-Gallai tampoco se aplica directamente a geometrías en las que los puntos tienen coordenadas que son pares de números complejos o cuaterniones, pero estas geometrías tienen análogos más complejos del teorema. Por ejemplo, en el plano proyectivo complejo existe una configuración de nueve puntos, la configuración de Hesse (los puntos de inflexión de una curva cúbica), en la que cada línea recta es no ordinaria, violando el teorema de Sylvester-Gallai. Dicha configuración se conoce como configuración de Sylvester-Gallai, y no puede ser realizada por puntos y líneas rectas del plano euclídeo. Otra forma de enunciar el teorema de Sylvester-Gallai es que siempre que los puntos de una configuración de Sylvester-Gallai estén embebidos en un espacio euclídeo, preservando colineslidsdes, los puntos deben estar todos en una sola línea recta, y el ejemplo de la configuración de Hesse muestra que esto es falso para el plano proyectivo complejo. Sin embargo, Kelly (1986) demostró un análogo en los números complejos del teorema de Sylvester-Gallai: siempre que los puntos de una configuración de Sylvester-Gallai estén embebidos en un espacio proyectivo complejo, los puntos deben estar todos en un subespacio bidimensional. De manera equivalente, un conjunto de puntos en un espacio complejo tridimensional cuya envolvente afín es el espacio completo debe tener una línea recta ordinaria y, de hecho, debe tener un número lineal de líneas ordinarias.[21] De manera similar, Elkies, Pretorius y Swanepoel (2006) demostró que siempre que una configuración de Sylvester-Gallai se inserta en un espacio definido sobre los cuaterniones, sus puntos deben estar en un subespacio tridimensional.
Todo conjunto de puntos en el plano euclídeo, y las líneas rectas que los conectan, puede abstraerse como los elementos y planos de un matroide orientado de rango 3. Los puntos y líneas de geometrías definidas utilizando sistemas numéricos distintos a los números reales también forman matroides, pero no necesariamente matroides orientados. En este contexto, el resultado de acotar inferiormente el número de líneas rectas ordinarias según Kelly y Moser (1958) puede generalizarse a matroides orientados: todo matroide orientado de rango 3 con elementos tiene al menos líneas rectas de dos puntos, o, equivalentemente, todo matroide de rango 3 con menos líneas de dos puntos debe ser no orientable.[22] Un matroide sin líneas de dos puntos se denomina matroide de Sylvester. De igual manera, la configuración de Kelly-Moser con siete puntos y solo tres líneas ordinarias forma uno de los menores prohibidos para matroides representables GF(4).[15]
Otra generalización del teorema de Sylvester-Gallai a espacios métricos arbitrarios fue conjeturada por Chvátal (2004) y demostrada por Chen (2006). En esta generalización, una terna de puntos en un espacio métrico se define como colineal cuando la desigualdad triangular para estos puntos es una igualdad, y una línea recta se define a partir de cualquier par de puntos incluyendo repetidamente puntos adicionales colineales con puntos ya añadidos a la línea recta , hasta que no se puedan añadir más. La generalización de Chvátal y Chen establece que todo espacio métrico finito tiene una línea recta que contiene todos los puntos o exactamente dos de ellos.[23]