Lemme de Schwartz-Zippel

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. »

Summarize Timeline Fact Check

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 \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 ${\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}$.

Summarize Timeline Top Qs Fact Check

On ne démontre ici que 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.