Complexity of Low-Chromatic Compact Free Subshifts

Definitions and mathematical statement

Let $\Gamma=({\mathbb{Z}}/2{\mathbb{Z}})*({\mathbb{Z}}/2{\mathbb{Z}})*({\mathbb{Z}}/2{\mathbb{Z}})=\langle a,b,c\mid a^2=b^2=c^2=e\rangle$, and give $2^\Gamma=\{0,1\}^\Gamma$ the product topology, with $\{0,1\}$ discrete. Use the left shift action \[ (g\cdot x)(h)=x(g^{-1}h)\qquad(g,h\in\Gamma,\ x\in2^\Gamma). \] A compact subshift is a compact set $X\subseteq2^\Gamma$ invariant under this action. It is free if \[ \forall x\in X\ \forall g\in\Gamma\setminus\{e\},\qquad g\cdot x\ne x. \] For such an $X$, let $G_X$ be the undirected graph on $X$ whose adjacency relation is \[ x\sim_{G_X}y\quad\Longleftrightarrow\quad y=s\cdot x\text{ for some }s\in\{a,b,c\}. \] The condition $\chi_B(G_X)\le3$ means that there is a Borel map $f:X\to\{0,1,2\}$, for the Borel structure inherited from $2^\Gamma$, such that \[ \forall x\in X\ \forall s\in\{a,b,c\},\qquad f(s\cdot x)\ne f(x). \] This uses the natural graph associated with the three free-product generators; the supplied excerpt does not explicitly define its graph convention.

For an explicit parameterization, let $\mathcal K(2^\Gamma)$ be the Vietoris hyperspace of nonempty compact subsets of $2^\Gamma$, and put \[ \mathcal F=\{X\in\mathcal K(2^\Gamma):X\text{ is an invariant free subshift}\},\qquad \mathcal C=\{X\in\mathcal F:\chi_B(G_X)\le3\}. \] The source question is whether $\mathcal C$ is $\boldsymbol\Sigma^1_2$-complete.

To make the complexity terminology explicit, for a Polish space $P$, a set $A\subseteq P$ is $\boldsymbol\Sigma^1_2$ if there is a Borel relation $R\subseteq P\times{\mathbb{N}}^{\mathbb{N}}\times{\mathbb{N}}^{\mathbb{N}}$ such that \[ p\in A\quad\Longleftrightarrow\quad\exists u\in{\mathbb{N}}^{\mathbb{N}}\ \forall v\in{\mathbb{N}}^{\mathbb{N}}\ R(p,u,v). \] Completeness requires membership in this pointclass and an appropriate universal reduction property. Under Borel reductions, that property says that for every standard Borel space $P$ and every $\boldsymbol\Sigma^1_2$ set $A\subseteq P$, there is a Borel map $r:P\to\mathcal K(2^\Gamma)$ with \[ p\in A\quad\Longleftrightarrow\quad r(p)\in\mathcal C. \] Under continuous reductions, one instead requires continuous reducing maps, with the test spaces specified by the chosen completeness convention. A relative formulation with target $\mathcal F$ additionally requires the reducing maps to take values in $\mathcal F$.

Unresolved qualifications. The supplied statement does not specify the reduction convention, the coding space, whether completeness is relative to $\mathcal F$, or whether the empty subshift is allowed. The hyperspace and nonemptiness conventions above give an explicit interpretation, but the intended completeness convention requires confirmation from the full source context. No equivalence between these possible completeness formulations is asserted here.

Short English statement

For the shift action of $({\mathbb{Z}}/2{\mathbb{Z}})*({\mathbb{Z}}/2{\mathbb{Z}})*({\mathbb{Z}}/2{\mathbb{Z}})$ on binary configurations, consider compact invariant sets on which every nonidentity group element acts without fixed points. The question asks whether those whose generator graph admits a Borel proper coloring with at most three colors form a $\boldsymbol\Sigma^1_2$-complete collection. The precise coding and reduction conventions remain unspecified in the supplied excerpt. The registry labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005028$, title "Complexity of Low-Chromatic Compact Free Subshifts," collection "Oberwolfach Reports Open Problems," exact source problem code catalogue entry. No individual proposer is identified in the supplied record.
• Supplied report citation: Mini-Workshop: Descriptive Combinatorics, LOCAL Algorithms and Random Processes (2023), Oberwolfach Reports, pp. 429--455, DOI 10.4171/owr/2022/8. The extracted passage carries page number 453. https://doi.org/10.4171/owr/2022/8. The registry separately records proposed year 2022; the difference between that year and the citation's 2023 label is unresolved here.
• Supplied literature source: On Homomorphism Graphs, identified by the supplied assessment as a 2024 primary paper. https://doi.org/10.1017/fmp.2024.8.
• Supplied literature source: "Oberwolfach report." https://doi.org/10.4171/owr/2022/8.
• Literature checked at: 2026-08-22. This is supplied dated curation, not an independently verified assessment. It labels the problem open and reports that the 2024 primary paper still treats the compact free subshift characterization as an open direction, with no result found establishing the stronger completeness claim for this class. The supplied background expressly requests independent verification of time-sensitive status and cited claims.
• The registry marks the statement corrected_verified and reports reconstruction and checking against the official Oberwolfach report. These are supplied provenance claims; this draft does not independently verify them or claim to have visited either linked source.