Бесквадратный многочлен

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

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

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

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

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

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

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

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

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

Если

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

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

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

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

и

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

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

${\displaystyle \НОД(b_{1},d_{1})=a_{1},}$

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

и

${\displaystyle 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}.}$

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

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

${\displaystyle a_{0}:=\НОД(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;}$
повторять до тех пор , пока не появится результат
${\displaystyle a_{i}:=\НОД(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}';}$
${\displaystyle b_{i}=1;}$
${\displaystyle a_{1},\ldots ,a_{i-1}.}$

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

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

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

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