Factor maps between sofic shifts

Definitions and mathematical statement

Let $X\subset A^{\mathbb Z}$ and $Y\subset B^{\mathbb Z}$ be nonempty two-sided sofic shifts. Here a sofic shift consists of the label sequences of bi-infinite paths in a finite directed graph with edges labelled by a finite alphabet. The spaces have the product topology and left shifts. Write $\mathcal L_n(X)$ for their occurring words of length $n$, and set \[ h(X)=\lim_{n\to\infty}\frac1n\log|\mathcal L_n(X)|, \] using natural logarithms. Define $h(Y)$ analogously and assume $h(X)\ge h(Y)$.

Give necessary and sufficient conditions, stated in terms of the two sofic systems or their finite labelled graph presentations, for a factor map $\pi:X\to Y$ to exist. A factor map is a continuous surjection with $\pi\sigma=\sigma\pi$. Equivalently, there must be a radius $r\ge0$ and a rule on the allowed $(2r+1)$-letter words of $X$ whose coordinatewise application has image exactly $Y$.

The problem includes equal-entropy pairs and systems which are not transitive; the radius is not specified in advance. It asks for an actual classification of when such a code exists, rather than the necessary entropy inequality alone. Boyle's update records a solution of the transitive, aperiodic-target, strictly unequal-entropy case. The target here retains the general factor-map problem beyond that case, as in the catalogue.

Short English statement

Determine exactly when one sofic shift can continuously encode another while commuting with the shift.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 4600008 (AMR-045-0008), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Boyle - Open Problems in Symbolic Dynamics (2008), Problem/Question/Conjecture 8.1. Original source indexed by AMR-045-0008. https://www.math.umd.edu/~mboyle/papers/openfinalsub3nov2007.pdf.
• S3 Boyle, solution updates for Problem 8.1. https://math.umd.edu/~mboyle/open/.