8

For each $n$, define $f_n:\mathbb R^+\rightarrow \mathbb R^+$ by $f_n(x) = \underbrace{x^{x^{x^{...^{x^x}}}}}_n$

I want to find a function $f:\mathbb R^+\rightarrow \mathbb R^+$ such that for any given $n$, $f$ is eventually greater than $f_n$.

Here $\mathbb R^+$ means the non-negative reals.

Cameron Buie
  • 102,994
Adam Rubinson
  • 20,052
  • Note that $\underbrace{x^{x^{x^\dots}}}_n=^n!!x$ – JSCB Sep 05 '12 at 13:10
  • see also http://en.wikipedia.org/wiki/Tetration and note that andres answer is like tetration of a number with itself, kind of like how squaring is multiplication of a number with itself – binn Sep 05 '12 at 13:14

1 Answers1

19

To make notation smoother, write $f(n,x)$ for $f_n(x)$. Let $$f(x)=f(\lceil x\rceil, x).$$ Here $\lceil x\rceil$ is the "ceiling" function that gives the smallest integer $\ge x$.

Remark: This is a typical "diagonalization" argument. Basically the same idea seems to have been first used by du Bois-Reymond to deal with orders of growth of functions. He did it a few years before Cantor used diagonalization in Set Theory.

André Nicolas
  • 507,029
  • 1
    I don't get it. What is the function? I am looking for one functions that works for all n. – Adam Rubinson Sep 05 '12 at 12:55
  • 2
    I don't follow, what is $f(x,x)$? – fretty Sep 05 '12 at 12:56
  • @fretty: I was having TeX trouble typing the ceiling function. Finally got the notation right. – André Nicolas Sep 05 '12 at 12:58
  • It looks like your function depends on n, which is not allowed. – Adam Rubinson Sep 05 '12 at 13:00
  • 2
    @AdamRubinson: It does not depend on $n$. It is given explicitly in terms of $x$. – André Nicolas Sep 05 '12 at 13:01
  • 3
    @AdamRubinson: No, the function does not depend on $n$. (It is defined in terms of the $f_n$s, but the function itself is independent of $n$. For instance, for $10 \le x \le 11$, we have $g(x) = f_{10}(x)$, and for $20 \le x \le 21$, we have $g(x) = f_{20}(x)$, etc. But the function $g$ does not depend on $n$.) – ShreevatsaR Sep 05 '12 at 13:03
  • 1
    @AdamRubinson: This is a function of $x$ and eventually does get bigger than each $f_n$. For a particular $n$ just plug in any $x > n$. – fretty Sep 05 '12 at 13:05
  • 3
    @AdamRubinson: Here is a similar problem: find a function that eventually grows faster than any $x^n$. Solution: Let $g(x)=x^{\lceil x\rceil}$. Exactly the same idea. – André Nicolas Sep 05 '12 at 13:08
  • 1
    BTW, $g(x) = f_{\lceil x \rceil}(x)$ (typed as g(x) = f_{\lceil x \rceil}(x)) renders fine, just in case you wanted to keep the original notation and were forced to change it just for TeX reasons. :) – ShreevatsaR Sep 05 '12 at 14:19
  • @ShreevatsaR: I think "flat" notation is more readable, at least on my fairly small-screened computer. – André Nicolas Sep 05 '12 at 14:25
  • Oh I see. Nice answer I suppose. Obviously it can be extended in the same way indefinitely – Adam Rubinson Sep 05 '12 at 16:04
  • 1
    Correct me if I'm wrong but I think this f is discontinuous. e.g. f(4) = 4^4^4^4, but f(4.01) = 4.01^4.01^4.01^4.01^4.01.

    If I sneakily/annoyingly add in the extra condition that f is continuous.... well, does such an f exist?

     – Adam Rubinson Sep 05 '12 at 16:13
  • @ Andre, thought about that a while ago and f(x) = x^x will do. And my function is cts and so a bit nicer – Adam Rubinson Sep 05 '12 at 16:15
  • 2
    @AdamRubinson: To solve the problem of majorizing the $x^n$, the familiar $e^x$ will do. I was just using the $x^{\lceil x\rceil}$ to illustrate the idea of the main proof in a simpler setting. – André Nicolas Sep 05 '12 at 16:21
  • @Andre fair play. If you want to majorize c^x where c>0, then my example function x^x is perhaps more appropriate. Edit: but then again, (x/d)^x will also work for any d>0. – Adam Rubinson Sep 05 '12 at 16:24
  • Related: I am trying to somehow classify "rates of convergence" with stuff like "Big Oh" convergence in mind (because I find it interesting). For example, I am considering infinite polynomials i.e. g(x) = a_0 + a_1 x + a_2 x^2 + ... such that g(x) = +infinity for all x>0. If someone can point me in the direction of any interesting sources, that would be greatly appreciated. – Adam Rubinson Sep 05 '12 at 16:35
  • 2
    @AdamRubinson: to answer the original problem with a continuous function, you can use the following approach. First define the function just on integers, using a diagonalisation like André’s: $g(n) = f_n(n)$. Then to define it on non-integer reals just “connect the dots”: that is, for $x \in (n,n+1)$, let $t = x - n \in (0,1)$, and set $g(x) = (1-t) g(n) + t g(n+1)$. Exercise: extending this idea, can you find a solution which is also differentiable? – Peter LeFanu Lumsdaine Sep 05 '12 at 16:35
  • 1
    @AdamRubinson: what you call infinite polynomials are generally known as formal power series, so searching on that name may give some leads on your question about finding ones that diverge for all positive values of $x$. – Peter LeFanu Lumsdaine Sep 05 '12 at 16:38
  • Thanks Peter for your responses.

    I can get a continuous f and I haven't tried, but from a few diagrams and a bit of intuition, I think I can also a differentiable f quite easily using your method.

    But using your method, I think (but might be wrong) we must have d^2y/dx^2 > 0 for some x. This isn't nice. Can we consider Andre's function but only the points n + 1/2 where n is an integer. Then do some kind of finite Lagrange interpolation for the first n points and take the limit as n goes to infinity and we should get a formal power series? I might try this one later...

     – Adam Rubinson Sep 06 '12 at 13:11
  • oh... and I fogot to mention... hopefully we can prove that our function / power series has d^2y/dx^2 < 0 for all x > 0. Also, hopefully our power series can be written concisely – Adam Rubinson Sep 06 '12 at 13:14