Circuit lower bounds and kolmogorov complexity
There is nothing wrong with your argument, but there is no contradiction. You prove that from some large enough $N$ the Kolmogorov complexity of the spectrum of $f_n$ is always at least $T$. But this statement is trivially true! Although we cannot prove that the Kolmogorov complexity of one string is large, if we have a sequence, then from some point it must contain only strings of large complexity. So what is this $N$ that you got? It must satisfy $N&gt;g^{-1}(c \cdot BB(T))$, what is a number that we cannot compute (because of $BB$), so there is no problem at all.