This link
http://googology.wikia.com/wiki/Array_notation
shows the definition of bowers linear array notation and the approximation $$\{n,a+1,b+1,c+1,d+1,...\}\ \approx f^a_{...+\omega^2d+\omega c+b}(n)$$
I think for very small entries the approximation is not very tight, so I would like to know some relatively tight bounds to understand how good the approximation is.
- How big must the entries be, such that the approximation is "well" ? Is the approximation already "well" for $$\underbrace { \{\ 3,...,3 \}\ }_n $$ ?
For 3 entry arrays the approximation is not very good. It gives $a \uparrow^c b \approx f_{c-1}^b(a)$. The actual result is closer to $a \uparrow^c b \approx f_{c}^b(a)$.
I will actually proof something this time.
Let $a<65536$.
We take $b\geq4$. Note that $f_{2}(f_2(b)) > f_{2}(16b) = 65536^b\cdot 16b > \{a,b\}$.
Therefore $f_{3}(f_3(b)) > f_{3}(2b) > f_{2}^{2b}(4) > \{a,b,2\}$.
By induction, $f_{c+1}(f_{c+1}(b)) > f_{c+1}(2b) > f_{c}^{2b}(4) > \{a,b,c\}$.
Then we have $f_{\omega}(f_{\omega}(4)) >f_{a+1}(2a) > \{a,2,1,2\}=\{a,a,a\}$.
$\{a,3,1,2\}=\{a,a,\{a,a,a\}\}<\{a,a,f_{\omega}(f_{\omega}(4))\}<f_{f_{\omega}(f_{\omega}(4))+1}(2a)<f_{f_{\omega}(f_{\omega}(f_{\omega}(4)))}(2a)<f_{f_{\omega}(f_{\omega}(f_{\omega}(4)))}(f_{\omega}(f_{\omega}(f_{\omega}(4))))=f_{\omega}(f_{\omega}(f_{\omega}(f_{\omega}(4))))$.
By induction again, $\{a,b,1,2\}<f_{\omega+1}(2b)$ for $b\geq2$.
By induction again, $\{a,b,c,2\}<f_{\omega+c}(2b)$ for $b\geq2$.
$\{a,2,1,3\}=\{a,a,a,2\}<f_{\omega+a}(2a)<f_{\omega2}(f_{\omega2}(4))$.
By triple induction, we will get $\{a,b,c,d\}<f_{\omega(d-1)+c}(2b)$.
$\{a,a,a,a\}<f_{\omega3+a}(a)<f_{\omega^2}(f_{\omega^2}(4))$
Induction, $\{a,b,1,1,2\} < f_{\omega^2+1}(b)$
Induction, $\{a,b,c,1,2\} < f_{\omega^2+c}(b)$
$\{a,2,1,2,2\}=\{a,a,a,1,2\}< f_{\omega^2+a}(a)<f_{\omega^2+\omega}(f_{\omega^2+\omega}(4))$
$\{a,b,1,2,2\} < f_{\omega^2+\omega+1}(2b)$
$\{a,b,c,d,2\} < f_{\omega^2+\omega(d-1)+c}(2b)$
$\{a,b,c,d,e\} < f_{\omega^2(e-1)+\omega(d-1)+c}(2b)$.
Now, realize that $$f_{\omega^2(e-1)+\omega(d-1)+c-1}^{2b}(a) \approx f_{\omega^2(e-1)+\omega(d-1)+c-1}^{2b}(2b) =f_{\omega^2(e-1)+\omega(d-1)+c}(2b)$$
Also note that large overestimations have been made. First expanding and then using the proper upper bound actually gives a much better bound.
In general the bound is a good bound for $n\geq3$ and the number of entries > 3.
Note that intuitively, we can replace every $2b$ with $b-1$ to get a lower bound. However we run into some problems when formally proving it. Eg. Estimating $f_3(f_3(b-1)-1)$ formally is very hard.