Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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
add comment

3 Answers

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.

share|improve this answer
1  
Also you might find this interesting: scottaaronson.com/writings/bignumbers.html –  Adrian Petrescu Mar 24 '11 at 2:19
add comment

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}}}}}$.

share|improve this answer
add comment

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.

share|improve this answer
5  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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