4
$\begingroup$

(I believe this belongs to computational algebraic number theory, but if additional/different tags are better, let me know.)

Consider the cubic equation $x^3-3x^2+x-3=0.$ We have that $x=3$ is a root. On the other hand, one can use one of the algorithms for solving cubics (the methods followed by Tartaglia or others), and find a different looking expression, namely $ x= 1 +\root 3\of{2+\frac{10}{3\sqrt3}} + \root 3\of{2-\frac{10}{3\sqrt3}}. $ In this example, one can check that the numbers are the same, by noting that $ \root3\of{2+\frac{10}{3\sqrt3}}=1+\frac1{\sqrt3}, $ but this leads to my question:

Suppose that $\alpha$ and $\beta$ are complex numbers with explicitly given expressions, and that $\alpha$ and $\beta$ belong to some finite extension of ${\mathbb Q}$.

By "explicitly given", one can mean that finitely many irreducible polynomials $p_i$ with integer coefficients are given, and that $\alpha$ and $\beta$ can be obtained from roots of these $p_i$ by radicals (as the expressions above), perhaps with additional information on which of the roots of the $p_i$ one is considering ("the smallest positive root," "the one whose imaginary part is positive and second largest," ...). If you see a more precise way of making sense of this, that is fine as well.

In the example I was discussing, if I had not noticed that the cubic root simplified as it did, a reasonable way of convincing myself the two numbers were actually the same would have been to compute them. Using lots and lots of digits.

Compute numerical approximations to $\alpha$ and $\beta$ using some reliable CAS. Can we explicitly find an a priori (and feasible?) bound for the number of digits one needs to compute to ensure that if both approximations coincide, then in fact $\alpha=\beta$?

The bound most likely would depend not just on the degree of the extension of ${\mathbb Q}$ where we can find $\alpha$, $\beta$, and all the radicals that make them up, but I imagine the degree is part of it.

(Somebody told me the LLL algorithm is perhaps the way of doing this, but this is all new to me.)

  • 0
    I see. A quick follow-up: Given a "candidate" for the minimal polynomial of $\alpha$, is there an efficient algorithm verifying it is indeed irreducible?2012-03-09

3 Answers 3

4

After a discussion in the comments with Qiaochu Yuan, I think we both agree that this would be a suggested algorithm in practice :

You are given two algebraic numbers $\alpha$ and $\beta$. Compute their respective minimal polynomials. If you get two distinct polynomials, you're done ; distinct minimal polynomials have distinct roots. If they are the same, compute numerically all the roots, and also compute $ \delta \overset{\text{def}}{=} \underset{\text{roots}}{\min} \{ \|r_i - r_j\| \} $ where $i$ and $j$ just mean "go over all distinct pairs of roots". This will be a (numerical) upper bound that will tell you if $\alpha$ and $\beta$ are distinct : now if you evaluate $\alpha$ and $\beta$ up to a precision of $\delta$ you should be able to tell if they are distinct or not.

Hope that helps,

  • 0
    OK. I'm convinced now that this works. I'll need to work out how feasible the bounds one gets are -- they seem terrible. @DanPetersen Many thanks!2012-05-16
3

Suppose that $a$ and $b$ are given by your expression, or something like it. Then we can construct formulas $F_a(x)$, $F_b(y)$ in the first-order language $\mathcal{L}$ with constant symbols $0$ and $1$, and binary function symbols $+$ and $\times$ such that $F_a(x)$ "says" that $x=a$, and $F_b(y)$ says that $y=b$. One can do this with expressions that are substantially more general than the ones you envisage, including expressions that are defined piecewise.

Let $\varphi$ be the sentence $\forall x\forall y((F_a(x)\land F_b(y))\longrightarrow (x=y)).$ Then $\varphi$ "says" that $a=b$.

Now use Tarski's decision procedure for the first-order theory of real-closed fields (or for algebraically closed fields of characteristic $0$, if appropriate) to decide the truth of $\varphi$. (Since the original Tarski proof, there have been substantial improvements in the decision procedure, and even some implementations.)

Remark: Using a "general" decision procedure to solve a limited class of problems almost guarantees inefficiency. So there remains the very real problem of implementation for problems of the specific type you are interested in.

  • 0
    Thanks! This is a nice observation. Unfortunately, as you point out, it seems terribly inefficient for the problem at hand, since the general decision procedure is known to be at least doubly exponential. Also, even if the bounds are terrible, I do not know how to extract specific information about running time in this case from the general procedure. But that is in itself an interesting question.2012-03-11
1

This may help. Suppose $r$ is a root of polynomial $p(z)$, and you can get bounds |p'(r)| \ge \alpha > 0 and |p''(z)| \le \beta for $|z−r| \le \delta$. Then if $2 \alpha > \beta \delta$, there are no other roots of $p(z)$ with $|z−r| \le \delta$.

  • 0
    Thanks, this is a nice idea.2012-03-11