2
$\begingroup$

I am wondering about the possible best case approximation and worst case approximation of irrational numbers. I think the appropriate formulation is whether there are functions $\hat{b}(q)$ and $\check{b}(q)$ such that for any $\alpha\in [0,1)\setminus \mathbb{Q}$ we have for only finitely many $q's$

$$ \check{b}(q) \leq \Big\vert \alpha-\frac{p}{q} \Big\vert \quad \text{and} \quad \Big\vert \alpha-\frac{p}{q} \Big\vert \leq \hat{b}(q) \quad \text{for some}\;\; p\in \mathbb{Z}. $$

Later edit: If I try to phrase it alternatively, for all irrational $\alpha$ we have functions $\check{b}(\alpha,q),\hat{b}(\alpha,q)$ satisfying for infinitely many $q$'s that $$ \check{b}(\alpha,q) \leq \Big\vert \alpha-\frac{p}{q} \Big\vert \leq \hat{b}(\alpha,q). $$

Given $f:\mathbb{N}\to [1,\infty)$ satisfying that $f(n)\to \infty$, can we find $\alpha$ such that $\hat{b}(\alpha,q)=o\big(\frac{1}{f(q)})$? Can we find $\alpha$ irrational such that $\frac{1}{qf(q)}=O\big(\check{b}(\alpha,q)\big)$?

End of later edit.

By the Piegonhole principle, we know that $\check{b}(q)\geq \frac{1}{2q}$. Also, by Liouville's theorem we can see that $\hat{b}(q)=o(q^{-n})$ for all $n$. Are there more explicit asymptotic bounds ? Can we say something like $\hat{b}(q)=o(e^{-q})$ ? Can we say that $\check{b}(q)=\Theta(\frac{1}{q})$?

I tried to ask this questions on Math Stackexchange, but I had no response. I assume something like this is known and I have not found this in a short search online. I am unused to these notions so I apologize if this is a silly question.

I would appreciate any insights on this.

Later edit: By Oleg Eroshkin's comments, it seems like there is no effective bound on how small $\hat{b}(\alpha,q)$ can be.

$\endgroup$
10
  • 1
    $\begingroup$ Are you considering only algebraic numbers or any number? $\endgroup$
    – Asaf
    Commented Sep 18, 2023 at 12:14
  • 1
    $\begingroup$ @Asaf I am considering any irrational number. $\endgroup$ Commented Sep 18, 2023 at 12:17
  • 2
    $\begingroup$ It's not clear what you are asking, since the Liouville's theorem is only for algebraic numbers. There are irrational numbers that are approximated arbitrarily well. Take a very fast growing function $f(x)$ and consider a number $\sum_n 10^{-f(n)}$. $\endgroup$ Commented Sep 18, 2023 at 12:19
  • 1
    $\begingroup$ @OlegEroshkin I don't really understand why this implies arbitrarily well approximation. I am assuming that for $\alpha =\sum_n 10^{-f(n)}$ you consider $p_N/q_N= \sum_n^N 10^{-f(n)}$ , with $q_N= 10^{f(N)}$. Do you mean that the lower bound of $\frac{1}{q_N}$ cannot be improved for a general irrational number? $\endgroup$ Commented Sep 18, 2023 at 13:57
  • 3
    $\begingroup$ To make things concrete, let me consider $f(n)=10^n$. So $\alpha=\sum_n 10^{-10^n}$ and $\frac{p}{q}=\sum_{n=1}^N 10^{-10^n}$. Then $q=10^{10^n}$ and $|\alpha-p/q|<\frac{2}{10^{10^{n+1}}}=\frac{2}{q^10}$. By considering faster growing functions, like $f(n)=10^{n!}$, i can make a number such that $|\alpha-p/q|$ is smaller than any given positive function of $q$. This idea goes back to Liouville, and such numbers are known as Liouville's numbers. They are oldest examples of transcendental numbers. $\endgroup$ Commented Sep 18, 2023 at 14:37

1 Answer 1

3
$\begingroup$

If $\alpha$ is a real irrational number, then there are infinitely many coprime integers $p,q$ with $q > 0$ such that

$$\displaystyle \left \lvert \alpha - \frac{p}{q} \right \rvert < \frac{1}{q^2}$$

by Dirichlet's theorem.

One can easily construct a real number such that one can replace the right hand side with a function of $q$ that goes to zero faster than $q^{-2}$ by an arbitrary amount. That is, for any function $f$ with $\lim_{x \rightarrow \infty} f(x) = 0$ we can find a real number $\alpha_f$ such that there exist infinitely many integers $p,q$ with $\gcd(p,q) = 1, q > 0$ satisfying

$$\displaystyle \left \lvert \alpha - \frac{p}{q} \right \rvert < \frac{f(q)}{q^2}.$$

One can do this in at least two ways. First, one can simply choose the sequence of partial quotients in the continued fraction expansion of $\alpha$ to tend to infinity arbitrarily fast. Essentially equivalently, one can choose

$$\displaystyle \alpha = \sum_{n=1}^\infty a_n$$

with the sequence $\{a_n\}_{n \geq 1} \subset \mathbb{R}_{>0}$ tending to zero arbitrarily fast. For example, Liouville's original construction of a transcendental number had the choice $a_n = 10^{-n!}$.

Conversely, the badly approximable numbers are those whose sequence of partial quotients is bounded. The absolute worst approximable number is therefore the unique real number whose sequence of partial quotients consist of only 1's. This is the Golden ratio, and the statement that this is the worst approximable irrational number is due to Hurwitz. In particular, Hurwitz proved that one can improve the constant 1 in the numerator of Dirichlet's theorem by any number greater than $1/\sqrt{5}$, but no smaller.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you for your answer. Do you, by chance, have an answer on the worst case approximation? $\endgroup$ Commented Sep 20, 2023 at 10:03
  • $\begingroup$ @Keen-ameteur yes there is a unique irrational number that is the most difficult to approximate by rational numbers by a theorem of Hurwitz. I can add this to the answer. $\endgroup$ Commented Sep 20, 2023 at 17:05
  • 2
    $\begingroup$ 'Unique' here needs a little bit of clarification; all of the associates of the golden ratio — that is, any irrationals whose continued fraction expansion ends in an infinite streak of ones — have the same approximability properties. Beyond the golden ratio, when you exclude $\varphi$ and its associates there's a second-most-difficult number to approximate, etc. See mathworld.wolfram.com/HurwitzsIrrationalNumberTheorem.html for more thorough details. $\endgroup$ Commented Sep 20, 2023 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.