Re: [math-fun] Platonic regular polyhedra with integer vertices ?
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 http://cp4space.wordpress.com
----- 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't! Even in an infinite dimensional grid, the only regular polygons of finite size are triangles, hexagons, and squares. We could probably prescribe the nth coordinate of the kth vertex of a regular pentagon, say, but infinitely many coordinates would be nonzero, resulting in infinite size. And it would only approach regularity as we consider higher and higher dimensions." --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
No wonder that witches love pentagrams... Perhaps the Pentagon relies on 'curled up' dimensions? :=) At 03:43 AM 5/26/2013, Adam P. Goucher wrote:
A pentagon cannot be embedded on an integer lattice of any number of dimensions.
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't! Even in an infinite dimensional grid, the only regular polygons of finite size are triangles, hexagons, and squares. We could probably prescribe the nth coordinate of the kth vertex of a regular pentagon, say, but infinitely many coordinates would be nonzero, resulting in infinite size. And it would only approach regularity as we consider higher and higher dimensions." --rwg _______________________________________________ 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
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't! Even in an infinite dimensional grid, the only regular polygons of finite size are triangles, hexagons, and squares. We could probably prescribe the nth coordinate of the kth vertex of a regular pentagon, say, but infinitely many coordinates would be nonzero, resulting in infinite size. And it would only approach regularity as we consider higher and higher dimensions." --rwg _______________________________________________ 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
Conway and I looked at describing lattice-related things using extra integer coordinates in this paper: - *Low-Dimensional Lattices V: Integral Coordinates for Integral Lattices<http://neilsloane.com/doc/Me151.pdf> *, J. H. Conway and N. J. A. Sloane, *Proc. Royal Soc. London, Series A*, 426 (1989), pp. 211-232. See http://neilsloane.com/doc/Me151.pdf On Sun, May 26, 2013 at 12:03 PM, 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't! Even in an infinite dimensional grid, the only regular polygons of finite size are triangles, hexagons, and squares. We could probably prescribe the nth coordinate of the kth vertex of a regular pentagon, say, but infinitely many coordinates would be nonzero, resulting in infinite size. And it would only approach regularity as we consider higher and higher dimensions." --rwg _______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
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
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
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
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
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
participants (7)
-
Adam P. Goucher -
Charles Greathouse -
Henry Baker -
James Propp -
Neil Sloane -
Victor Miller -
Victor S. Miller