Online Komlós converges to mean curvature flow

Résumé technique : Convergence du jeu de Komlós en ligne vers le flot de courbure moyenne

Énoncé du problème
Cet article étudie le comportement asymptotique du « jeu de Komlós en ligne », un jeu à somme nulle entre deux joueurs, Paul (un adversaire adaptatif) et Carol (une minimiseuse), joué sur $T$ tours dans $\mathbb{R}^m$.

• Configuration : À chaque tour $t$, Paul choisit un ensemble de $n$ vecteurs $\{a_{1,t}, \dots, a_{n,t}\}$ à l'intérieur de la boule unité euclidienne. Carol choisit de manière irrévocable des signes $\bar{\varepsilon}_t \in \{-1, 1\}^n$. Le vecteur d'état $y_t$ est mis à jour comme suit : $y_t = y_{t-1} + \sum_{i=1}^n \varepsilon_{i,t} a_{i,t}$, en partant de $y_0 = 0$.
• Objectif : Paul cherche à maximiser la norme $\ell_\infty$ finale $\|y_T\|_\infty$, tandis que Carol cherche à la minimiser. La valeur du jeu est notée $K_T(m, n)$.
• Contexte : Lorsque $T=1$, cela se réduit au problème classique de Komlós (lié à la conjecture de Komlós), où l'objectif est de borner la discrépance d'un lot unique de vecteurs. L'article se concentre sur le régime où $T \to \infty$, traitant le jeu comme une localisation du problème classique où le vecteur d'état devient grand et où la géométrie de la boule unité devient localement lisse.

Méthodologie
Les auteurs utilisent une approche de limite continue, jetant un pont entre la théorie de la discrépance combinatoire et la théorie des équations aux dérivées partielles (EDP) non linéaires et des solutions de viscosité.

1. Fonction de valeur et mise à l'échelle : Ils définissent une fonction de valeur $v(y, s)$ représentant l'issue du jeu avec $s$ tours restants. En introduisant une mise à l'échelle parabolique $w_\delta(x, t) = \delta v(x/\delta, t/\delta^2)$ avec $\delta = 1/\sqrt{T}$, ils transforment l'équation de programmation dynamique discrète en un schéma de différences finies.
2. Identification de l'EDP limite : Lorsque $\delta \to 0$, le schéma de différences finies converge vers une EDP parabolique non linéaire. L'étape clé consiste à analyser la limite de l'opérateur de Bellman :
   $$\max_A \min_{\bar{\varepsilon}} \delta^{-2} (w(x + \delta A\bar{\varepsilon}, t) - w(x, t))$$
   En utilisant le théorème de Banaszczyk (un analogue $\ell_2$ du théorème de Beck-Fiala), les auteurs caractérisent la limite du terme max-min. Ils montrent que pour $n \ge m-1$, ce terme converge vers un opérateur impliquant la somme des plus grandes courbures principales des ensembles de niveau de la solution.
3. Solutions de viscosité : L'équation limite est identifiée comme la formulation par ensemble de niveau d'un flot de courbure. Spécifiquement, pour $n \ge m-1$, l'équation est :
   $$\partial_t w + \frac{1}{2} |\nabla w| \text{div}\left(\frac{\nabla w}{|\nabla w|}\right) = 0$$
   Ceci est l'équation d'ensemble de niveau pour le flot de courbure moyenne (MCF). Les auteurs utilisent la théorie des solutions de viscosité (spécifiquement le principe de comparaison et les propriétés de stabilité) pour prouver la convergence des fonctions de valeur discrètes vers l'unique solution de viscosité de cette EDP.
4. Analyse du temps d'extinction : La valeur asymptotique du jeu est liée au temps d'extinction $\tau$ du corps convexe initial (le cube unité $[-1, 1]^m$) sous le flot de courbure correspondant. Les auteurs construisent des sous-solutions et des sur-solutions explicites en utilisant l'équation de la chaleur pour borner ce temps d'extinction.

Contributions clés et résultats

1. Théorème de la limite continue (Théorème 2.1) :
   Pour tout corps convexe à symétrie centrale $E$ et taille de lot $n \ge m-1$, la valeur du jeu de Komlós en ligne satisfait :
   $$\lim_{T \to \infty} \frac{K_T(m, n)}{\sqrt{T}} = \frac{1}{\sqrt{2\tau_n(E)}}$$
   où $\tau_n(E)$ est le temps d'extinction de $E$ sous le flot par la somme des $\min(n, m-1)$ plus grandes courbures principales. Pour $n \ge m-1$, il s'agit du flot de courbure moyenne standard.

2. Asymptotique dimensionnelle (Théorème 2.2) :
   L'article caractérise la croissance de la valeur du jeu par rapport à la dimension $m$. Lorsque $m, n \to \infty$ avec $n \ge m-1$ :
   $$(1-o(1))\sqrt{\log m} \le \lim_{T \to \infty} \frac{K_T(m, n)}{\sqrt{T}} \le (\sqrt{2} + o(1))\sqrt{\log m}$$
   Cela implique que le temps d'extinction $\tau$ du cube unité sous le MCF passe à l'échelle de $\Theta(1/\log m)$. Les bornes sont dérivées en comparant la solution du MCF à des solutions de l'équation de la chaleur linéaire avec des données terminales spécifiques.

3. Généralisation :
   Les résultats généralisent à des normes arbitraires $\|\cdot\|_E$ dans $\mathbb{R}^m$, et pas seulement à la norme $\ell_\infty$. L'EDP limite dépend de la géométrie de la boule unité $E$ de la norme choisie.

Signification et affirmations
L'article prétend établir un lien rigoureux entre le problème de l'équilibrage de vecteurs en ligne et les flux géométriques, spécifiquement le flot de courbure moyenne.

• Localisation : Les auteurs présentent leur résultat comme une « localisation » de la conjecture classique de Komlós. Alors que le problème classique ($T=1$) est un problème géométrique global, la limite pour $T \to \infty$ revient à zoomer sur la courbure locale de la boule unité, rendant le problème régi par la géométrie locale (la courbure) plutôt que par la structure combinatoire globale.
• Pont méthodologique : Ce travail s'appuie sur le cadre établi par Kohn et Serfaty, qui ont relié les jeux déterministes au MCF, mais l'étend au contexte de Komlós en ligne où l'adversaire dispose de plus de liberté (choisissant des vecteurs dans la boule plutôt que des cadres orthonormés). Cette extension repose crucialement sur les bornes de discrépance de Banaszczyk.
• Perspectives potentielles : Les auteurs expriment l'espoir que cette perspective d'EDP et l'utilisation de potentiels de l'équation de la chaleur pour les bornes inférieures puissent éclairer la conjecture de Komlós hors ligne et d'autres problèmes d'équilibrage de vecteurs, bien qu'ils déclarent explicitement ne pas avoir encore trouvé de connexion directe entre la limite $T \to \infty$ et la conjecture $T=1$. Ils notent que si les potentiels lisses (comme $\cosh$) sont standards pour les bornes supérieures en discrépance, l'utilisation de la solution de l'équation de la chaleur pour les bornes inférieures est moins courante dans ce cadre spécifique.

L'article ne propose pas de nouveaux algorithmes pour l'équilibrage de vecteurs ni ne prétend résoudre la conjecture de Komlós elle-même ; il fournit plutôt une caractérisation asymptotique de la valeur du jeu en ligne et un nouvel ensemble d'outils analytiques (solutions de viscosité et flux de courbure) pour étudier ces problèmes.