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$

2 Answers 2

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$
2
  • 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
    Commented Mar 13, 2011 at 23:07
  • $\begingroup$ I noticed this while you were typing. Thanks anyways! $\endgroup$
    – GH from MO
    Commented Mar 13, 2011 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 and acknowledge you have read our privacy policy.

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