1
$\begingroup$

There are a variety of ways to define large numbers (https://en.wikipedia.org/wiki/Large_numbers), such as Graham's number, TREE(3), Rayo's number, etc. Often times we know the relative size of these numbers, e.g. TREE(3) > Grahams number.

I am interested in examples where it is unknown which of two large numbers is larger. In particular do we have examples where

  1. Both numbers are very simple to define
  2. Both numbers are computable with a known algorithm (I'm not interested in cases where we can't tell which number is larger because we don't know it's value, such as the Busy Beaver numbers)
  3. Both numbers are mathematically interesting outside of their use answering this question
$\endgroup$

1 Answer 1

5
$\begingroup$

Given a natural number $n$, a Laver table is an ordered pair of the set $\{1,\ldots,2^n\}$ and a binary operator $\star_n$ on the set $\{1,\ldots,2^n\}$ satisfying certain conditions. There is only one Laver table on $\{1,\ldots,2^n\}$ for any given natural $n$, and this unique table is often denoted $A_n$. The first row, i.e. the sequence $(1\star_n k)_{1\leq k\leq 2^n}$, is periodic, and its period is always a power of two. For example, the first row of the table $A_3$ has period $4$, the first row of $A_4$ has period $4$, and the first row of $A_5$ has period $8$. The period of $A_n$'s first row as a function of $n$ is sequence A098820 on OEIS, and starts:

1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, ...

Under the assumption of the existence of an I3 rank-into-rank cardinal, a strong large cardinal axiom not provable in $\mathrm{ZFC}$ set theory, Dougherty showed that $32$ eventually appears in this sequence, and that the index of its first appearance (soemtimes called $q(5)$, as $2^5=32$) is larger than $A_9(A_8(A_8(254)))$, where $A$ is the Ackermann function. It is currently unknown if this lower bound can be improved. This number is computable with an algorithm, by writing an algorithm that enumerates the Laver tables in increasing size and halts when finding one whose first row has period $32$.

Since this lower bound is less than Graham's number, it is unknown if $q(5)$ is larger than Graham's number. I argue that these numbers have independent interest outside of this question, since Graham's number is an upper bound in a Ramsey theory problem and is one of the most well-known examples of a large integer, whereas Laver tables were derived from result on research on large cardinals.

Edit 2025: There is now a preprint "Notes on Laver Tables" by R. Qi, maybe proposition 2 here resolves the question. (I am not familiar enough with the ordinals $\kappa^m_n$ to know if parts 1 and 2 of proposition 2 can be combined to get $F(4)$ greater than Graham's number, or how $f$ works to understand $2^{f(p_{init},1)}$.)

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.