Sylvester–Gallai theorem

From Wikipedia, the free encyclopedia

"Sylvester's theorem in plane geometry" redirects here. For Sylvester's theorem in number theory, see Bertrand's postulate.

"Sylvester's theorem" redirects here. For Sylvester's theorem about matrices, see Sylvester's formula.

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).

1 Projective duality
2 Proof of the Sylvester–Gallai theorem
- 2.1 Coxeter's Proof of the Sylvester–Gallai theorem in Ordered Geometry
3 Generalizations of the Sylvester–Gallai theorem
4 Notes
5 References
6 External links

[edit] 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 finite set of lines in the projective plane 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.

[edit] 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.

Suppose for contradiction that we have a finite set of points not all collinear. Call it S. Define a connecting line to be a line which contains at least two points in the collection. Let (P,l) be the point and connecting line that are the smallest positive distance apart among all point-line pairs.

The line l goes through at least three points of S. Drop a perpendicular from P to l; there must be 2 points on the same side of the perpendicular (one might be exactly on the intersection of the perpendicular with l). Call the point closer to the perpendicular B, and the farther point C. Draw the line m connecting P to C. Then the distance from B to m is smaller than the distance from P to l! One way to see this is to notice that the right triangle with hypotenuse BC is similar and contained in the right triangle with hypotenuse PC.

Thus there cannot be a smallest positive distance between point-line pairs -- every point must be distance 0 from every line, or in other words, every point must lie on the same line.

[edit] Coxeter's Proof of the Sylvester–Gallai theorem in Ordered Geometry

Coxeter gave a proof of the Sylvester–Gallai theorem within ordered geometry^[2].

[edit] 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 ⁿ⁄₂ 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 lines in the projective plane has at least $\left\lceil \frac{6n}{13} \right\rceil$ ordinary points. 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.

[edit] 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.
^ Coxeter, H. S. M. (1969). Introduction to Geometry. New York: John Wiley & Sons, p. 181-182. ISBN 0471504580.

[edit] 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.

Crowe, D. W.; McKee, T. A. (1968). "Sylvester's problem on collinear points". Mathematics Magazine 41 (1): 30–34.

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. doi:10.1093/qmath/2.1.221.

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.

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.