توطئة شفارتز-زيبل

توطئة شفارتز-زيبل أو مبرهنة شفارتز-زيبل هي نتيجة أساسية في علم الاحتمال ولها تأثير على عدة مجالات في الرياضيات وعلم الحاسوب.

مقدمة

من الشائع جدا معرفة متطابقات متعددة الحدود مثل: $x^2-y^2=(x-y)(x+y)$ أو مبرهنة المربعات الأربع للاغرانج وهي:

$(a_1^1+a_2^2+a_3^3+a_4^4)(b_1^1+b_2^2+b_3^3+b_4^4)=(a_1{b}_1-a_2{b}_2-a_3{b}_3-a_4{b}_4{)}^2+(a_1{b}_2+a_2{b}_1+a_3{b}_4-a_4{b}_3{)}^2+(a_1{b}_3-a_2{b}_4+a_3{b}_1+a_4{b}_2{)}^2+(a_1{b}_4+a_2{b}_3-a_3{b}_2+a_4{b}_1{)}^2$

وهناك طريقة بسيطة لفحص هذه المتطابقات وهي عن طريق فتح الأقواس وفحص كل منهما إذا ما كانا متطابقين ! ولكن هذه العملية هي عملية أُسية بالنسبة لطول المدخل، إذ ان عدد احادية الحدود الناتجة عدد هو $(\genfrac{}{}{0ex}{}{n+d}{d})$ عندما d هو اعلى درجة احادي الحدود وما نريده إذا هي خوارزمية سريعة (أي تعقيدها الوقتي هو متعدد حدود بالنسبة للمدخل) ولكن هذا غير معلوم للان ومبرهنة شوارتز-زيبل تعطينا خوارزمية احتمالية سريعة.

تعريف المسألة

مسألة تطابق متعددات الحدود هي: معطى دائرة حسابية $C$ والتي تحسب متعدد الحدود $p(x_1,...,x_n)$ في $F[x_1,x_2,...,x_n]$ , جد خوارزمية حتمية التي تفحص إذا ما p صفر ويستخدم فقط $Poly(size(C))$ حسابات في $\mathbb{𝔽}$

المبرهنة

لنفرض ان $P\in F[x_1,x_2,...,x_n]$ متعدد حدودي ليس صفرا ودرجته $d\ge 0$ فوق حقل $\mathbb{𝔽}$ ولنفرض ان S مجموعة جزئية نهائية ل-$\mathbb{𝔽}$ حينها:

$P{r}_{r_1,r_2,...,r_n\in S}[P(r_1,r_2,...,r_n)=0]\le \frac{d}{\left|S\right|}$

البرهان

سوف نستخدم استقراء رياضي (Induction) على n ,

إذا n=1 , حسب المبرهنة الأساسية في الجبر هناك على الأكثر d جذور لذا فان المبرهنة تصح في هذه الحالة أي انه: $P{r}_{r_1\in S}[P(r_1)=0]\le \frac{d}{\left|S\right|}$

لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع $n-1$ متغيرات وبدون تقييد العموم نستطيع ان نفترض ان $p$ متعدد الحدود ب-$x_1$ ونستطيع ان نكتبه بالطريقة التالية:

$p(x_1,x_2,...,x_n)=\sum _{i=1}^d{x}_1^i{p}_i(x_2,...,x_n)$

بما ان $p$ ليس صفرا يوجد i بحيث ان $p_i$ ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور، مفهوم ضمنا أن $deg(p_i)\le d-i$ وذلك لان متعدد احادي الحدود $x_1^i$ درجته i وبما ان حاصل ضرب متعدد الحدود:$p_i(x_2,...,x_n)$ مع احادي الحدود هذا هو على الأكثر d لذا فان هذه الصفة صحيحة. الآن نختار عشوائيا $r_2,r_3,...,r_n$ من $S$ , وحسب فرضية الاستقراء الرياضي:

$P{r}_{r_2,...,r_n\in S}[p_i(r_1,r_2,...,r_n)=0]\le \frac{d-i}{\left|S\right|}$

.

إذا $p_i(r_2,...,r_n)\ne 0$ حينها $p(x_1,r_2,...,r_n)$ والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي أي:

$Pr[p_i(r_1,...r_n)=0|p_i(r_2,...,r_n)\ne 0]\le \frac{i}{\left|S\right|}$

حينها:

$Pr[p(r_1,...r_n)=0]\le Pr[p_i(r_2,...r_n)=0]+Pr[p_i(r_1,...r_n)=0|p_i(r_2,...,r_n)\ne 0]\le \frac{d-i}{\left|S\right|}+\frac{i}{\left|S\right|}=\frac{d}{\left|S\right|}$

استخدامات

1. هذه المبرهنة تقول بانه إذا كان عندنا في الحقل $\mathbb{𝔽}$ على الاقل $2d$ اعداد عندها يوجد خوارزمية احتمالية واحتمال خطأه على الأكثر $\frac{1}{2}$ وفي حالة انه يوجد اقل حينها نوسع $\mathbb{𝔽}$ ونختار نقاط عشوائية لذا فان هذه المسألة تتبع قسم التعقيد co-RP .
2. المبرهنة والتي تبحث مسألة تطابق متعددي حدود لها الكثير من التطبيقات في علم الحاسوب والرياضيات حيث ان مسألة التطابق كانت مهمة في برهنة $IP=PSPACE$ مسألة أخرى هي فحص إذا ما مخطوط معطى هو مخطط ثنائي وذلك حسب نظرية برهنها Tutte . ويمتد استخدامها لفحص إذا ما معطى عدد هو اولي.