\documentclass[12pt]{article}\usepackage[francais]{babel}
\usepackage{amssymb,amsmath}\usepackage[ansinew]{inputenc}
\addtolength{\voffset}{-2cm}
\addtolength{\textheight}{3cm}
\addtolength{\textwidth}{3cm}
\addtolength{\hoffset}{-1.5cm}
\newtheorem{lemme}{Lemme}
\newtheorem{theo}[lemme]{Th\'eor\`eme}
\newtheorem{ex}[lemme]{Exemple}
\newtheorem{cor}[lemme]{Corollaire}
\newtheorem{rem}[lemme]{Remarque}
\newtheorem{defi}[lemme]{D\'efinition}
\newenvironment{pf}{\begin{trivlist}\item[]{\bf Preuve}}
{\mbox{}\hfill\rule{.08in}{.08in}\end{trivlist}}
\def\n#1{\parallel #1\parallel}
\def\f{\mathbb{F}_p}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\ext{\texttt{Ext}}

\begin{document}
\title{Application des estim\'ees sommes-produits aux extracteurs, d'apr\`es Barak, Impagliazzo et Widgerson}
\author{Pierre Pansu}
\maketitle
\section{Objectif}

Exposer bri\`evement des r\'esultats r\'ecents, trouv\'es dans la litt\'erature informatique, qui utilisent l'estim\'ee somme-produit de Bourgain, Katz et Tao.

Aujourd'hui, c'est une construction d'extracteurs par Barak, Impagliazzo et Widgerson. Pour plus tard, une construction explicite de sous-espaces bien \'etal\'es dans $\R^N$ par Guruswami, Lee et Razborov. 


\section{Extracteurs}

Le probl\`eme suivant remonte \`a Von Neumann. Etant donn\'ee une source physique (compteur Geiger...) produisant des cha\^{\i}nes de bits al\'eatoires, dont la distribution est inconnue (mais pas trop exotique), comment, en leur appliquant un algorithme d\'eterministe, produire des cha\^{\i}nes de bits \'equir\'eparties, avec une pr\'ecision prescrite ?

L'algorithme d\'eterministe, c'est une application $\ext:\{0,1\}^m \to \{0,1\}^n$. La source, c'est une variable al\'eatoire $X$ \`a valeurs dans $\{0,1\}^m$, dont seule la loi, une mesure de probabilit\'e $\mu$ sur $\{0,1\}^m$, joue un r\^ole. Le g\'en\'erateur de bits al\'eatoires obtenu est la variable al\'eatoire $\ext\circ X$. Ce qui nous int\'eresse, c'est sa loi, i.e. la mesure image $\ext_* \mu$. Traditionnellement, on mesure le d\'efaut d'\'equir\'epartition par la distance $\ell^1$ \`a la distribution uniforme $U$.

\begin{defi}
La distance entre deux mesures de probabilit\'e $\mu$ et $\nu$ sur un ensemble fini est
\begin{eqnarray*}
dist(\mu,\nu)=\sum_{x}|\mu(\{x\})-\nu(\{x\})|.
\end{eqnarray*}
\end{defi}

Autrement dit, le probl\`eme consiste \`a trouver $\ext$ de sorte que $dist(\ext_* \mu,U)$ soit petit pour toutes les mesures $\mu$ d'une famille, la plus grande possible.

Si $\mu$ est fortement concentr\'ee en un point, il en est de m\^eme de $\ext_* \mu$, qui est donc tr\`es mal r\'epartie. Cela se mesure quantitativement au moyen de la min-entropie.

\begin{defi}
La {\em min-entropie} d'une mesure de probabilit\'e $\mu$ sur un ensemble fini est 
\begin{eqnarray*}
H^{\infty}(\mu)=\min\{-\log_2 \mu(\{x\})\,;\,\mu(\{x\})\not=0\}.
\end{eqnarray*}
\end{defi}

\begin{ex}
La min-entropie de toute mesure de probabilit\'e sur $\{0,1\}^n$ est $\geq n$, avec \'egalit\'e exactement pour la distribution uniforme.
\end{ex}

Clairement, la min-entropie diminue quand on remplace une mesure par son image par une application. D'autre part, la min-entropie est continue pour la distance $\ell^1$. Par cons\'equent, si l'image de $\mu$ est $2^{-N}$-proche de la distribution uniforme sur $\{0,1\}^n$, la min-entropie de $\mu$ vaut au moins $m-2^{n-N}$. Il est donc impossible d'am\'eliorer sensiblement une distribution de min-entropie inf\'erieure \`a $n$. 

\section{Extracteurs multi-sources}

On peut y arriver \`a condition d'utiliser plusieurs sources ind\'ependantes. En termes de mesures de probabilit\'es, la loi jointe de plusieurs variables al\'eatoires ind\'ependantes est un produit tensoriel de mesures. La famille de mesures consid\'er\'ee sur $\{0,1\}^m$ sera donc celle des produits tensoriels de $\ell$ mesures sur $\{0,1\}^{m'}$, o\`u $m=\ell m'$. 

Comment mesurer la qualit\'e d'un extracteur ? Le lemme \'el\'ementaire suivant montre que, si on s'autorise au moins un nombre quelconque (mais born\'e) de sources, on peut r\'eduire facilement l'\'ecart \`a l'\'equir\'epartition.

\begin{lemme}
\label{conv}
Soient $\mu$ et $\nu$ des mesures sur un groupe. Alors
\begin{eqnarray*}
dist(\mu\star\nu,U)\leq dist(\mu,U)dist(\nu,U).
\end{eqnarray*}
Par cons\'equent, si $dist(\mu,U)\leq 2^{-N}$, alors l'image $\mu^{\star \ell}$ de $\mu^{\otimes \ell}$ par l'extracteur $\sum:\{0,1\}^{\ell m'} \to \{0,1\}^{m'}$, $(x_1 ,\ldots,x_\ell)\mapsto x_1 +\cdots +x_\ell$ satisfait $dist(\mu^{\star \ell},U)\leq 2^{-N\ell}$.
\end{lemme}

\begin{pf}
En effet, si $\mu=U+f$, $\nu=U+g$, $\mu\star\nu=U+f\star g$, et $\n{f\star g}_{1}\leq \n{f}_1 \n{g}_1$.
\end{pf}

\medskip

Ce qui compte donc, c'est plut\^ot le nombre de sources, et comment il d\'epend de la borne sur la min-entropie des sources. Il est commun\'ement admis que c'est une application tir\'ee au hasard parmi toutes les applications possibles $\sum:\{0,1\}^{\ell m'} \to \{0,1\}^{n}$ qui donne le meilleur r\'esultat comme extracteur multisource. Voici un exemple de r\'esultat sur la performance de tels extracteurs. Deux sources suffisent.

\begin{theo}
\label{random}
Pour tout $\delta>0$ il existe $C>0$ tel que, pour tout $m'$, tout $k\geq\delta \log(m)$ et tout $n\leq 2k-C\log(m')$, une application $\ext:\{0,1\}^{2m'} \to \{0,1\}^n$ tir\'ee au hasard poss\`ede, avec forte probabilit\'e, la propri\'et\'e suivante : si $\mu_1$ et $\mu_2$ sont des mesures de probabilit\'e de min-entropies $\geq k$ sur $\{0,1\}^{m'}$, alors 
\begin{eqnarray*}
dist(\ext_* (\mu_1\otimes\mu_2),U)<2^{-n/C}.
\end{eqnarray*}
\end{theo}

En d'autres termes, l'extracteur al\'eatoire extrait effectivement la quasi-totalit\'e de l'entropie des sources. Le th\'eor\`eme expos\'e aujourd'hui fait les choix suivants : $\ell$ ind\'ependant de $n$, $m'=n$, ce qui implique une min-entropie $\geq \delta n$ o\`u $0<\delta<1$ est ind\'ependant de $n$. Noter que $\ell$ est forc\'ement $\geq 1/\delta$.

\begin{theo}
\label{biw}
{\em \cite{BIW}}. Il existe une constante absolue $C$ telle que, pour tout $\delta>0$, il existe $\ell\leq \delta^{-C}$ et une application $\ext:\{0,1\}^{n\ell} \to \{0,1\}^n$ calculable en temps polyn\^omial tels que si $\mu_1 ,\ldots,\mu_\ell$ sont des mesures de probabilit\'e de min-entropies $\geq \delta n$, alors 
\begin{eqnarray*}
dist(\ext_* (\mu_1\otimes\ldots\otimes\mu_\ell),U)<2^{-n/C}.
\end{eqnarray*}
\end{theo}

Ce r\'esultat semble assez faible, en comparaison du r\'esultat randomis\'e. En effet, $\ell$ est grand par rapport \`a $1/\delta$, donc l'entropie est inutilement gaspill\'ee. N\'eanmoins, la preuve est int\'eressante.

La référence \cite{R} comporte, outre des améliorations de ce résultat obtenues par des méthodes différentes, un survol des constructions d'extracteurs multi-sources.

\section{Id\'ee de la preuve}

L'id\'ee de d\'epart est d'identifier $\{0,1\}^n$ au corps premier $\f$ et de consid\'erer l'application 
$$\ext:\f^3 \to\f,\quad(a,b,c)\mapsto ab+c.$$ 
De l'estim\'ee somme-produit, il r\'esulte que pour tout $A\in\f$ pas trop petit ni trop grand, $|\ext(A\times A\times A)|>|A|^{1+\epsilon}$. En it\'erant $\ext$ un nombre $\ell=O(\log(1/\delta))$ fois, on obtient $\ext^\ell:\f^{3^\ell} \to \f$ telle que $\ext^\ell (A^{3^\ell})=\f$ pour $A$ pas trop petit. C'est ce qu'on voulait, pour les mesures particuli\`eres proportionnelles aux fonctions caract\'eristiques des sous-ensembles.

Il reste \`a passer des sous-ensembles aux mesures. Attention, il n'y a pas d'estim\'ee somme-produit pour les mesures. En effet, la somme des fonctions caract\'eristiques d'une progression arithm\'etique et d'une progression g\'eom\'etrique donne une mesure de probabilit\'e $\mu$ dont les convol\'ees additive et multiplicative ont des min-entropies tr\`es petites. En revanche, la version plus faible suivante est vraie : la min-entropie de toute mesure augmente significativement quand on prend son image par $\ext$.

\begin{lemme}
\label{1}
Il existe une constante absolue $\epsilon>0$ telle que pour tout $p$, si $\mu$, $\nu$ et $\pi$ sont des mesures de probabilit\'e sur $\f$ de min-entropie au moins $m$, alors $\ext(\mu\otimes\nu\otimes\pi)$ est $2^{-\epsilon m}$-proche d'une mesure de min-entropie au moins \'egale \`a $\min\{(1+\epsilon)m,0.9\log|\f|\}$.
\end{lemme}

Pour compl\'eter la preuve du th\'eor\`eme \ref{biw}, il suffit d'\'etablir le lemme suivant.

\begin{lemme}
\label{2}
Soient $\mu_1 ,\ldots,\mu_9$ neuf mesures de probabilit\'e sur $\f$ de min-entropies au moins \'egales \`a $0.9\log|\f|$. Alors l'image de la mesure produit par $\ext^2$ est $|\f|^{-0.1}$-proche de la distribution uniforme.
\end{lemme}

On a trich\'e en identifiant $\{0,1\}^n$ au corps premier $\f$. En effet, actuellement, il n'existe aucun algorithme qui, en un temps polyn\^omial en $n$, retourne un nombre premier compris entre $2^n$ et $2^{n+1}$. N\'eanmoins, en d\'etournant une faible partie du hasard contenu dans les sources, et en utilisant le test de primalit\'e polyn\^omial d'Agrawal, Kayal et Saxena, on peut le faire. 

\section{Preuve du lemme \ref{1}}
 
Etant donn\'ee une mesure de probabilit\'e $\mu$, on note $cp(\mu)$ la {\em probabilit\'e de collision}, i.e. la probabilit\'e que deux \'el\'ements tir\'es ind\'ependamment suivant $\mu$ co\"{\i}ncident. En d'autres termes, $cp(\mu)$ est le carr\'e de la norme $\ell^2$ de $\mu$ vue comme fonction positive. Pour la mesure uniforme sur un sous-ensemble $A$, $cp(\mu_A)=|A|^{-1}$.

Pour qu'une mesure soit proche d'une mesure de grande min-entropie, il suffit que sa probabilit\'e de collision soit petite. De m\^eme, sur un grand ensemble, petite probabilit\'e de collision \'equivaut \`a \'equir\'epartition.

\begin{lemme}
\label{cp/me}
1. Si $cp(\mu)\leq 1/KL$, alors il existe une mesure de probabilit\'e $\nu$ telle que $dist(\mu,\nu)\leq 1/\sqrt{L}$ et $H^{\infty}(\nu)\geq\log K$. 

2. Pour toute mesure de probabilit\'e $\mu$ sur un ensemble \`a $N$ \'el\'ements, $\frac{1}{N}dist(\mu,U)^2 \leq cp(\mu)\leq \frac{1}{N}+dist(\mu,U)^2$.
\end{lemme}

\begin{pf}

1. $\nu$ est la restriction de $\mu$ aux points de masse $\leq 1/K$.

2. On \'ecrit $\mu=U+f$. Alors $\n{f}_1 =dist(\mu,U)$ et $cp(\mu)-\frac{1}{N}=\n{f}_2^2$ est minimale quand $|f|$ est constante, maximale quand $f$ est concentr\'ee en un point.
\end{pf}

\begin{lemme}
\label{3}
Il existe une constante absolue $\epsilon>0$ telle que pour tout $p$, et tout entier $M$, on a la propri\'et\'e suivante. Soit $A\subset\f$ un ensemble de taille $\geq M^{1-10\epsilon}$. On suppose qu'il existe un autre ensemble $B\subset\f$ de taille $\geq M^{1-10\epsilon}$ tel que $A\cdot B\leq M^{1+\epsilon}$. Alors pour tout ensemble $C$ de taille $M$,
\begin{eqnarray*}
cp(\mu_A+\mu_C)\leq M^{-1-10\epsilon}.
\end{eqnarray*}
\end{lemme}

\begin{pf}
du lemme \ref{3}. On combine l'estim\'ee somme-produit avec le lemme de Balog et Szemer\'edi revu par Gowers (qui dit que si $A+_E B$ est petit, on peut extraire de grands sous-ensembles $A'\subset A$ et $B'\subset B$ tels que $A'+B'$ est petit, le lien \'etant que $cp(\mu_A +\mu_B)$ grand entra\^{\i}ne que $A+_E B$ est petit pour un $E$ tr\`es grand) et un lemme de Rusza (qui dit que si $A$ et $B$ sont de tailles \'egales et $A+B$ est petit, alors $A+A$ est petit).

Retour \`a la preuve du lemme \ref{1}. Appelons {\em $+$-amicaux} les ensembles qui satisfont \`a la conclusion du lemme 2. Il y a un lemme 3 qui consiste \`a \'echanger addition et multiplication dans le lemme 2. Appelons {\em $\times$-amicaux} ceux qui satisfont \`a la conclusion du lemme 3. Alors, en utilisant Balog-Szemer\'edi-Gowers, on montre que toute partie de $\f$ est, \`a un sous-ensemble tr\`es petit pr\`es, partitionn\'e en un ensemble $+$-amical $A_+$ et un ensemble $\times$-amical $A_\times$. Puis on observe que $\mu_A \cdot\mu_B +\mu_C$ est proche d'une combinaison convexe de $\mu_{A_+} \cdot\mu_B +\mu_C$ et de $\mu_{A_\times} \cdot\mu_B +\mu_C$, qui ont chacune une faible probabilit\'e de collision.
\end{pf}

\section{Preuve du lemme \ref{2}}

Attention, on va utiliser des notations suggestives mais qui peuvent induire en erreur.

\textbf{Notation}. {\em Si $\mu$ et $\nu$ sont des mesures de probabilit\'e sur $\f$, on note $\mu+\nu$ (resp. $\mu\cdot\nu$) la convolution additive (resp. multiplicative).}

Avec ces notations, $\ext_* (\mu\otimes\nu\otimes\pi)=\mu\cdot\nu + \pi$.

Soient $\mu_1 ,\ldots,\mu_9$ des mesures de probabilit\'e sur $\f$ de min-entropies $\geq 0.9\log|\f|$, i.e. pour tout $x\in\f$, $\mu_i (x)\leq |\f|^{-0.9}$. Alors $cp(\mu_i)=\sum_x \mu_i (x)^2 \leq |\f|^{-1.8}|\f|=|\f|^{-0.8}$.

Sachant que pour toutes mesures $\mu$ et $\nu$, $cp(\mu+\nu)\leq cp(\mu)$ (moyenner une fonction n'augmente pas la norme $\ell^2$),
\begin{eqnarray*}
cp(\ext^2 (\mu_1 ,\ldots,\mu_9))\leq cp((\mu_1 \cdot\mu_2 +\mu_3)\cdot(\mu_4 \cdot\mu_5 +\mu_6)).
\end{eqnarray*}
Pour toutes mesures $\mu$, $\nu$ et $\pi$ et toute application $f:\f^2 \to \f$, $f_*((\mu\cdot\nu)\otimes\pi)$, vue comme une fonction, est une moyenne des fonctions $f_*((x\cdot\nu)\otimes\pi$ lorsque $x$ d\'ecrit $\f$, donc $cp(f_*((\mu\cdot\nu)\otimes\pi)\leq\max\{cp(f_*((x\cdot\nu)\otimes\pi)\,;\,x\in\f\}$. En particulier,
\begin{eqnarray*}
cp((\mu_1 \cdot\mu_2 +\mu_3)\cdot(\mu_4 \cdot\mu_5 +\mu_6))\leq\max\{cp((\mu_1 \cdot x +\mu_3)\cdot(\mu_4 \cdot y +\mu_6))\,;\,x,\,y\in\f\}.
\end{eqnarray*}

La preuve du lemme \ref{2} se ram\`ene donc au lemme suivant.

\begin{lemme}
\label{abcd}
Soient $\mu_1 ,\ldots,\mu_4$ quatre mesures de probabilit\'e sur $\f$ de probabilit\'es de collisions $\leq c$. Alors
\begin{eqnarray*}
dist((\mu_1 +\mu_2)\cdot(\mu_3 +\mu_4),U)\leq O(c^2 |\f|^{3/2}).
\end{eqnarray*}
\end{lemme}

\begin{pf}
du lemme \ref{abcd}.

On va montrer que $dist((\mu_1 +\mu_2)\cdot(\mu_3 +\mu_4)^{-1},U)\leq O(c^2 |\f|)$. Ensuite, il suffit de passer aux probabilit\'es de collision, car celles-ci satisfont $cp(\mu\cdot\nu)=cp(\mu\cdot\nu^{-1})$ (la probabilit\'e que $xy=x'y'$ est \'egale \`a la probabilit\'e que $xy'^{-1}=x'y^{-1}$), puis revenir \`a la distance \`a $U$, grâce \`a la deuxi\`eme partie du lemme \ref{cp/me}, le prix \`a payer est un facteur $|\f|^{1/2}$.

Quitte \`a transporter $\mu_2$ et $\mu_4$ par $x\mapsto -x$, on \'etudie $dist((\mu_1 -\mu_2)\cdot(\mu_3 -\mu_4)^{-1},U)$. On d\'emontre le cas particulier o\`u $\mu_2 =\mu_1$ et $\mu_3 =\mu_4$ (le cas g\'en\'eral s'en d\'eduit assez rapidement).

Soient $X_i$ des variables ind\'ependantes de lois $\mu_i$. Comme une probabilit\'e de collision est une norme $\ell^2$, elle est toujours $\geq 1/|\f|$. Par cons\'equent, pour tout $s\in\f\setminus\{0\}$,
\begin{eqnarray*}
p(X_1 +sX_3 =X_2 +sX_4)\geq \frac{1}{|\f|}.
\end{eqnarray*}
Or cet \'ev\`enement se produit seulement si $X_3 =X_4$ (ce qui entra\^{\i}ne que $X_1 =X_2$), ou bien si $s=(X_2 -X_1)/(X_3 -X_4)$. Par cons\'equent,
\begin{eqnarray*}
p(s=(X_2 -X_1)/(X_3 -X_4))+p(X_1 =X_2 \wedge X_3 =X_4)\geq  \frac{1}{|\f|}.
\end{eqnarray*}
Donc, pour $s\not=0$, $p(s=(X_2 -X_1)/(X_3 -X_4))\geq\frac{1}{|\f|}-c^2$, ce qui entra\^{\i}ne que $dist((\mu_1 -\mu_2)\cdot(\mu_3 -\mu_4)^{-1},U)\leq \frac{2}{|\f|}+2|\f|c^2$.
\end{pf}



\begin{thebibliography}{}

\bibitem[BKT]{BKT} Bourgain, Jean; Katz, Netz; Tao, Terry
\emph{A sum-product estimate in finite fields, and applications.}
Geom. Funct. Anal. \textbf{14} (2004), no. 1, 27--57. 

\bibitem[BIW]{BIW} Barak, Boaz; Impagliazzo, Russel; Widgerson, Avi
\emph{Extracting randomness using few independant sources.}
SIAM J. Comput. \textbf{36} (2006), 1095-1118.
Aussi : FOCS 2004 et
http://www.math.ias.edu/$\sim$avi/PUBLICATIONS/MYPAPERS/BIW04/BIW.pdf

\bibitem[R]{R} Rao, Anup,
\emph{Extractors for a constant number of polynomially small min-entropy independent sources}.
http://www.math.ias.edu/$\sim$arao/pubs/indep.pdf

\end{thebibliography}

\end{document}
