Sylvester–Gallai theorem

The Sylvester–Gallai theorem in geometry states that, given a finite number of points in the Euclidean plane, either

all the points lie on a single line; or
there is at least one line which contains exactly two of the points.

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. According to a strengthening of the theorem, every finite point set (not all on a line) has at least a linear number of ordinary lines. There is an algorithm that finds an ordinary line in a set of $n$ points in time $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]

Woodall (1893) harvtxt error: multiple targets (2×): CITEREFWoodall1893 (help) 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]

Projective and dual 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 Euclidean plane can be viewed as a subset of the projective plane, but the additional points and lines of the projective plane do not change the problem, as any finite set of projective points can be transformed into a Euclidean point set without changing its set of ordinary lines. 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. However, the projective viewpoint allows certain configurations to be described more easily. By 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]

Proofs

For a description of Gallai's original proof of the theorem, see e.g. Borwein & Moser (1990).

Kelly's proof

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

Suppose that a finite set 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, there must exist a point P and a connecting line ℓ that are a positive distance apart but are closer than all other point-line pairs. Kelly proved that ℓ is ordinary, by contradiction.^[4]

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

However, this contradicts the original definition of P and ℓ as the point-line pair with the smallest positive distance. So the assumption that ℓ is not ordinary cannot be true, QED.^[4]

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.^[5]

Melchior observed that, for any graph embedded in the real projective plane, the formula $V-E+F$ must equal $1$ , the Euler characteristic of the projective plane. Here $V$ , $E$ , and $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 $F\leq 2E/3$ . Using this inequality to eliminate $F$ from the Euler characteristic leads to the inequality $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 $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 $E\leq 3V-3$ .^[5]

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.^[6]

Melchior's inequality

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

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

or equivalently,

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

Coxeter's proof

H. S. M. Coxeter (1969) gave another proof of the Sylvester–Gallai theorem within ordered geometry, an axiomatization of geometry that includes not only Euclidean geometry but several other related geometries.^[4] See Pambuccian (2009) for minimal axiom systems inside which the Sylvester–Gallai theorem can be proved.

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 (2007) report the time for this closest-pair search as $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 $O(n^{2})$ , was given earlier by Edelsbrunner & Guibas (1989), as a subroutine for finding the minimum-area triangle determined by three of a given set of points. The same paper of Edelsbrunner & Guibas (1989) also shows how to construct the dual arrangement of lines to the given points (as used in Melchior and Steenrod's proof) in the same time, $O(n^{2})$ , from which it is possible to identify all ordinary vertices and all ordinary lines. Mukhopadhyay, Agrawal & Hosabettu (1997) first showed how to find a single ordinary line (not necessarily the one from Kelly's proof) in time $O(n\log n)$ , and a simpler algorithm with the same time bound was described by Mukhopadhyay & Greene (2007).

The algorithm of Mukhopadhyay & Greene (2007) is based on Coxeter's proof using ordered geometry. It begins by choosing a point $p_{0}$ that is a vertex of the convex hull of the given points, and a line $\ell _{0}$ that is a supporting line of the convex hull, disjoint from the other given points. It sorts the other given points by the angle they make with $p_{0}$ , and within each group of points with the same angle, by their distance from $p_{0}$ . If any of these groups has only one point in it, then that point and $p_{0}$ form an ordinary line, and the algorithm returns it. Next, it finds a system of $O(n)$ lines through pairs of given points that belong to consecutive groups and are extreme within their groups (one closest to $p_{0}$ , and one farthest), and chooses from this system the line $\ell _{1}$ (through two given points $p_{1}$ and $p_{2}$ ) whose crossing point with $\ell _{0}$ is as close to $p_{0}$ as possible. The authors prove that $\ell _{1}$ must be ordinary, for if not then there would exist an ordinary line between one of its points and $p_{0}$ , a case that has already been ruled out.^[7]

The number of ordinary lines

The two known examples of point sets with fewer than n/2 ordinary lines.

While the Sylvester–Gallai theorem states that an arrangement of points, not all collinear, must determine an ordinary line, it does not say how many must be determined. Let t₂(n) be the minimum number of ordinary lines determined over every set of n non-collinear points. Melchior's proof showed that t₂(n) ≥ 3. de Bruijn and Erdős (1948) raised the question of whether t₂(n) approaches infinity with n. Theodore Motzkin (1951) confirmed that it does by proving that $t_{2}\geq {\sqrt {n}}$ . Gabriel Dirac (1951) conjectured that $t_{2}\geq \lfloor n/2\rfloor$ , for all values of n, a conjecture that still stands as of 2013^[update]. This is often referred to as the Dirac–Motzkin conjecture; see for example Brass, Moser & Pach (2005, p. 304). Kelly & Moser (1958) proved that t₂(n) ≥ 3n/7.

Example of Böröczky's (even) configuration with 10 points determining 5 ordinary lines.

Dirac's conjectured lower bound is asymptotically the best possible, since there is a proven matching upper bound t₂(n) ≤ n/2 for even n greater than four. The construction, due to Károly Böröczky, that achieves this bound consists of the vertices of a regular m-gon in the real projective plane and another m points (thus, n = 2m) on the line at infinity corresponding to each of the directions determined by pairs of vertices; although there are m(m − 1)/2 pairs, they determine only m distinct directions. This arrangement has only m ordinary lines, namely those that connect a vertex v with the point at infinity corresponding to the line determined by v's two neighboring vertices. Note that, as with any finite configuration in the real projective plane, this construction can be perturbed so that all points are finite, without changing the number of ordinary lines.^[8]

For odd n, only two examples are known that match Dirac's lower bound conjecture, that is, with t₂(n) = (n − 1)/2. One example, by Kelly & Moser (1958), consists of the vertices, edge midpoints, and centroid of an equilateral triangle; these seven points determine only three ordinary lines. The configuration in which these three ordinary lines are replaced by a single line cannot be realized in the Euclidean plane, but forms a finite projective space known as the Fano plane. Because of this connection, the Kelly–Moser example has also been called the non-Fano configuration.^[9] The other counterexample, due to McKee,^[8] consists of two regular pentagons joined edge-to-edge together with the midpoint of the shared edge and four points on the line at infinity in the projective plane; these 13 points have among them 6 ordinary lines. Modifications of Böröczky's construction lead to sets of odd numbers of points with $3\lfloor n/4\rfloor$ ordinary lines.^[10]

Csima & Sawyer (1993) proved that $t_{2}(n)\geq \lceil 6n/13\rceil$ except when n is seven. Asymptotically, this formula is already 12/13 ~ 92.3% of the proven n/2 upper bound. The n = 7 case is an exception because otherwise the Kelly–Moser construction would be a counterexample; their construction shows that t₂(7) ≤ 3. However, were the Csima–Sawyer bound valid for n = 7, it would claim that t₂(7) ≥ 4.

A closely related result is Beck's theorem, stating a tradeoff between the number of lines with few points and the number of points on a single line.

Ben Green and Terence Tao showed that for all sufficiently large point sets, n > n₀, the number of ordinary lines is indeed at least n/2. Furthermore, when n is odd, the number of ordinary lines is at least 3n/4 − C, for some constant C. Thus, the constructions of Böröczky for even and odd (discussed above) are best possible.^[11]

The number of connecting lines

As Paul Erdős observed, the Sylvester–Gallai theorem immediately implies that any set of n points that are not collinear determines at least n different lines. This result is known as the De Bruijn–Erdős theorem. As a base case, the result is clearly true for n = 3. For any larger value of n, the result can be reduced from n points to n − 1 points, by deleting an ordinary line and one of the two points on it (taking care not to delete a point for which the remaining subset would lie on a single line). Thus, it follows by mathematical induction. The example of a near-pencil, a set of n − 1 collinear points together with one additional point that is not on the same line as the other points, shows that this bound is tight.^[10]

Generalizations

The Sylvester–Gallai theorem does not directly apply to sets of infinitely many points or to geometries over finite fields. The set of all points in the plane is an infinite set with no ordinary lines, for instance, and the set of all points in a finite geometry such as the Fano plane also has no ordinary lines.^[4]

For geometries defined using complex number or quaternion coordinates, however, the situation is more complicated. For instance, in the complex projective plane there exists a configuration of nine points, Hesse's configuration (the inflection points of a cubic curve), in which every line is non-ordinary, violating the Sylvester–Gallai theorem. Such a configuration is known as a Sylvester–Gallai configuration, and it cannot be realized by points and lines of the Euclidean plane. Another way of stating the Sylvester–Gallai theorem is that whenever the points of a Sylvester–Gallai configuration are embedded into a Euclidean space, preserving colinearities, the points must all lie on a single line, and the example of the Hesse configuration shows that this is false for the complex projective plane. However, Kelly (1986) proved a complex-number analogue of the Sylvester–Gallai theorem: whenever the points of a Sylvester–Gallai configuration are embedded into a complex projective space, the points must all lie in a two-dimensional subspace. Similarly, Elkies, Pretorius & Swanepoel (2006) showed that whenever they are embedded into a space defined over the quaternions, they must lie in a three-dimensional subspace.

Every set of points in the plane, and the lines connecting them, may be abstracted as the elements and flats of a rank-3 oriented matroid. In this context, the result of Kelly & Moser (1958) lower-bounding the number of ordinary lines can be generalized to oriented matroids: every rank-3 oriented matroid with n elements has at least 3n/7 two-point lines, or equivalently every rank-3 matroid with fewer two-point lines must be non-orientable.^[12] A matroid without any two-point lines is called a Sylvester matroid. Relatedly, the Kelly–Moser configuration with seven points and only three ordinary lines forms one of the forbidden minors for GF(4)-representable matroids.^[9]

Notes

^ Elkies, Pretorius & Swanepoel (2006).
^ ^a ^b Borwein & Moser (1990).
^ Steinberg et al. (1944); Erdős (1982).
^ ^a ^b ^c ^d ^e ^f Aigner & Ziegler (2018).
^ ^a ^b ^c Melchior (1941).
^ Aigner & Ziegler (2018, p. 92); Steenrod's proof was briefly summarized in Steinberg et al. (1944).
^ Mukhopadhyay & Greene (2007).
^ ^a ^b Crowe & McKee (1968).
^ ^a ^b Geelen, Gerards & Kapoor (2000).
^ ^a ^b Pach & Sharir (2009)
^ Green & Tao (2013).
^ Björner et al. (1993).

References

Aigner, Martin; Ziegler, Günter M. (2018), "Chapter 11. Lines in the plane and decomposition of graphs", Proofs from THE BOOK (6th ed.), Springer, Theorem 1, pp. 77–78, doi:10.1007/978-3-662-57265-8_11, ISBN 978-3-662-57265-8
Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter M. (1993), Oriented matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge: Cambridge University Press, p. 273, ISBN 0-521-41836-4, MR 1226888
Borwein, P.; Moser, W. O. J. (1990), "A survey of Sylvester's problem and its generalizations", Aequationes Mathematicae, 40 (1): 111–135, doi:10.1007/BF02112289
Brass, Peter; Moser, William; Pach, János (2005), Research problems in discrete geometry, Berlin: Springer, ISBN 0-387-23815-8
de Bruijn, N. G.; Erdős, P. (1948), "A combinatioral [sic] problem" (PDF), Indagationes Mathematicae, 10: 421–423
Coxeter, H. S. M. (1969), Introduction to Geometry, New York: John Wiley & Sons, pp. 181–182, ISBN 0-471-50458-0
Crowe, D. W.; McKee, T. A. (1968), "Sylvester's problem on collinear points", Mathematics Magazine, 41 (1): 30–34, doi:10.2307/2687957, JSTOR 2687957
Csima, J.; Sawyer, E. (1993), "There exist 6n/13 ordinary points", Discrete & Computational Geometry, 9: 187–202, doi:10.1007/BF02189318
Dirac, G. (1951), "Collinearity properties of sets of points", Quart. J. Math., 2: 221–227, Bibcode:1951QJMat...2..221D, doi:10.1093/qmath/2.1.221
Edelsbrunner, Herbert; Guibas, Leonidas J. (1989), "Topologically sweeping an arrangement", J. Comput. System Sci., 38 (1): 165–194, doi:10.1016/0022-0000(89)90038-X, MR 0990055
Elkies, Noam; Pretorius, Lou M.; Swanepoel, Konrad J. (2006), "Sylvester–Gallai theorems for complex numbers and quaternions", Discrete and Computational Geometry, 35 (3): 361–373, arXiv:math/0403023, doi:10.1007/s00454-005-1226-7, MR 2202107
Erdős, P. (1943), "Problem 4065", Problems for solution: 4065–4069, American Mathematical Monthly, 50 (1): 65–66, doi:10.2307/2304011, JSTOR 2304011
Erdős, P. (1982), "Personal reminiscences and remarks on the mathematical work of Tibor Gallai" (PDF), Combinatorica, 2 (3): 207–212, doi:10.1007/BF02579228
Geelen, J. F.; Gerards, A. M. H.; Kapoor, A. (2000), "The excluded minors for GF(4)-representable matroids" (PDF), Journal of Combinatorial Theory, Series B, 79 (2): 247–299, doi:10.1006/jctb.2000.1963, MR 1769191, archived from the original (PDF) on 2010-09-24
Green, Ben; Tao, Terence (2013), "On sets defining few ordinary lines", Discrete & Computational Geometry, 50 (2): 409–468, arXiv:1208.4714, doi:10.1007/s00454-013-9518-9, MR 3090525
Kelly, L. M. (1986), "A resolution of the Sylvester–Gallai problem of J. P. Serre", Discrete and Computational Geometry, 1 (2): 101–104, doi:10.1007/BF02187687
Kelly, L. M.; Moser, W. O. J. (1958), "On the number of ordinary lines determined by n points", Can. J. Math., 10: 210–219, doi:10.4153/CJM-1958-024-6
Mandelkern, Mark (2016), "A constructive version of the Sylvester–Gallai theorem", Acta Mathematica Hungarica, 150: 121–130, doi:10.1007/s10474-016-0624-z
Melchior, E. (1941), "Über Vielseite der Projektive Ebene", Deutsche Mathematik, 5: 461–475
Motzkin, Th. (1951), "The lines and planes connecting the points of a finite set", Transactions of the American Mathematical Society, 70 (3): 451–464, doi:10.2307/1990609, JSTOR 1990609
Mukhopadhyay, A.; Agrawal, A.; Hosabettu, R. M. (1997), "On the ordinary line problem in computational geometry", Nordic Journal of Computing, 4 (4): 330–341
Mukhopadhyay, A.; Greene, E. (2007), "The ordinary line problem revisited", Proc. 19th Canadian Conference on Computational Geometry (PDF), pp. 61–64
Pach, János; Sharir, Micha (2009), "Chapter 1. Sylvester–Gallai Problem: The Beginnings of Combinatorial Geometry", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 1–12
Pambuccian, V. (2009), "A reverse analysis of the Sylvester–Gallai theorem", Notre Dame Journal of Formal Logic, 50 (3): 245–260, doi:10.1215/00294527-2009-010
Steinberg, R.; Buck, R. C.; Grünwald, T.; Steenrod, N. E. (1944), "Three point collinearity (solution to problem 4065)", American Mathematical Monthly, 51 (3): 169–171, doi:10.2307/2303021, JSTOR 2303021
Sylvester, J. J. (1893), "Mathematical question 11851", The Educational Times, 46 (383): 156
Woodall, H. J. (1893), "Mathematical question 11851 answered", The Educational Times, 46 (385): 231
Woodall, H. J. (1893), "Mathematical question 11851 answered", Mathematical Questions and Solutions from the Educational Times, 59: 98

External links

Malkevitch, Joseph (2003). "A discrete geometrical gem". AMS Feature Column. American Mathematical Society. Archived from the original on 2006-10-10.
Weisstein, Eric W. "Ordinary Line". MathWorld.
Proof presentation by Terence Tao at the 2013 Minerva Lectures

[FOOTNOTEElkiesPretoriusSwanepoel2006-1] Elkies, Pretorius & Swanepoel (2006).

[FOOTNOTEBorweinMoser1990-2] Borwein & Moser (1990).

[stein44-3] Steinberg et al. (1944); Erdős (1982).

[FOOTNOTEAignerZiegler2018-4] ^ ^a ^b ^c ^d ^e ^f Aigner & Ziegler (2018).

[FOOTNOTEMelchior1941-5] Melchior (1941).

[6] Aigner & Ziegler (2018, p. 92); Steenrod's proof was briefly summarized in Steinberg et al. (1944).

[FOOTNOTEMukhopadhyayGreene2007-7] Mukhopadhyay & Greene (2007).

[CM68-8] Crowe & McKee (1968).

[ggk00-9] Geelen, Gerards & Kapoor (2000).

[ps09-10] Pach & Sharir (2009)

[FOOTNOTEGreenTao2013-11] Green & Tao (2013).

[12] Björner et al. (1993).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]