Alternatywne dowody lematu Schwartza – Zippela

Znam tylko dwa dowody lematu Schwartza – Zippela. Pierwszy (bardziej powszechny) dowód został opisany we wpisie na Wikipedii . Drugi dowód odkryła Dana Moshkovitz.

Czy są jakieś inne dowody, które wykorzystują zasadniczo różne pomysły?

Oto kolejny pomysł na geometryczny dowód. Wykorzystuje geometrię rzutową w istotny sposób.

Niech być afinicznej punktu na zewnątrz hiperpowierzchni S . Rzutuj powierzchnię nadprzestrzenną na hiperpłaszczyznę w nieskończoności, używając c jako środka; to znaczy odwzoruj co x ∈ S na p ( x ) , przecięcie unikalnej linii przez c i x z hiperpłaszczyzną w nieskończoności. W preimages pod P punktu w nieskończoności wszystkie leżą w jednej linii, a w związku z tym (ponownie zmniejszenie problemu do wymiaru 1) jest najbardziej d z nich. Hiperpłaszczyzna w nieskończoności ma liczność | F m $c \in \mathbb F^m$$S$$c$$x \in S$$p(x)$$c$$x$$p$$d$, więc otrzymujemy znajomą górną granicę | S | ≤d | F m - 1 | .$|\mathbb F^{m-1}|$$|S| \leq d\ |\mathbb F^{m-1}|$

Jako odpowiedź na odpowiedź Per Vognsena, dowód Dany Moshkovitz już sugeruje bardzo łatwy dowód tylko dla nieco słabszej wersji Schwartz-Zippel Lemma, który moim zdaniem wystarczy do większości zastosowań.

$f : \mathbb{F}^n \to \mathbb{F}$$d$$\mathbb{F}$$q$$x \in \mathbb{F}^n$$f(x) \neq 0$$(q^n-1)/(q-1)$$x$$\mathbb{F}^n-\{x\}$$f$$d$ $x$$d$$f$$d(q^n-1)/(q-1)$$d q^{n-1}$

Biorąc pod uwagę łatwość tego dowodu, jestem pewien, że jest to folklor; jeśli nie, powinno być :) Byłbym wdzięczny, gdyby ktoś mógł podać referencje.

Dowód Moshkovitza opiera się na prostej geometrii, ale papier nie jest zbyt jasny. Oto pomysł:

$d$$m$$\mathbb F^m$$\mathbb F^m$$\mathbb F^{m-1}$$\mathbb F^m$$d\ |F|^{m-1}$

Sugeruje to, że inne dowody o podobnych cechach mogłyby działać.

$w = 0$

Edycja: Zobacz moją drugą odpowiedź, aby uzyskać nowy (ale nie całkowicie niezwiązany) dowód.

Próba 1:

Czy spojrzałeś na Lemmę A.36 (strona 529) książki Arora / Barak ? To prawie połowa strony i opiera się na indukcji.

Jeśli nie masz dostępu do książki, mogę przeprowadzić dowód tutaj.

Próba 2:

A co z Ciekawą historią Schwartz-Zippel Lemma ? Między innymi powołuje się na artykuł DeMillo-Liptona z 1977 r. Wymieniono także i porównano kilka innych artykułów.

Próba 3:

Interesujący może być również następujący temat MathOverflow: Algorytm P / poli do testowania tożsamości wielomianowej .

Lemma Schwartza-Zippla jest szczególnym przypadkiem twierdzenia Nogi Alona i Zoltana Fürediego, jak pokazano w rozdziale 4 tego artykułu: O zerach wielomianu w skończonej siatce , a zatem każdy nowy dowód tego twierdzenia daje nowy dowód Schwartza -Zippel. Na razie znam sześć różnych dowodów, z których dwa pojawiają się w artykule, a inne są tam wymienione.

Twierdzenie Alona-Furediego mówi, co następuje:

$F$$A = \prod_{i=1}^n A_i \subset F^n$$f \in F[\underline{t}] = F[t_1,\ldots,t_n]$$A$$f(x) \neq 0$$\min \prod y_i$$x \in A$, gdzie minimum jest przejmowane przez wszystkie liczby całkowite dodatnie z .$y_i \leq \# A_i$$\sum_{i=1}^n y_i = \sum_{i=1}^n \# A_i - \deg f$

W tym przypadku, jeśli przyjmiesz i minimum (co można łatwo zrobić za pomocą rzeczy Balls in Bins wspomnianych w artykule), wtedy otrzymasz pole Schwartza-Zippla nad polem (lub domena).$\deg f < \min \#A_i$

Pierwotne sformułowanie lematu Schwartza – Zippla dotyczy tylko pól:

Lemma (Schwartz, Zippel).
Niech być niezerowy wielomianem stopnia całkowitego na polu, . Niech być ograniczony podzbiór i pozwolić wybierane losowo i niezależnie od równomiernie . Następnie $P\in F[x_1,x_2,\ldots,x_n]$$d \geq 0$$F$$S$$F$$r_1, r_2, \dots, r_n$$S$
$\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$

Można przeformułować lemat tak, aby miał on sens dla dowolnych pierścieni komutacyjnych:

Lemma (Jeřábek).
Niech być niezerowy wielomianem stopnia całkowitego nad przemiennej pierścieniu . Niech będzie skończonym podzbiorem z i niech wybierane losowo i niezależnie od równomiernie . Następnie $P\in R[x_1,x_2,\ldots,x_n]$$d \geq 0$$R$$S$$R$$\forall s, t\in S:((\exists u\in R:(u\neq 0\land su=tu))\Rightarrow s=t)$ S Pr [ P ( r 1 , r 2 , … , r n ) = 0 ] ≤ $r_1, r_2, \dots, r_n$$S$
$\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$

Zaletą dowodu z wikipedii jest to, że uogólnia on, aby wykazać, że przeformułowanie jest prawdziwe w przypadku dowolnych pierścieni komutacyjnych, co zostało zauważone i opracowane tutaj przez Emila Jeřábka .

Daje to alternatywny dowód na lemat Schwartza-Zippela, dowodząc przeformułowania ogólnych pierścieni komutacyjnych i uzyskując normalne sformułowanie pól jako następstwo.