On the Guy-Kelly Conjecture for the No-Three-In-Line Problem

Cet article détaille l'erreur découverte en 2004 par Gabor Ellmann dans l'argument heuristique de Guy et Kelly concernant le problème « no-three-in-line », permettant ainsi de corriger leur borne supérieure conjecturée, une information qui, bien que simple, n'avait pas encore été publiée dans la littérature.

L'essentiel

Voici une explication simple et imagée de ce papier mathématique, comme si nous en discutions autour d'un café.

Le Problème : Le Jeu des Points et de la Règle

Imaginez que vous avez une grande grille carrée, comme un échiquier géant, avec des points aux intersections. Disons que votre grille fait $n$ cases de large et $n$ cases de haut. Cela vous donne un total de $n^2$ points.

Le défi, appelé le problème « Pas trois en ligne », est le suivant : Combien de points pouvez-vous colorier sur cette grille sans jamais que trois d'entre eux ne soient alignés sur une même ligne droite ?

C'est un peu comme jouer aux dames, mais avec une règle stricte : si vous placez trois pions, ils ne doivent jamais former une ligne droite (ni horizontale, ni verticale, ni en diagonale).

L'Intuition des Anciens (Guy et Kelly)

Il y a longtemps, deux mathématiciens, Guy et Kelly, ont essayé de deviner la réponse pour des grilles très, très grandes.
Ils ont dit : « Bon, on sait qu'on ne peut pas dépasser $2n$ points (c'est facile à prouver). Mais pour de très grandes grilles, on pense qu'on ne peut pas atteindre ce maximum. »

Ils ont utilisé une méthode de "devinette intelligente" (une heuristique) pour prédire combien de points on pouvait vraiment placer. Leur formule ressemblait à une recette de cuisine :

« Prenez le nombre $n$, multipliez-le par une constante magique, et vous obtiendrez le nombre maximum de points. »

Leur constante magique était basée sur un calcul qui donnait environ 2,08. Donc, ils pensaient qu'on pouvait placer environ $2,08 \times n$ points.

Le Problème : Une Petite Coquille dans la Recette

En 2004, un mathématicien nommé Gabor Ellmann a relu la recette de Guy et Kelly. Il a trouvé une erreur de calcul, une petite coquille dans l'ingrédient principal.

L'analogie du boulanger :
Imaginez que Guy et Kelly étaient des boulangers qui voulaient calculer combien de gâteaux ils pouvaient faire avec une certaine quantité de farine.

• Ils ont écrit dans leur carnet : « Si je fais des gâteaux pour 2 personnes ($2n$), je dois utiliser telle quantité de farine. »
• Mais en réalité, ils essayaient de calculer pour un nombre variable de personnes ($kn$), pas juste pour 2.
• En utilisant le chiffre "2" au lieu de la variable "k" dans leur équation, ils ont faussé tout le résultat. C'est comme si vous aviez calculé la taille d'un gâteau pour un anniversaire, mais en utilisant la taille d'un gâteau pour un bébé, ce qui vous a donné une estimation trop optimiste.

La Correction : Le Nouveau Nombre Magique

Grâce à l'erreur trouvée par Ellmann, Paul Voutier (l'auteur de ce papier) a pris le temps d'expliquer exactement où se trouvait le problème et comment le corriger.

Quand on remet la bonne variable à la bonne place dans l'équation, le nombre magique change.

• L'ancienne estimation : Environ $2,08 \times n$.
• La nouvelle estimation (corrigée) : Environ $1,81 \times n$.

C'est une différence significative ! Cela signifie que sur une grille géante, on ne peut pas mettre autant de points qu'on le pensait. La "règle des trois en ligne" est plus stricte qu'on ne le croyait.

Pourquoi ce papier est important ?

Ce papier est un peu comme un rapport de correction d'erreur (un erratum) très détaillé.

1. Il rend justice à l'erreur : Il montre exactement où Guy et Kelly s'étaient trompés (une ligne spécifique dans leur vieux papier de 1968).
2. Il officialise la correction : Guy et Kelly n'ont jamais publié la correction officielle avant la mort de Guy en 2020. Ce papier remplit ce vide dans la littérature mathématique.
3. Il confirme le travail récent : Il mentionne qu'un autre mathématicien, Prellberg, a aussi trouvé cette correction très récemment, mais ce papier de Voutier est celui qui explique le "pourquoi" et le "comment" de l'erreur de manière claire.

En résumé

Ce papier raconte l'histoire d'une erreur de calcul dans une célèbre devinette mathématique.

• Le problème : Combien de points mettre sur une grille sans qu'ils s'alignent ?
• L'erreur : Une vieille formule utilisait le mauvais chiffre, donnant une réponse trop optimiste.
• La solution : En corrigeant le calcul, on découvre que la limite réelle est plus basse (environ 1,81 fois la taille de la grille, et non 2,08).

C'est une preuve que même les plus grands mathématiciens peuvent faire une petite erreur de frappe ou de logique, et que la science avance en corrigeant ces détails, même des décennies plus tard !

Résumé technique

Voici un résumé technique détaillé de l'article de Paul M. Voutier, « On the Guy-Kelly Conjecture for the No-Three-in-Line Problem », rédigé en français.

1. Contexte et Problématique

Le problème du « no-three-in-line » (trois points non alignés) est un problème classique de géométrie discrète. Il consiste à déterminer la taille maximale $f_n$ d'un sous-ensemble $T$ d'une grille $S_n$ de $n^2$ points à coordonnées entières $(x, y)$ avec $1 \le x, y < n$, tel qu'aucun triplet de points de$T$ ne soit aligné.

• Bornes connues : La borne supérieure triviale est $f_n \le 2n$, déduite du principe des tiroirs. Il est établi que $f_n = 2n$ pour $n \le 64$ (la limite supérieure ayant été récemment atteinte par Prellberg en février 2026).
• La conjecture originale : Guy et Kelly, dans leur article de 1968 [3], ont émis l'hypothèse que pour $n$ suffisamment grand, $f_n < 2n$. Ils ont proposé une borne asymptotique basée sur un argument heuristique :
  $$f_n \sim \left(\frac{2\pi^2}{3}\right)^{1/3} n \approx 1.817 n$$
• L'anomalie : En mars 2024 (et signalé par Guy en octobre 2004), Gabor Ellmann a identifié une erreur dans le raisonnement heuristique de Guy et Kelly. Cette erreur conduit à une correction de la constante asymptotique.

2. Méthodologie et Analyse de l'Erreur

L'article de Voutier a pour objectif principal de documenter publiquement la nature précise de l'erreur et sa correction, des détails qui, bien que simples, n'avaient jamais été publiés dans la littérature scientifique avant ce travail (à l'exception d'une note récente de Prellberg).

L'argument heuristique de Guy et Kelly :

1. Comptage des alignements : Ils établissent d'abord que le nombre $t_n$ de triplets de points alignés dans $S_n$ est donné par :
   $$t_n = \frac{3}{\pi^2} n^4 \log(n) + O(n^4)$$
2. Probabilité d'alignement : La probabilité que trois points choisis au hasard soient alignés est approximativement $\frac{18 \log(n)}{\pi^2 n^2}$.
3. Hypothèse d'indépendance : En supposant l'indépendance des événements (ce qui est contesté par certaines études récentes, mais accepté pour l'heuristique), la probabilité qu'un ensemble de $kn$ points ne contienne aucun triplet aligné est estimée par :
   $$\left(1 - \frac{18 \log(n)}{\pi^2 n^2}\right)^{\binom{kn}{3}} \approx \exp\left(-\frac{3k^3 n \log(n)}{\pi^2}\right)$$
4. Estimation du nombre de solutions : En combinant cela avec le nombre total de sous-ensembles de taille $kn$, on obtient une estimation du nombre de solutions :
   $$O\left(n^{kn - \frac{3k^3 n}{\pi^2}} \cdot e^{O(n)}\right)$$
   Pour que ce nombre tende vers 0 lorsque $n \to \infty$ (indiquant qu'une telle configuration devient impossible), l'exposant doit être négatif, ce qui implique $k > \pi/\sqrt{3}$.

Identification de l'erreur :
Voutier localise l'erreur exacte dans l'article original de Guy et Kelly [3] à la ligne -4 de la page 530.

• L'erreur : L'équation originale contenait le terme $-2 + \frac{3k^3}{\pi^2}$.
• La correction : Ce terme devrait être $-k + \frac{3k^3}{\pi^2}$.
• Cause racine : Cette erreur provient d'une substitution incorrecte où les auteurs ont utilisé $2n$(la taille maximale conjecturée à l'époque) au lieu de la variable générique$kn$dans les estimations factorielles. Ils ont essentiellement estimé$\frac{(n^2)!}{(n^2 - 2n)!}$et$(2n)!$au lieu de$\frac{(n^2)!}{(n^2 - kn)!}$et$(kn)!$.

3. Résultats Principaux

La correction de l'erreur mathématique modifie l'inégalité critique pour la constante $k$.

• Nouvelle condition : L'analyse corrigée impose que $-k + \frac{3k^3}{\pi^2} < 0$.
• Résolution : Cela conduit à $k > \frac{\pi}{\sqrt{3}}$.
• Nouvelle Conjecture : La borne asymptotique pour $f_n$ est révisée comme suit :
  $$f_n \sim \frac{\pi}{\sqrt{3}} n \approx 1.813799 n$$
  Cette valeur est très proche de l'ancienne conjecture ($1.817$), mais mathématiquement distincte et justifiée par la correction de l'erreur algébrique.

4. Contributions et Signification

• Documentation historique : Ce papier comble une lacune dans la littérature en fournissant la première publication détaillée de la nature exacte de l'erreur de Guy et Kelly et de sa correction. Bien que Gabor Ellmann ait signalé l'erreur à R.K. Guy en 2004, Guy n'a jamais publié la correction formelle avant son décès en 2020.
• Validation de la conjecture corrigée : L'article confirme la dérivée de la borne supérieure corrigée, qui a également été retrouvée indépendamment par Thomas Prellberg dans un travail très récent [5].
• Nuance sur l'hypothèse d'indépendance : L'auteur note que l'hypothèse d'indépendance des événements (utilisée pour passer de la probabilité locale à la probabilité globale) est remise en question par des preuves empiriques (grilles symétriques) et des discussions théoriques récentes (Kaplan, Prellberg). Cependant, l'objectif de ce papier se limite à corriger l'erreur algébrique au sein du cadre heuristique existant, sans nécessairement valider la validité fondamentale de l'approche probabiliste elle-même.

En résumé, l'article de Voutier est une note technique essentielle qui rectifie une conjecture majeure en géométrie discrète en identifiant une erreur de calcul spécifique dans un travail classique, rétablissant ainsi la rigueur mathématique de la borne supérieure asymptotique pour le problème des trois points non alignés.