## 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 $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]
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$.