I am reading Remarks on a Ramsey theory for trees: Janos Pach, Jozsef Solymosi, Gabor Tardos http://arxiv.org/abs/1107.5301 I am stuck at inequality in proof of Lemma 6.

$n\geq 8$, $k=2\lfloor 3n/\log_2 n \rfloor$, $l = k/2 + 1$ We have

$$\sum_{i=1}^l \frac{l}{2^{m_i}} - n \geq \frac{l^2}{n^{1/3}} - n$$

This inequality should come from fact, that $\sum_i m_i \leq n$ and $2^{-m}$ is a convex function.

When I read "convex function" first that came on my mind was Jensen's inequality $\varphi \left( \sum x_i \right) \leq \sum \varphi(x_i)$. But this gives me much weaker result:

$$\sum_{i=1}^l \frac{l}{2^{m_i}} - n \geq \frac{l}{2^n} - n$$

What am I missing? There is everything relevant I hope. If I omitted something important I am sorry.


2 Answers 2


Another form of Jensen's inequality is that for a convex function $\phi$, we have that $\displaystyle \sum_i \lambda_i \phi(m_i) \geq \phi(\sum_i \lambda_i m_i)$. Take $\displaystyle \lambda_i = \frac{1}{l}$, and that becomes $\displaystyle \sum \frac{1}{l}2^{-m_i} \geq 2^{-\sum_i m_i/l} = 2^{-n/l}$. In other words, $\displaystyle \sum_i \frac{1}{2^{m_i}} \geq \frac{l}{2^{n/l}}$. Since $\displaystyle \frac{n}{l}$ is about $\frac{1}{3}\log n$, so we get that $\displaystyle \sum_i \frac{1}{2^{m_i}} \geq \frac{l}{n^{1/3}}$, which gives the inequality.


We will substitute $\sum_{i=1}^l m_i$ with sum of something bigger ($2^{-m}$ is decreasing) than it's arithmetic mean and Jensen will do the rest. As $l=3n/\log n$, the important part goes:

$$\sum_{i=1}^l 2^{-m_i} \geq \sum_{i=1}^l 2^{-n/l} = l 2^{-n/l} = l 2^{-n\log n/(3n)} = l2^{-\log n/3} = ln^{-1/3}$$

I should practice these computations more. If you find something wrong please let me know.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .