Beck's theorem (geometry)

In incidence geometry, Beck's theorem is a more quantitative form of the more classical Sylvester–Gallai theorem. It 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.

Precisely, the theorem asserts the existence of positive constants "C", "K" such that 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". Note that $|L|\; cdot\; \{2^j\; choose\; 2\}\; leq\; \{n\; choose\; 2\}$, since no two points can lie on two distinct lines. 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 $O(\; 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)$.

References

# Jozsef Beck, "On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry", Combinatorica 3 (1983), 281--297.