Бесквадратный полином

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

подразумевает Правило произведения , что если p ² делит f , то p делит формальную производную f   ′ от f . Обратное также верно и, следовательно, $f$ бесквадратен тогда и только тогда, когда $1$ является наибольшим общим делителем многочлена и его производной.

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

$f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{n}^{n}=\prod _{k=1}^{n}a_{k}^{k}\,$

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

По полю характеристики 0 частное $f$ своим наибольшим общим делителем (НОД) со своей производной является произведением $a_{i}$в приведенном выше бесквадратном разложении. В идеальном поле ненулевой характеристики p это частное является произведением $a_{i}$такой, что i не кратно p . Дальнейшие вычисления НОД и точные деления позволяют вычислить факторизацию без квадратов (см. факторизацию без квадратов по конечному полю ). В нулевой характеристике известен лучший алгоритм — алгоритм Юна, который описан ниже. Его вычислительная сложность не более чем в два раза превышает сложность вычисления НОД входного полинома и его производной. Точнее, если $T_{n}$ — время, необходимое для вычисления НОД двух многочленов степени $n$ и частное этих многочленов по НОД, то $2T_{n}$ является верхней границей времени, необходимого для вычисления полного разложения без квадратов.

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

Алгоритм Юна

В этом разделе описывается алгоритм Юна для разложения одномерных многочленов без квадратов над полем характеристики 0 . Это происходит путем последовательности вычислений НОД и точных делений.

Таким образом, входными данными является ненулевой полином f , и первый шаг алгоритма состоит из вычисления НОД a ₀ для f и его формальной производной f' .

Если

$f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{k}^{k}$

— искомая факторизация, мы имеем, таким образом,

$a_{0}=a_{2}^{1}a_{3}^{2}\cdots a_{k}^{k-1},$

$f/a_{0}=a_{1}a_{2}a_{3}\cdots a_{k}$

и

$f'/a_{0}=\sum _{i=1}^{k}ia_{i}'a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}.$

Если мы установим $b_{1}=f/a_{0}$, $c_{1}=f'/a_{0}$ и $d_{1}=c_{1}-b_{1}'$, мы поняли это

$\gcd(b_{1},d_{1})=a_{1},$

$b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},$

и

$c_{2}=d_{1}/a_{1}=\sum _{i=2}^{k}(i-1)a_{i}'a_{2}\cdots a_{i-1}a_{i+1}\cdots a_{k}.$

Повторяя этот процесс до тех пор, пока $b_{k+1}=1$ мы находим все $a_{i}.$

Это формализуется в виде следующего алгоритма:

$a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;$
повторить
$a_{i}:=\gcd(b_{i},d_{i});\quad b_{i+1}:=b_{i}/a_{i};\quad c_{i+1}:=d_{i}/a_{i};\quad i:=i+1;\quad d_{i}:=c_{i}-b_{i}';$
до $b_{i}=1;$
Выход $a_{1},\ldots ,a_{i-1}.$

Степень $c_{i}$ и $d_{i}$ на единицу меньше степени $b_{i}.$ Как $f$ является продуктом $b_{i},$ сумма степеней $b_{i}$ это степень $f.$ Поскольку сложность вычислений и делений НОД увеличивается более чем линейно с увеличением степени, из этого следует, что общее время работы цикла «повторения» меньше, чем время работы первой строки алгоритма, и что общее время работы Алгоритм Юна ограничен сверху вдвое большим временем, необходимым для вычисления НОД $f$ и $f'$ и частное $f$ и $f'$ по их НОД.

Квадратный корень

В общем, полином не имеет квадратного корня . Точнее, большинство многочленов нельзя записать в виде квадрата другого многочлена.

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

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