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.



What is the relation between KC and height of rational number?
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.$$


