Log inequality- is $(\lceil\log x\rceil - \lfloor\log m\rfloor)\cdot m+2^{\lfloor\log m\rfloor+1}\leq m\cdot(\lceil\log\frac{x}{m}\rceil+2)$?

Question

I'm having some hard times making a tight analysis of the memory requirements for my algorithm. I want to show the following inequality, which will show my data structure can use about 2 bits per counter more than the information theoretic lower bound (if we choose $x,m$ carefully), but I'm not sure this is correct.

Formally, Is it true that:

$$\forall x>m\in\mathbb N:(\lceil\log x\rceil - \left\lfloor\log m\right\rfloor)\cdot m+2^{\lfloor\log m\rfloor+1}\leq m\cdot\left(\left\lceil\log\frac{x}{m}\right\rceil+2\right)$$

When I was going over it yesterday, I thought this inequality, from a previous question would be enough, but I don't see now how to complete the proof. It follows immediately if I replace the "+2" by "+3", but I want the analysis to be tight if possible.

Is this inequality true?

Answer 1

Take, for example, $x=33, m=6$. We then have $\lceil \log x \rceil =6$, $\lfloor \log m \rfloor=2$, $\lceil\log \frac{x}{m}\rceil=\lceil \log 5.5\rceil=3$.

$x>m$ is obviously fulfilled as well.

Putting that in to your inequality, we have $$ (\lceil\log x\rceil - \left\lfloor\log m\right\rfloor)\cdot m+2^{\lfloor\log m\rfloor+1}=(6-2)\cdot 6+2^3=32\leq 30=6\cdot(3+2)= m\cdot\left(\left\lceil\log\frac{x}{m}\right\rceil+2\right), $$

contradiction. So no, your inequality does not hold.

The way you can construct your counterexample is actually more or less working the proof of your mentioned previous question backwards. You find $x,m$ such that $\lceil\log \frac{x}{m}\rceil=\lceil\log x\rceil - \lfloor\log m \rfloor -1$ (namely by choosing $x$ just a bit above and $m$ just a bit below a power of $2$), and then utilize that $2^{\lfloor \log m \rfloor +1}>m$.