3.2.4. Разложение полиномов на свободные от квадратов множители

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

Пусть J — произвольная числовая область; определим производную полинома следующими двумя правилами: для и следует отметить, что если Напомним, что для производных имеет место известное правило произведения

Теорема 3.2.17. Пусть J — область с однозначным разложениемг к а множители характеристики нуль, и пусть — примитивный отличный от константы полином в - Пусть — однозначное разложение полинома на неприводимые сомножители и — его производная. Тогда

Доказательство. Пусть . Тогда и

откуда следует, что Покажем методом от противного, что не делит Предположим, что

тогда откуда мы заключаем, что делит После сокращений в последнем соотношении мы получаем однако, поскольку полиномы взаимно просты, и, стало быть, . Это и есть нужное противоречие, поскольку из следует, что Таким образом степень равна и из соображений симметрии мы получаем что и требовалось доказать.

Из теоремы 3.2.17 мы заключаем, что если , то не имеет кратных сомножителей, и наоборот. Справедливо также

Следствие 3.2.18. Простые корни полинома не являются корнями его производной.

Следствие 3.2.19. Пусть J — поле и — неприводимый полином в который делит . Тогда если и только если

Доказательство. Поскольку мы можем записать и, следовательно, Значит, если то и очевидно, что Обратно, если то и по теореме делит или или Однако и, следовательно, откуда вытекает, что

Мы теперь готовы обсуждать алгоритм разложения на свободные от квадратов множители. Пусть — примитивный полином положительной степени от одной переменной, определенный на J, области с однозначным разложением на множители. [Как мы видели, выбирая примитивным, мы не ограничиваем общности.] Предположим, что — разложение на неприводимые множители положительной степени, так что для каждого , и пусть для положим

Тогда, очевидно,

что называется разложением полинома на свободные от квадратов множители. [Заметим, что некоторые из полиномов

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

[ здесь не присутствует]. Тогда наибольший свободный от квадратов делитель полинома равен

и, следовательно,

Поэтому , т.е. первый свободный от квадратов сомножитель полинома может быть вычислен с помощью дифференцирования, вычисления и деления. Повторяя процесс с вместо мы можем вычислить как первый свободный от квадратов сомножитель полинома и в конечном счете получить все свободные от квадратов сомножители полинома Итак, мы имеем следующий алгоритм:

PSQFF.

Разложение полиномов на свободные от квадратов множители (Polynomial Squarefree Factorization)

Вход: — примитивный полином положительной степени от одной переменной над областью J характеристики нуль с однозначным разложением на множители.

Выход: Полиномы и число такие, что — разложение полинома на свободные от квадратов множители.

1. [Инициализация]

2. [Конец?]

3. [Вычисление

4. [Обновление] перейти к шагу 2.

Анализ времени работы алгоритма PSQFF.

Ясно, что время работы этого алгоритма доминируется вычислениями имеющими место на шаге 3.

Если то ограничивает число выполнений цикла (состоящего из шагов 2, 3, и 4), в котором находится шаг 3. Кроме того, время, необходимое для вычисления на шаге 1, — это верхняя граница времени каждого вычисления на шаге 3. Имеют место:

Случай а. Полином принадлежит где J — поле. В этом случае вычисляется за время и так как имеется выполнений шага 3, то

Случай b. Полином принадлежит , где . В этом случае, как мы увидим в гл. 5, вычисляется за время и снова, поскольку имеется выполнений шага 3,

Дополнительную информацию об алгоритме разложения на свободные от квадратов множители можно найти в книгах (Wang, Trager, 1979) и Мы завершаем этот раздел примером, в котором неявно используется информация из гл. 5, а именно как вычислять

Пример. Найдем свободные от квадратов сомножители полинома Применяя алгоритм PSQFF, получаем при первом проходе: что указывает на отсутствие линейных сомножителей. При втором проходе мы имеем значит, это означает, что — сомножитель исходного полинома. В начале третьего и последнего прохода мы имеем и на шаге 2 видим, что степень полинома равна нулю; следовательно, т.е. — также сомножитель исходного полинома. Таким образом,