8
$\begingroup$

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.

  • 0
    Note that $\underbrace{x^{x^{x^\dots}}}_n=^n\!\!x$2012-09-05
  • 0
    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 itself2012-09-05

1 Answers 1

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.

  • 1
    I don't get it. What is the function? I am looking for one functions that works for all n.2012-09-05
  • 2
    I don't follow, what is $f(x,x)$?2012-09-05
  • 0
    @fretty: I was having TeX trouble typing the ceiling function. Finally got the notation right.2012-09-05
  • 0
    It looks like your function depends on n, which is not allowed.2012-09-05
  • 2
    @AdamRubinson: It does not depend on $n$. It is given explicitly in terms of $x$.2012-09-05
  • 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$.)2012-09-05
  • 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$.2012-09-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.2012-09-05
  • 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. :)2012-09-05
  • 0
    @ShreevatsaR: I think "flat" notation is more readable, at least on my fairly small-screened computer.2012-09-05
  • 0
    Oh I see. Nice answer I suppose. Obviously it can be extended in the same way indefinitely2012-09-05
  • 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?2012-09-05
  • 0
    @ Andre, thought about that a while ago and f(x) = x^x will do. And my function is cts and so a bit nicer2012-09-05
  • 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.2012-09-05
  • 0
    @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.2012-09-05
  • 0
    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.2012-09-05
  • 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?2012-09-05
  • 1
    @AdamRubinson: what you call infinite polynomials are generally known as [formal power series](http://en.wikipedia.org/wiki/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$.2012-09-05
  • 0
    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...2012-09-06
  • 0
    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 concisely2012-09-06