April 2009 - mathfun@mailman.xmission.com

[math-fun] muffin problem -- clusters and bounds
by Huddleston, Scott 01 Dec '17

01 Dec '17

I enclose examples of some of the bounds in my 28 Feb. post, and a derivation of the most involved example. S(12/7) = 3/7 = r/4 = (3-r)/3 Muffins: 1/7 * { [3,4]*12 } Persons: 1/7 * { [4*3]*4, [3*4]*3 } S(7/4) = 5/12 = (3-r)/3 = (2r-1)/6 Muffins: 1/12 * { [5,7]*6, [6*2] } Persons: 1/12 * { [5*3,6]*2, [7*3]*2 } S(40/23) = 19/46 = (2r-1)/6 = (12-5r)/8 Muffins: 1/46 * { [19,27]*24, [20,26]*12, [23*2]*4 } Persons: 1/46 * { [19*3,23]*8, [20*4]*3, [27*2,26]*12 } S(228/131) = 54/131 = (12-5r)/8 = (7r-6)/15 Muffins: 1/131 * { [54,77]*120, [55,76]*24, [57,74]*60, [65,66]*24 } Persons: 1/131 * { [54*3,66]*24, [54*2,55,65]*24, [57*4]*15, [77*2,74]*60, [76*3]*8 } S(449/258) = 319/774 = (7r-6)/15 = (73-32r)/42 Muffins: 1/774 * { [319,455]*210, [320,454]*30, [325,449]*42, [336,438]*30, [337,437]*90, [384,398]*42, [387*2]*5 } Persons: 1/774 * { [319*3,390]*42, [319*2,325,384]*42, [320*3,387]*10, [336,337*3]*30, [455*2,437]*90, [455,454,438]*30, [449*3]*14 } Here's a derivation of 449/258 example. 449 muffins -> 898 pieces, used in 124 4-parts with 496 pieces and 134 3-parts with 402 pieces. We split muffins between a 3-part and a 4-part when possible, but 4-parts contain 94 more pieces than 3-parts. We divide these 94 pieces (47 muffins) as evenly as possible among the 124 4-parts. 47 pairs of 4-parts contain both halves of a muffin, which I'll call an A^1 cluster and write A^1 = [a1*3,m]*2 where m denotes the two muffin halves and the other pieces are denoted a1, indicating a set of pieces of possibly different sizes that occure in A^1 clusters. 34 4-parts contain only muffin pieces whose mates appear in 3-parts. These I call A^0 clusters and write A^0 = [a0*4] The 449/258 example uses 30 A^0 clusters ([a0*4])*30 (120 a0 pieces, 30 4-parts) 47 A^1 clusters ([a1*3,m]*2)*47 (282 a1 pieces, 94 4-parts) Note that the A^1 cluster by itself sets an upper bound on S -- the cluster is 2 persons (size 2r), it cntains 1 complete muffin (size 1, pieces m*2), and it has 6 unmatched muffin pieces (a1*6), giving S(449/258) <= avg(a1) = (2r-1)/6. A^0 clusters also bound S by S(449/258) <= avg(a0) = r/4, but the A^1 cluster bound is tighter. Note that this (2r-1)/6 bound holds for examples 7/4 and 40/23. The muffin mates of a0 pieces (resp. a1 pieces) are z0 pieces (resp. z1 pieces). We distribute z0 and z1 pieces as evenly as possible across the 134 3-parts (402 pieces). With 282 z1 pieces, at least 14 3-parts must consist of only z1 pieces. These are Z^0 clusters, Z^0 = [z1*3] = [z10*3] where I refine piece labels so that z1 pieces appearing in Z^0 clusters are labelled z10. I create general Z^k clusters by finding minimal sets of persons that contain complete a0/z0 muffins. Maximally even distribution of the 120 z0 pieces places one per 3-part. Then a Z^1 cluster, closed under a0/z0 muffins, is Z^1 = [a0*4],[z0,z1*2]*4 = A^0,[z0,z11*2]*4 where z1 pieces appearing in Z^1 clusters are relabelled z11. Z^0 clusters bound S by S(449/258) <= avg(a10) = 1-avg(z10) = 1-r/3 = (3-r)/3 and Z^1 clusters provide an even tighter bound S(449/258) <= avg(a11) = 1-avg(z11) = 1-(5r-4)/8 = (12-5r)/8. The 449/258 example uses 14 Z^0 clusters = ([z10*3])*14 ( 42 z10 pieces, 14 3-parts) 30 Z^1 clusters = (A^0,[z0,z11*2]*4)*30 (240 z11 pieces, 120 3-parts) As before, we refine the labelling of a1 pieces into a10 and a11 pieces, according to z10 or z11 complements. The next level of clustering is constructed by taking closure under a10/z10 muffins. The 282 a1 pieces in the 47 A^1 clusters are divided into 240 a11 pieces and 42 a10 pieces. Thus at least 5 A^1 clusters must contain only a11 pieces, and with maximally even distribution we have 42 A^1 clusters with 1 a10 piece and 5 a11 pieces. Continuing to refine pieces according to their appearance in A^10 or A^11 clusters, we have A^10 = A^1 = {a110*6, ...} (6 a110 pieces and some other pieces) A^11 = Z^0, (A^1)*3 = (a111*15, ...) with 449/258 consisting of 5 A^10 clusters ( 5 A^1 clusters, 30 a110 pieces) 14 A^11 clusters (42 A^1 clusters, 252 a111 pieces) A^11 clusters provide bound S(449/258) <= avg(a111) = (7r-6)/15 The 449/258 example lies on the intersection of this bound and the next level cluster bound. The next cluster level takes a110/z110 muffin closure and induces clusters Z^10 = Z^1 Z^11 = A^10, (Z^1)*6 with 449/258 consisting of 0 Z^10 clusters 5 Z^11 clusters (i.e., only Z^11 clusters) and bound S(449/258) <= avg(a1111) = 1-avg(z1111) = (73-32r)/42. I conclude with some computer generated additional information on these bounds. If anyone sort of understands this post and would like to use my program as is (i.e., no manual and documentation is mostly my posts), drop me a note and I'll send the C++ source (300 lines). B<4>(r) = (1r-0)/4; S'(r) <= B<4>(r) on (3/2,2/1] tight bound on (3/2,8/5] and at r = (4+8k)/(2+5k) (3/2,8/5] contains mediant(3/2,8/5) = 11/7 S'( (3/2,8/5] ) = (3/8,2/5]; S'(11/7) = 11/28 B<>(r) = (1-0r)/2 B<4>(r) = B<>(r) at r = 2/1 = 2.0000000 S'(2/1) = 1/2 = 0.50000000 B<4,1>(r) = (3-1r)/3; S'(r) <= B<4,1>(r) on [12/7,2/1) tight bound on [9/5,2/1) and at r = (12+9k)/(7+5k) [9/5,2/1) contains mediant(9/5,2/1) = 11/6 S'( [9/5,2/1) ) = [2/5,1/3); S'(11/6) = 7/18 B<4>(r) = (1r-0)/4 B<4,1>(r) = B<4>(r) at r = 12/7 = 1.7142857 S'(12/7) = 3/7 = 0.42857143 B<4,1,1>(r) = (2r-1)/6; S'(r) <= B<4,1,1>(r) on (12/7,7/4] tight bound on (12/7,59/34] and at r = (21+59k)/(12+34k) (12/7,59/34] contains mediant(12/7,7/4) = 19/11 S'( (12/7,59/34] ) = (17/42,7/17]; S'(19/11) = 9/22 B<4,1>(r) = (3-1r)/3 B<4,1,1>(r) = B<4,1>(r) at r = 7/4 = 1.7500000 S'(7/4) = 5/12 = 0.41666667 B<4,1,1,1>(r) = (12-5r)/8; S'(r) <= B<4,1,1,1>(r) on [40/23,7/4) tight bound on [148/85,7/4) and at r = (80+148k)/(46+85k) [148/85,7/4) contains mediant(47/27,7/4) = 54/31 S'( [148/85,7/4) ) = [7/17,13/32); S'(54/31) = 51/124 B<4,1,1>(r) = (2r-1)/6 B<4,1,1,1>(r) = B<4,1,1>(r) at r = 40/23 = 1.7391304 S'(40/23) = 19/46 = 0.41304348 B<4,1,1,1,1>(r) = (7r-6)/15; S'(r) <= B<4,1,1,1,1>(r) on (40/23,228/131] tight bound on (40/23,1119/643] and at r = (228+1119k)/(131+643k) (40/23,1119/643] contains mediant(40/23,47/27) = 87/50 S'( (40/23,1119/643] ) = (142/345,265/643]; S'(87/50) = 103/250 B<4,1,1,1>(r) = (12-5r)/8 B<4,1,1,1,1>(r) = B<4,1,1,1>(r) at r = 228/131 = 1.7404580 S'(228/131) = 54/131 = 0.41221374 B<4,1,1,1,1,1>(r) = (73-32r)/42; S'(r) <= B<4,1,1,1,1,1>(r) on [449/258,228/131) tight bound on [9349/5372,228/131) and at r = (1347+9349k)/(774+5372k) [9349/5372,228/131) contains mediant(134/77,47/27) = 181/104 S'( [9349/5372,228/131) ) = [1107/2686,2267/5502); S'(181/104) = 75/182 B<4,1,1,1,1>(r) = (7r-6)/15 B<4,1,1,1,1,1>(r) = B<4,1,1,1,1>(r) at r = 449/258 = 1.7403101 S'(449/258) = 319/774 = 0.41214470 B<4,1,1,1,1,1,1>(r) = (61r-60)/112; S'(r) <= B<4,1,1,1,1,1,1>(r) on (449/258,764/439] tight bound on (449/258,149516/85913] and at r = (10696+149516k)/(6146+85913k) (449/258,149516/85913] contains mediant(449/258,764/439) = 1213/697 S'( (449/258,149516/85913] ) = (11909/28896,35408/85913]; S'(1213/697) = 32173/78064 B<4,1,1,1,1,1>(r) = (73-32r)/42 B<4,1,1,1,1,1,1>(r) = B<4,1,1,1,1,1>(r) at r = 764/439 = 1.7403189 S'(764/439) = 2533/6146 = 0.41213798 B<4,1,1,1,1,1,1,1>(r) = (1101-487r)/615; S'(r) <= B<4,1,1,1,1,1,1,1>(r) on [160212/92059,764/439) tight bound on [1313469/754729,764/439) and at r = (160212+6567345k)/(92059+3773645k) [1313469/754729,764/439) contains mediant(19549/11233,764/439) = 20313/11672 S'( [1313469/754729,764/439) ) = [1555262/3773645,111271/269985); S'(20313/11672) = 986147/2392760 B<4,1,1,1,1,1,1>(r) = (61r-60)/112 B<4,1,1,1,1,1,1,1>(r) = B<4,1,1,1,1,1,1>(r) at r = 160212/92059 = 1.7403187 S'(160212/92059) = 37941/92059 = 0.41213787

2 1

[math-fun] Isodiametric problem
by victor miller 16 Sep '10

16 Sep '10

A few days ago, at the AMS meeting, I saw a neat talk by Michael Mossinghoff about "isodiametic" problems -- e.g. Fix the diameter of a conv ex n-gon and ask for the ones with maximum perimeter. He reduced the problem to finding univariate polynomials whose non-zero coefficients alternate between +/- 1 and are divisible by a particular cyclotomic polynomial.. He was able to calculate all such up to about 500. Each such polynomial is compactly encoded by th length of the gaps between the non-zero terms. For small n almost all were periodic. He showed how a certain family of periodic constrctions give solutions, but as n got bigger the "sporadic" ones swamped them. He conjectued that these are eventually all of them. He had lots of pictures. The paper is not available yet. Victor

7 9

Re: [math-fun] Fast factoring ?? (really denesting)
by rwg＠sdf.lonestar.org 08 May '09

08 May '09

> On Fri, Dec 19, 2008 at 12:20 PM, <rwg(a)sdf.lonestar.org> wrote: > >> Amen. I've now tried ~ 10^8 cases of (a^(1/5)-b^(1/5))^(1/3) >> without further success, and for sqrt, only >> >> 3/5 4/5 3/5 2/5 2/5 4/5 1/5 1/5 >> 1/5 1/5 - 2 3 + 3 + 2 2 3 - 2 3 + 2 >> sqrt(4 - 3 ) = ---------------------------------------------------. >> 5 >> >> And, of course, these can only give pentanomials. >> --rwg >> ALGORISMIC MICROGLIAS > > I have no technical knowledge on denesting, but here is how I look at > the problem: > > Since sqrt( a^(1/5) + b^(1/5) ) = a^(-2/5) * sqrt( a + (a^4*b)^(1/5) > ), I'll consider only the form: sqrt( a + b^(1/5) ). If sqrt( a + > b^(1/5) ) could be denested, I'd expect it to be denested into the > form: > > x0 + x1*b^(1/5) + x2*b^(2/5) + x3*b^(3/5) + x4*b^(4/5). Notice that in the (comparatively easy) 4th root case, your conjecture catches 1/4 3/4 1/4 sqrt(161 - 12 5 ) = 2 5 - 3 sqrt(5) + 4 5 + 6 but not 1/4 1/4 1/4 3/4 3/4 1/4 sqrt(2) sqrt(31 - 4 3 5 ) = 3 5 - 2 sqrt(5) + 3 5 + 2 sqrt(3). > That's why I don't think you could find anything longer than > pentanomial. OTOH, sqrt( a^(1/7) + b^(1/7) ) is a better bet for > finding hexanomials or longer. Indeed, but the only one I've found so far is perversely pentanomial: 1/7 Sqrt(7 (2 - 2 )) 1/7 3/7 5/7 6/7 ------------------ = -1 + 2 2 + 2 + 2 - 2 . 1/14 2 > Just my 2 cents. > > Warut > You didn't propose 6th roots. Did you have reason to suspect that they are as infertile as they seem to be? --rwg PRECHRISTMAS PETRARCHISMS ALGORISMIC MICROGLIAS

17 71

Re: [math-fun] Devil in the Details
by Dan Asimov 30 Apr '09

30 Apr '09

I remember my H.S. algebra text had one of those boxed enrichment thingies on one page, that described the spiral of Theodorus and called it the "square-root sprial". Philip Davis in his book Spirals from Theodorus to Chaos, (A. K. Peters, Wellesley, MA, 1993) describes a formula for a smooth spiral interpolating the discrete points of the square-root spiral: T(x) = Prod_{k=1...oo} [(1 + i/sqrt(k)/(1 + i/sqrt(x + k))], -1 < x < oo. (This looks fairly close, at least, to what David wrote below.) In the March, 2004 American Mathematical Monthly, Detlef Gronau proves some characterizations of T as the unique interpolating function with certain nice properties: "The spiral of Theodorus", pp. 230-237. --Dan -------------------- David wrote: << I concocted the Spiral of Theodorus myself once. Though I figured it wasn't original, I am chagrined that I was beaten by 2500 years. It seemed clear to me that the vertices lie on some natural smooth curve. In the complex plane, the nth vertex is PROD(k = 1 to n; 1 + i/sqrt(k)) The best I could do with this is 1/sqrt(n!) PROD(k = 1 to n; sqrt(k) + i) which led me to believe the smooth curve might be akin to the gamma function, that is to say, well beyond my abilities. >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Devil in the Details
by Hans Havermann 30 Apr '09

30 Apr '09

Mathematician "E. Teuffel" is mentioned in a number of Google hits. Does anyone here what the "E" stood for? By the way, in a Wikipedia entry on the Spiral of Theodorus, he is called Frage von E. Teuffel, an unfortunate transcription error. :)

4 6

[math-fun] Mathematicians under pressure
by Hilarie Orman 29 Apr '09

29 Apr '09

If you saw a movie DVD on the shelf with the title "Fermat's Room", you'd surely have to watch it. There is indeed such a movie, and it is a mystery thriller involving mathematicians trapped in a small space. The movie begins with the assertion that you should leave if you don't know what a prime number is, and the first scene has an accessible explanation of Goldbach's Conjecture. Intriguing invitations to a mathematics gathering follow, and before you can finish "An elementary proof of the prime number theorem", the characters are in a seemingly pleasant remote location, anticipating a collegial workshop. Instead, they face death by mechanical presses as the room relentlessly contracts. Only by solving puzzles and entering the answers on a PDA can they delay their fate. The puzzles are ones you've heard before, and the group plows through them in valiant fashion, but they realize that they need to understand why they are in this predicament in order to save themselves. This leads to a multi-level problem solving session in which the characters try to analyze the puzzles, the mechanics of the room, how they came to be selected for this bizarre punishment, and who might be behind the plot. All the while the room gets smaller and smaller. As it turns out, the whole situation might be a cynical metaphor for megalomania of pursuit of mathematical glory. The immense rewards and adulation that would be the mantle of the one to prove Goldbach's Conjecture can cause an implosion of a person's moral center. As we have seen time and time again, mathematical discovery corrupts, and discovery of absolute quantities corrupts absolutely. Or something. At the end, one character makes the astonishing claim that the world is the same whether or not Goldbach's Conjecture is known to be true or not. Say what? The people behind this film must have been ... well, physicists or something. "Fermat's Room" is a movie that is just quirky enough to be entertaining. Rugged individualists will appreciate the graphic argument against seatbelts. For extra credit, watch it without subtitles (it's in Spanish).

1 0

Re: [math-fun] Fwd: almost minimal polynomial
by Phil Carmody 29 Apr '09

29 Apr '09

From: rcs(a)xmission.com > This looks like an interesting puzzle. > His sum of k = z^-3 + ... + z^3 can also be read as the sum > of a few cosines, or as the sum of a geometric series. It > should be easy to gather more data. I've already posted something very similar to NMBRTHRY and the OP. Here's a slightly faster Pari/GP script to aid the gathering of more data: ? least=.001;forstep(i=1,2000,2,z1=exp(2*Pi*I/i);for(k=1,i\2,if(gcd(k,i)>1,,z=z1^k;s=1;for(j=1,i\2,s+=z^j;r=2*real(s);d=abs(r-round(r));if(d>1e-20&&d<=least,least=d;print(i" ^"k" "j"\t"d)))))) Phil

1 0

Re: [math-fun] Devil in the Details
by rcs＠xmission.com 29 Apr '09

29 Apr '09

[For some reason I don't understand, the mailing list filtering software doesn't like this message. It's from Paul Payton. --Rich] -------------------- Date: Wed, 29 Apr 2009 13:10:08 -0700 Subject: RE: [math-fun] Devil in the Details From: "Payton, Paul" <paul.payton(a)lmco.com> I think "von Himmel" might have been a better ending name. Zehr lustig, mein Herren. -----Original Message----- From: math-fun-bounces(a)mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Wednesday, April 29, 2009 1:09 PM To: math-fun Subject: Re: [math-fun] Devil in the Details I think I'm missing a German joke. I know that "Frage von" means "question from", and "Antwort" must be "answer", but I don't know what "vom Heiligen" means. On Wed, Apr 29, 2009 at 3:55 PM, Thane Plambeck <tplambeck(a)gmail.com> wrote: [Hide Quoted Text] Antwort vom Heiligen solved this, I think On Wed, Apr 29, 2009 at 12:37 PM, Hans Havermann <pxp(a)rogers.com> wrote: Mathematician "E. Teuffel" is mentioned in a number of Google hits. Does anyone here what the "E" stood for? By the way, in a Wikipedia entry on the Spiral of Theodorus, he is called Frage von E. Teuffel, an unfortunate transcription error. :) _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun -- Thane Plambeck tplambeck(a)gmail.com http://thaneplambeck.typepad.com/

1 0

Re: [math-fun] Fwd: almost minimal polynomial
by Dan Asimov 29 Apr '09

29 Apr '09

I wonder if there's a connection with the fact that n=23 is the least n for which the cyclotomic ring Z[exp(2pi*i/n)] has non-unique factorization. (And all primes p >= 23 have the property that Z[exp(2pi*i/p)] is a non-UFD.) More monstrous moonshine? --Dan ----------- Rich wrote: << This looks like an interesting puzzle. His sum of k = z^-3 + ... + z^3 can also be read as the sum of a few cosines, or as the sum of a geometric series. It should be easy to gather more data. ----- Forwarded message from boston(a)MATH.WISC.EDU ----- Date: Wed, 29 Apr 2009 13:32:25 -0400 From: Nigel Boston <boston(a)MATH.WISC.EDU> When computing the Koetter-Vontobel lower bound for minimum pseudoweight of the binary Golay code, a certain term came out as 15.9996. My engineering collaborator rounded this to 16 but the fact that it's so close to an integer but not actually an integer is in itself interesting. The term is actually 4+2k, where k = z^-3 + z^-2 + z^-1 + 1 + z + z^2 + z^3 and z is the 23rd root of unity exp(2\pi i/23). k is 5.99977967. . . . >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Fwd: almost minimal polynomial
by rcs＠xmission.com 29 Apr '09

29 Apr '09

This looks like an interesting puzzle. His sum of k = z^-3 + ... + z^3 can also be read as the sum of a few cosines, or as the sum of a geometric series. It should be easy to gather more data. Rich ----- Forwarded message from boston(a)MATH.WISC.EDU ----- Date: Wed, 29 Apr 2009 13:32:25 -0400 From: Nigel Boston <boston(a)MATH.WISC.EDU> Reply-To: Nigel Boston <boston(a)MATH.WISC.EDU> Subject: almost minimal polynomial To: NMBRTHRY(a)LISTSERV.NODAK.EDU When computing the Koetter-Vontobel lower bound for minimum pseudoweight of the binary Golay code, a certain term came out as 15.9996. My engineering collaborator rounded this to 16 but the fact that it's so close to an integer but not actually an integer is in itself interesting. The term is actually 4+2k, where k = z^-3 + z^-2 + z^-1 + 1 + z + z^2 + z^3 and z is the 23rd root of unity exp(2\pi i/23). k is 5.99977967. Is there some underlying reason why k is so close to 6 ? Alternatively, why is x^6 + x^5 + x^4 - 5x^3 + x^2 + x + 1 "almost" a minimal polynomial for z over Q ? I searched for similar examples but there are no better until you get up to 77th and 79th roots of unity (z = exp(2\pi i 12/77), sum from z^-20 to z^20 is 1.999833364548; z = exp(2\pi i 3/79), sum from z^-62 to z^62 is 5.9999365499). ----- End forwarded message -----

1 0