Namespaces
Variants
Actions

Difference between revisions of "Duffin-Schaeffer conjecture"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 93 formulas out of 95 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202901.png" /> be a function defined on the positive integers and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202902.png" /> be the Euler [[Totient function|totient function]]. The Duffin–Schaeffer conjecture says that for an arbitrary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202903.png" /> (zero values are also allowed for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202904.png" />), the Diophantine inequality (cf. also [[Diophantine equations|Diophantine equations]])
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202905.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
Out of 95 formulas, 93 were replaced by TEX code.-->
  
has infinitely many integer solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202906.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202907.png" /> for almost-all real <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202908.png" /> (in the sense of [[Lebesgue measure|Lebesgue measure]]) if and only if the series
+
{{TEX|semi-auto}}{{TEX|partial}}
 +
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]])
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d1202909.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
\begin{equation} \tag{a1} \left| x - \frac { p } { q } \right| &lt; f ( q ) , \quad \operatorname { gcd } ( p , q ) = 1 , q &gt; 0, \end{equation}
  
diverges. By the [[Borel–Cantelli lemma|Borel–Cantelli lemma]], (a1) has only finitely many solutions for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029010.png" /> if (a2) converges, and by the [[Gallagher ergodic theorem|Gallagher ergodic theorem]], the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029011.png" /> for which (a1) has infinitely many integer solutions has measure either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029012.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029013.png" />.
+
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
  
The Duffin–Schaeffer conjecture is one of the most important unsolved problems in the [[Metric theory of numbers|metric theory of numbers]] (as of 1998). It was inspired by an effort to replace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029014.png" /> by a smaller function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029015.png" /> for which every irrational number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029016.png" /> can be approximated by infinitely many fractions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029017.png" /> such that (a1) holds. This question was answered by A. Hurwitz in 1891, who showed that the best possible function is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029018.png" />. The application of Lebesgue measure to improve this <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029019.png" /> was made by A. Khintchine [[#References|[a7]]] in 1924. He proved that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029020.png" /> is non-increasing and
+
\begin{equation} \tag{a2} \sum _ { q = 1 } ^ { \infty } \varphi ( q ) f ( q ) \end{equation}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029021.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
diverges. By the [[Borel–Cantelli lemma|Borel–Cantelli lemma]], (a1) has only finitely many solutions for almost-all $x$ if (a2) converges, and by the [[Gallagher ergodic theorem|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$.
  
diverges, then (a1) has infinitely many integer solutions for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029022.png" />. In 1941, R.J. Duffin and A.C. Schaeffer [[#References|[a1]]] improved Khintchine's theorem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029023.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029024.png" /> for infinitely many <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029025.png" /> and some positive constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029026.png" />. They also have given an example of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029027.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029028.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029029.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029030.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029032.png" />-dimensional analogue of the Duffin–Schaeffer conjecture: There are infinitely many integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029034.png" /> such that
+
The Duffin–Schaeffer conjecture is one of the most important unsolved problems in the [[Metric theory of numbers|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 [[#References|[a7]]] in 1924. He proved that if $q ^ { 2 } f ( q )$ is non-increasing and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029035.png" /></td> </tr></table>
+
\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
 +
 
 +
<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>
  
 
and
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029036.png" /></td> </tr></table>
+
\begin{equation*} \operatorname { gcd } ( p _ { 1 } \ldots p _ { k } , q ) = 1 \end{equation*}
  
for almost-all real numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029037.png" /> whenever the series
+
for almost-all real numbers $( x _ { 1 } , \dots , x _ { k } )$ whenever the series
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029038.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>
+
\begin{equation} \tag{a4} \sum _ { q = 1 } ^ { \infty } ( \varphi ( q ) f ( q ) ) ^ { k } \end{equation}
  
diverges. A.D. Pollington and R.C. Vaughan [[#References|[a10]]] have proved this <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029039.png" />-dimensional Duffin–Schaeffer conjecture for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029040.png" />. The corresponding result with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029041.png" /> instead of the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029042.png" /> was given by P.X. Gallagher [[#References|[a3]]].
+
diverges. A.D. Pollington and R.C. Vaughan [[#References|[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 [[#References|[a3]]].
  
Various authors have studied the problem that the number of solutions of (a1) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029043.png" /> is, for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029044.png" />, asymptotically equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029045.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029046.png" /> and the denominators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029047.png" /> in (a1) to sets of number-theoretic interest was investigated by G. Harman. In [[#References|[a6]]] he considers (a1) where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029049.png" /> are both prime numbers. In this case, the Duffin–Schaeffer conjecture has the form: If the sum
+
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 [[#References|[a6]]] he considers (a1) where $p$, $q$ are both prime numbers. In this case, the Duffin–Schaeffer conjecture has the form: If the sum
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029050.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a5)</td></tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029051.png" /> there are infinitely many prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029053.png" /> which satisfy (a1). Harman has proved this conjecture under certain conditions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029054.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029056.png" />, of distinct positive integers and a class of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029057.png" /> is said to satisfy the Duffin–Schaeffer conjecture if the divergence of
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029058.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a6)</td></tr></table>
+
\begin{equation} \tag{a6} \sum _ { n = 1 } ^ { \infty } \varphi ( q _ { n } ) f ( q _ { n } ) \end{equation}
  
implies that for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029059.png" /> there exist infinitely many <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029060.png" /> such that the Diophantine inequality
+
implies that for almost-all $x$ there exist infinitely many $n$ such that the Diophantine inequality
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029061.png" /></td> </tr></table>
+
\begin{equation*} \left| x - \frac { p } { q_n } \right| &lt; f ( q_n ) \end{equation*}
  
has an integer solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029062.png" /> that is mutually prime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029063.png" /> (cf. also [[Mutually-prime numbers|Mutually-prime numbers]]). There are tree types of results regarding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029065.png" /> 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]]]):
  
i) any one-to-one sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029066.png" /> and special <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029067.png" /> (e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029068.png" />);
+
i) any one-to-one sequence $q_n$ and special $f ( q )$ (e.g. $f ( q ) = O ( 1 / q ^ { 2 } )$);
  
ii) any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029069.png" /> and a special <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029070.png" /> (e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029071.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029072.png" />);
+
ii) any $f ( q ) \geq 0$ and a special $q_n$ (e.g. $q _ { n } = n ^ { k }$, $k \geq 2$);
  
iii) special <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029073.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029074.png" /> (e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029075.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029076.png" />). As an interesting consequence of the Erdös result, for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029077.png" /> infinitely many denominators of the [[Continued fraction|continued fraction]] convergents to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029078.png" /> lie in the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029079.png" /> if and only if (a6) diverges.
+
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.
  
Following J. Lesca [[#References|[a8]]], one may extend the Duffin–Schaeffer conjecture to the problem of finding sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029080.png" /> such that for every non-increasing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029081.png" />, 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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029082.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a7)</td></tr></table>
+
\begin{equation} \tag{a7} \sum _ { n = 1 } ^ { \infty } y _ { n } \end{equation}
  
implies that for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029083.png" /> there exist infinitely many <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029084.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029085.png" />. These <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029086.png" /> 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 } | &lt; y _ { n }$. These $x _ { n }$ are called eutaxic sequences. This problem encompasses all of the above conjectures.
  
As an illustration, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029087.png" /> be a sequence of reduced fractions with denominators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029088.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029089.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029090.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029091.png" /> with a fixed denominator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029092.png" />. This gives the classical Duffin–Schaeffer conjecture, since (a6) and (a7) coincide. It is known that the sequence of fractional parts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029093.png" /> is eutaxic if and only if the irrational number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029094.png" /> 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.
  
 
Finally, H. Nakada and G. Wagner [[#References|[a9]]] have considered a complex version of the Duffin–Schaeffer conjecture for imaginary quadratic number fields.
 
Finally, H. Nakada and G. Wagner [[#References|[a9]]] have considered a complex version of the Duffin–Schaeffer conjecture for imaginary quadratic number fields.
Line 64: 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120290/d12029095.png" />-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>

Revision as of 17:03, 1 July 2020

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=22361
This article was adapted from an original article by O. Strauch (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article