We are given the sequence defined by the recurrence relation $a\_{n+1}=a\_n^2+1$ with $a\_0=0$.


Let $h$ be a positive integer (*it represents the maximum number of bits, up to a constant factor, that we can use to codify the following approximation of $a\_n$*). We define the approximation $b\_n(h)$ of $a\_n$ as follows:


* $b\_n(h)=a\_n~~~~~~~~~~~~~~~~~$ for all $n\in\mathbb{N}$ such that $a\_n<2^h$.
* $b\_{n}(h)=2^{2{\lceil\log\_2 b\_{n-1}(h)\rceil}}~~~$ for all $n\in\mathbb{N}$ such that $a\_n\ge2^h$.




---


**Question**: Let $m(h)$ be the maximum value of $n$ such that $\lceil\log\_2 b\_{n}\rceil<2^h$. Is the ratio $\rho(h):=\frac{a\_{m(h)}}{b\_{m(h)}(h)}$ upper bounded by an absolute constant for all $h\in\mathbb{N}$?



Approximation of a quadratic map by using a limited binary representation
As it is defined, $\rho(h)=\frac{a\_{m(h)}}{b\_{m(h)}(h)}$ is bounded from above by $1$ for all $h$ large enough.


Say that $n$ is the largest index with $a\_{n}<2^{h}$. Suppose first that $a\_{n}\neq 2^{k}$. Then $2^{\lceil\log\_{2}b\_{n}(h)\rceil}>2^{\log\_{2}b\_{n}(h)}=b\_{n}(h)$, so $b\_{n+1}(h)\geq a\_{n+1}+1$, and it's easy to see that from that point onwards we have $b\_{n'}(h)\geq a\_{n'}+1$ for all $n'>n$.


On the other hand, $a\_{n}=2^{k}$ can only happen for $n\leq 2$ (try and write a power of $2$ as $(2x+1)^{2}+1$). Thus, for $h$ large, for every $m$ either $b\_{m}(h)=a\_{m}$ (when $a\_{m}<2^{h}$) or $b\_{m}(h)\geq a\_{m}+1$ (when $a\_{m}\geq 2^{h}$). This implies the initial claim.


Then we can take $M=\max\{\rho(h)|h\text{ small}\}$ and get a bound $\max\{1,M\}$ valid for all $h$ (I suspect that's $1$ anyway).




---


You can't do better than $0$ for a lower bound. I'll give a rough sketch, forgive the lack of details.


For $n$ large enough we have $\log\_{2}(a\_{n+k})-2^{k}\log\_{2}(a\_{n})\in\left(0,\frac{2}{a\_{n}^{2}}\right)$, using repeatedly that $\log\_{2}(x^{2}+1)-2\log\_{2}(x)<\frac{1}{x^{2}}$. Fix $n$ large and write $\log\_{2}(a\_{n})=a+\varepsilon$ with $a=\lfloor\log\_{2}(a\_{n})\rfloor\in\mathbb{Z}$ and $0<\varepsilon=\{\log\_{2}(a\_{n})\}<1$: then every $\log\_{2}(a\_{n+k})$ is in $2^{k}a+2^{k}\varepsilon+\left(0,\frac{2}{a\_{n}^{2}}\right)$. The orbit of $\varepsilon$ under the action of the duplication map modulo $1$ in $[0,1)$ is dense ($\varepsilon$ is generic enough, given its definition), so there are infinitely many $k$ with $\{\log\_{2}(a\_{n+k})\}\in\left(0,\frac{1}{3}\right)$. For each such $k$ we can define $h(k)$ to be the lowest $h$ that gives $a\_{n+k}<2^{h}\leq a\_{n+k+1}$, and then $\frac{b\_{n+k+1}(h(k))}{a\_{n+k+1}}\geq c$ for some absolute $c>1$ ($c=\frac{3}{2}$ should do). Finally one can prove that $m(h(k))-n-k$ is unbounded for $k\rightarrow\infty$ (as $m(h(k))$ is much larger than $n+k$), so that $\frac{b\_{m(h(k))}(h(k))}{a\_{m(h(k))}}$ is bounded from below by something close to $c^{m(h(k))-n-k}\rightarrow\infty$.


So for infinitely many $h$ we have $\frac{a\_{m(h)}}{b\_{m(h)}(h)}$ as close to $0$ as we like.


