4
$\begingroup$

Let $N\geq 1$ be a positive integer and assume that $N=2^{n_1}+2^{n_2}+\cdots+2^{n_{p}}$, $n_{1}>n_{2}>\cdots>n_{p}\geq 0$, is the binary representation of $N$. I believe that the following inequality is valid for every $0<s<1$ but I haven't been able to prove it: $$ \left(\frac{2^{n_1}}{N}\right)^s+\left(\frac{2^{n_2}}{N}\right)^s+\cdots+\left(\frac{2^{n_{p}}}{N}\right)^s\leq \frac{1}{2^s-1}. $$ Note that by continuity the inequality is valid for $s$ sufficiently close to zero since the left side approaches $p$ and the right side approaches infinity. When $s=1$ we get equality.

Note that one can assume that $N$ is odd, i.e., $n_p=0$. If $N$ is of the form $N=1+2+2^2+\cdots+2^{p-1}=2^{p}-1$, then one obtains a geometric sum and the inequality reduces to $2^{sp}-1\leq (2^p-1)^s$, which follows from $(a+b)^s\leq a^s+b^s$.

$\endgroup$

1 Answer 1

10
$\begingroup$

Rewrite the right hand side as $$\frac1{2^s-1}=\left(\frac12\right)^s+\left(\frac14\right)^s+\left(\frac18\right)^s+\ldots.$$ Then your inequality reads as $$\sum_{i=1}^p f(2^{n_i}/N)\leqslant \sum_{i>0} f(1/2^i)\quad\quad\quad(\heartsuit)$$ for a function $f(t)=t^s$. I claim that $(\heartsuit)$ holds for every concave function $f$ with $f(0)=0$. In other words, the infinite multiset $\{2^{n_i}/N\colon i=1,2,\ldots,p;0,0,\ldots\}$ majorizes the set $\{1/2,1/4,\ldots\}$. This is clear: for every $k=1,2,\ldots,p$ we have $$\sum_{i=1}^k\frac{2^{n_i}}N=\frac{2^{n_1}+\ldots+2^{n_k}}{N}=\left(1+\frac{2^{n_{k+1}}+\ldots+2^{n_p}}{2^{n_{1}}+\ldots+2^{n_{k}}}\right)^{-1}\geqslant \left(1+\frac{2^{n_{k}}-1}{2^{n_{k}}(2^k-1)}\right)^{-1}\\ >\left(1+\frac{1}{2^k-1}\right)^{-1}=1-\frac1{2^k}=\frac12+\frac14+\ldots+\frac1{2^k}.$$ The infinite version of Karamata inequality is proved by the same Abel transform trick as the proof given in Wikipedia.

$\endgroup$
3
  • $\begingroup$ Thank you Fedor for the clarifying answer and the reference to Karamata's inequality. $\endgroup$
    – aleari1009
    Aug 15 at 18:53
  • $\begingroup$ I was not accurate with infinite sets, hope that now it is ok $\endgroup$ Aug 15 at 22:21
  • $\begingroup$ Thanks for revising your post. When I read your original post I thought that it suffices to use the finite version of Karamata's inequality, but I suppose that in that case I need also to use condition (5) instead of (4) in the Wikipedia text. However, it seems to me that I would need the function to be decreasing or non-increasing because t^s is concave. But I will read the Wikipedia text carefully and follow your recommendation. Thanks a lot $\endgroup$
    – aleari1009
    Aug 16 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy