Глава 3. Полиномы

В этой главе мы познакомимся с полиномами; мы обнаружим, что с многих точек зрения полиномиальная арифметика родственна арифметике целых чисел: для полиномов имеется некоторая версия алгоритма Евклида и даже греко-китайская теорема об остатках. И еще многое из того, что мы узнали о целых числах (системы вычетов и т.д.), можно обобщить на полиномы, и здесь имеется бесконечно много приложений. Наиболее важным приложением полиномов с целыми коэффициентами является построение полей Галуа, которые играют ключевую роль в вычислительных науках.

3.1. Основные понятия

В этом разделе мы формально вводим полиномы и исследуем различные алгоритмы выполнения операций над ними. Мы будем главным образом интересоваться полиномами над кольцом целых чисел и над (конечными) полями. Читатель должен помнить об этом при изучении материала, поскольку полиномы по-разному «ведут себя» над этими двумя различными алгебраическими структурами.

3.1.1. Основные сведения о полиномах

Пусть J — область целостности к — неизвестная, т.е. — это не независимый элемент области J, а просто формальный символ. Выражение вида

где , называется полиномом от с коэффициентами из J или полиномом от над J; в этой книге мы будем использовать обе формы записи полиномов. Каждое выражение называется членом степени i полинома Если коэффициент при не равен 0, то — степень полинома; она обозначается

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

Два полинома с коэффициентами в J равны тогда и только тогда, когда для всех . Для этих полиномов определяем их сумму и произведение следующим образом:

Ясно, что и сумма, и произведение полиномов представляют собой некоторый полином от с коэффициентами из той же самой области целостности J. Мы можем теперь легко показать, что множество полиномов от с коэффициентами из области целостности J само является областью целостности, обозначаемой содержит как J, так и неизвестную Чтобы в этом убедиться, рассмотрим полиномы определенные выше; покажем, что где 0 обозначает нулевой полином Предположим, что так что . Отсюда следует, что поскольку являются элементами области целостности J. Однако — это коэффициент при в произведении следовательно, что означает отсутствие в делителей нуля.

Следует заметить, что равенство полиномов, как оно определено выше, — это не то же самое, что равенство функций, несмотря на то что любой полином из определяет на J функцию путем подстановки, т.е. функция, определенная полиномом отображает любой элемент j из J в Однако, как вы помните, две функции равны в точности тогда, когда они имеют равные значения для каждого элемента из J, и возможно, что два полинома определяют одну и ту же функцию на J, не будучи равными как полиномы. Например, в кольце полиномы не равны как полиномы, но

так что они равны как функции на В общем случае если J — область целостности с элементами где нуль и единица соответственно, то полином

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

Тот факт, что мы можем ставить полиному в соответствие целое число 0, его степень, является чрезвычайно полезным, потому что это позволяет нам переносить на полиномы доказательства по индукции того же типа, что мы использовали для целых чисел. Ниже приводятся приложения.

Рассмотрим полином [мы говорим, что — не тождественный нуль]. Полином делится на полином если существует полином такой, что в этом случае мы пишем . Степень полинома не превосходит степени полинома если, конечно, называется делителем или сомножителем полинома Отметим, что определенная так делимость не совпадает с введенной ранее делимостью целых чисел; например, имеет место, если и 5 и 7 рассматриваются как полиномы степени 0, в то время как целое число 5 не делит 7.

Теорема 3.1.1 (свойство евклидовости). Пусть J — область целостности; кроме того, пусть — стхт два полинома степеней в кольце и пусть обратим в J. Тогда существуют единственные полиномы (частное и остаток соответственно), такие, что

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

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

В гл. 5 мы обсуждаем, что случится, если не является обратимым в кольце J. Заметим, что если J — поле, то для наличия свойства евклидовости или деления достаточно, чтобы полином-делитель был отличен от нуля.

Мы имеем следующую процедуру, которая является хорошо известным синтетическим алгоритмом деления:

PDF. Полиномиальное деление над полем (Polynomial Division over a Field)

Вход: над полем, (Этот алгоритм будет работать и над областью целостности J при условии, что обратим в

Выход: обладающие свойством евклидовости (теорема 3.1.1).

1. [Основной цикл] для от до 0 выполнять для j от до к выполнять

2. [Выход] Вернуть , коэффициенты полинома вычисленного на шаге , коэффициенты полинома , где также вычисляются на шаге 1).

Анализ времени работы алгоритма PDF. Во все время работы алгоритма операции сложения, умножения и деления коэффициентов выполняются в поле (арифметика с одинарной точностью), и поэтому каждая операция выполняется за время

Шаг 1, основной цикл, очевидно доминирует во времени работы алгоритма. Этот цикл, очевидно, выполняется раз и при каждом выполнении имеет место одно деление и пересчитывается

коэффициентов. Поэтому шаг 1 выполняется за время и

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

Пример. Рассмотрим полиномы с целыми коэффициентами. Поскольку старший коэффициент полинома равен 1, мы можем применить PDF и получить

Если мы будем выписывать только коэффициенты, то получим следующую таблицу:

Пусть J — область целостности, и рассмотрим из Если а то можно разделить на (это может быть выполнено, поскольку коэффициент при обратим) и получить

т.е. — константа из кольца J. Мы говорим, что а — коремъ или нуль полинома если

Имеет место следующая

Теорема 3.1.2. Пусть J — область целостности, Тогда а — корень полинома если и только если

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

Следствие 3.1.3. Пусть J — область целостности, Тогда, если мы разделим на то остаток равен

Пример. Рассмотрим полином имеющий корни —1 и 2. Тогда, очевидно, ; более того, если мы разделим на , то получим в остатке следующем разделе мы увидим, как эффективно вычислять значение полинома в данной точке.

Если а — корень полинома , то называется кратностью корня а; если , то а называется простым корнем.

Имеет место следующая

Теорема 3.1.4. Пусть J — область целостности и — полином из Если степень полинома равна , то имеет не более корней с учетом кратностей. Эти корни лежат в J или в большей области.

Доказательство. Предположим, что — различные корни полинома в J или в большей области. (Случай кратных корней мы оставляем читателю.) Мы будем доказывать по индукции, что делится на Для это выполняется по теореме 3.1.2. Пусть предположение индукции верно для тогда можно представить в виде для некоторого Однако при мы получаем поскольку все корни различны, отсюда следует, что . Снова пользуясь теоремой 3.1.2, получаем и, следовательно, более того, из последнего выражения видно, что m не может быть больше, чем , поскольку при полином является константой, и это завершает доказательство теоремы.

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

Пример. Рассмотрим полином с коэффициентами из кольца содержащего делители нуля. Этот полином имеет четыре корня, а именно 1, —1 (или 7), 3 и 5.

Следствие 3.1.5. Пусть J — область целостности и Если степень полинома равна имеет больше, чем , корней, то

Теперь можно доказать следующую теорему.

Теорема 3.1.6. Пусть J — область целостности с единицей. Если она имеет бесконечное число элементов, то два различных полинома из всегда определяют различные полиномиальные функции.

Доказательство. Разность двух данных полиномов определяет функцию кото является разностью полиномиальных функций определенных полиномами соответственно. Если функции равны, то их разность должна быть равна 0 для любого из J. Однако из этого следует, что каждый элемент кольца J будет корнем полинома т.е. если то имеет больше, чем корней, откуда следует, что Поэтому