Résumé Technique : Randomstrasse101 – Problèmes Ouverts de 2025

Auteurs : Afonso S. Bandeira, Daniil Dmitriev, Kevin Lucca, Petar Nizić-Nikolac, Almut Rödder.
Contexte : Ce manuscrit compile seize problèmes ouverts (numérotés de 8 à 23 dans la série cumulative) issus du blog Randomstrasse101, dédié aux problèmes de théorie des probabilités, de calcul, de combinatoire et de statistiques. L'objectif est de fournir une référence stable pour les conjectures et problèmes discutés par le groupe du Département de Mathématiques de l'ETH Zurich en 2025.

Le document se concentre sur sept entrées principales (8 à 14), couvrant des sujets allant des inégalités de concentration tensorielles aux conjectures en géométrie convexe de haute dimension.

---

1. Inégalités de Concentration Tensorielle (Entrée 8)

Auteur : Kevin Lucca

• Problème : Déterminer des bornes supérieures pour l'espérance de la norme injective $\ell_p$ d'une somme de tenseurs aléatoires gaussiens. Plus précisément, on cherche à borner $E[\|\sum g_i T_i\|_{I_p}]$, où $T_i$ sont des tenseurs déterministes symétriques et $g_i$ des variables gaussiennes i.i.d.
• Conjecture 16 : Pour $p \ge 2$, l'espérance est bornée par $\tilde{O}_{r,p}(d^{1/2 - 1/p} \sqrt{\sum \|T_i\|_{I_p}^2})$.
• Méthodologie et État de l'art :
  • Le cas $r=p=2$ (matrices) est bien compris grâce aux inégalités de Khintchine non commutatives et aux techniques de traces.
  • Pour les tenseurs généraux ($r > 2$), l'approximation par les traces échoue car le calcul des normes injectives est NP-dur.
  • L'approche repose sur la théorie des processus gaussiens et l'intégrale d'entropie de Dudley, nécessitant le contrôle du nombre de recouvrement $N(B^d_p, D, \epsilon)$.
• Résultats Clés :
  • Une borne dimension-free a été obtenue pour $p \ge 2r$ (dans [BGJ+24]).
  • Le cas $p < 2r$ reste ouvert en raison d'obstacles volumétriques.
  • Des travaux récents (Aden-Ali, Boedihardjo) ont affiné les bornes pour des cas spécifiques (entrées indépendantes, tenseurs de Hankel), mais la conjecture générale pour les tenseurs non homogènes reste un défi majeur.

2. Le Nombre de Lovász des Graphes Circulants Aléatoires (Entrée 9)

Auteur : Daniil Dmitriev

• Problème : Caractériser le comportement asymptotique du nombre de Lovász $\vartheta(G)$ pour les graphes circulants aléatoires denses, un modèle intermédiaire entre les graphes aléatoires d'Erdős-Rényi $G(n, 1/2)$ et les graphes de Paley déterministes.
• Conjecture 18 : Pour un graphe circulant aléatoire $G$, $E[\vartheta(G)] = (1+o(1))\sqrt{n}$.
• Méthodologie :
  • Utilisation de la dualité forte pour reformuler le problème de programmation semi-définie (SDP) du nombre de Lovász en programmes linéaires (LP) dans les domaines "temps" et "fréquence".
  • Exploitation de la diagonalisation des matrices circulantes par la Transformée de Fourier Discrète (DFT).
  • Application de la propriété d'isométrie restreinte (RIP) de la matrice DFT sous-échantillonnée.
• Résultats :
  • Une borne inférieure précise et une borne supérieure en $O(\sqrt{n} \log \log n)$ ont été établies dans [BBD+25].
  • Cela suggère que les graphes circulants aléatoires partagent les propriétés pseudo-aléatoires des graphes d'Erdős-Rényi concernant le nombre de Lovász.

3. Injectivité et Stabilité du "Phase Retrieval" (Entrée 10)

Auteur : Afonso S. Bandeira

• Problème : Reconstruire un vecteur $x$ à partir de mesures de module $|Ax|$. La question centrale est l'injectivité de l'application et la stabilité de la reconstruction.
• Conjectures et Problèmes :
  • Conjecture 19 (Vinzant) : Pour $N = 4M-5$ mesures complexes, l'injectivité n'est pas garantie avec probabilité 1, et la probabilité d'injectivité tend vers 0 quand $M \to \infty$.
  • Conjecture 20 (Balan-Wang) : La stabilité est liée à la condition de complémentarité. Il existe une constante $\beta$ telle que le paramètre de stabilité $\omega(A)$ est borné par le maximum des normes des lignes de $A$.
  • Problème Ouvert 21 : Déterminer la valeur exacte de $\omega(A)$ pour des matrices gaussiennes et identifier l'exposant $\beta$.
• Signification : Ces problèmes sont cruciaux pour la physique quantique et l'imagerie, où seules les intensités (modules) sont mesurables.

4. Bases Mutuellement Non-Biaisées (MUB) et Conjecture de Zauner (Entrée 11)

Auteur : Afonso S. Bandeira

• Problème : Déterminer le nombre maximal de bases mutuellement non-biaisées (MUB) dans $\mathbb{C}^d$, noté $MUB(d)$.
• Conjecture 22 : $MUB(6) < 7$. C'est le cas ouvert le plus célèbre (d=6 n'est pas une puissance de nombre premier).
• Approche : Utilisation de preuves "Sum-of-Squares" (SoS). Il est connu que le niveau 2 ne suffit pas ; le problème ouvert 23 demande s'il existe une preuve de degré 4.
• Lien avec les ETF : Les MUB sont liés aux Equiangular Tight Frames (ETF). La Conjecture de Zauner (24) postule l'existence d'un ETF avec $d^2$ vecteurs pour toute dimension $d$ (SIC-POVMs).
• Avancées récentes : Des constructions conditionnelles basées sur des conjectures de théorie des nombres (conjectures de Stark) ont été proposées, mais une preuve inconditionnelle manque toujours.

5. Nombre de Clique du Graph de Paley (Entrée 12)

Auteur : Afonso S. Bandeira

• Problème : Estimer le nombre de clique $\omega(G_p)$ du graphe de Paley (déterministe mais pseudo-aléatoire).
• Conjecture 25 : $\omega(G_p) = O(\text{polylog}(p))$, contrairement aux graphes aléatoires où il est logarithmique.
• Méthodologie :
  • Utilisation de relaxations convexes (nombre de Lovász $\vartheta$) et de localisations itératives (sous-graphes induits par les voisins).
  • Conjectures 26 et 27 suggèrent que les localisations améliorent les bornes (ex: $\vartheta(G_{p,2}) \le \frac{2}{3}\sqrt{p}$).
  • Conjecture 28 : La relaxation SoS de degré 4 pourrait améliorer la borne $\sqrt{p}$ vers $O(p^{1/2-\epsilon})$.
• Lien avec la récupération compressée : La conjecture est liée à la propriété RIP (Restricted Isometry Property) des cadres de Paley au-delà de la limite de la racine carrée (Conjecture 29).

6. La Conjecture KLS et ses Implications (Entrée 13)

Auteur : Almut Rödder

• Problème : La conjecture de Kannan-Lovász-Simonovits (KLS) concerne la constante isopérimétrique $\psi_\mu$ des mesures log-concaves. Elle postule que cette constante est bornée inférieurement par une constante universelle (indépendante de la dimension), atteinte par des demi-espaces.
• Implications :
  • Inégalité de Poincaré.
  • Concentration de Lipschitz.
  • Temps de mélange des chaînes de Markov (Ball Walk) sur des corps convexes ($\tilde{O}(n^2)$).
• État de l'art (2025) :
  • La borne inférieure a progressé de $n^{-1/2}$ à $n^{-1/4}$, puis à une borne quasi-polynomiale $e^{-\sqrt{\log n}}$ (Chen, 2021), et enfin à $C (\log n)^{-1/2}$ (Klartag, 2023).
  • Résolution récente : La conjecture de la "Coquille Mince" (Thin Shell Conjecture) a été prouvée par Klartag et Lehec en 2025, ce qui implique la meilleure borne actuelle pour KLS.
  • Lien avec le problème de tranchage (Slicing Problem) : Résolu par Klartag et Lehec fin 2024, ce problème est équivalent à la conjecture KLS via la transformée de Laplace log.

7. Bornes Précises pour les Matrices de Graphes (Entrée 14)

Auteur : Petar Nizić-Nikolac

• Problème : Comprendre le spectre des matrices aléatoires apparaissant dans les hiérarchies de Sum-of-Squares (SoS) pour des problèmes comme le "Planted Clique". Ces matrices sont des "matrices de graphes" (Graph Matrices).
• Contexte : Les bornes de norme actuelles contiennent souvent des facteurs polylogarithmiques inutiles ($(\log n)^g$).
• Conjecture 31 (Bornes Précises) : La norme attendue d'une matrice de graphe associée à une forme $\alpha$ est de la forme $\Theta(n^{f(\alpha)} (\log n)^{g(\alpha)})$. L'objectif est de déterminer exactement les fonctions $f$ et $g$.
• Méthodologie :
  • Utilisation de la théorie des "Matrix Chaoses" (polynômes de variables aléatoires).
  • Application d'inégalités de concentration matricielles itérées (basées sur l'inégalité de Khintchine non commutative).
  • L'approche vise à éliminer les facteurs polylogarithmiques superflus pour certaines formes, améliorant ainsi les bornes inférieures pour les algorithmes SoS.

---

Signification Globale et Contributions

Ce manuscrit synthétise l'état de l'art de plusieurs domaines interconnectés en mathématiques appliquées et théoriques en 2025 :

1. Interdisciplinarité : Il met en lumière les liens profonds entre la théorie des probabilités (concentration), la géométrie convexe (KLS, isopérimétrie), la théorie des graphes (Paley, circulants), l'algèbre linéaire numérique (matrices de graphes, ETF) et l'informatique théorique (complexité des algorithmes SoS, récupération compressée).
2. Avancées Récentes : Le document note des percées majeures survenues en 2024-2025, notamment la résolution du problème de tranchage de Bourgain et de la conjecture de la coquille mince, qui ont des répercussions directes sur la conjecture KLS.
3. Outils Méthodologiques : Il souligne l'évolution des techniques, passant des méthodes classiques (traces, localisation) vers des approches plus sophistiquées comme la localisation stochastique, les matrices chaotiques, et les preuves par sommes de carrés (SoS).
4. Objectif : En formalisant ces problèmes ouverts, les auteurs visent à guider la recherche future, en particulier pour ceux qui cherchent à prouver ou réfuter ces conjectures, offrant un point de référence stable pour la communauté académique.