Forcing nested [2D] patterns

It is straightforward to find constraints that allow nested patterns; the challenge is to find ones that force such patterns to occur. Many nested patterns (such as the one made by rule 90, for example) contain large areas of uniform white, and it is typically difficult to prevent pure repetition of that area. One approach to finding constraints that can be satisfied only by nested patterns is nevertheless to start from specific nested patterns, look at what templates occur, and then see whether these templates are such that they do not allow any purely repetitive patterns. A convenient way to generate a large class of nested patterns is to use 2D substitution systems of the kind discussed on page 188. But searching all 4 billion or so possible such systems with 2 × 2 blocks and up to four colors one finds not a single case in which a nested pattern is forced to occur. It can nevertheless be shown that with a sufficiently large number of extra colors any nested pattern can be forced to occur. And it turns out that a result from the mid-1970s by Robert Ammann for a related problem of tiling (see below) allows one to construct a specific system with 16 colors in which constraints of the kind discussed here force a nested pattern to occur. One starts from the substitution system with rules

{1  {{3}}, 2  {{13, 1}, {4, 10}}, 3  {{15, 1}, {4, 12}}, 4  {{14, 1}, {2, 9}}, 5  {{13, 1}, {4, 12}}, 6 {{13, 1}, {8, 9}}, 7  {{15, 1}, {4, 10}}, 8  {{14, 1}, {6, 10}}, 9  {{14}, {2}}, 10  {{16}, {7}}, 11  {{13}, {8}}, 12  {{16}, {3}}, 13  {{5, 11}}, 14  {{2, 9}}, 15  {{3, 11}}, 16  {{6, 10}}}

This yields the nested pattern below which contains only 51 of the 65,536 possible 2 × 2 blocks of cells with 16 colors. It then turns out that with the constraint that the only 2 × 2 arrangements of colors that can occur are ones that match these 51 blocks, one is forced to get the nested pattern below.