# Estimating the number of non-negative integer $n$-tuples satisfying two conditions

I am interested in computing the number of non-negative integral $n$-tuples $(x_1, \cdots, x_n)$ satisfying the following two conditions, as a function of the parameters $D,T, w_1, \cdots, w_n, v_1, \cdots, v_n$ where $w_1, \cdots, w_n \in \mathbb{N}, \gcd(w_1, \cdots, w_n) = 1$ and $v_1, \cdots, v_n > 0$ say, such that:

$$\displaystyle w_1 x_1 + \cdots + w_n x_n = D,$$ and $$\displaystyle v_1 x_1 + \cdots + v_n x_n \leq T.$$ The latter condition is stated as an inequality so that we do not have obstructions where $v_1, \cdots, v_n$ are not rational and so there are no solutions at all.

Obviously, if $T$ is sufficiently large relative to $D, v_1, \cdots, v_n, w_1, \cdots, w_n$ then the latter condition is vacuous; as every tuple that satisfies the first equality would satisfy the latter inequality. In that case the answer would be $$\displaystyle \sim \frac{D^{n-1}}{w_1 \cdots w_n (n-1)!}.$$ Conversely, if $T$ is sufficiently small relative to the rest of the parameters, then there would be no solutions at all.

I am trying to obtain a precise statement that estimates the count as a function of the parameters above, any help would be appreciated.

In particular, the following more refined question may be a better candidate: Suppose that $T$ is fixed, so that those $(x_1, \cdots, x_n) \in \mathbb{R}_{\geq 0}^n$ satisfying $$\displaystyle v_1 x_1 + \cdots + v_n x_n \leq T$$ form a bounded region $K$, and in particular there exist $D \in \mathbb{N}$ such that the number of solutions of integers $$\displaystyle w_1 x_1 + \cdots + w_n x_n = D$$ in $K$ is non-zero. What value of $D$, as a function of $T$ and the weights, maximize the number of solutions?

• Are you making some relative-primality assumptions? $w_1x_1+\cdots+w_nx_n=D$ will have no solutions if $D$ is not a multiple of the gcd of the $x_i$. – Gerry Myerson Sep 28 '13 at 23:54
• Yes, it is understood that $\gcd(w_1, \cdots, w_n) = 1$; in fact in the case I am interested in all but one of the $w_i$'s is equal to 1. – Stanley Yao Xiao Sep 29 '13 at 0:35
• You are looking for dimensions of the space of global sections of a line bundle on a toric variety of Picard number two. It helps to know something about the bundle, for example if it is numerically effective. Cohomology vanishing would be useful as well. (I am being a bit loose here with terminology: it's a line bundle on a stack, else you work with $\mathbb Q$-Cartier divisors.) What range of $D$ and $T$ are you interested in? – Lev Borisov Sep 29 '13 at 3:35
• @Lev Borisov: It is understood that both $D$ and $T$ can be taken to be arbitrarily large; and that $T$ can be taken as a suitable function of $D$. – Stanley Yao Xiao Sep 29 '13 at 11:54
• It would be reasonably easy to write asymptotic formula as $D=kD_0, T=kT_0$, $k\to \infty$. It would be related to the volume of the polytope given by inequalities for $D_0,T_0$. – Lev Borisov Sep 29 '13 at 12:13

For an $n$-tuple of natural numbers $w:=(w_1,\dots,w_n)$ as defined in the assumptions, let $\Sigma$ denote the $(n-1)$-dimensional symplex $\{x\in[0,\infty)^n\, : \, (w\cdot x) =1\}$.

The set of non-negative integer solutions $(x_1,\dots,x_n)$ to $w_1 x_1 + \cdots + w_n x_n = D,$ is then $S_D=D\Sigma \cap\mathbb{Z}^n$. What you want is a local version of the above mentioned Issai Schur's theorem, $$\operatorname{card} S_D\sim \frac{D^{n-1}}{w_1\dots w_n(n-1)!} \quad \mathrm{as}\quad D\to +\infty.\qquad \qquad \mathbf{(1)}$$

To make a convenient statement, let $C\subset\mathbb{R}^n$ be a cone (that is $\mathbb{R}_+C\subset C$) with topological boundary $\partial C$ of null $n$-dimensional Lebesgue measure. Then $$\lim_{D\to\infty}\frac{\operatorname{card}(S_D\cap C)}{\operatorname{card}S_D}=\frac{|\Sigma \cap C|}{|\Sigma| }.\qquad \qquad\mathbf{(2)}$$

This of course includes your asymptotic enumeration problem if we assume $T=\rho D$ for a fixed $\rho$, in which case we can choose $C$ to be the half-space $\{x\in\mathbb{R}^n\, : \, (\rho w - v )\cdot x \ge0 \}$. Then the case of $T=\rho D(1+o(1))$ can be treated by easy monotonicity arguments .

Also, for any $0$-homogeneous continuous function $f:\mathbb{R}_+^n\to \mathbb{R}$ one has

$$\lim_{D\to\infty} \frac{1 }{\operatorname{card}S_D } \sum_{x\in S_D} f(x)= \frac{1}{|\Sigma| } { \int_\Sigma f(\sigma)d \sigma }\, .\qquad \qquad\mathbf{(3)}$$ In other words, with a more measure theoretic language, the discrete uniform probability measures supported on $S_D\subset D\Sigma$, radially projected on $\Sigma$, that is $$\mu_D:=\frac{1}{\operatorname{card}S_D}\sum_{x\in S_D}\delta_{\frac{x}{D}}$$ weakly* converge to the (normalized) $(n-1)$-dimensional Lebesgue measure $\mu$ on $\Sigma$, as $D\to\infty$. Incidentally, the $(n-1)$-dimensional Lebesgue measure of $\Sigma$ is $$|\Sigma|=\frac{1}{w_1\dots w_n(n-1)!}\|w\|_2\, .$$

$$\mathbf{*}$$

Proof. Everything reduces to the observation that for special cones $C$, the limit (2) holds since it is equivalent to (1). The general case then follows by a density argument.

Precisely, for $\lambda:=(\lambda_1,\dots\lambda_n)\in\mathbb{R}_+^n$, consider $$C:=\{x\in \mathbb{R}^n\, :\, x_k\ge \lambda_k (w\cdot x),\quad k=1,\dots,n \}\, .$$ Then $S_D\cap C=S_D\cap\{x :\, x_k\ge \lceil\lambda_k D\rceil, \, k=1,\dots,n \}$, which is just a translated copy of the set $S_E$ by the vector $(\lceil\lambda_1 D\rceil,\dots, \lceil\lambda_n D\rceil )$, where $$E:=D- \sum_{i=1}^n w_i\lceil \lambda_i D\rceil\sim D(1 - (w\cdot\lambda)) \, ,$$ so $\operatorname{card}(S_D\cap C)=\operatorname{card}S_E$. By (1) $\operatorname{card}S_E \sim (E/D)^{n-1}\operatorname{card}S_D\sim(1-(\lambda\cdot w))^{n-1}\operatorname{card}S_D .$

On the other hand $\Sigma\cap C=(1-(\lambda\cdot w))\Sigma + \lambda$ so $|\Sigma\cap C|=(1-(\lambda\cdot w))^{n-1}|\Sigma|$, and (2) follows for cones $C$ of this special form.

In terms of the above sequence of measures, this means that $\mu_D(A)\to\mu(A)$ for all homotetic translated copies $A\subset \Sigma$ of $\Sigma$, which is enough to ensure the w* convergence (by approximating $f\in C(\Sigma)$ by linear combinations of characteristic functions of the above sets $A$, or observing that any w*-limit $\nu$ of a subsequence is absolutely continuous and has $d\nu/d\mu=1$).

• so how does the expected asymptotic formula depend on $(v_1, \cdots, v_n)$ say? – Stanley Yao Xiao Sep 30 '13 at 14:36
• in that case $C$ is a half-space; then $v$ and $T$ enter the formula (2) in the value of $|\Sigma\cap C|$, that can be easily computed in terms of $v$ and $T$. – Pietro Majer Sep 30 '13 at 20:34
• Did you understand what I wrote? – Pietro Majer Oct 15 '13 at 20:19
• I was on vacation and with limited internet access in the last three weeks. However, I still do not see how to get an explicit formula from what you wrote. – Stanley Yao Xiao Oct 23 '13 at 21:04
• Is there a reference (book or paper) on these formulas? – Stanley Yao Xiao Oct 28 '13 at 21:05