On the stability of the penalty function for the ℤ 2 \mathbb{Z}^{2} -hard square shift

Chihiro Oguri, Mao Shinoda · 2025

Read On the stability of the penalty function for the ℤ 2 \mathbb{Z}^{2} -hard square shift by Chihiro Oguri, Mao Shinoda (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06958.txt.

Introduction

Chihiro Oguri and Mao Shinoda study a math question about patterns on a grid in a 2025 paper. They look at the hard square shift, a set of grid patterns with a ban on some neighbors. The question is whether the best patterns stay best when the scoring rule changes a little.

In one dimension, such stability is known to hold. In two dimensions, a past case based on Robinson tiling showed it can fail. Oguri and Shinoda study a nearest-neighbor system with a helpful filling property and positive variety. Their main result shows stability does hold there, which helps map where the two-dimensional case differs.

Catalog record

CREATORChihiro Oguri, Mao Shinoda
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06958

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the stability of the penalty function for the ℤ 2 \mathbb{Z}^{2} -hard square shift Chihiro Oguri, Mao Shinoda Abstract . We investigate the stability of maximizing measures for a penalty function of a two-dimensional subshift of finite type, building on the work of Gonschorowski et al. [ 1 ] . In the one-dimensional case, such measures remain stable under Lipschitz perturbations for any subshift of finite type. However, instability arises for a penalty function of the Robinson tiling, which is a two-dimensional subshift of finite type with no periodic point and zero entropy. This raises the question of whether stability persists in two-dimensional subshifts of finite type with positive topological entropy. In this paper, we address this question by studying the ℤ 2 \mathbb{Z}^{2} -hard square shift, a well-known example of a two-dimensional subshift with positive entropy. Our main theorem establishes that, in contrast to previous results, a penalty function of the hard square shift remains stable under Lipschitz perturbations. 2010 Mathematics Subject Classification Primary 37B51, 37B10, 37B25 1. Introduction Ergodic optimization is the study of maximizing measures. In its most basic form, let T:X\rightarrow X be a continuous map on a compact metric space X and for a continuous function \varphi:X\rightarrow\mathbb{R} we consider the maximum ergodic average \displaystyle\beta(\varphi)=\sup_{\mu\in\mathcal{M}_{T}(X)}\int\varphi\ d\mu where \mathcal{M}_{T}(X) is the space of T -invariant Borel probability measures on X endowed with the weak*-topology. An invariant measure which attains the maximum is called a maximizing measure for \varphi and denote by \mathcal{M}_{{\rm max}}(\varphi) the set of maximizing measures for \varphi . The stability of maximizing measures for a penalty function of a subshift of finite type was established by Gonschorowski et al. [ 1 ] . A penalty function is defined on the forbidden set of a subshift of finite type, assigning a value of 0 to admissible local configurations near the origin and -1 otherwise (see §2 for more details). It is straightforward to see that every maximizing measure of a penalty function is supported on the given subshift of finite type. In the one-dimensional case, maximizing measures remain supported on the given subshift under Lipschitz perturbations for any subshift of finite type. However, in the two-dimensional case, there exists a subshift of finite type where this stability fails. In [ 1 ] , the authors highlight the difference between one and two dimensions, demonstrating that instability arises in a penalty function of the Robinson tiling, which is a two-dimensional subshift of finite type with no periodic points and zero entropy. This naturally prompts the question of whether stability persists for a two-dimensional subshift of finite type with positive topological entropy. In this paper, we address this question by investigating the \mathbb{Z}^{2} -hard square shift , a well-known example of a two-dimensional subshift of finite type with positive entropy (See [ 2 ] for more properties of hard square shifts). Our main theorem establishes that, in contrast to the results on \mathbb{Z}^{2} subshift of finite type as presented by Gonschorowski et al., the penalty function of the hard square shift remains stable under Lipschitz perturbations. Informally, a subshift of finite type is defined by specifying a finite set of finite “forbidden patterns” F made up of letters from alphabet \mathcal{A} , and defining X_{F} to be the set of configurations in \mathcal{A}^{\mathbb{Z}^{d}} in which no pattern from F appears (see §2 for more details). The set F is called a forbidden set . The \mathbb{Z}^{2} -hard square shift is a subshift of finite type where no two adjacent 1’s appear, either horizontally or vertically. Although other forbidden sets can be used to define the hard square shift, we will use the following forbidden set F to define the penalty function later: (1) \displaystyle F=\left\{\begin{smallmatrix}1&1\\ 1&1\end{smallmatrix}~~\begin{smallmatrix}1&0\\ 1&0\end{smallmatrix}~~\begin{smallmatrix}1&0\\ 1&1\end{smallmatrix}~~\begin{smallmatrix}0&0\\ 1&1\end{smallmatrix}~~\begin{smallmatrix}0&1\\ 1&1\end{smallmatrix}\right\}. We now define the penalty function as follows: f(x)=\left\{\begin{array}[]{cc}-1&\mbox{if}~\begin{smallmatrix}x_{(0,1)}&x_{(1,1)}\\ x_{(0,0)}&x_{(1,0)}\end{smallmatrix}\in F\\ 0&\mbox{otherwise}\end{array}\right.. Now we can state our main theorem. Theorem 1 . Let X be the hard square shift and f be the penalty function. Then there exists \varepsilon>0 such that for every Lipschitz continuous function g with \|f-g\|_{{\rm Lip}}<\varepsilon , every maximizing measure of g is supported on X . We remark that the stability result for the hard square shift is relatively straightforward, since forbidden words can be easily eliminated by replacing 1 with 0 . However, extending this result to other nearest neighbor subshifts of finite type, such as those discussed in [ 2 ] , appears to be more challenging. This difficulty arises because, in general, there is no method to identify the exact locations of forbidden words, making it impossible to estimate the distances required to remove them. For the remainder of this paper, we fix our notations and definitions in §2 and provide the proof of the main theorem in §3. 2. Settings Let \mathcal{A} be a finite set, which we call an alphabet . The \mathbb{Z}^{2} full shift on \mathcal{A} is the set \mathcal{A}^{\mathbb{Z}^{2}} , endowed with the product topology of the discrete topology. Define a metric by \displaystyle d(\underline{x},\underline{y})=\left\{\begin{array}[]{cc}\frac{1}{2^{i}}&\underline{x}\neq\underline{y}\\ 0&\mbox{otherwise}\end{array}\right. for \underline{x},\underline{y}\in\mathcal{A}^{\mathbb{Z}^{2}} where i=\inf\{\|u\|_{\infty}:x_{u}\neq y_{u}\} . Then, this metric is compatible with the product topology. For any full shift \mathcal{A}^{\mathbb{Z}^{2}} , we define the \mathbb{Z}^{2} -action \{\sigma_{u}\}_{u\in\mathbb{Z}^{2}} on \mathcal{A}^{\mathbb{Z}^{2}} as follows: for any u\in\mathbb{Z}^{2} and \underline{x}\in\mathcal{A}^{\mathbb{Z}^{2}} , (\sigma_{u}(\underline{x}))_{v}=x_{u+v} for all u\in\mathbb{Z}^{2} . A subset X\subset\mathcal{A}^{\mathbb{Z}^{2}} is a subshift if it is closed and shift-invariant , i.e. for any \underline{x} and u\in\mathbb{Z}^{2} , \sigma_{u}(\underline{x})\in X . A configuration w on the alphabet \mathcal{A} is any mapping from a non-empty subset S of \mathbb{Z}^{2} to \mathcal{A} , where S is called the shape of w . For any configuration w with shape S and any T\subset S , denote by w|_{T} the restriction of w to T , i.e. the subconfiguration of w appearing T . A subshift X is a shift of finite type if there exists a finite collection F of finite configuration on \mathcal{A} such that X=X_{F} to be the set of \underline{x}\in\mathcal{A}^{\mathbb{Z}^{2}} such that \underline{x}|_{S}\notin F for all finite S\subset\mathbb{Z}^{2} . Definition 2.1 (The \mathbb{Z}^{2} -hard square shift) . Let \mathcal{A}=\{0,1\} and set the forbidden set by F=\left\{\begin{smallmatrix}1&1\\ 1&1\end{smallmatrix}~~\begin{smallmatrix}1&0\\ 1&0\end{smallmatrix}~~\begin{smallmatrix}1&0\\ 1&1\end{smallmatrix}~~\begin{smallmatrix}0&0\\ 1&1\end{smallmatrix}~~\begin{smallmatrix}0&1\\ 1&1\end{smallmatrix}\right\}. Then the subshift X=X_{F} is called the \mathbb{Z}^{2} -hard square shift . It is easy to see that the topological entropy of the hard square shift is positive. For any a,b\in\mathbb{Z} with a<b , we use [a,b] to denote \{a,a+1,\ldots,b\} . For each n\geq 0 define the box of size n as \displaystyle\Lambda_{n}=[-n,n]\times[-n,n]. The cardinality of \Lambda_{n} is given by \lambda_{n}=\#\Lambda_{n}=(2n+1)^{2} . For a continuous function f and a nonempty subset T\subset\mathbb{Z}^{2} define a dynamical sum over T by \displaystyle S_{T}f=\sum_{u\in T}f\circ\sigma^{u}. 3. Proof of the main theorem First we recall the following Lemma. Lemma 3.1 ( [ 1 , Lemma 2.1.] ) . Let J\subset X be a subset of a compact metric space X and f be a Lipschitz continuous function with f|_{J}=0 . For \varepsilon>0 and a Lipschitz continuous function g with \|f-g\|_{{\rm Lip}}<\varepsilon we have \displaystyle|g(x)-g(y)|<\varepsilon d(x,y) for all x,y\in J . This lemma will be applied in our setting with B=f^{-1}\{0\} . With this preparation, we now proceed to the proof of our main theorem. A key feature of this proof is its extension of the coupling and

Read the complete text