American Institute of Mathematical Sciences

Advanced
October  2012, 32(10): 3421-3431. doi: 10.3934/dcds.2012.32.3421

Inverting the Furstenberg correspondence

Jeremy Avigad 1,

1. 

Departments of Philosophy and Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, United States

Received  May 2011 Revised  February 2012 Published  May 2012

Given a sequence of sets $A_n \subseteq \{0,\ldots,n-1\}$, the Furstenberg correspondence principle provides a shift-invariant measure on $2^N$ that encodes combinatorial information about infinitely many of the $A_n$'s. Here it is shown that this process can be inverted, so that for any such measure, ergodic or not, there are finite sets whose combinatorial properties approximate it arbitarily well. The finite approximations are obtained from the measure by an explicit construction, with an explicit upper bound on how large $n$ has to be to yield a sufficiently good approximation.
    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.
Keywords: Furstenberg correspondence, computable measure theory, generic points..
Mathematics Subject Classification: Primary: 37A45; Secondary: 03F6.
Citation: Jeremy Avigad. Inverting the Furstenberg correspondence. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3421-3431. doi: 10.3934/dcds.2012.32.3421
References:
[1]

Jeremy Avigad, Uncomputably noisy ergodic limits,, Notre Dame Journal of Formal Logic, ().   Google Scholar

[2]

Jeremy Avigad, Philipp Gerhardy and Henry Towsner, Local stability of ergodic averages,, Trans. Amer. Math. Soc., 362 (2010), 261.  doi: 10.1090/S0002-9947-09-04814-4.  Google Scholar

[3]

Vitaly Bergelson, Ergodic theory and Diophantine problems,, in, 279 (2000), 167.   Google Scholar

[4]

Vitaly Bergelson and Hillel Furstenberg, WM groups and Ramsey theory,, Topology Appl., 156 (2009), 2572.  doi: 10.1016/j.topol.2009.04.007.  Google Scholar

[5]

Vitaly Bergelson, Hillel Furstenberg and Benjamin Weiss, Piecewise-Bohr sets of integers and combinatorial number theory,, in, 26 (2006), 13.   Google Scholar

[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.  doi: 10.1007/s11854-008-0002-z.  Google Scholar

[7]

Vitaly Bergelson and Randall McCutcheon, Recurrence for semigroup actions and a non-commutative Schur theorem,, in, 215 (1998), 205.   Google Scholar

[8]

Vasco Brattka, Peter Hertling and Klaus Weihrauch, A tutorial on computable analysis,, in, (2008), 425.   Google Scholar

[9]

C. M. Colebrook, The Hausdorff dimension of certain sets of nonnormal numbers,, Michigan Math. J., 17 (1970), 103.  doi: 10.1307/mmj/1029000420.  Google Scholar

[10]

H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions,, J. Analyse Math., 31 (1977), 204.  doi: 10.1007/BF02813304.  Google Scholar

[11]

H. Furstenberg, "Recurrence in Ergodic Theory and Combinatorial Number Theory,", M. B. Porter Lectures, (1981).   Google Scholar

[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.  doi: 10.1016/j.tcs.2009.02.010.  Google Scholar

[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, ().   Google Scholar

[14]

Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, Dynamical systems, simulation, abstract computation,, 2011, ().   Google Scholar

[15]

Andrzej Grzegorczyk, On the definitions of computable real continuous functions,, Fundamenta Mathematicae, 44 (1957), 61.   Google Scholar

[16]

Bernard Host and Bryna Kra, Uniformity seminorms on ℓ$^\infty$ and applications,, J. Anal. Math., 108 (2009), 219.  doi: 10.1007/s11854-009-0024-1.  Google Scholar

[17]

Mathieu Hoyrup, Randomness and the ergodic decomposition,, in, (2011), 122.   Google Scholar

[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.  doi: 10.1016/j.ic.2008.12.009.  Google Scholar

[19]

Anatole Katok and Boris Hasselblatt, "Introduction to the Modern Theory of Dynamical Systems,", With a supplementary chapter by Katok and Leonardo Mendoza, 54 (1995).   Google Scholar

[20]

Alexander P. Kreuzer, The cohesive principle and the Bolzano-Weierstraß principle,, Math. Log. Q., 57 (2011), 292.  doi: 10.1002/malq.201010008.  Google Scholar

[21]

Pavol Safarik and Ulrich Kohlenbach, On the computational content of the Bolzano-Weierstraß principle,, Math. Log. Q., 56 (2010), 508.  doi: 10.1002/malq.200910106.  Google Scholar

[22]

Karl Sigmund, Generic properties of invariant measures for Axiom A diffeomorphisms,, Invent. Math., 11 (1970), 99.  doi: 10.1007/BF01404606.  Google Scholar

[23]

Karl Sigmund, On dynamical systems with the specification property,, Trans. Amer. Math. Soc., 190 (1974), 285.  doi: 10.1090/S0002-9947-1974-0352411-X.  Google Scholar

[24]

Terence Tao, Norm convergence of multiple ergodic averages for commuting transformations,, Ergodic Theory Dynam. Systems, 28 (2008), 657.  doi: 10.1017/S0143385708000011.  Google Scholar

[25]

Terence Tao, "Poincaré's Legacies, Pages from Year Two of a Mathematical Blog," Part I,, Amer. Math. Soc., (2009).   Google Scholar

[26]

Henry Townser, A general correspondence between averages and integrals,, \arXiv{0804.2773}., ().   Google Scholar

[27]

V. V. V'yugin, Ergodic convergence in probability, and an ergodic theorem for individual random sequences,, Teor. Veroyatnost. i Primenen., 42 (1997), 35.   Google Scholar

[28]

V. V. V'yugin, Ergodic theorems for individual random sequences,, Theoret. Comput. Sci., 207 (1998), 343.  doi: 10.1016/S0304-3975(98)00072-3.  Google Scholar

[29]

Klaus Weihrauch, Computability on the probability measures on the Borel sets of the unit interval,, Theoret. Comput. Sci., 219 (1999), 421.  doi: 10.1016/S0304-3975(98)00298-9.  Google Scholar

show all references

References:
[1]

Jeremy Avigad, Uncomputably noisy ergodic limits,, Notre Dame Journal of Formal Logic, ().   Google Scholar

[2]

Jeremy Avigad, Philipp Gerhardy and Henry Towsner, Local stability of ergodic averages,, Trans. Amer. Math. Soc., 362 (2010), 261.  doi: 10.1090/S0002-9947-09-04814-4.  Google Scholar

[3]

Vitaly Bergelson, Ergodic theory and Diophantine problems,, in, 279 (2000), 167.   Google Scholar

[4]

Vitaly Bergelson and Hillel Furstenberg, WM groups and Ramsey theory,, Topology Appl., 156 (2009), 2572.  doi: 10.1016/j.topol.2009.04.007.  Google Scholar

[5]

Vitaly Bergelson, Hillel Furstenberg and Benjamin Weiss, Piecewise-Bohr sets of integers and combinatorial number theory,, in, 26 (2006), 13.   Google Scholar

[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.  doi: 10.1007/s11854-008-0002-z.  Google Scholar

[7]

Vitaly Bergelson and Randall McCutcheon, Recurrence for semigroup actions and a non-commutative Schur theorem,, in, 215 (1998), 205.   Google Scholar

[8]

Vasco Brattka, Peter Hertling and Klaus Weihrauch, A tutorial on computable analysis,, in, (2008), 425.   Google Scholar

[9]

C. M. Colebrook, The Hausdorff dimension of certain sets of nonnormal numbers,, Michigan Math. J., 17 (1970), 103.  doi: 10.1307/mmj/1029000420.  Google Scholar

[10]

H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions,, J. Analyse Math., 31 (1977), 204.  doi: 10.1007/BF02813304.  Google Scholar

[11]

H. Furstenberg, "Recurrence in Ergodic Theory and Combinatorial Number Theory,", M. B. Porter Lectures, (1981).   Google Scholar

[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.  doi: 10.1016/j.tcs.2009.02.010.  Google Scholar

[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, ().   Google Scholar

[14]

Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas, Dynamical systems, simulation, abstract computation,, 2011, ().   Google Scholar

[15]

Andrzej Grzegorczyk, On the definitions of computable real continuous functions,, Fundamenta Mathematicae, 44 (1957), 61.   Google Scholar

[16]

Bernard Host and Bryna Kra, Uniformity seminorms on ℓ$^\infty$ and applications,, J. Anal. Math., 108 (2009), 219.  doi: 10.1007/s11854-009-0024-1.  Google Scholar

[17]

Mathieu Hoyrup, Randomness and the ergodic decomposition,, in, (2011), 122.   Google Scholar

[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.  doi: 10.1016/j.ic.2008.12.009.  Google Scholar

[19]

Anatole Katok and Boris Hasselblatt, "Introduction to the Modern Theory of Dynamical Systems,", With a supplementary chapter by Katok and Leonardo Mendoza, 54 (1995).   Google Scholar

[20]

Alexander P. Kreuzer, The cohesive principle and the Bolzano-Weierstraß principle,, Math. Log. Q., 57 (2011), 292.  doi: 10.1002/malq.201010008.  Google Scholar

[21]

Pavol Safarik and Ulrich Kohlenbach, On the computational content of the Bolzano-Weierstraß principle,, Math. Log. Q., 56 (2010), 508.  doi: 10.1002/malq.200910106.  Google Scholar

[22]

Karl Sigmund, Generic properties of invariant measures for Axiom A diffeomorphisms,, Invent. Math., 11 (1970), 99.  doi: 10.1007/BF01404606.  Google Scholar

[23]

Karl Sigmund, On dynamical systems with the specification property,, Trans. Amer. Math. Soc., 190 (1974), 285.  doi: 10.1090/S0002-9947-1974-0352411-X.  Google Scholar

[24]

Terence Tao, Norm convergence of multiple ergodic averages for commuting transformations,, Ergodic Theory Dynam. Systems, 28 (2008), 657.  doi: 10.1017/S0143385708000011.  Google Scholar

[25]

Terence Tao, "Poincaré's Legacies, Pages from Year Two of a Mathematical Blog," Part I,, Amer. Math. Soc., (2009).   Google Scholar

[26]

Henry Townser, A general correspondence between averages and integrals,, \arXiv{0804.2773}., ().   Google Scholar

[27]

V. V. V'yugin, Ergodic convergence in probability, and an ergodic theorem for individual random sequences,, Teor. Veroyatnost. i Primenen., 42 (1997), 35.   Google Scholar

[28]

V. V. V'yugin, Ergodic theorems for individual random sequences,, Theoret. Comput. Sci., 207 (1998), 343.  doi: 10.1016/S0304-3975(98)00072-3.  Google Scholar

[29]

Klaus Weihrauch, Computability on the probability measures on the Borel sets of the unit interval,, Theoret. Comput. Sci., 219 (1999), 421.  doi: 10.1016/S0304-3975(98)00298-9.  Google Scholar

[1]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[2]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020050
[3]

Harrison Bray. Ergodicity of Bowen–Margulis measure for the Benoist 3-manifolds. Journal of Modern Dynamics, 2020, 16: 305-329. doi: 10.3934/jmd.2020011
[4]

Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217
[5]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458
[6]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051
[7]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024
[8]

Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327
[9]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276
[10]

Russell Ricks. The unique measure of maximal entropy for a compact rank one locally CAT(0) space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 507-523. doi: 10.3934/dcds.2020266

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (29)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences