Lessons from teaching gifted elementary school students (Part 5d)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

A bright young student of mine noticed that multiplication is repeated addition:

x \cdot y = x + x + x \dots + x,

Also, exponentiation is repeated addition:

x \uparrow y = x^y = x \cdot x \cdot x \dots \cdot x,

The notation x \uparrow y is unorthodox, but it leads to the natural extensions

x \upuparrows y = x \uparrow x \uparrow x \dots \uparrow x,

x \uparrow^3 y = x \upuparrows x \upuparrows x \dots \upuparrows x,

and so. I’ll refer the interested reader to Wikipedia and Mathworld (and references therein) for more information about Knuth’s up-arrow notation. As we saw in yesterday’s post, these numbers get very, very large… and very, very quickly.

When I was in elementary school myself, I remember reading in the 1980 Guiness Book of World Records about Graham’s number, which was reported to be the largest number ever used in a serious mathematical proof. Obviously, it’s not the largest number — there is no such thing — but the largest number that actually had some known usefulness. And this number is only expressible using Knuth’s up-arrow notation. (Again, see Wikipedia and Mathworld for details.)

From Mathworld, here’s a description of the problem that Graham’s number solves:

Stated colloquially, [consider] every possible committee from some number of people n and enumerating every pair of committees. Now assign each pair of committees to one of two groups, and find N, the smallest n that will guarantee that there are four committees in which all pairs fall in the same group and all the people belong to an even number of committees.

In 1971, Graham and Fairchild proved that there is a solution N, and that N \le F(F(F(F(F(F(F(12))))))), where

F(n) = 2 \uparrow^n 3.

For context, 2 \uparrow^4 3 is absolutely enormous. In yesterday’s post, I showed that 2 \uparrow^3 = 65,536. Therefore,

2 \uparrow^4 3 = 2 \uparrow^3 (2 \uparrow^3 2)

= 2 \uparrow^3 65,536

= 2 \upuparrows 2 \upuparrows 2 \upuparrows \dots \upuparrows 2,

repeated 65,536 times.

That’s just 2 \uparrow^4 3. Now try to imagine F(12) = 2 \uparrow^{12} 3. That’s a lot of arrows.

Now try to imagine F(F(12)) = 2 \uparrow^{F(12)} 3, which is even more arrows.

Now try to imagine F(F(F(F(F(F(F(12))))))). I bet you can’t. (I sure can’t.)

Graham and Fairchild also helpfully showed that N \ge 6. So somewhere between 6 and Graham’s number lies the true value of N.

A postscript: according to Wikipedia, things have improved somewhat since 1971. The best currently known bounds for N are

13 \le N \le 2 \uparrow^3 6.

Leave a comment

1 Comment

  1. Lessons from teaching gifted elementary school students: Index (updated) | Mean Green Math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: