Content deleted Content added
→top: Add {{Diophantine_approximation_graph.svg}} |
redir |
||
| (47 intermediate revisions by 29 users not shown) | |||
Line 1:
{{Short description|Rational-number approximation of a real number}}
{{more citations needed|date=May 2023}}
{{Use American English|date = March 2019}}
{{Diophantine_approximation_graph.svg}}
In [[number theory]], the study of '''Diophantine approximation''' deals with the approximation of [[real number]]s by [[rational number]]s. It is named after [[Diophantus of Alexandria]].
The first problem was to know how well a real number can be approximated by rational numbers. For this problem, a rational number ''
Knowing the "best" approximations of a given number, the main problem of the field is to find sharp [[upper and lower bounds]] of the above difference, expressed as a function of the [[denominator]]. It appears that these bounds depend on the nature of the real numbers to be approximated: the lower bound for the approximation of a rational number by another rational number is larger than the lower bound for [[algebraic number]]s, which is itself larger than the lower bound for all real numbers. Thus a real number that may be better approximated than the bound for algebraic numbers is certainly a [[transcendental number]].
Line 11 ⟶ 12:
Diophantine approximations and [[transcendental number theory]] are very close areas that share many theorems and methods. Diophantine approximations also have important applications in the study of [[Diophantine equation]]s.
The 2022 [[Fields Medal]] was awarded to [[James Maynard (mathematician)|James Maynard]], in part for his work on Diophantine approximation.
== Best Diophantine approximations of a real number ==
{{main|
Given a real number {{math|''α''}}, there are two ways to define a best Diophantine approximation of {{math|''α''}}. For the first definition,<ref name="Khinchin 1997 p.21">{{harvnb|Khinchin|1997|p=21}}</ref> the rational number {{math|''p''/''q''}} is a ''best Diophantine approximation'' of {{math|''α''}} if
Line 22 ⟶ 25:
:<math>\left|q\alpha -p\right| < \left|q^\prime\alpha - p^\prime\right|.</math>
A best approximation for the second definition is also a best approximation for the first one, but the converse is
The theory of [[Simple continued fraction|continued fraction]]s allows us to compute the best approximations of a real number: for the second definition, they are the [[
For example, the constant ''e'' = 2.718281828459045235... has the (regular) continued fraction representation
Line 38 ⟶ 41:
==Measure of the accuracy of approximations ==
The obvious measure of the accuracy of a Diophantine approximation of a real number {{math|''α''}} by a rational number {{math|''p''/''q''}} is <math display="inline">\left|\alpha - \frac{p}{q}\right|.</math> However, this quantity can always be made arbitrarily small by increasing the absolute values of {{math|''p''}} and {{math|''q''}}; thus the accuracy of the approximation is usually estimated by comparing this quantity to some function {{math|''φ''}} of the denominator {{math|''q''}}, typically a negative power of it.
For such a comparison, one may want upper bounds or lower bounds of the accuracy. A lower bound is typically described by a theorem like "for every element {{math|''α''}} of some subset of the real numbers and every rational number {{math|''p''/''q''}}, we have <math display="inline">\left|\alpha - \frac{p}{q}\right|>\phi(q)</math> ". In some cases, "every rational number" may be replaced by "all rational numbers except a finite number of them", which amounts to multiplying {{math|''φ''}} by some constant depending on {{math|''α''}}.
For upper bounds, one has to take into account that not all the "best" Diophantine approximations provided by the convergents may have the desired accuracy. Therefore, the theorems take the form "for every element {{math|''α''}} of some subset of the real numbers, there are infinitely many rational numbers {{math|''p''/''q''}} such that <math display="inline">\left|\alpha - \frac{p}{q}\right|<\phi(q)</math> ".
===Badly approximable numbers===
Line 51 ⟶ 54:
The badly approximable numbers are precisely those with [[Restricted partial quotients|bounded partial quotients]].<ref name=Bug245>{{harvnb|Bugeaud|2012|p=245}}</ref>
Equivalently, a number is badly approximable [[if and only if]] its [[Markov constant]] is finite or equivalently its simple continued fraction is bounded.
== Lower bounds for Diophantine approximations ==
{{unsourced section|date=May 2023}}
=== Approximation of a rational by other rationals ===
A rational number <math display="inline">\alpha =\frac{a}{b}</math> may be obviously and perfectly approximated by <math display="inline">\
If <math display="inline">\
:<math>
because <math>|aq - bp|</math> 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 [[
In summary, a rational number is perfectly approximated by itself, but is badly approximated by any other rational number.
Line 71 ⟶ 74:
In the 1840s, [[Joseph Liouville]] obtained the first lower bound for the approximation of [[algebraic number]]s: If ''x'' is an irrational algebraic number of degree ''n'' over the rational numbers, then there exists a constant {{nowrap|''c''(''x'') > 0}} such that
:<math> \left| x- \frac{p}{q} \right| > \frac{c(x)}{q^
holds for all integers ''p'' and ''q'' where {{nowrap|''q'' > 0}}.
Line 86 ⟶ 89:
{{main|Thue–Siegel–Roth theorem}}
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 {{harvs|first=Axel|last=Thue|authorlink=Axel Thue|year=1909|txt}}, {{harvs|frst=Carl Ludwig|last=Siegel|authorlink=Carl Ludwig Siegel|year=1921|txt}}, {{harvs|first=Freeman|last=Dyson|authorlink=Freeman Dyson|year=1947|txt}}, and {{harvs|first=Klaus|last=Roth|authorlink=Klaus Roth|year=1955|txt}}, leading finally to the Thue–Siegel–Roth theorem: If {{math|''x''}} is an irrational algebraic number and {{math|''ε > 0''}}
:<math>
\left| x- \frac{p}{q} \right|>\frac{c(x, \varepsilon)}{q^{2+\varepsilon}}
Line 92 ⟶ 95:
holds for every integer {{math|''p''}} and {{math|''q''}} such that {{math|''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.
=== Simultaneous approximations of algebraic numbers ===
{{main|Subspace theorem}}
Subsequently, [[Wolfgang M. Schmidt]] generalized this to the case of simultaneous approximations, proving that: If {{math|''x''<sub>1</sub>, ..., ''x''<sub>''n''</sub>}} are algebraic numbers such that {{math|1, ''x''<sub>1</sub>, ..., ''x''<sub>''n''</sub>}} are [[linear independence|linearly independent]] over the rational numbers and {{math|''ε''}} is any given positive real number, then there are only finitely many rational {{math|''n''}}-tuples {{math|(''p''<sub>1</sub>/''q'', ..., ''p''<sub>''n''</sub>/''q'')}} such that
:<math>\left|x_i - \frac{p_i
Again, this result is optimal in the sense that one may not remove {{math|''ε''}} from the exponent.
Line 122 ⟶ 125:
This implies immediately that one cannot suppress the {{math|''ε''}} in the statement of Thue-Siegel-Roth theorem.
: <math>\left|\alpha-\frac{p}{q}\right| < \frac{1}{\sqrt{5}q^2}\,.</math>
Therefore, <math>\frac{1}{\sqrt{5}\, q^2}</math> 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)<ref>{{harvnb|Perron|1913|loc=Chapter 2, Theorem 15}}</ref> showed that, in fact, given any irrational number {{math|''α''}}, and given three consecutive convergents of {{math|''α''}}, at least one must satisfy the inequality given in Hurwitz's Theorem.
=== Equivalent real numbers ===
Line 135 ⟶ 140:
So equivalence is defined by an integer [[Möbius transformation]] on the real numbers, or by a member of the [[Modular group]] <math>\text{SL}_2^{\pm}(\Z)</math>, 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 [[Joseph Alfred Serret|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 [[Simple continued fraction|continued fraction]] representations of ''x'' and ''y''▼
:<math>\begin{align}
y &= [v_0; v_1, v_2, \ldots]\, ,
\end{align}</math>
satisfy
▲'''Theorem''': Two irrational numbers ''x'' and ''y'' are equivalent if and only there exist two positive integers ''h'' and ''k'' such that the regular [[continued fraction]] representations of ''x'' and ''y''
:<math>
▲:<math>y=[v_0; v_1, v_2, \ldots]\, ,</math>
for every non negative integer ''i''.<ref>See {{harvnb|Perron|1929|loc=Chapter 2, Theorem 23, p. 63}}</ref>
Line 150 ⟶ 158:
===Lagrange spectrum ===
{{main|Markov spectrum}}
As said above, the constant in Borel's theorem may not be improved, as shown by [[Adolf Hurwitz]] in 1891.<ref>{{harvnb|Hardy|Wright|1979|p=164}}</ref>
Let <math>\phi = \tfrac{1+\sqrt{5}}{2}</math> be the [[golden ratio]].
Then for any real constant ''c'' with <math>c > \sqrt{5}\;</math> there are only a finite number of rational numbers {{math|''p''/''q''}} such that
Line 162 ⟶ 170:
By successive exclusions — next one must exclude the numbers equivalent to <math>\sqrt 2</math> — 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 [[Markov spectrum|Lagrange spectrum]].
They converge to the number 3 and are related to the [[Markov number]]s.<ref>{{harvnb|Cassels|1957|p=18}}</ref><ref>See [http://www.math.jussieu.fr/~miw/articles/pdf/IntroductionDiophantineMethods.pdf Michel Waldschmidt: ''Introduction to Diophantine methods irrationality and transcendence''] {{Webarchive|url=https://web.archive.org/web/20120209111526/http://www.math.jussieu.fr/~miw/articles/pdf/IntroductionDiophantineMethods.pdf |date=2012-02-09 }}, pp 24–26.</ref>
== Khinchin's theorem on metric Diophantine approximation and extensions == <!-- [[Khinchin's theorem on Diophantine approximations]] links here -->
Line 170 ⟶ 178:
:<math>\left| x- \frac{p}{q} \right| < \frac{\psi(q)}{|q|}.</math>
[[Aleksandr Khinchin]] proved in 1926 that if the series <math display="inline">\sum_{q} \psi(q) </math> diverges, then almost every real number (in the sense of [[Lebesgue measure]]) is <math>\psi</math>-approximable, and if the series converges, then almost every real number is not <math>\psi</math>-approximable. The circle of ideas surrounding this theorem and its relatives is known as ''metric Diophantine approximation'' or the ''metric theory of Diophantine approximation'' (not to be confused with height "metrics" in [[Diophantine geometry]]) or ''metric number theory''.
{{harvtxt|Duffin|Schaeffer|1941}} proved a generalization of Khinchin's result, and posed what is now known as the [[Duffin–Schaeffer conjecture]] on the analogue of Khinchin's dichotomy for general, not necessarily decreasing, sequences <math>\psi</math> . {{harvtxt|Beresnevich|Velani|2006}} proved that a [[Hausdorff measure]] analogue of the Duffin–Schaeffer conjecture is equivalent to the original Duffin–Schaeffer conjecture, which is a priori weaker.
In July 2019, [[Dimitris Koukoulopoulos]] and [[James Maynard (mathematician)|James Maynard]] announced a proof of the conjecture.<ref>{{cite
=== Hausdorff dimension of exceptional sets ===
Line 179 ⟶ 187:
An important example of a function <math>\psi</math> to which Khinchin's theorem can be applied is the function <math>\psi_c(q) = q^{-c}</math>, 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 <math>\psi_c</math>-approximable. Thus, the set of numbers which are <math>\psi_c</math>-approximable forms a subset of the real line of Lebesgue measure zero. The Jarník-Besicovitch theorem, due to [[Vojtech Jarnik|V. Jarník]] and [[Abram Samoilovitch Besicovitch|A. S. Besicovitch]], states that the [[Hausdorff dimension]] of this set is equal to <math>1/c</math>.<ref>{{harvnb|Bernik|Beresnevich|Götze|Kukso|2013|p=24}}</ref> In particular, the set of numbers which are <math>\psi_c</math>-approximable for some <math>c > 1</math> (known as the set of ''very well approximable numbers'') has Hausdorff dimension one, while the set of numbers which are <math>\psi_c</math>-approximable for all <math>c > 1</math> (known as the set of [[Liouville number]]s) has Hausdorff dimension zero.
Another important example is the function <math>\psi_\
== Uniform distribution ==
{{unsourced section|date=May 2023}}
Another topic that has seen a thorough development is the theory of [[equidistributed sequence|uniform distribution mod 1]]. Take a sequence ''a''<sub>1</sub>, ''a''<sub>2</sub>, ... of real numbers and consider their ''fractional parts''. That is, more abstractly, look at the sequence in
Related to uniform distribution is the topic of [[irregularities of distribution]], which is of a [[combinatorics|combinatorial]] nature.
== Algorithms ==
Grotschel, Lovasz and Schrijver describe algorithms for finding approximately-best diophantine approximations, both for individual real numbers and for set of real numbers. The latter problem is called '''simultaneous diophantine approximation'''.<ref name=":0">{{Cite Geometric Algorithms and Combinatorial Optimization}}</ref>{{Rp|page=|___location=Sec. 5.2}}
== Unsolved problems ==
{{unsourced section|date=May 2023}}
There are still simply
It is also unknown if there are algebraic numbers with unbounded coefficients in their continued fraction expansion.
== Recent developments ==
{{unsourced section|date=May 2023}}
In his plenary address at the [[International Mathematical Congress]] in Kyoto (1990), [[Grigory Margulis]] outlined a broad program rooted in [[ergodic theory]] that allows one to prove number-theoretic results using the dynamical and ergodic properties of actions of subgroups of [[semisimple Lie group]]s. The work of D. Kleinbock, G. Margulis and their collaborators demonstrated the power of this novel approach to classical problems in Diophantine approximation. Among its notable successes are the proof of the decades-old [[Oppenheim conjecture]] by Margulis, with later extensions by Dani and Margulis and Eskin–Margulis–Mozes, and the proof of Baker and Sprindzhuk conjectures in the Diophantine approximations on manifolds by Kleinbock and Margulis. Various generalizations of the above results of [[Aleksandr Khinchin]] in metric Diophantine approximation have also been obtained within this framework.
Line 196 ⟶ 210:
* [[Davenport–Schmidt theorem]]
* [[Duffin–Schaeffer
* [[Heilbronn set]]
* [[Low-discrepancy sequence]]
Line 205 ⟶ 219:
==References==
{{refbegin|30em}}
*{{cite journal |zbl=1148.11033 |last1=Beresnevich |first1=Victor |last2=Velani |first2=Sanju |title=A mass transference principle and the Duffin-Schaeffer conjecture for Hausdorff measures |journal=[[Annals of Mathematics]] |volume=164 |issue=3 |year=2006 |pages=971–992 |doi=10.4007/annals.2006.164.971|arxiv=math/0412141 |s2cid=14475449 }}
*{{cite book
| last1 = Bernik | first1 = V.
Line 227 ⟶ 241:
| volume = 42
| year = 2013
| isbn = 978-3-642-36067-1
| s2cid = 55652124
}}
* {{cite book |last=Bugeaud |first=Yann |title=Distribution modulo one and Diophantine approximation |series=Cambridge Tracts in Mathematics |volume=193 |___location=Cambridge |publisher=[[Cambridge University Press]] |year=2012 |isbn=978-0-521-11169-0 |zbl=1260.11001}}
Line 232 ⟶ 248:
*{{cite journal |zbl=0025.11002 |last1=Duffin |first1=R. J. |last2=Schaeffer |first2=A. C. |title=Khintchine's problem in metric diophantine approximation |journal=[[Duke Mathematical Journal]] |volume=8 |issue=2 |pages=243–255 |year=1941 |issn=0012-7094 |doi=10.1215/s0012-7094-41-00818-9}}
*{{cite journal | last1=Dyson | first1=Freeman J. | author1-link=Freeman Dyson | title=The approximation to algebraic numbers by rationals | doi= 10.1007/BF02404697 | mr=0023854 | zbl=0030.02101 | year=1947 | journal=[[Acta Mathematica]] | issn=0001-5962 | volume=79 | pages=225–240 | doi-access=free }}
*{{cite book |
*{{cite journal |first=A. |last=Hurwitz |author-link=Adolf Hurwitz |title=Ueber die angenäherte Darstellung der Irrationalzahlen durch rationale Brüche |trans-title=On the approximate representation of irrational numbers by rational fractions |language=de |journal=Mathematische Annalen |volume=39 |year=1891 |issue=2 |pages=279–284 |mr=1510702 |doi=10.1007/BF01206656 |s2cid=119535189 }}
* {{cite book |first=A. Ya. |last=Khinchin |author-link=Aleksandr Khinchin |title=Continued Fractions |publisher=Dover |year=1997 |orig-year=1964 |isbn=0-486-69630-8 }}
*{{cite journal |last1=Kleinbock |first1=D. Y. |last2=Margulis |first2=G. A. |author2-link= Grigory Margulis |title=Flows on homogeneous spaces and Diophantine approximation on manifolds |journal=Ann. Math. |volume=148 |issue=1 |year=1998 |pages=339–360 |mr=1652916 |zbl=0922.11061 |doi=10.2307/120997 |jstor=120997|arxiv=math/9810036 |bibcode=1998math.....10036K |s2cid=8471125 }}
* {{cite book |first=Serge |last=Lang |author-link=Serge Lang |title=Introduction to Diophantine Approximations |edition=New expanded |publisher=[[Springer-Verlag]] |year=1995 |isbn=0-387-94456-7 |zbl=0826.11030 }}
* {{cite book |first=G. A. |last=Margulis |author-link=Grigory Margulis |chapter=Diophantine approximation, lattices and flows on homogeneous spaces |title=A panorama of number theory or the view from Baker's garden |editor1-last=Wüstholz |editor1-first=Gisbert |editor1-link=Gisbert Wüstholz |pages=280–310 |publisher=[[Cambridge University Press]] |___location=Cambridge |year=2002 |mr=1975458 |isbn=0-521-80799-9 }}
Line 243 ⟶ 259:
* {{cite book |zbl=0421.10019 |last=Schmidt |first=Wolfgang M. |author-link=Wolfgang M. Schmidt |edition=1996 |title=Diophantine approximation |series=Lecture Notes in Mathematics |volume=785 |___location=Berlin-Heidelberg-New York |publisher=[[Springer-Verlag]] |year=1980 |isbn=3-540-09762-7 }}
* {{cite book |last=Schmidt |first=Wolfgang M. |author-link=Wolfgang M. Schmidt |title=Diophantine approximations and Diophantine equations |series=Lecture Notes in Mathematics |volume=1467 |publisher=[[Springer-Verlag]] |year=1996 |edition=2nd |isbn=3-540-54058-X |zbl=0754.11020 }}
*{{cite journal | last1=Siegel | first1=Carl Ludwig | author1-link=Carl Ludwig Siegel | title=Approximation algebraischer Zahlen | doi=10.1007/BF01211608 | year=1921 | journal=[[Mathematische Zeitschrift]] | issn=0025-5874 | volume=10 | issue=3 | pages=173–213 | s2cid=119577458 | url=https://zenodo.org/record/1538156 }}
* {{cite book |last=Sprindzhuk |first=Vladimir G. |title=Metric theory of Diophantine approximations |others=Transl. from the Russian and ed. by Richard A. Silverman. With a foreword by Donald J. Newman |series=Scripta Series in Mathematics |publisher=John Wiley & Sons |year=1979 |isbn=0-470-26706-2 |mr=0548467 |zbl=0482.10047}}
*{{cite journal | last1=Thue | first1=A. | author1-link=Axel Thue | title=Über Annäherungswerte algebraischer Zahlen | url=http://resolver.sub.uni-goettingen.de/purl?PPN243919689_0135 | year=1909 | journal=[[Journal für die reine und angewandte Mathematik]] | issn=0075-4102 | volume=1909 | issue=135 | pages=284–305 | doi=10.1515/crll.1909.135.284 | s2cid=125903243 }}
{{refend}}
== External links ==
* [http://people.math.jussieu.fr/~miw/articles/pdf/HCMUNS10.pdf Diophantine Approximation: historical survey] {{Webarchive|url=https://web.archive.org/web/20120214101838/http://people.math.jussieu.fr/~miw/articles/pdf/HCMUNS10.pdf |date=2012-02-14 }}. From ''Introduction to Diophantine methods'' course by [[Michel Waldschmidt]].
* {{springer|title=Diophantine approximations|id=p/d032600}}
| |||