Talk:Graham's number

WikiProject Mathematics (Rated C-class, Low-priority)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 C Class
 Low Priority
Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.

Visualizing Graham's number

The number of times you have to perform the "How many Knuth arrows are needed??" operation on Graham's number is finally small enough to write out; it is only 64. But have numbers for which the number of times you have to perform the "How many Knuth arrows are needed??" operation on a number too large to write out ever been used?? There have been a few references to numbers larger than Graham's number in some sections of the talk page. Do any of these numbers meet this criterion?? Georgia guy (talk) 16:52, 19 January 2012 (UTC)

For example, my BOX_M~ (a specific natural number involving "human problems" solutions) satisfies this criterion: http://www.scribd.com/doc/77714896/The-largest-number-ever-il-numero-dei-record The busy beaver function "Σ" is even faster (non computable functions). BTW I don't find this outcome very interesting for this section :)

Marcokrt (talk) 18:24, 19 January 2012 (UTC) — Preceding unsigned comment added by Marcokrt (talkcontribs) 18:19, 19 January 2012 (UTC)

Georgia guy:
In the fast-growing hierarchy we have fω64(6) > G, where fω is a version of Ackermann's function and corresponds to the operation you're asking about. If we look at a much larger ordinal index, say ε0 instead of ω, then we'll encounter numbers like fε0(2), which certainly meets your criterion -- even with the small argument of 2, it requires f8(8) > 2↑78 iterations of fω.
Marko:
I think it's not hard to show that your number satisfies $Box_{-}\widetilde{M} \ll f_{\epsilon_0}(3)\,\!$, where fε0 is as just described (linked) above.
(Please sign your posts by typing four tildes (~~~~) at the very end.)
r.e.s. (talk) 18:30, 20 January 2012 (UTC)

Ok r.e.s., even if probably $Box_{-}\widetilde{M} > f_{\epsilon_0}(3)\,\!$, it's easily possible to surpass its size, for example considering the one at the bottom of this page: http://www.polytope.net/hedrondude/array.htm My number is based on a set of philosophical/empiric assumptions and its definition could (abstracly) be useful to construct upper limits for particular kinds of "human condition related problems"... it's quite similar to a universal outlet, even if far less interesting ;)

Best regards Marcokrt (talk) 00:08, 21 January 2012 (UTC)

Parsing?

There was something in the article on Knuth's up-arrow notation which made me pause -- a single arrow is ordinary exponentiation? So... if I've parsed that -- and consequently the contents of this article -- correctly, then I think the following expansion defines G1.

(I'm using 'U' for 'Up Arrow')

G1 = 3 U U U U 3

3 U 3 = 3^3 = 27

3 U U 3 = 3 U (3U3) = 3^27 ~= 7.6 e12

3 U U U 3 = 3 U (3 U (3U3)) = 3 U (3^27) = 3^(3^27) ~= 3^(7.6e12) = some monster that is ~3.6*10^12 digits long ~= 10^(10^(10^1.1))

3 U U U U = 3 U (3U (3U (3U3))) = 3 ^ (some monster) = G1, "a jillion"

and then 3 (a jillion instances of U) 3 = G2, "a kajillion", etc etc up to G64.

Is this correct? DS (talk) 14:05, 11 September 2012 (UTC)

Yup! I think you got it. Owen× 14:37, 11 September 2012 (UTC)
Yes and No. It is correct that g1 = 3↑↑↑↑3, g2 = 3↑↑...↑3 (with g1 ↑s), and so on up to g64; however, your evaluations of 3↑↑↑3 and 3↑↑↑↑3 are way too small.
For example, 3↑↑↑3 = 3↑↑3↑↑3 = 3↑3↑3↑...3↑3 where the number of 3s is 3↑↑3 = 3↑27. This is much larger than your 3↑3↑3↑3, which is actually just 3↑↑4.
r.e.s. (talk) 01:15, 12 September 2012 (UTC)
R.e.s. is right; my mistake. Owen× 11:54, 12 September 2012 (UTC)

Improved bound

Look at this article. There are presented much stronger upper bound for that problem where Graham's number was used. 31.42.233.14 (talk) 22:23, 18 March 2013 (UTC)

It is a wiki article on Wikia, not a peer reviewed source. Probably not even considered reliable by Wikipedia guidelines. SpinningSpark 15:52, 17 August 2013 (UTC)

Up arrows

Just a suggestion. The article already uses → for Conway's notation. I wonder if it would be an idea to use the unicode up arrow too: ↑↑. Would make it easier for readers to copy / paste the formulae, I just wanted to post to facebook about Graham's number and remade one of the formulae as 2↑↑(2↑↑(2↑↑9)) which you can use anywhere that supports unicode.

I'm not going to actually do it because there are so many formulae in the article and for consistency of style you'd need to do the whole thing. But might be worth considering as something to do? Robert Walker (talk) 09:00, 16 August 2013 (UTC)

What does this mean?

I've read and re read this text. But I have no idea of what Grahams number explains. Could someone write something in plain english for the non professional what Graham's number is supposed to solve. — Preceding unsigned comment added by 92.32.104.205 (talk) 11:22, 18 October 2013 (UTC)

Maybe this will help ... Here's a formulation of the problem in terms of row-vectors (one dimensional arrays of n numbers), which I used in a program to study this problem with arbitrary colorings (OR):
A unit n-cube has 2n corners, corresponding to the 2n binary row-vectors of length n. (E.g. for n = 3, these are the 23 = 8 vectors [0 0 0], [0 0 1], [0 1 0], [0 1 1], [1 0 0], [1 0 1], [1 1 0], [1 1 1], and similarly for other values of n.) A coloring is just an assignment of either 'red' or 'blue' to each possible pair of these vectors. Let's call a given coloring eventful if there are four such vectors (say a,b,c,d) with the following two properties:
(1) the six possible pairs of the four vectors (i.e. the pairs {a, b} {a, c} {a, d} {b, c} {b, d} {c, d}) are all assigned the same color, and
(2) if a difference vector is formed from each of the six pairs (subtracting one vector of the pair from the other, in either order (e.g. {a, b} → a - b, {a, c} → c - a, etc.) then any two of these difference vectors is sufficient to generate the other four by linear combination. (This is an algebraic way of saying that the points corresponding to the four vectors are coplanar. There are well-known algorithms for checking this.)
NB: The number of pairs to be colored is 2n - 1(2n - 1), so the number of possible colorings is 22n - 1(2n - 1), which gets large very quickly.
Here's the behavior as n increases ...
n = 1:   0% of the possible colorings are eventful (because there are fewer than 4 corners),
n = 2:  ~3% of the possible colorings are eventful (2 of the 64 possible colorings),
n = 3:  ~30% of the possible colorings are eventful (estimated by random colorings),
n = 4:  ~95% of the possible colorings are eventful (estimated by random colorings),
5 ≤ n < N*:  the percentage of colorings that are eventful approaches (but does not reach) 100%,
n ≥ N*100% of the possible colorings are eventful, where N* is some unknown number greater than 12.
The existence of the number N* was proved by Graham & Rothschild, and "Graham's number" (G) was specially invented by Graham as an easily described upper bound on N*. (Maybe the number N* itself should be called the "Graham-Rothschild number" to distinguish it from G.)
r.e.s. (talk) 22:18, 23 October 2013 (UTC)
I think the IP was asking for something to go in to the article rather than an explanation here. Personally, I think the explanation already in the article is easier to understand than the above. SpinningSpark 15:30, 24 October 2013 (UTC)
You are right. This is even harder tounderstand. it is neither written in plain english or for the non professional. — Preceding unsigned comment added by 78.78.76.98 (talk) 07:33, 28 October 2013 (UTC)
Let me try in a thoroughly non-formal way that will probably annoy the hell out of every real mathematician reading this. For n=2 draw a square of dots (four dots). Draw lines joining every dot to every other dot. How many rectangles can be found in this figure? Only one of course, the original square. Now colour every line either black or red. Can you find a colouring scheme so that no rectangle is all the same colour? Trivially easy of course since there is only one rectangle. That one is a pass meaning Graham's number is more than 2. Now draw a cube of eight dots (n=3) and join every dot to every other dot. This is no longer trivial because besides the six squares of the cube faces there are also rectangles on the diagonals. It may be non-trivial but it is still pretty easy to find a colouring scheme so that no rectangle is all one colour. Pass that one too, Graham's number is greater than 3. For n=4 one must draw a four-dimensional cube, a tesseract or 4-cube. This is starting to get hard because rectangles can be found all over the place, but still possible to do. Carry on increasing n for higher and higher dimensions. Eventually you will come to a value of n where it is impossible to colour every rectangle in mixed colours. Graham manged to prove that this value of n cannot be greater than Graham's number (although it may well be a lot smaller). Graham's number is an upper bound on the maximum value of n. Regards, SpinningSpark 09:31, 28 October 2013 (UTC)
My reply above is not intended for the general reader, but is for anyone acquainted with (or willing to learn) the most-basic vector/array concepts. It is an explanation of the problem in terms of simple arrays of integers, completely avoiding the difficulty of visualizing hypercube geometry. Saying "just do with 4 & higher dimensional hypercubes what was done with a cube" does not convey a clear idea of *how* this is to be actually carried over to the higher dimensions, whereas the above explanation does describe the *how* (in terms of integer arrays), which makes it slightly technical.
r.e.s. (talk) 20:30, 30 October 2013 (UTC)
My question was if someone could write something in the article for the general reader. Not for the professional. — Preceding unsigned comment added by 92.32.106.60 (talk) 12:29, 6 November 2013 (UTC)