Decidibilidade de um problema relativo a polinômios

11

Eu me deparei com o seguinte problema interessante: sejam polinômios sobre o campo dos números reais e suponhamos que seus coeficientes sejam todos inteiros (ou seja, existe uma representação exata finita desses polinômios). Se necessário, podemos supor que o grau de ambos os polinômios seja igual. Vamos denotar por (resp. ) o maior valor absoluto de alguma raiz (real ou complexa) do polinômio (resp. ). A propriedade decidível? $p,q$ $x_p$ $x_q$ $p$ $q$ $x_p = x_q$

Caso contrário, essa propriedade é válida para algumas famílias restritas de polinômios? No contexto em que esse problema surge, os polinômios são polinômios característicos das matrizes e suas raízes são valores próprios.

Estou ciente de alguns algoritmos numéricos para calcular raízes de polinômios / autovalores, no entanto, estes parecem não ser úteis aqui, pois a saída desses algoritmos é apenas aproximada. Parece-me que a álgebra computacional pode ser útil aqui, no entanto, infelizmente, eu não tenho quase nenhum conhecimento nesse campo.

Não estou procurando uma solução detalhada para esse problema; no entanto, qualquer intuição e idéias para procurar a solução seriam úteis.

Agradeço antecipadamente.

computability undecidability computer-algebra 042
fonte

Se você pode calcular o campo de divisão, basta escrevê-los no formato e comparar; para alguns campos, o campo de divisão não é computável, mas não tenho certeza se isso vale para extensões de ?

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

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

Q

$\mathbb{Q}$

Xodarap 15/10/12

5

Também não conheço esse campo, mas acho que posso fornecer uma resposta não construtiva.

A teoria de primeira ordem dos campos fechados reais é decidível. Seu problema pode ser declarado como um sistema de equações e inequações algébricas sobre os números algébricos reais. Considere variáveis $2 (\deg P + \deg Q)$ . Você deseja saber se o seguinte sistema é satisfatório: $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 *}

Gilles 'SO- parar de ser mau'
fonte

1

Eu posso estar errado sobre isso: também não tenho muito conhecimento neste campo (onde estão os especialistas !?), mas acredito que tenho um algoritmo razoavelmente rápido para o que você está perguntando.

$P$ $I$ $x_P\in I$ $x_P'\notin I$ $P$ $R$ $P$ $Q$ $R$ $I$

$R$ $P$ $Q$ $I$ $x_P$ $Q$

Este é apenas um esboço, mas não é preciso muito para transformar isso em um algoritmo de boa-fé , na verdade, suspeito que o uso do Maple ou do Mathematica tornaria isso trivial.

cody
fonte

Decidibilidade de um problema relativo a polinômios

Respostas: