Computability of pressure for subshifts on countable amenable groups

Abstract There are a variety of results in the literature proving forms of computability for topological entropy and pressure on subshifts. In this work, we prove two quite general results, showing that topological pressure is always computable from above given an enumeration for a forbidden list inducing the subshift, and that for strongly irreducible (SI) shifts of finite type, topological pressure is computable. Our results apply to subshifts on all finitely generated amenable groups with decidable word problem and generalize several previous results which applied only to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:mrow> </mml:math> -subshifts. As corollaries, we obtain some results related to ground state energy and entropy, proving that the map sending φ to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:munder> <mml:mo movablelimits="true">sup</mml:mo> <mml:mrow> <mml:mi>μ</mml:mi> <mml:mo>∈</mml:mo> <mml:msub> <mml:mi>M</mml:mi> <mml:mi>σ</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>X</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:munder> <mml:mo>∫</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mrow> <mml:mi mathvariant="normal">d</mml:mi> </mml:mrow> <mml:mi>μ</mml:mi> </mml:mrow> </mml:math> is computable/computable from above when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>X</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> is, and that the map sending φ to its ground state/residual entropy is computable from above when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>X</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> is computable. We conclude by giving explicit bounds on computation time of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>X</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> in the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:mrow> </mml:math> setting for SI subshift of finite types and locally constant and rational valued φ , and show that in the special case <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>A</mml:mi> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , this algorithm runs in singly exponential time.