Sylvester–Gallai theorem

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

All the points are collinear; or
There is a line which contains exactly two of the points.

This theorem was posed as a problem by James Joseph Sylvester (1893), posed again independently by Paul Erdős (1943), and solved by Tibor Gallai in 1944^[1], although a proof of an equivalent statement had already been given by Melchior (1940). The Sylvester-Gallai theorem does not apply to sets of infinitely many points: consider for instance the lattice of integer points. A line that contains exactly two of a set of points is known as an ordinary line; an algorithm of Mukhopadhyay et al (1997) can be used to find an ordinary line in a set of n points in time O(n log n).

Projective duality

The question of the existence of an ordinary line can also be posed for points in the real projective plane instead of the Euclidean plane. This provides no additional generality, as any finite set of projective points can be transformed into a Euclidean point set preserving all ordinary lines, but the projective viewpoint allows certain configurations to be described more easily; for instance, McKee's configuration, described below, is most naturally viewed in projective geometry.

By projective duality, the existence of an ordinary line in a set of non-collinear points in the projective plane is equivalent to the existence of an ordinary point in a set of lines that do not all pass through a common point, where we define an ordinary point to be the point of intersection of exactly two lines. Melchior (1940), prior to Gallai's proof, showed that any such set of lines has at least three ordinary points, by using the Euler characteristic to show that any arrangement of lines has at least three vertices of degree four.

Proof of the Sylvester–Gallai theorem

For a description of Gallai's original proof see e.g. Borwein and Moser (1990). The proof below is instead due to Kelly.

We shall use the method of infinite descent. Suppose we have a finite number of points which are not collinear (in particular, we must have at least three points). Define a connecting line to be a line which contains at least two points in the collection; we then have to show that at least one connecting line contains exactly two points.

Let l be a connecting line. Since the points are not collinear, there is at least one point P which is not on l. If l contains exactly two points, we are done. Otherwise, we know that l contains at least three points, say A, B, and C. We may assume without loss of generality that B lies between A and C. Since the angles $\angle ABP$ and $\angle CBP$ add up to 180 degrees, they cannot both be obtuse; without loss of generality we may assume $\angle ABP$ is not obtuse (i.e. either acute or right-angled).

Now let m be the line connecting C and P. Then m is a connecting line which does not contain B. Furthermore, the distance between B and m is less than the distance between P and l.

To summarize so far, we have started with a connecting line l and a point P not on this line, and observed that either l contains exactly two points, or that there exists another connecting line m and a point B not on that line such that the distance between B and m is less than the distance between P and l. In the latter case, we simply repeat the argument again, but with P and l replaced by B and m. We cannot continue indefinitely because we would obtain an infinite decreasing sequence of distances, but the number of possible distances between points and connecting lines is finite because the original set was assumed to be finite. Thus we must eventually obtain a connecting line with exactly two points only.

Generalizations of the Sylvester–Gallai theorem

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

While the Sylvester–Gallai theorem tells us that there must exist at least one line containing exactly two points, an arrangement with exactly one line containing exactly two points has not yet been found. This led Dirac (1951) to conjecture that for any collection of $n$ points, not all collinear, there exist at least n⁄2 lines containing exactly two points.

As of 2006, only two counterexamples to Dirac's conjecture are known. One, by Kelly and Moser (1958), consists of the vertices, 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 geometry known as the Fano plane. The other counterexample, due to McKee (Crowe and McKee 1968), 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. McKee's configuration can be distorted so that all of its points lie within the usual Euclidean plane.

A weaker version of Dirac's conjecture, proven by Csima and Sawyer in 1993, states that any set of n points has at least $\lceil {\frac {6n}{13}}\rceil$ ordinary lines. 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.

Notes

^ Gallai's proof was first published as part of a collection of proofs by several other authors (Steinberg et al 1944). However, it has priority, as the solution editors note that it was submitted together with Erdős' statement of the problem.

References

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.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Crowe, D. W.; McKee, T. A. (1968). "Sylvester's problem on collinear points". Mathematics Magazine. 41 (1): 30–34.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Csima, J.; Sawyer, E. (1993). "There exist 6n/13 ordinary points". Discrete & Computational Geometry. 9: 187–202. doi:10.1007/BF02189318.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Dirac, G. (1951). "Collinearity properties of sets of points". Quart. J. Math. 2: 221–227.

Erdős, P. (1943). "Problem 4065". American Mathematical Monthly. 50: 65.

Kelly, L. M.; Moser, W. O. J. (1958). "On the number of ordinary lines determined by n points". Canad. J. Math. 10: 210–219.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Melchior, E. (1940). "Über Vielseite der projektiven Ebene". Deutsche Math. 5: 461–475.

Mukhopadhyay, A.; Agrawal, A.; Hosabettu, R. M. (1997). "On the ordinary line problem in computational geometry". Nordic Journal of Computing. 4 (4): 330–341.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Steinberg, R.; Buck, R. C.; Grünwald, T. (Tibor Gallai); Steenrod, N. E. (1944). "Three point collinearity (solution to problem 4065)". American Mathematical Monthly. 51: 169–171.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Sylvester, J. J. (1893). "Mathematical question 11851". Educational Times. 59: 98.

External links

Malkevitch, Joseph (2003). "A discrete geometrical gem".

Weisstein, Eric W. "Ordinary Line". MathWorld.

[1] Gallai's proof was first published as part of a collection of proofs by several other authors (Steinberg et al 1944). However, it has priority, as the solution editors note that it was submitted together with Erdős' statement of the problem.

[1]