Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Sylvester–Gallai Theorem

futilitycloset.com

Post reply on HN
Print view View original

41–50 of 52 posts

Re: The Sylvester–Gallai Theorem

#41

Post by loose-cannon »

fxwin wrote: post #31
Sniffnoy wrote: post #10

Earlier quoted context omitted.

I think what's going on here is that you've misunderstood the theorem's hypothesis. The hypothesis isn't that no three of the points are collinear; rather, it's the weaker statement that there isn't any one single line that all the points lie on. It's true that with your version of the hypothesis the theorem would be trivial; but with the actual hypothesis it is is nontrivial.

> hypothesis I think you meant premise?

The thing that you assume in a theorem is usually called a hypothesis.

Re: The Sylvester–Gallai Theorem

#43

Post by alan-crowe »

Nail2680 wrote: post #8

I might be too stupid to understand why this is interesting and useful. If it helps I am a working physicist, and a lot of pure math is lost on me. I think I followed this, but I don't know why one would care or this would be interesting.

It is interesting to a pure mathematician. Since it is obviously true, one's intuition is that it should have a simple proof. In particular, the obvious induction ought to work.

The base case is n=2. The line joining them passes through exactly two points because that is all you have.

Now we attempt the induction step. We have n+1 points. Leave one, p, out. We know that the theorem applies to the n points by the induction hypothesis. So we have points q and r that have a line going through them. And the point of the theorem is that the line goes through only q and r, exactly two points of the n. All we have to do is add in p, not on that line, and we are done.

But we are also stuck. Point p is not one of the n points participating in the induction hypothesis. Nothing tells us that p is not on the line joining q and r.

So how do we prove it? It is a good, intriguing puzzle, but in proof theory, not geometry.

Re: The Sylvester–Gallai Theorem

#44

Post by stackghost »

hyperhello wrote: post #20
stackghost wrote: post #17

Earlier quoted context omitted.

... yes, I understand. There's nothing novel here. I feel like I'm taking fucking crazy pills.

Math is like that. But try to put any number of points in some configuration where you can't find some line with only two on it. In this diagram, you can't do an axis-aligned line with more or less than three -- but you can go diagonal and cross only two points. There's always a way to find only two points. . . . . . . . . .

>There's always a way to find only two points.

As soon as the set of points are defined to be non-collinear in Euclidean space, this property must be true, purely from the definition of the problem. To suggest otherwise would be to violate either the problem definition or the axioms of Euclidean geometry.

Re: The Sylvester–Gallai Theorem

#45

Post by stackghost »

chenb4425 wrote: post #22
stackghost wrote: post #12

Earlier quoted context omitted.

>rather, it's the weaker statement that there isn't any one single line that all the points lie on ... of course there's no single line that all the points lie on. They've been defined to be non-collinear. Edit: can't reply because of HN's stupid rate-limit mechanism, but to this: >So the theorem proves that no matter which way you arrange any finite set of points, except for all on the same line, then you can always…

I think you are mistaking the fact that you can easily find an example satisfying the theorem’s statement with the proof that the statement is always true. Of course given any set of points that aren’t all on the same line, your nine your old could find a line passing through only two points. But could they explain to you why this is always possible, no matter the configuration of points? You can’t just say “I draw a…

>You must also explain why there isn’t a third point on the line, and why that line’s existence is guaranteed, which is not obvious (at least to me).

There isn't a third point on the line you found because the problem stipulates that the set of points is not collinear.

Re: The Sylvester–Gallai Theorem

#46

Post by hyperhello »

stackghost wrote: post #44
hyperhello wrote: post #20

Earlier quoted context omitted.

Math is like that. But try to put any number of points in some configuration where you can't find some line with only two on it. In this diagram, you can't do an axis-aligned line with more or less than three -- but you can go diagonal and cross only two points. There's always a way to find only two points. . . . . . . . . .

>There's always a way to find only two points. As soon as the set of points are defined to be non-collinear in Euclidean space, this property must be true, purely from the definition of the problem. To suggest otherwise would be to violate either the problem definition or the axioms of Euclidean geometry.

You're still not quite getting it, the statement isn't that trivial. It deals with the area between totally collinear (obviously impossible to find a lonely pair) and totally non-collinear (obviously impossible not to find a lonely pair).

Re: The Sylvester–Gallai Theorem

#47

Post by chenb4425 »

stackghost wrote: post #45
chenb4425 wrote: post #22

Earlier quoted context omitted.

I think you are mistaking the fact that you can easily find an example satisfying the theorem’s statement with the proof that the statement is always true. Of course given any set of points that aren’t all on the same line, your nine your old could find a line passing through only two points. But could they explain to you why this is always possible, no matter the configuration of points? You can’t just say “I draw a…

>You must also explain why there isn’t a third point on the line, and why that line’s existence is guaranteed, which is not obvious (at least to me). There isn't a third point on the line you found because the problem stipulates that the set of points is not collinear .

That's only assuming your set of points only contains three points. If you have four or more points, it's entirely possible that a line you draw between two points passes through a third.

.

...

If you're given the above set of points, it's obviously not collinear due to the point at the top, but if you draw a line through any of the bottom two points, it will hit a third.

Re: The Sylvester–Gallai Theorem

#48

Post by h3lp »

stackghost wrote: post #45
chenb4425 wrote: post #22

Earlier quoted context omitted.

I think you are mistaking the fact that you can easily find an example satisfying the theorem’s statement with the proof that the statement is always true. Of course given any set of points that aren’t all on the same line, your nine your old could find a line passing through only two points. But could they explain to you why this is always possible, no matter the configuration of points? You can’t just say “I draw a…

>You must also explain why there isn’t a third point on the line, and why that line’s existence is guaranteed, which is not obvious (at least to me). There isn't a third point on the line you found because the problem stipulates that the set of points is not collinear .

So it says that not ALL points are on that single line. But it doesn't stipulate that THREE points can't be on the line---the theorem is about proving that you can find one that doesn't have the third point.

Re: The Sylvester–Gallai Theorem

#49

Post by Mithriil »

Nail2680 wrote: post #8

I might be too stupid to understand why this is interesting and useful. If it helps I am a working physicist, and a lot of pure math is lost on me. I think I followed this, but I don't know why one would care or this would be interesting.

Also, see the title of the website.

Re: The Sylvester–Gallai Theorem

#50

Post by Mithriil »

stackghost wrote: post #11

>Every finite set of points in the Euclidean plane that is not collinear has a line that passes through exactly two of the points. Isn't this a tautology? The problem definition states that the set of points is in Euclidean space, which from Euclid's Axioms means we can draw a line between any two points. The set of points is defined to be not collinear, thus we cannot draw a line passing through more than two of the…

Say you've got a set of 5 points that are not all collinear (e.g. everytime you draw a line, you never get all 5 of them). Now every time you try to draw a line between two points, you always end up with a third one. Can this happen?

This is what is stated here: there always exists at least a pair where this does not happen.

Post reply on HN