Unproven conjectures

[wirehead]

Nice work! Unfortunately, it seems to me that no finite NxN box has weights that would give a strict 1/2 density bound.

What if there was an algorithm which could, for any real number larger than 1/2, produce a set of weights in a finite box which gives a density bound less than that real number? Or would such an algorithm not be guaranteed to exist?

Welcome to the forums!!

I believe amling was using an SAT solver to find the most recent update to the number -- in that case there already is an algorithm.

[1_1]

Welcome to the forums!!

I believe amling was using an SAT solver to find the most recent update to the number -- in that case there already is an algorithm.

Hi! I'm happy to be welcomed!

From what I gather, that could only find the configurations of weights assuming they already exist, which we haven't proved yet. I was more asking if it would be possible to prove that configurations of weights which give upper bounds arbitrarily close to 1/2 must exist.

Not that using a SAT solver to find weights isn't really cool on it's own, of course.

I also had another thought: finite weights can't enforce an upper bound of 1/2, but what about an infinite set of weights? As long as it was well defined, and added up to a finite number, I would believe such a set of weights could still prove an upper bound. Since Sokwe's proof requires looking at a weight in the top left corner, it wouldn't apply, so an infinite set of weights might be able to give us 1/2 as an upper bound.

[400spartans]

The smallest you can get it is population 306. (Confirmed with LLS.)

Code: Select all

x = 34, y = 28, rule = LifeHistory
12.2C4.2C$12.C5.C$7.2C5.C5.C7.2C$6.C.A4D2A4D2A4D2AD.C$2.2C.A2DAD2A2DA
D2A2DAD2A2DADA$2.C.2ADA2D2ADA2D2ADA2D2ADA2D2A$3.4D2A4D2A4D2A4D2A3DC$
3.2ADA2D2ADA2D2ADA2D2ADA2D2AD.C$3.AD2A2DAD2A2DAD2A2DAD2A2DAD2AC$3.4D
2A4D2A4D2A4D2A4D$3.D2A2DAD2A2DAD2A2DAD2A2DAD2AD$3.D2ADA2D2ADA2D2ADA2D
2ADA2D2AD$3.4D2A4D2A4D2A4D2A4D.2C$2.C2ADA2D2ADA2D2ADA2D2ADA2D2ADA2.C$
C2.AD2A2DAD2A2DAD2A2DAD2A2DAD2AC$2C.4D2A4D2A4D2A4D2A4D$3.D2A2DAD2A2DA
D2A2DAD2A2DAD2AD$3.D2ADA2D2ADA2D2ADA2D2ADA2D2AD$3.4D2A4D2A4D2A4D2A4D$
2.C2ADA2D2ADA2D2ADA2D2ADA2D2ADA$2.C.D2A2DAD2A2DAD2A2DAD2A2DAD2A$3.C3D
2A4D2A4D2A4D2A4D$4.2A2DAD2A2DAD2A2DAD2A2DAD2A.C$5.ADA2D2ADA2D2ADA2D2A
DA2DA.2C$4.C.D2A4D2A4D2A4DA.C$4.2C7.C5.C5.2C$15.C5.C$14.2C4.2C!

The bound was *(provisionally) improved to 278 cells on Discord by "400spartans", using a different self-forcing patch:

Code: Select all

x = 31, y = 28, rule = B3/S23
16bo4b2o$15bobo2bo2bo$7b2o6bo2bo2bo2bo$6bobo4b2ob2ob2ob2obo$2b2obo2bob2o2bo2b
o2bo2bobo$2bob2obo2b2obo2bo2bo2bo2b2o$7b2o4b2ob2ob2ob2o3bo$3b2obo2b2obo2bo2bo
2bo2b2o2bo$3bob2o2bob2o2bo2bo2bo2bob3o$7b2o4b2ob2ob2ob2o$4b2o2bob2o2bo2bo2bo
2bob2o$4b2obo2b2obo2bo2bo2bo2b2o$7b2o4b2ob2ob2ob2o5b2o$ob3obo2b2obo2bo2bo2bo
2b2obo2bo$2obob2o2bob2o2bo2bo2bo2bob3o$7b2o4b2ob2ob2ob2o$4b2o2bob2o2bo2bo2bo
2bob2o$4b2obo2b2obo2bo2bo2bo2b2o$7b2o4b2ob2ob2ob2o$2b3obo2b2obo2bo2bo2bo2b2ob
o$2bo2b2o2bob2o2bo2bo2bo2bob2o$3bo3b2o4b2ob2ob2ob2o$4b2o2bob2o2bo2bo2bo2bob3o
$5bobo2b2obo2bo2bo2bo2bo2bo$4bo2b2o4b3o4b2o3bobo$4b2o3b4o13bo$9bo3bo$12b2o!

* the result has not been verified independently yet; can anyone verify this?

Here's a still life which gives a new bound of 236 cells:

Code: Select all

x = 28, y = 26, rule = B3/S23
2bo8b2o$2b3o5bobo$5bo4bo2b2o2b2o$4bo2b2ob2obo2bo2bobo$4b2ob2o2bo2bob2o
b2obo$5bo4bo2b2o2bo4bo$2obo2bob2ob2o2bo2bob2ob2o$ob3ob2obo2bo2b2ob2obo
2bo$5bo4bo2b2o2bo4bo$4bo2b2ob2obo2bo2b2ob2o$4b2ob2o2bo2bob2ob2o2bo$5bo
4bo2b2o2bo4bo$2obo2bob2ob2o2bo2bob2ob3obo$ob3ob2obo2bo2b2ob2obo2bob2o$
5bo4bo2b2o2bo4bo$4bo2b2ob2obo2bo2b2ob2o$4b2ob2o2bo2bob2ob2o2bo$5bo4bo
2b2o2bo4bo$3bo2bob2ob2o2bo2bob2ob3obo$3b2ob2obo2bo2b2ob2obo2bob2o$5bo
4bo2b2o2bo4bo$5bob2ob2obo2bo2b2ob2o$6bobo2bo2bob2ob2o2bo$9b2o2b2o2bo4b
o$15bobo5b3o$15b2o8bo!

[Sokwe]

Here's a still life which gives a new bound of 236 cells:

Code: Select all

x = 28, y = 26, rule = B3/S23
2bo8b2o$2b3o5bobo$5bo4bo2b2o2b2o$4bo2b2ob2obo2bo2bobo$4b2ob2o2bo2bob2o
b2obo$5bo4bo2b2o2bo4bo$2obo2bob2ob2o2bo2bob2ob2o$ob3ob2obo2bo2b2ob2obo
2bo$5bo4bo2b2o2bo4bo$4bo2b2ob2obo2bo2b2ob2o$4b2ob2o2bo2bob2ob2o2bo$5bo
4bo2b2o2bo4bo$2obo2bob2ob2o2bo2bob2ob3obo$ob3ob2obo2bo2b2ob2obo2bob2o$
5bo4bo2b2o2bo4bo$4bo2b2ob2obo2bo2b2ob2o$4b2ob2o2bo2bob2ob2o2bo$5bo4bo
2b2o2bo4bo$3bo2bob2ob2o2bo2bob2ob3obo$3b2ob2obo2bo2b2ob2obo2bob2o$5bo
4bo2b2o2bo4bo$5bob2ob2obo2bo2b2ob2o$6bobo2bo2bob2ob2o2bo$9b2o2b2o2bo4b
o$15bobo5b3o$15b2o8bo!

I checked this with JLS. The pattern below shows a highlighted self-forcing patch. I don't know if it's a minimal patch (Edit: it's not).

Code: Select all

x = 28, y = 26, rule = LifeHistory
2.A8.2A$2.3A5.A.A$3.2DC4DC2DCA2.2A$3.DC2D2CD2CDC2DC2DC.A$3.D2CD2C2DC
2DCD2CD2CDA$3.2DC4DC2D2C2DC4DC2D$2A.C2DCD2CD2C2DC2DCD2CD2C$A.A2CD2CDC
2DC2D2CD2CDC2DC$3.2DC4DC2D2C2DC4DC2D$3.DC2D2CD2CDC2DC2D2CD2CD$3.D2CD
2C2DC2DCD2CD2C2DCD$3.2DC4DC2D2C2DC4DC2D$2A.C2DCD2CD2C2DC2DCD2CD2CA.A$
A.A2CD2CDC2DC2D2CD2CDC2DC.2A$3.2DC4DC2D2C2DC4DC2D$3.DC2D2CD2CDC2DC2D
2CD2CD$3.D2CD2C2DC2DCD2CD2C2DCD$3.2DC4DC2D2C2DC4DC2D$3.C2DCD2CD2C2DC
2DCD2CD2CA.A$3.2CD2CDC2DC2D2CD2CDC2DC.2A$3.2DC4DC2D2C2DC4DC2D$5.AD2CD
2CDC2DC2D2CD2CD$6.A.C2DC2DCD2CD2C2DCD$9.2A2.AC2DC4DC2D$15.A.A5.3A$15.
2A8.A!

Edit: here is a smaller self-forcing patch in the same still life. In this case, removing any "corner" cell from the self-forcing patch results in a non-self-forcing patch. I don't know if this is a minimal patch.

Code: Select all

x = 28, y = 26, rule = LifeHistory
2.A8.2A$2.3A5.A.A$5.A4.A2.2A2.2A$4.C2D2CD2CDC2DCD.A.A$4.2CD2C2DC2DCD
2CD2C.A$4.DC4DC2D2C2DC3D.A$2A.C2DCD2CD2C2DC2DCD2CDCA$A.A2CD2CDC2DC2D
2CD2CDC2DA$3.2DC4DC2D2C2DC4DCD$3.DC2D2CD2CDC2DC2D2CD2C$3.D2CD2C2DC2DC
D2CD2C2DC$3.2DC4DC2D2C2DC4DCD$2A.C2DCD2CD2C2DC2DCD2CDC2A.A$A.2ACD2CDC
2DC2D2CD2CDC2DC.2A$4.DC4DC2D2C2DC4DC2D$4.C2D2CD2CDC2DC2D2CD2CD$4.2CD
2C2DC2DCD2CD2C2DCD$4.DC4DC2D2C2DC4DC2D$3.A2DCD2CD2C2DC2DCD2CD2CA.A$3.
ACD2CDC2DC2D2CD2CDC2DA.2A$5.A.3DC2D2C2DC4DCD$5.A.2CD2CDC2DC2D2CD2C$6.
A.A.DC2DCD2CD2C2DC$9.2A2.2A2.A4.A$15.A.A5.3A$15.2A8.A!

Notice that while the still life is symmetric, the shape of the self-forcing patch is not.

Edit 2: can you give any details about how you found it?

[400spartans]

Edit 2: can you give any details about how you found it?

I'm just using Torma and Salo's program (https://github.com/ilkka-torma/gol-agars) with two minor tweaks to speed things up. First, I exclude patterns which are just a repetition of some smaller tiling. And second, this came up in a search which only looks at p1 agars in which every live cell is adjacent to 3 live cells and every dead cell is adjacent to 4 live cells. There are plenty of infinite self-forcing p1 agars which do not have this property, but the only known finite self-forcing p1 agar patterns all seem to have this property.

[muzik]

Conjecture: 29 is the lowest population for which an infinite number of distinct, non-pseudo oscillators exist.

Code: Select all

x = 22, y = 48, rule = B3/S23
3o$obo$3o$3o$3o$3o$obo$3o4$o$b2o$2o27$19b3o$19bobo$19b3o$19b3o$19b3o$19b3o$
19bobo$19b3o!

[Sokwe]

Conjecture: 29 is the lowest population for which an infinite number of distinct, non-pseudo oscillators exist.

I believe it. I think the lower bound will always be three more than whatever cell count for which we've fully enumerated all infinitely growth patterns. Right now this is 9+3 = 12. There is still technically the possibility of a 10-cell puffer/wickstretcher/gun that travels/fires towards a far off blinker which, upon reaching the blinker causes a burning reaction along the puffer trail/wick/glider stream until the pattern collapses back into the original 10-cell infinite growth + blinker.

[Haycat2009]

[ DATA EXPUNGED ]

[confocaloid]

Help me prove: Every patch where the dead cells have 4 neighbours and the alive cells have 3 neighbours is self-forcing.

This 8-by-8 patch should count as a counterexample. (Because the 36-bit 3-by-3 block array is glider-constructible.)

Code: Select all

x = 8, y = 8, rule = B3/S23
2ob2ob2o$2ob2ob2o2$2ob2ob2o$2ob2ob2o2$2ob2ob2o$2ob2ob2o!

[Haycat2009]

[ CENSORED ]

[confocaloid]

The only condition in the search was what I listed above.

No, it wasn't.

They wrote:

Edit 2: can you give any details about how you found it?

I'm just using Torma and Salo's program (https://github.com/ilkka-torma/gol-agars) with two minor tweaks to speed things up. First, I exclude patterns which are just a repetition of some smaller tiling. And second, this came up in a search which only looks at p1 agars in which every live cell is adjacent to 3 live cells and every dead cell is adjacent to 4 live cells. There are plenty of infinite self-forcing p1 agars which do not have this property, but the only known finite self-forcing p1 agar patterns all seem to have this property.

You wrote:

Help me prove: Every patch where the dead cells have 4 neighbours and the alive cells have 3 neighbours is self-forcing.

Let the property P be "every specified alive cell has =3 alive neighbours, and every specified dead cell has =4 alive neighbours".

o They searched for some self-forcing patches with the property P, without assuming that every self-forcing patch has property P, and also without assuming that every patch with the property P is self-forcing.

o In contrast, you are claiming that every patch with the property P is self-forcing. That is disproven by the counterexample I posted above (the 3-by-3 block array viewed as a 8-by-8 patch).

[eRroR_6o6]

Is there a proof/disproof that there is an infinite amount of elementary oscillator periods?

[confocaloid]

Is there a proof/disproof that there is an infinite amount of elementary oscillator periods?

A proof would need to rely on some precise definition of elementary.
Almost certainly there are large chaotic-looking blobs without any visible structure somewhere in search space that are p2023 oscillators, and p142857 oscillators, and p1048577 oscillators, and so on for arbitrarily high periods. There are no simple "local" reasons preventing existence of such oscillators.