3
$\begingroup$

Roughly speaking,Kolmogorov Complexity of a bits string or a description is the minimal length of programs outputing a bits string,and height of rational number is logarithm of the largest numerator or denominator of the rational.What is the relation between them? It seems that they are the same.

And more generally,what is the relation between Kolmogorov Complexity and height in arithmetic algebraic geometry?

Since I just know very little of arithmetic algebraic geometry,the question may be ambiguous.If so,please point out the ambiguity,and I will clarify it.

$\endgroup$
7
  • 1
    $\begingroup$ What? There's no way for Kolmogorov complexity to be "the same" as any invariant that doesn't depend on a choice of programming language (which Kolmogorov complexity does). Consider more explicitly, for example, the sequence of rational numbers $a_n = 2^{2^n}$, which has Kolmogorov complexity something like $O(\log n)$ but exponentially increasing height. $\endgroup$ Mar 30, 2014 at 1:47
  • $\begingroup$ @QiaochuYuan,I just ask the relation between them,if they are not the same.In fact,KC is invariant except constant,see An introduction to kolmogorov complexity and it's application by Vitanyi and Li for more.And if you are expert in arithmetic geometry,is there any definition of height of rational point in an intrinsic way?What is the relation between KC and intrinsic height? $\endgroup$ Mar 30, 2014 at 1:57
  • 2
    $\begingroup$ I tend to think of the height of a rational number, or more generally an algebraic number $\alpha$ of degree $d$, as the big-Oh number of bits it takes to describe the number (as one of some finite set of bounded size, e.g., Galois conjugation). So for example, for $h(\alpha)$, you could take the usual definition of Weil height, or the maximum of the absolute values of the coefficients of its minimal polynomial in $\mathbb{Z}[x]$ (with gcd(coefs) ${}=1$), or anything similar. I don't know the relation between this sort of "descriptive complexity" and Kolmogorov computational complexity. $\endgroup$ Mar 30, 2014 at 2:56
  • $\begingroup$ @JoeSilverman,they sound like relevent,if not the same,if I have not misunderstood what you says.I am not sure if they are just equivalent but in different forms, $\endgroup$ Mar 30, 2014 at 3:31
  • 1
    $\begingroup$ For a Martin-Löf random real $x$ with a fast rational Cauchy sequence $(q_n)$, there might be a connection between the Kolmogorov complexity of $q_n$ and its height. If I remember, I'll work out the details tomorrow. $\endgroup$
    – Jason Rute
    Mar 30, 2014 at 3:38

1 Answer 1

3
$\begingroup$

After thinking about it for a bit, the relationship is as follows for a rational $q$, $$K(\text{height}\,q) \leq^+ K(q) \leq^+ 2\,\text{height}\,q.$$ This isn't really a surprising or useful relationship, but I spell out the details nonetheless.

Upper Bound

Recall that the Kolmogorov complexity of a nonnegative rational $q$ is defined as $K(q):= K(k,l)$ where $q=k/l$ in lowest terms. Also recall that all notions of equality and inequality are up to an additive constant, which I will denote as $=^+$ and $\leq^+$. By (the stronger version of) symmetry of information we have $$K(q)= K(k,l)=^+ K(k \mid l,K(l)) + K(l).$$ Then we have the bounds (where $\log_2$ and $\text{height}$ are rounded down to an integer), $$K(q) \leq^+ \log_2 k + \log_2 l \leq 2\,\text{height}\,q.$$

$$ $$

I believe this upper bound $K(q) \leq^+ 2\,\text{height}\,q$ should be tight in the following sense. Let $(X,Y)$ be a Martin-Löf random pair in $\{0,1\}^\infty$. Recall, $X$ is a Martin-Löf random if, there is some $C$ such that for all $n$, $K(X\upharpoonright n) \geq n - C$ where $K\upharpoonright n$ denotes the first $n$ bits of $X$. A Martin-Löf random pair is (by van Lambalgen's theorem) is a pair where $X$ is Martin-Löf random and $Y$ is Martin-Löf random relative to $X$. Then, I believe that this implies that there is a constant $C$ such that for all $n$, $$K(X \upharpoonright n, Y\upharpoonright n) \geq 2n -C$$ (although, you should check this detail). Then let $q_n$ be the rational gotten by taking ratio of $X\upharpoonright n$ and $Y \upharpoonright n$ (converted via binary into integers). Then we have that there is some $C$ such that for all $n$, $$K(q_n) \geq 2\,\text{height}\,q_n - C.$$ (I guess I am also using that these $q_n$ are written in lowest terms---that is $X\upharpoonright n$ and $Y \upharpoonright n$ are relatively prime---for sufficiently large $n$. This seems reasonable, but I guess that is another detail that needs to be checked. If it is not true, I think "for all $n$" can be replaced with "infinitely many $n$".)

Lower bound

Since the height is computable from $q$, we have $$K(\text{height}\,q) \leq^+ K(q).$$

This lower bound is also tight in the following sense. Consider a computable real number like $\pi=3.14...$. Let $\pi_n$ denote the dyadic rational approximation of $\pi$ up to $n$ decimal places. Then there is some $C$ such that for all $n$, $$K(\pi_n) \leq K(n) + C.$$ For all the $n$ such that $\text{height}\,(\pi_n)=n$---which happens when $\pi_n$ has a $1$ for the $n$th decimal place---we have $$K(\pi_n) \leq K(\text{height}\, \pi_n) + C.$$

$\endgroup$
1
  • $\begingroup$ Thanks a lot,but I think it is very interesting,since the two direction are far away from each other. $\endgroup$ Mar 30, 2014 at 22:59

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.