Completed Section on Binary Rule, T, Substitution Rule

PDF, LaTeX.

I reordered the logic of the proofs and included the proof that the crystal satisfies the Binary Rule, according to David's comments in the post below. One thing that needs to be decided on is which Binary Rule to prove (regular or rotated?) and then after proving it for one, how to show that it holds for the other. We had a sketch of how to do this in the problem set writeup, but that argument used T^kC stuff (which currently follows my section on the Binary Rule).

Revised Exactly 1 Writeup

PDF, LaTeX.

After changing all the notation, I really don't like a_N^1 and A_N^1. I think the readability would improve if we gave the quadrant variable its own letter. How about we change Q_n back to being an occupied set rather than a region of Z^2?

Revised notation

Changes to the notation:

• We changed A_n to A_t to free up n so that we can abbreviate N = (2^n)-1.
• We clarified that B_N, D_N, and Q_N are regions of Z^2 and not occupied sets.
• A_N = tau^N A_0 is also equal to A_infinity intersect D_N (since there is no back fill)
• The set of occupied sites in the first quadrant is now A_N^1 (rather than Q_N as we had before)
• We also have some observations about how applying T conserves population and inserts a checkerboard of blank cells

I uploaded the PDF and LaTeX.

***** There is a slight problem with our notation for A_N^1. The definition of A_N^1 includes sites on the axes. This is okay for the rotated version of Exactly 1 because there are no occupied cells on the axes. However, the axes in the regular orientation are occupied. This means that it is not the case that A_N^1 = (TA_N) intersect Q_N.

The reason I am encountering this problem is that when I list some initial data for a_N and a_N^1 at the beginning of the Exactly 1 writeup, the data for a_N^1 on the regular neighborhood is not quite accurate because the sites on the axes are double counted. In other words, it is not the case that a_N = 4*a_N^1 -3, like it is for the rotated scheme.

An easy fix would be to simply not give initial data for a_N^1 at the beginning of the Exactly 1 writeup, but instead just initial data for a_N (since this is indepedent of whether we are in the rotated or regular neighborhood).

Section 5. of outline -- almost done!

I am almost finished with the section on the the transformation T, Binary Rule, and substitution rule (section 5 of our outline). The only thing that remains is to show that A_infty = union of T^(2k)C (k=0,1,...). I am not sure if we ever did prove this, and I'm not quite sure how to do it. I think what we did show is that this union of even iterates of T applied to the checkerboard satisfies the Binary Rule. However, we never proved, in turn, that the Binary Rule holds for the Exactly 1 Rule.

I think the approach we are taking in the writeup is:
1) Prove that U(T^(2k)C) = A_infty (not done)
2) Prove that U(T^(2k)C) satisfies the Binary Rule, and hence A_infty satisfies the Binary Rule (done)
3) Prove that the substitution rule satisfies the Binary Rule, and hence produces A_infty (done)

How do we prove item 1)?

I've uploaded my writeup here: PDF, LaTeX. I have done a lot of work on the other sections, so please read over that if you can (or we can scrutinize it in lab sometime).

1 or 3 Rule

By inspection:
Q_N = 2Q_(N-1) + 8r_(N-2) + correction

By recognizing that by population count that r_N = Q_N (The alternating boundary acts as a row of zeros since the rule is 1 or 3, thus the growth of the r_N's is identical to q_N's on the NE half, and shifted by (-1,-1) on the SW half.) and finding correction through Excel we get
Q_N = 2Q_(N-1) + 8Q_(N-2) - 6

Upon examination the cells which are repeated are at locations:
(2^(N-1), 2^(N-1)) twice,
(2^(N-2), 2^(N-1)+2^(N-2)),
(2^(N-1)+2^(N-2), 2^(N-2)),
(2^(N-2)+1, 2^(N-1)+2^(N-2)-1),
(2^(N-1)+2^(N-2)-1, 2^(N-2)+1),

By subtracting by Q_(N-1) to remove the constant
Q_N = 3Q_(N-1) + 6Q_(N-2) - 8Q_(N-3)

which gives us the characteristic polynomial
x^3 - 3x^2 - 6x + 8 = 0

with roots 4, 1, -2. Thus:
Q_N = c_1*4^n + c_2*(-2)^n + c_3

Fitting this to data for Q_3, Q_4, Q_5, we get
Q_N = (4^n+2)/3.

Since the whole box B_N = 4Q_N - 3 (the origin is counted 3 times too many), B_N = 4/3*4^n - 1/3. Since this is the rotated version, it follows that the density of the 13 rule is 2/3.

Undergraduate Symposium

Hannah and Mike: would you like to present at the Undergraduate Symposium on Thursday, April 12th? A poster or something maybe? The application deadline is February 26th.

Follow this link for more info.

Exactly 1 Finished Writeup

I have finished the writeup for the Exactly 1 Rule (section 2. in our outline): PDF, LaTeX. It still needs pictures and some polishing.

Edits to "Notation" document

1. The definition of tau_I: We defined only tau_1, not the more general tau_I. Also, I believe the "cup" should be a "cap."

2. Last line: q_n should be q_N, since this is at dyadic times. I also added the definition for b_N.

3. I think the "box neighborhood" and "diamond neighborhood" aren't really neighborhoods in the way that we think of the neighborhood of a point. I think better terms would be dyadic box and dyadic diamond, or something like that. Suggestions?

I've made changes 1. and 2. and uploaded the new notation document here: PDF, LaTeX.

Lab notes 14/2

Here is the notation file in DVI and LaTeX formats for your viewing and using pleasure, respectively.

Writing notes:

Use the "Proposition" convention for statement of asymptotic density of each diamond, and Lemmas for any support.

We need to think about where to use pictures and which ones.

Notation, Notation, Notation...

Here are the re-writes for the trivial 1or2 cases and 1or4 case, but i notice that even my notation isn't exactly consistent, let alone consistent with Charlie's. I think we should spend some time today in lab agreeing on notation conventions.

Updated Exactly 1 Writeup; Reordered Outline

I wrote up the section about the population count formulas for the Exactly 1 Diamond rule that we derived today. I made this the first section of the Exactly 1 writeup. I uploaded the PDF and LaTeX.

On the last page of the PDF writeup is the outline, which I have reordered somewhat. I put the proof by induction of the cloning process immediately after the new section on population count formulas. Next comes stuff about the transformation T. (Note that I copy and pasted relevant stuff from last semester into the PDF for these sections, and I still have to re-write these sections.) Let me know if you have suggestions for the outline/order of the writeup.

Exactly 1 Diamond Writeup

Re-writing the Exactly 1 Diamond section using the order of topics below (namely, with the Binary Rule at the end, sortof as an afterthought) will be harder than I anticipated. We used the Binary Rule extensively to prove things listed before it on the outline below (especially item 1). Anyway, here's my first stab at it: PDF, LaTeX.

Updated Exactly 1 Diamond Outline

Here is the PDF and LaTeX of the updated outline, which incorporates David's suggestions.

I altered the order somewhat to the (hopefully more logical) following: transformation T,
cloning process, proving density = 2/3 two ways (cloning process, transformation T), the Binary Rule, and the Substution rule.

Formulas for the population counts of diamond rules

Do we want to find the formulas for the population counts of the diamond rules at time (2^n)-1, like we did for the box rules? Or just the asymptotic densities?

Exactly 1 Diamond Rule

First I'm working on what to include in the section of the paper about the Exactly 1 rule on the Diamond Neighborhood and how to organize it. I wrote a list of things that could be included in LaTeX; you can get the PDF here and, if you would like to modify it, the LaTeX file here.

Fortunately, we have a rough draft of each of the items I mention. The first step I'd like to do, however, is to get your input on what to include and what organization to use (order of items, depth into which I write about each item, etc.). Then the next step would be to polish and improve the rough drafts of each item.

174

The blurb Charlie sent looks good. I agree with Mike that this argument should be included in the discussion of 1or4 (the example in NKS). Then one can describe the dynamics in a little more detail by noting that 1or4 is "solid" at all times in the sense that it equals Exactly1 at the same time but "filled in," and that 174 at that time consists of the filled in region intersected with the checkerboard C.

A New Kind of Science

As far as I can tell, the only mention of "1 or X" box/diamond rules in ANKS is on pages 170-172. Wolfram shows pictures of the evolution of 1 or 4 diamond rule (code 942) on page 171, states that the rule "yields an intricate, if very regular, pattern of growth," shows a 3D space-time display of the evolution on page 172 -- and that's about the extent of it.

The only other remotely close rule he describes is the "3 or 5" box rule (not counting self) (code = 175850) on page 177, the pattern of which he asserts has "seemingly random irregularities, at least on a small scale" but on a larger scale it follows a "rather smooth curve."

The missing page!

I've replaced PackardOriginal.pdf with an even funkier photocopy that has the missing page.