Re: [math-fun] Platonic regular polyhedra with integer vertices ?
This ultimately relies on a theorem of Yannakakis: suppose that the n-sides of the n-gon are given by equalities a_i . x = b_i (here a_i is a 2-vector, and b_i >= 0 is a scalar), and the vertices are v_i. The slack matrix associated with this is an n by n matrix whose (i,j)-th element is b_i - a_i . v_j (here . means dot product). Note that every entry in the matrix is nonnegative, since (0,0) is in the interior, we see that every point v in the n-gon must satisfy a_i . v <= b_i. A nonnegative factorization of an m by n nonnegative matrix A is a product of the form T U, where T is m by r and U is r by n and both T and U have nonnegative entries. The smallest r for which such a factorization exists is called the *nonnegative rank* of A. Yannakakis showed that the extension complexity (the smallest number of inequalities defining a polytope projecting to the original one) is exactly equal to the nonnegative rank of its slack matrix. Basically, you can see this by looking at {(x,y) | Ax + T y = b , y >= 0}. I just tried some software (called nimfa) to find nonnegative factorizations of a given rank (all the algorithms have a lot of randomness and try to find a good approximation of the form T U (i.e. A - TU is "small" for various definitions of small). It couldn't find a rank 4 approximation for the pentagon, but did find a rank 5 for the hexagon. Victor On Wed, May 29, 2013 at 9:22 AM, Charles Greathouse < charles.greathouse@case.edu> wrote: Can you give an example? I'm not quite sure how to apply that. Charles Greathouse Analyst/Programmer Case Western Reserve University ---------- Forwarded message ---------- From: Victor S. Miller <victorsmiller@gmail.com> Date: Tue, May 28, 2013 at 4:56 PM Subject: Re: [math-fun] Platonic regular polyhedra with integer vertices ? To: math-fun <math-fun@mailman.xmission.com> I don't know, but they can be obtained by nonnegative matrix factorization. When the nonnegative rank is small this should be practical. Victor Sent from my iPhone On May 28, 2013, at 16:39, Charles Greathouse <charles.greathouse@case.edu> wrote:
Are the actual minimal inequalities known, at least for small regular polygons?
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, May 28, 2013 at 4:22 PM, Victor Miller <victorsmiller@gmail.com wrote:
Jim, Look in the paper that I gave a link to. The actual number of inequalities is 2*ceil(log_2 n). They have a picture of realizing the octagon with 6 inequalities (and a projection). They also give an algorithm to find the inequalities. These aren't necessarily the minimal number.
Later in the paper they show that there are n-gons (not regular) whose coordinates are in [0..n] x [0..n^2] which can't be realized with fewer than sqrt(n)/sqrt(log n) (here I've suppressed absolute constants).
Victor
On Sun, May 26, 2013 at 2:13 PM, James Propp <jamespropp@gmail.com> wrote:
Victor,
Could you explain how this works for the specific case of the regular pentagon? I am assuming that "log_2 n inequalities" means "at most floor(log_2 n) inequalities" or "at most ceiling(log_2 n) inequalities"; either way, that means fewer than 5 inequalities when n=5, so there's something surprising going on with the pentagon example that would presumably illuminate the general case.
Jim Propp
On Sunday, May 26, 2013, Victor Miller <victorsmiller@gmail.com> wrote:
Here's something somewhat related: To describe a regular n-gon in the plane you need n inequalities. However, suppose you allow an "extended formulation" -- introduce extra dimensions, and describe a polytope there whose projection to the plane is regular n-gon. The surprising result is that you can describe such a polytope in log_2 n inequalities. Here's some generalizations of that: http://arxiv.org/pdf/1107.0371.pdf
Victor
What's known about how many faces a k-dimensional projection of an n-simplex, n-cube, or n-orthoplex can have? More generally, one can consider a fixed high-dimensional polytope and ask how many faces its lower-dimensional shadows can have; this is dual to the problem we've been discussing. Jim On Wednesday, May 29, 2013, Victor Miller <victorsmiller@gmail.com> wrote:
This ultimately relies on a theorem of Yannakakis: suppose that the n-sides of the n-gon are given by equalities a_i . x = b_i (here a_i is a 2-vector, and b_i >= 0 is a scalar), and the vertices are v_i. The slack matrix associated with this
is an n by n matrix whose (i,j)-th element is b_i - a_i . v_j (here . means dot product). Note that every entry in the matrix is nonnegative, since (0,0) is in the interior, we see that every point v in the n-gon must satisfy a_i . v <= b_i. A nonnegative factorization of an m by n nonnegative matrix A is a product of the form T U, where T is m by r and U is r by n and both T and U have nonnegative entries. The smallest r for which such a factorization exists is called the *nonnegative rank* of A. Yannakakis showed that the extension complexity (the smallest number of inequalities defining a polytope projecting to the original one) is exactly equal to the nonnegative rank of its slack matrix. Basically, you can see this by looking at {(x,y) | Ax + T y = b , y >= 0}. I just tried some software (called nimfa) to find nonnegative factorizations of a given rank (all the algorithms have a lot of randomness and try to find a good approximation of the form T U (i.e. A - TU is "small" for various definitions of small). It couldn't find a rank 4 approximation for the pentagon, but did find a rank 5 for the hexagon.
Victor
On Wed, May 29, 2013 at 9:22 AM, Charles Greathouse < charles.greathouse@case.edu> wrote: Can you give an example? I'm not quite sure how to apply that.
Charles Greathouse Analyst/Programmer Case Western Reserve University
---------- Forwarded message ---------- From: Victor S. Miller <victorsmiller@gmail.com> Date: Tue, May 28, 2013 at 4:56 PM Subject: Re: [math-fun] Platonic regular polyhedra with integer vertices ? To: math-fun <math-fun@mailman.xmission.com>
I don't know, but they can be obtained by nonnegative matrix factorization. When the nonnegative rank is small this should be practical.
Victor
Sent from my iPhone
On May 28, 2013, at 16:39, Charles Greathouse <charles.greathouse@case.edu
wrote:
Are the actual minimal inequalities known, at least for small regular polygons?
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, May 28, 2013 at 4:22 PM, Victor Miller <victorsmiller@gmail.com wrote:
Jim, Look in the paper that I gave a link to. The actual number of inequalities is 2*ceil(log_2 n). They have a picture of realizing the octagon with 6 inequalities (and a projection). They also give an algorithm to find the inequalities. These aren't necessarily the minimal number.
Later in the paper they show that there are n-gons (not regular) whose coordinates are in [0..n] x [0..n^2] which can't be realized with fewer than sqrt(n)/sqrt(log n) (here I've suppressed absolute constants).
Victor
On Sun, May 26, 2013 at 2:13 PM, James Propp <jamespropp@gmail.com> wrote:
Victor,
Could you explain how this works for the specific case of the regular pentagon? I am assuming that "log_2 n inequalities" means "at most floor(log_2 n) inequalities" or "at most ceiling(log_2 n) inequalities"; either way, that means fewer than 5 inequalities when n=5, so there's something surprising going on with the pentagon example that would presumably illuminate the general case.
Jim Propp
On Sunday, May 26, 2013, Victor Miller <victorsmiller@gmail.com> wrote:
Here's something somewhat related: To describe a regular n-gon in the plane you need n inequalities. However, suppose you allow an "extended formulation" -- introduce extra dimensions, and describe a polytope there whose projection to the plane is regular n-gon. The surprising result is that you can describe such a polytope in log_2 n inequalities. Here's some generalizations of that: http://arxiv.org/pdf/1107.0371.pdf
Victor
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A projection of an n-cube is known as a zonotope. Here's a short paper by Fukuda who gives bounds about faces, etc. of a zonotope: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.1132 Victor On Fri, May 31, 2013 at 3:34 PM, James Propp <jamespropp@gmail.com> wrote:
What's known about how many faces a k-dimensional projection of an n-simplex, n-cube, or n-orthoplex can have? More generally, one can consider a fixed high-dimensional polytope and ask how many faces its lower-dimensional shadows can have; this is dual to the problem we've been discussing.
Jim
On Wednesday, May 29, 2013, Victor Miller <victorsmiller@gmail.com> wrote:
This ultimately relies on a theorem of Yannakakis: suppose that the n-sides of the n-gon are given by equalities a_i . x = b_i (here a_i is a 2-vector, and b_i >= 0 is a scalar), and the vertices are v_i. The slack matrix associated with this
is an n by n matrix whose (i,j)-th element is b_i - a_i . v_j (here . means dot product). Note that every entry in the matrix is nonnegative, since (0,0) is in the interior, we see that every point v in the n-gon must satisfy a_i . v <= b_i. A nonnegative factorization of an m by n nonnegative matrix A is a product of the form T U, where T is m by r and U is r by n and both T and U have nonnegative entries. The smallest r for which such a factorization exists is called the *nonnegative rank* of A. Yannakakis showed that the extension complexity (the smallest number of inequalities defining a polytope projecting to the original one) is exactly equal to the nonnegative rank of its slack matrix. Basically, you can see this by looking at {(x,y) | Ax + T y = b , y >= 0}. I just tried some software (called nimfa) to find nonnegative factorizations of a given rank (all the algorithms have a lot of randomness and try to find a good approximation of the form T U (i.e. A - TU is "small" for various definitions of small). It couldn't find a rank 4 approximation for the pentagon, but did find a rank 5 for the hexagon.
Victor
On Wed, May 29, 2013 at 9:22 AM, Charles Greathouse < charles.greathouse@case.edu> wrote: Can you give an example? I'm not quite sure how to apply that.
Charles Greathouse Analyst/Programmer Case Western Reserve University
---------- Forwarded message ---------- From: Victor S. Miller <victorsmiller@gmail.com> Date: Tue, May 28, 2013 at 4:56 PM Subject: Re: [math-fun] Platonic regular polyhedra with integer vertices ? To: math-fun <math-fun@mailman.xmission.com>
I don't know, but they can be obtained by nonnegative matrix factorization. When the nonnegative rank is small this should be practical.
Victor
Sent from my iPhone
On May 28, 2013, at 16:39, Charles Greathouse < charles.greathouse@case.edu
wrote:
Are the actual minimal inequalities known, at least for small regular polygons?
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, May 28, 2013 at 4:22 PM, Victor Miller <victorsmiller@gmail.com wrote:
Jim, Look in the paper that I gave a link to. The actual number of inequalities is 2*ceil(log_2 n). They have a picture of realizing the octagon with 6 inequalities (and a projection). They also give an algorithm to find the inequalities. These aren't necessarily the minimal number.
Later in the paper they show that there are n-gons (not regular) whose coordinates are in [0..n] x [0..n^2] which can't be realized with fewer than sqrt(n)/sqrt(log n) (here I've suppressed absolute constants).
Victor
On Sun, May 26, 2013 at 2:13 PM, James Propp <jamespropp@gmail.com> wrote:
Victor,
Could you explain how this works for the specific case of the regular pentagon? I am assuming that "log_2 n inequalities" means "at most floor(log_2 n) inequalities" or "at most ceiling(log_2 n) inequalities"; either way, that means fewer than 5 inequalities when n=5, so there's something surprising going on with the pentagon example that would presumably illuminate the general case.
Jim Propp
On Sunday, May 26, 2013, Victor Miller <victorsmiller@gmail.com> wrote:
Here's something somewhat related: To describe a regular n-gon in the plane you need n inequalities. However, suppose you allow an "extended formulation" -- introduce extra dimensions, and describe a polytope there whose projection to the plane is regular n-gon. The surprising result is that you can describe such a polytope in log_2 n inequalities. Here's some generalizations of that: http://arxiv.org/pdf/1107.0371.pdf
Victor
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
James Propp -
Victor Miller