Namespaces
Variants
Actions

Difference between revisions of "Duffin-Schaeffer conjecture"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Automatically changed introduction)
m (latex details)
 
Line 9: Line 9:
 
Let $f ( q )$ be a function defined on the positive integers and let $\varphi ( q )$ be the Euler [[Totient function|totient function]]. The Duffin–Schaeffer conjecture says that for an arbitrary function $f ( q ) \geq 0$ (zero values are also allowed for $f ( q )$), the Diophantine inequality (cf. also [[Diophantine equations|Diophantine equations]])
 
Let $f ( q )$ be a function defined on the positive integers and let $\varphi ( q )$ be the Euler [[Totient function|totient function]]. The Duffin–Schaeffer conjecture says that for an arbitrary function $f ( q ) \geq 0$ (zero values are also allowed for $f ( q )$), the Diophantine inequality (cf. also [[Diophantine equations|Diophantine equations]])
  
\begin{equation} \tag{a1} \left| x - \frac { p } { q } \right| < f ( q ) , \quad \operatorname { gcd } ( p , q ) = 1 , q > 0, \end{equation}
+
\begin{equation} \tag{a1} \left| x - \frac { p } { q } \right| < f ( q ) , \quad \operatorname { gcd } ( p , q ) = 1 , q > 0, \end{equation}
  
 
has infinitely many integer solutions $p$ and $q$ for almost-all real $x$ (in the sense of [[Lebesgue measure|Lebesgue measure]]) if and only if the series
 
has infinitely many integer solutions $p$ and $q$ for almost-all real $x$ (in the sense of [[Lebesgue measure|Lebesgue measure]]) if and only if the series
Line 21: Line 21:
 
\begin{equation} \tag{a3} \sum _ { q = 1 } ^ { \infty } q f ( q ) \end{equation}
 
\begin{equation} \tag{a3} \sum _ { q = 1 } ^ { \infty } q f ( q ) \end{equation}
  
diverges, then (a1) has infinitely many integer solutions for almost-all $x$. In 1941, R.J. Duffin and A.C. Schaeffer [[#References|[a1]]] improved Khintchine's theorem for $f ( q )$ satisfying $\sum _ { q = 1 } ^ { Q } q f ( q ) \leq c \sum _ { q = 1 } ^ { Q } \varphi ( q ) f ( q )$ for infinitely many $Q$ and some positive constant $c$. They also have given an example of an $f ( q )$ such that (a3) diverges but (a2) converges which naturally leads to the Duffin–Schaeffer conjecture. Up to now (1998), this conjecture remains open. A breakthrough was achieved by P. Erdös [[#References|[a2]]], who proved that the conjecture holds, given the additional condition $f ( q ) = c / q ^ { 2 }$ or $f ( q ) = 0$ for some $c &gt; 0$. V.G. Sprindzuk comments in [[#References|[a11]]] that the answer may depend upon the Riemann hypothesis (cf. also [[Riemann hypotheses|Riemann hypotheses]]). He also proposes the following $k$-dimensional analogue of the Duffin–Schaeffer conjecture: There are infinitely many integers $( p _ { 1 } , \dots , p _ { k } )$ and $q$ such that
+
diverges, then (a1) has infinitely many integer solutions for almost-all $x$. In 1941, R.J. Duffin and A.C. Schaeffer [[#References|[a1]]] improved Khintchine's theorem for $f ( q )$ satisfying $\sum _ { q = 1 } ^ { Q } q f ( q ) \leq c \sum _ { q = 1 } ^ { Q } \varphi ( q ) f ( q )$ for infinitely many $Q$ and some positive constant $c$. They also have given an example of an $f ( q )$ such that (a3) diverges but (a2) converges which naturally leads to the Duffin–Schaeffer conjecture. Up to now (1998), this conjecture remains open. A breakthrough was achieved by P. Erdös [[#References|[a2]]], who proved that the conjecture holds, given the additional condition $f ( q ) = c / q ^ { 2 }$ or $f ( q ) = 0$ for some $c > 0$. V.G. Sprindzuk comments in [[#References|[a11]]] that the answer may depend upon the Riemann hypothesis (cf. also [[Riemann hypotheses|Riemann hypotheses]]). He also proposes the following $k$-dimensional analogue of the Duffin–Schaeffer conjecture: There are infinitely many integers $( p _ { 1 } , \dots , p _ { k } )$ and $q$ such that
  
 
<table class="eq" style="width:100%;"> <tr><td style="width:94%;text-align:center;" valign="top"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029035.png"/></td> </tr></table>
 
<table class="eq" style="width:100%;"> <tr><td style="width:94%;text-align:center;" valign="top"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029035.png"/></td> </tr></table>
Line 49: Line 49:
 
implies that for almost-all $x$ there exist infinitely many $n$ such that the Diophantine inequality
 
implies that for almost-all $x$ there exist infinitely many $n$ such that the Diophantine inequality
  
\begin{equation*} \left| x - \frac { p } { q_n } \right| &lt; f ( q_n ) \end{equation*}
+
\begin{equation*} \left| x - \frac { p } { q_n } \right| < f ( q_n ) \end{equation*}
  
 
has an integer solution $p$ that is mutually prime with $q_n$ (cf. also [[Mutually-prime numbers|Mutually-prime numbers]]). There are tree types of results regarding $q_n$, $f ( q )$ satisfying this conjecture (cf. [[#References|[a5]]]):
 
has an integer solution $p$ that is mutually prime with $q_n$ (cf. also [[Mutually-prime numbers|Mutually-prime numbers]]). There are tree types of results regarding $q_n$, $f ( q )$ satisfying this conjecture (cf. [[#References|[a5]]]):
Line 57: Line 57:
 
ii) any $f ( q ) \geq 0$ and a special $q_n$ (e.g. $q _ { n } = n ^ { k }$, $k \geq 2$);
 
ii) any $f ( q ) \geq 0$ and a special $q_n$ (e.g. $q _ { n } = n ^ { k }$, $k \geq 2$);
  
iii) special $q_n$, $f ( q )$ (e.g. $f ( q _ { n } ) q _ { n } &gt; c _ { 1 } ( \varphi ( q _ { n } ) / q _ { n } ) ^ { c _ { 2 } }$ for some $c _ { 1 } , c _ { 2 } &gt; 0$). As an interesting consequence of the Erdös result, for almost-all $x$ infinitely many denominators of the [[Continued fraction|continued fraction]] convergents to $x$ lie in the sequence $q_n$ if and only if (a6) diverges.
+
iii) special $q_n$, $f ( q )$ (e.g. $f ( q _ { n } ) q _ { n } > c _ { 1 } ( \varphi ( q _ { n } ) / q _ { n } ) ^ { c _ { 2 } }$ for some $c _ { 1 } , c _ { 2 } > 0$). As an interesting consequence of the Erdös result, for almost-all $x$ infinitely many denominators of the [[Continued fraction|continued fraction]] convergents to $x$ lie in the sequence $q_n$ if and only if (a6) diverges.
  
 
Following J. Lesca [[#References|[a8]]], one may extend the Duffin–Schaeffer conjecture to the problem of finding sequences $x _ { n } \in [ 0,1 ]$ such that for every non-increasing $y _ { n } \geq 0$, the divergence of
 
Following J. Lesca [[#References|[a8]]], one may extend the Duffin–Schaeffer conjecture to the problem of finding sequences $x _ { n } \in [ 0,1 ]$ such that for every non-increasing $y _ { n } \geq 0$, the divergence of
Line 63: Line 63:
 
\begin{equation} \tag{a7} \sum _ { n = 1 } ^ { \infty } y _ { n } \end{equation}
 
\begin{equation} \tag{a7} \sum _ { n = 1 } ^ { \infty } y _ { n } \end{equation}
  
implies that for almost-all $x \in [ 0,1 ]$ there exist infinitely many $n$ such that $| x - x _ { n } | &lt; y _ { n }$. These $x _ { n }$ are called eutaxic sequences. This problem encompasses all of the above conjectures.
+
implies that for almost-all $x \in [ 0,1 ]$ there exist infinitely many $n$ such that $| x - x _ { n } | < y _ { n }$. These $x _ { n }$ are called eutaxic sequences. This problem encompasses all of the above conjectures.
  
 
As an illustration, let $x _ { n }$ be a sequence of reduced fractions with denominators $q_{ m}$, $m = 1,2 , \dots$, and let $y _ { n } = f ( q _ { m } )$ for $x _ { n }$ with a fixed denominator $q_{ m}$. This gives the classical Duffin–Schaeffer conjecture, since (a6) and (a7) coincide. It is known that the sequence of fractional parts $n \, \alpha \, ( \operatorname { mod } 1 )$ is eutaxic if and only if the irrational number $\alpha$ has bounded partial quotients.
 
As an illustration, let $x _ { n }$ be a sequence of reduced fractions with denominators $q_{ m}$, $m = 1,2 , \dots$, and let $y _ { n } = f ( q _ { m } )$ for $x _ { n }$ with a fixed denominator $q_{ m}$. This gives the classical Duffin–Schaeffer conjecture, since (a6) and (a7) coincide. It is known that the sequence of fractional parts $n \, \alpha \, ( \operatorname { mod } 1 )$ is eutaxic if and only if the irrational number $\alpha$ has bounded partial quotients.
Line 72: Line 72:
  
 
====References====
 
====References====
<table><tr><td valign="top">[a1]</td> <td valign="top">  R.J. Duffin,  A.C. Schaeffer,  "Khintchine's problem in metric diophantine approximation"  ''Duke Math. J.'' , '''8'''  (1941)  pp. 243–255</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  P. Erdös,  "On the distribution of convergents of almost all real numbers"  ''J. Number Th.'' , '''2'''  (1970)  pp. 425–441</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  P.X. Gallagher,  "Metric simultaneous diophantine approximation II"  ''Mathematika'' , '''12'''  (1965)  pp. 123–127</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  G. Harman,  "Metric number theory" , ''London Math. Soc. Monogr.'' , '''18''' , Clarendon Press  (1998)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  G. Harman,  "Some cases of the Duffin and Schaeffer conjecture"  ''Quart. J. Math. Oxford'' , '''41''' :  2  (1990)  pp. 395–404</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  G. Harman,  "Metric diophantine approximation with two restricted variables III. Two prime numbers"  ''J. Number Th.'' , '''29'''  (1988)  pp. 364–375</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  A. Khintchine,  "Einige Saetze über Kettenbruche, mit Anwendungen auf die Theorie der Diophantischen Approximationen"  ''Math. Ann.'' , '''92'''  (1924)  pp. 115–125</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  J. Lesca,  "Sur les approximations diophantiennes a'une dimension"  ''Doctoral Thesis Univ. Grenoble''  (1968)</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  H. Nakada,  G. Wagner,  "Duffin–Schaeffer theorem of diophantine approximation for complex number"  ''Astérisque'' , '''198–200'''  (1991)  pp. 259–263</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  A.D. Pollington,  R.C. Vaughan,  "The $k$-dimensional Duffin and Schaeffer conjecture"  ''Mathematika'' , '''37''' :  2  (1990)  pp. 190–200</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  V.G. Sprindzuk,  "Metric theory of diophantine approximations" , Winston&amp;Wiley  (1979)</td></tr></table>
+
<table>
 +
<tr><td valign="top">[a1]</td> <td valign="top">  R.J. Duffin,  A.C. Schaeffer,  "Khintchine's problem in metric diophantine approximation"  ''Duke Math. J.'' , '''8'''  (1941)  pp. 243–255</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  P. Erdös,  "On the distribution of convergents of almost all real numbers"  ''J. Number Th.'' , '''2'''  (1970)  pp. 425–441</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  P.X. Gallagher,  "Metric simultaneous diophantine approximation II"  ''Mathematika'' , '''12'''  (1965)  pp. 123–127</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  G. Harman,  "Metric number theory" , ''London Math. Soc. Monogr.'' , '''18''' , Clarendon Press  (1998)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  G. Harman,  "Some cases of the Duffin and Schaeffer conjecture"  ''Quart. J. Math. Oxford'' , '''41''' :  2  (1990)  pp. 395–404</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  G. Harman,  "Metric diophantine approximation with two restricted variables III. Two prime numbers"  ''J. Number Th.'' , '''29'''  (1988)  pp. 364–375</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  A. Khintchine,  "Einige Saetze über Kettenbruche, mit Anwendungen auf die Theorie der Diophantischen Approximationen"  ''Math. Ann.'' , '''92'''  (1924)  pp. 115–125</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  J. Lesca,  "Sur les approximations diophantiennes a'une dimension"  ''Doctoral Thesis Univ. Grenoble''  (1968)</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  H. Nakada,  G. Wagner,  "Duffin–Schaeffer theorem of diophantine approximation for complex number"  ''Astérisque'' , '''198–200'''  (1991)  pp. 259–263</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  A.D. Pollington,  R.C. Vaughan,  "The $k$-dimensional Duffin and Schaeffer conjecture"  ''Mathematika'' , '''37''' :  2  (1990)  pp. 190–200</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  V.G. Sprindzuk,  "Metric theory of diophantine approximations" , Winston&amp;Wiley  (1979)</td></tr>
 +
</table>

Latest revision as of 07:42, 4 February 2024

Let $f ( q )$ be a function defined on the positive integers and let $\varphi ( q )$ be the Euler totient function. The Duffin–Schaeffer conjecture says that for an arbitrary function $f ( q ) \geq 0$ (zero values are also allowed for $f ( q )$), the Diophantine inequality (cf. also Diophantine equations)

\begin{equation} \tag{a1} \left| x - \frac { p } { q } \right| < f ( q ) , \quad \operatorname { gcd } ( p , q ) = 1 , q > 0, \end{equation}

has infinitely many integer solutions $p$ and $q$ for almost-all real $x$ (in the sense of Lebesgue measure) if and only if the series

\begin{equation} \tag{a2} \sum _ { q = 1 } ^ { \infty } \varphi ( q ) f ( q ) \end{equation}

diverges. By the Borel–Cantelli lemma, (a1) has only finitely many solutions for almost-all $x$ if (a2) converges, and by the Gallagher ergodic theorem, the set of all $x \in [ 0,1 ]$ for which (a1) has infinitely many integer solutions has measure either $0$ or $1$.

The Duffin–Schaeffer conjecture is one of the most important unsolved problems in the metric theory of numbers (as of 1998). It was inspired by an effort to replace $f ( q ) = 1 / q ^ { 2 }$ by a smaller function $f ( q )$ for which every irrational number $x$ can be approximated by infinitely many fractions $p / q$ such that (a1) holds. This question was answered by A. Hurwitz in 1891, who showed that the best possible function is $f ( q ) = 1 / ( \sqrt { 5 } q ^ { 2 } )$. The application of Lebesgue measure to improve this $f ( q )$ was made by A. Khintchine [a7] in 1924. He proved that if $q ^ { 2 } f ( q )$ is non-increasing and

\begin{equation} \tag{a3} \sum _ { q = 1 } ^ { \infty } q f ( q ) \end{equation}

diverges, then (a1) has infinitely many integer solutions for almost-all $x$. In 1941, R.J. Duffin and A.C. Schaeffer [a1] improved Khintchine's theorem for $f ( q )$ satisfying $\sum _ { q = 1 } ^ { Q } q f ( q ) \leq c \sum _ { q = 1 } ^ { Q } \varphi ( q ) f ( q )$ for infinitely many $Q$ and some positive constant $c$. They also have given an example of an $f ( q )$ such that (a3) diverges but (a2) converges which naturally leads to the Duffin–Schaeffer conjecture. Up to now (1998), this conjecture remains open. A breakthrough was achieved by P. Erdös [a2], who proved that the conjecture holds, given the additional condition $f ( q ) = c / q ^ { 2 }$ or $f ( q ) = 0$ for some $c > 0$. V.G. Sprindzuk comments in [a11] that the answer may depend upon the Riemann hypothesis (cf. also Riemann hypotheses). He also proposes the following $k$-dimensional analogue of the Duffin–Schaeffer conjecture: There are infinitely many integers $( p _ { 1 } , \dots , p _ { k } )$ and $q$ such that

and

\begin{equation*} \operatorname { gcd } ( p _ { 1 } \ldots p _ { k } , q ) = 1 \end{equation*}

for almost-all real numbers $( x _ { 1 } , \dots , x _ { k } )$ whenever the series

\begin{equation} \tag{a4} \sum _ { q = 1 } ^ { \infty } ( \varphi ( q ) f ( q ) ) ^ { k } \end{equation}

diverges. A.D. Pollington and R.C. Vaughan [a10] have proved this $k$-dimensional Duffin–Schaeffer conjecture for $k \geq 2$. The corresponding result with $\operatorname { gcd } ( p _ { 1 } , \dots , p _ { k } , q ) = 1$ instead of the condition $\operatorname { gcd } ( p _ { 1 } \ldots p _ { k } , q ) = 1$ was given by P.X. Gallagher [a3].

Various authors have studied the problem that the number of solutions of (a1) with $q \leq N$ is, for almost-all $x$, asymptotically equal to $2\sum _ { q = 1 } ^ { N } \varphi ( q ) f ( q )$.

The problem of restricting both the numerators $p$ and the denominators $q$ in (a1) to sets of number-theoretic interest was investigated by G. Harman. In [a6] he considers (a1) where $p$, $q$ are both prime numbers. In this case, the Duffin–Schaeffer conjecture has the form: If the sum

\begin{equation} \tag{a5} \sum _ { q = 2 , q \text { prime } } ^ { \infty } f ( q ) q ( \operatorname { log } q ) ^ { - 1 } \end{equation}

diverges, then for almost-all $x$ there are infinitely many prime numbers $p$, $q$ which satisfy (a1). Harman has proved this conjecture under certain conditions on $f ( q )$.

A class of sequences $q_n$, $n = 1,2 , \dots$, of distinct positive integers and a class of functions $f ( q ) \geq 0$ is said to satisfy the Duffin–Schaeffer conjecture if the divergence of

\begin{equation} \tag{a6} \sum _ { n = 1 } ^ { \infty } \varphi ( q _ { n } ) f ( q _ { n } ) \end{equation}

implies that for almost-all $x$ there exist infinitely many $n$ such that the Diophantine inequality

\begin{equation*} \left| x - \frac { p } { q_n } \right| < f ( q_n ) \end{equation*}

has an integer solution $p$ that is mutually prime with $q_n$ (cf. also Mutually-prime numbers). There are tree types of results regarding $q_n$, $f ( q )$ satisfying this conjecture (cf. [a5]):

i) any one-to-one sequence $q_n$ and special $f ( q )$ (e.g. $f ( q ) = O ( 1 / q ^ { 2 } )$);

ii) any $f ( q ) \geq 0$ and a special $q_n$ (e.g. $q _ { n } = n ^ { k }$, $k \geq 2$);

iii) special $q_n$, $f ( q )$ (e.g. $f ( q _ { n } ) q _ { n } > c _ { 1 } ( \varphi ( q _ { n } ) / q _ { n } ) ^ { c _ { 2 } }$ for some $c _ { 1 } , c _ { 2 } > 0$). As an interesting consequence of the Erdös result, for almost-all $x$ infinitely many denominators of the continued fraction convergents to $x$ lie in the sequence $q_n$ if and only if (a6) diverges.

Following J. Lesca [a8], one may extend the Duffin–Schaeffer conjecture to the problem of finding sequences $x _ { n } \in [ 0,1 ]$ such that for every non-increasing $y _ { n } \geq 0$, the divergence of

\begin{equation} \tag{a7} \sum _ { n = 1 } ^ { \infty } y _ { n } \end{equation}

implies that for almost-all $x \in [ 0,1 ]$ there exist infinitely many $n$ such that $| x - x _ { n } | < y _ { n }$. These $x _ { n }$ are called eutaxic sequences. This problem encompasses all of the above conjectures.

As an illustration, let $x _ { n }$ be a sequence of reduced fractions with denominators $q_{ m}$, $m = 1,2 , \dots$, and let $y _ { n } = f ( q _ { m } )$ for $x _ { n }$ with a fixed denominator $q_{ m}$. This gives the classical Duffin–Schaeffer conjecture, since (a6) and (a7) coincide. It is known that the sequence of fractional parts $n \, \alpha \, ( \operatorname { mod } 1 )$ is eutaxic if and only if the irrational number $\alpha$ has bounded partial quotients.

Finally, H. Nakada and G. Wagner [a9] have considered a complex version of the Duffin–Schaeffer conjecture for imaginary quadratic number fields.

The basic general reference books are [a11] and [a4].

References

[a1] R.J. Duffin, A.C. Schaeffer, "Khintchine's problem in metric diophantine approximation" Duke Math. J. , 8 (1941) pp. 243–255
[a2] P. Erdös, "On the distribution of convergents of almost all real numbers" J. Number Th. , 2 (1970) pp. 425–441
[a3] P.X. Gallagher, "Metric simultaneous diophantine approximation II" Mathematika , 12 (1965) pp. 123–127
[a4] G. Harman, "Metric number theory" , London Math. Soc. Monogr. , 18 , Clarendon Press (1998)
[a5] G. Harman, "Some cases of the Duffin and Schaeffer conjecture" Quart. J. Math. Oxford , 41 : 2 (1990) pp. 395–404
[a6] G. Harman, "Metric diophantine approximation with two restricted variables III. Two prime numbers" J. Number Th. , 29 (1988) pp. 364–375
[a7] A. Khintchine, "Einige Saetze über Kettenbruche, mit Anwendungen auf die Theorie der Diophantischen Approximationen" Math. Ann. , 92 (1924) pp. 115–125
[a8] J. Lesca, "Sur les approximations diophantiennes a'une dimension" Doctoral Thesis Univ. Grenoble (1968)
[a9] H. Nakada, G. Wagner, "Duffin–Schaeffer theorem of diophantine approximation for complex number" Astérisque , 198–200 (1991) pp. 259–263
[a10] A.D. Pollington, R.C. Vaughan, "The $k$-dimensional Duffin and Schaeffer conjecture" Mathematika , 37 : 2 (1990) pp. 190–200
[a11] V.G. Sprindzuk, "Metric theory of diophantine approximations" , Winston&Wiley (1979)
How to Cite This Entry:
Duffin-Schaeffer conjecture. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Duffin-Schaeffer_conjecture&oldid=55374
This article was adapted from an original article by O. Strauch (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article