Rational approximations of √2
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
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
(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 .