May 2013 - mathfun@mailman.xmission.com

Re: [math-fun] Platonic regular polyhedra with integer vertices ?
by Victor Miller 31 May '13

31 May '13

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(a)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(a)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(a)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(a)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(a)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(a)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(a)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 >>>> >>>>

2 2

[math-fun] Reduction - amplification
by Eric Angelini 31 May '13

31 May '13

Hello Math-Funsters, Take any positive integer and transform it via two successive operations – first reduction, then amplification. a) Reduction: all strings of same-parity digits are replaced par the sum of the said digits. Iterate the reduction if necessary. Example with 156186: 156186 – 66114 66114 – 1224 1224 – 18 b) Amplification: when an integer can no longer be reduced, replace every digit of it by its square (and concatenate the results). Thus 18 becomes: 18 – 164 Iterating the whole procedure gives (for 156186): 156186 – 18 – 2 – 4 – 16 – 136 – 10 – 10 – 10... [loop] Is there a positive integer somewhere which never loops? Is there a finite quantity of loops? 125 doesn’t end in the 10-loop: 125 – 1425 165 – 13625 485 125] --- We could test different amplification methods (keeping the reduction procedure) - for instance: a) instead of squaring the reduced digits, lift them to higher powers than 2 (d^3, d^4, d^5...) b) instead of powers, use multiplication (d becomes 2d, or 3d, or 4d, etc.) Is there a "more interesting" combination of reduction/amplification (in terms of results' variety)? Best, É.

1 0

[math-fun] Bracketings (where's David Gries when I need him?)
by Fred lunnon 31 May '13

31 May '13

[This may well be buried deep in Knuth's Art of Programming, or Arndt's fxtbook. But it proved a humbling exercise for this old coder, so I'm going to inflict it on everybody anyway.] The problem: given natural n , to generate in turn all sequences of n matched pairs of brackets; alternatively, ordered rooted trees with n+1 nodes, etc. --- see OEIS A000108. The solution should cost space linear in n , and (amortised) time constant per "bracketing" generated. My own current best effort below, hewed painfully from solid Maple, should give the general idea. [It employs a function with side-effects --- unavailable in some other languages, but easily circumvented.] While I suppose it's reasonably acceptable, I'm far from satisfied with all that fiddling with pointers that goes on in the middle. Can anybody manage something more elegant? Fred Lunnon ################################################################################ # Catalan number C(n) via recursion cat_rec := proc (n) local i,j,cati,cat; cat := array(0..n); cat[0] := 1; for i from 0 to n-1 do cati := 0; for j from 0 to i do cati := cati + cat[j]*cat[i-j] od; cat[i+1] := cati od; cat[n] end; # Matchings of n pairs of brackets, in reverse of reversed alphabetic order: # Seek leftmost P = Q [R] S with l > 1 ; # if R non-final, advance R and initialise everything Q to its left; # else relocate [ right then initialise shorter R and longer Q ; # Initial = [[...]] , final = []...[] ; # Right-hand sentinel ...[[[]]] -> ...[[][]] -> [...][[]] ; # Initialise bracketing of length 2 n init_bracket := proc (n, P) local j,l; l := 3; P := array(1..n+n+l+l); for j from 0 to n-1 do P[1+j+j] := +1; P[2+j+j] := -1 od; for j from 0 to l-1 do P[n+n+1+j] := +1; P[n+n+1+l+j] := -1 od; NULL end; # Next bracketing after P[i1] onwards, qua sequence +1,-1 for [,] ; # return highest index i altered, or 0 if P was final; # halt on return = n+n+2, start on n+n+3; next_bracket := proc (i0, P) local i,i1,i2,j,k,d; # P0 = P1 [P2] with P2 nonempty, or P1 ] ; # i1 = start P1, i2 = 1 + end P1 ; i1 := i0; d := 0; i := i1-1; while d = 0 or d = 1 do i := i+1; d := d+P[i] od; if d >= 0 then k := next_bracket(i, P) fi; # advance P2 ? if d < 0 then # P0 was final ...] i1 := i1+1; # shorten [P1] on left i2 := i+1; k := 0 elif k = 0 then # P2 was final ...[[ i2 := i+1; # lengthen P1 on right k := i else i2 := i-1 fi; # usual path for j from 1 to (i2-i1)/2 do # initialise P1 P[i1+j-1] := +1; P[i2-j] := -1 od; k end; switch := true; # test bracketings if switch then n := 4; cat_rec(n); init_bracket(n, P); cter := 0: print(cter, convert(P, list)); # pre-initial while next_bracket(1, P) <> n+n+2 do cter := cter + 1; print(cter, convert(P, list)) od: cter := cter + 1: print(cter, convert(P, list)); # post-final fi; # 14 # 0, [1,-1,1,-1,1,-1,1,-1,1,1,1,-1,-1,-1] # 1, [1,1,1,1,-1,-1,-1,-1,1,1,-1,1,-1,-1] (((()))) # 2, [1,1,1,-1,1,-1,-1,-1,1,1,-1,1,-1,-1] ((()())) # 3, [1,1,-1,1,1,-1,-1,-1,1,1,-1,1,-1,-1] (()(())) # 4, [1,1,1,-1,-1,1,-1,-1,1,1,-1,1,-1,-1] ((())()) # 5, [1,1,-1,1,-1,1,-1,-1,1,1,-1,1,-1,-1] (()()()) # 6, [1,-1,1,1,1,-1,-1,-1,1,1,-1,1,-1,-1] ()((())) # 7, [1,-1,1,1,-1,1,-1,-1,1,1,-1,1,-1,-1] ()(()()) # 8, [1,1,-1,-1,1,1,-1,-1,1,1,-1,1,-1,-1] (())(()) # 9, [1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1,-1] ()()(()) # 10, [1,1,1,-1,-1,-1,1,-1,1,1,-1,1,-1,-1] ((()))() # 11, [1,1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,-1] (()())() # 12, [1,-1,1,1,-1,-1,1,-1,1,1,-1,1,-1,-1] ()(())() # 13, [1,1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,-1] (())()() # 14, [1,-1,1,-1,1,-1,1,-1,1,1,-1,1,-1,-1] ()()()() # 15, [1,1,1,1,1,-1,-1,-1,-1,-1,1,1,-1,-1] ################################################################################

6 13

Re: [math-fun] Is the "LifeList" mailing list still active?
by Adam P. Goucher 29 May '13

29 May '13

> Dave Dyer wrote: > > The place to see is http://conwaylife.com/ No, it's actually not. There's still a private mailing list (now known as LifeCA), and it's still very much active. Sincerely, Adam P. Goucher

1 0

Re: [math-fun] Is the "LifeList" mailing list still active?
by Adam P. Goucher 29 May '13

29 May '13

Yes, and Dave Greene has archives dating from April 1992, when math-fun bifurcated. Sincerely, Adam P. Goucher http://cp4space.wordpress.com > ----- Original Message ----- > From: Allan Wechsler > Sent: 05/29/13 08:10 PM > To: math-fun > Subject: [math-fun] Is the "LifeList" mailing list still active? > > If it is, is it archived anywhere? > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2

[math-fun] Is the "LifeList" mailing list still active?
by Allan Wechsler 29 May '13

29 May '13

If it is, is it archived anywhere?

1 0

Re: [math-fun] Platonic regular polyhedra with integer vertices ?
by Adam P. Goucher 29 May '13

29 May '13

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(a)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(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

7 9

[math-fun] Type 3-1-3 babbling brook oscillators?
by Allan Wechsler 29 May '13

29 May '13

I was looking at simple formal structures for "babbling brook" type Life oscillators. If we had a babbling brook of length 3, where, when the brook was all dead, each end cell had 3 live neighbors and the middle cell had 1, we could see the following p4 oscillation pattern: 000, 101, 111, 010, and repeat. If such an oscillator exists, I can't find it. Is it possible to stabilize the bed of a type 3-1-3 oscillator?

1 0

Re: [math-fun] Einstein/Weinstein
by Adam P. Goucher 29 May '13

29 May '13

If this theory turns out to be correct, then it would be trivial to modernise this song: http://www.youtube.com/watch?v=weJeiN8IVTg Sincerely, Adam P. Goucher http://cp4space.wordpress.com > ----- Original Message ----- > From: Henry Baker > Sent: 05/24/13 06:48 PM > To: math-fun > Subject: Re: [math-fun] Einstein/Weinstein > > Not yet: > > "Until Weinstein produces a paper, physicists will remain unconvinced and, crucially, unable to properly assess the claims he is making. His lecture at Oxford today will give more mathematical details and Weinstein plans to put a manuscript on the Arxiv preprint server - a website where scientists often publish early drafts of their work, many of which subsequently get published in peer-reviewed journals." > > At 07:39 AM 5/24/2013, Warren D Smith wrote: > >is there a paper describing Weinstein's stuff? > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2

Re: [math-fun] Platonic regular polyhedra with integer vertices ?
by Bill Gosper 27 May '13

27 May '13

> On May 25, 2013, at 11:09 PM, Dan Asimov 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. >>>> >>>> Adam>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 >>>> >>>> > From: Warren D Smith >>>> Sent: 05/26/13 07:23 PM >>>> To: math-fun(a)mailman.xmission.com >>>> Subject: [math-fun] Embedding with integer coordinates >>>> >>>> If your thing has got two interpoint distances A,B such that (A/B)^2 >>>> is irrational, >>>> then its points cannot be be embedded in any finite dimension with >>>> integer coordinates. >>>> >>>> Regular pentagon, (A/B)^2=2.6180339887498948482 = g+1 >>>> where g=golden ratio >>>> where B=side, A=2-apart vertex sep >>>> >>>> icosahedron (including center as point) >>>> (A/B)^2 = sin(2*pi/5)^2 = (g/2)^2 + 1/4 =0.9045084971874737120 >>>> >>>> dodecahedron (ditto) >>>> (A/B)^2 = g^2 * (3/4) = 1.96352549156242113610 >>>> where A=radius, B=side >>>> >>>> all easily seen to be irrational, so none can be embedded. >>>> >>>> rwg> >>>> 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 >>>> >>>> --Eight(?) years ago I gave Julian, who is watching just my end of this >>>> discussion, a hardcopy of http://www.tweedledum.com/rwg/rectarith12.pdf >>>> >>> http://s216.photobucket.com/user/sjmathcircle/media/SJMC%2004-30-08/P430008… http://s216.photobucket.com/user/sjmathcircle/media/SJMC%2004-30-08/P430008… Last night he offered [Theorem: The only regular polygons embeddable in Z^n are triangles, squares, and hexagons.] On Sun, May 26, 2013 at 11:04 AM, Julian Ziegler Hunts <julianj.zh(a)gmail.com > wrote: > The proof: if we have a regular n-gon, we have two equally long vectors > making an angle of 2π/n. Then > cos^2(2π/n)=(u.v)^2/((u.u)*(v.v))=(u.v)^2/(u.u)^2 is a rational square, so > 2π/n is a rational angle with rational cosine, which only happens for > multiples of π/2 and π/3. The proof of that is something that I looked up > a while ago, maybe when we were doing radical denesting, and goes as > follows: Suppose cos(pπ/q) is rational. Then, since the map x->2x^2-1 > takes cos(t)->cos(2t) and rationals to rationals, cos(2^npπ/q) is > rational. Also, denominator(2x^2-1) is at least half the square of > denominator(x), and so is larger than denominator(x) when denominator(x) is > larger than 2. Since cosine has period 2π, and there are only finitely > many rationals in [0,2) with denominator at most q, we must have > cos(2^mpπ/q)=cos(2^npπ/q) for some m<n, so they have the same denominator. > Since cos(2^npπ/q) is the image of cos(2^mpπ/q) under n-m applications of > x->2x^2-1, this means that their denominators are ≤2, and therefore that > the denominator of cos(pπ/q) is ≤2. All rationals with denominator ≤2 are > accounted for by cosines of multiples of π/2 and π/3, so those are the only > rational angles with rational cosines. Note that a slight modification of > the above shows that the only rational angles achievable in Q^n are > multiples of π/4 and π/6. > > [Later:...] you could mention the extensions to higher dimensions (e.g. all but two of the (convex) regular polychora [namely, the 120- and 600-cell] can be embedded with integer coordinates), or other extensions of the question. And you could also add something about >4 dimensions (all embeddable) or nonconvex regular polytopes. Julian --rwg

1 0