Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
$\Delta$ is a set right? So are u talking about the cardinality of $\Delta$? –  user17762 Nov 10 '10 at 23:16
    
Ya understood. You were initially comparing a set with a number. Sorry for being so picky :) –  user17762 Nov 10 '10 at 23:20
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: en.wikipedia.org/wiki/Ehrhart_polynomial –  Qiaochu Yuan Nov 11 '10 at 0:11
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
That Computing... paper is definitely worth reading! –  Mariano Suárez-Alvarez Jul 12 '11 at 21:14
    
@Mariano Doh! Pronoun reference error –  deinst Jul 13 '11 at 2:48
add comment

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.

share|improve this answer
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.