Stable patterns which are not glider-constructible

[HartmutHolzwart]

**Subject: Exploring the Preimage and Loop Landscape of Skew N x 1 Tori**

Hi everyone,

Following the landmark work on unconstructible still lifes and agar-based limitations by Ilkka Törmä and Ville Salo (https://arxiv.org), I would like to propose a systematic look into a specific 1D projection of Conway's Game of Life: **collapsing periodic agars into an N × 1 Skew Torus.**

Many space-filling, periodic 2D agars naturally collapse into highly compact 1D structures via a coordinate lattice projection (essentially a structural Hadamard-type matrix reduction). By focusing specifically on these N × 1 Skew Tori with a horizontal skew factor s, the 8-cell Moore neighborhood maps onto a 1D ring of length N with the following coordinate offsets:

[-1, +1] U [s-1, s, s+1] U [-s-1, -s, -s+1] (mod N)

While this strips away the standard 2D visual plane, it provides a highly structured, lower-dimensional environment for analyzing global transition graphs. The system can be modeled using the group ring F_2[t]/(t^N - 1), and the state-transition graph collapses cleanly into a quotient graph under the Dihedral group D_N.

### Observations from Small Sizes
Brute-force checks on small universes show that varying N and the skew s radically alters the topology of the quotient graph:

* **N=17, s=3:** The state space is dominated by the All-Dead (0) basin (~96%). The remaining states collapse into pure, static 1D Still Lifes (Solitons).
* **N=17, s=4:** The All-Dead basin expands to over 97%, but the system unlocks a true **Period-16 cycle** in the quotient graph (Period-32 in raw space) that deforms and breathes through different cell counts (3 -> 5 -> 4 -> 9 ...).
* **N=14, s=3:** Even dimensions yield true 1-loop classes that are pure **Phoenix Agars** (cell overlap between consecutive generations is exactly zero).

### SAT Solving Advantages
Given that searching for specific preimage structures or long grandfather chains is generally PSPACE-hard, the linear 1D chain topology of these skew tori seems uniquely suited for SAT solvers.

Because the All-Dead basin is overwhelmingly dominant, random bit assignments trigger immediate conflicts during Unit Propagation. A CDCL solver should be able to prune the 2^N search space exceptionally fast. Additionally, symmetry-breaking clauses can be strictly derived from the D_N orbits.

### Questions for Discussion
I am interested in using this framework to study:
1. **Quantitative Entropies:** Can we find a formal bound for the exponential decay of non-Garden-of-Eden states as N scales?
2. **Isolated Cycles:** What is the distribution of true, strict d-loops (isolated cycles with an In-Degree of exactly 1)?
3. **Asymptotic Behavior:** What kind of hidden structural properties or unexpected attractor behaviors emerge as N grows significantly larger, particularly when N is prime?

I would love to get your thoughts on this, or collaborate on optimizing the CNF clause generation for these asymmetric 1D neighborhoods to test larger rings (N >= 31).

Cheers,
Hartmut

[glider_rider]

Are any of these infinite patches also self forcing? I assume they are all self forcing if my conjecture is true. These are all transformations of known patches, with a few exceptions.
EDIT:
All of these are self forcing. I did a quick check.

The pond agar is not self-forcing, it has the following predecessor:

Code: Select all

x = 6, y = 6, rule = B3/S23:T6,6
obo$o2b2o$o$3bobo$2obo$3bo!

I'm guessing what you meant is that it doesn't have any predecessors on a 3x3 torus.

[Anivec]

Are any of these infinite patches also self forcing? I assume they are all self forcing if my conjecture is true. These are all transformations of known patches, with a few exceptions.
EDIT:
All of these are self forcing. I did a quick check.

The pond agar is not self-forcing, it has the following predecessor:

Code: Select all

x = 6, y = 6, rule = B3/S23:T6,6
obo$o2b2o$o$3bobo$2obo$3bo!

Ah, I didn’t think it was truly self forcing.

[400spartans]

153-cell unsynthesizable still life:

Code: Select all

x = 22, y = 23, rule = B3/S23
13b2o$5bo6bobo$4bobo5bo6b2o$4bo2bo2b2obo2b2o2bo$2b2ob2obo2bo2bo2bobo$
2bo2bo2b2o2bob2o2bo$4bo2bo2b2obo2b2o$3b2ob2o2bo2bo2bo3b2o$2bo2bo2b2o2b
ob2o2bo2bo$bobo2bo2bob2o2bob2obo$bob2ob2o2bo2bo2bo2bo$2bo2bo2b2o2bob2o
2bo$4bo2bo2b2obo2b2o$3b2ob2o2bo2bo2bo$2bo2bo2b2o2bob2o2bo$bobo2bo2bob
2o2bob2o$o2b2ob2o2bo2bobo$obo2bo2b2o2bo2bo$bobo2bo2bob2obo$3b2ob2o2bo
2bo$2bo2bo5b2o$3bobo$4bo!

and a LifeHistory view of a 245-cell self-forcing patch for this still life:

Code: Select all

x = 22, y = 23, rule = LifeHistory
13.2A$5.A6.A.A$4.A.A4.DCD5.2A$4.A2.C2DACDC2D2C2.A$2.2A.2CDC2DC2DC2DCD
A$2.A2.C2D2C2DCD2C2DC$3.DC2DC2D2CDC2D2CD$3.2CD2C2DC2DC2DC2D.2A$2.A2DC
2D2C2DCD2C2DA2.A$.A.C2DC2DCD2C2DCD2CDA$.A.ACD2C2DC2DC2DC2DC$2.A.DC2D
2C2DCD2C2DCD$3.DC2DC2D2CDC2D2CD$3.2CD2C2DC2DC2DC2D$2.A2DC2D2C2DCD2C2D
C$.A.C2DC2DCD2C2DC.2C$A.D2CD2C2DC2DC.A$A.C2DC2D2C2DC2.A$.ADC2DC2DCD2C
.A$3.ACD2C2DCD.A$2.A.DCD4.2A$3.A.A$4.A!

[I6_I6]

153-cell unsynthesizable still life:

Code: Select all

x = 22, y = 23, rule = B3/S23
13b2o$5bo6bobo$4bobo5bo6b2o$4bo2bo2b2obo2b2o2bo$2b2ob2obo2bo2bo2bobo$
2bo2bo2b2o2bob2o2bo$4bo2bo2b2obo2b2o$3b2ob2o2bo2bo2bo3b2o$2bo2bo2b2o2b
ob2o2bo2bo$bobo2bo2bob2o2bob2obo$bob2ob2o2bo2bo2bo2bo$2bo2bo2b2o2bob2o
2bo$4bo2bo2b2obo2b2o$3b2ob2o2bo2bo2bo$2bo2bo2b2o2bob2o2bo$bobo2bo2bob
2o2bob2o$o2b2ob2o2bo2bobo$obo2bo2b2o2bo2bo$bobo2bo2bob2obo$3b2ob2o2bo
2bo$2bo2bo5b2o$3bobo$4bo!

and a LifeHistory view of a 245-cell self-forcing patch for this still life:

Code: Select all

x = 22, y = 23, rule = LifeHistory
13.2A$5.A6.A.A$4.A.A4.DCD5.2A$4.A2.C2DACDC2D2C2.A$2.2A.2CDC2DC2DC2DCD
A$2.A2.C2D2C2DCD2C2DC$3.DC2DC2D2CDC2D2CD$3.2CD2C2DC2DC2DC2D.2A$2.A2DC
2D2C2DCD2C2DA2.A$.A.C2DC2DCD2C2DCD2CDA$.A.ACD2C2DC2DC2DC2DC$2.A.DC2D
2C2DCD2C2DCD$3.DC2DC2D2CDC2D2CD$3.2CD2C2DC2DC2DC2D$2.A2DC2D2C2DCD2C2D
C$.A.C2DC2DCD2C2DC.2C$A.D2CD2C2DC2DC.A$A.C2DC2D2C2DC2.A$.ADC2DC2DCD2C
.A$3.ACD2C2DCD.A$2.A.DCD4.2A$3.A.A$4.A!

Brilliant! That's a new record by 1 cell. How did you find that?

[NNlk05]

Brilliant! That's a new record by 1 cell. How did you find that?

They said on Discord:

i decided to fire up the ol' unsynth life search program, no new population improvements, but found a few unsynthesizable still lifes that i thought were interesting:
...
153-cell unsynthesizable still life
...

[HartmutHolzwart]

This might not fit very well well. I’m still investigating small nx1 skew tori and the evolution graph we get when restricting to equivalence classes under the torus symmetry group.

The 17x1, skew 4 torus has more symmetry than the usual dihedral, so the graph collapses to just 2072 equivalence classes. Exaclty on of them produces a 1-loop:

Code: Select all

x = 17, y = 1, rule = B3/S23:T17+4,1
10b2obob2o!

Or mapped out on a 17x17 torus

Code: Select all

x = 17, y = 17, rule = B3/S23:T17,17
10b2obob2o$6b2obob2o$2b2obob2o$bob2o10b2o$o10b2obobo$7b2obob2o$3b2obob2o$obob2o10bo$2o10b2obo$8b2obob2o$4b2obob2o$2obob2o$b2o10b2obo$9b2obob2o$5b2obob2o$b2obob2o$ob2o10b2o!

This is just an isolated pattern on the specific torus, but I guess it has only few predecessors on a full board and thus may lead to another still life that is non constructible. Could someone search for an actual predecessor?

[vilc]

This is just an isolated pattern on the specific torus, but I guess it has only few predecessors on a full board and thus may lead to another still life that is non constructible. Could someone search for an actual predecessor?

Here is a predecessor, found with JLS :

Code: Select all

x = 17, y = 17, rule = B3/S23:T17,17
10b2obob2o$6b2obob2o$2b2obob2o$bob2o10b2o$o9bobobobo$6bo5b2o$3b2o2b4o$
obobobobo7bo$2o7bobobobo$7b4o2b2o$4b2o5bo$2obobobo$b2o10b2obo$9b2obob
2o$5b2obob2o$b2obob2o$ob2o10b2o!

I found it by forcing most cells except for a small region in the center. Clearing larger regions seems to only produce variations on this predecessor (there are at least 15 of them), but there seems to be remarkably few of them considering the low density of this still-life. I am currently running more thorough searches.

[HartmutHolzwart]

Thanks for that! I was musing whether there could exist patterns that have “few” predecessors (but not are not really self-forcing), and could still give rise to non-glider-constructible still-lifes. Very speculative.

[dvgrn]

I was musing whether there could exist patterns that have “few” predecessors (but not are not really self-forcing), and could still give rise to non-glider-constructible still-lifes. Very speculative.

Yup, it seems possible that a still life can be found that doesn't contain any self-forcing patches, and yet all of its many non-still-life predecessors are grandfatherless, or great^N-grandfatherless for some N.

I'm thinking that this might be a more likely property as still lifes get larger -- like, patch together a large number of regions that each have only a few non-stable predecessors. But I really have no idea, of course. I don't think we collectively have very good intuition yet about what happens to predecessor counts for dense still lifes that are bigger than our current rewinding-search tools can conveniently handle.

[Chris857]

I also had a speculation that maybe some still life exists that somehow requires infinite gliders to create the sparks necessary to make it. Don't know if any such thing exists.

[vilc]

JLS just finished the search for all predecessors of this 17x17 board, and found 1140 of them. Sample predecessor, which less structure but noticeable motifs :

Code: Select all

x = 17, y = 17, rule = B3/S23:T17,17
b2o4bo2bob3obo$3o6bo6bo$obob2ob2o3bo3bo$bo4b2o4bo2b2o$4bob2o$2bo2bobob
2ob3obo$o2b2obo4b2o$4bo4bob2o$3o7bobob2o$o4bob3obo4bo$o8bo4bobo$ob2ob
2o8bo$4b2o4bob3obo$2bob2o8bo$2bo2bob2ob2o$4bo4b2o3bo$ob2o3bob2o!

Edit:

I also had a speculation that maybe some still life exists that somehow requires infinite gliders to create the sparks necessary to make it. Don't know if any such thing exists.

This would look like a glider-construction version of American Dream, I guess. A first step would be to find a similar pattern with a still-life instead of a map of America. One would then attempt to synthesise the infinite trail of sparks in parallel, plus the space dust (assuming the infinite predecessor does not contain an orphan, which is unlikely if the space-dust region is large).

[HartmutHolzwart]

Another torus rle without predecessor von a 19x1 skew 3 torus. Quite likely it has predecessors on the 19x19.

Code: Select all

x = 19, y = 19, rule = B3/S23:T19,19
3o2bobo2bob2obo$2bobo2bob2obo3b3o$bo2bob2obo3b3o2bo$bob2obo3b3o2bobo$2obo3b3o2bobo2bo$o3b3o2bobo2bob2o$b3o2bobo2bob2obo$o2bobo2bob2obo3b2o$obo2bob2obo3b3o$2bob2obo3b3o2bobo$b2obo3b3o2bobo2bo$bo3b3o2bobo2bob2o$2b3o2bobo2bob2obo$2o2bobo2bob2obo3bo$bobo2bob2obo3b3o$o2bob2obo3b3o2bo$ob2obo3b3o2bobo$obo3b3o2bobo2bobo$3b3o2bobo2bob2obo!

The other two are

Code: Select all

x = 19, y = 19, rule = B3/S23:T19,19
2o2bobo2bobo2b2o$bobo2bobo2b2o3b2o$o2bobo2b2o3b2o2bo$obo2b2o3b2o2bobo$2b2o3b2o2bobo2bobo$o3b2o2bobo2bobo2bo$b2o2bobo2bobo2b2o$2bobo2bobo2b2o3b2o$bo2bobo2b2o3b2o2bo$bobo2b2o3b2o2bobo$o2b2o3b2o2bobo2bo$2o3b2o2bobo2bobo$2b2o2bobo2bobo2b2o$o2bobo2bobo2b2o3bo$obo2bobo2b2o3b2o$2bobo2b2o3b2o2bobo$bo2b2o3b2o2bobo2bo$b2o3b2o2bobo2bobo$3b2o2bobo2bobo2b2o!

And

Code: Select all

x = 19, y = 19, rule = B3/S23:T19,19
obobo2bobobo2bobo$bo2bobobo2bobo2bobo$bobobo2bobo2bobobo$obo2bobo2bobobo2bo$2bobo2bobobo2bobobo$bo2bobobo2bobobo2bo$bobobo2bobobo2bobo$obo2bobobo2bobo2bo$2bobobo2bobo2bobobo$bobo2bobo2bobobo2bo$o2bobo2bobobo2bobo$obo2bobobo2bobobo$2bobobo2bobobo2bobo$bobo2bobobo2bobo2bo$o2bobobo2bobo2bobo$obobo2bobo2bobobo$bo2bobo2bobobo2bobo$bobo2bobobo2bobobo$o2bobobo2bobobo2bo!

Those look even more likely to have predecessors