نطوّر طريقة تكرارية لحساب جذور المعادلات الحدودية التعسفية فوق حقل سلاسل Puiseux بما في ذلك تلك غير القابلة للفصل. تعمل الطريقة عبر تحويل المعادلة الحدودية وجذورها إلى شكل خاص ثم استخراج معادلة حدودية أحادية الحد جديدة تحتوي على معلومات حول جذورنا. نوفر أيضًا تنفيذًا عمليًا للخوارزمية بلغة Python.
لتكن \(\mathbb{N}\) مجموعة الأعداد الطبيعية بما في ذلك 0. وليكن \(K\) حقلًا و\(K((x^\frac{1}{n}))\) هو حقل سلاسل بويزو العاملة فوق \(K\). عناصر \(K((x^\frac{1}{n}))\) تكون على الشكل \(y = \sum_{k=k_0} ^\infty b_{k}x ^{\frac{k}{n}}, n \in \mathbb{Z}\). عندما يكون لـ\(y\) عدد محدود من الحدود، نسمّي \(d_x\) درجة \(y\). وليكن \(Q : K((x)) \mapsto K((x))\) معادلة حدودية فوق حقل سلاسل بويزو، \(Q(y) = a_{d_y} y^{d_y} + ... + a_1 y + a_0, d_y \in \mathbb{N^+}\)، حيث \(d_y\) هي درجة \(Q\). وليكن \(\alpha = \sum_{k=0} ^\infty b_{k}x ^{\frac{k}{n}}, n \in \mathbb{Z}\) جذرًا لـ\(Q\).
تكون المعادلة الحدودية ذات ضربية-س، عندما توجد \(s\) جذور \(\alpha_1,...,\alpha_s\) لـ\(Q\) بحيث تكون معاملات \(b_0\) جميعها صفرًا.
تكون المعادلة الحدودية \(Q\) ذات ضربية-س-زائدة، عندما توجد جذور \(s^+\) \(\alpha_1,...,\alpha_{s^+}\) لـ\(Q\)، \(s^+ \in \{1,...,s\}, s\) هي الضربية-س لـ\(Q\) بحيث تكون معاملات \(b_0\) جميعها صفرًا والحد \(b_1\) له نفس التقييم لجميع \(\alpha_j, j \in \{1,...,s^+\}\).
المعادلة الحدودية \(Q(y) = (y-(1+x+x^2))(y-x^{0.5})(y-x^{0.6})(y-x^{0.5} + x^2)\) لها ضربية-س 3 وضربية-س-زائدة 2.
ليكن \(v: K((x)) \mapsto \mathbb{Q}\) خريطة التقييم المعرفة بـ\(v(y) = k_0\).
لنتخيل للحظة أن لدينا خوارزمية لحساب أصغر جذر لمعادلة حدودية \(Q\)، على سبيل المثال، \(Q(y) = (y - (1+x+x^2)) (y-(2+x+x^2))\) فوق حقل سلاسل Puiseux. في هذه الحالة، الجذر الأصغر هو \((1+x+x^2)\). الأصغر هنا يعني الجذر الذي يحتوي على معامل رئيسي بأصغر تقييم، في هذه الحالة. لكن يمكننا فقط حساب الحد الأعلى تقييمًا، أي \(1\). كيف يمكننا المضي قدمًا لحساب الحدود التالية للجذر؟ قد تبدو الإجابة واضحة: من خلال تحويل جذور معادلة الحدود \(Q\). الآن لدينا معادلة الحدود المحوّلة \[Q_{shift} = (y - (x+x^2)) (y-(1x+x^2))\] ويمكننا بسهولة حساب الحد التالي بخوارزميتنا: \(x\). في هذه الورقة سنستكشف هذه الفكرة بشكل رئيسي: 1. كيفية تطوير خوارزمية لحساب أصغر جذر تحت ظروف معينة 2. كيفية تحويل معادلة الحدود لدينا لتلبية هذا الشرط. يمكن أيضًا رؤية نظرة عامة جيدة لهذه العملية في القسم [algorithm]. توجد طرق مماثلة لحل هذه المشكلة عبر سلاسل Puiseux وسلاسل القوى، على سبيل المثال في صيغة قاعدة Hensel ونُسخها المطورة (neiger) أو في طريقة Newton Puiseux (brieskorn2012plane).
في هذا القسم، نعرض النتيجة الرئيسية. تعمل هذه الطريقة عبر تقليص معادلتنا الحدودية إلى معادلة حدودية أصغر، تحت شروط معينة. في القسم 4 سنرى كيف يمكننا تحويل أي معادلة حدودية إلى واحدة تحقق هذه الشروط بالضبط. نحسب جذر معامل معادلتنا الحدودية معاملًا تلو الآخر كما في خوارزمية نيوتن-بويزو الأصلية.
لتكن \(Q : K((x)) \mapsto K((x))\) معادلة حدودية فوق حقل سلاسل بويزو، \(Q(y) = a_{d_y} y^{d_y} + ... + a_1 y + a_0, d_y \in \mathbb{N^+}\). ولتكن \(\alpha_1,...,\alpha_n\) جذور معادلتنا الحدودية ولتكن \(v(a_i) \geq 0, i \in \{1,...,d_y\}\). الآن نفترض \(v(\alpha_j) \geq e > 0 \ , j \in \{1,...,s\}\)، \(s \in \{1,...,d_y-1\} , e \in \mathbb{Q}\)، مع \(v(\alpha_j) = e\) لـ\(j \in \{1,...,s^+\}, s^+ >1\). \(s\) هي بالضبط ضربية-س لـ\(\alpha_j\)، \(s^+\) هي ضربية-س-زائدة. \(e\) هو أصغر تقييم لجميع \(\alpha_j\). يمكننا أيضًا تمثيل هذه الجذور كـ\(\alpha_j = c_{1_j} x^{e} + c_{2_j} x^{e + \gamma_{2_j}} + c_{3_j} x^{e + \gamma_{2_j} + \gamma_{3_j}} ..., \gamma_j \in \mathbb{Q}, j \in \{1,...,s^+\}.\) الآن الهدف من هذه النظرية هو حساب \(c_{1_j}, j \in \{1,...,s^+\} \). نفترض أيضًا \(v(\alpha_j) = 0, \ \forall j \in \{s+1,...,d_y\}.\) ننظر الآن إلى معاملات \(Q\). نتذكر \[a_i = b_{i_0}x^{\delta_1} + b_{i_1}x^{\delta 1 + \delta_2} + ..., \ \delta_k \in \mathbb{Q}, k \in \mathbb{N^+} .\] لنكن الآن \(Q_R(x) = b_{s_{min}}x^{d_y} + ... + b_{1_{min}} x\) حيث \(b_{i_{min}} := \min_{l \in \{1,...,d_x\}} \{b_{i_l} \neq 0 \}, i \in \{1,...,s\}\). إذًا جذور \(Q_R\) هي بالضبط \(c_{1_j}\). إذًا \(Q_R\) من الدرجة \(s\)، وجذور \(c^+\) هي بالضبط \(c_{1_j} j \{1,...,s^+\}\) التي تنتمي إلى الجذور ذات التقييم الأدنى. الجذور الأخرى \(s-s^+\) هي صفر.
نعلم أن \(c_{1_j}, j \in \{1,...,s^+\}\) كونها المعامل الصحيح لجذر \(Q\) يعادل \(Q(c_{1_j} x^{e}) \mod x^{e'} \equiv 0\)، أي أن \(c_{1_j}x\) هو جذر لـ\(Q(y) \mod x^{e'}\). \(e' \in \mathbb{Q}\) هو في هذه الحالة أي رقم أكبر من \(s \cdot e\) وأصغر من أي حد من \(Q\)، الذي له تقييم أكبر من \(e\). يمكن أيضًا رؤية ذلك من خلال النظر إلى المعادلة الحدودية في تحليلها العاملي. نُظهر أن \(Q(\beta x^e) = Q_R(\beta x^e) \mod x^{e'}\): \[\begin{aligned} Q(\beta x^e) &\equiv a_{d_y} (\beta x^e)^{d_y} + ... + a_1 \beta x^e + a_0 \mod x^{e'} \\ &\equiv a_{d_y} ^* (\beta x^e)^{d_y} + ... + a_1^* (\beta x^e) + a_0^* + \left( b_{d_{y_{min}}}(\beta x^e) ^{d_y} + ... + b_{1_{min}}(\beta x^e) + b_{0_{min}} \right) \mod x^{e'} \\ &\equiv b_{d_{y_{min}}}(\beta x^e)^{d_y} + ... + b_{1_{min}}(\beta x^e) + b_{0_{min}} \mod x^{e'} \\ &\equiv b_{s_{min}}(\beta x^e)^s + ... + b_{1_{min}}(\beta x^e) + b_{0_{min}} \mod x^{e'} \\\end{aligned}\] حيث \(a_i^{*} = a_i - b_{i_{min}}, i \in \{1,...,d_y\}\).
خلاصة القول: عندما نحل \(Q_R\) نحصل على الحلول \(c_{1_j}x^e\). سنشرح كيفية حل \(Q_R\) بمساعدة التحويلات في القسم 4. لتطبيق هذه النظرية، نحتاج إلى تحقيق الشرط \(v(\alpha_j) \geq e > 0, j \in \{1,...,s\}\) مع \(v(\alpha_j) = e\) لواحد على الأقل \(j \in \{1,...,s\}\) و \(v(\alpha_k) = 0, \ \forall k \in \{s+1,...,d_y\}\) (1). نحتاج أيضًا إلى الحصول على \(e\) (2) و\(s\) (3). بمجرد تطبيق هذه الخطوة، يمكننا استخراج (1), (2)، و(3)، للخطوة التالية، من مجموعة جذور \(Q_R\). يمكننا المضي قدمًا بنفس الطريقة لمتابعة المعاملات التالية \(c_{2_k},...,c_{d_{y_l}}\)، بعد تحويل معادلتنا الحدودية لتلبية افتراضنا مرة أخرى. \(k\) و\(l\) هما الفهارس المقابلة.
في هذا القسم، سنثبت كيفية تحويل معادلة حدودية \(Q: K((x^\frac{1}{n})) \mapsto K((x^\frac{1}{n}))\) إلى واحدة تحقق الشرط (1)، إذا لم تكن كذلك بالفعل، وكيفية استخراج (2) و(3). نبدأ أولًا بنظرية معروفة:
لنفترض أن لدينا معادلة حدودية \(P\) فوق \(K\)، مع \(\alpha_1,...,\alpha_n, n \in N^+\) كجذور لها. إذًا لأي ثابت \(c \in K\) تكون المعادلة الحدودية ذات الجذور \(\alpha_1 + c,...,\alpha_n +c \) على الشكل \[Q(y)=P(y-c)=a_{n}(y-c)^{n}+a_{n-1}(y-c)^{{n-1}}+\cdots +a_{{0}}.\] والمعادلة الحدودية ذات الجذور \(c\alpha_1,...,c\alpha_n\) تكون على الشكل \[Q(y) = a_{n}y^{n}+a_{n-1}cy^{{n-1}}+\cdots +a_{{0}}c^{n}.\]
نبدأ الآن بـ(1). يمكننا التحقق من (1) بحساب الأجزاء الثابتة من الجذور عبر \(Q_{|x=0}\). إذا كان لدينا على الأقل جذر واحد من \(Q_{|x=0}\) غير مساوٍ للصفر وآخر مساوٍ للصفر فإننا نحقق الشروط. التحقق من \(Q_{|x=0}\)، بشكل رئيسي للحصول على الجزء الثابت من جذر \(Q\)، هو تقنية شائعة ويمكن رؤيتها عند النظر إلى \(Q\) في تمثيل العوامل الخطية. في الحالة 1 أولًا، نريد التأكد من أن \(v(\alpha_j) = 0\) صحيح لواحد على الأقل \(i \in \{1,...,d_y\}\). ماذا لو كانت جميع جذور \(Q_{|x=0}\) صفرًا لجميع \(j \in \{1,...,d_y\}\)؟ في هذه الحالة، نحول معادلتنا الحدودية عبر الضرب كما في النظرية 1. لهذا الغرض، نحتاج فعليًا إلى معرفة \(e\)، تقييم \(\alpha_j\)، والذي يمكننا الحصول عليه عبر مضلع نيوتن لمعادلتنا الحدودية. وبالتالي نضرب جذورنا بـ\(a^e\). نعود الآن إلى معادلتنا الحدودية المحوّلة، التي تحقق \(v(\alpha_j) = 0\) صحيح لواحد على الأقل \(j \in \{1,...,d_y\}\). في الحالة 2 الآن نتحقق إذا كان \(v(\alpha_j) > 0\) صحيح لواحد على الأقل \(j \in \{1,...,d_y\}\). لنفترض أن لدينا \(v(\alpha_j) = 0, \forall i \in \{1,...,n\}\)، إذًا يمكننا الحصول على الحد الثابت لـ\(\alpha_j\) بتقييم \(Q_{|x=0}\) وأخذ جذوره، كما ناقشنا بالفعل. بمجرد حصولنا على جميع الأجزاء الثابتة \(c_j\) لـ\(\alpha_j\)، سنستخدمها لتحويل معادلتنا الحدودية بمساعدة النظرية 1. إذا انتهينا بمعادلة حدودية تحقق \(v(\alpha_j) > 0\) لجميع \(j \in \{1,...,d_y\}\)، نعود إلى الحالة 1. إذا لم يكن كذلك، فلدينا واحدة تحقق الشرط المطلوب. الآن يمكننا أخيرًا التحدث عن الحالة عندما يتم تحقيق (1): نحسب جذور \(Q_{|x=0}\) أو نأخذ الجذور المحسوبة بالفعل، أحدها الآن غير مساوٍ للصفر. دعونا نسميه \(\alpha_k, k \in \{1,...,d_y\}.\) في هذه الخطوة نحصل بالفعل على \(s\) -multiplicity لذلك الجذر، وهو بالضبط الضرب الذي نحتاجه لخطوتنا التالية. بعد هذا الحساب، نحول مرة أخرى، وهكذا، نصل إلى جذرنا تدريجيًا.
في هذا القسم، سنستكشف الخوارزمية بالتفصيل. يمكن العثور على تنفيذ لها في (ragon). أولًا، نقوم بتعريف فئة المعلومات التي تحفظ كل المعلومات المهمة لدينا. عند تهيئة الخوارزمية، نقوم بإنشاء كائن من فئة المعلومات، مع دقة محددة \(d\)، قائمة فارغة root_dict_list، وx_lift بقيمة \(0\). يمكن دائمًا حساب الألفا الحالية من خلال دمج أجزاء جذرنا من root_dict_list. ثم نعطي كائن المعلومات إلى الطريقة calculate_smallest_root، طريقتنا الرئيسية: كما نرى في [alg:calculate]، نتبع العملية الموصوفة في الأقسام 3 و4. نبدأ أولًا بحساب الانتقال الأولي، لجلب معادلتنا الحدودية إلى الشكل \(v(\alpha_j) \geq e > 0, j \in \{1,...,s\}\) مع \(v(\alpha_j) = e\) لواحد على الأقل \(j \in \{1,...,s\}\) و \(v(\alpha_k) = 0, \ \forall k \in \{s+1,...,d_y\}\)، كما هو موصوف في (1). في هذه العملية، نحصل بالفعل على الجزء الأول من جذرنا الأول ألفا. هذا يجلب لنا أيضًا \(s-\) الضرب من الجزء التالي من الجذر. في الحلقة التكرارية، التي تبدأ في السطر 4، نبدأ بتحويل معادلتنا الحدودية أفقيًا، بحيث نحصل على الشكل (1) مرة أخرى. تحويل المعادلة الحدودية أفقيًا يعني إضافة ثابت إلى جذرها. طريقة الانتقال الأولي تحسب جذور \(p_{|x=0}\) في السطر 1 مع get_sub_x_root. ثم نقوم بتحويل معادلتنا الحدودية عموديًا إذا كانت جميع الجذور، في هذه الحالة الموصوفة بواسطة shift_number، غير مساوية للصفر. التحويل العمودي يعني ضرب الجذور بثابت. الخوارزمية [alg:calculate_q] هي نفسها [alg:calculate_i] ولكنها لا تعيد أي شيء. الخوارزمية [alg:golden] تصف بالضبط عملية استخراج \(p_R\) من معادلة حدودية \(p\)، تمامًا كما استخرجنا \(Q_R\) من \(Q\) في النظرية 1. هنا من الممكن أيضًا التحقق مما إذا كانت معادلة الحدود \(p_R\)، التي تسمى new_poly في الكود والشيفرة الزائفة، لها شكل بسيط جدًا مثل عندما تتكون فقط من جذر واحد بضرب \(s\). هذا يعني أن ضربها \(s\) وضربها \(s^+\) هما نفس الشيء. ثم نبدأ نفس العملية كما في طريقة الانتقال الأولي لحساب جذور \(p_R\) أي new_poly.