Effective equality

(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.)

-
Very interesting question, but I have no idea. I'd like to see an answer though! What I can say actually, is that in your problem, if you follow Tartaglia's techniques then you'll get cubic roots along the way, but if you factor your polynomial and use quadratic formulas for the quadratic factor, you'll get the two other roots. Comparing them two by two is enough to conclude equality. –  Patrick Da Silva Mar 9 '12 at 21:08
Sure. Compute the characteristic polynomial both of the expressions you want to test for equality. If they don't have a common factor, you're done. If they do, they are equal if and only if they are equal to the same root of the common factor of their characteristic polynomial, so once you know what the smallest distance between any two roots of that polynomial is... –  Qiaochu Yuan Mar 9 '12 at 21:09
(That is, I am claiming that a bound certainly exists, not that I know how to find one. This follows from the fact that there are only finitely many polynomials of bounded degree with bounded integer coefficients.) –  Qiaochu Yuan Mar 9 '12 at 21:10
@Qiaochu : Is there a formula for the smallest distance between roots of a separable polynomial as a function of the coefficients? (I said separable because if not we'll clearly get $0$...) –  Patrick Da Silva Mar 9 '12 at 21:11
Hm. So perhaps the bound we are looking for is the minimal distance between two roots of a separable polynomial of some bounded degree. –  Patrick Da Silva Mar 9 '12 at 21:12

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,

-
I came across some important matter though : Are "characteristic" polynomials and "minimal" polynomials two words for the same thing? I was thinking minimal polynomial here ; the minimal polynomial of $\alpha$ is the monic polynomial of least degree of which $\alpha$ is a root. –  Patrick Da Silva Mar 9 '12 at 21:24
The idea I had in mind is to write down an obvious number field that some $\alpha$ lies in, an obvious basis of this number field over $\mathbb{Q}$, and then compute the characteristic polynomial of the matrix of multiplication by $\alpha$ with respect to the chosen basis. I don't know if this is easier or harder than trying to compute the minimal polynomial; if you try to compute the minimal polynomial by computing powers of $\alpha$ don't you end up having to decide whether various expressions in $\alpha$ are equal to each other? That's a special case of the problem you're trying to solve. –  Qiaochu Yuan Mar 9 '12 at 22:23
Oh, so it was a characteristic polynomial in the matrix sense. Perhaps that could work too ; I had not thought about this. –  Patrick Da Silva Mar 9 '12 at 22:24
@Qiaochu : I was more thinking of this for computing the minimal polynomial ; find all the roots (numerically) and multiply the linear factors together with $(x-\alpha)$ to see when do you get a polynomial with rational coefficients. But now that I am saying this, it looks quite hard to do with numerical tools since the "checking if there is rational coefficients" will be quite hard. Perhaps the characteristic polynomial over some basis would be a nicer approach. –  Patrick Da Silva Mar 9 '12 at 22:26
This way of computing with algebraic numbers is implemented in the computer algebra package Sage. Sage stores an algebraic number as a pair consisting of a minimal polynomial, and numerical approximation close enough to uniquely determine a root of that polynomial in $\mathbb{C}$. Testing whether two such elements are equal is done exactly as described above. –  David Loeffler Mar 10 '12 at 11:22

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.

-
This seems quite vague. –  Patrick Da Silva Mar 9 '12 at 22:27
@Patrick Da Silva: What seems vague is sometimes a matter of background. For someone who has done work in Model Theory, writing down the relevant formula is purely mechanical. And you might want to look up Tarski's result, which says that there is an algorithm for determining whether a sentence in the usual language for rings (or fields) is true in the reals. (All real-closed fields are elementarily equivalent.) Others who have given alternate proofs of the same result are Seidenberg and Paul Cohen. –  André Nicolas Mar 10 '12 at 0:26
Okay, so it seems vague without background. =) +1! –  Patrick Da Silva Mar 10 '12 at 1:20
@Patrick Da Silva: Thanks for pointing out that the answer might not be clear. I have added a few words, and a link. The decision procedures for the first-order theories of real-closed fields, and of algebraically closed fields of characteristic $0$, are interesting, particularly because of the contrast with the undecidability of first-order Peano Arithmetic. The result also means that there is a decision procedure for elementary geometry, via coordinatization. –  André Nicolas Mar 10 '12 at 1:38
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. –  Bruce George Mar 11 '12 at 16:33

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

-
This seems nice, but why? –  Patrick Da Silva Mar 10 '12 at 1:20
If $p'(r) = \rho e^{i\theta}$, then $\text{Re}( e^{-i\theta} p'(z)) \ge \alpha - \beta |z - r|$ for $|z - r| \le \delta$, and (for $|\omega|=1$ and $0 < t \le \delta$) $p(r + t \omega) = \omega \int_0^t p'(r + s \omega)\ ds$ so $\text{Re}(\omega^{-1} e^{-i\theta} p(r + t \omega) \ge \int_0^t (\alpha - \beta s)\ ds = \alpha t - \beta t^2/2 > 0$. –  Robert Israel Mar 11 '12 at 6:40
Thanks, this is a nice idea. –  Bruce George Mar 11 '12 at 16:34