1

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.

Jyrki Lahtonen
  • 133,153
Peter
  • 84,454
  • 2
    Well, we obviously have $3<n<3\uparrow^43$ – Simply Beautiful Art May 20 '16 at 23:16
  • http://math.stackexchange.com/questions/1057302/comparing-up-arrows/1306412#1306412 – Peter May 21 '16 at 18:47
  • The lemma that $a\uparrow^b c$ is strictly increasing in every argument (assuming a>1) is false for $a=c=2$. Can I prove the lemmas and the theorem in an easier way ? – Peter May 21 '16 at 19:06
  • 1
    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
  • @r.e.s. If you approve Saibian's theorem (See the link), then you have very sharp bounds for your number $n_k$ : Set $S:=3\uparrow^k 3$ and $T:=3\uparrow^{k+1} 3=3\uparrow^k S$. Applying Saibian's theorem gives $$(S-3)\uparrow^k (S-3)<S\uparrow^k(S-3)<(3\uparrow^k 3)\uparrow^k(S-3)<3\uparrow^kS=T<S\uparrow^k S$$ for $k\ge 2$ – Peter May 23 '16 at 08:41
  • @r.e.s. How do you define $a\uparrow^0 b$ to get $n_0=6$ ? I guess $a\uparrow^0 b=ab$ – Peter May 23 '16 at 08:48
  • Yes, by definition, $a\uparrow^0b = a\cdot b$ (multiplication). Bounds are nice, but finding the exact number would be more interesting. – r.e.s. May 23 '16 at 13:17
  • Yes, $3$ possible values remain. Maybe I find some possibilitiy to find the right one. – Peter May 23 '16 at 13:25
  • @r.e.s. I tried to follow Saibian's proof but I could not follow it completely. Would you mind to read his paper and verify the proof of the theorem and the lemma's ? The linked question has a link to his paper. – Peter May 23 '16 at 13:31
  • 1
    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. We have $n_2=3^{27}-2$ because of (claim) $n_2\uparrow\uparrow n_2>3\uparrow\uparrow\uparrow 3$ Proof : Let $S:=3^{27}$. Then, $(S-2)^{(S-2)}>3^{3^{27}}$ (This can be shown with logarithms) , therefore we have $(S-2)\uparrow\uparrow 2>3\uparrow\uparrow 4$. With induction, it follows $(S-2)\uparrow\uparrow k>3\uparrow\uparrow(k+2)$ for $k\ge 2$. The claim follows by setting $k=S-2$. – Peter May 24 '16 at 22:59
  • Well done! (I verified all of your steps.) – r.e.s. May 25 '16 at 02:16
  • FWIW, I just read Saibian's paper. In the proof of Saibian's theorem and its three supporting lemmas, I didn't spot any potential problems except for minor typographical errors (some "$=$"s that should be "$<$"s) and minor undefined notation ($b@(x)#n$ evidently means $b@[email protected]@(x)$ with $n\ b$s). – r.e.s. May 28 '16 at 03:46
  • 1
    @r.e.s. Thank you for the verification! – Peter May 28 '16 at 14:48

1 Answers1

3

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

Deedlit
  • 7,062