# 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/1793555/what-is-the-smallest-number-n-such-that-n-uparrow4-n3-uparrow5-3-holds", "fetch_time": 1561543941000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-26/segments/1560628000266.39/warc/CC-MAIN-20190626094111-20190626120111-00546.warc.gz", "warc_record_offset": 511128909, "warc_record_length": 37450, "token_count": 1548, "char_count": 3848, "score": 4.46875, "int_score": 4, "crawl": "CC-MAIN-2019-26", "snapshot_type": "latest", "language": "en", "language_score": 0.7778403162956238, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00004-of-00064.parquet"}