10
$\begingroup$

(1) Suppose $\frac{p_1}{q_1}$ and $\frac{p_2}{q_2}$ are rationals with $0<\frac{p_1}{q_1} <\frac{p_2}{q_2}$. We want to find a rational $\frac{a}{b}$ such that $\frac{p_1}{q_1}<\frac{a^2}{b^2} <\frac{p_2}{q_2}$.

I know that if we choose any rational in the open interval between $\sqrt{\frac{p_1}{q_1}}$ and $\sqrt{\frac{p_2}{q_2}}$, then this rational will have the desired property. However, the issue is that I am trying to use this proof as a part of a larger proof to prove the existence of the square root of any positive real number. So I cannot use any argument that directly references square roots.

Here is some work I have done so far. I went down the rabbit hole a bit and this may be a dead end, I'm not sure.

Since $\frac{p_1}{q_1} = \frac{p_1q_1q_2^2}{q_1^2q_2^2}$ and $\frac{p_2}{q_2} = \frac{p_2q_1^2q_2}{q_1^2q_2^2}$, it is sufficient to prove that:

(2) there exists a perfect square, $n^2$, (possibly 1) such that the interval between $n^2p_1q_1q_2^2$ and $n^2p_2q_1^2q_2$ contains a perfect square.

To prove (2) it is sufficient to prove that:

(3) for all positive integers $n$ there exist perfect squares, $k^2$ and $m^2$, such that $k^2n<m^2<k^2(n+1)$

So my question is either for assistance proving any of (1), (2), or (3) without using the existence of square roots of positive real numbers,

OR if this is something that MUST be proven using the existence of square roots, then just state that. I would NOT like help in proving the existence of square roots another way. If it MUST be done another way, I would like to figure out the other way myself.

That being said, I am sure that proving the existence of square roots of positive reals CAN be proven another way (likely much simpler), but I am hoping that the path I am taking may work too. I just need help with this last part.

$\endgroup$
  • $\begingroup$ Hint: $p_1q_1$ are between two perfect squares, namely $p_1^2$ and $q_1^2$. Why can't $p_1=q_1$? $\endgroup$ – Simply Beautiful Art Sep 15 '19 at 17:21
  • $\begingroup$ Well in theory $p_1$ can be equal to $q_1$ if the original interval starts at 1. But I'm sure this is a case that can be handled separately and am happy to assume for now that $p_1$ is different from $q_1$. $\endgroup$ – M D Sep 15 '19 at 17:36
  • $\begingroup$ Here's a theorem for you: Between any two real numbers there is a rational. This fact is a jumping off point from your very second line. A rational is between those two irrationals, because those irrationals are reals. $\endgroup$ – SquishyRhode Sep 15 '19 at 17:54
  • $\begingroup$ Yes, I am comfortable using the theorem that between any two reals there is a rational. However, the second line is one that I cannot use in my proof because it assumes that the square root of $\frac{p_1}{q_1}$ is a real number. I know that if I were to use that, then I would be done. My goal is to prove the original statement without ever referencing square roots. $\endgroup$ – M D Sep 15 '19 at 17:56
  • $\begingroup$ Nice question (+1). The answer is not difficult but at the same it is not obvious to a beginner in analysis. $\endgroup$ – Paramanand Singh Sep 16 '19 at 6:57
2
$\begingroup$

The following proof does not assume any knowledge of real numbers and square roots and uses only the properties of rational numbers. The argument below is typical of many analytical arguments and is the essence of definition of real numbers as envisaged first by Dedekind.


Let $x, y$ be two positive rationals with $x<y$. We are supposed to find a rational $a$ such that $x<a^2<y$. The problem is easily handled if $y$ itself is a perfect square. Thus if $y=t^2$ then we can choose $a<t$ such that $$y-a^2=t^2-a^2<y-x$$ ie $$(t-a) (t+a) <y-x$$ and this is easily done if we choose $$t-a<\frac{y-x} {2t}$$

We are thus left with the difficult case when $y$ is not a square. Let's consider the set $$A=\{a\mid a\in\mathbb {Q}, a>0,a^2<y\}$$ Clearly this set is non empty and bounded above. We will prove that there is no greatest member in this set. Suppose on the contrary that there is a greatest member, say $m$, in $A$. Then we have $m^2<y$ but for any rational $n>m$ we have $n^2>y$. Let's further assume $m<n<m+1$ and then we have $$n^2-m^2=(n-m)(n+m)<(n-m)(2m+1)$$ And we have an obvious contradiction if $$0<n-m<\min\left(1,\frac{y-m^2}{2m+1}\right)$$ because then we have $n^2-m^2<y-m^2$ or $n^2<y$.

In a similar manner we can show that the set $$B=\{b\mid b\in\mathbb {Q}, b>0,b^2>y\}$$ is non-empty, bounded below and has no least member. Now we can choose some specific members $a\in A, b\in B$ and an arbitrary positive integer $n$ and consider the sequence of numbers $$x_i=a+i\cdot\frac{b-a} {n} $$ so that $$a=x_0<x_1<x_2<\dots<x_n=b$$ In the above sequence there is a last, say $x_r$, which lies in $A$ and the next one $x_{r+1}\in B$ and we have $x_{r+1}-x_r=1/n$. Since $n$ is arbitrary it follows that give any positive rational number $\epsilon$ we can find members $a\in A, b\in B$ such that $b-a<\epsilon$.

Next we set $\epsilon=y-x>0$ and consider a specific number $k\in B$. Now we can choose $a\in A, b\in B$ with $b-a<\epsilon/(2k)$ and also ensure $b<k$. This implies that $a<b<k$ and thus $a+b<2k$ and $$b^2-a^2=(b+a)(b-a)<2k\cdot\frac{\epsilon}{2k}=\epsilon$$ or $$(b^2-y)+(y-a^2)<\epsilon$$ Each term in parentheses in positive and hence individually less than $\epsilon $. We thus have $$y-a^2<\epsilon=y-x$$ or $x<a^2<y$. Thus we have found a rational number $a$ as desired.


The above proof can be worked out (to aid in understanding) for specific example. Let's say we wish to find a square between $x=1.9$ and $y=2$. We take $a=1\in A, b=2\in B$ and set $n=100$ ($n$ is choosen such that $1/n< (y-x) / 2b$) and consider sequence of numbers $x_i=1+(i/100)$. Clearly $x_{41}=1.41\in A, x_{42}=1.42\in B$ and $1.9<1.41^2<2$.

$\endgroup$
2
$\begingroup$

Let rational $\ x\ z\in\mathbb Q\ $ be such that $\ 0<x<z;\ $ for instance, let $\ x:=\frac{p_1}{q_1}\ $ and $\ z:=\frac{p_2}{q_2},\ $ where the fractions are as in the OP's Question. Let $\ y:=\frac{x+z}2,\ $ so that $\ 0<x<y<z;\ (y\in\mathbb Q).$

The classical (and beautiful) Newton's method provides arbitrarily good rational approximations $\ r_n\ $ of $\ \sqrt y\ $ in the most elementary way, and $\ r_n^2\ $ provides an answer to the OP's Question when the Newton approximation is advanced enough.

The consecutive Newton approximations $\ r_n\ $ of $\ y\ $ converge to $\ y\ $ very fast:

$$ \rho_0:= 1\qquad r_0:=y $$ and $$ \rho_n\ :=\ \frac{\rho_{n-1}+r_{n-1}}2 $$ $$ r_n\ :=\ \frac y{\rho_n} $$

for arbitrary $\ n=1\ 2\ \ldots$.

we see that:

$$ \forall_{n=0}^\infty\quad \rho_n\cdot r_n\ =\ y $$ and, depending on $ y\le 1\ $ or $\ y\ge 1$, we get $$ r_0^2\ \le y\ \le \rho_0^2\qquad\mbox{or} \qquad r_0^2\ \ge y\ \ge \rho_0^2 $$ and $$ \forall_{n\in\mathbb N}\quad r_n^2\ \le\ y\ \le\ \rho_n^2 $$

I'll leave the estimates of the wonderful speed of approximation as a pleasant and most rewarding exercise (perhaps in mathematical induction).

$\endgroup$
  • $\begingroup$ If we $r$ is an approximation of $y$, then why is it true that $x<r^2<z$? I can see that we can have $x<r<z$, but not why $r^2$ should be in the interval. $\endgroup$ – M D Sep 15 '19 at 18:26
  • $\begingroup$ I am not as familiar with Newton's method approximations as I would like to be, so that is probably the main source of my confusion, not the clarity of your answer (which I appreciate you taking the time to write). With that said, in your comment you say that $r^2$ approximates $y$ very fast, but in the second sentence of your answer you say $r$ approximates $y$. So there is a rational number $r$ that is very close to $y$ and $r^2$ is also very close to $y$? I know there is something I am missing, but I may just need to read more about Newton's method. $\endgroup$ – M D Sep 15 '19 at 18:37
  • $\begingroup$ I tried too hard to edit well the general remarks so it was a bit of mess. The mathematics was fine all the time, I didn't change anything. Now, I fixed a typo and the general remarks. $\endgroup$ – Wlod AA Sep 15 '19 at 18:40
1
$\begingroup$

HINT:

Let your rationals be $0< r_1 < r_2$. Consider $0<a < b$ rationals so that $a^2 < r_1$ and $b^2 > r_2$. Now consider a set of intermediate points $x_k=a + \frac{k(b-a)}{N}$, $\ k = 0,1,\ldots, N$, where $N$ is sufficiently large so that $0<f(x_{k+1})-f(x_k)<r_2 - r_1$ for all $k$. It should be easy now.

ADDED: This works in a similary for any other "continuous" function $f$, like a polynomial. The property is "weak intermediate value", that is, if $f(a)\ne f(b)$ then $f([a,b]\cap \mathbb{Q})$ is dense in $[f(a),f(b)]$.

Note that even if we "avoid using the reals" in the proof, we used natural numbers and the fact that $\mathbb{Q}$ is an archimedean ordered field ( a subfield of $\mathbb{R}$ as it is).

$\endgroup$
  • $\begingroup$ Is the function $f$ meant to be $f(x) =x^2$? $\endgroup$ – M D Sep 16 '19 at 10:07
  • $\begingroup$ This is essentially the same idea as in my answer. BTW why do we need to know $\mathbb {Q} $ is a subset of $\mathbb {R} $ (see your last sentence)? $\endgroup$ – Paramanand Singh Sep 19 '19 at 3:10
  • $\begingroup$ @Paramanand Singh: Yes, you are right. For your question, we need to use the fact that our ordered field is archimedean. This is equivalent to being a subfield of $\mathbb{R}$. $\endgroup$ – orangeskid Sep 19 '19 at 4:38
0
$\begingroup$

NOTE: this answer ignores the constraints of the question.

Here's one way to do it.

Let $f$ be defined as follows:

$$ f(x) = x \cdot |x| $$

And let $f^{-1}$ be the inverse of $f$.

$f$ is like the square function except that it preserves signs. Note that $f$ is monotonic.

Let's define a function $B : \mathbb{Z} \times \mathbb{R} \to \mathbb{Q}$ .

$B_x(\alpha)$ is the largest rational number strictly less than $\alpha$ that is expressible as a fraction with a denominator of $x$. That fraction is not required to be in simplest form.

$$ B_x(\alpha) = \sup \left( \mathbb{R}_{\le \alpha} \;\bigcap\; \left\{ \frac{w}{x} \mathop. w \in \mathbb{Z} \right\} \right) $$

Here are a few examples:

$$ B_3\left(\frac{1}{2}\right) = \frac{1}{3} $$

$$ B_4\left(\frac{2}{3}\right) = \frac{2}{4} \;\;\text{and furthermore}\;\; B_4\left(\frac{2}{3}\right) = \frac{1}{2} $$


Lemma 101: upper bound on $\alpha - B_x(\alpha)$

The distance between $\alpha$ and $B_x(\alpha)$ is always less than or equal to $\frac{1}{x}$ . If the distance were any greater than $\frac{1}{x} + B_x(\alpha)$ would be closer to $\alpha$ than $B_x(\alpha)$, but still less than $B_x(\alpha)$ . This is a contradiction.

$$ \alpha - B_x (\alpha) \le \frac{1}{x} \tag{101} $$


Theorem 102: There exist integers $x$ and $y$ such that $\frac{a}{b} < \frac{xx}{yy} < \frac{p}{q} $

We are trying to show the following:

$$ \forall a p \in \mathbb{Z} \mathop. \forall b q \in \mathbb{Z} \setminus \{0\} \mathop. \exists x y \in \mathbb{Z} \mathop. \frac{a}{b} < \frac{p}{q} \implies \frac{a}{b} < \frac{xx}{yy} < \frac{p}{q} \tag{102} $$

Let $\beta = f^{-1}\left(\frac{p}{q}\right) - f^{-1}\left(\frac{a}{b}\right)$ . This is the distance between the pseudo-square root of our two endpoints.

Let $\gamma = \min\left(10, \lceil \frac{1}{\beta} \rceil \right)$ . $\gamma$ is a positive integer such that $\frac{1}{\gamma}$ is guaranteed to be smaller than $\beta$ .

Let $\delta$ be the smallest power of $2$ bigger than or equal to $\gamma$ .

$$ \delta = 2^{\lceil \mathrm{lb} \gamma \rceil} $$

Let's pick $\varepsilon$ as follows. It will be the numerator of our fraction.

$$ \varepsilon = B_\delta\left(f^{-1}\left(\frac{p}{q}\right)\right)$$

Because of how we picked $\delta$ we know the following:

$$ f^{-1}\left(\frac{a}{b}\right) < \frac{\varepsilon}{\delta} < f^{-1}\left(\frac{p}{q}\right) $$

And thus by applying $f$, our sign-preserving pseudo-square function.

$$ \frac{a}{b} < \pm \frac{\varepsilon\varepsilon}{\delta\delta} < \frac{p}{q} $$

In the cases where $\frac{a}{b}$ and $\frac{p}{q}$ are both positive, $ \frac{\varepsilon\varepsilon}{\delta\delta} $ is a perfect square as desired since it's positive.

$\endgroup$
  • $\begingroup$ Thanks for taking the time to answer. I see that you noted that this ignores the constraints of the problem. Is it because of the assumption that the inverse of $f$ is defined for all reals? I believe that is equivalent to assuming what I am trying to prove. For instance, how do we know $f^{-1}(2)$ exists without assuming that there exists a positive real number whose square is 2? Is this what your note was referring to? $\endgroup$ – M D Sep 15 '19 at 18:57
  • $\begingroup$ @MD Yes. I'm assuming the existence of square roots and not bothering to prove that they exist. I normally read details of proof attempts after composing an answer, but by then it was too late. :/ I think this approach might be salvageable if I use something like the Babylonian method to get upper and lower rational bounds to the square roots, but then it would be equivalent to the other answer. If it's adding no value, I can simply delete it. $\endgroup$ – Gregory Nisbet Sep 15 '19 at 19:10
  • $\begingroup$ No need to delete it! $\endgroup$ – M D Sep 15 '19 at 19:15

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.