2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is possible, but the solution that comes now to my mind isn't trivial. If you would consider field extensions $\mathbb{Q}[\sqrt{r_i},\ldots]$, then it should be possible to keep everything in rational numbers and possibly even in integers. However, such extensions behave a lot like dimensions ($\mathbb{R}[\sqrt{-1}]$ is exactly $\mathbb{C}$, which is a lot like $\mathbb{R}^2$), so there might be some linear equations involved. There might be some easier solution, but right now that's the only one I have. $\endgroup$ – dtldarek Nov 24 '14 at 23:37
1
$\begingroup$

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.

$\endgroup$

Your Answer

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