Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Qiaochu Yuan Dec 31 '09 at 20:28
    
Qiaochu, you're right, I'll fix that. –  Richard Jan 1 '10 at 0:04
    
Also, when all of the terms are linear there's no reason to say "polynomial"; usually one says "linear form." –  Qiaochu Yuan Jan 1 '10 at 22:14
    
Qiaochu, I changed it from 'polynomial' to 'expression'. Hopefully that should be less confusing for folks. –  Richard Jan 2 '10 at 2:33
    
It would be nice if you put the math inside dollars, and make the appropriate changes for suiting LaTeX. –  Anweshi Jan 4 '10 at 23:55
show 5 more comments

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  Richard Jan 3 '10 at 19:21
    
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. –  Richard Jan 3 '10 at 19:25
    
The link doesn't work for me! –  Ilya Nikokoshev Jan 5 '10 at 20:14
    
Urk! Not my fault! I've added a hopefully more stable link to a better reference by the same person. :) –  Sam Nead Jan 6 '10 at 0:12
    
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. –  Richard Jan 6 '10 at 1:28
add comment

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

share|improve this answer
    
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. –  David Speyer Jan 6 '10 at 12:13
    
And, yes, if you want to solve problems like this in practice, I recommend LattE. –  David Speyer Jan 6 '10 at 12:13
    
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. –  Richard Jan 6 '10 at 14:51
add comment

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.

share|improve this answer
    
"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. –  Richard Jan 2 '10 at 2:32
    
"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. –  Richard Jan 2 '10 at 2:50
    
Also, I'm not sure I understand the details concerning your point about using generating functions to count solutions for 'S'? –  Richard Jan 2 '10 at 2:53
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.