Théorème de Beck

Il existe des constantes positives C et K telles que pour n points quelconques du plan, au moins l'un des deux énoncés suivants soit vrai :

1. Il y a une droite qui contient au moins n/C des points.
2. Il y a au moins n²/K droites dont chacune contient au moins deux des points.

Dans l'énoncé originel de Beck, C est égal à 100 et K n'est pas précisé ; on ne sait pas quelles sont les valeurs optimales pour C et K.

Soient P un ensemble de n points du plan et j un entier strictement positif. Deux points A et B de P seront dits j-connectés si la droite qui les joint contient entre 2^j et 2^{j + 1} – 1 points de P (en comptant A et B).

Déduisons du théorème de Szemerédi-Trotter que le nombre de droites de ce type est un O(n²/2^3j + n/2^j). Considérons pour cela l'ensemble L des droites contenant au moins 2^j points de P. On remarque que

${\displaystyle |L|{2^{j} \choose 2}\leq {n \choose 2},}$

puisqu'une paire de points ne peut être incluse dans deux droites distinctes. D'après le théorème de Szemerédi-Trotter, il en résulte que le nombre d'incidences entre P et L est un O(n²/2^2j + n). Les droites qui relient des points j-connectés appartiennent à L et chacune d'entre elles contribue au total par au moins 2^j incidences. Le nombre de ces droites est donc un O(n²/2^3j + n/2^j).

Comme chacune d'elles relie Ω(2^2j) paires de points, on en déduit que le nombre de paires de points j-connectés est un O(n²/2^j + 2^jn).

Soit C > 0 une constante arbitraire. En faisant la somme, sur les j tels que C ≤ 2^j ≤ n/C, de la série géométrique, on voit alors que le nombre de paires qui sont j-connectées pour l'un de ces j est un O(n²/C).

D'autre part, le nombre total de paires est n(n – 1)/2. Donc si l'on choisit C assez grand, on peut trouver (par exemple) n²/4 paires qui ne sont j-connectées pour aucun des j tels que C ≤ 2^j ≤ n/C. Les droites qui connectent ces paires passent soit par moins de 2C points, soit par plus de n/C points. Si au moins l'une des droites est dans ce second cas, on obtient la conclusion 1 du théorème de Beck. On peut donc se placer dans le cas où les n²/4 paires sont toutes connectées par des droites passant par moins de 2C points. Mais chacune de ces droites ne peut connecter qu'au plus C(2C – 1) paires de points. Il y en a donc au moins n²/4C(2C – 1) qui connectent au moins deux points, et la conclusion 2 du théorème s'ensuit en prenant K = 4C(2C – 1).