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]

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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - B, 2004, 4 (4) : 935-960. doi: 10.3934/dcdsb.2004.4.935
[6]

Salvador Addas-Zanata. A simple computable criteria for the existence of horseshoes. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 365-370. doi: 10.3934/dcds.2007.17.365
[7]

Tao Yu. Measurable sensitivity via Furstenberg families. Discrete & Continuous Dynamical Systems - A, 2017, 37 (8) : 4543-4563. doi: 10.3934/dcds.2017194
[8]

Jian Li. Localization of mixing property via Furstenberg families. Discrete & Continuous Dynamical Systems - A, 2015, 35 (2) : 725-740. doi: 10.3934/dcds.2015.35.725
[9]

Feng-mei Tao, Lan-sun Chen, Li-xian Xia. Correspondence analysis of body form characteristics of Chinese ethnic groups. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 769-776. doi: 10.3934/dcdsb.2004.4.769
[10]

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
[11]

Serge Troubetzkoy. Recurrence in generic staircases. Discrete & Continuous Dynamical Systems - A, 2012, 32 (3) : 1047-1053. doi: 10.3934/dcds.2012.32.1047
[12]

Will Brian, Jonathan Meddaugh, Brian Raines. Shadowing is generic on dendrites. Discrete & Continuous Dynamical Systems - S, 2019, 12 (8) : 2211-2220. doi: 10.3934/dcdss.2019142
[13]

Frédéric Naud. The Ruelle spectrum of generic transfer operators. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2521-2531. doi: 10.3934/dcds.2012.32.2521
[14]

Ian D. Morris. Ergodic optimization for generic continuous functions. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 383-388. doi: 10.3934/dcds.2010.27.383
[15]

Mário Jorge Dias Carneiro, Alexandre Rocha. A generic property of exact magnetic Lagrangians. Discrete & Continuous Dynamical Systems - A, 2012, 32 (12) : 4183-4194. doi: 10.3934/dcds.2012.32.4183
[16]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[17]

Welington Cordeiro, Manfred Denker, Xuan Zhang. On specification and measure expansiveness. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 1941-1957. doi: 10.3934/dcds.2017082
[18]

Welington Cordeiro, Manfred Denker, Xuan Zhang. Corrigendum to: On specification and measure expansiveness. Discrete & Continuous Dynamical Systems - A, 2018, 38 (7) : 3705-3706. doi: 10.3934/dcds.2018160
[19]

Petr Kůrka. On the measure attractor of a cellular automaton. Conference Publications, 2005, 2005 (Special) : 524-535. doi: 10.3934/proc.2005.2005.524
[20]

Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741

2018 Impact Factor: 1.143

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences