Randomness and lowness notions via open covers

One of the main lines of research in algorithmic randomness is that of lowness notions. Given a randomness notion ℛℛ, we ask for which sequences AA does relativization to AA leave ℛℛ unchanged (i.e., ℛA=ℛℛA=ℛ)? Such sequences are called low for  ℛℛ. This question extends to a pair of randomness notions ℛℛ and SS, where SS is weaker: for which AA is SASA still weaker than ℛℛ? In the last few years, many results have characterized the sequences that are low for randomness by their low computational strength. A few results have also given measure-theoretic characterizations of low sequences. For example, Kjos-Hanssen (following Kučera) proved that AA is low for Martin-Löf randomness if and only if every AA-c.e. open set of measure less than 1 can be covered by a c.e. open set of measure less than 1.In this paper, we give a series of results showing that a wide variety of lowness notions can be expressed in a similar way, i.e., via the ability to cover open sets of a certain type by open sets of some other type. This provides a unified framework that clarifies the study of lowness for randomness notions, and allows us to give simple proofs of a number of known results. We also use this framework to prove new results, including showing that the classes Low(MLR,SR) and Low(W2R,SR) coincide, answering a question of Nies. Other applications include characterizations of highness notions, a broadly applicable explanation for why low for randomness is the same as low for tests, and a simple proof that Low(W2R,S)=Low(MLR,S), where SS is the class of Martin-Löf, computable, or Schnorr random sequences.The final section gives characterizations of lowness notions using summable functions and convergent measure machines instead of open covers. We finish with a simple proof of a result of Nies, that Low(MLR)=Low(MLR,CR).

► A unified approach to lowness for pairs of randomness notions via open covers. ► A characterization of the class Low(Weak-2-random, Schnorr random). ► A simplified proof of Low(Weak-2-random, Computably random)=Low(ML-random).