15
$\begingroup$

Is there any nonconstant function that grows at infinity slower than all iterations of the (natural) logarithm?

$\endgroup$
27
$\begingroup$

Yes, just take a function which is equal to $\log x$ on an initial interval such as $[1,K_1]$, then equal to $\log\log x$ on the interval $(K_1,K_2]$, then $\log\log\log x$ etc. where the values $K_1, K_2, \dots$ are chosen sufficiently large to ensure that the function really does tend to infinity. This can always be done, since each of the iterations of the log function does tend to infinity.

This function will not be continuous, but a similar function could certainly be created which is continuous.

This will produce a function which tends to infinity slower than any (fixed) iteration of $\log$. If you want something even slower, then call my function above $\phi (x)$, and repeat my construction using $\phi\phi(x)$ etc on successive intervals.

If this is still not slow enough, then ...

$\endgroup$
  • $\begingroup$ I suspect a smooth one could be created, and maybe G. H. Hardy's old book "Orders of Infinity" might be worth a look. $\endgroup$ – Old John Nov 21 '13 at 16:26
  • $\begingroup$ @Frank: my answer gives a continuous one, and it would not be difficult to smooth the kinks $\endgroup$ – Henry Nov 21 '13 at 16:27
  • $\begingroup$ @Frank Hardy's book is available (legally) here on Gutenberg, and although a bit old-fashioned (like me) it is still worth a read. $\endgroup$ – Old John Nov 21 '13 at 16:29
  • $\begingroup$ Thanks, this is a useful reference. $\endgroup$ – Frank Nov 21 '13 at 16:33
  • $\begingroup$ @Frank: smoothing the kinks was easier than I expected. $\endgroup$ – Henry Nov 21 '13 at 16:35
21
$\begingroup$

Let $\text{LogNestMonster}_i(n) = nest(log, i)(n) = \overbrace{log(log(...(log}^\text{i times}(n))...))$.

Many functions grow slower than $\text{LogNestMonster}_i$, no matter how large the $i$ you picked is:

  1. The inverse Ackermann function $\alpha$ grows slower than all $\text{LogNestMonster}$s. It (roughly) tells you how far in the sequence $1+1$, $2 \cdot 2$, $3^3$, $4\uparrow\uparrow4$, $5\uparrow\uparrow\uparrow5$, $...$ you have to go before exceeding $n$.

  2. The iterated logarithm $log^*$ also grows slower than all $\text{LogNestMonster}$s. It counts how many times you have to apply log to $n$ before the result is less than $1$.

  3. Also, consider the function $\frac{1}{n}$. It is not constant and is clearly asymptotically less than all $\text{LogNestMonster}$s, although I'm guessing it's not exactly what you had in mind since $\frac{1}{n}$ is $O(1)$ despite not being $\Theta(1)$.

$\endgroup$
  • $\begingroup$ @Frank It seems like a reasonable answer to me... $\endgroup$ – fluffy Nov 21 '13 at 21:42
  • $\begingroup$ 1/n is decreasing. I think the OP wants an increasing function. $\endgroup$ – marty cohen Oct 1 '15 at 18:29
  • $\begingroup$ @martycohen The answer mentions that already. $\endgroup$ – Craig Gidney Oct 1 '15 at 18:35
  • $\begingroup$ I haven't seen the nest function before and I'm interested in learning more. It's a bit hard to search for though, can you point me in the direction of any resources that talk about nest from a mathematical point of view? $\endgroup$ – 7yl4r Dec 27 '16 at 17:30
  • 1
    $\begingroup$ @7yl4r Iterated function. I've seen it called "iter" before. I just called it nest for the sake of the pun. $\endgroup$ – Craig Gidney Dec 27 '16 at 18:37
13
$\begingroup$

In fact there are functions that go to $\infty$ more slowly than any function you can write down a formula for. For positive integers $n$ let $f(BB(n)) = n$ where $BB$ is the Busy Beaver function. Extend to $[1,\infty)$ by interpolation.

EDIT: Stated more technically, a "function you can write down a formula for" is a recursive function: it can be computed by a Turing machine. $BB(n)$ is not recursive, and grows faster than any recursive function. If $g(n)$ is a recursive (integer-valued, for simplicity), nondecreasing function with $\lim_{n \to \infty} g(n) = \infty$, then there is a recursive function $h$ such that for all positive integers $n$, $g(h(n)) > n^2$. Namely, here is an algorithm for calculating $h(n)$ for any positive integer $n$: start at $y = 1$ and increment $y$ until $g(y) > n^2$, then output $y$.

Now since $BB$ grows faster than any recursive function, for sufficiently large $n$ (say $n \ge N$) we have $BB(n) > h(n+1)$. For any integer $x \ge h(N)$, there is $n \ge N$ such that $h(n) \le x < h(n+1)$, and then (since $f$ and $g$ are nondecreasing) $$f(x) \le f(h(n+1)) \le f(BB(n)) = n < \sqrt{g(h(n)} \le \sqrt{g(x)}$$ and thus $$\dfrac{f(x)}{g(x)} \le \dfrac{1}{\sqrt{g(x)}} \to 0\ \text{as} \ x \to \infty $$

$\endgroup$
  • $\begingroup$ This assumes, of course, that "$BB(n)$ doesn't count as a formula. $\endgroup$ – Andreas Blass Nov 21 '13 at 16:51
  • $\begingroup$ What about g(x)=f(x)/2 $\endgroup$ – Bulwersator Nov 21 '13 at 22:05
  • $\begingroup$ @Bulwersator They both have the exact same growth rate at $\infty$. A function $g(x)$ has a smaller growth rate than $f(x)$ at $\infty$ iff $$\lim_{x\to\infty}{\frac{g(x)}{f(x)}} = 0$$ or alternately: $$\lim_{x\to\infty}{\frac{f(x)}{g(x)}} = \infty$$. $\endgroup$ – AJMansfield Nov 22 '13 at 1:47
  • $\begingroup$ The inverse Ackermann function is frequently cited in these contexts. $\endgroup$ – MJD Nov 12 '14 at 4:42
7
$\begingroup$

Yes:

My favorite big-number function from positive numbers to positive numbers, a continuous variant of Old John's.

Write $log_{10}^{(n)} x$ for the $n$th iterated base 10 logarithm of $x$.

If $log_{10}^{(n)} x \in [0,1)$ then let $f(x)=n+log_{10}^{(n)} x$.

You can extend this to non-positive numbers with $f(0)=0$ and $f(-x)=-f(x)$ giving a continuous bijective function on the reals.

If you want a smooth function take natural logarithms base $e$ instead

$\endgroup$
  • $\begingroup$ excellent - thanks! $\endgroup$ – Frank Nov 21 '13 at 16:27
  • $\begingroup$ Note that a version of this function - 'how many iterations of log does it take to reduce $x$ to $\lt 1$?' - shows up regularly in the analysis of algorithms; see en.wikipedia.org/wiki/Iterated_logarithm for details. $\endgroup$ – Steven Stadnicki Nov 21 '13 at 21:27
2
$\begingroup$

Try the following: $$f(x):=\min\{n\geq1\>|\> \log^{\circ n}(x)<0\}\ .$$

$\endgroup$
  • $\begingroup$ Does this function tent toward infinity at all though? An explanation would be nice. $\endgroup$ – AJMansfield Nov 22 '13 at 1:55
  • $\begingroup$ @AJMansfield: It's more or less the inverse of $x_0:=0$, $x_{n+1}:=e^{x_n}$ $\>(n\geq0)$. $\endgroup$ – Christian Blatter Nov 22 '13 at 9:14

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.