1611672535-7205ee7fb92cecd63cdae109c575108c (826568), страница 19
Текст из файла (страница 19)
Теорема Гильбертао базисеПусть F — поле, fi (x1 , . . . , xn ) ∈ F [x1 , . . . , xn ], i ∈ Ω. Системойалгебраических уравнений (далее — системой) называется система вида{fi (x1 , . . . , xn ) = 0, i ∈ Ω}. Если |Ω| < ∞, то система называетсяконечной. Две системы называются эквивалентными, если множестваих решений совпадают. Обозначение: S1 ∼ S2 .Лемма 1. Всякая конечная система над R эквивалентна системеиз одного уравнения.Доказательство. Система {fi (x1 , . .
. , xn ) = 0, i = 1, . . . , m}эквивалентна уравнению2(x1 , . . . , xn ) = 0.f12 (x1 , . . . , xn ) + . . . + fmУпражнение. Доказать лемму 1 для произвольного алгебраическинезамкнутого поля.Лемма 2. Над полем C система {x = 0, y = 0} не эквивалентнаникакому уравнению.1147. Базисы ГрёбнераДоказательство. Пусть уравнение f (x, y) = 0 имеет решение x =0, y = 0. Пусть f (x, y) = a0 (y) + a1 (y)x + . . . + am (y)xm , где am (y) 6=0. Тогда существует такое y0 6= 0, что am (y0 ) 6= 0.
Значит, уравнениеa0 (y0 )+a1 (y0 )x+. . .+am (y0 )xm имеет корень x0 . Следовательно, (x0 , y0 )— решение уравнения f (x, y) = 0.¤Пусть A — ассоциативное коммутативное кольцо с 1. Говорят, чтоидеал I E A порождается элементами ai ∈ A, i ∈ Ω, если I := (ai , i ∈Ω) := {ai1 r1 + . . . + ain rn : ri ∈ A}, т. е. I есть наименьший идеалв A, содержащий ai , i ∈ Ω. Говорят, что элементы ai , i ∈ Ω, составляютбазис идеала I. Элементы ai , i ∈ Ω, называются порождающими (илиобразующими) элементами идеала I. Говорят, что идеал I EA допускаетконечный базис, если существуют a1 , . . . , an ∈ A такие, что I =(a1 , .
. . , an ).Теорема 1 (Гильберта о базисе). Пусть I E F [x1 , . . . , xn ]. Тогда Iдопускает конечный базис.Доказательство. Рассмотрим сначала случай, когда I порождаетсяодночленами m1 , m2 , . . . Покажем, что в I можно выбрать базисmi1 , . . . , mik . Проведём индукцию по n. При n = 1 утверждениеочевидно. В случае n неизвестных подставим во все одночлены xn = 1и в полученной совокупности выберем базис m01 , . . . , m0s .
Пусть mi ∈ Iсоответствует m0i и l есть наибольший показатель при xn в одночленахm1 , . . . , ms . Рассмотрим все одночлены из I степени p относительно xn ,p = 0, . . . , l − 1. Подставим в них xn = 1 и в полученном множестве(p)(p)вновь выберем базис m1 , . . . , msp . Легко видеть, что множество(j){m1 , . . . , ms , mi xjn : j = 0, . .
. , l − 1, i = 1, . . . , sj } является базисомв I.Далее рассмотрим лексикографический порядок на множествеαn1> xβ1 1 . . . xβnn , если либо α1 > β1 , либоодночленов, т. е. xα1 . . . xnα1 = β1 , . . . , αk = βk , αk+1 > βk+1 для некоторого k. Пусть J —идеал, порождённый старшими членами fC элементов f из I. Выберемконечный базис m1 , . . . , mk в J.
Пусть fi — многочлены из I, старшиечлены которых равны mi . Покажем, что fi образуют базис в I. Еслиf ∈ I, то fC = mi r для некоторых i и одночлена r. Тогда g = f − fi r ∈ Iи gC < fC . За конечное число шагов получим f ∈ (f1 , . . . , fk ).¤§ 2. Идеал системы, аффинное алгебраическое многообразие§ 2.115Идеал системы, аффинное алгебраическое многообразие, радикал идеалаДля всякой системы S = {fi (x1 , . .
. , xn ) = 0, i ∈ Ω} мы можемопределить идеал I(S) = (fi , i ∈ Ω).Лемма 1. Если f ∈ I(S), то f (x01 , . . . , x0n ) = 0 для любого решениясистемы S.Доказательство. Имеем f ∈ I(S) ⇔ f = r1 fi1 + . . . + rm fim .Следовательно, f (x01 , . . . , x0n ) = 0.¤(x01 , . . . , x0n )Предложение 1. Пусть {f1 , . . . , fm } и {g1 , .
. . , gk } — два базиса в I.Тогда системы S1 = {f1 = 0, . . . , fm = 0} и S2 = {g1 = 0, . . . , gk = 0}эквивалентны.Доказательство. Если x̄ = (x01 , . . . , x0n ) — решение S1 , тоgi (x01 , . . . , x0n ) = 0 по лемме 1. Следовательно, x̄ — решение системыS2 . Обратное аналогично.¤Таким образом, множество решений системы однозначноопределяется идеалом системы, а различным базисам одного идеалаотвечают эквивалентные системы.Следствие 1. Любая система эквивалентна конечной системе.Доказательство.
Из теоремы 1 § 1 следует, что во всяком идеалекольца F [x1 , . . . , xn ] можно выбрать конечный базис.¤Следствие 2. Любая система от одного неизвестногоэквивалентна системе из одного уравнения.¤Подмножество X в Fn называется аффинным алгебраическиммногообразием, если существует система S такая, что x̄ ∈ S ⇔ x̄ ∈X(S), где X(S) обозначает множество решений системы S. Если I EF [x1 , . .
. , xn ], то через X(I) обозначим подмножество в Fn , состоящееиз элементов, на которых все многочлены из I равны 0. Ясно, чтоS1 ∼ S2 ⇔ X(S1 ) = X(S2 ), а также что X(S) = X(I(S)).Заметим, что системы могут быть эквивалентны, но их идеалы несовпадают.Пример.
x = 0 ∼ x2 = 0, но (x2 ) 6= (x).Однако для любого многообразия X существует наибольший идеалJ(X), задающий это многообразие:J(X) = {f ∈ F [x1 , . . . , xn ] : f (x) = 0 для любого x ∈ X}.1167. Базисы ГрёбнераПредложение 2. S1 ∼ S2 ⇔ J(X(S1 )) = J(X(S2 )).Доказательство.
Покажем, что если J(X(S1 )) = J(X(S2 )), тоX(S1 ) = X(S2 ). Так как Si ⊆ I(Si ) ⊆ J(X(Si )), то для любого f ∈ S1имеем f ∈ J(X(S2 )), т. е. любое решение системы S2 является решениемсистемы S1 . Следовательно, X(S2 ) ⊆ X(S1 ). Аналогично показываетсяобратное. Теперь очевидны эквивалентности: S1 ∼ S2 ⇔ X(S1 ) =X(S2 ) ⇔ J(X(S1 )) = J(X(S2 )).¤Радикалом идеала I называется множествоr(I) = {f ∈ F [x1 , . . . , xn ] : f s ∈ I для некоторого s ∈ N}.Предложение 3. 1. I ⊆ r(I).
2. r(I) E F [x1 , . . . , xn ]. 3. X(I) =X(r(I)).Доказательство. 1. Очевидно.2. Пусть f1 , f2 ∈ r(I) и f1s1 ∈ I, f2s2 ∈Ps1 +s2=αk f1k f2s1 +s2 −k ∈ I, αk ∈ F . Если f2I. Тогда (f1 + f2 )s1произвольный, то (f1 f2 ) ∈ I ⇒ f1 f2 ∈ r(I). 3. Из I ⊆ r(I) следуетX(r(I)) ⊆ X(I). Обратно, если x̄ ∈ X(I) и f (x̄) 6= 0 для некоторогоf ∈ r(I), то f s (x̄) 6= 0 для любого s, но существует s такое, что f s ∈ I.¤Идеал I называется радикальным, если I = r(I).Упражнение.
Показать, что r(r(I)) = r(I).Далее в этом параграфе считаем F = C.Предложение 4. (см.: Прасолов В. В. Многочлены. М.: МЦНМО,2000.) Если f1P, . . . , fm без общих нулей, то существуют такиеm¤g1 , . . . , gm , что i=1 fi gi = 1.Теорема 1 (Гильберта о нулях). Для любой системы S над Cсправедливо равенствоJ(X(S)) = r(I(S)).Переформулировка: Для системы {fi (x1 , . .
. , xn ) = 0, i = 1, . . . , m}многочлен f (x1 , . . . , xn ) обращается в нуль на всех решениях даннойсистемы ⇔ существуютr1 (x1 , . . . , xn ), . . . , rm (x1 , . . . , xn ) и s ∈ NPmтакие, что f s = i=1 ri fi .Замечание. Над R теорема не верна.Доказательство. Пусть S = {f1 = 0, . .
. , fm = 0} и f (x01 , . . . , x0n ) = 0для любого (x01 , . . . , x0n ) ∈ X(S). Покажем, что существует s ∈ N такое,что f s ∈ (f1 , . . . , fm ). При f = 0 утверждение очевидно. Добавим117§ 3. Базис Грёбнера идеалак неизвестным x1 , . . . , xn новую неизвестную xn+1 = z и рассмотриммногочлены f1 , . . . , fm , 1 − zf . Они не имеют общих нулей, поэтому1=mXhi fi + hm+1 (1 − zf ),i=1где hi ∈ F [x1 , .
. . , xn , z]. ПоложимPm z = 1/f . После приведения к общему¤знаменателю получим: f s = i=1 ri fi , где ri ∈ F [x1 , . . . , xn ].Следствие 3. S1 ∼ S2 ⇔ r(I(S1 )) = r(I(S2 )).Следствие 3 показывает,аффинными алгебраическимиидеалами кольца C[x1 , . . . , xn ].¤что существует биекция междумногообразиями и радикальнымиПредложение5. Пусть f1 (x1 , . .
. , xn ) и f2 (x1 , . . . , xn )неприводимы. Тогда f1 = 0 ∼ f2 = 0 ⇔ f1 = αf2 , α ∈ C.Доказательство. Из неприводимости fi и факториальности кольцаC[x1 , . . . , xn ] следует, что если некоторая степень f делится на fi , то fделится на fi . Следовательно, r((fi )) = (fi ). Таким образом, f1 = 0 ∼f2 = 0 ⇔ (f1 ) = (f2 ) ⇔ f1 = αf2 .¤Следствие 4. Система S несовместна ⇔ 1 ∈ I(S).Доказательство. X(S) = ∅ ⇔ S ∼ 1 = 0 ⇔ r(I(S)) =r(C[x1 , . . .
, xn ]) ⇔ 1 ∈ r(I(S)) ⇔ 1 ∈ I(S).¤§ 3.Базис Грёбнера идеалаЗадача вхождения. Пусть идеал I E F [x1 , . . . , xn ] задан базисомI = (f1 , . . . , fm ). Требуется найти алгоритм, позволяющий за конечноечисло шагов выяснить, принадлежит ли данный многочлен h =h(x1 , . . . , xn ) идеалу I.Редукция. Предположим, что hC делится на (fi )C , т. е. hC = (fi )C ·q. Положим h1 = h − fi · q.
Тогда (h1 )C < hC и h ∈ I ⇔ h1 ∈ I.Таким образом, задачу вхождения теперь можно решать для h1 . Еслиза конечное число редукций h сводится к нулю (редуцируется), то h ∈ I.Базис f1 , . . . , fm в I называется базисом Грёбнера, если любой h ∈ Iредуцируется к нулю при помощи f1 , . . . , fm .Заметим, что f1 , .
. . , fm — базис Грёбнера в I ⇔ I = (f1 , . . . , fm )и для любого h ∈ I одночлен hC делится на некоторый (fi )C .1187. Базисы ГрёбнераЛемма 1. Пусть f1 , . . . , fm ∈ I такие, что для любого h ∈ Iодночлен hC делится на (fi )C для некоторого i. Тогда f1 , . . . , fm —базис Грёбнера в I.Упражнение. Н.О.Д.(fC , gC ) = 1 ⇒ {f, g} — базис Грёбнера в I =(f, g).Таким образом, если нам известен базис Грёбнера идеала I и данмногочлен h, то, проводя всевозможные редукции с помощью элементовбазиса, получаем, что h ∈ I ⇔ h редуцируется к нулю.Лемма 2. Пусть I E F [x1 , .
. . , xn ]. Тогда в I существует базисГрёбнера.Доказательство. Рассмотрим идеал, порождённый всемиэлементами fC , f ∈ I, и выберем в нём по теореме Гильбертао базисе конечный базис J. Тогда элементы исходного идеала, старшиечлены которых образуют базис J, составляют конечный базис Грёбнерав I.¤Пусть I = (f1 , . . . , fm ).