Разложение полинома в сумму квадратов

[YuryS]

Добрый день !

Есть такой вопрос - дан многочлен от нескольких переменных с целочисленными коэффициентами $h\in \mathbb{Z}[x_{1}, ... , x_{n}]$.
Требуется разложить его в сумму квадратов двух аналогичных полиномов $f$ и $g$, т.е., $h = f^{2} + g^{2}$.
Эту задачу можно решать общим методом, пытаясь найти разложение исходного полинома $h$ в произведение двух полиномов в (факториальном) кольце гауссовых полиномов, т.е., ища разложение $h = (f + ig)(f-ig) $.
Однако, для больших полиномов h системы компьютерной алгебры вычисляют такое разложение бесконечно долго - например, полином от 6 переменных с общей степенью 28 главного монома считался сутки, но не дал результата.
Существуют ли быстрые алгоритмы решения этой задачи специальными, именно для этой задачи предусмотренными , методами ?
Различные ИИ (LLMs) не дают ответа на этот вопрос.

[Alex Krylov]

По запросу SOS Programming не искали?

[dgwuqtj]

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

[YuryS]

Alex Krylov в сообщении #1714886 писал(а):

По запросу SOS Programming не искали?

По этой теме , в основном, ответы по оптимизации, т.е., про полиномы с вещественными коэффициентами. Задача же стоит про полиномы с целочисленными коэффициентами, т.е., это область диофантовых уравнений.

-- Чт янв 15, 2026 16:57:08 --

dgwuqtj в сообщении #1714887 писал(а):

Я не уверен, что в общем случае это сильно проще, чем факторизация.

Я общим случаем называю как раз факторизацию - разложение в произведение.
Интересует же (алгоритмическое) решение именно специальной задачи - разложения на сумму квадратов.

[Alex Krylov]

Есть вот такая, например, штука (лично не пробовал):
SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic
https://www.unilim.fr/pages_perso/simone.naldi/papers/2017_spectra.pdf
Один из авторов, Didier Henrion, видный представитель в данной области (SOS).

Т.е., если задача небольшой(!) размерности, можно попробовать получить "exact certificate of SOS-representability or NON-representability"

[YuryS]

Alex Krylov в сообщении #1714944 писал(а):

SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic

Да, спасибо, поизучаю.

[Alex Krylov]

Я вот что имею в виду...

Пусть $p$ - многочлен, для которого нам надо получить SOS-представление или удостовериться, что оно существует. Пусть $v$ - вектор мономов. Тогда должно выполняться $p=v^T Q v$, где симметричная матрица $Q$ должна быть неотрицательно определенной. Вот это $p=v^T Q v$ означает, кто коэффициенты при мономах должны быть равны, т.е. имеем систему линейных ограничений в форме равенств, от которых избавляемся, находя общее решение СЛАУ и подставляя его в $P$. В результате имеем одно линейное матричное неравенство, для которого надо решить "feasibility problem".

И якобы вышеуказанная программулька (для задач небольшой размерости) может проделывать подобные вещи в явной арифметике.