平方自由多項式

数学において、平方自由多項式は、その係数を含む代数的に閉じた体で多重根を持たない一変数多項式（体または積分領域上）である。特性0において、または有限体上で、一変数多項式が平方自由であるためには、非定数多項式の平方を約数として持たない必要がある。^[1]物理学や工学の分野では、平方自由多項式は一般に重根を持たない多項式と呼ばれる。

積の法則は、p ^{2 が}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のものは、互いに素な二乗自由多項式です（ここで、2 つの多項式が互いに素であると言われるのは、それらの最大公約数が定数である場合です。言い換えると、考慮される係数の分数の体上で互いに素であるということです）。 ^[1]すべての非ゼロ多項式は、非ゼロ定数による因数の乗算と除算を除いて一意である二乗自由因数分解を許容します。二乗自由因数分解は、既約因数への完全因数分解よりもはるかに計算が容易であるため、部分分数分解や有理分数の記号積分など、完全な因数分解が実際には必要ない場合によく使用されます。二乗自由因数分解は、コンピュータ代数システムに実装されている多項式因数分解アルゴリズムの最初のステップです。したがって、二乗自由因数分解アルゴリズムは、コンピュータ代数の基本です。

特性0の体上で、をその最大公約数 (GCD) でその導関数で割った商は、上記の平方自由分解における の積です。特性p がゼロでない完全体上では、この商は、 iがpの倍数ではないの積です。さらに GCD 計算と正確な除算を行うと、平方自由因数分解を計算できます (有限体上の平方自由因数分解を参照)。特性 0 では、より優れたアルゴリズムが知られています。Yun のアルゴリズムについては以下で説明します。^[1]この計算の複雑さは、最大でも、入力多項式とその導関数の GCD 計算の 2 倍です。より正確には、 が次数の 2 つの多項式の GCDと、これらの多項式の GCD による商を計算するために必要な時間である場合、 は完全な平方自由分解を計算するために必要な時間の上限です。 ${\displaystyle f}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$${\displaystyle T_{n}}$${\displaystyle n}$${\displaystyle 2T_{n}}$

多変量多項式の平方自由分解のためのアルゴリズムも知られており、これは一般的に多変量多項式を多項式係数を持つ単変量多項式として考え、単変量アルゴリズムを再帰的に適用することによって進む。^[3]

この節では、特性0の体上の一変数多項式の平方自由分解のためのYunのアルゴリズムについて説明します。^[1]これは、一連のGCD計算と正確な除算によって進行します。

したがって、入力はゼロ以外の多項式fであり、アルゴリズムの最初のステップはfのGCD a ₀とその形式導関数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 \gcd(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}:=\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;}$
出力 まで 繰り返す
${\displaystyle 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}';}$
${\displaystyle b_{i}=1;}$
${\displaystyle a_{1},\ldots ,a_{i-1}.}$

との次数はの次数より 1 小さいです。はの積であり、の次数の合計は の次数です。GCD の計算と除算の複雑さは次数とともに直線的に増加するため、「繰り返し」ループの合計実行時間はアルゴリズムの最初の行の実行時間よりも短くなり、Yun のアルゴリズムの合計実行時間は と の GCDとと の商をそれらの GCD で計算するのに必要な時間の 2 倍で上限が設定されます。 ${\displaystyle c_{i}}$${\displaystyle d_{i}}$${\displaystyle b_{i}.}$${\displaystyle f}$${\displaystyle b_{i},}$${\displaystyle b_{i}}$${\displaystyle f.}$${\displaystyle f}$${\displaystyle f'}$${\displaystyle f}$${\displaystyle f'}$

一般に、多項式には多項式の平方根はありません。より正確に言うと、ほとんどの多項式は別の多項式の平方として表すことはできません。

多項式が平方根を持つのは、平方根分解のすべての指数が偶数である場合のみです。この場合、平方根はこれらの指数を 2 で割ることで得られます。

したがって、多項式に平方根があるかどうかを判定し、存在する場合はそれを計算する問題は、平方根のない因数分解の特殊なケースです。