Proof, Sequences of Square Roots

Table of contents

1 Rough Problem Statement 2 Answers 2.1 Quick Answer 2.2 First Harder Answer 2.3 A Little More General Answer 3 Discussion

Rough Problem Statement

How do I show that an expression with square roots in it is irrational or not? What if the numbers are huge?

Answers by landen and evilgeek.

Answers

Quick Answer

If the expression is just y = z*sqrt(k) where z and k are positive integers then:
x^2 - z^2*k = 0 and y is a root of this polynomial. By the [http://mathworld.wolfram.com/RationalZeroTheorem.html Rational Roots Theorem] if this has rational roots they are integers. Use your calculator or computer to get rational numbers which bracket y, one higher and one lower. This is always computationally feasible even for huge k or z. Newton's Method (http://mathworld.wolfram.com/NewtonsMethod.html) will give a rational upper bound on sqrt(k). Then lower_bound = k / upper_bound. If there is an integer between the brackets then try that integer and see if it exactly solves x^2 - k = 0. If it does not then y is irrational. If it does then it is y. If necessary use a computer and rational arithmetic to get sufficiently accurate rational bounds on y. Notice you can put the bounds into the polynomial and see if it changes sign. If you keep all the decimals or use rational arithmetic when you check then it won't matter how you got these bounds. If you use rational arithmetic or check decimals with enough places this method is rigorous.
Q.E.D.

First Harder Answer

More general problems can be a lot harder. One of us (evilgeek) got this from his freshman(!) algebra class at Waterloo:

Show that y = sqrt(2) + sqrt(3) + sqrt(5) + sqrt(7) + sqrt(11) + sqrt(13);  y is irrational.

evilgeek found the following proof which requires more fluency with polynomials and the rational roots theorem.

Proof:
Let a = sqrt(a_1) + sqrt(a_2) + ... + sqrt(a_n), all a_k in Z. Then x=a is a root of a polynomial of the form
p = (x - sqrt(a_1) - sqrt(a_2) - ... - sqrt(a_n))*z.

For simplicity, let p be the product of all
x +/- sqrt(a_1) +/- sqrt(a_2) +/- ... +/- sqrt(a_n); p has order 2^n.
a is a root of this polynomial.

For each 1 <= i <= n, group all terms not involving a_i, and denote these quantities by "junk". By definition, there are exactly two factors of p with the same "junk" term, and said factors have sqrt(a_i) terms of opposite signs (i.e., one is positive and the other is negative). This means that these reduce to differences of squares:
(junk - sqrt(a_i))(junk + sqrt(a_i)) = junk^2 - a_i.
Since each "junk" has a unique counterpart, no lone factors of sqrt(a_i) will appear in p. Since this is true for all i, and a_i are integers, all the coefficients are products of integers, thus integers. This means that p is a monic polynomial with integer coefficients.

By the rational roots theorem, p may only have integer or irrational roots. Bounds on y may be established by noting that if a<sqrt(b)<c, then a^2<b<c^2, and obtaining bounds on the individual square roots to some precision. Bounds for y to two decimal places are 14.92 < y < 14.98, so y cannot be an integer and hence y is irrational.
Q.E.D.

The previous proof used the fact that if the answer were rational it had to be an integer and a calculator can then quickly tell in most cases if this is not an integer. Unless the sum is closer to an integer than your calculator can handle this is an easy test to apply. You could use your computer if lots of digits are required. It would be nice to know that the computer will always succeed with a feasible amount of work.

A Little More General Answer

This is a more general problem that includes the ones above. Assume z_i are integers and k_i are positive integers.
u_i = z_i *sqrt(k_i) which is typically irrational.

y = (sum i = 1 to m) u_i; then y is irrational or an integer:

Proof:
Define the polynomial p[x] = (product over all i and sign choices + | -  in front of u_i, i = 1 to m)
(x  - sum(i = 1 to m) ((+|-) u_i))

This polynomial is of degree 2^m in x because of the 2 sign choices in the factors. Treat the polynomial as a polynomial in u_i. If you change the sign of any u_i you get the same polynomial (with the factors in a different order). This polynomial is therefore of even degree in each u_i. If it were simplified, each u_i would be raised to an even power. Since the powers of u_i are even it has no sqrts in it anymore. So p[x] is monic with integer coefficients just like the example above. The rational roots theorem again says that if this polynomial has any rational roots they are integers. So we have proved that y which is the root when all + signs are chosen, is irrational or is an integer.

Computing a rational upper bound to the sqrt of an integer and a rational lower bound to the sqrt is computationally feasible even for numbers which are exceedingly large (Newton's method). If the bounds fall with just one integer in between we can try dividing that integer into the number to see if it is a perfect square. So if the number is a perfect square we can detect that and make both bounds equal the exact sqrt. If there is no integer in between we know it is not a perfect square. Factoring a perfect square is easy even though factoring a general big integer is not feasible (at least no one knows how to do it and has published).

Once we have bounds on all the sqrt(k_i) we can computer upper and lower bounds on all the u_i. We can add the upper bounds on the u_i and get an upper bound on y. We can add the lower bounds of the u_i to get a lower bound on y. Notice that we don't have to compute p[x] for this step.

If there is no integer between the upper and lower bounds for y we are done. y is not an integer and is therefore irrational.

If there is an integer between the bounds for y we have to do a little more work and compute p[x] explicitly.

Call the integer in the bounds of y, J. If J is not a root of p[x], y is irrational. Suppose J is a root and there is only one root of p[x] in the bounds for y. Then y is J and is rational. There could be multiple roots in the interval with y and J. So we might need more work.

The following argument for the other cases uses one idea from the calculus. That could be avoided. We thought it was unlikely anyone that is trying to follow this has not had a little calculus. It uses without comment lots of little facts about polynomials.

If J is a root of p[x] and there are other roots of p[x] in the bounds of y then we have to account for the roots of p[x] in more detail. Possible repeated roots make this harder to test. So we get our computer to compute p[x] explicitly. Compute h[x] = greatest common divisor, gcd(p[x],p'[x]). The Euclidean algorithm for polynomials (Knuth, "Seminumerical Algorithms") can determine h[x] in a feasible amount of time. p'[x] is just the derivative of p[x]. Now compute q[x] = p[x]/h[x]. q[x] has all of the roots of p[x] with the repeated roots removed. This is easy to prove with elementary calculus. Now that the repeated roots are removed we get the computer to narrow the bounds on each root until none overlap. This will always succeed because there are no repeated roots. Now if J is in the bounds of y we know that J = y. J is a root of q[x] and so is y and there are exactly as many intervals as the degree of q[x]. So the pigeon-hole principle is the reason we know J = y. If J is not in the interval with y then y is irrational.
Q.E.D.

Discussion

If you made it through that, then you can handle problems like this:
Is y = sum (i to m)(q_i * sqrt ( r_i))  irrational  where q_i and r_i are rationals, all r_i > 0?

Call Z the product of all the denominators of the q_i's and r_i's. Then compute y*Z. Since Z is an integer, y is irational if and only if y*Z is. However the right hand side of y*Z now has no denominators and fits our test above. So we can test y*Z.