Lemme de Schwartz-Zippel

Ne doit pas être confondu avec Lemme de Schwarz.

En mathématiques, le lemme de Schwartz-Zippel est un résultat important pour évaluer l'égalité entre deux polynômes multivariés. Ce lemme donne naturellement un algorithme probabiliste efficace pour résoudre la question de l'égalité entre polynômes, qui fut historiquement le premier à être prouvé correct^[1]. De fait il possède de nombreuses applications en théorie des nombres, en cryptographie, en géométrie, mais également dans les problèmes issues de la théorie des graphes et en théorie de la complexité^[1].

Histoire

Le résultat lui-même a été redécouvert plusieurs fois de manière indépendante. En 1922 Øystein Ore publie une première version limitée aux corps finis^[2], puis Richard DeMillo et Richard Lipton publient une version faible en 1978^[3]. Le lemme sous sa forme (forte) actuelle est due simultanément à Jack Schwartz^[4] et Richard Zippel^[5] en 1979, qui l'ont présenté indépendamment à la même conférence^[6]. En dépit de ses nombreux auteurs, et bien que n'étant pas issu d'une collaboration entre eux, le résultat est le plus souvent simplement attribué à « Schwartz-Zippel. »

Énoncé du lemme

On se place dans un corps commutatif ${\displaystyle \mathbb {F} }$ et on considère un polynôme multivarié ${\displaystyle P\in \mathbb {F} [x_{1},\dotsc ,x_{n}]}$, non identiquement nul, de degré ${\displaystyle d\geq 0}$.

Soit ${\displaystyle S}$ un sous-ensemble fini non vide de ${\displaystyle \mathbb {F} }$. Si ${\displaystyle s_{1},s_{2},\dotsc ,s_{n}}$ sont des éléments tirés uniformément et indépendamment de ${\displaystyle S}$, alors

${\displaystyle \displaystyle \Pr \left[P(s_{1},\dotsc ,s_{n})=0\right]\leq \delta (n,d,|S|)}$

où la fonction ${\displaystyle \delta }$ est bornée par:

• ${\displaystyle d/|S|}$ dans la version forte du lemme (due à Schwartz);
• ${\displaystyle nd/|S|}$ dans la version faible du lemme (due à DeMillo, Lipton, et Zippel).

Note : dans le cas des corps finis ${\displaystyle \mathbb {F} _{q}}$, il est possible qu'un polynôme s'évalue toujours à zéro sans être nul pour autant, comme par exemple ${\displaystyle x^{2}-x\in \mathbb {F} _{2}[x]}$, rendant inopérant le résultat de Schwartz-Zippel ; cette situation est évitée en s'assurant que ${\displaystyle d<q}$.

Preuve du lemme

Nous allons démontrer la version forte, la version faible en découlant naturellement. La preuve s'obtient par récurrence sur ${\displaystyle n}$.

Le cas ${\displaystyle n=1}$ correspond simplement au fait qu'un polynôme de degré ${\displaystyle d}$ possède au plus ${\displaystyle d}$ racines dans ${\displaystyle \mathbb {F} }$. Cela se montre aisément par contradiction : s'il y avait plus de ${\displaystyle d}$ racines, on pourrait écrire ${\displaystyle P}$ comme un produit d'au moins ${\displaystyle d+1}$ facteurs de la forme ${\displaystyle (x_{1}-\alpha _{i})}$ et donc ${\displaystyle P}$ serait de degré au moins ${\displaystyle d+1}$, ce qui est faux. Ainsi le cas ${\displaystyle n=1}$ du théorème est établi.

On suppose alors que le résultat tient pour tous les polynômes en ${\displaystyle m<n}$ variables, et on procède ainsi : soit ${\displaystyle P\in \mathbb {F} [x_{1},\dotsc ,x_{n}]}$, on extrait la dépendance en ${\displaystyle x_{1}}$de la manière suivante :

${\displaystyle P(x_{1},\dotsc ,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\dotsc ,x_{n})}$

en notant que cela est possible car le corps est commutatif.

Tous les polynômes ${\displaystyle P_{i}}$ ne peuvent pas être nuls, car sinon ${\displaystyle P}$ serait identiquement nul, ce qui est faux. Soit alors ${\displaystyle m}$ le plus grand indice tel que ${\displaystyle P_{m}\neq 0}$. Par construction, le degré de ${\displaystyle x^{m}P_{m}}$ est au plus ${\displaystyle d}$, c'est-à-dire que le degré de ${\displaystyle P_{m}}$ est au plus ${\displaystyle d-m}$. L'hypothèse de récurrence donne alors :

${\displaystyle \Pr[P_{m}(s_{2},\dotsc ,s_{n})=0]\leq {\frac {d-m}{|S|}}}$

Si ${\displaystyle P_{m}}$ ne s'annule pas sur ${\displaystyle s_{2},\dotsc ,s_{n}}$, alors ${\displaystyle P}$ est au moins de degré ${\displaystyle m}$. Appliquant encore l'hypothèse de récurrence, on a ainsi

${\displaystyle \Pr \left[P(s_{1},\dotsc ,s_{n})=0\mid P_{m}(s_{2},\dots ,s_{n})\neq 0\right]\leq {\frac {m}{|S|}}}$

On conclut de la manière suivante : dénotons par ${\displaystyle A}$ l'événement correspondant à l'annulation de ${\displaystyle P}$, et par ${\displaystyle B}$ l'annulation de ${\displaystyle P_{m}}$. Les deux formules ci-dessus s'écrivent alors :

${\displaystyle \Pr[B]\leq (d-m)/|S|}$

${\displaystyle \Pr[A\mid {\overline {B}}]\leq m/|S|}$

Ce qui permet d'écrire

${\displaystyle {\begin{aligned}\Pr[A]&=\Pr[A|B]\Pr[B]+\Pr[A|{\overline {B}}]\Pr[{\overline {B}}]\\&\leq \Pr[B]+\Pr[A|{\overline {B}}]\\&\leq {\frac {d-m}{|S|}}+{\frac {m}{|S|}}\\&={\frac {d}{|S|}}\end{aligned}}}$

Ainsi on a montré que le théorème est vrai pour un polynôme en ${\displaystyle n}$ variables.

Test d'identité polynomiale

Le lemme de Schwartz-Zippel donne immédiatement un algorithme probabiliste pour tester la nullité d'un polynôme, ou l'égalité entre deux polynômes (on teste la nullité de leur différence). Il suffit en effet de tirer ${\displaystyle n}$ valeurs uniformément au hasard et d'évaluer le polynôme, quitte à réitérer la procédure jusqu'à atteindre le niveau de certitude souhaité.

Les meilleures méthodes déterministes pour résoudre ce problème, lorsque le polynôme est fourni sous forme par exemple d'un circuit arithmétique, sont de complexité exponentielle. L'utilisation d'un aléa permet donc un gain substantiel et fait du lemme de Schwartz-Zippel un outil important. Réciproquement, trouver un algorithme déterministe aussi efficace aurait des implications profondes sur la théorie de la complexité^[7],[8].

Si on considère une classe restreinte de polynômes (généralement exprimés comme des circuits arithmétiques contraints) alors quelques algorithmes déterministes efficaces sont connus, au moins pour la profondeur 2 et 3^[9],[10], ou des instances très creuses^[11]. La profondeur 4 est abordable uniquement pour des classes très réduites^[12].

Parmi les algorithmes probabilistes, celui de Schwartz-Zippel est le plus efficace connu, mais il présente le défaut de consommer beaucoup d'aléa. Il existe des variantes plus parcimonieuses, telles que l'algorithme de Chen et Kao^[13] ou Lewin et Vadhan^[8], qui utilisent moins de bits aléatoires mais ont une complexité plus grande.

Applications

• En théorie de la complexité. Le lemme joue un rôle clé dans la preuve par Adi Shamir de IP = PSPACE^[14], plus spécifiquement dans l'étape montrant que QSAT appartient à ABPP^[15].
• En théorie des nombres. Le test de primalité d'Agrawal-Biswas^[16] repose sur l'algorithme de Schwartz-Zippel pour tester l'égalité ${\displaystyle (1+z)^{n}=1+z^{n}{\bmod {n}}}$, qui vaut lorsque ${\displaystyle n}$ est premier.
• En géométrie. En 2008, Zeev Dvir a démontré la conjecture de Kakeya dans les corps finis via une preuve remarquablement simple qui s'appuie notamment sur le lemme de Schwartz-Zippel^[17].
• En logique. L'identité entre diagrammes de décision binaire se ramène au problème de l'identité entre polynômes et peut donc être abordée par les mêmes outils.
• En théorie des graphes. Via le théorème de Tutte^[18], l'existence d'un couplage équivaut à ce que le polynôme caractéristique d'une certaine matrice soit le polynôme nul, ce que permet de vérifier (en probabilité) le lemme de Schwartz-Zippel^[19].
• En algorithmique. Si ${\displaystyle A,B,C}$ sont des matrices carrées de taille ${\displaystyle n\times n}$, l'identité ${\displaystyle AB=C}$ peut être vérifiée en temps ${\displaystyle O(n^{2})}$ en appliquant le lemme, plutôt que ${\displaystyle O(n^{3})}$ en effectuant le produit et en comparant.
• En cryptographie. En 2016, Garg et coll. ont proposé une construction d'obfuscation cryptographique dont la sécurité repose notamment sur une extension du lemme de Schwartz-Zippel à des valeurs tirées des distributions générales avec assez d'entropie (à la place d'exiger la distribution uniforme) et possiblement présentant une dépendance entre elles (à la place d'exiger que les valeurs soient indépendantes)^[20].

Références

• Portail des mathématiques