4
$\begingroup$

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential height functions.

The basic premise of Diophantine approximation is that you take a dense countable set(traditionally the rationals or the algebraic numbers), $A$ in some range(generally $(0,1)$) and a function $H: A \to \mathbb N$, the height function. You then see how given $N \in \mathbb N$ close you can get a member of $A$, usually referred to as $\alpha$ with $H(\alpha) < N$. The most famous result from this field is Dirichlet's Approximation Theorem which states that for any real in $(0,1)$ there exist infinitely many rationals $\frac{p}{q}$ such that $|x-\frac{p}{q}| \le \frac{1}{q^2}$. This has been shown to be optimal up to a constant.

Some height functions I imagined for the computable numbers would be

1) $H_c(\alpha)$ This is a restricted version of the above when the Turing machine is restricted to having $c$-characters not counting blank.

2) Same as 1 just counting transitions instead of states.

3) Some function on the time complexity to generate the number

4) Some function on the space complexity to generate the number

The first 2 are basically variants on Kolmogorov complexity I believe. The last two I'm not even sure how to map to the Naturals.

Here are some preliminary results I believe are true.

For 1 Using just rationals and an $x \in (0,1)$ you get an approximation of the following form $$|x-\alpha| \le Cc^{-H_c(\alpha)}$$ For some $C>0$. I believe I can prove this. If it is true that using algebraic numbers of degree at most $d$ gives an approximation function of $|x-\alpha| \le cH^{-d-1}(\alpha)$ for some $c>0$ then I believe the same approximation function holds even if you use all algebraic numbers. The basic reasoning behind this is that it takes $O((d+1)\log_c(\max(a_1,\dots,a_{d+1})))$ states to output all the coefficients to the tape and then you should be able to do Newton's algorithm with a constant number of states. In the last equation $a_1,\dots,a_{d+1}$ is the set of coefficients of the minimal polynomial specifying $\alpha$.

Noting that the number of transitions is approximately equal to $c+1$ times the number of states you get an equivalent statement for 2 that for $x \in (0,1)$ you get $$|x-\alpha| \le Cc^\frac{-H_c(\alpha)}{c+1}$$

For some constant $C > 0$. Due to these results I'd say 2 is probably the nicest approximation function since $c^\frac{n}{c+1}$ when restricted to integer inputs is bounded by $\sqrt[5]{4}^n$ or roughly $1.3195^n$.

A result I'd like to have and I believe is true is that the bounds on the approximation function for $3$ are optimal, that is that there exists $x \in (0,1)$ such that $$|x-\alpha| \ge Cc^\frac{-H_c(\alpha)}{c+1}$$ For some constant $C>0$ and all but finitely many computable $\alpha$.

My basic question is whether there is any research and if not whether this is worth pursuing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.