# Kolmogorov complexity of a product of two numbers

In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $$K(x)$$ of a word $$x$$ consisting of zeros and ones as the binary length of the shortest Pascal program that generates $$x$$. The Kolmogorov complexity $$K(n)$$ of a natural number $$n$$ is then defined as the Kolmogorov complexity of the binary representation of $$n$$.

To show that there's a constant $$d$$ such that $$K(x)\leq|x|+d$$ for all words $$x$$ (where $$|x|$$ is the length of $$x$$), he uses the following (pseudo) program $$A_x$$ to generate $$x$$:

begin
write(x);
end


But he notes (in the 2007 German edition of the book, but not in the 2004 English edition) that we would have to prefix the code with two numbers $$k$$ and $$l$$ with $$k$$ being the length of the (constant) "prefix" of the program (up to and including the opening parenthesis) and $$l$$ being the length of the "suffix" (starting with the closing parenthesis). The reason for this is that we can thus store $$x$$ verbatim (as a sequence of ones and zeros) while the constant part of the program is the same for each $$x$$ (and responsible for the constant $$d$$ above).

So far, so good. I can understand how this is supposed to work, but because he tries to avoid encoding the length of $$x$$ into the program (as he writes himself) we obviously have to know where the program ends to make sense of $$l$$. (One could for example image that one receives $$A_x$$ as a file.)

But two pages later there's an exercise where he claims that for a positive natural number $$n=pq$$ we have $$K(n)\leq K(p)+K(q)+c$$ with a constant $$c$$ independent of $$n$$, $$p$$, and $$q$$. I think the basic idea here is that $$c$$ is the length of a program that executes the corresponding programs for the two factors and multiplies them. But if the programs for $$p$$ and $$q$$ are programs like above we would need to know how long they are - which we don't. I can easily see how to prove $$K(n)\leq 2\max(K(p),K(q))+c$$ or $$K(n)\leq K(p)+\log_2(K(p))+K(q)+c$$ or something similar, but I'm at loss regarding $$K(n)\leq K(p)+K(q)+c$$. Any ideas?

• Seems like a mistake. This kind of inequality holds for self-delimiting Kolmogorov complexity (often denoted $C(\cdot)$), which doesn't satisfy $K(x) \leq |x| + O(1)$. May 17 '20 at 14:56