Skip to main content
3 of 3
updated with answers to question
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

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

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.

Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133