# Beck's theorem (geometry)

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.)

## 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 R$^3$ 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 R$^d$ 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

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.

### Proof
## 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

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 $2^{j}$ and $2^{j+1}-1$ points of P (including A and B).
From the Szemerédi–Trotter theorem, the number of such lines is $O(n^{2}/2^{3j}+n/2^{j})$, as follows: Consider the set P of n points, and the set L of all those lines spanned by pairs of points of P that contain at least $2^{j}$ points of P. Since no two points can lie on two distinct lines $|L|\cdot {2^{j} \choose 2}\leq {n \choose 2}$. Now using Szemerédi–Trotter theorem, it follows that the number of incidences between P and L is at most $O(n^{2}/2^{2j}+n)$. All the lines connecting j-connected points also lie in L, and each contributes at least $2^{j}$ incidences. Therefore, the total number of such lines is $O(n^{2}/2^{3j}+n/2^{j})$.
Since each such line connects together $\Omega (2^{2j})$ pairs of points, we thus see that at most $O(n^{2}/2^{j}+2^{j}n)$ pairs of points can be j-connected.
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 $C\leq 2^{j}\leq n/C$ is at most $O(n^{2}/C)$.
On the other hand, the total number of pairs is ${\frac {n(n-1)}{2}}$. Thus if we choose C to be large enough, we can find at least $n^{2}/4$ pairs (for instance) which are not j-connected for any $C\leq 2^{j}\leq n/C$. The lines that connect these pairs either pass through fewer than 2C points, or pass through more than n/C points. If the latter case holds for even one of these pairs, then we have the first conclusion of Beck's theorem. Thus we may assume that all of the $n^{2}/4$ pairs are connected by lines which pass through fewer than 2C points. But each such line can connect at most $C(2C-1)$ pairs of points. Thus there must be at least $n^{2}/4C(2C-1)$ lines connecting at least two points, and the claim follows by taking $K=4C(2C-1)$.