1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge V: Sylvester-Gallai Theorem, solved by Mandelbroth

  1. Aug 6, 2013 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Let's put up a new challenge:

    This is called the Fano plane:
    images?q=tbn:ANd9GcTeBAUe34X1D37rw9OoCvJiqtWvXW_svKHerc6opWpldiEM1RNTDA.png

    This is a geometric figure consisting of 7 points and 7 lines. However, it is a so-called projective plane. This means that it satisfies the following axioms:
    1) Through any two points, there is exactly one line
    2) Any two lines meet in exactly one point
    3) There are four point such that no line goes to more than two of them

    The study of projective planes and spaces goes deep and far. But for now, I'm asking something simpler. When you look at the figure, you see that one of the "lines" is actually a circle and not a straight line. Prove that you can't draw the above configuration on a plane such that all the lines are actually straight lines.

    If you find this too easy, then there is this generalization:
    Given ##n## points on a plane. If they do not all lie on a straight line, then there is a straight line in the plane that contains exactly two of the points.
     
    Last edited by a moderator: Aug 8, 2013
  2. jcsd
  3. Aug 6, 2013 #2
    Suppose ##n=1##. :biggrin:
     
    Last edited by a moderator: Aug 8, 2013
  4. Aug 6, 2013 #3
    Then, out of the collection of points, in which there is only one point, all lie on a straight line (IMO) (on many straight lines to be more precise). The claim which is to be proven has the same form as [itex](0=1)\rightarrow \cdots[/itex], and it will be true.
     
  5. Aug 6, 2013 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Zero points still lie on one line. Indeed, given any line ##L##, we have ##\emptyset\subseteq L##.
     
  6. Aug 6, 2013 #5
    Nevermind. I was correct in what I was saying. ##n\in\{0,1\}## is trivial (as is ##n=2##).

    I should stop second guessing myself.
     
  7. Aug 6, 2013 #6
    Cases [itex]n\in\{0,1,2,3\}[/itex] proven. We are making progress.

    I guess we are not in position of speaking about "generalization" of the challenge, since we haven't reached [itex]n=7[/itex] yet...

    (edit: Actually I don't yet know what to do with the case n=7 either... looks tough..)
     
    Last edited: Aug 6, 2013
  8. Aug 7, 2013 #7
    I might as well do ##n>3## as well.

    Suppose, by way of contradiction, that there are ##n## points, not all of which are collinear but with at least 3 points on each line connecting any 2 points. Let ##r## be the smallest distance between a line ##l## and a point ##x## not on that line. Because ##l## goes through at least 3 of the ##n## points, for a segment ##R## of length ##r## from ##x## to ##l## there are two cases:

    • The segment intersects ##l## at one of the ##n## points and there is exactly 1 point on either side of the segment, implying the rest of the points are contained in the line containing ##R##, in which case there is a line between only one of the points on either side and ##x##, reaching a contradiction.
    • There are at least two points on one side of the line containing ##R##. Call the point closer to the segment ##a##, and a further point ##b##. Let ##m## be the line that connects ##x## and ##b##. The distance from ##a## to ##m## is less than ##r##, reaching a contradiction.

    Thus, ##x## must be on ##l## if every line connecting 2 points contains at least 3 of the ##n## points. The result follows.
     
  9. Aug 7, 2013 #8
    I believe I drew a picture of the situation you described, and I don't see a contradiction.
     
  10. Aug 7, 2013 #9
    You believe you drew a picture or you believe there isn't a contradiction? :tongue:

    I've attached my drawing. I can show all the trig if you want, but it's fairly clear that the distance from ##a## to ##m## is less than ##r##.
     

    Attached Files:

  11. Aug 7, 2013 #10
    I know I drew something.

    What two claims are contradictory in "the contradiction"?
     
  12. Aug 7, 2013 #11
    For the second case, ##r## is taken to be the smallest distance between a line and a point not on that line, which I named ##l## and ##x## (respectively) for convenience. However, the distance from ##a## to ##m## is smaller than ##r## (implying that there isn't a smallest distance between a line and a point not on that line).

    If all lines containing 2 of the ##n## points contain at least 3 of them, then they must all, therefore, be collinear.
     
  13. Aug 7, 2013 #12
    ok, I had not understood your explanation properly. I guess I'll remove my picture now -->
     
  14. Aug 7, 2013 #13
    To clarify to other readers, this means that we go through all possible lines ell connecting some points, and for all fixed ell, again through all possible points x not on that ell. Then the final ell and x are chosen so that their distance is minimal.

    This looks like a good start, but I didn't yet understand how the final steps of the proof were supposed to work.

    Mandelbroth, can you clarify what you assume about the points a and b with respect to the line ell? Are completely free of it, or do you insist that one or both of them are on ell?
     
    Last edited: Aug 7, 2013
  15. Aug 7, 2013 #14
    The existence of at least one of the points is guaranteed by the fact that each line contains at least three of the ##n## points in both cases. In the second case, ##a## and ##b## are shown to exist because of this definition, and I did the trig calculations for the distance from ##a## to ##m## that way. In general, I suppose they are not required to be on ##l##, though. My proof uses the fact that there is a pair ##a## and ##b## that must exist under the assumptions of the proof.

    For the final part of the proof, if ##r## cannot exist with the beginning conditions, then there isn't a smallest distance between a line and a point not on that line under those conditions. We thus conclude that the points must all be on the same line.

    Edit: misunderstanding the confusion. See below.
     
    Last edited: Aug 7, 2013
  16. Aug 7, 2013 #15
    This:

    Clarify!

    In your drawing the a and b are not on ell, right? In that case your claim doesn't seem valid. It is possible that the distance between m and a is greater than r too.

    Your claim conserning the distance seems correct if a and b are on ell, but then we have other problems with the logic of the proof attempt.
     
  17. Aug 7, 2013 #16
    I did! :eek:
    I apologize. That would explain the confusion. I should fix that.

    Why?
     

    Attached Files:

    Last edited: Aug 7, 2013
  18. Aug 7, 2013 #17
    This can happen:

    [Broken]
     
    Last edited by a moderator: May 6, 2017
  19. Aug 7, 2013 #18
    Indeed, but a pair ##a## and ##b## satisfying the results of the proof are given to exist on the line.

    I'm asking about the logic of the proof attempt.
     
    Last edited by a moderator: May 6, 2017
  20. Aug 7, 2013 #19

    verty

    User Avatar
    Homework Helper

    Proving that generalization by strong induction definitely seems possible, although there is a hurdle to overcome. I won't prove it though, I'll leave it to anyone else who would like to try it.
     
  21. Aug 7, 2013 #20
    In the original proof attempt you divided the proof into two possible situations. In the same spirit I do a similar division now:

    Situation 1: When the line R splits the line ell into two pieces, both sides contain precisely one point on ell. (According to our anti-thesis, the line ell also must contain a third point at the intersection of ell and R.)

    Situation 2: When the line R splits the line ell into two pieces, at least other side contains at least two points on ell.

    I haven't checked any trigonometry yet, but it seems that in situation 2 we arrive at a contradiction as you showed in the second attachment drawing. So that half is ok.

    The first situation becomes a mystery. I don't see how we get a contradiction there.

    In the original proof attempt you made the following claim:

    Assume that when the line R splits line ell into two pieces, both sides contain precisely one point on ell, and also assume that no other points exist outside the line R. Then a contradiction follows.

    This claim was correct, but there are too much assumptions for the complete proof.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge V: Sylvester-Gallai Theorem, solved by Mandelbroth
  1. Solve v = f(x) for x (Replies: 3)

Loading...