수학에서, 제곱-없는 다항식(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)는 제곱-없는 인수의 거듭제곱으로 분해됩니다:
\(\quad\displaystyle
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_0\)을 계산하는 것으로 구성됩니다.
만약
\(\quad
f = a_1 a_2^2 a_3^3 \cdots a_k^k
\)
이 원하는 인수분해이면, 따라서 우리는 다음을 가집니다:
\(\quad
a_0 = a_2^1 a_3^2 \cdots a_k^{k-1},
\)
\(\quad
f/a_0 = a_1 a_2 a_3 \cdots a_k
\)
그리고
\(\quad\displaystyle
f'/a_0 = \sum_{i=1}^k i a_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'\)을 정하면, 우리는 다음을 얻습니다:
\(\quad
\gcd(b_1,d_1) = a_1,
\)
\(\quad
b_2=b_1/a_1 = a_2 a_3 \cdots a_n,
\)
그리고
\(\quad\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.
\)
이 과정을 \(b_{k+1}=1\)까지 반복하면 우리는 모든 \(a_i\)를 찾을 수 있습니다.
이것은 다음으로 알고리듬으로 형식화됩니다:
\(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로 나눔으로써 얻습니다.
따라서 다항식에 제곱근이 있는지 결정하는 문제와 만약 존재한다면 그것을 계산하는 문제는 제곱-없는 인수분해의 특별한 경우입니다.
Notes
- Yun, David Y.Y. (1976). On square-free decomposition algorithms SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation, pp. 26–35.
- Gianni P., Trager B. (1996). Square-Free Algorithms in Positive Characteristic Applicable Algebra In Engineering, Communication And Computing, 7(1), pp. 1–14.
