Многочлены


В. В. Прасолов



Многочлены
















МЦНМО

В. В. Прасолов





                Многочлены





Электронное издание








Москва Издательство МЦНМО 2017

УДК 512.62
ББК 22.144
     П70

Прасолов В. В. Многочлены
Электронное издание
М.: МЦНМО, 2017
335 с.
ISBN 978-5-4439-2638-4

         В книге изложены основные результаты исследований по теории многочленов, как классические, так и современные. Большое внимание уделено 17-й проблеме Гильберта о представлении неотрицательных многочленов суммами квадратов рациональных функций и ее обобщениям. Теория Галуа обсуждается прежде всего с точки зрения теории многочленов, а не с точки зрения общей теории расширения полей.
         Для студентов, аспирантов, научных работников — математиков и физиков.

Подготовлено на основе книги: В. В. Прасолов. Многочлены — М.: МЦНМО, 2014. — ISBN 978-5-4439-0233-3.














Издательство Московского центра непрерывного математического образования 119002, Москва, Большой Власьевский пер., 11, тел. (499) 241-08-04.
http://www.mccme . ru

ISBN 978-5-4439-2638-4

Q Прасолов В. В., 2017.
О МЦНМО, 2017.

Предисловие к первому изданию                            8

Глава 1. Корни многочленов                               9
1. Неравенства для корней                                9
   1.1. Основная теорема алгебры........................ 9
   1.2. Теорема Коши................................... 10
   1.3. Теорема Лагерра................................ 13
   1.4. Аполярные многочлены........................... 15
   1.5. Проблема Рауса-Гурвица......................... 20
2. Корни многочлена и его производной                   21
   2.1. Теорема Гаусса-Люка............................ 21
   2.2. Корни производной и фокусы эллипса............. 23
   2.3. Локализация корней производной................. 25
   2.4. Гипотеза Сендова-Илиева........................ 28
   2.5. Многочлены, у которых совпадают корни их самих
        и их производных............................... 30
3. Результант и дискриминант                            30
   3.1. Результант..................................... 30
   3.2. Дискриминант................................... 34
   3.3. Вычисление некоторых результантов и дискриминантов 35
4. Разделение корней                                    38
   4.1. Теорема Фурье-Бюдана........................... 38
   4.2. Теорема Штурма................................. 42
   4.3. Теорема Сильвестра............................. 43
   4.4. Разделение комплексных корней.................. 47
5. Ряд Лагранжа и оценки корней многочлена              49
   5.1. Ряд Лагранжа-Бюрмана........................... 49
   5.2. Ряд Лагранжа и оценки корней................... 52

Глава 2. Неприводимые многочлены                        58
6. Основные свойства неприводимых многочленов           58
   6.1. Разложение многочленов на неприводимые множители . 58
   6.2. Признак Эйзенштейна ........................... 61
   6.3. Неприводимость по модулю р..................... 63
7. Признаки неприводимости                              64
   7.1. Признак Дюма................................... 64
   7.2. Многочлены с доминирующим коэффициентом........ 68
   7.3. Неприводимость многочленов, принимающих
        малые значения................................. 71

Оглавление

8.  Неприводимость трехчленов и четырехчленов             72
   8.1. Неприводимость многочленов ж” ± хт ± хр ± 1..... 72
   8.2. Неприводимость некоторых триномов............... 77
9.  Теорема неприводимости Гильберта                     78
10. Алгоритмы разложения на неприводимые множители       82
   10.1. Алгоритм Берлекэмпа............................ 82
   10.2. Факторизация с помощью леммы Гензеля........... 85

Глава 3. Многочлены специального вида                     91
11. Симметрические многочлены                            91
   11.1. Примеры симметрических многочленов ............ 91
   11.2. Основная теорема о симметрических многочленах .... 93
   11.3. Неравенства Мюрхеда............................ 95
   11.4. Функции Шура................................... 98
12. Целозначные многочлены                               99
   12.1. Базис целозначных многочленов.................. 99
   12.2. Целозначные многочлены от многих переменных....102
   12.3. '/-аналог целозначных полиномов ...............103
13. Круговые многочлены                                 104
   13.1. Основные свойства круговых многочленов.........104
   13.2. Формула обращения Мёбиуса......................105
   13.3. Неприводимость круговых многочленов............107
   13.4. Выражение Фтоп через Ф„ .......................108
   13.5. Дискриминант кругового многочлена .............109
   13.6. Результант пары круговых многочленов...........110
   13.7. Коэффициенты круговых многочленов..............112
   13.8. Теорема Веддерберна............................113
   13.9. Многочлены, неприводимые по модулю р ..........114
14. Многочлены Чебышева                                 116
   14.1. Определение и основные свойства................116
   14.2. Ортогональные многочлены.......................121
   14.3. Неравенства для многочленов Чебышева...........124
   14.4. Производящая функция...........................126
15. Многочлены Бернулли                                 129
   15.1. Определения многочленов Бернулли ..............129
   15.2. Теоремы дополнения, сложения аргументов и умножения 132
   15.3. Формула Эйлера.................................134
   15.4. Теорема Фаульгабера-Якоби......................135
   15.5. Арифметические свойства чисел и многочленов Бернулли 137

Оглавление

5

Глава 4. Некоторые свойства многочленов                   151
16. Многочлены с предписанными значениями                151
   16.1. Интерполяционный многочлен Лагранжа ............151
   16.2. Интерполяционный многочлен Эрмита...............154
   16.3. Многочлен с предписанными значениями в нулях производной .........................................155
17. Высота многочлена и другие нормы                      158
   17.1. Лемма Гаусса....................................158
   17.2. Многочлены от одной переменной..................160
   17.3. Максимум модуля и неравенство Бернштейна........164
   17.4. Многочлены от многих переменных ................167
   17.5. Неравенство для пары взаимно простых многочленов . . 170
   17.6. Неравенство Миньотта............................171
18. Уравнения для многочленов                            174
   18.1. Диофантовы уравнения для многочленов............174
   18.2. Функциональные уравнения для многочленов........181
19. Преобразования многочленов                           187
   19.1. Преобразование Чирнгауза........................187
   19.2. Уравнение пятой степени в форме Бринга..........189
   19.3. Представление многочленов в виде сумм степеней линейных функций.....................................190
20. Алгебраические числа                                 194
   20.1. Определение и основные свойства.................194
   20.2. Теорема Кронекера...............................196
   20.3. Теорема Лиувилля................................199

Глава 5. Теория Галуа                                    203
21. Теорема Лагранжа и резольвента Галуа                 203
   21.1. Теорема Лагранжа................................203
   21.2. Резольвента Галуа...............................207
   21.3. Теорема о примитивном элементе..................212
22. Основы теории Галуа                                  214
   22.1. Соответствие Галуа..............................214
   22.2. Многочлен с группой Галуа ......................219
   22.3. Простые радикальные расширения..................220
   22.4. Циклические расширения..........................221
23. Решение уравнений в радикалах                        223
   23.1. Разрешимые группы...............................223

Оглавление

   23.2. Уравнения с разрешимой группой Галуа............225
   23.3. Уравнения, разрешимые в радикалах...............226
   23.4. Абелевы уравнения ..............................229
   23.5. Критерий Абеля-Галуа разрешимости уравнения простой степени......................................233
24. Вычисление групп Галуа                               239
   24.1. Дискриминант и группа Галуа.....................239
   24.2. Резольвентные многочлены........................239
   24.3. Группа Галуа по модулю р........................243

Глава 6. Идеалы в кольцах многочленов                    246
25. Теоремы Гильберта о базисе и о нулях                 246
   25.1. Теорема Гильберта о базисе......................246
   25.2. Теорема Гильберта о нулях.......................248
   25.3. Многочлен Гильберта.............................252
   25.4. Однородная теорема Гильберта о нулях для р-полей . . . 260
26. Базисы Грёбнера                                      263
   26.1. Многочлены от одной переменной..................263
   26.2. Деление многочленов от многих переменных........264
   26.3. Определения базисов Грёбнера....................265
   26.4. Алгоритм Бухбергера.............................268
   26.5. Приведенный базис Грёбнера......................270

Глава 7. Семнадцатая проблема Гильберта                  272
27. Суммы квадратов: введение                            272
   27.1. Некоторые примеры...............................272
   27.2. Теорема Артина-Касселса-Пфистера................277
   27.3. Неравенство между средним арифметическим и средним геометрическим...............................281
   27.4. Теорема Гильберта о неотрицательных многочленах р^(х, у)...............283
28. Теория Артина                                        289
   28.1. Вещественные поля...............................290
   28.2. Теорема Сильвестра для вещественно замкнутых полей . 295
   28.3. Семнадцатая проблема Гильберта..................298
29. Теория Пфистера                                      303
   29.1. Мультипликативные   квадратичные формы..........303
   29.2. С,-поля ........................................306

Оглавление                               7

   29.3. Теорема Пфистера о суммах квадратов рациональных функций..........................................308

Дополнение                                          313
30. Алгоритм Ленстры-Ленстры-Ловаса                 313
   30.1. Общее описание алгоритма...................313
   30.2. Приведенный базис решетки..................314
   30.3. Решетки и факторизация многочленов.........317

Литература                                          324

Предметный указатель                                331

   Теория многочленов составляет существенную часть университетских курсов алгебры и анализа. Тем не менее, книг, целиком посвященных теории многочленов, чрезвычайно мало.
   В этой книге изложены основные результаты исследований по теории многочленов, как классические, так и современные. Большое внимание уделено 17-й проблеме Гильберта о представлении неотрицательных многочленов суммами квадратов рациональных функций и ее обобщениям. Теория Галуа обсуждается прежде всего с точки зрения теории многочленов, а не с точки зрения общей теории полей и их расширений.
   В книгу не вошли два важных результата из теории многочленов, изложение которых занимает весьма много места: решение уравнений пятой степени с помощью тэта-функций и классификация коммутирующих многочленов. Эти результаты подробно изложены в двух недавно вышедших книгах, в написании которых я принимал непосредственное участие: [ПрС] и [ПрШ].
   Во время работы над этой книгой я получал финансовую поддержку от Российского фонда фундаментальных исследований согласно проекту №98-00-555.



Май 1999 г.

В. Прасолов

1.1. Основная теорема алгебры

   В те давние времена, когда алгебра была скудна теоремами, следующее утверждение получило название основной теоремы алгебры: «Многочлен степени п с комплексными коэффициентами имеет ровно п корней (с учетом их кратностей)». Впервые это утверждение сформулировал Альбер де Жирар в 1629 г., но он даже не пытался его доказывать. Первым осознал необходимость доказательства основной теоремы алгебры Даламбер, но его доказательство (1746) не было признано убедительным. Свои доказательства предложили Эйлер (1749), Фонсене (1759) и Лагранж (1771), но и эти доказательства были небезупречны.
   Первым удовлетворительное доказательство основной теоремы алгебры получил Гаусс, который привел три разных доказательства (1799, 1815 и 1816), а в 1845 г. опубликовал еще и уточненную версию своего первого доказательства.
   Обзор различных доказательств основной теоремы алгебры можно найти в [ТУ]. Мы ограничимся одним доказательством. Оно использует следующую теорему Руше, которая имеет и самостоятельный интерес.

   Теорема 1.1 (Руше). Пусть / и д— многочлены и у — замкнутая несамопересекающаяся кривая на комплексной плоскости. Тогда если
|/(-~д(z)| <\f(z)\ + |c?(z)|             (1)

при всех z у, то внутри кривой у расположено одинаковое количество корней многочленов / и д (с учетом их кратностей).

   Доказательство. Рассмотрим на комплексной плоскости векторные поля v(z) = f(z) и w(z) = g(z). Из условия (1) следует, что ни в какой точке кривой у векторы v и w не являются противоположно направленными .
   Напомним, что индексом кривой у относительно векторного поля v называют количество оборотов вектора v(z') при полном обходе точки z вдоль кривой у. (Для более подробного знакомства со свойствами индекса мы советуем обратиться к главе 6 книги [Пр1].) Рассмотрим векторное поле — — t-+(l — t)w. При этом vq = w и гц = v. Ясно также, что

Глава 1. Корни многочленов

в любой точке z е у вектор (z) ненулевой. Это означает, что для кривой у определен индекс ind(t) относительно векторного поля Vf. Целое число ind(t) непрерывно зависит от t, поэтому ind(t) = const. В частности, индексы кривой у относительно векторных полей v и w совпадают.
   Несложно показать, что индекс кривой у относительно векторного поля v равен сумме индексов особых точек, в которых v(z) = 0. (Индекс особой точки zq определяется как индекс кривой |'. — '.₍J| = е, где е достаточно мало.) Для векторного поля v(z) = f(z') индекс особой точки Zq равен кратности корня Zq многочлена /. Таким образом, из совпадения индексов кривой у относительно векторных полей v(z) = f(z') и w(z') = g(z') следует, что внутри кривой у расположено одинаковое количество корней многочленов / и д.                           □


   С помощью теоремы Руше можно не только доказать основную теорему алгебры, но и получить оценку для модуля любого корня многочлена /.


   ТЕОРЕМА 1.2. Пусть f{z) = zⁿ +aizⁿ ¹ + ...+ а„, где а, е С. Тогда внутри круга |z| = 1+max |а,| расположено ровно п корней многочлена f i
(с учетом их кратностей).



   Доказательство. Пусть а = шах|а^|. Многочлен </(z) = zⁿ имеет i
внутри рассматриваемого круга корень 0 кратности п. Поэтому достаточно проверить, что если |z| = 1 + а, то |/( — — д(z)| < |/(z)| + |<?(z)|. Мы даже докажем, что |/( — — д(z)| < |g(z)|, т. е.


|aiz” ¹ + ... + а„| < \z\ⁿ.


   Ясно, что если | z | = 1 + а, то


                                               |aiz + ...+aₙ|sta(|z|      +... + 1) — а-:—:—— — Щ —1<Щ . □
                                           Pl ⁻ 1



1.2. Теорема Коши

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

1. Неравенства для корней

11

   Теорема 1.3 (Коши). Пусть /(ж) — хп — Ь±ж”⁻¹ — ... — Ьп, где все числа bi неотрицательны, причем хотя бы одно из них отлично от нуля. Тогда многочлен / имеет единственный (некратный) положительный корень р, а модули всех остальных корней не превосходят р.


   Доказательство. Положим

У(ж)

_   /(«) _ bi        Ьп
—----~               — —

Если ж 0, то уравнение /(ж) = 0 эквивалентно уравнению F(x) = 0. При возрастании ж от 0 до 1^ функция F(x) строго убывает от 1^ до —1. Поэтому при ж > 0 функция F обращается в нуль ровно в одной точке р. При этом

—Ш ₌ F'{ₚ} ₌ J—_ р           v       р

	

Следовательно, р— некратный корень многочлена /.
   Остается доказать, что если жо — корень многочлена /, то q = = |жо | Р- Предположим, что q > р. Тогда из монотонности функции F следует, что F(q) < 0, т. е. /(g) > 0. С другой стороны, из равенства Жд = ЬхЖр⁻¹ + ... + Ьп следует, что — — big”⁻¹ + ... + bₙ, т. е. /(g) 0.
Приходим к противоречию.                                              □


   Замечание. Теорема Коши непосредственно связана с теоремой Перрона-Фробениуса о неотрицательных матрицах (по этому поводу см. [Wi]).

   У многочлена ж²” — ж” — 1 имеется п корней, модули которых равны модулю положительного корня этого многочлена. Поэтому в теореме Коши утверждение о том, что модули корней не превосходят р, вообще говоря, нельзя заменить на утверждение о том, что модули корней строго меньше р. Но, как показал Островский, в достаточно общей ситуации это можно сделать.

   ТЕОРЕМА 1.4 (Островский). Пусть /(ж) = ж” — Ь±ж”⁻¹ — ... — Ьп, где все числа bi неотрицательны, причем хотя бы одно из них отлично от нуля. Тогда если наибольший общий делитель номеров положительных коэффициентов bi равен 1, то многочлен / имеет единственный положительный корень р, а модули всех остальных корней строго меньше р.

Глава 1. Корни многочленов

   Доказательство. Пусть положительны только коэффициенты Ък,, bk₂, • • • ,bkₘ (fci < fe < ••• < кт). Наибольший общий делитель чисел кт равен 1, поэтому найдутся такие целые числа «1,..., зт, что sifci + ... + sₘkₘ = 1. Снова рассмотрим функцию





|fe-l
Уравнение F(x) = 0 имеет единственное положительное решение р. Пусть х—любой другой (ненулевой) корень многочлена /. Положим q = |ж|. Тогда

т. е. F (q) 0. При этом равенство F(q) =0 возможно лишь в том случае,
когда
bₖᵢ/xkⁱ = \bₖJxk’\ >0


при всех i. Но в таком случае

Ы¹ •... • bf k'.

т.е. х > 0. Это противоречит тому, что х р, ар — единственный положительный корень уравнения F(x) = 0. Таким образом, F(q) > 0. Поэтому из монотонности функции F(x) при положительных х следует, что q < р.                                                 □


   Из теоремы Коши-Островского можно вывести следующую оценку для модуля корней многочлена с положительными коэффициентами.


   Теорема 1.5. а) (Энестрём-Какейа) Если все коэффициенты многочлена д(х) — -хп^¹ + ... + aₙ-i положительны, то для любого корня 5 этого многочлена справедлива оценка


min lai —i-i} = 8 < |£| < Y = {, m;ⁱx {ai —i-i}•
   ——


   б) (Островский) Пусть —iFni, i < у при к = ..., кт. Тогда если
наибольший общий делитель чисел п, , кт равен 1, то |^| < у-

1. Неравенства для корней

13

  Доказательство. Рассмотрим многочлен


     — -                              = '-'■¹'" - (у«о - а₁)хп ¹ 

- (у«п-2 - а„-1)- - уОп-1.

По определению у - сч/сч-i, т. е. усц-х - а» > 0. Поэтому по теореме Коши у — единственный положительный корень многочлена (ж- у)д(х), а модули всех остальных корней этого многочлена не превосходят у.
   Если ⁻ — корень многочлена ⁻, то Г) = 5⁻¹—корень многочлена a,, tyⁿ ' + • • • + а₀. Поэтому


       ISI ¹ = Ini = , max Aai-1/аЛ = ( ₗz“j“ Aai —i-1} ) 1^г^п-1                   yl^^n-1        у




1

Т. С.

|5|>8= min {ai -i-i}.
1C«C«-1

   Когда выполнено условие б), корень у многочлена (ж - у)<Дж) строго больше модулей всех остальных корней этого многочлена.           □


   Замечание. Теорема Энестрёма-Какейа тоже связана с теоремой Перрона-Фробениуса: см. [AnSV].

   Существенное обобщение теоремы Энестрёма-Какейа получено в статье [GG]. При этом отброшено требование вещественности коэффициентов и ослаблено требование их монотонного возрастания. Но формулировка этой теоремы весьма громоздка, поэтому она здесь не приведена.


1.3. Теорема Лагерра


   Пусть zi,..., zₙ е С — точки, которым приписаны единичные массы. Тогда точку С = (zi + • • • + zₙ)/n называют центром масс точек z-\_,...,zₙ. Это понятие можно обобщить следующим образом. Сделаем дробно-линейное преобразование w, переводящее точку zq в ж, т. е.
w(z') = —----1- Ь. Найдем центр масс образов точек zi,..., zₙ, а затем
       - — Zo
сделаем обратное преобразование w⁻¹. Несложные вычисления показывают, что результат не зависит от а и Ь, а именно, мы получаем точку

>«0

          ( ¹
= Zo + п --------yzi — zo

        ¹ А ¹
+ • • • н--)
—i-ZoJ

(1)

— центр масс точек zi,... ,zₙ относительно точки zq.

Глава 1. Корни многочленов

   Центр масс точек zi,...,zₙ лежит внутри их выпуклой оболочки. Это утверждение легко переносится на случай центра масс относительно точки zq. Нужно лишь прямые, соединяющие точки Zi и Zj, заменить окружностями, проходящими через точки z,, Zj и zq. Точка zq, соответствующая точке ж, лежит при этом вне выпуклой оболочки.

   ТЕОРЕМА 1.6. Пусть /(z) = (z — Zi) • ... • (z — z„). Тогда центр масс корней многочлена / относительно произвольной точки z задается формулой
— — — — nf( z)/f'(z).

   Доказательство. Ясно, что f(z)/f( z) = (z-z i)⁻¹+.. .+(z—z „)⁻¹. Требуемое утверждение непосредственно следует из формулы (1). □

   Теорема 1.7 (Лагерр). Пусть /(z) —многочлен степени п и х— его некратный корень. Тогда центром масс всех остальных корней многочлена относительно точки х служит точка

Х = х — 2(n — 1 )//(ж)//"(ж).

   Доказательство. Пусть /(z) = — — x)F(z). Тогда /'(z) = -F(z) + + — — х)F'(z) и f"(z) = 2F'(z) + — — x)F"(z). Поэтому f (x) = F(x) и f"(x) = 2F'(x). Применим предыдущую теорему к многочлену F степени — — 1 и к точке z = х. В результате получим требуемое.     □

   Теорема 1.8 (Лагерр). Пусть /(z) —многочлен степени п и

X(z)=z- 2(п — 1 )f'(z)/f"(z).

Предположим, что окружность (или прямая) С проходит через некратный корень zi многочлена /, а все остальные корни многочлена / принадлежат одной из двух областей, на которые С делит плоскость. Тогда X(zi) принадлежит той же самой области.

   Доказательство. В случае обычного центра масс окружности С соответствует прямая, по одну сторону от которой лежат все корни многочлена, кроме z±. Их центр масс лежит по ту же самую сторону от этой прямой.                                                  □