# Everything2

# Graham’s Number

**cooled by**GrouchyOldMan

(thing) | by Seqram |
Sun Sep 17 2000 at 18:06:25 |

A really small number, smaller than almost all natural numbers.

It’s still, however, big enough to blow the average mind and all others within three feet of it.

It’s an upper bound in Ramsey theory, used in a proof by R. L. Graham. To represent it we need ^ notation, but I think my book uses it a bit differently from thenode I just linked to it. Actually, if you ask me, ^ notation is still woefully inadequate for the job, so I’ll be augmenting it myself.

OK, so ^-notation as I use it here:

3^3 is what it usually means in computer science: 3^{3}=27.

3^^3, though, is 3^(3^3)=3^{33}=3^{27}. Already a biggish number: 7,625,597,484,987.

3^^^3 is 3^^(3^^3) which is 3^^7,625,597,484,987 which is 3^(7,625,597,484,987^7,625,597,484,987). And that’s already more than most people want to think about.

3^^^^3=3^^^(3^^^3), and so on. From here on, I’ll use my own augmentation to the notation: 3^_{4}3 will mean 3^^^^3. The subscript indicates how many ^s there are.

**Now.** Start with G_{1}=3^_{3^^^^3}3. I’ll wait for your brain to stop sizzling. That’s 3^^^^3 ^’s between the 3’s. And you know what *that* can do to a number.

From there, consider G_{2}=3^_{G1}3. Yes, that’s G_{1} ^s. Owwwww.

Continue on in this fashion, with each number specifying the number of ^s in the next one, until you get to G_{63}. It’s no longer meaningful to say it’s incredibly big, it’s just too incredibly big. **That** is Graham’s number: G_{63}.

Obviously, you can invent numbers as big as you like. The point is that this one is the biggest (so far) used for something actually meaningful (if you consider Ramsey theory meaningful). It’s actually been used in a proof, it’s an upper bound, etc. Mind, it’s only a *bound*, and not necessarily the tightest one out there. In fact, many mathematicians suspect that the actual answer that Graham’s number bounds is just 6.

I like it! | 2 C!s |

(essay) | by sam512 |
Wed Nov 13 2002 at 16:31:20 |

#### What exactly is the function of Graham’s Number? What was R. L. Graham proving?

Well, it’s used in a very difficult and relatively new region of combinatorial mathematics known as Ramsey Theory. There’s a mathematical problem in Ramsey Theory, a fairly difficult one to explain and an extremely difficult one to solve. But here’s the explanation anyway.

Before you can understand the question, you need to understand a bit of Ramsey Theory. Firstly, let’s find out what a complete graph is. A complete graph order N (which is written K_{N}) consists of N points, all of them joined to all the others. For example, K_{1} is just one lone point all on its own. K_{2} is two points, joined by aline. K_{3} is three points joined to make a triangle. K_{4} is a four points joined to make a square, with a cross in the middle to join the diagonally opposite points. K_{5}is a pentagon with a five-pointed star inscribed in it. you know what I’m talking about. A pentagram.

Now, imagine taking two pens, say, red or blue, and randomly colouring all the lines. Sure, you get a pretty pattern, but if you look at the pattern, there might be smaller patterns. For instance, you might find three points which are all joined by red lines to make a red triangle. That’s a red K_{3}! Now, you understand that if you colour the lines randomly, you might not get a triangle. That’s true. However, if you make the complete graph big enough, and then colour all the lines, then even if you colour them randomly, you are **guaranteed** to get either a red or a blue triangle. All you need is a big enough graph.

Now, there are variations on this question. Suppose, for instance, that you use three colours instead of two. Or suppose you wanted to find not a triangle, but a square? Or a snake of eight lines?

As long as the complete graph is big enough, you will find that you get all of these things, no matter how randomly you colour them. But finding out “how big is big enough” is very difficult mathematically speaking as the numbers get insanely huge. As big as Graham’s Number, in fact.

So here’s the ultra-tough question that Graham was trying to solve.

“Two-colour the diagonals of an N-dimensional hypercube. What is the smallest N such that there must exist a K_{4} of one colour *whose vertices are coplanar*?”

Don’t waste time trying to crack it yourself… you’ll fail. Honest. The answer to this question is yet to be found, but the man studying it, R. L. Graham, did the next best thing and came up with an upper limit. That upper limit is Graham’s Number.

According to the most recent set of studies, the solution for N is probably **6**.

Now there’s a nice number that the human mind can comprehend without melting. That’s nearly all from me, folks, I just want to round it off by saying that I hope that, when you go home and see your miserable little millions, billions, and googolplexes, you laugh, think of Graham’s Number, and realise that infinity ismuch, much bigger than most people imagine. Thank you, and goodnight.

A correction to Seqram‘s writings.

(Brackets are a total pain at this point, so please know that stuff like 3^4^5^2 should be taken to mean 3^(4^(5^2)) and NOT ((3^4)^5)^2. Just warning you.)

3^^1 = 3

3^^2 = 3^3

3^^3 = 3^3^3

3^^4 = 3^3^3^3 etc.

Therefore

3^^^3 = 3^^3^^3 = 3^^7,625,597,484,987 which is NOT 3^(7,625,597,484,987^7,625,597,484,987), but actually,

= 3^3^3^3^…^3^3

where there are 7,625,597,484,987 threes in the sequence. This sequence is called a power tower, and is pronounced “A power tower of seven trillion, six hundred and twenty-five billion, five hundred and ninety-seven million, four hundred and eighty-four thousand, nine hundred and eighty-seven threes”. If you wrote it out, you’d have a 3, then another three just above it and to the right, then another one… until you had 7,625,597,484,987 threes in the tower. That, alone, would take even amachine a couple of years to do.

3^^^3 is already a monumentally big number. This number has no real-world equivalent at all. We left them all behind a long time ago. It’s impossible for a humanmind to conceive of this number, though its construction (you know, the power tower) is just conceivable. Plus it can be (technically) be written out in a proper mathematical form. Where was I?

3^^^^3

Now this is a seriously big number, very, very much larger than 3^^^3 or indeed any other number you probably know about. If it wasn’t a single step in the construction of Graham’s Number then I wouldn’t be surprised to find it was the largest number in the world.

3^^^^3

= 3^^^3^^^3

= 3^^^(a power tower of 7,625,597,484,987 threes)

= 3^^3^^…^^3^^3^^3^^3 where there are 7,625,597,484,987 threes in the list.

= 3^^3^^…^^3^^3^^7,625,597,484,987

= 3^^3^^…^^3^^(a power tower of 7,625,597,484,987 threes)

… If you keep expanding it you get

A power tower of (a power tower of (a power tower of… (a power tower of 7,625,597,484,987 threes) … threes) threes) threes

where there are 7,625,597,484,987 power towers. See arrow notation.

The remainder of the construction is as Seqram said.

Thanks to krimson for setting me straight on some of this.

I like it! | 6 C!s |

(idea) | by jbrandon |
Sat Jan 04 2003 at 2:55:01 |

The answer to the question that sam512 poses: “How many people must there be in a room, such that necessarily a group of four of them are either mutual friends or mutual strangers?” is 18, and well known.

It can be asked as “What is the smallest possible value of n such that any for any graph G with n or more nodes, G or its complement contains K_{4}” Answering this question is a matter of tedium.

For non-math types, the complement of a graph is the same graph with all the edges removed, and edges put in where there were none before. Thecomplement of K_{n} is a disconnected set of n nodes

“What is the smallest possible value of N, such that K_{2^N} will force K_{4} to appear when randomly two-coloured?” *is* the question that inspired Graham to descibe his famous number, but it is not the same as the question above. The “common man” equivalent can be read below. I find it harder to understand than thegraph theory question.

“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 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.”

I like it! |

(person) | by AndreM |
Sat Jan 30 2010 at 2:34:15 |

Graham’s Number is a humongous beast, It is larger than we can express in exponential notation. It is larger than we can visualize. It is insanely larger than the largest number that any advanced technology that we can visualize, can visualize.

You don’t believe me? Consider this :

A trillion is a very large number, but we can put it into context and visualize it (“a little less than the GDP of Australia in US dollars”). If you divide a trillion by 1000, you can immediately visualize the change – a mere billion (“what Bill Gates earned last year”).

Graham’s Number (GN) is so large, that there is no known method for differentiating GN and GN/1000. Or GN/(Googolplex), for that matter. That’s right, a number so large that you can multiply or divide it by pretty much any number you can write in exponential notation, and the best mathematician in the world “observing” both numbers would not be able to say whether the new number was any different from GN.

I use the word “observing” in a theoretical sense, of course, as there is no known method of quantifying GN.

I like it! | 1 C! |

## Deixe um comentário