قواعد جروبنر فوق مثاليَّات الحدوديَّات بأكثر من متغير

Grobner Basis Over Ideals of Multivariate Polynomial Ring

Khaled Suleiman Al-Akla
Faculty of Science || Baath University || Syria

قواعد جروبنر فوق مثاليَّات الحدوديَّات بأكثر من متغير

خالد سليمان العكله
كلية العلوم || جامعة البعث || سوريا

المقدمة:

ظهرت قواعد جروبنر في عام 1965على يد جروبنر (Gröbner)، كما قام العالم برونو بوشبرغر
(B. Buchberger) بتصميم خوارزمية لإيجاد هذه القواعد للحصول على طرائق لحل بعض المشكلات الأساسية في الجبر التبادلي ، وهو قسم من الجبر يهتم بالحدوديَات والمثاليات بالإضافة إلى الهندسة الجبرية[2،3]، وتساهم أيضاً في حل المسائل البعيدة عن الجبر مثل: مسائل القيم الحديَة والعديد من المسائل في العلوم التقنيَة، وفي عام 1985 استخدم العالم (N.K.Bose) طريقة جروبنر في أحد كتبه في حل بعض أنظمة المعادلات في الفضاء من الرتبة ( ) .[3] وفي عام2001 وضَّح (B. Buchberger) بمقدمة قصيرة أهميَة استخدام قواعد جروبنر في نظرية المعادلات، مؤخراً في معهد (Iniria) قام عدة باحثين بإدخال قواعد جروبنر في إيجاد حلول أنظمة المعادلات الجبرية من الدرجة ( ) [4]، لابد من التنويه إلى أنه عند استخدامنا الرمز فإننا نقصد به حقلاً وعندئذ تكون منطقة تكاملية.

مشكلة البحث:
تكمن في معرفة انتماء حدودية إلى مثالي ما مولَّد بمجموعة من الحدوديَّات والحل سيكون باستخدام خوارزمية التقسيم الإقليدي، بالإضافة إلى مسألة الاحتواء بين المثاليات باستخدام قواعد جروبنر.
هدف البحث: يهدف هذا البحث إلى دراسة موجزة لقواعد جروبنر وكيفية إيجادها، وأهم التطبيقات لهذه القواعد ومنها:
المسألة الرئيسيَّة في المثاليات: بفرض لدينا حلقة الحدوديَّات والمثالي باعتبار ، وبفرض عندئذ الشرط اللازم والكافي كي تنتمي الحدوديّة إلى هو أن يكون باقي قسمة على يساوي الصفر، وذلك باستخدام خوارزميَّة التقسيم الإقليدي.
مسألة الاحتواء: بفرض لدينا وسوف نقوم باستخدام قواعد جروبنر تحديد متى يكون أو أو
مواد البحث وطرائقه:
يعد نوع هذه الدراسة في هذا البحث جزء مرتبط بأطروحة ماجستير تتحدث عن بعض تطبيقات قواعد جروبنر فوق مثاليّات حلقة الحدوديّات بأكثر من متغير معتمدين الأسلوب الاستقرائي في التفكير، والمراد من هذا البحث هو تعميم خوارزميه القسمة بمتغير واحد إلى خوارزمية التقسيم الإقليدي بأكثر من متحول وتوظيفها في تطبيقات قواعد جروبنر المتعددة، ومن أهم أدوات هذا البحث الملاحظة البسيطة وبعض التعميمات، إضافة إلى المصادر والوثائق المختلفة .

تعريف1:

حلقة الحدوديات بـ متغير فوق الحقل يعبر عنها بالشكل وكل عنصر فيها يدعى حدودية ويأخذ الشكل: حيث:

ولنرمز للمثالي في حلقة الحدوديات بالرمز .
ندعو المثالي المؤلف من جميع الحدوديَات المرتبطة خطيَا وفق العلاقة:
بالمثالي المولد بـ هو عبارة عن المجموعة ، باعتبار مجموعة من الحدوديّات .
ترتيب الحدود في حلقة كثيرات الحدود:
تعريف2: بفرض لدينا المجموعة T^n المعرفة بالشكل
T^n={〖X^β=x〗_1^(β_1 )… x_n^(β_n ): β_i ∈N، i=1، …، n}
حيث ∈ N^n β=(β_(1 ) ,… ,β_(n ) ) .
إن الترتيب الحدودي في T^n هو الترتيب الكلي في T^n والذي يحقق الشرطين الآتيين:
من أجل جميع T^n ∈ X^β ,1 ≠ X^β .
إذا كانت X^β < X^α , إذاً X^ᵞ <X^β X^ᵞ X^α من أجل جميع T^n ∈ X^ᵞ .
بفرض أن هي حلقة الحدوديات بـ n متغيَر فوق الحقل
عندما n=1 نحصل على حلقة الحدوديات ، وبسهولة نستطيع ترتيب الحدود في كما يلي: < … 1< x < x^2 < x^3
أما في حالة العامة فإن الترتيب السابق غير ممكن لذا سنلجأ لأنواع أخرى من الترتيب وهناك عدة أنواع نذكر منها:
الترتيب المعجمي، الترتيب المعجمي الدرجي، الترتيب المعجمي الدرجي العكسي .
تعريف3: يعرف الترتيب المعجمي (order lexicographical) في T^n حيث:
〖> x〗_n >⋯ 〖 x〗_2 > 〖 x〗_1

α=(α_1، …، α_n )، β=(β_1، …، β_n )∈N^nكما يلي:
X^β < X^α ⟺ الاحداثيات الأولى المختلفة α_i، β_i في α و β من اليسار تحقق β_i < α_i
تعريف4: يعرف الترتيب المعجمي الدرجي (lexicographical order degree) في T^n حيث:
〖> x〗_n >⋯ 〖 x〗_2 > 〖 x〗_1
α=(α_1، …، α_n )، β=(β_1، …، β_n )∈N^n كما يلي:
X^β < X^α ⟺ ∑_(i=1)^n▒〖α_i<∑_(i=1)^n▒β_i 〗
وفي حال ∑_(i=1)^n▒〖α_i=∑_(i=1)^n▒β_i 〗 عندها في هذه الحالة نطبق ” lex” حيث
〖> x〗_n >⋯ 〖 x〗_2 > 〖 x〗_1

تعريف5: يعرف الترتيب المعجمي الدرجي العكسي: (lexicographical order reverse degree)
في T^n حيث: 〖> x〗_n >⋯ 〖 x〗_2 > 〖 x〗_1
α=(α_1، …، α_n )، β=(β_1، …، β_n )∈N^n
كما يلي X^β < X^α ⟺ ∑_(i=1)^n▒〖α_i<∑_(i=1)^n▒β_i 〗
أو ∑_(i=1)^n▒〖α_i=∑_(i=1)^n▒β_i 〗 و X^β < X^α الإحداثيات الأولى α_i، β_i في α و β من اليمين، والتي هي مختلفة، وتحقق β_i > α_i
سوف نعبر عن هذا الترتيب دائماً بـ ” degrevlex” .
ملاحظة: في حالة متغيرين إن الترتيبين degrevlex”” و ” deglex ” يكونان متطابقين أما في الحالة العامة فهذا غير محقق كما يظهر المثال التالي:
مثال 1:
〖 x〗_1^2 〖 x〗_2 〖 x〗_3 > 〖 x〗_1 〖 x〗_2^3 باستخدام ” deglex ” مع x l > x 2 > x 3 بينما
〖 x〗_1^2 〖 x〗_2 〖 x〗_3 < 〖 x〗_1 〖 x〗_2^3 باستخدام degrevlex”” مع x l > x 2 > x 3
تعريف6: لتكن العلاقة ترتيباً معيناً على إن الحدودية تكتب بشكل وحيد كما يلي:
، حيث ،
تعريف7: لنعرف المصطلحات التالية التي لها دور هام في قواعد جروبنر
lp(f)=X^( ): جداء القوة الرئيسي في ((the leading power product of f
lc(f)=〖 〗_i: المعامل الرئيسي في (the leading coefficient of f ) .
lt(f)=〖 〗_i X^( ): الحد الرئيسي في (the leading term of f ) .
مبرهنة هيلبرت الاساسية:
كل مثالي يمتلك مجموعة مولدة منتهية حيث .
بفرض مثالي في ويكون المثالي الرئيسي هوالمثالي المولد بالحدود الرئيسية لجميع عناصر عندئذ نكتب: .
مبرهنة [9]:
إذا كانت قاعدة جروبنر لـ عندئذٍ .
نتيجة:
بفرض قاعدة جروبنر للمثالي في ، وليكن عندئذٍ إذا وفقط إذا كان باقي قسمة بوساطة يساوي
(أو بالرموز )
ملاحظة [ 10]:
الخاصة المذكورة في النتيجة السابقة يمكن استخدامها تعريفاً لقاعدة جروبنر أي:
بفرض قاعدة ما للمثالي وبتحقق الشرط وذلك نجد أن هي قاعدة جروبنر.
خوارزمية القسمة:
إن خوارزمية القسمة في هي تعميم لخوارزمية القسمة في .
تعريف8: [5] لتكن من الحلقة نقول إن تختزل الى بوساطة بخطوة واحدة ونعبر عن ذلك إذا وفقط إذا كان يقسم ونكتب .
وبتعميم التعريف السابق [7]: إذا كان لدينا حدوديات في
و ، نقول عن إنه يختزل إلى بوساطة عناصر و نعبر عن ذلك: إذا وفقط إذا وجدت سلسلة الأدلة وسلسلة من الحدوديات حيث:

مبرهنة1(خوارزمية القسمة) : ليكن حقلاً و حلقة الحدوديات فوق الحقل وليكن عندئذٍ يوجد بحيث يتحقق:

نسمي باقي قسمة على
و لإيجاد سنعتمد على الخوارزمية التالية:
خوارزمية التقسيم الإقليدي:
المدخلات : ,
المخرجات : حيث : و تختزل بواسطة
{ } و
البداية :
طالما اعمل :
إذا وجدت بحيث تقسم إذاً اختر أقل قيمة بحيث تقسم

وإلا

مثال2: لتكن لدينا الحدوديات التالية:

وسوف نكتب الحدودية بدلالة الحدوديتين
بداية نكتب
وبعد إجراء العديد من الخطوات بحسب ما تمليه علينا خوارزمية التقسيم الإقليدي المذكورة آنفا نجد أن:

الآن سنتحدث عن قواعد جروبنر وطريقة بناءها وذلك بالاعتماد على خوارزمية بوشبرغر.
قواعد جروبنر: Grobner’s bases
تعريف 9:
بفرض مثالي في الحلقة عندئذ ندعو المجموعة بـــ قاعدة جروبنر لـ إذا تحقق ما يلي .
مبرهنة2:
إذا كانت قاعدة جروبنر لـ عندئذ .
مبرهنة3:
كل مثالي غير صفري يمتلك قاعدة جروبنر.
خوارزمية Buchberger لبناء قواعد جروبنر:
قبل التعرف على الخوارزمية التي نحسب من خلالها قواعد جروبنر لابد من ذكر تعريف
S- Polynomials لحدوديتين . ومن ثم ذكر مبرهنة بوشبرغر.
تعريف10 : [5]
بفرض حدوديتان من وليكن لدينا ترتيب حدود معين: على عندئذ نعبر عن بالعلاقة التالية:

مبرهنة Buchberger الأولى: [14،5] لتكن مجموعة من الحدوديات الغير صفرية في عندئذ قاعدة جروبنر وذلك من أجل إذا وفقط إذا تحقق الشرط:

وسنعرض الآن خطوات خوارزميّة تشكيل قواعد جروبنر:

المدخلات : f_i≠0(1≤i≤s) F={f_1,…,f_s }⊆k[x_1,…,x_n ] المخرجات : G={g_1,…,g_t } قاعدة جروبنر من أجل 〈f_1,…,f_s 〉
البداية : G:=F , G:=({f_i,f_j }│f_i≠f_j∈G)
طالما G≠0 اعمل
اختر أي {f,g}∈G
G:=G-{{f,g}}
S(f,g) 〖□(→┴G )〗_+ hحيث h تختزل بواسطة G
إذا h≠0 وبالتالي :
G:=G⋃{{u,h}│ u∈Gجميع أجل من }
G:=G⋃{h}
مثال3:
لتكن ولنستخدم الترتيب المعجمي lex”” مع ، من أجل حساب قاعدة جروبنر لـــــ ؟
في البداية
المرور الأول

(اختزلت بوساطة ) أي نكتب
وبعد إجراء العديد من الخطوات بحسب خوارزميّة بوشبرغر نتوصل إلى قاعدة جروبنر المعطاة بالشكل الآتي: ويكون وذلك مهما تكن .
ملاحظة: إن قواعد جروينر التي حصلنا عليها بطريقة بوشبرغر ليست وحيدة عموماً وذلك لأسباب منها:
في الخوارزمية السابقة يتم اختيار الحدوديات بشكل عشوائي.
من أجل أي ترتيب سوف نحصل على قاعدة جديدة.
لذا سنضع بعض الشروط عليها لتصبح وحيدة، من أجل ذلك سنعطي التعريف التالي:
تعريف 9: (قاعدة جروبنر الصغرى): [8] نقول عن قاعدة جروبنر إنها صغرى إذا تحقق:
من أجل كل و لا تقسم .

نتيجة1:
بفرض قاعدة جروبنر للمثالي ، و للحصول على قاعدة جروبنر صغرى من سنحذف كل يتحقق من أجلها وجود بحيث:
يقسم
ثم نقسم على وذلك .
تعريف10( قاعدة جروبنر المختزلة): [11] نقول عن قاعدة جروبنر إنها مختزلة إذا كان:
من اجل كل .
ومن أجل كل تختزل بواسطة .
بمعنى آخر: بفرض من أجل كل لا يوجد حد في قابل للقسمة بواسطة أي .
نلاحظ أن كل قاعدة جروبنر مختزلة تكون صغرى . وسنعرض الآن نظريه بوشبرغر الثانية:
مبرهنة Buchberger الثانية: [12،13] من أجل ترتيب حدود معين. أي مثالي مغاير للصفر يمتلك قاعدة جروبنر مختزلة وحيدة.
مثال4:
بفرض لدينا مستخدمين الترتيب
ولنوجد قاعدة جروبنر و جروبنر الصغرى ثم المختزلة ؟
المناقشة:
بعد تطبيق خوارزمية بوشبرغر لإيجاد قواعد جروبنر نجد أن:
وذلك باعتبار و
ولإيجاد قاعدة جروبنر الصغرى نقسم على( ( -1 فنجد

ونجد بسهولة أنها قاعدة جروبنر المختزلة للمثالي .
النتائج:
الآن سندرس بعض تطبيقات قواعد جروبنر في مثاليات حلقة الحدوديّات وأهمها:
المسألة الرئيسية للمثاليات (مسألة الانتماء الرئيسية): [5] بفرض لدينا و قاعدة جروبنر للمثالي المولّد بمجموعه من الحدوديات وباختيار أحد انواع الترتيب المذكورة سابقا نجد أنه:
ومن الجدير بالذكر هنا أنه إذا تحقق عندئذ فإن ستكتب بالشكل: حيث
بكلام آخر: نقول إنه لمعرفة انتماء حدوديّة ما إلى مثالي مولّد بمجموعة من الحدوديّات علينا إيجاد قاعدة جروبنر للمثالي ، باستخدام خوارزميه التقسيم الإقليدي سنجد أنه باقي قسمة بواسطه قاعدة جروبنر الناتجة هو الصفر وإلا فلن تنتمي الى
مثال5:
بفرض لدينا و وليكن مستخدمين ، باعتبار وليكن لدينا الحدوديَة المعطاة بالشكل: ولنثبت أن تنتمي لــ ؟
لنوجد قاعدة جروبنر باستخدام خوارزميّة Buchberger فنجد أنها تكتب بالشكل:

، ،
ومن السهل استنتاج أن هي قاعدة جروبنر المختزلة لأن يقسم
و يقسم .

وبعد إجراء العديد من الخطوات وذلك باستخدام خوارزميّة التقسيم الإقليدي نجد أن ونكتب بالشكل:
مسألة الاحتواء: [5] بفرض لدينا وسوف نقوم باستخدام قواعد جروبنر تحديد متى يكون أو أو ؟
لإثبات أن وكانت عندئذ يكفي إثبات أن وكنا قد ناقشنا ذلك في التطبيق السابق وكذلك الأمر لإثبات
لاختبار فيما إذا كان يكفي إثبات أن لكل من قاعدة جروبنر مختزلة مشتركة، أو يكفي إثبات أن و .
مثال6:
بفرض لدينا و والمطلوب إثبات فيما إذا كان أو أو ؟
لنوجد قاعدة جروبنر لــ باستخدام خوارزميّة بوشبرغر فنجد إنها معطاة بالعلاقة: وهي أيضاً قاعدة جروبنر المختزلة، ونجد أن قاعدة جروبنر المختزلة لـــ يعبر عنها بالشكل:
من الواضح أنهما غير متساويتين إذا نستنتج أن ،
كما من الواضح أن لأن ، وبسهوله نستطيع إثبات أن وذلك لأن
الخلاصة:
في نهاية هذا البحث نكون قد تعرفنا على قواعد جروبنر وعلى بعض الخوارزميات لإيجادها، وتحدثنا عن بعض تطبيقاتها ومن الجدير بالذكر بأن هنالك العديد من التطبيقات الأخرى التي استخدمت فيها قواعد جروبنر على سبيل المثال: إيجاد حلول جملة معادلات جبرية بـــــ n متغير وذلك في ، وتستخدم أيضاً لحساب المعاملات Syzygies لحدودية ما فوق حلقة أو مودول .
التوصيات:
إلى يومنا هذا مازالت هناك العديد من المحاولات للبحث في هذا المجال وذلك لإيجاد طرائق جديدة لمعرفة تلك القواعد، ونوصي بتعميم استخدام قواعد جروبنر في الفضاءات الإسقاطية لما لها من أهميّة، وتوسيع مجالات استخدامها لتشمل مجالات أخرى في الرياضيات البحتة والتطبيقية .
المراجع:
Bose, N. K. And Guiver, J. P, “Multidimensional Systems Theory: progress, directions, and open problems in multidimensional systems”, ch.6, PP.184-232 (1985).
Buchberger, B., “Grobner Bases: A Short Introduction for Systems Theorist, Computer Aided Systems Theory – EUROCAST”, Lecture Notes in Computer Science, 2178, PP.1-19, (2001).
Buchberger, B., “Ein Algorithmus zum Auffinden der Basis elemente des Restklassenringes nach einem nulldimensionalem Polynomideal”, Dissertation. Univ. of Innsbruck, (1965).
Yengui, I., “Algorithmes for comuting syzygies over V[X1…….Xn], a valuaion ring”, Département de Mathématiques, Faculté des Sciences de Sfax, Tunisie, (2011).
Adams, W.W. and Loustaunau, P”An Introduction to Grobner Bases Graduate Studies in Mathematics”, Vol.3, Mathematics Subject Classification. Primary 13P10, (2000).
Kreuzer, M. and Xiu, X., ” Efficient Grobner Basis Computation in Group Rings and Applications”, Braunschweig, (2013).
Elkadi, M. and Mourrain, B., “Some Applications of Bezoutians in Effective Algebraic Geometry”, inria-00073109, version 1, (1998).
Buchberger, B., “Introduction to Grobner Bases”, Talk at the Summer School Emerging Topics in Cryptographic Design and Cryptanalysis, Samos, Greece, (2007).
Gago.Vargas, J. “etal” (2006), Sudokus and Grobner bases: not only a divertimento, Computer Algebra in Scientific Computing: Lecture Notes in Computer Science, 4194, PP.155-165.
Garcia, N., Bases de Grobner, Departamento de mathematica, dmat.cfm.cl/Works/bases-de-grobner.pdf, (2009).

د. عبد الباسط الخطيب، د. سليمان الخطيب، عوض العبدلله، دراسة قواعد جروبنر وبعض تطبيقاتها، مجلة جامعة البعث، العدد 37 ((2015.
Lombardi, H. and Schuster, P. and Yengui, I.” The Gröbner ring conjecture in one variable”, Preprint, (2010).
Huishi, Li. Gröbner Bases in Ring Theory. World Scientific Publishing, (2011).
د. شوقي محمد الرَّاشد، بشرى هيثم جاد الله، دراسة في الهندسة الجبرية حول نظرية الحذف وتعميمها، (2017).
د. عبد الباسط الخطيب، د. سليمان الخطيب، محمد نور الخطيب، نظرية الحاصل لكثيري الحدود وبعض تطبيقاته، مجلة جامعة البعث، العدد) 38 (2016.