In discrete geometry, Beck's theorem is any of several different results, two of which are given below. Both appeared, alongside several other important theorems, in a well-known paper by József Beck. The two results described below primarily concern lower bounds on the number of lines determined by a set of points in the plane. (Any line containing at least two points of point set is said to be determined by that point set.)
Contents
Erdős–Beck theorem
The Erdős–Beck theorem is a variation of a classical result by L. M. Kelly and W. O. J. Moser involving configurations of n points of which at most n − k are collinear, for some 0 < k < O(√n). They showed that if n is sufficiently large, relative to k, then the configuration spans at least kn − (1/2)(3k + 2)(k − 1) lines.
Elekes and Csaba Toth noted that the Erdős–Beck theorem does not easily extend to higher dimensions. Take for example a set of 2n points in R3 all lying on two skew lines. Assume that these two lines are each incident to n points. Such a configuration of points spans only 2n planes. Thus, a trivial extension to the hypothesis for point sets in Rd is not sufficient to obtain the desired result.
This result was first conjectured by Erdős, and proven by Beck. (See Theorem 5.2 in.)
Statement of the theorem
Let S be a set of n points in the plane. If no more than n − k points lie on any line for some 0 ≤ k < n − 2, then there exist Ω(nk) lines determined by the points of S.
Beck's theorem
Beck's theorem says that finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.
Although not mentioned in Beck's paper, this result is implied by the Erdős–Beck theorem.
Statement of the theorem
The theorem asserts the existence of positive constants C, K such that given any n points in the plane, at least one of the following statements is true:
- There is a line which contains at least n/C of the points.
- There exist at least
n 2 / K lines, each of which contains at least two of the points.
In Beck's original argument, C is 100 and K is an unspecified constant; it is not known what the optimal values of C and K are.
Proof
A proof of Beck's theorem can be given as follows. Consider a set P of n points in the plane. Let j be a positive integer. Let us say that a pair of points A, B in the set P is j-connected if the line connecting A and B contains between
From the Szemerédi–Trotter theorem, the number of such lines is
Since each such line connects together
Now, let C be a large constant. By summing the geometric series, we see that the number of pairs of points which are j-connected for some j satisfying
On the other hand, the total number of pairs is