pith. sign in

arxiv: 2606.25475 · v1 · pith:TRKRMIRUnew · submitted 2026-06-24 · 🧮 math.DS

A Krieger Embedding Theorem for Near Markov Sofic Shifts

Brian Marcus , Tom Meyerovitch , Chengyu Wu This is my paper

Pith reviewed 2026-06-25 19:55 UTC · model grok-4.3

classification 🧮 math.DS
keywords Krieger embedding theoremnear Markov sofic shiftssubshift embeddingmixing sofic shiftsirreducible shiftsfinite decidabilitysymbolic dynamics
0
0 comments X

The pith

Necessary and sufficient conditions exist for embedding subshifts into irreducible near Markov sofic shifts.

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

This paper generalizes Krieger's classical embedding theorem from mixing shifts of finite type to the narrower class of irreducible near Markov sofic shifts. It supplies adapted conditions that are both necessary and sufficient for a subshift to embed as a proper subshift into such a target. The same conditions become finitely decidable when the source subshift is irreducible and sofic. This matters because it identifies a larger but still tractable family of target systems for which embedding questions admit clean answers.

Core claim

Krieger's conditions, which characterize embeddings into mixing shifts of finite type, can be generalized to give necessary and sufficient conditions for embedding a subshift into a mixing near Markov sofic shift. If the subshift to be embedded is irreducible sofic, the conditions are finitely decidable.

What carries the argument

Generalized Krieger conditions adapted to the conjugacy-invariant class of near Markov sofic shifts.

If this is right

  • A subshift embeds into an irreducible near Markov sofic shift precisely when it satisfies the generalized conditions.
  • The embedding decision is algorithmic when the source is an irreducible sofic shift.
  • The result applies to all irreducible targets in the near Markov sofic class.
  • The conditions remain valid under conjugacy of the target.

Where Pith is reading between the lines

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

  • These criteria could support computational checks of embeddability for small or finitely presented symbolic systems.
  • Analogous generalizations might be possible for other conjugacy-invariant subclasses of sofic shifts that share Markov-like structural features.

Load-bearing premise

The target must belong to the class of near Markov sofic shifts, since the original conditions fail for general mixing sofic shifts.

What would settle it

An explicit pair consisting of a subshift satisfying the generalized conditions and an irreducible near Markov sofic shift into which no embedding exists would falsify the sufficiency claim.

Figures

Figures reproduced from arXiv: 2606.25475 by Brian Marcus, Chengyu Wu, Tom Meyerovitch.

Figure 1
Figure 1. Figure 1: The edge shift Z This phenomenon has been known since the time of Krieger’s em￾bedding theorem; indeed, see [B, Example 3.1] for a more elaborate example Y . Recently, Krieger [Kr3] showed that for some special classes of (non￾SFT) sofic shifts Y his original necessary conditions are sufficient for proper embedding. The main results of our paper, Theorem 7 (char￾acterization of embeddings) and Theorem 24 (… view at source ↗
Figure 2
Figure 2. Figure 2: The diagram illustrating the relationships among the various maps in Lemma 6. The arrows in the diagram are of two types: continuous injective maps, which have one arrowhead at the head and a hook at the tail, and continuous surjective maps, which have two arrowheads at the head. Proof. Using surjectivity of πZ, we can find a section ψ : Z → Zˆ for πZ : Zˆ → Z. By this we mean that πZ ◦ ψ = Id Z. Note that… view at source ↗
Figure 3
Figure 3. Figure 3: An example where the f-blowup is not unique up tp conjugacy. Though Example 11 suggests that a subshift may have many non￾conjugate blowups, the following proposition shows that any f-blowup must be conjugate to an f-blowup in standard form [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
read the original abstract

Krieger's classical embedding theorem gives necessary and sufficient conditions for embedding a subshift into a mixing shift of finite type (SFT) as a proper subshift. The same result does not hold if one replaces mixing SFT by a mixing sofic shift. In this paper, we generalize Krieger's conditions to give necessary and sufficient conditions for embedding a subshift into a mixing (in fact irreducible) near Markov sofic shift (a special conjugacy-invariant class of sofic shifts). We also show that if the subshift to be embedded is irreducible sofic, then the conditions are finitely decidable.

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 / 0 minor

Summary. The paper generalizes Krieger's classical embedding theorem to give necessary and sufficient conditions for embedding a subshift into a mixing (in fact irreducible) near Markov sofic shift, a conjugacy-invariant subclass of sofic shifts. It further shows that these conditions are finitely decidable when the subshift to be embedded is itself irreducible sofic.

Significance. If the result holds, the work extends a core theorem in symbolic dynamics to a strictly larger class of systems where the original Krieger conditions are known to fail, while preserving conjugacy invariance. The finite decidability statement for irreducible sofic sources adds computational content that is absent from the classical SFT case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary and for noting the potential significance of the generalization of Krieger's theorem to irreducible near Markov sofic shifts, along with the finite decidability result for irreducible sofic sources. The recommendation is uncertain, but the report contains no specific major comments to address point by point.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper generalizes Krieger's classical embedding theorem (an external result) to the conjugacy-invariant subclass of near Markov sofic shifts, explicitly noting that the original conditions fail for general mixing sofic shifts. The abstract and context present necessary and sufficient conditions as a direct mathematical extension without any equations, definitions, or claims that reduce the result to fitted parameters, self-referential quantities, or load-bearing self-citations. The decidability claim for irreducible sofic subshifts is likewise a standard computability statement scoped to the subclass, with no reduction to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard background theory of subshifts, sofic shifts, and conjugacy, plus the paper-specific definition of the near-Markov class; no free parameters or invented entities appear in the abstract.

axioms (1)
  • standard math Standard properties of subshifts, sofic shifts, irreducibility, and conjugacy in symbolic dynamics.
    Invoked implicitly when stating that the result fails for general sofic shifts and holds for the near-Markov subclass.

pith-pipeline@v0.9.1-grok · 5623 in / 1252 out tokens · 32437 ms · 2026-06-25T19:55:20.808863+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

15 extracted references · 1 linked inside Pith

  1. [1]

    Boyle, Lower entropy factors of sofic systems , Ergod

    M. Boyle, Lower entropy factors of sofic systems , Ergod. Th. Dynam. Syst. 4 (1984), 541-557

    1984

  2. [2]

    Boyle, B

    M. Boyle, B. Kitchens and B. Marcus, A note on minimal covers for sofic systems , Proceedings of the American Mathematical Society, 95, no. 3 (1985): 403–11

    1985

  3. [3]

    Boyle and W

    M. Boyle and W. Krieger, Almost Markov and Shift Equivalent Sofic Systems , Springer Lecture Notes in Mathematics, no. 1348 (1988), 335-395

    1988

  4. [4]

    Boyle, B

    M. Boyle, B. Marcus and P. Trow, Resolving maps and the dimension group for shifts of finite type , Volume 70, Memoirs of the American Mathematical Society, 1987

    1987

  5. [5]

    Kitchens, Symbolic Dynamics: One-sided, Two-sided and countable stste , Springer Universitext, 1988

    B. Kitchens, Symbolic Dynamics: One-sided, Two-sided and countable stste , Springer Universitext, 1988

    1988

  6. [6]

    Krieger, On the subsystems of topological Markov chains , Ergod

    W. Krieger, On the subsystems of topological Markov chains , Ergod. Th. Dynam. Sys. 2 (1982), 195-202

    1982

  7. [7]

    Krieger, On images of sofic systems ,arXiv:1101.1750v2, 2018 (v1 in 2011)

    W. Krieger, On images of sofic systems ,arXiv:1101.1750v2, 2018 (v1 in 2011)

    Pith/arXiv arXiv 2018

  8. [8]

    Krieger, On the subsystems of certain sofic shifts , arXiv:2507.02717v2, 2025

    W. Krieger, On the subsystems of certain sofic shifts , arXiv:2507.02717v2, 2025

    arXiv 2025

  9. [9]

    Manning, Axiom A Diffeomorphisms have Rational Zeta Functions , Bulletin of the London Mathematical Society, 3 (1971), 215-220

    A. Manning, Axiom A Diffeomorphisms have Rational Zeta Functions , Bulletin of the London Mathematical Society, 3 (1971), 215-220

    1971

  10. [10]

    Lind and B

    D. Lind and B. Marcus, An introduction to symbolic dynamics and coding , second edition, Cambridge Mathematical Library, Cambridge University Press (2021)

    2021

  11. [11]

    Marcus, Sofic systems and encoding data , IEEE Trans

    B. Marcus, Sofic systems and encoding data , IEEE Trans. Inform. Theory, 31 , (1985), 366-377

    1985

  12. [12]

    Marcus, T

    B. Marcus, T. Meyerovitch, K. Thomsen and C. Wu, Factorizable Embeddings and the Period of an irreducible sofic shift , Preprint, arXiv:2508.02554, 2025

    arXiv 2025

  13. [13]

    Thomsen, On the structure of a sofic shift space , Trans

    K. Thomsen, On the structure of a sofic shift space , Trans. Amer. Math. Soc. 356 (2004), 3557-3619

    2004

  14. [14]

    Nasu, Constant-to-one and onto global maps of homomorphisms between strongly connected graphs, Ergod

    M. Nasu, Constant-to-one and onto global maps of homomorphisms between strongly connected graphs, Ergod. Th. & Dynam. Sys., 3 (1983), 387--411

    1983

  15. [15]

    Weiss, Subshifts of finite type and sofic systems , Monatshefte Mathematik, 77 (1973), 462-474

    B. Weiss, Subshifts of finite type and sofic systems , Monatshefte Mathematik, 77 (1973), 462-474

    1973