5
$\begingroup$

I was reading this question on functions "in the middle" of linear and exponential growth, and it caused me to think of this function:

$$ G(x) = \left(1 + \frac{x}{f(x)}\right)^{f(x)} $$

for some non-decreasing function $f$. If $f(x)$ is constant, then $G$ is just a polynomial in $x$. If $f(x) \geq x^2$, then I believe $G(x) \to e^x$ as $x \to \infty$ (edit: should be $G(x) \sim e^x$). This might be true for other $f(x) = \omega(x)$, I'm not sure.

Three questions:

  • Is $G$ of interest or use anywhere, or has its growth rate been studied? Is there an interesting connection I'm missing?
  • What can we say about how fast $G$ grows for choices of $f$ between constant and $x^2$? In particular, can we say something interesting or simpler about how fast these grow?
    • $\left(1 + \sqrt{x}\right)^{\sqrt{x}}$
    • $\left(1 + x^{\alpha}\right)^{x^{1-\alpha}}$
    • $\left(1+\frac{x}{\log x}\right)^{\log x}$
    • What I was sort of hoping is that a choice of $f$ would give a function so that $G(G(x)) = \Theta(e^x)$; does that seem possible?
$\endgroup$
6
$\begingroup$

Let's suppose $x/f(x) \to 0$. Then take logarithm. As $x \to \infty$, $$ \log G(x) = f(x) \log\left(1+\frac{x}{f(x)}\right) =f(x)\left(\frac{x}{f(x)}+O\left(\left(\frac{x}{f(x)}\right)^2\right)\right) \\ = x + O\left(\frac{x^2}{f(x)}\right) \tag{*}$$ Now if we have the stronger $x^2/f(x) \to 0$, then $$ G(x) = \exp\left(x + O\left(\frac{x^2}{f(x)}\right)\right) =e^x\exp \left(O\left(\frac{x^2}{f(x)}\right)\right) =e^x\left(1+o(1)\right) \tag{**}$$ But note: it is incorrect to write this as $G(x) \to e^x$. Instead write $G(x) \sim e^x$.

Now consider the three examples. See if I made any mistakes.
..........
$$ G_1(x) = (1+\sqrt{x}\;)^{\sqrt{x}} \\ \log G_1(x) = \sqrt{x}\log(1+\sqrt{x}\;) = \sqrt{x}\log\left(\sqrt{x}\left(1+\frac{1}{\sqrt{x}}\right)\right) \\ =\sqrt{x}\left(\log\sqrt{x}+\log\left(1+\frac{1}{\sqrt{x}}\right)\right) =\sqrt{x}\left(\frac{1}{2}\log x+\frac{1}{\sqrt{x}}+O\left(\frac{1}{x}\right)\right) \\ G_1(x) = e^{(1/2)\sqrt{x}\log x} e^1 (1+o(1)) \\ G_1(x) \sim e\;x^{(1/2)\sqrt{x}} $$
..........
Assume $\alpha>1/2$
$$ G_2(x) = (1+x^\alpha)^{x^{1-\alpha}} \\ \log G_2(x) = x^{1-\alpha}\log\left(1+x^\alpha\right) =x^{1-\alpha}\left(\log x^\alpha+ \log\left(1+x^{-\alpha}\right)\right) \\ =x^{1-\alpha}\left(\alpha \log x+x^{-\alpha} +O\left(x^{-2\alpha}\right)\right) \\ G_2(x) = e^{x^{1-\alpha}\alpha\log x} e^{x^{1-2\alpha}} (1+o(1)) \sim x^{x^{1-\alpha}\alpha} $$
..........
$$ G_3(x) = \left(1+\frac{x}{\log x}\right)^{\log x} \\ \log G_3(x) = \log x \log\left(1+\frac{x}{\log x}\right) =\log x\left(\log\frac{x}{\log x}+O\left(\frac{\log x}{x}\right)\right) \\ =(\log x)^2 -\log x \log\log x+o(1) \\ G_3(x) \sim e^{(\log x)^2-\log x \log\log x} = x^{\log x - \log\log x} $$

$\endgroup$
  • $\begingroup$ what is the $\sim$ difference? $\endgroup$ – Brout Apr 4 '15 at 18:17
  • 1
    $\begingroup$ Do you mean $e^x (1 + o(1))$? $\endgroup$ – Geoffrey Irving Apr 4 '15 at 18:19
  • 1
    $\begingroup$ @Turbo In this context, $\sim$ means "asymptotic to". So $F(x)\sim G(x)$ is a shorthand notation for $\lim F(x)/G(x)=1$, or alternatively $F(x) = G(x)(1+o(1))$. $\endgroup$ – Joe Silverman Apr 4 '15 at 19:41
  • 1
    $\begingroup$ The first of these can be attained much more easily: $(1+\sqrt{x})^{\sqrt{x}} = \sqrt{x}^{\sqrt{x}}\cdot(1+\frac1{\sqrt{x}})^{\sqrt{x}}$, and the latter clearly goes to $e$ as $x\to\infty$. $\endgroup$ – Steven Stadnicki Apr 5 '15 at 7:19
  • 1
    $\begingroup$ Thanks for the response. Stepping back, I guess the takeaway is that the question is probably not very interesting. If $f(x) = o(x)$, then the $1 +$ is essentially noise in the growth rate (right?), and you're looking at $\sim \left(\frac{x}{f(x)}\right)^{f(x)}$. So the cases $f(x) = \omega(x)$ are more interesting, but they're not that interesting either because they're all something like $e^{\Theta(x)}$. $\endgroup$ – usul Apr 5 '15 at 9:02

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.