-
Previous Article
Classification of Rauzy classes in the moduli space of Abelian and quadratic differentials
- DCDS Home
- This Issue
-
Next Article
Computation of rotation numbers for a class of PL-circle homeomorphisms
Inverting the Furstenberg correspondence
1. | Departments of Philosophy and Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, United States |
We draw conclusions for computable measure theory, and show, in particular, that given any computable shift-invariant measure on $2^N$, there is a computable element of $2^N$ that is generic for the measure. We also consider a generalization of the correspondence principle to countable discrete amenable groups, and once again provide an effective inverse.
References:
[1] |
Jeremy Avigad, Uncomputably noisy ergodic limits, Notre Dame Journal of Formal Logic, to appear. |
[2] |
Jeremy Avigad, Philipp Gerhardy and Henry Towsner, Local stability of ergodic averages, Trans. Amer. Math. Soc., 362 (2010), 261-288.
doi: 10.1090/S0002-9947-09-04814-4. |
[3] |
Vitaly Bergelson, Ergodic theory and Diophantine problems, in "Topics in Symbolic Dynamics and Applications" (eds. F. Blanchard, A. Maass and A. Nogueira), London Math. Soc. Lecture Note Ser., 279, Cambridge Univ. Press, Cambridge, (2000), 167-205. |
[4] |
Vitaly Bergelson and Hillel Furstenberg, WM groups and Ramsey theory, Topology Appl., 156 (2009), 2572-2580.
doi: 10.1016/j.topol.2009.04.007. |
[5] |
Vitaly Bergelson, Hillel Furstenberg and Benjamin Weiss, Piecewise-Bohr sets of integers and combinatorial number theory, in "Topics in Discrete Mathematics" (eds. M. Klazar, et al.), Algorithms Combin., 26, Springer, Berlin, (2006), 13-37. |
[6] |
Vitaly Bergelson, Alexander Leibman and Emmanuel Lesigne, Complexities of finite families of polynomials, Weyl systems, and constructions in combinatorial number theory, J. Anal. Math., 103 (2007), 47-92.
doi: 10.1007/s11854-008-0002-z. |
[7] |
Vitaly Bergelson and Randall McCutcheon, Recurrence for semigroup actions and a non-commutative Schur theorem, in "Topological Dynamics and Applications" (eds. M. G. Nerurkar, D. P. Dokken and D. B. Ellis) (Minneapolis, MN, 1995), Contemp. Math., 215, Amer. Math. Soc., Providence, RI, (1998), 205-222. |
[8] |
Vasco Brattka, Peter Hertling and Klaus Weihrauch, A tutorial on computable analysis, in "New Computational Paradigms: Changing Conceptions of What is Computable" (eds. S. Barry Cooper, Benedikt Löwe and Andrea Sorbi), Springer, New York, (2008), 425-491. |
[9] |
C. M. Colebrook, The Hausdorff dimension of certain sets of nonnormal numbers, Michigan Math. J., 17 (1970), 103-116.
doi: 10.1307/mmj/1029000420. |
[10] |
H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math., 31 (1977), 204-256.
doi: 10.1007/BF02813304. |
[11] |
H. Furstenberg, "Recurrence in Ergodic Theory and Combinatorial Number Theory," M. B. Porter Lectures, Princeton University Press, Princeton, N.J., 1981. |
[12] |
Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties, Theor. Comput. Sci., 410 (2009), 2207-2222.
doi: 10.1016/j.tcs.2009.02.010. |
[13] |
Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems, in "Proceedings of Computability and Complexity in Analysis (CCA)'' (eds. Xizhong Zheng and Ning Zhong), Electronic Proceedings in Theoretical Computer Science, arXiv:1006.0392. |
[14] |
Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, Dynamical systems, simulation, abstract computation, 2011, arXiv:1101.0833. |
[15] |
Andrzej Grzegorczyk, On the definitions of computable real continuous functions, Fundamenta Mathematicae, 44 (1957), 61-71. |
[16] |
Bernard Host and Bryna Kra, Uniformity seminorms on ℓ$^\infty$ and applications, J. Anal. Math., 108 (2009), 219-276.
doi: 10.1007/s11854-009-0024-1. |
[17] |
Mathieu Hoyrup, Randomness and the ergodic decomposition, in "Computability in Europe (CiE) 2011" (eds. Benedikt Löwe, et al.), Springer, Berlin, (2011), 122-131. |
[18] |
Mathieu Hoyrup and Cristóbal Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. and Comput., 207 (2009), 830-847.
doi: 10.1016/j.ic.2008.12.009. |
[19] |
Anatole Katok and Boris Hasselblatt, "Introduction to the Modern Theory of Dynamical Systems," With a supplementary chapter by Katok and Leonardo Mendoza, Encyclopedia of Mathematics and its Applications, 54, Cambridge Univ. Press, Cambridge, 1995. |
[20] |
Alexander P. Kreuzer, The cohesive principle and the Bolzano-Weierstraß principle, Math. Log. Q., 57 (2011), 292-298.
doi: 10.1002/malq.201010008. |
[21] |
Pavol Safarik and Ulrich Kohlenbach, On the computational content of the Bolzano-Weierstraß principle, Math. Log. Q., 56 (2010), 508-532.
doi: 10.1002/malq.200910106. |
[22] |
Karl Sigmund, Generic properties of invariant measures for Axiom A diffeomorphisms, Invent. Math., 11 (1970), 99-109.
doi: 10.1007/BF01404606. |
[23] |
Karl Sigmund, On dynamical systems with the specification property, Trans. Amer. Math. Soc., 190 (1974), 285-299.
doi: 10.1090/S0002-9947-1974-0352411-X. |
[24] |
Terence Tao, Norm convergence of multiple ergodic averages for commuting transformations, Ergodic Theory Dynam. Systems, 28 (2008), 657-688.
doi: 10.1017/S0143385708000011. |
[25] |
Terence Tao, "Poincaré's Legacies, Pages from Year Two of a Mathematical Blog," Part I, Amer. Math. Soc., Providence, RI, 2009. |
[26] |
Henry Townser, A general correspondence between averages and integrals, arXiv:0804.2773. |
[27] |
V. V. V'yugin, Ergodic convergence in probability, and an ergodic theorem for individual random sequences, Teor. Veroyatnost. i Primenen., 42 (1997), 35-50; translation in Theory Probab. Appl. 42 (1997), 39-50. |
[28] |
V. V. V'yugin, Ergodic theorems for individual random sequences, Theoret. Comput. Sci., 207 (1998), 343-361.
doi: 10.1016/S0304-3975(98)00072-3. |
[29] |
Klaus Weihrauch, Computability on the probability measures on the Borel sets of the unit interval, Theoret. Comput. Sci., 219 (1999), 421-437.
doi: 10.1016/S0304-3975(98)00298-9. |
show all references
References:
[1] |
Jeremy Avigad, Uncomputably noisy ergodic limits, Notre Dame Journal of Formal Logic, to appear. |
[2] |
Jeremy Avigad, Philipp Gerhardy and Henry Towsner, Local stability of ergodic averages, Trans. Amer. Math. Soc., 362 (2010), 261-288.
doi: 10.1090/S0002-9947-09-04814-4. |
[3] |
Vitaly Bergelson, Ergodic theory and Diophantine problems, in "Topics in Symbolic Dynamics and Applications" (eds. F. Blanchard, A. Maass and A. Nogueira), London Math. Soc. Lecture Note Ser., 279, Cambridge Univ. Press, Cambridge, (2000), 167-205. |
[4] |
Vitaly Bergelson and Hillel Furstenberg, WM groups and Ramsey theory, Topology Appl., 156 (2009), 2572-2580.
doi: 10.1016/j.topol.2009.04.007. |
[5] |
Vitaly Bergelson, Hillel Furstenberg and Benjamin Weiss, Piecewise-Bohr sets of integers and combinatorial number theory, in "Topics in Discrete Mathematics" (eds. M. Klazar, et al.), Algorithms Combin., 26, Springer, Berlin, (2006), 13-37. |
[6] |
Vitaly Bergelson, Alexander Leibman and Emmanuel Lesigne, Complexities of finite families of polynomials, Weyl systems, and constructions in combinatorial number theory, J. Anal. Math., 103 (2007), 47-92.
doi: 10.1007/s11854-008-0002-z. |
[7] |
Vitaly Bergelson and Randall McCutcheon, Recurrence for semigroup actions and a non-commutative Schur theorem, in "Topological Dynamics and Applications" (eds. M. G. Nerurkar, D. P. Dokken and D. B. Ellis) (Minneapolis, MN, 1995), Contemp. Math., 215, Amer. Math. Soc., Providence, RI, (1998), 205-222. |
[8] |
Vasco Brattka, Peter Hertling and Klaus Weihrauch, A tutorial on computable analysis, in "New Computational Paradigms: Changing Conceptions of What is Computable" (eds. S. Barry Cooper, Benedikt Löwe and Andrea Sorbi), Springer, New York, (2008), 425-491. |
[9] |
C. M. Colebrook, The Hausdorff dimension of certain sets of nonnormal numbers, Michigan Math. J., 17 (1970), 103-116.
doi: 10.1307/mmj/1029000420. |
[10] |
H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math., 31 (1977), 204-256.
doi: 10.1007/BF02813304. |
[11] |
H. Furstenberg, "Recurrence in Ergodic Theory and Combinatorial Number Theory," M. B. Porter Lectures, Princeton University Press, Princeton, N.J., 1981. |
[12] |
Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties, Theor. Comput. Sci., 410 (2009), 2207-2222.
doi: 10.1016/j.tcs.2009.02.010. |
[13] |
Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems, in "Proceedings of Computability and Complexity in Analysis (CCA)'' (eds. Xizhong Zheng and Ning Zhong), Electronic Proceedings in Theoretical Computer Science, arXiv:1006.0392. |
[14] |
Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, Dynamical systems, simulation, abstract computation, 2011, arXiv:1101.0833. |
[15] |
Andrzej Grzegorczyk, On the definitions of computable real continuous functions, Fundamenta Mathematicae, 44 (1957), 61-71. |
[16] |
Bernard Host and Bryna Kra, Uniformity seminorms on ℓ$^\infty$ and applications, J. Anal. Math., 108 (2009), 219-276.
doi: 10.1007/s11854-009-0024-1. |
[17] |
Mathieu Hoyrup, Randomness and the ergodic decomposition, in "Computability in Europe (CiE) 2011" (eds. Benedikt Löwe, et al.), Springer, Berlin, (2011), 122-131. |
[18] |
Mathieu Hoyrup and Cristóbal Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. and Comput., 207 (2009), 830-847.
doi: 10.1016/j.ic.2008.12.009. |
[19] |
Anatole Katok and Boris Hasselblatt, "Introduction to the Modern Theory of Dynamical Systems," With a supplementary chapter by Katok and Leonardo Mendoza, Encyclopedia of Mathematics and its Applications, 54, Cambridge Univ. Press, Cambridge, 1995. |
[20] |
Alexander P. Kreuzer, The cohesive principle and the Bolzano-Weierstraß principle, Math. Log. Q., 57 (2011), 292-298.
doi: 10.1002/malq.201010008. |
[21] |
Pavol Safarik and Ulrich Kohlenbach, On the computational content of the Bolzano-Weierstraß principle, Math. Log. Q., 56 (2010), 508-532.
doi: 10.1002/malq.200910106. |
[22] |
Karl Sigmund, Generic properties of invariant measures for Axiom A diffeomorphisms, Invent. Math., 11 (1970), 99-109.
doi: 10.1007/BF01404606. |
[23] |
Karl Sigmund, On dynamical systems with the specification property, Trans. Amer. Math. Soc., 190 (1974), 285-299.
doi: 10.1090/S0002-9947-1974-0352411-X. |
[24] |
Terence Tao, Norm convergence of multiple ergodic averages for commuting transformations, Ergodic Theory Dynam. Systems, 28 (2008), 657-688.
doi: 10.1017/S0143385708000011. |
[25] |
Terence Tao, "Poincaré's Legacies, Pages from Year Two of a Mathematical Blog," Part I, Amer. Math. Soc., Providence, RI, 2009. |
[26] |
Henry Townser, A general correspondence between averages and integrals, arXiv:0804.2773. |
[27] |
V. V. V'yugin, Ergodic convergence in probability, and an ergodic theorem for individual random sequences, Teor. Veroyatnost. i Primenen., 42 (1997), 35-50; translation in Theory Probab. Appl. 42 (1997), 39-50. |
[28] |
V. V. V'yugin, Ergodic theorems for individual random sequences, Theoret. Comput. Sci., 207 (1998), 343-361.
doi: 10.1016/S0304-3975(98)00072-3. |
[29] |
Klaus Weihrauch, Computability on the probability measures on the Borel sets of the unit interval, Theoret. Comput. Sci., 219 (1999), 421-437.
doi: 10.1016/S0304-3975(98)00298-9. |
[1] |
Dubi Kelmer. Approximation of points in the plane by generic lattice orbits. Journal of Modern Dynamics, 2017, 11: 143-153. doi: 10.3934/jmd.2017007 |
[2] |
Jon Chaika, Howard Masur. There exists an interval exchange with a non-ergodic generic measure. Journal of Modern Dynamics, 2015, 9: 289-304. doi: 10.3934/jmd.2015.9.289 |
[3] |
Aihua Fan, Lingmin Liao, Jacques Peyrière. Generic points in systems of specification and Banach valued Birkhoff ergodic average. Discrete and Continuous Dynamical Systems, 2008, 21 (4) : 1103-1128. doi: 10.3934/dcds.2008.21.1103 |
[4] |
Thomas Dauer, Marlies Gerber. Generic absence of finite blocking for interior points of Birkhoff billiards. Discrete and Continuous Dynamical Systems, 2016, 36 (9) : 4871-4893. doi: 10.3934/dcds.2016010 |
[5] |
Vieri Benci, C. Bonanno, Stefano Galatolo, G. Menconi, M. Virgilio. Dynamical systems and computable information. Discrete and Continuous Dynamical Systems - B, 2004, 4 (4) : 935-960. doi: 10.3934/dcdsb.2004.4.935 |
[6] |
Tao Yu. Measurable sensitivity via Furstenberg families. Discrete and Continuous Dynamical Systems, 2017, 37 (8) : 4543-4563. doi: 10.3934/dcds.2017194 |
[7] |
Salvador Addas-Zanata. A simple computable criteria for the existence of horseshoes. Discrete and Continuous Dynamical Systems, 2007, 17 (2) : 365-370. doi: 10.3934/dcds.2007.17.365 |
[8] |
Fei Liu, Fang Wang, Weisheng Wu. On the Patterson-Sullivan measure for geodesic flows on rank 1 manifolds without focal points. Discrete and Continuous Dynamical Systems, 2020, 40 (3) : 1517-1554. doi: 10.3934/dcds.2020085 |
[9] |
Jian Li. Localization of mixing property via Furstenberg families. Discrete and Continuous Dynamical Systems, 2015, 35 (2) : 725-740. doi: 10.3934/dcds.2015.35.725 |
[10] |
Feng-mei Tao, Lan-sun Chen, Li-xian Xia. Correspondence analysis of body form characteristics of Chinese ethnic groups. Discrete and Continuous Dynamical Systems - B, 2004, 4 (3) : 769-776. doi: 10.3934/dcdsb.2004.4.769 |
[11] |
Alexander Gomilko, Mariusz Lemańczyk, Thierry de la Rue. On Furstenberg systems of aperiodic multiplicative functions of Matomäki, Radziwiłł, and Tao. Journal of Modern Dynamics, 2021, 17: 529-555. doi: 10.3934/jmd.2021018 |
[12] |
Will Brian, Jonathan Meddaugh, Brian Raines. Shadowing is generic on dendrites. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2211-2220. doi: 10.3934/dcdss.2019142 |
[13] |
Serge Troubetzkoy. Recurrence in generic staircases. Discrete and Continuous Dynamical Systems, 2012, 32 (3) : 1047-1053. doi: 10.3934/dcds.2012.32.1047 |
[14] |
Neal Koblitz, Alfred Menezes. Another look at generic groups. Advances in Mathematics of Communications, 2007, 1 (1) : 13-28. doi: 10.3934/amc.2007.1.13 |
[15] |
Zoltán Buczolich, Balázs Maga, Ryo Moore. Generic Birkhoff spectra. Discrete and Continuous Dynamical Systems, 2020, 40 (12) : 6649-6679. doi: 10.3934/dcds.2020131 |
[16] |
Frédéric Naud. The Ruelle spectrum of generic transfer operators. Discrete and Continuous Dynamical Systems, 2012, 32 (7) : 2521-2531. doi: 10.3934/dcds.2012.32.2521 |
[17] |
Ian D. Morris. Ergodic optimization for generic continuous functions. Discrete and Continuous Dynamical Systems, 2010, 27 (1) : 383-388. doi: 10.3934/dcds.2010.27.383 |
[18] |
Mário Jorge Dias Carneiro, Alexandre Rocha. A generic property of exact magnetic Lagrangians. Discrete and Continuous Dynamical Systems, 2012, 32 (12) : 4183-4194. doi: 10.3934/dcds.2012.32.4183 |
[19] |
Welington Cordeiro, Manfred Denker, Xuan Zhang. On specification and measure expansiveness. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 1941-1957. doi: 10.3934/dcds.2017082 |
[20] |
Welington Cordeiro, Manfred Denker, Xuan Zhang. Corrigendum to: On specification and measure expansiveness. Discrete and Continuous Dynamical Systems, 2018, 38 (7) : 3705-3706. doi: 10.3934/dcds.2018160 |
2021 Impact Factor: 1.588
Tools
Metrics
Other articles
by authors
[Back to Top]