Quantitative rate of growth for iterates of $f(x)=x+cx^2$?

123 Views Asked by At

Suppose that $\alpha$ and $c$ are in the interval $(0,1)$ and let $f(\alpha)=\alpha(1+c\alpha)$. A fairly straightforward estimate shows that if we keep iterating this function, we eventually get to infinity. But what I want is a guarantee that it will exceed one relatively quickly: $$f^{k}(\alpha)>1 \qquad\text{where}\qquad k\geq \lceil 2/c\alpha \rceil.$$

This question is left as an exercise in Verstraëte's notes on Roth's theorem, but I've not been able to figure it out. (In the notes there is a typo; he writes "$k\leq$" but this is obviously false.)

It may help to note that we're asking for the value of $f_k$, where $f_0=\alpha$ and $f_{n+1}=f_n+cf_n^2$, so if you are good at solving nonlinear difference equations, we may get some mileage out of that. But I have not been able to make, say, Euler's method, pop out something useful.

2

There are 2 best solutions below

1
On

$\newcommand{\a}{\alpha} \newcommand{\g}{\gamma}$ We leave to the reader the observation that $f^n(\a)=\a p_n(c\a)$ for polynomials $p_n$ with positive integer coefficients, for which the constant term is $1$, and in general satisfying the recurrence $p_{n+1}(x)=(1+xp_n(x))p_n(x)$. We aim to estimate the coefficients of $p_n$.

Specifically, we claim that $[x^i]p_n(x)\geq (n)_i$, where $(n)_i$ is the falling factorial, i.e. $\frac{n!}{(n-i)!}$, for $n\geq i\geq 0$ not both zero. The proof goes by induction. For our base cases, it's clearly true that $[x^i]p_n(x)\geq (n)_i$ when $i>n$, since then the RHS is zero. We now show that $[x^n]p_n(x)\geq n!$. This, in turn, goes by induction: clearly it is true for $n=1$ and in general we may use our recursive formula to show that

$$ [x^{n+1}]p_{n+1}(x) \geq [x^n]p_n(x) +[x^{n-1}]p_n(x)\cdot[x^1]p_n(x) = n!\cdot (n!/1!)n = (n+1)!. $$

This shows the base case. If we assume the statement is true for a given pair $n\geq i\geq 0$, then our recurrence implies that it is true for $n+1\geq i\geq 0$ because \begin{align*} [x^i]p_{n+1}(x) &\geq (n)_i + \sum_{j=1}^i (n)_{i-j}(n)_j \\ & = (n)_{i-1}(n-i+1)+(n)_{i-1}(n) + \sum_{j=2}^i (n)_{i-j}(n)_j \\ &\geq (n)_{i-1}(n+1) + \sum_{j=2}^i (n)_{i-j}(n)_j \\ &\geq (n+1)_i. \end{align*}

Note that in the third line we have used that $2n-i+1\geq n+1$, which holds since $i\leq n$.

We now consider the term $\kappa=\lceil k/2\rceil$. Setting $\g=[x^\kappa]p_k(x)$, the positivity of $p$ tells us that $f^k(\a)\geq \a\g(c\a)^\kappa \geq\alpha(k)_\kappa(c\a)^\kappa$.

Stirling's formula tells us that $$ (k)_\kappa = \frac{k!}{(k-\kappa)!} \geq \frac{\sqrt{2\pi} (k^{k+\frac12}) e^{-k}}{e (k-\kappa)^{k-\kappa+\frac12} e^{-k+\kappa}} \geq \frac{\sqrt{2\pi}}{e} \frac{k^{k+\frac12}}{(k/2)^{k/2-\frac12}} e^{-k/2-1/2}$$ and therefore $$f^k(\a)\geq \frac{\a\sqrt{2\pi}}{e^2}\left(\frac{k^2}{ke/2}\right)^{k/2} \frac{k}{\sqrt2}(c\a)^{k/2} \geq \frac{\a k\sqrt{\pi}}{e^{3/2}}\left(\frac{2kc\a}{e}\right)^{k/2} \geq \frac{2\sqrt{\pi}}{ce^{3/2}}\left(\frac{4}{e}\right)^{1/c\alpha}>1$$

The last inequality follows because we may replace the $1/c\a$ in the exponent with just $1/c$, use basic calculus to show that the function is decreasing for all $c>0$, thus check that the right-bound $8e^{-5/2}\sqrt{\pi}>1$, which concludes the proof.

0
On

+1 to Did's easy and elegant method, it should be an answer indeed.

This book "Iteration of Rational Functions: Complex Analytic Dynamical Systems" (by Alan F. Beardon) contains this easy to prove result (page 41):

enter image description here

Specifically, from the corollary and given all the terms are positive, $$f^{\circ k}(x)=x+ckx^2+...>x+ckx^2$$ Enforcing $$\alpha+ck\alpha^2>1 \Rightarrow f^{\circ k}(\alpha) >1$$ which is true when $$k > \frac{1-\alpha}{c\alpha^2} \tag{1}$$ This is indeed not the asked estimation, but it's a very easy result to obtain and it gives better estimates for $k$ when $\alpha \in \left[\frac{1}{3},1\right)$ (easy to show from $\frac{1-\alpha}{c\alpha^2} \leq \frac{2}{c\alpha}$). E.g. a Python code like this (note: $(1)$ is the obtained estimate)

import math

def askedEstimate(a,c):
    return math.ceil(2/(a*c))

def obtainedEstimate(a,c):
    return math.ceil((1-a)/(c*a*a))

def f(a,c):
    return a + c * a * a

def m_f(a,c,n):
    v = a
    for i in xrange(0,n):
        v = f(v,c)
    return v

def report_for(a, c):
    a_estimate = int(askedEstimate(a, c))
    o_estimate = int(obtainedEstimate(a, c))
    print "--------------------------------------------"
    print "a:",a,"and c:",c
    print "asked estimation:",a_estimate
    print "obtained estimation:",o_estimate
    print "function value at ",a_estimate," iterations:", m_f(a, c, a_estimate)
    print "function value at ",o_estimate," iterations:", m_f(a, c, o_estimate)


report_for(0.75, 0.75)
report_for(0.50, 0.75)
report_for(0.25, 0.75)

report_for(0.75, 0.50)
report_for(0.50, 0.50)
report_for(0.25, 0.50)

report_for(0.75, 0.25)
report_for(0.50, 0.25)
report_for(0.25, 0.25)

prints

--------------------------------------------
a: 0.75 and c: 0.75
asked estimation: 4
obtained estimation: 1
function value at  4  iterations: 31.3989860965
function value at  1  iterations: 1.171875
--------------------------------------------
a: 0.5 and c: 0.75
asked estimation: 6
obtained estimation: 3
function value at  6  iterations: 296.591123512
function value at  3  iterations: 1.85630297661
--------------------------------------------
a: 0.25 and c: 0.75
asked estimation: 11
obtained estimation: 16
function value at  11  iterations: 63995865.6506
function value at  16  iterations: 8.3899753688e+245
--------------------------------------------
a: 0.75 and c: 0.5
asked estimation: 6
obtained estimation: 1
function value at  6  iterations: 444.886685268
function value at  1  iterations: 1.03125
--------------------------------------------
a: 0.5 and c: 0.5
asked estimation: 8
obtained estimation: 4
function value at  8  iterations: 1600.97006152
function value at  4  iterations: 1.8258258258
--------------------------------------------
a: 0.25 and c: 0.5
asked estimation: 16
obtained estimation: 24
function value at  16  iterations: 1.14820788096e+30
function value at  24  iterations: inf
--------------------------------------------
a: 0.75 and c: 0.25
asked estimation: 11
obtained estimation: 2
function value at  11  iterations: 191987596.952
function value at  2  iterations: 1.08892822266
--------------------------------------------
a: 0.5 and c: 0.25
asked estimation: 16
obtained estimation: 8
function value at  16  iterations: 2.29641576193e+30
function value at  8  iterations: 2.68039109376
--------------------------------------------
a: 0.25 and c: 0.25
asked estimation: 32
obtained estimation: 48
function value at  32  iterations: inf
function value at  48  iterations: inf