Unproven conjectures

[g0t0]

Conjecture: there are not oscillator with period >2 in B8/S<any> rules(accepting infinity patterns such as agar)

Edit:
Overturn! this is a p6 oscillator:

Code: Select all

x = 6, y = 3, rule = B8/S234568
6o$ob4o$6o!

[Disaster16439]

Conjecture: there are not oscillator with period >2 in B8/S<any> rules(accepting infinity patterns such as agar)

Edit:
Overturn! this is a p6 oscillator:

Code: Select all

x = 6, y = 3, rule = B8/S234568
6o$ob4o$6o!

Could the conjecture still hold if we add the restriction that the period is odd?

[EvinZL]

Conjecture: there are not oscillator with period >2 in B8/S<any> rules(accepting infinity patterns such as agar)

Edit:
Overturn! this is a p6 oscillator:

Code: Select all

x = 6, y = 3, rule = B8/S234568
6o$ob4o$6o!

Could the conjecture still hold if we add the restriction that the period is odd?

p3:

Code: Select all

x = 5, y = 5, rule = B8/S0123456-c7c8
b3o$b3o$5o$obobo$5o!

EDIT: p5

Code: Select all

x = 14, y = 8, rule = B8/S0123-y4-ce567c8
4b7o$b7ob5o$b2ob10o$b5o2bob4o$4obo2b5o$10ob2o$5ob7o$3b7o!

p7

Code: Select all

x = 9, y = 11, rule = B8/S01234567c8
6b3o$6b3o$6b3o$6b3o$9o$2ob4obo$5ob3o$4b3obo$4b5o$4b5o$4b5o!

[NNlk05]

For every finite Game of Life pattern with n live cells, the next generation contains at most 3n−6 live cells.

I don't have a mathematical proof for this; I just know that a straight line with n cells (n > 2) has a population of 3n-6 in the next generation, and that looks pretty optimal. Has work on this been done before?

See:

i'm pretty sure it can be proven pretty easily that the maximum amount of cells from one generation to the next in B3/S23 is 3p, where p is the population at the before-generation.
here are some agars that showcase this maximum:

Code: Select all

x = 7, y = 9, rule = B3/S23:T9,9
o2bo2bo$o2bo2bo$o2bo2bo$o2bo2bo$o2bo2bo$o2bo2bo$o2bo2bo$o2bo2bo$o2bo2b
o!
[[ SHOWGENSTATS ]]

Code: Select all

x = 9, y = 9, rule = B3/S23:T9,9
bo2bo2bo$2bo2bo2bo$o2bo2bo$bo2bo2bo$2bo2bo2bo$o2bo2bo$bo2bo2bo$2bo2bo
2bo$o2bo2bo!
[[ SHOWGENSTATS ]]

ćode+x = 9, y = 9, rule = B3/S23:T9,9
bo2bo2bo$o2bo2bo$o2bo2bo$2bo2bo2bo$2bo2bo2bo$bo2bo2bo$bo2bo2bo$o2bo2b
o$o2bo2bo!
code+
now, what about extending this question to ask what the maximum amount of cells from one generation to two generations after is in B3-S23_ what about three generations, four generation, and so on_

[HartmutHolzwart]

You might not have recognized it, but I spent some time on the topic, see the patterns forum. In skew tori, there are basically three regimes that achieve maximum growth rates. The 3x3 torus with a block, the 3x1 with a stripe and 3x1 with skew 1. The last two can be mixed.

https://conwaylife.com/forums/viewtopic.php?t=7395

[g0t0]

For every finite Game of Life pattern with n live cells, the next generation contains at most 3n−6 live cells.

I don't have a mathematical proof for this; I just know that a straight line with n cells (n > 2) has a population of 3n-6 in the next generation, and that looks pretty optimal. Has work on this been done before?

S3 is seemed to be useless.

How about the same conjecture in B3/S2?

[g0t0]

Conjecture: the are no infinite growth in a row of n cells.

[g0t0]

What about a hypothetical spaceship that will certainly produce lots of gliders when destroyed? As an extreme example, we could use 0E0P metacells to emulate a chaotic spaceship from another (preferably explosive) rule, and I strongly doubt you can collide such metaships together (either in a way that simulates another rule or otherwise) without releasing gliders in every direction, making cleanup almost impossible. There is also almost certainly no way that you can clean up the released gliders using other metaships without releasing gliders in every direction. There will almost certainly be gliders that will be permanently out of reach of the RCT - no mechanism could be used to catch them.

If someone were to try this (using some futuristic supercomputer, since there is no way modern desktop computers could begin to run this), make sure that the emulated spaceship cannot cleanly annihilate copies of itself.

If this method turns out to be insufficient somehow, we might be able to engineer a spaceship that will always release gliders in every direction.

EDIT: We could also - as an example firmly outside of plausibility - make a spaceship that is so ridiculously large that any collision involving it will end up producing IceNine. (I only came up with this after seeing my post count at 137). Since IceNine, if it exists at all, is an unstoppable quadratic growth pattern, this would make it impossible for the spaceship to be cleanly destroyed at all, let alone by copies of itself.

0E0P metacell ships can hit unexpectedly and explode!

[g0t0]

Conjecture: there are not oscillator with period >2 in B8/S<any> rules(accepting infinity patterns such as agar)

Edit:
Overturn! this is a p6 oscillator:

Code: Select all

x = 6, y = 3, rule = B8/S234568
6o$ob4o$6o!

Could the conjecture still hold if we add the restriction that the period is odd?

p3:

Code: Select all

x = 5, y = 5, rule = B8/S0123456-c7c8
b3o$b3o$5o$obobo$5o!

EDIT: p5

Code: Select all

x = 14, y = 8, rule = B8/S0123-y4-ce567c8
4b7o$b7ob5o$b2ob10o$b5o2bob4o$4obo2b5o$10ob2o$5ob7o$3b7o!

p7

Code: Select all

x = 9, y = 11, rule = B8/S01234567c8
6b3o$6b3o$6b3o$6b3o$9o$2ob4obo$5ob3o$4b3obo$4b5o$4b5o$4b5o!

No INT rule.

[NNlk05]

Conjecture: the are no infinite growth in a row of n cells.

Overturn by counterexample

[rabbit]

I would assume that g0t0 is talking about full 1xN rectangles, rather than 1xN patterns of any variety.

I checked all filled boxes from 1x1 up to 1x10000 with a small apgsearch stdin script and none of them yielded linear growth. It appears that, on the whole, they tend to settle into repetitive behaviour that leaves little room for switch engines to appear, although I'm not sure if they fully repeat or not -- for example, 1x4330 is the smallest of the 1xN boxes that produces MWSSes.

[LuveelVoom]

Does there exist an unsynthesizable spaceship?

I think the best way to go about proving this would be to find an agar with a p2 generator and bottom eater, prove that it cannot be synthesized (but can be stabilized!) due to requiring infinite extension at the sides to synthesize, then stabilize it inside of a c/2o spaceship.

[g0t0]

I would assume that g0t0 is talking about full 1xN rectangles, rather than 1xN patterns of any variety.

I checked all filled boxes from 1x1 up to 1x10000 with a small apgsearch stdin script and none of them yielded linear growth. It appears that, on the whole, they tend to settle into repetitive behaviour that leaves little room for switch engines to appear, although I'm not sure if they fully repeat or not -- for example, 1x4330 is the smallest of the 1xN boxes that produces MWSSes.

Look this: https://oeis.org/A061342 https://oeis.org/A152389

If some lines behave infinite growth, is there a -1 will be in these sequences?

[g0t0]

A lively pattern in Life is a pattern where every live cell survives to the next generation (because they all have 2 or 3 live neighbours). By this definition, still-lives are the lively patterns where no dead cell has exactly 3 neighbours so no birth can occur.

The above describes 1-lively patterns. An N+1-lively pattern is one with an N-lively successor: generation 3 of the pi-heptomino (holding that pi is gen 0) aka "house" is 2-lively, because it's lively and so is its successor.

Conjectures:

• No pattern in Conway's Game of Life is 3-lively or higher except still-lives.

• No pattern in Conway's Game of Life is w-lively except still-lives (an example of a non-SL pattern like this being the shoots of Life without Death).

hotdogPi has attempted a proof that the only >=3-lively patterns are still-lives: "in generation 0 all cells must be S2, but this cannot be true in generation 1 because a B3 just occurred". Is this proof correct? If not, can a good proof or disproof be found?

It's quite simple.

Code: Select all

x = 26, y = 13, rule = LifeHistory
$11.C8.CAC$2.3A5.3A7.3A$.A2.A4.A2.A6.A2.A$.2A6.2A8.2A3$2.ABA$2.A2B$.A
2.A$.2A!

The cell born in generation 2 must next to a cell born in generation 1.
Then the cell born in generation 1 must die.

Edit:

[catagolue][/catagolue]
The pre-block is a counterexample for both conjectures:

Code: Select all

x = 2, y = 2, rule = B3/S23
2A$.A!

You've done it! And of course the reward of a taskmaster to his subjects is to set them another task.

A spirited pattern in Life is a pattern where all live cells have 2 or 3 neighbours (so they all survive) and at least one dead cell has 3 neighbours (so it will come alive in the next generation). The set of spirited patterns in Life is the set of induction coils with still-lives excluded, or the set of lively patterns with still-lives excluded.

A 1-spirited pattern immediately evolves into a non-spirited pattern, e.g. the preblock evolving into a block. An N+1-spirited pattern has an N-spirited successor: house is 2-spirited, because its gen-0 form is spirited and so is its gen-1 form.

Conjectures still open:

• There is no 3-spirited pattern. (thus there is no N-spirited pattern with N > 3, because they rely on the existence of 3-spirited patterns somewhere down the line)

• There is no w-spirited pattern. (e.g. the shoots from Life without death)

[g0t0]

For every finite Game of Life pattern with n live cells, the next generation contains at most 3n−6 live cells.

I don't have a mathematical proof for this; I just know that a straight line with n cells (n > 2) has a population of 3n-6 in the next generation, and that looks pretty optimal. Has work on this been done before?

Proof of pop <= 3n:



The sum of all numbers is pop and number in every cell <= 3.
Q.E.D.

[g0t0]

Conjecture:

For infinite 50% soup, the limit of the density when time->inf exists.

[NNlk05]

Conjecture:

For infinite 50% soup, the limit of the density when time->inf exists.

Around 37%, IIRC. In sparser soups, imminent growth and/or the potential quadratic growth may skew it.

[LuveelVoom]

I had a bunch of leftover credits, so I asked Claude Opus 5.5 to take a shot at the oscillating agar density conjecture; it did not solve it, but it claims to have established a new upper bound of 16/31 ≈ 0.516, much lower than amling's 1176/2087 bound ≈ 0.563.

Now, I have not verified this proof. Please do not believe that this proof is valid. It is very likely that it might just be flat out wrong. However, I am posting it here in case someone can verify it and determine that the upper bound has in fact been lowered. (Edit: 400spartans has looked at it and said the code is valid, so it probably is)

I feel a bit guilty for using AI to do this... I don't know how AI-assisted very's INT speed limits proof was, but I relied heavily on AI for this; the AI did the vast majority of the work. Yes, that includes the writeup, which reads like Slop, I did not know how to explain most of this on my own.

I feel like a hypocrite, to be honest. I don't know what to think.

Please check the validity of this.

Also, apparently, PHPbb doesn't support uploading PDF or .py files for some reason???? so you're going to have to have it in archive form. It's not a .zip bomb. I swear it is not a .zip bomb ok please trust me


Edit: A solve for 3x4 windows has completed, establishing a new upper bound of 5146199/10000000 (0.5146 or so)

[NNlk05]

Now, I have not verified this proof. Please do not believe that this proof is valid. It is very likely that it might just be flat out wrong. However, I am posting it here in case someone can verify it and determine that the upper bound has in fact been lowered.

It checks out for me, although I'll be cautious until we get a second opinion or a third, a fourth, etc...
Here's the Python file

Code: Select all

#!/usr/bin/env python3
"""All-period LP bound for oscillating agars in Conway's Life (3x3 two-generation windows).
Requirements: pip install numpy scipy highspy        Usage: python bound_16_31.py
Cell states: 0 dead->dead, 1 alive->dead, 2 dead->alive, 3 alive->alive; windows are row-major 3x3."""
import numpy as np, highspy
from scipy.sparse import coo_matrix

# 1. Reachable windows: run every 5x5 pattern at time t, record (3x3 core at t, 3x3 core at t+1).
reach = np.zeros(1 << 18, bool)
for s in range(0, 1 << 25, 1 << 22):
    P = np.arange(s, s + (1 << 22), dtype=np.int64)
    core = np.zeros_like(P); nxt = np.zeros_like(P)
    for k in range(9):
        r, c = divmod(k, 3); r += 1; c += 1
        cc = (P >> (r*5 + c)) & 1
        n = sum((P >> ((r+a)*5 + (c+b))) & 1 for a in (-1, 0, 1) for b in (-1, 0, 1) if (a, b) != (0, 0))
        core |= cc << k; nxt |= ((n == 3) | ((cc == 1) & (n == 2))).astype(np.int64) << k
    reach[core | (nxt << 9)] = True
codes = np.nonzero(reach)[0]
W = np.stack([((codes >> k) & 1) | (((codes >> (9+k)) & 1) << 1) for k in range(9)], 1)
N = len(W); print("reachable windows:", N)

# 2. Constraints: left/right 3x2 overlaps, top/bottom 2x3 overlaps, stationarity (t layer = t+1 layer), normalisation.
def key(cells, layer=None):
    v = np.zeros(N, np.int64)
    for k in cells: v = v*4 + (W[:, k] if layer is None else (W[:, k] >> layer) & 1)
    return v
pairs = [(key([0,1,3,4,6,7]), key([1,2,4,5,7,8])), (key([0,1,2,3,4,5]), key([3,4,5,6,7,8])),
         (key(range(9), 0), key(range(9), 1))]
rows, cols, vals, off = [], [], [], 0
for a, b in pairs:
    u, inv = np.unique(np.concatenate([a, b]), return_inverse=True)
    rows += [off+inv[:N], off+inv[N:]]; cols += [np.arange(N)]*2; vals += [np.ones(N), -np.ones(N)]; off += len(u)
rows.append(np.full(N, off)); cols.append(np.arange(N)); vals.append(np.ones(N))
A = coo_matrix((np.concatenate(vals), (np.concatenate(rows), np.concatenate(cols))), shape=(off+1, N)).tocsc()
b = np.zeros(off+1); b[-1] = 1
c = (W[:, 4] & 1).astype(float)                      # centre alive at time t
print("rows:", A.shape[0])

# 3. Solve: minimise -density.
h = highspy.Highs(); h.setOptionValue('output_flag', False); h.setOptionValue('solver', 'ipm')
lp = highspy.HighsLp(); lp.num_col_ = N; lp.num_row_ = A.shape[0]; inf = highspy.kHighsInf
lp.col_cost_ = -c; lp.col_lower_ = np.zeros(N); lp.col_upper_ = np.full(N, inf)
lp.row_lower_ = b; lp.row_upper_ = b
lp.a_matrix_.format_ = highspy.MatrixFormat.kColwise
lp.a_matrix_.start_ = A.indptr; lp.a_matrix_.index_ = A.indices; lp.a_matrix_.value_ = A.data.astype(float)
h.passModel(lp); h.run()
print(f"LP optimum: {-h.getInfo().objective_function_value:.9f}   (16/31 = {16/31:.9f})")

# 4. Certificate: round the dual to integers over D and take max_w (c_w D - (A^T u)_w) in exact integer arithmetic.
D = 10**8
u = np.rint(-np.array(h.getSolution().row_dual)[:-1] * D).astype(np.int64)
z = int(((c * D).astype(np.int64) - A[:-1].T.tocsr().astype(np.int64) @ u).max())
print(f"RIGOROUS bound: density <= {z}/{D} = {z/D:.9f}")

[yyh_baboon]

Proof of pop <= 3n:



The sum of all numbers is pop and number in every cell <= 3.
Q.E.D.

in fact the 3 is only achieved when a cell has 2 live neighbors and the other 6 will turn alive for next generation.
the corners can’t actually fulfill this requirement—this lowers the bound to 3n-2

Code: Select all

x = 3, y = 3, rule = LifeHistory
D.A$DE$.A!

the yellow cell is the uppermost cell of the leftmost column. its number can’t be above 7/3 because the 2 red cells can’t be born.
doing so at all the corners can cut upper limit.

[HartmutHolzwart]

If you were an AI, I would say “think harder”. If you go on a finite torus, then there are several ways to get factor 3. In the end this won’t give you something better for finite patterns in the infinite plane, but it’s not as obvious as you might think. This is the difference between a formal proof and a motivation.

[HartmutHolzwart]

I had a bunch of leftover credits, so I asked Claude Opus 5.5 to take a shot at the oscillating agar density conjecture; it did not solve it, but it claims to have established a new upper bound of 16/31 ≈ 0.516, much lower than amling's 1176/2087 bound ≈ 0.563.

Now, I have not verified this proof. Please do not believe that this proof is valid. It is very likely that it might just be flat out wrong. However, I am posting it here in case someone can verify it and determine that the upper bound has in fact been lowered. (Edit: 400spartans has looked at it and said the code is valid, so it probably is)

I feel a bit guilty for using AI to do this... I don't know how AI-assisted very's INT speed limits proof was, but I relied heavily on AI for this; the AI did the vast majority of the work. Yes, that includes the writeup, which reads like Slop, I did not know how to explain most of this on my own.

I feel like a hypocrite, to be honest. I don't know what to think.

Please check the validity of this.


Also, apparently, PHPbb doesn't support uploading PDF or .py files for some reason???? so you're going to have to have it in archive form. It's not a .zip bomb. I swear it is not a .zip bomb ok please trust me


Edit: A solve for 3x4 windows has completed, establishing a new upper bound of 5146199/10000000 (0.5146 or so)

I would be very surprised, how does the proof basically work?