View source for Beck's theorem (geometry)

{{short description|On lower bounds on the number of lines determined by a set of points in the plane}}
{{for|the category theory developed by a different author|Beck's monadicity theorem}}
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]].<ref name="becks-paper"/> 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 [[Leroy Milton Kelly|L. M. Kelly]] and W. O. J. Moser<ref>{{cite web|url=http://www.math.mcgill.ca/people/moser|title=William O. J. Moser}}</ref> involving configurations of ''n'' points of which at most ''n''&nbsp;&minus;&nbsp;''k'' are collinear, for some 0&nbsp;<&nbsp;''k''&nbsp;<&nbsp;''O''({{radic|''n''}}). They showed that if ''n'' is sufficiently large, relative to ''k'', then the  configuration spans at least ''kn''&nbsp;&minus;&nbsp;(1/2)(3''k''&nbsp;+&nbsp;2)(''k''&nbsp;&minus;&nbsp;1) lines.<ref>{{citation | last1 = Kelly | first1 = L. M. | author1-link = Leroy Milton Kelly | last2 = Moser | first2 = W. O. J. | title = On the number of ordinary lines determined by ''n'' points | journal = Can. J. Math. | volume = 10 | year = 1958 | pages = 210–219 | doi = 10.4153/CJM-1958-024-6 | s2cid = 123865536 | doi-access = free }}</ref>

Elekes and Csaba Toth noted that the Erdős–Beck theorem does not easily extend to higher dimensions.<ref>{{cite book|last=Elekes|first=György |author1-link=György Elekes|author2=Tóth, Csaba D.|title=Proceedings of the twenty-first annual symposium on Computational geometry |chapter=Incidences of not-too-degenerate hyperplanes |author2-link=Csaba D. Tóth|year=2005|isbn=1-58113-991-8|publisher=Annual Symposium on Computational Geometry|location=Pisa, Italy|pages=16–21|doi=10.1145/1064092.1064098 |s2cid=9617907 }}</ref> Take for example a set of 2''n'' points in '''R'''<sup>3</sup> all lying on two [[skew lines]]. Assume that these two lines are each incident to ''n'' points.  Such a configuration of points spans only 2''n'' planes. Thus, a trivial extension to the hypothesis for point sets in '''R'''<sup>''d''</sup> is not sufficient to obtain the desired result.

This result was first conjectured by [[Paul Erdős|Erdős]], and proven by Beck. (See ''Theorem 5.2'' in.<ref name="becks-paper">{{cite journal|last=Beck|first=József|author-link=József Beck|year=1983|title=On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry|journal=Combinatorica |volume=3|issue=3–4|pages=281–297|mr=0729781|doi=10.1007/BF02579184|s2cid=31011939}}</ref>)

===Statement===
Let ''S'' be a set of ''n'' points in the plane. If no more than ''n''&nbsp;&minus;&nbsp;''k'' points lie on any line for some 0&nbsp;≤&nbsp;''k''&nbsp;<&nbsp;''n''&nbsp;&minus;&nbsp;2, then there exist Ω(''nk'') lines determined by the points of&nbsp;''S''.

===Proof===
{{Empty section|A proof of this theorem|date=March 2010}}

==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]].<ref>Beck's Theorem can be derived by letting ''k''&nbsp;=&nbsp;''n''(1&nbsp;−&nbsp;1/''C'') and applying the Erdős–Beck theorem.</ref>

===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 <math>n^2/K</math> 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 <math>2^j</math> and <math>2^{j+1}-1</math> points of ''P'' (including ''A'' and ''B'').

From the [[Szemerédi–Trotter theorem]], the number of such lines is <math>O( n^2 / 2^{3j} + n / 2^j )</math>, 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 <math> 2^j </math> points of ''P''. Since no two points can lie on two distinct lines <math> |L| \cdot {2^j \choose 2} \leq {n \choose 2}</math>. Now using [[Szemerédi–Trotter theorem]], it follows that the number of incidences between ''P'' and ''L'' is at most <math>O(n^2/2^{2j} + n)</math>. All the lines connecting ''j-connected'' points also lie in ''L'', and each contributes at least <math>2^j</math> incidences. Therefore, the total number of such lines is <math>O(n^2/2^{3j} + n/2^j)</math>.

Since each such line connects together <math>\Omega( 2^{2j} )</math> pairs of points, we thus see that at most <math>O( n^2 / 2^j + 2^j n )</math> 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 <math>C \leq 2^j \leq n/C</math> is at most <math>O( n^2 / C)</math>.

On the other hand, the total number of pairs is <math>\frac{n(n-1)}{2}</math>.  Thus if we choose ''C'' to be large enough, we can find at least <math>n^2 / 4 </math> pairs (for instance) which are not ''j''-connected for any <math>C \leq 2^j \leq n/C</math>.  The lines that connect these pairs either pass through fewer than 2''C'' 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 <math>n^2 / 4</math> pairs are connected by lines which pass through fewer than 2''C'' points.  But each such line can connect at most <math>C(2C-1)</math> pairs of points.  Thus there must be at least <math>n^2 / 4C(2C-1)</math> lines connecting at least two points, and the claim follows by taking <math>K = 4C(2C-1)</math>.

== References ==
<references/>

{{Incidence structures}}

{{DEFAULTSORT:Beck's Theorem (Geometry)}}
[[Category:Euclidean plane geometry]]
[[Category:Theorems in discrete geometry]]
[[Category:Articles containing proofs]]