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

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

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

${\displaystyle (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}}$

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

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

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

${\displaystyle 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 جذور لذا فان المبرهنة تصح في هذه الحالة أي انه: ${\displaystyle Pr_{r_{1}\in S}[P(r_{1})=0]\leq {\frac {d}{|S|}}}$

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

${\displaystyle p(x_{1},x_{2},...,x_{n})=\sum _{i=1}^{d}x_{1}^{i}p_{i}(x_{2},...,x_{n})}$

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

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

.

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

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

حينها:

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