5
$\begingroup$

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

  1. $a_1$ through $a_n$ are positive bounded integers
  2. $x_1$ through $x_n$ are positive bounded real numbers
  3. '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:

  1. $a_1$ through $a_n$ are positive bounded integers
  2. $x_1$ through $x_n$ are positive bounded real numbers
  3. '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?

$\endgroup$
10
  • $\begingroup$ As a general rule, it's mildly confusing to use words like "weight" and "closed," which have well-established mathematical meanings, in their non-mathematical senses to ask a mathematical question. $\endgroup$ Dec 31, 2009 at 20:28
  • $\begingroup$ Qiaochu, you're right, I'll fix that. $\endgroup$
    – Richard
    Jan 1, 2010 at 0:04
  • $\begingroup$ Also, when all of the terms are linear there's no reason to say "polynomial"; usually one says "linear form." $\endgroup$ Jan 1, 2010 at 22:14
  • $\begingroup$ Qiaochu, I changed it from 'polynomial' to 'expression'. Hopefully that should be less confusing for folks. $\endgroup$
    – Richard
    Jan 2, 2010 at 2:33
  • $\begingroup$ It would be nice if you put the math inside dollars, and make the appropriate changes for suiting LaTeX. $\endgroup$
    – Anweshi
    Jan 4, 2010 at 23:55

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Fascinating about counting lattice points in polyhedra... thinking about it, that's exactly equivalent to my problem specification. As to your second point: I'm somewhat interested in the relationship between the 'precision' to which the real numbers (or integer sizes after a transformation) are known and the max(S) value for which this is a unique solution for [a_1, a_2, ..., a_n], however, I don't have a particular precision/integer size in mind. $\endgroup$
    – Richard
    Jan 3, 2010 at 19:21
  • $\begingroup$ As for 'S', my original problem specification described an example where one has a bag filled with marbles of certain (known) mass values, though the copy numbers of each marble type are unknown. A game is then played where you have to weigh the bag, obtaining a total weight 'S', and then decide whether: (1) you can exactly extrapolate the copy numbers of each marble type, or (2) how well you can extract probabilities for copy numbers. I wanted to know if there were analytical methods available to accomplish this and/or the most efficient algorithmic solution. $\endgroup$
    – Richard
    Jan 3, 2010 at 19:25
  • $\begingroup$ The link doesn't work for me! $\endgroup$ Jan 5, 2010 at 20:14
  • $\begingroup$ Urk! Not my fault! I've added a hopefully more stable link to a better reference by the same person. :) $\endgroup$
    – Sam Nead
    Jan 6, 2010 at 0:12
  • $\begingroup$ Sam, thanks! I'm glad to see that I eventually found my way back to where you were pointing me. :) LattE is a pretty neat program. $\endgroup$
    – Richard
    Jan 6, 2010 at 1:28
4
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ One should note that Barvinok's algorithm in polynomial in $\log a_i$, for fixed $n$; it is exponential in $n$. I think that, if we are allowed to change $n$, this problem should be #P complete, but I don't know a reference. $\endgroup$ Jan 6, 2010 at 12:13
  • $\begingroup$ And, yes, if you want to solve problems like this in practice, I recommend LattE. $\endgroup$ Jan 6, 2010 at 12:13
  • $\begingroup$ David, good point about Barvinok's algorithm. I'll update the post when/if I run across the reference for the problem being #P-complete. $\endgroup$
    – Richard
    Jan 6, 2010 at 14:51
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ "I assume the xi from the first two paragraphs are what is called ri later." Yes, sorry about that. The x_k terms are the real numbers, but the use of r_k is just confusing. Fixed. $\endgroup$
    – Richard
    Jan 2, 2010 at 2:32
  • $\begingroup$ "We may also assume gcd(x_1, ..., x_n) = 1..." --> You would also have to divide 'S' in this case, which I define as fixed at some value. $\endgroup$
    – Richard
    Jan 2, 2010 at 2:50
  • $\begingroup$ Also, I'm not sure I understand the details concerning your point about using generating functions to count solutions for 'S'? $\endgroup$
    – Richard
    Jan 2, 2010 at 2:53

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.