|
26
|
|
edited Jan 6 2010 at 1:16 |
[One can now state the first part of the question as: given Imagine an n-simplex(, the solution set for the expressionbelow): $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, with 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 .
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.)
] - Resolved (See answer below.)
To push my luck... the second part of my question is, given some bounds on [$a_1$, $a_2$, ..., $a_n$] what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
|
25
|
|
edited Jan 5 2010 at 15:15 |
Update/Reformulation of question (let me know if the title change is inappropriate). Thanks so much to everyone for bearing with me here, and thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for polytopes.
First part RESOLVED (See my answer below) [One can now state the first part of the question as: given an n-simplex (the solution set for the expression below), with a single vertex on the origin, as well as on each axis at some arbitrary (strictly positive) distance from the origin, what is the lattice integer-point count?
Can 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.)
] - Resolved (See answer below.)
To push my luck... the second part of my question is, given some bounds on [$a_1$, $a_2$, ..., $a_n$] what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
|
24
|
|
edited Jan 5 2010 at 13:53 |
Update/Reformulation of question (let me know if the title change is inappropriate). Thanks so much to everyone for bearing with me here, and thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for polytopes.
First part RESOLVED (See my answer below)
[One can now state the first part of the question as: given an n-simplex (the solution set for the expression below), with a single vertex on the origin, as well as on each axis at some arbitrary (strictly positive) distance from the origin, what is the lattice integer-point count?
Can 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.)
]
To push my luck... the second part of my question is, given some bounds on [$a_1$, $a_2$, ..., $a_n$] what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
23
|
|
edited Jan 5 2010 at 13:37 |
Update/Reformulation of question (let me know if the title change is inappropriate). Thanks so much to everyone for bearing with me here, and thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for polytopes.
First part RESOLVED (See my answer below)
[One can now state the first part of the question as: given an n-simplex (the solution set for the expression below), with a single vertex on the origin, as well as on each axis at some arbitrary (strictly positive) distance from the origin, what is the lattice integer-point count?
Can 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.)
]
To push my luck... the second part of my question is, given some bounds on [$a_1$, $a_2$, ..., $a_n$] what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
|
22
|
|
edited Jan 5 2010 at 13:21 |
Counting lattice points for on an n-simplexpolytope
Update/Reformulation of question (let me know if the title change is inappropriate). Thanks so much to everyone for bearing with me here, and thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for polytopes.
One can now state the question as: given an n-simplex (the solution set for the expression below), with a single vertex on the origin, as well as on each axis at some arbitrary (strictly positive) distance from the origin, what is the lattice integer-point count?
Can 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 Wikipedia "Geometry for N-Dimensional Graphics" (http://en.wikipedia.org/wiki/Simplex#Example_in_3-dimensions_.28N.3D3.29) 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_2$-$v_0$ det([($v_1$-$v_0$), ... $v_{n-1}$-$v_0$ $v_n$-$v_0$)..., ($v_n$-$v_0$)])
(Problems writing LaTeX for matrices here, please see terms as column vectors to obtain square matrix.)
To push my luck... given some bounds on [$a_1$, $a_2$, ..., $a_n$] what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
|
21
|
|
edited Jan 5 2010 at 12:52 |
Lattice Counting lattice points of for an N-dimensional n-simplex polytopewith single vertices at integer distances along each axis
Update/Reformulation of question (let me know if the title change is inappropriate). Thanks so much to everyone for bearing with me here, and thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for polytopes.
One can now state the question as: given an N-dimensional polytope n-simplex (the solution set for the expression below), with a single vertex on the origin, as well as on each axis at some arbitrary (strictly positive) integer distance from the origin, what is the lattice integer-point count?
Is there a general solution for the volume of such a polytope (of some arbitrary dimension), such that we can
Can 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 Wikipedia (http://en.wikipedia.org/wiki/Simplex#Example_in_3-dimensions_.28N.3D3.29) 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:
$\dfrac{1}{n!}$ * det($v_1$-$v_0$ $v_2$-$v_0$ ... $v_{n-1}$-$v_0$ $v_n$-$v_0$).
To push my luck... given some bounds on [$a_1$, $a_2$, ..., $a_n$] what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
|
20
|
|
edited Jan 5 2010 at 8:40 |
Update/Reformulation of question (let me know if the title change is inappropriate). Thanks so much to everyone for bearing with me here, and thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for polytopes.
One can now state the question as: given an N-dimensional polytope (the solution set for the expression below), with a single vertex on each axis at some arbitrary (strictly positive) integer distance from the origin, what is the lattice integer-point count?
Is there a general solution for the volume of such a polytope (of some arbitrary dimension), such that we can use Ehrhardt polynomials to compute the integer point count?
To push my luck... given some bounds on [$a_1$, $a_2$, ..., $a_n$] what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
|
19
|
|
edited Jan 5 2010 at 8:33 |
Bounds on the sum 'S' for expressions Lattice points of the form: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = 'S', that allow for unique an N-dimensional polytope with single vertices at integer coefficients ($a_k$)distances along each axis
Update - Update/Reformulation of question (let me know if the title change is inappropriate). Thanks so much to everyone for bearing with me here, and thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for N-dimensional polytopepolytopes.
One can now state the question as: given an N-dimensional polytope , (the solution set for the expression belowbelow), with a single vertex on each axis at some arbitrary integer distance from the origin, what is the lattice integer-point countfor the polytope?
Is there a general solution for the volume of such a polytope , (of some arbitrary dimensiondimension), such that we can use Ehrhardt polynomials to compute the integer point count?
What
To push my luck... what is the maximum sum, 'S', of the integer distances from the origin to the vertices on each axis that allows for only a single lattice integer point?
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?
|
|
|
|
|
18
|
|
edited Jan 5 2010 at 8:26 |
Update - Thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for N-dimensional polyhedra, here defined by the expression: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = 'S', Where [$a_1$, $a_2$, ..., $a_n$] $\geq$ 0 are integers, and [$x_1$, $x_2$, polytope..., $x_3$] $\geq$ 0 One can be thought of now state the question asfixed-precision real-numbers or integers (transformed via : given an appropriate multiplicative factor). It seems like there should be N-dimensional polytope, the solution set for the expression below, with a single vertex on each axis at some analogue or extension of Pick's theorem (arbitrary integer distance from the literatureorigin, it appears that higher-dimensional extensions exist) that can be used to efficiently find what is the number of integer lattice points integer-point count for polyhedrathe polytope? Is there a general solution for the volume of such a polytope, as defined aboveof arbitrary dimension, once such that we know can use Ehrhardt polynomials to compute the volume. That should give you integer point count? What is the number maximum sum, 'S', of the integer solution sets [$a_1$, $a_2$, ..., $a_n$] which yield 'S' for a particular [$x_1$, $x_2$, ..., $x_n$]. Perhaps it would also allow one distances from the origin to quickly find the maximum value of 'S' vertices on each axis that allows for which only a unique solution set exists. single lattice integer point? Previous formulation of question: Imagine an expression of the form: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, where:
|
|
|
|
|
17
|
|
edited Jan 5 2010 at 2:11 |
Bounds on the sum 'S' for expressions of the form: a_1*x_1 $a_1$*$x_1$ + a_2*x_2 $a_2$*$x_2$ + ... + a_n*x_n $a_n$*$x_n$ = 'S', that allow for unique integer coefficients (a_k)$a_k$)
Update - Thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for N-dimensional polyhedra, here defined by the expression:
$a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = 'S',
Where [$a_1$, $a_2$, ..., $a_n$] $\geq$ 0 are integers, and [$x_1$, $x_2$, ..., $x_3$] >=0 $\geq$ 0 can be thought of as fixed-precision real-numbers or integers (transformed via an appropriate multiplicative factor).
It seems like there should be some analogue or extension of Pick's theorem (from the literature, it appears that higher-dimensional extensions exist) that can be used to efficiently find the number of integer lattice points for polyhedra, as defined above, once we know the volume. That should give you the number of integer solution sets [$a_1$, $a_2$, ..., $a_n$] which yield 'S' for a particular [$x_1$, $x_2$, ..., $x_n$]. Perhaps it would also allow one to quickly find the maximum value of 'S' for which only a unique solution set exists.
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?
Quick observation - If you allow integer coefficients of, say '$a_k$' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the expression) will increase exponentially as $max(a_k)^{n}$ = $30^{n}$ while the range of 'S' will grow only as a first-degree polynomial: ($max(a_1)^n*x_1 + max(a_2)^n*x_2 + ... + max(a_n)^n*x_n$) = ~($30^n*x_1 + 30^n*x_2 + ... + 30^n*x_n$).
Hence, I'm most interested in what one can say at the limit of a low number of different terms.
|
|
|
|
|
16
|
|
edited Jan 5 2010 at 2:06 |
Update - Thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for N-dimensional polyhedra, here defined by the expression:
a_1*x_1
$a_1$*$x_1$ + a_2*x_2 $a_2$*$x_2$ + ... + a_n*x_n $a_n$*$x_n$ = 'S',
Where [a_1, a_2, a_n] >=0 $a_1$, $a_2$, ..., $a_n$] $\geq$ 0 are integers, and [x_1, x_2, $x_1$, $x_2$, ..., x_3] $x_3$] >=0 can be thought of as fixed-precision real-numbers or integers (transformed via an appropriate multiplicative factor).
It seems like there should be some analogue or extension of Pick's theorem (from the literature, it appears that higher-dimensional extensions exist) that can be used to efficiently find the number of integer lattice points for polyhedra, as defined above, once we know the volume. That should give you the number of integer solution sets [a_1, a_2, $a_1$, $a_2$, ..., a_n] $a_n$] which yield 'S' for a particular [x_1, x_2, $x_1$, $x_2$, ..., x_n]. $x_n$]. Perhaps it would also allow one to quickly find the maximum value of 'S' for which only a unique solution set exists.
Imagine an expression of the form: a_1*x_1 $a_1$*$x_1$ + a_2*x_2 $a_2$*$x_2$ + ... + a_n*x_n $a_n$*$x_n$ = S, where:
- a_1
- $a_1$ through a_n $a_n$ are positive bounded integers
- x_1
- $x_1$ through x_n $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 $x_1$ through x_n) $x_n$) below which there is only one solution for positive integer coefficients a_1 $a_1$ through a_n? $a_n$? For example, given the expression a_1*98 $a_1$*98 + a_2*99 $a_2$*99 = 'S', where coefficients a_1 $a_1$ and a_2 $a_2$ = [1 through 100], one finds that you can always exactly recover the original a_1 $a_1$ and a_2 $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 $a_1$ through a_n $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?
Quick observation - If you allow integer coefficients of, say 'a_k' $a_k$' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the expression) will increase exponentially as max(a_k)^n $max(a_k)^{n}$ = 30^(n) $30^{n}$ while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*x_1 $max(a_1)^n*x_1 + max(a_2)^n*x_2 + ... + max(a_n)^n*x_nmax(a_n)^n*x_n$) = ~(30^n*x_1 ($30^n*x_1 + 30^n*x_2 + ... + 30^n*x_n)30^n*x_n$).
Hence, I'm most interested in what one can say at the limit of a low number of different terms.
|
|
|
|
|
15
|
|
edited Jan 4 2010 at 23:51 |
Update - Thanks to Sam Nead for pointing out that this problem statement is equivalent to a particular integer-point enumeration problem for N-dimensional polyhedra, here defined by the expression:
a_1*x_1 + a_2*x_2 + ... + a_n*x_n = 'S',
Where [a_1, a_2, a_n] >=0 are integers, and [x_1, x_2, ..., x_3] >=0 can be thought of as fixed-precision real-numbers or integers (transformed via an appropriate multiplicative factor).
It seems like there should be some analogue or extension of Pick's theorem (from the literature, it appears that higher-dimensional extensions exist) that can be used to efficiently find the number of integer lattice points for polyhedra as defined above. That should give you the number of integer solution sets [a_1, a_2, ..., a_n] which yield 'S' for a particular [x_1, x_2, ..., x_n]. Perhaps it would also allow one to quickly find the maximum value of 'S' for which only a unique solution set exists.
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?
Quick observation - If you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the expression) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*x_1 + max(a_2)^n*x_2 + ... + max(a_n)^n*x_n) = ~(30^n*x_1 + 30^n*x_2 + ... + 30^n*x_n).
Hence, I'm most interested in what one can say at the limit of a low number of different terms.
|
|
|
|
|
14
|
|
edited Jan 2 2010 at 2:29 |
Bounds on the sum 'S' for polynomials expressions of the form: a_1*x_1 + a_2*x_2 + ... + a_n*x_n = 'S', that allow for unique integer coefficients (a_k)
Imagine a polynomial 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 polynomial expression
Can we say anything about the maximum value of 'S' (for a given r_1 x_1 through r_nx_n) below which there is only one solution for positive integer coefficients a_1 through a_n? For example, given the polynomial 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?
(I've removed the example about weighing a 'heterogeneous sack of marbles'. I feel that it was unnecessary and long-winded. However, I have saved the original version of this question and it can be restored if this change is unacceptable.)
Quick observation - If you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomialexpression) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 max(a_1)^n*x_1 + max(a_2)^n*r_2 max(a_2)^n*x_2 + ... + max(a_n)^n*r_nmax(a_n)^n*x_n) = ~(30^n*r_1 (30^n*x_1 + 30^n*r_2 30^n*x_2 + ... + 30^n*r_n)30^n*x_n).
Hence, I'm most interested in what one can say at the limit of a low number of different termsin the polynomial.
|
|
|
|
|
13
|
|
edited Jan 1 2010 at 17:40 |
Imagine a polynomial 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 polynomial
Can we say anything about the maximum value of 'S' (for a given r_1 through r_n) below which there is only one solution for positive integer coefficients a_1 through a_n? For example, given the polynomial 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?
(I've removed the example about weighing a 'heterogeneous sack of marbles'. I feel that it was unnecessary and long-winded. However, I have saved the original version of this question and it can be restored if this change is unacceptable.)
Quick observation - If you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n).
Hence, I'm most interested in what one can say at the limit of a low number of different terms in the polynomial.
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
12
|
|
edited Jan 1 2010 at 16:54 |
Imagine a polynomial 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 polynomial
Can we say anything about the maximum value of 'S' (for a given r_1 through r_n) below which there is only one solution for positive integer coefficients a_1 through a_n? For example, given the polynomial 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 here?) Are there nice methods used?] <-- This seems to accomplish this aside from using be a computer to scan through different values restricted/special case of the integer coefficientssubset-sum problem, so existing dynamic programming algorithms would work. Can one do better here?
(I've removed the example about weighing a 'heterogeneous sack of marbles'. I feel that it was unnecessary and long-winded. However, I have saved the original version of this question and it can be restored if this change is unacceptable.)
Quick observation - If you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n).
Hence, I'm most interested in what one can say at the limit of a low number of different terms in the polynomial.
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
11
|
|
edited Jan 1 2010 at 14:14 |
Counting multiple heterogenous marbles using only their combined massBounds on the sum 'S' for polynomials of the form: a_1*x_1 + a_2*x_2 + ... + a_n*x_n = 'S', that allow for unique integer coefficients (a_k)
I've changed the title to get rid of unnecessary and misleading terminology (thanks Qiaochu!), and I've also cleaned up the two questions I have about the system I'm describing. Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined mass representable as a limited-precision real number (all of these values are known to you). You are then handed the "closed" sack (i.e. contents are not visible to you), a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by measuring the total mass/weight on the scale. This should be similar to defining a polynomial 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(copy numbers of the different marbles),x_1 through x_n are positive bounded real numbers (masses of the different marble types) 'S' is the sum of the polynomial (i.e. total mass of the closed sack)Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem one wants to somehow 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 here?) Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients? I'm pushing my luck, but can we say anything about the maximum value of 'S' (for a given r_1 through r_n) below which there is only one solution for positive integer coefficients a_1 through a_n? For example, given the polynomial 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? Quick note - As one might expect, with fixed-precision real-number masses Above such a bound, and at the limit is there an efficient way to obtain all possible sets of integers a_1 through a_n that satisfy the relation for a large number of different marble types given 'S'? (Can the LLL or terms in PSLQ algorithms be used here?) Are there nice methods to accomplish this aside from using a computer to scan through different values of the polynomial), integer coefficients? (I've removed the information on individual marble copy numbers quickly becomes example about weighing a 'washed out'heterogeneous sack of marbles'. I.eI feel that it was unnecessary and long-winded. However, I have saved the original version of this question and it can be restored if this change is unacceptable.) Quick observation - If you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n). Hence, I'm most interested in what one can say at the limit of a low number of different marble typesterms in the polynomial.
|
|
|
|
|
10
|
|
edited Jan 1 2010 at 13:20 |
I've changed the title to get rid of unnecessary and misleading terminology (thanks Qiaochu!), and I've also cleaned up the two questions I have about the system I'm describing.
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined mass representable as a limited-precision real number (all of these values are known to you). You are then handed the "closed" sack (i.e. contents are not visible to you), a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by measuring the total mass/weight on the scale.
This should be similar to defining a polynomial 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 (copy numbers of the different marbles),
- x_1 through x_n are positive bounded real numbers (masses of the different marble types)
- 'S' is the sum of the polynomial (i.e. total mass of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem one wants to somehow 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 here?) Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
I'm pushing my luck, but can we say anything about the maximum value of 'S' (for a given r_1 through r_n) below which there is only one solution for positive integer coefficients a_1 through a_n? For example, given the polynomial 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?
Quick point note - As one might expect, with fixed-precision real-number masses, and at the limit of a large number of different marble types (or terms in the polynomial), the information on individual marble copy numbers quickly becomes 'washed out'. I.e. if you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n).
Hence, I'm most interested in what one can say at the limit of a low number of different marble types.
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
9
|
|
edited Jan 1 2010 at 13:10 |
I've changed the title to get rid of unnecessary and misleading terminology (thanks Qiaochu!), and I've also cleaned up the two questions I have about the system I'm describing.
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined mass representable as a limited-precision real number (all of these values are known to you). You are then handed the "closed" sack (i.e. contents are not visible to you), a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by measuring the total mass/weight on the scale.
This should be similar to defining a polynomial 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 (copy numbers of the different marbles),
- x_1 through x_n are positive bounded real numbers (masses of the different marble types)
- 'S' is the sum of the polynomial (i.e. total mass of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem one wants to somehow 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 here?) Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
I'm pushing my luck, but can we say anything about the maximum value of 'S' (for a given r_1 through r_n) below which there is only one solution for positive integer coefficients a_1 through a_n? For example, given the polynomial a_1*98 + a_2*99 = 'S' 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?
Quick point - As one might expect, with fixed-precision real-number masses, and at the limit of a large number of different marble types (or terms in the polynomial), the information on individual marble copy numbers quickly becomes 'washed out'. I.e. if you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n).
Hence, I'm most interested in what one can say at the limit of a low number of different marble types.
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
8
|
|
edited Jan 1 2010 at 13:03 |
The I've changed the title is awful and needs to be changed get rid of unnecessary and misleading terminology (Qiaochu's suggestion has helped so far)thanks Qiaochu!), but it's based on and I've also cleaned up the following example that's been troubling me:two questions I have about the system I'm describing. Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem one wants to somehow 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 to accomplish this?here?) It would be terrific to have some method to obtain a probabilistic estimate for the values of a_1 through a_n (i.e. the copy numbers for the different types of marbles). Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients? Update I'm pushing my luck, but can we say anything about the maximum value of 'S' for a given r_1 through r_n below which there is only one solution for a_1 through a_n? For example, given the polynomial a_1*98 + a_2*99 = 'S' where a_1, a_2 = [1 through 100], one finds that you can always exactly recover a_1 and a_2 if 'S' < 9899. Quick point - As one might expect, with fixed-precision real-number masses, and at the limit of a large number of different marble types (or terms in the polynomial), the information on individual marble copy numbers quickly becomes 'washed out'. I.e. if you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n).
|
|
|
|
|
7
|
|
edited Jan 1 2010 at 0:47 |
The title is awful and needs to be changed (Qiaochu's suggestion has helped so far), but it's based on the following example that's been troubling me:
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined mass representable as a limited-precision real number (all of these values are known to you). You are then handed the "closed" sack (i.e. contents are not visible to you), a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by measuring the total mass/weight on the scale.
This should be similar to defining a polynomial 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 (copy numbers of the different marbles),
- x_1 through x_n are positive bounded real numbers (masses of the different marble types)
- 'S' is the sum of the polynomial (i.e. total mass of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem , one wants to somehow 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 to accomplish this?)
It would be terrific to have some method to obtain a probabilistic estimate for the values of a_1 through a_n (i.e. the copy numbers for the different types of marbles). Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
Update - As one might expect, with fixed-precision real-number masses, and at the limit of a large number of different marble types (or terms in the polynomial), the information on individual marble copy numbers quickly becomes 'washed' outwashed out'. I.e. if you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n).
Hence, I'm most interested in what one can say at the limit of a low number of different marble types.
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
6
|
|
edited Jan 1 2010 at 0:41 |
|
|
|
|
|
|
5
|
|
edited Jan 1 2010 at 0:32 |
Ok, so the The title is awful and needs to be changed (Qiaochu's suggestion has helped so far), but it's based on the following example that's been troubling me:
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined mass representable as a limited-precision real number (all of these values are known to you). You are then handed the "closed" sack (i.e. contents are not visible to you), a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by measuring the total mass/weight on the scale.
This should be similar to defining a polynomial 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 (copy numbers of the different marbles),
- x_1 through x_n are positive bounded real numbers (weights masses of the different marble types)
- 'S' is the sum of the polynomial (i.e. total weight mass of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem, one wants to somehow 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 to accomplish this?)
It would be terrific to have some method to obtain a probabilistic estimate for the values of a1 a_1 through a_n (i.e. the copy numbers for the different types of marbles). Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
Update - As one might expect, with fixed-precision real-number masses, and at the limit of a large number of different marble types (or terms in the polynomial), the information on individual marble copy numbers quickly becomes 'washed' out. I.e. if you allow integer coefficients of, say 'a_k' = [0-30], and 'n' different terms, the number of possible values of 'S' (for the sum of the polynomial) will increase exponentially as max(a_k)^n = 30^(n) while the range of 'S' will grow only as a first-degree polynomial: (max(a_1)^n*r_1 + max(a_2)^n*r_2 + ... + max(a_n)^n*r_n) = ~(30^n*r_1 + 30^n*r_2 + ... + 30^n*r_n).
Hence, I'm most interested in what one can say at the limit of a low number of different marble types.
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
4
|
|
edited Jan 1 2010 at 0:10 |
Copy-numbers from the weight of a closed sack of Counting multiple heterogenous marbles using only their combined mass
Ok, so the title is awful and needs to be changed (Qiaochu's suggestion has helped so far), but it's based on the following example that's been troubling me:
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined weight mass representable as a limited-precision real number (all of these values are known to you). You are then handed the closed "closed" sack (i.e. contents are not visible to you), a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by weighing itmeasuring the total mass/weight on the scale.
This should be similar to defining a polynomial 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 (copy numbers of the marbles),
- x_1 through x_n are positive bounded real numbers (weights of the different marble types)
- 'S' is the sum of the polynomial (i.e. total weight of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem, one wants to somehow 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 to accomplish this?)
It would be terrific to have some method to obtain a probabilistic estimate for the values of a1 through a_n (i.e. the copy numbers for the different types of marbles). Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
3
|
|
edited Dec 31 2009 at 15:48 |
Ok, so the title is awful and needs to be changed, but it's based on the following example that's been troubling me:
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined weight representable as a limited-precision real number (all of these values are known to you). You are then handed the closed sack, a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by weighing it.
This should be similar to defining a polynomial 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 (copy numbers of the marbles),
- x_1 through x_n are positive bounded real numbers (weights of the different marble types)
- 'S' is the sum of the polynomial (i.e. total weight of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem, one wants to somehow 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 to accomplish this?)
It would be terrific to have some method to obtain a probabilistic estimate for the values of a1 through a_n (i.e. the copy numbers for the different types of marbles). Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
2
|
|
edited Dec 31 2009 at 13:17 |
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined weight representable as a limited-precision real number (all of these values are known to you). You are then handed the closed sack, a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by weighing it.
This should be similar to defining a polynomial 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 (copy numbers of the marbles),
- x_1 through x_n are positive bounded real numbers (weights of the different marble types)
- 'S' is the sum of the polynomial (i.e. total weight of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem, one wants to somehow 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 to accomplish this?)
Or in the absence of that, perhaps one wants
It would be terrific to have some method to obtain a probabilistic estimate for the value values of a1 through a_n (i.e. the copy numbers for the different types of marbles). Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
|
|
1
|
|
asked Dec 31 2009 at 13:07 |
Copy-numbers from the weight of a closed sack of heterogenous marbles
Imagine the scenario where someone fills a sack with 'n' different types of marbles (red/blue/green/etc), each type having a defined weight representable as a limited-precision real number (all of these values are known to you). You are then handed the closed sack, a fixed-precision scale, and asked to do your best to find how many copies of each marble type are inside the sack - only by weighing it.
This should be similar to defining a polynomial 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 (copy numbers of the marbles),
- x_1 through x_n are positive bounded real numbers (weights of the different marble types)
- 'S' is the sum of the polynomial (i.e. total weight of the closed sack)
Now, provided the values of x_1 through x_n, as well as the sum of the polynomial 'S', to solve the problem, one wants to somehow 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 to accomplish this?)
Or in the absence of that, perhaps one wants some method to obtain a probabilistic estimate for the value of a1 through a_n (i.e. the copy numbers for the different types of marbles). Are there nice methods to accomplish this aside from using a computer to scan through different values of the integer coefficients?
Note - Having read and thought a bit more about my previous question (and the LLL or PSLQ algorithms kindly suggested by Michael Lugo), this is bit of a follow-up. However, I felt that it was sufficiently different in nature to warrant a second posting (I can change the original if that's more reasonable).
Link to earlier question - http://mathoverflow.net/questions/10084/extracting-integer-multiplicative-factors-from-the-sum-of-certain-sets-of-finite
|
|
|
