Beck's theorem

There are two (completely different) theorems in mathematics (by two different mathematicians) going under the name of Beck's theorem.

Beck's theorem in category theory

Beck's monadicity theorem asserts that a functor

is monadic if and only if

1. U has a left adjoint;
2. U reflects isomorphisms; and
3. C has co-equalizers of U-split co-equalizer pairs, and U preserves those co-equalizers.

This is a basic result of J. M. Beck from around 1967, often stated in dual form for comonads. Its importance arises in relation with descent, in particular in the Grothendieck approach to algebraic geometry. Passing to a category of coalgebras for a comonad T is a high-flown way of modelling what taking equivalence classes does, in less touchy situations. The theorem, often also called the Beck tripleability theorem because of the older term triple for comonads, gives an exact categorical description of the process of 'descent', at this level. In 1970 the whole Grothendieck approach via descent data was shown (Benabou and others) to be equivalent, somewhat non-obviously, to the comonad approach. In later work, and after a hiatus of communication between algebraic geometers and category theorists, Deligne applied Beck's theorem to tannakian category theory, greatly simplifying the basic developments.

Beck's theorem in incidence geometry

Beck's theorem [1] 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:

1. There is a line which contains at least n/C of the points.
2. There exist at least n² / 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. This theorem can be viewed as a more quantitative form of the more classical Sylvester-Gallai theorem. It says that finite collections of points 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.

A proof of Beck's theorem can be given as follows. Consider a collection of n points. Let j be a positive integer. Let us say that a pair of points A, B in the collection is j-connected if the line connecting A and B contains between 2^j and 2^{j + 1} - 1 points in the collection. From the Szemerédi-Trotter theorem, the number of such lines is O(n² / 2^3j + n / 2^j), where we are using big O notation. Since each such line connects together O(2^2j) points, we thus see that at most O(n² / 2^j + 2^jn) pairs of points can be j-connected.

Now let C be a large number. By summing the geometric series, we see that the number of pairs of points which are j-connected for some j satisfying is at most O(n² / C + n² / C). On the other hand, the total number of pairs is . Thus if we choose C to be large enough, we can find at least n² / 4 pairs (for instance) which are not j-connected for any . Thus 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² / 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² / 4C(2C - 1) lines connecting at least two points, and the claim follows by taking K = 4C(2C - 1).

References

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