Bukti alternatif dari lemma Schwartz-Zippel

28

Saya hanya mengetahui dua bukti dari lemma Schwartz-Zippel. Bukti pertama (lebih umum) dijelaskan dalam entri wikipedia . Bukti kedua ditemukan oleh Dana Moshkovitz.

Apakah ada bukti lain yang menggunakan ide yang sangat berbeda?

Dai Le
sumber
2
Bisakah Anda mengatakan sesuatu tentang motivasi Anda? Mencari generalisasi di berbagai arah? Mungkin wawasan geometris?
Per Vognsen
Saya tidak punya motivasi khusus. Saya akan sangat terkejut bahwa hanya ada dua cara yang mungkin untuk membuktikan lemma penting ini!
Dai Le
Sementara saya setuju bahwa lemma ini penting, lemma penting tidak harus memiliki banyak bukti yang berbeda. Karena itu, alasanmu kedengarannya agak aneh bagiku.
Tsuyoshi Ito
1
@ Tsuyushi Ito: Saya setuju dengan komentar Anda bahwa lemon penting mungkin tidak memiliki banyak bukti yang diketahui. Tapi saya pikir itu bermakna untuk bertanya apakah itu juga yang terjadi pada SZ Lemma. Karena SZ bersifat fundamental, kemungkinan ditemukan SZ secara independen oleh banyak orang dari konteks yang berbeda. Jadi, untuk mempelajari bukti yang berbeda kadang-kadang IMHO cukup mencerahkan. Sekali lagi terima kasih atas komentar luar biasa dari semua orang!
Dai Le

Jawaban:

16

Inilah ide lain yang saya miliki untuk bukti geometris. Ia menggunakan geometri projektif dengan cara yang esensial.

Mari cFm menjadi titik affine luar hypersurface S . Proyeksikan hypersurface ke hyperplane di infinity menggunakan c sebagai pusat; yaitu, memetakan setiap xS ke p(x) , persimpangan garis unik melalui c dan x dengan hyperplane di infinity. The preimages bawah p dari titik di tak terhingga semua kebohongan pada baris yang sama, dan karena itu (lagi mengurangi masalah untuk dimensi 1) ada sebagian d dari mereka. Hyperplane di infinity memiliki kardinalitas |Fm1|, jadi kami mendapatkan batas atas yang familier|S|d |Fm1|.

Per Vognsen
sumber
Indah! Dan hanya untuk menekankan titik penting, garis tidak terkandung dalam hypersurface karena melewati titik c, yang berada di luar permukaan.
arnab
1
@arnab: Memang, Anda sudah membuat poin itu dengan baik di pos Anda sendiri.
Per Vognsen
1
@arnab: BTW, saya harap jelas bahwa saya tidak mengklaim ide ini benar-benar "baru". Semua bukti ini memiliki bau yang serupa. Mungkin itu yang diharapkan.
Per Vognsen
2
@ Per: Ya, tapi untuk beberapa alasan, saya suka versi argumen Anda lebih baik daripada Moshkovitz karena tampaknya entah bagaimana lebih geometris dan Anda tidak perlu berpikir tentang memimpin monomial. Tapi saya setuju, ide dasarnya sama.
arnab
@ Per: kontribusi Anda sudah luar biasa. Ya, mereka tidak benar-benar baru, tetapi saya sangat menyukai interpretasi Anda. Ini seperti memberikan interpretasi baru pada karya musik klasik. :-)
Dai Le
18

Sebagai tindak lanjut dari jawaban Per Vognsen, bukti Dana Moshkovitz sudah menunjukkan bukti yang sangat mudah untuk hanya versi Schwartz-Zippel Lemma yang sedikit lebih lemah yang, saya pikir, cukup untuk sebagian besar aplikasi.

Misalkan menjadi polinomial bukan-nol derajat d , di mana F adalah bidang urutan terbatas q , dan misalkan x F n menjadi titik sedemikian rupa sehingga f ( x ) 0 . Ada ( q n - 1 ) / ( q - 1 ) banyak garis berbeda yang melewati x sedemikian rupa sehingga mereka mempartisi F n - { x }f:FnFdFqxFnf(x)0(qn1)/(q1)xFn{x}. Pembatasan untuk masing-masing baris ini adalah gelar d univariat polinomial, yang nol, karena nol di x , dan sebagainya, memiliki paling d nol. Jadi, jumlah total nol f paling banyak adalah d ( q n - 1 ) / ( q - 1 ) . Schwartz-Zippel, sebagai perbandingan, memberikan batas atas yang lebih kuat dari d q n - 1 .fd xdfd(qn1)/(q1)dqn1

Mengingat kemudahan bukti ini, saya yakin itu cerita rakyat; jika tidak, seharusnya :) Saya akan menghargai jika seseorang dapat memberikan referensi.

arnab
sumber
3
Sangat bagus! Tahukah Anda dia melakukan hal yang persis sama, hanya dengan titik proyektif di infinity daripada titik affine? Saya menambahkan paragraf ke jawaban asli saya untuk menjelaskan hubungan lebih lanjut.
Per Vognsen
1
Ah, itu interpretasi yang bagus! Terima kasih!
arnab
14

Bukti Moshkovitz didasarkan pada geometri sederhana tetapi makalahnya tidak terlalu jelas. Inilah idenya:

Sebuah gelar polinomial dalam m variabel pemotongan keluar hypersurface di F m . Persimpangan dari hypersurface dan garis independen (yaitu persimpangan bukan seluruh garis) memiliki paling banyak d poin. Jika Anda dapat menemukan arah yang di mana-mana independen hypersurface, Anda dapat berdaun-daun F m oleh garis sejajar dalam arah dan jumlah persimpangan dalam setiap baris. Foliation ini parameterized oleh komplemen ortogonal arah, yang merupakan isomorfik hyperplane untuk F m - 1 , sehingga jumlah total poin hypersurface di semua F m adalah paling banyak d | FdmFmFmFm1Fm .d |F|m1

Ini menunjukkan bahwa bukti lain di sepanjang garis yang sama dapat bekerja.

Sunting: Saya ingin mengatakan sedikit tentang bagaimana bukti Arnab berhubungan dengan Moshkovitz. Dia mengambil titik di luar permukaan hiper dan mempertimbangkan pensil garis melalui titik itu. Moshkovitz menganggap keluarga garis paralel. Tampaknya berbeda tetapi ini benar-benar sama! Keluarga paralel adalah pensil garis yang melewati titik tanpa batas. Aljabar Arnab berlaku kata demi kata jika Anda pertama kali melakukan homogenisasi polinomial dan membatasi hyperplane pada infinity dengan menghubungkan , yang menghapus semua istilah yang tidak mengarah.w=0

Sunting: Lihat jawaban saya yang lain untuk bukti baru (tetapi tidak sepenuhnya terkait).

Per Vognsen
sumber
6

Percobaan 1:

Sudahkah Anda melihat Lemma A.36 (halaman 529) dari buku Arora / Barak ? Hampir setengah halaman, dan didasarkan pada induksi.

Jika Anda tidak memiliki akses ke buku itu, saya bisa membawa buktinya di sini.


Percobaan 2:

Bagaimana dengan Sejarah Penasaran tentang Schwartz-Zippel Lemma ? Di antara yang lain, itu mengutip kertas DeMillo-Lipton , dating kembali ke tahun 1977. Beberapa makalah lain diberi nama dan membandingkan juga.


Percobaan 3:

Topik MathOverflow berikut mungkin menarik juga: Algoritma P / poly untuk pengujian identitas polinomial .

MS Dousti
sumber
Ya saya lakukan. Tetapi bukti ini pada dasarnya sama dengan yang ada di wikipedia.
Dai Le
4

Schwartz-Zippel lemma adalah kasus khusus dari teorema Noga Alon dan Zoltan Füredi seperti yang ditunjukkan pada Bagian 4 makalah ini: Pada Nol dari Polinomial dalam Grid Hingga , dan karenanya setiap bukti baru dari teorema tersebut memberikan bukti baru dari Schwartz -Zippel. Sampai sekarang, saya tahu enam bukti berbeda, dua di antaranya muncul di koran dan yang lainnya dirujuk di sana.

Teorema Alon-Furedi mengatakan sebagai berikut:

FA=i=1nAiFnfF[t_]=F[t1,,tn]Af(x)0minyixAyi#Aii=1nyi=i=1n#Aidegf

degf<min#Ai

Anurag
sumber
Bisakah Anda melihat lemma 2.2 di web.stanford.edu/~rrwill/graph-cr.pdf ? Inilah yang Ryan Williams maksudkan dengan komentarnya di bawah jawaban saya, dan itu ada dalam daftar ToDo saya sejak saat itu untuk memeriksa apakah dapat digeneralisasikan ke dering komutatif. Sepertinya saya Anda saat ini jauh lebih dalam tentang ini daripada saya, jadi mengapa Anda tidak mencobanya?
Thomas Klimpel
@ThomasKlimpel: Saya akan memodifikasi jawabannya. Saya menulisnya ketika saya baru mulai menggunakan teori stackexchange CS. Dan ya, Lemma 2.2 bekerja di atas ring komutasi semena-mena karena {0,1} ^ n selalu memenuhi kondisi (D).
Anurag
SRxySxyA1××AnRnAi
3

Formulasi asli lemma Schwartz-Zippel hanya berlaku untuk bidang:


PF[x1,x2,,xn]d0FSFr1,r2,,rnS
Pr[P(r1,r2,,rn)=0]d|S|.

Seseorang dapat memformulasikan kembali lemma sedemikian sehingga masuk akal untuk cincin komutatif yang sewenang-wenang:


PR[x1,x2,,xn]d0RSRs,tS:((uR:(u0su=tu))s=t)r1,r2,,rnS
Pr[P(r1,r2,,rn)=0]d|S|.

Keuntungan dari bukti dari wikipedia adalah bahwa ia secara umum menunjukkan bahwa reformulasi berlaku untuk cincin komutatif yang sewenang-wenang, yang telah diperhatikan dan dikerjakan oleh Emil Jeřábek di sini .

Ini memberikan bukti alternatif lemma Schwartz-Zippel, dengan membuktikan formulasi ulang untuk cincin komutatif umum, dan mendapatkan formulasi normal untuk bidang sebagai akibat wajar.

Thomas Klimpel
sumber
Polinomial adalah aljabar bebas untuk cincin komutatif, yaitu aljabar bebas yang dihasilkan oleh penjumlahan, inversi aditif, penggandaan dan konstanta relatif terhadap aksioma cincin komutatif. Harapan awal adalah menemukan generalisasi lemma Schwartz-Zippel untuk aljabar bebas yang juga mengandung inversi multiplikatif (digeneralisasi) relatif terhadap aksioma cincin reguler komutatif . Lihat juga karya Jan A. Bergstra .
Thomas Klimpel
1
Zm
1
@RyanWilliams Makalah On Zero of a Polinomial in a Finite Grid yang dikutip dalam jawaban baru-baru ini oleh Anurag Bishnoi menggeneralisasikan kedua lemma di atas, teorema Alon-Furedi dan lemma 2.2 dari kertas SODA'15 itu (dan membuktikan ketajaman ikatan) . Itu ada dalam daftar ToDo saya sejak komentar Anda untuk menemukan generalisasi seperti itu, jadi ini adalah pencapaian yang signifikan dari sudut pandang saya (jadi orang dapat memberi selamat kepada penulis).
Thomas Klimpel