Университет города Переславля

          "Алгоритмы непрерывной математики"
        осенний семестр 1998-99 учебного года
                  С.В.Дужин

                  Лекция 3
            Идеалы и базисы Гребнера


Теорема 1.
Система уравнений не имеет решений над полем комплексных чисел
тогда и только тогда, когда ее базис Гребнера относительно любого порядка
содержит ненулевую константу.

Пример 1. Система уравнений
x+y=1, x^2+2xy+y^2=2
несовместна.
Соответствующий идеал содержит ненулевую константу, т.к.
(x+y+1)(x+y-1) + (x^2+2xy+y^2-2) = -3.
Константа не редуцируется и, следовательно, принадлежит любому базису
Гребнера.

Пример 2. Система состоит из одного уравнения x^2+y^2+1=0,
которое и составляет базис Гребнера. В список, состоящий из
одного многочлена {x^2+y^2+1}, ненулевая константа не входит.
По теореме, это уравнение должно иметь комплексные корни (в самом деле,
пара (i,0) является решением). Заметим, что над полем
действительных чисел данная система решений не имеет.

Теорема 2.
Система уравнений имеет конечное число решений (над полем комплексных
чисел) тогда и только тогда, когда любая переменная входит в ведущий моном
некоторого элемента базис Гребнера в чистом виде, т.е. для любого i=1,...,n
базис Гребнера содержит многочлен вида
   c*x_i^{k_i} + младшие члены.

Определение. Идеал, порожденный данным набором многочленов f_1,...,f_k,
-- это множество всех комбинаций вида g_1f_1 + ... + g_kf_k, где g_i
-- произвольные многочлены. Идеал обозначается I = <f_1,...,f_k>.

Важное наблюдение. Предположим, что нам дана какая-то система полиномиальных 
уравнений. Запишем ее в виде f_1=0, ..., f_k=0. Тогда для любого 
многочлена f, принадлежащего идеалу <f_1,...,f_k>, уравнение f=0 является
следствием данной системы. 

Соответствие 
   {множества точек в C^n} -->  {идеалы в A}
Множеству M в C^n отвечает совокупность всех многочленов,
которые обращаются в нуль во всех точках множества M.

Примеры.

1. Одноточечное множество {(0,0)} на плоскости.
Ему соответствует идеал <x,y>.

2. Пространственная кривая {(t,t^2,t^3)}.
Ей отвечает идеал <y-x^2,z-x^3>.

Соответствие 
   {идеалы в A} --> {множества точек в C^n}
Идеалу I отвечает множество всех точек, в которых обращаются в нуль все
многочлены, принадлежащие I, т.е. множество всех решений соответствующей
системы уравнений.

Примеры.

1. <xy, x+y-1> -- 2 точки

2. <xy, y^2-y> -- точка и прямая