🔢 mathematics

The largest 5th pivot may be the root of a 61st degree polynomial

Cet article présente une nouvelle méthode combinant l'optimisation numérique et l'algèbre exacte pour démontrer que le plus grand facteur de croissance observé pour la taille $n=5$ dans l'élimination de Gauss avec pivotage complet est la racine d'un polynôme de degré 61, tout en affinant la borne supérieure correspondante.

Auteurs originaux : James Chen, Alan Edelman, John Urschel

Publié 2026-03-17

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : James Chen, Alan Edelman, John Urschel

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 architecte chargé de construire un pont (une matrice) qui doit supporter un poids énorme (des calculs complexes). Pour que le pont ne s'effondre pas sous la pression, vous devez choisir les meilleurs points d'appui, appelés pivots.

Dans le monde des mathématiques, il existe une règle très stricte pour choisir ces points d'appui, appelée « pivotage complet ». La question qui hante les mathématiciens depuis des décennies est la suivante : « Quelle est la pire situation possible ? » Autrement dit, jusqu'où peut gonfler le poids sur le pont avant qu'il ne devienne instable ?

Ce poids gonflé s'appelle le facteur de croissance.

Voici l'histoire de la découverte faite par James Chen, Alan Edelman et John Urschel, racontée simplement :

1. Le mystère du nombre 4,1325...

Depuis les années 1960, les mathématiciens savaient que pour de petites matrices (taille 1, 2, 3, 4), le facteur de croissance était un nombre simple et propre : 1, 2, 2,25, et 4.

Mais pour la taille suivante, n = 5, c'était le chaos. Depuis 1988, des ordinateurs puissants essayaient de trouver le pire cas possible. Ils calculaient, calculaient, et trouvaient toujours le même nombre bizarre : 4,1325...
C'était comme si vous cherchiez le sommet d'une montagne, et que chaque fois que vous montiez, vous voyiez le même pic lointain, mais vous ne saviez jamais si c'était le vrai sommet ou juste un faux sommet.

2. La méthode du détective : Mélanger l'instinct et la rigueur

Les auteurs de ce papier ont eu une idée géniale. Au lieu de juste laisser l'ordinateur deviner (ce qui est comme chercher une aiguille dans une botte de foin à l'aveugle), ils ont utilisé une approche en deux temps, un peu comme un détective :

Étape 1 : L'instinct numérique (Le JuMP). Ils ont d'abord laissé un logiciel moderne faire des millions de calculs rapides pour trouver le meilleur candidat. Le logiciel a dit : « Regardez, la structure de la matrice qui donne 4,1325... ressemble à ceci ». C'est comme si le détective trouvait une empreinte de pas très précise.
Étape 2 : La rigueur mathématique (Les bases de Gröbner et les discriminants). Une fois l'empreinte trouvée, ils ont arrêté de deviner. Ils ont pris cette structure et ont utilisé des outils mathématiques très puissants (des « bases de Gröbner ») pour transformer ce problème en une équation pure.

3. La révélation : Le nombre est une racine cachée

Le résultat est stupéfiant. Le nombre 4,1325... n'est pas un nombre aléatoire. Il est la racine exacte d'un polynôme de degré 61.

L'analogie : Imaginez que vous cherchiez un trésor. Jusqu'ici, vous ne saviez que la carte indiquait « environ 4,13 km ». Grâce à ce papier, ils ont découvert que le trésor est caché exactement là où l'équation $x^{61} + ... = 0$ est vraie. C'est comme passer d'une estimation floue à une formule mathématique parfaite, même si cette formule est très complexe (degré 61, c'est énorme !).

Ils ont prouvé que, dans le cadre des règles qu'ils ont observées, aucun nombre plus grand n'est possible. Ils conjecturent (ils pensent très fort) que c'est le vrai maximum absolu.

4. La limite supérieure : On a réduit la zone de recherche

Avant ce papier, on savait que le facteur de croissance ne pouvait pas dépasser 4,94 (une limite établie en 1969). C'était comme dire : « Le trésor est quelque part entre 4,13 km et 4,94 km ».

Grâce à une nouvelle technique combinant des mathématiques pures et des calculs intervalles (une méthode qui vérifie des zones entières sans erreur d'arrondi), ils ont réussi à réduire cette zone. Ils ont prouvé que le trésor ne peut pas être au-delà de 4,84.

C'est une amélioration, même si elle semble petite. C'est comme si, après des années de recherche, on avait réussi à dire : « Le trésor n'est pas dans la forêt entière, il est dans ce petit bois précis ».

En résumé

Ce papier est une victoire de la collaboration entre l'homme et la machine :

L'ordinateur a trouvé le chemin (la structure de la matrice).
Les mathématiciens ont utilisé des outils algébriques complexes pour prouver que ce chemin mène à un nombre exact, défini par un polynôme géant de 61 degrés.

Ils ont résolu un mystère vieux de 30 ans pour la taille 5, et ont ouvert la voie pour les tailles 6, 7 et 8. C'est une preuve magnifique que même les problèmes les plus compliqués peuvent être débloqués en mélangeant l'intuition numérique et la rigueur exacte.

Et le tout est dédié à la mémoire de Nick Higham, un grand ami des mathématiques qui aimait passionnément ce genre de puzzles.

1. Problématique

L'article s'attaque à un problème classique et notoirement difficile de l'algèbre linéaire numérique : déterminer le facteur de croissance maximal ( $g(A)$ ) lors de l'élimination de Gauss avec pivots complets (complete pivoting) pour des matrices réelles de taille $n \times n$ .

Le facteur de croissance est défini comme le rapport entre la plus grande valeur absolue d'un élément apparaissant au cours de l'élimination et la plus grande valeur absolue d'un élément de la matrice initiale. Ce facteur est crucial pour l'analyse de la stabilité numérique de l'algorithme.

Pour $n=5$ , la valeur maximale observée numériquement depuis 1988 (via les logiciels NPSOL, LANCELOT, et plus récemment JuMP) est d'environ 4,1325. Cependant, la nature exacte de ce nombre et la preuve qu'il s'agit bien du maximum absolu restaient inconnues en raison de la complexité combinatoire des contraintes d'inégalités polynomiales impliquées.

2. Méthodologie

Les auteurs proposent une approche hybride innovante combinant optimisation numérique, algèbre symbolique exacte et arithmétique d'intervalles. Leur méthode se décompose en deux axes principaux :

A. Approche « JuMP + Base de Gröbner + Polynôme Discriminant » (Pour les bornes inférieures)

Cette méthode vise à prouver que la valeur observée numériquement est la racine exacte d'un polynôme à coefficients entiers, et qu'elle est optimale sous un ensemble spécifique de contraintes d'égalité.

Optimisation Numérique (JuMP) : Utilisation du logiciel d'optimisation JuMP (Julia) pour identifier une structure de contraintes d'égalité (où certains pivots ou éléments de matrice sont égaux en valeur absolue) qui maximise le facteur de croissance.
Élimination Symbolique (Base de Gröbner) : Une fois la structure de contraintes fixée par l'optimisation numérique, les auteurs utilisent des bases de Gröbner pour éliminer les variables non linéaires dépendantes et réduire le système à un nombre minimal de variables.
Optimisation Exacte (Polynôme Discriminant) : Pour trouver le maximum exact sous ces contraintes, ils calculent le discriminant d'un polynôme résultant par rapport à une variable de paramétrage. Les racines de ce discriminant fournissent les candidats pour les extrema locaux.
Résultat : Cette procédure permet de transformer une valeur numérique approchée en une expression algébrique exacte.

B. Analyse Mathématique et Arithmétique d'Intervalles (Pour les bornes supérieures)

Pour améliorer la borne supérieure théorique, les auteurs utilisent une méthode de type « branch-and-bound » (découpage et élagage) couplée à l'arithmétique d'intervalles.

Réduction du problème : Ils décomposent le problème $5 \times 5$ en étudiant les sous-matrices $3 \times 3$ qui apparaissent après deux étapes d'élimination.
Construction de couvertures : Ils génèrent des ensembles de boîtes dyadiques (intervalles) couvrant toutes les matrices $3 \times 3$ normalisées ayant un facteur de croissance élevé ( $\ge 2,15$ ou $2,2$).
Test d'incompatibilité : Ils prouvent mathématiquement que certaines combinaisons de matrices $3 \times 3$ à fort facteur de croissance sont incompatibles avec la structure d'une matrice $5 \times 5$ à pivots complets.
Vérification rigoureuse : L'arithmétique d'intervalles garantit que les calculs numériques ne contiennent aucune erreur d'arrondi, assurant la validité mathématique de la borne supérieure.

3. Contributions et Résultats Clés

Pour $n=5$

Valeur Exacte : Les auteurs démontrent que la valeur observée de 4,132517... est exactement la racine réelle unique dans l'intervalle $[4, 5]$ $[4, 5]$ d'un polynôme de degré 61 à coefficients entiers (dénommé $P_5(g)$ $P_{5} (g)$ ).
- Ce polynôme est fourni explicitement dans l'article.
- Les coefficients de ce polynôme sont extrêmement grands, illustrant la complexité algébrique du problème.
Conjecture : Ils émettent la Conjecture 2.1 : ce nombre (racine du polynôme de degré 61) est non seulement la borne inférieure pour une sous-classe de matrices, mais bien le facteur de croissance maximal absolu pour toute matrice $5 \times 5$ à pivots complets.
Borne Supérieure Améliorée : Ils réduisent la borne supérieure théorique de $4 \frac{17}{18} \approx 4,944$ (établie par Tornheim en 1969) à 4,84. Bien que cette amélioration soit modeste, elle démontre la viabilité de nouvelles techniques pour réduire l'écart avec la conjecture.

Pour $n=6, 7, 8$

La même méthode est appliquée aux dimensions supérieures, produisant de nouvelles bornes inférieures (suspectées être des maxima) :

$n=6$ : Le facteur de croissance est exactement 5.
$n=7$ : Le facteur de croissance est la racine d'un polynôme de degré 6 ( $P_7(g) = 3g^6 - 86g^5 + \dots$ ), valant environ 6,0569.
$n=8$ : Le facteur de croissance est 8, atteint par la matrice de Hadamard de Sylvester (et d'autres matrices non-Hadamard découvertes récemment).

4. Signification et Impact

Nature Algébrique du Problème : L'article révèle que le facteur de croissance maximal pour $n=5$ n'est pas un nombre transcendantal ou une constante simple, mais un nombre algébrique de degré élevé (61). Cela contredit l'intuition selon laquelle les solutions de problèmes d'optimisation numériques simples devraient avoir des formes algébriques simples.
Nouvelle Méthodologie : La fusion de l'optimisation numérique (pour explorer l'espace des solutions et identifier les contraintes actives) et de l'algèbre symbolique exacte (pour prouver l'optimalité et trouver la forme fermée) constitue une avancée méthodologique majeure. Elle permet de traiter des problèmes où l'explosion combinatoire rendrait une approche purement symbolique impossible.
Hommage à Nick Higham : Le papier est dédié à la mémoire de Nick Higham, un expert éminent en analyse numérique, qui a longuement étudié ce problème. Les auteurs regrettent de ne pas avoir pu lui présenter ces résultats de son vivant.
Perspectives : Bien que la conjecture pour $n=5$ ne soit pas encore prouvée rigoureusement pour toutes les configurations possibles (en raison de l'explosion combinatoire des structures d'égalité), les résultats fournis sont considérés comme la preuve la plus solide à ce jour. Le papier suggère que la résolution complète du problème pour $n=5$ nécessitera probablement une fusion encore plus poussée des mathématiques et du calcul haute performance.

En résumé, cet article transforme une question numérique ouverte depuis des décennies en un problème algébrique précis, fournissant une description exacte du facteur de croissance maximal pour $n=5$ et des bornes rigoureuses pour les dimensions supérieures.