Talk:Sylvester–Gallai theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Geometry

Trivial proof[edit]

One should add the trivial Kelly proof using the minimality of the distance between one point and a line which does not contain it.

Huh? The Kelly proof is in the section "Proof of the Sylvester–Gallai theorem". But I think it's longer than the projective duality one, so I don't know why you call it trivial. —David Eppstein 14:51, 24 April 2007 (UTC)

The picture was the right diagram for the Kelly proof, but the words made no sense; now modified. Also I think I would use the word "gem", not "trivial". Just saying.— Preceding unsigned comment added by 18.250.7.232 (talk) 20:44, March 12, 2008

Redirect[edit]

I don't know if Sylvester's matrix theorem is also by the same Sylvester, but since Sylvester's theorem redirects here, I'm adding a disambiguation link Cai 10:21, 24 April 2007 (UTC)

Proof[edit]

Uh...I'm going to leave myself logged out for this comment since, based on the past editors of this article, I feel sure it will turn out to highly embarrassing. That said, does the proof here make any sense? I haven't done the details but the basic structure is giving me pause. We assume for the sake of contradiction that the points aren't collinear, do some stuff, and get to a contradiction. So...what? We conclude that any set of points is collinear? Assuming that the details given are correct, it seems like the structure should be, "Let S be a set of points which aren't all collinear and assume for the sake of contradiction that every connecting line of S has more than two points. Since S is not collinear, there exist pairs (P,l) where l is a connecting line of S and P is a point in S at positive distance from l. Let (P,l) be such a pair with minimum distance." Now l has at least three points from S and we proceed as before, arriving at a contradiction that tells us that S must have a connecting line with only two points. Yes? - 67.70.227.10 (talk) 16:39, 16 June 2009 (UTC)

I think you've got the gist of the proof. I agree that the wording needs to be improved. It's not very clear. Here are the key points of the proof:
  • Assume all determined lines pass through three points.
  • Obviously, there are only a finite number of point-line pairs.
  • One of these pairs must determine the minimum perpendicular distance from point to line.
  • Using this "minimal" pair, we can construct another point-line pair that determines a closer distance.
  • This contradicts our assumption that we had the "closest" pair. Therefore, one of our assumptions must be false, i.e., the assumption that all determined lines pass through three points.
One may also see this as an "algorithmic proof". Using Kelly's construction to obtain successively "closer" point-line pairs, one will progress through a sequence of distinct point-line pairs. ("Distinct" b/c the distance always decreases.) This sequence must eventually terminate at an ordinary line. Jwesley78 02:27, 30 December 2009 (UTC)

Melchior[edit]

A couple comments:

  • It would not take much more work to give Melchior's full derivation. If I get time I might try to add it.
  • The section on "Generalizations of the Sylvester–Gallai theorem" seems inconsequential. Perhaps it should be removed?

Jwesley78 02:01, 29 December 2009 (UTC)

Is it appropriate to give the proof here?[edit]

Wikipedia is not a textbook, so proofs are generally not appropriate unless they have substantial historical interest — and, even then, it generally suffices to outline the main ideas of the proof, without the details one would normally require in a book or journal paper. All the best, --Jorge Stolfi (talk) 01:51, 30 December 2009 (UTC)

I would disagree. I think they are appropriate for many articles, especially if the proof does not require significant background knowledge. For comparison, here are a few other articles that contains proofs:
Jwesley78 02:07, 30 December 2009 (UTC)
Well, examples do not prove anything: Wikipedia should be written in good English, but I can easily find ten articles with gross grammatical errors in them. But, more to the point: in two of those examples, at least (Euler's characteristic and the Pythagorean theorem), the *original* proofs have *historical* interest; and therefore it is those proofs which should be described in the articles. Modern proofs such as found in textbooks, even for important theorems, are inappropriate detail and should be omitted. Moreover, a new proof written specifically for Wikipedia is also half a step beyond the line of "original research", and therefore doubly inappropriate.
Compare with other sciences. Articles like ethanol, Mars, paramecium contain only the facts, with hardly a hint of the experimental data and calculations that led to them. They will only mention *historical* experiments and calculations, such as Michelson's, Lavoisier's, Mendel's and so on; but even then in a very summarized way. Why mathemtical articles shoudl be different?
Finally, while a theorem is in a sense an "absolute" thing, a proof is only an arbitrary path or reasoning that can be used to get there from other accepted facts. Which facts are axioms and which are theorems is merely a matter of choice. Indeed, a proof of a complex theorem requires the choice of a set of axioms and a longish chain of lemmas; these things can be done in a book or in a course syllabus, but not in an encyclopedia article, which is meant to be read and edited on its own.
Finally, proofs are useful for two things only: in journals and monographs, to convince skeptical fellow mathematicians that a claim is true; and in textbooks, to teach students how to "think mathematically". Since Wikipedia does not accept original research, the first use is automatically out. As for the second use, readers who are students already have plenty of proofs in their textbooks; and other readers will have no use for the proof. Either way, proofs are only clutter standing in the way of the facts.
I will not fight over this issue, but I beg you to reconsider. All the best, --Jorge Stolfi (talk) 14:17, 30 December 2009 (UTC)

Dirac's conjecture[edit]

The following invisible comment was attached to the statement of Dirac's conjecture:

Dirac's original paper used brackets around the n/2. (This generally implies "take the integer part".) Thus, the "counter-examples" below are not truly "counter-examples".

What brackets "generally mean" is irrelevant, the question is what they meant to Dirac. It seems unlikely that they meant "round half-integers up" i.e. "ceiling of", since then the brackets would be superfluous (for integers, tn/2 is equivalent to tn/2). So I would guess that it meant "floor of". In that case the two "counter-examples" should be renamed "examples (with odd n?) where equality holds". All the best, --Jorge Stolfi (talk) 01:58, 30 December 2009 (UTC)

I changed the wording to not call them "counter-examples" to Dirac's conjecture. They are simply examples for which the number of ordinary lines is less than n/2. I'll remove that comment now. Jwesley78 02:09, 30 December 2009 (UTC)
It is better now, good! But we still need to find out what Dirac meant by the brackets, and replace it by the proper notation (ceiling or floor). It is not OK to use Dirac's notation in the article without defining it. All the best, --Jorge Stolfi (talk) 14:24, 30 December 2009 (UTC)
Floor. See Floor and ceiling functions. Kope (talk) 15:21, 30 December 2009 (UTC)

Arrangements with few ordinary lines[edit]

I don't think the construction below is quite right. I've removed it from the article until it can be corrected. I think I'm reading the source correctly, but it might be wrong. The original example apparently comes from Motzkin (1975) in "Sets for which no point lies on many connecting lines." Motzkin's description of the arrangement seems a bit more complicated.

In the projective plane, it is known that for all m. To see this, consider the vertices of a regular m-gon (where ), and note that any pair of vertices of a regular m-gon determines a line pointing in one of only m possible directions. Place a point on each vertex, and another point on the line at infinity corresponding to each of the m directions determined by the vertices. This arrangement of 2m points determine m ordinary lines. The ordinary lines are found by connecting a vertex v with the point on the line at infinity corresponding to the line determined by v's two neighboring vertices. For , a similar construction can be made from the vertices of a regular (m-1)-gon with a point at its center and m points on the line at infinity.[1]

  1. ^ Erdos, Paul; Purdy, G. (1995). "Extremal problems in combinatorial geometry". In R. Graham, M. Grotschel, and L. Lovasz. Handbook of Combinatorics. 1. Elsevier Science. pp. 809–874.  Cite uses deprecated parameter |coauthors= (help)

Jwesley78 05:55, 30 December 2009 (UTC)

I don't see what's wrong with this construction, and have restored it to the article. Can you be more specific about your objections to it, other than that a source that is not cited for it describes a different construction? —David Eppstein (talk) 05:58, 30 December 2009 (UTC)

The problem is the case. (The first case appears correct to me.) I added this example earlier this evening, then after thinking about it, I started to doubt its veracity. I'm working through Motzkin's original paper to see how Erdos/Purdy constructed it from his original. I probably won't be able to finish it this evening. Jwesley78 06:03, 30 December 2009 (UTC)
I think Erdos/Purdy may have had it wrong. It appears to me that the construction is the same whether m is even or odd. Erdos/Purdy say:

If n = 2m = 4k+2, then take a regular 2k-gon and its center, together with 2k+1 points on the line at infinity.

(They used k to step through the members of the family.) The point in the center seems to introduce m/2 ordinary lines (with points at infinity).
It appears to me that the vertices of a regular m-gon with m points at infinity will work whether m is even or odd.
Jwesley78 06:24, 30 December 2009 (UTC)
Ok, it was the even m case that I was looking at and not seeing a problem with, since there's so little detail in the odd case. But I agree there is something fishy with the odd case as written here: there are only m − 1 points on the line at infinity that are crossed by diagonals of the (m − 1)-gon, so where does the mth point on the line at infinity go? Yes, the same construction as in the even case seems to work. —David Eppstein (talk) 06:28, 30 December 2009 (UTC)

I did a little more research on this. It appears that this configuration was first published by Crowe and McKee in 1968 and credited there to Borocsky. I don't have the "Handbook" with me now, but I believe Erdos/Purdy credited the wrong source (Motzkin 1975) for this. Jwesley78 18:30, 31 December 2009 (UTC)

But that must be the older Böröczky. Böröczky Jr was 4 years old in 1968. Kope (talk) 07:11, 2 January 2010 (UTC)
Oops. I did some searches, saw that there was a mathematician named K. Böröczky, and didn't check more carefully as I should have. —David Eppstein (talk) 07:24, 2 January 2010 (UTC)

Wrong name[edit]

It seems bizarre to call this the "Sylvester-Gallai theorem" when Sylvester merely posed the problem and Gallai's proof was 3 years later than Melchior's. Isn't there any source that calls it "Melchior's theorem"? All the best, --Jorge Stolfi (talk) 09:46, 31 December 2009 (UTC)

The name "Sylvester-Gallai theorem" is well-established in the literature. I've not seen it called anything other than that. I believe Melchior's work was completely independent of Sylvester's/Erdos's question. He was concerned with polygrams (i.e. "Vielseit"). Coxeter's review of the paper is here. I suspect that the connection between Erdos's question and Melchior's result was not found until years after the name was already well-established. An interesting historical note (that my advisor told me) is that it is suspected that Melchior died in WWII during the carpet bombings of Munich, as there is no record of him after the war. Jwesley78 15:25, 31 December 2009 (UTC)
In modern terminology polygrams are called arrangements of lines. From Coxeter's review it seems that Melchior was primarily trying to classify simplicial arrangements. —David Eppstein (talk) 17:19, 31 December 2009 (UTC)
Similar things happen, see, e.g., Hahn–Banach theorem.Kope (talk) 15:12, 1 January 2010 (UTC)

Reference style[edit]

Hi David, I see that you reverted all the references to the style Author(Year). I really can't see the advantage of that style in Wikipedia. Among many other disadvantages, you lose the links from refs back to the text. Sigh... All the best, --Jorge Stolfi (talk) 22:26, 1 January 2010 (UTC)

I used Author (year) only for references that were already in the format "In year Author ...". That is, the referencing style only formalizes what was already in the text. But if the text includes a clear statement like this of which paper is being referred to, what is the point of also having a footnote pointing to the same paper? —David Eppstein (talk) 00:26, 2 January 2010 (UTC)

Affine form of Melchior's theorem?[edit]

The article says that formulating the Sylvester–Gallai theorem projectively adds no generality. It might say more precisely that the affine form is equivalent to the projective form: on one hand any affine configuration of points can be viewed as a projective configuration with no points at infinity, so assuming the projective theorem there will be a projective ordinary line which obviously is not the line at infinity and the affine theorem holds; conversely for any finite projective configuration of points one can choose a line not meeting any of them as line at infinity, and the affine theorem will imply the projective theorem.

However as far as I can see this does not apply to the dual version. An affine form of the dual statement "any finite arrangement of lines in affine space that are neither all parallel nor all concurrent in a same point must have an ordinary point" would imply the projective form, again by choosing as the line at infinity any line not passing through any intersection point of the arrangement. However assuming the projective form (which Melchior proved), it appears more problematic to obtain the stated affine form. Indeed viewing an affine arrangement as a projective one, one obtains at least three ordinary projective points; however it seems conceivable that all those points lie on the line at infinity, corresponding only to pairs of parallel lines, but not to affine ordinary points. Is there a complement to Melchior's theorem that says there are three non collinear ordinary points? This would imply (and be equivalent to) the affine form of the statement. Marc van Leeuwen (talk) 14:37, 9 May 2012 (UTC)

I don't see the problem; if all intersections are on the line at infinity then the configuration is simply a family of "parallel" lines (in the affine sense) sharing a single intersection point on the line at infinity, contrary to any S-G hypothesis. Assume otherwise: take lines A and B from two distinct intersection points on the line at infinity; lines A and B must intersect at a point not on the line at infinity.
If it helps, I know of a couple papers by J. Lenchner concerning the Sylvester-Gallai in Euclidean and Hyperbolic space. See "On the dual and sharpened dual of Sylvester's Theorem in the plane": http://www.research.ibm.com/people/l/lenchner/publications.html Justin W Smith (talk) 17:20, 21 October 2012 (UTC)
Maybe you don't see the problem, but in any case your argument does not answer it. Consider a set of affine lines that are neither all parallel nor all concurrent in a single point. We want to find an ordinary point in the affine plane: point where just two of those lines intersect. We may consider it as a projective configuration, in which case Melchior hands us no less than three ordinary points. But these might be on the line at infinity, giving each just a simple pair of parallel lines, and those don't count. You say take lines A and B from two distinct intersection points on the line at infinity; lines A and B must intersect at a point not on the line at infinity. Fair enough, but who says that intersection point is ordinary? Indeed, while I think it is impossible to find an example where all three ordinary points are at infinity, one can arrange for two of them to be at infinity, and for all lines through those two points to only intersect (elsewhere) in non-ordinary affine points. By the way I did get that same reference as answer to a StackExchange question, and I think it does settle my question, but non-trivially (it is theorem 7. of the paper you referred to; it's proof is certainly not trivial). Marc van Leeuwen (talk) 10:01, 22 October 2012 (UTC)
Hmmm... I think you're saying something like: "Perhaps, there's an arrangement of lines in the projective plane in which all of the ordinary intersections occur on a single line. (This obviously does not violate Melchior's inequality.) So, if we make that line (with all of the ordinary intersections) the line at infinity (and remove it), then there exists an affine arrangement without a ordinary point! Therefore, the "projective" form of the theorem does not imply the affine form!" Is this your question, or close to it? Justin W Smith (talk) 01:41, 23 October 2012 (UTC)

1941(?) Melchior paper[edit]

A few years ago I located the Melchior paper in the UC library and scanned it: Uber Vielseite der projektiven Ebene. From what I can tell, the article itself says that it's from "Volume 5, Issue 6", but I don't see the year printed therein. Justin W Smith (talk) 17:36, 21 October 2012 (UTC)

The UC library catalog says that "Volume 5" was published in 1940. (So if anyone wishes to undo my recent edit, I wouldn't protest; there appear to be conflicting sources.) Justin W Smith (talk) 17:49, 21 October 2012 (UTC)

Redirect from "Sylvester's Problem"[edit]

Seems to me that "Sylvester's Problem" would be more appropriately applied to the famous four point problem. That problem doesn't seem to be an article in Wikipedia.