From:larsen@mace.princeton.edu (Michael Larsen)Newsgroups:sci.mathSubject:Re: Request: summary of certain old topics, and two questionsDate:20 Nov 90 13:00:34 GMTOrganization: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.mathSubject:Re: Request: summary of certain old topics, and two questionsDate:20 Nov 90 16:33:34 GMTOrganization: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.mathSubject:Re: Sylvester [was Re: summary...]Date:21 Nov 90 20:05:00 GMTReply-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