# Is there any pratical use to really large number mathematics (e.g. Graham's Number or Tree(3))? **URL:** \ **Category:** Factual Questions\ **Created:** [November 4, 2018, 3:18am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958 "2018-11-04T03:18:23Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [November 4, 2018, 3:18am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/1 "2018-11-04T03:18:23Z")
Watching some YouTube videos of the biggest numbers ever used in a legitimate calculation usually gets you things about Graham’s number or Tree(3) (as an example). The numbers represented in those things is beyond huge. Indeed while [Graham’s number](https://www.youtube.com/watch?v=XTeJ64KD5cg) is truly ridiculously huge [Tree(3)](https://www.youtube.com/watch?v=3P6DWAwwViU) makes Graham’s Number seem a spec. As is noted in the Graham’s number video, if you could hold that number in your head your head would literally collapse into a black hole. Tree(3) is waaaay bigger. My question is, while it is fun to think about these things, are they of any use whatsoever? Or are they just play things? The explanation of Graham’s number, while a real calculation, seems completely random and more a math puzzle than anything that is useful. Am I missing something? Is working these sorts of problems out a useful effort in advancing mathematics? ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [November 4, 2018, 3:32am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/2 "2018-11-04T03:32:42Z")
Graham’s number arose as an upper bound in a combinatorial problem, which seems eminently practical. That tree function fits into the same general theme in a sense, as it concerns counting trees (the combinatorial structures, not botanical ones). In short, these numbers arise from real mathematical investigations, not some random puzzles. ETA Wikipedia actually has a decent explanation of the history of those numbers, including links to mathematical references. ---
**Author:** ![rat\_avatar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rat_avatar/32/255_2.png) [@rat\_avatar](https://boards.straightdope.com/u/rat_avatar)\ **Post date:** [November 4, 2018, 3:56am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/3 "2018-11-04T03:56:55Z")
Kruskal’s tree theorem which I think is a parent to TREE(3) is pretty useful for functions like finding a minimum spanning tree. Here is a graph library that shows an example that it is used as this format doesn’t really let me demonstrate how to use it. [Generate edges in a minimum spanning forest of an undirected weighted graph.](https://networkx.github.io/documentation/latest/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_edges.html) Graph arborescence and pruning are pretty critical in modern systems Big-O algorithm time complexity becomes a problem. I can’t think of how to describe this but showing that a seemingly random tree’s complexity will go to zero is of huge value. Producing a tree with a minimum sum of edge weights is one way to think of it. As the common ancestor is the criteria in TREE(3) like solutions can be much faster than a DFS for a directed acyclic graph which is np-hard as an example. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [November 4, 2018, 5:50am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/4 "2018-11-04T05:50:47Z")
> [@rat\_avatar](#): > > Graph arborescence and pruning are pretty critical in modern systems Big-O algorithm time complexity becomes a problem. Hint for programmers: If your algorithm is O(TREE(n)) then you need to go back to the drawing board. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 4, 2018, 12:39pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/5 "2018-11-04T12:39:42Z")
> [@Sage\_Rat](#): > > Hint for programmers: > > If your algorithm is O(TREE(n)) then you need to go back to the drawing board. OTOH, if you have an algorithm that is O(n \* InverseTree(n)), for example, you can treat it as linear time. There are several algorithms where log\* or inverse Ackerman’s is a factor and you can treat those as constants in practice. Even log log n is going to be 7 at most. In Computer Science there are occasionally algorithms discovered where the constant factor is large-ish, in the 100s or worse, e.g., 233 n[sup]2[/sup]. But once you know it’s quadratic then typically people can find algorithms with better constants. This doesn’t apply to the particular numbers cited by the OP, but it might happen with other bounds. I wrote a paper once where I just came up with a quick and dirty very large bound for something to show that certain classes were distinct. I could have really dropped the value down if I wanted to. But since I only needed to prove such a bound existed, why bother? ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [November 4, 2018, 12:51pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/6 "2018-11-04T12:51:46Z")
> [@ftg](#): > > OTOH, if you have an algorithm that is O(n \* InverseTree(n)), for example, you can treat it as linear time. > > There are several algorithms where log\* or inverse Ackerman’s is a factor and you can treat those as constants in practice. Even log log n is going to be 7 at most. > > In Computer Science there are occasionally algorithms discovered where the constant factor is large-ish, in the 100s or worse, e.g., 233 n[sup]2[/sup]. But once you know it’s quadratic then typically people can find algorithms with better constants. > > This doesn’t apply to the particular numbers cited by the OP, but it might happen with other bounds. > > I wrote a paper once where I just came up with a quick and dirty very large bound for something to show that certain classes were distinct. I could have really dropped the value down if I wanted to. But since I only needed to prove such a bound existed, why bother? Ah, I see. 🆒 ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 4, 2018, 1:11pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/7 "2018-11-04T13:11:42Z")
Yeah, for most of these problems, the real goal is to show that something is finite. If you can find some defined number, and show that the thing you’re looking for is always smaller than that, then you’ve done that. And if finiteness is literally all you’re looking for, then you don’t need to be efficient about defining that upper bound, and an easy-to-find upper bound that’s ludicrously large is better than a hard-to-find upper bound of a reasonable size. If finiteness isn’t literally the only thing you care about, then it might be useful to have a smaller upper bound. But even in that case, the ludicrous bound is still useful, since the method you used to define that might provide a framework that subsequent researchers can use to find smaller, more practical, bounds. EDIT: Oh, and there’s a very real sense in which G or TREE(3) or whatever is actually incomprehensibly small. There are vastly more numbers larger than TREE(3) than there are numbers smaller than it. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 4, 2018, 2:49pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/8 "2018-11-04T14:49:02Z")
There’s a sort of paradox in my intuition; I wonder if it affects others. An infinity like ℵ[sub]0[/sub] doesn’t particularly bother me. P(ℵ[sub]0[/sub]) or P(P(ℵ[sub]0[/sub])) seem humdrum, boring. But TREE(3) or Graham’s number G(64) or, heaven forbid, TREE(TREE(3)) or G(G(64)), while “smaller than infinity,” just boggles the mind. The very existence of such numbers seems unsettling! ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [November 4, 2018, 3:09pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/9 "2018-11-04T15:09:16Z")
One can invent various weird “puzzles” whose solutions involve these large numbers, though that is not usually how they were originally described. For example, consider a hydra (rooted tree) with many heads (leaves of the tree). If you cut off a head directly attached to the root, it does not grow back, but if cut off a head not directly connected to the root at time n, it regenerates n copies of the part of the tree above the branch node from which the head was removed. How many steps will it take to cut off all the heads? A lot… but the point of this type of theorem is that it is a finite number. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 4, 2018, 5:24pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/10 "2018-11-04T17:24:16Z")
Yup, **septimus** , that’s quite common. Most people’s notion of “a million” is larger than their notion of “infinity”. ---
**Author:** ![k9bfriender](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/k9bfriender/32/3283_2.png) [@k9bfriender](https://boards.straightdope.com/u/k9bfriender)\ **Post date:** [November 4, 2018, 8:30pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/11 "2018-11-04T20:30:38Z")
> [@Chronos](#): > > Yup, **septimus** , that’s quite common. Most people’s notion of “a million” is larger than their notion of “infinity”. It would take me longer to count to a million than it would to know that I can’t count to infinity. A million is actually a number, infinity isn’t. In any case, what I’d love to see these numbers used for is some of these [resource management](https://boards.straightdope.com/sdmb/showthread.php?t=804615) [incremental games.](https://boards.straightdope.com/sdmb/showthread.php?t=702833) They already get up to numbers that most would consider indistinguishable from infinity. I would love to see them add some up arrow notation in the numbers, though, that’d take it to a whole new level. ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [November 4, 2018, 9:28pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/12 "2018-11-04T21:28:13Z")
> [@septimus](#): > > The very existence of such numbers seems unsettling! If you really want to pop a brain gasket watch [this video](https://www.youtube.com/watch?v=IihcNa9YAPk). It is some extra footage from the video on TREE(3) I linked in the OP (I did not know it existed when I wrote the OP hence the delay). Basically the guy talking about this talks about how long it would take to solve this problem using finite mathematics. The short version is, while it can be done in principle, it is essentially impossible. No matter how fast you worked (within literal physical limits of the universe) the universe would reset itself way before you ever managed to do it. That and the proof is too big to fit in this universe. Mathematicians have other (non-finite) means to get answers to these questions fortunately. ---
**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\ **Post date:** [November 4, 2018, 9:58pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/13 "2018-11-04T21:58:36Z")
1, 3, TREE(3) is a pretty rapidly growing function. 😃 ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [November 4, 2018, 10:02pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/14 "2018-11-04T22:02:40Z")
While watching the [follow-up video](https://youtu.be/IihcNa9YAPk?t=19) I linked just above the speaker mentions [Kruskal’s tree theorem](https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem) that TREE(n) can not be proved to be finite using finite mathematics BUT you CAN prove that TREE(n) is finite using finite mathematics as long as you give a value to (n). So, you can prove TREE(3) and TREE(4) and TREE(98234698234) are finite (in principle using finite mathematics but you cannot prove it merely saying no matter what value you use is finite. I hope I got that all right and haven’t lost anyone (watch the video…he explains it much better than I do). What I do not understand is how that works. How can it be said you cannot prove TREE(n) is finite but you CAN prove it is finite for whatever number you choose to put in place of (n)? If I can prove any value of TREE(n) is finite (using finite mathematics) then why can I not say all values of TREE(n) are, ultimately, finite? ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [November 4, 2018, 10:04pm UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/15 "2018-11-04T22:04:08Z")
> [@Lumpy](#): > > 1, 3, TREE(3) is a pretty rapidly growing function. 😃 That’s what blows my mind. TREE(1) = 1 TREE(2) = 3 TREE(3) = A number waaay bigger than the universe. Completely weird. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [November 5, 2018, 1:05am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/16 "2018-11-05T01:05:23Z")
> [@Whack-a-Mole](#): > > That’s what blows my mind. > > TREE(1) = 1 > > TREE(2) = 3 > > TREE(3) = A number waaay bigger than the universe. > > Completely weird. As **Chronos** noted, TREE(3) is just a tiny itsy-bitsy value in the greater scheme of things. Most numbers are bigger than the universe and, by the same token, I would expect that most number sequences should expand faster than TREE(n)… True? Obviously they don’t today, but most number sequences are things like i[sub]n + 1[/sub] = i[sub]n[/sub][sup]2[/sup] + 1. We’re usually choosing functions with tiny constants, which isn’t how most number sequences should be. ---
**Author:** ![Andy\_L](https://avatars.discourse-cdn.com/v4/letter/a/c67d28/32.png) [@Andy\_L](https://boards.straightdope.com/u/Andy_L)\ **Post date:** [November 5, 2018, 1:17am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/17 "2018-11-05T01:17:25Z")
> [@Sage\_Rat](#): > > As **Chronos** noted, TREE(3) is just a tiny itsy-bitsy value in the greater scheme of things. Most numbers are bigger than the universe and, by the same token, I would expect that most number sequences should expand faster than TREE(n)… True? Obviously they don’t today, but most number sequences are things like i[sub]n + 1[/sub] = i[sub]n[/sub][sup]2[/sup] + 1. We’re usually choosing functions with tiny constants, which isn’t how most number sequences should be. This reminds me of this interesting fact. If you pick a positive integer less than a googol in magnitude at random, it is almost certain that that integer will have a “9” in its base-10 representation. But for integers in the range we see on a day to day basis (say, integers less than 2000 or so), having “9” in the base-10 representation is fairly rare. TREE seems unusual to us, because it’s not much like the functions we need in daily life - but as you suggest, if we picked a function “at random” somehow out of a bigger set of possible functions than we usually imagine, TREE might seem much more typical. ---
**Author:** ![borschevsky](https://avatars.discourse-cdn.com/v4/letter/b/97f17d/32.png) [@borschevsky](https://boards.straightdope.com/u/borschevsky)\ **Post date:** [November 5, 2018, 1:30am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/18 "2018-11-05T01:30:00Z")
> [@septimus](#): > > But TREE(3) or Graham’s number G(64) or, heaven forbid, TREE(TREE(3)) or G(G(64)), while “smaller than infinity,” just boggles the mind. The very existence of such numbers seems unsettling! From the Hitchhiker’s Guide: > [@Douglas Adams](#): > > It wasn’t infinity in fact. Infinity itself looks flat and uninteresting. Looking up into the night sky is looking into infinity - distance is incomprehensible and therefore meaningless. The chamber into which the aircar emerged was anything but infinite, it was just very very very big, so big that it gave the impression of infinity far better than infinity itself. ---
**Author:** ![Whack-a-Mole](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/whack-a-mole/32/141_2.png) [@Whack-a-Mole](https://boards.straightdope.com/u/Whack-a-Mole)\ **Post date:** [November 5, 2018, 2:07am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/19 "2018-11-05T02:07:12Z")
> [@Sage\_Rat](#): > > As **Chronos** noted, TREE(3) is just a tiny itsy-bitsy value in the greater scheme of things. Most numbers are bigger than the universe and, by the same token, I would expect that most number sequences should expand faster than TREE(n)… True? Obviously they don’t today, but most number sequences are things like i[sub]n + 1[/sub] = i[sub]n[/sub][sup]2[/sup] + 1. We’re usually choosing functions with tiny constants, which isn’t how most number sequences should be. For me I think it is the amazing progression that blows my mind…1, 3, ludicrously huge. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [November 5, 2018, 3:55am UTC](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958/20 "2018-11-05T03:55:30Z")
When discussing a function rather than a single natural number, the rate of growth of the function is of theoretical and practical importance. A function that grows too fast may not be primitive recursive or even computable. As **Whack-a-Mole** notes, “finite mathematics” (ie Peano arithmetic) cannot prove that Friedman’s TREE(n) function is defined for all natural numbers, even though for any n it can prove the statement “TREE(n) is finite”. Simply trying to combine all the statements “TREE(1) is finite”, “TREE(2) is finite”, etc., obviously does not result in a finite proof. One reason such functions may be “blowing your mind” is that most familiar functions are primitive recursive, and there is a limit on how rapidly such functions can grow with n. So encountering “in the wild” a function from outside this comfort zone may seem weird. [Next page](https://boards.straightdope.com/t/is-there-any-pratical-use-to-really-large-number-mathematics-e-g-grahams-number-or-tree-3/823958.md?page=2)