Разрешимость задачи о полиномах

Я столкнулся со следующей интересной проблемой: пусть - многочлены над полем действительных чисел, и предположим, что все их коэффициенты целочисленные (то есть существует конечное точное представление этих многочленов). При необходимости можно предположить, что степень обоих полиномов равна. Обозначим через (соответственно ) наибольшее абсолютное значение некоторого (действительного или комплексного) корня многочлена (соответственно ). Является ли свойство разрешимым?$p,q$$x_p$$x_q$$p$$q$$x_p = x_q$

Если нет, верно ли это свойство для некоторых ограниченных семейств полиномов? В контексте, из которого возникает эта проблема, полиномы являются характеристическими полиномами матриц, а их корни являются собственными значениями.

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

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

Заранее спасибо.

Я не обладаю знаниями в этой области, но я думаю, что могу дать неконструктивный ответ.

Теория вещественных замкнутых полей первого порядка разрешима. Ваша проблема может быть сформулирована в виде системы алгебраических уравнений и неравенств над действительными алгебраическими числами. Рассмотрим переменные . Вы хотите знать , является ли выполнимо следующая система: $2 (\deg P + \deg Q)$$x_1,\ldots,x_{\deg P}, y_1,\ldots,y_{\deg P}, x'_1,\ldots,x'_{\deg P}, y'_1,\ldots,y'_{\deg P}$

$$\begin{align*} P(x_j+i\,y_j) &= 0 & \text{for \(1 \le j \le \deg P\)} \\ Q(x'_k+i\,y'_k) &= 0 & \text{for \(1 \le k \le \deg Q\)} \\ x_j^2 + y_j^k &\le x_1^2 + x_2^2 & \text{for \(2 \le j \le \deg P\)} \\ x'_j^2 + y'_j^k &\le x'_1^2 + x'_2^2 & \text{for \(2 \le k \le \deg Q\)} \\ x_1^2 + y_1^2 = x'_1^2 + y'_1^2 \\ \end{align*}$$

Первые два семейства уравнений выражают, что и являются корнями полиномов, следующие два семейства неравенств выражают, что и имеют наибольшее абсолютное значение, и последнее неравенство сравнивает эти самые большие абсолютные значения.$x_j+i\,y_j$$x'_k+i\,y'_k$$x_1+i\,y_1$$x'_1+i\,y'_1$

Это разрешимо ли выполнима эта система: ваша проблема разрешима. Однако, это утверждение, вероятно, не самый эффективный способ пойти об этом.

Более полезный ответ , вероятно , включает в себя теорию Грёбнера . Если вы пытаетесь решить эту проблему для себя, я думаю, что чтение первых нескольких глав любой книги по вычислительной алгебре даст вам необходимую справочную информацию. Если вы просто стремитесь решить основную проблему, вероятно, есть готовый алгоритм, который вы можете реализовать.

Я могу ошибаться по этому поводу: я также не очень хорошо осведомлен в этой области (где эксперты !?), но я считаю, что у меня есть достаточно быстрый алгоритм для того, что вы спрашиваете.

Я буду предполагать, для простоты, что все корни вещественны. Найти интервал , связанный с корнем с наивысшим абсолютным значением (т.е. интервал такой , что и для всех остальных корней ). Такой интервал может быть найден при совместном использовании дихотомии и теоремы Штурма . Теперь вычислить многочлен НОД в и . Убедитесь в том, что имеет корень в (опять - таки с теоремой Штурма).I x P ∈ I x ′ P ∉ I P R P Q R $P$$I$$x_P\in I$$x_P'\notin I$$P$ $R$$P$$Q$$R$$I$

Если я не ошибаюсь, имеет такой корень тогда и только тогда , когда и имеют общий корень в , который , в свою очередь , возможно только в том случае является корнем . Как применение теоремы Штурма, так и GCD довольно быстрые (на самом деле не более квадратичного по размеру полиномов).P Q I x P$R$$P$$Q$$I$$x_P$$Q$

Это всего лишь набросок, но не нужно много, чтобы превратить его в добросовестный алгоритм, на самом деле я подозреваю, что использование Maple или Mathematica сделает это тривиальным.