1leonkadende: Schwartz-Zippel-Lemma

In der Mathematik ist der Schwartz-Zippel-Lemma (auch DeMillo-Lipton-Schwartz-Zippel-Lemma ) ein Werkzeug, das üblicherweise bei der probabilistischen Polynomialidentitätsprüfung verwendet wird, dh im Problem bei der Bestimmung, ob ein gegebenes multivariates Polynom das ist 0-Polynom (oder identisch gleich 0). Es wurde unabhängig von Jack Schwartz, ^[1]Richard Zippel, ^[2] und Richard DeMillo und Richard J. Lipton entdeckt, obwohl DeMillo und Liptons Version ein Jahr vor dem Ergebnis von Schwartz und Zippel gezeigt wurde. ^[3] Die endliche Feldversion von Diese Bindung wurde von Øystein Ore im Jahr 1922 nachgewiesen. ^[4]

Aussage des Lemmas [ edit ]

Der Input für das Problem ist ein -variables Polynom über ein Feld F . Es kann in den folgenden Formen auftreten:

Algebraische Form [ edit ]

Zum Beispiel ist

${displaystyle (x_{1}+3x_{2}-x_{3})(3x_{1}+x_{4}-1)cdots (x_{7}-x_{2})equiv 0 ?}$
Um dieses Problem zu lösen, können wir es multiplizieren und prüfen, ob alle Koeffizienten 0 sind. Dies erfordert jedoch exponentielle Zeit. Im Allgemeinen kann ein Polynom durch eine arithmetische Formel oder Schaltung algebraisch dargestellt werden.

Determinante einer Matrix mit Polynomeinträgen [ edit

Let

${displaystyle p(x_{1},x_{2},ldots ,x_{n})}$
ist die Determinante der Polynommatrix.
Derzeit ist kein subexponentieller Zeitalgorithmus bekannt, der dieses Problem deterministisch lösen kann. Es gibt jedoch randomisierte Polynomalgorithmen zum Testen von Polynomidentitäten. Ihre Analyse erfordert normalerweise eine Begrenzung der Wahrscheinlichkeit, dass ein Polynom ungleich Null an zufällig ausgewählten Testpunkten Wurzeln hat. Das Schwartz-Zippel-Lemma sieht dies folgendermaßen vor:
Satz 1 (Schwartz, Zippel). Let

${displaystyle Pin F[x_{1},x_{2},ldots ,x_{n}]}$
"/>
sei ein Non -Null-Polynom von insgesamt Grad $d \geq 0$ über einem Feld F. Sei S eine endliche Teilmenge von F und sei $r 1] r 2 ..., r n$ willkürlich unabhängig und einheitlich aus S. Then

${displaystyle Pr[P(r_{1},r_{2},ldots ,r_{n})=0]leq {frac {d}{|S|}}.}$
Im Fall der einzelnen Variablen folgt dies direkt aus der Tatsache, dass ein Polynom nur Wurzeln haben kann. Es erscheint daher logisch zu glauben, dass eine ähnliche Aussage für multivariable Polynome gelten würde. Dies ist tatsächlich der Fall.
Beweis. Der Beweis erfolgt durch mathematische Induktion am n . Für $n = 1$ können, wie bereits erwähnt, P höchstens d Wurzeln haben. Dies gibt uns den Basisfall. Nehmen wir nun an, dass der Satz für alle Polynome in $n - 1$ Variablen gilt. Wir können dann P als ein Polynom in x ₁ betrachten, indem wir es als schreiben

${ displaystyle P (x_ {1}, dots, x_ {n}) = sum _ {i = 0} ^ {d} x_ {1} ^ {i} P_ {i} (x_ {2}, dots, x_ {n}).}$
Da $P$ nicht identisch 0 ist, gibt es einige $i$ so dass ${ displaystyle P_ {i }}$ ist nicht identisch 0. Nehmen Sie den größten $i$ . $i (19659170) (19659170) P_ {i} leq di}$ seit dem Grad von $] { displaystyle x_ {1} ^ {i} P_ {i}}$ ist höchstens d.
Nun wählen wir zufällig ${19659159] { displaystyle r_ {2}, Punkte, r_ {n}}$ von $S$ . Durch die Induktionshypothese ${ displaystyle Pr [P_{i}(r_{2},ldots ,r_{n})=0] leq { frac {di} {| S |}}.}$
If ${ displaystyle P_ {i} (r_ {2}, ldots, r_ {n}) neq 0}$ dann ${ displaystyle P (x_ {1}, r_ {2}, ldots, r_ { n})}$ ist grad $i$ (und somit nicht identisch null)

${ displaystyle Pr [P(r_{1},r_{2},ldots ,r_{n})=0|P_{i}(r_{2},ldots ,r_{n})neq 0] leq { frac {i} {| S |}}.]$
Wenn wir das Ereignis angeben ${[Displaystyle P (1)] (1) , r_ {2}, ldots, r_ {n}) = 0}$ von $A$ das Ereignis ${ displaystyle P_ {i} (r_ {2}, ldots, r_ {n}) = 0}$ von $B$ und die Ergänzung von $B$ von ${ displaystyle B ^ {c}}$ haben wir

${displaystyle {begin{aligned}Pr[A]&=Pr[Acap B]+Pr[Acap B^{c}]&=Pr[B]Pr[A|B]+Pr[B^{c}]Pr[A|B^{c}]&leq Pr[B]+Pr[A|B^{c}]&leq {frac {d-i}{|S|}}+{frac {i}{|S|}}={frac {d}{|S|}}end{aligned}}}$

Anwendungen ] [ edit ]

Die Bedeutung des Schwartz-Zippel-Theorems und der Testpolynomialidentitäten folgt von Algorithmen, die erhalten werden, zu Problemen, die auf das Problem reduziert werden können der polynomialen Identitätsprüfung.

Vergleich zweier Polynome [ edit ]

Bei einem Paar von Polynomen ${ displaystyle p_ {1} (x)}$ und ${ displaystyle p_ {2} (x)}$ ist

${1945Start p_ {1} (x) Äquivalent p_ { 2} (x)}$ ?
Dieses Problem kann gelöst werden, indem es auf das Problem des Polynomidentitätstests reduziert wird. Es ist gleichbedeutend mit der Prüfung, ob

${displaystyle [p_{1}(x)-p_{2}(x)]equiv 0.}$