MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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})$?

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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? – user9072 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).$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.