high density predecessors of the full board

[HartmutHolzwart]

Code: Select all

#Life 1.05
#P 0 0
........**...*...**...
.....*....*...**...*
....*.**...*...**.*.**
.......**.*.**...*...
....*....*...**.*.*….
...*.**...*....*...**.
......**.*.**...*…**.
...*....*...**.*.**...*
..*.**...*....*...**.*.
.....**.*.**...*....*.
..*....*...**.*.**...*
.*.**...*....*...**.*.
....**.*.**...*....*.
.*....*...**.*.**...*.
..**.*.

++this pattern can be extended

[amling]

An interesting implied question of what the minimum (infimal) density is. If I've counted correctly the above is 7/19, but you can get down to 1/3 with just stripes:

Code: Select all

x = 9, y = 3, rule = Life:T9,3
bo2bo2bob$bo2bo2bob$bo2bo2bob!

EDIT: An easy counting argument I think shows you can't beat 1/3: each live cell touches at most 6 dead cells (need 2 live neighbors to stay alive) and can therefore cover birthing on average a max of 6/3 = 2 (as each dead cell needs 3 live neighbors).

[HartmutHolzwart]

I’d say the minimum is attained with a maximum growth factor of three. So it’s pretty clear that the stripes are best possible. There are also obvious arrangements with pre-blocks in a rectangular grid or diagonal lines separated by 2. These are all L_2-only solutions, i.e. every on cell has two on neighbors.


@Keith Amling: The interesting question is the maximum density that one can get by using additional L_3 cells. Could you give that a try? I mean at finding infinite grids with a bigger density (using small skew fundamental regions). I think in the example above the vectors would be something like (1,-4) and (5,2) (positive coordinates are right down). If I count correctly, then in the fundamental regions there are 5 l_3 and 1 L_2 in the fundamental region, the rest is D_3.

I tried to get AI work on it, but still struggle in communicating with it.

[dvgrn]

The discussion so far is about parents of an all-ON board -- the T=-1 state. But the title only says "predecessors".

Are the any known results about T=-2 or earlier predecessors of the full board?

[ElijahKen]

The discussion so far is about parents of an all-ON board -- the T=-1 state. But the title only says "predecessors".

Are the any known results about T=-2 or earlier predecessors of the full board?

I've been curious about this as well, but the farthest back I've found is this T=-3 predecessor:

Code: Select all

x = 6, y = 6, rule = B3/S23:T12,6
ob2obo$ob2obo$ob2obo$ob2obo$ob2obo$ob2obo!

I'm also wondering: what is the smallest change in a p1 agar that converts it into a parent of the all-ON board?
EDIT: Ooh, here is an accidental T=-6 predecessor:

Code: Select all

x = 6, y = 6, rule = B3/S23:T12,6
o3bo$bo3bo$o3bo$bo3bo$o3bo$bo3bo!

Edit 2: T=-7, engineered:

Code: Select all

x = 4, y = 6, rule = B3/S23:T12,6
o2bo$b2o$o2bo$o2bo$b2o$o2bo!

Edit 3: T=-11:

Code: Select all

x = 12, y = 6, rule = B3/S23:T12,6
o3bo2bo3bo$2b2ob2ob2o$2o2bo2bo2b2o$2o2bo2bo2b2o$2b2ob2ob2o$o3bo2bo3bo
!

EDIT 4: JLS gives a T=-19 example, there are likely even farther back ones (particularly for bigger tori):

Code: Select all

x = 12, y = 6, rule = B3/S23:T12,6
bboo4boo$ooboobbooboo$boboobboobo$boboobboobo$ooboobbooboo$bboo4boo!

[HartmutHolzwart]

Success! I finally got Gemini to understand the pattern and generate a correct rle.

Code: Select all

#N 19x19_Snake_Igniter
#O Hartmut Holzwart
#C Minimal fundamental region scaled to a flat 19x19 orthogonal torus.
#C Perfect 180-degree rotational symmetry. Initial density: 36.84%.
x = 19, y = 19, rule = B3/S23:T19,19
2obob2o3bo4bo$
2bo3b2obob2o3bo$
3bo4bo3b2obob2o$
obob2o3bo4bo3bo$
bo3b2obob2o3bo$
2bo4bo3b2obob2o$
bob2o3bo4bo3b2o$
o3b2obob2o3bo$
bo4bo3b2obob2o$
ob2o3bo4bo3b2o$
3b2obob2o3bo4bo$
o4bo3b2obob2o$
b2o3bo4bo3b2obo$
2b2obob2o3bo4bo$
4bo3b2obob2o3bo$
2o3bo4bo3b2obob$
b2obob2o3bo4bo$
3bo3b2obob2o3bo$
o3bo4bo3b2obobo!

The one-line skew torus version:

Code: Select all

#N 19x1_Snake_Igniter
#O Hartmut Holzwart
#C [[ TOPOLOGY CYLINDER ]]
#C [[ SKEW 6 ]]
x = 19, y = 1, rule = B3/S23:T19,1,6
2obob2o3bo4bo!

Edit: Gemini says this is the only solution at this size up to symmetry, so likely the smallest case with density > 1/3. Challenge: Do better than 7/19.

[ElijahKen]

...
Challenge: Do better than 7/19.

Doesn't this descendant of the last code block in my previous post have density 96/(24*24) = 1/6 < 7/19?
<removed, because not relevant>
Or did you mean 1 generation parents with density < 7/19? I'm rather confused.
EDIT: Oh, you meant parents that are denser than 7/19. Nevermind.

[amling]

Mmm, somehow my brain mapped "predecessor" to "parent". I think there are quite a few obvious questions here, namely:

(*) Highest parent density. This is determined by ratio of what HH called "L_2" to "L_3" cells and a quick LLSSS search I believe can show it is not possible to have all L_3 cells. Perhaps more thought on this once I have more examples and some guess at a bound.

(*) Highest and lowest ancestor densities.

(*) Deepest ancestor (i.e. most generations back).

I dusted off my old "rlagar" project which I had previously used to enumerate all small-lattice-volume agars and analyze them in terms of their spatial connection ranks, their periods, etc. It's easy enough to repurpose it to enumerate and trace the evolution of all small (spatially) periodic patterns until they either loop in time or reach all cells on. For an hour or so of hacking and like 10 minutes of computer time I believe I have enumerated all up to volume 30. I might hope that given time on the big computer I could do up to volume 43 (1 TB memory is 2^43 bits and my algo uses essentially 2^V bits). TBD if I'm right and willing to wait it out. Until then, up to volume 30 turned up...

(*) A max parent density of 7/19 (the one above).

(*) A max ancestor density of 2/3. The smallest/first is at volume 6:

Code: Select all

x = 6, y = 1, rule = B3/S23:T6,1
4o2b!

Code: Select all

x = 22, y = 8, rule = B3/S23:T24,8
4o2b4o2b4o2b4o$4o2b4o2b4o2b4o$4o2b4o2b4o2b4o$4o2b4o2b4o2b4o$4o2b4o2b4o
2b4o$4o2b4o2b4o2b4o$4o2b4o2b4o2b4o$4o2b4o2b4o2b4o!

(*) A min ancestor density of 1/6. The smallest/first is at volume 12:

Code: Select all

x = 6, y = 2, rule = B3/S23:T6,2
bo4b$o5b!

Code: Select all

x = 20, y = 12, rule = B3/S23:T24,12
bo5bo5bo5bo$o5bo5bo5bo$bo5bo5bo5bo$o5bo5bo5bo$bo5bo5bo5bo$o5bo5bo5bo$b
o5bo5bo5bo$o5bo5bo5bo$bo5bo5bo5bo$o5bo5bo5bo$bo5bo5bo5bo$o5bo5bo5bo!

(*) A max depth of 40. The smallest/first is at volume 24:

Code: Select all

x = 12, y = 2, rule = B3/S23:T12-4,2
b3ob2obo2bo$o2bobo2bo3b!

Code: Select all

x = 24, y = 12, rule = B3/S23:T24,12
b3ob2obo2bob3ob2obo2bo$o2bobo2bo3bo2bobo2bo$o2bob3ob2obo2bob3ob2o$o3bo
2bobo2bo3bo2bobo$b2obo2bob3ob2obo2bob3o$bo2bo3bo2bobo2bo3bo2bo$b3ob2ob
o2bob3ob2obo2bo$o2bobo2bo3bo2bobo2bo$o2bob3ob2obo2bob3ob2o$o3bo2bobo2b
o3bo2bobo$b2obo2bob3ob2obo2bob3o$bo2bo3bo2bobo2bo3bo2bo!

[HartmutHolzwart]

Great finds! Now the challenge for the max density parent still remains. There are arithmetic restrictions on the numbers of L_2, L_3, D_3 allowed, hence the geometry of the lattice. So one direction would be to proof there are no pure L_3 only geometries. The other would be to search suitable parents with higher density on nx1 skewed tori. Could you give that a try (67 x 1 would be the next amenable candidate)?

I want to post the math later on when I get to it.

[amling]

So one direction would be to proof there are no pure L_3 only geometries.

I had this when I posted earlier but didn't write it up out of laziness:

L_3-only full board predecessor is the same as still life in S3/B01245678. LLSSS shows a height limit on width 5 patches [1]:

Code: Select all

$ cat W5.in
| WWWWW |
| WWWWW |
$ rlife llsss --rule 'S3/B01245678' p1 W5.in --left-edge any --right-edge any --ends none
...
20260826 08:00:01 [INFO] Completed w_pos 17: 0 B [-200.00%], 3.096424ms [-102.17%]
...
20260826 08:00:01 [INFO] Last firstest partial RLE:
20260826 08:00:01 [INFO] x = 9, y = 17, rule = B01245678/S3History
20260826 08:00:01 [INFO] F.B3AB.F$F.5B.F$F.A3BA.F$F.B3AB.F$F.2BA2B.F$F.5B.F$F.AB2AB.F$F.2B2AB.
20260826 08:00:01 [INFO] F$F.5B.F$F.2A2BA.F$F.2AB2A.F$F.4BA.F$F.BA3B.F$F.3ABA.F$F.3BAB.F$F.4BA
20260826 08:00:01 [INFO] .F$F.3A2B.F!
...
20260826 08:00:01 [INFO] Total: 152.125574ms (898.617ms user, 349.912ms sys)
20260826 08:00:01 [INFO] Done

Code: Select all

x = 9, y = 17, rule = B01245678/S3History
F.B3AB.F$F.5B.F$F.A3BA.F$F.B3AB.F$F.2BA2B.F$F.5B.F$F.AB2AB.F$F.2B2AB.
F$F.5B.F$F.2A2BA.F$F.2AB2A.F$F.4BA.F$F.BA3B.F$F.3ABA.F$F.3BAB.F$F.4BA
.F$F.3A2B.F!

I.e. there are no possible 5x18 patches. Therefore also no full planes, therefore also no full planes with 2 ranks of shift symmetries, i.e. no repeating lattice patterns.

For completeness, LLSSS's requirements for such a patch near the boundary are that each partial CA neighborhood must be extensible to a full 10 cell one (9 present and 1 future), but the extensions do not have to be compatible in any way between multiple neighborhoods. "Extends to a full plane" is at least as strong as this which is what we need for the above.

There are arithmetic restrictions on the numbers of L_2, L_3, D_3 allowed, hence the geometry of the lattice. ... Could you give that a try (67 x 1 would be the next amenable candidate)?

I want to post the math later on when I get to it.

2^67 is too much RAM and even if that wasn't a problem, 2^67 is too many states and will take too long for the exhaustive searcher, not to mention that there are several non-isomorphic (up to D_4 rotational symmetry) lattices on 67x1, depending on the skew (if my analyzer is correct, there are 18, with skews: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 16, 18, 23, 29).

I could try checking evolutions of random states but it seems reasonably unlikely to stumble on a parent of the full board. Maybe it's SAT solver time? It would be (for me) a bunch of annoying code to write and I just have no idea if it would have a chance given total lack of intuition about SAT solver feasible scale.

Your post seems to suggest you have some reason for wanting 67x1 and am I very keen to hear it.



Overnight volumes 31-37 completed, turning up...

(*) Higher max ancestor density of 13/18 at volume 36:

Code: Select all

x = 12, y = 3, rule = B3/S23:T12,3
12o$6obo2bob$6o6b!

Code: Select all

x = 36, y = 18, rule = B3/S23:T36,18
36o$6obo2bob6obo2bob6obo2bo$6o6b6o6b6o$36o$6obo2bob6obo2bob6obo2bo$6o
6b6o6b6o$36o$6obo2bob6obo2bob6obo2bo$6o6b6o6b6o$36o$6obo2bob6obo2bob6o
bo2bo$6o6b6o6b6o$36o$6obo2bob6obo2bob6obo2bo$6o6b6o6b6o$36o$6obo2bob6o
bo2bob6obo2bo$6o6b6o6b6o!

(*) Longer ancestor depth of 58 at volume 36:

Code: Select all

x = 12, y = 3, rule = B3/S23:T12-6,3
obobo4b2o$o3bob2obo$2o2bo2b3o!

Code: Select all

x = 36, y = 18, rule = B3/S23:T36,18
obobo4b2obobobo4b2obobobo4b2o$o3bob2obo2bo3bob2obo2bo3bob2obo$2o2bo2b
3o2b2o2bo2b3o2b2o2bo2b3o$3b2obobobo4b2obobobo4b2obobobo$2obo2bo3bob2ob
o2bo3bob2obo2bo3bo$b3o2b2o2bo2b3o2b2o2bo2b3o2b2o2bo$obobo4b2obobobo4b
2obobobo4b2o$o3bob2obo2bo3bob2obo2bo3bob2obo$2o2bo2b3o2b2o2bo2b3o2b2o
2bo2b3o$3b2obobobo4b2obobobo4b2obobobo$2obo2bo3bob2obo2bo3bob2obo2bo3b
o$b3o2b2o2bo2b3o2b2o2bo2b3o2b2o2bo$obobo4b2obobobo4b2obobobo4b2o$o3bob
2obo2bo3bob2obo2bo3bob2obo$2o2bo2b3o2b2o2bo2b3o2b2o2bo2b3o$3b2obobobo
4b2obobobo4b2obobobo$2obo2bo3bob2obo2bo3bob2obo2bo3bo$b3o2b2o2bo2b3o2b
2o2bo2b3o2b2o2bo!

[HartmutHolzwart]

Wow! These deep predecessors are very impressive.

Coming back to the max density immediate parents:
1) thanks for the proof that L_3 only is not possible

2) Maybe you can find other cases the actually use L_3 and are not record? I still think the 19x19 is the minimum example with density > 1/3. If you could try out some of the smaller lattice geometries, that would also be helpful to get a better understanding on potential record holders

3) For the 19x1 I actually used a simple Python script: Generate all length 19 rle strings with run length less than 2 for “o” and less than four for “b”. Test only those skews where the original and the skew version don’t overlap on two consecutive on cells (this would lead to a block in the final pattern which can be excluded as it leads to non-dense islands (I think). Restrict the skew to 10. Then there are only two mirror symmetric version of the pattern I posted (which I found earlier on manually). This strategy fails for any n x 1 torus with smaller n.

[amling]

I have done some of my own math about L_2 and L_3. Some arithmetic gives dead cells = 2 L_2 + 5/3 L_3 and so L_3 has to be divisible by 3. We're concerned with maximizing L_3/L_2. The 7/19 above is L_3=6, L_2=1 and so we only need to consider L_3/L_2 >= 6 (really > 6 but I've included 6s in the table anyway). Up to lattice volume 75 I think all we've got is:

Code: Select all

L_2   L_3    D    V     L/V   status
---   ---   --   --   -----   ------
  1     6   12   19    7/19   found
  1     9   17   27   10/27   disproven
  1    12   22   35   13/35   disproven
  1    15   27   43   16/43   unknown
  1    18   32   51   19/51   unknown
  1    21   37   59   22/59   unknown
  1    24   42   67   25/67   unknown
  1    27   47   75   28/75   unknown
  2    12   24   38   14/38   unknown (ties 7/19)
  2    15   29   46   17/46   unknown
  2    18   34   54   20/54   unknown
  2    21   39   62   23/62   unknown
  2    24   44   70   26/70   unknown
  3    18   36   57   21/57   unknown (ties 7/19)
  3    21   41   65   24/65   unknown
  3    24   46   73   27/73   unknown

I assume you're picking 67 aiming for L_2=1, L_3=24 but what about the smaller rows like L_2=1, L_3=15, V=43? Do you know something about them I do not?

[HartmutHolzwart]

If one counts the number of edges between live cells, one gets 2*L_2+3*L_3 edges. Every edge is counted twice, so this sum must be even, thus the number of L_3 must be even. That means L_3 is divisible by 6. This in turn excludes some of the possibilities you listed, like 43x1.

[Ilkka Törmä]

Ville Salo and I actually have a tool, Griddy, that can solve such density problems (among other things). I just used it to verify that 7/19 is the maximum density of parents of the full board. The code, commented to explain what's going on, is this:

Code: Select all

-- Use the king topology on the 2D grid
%topology king
-- Use the binary alphabet; the encoding is a technical detail that improves speed here
%alphabet encoding=tally 0 1
-- There are commands for minimizing the density, but we want to maximize it, so we swap the weights
%set_weights {0:1 1:0}
-- Define the GoL cellular automaton:
-- For each cell x, let num be the number of 1-cells in the open neighborhood of x.
-- If num is 3, or if num is 2 and x is live, then x becomes live; otherwise it becomes dead.
%CA gol
x let num := #n[Bo 1 x] n=1 in if num == 3 | (x = 1 & num == 2) then 1 else 0
-- The all-1 configuration (more precisely, the singleton set containing only this configuration): for all cells x, x is live
%sft all_one Ax x=1
-- Compute the preimage of all_one by gol
%preimage ones_preim gol all_one
-- Compute a lower bound for the minimum density of dead cells.
-- @verbose prints some extra info along the way.
-- @rationalize attempts to use exact rational arithmetic.
-- The other arguments are technical.
-- In the end, this should print 12/19.
%density_lower_bound ones_preim symmetries=[rot90 refl0] solver=HiGHS_simplex @verbose@rationalize
(1,0); (0,0) (1,0) (-1,0) (2,0) (0,1) (1,1) (0,-1) (1,-1) (-1,1) (-1,-1) (2,1) (2,-1) (0,2) (1,2) (0,-2) (1,-2)

When rationalization succeeds, this outputs:

Code: Select all

Weights set to {'0': 1, '1': 0}
Computing lower bound for density in ones_preim
Computing pattern variables
Done with 707 variables, now adding constraints
Node (): considering patterns of size 21
Done with 441 constraints in 0.8479390144348145 seconds, now solving
Solved in 0.029064416885375977 seconds, bound 0.631578947368421
Attempting to rationalize
Succesfully rationalized solution, bound 12/19
Bound 12/19
Calculation took 1.622818946838379 seconds.

[HartmutHolzwart]

1) could the argument be condensed into a human readable form? Could there be infinite quasi-crystal like structures that obstinat similar or higher densities, i.e., the result is not restricted to lattices with a finite fundamental region?
2) mapping out the possible pairs of densities for consecutive generations of CGOL boards as a subset of [0,1]x[0,1], how would that look like as a graph?
3) Visualizing the cube of possible density triples of three consecutive CGOL generations, how would that picture luck liebe in the 3-dimensional unit cube? What are the known results?

[Ilkka Törmä]

1) could the argument be condensed into a human readable form? Could there be infinite quasi-crystal like structures that obstinat similar or higher densities, i.e., the result is not restricted to lattices with a finite fundamental region?

The result holds for all parents, periodic or not. The program constructs something called a "discharging argument". It means that we first place a given amount of "charge" on the cells depending on their state (so live cells get 0 and dead cells get 1). Then we find a set of deterministic local rules that redistribute the charge, such as "if this cell is live, its east neighbor is dead and its north neighbor is dead, then send 2/9 charge to the east neighbor". These rules are applied simultaneously to every cell. If every cell ends up with charge at least X in every valid pattern, then the density of every infinite pattern must be at least X. Because the rules are local (have finite range), it's enough to check a finite set of locally valid finite patterns.

You can see the discharging rules it finds with the flag `@show_rules`, and you can try to simplify them with `@simplify`. It seems to end up with around 40 rules, but has trouble converting the floating point numbers to rationals for some reason. And you'll still have to do the case analysis yourself, so it's still not exactly human readable.

[HartmutHolzwart]

OK. I’d still like to have something human readable, but I guess that is just impossible given the nature of the problem.

Could you find further full board parents with a density between 1/3 and 7/19? So with a higher ratio of L_2?

[HartmutHolzwart]

cgol_refined_density_map.png (300.02 KiB) Viewed 281 times

A plot of my current understanding of the map of possible density pairs for consecutive CGOL generations. The point on thee upper right should be (3/8,1), not what is there.

What it actually means: I’m pretty sure that the density pairs in the green triangle can be realized by actual boards, at least the rational points. We know that we cannot get (3/8,1), but at least (7/19,1). Anything in the triangle between (1/3,1), (7/19,1) and (1,0) might be possible, in the triangle (7/19,1) , (3/8,1) and (1,0) I’m pessimistic.

So new challenge: Find more examples in one of those triangles or proofs pairs to be impossible.

[HartmutHolzwart]

Does this 20x1 skew torus pattern work?

Code: Select all

x = 20, y = 1, rule = B3/S23:T20-7,1
2obobo3bo3bo3bo2b!

Seems so. Which would mean that more patterns exist that populate the interesting zone in my density plot.

Another one:

Code: Select all

x = 20, y = 1, rule = B3/S23:T20-7,1
2obo2bo2bo2bo4bo2b!

Now switching to longer skewed tori

[Chris857]

But stepping ahead 1 generation, not all the cells are alive (one is dead in each)

[HartmutHolzwart]

The Intention was to show that there are other solutions in the high density regime that break the “trivial barrier” d_1 <= 1-3*d_0.


Here is another such pattern in in the regime above the trivial barrier. It is just a band created out of multiple copies the 19x1 solution padded a bit to the left and right to minimize loss.

Code: Select all

#N M15 Verified Density Threshold Breaker
#O Reconstructed AI/Human Collaboration
#C Assembled strictly via the core-padding blueprint.
x = 308, y = 1, rule = B3/S23:T308-6,1
3b2o2b2obob2o3bo4bo3b2obob2o3bo4bo3b2obob2o3bo4bo3b2obob2o3bo4bo3b2o
bob2o3bo4bo3b2obob2o3bo4bo3b2obob2o3bo4bo3b2obob2o3bo4bo3b2obob2o3bo
4bo3b2obob2o3bo4bo3b2obob2o3bo4bo3b2obob2o3bo4bo3b2obob2o3bo4bo3b2ob
ob2o3bo4bo3b2obob2o3bo4bo3bb6o9b!

[HartmutHolzwart]

A family of high average density boards, i.e. near full boards based on skewed n x 1 tori with skew 3, based on variations of the 19 x 1 solution.

Code: Select all

#N High-Density 21x1 Skew Torus Precursor
#O AI & Peer Collaboration
#C Combined Density: 8/21 + 20/21 = 28/21 = 4/3
#C Corrected native LifeViewer rule-suffix topology for horizontal skew.
x = 21, y = 1, rule = B3/S23:T21+3,1
o2bo3bobobobo3bo2bo!

Code: Select all

#N Expanded 59x1 Plastered Skew Torus Precursor (Perfect Symmetry)
x = 59, y = 1, rule = B3/S23:T59+3,1
o2bo3bobobo3bo2b2o2bo3bobobobo3bo2b2o2bo3bobobo3bo2bo!

Code: Select all

#N Infinite Progression Plaster Suite: 97x1 Torus Precursor (Verified Matrix)
#O AI & Peer Collaboration
#C Combined Density: 34/97 + 96/97 = 130/97 = 1.3402 (> 4/3)
#C Calculated directly from coordinates via Python RLE Tokenizer.
x = 97, y = 1, rule = B3/S23:T97+3,1
o2bo3bobo3bo2bo2bo2bo3bobo3bo2bo2bo3bobobobobobobo3bo2bo2bo3bobo3bo
2bo2bo2bo3bobo3bo2bo!