Multiple Recurrence and Algorithmic Randomness

MaRDI QIDQ6272530zbMATH OpenFDO

Authors Rodney G. Downey, S. Nandakumar, André Nies

Publication date 14 April 2016

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Ergodic theorems, spectral theory, Markov operators (37A30)

Abstract: This work contributes to the programme of studying effective versions of "almost everywhere" theorems in analysis and ergodic theory via algorithmic randomness. We determine the level of randomness needed for a point in a Cantor space ${0,1}^{NN}$ with the uniform measure and the usual shift so that effective versions of the multiple recurrence theorem of Furstenberg holds for iterations starting at the point. We consider recurrence into closed sets that possess various degrees of effectiveness: clopen, $PPI$ with computable measure, and $PPI$. The notions of Kurtz, Schnorr, and ML randomness, respectively, turn out to be sufficient. We obtain similar results for multiple recurrence with respect to the $k$ commuting shift operators on ${0,1}^{N{N}^{ormalsizek}}$.

This page was built for publication: Multiple Recurrence and Algorithmic Randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6272530)