Algorithmic Randomness Interacts with Analysis and Ergodic Theory (16w5072)

Arriving in Oaxaca, Mexico Sunday, December 4 and departing Friday December 9, 2016


(Carnegie Mellon University)

(University of Wisconsin–Madison)

(The University of Auckland)


The workshop brings together researchers in randomness and reverse mathematics on the one side, and computable analysis and effective ergodic theory on the other side, with the goal of clarifying the connections between these areas and then using them to obtain new information about each area. Currently the researchers are separated both geographically and by their background, to the extent that they sometimes work on closely related topics without knowing of each other. We expect to make progress on topics including the ones discussed below through the new interactions to be fostered between researchers.

Effective ergodic theory. One form of Birkhoff's ergodic theorem says that for a measure preserving operator $T$ and a real valued integrable function $f$ on an appropriate probability space (for instance, Cantor space $2^\mathbb N$), for almost every $x$ the averages of the values $f(T^i(x))$ for $i=0 \ldots n$ converge as $n \to \infty$. Given an effective setting of this theorem, how much randomness of $x$ is necessary to ensure this convergence? Combining results of V'yugin (Teor. Veroyatnost. i Primenen, 1997) and Franklin and Towsner (Moscow J. Math., to appear) settles an important case, where $f$ is lower semi-computable and $T$ is ergodic: the randomness notion describing convergence is Martin-Löf's. This leave open the case that $f$ is lower semi-computable and $T$ is merely measure-preserving. Recently Miyabe, Nies, and Zhang showed that a randomness notion slightly stronger than Martin-Löf's is sufficient in this case. One conjecture is that density randomness is the right strength here. An intermediate case due to Hoyrup is given by a “nearly ergodic” computable operator $T$, which decomposes into a finite number of ergodic operators. Hoyrup (Ann. Pure and Applied Logic, 2013) has shown that these components are not necessarily computable.

Adam Day has recently given a new proof, using descriptive string (i.e., Kolmogorov) complexity, of a theorem due to Kolmogorov and Sinai independently: two isomorphic ergodic systems have the same entropy. This is only one example of new interactions between Kolmogorov complexity and ergodic theory. They will be further explored at the workshop.

A considerable part of effective analysis is based on feasible computability, which means that the relevant objects are realistically computable, usually with polynomial time bounds. Recently Nies (Proc. of STACS 2014), and independently Kawamura and Miyabe, obtained the analog of the above-mentioned Brattka-Miller-Nies result in the feasible setting: a real $z$ is polynomial time random if and only if each polynomial time computable function is differentiable at $z$. Feasible ergodic theory, on the other hand, appears to be untouched. The interaction at the workshop between experts on feasible analysis and on ergodic theory is auspicious.

Algorithmic randomness and effective rates of convergence. The workshop will address the extent to which convergence theorems in analysis have effective rates of convergence. For a computable sequence of measurable functions, a suitably effective rate of convergence implies that these functions converge pointwise on algorithmically random inputs. This provides a further link between algorithmic randomness and computable analysis, and brings the study of effective rates of convergence in ergodic theorems, martingale convergence theorems, and so on to bear on questions in algorithmic randomness. See for instance work of Avigad and Rute (Ergod. Th. and Dynam. Sys., to appear), and Kohlenbach and Leuştean (Adv. in Mathematics, 2012).

Random closed sets and energy randomness. Barmpalias et al. (Journal of Logic and Computation 17, 2007) studied the following question: which reals can be points of random closed sets? Diamondstone and Kjos-Hanssen (Ann. Pure Applied Logic 163, 2012) related the question to Galton-Watson processes. This led them to effectivize a notion from probability, which itself was appropriated from mathematical physics. Call a real energy $s$-random if it is random for some measure $\mu$ with finite Riesz $s$-energy. Diamondstone and Kjos-Hanssen showed that energy $s$-randomness for the appropriate dimension $s$ implies being a point of a random close set; they conjectured equivalence. Rute proved their conjecture, and also showed that the same notion (with a different dimension parameter) characterizes the zeros of Martin-Löf random Brownian motions. This completed work started by Allen, Bienvenu, and Slaman (arXiv:1405.6312, 2014).

In a very recent development, Miller and Rute (arXiv:1509.00524)
have given a natural characterization of energy $s$-randomness in terms of Levin's a priori complexity. Similar to other directions in the proposal, this shows a strong connection between notions imported from classical mathematics and those native to algorithmic randomness.

Reverse mathematics and randomness. Let $\mathtt{RCA}$ denote the usual “base theory”, given by the axiom system stating some basic properties of the natural numbers, a certain amount of induction, and, essentially, the existence of all computable sets. Let $\mathcal C$ denote a randomness notion. At the workshop we plan to study the strength of the system $\mathtt{RCA}$ together with the statement that for each oracle $X$ there is a bit sequence $Y$ that is random relative to $X$ in the sense of $\mathcal C$. For ML-randomness, the resulting principle is very weak Königs Lemma $\mathtt{WWKL}$. For the stronger notion of 2-randomness, the corresponding principle has been recently studied by Avigad, Dean, and Rute (Ann. Pure and Applied Logic, 2012). Interestingly, the systems corresponding to different randomness notions can be equivalent. For instance, this is the case for computable randomness versus Schnorr randomness. On the other hand, analytic notions such as differentiability can be used to separate such axioms. We will in particular consider notions slightly stronger than Martin-Löf randomness. The system for difference randomness (that is, Martin-Löf random not computing the halting problem) is equivalent to $\mathtt{WWKL}$, while the system for weak 2-randomness strictly implies $\mathtt{WWKL}$. It would be interesting to determine the dividing line. Understanding the effective content of theorems on topological dynamics can also determine the strength of the classical theorems in reverse mathematics. For instance, Adam Day has recently used this idea to show that another theorem due to Birkhoff, on the existence of almost periodic points, is strictly in between a system called arithmetic comprehension and weak König's lemma $\mathtt{WKL}$. This theorem was proved in the special setting of a continuous operator on Cantor space - the strength of Birkhoff's result for continuous operators on other compact spaces remains open.

Density randomness. Let us call a Martin-Löf random real $z$ density random if every effectively closed set containing $z$ has density one at $z$. Density randomness has been characterized in multiple ways by using effective versions of other well-known “almost everywhere” theorems due to Lebesgue; for instance, Miyabe, Nies, and Zhang (2014) characterized it as the points where the Lebesgue differentiation theorem holds for lower semi-computable functions. On the other hand, no characterization purely in terms of computational complexity is known; in particular, we do not know whether for a Martin-Löf random set, density randomness is equivalent to not computing all the far-from-random (i.e., K-trivial) sets.

Porosity is an important geometric concept that arises frequently when one studies sets of differentiability of a function. We say that a class $P \subseteq \mathbb R$ is porous at a real $z$ if arbitrary short intervals $I$ around $z$ have a subinterval $L$, of size a fixed fraction of the size of $I$, such that $L \cap P = \emptyset$; $z$ is a non-porosity point if no effectively closed class $P$ containing $z$ is porous at $z$. Clearly each density random point is a non-porosity point. Bienvenu, Hölzl, Miller, and Nies (J. Math. Logic, 2014) relate porosity to complexity: a Turing incomplete random real is a non-porosity point for all effectively closed $P$. Many related questions, such as the converse of their result, remain open.

Combining density with the cost function method (see e.g. Nies, Computability and Randomness, OUP, 2009) has recently allowed Greenberg, Miller, and Nies to understand subclasses of the far-from random sets. They proved that a c.e. set is below both halves of some Martin-Löf random oracle if and only if it obeys the cost function $c(x,s) = \sqrt{\Omega_s- \Omega_x}$, where $\Omega_t$ is the state of Chaitin's halting probability at stage $t$. Intuitively, obedience to $c$ means that few numbers can be enumerated into the set, because the total cost of enumerations has to be kept finite; $c(x,s)$ defines the cost of putting $x$ as a least element into the set at a stage $s>x$.