# Comparing sums of surds

Without using a calculator, how would you determine if terms of the form $\sum b_i\sqrt{a_i}$ are positive? I am mainly interested in the case where $a_i, b_i$ are integers.

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. This is a fail-proof method, regardless of the numbers that are involved.

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. Taylor approximations might offer an approximation, though the bound could be very tight (and hence require many terms).

Do you have any other suggestions?

Note by Calvin Lin
6 years, 11 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

For the given example, conjugate surds do the trick. It is equal to $\frac { (\sqrt{2} + \sqrt{5} + \sqrt{13})^{2} -(\sqrt{3} + \sqrt{7} + \sqrt{11})^{2}} {A}$ where A is a positive real.

Expanding the numerator, I get $-1 +2 ( (\sqrt{10}-\sqrt{21})+ (\sqrt{26}-\sqrt{33}) + (\sqrt{65}-\sqrt{77}))$ which is obviously negative.

- 6 years, 11 months ago

Wait, so how is this different from squaring both sides in Calvin's example?

- 6 years, 11 months ago

Admittedly both methods yield the same computations :p. The reasoning is different though (algebraic manipulations vs increasing functions)

- 6 years, 11 months ago

Whether there's an efficient method for this in general is a well-known open problem in computational complexity; see http://en.wikipedia.org/wiki/Sumofradicals (in particular, I believe it's not even known whether this problem is in NP, let alone P).

There are, of course, a bunch of inefficient ways to figure out whether a sum like $S = \sum_{i=1}^{n} b_i\sqrt{a_i}$ is positive or negative. One way to do this is to estimate the size of S by first computing the product of all of its conjugates,

$P = \left|\prod\sum \pm b_i\sqrt{a_i}\right|$

and then applying the estimate

$|S| \geq \dfrac{P}{(\sum |b_i\sqrt{a_i}|)^{2^{n}-1}}$

Now, to determine whether $S$ is positive or negative, it just suffices to approximate S to within this lower bound for $|S|$, which you can do via Taylor series or any other convergent expansion.

- 6 years, 11 months ago

So, if we don't know of an efficient method that applies to all situations, can we figure out efficient methods that apply to certain conditions? In Math, we sometimes develop tools that work according to the conditions in various scenarios, and then break them up into cases.

For example, taking the idea of Jensens, is $\sum \sgn(b_i) b_i^2 a_i = 0$ a sufficient condition for us to apply Jensen's to obtain information about the signage?

Staff - 6 years, 11 months ago

That condition isn't enough; one easy way to see this is if you just flip all the signs of the $b_i$, that sum stays equal to 0 whereas the original expression switches signs.

The inequality you probably want is a generalization of Jensen's inequality called Karamata's majorization inequality (http://en.wikipedia.org/wiki/Karamata's_inequality). In addition to your condition above, you also need the positive terms to 'majorize' the negative terms (see the wikipedia link for more information). Of course, this only applies in a very limited range of situations.

- 6 years, 11 months ago

Indeed! I like your observation about flipping the signs. That's why I wrote "obtain information about the signage", without claiming that it must be positive.

Yes, the majorization inequality is a sufficient condition, and can be interpreted as Jensen's applied term wise. Essentially, you work from the smallest value, similar to the inequality chain that I presented in my reply to Ivan.

Staff - 6 years, 11 months ago

I'm not quite familiar with "Jensen's inequality". Could anyone please elaborate a bit further? I would be most grateful!

- 6 years, 11 months ago

Jensen's is a statement of convexity / concavity.

A function $f(x)$ is concave in an interval $[a,b]$, if for any $x$ and $y$ in the interval, and $0 \leq t \leq 1$,

$f(tx+(1-t)y)\geq t f(x)+(1-t)f(y)$

If the function is also twice differentiable, we can simply check that $f''(x) < 0$.

If $f(x)$ is a concave function (over the entire real line), then the maximum value of $\sum_{i=1}^n f(x_i )$ subject to $\sum_{i=1}^n x_i = K$ (for some constant $K$ ) will be attained when all $x_i$ values are the same, namely $\frac{K}{n}$.

As an example, since $\sqrt{x}$ is a concave function on $[0, \infty)$ (Show this using both ways!), thus we know that

$\sqrt{ 3 } + \sqrt{5} \leq 2 \sqrt{\frac{8}{2} } = 4 .$

If you evaluate the LHS, you get $\sqrt{3} + \sqrt{5} = 3.968$. Of course, the condition that $\sum x_i = K$ is extremely restrictive.

As an extension, to apply it to the inequality that I stated, you can show that

$\sqrt{3} + \sqrt{7} + \sqrt{11} \geq \sqrt{2} + \sqrt{7} + \sqrt{12} \geq \sqrt{2} + \sqrt{5} + \sqrt{14} \geq \sqrt{2} + \sqrt{5} + \sqrt{ 13 }$

Staff - 6 years, 11 months ago

And Jensen's Inequality says that if a function is concave, then for any $\lambda_1+\lambda_2+\lambda_3+\dots+\lambda_n=1$,

$f(\lambda_1x_1+\lambda_2x_2+\lambda_3x_3+\dots+\lambda_nx_n)\ge\lambda_1f(x_1)+\lambda_2f(x_2)+\lambda_3f(x_3)+\dots+\lambda_nf(x_n)$

You can use Jensen's Inequality to prove AM-GM by using $f(x)=\log x$ and $\lambda_1=\lambda_2=\lambda_3=\dots=\lambda_n=\frac{1}{n}$. Already, we know that $\log x$ is concave (we can check the second derivative), and we also know $\lambda_1+\lambda_2+\lambda_3+\dots+\lambda_n=n\frac{1}{n}=1$, so

$\frac{a_1+a_2+a_3+\dots+a_n}{n}\ge\sqrt[n]{a_1a_2a_3\dots a_n}$ $\log(\frac{1}{n}a_1+\frac{1}{n}a_2+\frac{1}{n}a_3+\dots+\frac{1}{n}a_n)\ge\log\sqrt[n]{a_1a_2a_3\dots a_n}=\frac{1}{n}\log a_1+\frac{1}{n}\log a_2+\frac{1}{n}\log a_3+\dots+\frac{1}{n}\log a_n$

Plugging in our definitions, we get

$f(\lambda_1x_1+\lambda_2x_2+\lambda_3x_3+\dots+\lambda_nx_n)\ge\lambda_1f(x_1)+\lambda_2f(x_2)+\lambda_3f(x_3)+\dots+\lambda_nf(x_n)$

which is true by Jensen's Inequality.

- 6 years, 11 months ago

Oscar, in your statement of Jensen's inequality, you also need the $\lambda_i$ to be nonnegative.

- 6 years, 11 months ago

Is that true? I didn't think it was.

- 6 years, 11 months ago

Yes you do. One way of remembering Jensen's is that (for concave functions) the secant line of the function lies below the graph. This only holds through within the region bounded by your end points, and is false otherwise. Thus, the values of $\lambda$ need to lie within $[0,1]$.

As an explicit example, consider $f(x) = - x^2$. Take the points $x_1 = 1$ and $x_2 = 2$. How do we reach 0 by connecting the lines? We want $0 = \lambda 1 + (1-\lambda) 2$ which gives us $\lambda = 2$. Then, your claim is

$0 = f(0) = f( 2 \times 1 + (-1) \times 2) \geq 2 f(1) + (-1) f(2) = 2 .$

- 6 years, 11 months ago

Thank you very much guys. :)

- 6 years, 11 months ago

http://prntscr.com/1lxjuk

I have this comparison, but it would be tedious work especially with more terms

- 6 years, 11 months ago

That's a good idea, choosing to bound the difference of terms by one another.

However, this gets very complicated very quickly. There is no guarantee that there is an equal number of positive and negative terms, nor how we should bound one difference by another. It is possible that the total sum has absolute values less than $0.1$, which each of the differences have absolute value more than $1$. In this case, such an approach would not work.

Staff - 6 years, 11 months ago

haha thanks :P I can only do this cuz I haven't learned all sorts of funny things just as yet from my country's education system yet. I could only come up with this :D

- 6 years, 11 months ago

Are you sure about five surds?

$- \sqrt{2} + \sqrt{3} + \sqrt{5} + \sqrt{7} - \sqrt{17} > 0$

$\sqrt{3} + \sqrt{5} + \sqrt{7} > \sqrt{2} + \sqrt{17}$

$15 + 2\sqrt{10} + 2\sqrt{14} + 2\sqrt{35} > 19 + 2\sqrt{34}$

$2\sqrt{10} + 2\sqrt{14} + 2\sqrt{35} > 4 + 2\sqrt{34}$

I don't think the number of surds is decreased. We still have five surds (although one is simply $\sqrt{16} = 4$ and the rest have a factor of $2$ out). I can't see a way to continue it; how would you do it?

- 6 years, 11 months ago

I'm more concerned with looking at the sum of many terms. With few terms, there could be various tricks involved that could help us slightly reduce the number. In that sense, 5/6 was chosen arbitrarily.

It is also not immediately clear that 6 cannot work. There could be some kind of algebraic manipulation that reduces the number.

Staff - 6 years, 11 months ago

I'm slightly surprised that no one mentioned using convergents (and semi-convergents) to approximate square roots into rational numbers using partial fractions, despite being a question Close to the root which uses this to find method.

This gives us a quick way to approximate the surd using rational numbers, which are much easier to add and multiply.

Staff - 6 years, 11 months ago

maclaurin series or something? I'm not very sure with all these exquisite formulas :P

- 6 years, 11 months ago

No, the approaches presented in the solutions generally require knowledge of continued fractions and convergents/semi-convergents.

I added a solution using Farey sequences to justify the answer. However, this is not ideal because it doesn't explain where to find the approximations (apart from slowly searching).

Staff - 6 years, 11 months ago