16
$\begingroup$

In one of my classes, the professor asked about what we think the largest function was. Many thought perhaps ${e^x}^{e^x}$, but I thought about $n!$

When I talk about a "largest function", I mean the function that increases the quickest.

The professor asked about a function larger than $n!$ to which I responded, $2n!$

Although snarky in nature, it is technically true.

So my question is this:

What is the "largest function" if we define "largest" as being "increases the quickest". A parent function is what we need, as it prevents someone like myself from putting a larger coefficient before the function.

|cite|improve this question
$\endgroup$
  • 21
    $\begingroup$ You have to precise what a "function" should be. The busy-beaver function for example grows asymptotically faster than any computable function. $\endgroup$ – Peter Jun 29 '18 at 17:27
  • 11
    $\begingroup$ If you take the functions $2^x,2^{(2^x)},2^{(2^{(2^x)})},\cdots$ you get a sequence of functions such that every function grows much faster than the previous one, not only somewhat faster. $\endgroup$ – Peter Jun 29 '18 at 17:29
  • 17
    $\begingroup$ See Scott Aaronson's excellent essay, "Who Can Name the Bigger Number?" $\endgroup$ – Jair Taylor Jun 29 '18 at 17:37
  • 7
    $\begingroup$ You should rule out the "obvious responses" with a more careful definition of a growth rate. Study en.wikipedia.org/wiki/Fast-growing_hierarchy to understand how this is meant. $\endgroup$ – Peter Jun 29 '18 at 17:39
  • 14
    $\begingroup$ I'm a little surprised (well a lot surprised) a professor teaching this level of class would ask a naive question like this and expect his students not to be too sophisticated for it. At least you have the decency to recognize you need "parent" functions or classes of functions to have this answerable without the utterly obvious $2f'(x)>f'(x)$. But you need to have the concept of "parent" function much more precisely defined to have this question worth discussion. (The busy-beaver function is probably the most relevant comment on this thread.) $\endgroup$ – fleablood Jun 29 '18 at 17:46
33
$\begingroup$

Look into hyperoperators.

https://en.wikipedia.org/wiki/Hyperoperation

This is a sequence of binary operators, each generating larger numbers than the previous. Define $f_n(x) = n \uparrow^n x$. You now have an infinite sequence of functions, each one in the sequence grows faster than the previous one. And they will grow MUCH faster than $n!$.

|cite|improve this answer
$\endgroup$
  • 20
    $\begingroup$ To give you an idea how how big this gets: $$\begin{align*}f_1(2) & = 1 \\ f_2(2) & = 4 \\ f_3(2) & = 3^{27} \\ f_4(2) & = \text{Wolframalpha cannot calculate how many digits this value has}\end{align*}$$ $\endgroup$ – InterstellarProbe Jun 29 '18 at 19:35
  • 5
    $\begingroup$ Numberphile did a video that featured hyperoperators a few years ago. $\endgroup$ – Denis de Bernardy Jun 30 '18 at 12:44
  • 9
    $\begingroup$ While this is true, this only demonstrates the existence of an infinite sequence of "larger" functions, rather than proving the nonexistence of a "largest" function. (You might think it's obvious how to extend this to a proof that there is no "largest" function, but proving the same thing without bringing in hyperoperators is about as obvious.) $\endgroup$ – user2357112 supports Monica Jun 30 '18 at 19:27
  • $\begingroup$ @user2357112 other users had already discussed theoretical functions that are "larger" than anything computable and that there is no "largest" function. But, the OP was specifically asking for an example of what such a function might look like. Enter hyperoperators. They can be used to produce functions that grow much faster than $n!$, which is specifically what the OP sought. $\endgroup$ – InterstellarProbe Jun 30 '18 at 22:55
  • $\begingroup$ This doesn't answer the question at all. $\endgroup$ – Don Hatch Jul 2 '18 at 6:47
37
$\begingroup$

There are many large functions, e.g. $e^n$, $n!$ etc.

And you might know that $e^n$ grows faster than $n^k$ for any $k\geq 1$.

But there are other interesting functions, e.g. the Busy Beaver function. It asymtotically grows faster than any computable function. That means you cannot even write a computer program that produces a faster growing function.

The nice thing is: The busy beaver function is well-defined, but not computable:)! This function really gives an upper bound for the growth of computable functions (e.g., it grows much faster than any function that just contains hyperoperators or the TREE function).

edit: Of course, there are more and even faster growing functions.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I remember proving this in my proofs class! Good times, for sure. Your response adheres moreso to my original line of thinking, I think. $\endgroup$ – Prime Jun 29 '18 at 17:45
  • $\begingroup$ Your answer got me thinking that there must even exist functions which grow faster than all well-defined functions. However when trying to prove it I started wondering whether "well-defined" is well-defined. $\endgroup$ – kasperd Jun 30 '18 at 22:31
  • $\begingroup$ @kasperd: You can't complete such a proof, because you might be living in a pointwise definable model of set theory where ervery function is well-defined. $\endgroup$ – Henning Makholm Jul 1 '18 at 0:49
31
$\begingroup$

There is none. Given any function from $\mathbb R$ to $\mathbb R$, it is not hard to construct another function that grows faster than it.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ My question is moreso about parent functions. For example, is there a parent function that grows faster than $n!$? $\endgroup$ – Prime Jun 29 '18 at 17:35
  • 4
    $\begingroup$ Indeed, given a countably infinite set of functions from $\mathbb R$ to $\mathbb R$ one can define another function that grows faster than any function in the set, where "grows faster" can be interpreted as eventually greater than, or as differences approach infinity, or as ratio to any in the set approaches infinity, or as ratio of logarithm to the logarithm of any in the set approaches infinity --- pretty much any manner of pointwise comparison of your choosing. $\endgroup$ – Dave L. Renfro Jun 29 '18 at 17:37
  • 26
    $\begingroup$ You need to define what a "parent function" is better. $\endgroup$ – fleablood Jun 29 '18 at 17:47
  • 1
    $\begingroup$ @SincerelyPrime In regard to Dave's comment there a number of cardinal invariants of the continuum which deal with "the largest function" in some way. $\mathfrak {d}$ and $\mathfrak{b}$ come to mind. See en.wikipedia.org/wiki/Cardinal_characteristic_of_the_continuum for more information. $\endgroup$ – DRF Jun 29 '18 at 18:39
  • $\begingroup$ @Prime, I think fleablood's comment was for you. $\endgroup$ – grovkin Jul 1 '18 at 23:24
11
$\begingroup$

There is no largest function, any more than there is a largest number. Take the largest function you can think of, call its slope $f'(x)$. Now double that function - you have doubled your slope to $2f'(x)$.

|cite|improve this answer
$\endgroup$
  • 7
    $\begingroup$ The new slope is actually $2f(x)f'(x)$: it doesn't just double. $\endgroup$ – Randall Jun 29 '18 at 17:37
  • 3
    $\begingroup$ Yeah, if you want to double the slope, you need to take $f(2x)$. $\endgroup$ – probably_someone Jun 29 '18 at 21:35
  • 4
    $\begingroup$ @probably_someone Even with $g(x) = f(2x)$ we have $g'(x) = 2 f'(2x) \not = 2 f'(x)$ = doubling the slope. $\endgroup$ – Ovi Jun 30 '18 at 9:30
  • 11
    $\begingroup$ To double the slope, all you need to do is to double the function. $\endgroup$ – Eric Duminil Jun 30 '18 at 13:30
4
$\begingroup$

Take a look at Hardy's translation and edition of Du Bois-Reymond's Orders of Infinity, page 10:

enter image description here

|cite|improve this answer
$\endgroup$
  • $\begingroup$ for all functions $\phi_1, \phi_2$ such that $\phi_1 \prec \phi_2$, which are there more of? $\endgroup$ – Mitch Jul 1 '18 at 23:42
4
$\begingroup$

Given a sequence of functions $f_i:\mathbb N \to \mathbb N$, let $f_\infty:\mathbb N \to \mathbb N$ be defined by $$f_\infty(n) = 1+\max\{f_1(n),f_2(n),\dotsc,f_n(n)\}$$ $f_\infty$ is eventually greater than any function in the sequence $f_i$.

Alternatively we can define $f_\infty$ by $$f_\infty(n)=1+\sum_{i=1}^nf_i(n)$$ This type of argument is called a diagonal argument.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

I remember that this one gets mighty big mighty fast: https://en.wikipedia.org/wiki/Ackermann_function

However whatever function you claim is the biggest, I can beat it by squaring it.

It is like trying to name the smallest positive number. Whatever number you claim is smallest, I can cut in half.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Well, referring to a smallest positive number, what you said is only true for $\mathbb{R}$ ... this is obvious. And squaring a function is simply the square of that function...I am speaking about largest parent functions which I will define a little bit later with a largely requested edit. $\endgroup$ – Prime Jul 7 '18 at 2:27
0
$\begingroup$

There is no 'largest' function, as one can always add, multiply, or exponentiate again to produce a larger one, there are some that get very large, very quickly. For example, the Ackermann function $A(x, y)$, which is defined as follows (for $x, y \geq 0$): $$ A(x,y) = \left\{ \begin{array}{ll1} x + 1 & \text{if }y=0 \\ A(x-1,1)&\text{if }x>0, y=0\\ A(x-1,A(x,y-1))&\text{if }x,y>0 \end{array} \right. $$ Powered by a recursive definition, this function grows astonishingly fast. For example, while $A(1, 1) = 3$ and $A(2, 2) = 7$, $A(3, 3) = 61$, $A(4, 4)$ is: $$2^{2^{2^{65536}}} - 3$$ and will overload most computers (to give an idea of scale, a computer with a 128 bit processor can handle numbers with about $40$ digits, and this is many, many times larger than that). And while this is an astoundingly large function, there are infinitely larger ones.

|cite|improve this answer
$\endgroup$

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.