Suppose $A$ is the set of all rational numbers $p$ such that $p^2 <2$ and $B$ is the set of all rational numbers $p$ such that $p^2 > 2$. We want to show that $A$ contains no largest element and $B$ contains no smallest element.

In Rudin's Principles of Mathematical Analysis, he associates $q = p- \frac{p^2-2}{p+2} = \frac{2p+2}{p+2}$. Did he just come up with this using trial and error?

  • $\begingroup$ Maybe he did, after all it is not that deep. Walter Rudin was an excellent author. $\endgroup$ – AD. Dec 20 '10 at 17:40
  • 7
    $\begingroup$ There is a good explanation to your question on page 3 of this file (math.berkeley.edu/~gbergman/ug.hndts/m104_Rudin_exs.pdf) In addition, there are many helpful supplemental exercises and answers to many questions that came up during the course of a Rudin analysis class on the page it came from (math.berkeley.edu/~gbergman/ug.hndts/#Rudin). $\endgroup$ – Tyler Dec 20 '10 at 17:46
  • 3
    $\begingroup$ The title is uninformative. $\endgroup$ – lhf Aug 5 '11 at 16:37
  • $\begingroup$ (This is from Rudin Principles of Mathematical Analysis) $\endgroup$ – MJD Sep 4 '14 at 2:45
  • $\begingroup$ Not trial and error. See my answer below with the link to the picture. Simple geometry. $\endgroup$ – Robert McLean MD PhD Jun 11 '18 at 5:20

The point here is that iterations of the Möbius transformation $p \mapsto \frac{2p+2}{p+2}$ converge to $\sqrt{2}$, so every time you apply the transformation you get closer to $\sqrt{2}$. This can be thought of as describing a generalized continued fraction

$$2 - \cfrac{2}{4 - \cfrac{2}{4 - \cfrac{2}{\cdots}}}$$

for $\sqrt{2}$. The dynamics of Möbius transformations in general are fairly well-understood; for the transformation $p \mapsto \frac{ap+b}{cp+d}$ the possible fixed points are the roots of the quadratic polynomial $cp^2 + dp = ap + b$, and using the Banach fixed point theorem (or a more specific closed form of iterations of Möbius transformations using linear algebra) one can determine which of the fixed points are attractive or repellent.

So if one wanted to design a Möbius transformation converging to $\sqrt{n}$ for some non-square $n$, this would require that $d = a, c = 1, b = n$, giving

$$p \mapsto \frac{ap + n}{p + a}$$

for some $a$, and it should not be hard to find a value of $a$ such that the fixed point $\sqrt{n}$ is attractive.

While this technique is a nice trick, because the polynomial $cp^2 + dp = ap + b$ is quadratic, it does not generalize to prove the corresponding result for roots of cubic or higher degree polynomials.

  • $\begingroup$ So it seems that you can create linear fractional transformations that converge to square roots. Are there any other types of transformations that one could create to converge to (say) $\sqrt[3]{3}$? $\endgroup$ – PrimeNumber Dec 20 '10 at 19:44
  • $\begingroup$ What is [3]? If it's just 3, then this is sqrt{27}, so it falls under the scope of the construction I laid out. More generally I believe you should be able to write down a Mobius transformation converging to any root of a quadratic polynomial with integer (equivalently, rational) coefficients. $\endgroup$ – Qiaochu Yuan Dec 20 '10 at 19:46
  • $\begingroup$ Edited. I meant the cube root of 3. $\endgroup$ – PrimeNumber Dec 20 '10 at 19:54
  • 1
    $\begingroup$ @Trevor: the corresponding thing to try would be something like p -> (ax + 3)(x^2 + a) for some a. But I have not done the computations to check if we can choose a such that sqrt[3]{3} is an attractive fixed point. In any case, this kind of argument gets more unwieldy the more complicated the number you try to do it with; a much more uniform way to prove the corresponding result for arbitrary irrational numbers a is to use, for example, the truncations of the decimal expansion of a or the convergents to its (ordinary) continued fraction. $\endgroup$ – Qiaochu Yuan Dec 20 '10 at 20:00
  • 2
    $\begingroup$ Halley's method for solving $x^3 = 3$ is the iteration $x \to \frac{x(x^3+6)}{2 x^3 + 3}$. This has an attracting fixed point at $3^{1/3}$, maps rationals to rationals, and converges monotonically to that fixed point from any starting point with $x > 0$. $\endgroup$ – Robert Israel Aug 5 '11 at 16:43

Below I show that Rudin's approximation arises simply by applying by the secant method - a difference analog of Newton's method for finding successively better approximations to roots.enter image description here

As the linked Wikipedia article shows, the recurrence relation for the secant method is as below.

$$\rm S_{n+1}= \dfrac{S_{n-1}\ f\:(S_n) - S_n\ f\:(S_{n-1})}{f\:(S_n)-f\:(S_{n-1})}\qquad\qquad\qquad\qquad$$

For $\rm\ (S_{n-1},S_n,S_{n+1}) = (q,p,p')\ $ and $\rm\ f\:(x) = x^2-d\:,\:$ we obtain

$$\rm p'\ =\ \dfrac{q\:(p^2-d) - p\:(q^2-d)}{p^2-d-(q^2-d)}\ =\ \dfrac{(p-q)\:(p\:q+d)}{p^2-q^2}\ =\ \dfrac{p\:q+d}{p+q}$$

Finally specializing $\rm\: q = 2 = d\: $ yields Rudin's approximation $\rm\displaystyle\ p'\ =\ \frac{2\:p+2}{\ \:p+2}$

The secant method has beautiful connections with the group law on conics. To learn about this folklore, I highly recommend Sam Northshield's Associativity of the Secant Method. The reader already familiar with the group law on elliptic curves, but unfamiliar with the degenerate case of conics, might also find helpful some of Franz Lemmermeyer's expositions, e.g. Conics - a poor man's elliptic curves.

Finally, note this the approximation can be derived purely algebraically as follows.

Given lower and upper approximations to a square-root, we may obtain a better lower approximation $\rm\ p'\ $ by $\:$ "composing" $\:$ them,$\ $ namely:

THEOREM $\rm\displaystyle\quad\ \ q\ >\ \sqrt d\ > \ p\ \ \:\Rightarrow\:\ \ \sqrt d\ > \ p'\ >\ p\quad\ \ for\quad\ p' \:=\ \frac{p\:q+d}{p+q} $

Proof: $\rm\quad\displaystyle 0\ \: >\ (q-\sqrt d)\ \ (p-\sqrt d)\ =\ p\:q+d - (p+q)\:\sqrt d\ \ \Rightarrow\ \ \sqrt d\ >\ p'$

Finally $\rm\quad\quad\displaystyle p'-p\ =\ \frac{p\:q+d}{p+q} - p\ =\ \frac{\ d - p^2}{p+q}\: >\ 0\ \ \Rightarrow\ \ p'\ >\ p$

  • $\begingroup$ Note This answer was (partially) merged by a moderator from another question (where it was the accepted answer). If anything appears strange (context, etc) it is probably due to the merge. $\endgroup$ – Bill Dubuque Jun 17 '16 at 14:34
  • $\begingroup$ @zyx Thanks, I've updated it. $\endgroup$ – Bill Dubuque Aug 22 '16 at 18:58

I had this same question.

For a very clear explanation, see page 25 and 26 of this.


This is a duplicate question. See 1. I answer it there, but I will repeat partially.

No. This isn't random. It is simple analytic geometry. One is trying to find the root of the equation $f(x)=x^2-2$. One starts with a rational $p$. Now, take the point $(2,2)$ on the graph. Form the chord between $(p,f(p))$ and $(2,2)$, solve for the intersection of the chord with the $x$-axis and that is Rudin's rabbit out of the hat formula. Picture is here: https://ggbm.at/nkfcPUB4


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.