From:           larsen@mace.princeton.edu (Michael Larsen)
Newsgroups:     sci.math
Subject:        Re: Request: summary of certain old topics, and two questions
Date:           20 Nov 90 13:00:34 GMT
Organization:   Princeton University, Princeton, New Jersey

In article <9226@mirsa.inria.fr> abbott@mirsa.inria.fr writes:
>
>Find an easy(?) proof [or counter-example]:
>let S be a set of points in the Euclidean plane such that
>for all x in S and for all y in S-{x} there is z in S-{x,y} collinear with x&y.
>==> S is an infinite set.

This is a semi-classical problem.  I think it goes under the name of
Sylvester's theorem.  My favorite proof was discovered by
Noam Elkies, a sometime contributor to this newsgroup, when he was 13.
(I was working at the math program which he was attending; needless to say, we
were astounded.)

The proof is as follows:  This is obviously a question of projective geometry,
so we may dualize (switch lines and points).  So the problem is this:
Given a finite collection of lines in the plane, show that there is an
intersection point at which exactly two meet.  Now remove a line at
infinity which is not in the collection, and return to the affine plane.
Consider the triangle ABC of smallest area bounded by three of these lines.  
If there is a tie, we fix an origin and choose a minimal triangle whose centroid
is as far as possible from that origin.

Since at least 3 lines meet at each point A, B, C, we can find
lines L, M, and N passing through A, B, and C respectively, and not equal
to AB, BC, or CA.  If L and M meet at X, M and N at Y, and N and L at Z,
triangles XBC, AYC, and ABZ have area greater than or equal to that of
ABC.  But it is easy to show that if you divided a triangle XYZ into
4 parts by choosing a point on each side and connecting, the area of the
center triangle is greater than or equal to the largest of the corner triangles,
with equality if and only if all three points are midpoints.
Therefore, XBC, AYC, ABZ, and ABC are all congruent, and one of the three outer
triangles has a midpoint further from the origin than ABC.  The contradiction
proves the theorem.

						-Michael Larsen

From:           tycchow@phoenix.Princeton.EDU (Timothy Yi-chung Chow)
Newsgroups:     sci.math
Subject:        Re: Request: summary of certain old topics, and two questions
Date:           20 Nov 90 16:33:34 GMT
Organization:   None.  This saves me from writing a disclaimer.

In article <4171@idunno.Princeton.EDU> larsen@mace.princeton.edu (Michael Larsen) writes:
>In article <9226@mirsa.inria.fr> abbott@mirsa.inria.fr writes:
>>
>>Find an easy(?) proof [or counter-example]:
>>let S be a set of points in the Euclidean plane such that
>>for all x in S and for all y in S-{x} there is z in S-{x,y} collinear
>>with x&y.
>>==> S is an infinite set.
>
>This is a semi-classical problem.  I think it goes under the name of
>Sylvester's theorem.  My favorite proof was discovered by
>Noam Elkies, a sometime contributor to this newsgroup, when he was 13.
>(I was working at the math program which he was attending; needless to say, we
>were astounded.)

An even nicer (in my opinion) proof is one I heard from Erdos.  It is
not Erdos' proof, but I forget who he attributed it to.  In fact, Erdos
admitted that he had thought about the problem for a while but failed to
see a solution.

First of all, a technicality: there is an obvious counterexample, namely
of three or more points all in a straight line.  However, if we require
that not all the points of S are in a straight line, then the statement
is true.

Suppose S is finite.  Let L be the set of all lines that contain at
least two points of S.  For any line l and any point p, let d(l,p) be
the distance between l and p.  Let D be the set of all distances d(l,p)
as l ranges over all of L and p ranges over all points in S not on l.
Since not all the points in S are on a line, D is nonempty.  Since S is
finite, D is finite, and thus D has a least element d>0.  Take a line
l_0 in L and a point p_0 in S for which this distance is attained.
Drop a perpendicular from p_0 to l_0, meeting at X.  We have this
picture:

                        p_0 .
                            |
                            | d
     _______________________|_______________________  l_0
                            X

Now, since l_0 contains at least three distinct points of S by
hypothesis, either there are two or more points in S to the left of X
or there are two or more points in S to the right of X.  Suppose
without loss of generality that the former holds, and let p_1 and p_2
be two points in S on l_0, with p_2 closer to X.  Inspection of similar
triangles shows that the distance between p_2 and the line in L
determined by p_0 and p_1 is less than d, contradicting the minimality
of d.
--
Tim Chow    tycchow@phoenix.princeton.edu
Nowadays the only unforgivable sins are racism, sexism, homophobia, and bigotry.

From:           elkies@brauer.harvard.edu (Noam Elkies)
Newsgroups:     sci.math
Subject:        Re: Sylvester [was Re: summary...]
Date:           21 Nov 90 20:05:00 GMT
Reply-To:       elkies@zariski.harvard.edu (Noam Elkies)
Organization:   Harvard Math Department

In article <4171@idunno.Princeton.EDU> larsen@mace.princeton.edu (Michael Larsen) writes:
>In article <9226@mirsa.inria.fr> abbott@mirsa.inria.fr writes:
>>
>>Find an easy(?) proof [or counter-example]:
>>let S be a set of [noncollinear] points in the Euclidean plane such that
>>for all x in S and for all y in S-{x} there is z in S-{x,y} collinear with x&y.
>>==> S is an infinite set.
>
>This is a semi-classical problem.  I think it goes under the name of
>Sylvester's theorem.  My favorite proof was discovered by
>Noam Elkies, a sometime contributor to this newsgroup, when he was 13. [...]

I'm afraid I cannot claim credit to this; the proof is contained in
one of Martin Gardner's "Mathematical Games" columns in _Scientific American_,
wherein he introduces projective geometry and duality.  I had certainly read
most of these columns in back copies of _Sci. Am._ by the time I was assigned
Sylvester's problem (not properly "Sylvester's Theorem" since Sylvester
didn't prove it), so my solution was at best a subconscious reconstruction
of that proof.

However, I *can* claim credit to an analogous solution to the corresponding
question over the complex numbers, asked by Serre in 1966 (Problem 5359
in Vol.73 (1966) of the _Amer. Math. Monthly_):  Let S be a finite subset
of *complex* projective 3-dimensional space, such that the line through
any two points of S contains at least a third point of S; show that
all the points of S are coplanar.  (We can no longer conclude collinearity
because there are counterexamples in the complex plane, of which the
simplest is the set of nine inflection points of a nondegenerate cubic.)

This was first proved in 1986 by L.M. Kelly ("A resolution of the Sylvester-
Gallai problem of J.-P. Serre", Discrete Comput. Geom. 1 (1986), 101--104),
using an inequality of Hirzebruch on arrangements of lines (or, dually, of
points) in the complex projective plane.  But Hirzebruch's inequality
requires Miyaoka's inequality on the characteristic classes of a complex
projective 2-fold of general type (specifically the surface obtained
by taking the square roots of the linear forms on CP^2 defining the lines
of the arrangement) --- which seems an outrageously sophisticated tool 
to apply to such a problem.

And indeed it turns out that essentially the same idea which gave "my"
proof in P^2(R) also does it in P^3(C): construct the dual configuration,
throw away a generic plane to get a configuration of planes in the affine
plane C^3, and, assuming that these planes are not coincident, consider
those four non-coincident planes forming a "tetrahedron" of minimal "volume"
(the "volume" is defined as the absolute value of the determinant formed
from the coordinates of the four points of triple intersection of the planes).
Again a contradiction is obtained from tetrahedra formed by other planes
which must go through the lines of intersection of those four planes.
To be sure, the proof is not as immediate as in the real case, but it
is entirely elementary.

Note that the generalization to projective space over an arbitrary field K
won't give rise to any new theorems of this kind:  if K is of characteristic 
zero, any finite arrangement of points and lines over K can be embedded
in complex projective space of the same dimension; and if K is of
positive characteristic, it contains a finite field k, and then
the points of projective space of arbitrary dimension over k
give an obvious counterexmaple.

--Noam D. Elkies (elkies@zariski.harvard.edu)
  Department of Mathematics, Harvard University