0
$\begingroup$

I'm trying to prove the following inequality (or something similar, up to a constant factor in either side of the inequality): $$k\cdot\sum_{i=1}^{k}x_{i}\cdot\ln\left(x_{i}\right)\geq\sum_{i=1}^{k}x_{i}\cdot\left(x_{i}-1\right)$$ where $\forall i\in\left[k\right]$, $x_i \in\left[0,k\right]$ (the $x_i$s are not necessarily natural numbers, but we can assume that they're rational if it helps), and $\sum_{i=0}^k x_i=k$.

I've tried plotting it for $k=2,3$ and ran some numerical experiments for larger $k$, and I'm 99% sure this inequality is correct, but I'm still struggling with the proof.

Up to some normalizing, I find the left-hand side quite similar to the entropy of a probability distribution, but I didn't manage to take advantage of this fact either. I also tried looking for inequalities that only hold on simplex-like hyperplanes, but couldn't find anything useful.

Any ideas? Thanks!

$\endgroup$
1
  • 2
    $\begingroup$ Rewrite the RHS as $\sum_i(x_i-1)^2$ and use the first order Taylor formula at $1$ with the remainder in the Lagrange form for the function $x\mapsto x\log x$ on the LHS. That will immediately give you "something similar" with $2k$ instead of $k$ on the left. Then you can tweak this idea a bit to improve the constant. $\endgroup$
    – fedja
    Commented Sep 2, 2021 at 9:25

1 Answer 1

3
$\begingroup$

Expanding a little bit on fedja's comment, it is actually convenient to consider the inequality in the equivalent form $$ \sum_{i=1}^k ( x_i \ln x_i - x_i + 1) \geq c_k \sum_{i=1}^k (x_i-1)^2 , $$ where we are interested to find $c_k$ such that the inequalities hold for all $x_i \in [0,k]$ with $\sum_{i=1}^k x_i = k$.

By Taylor, it is easy to see, that we have the two inequalities $$ x \ln x -x +1 \geq \tfrac{1}{2} (x-1)^2 \qquad\text{ for } x \in [0,1] $$ and $$ x \ln x -x +1 \leq \tfrac{1}{2} (x-1)^2 \qquad\text{ for } x \geq 1 $$ Hence, we are only in trouble for $x\in [1,k]$. By comparing the derivatives of the function on the left hand and right hand side: $\ln(x)$ and $x-1$, we also see that the defect in the second estimate is monotone increasing in $x$ starting at $x=1$, where both are equal.
Hence, we find the optimal constant as $$ c_k = \inf_{x\in [0,k]} \frac{x \ln x -x +1}{(x-1)^2} = \frac{k \ln k - k +1}{(k-1)^2}. $$ Note that $c_k$ is monotone decreasing in $k$ with $c_1=1/2$. In particular, it holds $c_k \geq \frac{1}{2k}$, but this gives not the correct asymptotics, since for $k\geq 2$, one can use the lower bound $$ c_k \geq \frac{\ln k -1}{k} , $$ which is asymptotic sharp for $k\to \infty$.

$\endgroup$

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.