Diophantine approximation

A badly approximable number is an x for which there is a positive constant c such that for all rational p/q we have

${\displaystyle \left|{x-{\frac {p}{q}}}\right|>{\frac {c}{q^{2}}}\ .}$

The badly approximable numbers are precisely those with bounded partial quotients.[6]

Equivalently, a number is badly approximable if and only if its Markov constant is bounded.

A rational number ${\textstyle \alpha ={\frac {a}{b}}}$ may be obviously and perfectly approximated by ${\textstyle {\frac {p_{i}}{q_{i}}}={\frac {i\,a}{i\,b}}}$ for every positive integer i.

If ${\textstyle {\frac {p}{q}}\not =\alpha ={\frac {a}{b}}\,,}$ we have

${\displaystyle \left|{\frac {a}{b}}-{\frac {p}{q}}\right|=\left|{\frac {aq-bp}{bq}}\right|\geq {\frac {1}{bq}},}$

because ${\displaystyle |aq-bp|}$ is a positive integer and is thus not lower than 1. Thus the accuracy of the approximation is bad relative to irrational numbers (see next sections).

It may be remarked that the preceding proof uses a variant of the pigeonhole principle: a non-negative integer that is not 0 is not smaller than 1. This apparently trivial remark is used in almost every proof of lower bounds for Diophantine approximations, even the most sophisticated ones.

In summary, a rational number is perfectly approximated by itself, but is badly approximated by any other rational number.

In the 1840s, Joseph Liouville obtained the first lower bound for the approximation of algebraic numbers: If x is an irrational algebraic number of degree n over the rational numbers, then there exists a constant c(x) > 0 such that

${\displaystyle \left|x-{\frac {p}{q}}\right|>{\frac {c(x)}{q^{n}}}}$

holds for all integers p and q where q > 0.

This result allowed him to produce the first proven example of a transcendental number, the Liouville constant

${\displaystyle \sum _{j=1}^{\infty }10^{-j!}=0.110001000000000000000001000\ldots \,,}$

which does not satisfy Liouville's theorem, whichever degree n is chosen.

This link between Diophantine approximations and transcendental number theory continues to the present day. Many of the proof techniques are shared between the two areas.

Over more than a century, there were many efforts to improve Liouville's theorem: every improvement of the bound enables us to prove that more numbers are transcendental. The main improvements are due to Axel Thue (1909), Siegel (1921), Freeman Dyson (1947), and Klaus Roth (1955), leading finally to the Thue–Siegel–Roth theorem: If x is an irrational algebraic number and ε a (small) positive real number, then there exists a positive constant c(x, ε) such that

${\displaystyle \left|x-{\frac {p}{q}}\right|>{\frac {c(x,\varepsilon )}{q^{2+\varepsilon }}}}$

holds for every integer p and q such that q > 0.

In some sense, this result is optimal, as the theorem would be false with ε = 0. This is an immediate consequence of the upper bounds described below.

Subsequently, Wolfgang M. Schmidt generalized this to the case of simultaneous approximations, proving that: If x₁, ..., x_n are algebraic numbers such that 1, x₁, ..., x_n are linearly independent over the rational numbers and ε is any given positive real number, then there are only finitely many rational n-tuples (p₁/q, ..., p_n/q) such that

${\displaystyle \left|x_{i}-{\frac {p_{i}}{q}}\right|<q^{-(1+1/n+\varepsilon )},\quad i=1,\ldots ,n.}$

Again, this result is optimal in the sense that one may not remove ε from the exponent.

All preceding lower bounds are not effective, in the sense that the proofs do not provide any way to compute the constant implied in the statements. This means that one cannot use the results or their proofs to obtain bounds on the size of solutions of related Diophantine equations. However, these techniques and results can often be used to bound the number of solutions of such equations.

Nevertheless, a refinement of Baker's theorem by Feldman provides an effective bound: if x is an algebraic number of degree n over the rational numbers, then there exist effectively computable constants c(x) > 0 and 0 < d(x) < n such that

${\displaystyle \left|x-{\frac {p}{q}}\right|>{\frac {c(x)}{|q|^{d(x)}}}}$

holds for all rational integers.

However, as for every effective version of Baker's theorem, the constants d and 1/c are so large that this effective result cannot be used in practice.

The first important result about upper bounds for Diophantine approximations is Dirichlet's approximation theorem, which implies that, for every irrational number α, there are infinitely many fractions ${\displaystyle {\tfrac {p}{q}}\;}$ such that

${\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{q^{2}}}\,.}$

This implies immediately that one cannot suppress the ε in the statement of Thue-Siegel-Roth theorem.

Adolf Hurwitz (1891)[7] strengthened this result, proving that for every irrational number α, there are infinitely many fractions ${\displaystyle {\tfrac {p}{q}}\;}$ such that

${\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{{\sqrt {5}}q^{2}}}\,.}$

Therefore, ${\displaystyle {\frac {1}{{\sqrt {5}}\,q^{2}}}}$ is an upper bound for the Diophantine approximations of any irrational number. The constant in this result may not be further improved without excluding some irrational numbers (see below).

Émile Borel (1903)[8] showed that, in fact, given any irrational number α, and given three consecutive convergents of α, at least one must satisfy the inequality given in Hurwitz's Theorem.

Definition: Two real numbers ${\displaystyle x,y}$ are called equivalent[9][10] if there are integers ${\displaystyle a,b,c,d\;}$ with ${\displaystyle ad-bc=\pm 1\;}$ such that:

${\displaystyle y={\frac {ax+b}{cx+d}}\,.}$

So equivalence is defined by an integer Möbius transformation on the real numbers, or by a member of the Modular group ${\displaystyle {\text{SL}}_{2}^{\pm }(\mathbb {Z} )}$, the set of invertible 2 × 2 matrices over the integers. Each rational number is equivalent to 0; thus the rational numbers are an equivalence class for this relation.

The equivalence may be read on the regular continued fraction representation, as shown by the following theorem of Serret:

Theorem: Two irrational numbers x and y are equivalent if and only if there exist two positive integers h and k such that the regular continued fraction representations of x and y

${\displaystyle {\begin{aligned}x&=[u_{0};u_{1},u_{2},\ldots ]\,,\\y&=[v_{0};v_{1},v_{2},\ldots ]\,,\end{aligned}}}$

satisfy

${\displaystyle u_{h+i}=v_{k+i}}$

for every non negative integer i.[11]

Thus, except for a finite initial sequence, equivalent numbers have the same continued fraction representation.

Equivalent numbers are approximable to the same degree, in the sense that they have the same Markov constant.

As said above, the constant in Borel's theorem may not be improved, as shown by Adolf Hurwitz in 1891.[12] Let ${\displaystyle \phi ={\tfrac {1+{\sqrt {5}}}{2}}}$ be the golden ratio. Then for any real constant c with ${\displaystyle c>{\sqrt {5}}\;}$ there are only a finite number of rational numbers p/q such that

${\displaystyle \left|\phi -{\frac {p}{q}}\right|<{\frac {1}{c\,q^{2}}}.}$

Hence an improvement can only be achieved, if the numbers which are equivalent to ${\displaystyle \phi }$ are excluded. More precisely:[13][14] For every irrational number ${\displaystyle \alpha }$, which is not equivalent to ${\displaystyle \phi }$, there are infinite many fractions ${\displaystyle {\tfrac {p}{q}}\;}$ such that

${\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{{\sqrt {8}}q^{2}}}.}$

By successive exclusions — next one must exclude the numbers equivalent to ${\displaystyle {\sqrt {2}}}$ — of more and more classes of equivalence, the lower bound can be further enlarged. The values which may be generated in this way are Lagrange numbers, which are part of the Lagrange spectrum. They converge to the number 3 and are related to the Markov numbers.[15][16]

An important example of a function ${\displaystyle \psi }$ to which Khinchin's theorem can be applied is the function ${\displaystyle \psi _{c}(q)=q^{-c}}$, where c > 1 is a real number. For this function, the relevant series converges and so Khinchin's theorem tells us that almost every point is not ${\displaystyle \psi _{c}}$-approximable. Thus, the set of numbers which are ${\displaystyle \psi _{c}}$-approximable forms a subset of the real line of Lebesgue measure zero. The Jarník-Besicovitch theorem, due to V. Jarník and A. S. Besicovitch, states that the Hausdorff dimension of this set is equal to ${\displaystyle 1/c}$.[19] In particular, the set of numbers which are ${\displaystyle \psi _{c}}$-approximable for some ${\displaystyle c>1}$ (known as the set of very well approximable numbers) has Hausdorff dimension one, while the set of numbers which are ${\displaystyle \psi _{c}}$-approximable for all ${\displaystyle c>1}$ (known as the set of Liouville numbers) has Hausdorff dimension zero.

Another important example is the function ${\displaystyle \psi _{\varepsilon }(q)=\varepsilon q^{-1}}$, where ${\displaystyle \varepsilon >0}$ is a real number. For this function, the relevant series diverges and so Khinchin's theorem tells us that almost every number is ${\displaystyle \psi _{\varepsilon }}$-approximable. This is the same as saying that every such number is well approximable, where a number is called well approximable if it is not badly approximable. So an appropriate analogue of the Jarník-Besicovitch theorem should concern the Hausdorff dimension of the set of badly approximable numbers. And indeed, V. Jarník proved that the Hausdorff dimension of this set is equal to one. This result was improved by W. M. Schmidt, who showed that the set of badly approximable numbers is incompressible, meaning that if ${\displaystyle f_{1},f_{2},\ldots }$ is a sequence of bi-Lipschitz maps, then the set of numbers x for which ${\displaystyle f_{1}(x),f_{2}(x),\ldots }$ are all badly approximable has Hausdorff dimension one. Schmidt also generalized Jarník's theorem to higher dimensions, a significant achievement because Jarník's argument is essentially one-dimensional, depending on the apparatus of continued fractions.