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

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

مقدمة

من الشائع جدا معرفة متطابقات متعددة الحدود مثل: $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}$

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

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

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

المبرهنة

لنفرض ان $P\in F[x_{1},x_{2},...,x_{n}]$ متعدد حدودي ليس صفرا ودرجته $d\geq 0$ فوق حقل $\mathbb {F}$ ولنفرض ان S مجموعة جزئية نهائية ل-$\mathbb {F}$ حينها:

$Pr_{r_{1},r_{2},...,r_{n}\in S}[P(r_{1},r_{2},...,r_{n})=0]\leq {\frac {d}{|S|}}$

البرهان

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

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

لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع $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})\leq d-i$ وذلك لان متعدد احادي الحدود $x_{1}^{i}$ درجته i وبما ان حاصل ضرب متعدد الحدود:$p_{i}(x_{2},...,x_{n})$ مع احادي الحدود هذا هو على الأكثر d لذا فان هذه الصفة صحيحة. الآن نختار عشوائيا $r_{2},r_{3},...,r_{n}$ من $S$ , وحسب فرضية الاستقراء الرياضي:

$Pr_{r_{2},...,r_{n}\in S}[p_{i}(r_{1},r_{2},...,r_{n})=0]\leq {\frac {d-i}{|S|}}$

.

إذا $p_{i}(r_{2},...,r_{n})\neq 0$ حينها $p(x_{1},r_{2},...,r_{n})$ والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي أي:

$Pr[p_{i}(r_{1},...r_{n})=0|p_{i}(r_{2},...,r_{n})\neq 0]\leq {\frac {i}{|S|}}$

حينها:

$Pr[p(r_{1},...r_{n})=0]\leq Pr[p_{i}(r_{2},...r_{n})=0]+Pr[p_{i}(r_{1},...r_{n})=0|p_{i}(r_{2},...,r_{n})\neq 0]\leq {\frac {d-i}{|S|}}+{\frac {i}{|S|}}={\frac {d}{|S|}}$

استخدامات

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