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?
Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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} $$

Improve this answer
$\endgroup$
5
  • $\begingroup$ what is the $\sim$ difference? $\endgroup$
    – Turbo
    Commented Apr 4, 2015 at 18:17
  • 1
    $\begingroup$ Do you mean $e^x (1 + o(1))$? $\endgroup$
    – Geoffrey Irving
    Commented Apr 4, 2015 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
    Commented Apr 4, 2015 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
    Commented Apr 5, 2015 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
    Commented Apr 5, 2015 at 9:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .