pith. sign in

arxiv: 2406.12777 · v2 · submitted 2024-06-18 · 🧮 math.DS · math.GR· math.LO

Medvedev degrees of subshifts on groups

Sebasti\'an Barbieri , Nicanor Carrasco-Vargas This is my paper

Pith reviewed 2026-05-24 00:07 UTC · model grok-4.3

classification 🧮 math.DS math.GRmath.LO
keywords Medvedev degreessubshifts of finite typesofic subshiftsquasi-isometriesvirtually polycyclic groupsbranch groupsgroup actionsdynamical invariants
0
0 comments X

The pith

Medvedev degrees of subshifts transfer via quotients, subgroups, translation-like actions and quasi-isometries, enabling full classifications for SFTs on virtually polycyclic groups and branch groups with decidable word problem.

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

The paper develops theory showing how Medvedev degrees transfer between subshifts on groups linked by quotients, subgroups, translation-like actions, and quasi-isometries. These transfer rules are applied to determine the possible Medvedev degrees taken by subshifts of finite type on finitely generated groups. Complete classifications result for virtually polycyclic groups and for branch groups with decidable word problem. Groups quasi-isometric to the hyperbolic plane are shown to admit SFTs realizing nonzero Medvedev degree, and classifications are also given for sofic subshifts on several classes.

Core claim

Using transfer principles induced by algebraic and geometric relations between groups, the possible Medvedev degrees of subshifts of finite type are completely classified on virtually polycyclic groups and on branch groups with decidable word problem; groups quasi-isometric to the hyperbolic plane admit SFTs with nonzero Medvedev degree; and the degrees of sofic subshifts are classified for several further classes of groups.

What carries the argument

Transfer principles for Medvedev degrees induced by quotients, subgroups, translation-like actions, and quasi-isometries between groups.

If this is right

  • Virtually polycyclic groups have their possible SFT Medvedev degrees completely determined.
  • Branch groups with decidable word problem have their possible SFT Medvedev degrees completely determined.
  • Every group quasi-isometric to the hyperbolic plane admits at least one SFT whose Medvedev degree is nonzero.
  • Sofic subshifts have their Medvedev degrees classified on several additional classes of groups.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The transfer machinery may apply to other computability-based invariants beyond Medvedev degrees.
  • Classifications on polycyclic and branch groups could inform decidability questions for tilings or configurations on those groups.
  • Existence of nonzero-degree SFTs near the hyperbolic plane suggests similar existence results may hold for other non-amenable geometries.

Load-bearing premise

The algebraic and geometric relations between groups induce corresponding transfers of Medvedev degrees between the subshifts defined on those groups.

What would settle it

An explicit group relation (such as a quasi-isometry) together with an SFT whose Medvedev degree fails to match any value predicted by the transfer from the other group, or a virtually polycyclic group admitting an SFT whose Medvedev degree lies outside the classified set.

read the original abstract

The Medvedev degree of a subshift is a dynamical invariant of computable origin that can be used to compare the complexity of subshifts that contain only uncomputable configurations. We develop theory to describe how these degrees can be transferred from one group to another through algebraic and geometric relations, such as quotients, subgroups, translation-like actions and quasi-isometries. We use the aforementioned tools to study the possible values taken by this invariant on subshifts of finite type on some finitely generated groups. We obtain a full classification for some classes, such as virtually polycyclic groups and branch groups with decidable word problem. We also show that all groups which are quasi-isometric to the hyperbolic plane admit SFTs with nonzero Medvedev degree. Furthermore, we provide a classification of the degrees of sofic subshifts for several classes of groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript develops transfer theorems for Medvedev degrees of subshifts under algebraic and geometric relations between groups, including quotients, subgroups, translation-like actions, and quasi-isometries. These tools are applied to classify the possible Medvedev degrees of subshifts of finite type on virtually polycyclic groups and on branch groups with decidable word problem, to show that groups quasi-isometric to the hyperbolic plane admit SFTs of nonzero Medvedev degree, and to classify Medvedev degrees of sofic subshifts for several additional classes of groups.

Significance. If the transfer theorems hold, the results provide a substantial extension of computability invariants in symbolic dynamics from Z^d to broader classes of finitely generated groups. The explicit classifications for virtually polycyclic and branch groups, together with the quasi-isometry existence result, constitute concrete progress; the development of the transfer machinery itself is a reusable contribution that links group-theoretic relations directly to dynamical complexity measures.

minor comments (3)
  1. [§2] §2: the definition of the transfer map under translation-like actions should include an explicit statement of the domain and codomain subshifts to avoid ambiguity when the action is not free.
  2. [Theorem 4.3] Theorem 4.3: the statement that the classification is 'complete' for virtually polycyclic groups would benefit from a short remark confirming that every possible Medvedev degree in the target set is realized by some SFT.
  3. [Figure 1] Figure 1: the diagram illustrating the quasi-isometry transfer would be clearer if the direction of the degree inequality were labeled on the arrows.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, accurate summary of the transfer theorems and their applications to virtually polycyclic groups, branch groups, and quasi-isometries to the hyperbolic plane, and for recommending minor revision. We are pleased that the significance of extending computability invariants beyond Z^d is recognized.

Circularity Check

0 steps flagged

No significant circularity; derivations self-contained

full rationale

The paper first develops transfer theorems for Medvedev degrees under quotients, subgroups, translation-like actions and quasi-isometries from the standard definitions of subshifts and Medvedev degrees. These tools are then applied to obtain classifications for virtually polycyclic groups, branch groups with decidable word problem, and existence results for groups quasi-isometric to the hyperbolic plane. No step reduces a claimed result to a fitted parameter, self-citation chain, or definitional renaming; the central claims rest on internally proven transfer properties applied to external group-theoretic facts. This is the normal case of a self-contained mathematical development.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based solely on abstract; no free parameters, invented entities, or ad-hoc axioms are mentioned. The work relies on standard background from group theory, computability theory, and symbolic dynamics.

axioms (1)
  • standard math Standard axioms and definitions of groups, subshifts, and Medvedev degrees from prior literature
    The abstract invokes these established concepts to define the transfer theory and classifications.

pith-pipeline@v0.9.0 · 5674 in / 1391 out tokens · 28486 ms · 2026-05-24T00:07:52.573382+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages · 2 internal anchors

  1. [1]

    Aubrun, S

    N. Aubrun, S. Barbieri, and E. Jeandel. About the Domino Problem for Subshifts on Groups. In V. Berth´ e and M. Rigo, editors,Sequences, Groups, and Number Theory, pages 331–389. Springer International Publishing, Cham, 2018

    work page 2018

  2. [2]

    Aubrun, S

    N. Aubrun, S. Barbieri, and E. Moutot. The Domino Problem is Undecidable on Surface Groups. In P. Rossmanith, P. Heggernes, and J.-P. Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) , volume 138 of Leibniz Interna- tional Proceedings in Informatics (LIPIcs) , pages 46:1–46:14, Dagstuhl, Germany, 20...

    work page 2019

  3. [3]

    Aubrun, S

    N. Aubrun, S. Barbieri, and M. Sablik. A notion of effectiveness for subshifts on finitely generated groups. Theoretical Computer Science, 661:35–55, 2017

    work page 2017

  4. [4]

    Aubrun and J

    N. Aubrun and J. Kari. Tiling Problems on Baumslag-Solitar groups. Electronic Proceedings in Theoretical Computer Science, 128:35–46, Sept. 2013

    work page 2013

  5. [5]

    A. Ballier. Universality in symbolic dynamics constrained by medvedev degrees. arXiv:1304.5418, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  6. [6]

    Ballier and M

    A. Ballier and M. Stein. The domino problem on groups of polynomial growth. Groups, Geometry, and Dynamics, 12(1):93–105, 2018

    work page 2018

  7. [7]

    Barbieri

    S. Barbieri. Shift spaces on groups : computability and dynamics . Theses, Universit´ e de Lyon, June 2017

    work page 2017

  8. [8]

    Barbieri

    S. Barbieri. A geometric simulation theorem on direct products of finitely generated groups. Discrete Analysis, 09, 2019

    work page 2019

  9. [9]

    Barbieri

    S. Barbieri. On the entropies of subshifts of finite type on countable amenable groups. Groups, Geometry, and Dynamics , 15(2):607–638, 2021

    work page 2021

  10. [10]

    Barbieri, N

    S. Barbieri, N. Carrasco-Vargas, and C. Rojas. Effective dynamical systems beyond dimension zero and factors of SFTs. arXiv:2401.07973, 2024

    work page arXiv 2024

  11. [11]

    Barbieri, M

    S. Barbieri, M. Sablik, and V. Salo. Groups with self-simulable zero-dimensional dynamics. arXiv:2104.05141, 2021

    work page arXiv 2021

  12. [12]

    Bartholdi

    L. Bartholdi. The domino problem for hyperbolic groups. arXiv:2305.06952, 2023

    work page arXiv 2023

  13. [13]

    Bartholdi, R

    L. Bartholdi, R. I. Grigorchuk, and Z. ˇSuni. Branch groups. volume 3 of Handbook of Algebra, pages 989–1112. North-Holland, 2003

    work page 2003

  14. [14]

    Bartholdi and V

    L. Bartholdi and V. Salo. Shifts on the lamplighter group. arXiv:2402.14508, 2024. 23

    work page arXiv 2024

  15. [15]

    Baumslag, F

    G. Baumslag, F. B. Cannonito, and C. F. Miller. Computable algebra and group embeddings. Journal of Algebra, 69(1):186–212, Mar. 1981

    work page 1981

  16. [16]

    R. Berger. The Undecidability of the Domino Problem . Memoirs of the American Mathematical Society. American Mathematical Society, 1966

    work page 1966

  17. [17]

    Bogopolski, A

    O. Bogopolski, A. Martino, and E. Ventura. Orbit decidability and the conjugacy problem for some extensions of groups. Transactions of the American Mathematical Society, 362(4):2003–2036, 2010

    work page 2003

  18. [18]

    M. R. Bridson and A. Haefliger. Metric Spaces of Non-Positive Curvature . Number 319 in Grundlehren Der Mathematischen Wissenschaften. Springer, Berlin ; New York, 1999

    work page 1999

  19. [19]

    Carrasco-Vargas

    N. Carrasco-Vargas. The geometric subgroup membership problem. to appear in Groups, Geom- etry and Dynamics. arXiv:2303.14820 , Mar. 2023

    work page arXiv 2023

  20. [20]

    Carroll and A

    D. Carroll and A. Penland. Periodic points on shifts of finite type and commensurability invariants of groups. The New York Journal of Mathematics , 21:811–822, 2015

    work page 2015

  21. [21]

    Ceccherini-Silberstein and M

    T. Ceccherini-Silberstein and M. Coornaert. Cellular Automata and Groups . Springer Monogr. Math. Springer, Berlin, 2010

    work page 2010

  22. [22]

    D. Cenzer. Π 0 1 classes in computability theory. In E. R. Griffor, editor, Handbook of Computability Theory, volume 140 ofStudies in Logic and the Foundations of Mathematics, pages 37–85. Elsevier, 1999

    work page 1999

  23. [23]

    D. B. Cohen. The large scale geometry of strongly aperiodic subshifts of finite type. Advances in Mathematics, 308:599–626, Feb. 2017

    work page 2017

  24. [24]

    D. B. Cohen. A counterexample to the easy direction of the geometric Gersten conjecture. Pacific Journal of Mathematics , 298(1):27–31, Feb. 2019

    work page 2019

  25. [25]

    D. B. Cohen, C. Goodman-Strauss, and Y. Rieck. Strongly aperiodic subshifts of finite type on hyperbolic groups. Ergodic Theory and Dynamical Systems , pages 1–44, Sept. 2021

    work page 2021

  26. [26]

    de La Harpe

    P. de La Harpe. Topics in Geometric Group Theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, 2000

    work page 2000

  27. [27]

    Drut ¸u, M

    C. Drut ¸u, M. Kapovich, and B. Nica.Geometric Group Theory. Number volume 63 in Colloquium Publications. American Mathematical Society, Providence, Rhode Island, 2018

    work page 2018

  28. [28]

    Durand, A

    B. Durand, A. Romashchenko, and A. Shen. Fixed-point tile sets and their applications. Journal of Computer and System Sciences , 78(3):731–764, May 2012

    work page 2012

  29. [29]

    Goodman-Strauss

    C. Goodman-Strauss. A hierarchical strongly aperiodic set of tiles in the hyperbolic plane. The- oretical Computer Science, 411(7):1085–1093, Feb. 2010

    work page 2010

  30. [30]

    W. Hanf. Nonrecursive Tilings of the Plane. I. The Journal of Symbolic Logic , 39(2):283–285, 1974

    work page 1974

  31. [31]

    P. G. Hinman. A survey of Muˇ cnik and Medvedev degrees. The Bulletin of Symbolic Logic , 18(2):161–229, 2012

    work page 2012

  32. [32]

    M. Hochman. A note on universality in multidimensional symbolic dynamics. Discrete and Continuous Dynamical Systems - S , 2(2):301–314, 2009. 24

    work page 2009

  33. [33]

    Hochman and T

    M. Hochman and T. Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics , 171(3):2011–2038, May 2010

    work page 2011

  34. [34]

    P. K. Hooper. The undecidability of the Turing machine immortality problem.Journal of Symbolic Logic, 31(2):219–234, June 1966

    work page 1966

  35. [35]

    E. Jeandel. On Immortal Configurations in Turing Machines. In S. B. Cooper, A. Dawar, and B. L¨ owe, editors,How the World Computes , Lecture Notes in Computer Science, pages 334–343, Berlin, Heidelberg, 2012. Springer

    work page 2012

  36. [36]

    E. Jeandel. Some Notes about Subshifts on Groups. working paper or preprint, hal-01110211, Jan. 2015

    work page 2015

  37. [37]

    E. Jeandel. Translation-like Actions and Aperiodic Subshifts on Groups. arXiv:1508.06419 [cs, math], Aug. 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  38. [38]

    J. Kari. The Tiling Problem Revisited (Extended Abstract). In J. Durand-Lose and M. Mar- genstern, editors, Machines, Computations, and Universality , volume 4664, pages 72–79. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007

    work page 2007

  39. [39]

    S. Katok. Fuchsian Groups. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, June 1992

    work page 1992

  40. [40]

    A. E. M. Lewis, R. A. Shore, and A. Sorbi. Topological aspects of the Medvedev lattice. Archive for Mathematical Logic, 50(3):319–340, May 2011

    work page 2011

  41. [41]

    D. A. Lind. The entropies of topological Markov shifts and a related class of algebraic integers. Ergodic Theory Dynam. Systems , 4(2):283–300, 1984

    work page 1984

  42. [42]

    Yu. T. Medvedev. Degrees of difficulty of the mass problem. Dokl. Akad. Nauk SSSR (N.S.) , 104:501–504, 1955

    work page 1955

  43. [43]

    J. S. Miller. Two notes on subshifts. Proceedings of the American Mathematical Society , 140(5):1617–1622, 2012

    work page 2012

  44. [44]

    D. Myers. Nonrecursive tilings of the plane. II. Journal of Symbolic Logic , 39(2):286–294, June 1974

    work page 1974

  45. [45]

    S. T. Piantadosi. Symbolic dynamics on free groups. Discrete & Continuous Dynamical Systems , 20(3):725, 2008

    work page 2008

  46. [46]

    D. Segal. Polycyclic Groups . Cambridge Tracts in Mathematics. Cambridge University Press, 1983

    work page 1983

  47. [47]

    B. Seward. Burnside’s problem, spanning trees and tilings. Geometry & Topology, 18(1):179–210, 2014

    work page 2014

  48. [48]

    S. G. Simpson. Medvedev degrees of two-dimensional subshifts of finite type. Ergodic Theory and Dynamical Systems, 34(2):679–688, 2014

    work page 2014

  49. [49]

    A. Sorbi. The Medvedev lattice of degrees of difficulty. In S. B. Cooper, S. S. Wainer, and T. A. Slaman, editors, Computability, Enumerability, Unsolvability: Directions in Recursion Theory , London Mathematical Society Lecture Note Series, pages 289–312. Cambridge University Press, Cambridge, 1996. 25

    work page 1996