Medvedev degrees of SFTs on cocompact Fuchsian groups

Abstract

We prove that for any cocompact Fuchsian group the class of Medvedev degrees attained by subshifts of finite type is the class of ${\Pi }_1^0$ degrees. This result relies on the construction of a rigid hierarchical structure in a graph model of the hyperbolic plane, and on the fact that every such group admits a representation in ${\mathrm{PSL}}_2(\mathbb{R})$ such that the matrices in the image have coefficients that are computable real numbers.

arXiv comment62 pages, but a staggering total of 51 figures