# Performing computations over the set of constructable numbers

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?

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?

• Note: I had trouble finding good tags for this... – Exp HP Sep 12 '16 at 19:59
• This is more of a pure mathematics question, and it's quite broad, but here's how Mathematica manipulates them: reference.wolfram.com/language/ref/AlgebraicNumber.html, and sage: doc.sagemath.org/html/en/reference/number_fields/sage/rings/…. I believe it's a standard problem in computational number theory, there are books on this subject. For example, to check if two algebraic numbers are equal, one might compute their minimal polynomials, and check that they are the same root of the same polynomial; your representation makes this more awkward than necessary. – Kirill Sep 12 '16 at 21:27
• BTW, I'm not sure it's helpful to restrict yourself to only constructible numbers (which use only quadratic extensions). Generalizing the problem to all algebraic numbers, not even merely those expressible in radicals, would make it easier to approach. – Kirill Sep 12 '16 at 21:33
• @Kirill algebraic numbers would certainly do if there is a way to perform exact arithmetic on them. In the past I remember looking for such a library when trying to solve a similar problem, but the documentation for the ones I could find just rendered my brain to mush – Exp HP Sep 12 '16 at 21:50
• The LEDA programming library uses a similar representation for algebraic numbers in arbitrary precision, see algorithmic-solutions.info/leda_guide/number_types/real.html – BrunoLevy Sep 13 '16 at 14:18