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 u_{n+1} = \frac{u_n+2}{u_n+1} converges to ±√2, and setting U_n = \frac{u_n-\sqrt 2}{u_n+\sqrt 2} 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 x \mapsto x^2-2):

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

This method requires iterating v_{n+1} = \frac 1 2 (v_n + 2/v_n), 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 a best approximation of √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
2(p+q)^2 - (p+2q)^2 = p^2 - 2q^2 (which explains the mechanism in the iteration of \frac p q \mapsto \frac{p+2q}{p+q}) and (p^2+2q^2)^2 - (2pq)^2 = (p^2-2q^2)^2, which explains it for \frac p q \mapsto \frac{p}{2q} + \frac{q}{p}.

The most literate readers will say we are working with the integer ring of the field \mathbb Q(\sqrt 2), and will tell you that p²-2q² is the norm of p+q\sqrt{2}, with the interesting property (a^2-2b^2)(c^2-2d^2) = (ac+2bd)^2 - 2(ad+bc)^2. The solutions of Pell-Fermat equation given by u_n=p_n/q_n are simply the coefficients in p_n-q_n\sqrt 2 = (1-\sqrt 2)^{n+1}, while v_n=a_n/b_n comes from a_n-b_n\sqrt 2 = (1-\sqrt 2)^{2^n}. 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 p^2-2q^2=1 is quadratic, the set of points (p,q) in the plane parameterised by its solutions is a conic (a hyperbola). It admits a rational parameterisation, in the following way:

  1. choose some solution O=(1,0)
  2. if M=(p,q) is another solution, consider the (reciprocal) slope of the line OM, which is t = \frac {p-1} q
  3. considering a slope t, show that there is a unique point M = (1+tz,z) such that (1+tz)^2-2z^2 = 1, namely z = \frac{2t}{t^2-2}
  4. notice that if p and q are rational/real/complex, then so is t (check the converse too)
  5. if you are a graduate student in algebraic geometry, try to show the two relevant projective schemes are isomorphic over \mathrm{Spec} \mathbb Z[1/2]

As a consequence, all rational solutions of the Pell-Fermat equation p^2-2q^2 = 1 can be enumerated bijectively by \big(\frac{3t^2-2}{t^2-2}, \frac{2t}{t^2-2}\big) for rational values of t. The group structure on these solutions can be illustrated by matrices:
(p,q) \mapsto \begin{pmatrix} p & 2q \\ q & p \end{pmatrix}.

This way of finding rational points on conics is also a quick method to find all Pythagorean triples: the rational solutions of p^2+q^2=1 are given by \big(\frac{t^2-1}{t^2+1},\frac{2t}{t^2-1}\big). This is easily shown to be equivalent to the statement that integers satisfy a^2+b^2=c^2 if and only if we can write a = (m^2-n^2), b=2mn, c=m^2+n^2 for integers m>n.


Entry filed under: algebra, calculus, english. Tags: , , , , .

Laver tables and “unprovable” statements Monads in mathematics 1 : examples

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed



%d bloggers like this: