Graham\'s number - Citizendia

Graham's number, named after Ronald Graham, is a large number often described as the largest finite number that has ever been seriously used in a mathematical proof. Ronald Lewis Graham (born October 31, 1935) is a Mathematician credited by the American Mathematical Society with being "one of the principal In Mathematics, a proof is a convincing demonstration (within the accepted standards of the field that some Mathematical statement is necessarily true Guinness World Records even listed Graham's number as the World Champion largest number. Guinness World Records, known until 2000 as The Guinness Book of Records (and in previous U Graham's number is much larger than other well known large numbers such as a googol and a googolplex, and even larger than Skewes' number and Moser's number, other well-known large numbers. A googol is the Large number 10100 that is the digit 1 followed by one hundred zeros (in Decimal representation In Number theory, Skewes' number can refer to any of several extremely large numbers used by the South African mathematician Stanley Skewes as Upper In Mathematics, Steinhaus – Moser Notation is a means of expressing certain extremely Large numbers It is an extension of Steinhaus&rsquos Indeed, there is no concise way to write Graham's number, or any reasonable approximation, using conventional mathematical operators. Even power towers (of the form $a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}}$ ) are useless for this purpose. It can be most easily notated by recursive means using Knuth's up-arrow notation or the Hyper operator. In Mathematics, Knuth's up-arrow notation is a method of notation of very large Integers introduced by Donald Knuth in 1976 The hyper operators forming the hyper n family are related to Knuth's up-arrow notation and Conway chained arrow notation as follows

1 Graham's problem
2 Definition of Graham's number
- 2.1 Magnitude of Graham's number
3 See also
4 References
5 External links

Graham's problem

Graham's number is connected to the following problem in the branch of mathematics known as Ramsey theory:

Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on

2 n

vertices. This article provides an introduction For a more detailed and technical article see Ramsey's theorem. In Geometry, a hypercube is an n -dimensional analogue of a square ( n = 2 and a Cube ( n = 3 In Geometry, a vertex (plural "vertices" is a special kind of point. In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an For other uses see Vertex. In Graph theory, a vertex (plural vertices) or node is the fundamental unit out Then colour each of the edges of this graph using only the colours red and black. What is the smallest value of n for which every possible such colouring must necessarily contain a single-coloured complete sub-graph with 4 vertices which lie in a plane?

Although the solution to this problem is not yet known, Graham's number is the smallest known upper bound for it. In Mathematics, especially in Order theory, an upper bound of a Subset S of some Partially ordered set ( P, &le This bound was found by Graham and B. L. Rothschild (see (GR), corollary 12). They also provided the lower bound 6, adding the qualifying understatement: "Clearly, there is some room for improvement here. In Mathematics, especially in Order theory, an upper bound of a Subset S of some Partially ordered set ( P, &le "

In Penrose Tiles to Trapdoor Ciphers, Martin Gardner wrote, "Ramsey-theory experts believe the actual Ramsey number for this problem is probably 6, making Graham's number perhaps the worst smallest-upper-bound ever discovered. Martin Gardner (b October 21, 1914, Tulsa Oklahoma) is a popular American mathematics and science writer specializing in Recreational mathematics " More recently Geoff Exoo of Indiana State University has shown (in 2003) that it must be at least 11 and provided evidence that it is larger. Indiana State University ( ISU) is a Public university that is located in Terre Haute Indiana, United States.

Definition of Graham's number

Using Knuth's up-arrow notation, Graham's number $G$ is defined as

$G = \left . \begin{matrix} 3 \underbrace{ \uparrow \ldots \uparrow } 3 \\ \underbrace{ \vdots } \\ 3 \uparrow\uparrow\uparrow\uparrow 3 \end{matrix} \right \} \text{64 layers}$

Equivalently,

G = g 64

where $g_1=3\uparrow\uparrow\uparrow\uparrow 3$ , $g_n = 3\uparrow^{g_{n-1}}3$

G = f 64 (4)

where

f (n) = hyper(3, n + 2,3)

and hyper() is the hyper operator. In Mathematics, Knuth's up-arrow notation is a method of notation of very large Integers introduced by Donald Knuth in 1976 The hyper operators forming the hyper n family are related to Knuth's up-arrow notation and Conway chained arrow notation as follows

Graham's number G itself cannot succinctly be expressed in Conway chained arrow notation, but $3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2$ , see bounds on Graham's number in terms of Conway chained arrow notation. Conway chained arrow notation, created by mathematician John Horton Conway, is a means of expressing certain extremely Large numbers. Conway chained arrow notation, created by mathematician John Horton Conway, is a means of expressing certain extremely Large numbers.

Magnitude of Graham's number

Since appreciation of the true size of Graham's number can be difficult, it can be helpful to express the first term of the sequence in terms of exponentiation:

$g_1 = 3 \uparrow \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) = 3 \uparrow \uparrow \uparrow \left( \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copies of 3}} \right) = \left. \begin{matrix} \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\text{copies of 3}}\text{copies of 3}} \\ \vdots \\ \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copies of 3}}\text{copies of 3}}\text{copies of 3} \end{matrix} \right \} \left. \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copies of 3}} \right. \text{layers}$

A simpler expression can be given using tetration:

$g_1 = 3 \uparrow \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow (3 \uparrow \uparrow 3)) = 3 \uparrow \uparrow \uparrow (^{{}^3 3} 3) = \underbrace{^{^{^{^{^3\cdot}\cdot}\cdot}3}3}_{ ^{{}^3 3} 3 \text{ copies of 3}}$

Note that the arrows are right-associative; e. In Mathematics, tetration (also known as hyper -4 In Mathematics, associativity is a property that a Binary operation can have g. , $3 \uparrow 3 \uparrow 3 = 3 \uparrow (3 \uparrow 3) = 3 \uparrow 27 = 7,625,597,484,987$ .

This first term, g₁, is already much greater than the number of atoms in the observable universe, and grows at an enormous rate as it is iterated through the sequence g.

References

Gardner, Martin (1989). The hyper operators forming the hyper n family are related to Knuth's up-arrow notation and Conway chained arrow notation as follows In Number theory, Skewes' number can refer to any of several extremely large numbers used by the South African mathematician Stanley Skewes as Upper In Mathematics, Knuth's up-arrow notation is a method of notation of very large Integers introduced by Donald Knuth in 1976 Martin Gardner (b October 21, 1914, Tulsa Oklahoma) is a popular American mathematics and science writer specializing in Recreational mathematics Penrose Tiles to Trapdoor Ciphers. ISBN 0-88385-521-6.
Graham, R. L. ; Rothschild, B. L. (1971). "Ramsey's Theorem for n-Parameter Sets". Transactions of the American Mathematical Society 159: 257-292. doi:10.2307/1996010. A digital object identifier ( DOI) is a permanent identifier given to an Electronic document.

External links

"A Ramsey Problem on Hypercubes" by Geoff Exoo
Mathworld article on Graham's number
How to calculate Graham's number

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Graham's problem

Definition of Graham's number

Magnitude of Graham's number

See also

References

External links