# What is the smallest number $n$ , such that $n\uparrow^4 n>3\uparrow^5 3$ holds?

What is the smallest number $n$, such that $$n\uparrow^4 n>3\uparrow^5 3$$ holds ?

$\uparrow$ stands for Knut's up-arrow-notation and is defined as follows

$a\uparrow b=a^b$

$$a\uparrow \uparrow b=a\uparrow a\uparrow ...\uparrow a\uparrow a$$ with $b$ $a's$

$$a\uparrow^3 b=a\uparrow\uparrow a\uparrow\uparrow...\uparrow\uparrow a\uparrow\uparrow a$$ with $b$ $a's$

$$a\uparrow^4 b=a\uparrow^3 a\uparrow^3 ...\uparrow^3 a\uparrow^3 a$$ with $b$ $a's$ and so on.

We have $$3\uparrow^5 3=3\uparrow^4 3\uparrow^3 3\uparrow\uparrow 3^{27}$$

Note, that every uparrow-expression is calculated from right to left, so we have $a\uparrow\uparrow a\uparrow\uparrow a=a\uparrow\uparrow (a\uparrow\uparrow a)$

Because of $3\uparrow^5 3=3\uparrow^4 3\uparrow^4 3$ , I guess that $n$ is approximately $3\uparrow^4 3$. Can we calculate $n$ more precisely ?

Notation : Applying Saibian's theorem , we have with $S:=3\uparrow^4 3$ :

$$(S-3)\uparrow^4 (S-3)<3\uparrow^5 3<S \uparrow^4 S$$

Proof : $(S-3)\uparrow^4 (S-3)<(3\uparrow^4 3)\uparrow^4 (S-3)<3\uparrow^4 S=3\uparrow^5 3$

The right inequality follows from $3\uparrow^5 3=3\uparrow^4 S<S\uparrow^4 S$

So, the bounds for $n$ are very sharp indeed.

• Well, we obviously have $3<n<3\uparrow^43$ – Simply Beautiful Art May 20 '16 at 23:16
• math.stackexchange.com/questions/1057302/comparing-up-arrows/… – Peter May 21 '16 at 18:47
• For $k=0,1,2,...$, let $n_k$ be the least $n$ such that $n\uparrow^k n>3\uparrow^{k+1} 3$. Then $n_0=6,n_1=12$, and finding $n_2$ would be interesting, let alone $n_3$ or your $n_4$. (I think $n_2$ would be especially interesting because it seems infeasible to find, even though it must be less than $3\uparrow\uparrow 3 = 7625597484987$.) – r.e.s. May 22 '16 at 19:06
• It would be very useful if that were done, but unfortunately I haven't the time just now -- perhaps in the near future, if no one else has done so. (Maybe the googology folks have written something?) – r.e.s. May 23 '16 at 13:54
• @r.e.s. Thank you for the verification! – Peter May 28 '16 at 14:48

In general, for $k \ge 2$ the smallest $n$ such that $n \uparrow^k n > 3 \uparrow^{k+1} 3$ is $n = (3 \uparrow^k 3) - 2$.

Set $S = 3 \uparrow^k 3$. We will prove:

Lemma: For all $0 \le i \le k$ and $j \ge 2$, $(S-2) \uparrow^i j > 3 \uparrow^i (j+2)$.

Proof by induction on $i$ and then on $j$.

Base case: $i=0$. Using the convention that $a \uparrow^0 b = ab$, we have

$$(S-2)\uparrow^0 j = (S-2)j > 6j \ge 3(j+2) = 3 \uparrow^0 (j+2)$$

Base case: We assume the lemma for $i-1$, and prove it for $i$ and $j=2$. By the inductive hypothesis, we have $(S-2) \uparrow^{i-1} (S-2) > 3 \uparrow^{i-1} S$. But then we have

$$(S-2) \uparrow^i 2 = (S-2) \uparrow^{i-1} (S-2) > 3 \uparrow^{i-1} S \ge 3 \uparrow^{i-1} (3 \uparrow^i 3) = 3 \uparrow^i 4$$

Main case: We assume the lemma for $i$ and $j$, and prove it for $i$ and $j+1$.

$$(S-2) \uparrow^i (j+1) = (S-2) \uparrow^{i-1} ((S-2) \uparrow^i j) > 3 \uparrow^{i-1} (3 \uparrow^i (j+2)) = 3 \uparrow^i (j+3)$$

and the lemma is proved.

Setting $i = k$ and $j = S-2$ gets the desired inequality. (Peter has already shown that $n = S-3$ is not sufficient.)

• You forgot the induction step for $i$ – Peter Jun 1 '16 at 11:05
• No, it's there. You can consider the second base case and the main case as the inductive step for $i$; we prove the lemma with $i$ and $j=2$ based on $i-1$, then we induct on $j$ to prove the lemma for $i$ with all $j$. – Deedlit Jun 1 '16 at 11:27
• OK, now I see. You proved it for $j=2$ and ALL $i$, right ? – Peter Jun 1 '16 at 11:32
• Yes; I tried to clarify that part. – Deedlit Jun 1 '16 at 11:33
• OK, now it is clear. So, we have $n_k=(3\uparrow^k 3)-2$ for every $k\ge 2$. Very nice indeed! – Peter Jun 1 '16 at 11:35