I have (very) recently gotten into the study of algorithmic randomness, and figure that airing some things out here on the blog might do me some good. I will not be providing an in-depth introduction to the fundamentals of the area here. What I will do in this post is give some basic definitions, and spell out the statement of one recent example from the field, for the sake of illustrating the kind of work that I am interested in.

First of all, let’s consider an example of a classical measure-theoretic result. Suppose we have an integrable function . We call a point a Lebesgue point of provided that

where here is the Lebesgue measure, and the limit is over cubes shrinking down to . This terminology is due to the classical

Lebesgue Differentiation Theorem. Let be an integrable function. Then almost every point is a Lebesgue point of .

To say that “almost every” point is a Lebesgue point is to say that the set of Lebesgue points has measure . Recently, Pathak proved a version of the Lebesgue differentiation theorem in the spirit of algorithmic randomness. Her result follows a pattern that has been seen before, e.g. in V’yugin: (1) take some probabilistic or measure-theoretic result that holds almost everywhere, (2) add some computability-related hypothesis, (3) conclude that the result in fact holds for every Martin-Löf random point in the space.

OK, fine. So what is a Martin-Löf random point? To answer that, let’s consider a fuzzy moral question: what should count as a “random” element in our measure space? We might say that a random point shouldn’t be too special; so we might make this try:

Attempted Definition. A random point in a measure space is one that doesn’t satisfy any properties of measure , i.e. it is not contained in any null set.

This runs into the problem that, well, for any . Martin-Löf’s 1966 definition is based on the same general idea, but it gives an account of randomness that can be satisfied and turns out to have all sorts of interesting interactions with computability theory:

Definition. A random point is one that isn’t contained in any effectively null set.

Definition. An effectively null set is one of the form

where is a sequence of uniformly effectively open sets, for which for all .

Definition. A set is effectively open if it is a union of balls

with a computably enumerable subset of .

Basically, the sets narrow in on the null set in an effective manner. Any point in the space that cannot be pinned down in such an effectively null is what we call a Martin-Löf random point.

Alright, so returning to Pathak’s version of the Lebesgue differentiation theorem, what is her additional hypothesis? She restricts attention to functions that are not just integrable, but also:

Definition. A function is -computable if there is a computable sequence of polynomials such that

for all .

So, we only consider that can be effectively approximated by polynomials in the -norm. Pathak’s result is then:

Theorem. If is -computable, then every Martin-Löf random point is a Lebesgue point for .

I have put up some rough working notes in the Miscellania section of my web page that situate Pathak’s result in a conceptual framework developed by Mathieu Hoyrup and Cristóbal Rojas for working with algorithmic randomness in spaces other than Cantor space (where classical computability theory lives). Their work brings a unifying, systematic approach to results like Pathak’s and V’yugin’s (linked to above). I wrote the notes for my own benefit, as a way to get clear on some of the structure and details of the papers I’ve been talking about; perhaps someone else might find them helpful too.