46
$\begingroup$

First, my apologies if this has already been asked/answered. I wasn't able to find this question via search.

My question comes from Rudin's "Principles of Mathematical Analysis," or "Baby Rudin," Ch 1, Example 1.1 on p. 2. In the second version of the proof, showing that sets A and B do not have greatest or lowest elements respectively, he presents a seemingly arbitrary assignment of a number $q$ that satisfies equations (3) and (4), plus other conditions needed to show that $q$ is the right number for the proof. As an exercise, I tried to derive his choice of $q$ so that I may learn more about the problem.

If we write equations (3) as $q = p - (p^2 - 2)x$, we can write (4) as

$$ q^2 - 2 = (p^2 - 2)[1 - 2px + (p^2 - 2)x^2]. $$

Here, we need a rational $x > 0$, chosen such that the expression in $[...]$ is positive. Using the quadratic formula and the sign of $(p^2 - 2)$, it can be shown that we need

$$ x \in \left(0, \frac{1}{p + \sqrt{2}}\right) \mbox{ for } p \in A, $$

or, for $p \in B$, $x < 1/\left(p + \sqrt{2}\right)$ or $x > 1/\left(p - \sqrt{2}\right)$.

Notice that there are MANY solutions to these equations! The easiest to see, perhaps, is letting $x = 1/(p + n)$ for $n \geq 2$. Notice that Rudin chooses $n = 2$ for his answer, but it checks out easily for other $n$.

The Question: Why does Rudin choose $x = 1/(p + 2)$ specifically? Is it just to make the expressions work out clearly algebraically? Why doesn't he comment on his particular choice or the nature of the set of solutions that will work for the proof? Is there a simpler derivation for the number $q$ that I am missing?

$\endgroup$
23
$\begingroup$

In the interest of making this question and answer more self-contained, here is the example in question. My answer is below.

enter image description here

I think you hit the nail on the head. He was looking for a rational $y$ such that $q = p+y$ will have the desired properties in both cases.

First, if $p \in A$ we want $p<q \Leftrightarrow y > 0$ and if $p \in B$ we want $p>q \Leftrightarrow y < 0$. We might as well take advantage of the sign of $p^2-2$ in each case to achieve this by searching for a positive quantity $x$ such that $q = p - (p^2-2)x$.

As you showed, any choice $0 < x < 1/(p+\sqrt{2})$ will satisfy the requirements $p \in A \Rightarrow q \in A$ and $p \in B \Rightarrow q \in B$. He wanted to ensure $x$ was rational, and the easiest way to do this is to take $x = 1/(p+k)$ where $k$ is an integer larger than or equal to $2$. There's no need to complicate matters further than that, so he simply chooses the smallest $k$ which works, namely $2$.

My derivation was the same as yours, and I doubt you could get it more simple than that.

As for why he didn't comment on his choice: well, that's kind of just how Rudin is. He will rarely (if ever?) comment on the motivation for his proofs! It is endearing to some and perhaps a little infuriating to others.

| cite | improve this answer | |
$\endgroup$
32
$\begingroup$

Rudin's approximation to $\sqrt{2}$ 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 stunningly 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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you for this! Though there's one thing I don't understand: the secant method tells us that in certain cases the sequence ${(S_{n})}$ will converge to the root of the given function, but does it also tell us that the value $S_{n}$ will be closer to the root than $S_{n-1}$? How does Rudin know that p' will be closer to the root than p and not farther away? $\endgroup$ – Rasputin Aug 25 '16 at 11:59
  • $\begingroup$ The Associativity link is dead $\endgroup$ – frogeyedpeas Oct 10 '17 at 16:20
  • $\begingroup$ @frogeyedpeas I fixed it $\endgroup$ – user153330 Mar 28 '18 at 16:25
  • $\begingroup$ @Rasputin Generally monotonicity is the trick: if $p<\sqrt{2}$ then $\left ( \frac{2p+2}{p+2} \right )^2 = \frac{4p^2+8p+4}{p^2+4p+4}=2\frac{2p^2+4p+2}{p^2+4p+4}<2$, because the denominator of the last expression is equal to the numerator plus $2-p^2$. On the other hand, $q>p$ is apparent from the form $q=p-\frac{p^2-2}{p+2}$. $\endgroup$ – Ian Jun 10 '18 at 4:20
  • $\begingroup$ @Rasputin Actually there's nothing that guarantees that $S_n>S_{n+1}$ or that $S_n<S_{n+1}$ just due to the Secant Method, what you can do however is to once you use the Secant Method to get some expression is to see whether that is the case (if it's not then you have to use some other method). $\endgroup$ – Stupid Questions Inc Oct 17 '19 at 10:28
10
$\begingroup$

Given a positive rational $p$ with $p^{2} < 2$, Rudin finds a rational $q$ with $q > p$ and $q^{2} < 2$. He finds an expression for $q$ in terms of $p$ which is definitely based on numerical techniques for finding square root of a number. Giving a formula for $q$ without any explanation makes it all the more mysterious and therefore this question came into being.

A much simpler approach is to show that such a $q$ exists without giving a direct formula for it. This is what Hardy does in the first chapter of his book "A Course of Pure Mathematics". Clearly for any given positive integer $n$, we can find find $n + 1$ rational numbers between $1$ and $2$ namely $1, 1 + 1/n$, $1 + 2/n, \cdots, 1 + n/n = 2$. Since $1^{2} < 2 < 2^{2}$, it is evident that in this sequence of rationals there will be a last whose square is less than $2$ and the next one will have its square greater than $2$.

Thus we have two rationals positive rationals $x, y$ such that $x^{2} < 2 < y^{2}$ and $y - x = 1/n$. By taking $n$ large enough it is easy to see that given any positive rational $\epsilon$ we can find positive rationals $x, y$ with $x^{2} < 2 < y^{2}, x < 2, y < 2$ and $y - x < \epsilon$. It thus follows that $y^{2} - x^{2} = (y + x)(y - x) < 4\epsilon$. This means that $(y^{2} - 2) + (2 - x^{2}) < 4\epsilon$ and hence $(y^{2} - 2) < 4\epsilon, (2 - x^{2}) < 4\epsilon$ as both the expressions $(y^{2} - 2), (2 - x^{2})$ are positive.

Now we choose $4\epsilon = 2 - p^{2}$ and then we can find positive rational $x$ such that $2 - x^{2} < 4\epsilon = 2 - p^{2}$ so that $x > p$ and we already have $x^{2} < 2$.

See the smartness of the above technique. Ideally what we need is an approximation (on the lower side) for $\sqrt{2}$ which is better than existing approximation $p$. So we just need to choose a rational between $p$ and $\sqrt{2}$. This is possible without even defining the symbol $\sqrt{2}$ because we have access to numbers $1$ (lower approx to $\sqrt{2}$) and $2$ (higher approx) and then we can divide the gap between $1$ and $2$ as finely as possible to obtain approximations to $\sqrt{2}$ which are as good as we need.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hardy says that given any rational $r$, and positive natural $N$, we can find a rational $s$ lying on either side of $r$. And given any two rational numbers we can interpolate successive rational numbers which differ from each other as little as we please. How do we prove these equivalent statements? $\endgroup$ – Maxis Jaisi Oct 6 '16 at 13:51
  • $\begingroup$ @MaxisJaisi: Hardy says that for given $r, N$ we can find an $s$ on either side of $r$ which differs from $r$ by less than $1/N$. Suppose we want an $s$ on right of $r$ (i.e. $s > r$) then we just have to choose a rational $s$ between $r$ and $r + (1/N)$. This is possible because between any two rationals there lies another rational. Similarly we can choose $s$ between $r - 1/N$ and $r$ and this will be less than $r$. Such statements are very obvious and easy to prove (for a student of 11-12 years) and I don't know what more I can say. $\endgroup$ – Paramanand Singh Oct 6 '16 at 18:48
8
$\begingroup$

Here's how I would be motivated to make Rudin's choice.

Say we have rational $p=\dfrac a b$ with integers $a,b; b\ne0$.

$p$ can be close to $\sqrt2$ but not equal. That is, $a-b\sqrt2$ can be small but not zero.

To find $c$ and $d$ such that $c-d\sqrt2$ is even smaller, multiply by $2-\sqrt2,$ which is between $0$ and $1.$

I.e., $(a-b\sqrt2)(2-\sqrt2)=\color{blue}{(2a+2b)}-\color{green}{(a+2b)}\sqrt2 < a-b\sqrt2$.

So take $\color{blue}{c=2a+2b}; \color{green}{d=a+2b}; q=\dfrac {\color{blue}{c}}{\color{green}{d}}$$=\dfrac {\color{blue}{{2a+2b}}}{\color{green}{a+2b}}=\dfrac{\color{blue}{2p+2}}{\color{green}{p+2}}$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Great idea! I like this :) $\endgroup$ – Stupid Questions Inc Oct 16 '19 at 7:40
2
$\begingroup$

Rudin's choice was quite natural:

From B, let $q=p-a>\sqrt{2}$, with $a,p,q\in\mathbb{Q^+}$.

It follows that $a<p-\sqrt{2}<p^2-2$, a rational number. Thus $$a=\frac{p^2-2}{b},$$ with $b\in\mathbb{Q^+}$. Notice $$\frac{p^2-2}{p+\sqrt{2}}=p-\sqrt{2}>a,$$ meaning $b>p+\sqrt{2}$ so $p+2$ will suffice. Having found a nice $a$ we can write $$q=p-\frac{p^2-2}{p+2}.$$

The same may be derived from A.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Please, avoid making several edits. $\endgroup$ – Aloizio Macedo May 6 at 10:58
1
$\begingroup$

There is also this approach: it is not difficult to figure out, through the binomial theorem, that both

$$P_n=(1+\sqrt{2})^n+(1-\sqrt{2})^n\qquad\text{and}\qquad Q_n = \frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{\sqrt{2}} $$ are integers, and $$ \lim_{n\to +\infty}\frac{P_n}{Q_n}=\sqrt{2}\lim_{n\to +\infty}\frac{(1+\sqrt{2})^n+(1-\sqrt{2})^n}{(1+\sqrt{2})^n-(1-\sqrt{2})^n}=\sqrt{2}\lim_{n\to +\infty}\frac{1+\frac{1}{(3+2\sqrt{2})^n}}{1-\frac{1}{(3+2\sqrt{2})^n}}=\sqrt{2}. $$ Both $P_n$ and $Q_n$ fulfill the recurrence relation $\ell_{n+2}=2\ell_{n+1}+\ell_n$, so $\frac{P_n}{Q_n}$ is exactly the $n$-th convergent of the continued fraction of $\sqrt{2}=[1;2,2,2,2,\ldots]$.

| cite | improve this answer | |
$\endgroup$

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.