El teorema de Sylvester-Gallai en geometría establece que todo conjunto finito de puntos en el plano euclidiano tiene una línea que pasa por exactamente dos de los puntos o una línea que pasa por todos ellos. Lleva el nombre de James Joseph Sylvester , quien lo planteó como un problema en 1893, y de Tibor Gallai , quien publicó una de las primeras demostraciones de este teorema en 1944.
Una recta que contiene exactamente dos de un conjunto de puntos se conoce como recta ordinaria . Otra forma de enunciar el teorema es que todo conjunto finito de puntos que no es colineal tiene una recta ordinaria. Según un fortalecimiento del teorema, cada conjunto de puntos finitos (no todos en una línea) tiene al menos un número lineal de líneas ordinarias. Un algoritmo puede encontrar una línea ordinaria en un conjunto de puntos en el tiempo .
El teorema de Sylvester-Gallai fue planteado como un problema por JJ Sylvester (1893). Kelly (1986) sugiere que Sylvester pudo haber sido motivado por un fenómeno relacionado en geometría algebraica , en el que los puntos de inflexión de una curva cúbica en el plano proyectivo complejo forman una configuración de nueve puntos y doce líneas (la configuración de Hesse ) en la que cada La 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]
HJ Woodall (1893a, 1893b) afirmó tener una breve demostración del teorema de Sylvester-Gallai, pero ya se observó que estaba incompleta en el momento de su publicación. Eberhard Melchior (1941) demostró el teorema (y en realidad un resultado ligeramente más sólido) en una formulación equivalente, su dual proyectivo . Desconociendo la prueba de Melchor, [2] Paul Erdős (1943) volvió a plantear la conjetura, que fue posteriormente demostrada por Tibor Gallai , y poco después por otros autores. [3]
En una revisión de 1951, Erdős llamó al resultado "teorema de Gallai", [4] pero ya se llamaba teorema de Sylvester-Gallai en una revisión de 1954 de Leonard Blumenthal . [5] Es uno de los muchos temas matemáticos que llevan el nombre de Sylvester .
La cuestión de la existencia de una línea ordinaria también se puede plantear para puntos en el plano proyectivo real RP 2 en lugar del plano euclidiano . El plano proyectivo se puede formar a partir del plano euclidiano agregando puntos adicionales "en el infinito" donde las líneas que son paralelas en el plano euclidiano se cruzan entre sí, y agregando una sola línea "en el infinito" que contenga todos los puntos agregados. Sin embargo, los puntos adicionales del plano proyectivo no pueden ayudar a crear conjuntos de puntos finitos no euclidianos sin una línea ordinaria, ya que cualquier conjunto de puntos finitos en el plano proyectivo se puede transformar en un conjunto de puntos euclidianos con el mismo patrón combinatorio de incidencias de puntos y líneas. . Por lo tanto, cualquier patrón de un número finito de puntos y líneas que se cruzan que existe en uno de estos dos tipos de plano también existe en el otro. Sin embargo, el punto de vista proyectivo permite describir más fácilmente determinadas configuraciones. En particular, permite el uso de la dualidad proyectiva , en la que los roles de puntos y líneas en enunciados de geometría proyectiva se pueden intercambiar entre sí. Bajo dualidad proyectiva, la existencia de una línea ordinaria para un conjunto de puntos no colineales en RP 2 es equivalente a la existencia de un punto ordinario en una disposición no trivial de un número finito de líneas. Se dice que un arreglo es trivial cuando todas sus líneas 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 líneas tienen una estructura combinatoria estrechamente relacionada con los zonoedros , poliedros formados como la suma de Minkowski de un conjunto finito de segmentos de línea , llamados generadores. En este sentido, cada par de caras opuestas de un zonoedro corresponde a un punto de cruce de una disposición de líneas en el plano proyectivo, con una línea para cada generador. El número de lados de cada cara es el doble del número de líneas que se cruzan en el arreglo. Por ejemplo, el dodecaedro alargado que se muestra es un zonoedro con cinco generadores, dos pares de caras hexagonales opuestas y cuatro pares de caras de paralelogramo opuestas. En la disposición correspondiente de cinco líneas, dos triples de líneas se cruzan (correspondientes a los dos pares de hexágonos opuestos) y los cuatro pares de líneas restantes se cruzan en puntos ordinarios (correspondientes a los cuatro pares de paralelogramos opuestos). Una afirmación equivalente del teorema de Sylvester-Gallai, en términos de zonoedros, es que cada zonoedro tiene al menos una cara de paralelogramo (contando rectángulos, rombos y cuadrados como casos especiales de paralelogramos). Más claramente, siempre que se pueda garantizar que conjuntos de puntos en el plano tengan al menos líneas ordinarias, se puede garantizar que los zonoedros con generadores tengan al menos caras de paralelogramo. [6]
El teorema de Sylvester-Gallai se ha demostrado de muchas maneras diferentes. La prueba de Gallai de 1944 alterna entre geometría euclidiana y proyectiva, para transformar los puntos en una configuración equivalente en la que se puede encontrar una línea ordinaria como una línea de pendiente más cercana a cero; para más detalles, véase Borwein y Moser (1990). La prueba de Melchior de 1941 utiliza la dualidad proyectiva para convertir el problema en una pregunta equivalente sobre la disposición de líneas, que puede responderse utilizando la fórmula poliédrica de Euler . Otra prueba de Leroy Milton Kelly muestra por contradicción que la línea de conexión con la distancia más pequeña distinta de cero a otro punto debe ser ordinaria. Y, siguiendo una prueba anterior de Steinberg, HSM Coxeter demostró que los conceptos métricos de pendiente y distancia que aparecen en las pruebas de Gallai y Kelly son innecesariamente poderosos, demostrando en cambio el teorema utilizando sólo los axiomas de la geometría ordenada .
Esta prueba es de Leroy Milton Kelly . Aigner y Ziegler (2018) la llaman "simplemente la mejor" de las muchas demostraciones de este teorema. [7]
Supongamos que no todos los puntos de un conjunto finito son colineales. Defina una línea de conexión para que sea una línea que contenga al menos dos puntos en la colección. Por finitud, debe tener un punto y una línea de conexión que estén separados por una distancia positiva pero más cercanos que todos los demás pares de punto y línea. Kelly demostró que eso es normal, por contradicción . [7]
Supongamos que eso no es normal. Luego pasa por al menos tres puntos de . Al menos dos de ellos están en el mismo lado de la proyección perpendicular de on . Llámalos y , siendo el más cercano (y posiblemente coincidiendo con él). Dibuja la línea de conexión que pasa por y , y la perpendicular de a en . Entonces es más corto que . Esto se desprende del hecho de que y son triángulos semejantes , uno contenido dentro del otro. [7]
Sin embargo, esto contradice la definición original de y como el par punto-línea con la distancia positiva más pequeña. Así que la suposición de que no es ordinaria no puede ser cierta, QED. [7]
En 1941 (por lo tanto, antes de que Erdős publicara la pregunta y la prueba posterior de Gallai), Melchior demostró que cualquier disposición finita no trivial de líneas en el plano proyectivo tiene al menos tres puntos ordinarios. Por dualidad, este resultado también dice que cualquier conjunto finito no trivial de puntos en el plano tiene al menos tres rectas ordinarias. [8]
Melchior observó que, para cualquier gráfico incrustado 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 gráfico, respectivamente. Cualquier disposición de líneas no trivial en el plano proyectivo define un gráfico en el que cada cara está delimitada por al menos tres aristas, y cada arista limita dos caras; entonces, el doble conteo da la desigualdad adicional . Usar esta desigualdad para eliminar de la característica de Euler conduce a la desigualdad . Pero si cada vértice del arreglo fuera el punto de cruce de tres o más líneas, 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 cruce de sólo dos rectas y, como muestra el análisis más cuidadoso de Melchior, se necesitan al menos tres vértices ordinarios para satisfacer la desigualdad . [8]
Como señalan Aigner y Ziegler (2018), Norman Steenrod también dio el mismo argumento a favor de la existencia de un vértice ordinario en 1944 , quien lo aplicó explícitamente al problema de la recta ordinaria dual. [9]
Con un argumento similar, Melchor pudo demostrar un resultado más general. Para cada , sea el número de puntos en los que inciden las líneas. Entonces [8]
o equivalente,
HSM Coxeter (1948, 1969) escribe sobre la prueba de Kelly de que su uso de la distancia euclidiana es innecesariamente poderoso, "como usar un mazo para partir una almendra". En cambio, Coxeter dio otra prueba 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 sólo la geometría euclidiana sino varias otras geometrías relacionadas. [10] La prueba de Coxeter es una variación de una prueba anterior dada por Steinberg en 1944. [11] El problema de encontrar un conjunto mínimo de axiomas necesarios para demostrar el teorema pertenece a la matemática inversa ; véase Pambuccian (2009) para un estudio de esta cuestión.
El enunciado habitual del teorema de Sylvester-Gallai no es válido en el análisis constructivo , ya que implica el principio menos limitado de omnisciencia , una forma debilitada de la ley del tercero excluido que se rechaza como axioma de la matemática constructiva. Sin embargo, es posible formular una versión del teorema de Sylvester-Gallai que sea válida dentro de los axiomas del análisis constructivo y adaptar la prueba de Kelly del teorema para que sea una prueba válida según estos axiomas. [12]
La prueba de Kelly de la existencia de una recta ordinaria se puede convertir en un algoritmo que encuentra una recta ordinaria buscando el par más cercano de un punto y una recta que pasa por otros dos puntos. Mukhopadhyay y Greene (2012) informan que el tiempo para esta búsqueda del par más cercano es , basado en una búsqueda de fuerza bruta de todos los triples de puntos, pero un algoritmo para encontrar el punto dado más cercano a cada línea que pasa por dos puntos dados, en el tiempo , fue dada anteriormente por Edelsbrunner y Guibas (1989), como una subrutina para encontrar el triángulo de área mínima determinado por tres de un conjunto dado de puntos. El mismo artículo de Edelsbrunner y Guibas (1989) también muestra cómo construir la disposición dual de líneas hasta los puntos dados (como se usa en la prueba de Melchior y Steenrod) al mismo tiempo, a partir de la cual es posible identificar todos los vértices ordinarios y todas las líneas ordinarias. Mukhopadhyay, Agrawal y Hosabettu (1997) mostraron por primera vez cómo encontrar una sola línea ordinaria (no necesariamente la de la prueba de Kelly) en el tiempo , y Mukhopadhyay y Greene (2012) describieron un algoritmo más simple con el mismo límite de tiempo.
El algoritmo de Mukhopadhyay & Greene (2012) se basa en la prueba de Coxeter utilizando geometría ordenada. Realiza los siguientes pasos:
Como demuestran los autores, la línea devuelta por este algoritmo debe ser normal. La prueba es por construcción si se devuelve en el paso 4, o por contradicción si se devuelve en el paso 7: si la línea devuelta en el paso 7 no fuera ordinaria, entonces los autores prueban que existiría una línea ordinaria entre uno de sus puntos y , pero esta línea ya debería haber sido encontrada y devuelta 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 dice cuántos deben determinarse. Sea el número mínimo de rectas ordinarias determinado sobre cada conjunto de puntos no colineales. La prueba de Melchor demostró que . de Bruijn y Erdős (1948) plantearon la cuestión de si se aproxima al infinito con . Theodore Motzkin (1951) confirmó que sí, demostrando que . Gabriel Dirac (1951) conjeturó que , para todos los valores de . A esto se le suele denominar conjetura de Dirac-Motzkin ; véase, por ejemplo, Brass, Moser y Pach (2005, p. 304). Kelly y Moser (1958) demostraron que .
El límite inferior conjeturado por Dirac es asintóticamente el mejor posible, ya que los números pares mayores que cuatro tienen un límite superior coincidente . La construcción, debida a Károly Böröczky, que logra esta cota consiste en los vértices de un -gón regular en el plano proyectivo real y otros puntos (así, ) en la recta del infinito correspondiente a cada una de las direcciones determinadas por pares de vértices. Aunque hay pares de estos puntos, sólo determinan direcciones distintas. Esta disposición tiene sólo líneas ordinarias, las líneas que conectan un vértice con el punto en el infinito colineales con los dos vecinos de . Como ocurre con cualquier configuración finita en el plano proyectivo real, esta construcción se puede alterar de modo que todos los puntos sean finitos, sin cambiar el número de líneas ordinarias. [14]
Para impar , sólo se conocen dos ejemplos que coinciden con la conjetura del límite inferior de Dirac, es decir, con Un ejemplo, de Kelly y Moser (1958), consta de los vértices, los puntos medios de las aristas y el centroide de un triángulo equilátero; estos siete puntos determinan sólo tres rectas ordinarias. La configuración en la que estas tres líneas ordinarias son reemplazadas por una sola línea no puede realizarse en el plano euclidiano, 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 Fano. [15] El otro contraejemplo, debido a McKee, [14] consiste en dos pentágonos regulares unidos borde con borde junto con el punto medio del borde compartido y cuatro puntos en la línea en el infinito en el plano proyectivo ; estos 13 puntos tienen entre ellos 6 líneas ordinarias. Las modificaciones de la construcción de Böröczky conducen a conjuntos de números impares de puntos con líneas ordinarias. [dieciséis]
Csima y Sawyer (1993) demostraron que excepto cuando es siete. Asintóticamente, esta fórmula ya tiene el límite superior probado . El caso es una excepción porque de lo contrario la construcción de Kelly-Moser sería un contraejemplo; su construcción lo demuestra . Sin embargo, si el vínculo Csima-Sawyer fuera válido para , 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 demostraron que para todos los conjuntos de puntos suficientemente grandes (es decir, para alguna elección adecuada de ), el número de líneas ordinarias es al menos . Además, cuando es impar , el número de líneas 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 ordinarias está estrechamente relacionado con el problema de maximizar el número de líneas de 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 sigue siendo válido.
Como observó Paul Erdős , el teorema de Sylvester-Gallai implica inmediatamente que cualquier conjunto de puntos que no sean colineales determina al menos rectas diferentes. Este resultado se conoce como teorema de De Bruijn-Erdős . Como caso base, el resultado es claramente válido para . Para cualquier valor mayor de , el resultado se puede reducir de puntos a puntos, eliminando una línea ordinaria y uno de los dos puntos que contiene (teniendo cuidado de no eliminar un punto cuyo subconjunto restante se encuentre en una sola línea). Por tanto, se sigue por inducción matemática. El ejemplo de un casi lápiz, un conjunto de puntos colineales junto con un punto adicional que no está en la misma línea que los otros puntos, muestra que este límite es estrecho. [dieciséis]
El teorema de Sylvester-Gallai se ha generalizado a conjuntos de puntos coloreados en el plano euclidiano y a sistemas de puntos y rectas definidos algebraicamente o por distancias en un espacio métrico . En general, estas variaciones del teorema consideran sólo conjuntos finitos de puntos, para evitar ejemplos como el conjunto de todos los puntos en el plano euclidiano, que no tiene una recta ordinaria.
Una variación del problema de Sylvester, planteado a mediados de la década de 1960 por Ronald Graham y popularizado por Donald J. Newman , considera conjuntos planos finitos de puntos (no todos en una línea) a los que se les dan dos colores, y pregunta si cada uno de esos conjuntos tiene un línea que pasa por dos o más puntos que son todos del mismo color. En el lenguaje de conjuntos y familias de conjuntos , una afirmación equivalente es que la familia de los subconjuntos colineales de un conjunto de puntos finitos (no todos en una línea) no puede tener la Propiedad B. Theodore Motzkin anunció una prueba de esta variación, pero nunca se publicó; la primera prueba publicada fue la de Chakerian (1970). [20]
Así como el plano euclidiano o el plano proyectivo se pueden definir usando números reales para las coordenadas de sus puntos ( coordenadas cartesianas para el plano euclidiano y coordenadas homogéneas para el plano proyectivo), se pueden definir sistemas abstractos análogos de puntos y líneas usando otros sistemas numéricos como coordenadas. El teorema de Sylvester-Gallai no es válido para geometrías definidas de esta manera sobre campos 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 líneas 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 del teorema más complicados. 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 no es ordinaria, violando el teorema de Sylvester-Gallai. Esta configuración se conoce como configuración de Sylvester-Gallai y no puede realizarse mediante puntos y líneas del plano euclidiano. Otra forma de enunciar el teorema de Sylvester-Gallai es que siempre que los puntos de una configuración de Sylvester-Gallai están incrustados en un espacio euclidiano, preservando las colinealidades , todos los puntos deben estar en una sola línea, 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 de números complejos del teorema de Sylvester-Gallai: siempre que los puntos de una configuración de Sylvester-Gallai están incrustados en un espacio proyectivo complejo, todos los puntos deben estar en un subespacio bidimensional. De manera equivalente, un conjunto de puntos en un espacio complejo tridimensional cuyo casco afín es el espacio completo debe tener una línea ordinaria y, de hecho, debe tener un número lineal de líneas ordinarias. [21] De manera similar, Elkies, Pretorius y Swanepoel (2006) demostraron que siempre que una configuración de Sylvester-Gallai está incrustada en un espacio definido sobre los cuaterniones, sus puntos deben estar en un subespacio tridimensional.
Cada conjunto de puntos en el plano euclidiano, y las líneas que los conectan, pueden abstraerse como los elementos y pisos de una matroide orientada de rango 3 . Los puntos y líneas de geometrías definidas utilizando otros sistemas numéricos distintos de los números reales también forman matroides , pero no necesariamente matroides orientadas. En este contexto, el resultado de Kelly y Moser (1958) de limitar el número de líneas ordinarias a límites inferiores se puede generalizar a matroides orientadas: cada matroide orientada de rango 3 con elementos tiene al menos líneas de dos puntos, o de manera equivalente, cada matroide de rango 3 con elementos tiene al menos líneas de dos puntos, o de manera equivalente, cada matroide de rango 3 La matroide con menos líneas de dos puntos no debe ser orientable. [22] Una matroide sin líneas de dos puntos se llama matroide Sylvester . De manera relacionada, la configuración de Kelly-Moser con siete puntos y solo tres líneas ordinarias forma uno de los menores prohibidos para las matroides representables con GF (4) . [15]
Chvátal (2004) conjeturó otra generalización del teorema de Sylvester-Gallai a espacios métricos arbitrarios y Chen (2006) la demostró. En esta generalización, un triple de puntos en un espacio métrico se define como colineal cuando la desigualdad del triángulo para estos puntos es una igualdad, y una línea se define a partir de cualquier par de puntos incluyendo repetidamente puntos adicionales que son colineales con puntos ya agregados. a la línea, hasta que no se puedan agregar más puntos de este tipo. La generalización de Chvátal y Chen establece que todo espacio métrico finito tiene una línea que contiene todos los puntos o exactamente dos de los puntos. [23]
