Pith. sign in

REVIEW 5 minor 44 references

Computable Ergodic Optimisation

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For computable potentials on well-behaved systems, the zero-temperature maximum average is computable and the maximising measures form a Π₁ compact set; on one-dimensional SFTs both are given by a finite-time max-mean-cycle algorithm.

desk verdict Clean, usable transfer of computable-analysis tools to zero-temperature ergodic optimisation, plus a working finite-time algorithm for the SFT case that people actually code. read the letter →

arxiv 2607.11404 v1 pith:6KLLULHT submitted 2026-07-13 math.DS cs.CCcs.LOmath-phmath.MP

Léo Gayral , Mathieu Hoyrup This is my paper · ORCID
classification math.DScs.CCcs.LOmath-phmath.MP MSC 37A5037B1003D7868Q17
keywords ergodicoptimisationzerotemperaturecomputableanalysismaximisingmeasuressubshiftsoffinitetypemaximummeancycleDeBruijngraphdynamicalsystems
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Zero-temperature ergodic optimisation asks which invariant probability measures maximise the long-run average of a continuous potential φ. The paper shows that when the underlying dynamical system is computably compact and its set of invariant measures is computably overt, any computable φ yields a computable maximum average β(φ) and a Π₁-computable compact set of maximising measures. In the concrete setting of one-dimensional subshifts of finite type with finite-range potentials taking values in a field that permits exact arithmetic, both quantities become exactly computable: the maximising support is itself an SFT whose forbidden patterns are recovered by a maximum-mean-cycle algorithm of complexity O(|A|^{3r+1}). The result therefore turns an abstract optimisation problem into an explicit graph-theoretic computation, with a matching open-source implementation.

What carries the argument

The reduction of maximising measures for a finite-range potential to the vertices of a De Bruijn graph that realise the maximum mean cycle weight (via a cohomologous function and Karp-style dynamic programming). This reduction simultaneously computes β(φ) and produces an explicit finite set of forbidden patterns whose SFT is precisely the support of all maximising measures.

What would settle it

Exhibit a computable dynamical system that is computably compact, a computable potential, and a proof that the set of invariant measures is computably overt, yet the maximum ergodic average is not a computable real, or the set of maximising measures is not Π₁.

Watch

Extended reading notes

Core claim

Under the two standing hypotheses that the ambient space is computably compact and that the set of invariant measures is computably overt, the maximum ergodic average of any computable potential is a computable real number and the set of maximising measures is a Π₁ compact subset of the space of measures. On one-dimensional SFTs with finite-range potentials the same objects are obtained exactly, in finite time, by reducing the problem to the maximum mean weight of cycles in a De Bruijn graph.

Load-bearing premise

The set of invariant measures must itself be computably overt; without that density of computable measures the upper bounds on complexity no longer hold, and the paper notes that the property fails for some natural computable maps and is undecidable for general two-dimensional SFTs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies computability properties of zero-temperature ergodic optimisation. For a computable dynamical system (X,T) and computable continuous potential φ, under the hypotheses that X is computably compact and that the set MT(X) of invariant measures is computably overt, Theorem 3.2 shows that the maximum ergodic average β(φ) is a computable real number and that the set Mmax(φ) of maximising measures is a Π1-computable compact subset of M(X). In the special case of one-dimensional subshifts of finite type with finite-range potentials taking values in a computable ordered field F, Section 5 reduces the problem to maximum-mean-weight cycles on the associated De Bruijn graph and supplies an explicit algorithm of complexity O(|A|^{3r+1}) that computes both β(φ) and a finite set of forbidden patterns defining an SFT whose invariant measures are exactly the maximising ones; a matching public code repository is provided.

Significance. The results cleanly transfer standard tools of computable analysis (computable compactness, overtness, and preservation under continuous maps and integration) to the setting of ergodic optimisation, thereby answering the natural zero-temperature counterpart of earlier positive-temperature computability results. The explicit polynomial-time algorithm for finite-range potentials on one-dimensional SFTs, together with working code, is a concrete and immediately usable contribution that goes beyond abstract upper bounds. The paper carefully documents the limitations of the overtness hypothesis, so the scope of the claims is transparent. Overall the work strengthens the bridge between computability theory and thermodynamic formalism.

minor comments (5)
  1. Abstract, first sentence: “physicals systems” is a typographical error for “physical systems”.
  2. Section 2.3, Definition 2.4 and Remark 2.5: the distinction between the paper’s Πk closed sets and the classical effective descriptive-set-theoretic Π0k sets is useful, but a one-sentence pointer to the literature (e.g., Weihrauch or Brattka–Presser) would help readers less familiar with the hierarchy.
  3. Section 5.2, Remark 5.2: the counter-example with λ is clear, yet the subsequent claim that one can still obtain a nested sequence of outer approximations Fn is left somewhat informal; a short explicit statement of the resulting algorithm would improve readability.
  4. Section 5.3: the complexity bound O(|A|^{3r+1}) is stated after the description of the adapted Karp procedure; it would be helpful to isolate the precise arithmetic-operation count (or bit-complexity when F=Q) in a displayed equation or remark.
  5. References: the arXiv identifier of the companion positive-temperature paper [GST25] is missing; adding it would aid readers.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; Theorem 3.2 and the Section 5 algorithm are self-contained applications of standard computable-analysis preservation properties and classical graph algorithms.

full rationale

The derivation chain of Theorem 3.2 applies the general facts of Propositions 2.12–2.15 (computable compactness/overtness of M(X) and MT(X), preservation of max under computable maps) directly to a computable potential φ; those propositions are standard results from the literature (Weihrauch, Hoyrup–Rojas, etc.) and are not redefined in terms of β(φ) or Mmax(φ). The algorithmic claims of Section 5 reduce finite-range maximisation on a 1-D SFT to max-mean-weight cycles on the De Bruijn graph via Bousch’s cohomology (external) and an explicit adaptation of Karp’s algorithm; the reduction (Proposition 5.4, Corollary 5.5) is proved from first principles inside the paper and does not presuppose the output set F. The sole self-citation to the authors’ prior positive-temperature work [GST25] appears only as motivational analogy in the abstract and introduction and is never invoked as a load-bearing uniqueness theorem, ansatz, or uniqueness result. No parameters are fitted to data and later recovered as “predictions,” no quantity is defined in terms of the claimed output, and the supplied code repository independently realises the algorithm. Consequently the claimed computability bounds are not equivalent to their inputs by construction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper works entirely inside classical computable analysis and ergodic theory; the only non-standard ingredients are the two effective hypotheses (computable compactness of X and computable overtness of MT) that delimit the scope of Theorem 3.2, plus the decidability of equality in the coefficient field F required for the exact algorithm.

assumptions (5)
  • domain assumption X is a compact computable metric space and T is a computable continuous map (Definition 3.1).
    Standard setting of computable dynamical systems; invoked throughout Section 3.
  • domain assumption Hypothesis 1○: X (hence M(X) and MT(X)) is computably compact.
    Needed for the Π1 upper bound on β(φ); stated explicitly before Theorem 3.2.
  • domain assumption Hypothesis 2○: MT(X) is computably overt.
    Needed for the Σ1 lower bound (hence computability) of β(φ); the paper surveys when it holds or fails.
  • domain assumption The coefficient field F admits decidable equality and order (and computable addition and rational multiplication).
    Required for the exact finite-time algorithm of Section 5; fails for general computable reals.
  • standard math Bousch’s cohomology characterisation: a finite-range potential is cohomologous to a function ≤ β whose maximising set is an SFT.
    Cited from Bou01 and used to justify that maximising measures are supported on an SFT (Proposition 5.4).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computable Ergodic Optimisation." pith.science (2026). https://pith.science/paper/6KLLULHT

@misc{pith2026260711404,
  author       = {Pith},
  title        = {Pith review of: Computable Ergodic Optimisation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6KLLULHT}},
  note         = {Machine review of arXiv:2607.11404}
}
abstract

Links between physicals systems and computability properties have been an active field of investigation in recent years. Inspired by a previous work in the context of positive temperature Gibbs measures, we prove here that in the context of zero-temperature ergodic optimisation, for a computable potential and provided with several reasonable assumptions, the maximum ergodic average is a computable real number, and the set of maximising measures is a $\Pi_1$-computable compact set. Then, in the more specific context of symbolic dynamics, with finite-range interactions on subshifts of finite type, we provide an explicit algorithm to compute both the maximum ergodic average and the set of maximising measures in finite time, with a matching code repository.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 7 canonical work pages

  1. [1]

    A First Course in Dynamics: with a Panorama of Recent Developments , publisher =

    Katok, Anatole and Hasselblatt, Boris , year =. A First Course in Dynamics: with a Panorama of Recent Developments , publisher =

  2. [2]

    2008 , edition =

    Ambrosio, Luigi and Gigli, Nicola and Savaré, Giuseppe , title =. 2008 , edition =

    2008

  3. [3]

    Computable Analysis , year =

    Weihrauch, Klaus , publisher =. Computable Analysis , year =

  4. [4]

    Handbook of Computability and Complexity in Analysis , year =

    Hoyrup, Mathieu and Rute, Jason , title =. Handbook of Computability and Complexity in Analysis , year =

  5. [5]

    Dynamics, Games and Science

    Buescu, Jorge and Graça, Daniel and Zhong, Ning , title =. Dynamics, Games and Science. 2011 , publisher =

    2011

  6. [6]

    Recent Developments in Fractal Geometry and Dynamical Systems , pages =

    Computability in Dynamical Systems , author =. Recent Developments in Fractal Geometry and Dynamical Systems , pages =. 2024 , publisher =

    2024

  7. [7]

    Proceedings of the 52nd Symposium on Theory of Computing , pages =

    Rojas, Cristóbal and Yampolsky, Michael , title =. Proceedings of the 52nd Symposium on Theory of Computing , pages =. 2020 , doi =

    2020

  8. [8]

    Journal of Symbolic Logic , author =

    Nonrecursive Tilings of the Plane. Journal of Symbolic Logic , author =. 1974 , pages =. doi:10.2307/2272640 , number =

    work page doi:10.2307/2272640 1974

Show all 44 references
  1. [9]

    Journal of Symbolic Logic , author =

    Nonrecursive Tilings of the Plane. Journal of Symbolic Logic , author =. 1974 , pages =. doi:10.2307/2272641 , number =

    1974 doi

  2. [10]

    doi:10.1088/1361-6544/addbb8 , year =

    Gayral, Léo and Sablik, Mathieu and Taati, Siamak , title =. doi:10.1088/1361-6544/addbb8 , year =

    doi

  3. [11]

    ITCS , pages =

    Braverman, Mark and Grigo, Alexander and Rojas, Cristóbal , title =. ITCS , pages =. 2012 , doi =

    2012

  4. [12]

    2003 , doi =

    Computability on Subsets of Metric Spaces , journal =. 2003 , doi =

    2003

  5. [13]

    Journal of Universal Computer Science , volume =

    Spandl, Christoph , title =. Journal of Universal Computer Science , volume =. 2008 , number =

    2008

  6. [14]

    Nonlinearity , volume =

    Burr, Michael and Das, Suddhasattwa and Wolf, Christian and Yang, Yun , title =. Nonlinearity , volume =. 2022 , number =

    2022

  7. [15]

    Nonlinearity , volume =

    Burr, Michael and Wolf, Christian , title =. Nonlinearity , volume =. 2020 , pages =

    2020

  8. [16]

    A Characterization of the Entropies of Multidimensional Shifts of Finite Type , volume =

    Hochman, Michael and Meyerovitch, Tom , doi =. A Characterization of the Entropies of Multidimensional Shifts of Finite Type , volume =. Annals of Mathematics , number =

  9. [17]

    Inventiones Mathematicae , number =

    Meyerovitch, Tom , title =. Inventiones Mathematicae , number =. 2011 , doi =

    2011

  10. [18]

    Ergodic Theory and Dynamical Systems , volume =

    Jeandel, Emmanuel and Vanier, Pascal , title =. Ergodic Theory and Dynamical Systems , volume =. 2015 , doi =

    2015

  11. [19]

    Journal of Computer and System Sciences , volume =

    Boyer, Laurent and Delacourt, Martin and Poupet, Victor and Sablik, Mathieu and Theyssier, Guillaume , title =. Journal of Computer and System Sciences , volume =. 2015 , number =

    2015

  12. [20]

    Israel Journal of Mathematics , volume =

    Westrick, Linda , title =. Israel Journal of Mathematics , volume =. 2017 , doi =

    2017

  13. [21]

    Ergodic Theory and Dynamical Systems , volume =

    Hellouin de Menibus, Benjamin and Sablik, Mathieu , title =. Ergodic Theory and Dynamical Systems , volume =. 2018 , number =

    2018

  14. [22]

    2023 , volume =

    Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata , journal =. 2023 , volume =. doi:10.1016/j.jcss.2023.01.002 , author =

    2023 doi

  15. [23]

    2019 , volume =

    Jenkinson, Oliver , journal =. 2019 , volume =. doi:10.1017/etds.2017.142 , title =

    2019 doi

  16. [24]

    Discrete and Continuous Dynamical Systems , year =

    Ergodic Optimization , author =. Discrete and Continuous Dynamical Systems , year =

  17. [25]

    Comptes Rendus

    Brémont, Julien , title =. Comptes Rendus. Mathématique , pages =. 2008 , volume =

    2008

  18. [26]

    2010 , doi =

    Ergodic Optimization for Generic Continuous Functions , journal =. 2010 , doi =

    2010

  19. [27]

    Journal of Statistical Physics , year =

    van Enter, Aernout and Miȩkisz, Jacek , title =. Journal of Statistical Physics , year =

  20. [28]

    2016 , pages =

    Ground States are Generically a Periodic Orbit , journal =. 2016 , pages =. doi:10.1007/s00222-015-0638-0 , author =

    2016 doi

  21. [29]

    Mathematical Structures in Computer Science , author =

    Dynamical Systems: Stability and Simulability , volume =. Mathematical Structures in Computer Science , author =. 2007 , pages =. doi:10.1017/S096012950700597X , number =

    2007 doi

  22. [30]

    Mathematical Structures in Computer Science , number =

    Computable Analysis with Applications to Dynamic Systems , author =. Mathematical Structures in Computer Science , number =. 2020 , doi =

    2020

  23. [31]

    Computability of Probability Measures and

    Hoyrup, Mathieu and Rojas, Cristóbal , doi =. Computability of Probability Measures and. Information and Computation , number =

  24. [32]

    2011 , doi =

    Dynamics and Abstract Computability: Computing Invariant Measures , journal =. 2011 , doi =

    2011

  25. [33]

    Computational Dynamical Systems , year =

    Cotler, Jordan and Rezchikov, Semon , booktitle =. Computational Dynamical Systems , year =

  26. [34]

    doi:10.46298/lmcs-20(2:19)2024 , journal =

    Robust Non-Computability of Dynamical Systems and Computability of Robust Dynamical Systems , author =. doi:10.46298/lmcs-20(2:19)2024 , journal =

    2024 doi

  27. [35]

    Annales scientifiques de l'École Normale Supérieure , pages =

    Bousch, Thierry , title =. Annales scientifiques de l'École Normale Supérieure , pages =. 2001 , volume =

    2001

  28. [36]

    Discrete Mathematics , volume =

    Karp, Richard , title =. Discrete Mathematics , volume =. 1978 , doi =

    1978

  29. [37]

    Information Processing Letters , volume =

    Chaturvedi, Mmanu and McConnell, Ross , title =. Information Processing Letters , volume =. 2017 , doi =

    2017

  30. [38]

    Journal of Logic and Computation , volume =

    Hamkins, Joel and Nenu, Theodor , title =. Journal of Logic and Computation , volume =. 2026 , month =

    2026

  31. [39]

    Proceedings of the London Mathematical Society , volume =

    Turing, Alan , title =. Proceedings of the London Mathematical Society , volume =. 1937 , pages =

    1937

  32. [40]

    1975 , volume =

    Li, Tien-Yien and Yorke, James , journal =. 1975 , volume =. doi:10.2307/2318254 , title =

    1975 doi

  33. [41]

    Ukrains’kyi Matematychnyi Zhurnal , year =

    Coexistence of Cycles of a Continuous Map of the Line Into Itself , author =. Ukrains’kyi Matematychnyi Zhurnal , year =

  34. [42]

    Coexistence of Cycles of a Continuous Map of the Line Into Itself , journal =

    Sharkovsky, Oleksandr , translator =. Coexistence of Cycles of a Continuous Map of the Line Into Itself , journal =. 1995 , doi =

    1995

  35. [43]

    2026 , howpublished =

    Gayral, Léo , title =. 2026 , howpublished =

    2026

  36. [44]

    2501.00006 , archiveprefix =

    Rojas, Cristóbal and Yampolsky, Michael , year =. 2501.00006 , archiveprefix =

    arXiv

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.