Année 2023-24 - Equipe PEIPS (CMAP)¶
Groupe de Travail Discrete Random Objects: Limits and EStimates¶
Résumé de la séance 9 - Preuve de la conjecture de sensibilité ¶
Orateur : Théo Lenoir (résumé par Ariane Carrance)¶
Sommaire¶
Notations¶
On note
- $Q^n$ l'hypercube $n$-dimensionnel $\{0,1\}^n$
- $S_n(\mathbb{R})$ l'ensemble des matrices réelles de dimension $n$
- pour $M \in S_n(\mathbb{R})$, $\lambda_1(M) \geq \dotsm \geq \lambda_n(M)$ ses valeurs propres ordonnées.
Et on appelle fonction $n$-booléenne toute fonction $f: \{-1,1\}^n \to \{-1,1\}$. Dans ce qui suit, $f$ désigne une fonction $n$-booléenne.
Explication de la conjecture¶
En informatique, il est important d'estimer si deux mesures de complexité $A,B$ sont équivalentes, c'est-à-dire :
$\exists C,C',k,k'\ \ \forall x \ \ A(x)\leq CB(x)^k, \, B(x)\leq C'A(x)^{k'}$. En effet, dans ce cas, tout algorithme polynomial en $A$ sera polynomial en $B$, et réciproquement. Pour les fonctions booléennes, il y a deux mesures notables de leur complexité : la sensibilité et la bloc-sensibilité.
La sensibilité de $f$ en $x \in \{-1,1\}^n$ est le nombre de voisins $y$ de $x$ (i.e., les points de $\{-1,1\}^n$ qui diffèrent de $x$ par une seule coordonnée) tels que $f(y)\neq f(x)$. On la note $s(f,x)$.
La sensibilité de $f$ est $s(f):=max_{x\in \{-1,1\}^n}s(f,x)$.
La bloc-sensibilité de $f$ en $x \in \{-1,1\}^n$ est le plus grand $k$ tel que $\exists B_1, \dots, B_k$ disjoints, inclus dans $\{1, \dots, n\}$, tels que $f(x)\neq f(x^{(B_i)})$ $\forall 1\leq i \leq k$ (où $x^{(B_i)}$ signifie qu'on a changé les coordonnées de $x$ dont les indices sont dans $B_i$). On la note $Bs(f,x)$.
La bloc-sensibilité de $f$ est $Bs(f):=max_{x\in \{-1,1\}^n}Bs(f,x)$.
En considérant des blocs de taille 1, on obtient :
Nisan et Szegedy conjecturent en 1994 [NS94] que la bloc-sensibilité est également bornée par une fonction polynomiale de la sensibilité, ce qui impliquerait que les deux sont équivalentes. Cela a été prouvé par Huang en 2019 :
Pour expliquer comment Huang a prouvé ce résultat, nous avons besoin de présenter quelques propriétés des fonctions booléennes.
preuve :
Il suffit de montrer que le système $\{\sum_I\alpha_I\prod_{i \in I}x_i=f(x)\}$ a au plus une solution. En effet, c'est un système linéaire constitué de $2^n$ équations (une par $x \in \{-1,1\}^n$) et avec $2^n$ inconnues (les $\alpha_I$). Or, si $(\alpha_I)$ est solution, alors, pour tout $I \subset \{1, \dots, n\}$, on a :
$$\sum_{x\in\{-1,1\}^n} f(x)\prod_{i \in I}x_i=\sum_{x\in\{-1,1\}^n} \sum_{J \subset\{1, \dots, n\}} \alpha_J \prod_{i \in I} x_i\prod_{j \in J} x_j=\sum_J\alpha_J\sum_{x\in\{-1,1\}^n} \prod_{i \in I} x_i\prod_{j \in J} x_j=\sum_J 2^n 1_{I=J}\alpha_I=2^n\alpha_I$$
donc on a bien unicité de la solution.
Pour $f$ booléenne, on note $deg(f)$ le degré de la fonction polynomiale associée. On a :
Remarque : une première borne avec un facteur 2 avait été prouvée par Nisan et Szegedy [NS94].
Un autre résultat préliminaire important est le suivant :
(a) $\forall n \ \ \forall H \subset Q^n$ t.q. $|H|\neq 2^{n-1}$, $\max(\max_{x \in H}deg_H(x),\max_{x \in H^c}deg_{H^c}(x))\geq h(n)$
(b) $\forall f$ booléenne $s(f)\geq h(deg(f))$.
Pour prouver la conjecture de sensibilité, nous allons montrer que la première assertion est vraie pour $h=\sqrt{\cdot}$.
Théorème sur l'hypercube¶
D'après ce qui précède, pour prouver la conjecture de sensibilité, il suffit ainsi de montrer le résultat suivant :
$\forall n \geq 2\ \ \forall V \subset Q^n$ t.q. $|V|=2^{n-1}+1 \ \ \max_{x \in V}deg_V(x)\geq \sqrt{n}$.
En effet, cela suffit pour montrer que l'assertion (a) est vraie pour $h=\sqrt{\cdot}$, car * (a) est croissante pour l'inclusion, donc elle sera aussi vérifiée pour tout $|V|\geq 2^{n-1}+1$ * (a) est stable par passage au complémentaire, donc elle sera aussi vérifiée pour $|V|<2^{n-1}$.
Pour démontrer ce théorème, la preuve de Huang passe par plusieurs lemmes :
Pour $M \in S_n(\mathbb{R})$, $$\lambda_k(M)=\sup_{E \text{ s.e.v. de dim }k \subset\mathbb{R}^n}\inf_{\lVert x \rVert=1, x \in E}(Mx,x)$$.
preuve :
Soit $(e_1, \dotsm, e_n)$ une base orthonormée de vecteurs propres associés à $(\lambda_1(M), \dotsm, \lambda_n(M))$. En prenant $E=Vect(e_1, \dotsm, e_k)$, on a $\inf_{\lVert x \rVert=1, x \in E}(Mx,x)=\lambda_k(M)$, ce qui donne la première inégalité.
Pour avoir la deuxième inégalité, prenons $F$ un sous-espace-vectoriel de dimension $k$. Alors $F'=F \cap Vect(e_k,\dotsm,e_n) \neq \{0\}$, donc il existe $y \in F'$ avec $\lVert y \rVert=1$, et $(My,y)\leq \lambda_k\lVert y\rvert^2=\lambda_k$. Donc $\lambda_k\geq \inf_{x\in F, \lVert x \rVert=1}(Mx,x)$, ce qui donne la deuxième inégalité.
Soit $M \in S_n(\mathbb{R})$, et $\tilde{M}$ une sous-matrice principale de $M$, de taille $m$. Alors :
(1) $\lambda_i(M)\geq \lambda_i(\tilde{M}) \ \ \forall \, 1\leq i \leq m$
(2) $\lambda_i(\tilde{M})\geq \lambda_{n-m+i}(M) \ \ \forall \, m+1\leq i\leq n$.
preuve :
(1) : Soient $i_1<\dotsm<i_m$ les indices des colonnes restantes dans $\tilde{M}$, alors : $$\lambda_i(\tilde{M})=\sup_{E \text{ sev de dim }k \subset Vect(e_{i_1}, \dotsm,e_{i_m}}\inf_{x \in E}(Mx,x)\leq \lambda_i(M)$$.
(2) : même argument pour $-M$ et $-\tilde{M}$: $$\lambda_i(-M)\geq\lambda_i(-\tilde{M})\iff-\lambda_{n+1-i}(M)\geq -\lambda_{m+1-i}(\tilde{M})\iff \lambda_{n+1-i}(M)\leq\lambda_{m+1-i}(\tilde{M}) \iff \lambda_i(\tilde{M})\geq\lambda_{n-m+i}(M).$$
Soit $$ A_1:= \begin{pmatrix} 0 & 1 \\ 1& 0 \end{pmatrix}, $$ et $$ A_{n+1}:= \begin{pmatrix} A_n & I_{2^n} \\ I_{2^n} & -A_n \end{pmatrix}. $$ Alors $A_n$ a pour valeurs propres $\sqrt{n}$ et $-\sqrt{n}$ avec multiplicités $2^{n-1}$.
preuve :
On montre facilement par récurrence que $An^2=nI_{2^n}$, ce qui implique que $A_n$ est diagonalisable à spectre $\subset\{\pm\sqrt{n}\}$. De plus, on peut aussi montrer par récurrence que $tr(A_n)=0$, donc $\sqrt{n}$ et $-\sqrt{n}$ ont la même multiplicité.
Soit $H$ un graphe (fini non orienté) avec $m\leq n$ sommets et $A\in S_n(\mathbb{R})$ telle que $|A|$ soit la matrice d'adjacence de $H$. Alors : $\max_{x \in H} deg_H(x)\geq \lambda_1(A)$.
preuve :
Soit $V$ un vecteur propre associé à $\lambda_1=\lambda_1(A)$ tel que $|V_i|=\lVert V \rVert_{\infty}$. Alors $$|\lambda_1V_i|=|(AV)_i|=|\sum_{j=1}^nA_{i,j}V_j|\leq\lVert V \rVert_{\infty}\sum_{j=i}^n|A_{i,j}|=\lVert V \rVert_{\infty}deg(i)$$ donc $\max deg\geq\lambda_1(A)$.
preuve du théorème :
On peut vérifier que les valeurs absolues de la matrice $A_n$ du Lemme 2 donnent une matrice d'adjacence de $Q^n$. Par le Lemme 2, $\lambda_i(A_n)=\sqrt{n}$ pour $1\leq i \leq 2^{n-1}$, et $\lambda_i(A_n)=-\sqrt{n}$ pour $2^{n-1}+1\leq i \leq 2^{n}$. Puis, par le Lemme 3, pour $H \subset Q^n$ t.q. $|H|=2^{n-1}+1$, la matrice d'adjacence de $H$ est la valeur absolue d'une sous-matrice $A_H$ de $A_n$, donc $\max_{x \in H} deg_H(x) \geq \lambda_1(A_H)$. Enfin, par le Lemme 1, $\lambda_1(A_H)\geq \lambda_{2^n-(2^{n-1}+1)+1}(A_n)=\lambda_{2^{n-1}}(A_n)=\sqrt{n}$.
Références¶
[GL92] C. Gotsman, N. Linial, The equivalence of two problems on the cube, Journal of Combinatorial Theory Series A 61, No. 1, pp142-146 (1992).
[NS94] N. Nisan, M. Szegedy, On the degree of Boolean functions as real polynomials, Computational Complexity 4, No. 4, pp 301-313 (1994).
[Tal13] A. Tal, Properties and applications of boolean function composition, Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ITCS ’13, pp 441–454 (2013).
[Hua19] H. Huang, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, Annals of Mathematics (2) 190, No. 3, pp 949-955 (2019).