On the gap between trivial and nontrivial initial segment prefix-free complexity Martijn Baartse, George Barmpalias Abstract: An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if K(X~n) ~+ K(0^n) for all n, where K is the prefix-free complexity and ~+ denotes inequality modulo a constant. In other words, if the information in any initial segment of it is merely the information in a sequence of 0s of the same length. We study the gap between the trivial com- plexity K(0^n) and the complexity of a non-trivial sequence, i.e. the functions f such that (*) K(X~n) ~+ K(0^n) + f (n) for all n for a non-trivial (in terms of initial segment complexity) sequence X. We show that given any ~^0_2 unbounded non-decreasing function f there exist uncountably many sequences X which satisfy (*). On the other hand there exists a ~^0_3 unbounded non-decreasing function f which does not satisfy (*) for any X with non-trivial initial segment complexity. This improves the bound ~^0_4 that was known from [CM06]. Finally we give some applications of these results.