The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

A line that contains exactly two of a set of points is known as an ordinary line. Another way of stating the theorem is that every finite set of points that is not collinear has an ordinary line. According to a strengthening of the theorem, every finite point set (not all on one line) has at least a linear number of ordinary lines. An algorithm can find an ordinary line in a set of ${\displaystyle n}$ points in time ${\displaystyle O(n\log n)}$.

History

The Sylvester–Gallai theorem was posed as a problem by J. J. Sylvester (1893). Kelly (1986) suggests that Sylvester may have been motivated by a related phenomenon in algebraic geometry, in which the inflection points of a cubic curve in the complex projective plane form a configuration of nine points and twelve lines (the Hesse configuration) in which each line determined by two of the points contains a third point. The Sylvester–Gallai theorem implies that it is impossible for all nine of these points to have real coordinates.^[1]

H. J. Woodall (1893a, 1893b) claimed to have a short proof of the Sylvester–Gallai theorem, but it was already noted to be incomplete at the time of publication. Eberhard Melchior (1941) proved the theorem (and actually a slightly stronger result) in an equivalent formulation, its projective dual. Unaware of Melchior's proof,^[2] Paul Erdős (1943) again stated the conjecture, which was subsequently proved by Tibor Gallai, and soon afterwards by other authors.^[3]

In a 1951 review, Erdős called the result "Gallai's theorem",^[4] but it was already called the Sylvester–Gallai theorem in a 1954 review by Leonard Blumenthal.^[5] It is one of many mathematical topics named after Sylvester.

Equivalent versions

The question of the existence of an ordinary line can also be posed for points in the real projective plane RP² instead of the Euclidean plane. The projective plane can be formed from the Euclidean plane by adding extra points "at infinity" where lines that are parallel in the Euclidean plane intersect each other, and by adding a single line "at infinity" containing all the added points. However, the additional points of the projective plane cannot help create non-Euclidean finite point sets with no ordinary line, as any finite point set in the projective plane can be transformed into a Euclidean point set with the same combinatorial pattern of point-line incidences. Therefore, any pattern of finitely many intersecting points and lines that exists in one of these two types of plane also exists in the other. Nevertheless, the projective viewpoint allows certain configurations to be described more easily. In particular, it allows the use of projective duality, in which the roles of points and lines in statements of projective geometry can be exchanged for each other. Under projective duality, the existence of an ordinary line for a set of non-collinear points in RP² is equivalent to the existence of an ordinary point in a nontrivial arrangement of finitely many lines. An arrangement is said to be trivial when all its lines pass through a common point, and nontrivial otherwise; an ordinary point is a point that belongs to exactly two lines.^[2]

Arrangements of lines have a combinatorial structure closely connected to zonohedra, polyhedra formed as the Minkowski sum of a finite set of line segments, called generators. In this connection, each pair of opposite faces of a zonohedron corresponds to a crossing point of an arrangement of lines in the projective plane, with one line for each generator. The number of sides of each face is twice the number of lines that cross in the arrangement. For instance, the elongated dodecahedron shown is a zonohedron with five generators, two pairs of opposite hexagon faces, and four pairs of opposite parallelogram faces. In the corresponding five-line arrangement, two triples of lines cross (corresponding to the two pairs of opposite hexagons) and the remaining four pairs of lines cross at ordinary points (corresponding to the four pairs of opposite parallelograms). An equivalent statement of the Sylvester–Gallai theorem, in terms of zonohedra, is that every zonohedron has at least one parallelogram face (counting rectangles, rhombuses, and squares as special cases of parallelograms). More strongly, whenever sets of ${\displaystyle n}$ points in the plane can be guaranteed to have at least ${\displaystyle t_{2}(n)}$ ordinary lines, zonohedra with ${\displaystyle n}$ generators can be guaranteed to have at least ${\displaystyle 2t_{2}(n)}$ parallelogram faces.^[6]

Proofs

The Sylvester–Gallai theorem has been proved in many different ways. Gallai's 1944 proof switches back and forth between Euclidean and projective geometry, in order to transform the points into an equivalent configuration in which an ordinary line can be found as a line of slope closest to zero; for details, see Borwein & Moser (1990). The 1941 proof by Melchior uses projective duality to convert the problem into an equivalent question about arrangements of lines, which can be answered using Euler's polyhedral formula. Another proof by Leroy Milton Kelly shows by contradiction that the connecting line with the smallest nonzero distance to another point must be ordinary. And, following an earlier proof by Steinberg, H. S. M. Coxeter showed that the metric concepts of slope and distance appearing in Gallai's and Kelly's proofs are unnecessarily powerful, instead proving the theorem using only the axioms of ordered geometry.

Kelly's proof

This proof is by Leroy Milton Kelly. Aigner & Ziegler (2018) call it "simply the best" of the many proofs of this theorem.^[7]

Suppose that a finite set ${\displaystyle S}$ of points is not all collinear. Define a connecting line to be a line that contains at least two points in the collection. By finiteness, ${\displaystyle S}$ must have a point ${\displaystyle P}$ and a connecting line ${\displaystyle \ell }$ that are a positive distance apart but are closer than all other point-line pairs. Kelly proved that ${\displaystyle \ell }$ is ordinary, by contradiction.^[7]

Assume that ${\displaystyle \ell }$ is not ordinary. Then it goes through at least three points of ${\displaystyle S}$. At least two of these are on the same side of ${\displaystyle P'}$, the perpendicular projection of ${\displaystyle P}$ on ${\displaystyle \ell }$. Call them ${\displaystyle B}$ and ${\displaystyle C}$, with ${\displaystyle B}$ being closest to ${\displaystyle P'}$ (and possibly coinciding with it). Draw the connecting line ${\displaystyle m}$ passing through ${\displaystyle P}$ and ${\displaystyle C}$, and the perpendicular from ${\displaystyle B}$ to ${\displaystyle B'}$ on ${\displaystyle m}$ . Then ${\displaystyle BB'}$ is shorter than ${\displaystyle PP'}$. This follows from the fact that ${\displaystyle PP'C}$ and ${\displaystyle BB'C}$ are similar triangles, one contained inside the other.^[7]

However, this contradicts the original definition of ${\displaystyle P}$ and ${\displaystyle \ell }$ as the point-line pair with the smallest positive distance. So the assumption that ${\displaystyle \ell }$ is not ordinary cannot be true, QED.^[7]

Melchior's proof

In 1941 (thus, prior to Erdős publishing the question and Gallai's subsequent proof) Melchior showed that any nontrivial finite arrangement of lines in the projective plane has at least three ordinary points. By duality, this results also says that any finite nontrivial set of points on the plane has at least three ordinary lines.^[8]

Melchior observed that, for any graph embedded in the real projective plane, the formula ${\displaystyle V-E+F}$ must equal ${\displaystyle 1}$, the Euler characteristic of the projective plane. Here ${\displaystyle V}$, ${\displaystyle E}$, and ${\displaystyle F}$ are the number of vertices, edges, and faces of the graph, respectively. Any nontrivial line arrangement on the projective plane defines a graph in which each face is bounded by at least three edges, and each edge bounds two faces; so, double counting gives the additional inequality ${\displaystyle F\leq 2E/3}$. Using this inequality to eliminate ${\displaystyle F}$ from the Euler characteristic leads to the inequality ${\displaystyle E\leq 3V-3}$. But if every vertex in the arrangement were the crossing point of three or more lines, then the total number of edges would be at least ${\displaystyle 3V}$, contradicting this inequality. Therefore, some vertices must be the crossing point of only two lines, and as Melchior's more careful analysis shows, at least three ordinary vertices are needed in order to satisfy the inequality ${\displaystyle E\leq 3V-3}$.^[8]

As Aigner & Ziegler (2018) note, the same argument for the existence of an ordinary vertex was also given in 1944 by Norman Steenrod, who explicitly applied it to the dual ordinary line problem.^[9]

Melchior's inequality

By a similar argument, Melchior was able to prove a more general result. For every ${\displaystyle k\geq 2}$, let ${\displaystyle t_{k}}$ be the number of points to which ${\displaystyle k}$ lines are incident. Then^[8]

${\displaystyle \displaystyle \sum _{k\geq 2}(k-3)t_{k}\leq -3.}$

or equivalently,

${\displaystyle \displaystyle t_{2}\geqslant 3+\sum _{k\geq 4}(k-3)t_{k}.}$

Axiomatics

H. S. M. Coxeter (1948, 1969) writes of Kelly's proof that its use of Euclidean distance is unnecessarily powerful, "like using a sledge hammer to crack an almond". Instead, Coxeter gave another proof of the Sylvester–Gallai theorem within ordered geometry, an axiomatization of geometry in terms of betweenness that includes not only Euclidean geometry but several other related geometries.^[10] Coxeter's proof is a variation of an earlier proof given by Steinberg in 1944.^[11] The problem of finding a minimal set of axioms needed to prove the theorem belongs to reverse mathematics; see Pambuccian (2009) for a study of this question.

The usual statement of the Sylvester–Gallai theorem is not valid in constructive analysis, as it implies the lesser limited principle of omniscience, a weakened form of the law of excluded middle that is rejected as an axiom of constructive mathematics. Nevertheless, it is possible to formulate a version of the Sylvester–Gallai theorem that is valid within the axioms of constructive analysis, and to adapt Kelly's proof of the theorem to be a valid proof under these axioms.^[12]

Finding an ordinary line

Kelly's proof of the existence of an ordinary line can be turned into an algorithm that finds an ordinary line by searching for the closest pair of a point and a line through two other points. Mukhopadhyay & Greene (2012) report the time for this closest-pair search as ${\displaystyle O(n^{3})}$, based on a brute-force search of all triples of points, but an algorithm to find the closest given point to each line through two given points, in time ${\displaystyle O(n^2}$Zdroj:https://en.wikipedia.org?pojem=Sylvester–Gallai_theorem
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.