pdf
Rational approximation — aops wiki
proofwiki
The Beginning of Transcendental Numbers
1.1 Review of Approximating by Rationals
Definition 1.1.1 (Approximated by rationals to order $n$) A real number $x$ is approximated by rationals to order $n$ if there exist a constant $k(x)$ (possibly depending on $x$) such that there are infinitely many rational $\frac pq$ with$$\left|x-\frac{p}{q}\right|< \frac{k(x)}{q^{n}}\tag1\label1$$Recall that Dirichlet’s Box Principle gives us:$$\left|x-\frac{p}{q}\right|< \frac{1}{q^{2}}\tag2\label2$$for infinitely many fractions $\frac pq$. This was proved by choosing a large parameter $Q$, and considering the $Q+1$ fractionary parts $\{qx\} ∈ [0, 1)$ for $q ∈ \{0,…, Q\}$. The box principle ensures us that there must be two different $q$’s, say: $0 \leq q_{1}< q_2\le Q$ such that both $\{q_1x\}$ and $\{q_2x\}$ belong to the same interval $\left[\frac{a}{Q}, \frac{a+1}{Q}\right)$, for some $0 ≤ a ≤ Q − 1$. Note that there are exactly $Q$ such intervals partitioning $[0, 1)$, and $Q + 1$ fractionary parts! Now, the length of such an interval is $\frac1Q$ so we get $\left|\left\{q_2x\right\}-\left\{q_1x\right\}\right|< \frac1Q$. There exist integers $p_1$ and $p_2$ such that $\left\{q_1x\right\}=q_1x-p_1,\left\{q_2x\right\}=q_2x-p_2$. Letting $p=p_{2}-p_{1}$ we find $\left|\left(q_{2}-q_{1}\right) x-p\right| \leq \frac{1}{Q}$. Let $q = q_2 − q_1$, so $1 ≤ q ≤ Q$, and the previous equation can be rewritten as$$\left|x-\frac{p}{q}\right|< \frac{1}{q Q} \leq \frac{1}{q^{2}}\label3\tag3$$Now, letting $Q → ∞$, we get an infinite collection of rational fractions $p/q$ satisfying the above equation. If this collection contains only finitely many distinct fractions, then one of these fractions, say $p_0/q_0$, would occur for infinitely many choices $Q_k$ of $Q$, thus giving us: $\left|x-\frac{p_{0}}{q_{0}}\right|< \frac{1}{q Q_{k}} \rightarrow 0$ as $k → ∞$. This implies that $x =p_0/q_0∈\mathbb Q$. So, unless $x$ is a rational number, we can find infinitely many distinct rational numbers $p/q$ satisfying \eqref{3}. This means that any real, irrational number can be approximated to order $n = 2$ by rational numbers.
1.2 Liouville’s Theorem
Theorem 1.2.1 (Liouville’s Theorem). Let $x$ be a real algebraic number of degree $n$. Then $x$ is approximated by rationals to order at most $n$.
Proof. Let $f(X)=a_{n} X^{n}+\cdots a_{1} X+a_{0}$ be the polynomial with integer coefficients of smallest degree (minimal polynomial) such that $x$ satisfies $f(x)=0$. Note that $\deg x = \deg f$ and the condition of minimality implies that $f(X)$ is irreducible over $\mathbb Z$. Further, a well known result from algebra states that a polynomial irreducible over $\mathbb Z$ is also irreducible over $\mathbb Q$. In particular, as $f(X)$ is irreducible over $\mathbb Q$, $f(X)$ does not have any rational roots. If it did, then $f(X)$ would be divisible by a linear polynomial $(X −\frac ab)$. Let $G(X) =\frac{f(X)}{X−\frac ab}$. Clear denominators (multiply throughout by $b$), and let $g(X) =bG(X)$. Then $\deg g =\deg f − 1$, and $g(x) = 0$. This contradicts the minimality of $f$ (we choose $f$ to be a polynomial of smallest degree such that $f(x) = 0$). Therefore, $f$ is non-zero at every rational. Let $M=\sup _{|z-x|< 1}\left|f'(z)\right|$. Let now $p/q$ be a rational such that $\left|x −\frac pq\right|< 1$. The Mean Value Theorem gives us that$$\left|f\left(\frac{p}{q}\right)-f(x)\right|=\left|f'(c)\left(x-\frac{p}{q}\right)\right| \leq M\left|x-\frac{p}{q}\right|\tag4\label4$$where $c$ is some real number between $x$ and $p/q$; $|c − x| < 1$ for $p/q$ moderately close to $x$.
Now we use the fact that $f(X)$ does not have any rational roots: $0 \neq f\left(\frac{p}{q}\right)=a_{n}\left(\frac{p}{q}\right)^{n}+\cdots+a_{0}=\frac{a_{n} p^{n}+\cdots a_{1} p^{n-1} q+a_{0} q^{n}}{q^{n}}$ The numerator of the last term is a nonzero integer, hence it has absolute value at least 1. Since we also know that $f(x) = 0$ it follows that$$\left|f\left(\frac{p}{q}\right)-f(x)\right|=\left|f\left(\frac{p}{q}\right)\right|=\frac{\left|a_{n} p^{n}+\cdots a_{1} p^{n-1} q+a_{0} q^{n}\right|}{q^{n}} \geq \frac{1}{q^{n}}\tag5\label5$$Combining the equations \eqref{4} and \eqref{5}, we get:$$\frac{1}{q^{n}} \leq M\left|x-\frac{p}{q}\right| \Rightarrow \frac{1}{M q^{n}} \leq\left|x-\frac{p}{q}\right|\label6\tag6$$whenever $\left|x−\frac pq\right| < 1$. This last equation shows us that $x$ can be approximated by rationals to order at most $n$. For assume it was otherwise, namely that $x$ can be approximated to order $n + \varepsilon$. Then we would have an infinite sequence of distinct rational numbers $\left\{p_i \over q_i\right\}_{i≥1}$ and a constant $k(x)$ depending only on $x$ such that $\left|x-\frac{p_{i}}{q_{i}}\right|< \frac{k(x)}{q_{i}^{n+\varepsilon}}$ Since the numbers $p_i \over q_i$ converge to $x$ we can assume that they already are in the interval $(x − 1, x + 1)$. Hence they also satisfy \eqref{6}:$\frac{1}{q_{i}^{n}} \leq M\left|x-\frac{p_{i}}{q_{i}}\right|$. Combining the last two equations we get $\frac{1}{M q_{i}^{n}} \leq\left|x-\frac{p_{i}}{q_{i}}\right|< \frac{k(x)}{q_{i}^{n+\varepsilon}}$ hence $q_{i}^{\varepsilon}< M$ and this is clearly impossible for arbitrarily large $q$ since $ε> 0$ and $q_i → ∞$.
Exercise 1.2.2. Justify the fact that if $\left\{\frac{p_{i}}{q_{i}}\right\} _{i \geq 1}$ is a rational approximation to order $n ≥ 1$ of $x$, then $q_i → ∞$.
Remark 1.2.3. So far we have seen that the order to which an algebraic number can be approximated by rationals is bounded by its degree. Hence if a real, irrational number $α \notin\mathbb Q$ can be approximated by rationals to an arbitrary large order, then $α$ must be transcendental! This provides us with a recipe for constructing transcendental numbers.
1.3 Constructing Transcendental Numbers
1.3.1 $\sum_{m} 10^{-m !}$
The following construction of transcendental numbers is due to Liouville.
Theorem 1.3.1. The number $x=\sum_{m=1}^{\infty} \frac{1}{10^{m !}}$ is transcendental.
Proof. The series defining $x$ is convergent, since it is dominated by the geometric series $\sum \frac{1}{10^{m}}$. In fact, the series converges very rapidly and it is this high rate of convergence that will yield $x$ is transcendental. Fix $N$ large, and let $n > N$. Write $\frac{p_{n}}{q_{n}}=\sum_{m=1}^{n} \frac{1}{10^{m !}}$ with $p_n, q_n > 0$ and $(p_n, q_n) = 1$. Then $\left\{\frac{p_{n}}{q_{n}}\right\} _{n\geq 1}$ is a monotone increasing sequence converging to $x$. In particular, all these rational numbers are distinct.
Not also that $q_n$ must divide $10^{n!}$, which implies $q_{n} \leq 10^{n !}$. Using this, we get $0< x-\frac{p_{n}}{q_{n}}=\sum_{m>n} \frac{1}{10^{m !}}=\frac{1}{10^{(n+1) !}}\left(1+\frac{1}{10^{n+2}}+\frac{1}{10^{(n+2)(n+3)}}+\cdots\right)$$< \frac{2}{10^{(n+1) !}}=\frac{2}{\left(10^{n !}\right)^{n+1}}$$< \frac{2}{q_{n}^{n+1}} \leq \frac{2}{q_{n}^{N}}$ This gives an approximation by rationals of order $N$ of $x$. Since $N$ can be chosen arbitrarily large, this implies that $x$ can be approximated by rationals to arbitrary order. We can conclude, in view of our precious remark 1.2.3 that $x$ is transcendental.
1.3.2 $\left[10^{1 !}, 10^{2 !}, \ldots\right]$
Theorem 1.3.2. The number $y=\left[10^{1 !}, 10^{2 !}, \ldots\right]$ is transcendental.
Proof. Let $\frac{p_{n}}{q_{n}}$ be the continued fraction of $\left[10^{1!} \cdots 10^{n!}\right]$. Then$$\label{7}\tag{7}\left|y-\frac{p_{n}}{q_{n}}\right|=\frac{1}{q_{n} q_{n+1}'}=\frac{1}{q_{n}\left(a_{n+1}'q_n+q_{n-1}\right)}< \frac1{a_{n+1}}=\frac1{10^{(n+1)!}}$$Since $q_k = a_nq_{k−1} + q_{n−2}$, it implies that $q_k > q_{k−1}$. Also, $q_{k+1} = a_{k+1}q_n +q_{k−1}$, so we get$$\frac{q_{k+1}}{q_{k}}=a_{k+1}+\frac{q_{k-1}}{q_{k}}< a_{k+1}+1$$Hence writing this inequality for $k = 1, · · · , n − 1$ we obtain$$\begin{aligned} q_{n}=q_{1} \frac{q_{2}}{q_{1}} \frac{q_{3}}{q_{2}} \cdots \frac{q_{n}}{q_{n-1}} &< \left(a_{1}+1\right)\left(a_{2}+1\right) \cdots\left(a_{n}+1\right) \\ &=\left(1+\frac{1}{a_{1}}\right) \cdots\left(1+\frac{1}{a_{n}}\right) a_{1} \cdots a_{n} \\ &< 2^{n} a_{1} \cdots a_{n}=2^{n} 10^{1 !+\cdots+n !} \\ &< 10^{2 n !}=a_{n}^{2}\end{aligned}\tag8\label8$$Combining equations \eqref{7} and \eqref{8} we get:\begin{aligned}\left|y-\frac{p_{n}}{q_{n}}\right| &< \frac{1}{a_{n+1}}=\frac{1}{a_{n}^{n+1}} \\ &< \left(\frac{1}{a_{n}^{2}}\right)^{\frac{n}{2}}< \left(\frac{1}{q_{n}^{2}}\right)^{\frac{n}{2}} \\ &=\frac{1}{q_{n}^{n / 2}} \end{aligned}In this way we get, just as in the previous theorem, an approximation of $y$ by rationals to arbitrary order. This proves that $y$ is transcendental.
Rational approximation — aops wiki
proofwiki
The Beginning of Transcendental Numbers
1.1 Review of Approximating by Rationals
Definition 1.1.1 (Approximated by rationals to order $n$) A real number $x$ is approximated by rationals to order $n$ if there exist a constant $k(x)$ (possibly depending on $x$) such that there are infinitely many rational $\frac pq$ with$$\left|x-\frac{p}{q}\right|< \frac{k(x)}{q^{n}}\tag1\label1$$Recall that Dirichlet’s Box Principle gives us:$$\left|x-\frac{p}{q}\right|< \frac{1}{q^{2}}\tag2\label2$$for infinitely many fractions $\frac pq$. This was proved by choosing a large parameter $Q$, and considering the $Q+1$ fractionary parts $\{qx\} ∈ [0, 1)$ for $q ∈ \{0,…, Q\}$. The box principle ensures us that there must be two different $q$’s, say: $0 \leq q_{1}< q_2\le Q$ such that both $\{q_1x\}$ and $\{q_2x\}$ belong to the same interval $\left[\frac{a}{Q}, \frac{a+1}{Q}\right)$, for some $0 ≤ a ≤ Q − 1$. Note that there are exactly $Q$ such intervals partitioning $[0, 1)$, and $Q + 1$ fractionary parts! Now, the length of such an interval is $\frac1Q$ so we get $\left|\left\{q_2x\right\}-\left\{q_1x\right\}\right|< \frac1Q$. There exist integers $p_1$ and $p_2$ such that $\left\{q_1x\right\}=q_1x-p_1,\left\{q_2x\right\}=q_2x-p_2$. Letting $p=p_{2}-p_{1}$ we find $\left|\left(q_{2}-q_{1}\right) x-p\right| \leq \frac{1}{Q}$. Let $q = q_2 − q_1$, so $1 ≤ q ≤ Q$, and the previous equation can be rewritten as$$\left|x-\frac{p}{q}\right|< \frac{1}{q Q} \leq \frac{1}{q^{2}}\label3\tag3$$Now, letting $Q → ∞$, we get an infinite collection of rational fractions $p/q$ satisfying the above equation. If this collection contains only finitely many distinct fractions, then one of these fractions, say $p_0/q_0$, would occur for infinitely many choices $Q_k$ of $Q$, thus giving us: $\left|x-\frac{p_{0}}{q_{0}}\right|< \frac{1}{q Q_{k}} \rightarrow 0$ as $k → ∞$. This implies that $x =p_0/q_0∈\mathbb Q$. So, unless $x$ is a rational number, we can find infinitely many distinct rational numbers $p/q$ satisfying \eqref{3}. This means that any real, irrational number can be approximated to order $n = 2$ by rational numbers.
1.2 Liouville’s Theorem
Theorem 1.2.1 (Liouville’s Theorem). Let $x$ be a real algebraic number of degree $n$. Then $x$ is approximated by rationals to order at most $n$.
Proof. Let $f(X)=a_{n} X^{n}+\cdots a_{1} X+a_{0}$ be the polynomial with integer coefficients of smallest degree (minimal polynomial) such that $x$ satisfies $f(x)=0$. Note that $\deg x = \deg f$ and the condition of minimality implies that $f(X)$ is irreducible over $\mathbb Z$. Further, a well known result from algebra states that a polynomial irreducible over $\mathbb Z$ is also irreducible over $\mathbb Q$. In particular, as $f(X)$ is irreducible over $\mathbb Q$, $f(X)$ does not have any rational roots. If it did, then $f(X)$ would be divisible by a linear polynomial $(X −\frac ab)$. Let $G(X) =\frac{f(X)}{X−\frac ab}$. Clear denominators (multiply throughout by $b$), and let $g(X) =bG(X)$. Then $\deg g =\deg f − 1$, and $g(x) = 0$. This contradicts the minimality of $f$ (we choose $f$ to be a polynomial of smallest degree such that $f(x) = 0$). Therefore, $f$ is non-zero at every rational. Let $M=\sup _{|z-x|< 1}\left|f'(z)\right|$. Let now $p/q$ be a rational such that $\left|x −\frac pq\right|< 1$. The Mean Value Theorem gives us that$$\left|f\left(\frac{p}{q}\right)-f(x)\right|=\left|f'(c)\left(x-\frac{p}{q}\right)\right| \leq M\left|x-\frac{p}{q}\right|\tag4\label4$$where $c$ is some real number between $x$ and $p/q$; $|c − x| < 1$ for $p/q$ moderately close to $x$.
Now we use the fact that $f(X)$ does not have any rational roots: $0 \neq f\left(\frac{p}{q}\right)=a_{n}\left(\frac{p}{q}\right)^{n}+\cdots+a_{0}=\frac{a_{n} p^{n}+\cdots a_{1} p^{n-1} q+a_{0} q^{n}}{q^{n}}$ The numerator of the last term is a nonzero integer, hence it has absolute value at least 1. Since we also know that $f(x) = 0$ it follows that$$\left|f\left(\frac{p}{q}\right)-f(x)\right|=\left|f\left(\frac{p}{q}\right)\right|=\frac{\left|a_{n} p^{n}+\cdots a_{1} p^{n-1} q+a_{0} q^{n}\right|}{q^{n}} \geq \frac{1}{q^{n}}\tag5\label5$$Combining the equations \eqref{4} and \eqref{5}, we get:$$\frac{1}{q^{n}} \leq M\left|x-\frac{p}{q}\right| \Rightarrow \frac{1}{M q^{n}} \leq\left|x-\frac{p}{q}\right|\label6\tag6$$whenever $\left|x−\frac pq\right| < 1$. This last equation shows us that $x$ can be approximated by rationals to order at most $n$. For assume it was otherwise, namely that $x$ can be approximated to order $n + \varepsilon$. Then we would have an infinite sequence of distinct rational numbers $\left\{p_i \over q_i\right\}_{i≥1}$ and a constant $k(x)$ depending only on $x$ such that $\left|x-\frac{p_{i}}{q_{i}}\right|< \frac{k(x)}{q_{i}^{n+\varepsilon}}$ Since the numbers $p_i \over q_i$ converge to $x$ we can assume that they already are in the interval $(x − 1, x + 1)$. Hence they also satisfy \eqref{6}:$\frac{1}{q_{i}^{n}} \leq M\left|x-\frac{p_{i}}{q_{i}}\right|$. Combining the last two equations we get $\frac{1}{M q_{i}^{n}} \leq\left|x-\frac{p_{i}}{q_{i}}\right|< \frac{k(x)}{q_{i}^{n+\varepsilon}}$ hence $q_{i}^{\varepsilon}< M$ and this is clearly impossible for arbitrarily large $q$ since $ε> 0$ and $q_i → ∞$.
Exercise 1.2.2. Justify the fact that if $\left\{\frac{p_{i}}{q_{i}}\right\} _{i \geq 1}$ is a rational approximation to order $n ≥ 1$ of $x$, then $q_i → ∞$.
Remark 1.2.3. So far we have seen that the order to which an algebraic number can be approximated by rationals is bounded by its degree. Hence if a real, irrational number $α \notin\mathbb Q$ can be approximated by rationals to an arbitrary large order, then $α$ must be transcendental! This provides us with a recipe for constructing transcendental numbers.
1.3 Constructing Transcendental Numbers
1.3.1 $\sum_{m} 10^{-m !}$
The following construction of transcendental numbers is due to Liouville.
Theorem 1.3.1. The number $x=\sum_{m=1}^{\infty} \frac{1}{10^{m !}}$ is transcendental.
Proof. The series defining $x$ is convergent, since it is dominated by the geometric series $\sum \frac{1}{10^{m}}$. In fact, the series converges very rapidly and it is this high rate of convergence that will yield $x$ is transcendental. Fix $N$ large, and let $n > N$. Write $\frac{p_{n}}{q_{n}}=\sum_{m=1}^{n} \frac{1}{10^{m !}}$ with $p_n, q_n > 0$ and $(p_n, q_n) = 1$. Then $\left\{\frac{p_{n}}{q_{n}}\right\} _{n\geq 1}$ is a monotone increasing sequence converging to $x$. In particular, all these rational numbers are distinct.
Not also that $q_n$ must divide $10^{n!}$, which implies $q_{n} \leq 10^{n !}$. Using this, we get $0< x-\frac{p_{n}}{q_{n}}=\sum_{m>n} \frac{1}{10^{m !}}=\frac{1}{10^{(n+1) !}}\left(1+\frac{1}{10^{n+2}}+\frac{1}{10^{(n+2)(n+3)}}+\cdots\right)$$< \frac{2}{10^{(n+1) !}}=\frac{2}{\left(10^{n !}\right)^{n+1}}$$< \frac{2}{q_{n}^{n+1}} \leq \frac{2}{q_{n}^{N}}$ This gives an approximation by rationals of order $N$ of $x$. Since $N$ can be chosen arbitrarily large, this implies that $x$ can be approximated by rationals to arbitrary order. We can conclude, in view of our precious remark 1.2.3 that $x$ is transcendental.
1.3.2 $\left[10^{1 !}, 10^{2 !}, \ldots\right]$
Theorem 1.3.2. The number $y=\left[10^{1 !}, 10^{2 !}, \ldots\right]$ is transcendental.
Proof. Let $\frac{p_{n}}{q_{n}}$ be the continued fraction of $\left[10^{1!} \cdots 10^{n!}\right]$. Then$$\label{7}\tag{7}\left|y-\frac{p_{n}}{q_{n}}\right|=\frac{1}{q_{n} q_{n+1}'}=\frac{1}{q_{n}\left(a_{n+1}'q_n+q_{n-1}\right)}< \frac1{a_{n+1}}=\frac1{10^{(n+1)!}}$$Since $q_k = a_nq_{k−1} + q_{n−2}$, it implies that $q_k > q_{k−1}$. Also, $q_{k+1} = a_{k+1}q_n +q_{k−1}$, so we get$$\frac{q_{k+1}}{q_{k}}=a_{k+1}+\frac{q_{k-1}}{q_{k}}< a_{k+1}+1$$Hence writing this inequality for $k = 1, · · · , n − 1$ we obtain$$\begin{aligned} q_{n}=q_{1} \frac{q_{2}}{q_{1}} \frac{q_{3}}{q_{2}} \cdots \frac{q_{n}}{q_{n-1}} &< \left(a_{1}+1\right)\left(a_{2}+1\right) \cdots\left(a_{n}+1\right) \\ &=\left(1+\frac{1}{a_{1}}\right) \cdots\left(1+\frac{1}{a_{n}}\right) a_{1} \cdots a_{n} \\ &< 2^{n} a_{1} \cdots a_{n}=2^{n} 10^{1 !+\cdots+n !} \\ &< 10^{2 n !}=a_{n}^{2}\end{aligned}\tag8\label8$$Combining equations \eqref{7} and \eqref{8} we get:\begin{aligned}\left|y-\frac{p_{n}}{q_{n}}\right| &< \frac{1}{a_{n+1}}=\frac{1}{a_{n}^{n+1}} \\ &< \left(\frac{1}{a_{n}^{2}}\right)^{\frac{n}{2}}< \left(\frac{1}{q_{n}^{2}}\right)^{\frac{n}{2}} \\ &=\frac{1}{q_{n}^{n / 2}} \end{aligned}In this way we get, just as in the previous theorem, an approximation of $y$ by rationals to arbitrary order. This proves that $y$ is transcendental.