عرض مصدر توطئة شفارتز-زيبل

{{يتيمة|تاريخ=نوفمبر 2017}}
{{لا مصدر|تاريخ=مارس 2016}}
'''توطئة شفارتز-زيبل''' أو '''مبرهنة شفارتز-زيبل''' هي نتيجة أساسية في [[نظرية الاحتمال|علم الاحتمال]] ولها تأثير على عدة مجالات في ال[[رياضيات]] و[[علم الحاسوب]].

== مقدمة ==
من الشائع جدا معرفة متطابقات [[متعددة الحدود]] مثل: <math>x^2-y^2=(x-y)(x+y) </math> أو [[مبرهنة المربعات الأربع للاغرانج]] وهي:
:<math>(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</math>
وهناك طريقة بسيطة لفحص هذه المتطابقات وهي عن طريق فتح الأقواس وفحص كل منهما إذا ما كانا متطابقين ! ولكن هذه العملية هي عملية أُسية بالنسبة لطول المدخل، إذ ان عدد احادية الحدود الناتجة عدد هو <math>\binom{n+d}{d}</math> عندما d هو اعلى درجة احادي الحدود وما نريده إذا هي خوارزمية سريعة (أي تعقيدها الوقتي هو متعدد حدود بالنسبة للمدخل) ولكن هذا غير معلوم للان ومبرهنة شوارتز-زيبل تعطينا خوارزمية '''احتمالية''' سريعة.

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

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

<div style="text-align: center;"><math> Pr_{r_1,r_2,...,r_n\in S}[P(r_1,r_2,...,r_n)=0]\le \frac{d}{|S|}</math></div>
== البرهان ==
سوف نستخدم [[استقراء رياضي]] (Induction) على n ,

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

لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع <math> n-1 </math> متغيرات وبدون تقييد العموم نستطيع ان نفترض ان <math> p</math> متعدد الحدود ب-<math> x_1 </math> ونستطيع ان نكتبه بالطريقة التالية:
<div style="text-align: center;"><math>p(x_1,x_2,...,x_n)=\sum_{i=1}^d x_1^i p_i(x_2,...,x_n) </math> </div>
بما ان <math>p</math> ليس صفرا يوجد i بحيث ان <math> p_i </math> ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور، مفهوم ضمنا أن <math> deg(p_i) \le d-i </math> وذلك لان متعدد احادي الحدود <math> x_1^i</math> درجته i وبما ان حاصل ضرب متعدد الحدود:<math> p_i(x_2,...,x_n) </math> مع احادي الحدود هذا هو على الأكثر d لذا فان هذه الصفة صحيحة. الآن نختار عشوائيا <math>r_2,r_3,...,r_n </math> من <math>S</math> , وحسب فرضية الاستقراء الرياضي:

<div style="text-align: center;"><math>Pr_{r_2,...,r_n\in S}[p_i(r_1,r_2,...,r_n)=0]\le \frac{d-i}{|S|} </math></div>.
إذا <math>p_i(r_2,...,r_n)\neq 0</math> حينها <math> p(x_1,r_2,...,r_n)</math> والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي أي:
<div style="text-align: center;"> <math> Pr[p_i(r_1,...r_n)=0|p_i(r_2,...,r_n)\neq 0] \le \frac{i}{|S|} </math></div>
حينها:
<div style="text-align: center;"> <math> 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)\neq 0] \le \frac{d-i}{|S|}+\frac{i}{|S|} = \frac{d}{|S|}</math></div>

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

{{شريط بوابات|رياضيات}}

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