There’s an old math paradox that says that all natural numbers are interesting, since otherwise there would have to be a smallest uninteresting number, and that in itself is pretty interesting. Of course, this is meant to show that ideas in the English language do not always translate to well-defined mathematical concepts, but let’s ignore our better mathematical sense and tinker with the idea of how interesting different numbers are a little bit. In particular, I claim that 11630 is utterly bland and uninteresting.

Why 11630?

Before saying why 11630 is uninteresting, I should probably say what I consider “interesting” to even mean. Interesting, to me, means that it has some (semi-unique) mathematical property that sets it apart from other numbers. 11 is interesting because it is prime, 16 is interesting because it is a perfect power (16 = 4²), and so on. Clearly, there is some ambiguity in this definition, since one could consider composite numbers interesting, just as I considered prime numbers interesting. Additionally, do we consider 2719 interesting simply because it is prime? I’d say no, since there are hundreds of prime numbers that come before it — perhaps only the first few numbers that satisfy a given property should be considered interesting as a result of it?

Using these ideas, it seems like determining how interesting a number is would be a task perfectly suited to the Online Encyclopedia of Integer sequences (OEIS). If you’re unfamiliar with it (i.e., if you’re not a math person and have no place reading my blog), the OEIS is a database containing thousands of (you guessed it) integer sequences that have been submitted by users over the last decade or so (such as the sequence of prime numbers 2, 3, 5, 7, 11,… and the sequence of perfect powers 1, 4, 8, 9, 16,…). Presumably, if an integer is interesting then it will appear in at least one or two of the 159437 sequences contained in the database, right? Indeed, it seems that we can get a rough idea of how interesting a number is by looking at how many sequences that number appears in in the database compared to other numbers of similar size.

11630 is the first number that is not listed in a single sequence in the OEIS. It is not prime, nor is it highly composite (11630 = 2×5×1163). It doesn’t have any particularly notable residue properties, and it doesn’t come up in counting problems. It’s boring in every way, and it seems as though not a single mathematician has found a use for it in the last dozen or so years (let me know if you’ve discovered otherwise).

What Numbers are Interesting?

First off, I’m not going to deal with particularly small numbers (say in the range of 1 – 50) since, as the strong law of small numbers quips, these numbers will appear all over the place just because they’re small. You could probably argue that most (if not all) of them are interesting, so I’ll instead take a look at a couple larger numbers that are particularly interesting.

The number 421 appears in some 1894 sequences, while most numbers that size appear in about 940 sequences. This seems to indicate that 421 is a particularly interesting number, but why? What’s so special about 421? Well, it’s prime (in fact, it’s a twin prime, Pythagorean prime, cuban prime, lucky number of Euler prime, additive prime, and irregular prime), it’s congruent to 1 mod 2,3,4, 5, 6,7, 10, 12, it’s the sum of five primes, and 421² = 420² + 29². Similarly, 512 appears in 2116 sequences even though most numbers around 512 appear in about 800 sequences. This is perhaps less surprising than 421, since 512 = 2⁹ = 8³ = 16² + 16² is a number that somehow seems “nice” due to it being a perfect power. Additionally, 512 is a Leyland number, Harshad number, and it comes up in all sorts of counting problems.

What of the Paradox?

Recalling the paradox from earlier, we are now forced to ask ourselves whether or not 11630 is now interesting as a result of it being the first number not included in the OEIS. Rather than come up with an answer, I’m going to take the easy way out and let the OEIS decide. The sequence of uninteresting numbers is 11630, 12067, 12407, 12887, 13258, 13794, 13882, 13982, 14018, 14163,… Let’s submit that to the OEIS and see if they consider it to be interesting or not.

Update [June 13, 2009]: I got word back via e-mail today that this sequence didn’t make the cut. So there you have it — these numbers truly are uninteresting.

Update [November 12, 2009]: It looks like 11630 is now listed in the OEIS. Additionally, 12067 was recently added, meaning that 12407 is now the first uninteresting number.

Update [October 7, 2011]: Interested readers might want to check out this paper, which explores similar questions and mentions the numbers computed here.

Update [November 14, 2011]: The British television show QI recently aired a segment on exactly this topic. See the video here.

Update [November 22, 2013]: A whole bunch of these numbers have been added to the OEIS lately, making 14228 the new first uninteresting number.

Downloads:

• OEIS counts (1 – 50000) [Excel spreadsheet — 6.81MB]
• OEIS counts (1 – 50000) [.txt — 444kB]

I’ve decided that, starting today, I will once a month post a mathematical result that I find interesting and/or useful, but I feel sadly gets less attention than it deserves (Update: well, that lasted about four months). I will try to present all relevant preliminaries along with the result to provide context, so hopefully the results and proofs will be accessible to someone at the upper undergraduate level.

Since I’m a quantum kinda guy, it seems natural that the first such lemma deals with quantum information science. In particular, it helps quantify the behaviour of unital quantum channels acting on density operators. Before delving into the result, let’s begin with…

Quantum Preliminaries

Given the complex matrix space M_n, a quantum channel E is defined to be a completely positive, trace-preserving map. That is, it is a map of the form

where {A_j} ∈ M_n is a family of matrices. Trace-preservation of E is equivalent to the requirement that

In many physical situations we are interested in unital quantum channels; that is, channels that satisfy E(I) = I. Such channels in general exhibit much nicer behaviour than arbitrary quantum channels, and this month’s lemma will show one particular instance of this fact.

The Hardy-Littlewood-Polya Theorem

The proof of the lemma relies on a classical result known as the Hardy-Littlewood-Polya Theorem. The result explains how doubly stochastic matrices act on vectors. Since it seems to be surprisingly difficult to find on Wikipedia and other popular (read: non-research) websites, I will state it here.

Theorem [Hardy-Littlewood-Polya]. Let x,y ∈ Rⁿ be real vectors. Then x majorizes y if and only if y = Dx for some doubly stochastic matrix D ∈ M_n.

It might be worth mentioning that the “if” direction of the proof is borderline trivial; the real meat and potatoes of the theorem is the “only if” direction.

The Lemma Itself

The lemma makes precise something that feels quite natural when thought of physically: a unital channel (that is, a completely positive, trace-preserving map E for which E(I) = I) can only increase the impurity (or “mixedness”) of quantum states. It has several simple consequences that are of great use when dealing with unital channels, and furthermore its proof makes excellent use of classical machinery. It was originally due to Uhlmann [1,2], but has recently appeared in [3]. The proof provided in the PDF attached at the end of this post is from the latter source.

Lemma [Unital Channel Eigenvalue Majorization]. Suppose ρ = E(σ) for a unital channel E. Then the ordered spectrum r of ρ is majorised by the ordered spectrum s of σ.

One particularly useful corollary of this lemma is presented here, and its proof is omitted (and dare I say left as an exercise for the reader?)

Corollary. If E is a unital quantum channel and ρ is a positive operator, then rank(E(ρ)) ≥ rank(ρ).

Related Links

• Lemma of the Month #1: Unital Channel Eigenvalue Majorization [pdf]

References

1. A. Uhlmann, Commun. Math. Phys. 54, 21 (1977).
2. I. Bengtsson, and K. Zyczkowski, Geometry of quantum states, Cambridge University Press (2006).
3. D. W. Kribs, R. W. Spekkens, Phys. Rev. A 74, 042329 (2006). arXiv:quant-ph/0608045v2

Over the last few days, the internet news has been filled with stories of an Iraq-born 16-year-old boy who “cracked the mystery of the Bernoulli numbers”. This has of course been promptly been picked up by dozens of blogs and regurgitated all over the place. However, if you’re mathematically-inclined like me, this might lead you to wonder “there was a mystery of the Bernoulli numbers?” Well, wonder no more, because no there was not. The formula for B_n, the n^th Bernoulli number, that was “discovered” by the boy is as follows:

This formula was originally derived by a mathematician named Julius Worpitzky in 1883. Some sources have tried half-heartedly to correct the article by appending a sentence to the bottom of the story:

Later, a clarification was given‚ by the mathematical community that the probable solution to this century old problem was available in mathematical circuits though not openly available to all.

– thaindian.com

The problem is that this isn’t even true; the “probable solution” (what does that mean, exactly?) was not under some mysterious mathematical lock-and-key. It was well-known and even included on the Wikipedia page describing the Bernoulli numbers (at the time of this writing, it is about halfway down the page under the section titled “Connection with the Worpitzky number”). Uppsala University has even issued an official statement saying that the news articles are false.

So while the boy’s derivation of the formula is indeed impressive considering his age (if he did indeed derive it himself rather than following the steps outlined on the wiki page), the story about this “puzzle” being solved is almost entirely false.

Update [June 6, 2009]: The Mathematical Association of America has now posted an article about this same topic.

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.