🔢 mathematics

A Salem-Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles

Cet article présente une construction de type Salem–Spencer modifiée sur les entiers de Gauss pour prouver que le plus grand sous-ensemble d'une grille entière de $n \times n$ ne contenant aucun triangle rectangle isocèle non dégénéré a une taille d'au moins $\Omega(n^{1.3})$ , réduisant ainsi l'écart avec la meilleure borne supérieure actuelle.

Auteurs originaux : Gyula Károlyi, Jozsef Solymosi

Publié 2026-07-28

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Gyula Károlyi, Jozsef Solymosi

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un détective essayant de résoudre un mystère dans une ville géante et infinie, entièrement composée d'intersections de grilles. Cette ville est le monde des mathématiques, plus précisément d'une branche appelée la combinatoire, qui consiste à compter, disposer et trouver des motifs dans des objets discrets. Dans cette ville, les « rues » sont simplement des nombres, et les « bâtiments » sont des points où deux nombres se rencontrent, comme des coordonnées $(x, y)$ sur une carte.

Le mystère en question implique une règle très spécifique : vous voulez construire le plus grand quartier possible (un sous-ensemble de points) où une certaine forme est strictement interdite. Cette forme est le triangle rectangle isocèle. Vous connaissez bien ces triangles : ils ont un angle qui est un angle droit parfait (comme le coin d'une feuille de papier), et les deux côtés touchant ce coin ont exactement la même longueur. La question que les mathématiciens posent depuis longtemps est : Quelle taille peut atteindre un quartier avant que vous ne soyez forcé de construire accidentellement l'un de ces triangles ? Ce n'est pas seulement un jeu de géométrie ; c'est un puzzle profond qui relie la façon dont les nombres se comportent, la façon dont on chiffre les données et même notre compréhension de la structure de l'univers. Si vous trouvez un immense quartier sans triangles, cela signifie qu'il existe des façons cachées et complexes d'organiser les nombres pour éviter des motifs simples. Pendant des décennies, les mathématiciens savaient que la réponse se trouvait quelque part entre « très grand » et « presque toute la ville », mais l'écart entre la taille du plus petit grand quartier et celle du plus grand était énorme. C'était comme savoir qu'un coffre au trésor se trouve quelque part dans un désert, mais ne pas savoir s'il est enterré sous un seul grain de sable ou sous une montagne d'or.

La grande découverte de l'article : Une nouvelle façon de construire des villes « sans triangles »

Dans cet article, deux mathématiciens, Gyula Károlyi et József Solymosi, ont construit un nouveau quartier massif, bien plus grand que ce que l'on pensait possible auparavant. Ils ont réussi à construire un sous-ensemble de points dans une grille qui évite les triangles rectangles isocèles, et leur construction est si grande qu'elle prouve que la taille d'un tel quartier croît à un rythme d'environ $n^{1,3}$ (où $n$ est la taille de la grille).

Pour comprendre comment ils ont procédé, imaginez que vous essayez de construire une tour avec des blocs, mais avec une règle stricte : vous ne pouvez pas empiler les blocs de manière à former une forme « mauvaise » spécifique. Par le passé, les mathématiciens essayaient de construire ces tours en choisissant des blocs qui étaient totalement sûrs individuellement. Mais Károlyi et Solymosi ont réalisé qu'ils pouvaient être plus intelligents. Ils ont utilisé une technique qu'ils appellent le « pelage » (peeling), qui est comme un jeu de Jenga où l'on peut avoir une tour légèrement bancale, tant que l'on peut retirer les blocs un par un dans un ordre spécifique jusqu'à ce que l'ensemble soit sûr.

Les ingrédients magiques

Les auteurs ont utilisé quelques astuces ingénieuses pour réussir cela :

Les entiers de Gauss (La « grille magique ») : Au lieu d'utiliser des nombres normaux, ils ont utilisé un type spécial de nombres appelés entiers de Gauss. Vous pouvez les voir comme des points sur une grille où chaque point possède une coordonnée « x » et une coordonnée « y », mais qui sont traités comme un seul nombre magique. Cela leur a permis de faire pivoter et de déplacer leurs blocs d'une manière que les nombres normaux ne permettaient pas.
L'alphabet « sans retenue » : Lorsque vous additionnez des nombres, il arrive parfois que vous obteniez une « retenue » (comme quand $9 + 1 = 10$ , le 1 est reporté sur le niveau suivant). Les auteurs ont trouvé un ensemble spécial de « chiffres » (un petit groupe de points) où, si vous les additionnez pour former un triangle, les mathématiques ne produisent jamais de « retenue » vers le niveau supérieur. Cela permet de garder les règles locales simples.
L'ordre de pelage (La recette secrète) : C'est la partie la plus novatrice. Ils ont trouvé un groupe de 281 points qui contiennent des triangles si on les regarde tous ensemble. Cependant, ils ont découvert un ordre spécifique pour retirer ces points. Si vous retirez le premier point, aucun triangle ne reste avec ce point comme sommet, puis vous retirez le suivant, et ainsi de suite. Une fois que vous avez terminé, l'ensemble restant est parfaitement sûr. C'est comme avoir une pièce remplie de gens où tout le monde se tient la main en cercle, mais si vous demandez à chacun de partir dans un ordre spécifique, le cercle se brise avant que quiconque ne soit blessé.

Le résultat : Un bond de géant

En utilisant un outil d'IA puissant appelé AlphaEvolve (qui les a aidés à chercher à travers des millions de possibilités pour trouver l'arrangement parfait), ils ont trouvé un « ordre de pelage » pour un ensemble de 281 points.

Lorsqu'ils ont appliqué leur méthode à une grille de taille $n$ , ils ont prouvé que l'on peut trouver un sous-ensemble sans triangle dont la taille est d'au moins $n^{1,3178...}$ .

Pour mettre cela en perspective :

Avant cela, la borne inférieure la plus connue était beaucoup plus petite (environ $n^{1,05}$ ).
La meilleure borne supérieure connue (la limite théorique de la taille possible) est d'environ $n^2$ divisé par certains facteurs logarithmiques.
Leur résultat, $n^{1,3}$ , comble un écart important, montrant que ces quartiers sans triangles peuvent être beaucoup plus grands que ce que l'on soupçonnait auparavant.

Ce qu'ils n'ont PAS fait

Il est important de noter ce que cet article ne prétend pas. Ils n'ont pas prouvé que $n^{1,3}$ est la taille maximale absolue possible. Ils n'ont pas trouvé le quartier « parfait » qui serait aussi grand que mathématiquement possible. Ils n'ont pas non plus prouvé que 281 est le plus grand nombre de points que l'on puisse utiliser dans leur méthode spécifique ; ils ont simplement trouvé un très bon nombre.

L'article stipule explicitement qu'il existe encore un « grand écart » entre leur nouvelle borne inférieure ( $n^{1,3}$ ) et la borne supérieure ( $n^2$ ). Le mystère n'est pas totalement résolu, mais ils ont certainement trouvé une pièce du puzzle bien plus grande que quiconque ne l'avait fait auparavant.

Ce qu'il faut retenir

Cet article est un triomphe combinant la logique mathématique classique et la recherche par IA moderne. En traitant les nombres comme des points sur une grille, en trounant une zone spéciale « sans retenue », et en utilisant une stratégie de « pelage » ingénieuse pour retirer les points dangereux un par un, les auteurs ont montré que nous pouvons construire des villes « sans triangles » bien plus grandes que nous ne le pensions. C'est un exemple frappant de la façon dont une nouvelle perspective — regarder le problème non pas comme un mur statique, mais comme un processus dynamique de retrait — peut débloquer de nouvelles possibilités dans le monde des nombres.

Résumé Technique : Une construction de type Salem–Spencer pour de grands sous-ensembles de grilles d'entiers sans triangles rectangles isocèles

Énoncé du Problème
L'article traite du problème de la détermination de la taille maximale, notée $F(n)$ , d'un sous-ensemble de la grille d'entiers $\{0, 1, \dots, n-1\}^2$ qui ne contient aucun triangle rectangle isocèle (TRI) non dégénéré. Bien que la borne supérieure pour cette quantité soit connue comme étant $F(n) \ll n^2 / (\log n)^{1+c}$ pour une certaine constante $c > 0$ (via des extensions de la méthode de Bloom–Sisask), les meilleures bornes inférieures connues ont été historiquement faibles. Les auteurs visent à établir une borne inférieure superlinéaire, spécifiquement $F(n) = \Omega(n^\alpha)$ pour un $\alpha > 1$ , en utilisant une construction de type Salem–Spencer modifiée et adaptée aux entiers de Gauss.

Méthodologie
Les auteurs emploient une construction basée sur les chiffres sur les entiers de Gauss $\mathbb{Z}[i]$ , identifiant les points du réseau $(x, y)$ avec $x + iy$. La construction repose sur quatre composantes principales :

Codage Linéaire des TRI : Un triangle rectangle isocèle avec des sommets $a, b, c \in \mathbb{Z}[i]$ (où $b$ est le sommet de l'angle droit) est codé par l'équation linéaire $a + ic = (1+i)b$. Les solutions dégénérées correspondent à $a=b=c$ .
Alphabets de Base sans Retenue pour les TRI : Les auteurs définissent un alphabet $P \subset \mathbb{Z}[i]$ comme un système partiel de résidus modulo un entier de Gauss non trivial $\beta$ . $P$ est dit « sans retenue pour les TRI » si l'équation $a + ic = (1+i)b$ est vérifiée modulo $\beta$ uniquement si elle est vérifiée exactement (c'est-à-dire qu'aucune « retenue » ne survient pour créer un faux positif de triangle).
Ordres d'Épluchage de TRI : Contrairement aux constructions classiques de Salem–Spencer qui exigent que l'alphabet lui-même soit exempt de la configuration interdite, cette méthode permet à l'alphabet $P$ de contenir des TRI. Au lieu de cela, $P$ est doté d'un « ordre d'épluchage » $p_1, \dots, p_q$ . Il s'agit d'une séquence telle que pour tout suffixe $R_t = \{p_t, \dots, p_q\}$ , la seule solution à $a + ic = (1+i)p_t$ avec $a, c \in R_t$ est la solution triviale $a=c=p_t$ . Cette propriété garantit que lors de la construction de grands ensembles via des développements en base, tout TRI potentiel peut être éliminé en épluchant les chiffres à partir de la position la plus significative.
Classes de Composition : L'ensemble final est construit en prenant tous les mots de longueur $m$ sur l'alphabet $P$ partageant une « composition » spécifique (comptage de fréquence de chaque chiffre). En se restreignant à une grande classe de composition, l'ordre d'épluchage se propage à travers toutes les positions de chiffres, garantissant que l'ensemble résultant est exempt de TRI.

Contributions Clés et Résultats

Théorème Général (Théorème 2.6) : Les auteurs prouvent que si un alphabet sans retenue pour les TRI $P$ de taille $q$ existe en base $\beta$ avec un ordre d'épluchage valide, alors $F(n) \gg \frac{n^{\log q / \log |\beta|}}{(\log n)^{(q-1)/2}}$ .
Petit Exemple : En utilisant $\beta = 2+2i$ et $P=\{0, 1, i\}$ , ils démontrent une construction produisant un exposant $\alpha \approx 1.0566$ .
Construction Optimisée (Théorème 4.2) : Le résultat principal utilise une base $\beta = 51 + 51i$ $β = 51 + 51 i$ et une région sans retenue $C$ $C$ dérivée d'un diamant centré dans le domaine fondamental. En utilisant l'agent d'IA AlphaEvolve, les auteurs ont découvert un ordre spécifique de 281 points distincts dans $C$ $C$ qui forme un ordre d'épluchage de TRI valide.
- Cela produit la borne :
  $F(n) \gg \frac{n^\alpha}{(\log n)^{140}}$
  où $\alpha = \frac{\log 281}{\log |51+51i|} \approx 1.317865$ .
- Cela établit que $F(n) = \Omega(n^{1.3})$ .

Signification et Revendications
L'article affirme combler l'écart entre les bornes supérieures et inférieures connues pour $F(n)$ en fournissant la première borne inférieure superlinéaire avec un exposant nettement supérieur à 1. La signification réside dans :

Technique Novatrice : L'introduction de l'« ordre d'épluchage » permet d'utiliser des alphabets qui ne sont pas eux-mêmes exempts de TRI, élargissant l'espace de recherche pour de grands ensembles de chiffres au-delà de ce qui était possible avec les méthodes précédentes.
Découverte Computationnelle : L'utilisation d'AlphaEvolve pour trouver le certificat spécifique de 281 points démontre une approche hybride où l'IA aide à la découverte de structures combinatoires, tandis que la validité mathématique de l'ensemble est rigoureusement vérifiée par un certificat déterministe (Annexe B).
Modestie des Revendications : Les auteurs précisent explicitement que leur résultat ne prouve pas que 281 est la taille maximale possible de l'alphabet pour la base choisie, ni que cette base est globalement optimale. Le terme « optimisée » se réfère strictement à l'objectif de recherche computationnelle. Le papier sépare l'argument géométrique (existence de régions sans retenue) de la recherche finie (trouver l'ordre d'épluchage), rendant le résultat indépendamment vérifiable.

Le travail ne propose pas de nouvelles applications ou de directions expérimentales futures au-delà de suggérer des extensions à différentes bases gaussiennes, des régions asymétriques et des blocs de chiffres.

La grande découverte de l'article : Une nouvelle façon de construire des villes « sans triangles »

Les ingrédients magiques

Le résultat : Un bond de géant

Ce qu'ils n'ont PAS fait

Ce qu'il faut retenir

Articles similaires