Undergrad Why is Graham's number a factor of 3?

[BWV]

Grahams Number, the largest number used in a mathematical proof (so large you can't even comprehend how $&%ing big it is), is a factor of 3 (I.e. g1= 3^^^^3 using the ^ for the Knuth up-arrow notation and grahams number = g64 where each step from g1 to 64 the number of arrows is iterated from the previous number, so g1 is incomprehensible and g2 has g1 number of ^'s and so on)

the number is the upper bound to the problem:

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?

 

[jedishrfu]

Here’s a fascinating discussion of Graham’s number although I couldn’t find why exactly it’s based on 3:

https://waitbutwhy.com/2014/11/1000000-grahams-number.html

Looking at the problem and it’s 4 coplanar vertices, it seems it’s most likely related to the 3 ways these four vertices can be connected. As an example, given vertices A,B,C,D then the connections would be AB,AC,AD but this is only a guess. It could also be related to the spaces divided up by these vertices like a tetrahedron projected onto a plane with one vertex in the center then connecting lines divide up the plane into 3 regions.

 

[BWV]

That is a great link - its where I learned what little I know about it.

 

[pinball1970]

That is a great link - its where I learned what little I know about it.

I made the mistake of catching numberphile on this googling it then watching More you tube posts then finally physics forums.

I have been trying to get my head round it ever since

Grahams number is insane, just picturing the structure is insane, 3|||3 makes a googolplex look small. I would like to know how they know now Tree(3) is so much bigger.
Not much on the net I can grasp

 

[jedishrfu]

You might find something useful in the Quora discussion:

https://www.quora.com/Is-Tree-3-bigger-than-Graham’s-number

There's a set of videos referenced in the post but like the number itself may take a long time to view and reflect upon before you feel you've found an answer to your question.

Popular Mechanics article on it:

https://www.popularmechanics.com/science/math/a28725/number-tree3/

Alternatively, this video below attempt to answer the question in 10 minutes:



and this Numberphile video:

 

[BWV]

Ok so what about G(Tree(3)) vs Tree(G64)?

 

[jedishrfu]

This might be conjectured by analogy:

We consider two functions $f(x) = x^2$ versus $g(x) = e^x$ and then ask $f(g(x)) <?> g(f(x))$ if so then:

Is there a theorem that encapsulates the notion of function growth which in our case g(x) >> f(x) as x gets very large does that imply g(f(x)) will grow much faster than f(g(x))?​

Using DESMOS, it seems that $g(f(x)) = e^{x^2}$ grows faster than $f(g(x) = (e^x)^2$ which upon rewriting f(g(x)) = e^{2x} and noting that $x^2$ grows much faster than $2x$

so that would imply that given $TREE(3) >> G(64)$ then $TREE(G64)$ grow much faster than $G(TREE(3))$

Perhaps @Mark44 or @fresh_42 can comment here.

 

[Mark44]

My only comment is that the thread title is misleading: "Why is Graham's number a factor of 3?"

Since 3 is a prime, its only integer factors are itself and 1. A better thread title would be "Why is Graham's number a power of 3?

 

[pinball1970]

Ok so what about G(Tree(3)) vs Tree(G64)?

That's cheating ha ha! I think the fact these enormous numbers have been used in proofs and the fact they are finite makes them interesting.
Also the way the arrow notation escalates so wildly after only a couple of terms.
The comparisons of what some the numbers could represent and the fact Grahams leaves physical reality pretty quickly is mind boggling.

 

[jedishrfu]

As an aside, I guess if we consider TREE(n) and Grahams number G(64) mind-boggling what would we consider Graham's cracker more so?

https://www.snopes.com/fact-check/graham-cracker-origins/

 

[pinball1970]

You might find something useful in the Quora discussion:

https://www.quora.com/Is-Tree-3-bigger-than-Graham’s-number

There's a set of videos referenced in the post but like the number itself may take a long time to view and reflect upon before you feel you've found an answer to your question.

Popular Mechanics article on it:

https://www.popularmechanics.com/science/math/a28725/number-tree3/

Alternatively, this video below attempt to answer the question in 10 minutes:



and this Numberphile video:

Thanks

Understanding is not the right word but at least this has given me a glimpse of how fast these beasts can grow.

 

[pinball1970]

My only comment is that the thread title is misleading: "Why is Graham's number a factor of 3?"

Since 3 is a prime, its only integer factors are itself and 1. A better thread title would be "Why is Graham's number a power of 3?

Why is it 3? 4 seems to make more sense, sides and vertices.

 

[jedishrfu]

Most likely 1 and 2 were trivial but 3 produced interesting math results.

Also 4 is a multiple of 2 and so may not have been interesting enough.