## Rational approximations of √2

*23 February 2009 at 5:23 pm* *
Leave a comment *

Introducing undergraduates to rational approximations of √2 can be an opportunity to insidiously tell them about many parts of mathematics they certainly don’t want to hear about. In a less pessimistic way, I would say this is a nice way to illustrate the use of several theories in abstract mathematics.

First, you may want to tell them it is not a rational number, which could be easy, unless they never heard about factoring integers.

Then, you could use classical sequences from high school classes: it is easy to check that iterating converges to ±√2, and setting they will even be able to give an explicit formula with a geometric sequence. There is of course a well-known algorithm which speeds up considerably the computation : *Newton’s method*. This can be illustrated geometrically by drawing the graph of a function having √2 as a root (for example ):

- take a rough approximation, such as x=1
- imagine the function is affine (replacing the graph by its tangent)
- use the approximation of the function to calculate an approximation of the solution
- use this newly found rough solution to iterate from step 1

This method requires iterating , and converges considerably faster. Both methods yield sequences of rational numbers converging to √2, so should be considered as methods to obtain fractional numbers giving good approximations of √2.

Since I am trying to learn basic Haskell, here is how it could be done :

import List import System.Environment -- Naïve method un :: [Rational] un = unfoldr (\x -> Just (x, (x+2)/(x+1))) 1 -- Newton's method vn :: [Rational] vn = unfoldr (\x -> Just (x,x/2+1/x)) 1 main = do argv <- getArgs -- () -> IO [String] let s = read (head argv) -- [String] -> Int in (putStrLn . show) (un!!s) -- Int -> IO String

Change the last `un`

to `vn`

in order to test Newton’s method. To use the little program on a computer with the GHC compiler, type

$ ghc -o sqrt2 sqrt2.hs $ ./sqrt2 22 318281039 % 225058681

which gives you the 22th iteration of the first sequence. Using Newton’s method, the fifth iteration is 886731088897/627013566048. Now you could explain the relevance of these computations by telling about best rational approximations.

Definition.A rational number is said to be abest approximationof √2 if there is no rational number closer to √2 having small denominator.

Then go further in the maths telling your students how solutions of the Pell-Fermat equation *p²-2q²=±1* provide best approximations of √2 by irreducible fractions *p/q*. Try to make them find several easy solutions, such as (1,1), (3,2), (7,5), and show them how the two sequences we defined earlier give a infinite sequence of solutions for free, using the identites

(which explains the mechanism in the iteration of ) and , which explains it for .

The most literate readers will say we are working with the integer ring of the field , and will tell you that p²-2q² is the *norm* of , with the interesting property . The solutions of Pell-Fermat equation given by are simply the coefficients in , while comes from . This is a good time to pause and tell about fast exponentiation by squaring (find it in your favorite search engine…).

Last but not least, since the Pell-Fermat equation is quadratic, the set of points in the plane parameterised by its solutions is a conic (a hyperbola). It admits a rational parameterisation, in the following way:

- choose some solution
- if is another solution, consider the (reciprocal) slope of the line , which is
- considering a slope
*t*, show that there is a unique point such that , namely - notice that if
*p*and*q*are rational/real/complex, then so is*t*(check the converse too) - if you are a graduate student in algebraic geometry, try to show the two relevant projective schemes are isomorphic over

As a consequence, all rational solutions of the Pell-Fermat equation can be enumerated bijectively by for rational values of *t*. The group structure on these solutions can be illustrated by matrices:

.

This way of finding rational points on conics is also a quick method to find all Pythagorean triples: the rational solutions of are given by . This is easily shown to be equivalent to the statement that integers satisfy if and only if we can write , , for integers .

Entry filed under: algebra, calculus, english. Tags: algebra, calculus, conic, Newton method, square root.

Trackback this post | Subscribe to the comments via RSS Feed