قاعدة جروبنر

في الرياضيات ، وبشكل أكثر تحديدًا في الجبر الحاسوبي ، والهندسة الجبرية الحسابية ، والجبر التبادلي الحسابي ، فإن أساس جروبنر هو نوع معين من مجموعة توليد مثالية في حلقة متعددة الحدود K [ x ₁ ، ...، x _n ] على حقل K. يسمح أساس جروبنر باستنتاج العديد من الخصائص المهمة للمثالية والتنوع الجبري المرتبط بها بسهولة، مثل البعد وعدد الأصفار عندما يكون منتهيًا. يعد حساب أساس جروبنر أحد الأدوات العملية الرئيسية لحل أنظمة المعادلات متعددة الحدود وحساب صور التنوعات الجبرية تحت الإسقاطات أو الخرائط النسبية .

يمكن اعتبار حساب أساس جروبنر بمثابة تعميم متعدد المتغيرات وغير خطي لكل من خوارزمية إقليدس لحساب القواسم المشتركة الأعظم للعديد من الحدود ، والإزالة الغاوسية للأنظمة الخطية. ^[1]

تم تقديم قواعد جروبنر بواسطة برونو بوخبرجر في أطروحته للدكتوراه عام 1965، والتي تضمنت أيضًا خوارزمية لحسابها ( خوارزمية بوخبرجر ). أطلق عليها اسم مستشاره فولفجانج جروبنر . في عام 2007، حصل بوخبرجر على جائزة باريس كانيللاكيس للنظرية والتطبيق من جمعية آلات الحوسبة عن هذا العمل. ومع ذلك، قدم عالم الرياضيات الروسي نيكولاي غونتر فكرة مماثلة في عام 1913، ونشرت في العديد من المجلات الرياضية الروسية. تجاهل المجتمع الرياضي هذه الأوراق إلى حد كبير حتى إعادة اكتشافها في عام 1987 بواسطة بودو رينشوخ وآخرون. ^[2] تم تطوير مفهوم مماثل لمتسلسلة القوى المتعددة المتغيرات بشكل مستقل بواسطة هيسوكي هيروناكا في عام 1964، والذي أطلق عليها اسم القواعد القياسية . وقد استخدم بعض المؤلفين هذا المصطلح أيضًا للإشارة إلى قواعد جروبنر.

تم توسيع نظرية قواعد جروبنر من قبل العديد من المؤلفين في اتجاهات مختلفة. وقد تم تعميمها على هياكل أخرى مثل كثيرات الحدود على حلقات مثالية أساسية أو حلقات كثيرات الحدود ، وكذلك بعض فئات الحلقات غير التبادلية والجبر، مثل جبر الخام .

تُعرَّف قواعد جروبنر في المقام الأول للمثل العليا في حلقة متعددة الحدود فوق حقل K. وعلى الرغم من أن النظرية تعمل لأي حقل، فإن معظم حسابات قاعدة جروبنر تتم إما عندما يكون K هو حقل الأعداد الكسرية أو الأعداد الصحيحة modulo عدد أولي. ${\displaystyle R=K[x_{1},\ldots ,x_{n}]}$

في سياق قواعد جروبنر، يتم تمثيل كثير الحدود غير الصفرية في بشكل شائع كمجموع حيث تكون عناصر غير صفرية لـ K ، تسمى معاملات ، و تكون أحاديات الحدود (تسمى حاصل ضرب القوى من قبل بوخبرجر وبعض أتباعه) من الشكل حيث تكون أعدادًا صحيحة غير سالبة. يسمى المتجه متجه الأس للحدود الأحادية. عندما تكون قائمة المتغيرات ثابتة، غالبًا ما يتم اختصار تدوين الحدود الأحادية على النحو التالي${\displaystyle R=K[x_{1},\ldots ,x_{n}]}$${\displaystyle c_{1}M_{1}+\cdots +c_{m}M_{m},}$${\displaystyle c_{i}}$${\displaystyle M_{i}}$${\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}},}$${\displaystyle a_{i}}$${\displaystyle A=[a_{1},\ldots ,a_{n}]}$${\displaystyle X=[x_{1},\ldots ,x_{n}]}$${\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}=X^{A}.}$

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

إذا كانت مجموعة منتهية من الحدوديات في حلقة الحدوديات R ، فإن المثال المثالي الناتج عن F هو مجموعة التركيبات الخطية لعناصر F ذات المعاملات في R ؛ أي مجموعة الحدوديات التي يمكن كتابتها باستخدام${\displaystyle F=\{f_{1},\ldots ,f_{k}\}}$ ${\textstyle \sum _{i=1}^{k}g_{i}f_{i}}$${\displaystyle g_{1},\ldots ,g_{k}\in R.}$

تتطلب جميع العمليات المتعلقة بقواعد جروبنر اختيار ترتيب إجمالي على أحاديات الحدود، مع الخصائص التالية للتوافق مع الضرب. لجميع أحاديات الحدود M و N و P و

1. ${\displaystyle M\leq N\Longleftrightarrow MP\leq NP}$
2. ${\displaystyle M\leq MP}$.

يُطلق أحيانًا على الطلب الإجمالي الذي يلبي هذه الشروط اسم الطلب المقبول .

تشير هذه الشروط إلى أن الترتيب هو ترتيب جيد ، أي أن كل تسلسل متناقص بدقة من أحاديات الحدود هو منتهٍ.

على الرغم من أن نظرية أساس جروبنر لا تعتمد على اختيار معين لترتيب أحادي الحد المقبول، فإن ثلاثة ترتيبات أحادية الحد مهمة بشكل خاص للتطبيقات:

• الترتيب المعجمي ، ويسمى عادة lex أو plex (للترتيب المعجمي البحت).
• الدرجة الكلية للترتيب المعجمي العكسي ، ويسمى عادة ديجريفلكس .
• ترتيب الإزالة ، lexdeg .

تم تقديم نظرية أساس جروبنر في البداية للترتيب المعجمي. وسرعان ما أدرك الناس أن أساس جروبنر لـ degrevlex أسهل في الحساب دائمًا تقريبًا، وأنه من الأسهل دائمًا تقريبًا حساب أساس جروبنر lex عن طريق حساب أساس degrevlex أولاً ثم استخدام "خوارزمية تغيير الترتيب". عندما تكون هناك حاجة إلى الاستبعاد، فإن degrevlex ليس مناسبًا؛ يمكن استخدام كل من lex و lexdeg ولكن، مرة أخرى، العديد من العمليات الحسابية سهلة نسبيًا مع lexdeg ومستحيلة تقريبًا مع lex.

بمجرد تحديد ترتيب أحادي الحد، يتم ترتيب حدود كثير الحدود (حاصل ضرب أحادي الحد بمعامله غير الصفري) بشكل طبيعي حسب أحاديات الحدود المتناقصة (لهذا الترتيب). وهذا يجعل تمثيل كثير الحدود كقائمة مرتبة من أزواج متجهات المعامل والأس تمثيلًا قانونيًا لكثيرات الحدود (أي أن كثيرتي الحدود متساويتان إذا وفقط إذا كان لهما نفس التمثيل).

يُطلق على الحد الأول (الأعظم) لكثيرة الحدود p لهذا الترتيب والحدود الأحادية والمعامل المقابلين على التوالي اسم الحد الرئيسي والحدود الأحادية الرئيسية والمعامل الرئيسي ويُشار إليهما في هذه المقالة بـ lt( p ) وlm( p ) و lc( p ) .

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

العمليات الحدودية الأخرى التي تتضمنها حسابات أساس جروبنر متوافقة أيضًا مع الترتيب أحادي الحد؛ أي أنه يمكن إجراؤها دون إعادة ترتيب النتيجة:

• تتمثل عملية إضافة كثيرات الحدود في دمج القائمتين المتوافقتين من المصطلحات، مع معاملة خاصة في حالة وجود تعارض (أي عندما يظهر نفس الحد الواحد في كثيرات الحدود).
• تتكون عملية ضرب كثير الحدود في عدد قياسي من ضرب كل معامل في هذا العدد القياسي، دون أي تغيير آخر في التمثيل.
• تتكون عملية ضرب كثير الحدود في أحادي الحدود m من ضرب كل أحادي حدود من كثير الحدود في m . وهذا لا يغير مصطلح الترتيب حسب تعريف ترتيب أحادي الحدود.

ليكن و حدين أحاديين، مع متجهات أسية و${\displaystyle M=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}}$${\displaystyle N=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}}$${\displaystyle A=[a_{1},\ldots ,a_{n}]}$${\displaystyle B=[b_{1},\ldots ,b_{n}].}$

يقال أن M يقسم N ، أو أن N مضاعف لـ M ، إذا كان لكل i ؛ أي إذا كان A ليس أكبر من B من حيث المكونات. في هذه الحالة، يتم تعريف الحاصل على أنه بعبارة أخرى، متجه الأس هو الطرح المكوني لمتجهي الأس لـ N و M.${\displaystyle a_{i}\leq b_{i}}$${\textstyle {\frac {N}{M}}}$${\textstyle {\frac {N}{M}}=x_{1}^{b_{1}-a_{1}}\cdots x_{n}^{b_{n}-a_{n}}.}$${\textstyle {\frac {N}{M}}}$

القاسم المشترك الأعظم gcd( M , N ) لـ M و N هو أحادي الحد الذي يكون متجه أسه هو الحد الأدنى المكون لـ A و B. يتم تعريف المضاعف المشترك الأصغر lcm( M , N ) على نحو مماثل مع max بدلاً من min . ${\textstyle x_{1}^{\min(a_{1},b_{1})}\cdots x_{n}^{\min(a_{n},b_{n})}}$

واحد لديه

${\displaystyle \operatorname {lcm} (M,N)={\frac {MN}{\gcd(M,N)}}.}$

إن اختزال كثير الحدود بواسطة كثيرات حدود أخرى فيما يتعلق بترتيب أحادي الحد هو أمر أساسي في نظرية أساس جروبنر. إنه تعميم لكل من اختزال الصف الذي يحدث في خطوات الإزالة الغاوسية والقسمة للقسمة الإقليدية لكثيرات الحدود أحادية المتغير . ^[1] عندما يتم إكماله قدر الإمكان، يُطلق عليه أحيانًا القسمة المتعددة المتغيرات على الرغم من عدم تحديد نتيجته بشكل فريد.

يعد الاختزال بالرصاص حالة خاصة من الاختزال يسهل حسابها. وهو أمر أساسي لحساب أساس جروبنر، حيث لا يلزم الاختزال العام إلا في نهاية حساب أساس جروبنر، للحصول على أساس جروبنر مخفض من أساس غير مخفض.

دع الترتيب الأحادي المقبول يكون ثابتًا، والذي يشير إليه كل مقارنة أحادية الحد التي ستحدث في هذا القسم.

تكون كثيرة الحدود f قابلة للاختزال بواسطة كثيرة حدود أخرى g إذا كانت أحادية الحدود الرئيسية lm( f ) مضاعفًا لـ lm( g ) . تكون كثيرة الحدود f قابلة للاختزال بواسطة g إذا كانت أحادية الحدود لـ f مضاعفًا لـ lm( g ) . (لذا، إذا كانت f قابلة للاختزال بواسطة g ، فهي قابلة للاختزال أيضًا، ولكن قد تكون f قابلة للاختزال بدون أن تكون قابلة للاختزال بواسطة g.)

افترض أن f قابلة للاختزال بواسطة g ، وليكن cm حدًا لـ f بحيث يكون الحد الأحادي m مضاعفًا لـ lm( g ) . يتكون الاختزال أحادي الخطوة لـ f بواسطة g من استبدال f بـ

${\displaystyle \operatorname {red} _{1}(f,g)=f-{\frac {c}{\operatorname {lc} (g)}}\,{\frac {m}{\operatorname {lm} (g)}}\,g.}$

تزيل هذه العملية أحادي الحد m من f دون تغيير الحدود مع أحادي الحد الأكبر من m (لترتيب أحادي الحد). على وجه الخصوص، يؤدي الاختزال الأولي بخطوة واحدة لـ f إلى إنتاج متعدد الحدود تكون جميع أحاديات الحد فيه أصغر من lm( f ) .

بالنظر إلى مجموعة محدودة G من كثيرات الحدود، يمكننا القول إن f قابلة للاختزال أو قابلة للاختزال الأولي بواسطة G إذا كانت قابلة للاختزال أو قابلة للاختزال الأولي، على التوالي، بواسطة عنصر واحد على الأقل من g من G. في هذه الحالة، يكون الاختزال بخطوة واحدة (أو اختزال أولي بخطوة واحدة) لـ f بواسطة G هو أي اختزال بخطوة واحدة (أو اختزال أولي بخطوة واحدة) لـ f بواسطة عنصر من G.

يتكون الاختزال (الكامل) (أو الاختزال التمهيدي) لـ f بواسطة G من تكرار عمليات الاختزال ذات الخطوة الواحدة (أو الاختزال التمهيدي ذي الخطوة الواحدة) حتى الحصول على كثير حدود غير قابل للاختزال (أو غير قابل للاختزال التمهيدي) بواسطة G. يُطلق عليه أحيانًا الشكل الطبيعي لـ f بواسطة G. بشكل عام، لا يتم تعريف هذا الشكل بشكل فريد لأنه يوجد بشكل عام العديد من عناصر G التي يمكن استخدامها لاختزال f ؛ هذا عدم التفرد هو نقطة البداية لنظرية أساس جروبنر.

يُظهر تعريف الاختزال على الفور أنه إذا كان h شكلًا طبيعيًا لـ f بواسطة G ، فلدينا

${\displaystyle f=h+\sum _{g\in G}q_{g}\,g,}$

حيث أن h غير قابلة للاختزال بواسطة G و هي حدوديات بحيث في حالة الحدوديات أحادية المتغير، إذا كانت G تتكون من عنصر واحد g ، فإن h هو باقي القسمة الإقليدية لـ f على g ، و q _g هو الحاصل. علاوة على ذلك، فإن خوارزمية القسمة هي بالضبط عملية الاختزال الأولي. لهذا السبب، يستخدم بعض المؤلفين مصطلح القسمة المتعددة المتغيرات بدلاً من الاختزال. ${\displaystyle q_{g}}$${\displaystyle \operatorname {lm} (q_{g}\,g)\leq \operatorname {lm} (f).}$

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

في هذا المثال المكون من متغيرين، الترتيب الأحادي الذي يتم استخدامه هو الترتيب المعجمي مع ونفكر في اختزال ، بواسطة مع${\displaystyle x>y,}$${\displaystyle f=2x^{3}-x^{2}y+y^{3}+3y}$${\displaystyle G=\{g_{1},g_{2}\},}$$${\displaystyle {\begin{aligned}g_{1}&=x^{2}+y^{2}-1,\\g_{2}&=xy-2.\end{aligned}}}$$

بالنسبة لخطوة الاختزال الأولى، يمكن اختزال الحد الأول أو الحد الثاني من الدالة f . ومع ذلك، فإن اختزال الحد يعني إزالة هذا الحد على حساب إضافة حدود أدنى جديدة؛ إذا لم يكن الحد القابل للاختزال الأول هو الذي يتم اختزاله، فقد يحدث أن يؤدي اختزال آخر إلى إضافة حد مماثل، والذي يجب اختزاله مرة أخرى. لذلك، من الأفضل دائمًا اختزال الحد القابل للاختزال الأكبر (بالنسبة لترتيب أحادي الحد) أولاً؛ أي، على وجه الخصوص، اختزال أولي أولاً حتى نحصل على متعددة حدود غير قابلة للاختزال أوليًا.

الحد الرئيسي لـ f يمكن اختزاله بـ وليس بـ ، لذا تتكون خطوة الاختزال الأولى من الضرب في -2 x وإضافة النتيجة إلى f : ${\displaystyle 2x^{3}}$${\displaystyle g_{1}}$${\displaystyle g_{2}.}$${\displaystyle g_{1}}$

${\displaystyle f\;\xrightarrow {-2xg_{1}} \;f_{1}=f-2xg_{1}=-x^{2}y-2xy^{2}+2x+y^{3}+3y.}$

الحد الرئيسي لـ هو مضاعف للحدود الأحادية الرئيسية لكل من و لذا، يكون لدى المرء خياران لخطوة الاختزال الثانية. إذا اختار المرء، فإنه يحصل على حدود متعددة يمكن اختزالها مرة أخرى بمقدار${\displaystyle -x^{2}y}$${\displaystyle f_{1}}$${\displaystyle g_{1}}$${\displaystyle g_{2},}$${\displaystyle g_{2},}$${\displaystyle g_{2}\colon }$

${\displaystyle f\;\xrightarrow {-2xg_{1}} \;f_{1}\;\xrightarrow {xg_{2}} \;-2xy^{2}+y^{3}+3y\;\xrightarrow {2yg_{2}} \;f_{2}=y^{3}-y.}$

لا يمكن إجراء أي تخفيض آخر، كما هو الحال مع التخفيض الكامل لـ f . ${\displaystyle f_{2}}$

نحصل على نتيجة مختلفة مع الخيار الآخر للخطوة الثانية:

${\displaystyle f\;\xrightarrow {-2xg_{1}} \;f_{1}\;\xrightarrow {yg_{1}} \;-2xy^{2}+2x+2y^{3}+2y\;\xrightarrow {2yg_{2}} \;f_{3}=2x+2y^{3}-2y.}$

مرة أخرى، النتيجة غير قابلة للاختزال، على الرغم من أن التخفيضات في الرصاص فقط هي التي أجريت. ${\displaystyle f_{3}}$

باختصار، يمكن أن يؤدي التخفيض الكامل لـ f إلى أي من الأمرين أو${\displaystyle f_{2}=y^{3}-y}$${\displaystyle f_{3}=2x+2y^{3}-2y.}$

من أجل التعامل مع المشكلات التي تفرضها هذه اللا تفردية، قدم بوخبرغر قواعد جروبنر ومتعددات الحدود S. بديهيًا، يمكن اختزال 0 = f − f إلى وهذا يعني أن تنتمي إلى المثالية الناتجة عن G . لذا، لا يتغير هذا المثالي عن طريق الإضافة إلى G ، وهذا يسمح بمزيد من الاختزالات. على وجه الخصوص، يمكن اختزالها إلى بواسطة وهذا يعيد تفرد الشكل المختزل. ${\displaystyle f_{2}-f_{3}.}$${\displaystyle f_{2}-f_{3}}$${\displaystyle f_{3}-f_{2}}$${\displaystyle f_{3}}$${\displaystyle f_{2}}$${\displaystyle f_{3}-f_{2}}$

هنا تبدأ خوارزمية بوخبرجر لقواعد جروبنر بإضافة الحدود إلى G

${\displaystyle g_{3}=yg_{1}-xg_{2}=2x+y^{3}-y.}$

هذه الحدودية، التي أطلق عليها بوخبرغر اسم حدودية S ، هي الفرق بين الاختزالات ذات الخطوة الواحدة للمضاعف المشترك الأصغر للحدود الأحادية الرئيسية لـ و ، بواسطة و على التوالي: ${\displaystyle x^{2}y}$${\displaystyle g_{1}}$${\displaystyle g_{2}}$${\displaystyle g_{2}}$${\displaystyle g_{1}}$

${\displaystyle g_{3}=\left(x^{2}y-{\frac {x^{2}y}{lt(g_{2})}}g_{2}\right)-\left(x^{2}y-{\frac {x^{2}y}{lt(g_{1})}}g_{1}\right)={\frac {x^{2}y}{lt(g_{1})}}g_{1}-{\frac {x^{2}y}{lt(g_{2})}}g_{2}}$.

في هذا المثال، لدينا هذا لا يكمل خوارزمية بوخبرجر، حيث أن xy يعطي نتائج مختلفة، عند تقليله بواسطة أو${\displaystyle g_{3}=f_{3}-f_{2}.}$${\displaystyle g_{2}}$${\displaystyle g_{3}.}$

بالنظر إلى الترتيب أحادي الحد، فإن متعدد الحدود S أو الزوج الحرج من متعددي الحدود f و g هو متعدد الحدود

${\displaystyle S(f,g)=\operatorname {red} _{1}(\mathrm {lcm} ,g)-\operatorname {red} _{1}(\mathrm {lcm} ,f)}$؛

حيث يشير lcm إلى المضاعف المشترك الأصغر للحدود الأحادية الرئيسية لـ f و g . وباستخدام تعريف ، فإن هذا يترجم إلى: ${\displaystyle \operatorname {red} _{1}}$

${\displaystyle {\begin{aligned}S(f,g)&=\left(\mathrm {lcm} -{\frac {1}{\operatorname {lc} (g)}}\,{\frac {\mathrm {lcm} }{\operatorname {lm} (g)}}\,g\right)-\left(\mathrm {lcm} -{\frac {1}{\operatorname {lc} (f)}}\,{\frac {\mathrm {lcm} }{\operatorname {lm} (f)}}\,f\right)\\&={\frac {1}{\operatorname {lc} (f)}}\,{\frac {\mathrm {lcm} }{\operatorname {lm} (f)}}\,f-{\frac {1}{\operatorname {lc} (g)}}\,{\frac {\mathrm {lcm} }{\operatorname {lm} (g)}}\,g\\\end{aligned}}.}$

باستخدام الخاصية التي تربط المضاعف المشترك الأصغر والمضاعف القاسم المشترك الأكبر ، يمكن أيضًا كتابة كثيرة الحدود S على النحو التالي:

${\displaystyle S(f,g)={\frac {1}{\operatorname {lc} (f)}}\,{\frac {\operatorname {lm} (g)}{\mathrm {gcd} }}\,f-{\frac {1}{\operatorname {lc} (g)}}\,{\frac {\operatorname {lm} (f)}{\mathrm {gcd} }}\,g;}$

حيث يشير gcd إلى القاسم المشترك الأعظم للحدود الأحادية الرئيسية لـ f و g .

نظرًا لأن أحاديات الحدود التي يمكن اختزالها بواسطة كل من f و g هي مضاعفات المضاعف المشترك الأصغر بالضبط ، فيمكن التعامل مع جميع حالات عدم تفرد الاختزال من خلال النظر فقط إلى متعددات الحدود S. هذه حقيقة أساسية لنظرية أساس جروبنر وجميع الخوارزميات المستخدمة في حسابها.

لتجنب الكسور عند التعامل مع كثيرات الحدود ذات المعاملات الصحيحة، غالبًا ما يتم تعريف كثيرات الحدود S على أنها

${\displaystyle S(f,g)=\operatorname {lc} (g)\,{\frac {\operatorname {lm} (g)}{\mathrm {gcd} }}\,f-\operatorname {lc} (f)\,{\frac {\operatorname {lm} (f)}{\mathrm {gcd} }}\,g;}$

هذا لا يغير أي شيء في النظرية حيث أن الحدوديين مرتبطان .

ليكن حلقة متعددة الحدود فوق حقل F. في هذا القسم، نفترض أنه تم تحديد ترتيب أحادي الحدود المقبول. ${\displaystyle R=F[x_{1},\ldots ,x_{n}]}$

ليكن G مجموعة منتهية من كثيرات الحدود في R والتي تولد I مثالية . المجموعة G هي أساس Gröbner (بالنسبة لترتيب أحادي الحد)، أو بشكل أكثر دقة، أساس Gröbner لـ I إذا

1. إن المثل الأعلى الناتج عن أحاديات الحدود الرائدة في كثيرات الحدود في I يساوي المثل الأعلى الناتج عن أحاديات الحدود الرائدة في G ،

أو على نحو مكافئ،

هناك العديد من الخصائص المميزة، والتي يمكن اعتبار كل منها تعريفًا مكافئًا لقواعد جروبنر. من أجل الإيجاز، في القائمة التالية، تعني عبارة "كلمة واحدة/كلمة أخرى" أنه يمكن للمرء أن يأخذ "كلمة واحدة" أو "كلمة أخرى" لوجود توصيفين مختلفين لقواعد جروبنر. كل التأكيدات التالية هي توصيفات لقواعد جروبنر:

عند حساب التعريف أعلاه، فإن هذا يوفر 12 توصيفًا لقواعد جروبنر. إن حقيقة أن العديد من التوصيفات ممكنة تجعل قواعد جروبنر مفيدة للغاية. على سبيل المثال، يوفر الشرط 3 خوارزمية لاختبار العضوية المثالية ؛ يوفر الشرط 4 خوارزمية لاختبار ما إذا كانت مجموعة من الحدوديات هي أساس جروبنر وتشكل أساس خوارزمية بوخبرجر لحساب قواعد جروبنر؛ يسمح الشرطان 5 و6 بالحوسبة بطريقة مشابهة جدًا للحساب المعياري . ${\displaystyle R/I}$

لكل ترتيب أحادي الحد المقبول ولكل مجموعة محدودة من الحدود G ، يوجد أساس Gröbner يحتوي على G ويولد نفس المثال. علاوة على ذلك، يمكن حساب أساس Gröbner هذا باستخدام خوارزمية Buchberger .

تستخدم هذه الخوارزمية الشرط 4، وتستمر تقريبًا على النحو التالي: بالنسبة لأي عنصرين من G ، احسب التخفيض الكامل بواسطة G لمتعددة الحدود S الخاصة بهما ، وأضف النتيجة إلى G إذا لم تكن صفرًا؛ كرر هذه العملية مع تضمين العناصر الجديدة من G حتى تنتج جميع التخفيضات في النهاية صفرًا.

تنتهي الخوارزمية دائمًا بسبب مبرهنة ديكسون أو لأن حلقات كثيرة الحدود هي حلقات نوثرية ( نظرية أساس هيلبرت ). يضمن الشرط 4 أن تكون النتيجة أساس جروبنر، وتضمن تعريفات كثيرات الحدود S والاختزال عدم تغيير المثالية الناتجة.

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

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

تحتوي جميع قواعد جروبنر الدنيا لمثالية معينة (لترتيب أحادي الحد الثابت) على نفس عدد العناصر، ونفس أحاديات الحد الرائدة، وتحتوي قواعد جروبنر غير الدنيا على عناصر أكثر من القواعد الدنيا.

أساس جروبنر هويتم اختزالها إذا كانت كل حدودية فيها غير قابلة للاختزال بواسطة العناصر الأخرى للأساس، ولها1كمعامل رئيسي. لذا، فإن كل أساس جروبنر مخفض يكون ضئيلاً، ولكن لا يلزم اختزال أساس جروبنر الأدنى.

بالنظر إلى أساس جروبنر لمثالية I ، نحصل على أساس جروبنر مخفض لـ I عن طريق إزالة الحدوديات القابلة للاختزال الأولي بواسطة عناصر أخرى من الأساس (للحصول على أساس أدنى)؛ ثم استبدال كل عنصر من عناصر الأساس بنتيجة الاختزال الكامل بواسطة العناصر الأخرى من الأساس؛ وأخيرًا، عن طريق قسمة كل عنصر من عناصر الأساس على معامله الرئيسي.

جميع قواعد جروبنر المخفضة لمثال (لترتيب أحادي الحد الثابت) متساوية. ويترتب على ذلك أن مثاليين متساويان إذا وفقط إذا كان لهما نفس قاعدة جروبنر المخفضة.

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

عند العمل مع كثيرات الحدود على مجال الأعداد النسبية ، من المفيد العمل فقط مع كثيرات الحدود ذات المعاملات الصحيحة. في هذه الحالة، يمكن استبدال الشرط الخاص بالمعاملات الرئيسية في تعريف الأساس المخفض بالشرط الذي ينص على أن جميع عناصر الأساس هي كثيرات حدود بدائية ذات معاملات صحيحة، مع معاملات رئيسية موجبة. وهذا يعيد تفرد القواعد المخفضة. ${\displaystyle \mathbb {Q} }$

بالنسبة لكل ترتيب أحادي الحد، فإن المجموعة الفارغة من كثيرات الحدود هي أساس جروبنر الفريد للمثالية الصفرية .

لكل ترتيب أحادي الحد، فإن مجموعة من الحدوديات التي تحتوي على ثابت غير صفري هي أساس جروبنر للمثالية الوحدوية (حلقة الحدوديات بالكامل). وعلى العكس من ذلك، فإن كل أساس جروبنر للمثالية الوحدوية يحتوي على ثابت غير صفري. يتكون أساس جروبنر المخفض للوحدة من الحدودية المفردة 1 .

في حالة كثيرات الحدود في متغير واحد، يوجد ترتيب أحادي الحد مقبول فريد، وهو الترتيب حسب الدرجة. قواعد جروبنر الدنيا هي الحدود الفردية المكونة من كثير حدود واحد. قواعد جروبنر المخفضة هي كثيرات الحدود الأحادية .

ليكن حلقة من الحدوديات ثنائية المتغيرات ذات المعاملات النسبية، وخذ في الاعتبار المثال المثالي الناتج عن الحدوديات ${\displaystyle R=\mathbb {Q} [x,y]}$${\displaystyle I=\langle f,g\rangle }$

${\displaystyle f=x^{2}-y}$،

${\displaystyle g=x^{3}-x}$.

من خلال تقليل g بواسطة f ، نحصل على كثيرة حدود جديدة k بحيث${\displaystyle I=\langle f,k\rangle :}$

${\displaystyle k=g-xf=xy-x.}$

لا يمكن اختزال أي من f و k بواسطة الآخر، ولكن يمكن اختزال xk بواسطة f ، مما يعطي حدودًا أخرى في I :

${\displaystyle h=xk-(y-1)f=y^{2}-y.}$

تحت الترتيب المعجمي لدينا ${\displaystyle x>y}$

lt( ف ) = x ²

lt( k ) = xy

lt( ح ) = ص ²

نظرًا لأن f و k و h تنتمي إلى I ، ولا يمكن اختزال أي منها بواسطة الآخرين، فلا شيء من و هو أساس جروبنر لـ I.${\displaystyle \{f,k\},}$ ${\displaystyle \{f,h\},}$${\displaystyle \{h,k\}}$

من ناحية أخرى، { f , k , h } هو أساس جروبنر لـ I ، نظرًا لأن كثيرات الحدود S

${\displaystyle {\begin{aligned}yf-xk&=y(x^{2}-y)-x(xy-x)=f-h\\yk-xh&=y(xy-x)-x(y^{2}-y)=0\\y^{2}f-x^{2}h&=y(yf-xk)+x(yk-xh)\end{aligned}}}$

يمكن اختزالها إلى الصفر بواسطة f و k و h .

الطريقة التي تم استخدامها هنا لإيجاد h و k وإثبات أن { f و k و h } هي أساس Gröbner هي تطبيق مباشر لخوارزمية Buchberger . لذا، يمكن تطبيقها ميكانيكيًا على أي مثال مماثل، على الرغم من وجود العديد من الحدوديات ومتعددات الحدود S بشكل عام للنظر فيها، والحساب عمومًا كبير جدًا بحيث لا يمكن إجراؤه بدون جهاز كمبيوتر.

ما لم يتم ذكره صراحةً، فإن جميع النتائج التالية ^[3] صحيحة لأي ترتيب أحادي الحد (راجع هذه المقالة للتعرف على تعريفات الترتيبات المختلفة المذكورة أدناه).

من المفاهيم الخاطئة الشائعة أن الترتيب المعجمي ضروري لبعض هذه النتائج. على العكس من ذلك، فإن الترتيب المعجمي هو، في أغلب الأحيان، الأصعب في الحساب، واستخدامه يجعل العديد من العمليات الحسابية غير عملية والتي تكون سهلة نسبيًا مع الترتيب المعجمي العكسي المتدرج (grevlex)، أو عندما تكون هناك حاجة إلى الاستبعاد، ترتيب الاستبعاد (lexdeg) الذي يقتصر على grevlex في كل كتلة من المتغيرات.

تعتبر قواعد جروبنر المخفضة فريدة لأي مثال معين وأي ترتيب أحادي الحد. وبالتالي، فإن مثالين متساويين إذا وفقط إذا كان لهما نفس قاعدة جروبنر (المختزلة) (عادةً ما تنتج برامج قاعدة جروبنر المخفضة دائمًا قواعد جروبنر المخفضة).

يؤدي اختزال كثيرة الحدود f بواسطة أساس جروبنر G للمثال المثالي I إلى 0 إذا وفقط إذا كانت f في I. وهذا يسمح باختبار عضوية عنصر في المثال المثالي. وتتمثل طريقة أخرى في التحقق من أن أساس جروبنر لـ G ∪ { f } يساوي G.

لاختبار ما إذا كان المثال المثالي I الناتج عن f ₁ , ... , f _k موجودًا في المثال المثالي J ، يكفي اختبار أن كل f _I موجود في J. يمكن للمرء أيضًا اختبار مساواة قواعد جروبنر المخفضة لـ J و J ∪ { f ₁ , ... , f _k } .

يمكن النظر إلى أي مجموعة من الحدوديات كنظام من المعادلات الحدودية عن طريق مساواة الحدوديات بالصفر. تعتمد مجموعة حلول مثل هذا النظام فقط على المثالية الناتجة، وبالتالي لا تتغير عندما يتم استبدال مجموعة التوليد المعطاة بأساس جروبنر، لأي ترتيب، للمثالية الناتجة. يسمى هذا الحل، مع إحداثيات في حقل مغلق جبريًا يحتوي على معاملات الحدوديات، صفرًا للمثالية . في الحالة المعتادة للمعاملات النسبية ، يتم اختيار هذا الحقل المغلق جبريًا كحقل مركب .

لا يحتوي المثالي على أي صفر (نظام المعادلات غير متسق ) إذا وفقط إذا كان 1 ينتمي إلى المثالي (هذا هو Nullstellensatz لهيلبرت )، أو على نحو مكافئ، إذا كانت قاعدة جروبنر الخاصة به (لأي ترتيب أحادي الحد) تحتوي على 1، أو أيضًا، إذا كانت قاعدة جروبنر المخفضة المقابلة هي [1].

بالنظر إلى أساس جروبنر G للمثال المثالي I ، فإنه يحتوي فقط على عدد محدود من الأصفار، إذا وفقط إذا، لكل متغير x ، يحتوي G على كثير حدود مع أحادي حد رئيسي يكون قوة x (بدون ظهور أي متغير آخر في الحد الرئيسي). إذا كانت هذه هي الحالة، فإن عدد الأصفار، المحسوبة بالتعدد، يساوي عدد أحاديات الحدود التي ليست مضاعفات لأي أحادي حد رئيسي لـ G. يُسمى هذا العدد درجة المثالي.

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

إن بُعد المثالي I في حلقة متعددة الحدود R هو بُعد كرول للحلقة R / I ويساوي بُعد المجموعة الجبرية لأصفار I. وهو يساوي أيضًا عدد المستويات الفائقة في الوضع العام اللازمة لوجود تقاطع مع المجموعة الجبرية، وهو عدد محدود من النقاط. إن درجة المثالي والمجموعة الجبرية المرتبطة به هي عدد نقاط هذا التقاطع المحدود، مع العدّ بالتعدد. وعلى وجه الخصوص، فإن درجة السطح الفائق تساوي درجة متعددة الحدود الخاصة به.

تعتمد الدرجة والبعد فقط على مجموعة أحاديات الحدود الرائدة لقاعدة جروبنر المثالية لأي ترتيب أحادي الحدود.

البعد هو الحجم الأقصى لمجموعة فرعية S من المتغيرات بحيث لا يوجد حد أحادي رئيسي يعتمد فقط على المتغيرات في S. وبالتالي، إذا كان البعد المثالي 0، فعندئذٍ لكل متغير x يوجد حد أحادي رئيسي في أساس جروبنر يكون قوة x .

يمكن استنتاج البعد والدرجة من سلسلة هيلبرت للمثالية، وهي السلسلة ، حيث هو عدد أحاديات الحدود من الدرجة i التي ليست مضاعفات لأي أحادي حدود رئيسي في أساس جروبنر. يمكن جمع سلسلة هيلبرت في كسر نسبي ${\textstyle \sum _{i=0}^{\infty }d_{i}t^{i}}$${\displaystyle d_{i}}$

${\displaystyle \sum _{i=0}^{\infty }d_{i}t^{i}={\frac {P(t)}{(1-t)^{d}}},}$

حيث d هو البعد المثالي و هو متعدد الحدود بحيث هو درجة المثالي. ${\displaystyle P(t)}$${\displaystyle P(1)}$

على الرغم من أن البعد والدرجة لا يعتمدان على اختيار الترتيب الأحادي الحد، فإن سلسلة هيلبرت والحدود المتعددة تتغيران عندما نغير الترتيب الأحادي الحد. ${\displaystyle P(t)}$

توفر معظم أنظمة الجبر الحاسوبية التي توفر وظائف لحساب قواعد جروبنر وظائف أيضًا لحساب سلسلة هيلبرت، وبالتالي أيضًا البعد والدرجة.

يسمح حساب قواعد جروبنر لترتيب أحادي الحد بالحذف بنظرية الحذف الحسابية . ويستند هذا إلى النظرية التالية.

لنفترض وجود حلقة متعددة الحدود حيث يتم تقسيم المتغيرات إلى مجموعتين فرعيتين X و Y. دعنا نختار أيضًا ترتيب أحادي الحد للإزالة "يزيل" X ، أي ترتيب أحادي الحد حيث تتم مقارنة أحاديتي الحد من خلال مقارنة أجزاء X أولاً ، وفي حالة المساواة فقط، مع مراعاة أجزاء Y. وهذا يعني أن أحادي الحد الذي يحتوي على متغير X أكبر من كل أحادي الحد مستقل عن X. إذا كانت G أساس جروبنر للمثالية I لهذا الترتيب أحادي الحد، فإن أساس جروبنر لـ (غالبًا ما يُطلق على هذا المثالي مثالي الإزالة ). علاوة على ذلك، يتكون بالضبط من متعددات الحدود G التي تنتمي حدودها الرئيسية إلى K [ Y ] (هذا يجعل حساب ، حيث يجب التحقق من أحاديات الحد الرئيسية فقط). ${\displaystyle K[x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m}]=K[X,Y],}$${\displaystyle G\cap K[Y]}$${\displaystyle I\cap K[Y]}$${\displaystyle G\cap K[Y]}$${\displaystyle G\cap K[Y]}$

تتمتع خاصية الإزالة هذه بالعديد من التطبيقات، وسيتم وصف بعضها في الأقسام التالية.

تطبيق آخر في الهندسة الجبرية هو أن الإزالة تحقق العملية الهندسية لإسقاط مجموعة جبرية أفينية في فضاء فرعي من الفضاء المحيط: مع التدوين أعلاه، يتم تعريف ( إغلاق زاريسكي ) لإسقاط المجموعة الجبرية المحددة بواسطة المثالي I في الفضاء الفرعي Y بواسطة المثالي${\displaystyle I\cap K[Y].}$

الترتيب المعجمي بحيث يكون ترتيبًا استبعاديًا لكل قسم وبالتالي فإن أساس جروبنر لهذا الترتيب يحمل معلومات أكثر بكثير مما هو ضروري عادةً. قد يفسر هذا سبب كون قواعد جروبنر للترتيب المعجمي عادةً هي الأصعب في الحساب. ${\displaystyle x_{1}>\cdots >x_{n}}$${\displaystyle \{x_{1},\ldots ,x_{k}\},\{x_{k+1},\ldots ,x_{n}\}.}$

إذا كان I و J مثاليين تم إنشاؤهما على التوالي بواسطة { f ₁ ، ...، f _m } و{ g ₁ ، ...، g _k }، فإن حساب أساس جروبنر واحد ينتج أساس جروبنر لتقاطعهما I ∩ J. لهذا، يتم تقديم t غير محدد جديد ، ويتم استخدام ترتيب الإزالة بحيث تحتوي الكتلة الأولى على t فقط وتحتوي الكتلة الأخرى على جميع المتغيرات الأخرى (هذا يعني أن أحادي الحد الذي يحتوي على t أكبر من كل أحادي الحد الذي لا يحتوي على t ). مع ترتيب أحادي الحد هذا، يتكون أساس جروبنر لـ I ∩ J من الحدود التي لا تحتوي على t ، في أساس جروبنر للمثالي

${\displaystyle K=\langle tf_{1},\ldots ,tf_{m},(1-t)g_{1},\ldots ,(1-t)g_{k}\rangle .}$

بعبارة أخرى، يتم الحصول على I ∩ J عن طريق إزالة t في K. ويمكن إثبات ذلك من خلال ملاحظة أن K المثالية تتكون من كثيرات الحدود بحيث و . مثل هذه كثيرة الحدود تكون مستقلة عن t إذا وفقط إذا كانت a = b ، مما يعني أن${\displaystyle (a-b)t+b}$${\displaystyle a\in I}$${\displaystyle b\in J}$${\displaystyle b\in I\cap J.}$

المنحنى النسبي هو منحنى جبري يحتوي على مجموعة من المعادلات البارامترية من النموذج

${\displaystyle {\begin{aligned}x_{1}&={\frac {f_{1}(t)}{g_{1}(t)}}\\&\;\;\vdots \\x_{n}&={\frac {f_{n}(t)}{g_{n}(t)}},\end{aligned}}}$

حيث و هما كثيرات حدود أحادية المتغير لـ 1 ≤ i ≤ n . قد يفترض المرء (وسوف يفترض) أن و هما عددان أوليان (لا يوجد لهما عوامل مشتركة غير ثابتة). ${\displaystyle f_{i}(t)}$${\displaystyle g_{i}(t)}$${\displaystyle f_{i}(t)}$${\displaystyle g_{i}(t)}$

يتلخص التضمين في حساب المعادلات الضمنية لمثل هذا المنحنى. وفي حالة n = 2، أي بالنسبة للمنحنيات المستوية، يمكن حساب ذلك باستخدام المحصلة . والمعادلة الضمنية هي المحصلة التالية:

${\displaystyle {\text{Res}}_{t}(g_{1}x_{1}-f_{1},g_{2}x_{2}-f_{2}).}$

يسمح الإزالة باستخدام قواعد جروبنر بالاستدلال على أي قيمة لـ n ، وذلك ببساطة عن طريق إزالة t في المثالية. إذا كانت n = 2، فإن النتيجة هي نفسها كما هو الحال مع المحصلة، إذا كانت الخريطة حقنية لكل t تقريبًا . في الحالة الأخرى، تكون المحصلة قوة لنتيجة الإزالة. ${\displaystyle \langle g_{1}x_{1}-f_{1},\ldots ,g_{n}x_{n}-f_{n}\rangle .}$${\displaystyle t\mapsto (x_{1},x_{2})}$

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

ويتم ذلك عن طريق تشبع المعادلات بشروط الانحطاط، والذي يمكن أن يتم من خلال خاصية الإزالة لقواعد جروبنر.

تتكون عملية تحديد موضع الحلقة من إضافة معكوسات رسمية لبعض العناصر إليها. لا يتناول هذا القسم إلا حالة عنصر واحد، أو ما يعادله من عدد محدود من العناصر (إضافة معكوسات عدة عناصر يعادل إضافة معكوس حاصل ضربها). تحديد موضع الحلقة R بواسطة عنصر f هو الحلقة حيث t هو غير محدد جديد يمثل معكوس f . تحديد موضع المثالي I لـ R هو المثالي لـ عندما تكون R حلقة متعددة الحدود، فإن الحوسبة في ليست فعالة بسبب الحاجة إلى إدارة المقامات. لذلك، يتم استبدال التحديد عادةً بعملية التشبع . ${\displaystyle R_{f}=R[t]/(1-ft),}$${\displaystyle R_{f}I}$${\displaystyle I_{f}.}$${\displaystyle R_{f}}$

الالتشبع بالنسبة إلىfللمثاليةIفيRهو الصورة العكسية لـتحت الخريطة القياسية منRإلىوهو المثال المثاليالذي يتكون من جميع عناصرRالتي ينتمي حاصل ضربها بقوةfإلىI.${\displaystyle R_{f}I}$${\displaystyle R_{f}.}$${\displaystyle I:f^{\infty }=\{g\in R\mid (\exists k\in \mathbb {N} )f^{k}g\in I\}}$

إذا كان J هو المثالي الناتج عن I و1− ft في R [ t ]، فإنه يتبع ذلك أنه إذا كانت R حلقة متعددة الحدود، فإن حساب أساس جروبنر الذي يزيل t ينتج أساس جروبنر لتشبع المثالي بواسطة متعددة الحدود. ${\displaystyle I:f^{\infty }=J\cap R.}$

الخاصية المهمة للتشبع، والتي تضمن إزالة المكونات غير القابلة للاختزال من المجموعة الجبرية التي يحددها المثالي I والتي يكون فيها كثير الحدود f يساوي صفرًا، هي التالية: يتكون التحلل الأولي لـ من مكونات التحلل الأولي لـ I التي لا تحتوي على أي قوة لـ f . ${\displaystyle I:f^{\infty }}$

يمكن الحصول على أساس جروبنر للتشبع بواسطة f للمثالية متعددة الحدود الناتجة عن مجموعة محدودة من متعددات الحدود F ، عن طريق إزالة t في أي عن طريق الحفاظ على متعددات الحدود مستقلة عن t في أساس جروبنر لترتيب الإزالة بإزالة t . ${\displaystyle F\cup \{1-tf\},}$${\displaystyle F\cup \{1-tf\}}$

بدلاً من استخدام F ، يمكن للمرء أيضًا البدء من أساس جروبنر لـ F. تعتمد الطريقة الأكثر كفاءة على المشكلة. ومع ذلك، إذا لم يزيل التشبع أي مكون، أي إذا كان المثالي مساويًا للمثال المشبع، فإن حساب أساس جروبنر لـ F أولاً يكون أسرع عادةً. من ناحية أخرى، إذا أزال التشبع بعض المكونات، فقد يكون الحساب المباشر أسرع بشكل كبير.

إذا أراد المرء التشبع بالنسبة إلى العديد من الحدوديات أو بالنسبة إلى حدودية واحدة هي حاصل ضرب، فهناك ثلاث طرق للمتابعة والتي تعطي نفس النتيجة ولكن قد يكون لها أوقات حساب مختلفة للغاية (يعتمد الأمر على المشكلة الأكثر كفاءة). ${\displaystyle f_{1},\ldots ,f_{k}}$${\displaystyle f=f_{1}\cdots f_{k},}$

• التشبع بواسطة حساب أساس جروبنر واحد.${\displaystyle f=f_{1}\cdots f_{k}}$
• التشبع بواسطة ثم تشبع النتيجة بواسطة وهكذا.${\displaystyle f_{1},}$${\displaystyle f_{2},}$
• إضافة الحدود إلى F أو إلى أساس غروبنر الخاص بها وحذفها في حساب أساس غروبنر واحد.${\displaystyle 1-t_{1}f_{1},\ldots ,1-t_{k}f_{k},}$${\displaystyle t_{i}}$

تتضمن نظرية هيلبرت Nullstellensatz نسختين. الأولى تؤكد أن مجموعة من الحدوديات ليس لها أصفار مشتركة على إغلاق جبري لحقل المعاملات، إذا وفقط إذا كان 1 ينتمي إلى المثال المثالي الناتج. يمكن اختبار ذلك بسهولة باستخدام حساب أساس جروبنر، لأن 1 ينتمي إلى مثال مثالي إذا وفقط إذا كان 1 ينتمي إلى أساس جروبنر للمثال المثالي، لأي ترتيب أحادي الحد.

تؤكد النسخة الثانية أن مجموعة الأصفار المشتركة (في الإغلاق الجبري لحقل المعاملات) للمثالية موجودة في السطح الفائق لأصفار كثيرة الحدود f ، إذا وفقط إذا كانت قوة f تنتمي إلى المثال. يمكن اختبار ذلك عن طريق تشبع المثال بواسطة f ؛ في الواقع، تنتمي قوة f إلى المثال إذا وفقط إذا كان التشبع بواسطة f يوفر أساس جروبنر يحتوي على 1.

حسب التعريف، يمكن وصف مجموعة نسبية متآلفة ذات بعد k بمعادلات بارامترية من النموذج

${\displaystyle {\begin{aligned}x_{1}&={\frac {p_{1}}{p_{0}}}\\&\;\;\vdots \\x_{n}&={\frac {p_{n}}{p_{0}}},\end{aligned}}}$

أين يوجد n +1 حدود متعددة في المتغيرات k (معلمات تحديد المعلمات) وبالتالي فإن معلمات وإحداثيات نقاط التنوع هي أصفار للمثالية ${\displaystyle p_{0},\ldots ,p_{n}}$${\displaystyle t_{1},\ldots ,t_{k}.}$${\displaystyle t_{1},\ldots ,t_{k}}$${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle I=\left\langle p_{0}x_{1}-p_{1},\ldots ,p_{0}x_{n}-p_{n}\right\rangle .}$

يمكن للمرء أن يخمن أنه يكفي إزالة المعلمات للحصول على المعادلات الضمنية للتنوع، كما حدث في حالة المنحنيات. لسوء الحظ، هذا ليس هو الحال دائمًا. إذا كان لهما صفر مشترك (يُسمى أحيانًا نقطة الأساس )، فإن كل مكون غير قابل للاختزال للمجموعة الجبرية غير الفارغة المحددة بواسطة هو مكون غير قابل للاختزال للمجموعة الجبرية المحددة بواسطة I . ويترتب على ذلك أنه في هذه الحالة، يوفر الإزالة المباشرة لـ مجموعة فارغة من كثيرات الحدود. ${\displaystyle p_{i}}$${\displaystyle p_{i}}$${\displaystyle t_{i}}$

لذلك، إذا كانت k >1، فإننا نحتاج إلى حسابين أساسيين لـ Gröbner لتوضيح:

1. تشبع بواسطة للحصول على أساس Gröbner${\displaystyle I}$${\displaystyle p_{0}}$${\displaystyle G}$
2. احذف من للحصول على أساس جروبنر للمثالية (للمعادلات الضمنية) للتنوع.${\displaystyle t_{i}}$${\displaystyle G}$

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

1. حتى عندما تكون قاعدة جروبنر الناتجة صغيرة، فإن الحدود المتوسطة يمكن أن تكون ضخمة. وينتج عن ذلك أن معظم وقت الحوسبة قد يُقضى في إدارة الذاكرة . لذا، قد تكون خوارزميات إدارة الذاكرة المتخصصة جزءًا أساسيًا من التنفيذ الفعال.
2. قد تكون الأعداد الصحيحة التي تحدث أثناء عملية حسابية كبيرة بما يكفي لجعل خوارزميات الضرب السريعة والحسابات متعددة الوحدات مفيدة. لهذا السبب، تستخدم معظم التطبيقات المحسنة مكتبة GMPlibrary . كما يتم استخدام الحساب المعياري ونظرية الباقي الصيني ورفع هينسل في التطبيقات المحسنة
3. إن اختيار متعددات الحدود S المراد اختزالها ومتعددات الحدود المستخدمة في اختزالها مكرس للأساليب التجريبية . وكما هو الحال في العديد من المشكلات الحسابية، لا تستطيع الأساليب التجريبية اكتشاف معظم التبسيطات المخفية، وإذا تم تجنب الاختيارات التجريبية، فقد نحصل على تحسن كبير في كفاءة الخوارزمية.
4. في معظم الحالات يتم تقليص معظم حدود S التي يتم حسابها إلى الصفر؛ أي أن معظم وقت الحوسبة يُنفق لحساب الصفر.
5. الترتيب الأحادي الذي غالبًا ما يكون مطلوبًا للتطبيقات (المعجمية الصرفة) ليس الترتيب الذي يؤدي إلى أسهل عملية حسابية، وهو عادةً ترتيب degrevlex .

لحل 3. تم اقتراح العديد من التحسينات والمتغيرات والأساليب قبل تقديم خوارزميات F4 وF5 بواسطة جان شارل فوجير . نظرًا لأن هذه الخوارزميات مصممة لمعاملات الأعداد الصحيحة أو مع معاملات في الأعداد الصحيحة modulo a عدد أولي ، تظل خوارزمية Buchberger مفيدة للمعاملات الأكثر عمومية.

بشكل تقريبي، تحل خوارزمية F4 المشكلة 3. عن طريق استبدال العديد من عمليات الاختزال متعددة الحدود S باختزال صف لمصفوفة كبيرة واحدة يمكن استخدام طرق متقدمة للجبر الخطي لها . وهذا يحل المشكلة 4 جزئيًا، حيث تتوافق عمليات الاختزال إلى الصفر في خوارزمية Buchberger مع العلاقات بين صفوف المصفوفة المراد اختزالها، وتتوافق الصفوف الصفرية للمصفوفة المخفضة مع أساس فضاء المتجه لهذه العلاقات.

تعمل خوارزمية F5 على تحسين F4 من خلال تقديم معيار يسمح بتقليل حجم المصفوفات المراد تقليلها. هذا المعيار مثالي تقريبًا، حيث أن المصفوفات المراد تقليلها لها رتبة كاملة في حالات منتظمة بدرجة كافية (على وجه الخصوص، عندما تشكل حدود الإدخال تسلسلًا منتظمًا ). يعد ضبط F5 للاستخدام العام أمرًا صعبًا، حيث تعتمد أدائها على ترتيب حدود الإدخال والتوازن بين زيادة درجة حدود العمل وعدد حدود الإدخال التي يتم أخذها في الاعتبار. حتى الآن (2022)، لا يوجد تنفيذ موزع أكثر كفاءة بشكل ملحوظ من F4، ولكن تم استخدام F5 بنجاح على الأعداد الصحيحة المعيارية للعديد من التحديات التشفيرية ؛ على سبيل المثال، لكسر تحدي HFE .

تم حل المشكلة 5 من خلال اكتشاف خوارزميات تحويل الأساس التي تبدأ من أساس جروبنر لترتيب أحادي الحد لحساب أساس جروبنر لترتيب أحادي الحد آخر. خوارزمية FGLM هي خوارزمية تحويل أساس تعمل فقط في حالة البعد الصفري (حيث تحتوي الحدوديات على عدد محدود من الأصفار المشتركة المعقدة) ولها تعقيد حدودي في عدد الأصفار المشتركة. خوارزمية تحويل الأساس التي تعمل في الحالة العامة هي خوارزمية Gröbner walk . ^[4] في شكلها الأصلي، قد تكون FGLM هي الخطوة الحاسمة لحل أنظمة المعادلات متعددة الحدود لأن FGML لا تأخذ في الاعتبار ندرة المصفوفات المعنية . تم إصلاح هذا من خلال تقديم خوارزميات FGLM المتفرقة . ^[5]

تحتوي معظم أنظمة الجبر الحاسوبية العامة على تنفيذات لخوارزمية واحدة أو أكثر لقواعد جروبنر، وغالبًا ما تكون مضمنة أيضًا في وظائف أخرى، مثل حل أنظمة المعادلات متعددة الحدود أو لتبسيط الدوال المثلثية؛ هذه هي الحال، على سبيل المثال، في CoCoA و GAP و Macaulay 2 و Magma و Maple و Mathematica و SINGULAR و SageMath و SymPy . عندما تكون F4 متاحة، تكون عمومًا أكثر كفاءة من خوارزمية Buchberger. لا يتم توثيق تقنيات التنفيذ والمتغيرات الخوارزمية دائمًا، على الرغم من أنها قد يكون لها تأثير كبير على الكفاءة.

تتضمن مكتبة Msolve تنفيذات F4 و(sparse)-FGLM . ^[6] إلى جانب خوارزميات Gröbner، تحتوي مكتبة Msolve على خوارزميات سريعة لعزل الجذر الحقيقي ، وتجمع كل هذه الوظائف في خوارزمية للحلول الحقيقية لأنظمة المعادلات متعددة الحدود والتي تتفوق بشكل كبير على البرامج الأخرى لهذه المشكلة (Maple وMagma). ^[6] يتوفر Msolve على GitHub ، وهو متصل بـ Julia وMaple وSageMath؛ وهذا يعني أنه يمكن استخدام Msolve مباشرة من داخل بيئات البرامج هذه.

يتم تقييم تعقيد حسابات قاعدة جروبنر عادةً من حيث عدد n من المتغيرات والدرجة القصوى d لمتعددات الحدود المدخلة.

في أسوأ الأحوال، يكون المعامل الرئيسي للتعقيد هو الدرجة القصوى لعناصر أساس جروبنر المخفض الناتج. وبصورة أكثر دقة، إذا احتوى أساس جروبنر على عنصر بدرجة كبيرة D ، فقد يحتوي هذا العنصر على حدود غير صفرية يتطلب حسابها وقتًا من ناحية أخرى، إذا كانت جميع الحدوديات في أساس جروبنر المخفض مثالية متجانسة بدرجة D على الأكثر ، فيمكن حساب أساس جروبنر بالجبر الخطي على فضاء متجه الحدوديات من الدرجة الأقل من 2 D ، والتي لها بعد ^[1] لذا، فإن تعقيد هذا الحساب هو${\displaystyle \Omega (D^{n})}$${\displaystyle \Omega (D^{n})>D^{\Omega (n)}.}$${\displaystyle O(D^{n}).}$${\displaystyle O(D^{n})^{O(1)}=D^{O(n)}.}$

إن أسوأ تعقيد محتمل لحساب أساس جروبنر يكون أسيًا مضاعفًا في n . وبصورة أكثر دقة، يكون التعقيد محدودًا بالحدود العليا في باستخدام تدوين o الصغير ، وبالتالي يكون محدودًا بـ من ناحية أخرى، تم تقديم أمثلة لقواعد جروبنر المخفضة التي تحتوي على حدود من الدرجة أو تحتوي على عناصر. ونظرًا لأن كل خوارزمية لحساب أساس جروبنر يجب أن تكتب نتيجتها، فإن هذا يوفر حدًا أدنى للتعقيد. ${\textstyle d^{2^{n}}.}$${\textstyle d^{2^{n+o(n)}}.}$${\textstyle d^{2^{\Omega (n)}},}$${\textstyle d^{2^{\Omega (n)}}}$

أساس Gröbner هو EXPSPACE-complete . ^[7]

تم تعميم مفهوم وخوارزميات قواعد جروبنر على وحدات فرعية من وحدات حرة على حلقة متعددة الحدود. في الواقع، إذا كانت L وحدة حرة على حلقة R ، فيمكن اعتبار المجموع المباشر حلقة من خلال تحديد حاصل ضرب عنصرين من L ليكون 0. يمكن تحديد هذه الحلقة بـ ، حيث هو أساس L. يسمح هذا بتحديد وحدة فرعية من L تم إنشاؤها بواسطة مع مثالية تم إنشاؤها بواسطة وحاصل الضرب ، . إذا كانت R حلقة متعددة الحدود، فإن هذا يقلل من نظرية وخوارزميات قواعد جروبنر للوحدات إلى نظرية وخوارزميات قواعد جروبنر للمثاليات. ${\displaystyle R\oplus L}$${\displaystyle R[e_{1},\ldots ,e_{l}]/\left\langle \{e_{i}e_{j}|1\leq i\leq j\leq l\}\right\rangle }$${\displaystyle e_{1},\ldots ,e_{l}}$${\displaystyle g_{1},\ldots ,g_{k}}$${\displaystyle R[e_{1},\ldots ,e_{l}]}$${\displaystyle g_{1},\ldots ,g_{k}}$${\displaystyle e_{i}e_{j}}$${\displaystyle 1\leq i\leq j\leq l}$

تم تعميم مفهوم وخوارزميات قواعد جروبنر أيضًا على المثل العليا على حلقات مختلفة، تبديلية أم لا، مثل حلقات كثيرة الحدود على حلقة مثالية رئيسية أو جبر ويل .

تم تطبيق أساس جروبنر في نظرية أكواد تصحيح الأخطاء لفك التشفير الجبري. باستخدام حساب أساس جروبنر على أشكال مختلفة من معادلات تصحيح الأخطاء، تم تطوير طرق فك التشفير لتصحيح أخطاء الرموز الدورية، ^[8] وأكواد التنوع الأفيني، ^[9] والأكواد الجبرية الهندسية وحتى أكواد الكتل الخطية العامة. ^[10] لا يزال تطبيق أساس جروبنر في فك التشفير الجبري مجالًا بحثيًا لنظرية تشفير القناة.

• مبرهنة بيرجمان الماسية ، امتداد لقواعد جروبنر إلى حلقات غير تبديلية
• أساس أكثر خطورة
• قاعدة جانيت
• السلاسل المنتظمة ، طريقة بديلة لتمثيل المجموعات الجبرية

• آدامز، ويليام دبليو؛ لوستوناو، فيليب (1994). مقدمة لقواعد جروبنر . دراسات عليا في الرياضيات . المجلد 3. الجمعية الرياضية الأمريكية . رقم ISBN 0-8218-3804-0.
• لي، هويشي (2011). قواعد جروبنر في نظرية الحلقات . مجلة العلوم العالمية . رقم ISBN 978-981-4365-13-0.
• بيكر، توماس؛ ويسفينينج، فولكر (1998). قواعد جروبنر: نهج حسابي للجبر التبادلي . نصوص الدراسات العليا في الرياضيات. المجلد 141. سبرينغر. رقم ISBN 0-387-97971-9.
• بوخبرغر، برونو (1965). خوارزمية لإيجاد العناصر الأساسية لحلقة فئة البقايا لمثالية حدودية ذات بعد صفري (PDF) (دكتوراه). جامعة إنسبروك. — (2006). "أطروحة الدكتوراه لبرونو بوخبرجر 1965: خوارزمية لإيجاد العناصر الأساسية لحلقة فئة البقايا لمثالية حدودية ذات أبعاد صفرية". مجلة الحوسبة الرمزية . 41 (3-4). ترجمة أبرامسون، م.: 471-511. doi : 10.1016/j.jsc.2005.09.007 . [هذه هي أطروحة بوخبرغر التي اخترعت قواعد جروبنر.]
• بوخبرغر، برونو (1970). "معيار خوارزمي لحل نظام المعادلات الجبرية" (PDF) . المعادلات الرياضية . 4 : 374-383. doi :10.1007/BF01844169. S2CID  189834323. (هذا هو النشر الدوري لأطروحة بوخبرجر.) بورشبرجر، ب.؛ وينكلر، ف.، محرران. (26 فبراير 1998). "معيار خوارزمي لحل نظام من المعادلات الجبرية". قواعد وتطبيقات جروبنر . سلسلة محاضرات الجمعية الرياضية اللندنية. المجلد 251. مطبعة جامعة كامبريدج. ص 535-545. رقم ISBN 978-0-521-63298-0.
• بوخبرغر، برونو؛ كاورز، مانويل (2010). "قواعد جروبنر". سكولاربيديا . 5 (10): 7763. رمز Bibcode :2010SchpJ...5.7763B. doi : 10.4249/scholarpedia.7763 .
• فروبيرج، رالف (1997). مقدمة لقواعد غروبنر . وايلي. رقم ISBN 0-471-97442-0.
• ستورمفيلز، بيرند (نوفمبر 2005). "ما هو ... أساس جروبنر؟" (PDF) . إشعارات الجمعية الرياضية الأمريكية . 52 (10): 1199-1200، مقدمة موجزة{{cite journal}}: CS1 maint: postscript (link)
• شيرشوف، أناتولي آي. (1999). "بعض المشاكل الخوارزمية لجبر لاي" (ملف PDF) . نشرة ACM SIGSAM . 33 (2): 3-6. doi :10.1145/334714.334715. S2CID  37070503.(مترجم من مجلة سيبيرسك للرياضيات، المجلد 3 (1962)، ص 292-296).
• Aschenbrenner, Matthias ; Hillar, Christopher (2007). "Finite generation of symmetric ideals". Transactions of the American Mathematical Society . 359 (11): 5171–92. arXiv : math/0411514 . doi : 10.1090/S0002-9947-07-04116-5 . S2CID  5656701.(حول قواعد جروبنر ذات الأبعاد اللانهائية للحلقات متعددة الحدود في عدد لا نهائي من القيم غير المحددة).

• تنفيذ فوجير لخوارزميته F4
• "أساس جروبنر"، موسوعة الرياضيات ، EMS Press ، 2001 [1994]
• Buchberger, B. (2003). "Gröbner Bases: A Short Introduction for Systems Theorists" (PDF) . في Moreno-Diaz, R.؛ Buchberger, B.؛ Freire, J. (المحررون). نظرية الأنظمة بمساعدة الحاسوب — EUROCAST 2001: مجموعة مختارة من الأوراق البحثية من ورشة العمل الدولية الثامنة حول نظرية الأنظمة بمساعدة الحاسوب. Springer. ص 1-19. ISBN 978-3-540-45654-4.
• بوخبيرجر، ب. Zapletal، A. “ببليوغرافيا قواعد Gröbner”.
• صفحة مقارنة التوقيتات لبرنامج Gröbner Bases
• البروفيسور برونو بوخبرجر برونو بوخبرجر
• فايستين، إريك دبليو. “أساس غروبنر”. عالم الرياضيات .
• مقدمة عن أساس جروبنر على سكولاربيديا