# What does this notation mean: $\lg^{\ast} n = \min \{ i \ge 0 \,:\, \lg^i n \le 1 \}$?

For my algorithms course I am studying the definition of the iterated logarithm function (and functional iteration in general) and I don't quite understand the set notation used (it's been quite a few years since I last looked at set notation). Could someone please explain this definition?

$$\lg^{\ast} n = \min \{ i \ge 0 \,:\, \lg^i n \le 1 \} .$$

-
It simply means ‘the least non-negative $i$ such that the $i$-fold iterated logarithm of $n$ is at most $1$.’ What precisely about the notation is causing you trouble? – Zhen Lin Sep 23 '11 at 0:50

The notation defines $\lg^*(n)$ as the minimum element of the set $\{ i\ge 0\mid \lg^i(n) \le 1 \}$

The set $\{ i\ge 0\mid \lg^i(n) \le 1 \}$ (which can be notated either with a colon or a vertical bar, purely down to author preferences) is the set of all $i\ge 0$ such that $\lg^i(n)\le 1$. Strictly speaking the notation ought to say which set we pull the $i$'s from, but in this case we can guess that it's probably the integers -- otherwise the rest of the expression would not make sense.

$\lg^i(n)$ is the $\lg$ function iterated $i$ times and applied to $n$. For example, $\lg^5(25)$ means $\lg(\lg(\lg(\lg(\lg(25)))))$.

$\lg$ is a logarithm. It doesn't say exactly which base it has, but in algorithmics the tradition is to use base-2 logarithms unless something else is stated explicitly, so we can assume that is the case.

Thus, $\lg^*(n)$ is the number of times we need to take successive base-2 logarithms of $n$ before we reach a number less than $1$. This is a very slow-growing function; let's compute $\lg^*(10^9)$:

$$\lg(10^9)=28.9$$ $$\lg^2(10^9)=\lg(28.9)=4.8$$ $$\lg^3(10^9)=\lg(4.8)=2.3$$ $$\lg^4(10^9)=\lg(2.3)=1.2$$ $$\lg^5(10^9)=\lg(1.2)=0.26$$ so $\lg^*(10^9)=5$. This is in practice the maximum value for $\lg^*$ -- it only becomes 6 for $n>2^{65536}$, which is so much larger than, say, the number of atoms in the known universe that it isn't even funny.

-
+1 Nice answer. Somewhat confusingly, the notation $\lg x$ is the ISO standard for $\log_{10} x$. :) I haven't come across this base-10 usage though. – Srivatsan Sep 23 '11 at 2:16
In every case I can ever recall seeing, $\lg x$ meant a base-$2$ logarithm, and $\ln x$ meant natural log. The ambiguous one is $\log x$ (without subscript) which sometimes meant $\log_{10} x$ and sometimes $\log_e x.$ – David K Oct 11 '14 at 9:50
@DavidK: In computer science it is not uncommon to write $\log x$ to mean $\log_2 x$ too. – Henning Makholm Oct 11 '14 at 13:11

So, the thing in braces is a set. The things on the left of the colon define a set by themselves, and then the things on the right of the colon define a restriction that makes a subset. In this case, the set you start out with is all numbers (presumably integers) greater than or equal to 0, and the restriction is that a number i from this range is in your set if, when the lg function is iterated i times on your argument n, you get a value less than or equal to 1. The "min" means in this case the smallest integer in this set. So this is a fancy way of saying "the smallest number such that when you iterate the lg function that many times you get a result less than 1."

-

In this context I would expect $\lg^i$ to mean taking the logarithm $i$ times. For example $\lg^3 x$ would mean $\lg(\lg(\lg(x)))$.

So $\lg^*$ means count the number of times you need to take the logarithm until you reach 1 or less.

If $\lg$ is $\log_{10}$ then

• $\lg^* n =0$ when $n \le 1$
• $\lg^* n =1$ when $1 \lt n \le 10$
• $\lg^* n =2$ when $10 \lt n \le 10^{10}$
• $\lg^* n =3$ when $10^{10} \lt n \le 10^{10^{10}}$ etc.
-