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

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.

• Perhaps it is helpful to split the procedure into two parts. First, determine if they generate isomorphic field extensions (which only depends on the $f_\alpha$ and not on the embedding), which amounts to finding a Teacherhaus transformation between the polynomials. Next, determine if there is one which respects the embedding/choice of root. Commented Mar 27 at 5:13
• (that should be Tschirnhaus, of course) Commented Mar 27 at 5:21
• Please use a high-level tag like "nt.number-theory". I added this tag now. Regarding high-level tags, see meta.mathoverflow.net/questions/1075 Commented Mar 27 at 9:04
• I don't think the assertion about $k\alpha = \beta mod 1$ is equivalent to $\mathbb{Q}(\alpha) = \mathbb{Q}(\beta)$. Clearly $\alpha = \sqrt{2} + \sqrt{3}$ and $\beta = 2\sqrt{2} + 3\sqrt{3}$ generate the same extension, but I don't think that $k\alpha = \beta \bmod 1$ is solvable. Commented Mar 27 at 14:53
• Thanks for the comments I made changes accordingly Commented Mar 27 at 15:23

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}$$.

• The question in the title isn't whether the extensions are isomorphic, but whether they are equal (as subfields of $\mathbb C$) Commented Mar 27 at 16:35
• You're right, I was hasty. Commented Mar 28 at 8:26

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.