Unproven conjectures

[LuveelVoom]

Write-up of everything "achieved" (again, it's AI, so it's unverified and none of the stuff here is necessarily true (except for the 16/31 bound and the degree lemma, which have been checked)

R2 and R3 are just rewordings of R1, useless

R4 is an just an argument, not worthy of being a lemma (overcrowded live cell must have not been overcrowded 1 gen before because it is alive)

R5 is Ai tryharding feeling obligated to use notation it introduced but haven't used. I think it's incorrect

R6 is total bs

R7 is useless, I think.

it skipped R8, lol

R9 doesn't even prove anything. It's just introduction, empty burger

Appendix is useless

(except for the 16/31 bound and the degree lemma, which have been checked)

what's a degree lemma?

Glad to see these things are not infallible yet.

[The degree lemma is that any agar where no cells die of overcrowding has density <1/2, which feels extremely obvious but doesn't seem to have been proved before] EDIT: This... this is Elkies' theorem. I might be dumb.

[LuveelVoom]

Supposed "corrected version" based on your criticism. I skimmed it and it seems somewhat better.

[g0t0]

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.

This is infinite soup. Quadratic growth can't remain forever.

What does 'Around 37%' means?

[g0t0]

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.

Doing so at all the corners can cut upper limit?

What if two corners is a same cell?

However, do it at the highest and lowest is correct and can cut the bound to 3n-2.

[yyh_baboon]

Doing so at all the corners can cut upper limit?

What if two corners is a same cell?

However, do it at the highest and lowest is correct and can cut the bound to 3n-2.

I actually noticed that 2 cornrers can be the same cell, thus deriving at the limit of 3n-2. But when the population is sufficiently large, can we do further improvements to bring the population upper bound to 3n-6?(this is attainable by a 1*n line)

[HartmutHolzwart]

Supposed "corrected version" based on your criticism. I skimmed it and it seems somewhat better.

Can this method be used to derive an even stronger bound for p2 and p3 oscillators? Can we use it to find out more on the space of possible density pairs resp. triples? Like limiting the maximum density of the densest generation?

[yujh]

I have did a bit of things myself (not really sure what the ai is doing) and I do not believe checking 3x3 or 3x4 areas yield new bounds. However 4x4 does seem to give better bounds for p2 agars:

Code: Select all

2  5  5  2
5  15 15 5
5  15 15 5
2  5  5  2

seems to give 5/9 using just previously mentioned methods in this thread. I have not verified this yet.

I will include some details later when I do 5x5

[g0t0]

Doing so at all the corners can cut upper limit?

What if two corners is a same cell?

However, do it at the highest and lowest is correct and can cut the bound to 3n-2.

I actually noticed that 2 cornrers can be the same cell, thus deriving at the limit of 3n-2. But when the population is sufficiently large, can we do further improvements to bring the population upper bound to 3n-6?(this is attainable by a 1*n line)

Cornrers? What's your first language?

I think we can cut it by excluding 1xn bounding box.

[NooneAtAll3]

I have did a bit of things myself (not really sure what the ai is doing) and I do not believe checking 3x3 or 3x4 areas yield new bounds. However 4x4 does seem to give better bounds for p2 agars:

Code: Select all

2  5  5  2
5  15 15 5
5  15 15 5
2  5  5  2

seems to give 5/9 using just previously mentioned methods in this thread. I have not verified this yet.

I will include some details later when I do 5x5

what are those numbers?
is that previous approach or smth?

what Ai did was given frequencies to whole patterns, not individual cells

best result for previous approach for p2 was

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)

are you sure you didn't set up p1 accidentally?

[NooneAtAll3]

EDIT: This... this is Elkies' theorem. I might be dumb.

yeah, doesn't help that in his paper he introduces it as conjecture, spends most of the paper discussing different problem and then whams you with "proof of conjecture"

nowadays people are usually more careful, using "conjecture" only for unknown stuff and "theorem/our main result" for "we'll prove it in the latter half"

Supposed "corrected version" based on your criticism. I skimmed it and it seems somewhat better.

definitely better - I can understand eigenvalues theorem (R6) now!
apparently not bs, just spectral graph theory :/

Ai seems to still be confused between density-within-generation and density-over-multiple-generations, but magic of this theorem is that it works in both cases (as long as you count separate generations as non-neighbouring)

I've tried to make the proof more presentable, but it's essentially density <= (avg neighbours in set - min_eigen)/(avg neighbours total - min_eigen) and getting eigen lower bound of -4 on Moore requires spectral machinery...
Elementary machinery, mind it, but still very clunky to write down all the required introductory proofs

I think there're slightly easier arguments for -8 (all cells have 8 neighbours) and -6 (split cells into 2x2 groups + 5 edges per node connecting outside) bounds, but eigenvalues are still very disconnected from graph and weights intuition

---

R8 and R9 got finally written down, but they seem useless and only cover one specific case each (and even then limited)
R5 got explained better, so I raise my grading from "incorrect" to "useless". Basically covered by LP method

===

also, if I understand it correctly, there might still be some juice to squeeze by adding constraints about 1x1x1, 1x1x2 and other sizes (or even shapes) while still not growing beyond 3x3x2 superlife rule

if you do go outside 3x3x2, I think amling had much more success with pyramid shape in the previous approach, so that might be worth an attempt, considering that it isn't really about symmetry of superrule encoding or inside region - only about translates of one fitting inside the other

I've spent some time on it and now can explain most general theorem and practical consequences:

Given
- 3 arbitrary sets of cell-moments of Life "spacetime" - smallSet, BigSetA and BigSetB
- 2 relative positions of BigSets from the smallSet - A and B
- assignment of cell liveness for the smallSet

For any evolution of Life universe

1) place smallSet on every cell-moment
2) mark smallSets equal to the given liveness assignment
3) for every smallSet place BigSetA at displacement A - set AA; BigSets placed relative to marked smallSets form set Aa
4) for every smallSet place BigSetB at displacement B - set BB; BigSets placed relative to marked smallSets form set Bb

Now ratios |Aa|/|AA| and |Bb|/|BB| are equal, due to 1-to-1 correspondence (|AA| == |BB| == cell-moments, |Aa|==|Bb|==cell-moments with marked smallSet)

---

Obviously, since the result is about subsets of BigSets, we'll be operating on separating those
And obvious way is to split by "cell liveness in BigSet", forming equivalence classes ("Superlife A/B" colors)
And to make theorem's subsets go cleanly along borders of equivalence classes, it's sufficient to make smallSet be within BigSets

Now, you can just assign a separate variables to equivalence classes of both BigSets and run wild totally free to choose arbitrary BigSets... But I have a feeling that won't be as useful

So obvious goal is to make equivalence classes for both coincide and be represented by same variables (same "SuperLife" rule for both)

If you do choose same BigSet in exact same orientation, just translated sideways - you're guaranteed to get that.
If BigSets are of different shape or anything other than Life's space symmetries away from each other - you're guaranteed to fail

Question then becomes "what if BigSetB is rotated/mirrored version of BigSetA? (i.e. smallSet is rotated/mirrored when creating linprog constraint)"
after going back and forth for while, I think I managed to convince myself that classical "given Life universe evolution, take 8 rotated/mirrored copies of it - then apply theorem on union of them" should suffice
(linprog already operates on such mix, and upper density bound stays the same)

---

The last useful part is that smallSet should be maximal - that is, if you add constraint about smallSet in positions A and B, you don't need to add constraint about smallSet's subset at position A and exact same subset at position B
That's basically doing "a1=b1; a2=b2, but now add a1+a2=b1+b2 "

But note that this doesn't cover different subsets

The opposite way to look at it is that "smallSet is same in positions A and B" can be split into "smallSet is same and extra cell == live in positions A and B" + "smallSet is same and extra cell == dead in positions A and B" if that extra cell fits

So, for Ai example of 3x3x2 with 3x2x2 constraint - you shouldn't need adding 3x1x2 constraints for same (0;1;0) displacement, but you can add one for (0;2;0) displacement of one against the other

---

All that suggests following algorithm:

Code: Select all

given BigSet of cell-moments

make a list of all possible evolutions passing through it (linprog variables)
add constraints "sum of all evolutions = 1" and "0 <= every evolution <= 1"

take 2 copies of BigSet
for all combinations of displacement, rotation and mirroring of one against the other:
    find where 2 copies intersect
    intersection set is smallSet
    location of intersection inside either BigSet copy are subsetA and subsetB
    
    for every cell assignment of smallSet
        create weighted sum
        for every BigSet evolution
            if subsetA == smallSet cell assignment
                add +1 to evolution's weight
            if subsetB == smallSet cell assignment
                add -1 to evolution's weight
        set constraint "weighted sum == 0"
                
create weighted sum
for every BigSet evolution
    if central cell is live
        add -1 to evolution's weight
optimize for min weighted sum     # linprogs usually search for min

if BigSet is symmetric, some of the resulting constraints naturally say that rotated evolutions have equal frequency - but be careful with combining them into one variable, because sum weights might not be {-1, 0, 1} anymore

it's necessary to have all BigSet evolutions represented for the bound to be valid, but it's fine to have extras. It's also fine to only add part of the constraints - your bound would just be weaker