Multiple Recurrence and Algorithmic Randomness

2016/04/14 by Rodney G. Downey, Downey, Rodney G., Satyadev Nandakumar +3
Computer Science · Mathematics · #03D32 #37A30 #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Dynamical Systems (math.DS) #FOS: Mathematics #Logic (math.LO) #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1604.04230

openalex publication_date 2016/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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\^\NN^{\normalsize k}.

Citations

• On Computable Numbers, with an Application to the Entscheidungsproblem

Related

• Sets of k-recurrence but not (k+1)-recurrence
• Multiple recurrence and the structure of probability-preserving systems
• Randomness and Non-ergodic Systems
• Ergodic theorems for algorithmically random points
• On the close interaction between algorithmic randomness and constructive/computable measure theory