Alternative Beweise der Schwartz-Zippel-Deckspelze

28

Mir sind nur zwei Beweise für die Schwartz-Zippel-Deckspelze bekannt. Der erste (häufigere) Beweis ist im Wikipedia-Eintrag beschrieben . Der zweite Beweis wurde von Dana Moshkovitz entdeckt.

Gibt es noch andere Beweise, die ganz andere Ideen verwenden?

Dai Le
quelle
2
Können Sie etwas zu Ihrer Motivation sagen? Suchen Sie nach Verallgemeinerungen in verschiedene Richtungen? Vielleicht geometrische Einsicht?
Per Vognsen
Ich habe keine besondere Motivation. Ich werde sehr überrascht sein, dass dies die einzigen zwei Möglichkeiten sind, dieses wichtige Lemma zu beweisen!
Dai Le
Ich stimme zu, dass dieses Lemma wichtig ist, aber wichtige Lemmas haben nicht unbedingt viele verschiedene bekannte Beweise. Daher klingt Ihr Grund für mich ein bisschen seltsam.
Tsuyoshi Ito
1
@ Tsuyushi Ito: Ich stimme Ihrer Bemerkung zu, dass wichtige Deckspelzen möglicherweise nicht viele bekannte Beweise haben. Aber ich denke, es ist sinnvoll zu fragen, ob dies auch für SZ Lemma der Fall ist. Da SZ von grundlegender Bedeutung ist, ist es wahrscheinlich, dass es von vielen Menschen aus verschiedenen Kontexten unabhängig entdeckt wurde. Daher ist es meiner Meinung nach manchmal ziemlich aufschlussreich, verschiedene Beweise zu lernen. Nochmals vielen Dank für tolle Kommentare von allen!
Dai Le

Antworten:

16

Hier ist eine andere Idee, die ich für einen geometrischen Beweis hatte. Es nutzt die projektive Geometrie in einer wesentlichen Weise.

Lassen Sie cFm ein affiner Punkt außerhalb der Hyperfläche S . Projizieren Sie die Hyperfläche mit c als Mittelpunkt im Unendlichen auf die Hyperebene . das heißt, jede Karte xS auf p(x) , den Schnittpunkt der Linie , die durch einzigartige c und x mit der Hyperebene im Unendlichen. Die Vorbilder unter p eines Punktes im Unendlichen liegen alle auf der gleichen Linie, und daher gibt es (wiederum das Problem auf Dimension 1 reduzierend) die meisten d von ihnen. Die Hyperebene im Unendlichen hat Mächtigkeit |Fm1|erhalten wir die bekannte Obergrenze|S|d |Fm1|.

Per Vognsen
quelle
Schön! Und nur um einen entscheidenden Punkt hervorzuheben, ist die Linie nicht in der Hyperfläche enthalten, da sie durch den Punkt c verläuft, der sich außerhalb der Oberfläche befindet.
Arnab
1
@arnab: In der Tat haben Sie diesen Punkt in Ihrem eigenen Beitrag bereits gut formuliert.
Per Vognsen
1
@arnab: Übrigens, ich hoffe, es ist klar, dass ich nicht behaupte, dass diese Idee wirklich "neu" ist. Alle diese Beweise haben einen ähnlichen Geruch. Das ist wahrscheinlich zu erwarten.
Per Vognsen
2
@Per: Ja, aber aus irgendeinem Grund gefällt mir Ihre Version des Arguments besser als die von Moshkovitz, weil es irgendwie geometrischer wirkt und Sie nicht über führende Monome nachdenken müssen. Aber ich stimme zu, die Grundidee ist sehr ähnlich.
Arnab
@Per: deine beiträge waren schon wundervoll. Ja, sie sind nicht wirklich neu, aber ich mag deine Interpretation sehr. Es ist, als würde man einem klassischen Musikstück eine neue Interpretation geben. :-)
Dai Le
18

Als Folge der Antwort von Per Vognsen deutet der Beweis von Dana Moshkovitz bereits auf einen wirklich einfachen Beweis für eine nur geringfügig schwächere Version des Schwartz-Zippel-Lemmas hin, der meiner Meinung nach für die meisten Anwendungen ausreicht.

Sei ein von Null verschiedenes Polynom vom Grad d , wobei F ein endliches Feld der Ordnung q ist , und sei x F n ein Punkt mit f ( x ) 0 . Es gibt ( q n - 1 ) / ( q - 1 ) viele verschiedene Linien, die durch x verlaufen, so dass sie F n - { x } unterteilen.f:FnFdFqxFnf(x)0(qn1)/(q1)xFn{x}. Die Beschränkung von auf jede dieser Linien ist ein univariates Polynom vom Grad d , das ungleich Null ist, weil es bei x ungleich Null ist und daher höchstens d Nullen hat. Somit ist die Gesamtzahl der Nullen von f ist höchstens d ( q n - 1 ) / ( q - 1 ) . Zum Vergleich gibt Schwartz-Zippel die stärkere Obergrenze von d q n - 1 an .fd xdfd(qn-1)/(q-1)dqn-1

Angesichts der Leichtigkeit dieses Beweises bin ich sicher, dass es Folklore ist; Wenn nicht, sollte es sein :) Ich würde mich freuen, wenn jemand eine Referenz liefern könnte.

Arnab
quelle
3
Sehr schön! Wussten Sie, dass sie genau dasselbe tut, nur mit einem projektiven Punkt im Unendlichen und nicht mit einem affinen Punkt? Ich habe meiner ursprünglichen Antwort einen Absatz hinzugefügt, um die Beziehung näher zu erläutern.
Per Vognsen,
1
Ah, das ist eine großartige Interpretation! Vielen Dank!
Arnab
14

Moshkovitz 'Beweis basiert auf einer einfachen Geometrie, aber das Papier ist nicht klar genug. Hier ist die Idee:

Ein Grad- Polynom in m Variablen schneidet eine Hyperfläche in F m aus . Der Schnittpunkt der Hyperfläche und einer unabhängigen Linie (dh der Schnittpunkt ist nicht die ganze Linie) hat höchstens d Punkte. Wenn Sie eine Richtung finden, die überall unabhängig von der Hyperfläche ist, können Sie F m durch parallele Linien in dieser Richtung blättern und Schnittpunkte innerhalb jeder Linie zählen. Die Foliation wird durch das orthogonale Komplement der Richtung parametrisiert, das eine zu F m - 1 isomorphe Hyperebene ist , so dass die Gesamtzahl der Hyperoberflächenpunkte über alle F m höchstens d | beträgt FdmFmFmFm-1Fm .d |F|m1

Dies deutet darauf hin, dass andere Beweise in ähnlicher Weise funktionieren könnten.

Edit: Ich wollte ein wenig darüber sagen, wie Arnabs Beweis sich auf Moshkovitz bezieht. Er nimmt einen Punkt außerhalb der Hyperfläche und betrachtet den Linienstift durch diesen Punkt. Moshkovitz betrachtet eine Familie paralleler Linien. Es scheint anders zu sein, aber es ist wirklich dasselbe! Eine Parallelfamilie ist ein Linienstift durch einen Punkt im Unendlichen. Die Arnab-Algebra wird wörtlich angewendet, wenn Sie zuerst die Homogenisierung des Polynoms durchführen und durch Einstecken von auf die Hyperebene im Unendlichen beschränken , wodurch alle nicht führenden Terme gelöscht werden.w=0

Bearbeiten: Siehe meine andere Antwort für einen neuen (aber nicht völlig unabhängigen) Beweis.

Per Vognsen
quelle
6

Versuch 1:

Haben Sie sich Lemma A.36 (Seite 529) von Arora / Baraks Buch angesehen ? Es ist fast eine halbe Seite und basiert auf Induktion.

Wenn Sie keinen Zugang zu dem Buch haben, kann ich den Beweis hier durchführen.


Versuch 2:

Was ist mit der kuriosen Geschichte des Schwartz-Zippel-Lemmas ? Darin wird unter anderem die Arbeit von DeMillo-Lipton aus dem Jahr 1977 zitiert . Einige andere Arbeiten werden ebenfalls benannt und verglichen.


Versuch 3:

Das folgende MathOverflow-Thema könnte ebenfalls von Interesse sein: P / Poly-Algorithmus zum Testen der polynomiellen Identität .

MS Dousti
quelle
Ja, habe ich. Aber dieser Beweis ist im Wesentlichen der gleiche wie der aus Wikipedia.
Dai Le
4

Das Schwartz-Zippel-Lemma ist ein Spezialfall eines Satzes von Noga Alon und Zoltan Füredi, wie in Abschnitt 4 dieses Aufsatzes gezeigt: Über Nullen eines Polynoms in einem endlichen Gitter , und daher liefert jeder neue Beweis dieses Satzes einen neuen Beweis für Schwartz -Zippel. Bis jetzt kenne ich sechs verschiedene Beweise, von denen zwei in der Zeitung erscheinen und auf andere dort verwiesen wird.

Das Alon-Furedi-Theorem sagt Folgendes:

Sei ein Feld, sei A = n i = 1 A iF n ein endliches Gitter und sei f F [ t _ ] = F [ t 1 , ... , t n ] ein Polynom, das nicht existiert identisch verschwinden auf A . Dann f ( x , wobei das Minimum über alle positiven ganzen Zahlen y i# A i mit ∑ übernommen wirdFA=i=1nAiFnfF[t_]=F[t1,,tn]A für mindestens min y i Elemente x Af(x)0minyixAyi#Ai.i=1nyi=i=1n#Aidegf

Wenn Sie in diesem Fall annehmen und das Minimum berechnen (was mit den im Artikel erwähnten Balls in Bins-Dingen leicht möglich ist), erhalten Sie Schwartz-Zippel-Lemma über ein Feld (oder eine Domain). .degf<min#Ai

Anurag
quelle
Können Sie sich Lemma 2.2 in web.stanford.edu/~rrwill/graph-cr.pdf ansehen ? Dies ist, was Ryan Williams mit seinem Kommentar unter meiner Antwort meint, und er steht seitdem auf meiner ToDo-Liste, um zu prüfen, ob er auf kommutative Ringe verallgemeinert werden kann. Mir scheint, Sie sind momentan viel tiefer in diese Sache verstrickt als ich. Warum probieren Sie es nicht aus?
Thomas Klimpel
@ThomasKlimpel: Ich werde die Antwort ändern. Ich habe es geschrieben, als ich gerade angefangen habe, CS Theory StackExchange zu verwenden. Und ja, Lemma 2.2 funktioniert über beliebige kommutative Ringe, da {0,1} ^ n immer die Bedingung (D) erfüllt.
Anurag,
Eine Teilmenge eines beliebigen kommutativen Ring R ist die Bedingung zu erfüllen , (D) , wenn für alle x y S , x - y kein Nullteiler ist. Ein "Gitter" A 1 × × A nR n soll diese Bedingung erfüllen, wenn alle A i 's sie erfüllen. Schwartz-Zippel und andere verwandte Ergebnisse arbeiten unter dieser Verallgemeinerung, wie in der Veröffentlichung gezeigt. SRxySxyA1××AnRnAi
Anurag,
3

Die ursprüngliche Formulierung der Schwartz-Zippel-Deckspelze gilt nur für Felder:

Lemma (Schwartz, Zippel).
Lassen werden , um ein Nicht-Null - Polynom gesamten Grad d 0 über ein Feld, F . Sei S eine endliche Teilmenge von F und sei r 1 , r 2 , ... , r n unabhängig und gleichmäßig aus zufällig ausgewähltPF[x1,x2,,xn]d0FSFr1,r2,,rn. Dann wird Pr [ P ( rS
Pr[P(r1,r2,,rn)=0]d|S|.

Man kann das Lemma so umformulieren, dass es für beliebige kommutative Ringe Sinn macht:

Lemma (Jeřábek).
Lassen eine Nicht-Null - Polynom gesamten Grad sein , d 0 über einen kommutativen Ring, R . Sei S eine endliche Teilmenge von R mit s , t S : ( ( u R :PR[x1,x2,,xn]d0RSR und sei r 1 , r 2 , , r n unabhängig und gleichmäßig aus S zufällig ausgewählt. Dann ist Pr [ P ( r 1 , r 2 , , r n ) = 0 ] ds,tS:((uR:(u0su=tu))s=t)r1,r2,,rnS
Pr[P(r1,r2,,rn)=0]d|S|.

Der Vorteil des Beweises aus Wikipedia ist, dass er verallgemeinert zeigt, dass die Neuformulierung für beliebige kommutative Ringe gilt, was Emil Jeřábek hier bemerkt und ausgearbeitet hat .

Dies gibt einen alternativen Beweis für das Schwartz-Zippel-Lemma, indem die Neuformulierung für allgemeine Kommutativringe bewiesen und die normale Formulierung für Felder als Korollar erhalten wird.

Thomas Klimpel
quelle
Polynome sind die freie Algebra für kommutative Ringe, dh die freie Algebra, die durch Addition, additive Inverse, Multiplikation und Konstanten relativ zu den Axiomen kommutativer Ringe erzeugt wird. Die anfängliche Hoffnung bestand darin, eine Verallgemeinerung des Schwartz-Zippel-Lemmas für die freie Algebra zu finden, die zusätzlich (generalisierte) multiplikative Inversen relativ zu den Axiomen kommutativer regulärer Ringe enthält . Siehe auch Arbeiten von Jan A. Bergstra .
Thomas Klimpel
1
Zm
1
@RyanWilliams Die Arbeit über Nullen eines Polynoms in einem endlichen Gitter, die in der jüngsten Antwort von Anurag Bishnoi zitiert wurde, verallgemeinert sowohl das obige Lemma, das Alon-Furedi-Theorem als auch das Lemma 2.2 aus dieser SODA'15-Arbeit (und beweist die Schärfe der Schranke) . Es war auf meiner ToDo-Liste seit Ihrem Kommentar, eine solche Verallgemeinerung zu finden, also ist es aus meiner Sicht eine bedeutende Errungenschaft (also könnte man den Autoren gratulieren).
Thomas Klimpel