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

Improve this question
$\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
    Commented Dec 24, 2020 at 19:03
  • $\begingroup$ Yes, thank you @D.Dona $\endgroup$
    – Penelope Benenati
    Commented Dec 24, 2020 at 19:27

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Penelope Benenati
    Commented 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$
    – Penelope Benenati
    Commented Dec 24, 2020 at 21:06
  • 1
    $\begingroup$ @PenelopeBenenati I added a sketch for the lower bound. $\endgroup$
    – D. Dona
    Commented 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
    Commented 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$
    – Penelope Benenati
    Commented Dec 25, 2020 at 11:04

You must log in to answer this question.

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