2
$\begingroup$

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}$?

$\endgroup$
2
  • 1
    $\begingroup$ Technically $b_{n}$ is not defined for the first $n$ for which $a_{n}\geq 2^{h}$. Do you mean $b_{n}(h)=2^{2\lceil\log_{2}b_{n-1}(h)\rceil}$ in the second? $\endgroup$
    – D. Dona
    Dec 24, 2020 at 19:03
  • $\begingroup$ Yes, thank you @D.Dona $\endgroup$ Dec 24, 2020 at 19:27

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer. When you write "Say that $n$ is the largest integer with $a_{n}<2^{h}$" I am bit confused because you are denoting by $n$ a quantity, while $n$ was used as a subscript for both $a_n$ and $b_n$. By the way, I am also very interested in bounding $\rho(h)$ from below. Considering that $a_n=2^{c\cdot 2^n}$ for a constant $c\approx 0.587$, may I ask you your opinion also about a lower bound of $\rho(h)$? PS: My final goal is actually to find a method to approximate $a_n$ up to a constant factor using at most $h$ bits. $\endgroup$ Dec 24, 2020 at 20:44
  • $\begingroup$ Sorry, I meant that $a_n\sim 2^{c\cdot 2^n}$ for $n\to\infty$, and the asymptotic convergence of $c$ seems to be fast. $\endgroup$ Dec 24, 2020 at 21:06
  • 1
    $\begingroup$ @PenelopeBenenati I added a sketch for the lower bound. $\endgroup$
    – D. Dona
    Dec 24, 2020 at 22:04
  • 1
    $\begingroup$ Theoretically speaking, I'd say the best bet is to find $c$ exactly, and the asymptotics would give what you want. Even finding an approximation $c_{n}$ accurate to the $n$-th digit is enough to get $a_{n}$ up to multiplicative constant, since $2^{n}|c-c_{n}|$ is bounded: in that case, playing delicately with expansions of $\log(x+1)-\log(x)$ may be sufficient, as I was doing at the beginning of the lower bound sketch. That said, I don't know the practical problems of implementing that on a real computer (if that, as I assume, is your goal). $\endgroup$
    – D. Dona
    Dec 25, 2020 at 9:29
  • 1
    $\begingroup$ Thank you once again for your help @D.Dona ! The underlying problem is more general and interesting. Given a $h$ bits binary representation of $\log_2(x)$ and $\log_2(y)$, we want to compute $\log_2(z)$ where $z=x\,y+1$. This computation must be repeated several times, namely bottom-up in a binary tree $T$ where $x$ and $y$ are the integers associated with any two siblings children of $z$, starting from the leaves; the value of each leaf is $1$. The goal is to approximate $\log_2(r)$ where $r$ is the value of the root, when $h$ is the ceiling of the logarithm of the number of leaves of $T$. $\endgroup$ Dec 25, 2020 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.