Thanks, Victor! The picture of the 6-faced polyhedron projecting to an 8-sided polygon on page 2 gave me exactly the intuition I was hoping for (though it leaves unresolved the issue of the extension complexity of the pentagon). Jim Propp On Tuesday, May 28, 2013, 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
On Sun, May 26, 2013 at 10:52 AM, James Propp <jamespropp@gmail.com> wrote:
I remember convincing myself (back in high school) that (1,0,0,0,0), (0,1,0,0,0), (0,0,1,0,0), (0,0,0,1,0), and (0,0,0,0,1) formed the vertices of a regular pentagon in R^5. I suspect this is the kind of mistake everyone needs to make at least once.
Jim Propp
On Sunday, May 26, 2013, Adam P. Goucher <apgoucher@gmx.com> wrote:
A pentagon cannot be embedded on an integer lattice of any number of dimensions. Suppose it could. Let one of the vertices be at the origin, and the other two vectors represented by x, y.
Then cos^2(3pi/5) = (x.y)^2/((x.x)(y.y)) = a rational number.
But cos^2(3pi/5) is irrational.
I believe that the only regular polygons embeddable in Z^n are the triangle, square and hexagon. (I made an equivalent assumption to reduce the latest Project Euler problem to a number-theoretic bash. Unfortunately, it still takes 400 CPU-hours... :/)
Let's see if we can prove it. cos^2(pi - 2pi/n) being rational is equivalent to the real and imaginary parts of e^(2 pi i/n) being roots of quadratic equations. And that is equivalent to e^(2 pi i/n) having minimal (cyclotomic) polynomial of degree <= 2, i.e. phi(n) <= 2.
But the only n for which phi(n) <= 2 are 1, 2, 3, 4 and 6. QED.
Corollary: The only regular polytopes embeddable in Z^n (for any n) are:
Line segment {(0), (1)} Hexagon {(0,1,2),(0,2,1),{1,2,0},(2,1,0),(2,0,1),(1,0,2)} Simplex {(1,0,0,0,...,0), (0,1,0,0,...,0), ... (0,0,0,0,...,1)} Hypercube {(±1, ±1, ..., ±1)} Orthoplex {(±1,0,0,...,0), (0,±1,0,...,0), ... (0,0,0,...,±1)} 24-cell {(±2,0,0,0), (0,±2,0,0), (0,0,±2,0), (0,0,0,±2), (±1,±1,±1,±1)}
Sincerely,
Adam P. Goucher
----- Original Message ----- From: Bill Gosper Sent: 05/26/13 09:33 AM To: > _______________________________________________ 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