Unproven conjectures

[Entity Valkyrie 2]

Does there exist a synthesizable, elementary knightship?

Obviously yes. There is no proof that knightships must be self-forcing.

Ah, my favorite proof technique:
Theorem. $P$

Proof.
Nobody has yet produced a proof of $\neg P$.
QED.

Lol that's the burden of proof fallacy

[Entity Valkyrie 2]

Can I please request for a P3 dot fountain?

Do you have a P3 dot fountain?

Back in 2019, before I was aware of the "Unsolved conjectures" thread, one of my unsolved conjectures was "Does there exist a p3 dot 'fountain' ". More specifically, does there exist a p3 oscillator where one phase contains the white cell but none of the red cells, and there are never any cells in the blue region (extends indefinitely up and left)

Code: Select all

x = 9, y = 9, rule = LifeHistory
9B$9B$9B$9B$9B$9B$4B2DC2D$4.5D$5.3D!

I was quite surprised that no p3 dot fountains were known at the time, since the corresponding case for a domino fountain was already known (258P3). I asked again in 2021, but got this response:

Just asking, can anyone search for a P3 strong dot sparker?

Sadly, I believe it's all but confirmed by countless unsuccessful searches that those aren't actually possible.

But of course, not finding one after many non-exhaustive searches is not proof of nonexistence, and only four months later, JP21 discovers the first p3 dot fountain, answering my conjecture with a solid “yes”.

It has been found!!!

Code: Select all

#N P3 dot sparker
x = 67, y = 38, rule = B3/S23
34bo2$14bo4bobo3bob2ob3o3b3o11b2o2b2ob2o3bob2o$b2o11bo2b3obo3bo4bo2b3o
2bobo9bobo2bobobobob2obo$o2bob2o3bo2bob3o2b2o2bo4bo3b3o2bobo11b2o3bobo
bo4bo$2ob4o2bobo5b3o7bo5bo7b4o3bo2bo2b3o2bo2bob2o$bo8bo4bo6b3obobo8b3o
7bobo4b2o4bo3bo$bobobo5b3o3bob4o3b2o2b5ob3o4b2o2bo3bob2o4b2o3bo$2o4bo
3b3o4bo9bob3o12b3o2bo5b2o2bo2bob2o$2bobobo13bo3bob2o4bo2b2o7b2o2b5o2b
3obobo4bo$2bobob2o3bo4b4o3bo4bo3b2ob4o9bo2b2obo2bobobob2obo$3b2obob2o
12bo2bo2bobob2o3bobo9b2obobobobo3bob2o$7b2o2bo3bo2b2o2b4ob3o2b2o6bo9bo
bobob2o$10b2o3bobobo7bo11b3ob2obo2bo2b2o$16bo5b3obob2o6b2obob2o2b2o2b
2o$22bo4bo3bo4b2obobobo$24b2o2bobo2bo3b3o4b3o$18b2o3b2obobobo2bo4bo2bo
bo2bo$18bo4b4obobob2o5bo3bobo$19bobo5bo4bo5b4o3b2o$21b3o3bobobo6bo3b2o
3bo$18bo3b4obo11b2o4b2o$14b2obobo3bob2obo2bo9b4o$15bobobobo6bobo10bo2b
o$14bo2b4ob2ob2obobob2o$15b2o2bo3b2obobobo$17bo4bo3bobo3bo$17bo3bob3o
3b2o$18b2obo$21bob3o$20b2obo2bo$18b3o2bob2o$17bobo3bo$17bo3bobo$18b2ob
2o2$16b7o$16bo2bo2bo!

The current smallest p3 dot fountain is this:

Code: Select all

x = 21, y = 18, rule = B3/S23
16b2o$11bo3bo2bo$14bobobo$7b3o3bob2ob2o$5bobo2b3o4bo$5b2o3b3ob2obo$3b3o4bo3bobo$2bo4bo$3b2o4b3o$4b3obobobob2o$4b2o4bobo5b2o$ob2obob4obobo4bo$2obobo6bob5o$4bo3bo3b2obo$5b4o7b5o$17bo2bo$7b2o6bo$7b2o6b2o!

It does have some uses, such as in the p3 hotcrystal0 glider reflector.

[HerscheltheHerschel]

An (unproven) extension of EV2's (proven) conjecture "Is there a Thessalonic reflector?":
Is there a Thessalonic reflector which doesn't use conduits?

[EvinZL]

An (unproven) extension of EV2's (proven) conjecture "Is there a Thessalonic reflector?":
Is there a Thessalonic reflector which doesn't use conduits?

There exists a conduit-free Thessalonic (in fact, blockic) reflector based on universal constructor technology.

[HerscheltheHerschel]

An (unproven) extension of EV2's (proven) conjecture "Is there a Thessalonic reflector?":
Is there a Thessalonic reflector which doesn't use conduits?

There exists a conduit-free Thessalonic (in fact, blockic) reflector based on universal constructor technology.

Yeah, but is there a fully Thessalonic one?

[qqd]

It is possible to implement the 3D reversible rule corresponding to B3/S23 (based on Toffoli's method) to go back to previous generations without keeping a memory of them? I presume it would greatly speed up Golly, though I am not so sure. Here is a link to his paper:

Code: Select all

https://pdf.sciencedirectassets.com/271538/1-s2.0-S0304397500X00229/1-s2.0-030439759500038X/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEIn%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJIMEYCIQChXemwwN0G3FfUsFAtWxeUCB4LpIaEgzrtG1XkloCuWgIhAM%2FZawl%2BVufwUkvNN%2BDf6KcL10PAbFZ%2BR8xDAL7kFZFQKrsFCJL%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEQBRoMMDU5MDAzNTQ2ODY1Igyz%2BzaIYymg%2BxRgPxcqjwVwA5g8ETfJAD7UaJq4c2HWfHkpDe6oO8Dw3vPPr7Yk6B4Bnm6WhGq1s%2FOslqrGCR9qa5N7sh4XC3QJKyLO8p2MJEyuvh2KkNp5c7Kta1PNr2zILj422dWUga0EhAhNq1cJ2xQsaP%2F5uaCuwZ%2FSb%2BvuT1oK8EzDzjWoV2K2LIbLQRE7sXDxIlkAYLMTqvcSYDYwGMfV3tEyB1w14p0L4mIhJi9gKsix08PQd6JPWvTFfWmQcblIGnmsHAG6LZJ9L9Qu%2BEIZxyJKU2ujuZIYPMin%2FA4aO9S8x8j%2BKL8oEs87KtZwZmKJ6RNNUdBCPowsArYrR4v2jsgXoAaz4KLa8m68CbxU02XcR%2FpmfseojdmmoWOKOLLOmPMbVc8IADu9bysGMJJkwe8DnFxeJXK3lzIa13ONosluDloP%2FdqPmGQ2W%2BRcG4hP%2BsHTcpD%2BP1dAY43OxPfNWYpsX5l63DVTvm%2FoLPcSn%2B%2B505WOCHS4mvM7rLU09nh2fBXITSyBu6%2BAFVCKmQ9k9SZbxmGx3ujUWO%2BFaCHVzyukMIQW%2B5i3B7IJle368AUxr7BEnjdch4SYQ96DlNI8AdkXhJ8StXwmH9tMY57MNmkozzq7XvgPDsxEZ%2FC0N8WcHMyEXC434ejEY2SFnxGCHfUZO29l2qb15sVkB%2BBhN7T4KsjNKhJU4qmN3bZFyZmqzEwnEEvEmVCG9w6scybwESbat56%2BTEWqNCfE3aH%2B1PbteLVkbTbg7J1z9sn2YiQ58l%2BuQvlNAkeqUQFRCcAR8faFejTBjALWJLH87THKaBhoefZxizLUKfyuCZWUI%2BZuJ48M0%2BYWjwmx4nQ7FDf9qV4BFbwc3mfjWG1GcDR59PLvkMT9aA4zwmQ8MKKUhqkGOrAB5SsoabRMvMNipwXOm%2BYx6YxAcaLeXZqAg%2B6Y4PTnggvsHT2gXI67gdNgYEALBrE6xs7J2vDzvISJdV2%2FExELM0r8lx2vQxBzc4E3Lm48JcvBmynsLXGGR1r3nm7YNezu4wAZsjJCfmMBsUUSA%2FDVrMPtHeNKkWrDtR8qGOi0xdpzhpvQz7iIIDJnQuIyHsHHz8JiYktDcEchxqMCrcpCVd7B9qH%2BH8Irft43AeNsS68%3D&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20231007T171514Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTY7INTNPU3%2F20231007%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=95393cc6b5726a80ecbfd690e60edccf79db4224c43b5e57d2c61cea1fba36f5&hash=ca71341a15d40a5c7367be311d5c791295a312deb5364688dbc5050de817f6c4&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=030439759500038X&tid=spdf-521059af-dc53-440f-ae32-481161e8166a&sid=f854941d9250a54d478a040-2b9f6d72acdfgxrqb&type=client&tsoh=d3d3LnNjaWVuY2VkaXJlY3QuY29t&ua=1b035a5557550157035c50&rr=8127c8f25e38b476&cc=ae

[AlbertArmStain]

New conjecture:
There exists only one unique rumbling river rotator and excluding longer wicks which it can be derived from it.

[Haycat2009]

An (unproven) extension of EV2's (proven) conjecture "Is there a Thessalonic reflector?":
Is there a Thessalonic reflector which doesn't use conduits?

There exists a conduit-free Thessalonic (in fact, blockic) reflector based on universal constructor technology.

Yeah, but is there a fully Thessalonic one?

Yes, just add a random fishhook somewhere in the pattern to initiate a null reaction.

[400spartans]

The article https://conwaylife.com/wiki/Density states:

The maximum average density of an oscillating agar is conjectured but not proven to be 1/2. The current upper bound is 8/13, proven by Hartmut Holzwart in 1992.

The following is a proof that the maximum average density of an oscillating agar is bounded above by 17/28 (which is very slightly smaller than 8/13).

Consider three consecutive generations of a 3x3 grid of cells in some oscillating agar. Assign weights to each of these 27 cells as follows:

2 2 2
2 0 2
2 2 2

0 1 0
1 7 1
0 1 0

0 0 0
0 1 0
0 0 0

I claim that the maximum weight of the on cells is 17.

First, note that at most 4 of the weight-1 cells can be on, as otherwise we'd have an on cell in the third generation that either survived or was born from having 4 on neighbors.

Now, if the weight-7 cell is on, then at most 3 of the weight-2 cells can be on. So the maximum weight in this case is 4*1 + 3*2 + 1*7 = 17

If the weight-7 cell is off, then we have the following cases:

• If 6 or fewer weight-2 cells are on, then the maximum possible weight is 6*2 + 4*1 = 16
• If exactly 7 weight-2 cells are on, there will always be two edge cells with at least four on neighbors in the first generation. So at least two edge cells will be off in the second generation. This means at most 3 weight-1 cells can be on in total, so the maximum weight is 7*2 + 3*1 = 17
• If exactly 8 weight-2 cells are on, all edge cells will be dead in the second generation, so the maximum possible weight is 8*2 + 1*1 = 17

Therefore the maximum "on" weight is 17. The total weight of all cells is 28. If we express this relationship as an inequality, calculate inequalities of this form for every 3-generation snippet of a 3x3 grid in our agar, and add them up, we'd get that (sum of all the weights in the grid) * (# of on cells) <= (maximum on weight in the grid) * (# of total cells). In this case, the resulting inequality is 28 * (# of on cells) <= 17 * (# of total cells). So, the maximum average on cell density for any periodic pattern is 17/28.

[Sokwe]

The following is a proof that the maximum average density of an oscillating agar is bounded above by 17/28 (which is very slightly smaller than 8/13).

Nice! I personally think the exposition would be a bit improved if you separate the following steps and explain them a little more:

If we express this relationship as an inequality, calculate inequalities of this form for every 3-generation snippet of a 3x3 grid in our agar, and add them up

[400spartans]

I personally think the exposition would be a bit improved if you separate the following steps and explain them a little more:

Yeah I think that part is better explained with a little bit of abstraction. Note that below when I refer to "cell" I mean a particular generation of a cell. For the sake of abstraction I'm representing the generations of an oscillating pattern as a 3-dimensional grid of cells with a time axis.

No matter where we select this 3x3x3 box (3x3 grid + 3 generations), as long as we assign weights in the manner described above, we know that the weight of the on cells in the box is at most 17. If we put two 3x3x3 boxes of weights side by side, then in the resulting 6x3x3 box of weights, we know that the weight of the on cells in the combined box is at most 34, which is 17 times the number of boxes. We can also combine them by adding some of their weights together. For example, they can add up to the following 5x3x3 box of weights:

2 2 4 2 2
2 0 4 0 2
2 2 4 2 2

0 1 0 1 0
1 7 2 7 1
0 1 0 1 0

0 0 0 0 0
0 1 0 1 0
0 0 0 0 0

Once again, the weight of the on cells in the combined box above is at most 34, which is 17 times the number of boxes.

In this same manner, we can create a 3x3x3 box of weights for every possible 3x3x3 box in our oscillating agar (wrapping around at the edges), and add them all together. To figure out what the resulting box will look like, note that for each cell in our oscillating agar and for each possible position in the original 3x3x3 box of weights, there is exactly one box that puts that particular cell into that particular position. This means that the total sum of weights for each cell is just the sum of the weights in the 3x3x3 box, which is 28. As before, we know that the weight of the on cells in the combined box is at most 17 times the number of boxes. And since there is a box for each cell, this is just 17 times the total number of cells.

So, we now have a box of weights with the same size as our oscillating agar, where every cell has a weight of 28 and the weight of the on cells is at most 17 times the total number of cells. So the weight of the on cells is 28 times the number of on cells, and we know this is less than or equal to 17 times the total number of cells. Therefore the number of on cells is less than or equal to 17/28 times the total number of cells, which means the average density of any oscillating pattern is at most 17/28.

[Quantum-mechanics]

A metacell with MWSS show and can show with drawing.

[NooneAtAll3]

So, the maximum average on cell density for any periodic pattern is 17/28.

a) It is slightly more powerful, since it's the maximum average density for any evolution (in the limit), not just periodic
I guess the only distinction would be spacefiller or smth, but still

----

b) That strategy is kinda... generalizable

Choose any set of cell-moments in GoL's "spacetime"
Assign each of them a weight, summing to S
If all possible universe evolutions passing through that set don't cover more than C total weight with alive cells, then C/S is an upper bound on the density
(same idea - put that set on all possible displacements, sum over live cells over sets == sum over sets over live cells == S*live <= C*sets == C*all_cells)

b2) There isn't anything limiting weights to integers ...so optimal values for any cellset are findable via linear programming

Code: Select all

Given weights and upper bound Limit  
We need to minimize [Limit], subject to constraints:

Summ of all weights == 1 //normalisation
for each legal evolution:
	sum of weights in live cells - Limit <= 0

Sadly, now complexity isn't in the weights/upper bound calculation - but in listing all the legal evolutions through the chosen set.
Some optimizations are possible, tho

b3) If our "2+1D" shape is symmetric (in space), then asymmetric weights can be summed with the "mirrored" version to still get same upper bound - thus we can limit ourselfs to symmetric weights, thus symmetric cell-moments can be combined into single weight variables, and evolutions that rotate into each other result in same inequalities

b4) I can't think how to rule out some individual weights being negative. But, we can use non-negative-weight subset of solutions anyway, since all weight sets give some kind of an upper bound.
Continuing with that restriction, we can shrink the "all legal evolutions" line to only the "maximal" ones - i.e. those where you can't filp any amount of the dead cells into life and still have legal evolution (because any added live cell guarantees non-decrease in weight, thus making lesser evolutions redundant)

This doesn't seem that important on the first glance for brute force, but this loop-over-evolutions most likely will be done with SAT-solvers - where each step now can be encoded not as "at least one cell is different from previous", but as a more powerful "at least one now-dead cell is alive" (just don't forget to make solver prefer live cells as the first choice in all guesses)

-----

c) Given what's stated above, most simple shape I chose to test was "single step", i.e. 3x3+1x1 inverted pyramid
all 8 "edge" cells on upper layer symmetric-ize into each other, while evolutions collapse into 2 maximal ones:
111
111 0
111

and

110
110 1
000

Code: Select all

from scipy.optimize import linprog
#edg, ctr, next, lim
c=[0,  0,    0,   1]
A_ub = [
[ 8,   1,   0,   -1],
[ 3,   1,   1,   -1],
]
b_ub = [0]*len(A_ub)
A_eq = [
[8,    1,   1,    0]
]
b_eq = [1]
res = linprog(c, A_ub=A_ub, b_ub = b_ub, A_eq=A_eq, b_eq=b_eq)
print(res.fun, res.x)

Denormalizing result back gives

111
101 5
111

solution, which results in 8/13 (0.615) density - equal to the previous record.
Interestingly, I think it's even possible to track same "copy of the set on all displacements" and "only use the maximal evolutions" steps in that proof as well, just not with full perspective realized like now

If you unbound all the variables, but forget to add all the evolutions - then that center weight would go to -inf, dragging Limit along
Funny "Limit=0" result:

1 1 1
1 -8 1 5
1 1 1

Fixed, obviously, by inserting the whole transition table
A_ub = [[8,1,0,-1], [7,1,0,-1], [6,1,0,-1]...]

Same solution tho

---

3x3x2 results in

222 | 010
202 | 161
222 | 010

and 16/26 = 8/13 (0.615)

3x3x3 solution is optimal

222 | 010 | 000
202 | 171 | 010
222 | 010 | 000

17/28 (0.607)

3x3x4 took ~20-25 minutes of python bruteforce with stupid prunning, no maximal-based optimizations

12 12 12 | 3 9 3 | 0 4 0 | 0 0 0
12 0 12 | 9 42 9 | 4 9 4 | 0 4 0
12 12 12 | 3 9 3 | 0 4 0 | 0 0 0

130/215 = 26/43 (0.605, slightly below 17/28)

if anyone wants to try larger shapes, I invite you to try

Edit:
5x5+3x3+1x1 i.e. 3-high pyramid, i.e. 2 generations

0 8 8 8 0
8 24 24 24 8 | 11 27 11
8 24 32 24 8 | 27 48 27 | 39
8 24 24 24 8 | 11 27 11
0 8 8 8 0

320/559 (0.572, even smaller than 26/43)

Edit 2:

p2 (i.e. center cell loops back to the same state) weights

06 12 022 12 06
16 56 068 56 16 | 25 057 25
22 68 127 68 22 | 57 108 57
16 56 068 56 16 | 25 057 25
06 12 022 12 06

[s]I forgot to write down the "max live/total" :/
Maybe someone wants to take it as a puzzle?[/s]
736/1299 (0.567)

I tried p1 as well (middle 3x3 stays the same)

0 0 0 0 0
0 1 1 1 0
0 1 3 1 0
0 1 1 1 0
0 0 0 0 0

6/11 (0.545)

I have no idea why there's so many zeroes and how this would change as area grows

I've looked into the still live limit=1/2 paper, and it actually has weights! ...for S4 and S5 rules, where this way is more optimal than alternatives

So this technique isn't new, credit should go to "Greg Kuperberg". Makes me wonder why he didn't try oscillators/why his results aren't known

Edit 3:

p2 where live cells in gen0 aren't forced dead by gen1 (it was only "center cell is same" before)

0 2 2 2 0
2 4 6 4 2 | 3 5 3
2 6 11 6 2| 5 8 5
2 4 6 4 2 | 3 5 3
0 2 2 2 0

64/115 (0.557)

[AbhpzTa]

pretty random, but I conjecture that there exists no stable or periodic (stationary) object that cannot be hit with a glider to create debris with a larger population than the original object. for example, the block has two collisions that have a greater final population.

I think the following 8492-cell still-life (a long^4243 ship) is a counterexample...

Smaller counterexample (a 392-cell still life):

Code: Select all

x = 28, y = 28, rule = B3/S23
2ob2o2b2ob2ob2ob2ob2o2b2ob2o$2obobo2bob2ob2ob2obo2bobob2o$3bob2obo10bo
b2obo$4o4b12o4b4o$o3b3o14b3o3bo$b2obo2b14o2bob2o$2bobobo14bobobo$o4bob
14obo4bo$4obobo12bobob4o$3bobobo2b8o2bobobo$2obobobobo8bobobobob2o$2ob
obobobob6obobobobob2o$3bobobobobo4bobobobobo$2obobobobobob2obobobobobo
b2o$2obobobobobob2obobobobobob2o$3bobobobobo4bobobobobo$2obobobobob6ob
obobobob2o$2obobobobo8bobobobob2o$3bobobo2b8o2bobobo$4obobo12bobob4o$o
4bob14obo4bo$2bobobo14bobobo$b2obo2b14o2bob2o$o3b3o14b3o3bo$4o4b12o4b
4o$3bob2obo10bob2obo$2obobo2bob2ob2ob2obo2bobob2o$2ob2o2b2ob2ob2ob2ob
2o2b2ob2o!

Max-finpop collision (finpop=388):

Code: Select all

x = 28, y = 36, rule = B3/S23
3bobo$3b2o$4bo6$2ob2o2b2ob2ob2ob2ob2o2b2ob2o$2obobo2bob2ob2ob2obo2bobo
b2o$3bob2obo10bob2obo$4o4b12o4b4o$o3b3o14b3o3bo$b2obo2b14o2bob2o$2bobo
bo14bobobo$o4bob14obo4bo$4obobo12bobob4o$3bobobo2b8o2bobobo$2obobobobo
8bobobobob2o$2obobobobob6obobobobob2o$3bobobobobo4bobobobobo$2obobobob
obob2obobobobobob2o$2obobobobobob2obobobobobob2o$3bobobobobo4bobobobob
o$2obobobobob6obobobobob2o$2obobobobo8bobobobob2o$3bobobo2b8o2bobobo$
4obobo12bobob4o$o4bob14obo4bo$2bobobo14bobobo$b2obo2b14o2bob2o$o3b3o
14b3o3bo$4o4b12o4b4o$3bob2obo10bob2obo$2obobo2bob2ob2ob2obo2bobob2o$2o
b2o2b2ob2ob2ob2ob2o2b2ob2o!

[HerscheltheHerschel]

snip

snip

Smaller counterexample (a 392-cell still life):

Code: Select all

x = 28, y = 28, rule = B3/S23
2ob2o2b2ob2ob2ob2ob2o2b2ob2o$2obobo2bob2ob2ob2obo2bobob2o$3bob2obo10bo
b2obo$4o4b12o4b4o$o3b3o14b3o3bo$b2obo2b14o2bob2o$2bobobo14bobobo$o4bob
14obo4bo$4obobo12bobob4o$3bobobo2b8o2bobobo$2obobobobo8bobobobob2o$2ob
obobobob6obobobobob2o$3bobobobobo4bobobobobo$2obobobobobob2obobobobobo
b2o$2obobobobobob2obobobobobob2o$3bobobobobo4bobobobobo$2obobobobob6ob
obobobob2o$2obobobobo8bobobobob2o$3bobobo2b8o2bobobo$4obobo12bobob4o$o
4bob14obo4bo$2bobobo14bobobo$b2obo2b14o2bob2o$o3b3o14b3o3bo$4o4b12o4b
4o$3bob2obo10bob2obo$2obobo2bob2ob2ob2obo2bobob2o$2ob2o2b2ob2ob2ob2ob
2o2b2ob2o!

Max-finpop collision (finpop=388):

Code: Select all

x = 28, y = 36, rule = B3/S23
3bobo$3b2o$4bo6$2ob2o2b2ob2ob2ob2ob2o2b2ob2o$2obobo2bob2ob2ob2obo2bobo
b2o$3bob2obo10bob2obo$4o4b12o4b4o$o3b3o14b3o3bo$b2obo2b14o2bob2o$2bobo
bo14bobobo$o4bob14obo4bo$4obobo12bobob4o$3bobobo2b8o2bobobo$2obobobobo
8bobobobob2o$2obobobobob6obobobobob2o$3bobobobobo4bobobobobo$2obobobob
obob2obobobobobob2o$2obobobobobob2obobobobobob2o$3bobobobobo4bobobobob
o$2obobobobob6obobobobob2o$2obobobobo8bobobobob2o$3bobobo2b8o2bobobo$
4obobo12bobob4o$o4bob14obo4bo$2bobobo14bobobo$b2obo2b14o2bob2o$o3b3o
14b3o3bo$4o4b12o4b4o$3bob2obo10bob2obo$2obobo2bob2ob2ob2obo2bobob2o$2o
b2o2b2ob2ob2ob2ob2o2b2ob2o!

Now synthesize it.

[amling]

So, the maximum average on cell density for any periodic pattern is 17/28.

b) That strategy is kinda... generalizable

Dang, I saw the reduction to 17/28 posted while I was out of town and thought the exact same thing (use linear programming to pick weights), but couldn't really try anything until I got back home.

I follow the argument that if the considered space is symmetric the weights might as well be by averaging orbits, but I don't follow why that makes all eight outer weights in the 3x3+1x1 case the same (as none of the symmetries that are obvious to me carry corners to edges).

EDIT: Nope, I get it. It's not true in any real general geometric sense, it's just that this very tiny board only has one CA check and for that CA check all eight count towards its sum the same.

I do however reproduce the same weights and result (8/13) for 3x3+1x1:

Code: Select all

| 1 1 1 | X X X |
| 1 0 1 | X 5 X |
| 1 1 1 | X X X |

Skipping forward to 3x3x4 it takes my unoptimized first cut of the code ~13m to generate ~534K constraints, then ~6s for the 3p linear programming solver to solve that, producing the same (130/215):

Code: Select all

| 12 12 12 | 03 09 03 | 00 04 00 | 00 00 00 |
| 12 00 12 | 09 42 09 | 04 09 04 | 00 04 00 |
| 12 12 12 | 03 09 03 | 00 04 00 | 00 00 00 |

Adding one extra cell in the next generation (3x3x4+1x1) did about the same (sameish time, identical constraint count and final weights).

5x5+3x3+1x1 took only ~14s to generate ~81K constraints and solved instantly, producing the same (320/559):

Code: Select all

| 00 08 08 08 00 | XX XX XX XX XX | XX XX XX XX XX |
| 08 24 24 24 08 | XX 11 27 11 XX | XX XX XX XX XX |
| 08 24 32 24 08 | XX 27 48 27 XX | XX XX 39 XX XX |
| 08 24 24 24 08 | XX 11 27 11 XX | XX XX XX XX XX |
| 00 08 08 08 00 | XX XX XX XX XX | XX XX XX XX XX |

5x5+3x3x2 took ~24m to generate ~1.9M constraints and solved in ~27s, but produced the same results as 5x5+3x3+1x1.

TBD if I can optimize or wait out doing anything bigger (I'm trying 5x5x2 and 6x6+4x4+2x2 to start).

EDIT: Fancier computer and slightly fancier algorithm (drop boards which have a single cell addition which is legal since they're not even cell-wise maximal and then parallelize the generation somewhat haphazardly) is doing a lot better. With this 5x5+3x3x2+1x1 generates ~256K constraints in ~14s and solves it instantly, producing same weights as 5x5+3x3+1x1. 6x6+4x4+2x2 and 5x5x2 still a work in progress...

EDIT: 5x5x2 took ~33m to produce ~173K constraints and solved instantly, but produced same weights as 3x3+1x1. 6x6+4x4+2x2 took ~21m to produce ~3.9M constraints but hit the 8G memory limit I had imposed when trying to solve. 5x5x2+3x3 took ~73m to produce ~44M constraints but hit the 8G memory limit trying to construct the LP library's model of the problem. Unfortunately I'm gonna have to wait for other stuff to finish running before I can allow them more memory. Maybe some day when my search queue has burned down a bit I'll be back...

[amling]

6x6+4x4+2x2 took ~21m to produce ~3.9M constraints but hit the 8G memory limit I had imposed when trying to solve. 5x5x2+3x3 took ~73m to produce ~44M constraints but hit the 8G memory limit trying to construct the LP library's model of the problem.

I had to give it a little more memory (only ~10GB) and switch solvers but I got 6x6+4x4+2x2 through. The new solver, "minilp" is supposedly not fast but it still solved pretty quickly (around 30s). Final bound is 1176/2087 = 0.5634882606612366, which is better Weights are:

Code: Select all

| 024 072 120 120 072 024 | XXX XXX XXX XXX XXX XXX | XXX XXX XXX XXX XXX XXX |
| 180 114 180 180 114 180 | XXX 096 241 241 096 XXX | XXX XXX XXX XXX XXX XXX |
| 120 072 294 294 072 120 | XXX 241 154 154 241 XXX | XXX XXX 179 179 XXX XXX |
| 120 072 294 294 072 120 | XXX 241 154 154 241 XXX | XXX XXX 179 179 XXX XXX |
| 180 114 180 180 114 180 | XXX 096 241 241 096 XXX | XXX XXX XXX XXX XXX XXX |
| 024 072 120 120 072 024 | XXX XXX XXX XXX XXX XXX | XXX XXX XXX XXX XXX XXX |

Even with 60G memory, 5x5x2+3x3 and minilp filled memory and died. I can't get a version with the "highs" solver to build on the bigger box (some horrible linker error).

I got it to dump out a standalone ".lp" file, but run on it `glpk` aborts with "too many constraint coefficients" and (standalone) (coinor) `clp` segfaults (which is what happened with the linked version of it earlier). Unfortunately I'm running out of ideas here.

[Sokwe]

5x5+3x3+1x1 i.e. 3-high pyramid, i.e. 2 generations

0 8 8 8 0
8 24 24 24 8 | 11 27 11
8 24 32 24 8 | 27 48 27 | 39
8 24 24 24 8 | 11 27 11
0 8 8 8 0

320/559 (0.572, even smaller than 26/43)

I had to give it a little more memory (only ~10GB) and switch solvers but I got 6x6+4x4+2x2 through. The new solver, "minilp" is supposedly not fast but it still solved pretty quickly (around 30s). Final bound is 1176/2087 = 0.5634882606612366, which is better Weights are:

Code: Select all

| 024 072 120 120 072 024 | XXX XXX XXX XXX XXX XXX | XXX XXX XXX XXX XXX XXX |
| 180 114 180 180 114 180 | XXX 096 241 241 096 XXX | XXX XXX XXX XXX XXX XXX |
| 120 072 294 294 072 120 | XXX 241 154 154 241 XXX | XXX XXX 179 179 XXX XXX |
| 120 072 294 294 072 120 | XXX 241 154 154 241 XXX | XXX XXX 179 179 XXX XXX |
| 180 114 180 180 114 180 | XXX 096 241 241 096 XXX | XXX XXX XXX XXX XXX XXX |
| 024 072 120 120 072 024 | XXX XXX XXX XXX XXX XXX | XXX XXX XXX XXX XXX XXX |

Nice work! Unfortunately, it seems to me that no finite NxN box has weights that would give a strict 1/2 density bound. Here's my quick, unrefined argument (excuse me if there's a much smarter or more obvious argument, and forgive me if there's a flaw):

For any NxNxK, finding optimal weights over still life configurations is less restrictive than over all configurations, so the NxNxK still life density bound from this method will always be less than or equal to the arbitrary agar bound for NxNxK. Since a still life doesn't change, the optimal still life weights in one generation must also be optimal for all other generations, so we need only consider the still life weights in a single generation.

Let S be the set of all NxN configurations that can be completed to form an infinite still life whose inversion (off cells become on and vice versa) is also an infinite still life (in particular, S is closed under inversion). Consider optimizing weights over S, which is less restrictive than optimizing over all NxN still life configurations. Normalize so the sum of all weights in the NxN box is equal to 1.

Assume (in order to reach a contradiction) that some set of weights on the NxN box gives a 1/2 density bound (i.e., for each configuration in S, the sum of the on weights is less than or equal to 1/2). S is closed under inversion, so the sum of the off weights must also be less than or equal to 1/2. Since the sum of all weights is 1, both the sum of the on weights and the sum of the off weights must each be exactly 1/2.

Consider the following snippets of two infinite still lifes that differ by only 8 cells:

Code: Select all

x = 92, y = 20, rule = B3/S23
4o4b4o4b4o4b4o32b4o4b4o4b4o4b4o$4b4o4b4o4b4o4b4o32b4o4b4o4b4o4b4o$4o4b
4o4b4o4b4o32b4o4b4o4b4o4b4o$4b4o4b4o4b4o4b4o32b4o4b4o4b4o4b4o$4o4b4o4b
4o4b4o32b4o4b4o4b4o4b4o$4b4o4b4o4b4o4b4o32b4o4b4o4b4o4b4o$4o4b4o4b4o4b
4o32b4o4b4o4b4o4b4o$4b4o4b4o4b4o4b4o32b4o4b3obo3b4o4b4o$4o4b4o4b4o4b4o
32b4o4b4o2bobob2o4b4o$o2bob2obo2bob2obo2bob2obo2bob2o29bo2bob2obo2bobo
2b2obob2obo2bob2o$o2bob2obo2bob2obo2bob2obo2bob2o29bo2bob2obo2bob3o3bo
b2obo2bob2o$4o4b4o4b4o4b4o32b4o4b4o4b4o4b4o$4b4o4b4o4b4o4b4o32b4o4b4o
4b4o4b4o$b2obo2bob2obo2bob2obo2bob2obo2bo29b2obo2bob2obo2bob2obo2bob2o
bo2bo$b2obo2bob2obo2bob2obo2bob2obo2bo29b2obo2bob2obo2bob2obo2bob2obo
2bo$4b4o4b4o4b4o4b4o32b4o4b4o4b4o4b4o$4o4b4o4b4o4b4o32b4o4b4o4b4o4b4o$
o2bob2obo2bob2obo2bob2obo2bob2o29bo2bob2obo2bob2obo2bob2obo2bob2o$o2bo
b2obo2bob2obo2bob2obo2bob2o29bo2bob2obo2bob2obo2bob2obo2bob2o$4o4b4o4b
4o4b4o32b4o4b4o4b4o4b4o!

Notice that each pattern gives its own inversion by flipping over the central vertical axis, so NxN snippets of these still lifes are in S. Consider for example the following highlighted 10x10 boxes:

Code: Select all

x = 92, y = 20, rule = LifeHistory
4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A
4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A4.
4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A4.4A
4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.3A.A3.4A4.4A$4A4.4A
4.4A4.4A32.4A4.4A2.A.A.2A4.4A$A2.A.2A.A2.A.2A.A2.A.2A.A2.A.2A29.A2.A.
2A.A2.A.A2.2A.A.2A.A2.A.2A$A2.A.2A.A2.A.2A.E2BCB2CBCB.A.2A29.A2.A.2A.
A2.A.3AD2BCB2CBCB.A.2A$4A4.4A4.4C4B2C2A32.4A4.4A4.4C4B2C2A$4.4A4.4A4B
4C2B2.4A32.4A4.4A4B4C2B2.4A$.2A.A2.A.2A.A2.AB2CBC2BCBCA.A2.A29.2A.A2.
A.2A.A2.AB2CBC2BCBCA.A2.A$.2A.A2.A.2A.A2.AB2CBC2BCBCA.A2.A29.2A.A2.A.
2A.A2.AB2CBC2BCBCA.A2.A$4.4A4.4A4B4C2B2.4A32.4A4.4A4B4C2B2.4A$4A4.4A
4.4C4B2C2A32.4A4.4A4.4C4B2C2A$A2.A.2A.A2.A.2A.C2BCB2CBCB.A.2A29.A2.A.
2A.A2.A.2A.C2BCB2CBCB.A.2A$A2.A.2A.A2.A.2A.C2BCB2CBCB.A.2A29.A2.A.2A.
A2.A.2A.C2BCB2CBCB.A.2A$4A4.4A4.4C4B2C2A32.4A4.4A4.4C4B2C2A!

Notice that these boxes only differ by one cell (highlighted), the upper left corner. Since the sum of on weights in both 10x10 boxes is 1/2, the weight on the upper left corner cell must be 0. Now shift the boxes left by one cell:

Code: Select all

x = 92, y = 20, rule = LifeHistory
4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A
4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A4.
4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A4.4A
4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.3A.A3.4A4.4A$4A4.4A
4.4A4.4A32.4A4.4A2.A.A.2A4.4A$A2.A.2A.A2.A.2A.A2.A.2A.A2.A.2A29.A2.A.
2A.A2.A.A2.2A.A.2A.A2.A.2A$A2.A.2A.A2.A.2ADE2BCB2CBC2.A.2A29.A2.A.2A.
A2.A.2AED2BCB2CBC2.A.2A$4A4.4A3.B4C4BC3A32.4A4.4A3.B4C4BC3A$4.4A4.3AC
4B4CB3.4A32.4A4.3AC4B4CB3.4A$.2A.A2.A.2A.A2.CB2CBC2BCB2A.A2.A29.2A.A
2.A.2A.A2.CB2CBC2BCB2A.A2.A$.2A.A2.A.2A.A2.CB2CBC2BCB2A.A2.A29.2A.A2.
A.2A.A2.CB2CBC2BCB2A.A2.A$4.4A4.3AC4B4CB3.4A32.4A4.3AC4B4CB3.4A$4A4.
4A3.B4C4BC3A32.4A4.4A3.B4C4BC3A$A2.A.2A.A2.A.2ABC2BCB2CBC2.A.2A29.A2.
A.2A.A2.A.2ABC2BCB2CBC2.A.2A$A2.A.2A.A2.A.2ABC2BCB2CBC2.A.2A29.A2.A.
2A.A2.A.2ABC2BCB2CBC2.A.2A$4A4.4A3.B4C4BC3A32.4A4.4A3.B4C4BC3A!

These boxes differ by two cells (highlighted), the upper left corner, and the cell immediately to the right of the upper left corner. Since the upper left corner cell has weight 0, it does not contribute to the sum of the on weights. Thus for the same reason as before, the cell just to the right of the upper left corner must also have weight 0.

Shifting the box by one cell to the left again, we find that the patterns still only differ by two cells, one of which has weight 0. Then the other must also have weight 0, so continuing in this manner we find that all cells in the top row have weight 0.

Now consider the following boxes:

Code: Select all

x = 92, y = 20, rule = LifeHistory
4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A
4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A4.
4A4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A$4A4.4A
4.4A4.4A32.4A4.4A4.4A4.4A$4.4A4.4A4.4A4.4A32.4A4.3A.A3.4A4.4A$4A4.4A
4.4A4.4A32.4A4.4A2.A.A.2A4.4A$A2.A.2A.A2.A.2A.CDBCB2CBCB.A.2A29.A2.A.
2A.A2.A.A2.CEBCB2CBCB.A.2A$A2.A.2A.A2.A.2A.E2BCB2CBCB.A.2A29.A2.A.2A.
A2.A.3AD2BCB2CBCB.A.2A$4A4.4A4.4C4B2C2A32.4A4.4A4.4C4B2C2A$4.4A4.4A4B
4C2B2.4A32.4A4.4A4B4C2B2.4A$.2A.A2.A.2A.A2.AB2CBC2BCBCA.A2.A29.2A.A2.
A.2A.A2.AB2CBC2BCBCA.A2.A$.2A.A2.A.2A.A2.AB2CBC2BCBCA.A2.A29.2A.A2.A.
2A.A2.AB2CBC2BCBCA.A2.A$4.4A4.4A4B4C2B2.4A32.4A4.4A4B4C2B2.4A$4A4.4A
4.4C4B2C2A32.4A4.4A4.4C4B2C2A$A2.A.2A.A2.A.2A.C2BCB2CBCB.A.2A29.A2.A.
2A.A2.A.2A.C2BCB2CBCB.A.2A$A2.A.2A.A2.A.2A.C2BCB2CBCB.A.2A29.A2.A.2A.
A2.A.2A.C2BCB2CBCB.A.2A$4A4.4A4.4A4.4A32.4A4.4A4.4A4.4A!

These boxes differ by two cells (highlighted), one in the top row, which we know has weight 0, and the leftmost cell in the second row from the top. Thus the highlighted cell in the second row has weight 0, and we can move along as before to show that all cells in the second row have weight 0.

Continuing in this manner, we eventually conclude that all cells in the NxN box have weight 0, contradicting the assumption that they sum to 1.

[amling]

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

The argument makes sense to me.

You could consider these two problems (the oscillator agar bound and the still life bound) to be 3-D and 2-D versions of a general restricted finite-size neighborhoods problem (the finite-size being the size of the CA check and the restriction being that it must be met). I believe in the 1-D case such weight-based bounds are asymptotically sharp, even with the silly choice of all-uniform weights. Roughly: any dense, wide window has to have a dense cycle and so windows can't be much denser than cycles. In the limit the "much" drops out. Unfortunately this relies fundamentally on the 1-D nature and the ability to patch solutions together at their 0-D boundaries and so I see no obvious translation to the original problems.

Nonetheless, it's enough to make me conjecture/hope that in the original problem(s) the weight-based bounds would be asymptotically sharp even if no individual one is.

[wirehead]

Probably would be an easy conjecture to prove: No isotropic rule has a 1-cell spaceship. And no isotropic 2-state rule has a 2-cell spaceship.

[confocaloid]

Probably would be an easy conjecture to prove: No isotropic rule has a 1-cell spaceship. And no isotropic 2-state rule has a 2-cell spaceship.

Isn't it intuitively obvious from symmetry? A single cell and every two-cell pattern are left unchanged by a 180-degree rotation. Such pattern cannot be a spaceship in an isotropic rule; otherwise, a 180-degree rotation would "magically" reverse the direction of movement, without actually changing the states of cells.

[wirehead]

Isn't it intuitively obvious from symmetry?

That appears to be a fair proof.

[amling]

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

The argument makes sense to me.

You could consider these two problems (the oscillator agar bound and the still life bound) to be 3-D and 2-D versions of a general restricted finite-size neighborhoods problem (the finite-size being the size of the CA check and the restriction being that it must be met). I believe in the 1-D case such weight-based bounds are asymptotically sharp, even with the silly choice of all-uniform weights. Roughly: any dense, wide window has to have a dense cycle and so windows can't be much denser than cycles. In the limit the "much" drops out. Unfortunately this relies fundamentally on the 1-D nature and the ability to patch solutions together at their 0-D boundaries and so I see no obvious translation to the original problems.

Nonetheless, it's enough to make me conjecture/hope that in the original problem(s) the weight-based bounds would be asymptotically sharp even if no individual one is.

Having spent more time to think about it, I have realized that the existence of aperiodic tile sets on lattices means there are counterexamples in the general 2D case ("general" in the sense of allowing arbitrary finite-window-adjudicable compatibility conditions).

I still conjecture/hope that in the specific case of the S23/B3 CA these bounds are asymptotically sharp, but it means any proof of such is going to have to rely on something more specific than mere locality.

[EvinZL]

Conjecture: The maximum density of any phase of a non-venetian blinds phoenix is 1/4

[1_1]

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?