January 2012 - mathfun@mailman.xmission.com

[math-fun] Littlewood dragons
by Mike Stay 06 Jan '12

06 Jan '12

A video by Greg Egan. http://vimeo.com/34550155 -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

1 0

Re: [math-fun] Biggest Little Octagon
by Dan Asimov 06 Jan '12

06 Jan '12

I'm not sure I understand what Wikipedia means here. What makes a solvable group of a given order "maximal" ? The fact that it's solvable implies its composition factors are Z/2Z, Z/3Z, Z/7Z. It could be Z/42Z or S_3 x Z/7Z or maybe some other things. And whatever maximal means, does there always exist a unique maximal solvable group of a given order (as "the maximal" below implies for 42) ? --Dan RWG mentioned: << http://en.wikipedia.org/wiki/Septic_equation sez "The Galois group <http://en.wikipedia.org/wiki/Galois_group> of this septic is the maximal solvable group of order 42." >> ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Biggest Little Octagon
by Bill Gosper 06 Jan '12

06 Jan '12

I couldn't express in radicals the (decic) Hexagon coordinates (http://mathworld.wolfram.com/GrahamsBiggestLittleHexagon.html) so I N A I V E L Y sought the Octagon. As far as I can Google, the univariate polynomials have never been written. A few hours with Resultant and 8G suggests why. If the bottommost vertex lies at (0,-1), the equation for the next-bottommost is 0= an (apparently irreducible) polynomial of degree 1872 with leading coefficient ~ 2.500474035501180*10^4244. The relevant root is ~-0.8946150293614985078063489766550846192654082886696687277707235119368\ 3381052661981830070725316844917984914222814666702729402156616431103191\ 5113334527424812898682528354633020185161200054393827649877953027688718\ 9821519807938387261042335825894072479219978185428285819499151742726948\ 1253539986988090644767767756895648857009098846656474169735583498317364\ 0417156963302378587405533205650717901440893242162746162522154127519400\ 68014831008223709670737308174873863117110982157364646771271039885075... This polynomial is so huge that it's not even possible to guess it by PSLQing the numerical solution to a multivariate partial solution. Apparently, it was not even clear until last year which equations to solve, i.e. which chords are unit length. --rwg

1 3

[math-fun] Equiripple approximations (Chebyshev)
by Warren Smith 06 Jan '12

06 Jan '12

> From: rwg(a)best.com > Message-Id: <200003260524.VAA21784(a)shell12.ba.best.com> > To: math-fun(a)optima.CS.Arizona.EDU > > A&S 9.1.44 with z=r, cos(theta) = t is > > inf > ==== > \ k > cos(r t) = 2 > (- 1) J (r) T (t) + J (r), > / 2 k 2 k 0 > ==== > k = 1 > > whose truncations give optimal (in the Tchebychev sense) approximations > to cos(r t) in [-1,1]. Thus, taking only terms 0,1, with r=pi/2, gives --RWG may be confused, anyhow this sentence was wrong. Specifically, Chebyshev series do NOT when truncated yield optimum i.e. equiripple approximations, though there are theorems and experience both saying that Chebyshev truncations usually are not too bad. To get the true equiripple there are proceudres such as Remez iteration that converge to it starting from good enough initial guess.

1 0

[math-fun] exact values of approximations
by Bill Gosper 06 Jan '12

06 Jan '12

Summary: The best (five extrema, equal ripple) quadratic approximation to cos(π x/2) on [-1,1] is -x^2 + (1/2)*(1 + x0^2 + Sqrt[Pi^2 - 16*x0^2]/Pi) where (4*x0)/Pi == Sin[(Pi*x0)/2] i.e., x0 = -(2nd) and 4th extrema ~ .6995333146440 . (which RIES inverts in .567 sec.) (Boy do we need the Kepler's eqn inverter fn.) Ripple amplitude = 1/2 - x0^2/2 - Sqrt[Pi^2 - 16*x0^2]/(2*Pi) ~ 0.0280048 So the coefficient(s), amplitude, and turning point are all expressible in terms of this single constant x0. http://pi.lacim.uqam.ca/eng/ gives no match. http://isc.carma.newcastle.edu.au/ and oldweb.cecm.sfu.ca/projects/ISC/ISCmain.html seem down. --rwg ---------------------------- Date: Sat, 25 Mar 2000 21:24:36 -0800 (PST) From: rwg(a)best.com Message-Id: <200003260524.VAA21784(a)shell12.ba.best.com> To: math-fun(a)optima.CS.Arizona.EDU A&S 9.1.44 with z=r, cos(theta) = t is inf ==== \ k cos(r t) = 2 > (- 1) J (r) T (t) + J (r), / 2 k 2 k 0 ==== k = 1 whose truncations give optimal (in the Tchebychev sense) approximations to cos(r t) in [-1,1]. Thus, taking only terms 0,1, with r=pi/2, gives %pi t %pi 2 %pi %pi cos(-----) ~ - 4 J (---) t + 2 J (---) + J (---) 2 2 2 2 2 0 2 2 ~ 0.9714045 - 0.99880666 t as the parabola "best" approximating the central arch of cos(pi t/2). The error ripple heights are ~ [0.028596, -0.028000, 0.027402] at 0, +-t0, and +-1, where t0 satisfies %pi t0 %pi sin(------) 2 t0 = ----------------- ~ .701432 . %pi 16 bessel_j (---) 2 2 While T_n is an equal-ripple approximation to 0 (amplitude 2^-n, when scaled to be monic), the cumulative effect of approximating all the higher order (>2) terms is no longer equal ripple, but is pretty close. In so simple a case, we can actually write the equal-ripple (Remez) coefficients, a and b, in %pi x 2 cos(-----) ~ a x + b, 2 to wit, 2 2 %pi x0 2 %pi x0 (%pi cos (------) - 8) sin (------) 4 4 a = - 1, b = mu + 1, mu = ------------------------------------, 8 where mu is the ripple amplitude and x0 is the turning point, satisfying %pi x0 %pi sin(------) 2 x0 = --------------- ~ 0.6995333, 4 nearly the same equation as for t0, the Tchebychev turning point. From this, or from the approximate equality of the lead coefficients, i.e., -1 ~ -4 J2(pi/2), we can expect J2(pi/2) to be nearly 1/4. In fact it's ~ .2497 . This x0 then gives mu ~ -0.028005 (necessarily edging out the Tcheby worst case of .0286 at the origin.) So the Remez approximation is %pi x 2 cos(-----) ~ 0.9719952 - x 2 (equal-ripple in [-1,1].)

1 0

[math-fun] Countdown to 2012
by Hans Havermann 06 Jan '12

06 Jan '12

10*9*8+7+6-5+4*321 Happy New Year!

2 1

[math-fun] Unique factorization (answers to RCS)
by Warren Smith 05 Jan '12

05 Jan '12

RC Schroeppel: Assuming some version of GRH, every [algebraic?] UFD has a hard-to-compute axiom-of-choice-style norm so that the Euclidean algorithm completes in four steps. [I've got some details wrong here, but you get the flavor.] This might be why the phrase 'Euclidean-for- the-norm' was introduced. 2^(1/5) generates a Euclidean field, with a not-too-hard dimishing norm. The idea is to compute the remainder's standard norm. If that's not smaller than norm(divisor), you adjust the quotient with a choice of ~50 values. Try adding +-1, +-2^1/5, +-4^1/5, etc. At least one will work. [This is my work, based on cutting up the unit cube into 100K boxes.] --well, that news sucks. If the reason this is hard is, the norms are incredibly hairy, then we're in trouble. RCS: [Hendrik?] Lenstra (in his thesis?) has a way of generating a lot of Euclidean fields. I never understood his trick, but it's not profound. --I think it's related to lattices and volumes. If you have a lattice in 3-space (or some dimensional space) and you have a convex body centered at origin, and maybe it has to be a centrosymmetric convex body, then if the convex body is large enough compared to the volume associated with any one lattice point, then body guaranteed to contain a lattice point. (Thm of Minkowski vastly generalizing the pigeonhole principle.) So in the Euclidean algorithm, have A & B, want to replace the bigger one B with "B mod A" which means B-k*A for some k. Well, note these points as k varies form a lattice, or translated lattice anyhow. To prove the euclidean algorithm descends you prove this lattice contains a smaller-norm point, which you do with Minkowski theorem or its ilk (in cases where you can make that work, anyhow). This sounds like a quite productive, easy. & obvious approach, but everybody since Minkowski has known about it, it is massively used for everything, so I doubt it'll work since if it did, they would have done it already? Or maybe I overestimate their wisdom. RCS: Puzzle on adjoining 1^(1/N): I though this was the distinction between regular & irregular primes, and there were about 50% each, empirically. This doesn't match the Masley-Montgomery result. What's my error? --I think your defn of regular & irregular primes is wrong. Kummer came up with "ideals" to get around the lack of unique factorization and still survive. RCS: What's an example of a totally-complex cubic field? :-)? --I think my defn of "totally complex" must have been wrong, I think I meant "complex" cubic field which is to say, not a totally-real one.

1 0

[math-fun] Unique factorization
by Warren Smith 05 Jan '12

05 Jan '12

> From: Dan Asimov > These rings are defined as the algebraic integers O_N of the field Q(sqrt(-N)). > > But in fact O_3 = Z[(sqrt(-3)+1)/2] and O_7 = Z[(sqrt(-7)+1)/2]. > > In Z[sqrt(-3)] we have (1+sqrt(-3))(1-sqrt(-3) = 2*2, and > in Z[sqrt(-7)] we have (1+sqrt(-7))(1-sqrt(-7) = 2*2*2, > showing non-unique factorization. --aha, thank you for saving me from this error, the rings are not defined the way I naively thought. There may be other cases of my naivete of this ilk in there too (?). Anyway, the BIG QUESTION I wanted to stick in your faces was, can we get an INFINITE SET of these normed-Euclidean rings? I mean, I don't see why this question has to be so hard it's been open for 80-200 years. What's the big deal? If there's a big infinite pile of these fields like the computers and Heilbronn say, then why can't you just invent some unified Euclidean algorithm for them, or anyhow enough of them, and game over?

1 0

[math-fun] Unique factorization
by Warren Smith 05 Jan '12

05 Jan '12

J.L.Masley & H.M.Montgomery 1975: if the Nth roots of unity (i.e. complex R such that R^N=1) are adjoined to the integers, then we get a ring enjoying "unique factorization into primes" exactly in the following cases: N = 1,3,4,5,7,8,9,11,12,15,16,20,24, 13,17,19,21,25,27,28,32,33,35,36,40,44,45,48,60,84. K.Heegner 1952 & H.Stark 1967: If sqrt(-N) is adjoined to the integers, N>0, then we get a ring enjoying "unique factorization into primes" exactly in the following cases: N = 1,2,3,7,11, 19,43,67,163. In both cases, for the N in the first line there is a known Euclid-like GCD algorithm which proves it. For the N in the second line, the proof is harder. The proof that no other N work is way harder. For example 6 = 2*3 = (1+i*sqrt5)*(1-i*sqrt5) has nonunique factorization for N=5. Exactly for N = 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 and -1,-2,-3,-7,-11, adjoining sqrt(N) to the integers yields a norm-lowering Euclidean algorithm. V.Cioffari 1979: Exactly for N = 2,3,10, adjoining cbrt(N) to the integers yields a norm-lowering Euclidean algorithm. [Also known we get finite sets for 4th roots and 5th roots.] Exactly for (A,B) in the following list, adjoining both sqrt(A) and sqrt(B) to the integers yields a ring with a norm-lowering Euclidean algorithm: (-1, 2), (-1, 3), (-1, 5), (-1, 7), (-2, -3), (-2, 5), (-3, 2), (-3, 5), (-3,-7), (-3, -11), (-3, 17), (-3, -19), (-7, 5) [F.Lemmermeyer 1989-1995] There are only finitely many cubic totally-complex or totally-real-cyclic algebraic number fields with a norm-lowering Euclidean algorithm (H.Davenport 1950; H.Heilbronn 1938). "Totally complex" means none of the roots of the minimal polynomial are real. Totally real means all of them are real. Here "cyclic" means that if you adjoin one root of the minimal polynomial, that is equivalent to adjoining all of them. Almost all cubic real fields are noncyclic. There are only finitely many quartic totally-complex and totally-real algebraic number fields with a norm-lowering Euclidean algorithm (H.Davenport 1950; F.Lemmermeyer 1995, D.A.Clark 1992-6). In all of the above cases, the list of rings was finite. Can we make some such list of N which is INFINITE? Apparently the answer is yes, but I'm not sure anybody has ever proved it in any interesting sense? Adjoining pi to the integers has unique factorization but it is boring/useless because it is nondiscrete and there is no way to multiply to ring elements to get an integer (aside from the obvious). Here are two apparently-infinite lists of N such that adjoining sqrt(N) to the integers yields a ring enjoying unique factorization http://oeis.org/A003172 http://oeis.org/A003655 but in these cases (a) I don't know if anybody ever proved they really are infinite -- I think the question is open -- albeit see H. te Riele & H.Williams: http://www.emis.de/journals/EM/expmath/volumes/12/12.1/pp99_113.pdf for large computations suggesting infinity; (b) even if they are infinite, I think it isn't very interesting/useful unless you have a Euclid algorithm so you can rapidly find GCD, and a notion of norm so we can talk about A being "smaller than" B and thus the "least" factor. These lists if restricted to such cases become finite. So... QUESTION: So what I want, but do not have, is an infinite set of ways to extend the integers into a larger countable ring (but still contained inside the reals or complex numbers or some finite-dimensional -- preferably bounded dimensional -- such space) so that (i) we get unique factorization via norm-based Euclidean algorithm. (ii) we get discreteness, i.e. the number of ring elements in any ball in the complex plane, or anyhow within some finite-dimensional space erected over the integers, is finite. This seems to force us to restrict to ALGEBRAIC number fields. Heilbronn 1938 and/or 1950 conjectured the number of cubic non-cyclic totally-real algebraic number fields with a norm-lowering Euclidean algorithm, was infinite. This conjecture if true would seem to solve my problem. However, I think this conjecture still is open, albeit seems supported by computer evidence, Lemmermeyer: http://www.rzuser.uni-heidelberg.de/~hb3/publ/survey.pdf

2 1

Re: [math-fun] pizza packing
by Bill Gosper 05 Jan '12

05 Jan '12

> I love that m=n sequence 2, 2, 1.942, 1.997, 1.951, 2, 1.942,... it's unlikely the values are the best possible for n>=6. > Are the exact polynomials available? for n=4, s=1+cos(t)-sin(t)+tan(t) at the t value that minimizes s. for n=5 and n=6, they were computed by david cantrell, and i have a mathematica notebook that probably contains some clue, but i'm afraid i can't decipher it. i'll be glad to e-mail it to you if you want. erich ------ Yow, an unsolvable quintic! --rwg

1 0