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

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

مقدمة

من الشائع جدا معرفة متطابقات متعددة الحدود مثل: $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 صفر ويستخدم فقط $P o l y (s i z e (C))$ حسابات في $F$

المبرهنة

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

P r_{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 جذور لذا فان المبرهنة تصح في هذه الحالة أي انه: $P r_{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 ليكون الأكبر وصفته كما هو مذكور، مفهوم ضمنا أن $d e g (p_{i}) \leq 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] \leq \frac{d - i}{| S |}

.

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

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

حينها:

P r [p (r_{1}, . . . r_{n}) = 0] \leq P r [p_{i} (r_{2}, . . . r_{n}) = 0] + P r [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 |}

استخدامات

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

بوابة رياضيات