3
$\begingroup$

Given two natural numbers $i$ and $p$ such that $0 < i \leqslant 2^p$, let $ \psi(p,i) := p - \alpha + 1 - \frac{1}{2^p}\left((2^p+i)\lg(2^p+i) - i\lg i - i + \alpha - \frac{2^p}{i+1} - \frac{i}{2^p+1}\right), $ where $\alpha \simeq 1.264499$ and $\lg n$ is the binary logarithm of $n$. I am looking for $\min_{p,i}\psi(p,i)$.

It seems that $\min_{i}\psi(p,i) = \psi(p,2^p)$ or $\psi(p,2^p-1)$. Anyway, I can then minimize over $p$.

We have $ \frac{\partial\psi}{\partial i}(p,i) = - \frac{1}{(i+1)^2} - \frac{1}{2^p}\left(\lg(2^p+i) - \lg i - \frac{1}{2^p+1} - 1\right). $ (The derivative with respect to $p$ is much worse.) Also $ \lim_{i \rightarrow 0^{+}}\frac{\partial\psi}{\partial i}(p,i) = -\infty,\quad \text{and}\quad \left.\frac{\partial\psi}{\partial i}(p,i)\right|_{i=2^p} \!\!= \frac{1}{2^p(2^p+1)^2} > 0. $ The derivative is strictly increasing (the second derivative is positive). How can I prove that the root of $\partial\psi/\partial i = 0$ is between $i=2^p-1$ and $i=2^p$? And which of these values is the minimum?

  • 0
    @Raskolnikov: You are right. Fixed.2012-09-05

1 Answers 1

0

It is tedious, even with the help of some computer algebra system, to check that $\left.\partial\psi/\partial i\right|_{i=2^p-1} < 0$, so the root is indeed between $2^p-1$ and $2^p$. It is then fastidious to check that $\psi(p,2^p-1) > \psi(p,2^p)$, so $\min_{0.

After that, the minimization of $\psi(p,2^p)$ yields $\min_{0 < p, 0 < i \leqslant 2^p}\psi(p,i) = -\alpha$.