# Bound on the Kolmogorov complexity of integers

I am reading Elements of Information Theory (Thomas M. Cover, Joy A. Thomas, 2nd edition) in which the following theorems are given (page 475--476):

1. For any integer $$n$$

$$K(n) \leq \log^* n + c.$$

1. There are an infinite number of integers such that $$K(n) > \log n$$.

Where $$K(n)$$ is the Kolmogorov complexity of $$n$$ and $$\log^* n$$ is the iterated logarithm of $$n$$.

Assuming both statements true, this implis that there are an infinite number of integers $$n$$ such that

$$\log n < \log^* n + c.$$

Knowing the growing rate of $$\log$$ and $$\log^*$$ this does not seem possible if $$c$$ is independent of $$n$$... Is it? If not, which one of the two above statements is false?

• I'm not sure I see the issue. For any sufficiently large $n$, $\log^* n > \log n + \log \log n > \log n$. So wouldn't the inequality $\log n < \log^* n + c$ hold for any fixed $c$ as soon as $n$ is large enough? – Artemy May 18 '19 at 11:00
• @Artemy I don't see how $log^* n > log n + log log n$ for sufficiently large n... Care to elaborate? – Holt May 18 '19 at 11:31
• In Cover & Thomas, 2nd ed., p. 469, $\log^* n$ is defined as $\log n + \log \log n + \log \log \log n + ...$ (where only positive terms are kept). – Artemy May 18 '19 at 13:21
• @Artemy if this is the definition used in the book, them it would make sense. The Wikipedia definition is different thought, and I don't think they are equivalent (especially when looking at the value). – Holt May 18 '19 at 13:31
• They are not equivalent, and yes, that is the definition used in the book (see p. 469). – Artemy May 19 '19 at 9:30