I am having trouble verifying the following claim in Van Vu's 2000 paper "On a refinement of Waring's problem". First we define a few things.

Let $m \in \mathbb{N}_0$ and $r \geq 2, r \in \mathbb{N}$ be fixed. Choose $P_j \in$ {$2, 4, \cdots, 2^t$} where $t$ is chosen so that $2^t$ is the smallest integer power of 2 bigger than $m^{1/r}$. Suppose that $l \in \mathbb{N}$ is sufficiently large. Let $\mathcal{P}$ denote the set of $l$-tuples {$P_1, \cdots, P_l$} with $2 \leq P_1 \leq \cdots \leq P_l$. For each $A \in \mathcal{P}$, write $P_A = \prod_{P_j \in A} P_j$. Then verify the inequality $$\displaystyle \sum_{A \in \mathcal{P}} P_A^{r/l} = O(m)$$

The idea here is that if $P_A$ is as large as possible, then $P_A^{r/l} = O(m^{l/r \cdot r/l}) = O(m)$, and the other terms are not so significant since the number of summands is small. However, how do I rigorously show that we indeed have the bound $O(m)$ instead of say, $O(m^{1 + \epsilon})$?

-

As each $P_A$ is a product of at most $l$ elements of {$2,4,\dots,2^t$} counted with multiplicity, we have for any $\lambda>0$, $$\sum_{A \in \mathcal{P}} P_A^\lambda\leq(2^\lambda+2^{2\lambda}+\cdots+2^{t\lambda})^l<(2^{(t+1)\lambda}/(2^\lambda-1))^l.$$ Assuming $\lambda$ and $l$ are fixed, we obtain $$\sum_{A \in \mathcal{P}} P_A^\lambda\ll(2^{t+1})^{\lambda l}<(4m^{1/r})^{\lambda l}\ll m^{\lambda l/r}.$$ Applying this for $\lambda:=r/l$ yields, for fixed $r$ and $l$, $$\sum_{A \in \mathcal{P}} P_A^{r/l} \ll m.$$

EDIT: I corrected an oversight in my original message.

-
Maybe I am just slow, as it is somewhat late where I am; but who do you get the first inequality; (sum 2^(i lambda) )^l would be clear? –  quid Mar 13 '11 at 23:07
I noticed this while you were typing. Thanks anyways! –  GH from MO Mar 13 '11 at 23:12
Thank you very much! –  Stanley Yao Xiao Mar 13 '11 at 23:57

The sum in question is essentially equal to

$$\sum_{P_1< \cdots < P_l}P_1^{r/l}\cdots P_l^{r/l}=\frac1{l!}\sum_{\substack{P_1,\dots,P_l\\\ {\rm distinct}}} P_1^{r/l}\cdots P_l^{r/l}\le \frac1{l!}\Bigl(\sum_PP^{r/l}\Bigr)^l=O(2^{rt})=O(m).$$

-