2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – user9072 Mar 13 '11 at 23:07
  • $\begingroup$ I noticed this while you were typing. Thanks anyways! $\endgroup$ – GH from MO Mar 13 '11 at 23:12
2
$\begingroup$

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).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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