Master document with changes to captions

I made changes to some of the captions and uploaded the latest LaTeX and PDF. I also uploaded a zip file containing those two files and all the pictures (.eps format).



Two questions about captions I wasn't sure about:

• should they all be complete sentences?
• should they all end with a period (even the really short ones)?
  

pictures.......

So LaTeX is a pain in the rear end, I've spent countless hours trying to get this file built correctly with the pictures not fuzzy. Sorry that it took so long. I was only able to build it correctly as an EPS file for now, maybe I'll figure out how to get a PDF or DVI soon. Anyway, we should go over in lab the following:

-captions of pictures
-intro, I wrote some gibberish down, but not anything complete or 100% correct
-convergence issue of 4 condition
-abstract

The formatted pictures, source file and EPS file are in this folder:

http://mywebspace.wisc.edu/maretzlaff/web/cafinal/

Latest Master Document

This contains Hannah's section on tau_134.

LaTeX, PDF.

Mike -- can you please confirm bibliography item 9. There was no label for that (do we reference it in the paper?), so I called it "w2." Also there was an ñ in the page numbers; I figured this was supposed to be a hyphen and so changed it to that.

134

PDF TEX

PDF version of latest master document

I uploaded the latest master document from Mike's post below to my webspace: LaTeX, PDF

David's corrections

I have incorporated all of David's corrections, and Charlie and I went through my initial draft of the notation section together to streamline it. By tomorrow I plan to have something written for the background section. Here are the DVI, PS, LaTeX files.

notation section with words!!!!

lets go over in lab today, then talk about pics. Here is the DVI and TeX.

Revised Master Document

I made some slight changes to Mike's sections -- mostly making language consistent with what I've been using (e.g., "Exactly 1 rule" instead of "exactly 1 diamond") and fixing a couple of spelling mistakes, etc.


One issue I encountered: Mike uses the Binary Rule to prove rho_14 = 1 before the section in which the Binary Rule is introduced. Perhaps we should move the Binary Rule section up. Also, the 174 section uses the Binary Rule before the Binary Rule section.

I feel like we should add a sentence that explains in English that tau_14^n is the same as applying tau_1 (n-1) times and then tau_14 once. I think that would help the reader understand those lemmas more easily.

Another question: What do we mean when we say the "1 or 4 Diamond"? Is that the 1 or 4 "crystal" (i.e., the occupied set)? That term is a bit confusing because we also have D, the diamond region, and the diamond neighborhood (von Neumann).

Do we capitalize titles of sections? (For example, "A perturbation of Exactly 1" or "A Perturbation of Exactly 1")

I have uploaded the LaTeX and PDF to my webspace.

I also made bitmap images in MCell of all of the figures that we need (Zip file). Next week in lab we will edit these in Photoshop.

updated master with inserts

New with what we added in lab today (references, 14, 174, 12). in DVI, TEX, PS formats. I am going to take a stab at making the introduction and notation readable this weekend.

Updated Master Document with introduction to T

I wrote the introduction and motivation for T section of the paper (section 1.3). Feel free to modify it in lab tomorrow. Email me the updated master.tex file after you finish tweaking it and I will upload it to my webspace.

LaTeX, PDF

References

How should we list references? That is, what's the best way to do it in LaTeX?

I googled around and found BibTex -- do we want to use this?

Master document with David's changes

LaTeX, PDF

I could understand all the scribbles except the change to the first sentence of the Substitution Scheme section. Before, it read: "The Exactly 1 rule is one of few cellular automata that admit...." Now it reads: "The Exactly 1 rule is one of few non-trivial, solvable automata that admit...." David -- you might have written "finite" after "solvable," but I can't tell for sure.

Updated Master Document

This version now contains the notation in the introduction and has the updated version of the 13 section using interiors of the triangular regions.

LaTeX, PDF

Something that occurred to me that we should consider: Should we write down what exactly are the 4 rigid transformations for regions III-VI (i.e., the rotations and translations) like I did in the exactly 1 section?

Updated 13 section

The solution we came up with for the P_I = P_III issue is that the cells (1,N) belongs to P_III but is not covered by the rigid transformation of the configuration in I shifted by (+1,-1). (Likewise for P_V.)

LaTeX

Draft of 1 or 3 figure

New revised figure draft for 1 or 3.

figure

Is this a reasonable format, or shall we do something different (keeping the paper cohesive)?

References

Also, please gather a preliminary list of references and add them as a final section in the main document.

Get to Work!

Charlie's post looks like a big improvement. I'll see the three of you on April 9. It would be great if a little more progress could transpire by then. For starters,

* a reasonably polished draft of the 14 section by Mike;
* a good start on the 134 material by Hannah;
* insertion of the Notation into the main document (including the new rotation notation).

Also, first drafts of the figures would be great.

Have a nice break,
D.

2 things to do / keep in mind

1. Delete unnecessary "rotated" throughout the document
2. Include periods, commas and semicolons in displays

1 or 3 triangle business

I think I got the triangle book-keeping down in a relatively neat fashion. It required some new notation (P_I for the population in region I, P_II for region II, etc.), but I think it's pretty slick in the end.

Master document: LaTeX, PDF

Suggested change: instead of

"we examine the six triangular regions and one square (see Fig. **) bounded by"

how about we delete the "bounded by" (it's awkward because we give region 7 as a Cartesian product) and change all the ='s to >='s in the description of each region.

Also, we need to add a paragraph to this section proving "no backfill."

Six triangle picture

Here's a possible picture to illustrate the triangles.

pic

First draft of 1 or 3.

Here's 1 or 3 so far.

pdf
tex

Master document; proof of "no backfill" for exactly 1

Here is the LaTeX and PDF for the "master document" (i.e., the document containing all of the sections). I included section titles for 14 and 174 (M) and 13 and 134 (H) as placeholders.

The proof of "no backfill" for Exactly 1 is at the top of page 4. The other new thing is that I introduce the claim of "no backfill" in the third paragraph of Section 2: Exactly 1 (page 2).

A couple of things to consider for the "no backfill" proof for Exactly 1:

• I showed it for the rotated version; should we bother to show afterward that it also holds for the unrotated version?
• In the second paragraph of the proof (the "assume holds for n and show holds for n+1" part), I may need to say a bit more. For example, I may need to show that the sites outside B_N_(n+1) cannot affect sites in B_N_(n+1) because of Lemma 2 (analogous to the statement in the previous paragraph in which I show that sites outside B_3 do not affect sites in B_3 because of the boundary of empty cells formed by Lemma 2). Or is what I have written enough?
  

Introduction

I started working on the portion of the introduction that proves properties of the transformation T. I am struggling with the second part of the proof that the T^kC partition Z^2. Here is the LaTeX, PDF.

Consequences of the change of notation

Here is something to consider: if we change the subscript t's to superscript t's, we must change the following:

1. A_t
2. B_t
3. D_t
4. Q_n
5. a_n
6. q_n

...and there may be more that I can't think of right now. Do we really want to make a change in notation that makes 6 objects look somewhat awkward just so that A_I^t looks like tau_I^t? I think it'd be okay to have A_t^I but tau_I^t. After all, we already had rho_I for the asymptotic density, which bucks the trend that we had of subscript t for objects 1 through 6.

Section on Binary Rule, T, Subsitution Rule

I worked on this writeup some more, and it's almost done. PDF, LaTeX.

One question that came to mind: Our current wording of the Binary Rule holds only for the first quadrant; do we want to throw some absolute values in there to extend it to the other 3 quadrants?

Another question to consider: split up Corollary 1 into two corollaries or keep it as one corollary?
1) A_infty = UT^(2k)C
2) A_infty satisfies the "complementary Binary Rule"

updated trivials and 14

here are updated documents for 1or4 and 1or2. I will add the wolfram 174 thingy and have something "tangible" for 134 rule by monday.

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.

A good exercise and remark for the paper

We discovered today that Packard-Wolfram has a supposed solidification rule that is in fact Exactly 1 modified so that a 1 that is completely surrounded becomes a 0. This can be analyzed as another perturbation of Exactly 1. We have the tools to show that the final configuration is simply a checkerboard (and so has density 1/2) and that the state at any point in time is that checkerboard intersected with the corresponding state of the 1or2 rule. Work out the details and remember to include a remark in the write up.

Outline for paper for Diamond rules

1. Introduction / History / Notation, Lightcone/Sierpinski, 12x rules, T and its properties
2. 1 (C)
3. 14 and 174 (M)
4. 13 and 134 (H)
5. Binary Rule, A = Union of iterates of T, and Subsitution rule (C)
6. Asymptotic Density (M)
   Finite seed invariance
   Macro dynamics - von Koch schemes
7. References

Also - Pictures!!!

Wolfram's papers

N.H. Packard and S. Wolfram: Journal of Statistical Physics, 38 (March 1985) 901-946

S. Wolfram: Scientific American, 251 (September 1984) 188-203

A New Kind of Science (online version)

Let's continue to use my file space

http://psoup.math.wisc.edu/CURL/

as one place for documents. My papers with Janko are called PackardSnowflakes and Snowfakes there. I've also put a preprint version of the first Packard paper there under the name PackardOriginal. Most of the other resources I asked you to gather should be available on the web.

Background Research

We need to find and read the following articles:

Packards original paper in World Scientific, "Theory and Application of CA" 1986 pp. 305-310
Article by Wolfram in Scientific American vol 251, 1984
Paper by Packard and Wolfram jointly in Journal of Statistical Physics vol 38 #5,6 1985
A New Kind of Science by Wolfram
Advances in Applied Math vol 21 pp. 241-304 article by Griffeath 1998

We also need to think about proving that any finite seed has the same density as a singleton (for the Diamond Rules)