Schwartz – Zippelovo lemma - Schwartz–Zippel lemma

V matematice je Schwartz – Zippelovo lemma (nazývané také Lemma DeMillo-Lipton-Schwartz – Zippel) je nástroj běžně používaný v pravděpodobnosti polynomiální testování identity, tj. v problému určení, zda daný multivariační polynomiální je 0-polynom^{[je zapotřebí objasnění ]} (nebo shodně se rovná 0). To bylo objeveno nezávisle na Jack Schwartz,^[1] Richard Zippel,^[2] a Richard DeMillo a Richard J. Lipton, ačkoli verze DeMilla a Liptona byla uvedena rok před výsledkem Schwartze a Zippela.^[3] Konečnou polní verzi této vazby prokázal Øystein Ore v roce 1922.^[4]

Prohlášení o lemmatu

Vstup do problému je nproměnný polynom nad a pole F. Může nastat v následujících formách:

Algebraická forma

Například je

${ displaystyle (x_ {1} + 3x_ {2} -x_ {3}) (3x_ {1} + x_ {4} -1) cdots (x_ {7} -x_ {2}) equiv 0 ? }$

Abychom to vyřešili, můžeme to vynásobit a zkontrolovat, zda jsou všechny koeficienty 0. To však trvá exponenciální čas. Obecně lze polynom algebraicky reprezentovat pomocí aritmetický vzorec nebo obvod.

Determinant matice s polynomiálními položkami

Nechat

${ displaystyle p (x_ {1}, x_ {2}, ldots, x_ {n})}$

být určující z polynomiální matice.

V současné době není znám žádný subexponenciální čas algoritmus které mohou tento problém deterministicky vyřešit. Existují však randomizované polynomiální algoritmy pro testování polynomiálních identit. Jejich analýza obvykle vyžaduje vazbu na pravděpodobnost, že nenulový polynom bude mít kořeny v náhodně vybraných testovacích bodech. Lemma Schwartz – Zippel to stanoví následovně:

Věta 1 (Schwartz, Zippel). Nechat

${ displaystyle P in F [x_ {1}, x_ {2}, ldots, x_ {n}]}$

být nenulovým polynomem součtu stupeň d ≥ 0 přes pole F. Nechť S je konečná podmnožina F a nechť r₁, r₂, ..., r_n být vybrán náhodně nezávisle a jednotně ze S. Pak

${ displaystyle Pr [P (r_ {1}, r_ {2}, ldots, r_ {n}) = 0] leq { frac {d} {| S |}}.}$

V případě jedné proměnné to vyplývá přímo ze skutečnosti, že polynom z stupeň d nemůže mít více než d kořeny. Zdá se tedy logické si myslet, že podobné tvrzení by platilo i pro více proměnné polynomy. To je ve skutečnosti případ.

Důkaz. Důkaz je matematická indukce na n. Pro n = 1, jak již bylo zmíněno dříve, P může mít maximálně d kořeny. To nám dává základní případ. Nyní předpokládejme, že věta platí pro všechny polynomy v n − 1 proměnné. Pak můžeme zvážit P být polynomem v X₁ napsáním jako

${ displaystyle P (x_ {1}, tečky, x_ {n}) = součet _ {i = 0} ^ {d} x_ {1} ^ {i} P_ {i} (x_ {2}, tečky, x_ {n}).}$

Od té doby P není shodně 0, existuje i takhle ${ displaystyle P_ {i}}$ není shodně 0. Vezměte největší takový i. Pak ${ displaystyle deg P_ {i} leq d-i}$, protože stupeň ${ displaystyle x_ {1} ^ {i} P_ {i}}$ je nanejvýš d.

Nyní náhodně vybereme ${ displaystyle r_ {2}, tečky, r_ {n}}$ z S. Podle indukční hypotézy ${ displaystyle Pr [P_ {i} (r_ {2}, ldots, r_ {n}) = 0] leq { frac {d-i} {| S |}}.}$

Li ${ displaystyle P_ {i} (r_ {2}, ldots, r_ {n}) neq 0}$, pak ${ displaystyle P (x_ {1}, r_ {2}, ldots, r_ {n})}$ je stupně i (a tedy ne identicky nula) tak

${ displaystyle Pr [P (r_ {1}, r_ {2}, ldots, r_ {n}) = 0 | P_ {i} (r_ {2}, ldots, r_ {n}) neq 0 ] leq { frac {i} {| S |}}.}$

Pokud událost označíme ${ displaystyle P (r_ {1}, r_ {2}, ldots, r_ {n}) = 0}$ podle A, událost ${ displaystyle P_ {i} (r_ {2}, ldots, r_ {n}) = 0}$ podle Ba doplněk B podle ${ displaystyle B ^ {c}}$, my máme

${ displaystyle { begin {aligned} Pr [A] & = Pr [A cap B] + Pr [A cap B ^ {c}] & = Pr [B] Pr [A | B] + Pr [B ^ {c}] Pr [A | B ^ {c}] & leq Pr [B] + Pr [A | B ^ {c}] & leq { frac {di} {| S |}} + { frac {i} {| S |}} = { frac {d} {| S |}} end {zarovnáno}}}$

Aplikace

Důležitost věty Schwartz – Zippel a testování polynomiálních identit vyplývá z algoritmů, které se získají, až po problémy, které lze snížit na problém polynomiální testování identity.

Porovnání dvou polynomů

Vzhledem k dvojici polynomů ${ displaystyle p_ {1} (x)}$ a ${ displaystyle p_ {2} (x)}$, je

${ displaystyle p_ {1} (x) equiv p_ {2} (x)}$?

Tento problém lze vyřešit snížením na problém testování polynomiální identity. Je to rovnocenné kontrole, zda

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

Proto pokud to dokážeme určit

${ displaystyle p (x) equiv 0,}$

kde

${ displaystyle p (x) = p_ {1} (x) ; - ; p_ {2} (x),}$

pak můžeme určit, zda jsou oba polynomy ekvivalentní.

Porovnání polynomů má aplikace pro větvicí programy (nazývané také binární rozhodovací diagramy ). Program větvení jen pro čtení může být reprezentován a multilineární polynom který počítá (přes jakékoli pole) na {0,1} -vstupy stejné Booleovská funkce jako program větvení a dva programy větvení počítají stejnou funkci právě tehdy, pokud jsou odpovídající polynomy stejné. Identitu booleovských funkcí vypočítaných větvicími programy pro čtení lze tedy snížit na testování polynomiální identity.

Srovnání dvou polynomů (a tedy testování polynomiálních identit) má také aplikace v 2D kompresi, kde problém hledání rovnosti dvou 2D textů A a B se redukuje na problém porovnání rovnosti dvou polynomů ${ displaystyle p_ {A} (x, y)}$ a ${ displaystyle p_ {B} (x, y)}$.

Testování originality

Dáno ${ displaystyle n in mathbb {N}}$, je ${ displaystyle n}$ A prvočíslo ?

Jednoduchý randomizovaný algoritmus vyvinutý společností Manindra Agrawal a Somenath Biswas může pravděpodobnostně určit, zda ${ displaystyle n}$ je hlavní a využívá k tomu testování polynomiální identity.

Navrhují, aby všechna prvočísla n (a pouze prvočísla) splňují následující polynomiální identitu:

${ displaystyle (1 + z) ^ {n} = 1 + z ^ {n} ({ mbox {mod}} ; n).}$

To je důsledek Frobeniova endomorfismus.

Nechat

${ displaystyle { mathcal {P}} _ {n} (z) = (1 + z) ^ {n} -1-z ^ {n}.}$

Pak ${ displaystyle { mathcal {P}} _ {n} (z) = 0 ; ({ mbox {mod}} ; n)}$ iff n je prvočíslo. Důkaz lze nalézt v [4]. Protože však tento polynom má určitý stupeň ${ displaystyle n}$, a od té doby ${ displaystyle n}$ může nebo nemusí být prvočíslo, metoda Schwartz – Zippel by nefungovala. Agrawal a Biswas používají sofistikovanější techniku, která rozděluje ${ displaystyle { mathcal {P}} _ {n}}$ náhodným monickým polynomem malého stupně.

Prvočísla se používají v řadě aplikací, jako je velikost hash tabulky, pseudonáhodné generátory čísel a v generování klíčů pro kryptografie. Proto hledání velmi velkých prvočísel (v řádu (alespoň) ${ displaystyle 10 ^ {350} přibližně 2 ^ {1024}}$) se stává velmi důležitým a jsou vyžadovány efektivní algoritmy testování prvočísel.

Perfektní shoda

Nechat ${ displaystyle G = (V, E)}$ být graf z n vrcholy kde n je sudý. Ano G obsahovat a perfektní shoda ?

Věta 2 (Tutte 1947 ): A Tutte matrix determinant není a 0-polynomiální kdyby a jen kdyby existuje perfektní shoda.

Podmnožina D z E se nazývá shoda, pokud každý vrchol v PROTI je incident s maximálně jednou hranou v D. Shoda je dokonalá, pokud je každý vrchol v PROTI má přesně jednu hranu, která s ní naráží D. Vytvořit Tutte matrix A následujícím způsobem:

${ displaystyle A = { begin {bmatrix} a_ {11} & a_ {12} & cdots & a_ {1 { mathit {n}}} a_ {21} & a_ {22} & cdots & a_ {2 { mathit {n}}} vdots & vdots & ddots & vdots a _ {{ mathit {n}} 1} a _ {{ mathit {n}} 2} & ldots & a _ { mathit {nn}} end {bmatrix}}}$

kde

${ displaystyle a_ {ij} = { begin {cases} x_ {ij} ; ; { mbox {if}} ; (i, j) v E { mbox {a}} i j 0 ; ; ; ; { mbox {jinak}}. end {cases}}}$

Tutteho determinant matice (v proměnných X_ij, ${ displaystyle i$ ) je pak definován jako určující z toho šikmo symetrická matice který se shoduje se čtvercem pfaffian matice A a je nenulový (jako polynom), právě když existuje dokonalá shoda. Jeden pak může pomocí testování polynomiální identity zjistit, zda G obsahuje perfektní shodu. Pro grafy s polynomiálně ohraničenými permanenty existuje deterministický algoritmus černé skříňky (Grigoriev & Karpinski 1987).^[5]

Ve zvláštním případě vyváženého bipartitní graf na ${ displaystyle n = m + m}$ vrcholy má tato matice podobu a bloková matice

${ displaystyle A = { begin {pmatrix} 0 & X - X ^ {t} & 0 end {pmatrix}}}$

pokud první m řádky (resp. sloupce) jsou indexovány s první podmnožinou bipartice a poslední m řádky s doplňkovou podmnožinou. V tomto případě se pfaffian shoduje s obvyklým determinantem m × m matice X (až do podpisu). Tady X je Edmondsova matice.

Poznámky

Reference

externí odkazy

• Zvědavá historie lemmu Schwartz – Zippel tím, že Richard J. Lipton