The other day I discovered the Hardy-Ramanujan theorem, which suggested to me that the Kolmogorov complexity of any factorization of some $n$, given $n$, is negligible, a claim I am looking to verify. I.e., because there are few prime factors, any partition thereof can be described efficiently.
The theorem states that the number of prime factors with multiplicity, $\Omega(n)$, takes the expected value $$ E[\Omega(n)] = \ln \ln n $$ (if the `$\log$' in the original is the natural logarithm).
Assume that you are given $n\in \mathbb{N}$ and know that $\exists x_1,\ldots,x_k. \prod_{i=1}^k x_i = n$. The number of ways of distributing the $\Omega(n)$ prime factors among $k$ distinct composite factors is no more than $k^{\Omega(n)}$, describable in $\approx \Omega(n) \lg k$ bits. Some ways of summarizing this are as follows: $$ K(x_{1\ldots k} \mid n, k) \le \Omega(n)\cdot\lg k + O(1) $$ $$ E[K(x_{1\ldots k} \mid n, k)] = \ln\ln n\cdot \lg k + O(1) $$ $$ E[K(x_{1\ldots k} \mid n, k)] \le \lg\lg n\cdot \lg k + O(1) $$ $$ E[K(x_{1\ldots k} \mid n)] \le K(k) + \lg\lg n\cdot \lg k + O(1) $$ If we assume that $k \le \Omega(n)$: $$ E[K(x_{1\ldots k} \mid n, k)] \le \lg\lg n\cdot \lg\lg\lg n + O(1) $$
From this I conclude that, in general, $K(n, x_{1\ldots k} ) \sim K(n)$.
Is this correct?