For Israeli and Goldenfeld
it's all about taking
one of two possible paths
and getting to the same place
One path says
Okay, look I have a fine-grained description
of the system
I'm going to evolve it forward
with my fine-grained rule and at the end
I'm going to simplify the answer I'm gonna say look yes
I mean I kept track of all these details
but in fact
you know what?
I only need to know some of the output
I only need to know some of the final stages of system
So you can think of that as sort of walking along like this and then projecting up
Another way you can do it though
right, is you can say look you give you this fine-grained description
but I know I don't really care so much about this I'm going to project that down.
Here's my fine-grain beginning initial condition
I'm going to project that down to a simpler
description and then I'm going to use a new rule
that allows me to evolve that simplified description forward.
So there are two paths and if you've done it right,
they'll get you to the same place
evolve the fine-grained system forward and project or
project and evolve the coarse-grained description forward.
A mathematician would say that these two operations
right, the operation of evolving forward and the operation of projecting up commute
you can do one or the other in either order,
and you'll get the same answer
A then B projecting then evolving is the same as B then A
evolving and projecting.
So let's see how this plays out with a particular example.
Again, I'll just take one from their paper.
This is rule 105. Rule 105 is quite similar to rule 150 which you've seen before.
It takes the XOR of the three pixels above the pixel in question
and then inverts them.
So that's the only difference between rule 105 and 150 is that final inversion.
Another way to think of that is
equivalently, the output is black when there's an even number of black cells above.
alright
So now you know what we have to do, right?
The first thing is we're going to consider not the final state of one pixel
but the final state of two pixels.
And we're going to ask what happens
not when you take one time step but in fact when you take two time steps.
And that means that those two final pixels will depend on a group of six pixels
two time steps previously.
And now we'll consider those pairs of pixels to be the supercells.
So you have a big supercell here, which is two pixels [takes] four possible states
and you have three supercells up here.
So that's our f hat
What we have to do now is find a combination, a projection
p that takes that supercell and summarizes it,
simplifies it.
It maps each of those four possible states down to one of two possible states
We have a projection p and we want to find an evolution operator g
that allows us to evolve forward
those projected down superstates.
So the p is what takes you from the fine-grained descriptions up
to the coarse-grained description
and that g is what's going to take you
between to coarse-grained descriptions at different times.
So you can either go
f, f, f, f, f, p or
p, g, g
right
For every two times you iterate f you're going [of course] only to iterate g once
and this simple example
we'll just do the case where you skip one step and so you have supercells
of size two
so
Fortunately it turns out
It is possible to find a p and g that enable that diagram to commute and here it is in the case of Rule 105
Right in this case the projection rule says look if the supercell has one cell
that's black and one cell that's white make that's all white if
Both cells are white or both cells or black
then make it black
It's sort of like an extra rule
itself in fact
Actually, it looks a little bit like an edge detector
it's as, look, if there's a difference within the supercell mark it one way
But if there's no difference in the supercells that are homogeneous mark it the other way
If you use that projection operator then it turns out in fact that your g
Right which is now of course taking binary values right take a binary value because you projected the four possible states supercell down to a cell
It only has one of two possible states, and that's what g operates on
that g evolution operator actually turns out to be rule 150
So what we've shown
is that it's possible to find a non-trivial coarse-graining ??? an interesting one ???
to find a non-trivial coarse graining and
an evolution operator that's still within the space of
cellular automata some of an evolution operator that enables that diagram to commute.
And so now just as we were able to talk about different kinds of
Markov chains coarse-graining into each other
we're now able to talk about how rules coarse-grain into each other.
And in fact for a non-trivial projection operator Rule 105
course-grains into rule 150.
Here's what it looks like.
In the top you can see the fine-grained level description
and the bottom you can see the coarse-grained level description.
At the top there you can see that we have the smaller pixels
and those smaller pixels are both
small in the x direction along this axis here
and smaller in the time direction
then in the coarse-grained case the coarse-grained case of course
???mps pairs of states into one and then in fact the jumps are now larger
there are two time steps instead of one.
And by looking at the the comparison between these two
you can sort of see what's going on, right. First of all of course
the coarse-grained description is capturing something interesting
about the fine-grained description, right.
We still have this idea that these triangles are sort of
These these little perturbations that begin
That we begin with that lead to these expanding ways
right we still get that kind of wave like texture.
These sort of propagating spaces that have kind of internal structure
But you can also see that we are missing things too, right?
So if you look at those two triangles at the fine-grained level
one of them is sort of darker than the other
But in fact when we coarse-grain the differences between those two triangles goes away.
So somehow rule 150
when we evolve it forward is operating our coarse-grained descriptions.
That's thrown out some interesting features of Rule 105
another obvious feature here that distinguishes rule 105 from rule 150
is that we lose that kind of zebra stripe pattern
and that's of course because if
A pair of squares is both white or both black
the projection operator maps them both into a square that's both black.
So we've lost some of the structure
both in the sort of places where those opening
Propagating triangle waves have sort of reached it
and also within the triangles themselves
This gives you a little bit of a better sense
now as we'll see it's not always the case.
That's the picture that you get
when you coarse-grain
looks
similar in some important respects to the fine-grained descriptions
Here it's a particularly elegant example of how we we're able to capture something about the rule
But of course not everything
we can't really capture everything of course
because that projection operator
is a lossy compression, it throws out information.
And for rule 105 it really matters
whether everything is white or everything is black
But in fact the rule 150 when we do the projection
it masks both of those cases to the same state.
so
Israeli and Goldenfeld hacked and they hacked and hacked and hacked
and they looked at all 256 rules. And they tried to figure out
how or the extent to which one rule could course-grain into another.
So these arrows here show you how it's possible
to find whether or not it's possible to find a projection operator
and an evolution operator that allows one rule set to map to another
upon that coarse-graining and in fact they consider not only
supercells of size 2 but also size 3 and size 4 and
and computation of this starts getting really hard
because there's so many different kinds of projection operators you can use
and there's so many different possible
evolutions that you can pick that you start to run out of time
it gets exponentially hard to find a good projection operator,
that gets exponentially hard to search the space.
There's only a partial map, but what you can see here is for example
in the bottom the result that we just talked through a little bit laboriously
which is the fact that it's possible to find a projection operator
that takes you from state 105 or
from evolution rule 105 to evolution rule 150.
By the way one of the things you can notice from this graph
is that it's clear that Israeli and Goldenfeld
haven't actually found every possible coarse-graining relationship.
And that's because there should be a feature of this network
that doesn't actually happen.
And that's that if A coarse-grains into B
If A renormalizes into B,
if it's possible to find a projection and evolution operator to take A and B
and B renormalizes into C
it's possible to find a projection that takes B into C
then it should also be possible
to renormalize A into C
of course now you're going to be course-graining twice
and it's harder of course for Israeli and Goldenfeld to find those
but if you look at this chart
what you should see
is for example the fact that not only does rule 23 coarse-grain to rule 128
and not only does rule 128 coarse-grain to rule 0
but it also should be the case that it's possible for rule 23
to coarse-grain all the way down to rule 0
just by doing two projections and zooming out even further.
That said Israeli and Goldenfeld did a pretty good job
looking at an enormous number of possible
relationships between all of these possible rulesets
And I find these diagrams quite compelling.
It tells you something really complicated, really interesting about how
deterministic rules and deterministic projections
map into each other other.
One of the things that you'll see from that network
is that not only does rule 105 coarse-grains to rule 150
but in fact rule 50 coarse-grains into itself.
So the pretentious way to say this
this is a fixed point of renormalization group.
With that projection operator
you actually take rule 150 into a zoomed-out version of itself.
You sort of skip a step, you project down the supercells
and you recover the same rules.
Now it's important to notice there's a subtlety here, right.
It doesn't mean that the image itself is self-similar
doesn't necessarily mean the rule 150
is kind of fractal in some interesting way.
Because the coarse-graining may not be
the kind of coarse-graining that just simply zooms out.
Consider for example the projection we had going from rule 105 to 150.
Now wasn't a simple decimation in the way that we did on the Alice picture for example
at the beginning of this renormalization module.
In that case, right, we're renormalizing Alice. We took her picture,
we looked at little packages of cells, and we just take one of the values to define
The value of that grid of that larger grid cell
that's supercell in the Alice case.
But if you remember the rule 105 to rule 150 projection
that worked and that case was actually an edge detector.
If the cell was all white or all black
it got mapped to something that was all black.
So it doesn't necessarily mean that if you kind of fuzz
rule 150 it still looks like rule 150.
It really depends upon the details of that projection operator.
That said in fact you might think of it another way.
Ihe rule 150 is a fixed point of renormalization group
with potentially a much more interesting projection
than a simple decimation.