Знаходження коренів систем рівнянь алгебри за допомогою базису Гребнера

Юрій Мазуров 2 роки тому Переглядів:

1 Знаходження коренів систем рівнянь алгебри за допомогою базису Гребнера А.В. Шокуров, ІСП РАН Анотація. Описано та обґрунтовано алгоритм знаходження рішення системи алгебраїчних рівнянь над полем k для ідеалів нульової розмірності, якщо заданий базис Гребнера ідеалу цієї системи для лексикографічного порядку на термах від її змінних. Отримане рішення лежить в замиканні алгебри основного поля. Наведено приклад системи рівнянь алгебри, що має єдине рішення в основному полі, а загальна кількість рішень експоненційно щодо опису цієї системи. Ключові слова. Базис Гребнера, ідеал, 1. Вступ Нехай до поля, а K його алгебраїчне замикання. Нагадаємо, що алгебраїчне замикання кільця раціональних функцій над полем від нескінченного числа незалежних змінних називається універсальним розширенням поля K. Позначатимемо його Ω. Ідеал, породжений кінцевою множиною. позначимо через (F). Згідно з теоремою Гільберта про базис, для будь-якого ідеалу існує кінцева безліч багаточленів, що породжує цей ідеал. Розмаїттям ідеалу (див. [1]), в К п будемо називати безліч виконується рівність 0. Елемент Ω називається загальним коренем простого ідеалу I, якщо виконані умови: 0. Завдання 1. Задано кінцеву множину F елементів у кільці багаточленів над полем і базис Гребнера G ідеалу (F). Визначити, що виконується: або, і звичайно, або й нескінченно. Завдання 2. Задано кінцеве безліч елементів F в кільці багаточленів над полем і базис Гребнера G ідеалу (F). Визначити, що виконується: 0 або 0. Нагадаємо, визначення лексикографічного порядку на безлічі термів від змінних. Оскільки є взаємнооднозначна відповідність безлічі термів від змінних, і елементами прямоготвори п екземплярів безлічі невід'ємних чисел, достатньо визначити порядок. Для, будемо вважати, що, якщо і при деякому одному при будь-якому. Зокрема,. Завдання 3. Задано кінцеве безліч елементів F в кільці багаточленів. для якого 0 і базис Гребнера G ідеалу (F) щодо лексикографічного порядку. Знайти (побудувати) безліч V((F)). Наводяться алгоритми вирішення поставлених завдань та доведено їхню коректність. 2. Ідеали нульової розмірності Лемма 1. Різноманітність V(I) рішень ідеалу, звичайно тоді й тільки тоді, коли, / кінцевомірне над k векторний простір. Доведення. Необхідність. Якщо рішень немає, то згідно з теоремою Гільберта про нулі ідеал I містить одиницю і, тому, збігається з кільцем багаточленів. Отже. /

2 Нехай тепер безліч V(I) не порожня, звичайно і. при 1. всі його елементи. Оскільки, належать замиканню алгебри поля k, то для кожного такого, існує многочлен, з коренем,. Тоді багаточлени. 1, звертаються в нуль на всіх рішеннях ідеалу, і, отже, за теоремою Гільберта про нулі існують такі, що. Тож. /1, де deg. Достатність. Нехай тепер, / кінцева. Якщо це розмірність нульова, то,, отже, безліч рішень порожньо, тобто. звичайно. Розглянемо випадок коли розмірність, / кінцева, але не дорівнює нулю. Розглянемо базис Гребнера ідеалу I для лексикографічного порядку на багатьох багаточленів. Відповідно до визначення базису Гребнера, кожен многочлен, редукується до єдиного нередукованому многочлену, тобто. всі терми отриманого многочлена не містять терми, що поділяються на старші терми багаточленів з базису Гребнера ідеалу I. Розглянемо багаточлени виду. За визначенням лексикографічного порядку, будь-який терм, куди входить хоча одна зі змінних. старша за будь-якоготерма виду. Тому існує багаточлен, що належить базису Гребнера ідеалу I (інакше розмірність векторного простору, / над полем до була б нескінченною), а отже, і ідеалу I. Аналогічно для всіх інших змінних існують. Тоді рішення ідеалу I лежать у творі всіх рішень 0, тобто. у кінцевій множині. Лемма 2. Розмірність ідеалу, що дорівнює нулю тоді і тільки тоді, коли різноманіття V(I) звичайно і непусто. Доведення. Нехай, неприведене уявлення ідеалу I примарними ідеалами і, асоційовані з цим уявленням прості ідеали (відповідно до теореми Ласкера, див [1]). Розмірність ідеалу I, за визначенням, дорівнює максимальній розмірності простих ідеалів. 197 Припустимо, що 0. Тоді для всіх 1, виконано 0. Безпосередньо з визначень випливає, що і, отже, множини кінцеві. Тому і безліч рішень звісно. Нехай тепер множина V(I) звичайно. Тоді й усі кінцеві. Досить перевірити, що з простого ідеалу р розмірності більшої нуля безліч V(p) нескінченно. Для цього, згідно з лемою 1, достатньо переконатися, що величина / нескінченна. Нехай, загальний корінь ідеалу нар. Тоді визначено вкладення 198. Ω. Оскільки dim p > 0, компоненти загального кореня цього ідеалу містять трансцендентні елементи. Без обмеження спільності вважатимуться, що трансцендентен. Тоді елементи. лінійно незалежні над k. Отже. нескінченна, а оскільки, в силу визначення загального кореня, простого ідеалу р, виконується рівність. /, то й величина, / нескінченна. Лемма 3. Нехай G базис Гребнера ідеалу I. Відображення. /, задане формулою, де неприведена редукція, визначено коректно, однозначно взаємно і є k-гомоморфізмом векторних просторів. Доведення. Формула задає гомоморфізм k-векторнихпросторів. ядром якого є ідеал I. Отже, визначено коректно та є k-мономорфізмом. Наслідок 1. Нехай G базис Гребнера ідеалу I. Розмірність ідеалу I дорівнює нулю тоді і тільки тоді, коли безліч неприведених щодо базису Гребнера G термів звичайно. Теорема 1. Нехай G базис Гребнера власного ідеалу кільця многочленів. Цей ідеал має розмірність 0 тоді і тільки тоді, коли для будь-якого допустимого порядку при кожному 1 існує багаточлен зі старшим термом де деяке ціле негативне число. Доведення. Якщо деякого i немає елемента базису Гребнера ідеалу I зі старшим термом, то терми неприводимы.

3 Отже, безліч термів, що не наводяться, нескінченно, і, тому, згідно з наслідком 1 розмірність ідеалу I не дорівнює нулю. Нехай базис Гребнера ідеалу I містить багаточлени, старшими термами яких є. І тут необхідною умовою неприводимости терма t є виконання співвідношень всім i=1,,n. Тому, потужність безлічі неприводимых термів не перевищує величину, і, отже, кінцева. А тоді, згідно з слідством 1, розмірність ідеалу I дорівнює нулю. 3. Розв'язання систем рівнянь Розв'язання задачі 1. Відповідно до теореми Гільберта про нулі, умова еквівалентна умові 1, або, еквівалентно, 1. Нехай тепер 1. Тоді. Питання про кінцівку чи нескінченність різноманіття V((F)) вирішується тепер теоремою 1 і лемою 2. Досить перевірити, чи містить базис Гребнера G багаточлени зі старшими термами при всіх i = 1. п. Завдання 2 повністю вирішується в теоремі 1. Для вирішення Завдання 3 потрібно вирішити наступне завдання. Завдання знаходження хоч одного рішення ідеалу нульової розмірності, якщо заданий наведений базис Гребнера цього ідеалу щодо лексикографічного порядку. Припустимо, щозаданий базис Гребнера, ідеалу, нульової розмірності. Нехай також є оракул A, що вирішує задачу знаходження кореня будь-якого багаточлена однієї змінної над К, де алгебраїчне замикання поля k. Зазначимо, що маючи базис Гребнера щодо деякого порядку, завжди можна знайти відповідний базис Гребнера щодо лексикографічного порядку (див., наприклад, [3]). Нехай, ідеал і G наведений базис Гребнера щодо лексикографічного порядку цього ідеалу. Тоді перетин складається точно з одного многочлена і є базисом Гребнера ідеалу кільця. Знаходимо за допомогою оракула A рішення рівняння 0 (K замикання алгебри поля k). Зауважимо, що з будь-якого рішення,, ідеалу I виконується співвідношення 0. Припустимо тепер, що рішення,, ідеалу. Щоб знайти продовження. отриманого вище рішення, обчислимо елементи базису Гребнера G, що знаходяться в кільці 199. Потім виконаємо підстановки для всіх j=1, i отримані багаточлени базису Гребнера. Отримаємо набір багаточленів, що залежать лише від однієї змінної. Обчислимо їх найбільший спільний дільник. Як буде показано нижче, отриманий многочлен має ступінь не менше одиниці і, отже, має безліч рішень в алгебраїчному замиканні поля k. Знаходимо за допомогою оракула A розв'язування рівняння 0. Тоді вектор. є рішенням ідеалу. Далі повторюємо описану процедуру доти, доки знайдемо повний вектор рішення ідеалу I. Нижче наведено алгоритм для описаної процедури знаходження рішення алгебраїчної системи рівнянь. Алгоритм А. Дано: Базис Гребнера, щодо лексикографічного порядку ідеалу, нульової розмірності.Вихід: Крапка. де До алгебраїчне замикання поля k. Крок 1 i := 1. Крок 2 Знаходимо перетин, що складається точно з 200 одного многочлена. Крок 3 := A деяке рішення рівняння 0. Крок 4 i := i + 1. Крок 5 Якщо i> п, перейти до кроку 10. Крок 6 Знаходимо перетин. Крок 7, :=. Крок 8 Знаходимо найбільший спільний дільник елементів множини. Крок 9 Переходимо до кроку 3. Крок 10 Вихід: Крапка. де До алгебраїчне замикання поля k є рішенням ідеалу I.

4 Теорема 2. Для будь-якого ідеалу розмірності нуль алгоритм А знаходить його рішення. Для доказу теореми достатньо довести, що на кроці 8 наведеного вище алгоритму завжди отримуємо багаточлен ступеня не менше одиниці, або, еквівалентно, кожне рішення, ідеалу, триває до рішення, ідеалу. Доказ цього твердження вимагатиме кілька допоміжних тверджень. Для будь-якого підмножини M кільця і будь-якого 0 5 коренем ідеалу I, то і. Отже. Тому і, Ω загальний корінь ідеалу. Лемма 12. Нехай, примарний ідеал і, загальний корінь простого ідеалу асоційованого з ідеалом. Тоді існує такий, що загальний корінь ідеалу. Доведення. Слід з лем 8 і 11. Лемма 13. Нехай, примарний ідеал розмірності 0 і, корінь ідеалу. Тоді існує такий, що корінь ідеалу. Доведення. Є окремим випадком леми 12, оскільки кожен корінь простого ідеалу розмірності нуль є його загальним коренем. Нагадаємо, що V(I) різноманіття ідеалу. Лемма 14. Якщо ідеал I є перетином ідеалів, де j пробігає від 1 до т, то. Доведення. Нехай. Тоді за деякого 1 виконується. А оскільки, то й. Отже, нехай тепер. Тоді для всіх j = 1. т є для яких 0. Оскільки всі є ідеалами, то твір є їх загальним елементом і, отже, належитьідеалу I. Елемент не належить різноманіттю V(I), коли виконується 0. Отже,. Лемма 15. Нехай, ідеал нульової розмірності і, корінь ідеалу. Тоді існує такий, що корінь ідеалу. Доведення. Відповідно до теореми Ласкера (див. [1]) Існує уявлення ідеалу I у вигляді перетину кінцевої множини примарних ідеалів. Нагадаємо, що розмірністю ідеалу називається максимальна розмірність асоційованих з його призмарними компонентами простих ідеалів. Оскільки I ідеал розмірності нуль, то всі ідеали також нульової розмірності. Очевидно, що виконується рівність, де. примарні ідеали розмірності нуль. Тому, згідно з лемою 14, для всіх i = 1. п має місце розкладання 1,. 2 Оскільки, корінь ідеалу, то з уявлення (2) випливає, що при деякому j елемент, є коренем ідеалу. Тому, по лемі 13 існує такий, що корінь ідеалу, 1, а, отже, згідно з формулами (1) і (2), є коренем ідеалу. Визначення 1. Розмірністю системи рівнянь алгебри називається розмірність відповідного ідеалу цієї системи. Системи рівнянь алгебри розмірності нуль будемо називати повними. Лемма 16. Нехай багаточлен із раціональними коефіцієнтами від однієї змінної. Тоді рівняння p(x) = 0 алгоритмічно можна розв'язати в полі раціональних чисел. Оскільки задача знаходження базису Гребнера ідеалу I щодо довільного порядку є алгоритмічно розв'язною, а по теоремі 1 для ідеалу розмірності нуль для кожної змінної існують багаточлени, що залежать тільки від цієї змінної і належать ідеалу I, завдання побудови таких многочленів алгоритмічно розв'язне. Нехай безліч раціональних рішень рівняння 0. Тоді раціональні рішення системи ідеалу I належать твору. Тому з леми 16 випливаєалгоритмічна розв'язність повної системи рівнянь алгебри над полем. Наслідок 3. Завдання знаходження рішення повної системи рівнянь алгебри над полем раціональних чисел є алгоритмічно розв'язним. Для неповних систем рівнянь, наприклад, діафантових рівнянь, твердження слідства 3 не виходить