Talk:Graham's number

?

I don't understand. If the number is larger then the number of elementary particles in the universe, then why could it possibly matter. How/why was it used in proofs? If it's too large to even think about what's the point. What is the largest number that does "matter"? I define numbers that matter as numbers that can be used. (i.e. I have n dollars or There are n of those in the world.)--Ledlaxman24 01:45, 21 April 2006 (UTC)

If you have 70 people standing in line to get into a movie or a concert that isn't too many. Yet there are over a googol (10¹⁰⁰) ways in which those mere 70 people could end up being arranged in line. This is more than the number of particles in the visible universe, yet the situation I've described is easy to imagine. Or think about how many possible 40-move chess games there are. If you do some calculations (see Shannon number) you get around 10¹²⁰. A computer can't calculate all those possibilites because, again, there isn't enough space in the entire space to store all those possibilities. Does that mean they don't exist? To me it means we have certain scenarios in which we have humongous numbers and we find it useful to develop some techniques to deal with them. Kaimiddleton 07:36, 22 April 2006 (UTC)

Thsnks, now it makes sense. Could you add that in somewhere on the page (preferably at the top). I'm in tenth grade geometry, and didn't understad any of the hypercube stuff. I think it would benefit everyone (especially non-mathmaticians) if you explained it like that.--Ledlaxman24 12:35, 22 April 2006 (UTC)

Ok, I've reworked the article some to put it into perspective. You might want to check out the article on large numbers for more discussion. Kaimiddleton 04:02, 23 April 2006 (UTC)

Digits

I rather like the listing of the last ten digits; it makes the number seem more concrete somehow. Are there any similar tricks we could do to get the first 10 digits? Yours hopefully, Agentsoo 09:34, 29 July 2005 (UTC)

Not by any method I know of, but then again, I don't know much. A method to calculate the first ten digits may exist, but if it did, it would certainly be a lot more complicated. Calculating the last digits of the number is quite simple (as the article says, elementary number theory) using modular arithmetic. The powers of the number can go higher and higher but the final digits will cycle, so it is possible to work out. Calculating the first digits would be much more difficult, if possible at all. -- Daverocks 10:12, 8 August 2005 (UTC)

Number of digits

How many digits does this large number have?? 66.32.246.115

This large number has a large number of digits. ;) Okay, take the common logarithm of Graham's number, round it down to the nearest whole number, and then add 1. That's the number of digits. I'd write it out in full for you, but there aren't enough particles in the known universe... :) -- Oliver P. 00:26, 9 Mar 2004 (UTC)

So how about the number of digits of THAT number (namely, the number you are saying you'd write down)??

How many times would you have to take the logarithm of the number acquired in the previous step (starting with Graham's number) before you get a number that can be written using the particles in the known universe? :) Fredrik 00:37, 9 Mar 2004 (UTC)

Even the number of times you take the logarithm, to get a writeable numbers, is too large to write. That is, you don't just take a logarithm once, or twice, or even a million times; if you took the logarithm $2^{10^{80}}$ times (about as many as you could write with all the particles in the universe) you still wouldn't be even in the ball park of being able to write out the result - even if you had any particles left over to do it 8^) In fact, even the number of times you had to take the logarithm, is so large that the number of times you had to take it's logarithm, is too large to write - and so on, and so on, 65 layers deep... Securiger 16:49, 3 May 2004 (UTC)

I don't see any way to visualise the magnitude of the number.... my only conclusion is 'whoa this is large'. Can't we find some kind of magnitude comparison to help out to fathom G? — Sverdrup 00:42, 9 Mar 2004 (UTC)

Well, if you'll allow me to define numbers in O notation, then Graham's number is O(A⁶⁴). This grows faster than exponentiation, iterated exponentiation, iterated iteration of exponentiation, etc. So Graham's number simply cannot be written this way, or any related way. Conway's chained arrow notation, however, is sufficient to write Graham's number. --67.172.99.160 02:35, 19 March 2006 (UTC)

An amusing exercise for the student

Obviously Graham's number is divisable by three, and hence not prime. And since all powers of three are odd, obviously Graham's number minus one is even, and hence not prime. Question: is Graham's number minus two prime? Prove your result. Securiger 16:49, 3 May 2004 (UTC)

• Securiger, I know enough to know that Graham's number minus 2 is not prime. Given that it is a number of the form 3^3^3^3^3^3^3^3... with at least 2 3's, its final digit is a 7. A number ending in 7 will end in 5 if you subtract 2, and apart from the single digit 5, a number ending in 5 is not prime because it has 5 as a factor. Therefore, Graham's number minus 2 is not prime. And, Graham's number minus 3, which is even, is not prime. Georgia guy 22:26, 8 Mar 2005 (UTC)

Wow

I tried figuring out just how big this number is, and my mind blew a gasket when it got to the 4th Knuth iteration. Yikes. I'm glad there's only 1e87 particles in the universe, otherwise some wacko would already be trying to write it out. --Golbez 06:53, Sep 3, 2004 (UTC)

Operation needed for Graham's number

Recall from the above the Graham's number is to large to visualize simply with the help of tetration. Try the question "What operation is needed to visualize it??" Please highlight it in the list below, defining each operation as being related to the previous one the way multiplication is related to addition.

1. Addition
2. Multiplication
3. Exponentiation
4. Tetration
5. Pentation
6. Hexation
7. Heptation
8. Oktation
9. Enneation
10. Dekation
11. Hendekation or above

66.245.74.65 23:51, 30 Oct 2004 (UTC)

None of these are even close to sufficient. Regular exponentiation requires 1 Knuth arrow to be represented, and dekation requires 8. Dekation in itself is a very powerful operator that produces large numbers. But for every layer of the 65 layers that Graham's number goes further into, what happens is that the number of arrows is equal to the result of the previous step. $3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987$, so we have 7625597484987 arrows already. Which is much, much larger than dekation. The next step will have $3^{7625597484987}$ arrows, a gargantuan number. This is just the number of arrows. And we're doing this 65 times. -- Daverocks 07:42, 19 August 2005 (UTC)

Sorry, I have to correct a fact in my own statement here. You start with $3\uparrow \uparrow \uparrow \uparrow 3$, and this is the number of arrows required for the next step, and so on and so on (one does not start with $3\uparrow \uparrow 3$ as I stated above). -- Daverocks 12:12, 30 August 2005 (UTC)

Comparison

Is it bigger than googol? Googolplex?

Yes. It is even bigger than googolduplex, googoltriplex, and even googolcentuplex, defining googol(n)-plex as the number 10^10^10^10^...10^10^10^10^googol where there are a total of n 10's. 66.245.110.114 23:55, 6 Dec 2004 (UTC)

Adding to that, one can easily find numbers larger than a googolplex, even though it is also unconceiveably large. However, $9^{9^{9^{9^{9^{9}}}}}$ is larger, and can be written with fewer symbols. Remember that a googolplex is $10^{10^{100}}$, which requires 7 symbols to be written down. The above-mentioned number only requires 6. -- Daverocks 10:30, 8 August 2005 (UTC)

BTW, isn't $9^{9^{9^{9}}}$ already larger than $10^{10^{100}}$ ? --FvdP 20:56, 19 August 2005 (UTC)

Actually, FvdP, you're probably right. -- Daverocks 12:05, 30 August 2005 (UTC)

Definately right in fact; stacking new power layers is much more powerful than incresing the numbers of lower layers. (which is why the procedure for G gets so very large very fast.) For example, $9^{9^{9^{9}}}=9^{9^{387,420,489}}$ which is clearly larger than $10^{10^{100}}$

Still informally but with more precision, here is another way to see it, by taking twice the logarithm on each side: $\log 9^{9^{9^{9}}}=9^{9^{9}}\log 9$ so $\log \log 9^{9^{9^{9}}}=9^{9}\log 9+\log \log 9\approx 9^{9}\log 9$, while similarly, $\log \log 10^{10^{100}}\approx 100\log 10$. There is (almost) no more dispute which is greater ;-) You see here how the actual numbers in the lower exponentiation layers just seem to evaporate and play no significant role in the proof. --FvdP 22:08, 23 December 2005 (UTC)

notation

Are you saying that even if you used the notation like 10^10^100^100000000 etc, there isnt enough ink or hdd space in the universe to express graham's #? 69.142.21.24 05:20, 5 September 2005 (UTC)

That is correct. Graham's number is far too large to simply be expressed in powers of powers of powers. Even if one takes the exponentiation operator to a higher level, such as tetration or many (actually, an incomprehensible number of) hyper operators above this, it would still not be even close to sufficient to expressing Graham's number with all the matter in the known universe. -- Daverocks 12:32, 19 September 2005 (UTC)

Largest number with an article

I assume from the above discussion that this is the largest number to have a serious Wikipedia article devoted to it. Is that correct? CDThieme 03:02, 8 October 2005 (UTC)

Well, the greatest integer. We have plenty of articles about infinite numbers, and Graham's number is finite. Factitious 19:51, 10 October 2005 (UTC)

Can numbers be infinite? I don't think so, a number is a number. Infinite is a concept. Rbarreira 19:24, 20 December 2005 (UTC)

See Aleph-null, for instance. Factitious 22:32, 21 December 2005 (UTC)

There are larger finite integers in math. In Friedman's Block Subsequence Theorem, n(4), the lower bound for the length of the string for four letters, is far, far larger than Graham's number.Mytg8 14:42, 4 May 2006 (UTC)

Years in Hell

Imagine being in Hell for a Graham's Number of years. (It's said that people stay in hell for all eternity...) If someone was taken out of Hell after that many years, what could they say and how would they feel? Think about and imagine this. --Shultz 00:15, 2 January 2006 (UTC)

Nonsense. The universe is only 13,700,000,000 years old, a number that can be written in comma format with only 4 periods of digits. Graham's number is far too large to write in comma form with even millions of such periods. Georgia guy 01:10, 2 January 2006 (UTC)

Letter

Since this is obviously too large a number to write down, is there a letter to represent it in common usage?

"Graham's Number" is used to refer to it.--Lkjhgfdsa 20:29, 19 April 2006 (UTC)

There's nothing like e or π. If context of the discussion is known one might use G. Kaimiddleton 07:50, 20 April 2006 (UTC)

Upper bound of something

You know with this nummer being so large, how on earth was it proven to be the upper bound of that question?

• Maybe even more specific: does anyone know where to find the proof. I can find a zillion articles about Grahams number, how big it is and why. But the proof itself I can not find. Is it available in public domain? Pukkie 07:37, 2 June 2006 (UTC)

• That's a good question. According to the magazine article that announced the discovery back in 1977, the proof was unpublished. As far as I know, it has never been published. Very odd. Of course, Friedman has never published his proof of n(4) either...  :-) Mytg8 15:48, 2 June 2006 (UTC)

Colloquial statement of the problem

Can someone clarify this for me? The problem connected to Graham's number is described as: "Take any number of people, list every possible committee that can be formed from them, and consider every possible pair of committees. How many people must be in the original group so that no matter how the assignments are made, there will be four committees in which all the pairs fall in the same group, and all the people belong to an even number of committees." What does this mean? I understand the first part, taking n people and listing all 2^n committees, and then considering all (2^n choose 2) pairs. I don't understand anything else except that all people are in an even number of committees. Thanks. :) CecilPL 20:57, 12 May 2006 (UTC)

• That's a tricky question, I find it hard to be both correct and coloquial. I'll give it a try:

"Take a number of people, list every possible committee that can be formed from them, and consider every possible pair of committees. Now assign every pair of committees to one of two secretaries. How many people must be in the original group so that no matter how the assignments are made there will always be a secretary with a group of four committees where all the people belong to an even number of these four committees." Pukkie 10:52, 7 June 2006 (UTC)

I do think that's better. Any one object to it replacing the description in the article? --Michael C. Price ^talk 08:19, 23 June 2006 (UTC)

There is a serious problem with the 'colloquial statement', both in its old form and in the new one. It yields only a necessary condition for the four points to be complanar, not a sufficient one. This means that, at least a priori, there is good reason to assume that a lower number is sufficient for guaranteeing a monochromatic 4-set satisfying the 'colloquial statement' than the original one.

I've tried to find the origin of the 'colloquial statement'. It is found also in the mathworld article on Graham's number, which refers to some popular articles I do not have access to. It also refers to the original article, in Transactions of the American Mathematics Society. I added a reference to this, but didn't find the 'colloquial statement' there. Could someone please search the source of it; since it is rather nice, it would prefer improvement to deletetion.

A short but technical explanation of the trouble: Adopt the article notation. Note, that there are 6 sub-2-sets of any given 4-set of vertices. Thus, let n=6, and choose the four vertices in such a way that each one of the six coordinates will be 1 in exactly one of these six 2-sets, and 0 in its complement. Explicitly, you may pick the four vertices A, B, B, and D with coordinates

(1,1,1,0,0,0), (1,0,0,1,1,0), (0,1,0,1,0,1), and (0,0,1,0,1,1),

respectively. This set does not lie in one plane; if you consider the vectors ${\overline {AB}}=(0,-1,-1,1,1,0)$, ${\overline {AC}}=(-1,0,-1,1,0,1)$, and ${\overline {AD}}=(-1,-1,0,0,1,1)$, you'll find that they are linearly independent. Thus it is not a 4-set of the kind Graham and Rotschild discuss.

On the other hand, if we give the 'colloquial' interpretation, we should consider A, B, C, and D as four committees with three members each, formed within a set of six people (one for each coordinate). If the six people are named a, b,..., f, then we find that A consists of a, b, and c, which we briefly may write as A=abc. Similarly, B=ade, C=bdf, and D=cef. Thus, each person is a member of an even number (namely 2) of the committees.

This is not so interesting for the case n=6, of course; but the construction could easily be extended to many millions of 4-sets, if e.g. n=30. JoergenB 18:54, 26 September 2006 (UTC)

You are right, I will delete the colloquial version. If someone has a good way to say 'in the same plane' colloquially we can put the corrected version back. Pukkie 08:20, 21 October 2006 (UTC)

But???

Think of this all hypothetically... What if one could create a Solar System-sized computer that was made ONLY to store Graham's number in exponential form. all calculations could be routed from a diffrent computer. can it be done? — Preceding unsigned comment added by Geobeedude (talk • contribs)

• No, it can't. Even the number of Knuth arrows is too large to be stored that way. --Ixfd64 18:23, 19 May 2006 (UTC)
• More to point, if I recall my calculations correctly, the number of digits reaches beyond the number of particles in the universe by the 4th iteration. So by the time you hit the 64th, ... well let's put it this way. Let's say you stored it in decimal (It would be binary, but let's go with this for simplicity). You need at least one particle for each digit, because that's how the computer's memory works. Even if it's so much as an electron in an electrical field, that digit has to be "stored" by something. So you would have to use the entire universe's worth of particles just to store the digits of the 4th iteration - let alone the 64th. You would need an unimaginably large number of *universes* to even begin writing the number down. --Golbez 08:12, 20 June 2006 (UTC)

numbers larger than Graham's number

It seems that Graham's number is no longer the largest number used in serious mathematical proofs. See some of the work by Harvey Friedman, for example. He mentions numbers like n(4) and TREE[3]. [1] [2] Should we mention these numbers in the article? --Ixfd64 18:28, 19 May 2006 (UTC)

• Maybe but just mentioning them is a bit short. Also: I do not understand TREE[3]. How big is this in Conway chained arrow notation? Pukkie 11:36, 30 May 2006 (UTC)

I read the above papers some time ago. As I recall, this number can only be descibed with more than 2^1024 symbols in any notation.Mytg8 16:45, 20 June 2006 (UTC)

Well, you could create a new notation that asks for the number of symbols required in your case, couldn't you?? Georgia guy 16:49, 20 June 2006 (UTC)

What is n() or TREE()?

Well, we could try Jonathan Bowers' array notation. --Ixfd64 22:35, 21 June 2006 (UTC)

Actually, In Graham's and Rotschild's original article, they prove much more general statements. The Graham number estimate is just one of the first one deducible from their proof, out of an infinite series. JoergenB 18:05, 26 September 2006 (UTC)

According to the original 1977 Scientic American article that announced the number, Martin Gardner stated that the proof for what is called Graham's number was unpublished. AFAIK, the proof has never been published. I'm not familiar with that 1971 Graham and Rothschild paper; perhaps it was an earlier estimate but it's not the same number. A Usenet discussion of this topic-http://groups.google.com/group/sci.math/browse_thread/thread/3f2bec34954af48c/28b726a9fe028bcb?lnk=gst&q=%22graham%27s+number%22&rnum=3#28b726a9fe028bcbMytg8 04:24, 27 September 2006 (UTC)

I do not have access to the SciAm article, but certainly consider Graham's and Rotschild's as the original... When you write Martin Gardner stated that the proof for what is called Graham's number was unpublished, I hope you mean something like 'the proof of the fact that this number indeed is an upper bound'. (A number in itself does not have a proof, not even in Gödel's theory.) Does he really claim this to be unpublished; and doesn't he mention the G&R article Ramsey's theorem for n-parameter sets at all?

The reference is interesting; I'll try to analyse the relationship between the original G&R number and the Gardner-Graham one as soon as I get the time. The representations are different, but that doesn't automatically mean that the numbers are. Actually, as G&R define their estimate, it is a power of 2 rather than a power of 3, which does indicate that the numbers are not quite the same:-) However, even so, it would be a surprise if the older number was smaller, for obvious reasons. Thus, I'll have to correct my corrections; but we also have a potential candidate for a larger number than the GG one, from the horse's own mouth. JoergenB 23:03, 28 September 2006 (UTC)

As I wrote in the posting that began the cited sci.math thread in 2004, the upper bound published by Graham & Rothschild in 1971 is much smaller than the one that appears to have been strangely attributed to Graham by Gardner in 1977. It seems obvious that Gardner's was a misattribution unless Graham & Rothschild had it wrong in 1971 -- and afaik no publication has made that claim. (In fact, Exoo's 2003 paper refers to the 1971 value -- not Gardner's -- as "Graham's number".) But maybe it's best to just accept the popular misattribution, and continue referring to the so-called "Graham's number" by that name, even though it's apparently not Graham's at all. --r.e.s. (Talk) 00:45, 29 September 2006 (UTC)

The correct thing to do is of course to go through the proof of G&R, and deduce the estimate from that :-(. Also, there is a slight vagueness in their article; what they write is precisely (my emphasis) '... the best estimate for $N^{*}$ we obtain this way is roughly

$N^{*}\leq F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).$'

Now, I do not know what 'roughly' means, without further investigations. I'll have to read the whole stuff, sometime, I fear.

Another question to you people who have the SciAm article: Could you please check whether the secretary parable is there, and if so, if there were other conditions added? 'Our' article is still defect, and I haven't yet got any reaction to my comment in the section on the colloquial statement of the problem (supra). It is clear that this cannot be left in an erroneous form, and I'd prefer a correction to a deletion. JoergenB 10:12, 29 September 2006 (UTC)

I have an old Xerox copy and here are some quotes from the SciAm article-"Mathematical Games";volume 237 pp 18-28 November 1977--if they'll help anything. The article is on Ramsey graph theory, author Martin Gardner, and is informal-as you would expect from a popular journal. He goes into some history of Ramsey Graphs, then p.24 brings up Ronald L. Graham, "...one of the nation's top combinatorialists...(who) has made many significant contributions to generalized Ramsey theory... unquote. Then a couple paragraphs later ...this suggests the following Euclidean Ramsey problem: What is the smallest dimension of a hypercube such that if the lines joining all pairs of corners are two-colored, a planar K_4 will be forced? ...The existence of an answer when the forced monochromatic K_4 is planar was first proved by Graham and Bruce L. Rothschild in a far reaching generalization of Ramsey's theorem that they found in 1970. *(the 1971 paper?)* (continuing) Finding the actual number, however, is something else. In an unpublished proof Graham has recently established an upper bound, but it is a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof. End quote.

The 1971 G&R article indeed was 'received by the editors' 1970. Math articles may have considerable time lags.JoergenB 21:34, 29 September 2006 (UTC)

Gardner then proceeds to describe the usual description of the number using Knuth's arrows, starting with 3^^^^3, continued for 2^6 layers(as he terms it). Back to quote: It is this bottom layer that Graham has proved to be an upper bound for the hypercube problem, unquote. No mention of secretaries, committees, etc. But wait, there appears to be another, earlier, estimate :-)http://www.math.ucsd.edu/~fan/ron/papers/78_02_ramsey_theory.pdf p.11?Mytg8 19:41, 29 September 2006 (UTC)

Interesting! But this 'new old' G&R paper is markedly longer. Well, we have some reading to do, I guess. JoergenB 21:34, 29 September 2006 (UTC)

One more link- http://groups.google.com/group/sci.math.research/browse_thread/thread/dfe28ba0cb00f7bc/5ade381fadaf1485?lnk=st&q=%22graham%27s+number%22&rnum=12#5ade381fadaf1485 In this 2002 topic and response to Exoo, author tchow says he asked Graham himself about the number and Graham said the theorem was unpublished.Mytg8 15:03, 30 September 2006 (UTC)

Graham's number tower image

Isn't there a convenient way of expressing Graham's number by simply writing out the 64-layer arrow tower? That will knock some sense into those people.

The first layer is 3^^^^3, which denotes the number of arrows in the below layer, with that number (an insane number of arrows) denoting the number of arrows below that layer, and this recursive operations continues for 64 layers.

The number in the second layer is already way larger than the number of particles in the universe...

(And if i'm not mistaken, Graham's Number is the upper bound for the number of dimensions required for a standard hypercube, when its corners are 2-colored, forces a tetrahedron? (Grr...Wikipedia does not have an article describing the Ramsey graphs)Doomed Rasher 22:58, 3 October 2006 (UTC)

How large is 3^^^^3?

I've been trying to come to grips with Graham's Number and have been truly awestruck by how staggeringly, inconceivably huge it is. But it's obvious from the various questions that few people have any idea of the scale of it. I've tried working out some idea of 3^^^^3 but I can't get anywhere (probably due to my infamiliarity with Knuth arrow notation). How big is g₁? g₂? How many in the sequence can be represented in some kind of mainstream notation? -Maelin 11:52, 12 October 2006 (UTC)

Take a look at Ackerman_function#Ackermann_numbers where there is an example of 4^^^^4. Kaimiddleton 21:35, 14 October 2006 (UTC)

Oops, I notice there's an error there, currently. Look at this edit for a correct (though poorly formatted) version. Kaimiddleton 21:48, 14 October 2006 (UTC)

question on notation

wouldn't $g_{n}=3\uparrow ^{g_{n-1}}3$ be the same as $g_{n}=3\uparrow ^{68}3$ ? —The preceding unsigned comment was added by 199.90.15.3 (talk) 17:42, 11 December 2006 (UTC).

No. Remember, the number of up-arrows in each term g_n is equal to the actual number, g_n-1. So we have $\textstyle g_{1}=3\uparrow ^{4}3=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)$ which is very big. Then, $\textstyle g_{2}=3\uparrow ^{g_{1}}3=3\uparrow ^{(3\uparrow ^{4}3)}3$, that is, there are g₁ up-arrows between the threes in g₂. That makes g₂ quite colossally big. Then g₃ has that many up-arrows between its 3s, and so on.

With Knuth up-arrows, each new up-arrow blows you way out of the ball park. $\textstyle 3\uparrow \uparrow \uparrow 3$ is huge, but $\textstyle 3\uparrow \uparrow \uparrow \uparrow 3$ makes it look tiny by comparison. And in the sequence g_n by which Graham's number is defined, you're not adding one up arrow each time, you're adding inconceivably huge numbers of up arrows each time. And you do that 64 times. Graham's number is big. Maelin (Talk | Contribs) 22:06, 11 December 2006 (UTC)