If $\Big|x-\frac{p}{q}\Big|<\frac{1}{2q^2}$ then $p/q$ is necessarily one of the convergents : Extend the proof to irrational $x$

218 Views Asked by At

Prove that, if $x$ is any irrational number, and if $p/q$ is a rational fraction in lowest terms, with $q\geq 1$, such that $$\Big|x-\frac{p}{q}\Big|<\frac{1}{2q^2}$$ then $p/q$ is necessarily one of the convergents of the simple continued fraction expansion of $x$.

A proof assuming $x$ as a rational number is given in Page 637,638, Appendix 4 : Number Theory, Quantum Computation and Quantum Information by Nielsen and Chuang.

qcc qc

The proof in the given reference is for the case when $x$ is rational, so can I extend the proof for the case when $x$ is irrational ?

My Attempt

If $x$ is irrational number the continuous fraction expansion is $x=[a_0,a_1,\cdots,a_n,\cdots]=[a_0,a_1,\cdots,a_n,x_{n+1}]$ where $x_{n+1}=[a_{n+1},a_{n+2},\cdots]$, then $x=\frac{x_{n+1}p_n+p_{n-1}}{x_{n+1}q_n+q_{n-1}}$

Therefore in equation A.4.53, $$ x=\frac{\lambda p_n+p_{n-1}}{\lambda q_n+q_{n-1}}\implies x_{n+1}=\lambda\implies x=[a_0,a_1,\cdots,a_n,\lambda] $$ Choosing $n$ as even, we have $\lambda=\frac{2}{\delta}-\frac{q_{n-1}}{q_n}>2-1=1$

So since $x$ is irrational, $\lambda$ is an irrational number greater than $1$, therefore has a simple continuous fraction $\lambda=[b_0,b_1,\cdots]$, and so $x=[a_0,a_1,\cdots,a_n,\lambda]=[a_0,a_1,\cdots,a_n,b_0,b_1,\cdots]$ is a simple continuous fraction for $x$ with $p/q=p_n/q_n$ as the convergent.

Is it an extension of the given proof when $x$ is irrational ?

1

There are 1 best solutions below

4
On

If $x$ is irrational and $|x - \frac pq| < \frac1{2q^2}$, let $x'$ be any convergent of $x$ strictly between $x$ and $\frac pq$: this exists since $x$ has infinitely many convergents, getting arbitrarily close to $x$ from both sides. Then $|x' - \frac pq| < \frac1{2q^2}$ as well; therefore $\frac pq$ is a convergent of $x'$ by the theorem, and any convergent of $x'$ is also a convergent of $x$.