16
$\begingroup$

Without using a calculator, how would you determine if terms of the form $\sum b_i\sqrt{a_i} $ are positive? (You may assume that $a_i, b_i$ are integers, though that need not be the case)

When there are 5 or fewer terms involved, we can try and split the terms and square both sides, to reduce the number of surds that are involved. For example, to determine if $$\sqrt{2} - \sqrt{3} - \sqrt{5} + \sqrt{7} > 0, $$ we can square both sides of $\sqrt{2} + \sqrt{7} > \sqrt{3}+\sqrt{5} $ to obtain $$9 + 2 \sqrt{14} > 8 + 2 \sqrt{15}.$$

Repeated squaring eventually resolves this question, as the number of surds are reduced.

However, when there are more than 6 terms involved, then repeated squaring need not necessarily reduce the terms that are involved.

E.g. How would you determine if

$$\sqrt{2} - \sqrt{3} + \sqrt{5} - \sqrt{7} - \sqrt{11} + \sqrt{13} < 0 $$

I can think of several approaches

  1. There are special cases, which allow us to apply Jensen's inequality. However, this gives a somewhat restrictive condition on the set of values.

  2. Show that $$ \sqrt{2} + \sqrt{5} + \sqrt{13} < 7.26 < \sqrt{3} + \sqrt{7} + \sqrt{11} $$ However, it might not be feasible to guess what the middle number is, unless you already had a calculator.

  3. Calculate the surds to the appropriate level of precision (e.g. use Taylor expansion). This could be a little annoying.

Do you have any other suggestions?

$\endgroup$
  • $\begingroup$ For option $2$, wouldn't using Taylor approximations work? $\endgroup$ – Potato Aug 15 '13 at 0:44
  • $\begingroup$ I would consider using interval arithmetic for a problem like this. $\endgroup$ – abiessu Aug 15 '13 at 0:48
  • $\begingroup$ @Potato That is a possibility, though it requires being extremely precise with calculations. Whereas, repeated squaring for 5 terms of less will always work (and is reasonably easy to do for integers). $\endgroup$ – Calvin Lin Aug 15 '13 at 0:49
  • $\begingroup$ Why wouldn't you just compute all of the relevant surds to the appropriate level of precision? This isn't all that hard to do by hand, although it is a little annoying. $\endgroup$ – Qiaochu Yuan Aug 15 '13 at 0:53
  • 1
    $\begingroup$ This is actually a well-established open question in computer sciences; many computational geometry problems actually have it lurking behind the scenes. See cstheory.stackexchange.com/questions/4053/… $\endgroup$ – Steven Stadnicki Jan 28 '14 at 6:02
1
$\begingroup$

Robert Israel's answer in my question About rationalizing expressions is the the brute-force, but always-working method to do it. Although it is of exponential complexity, it shows the possibility of a finite-time algorithm besides calculation.

$\endgroup$
1
$\begingroup$

This is answer is incomplete it only handles the case of six surds.

For six surds there is still way to do it in general using squaring. Suppose you want to check if the inequality : $$ \sqrt{a} + \sqrt{b} + \sqrt{c} < \sqrt{a'} + \sqrt{b'} + \sqrt{c'} $$ is true. Squaring both sides and letting $$ A = bc,\quad B=ac,\quad C=ab,\quad K = a^2+b^2+c^2,\quad \dots $$ we get an expression of the form: $$ K + 2\sqrt{A} + 2\sqrt{B} + 2\sqrt{C} < K' + 2\sqrt{A'} + 2\sqrt{B'} + 2\sqrt{C'}\quad\quad (*)$$ now square again, you get another expression of the same shape $$ K_1 + (4K+2a) \sqrt{A} + (4K+2b)\sqrt{B} + (4K+2c)\sqrt{C} <\\ K'_1 + (4K'+2a') \sqrt{A'} + (4K'+2b')\sqrt{B'} + (4K'+2c')\sqrt{C'} \quad\quad(**)$$

Now if $X,Y$ and $\theta$ are positive numbers and $X \ge \theta /2$, $Y \ge \theta /2$ then as it is easy to check $$ X^2-\theta X < Y^2 - \theta X \quad\quad \text{if and only if}\quad\quad X < Y $$ letting $X$ equal to the left hand side of (*), $Y$ equal to the right hand side and $\theta = 2K+a$, (assuming $a$ is the smallest of $a,b,c,a',b',c'$) as we have trivially $$ X = K + 2 \sqrt{A} + \dots > \frac{2K+a}{2} = \frac{\theta}2 $$ and the same for $Y$, we can subtract $2K+a$ times (*) from (**) and obtain an inequality equivalent to the original but with one surd less.

With some care I think you can manage to extend this to positive and negative coefficients. But I can't see how to extend it in general for larger number of surds. For example if you have four surds in one side then squaring twice you get at most seven surds $$ \sqrt{ab}, \sqrt{ac}, \sqrt{ad}, \sqrt{bc}, \sqrt{bd}, \sqrt{cd},\sqrt{abcd} $$ if you manage somehow to reduce the number of surds but leave more than three surds, then squaring again a couple of times recovers all the surds, so you need to reduce four surds in a single blow.

By the way in your example squaring the inequality we see that it is equivalent to $$ 20 + 2 \sqrt{10} + 2\sqrt{26}+2\sqrt{65} < 21 + 2 \sqrt{21}+2\sqrt{33}+2\sqrt{77} $$ in this case you have finished as every term in the left is smaller than the corresponding term in the right.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.