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.