Contexte et revendication d'OpenAI

Dans le dépôt math publié récemment, OpenAI avance qu’une variante du Fast Fourier Transform (FFT) aurait un terme logarithmique légèrement inférieur à celui du classique Cooley‑Tukey. L’article de Ben Recht rappelle que le FFT standard réalise la transformée discrète en moins de 5 n log₂ n opérations arithmétiques, contre n² dans la version naïve. Pour n=1 000, cela représente un gain de 20 fois ; pour n=1 000 000, le gain dépasse 10 000 fois. La prétendue amélioration d’OpenAI se situe donc dans la constante cachée du facteur log n, non dans l’ordre asymptotique.

Analyse de la complexité et des constantes

Le texte critique l’usage abusif du big‑O. Un algorithme déclaré T(n)=O(n) peut cacher une constante C de taille astronomique. L’auteur cite une estimation de C≈10¹⁰⁰ pour n=10¹², ce qui rend le nouveau FFT « galactique ». Même si, théoriquement, O(n) est inférieur à O(n log n), le facteur 10¹⁰⁰ implique que le Cooley‑Tukey resterait 10⁹⁹ fois plus rapide pour n=10¹⁰⁰. Ainsi, la supériorité asymptotique ne se traduit jamais en avantage pratique.

Limitations pratiques et exigences de précision

Le modèle de calcul décrit par OpenAI repose sur une arithmétique complexe exacte. Il suppose la capacité de stocker et de multiplier des nombres complexes dont les amplitudes croissent de façon superpolynomiale avec n. En représentation binaire, la taille mémoire de ces nombres serait exponentielle par rapport à la longueur d’entrée, ce qui dépasse largement les capacités des ordinateurs actuels. Aucun matériel ne peut réaliser une multiplication d’entiers de taille 10¹⁰⁰ en une opération unique, ce qui invalide l’hypothèse de base du théorème présenté.

Implications pour la recherche

Les « algorithmes galactiques » peuvent stimuler la théorie, mais leur utilité dépend de la capacité à réduire les constantes cachées. L’article de Recht souligne que, sans un modèle de calcul réaliste, la preuve de faisabilité asymptotique ne conduit pas à une implémentation exploitable. En l’état, la proposition d’OpenAI ne fournit ni données expérimentales ni analyse de la charge mémoire, rendant la comparaison avec le FFT de Cooley‑Tukey purement spéculative. Les chercheurs doivent donc rester prudents face aux revendications qui reposent sur des abstractions mathématiques détachées des contraintes matérielles.