Décidabilité d'un problème concernant les polynômes

J'ai rencontré le problème intéressant suivant: soit polynômes sur le champ des nombres réels, et supposons que leurs coefficients soient tous entiers (c'est-à-dire qu'il existe une représentation exacte finie de ces polynômes). Si nécessaire, nous pouvons supposer que le degré des deux polynômes est égal. Notons x p (resp. X q ) la plus grande valeur absolue d'une racine (réelle ou complexe) du polynôme p (resp. Q ). La propriété x p = x q est-elle décidable?$p,q$$x_p$$x_q$$p$$q$$x_p = x_q$

Sinon, cette propriété est-elle valable pour certaines familles restreintes de polynômes? Dans le contexte d'où vient ce problème, les polynômes sont des polynômes caractéristiques de matrices, et leurs racines sont des valeurs propres.

Je connais certains algorithmes numériques pour calculer les racines des polynômes / valeurs propres, mais ils ne semblent pas être utiles ici, car la sortie de ces algorithmes n'est qu'approximative. Il me semble que l'algèbre informatique pourrait être utile ici, cependant, malheureusement, je n'ai presque aucune connaissance dans ce domaine.

Je ne cherche pas une solution détaillée à ce problème, mais toute intuition et idée où rechercher la solution seraient utiles.

Merci d'avance.

Je ne connais pas non plus ce domaine, mais je pense pouvoir apporter une réponse non constructive.

La théorie du premier ordre des champs fermés réels est décidable. Votre problème peut être présenté comme un système d'équations et d'inéquations algébriques sur les nombres algébriques réels. Considérons variables x 1 , … , x deg P , y 1 , … , y deg P , x ′ 1 , … , x ′ deg P$2 (\deg P + \deg Q)$ . Vous voulez savoir si le système suivant est satisfaisable: \ 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 \\$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*}$$

Les deux premières familles d'équations expriment que les et x ′ k + $x_j+i\,y_j$ sont les racines des polynômes, les deux familles d'inéquation suivantes expriment quex1+$x'_k+i\,y'_k$ et x ′ 1 + $x_1+i\,y_1$ a la plus grande valeur absolue, et la dernière inéquation compare ces plus grandes valeurs absolues.$x'_1+i\,y'_1$

Il est possible de déterminer si ce système est satisfaisable: votre problème est décidable. Cependant, cette déclaration n'est probablement pas la manière la plus efficace de s'y prendre.

Une réponse plus utile implique probablement la théorie des bases de Gröbner . Si vous essayez de résoudre ce problème par vous-même, je pense que la lecture des premiers chapitres de tout livre d'algèbre informatique vous donnera le contexte requis. Si vous visez simplement à résoudre votre problème sous-jacent, il existe probablement un algorithme standard que vous pouvez implémenter.

Je peux me tromper à ce sujet: je ne suis pas non plus très bien informé dans ce domaine (où sont les experts!?), Mais je pense avoir un algorithme assez rapide pour ce que vous demandez.

Je vais supposer, pour simplifier, que toutes les racines sont réelles. Trouver un intervalle lié à la racine de avec la valeur absolue la plus élevée (c'est-à-dire un intervalle $P$$I$$x_P\in I$$x_P'\notin I$$P$ $R$$P$$Q$$R$$I$

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

Ce n'est qu'un croquis, mais cela ne prend pas grand-chose pour en faire un algorithme de bonne foi , en fait je soupçonne que l'utilisation de Maple ou de Mathematica rendrait cela trivial.