Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?

Question

For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple $$ (f_\alpha, x, y, r) \in \mathbb{Q}[x] \times \mathbb{Q}^3 $$ so that $\alpha$ is the unique root of $f_\alpha$ inside the circle centered at $(x, y)$ of radius $r$ in the complex plane - that is $x, y, r \in \mathbb{Q}$ give the information needed to distinguish $\alpha$ from the other roots of $f_\alpha$ (Galois conjugates).

Given these finite representations of algebraic numbers, we can ask the following question:

Is it decidable (i.e. computable by a Turing machine) whether two real irrational algebraic numbers $\alpha$ and $\beta$ generate the same extension of the rationals?

A related question is a reachability question in dynamical systems:

If $\alpha, \beta$ are real irrational algebraic numbers, does there exist an effective procedure for determining whether there exists some integer $k \geq 1$ such that $$ k\alpha = \beta \mod 1? $$

For example, when $x = \sqrt{2}/4$, and $y = \sqrt{2}/2$, we can find that there exists a $k=2$ solving the problem. But it is unclear if this is the case in general.

Answer 1

Yes, there are algorithms for factoring $f_\beta$ over the number field $\mathbb{Q}(\alpha)$; if a linear factor is found and both irreducible polynomials have the same degree, then $\mathbb{Q}(\alpha)\simeq\mathbb{Q}(\beta)$. If the degrees differ, the fields will have different degrees (thus can't be isomorphic); if no linear factor is found, then no root of $f_\beta$ exists in $\mathbb{Q}(\alpha)$.

When the field matches and, moreover, has nontrivial automorphisms, several linear factors will turn up, and then the additional information about real or complex embeddings can be exploited to select the "right" factor. (This additional information is not needed for deciding isomorphism - the minimal polynomials suffice for that.)

See any good book about computational algebraic number theory, e.g. this one. Implementations exist, e.g. in PARI/gp:

(09:33) gp > nf1=nfinit(y^2-3);
(09:34) gp > nffactor(nf1, x^2-2*x-2)
%3 = 
[x + Mod(-y - 1, y^2 - 3) 1]

[ x + Mod(y - 1, y^2 - 3) 1]

(09:34) gp > 

i.e., $x^2-2x-2 = (x-(\sqrt{3}+1))^1(x-(-\sqrt{3}+1))^1$, representing the right-hand side as a matrix of factors and exponents.

Note that (as the other answer also hints) the given radii $r$ may still be too large to conclude in one step - it may be necessary to first compute tighter bounds for the roots based on the input data. For example, consider $f_\alpha=x^4-x-1$ and $f_\beta=x^4+x^3-1$. Then $\alpha^3-1=1/\alpha$ is a root of $f_\beta$ (regardless which real or complex root of $f_\alpha$ we take for $\alpha$), and there are no non-identity automorphisms. But if we're given that $-3/5 < \alpha < 3/2$ and $-3 < \beta < 1/2$, we can't immediately rule out that both numbers come from the same real embedding of the abstract field, even though each interval contains only a single real root of the respective polynomial, as is easily verified in exact rational arithmetic. Refining the bounds to $1/2 < \alpha < 3/2$ and $-2 < \beta < -1/2$ resolves the matter: With these data the fields $\mathbb{Q}(\alpha)$ and $\mathbb{Q}(\beta)$ are isomorphic but different subfields of $\mathbb{R}$.

Answer 2

Indeed there are algorithms for factoring $f_\beta$ over $\mathbb Q(\alpha)$, and the number of linear factors gives the number of distinct roots of $f_\beta$ in $\mathbb Q(\alpha)$ (and their multiplicities). From this one can determine whether $\mathbb Q(\alpha)$ and $\mathbb Q(\beta)$ are isomorphic: $f_\alpha$ and $f_\beta$ need to have the same degree, and each should have a root in the opposite field.

However, I think the question requires a further bit of consideration. Imagine, for example, that the splitting field of $f_\alpha$ has Galois group $S_7$, with five roots in $\mathbb R$, two of which are $\alpha$ and $\alpha'$. Let $\beta=\alpha+1$ and $\beta'=\alpha'+1$. Then the preceding paragraph will have all positive answers when we apply it to $\alpha$ and $\beta$, and also when we apply it to $\alpha$ and $\beta'$. However, with the Galois group being symmetric, $\alpha'\notin\mathbb Q(\alpha)$, and consequently $\beta'\notin \mathbb Q(\alpha)$, whereas $\beta\in\mathbb Q(\alpha)$.

So, to finish off the question of whether $\mathbb Q(\alpha)$ and $\mathbb Q(\beta)$ are actually equal (having found them to be isomorphic), one needs to find the formulas $g_1,\ldots,g_k\in\mathbb Q[X]$ with $\beta_i=g_i(\alpha)$, where $\beta_1,\ldots,\beta_k$ are the (real) roots of $f_\beta$ in $\mathbb Q(\alpha)$. This can be done just by searching through $\mathbb Q[X]$: we'll know them when we see them. Then use the given radii $r$ isolating $\alpha$ and $s$ isolating $\beta$ (or possibly $\frac r2,\frac r4,\ldots$ as needed) to test the different real roots of $f_\beta$ and determine which of them actually lie in $\mathbb Q(\alpha)$. If the given $\beta$ is one of these, then $\mathbb Q(\beta)\subseteq\mathbb Q(\alpha)$ (making these fields equal, since $f_\alpha$ and $f_\beta$ have the same degree). If not, then of course the fields are not equal.

For the algorithms for factoring polynomials over $\mathbb Q(\alpha)$, I usually refer to Edwards's book Galois Theory (Springer, 1984), Section 57 and thereabouts.