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
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@mailman.xmission.com > Subject: Re: [math-fun] Platonic regular polyhedra with integer vertices ? > > Cris Moore>What is the smallest number of dimensions in which we can > embed a pentagon with integer vertices? > > More generally, for an n-gon, the argument below suggests (I think) > that we need at least p-1 dimensions where p is the largest prime factor of n. > We can do a hexagon in three dimensions, but not, I think, in two. > > Cris > > On May 25, 2013, at 11:09 PM, Bill Gosper wrote: > > > Let's see. If a Platonic solid K can be embedded in R^3 with integer > vertices, then the center will be a rational point, so by an integer > expansion it, too, will be integer. So by an integer translation we > can assume K has integer vertices and center. > > Then the isometry group Isom(K) will be a subgroup of GL(3,Z), so in > particular GL(3,Z) must have an element g of order 5. Then a > primitive 5th root of unity must be an eigenvalue of g's matrix. But > such roots of unity have a minimal polynomial equal to (x^5-1)/(x-1) = > an integer polynomial of 4th degree, so can't be an eigenvalue of an > integer 3x3 matrix. > > No, That was DanA. > > http://www.tweedledum.com/rwg/rectarith12.pdf (end) illustrates hexagons in > R^3, > followed immediately by > > "How many dimensions before we see (regular) octagons, pentagons, > dodecagons, ...? > We won
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
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun