Fast-growing functions revisited

There have been many exciting results proved by members of the Googology wiki, a website concerned with fast-growing functions. Some of the highlights include:

  • Wythagoras’s construction of an 18-state Turing machine which takes more than Graham’s number of steps to terminate.
  • LittlePeng9’s construction of a Turing machine which simulates the Buchholz hydra, showing that ‘BB(160,7)>>most of defined computable numbers’.

Recently, however, there have been claims that several of the results on cp4space pertaining to fast-growing functions have never been proved. For the record, here are the original (hitherto unpublished) proofs with all of the missing details filled in such that they are no longer ‘exercises for the reader’:

Theorem 1: TREE(3) > f^5(8), where f(n) := tree^n(7)

lowerbound

To prove this (see here for definitions), it is sufficient to exhibit a sequence of trees whose nodes are each coloured red, green, or blue, such that there is no colour-preserving embedding of an earlier tree into a later tree. We begin the sequence as follows:

first20

The first tree is a single red node, and we henceforth have no red nodes in any of the later trees. The twelfth tree, T12, and all subsequent trees have a single green root node connected to:

  • n branches containing a single blue node attached to a single green leaf;
  • m branches containing a single blue leaf;
  • one or more green trees.

Trees T1 through to T11 can be seen to not embed into any tree of this form, so it remains to define the sequence {T12, ….} and show that none of these trees embeds into any later tree.

The sequence begins as follows:

T1 {}
T2 [[]]
T3 [()()]
T4 [((()))]
T5 ([(())][])
T6 ([(())](()))
T7 ([(())]()()())
T8 ([(())]()())
T9 ([(())]())
T10 ([(())])
T11 [(())]
T12 ([()][()][()][()][()][])
T13 ([()][()][()][()][()](()))
T14 ([()][()][()][()][()]()()())
T15 ([()][()][()][()][()]()())
T16 ([()][()][()][()][()]())
T17 ([()][()][()][()][()])
T18 ([()][()][()][()][][][][][][][][][])
T19 ([()][()][()][()][][][][][][][][](()))
T20 ([()][()][()][()][][][][][][][][]()()())
T21 ([()][()][()][()][][][][][][][][]()())
T22 ([()][()][()][()][][][][][][][][]())
T23 ([()][()][()][()][][][][][][][][])
T24 ([()][()][()][()][][][][][][][]X7)

where X7 is any (monochromatically green) tree on 7 vertices. This can be followed by the sequence:

T25 ([()][()][()][()][][][][][][][]X8)
T26 ([()][()][()][()][][][][][][][]X9)
T27 ([()][()][()][()][][][][][][][]X10)
...
T_(23 + tree(7)) ([()][()][()][()][][][][][][][]())

where X7, X8, X9, X10, … () is a maximal-length sequence for tree(7). If any earlier tree here embeds into a later tree, then the same must have been true in the maximal-length sequence for tree(7), contradicting the definition.

Consequently, we’ve already proved that TREE(3) > tree(7). We can then extend the sequence further by ‘burning’ another blue node (pair of square brackets):

T_(24 + tree(7)) ([()][()][()][()][][][][][][][])
T_(25 + tree(7)) ([()][()][()][()][][][][][][]Y1)

where Y1 is the first tree in the maximal-length sequence for tree(tree(7)). We proceed in the same way as before with a sequence of tree(tree(7)) terms, culminating in:

T_(23 + tree(7) + tree(tree(7))) ([()][()][()][()][][][][][][]())
T_(24 + tree(7) + tree(tree(7))) ([()][()][()][()][][][][][][])
T_(25 + tree(7) + tree(tree(7))) ([()][()][()][()][][][][][]Y2)

where Y2 is the first tree in the maximal-length sequence for tree(tree(tree(7))). Repeating this process, we eventually reach the tree:

([()][()][()][()])

at time 24 + tree(7) + tree(tree(7)) + … + tree^8(7). We can then make the next tree in our process have the form:

([()][()][()][][][][][]...[]X7)

where we have created tree^8(7) new blue nodes by ‘burning’ a branch of the form [()]. The same argument as before allows us to reach the tree:

([()][()][()])

at time well beyond tree^(tree^8(7))(7). Repeating this outer iteration another three times gets us to the claimed bound.

To see that no tree embeds homeomorphically into a later tree, we note that if T precedes T’, then we have at least one of the following:

  • T contains more copies of [()] than T’;
  • T contains more copies of [] than T’;
  • The monochromatic green subtree of T precedes (in some tree(k) sequence) the monochromatic green subtree of T’;

where the latter condition was ensured by using a sequence for tree(k) which has this property by definition.

Theorem 2: tree(n) outgrows f_alpha(n) for every alpha preceding the small Veblen ordinal

This is implied by the statement in Harvey Friedman’s e-mails to the FOM mailing list:

One of our many finite forms of Kruskal's theorem asserts that

for all k, TREE[k] exists.

This function eventually dominates every provably recursive
function of the system ACA_0 + Pi12-BI.

and this is elaborated upon in Deedlit’s excellent MathOverflow answer.

Theorem 3: SSCG(4n + 3) >= SCG(n)

Conveniently, someone had e-mailed me to ask for an explicit proof of this statement, so I’ll include the reply I sent:

Suppose you have a sequence of N = SCG(n) (not necessarily simple)
subcubic graphs, (G_1, ..., G_N), such that G_i has at most i + n
vertices and no graph is a minor of a later graph.

Now, we let H_i be obtained from G_i by replacing each vertex with
a copy of the 4-vertex 3-edge Y-shaped graph, K3,1. For each pair
of adjacent vertices in the original graph, we join two as-yet-unused
'limbs' of the corresponding Y-shapes in the new graph. Then H_i is
simple and subcubic, and we can show that no graph is a minor of a
later graph. This is most easily shown by the fact that for subcubic
graphs, 'minor' is equivalent to 'topological minor', so it suffices
to show that no graph is homeomorphically embeddable into a later
graph. (Proof: if H_i embeds into H_j, the degree-3 vertices of H_i
must map to degree-3 vertices of H_j; this induces a homeomorphic
embedding from G_i to G_j.)

At this point we're almost done. The graphs (H_1, H_2, H_3, ...)
have at most (4n + 4, 4n + 8, 4n + 12, ...) vertices, respectively.
To prove the claim, we actually want a sequence with at most
(4n + 4, 4n + 5, 4n + 6, ...).

Now, since G_1 contains at least 2 vertices, it must contain at
least 1 edge which is not a self-loop (otherwise, every vertex has
degree <= 2 and we can add another edge, producing a more optimal
initial graph G_0, contradicting the assumption that our original
sequence of graphs is maximal). Consequently, H_1 contains a path
of vertices of degrees (3, 2, 2, 3). Let H_1' be the graph obtained
by contracting this path once, and H_1'' be the graph obtained by
contracting it again. Then the graphs (H_1, H_1', H_1'', H_2, H_3,
...) have the property that no graph is a minor of a later graph.

Hence, we can construct the sequence which begins:

- H_1 with at most 4n + 4 vertices;
- (H_1' + K_2) with at most 4n + 5 vertices;
- (H_1' + K_1 + K_1) with at most 4n + 6 vertices;
- (H_1' + K_1) with at most 4n + 7 vertices;
- H_1' with at most 4n + 8 vertices;
- (H_1'' + C_7) with at most 4n + 9 vertices;
- (H_1'' + C_6) with at most 4n + 10 vertices;
- (H_1'' + C_5) with at most 4n + 11 vertices;

where + denotes disjoint union of graphs. At this point, we've
'bought ourselves enough vertices' to continue the sequence as
follows:

- (H_2 + K_1 + K_1 + K_1 + K_1) with at most 4n + 12 vertices;
- (H_2 + K_1 + K_1 + K_1) with at most 4n + 13 vertices;
- (H_2 + K_1 + K_1) with at most 4n + 14 vertices;
- (H_2 + K_1) with at most 4n + 15 vertices;

- (H_3 + K_1 + K_1 + K_1 + K_1) with at most 4n + 16 vertices;
- (H_3 + K_1 + K_1 + K_1) with at most 4n + 17 vertices;
- (H_3 + K_1 + K_1) with at most 4n + 18 vertices;
- (H_3 + K_1) with at most 4n + 19 vertices;

and so forth. The property of no graph being a minor of a later
graph can easily be seen to be true, because at each iteration
we either have:

 - the 'big component' (the union of connected components which
contain at least one degree-3 vertex) gets strictly smaller (in
the poset of graphs under the minorship relation);
 - or the 'big component' stays identical and the 'small
component' gets strictly smaller;

and any homeomorphic embedding of one graph into another must map
the big component of the first graph into the big component of the
other graph.

I'm sure that there's enough slack in this proof to improve the
upper bound to SSCG(4n + 2) (by starting with H_1' instead of H_1),
but this proof suffices to show the claimed statement.

Theorem 4: SSCG(3) > TREE^(TREE^2(3))(3)

Again, we want to exhibit a sequence for SSCG(3) which exceeds TREE^(TREE^2(3))(3). We can begin as follows:

first17

All subsequent graphs are the disjoint union of:

  • p copies of the double-square with leaves attached to two diametrically opposite degree-2 vertices;
  • q copies of the double-square with leaves attached to two degree-2 vertices which are neither adjacent nor diametrically opposite;
  • r copies of the double-square with a single leaf;
  • s copies of the double-square;
  • a graph T which does not contain the double-square as a graph minor.

For example, the last graph in the above sequence is (1, 0, 0, 1, Ø), where Ø is the graph with no vertices or edges.

We define a sequence such that if the graph (p, q, r, s, T) precedes the graph (p’, q’, r’, s’, T’) in the sequence we define, then we have one of the following:

  • p > p’;
  • p = p’ and q > q’;
  • (p, q) = (p’, q’) and r > r’;
  • (p, q, r) = (p’, q’, r’) and s > s’;
  • (p, q, r, s) = (p’, q’, r’, s’) and T is not a graph minor of T’.

With this convenient notation, we can write down some more terms of the sequence:

G18 (1, 0, 0, 0, 15-cycle)
G19 (1, 0, 0, 0, 14-cycle)
...
G29 (1, 0, 0, 0, square)
G30 (1, 0, 0, 0, triangle = H1)
G31 (1, 0, 0, 0, H2)
G32 (1, 0, 0, 0, H3)
...
G(2^(3 × 2^95) + 20) (1, 0, 0, 0, isolated_vertex)
G(2^(3 × 2^95) + 21) (1, 0, 0, 0, Ø)

where H1, H2, H3, … is the sequence of length 2^(3 × 2^95) − 9 that provides a lower bound for SSCG(2).

We can encode a rooted ordered coloured tree as a graph using the construction described here; this graph satisfies the properties required of T. The long initial segment of length 2^(3 × 2^95) + 21 means that we can use lots of vertices in the next step:

G(2^(3 × 2^95) + 22) (0, 2^(2^96), 0, 0, T1)

where T1 is the encoding of the first tree in a maximal-length sequence of rooted coloured trees for TREE(3). The ‘shrinking counter’ mechanism allows us to obtain a sequence of (l+7) TREE(3) graphs (none of which is a minor of any later graph) culminating in:

G(2^(3 × 2^95) + 22 + (l+7) TREE(3)) (0, 2^(2^96), 0, 0, Ø)
G(2^(3 × 2^95) + 23 + (l+7) TREE(3)) (0, 2^(2^96)-1, TREE(3), 0, U1)

where U1 is the encoding of the first tree in a maximal-length sequence of rooted coloured trees for TREE^2(3). At the end of the graph sequence corresponding to this tree sequence, we have the graph represented by the 5-tuple:

(0, 2^(2^96)-1, TREE(3), 0, Ø)

which can then be followed by:

(0, 2^(2^96)-1, TREE(3)-1, TREE^2(3), V1)

where V1 is the encoding of the first tree in a maximal-length sequence of rooted coloured trees for TREE^3(3). We can continue to repeat this same argument a total of TREE^2(3) times, decrementing the penultimate element of this 5-tuple each time, with the final iteration exceeding TREE^(TREE^2(3))(3) steps before we reach:

(0, 2^(2^96)-1, TREE(3)-1, 0, Ø)

This already proves what we set out to show, but it is clear that the iteration can go much further.

This entry was posted in Fast-growing functions. Bookmark the permalink.

7 Responses to Fast-growing functions revisited

  1. Catisfluffy says:

    One of the complaints on the Googology Wiki is that comparisons with the fast-growing hierarchy are essentially meaningless unless you specify a sufficiently large system of fundamental sequences. For example, if omega[n]=BB(n), then f_omega is uncomputable. Although Friedman did make a system of fundamental sequences up to that level, it’s noticeably different from “standard” systems and as such it’s somewhat misleading to claim any comparison with “the fast-growing hierarchy”.

  2. devrim turker says:

    https://inst.eecs.berkeley.edu/~cs61bl/r//cur/trees/fibonacci-tree.html?topic=lab15.topic&step=7&course=

    19:49’’24e’ 24 Tem 2020 Cum tarihinde, Complex Projective 4-Space şunu yazdı: #yiv2859772575 a:hover {color:red;}#yiv2859772575 a {text-decoration:none;color:#0088cc;}#yiv2859772575 a.yiv2859772575primaryactionlink:link, #yiv2859772575 a.yiv2859772575primaryactionlink:visited {background-color:#2585B2;color:#fff;}#yiv2859772575 a.yiv2859772575primaryactionlink:hover, #yiv2859772575 a.yiv2859772575primaryactionlink:active {background-color:#11729E !important;color:#fff !important;}#yiv2859772575 WordPress.com | apgoucher posted: “There have been many exciting results proved by members of the Googology wiki, a website concerned with fast-growing functions. Some of the highlights include: Wythagoras’s construction of an 18-state Turing machine which takes more than Graham’s number” | |

  3. I think the illustration for T17 is missing. The illustrations jump from T16 to T18. The explanation is clear, though.

  4. If I am understanding things correctly, tree(7) is 30 (the maximal-length sequence constructed from the 11 monochromatic tree structures with at most 7 nodes). And tree(tree(7)) would be computed similarly, except it would be the maximal-length sequence derived from all trees of at least 30 nodes, meaning we have to evaluate the possibilities that derive from https://oeis.org/A000055 [30+1] cases. And so on.

  5. This reply should supersede my two prior replies. Feel free to delete them if you wish.

    If I’m understanding tree(7) correctly, the maximal length sequence constructed from the 11 monochromatic tree structures (see https://oeis.org/A000055) with at most 7 nodes might look like this:

    (()()()()()())
    (()()()()())()
    (()()()()())
    (()()())(()())
    ()()(()())()()
    (()()())()()()
    (()()())()()
    (()()())()
    (()())(()(()))
    (()())()(()())
    (()())(()())
    ((())(())(()))
    ((()))(()(()))
    (())(()(()))
    (()())(((())))
    (()())((()))
    (()())(())
    (()())() isomorphic to (()()())
    ()()()()()()() isomorphic to ((((((())))))) and many others
    ()()()()()() ditto (((((())))))
    ()()()()() ditto ((((()))))
    ()()()() ditto (((())))
    ()()() ditto ((()))
    ()() ditto (())
    ()

    There are 25 such, so tree(7) is 25. tree(tree(7)) would thus be tree(25), which would require us to figure out the maximal length sequence constructed from the 104636890 possible shapes (again, see https://oeis.org/A000055). And so on. The graph of A000055 shows basically exponential growth, so tree^8(7) is essentially an 8-fold exponentiation of tree(7) and f5(8) is a 5-level tower operation of tree of tree^8(7).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s