Upper bound of $\sum_{i \in S} i \log i $ with respect to the sum of elements in list $S$?

Question

Given a list of finite positive integers, denoted by $S$, for which $$\sum_{i \in S} i = m$$ how to derive the upper bound for $$\sum_{i \in S} i \log i$$ with respect to $m$?

Additional info: the distribution of numbers in $S$ follows the power law, in other words, the fraction of numbers with value $v$ approximately equals to $v^{-\gamma}$ for some $\gamma$ in range $[2, 3]$.

---

What I have tried so far: $$ \sum_{i \in S} i \log i = m \log m + \sum_{i \in S} i \log \frac{i}{m} $$

I understand it is upper bounded by $m \log m$, but I think there is a more accurate bound.

Answer 1

Well, if you consider the sets $$ S_1=\{1,2,3,4,5,6,7,8,9,10,21,22,23,24,25,26,27,28,29,30\} $$ $$ S_2=\{6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25\}$$ both $S_1$ and $S_2$ have the same number of elements and the same sum, $m=310$. Although $\sum_{k\in S}k\log k$ behaves pretty differently on $S_1$ and $S_2$: it equals $\approx 929.57$ for $S_1$ and $\approx 872.127$ for $S_2$. More generally, the asymptotic behaviour of $\sum_{k\in S}k\log k$ depends on the distribution of the elements of $S$, not only the sum of the elements. For segments of consecutive numbers it is more than reasonable to invoke summation by parts:

$$\begin{eqnarray*} \sum_{k=1}^{N}k\log(k) &=& \frac{N(N+1)}{2}\log(N)-\sum_{k=1}^{N-1}\frac{k(k+1)}{2}\log\left(1+\frac{1}{k}\right)\\ &=&\frac{N^2}{2}\log(N)+\frac{N}{2}\log(N)-\sum_{k=1}^{N-1}\frac{k+1}{2}+\sum_{k=1}^{N-1}\frac{k(k+1)}{2k^2}+O\left(\sum_{k=1}^{N-1}\frac{1}{k}\right)\\ &=&\frac{N^2}{2}\log(N)-\frac{N^2}{4}+\frac{N}{2}\log(N)+\frac{N}{4}+O(\log N).\end{eqnarray*}$$ Another thing you may notice is that $x\log x$ is a convex function on $\mathbb{R}^+$, hence $$ \sum_{k=1}^{N}x_k\log(x_k) \geq (x_1+\ldots+x_N)\log\frac{x_1+\ldots+x_N}{N}=m\log\frac{m}{N} $$ follows from Jensen's inequality.

---

If there are roughly $v^{-\gamma}$ (with $\gamma>2$) elements with a value close to $v$,

$$ \sum_{k\in S}k\log k \approx \sum_{v=v_{\text{min}}}^{v=v_{\text{max}}}v^{-\gamma} v \log v \approx \int_{v_{\text{min}}}^{v_{\text{max}}}v^{1-\gamma}\log v\,dv\approx \left[\frac{v^{2-\gamma}\log v}{(2-\gamma)}\right]_{v_{\text{max}}}^{v_{\text{min}}}. $$

Answer 2

Probably not an answer.

If the $i$'s were consecutive integer numbers, $$\sum_{i=1}^m i \log(i)=\log (H(m))$$ where $H(m)$ is the hyperfactorial function.

For large values of $m$, Stirling type expansions give $$H(m)=m^2 \left(\frac{1}{2} \log \left({m}\right)-\frac{1}{4}\right)+\frac{1}{2} m \log \left({m}\right)+\left(\log (A)+\frac{1}{12} \log \left({m}\right)\right)+\frac{1}{720 m^2}+O\left(\frac{1}{m^4}\right)$$ where $A$ is Glaisher constant.