%From ivan@arjantse.mccme.ru Sat Aug  3 23:58:05 2002
%Date: Sat,  3 Aug 2002 22:13:35 +0400 (MSD)
%From: Ivan V. Arzhantsev <ivan@arjantse.mccme.ru>
%To: vitar@mccme.ru
%Subject: Bazisy Grobnera - text
%
% Текст отправлен Виталию Арнольду 03.08.02
%
\documentstyle[11pt,russcorr,twoside]{report}
%%%\documentclass[11pt,twoside]{report}
%%%\usepackage{russcorr}
\textwidth=110mm
\textheight=175mm
\hoffset=5mm
\voffset=10mm
\hfuzz=1pt

\def\Lla{\Longleftarrow}
\def\Lra{\Longrightarrow}
\def\Llra{\Longleftrightarrow}
\def\ide{\triangleleft}
\def\ov{\overline}
\def\wt{\widetilde}

\newcommand{\bx}[1]{\mbox{\jirny {#1}}}
\newfont{\jirny}{msbm10 at 12pt}

\makeatletter
\newcommand{\l@abcd}[2]{\hbox to\textwidth{#1\dotfill #2}}


%corrected for 2-e Recently it was as the next line
%\renewcommand{\k}{{\bx K}}       % поле k
\newcommand{\k}{{\bx K}}       % поле k
\newcommand{\A}{{\bx A}}       % поле A
\newcommand{\C}{{\bx C}}       % поле C
\newcommand{\R}{{\bx R}}       % поле R
\newcommand{\Q}{{\bx Q}}       % поле Q
\newcommand{\Z}{{\bx Z}}       % кольцо Z
\newcommand{\N}{{\bx N}}       % N

\newcommand{\do}{{\bf Доказательство.}\ }
\newcommand{\qedh}{~~{\vrule height 5pt width 5pt depth 0pt}}
\newcommand{\qedv}{~~{\vrule height 5pt width 5pt depth 0pt}%
                  \par\smallskip\par}

\renewcommand{\bibname}{Литература о базисах Гребнера}

\newcounter{pr}[chapter]
\newcounter{refer}[chapter]

\newcommand{\bde}[1]{\par%
\pagebreak[1]\smallskip%
\refstepcounter{pr}\noindent{\bf Определение \arabic{chapter}.\arabic{pr}.}%
\ \ {\rm #1}\par\smallskip\par}

\newcommand{\bza}[2]{\par%
\pagebreak[1]\smallskip%
\refstepcounter{pr}\noindent{\bf Задача{#1} \arabic{chapter}.\arabic{pr}.}%
\ \ {\rm #2}\par\smallskip\par}

\newcommand{\bth}[1]{\par%
\pagebreak[1]\smallskip%
\refstepcounter{pr}\noindent{\bf Теорема \arabic{chapter}.\arabic{pr}.}%
\ \ {\it #1}\par\smallskip\par}

\newcommand{\bco}[1]{\par%
\pagebreak[1]\smallskip%
\refstepcounter{pr}\noindent{\bf Следствие \arabic{chapter}.\arabic{pr}.}%
\ \ {\it #1}\par\smallskip\par}

\newcommand{\bpr}[1]{\par%
\pagebreak[1]\smallskip%
\refstepcounter{pr}\noindent{\bf Предложение \arabic{chapter}.\arabic{pr}.}%
\ \ {\it #1}\par\smallskip\par}

\newcommand{\ble}[1]{\par%
\pagebreak[1]\smallskip%
\refstepcounter{pr}\noindent{\bf Лемма \arabic{chapter}.\arabic{pr}.}%
\ \ {\it #1}\par\smallskip\par}

\newcommand{\bex}[1]{\par%
\pagebreak[1]\smallskip%
\refstepcounter{pr}\noindent{\bf Пример \arabic{chapter}.\arabic{pr}.}%
\ \ {\rm #1}\par\smallskip\par}

\renewcommand{\thepr}{\thechapter.\arabic{pr}}

\pagestyle{headings}



\makeatother
\begin{document}

\tableofcontents


\newpage

\thispagestyle{plain}

\markboth{\thesection\hspace{1em}Предисловие}{Предисловие}
\section*{Предисловие}

\addcontentsline{toc}{abcd}{Предисловие}

Этот курс является расширенным вариантом записок лекций, прочитанных
студентам пятого курса математического факультета
Московского Педагогического Государственного Университета осенью 1998 года
и вышедших отдельными брошюрами в издательствах "Диалог-МГУ" (1999 год)
и "МАКС Пресс" (2002 год). Излагаемый материал также послужил основой
для четырех занятий, проведенных автором в рамках летней школы для
старших школьников и студентов младших курсов "Современная математика"
(Дубна, 16-28 июля 2002 года).

Для освоения курса достаточно иметь самые начальные знания по алгебре.
Предполагается, что читатель
знаком с понятиями кольца, поля и владеет теорией
систем линейных уравнений.
Даже излагаемые
на втором курсе сведения об идеалах колец здесь в основном
напоминаются.

Теорема Абеля о неразрешимости в радикалах алгебраических уравнений степени
пять и выше на первый взгляд лишает нас всякого оптимизма относительно
возможности решения произвольного уравнения или системы уравнений.
Однако рассматриваемые здесь результаты, объединенные с численными методами
решения уравнений, позволяют эффективно решать многие
системы алгебраических уравнений.

У этого курса две цели. Первая -- продемонстрировать,
что такие абстрактные теоремы как теорема Гильберта
о базисе или теорема Гильберта о нулях имеют простую и весьма полезную
интерпретацию в теории систем алгебраических уравнений. В случае
теоремы Гильберта о нулях существенно, чтобы система рассматривалась
не над вещественными, а над комплексными числами.
Это может послужить еще одной мотивировкой для введения комплексных
чисел, естественность которых нередко вызывает сомнения
у студентов--младшекурсников.
Вторая цель -- ввести понятие базиса Гребнера идеала
и показать, насколько сильные
алгоритмические методы это понятие предоставляет для решения общих
систем алгебраических уравнений.
В последние десятилетия базис Гребнера идеала стал играть важную роль во многих
исследованиях по абстрактной алгебре, компьютерной алгебре,
алгебраической геометрии, теории выпуклых многогранников, дискретной геометрии
и других областях математики, и поэтому изложение первоначальных сведений по этому
вопросу в рамках университетского курса представляется вполне уместным.
Мы не останавливаемся здесь на
вычислительных аспектах теории,
но изложенного материала вполне достаточно,
например, для того, чтобы подготовленный студент написал
программу, которая для произвольной системы алгебраических
уравнений отвечала на вопрос конечно или бесконечно число ее (комплексных)
решений.

В основной части текста (главы 1-5) мы доказываем лишь простые утверждения. Все
трудные результаты приводятся на уровне формулировок
и иллюстраций. Это сделано для того, чтобы не утруждать читателя излишними
подробностями и быстрее перейти к решению конкретных систем.
По нашему мнению, алгоритм Бухбергера и его применение к решению
систем, изложенные в виде рецептов, доступны школьнику
старших классов. Удивительно, что понятие базиса Гребнера возникло
в математике сравнительно недавно. Оно было введено Бруно Бухбергером
в его диссертации 1965 г., написанной под руководством Вольфганга Гребнера.
Аналогичные идеи были высказаны также Х.~Хиронакой и А.~И.~Ширшовым.


Для полноты изложения в главе 6 собраны доказательства
всех использованных утверждений. Глава 7 содержит
материал, касающийся современных исследований по базисам Гребнера.
Лекции снабжены большим количеством задач, решение которых весьма полезно
для овладения изложенным материалом.

После появления первого издания настоящего курса в нашей стране вышло
в свет несколько замечательных книг, в которых обсуждаются базисы Гребнера.
В первую очередь отметим монографию Д.~Кокса, Дж.~Литтла и Д.~О'Ши
"Идеалы, многообразия и алгоритмы" (Москва: Мир, 2000.).
Единственное, чем можно мотивировать перепечатку наших лекций после
появления книги Д.~Кокса и др. -- это небольшим объемом первых. К тому же
книга Д.~Кокса, Дж.~Литтла и Д.~О'Ши уже исчезла из московских книжных
магазинов. Также мы рекомендуем читателю, желающему быстро освоить
основные факты о базисах Гребнера, главу 6
книги В.~В.~Прасолова "Многочлены" (Москва: МЦНМО, 2000).
В этих лекциях мы активно использовали материал как из упомянутых книг, так
и из других источников, перечисленных в конце текста, поэтому курс нисколько
не претендует на оригинальность.


Автор познакомился с понятием базиса Гребнера на лекциях
профессора В.~Н.~Латышева, которые,
будучи студентом, прослушал в Московском Государственном
Университете им. М.~В.~Ломоносова в 1994 году. Я благодарен Виктору Николаевичу
за его лекции, а также за последующие полезные обсуждения.
Особая благодарность слушателям курса в летней школе "Современная
математика" -- их интерес к теме, многочисленные вопросы и замечания побудили
автора существенно дополнить изначальный текст.
Также я благодарен Московскому Центру Непрерывного Математического Образования
за предоставленную возможность издать этот курс, и моей жене
Л.~А.~Аржанцевой за помощь в компьютерных вычислениях и в работе над текстом.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter[Основные понятия и определения]
{Основные понятия и результаты теории систем
алгебраических уравнений}

\section{Введение}


Фиксируем натуральное число $n$ и некоторое поле $\k$
(можно считать, что $\k$ есть поле рациональных чисел $\Q$,
поле действительных чисел $\R$ или поле комплексных чисел $\C$).
Пусть $x_1,\dots,x_n$ --- переменные, а
$P_1(x_1,\dots,x_n)$,
$P_2(x_1,\dots,x_n)$,
\dots --- набор (возможно, бесконечный)
многочленов от переменных $x_1,\dots,x_n$ с коэффициентами в поле $\k$.

\bde{{\it Системой алгебраических уравнений} (САУ) называется система вида
$$
\cases{P_1(x_1,\dots,x_n)=0;\cr
       P_2(x_1,\dots,x_n)=0;\cr
       \quad\cdots\cdots\cdots\cr}
\refstepcounter{refer}
\eqno{(\therefer)}
\label{sys1}
$$}

\bde{САУ называется {\it конечной}, если в нее входит
лишь конечное число уравнений.}

\bde{Набор чисел $(a_1,a_2,\dots,a_n)$ из поля $\k$ называется {\it решением}
системы (\ref{sys1}), если
$$P_1(a_1,a_2,\dots,a_n)=0,\ P_2(a_1,a_2,\dots,a_n)=0,\ \dots\ .$$}

\bde{Две САУ  называются {\it эквивалентными},
если множества их решений совпадают.}

\bex{Над полем $\R$ системы
$$ \left\{ x^2+y^2=-1\right. \quad\mbox{ и }\quad
\left\{
\begin{array}{l}
x+y=2;\\
x^2+2xy+y^2=3.
\end{array}
\right.  $$
эквивалентны, так как множества их решений пусты.

Над полем $\C$ системы неэквивалентны, т.к. $x=i$, $y=0$
удовлетворяет первой системе, но не удовлетворяет второй.}\label{1ex5}

Решить систему значит описать множество всех ее решений или доказать,
что решений нет.


\bza{}{Решить первую и вторую систему над $\C$.}\label{z1}

{\bf Основная задача.} Научиться решать САУ.

\smallskip

В такой общей постановке задача вряд ли может быть решена.
Исторически алгебра формировалась как наука о решении САУ
(заметим, что одно алгебраическое уравнение можно рассматривать
как частный случай САУ). Было накоплено огромное количество результатов,
в том числе и негативного характера. Наиболее яркий из таких результатов
--- это теорема Абеля о неразрешимости в радикалах общего
алгебраического уравнения степени $\ge 5$.

В этом курсе мы рассмотрим несколько методов, позволяющих эффективно
решать САУ. Эти методы были
развиты сравнительно недавно и тесно примыкают к весьма абстрактным
разделам коммутативной алгебры.

Интересно также качественное исследование множества решений САУ.
Например, хотелось бы знать:

1) Имеет ли система хотя бы одно решение?

2) Эквивалентны ли две данные системы?

3) Конечно или бесконечно множество решений системы?

4) Как устроено множество решений с геометрической точки зрения?

Развиваемые здесь методы оказываются полезными
при исследовании подобных вопросов.

\bigskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Системы линейных уравнений}

Простейший пример САУ --- это система линейных уравнений.
Здесь имеется вполне завершенная теория, которая как правило
излагается в ВУЗе на первом курсе.

Напомним основные определения и результаты.

Рассмотрим систему
$$
\cases{a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n=b_1,  \cr
       a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n=b_2,  \cr
       \dots   \cr
       a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n=b_m.  \cr}
\refstepcounter{refer}
\eqno{(\therefer)}
\label{sys2}
$$

\bde{Система (\ref{sys2}) называется {\it совместной}, если она
имеет хотя бы одно решение.}

\bde{Система (\ref{sys2}) называется {\it определенной}, если она
имеет ровно одно решение.}

\bde{Матрица
$$A=\left(
\matrix{a_{11}&\ldots&a_{1n}\cr
\vdots&\ddots&\vdots\cr
a_{m1}&\ldots&a_{mn}\cr}
\right)$$
называется {\it матрицей коэффициентов} системы (\ref{sys2}), а матрица
$$\wt A=\left(
\matrix{a_{11}&\ldots&a_{1n}\cr
\vdots&\ddots&\vdots\cr
a_{m1}&\ldots&a_{mn}\cr}\left|
\matrix{b_1\cr
\vdots\cr
b_m\cr}
\right.\right)$$
-- {\it расширенной матрицей} системы.}

Универсальный метод решения систем линейных уравнений (т.е. метод,
применимый к произвольной системе) --- это метод Гаусса, или метод
последовательного исключения неизвестных.
Он состоит в следующем.

{\bf Шаг 1.}\ \ Элементарными преобразованиями строк
приводим расширенную матрицу системы к ступенчатому виду

{\unitlength=0.5mm
$$\left(
\matrix{a_{11}&\ldots&a_{1n}\cr
\vdots&\ddots&\vdots\cr
a_{m1}&\ldots&a_{mn}\cr}\left|
\matrix{b_1\cr
\vdots\cr
b_m\cr}
\right.\right)\leadsto
\left(
\begin{picture}(70,17)
\put(0,-10){\begin{picture}(60,40)%
\multiput(63,-3)(0,7){4}{*}
\put(13,4){\circle{10}}
\put(58,-3){\line(0,1){29}} %разделитель
\put(41,-2){\line(1,0){15}}
\put(41,-2){\line(0,1){7}}
\put(42,-3){*}
\put(31,5){\line(1,0){10}}
\put(31,5){\line(0,1){7}}
\put(32,4){*}
\put(21,12){\line(1,0){10}}
\put(21,12){\line(0,1){7}}
\put(22,11){*}
\put(1,19){\line(1,0){20}}
\put(1,19){\line(0,1){7}}
\put(4,18){*}
\end{picture}}
\end{picture}
\right)
$$}

\smallskip

{\bf Теорема Кронекера - Капелли.}\ \ {\it Система (\ref{sys2})
совместна тогда и только тогда, когда ранг $rk\,A$
матрицы коэффициентов равен рангу $rk\,\wt A$
расширенной матрицы.}

\smallskip

После приведения к ступенчатому виду равенство рангов означает, что
число ненулевых строк у матриц $A$ и $\wt A$ одинаково.

\smallskip

Далее предполагаем, что система совместна.

{\bf Шаг 2.}\ \ Переменные, которые соответствуют "ступенькам"
в ступенчатом виде, назовем {\it главными}, а прочие неизвестные
--- {\it свободными}.

\smallskip

\hangindent=6cm \hangafter=-4
\noindent
{\unitlength=0.5mm
\begin{picture}(0,0)
\put(-110,-23){$\left(\begin{picture}(80,17)%
\multiput(75,-9)(0,7){4}{\circle*{2}}
\put(68,-12){\line(0,1){28}} %разделитель
\put(56,-12){\line(1,0){11}}
\put(56,-12){\line(0,1){7}}
\put(61,-9){\circle*{2}}
\put(45,-5){\line(1,0){11}}
\put(45,-5){\line(0,1){7}}
\put(50,-2){\circle*{2}}
\put(23,2){\line(1,0){22}}
\put(23,2){\line(0,1){7}}
\put(39,5){\circle*{2}}
\put(28,5){\circle*{2}}
\put(1,9){\line(1,0){22}}
\put(1,9){\line(0,1){7}}
\put(6,12){\circle*{2}}
\put(17,12){\circle*{2}}
\put(3,23){$x_1$}
\put(14,23){$x_2$}
\put(25,23){$x_3$}
\put(36,23){$x_4$}
\put(47,23){$x_5$}
\put(58,23){$x_6$}
\end{picture}\right)$}
\end{picture}}
Так на схеме слева переменные $x_1$, $x_3$, $x_5$, $x_6$ --- главные,
а $x_2$, $x_4$ --- свободные.

\

\

\bigskip

Выбор главных и свободных переменных неоднозначен.
В то же время число главных и число
свободных неизвестных определено однозначно.

\bza{}{Привести пример системы линейных уравнений, у которой нет нулевых
коэффициентов, число решений бесконечно, но переменная $x_1$ не может
быть свободной.}\label{z3}

\bza{}{Сколько есть способов выбрать множество свободных
неизвестных в системе
$$
\left\{
\begin{array}{l}
x_1+2x_2+x_3+x_4-x_5=0\\
2x_1+3x_2+2x_3+2x_4-2x_5=1 \ \ \ \ ?
\end{array}
\right.
$$}\label{z2}

\bth{Число свободных неизвестных равно $n-rk A$.
В частности, система (\ref{sys2}) определена
$\Longleftrightarrow$ $rk A=rk\wt A=n$.}\label{aaa}

{\bf Шаг 3.}\ \ Выражаем в обратном порядке главные неизвестные
через свободные. Свободные неизвестные могут независимо принимать
произвольные значения из поля $\k$.

\smallskip

{\bf Замечание.} Если система над бесконечным полем
($\Q$, $\R$, $\C$, \dots) имеет более одного решения,
то она имеет бесконечно много решений (есть свободная неизвестная).
В частности, множество из двух точек в $\R^n$ не может быть
задано системой линейных уравнений.

\smallskip

Помимо метода Гаусса есть и другие методы решения системы (\ref{sys2}).
Например, метод Крамера использует определители.
Этот метод не универсален, он применим только к
квадратным определенным системам.

\medskip

{\bf Геометрически} множество решений системы линейных уравнений
над $\R$ есть некоторое подмножество пространства $\R^n$.
Эти множества описывает следующая теорема.

\bth{1) Множество решений системы (\ref{sys2}) либо пусто, либо
есть линейное многообразие
$M$, т.е. результат параллельного переноса подпространства
$U\subseteq\R^n$ на некоторый вектор $a\in \R^n$.

{\unitlength=0.5mm
\begin{picture}(80,80)
\put(70,20){\begin{picture}(0,0)%
%%%%%%%%%%  оси координат
\put(0,-5){\vector(0,1){55}}
\put(-10,0){\vector(1,0){85}}
\put(-15,-5){\vector(3,1){75}}
\put(2,45){$Oz$}
\put(70,-7){$Ox$}
\put(62,17){$Oy$}
%%%%%%%%%%  плоскости
\multiput(0,0)(15,20){2}{%
\thicklines
\put(-20,0){\line(2,-1){30}}
\put(-20,0){\line(-1,1){10}}
\put(-20,15){\line(-2,-1){10}}
\put(-20,15){\line(3,-1){30}}
\put(30,-10){\line(-4,3){20}}
\put(30,-10){\line(-2,-1){10}}
\put(10,-15){\line(1,0){10}}%
}
{\thicklines
\put(0,0){\vector(3,4){15}}}
\put(15,15){$a$}
\put(-20,35){$M$}
\put(35,-15){$U$}
\end{picture}}
\end{picture}}

2) Обратно, всякое линейное многообразие может быть
задано системой линейных уравнений.}\label{1th12}

\bza{*}{Доказать теорему \ref{1th12}.}\label{z4}

\bex{В $\R^3$ есть четыре типа подпространств:
1) начало координат;
2) прямая, проходящая через 0;
3) плоскость, проходящая через 0;
4) все пространство $\R^3$.

Поэтому в качестве множества решений системы линейных
уравнений от трех неизвестных может выступать пустое множество, произвольная
точка, произвольная прямая, произвольная плоскость или все
пространство $\R^3$.}

\bza{}{Привести примеры конкретных систем от 3-х неизвестных,
реализующие каждую из указанных возможностей.}

Итак, указан явный алгоритм решения системы (\ref{sys2}),
а также получены ответы на качественные вопросы.
В этой теории встают алгоритмические проблемы наиболее
эффективного способа приведения матрицы к ступенчатому виду,
вычисления определителя матрицы за наименьшее число операций и т.п.
Здесь мы не будем касаться подобных задач.

Резюмируя вышесказанное, отметим, что

1) теория систем линейных уравнений не зависит от того, над каким
полем рассматривается система
(в теории нелинейных систем это уже не так, см. пример \ref{1ex5});

2) свободные переменные могут независимо принимать {\bf произвольные}
значения из основного поля, а главные переменные {\bf однозначно}
через них выражаются.


{\bf Проблема.} Какие результаты из теории систем линейных
уравнений можно перенести на произвольные САУ?
В частности, можно ли там определить понятие свободной переменной?



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Некоторые сведения о многочленах}


Пусть $\k[x_1,\dots, x_n]$ -- множество всех многочленов от переменных
$x_1,\dots, x_n$ с коэффициентами в поле $\k$ (или, как говорят, над
полем $\k$). На этом множестве определены операции сложения и умножения.
Множества с такими операциями в алгебре называют кольцами.

Для многочленов от одной неизвестной будем обозначать
$deg\ f(x)$ степень многочлена $f(x)$.

\smallskip

{\bf Теорема о делении с остатком для многочленов от одной переменной.}
\ \ {\it Для любых многочленов $f(x), \ g(x) \in \k[x], \ g(x)\ne 0$
существуют и единственны многочлены $q(x), \\ r(x) \in \k[x]$ такие, что
$f(x)=g(x)q(x)+r(x)$ и $deg\ r(x) < deg\ g(x)$.}

\smallskip

Многочлен $q(x)$ называется неполным частным, а многочлен $r(x)$ --
остатком при делении $f(x)$ на $g(x)$. Доказательство этой теоремы несложно
получить рассуждая по индукции по степени многочлена $f(x)$ (деление
многочленов "в столбик").

\smallskip

\bza{}{Разделить $x^2-x+1$ на $x^3+2x$ с остатком.}\label{z5}

\bza{}{Верна ли теорема о делении с остатком в кольце
$\Z[x]$ ?}\label{z6}

\smallskip

{\bf Теорема Безу.} \ \ {\it  Число $\alpha\in \k$ является корнем многочлена
$f(x)\in \k[x]$ тогда и только тогда, когда $f(x)$ делится на $(x-\alpha)$
(без остатка).}

\smallskip

Доказательство этой теоремы следует из теоремы о делении с остатком
(степень остатка при делении $f(x)$ на $(x-\alpha)$ равна нулю,
т.е. это константа).

\smallskip

\bde{Многочлен $p(x_1,\dots, x_n)$ называется {\it неприводимым}, если
он отличен от константы и равенство $p=p_1p_2$ влечет за собой равенство
константе одного из многочленов $p_1$ или $p_2$.}

\smallskip

\bde{Два многочлена называются {\it ассоциированными}, если они отличаются
ненулевым числовым множителем.}

\smallskip

Неприводимые многочлены являются аналогом простых чисел.
Для многочленов также имеет место теорема об однозначном разложении
на простые множители.

\smallskip

{\bf Теорема о факториальности кольца многочленов.} \\ {\it
Каждый многочлен из кольца $\k[x_1,\dots, x_n]$, отличный от константы,
разлагается в произведение неприводимых многочленов, причем это разложение
единственно с точностью до порядка множителей и ассоциированности.}

\smallskip

В случае кольца многочленов от одной переменной доказательство этой теоремы
полностью аналогично доказательству соответствующей теоремы для целых чисел
(последнюю называют основной теоремой арифметики). Здесь используется алгоритм
Евклида, из которого выводят

\smallskip

{\bf Лемма о линейном представлении наибольшего общего делителя (НОД).}
\ \ {\it Пусть $f(x), \ g(x) \in \k[x]$ и $d(x)=\mbox{НОД}(f(x), g(x))$.
Тогда существуют многочлены $u(x)$ и $v(x)$, такие что
$f(x)u(x)+g(x)v(x)=d(x)$.}

\smallskip

а затем

\smallskip

{\bf Основная лемма.} \ \ {\it Если $f(x)g(x)$ делится на неприводимый
многочлен $p(x)$, то либо $f(x)$ делится на $p(x)$, либо $g(x)$
делится на $p(x)$.}

\smallskip

Детали доказательства мы оставляем читателю. Для многочленов от многих
переменных доказательство факториальности сложнее. Оно приведено
в Главе~\ref{proofs}.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\section[Системы уравнений над $\R$ и $\C$]%
{Системы уравнений над вещественными и комплексными числами}


Между нелинейными системами над $\R$ и над $\C$ имеются
принципиальные различия.
Это связано с тем, что поле $\C$ алгебраически замкнуто.

\bde{Поле $\k$ называется
{\it алгебраически замкнутым},
если всякий непостоянный многочлен с коэффициентами из поля
$\k$ имеет корень в поле $\k$.

В противном случае говорят, что поле
{\it алгебраически незамкнуто}.}

\bza{}{Доказать, что если поле $\k$ алгебраически замкнуто,
то каждый многочлен степени $N$ с коэффициентами из $\k$
имеет в $\k$ ровно $N$ корней (с учетом кратностей).}\label{z7}

Поле $\R$ алгебраически незамкнуто, так как многочлен $x^2+1$
не имеет вещественных корней.

\smallskip

{\bf Основная теорема алгебры.}\ \ {\it Каждый непостоянный
многочлен с комплексными коэффициентами имеет комплексный
корень.}

\smallskip

Следовательно, поле $\C$ алгебраически замкнуто.




\bza{*}{Являются ли алгебраически замкнутыми следующие поля:
1) $\Q$; 2) $\Z_p=\{\ov 0,\ov 1,\dots,\ov{p-1}\}$
--- поле вычетов по простому модулю $p$;
3) $\C(t)=\{{f\over g}\mid f,g\in\C[t],\ g\not\equiv 0\}$
--- поле рациональных дробей над $\C$ ?}\label{z8}

\bpr{Всякая конечная система уравнений над $\R$ эквивалентна
системе из одного уравнения.}\label{1pr19}

{\bf Доказательство.} Система
$$
\cases{P_1(x_1,\dots,x_n)=0,\cr
       P_2(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       P_m(x_1,\dots,x_n)=0\cr}
$$
эквивалентна уравнению
$$P_1^2(x_1,\dots,x_n)+P_2^2(x_1,\dots,x_n)+\dots +P_m^2(x_1,\dots,x_n)=0\qedh$$

\bza{**}{Доказать данное предложение для произвольного
алгебраически незамкнутого поля.}\label{z9}

На практике данное предложение не очень полезно, так как решить полученное
уравнение, как правило, труднее, чем решить систему.
Однако предложение \ref{1pr19} представляет определенный теоретический
интерес.

Покажем, что над полем $\C$ предложение \ref{1pr19} неверно.

\ble{Над полем $\C$ система
$$
\cases{x=0\cr
       y=0\cr}
$$
не эквивалентна никакому уравнению.}\label{1le21}

{\bf Доказательство.} Пусть уравнение $P(x,y)=0$
имеет решение $x=0$, $y=0$. Покажем, что тогда оно имеет
и другие решения. Пусть
$$  P(x,y)=b_0(y)+b_1(y)x+\dots+b_m(y)x^m,  $$
где $b_i(y)$ --- многочлены от $y$ и $b_m(y)\not\equiv 0$.
Тогда существует такое $y_0\ne 0$, что $b_m(y_0)\ne 0$.
По основной теореме алгебры уравнение
$$  b_m(y_0)x^m+\dots+b_1(y_0)x+b_0(y_0)=0  $$
от одной переменной $x$ имеет некоторый корень $x_0$.
Значит, уравнение $P(x,y)=0$ имеет ненулевое решение $(x_0,y_0)$.
Лемма доказана.\qedv

\bza{}{а) Привести пример многочлена от одной неизвестной с целыми
коэффициентами, который не имеет рациональных корней и имеет ровно три
действительных корня.


б) Привести пример системы уравнений с целыми коэффициентами от двух
неизвестных, которая несовместна над $\Q$, имеет ровно три решения
над $\R$ и бесконечно много решений над $\C$.}\label{z10}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\chapter[САУ и их идеалы]
{Системы уравнений и идеалы в кольцах многочленов}


\section{Понятие идеала}

В этом параграфе мы напомним некоторые сведения из теории колец.
Пусть $R$ --- коммутативное ассоциативное кольцо с единицей 1.

\bde{Непустое подмножество $I$ кольца $R$ называется {\it идеалом} в $R$
(записывается $I\ide R$), если
\begin{itemize}
\item[1)] $\forall a,b\in I\quad a-b\in I$;
\item[2)] $\forall a\in I,\ \forall c\in R\quad ac\in I$.
\end{itemize}}

\bex{В кольце целых чисел $\Z$ множество $n\Z$ целых чисел, которые
делятся на фиксированное целое число $n$, составляет идеал.
При $n=2$ имеем идеал четных чисел, при $n=1$ --- все кольцо $\Z$,
а при $n=0$ --- один элемент 0.}

\bpr{В кольце $\Z$ всякий идеал имеет вид $n\Z$, $n=0,1,2,\dots$.}\label{2pr3}

{\bf Доказательство.} Пусть $I$ --- ненулевой идеал в $\Z$ и $a\in I$
--- наименьшее натуральное число в $I$ (объясните, почему такое существует).
Из определения идеала следует $a\Z\subseteq I$ (проверьте).
Пусть $b\in I$, но $b\notin a\Z$. По теореме о делении с остатком
существуют такие $q$ и $r$, что $b=aq+r$ и $0<r<a$.
Но $r=b-aq\in I$ --- противоречие с минимальностью $a$.
Итак, $I=a\Z$. Предложение доказано.\qedv

\bza{}{Пусть $I\ide R$. Доказать, что $I=R\Llra 1\in I$.}


\bza{}{(Основная теорема сельского хозяйства) Доказать, что в поле нет
нетривиальных идеалов.}\label{z11}

\bza{}{Проверьте, что множество $(a)=\{ar\mid r\in R\}$
есть идеал кольца $R$ для всякого фиксированного $a\in R$.}

\bde{Идеал $I$ кольца $R$ называется {\it главным}, если существует
такой элемент $a\in I$, что $I=(a)$.
Элемент $a$ называется {\it порождающим} (или {\it образующим})
для идеала $I$.}

Например, идеал $n\Z\ide\Z$ -- главный и $n\Z=(n)=(-n)$.

\bex{В кольце многочленов от двух неизвестных $\k[x,y]$
множество многочленов, свободный член которых равен нулю,
образует идеал $I_0$, и этот идеал не является главным.
Действительно, если $I_0=(f)$, $f\in \k[x,y]$,
то, поскольку $x\in I_0$, $f$ есть либо ненулевая константа
(и тогда $I_0=\k[x,y]$ --- противоречие), либо
$f=\alpha x$, $\alpha\in \k$, $\alpha\ne 0$.
Но $y\in I_0$, и потому $f$ делит $y$ ---
противоречие.}\label{2ex7}

\bde{Кольцо $R$ называется {\it кольцом главных идеалов},
если каждый идеал в $R$ является главным.}

Кольцо $\Z$ является кольцом главных идеалов (предложение \ref{2pr3}),
а кольцо $\k[x,y]$ --- нет (пример \ref{2ex7}).

Понятие главного идеала можно обобщить следующим образом.
Пусть $a_1,a_2,\dots,a_k$ --- произвольные элементы
кольца $R$.

\bza{}{Доказать, что множество
$$ (a_1,a_2,\dots,a_k)=\{a_1r_1+a_2r_2+\dots+a_kr_k\mid
   r_1,r_2,\dots,r_k\in R\}\subseteq R   $$
есть идеал кольца $R$.}

\bde{Элементы $a_1,\dots,a_k$ составляют {\it базис} идеала
$I=(a_1,a_2,\dots,a_k)$. Говорят, что идеал $I\ide R$
{\it допускает конечный базис}, если в нем найдутся такие элементы
$a_1,a_2,\dots,a_k$, что $I=
(a_1,a_2,\dots,a_k)$.}

Заметим, что в определении базиса идеала (в отличие от определения
базиса векторного пространства) нет
требования минимальности на число элементов базиса. Например, добавляя к
базису произвольный элемент идеала, мы вновь получаем базис того
же идеала.

\bza{}{Доказать, что
$(a_1,a_2,\dots,a_k,a)=(a_1,a_2,\dots,a_k)$ для любого
$a\in(a_1,a_2,\dots,a_k)$.}


\bza{}{Доказать, что в кольце $\Z$ идеал (5,13) совпадает со всем
кольцом $\Z$. Более общо,
$(a_1,a_2,\dots,a_k)=(\mbox{НОД}(a_1,a_2,\\ \dots,a_k))$.}\label{z12}


\bza{}{Доказать, что в кольце $\k[x,y]$ идеал $I_0$
(см. пример \ref{2ex7}) совпадает с идеалом $(x, y)$.}

\bza{}{Доказать, что $(f_1)=(f_2)$ тогда и только тогда, когда
многочлены $f_1$ и $f_2$ отличаются на ненулевую константу.}\label{zn1}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%







\section[Теорема Гильберта о базисе]{Идеалы в кольцах многочленов
\protect\\ Теорема Гильберта о базисе}

В этом параграфе мы более подробно рассмотрим идеалы и
их базисы в кольце многочленов.

\bpr{Кольцо $\k[x]$ есть кольцо главных идеалов для любого поля $\k$.}
\label{2pr13}

Доказательство по сути повторяет доказательство предложения \ref{2pr3}
(воспользоваться теоремой о делении с остатком для многочленов).

\bza{}{Найти образующую идеала в $\R[x]$, состоящего из всех
многочленов, обращающихся в ноль в точках $x=0$, $x=1$ и $x=2$.}\label{z13}

\bza{*}{Доказать, что кольцо $\Z[x]$ не является кольцом
главных идеалов.}\label{z14}


Как уже указывалось, кольца многочленов от многих
переменных не являются кольцами главных идеалов. Тем не менее
для них справедлива следующая фундаментальная теорема,
доказанная Давидом Гильбертом на рубеже XIX и XX веков:

\smallskip

{\bf Теорема Гильберта о базисе.}\ \ {\it Каждый идеал \linebreak
$I\ide\k[x_1,\dots, x_n]$ допускает конечный базис,
т.е. найдутся такие
$f_1(x_1,\dots,x_n)$, \dots, $f_k(x_1,\dots,x_n)\in I$,
что $$I=\{f_1r_1+\dots+f_kr_k\mid r_1,\dots,r_k\in \k[x_1,\dots,x_n]\}.$$}

\smallskip

Доказательство приведено в Главе~\ref{proofs}.


\bza{*}{Рассмотрим в кольце $\k[x,y]$ идеалы:
\begin{itemize}
\item[1)] $I_1=\{\sum_{i,j}a_{ij}x^iy^j\mid a_{ij}\in \R,\ i+j\ge 17\}$;
\item[2)] $I_2=(y,x^2,yx^3,y^2x^4,y^3x^5,\dots)$
(самостоятельно определите идеал, порожденный бесконечным
множеством элементов!)\label{z15}
\end{itemize}
Найти конечные базисы в этих идеалах.}

\bza{*}{Найти конечный базис в идеале
$$  I_3=\{f(x,y,z,t)\in\R[x,y,z,t]\mid f(a,a,a,a)=0\ \forall a\in
\k\},$$ где $\k$ -- произвольное бесконечное поле.}\label{z16}

\bza{}{Найти четыре различных базиса в идеале
$$  (x,y,z)\ide \k[x,y,z].  $$}\label{z17}

\bza{}{Доказать, что для любого множества $M$ многочленов от $n$ переменных
в нем найдется конечное подмножество $m_1,\dots, m_k$ такое, что каждый
многочлен $m\in M$ может быть представлен в виде $m=m_1r_1+\dots+m_kr_k$,
где $r_i$ -- некоторые многочлены.} \label{z18}

\bza{}{Привести пример кольца $R$  и идеала $I\ide R$, таких что $I$
не обладает конечным базисом.} \label{z191}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Идеал системы}

Со всякой САУ
$$
\cases{P_1(x_1,\dots,x_n)=0,\cr
       P_2(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr}
$$
мы можем связать идеал $I$, порожденный многочленами, отвечающими уравнениям
системы :
$$I=(P_1(x_1,\dots,x_n),P_2(x_1,\dots,x_n),\dots).$$
Если систему (\ref{sys1}) обозначить для краткости буквой $S$,
то соответствующий идеал будет обозначаться $I(S)$.

\ble{Если $F\in I(S)$, то
$F(x^0_1,\dots,x^0_n)=0$
для всякого решения $(x^0_1,\dots,x^0_n)$ системы $S$.}\label{2le19}

{\bf Доказательство.}
$F\in I(S)\Llra F=r_1P_1+\dots+r_mP_m$,
откуда
$$
\begin{array}{l}
F(x^0_1,\dots,x^0_n)
=r_1(x^0_1,\dots,x^0_n)P_1(x^0_1,\dots,x^0_n)+
\dots \\ +r_m(x^0_1,\dots,x^0_n)P_m(x^0_1,\dots,x^0_n)
=r_1(x^0_1,\dots,x^0_n)\cdot 0+\dots\\ +r_m(x^0_1,\dots,x^0_n)\cdot 0=0.\qedh
\end{array}
$$

\bpr{Пусть $\{P_1,\dots,P_m\}$ и $\{\ov P_1,\dots,\ov P_k\}$
--- два базиса одного идеала $I$. Тогда системы

$$
\cases{P_1(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       P_m(x_1,\dots,x_n)=0\cr}
\quad (*)
\refstepcounter{refer}\label{sys*}
\qquad\mbox{и}\qquad
\cases{\ov P_1(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       \ov P_k(x_1,\dots,x_n)=0\cr}
\quad (**)
\refstepcounter{refer}\label{sys**}
$$
эквивалентны.}\label{aabb}

{\bf Доказательство.}
Пусть
$(x^0_1,\dots,x^0_n)$
--- решение системы (*).
Покажем, что оно является решением системы (**).
Поскольку $\ov P_i\in(P_1,\dots,P_m)$ по условию,
из леммы \ref{2le19} следует, что
$\ov P_i(x^0_1,\dots,x^0_n)=0$.
Аналогично, каждое решение (**) является решением (*).\qedv

{\bf Вывод.} Множество решений системы однозначно
определяется идеалом системы. Различные базисы одного идеала
отвечают эквивалентным системам.

\bco{Каждая система алгебраических уравнений
эквивалентна конечной системе.}\label{2co21}

{\bf Доказательство.} Из теоремы Гильберта о базисе следует,
что во всяком идеале $I\ide\k[x_1,\dots,x_n]$
можно выбрать конечный базис.\qedv

На самом деле, анализируя доказательство теоремы Гильберта
о базисе, можно доказать, что всякая бесконечная система
$$
\cases{P_1(x_1,\dots,x_n)=0,\cr
       P_2(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr}
$$
эквивалентна системе
$$
\cases{P_1(x_1,\dots,x_n)=0,\cr
       P_2(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       P_N(x_1,\dots,x_n)=0,\cr}
$$
а уравнения $P_{N+1}(x_1,\dots,x_n)=0$, $P_{N+2}(x_1,\dots,x_n)=0$, \dots
на множество решений системы не влияют.

Следствие \ref{2co21} позволяет нам в дальнейшем рассматривать
только конечные системы.

\bco{Всякая САУ от одного неизвестного эквивалентна
системе из одного уравнения.}\label{2co22}

{\bf Доказательство.} Следует из предложения \ref{2pr13}.\qedv

\bza{}{а) Доказать следствие \ref{2co22} непосредственно,
используя понятие наибольшего общего делителя многочленов;

б) Какому уравнению эквивалентна система:
$$
\cases{x^4+x^3-x-1=0,\cr
       x^3+2x^2+2x+1=0,\cr
       x^6+x^5+x^2+2x+1=0\cr} \ \ \ \ ?
$$}\label{z19}


Может показаться, что если системы $S_1$ и $S_2$ эквивалентны, то
$I(S_1)=I(S_2)$.
Эту гипотезу легко опровергнуть.

\bex{Уравнения $x=0$ и $x^2=0$ эквивалентны, тогда как идеалы
$(x^2)$ и $(x)$ не совпадают.}

\bza{}{Привести пример эквивалентных систем $S_1$ и $S_2$ таких, что
$I(S_1)\not\subset I(S_2)$ и $I(S_2)\not\subset I(S_1)$.}\label{z20}

Можно ли, имея лишь идеалы $I(S_1)$ и $I(S_2)$, выяснить, эквивалентны
ли системы $S_1$ и $S_2$ (разумеется, не решая самих систем)?
Например, над полем $\R$ уравнения
$x^2+y^2-2xy+1=0$ и $x^4+y^4+2=0$
эквивалентны (не имеют решений),
но связи между идеалами
$(x^2+y^2-2xy+1)$ и $(x^4+y^4+2)$ не видно.

Для алгебраически замкнутых полей
Гильберт получил очень красивый
ответ на интересующий нас вопрос.
Формулировке (но не доказательству) этого ответа мы посвятим
следующую главу.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%








\chapter[Теорема Гильберта о нулях]{Понятие аффинного алгебраического
многообразия и формулировка теоремы Гильберта о нулях}

\section[Определения и примеры]{Определение и примеры аффинных \protect\\
алгебраических многообразий}

Неформально говоря,
аффинные алгебраические многообразия ---
это множества решений систем алгебраических уравнений.
Несмотря на кажущуюся простоту определения,
объект это весьма сложный. Для его изучения за последние два века
в математике сформировалась специальная дисциплина --- алгебраическая
геометрия --- одна из самых высоконаучных, самых разработанных
и самых трудных дисциплин. В нашем курсе мы лишь коснемся этого предмета.

На самом деле определение алгебраического многообразия весьма
технично, но мы ограничимся следующей наивной точкой зрения.

\smallskip

Пусть $\A^n$ --- это $n$-мерное пространство над полем $\k$.

\smallskip

\bde{Подмножество $X$ в $\A^n$ называется
{\it аффинным алгебраическим многообразием},
если найдется такая система $S$:
$$
\cases{f_1(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       f_m(x_1,\dots,x_n)=0,\cr}
$$
что $\ov x\in X\Llra \ov x$ --- решение системы $S$.}

Множество решений системы $S$ обозначим через $X(S)$.
Для идеала $I\ide \k[x_1,\dots,x_n]$ определим
подмножество $X(I)$ в $\A^n$ как множество точек, в которых все
многочлены из идеала $I$ равны нулю.

Ясно, что две системы $S_1$ и $S_2$ эквивалентны $\Llra$
$X(S_1)=X(S_2)$.
Поэтому эквивалентные системы определяют
одно и то же многообразие, а неэквивалентные системы ---
различные многообразия.

Ясно также, что $X(S)=X(I(S))$.

\bza{}{Задать уравнениями в $\C^3$ множество, состоящее из трех точек
$(1,2,3), \ (4,5,6)$ и $(7,8,9)$.}\label{z22}




\bza{}{Доказать, что аффинными многообразиями

\noindent{\bf являются:}

а) произвольный конечный набор точек на прямой $\A^1$;

б) произвольный конечный набор точек в $\A^n$;

в) произвольное подпространство в $\A^n$;

г) произвольный конечный набор подпространств в $\A^n$;

д) всякая парабола на плоскости;

\noindent{\bf не являются:}

е) подмножество целых чисел на прямой $\R^1$;

ж) множество $\{(x,y)\mid y=\sin x\}\subseteq \R^2$.}\label{z23}

\bza{}{Доказать, что а) пересечение; б) объединение
двух аффинных многообразий в $\A^n$ является
аффинным многообразием.}\label{z24}


\bex{Множество точек $\{(t,t^2,t^3)\mid t\in\k\}\subseteq \A^3$
является аффинным многообразием, его задает система
$$
\cases{y=x^2\cr
       z=x^3.\cr}
$$
Соответствующий идеал $I=(x^2-y,x^3-z)\ide\k[x,y,z]$.}

Как уже указывалось, совсем несхожие идеалы могут задавать
совпадающие многообразия. В то же время для всякого многообразия
$X$ есть наибольший идеал $J(X)$, задающий это многообразие и
содержащий все остальные задающие его идеалы.
А именно,
$$  J(X)=\{P\in\k[x_1,\dots,x_n]\mid P(\ov x)=0\ \
   \forall \ov x\in X\}.   $$

\bza{}{Проверить, что $J(X)$ --- идеал.}

Например, для точки ноль в $\A^2$ идеал $J$ есть $(x, y)$, а для оси $Ox$
в $\A^2$ идеал $J$ есть $(y)$.


Идеал $J(X(S))$ может не совпадать с идеалом системы, но обязательно его
содержит. Так множество нулей идеала $(x^2)\ide\k[x]$
есть одна точка $\{0\}$, $J(\{0\})=(x)$ и $(x^2)\subset(x)$.


\bza{}{Найти $J(X)$, где $X=$

а) $\{2,3,4,5\}\subseteq\A^1$;

б) $\{x=y=z\}\subseteq\A^3$;

в) $\{(x,y)\mid x^4=y^2\}\subseteq\A^2$;

г) $\{(x,y)\mid x^2-2xy+y^2=0\}\subseteq\A^2$.}\label{z25}


\bza{**}{а) Рассмотрим кривую $X$ в $\C^3$, заданную параметрически
$x=t^3, \ \ y=t^4, \ \ z=t^5, \ \  t\in\C$. Доказать, что идеал $J(X)$
не может быть порожден двумя элементами.

б) Задать указанную кривую системой из трех уравнений.}\label{z26}


\bpr{Системы $S_1$ и $S_2$ эквивалентны
тогда и только тогда, когда $J(X(S_1))=J(X(S_2))$.}\label{3pr7}

{\bf Доказательство.}  Системы $S_1$ и $S_2$ эквивалентны \
$\Llra$ \ $X(S_1)=X(S_2) \Llra
J(X(S_1))=J(X(S_2))$.\qedv

\bza{}{Доказать эти эквивалентности.}

\noindent Предложение \ref{3pr7} пока представляется бесполезным
с практической точки зрения, так как неясно, как находить идеал
$J(X(S))$.

Над полем $\C$ идеал $J(X(S))$ можно описать более конструктивно.
В этом и состоит теорема Гильберта о нулях.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\section{Радикал идеала}

Пусть $I\ide \k[x_1,x_2,\dots,x_n]$ --- произвольный идеал.

\bde{{\it Радикалом} идеала $I$ называется множество
$$  r(I)=\{f\in\k[x_1,\dots,x_n]\mid\exists s\in\N:\ f^s\in I\}.  $$}

\bpr{\begin{itemize}
\item[1)] $I\subseteq r(I)$;
\item[2)] $r(I)$ --- идеал в $\k[x_1,\dots,x_n]$;
\item[3)] $X(I)=X(r(I))$.
\end{itemize}}

{\bf Доказательство.}  1) Для всякого $f\in I$ возьмем $s=1$.

2) Нужно проверить два свойства из определения идеала:

(1) $f_1,f_2\in r(I) \Lra f_1-f_2\in r(I)$.
Нам известно, что $\exists s_1,s_2\in \N$:
$f_1^{s_1}\in I$ и $f_2^{s_2}\in I$.
Тогда
$$  (f_1-f_2)^{s_1+s_2}=\sum_{k=0}^{s_1+s_2}
C_{s_1+s_2}
    ^k(-1)^{s_1+s_2-k}f_1^kf_2^{s_1+s_2-k}  $$
(формула бинома Ньютона).
При $k\ge s_1$
$f_1^k=f_1^{s_1}\cdot f_1^{k-s_1}\in I$ $\Lra$
$f_1^k\cdot C^k_{s_1+s_2}(-1)^k f_2^{s_1+s_2-k}\in I$.
При $k<s_1$ имеем
$s_1+s_2-k> s_2$ $\Lra$ $f_2^{s_1+s_2-k}\in I$ $\Lra$
$f_2^{s_1+s_2-k}\cdot C^k_{s_1+s_2}(-1)^{s_1+s_2-k} f_1^k\in I$.
Итак, все слагаемые лежат в $I$ $\Lra$
$(f_1-f_2)^{s_1+s_2}\in I$ $\Lra$ $f_1-f_2\in r(I)$;

(2) $f_1\in r(I)$, $f_2\in\k[x_1,\dots,x_n]$ $\Lra$ $f_1f_2\in r(I)$.
Мы знаем, что $\exists s:\ f_1^s\in I$.
Но тогда $(f_1f_2)^s=f_1^sf_2^s\in I$ $\Lra$ $f_1f_2\in r(I)$.

3) Из того, что $I\subseteq r(I)$ следует, что $X(r(I))\subseteq X(I)$.
Обратно, пусть $\ov x\in X(I)$ и пусть $f(\ov x)\ne 0$
для некоторого $f\in r(I)$. Тогда
$f^s(\ov x)=(f(\ov x))^s\ne 0\ \forall s$ --- противоречие,
т.к. $\exists s:\ f^s\in I$.\qedv

\bza{}{Найти $r(I)$ для следующих идеалов $I$:

$
\begin{array}{ll}
\mbox{а) }I=(x^2)\ide\k[x]; & \mbox{в) }I=(x^2,y^3)\ide\k[x,y]; \\
\mbox{б) }I=(x,y)\ide\k[x,y]; & \mbox{г) }I=(x^2+y^2+z^2)\ide\k[x,y,z].
\end{array}
$}\label{z27}

\bza{}{Доказать, что в кольце многочленов радикал главного идеала
является главным идеалом.}\label{z28}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\section{Теорема Гильберта о нулях}

{\bf Теорема Гильберта о нулях.}\ \ Над полем комплексных чисел для каждой
системы алгебраических уравнений $S$ имеем

\medskip

\centerline{\fbox{$$ J(X(S))=r(I(S)) $$}}

\bigskip

После переформулировки на язык систем уравнений утверждение становится более
понятным: \  для системы
$$
\cases{f_1(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       f_m(x_1,\dots,x_n)=0\cr}
$$
алгебраических уравнений многочлен
$F(x_1,\dots,x_n)$ обращается в нуль на всех решениях данной
системы тогда и только тогда, когда найдутся
$r_1(x_1,\dots,x_n),\dots,r_m(x_1,\dots,x_n)$ и $s\in \N$
такие, что
\fbox{$F^s=r_1f_1+\dots+r_mf_m$}.

\medskip

(Объясните эквивалентность этих формулировок!)

\medskip

Например, к системе
$$
\cases{f_1=x+2y+4yz^2=0,\cr
       f_2=4xz^2-y=0\cr}
$$
можно добавить уравнение $x+y=0$ и множество решений не изменится, поскольку
$(x+y)^2=f_1x-f_2y$. Теорема Гильберта о нулях утверждает, что множество
решений системы не изменяет только добавление уравнений, полученных
подобным способом.

\bza{}{1) \ Показать на примере, что над полем $\R$
теорема Гильберта неверна.

2) \ Доказать, что если коэффициенты многочленов $f,f_1,\linebreak \dots,f_m$
 вещественые и при этом $f$ обращается в нуль на множестве общих нулей
 многочленов $f_1,\dots,f_m$ над $\C$, то существуют такие многочлены
$r_1,\dots,r_m$ с вещественными коэффициентами, что
$f^s=r_1f_1+\dots+r_mf_m$ для некоторого $s\in \N$.}\label{z29}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section[Применения]{Применения в теории систем\protect\\ алгебраических
уравнений над $\C$}

\bco{Системы $S_1$ и $S_2$ эквивалентны
тогда и только тогда, когда $r(I(S_1))=r(I(S_2))$.}\label{3co13}

Это следствие можно применять в конкретных задачах
уже достаточно эффективно. Оно позволяет доказывать
эквивалентность двух систем, не находя множества их решений.

\bde{Идеал $I$ называется {\it радикальным}, если $I=r(I)$.}

Следствие~\ref{3co13} показывает, что имеется естественная биекция между
радикальными идеалами кольца многочленов и классами эквивалентности систем
(т.е. аффинными алгебраическими многообразиями).

\bza{}{Доказать, что радикал произвольного идеала является радикальным
идеалом.}\label{z30}


\bpr{Пусть $f_1(x_1,\dots,x_n)$ и $f_2(x_1,\dots,x_n)$ ---
два неприводимых многочлена.
Уравнения $f_1=0$ и $f_2=0$ эквивалентны тогда и только тогда,
когда многочлены $f_1$ и $f_2$ пропорциональны.}\label{3za14}

{\bf Доказательство.} Из неприводимости $f_1$ и теоремы о
факториальности кольца многочленов следует, что если какая-то степень
многочлена $f$ делится на $f_1$, то и сам $f$ делится на $f_1$. Поэтому
$r((f_1))=(f_1)$.

Уравнения эквивалентны тогда и только тогда, когда \linebreak
$r((f_1))=r((f_2))$
$\Llra$ $(f_1)=(f_2)$. Последнее равносильно пропорциональности
многочленов (см. задачу~\ref{zn1}).\qedv

\bza{}{На примере показать, что предложение~\ref{3za14}
не может быть доказано над $\R$.}\label{z31}

\bza{}{Доказать, что над $\C$ система эквивалентна одному
уравнению тогда и только тогда, когда радикал идеала этой системы является
главным идеалом. Верно ли, что в этой ситуации идеал системы является
главным ?}\label{z32}



\bza{}{Объяснить, почему утверждения леммы \ref{1le21} и примера
\ref{2ex7} эквивалентны.}\label{z33}


\bco{Система $S$ несовместна $\Llra$ $1\in I(S)$.}\label{3co16}

{\bf Доказательство. } $\Lla$ Если $1\in I(S)$, то к системе
можно добавить уравнение $1=0$, которое не имеет решений.

$\Lra$ Если $S$ несовместна, то $X(S)=\emptyset$. В соответствии между
аффинными многообразиями и радикальными идеалами пустому множеству отвечает
идеал, совпадающий со всем кольцом многочленов (почему ?),
откуда
$J(X(S))=r(I(S))=\C[x_1,\dots,x_n]$.
Поэтому $1\in r(I(S))$, т.е.
$\exists s:\ 1^s\in I(S)\Lra 1\in I(S)$.\qedv

Заметим, что в условиях следствия \ref{3co16}
$I(S)=\C[x_1,\dots,x_n]$.

\bex{Система
$$
\cases{x^2+xy-y+1=0,\cr
 x^3-x^2+x+y^3=0,\cr
 y^4+x^3+yx^3+x-1=0\cr}
$$
несовместна.}

Действительно, если обозначить уравнения
$f_1=0$, $f_2=0$ и $f_3=0$ соответственно, то
$xf_1+yf_2-f_3=1=0$ --- противоречие.\qedv

Следствие \ref{3co16} показывает, что уравнение "1=0"
как следствие системы является единственной причиной
несовместности системы над $\C$.
Над полем $\R$ это не так.

При изучении на 1-ом курсе поля комплексных чисел
студентам достаточно трудно объяснить, зачем такое
поле рассматривать и почему надо полагать именно $i^2=-1$.
Хочется надеяться, что после изучения основной теоремы алгебры и
теоремы Гильберта о нулях те достоинства, которыми обладают
комплексные числа по сравнению с действительными,
станут более понятными.

С другой стороны, системы с действительными коэффициентами очень важны
в приложениях. Исследованию специфики систем алгебраических уравнений
с действительными коэффициентами посвящено много работ, см. например
обзор в разделе 3.2 книги~\cite{3}.

В следующей главе мы вернемся к многочленам
над произвольным полем. В идеале системы $I(S)$ будет
построен некоторый замечательный базис --- базис Гребнера.
В главе 5 мы укажем ряд алгоритмов, позволяющих решать многие
(но не \linebreak все !) системы алгебраических уравнений.
При этом теоретические результаты настоящей главы
окажутся весьма полезными.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter{Базис Гребнера идеала}

\section[Лексикографический порядок]{Лексикографический порядок\protect\\
на множестве одночленов}

Для нахождения базиса Гребнера идеала $I\ide\k[x_1,\dots,x_n]$
нам потребуется определить для многочлена
$P(x_1,\dots,x_n)$ понятие старшего члена.

Ясно, что старший член многочлена $3x^5-x+2$ есть одночлен $3x^5$.
А как выделить старший член у многочлена от многих переменных,
например у $x^2y+y^2x+z^5$?
Имеется несколько способов однозначного определения
старшего члена многочлена. Здесь мы рассмотрим только один такой способ,
называемый {\it лексикографическим}.

\bde{Многочлен, состоящий из одного члена
$P=ax_1^{k_1}x_2^{k_2}\dots x_n^{k_n}$, $a\in\k$,
называют {\it одночленом} или {\it мономом}.

Старшим членом многочлена
$
P=\sum a_{i_1\dots i_n}x_1^{i_1}\dots x_n^{i_n}
$
будет один из его одночленов $a_{i_1\dots i_n}x_1^{i_1}\dots x_n^{i_n}$.
Каждому такому одночлену можно сопоставить набор
$(i_1,\dots,i_n)$
целых неотрицательных
чисел,
который называют {\it набором степеней}.}

Например, при $n=5$ одночлену $\sqrt 2 x_2^3x_4$ отвечает набор (0,3,0,1,0),
а одночлену $3x_1^5x_4x_5^3$ --- набор (5,0,0,1,3),

\bde{Будем говорить, что
набор $(i_1,\dots,i_n)$ {\it больше}
набора $(j_1,\dots,j_n)$, если $\exists k\le n$
такое, что $i_1=j_1$, $i_2=j_2$, \dots, $i_{k-1}=j_{k-1}$,
$i_k>j_k$.}

Например, при $n=4$
$$(2,3,0,7)<(4,0,0,0)\
\ (k=1)\quad\mbox{и}\quad(3,1,5,2)>(3,1,5,1)\ \ (k=4). $$ Ясно,
что указанным способом можно сравнить любые два различных набора
одной длины.

\bza{}{а) Конечно ли число наборов, меньших данного набора
$(i_1,i_2,\dots,i_n)$ ?

б)* Пусть $A_1$, $A_2$, \dots --- наборы целых неотрицательных чисел
длины $n$. Доказать, что не существует бесконечной цепочки $A_1>A_2>\dots$.}
\label{4za3}

{\bf Замечание.} Этот способ упорядочения наборов называют еще
{\it чисто лексикографическим}. Рассматривают также
{\it однородный лексикографический} порядок: у двух наборов
$(i_1,\dots,i_n)$ и $(j_1,\dots,j_n)$ вначале сравнивают степени
$\sum_{t=1}^n i_t$ и $\sum_{t=1}^n j_t$ и только в случае их
совпадения наборы сравнивают лексикографически.
При таком упорядочении решение задачи \ref{4za3} сильно
упрощается.  Однако достоинства чисто лексикографического
порядка мы увидим в главе 5. В главах 4-5 упорядочение всюду считается
чисто лексикографическим.

\bde{{\it Старшим членом} многочлена
$$P(x_1,\dots,x_n)=\sum a_{i_1\dots i_n}x_1^{i_1}\dots x_n^{i_n}$$
называется ненулевой одночлен
$a_{i_1^0\dots i_n^0}x_1^{i^0_1}\dots x_n^{i^0_n}$,
такой что набор
$(i_1^0,\dots, i_n^0)$
больше всякого другого набора степеней, встречающегося в $P(x_1,\dots,x_n)$.}

Например, старший член многочлена $3x_1+x_2^2x_3^4+x_4^7$
есть $3x_1$ (это может показаться странным!), а старший член
многочлена $x^2y+y^2x+z^5$ есть $x^2y$
(здесь мы нумеруем $x_1=x$, $x_2=y$, $x_3=z$).

\smallskip

{\bf Лемма о старшем члене.}\ \ Старший член произведения многочленов
$P_1\cdot P_2$ есть произведение старших членов $P_1$ и $P_2$.

\smallskip

Доказательство немедленно следует из того факта, что если
$(i_1,\dots, i_n)<(l_1,\dots, l_n)$ и $(j_1,\dots, j_n)\le(k_1,\dots, k_n)$,
то \linebreak $(i_1+j_1,\dots, i_n+j_n)<(l_1+k_1,\dots, l_n+k_n)$.

\medskip

{\bf Творческая задача.} Предложить несколько других
способов упорядочения одночленов, для которых справедлива
лемма о старшем члене. (Мы приведем примеры таких
упорядочений в главе 7.)




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Многогранник Ньютона многочлена}

Со времен Ньютона в математике известна следующая замечательная
геометрическая интерпретация наборов степеней многочлена от
многих переменных.

Рассмотрим многочлен
$$P(x,y)=3xy+x^2y^3-5x^3y^2-x^4y+2x^4y^2-x^5y^2$$
и отметим на плоскости $\R^2$ наборы степеней его одночленов:
(1,1); (2,3); (3,2); (4,1); (4,2); (5,2).
Получен конечный набор точек с целыми координатами.
Их выпуклая оболочка есть выпуклый многоугольник (см. рисунок).

\vspace{0.7cm}

\begin{picture}(60,40)
\put(80,-5){\vector(0,1){50}}
\put(75,0){\vector(1,0){70}}
\put(110,30){$N(P)$}
\put(81,45){$y$}
\put(145,1){$x$}
\multiput(90,-0.5)(10,0){6}{\line(0,1){1}}
\multiput(79.5,10)(0,10){4}{\line(1,0){1}}
\put(90,10){\circle*{2}}
\put(100,30){\circle*{2}}
\put(110,20){\circle*{2}}
\put(120,10){\circle*{2}}
\put(120,20){\circle*{2}}
\put(130,20){\circle*{2}}
\put(90,10){\line(1,2){10}}
\put(90,10){\line(1,0){30}}
\put(130,20){\line(-1,-1){10}}
\put(130,20){\line(-3,1){30}}
\end{picture}

\bigskip

\noindent Его обозначают $N(P)$ и называют {\it многогранником
(многоугольником) Ньютона}
многочлена $P$ (если $P$ есть многочлен от $n$ переменных,
$N(P)$ есть выпуклый многогранник в пространстве $\R^n$).
Оказывается, многие свойства многочлена $P$ можно узнать
только по многограннику $N(P)$
(попробуйте указать примеры таких свойств).


\hangindent=-9.3cm \hangafter=-5
\begin{picture}(0,0)
\put(220,-45){\begin{picture}(60,40)%
\put(0,-5){\vector(0,1){50}}
\put(-5,0){\vector(1,0){70}}
\put(1,45){$y$}
\put(65,1){$x$}
\multiput(10,-0.5)(10,0){6}{\line(0,1){1}}
\multiput(-0.5,10)(0,10){4}{\line(1,0){1}}
\put(10,10){\circle*{2}}
\put(10,40){\circle*{2}}
\put(30,10){\circle*{2}}
\put(30,40){\circle*{2}}
\put(40,30){\circle*{2}}
\put(10,10){\line(0,1){30}}
\put(10,10){\line(1,0){20}}
\put(40,30){\line(-1,-2){10}}
\put(40,30){\line(-1,1){10}}
\put(10,40){\line(1,0){20}}
\end{picture}}
\end{picture}
\bza{}{\ \ а) Найти набор степеней \\
старшего члена многочлена,
многоугольник \\ Ньютона которого указан
на рисунке.

б) Что представляет собой многогранник Ньютона
для многочлена от одной переменной?

\pagebreak

в) Найти число вершин, число ребер и число граней многогранника
Ньютона многочлена
$$
x^4+2y^4+3z^4-xyz+2x^3y^3-xz+y^2z^2-5.
$$
}\label{4za5}

\medskip

\bde{ {\it Суммой Минковского} двух подмножеств $P_1$ и $P_2$ арифметического
пространства называется подмножество
$$
P_1+P_2=\{p_1+p_2 \mid p_1\in P_1, p_2\in P_2 \}.
$$}

\medskip

\bpr{Для любых многочленов $f,\ g\in\k[x_1,\dots,x_n]$ имеет
место равенство $N(fg)=N(f)+N(g)$.}

\medskip

{\bf Замечание.}\ Указанное свойство аналогично свойству степени
многочлена из леммы о старшем члене. Можно сказать, что многогранник Ньютона
является "обобщенной степенью" многочлена.

\medskip

{\bf Доказательство.}\
Пусть $w$ -- произвольная
линейная функция на пространстве $\R^n$. Для произвольного выпуклого
многогранника $P$ будем называть подмножество
$$
P^w=\{p\in P \mid w(p)\le w(p') \ \ \forall \ \ p'\in P\}
$$
гранью многогранника $P$, отвечающей функции $w$. (Легко видеть, что это
определение соответствует нашему интуитивному пониманию того, что такое
грань.)

\medskip

\bza{}{Доказать, что сумма Минковского двух выпуклых многогранников является
выпуклым многограннииком.
Доказать, что $(P_1+P_2)^w=P_1^w+P_2^w$ для любых выпуклых многогранников
$P_1$ и $P_2$. В частности, для любой вершины $v$ многогранника $P_1+P_2$
однозначно определены вершины $v_1$ и $v_2$ многогранников $P_1$ и $P_2$
соответственно, для которых $v=v_1+v_2$. Показать на примере, что сумма двух
вершин не всегда является вершиной.}


\medskip

Многогранник $N(fg)$ -- это выпуклая оболочка точек \linebreak
$v_1+v_2$, где $v_1$
пробегает наборы степеней $f$, а $v_2$ -- наборы степеней $g$ (почему ?).
Но все эти точки лежат в $N(f)+N(g)$, причем среди них есть все вершины
многогранника $N(f)+N(g)$. \qedv

\medskip

Ряд интересных свойств многогранников Ньютона, а также обобщение этого
понятия с одного многочлена на полиномиальный идеал можно найти в книге
Б.~Штурмфельса~\cite{6}.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Задача вхождения}

Вернемся к идеалам в кольцах многочленов.
Как выяснить, принадлежит ли многочлен $h(x)$ главному идеалу $(f(x))$?
Да очень просто, нужно делить многочлен $h(x)$ на $f(x)$
"в столбик" и если разделится без остатка, то $h(x)\in(f(x))$,
иначе $h(x)\not\in(f(x))$.

\bza{}{Принадлежит ли $x^2+2$ идеалу $(x^3+x+1)$?}

Аналогичная задача часто возникает и для многочленов от нескольких
переменных, но здесь ее решение существенно сложнее.

\smallskip

{\bf Задача вхождения.} Пусть идеал
$I\ide\k[x_1,\dots,x_n]$ задан своим базисом $I=(f_1,\dots,f_m)$.
Требуется найти алгоритм, позволяющий за конечное число шагов
выяснить, принадлежит ли данный многочлен
$h(x_1,\dots,x_n)$
идеалу $I$, т.е. существуют ли такие многочлены
$r_1(x_1,\dots,x_n)$, \dots, $r_m(x_1,\dots,x_n)$,
что $h=f_1r_1+\dots+f_mr_m$.

\smallskip

\bex{Принадлежит ли многочлен
$h=x_2x_3^2x_4-x_1x_3x_4^2$
идеалу $(x_1+x_2,x_3+x_4)\ide\k[x_1,x_2,x_3,x_4]$?}

{\bf Ответ.} Да, $h=(x_1+x_2)x_3^2x_4-(x_3+x_4)x_1x_3x_4$.

Здесь мы использовали подбор. Этот
метод не поможет при более громоздких выражениях для $h$ и $f_i$.

\bza{}{Доказать, что
$x+y^2x+3xy^3\not\in (x^2,y)\ide\k[x,y]$.}\label{4za8}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\section[Определение базиса Гребнера]{Определение
базиса Гребнера\protect\\ и решение задачи вхождения}

После некоторых раздумий можно найти следующий метод
упрощения выражения для $h$ в задаче вхождения.

Зафиксируем обозначения. Для всякого многочлена $P$ имеем
$P=P_C+P_M$, где $P_C$ --- старший член $P$, а $P_M$ ---
сумма остальных членов.
Например, для $P=2x^2+xy^3-4z^2$ $P_C=2x^2$, $P_M=xy^3-4z^2$.

\medskip

{\bf Операция редукции.} Предположим, что старший член многочлена $h$
делится на старший член некоторого из многочленов $f_i$,
т.е. $h_C=f_{iC}Q$, где $Q$ --- одночлен.
Тогда положим $h_1=h-Qf_i=Q(-f_{iM})+h_M$.
При этом старший член $h_1$ меньше старшего члена $h$.

\medskip

\ble{$h\in(f_1,\dots,f_m)\Llra
h_1\in(f_1,\dots,f_m).$}

{\bf Доказательство.} Достаточно проверить, что разность $h-h_1$
принадлежит $(f_1,\dots,f_m)$.  Имеем
$h-h_1=Qf_i\in(f_1,\dots,f_m)$. \qedv

Итак, задачу вхождения теперь можно решать не для $h$, а для $h_1$
и здесь вновь можно применять редукцию (возможно, с другим $f_i$).
Если за конечное число редукций многочлен $h$ сведется
(редуцируется) к нулю, то $h\in(f_1,\dots,f_m)$, т.к.
нуль принадлежит любому идеалу.

\medskip

\bex{$h=x_2x_3^2x_4-x_1x_3x_4^2$,
$f_1=x_1+x_2$, $f_2=x_3+x_4$.
Моном $h_C=-x_1x_3x_4^2$ делится на $f_{1C}=x_1$ $(Q=-x_3x_4^2)$

\medskip

{\bf Редукция 1.}\ \
$h\to x_2x_3^2x_4+x_2x_3x_4^2=h_1$.  Здесь
$h_{1C}=x_2x_3^2x_4$ делится на $f_{2C}=x_3$ $(Q=x_2x_3x_4)$.

\medskip

{\bf Редукция 2.}\ \ $h_1\to x_2x_4^3+x_2x_3x_4^2=h_2$ (редукция произведена дважды).
Здесь $h_{2C}=x_2x_3x_4^2$
делится на $f_{2C}=x_3$ $(Q=x_2x_4^2)$.

\medskip

{\bf Редукция 3.}\ \ $h_2\to x_2x_4^3-x_2x_4^3= 0$.

\medskip

Итак, $h\in (f_1,f_2)$.}

\pagebreak

А как быть, если $h$ не редуцируется к нулю, т.е. на
некотором этапе возникает многочлен, старший член которого
не делится ни на один из одночленов $f_{1C}$, $f_{2C}$, \dots, $f_{mC}$?
Можно ли утверждать, что $h$ не принадлежит идеалу ?

Как это часто бывает в математике, если мы не можем сказать
ничего конкретного, мы фиксируем желаемое в определении.

\bde{Базис $f_1,\dots,f_m$ идеала $I=(f_1,\dots,f_m)$
называется {\it базисом Гребнера} этого идеала,
если всякий многочлен $h\in I$ редуцируется к нулю при помощи
$f_1,\dots,f_m$,}\label{4de11}

или

\smallskip

\noindent{\bf Определение \ref{4de11}.1}\ \
Набор многочленов $f_1,\dots,f_m$ --- {\it базис Гребнера} в
$I=(f_1,\dots,f_m)$, если для любого $h\in I$ одночлен $h_C$
делится на один из одночленов $f_{1C},f_{2C},\dots,f_{mC}$.

\smallskip

\bza{}{a) \ Доказать эквивалентность этих определений.

б) \ Пусть $f_1,\dots,f_m$ --- базис Гребнера идеала $I$.
Доказать, что если $h\in I$, то $h$ редуцируется к нулю
произвольной применимой к нему последовательностью редукций.}\label{4za12}

\bza{}{ Пусть $f_1,\dots,f_m$ -- набор многочленов из идеала $I$, для которых
старший член $h_C$ любого элемента $h\in I$ делится на один из старших
членов $f_{iC}$. Доказать, что в этом случае многочлены $f_1,\dots,f_m$
являются базисом идеала $I$ и тем самым являются базисом Гребнера в $I$.
}\label{4za13}

\bex{Покажем, что $f_1=x$, $f_2=y$ есть базис Гребнера в идеале
$(x,y)\ide\k[x,y]$. Пусть $h(x,y)$ --- произвольный многочлен.
Если старший член $h$ делится на $x$, то редукция с помощью $f_1$
есть замена $x$ на 0 (обнуление старшего члена).
Если старший член делится на $y$, редукция с помощью $f_2$
также обнуляет старший член. Поэтому всякий многочлен
редуцируется к своему свободному члену.
Остается заметить, что многочлен принадлежит идеалу $(x,y)$
тогда и только тогда, когда его свободный член равен нулю.}

\bex{Рассмотрим идеал $I=(x^2-y,x^2-z)\ide\k[x,y,z]$,
$f_1=x^2-y$, $f_2=x^2-z$.
Многочлен $z-y\in I$, так как $z-y=f_1-f_2$.
С другой стороны, старший член $z-y$ не делится на старшие члены
$f_1$ и $f_2$
(они равны $x^2$).
Поэтому $f_1$ и $f_2$ не образуют базис Гребнера идеала $I$.
Ниже мы докажем, что $f_1$, $f_2$ и $f_3=z-y$ --- базис Гребнера в $I$.}
\label{4ex15}

{\bf Решение задачи вхождения.}\ \
Предположим, что нам известен базис Гребнера идеала $I$.
Пусть дан многочлен $h$.
Будем производить всевозможные редукции
$h$ с помощью элементов базиса (любая из цепочек возможных редукций конечна).
Многочлен $h$ лежит в $I$ тогда и только тогда, когда
в результате редукций получаем нуль.

Это решение представляет собой алгоритм, который несложно
реализовать на ЭВМ и применять к задачам со сколь угодно
сложными выражениями для $f_i$ и $h$.

Заметим, что из задачи~\ref{4za13} и теоремы Гильберта о базисе вытекает
существование базиса Гребнера в любом идеале. В самом деле, рассмотрим
идеал, порожденный старшими членами элементов идеала и выберем в нем
конечный базис из числа образующих. Тогда элементы исходного идеала,
старшие члены которых
образуют базис идеала старших членов, составляют конечный базис Гребнера
исходного идеала. Однако это доказательство существования не дает
алгоритма построения базиса Гребнера идеала по некоторому
его исходному базису.
Такой алгоритм будет предъявлен в следующем параграфе.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section[Алгоритм Бухбергера]{Алгоритм Бухбергера\protect\\Бриллиантовая
лемма}

Пусть $I\ide\k[x_1,\dots,x_n]$ --- идеал и
$f_1,\dots,f_m$
 --- его базис.

\bde{Говорят, что многочлены $f_i$ и $f_j$
имеют {\it зацепление}, если их старшие члены
$f_{iC}$ и $f_{jC}$ делятся одновременно
на некоторый одночлен $w$, отличный от константы.}

Если $f_i$ и $f_j$ имеют зацепление, т.е.
$f_{iC}=wq_1$, $f_{jC}=wq_2$, где $w$ -- наибольший
общий делитель $f_{iC}$ и $f_{jC}$, то рассмотрим многочлен
$F_{i,j}=f_iq_2-f_jq_1\in I$. (Его принято называть S-многочленом
пары $f_i,f_j$ и обозначать $S(f_i,f_j)$ или $S(i,j)$.)
Редуцируем многочлен $F_{i,j}$ с помощью базиса
$f_1,\dots,f_m$ до тех пор, пока это возможно.
В результате получим нередуцируемый многочлен $\wt F_{i,j}$.
Если $\wt F_{i,j}\equiv 0$, то будем говорить, что зацепление
{\it разрешимо}. Иначе добавим
$\wt F_{i,j}$ к базису идеала $I$: $f_{m+1}=\wt F_{i,j}$.

В новом базисе $f_1,\dots,f_m,f_{m+1}$ будем вновь искать
возможные зацепления и редуцировать соответствующие многочлены $F_{i,j}$.

\bza{}{В базисе $f_1,\dots,f_m,f_{m+1}$ зацепление $(i,j)$ разрешимо.
}\label{4za17}

\bex{Рассмотрим идеал $I=(x^2-y,x^2-z)$ (Пример~\ref{4ex15}).
Здесь $f_1=x^2-y$, $f_2=x^2-z$.
Имеется зацепление $f_{1C}\:\vdots\: x^2$, $f_{2C}\:\vdots\: x^2$,
$\Lra$ $F_{1,2}=-y+z$. Положим $f_3=y-z$.
Других зацеплений нет.}\label{4ex18}

\bex{Пусть $I=(f_1=x^2+y^2+z^2,f_2=x+y-z,f_3=y+z^2)$.
Зацепление имеют только $f_1$ и $f_2$:
$$
F_{1,2}=f_1-xf_2=y^2+z^2-xy+xz=-xy+xz+y^2+z^2.
$$
Редуцируем с помощью $f_2$:
$$
-xy+xz+y^2+z^2\leadsto (y-z)y-(y-z)z+y^2+z^2=2y^2+2z^2-2yz.
$$
Редуцируем с помощью $f_3$:
$$2y^2+2z^2-2yz\leadsto
2z^4+2z^3+2z^2.$$
Дальше редуцировать нельзя $\Lra$ $f_4=2z^4+2z^3+2z^2$.
На константу можно сократить и считать, что $f_4=z^4+z^3+z^2$.
Других зацеплений нет.}\label{4ex19}

Оказывается, что и в общем случае возможно лишь конечное число
неразрешимых зацеплений.

\bth{Для каждого набора многочленов
$f_1,\dots,f_m
\in\k[x_1,\dots,x_n]$
после редуцирования конечного числа зацеплений мы получим набор
$f_1,\dots,f_m, f_{m+1},\dots,f_M$,
в котором каждое зацепление разрешимо.}
\label{4th20}

\pagebreak

\bth{(Diamond Lemma).\ \
Базис $f_1,\dots,f_m$ идеала $I$
является базисом Гребнера тогда
и только тогда, когда в нем нет зацеплений или каждое зацепление разрешимо.}
\label{4th21}

Доказательства этих теорем приведены в Главе 6.

\smallskip

Теоремы \ref{4th20} и \ref{4th21} обосновывают существование
эффективного алгоритма для построения базиса Гребнера
идеала. Этот алгоритм называется {\it алгоритмом Бухбергера}.
Повторим еще раз его этапы.
Пусть $f_1,\dots,f_m$ -- набор многочленов, являющийся базисом идеала $I$.

\begin{itemize}
\item[1)] Проверим, есть ли в наборе зацепления. Если зацеплений
нет, то набор является базисом Гребнера идеала $I$, иначе
переходим к пункту 2.


\item[2)] По найденному зацеплению $(i,j)$ многочленов $f_i$ и
$f_j$ положим $f_{iC}=wq_1$, $f_{jC}=wq_2$, и  составим
многочлен $F_{i,j}=f_iq_2-f_jq_1$.  Редуцируем многочлен
$F_{i,j}$ с помощью набора $\{f_i\}$ до тех пор, пока
это возможно. Если многочлен $F_{i,j}$ редуцировался к
ненулевому многочлену $f$, то переходим к пункту 3,
иначе к пункту 4. (Отметим, что редуцируемость многочлена $F_{i,j}$ к нулю
и вид многочлена $f$ вообще говоря зависят от выбранной нами последовательности
применяемых редукций (покажите это на примере !). В алгоритме мы используем
любую применимую последовательность редукций и, получив нередуцируемый
многочлен $f$, переходим к пункту 3, более никогда зацепление $(i,j)$
не рассматривая.)


\item[3)] Добавляем многочлен $f$ к набору $f_1,f_2,\dots,f_k$
в качестве $f_{k+1}$ и переходим к пункту 4.




\item[4)]
В построенном к настоящему моменту множестве многочленов
$\{f_i\}$ рассматриваем зацепление, которое не было рассмотрено
ранее, и переходим к пункту 2. Если все имеющиеся зацепления
ранее рассматривались, алгоритм завершен.
\end{itemize}

За конечное число шагов мы получим набор
$f_1,\dots,f_m, f_{m+1},\linebreak\dots,f_M$,
где каждое зацепление разрешимо.
Это и есть базис Гребнера идеала $I=(f_1,\dots,f_m)$
(см. примеры \ref{4ex18}, \ref{4ex19}).

\bza{}{Когда
набор многочленов $f_1(x),\dots,f_m(x)$ является базисом Гребнера порожденного
ими идеала в $\k[x]$ ?} \label{nznz}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\section[Минимальный редуцированный базис]{Минимальный
редуцированный\protect\\ базис Гребнера}

Итак, базис Гребнера идеала $I\ide\k[x_1,\dots,x_n]$ построен.
Можно ли его упростить?

\smallskip

{\bf Упрощение первое.}
Пусть $f_1$ и $f_2$ --- элементы базиса Гребнера такие, что
$f_{1C}$ делится на $f_{2C}$.
Тогда удалим элемент $f_1$ из базиса.

\bza{}{Элементы $f_2,\dots,f_m$ по-прежнему составляют
базис Гребнера идеала $I$.}\label{4za22}

\bde{Базис Гребнера
$\{f_1,\dots,f_m\}$
называется {\it минимальным}, если  $f_{iC}$ не делится на $f_{jC}$
при $i\ne j$.}

Каждый базис Гребнера можно свести к минимальному,
отбрасывая "лишние" члены. Отметим, что минимизацию можно применять к
базису идеала только если известно что этот базис является базисом Гребнера,
иначе может измениться
сам идеал $I$ (рассмотрите идеал $(x,x+y)$ !).


{\bf Упрощение второе} касается нестарших членов многочленов
$f_1,\dots,f_m$.
Предположим, что некоторый член $q$ многочлена $f_i$
делится на старший член многочлена $f_j$.
Тогда редуцируем $q$ с помощью $f_j$
и результат редукции запишем в $f_i$ на место $q$.
При этой операции базис Гребнера идеала остается
базисом Гребнера, число элементов базиса
не изменяется, но понижаются степени членов многочленов $f_1,\dots,f_m$.

\bde{Базис Гребнера
$\{f_1,\dots,f_m\}$
называется {\it редуцированным}, если ни один член многочлена $f_i$
не делится на старший член многочлена $f_j$ для всех
$i,j=1,\dots,m$, $i\ne j$.}

Каждый базис Гребнера конечной последовательностью редукций
можно свести к редуцированному базису Гребнера.
Оказывается, больше никаких упрощений произвести нельзя.
Более того, имеет место

\bth{Минимальный редуцированный базис Гребнера идеала
$I\ide\k[x_1,\dots,x_n]$
определен однозначно\footnote{Мы дополнительно предполагаем, что числовой
коэффициент при старшем члене каждого элемента нашего базиса равен единице.},
т.е. не зависит от выбора исходного базиса идеала
$I$ и от последовательности проводимых операций
(но зависит от упорядочения переменных $x_1,\dots,x_n$).}\label{4th25}

(Доказательство см. в Главе 6.)

\smallskip

\bex{Рассмотрим базис Гребнера $f_1=x^2+y^2+z^2$;
$f_2=x+y-z$; $f_3=y+z^2$; $f_4=z^4+z^3+z^2$ из примера \ref{4ex19}.
\begin{itemize}
\item[1)] {\it Минимизация:} старший член $f_1$
делится на старший член $f_2$ $\Lra$ $f_1$ можно отбросить.
\par
Минимальный базис: $\{f_2,f_3,f_4\}$.
\item[2)] {\it Редукция:} заменяем $y$ в $f_2$ на $-z^2$.
Имеем: $f_2\leadsto x-z^2-z$.
Больше редукций делать не с чем.
Итак, минимальный редуцированный базис есть
$\{x-z^2-z;y+z^2;z^4+z^3+z^2\}$.
\end{itemize}}\label{4za26}

\bza{}{Выберите какой-либо другой базис в идеале
из примера~\ref{4za26} и убедитесь, что построенный
с помощью этого базиса минимальный редуцированный базис Гребнера
совпадает с уже построенным.}

\bza{}{Укажите алгоритм, определяющий, совпадают ли идеалы $(f_1,\dots,f_k)$
и $(g_1,\dots,g_s)$ в кольце $\k[x_1,\dots,x_n]$.}\label{4za271}

С точки зрения теории систем алгебраических уравнений построение минимального
редуцированного базиса Гребнера идеала
системы состоит из двух этапов. На первом этапе,
редуцируя всевозможные зацепления, мы добавляем новые (нередуцируемые
к нулю) уравнения к исходной системе не изменяя множества ее решений
(поскольку добавленные уравнения принадлежат идеалу системы). На втором
этапе мы отбрасываем (минимизация) или "упрощаем" (редуцирование) некоторые
уравнения системы. При этом часто оказывается, что именно
исходные уравнения системы либо отброшены, либо существенно
упрощены и полученная система (а она эквивалентна исходной)
легко решается.
Однако базис Гребнера не всегда допускает упрощения, и в этом
случае мы просто увеличиваем число уравнений системы. Но и эта
процедура полезна при решении системы и, как показывают
результаты следующей главы, успех (возможно при помощи
компьютерных вычислений) во многих случаях гарантирован.

\bza{}{ Показать, что для систем линейных уравнений алгоритм Бухбергера
плюс минимизация
есть метод Гаусса приведения системы к ступенчатому виду,
а переход к редуцированному базису Гребнера равносилен обратному
ходу в методе Гаусса (выражение главных неизвестных через свободные).}

\bza{}{ Показать, что алгоритм Бухбергера плюс минимизация в случае многочленов
от одной переменной доставляют алгоритм нахождения НОДа конечного набора
многочленов.}


В этом курсе мы не станем обсуждать проблему оценки сложности алгоритма
Бухбергера. Перечислим лишь чем такая сложность
измеряется. Пусть дан идеал $I$ кольца \linebreak
$\k[x_1,\dots,x_n]$, порожденный
$k$ многочленами, степени которых не превосходят числа $d$.
При фиксированных значениях $n$, $k$ и $d$ нужно оценить:

1)\ максимально возможную степень многочлена, возникающего в минимальном
редуцированном базисе Гребнера;

2)\ число элементов минимального редуцированного базиса Гребнера;

3)\ степени и коэффициенты многочленов, возникающих в промежуточных
вычислениях;

4)\ число операций, которые необходимо произвести.

Эти характеристики будут зависить от того, какой порядок на множестве
одночленов мы выберем (общее понятие порядка будет обсуждаться в главе 7),
а также какую из модификаций алгоритма Бухбергера будем использовать.
Информацию на этот счет можно найти в книгах, указанных в конце текста,
а также в цитируемых там журнальных статьях. Следует отметить, что
в этом направлении остается еще много нерешенных задач и, видимо, еще
преждевременно говорить о том, что удовлетворительная теория здесь построена.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\section{Вычисление базисов Гребнера}

Мы предлагаем читателю использовать изложенные выше сведения в конкретных
вычислениях.
Постройте минимальный редуцированный базис Гребнера для идеалов
(во всех задачах считаем $x>y>z$ и вычисляем базис Гребнера для чисто
лексикографического порядка):


\medskip

\noindent 1) $(x^2-1,\, (x-1)y,\, (x+1)z)$;

\medskip

\noindent 2) $(x^2-1,\, (x-1)y,\, (x-1)z)$;

\medskip

\noindent 3) $(x^3yz-xz^2,\, xy^2z-xyz,\, x^2y^2-z)$;

\medskip

\noindent 4) $(x^2y+xz+y^2z,\, xz^2-zy,\, xyz-y^2)$;

\medskip

\noindent 5) $(xy^2-z-z^2,\, x^2y-y,\, y^2-z^2)$;

\medskip

\noindent 6) $(xy+x^2z,\, xz+yz^3,\, yz-y^2z^3)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\chapter[Применения базисов Гребнера]{Применение базисов
Гребнера для решения систем алгебраических уравнений}

\section{Критерий несовместности}

В этом параграфе будет указан эффективный критерий несовместности
для системы алгебраических уравнений.
Основное поле предполагается полем $\C$.

\bth{Система $S$ несовместна тогда и только тогда, когда
базис Гребнера идеала $I(S)$ содержит ненулевую константу.}

{\bf Доказательство.} Если ненулевая константа принадлежит
$I(S)$, то система несовместна. Наоборот, если $S$ несовместна,
то по следствию \ref{3co16} $1\in I(S)$.  Поэтому старший член
некоторого элемента базиса Гребнера делит 1 и потому есть
константа.\qedv

\bza{}{Выпишите некоторую (не совсем простую)
несовместную систему $S$ и вычислите
базис Гребнера идеала $I(S)$.}

\medskip

Отметим, что
в математике имеются и другие способы выяснения совместна ли данная САУ
или нет. Так широко известная в математической логике теорема
Тарского-Зайденберга об элиминации кванторов позволяет в частности
распознавать совместность систем над вещественными и комплексными числами.
Доказательство этой теоремы, основанное на "методе интервалов"
(см. раздел 3.8 книги
Н.~К.~Верещагин, А.~Шень, Языки и исчисления, М.: МЦНМО, 2000, 286 стр.),
предлагает достаточно простой (но трудоемкий !) алгоритм для
такого распознавания.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Критерий эквивалентности систем}

Поиск алгоритма для выяснения эквивалентности двух систем над комплексными
числами естественно приводит нас к алгоритмическому исследованию
радикала идеала. Начнем с алгоритма, определяющего, принадлежит
ли многочлен радикалу данного идеала.

\bza{*}{Пусть $\k$ -- произвольное поле.
Рассмотрим идеал $I=(f_1,\dots,f_m)$ кольца $\k[x_1,\dots,x_n]$.

1)\ Доказать, что многочлен $f\in \k[x_1,\dots,x_n]$
тогда и только тогда лежит в радикале идеала
$I$, когда в кольце $\k[x_1,\dots,x_n,y]$ (здесь $y$ - дополнительная
переменная) идеал $(f_1,\dots,f_m, 1-yf)$ совпадает со всем кольцом;

2)\ Указать алгоритм, определяющий, принадлежит ли многочлен $f$ радикалу
идеала $(f_1,\dots,f_m)$.}\label{5za2111}

Следствие~\ref{3co13} показывает, что две системы $S_1$ и $S_2$
эквивалентны тогда и только тогда, когда $I(S_1)\subseteq r(I(S_2))$
и $I(S_2)\subseteq r(I(S_1))$. Отсюда непосредственно следует

\bth{ Две системы над полем комплексных чисел
$$
\cases{f_1(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       f_m(x_1,\dots,x_n)=0\cr}
\quad
\qquad\mbox{и}\qquad
\cases{g_1(x_1,\dots,x_n)=0,\cr
       \quad\cdots\cdots\cdots\cr
       g_k(x_1,\dots,x_n)=0\cr}
\quad
$$
эквивалентны тогда и только тогда, когда $f_i\in r((g_1,\dots,g_k)) \linebreak
i=1,\dots, m$ и $g_j\in r((f_1,\dots,f_m)), j=1,\dots,k$
\footnote{Автор благодарен А.~Гайфуллину, обратившему его внимание на
этот результат.}.}

\medskip

\bza{}{Пусть $I=(f_1,\dots,f_m)$ и $l=a_1x_1+\dots+a_nx_n$, $a_i\in\k$.
Указать алгоритм, определяющий минимальное число $s$, для которого
$l^s\in I$, или показывающий, что $l$ не лежит
в радикале идеала $I$.}\label{5za2112}


Далее естественно рассмотреть задачу об алгоритмическом построении образующих
радикала данного идеала. Эта задача решена, однако ее решение слишком сложное для
того, чтобы обсуждать его в этом курсе. Подготовленному читателю мы
рекомендуем обратиться к статьям (Gianni P., Trager B., Zacharias G,
Gr\"obner bases and primary decomposition of polynomial ideals, in:
Computational Aspects of Commutative Algebra, ed. by Robbiano L.,
Academic Press, New York, 1988, 15-33) и (Eisenbud D., Huneke C.,
Vasconcelos W., Direct methods for primary decomposition, Invent. Math.,
110 (1992), 207-235). Было бы очень интересно отыскать простое решение
указанной задачи.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\section[Критерий конечности]{Критерий конечности числа решений системы}

Предположим, что система $S$ от неизвестных $x_1,x_2,\dots,x_n$
имеет конечное число решений.
Тогда неизвестная $x_1$ может принимать на множестве решений
только конечное число значений.
Обозначим их $\alpha_1,\alpha_2,\dots,\alpha_{N_1}$.
Многочлен $f(x_1)=(x_1-\alpha_1)(x_1-\alpha_2)\dots (x_1-\alpha_{N_1})$
обращается в ноль на множестве решений системы $S$.
По теореме Гильберта о нулях
$\exists k_1\in\N:\ f^{k_1}\in I(S)$.
Старший член многочлена $f^{k_1}$ есть $x_1^{N_1k_1}$.
По определению базиса Гребнера имеется такой элемент
$f_i$ в этом базисе, что
старший член $f_i$
делит старший член $f^{k_1}$.
Поэтому старший член $f_i$ есть степень переменной $x_1$.
Аналогично, для остальных переменных $x_2,\dots,x_n$
должны найтись элементы базиса Гребнера,
старшие члены которых являются степенями этих переменных.

Обратно, пусть
$f_1,\dots,f_n$
--- элементы базиса Гребнера идеала $I(S)$ такие, что старший член
$f_{iC}$ равен $x_i^{N_i}$.
В силу лексикографического упорядочения одночленов
(вот где существенно, что порядок чисто лексикографический !)
многочлен $f_n$ не содержит переменных $x_1,x_2,\dots,x_{n-1}$,
т.е.
$$ f_n=a_{N_n}x_n^{N_n}+a_{N_n-1}x_n^{N_n-1}+\dots+a_1x_n+a_0 $$
и $a_{N_n}\ne 0$.
Отсюда, переменная $x_n$ как корень многочлена от одной
неизвестной может принимать лишь конечное число значений.
Аналогично, многочлен $f_{n-1}$ зависит лишь от $x_n$ и $x_{n-1}$
и старший член его не равен нулю ни при каких значениях $x_n$.
Но $x_n$ принимает
лишь конечное число значений, и потому значения
$x_{n-1}$ принадлежат множеству корней конечного числа многочленов,
то есть конечному множеству.
Рассуждая аналогично, мы показываем, что переменные
$x_{n-2},x_{n-3},\dots,x_1$ могут принимать лишь конечное число значений.
Тем самым доказана

\bth{Число решений системы $S$ конечно тогда и только тогда, когда
базис Гребнера идеала $I(S)$ содержит элементы
$f_1,f_2,\dots,f_n$,
старшие члены которых являются \linebreak степенями переменных
$x_1,x_2,\dots,x_n$ соответственно.}

Заметим, что в данном критерии не требуется, чтобы старшие члены всех
элементов базиса Гребнера являлись степенями переменных.



Итак, применяя алгоритм Бухбергера к произвольной системе $S$,
мы получаем базис Гребнера и, глядя на него, можно сразу
сказать, конечно или бесконечно число решений системы.

Если мы выяснили, что система $S$
имеет решения и их конечное число, то наш алгоритм сводит
решение системы к последовательному решению конечного числа
алгебраических уравнений от одной неизвестной.
Хотя точной формулы здесь вообще говоря нет
(теорема Абеля), известно много достаточно точных численных методов
решения и потому можно использовать компьютер.


\bza{}{ Показать, что для систем линейных уравнений указанный критерий
конечности числа решений эквивалентен критерию определенности системы из
главы 1 (см. теорему~\ref{aaa}).}

\bex{Решить систему:
$$
\cases{ab=c^2+c,\cr
a^2=a+bc,\cr
ac=b^2+b.\cr}
$$
Будем считать $a>b>c$.
Занумеруем уравнения
$f_1$, $f_2$ и $f_3$.
Зацепления $f_1$ и $f_2$ дают
$$ f_1\cdot a-f_2\cdot b=(-c^2-c)a+(a+bc)b=ab-ac+b^2c-ac^2=f_4.
$$
Редукция с помощью $f_1$:  $f_4\leadsto
-ac^2-ac+b^2c+c^2+c=\ov{f_4}.$

\medskip

\noindent Редукция с помощью $f_3$:
$\ov{f_4}\leadsto
-b^2-b-bc+c^2+c=\ov{\ov{f_4}}.$

\medskip

\noindent Зацепление $f_2$ и $f_3$:
$f_2c-f_3a=ab+ab^2-ac-bc^2=f_5$.

\medskip

\noindent Редукция с помощью $f_1$:
$f_5\leadsto
-ac+cb+c^2+c=\ov{f_5}.$

\medskip

\noindent Редукция с помощью $f_3$:
$\ov{f_5}\leadsto
-b^2-b+cb+c^2+c=\ov{\ov{f_5}}.$

\medskip

\noindent Редукция с помощью $\ov{\ov{f_4}}$:
$\ov{\ov{f_5}}\leadsto
2bc=\ov{\ov{\ov{f_5}}}$

\bigskip

\noindent Зацепление $f_1$ и $f_3$:
$f_1c-f_3b=b^3+b^2-c^3-c^2=f_6$.

\medskip

\noindent Редукция с помощью $\ov{\ov{f_4}}$:
$f_6\leadsto
-b^2c+bc+bc^2-c^3-c^2=\ov{f_6}$

\pagebreak

\noindent Редукция с помощью $\ov{\ov{f_4}}$:
$\ov{f_6}\leadsto
2bc+2bc^2-2c^3-2c^2=\ov{\ov{f_6}}$


\medskip

Редуцируем ${\ov{\ov{f_6}}}$ с помощью $\ov{\ov{\ov{f_5}}}$.
Получим $-2c^3-2c^2=\ov{\ov{\ov{f_6}}}$.
Мы видим, что в базисе Гребнера лежат элементы
$a^2-a-bc$, $-b^2-b-bc+c^2+c$,
$-2c^3-2c^2$.
Отсюда следует конечность числа решений.
Найдем эти решения.
Из $-2c^3-2c^2=0$ $\Lra$ $c=0$ или $c=-1$.
\begin{itemize}
\item[1)] $c=-1$. Из $2bc=0$ $\Lra$ $b=0$.
Имеем $a^2-a-bc=0$ $\Lra$
$a^2=a$ $\Lra$ $a=0$ или $a=1$.
Наборы: $(1,0,-1)$ --- не годится, $(0,0,-1)$ --- годится.
\item[2)] $c=0$ $\Lra$ $a^2=a$ $\Lra$ $a=0$ или $a=1$,
$b^2+b=0$ $\Lra$ $b=0$ или $b=-1$.
Наборы: $(0,0,0)$ --- годится, $(0,-1,0)$ --- годится,
$(1,0,0)$ --- годится, $(1,-1,0)$ --- не годится.
\end{itemize}
{\bf Ответ.} $\{(0,0,0);\ (1,0,0);\ (0,-1,0);\ (0,0,-1)\}$.}

\bex{Решить систему:
$$
\cases{ab=c^2+c,\cr
a^2+a=bc,\cr
ac=b^2+b.\cr}\label{bbb}
$$
Зацепление $f_1$ и $f_2$: $ f_1\cdot a-f_2\cdot b=-ab-ac+b^2c-ac^2=f_4 $.

\medskip

\noindent Редукция с помощью $f_1$:
$f_4\leadsto
-ac^2-ac+b^2c-c^2-c=\ov{f_4}$

\medskip

\noindent Редукция с помощью $f_3$:
$\ov{f_4}\leadsto
-b^2-b-bc-c^2-c=\ov{\ov{f_4}}$.

\medskip

Дальнейшие вычисления показывают, что все прочие
зацепления редуцируются к нулю.

Значит, базис Гребнера состоит из 4-х элементов
$$\{f_1,f_2,f_3,\ov{\ov{f_4}}\}.$$
Отсюда следует, что переменная $c$ может принимать бесконечно
много значений.}\label{5ex3}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\section[Свободные неизвестные]{Свободные неизвестные\protect\\
Размерность множества решений}

Обратимся теперь к системам, имеющим бесконечное множество решений.
Что значит здесь решить систему?
Ведь перечислить явно бесконечно много решений невозможно.
Выход подсказывает понятие свободной неизвестной
из теории линейных систем (параграф 1.2):
для описания множества решений все переменные разделяются на
два множества --- свободные и главные.
Свободным неизвестным можно придавать любые значения,
а главные выражаются через них.
Однако в нелинейном случае на этом пути встает ряд
трудностей. Проиллюстрируем их на примере.

\bex{Рассмотрим уравнение $x^3y^2=1$. Ясно, что оно
имеет бесконечно много решений.
В то же время ни $x$ ни $y$ не может принимать все значения, т.к.
$x\ne 0$, $y\ne 0$.
Если все-таки считать $x$ свободной, $x\in\C\setminus\{0\}$,
то $y=\sqrt{1/x^3}$. Но функция $\sqrt{\ }$ над полем $\C$ определена
неоднозначно --- каждому значению $x$ отвечают два значения $y$.}

Попытаемся определить понятие свободной неизвестной для
произвольной системы с учетом указанных трудностей.

\bde{Множество $H_F\subset\C^n$ решений ненулевого уравнения
$F(x_1,\dots,x_n)=0$ называется {\it
гиперповерхностью}\footnote{Как показывает задача~\ref{z9}, над алгебраически
незамкнутым полем любое аффинное многообразие является гиперповерхностью.}.}

\bde{Подмножество $U\subset\C^n$ называется {\it алгебраически плотным}
(далее просто {\it плотным}),
если его дополнение содержится в
некоторой гиперповерхности $H_F$.}

\bza{}{1) Какие подмножества плотны в $\C$ ?

2) Привести несколько примеров плотных подмножеств \linebreak
в $\C^2$.}\label{5za10}

\bth{ Пусть $S$ --- система уравнений от неизвестных
$x_1,x_2,\dots,x_n$;
$x_{i_1},x_{i_2},\dots,x_{i_k}$ ---
некоторый набор из этих неизвестных и
$Ox_{i_1}\dots x_{i_k}$
--- соответствующее координатное
подпространство в $\C^n$.
Координатная проекция $\C^n\to Ox_{i_1}\dots x_{i_k}$
определяет отображение множества решений $X(S)$ системы $S$
на подпространство $Ox_{i_1}\dots x_{i_k}$,
и образ этого отображения либо плотен в
$Ox_{i_1}\dots x_{i_k}\cong \C^k$,
либо лежит в некоторой гиперповерхности $H_F$ в $\C^k$.}\label{5th11}

(Доказательство см. в Главе 6.)

\smallskip

В первом случае набор переменных
$x_{i_1},\dots,x_{i_k}$
называют {\it свободным} (ведь эти переменные могут принимать
почти любые наборы значений на множестве решений $X(S)$),
а во втором случае --- {\it зависимым}
(поскольку значения переменных \linebreak
$x_{i_1},\dots,x_{i_k}$ на множестве решений
лежат на гиперповерхности $F(x_{i_1},\dots, x_{i_k})=0$).

\bde{ {\it Размерностью} \ $dim\ X(S)$ множества решений
$X(S)$ системы $S$ называется максимальное число переменных по
всем свободным наборам переменных. Свободный набор переменных,
в котором число переменных равно $dim\ X(S)$, будем называть
{\it максимальным свободным набором переменных}. Если свободных переменных
нет, будем говорить, что множество решений {\it нульмерно}.}

\bza{*}{Пусть $F(x_1,\dots,x_n)$ --- ненулевой многочлен.
Доказать, что размерность множества решений уравнения \linebreak
$F=0$ равна $n-1$.
}\label{5za13}

\bza{}{Доказать, что набор из одной переменной $\{x_i\}$
является свободным для системы $S$ тогда и только тогда,
когда $x_i$ принимает бесконечно много значений
на множестве решений $X(S)$.}\label{5za14}

\bza{}{Доказать, что подмножество свободного набора переменных
вновь является свободным набором переменных.}\label{5za141}

\bza{*}{ Привести пример системы и свободного набора переменных
для этой системы, который не может быть включен в максимальный
свободный набор переменных.}\label{5za15}

\medskip

Как для данной системы эффективно находить максимальные
свободные наборы переменных и размерность множества
решений?

Здесь нам вновь помогут базисы Гребнера.
\bigskip

{\bf Алгоритм поиска} максимального свободного набора переменных:
\begin{itemize}
\item[1)] Рассмотрим лексикографический порядок:

$x_1>x_2>\dots>\widehat{x_i}>\dots>x_n>x_i$
(переменная $x_i$ переставлена в конец)
и построим для него базис Гребнера идеала $I(S)$.
Если в нем есть элемент, зависящий только от $x_i$,
то $x_i$ --- зависимая переменная, иначе --- свободная.

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

\item[2)] Перенумеровав переменные, считаем, что $x_n$ ---
свободная.  Переставляя на предпоследнее место переменные
\linebreak $x_1,\dots,x_{n-1}$, строим базисы Гребнера для
лексикографических порядков
$x_1>x_2>\dots>\widehat{x_i}>\dots>x_i>x_n$.
Если такой базис содержит элемент, зависящий лишь от
$x_i$ и $x_n$, то набор $\{x_i,x_n\}$ зависим, иначе свободен.


\item[3)] Подставляя в качестве $x_n$ последовательно все
свободные переменные и действуя как в пункте 2), находим все
свободные пары переменных.  Продолжая в том же духе, мы найдем
все свободные тройки, четверки и т.д. до максимальных наборов.
\end{itemize}

Обоснование этого алгоритма, а также возможные его оптимизации мы
оставляем читателю.

\bza{}{Доказать, что множество решений конечно
$\Llra$ множество решений нульмерно.}\label{5za16}



\bex{Вернемся к системе из примера~\ref{bbb}.
$$
\cases{ab=c^2+c,\cr
a^2+a=bc,\cr
ac=b^2+b.\cr}
$$
Для порядка $a>b>c$
мы построили базис Гребнера
$$\{f_1=ab-c^2-c,f_2=a^2+a-bc,f_3=ac-b^2-b,f_4=b^2+b+bc+c^2+c\}.$$
Отсюда следует, что переменная $c$ свободна, а набор
$\{b,c\}$ зависим.
Положим $b>a>c$. Имеем
$f_1=ab-c^2-c$, $f_2=bc-a^2-a$, $f_3=b^2+b-ac.$

\medskip

\noindent Зацепление $f_1$ и $f_2$: $f_1c-f_2a=-c^3-c^2+a^3+a^2=f_4$.

\medskip

Получена зависимость между $a$ и $c$ $\Lra$ набор $\{a,c\}$ не свободен.

\medskip

Наконец, положим $c>a>b$. Тогда из зацепления второго и третьего
уравнений системы получаем многочлен $-a^3-a^2+b^3+b^2$.
Следовательно, набор $\{a,b\}$ не свободен.


{\bf Вывод.} Множество решений имеет размерность 1.}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\section[Геометрическая структура]{Геометрическая структура
множества решений системы}

Пусть максимальный свободный набор переменных для
системы $S$ получен.  Перенумеровав переменные, можно считать,
что этот набор есть $\{x_1,x_2,\dots,x_k\}$.  Имеется проекция
\linebreak $\phi\colon X(S)\to Ox_1\dots x_k$,
образ которой мы обозначим $U$. Множество $U$ плотно в
$Ox_1\dots x_k\cong \C^k$.

Пусть $u_0=(x_1^0,\dots,x_k^0)\in U$.
Рассмотрим прообраз
$\phi^{-1}(u_0)$.
Множество точек в этом прообразе -- это множество решений нашей системы
при фиксированных значениях свободных переменных
$x_1=x_1^0,\dots,x_k=x_k^0$.

Хотелось бы думать, что прообраз
$\phi^{-1}(u_0)$ конечен.
Однако это не всегда так.

\bex{Рассмотрим уравнение $xyz=0$.
Набор $\{x,y\}$ является максимальным свободным набором переменных.
При $x\ne 0$, $y\ne 0$ переменная $z$ находится однозначно: $z=0$.
Однако если $x=0$ или $y=0$, то $z$ может принимать любые значения.
Поэтому прообраз каждой точки из координатного креста плоскости
$Oxy$ есть аффинная прямая.}\label{5ex17}

\bza{}{Найти множество $U$ в примере \ref{5ex17}.}\label{5za19}

Тем не менее, имеет место следующая теорема.

\bth{Во множестве $U$ найдется такое плотное подмножество $U_1$,
что $\phi^{-1}(u)$ конечно для всякого $u\in U_1$.}\label{5th20}

(см. доказательство в Главе 6.)

\smallskip

Так, в примере \ref{5ex17} $U_1=U\setminus\{Ox\cup Oy\}$.

Если значения свободных переменных принадлежат множеству $U_1$,
то значения остальных переменных находятся "почти однозначно".
На явные формулы для выражения
$x_{k+1},\dots,x_n$ через
$x_1,\dots,x_k$
рассчитывать не приходится, но при фиксированных значениях
$x_1,\dots,x_k$
из $U_1$ значения
$x_{k+1},\dots,x_n$ можно найти, решая конечное число
алгебраических уравнений от одной неизвестной.

Если же значения
$(x_1,\dots,x_k)\in U\setminus U_1$,
то происходят вырождения.
Здесь следует подставить значения
$x_1,\dots,x_k$
в систему и вновь начать решать полученную систему от неизвестных
$x_{k+1}$, \dots, $x_n$ рассмотренными методами.

В заключение получим точное решение системы из примера \ref{5ex3}.
Построенный базис Гребнера
$$\{f_1=ab-c^2-c,f_2=a^2+a-bc,f_3=ac-b^2-b,$$
$$f_4=b^2+b+bc+c^2+c\}$$
является минимальным, но не редуцированным. Минимальным редуцированным
базисом в этом случае является базис
$$\{f_1=ab-c^2-c, f_2=a^2+a-bc, f_3=ac+bc+c^2+c,$$
$$f_4=b^2+b+bc+c^2+c\}.$$
Поэтому исходная система
$$
\cases{ab=c^2+c,\cr
a^2+a=bc,\cr
ac=b^2+b\cr}
$$

\pagebreak

эквивалентна системе
$$
\cases{ab=c^2+c,\cr
a^2+a=bc,\cr
ac=-bc-c^2-c,\cr
b^2+b+bc+c^2+c=0.\cr}
$$

При $c=0$ имеем решения $(0, 0, 0)$, $(0, -1, 0)$ и $(-1, 0, 0)$.
При $c\ne 0$ из третьего уравнения получаем $a=-b-c-1$.
После подстановки этого выражения в первое и второе уравнения получаем
уравнения, эквивалентные четвертому. Переменная $c$ является
свободной, переменная $b$ выражается из четвертого уравнения $$
  b=\frac{-c-1\pm\sqrt{-3c^2-2c+1}}{2},
$$
а для переменной $a$ имеем
$$
  a=\frac{-c-1\mp\sqrt{-3c^2-2c+1}}{2}.
$$
Окончательно получаем ответ:

1) $c$ -- любое комплексное число,
  $b=\frac{-c-1\pm\sqrt{-3c^2-2c+1}}{2}$ и
  $a=\frac{-c-1\mp\sqrt{-3c^2-2c+1}}{2}$;

2) $a=b=c=0$.

Отсюда следует, что $U=U_1=O_c$, то есть свободная переменная может
принимать любые значения, при фиксированном значении $c\ne 0$
система имеет два решения, а при $c=0$ система имеет три
решения.

\medskip

{\bf Замечание.}\ Множество решений уравнения $xyz=0$ есть объединение
трех плоскостей. Ряд приведенных в этой главе примеров был основан
именно на том, что множество решений системы есть объединение конечного
числа подобных "частей", каждая из которых является решением системы,
полученной из исходной добавлением дополнительных уравнений.
В алгебраической геометрии эти "части" называют {\it неприводимыми
компонентами} множества решений и предпочитают изучать каждую из
компонент отдельно. Подробное изучение понятия неприводимой компоненты
выходит за рамки настоящего курса. Заинтересованному читателю следует
обратиться к учебникам по алгебраической геометрии,
см. например И.~Р.~Шафаревич, Основы алгебраической геометрии, том~1,
М.: Наука, 1988.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Решение систем}

Решите следующие системы (это можно сделать, не применяя понятие
базиса Гребнера, однако мы рекомендуем именно этот путь в качестве
тренировки). В каждом из случаев продемонстрируйте применение
критериев совместности, конечности числа решений
и понятие свободной переменной,
найдите размерность множества решений.

\bigskip

1)
$$
\cases{x^2=1,\cr
(x-1)y=0,\cr
(x+1)z=0.\cr}
$$

\bigskip

2)
$$
\cases{x^2+y^2+z^2=0,\cr
x+y-z=0,\cr
y+z^2=0.\cr}
$$


\bigskip

3)
$$
\cases{xz-2y+1=0,\cr
yz-1+z=0,\cr
yz+xyz+z=0.\cr}
$$

\bigskip

4)
$$
\cases{x^3yz-xz^2=0,\cr
xy^2z-xyz=0,\cr
x^2y^2-z=0.\cr}
$$

\bigskip

5)
$$
\cases{xy^2-z-z^2=0,\cr
x^2y-y=0,\cr
y^2-z^2=0.\cr}
$$

\bigskip

6)
$$
\cases{xy+z-1=0,\cr
x-y-z^2=0,\cr
x^2-2y+1=0.\cr}
$$

\bigskip
7)
$$
\cases{zx-y-x+xy=0,\cr
yz-z+x^2+yx^2=0,\cr
x-x^2+y=0.\cr}
$$

\bigskip

8)
$$
\cases{xy-xz+y^2=0,\cr
yz-x^2+x^2y=0,\cr
x-xy+y=0.\cr}
$$

\bigskip

9)
$$
\cases{yz+x^2+z=0,\cr
xyz+xz-y^3=0,\cr
xz+y^2=0.\cr}
$$

\bigskip

10)
$$
\cases{x^2+z^2y+yz=0,\cr
y^2-zx+x=0,\cr
xy+z^2-1=0.\cr}
$$

\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter{Доказательства}\label{proofs}

\section[К главе 1]{К главе 1}

{\bf Доказательство теоремы о факториальности кольца многочленов
от многих переменных.}

\medskip

Проведем индукцию по числу переменных. Для кольца многочленов
от одной переменной факториальность доказана выше. Считаем, что
кольцо $\k[x_1,\dots, x_{n-1}]$ факториально. Рассмотрим многочлен
$f(x_1,\dots, x_n)$ как многочлен от переменной $x_n$ с коэффициентами
в кольце $\k[x_1,\dots, x_{n-1}]$, т.е.
$$
f(x_n)=f_0(x_1,\dots, x_{n-1})+f_1(x_1,\dots,
x_{n-1})x_n+\dots$$
$$+f_m(x_1,\dots,x_{n-1})x_n^m.
$$

\smallskip

\bde{{\it Содержанием} многочлена $f$ называется многочлен
$Cont(f)=\mbox{НОД}(f_0(x_1,\dots, x_{n-1}),\dots, f_m(x_0,\dots,
x_{n-1})).$}

\smallskip

{\bf Лемма Гаусса.} \ \ $Cont(fg)=Cont(f)Cont(g).$

\smallskip

{\bf Доказательство.} Ясно, что $Cont(fg)$ делится на \linebreak
$Cont(f)Cont(g)$.
Сократив на общий множитель, будем считать, что $Cont(f)=Cont(g)=1$.
Пусть $p$ -- неприводимый делитель $Cont(fg)$. Допустим,
что $p$ делит $f_0,\dots, f_s$ и $g_0,\dots, g_r$, но не делит
$f_{s+1}$ и $g_{r+1}$. Тогда в $fg$ коэффициент при $x_n^{s+r+2}$ делится
на $p$, все входящие в него члены делятся на $p$, и потому $f_{s+1}g_{r+1}$
делится на $p$. В силу неприводимости $p$ один из сомножителей делится на $p$.
Противоречие. \qedv

\smallskip

Рассмотрим поле рациональных дробей
$$
 D=\{ \frac{f(x_1,\dots, x_{n-1})}{g(x_1,\dots, x_{n-1})} \mid g\ne 0\}.
$$
Многочлен $f$ можно рассматривать как многочлен от $x_n$ над
полем $D$. Утверждается, что если $f$ неприводим в $\k[x_1,\dots, x_n]$,
то он неприводим и в $D[x_n]$. Действительно, если $f=gh$ -- разложение
в $D[x_n]$, то, приведя к общему знаменателю коэффициенты,
получим $qf=g'h'$, где
$g'$, $h'$ -- многочлены из $\k[x_1,\dots, x_n]$ тех же степеней по $x_n$, что
и $g$, $h$. Сократив на $Cont(g')Cont(h')$, получим $r'f'=g''h''$. По лемме
Гаусса $r'$ есть константа. Поэтому $f'$, а следовательно и $f$,
приводимы в $\k[x_1,\dots, x_n]$.

Проведенное рассуждение показывет, что разложение на неприводимые множители в
$D[x_n]$ определяет разложение на неприводимые множители в $\k[x_1,\dots,
x_n]$. Однозначность разложения вытекает из однозначности разложения
в $D[x_n]$ и \linebreak в $\k[x_1,\dots, x_{n-1}]$. \qedv



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section[К главе 2]{К главе 2}

{\bf Доказательство теоремы Гильберта о базисе.}

\medskip

Рассмотренное ниже доказательство принадлежит Гордану (1900). Оно было
получено почти сразу после оригинального доказательства Гильберта.
Для нас оно интересно тем, что в нем (впервые ?) возникло понятие
идеала старших членов и идеи, близкие к понятию базиса Гребнера.

\bigskip

{\bf Этап 1.}\ Пусть $I\ide\k[x_1,\dots, x_n]$ -- идеал, порожденный
(бесконечным) множеством одночленов $m_1, m_2, \dots$.

\smallskip

{\bf Лемма Диксона.}\ {\it В идеале $I$ можно выбрать базис из конечного числа
одночленов $m_1, m_2,\dots, m_k$.
Другими словами, любое множество одночленов
содержит конечное число минимальных элементов относительно отношения
делимости. Эти элементы составляют наименьший
мономиальный базис идеала $I$.}

\smallskip

{\bf Доказательство.}\ Будем использовать индукцию по числу переменных.
В случае, когда $n=1$, базис состоит из одного одночлена наименьшей степени.
В случае $n$ переменных подставим во все одночлены $x_n=1$ и в полученной
совокупности одночленов от $n-1$ переменной выберем минимальный базис
$m_1',\dots,m_s'$. Рассмотрим одночлены $m_1,\dots, m_s$, отвечающие
$m_i'$, с наименьшими показателями при $x_n$. Пусть $l$ есть наибольший
показатель при $x_n$ в одночленах $m_1,\dots, m_s$. Рассмотрим все
одночлены из $I$ степени $p$ относительно $x_n$, $p=0,1,\dots, l-1$. Подставим
в них $x_n=1$ и в полученном множестве выберем вновь минимальные
одночлены $m_1^{(p)},\dots, m_{s_p}^{(p)}$. В конечном
множестве одночленов $m_1,\dots, m_s,\dots, m_i^{(p)}x_n^p\dots$
остается выбрать минимальные элементы относительно отношения делимости.\qedv

\bigskip

\begin{picture}(195,150)

\put(30,0){\vector(0,1){150}}
\put(10,30){\vector(1,0){195}}

\put(135,30){\circle*{5}}
\put(90,45){\circle*{5}}
\put(75,75){\circle*{5}}
\put(60,105){\circle*{5}}

\thicklines
\put(135,30){\line(-3,1){45}}
\put(90,45){\line(-1,2){15}}
\put(75,75){\line(-1,2){15}}
\put(60,105){\line(0,1){30}}

\linethickness{0.0001mm}
\multiput(60,105)(5,-10){7}{\line(1,0){85}}
\put(113,37){\line(1,0){65}}
\put(60,115){\line(1,0){80}}
\put(60,125){\line(1,0){75}}

\put(135,15){$x^7$}
\put(60,45){$x^4y$}
\put(45,75){$x^3y^3$}
\put(35,105){$x^2y^5$}
\end{picture}

\bigskip

\bigskip

Эта лемма допускает следующую геометрическую интерпретацию. Будем
сопоставлять одночлену точку решетки $\Z^n$ -- набор степеней одночлена.
Тогда одночлены из наименьшего мономиального базиса отвечают точкам,
попавшим на конечную часть ломанной -- границы выпуклой оболочки всех
одночленов идеала.

\bigskip

{\bf Этап 2.}\ Общий случай. Рассмотрим лексикографический порядок на
множестве одночленов. Пусть $J$ -- идеал, порожденный старшими членами
$f_C$ элементов $f$ идеала $I$. Выберем конечный базис $m_1,\dots, m_k$
в идеале $J$. Пусть $f_i$ -- многочлены из идеала $I$,
старшие члены которых равны $m_i$. Покажем, что $f_i$ образуют базис
в $I$. Для произвольного элемента $f\in I$ его старший член
$f_C=m_ir$ для некоторого номера $i$ и одночлена $r$. Тогда старший
член $f-f_ir$ строго меньше старшего члена $f$. За конечное число
мы получим $f\in (f_1,\dots, f_k)$. \qedv

\bigskip

Другое доказательство этой теоремы основано на рассмотрении
кольца $\k[x_1,\dots, x_n]$ как кольца многочленов от $x_n$
с коэфициентами в $\k[x_1,\dots, x_{n-1}]$. Можно показать, что
старшие члены многочленов из идеала $I$ образуют идеал $P$ \linebreak
в $\k[x_1,\dots, x_{n-1}]$. По предположению индукции $P$
имеет конечный базис. Это позволяет построить конечный базис в $I$.
Детали мы оставляем читателю.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section[К главе 3]{К главе 3}

{\bf Доказательство теоремы Гильберта о нулях.}

\medskip

Удачное доказательство этой теоремы содержится в книге В.~В.~Прасолова
"Многочлены". Для полноты изложения мы приведем здесь это доказательство.
Помимо собственно доказательства в процессе рассуждений
читатель познакомится с такими полезными в алгебре фактами как лемма Нетер
о нормализации, характеристическое свойство максимальных идеалов и прочее.

Сначала мы докажем частный случай теоремы о нулях, из которого затем выведем
общую теорему. Далее кольцо \linebreak $\C[x_1,\dots,x_n]$ будем обозначать
буквой $K$.

\medskip

{\bf Предложение 1. }\ {\it Пусть многочлены $f_1,\dots,f_m\in K$
не имеют общих нулей. Тогда существуют такие многочлены
$g_1,\dots,g_m\in K$, что
$$
g_1f_1+\dots+g_mf_m=1.
$$}

\medskip

{\bf Доказательство.}\ \ Предположим, что таких многочленов не существует.
Это в точности означает что идеал $(f_1,\dots,f_m)$ не совпадает со всем
кольцом $K$.

\bigskip

ШАГ 1. \ Пусть $J$ - максимальный (собственный) идеал кольца $K$,
содержащий $(f_1,\dots,f_m)$. Тогда кольцо $A=K/J$ является полем.

В самом деле, достаточно проверить, что в кольце $K/J$ любой ненулевой элемент
обратим. Если $f\notin J$, то $J+(f)$ -- идеал, строго содержащий $J$,
поэтому $J+(f)=K$. Это показывает, что найдутся такие многочлены
$a\in J$ и $b\in K$, что $a+bf=1$. В таком случае класс
$\overline{b}\in A$ является обратным для класса $\overline{f}\in A$.

Пусть $\alpha_i$ -- образ элемента $x_i$ при канонической проекции
$$
 p: \ \C[x_1,\dots,x_n]\to \C[x_1,\dots,x_n]/J=A.
$$
Таким образом, $A=\C[\alpha_1,\dots,\alpha_n]$ -- конечно порожденная
алгебра над $\C$, являющаяся в то же время полем.

\bigskip

ШАГ 2. \ Если конечно порожденная алгебра над $\C$ является полем,
то она совпадает с $\C$.

Для доказательства этого утверждения нам понадобится\footnote{
В доказательстве можно было бы обойтись и без леммы Нетер (см. например
В.~Доценко, Об одном доказательстве теоремы Гильберта о нулях,
Мат. Просвещение, третья серия, вып. {\bf 6} (2002), 116-118),
но мы решили познакомить читателя с этим результатом.}

\medskip

{\bf Лемма Нетер о нормализации.} \ {\it В алгебре \linebreak
$A=\C[\alpha_1,\dots,\alpha_n]$
можно выбрать алгебраически независимые над $\C$ элементы
$y_1,\dots,y_k$ так, что любой элемент $a\in A$ будет {\it целым}
над $\C[y_1,\dots,y_k]$, т.е.
будет удовлетворять
нормированному алгебраическому уравнению над $\C[y_1,\dots,y_k]:$
$$
  a^l+b_1a^{l-1}+\dots+b_l=0, \ \ \mbox{где} \ \
  b_1,\dots,b_l\in \C[y_1,\dots,y_k].
$$}

\medskip

{\bf Доказательство.} \ Применим индукцию по $n$. Если элементы
$\alpha_1,\dots,\alpha_n$ алгебраически независимы, то утверждение
очевидно. Пусть $f(\alpha_1,\dots,\alpha_n)=0$ -- алгебраическое соотношение
между ними. Если $f$ -- многочлен степени $m$, у которого коэффициент при
$x_n^m$ не равен нулю, то
$$
  \alpha_n^m+b_1\alpha_n^{m-1}+\dots+b_m=0, \ \ \ \
   b_1,\dots,b_m\in \C[\alpha_1,\dots,\alpha_{n-1}].
$$
Это показывает, что $\alpha_n$ цел над $\C[\alpha_1,\dots,\alpha_{n-1}]$.
По предположению индукции мы можем выбрать искомые элементы  \linebreak
$y_1,\dots,y_k$ для кольца $\C[\alpha_1,\dots,\alpha_{n-1}]$. Теперь
тот факт, что всякий элемент из $\C[\alpha_1,\dots,\alpha_n]$ цел
над $\C[y_1,\dots,y_k]$ вытекает из следующих стандартных свойств
целых элементов, проверку которых мы оставляем читателю:

\medskip

(I) \ если элемент $a\in \C[\alpha_1,\dots,\alpha_n]$ цел над
$\C[\alpha_1,\dots,\alpha_{n-1}]$, то $a$ цел и над $\C[y_1,\dots,y_k]$;

\medskip

(II) \ если $a_1, a_2\in \C[\alpha_1,\dots,\alpha_n]$ целы над
       $\C[\alpha_1,\dots,\alpha_{n-1}]$,
       то элементы $a_1+a_2$ и $a_1a_2$ также целы над
       $\C[\alpha_1,\dots,\alpha_{n-1}]$.

\medskip

Если же коэффициент при $x_n^m$ в многочлене $f$ равен нулю, то сделаем замену
$x_n=\xi_n, \ x_i=\xi_i+a_i\xi_n, \ i=1,\dots,n-1$. Попробуем подобрать
числа $a_i\in \C$ так, чтобы у многочлена
$$
 g(\xi_1,\dots,\xi_{n-1},\xi_n)=f(x_1,\dots,x_n)=$$
$$ =f(\xi_1+a_1\xi_n,\dots,\xi_{n-1}+a_{n-1}\xi_n,\xi_n)
$$
был ненулевой коэффициент при $\xi_n^m$. Этот коэффициент равен
$$
  g_m(0,\dots,0,1)=f_m(a_1,\dots,a_{n-1},1),
$$
где $f_m$ и $g_m$ -- однородные составляющие старшей степени
многочленов $f$ и $g$. Ясно, что ненулевой однородный многочлен
$f_m(x_1,\dots,x_n)$ не может быть тождественно равен нулю при $x_n=1$.
\qedv

Вернемся к доказательству того, что поле $A$ совпадает с $\C$.
Выберем элементы $y_1,\dots,y_k$, о которых идет речь в лемме Нетер.
Покажем, что в таком случае в алгебре $B=\C[y_1,\dots,y_k]$ любой
ненулевой элемент $x$ обратим. По условию $A$ -- поле, поэтому
$x$ обратим в $A$. Кроме того, согласно лемме Нетер элемент $x^{-1}$
удовлетворяет уравнению
$$
  (x^{-1})^l+b_1(x^{-1})^{l-1}+\dots+b_l=0, \ \ \ b_1,\dots,b_l\in B.
$$
Умножив обе части этого уравнения на $x^{l-1}$, получим
$$
 x^{-1}=-b_1-b_2x-\dots-b_lx^{l-1}\in B.
$$

Но $B$ есть кольцо многочленов над полем $\C$. Обратимыми элементами
в нем являются только константы. Поэтому $B=\C$. Любой
элемент из $A$ является корнем нормированного многочлена с коэффициентами
в $B$. Следовательно, $A=\C$.

\bigskip

ШАГ 3. \ Многочлены $f_1,\dots,f_m$ обращаются в нуль в точке
$$
 (\alpha_1,\dots,\alpha_n)\in \C^n.
$$

В самом деле, при канонической проекции
$$
 p:\ \C[x_1,\dots,x_n] \to \C[x_1,\dots,x_n]/J=A=\C
$$
элементы $x_i$ переходят в $\alpha_i$, а многочлены $f_1,\dots,f_m$,
принадлежащие идеалу $J$, переходят в нуль.

Итак, предположив, что $(f_1,\dots,f_m)\ne \C[x_1,\dots,x_n]$,
мы показали, что у многочленов $f_1,\dots,f_m$ есть общий корень.
Предложение~1 доказано. \qedv

Докажем теперь теорему Гильберта о нулях: если многочлен $F(x_1,\dots,x_n)$
обращается в нуль на всех общих решениях уравнений $f_1=0$, \dots
$f_m=0$, то найдется $s\in \N$, для которого $F^s\in (f_1,\dots,f_m)$.
Для $F=0$ утверждение очевидно, поэтому будем считать, что $F\ne 0$.
Добавим к переменным $x_1,\dots,x_n$ новую переменную $x_{n+1}=z$ и рассмотрим
многочлены $f_1,\dots,f_m,1-zF$. У них нет общих нулей, поэтому
$$
 1=h_1f_1+\dots+h_mf_m+h(1-zF),
$$
где $h_1,\dots,h_m,h$ -- некоторые многочлены от переменных \linebreak
$x_1,\dots,x_n,z$. Положим $z=1/F$. После приведения к общему знаменателю
получим
$$
  F^s=r_1f_1+\dots+r_mf_m,
$$
где $r_1,\dots,r_m$ -- многочлены от $x_1,\dots,x_n$. Это соотношение
имеет требуемый вид. \qedv


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section[К главе 4]{К главе 4}

{\bf Доказательство теоремы~\ref{4th20}.}

\medskip

Будем рассуждать от противного. Пусть при редуцировании многочленов $F_{i,j}$
возникает бесконечно много нередуцируемых многочленов. Рассмотрим идеал,
порожденный их старшими членами. По теореме Гильберта о базисе в нем можно
выбрать конечный базис из числа образующих. Тогда у любого
последующего многочлена старший член делится на старший член одного из
"базисных" многочленов и, следовательно, этот многочлен можно редуцировать.
Полученной противоречие завершает доказательство. \qedv

\bigskip

{\bf Доказательство теоремы~\ref{4th21}.}

\medskip

Если $\{f_1,\dots,f_m\}$ является базисом Гребнера, то каждый многочлен
$F_{i,j}$ редуцируется к нулю, поскольку по определению он лежит в идеале
$I$. Следовательно, любое зацепление разрешимо.

Для доказательства обратной импликации уточним используемые обозначения.
Пусть $f=ax^{\alpha}+\dots$ и $g=bx^{\beta}+\dots$, где
$ax^{\alpha}=ax_1^{\alpha_1}\dots x_n^{\alpha_n}$ есть старший член многочлена
$f$ и $bx^{\beta}=bx_1^{\beta_1}\dots x_n^{\beta_n}$ есть старший член
многочлена $g$. Обозначим через $x^{\gamma}$ наименьшее общее кратное
одночленов $x^{\alpha}$ и $x^{\beta}$. Напомним, что
$S(f,g)=\frac{x^{\gamma}}{ax^{\alpha}}f-\frac{x^{\gamma}}{bx^{\beta}}g$
(эти обозначения здесь удобнее чем индексные обозначения $F_{i,j}$).
Доказательство будет использовать следующую лемму.

\medskip

{\bf Лемма 1.} \ {\it Пусть $f_1,\dots,f_s$ -- многочлены с одним и тем же
старшим членом $x^{\alpha}$. Тогда если старший член многочлена
$f=\sum \lambda_if_i$ строго меньше чем
$x^{\alpha}$, то $f=\sum_{i<j} \nu_{i,j} S(f_i,f_j)$
(здесь $\lambda_i$  и $\nu_{i,j}$ -- числа).}

\medskip

{\bf Доказательство.}\ По условию $f_i=a_ix^{\alpha}+\dots$ и
$f_j=a_jx^{\alpha}+\dots$, поэтому $S(f_i,f_j)=\frac{f_i}{a_i}-\frac{f_j}{a_j}$.
Ясно также, что
$$
f=\sum \lambda_if_i=\lambda_1a_1(\frac{f_1}{a_1}-\frac{f_2}{a_2})+
(\lambda_1a_1+\lambda_2a_2)(\frac{f_2}{a_2}-\frac{f_3}{a_3})+\dots
$$
$$
\dots+(\lambda_1a_1+\dots+\lambda_{s-1}a_{s-1})
(\frac{f_{s-1}}{a_{s-1}}-\frac{f_s}{a_s})+
(\lambda_1a_1+\dots+\lambda_sa_s)\frac{f_s}{a_s}.
$$
Однако по условию $\lambda_1a_1+\dots+\lambda_sa_s=0$. \qedv

\medskip

Вернемся к доказательству теоремы. Нам достаточно показать, что любой многочлен
$f\in I$ представим в виде $f=\sum h_if_i$, где старший член $f$ совпадает с
наибольшим из старших членов многочленов $h_if_i$.
Будем рассуждать от противного. Пусть $f=\sum h_if_i$ -- запись $f$, для которой
наибольший из старших членов многочленов $h_if_i$ является наименьшим
возможным,
однако этот старший член все равно больше старшего члена многочлена $f$.
Перепишем данное представление как $f=\sum_{i=1}^t (h_{iC}f_i+h_{iM}f_i)
+\sum_{i=t+1}^m h_if_i$, где многочлены $h_{iC}f_i$, $i=1,\dots,t$ -- это
в точности члены представления, старший член которых является наибольшим.
По предположению старшие члены в сумме $F=\sum_{i=1}^t h_{iC}f_i$ взаимно
уничтожаются. По лемме 1 имеем представление
$F=\sum_{i<j} \nu_{i,j} S(h_{iC}f_i, h_{jC}f_j)$. Однако $h_{iC}$ -- одночлены,
поэтому $S(h_{iC}f_i, h_{jC}f_j)$ делится на
$S(f_i,f_j)$. Редуцируемость к нулю
многочленов $S(f_i,f_j)$ с помощью набора $\{f_i\}$ обеспечивает нам
представление каждого из $S(f_i,f_j)$ в виде комбинации $\sum g_lf_l$,
для которых старший член многочлена $S(f_i,f_j)$ совпадает с наибольшим
из старших членов многочленов $g_lf_l$. Подставляя полученные комбинации
в выражения для $F$ и $f$, получим представление $f$ в виде комбинации
$\sum d_sf_s$, у которой наибольший из старших членов многочленов $d_sf_s$
меньше, чем у исходной комбинации. Требуемое противоречие получено.

Остается объяснить, почему не нужно рассматривать S-многочлены для тех пар
$f_i, f_j$, которые не имеют зацепления. Мы докажем, что если старшие члены
многочленов $f$ и $g$ взаимно просты, то $S(f,g)$ редуцируется к нулю
при помощи многочленов $f$ и $g$. Для этого достаточно доказать,
что $f$ и $g$ образуют базис Гребнера идеала $(f,g)$, или что
старший член любого многочлена вида $fu+gv$ делится либо на старший
член $f_C$, либо на старший член $g_C$. Предположим противное в последнем
утверждении. Пусть $F=fu+gv$ -- многочлен, старший член которого не делится
ни на $f_C$, ни на $g_C$. Можно считать, что в этой записи старший член
многочлена $u$ минимален по всем таким представлениям многочлена $F$.
По предположению старшие члены многочленов $fu$ и $gv$ сокращаются, откуда
$u_C=wg_C$, а $v_C=-wf_C$ для некоторого одночлена $w$.
Но тогда $F=f(gw+u_1)+g(-wf+v_1)=fu_1+gv_1$, и старший член $u_1$
меньше старшего члена $u$. Противоречие. \qedv


\bigskip

{\bf Доказательство теоремы~\ref{4th25}.}

\medskip

ШАГ 1. \ Пусть $f_1,\dots,f_s$ и $g_1,\dots,g_t$ -- два минимальных
базиса Гребнера идеала $I$. Мы покажем, что $s=t$ и (возможно после
перестановки многочленов) старшие члены $f_i$ и $g_i$ совпадают
для всех $i$ (мы предполагаем, что все многочлены нормированы,
т.е. имеют коэффициент 1 при старшем члене).
По определению базиса Гребнера, старший член
многочлена $f_1$ делится на старший член некоторого из $g_i$ (можно считать,
что на старший член многочлена $g_1$). С другой стороны, старший член
$g_1$ делится на старший член некоторого $f_j$. В силу минимальности
базиса $f_1,\dots,f_s$ получаем $j=1$. Отсюда следует, что старшие члены
$f_1$ и $g_1$ совпадают. Далее, старший член $f_2$ делится
на старший член $g_k$, причем $k\ne 1$, т.к. иначе старший член $f_2$
делился бы на старший член $f_1$, что противоречило бы минимальности
базиса $f_1,\dots,f_s$. Можно считать, что $k=2$ и мы получаем как и выше,
что старшие члены $f_2$ и $g_2$ совпадают. Продолжая
этот процесс, несложно заметить, что многочлены $f_i$ и $g_j$ должны
исчерпаться одновременно, откуда $s=t$.

\medskip

ШАГ 2. \ Пусть базисы $f_1,\dots,f_s$ и $g_1,\dots,g_s$ дополнительно
являются редуцированными. Предположим, что $f_i-g_i\ne 0$ для некоторого
$i$. Тогда старший член многочлена $f_i-g_i\in I$ делится на старший
член одного из $g_j$. С другой стороны, старший член $f_i-g_i$ является
нестаршим членом одного из многочленов $f_i$ или $g_i$. Заметим, что
старшие члены $g_j$ и $f_j$ совпадают. Получено противоречие с
редуцированностью базисов. \qedv





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section[К главе 5]{К главе 5}

{\bf Доказательство теоремы~\ref{5th11}.}

\medskip

После перенумерации можно обозначить переменные \linebreak
$x_{i_1},\dots,x_{i_k}$ просто $x_1,\dots,x_k$.
Рассмотрим естественную проекцию $\pi$ подалгебры $A=\C[x_1,\dots,x_k]$ алгебры
$\C[x_1,\dots,x_n]$ на факторалгебру $B=\C[x_1,\dots,x_n]/I(S)$.
Если отображение $\pi$ не является инъективным, то найдется многочлен
$F(x_1,\dots,x_k)$, лежащий в идеале системы. Это означает, что образ
координатной проекции лежит в гиперповерхности $H_F$.

Предположим, что отображение $\pi$ является вложением и докажем, что
образ координатной проекции в этом случае плотен. Мы будем отождествлять
алгебру $A$ с ее образом $\pi(A)$ и рассматривать $A$ как подалгебру в $B$.
Нам потребуется следующее утверждение, заимствованное из книги
Э.~Б.~Винберга и А.~Л.~Онищика "Семинар по группам Ли и алгебраическим
группам", М. Наука, 1988, стр.~72.


\medskip

{\bf Предложение 1.}\  {\it Пусть $B$ -- алгебра без делителей нуля, конечно
порожденная над своей подалгеброй $A$. Тогда для любого элемента
$b\in B, \ b\ne 0$ найдется такой элемент $a\in A, \ a\ne 0$, что
всякий гомоморфизм $\phi:A\to \C$, не аннулирующий $a$, продолжается
до гомоморфизма $\psi: B\to \C$, не аннулирующего $b$.}


\medskip

{\bf Доказательство.}\ \ ШАГ  1. \ \  Пусть $B=A[u]$, где элемент $u$ не
удовлетворяет никакому уравнению над $A$ (т.е. является трансцендентным
над $A$). Для любого многочлена $f\in A[x]$ обозначим через $f^{\phi}$
многочлен из $\C[x]$, полученный из $f$ применением гомоморфизма $\phi$
ко всем коэффициентам. Пусть $b=g(u)$.
Возьмем в качестве $a$ любой ненулевой коэффициент многочлена $g$.
Тогда $g^{\phi}\ne 0$.
Пусть $\alpha\in\C$ -- любое число,
не являющееся корнем многочлена $g^{\phi}$. Определим гомоморфизм
$\psi$ формулой $\psi(f(u))=f^{\phi}(\alpha)$. Тогда $\psi(b)\ne 0$.

\medskip

ШАГ 2.\ \ Предположим, что $B=A[u]$ и элемент $u$ является алгебраическим
над $A$. Пусть $p\in A[x]$ -- минимальный многочлен элемента $u$ и $a_1$ --
старший коэффициент этого многочлена. Если $q\in A[x]$ -- такой многочлен,
что $q(u)=0$, то существует такое $k$, что $a_1^kq$ делится на $p$ в $A[x]$.
Поэтому, если $\phi(a_1)\ne 0$ и $\alpha\in \C$ -- любой корень многочлена
$p^{\phi}$, то формула $\psi(f(u))=f^{\phi}(\alpha)$ корректно определяет
гомоморфизм $\psi: B\to \C$, совпадающий с $\phi$ на $A$.

Любой элемент $b\in B$ алгебраичен над $A$. Пусть $h\in A[x]$ --
такой ненулевой многочлен, что $h(b)=0$. Можно считать, что свободный
член $a_2$ многочлена $h$ отличен от нуля. Если $\psi(b)=\beta$, то
$h^{\phi}(\beta)=0$. Пусть $\phi(a_2)\ne 0$. Тогда и $\beta\ne 0$.
Остается положить $a=a_1a_2$.

\medskip

ШАГ 3.\ \ Индукция по числу образующих алгебры $B$ над $A$ сводит
доказательство к последовательному применению шагов 1 и 2. \qedv

\bigskip

Вернемся к доказательству теоремы~\ref{5th11}.
Точки на множестве решений $X(S)$ определяются значениями переменных
$x_i$, для которых обнуляются все многочлены из идеала системы.
Это позволяет установить биекцию между точками из $X(S)$ и гомоморфизмами
алгебры $B=\C[x_1,\dots,x_n]/I(S)$ в поле $\C$ (значения переменных отвечают
образам этих переменных при соответствующем гомоморфизме).


Предположим, что алгебра
$B$ не имеет делителей нуля. По только что доказанному найдется такой
элемент $a$ алгебры $A=\pi(\C[x_1,\dots,x_k])$, что каждый гомоморфизм
$A\to \C$, не обнуляющий $a$, продолжится до гомоморфизма $B\to \C$
(здесь мы положили $b=1$). Это означает, что каждая точка на координатном
подпространстве $Ox_1\dots x_k$, в которой не обращается в нуль многочлен
$a$, является образом некоторой точки из $X(S)$ при координатной проекции.

Рассмотрим случай, когда алгебра $B$ имеет делители нуля. Мы покажем,
что этот случай сводится к предыдущему. Пусть $b_1\ne 0$, $b_2\ne 0$, но
$b_1b_2=0$. Тогда хотя бы одно из отображений
$\pi_i:A\to B/(b_i)$, $i=1,2$ инъективно. В самом деле, если $\pi_i(c_i)=0$,
то $\pi(c_1c_2)=0$, что противоречит инъективности $\pi$, поскольку в $A$
делителей нуля нет. Далее мы можем рассматривать в качестве $B$
соответствующую $B_i$ и доказывать, что для отвечающего ей множества решений
образ координатной проекции плотен в $Ox_1\dots x_k$ (тем более
будет плотен образ $X(S)$). Если в $B_i$ есть делители нуля $b_3$
и $b_4$, поступаем аналогично и т. д. В результате мы получим идеал в $B$,
порожденный элементами $b_i, b_j,\dots$. По теореме Гильберта
о базисе такой идеал порождается конечным числом своих базисных элементов.
Следовательно, за конечное число шагов мы получим алгебру $B'$, в которую
вкладывается $A$ и которая не содержит делителей нуля. \qedv


\bigskip

{\bf Доказательство теоремы~\ref{5th20}.}

\medskip

В силу максимальности свободного набора $\{x_1,\dots,x_k\}$
для любого $j>k$ значения переменных $\{x_1,\dots,x_k,x_j\}$
на множестве решений связаны соотношением $F_j(x_1,\dots,x_k,x_j)=0$.
Пусть $h_j(x_1,\dots,x_k)$ -- коэффициент при старшем члене по переменной
$x_j$. Если при значениях $x_1=x_1^0,\dots,x_k=x_k^0$ значение
$h_j(x_1^0,\dots,x_k^0)$ отлично от нуля, то переменная $x_j$ может
принимать лишь конечное число значений на соответствующем прообразе
$\phi^{-1}(u_0)$. Поэтому для всех точек множества $U$,
в которых многочлен
$h_{k+1}(x_1,\dots,x_k)h_{k+2}(x_1,\dots,x_k)\dots
h_n(x_1,\dots,x_k)$
отличен от нуля, прообраз $\phi^{-1}(u_0)$ конечен. \qedv


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\chapter[Универсальный базис Гребнера]{Добавление. Универсальный базис Гребнера}

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

Рассмотрим произвольное поле $\k$ и кольцо многочленов $\k[x_1,\dots,x_n]$.
Предположим, что на множестве одночленов $\{x^a=x_1^{a_1}\dots x_n^{a_n}\}$
введен полный порядок
$\prec$, для которого выполнены свойства:

1) единица $1=x^0$ есть (единственный) минимальный элемент этого порядка;

2) если $x^a\prec x^b$, то для любого $x^c$ имеем $x^ax^c\prec x^bx^c$.

Всюду далее слово "порядок" будет означать полный порядок на множестве
одночленов со свойствами 1),2).
Порядок позволяет корректно определить старший член у любого
многочлена.

\medskip

\bza{}{Доказать в этой ситуации справедливость леммы о старшем члене.}

\medskip

\bex{Пусть $\omega_1,\dots,\omega_n$ -- набор положительных действительных чисел,
линейно независимых над полем рациональных чисел. Будем считать,
что одночлен $x^a=x_1^{a_1}\dots x_n^{a_n}$ больше одночлена
$x^b=x_1^{b_1}\dots x_n^{b_n}$ если
$a_1\omega_1+\dots+a_n\omega_n>b_1\omega_1+\dots+b_n\omega_n$.
Нетрудно проверить, что тем самым определен порядок
(зачем нужны положительность и линейная
независимость чисел $\omega_i$ ?). Мы получили достаточно богатый
запас порядков. В то же время, лексикографический порядок нельзя определить
подобным способом (почему ?).}

\medskip

\bza{}{1)\ Описать все возможные порядки на множестве одночленов от одной
переменной;

2)\ Доказать, что при $n>1$ число различных порядков бесконечно.}

\medskip

\bza{*}{Доказать, что для любого порядка $\prec$ не существует бесконечной
цепочки одночленов $x^{a_1}\succ x^{a_2}\succ x^{a_3}\succ\dots$.}\label{7za2}

\medskip

После того, как старший член определен, определение базиса Гребнера
дословно переносится на порядок $\prec$. Заметим, что базис Гребнера,
построенный по некоему порядку $\prec$, может очень сильно отличаться
от базиса Гребнера, построенного по лексикографическому порядку. Проблема выбора
для данного идеала того порядка, для которого базис Гребнера будет иметь
максимально простой и удобный вид, активно
исследуется в настоящее время. Читателю, желающему попробовать здесь свои
силы, рекомендуем ознакомиться с литературой по базисам Гребнера, приведенной
в конце курса. Сейчас же мы, следуя книге~\cite{6}, докажем
весьма неожиданный результат --
для любого идеала $I\lhd \k[x_1,\dots,x_n]$ найдется конечный универсальный
базис Гребнера, т.е. базис, который подходит для всех возможных порядков.

\medskip

\bde{Базис $f_1,\dots,f_M$ идеала $I$ называется {\it универсальным} базисом
Гребнера, если он является базисом Гребнера идеала $I$ для любого возможного
порядка $\prec$ на множестве одночленов.}

\medskip

\bth{Любой идеал $I\lhd \k[x_1,\dots,x_n]$ обладает конечным универсальным
базисом Гребнера.}

\medskip

{\bf Доказательство.}\ С каждым порядком $\prec$ мы свяжем (мономиальный)
идеал $I(\prec)$ -- это идеал, порожденный старшими членами многочленов
из идеала $I$ относительно порядка $\prec$. Заметим, что базис Гребнера
идеала $I$ относительно порядка $\prec$ однозначно определяется идеалом
$I(\prec)$ -- достаточно найти базис идеала $I(\prec)$ из одночленов
и в качестве базиса Гребнера в $I$ взять многочлены из $I$, старшие члены
которых образуют упомянутый базис в $I(\prec)$. (С другой стороны,
для различных порядков $\prec_1$ и $\prec_2$ идеалы $I(\prec_1)$
и $I(\prec_2)$ могут совпадать -- приведите пример !)
Если мы докажем, что среди идеалов $I(\prec)$ по всем порядкам $\prec$
имеется лишь конечное число различных, то для получения (конечного)
универсального базиса Гребнера нам будет достаточно объединить базисы
Гребнера, отвечающие этому конечному набору мономиальных идеалов.

Будем рассуждать от противного. Пусть число идеалов вида $I(\prec)$ бесконечно.
Рассмотрим многочлен $f_1\in I$. Число членов в нем конечно, поэтому
найдется такой член $m_1$ этого многочлена, который содержится в бесконечном
множестве $A_1$ различных идеалов типа $I(\prec)$.

\medskip

\ble{Найдется многочлен $f_2\in I$, ни один член которого не делится на $m_1$.}
\label{7le1}

\medskip

{\bf Доказательство.}\ Поскольку $m_1$ лежит в бесконечном числе идеалов
вида $I(\prec)$, мы можем выбрать из них идеал \linebreak $I(\prec_1)$, который
не совпадает с $(m_1)$. Будем называть одночлены, не попавшие
в идеал $I(\prec_1)$, {\it нормальными} одночленами относительно порядка
$\prec_1$. Докажем, что любой многочлен $F\in \k[x_1,\dots,x_n]$ допускает
ровно одну запись вида $F=F_1+F_2$, где $F_1$ -- линейная комбинация нормальных
одночленов, а многочлен $F_2$ лежит в $I$. В самом деле, если среди членов
многочлена $F$ есть принадлежащие к идеалу $I(\prec_1)$, к таким членам
можно применить редукцию. Задача~\ref{7za2} показывает, что после
конечного числа редукций многочлен $F$ можно будет заменить линейной комбинацией
нормальных одночленов. Это показывает, что нужная запись существует.
Для доказательства единственности достаточно
рассмотреть случай $F_1+F_2=0$, или $F_1=-F_2$, что означает, что $F_1\in I$.
В этом случае старший член многочлена $F_1$
относительно порядка $\prec_1$ лежит в идеале $I(\prec_1)$, что приводит
к противоречию с нормальностью всех членов $F_1$.

Пусть $r$ -- одночлен, лежащий в $I(\prec_1)$ и не делящийся на $m_1$.
Рассмотрим для него полученную запись $r=F_1+F_2$. Остается
положить $f_2=r-F_1$ (все члены $F_1$ нормальны и потому не делятся на $m_1$).
\qedv

\medskip

Пусть $f_2$ -- многочлен, построенный в предыдущей лемме. Тогда
мы вновь замечаем, что любой идеал вида $I(\prec)$ содержит один
из его членов и потому найдется бесконечное множество идеалов
$A_2$ из числа идеалов из $A_1$, которые содержат некоторый член
$m_2$ многочлена $f_2$. Пусть $I(\prec_2)$ -- один из этих
идеалов, не совпадающий с $(m_1, m_2)$. Повторяя рассуждения из
доказательства леммы~\ref{7le1}, мы найдем многочлен $f_3\in I$,
ни один из членов которого не лежит в идеале $(m_1,m_2)$.
В этом многочлене мы опять находим член $m_3$, который лежит в бесконечно
многих идеалах типа $I(\prec)$ из множества $A_2$ и т.д. Окончательно
мы получим бесконечную цепочку попарно различных идеалов
$$
(m_1)\subset (m_1, m_2)\subset (m_1,m_2,m_3)\subset \dots
$$
Это противоречит теореме Гильберта о базисе. \qedv

\medskip

\bza{}{Пусть $f\in\k[x_1,\dots,x_n]$. Найти универсальный базис Гребнера
главного идеала $(f)$.}\label{7za05}

\medskip

Несколько интересных примеров вычислений универсального базиса Гребнера,
а также общий алгоритм его нахождения можно найти в главах 1 и 3 книги~\cite{6}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter{Указания и ответы к задачам}

\section[К главе 1]{К главе 1}


\ \ \ \ {\bf \ref{z1}.}\ Первая система: $x=\pm i\sqrt{1+y^2}, \ y \in \C$
(бесконечно много решений).
Вторая система несовместна.

\medskip

{\bf \ref{z3}.}
$$
\left\{
\begin{array}{l}
x_1+x_2+x_3=1\\
2x_1+x_2+x_3=2
\end{array}
\right.
$$

\medskip

{\bf \ref{z2}.}\ $(x_3, x_4, x_5), \ (x_1, x_4, x_5), \
(x_1, x_3, x_5), \ (x_1, x_3, x_4)$ -- 4 способа.

\medskip

{\bf \ref{z4}.}\ 1) Проверьте, что множество $U$ решений однородной системы

$$
\cases{a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n=0,  \cr
       a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n=0,  \cr
       \dots   \cr
       a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n=0  \cr}
\refstepcounter{refer}
\eqno{(\therefer)}
\label{ssys2}
$$
является подпространством в $\R^n$.

\smallskip

2) Докажите, что каждое решение системы
$$
\cases{a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n=b_1,  \cr
       a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n=b_2,  \cr
       \dots   \cr
       a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n=b_m  \cr}
\refstepcounter{refer}
\eqno{(\therefer)}
\label{asys2}
$$
есть сумма некоторого фиксированного решения $a$ этой системы и решения
$u\in U$ соответствующей однородной системы. Тем самым множество решений
есть линейное мноообразие.

\smallskip

3) Обратно, по каждому подпространству $U$ построим однородную систему,
множеством решений которой является $U$. Коэффициенты уравнений этой системы
суть базисные вектора ортогонального дополнения к $U$ в $\R^n$.
Подставим в эту однородную систему вектор $a$ и найдем столбец свободных
членов искомой системы.

\medskip

{\bf \ref{z5}.}\ $q(x)=0, \ r(x)=x^2-x+1.$

\medskip

{\bf \ref{z6}.}\ Нет. Нельзя разделить с остатком
 $x$ на $2x$.


\medskip

{\bf \ref{z7}.}\ Воспользоваться теоремой Безу и индукцией по степени
многочлена.


\medskip

{\bf \ref{z8}.}\ Нет. Следующие многочлены не имеют корней:

1) $x^2+1$ над $\Q$;

2) $x^p-x+\overline{1}$ над $\Z_p$ \ (малая теорема Ферма);

3) $x^2-t$ над $\C(t)$ (каковы степени числителя и знаменателя у возможного
корня ?).


\medskip

{\bf \ref{z9}.}\ Пусть $\k$ алгебраически незамкнуто. Тогда имеется многочлен
$a_mx^m+\dots+a_1x+a_0$, не имеющий корней. Уравнение
$F(x,y)=a_mx^m+a_{m-1}x^{m-1}y+\dots+a_1xy^{m-1}+a_0y^m=0$ имеет единственное
решение $(0, 0)$. Система
$$
\left\{
\begin{array}{l}
P_1=0\\
P_2=0
\end{array}
\right.
$$
эквивалентна уравнению $F(P_1(x_1,\dots, x_n), P_2(x_1,\dots, x_n))=0$.
Далее проводим индукцию по числу уравнений системы.


\medskip

{\bf \ref{z10}.}\ а) $(x^2-2)(x^3-2)$;

\medskip

 \ \ \ \ \ \ \ б)
$\left\{
\begin{array}{l}
(x^2-2)(x^3-2)(y^2+1)=0\\
(y-1)(y^2+1)=0
\end{array}
\right.$

\smallskip

\ \ \ \ \ \ \  или $(x^2-2)^2(x^3-2)^2+y^2=0$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section[К главе 2]{К главе 2}

\ \ \ \ \ {\bf \ref{z11}.}\ Воспользоваться предыдущей задачей.


\medskip

{\bf \ref{z12}.}\ Воспользоваться леммой о линейном представлении НОД.

\medskip

{\bf \ref{zn1}.}\ Если $f_1$ делится на $f_2$, а $f_2$ на $f_1$, то
степени этих многочленов совпадают и они отличаются на ненулевую
константу.

\medskip

{\bf \ref{z13}.}\ $x(x-1)(x-2)$.

\medskip

{\bf \ref{z14}.}\ Рассмотреть идеал, порожденный $2$ и $x$.

\medskip

{\bf \ref{z15}.}\ 1) \ $x^{17}, x^{16}y,\dots, y^{17}$;

\ \ \ \ \ \ \ \ 2) $y, x^2.$

\medskip

{\bf \ref{z16}.}\ $x-y, x-z, x-t.$ В самом деле, $f(x,y,z,t)-f(x,x,z,t)=
(x-y)f_1(x,y,z,t)$. \ Поэтому
$$
f(x,y,z,t)=(x-y)f_1(x,y,z,t)+(x-z)f_2(x,z,t)+$$
$$+(x-t)f_3(x,t)+f(x,x,x,x). $$
Где в рассуждениях существенно, что поле $\k$ бесконечно ?


\medskip

{\bf \ref{z17}.}\ Подходят базисы типа $\{ z, y, x\},\ \{ x+y+z, y+z, z\},
\ \{x+y^2-z^4, -y+5z^7, 2z\},\ \{x-2x^3+y-2y^2+z, z+y-2y^2-2x^2, z-2y^2+x^3
\}$.

\medskip

{\bf \ref{z18}.}\ Рассмотреть идеал, порожденный множеством $M$, и
показать, что конечный базис в нем можно выбрать из элементов $M$.

\medskip

{\bf \ref{z191}.}\ Можно рассмотреть кольцо $\k[x_1,x_2,\dots]$ от
счетного числа переменных и в качестве $I$ взять идеал $(x_1,x_2,\dots)$,
состоящий из многочленов с нулевым свободным членом. Здесь существенно
что каждый многочлен зависит лишь от конечного числа переменных. Можно также
в качестве $R$ взять множество последовательностей $(a_1,a_2,\dots), \ a_i\in
\k$ с покоординатным сложением и умножением, а в качестве $I$ -- множество
последовательностей, у которых лишь конечное число членов отлично от нуля.

\medskip

{\bf \ref{z19}.}\ б) $(x+1)(x^2+x+1)=0$.

\medskip

{\bf \ref{z20}.}\ $S_1: x^2y=0$, $S_2: xy^2=0$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section[К главе 3]{К главе 3}

\ \ \ \ \ {\bf \ref{z22}.}\ $(x-1)(x-4)(x-7)=0, \ (x-1)(x-4)(y-8)=0, \dots, \
(z-3)(z-6)(z-9)=0$ (всего 27 уравнений). На самом деле данные три точки можно
задать и тремя уравнениями, например $x+1=y=z-1, (x-1)(x-4)(x-7)=0$, однако
первый способ представляется более универсальным.
\medskip

{\bf \ref{z23}.}\ е) Множество корней ненулевого многочлена от одной
переменной конечно;

\ \ \ \ \ \ ж) Рассмотреть пересечение данного множества с осью $Ox$
и воспользоваться предыдущим пунктом.


\medskip

{\bf \ref{z24}.}\  а) Следует объединить уравнения системы, задающие
многообразия.

\ \ \ \ \ \ б) Если одно многообразие задано системой $f_i=0$,
а другое системой $g_j=0$, то система $f_ig_j=0$ задает объединение
многообразий.


\medskip

{\bf \ref{z25}.}\ а) $((x-2)(x-3)(x-4)(x-5))$.

\ \ \ \ \ \ б) $(x-y, x-z)$.

\ \ \ \ \ \ в) $(x^4-y^2)$.

\ \ \ \ \ \ г) $(x-y)$.


\medskip

{\bf \ref{z26}.}\  a) Положим степень одночлена $x^iy^jz^k$ равной
$3i+4j+5k$. Ясно, что степень произведения одночленов равна сумме их
степеней. Произвольный многочлен $f$ можно представить в виде
$f=f_0+f_1+\dots+f_N$, где $f_l$ -- сумма всех одночленов степени $l$.
Проверьте, что если $f\in J(X)$, то и $f_l\in J(X)$ для любого $l$
(это свойство идеала называется {\it однородностью}).
Для этого покажите, что $f_l(1,1,1)=0$. Проверьте также,
что элементы наименьшей степени в идеале $J(X)$ -- это $a=y^2-xz$ (степени 8),
$b=x^3-yz$ (степени 9)
и $c=z^2-x^2y$ (степени 10). Предположим, что идеал $J(X)$ порожден
элементами $g$ и $h$. Обозначим через $g'$ и $h'$ компоненты многочленов
$g$ и $h$ степени $\le 10$. Тогда $a$, $b$ и $c$ должны выражаться через
$g'$ и $h'$ с числовыми коэффициентами (сравните степени !). Это противоречит
линейной независимости многочленов $a$, $b$ и $c$.

\medskip

\ \ \ \ \ \ б) Подходит система $x^4=y^3, \ x^5=z^3, \ y^5=z^4$. В самом
деле, если $x=0$, то $y=z=0$, иначе положим $t=\frac{y}{x}$. Тогда
$$
t^3=\frac{y^3}{x^3}=x, \ t^4=\frac{y^4}{x^4}=y, \
t^5=\frac{y^5}{x^5}=\frac{y^5}{z^3}=z.
$$

\medskip

{\bf \ref{z27}.}\ а) $(x)$, \ б) $(x,y)$, \ в) $(x,y)$, г) $(x^2+y^2+z^2)$
(см. следующую задачу).


\medskip

{\bf \ref{z28}.}\  Если $I=(f)$ и $f=f_1^{k_1}\dots f_s^{k_s}$ --
разложение на неприводимые множители, то $r(I)=(f_1\dots f_s)$
(воспользоваться теоремой о факториальности кольца многочленов).

\medskip

{\bf \ref{z29}.}\ 1) \ Рассмотреть идеал $(x^2+1)$.

2) \  По теореме Гильберта о нулях $f^s=h_1f_1+\dots+h_mf_m$
для некоторых многочленов $h_j$ с комплексными коэффициентами.
Пусть $h_j=r_j+iq_j$, где $r_j$ и $q_j$ -- многочлены с вещественными
коэффициентами. Тогда $f^s=r_1f_1+\dots+r_mf_m$.

\medskip

{\bf \ref{z30}.}\ Если $f^k\in r(I)$, то существует такое $s$,
что $(f^k)^s\in I$. Отсюда $f\in r(I)$.

\medskip

{\bf \ref{z31}.}\ Уравнения $1=0$ и $x^2=-1$ не пропорциональны.


{\bf \ref{z32}.}\ Если $r(I(S))=(f)$, то система эквивалента
уравнению $f=0$. Обратно, если система эквивалентна уравнению
$f=0$, то идеал $r((f))$ является главным (задача~\ref{z28}).
Идеал системы в этой ситуации главным быть не обязан: рассмотрите
систему $x^2y=0, \ xy^2=0$.


\medskip

{\bf \ref{z33}.}\ Здесь идеал $(x,y)$ является радикальным.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section[К главе 4]{К главе 4}

\ \ \ \ \ {\bf \ref{4za3}.}\ a) Вообще говоря нет:
набор вида $(0,k)$ меньше набора
$(1,0)$. Опишите все наборы $w$, для которых число наборов, меньших $w$,
конечно.

б) Воспользоваться индукцией по $n$.

\medskip

{\bf \ref{4za5}.}\ а) (4,3);

б)  Отрезок (или точку);

в) Вершины $(0,0,0)$, $(4,0,0)$, $(0,4,0)$, $(0,0,4)$, $(3,3,0)$,
   8 ребер, 5 граней.  

\medskip

{\bf \ref{4za8}.}\ После подстановки $y=0$ многочлен не делится на $x^2$.

\medskip

{\bf \ref{4za12}.}\ Воспользоваться задачей \ref{4za3} б).

\medskip

{\bf \ref{4za17}.}\ Редукция многочлена $\wt F_{i,j}$ при помощи
$f_{m+1}$ равна нулю.

\medskip

{\bf \ref{nznz}.}\ В точности тогда, когда среди $f_i$ есть
многочлен, который делит все остальные.

\medskip

{\bf \ref{4za22}.} \ Воспользоваться задачей \ref{4za13}.

\medskip

{\bf \ref{4za271}.} \ Построим базисы Гребнера в обеих идеалах, затем
построим минимальные редуцированные базисы Гребнера. Остается проверить
их совпадение.
Можно также решать задачу вхождения во второй идеал для $f_1,\dots,f_k$
и обратно.

\medskip


{\bf Вычисление базисов Гребнера.}

\medskip

1) \ \  $x^2-1$, $(x-1)y$, $(x+1)z$, $yz$;

\medskip

2) \ \  $x^2-1$, $(x-1)y$, $(x-1)z$;

\medskip

3) \ \ $xy^2z-xyz$, $x^2y^2-z$, $x^2yz-z^2$, $yz^2-z^2$, $x^2z^2-z^3$;

\medskip

4) \ \ $x^2y+xz+y^2z$, $xz^2-zy$, $xyz-y^2$, $y^3+y^2z^3+yz^2$,
$xy^2+y^2z^2+zy$;

\medskip

5) \ \ $x^2y-y$, $2y^2+z$, $2z^2+z$, $xz+z$;


\medskip

6) \ \ $xz+yz^3$, $xy+yz^3$, $yz^4-yz$, $y^2z-yz^2$.

\medskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section[К главе 5]{К главе 5}

\ \ \ \ \  {\bf \ref{5za2111}.}\ 1) Пусть $f^p\in I$. Тогда
$1=(1-yf)(1+yf+\dots+y^{p-1}f^{p-1})+f^py^p$. Обратно, если
$(f_1,\dots,f_m,1-yf)$ совпадает со всем кольцом, то многочлен $f$
обращается в нуль на множестве общих нулей многочленов $f_1,\dots,f_m$
не только над полем $\k$, но и над любым полем, содержащим $\k$
(рассмотрите представление $1=f_1h_1+\dots+f_mh_m+(1-yf)h$). По теореме
Гильберта о нулях, примененной к алгебраически замкнутому
полю\footnote{Заметим, что в доказательстве теоремы Гильберта о нулях
использовалось лишь одно свойство поля комплексных чисел -- его
алгебраическая замкнутость.}, содержащему
поле $\k$ (известно, что такое найдется для любого $\k$), $f$ лежит
в радикале идеала $(f_1,\dots,f_m)$. Последнее не зависит от того,
рассматриваются многочлены $f_1,\dots,f_m,f$ над полем $\k$ или каким-либо
его расширением.

\ 2) Многочлен $f$ принадлежит радикалу идеала $(f_1,\dots,f_m)$
тогда и только тогда, когда в базисе Гребнера идеала \linebreak
$(f_1,\dots,f_m,1-yf)$ содержится ненулевая константа.

\medskip

{\bf \ref{5za2112}.}\ После линейной замены переменных можно считать,
что $l=x_n$. Тогда нужно найти элемент $x_n^s$ в минимальном базисе Гребнера
для лексикографического порядка \linebreak
$x_1>\dots>x_n$ или убедиться, что такого
элемента там нет.

\medskip

{\bf \ref{5za10}.}\ а)\ Это в точности дополнения до конечных
подмножеств;

б)\ Дополнения до алгебраических кривых; дополнения до конечных подмножеств.

\medskip

{\bf \ref{5za13}.}\ Можно считать, что переменная $x_1$ входит в многочлен
$F$. Покажем, что набор $\{x_2,\dots,x_n\}$ является свободным.
Если значения переменных $x_2,\dots,x_n$ на множестве решений лежат на
гиперповерхности $H(x_2,\dots,x_n)=0$, то по теореме Гильберта о нулях
для некоторого $s\in \N$ многочлен $H^s$ делится на $F$ -- противоречие.

\medskip

{\bf \ref{5za14}.}\
Вытекает из теоремы~\ref{5th11} и задачи~\ref{5za10}, 1).

\medskip

{\bf \ref{5za141}.}\ Если поднабор зависим, переменные из этого
поднабора связаны алгебраическим уравнением, что противоречит свободности
набора.

\medskip

{\bf \ref{5za15}.}\ Для системы $xy=0$, $xz=0$ набор $\{y,z\}$ является
единственным максимальным свободным набором, поэтому свободный набор
$\{x\}$ нельзя включить в максимальный.

\medskip


{\bf \ref{5za16}.}\ Эти условия эквивалентны тому, что каждая переменная
принимает на множестве решений лишь конечное число значений.


\medskip

{\bf \ref{5za19}.}\ Взяв в качестве максимального свободного набора
набор $\{x,y\}$, получим $U=Oxy$.

\medskip

{\bf Решение систем.}

\bigskip

1)
$x=1$,
$y\in\C$,
$z=0$ или $x=-1$, $y=0$, $z\in \C$.

\medskip

Базис Гребнера при $x>y>z$ : $x^2-1$, $xy-y$, $xz+z$, $yz$.

\bigskip

2)
$x=y=z=0$ или
$x=-1$, $y={{1\pm i\sqrt3}\over2}$,
$z={{-1\pm i\sqrt3}\over2}$.

\medskip

Базис Гребнера при $x>y>z$ : $x-z^2-z$, $y+z^2$, $z^2+z^3+z^4$.

\bigskip

3)
$x={{-3\pm i\sqrt7}\over2}$,
$y={{1\pm i\sqrt7}\over4}$,
$z={{5\mp i\sqrt7}\over8}$.

\medskip

Базис Гребнера при $x>y>z$ : $x+4z-1$, $-3+4z+2y$, $4z^2-5z+2$.

\bigskip

4)
$x=0$, $y\in\C$, $z=0$;

\quad $x\in\C$, $y=0$, $z=0$;

\quad $x\in\C$, $y=1$, $z=x^2$.

Базис Гребнера при
$x>y>z$ : $x^2y^2-z$, $x^2yz-z^2$, $-z^3+x^2z^2$, $xy^2z-xyz$, $-z^2+z^2y$.

\bigskip

5)
$x\in\C$,
$y=0$,
$z=0$ или $x=-1$, $y={\pm{1\over 2}}$, $z=-{1\over 2}$.

\medskip

Базис Гребнера при $x>y>z$ : $x^2y-y$, $xz+z$, $2y^2+z$, $2z^2+z$.

\bigskip

6)
 $x=1$, $y=1$, $z=0$;

\quad $x=-1\pm i\sqrt2$, $y=\mp i\sqrt2$,
$z=-1\mp i\sqrt2$;

\quad $x=\pm~i\sqrt2$,
$y=-{1\over2}$, $z=1\pm {{i\sqrt2}\over2}$.

\medskip

Базис Гребнера при
$y>z>x$ : $-x^2+2y-1$, $2z-2+x^3+x$, $(x^2+2x+3)(x^2+2)(x-1)^2$.

\bigskip

7)
$(0,0,0)$; $(1,0,1)$; $(-1,2,-3)$.

\medskip

Базис Гребнера при $y>z>x$ : $x-x^2+y$, $x^2-2x^3+z$, $-x^2+x^4$.


\bigskip

8)
$x=0$,
$y=0$,
$z\in \C$ или $x={{1\pm i\sqrt3}\over2}$, $y={{1\mp i\sqrt3}\over2}$,
$z={{-1\mp i\sqrt3}\over2}$.

\medskip

Базис Гребнера при $x>y>z$ : $x+y+yz$, $y^2+z^2y$, $yz+z^2y+z^3y$.

\bigskip

9)
$x=y=z=0$ или
$x={1\over2}$, $y=-{1\over2}$,
$z=-{1\over2}$ или $x={{-1\pm i\sqrt3}\over4}$, $y=-{1\over2}$,
$z={{1\pm i\sqrt3}\over4}$.

\medskip

Базис Гребнера при
$x>y>z$ : $yz+x^2+z$, $xz-2z^3$, $y^2+2z^3$, $2z^2y+z^2$, $z^2+8z^5$.

\bigskip

10)
$x=0$,
$y=0$,
$z=\pm 1$.

\medskip

Базис Гребнера при
$x>z>y$ : $x^2+z^2y+yz$, $y^2-zx+x$, $xy+z^2-1$, $-z^2+1+z^3-z+y^3$,

$y^2z^2-y^2$, $y^4$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section[К главе 7]{К главе 7}

\ \ \ \ \  {\bf \ref{7za2}.}\ Достаточно доказать, что найдутся такие номера
$i<j$, для которых $x^{a_j}$ делится на $x^{a_i}$, а это в точности
лемма Диксона.

\medskip

{\bf \ref{7za05}.}\ Универсальный базис состоит из одного многочлена $f$.
В самом деле, для любого порядка старший член многочлена $fg$ делится
на старший член $f$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%







\begin{thebibliography}{99}

\addcontentsline{toc}{abcd}{Литература о базисах Гребнера}

\bibitem{1}
Бухбергер~Б., Алгоритмический метод в теории полиномиальных идеалов ---
в книге "Компьютерная алгебра. Символьные и алгебраические вычисления",
М.: Мир, 1986. - 392 стр.

\bibitem{2}
Уфнаровский~В.~А., Комбинаторные и асимптотические методы в алгебре
- ВИНИТИ, Современные проблемы математики, Фундаментальные направления,
том 57, Москва, 1990 (параграф 2).

\bibitem{3}
Дэвенпорт Дж., Сирэ И., Турнье Э., Компьютерная алгебра, -
М.: Мир, 1991. - 350 стр. (глава 3).

\bibitem{4}
Латышев В.Н., Комбинаторная теория колец. Стандартные базисы, -
М.: МГУ, 1988. - 68 стр.

\bibitem{7}
Прасолов В. В., Многочлены -- М.: МЦНМО, 2000. - 335 стр. (глава 6).

\bibitem{8}
Кокс Д., Литтл Дж., О'Ши, Д., Идеалы, многообразия и алгоритмы --
М. Мир, 2000. - 687 стр.

\bibitem{5}
Eisenbud D. Commutative Algebra with a View Toward Al\-geb\-raic Geometry --
Graduate Texts in Math. 150, Springer-Verlag, New York, 1995
(глава 15).

\bibitem{6}
Sturmfels B. Gr\"obner Bases and Convex Polytopes --
AMS, Providence, RI, 1995.

\bibitem{9}
Adams W.W., Loustaunau P., An introduction to Gr\"obner Bases --
AMS, Graduated Studies in Math. Vol. III, 1994.

\bibitem{10}
Becker T., Kredel H., Weispfenning V., Gr\"obner Bases: A Computational
Approach to Commutative Algebra, Graduated Texts in Math., Springer,
New York, 1993.







\end{thebibliography}

\end{document}
