Determine sign of sum of square roots

Question

Problem

Given positive square-free integers $r_i$ and non-zero integers $a_i$, is there an algorithm for determining the sign of $\sum_{i=1}^n a_i\sqrt{r_i}$ without calculating approximations for the square roots?

If $n=2$ it is easy and I hope it shows more clearly what I am asking:

Solution for $n=2$

If $a_1$ and $a_2$ have the same sign it is trivial.

Assume $a_1>0$, $a_2<0$ then the following statements are equivalent:

$a_i\sqrt{r_1} + a_2\sqrt{r_2} > 0$

$a_i\sqrt{r_1} > (-a_2)\sqrt{r_2}$

$(a_i\sqrt{r_1})^2 > ((-a_2)\sqrt{r_2})^2$ (because both rhs and lhs are positive)

$a_1^2 r_1 > a_2^2 r_2$

This last statement can be evaluated exactly using only integer operations. However if I have three or more roots on either side, the squaring step does increase the number of square roots.

Edit

The keyword field extiensions by @dtldarek led me to the related question How do extension fields implement $>, <$ comparisons?. Also the comment A field that is an ordered field in two distinct ways seems to indicate that the order is defined by embedding the field in $\mathbb{R}$ and using the order of $\mathbb{R}$. I am trying to define the same order using only operations inside the field, because the reals are more difficult (impossible?) to represent exactly in a computer program.

Answer 1

I ended up solving the problem by constructing a field extension containing the number. For constructing the field extension you have to be careful not adding redundant roots. Then by the method above you can reduce the degree of the extension and repeat until the number whose sign is to be tested is rational.

Example: finding the sign of  $a= \sqrt{6}-\sqrt{2}-\sqrt{3}+1$

1. Construct a field extension containing $a$.    the obvious cnadidate is $\mathbb Q[\sqrt{2}, \sqrt{3}, \sqrt{6}]$ but of course    $\sqrt{6} = \sqrt{3}\sqrt{2} \in \mathbb Q[\sqrt{2},\sqrt{3}]$. In order to avoid     infinite loops in the algorithm it is important to have a good representation of the extension field without redundant roots. Note: it is not important which two of the three roots are chosen.

2. Treat the extension as a sequence of quadratic extensions. $\mathbb Q[\sqrt{2},\sqrt{3}] = \mathbb Q[\sqrt{2}][\sqrt{3}]$. This simplifies the algorithm since it only needs to deal with quadratic extension. A number in a quadratic extension $F[\sqrt{r}]$ can be uniquely written as $u + v\sqrt{r}$ with $u$  and $v\in F$.

3. Write the number in the form $u + v\sqrt{r}$. $$a = \underbrace{1-\sqrt{2}}_{\in \mathbb Q[\sqrt{2}]}+(\underbrace{\sqrt{2}-1}_{\in \mathbb Q[\sqrt{2}]})\sqrt{3}$$

4. By the reasoning which is already in the question for $n=2$ we can find a number $b\in \mathbb Q[\sqrt{2}]$ which has the same sign as $a$. We find $$b=3(\sqrt{2}-1)^2-(\sqrt{2}-1)^2.$$ This reduces the problem from the field $\mathbb Q[\sqrt{2}][\sqrt{3}] $ to the field $\mathbb Q[\sqrt{2}] $.

5. Analogous to step 3. Write the number $b$ in the form $u + v\sqrt{r}$. $$b = \underbrace{6}_{\in \mathbb Q}+(\underbrace{-4}_{\in \mathbb Q})\sqrt{2}.$$

6. Analogous to step 4. Find $c\in\mathbb Q$ having the same sign as $b$. We find $$c=6^2-4^2\cdot2=4>0.$$

Since $a$, $b$, and $c$ all have the same sign, we conclude that $a$ is positive.