Counting lakes

For general discussion about Conway's Game of Life.
Post Reply
Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Counting lakes

Post by Elithrion » February 6th, 2009, 12:46 am

On the counting of lakes, from http://www.conwaylife.com/wiki/index.ph ... =Talk:Lake

The definitely true conclusions so far are as follows:
-counting lakes is equivalent to counting SAPs with an extra properties. All the properties are then as follows: 1) the walk must never intersect itself, except 2) the last step of the walk must bring you back to the origin, additionally 3) every step must be orthogonal (that is, in a direction that is perpendicular) to the one before. Finally, the number of steps is equal to half the number of cells in the final lake, but this isn't interesting enough to get its own number.
-notation: the number of steps is going to be k, the number of cells is c, the number of the length of the walk is n, so that "n = k/4 = c/8". I'll also sometimes use italics, and sometimes not. S_n is the number of walks with 4*n steps.
-only walks with "k mod 4 = 0" are allowed (that is, the number of steps must be divisible by 4, and the number of cells by 8)
-you get back to the origin on the last step if and only if (iff from here onward), the number of steps in each direction is k/4
-a walk of length k intersects itself if it contains a walk of length k', k' < k. The reverse also seems to be true.

So then, Nathaniel's program says that for n = {1, 2, 3, ...}, S_n = {1, 0, 1, 1, 4, 7, 31, 98, 446, 1894,...}. And yes, using sets there is a little sketchy notation-wise, but whatever.

My own conjecturing gives a few results that I'm fairly confident in:
-there are (k/2 C k/4)^2 = ((k/2)!)^2/((k/4)!)^4 walks that start and end at the origin, possibly intersecting themselves. The reasoning is that you have k/2 steps in each of the orthogonal directions, and you must assign exactly half to each of the opposite directions along those, then multiply the assignments together for the total number of combinations.
-the above formula gives you 4* too many walks because you can rotate them into one another
-the above formula gives you 2* too many walks because you can reflect them into one another
-the above formula gives you k* too many walks because you can displace them into one another (i.e. any point on the closed walk could be the starting point)


And now, on to the feature speculation!
By the binomial thingie, we have accounted for both requirements 2) and 3), so we only need to deal with avoiding self-intersection. I'm fairly sure that finding all walks of length k and then removing from them all possible walks that include previous self-avoiding walks of length less than k will give us the full count. To this end, my formula guess du jour is something like (this is more of a sketch than a conclusion):
S_(n/4) = 1/8k*((k/2)!)^2/((k/4)!)^4 - sum(S_i*(((k-i)/2)!)^2/(((k-i)/4)!)^4),i=1..k)
n/4 is used so I don't have to multiply k by 4 everywhere or amend my initial definition of S_n. The first part of the equation is obviously just the total number of walks (self-avoiding or not) adjusted for rotation/reflection/displacement. For the second part, the reasoning here is that we take all the smaller walks that we've found thus far, and we attach to each of them tails that would make the whole thing as long as the walks we're looking at now. So, now we have walks of the current length that have loops in them. Since we're counting all the walks we've found with all possible new tails (so that they still start/end at the origin of course), we should thus obtain (the number of) all walks of current walks that have loops in them, i.e. the ones that fail to self-avoid. So, having found the number of such walks, we subtract it from the number of total walks to obtain the number of ones that do self-avoid.

Of course, as I said, this is mostly a sketch. One immediate problem with it, is that the new tails we attach might themselves have loops in them, which would make us double-count a whole lot of cases. One solution I'm pondering is to stick in a bunch more recursion onto the tails we attach to make sure they are loopless in the same way we're trying to use for the walks proper. Before trying that, however, I'd like to figure out whether the rest of the theory/execution holds up.
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Counting lakes

Post by Elithrion » February 6th, 2009, 2:25 am

Okay, I got lost in notation after all. Let's define S(k) = S_(n/4), that is the number of possible walks we're looking for that have k steps. I.e. when it's a function it's referring to number of steps, not the number in the order. Yes, my own choice of notation was confusing me and this rewrite probably confuses anyone who's not me. Anyway, I was being silly. We know the number of tails we can attach, since that's just S(k-i). I'm pretty sure. Thus, the formula turns into:
S(k) = 1/8k*((k/2)!)^2/((k/4)!)^4 - sum(S(i) * S(k-i),i=1..k)

Oh, and "sum(,)" is obviously sigma notation, if that's not clear.
Also, let's say S_0 = 0, since that's not elsewhere defined.

One problem is still that I'm not entirely sure what needs to happen with reflection/rotation/displacement of the second half. The tail term might need a factor of *8k or something. Tempted to just try it with various factors and choose the best one instead of reasoning it through. Oh well, either way, I'll do this some more "tomorrow" (i.e. today, but after sleep).

[edit:] except make that ...-sum(S(i)*Z,i=k/2..k)
where Z = S(i_1)*S(i_2)*...*S(i_m), s.t. i_1+i_2+...+i_m = k-i
i.e. instead of multiplying by just the loops that can be produced by (k-i) steps, we need to account for the possibility of multiple loops, that is, lots of small loops, whose net length is (k-i). Also, starting at k/2 avoids double-counting.

And also, this won't be exact for small k, since some things are invariant under rotation/reflection and there are many of them for smaller numbers and few for larger ones, but we threw that factor anyway.

Anything in the edit may be totally wrong or silly, since it's late and I keep thinking "there's a good way to write that sum thing in Z, but I can't think of it!" Maybe multinomials?
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Counting lakes

Post by Elithrion » February 8th, 2009, 2:13 am

My idea - explained with pictures! (also, changed a little since last post, since I had made some mistakes/oversights)

Let's say we have all candidate walks with 60 steps. They all have steps orthogonal to the previous one and they all begin and end at the origin (i.e. form closed loops). But now we must find all the ones that intersect themselves! So, we find one candidate:
Image
But it fails because it intersects! But looking at it, we see that it's actually made up of 4 loops that we've found before. One has 36 steps, one has 16 steps, one has 12 steps, and one has 4 steps. Each of these loops is attached to another one. So, now we think to ourselves: in how many ways could we attach these loops to each other? Well, the 16 step one could attach by any one of its point to any one of the point on the 36 step one, so that's 16*36 for those two, then the 12 step one could attach by any one of its points to the 36 step one, so that's 12*36 for those two, then the 4 step one could attach, etc, so 4*12, for a total of 4*12^2*36^2*16. But! We could attach any of these loops in any state of rotation/reflection, so we need 4*12^2*36^2*16*8^2 (would be 8^3, but our 4-step and 12-step ones are invariant under rotation/reflection; also, the first one might as well be in a constant position so we don't get duplicates). But! We could have each of the loops be any of the versions we have available at each number of steps, so we need 4*12*16*36*8^2*S(4)*S(12)*S(16)*S(36). But! They could also attach to each other in different order (here, we have 4 to 12 to 36 to 16), so let's fix 4-step as "first. Then we have these combinations (12,16,36) to 4 -> 4^3*12*16*36; 16 to 4 to 12 to 36 -> 4^2*12^2*16*36; some analogous ones; and then 4 to 12 to 16 to 36 -> 4*12^2*16^2*36; some other analogous ones. Adding everything up, we get 4*12*16*36*(4^2+12^2+16^2+36^2+4*12+4*16+4*36+12*16+12*36+16*36)*8^2*S(4)*S(12)*S(16)*S(36). But! We can have different combinations of lengths, not just 4-12-16-36 so we need to do this for every combination that adds up to 60 steps.
(I'm still thinking up an excuse to throw multinomials in there - it would certainly make life much easier, but it's not coming to mind especially readily)

And that's about it. Count up all the bad combinations (as complicated as that is) and subtract them from the total. And you might be wondering why I'm posting an explanation of the reasoning instead of doing the job... well, for one, I need some validation that this is sound, and for another, this is sufficiently complex computationally that I'd probably have to write a program to do it (the "all combinations that add up to 60" is especially a chore), and that's a lot of work.

Oh, and we can't actually do 60 right now, since we don't know 56 or 52, but I just happened to draw one of that length by chance.




Also, an alternative "solution"! The orthogonality condition is actually pretty much equivalent to taking half the number of steps but being able to move freely (to visualise this, pretend you're moving diagonally), except for the very first walk, where with it you can get back to the origin and with half the steps you cannot. In every other case, though, the two options seem equivalent. So, if we replace orthogonality with shorter walks, we just get the need to count SAPs with no extra properties. And since they have a name, I assume there are already several papers out there that provide counts and maybe the formula is even known! *takes a bow*
Vi veri veniversum vivus vici.

User avatar
Nathaniel
Site Admin
Posts: 861
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada
Contact:

Re: Counting lakes

Post by Nathaniel » February 8th, 2009, 11:01 am

Elithrion wrote:Also, an alternative "solution"! The orthogonality condition is actually pretty much equivalent to taking half the number of steps but being able to move freely (to visualise this, pretend you're moving diagonally), except for the very first walk, where with it you can get back to the origin and with half the steps you cannot. In every other case, though, the two options seem equivalent. So, if we replace orthogonality with shorter walks, we just get the need to count SAPs with no extra properties. And since they have a name, I assume there are already several papers out there that provide counts and maybe the formula is even known! *takes a bow*
Are you sure about this? It seems then like the term for 8n cells should equal (except for the n = 1 case) the number of polyominoes with 2n cells, but that's not the case (see http://www.research.att.com/~njas/sequences/A057730). That URL is assuming that holes in the polyominoes are allowed, but that won't matter for small terms anyways (and in particular their value for 2n = 10 is less than our value for 8n = 40).

I'll think a bit more on your other stuff before replying to it ;)

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Counting lakes

Post by Elithrion » February 8th, 2009, 2:33 pm

Nathaniel wrote:(and in particular their value for 2n = 10 is less than our value for 8n = 40).
Well, as long as we're proving each other wrong, their value for 2n = 10 is actually greater than our value for 8n = 40. In particular, there are two cases that work with diagonal lines but don't work with two-step orthogonal ones, it seems (I had to draw it out to convince myself).
Image
And in more detail, Image Image
are the two possible attempts of going from diagonal to two-step orthogonal, both of which result in failure.


I'm still having some trouble wrapping my head around what specific element of the polygons makes this not work...
Vi veri veniversum vivus vici.

Elithrion
Posts: 100
Joined: February 3rd, 2009, 4:02 pm
Contact:

Re: Counting lakes

Post by Elithrion » February 10th, 2009, 5:36 pm

So, thought about it yet? :P Still think computing an explicit formula is "intractable" (spotted your blog post)? 'Cause I think this qualifies as traction of some sort at least.

Also, on the polyominoes note, it seems that the problem is that each side must be assigned an additional property, say, Inside or Outside. Adjacent sides have the opposite property, resulting in all vertical sides always having one, and horizontal ones having the other. Finally, two sides that are both "inside" may not lie within one space of each other. This last condition is impossible to meet if there is anywhere in the figure a pair of horizontal sides, and somewhere else a pair of vertical sides, so that the sides in both pairs are only one apart. That seems pretty hard (and fairly uninteresting) to quantify, but at least it's visually/conceptually convincing and covers the problem with my diagonal-lines proposal.
Vi veri veniversum vivus vici.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Counting lakes

Post by Macbi » April 1st, 2009, 12:57 pm

As an aside, I think that quasars can be extended in exactly the same way as lakes.

H. V. McIntosh
Posts: 49
Joined: June 20th, 2009, 5:26 pm
Location: Mexico

Re: Counting lakes

Post by H. V. McIntosh » September 2nd, 2009, 12:09 am

Macbi wrote:As an aside, I think that [... quasars ...] can be extended in exactly the same way as lakes.
All of this seems to be an exercise in random walks, which would also seem to include the enumeration of many other extensions. Some of them consist of inserting multiple copies of a given segment, and account for such sequences as x, long x, long long x, and so on. It is not hard to visualize what they should look like, nor how many of them there are, although it is not necessarily profitable to continue listing them. But there is often a choice between possible insertions, even though the resulting figure is still one dimensional. For example, the polyhats, while one dimensional, admit a two-dimensional variation in which the height of the vertical bar in each segment may remain the same, increase by two, or decrease by two (although not to zero). The bracketing bars have to be stabilized, but this can generally be done with a variety of hooks, blocks, and snakes. A special case arises when some regularity is required, such as returning to an earlier height; this becomes the parenthesis balancing problem. Finally there is the truly two-dimensional problem of enumerating lakes, chains of ponds, or the mentioned quasars supposing that one has decided how the extension should take place. By and large, these are all questions which can be resolved by graph theory, and particularly through the algebra of the connection matrix. What might be interesting is to look at this algebra and seeing how it works, rather than just consulting tables such as Sloane's.
-hvm

H. V. McIntosh
Posts: 49
Joined: June 20th, 2009, 5:26 pm
Location: Mexico

Re: Counting lakes

Post by H. V. McIntosh » September 3rd, 2009, 10:57 pm

I wrote:All of this seems to be an exercise in random walks
just as the first post on this thread said. The theory includes self-avoidance and closure, so it is mostly a question of understanding and applying it. What I hadn't previously realized is the multitude of extensible Life artifacts to which it is applicable, provoked by an encounter with "Beehive at beehive" and "Beehive at loaf." Of course there is also a "Loaf at loaf" and both can be convoluted almost at will. Somehow it seems that Life's vocabulary takes some of the blame for all the proliferation - specifically the separation between strict still life and "pseudo" still life.

Given enough empty space between objects or their furtherest reaches during a cycle, the rules of Life keep them from interacting. Near approaches are harder to categorize, but many objects are classified as "ties" which could just as well be separated from each other; in particular, this pair consisting of one horizontal and one vertical beehive. Would we call two parallel beehives separed by an empty line a "Bibeehive?"

Whatever; we have one glorious random walk here. Our walker, canonically an inebriated departee from a dispensary of alcoholic beverages, has the choice or turning left or right while lurching along. But instead of going straight ahead, there is another choice - turning into a werewolf or not. And of subsequently reverting. Nor must we worry about turning into a pumpkin at midnight; domino walks must close, but bread and honey are immune.

So much for ties. Looking through the catalogues, the term "bridge" occurs rarely, and often looks like a tie. In fact, somewhere I read that "tie" was appropriated so that there could be a "boat tie." Also, how often is "weld" used; such a thing is feasible, but is it often used in constructing compound objects?

Could we use some better definitions here and there?" Also, are things like "tail" and "claw" defined, or they just informal terms?
-hvm

User avatar
Extrementhusiast
Posts: 1966
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Counting lakes

Post by Extrementhusiast » September 6th, 2009, 1:12 pm

Well, this is a rather weird topic. Don't know why I'm posting this, but I just thought I'd comment.
I Like My Heisenburps! (and others)

H. V. McIntosh
Posts: 49
Joined: June 20th, 2009, 5:26 pm
Location: Mexico

Re: Counting lakes

Post by H. V. McIntosh » September 6th, 2009, 7:36 pm

I wrote:Could we use some better definitions here and there?" Also, are things like "tail" and "claw" defined, or are they just informal terms?
By searching through the LifeWiki I could probably answer my own question. "Tail" has an entry and is mentioned on some 70 pages, but "Claw" and "Hook" do not although they are mentioned on nearly as many pages. At "Six L's" we find that the tails constitute the whole dog. The terms seem to attract adjectives like "long" or "on" which are readily understood as applications of their colloquial usage.

Perhaps some additions to the Glossary section would be useful, particularly if one would like to see the naming system reflect the structure of Life artifacts more accurately. On the other hand, since so many names have already been assigned, the best that might be expected would be to warn the unwary of the variations. Given that the topic of this thread is "lakes" or "random walks" it might be noted that having polymerized likely candidates, the appropriateness of polymerizing their names follows.
-hvm

User avatar
PM 2Ring
Posts: 152
Joined: March 26th, 2009, 11:18 am

Re: Counting lakes

Post by PM 2Ring » September 10th, 2009, 6:18 am

I must confess I don't have much interest in counting lakes, but IMHO the issue of naming systems for Life patterns is an important one. Perhaps it deserves its own thread...

Post Reply