Pol. Identität/Schwartz-Zippel < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:25 So 07.04.2013 | | Autor: | el_grecco |
| Aufgabe | Polynomielle Identitäten:
Gegeben: Polynom in mehreren Variablen (durch Term in Variablen +, *)
Gefragt: P=0
Lösung Randomisierter Algorithmus:
Setze für die Variablen zufällige Werte ein und rechne aus.
Ergebnis = 0 [mm] $\Rightarrow$ [/mm] Polynom P möglicherweise gleich 0.
Ergebnis [mm] $\not= [/mm] 0 [mm] \Rightarrow$ [/mm] Polynom P sicher nicht 0.
Beispiel:
[mm] $(a^2+b^2+c^2+d^2)(A^2+B^2+C^2+D^2)-(aA+bB+cC+dD)^2-(ab-bA-cD-dC)^2-(aC+bD-cA-dB)^2-(aD-bC+cB-dA)^2=0$
[/mm]
Lemma (Schwartz-Zippel):
Sei P ein nichtverschwindendes Polynom in den Variablen [mm] $x_1,...,x_n$ [/mm] vom Grad [mm] $\leq [/mm] d$ (summarischer Grad; z.B. $xyz + [mm] x^2 [/mm] +z$ hat Grad 3). N > 0. Die Zahl der [mm] $\vec [/mm] x [mm] \in \{ -N,...,N \}^n$ [/mm] sodass [mm] $P(\vec [/mm] x) = 0$ ist höchstens [mm] $dn(2n+1)^{n-1}$.
[/mm]
Bemerkung:
Ist $P [mm] \not= [/mm] 0$ und wird [mm] $\vec [/mm] x [mm] \in \{ -N,...,N \}$ [/mm] zufällig gewählt, so ist die Wahrscheinlichkeit, dass [mm] $P(\vec [/mm] x)=0$ höchstens [mm] $\bruch{dn(2N+1)^{n-1}}{(2n+1)^n}=\bruch{dn}{2N+1}$. [/mm] Diese ist [mm] $\leq [/mm] 25%$ falls $N [mm] \geq \bruch{4dn-1}{2}$.
[/mm]
Anwendung: Test auf perfektes Matching
Gegeben: Ungerichteter Graph G=(V,E).
Gesucht: Perfektes Matching, d.h. eine Teilmenge der Kanten $M [mm] \subseteq [/mm] E$, sodass keine zwei Kanten aus M einen Knoten gemeinsam haben.
$(u,v) [mm] \in [/mm] M,(x,y) [mm] \in [/mm] M [mm] \Rightarrow [/mm] u [mm] \not= [/mm] x, u [mm] \not= [/mm] y, v [mm] \not= [/mm] x, v [mm] \not= [/mm] y$ oder $u=x,v=y$ oder $u=y,v=x$.
Und außerdem jeder Knoten auf einer Kante in M liegt.
[mm] $\forall [/mm] v [mm] \in [/mm] V [mm] \exists(u,x) \in [/mm] M$ mit u = v oder x = v.
OBdA $(x,y) [mm] \in [/mm] M [mm] \to [/mm] (y,x) [mm] \in [/mm] M$ (oder Formulierung als Menge). Probabilistischer Test für die Frage, ob ein gegebener Graph ein perfektes Matching zulässt.
Gegeben: G=(V,E)
Nummeriere Knoten [mm] $V=\{ v_1,...,v_n\}$.
[/mm]
Führe für $1 [mm] \leq [/mm] i < j [mm] \leq [/mm] n$ eine Variable [mm] $x_{ij}$ [/mm] ein, insgesamt [mm] $\bruch{n(n+1)}{2}$ [/mm] Variablen.
Bilde die $n [mm] \times [/mm] n$ Matrix [mm] $A=(a_{ij})_{ij}$, [/mm] wobei [mm] $a_{ij}=\begin{cases} x_{ij} & \mbox{falls } i < j \& (v_i,v_j) \in E\\ -x_{ji} & \mbox{falls } j < i \& (v_i,v_j) \in E\\ 0 & \mbox{sonst} \end{cases}$
[/mm]
Beispiel:
[mm] $A=\pmat{ 0 & x_{12} & x_{13} & x_{14} \\ -x_{12} & 0 & 0 & \\ -x_{13} & 0 & 0 & x_{34} \\ -x_{14} & -x_{24} & - x_{34} & 0}$
[/mm]
$det A = [mm] x_{12}*det \pmat{ x_{12} & x_{13} & x_{14} \\ 0 & 0 & x_{34} \\ -x_{24} & - x_{34}} [/mm] - [mm] x_{13}*det \pmat{ x_{12} & x_{13} & x_{14} \\ 0 & 0 & x_{24} \\ -x_{24} & - x_{34} & 0}=x_{12}(-x_{34}(-x_{12}x_{34}+x_{13}+x_{24}))-x_{13}(-x_{24}(-x_{12}x_{34}+x_{13}x_{24}))=(x_{13}x_{24}-x_{12}x_{34})^2$
[/mm]
Unter Verwendung des Gauß-Verfahrens (elementare Spalten- und Zeilenumformungen) kann die Determinante als Polynom polynomieller Größe geschrieben werden. Mit vorherigen Verfahren kann dann auf Verschwinden getestet werden. Mit Hilfe dieses Verfahrens kann man sogar ein perfektes Matching konstruieren, indem man der Reihe nach Kanten ausprobiert.
Satz von Tutte:
Es gibt ein perfektes Matching, wenn die zugehörige Matrix A invertierbar ist (Determinante ungleich 0). |
Hallo,
eine Sache vorweg: es handelt sich nicht um eine Aufgabe, sondern um die Mitschrift aus der Vorlesung "Komplexitätstheorie" zum Thema "Polynomielle Identitäten; Lemma von Schwartz-Zippel". Leider habe ich an dem Tag gefehlt und kann der Mitschrift nicht ganz folgen. Es ist zwar viel zu lesen, aber ich hoffe trotzdem, dass sich jemand findet, der bereit ist zu helfen, denn die Klausur steht bald an.
Meine Fragen:
- Was muss man sicher unter einer "polynomiellen Identität" vorstellen bzw. was ist an einem Nullpolynom so interessant?
- Kann bitte jemand in Worten beschreiben, was das "Lemma von Schwartz-Zippel" aussagt bzw. wie das Lemma oben überhaupt zu lesen ist?
- Die Problemstellung von perfektem Matching ist mir klar. Probleme habe ich mit der Matrix [mm] $A=(a_{ij})_{ij}$ [/mm] (anscheinend bezeichnet man diese Matrix als "Tutte-Matrix") bzw. dem Beispiel. Ausgehend von [mm] $\bruch{n(n+1)}{2}$ [/mm] müsste man hier 10 Variablen haben, wegen n = 4. Ich komme aber nur auf 6 Variablen: [mm] $x_{12},x_{13},x_{14},x_{23},x_{24},x_{34}$. [/mm] Woran liegt das?
- Müsste es nicht $det A = [mm] x_{12}*det \pmat{ x_{12} & x_{13} & x_{14} \\ 0 & 0 & x_{34} \\ -x_{24} & - x_{34}} [/mm] - [mm] x_{13}*det \pmat{ x_{12} & x_{13} & x_{14} \\ 0 & 0 & 0 \\ -x_{24} & - x_{34} & 0} [/mm] + [mm] x_{14}*det \pmat{ x_{12} & x_{13} & x_{14} \\ 0 & 0 & \\ 0 & 0 & x_{34}}$ [/mm] heißen?
Ich hoffe trotz dieses Romans, dass sich ein Helfer findet!
Vielen Dank für die Mühe!
Gruß
el_grecco
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:30 So 07.04.2013 | | Autor: | felixf |
Moin,
> Polynomielle Identitäten:
> Gegeben: Polynom in mehreren Variablen (durch Term in
> Variablen +, *)
> Gefragt: P=0
> Lösung Randomisierter Algorithmus:
> Setze für die Variablen zufällige Werte ein und rechne
> aus.
> Ergebnis = 0 [mm]\Rightarrow[/mm] Polynom P möglicherweise gleich
> 0.
> Ergebnis [mm]\not= 0 \Rightarrow[/mm] Polynom P sicher nicht 0.
>
> Beispiel:
>
> [mm](a^2+b^2+c^2+d^2)(A^2+B^2+C^2+D^2)-(aA+bB+cC+dD)^2-(ab-bA-cD-dC)^2-(aC+bD-cA-dB)^2-(aD-bC+cB-dA)^2=0[/mm]
>
> Lemma (Schwartz-Zippel):
> Sei P ein nichtverschwindendes Polynom in den Variablen
> [mm]x_1,...,x_n[/mm] vom Grad [mm]\leq d[/mm] (summarischer Grad; z.B. [mm]xyz + x^2 +z[/mm]
> hat Grad 3). N > 0. Die Zahl der [mm]\vec x \in \{ -N,...,N \}^n[/mm]
> sodass [mm]P(\vec x) = 0[/mm] ist höchstens [mm]dn(2n+1)^{n-1}[/mm].
Das soll doch sicher $d n (2 N + [mm] 1)^{n-1}$ [/mm] lauten, oder?
> Bemerkung:
> Ist [mm]P \not= 0[/mm] und wird [mm]\vec x \in \{ -N,...,N \}[/mm] zufällig
> gewählt, so ist die Wahrscheinlichkeit, dass [mm]P(\vec x)=0[/mm]
> höchstens
> [mm]\bruch{dn(2N+1)^{n-1}}{(2n+1)^n}=\bruch{dn}{2N+1}[/mm]. Diese
> ist [mm]\leq 25%[/mm] falls [mm]N \geq \bruch{4dn-1}{2}[/mm].
>
> Hallo,
>
> eine Sache vorweg: es handelt sich nicht um eine Aufgabe,
> sondern um die Mitschrift aus der Vorlesung
> "Komplexitätstheorie" zum Thema "Polynomielle
> Identitäten; Lemma von Schwartz-Zippel". Leider habe ich
> an dem Tag gefehlt und kann der Mitschrift nicht ganz
> folgen. Es ist zwar viel zu lesen, aber ich hoffe trotzdem,
> dass sich jemand findet, der bereit ist zu helfen, denn die
> Klausur steht bald an.
>
> Meine Fragen:
> - Was muss man sicher unter einer "polynomiellen
> Identität" vorstellen bzw. was ist an einem Nullpolynom so
> interessant?
Eine polynomielle Identitaet ist eine Identitaet in polynomieller Form. Bekannte Identitaeten sind z.B. die Binomial-Identitaten, die man aus der Schule kennt:
* $(a + [mm] b)^2 [/mm] = [mm] a^2 [/mm] + 2 a b + [mm] b^2$
[/mm]
* $(a - [mm] b)^2 [/mm] = [mm] a^2 [/mm] - 2 a b + [mm] b^2$
[/mm]
* [mm] $a^2 [/mm] - [mm] b^2 [/mm] = (a - b) (a + b)$
Diese kann man auch als polynomielle Identitaet schreiben:
* $(a + [mm] b)^2 [/mm] - [mm] (a^2 [/mm] + 2 a b + [mm] b^2) [/mm] = 0$
* $(a - [mm] b)^2 [/mm] - [mm] (a^2 [/mm] - 2 a b + [mm] b^2) [/mm] = 0$
* [mm] $(a^2 [/mm] - [mm] b^2) [/mm] - ((a - b) (a + b)) = 0$
Diese Identitaeten sagen einfach aus, dass $(a + [mm] b)^2 [/mm] = [mm] a^2 [/mm] + 2 a b + [mm] b^2$ [/mm] ist, egal in welchem (kommutativen) Ring (mit Eins) man sich gerade befindet.
> - Kann bitte jemand in Worten beschreiben, was das "Lemma
> von Schwartz-Zippel" aussagt bzw. wie das Lemma oben
> überhaupt zu lesen ist?
Es sagt einem: wenn man zufaellig einen Punkt in [mm] $\{ -N, \dots, N \}^n$ [/mm] waehlt und in ein von 0 verschiedenes multivariates Polynom vom Grad [mm] $\le [/mm] d$ einsetzt, dann ist die Wahrschienlichkeit, dass der Wert gleich 0 ist, recht klein (und zwar $d n (2 N + [mm] 1)^{n-1} [/mm] / (2 N + [mm] 1)^n [/mm] = [mm] \frac{d n}{2 N + 1}$. [/mm] (Das geht gegen 0 fuer $N [mm] \to \infty$.)
[/mm]
Wenn du also testen moechtest, ob eine polynomielle Identitaet gilt, und du setzt viele verschiedene zufaellige Punkte ein und es kommt immer 0 heraus, dann ist die Wahrscheinlichkeit, dass sie stimmt, recht hoch. Wenn dagegen einmal was [mm] $\neq [/mm] 0$ herauskommt, weisst du sofort, dass die Gleichung nicht stimmt.
(Siehe auch ![[]](/images/popup.gif) hier.)
LG Felix
|
|
|
| |
|
Moin Felix,
Danke für Deine Antwort, sie hat mich ein gutes Stück weitergebracht! 
> >
> > Lemma (Schwartz-Zippel):
> > Sei P ein nichtverschwindendes Polynom in den Variablen
> > [mm]x_1,...,x_n[/mm] vom Grad [mm]\leq d[/mm] (summarischer Grad; z.B. [mm]xyz + x^2 +z[/mm]
> > hat Grad 3). N > 0. Die Zahl der [mm]\vec x \in \{ -N,...,N \}^n[/mm]
> > sodass [mm]P(\vec x) = 0[/mm] ist höchstens [mm]dn(2n+1)^{n-1}[/mm].
>
> Das soll doch sicher [mm]d n (2 N + 1)^{n-1}[/mm] lauten, oder?
Der Kommilitone hat es dann falsch abgeschrieben oder es war schon an der Tafel fehlerhaft.
Was bedeutet eigentlich das "dn"?
Also so wie ich den Nutzen vom Schwartz-Zippel-Lemma dank Deiner Erklärung verstanden habe, erspart das einem den (unter Umständen) teuren Test ob eine polynomielle Identität gilt. Bezüglich "Perfect Matching" macht man sich dieses Lemma in der Determinante zu Nutze, da nach dem "Satz von Tutte" perfektes Matching vorliegt, wenn die Determinante ungleich 0 ist.
Leider habe ich aber noch immer Probleme bei den anderen beiden Fragen und es gibt auch keine Übungsaufgabe zu dem Thema. Wäre nett, wenn Du bei Gelegenheit und Motivation etwas dazu schreiben könntest.
Gruß
el_grecco
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:33 Mo 08.04.2013 | | Autor: | felixf |
Moin el_grecco,
> > > Lemma (Schwartz-Zippel):
> > > Sei P ein nichtverschwindendes Polynom in den
> Variablen
> > > [mm]x_1,...,x_n[/mm] vom Grad [mm]\leq d[/mm] (summarischer Grad; z.B. [mm]xyz + x^2 +z[/mm]
> > > hat Grad 3). N > 0. Die Zahl der [mm]\vec x \in \{ -N,...,N \}^n[/mm]
> > > sodass [mm]P(\vec x) = 0[/mm] ist höchstens [mm]dn(2n+1)^{n-1}[/mm].
> >
> > Das soll doch sicher [mm]d n (2 N + 1)^{n-1}[/mm] lauten, oder?
>
> Der Kommilitone hat es dann falsch abgeschrieben oder es
> war schon an der Tafel fehlerhaft.
>
> Was bedeutet eigentlich das "dn"?
das ist das Produkt aus d (Grad) und n (Dimension).
> Also so wie ich den Nutzen vom Schwartz-Zippel-Lemma dank
> Deiner Erklärung verstanden habe, erspart das einem den
> (unter Umständen) teuren Test ob eine polynomielle
> Identität gilt. Bezüglich "Perfect Matching" macht man
> sich dieses Lemma in der Determinante zu Nutze, da nach dem
> "Satz von Tutte" perfektes Matching vorliegt, wenn die
> Determinante ungleich 0 ist.
Genau.
> Leider habe ich aber noch immer Probleme bei den anderen
> beiden Fragen und es gibt auch keine Übungsaufgabe zu dem
> Thema. Wäre nett, wenn Du bei Gelegenheit und Motivation
> etwas dazu schreiben könntest.
Vielleicht find ich morgen noch etwas Zeit, heute ist's leider nichts geworden... Aber garantieren kann ich fuer nichts.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:13 Di 09.04.2013 | | Autor: | el_grecco |
Moin' Felix,
ich danke Dir für Deine Mühe.
Inzwischen habe ich entdeckt, dass das Beispiel mit dem perfekten Matching vermutlich dem Beispiel in Introduction to the theory of complexity auf Seite 194 entsprechen soll. Ich denke ich komme jetzt klar.
Gruß
el_grecco
|
|
|
|
