Rozstrzygalność problemu dotyczącego wielomianów

11

Natknąłem się na następujący interesujący problem: niech będą wielomianami na polu liczb rzeczywistych i załóżmy, że wszystkie ich współczynniki są liczbami całkowitymi (tzn. Istnieje dokładna reprezentacja tych wielomianów). W razie potrzeby możemy założyć, że stopień obu wielomianów jest równy. Oznaczmy przez (resp. ) największa wartość bezwzględna niektórych (rzeczywistej lub zespolonej) pierwiastka wielomianu (resp. ). Czy rozstrzygać o właściwości ? $p,q$ $x_p$ $x_q$ $p$ $q$ $x_p = x_q$

Jeśli nie, to czy ta właściwość obowiązuje dla niektórych ograniczonych rodzin wielomianów? W kontekście, z którego wynika ten problem, wielomiany są charakterystycznymi wielomianami macierzy, a ich pierwiastki są wartościami własnymi.

Zdaję sobie sprawę z niektórych algorytmów numerycznych do obliczania pierwiastków wielomianów / wartości własnych, jednak wydaje się, że tutaj one nie są przydatne, ponieważ dane wyjściowe tych algorytmów są jedynie przybliżone. Wydaje mi się, że algebra komputerowa może się tu przydać, niestety nie mam prawie żadnej wiedzy w tej dziedzinie.

Nie szukam szczegółowego rozwiązania tego problemu, jednak każda intuicja i pomysły na znalezienie rozwiązania byłyby pomocne.

Z góry dziękuję.

computability undecidability computer-algebra

— 042
źródło

Jeśli potrafisz obliczyć pole podziału, możesz je zapisać w postaci i porównać; w przypadku niektórych pól pole podziału nie jest obliczalne, ale nie jestem pewien, czy dotyczy to rozszerzeń ?

(x - x_{0}) (x - x_{1}) \dots

$(x-x_0)(x-x_1)\dots$

Q

$\mathbb{Q}$

— Xodarap,

5

Nie mam również wiedzy w tej dziedzinie, ale myślę, że mogę udzielić niekonstruktywnej odpowiedzi.

Teoria pierwszego rzędu rzeczywistych pól zamkniętych jest rozstrzygalna. Twój problem można określić jako układ równań algebraicznych i nierówności względem rzeczywistych liczb algebraicznych. Rozważ zmienne . Chcesz wiedzieć, czy następujący system jest zadowalający: $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*}

$\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*}$

Pierwsze dwie rodziny równań wyrażają, że i są pierwiastkami wielomianów, kolejne dwie rodziny nierówności wyrażają, że i mają największą wartość bezwzględną, a ostatnie równanie porównuje te największe wartości bezwzględne. $x_j+i\,y_j$ $x'_k+i\,y'_k$ $x_1+i\,y_1$ $x'_1+i\,y'_1$

Można zadecydować, czy ten system jest zadowalający: problem można rozstrzygnąć. Jednak to stwierdzenie nie jest prawdopodobnie najskuteczniejszym sposobem na obejście tego.

Bardziej użyteczna odpowiedź prawdopodobnie dotyczy teorii baz Gröbnera . Jeśli próbujesz rozwiązać ten problem sam, myślę, że przeczytanie kilku pierwszych rozdziałów jakiejkolwiek książki algebry obliczeniowej da ci niezbędne tło. Jeśli chcesz tylko rozwiązać swój podstawowy problem, prawdopodobnie istnieje gotowy algorytm do zaimplementowania.

— Gilles „SO- przestań być zły”
źródło

1

Mogę się mylić w tej kwestii: nie mam zbyt dużej wiedzy w tej dziedzinie (gdzie są eksperci !?), ale uważam, że mam dość szybki algorytm do tego, o co pytasz.

Przypuszczam, dla uproszczenia, że wszystkie korzenie są prawdziwe. Znajdź przedział związany z pierwiastkiem o najwyższej wartości bezwzględnej (tj. Przedział taki, że i dla wszystkich innych pierwiastków ). Taki odstęp można znaleźć dzięki połączeniu dychotomii i twierdzenia Sturma . Teraz obliczenie wielomianowe GCD z i . Sprawdź, czy ma pierwiastek w (ponownie z twierdzeniem Sturma). $P$ $I$ $x_P\in I$ $x_P'\notin I$ $P$ $R$ $P$ $Q$ $R$ $I$

Jeśli nie myli, jest taki jak korzeń tylko wtedy, gdy i mają wspólny pierwiastek , która z kolei jest możliwe tylko wtedy, gdy jest pierwiastkiem . Zarówno zastosowanie twierdzenia Sturma, jak i GCD jest raczej szybkie (w rzeczywistości nie większe niż kwadratowe wielkości wielomianów). $R$ $P$ $Q$ $I$ $x_P$ $Q$

To tylko szkic, ale przekształcenie go w prawdziwy algorytm nie wymaga wiele , w rzeczywistości podejrzewam, że użycie Maple lub Mathematica uczyniłoby to trywialnym.

— cody
źródło