A compensated coupling bound for the average sensitivity of polynomial threshold functions

Résumé Technique : Une borne de couplage compensée pour la sensibilité moyenne des fonctions de seuil polynomiales

Énoncé du Problème
L'article traite du problème de la détermination d'une borne pour la sensibilité moyenne ($AS(f)$) des fonctions de seuil polynomiales (PTF). Une PTF est une fonction booléenne $f: \{-1, 1\}^n \to \{-1, 1\}$ définie comme le signe d'un polynôme réel $p$ de degré au plus $d$. La sensibilité moyenne est définie comme l'espérance du nombre de bits d'entrée qui, lorsqu'ils sont inversés, changent la sortie de la fonction :
$$AS(f) = \sum_{i=1}^n P\{f(X) \neq f(X^{\oplus i})\}$$
où $X$ est uniformément réparti sur le cube booléen $\Omega_n$. Bien que la conjecture de Gotsman–Linial (identifiant les maximisateurs symétriques exacts) ait été démontrée comme fausse, la recherche de bornes supérieures uniformes serrées demeure un sujet central de l'analyse des fonctions booléennes et de la complexité computationnelle. Un travail précédent par OpenAI [1] a établi une borne de $8d\sqrt{n}$, et une note antérieure des auteurs a affiné ce résultat avec un coefficient uniforme de 3,83.

Méthodologie
Les auteurs affinent l'argument de « graduation pondérée » (weighted-grading) développé initialement par OpenAI [1]. Cette approche réduit l'estimation de la sensibilité moyenne à un problème de couplage impliquant des variables aléatoires binomiales. Les contributions méthodologiques centrales de cet article sont :

1. Estimation de Couplage Compensé : Les auteurs introduisent un lemme probabiliste raffiné (Lemme 2) impliquant un « couplage compensé ». Ce lemme limite le second moment de la différence entre deux variables aléatoires ($U, V$) ayant des distributions identiques et un déplacement borné ($V - U \le a$). En introduisant une correction linéaire au potentiel de couplage, les auteurs éliminent la perte en degré au carré présente dans les bornes antérieures.
2. Estimation à Gamme Finie : L'article dérive une estimation à paramètres finis qui rend compte des dimensions $n$ et des degrés $d$ spécifiques, plutôt que de s'appuyer uniquement sur des approximations asymptotiques.
3. Construction de Couplage Binomial : Les auteurs construisent des couplages binomiaux spécifiques pour démontrer l'étroitesse de leur relaxation. Ils montrent que le coefficient dérivé est asymptotiquement optimal pour la relaxation spécifique qui n'utilise que les deux lois marginales, la contrainte de déplacement unilatérale et la comparaison de graduation par facteur deux existante.

Résultats Clés
L'article établit deux bornes principales pour une fonction de seuil polynomiale réelle $f$ de degré $d$ sur le cube booléen de dimension $n$ :

1. Borne Asymptotique Uniforme :
   $$AS(f) \le \frac{8}{\sqrt{2\pi}} d\sqrt{n} \approx 3.19 d\sqrt{n}$$
   Cette borne est valable uniformément pour toutes les dimensions $n$ et tous les degrés $d$.

2. Borne à Paramètres Finis Plus Forte :
   $$AS(f) \le \min\left\{n, \frac{8 d b_n (n + d)}{n + 2d}\right\}$$
   où $b_n = E|B_n - n/2|$ pour $B_n \sim \text{Bin}(n, 1/2)$. Cette formule capture explicitement la dépendance vis-à-vis de $n$ et $d$, montrant que le coefficient diminue à mesure que $d$ augmente par rapport à $n$.

Les auteurs prouvent également que le coefficient $8/\sqrt{2\pi}$ ne peut être amélioré en se contentant de borner le second moment sur tous les couplages avec des marginales binomiales et des contraintes de déplacement, établissant ainsi une barrière pour cette approche de relaxation spécifique.

Revendications et Signification
L'article positionne sa contribution comme un affinement de l'étape de probabilité au sein du cadre de graduation pondérée existant.

• Affinement : Le travail améliore le coefficient uniforme de 3,83 à $8/\sqrt{2\pi}$.
• Uniformité : La nouvelle borne est valide uniformément à travers les dimensions et les degrés, y compris dans les cas où le degré croît avec la dimension.
• Limites et Modestie : Les auteurs déclarent explicitement qu'ils n'affirment pas l'optimalité pour les fonctions de seuil polynomiales elles-mêmes. Ils précisent que les couplages construits démontrant l'étroitesse du coefficient peuvent ne pas provenir de réelles fonctions de seuil polynomiales. De plus, l'article ne prétend pas établir une priorité historique exhaustive, une revue par les pairs humaine indépendante ou une preuve formelle en Lean.
• Vérification : Les résultats sont soutenus par des inégalités analytiques et une vérification computationnelle extensive (vérifiant plus de 12 000 inégalités ponctuelles et 8 000 paires dimension-degré) utilisant l'arithmétique exacte et des bibliothèques standards, plutôt que des approximations en virgule flottante.

En résumé, l'article fournit une borne supérieure plus serrée et uniformément valide pour la sensibilité moyenne des PTF en affinant l'étape de couplage dans l'argument de graduation pondérée, tout en délimitant soigneusement la portée de ses affirmations d'optimalité concernant la relaxation spécifique utilisée.