Skip to Main Content

A Discrete Geometrical Gem

Feature Column Archive

2. Planar point configurations

Many people first learn about Sylvester's Problem (or the Sylvester-Gallai Theorem and sometimes, the Gallai-Sylvester Theorem) from H.S.M. Coxeter's influential book An Introduction to Geometry.
 

Photo of H.S.M. Coxeter


This book, whose second edition of 1969 is the better known version, attempted to revitalize an interest in geometry. Geometry is a subject that unfortunately, despite its importance within mathematics, does not seem to attract as many people with mathematical talent as one might expect, in light of the fertileness of its problems and the many easy-to-state problems that still are unanswered.

In the configuration of points below we start with 6 points and note that some pairs of the points have the property that they determine a line which contains some other point of the original 6.
 



Configuration of 6 points and connecting lines


Six points will determine a maximum of 15 lines (for n points, the number would be n(n-1)/2 lines); but since some of the lines may contain more than two points, there may be fewer than 15 lines determined by 6 points. Lines determined by points of a specified point set are known asconnecting lines of the point set. In this configuration we have A, B, and C lying on a single line and F, E, and C lying on a single line. Can you locate the additional line with 3 points on it? All remaining lines in the diagram (not drawn) have exactly two points on the lines. Diagrams of point-line configurations traditionally often omit lines with exactly two points, showing only those lines which have more than two points, since this convention resolves the case of a "close call" as to whether or not a point X of a configuration is on a line determined by another pair of points in the configuration.

From the way that Sylvester's problem is stated it would not appear that the concept of distance (metric) would have to enter into the solution. Yet the proof that Coxeter (1907-2003) gives, due to Leroy Kelly, involves distance ideas. One easily sees why Coxeter gives Kelly's proof; it's a gem. Yet Coxeter comments on the idea of using distance in the proof: "It is like using a sledge hammer to crack an almond."

Suppose we have a finite set of points P not all on a line. Consider the set L of all the lines that are determined by pairs of points in P. Note that some pairs of points in P will determine the same line l in L because these points lie on l. Now for each point p in P and each line l in L, with the property that p is not a point of l, consider the point-line pair, (p, l). Note that because we know that P is a finite set, L will also be a finite set, so that the number of pairs (p, l) is also finite. For each of the pairs (p, l) compute the distance from the point p to the line l. Recall that computing the distance between a point and a line means computing the length of the unique perpendicular segment from the point to the line. Since we have only a finite number of calculations to make, we can find that pair (p*, l*) for which the distance is a minimum. We now show why it must be that the linel* has exactly two points of P on it.

Suppose, on the contrary, that l* has three points of P on it. Let us denote by q the point on l* which is closest to the point p*. (The line through p* and q,  p*q, is perpendicular to l*.) Now, of the three points of P on l*, two of them must be on the same side of q (or a point of the three is q). Label these points r and s and choose the names so that r lies between q and s (note that it is possible that r and q coincide). We can draw the diagram below associated with the situation.
 


Diagram illustrating Kelly's proof of the Sylvester-Gallai Theorem
 

The distance from r (a point of P) to the line p*s (a line of L) is shorter than the distance from q to p*! However, this can not be true since we chose p* and l* so that among all pairs (p, l) they achieved a minimum distance. This contradiction means that the assumption of having more than two points onl* can not hold.

There are other clever proofs, including the proof of Gallai, and they all use the fact that one is dealing with a finite point set in an ingenious way. (The analog of Sylvester-Gallai for an infinite set need not hold.) This can take the form of looking at the measure of some angle or the area of some triangle and using finiteness to be certain that there is an angle or triangle of minimal "size." Using a bit of geometric reasoning and this object which has a nice minimality property, one reaches a contradiction. Kelly's proof above is in this same mold.


  1. Introduction
  2. Planar point configurations
  3. Some ramifications of the Sylvester-Gallai Theorem
  4. Generalizations and adding color
  5. References