Graham's number is an immense number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is much larger than many other large numbers such as Skewes's number and Moser's number, both of which are in turn much larger than a googolplex. As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham's number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe. Thus Graham's number cannot be expressed even by physical universe-scale power towers of the form , even though Graham's number is indeed a power of 3.
However, Graham's number can be explicitly given by computable recursive formulas using Knuth's up-arrow notation or equivalent, as was done by Ronald Graham, the number's namesake. As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers, the latter of which grow faster than any computable sequence. Though too large to ever be computed in full, the sequence of digits of Graham's number can be computed explicitly via simple algorithms; the last 13 digits are ...7262464195387. Using Knuth's up-arrow notation, Graham's number is , [1] where
Graham's number was used by Graham in conversations with popular science writer Martin Gardner as a simplified explanation of the upper bounds of the problem he was working on. In 1977, Gardner described the number in Scientific American , introducing it to the general public. At the time of its introduction, it was the largest specific positive integer ever to have been used in a published mathematical proof. The number was described in the 1980 Guinness Book of World Records , adding to its popular interest. Other specific integers (such as TREE(3)) known to be far larger than Graham's number have since appeared in many serious mathematical proofs, for example in connection with Harvey Friedman's various finite forms of Kruskal's theorem. Additionally, smaller upper bounds on the Ramsey theory problem from which Graham's number was derived have since been proven to be valid.
Graham's number is connected to the following problem in Ramsey theory:
Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2n vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?
In 1971, Graham and Rothschild proved the Graham–Rothschild theorem on the Ramsey theory of parameter words, a special case of which shows that this problem has a solution N*. They bounded the value of N* by 6 ≤ N* ≤ N, with N being a large but explicitly defined number
where in Knuth's up-arrow notation; the number is between 4 → 2 → 8 → 2 and 2 → 3 → 9 → 2 in Conway chained arrow notation. [2] This was reduced in 2014 via upper bounds on the Hales–Jewett number to
which contains three tetrations. [3] In 2019 this was further improved to: [4]
The lower bound of 6 was later improved to 11 by Geoffrey Exoo in 2003, [5] and to 13 by Jerome Barkley in 2008. [6] Thus, the best known bounds for N* are 13 ≤ N* ≤ N''.
Graham's number, G, is much larger than N: it is , where . This weaker upper bound for the problem, attributed to an unpublished work of Graham, was eventually published and named by Martin Gardner in Scientific American in November 1977. [7]
The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977, writing that Graham had recently established, in an unpublished proof, "a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof." The 1980 Guinness Book of World Records repeated Gardner's claim, adding to the popular interest in this number. According to physicist John Baez, Graham invented the quantity now known as Graham's number in conversation with Gardner. While Graham was trying to explain a result in Ramsey theory which he had derived with his collaborator Bruce Lee Rothschild, Graham found that the said quantity was easier to explain than the actual number appearing in the proof. Because the number which Graham described to Gardner is larger than the number in the paper itself, both are valid upper bounds for the solution to the problem studied by Graham and Rothschild. [8]
Using Knuth's up-arrow notation, Graham's number G (as defined in Gardner's Scientific American article) is
where the number of arrows in each layer is specified by the value of the next layer below it; that is,
where
and where a superscript on an up-arrow indicates how many arrows there are. In other words, G is calculated in 64 steps: the first step is to calculate g1 with four up-arrows between 3s; the second step is to calculate g2 with g1 up-arrows between 3s; the third step is to calculate g3 with g2 up-arrows between 3s; and so on, until finally calculating G = g64 with g63 up-arrows between 3s.
Equivalently,
and the superscript on f indicates an iteration of the function, e.g., . Expressed in terms of the family of hyperoperations , the function f is the particular sequence , which is a version of the rapidly growing Ackermann function A(n, n). (In fact, for all n.) The function f can also be expressed in Conway chained arrow notation as , and this notation also provides the following bounds on G:
To convey the difficulty of appreciating the enormous size of Graham's number, it may be helpful to express—in terms of exponentiation alone—just the first term (g1) of the rapidly growing 64-term sequence. First, in terms of tetration () alone:
where the number of 3s in the expression on the right is
Now each tetration () operation reduces to a power tower () according to the definition where there are X 3s.
Thus,
becomes, solely in terms of repeated "exponentiation towers",
and where the number of 3s in each tower, starting from the leftmost tower, is specified by the value of the next tower to the right.
In other words, g1 is computed by first calculating the number of towers, (where the number of 3s is ), and then computing the nth tower in the following sequence:
1st tower: 3 2nd tower: 3↑3↑3 (number of 3s is 3) = 7625597484987 3rd tower: 3↑3↑3↑3↑...↑3 (number of 3s is 7625597484987) = … ⋮ g1 = nth tower: 3↑3↑3↑3↑3↑3↑3↑...↑3 (number of 3s is given by the n − 1th tower)
where the number of 3s in each successive tower is given by the tower just before it. The result of calculating the third tower is the value of n, the number of towers for g1.
The magnitude of this first term, g1, is so large that it is practically incomprehensible, even though the above display is relatively easy to comprehend. Even n, the mere number of towers in this formula for g1, is far greater than the number of Planck volumes (roughly 10185 of them) into which one can imagine subdividing the observable universe. And after this first term, still another 63 terms remain in the rapidly growing g sequence before Graham's number G = g64 is reached. To illustrate just how fast this sequence grows, while g1 is equal to with only four up arrows, the number of up arrows in g2 is this incomprehensibly large number g1.
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for expressions in logical proofs.
In mathematics, a binary operation or dyadic operation is a rule for combining two elements to produce another element. More formally, a binary operation is an operation of arity two.
In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that either produces the most output possible, or runs for the longest number of steps. Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game. Rather than traditional programming languages, the programs used in the game are n-state Turing machines, one of the first mathematical models of computation.
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices A and B is denoted as AB.
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)
Large numbers are numbers significantly larger than those typically used in everyday life, appearing frequently in fields such as mathematics, cosmology, cryptography, and statistical mechanics. They are typically large positive integers, or more generally, large positive real numbers, but may also be other numbers in other contexts. Googology is the study of nomenclature and properties of large numbers.
A chemical equation is the symbolic representation of a chemical reaction in the form of symbols and chemical formulas. The reactant entities are given on the left-hand side and the product entities are on the right-hand side with a plus sign between the entities in both the reactants and the products, and an arrow that points towards the products to show the direction of the reaction. The chemical formulas may be symbolic, structural, or intermixed. The coefficients next to the symbols and formulas of entities are the absolute values of the stoichiometric numbers. The first chemical equation was diagrammed by Jean Beguin in 1615.
In mathematics, the modern component-free approach to the theory of a tensor views a tensor as an abstract object, expressing some definite type of multilinear concept. Their properties can be derived from their definitions, as linear maps or more generally; and the rules for manipulations of tensors arise as an extension of linear algebra to multilinear algebra.
In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976.
Conway chained arrow notation, created by mathematician John Horton Conway, is a means of expressing certain extremely large numbers. It is simply a finite sequence of positive integers separated by rightward arrows, e.g. .
In mathematics, Steinhaus–Moser notation is a notation for expressing certain large numbers. It is an extension of Hugo Steinhaus's polygon notation.
In mathematics, the integral test for convergence is a method used to test infinite series of monotonous terms for convergence. It was developed by Colin Maclaurin and Augustin-Louis Cauchy and is sometimes known as the Maclaurin–Cauchy test.
In mathematics, tetration is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though Knuth's up arrow notation and the left-exponent xb are common.
In mathematics, the derived categoryD(A) of an abelian category A is a construction of homological algebra introduced to refine and in a certain sense to simplify the theory of derived functors defined on A. The construction proceeds on the basis that the objects of D(A) should be chain complexes in A, with two such chain complexes considered isomorphic when there is a chain map that induces an isomorphism on the level of homology of the chain complexes. Derived functors can then be defined for chain complexes, refining the concept of hypercohomology. The definitions lead to a significant simplification of formulas otherwise described (not completely faithfully) by complicated spectral sequences.
In mathematics, pentation is the fifth hyperoperation. Pentation is defined to be repeated tetration, similarly to how tetration is repeated exponentiation, exponentiation is repeated multiplication, and multiplication is repeated addition. The concept of "pentation" was named by English mathematician Reuben Goodstein in 1947, when he came up with the naming scheme for hyperoperations.
In signal processing, a polyphase matrix is a matrix whose elements are filter masks. It represents a filter bank as it is used in sub-band coders alias discrete wavelet transforms.
In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations in this context) that starts with a unary operation (the successor function with n = 0). The sequence continues with the binary operations of addition (n = 1), multiplication (n = 2), and exponentiation (n = 3).
A mathematical constant is a key number whose value is fixed by an unambiguous definition, often referred to by a special symbol, or by mathematicians' names to facilitate using it across multiple mathematical problems. Constants arise in many areas of mathematics, with constants such as e and π occurring in such diverse contexts as geometry, number theory, statistics, and calculus.
A galactic algorithm is one with world-beating theoretical (asymptotic) performance, but which is never used in practice. Typical reasons are that the performance gains only appear for problems that are so large they never occur, or the algorithm's complexity outweighs a relatively small gain in performance. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.
In mathematics, the Graham–Rothschild theorem is a theorem that applies Ramsey theory to combinatorics on words and combinatorial cubes. It is named after Ronald Graham and Bruce Lee Rothschild, who published its proof in 1971. Through the work of Graham, Rothschild, and Klaus Leeb in 1972, it became part of the foundations of structural Ramsey theory. A special case of the Graham–Rothschild theorem motivates the definition of Graham's number, a number that was popularized by Martin Gardner in Scientific American and listed in the Guinness Book of World Records as the largest number ever appearing in a mathematical proof.