18
$\begingroup$

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

$\endgroup$
0

5 Answers 5

34
$\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$
9
  • $\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
    Commented Nov 21, 2013 at 16:26
  • $\begingroup$ @Frank: my answer gives a continuous one, and it would not be difficult to smooth the kinks $\endgroup$
    – Henry
    Commented Nov 21, 2013 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
    Commented Nov 21, 2013 at 16:29
  • $\begingroup$ Thanks, this is a useful reference. $\endgroup$
    – Frank
    Commented Nov 21, 2013 at 16:33
  • $\begingroup$ @Frank: smoothing the kinks was easier than I expected. $\endgroup$
    – Henry
    Commented Nov 21, 2013 at 16:35
28
$\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$
7
  • $\begingroup$ @Frank It seems like a reasonable answer to me... $\endgroup$
    – fluffy
    Commented Nov 21, 2013 at 21:42
  • $\begingroup$ 1/n is decreasing. I think the OP wants an increasing function. $\endgroup$ Commented Oct 1, 2015 at 18:29
  • $\begingroup$ @martycohen The answer mentions that already. $\endgroup$ Commented Oct 1, 2015 at 18:35
  • 1
    $\begingroup$ @7yl4r Iterated function. I've seen it called "iter" before. I just called it nest for the sake of the pun. $\endgroup$ Commented Dec 27, 2016 at 18:37
  • 1
    $\begingroup$ The play on words is hilarious! (+1!) $\endgroup$ Commented Mar 10, 2017 at 19:19
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$
4
  • $\begingroup$ This assumes, of course, that "$BB(n)$ doesn't count as a formula. $\endgroup$ Commented Nov 21, 2013 at 16:51
  • $\begingroup$ What about g(x)=f(x)/2 $\endgroup$ Commented Nov 21, 2013 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$ Commented Nov 22, 2013 at 1:47
  • $\begingroup$ The inverse Ackermann function is frequently cited in these contexts. $\endgroup$
    – MJD
    Commented Nov 12, 2014 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$
2
  • $\begingroup$ excellent - thanks! $\endgroup$
    – Frank
    Commented Nov 21, 2013 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$ Commented Nov 21, 2013 at 21:27
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Does this function tent toward infinity at all though? An explanation would be nice. $\endgroup$ Commented Nov 22, 2013 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$ Commented Nov 22, 2013 at 9:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .