MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi all, I have a question Concerning Beck's theorem. I have read it from and I have two questions :

  1. I suppose Beck's theorem doesn't hold when instead of saying "at least two points" we take "exactly two points",since there may be lines which do not connect exactly two points at all, right?

  2. In the proof mentioned above, I think the statement that "The lines that connect these pairs either pass through fewer than 2C points, or pass through more than n/C points." is incorrect, it should be "fewer than C points" or more than "2n/C points". Am I right or do I miss some logic here?


share|cite|improve this question
@rose: I repaired the broken link (the apostrophe needs a special character). – Joseph O'Rourke Apr 11 '12 at 19:50

1, Yes, it only holds with at least two, otherwise you get the ordinary lines problem, for which the answer is linear in n, for more see

2, No, you miss something, I think it is correct on wikipedia (or I miss some logic...)

share|cite|improve this answer
Thanks, but where do I miss something for point 2? Since C<=2^j<=N/C, if line is not j-connected, either it contains more than 2^{j+1} points or less than 2^{j} points, right? Hence it should contain fewer than C or more than 2N/C points. Where is my fault? – rose Apr 17 '12 at 16:27
If a line contains less than 2^j points, then it does not mean that it contains less then C points, because C might not be a power of two. E.g. suppose C=5, j=3. Then if a line contains 7 points, it is 2-connected (and not 3-connected). We cannot conclude that 7<C, only that 7<2C. – domotorp Apr 17 '12 at 18:42
but we are considering the case when line is not j-connected for all j such that C<=2^{j} <=N/C, that's why we can conclude that line should contain less than C points – rose Apr 18 '12 at 1:32
In my previous example, a line with 7 points is not j-connected for any such j (since only 2-connected) and it contains more than C points. – domotorp Apr 20 '12 at 5:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.