Autour du théorème 5K de Banaszczyk

La discrépance $\beta(U,V)$ entre deux compacts convexes $U$ et $V$ de l’espace euclidien, mesure combien on doit dilater $V$, dans le pire des cas, pour faire tenir une somme signée d’éléments arbitraires de $U$. Un célèbre résultat de Spencer énonce que $\beta(Q_d, Q_d) \leq 6 d^{1/2}$, où $Q_d=[-1,1]^d$.  Le problème de Komlos est d’estimer (asymptotiquement) $\beta(B_2^d, Q_d)$ : la méthode de Spencer donne ici une majoration en $O(\log d)$.

Le théorème 5K de Banaszczyk implique une majoration en $(\log d)^{1/2}$, qui a été récemment améliorée par Bansal-Jiang. Nous donnerons une preuve analytique du théorème 5K, qui suit pour l’essentiel la preuve originelle, puis nous énoncerons la reformulation de Dadush et al. qui a permis une preuve algorithmique (et probabiliste) de cet énoncé.