قاعدة غروبنر

في الرياضيات ، وتحديدًا في الجبر الحاسوبي ، والهندسة الجبرية الحاسوبية ، والجبر التبادلي الحاسوبي ، تُعد قاعدة غروبنر نوعًا خاصًا من المجموعات المولدة لمثالي في حلقة متعددة الحدود $K[x_{1},\ldots ,x_{n}]$ فوق حقل $K$ تُتيح قاعدة غروبنر استنتاج العديد من الخصائص المهمة للمثالي والتنوع الجبري المرتبط به بسهولة، مثل البُعد وعدد الأصفار عندما يكون محدودًا. يُعد حساب قاعدة غروبنر أحد الأدوات العملية الرئيسية لحل أنظمة المعادلات متعددة الحدود وحساب صور التنوعات الجبرية تحت الإسقاطات أو الخرائط الكسرية .

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

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

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

أدوات

حلقة متعددة الحدود

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

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

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

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

ترتيب أحادي الحد

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

$M\leq N\Longleftrightarrow MP\leq NP$
$M\leq MP$ .

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

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

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

الترتيب المعجمي ، ويطلق عليه عادةً lex أو plex (للترتيب المعجمي البحت).
الترتيب المعجمي العكسي للدرجة الكلية ، والذي يُطلق عليه عادةً اسم degrevlex .
ترتيب الحذف ، lexdeg .

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

العمليات الأساسية

الحد الرئيسي، والمعامل، والحد الأحادي

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

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

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

عمليات متعددة الحدود

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

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

قابلية قسمة وحيدات الحد

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

يُقال إن $M$ يقسم $N$ ، أو أن $N$ من مضاعفات M ، $إذا$ $a_{i}\leq b_{i}$ لكل $i$ ؛ أي إذا كانت $A$ لا تزيد عن $B$ من حيث مكوناتها . في هذه الحالة، يكون ناتج القسمة ${\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}}}$ هو الطرح المكوني لمتجهات الأس لـ $N$ و $M.$

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

يمتلك المرء

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

تخفيض

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

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

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

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

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

\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$ ، فإن المرء لديه

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

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

عدم تفرد الاختزال

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

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

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

المصطلح الرئيسي $2x^{3}$ يمكن اختزال f $بواسطة$ $g_{1}$ وليس عن طريق $g_{2}.$ لذا تتكون خطوة الاختزال الأولى من الضرب $g_{1}$ بطرح $2x$ وإضافة النتيجة إلى $f$ $:$ $f\;\xrightarrow {\overset {}{-2xg_{1}}} \;f_{1}=f-2xg_{1}=-x^{2}y-2xy^{2}+2x+y^{3}+3y.$

المصطلح الرئيسي $-x^{2}y$ ل $f_{1}$ هو مضاعف للحدود الرئيسية لكليهما $g_{1}$ و $g_{2},$ إذن، أمام المرء خياران لخطوة الاختزال الثانية. إذا اختار $g_{2},$ نحصل على متعددة حدود يمكن اختزالها مرة أخرى بواسطة $g_{2}\colon$ $f\;\xrightarrow {\overset {}{-2xg_{1}}} \;f_{1}\;\xrightarrow {xg_{2}} \;-2xy^{2}+y^{3}+3y\;\xrightarrow {2yg_{2}} \;f_{2}=y^{3}-y.$ لا يمكن إجراء أي تخفيض إضافي، لذلك $f_{2}$ يمثل اختزالاً كاملاً لـ $f$ .

يحصل المرء على نتيجة مختلفة مع الخيار الآخر للخطوة الثانية: $f\;\xrightarrow {\overset {}{-2xg_{1}}} \;f_{1}\;\xrightarrow {yg_{1}} \;-2xy^{2}+2x+2y^{3}+2y\;\xrightarrow {2yg_{2}} \;f_{3}=2x+2y^{3}-2y.$ ومرة أخرى، النتيجة $f_{3}$ غير قابل للاختزال، على الرغم من أنه تم إجراء تخفيضات في الرصاص فقط.

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

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

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

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

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

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

.

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

متعدد الحدود S

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

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

؛

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

{\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 أيضًا على النحو التالي:

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$ هي مضاعفات المضاعف المشترك الأصغر $(lcm$ )، فإنه يمكن معالجة جميع حالات عدم تفرد الاختزال بالنظر فقط إلى كثيرات الحدود من النوع S. هذه حقيقة أساسية لنظرية أساس غروبنر وجميع الخوارزميات المستخدمة لحسابها.

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

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

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

تعريف

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

ليكن $G$ مجموعة منتهية من كثيرات الحدود في $R$ تولد مثاليًا $I.$ تُسمى المجموعة $G$ أساس غروبنر (بالنسبة لترتيب أحاديات الحدود)، أو بتعبير أدق، أساس غروبنر لـ $I$ إذا

المثالي الناتج عن الحدود الأحادية الرئيسية لكثيرات الحدود في $I$ يساوي المثالي الناتج عن الحدود الأحادية الرئيسية لـ $G$ ،

أو، على نحو مماثل،

الحد الرئيسي لكل متعدد حدود في $I$ هو مضاعف للحد الرئيسي لبعض متعددات الحدود في $G.$

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

تكون كثيرة الحدود $f$ في $I$ إذا وفقط إذا كان بعض/كل اختزال كامل للخطوة الأولى/اختزال $f$ بواسطة $G$ ينتج عنه كثيرة الحدود الصفرية؛
لكل متعدد حدود $S$ $من$ عناصر $G$ ، ينتج عن بعض/كل اختزال كامل للعنصر $s$ بواسطة $G$ الصفر؛
جميع عمليات الاختزال الكاملة لعنصر من $R$ تنتج نفس النتيجة؛
تشكل أحاديات الحدود غير القابلة للاختزال بواسطة $G$ أساسًا للفضاء المتجهي $F$ $R/I.$

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

وجود

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

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

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

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

قواعد جروبنر المخفضة

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

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

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

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

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

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

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

حالات خاصة

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

لكل ترتيب أحادي الحد، تُشكّل مجموعة كثيرات الحدود التي تحتوي على ثابت غير صفري أساس غروبنر للمثالي الواحد (حلقة كثيرات الحدود بأكملها). وبالعكس، يحتوي كل أساس غروبنر للمثالي الواحد على ثابت غير صفري. ويتكون أساس غروبنر المُختزل للمثالي الواحد من كثيرة الحدود المفردة $1$ .

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

مثال ومثال مضاد

{\displaystyle f} — أصفار $f$ تشكل القطع المكافئ الأحمر؛ أصفار $g$ تشكل الخطوط الرأسية الزرقاء الثلاثة. ويتكون تقاطعها من ثلاث نقاط.

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

f=x^{2}-y

،

g=x^{3}-x

.

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

k=g-xf=xy-x.

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

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

في ظل الترتيب المعجمي مع $x>y$ لدينا

\mathrm {lt} (f)=x^{2}

\mathrm {lt} (k)=xy

\mathrm {lt} (h)=y^{2}

بما أن $f و k$ و $h$ تنتمي إلى $I$ ، ولا يمكن اختزال أي منها بواسطة الآخرين، فلا أحد $\{f,k\},$ $\{f,h\},$ و $\{h,k\}$ هي أساس غروبنر لـ $I.$

من ناحية أخرى، تُعدّ ${f, k, h}$ أساس غروبنر لـ $I$ ، لأن كثيرات الحدود S

{\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}$ تشكل أساس غروبنر، هي تطبيق مباشر لخوارزمية بوخبيرغر . لذا، يمكن تطبيقها آليًا على أي مثال مشابه، مع العلم أنه، بشكل عام، توجد العديد من كثيرات الحدود وكثيرات حدود S التي يجب أخذها في الاعتبار، وعادةً ما تكون الحسابات معقدة للغاية بحيث لا يمكن إجراؤها بدون حاسوب.

خصائص وتطبيقات قواعد غروبنر

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

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

مساواة المُثُل

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

العضوية وإدماج المُثُل

يؤدي اختزال متعددة الحدود f باستخدام أساس غروبنر G للمثالي $I$ إلى صفر إذا وفقط إذا كانت f تنتمي إلى $I.$ وهذا يسمح باختبار انتماء عنصر ما إلى المثالي. وتتمثل طريقة أخرى في التحقق من أن أساس غروبنر لـ G $\cup {f}$ يساوي G.

لاختبار ما إذا كان المثالي $I$ المُوَلَّد بواسطة $f 1, ..., f k$ مُحتوى في المثالي $J$ ، يكفي اختبار أن كل $f I$ ينتمي إلى $J.$ ويمكن أيضًا اختبار تساوي قواعد غروبنر المُختزلة لـ $J$ و $J \cup {f 1, ..., f k}$ .

حلول نظام المعادلات الجبرية

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

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

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

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

الأبعاد والدرجات ومتسلسلات هيلبرت

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

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

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

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

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

حيث d هو بُعد المثالي و $P(t)$ هو كثير الحدود. العدد $P(1)$ هي درجة المجموعة الجبرية المحددة بواسطة المثالي، في حالة المثالي المتجانس أو ترتيب أحادي الحد متوافق مع الدرجة؛ أي لمقارنة أحاديي حد، تتم مقارنة درجاتهما الكلية أولاً.

لا يعتمد البعد على اختيار ترتيب أحادي الحد، على الرغم من أن متسلسلة هيلبرت ومتعددة الحدود $P(t)$ قد تتغير بتغيرات ترتيب أحادي الحد. ومع ذلك، بالنسبة للمثاليّات المتجانسة أو ترتيبات أحادي الحد المتوافقة مع الدرجة، فإن متسلسلة هيلبرت ومتعددة الحدود $P(t)$ لا تعتمد على اختيار ترتيب أحادي الحد. ^{[ 5 ]}

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

الاستبعاد

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

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

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

من التطبيقات الأخرى، في الهندسة الجبرية ، أن الحذف يحقق العملية الهندسية لإسقاط مجموعة جبرية أفينية على فضاء جزئي من الفضاء المحيط: باستخدام الترميز أعلاه، فإن ( إغلاق زاريسكي لـ) إسقاط المجموعة الجبرية المعرفة بواسطة المثالي I على الفضاء الجزئي Y يُعرَّف بواسطة المثالي $I\cap K[Y].$

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

أفكار متقاطعة

إذا كان $I$ و $J$ مثاليين مُولَّدين على التوالي بواسطة { f ₁ , ..., f _m } و { g ₁ , ..., g _k }، فإن حسابًا واحدًا لأساس غروبنر يُنتج أساس غروبنر لتقاطعهما $I \cap J.$ لهذا، يُدخل متغير غير مُحدد جديد t ، ويُستخدم ترتيب حذف بحيث تحتوي الكتلة الأولى على t فقط ، بينما تحتوي الكتلة الأخرى على جميع المتغيرات الأخرى (وهذا يعني أن أي حد أحادي يحتوي على t يكون أكبر من أي حد أحادي لا يحتوي على t ). مع هذا الترتيب للحدود الأحادية، يتكون أساس غروبنر لـ $I \cap J$ من كثيرات الحدود التي لا تحتوي على t ، أي أساس غروبنر للمثالي.

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

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

التعبير الضمني عن منحنى عقلاني

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

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

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

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

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

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

التشبع

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

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

تعريف التشبع

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

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

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

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

حساب التشبع

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

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

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

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

نولستيلينساتز الفعال

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

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

التضمين في بُعد أعلى

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

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

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

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

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

لذلك، إذا كانت قيمة k > 1، فإن حسابين أساسيين من Gröbner مطلوبان للتضمين:

مشبع $I$ بواسطة $p_{0}$ للحصول على أساس غروبنر $G$
تخلص من $t_{i}$ من $G$ للحصول على أساس جروبنر للمثالي (للمعادلات الضمنية) للتنوع.

الخوارزميات والتطبيقات

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

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

لحل المسألة رقم 3، تم اقتراح العديد من التحسينات والتعديلات والأساليب الاستدلالية قبل ظهور خوارزميتي F4 وF5 على يد جان-شارل فوجير . ولأن هاتين الخوارزميتين مصممتان لمعاملات صحيحة أو معاملات ضمن نطاق الأعداد الصحيحة بتردد عدد أولي ، فإن خوارزمية بوخبيرغر تظل مفيدة للمعاملات الأكثر عمومية.

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

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

تم حل المشكلة رقم 5 باكتشاف خوارزميات تحويل الأساس التي تبدأ من أساس غروبنر لترتيب أحادي الحد لحساب أساس غروبنر لترتيب أحادي الحد آخر. خوارزمية FGLM هي إحدى خوارزميات تحويل الأساس هذه، وهي تعمل فقط في الحالة الصفرية الأبعاد (حيث يكون لكثيرات الحدود عدد محدود من الأصفار المشتركة المركبة)، ولها تعقيد متعدد الحدود بالنسبة لعدد الأصفار المشتركة. أما خوارزمية تحويل الأساس التي تعمل في الحالة العامة فهي خوارزمية مسار غروبنر . ^{[ 6 ]} في شكلها الأصلي، قد تكون خوارزمية FGLM هي الخطوة الحاسمة لحل أنظمة المعادلات متعددة الحدود، لأن خوارزمية FGLM لا تأخذ في الحسبان تباعد المصفوفات المعنية . وقد تم تدارك هذا الأمر من خلال تقديم خوارزميات FGLM المتباعدة . ^{[ 7 ]}

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

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

تعقيد

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

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

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

أساس غروبنر هو EXPSPACE-كامل . ^{[ 9 ]}

التعميمات

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

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

مجالات التطبيق

رموز تصحيح الأخطاء

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

انظر أيضاً

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

مراجع

1 2 3 لازارد، دانيال (1983). "قواعد غروبنر، والحذف الغاوسي، وحل أنظمة المعادلات الجبرية". الجبر الحاسوبي . سلسلة محاضرات في علوم الحاسوب. المجلد 162. الصفحات 146-156 . doi : 10.1007/3-540-12868-9_99 . ISBN 978-3-540-12868-7.
↑ رينشوخ، بودو؛ رولوف، هارتموت؛ راسبوتين، جورجي ج.؛ أبرامسون، مايكل (يونيو 2003). "مساهمات في نظرية المُثُل البنّاءة متعددة الحدود XXIII: أعمال منسية لعالم الرياضيات من لينينغراد، ن. م. غيونتر، حول نظرية المُثُل متعددة الحدود" (ملف PDF) . نشرة ACM SIGSAM . 37 (2): 35-48 . doi : 10.1145/944567.944569 . S2CID 1819694 .
↑ كوكس، ديفيد أ .؛ ليتل، جون؛ أوشيا، دونال (1997). المُثُل، والأنواع، والخوارزميات: مقدمة في الهندسة الجبرية الحاسوبية والجبر التبادلي . سبرينغر. ISBN 0-387-94680-2.
↑ لازارد، دانيال (2021). "درجة المثالي متعدد الحدود ومتباينات بيزو" .
↑ إيني، فيفيانا؛ هيرتسوغ، يورغن (2012). قواعد غروبنر في الجبر التبادلي . دراسات عليا في الرياضيات. المجلد 130. بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية. ISBN 978-0-8218-7287-1.الاقتراح 4.29
^ كولارت، ستيفان؛ كالكبرينر، مايكل. مول دانيال (1997). "تحويل القواعد بمسيرة غروبنر" . مجلة الحساب الرمزي . 24 ( 3-4 ). إلسفير: 465-469 . دوى : 10.1006/jsco.1996.0145 .
↑ فاوغير، جان-شارل ؛ تشينكي، مو (2017). "خوارزميات FGLM المتفرقة" . مجلة الحوسبة الرمزية . 80. إلسيفير: 538-569 . arXiv : 1304.1238 . doi : 10.1016/j.jsc.2016.07.025 . S2CID 149627 .
1 2 بيرثوميو، جيريمي؛ إيدر، كريستيان؛ صفي الدين، مهاب (2021). Msolve: مكتبة لحل أنظمة المعادلات متعددة الحدود . المؤتمر الدولي السادس والأربعون للحساب الرمزي والجبري لعام 2021. سانت بطرسبرغ، روسيا. arXiv : 2104.03572 . doi : 10.1145/3452143.3465545 .
↑ ماير، إرنست دبليو. (سبتمبر 1997)، "بعض نتائج التعقيد للمثاليات متعددة الحدود"، مجلة التعقيد ، 13 (3): 303-325 ، doi : 10.1006/jcom.1997.0447
↑ تشين، إكس؛ ريد، آي إس؛ هيليسيث، تي؛ ترونغ، تي كي (1994). "استخدام قواعد غروبنر لفك تشفير الرموز الدورية الثنائية حتى الحد الأدنى الحقيقي للمسافة". معاملات IEEE في نظرية المعلومات . 40 (5): 1654-1661 . doi : 10.1109/18.333885 .
↑ فيتزجيرالد، ج.؛ لاكس، ر. ف. (1998). "فك تشفير رموز التنوع الأفيني باستخدام قواعد غروبنر". التصاميم، والرموز، والتشفير . 13 (2): 147-158 . doi : 10.1023/A:1008274212057 . S2CID 2515114 .
↑ بوليجين، س.؛ بيليكان، ر. (2009). "فك تشفير رموز تصحيح الأخطاء الخطية حتى نصف المسافة الدنيا باستخدام قواعد غروبنر". قواعد غروبنر، والترميز، وعلم التشفير . سبرينغر . ص 361-365 . ISBN 978-3-540-93805-7.

للمزيد من القراءة

آدامز، ويليام و.؛ لوستاوناو، فيليب (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. دوى : 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 . (مترجم من Sibirsk. Mat. Zh. Siberian Mathematics Journal 3 (1962), 292–296).
أشينبرينر، ماتياس ؛ هيلار، كريستوفر (2007). "التوليد المحدود للمثاليّات المتناظرة" . معاملات الجمعية الرياضية الأمريكية . 359 (11): 5171-92 . arXiv : math/0411514 . doi : 10.1090/S0002-9947-07-04116-5 . S2CID 5656701 . (على قواعد غروبنر اللانهائية الأبعاد لحلقات كثيرات الحدود في عدد لا نهائي من المتغيرات غير المحددة).

روابط خارجية

تطبيق فوغير الخاص لخوارزمية F4 الخاصة به
"أساس غروبنر" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
بوخبيرغر، ب. (2003). "قواعد غروبنر: مقدمة موجزة لنظريي النظم" (ملف PDF) . في: مورينو-دياز، ر.؛ بوخبيرغر، ب.؛ فراير، ج. (محررون). نظرية النظم بمساعدة الحاسوب - يوروكاست 2001: مجموعة مختارة من أوراق العمل من ورشة العمل الدولية الثامنة حول نظرية النظم بمساعدة الحاسوب . سبرينغر. الصفحات 1-19 . ISBN 978-3-540-45654-4.
بوخبيرجر، ب. Zapletal، A. “ببليوغرافيا قواعد Gröbner” .
صفحة التوقيتات المقارنة لبرنامج Gröbner Bases
الأستاذ برونو بوتشبيرغر
فايستين، إريك دبليو. “أساس جروبنر” . عالم الرياضيات .
مقدمة أساسية عن غروبنر على موقع سكولاربيديا

[laz-1] 1 2 3 لازارد، دانيال (1983). "قواعد غروبنر، والحذف الغاوسي، وحل أنظمة المعادلات الجبرية". الجبر الحاسوبي . سلسلة محاضرات في علوم الحاسوب. المجلد 162. الصفحات 146-156 . doi : 10.1007/3-540-12868-9_99 . ISBN 978-3-540-12868-7.

[2] رينشوخ، بودو؛ رولوف، هارتموت؛ راسبوتين، جورجي ج.؛ أبرامسون، مايكل (يونيو 2003). "مساهمات في نظرية المُثُل البنّاءة متعددة الحدود XXIII: أعمال منسية لعالم الرياضيات من لينينغراد، ن. م. غيونتر، حول نظرية المُثُل متعددة الحدود" (ملف PDF) . نشرة ACM SIGSAM . 37 (2): 35-48 . doi : 10.1145/944567.944569 . S2CID 1819694 .

[3] كوكس، ديفيد أ .؛ ليتل، جون؛ أوشيا، دونال (1997). المُثُل، والأنواع، والخوارزميات: مقدمة في الهندسة الجبرية الحاسوبية والجبر التبادلي . سبرينغر. ISBN 0-387-94680-2.

[4] لازارد، دانيال (2021). "درجة المثالي متعدد الحدود ومتباينات بيزو" .

[5] إيني، فيفيانا؛ هيرتسوغ، يورغن (2012). قواعد غروبنر في الجبر التبادلي . دراسات عليا في الرياضيات. المجلد 130. بروفيدنس، رود آيلاند: الجمعية الرياضية الأمريكية. ISBN 978-0-8218-7287-1.الاقتراح 4.29

[6] كولارت، ستيفان؛ كالكبرينر، مايكل. مول دانيال (1997). "تحويل القواعد بمسيرة غروبنر" . مجلة الحساب الرمزي . 24 ( 3-4 ). إلسفير: 465-469 . دوى : 10.1006/jsco.1996.0145 .

[7] فاوغير، جان-شارل ؛ تشينكي، مو (2017). "خوارزميات FGLM المتفرقة" . مجلة الحوسبة الرمزية . 80. إلسيفير: 538-569 . arXiv : 1304.1238 . doi : 10.1016/j.jsc.2016.07.025 . S2CID 149627 .

[msolve-8] 1 2 بيرثوميو، جيريمي؛ إيدر، كريستيان؛ صفي الدين، مهاب (2021). Msolve: مكتبة لحل أنظمة المعادلات متعددة الحدود . المؤتمر الدولي السادس والأربعون للحساب الرمزي والجبري لعام 2021. سانت بطرسبرغ، روسيا. arXiv : 2104.03572 . doi : 10.1145/3452143.3465545 .

[HLP-9] ماير، إرنست دبليو. (سبتمبر 1997)، "بعض نتائج التعقيد للمثاليات متعددة الحدود"، مجلة التعقيد ، 13 (3): 303-325 ، doi : 10.1006/jcom.1997.0447

[10] تشين، إكس؛ ريد، آي إس؛ هيليسيث، تي؛ ترونغ، تي كي (1994). "استخدام قواعد غروبنر لفك تشفير الرموز الدورية الثنائية حتى الحد الأدنى الحقيقي للمسافة". معاملات IEEE في نظرية المعلومات . 40 (5): 1654-1661 . doi : 10.1109/18.333885 .

[11] فيتزجيرالد، ج.؛ لاكس، ر. ف. (1998). "فك تشفير رموز التنوع الأفيني باستخدام قواعد غروبنر". التصاميم، والرموز، والتشفير . 13 (2): 147-158 . doi : 10.1023/A:1008274212057 . S2CID 2515114 .

[12] بوليجين، س.؛ بيليكان، ر. (2009). "فك تشفير رموز تصحيح الأخطاء الخطية حتى نصف المسافة الدنيا باستخدام قواعد غروبنر". قواعد غروبنر، والترميز، وعلم التشفير . سبرينغر . ص 361-365 . ISBN 978-3-540-93805-7.

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗