Aside from the power, gamma, exponential functions are there any other very fast growing functions in (semi-) regular use?

  • 1
    Does the tangent function count? – Douglas Zare Mar 24 '11 at 2:17
  • @Douglas Zare: I would say that goes too fast. – John Smith Mar 24 '11 at 2:28
  • 1
    The question you pose is a bit vague. Here is a possible refinement: Give an example of a meromorphic function $f(x)$ with $f(x)>x$ for sufficiently large $x\in\mathbb{R}$. Moreover, $f(x)$ should not be the composition of the above elementary functions. (along with multiplication and addition, etc). – Eric Naslund Mar 24 '11 at 2:51
up vote 1 down vote accepted

It depends on what you mean by "in use"; the Busy Beaver function, which grows strictly faster than any sequence produceable by a Turing machine, is sometimes used in theoretical results in computability although only the first four terms are actually known. I'm not sure if it's the sort of thing you're looking for.

Tetration is a standard example. Consider, for example, $f(n) = 2\uparrow\uparrow n$, so f(1) = 2, f(2) = $2^2$, f(3) = $2^{2^2}$, f(4) = $2^{2^{2^2}}$, etc.

  • 6
    I was once at a talk about combinatorics, and the speaker wrote $2^{2^{2^{2^{2^{2^{n}}}}}}$, and then they stepped back, and said something to the effect of "Expressions like this scare the **** out of me..." and then calmly continued the discussion! – JavaMan Mar 24 '11 at 3:13

An upper bound in Szemerédi's regularity lemma grows pretty fast: it is "given by a $\log(1/\epsilon^5)$-level iterated exponential of $m$", and there's a lower bound by Gowers which is "a $\log(1/\epsilon)$-level iterated exponential of $m$".

Less spectacular is the upper bound in Szemerédi's theorem: $2^{2^{\delta^{-2^{2^{k+9}}}}}$.

Knuth's uparrow notation grows pretty fast. Basically, it goes as follows:

$$a\uparrow b=a^b$$

$$a\uparrow\uparrow b=a^{a^{a^{\dots}}}\bigg\}b\text{ amount of }a's$$

$$a\uparrow\uparrow\uparrow b=\underbrace{a\uparrow\uparrow(a\uparrow\uparrow (\dots(a\uparrow\uparrow a)\dots))}_{b\text{ amount of }a's}$$

etc. you get the main idea. It's use? It's a good way to represent large numbers, the most famous of which is known as Graham's number, which is the upper bound to a problem in Ramsey theory:

enter image description here

Possibly just as famous as the above, we have the Ackermann function. It's original usage was to show that not all total computable functions are primitive recursive, and it eventually built its way into things like Computability theory and computer science.

Within the realm of googology, one of the arguably most useful function is the fast growing hierarchy. It is useful because its simple and it can easily be used to rank most functions. For example, it is not only able to rank against addition, multiplication, and exponentiation, but it can easily extend further, providing non-trivial decent lower bounds to even the TREE sequence:

$$\text{TREE}(n)\ge f_{\vartheta(\Omega^\omega\omega)}(n)$$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.