1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Well, we obviously have $3<n<3\uparrow^43$ $\endgroup$ – Simply Beautiful Art May 20 '16 at 23:16
  • $\begingroup$ math.stackexchange.com/questions/1057302/comparing-up-arrows/… $\endgroup$ – Peter May 21 '16 at 18:47
  • 1
    $\begingroup$ 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$.) $\endgroup$ – r.e.s. May 22 '16 at 19:06
  • 1
    $\begingroup$ 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?) $\endgroup$ – r.e.s. May 23 '16 at 13:54
  • 1
    $\begingroup$ @r.e.s. Thank you for the verification! $\endgroup$ – Peter May 28 '16 at 14:48
3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ You forgot the induction step for $i$ $\endgroup$ – Peter Jun 1 '16 at 11:05
  • $\begingroup$ 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$. $\endgroup$ – Deedlit Jun 1 '16 at 11:27
  • $\begingroup$ OK, now I see. You proved it for $j=2$ and ALL $i$, right ? $\endgroup$ – Peter Jun 1 '16 at 11:32
  • $\begingroup$ Yes; I tried to clarify that part. $\endgroup$ – Deedlit Jun 1 '16 at 11:33
  • $\begingroup$ OK, now it is clear. So, we have $n_k=(3\uparrow^k 3)-2$ for every $k\ge 2$. Very nice indeed! $\endgroup$ – Peter Jun 1 '16 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.