The Cook Book

Recipe for the week of April 8 - 14

Another complex SPO: Pritikin's Pagoda

It's been more than 18 months since I last mentioned one of my favorite unsolved combinatorial puzzles in the recipe for Nov. 21-27, 1984, so I'll repeat it here. As explained earlier, the problem concerns invariant finitite configurations, known as stable periodic objects (SPOs), for Moore neighborhood, threshold 2 excitable cellular automata. But the puzzle can be formulated quite simply without any reference to the associated dynamics.

Namely, supposing that N colors are arranged in a cyclic color wheel, is it possible to paint a finite collection of sites in the two-dimensional integer lattice so that each site of a given color sees at least 2 of its 8 nearest neighbors with the preceding color from the wheel? It is not hard to design examples for N up to 5 with pencil and graph paper. N = 6 is more of a challenge; try it! This week's soup is an SPO for N = 7 designed a few years ago by Dan Pritikin, a combinatorist now at Miami of Ohio. It reminds me of a pagoda at least as much as Ursa Major suggests a bear. The frame around the image specifies the cyclic palette arrangement if anyone wants to verify the solution by hand. (A more sensible alternative is to use our WinCA software to check invariance under range 1 Box, threshold 2, 7 color Greenberg-Hastings dynamics.) Get the experiment dan7.xpt and initial bitmap dan7.bmp to watch the pagoda's evolution.

Remarkably, Pritikin went on to find exotic SPOs for 8, 9 and 10 colors, this last being featured in our recipe a year and a half ago. Get dan10.bmp to meet the record holder since there is still no known example with 11 or more colors. In contrast to Dan's 10-color giant, which sends out waves in four directions under GH dynamics, the pagoda is content to shimmer. For anyone with a combinatorial bent who would like to make new progress on this problem, I suggest that the most 'doable' and interesting result at this point would be to show there are no examples once N is sufficiently large. That seems to be the conjecture of most folks who have thought about the issue. Whatever methods might establish the existence of a finite maximal number of possible colors would undoubtedly yield dividends for other chapters in excitable CA theory.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !