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

I am interested in knowing the order of magnitude of the following two weighted sums. The first one is as follows:

Suppose $(w_1, w_2, \cdots, w_{n-1})$ are positive numbers, and suppose that $\lambda$ is a positive real number. Let $d$ be a given positive integer (with $d < \lfloor \lambda \rfloor$). Then I want to know the value of $$\displaystyle \sum_{\substack{w_1 x_1 + \cdots + w_{n-1} x_{n-1} \leq \lambda, \text{ } x_1 < d}} 1 $$ where the sum is over non-negative integers $x_1, \cdots x_{n-1}$.

If $w_1 = w_2 = \cdots = w_{n-1} = 1$ and $\lambda$ is a positive integer, then the above sum can be expressed as $$\displaystyle \sum_{x_1 + \cdots + x_n = \lambda} 1 - \sum_{x_2 + \cdots + x_n = \lambda - d} 1,$$ which can be expressed in closed form: $$\displaystyle \binom{\lambda + n - 1}{n-1} - \binom{\lambda - d + n - 1}{n-1}$$ which is equal to $$\displaystyle \frac{(\lambda + n-1) \cdots (\lambda + 1)}{(n-1)!} - \frac{(\lambda - d + n-1) \cdots (\lambda - d + 1)}{(n-1)!} = \frac{d\lambda^{n-2}}{(n-2)!} + O(\lambda^{n-3}).$$ Now my question is for arbitrary weights $(w_1, \cdots, w_{n-1})$ and $\lambda$ an arbitrary positive integer, can the same estimate hold? In particular, I am asking if the following equality holds: $$\displaystyle \sum_{\substack{w_1 x_1 + \cdots + w_{n-1} x_{n-1} \leq \lambda, \text{ } x_1 < d}} 1 = \frac{d\lambda^{n-2}}{w_1 \cdots w_{n-1} (n-2)!} + O(\lambda^{n-3})$$

A related question is whether the following weighted sum has a nice asymptotic form as well:

$$\displaystyle \sum_{\substack{w_1 x_1 + \cdots + w_{n-1} x_{n-1} \leq \lambda, \text{ } x_1 < d}} w_1 x_1 + \cdots + w_{n-1} x_{n-1} $$

I suspect, based on the answer provided at Values of various weighted sums , that the asymptotic should be

$$\displaystyle \frac{ d\lambda^{n-1}}{w_1 \cdots w_{n-1} (n-2)!} + O(\lambda^{n-2}).$$

A third sum I want to estimate is when the weight of the summands need not be the same as the original weight. In particular, for integral weights $w_1, \cdots, w_{n-1}$ and $v_1, \cdots, v_{n-1}$ positive real numbers not identical to $w_1, \cdots, w_{n-1}$ and $\lambda$ a positive integer:

$$\displaystyle \sum_{w_1 x_1 + \cdots + w_{n-1}x_{n-1} = \lambda, x_1 < d} v_1 x_1 + \cdots + v_{n-1} x_{n-1}$$

Here I suspect the answer to be

$$\displaystyle \frac{d\lambda^{n-2}}{w_1 \cdots w_{n-1}(n-2)!} \left(\frac{v_1}{w_1} + \cdots + \frac{v_{n-1}}{w_{n-1}}\right) + O(\lambda^{n-3})$$

Any help would be much appreciated.

share|improve this question
    
I am fairly certain that in general you will need to use a generalized Euler-Maclaurin formula here, and would be very interested indeed to know if a simpler approach can work. I have some unpublished notes on this topic from some years back; feel free to contact me if this is of interest. –  Steve Huntsman Mar 6 '12 at 17:47
    
Yes that would be great... do you have any idea if any of the assertions in the question are true? –  Stanley Yao Xiao Mar 7 '12 at 0:21
add comment

1 Answer

up vote 9 down vote accepted

We might as well assume that $\lambda$ is an integer. Then your first sum is the coefficient of $x^\lambda$ in $$ F(x) =\frac{1+x^{w_1}+x^{2w_1}+\cdots+x^{(d-1)w_1}} {(1-x^{w_2})\cdots(1-x^{w_{n-1}})(1-x)}. $$ The Laurent expansion of $F(x)$ at $x=1$ begins $$ F(x) = \frac{d}{w_2w_3\cdots w_{n-1}}\frac{1}{(1-x)^{n-1}} +\cdots, $$ so the coefficient of $x^\lambda$ is asymptotic to $$ \frac{d}{w_2\cdots w_{n-1}}{-(n-1)\choose \lambda} \sim \frac{d}{w_2\cdots w_{n-1}}\frac{\lambda^{n-2}} {(n-2)!}, $$ agreeing with your first conjecture except that there is no $w_1$ in the denominator.

Addendum. For the second sum, define $$ G(x,y) = \frac{1+x^{v_1}y^{w_1}+\cdots+x^{(d-1)v_1}y^{(d-1)w_1}} {(1-x^{v_2}y^{w_2})\cdots(1-x^{v_{n-1}}y^{w_{n-1}})}. $$ Then the second sum is equal to the coefficient of $y^\lambda$ in $$ \frac{d}{dx} G(x,y)|_{x=1} = \frac{v_1y^{w_1}+\cdots+(d-1)v_1y^{(d-1)w_1}} {(1-y^{w_2})\cdots (1-y^{w_{n-1}})} $$ $$ + \sum_{k=2}^{n-1} \frac{(1+y^{w_1}+\cdots+y^{(d-1)w_1})v_k} {(1-y^{w_k})\cdot (1-y^{w_2})(1-y^{w_3})\cdots (1-y^{w_{n-1}})}. $$ The first term grows like $(1-y)^{-(n-2)}$ and thus is asymptotically negligible compared to the remaining terms (the sum from $k=2$ to $n-1$). Thus $$ \frac{d}{dx} G(1,y) \sim d\sum_{k=2}^{n-1} \frac{v_k}{w_k(w_2 w_3\cdots w_{n-1})} \frac{1}{(1-y)^{n-1}}. $$ The coefficient of $y^\lambda$ is asymptotic to $$ \frac{d}{w_2w_3\cdots w_{n-1}}\sum_{k=2}^{n-1}\frac{v_k}{w_k} \cdot \frac{\lambda^{n-2}}{(n-2)!}. $$ This agrees with the conjecture (up to computational error) except for the $w_1$ factor and $v_1/w_1$ term.

share|improve this answer
    
Is there any chance that the second conjecture is true? In the case I am interested I have $w_1 = 1$ anyway, so the correct form of the first conjecture yields the same thing as my original conjecture. –  Stanley Yao Xiao Mar 7 '12 at 3:20
    
I have added an addendum on the second conjecture. –  Richard Stanley Mar 7 '12 at 17:16
add comment

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.