8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What are your thoughts? What have you tried and where did you get stuck? $\endgroup$ – Raphael Oct 9 '16 at 12:46
  • $\begingroup$ @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'. $\endgroup$ – Mees de Vries Oct 9 '16 at 16:42
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Raphael Oct 9 '16 at 22:38
3
+50
$\begingroup$

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
the answers to this question

.


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.

$\endgroup$
  • $\begingroup$ Nice, but why do you put newline before the dot? I tried to compile your whitespace code, but no luck. $\endgroup$ – Evil Oct 17 '16 at 15:32
  • $\begingroup$ 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! $\endgroup$ – D.W. Oct 17 '16 at 21:52
3
$\begingroup$
  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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mees de Vries Oct 17 '16 at 8:22
  • $\begingroup$ 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! $\endgroup$ – D.W. Oct 17 '16 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.