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?

  • $\begingroup$ 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? $\endgroup$ – Artemy May 18 '19 at 11:00
  • $\begingroup$ @Artemy I don't see how $log^* n > log n + log log n$ for sufficiently large n... Care to elaborate? $\endgroup$ – Holt May 18 '19 at 11:31
  • $\begingroup$ 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). $\endgroup$ – Artemy May 18 '19 at 13:21
  • $\begingroup$ @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). $\endgroup$ – Holt May 18 '19 at 13:31
  • $\begingroup$ They are not equivalent, and yes, that is the definition used in the book (see p. 469). $\endgroup$ – Artemy May 19 '19 at 9:30

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.