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. Recibe su nombre en honor a James Joseph Sylvester , quien lo planteó como problema en 1893, y a Tibor Gallai , quien publicó una de las primeras demostraciones de este teorema en 1944.
Una línea que contiene exactamente dos de un conjunto de puntos se conoce como una línea ordinaria . Otra forma de enunciar el teorema es que cada conjunto finito de puntos que no es colineal tiene una línea ordinaria. De acuerdo con un fortalecimiento del teorema, cada conjunto finito de puntos (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 puede haber estado motivado por un fenómeno relacionado en la 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 línea determinada por dos de los puntos contiene un tercer punto. El teorema de Sylvester-Gallai implica que es imposible que todos estos nueve puntos tengan coordenadas reales. [1]
HJ Woodall (1893a, 1893b) afirmó tener una prueba corta del teorema de Sylvester-Gallai, pero ya se había notado que estaba incompleta en el momento de su publicación. Eberhard Melchior (1941) demostró el teorema (y en realidad un resultado ligeramente más fuerte) en una formulación equivalente, su dual proyectivo . Sin saber de la prueba de Melchior, [2] Paul Erdős (1943) volvió a formular 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 había sido llamado teorema de Sylvester-Gallai en una revisión de 1954 por 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 puede plantearse para puntos en el plano proyectivo real RP 2 en lugar del plano euclidiano . El plano proyectivo puede formarse a partir del plano euclidiano añadiendo puntos adicionales "en el infinito" donde las líneas que son paralelas en el plano euclidiano se intersecan entre sí, y añadiendo una única línea "en el infinito" que contenga todos los puntos añadidos. Sin embargo, los puntos adicionales del plano proyectivo no pueden ayudar a crear conjuntos de puntos finitos no euclidianos sin ninguna línea ordinaria, ya que cualquier conjunto de puntos finitos en el plano proyectivo puede transformarse en un conjunto de puntos euclidianos con el mismo patrón combinatorio de incidencias punto-línea. Por lo tanto, cualquier patrón de un número finito de puntos y líneas que se intersecan 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 ciertas configuraciones más fácilmente. En particular, permite el uso de la dualidad proyectiva , en la que los roles de los puntos y las líneas en los enunciados de la geometría proyectiva pueden intercambiarse entre sí. En virtud de la 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 un arreglo 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 líneas. [2]
Los arreglos 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 un arreglo de líneas en el plano proyectivo, con una línea por 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 opuestas de hexágonos y cuatro pares de caras opuestas de paralelogramos. En el arreglo de cinco líneas correspondiente, dos triples de líneas se cruzan (que corresponden a los dos pares de hexágonos opuestos) y los cuatro pares de líneas restantes se cruzan en puntos ordinarios (que corresponden a los cuatro pares de paralelogramos opuestos). Un enunciado 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 firmemente, siempre que se pueda garantizar que los 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 ha sido demostrado de muchas maneras diferentes. La prueba de Gallai de 1944 alterna entre la geometría euclidiana y la proyectiva, con el fin de transformar los puntos en una configuración equivalente en la que una línea ordinaria puede encontrarse como una línea de pendiente más cercana a cero; para más detalles, véase Borwein y Moser (1990). La prueba de 1941 de Melchior utiliza la dualidad proyectiva para convertir el problema en una pregunta equivalente sobre disposiciones 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 menor distancia 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 solo los axiomas de la geometría ordenada .
Esta demostración es de Leroy Milton Kelly . Aigner y Ziegler (2018) la consideran "simplemente la mejor" de las muchas demostraciones de este teorema. [7]
Supongamos que un conjunto finito de puntos no es colineal. Definamos una línea de conexión como una línea que contiene al menos dos puntos en el conjunto. Por finitud, debe tener un punto y una línea de conexión que estén separados por una distancia positiva de modo que ningún otro par de puntos y líneas tenga una distancia positiva menor. Kelly demostró que es ordinaria, por contradicción . [7]
Supóngase que no es ordinario. Entonces pasa por al menos tres puntos de . Al menos dos de estos están en el mismo lado de , la proyección perpendicular de sobre . Llámalos y , siendo el más cercano a (y posiblemente coincidiendo con él). Dibuja la línea de conexión que pasa por y , y la perpendicular desde a sobre . Entonces es más corto que . Esto se deduce 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. Por lo tanto, la suposición de que no es ordinaria no puede ser verdadera, QED. [7]
En 1941 (es decir, antes de que Erdős publicara la pregunta y la posterior prueba 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 líneas ordinarias. [8]
Melchior observó que, para cualquier grafo insertado 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 de líneas no trivial 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 da como resultado la desigualdad adicional . El uso de esta desigualdad para eliminar de la característica de Euler conduce a la desigualdad . Pero si cada vértice en la disposición fuera el punto de cruce de tres o más líneas, entonces el número total de aristas sería al menos , contradiciendo esta desigualdad. Por lo tanto, algunos vértices deben ser el punto de cruce de solo dos líneas, 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), el mismo argumento para la existencia de un vértice ordinario también fue presentado en 1944 por Norman Steenrod , quien lo aplicó explícitamente al problema de la línea ordinaria dual. [9]
Con un argumento similar, Melchior pudo demostrar un resultado más general. Para cada , sea el número de puntos a los que inciden las líneas. Entonces [8]
o equivalentemente,
HSM Coxeter (1948, 1969) escribe sobre la prueba de Kelly que su uso de la distancia euclidiana es innecesariamente poderoso, "como usar un mazo para romper 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 solo la geometría euclidiana sino también 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 las matemáticas inversas ; 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 de omnisciencia menos limitado , una forma debilitada de la ley del tercio excluido que se rechaza como axioma de las matemáticas constructivas. 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 bajo estos axiomas. [12]
La prueba de Kelly de la existencia de una línea ordinaria se puede convertir en un algoritmo que encuentra una línea ordinaria buscando el par más cercano de un punto y una línea a través de 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 a través de dos puntos dados, en el tiempo , fue dado 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 a los puntos dados (como se usa en la prueba de Melchior y Steenrod) en el mismo tiempo, , a partir del 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 demostración de Coxeter mediante geometría ordenada y realiza los siguientes pasos:
Como demuestran los autores, la línea devuelta por este algoritmo debe ser ordinaria. 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 demuestran que existiría una línea ordinaria entre uno de sus puntos y , pero esta línea ya debería haberse encontrado y devuelto en el paso 4. [13]
Aunque el teorema de Sylvester-Gallai establece que una disposición de puntos, no todos colineales, debe determinar una línea ordinaria, no dice cuántos deben determinarse. Sea el número mínimo de líneas ordinarias determinadas sobre cada conjunto de puntos no colineales. La prueba de Melchior mostró que . de Bruijn y Erdős (1948) plantearon la cuestión de si tiende al infinito con . Theodore Motzkin (1951) confirmó que sí lo hace al demostrar que . Gabriel 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) 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 correspondiente . La construcción, debida a Károly Böröczky, que logra este límite consiste en los vértices de un -gono regular en el plano proyectivo real y otros puntos (por lo tanto, ) en la línea en el infinito correspondiente a cada una de las direcciones determinadas por pares de vértices. Aunque hay pares de estos puntos, determinan solo direcciones distintas. Esta disposición tiene solo líneas ordinarias, las líneas 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 ser perturbada para que todos los puntos sean finitos, sin cambiar el número de líneas ordinarias. [14]
Para impar , solo 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), consiste en los vértices, los puntos medios de las aristas y el centroide de un triángulo equilátero; estos siete puntos determinan solo tres líneas ordinarias. La configuración en la que estas tres líneas ordinarias se reemplazan por una sola línea no se puede realizar en el plano euclidiano, sino que forma un espacio proyectivo finito conocido como el plano de Fano . Debido a esta conexión, el ejemplo de Kelly-Moser también se ha llamado 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. [16]
Csima y Sawyer (1993) demostraron que excepto cuando es siete. Asintóticamente, esta fórmula ya tiene el límite superior demostrado . 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 el límite de 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 de hecho 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 plantación de huertos 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 uno busca puntos ordinarios, 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 que no sean colineales determina al menos líneas 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 se puede reducir de puntos a puntos, eliminando una línea ordinaria y uno de los dos puntos en ella (teniendo cuidado de no eliminar un punto para el cual el subconjunto restante estaría en una sola línea). Por lo tanto, se deduce por inducción matemática. El ejemplo de un lápiz cercano, 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 estricto. [16]
El teorema de Sylvester-Gallai se ha generalizado a conjuntos de puntos coloreados en el plano euclidiano y a sistemas de puntos y líneas definidos algebraicamente o por distancias en un espacio métrico . En general, estas variaciones del teorema consideran solo conjuntos finitos de puntos, para evitar ejemplos como el conjunto de todos los puntos en el plano euclidiano, que no tiene una línea 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 planares (no todos en una línea) a los que se les dan dos colores, y pregunta si cada uno de esos conjuntos tiene una línea que pasa por dos o más puntos que son todos del mismo color. En el lenguaje de los 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 de Chakerian (1970). [20]
Así como el plano euclidiano o el plano proyectivo se pueden definir utilizando 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 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 en 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 más complicados 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 es no ordinaria, violando el teorema de Sylvester-Gallai. Tal configuración se conoce como configuración de Sylvester-Gallai , y no puede realizarse por 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 colineales , los puntos deben estar todos 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úmero complejo del teorema de Sylvester-Gallai: siempre que los puntos de una configuración de Sylvester-Gallai estén insertos 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 cuya envoltura afín es todo el espacio 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é inserta 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 planos de un matroide orientado 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 orientados. En este contexto, el resultado de Kelly y Moser (1958) de limitar por debajo el número de líneas ordinarias puede generalizarse a matroides orientados: cada matroide orientado de rango 3 con elementos tiene al menos líneas de dos puntos, o equivalentemente, cada matroide de rango 3 con menos líneas de dos puntos debe ser no orientable. [22] Un matroide sin ninguna línea de dos puntos se llama matroide de Sylvester . En relación con esto, la configuración de Kelly-Moser con siete puntos y solo tres líneas ordinarias forma uno de los menores prohibidos para los matroides representables por 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, un triple 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 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 ese tipo. La generalización de Chvátal y Chen establece que cada espacio métrico finito tiene una línea que contiene todos los puntos o exactamente dos de los puntos. [23]
