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$

1 Answer 1

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 agree to our terms of service and acknowledge you have read our privacy policy.