قواعد غروبنر و أحد تطبيقاتها في الهندسة الجبريّة

استمع على ساوندكلاود 🎧

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

1- الهندسةُ الجبريّةُ و الجبرُ التّبادليّ و نظريّةُ مثاليّاتِ كثيراتِ الحدودِ Algebraic geometry، commutative algebra and polynomial ideal theory.

2- نظريّةُ اللامتغيّراتِ Invariant Theory

3- برهانُ نظريّةِ الأتمتةِ الهندسيّةِ Automated geometrical theorem proving

4- نظريّةُ التّشفير Coding Theory

5- برمجةُ الأعدادِ الصّحيحةِ Integer programming

6- التّوابعُ الهندسيّةُ الزّائديّةُ Hypergeometric function

7- علمُ الإحصاءِ Statistics

لماذا قواعد غروبنر ؟

ملاحظة: سنفرضُ فيما يلي أنّ k حقلاً ما.

من أحدِ أهمِّ تطبيقاتِ قواعدِ غروبنر حلّها لمسألةِ الإنتماء إلى مثالي ما I في الحلقة بعدة متحولات . فعلى الرّغم من تعميم خوارزميّة القسمةِ في ساحةِ المثاليّات الرّئيسيّة k[x] على الحلقة بعدة متحولاتٍ ، والاعتماد على تمهيدية ديكسون Dickson’s Lemma، و نظريّة القاعدة لهلبرت Hilbert Basis Theorem ، إلّا أنّه لم يتمّ حلّ مسألة انتماءِ كثيرِ حدودٍ ما إلى مثاليٍّ ما مختلفٍ عن المثاليِّ الصّفريّ . إذ كانت هنالك مشكلةُ تعيين باقي القسمةِ بشكلٍ وحيدٍ. وسنبيّن هذا في المثال التّالي.

مثال 1: لنعتمد التّرتيب الهجائيّ (سنذكر تعريف هذا التّرتيب لاحقاً) على الحلقةِ و لتكن كثيراتُ حدودٍ من R . بتقسيمِ f على ثمّ على نجد:

أما إذا قسّمنا f على ثمّ على فنجد:

نلاحظ أنّ ، ممّا يدلّ على عدمِ وحدانيّةِ تعيينِ باقي القسمة r . حيث أنَّه يعتمدُ على ترتيب كثيراتِ الحدودِ الّتي نقسِّمُ عليها أيّهما أوّل. باستخدام قواعد غروبنر نستطيع تعيين r بشكلٍ وحيدٍ وَدونَ أن تتأثّرَ بترتيبِ كثيراتِ الحدودِ الّتي نُقَسِّمُ عليها.

كي نستطيع عرض تعريف قاعدة غروبنر وذكر مثالٍ على كيفيّةِ حلِّ المسألةِ الآنفةِ الذِّكرِ لا بدَّ من التَّعرّفِ أوّلاً على علاقاتِ التَّرتيبِ على أُحاديّاتِ الحدّ في الحلقة

وَبعضِ المفاهيمِ والمصطلحاتِ.

تعاريف1.1

تعريف

التّرتيبُ الهجائيّ (الليكسوغرافيكيّ) : . Lexicographic Order

لتكن نقول إنّ إذا كان أوّل عددٍ مختلفٍ عن الصّفر - من اليسار- في الشّعاع الفرق موجِباً و نكتب إذا كان .

مثال 2:

إنّ أشعّةَ القاعدةِ النّظاميّةِ للفضاءِ المُتجهيِّ ،

تحقّق أنّ :

تعريف

التّرتيبُ الهجائيّ المدرَّج. Graded Lexicographic Order :

لتكن نقول إنّ إذا كان: أو و ، حيث :

و .

تعريف

التّرتيب الهجائيّ المدرَّج العكسيّ: Graded Reverse Lexicographic Order

لتكن نقول إنّ إذا كان:

أو:

و أوّلُ عددٍ مختلفٍ عن الصّفر - من اليمين - في الشّعاع الفرقِ سالباً، و نكتب إذا كان .

بعد أن عرَّفنا التّراتيبَ السّابقةَ على أحاديّاتِ الحدَ في الحلقة نستطيعُ أن نرتِّب كلَّ كثيرِ حدودٍ

فمثلاً إذا كان:

فإنّه يُكتب :

• وفقاً للتّرتيبِ الهجائيِّ بالشَّكل التّالي:

• وفقاً للتّرتيب الهجائيّ المُدرَّج بالشّكل التّالي:

• وفقاً للتّرتيب الهجائيّ المُدرَّج العكسيّ بالشّكل التّالي:

حيث حدود f مرتَّبةٌ تنازليَاً في جميعِ التّراتيبِ السّابقة.

تعريف2.1 ليكن كثيرُ حدودٍ مختلفٍ عن الصّفر و علاقةُ ترتيبٍ على أحاديّاتِ الحدَ في الحلقةِ سنعتبرُ الرّموز التّالية:

المثاليّات أحاديّة الحدّ Monomial Ideals

بعض التّعاريفِ الأساسيّة:

سنفرض فيما يلي أنّ مثاليٌّ ما مختلفٌ عن المثاليّ الصّفريّ إلا إذا أشرنا إلى خلاف ذلك.

تعريف1.2 نقول إنّ I أحاديّ الحدَ إذا وُجِدت مجموعةٌ جزئيّةٌ ، من الممكن أن تكون غيرُ منتهيةٍ، بحيث يتكوَّنI من جميعِ المجاميع المنتهيةِ حيث

. و نعبِّر عن I في هذه الحالة بالشّكل التّالي :

تعريف 2.2 بفرضI مثاليّ غيرُ صفريٍّ :

نرمز بـ LT(I) للمجموعة التّالية :

نرمز بـ 〈LT(I)〉 للمثاليّ المولّد بجميع عناصر المجموعة LT(I).

مُبرهنة : ليكن مثاليّاً ما، عندئذٍ :

1- 〈LT(I)〉إيديال أحاديّ الحدّ .

2- تُوجَد بحيث :

تعريف 3.2 نقول إنّ المجموعةَ المنتهيةَ قاعدة غروبنر لـ I إذا تحقق الشّرط التّالي :

خواص قواعد غروبنر

مبرهنة: إذا كان مثاليّاً ما وكانت قاعدة غروبنر و كثير حدودٍ ما فإنَّه يوجد وحيد يحقق الخاصَتَين التّاليتين:

1- جميع حدود r لا تقبل القسمة على أيٍّ من .

2- يوجد g∈I بحيث يكون : f=g+r.

حيث r هو باقي قسمة f على G بغضِّ النَّظر عن كيفيّةِ ترتيب عناصر G أثناء إجراء عمليّة القسمة .

ملاحظة: أيّاً كانَ كثيرُ الحدودِ سنرمز لباقي قسمته على المجموعةِ المُرتبة بـ . أمَا إذا كانت L قاعدة غروبنر فإنّه لا أهميّة لترتيبِ عناصرها .

تعريف 5.2 ليكن كثيرَي حدودٍ مختلفَين عن الصّفر.

1- إذا كان multidegree(f)= α وَ multidegree(f)= β نرمزبـ

حيث : . ندعو المضاعفَ المشتركَ الأصغرَ لِـ LM(f) وَ LM(g) و نرمز له بالرّمز :

2- نسمي S–كثير حدودٍ لِـ f وَ كثير الحدود التّالي:

نظريّة (معيار بوشبرجر): بفرض I مثاليّ ما و مجموعةٌ ما عندئذٍ:

G قاعدة غروبنر لـ I

كما وضع بوشبرجر خوارزميّةً من أجلِّ إيجادِ قواعد غروبنر باستخدامِ برامج جبر الحاسوب وغيرها:

خوارزميّة بوشبرجر

Buchberger’s Algorithm

نظريّة:

إذا كان مثاليّ ما فإنّنا نستطيعُ إيجادَ قاعدةِ غروبنر له بعددٍ منتهٍ من الخطوات كما في الخوارزميّة التّالية :

و من حسن حظِّ من يحتاج قواعد غروبنر في أبحاثِه عامّةً و الجبريّين خاصّةً أنّه يمكن إيجاد قاعدة غروبنر صُغرى و هي أيضاً مُبرمَجة في برامجِ الحاسوب المختلفةِ والّتي سنذكُر بعضاً منها فيما يلي:

تعريف 6.2: قاعدة غروبنر المختَزَلِة (المُخفَّضَة) Reduced Göebner basis.

إنّ قاعدة غروبنر المختزَلة لمثاليّ ما I هي قاعدة غروبنر له، G، تحقق الخاصَتَين التّاليَتين:

1-

2- أيّاً كانَ فإنَّ جميعَ أحاديّاتِ الحدّ فيه لا تنتمي للمثاليّ:

مبرهنة: إذا كان مثاليّ ما فإنّ قاعدة غروبنر المختزَلة له بالنّسبة لترتيبٍ معيّنٍ موجودةٌ ووحيدةٌ.

كيفيّةُ إيجادِ قاعدة غروبنر

مثال 3 : لنوجد قاعدة غروبنر للمثاليّ :

معتمِدين التّرتيبَ الهجائيَّ المدَرَّج glex.

1- نبحث فيما إذا كانت المجوعةُ قاعدةَ غروبنر لـ I .

نلاحظ أنّ:

و بالتّالي فإنّ المجموعةَ F ليست قاعدة غروبنر لـ I.

2- إنّ و باقي قسمته على F يساوي ذلك نضيفه إلى المجموعة المولِّدة F فيصبح لدينا . نلاحظ الآن أنّ:

، و لكن لذلك نضيفه إلى F فتصبح .

و بتكرار الإجراء ذاته نجد أنّ قاعدة غروبنر لـ I هي :

سنعرض الآن أحد التّطبيقاتِ الهامةِ لنظريّةِ قواعد غروبنر:

مسألة الانتماءِ إلى مثاليّ :

The Ideal Membership Problem

استطاعت نظريّة قواعد غروبنر مع خوارزميّة القسمة أن تحلّ هذه المسألة و هي : إذا كان مثاليّاً ما و كان كثيرُ حدودٍ ما نستطيعُ معرفةَ فيما إذا كان g ينتمي إلى I أم لا .

مثال 4: لنأخذ في الحلقة R= k[x،y،z]:

معتَمِدين التّرتيب الهجائيّ المدَرَّج grlex، هل ؟

1- نبحث فيما إذا كانت المجوعة قاعدة غروبنر لـ I .

نلاحظ أنّ الحدّ الرئيسيّ لكثير الحدود

وهو

لا ينتمي للمثالي :

و بالتالي ليست قاعدة غروبنر لـ I.

2- بما أنّ ليست قاعدة غروبنر لـ I نوجد قاعدة غروبنر له .

بحساب قاعدةِ غروبنر المختزَلة (المخفَّضة) لـ I وفق التّرتيب الهجائيّ المدرَّج نجد أنّها على الشّكل التّالي :

بقسمة g على نجد أنّ باقي القسمة معدوم :

ممّا يعني أنّ .

يُعتَبَر إيجادُ قواعدِ غروبنر مع خوارزميّة بوشبرجِر من المفاهيمِ الأساسيّةِ في الجبر بُغيةَ إجراء حساباتٍ أكثر تقدّماً في الهندسة الجبريّة، كنظريّة الإبعاد وفي الإحصاء وفي نظريّة التحكّم والهندسة وعلم الأحياء الجزيئي وغيرها. كما أنّه من أجلّ إيجادها بدّقة في حالة الحسابات الطويلة والمعقدّة يمكننا الاعتماد على برامج الحاسوب CoCoA،Macaulay2 ،Magma ، Singular، Maple، Mathematica.

لقد كانت تجربتي الأولى في قواعد غروبنر في العام 2006، حينما وجّهني البروفيسور أنطوان شومبر لوارAntoine Chambert-Loir ( حديث العضويّة في المعهد الجامعيّ في فرنسا) مشكوراً لإجراء دراسة عنها. أتمنى أن تحمل كل الفائدة لكلِّ باحث و مهتّم في الرّياضيات وتطبيقاتها المختلفة.

المصادر :

- Bernd Sturmfels، W H A T I S a Gröbner Basis? VOLUME 52، NUMBER 10، NOVEMBER 2005.

- David Cox، John Little، Donal O’Shea، Ideals، Varieties، and Algorithms Singer Verlag، Berlin and New York، 1992.