Difference between revisions of "Rational approximation of famous numbers"

(added one section that is common for all three "non-Liouvillian" articles)
(hm)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
==Introduction==
+
'''Rational approximation''' is the application of [[Rational approximation|Dirichlet's theorem]] which shows that, for each irrational number <math>x\in\mathbb R</math>, the inequality <math>\left|x-\frac pq\right|<\frac 1{q^2}</math> has infinitely many solutions. On the other hand, sometimes it is useful to know that <math>x</math> cannot be approximated by rationals too well, or, more precisely, that <math>x</math> is not a [[Liouvillian number]], i.e., that for some power <math>M<+\infty</math>, the [[inequality]] <math>\left|x-\frac pq\right|\ge \frac 1{q^M}</math> holds for all sufficiently large denominators <math>q</math>.  
The [[Rational approximation|Dirichlet's theorem]] shows that, for each irrational number <math>x\in\mathbb R</math>, the inequality <math>\left|x-\frac pq\right|<\frac 1{q^2}</math> has infinitely many solutions. On the other hand, sometimes it is useful to know that <math>x</math> cannot be approximated by rationals too well, or, more precisely, that <math>x</math> is not a [[Liouvillian number]], i.e., that for some power <math>M<+\infty</math>, the inequality <math>\left|x-\frac pq\right|\ge \frac 1{q^M}</math> holds for all sufficiently large denominators <math>q</math>. So, how does one show that a number is not Liouvillian? The answer is given by the following.
+
==Theorem==
==Main theorem==
 
 
Suppose that there exist <math>0<\beta<\gamma<1</math>, <math>1<Q<+\infty</math>
 
Suppose that there exist <math>0<\beta<\gamma<1</math>, <math>1<Q<+\infty</math>
 
and a sequence of pairs of integers <math>(P_n,Q_n)</math> such that for all sufficiently large <math>n</math>, we have <math>|Q_n|\le Q^n</math> and  
 
and a sequence of pairs of integers <math>(P_n,Q_n)</math> such that for all sufficiently large <math>n</math>, we have <math>|Q_n|\le Q^n</math> and  
Line 8: Line 7:
 
The exact formulation of the main theorem in this article is fitted to the Beukers proof of the non-Liouvillian character of <math>\pi</math>, but the general spirit of all such theorems is the same: roughly speaking, they tell you that in order to show that <math>x</math> cannot be approximated by rationals too well, one needs to find plenty of small, but not too small, linear combinations of  <math>x</math> and <math>1</math> with not too large integer coefficients.
 
The exact formulation of the main theorem in this article is fitted to the Beukers proof of the non-Liouvillian character of <math>\pi</math>, but the general spirit of all such theorems is the same: roughly speaking, they tell you that in order to show that <math>x</math> cannot be approximated by rationals too well, one needs to find plenty of small, but not too small, linear combinations of  <math>x</math> and <math>1</math> with not too large integer coefficients.
  
==Proof of the Main Theorem==
+
===Proof===
 
Choose the least <math>n</math> such that <math>\gamma^n\le 2q</math>. Note that for such choice of <math>n</math>, we have <math>\gamma^n> \frac {\gamma}{2q}</math>. Also note that <math>Q_n\ne 0</math> (otherwise <math>|P_n|</math> would be an integer strictly between <math>0</math> and <math>1</math>). Now, there are two possible cases:
 
Choose the least <math>n</math> such that <math>\gamma^n\le 2q</math>. Note that for such choice of <math>n</math>, we have <math>\gamma^n> \frac {\gamma}{2q}</math>. Also note that <math>Q_n\ne 0</math> (otherwise <math>|P_n|</math> would be an integer strictly between <math>0</math> and <math>1</math>). Now, there are two possible cases:
  
Line 30: Line 29:
 
=\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==
+
==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  
 
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  
  
Line 47: Line 46:
 
<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>  
 
<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
+
==Example==
==Applications==
+
This section will prove that the number <math>\ln 2</math> is not [[Liouvillian number|Liouvillian]]. It can be read right after its parent article [[rational approximation of famous numbers]]. The proof of the non-Liouvillian character of <math>\ln 2</math> is much easier than that for <math>\pi</math>, but somewhat more difficult than that for <math>e</math>.
* Proof that [[e is not Liouvillian]]
+
 
* Proof that [[ln 2 is not Liouvillian]]
+
===A Useful Integral===
* Beukers' proof that [[pi is not Liouvillian]]
+
Everyone knows an integral representation for <math>\ln 2</math>. It comes right from the definition of the natural [[logarithm]]: <math>\ln 2=\int_0^1\frac {1}{1+x}\,dx</math>. Let us look at what will happen if we replace <math>1</math> in the numerator by some polynomial <math>P(x)</math> of degree <math>n</math> with integer coefficients. Since <math>P(x)-P(-1)=(1+x)R(x)</math> where <math>R(x)=\sum_{k=0}^{n-1} c_k x^k</math> is some polynomial of degree <math>n-1</math> with integer coefficients, we see that
 +
 
 +
<math>\int_0^1\frac{P(x)}{1+x}\,dx=\sum_{k=0}^{n-1}\frac {c_k}{k+1}+P(-1)\ln 2.</math>
 +
 
 +
Let now <math>D_n</math> be the [[least common multiple]] of the numbers <math>1,2,\dots, n</math>. Then
 +
 
 +
<math>D_n\int_0^1\frac{P(x)}{1+x}\,dx=P_n-Q_n\ln 2</math>
 +
 
 +
with some integer <math>P_n</math> and <math>Q_n=-D_nP(-1)</math>.
 +
It remains to choose a polynomial <math>P(x)</math> that makes the integral small.
 +
 
 +
===Polynomial <math>P(x)</math>===
 +
We shall just take our "magic polynomial" <math>P(x):=\frac{1}{n!}\left(\frac{d}{dx}\right)^n[x^n(1-x)^n]</math>
 +
(see the [[rational approximation of famous numbers|parent article]] for its properties).
 +
 
 +
===Estimates of the Integral===
 +
Integrating by parts <math>n</math> times, we see that
 +
<math>\int_0^1\frac{P(x)}{1+x}\,dx=
 +
(-1)^n\int_0^1\left[\frac{x(1-x)}{1+x}\right]^n\,\frac{dx}{1+x}</math>.
 +
Since <math>\max_{0<x<1}x(1-x)=\frac 14</math> and since it is attained only at the point <math>x=\frac 12</math> where <math>1+x>1</math>, we can conclude that <math>\Gamma=\max_{0<x<1}\frac{x(1-x)}{1+x}<\frac 14</math>. The absolute value of our integral does not exceed <math>\Gamma^n</math> for all <math>n</math>. To estimate it from below, just notice that the integrand is at least <math>\frac 12\left(\frac 2 {15}\right)^n</math> for <math>\frac 1 3 < x< \frac 2 3</math>, so the absolute value of our integral is at least <math>\frac 16\left(\frac 2 {15}\right)^n>\left(\frac 1 8\right)^n</math> for large <math>n</math>.
 +
 
 +
===Estimate of <math>D_n</math>===
 +
Since the largest possible power of a given prime <math>p\le n</math> that can divide one of the numbers <math>1,2,\dots,n</math> is <math>\left\lfloor\frac{\log n}{\log p}\right\rfloor</math> where <math>\lfloor\cdot\rfloor</math> is the floor function, we have
 +
 
 +
<math>D_n=\prod_{p\mathrm{\ prime,}\,p\le n}p^{\left\lfloor\frac{\log n}{\log p}\right\rfloor}\le \left(\prod_{p\mathrm{\ prime,}\,p\le \sqrt n}n\right)\cdot\left( \prod_{p\mathrm{\ prime,}\,\sqrt n<p\le n}p\right)\le n^{\sqrt n}\cdot\prod_{p\mathrm{\ prime,}\,p\le n}p\le n^{\sqrt n}\cdot 4^n</math>
 +
 
 +
according to [[Prime Number Theorem|Chebyshev's estimate]]. Also, we clearly have <math>D_n\ge 1</math>. Thus the absolute value of the product <math>D_n\int_0^1\frac{P(x)}{1+x}\,dx</math>
 +
is between <math>(1/8)^n</math> and <math>(4\Gamma)^n\cdot n^{\sqrt n}</math> for large <math>n</math>. Note that <math>n^{\sqrt n}</math> grows slower than any geometric progression, so the upper bound can be replaced by <math>\gamma^n</math> with any <math>\gamma\in(4\Gamma, 1)</math>. In order to apply the main theorem from the [[rational approximation of famous numbers|parent article]], it remains to show that <math>Q_n</math> do not grow too fast.
 +
 
 +
===Estimate of <math>Q_n</math>===
 +
We already saw that <math>D_n</math> grows not much faster than <math>4^n</math>. As to <math>|P(-1)|</math>, it does not exceed the sum of the absolute values of the coefficients of <math>P(x)</math>, which is not greater than <math>8^n</math>. Thus <math>|Q_n|</math> grow not much faster than <math>32^n</math>, and we are done.
 +
 
 +
==See Also==
 +
*[[Euler's constant]]
 +
*[[Pi]]
 +
 
 +
[[Category:Number theory]]

Latest revision as of 12:48, 26 January 2008

Rational approximation is the application of Dirichlet's theorem which 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$.

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

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.$

Example

This section will prove that the number $\ln 2$ is not Liouvillian. It can be read right after its parent article rational approximation of famous numbers. The proof of the non-Liouvillian character of $\ln 2$ is much easier than that for $\pi$, but somewhat more difficult than that for $e$.

A Useful Integral

Everyone knows an integral representation for $\ln 2$. It comes right from the definition of the natural logarithm: $\ln 2=\int_0^1\frac {1}{1+x}\,dx$. Let us look at what will happen if we replace $1$ in the numerator by some polynomial $P(x)$ of degree $n$ with integer coefficients. Since $P(x)-P(-1)=(1+x)R(x)$ where $R(x)=\sum_{k=0}^{n-1} c_k x^k$ is some polynomial of degree $n-1$ with integer coefficients, we see that

$\int_0^1\frac{P(x)}{1+x}\,dx=\sum_{k=0}^{n-1}\frac {c_k}{k+1}+P(-1)\ln 2.$

Let now $D_n$ be the least common multiple of the numbers $1,2,\dots, n$. Then

$D_n\int_0^1\frac{P(x)}{1+x}\,dx=P_n-Q_n\ln 2$

with some integer $P_n$ and $Q_n=-D_nP(-1)$. It remains to choose a polynomial $P(x)$ that makes the integral small.

Polynomial $P(x)$

We shall just take our "magic polynomial" $P(x):=\frac{1}{n!}\left(\frac{d}{dx}\right)^n[x^n(1-x)^n]$ (see the parent article for its properties).

Estimates of the Integral

Integrating by parts $n$ times, we see that $\int_0^1\frac{P(x)}{1+x}\,dx= (-1)^n\int_0^1\left[\frac{x(1-x)}{1+x}\right]^n\,\frac{dx}{1+x}$. Since $\max_{0<x<1}x(1-x)=\frac 14$ and since it is attained only at the point $x=\frac 12$ where $1+x>1$, we can conclude that $\Gamma=\max_{0<x<1}\frac{x(1-x)}{1+x}<\frac 14$. The absolute value of our integral does not exceed $\Gamma^n$ for all $n$. To estimate it from below, just notice that the integrand is at least $\frac 12\left(\frac 2 {15}\right)^n$ for $\frac 1 3 < x< \frac 2 3$, so the absolute value of our integral is at least $\frac 16\left(\frac 2 {15}\right)^n>\left(\frac 1 8\right)^n$ for large $n$.

Estimate of $D_n$

Since the largest possible power of a given prime $p\le n$ that can divide one of the numbers $1,2,\dots,n$ is $\left\lfloor\frac{\log n}{\log p}\right\rfloor$ where $\lfloor\cdot\rfloor$ is the floor function, we have

$D_n=\prod_{p\mathrm{\ prime,}\,p\le n}p^{\left\lfloor\frac{\log n}{\log p}\right\rfloor}\le \left(\prod_{p\mathrm{\ prime,}\,p\le \sqrt n}n\right)\cdot\left( \prod_{p\mathrm{\ prime,}\,\sqrt n<p\le n}p\right)\le n^{\sqrt n}\cdot\prod_{p\mathrm{\ prime,}\,p\le n}p\le n^{\sqrt n}\cdot 4^n$

according to Chebyshev's estimate. Also, we clearly have $D_n\ge 1$. Thus the absolute value of the product $D_n\int_0^1\frac{P(x)}{1+x}\,dx$ is between $(1/8)^n$ and $(4\Gamma)^n\cdot n^{\sqrt n}$ for large $n$. Note that $n^{\sqrt n}$ grows slower than any geometric progression, so the upper bound can be replaced by $\gamma^n$ with any $\gamma\in(4\Gamma, 1)$. In order to apply the main theorem from the parent article, it remains to show that $Q_n$ do not grow too fast.

Estimate of $Q_n$

We already saw that $D_n$ grows not much faster than $4^n$. As to $|P(-1)|$, it does not exceed the sum of the absolute values of the coefficients of $P(x)$, which is not greater than $8^n$. Thus $|Q_n|$ grow not much faster than $32^n$, and we are done.

See Also