# Is there a "largest function"?

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.

• You have to precise what a "function" should be. The busy-beaver function for example grows asymptotically faster than any computable function. Commented Jun 29, 2018 at 17:27
• 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. Commented Jun 29, 2018 at 17:29
• See Scott Aaronson's excellent essay, "Who Can Name the Bigger Number?" Commented Jun 29, 2018 at 17:37
• 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. Commented Jun 29, 2018 at 17:39
• 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.) Commented Jun 29, 2018 at 17:46

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.

• I remember proving this in my proofs class! Good times, for sure. Your response adheres moreso to my original line of thinking, I think. Commented Jun 29, 2018 at 17:45
• 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. Commented Jun 30, 2018 at 22:31
• @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. Commented Jul 1, 2018 at 0:49

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

• 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*} Commented Jun 29, 2018 at 19:35
• Numberphile did a video that featured hyperoperators a few years ago. Commented Jun 30, 2018 at 12:44
• 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.) Commented Jun 30, 2018 at 19:27
• @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. Commented Jun 30, 2018 at 22:55
• This doesn't answer the question at all. Commented Jul 2, 2018 at 6:47

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.

• My question is moreso about parent functions. For example, is there a parent function that grows faster than $n!$? Commented Jun 29, 2018 at 17:35
• 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. Commented Jun 29, 2018 at 17:37
• You need to define what a "parent function" is better. Commented Jun 29, 2018 at 17:47
• @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.
– DRF
Commented Jun 29, 2018 at 18:39
• @Prime, I think fleablood's comment was for you. Commented Jul 1, 2018 at 23:24

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

• The new slope is actually $2f(x)f'(x)$: it doesn't just double. Commented Jun 29, 2018 at 17:37
• Yeah, if you want to double the slope, you need to take $f(2x)$. Commented Jun 29, 2018 at 21:35
• @probably_someone Even with $g(x) = f(2x)$ we have $g'(x) = 2 f'(2x) \not = 2 f'(x)$ = doubling the slope.
– Ovi
Commented Jun 30, 2018 at 9:30
• To double the slope, all you need to do is to double the function. Commented Jun 30, 2018 at 13:30

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

• for all functions $\phi_1, \phi_2$ such that $\phi_1 \prec \phi_2$, which are there more of? Commented Jul 1, 2018 at 23:42

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.

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.

• 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. Commented Jul 7, 2018 at 2:27

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.

I'm just saying, the function that I think is the LARGEST ar aka the one that increases the value of the number is, what I invented, is Pxn("number").That kinda makes in infifnite because how it works for example if I took $$1$$, it would give me $$\pi$$, but if I take $$3$$, that means take every single number of $$\pi$$ and multiply it by $$3$$ so $$3.14"$$ would be $$6.312"$$. So there you go, bye (I wrote this and I'm 9yr old)