Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The first of my questions may be entirely elementary, but the second (closely related) question may be of appropriate interest for this site.

Suppose that we are given $w_1, w_2, \cdots, w_n$ of positive integers which are co-prime. Let $H > 1$ be a positive parameter. I am interested in evaluation the sum

$$\displaystyle \sum_{w_1 x_1 + \cdots + w_n x_n \leq H} (w_1 x_1 + \cdots + w_n x_n)$$

I think the sum can be expressed in the form $c_0 H^{n+1} + O(H^{n})$ for some positive constant $c_0 > 0$, and if this is the case then I want to know what $c_0$ is in terms of the weights $w_1, \cdots, w_n$.

Second question is for general weights $w_1, \cdots, w_n$, where these are positive real numbers (but not necessarily integers), can we obtain the same result? Since a counting argument is not so clear here, what would be the way to show it?

Thanks for any insights.

share|improve this question
    
For your "elementary" first question I assume that you are summing over all choices of non-negative integers $x_1,\dots,x_n$ which have the weighted sum less than $H$. I would guess that you could get a good approximation to the second question by taking sums less than $NH$ using integer weights obtained by rounding the $Nw_i$ –  Aaron Meyerowitz Feb 14 '12 at 19:22

3 Answers 3

up vote 3 down vote accepted

new answer I think that the sum will be $$\frac{n}{w_1w_2\dots w_n}\binom{H+n}{n+1}+o(H^{n}).$$ I do not think that it matters if the positive values $w_i$ are integers nor (if they are) if they are relatively prime. If my calculations are correct, then in the special case that $w_1=w_2=\dots=w_n=1$ and $H$ is an integer, the sum comes out to exactly $n\binom{H+n}{n+1}.$

As an experiment: with $w_1=e,w_2=\pi,w_3=\sqrt{17}$ and $H=1000$ the exact sum (to the nearest integer) is $3,597,483,570$ while the estimate is $3,571,444,698.$

old answer I think that $c_0H^{n+1}$ seems more likely.

In the special case $n=1, w_1=1$ you would have the sum of all the integers up to $H$ and hence $\frac{H(H+1)}{2}$ (We may as well assume $H$ is an integer.) In general for $n=1$ we can assume that $H=kw_1$ and get $\frac{1}{2w_1}H^2+O(H).$

The case that there are $n$ $w_i$ all equal to 1 might fit the description and be worth working out.

The case $n=2$ with $w_1=1$ is the sum $$\sum_{x_2=0}^{\lfloor H/w_2 \rfloor}\ \sum_{j=0 }^{H-x_2w_2}(x_2w_2+j)$$ which could be exactly worked out without too much grief and is clearly $c_0H^3+O(H^2).$

In general one could pull out $w_1$, (say the smallest of the relatively prime $w_i$) and then add the sums for $H,H-w_1,H-2w_1,\dots$ with the weights $w_2,\dots,w_n$

share|improve this answer
    
I think you are right and have corrected this in the question. –  Stanley Yao Xiao Feb 14 '12 at 20:02
    
I still think that the constant is correct but that can't be $o(H^{n})$ as written because for $w_1=w_2=\dots=w_n=w$ the exact value would be $\frac{nH(H/w+1)(H/w+2)\dots(H/w+n)}{(n+1)!}.$ This suggests possible $o(H^n)$ formulas for the general case but it would take further investigation. –  Aaron Meyerowitz Feb 15 '12 at 0:09
    
Of course we would have to replace $H$ by $qw$ if $qw \lt H \lt (q+1)w.$ The sum clearly is non-decreasing in $H$. in the integer case there is probably an exact formula for each congruence class mod the lcm of the $w_i$. –  Aaron Meyerowitz Feb 15 '12 at 18:18

As a response to this question A weighted sum of non-negative integers Qiaochu Yuan and me mentioned that the number of times some $k$ can be written as $\sum x_i w_i$ is called denumerant and is $c k^{n-1} + O(k^{n-2})$, where the constant depends only on $w_i$ and $n$, namely it is $1/ (n-1)!\prod w_i$.

Now, let $d_k$ denote the denumerant, then what you are looking for is, going by Aaron Meyerowitz clarifying comment, equal to $\sum_{k \le H} k d_k$. Plugging in the asymtotics for the denumerant and evaluating the sum, which is up to lower order terms $c \sum k^{n}$ you should get what you are looking for, even with a value for the constant.

For the second question, I agree with Aaron Meyerowitz that the thing seems insensitive to small perturbations and so one can pass to rational and thus integral weights.

share|improve this answer

Here is an insight. Look at the rectangular simplex formed in the positive orthant that is cut off by the plane H = wvec dot vvec, where wvec is your vector of weights. Your sum will be a weighted sum of lattice points grouped by planes parallel to the constraint plane. This perspective should confirm your estimate up to a multiplicative constant, even in the case the weight vector is composed of arbitrary reals. (I assume as Aaron does that the x_i you use in the sum lie inside the simplex as lattice point coordinates.)

Gerhard "Ask Me About System Design" Paseman, 2012.02.14

share|improve this answer

Your Answer

 
discard

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.