17
$\begingroup$

Are there some natural contexts in which a double exponential occurs, $x$ to the ($y$ to the $z$): $$ x ^ {(y ^ z)} \;, \textrm{or} \;, a ^ {(b ^ c)} \; \textrm{?} $$ Of course one can contrive many problems that ask computational questions concerning towers of exponents, possibly challenging problems. And in my own area of research, $2^{n^2}$ is not uncommon; EXP is exponential-time $O( 2^ {n^k} )$. Generalized chess falls in this class.

I am more seeking some context in which such a (limited) tower occurs naturally and would be understood and appreciated by high-school or early-college students.

$\endgroup$
1
  • 2
    $\begingroup$ The power set is a pretty natural thing to think about. I find that my discrete math students find calculating the cardinality of the power set to be a satisfying puzzle (trivial to us, but not to a high school / early college student). Then the power set of the power set gives an example. Not sure if it would qualify as "natural". $\endgroup$ – Steven Gubkin Mar 19 at 12:43

11 Answers 11

27
$\begingroup$

If your students have learned some statistics, then you could point out that the normal distribution's probability density function uses this double exponential.

$$f(x)=\frac{1}{\sigma\sqrt{2\pi}}\exp\left(-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2\right)$$

$\endgroup$
3
  • 3
    $\begingroup$ That's just a polynomial; the 2 is a constant. Though it's not clear to me if polynomial in exponent is what OP's after rather than 2^e^x. $\endgroup$ – Joshua Mar 19 at 17:13
  • 4
    $\begingroup$ @Joshua: I'm just seeking a tower, so $e^{x^2}$ does indeed answer my question. $\endgroup$ – Joseph O'Rourke Mar 19 at 22:19
  • $\begingroup$ @JosephO'Rourke: OK but that makes the question a lot less interesting, and of course it can just be written without a tower as $e^{xx}$. $\endgroup$ – R.. GitHub STOP HELPING ICE Mar 21 at 16:59
12
$\begingroup$

Count all possible functions mapping $i$ input bits to $o$ output bits: For each of the $2^i$ input combinations, each output has two possible outputs ($0$ and $1$), i.e. you have $2^{2^i}$, leading to a total of $2^{o\cdot 2^i}$ binary functions. And course if you're working with $n$ different values per input/output instead of binary you end up with $n^{o\cdot n^i}$ functions.

$\endgroup$
2
  • $\begingroup$ \$i\$ might not be the best number to use here... I initially thought you were talking about imaginary exponents, which is probably a bit much for high school students. $\endgroup$ – Hearth Mar 21 at 4:51
  • $\begingroup$ @Hearth Good point 😅 I was trying to avoid a subscript-feast à la $n_v^{n_o\cdot n_v^{n_i}}$... $\endgroup$ – Tobias Kienzler Mar 21 at 18:30
8
$\begingroup$

The number of undirected graphs of order $n$ is $2^{n \choose 2} = 2^{(n^2-n)/2}$ (e.g. consider the adjacency vector as a binary-encoded number). You can describe this in terms of the number of different arrangements in which $n$ classmates can be friends. This also has the benefit of being easy to enumerate for small numbers.

$\endgroup$
4
$\begingroup$

If $S$ represents the set of $n$ students of a school, then $\mathscr P(S)$ is the set of rosters for all possible clubs that that school could host (if we assume that any two clubs with exactly the same set of students merged their interests into a single club charter). In that same scenario, the yearbook that printed pictures of all of the clubs would be a member of $\mathscr P(\mathscr P(S))$. Thus, there would be $2^{2^n}$ possible yearbooks based on the different numbers and arrangements of clubs the students could form.

$\endgroup$
4
$\begingroup$

Gompertz model was created in 1825 to study human mortality curves. From the 1920's, it was used in economic fields, and from there it was also used in Biology to study cells and microorganisms, such as microbes, growth of tumours, and survival of cancer patients. The model is described by the differential equation $$\dfrac{dN}{dt} = rN \ln \left(\dfrac{K}{N} \right),$$ and in the context of growth of tumours, $N=N(t)$ is the number of cells at time $t$, and $K$ is a positive constant related to the maximum possible size of the tumour.

The general solution for the model reads $N(t)= Ke^{-Ce^{rt}}$, where $C$ is a constant related to the initial condition $N(0)$.

References: https://doi.org/10.1371/journal.pone.0178691

$\endgroup$
3
$\begingroup$

It is easy to square a number. So instead of computing $\exp(z)$ you can compute $\exp(z/2^k)^{2^k}$ for some suitably large positive integer $k$. This is a very simple way of accelerating the convergence of the Taylor series for $\exp$, also known as "argument reduction". The double-exponential is important here because it allows you to get the $2^k$-th power using just $k$ squarings; the technique will not work without perfect powers.

$\endgroup$
0
3
$\begingroup$

What a nice collection of answers!

I am inclined to use $\lfloor A^{3^n} \rfloor$ where $A$ is Mill's constant, $$A \approx 1.3063778838630806904686144926 \;, $$ just because it is astounding that this evaluates to a prime for every $n \in \mathbb{N}$: $$ 2, 11, 1361, 2521008887, \ldots \;. $$ See A051254. But really, @JoelReyesNoche's answer is best.

$\endgroup$
1
  • $\begingroup$ It should be stated that the provided value depends on RH. $\endgroup$ – Pedro A Mar 22 at 4:40
3
$\begingroup$

The maximum of a large number of independent, identically distributed random variables -- e.g., the highest flood observed over a long period -- has an extreme value distribution. One common case is the Gumbel distribution, whose cdf has the double-exponential form $e^{-e^{-x}}$.

$\endgroup$
2
$\begingroup$

Inspired by your example, I like the number of matrices, tensors, binary or n-ary relations over a specified set (where the domain and range of such a relation need not match), such as asking about colorings using $k$ colors of a $n \times n$ board. Continuous or "non-combinatorial" applications feel hard to come up with, perhaps due to dimensionless exponential constraints, but might also exist?

$\endgroup$
2
$\begingroup$

I think there are really two different ways that this can occur. (1) You can have people writing math in real-world contexts where it makes sense to use a notation that is this type of tower of exponents. (2) You can have a function of $x$ that blows up like $a^{b^x}$ or $a^{x^b}$ as $x\rightarrow\infty$.

I'm a physicist, and the contexts where I see #1 are generally things having to do with statistical physics. For example, I can have $10^{23}$ atoms in a box, and I can ask what is the probability that if I check at a certain time, all the atoms will be on the left side. This will be $2^{-10^{23}}$. Similar examples are things like the time scale for a white dwarf to spontaneously decay into a black hole by quantum tunneling, or probabilities involving Boltzmann brains.

$\endgroup$
1
$\begingroup$

Let n be given and consider the set of logical formulas with $n$ variables. Two formulas are equivalent if they are both true, or both false, for any assignment of truth values to the variables. For example, the formulas $\lnot a\land b$ and $\lnot(a\lor\lnot b)$ are equivalent, because both are true only when $a$ is false and $b$ is true. This naturally partitions the family of formulas into classes, with two formulas in the same class if they are equivalent.

How many classes are there? The answer is

$$2^{2^n}.$$

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