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"
(hm)
 
(12 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
{{stub}}
+
'''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>.  
−
==Introduction==
+
==Theorem==
−
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
+
Suppose that there exist <math>0<\beta<\gamma<1</math>, <math>1<Q<+\infty</math>
−
==Main theorem==
+
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  
−
''
+
<math>\beta^n< \left|P_n-Q_n x\right|<\gamma^n</math>. Then, for every <math>M>\frac{\log(Q/\beta)}{\log(1/\gamma)}</math>, the inequality <math>\left|x-\frac pq\right|<\frac 1{q^M}</math> has only finitely many solutions.
−
Suppose that there exist <math>\beta>\mu>1</math>, <math>Q>1</math>
 
−
and a sequence of rational numbers <math>\frac {P_n}{Q_n}</math> such that for all <math>n</math>, <math>Q_n\le Q^n</math> and  
 
−
<math>Q^{-\beta n}< \left|x-\frac {P_n}{Q_n}\right|<Q^{-\mu n}</math>. Then, for every <math>M>\frac\beta{\mu-1}</math>, the inequality <math>\left|x-\frac pq\right|<\frac 1{q^M}</math> 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 <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 good but not too good rational approximations of <math>x</math>.  
+
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:
 +
 
 +
'''Case 1:''' <math>P_n-Q_n\frac pq=0</math>.
 +
Then <math>\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}</math>
 +
 
 +
if <math>q</math> is large enough.
 +
 
 +
'''Case 2:''' <math>P_n-Q_n\frac pq\ne 0</math>. Then
 +
 
 +
<math>\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|
 +
</math>
 +
 
 +
Hence, in this case,
 +
 
 +
<math>\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}</math>
 +
 
 +
if <math>q</math> is large enough. (recall that <math>\beta<\gamma</math>, so <math>1+\frac{\log Q}{\log(1/\gamma)}
 +
=\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>
 +
 
 +
==Example==
 +
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>.
 +
 
 +
===A Useful Integral===
 +
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

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