4
$\begingroup$

Let $\Omega = $ {$\omega_{i}$} be an ordered set of $n$ positive reals in the unit interval, $\omega_{1} \leq \cdots \leq \omega_{n} \leq 1$. Define the $n$-simplex $\Delta(\Omega; (\mathbb{R}^{+})^{n})$ by the non-negative points $(x_{1}, \dots, x_{n}) \subset (\mathbb{R}^{+})^{n}$ which satisfy the inequality \begin{eqnarray} \omega_{1} x_{1} + \cdots + \omega_{n} x_{n} \leq 1. \end{eqnarray} Let $X$ be a non-trivial subset of the integers $\mathbb{Z}^{n}$. Define $\Delta(\Omega, X) = X \cap \Delta(\Omega, (\mathbb{R}^{+})^{n})$. It is well-known that \begin{eqnarray} |\Delta(\Omega, \mathbb{N}^{n})| \leq \frac{1}{n!} \prod_{i = 1}^{n} \frac{1}{\omega_{i}} \quad \text{and} \quad |\Delta(\Omega, (\mathbb{Z}^{+})^{n})| \leq \frac{1}{n!} \left(1 + \sum_{i = 1}^{n} \omega_{i} \right)^{n} \prod_{i = 1}^{n} \frac{1}{\omega_{i}}, \end{eqnarray} where $\mathbb{Z}^{+}$ denotes the set of non-negative integers.

Question(s): For the given bounds above, are any sharper bounds known? Given the similarity in form, are there formulas for other $X$ sets, say for integers greater than some arbitrary integer $c$ or integers satisfying some congruence condition (e.g., $a \equiv b$ mod $d$)?

(Update) The theory of Ehrhart polynomials is relevant to the question above.

Question: Suppose I'd like to use the Ehrhart machinery to count the number of non-negative integer solutions of $a_{1} x_{1} + \cdots + a_{n} x_{n} \leq r$ for a non-negative integer $r$ and positive integers {$a_{i}$}. How does one proceed?

Thanks!

  • 0
    $\Delta$ is a set right? So are u talking about the cardinality of $\Delta$?2010-11-10
  • 0
    Ya understood. You were initially comparing a set with a number. Sorry for being so picky :)2010-11-10
  • 1
    You should expect the number to look like the volume of Delta if the omega_i are sufficiently small, with an error on the order of the surface area of Delta. If you want something more precise than this, then when the omega_i are rational you might want to look at the literature on Ehrhardt polynomials: http://en.wikipedia.org/wiki/Ehrhart_polynomial2010-11-11

2 Answers 2

3

In answer to your question on how one uses the Ehrhart machinery to count the number of lattice points in $a_1 x_1 + \cdots + a_n y_n \le r$ with integer $r$ and $a_i$ see these papers of Matt Beck on counting lattice points in rational simplices (and that simplex in particular.) Other papers his are probably also relevant. I am pretty sure that it is also covered in Computing the Continuous Discretely (It is worth reading regardless of whether it answers your question.)

  • 1
    That *Computing...* paper is definitely worth reading!2011-07-12
  • 0
    @Mariano Doh! Pronoun reference error2011-07-13
2

If $\omega_1 = \cdots = \omega_n = 1/k$ then the equation translates to

$\displaystyle x_1 + \cdots + x_n \leq k$

and so the number of non-negative integer solutions is $\binom{n+k-1}{k}$, which is roughly $n^k/k!$, compared to your estimate $k^n/n!$ (that's assuming $k$ is much smaller; if we assume $n$ is much smaller, we get your estimate).

By the way, how do you derive your own upper bound? I assume you start with the volume of the simplex $1/n!$ and then blow up dimension $i$ by $1/\omega_i$, getting your expression. How do you then relate it to the number of lattice points? You can easily construct a convex polytope of arbitrarily small area with arbitrarily many lattice points.