Bound on sum of logarithms Consider a natural number $m$ and let $m_i, i=1,2,...,\lfloor{\sqrt{m}}\rfloor$ be natural numbers such that:
$$\sum_{i=1}^{\lfloor{\sqrt{m}}\rfloor} m_i = m$$
My question regards the following sum:
$$\sum_{i=1}^{\lfloor{\sqrt{m}}\rfloor} \log(\frac{m_i}{i}) $$
What can we say for the maximum size of this sum in comparison to $m$? Will it be of the order of $\sqrt{m}$?
 A: Let $k=\lfloor \sqrt{m}\rfloor$. The sum is
$$\sum_{i=1}^k\log\left(\frac{m_i}{i}\right)=\log\left(\frac{m_1m_2\cdots m_k}{k!}\right) $$
By AM-GM
$$m_1m_2\cdots m_k\leq \left(\frac{m_1+m_2+\cdots+m_k}{k}\right)^k=\left(\frac{m}{k}\right)^k $$
For $k!$, we need a lower bound. Among various options:
$$k!\geq \left(\frac{k}{e}\right)^k$$
Hence,
$$\frac{m_1m_2\cdots m_k}{k!}\leq\left(\frac{me}{k^2}\right)^k$$
$$\log\left(\frac{m_1m_2\cdots m_k}{k!}\right)\leq k\log\left(\frac{me}{k^2}\right)\leq\sqrt{m}\log\left(\frac{me}{k^2}\right)$$
Note that $m/k^2 \to 1$ as $m\to\infty$, so $\log\left(me/k^2\right)\to \log(e)=1$ and $\log\left(me/k^2\right)<2$ for sufficiently large $m$. Alternatively, you can try showing that $m/k^2\leq 4$ for all $m$, so $\log\left(me/k^2\right)\leq \log(4e)=\log(4)+1$. The point is to show that $\log\left(me/k^2\right)$ is bounded by a constant.
A: By the AM-GM inequality,
$$
\prod_i m_i 
\le \left(\frac{\sum_i m_i}{\lfloor \sqrt m \rfloor}\right)^{\lfloor \sqrt m \rfloor}
= \left(\frac{m}{\lfloor \sqrt m \rfloor}\right)^{\lfloor \sqrt m \rfloor}
\approx (\sqrt m)^{\sqrt m}
$$
(I'm too tired to care about the floor thingy right now). Therefore
$$
\sum_i \log\frac{m_i}{i}
= \log\prod_i\frac{m_i}{i}
\le \log \frac{(\sqrt m)^{\sqrt m}}{(\sqrt m)!}
= \sqrt m \log (\sqrt m) - \log(\sqrt m)!
$$
From looking a bit on the wiki page for Stirling's approximation, we find
$$
\log n! = n\log n + \Theta(n)
$$
If we plug that into the above we get
$$
\sum_i \log\frac{m_i}{i} \in O(\sqrt m)
$$
Note also that the AM-GM inequality is an equality in case all the $m_i$ are equal. That means that the above order can be attained. So we have in the worst case
$$
\sum_i \log\frac{m_i}{i} \in \Theta(\sqrt m)
$$
i.e. we can't improve on the order in the general case. This was like you guessed! We can make the bound more precise by adding more terms of the Stirling approximation.
