Square-free polynomial

Original article: w:Square-free polynomial

수학에서, 제곱-없는 다항식(square-free polynomial)은 비-단위(unit) 인수의 임의의 제곱을 인수로 가지지 않는 필드(field) (또는 보다 일반적으로, 고유한 인수분해 도메인(unique factorization domain))에 걸쳐 정의된 다항식(polynomial)입니다. 필드 k에 걸쳐 일변수 다항식의 중요한 경우에서, 이것은 $f\in k[X]$이 제곱-없는 것과 양의 차수의 모든 각 다항식 $b\in k[X]$에 대해 $b^{2}\nmid f$인 것은 필요충분 조건임을 의미합니다. 물리학 및 공학 분야의 응용에서, 제곱-없는 다항식은 공통적으로 반복된 근을 갖지 않는 다항식(polynomial with no repeated roots)이라고 불립니다. 그러한 다항식은 분해 가능(separable)이라고 부르지만, 완전 필드에 걸쳐 분해 가능인 것은 제곱-없는 것과 동일합니다.

다항식의 제곱-없는 인수분해(square-free factorization) 또는 제곱-없는 분해(square-free decomposition)는 제곱-없는 인수의 거듭제곱으로 분해됩니다:

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

여기서 1과 같지 않은 a_k의 그들은 쌍별 서로소(pairwise coprime) 제곱-없는 다항식입니다. 필드(field)에서 계수를 갖는 모든 각 비-영 다항식은 제곱-없는 인수분해를 허용하고, 이는 비-영 상수에 의해 인수의 곱셈까지(up to) 고유합니다. 제곱-없는 인수분해는 기약(irreducible) 인수에 대한 완전 인수분해(factorization)보다 훨씬 쉽게 계산할 수 있고, 따라서 부분 분수(partial fraction) 분해와 유리수 분수(rational fraction)의 기호적 적분(symbolic integration)에 대해, 완전 인수분해가 실제로 필요하지 않을 때 종종 선호됩니다. 제곱-없는 인수분해는 컴퓨터 대수학 시스템(computer algebra system)에서 구현되는 다항식 인수분해(polynomial factorization) 알고리듬의 첫 번째 단계입니다. 그러므로, 제곱-없는 인수분해의 알고리듬은 컴퓨터 대수학(computer algebra)에서 기본입니다.

필드에 걸쳐 일변수(univariate) 다항식의 경우에서, 다항식의 임의의 중복 인수는 f의 자명하지 않은 공통 인수와 그것의 형식적 도함수(formal derivative) f ′를 유도하므로, 제곱-없는 것이 되는 f에 대해 충분 조건은 f의 최대 공약수(greatest common divisor)와 f ′이 1인 것입니다. 이 조건은 특성 0의 필드에 걸쳐, 또는 보다 일반적으로, 완전 필드(perfect field)에 걸쳐 필요이며, 왜냐하면 그러한 필드에 걸쳐, 모든 각 기약 다항식은 분해 가능(separable)하고, 따라서 그의 도함수와 서로소(coprime)이기 때문입니다.

특성 0의 필드에 걸쳐, 그의 GCD와 함께 그의 도함수에 의해 $f$의 몫은 위의 제곱-없는 분해에서 $a_{i}$의 곱입니다. 비-영 특성 p의 완전 필드에 걸쳐, 이 몫은 i가 p의 중복이 아닌 것을 만족하는 $a_{i}$의 곱입니다. 게다가 GCD 계산과 정확한 나눗셈은 제곱-없는 인수분해를 계산하는 것을 허용합니다 (유한한 필드에 걸쳐 제곱-없는 인수분해(square-free factorization over a finite field)를 참조하십시오). 특성 영에서, 아래에 설명된 윤의 알고리듬이 더 좋은 알고리듬으로 알려져 있습니다. 그의 계산 복잡도(computational complexity)는, 많아야, 입력 다항식과 그의 도함수의 GCD 계산의 2배입니다. 더 정확하게 말하면, 만약 $T_{n}$이 차수 $n$의 다항식과 GCD에 의한 이들 다항식의 몫의 GCD를 계산하기 위한 필요한 시간이라면, $2T_{n}$은 제곱-없는 분해를 계산하기 위해 필요한 시간의 위쪽 경계입니다.

다변수 다항식의 제곱-없는 분해의 계산에 대해 알려진 알고리듬이 역시 있습니다.

Yun's algorithm

이 절은 특성 0(characteristic 0)의 필드에 걸쳐 일변수 다항식의 제곱-없는 분해에 대해 윤의 알고리듬을 설명합니다. 그것은 GCD 계산과 완전 나눗셈의 연속에 의해 진행됩니다.

입력은 따라서 비-영 다항식 f이고, 알고리듬의 첫 번째 단계는 f와 그의 형식적 도함수(formal derivative) f'의 GCD a₀을 계산하는 것으로 구성됩니다.

만약

$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;$
repeat
$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}';$
until $b=1;$
Output $a_{1},\ldots ,a_{i-1}.$

$c_{i}$와 $d_{i}$의 차수는 $b_{i}$의 차수보다 일 작습니다. $f$가 $b_{i}$의 곱이기 때문에, 합은 $b_{i}$의 차수의 합은 $f$의 차수입니다. GCD 계산 및 나눗셈의 복잡도는 차수와 함께 선형 이상으로 증가하기 때문에, "반복"("repeat") 루프의 전체 실행 시간은 알고리듬의 첫 번째 줄의 실행 시간보다 작고, 윤의 알고리듬의 전체 실행 시간은 $f$와 $f'$의 GCD 그리고 그들 GCD에 의한 $f$ and $f'$의 몫을 계산하기 위해 필요한 시간의 두 배에 의해 위쪽 경계됩니다.

Square root

일반적으로, 다항식은 제곱근(square root)을 가지지 않습니다. 보다 정확하게, 대부분의 다항식은 다른 다항식의 제곱으로 쓸 수 없습니다.

다항식이 제곱근을 가지는 것과 제곱-없는 분해의 모든 지수가 짝수인 것은 필요충분 조건입니다. 이 경우에서, 제곱근은 이들 지수로 2로 나눔으로써 얻습니다.

따라서 다항식에 제곱근이 있는지 결정하는 문제와 만약 존재한다면 그것을 계산하는 문제는 제곱-없는 인수분해의 특별한 경우입니다.