Théorème de Sylvester-Gallai

En géométrie discrète, le théorème de Sylvester-Gallai affirme qu'étant donné un ensemble fini de points du plan, on a l'alternative suivante :

  • soit tous les points sont alignés,
  • soit il existe une droite qui contient exactement deux de ces points.

Les droites contenant exactement deux points sont nommées droites ordinaires. Ce théorème ne s'applique pas à des ensembles infinis de points : il suffit pour s'en convaincre de considérer l'ensemble des points de coordonnées entières dans le plan euclidien.

Historique

Ce théorème est issu d'un problème initialement posé par James Joseph Sylvester[1], qui fut reposé indépendamment par Paul Erdős[2]. Il fut résolu par Tibor Gallai en 1944[3], même si un théorème équivalent avait déjà été montré par Eberhard Melchior (en)[4].

Point de vue projectif et problème dual

Le même problème peut être posé dans le plan projectif réel plutôt que dans le plan euclidien. Le problème projectif ne généralise en rien le problème euclidien, car tout ensemble fini de points projectifs peut être ramené à un ensemble de points du plan euclidien par une transformation conservant les droites ordinaires. Le point de vue projectif permet cependant de décrire plus naturellement et donc plus facilement certaines configurations, par exemple la configuration de McKee, décrite plus bas.

Par dualité projective, l'existence d'une droite ordinaire associée à un ensemble fini de points non alignés du plan projectif est équivalente à l'existence d'un point ordinaire, c'est-à-dire un point d'intersection d'exactement deux droites, dans un ensemble de droites qui ne passent pas toutes par un point commun.

Melchior a montré en 1940, avant la preuve de Gallai, que tout ensemble fini de droites non concourantes présente au moins trois points ordinaires. Il s'est servi de la caractéristique d'Euler pour montrer que tout tel arrangement de droites a au moins trois sommets de degré 4 ; par dualité, tout ensemble de points non alignés possède donc au moins trois droites ordinaires.

Démonstration

La preuve suivante[5] est due à Leroy Milton Kelly (en)[6] et repose sur la méthode de descente infinie.

Supposons donné un ensemble fini de points du plan, non alignés (en particulier, cet ensemble contient au moins trois points). Nous appellerons droite de connexion toute droite qui contient au moins deux points de l'ensemble. Il s'agit de montrer qu'au moins une de ces droites de connexion contient exactement deux points.

La grandeur utilisé pour la méthode de la descente infinie sera le minimum des distances entre chaque droite de connexion et tous les points extérieurs à celles-ci.

Supposons donc que notre ensemble de points n'est pas aligné, et soit (P,l) un point et une droite de connexion de distance minimale strictement positive parmi tous les points et les droites de connexion. Par hypothèse, l contient alors trois points, notés A, B et C. On considère la perpendiculaire à l passant par P. Il doit y avoir au moins deux points se trouvant d'un côté de la perpendiculaire. Considérons que C est le point le plus éloigné et B le point le moins éloigné de la perpendiculaire. Considérons alors la droite de connexion m passant par C et P. m est alors une droite de connexion qui ne contient pas B et la distance séparant B de m est strictement inférieure à la distance séparant P de l. En effet, si l'on considère les projections, le triangle rectangle hypoténuse BC est semblable à celui d'hypoténuse PC, et strictement inclus dans celui-ci.

Ainsi nous avons montré qu'il est toujours possible sous l'hypothèse initiale de trouver un point de notre ensemble avec une distance minimale aux droites de connexions strictement inférieur à un point donné. Ceci mène à une contradiction, puisqu'il y a un nombre fini de telles distances.

Généralisations

Les deux configurations connues de n points présentant moins de n/2 droites ordinaires.

Si le théorème de Sylvester-Gallai affirme l'existence d'au moins une droite de connexion contenant exactement deux points (droite ordinaire), on ne connaît pas d'arrangement de points tel qu'il n'existe qu'une seule droite ordinaire ; le résultat de Melchior montre que, si les points ne sont pas tous alignés, il existe au moins trois droites ordinaires.

Ceci conduisit Gabriel Dirac à émettre la conjecture[7] affirmant que pour tout ensemble de n points non alignés, il existe au moins n⁄2 droites ordinaires. En 2006, cette conjecture est démentie par seulement deux contre-exemples :

  • Le premier, trouvé par Kelly et Moser[8], est composé par les sommets, les milieux d'arêtes, et le centre d'un triangle équilateral ; ces sept points déterminent seulement trois droites ordinaires. La configuration dans laquelle ces trois droites ordinaires se confondent en une seule droite ne peut être réalisée dans le plan euclidien, mais forme un plan projectif fini connu sous le nom de plan de Fano.
  • L'autre contre-exemple, imaginé par McKee[9], est constitué des sommets de deux pentagones réguliers ayant une arête commune, du milieu de cette arête, et de quatre points à l'infini (c'est-à-dire situés sur la droite à l'infini dans le plan projectif). Ces 13 points déterminent 6 droites ordinaires. Il est possible de déformer cette configuration de manière à ramener tous les points dans le plan euclidien usuel.

Une version plus faible de la conjecture de Dirac a été prouvée par Csima et Sawyer[10]. Elle énonce que dans n'importe quel ensemble de n points, il y a au moins droites ordinaires.

Un résultat proche du théorème de Sylvester-Gallai est le théorème de Beck, qui affirme qu'un ensemble de points du plan présente soit un grand nombre de droites de connexion, soit un grand sous-ensemble maximal de points alignés.

Aspects algorithmiques

Un algorithme de Mukhopadhyay et al.[11],[12] permet de trouver une droite ordinaire dans un ensemble de n points en temps O(n log n).

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sylvester–Gallai theorem » (voir la liste des auteurs).
  1. ↑ (en) J. J. Sylvester, « Mathematical question 11851 », Educational Times, vol. 59,‎ , p. 98
  2. ↑ (en) P. Erdős, « Problem 4065 », Amer. Math. Month., vol. 50, no 1,‎ , p. 65–66 (DOI 10.2307/2304011)
  3. ↑ La preuve de Gallai fut d'abord publiée parmi d'autres preuves de divers autres auteurs ((en) R. Steinberg, R. C. Buck, T. Grünwald (Tibor Gallai) et N. E. Steenrod, « Three point collinearity (solution to problem 4065) », Amer. Math. Month., vol. 51, no 3,‎ , p. 169–171 (DOI 10.2307/2303021)). La priorité lui est cependant accordée, car, comme le notent les publicateurs de la solution, elle fut soumise associée au problème posé par Erdős.
  4. ↑ (de) E. Melchior, « Über Vielseite der Projektive Ebene », Deutsche Math. (de), vol. 5,‎ , p. 461–475
  5. ↑ Pour la preuve originale de Gallai, se reporter à (en) P. Borwein et W. O. J. Moser, « A survey of Sylvester's problem and its generalizations », Aequationes Mathematicae, vol. 40, no 1,‎ , p. 111–135 (DOI 10.1007/BF02112289).
  6. ↑ (en) L. M. Kelly, « A resolution of the Sylvester–Gallai problem of J. P. Serre », Discrete Comput. Geom., vol. 1, no 1,‎ , p. 101–104 (DOI 10.1007/BF02187687).
  7. ↑ (en) G. Dirac, « Collinearity properties of sets of points », Quart. J. Math., vol. 2,‎ , p. 221–227 (DOI 10.1093/qmath/2.1.221)
  8. ↑ (en) L. M. Kelly et W. O. J. Moser, « On the number of ordinary lines determined by n points », Canad. J. Math., vol. 10,‎ , p. 210–219 (DOI 10.4153/CJM-1958-024-6)
  9. ↑ (en) D. W. Crowe et T. A. McKee, « Sylvester's problem on collinear points », Mathematics Magazine, vol. 41, no 1,‎ , p. 30–34 (DOI 10.2307/2687957)
  10. ↑ (en) J. Csima et E. Sawyer, « There exist 6n/13 ordinary points », Discrete Comput. Geom., vol. 9,‎ , p. 187–202 (DOI 10.1007/BF02189318)
  11. ↑ (en) A. Mukhopadhyay, A. Agrawal et R. M. Hosabettu, « On the ordinary line problem in computational geometry », Nordic Journal of Computing, vol. 4, no 4,‎ , p. 330–341
  12. ↑ (en) A. Mukhopadhyay et E. Greene, « The ordinary line problem revisited », dans Proc. 19th Canadian Conference on Computational Geometry, (lire en ligne), p. 61–64

Voir aussi

Liens externes