The set of constructible numbers


is the smallest field extension of $\mathbb{Q}$ that is closed under square root and complex conjugation. I am looking for an algorithm that decides if two constructible numbers are equal (or, what is the same, if a constructible number is zero).

As equality of rational numbers is trivial, this algorithm probably needs to reduce the complexity of the involved number in several steps.

Does such an algorithm exist? If yes, what does it look like?

  • 2
    $\begingroup$ In what form would the two constructible numbers be presented to the algorithm? $\endgroup$ – Joseph O'Rourke Mar 16 '17 at 19:34
  • 1
    $\begingroup$ A constructible number would be defined by a finite sequence of $+,-,*,/, \sqrt_\pm{}$ and complex conjugation applied to rational numbers, where $\sqrt_\pm{}$ would be one of the possible square roots of the given number. $\endgroup$ – J. Fabian Meier Mar 16 '17 at 19:37
  • 5
    $\begingroup$ There exist algorithms to deal with algebraic numbers in $\mathbb{C}$ (i.e., compute their sums, differences, products and inverses, solve algebraic equations on them, take their real and imaginary parts, and compare them for equality and, when they are real, for order). This solves your problem and much more. The basic idea is to represent an algebraic by a polynomial in $\mathbb{Q}[t]$ of which it is a root, and an interval (in real and imaginary parts if necessary) in which it is the only root. $\endgroup$ – Gro-Tsen Mar 16 '17 at 19:39
  • 2
    $\begingroup$ Furthermore, I should add that such algorithms are not purely theoretical: they are implemented, e.g., in Sage, which is capable of handling exact algebraics (although, to be fair, complexity becomes quickly awful whenever you do something not too trivial). $\endgroup$ – Gro-Tsen Mar 16 '17 at 19:41
  • 1
    $\begingroup$ See, for example, Henri Cohen, A Course in Computational Algebraic Number Theory (Springer 1993 / GTM 138), specifically §4.2. But this is merely one possible reference among many: the subject is really quite standard, and googling "algorithm exact algebraic arithmetic" returns various relevant results (which probably themselves point to other references). More abstractly, Rabin's theorem on the algebraic closure can also be relevant. $\endgroup$ – Gro-Tsen Mar 16 '17 at 21:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.