Bicoloring of $\mathbb{N}^2$, avoiding set of patterns, is the maximal limit density rational?

Question

Consider a bi-coloring of $\mathbb{N}^2$, (black and white), where we wish to maximize the limit (limsup) of the density of black squares in $[n] \times [n]$ as $n \to \infty$. Here, we identify each point with a square in the obvious way.

However, we have specified a finite set of black sub-patterns that are not allowed. That is, a pattern is a subset of $[k]\times [k]$, and any translation of this subset is not allowed in the coloring as all black squares.

For example, perhaps we do not allow two adjacent black squares. Then, a checkerboard coloring has limit density $1/2$.

Updated after answer

Q1: For any finite set of forbidden patterns, will the coloring(s) maximizing the density always be periodic? NO

Q2: Is there a finite set of forbidden patterns, such that the maximal limit density can only be obtained by a non-periodic coloring? YES

Q2b: Is there a finite set of forbidden patterns, such that the maximal limit density is an irrational number? Note that this requires a non-periodic pattern.

Q3: Is there a limit density that is not realizable, that is, there is a sequence of colorings, $c_1,c_2,\dots$ with increasing limit density, but the limit density is not realizable by any coloring?

Q4: Since this feels closely related to tiling problems and permutation patterns, might it be that the question "Does the set $F$ allow a coloring with limit density $\geq d$?" is undecidable? YES

According to bijection with Wang tiles, where all tiles having equal density. Deciding if a finite set of Wang tiles, tile the plane, is undecidable.

*Note that for every set of forbidden patterns, coloring all squares white is a valid coloring. *

Note: We only consider a finite set of forbidden patterns in all questions.

Answer 1

This is an improved version of the answer. The previous version (answering Q1 and Q2) is saved below.

We show now that Q2b is equivalent to the question whether a finite set of translational Wang tiles may have an irrational supremum density of occurences of some tile in a tiling of the plane. By a translational Wang tiles we mean Wang tiles which can be only translated but neither rotated nor reflected. (Thus usual Wang tiles are a partial case.)

$\underline{\Rightarrow}$. Assume that an irrational supremum density in our question may appear. Let $M$ be larger than the diameter of any prohibiting pattern. Cut the optimal arrangement into $M\times M$ squares, and call a $2M\times 2M$ square consisting of four such squares a tile (so neighboring tiles overlap by an $2M\times M$, $M\times 2M$, or $M\times M$ rectangle). Then any arrangement of tiles leads to a valid coloring iff the obvious rules how these tiles should be neighbored are satisfied; these rules simply tell which two tiles can be neighbors in which direction. One can easily see that such rules can be modelled by translational Wnag tiles (if needed, I may put more details, but I hope this is known). Finally, it is clear that some of these tiles should have an irrational density, if the total density is irrational.

$\underline{\Leftarrow}$. Conversely, to each system of translational Wang tiles where sime tile may appear with an irrational maximal densiry we put into correspondence the set of patterns in a following manner. We want to construct a corresponding set of patterns.

First of all, by a standard application of Koenig's lemma, it suffices to find arbitrarily large squares which may be colored with the density close enough to irrational $d$, and that no coloring has a density larger than $d$. To prove the lattter, we will use the Wang tiles condition.

Choose a $k$ much larger than the maximal size of a pattern, an even $n$ much larger than $k$, and an even $N$ much larger than $n$. To each pattern, biject some $n\times n$ square so that (i) each square used contains either $d$ or $d+1$ black squares, and it contains all boundary cells; (ii) this square contains $d+1$ black cells if it is of a distinguished type; (iii) any two squares used differ, even if we delete at most $k$ black squares from each. Call the corresponding squares complete.

1. Prohibit any $n\times n$ square which is not a subsquare of a shifted complete square.

2. For a $(N+n)\times (N+n)$ square one of whose $n\times n$ corners contains a black cell, only its $(2n-1)\times (2n-1)$ corner squares may also contain something black.

These restrictions yield that black cells group into clusters fitting into $n\times n$ squares, and such clusters are sufficiently far apart.

3. Finally, put the restrictions on the neighboring $n\times n$ tiles at distance $N$ apart (meaning that the position of the second $n\times n$ square is obtained from that of the first one by the shift by $N$). That is --- prohibit some $n\times (n+N)% and $(n+N)\times n$ arrangements where the bordering complete squares are of types which cannot be neighbors in this way. (Recall here that we enumerate all translational types, so rotation of a Wang tile changes its type!)

END_OF_CONSTRUCTION

Now, an aperiodic Wang tiling with irrational maximal possible density of a disinguished tile provides an arrangement which we want to prove to be optimal. Let $\alpha$ be its density.

Consider some optimal arrangement. We claim that it contains arbitrarily large squares which are organized as if they correspond to some lagre piece of a Wang tiling. Take any $ND\times ND$ square $Q$, where $D$ is large, and $Q$ has a density at least $\alpha$. Then, even if its clusters are arranged not that regularly, the restrictions we have yield that there exists a large subregion of $Q$ where they are arranged regularly, and the density is still large. This is what we needed (recall Koenig's lemma).

OLD VERSION. It seems that one may encode, say, Wang tiles by this type of restrictions. E.g. it answers Q2 (and Q1 in its present form) in the affirmative.

Proceed as follows. Assume you have $\leq n!$ translational types of yiles. Choose $N$ much larger than $n$.

1. Prohibit two black cells in one row or column of an $n\times n$ square.

2. Tell that all black cells in a $N\times N$ square should lie in some $n\times n$ square.

After that, the density is bounded by $n/N^2$, and we would like to reach this bound. For that, if we want a periodic arrangement of such density, each $N\times N$ square should contain exactly $n$ black cells in an $n\times n$ square, all in different rows and columns (we say that such $n\times n$ square is complete). We biject some of complete squares to the elements of a chosen set of Wang tiles and prohibit the rest.

3. Tell that in an $(n+N)\times (n+N)$ square, if one $n\times n$ corner contains $n$ cells, then only the other corners of size $n\times n$ may contain black cells.

This shows that the positions of complete squares in a periodic arrangement form a lattice generated by $(0,N)$ and $(N,0)$.

4. Finally, impose the restrictions on the neighboring tiles as you wish. That is --- prohibit some $n\times (n+N)$ and $(n+N)\times n$ arrangements where the bordering complete squares are of types which cannot be neighbors in this way. (Recall here that we enumerate all translational types, so rotation of a Wang tile changes its type!)

Now, since we know that there exists a set of Wang tiles admitting non-periodic tilings only, this shows that the maximal density arrangement can indeed be aperiodic.

Answer 2

I believe the answer to Q2b is yes, there does exist setups where the limit density is irrational.

Consider the Kari-Culik (Wang) tilings, and let $\Phi$ be projection onto the top label of each tile (treating $0'$ as $0$). Durand, Gamard, and Grandjean in http://arxiv.org/abs/1312.4126 show that for any Kari-Culik tiling $x$, the row averages of $\Phi(x)$ converge. Further, if $(\gamma_i)_{i\in\mathbb Z}$ is a vector of row averages,

$\gamma_i=f(\gamma_{i-1})$ where $f(t) = \begin{cases}2t&t\in[1/3,1)\\ t/3 & t\in[1,2]\end{cases}$.

$f$ is conjugate to an irrational rotation via the map $\varphi:[1/3,2]\to [0,1]$ given by $\varphi(t) = \frac{\log t+\log 3}{\log 6}$, and so since an irrational rotation gives a uniform orbit density, pushing forward through $\varphi$, we can compute the average

$\mathrm{Ave}(\Phi(x)) = \frac{5}{\log 216}$

for any Kari-Culik tiling $x$. I didn't think about the correspondence of Wang tilings and your problem in detail, but after translating the Kari-Culik tiles into the framework of your bi-coloring, an irrational average should be preserved.

Answer 3

You can give a negative answer to Q3 basically by compactness. This is a standard argument in "ergodic optimization". In fact you can do slightly better than what you ask for. You can achieve the maximal density not only in a $\limsup$ sense, but actually in a limit sense. That is, if $\rho$ is the maximal $\limsup$ density, you can produce a point where for every $\epsilon>0$, there is an $N$ such that every $N\times N$ block has density at least $\rho-\epsilon$. In particular, the (limit)-density of the configuration is $\rho$.

Proof: Let $F$ be the collection of forbidden all-one configurations and suppose these have maximum diameter $K$. Let $\xi_N$ be a legal configuration on $[1,N]^2$ with the maximal number of 1's. Let $\rho_N$ be the density of 1's in $\xi_N$ (the number of 1's divided by $N^2$). Let $\xi$ be any limit point of these configurations.

Claim 1: $\rho_N$ is a convergent sequence.

Proof: For $0\le k<N$, we have $(mN+k)^2\rho_{mN+k}\le (m+1)^2\rho_N N^2$ as if not, $\xi_{mN+k}$ contains an $N\times N$ sub-region with density exceeding $\rho_N$. We therefore obtain $\rho_{mN+k}\le (m+1)^2/m^2\rho_N$, so that $\limsup\rho_n\le \rho_N$. Hence $\lim\rho_n=\inf\rho_n$.

Now let $\epsilon>0$. Let $N$ be such that $(N+2K)^2/N^2<1+\epsilon$.

Claim 2: The restriction of $\xi$ to any $N\times N$ subregion has density at least $\rho-\epsilon$ of 1's.

Proof: Suppose not. Suppose that the restriction of $\xi$ to an $N\times N$ subregion $R$ has density less than $\rho-\epsilon$. Then since $\xi$ is the limit of a subsequence of $\xi_n$, there is a $\xi_n$, such that the restriction of $\xi_n$ to $R$ matches $\xi$. We now modify $\xi_n$: delete the $(N+2K)\times (N+2K)$ region surrounding $R$ and paste a copy of $\xi_N$ into the middle to produce $\tilde\xi_n$. This is a legal configuration. The number of 1's that have been removed is at most $(\rho-\epsilon)N^2+((N+2K)^2-N^2)<\rho N^2$. The number of 1's that have been added is $\rho_N N^2\ge \rho N^2$. Hence $\tilde\xi_n$ has greater density than $\xi_n$. This is a contradiction.