On initial segment complexity and degrees of randomness

One approach to understanding the. ne structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define X <=(K) Y to mean that (for all n) K( X vertical bar n) <= K(Y vertical bar n) + O( 1). The equivalence classes under this relation are the K-degrees. We prove that if X circle plus Y is 1-random, then X and Y have no upper bound in the K-degrees (hence, no join). We also prove that n-randomness is closed upward in the K-degrees. Our main tool is another structure intended to measure the degree of randomness of real numbers: the nu L-degrees. Unlike the K-degrees, many basic properties of the nu L-degrees are easy to prove. We show that X <=(K) Y implies X <=(nu L) Y, so some results can be transferred. The reverse implication is proved to fail. The same analysis is also done for <=(C), the analogue of <=(K) for plain Kolmogorov complexity. Two other interesting results are included. First, we prove that for any Z is an element of 2(omega), a 1-random real computable from a 1-Z-random real is automatically 1-Z-random. Second, we give a plain Kolmogorov complexity characterization of 1-randomness. This characterization is related to our proof that X <=(C) Y implies X <=(nu L) Y.