An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if the prefix-free Kolmogorov complexity of each initial segment of X is the same as the complexity of the sequence of 0s of the same length, up to a constant. We study the gap between the minimum complexity K(0 n ) and the initial segment complexity of a nontrivial sequence, and in particular the nondecreasing unbounded functions f such that ⋆ for a nontrivial sequence X, where K denotes the prefix-free complexity. Our first result is that there exists a unbounded nondecreasing function f which does not have this property. It is known that such functions cannot be hence this is an optimal bound on their arithmetical complexity. Moreover it improves the bound that was known from Csima and Montalbán (Proc. Amer. Math. Soc. 134(5):1499–1502, 2006).
Our second result is that if f is then there exists a non-empty class of reals X with nontrivial prefix-free complexity which satisfy (⋆). This implies that in this case there uncountably many nontrivial reals X satisfying (⋆) in various well known classes from computability theory and algorithmic randomness; for example low for Ω, non-low for Ω and computably dominated reals. A special case of this result was independently obtained by Bienvenu, Merkle and Nies (STACS, pp. 452–463, 2011).