Performing computations over the set of constructable numbers

Question

The set of constructable numbers is commonly defined in one of two ways:

• the set of finite numbers reachable from the rational numbers through a finite sequence of addition/subtraction, multiplication/division, and square root operations.

• They are also defined as an infinite chain of "field extensions" on the rational numbers which basically boils down to this:

  1. Begin by defining the set of constructable numbers as $K = \mathbb Q$. (the rationals)
  2. Find an arbitary constructable $q$ such that $\sqrt q$ is not yet known to be constructable.
  3. Declare all polynomials over $\sqrt q$ to be constructable; i.e. define $K'\equiv\{a + b\sqrt q \mid a,b\in K\}$.
     • (note there is special notation for this: $K'\equiv K[\sqrt q]$)
  4. Return to step 2, using $K'$ in place of $K$. (and repeat ad infinitum)

It is not altogether difficult to locate inductive-style proofs of the fact that these two definitions are equivalent. This is cool and all, but...

How on earth do you use them?

If you were to tell a machine to perform computations involving these numbers, how would you do it? A naive strategy would be to do this:

• Any given value in the computation is stored as a ternary tree of values that includes the numbers used to create the field extensions; E.g. a member of $\mathbb Q[\sqrt a][\sqrt b]$ will store three elements of $\mathbb Q[\sqrt a]$ ($b$ and the coefficients), each of which will store three rationals ($a$ and the coefficients). (let's leave aside the issue of all the unnecessary copies of $a$ this creates, which is in practice easily addressed)
• Given two numbers $x,y \in \mathbb Q[k_1][k_2]\dots[k_n]$, their sum, difference, product, and quotient can all be straightforwardly obtained as members of $\mathbb Q[k_1][k_2]\dots[k_n]$.
• To take a square root of a number $q \in K(=Q[k_1][k_2]\dots[k_n])$, first try to find a nonnegative root $x \in K$ of the equation $x^2 - q = 0$. If this fails, create $\sqrt q$ as a member of a new field extension $K[\sqrt q]$.

But this isn't complete; the second rule above requires the sequences of $k$ values to match! If we're generating these field extensions on demand, then how do we define operations when they do not match?

Notice that the same number can have many vastly different representations!

\begin{alignat}{4} (1 + \sqrt 3) + (1 + \sqrt 5) &= (2 + \sqrt3) &&+ (1 + 0\sqrt3)\sqrt5 \quad&&\in \mathbb Q[\sqrt3][\sqrt5] \\ &= (2 + \sqrt5) &&+ (1 + 0\sqrt5)\sqrt3 \quad&&\in \mathbb Q[\sqrt5][\sqrt3] \\ &= (2 + 0\sqrt{15}) &&+ (1 + \frac13\sqrt{15})\sqrt3 \quad&&\in \mathbb Q[\sqrt{15}][\sqrt3] \end{alignat}

How can we recognize these all as equal?

---

They seemed very promising at first, but now I am not so sure...

Is there a workable representation of constructable numbers which is actually amenable to computation?

---

Addendum

At this point I've decided that a CAS was all I really needed to begin with.

However, my secondary motivation for asking the question remains, which is that I am still genuinely interested in how one would perform operations on such numbers.

For point of reference, at some point while I was trying to implement my own, I had in fact begun writing something that vaguely resembled the simple beginnings of some sort of term rewriting system:

class Term t where
    -- Methods that attempty to merge two terms into one.
    trySimplifySum     :: (t,t) -> Maybe t
    trySimplifyProduct :: (t,t) -> Maybe t
    trySimplifyRoot    :: t -> Maybe t

data Expression t = Expr { isSimplified :: Bool
                         , getRawExpr   :: RawExpression t }

data RawExpression t = SingleTerm t
                     | Sum [Expression t]
                     | Product [Expression t]
                     | Root (Expression t)

simplify :: (Term t) => Expression t -> Expression t
expand   :: (Term t) => Expression t -> Expression t
factor   :: (Term t) => Expression t -> Expression t

simplify =
     -- simplify using a greedy algorithm
     -- (which I REALLY hope is all I need...)
     --
     -- recurse on unsimplified subexpressions;
     -- attempt to reduce terms by brute force,
     --    using trySimplify* on all pairs, and starting over
     --    each time a simplification succeeds;
     -- replace empty sums/products with zero and one

expand = {- do the obvious thing -}
factor = error "oh god I hope I never have to write this"

and it was around this point when I had to step back and ask myself, is this really necessary?

well...is it?

Answer 1

I now feel this is an instance of the XY problem.

Needless to say, the reason I asked this question was because I was trying to implement it. However, there is no need for me to implement something like this!

As people have noted in the comments, CAS systems such as Mathematica provide a natural way of working with such numbers. And not just that, but they also provide direct solutions to some of the problems that caused me to think I needed this data type in the first place!

Unsurprisingly, even SymPy can manipulate these numbers; this is the solution I decided to go with since it is available out-of-the-box in Jupyter.

I am still open to other answers (see addendum)