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

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

 مقدمة 
من الشائع جدا معرفة متطابقات متعددة الحدود مثل:  أو مبرهنة المربعات الأربع للاغرانج وهي:

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

 تعريف المسألة 
مسألة تطابق متعددات الحدود هي: معطى دائرة حسابية  والتي تحسب متعدد الحدود  في  , جد خوارزمية حتمية التي تفحص إذا ما p صفر ويستخدم فقط  حسابات في 

 المبرهنة 
لنفرض ان  متعدد حدودي ليس صفرا ودرجته  فوق حقل  ولنفرض ان S مجموعة جزئية نهائية ل- حينها:

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

إذا n=1 , حسب المبرهنة الأساسية في الجبر هناك على الأكثر d جذور لذا فان المبرهنة تصح في هذه الحالة أي انه: 

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

بما ان  ليس صفرا يوجد i بحيث ان  ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور، مفهوم ضمنا أن  وذلك لان متعدد احادي الحدود  درجته i وبما ان حاصل ضرب متعدد الحدود: مع احادي الحدود هذا هو على الأكثر d لذا فان هذه الصفة صحيحة. الآن نختار عشوائيا  من  , وحسب فرضية الاستقراء الرياضي:

.
إذا  حينها  والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي أي:

حينها:


 استخدامات 
 هذه المبرهنة تقول بانه إذا كان عندنا في الحقل  على الاقل  اعداد عندها يوجد خوارزمية احتمالية واحتمال خطأه على الأكثر  وفي حالة انه يوجد اقل حينها نوسع  ونختار نقاط عشوائية لذا فان هذه المسألة تتبع قسم التعقيد co-RP .
 المبرهنة والتي تبحث مسألة تطابق متعددي حدود لها الكثير من التطبيقات في علم الحاسوب والرياضيات حيث ان مسألة التطابق كانت مهمة في برهنة  مسألة أخرى هي فحص إذا ما مخطوط معطى هو مخطط ثنائي وذلك حسب نظرية برهنها Tutte . ويمتد استخدامها لفحص إذا ما معطى عدد هو اولي.

تصنيف:جبر حاسوبي
تصنيف:مبرهنات
تصنيف:متعددات الحدود
تصنيف:موضوعات