Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Rational approximation of famous numbers"

(→‎Proof of the Main Theorem)
(added one section that is common for all three "non-Liouvillian" articles)
Line 30: Line 30:
 
=\frac{\log(Q/\gamma)}{\log(1/\gamma)}<\frac{\log(Q/\beta)}{\log(1/\gamma)} </math>).
 
=\frac{\log(Q/\gamma)}{\log(1/\gamma)}<\frac{\log(Q/\beta)}{\log(1/\gamma)} </math>).
  
 +
==Magic polynomial==
 +
Before proceeding to the applications of the main theorem, let us introduce one very useful polynomial that often appears in proofs of irrationality. It is the polynomial
 +
 +
<math>P(x)\frac 1{n!}\left(\frac d{dx}\right)^n [x^n(1-x)^n]</math>
 +
 +
Its coefficients can be easily computed using the [[Binomial Theorem|binomial theorem]]:
 +
 +
<math>P(x)=\sum_{k=0}^n (-1)^k{n+k\choose n}{n\choose k}x^k.</math>
 +
 +
The important points are that all the coefficients are integer and
 +
the sum of their absolute values does not exceed
 +
<math>\max_{0\le k\le n}{n+k\choose n}\sum_{0\le k\le n}{n\choose  k}\le {2n\choose n}2^n\le 8^n</math>.
 +
 +
Another useful remark is that the first <math>n-1</math> derivatives of <math>x^n(1-x)^n</math> vanish at <math>0</math> and <math>1</math>, which makes the integration by parts extremely convenient:
 +
 +
<math>\int_0^1 F(x)P(x)\,dx=(-1)^n\frac 1{n!}\int_0^1 F^{(n)}(x) x^n(1-x)^n\,dx.</math>
 +
 +
And now everything is ready for three
 
==Applications==
 
==Applications==
−
* Beuker's proof that [[pi is not Liouvillian]]
 
 
* Proof that [[e is not Liouvillian]]
 
* Proof that [[e is not Liouvillian]]
 
* Proof that [[ln 2 is not Liouvillian]]
 
* Proof that [[ln 2 is not Liouvillian]]
 +
* Beukers' proof that [[pi is not Liouvillian]]

Revision as of 21:51, 26 June 2006

Introduction

The Dirichlet's theorem shows that, for each irrational number $x\in\mathbb R$, the inequality $\left|x-\frac pq\right|<\frac 1{q^2}$ has infinitely many solutions. On the other hand, sometimes it is useful to know that $x$ cannot be approximated by rationals too well, or, more precisely, that $x$ is not a Liouvillian number, i.e., that for some power $M<+\infty$, the inequality $\left|x-\frac pq\right|\ge \frac 1{q^M}$ holds for all sufficiently large denominators $q$. So, how does one show that a number is not Liouvillian? The answer is given by the following.

Main theorem

Suppose that there exist $0<\beta<\gamma<1$, $1<Q<+\infty$ and a sequence of pairs of integers $(P_n,Q_n)$ such that for all sufficiently large $n$, we have $|Q_n|\le Q^n$ and $\beta^n< \left|P_n-Q_n x\right|<\gamma^n$. Then, for every $M>\frac{\log(Q/\beta)}{\log(1/\gamma)}$, the inequality $\left|x-\frac pq\right|<\frac 1{q^M}$ has only finitely many solutions.

The exact formulation of the main theorem in this article is fitted to the Beukers proof of the non-Liouvillian character of $\pi$, but the general spirit of all such theorems is the same: roughly speaking, they tell you that in order to show that $x$ cannot be approximated by rationals too well, one needs to find plenty of small, but not too small, linear combinations of $x$ and $1$ with not too large integer coefficients.

Proof of the Main Theorem

Choose the least $n$ such that $\gamma^n\le 2q$. Note that for such choice of $n$, we have $\gamma^n> \frac {\gamma}{2q}$. Also note that $Q_n\ne 0$ (otherwise $|P_n|$ would be an integer strictly between $0$ and $1$). Now, there are two possible cases:

Case 1: $P_n-Q_n\frac pq=0$. Then $\left|x-\frac pq\right|=\left|x-\frac {P_n}{Q_n}\right|>\frac{\beta^n}{|Q_n|}>(\beta/Q)^n =(\gamma^n)^{\frac{\log(Q/\beta)}{\log(1/\gamma)}}> \left(\frac\gamma{2q}\right)^{\frac{\log(Q/\beta)}{\log(1/\gamma)}}>\frac 1{q^M}$

if $q$ is large enough.

Case 2: $P_n-Q_n\frac pq\ne 0$. Then

$\frac 1q\le\left|P_n-Q_n\frac pq\right|\le \left|P_n-Q_n x\right|+|Q_n|\cdot\left|x-\frac pq\right|\le \frac 1{2q}+Q^n\left|x-\frac pq\right|$

Hence, in this case,

$\left|x-\frac pq\right|\ge \frac 1{2q}Q^{-n}\ge \frac \gamma{2q}Q^{-n}=\frac \gamma{2q}(\gamma^n)^{\frac{\log Q}{\log(1/\gamma)}}\ge \left(\frac\gamma{2q}\right)^{1+\frac{\log(Q}{\log(1/\gamma)}}>\frac 1{q^M}$

if $q$ is large enough. (recall that $\beta<\gamma$, so $1+\frac{\log Q}{\log(1/\gamma)} =\frac{\log(Q/\gamma)}{\log(1/\gamma)}<\frac{\log(Q/\beta)}{\log(1/\gamma)}$).

Magic polynomial

Before proceeding to the applications of the main theorem, let us introduce one very useful polynomial that often appears in proofs of irrationality. It is the polynomial

$P(x)\frac 1{n!}\left(\frac d{dx}\right)^n [x^n(1-x)^n]$

Its coefficients can be easily computed using the binomial theorem:

$P(x)=\sum_{k=0}^n (-1)^k{n+k\choose n}{n\choose k}x^k.$

The important points are that all the coefficients are integer and the sum of their absolute values does not exceed $\max_{0\le k\le n}{n+k\choose n}\sum_{0\le k\le n}{n\choose k}\le {2n\choose n}2^n\le 8^n$.

Another useful remark is that the first $n-1$ derivatives of $x^n(1-x)^n$ vanish at $0$ and $1$, which makes the integration by parts extremely convenient:

$\int_0^1 F(x)P(x)\,dx=(-1)^n\frac 1{n!}\int_0^1 F^{(n)}(x) x^n(1-x)^n\,dx.$

And now everything is ready for three

Applications

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Rational_approximation_of_famous_numbers&oldid=4812"