By Ben Blum-Smith

2011-08-10 06:13:24 8 Comments

This question has been in my mind since high school.

We can get multiplication of natural numbers by repeated addition; equivalently, if we define $f$ recursively by $f(1)=m$ and $f(n+1)=f(n)+m$, then $f(n) = m \times n$. Likewise, we get exponentiation by repeated multiplication. If $g(1)=m$ and $g(n+1)=mg(n)$, then $g(n) = m^n$. In my high school mind it was natural to imagine a new function defined by repeated exponentiation: $h(1)=m$ and $h(n+1)=m^{h(n)}$.

These definitions only make sense for $n$ a natural number, but of course there are standard very mathematically satisfying ways to define multiplication and exponentiation by any real number. My question is this:

Can the function $h$ defined above also be extended in a natural way to $\mathbb{R}^{>0}$?

The question is in the spirit of seeking an extension of $f(n)=n!$ to $\mathbb{R}$ and arriving at $\Gamma(x)$.

Let me focus the question, and attempt to make precise what I mean by "in a natural way." Take $h(1)=2$ and $h(n+1)=2^{h(n)}$. $h$ is now defined on $\mathbb{N}$, and $h(2)=4$, $h(3)=16$, $h(4)=2^{16}=65,536$ etc. Is it possible to extend the domain of definition of $h$ to all positive reals in such a way that

a) The functional equation $h(x+1)=2^{h(x)}$ continues to be satisfied for all $x$ in the domain.

b) $h$ is $C^\infty$. (Analytic would be even better but this seems maybe too much to hope for?)

c) All $h$'s derivatives are monotone.

These requirements are my attempt to codify what would count as "natural." I am open to suggestions about what would be a better list of requirements.

If such a function exists, I would like to know how to construct it; if it doesn't, I would like to know why (i.e. outline of proof), and if relaxing some of the requirements (e.g. just the first derivative monotone) would make it possible.

(If the function exists, I am also interested in the questions, "is it unique?" "Could we add some natural requirements to make it unique?" But my main query is about existence.)


@Qiaochu Yuan 2011-08-10 15:22:44

This is not an answer to your question but a long comment on its motivation. Multiplication is at least two conceptually distinct things, only one of which can reasonably be described as repeated addition:

  • The natural map $\mathbb{Z} \times A \to A$ given by $(n, a) \mapsto na$ where $A$ is an abelian group; this really is repeated addition, and is in particular bilinear.
  • The composition $\text{End}(A) \times \text{End}(A) \to \text{End}(A)$ of endomorphisms of an abelian group.

What's confusing is that these two definitions agree in familiar cases. If $A = \mathbb{Z}$ (the abelian group), repeated addition gives a natural map $\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$. On the other hand, $\text{End}(\mathbb{Z}) \cong \mathbb{Z}$ (the ring), and composition of endomorphisms gives a natural map $\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$. These happen to be the same map, but this is an illusion caused by the fact that we're looking at such a fundamental abelian group $\mathbb{Z}$.

Similarly, if $A = \mathbb{R}$ (the abelian group), repeated addition gives a natural map $\mathbb{Z} \times \mathbb{R} \to \mathbb{R}$. On the other hand, the reasonable endomorphisms of $\mathbb{R}$ form a ring isomorphic to $\mathbb{R}$ (the ring), giving a natural map $\mathbb{R} \times \mathbb{R} \to \mathbb{R}$, and the restriction to $\mathbb{Z}$ in the first factor of the second map gives the first.

But when we think of multiplication of real numbers, the first picture is misleading: in what sense is $\pi \times \pi = \pi^2$ repeated addition? Simple: it isn't. It's better conceptualized as composition of scalings of the real line (the endomorphism definition).

The endomorphism definition generalizes immediately to multiplication of complex numbers and matrix multiplication, a context where "repeated addition" doesn't even begin to capture what multiplication is all about. This is probably a big reason why people have a difficult time with complex numbers: nobody's explained to them that they're just composing rotations and scalings of the plane.

Exponentiation is at least three conceptually distinct things, only one of which can reasonably be described as repeated multiplication:

  • The natural map $\mathbb{Z} \times G \to G$ given by $(n, g) \mapsto g^n$ where $G$ is a group; this really is repeated multiplication. Note that for fixed $n$ we don't get a homomorphism in general if $G$ is non-abelian, but for fixed $g$ we get a homomorphism $\mathbb{Z} \to G$.
  • The natural map $B \to B$ given by $x \mapsto e^x = \exp(x) = \sum \frac{x^k}{k!}$ where $B$ is a topological ring and the series converges (which for example is always true in a Banach algebra). If it exists for all $x \in B$, this map is a homomorphism from the additive group of $B$ to the multiplicative group of $B$; moreover, the homomorphism $t \mapsto e^{tx}$ from $\mathbb{R}$ to $B^{\times}$ is (in nice cases) uniquely determined by the fact that its derivative at $t = 0$ (in nice cases where this exists) is $x$. In other words, this is a very, very natural map.
  • Any map that extends or is analogous to one or both of the above two maps.

The reason maps in the third category exist is because of the nice homomorphism properties that anything behaving like an exponential ought to satisfy, which we often want to imitate in other settings (e.g. the exponential map in Riemannian geometry). Thus, for example, we have an exponential $(a, x) \mapsto a^x = e^{x \log a}$ where $a$ is a positive real and $x$ is an element of a topological ring, generalizing the second definition, such that

  • $a^{x+y} = a^x a^y$ (when $x, y$ commute) and
  • $(ab)^x = a^x b^x$

and if $x$ is chosen to be a scalar multiple of the identity, we get back a special case of the first map for $G = (\mathbb{R}_{>0}, \times)$.

But I still think this is misleading. One sign is that exponentials with arbitrary bases behave quite badly once $a$ is allowed to be anything other than a positive real. The first time I tried to graph the equation

$$y = (-10)^x$$

on my calculator impressed this point on me very strongly. (Try it and see what happens.) Of course this is due to the fact that logarithms aren't well-defined in general, which, while interesting, only further emphasises the point that instead of allowing both arbitrary bases and exponents we should stick to repeated multiplication, $e^x$, and logarithms, which are the real stars of the show.

So insofar as multiplication and exponentiation are repeated addition and multiplication, at least this is sensible because addition and multiplication are associative.

Exponentiation is not associative, and it shouldn't be, because in many more general cases its two inputs are different types of things.

Therefore, there's no reason to expect repeated exponentiation to have any reasonable properties along the lines of the natural and useful homomorphism properties of multiplication and exponentiation, and as far as I know, it doesn't.

@Qiaochu Yuan 2011-08-10 15:39:37

I was going to write this up as a blog post at some point, but it might as well be here instead. See also… and… for my previous answers discussing this theme.

@Ben Blum-Smith 2011-08-10 18:32:58

+1 I love the algebraic birds-eye view you're taking with this answer (and the hope for more perspectives like this was why I hadn't accepted Zev's answer yet). But I have to stick up for the question. First, let me clarify that I don't fail to understand the reasons why we wouldn't expect things to work as smoothly for repeated exponentiation as for exponentiation and multiplication. For example it was in deference to these reasons I shied away from requiring my desired extension of $h$ to be analytic.

@Ben Blum-Smith 2011-08-10 18:59:30

Second (and speaking in part to the other answers you linked), in the setting of $\mathbb{N}$, the progression succession - addition - multiplication - exponentiation does feel natural to me. I know it doesn't to you but this seems a matter of taste and point of view. I imagine it feels natural to computer scientists in general. As a former high school teacher I can testify that (minus succession) it feels natural to high schoolers and is also very useful in helping them understand properties of exponential functions by analogy with linear functions.

@Ben Blum-Smith 2011-08-10 19:05:40

But (third), if succession - addition - multiplication - exponentiation is a natural progression in the setting of $\mathbb{N}$ then $h$ as defined above is a natural function on $\mathbb{N}$. Now enters a question I am finding myself interested in: whenever we have a "natural" function on $\mathbb{N}$, is there a "natural" extension to $\mathbb{R}$? What would such an extension have to look like? What would be the minimum information needed to characterize it uniquely? Are there multiple good candidates? (The basic inspiration here, again, is $\Gamma(x)$ extending $n!$.)

@Ben Blum-Smith 2011-08-10 19:22:37

Fourth. You seem to be coming from the point of view that the fact (for example) that the definitions of multiplication on $\mathbb{Z}$ as a) a special case of the bilinear action of $\mathbb{Z}$ on any abelian group and b) the composition of endomorphisms in $End(\mathbb{Z})$ happen to coincide is sort of an annoying confusing coincidence stemming from $\mathbb{Z}$'s fundamentalness and simplicity, almost like there isn't room in $\mathbb{Z}$ for them not to coincide. (That was admittedly a crazy sentence.)

@Qiaochu Yuan 2011-08-10 19:27:00

@Ben: your last comment describes my attitude almost exactly. There is very little room for them not to coincide given that they are both bilinear and act as the identity when fed $1 \in \mathbb{Z} \subseteq \text{End}(A)$. The fact that they do is fine for dealing with the integers but very misleading once you get to the complex numbers, as I mentioned above.

@Qiaochu Yuan 2011-08-10 19:28:13

@Ben: as for your third comment, I don't know. The factorial is deceptively easy to define but makes its appearance in mathematics in several fundamental, nontrivial ways (Taylor series, the sizes of the symmetric groups, various probability distributions). The same is probably not true of an arbitrary "natural" function on $\mathbb{N}$.

@Ben Blum-Smith 2011-08-10 19:38:55

But couldn't you also view this overlap between two more general notions in the special setting of $\mathbb{Z}$ as interesting and illuminating? Might there not be some useful insight in thinking about this interplay? Similarly, the original question could be seen as really being about the interplay between viewing $\mathbb{N}$ as the indexing set for an iterative process and viewing it as a subset of $\mathbb{R}$. Don't you think this is interesting to think about?

@Ben Blum-Smith 2011-08-10 19:58:36

@QiaochuYuan let us continue this discussion in chat

@Doug Spoonwood 2011-09-15 18:50:45

It doesn't work out that "repeated addition" qualifies as a binary function in general. Multiplication does qualify as a binary function. Those together suffice to indicate that multiplication is not repeated addition, even for the cases you've mentioned that you claim where multiplication really is repeated addition.

@ziggurism 2017-10-31 15:01:28

I like this answer, but isn't the ending a little anticlimactic? Can we not give a stronger answer for why the apparently unrelated operations $\mathbb{Z}\times A\to A$ and $\text{End}(A)\times \text{End}(A)\to \text{End}(A)$ coincide, more than "it's just a coincidence"? When I see an operation with no business being commutative turn out commutative, I start looking around for Eckmann and Hilton to give an explanation ...

@ziggurism 2017-10-31 15:01:35

Perhaps it would go something like this. In a copowered category $C$, we have copowers of arrows $m\cdot f\colon S\cdot X \to T\cdot Y$, where $S,T$ are sets (or whatever our category is enriched in). A priori, composition of arrows and copowers of arrows are different operations. But composition of arrows satisfies the exchange law $(m\cdot f)\circ(n\cdot g)=(m\circ n)\cdot(f\cdot g)$. If $C$ were a category with one object, composition would become a binary operation and Eckmann-Hilton would apply...

@ziggurism 2017-10-31 15:02:12

Instead, consider that inside $C$ lives an image of Set, generated either as $1$, $1+1$, ... or else as objects of the form $S\cdot 1$ for any set $S$, and the category of sets is well-pointed (1 is a generator). Call this image subcategory $\mathbb{N}\subseteq C$. On this subcategory, copower of arrows can be identified with cartesian product of arrows. And cartesian product is symmetric (obvious?). Eckmann-Hilton dictates that composition and product coincide on the subcategory spanned by 1, hence also on all of $\mathbb{N}$ (this step is hazy)...

@ziggurism 2017-10-31 15:02:21

Now to decategorify: viewing ring as a category with one object, its two operations (multiplication by integers = repeated addition, and ring multiplication) coincide and are commutative on the characteristic subring because muliplication of integers is commutative, and because of Eckmann-Hilton. The two kinds of multiplication are unrelated, except when restricted to characteristic subring, where they must coincide by Eckmann-Hilton. What do you think?

@ziggurism 2017-10-31 18:09:49

On second thought, my proposal as stated doesn't make much sense. A ring, viewed as a category with one object, doesn't have a terminal object, and the inclusion of its characteristic subring is not due to any generating object.

@Travis Bemrose 2019-02-07 14:42:30

GREAT input. I think it could benefit from a small addition at the beginning, addressing the comment in the accepted answer and explaining that these are the reasons why math research has focused on things other than tetration - it's not the natural/useful thing in most cases.

@Zev Chonoles 2011-08-10 06:21:30

What you're after is called tetration (the example you computed is given here), and it has an active community of people who are interested in it (though my sense is that it is not quite in the mainstream of mathematics research at the moment, for whatever reason). The Wikipedia page indicates that the problem of extending tetration to arbitrary real powers in a sufficiently regular/smooth way is still not satisfactorily solved, so I'm afraid I don't know the answer to your question about the existence of such a function $h(x)$.

Tetration is further generalized by Knuth's up-arrow notation, and then generalized even more by Conway's chained arrow notation.

@Zev Chonoles 2011-08-10 14:52:44

Why the downvote?

@Ross Millikan 2011-08-10 15:31:06

I don't understand the downvote. It seems a reasonable and helpful answer. Supplying the proper term (here tetration) can give OP the entry needed to find information-I have been on the receiving end and appreciate it greatly.

@Ben Blum-Smith 2011-08-10 17:22:59

I also don't understand the downvote. I find the answer extremely helpful. I didn't mark the question answered yet only because I hope to get more perspectives.

@Ben Blum-Smith 2011-08-10 21:25:41

Perhaps Qiaochu's answer offers some illumination about why it's not more mainstream...

Related Questions

Sponsored Content

0 Answered Questions

How do I find the properties of this function?

  • 2018-06-21 11:05:02
  • Hariharan
  • 45 View
  • 0 Score
  • 0 Answer
  • Tags:   functions

3 Answered Questions

[SOLVED] Is there a function for every possible line?

1 Answered Questions

3 Answered Questions

4 Answered Questions

[SOLVED] Codomain of a function

3 Answered Questions

0 Answered Questions

Domain of $x^{m/n}$?

3 Answered Questions

0 Answered Questions

Order of Recursion?

6 Answered Questions

[SOLVED] Function Notation

Sponsored Content