# Decidability of Equality of Radical Expressions

Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).

• What are your thoughts? What have you tried and where did you get stuck?
– Raphael
Oct 9 '16 at 12:46
• @Raphael, to be clear, this is not homework or research -- it's just a question of an idle mind. I have no non-trivial thoughts about this yet. Obviously this is trivial without the roots. I'm pretty sure the set of $\mathbb Q$-polynomials in $n$th roots of integers has decidable equality, because checking $\mathbb Q$-linear independence of such roots should be easy (?). But I'm completely stuck when it comes to nested radicals, or even fractions of such "radical polynomials'. Oct 9 '16 at 16:42
• – Raphael
Oct 9 '16 at 22:38

Yes. ​ By the real-number analogue of the Tseytin transformation, that
reduces to the existential theory of the reals, which is in PSPACE by

page 291 and the bottom of page 290 from this paper
and

.

For all real numbers $x$, $\sqrt{x^2}$ and $x$ are both well-formed and ​ ​ ​ $\sqrt{x^2} = x$ ​ if and only if ​ $0\leq x$ ​ , ​ ​ ​ so testing inequality reduces to your problem. ​ ​ ​ ​ ​ ​ ​ I'm not aware of any better upper bound for testing inequalities of sums-of-square-roots than this paper, which puts it in the counting hierarchy.

• Nice, but why do you put newline before the dot? I tried to compile your whitespace code, but no luck.
– Evil
Oct 17 '16 at 15:32
• Thanks for the answer! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you!
– D.W.
Oct 17 '16 at 21:52
1. Algebraic numbers are solutions of polynomials with rational coefficients.
2. $+,\times,-,/$ of algebraic numbers result in algebraic numbers because algebraic numbers form a field (1). This means nested radicals are algebraic numbers too (2).
3. Nested radicals can be denested by algorithm (3,4).
4. Each algebraic number of degree $n$ can be uniquely represented as a $n$ by $n$ matrix of integers under a suitable basis (for example, $[1,x, (x^2+1)/2]$). This representation allows symbolic evaluation of $+,\times,-,/$ by matrix addition, multiplication, and inverse (p.159 of 5,6,7).
5. Two terms are equal if their unique representations are identical.
• I feel like the important/interesting part here is the denesting algorithm; the rest works (even without the denesting algorithm, since nested radicals are clearly algebraic even if you don't know how to denest them), but is kind of a cannon for a fly. Oct 17 '16 at 8:22
• Thanks for the answer! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you!
– D.W.
Oct 17 '16 at 21:51