5
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$ Commented Sep 28, 2013 at 23:54
  • $\begingroup$ 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. $\endgroup$ Commented Sep 29, 2013 at 0:35
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Sep 29, 2013 at 3:35
  • $\begingroup$ @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$. $\endgroup$ Commented Sep 29, 2013 at 11:54
  • $\begingroup$ 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$. $\endgroup$ Commented Sep 29, 2013 at 12:13

1 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ so how does the expected asymptotic formula depend on $(v_1, \cdots, v_n)$ say? $\endgroup$ Commented Sep 30, 2013 at 14:36
  • $\begingroup$ 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$. $\endgroup$ Commented Sep 30, 2013 at 20:34
  • $\begingroup$ Did you understand what I wrote? $\endgroup$ Commented Oct 15, 2013 at 20:19
  • $\begingroup$ 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. $\endgroup$ Commented Oct 23, 2013 at 21:04
  • $\begingroup$ Is there a reference (book or paper) on these formulas? $\endgroup$ Commented Oct 28, 2013 at 21:05

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.