Коротко: над полем нулевой характеристики (в частности над $\mathbb{Q}$ или $\mathbb{Z}$ при учёте примитивности) многочлен $P(x)$ делится на квадрат непостоянного многочлена тогда и только тогда, когда $P$ имеет общий ненулевой множитель с производной $P^{\prime }$, то есть
$$\gcd (P,P^{\prime })\ne 1.$$
Пояснения и алгоритм
1) Критерий (теоретическое основание).
- Если $P={\prod }_i{f}_i^{e_i}$ — разложение по неприводимым множителям в алг. замыкании, то $P$ содержит квадрат ненулевого многочлена $⟺$ существует $i$ с $e_i\ge 2$. В нулевой характеристике это эквивалентно $\gcd (P,P^{\prime })$ имеет положительную степень (потому что $P^{\prime }$ аннулирует все простые факторы, оставляя те, у которых степень $\ge 1$).
- Следствие: над $\mathbb{Q}[x]$ достаточно вычислить $G=\gcd (P,P^{\prime })$. Если $\mathrm{deg}G\ge 1$, то есть повторный фактор.
2) Как найти сам максимальный квадратный делитель $Q^2$ (алгоритм получения $Q$).
- Выполнить квадратнобезличное разложение (squarefree factorization). Стандартный алгоритм:
1. Пусть $G:=\gcd (P,P^{\prime })$, $A:=P/G$, $i:=1$.
2. Пока $A\ne 1$:
- $B:=\gcd (A,G)$.
- $F_i:=A/B$. Тогда $F_i$ — квадратнобезличный множитель, встречающийся в степени $i$ в разложении $P$.
- Записать $F_i$ с кратностью $i$.
- Положить $A:=B,G:=G/B,i:=i+1$.
3. Если в конце $G\ne 1$, остальные множители имеют степени $\ge i$ и разбираются аналогично (алгоритм выходит за рамки краткого описания, но это стандартный PRS-подход).
- После получения $P={\prod }_i{F}_i^i$ максимальный многочлен $Q$ с $Q^2\mid P$ равен
$$Q=\prod _i{F}_i^{\lfloor i/2\rfloor }.$$
3) Практические замечания (для вычислительной реализации)
- Работать в $\mathbb{Q}[x]$ удобнее: сначала вынести содержание (content) из $P$ (по Гауссу), работать с примитивной частью в $\mathbb{Z}[x]$ или прямо в $\mathbb{Q}[x]$.
- Для устойчивого вычисления $\gcd$ на целых коэффициентах используют субрест-алгоритм (subresultant PRS) или модульные методы (вычислять $\gcd$ по модулю нескольких простых $p$ и поднимать результат по CRT). При выборе модульных простых нужно исключать простые, делящие начальный коэффициент или дискриминант, чтобы не получить ложные результаты из-за особых характеристик.
- Для больших коэффициентов и степеней рекомендуется модульный/латинный подход; для практических CAS есть готовые реализации squarefree_factorization.
4) Примеры
- $P(x)=(x^2+1{)}^2$. Тогда $P^{\prime }=4x(x^2+1)$, $\gcd (P,P^{\prime })=x^2+1\ne 1$. Получаем $Q=x^2+1$.
- $P(x)=x^5$. Тогда $P^{\prime }=5x^4$, $\gcd (P,P^{\prime })=x^4$; максимальный $Q=x^2$ (потому что $x^4=(x^2{)}^2$ и большая степень даёт более высокий квадрат).
- $P(x)=x^2+1$. Тогда $P^{\prime }=2x$, $\gcd =1$ — квадратного делителя нет.
5) Граничные случаи и где наивные методы подводят
- Сведение по модулю простого $p$: $\gcd (P,P^{\prime })$ по модулю $p$ может быть ненулевым хотя в $\mathbb{Q}[x]$ он тривиален (и наоборот), если $p$ делит коэффициенты так, что появляется вырождение (например, совпадение корней мод $p$). Нельзя полагаться на один простой модуль без проверки.
- Численные методы (приближённые корни) легко путают близкие простые корни с кратными; для гарантии нужен точный алгебраический критерий (gcd).
- Производная равна нулю (т.е. $P^{\prime }\equiv 0$) только в характеристике $p>0$ для особых форм (напр., $x^p$ в char $p$). В характеристике 0 такой проблемы нет.
- Вопрос о делимости в $\mathbb{Z}[x]$ vs $\mathbb{Q}[x]$: по лемме Гаусса делимость на квадрат в $\mathbb{Q}[x]$ эквивалентна делимости на квадрат примитивного множителя в $\mathbb{Z}[x]$ с учётом рациональных констант; на практике перед проверкой удобно привести $P$ к примитивной целой части.
- Попытки обнаружить квадратный делитель просто проверкой дискриминанта: дискриминант ноль ⇔ есть кратный корень, но вычисление дискриминанта может быть дорого и подвержено переполнению; кроме того, дискриминант может быть 0 из-за кратных корней, и это по сути то же, что $\gcd (P,P^{\prime })\ne 1$, но вычислительно менее удобен.
Краткий итог действий для практической проверки
1. Убедиться, что работаем в нулевой характеристике (например, над $\mathbb{Q}$).
2. Вынести содержание $\mathrm{cont}(P)$ и взять примитивную часть.
3. Вычислить $G=\gcd (P,P^{\prime })$ (субрекурсивно или модульно).
4. Если $\mathrm{deg}G\ge 1$, то квадратный делитель существует; для получения максимального $Q$ сделать squarefree-разложение и взять $\prod F_i^{\lfloor i/2\rfloor }$.
Если нужно, могу дать короткую реализацию шагов в псевдокоде или пример вычисления через конкретную САD/алгоритм для заданного числового многочлена.