Phoenix de Bruijn diagrams
This current de Bruijn analysis began some time ago when someone asked about that huge blinker
which appeared on the front cover of Scientific American along with one of Martin Gardner's
columns about Life. The immediate reaction was that they were something of a triviality, given that
the two tiles (shall we call them a and b?)
1 . 1 .
2 2 2 2
1 1 and 1 1
2 . . 2
could be strung out into chains, and could easily turn corners. Such a configuration is called a
Phoenix, for the obvious reason that each generation disappears completely as it generates its
successor. There are some other things which fulfill the requirement; many of them connect to figures
which remain constant from generation to generation. The barber pole is an example of one of them.
The phoenix condition is restrictive enough that the de Bruijn diagrams for some narrow strips and
low periods could be calculated on a PC. When Gerardo Cisneros worked out the spaceships, he also
extended the phoenix results, but their analysis was left until after the examination of the spaceships.
Now it is their turn; here are some results for freestanding figures. Quiescence at infinity in one
direction is imposed from the outset, but in the orthogonal direction it depends on whether the zero
tile is an isolated component or not.
width of
nonzero number of number of consolidated
column nodes links nodes components
--------- --------- --------- ----------- -----------
1,2,3 1 1 1 1
4 17 17 3 3
5 33 33 5 5
6 71 79 14 6
7 145 171 55 4
8 337 411 137 10
9 818 970 .. 44
10 1845 2187 .. 98
11 4556 5640 .. 91
12 11229 14607 .. 50
Having analyzed the spaceship diagrams in considerable detail, it is interesting to look at the
similarities and differences between the two systems.
In both cases, the minimum width is 4, but one of the first points for conjecture concerns its value in
general. Unless the diagram is forbidden - for example, by the first level having no links to zero, or
there exists an independent proof that the figures do not exist - such a width is to be expected. That it
is not too small is reasonable, and there is a (generally) extravagant upper limit (the maximum cycle
length in the first level diagram).
For spaceships, the smallest figure had three components; that zero was one of them implied that
there was no configuration of finite vertical extent. The same is true here; as with the spaceship, each
generation belongs to its own component. Unlike the spaceship, for which each component is
symmetric by vertical reflection, the two generations, strings of a tiles and their vertical reflections,
are mutual reflections, as is evident from examining the tiles displayed above.
At width 5, the only variation possible is the centering of the filaments of width 5, since they cannot
be bridged.
Two possibilities arise at width 6 --- the b tile can be used to shift the filament over by TWO cells,
and two new tiles can be used to line up a tiles against the outer walls of the strip. There are three
centerings for the a- and a'- filaments, but the center one admits of no variation. Consequently there
are six components: zero is still isolated, alpha and beta respectively hold the filaments hugging the
walls and crossing over, two for the generations of the central filament, and a gamma component.
At width 7 there are only four components - zero (1 consolidated node), alpha and beta, (with 14
consolidated nodes each) and gamma (with 26 consolidated nodes).
Width 8 is the significant width, of course, because it is the smallest width for which the zero tile is
no longer isolated; this is a consequence of the formation of a ring of four a-tiles, but unfortunately
there is still not enough wriggle room for attaching anything else to the ring - for example, to extend
its vertical edges. Such rings do have a compressed version, already visible at width 7, which fits
sideways into the strips, since it can be stabilized by connecting it to filaments, which can eventually
terminate on a mirror image or something else suitable. But nothing in the assemblage is yet
sufficient to make it freestanding.
However, it requires width 10 to get a zero-component with any appreciable versatility.
Width 8 also accomodates parallel avatar filaments, if they are packed just right; there are three
packings of two generations each, for a total of 6 isolated components; together with zero, alpha,
beta, and gamma (which are enlargements of their respective themes) making a total of 10.
Giving the possibility of twisting and turning, notably of the a-tiles abetted by the b-tiles, the phoenix
avatar structure is not so pronounced as for the spaceships. Nevertheless it is readily visible and
exerts a strong influence on the structure of the diagrams and the physical appearance of a phoenix.
At widths of eight and greater, the packing of multiple filaments, and the arbitrariness of their
placement with respect to one another generates a myriad of components. In particular, filaments 4
wide can be stacked in 3 different ways without interference. Thus width 8 has 6 isolated
components, 3 each for the two generations, which are pure cycles of the 8 joined pairs of a-tiles and
their reflection. For width 14, there will be 18, 9 each for the generations is which three filements
stretch alongside each other, and so on.
Slightly wider strips allow more relative displacements, up to all 8 possible shifts; but at the same
time shifting and joining become possible, resulting that the components no longer consist of a single
cycle, and thus become less and less isolated.
Doubtless the same phenomonon occurs for spaceships, but for them it was only beginning to
manifest itself at the widest strips which it was possible to examine.