Counting lattice points on an n-simplex - MathOverflow

Counting lattice points on an n-simplex

2009-12-31T13:07:19Z

Imagine an n-simplex, the solution set for the expression: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, where:

$a_1$ through $a_n$ are positive bounded integers
$x_1$ through $x_n$ are positive bounded real numbers
'S' is the sum of the expression

This n-simplex therefore has a single vertex on the origin, as well as a single vertex on each axis at some arbitrary (strictly positive) distance from the origin.

What is the lattice integer-point count?

Can one use Ehrhardt polynomials to compute the integer point count for the n-simplex, perhaps under the restriction that we have vertices strictly at integer coordinates?

From "Geometry for N-Dimensional Graphics" (by Andrew J. Hanson, CS Dept., Indiana University) we know that the oriented volume for the n-simplex with vertices {$v_1$, ..., $v_n$}, or {$a_1$*$x_1$, ..., $a_n$*$x_n$} is:

$V_n$ = $\dfrac{1}{n!}$ * det([($v_1$-$v_0$), ..., ($v_n$-$v_0$)])

(Problems writing LaTeX for matrices here, please see terms as column vectors to obtain square matrix.)

Previous formulation of question: Imagine an expression of the form: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, where:

$a_1$ through $a_n$ are positive bounded integers
$x_1$ through $x_n$ are positive bounded real numbers
'S' is the sum of the expression

Can we say anything about the maximum value of 'S' (for a given $x_1$ through $x_n$) below which there is only one solution for positive integer coefficients $a_1$ through $a_n$? For example, given the expression $a_1$*98 + $a_2$*99 = 'S', where coefficients $a_1$ and $a_2$ = [1 through 100], one finds that you can always exactly recover the original $a_1$ and $a_2$ if 'S' < 9899. Is there an analytical or more elegant method for obtaining that bound?

[Above such a bound, is there an efficient way to obtain all possible sets of integers $a_1$ through $a_n$ that satisfy the relation for a given 'S'? Can the LLL or PSLQ algorithms be used?] <-- This seems to be a restricted/special case of the subset-sum problem, so existing dynamic programming algorithms would work. Can one do better here?

Answer by Christopher Creutzig for Counting lattice points on an n-simplex

2010-01-01T20:00:31Z

~~From your problem description, I assume the $x_i$ from the first two paragraphs are what is called $r_i$ later.~~ I do not yet have a complete answer, but would like to point out some observations and ideas (sorry, I'm not allowed to write comments yet):

It seems to me that we can, without loss of generality, assume the $x_i$ to be commensurable. Otherwise, split $S\in\mathbb{Z}[x_1,\dots,x_n]$ into a representation wrt a basis of $\mathbb{Z}[x_1,\dots,x_n]$.

Thus, by multiplying through with a suitable constant, we can assume that the $x_i$ are positive integers. We may also assume $\gcd(x_1,\dots,x_n)=1$, since otherwise, any $S$ for which the equation has a solution is also divisible by this gcd, which allows dividing the whole equation. *Edit: Both of these simplifying assumptions shift the set of solutions (to solutions for some other $S$ and $r_1,\dots,r_n$, but in a bijective way.*

The number of solutions for any particular $S$ and $x_1,\dots,x_n$ can be counted using generating functions (similar to Polya's method for counting possibilities of giving change); with your example $S=98\,a_1+99\,a_2$ and $0 \leq a_1,a_2 \leq 100$, the number of solutions for $S$ is the coefficient of $x^S$ in the polynomial $(x^{98}+x^{2\cdot98}+\cdots+x^{100\cdot98})\,(x^{99}+x^{2\cdot99}+\cdots+x^{100\cdot99})$, whose lowest exponent with coefficient larger than $1$ is $9899$.

I'm not sure I've got a good way of explaining this. Essentially, the first of these polynomials is the generating function for the number of solutions for $S=98\,a_1$ and the second is the generating function for the number of solutions for $S=99\,a_2$. Since in these generating functions, the $S$ values are in the exponents, summation of the $S$ values corresponds to multiplication.

If you wanted to write a computer program to find the smallest $S$ such that the corresponding coefficient in the generating function as given above fulfills some condition (e.g., is larger than $1$), it would probably be a good idea to use standard written multiplication and use a heap structure for carrying out the steps. Such an implementation would provide a stream of coefficient/exponent pairs and can also use such as one of its two inputs, which means that the multiplication of very many polynomials can be performed with little memory overhead, especially without needing to store all the coefficients already checked and found not interesting, and the calculation can stop almost without computing anything beyond the first “interesting” term.

Answer by Sam Nead for Counting lattice points on an n-simplex

2010-01-03T00:04:27Z

I am informed that you are "counting lattice points inside of a polyhedron."

Here is a lecture on the subject - the picture on page six looks like the version of the problem you are interested in. To be honest, I found these notes by doing a google search. I am told that this is a huge field!

It might help if you could narrow your problem even further. For example, you say that the $x_i$ are bounded real numbers. Do you know these to some high precision? Or can you give some information on how the $x_i$ are given? And can you say the same for $S$?

EDIT: Here is a survey paper by the same author, Jesús De Loera, covering the same material in greater detail.

Answer by Richard for Counting lattice points on an n-simplex

2010-01-05T13:51:36Z

For a polynomial-time method of counting integer lattice points for the n-simplex (with fixed dimension):

Review article - Crites, A., Goff, M., Korson, M., Patrolia, L., Wolcott, L. "Counting Lattice Points in Polyhedra."

Available here with references for Barvinok's 1994 & 1999 algorithms - http://www.math.washington.edu/~thomas/teaching/m583_s2008_web/Barvinok.pdf

For an implementation of Barvinok's algorithm, see J.A. De Loera's LattE program (hosted at UC Davis): http://www.math.ucdavis.edu/~latte/group.htm