Up’s balloon house

Let me say right off the bat that I am in no way insulting or belittling the new Pixar film Up, which was released in theatres this weekend; it was one of Pixar’s better outings, and that’s saying something. However, after reading a ridiculous article on PopularMechanics.com that actually defends the physical plausibility of Up, I couldn’t help but write a thing or two about the (im)plausibility of the movie myself.

The absurdness of the article appears as early as its fourth sentence:

Given the fact that one cubic foot of Helium can lift 60 pounds, with even small, 1 x 1-foot balloons, Carl’s rig has the capacity to lift about 618 tons—enough to lift about 150 Hummers.

– PopularMechanics.com

Let’s think for a second about the numbers in that sentence, shall we? One cubic foot of helium can lift 60 pounds. Really, PopularMechanics? When was the last time that you were at a fair and saw a full-grown man get carried away by four helium balloons? How about instead of putting window washers and construction workers on scaffolding, we just tie a handful of balloons to their waist? Seems like a more economical solution to me.

Indeed, since PopularMechanics.com can’t seem to be bothered, let’s do some actual math to figure out how plausible the situation in Up really is. Helium’s density is about 5.06 grams per cubic foot and the density of air is roughly 36.11 grams per cubic foot. Thus, one cubic foot of helium can lift roughly 31.05 grams (this number will vary slightly depending on what figure you use for air density and whether or not you include the weight of the balloon itself, but I think that we can all agree that it is slightly less than 60 pounds).

Assuming that the average balloon indeed holds a cubic foot of helium (this seems like a reasonable assumption to me), we then find that it would take some 2630 balloons just to lift a 180-pound old man. To pick up his house (assuming a weight of 50 tons, which seems reasonable to me) as well would then require some 1.46 million balloons—a far cry from the reported 20622 balloons that were actually used. But hey, 20622 balloons would be enough to lift about 1400 pounds, or just under 3/4 of a ton. That’s pretty close to what you said, right PopularMechanics?

Update [June 1, 2009]: PopularMechanics has now corrected their article by replacing the offending text with “Given the fact that Helium can lift over six times its weight, Carl’s idea isn’t entirely fiction.”

One interesting Life-like cellular automaton, known as “2×2“, is particularly abundant with frequently-occurring oscillators and has thus attracted some attention from Life enthusiasts over the years. The 2×2 automaton takes place on a grid much like Conway’s Game of Life, but cells are born if they have exactly 3 or 6 neighbours, and they survive if they have exactly 1, 2, or 5 neighbours (this behaviour is summarized by the rulestring “B36/S125”).

Some small period 2 oscillators in B36/S125

Take a look at the second oscillator from the left in the top row of the above image — it is a 2 × 4 rectangle that oscillates back and forth. The oscillators that I will be looking at in this post are rectangles like this; rectangles of sizes 2m × 2n such that m + n is odd (the reason for these restrictions on the sizes of the rectangles is simply that they aren’t oscillators otherwise (not quite, see the correction in the comments)). The next two smallest of these rectangular oscillators are shown here:

Rectangular oscillators in B36/S125

As you can see, the oscillators behave a bit more unpredictably as their size increases. The question that I will answer now is “What is the period of a 2m × 2n rectangular oscillator in the 2×2 rule in terms of m and n?”

I will present the final answer right now, since it isn’t particularly simple: the period is 2^k+1 – 2, where k is the least natural number such that 2^k = ± 1 mod (m + n). While this answer isn’t exactly pretty, the k values have at least already been computed up to m + n = 2001 (see Sloane’s A003558), and there is at least some theory developed about them (see Suborder Function at Mathworld).

It is perhaps worth noting that B36/S125 isn’t the only rule in which these oscillators work; it’s simply the most well-known. These rectangular oscillators behave the same in any rule from B3/S5 to B3678/S012567.

Deriving the Answer

Disclaimer: The following contains much handwaving. It can be made rigorous, but I don’t particularly want to; the argument is long enough as it is, and this is recreational mathematics, after all.

Before proceeding, let’s make a simplification by noticing that a 2m × 2n rectangle is simply another phase of a 2 × 2(m + n – 1) rectangular oscillator. It is thus enough to consider 2 × 4n rectangular oscillators, where n is an integer.

The thing to notice about these oscillators is that, as described by Dean Hickerson in this thread, each phase of these block oscillators can be described as an XOR of rectangles. For example, consider the following phase of one of the above oscillators:

2 × 12 XOR 6 × 8

The above phase can be considered the XOR of a 2 × 12 rectangle and a 6 × 8 rectangle. Different phases may require a different number of rectangles to be XORed, but every phase can always be represented in this way. More important, however, is the fact that the evolution of the oscillators occurs in a very predictable way when modeled like this. Consider the following grid. (Aside: you will likely recognize that it resembles very closely one half of the Sierpinski triangle. This is no coincidence; it turns out that these oscillators are, in a sense, emulating the “Rule 90” 1D cellular automaton.)

XOR grid

The way to read the above grid is that that row represents the current generation and the column represents the size of the rectangle that is being XORed (the first column represents a 2 × 4n rectangle, the second column represents a 4 × (4n – 2) rectangle, the third column represents a 6 × (4n – 4) rectangle, and so on). Thus, you “start” in the top-left cell, and that represents the 2 × 4n rectangle that you start with (in generation 0). To go to generation 1, go to the next row, where we see that the only filled in cell is in the second column, which is the 4 × (4n – 2) column. Thus, the first generation will just be a filled-in 4 × (4n – 2) rectangle. To see what generation 2 will look like, go to the next row, where we see that two cells are filled in, corresponding to 2 × 4n and 6 × (4n – 4) rectangles. Thus, XOR together two rectangles of those sizes (in the sense described earlier) to get what generation 2 must look like.

The key to determining the oscillators’ periods comes from realizing that if we continue to label the columns in the way I described, eventually we hit zero-length rectangles, which doesn’t make a whole lot of sense. Thus, we simply do not XOR any of those rectangles that are of length zero. But what about rectangles of negative length? Instead of counting down into negative numbers, start counting back up. This is probably easiest to illustrate with an example, so I’ll use the n = 3 case.

Coloured XOR grid (n = 3)

Red columns represent 2 × 12, orange represent 4 × 10, yellow represent 6 × 8, green represent 8 × 6, blue represent 10 × 4, purple represent 12 × 2, and grey represent zero-width rectangles that can be ignored. Thus, we see that (for example), in generation 9 (row 10), there is a puple and a green and so the oscillator will look like a 12 × 2 rectangle XORed with an 8 × 6 rectangle.

The period can be determined by grids of this type by going down the rows, looking for the first row (after row 1) that has an odd number of red cells filled in (so that after XORing, a 2 × 4n rectangle will be present) and an even number of each other colour besides grey (so that after XORing, no rectangles of other sizes will be present). It can be shown that the first time this occurs must be at the bottom of one the triangles that reaches all the way to the left (so in row 3, 7, 15, 31, and so on). This corresponds to the oscillators always having period that is equal to 2^k – 2, where k is some integer. To determine what that integer is, notice that if one of these oscillators starts off as a 2 × 4n rectangle, then it will appear rotated 90 degrees as a 4n × 2 rectangle halfway through its period. Thus, we need the least k such that row 2^k-1 contains a single purple cell (i.e., 2^k-1 = ± 1 mod (2n + 1)).

By transforming back to 2m × 2n rectangles and shifting around k a little bit, we see that the period is 2^k+1 – 2, where k is the least integer such that 2^k = ± 1 mod (m + n).

Thus, using Sloane’s A003558 as our guide, we see that the period of a 2m × 2n rectangle for m + n = 3, 5, 7, 9, … is 2, 6, 14, 14, 62, 126, 30, 30, 1022, …

Update [May 28, 2009]: This sequence is now listed in the OEIS as Sloane’s A160657.

Update [January 14, 2019]: A few people (at least Dave Greene as well as wwei and Blinkerspawn in the comments below) noticed that this argument is incorrect — I have just demonstrated an upper bound on the period of these oscillators, and the true period may be a factor of that upper bound (this first happens for the 2-by-72 oscillator, which has period equal to 1/3 of the value claimed in this post). Sequence A160657 has now been updated with the correct values.

No. No it does not.

Update [June 14, 2011]: Entering “Conway’s Game of Life” into Wolfram Alpha now does provide you with information about the game. I suppose that means that it officially lives up to the hype.

I spent the beginning of this week at the 4th Workshop on Theory of Quantum Computation, Communication and Cryptography, and I decided that I might as well post some information and thoughts about it since it was probably the best quantum workshop that I’ve attended thus far (not least because it was only three days long and the Institute for Quantum Computing knows how to do food right). There were some fifteen or so talks, and here I’ll describe two of my personal favourites.

Quantum algorithm for online memory checking

Wim van Dam and Qingqing Yuan

In his talk on online memory checking, Wim van Dam described the problem of trying to retrieve data from an unreliable and public server. Because the server is public, an adversary could tamper with its data, rendering the information that you retrieve useless. The online memory checking question of interest is then how to make sure that the requested information has not been tampered with.

One obvious (albeit largely useless) approach to making sure that the public server has not been tampered with is to simply keep a copy of its entire contents on a private server as well. When data is requested from the public server, check to see if it matched the data on the private server, and you’re good to go. This carries the obvious problem that you have to keep two copies of all of the data.

The obvious improvement to this is to use some sort of hashing function on the contents of the public server, store the results on a private server, and then check to see if the hash of your retrieved data equals the hash of the stored data whenever you access the public server. The question of how large the hash (or whatever encoding of the information you use) must be was answered in 1994 by Blum et al. and in 2005 by Naor and Rothblum: s × t ∈ Ω(n), where n is the size of the data on the public server, s is the size of the data stored on the private server, and t is the number of queries made to the public server.

Wim van Dam and Qingqing Yuan show that if the memory checker is allowed to act in a quantum mechanical manner, then the complexity of the problem is reduced to s × t ∈ Ω(polylog(n)). Score 1 for quantum algorithms.

A necessary condition for approximate quantum error correction

Cedric Bény

It’s not particularly surprising that this talk spoke to me pretty directly, as it deals with the same approach to the same subarea of the same field of research that I do. That and my name was mentioned in the talk. Score 10 for Cedric Bény.

The main result of the talk was a generalization of the Knill-Laflamme conditions to the realm of approximate quantum error correction (as opposed to perfect quantum error correction).  The idea was that the Knill-Laflamme conditions can be restated in terms of the complementary channel in a very natural way: a given subspace is correctable for a channel if and only if the complementary channel sends everything supported on that subspace to a single fixed operator (another way of saying this is that the subspace is private for the complementary channel, a connection that was explored by Kretschmann, Kribs and Spekkens in 2007).

It turns out that there is a natural way to generalize this formulation of the Knill-Laflamme conditions. The idea is that if the complementary channel, when restricted to a given subspace, is within a small distance of a channel that maps everything to a fixed operator (where distance is measured via the diamond norm), then that subspace is approximately correctable (and he of course quantifies the “small distance” and “approximately”).

He also provides a generalization of these results to approximate error correction of subsystem codes, which is a nice bonus.  Finally, it’s interesting to note that the set of operators that are approximately correctable by a given recovery operation does not necessarily form an algebra, in contrast to the perfect error correction situation.

Given a k × n grid, a self-avoiding walk (SAW) on that grid is a connected path that never touches the same square more than once and never doubles back on itself (note that some sources make the convention that the path is drawn on the edges of the grid from vertex to vertex, but here I will make the convention that the path connects the centres of the squares that the grid forms). I will define a maximal self-avoiding walk to be a self-avoiding walk that touches every square of the grid on which it resides. One natural question that we can ask in this setting is “How many maximal self-avoiding walks are there on a k × n grid?”

Before proceeding, let’s simplify things slightly by making the restriction that the maximal self-avoiding walks must start in the bottom-left corner of the grid (this restriction leaves us with the walks that are known as “Greek-key tours”). Let f(k, n) denote the number of maximal self-avoiding walks on a k × n grid. Unfortunately, finding an expression for f(k, n) in complete generality seems to be out of reach, so we will instead try to answer the question for certain fixed values of k.

Case 1: k = 1
Regardless of n, there is clearly only one maximal self-avoiding walk in this case: a straight line. Thus, f(1, n) = 1 regardless of the value of n.

Case 2: k = 2
It is not difficult to prove (by induction, for example) that f(2, n) = n.

Case 3: k = 3
This is the first case whose solution does not seem trivial. It is well-known (by people who have looked at this problem, anyways) that the number of maximal self-avoiding walks on a 3 × n grid for n = 1, 2, … is 1, 3, 8, 17, 38, … (Sloane’s A046994). This sequence is defined by the following recurrence relations:

Well, from these recurrence relations we can derive the following closed form expression for f(3, n):

It may be worth noting that this formula can be simplified significantly if you consider the case when n is odd separately from the case when n is even, and write f(3, n) as a branch function.

Case 4: k = 4
The number of maximal self-avoiding walks on a 4 × n grid for n = 1, 2, … is 1, 4, 17, 52, 160, … (Sloane’s A046995), but to date no simple closed-form formula for f(4, n) has been found. In 2003, Dean Hickerson proposed the following recurrence relation to define f(4, n), which holds at least for the first 25 terms of the sequence:

While it is possible to derive a closed-form formula for f(4, n) from the above recurrence relation using standard difference equation techniques, the formula is extremely long and cumbersome. One piece of information that we can extract from the closed-form formula (which I won’t write out here) is that f(4, n) ∈ O(2.539ⁿ).

Case 5: k ≥ 5
It is now clear that this problem grows very large very quickly, and proceeding in this manner may not be (realistically) feasible. Not much is known about f(k, n) when both k and n are greater than or equal to 5. The best approach in this case is likely that of brute force.

Computing the Number of Maximal SAWs

Here I provide two programs for computing the number of maximal SAWs on a grid of your chosen size. It is recommended that you use the C script rather than the Visual Basic program, as the C script is much faster.

If the Visual Basic file below gives you an error message when you try to run it, you may need to download and install the Visual Basic 6.0 run time files. Click here to download these files. As far as I know, this program should work on Windows 98, ME, 2000, XP and Vista, but I can’t make any guarantees about its compatability.

Download:

• Maximal SAW Calculator in Visual Basic [Windows exe — 28.0kB]
• Maximal SAW Calculator in C [Windows exe — 17.6kB]
• Maximal SAW Calculator in C source code [zip — 1.06kB]

Maximal SAW Table of Values

This is a table giving the number of maximal SAWs on a k × n grid. Several of the values in the table below were calculated using the above software — the cells that have “?” in them correspond to values that are currently unknown due to computational limits. Note that there is trivially symmetry across the main diagonal of the table. I apologize for the unreadably small font.

Update (August 7, 2024): Jay Pantone, Alexander R. Klotz, and Everett Sullivan have written a great paper that (among other things) significantly expands these results.

Related Links:

• ‘Greek-key’ tours on 3 × n chessboards — A mathforum.org posting by Thomas Womack in April 1999 about maximal SAWs.