Does there exist a general theory of "arithmetic complexity"/"arithmetic height"?

Question

This question is hopelessly vague, but here goes:

Say I'm given some finite precision complex number, which I'm told is algebraic over $\mathbb{Q}$. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

For example, say I'm given $\sqrt{2}$ to 50 decimal places. Then what number this represents could be one of many things: the rational number which is $\sqrt{2}$ to 50 decimal places itself, or precisely $\sqrt{2}$, or other things. In some sense $\sqrt{2}$ is the "right" answer: it is definitely easier to describe than the other possibilities.

Arguably the general situation is not going to be as clear cut as in this case, but I'd love to know if there is any general theory along these lines that I haven't heard of. It seems like you can do a fair amount of stuff just working with a height function on number fields, and finding all elements agreeing up to that given precision within certain bounds for the height, but I feel there should be much more to say.

For example, given a number field $K$ of degree $d$ over $\mathbb{Q}$, we can define a height by $h(a) = \frac{1}{d} \sum_{v \in M_K} \log \left( \mathrm{max}(1,v(a) \right )$ where $v$ runs over the set $M_K$ of valuations. I don't know how good a choice this is, but it is explicit enough to allow to use it to show some of the above properties.

Edit: Actually, a definition that is easier to deal with is something like Kevin mentioned: set the height $H(a)$ to be the sum of the degree of $a$ and of the absolute values of the coefficients of its minimal polynomial. Then it is definitely true that there are only finitely many numbers with height $H$ lower than some given bound. This makes it very easy to deal with on a case by case basis (although it is obviously not computationally effective), so I'm more interested in what general type of theorems you can get.

A good example of the flavour of the theorems I have in mind would be the Thue-Siegel-Roth Theorem: in a way, it expresses how hard it is to approximate algebraic numbers with rational numbers. In particular, it gives an idea that it is hard to approximate an algebraic number of low complexity by a rational number of similarly low complexity. But in my mind this should be just the beginning.

(No idea what tags to use: I don't think complexity theory is adequate, but I can't find any better)

Answer 1

In practice what you'll do is look for linear relations with integer coefficients between powers of $\alpha$ (starting with $\alpha^0=1$). If $\alpha$ is algebraic then suddenly you'll find a relation where the coefficients are smallish and the linear cobination is vanishingly small. The $LLL$ algorithm (implemented in e.g. pari-gp) does this for you. A measure of the complexity could then just be the sum of the absolute values of the coefficients of the polynomial or some such thing.

Answer 2

In your example, what you seem to be asking for is the algebraic number with the simplest possible description, that agrees with those 50 digits. Since the sqrt(2) seems likely to have a shorter description than any of the other algebraic numbers having those precise digits, it is quite reasonable to want to take it as a description of sqrt(2) itself.

There is a highly developed generalizations of such questions in the field known as information theory. The basic situation is that we have a finite or infinite string of bits, and we want to measure the amount of information in this string. One solution, the main idea of Kolmogorov complexity is to measure the complexity or information content of a string by the size of the smallest program able to produce it. For example, the string "abababababab.....abab" of length 100 million symbols has a comparatively short program that produces it, whereas a more random sequence will not have such a program.

In your case, the digits of sqrt(2) have a relatively short program able to produce them, and so have comparatively little information content in Kolmogorov complexity. Every algebraic number is computable and so has some program to produce it, and thus one can arrive at a general solution of your problem this way.

But of course, this problem is not just about algebraic numbers, but about the information present in sequences in general. And this is what the subject of infomration theory is about.

Let me remark that the question is interesting even for natural numbers! That is, some large integers have very short descriptions, such as 10¹⁰¹⁰, but another number of the same relative size might have only much longer descriptions. We could measure the infomration content of a natural number by the size of the smallest program able to write out the decimal (or binary) representation of that number. Numbers whose smallest programs are basically storing the digits of the number itself could be said to be incompressible, and this is one of many interesting concepts studied in this area.

Answer 3

There is a well-defined theory of this in terms of algorithmic complexity (aka Kolmogorov complexity), but it won't let you actually compute this number unless you put more constraints on your problem. The idea behind Kolmogorov complexity is that you fix some system of universal computation (Turing machines, lambda calculus, etc), and then you define the complexity of a number to be the length of the shortest program which will print out the digits of the number (in this case, presumably you want it to print the coefficients of the polynomial). Unfortunately, the Kolmogorov complexity is (a) uncomputable, and (b) it can vary depending on the exact model of computation you choose (though never by more than an additive constant, due to to the equivalence of all models of computation).

However, you can use a different idea of the same general character, if you can put more constraints on the generators of your polynomials. In particular, if you can specify the possible probability distributions over the coefficients of the polynomials, then you can use maxent (entropy maximization) methods to estimate which polynomials are most likely to have generated the digits you want. The reason you have to specify the possible distributions is because there is no uniform distribution over the natural numbers, and so you have to decide what ignorance means in this situation.

Answer 4

Every answer before points You into algebraic complexity theory which is very fashionable today. I would like to try to point in some other direction, which probably is not what You are looking for, but is in my opinion interesting. I have hope that other than usual look is interesting and is not just misinterpretation of Your question.

Say I'm given some finite precision complex number, which I'm told is algebraic over $\mathbb{Q}$. Is there some well defined notion of arithmetic complexity which can allow me to deduce exactly what algebraic number this finite precision number represents?

Finite precision number is rational number. Then it has finite representation as continued fraction or as decimal number with finite number of digits. Say last digit is $a_n$ which means that we know Your number as $A=...a_0 + a_1/10 + a_2/10^2+... + a_n/10^n$ Then as You may see from decimal representation such number represents whole interval $I=[A,A+(a_n+1)/10^n]$. So as You ask for algebraic numbers, it may represent every algebraic number within this interval.

The other way to look at is is to use Stern-Brocot tree which is by means of continued fraction $A=[b_0;b_1,b_2,...,b_k]$ for some k. Then number A represents the whole tree when A is a root of it, and every branch of this tree, finite or infinite represents some number. It is interesting, that there You may say that every possible subtree with root in A may be represented by sequences of turns like $LLRRLLLLRLRLLR...$ (XX) on the tree, where R means right, and L means left, finite or infinite. There are interesting relation to Minkowski question mark function and Cantor function.

Then if I understand right, it is possible to reformulate Your question and say that You are asking for algebraic numbers represented within given interval or represented by certain sequences within giver family of sequences like (XX).

As You may see subtree of Stern-Brocot tree is isomorphic to the whole tree, and it is obvious that within given interval You may find infinite number of algebraic numbers. So in fact if You will see any pattern for algebraic number in given interval ( given with some procession) then You may reformulate it as property of whole set of algebraic numbers. And up to Your question: within given interval there is infinite subset of algebraic numbers with any computational complexity. That is because within subtree of Stern-Brocot tree there are presented sequences of any Kolmogorov measure You may think of. Stating finite precision, in fact You give some very beginning sequence in a tree, but not the infinite possible rest.

Interesting case is to ask if there exists any patterns for S-B tree or for any other (decimal, hexadecimal etc) representation for a numbers which may give us insight into property of numbers ( there are some, such simple as divisibility by 2 for example or much more complicated). For example is there any property in any representation ( possibly effective, not straight from the definition of algebraic number) which allows us to say that given number is algebraic, or algebraic of specified kind? As far as I know there is no pattern in continued fractions coefficients for general algebraic number, although, You may find pattern in numbers which are roots of quadratic diofantine equations. So Your question in general has no answer,but there are some patterns in known representations of numbers which gives us some classes of algebraic numbers: for example quadratic one. Maybe someday someone will find other patterns/representations which provide us other possibilities...