1
$\begingroup$

Let $\omega=(\omega_1,\ldots,\omega_{m})$ be an $m$-tuple of real numbers. Let $|\omega|_{m}:=\sup\limits_{1 \leq j \leq m}|\omega_j|_{1}$ be a metric on flat torus $\mathbb{T}^{m}=\mathbb{R}^{m}/\mathbb{Z}^m$, i. e. $|\theta|_{1}$ is the distance from $\theta$ to nearest integer.

We say that an $m$-tuple $\omega$ satisfies the Diophantine condition of order $\nu \geq 0$ if there is a constant $C>0$ such that for all natural $q$ the inequality $$|\omega q|_{m} \geq C \left(\frac{1}{q}\right)^{\frac{1+\nu}{m}}$$ is satisfied.

Suppose we have some algorithm that provides a sequence of convergents (fractions which approximate $\omega$) with denominators $\{ q_{k} \}$. I want to find such an algorithm, which satisfyes the following properties

Property 1. If $\omega$ satisfies the Diophantine condition, then $q_{k+1}=O\left(q^{1+\nu}_{k}\right)$.

Property 2. For many (in some sense) $\omega$ there is a constant $\hat{C}>0$ such that the estimate $$\sum\limits_{k=N}^{\infty}\frac{1}{q_{k}} \leq \hat{C}\frac{1}{q_{N}}$$ holds for all large enough $N$.

The classic continued fraction algorithm for $m=1$ provides the required denominators: property 1 is equivalent to the Diophantine condition and Property 2 holds for all real numbers.

Are there known multi-dimensional algorithms, satisfying the above properties? I will be grateful for any help.

$\endgroup$
0
$\begingroup$

Theorem. Suppose that an $m$-tuple $\omega$ satisfies the Diophantine condition of order $\nu \geq 0$. Then there exists a sequence $\{q_{k}\}$ of natural numbers, $k=1,2,\ldots$, and a constant $\hat{C}=\hat{C}(\omega)>0$ such that

  • $|\omega q_{k}|_{m} \leq \hat{C} \cdot \left(\frac{1}{q_{k+1}}\right)^{1/m}$.
  • $q_{k} \leq q_{k+1}$, $q_{k+1}=O\left(q^{1+\nu}_{k}\right)$ and there exists constants $\gamma_{2}>\gamma_{1}>1$ and $A_{1},A_{2}>0$ such that $$A_{1} \gamma^{k}_{1}\leq q_{k} \leq A_{2} \gamma^{k}_{2}.$$
  • $\sum\limits_{k=N}^{\infty}\frac{1}{q_{k}} \leq \hat{C}\frac{N}{q_{N}}$.

Proof.

  • By the Dirichlet theorem, for all $Q>0$ there exists a natural number $1 \leq q \leq Q$ such that $$|\omega q|_{m} \leq \left(\frac{1}{Q}\right)^{1/m}.$$ Let $\alpha>1$ be fixed and let $q_{k}$ be a number $q$ from the Dirichlet theorem for $Q = \alpha^{k}$. If we get $q_{k+1}<q_{k}$ for some $k$, then we can put $q_{k}:=q_{k+1}$ and so on.

  • Now for some $C>0$ we have $$C \left(\frac{1}{q^{1+\nu}_{k}}\right)^{1/m} \leq |\omega q_{k} | < \left(\frac{1}{\alpha^{k}}\right)^{1/m} \leq \left(\frac{1}{q_{k}}\right)^{1/m}$$ and, consequently, $$C^{\frac{m}{1+\nu}}\alpha^{\frac{k}{1+\nu}} \leq q_{k} \leq \alpha^{k}.$$ It is easy too see that $$q_{k+1} \leq \alpha^{k+1}=\alpha\cdot\alpha^{k}=\alpha C^{-m}\left(C^{\frac{m}{1+\nu}} \alpha^{\frac{k}{1+\nu}}\right)^{1+\nu}\leq \alpha C^{-m} q^{1+\nu}_{k}.$$ Thus, $q_{k+1}=O(q^{1+\nu}_{k})$. One can put $\gamma_{1}:=\alpha^{\frac{1}{1+\nu}}$ with $A_{1}:=C^{\frac{m}{1+\nu}}$ and $\gamma_{2}:=\alpha$ with $A_{2}:=1$. Also note that $$|\omega q_{k}| < \left(\frac{1}{\alpha^{k}}\right)^{1/m}=\alpha^{1/m}\left(\frac{1}{\alpha^{k+1}}\right)^{1/m} \leq \alpha^{1/m}\left(\frac{1}{q_{k+1}}\right)^{1/m}.$$

  • Now we will estimate $\sum\limits_{k=N}^{\infty}\frac{1}{q_{k}}=\frac{1}{q_{N}}\sum\limits_{k=0}^{\infty}\frac{q_{N}}{q_{N+k}}.$ From the previous inequalities we have $$\frac{q_{N}}{q_{N+k}} \leq \frac{A_2}{A_1}\frac{\gamma^{N}_{2}}{\gamma^{N+k}_{1}}=\frac{A_2}{A_1}\alpha^{\frac{N\nu - k}{1+\nu}}.$$ We use this estimate only for $k \geq 2\nu N$, for low values of $k$ we will use $\frac{q_{N}}{q_{N+k}} \leq 1$. So, $$\frac{1}{q_{N}}\sum\limits_{k=0}^{\infty}\frac{q_{N}}{q_{N+k}} \leq \frac{1}{q_{N}} 2\nu N + \frac{1}{q_{N}}\sum\limits_{k \geq 2\nu N}\alpha^{\frac{N\nu - k}{1+\nu}} \leq \hat{C}\cdot\frac{N}{q_{N}},$$ where $\hat{C}>0$ is an appropriate constant.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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