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?
Best Answer
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.