February 2009 - mathfun@mailman.xmission.com

[math-fun] Probability of a real polynomial's having all roots real
by Dan Asimov 10 Feb '09

10 Feb '09

Let c = (c_0,...,c_(n-1)) have the standard normal distribution on R^n, i.e., the c_k are independent real random variables, each with probability density given by d(x) = (1/(sqrt(2 pi)) exp(-x^2 / 2)) QUESTION: Find the probability f(n) that the polynomial P(x) = x^n + c_(n-1) x^(n-1) + ... + c_1 x + c_0 has all its roots real ? (It's easy to find an integral expression for f(2), but not a closed form.) Better yet, find an asymptotic expression for f(n) as n -> oo . --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] more Reflections on Orientation
by Fred lunnon 09 Feb '09

09 Feb '09

[With some trepidation, I'm risking re-opening the can of worms which got me (and the annelids) into hot water here a year ago ...] Summarising the situation as I currently view it, there are actually _two_ distinct kinds of orientation traditionally employed when discussing objects such as flats, spheres and more general manifolds under the action of spatial transformations such as isometries. Space for these purposes is also traditional: Euclidean, projective, inversive, or maybe elliptic, spherical, hyperbolic etc. The essential distinction is between orientation determined by the action of an isometry on the object itself, contrasted with determined by action on the complement. Into the first class fall cues such as the arrowhead on a line or "spear" in the plane, or the lettering on a banner in space; into the second, the left or right side of a line in the plane, or the colour scheme on one side of the banner. Why should the announcement of this notion cause such uncomprehending consternation among substantial numbers of my colleagues? The major reason is probably that for most purposes, it doesn't actually matter: if an object is subjected only to proper isometries [often referred to --- in a shorthand which might have been designed to perpetuate confusion over this matter --- "orientation preserving"] then cues of either type give the same result. It is only when one comes to consider the mysteries of improper ["orientation reversing"] isometries that an appalling anomaly becomes apparent: cues of different classes now (always) give inconsistent orientations! In attempting to put all this down coherently, I've run into another familiar elephant trap: nomenclature, over which I agonise endlessly in circles, and rarely with much success. I offer up the following alternatives for your consideration, and perhaps improvement: For the first class, "endogenous orientation" or "endo-sense" or "chirality"; for the second class, "exogenous orientation" or "exo-sense" or "chroma"; suggestions, anybody? Incidentally currently available coordinate systems might have been deliberately designed to exacerbate the situation (regarding user confusion, rather than etymological indecision). If the sign of the scale factor is interpreted as encoding orientation, rather than discarded as is traditional, then projective (homogeneous) matrices, as well as geometric (Clifford) algebras such as J.M.Selig's grade-4 algebra and my own DCQ algebra, all cope well with proper isometries, then lose it irreparably (in umpteen different ways) with improper. But I realised only recently that for Lie-sphere geometry there is light at the end of the Dupin cyclide. This is an inversive space, in which spheres (of codimension 1) are explicitly oriented via the sign of a radius component. In 3-space for instance, an appropriate grade-6 algebra has generaters x,y,z (axes), u,v (inversions) and r (radius), where x^2 = y^2 = z^2 = u^2 = +1, v^2 = r^2 = -1. And --- hallelujah --- under _all_ Lie transformations (including Euclidean, Moebius and Laguerre), exo-sense/chroma is transformed correctly! At last, a sign of divine favour? But soft ... why should either class be preferred to the the other? After all, they could be viewed (in a slightly nightmare scenario, it is true) as duals of one another. Well now --- there is in practice very little to choose between the algebra above and the alternative x^2 = y^2 = z^2 = u^2 = -1, v^2 = r^2 = +1 [it's the difference between Selig's algebra and DCQ's]. And lo' and behold: when the squared signs are reversed, the conserved orientation changes from exo-sense/chroma to endo-sense/chirality. Fred Lunnon

1 2

[math-fun] Coding + and = with digits inside an integer
by Eric Angelini 09 Feb '09

09 Feb '09

Hello Math-Fun, Hans Haverman has done a great job so far (work in progress): (...) [Hans]: We've already decided that the initial digit should not be "0". Let's add the proviso that the initial TWO digits should not be "+0". In addition, let us disallow ANY of the following substrings: {"++", "+00", "+01", "+02", "+03", "+04", "+05", "+06", "+07", "+08", "+09", "=00", "=01", "=02", "=03", "=04", "=05", "=06", "=07", "=08", "=09", "=+0"}. There might be other things we won't like, but let's see what we get so far... (...) Number of 6-digit solutions: =\+ 0 1 2 3 4 5 6 7 8 1 0 2 54 0 3 52 0 48 4 50 0 46 44 5 48 0 46 44 42 6 48 0 42 42 44 44 7 46 0 42 44 40 42 40 8 44 0 44 42 40 40 36 36 9 42 0 42 40 38 38 36 34 30 We see that coding '=' with 2 and '+' with 0 produces 54 terms (54 is the highest integer in the above array); this gives the longest finite sequence of 6-digit integers with such a substitution: S(6) = 112308, 112407, 112506, 112605, 112704, 112803, 132409, 132508, 132607, 132706, 132805, 132904, 142509, 142608, 142707, 142806, 142905, 152609, 152708, 152807, 152906, 162709, 162808, 162907, 172809, 172908, 182909, 308211, 407211, 409213, 506211, 508213, 509214, 605211, 607213, 608214, 609215, 704211, 706213, 707214, 708215, 709216, 803211, 805213, 806214, 807215, 808216, 809217, 904213, 905214, 906215, 907216, 908217, 909218. --- Full explanation and more (5-digit and 7-digit integer) here: http://www.cetteadressecomportecinquantesignes.com/DigitSubstitution.htm 8-digit results to come. Best, É.

1 0

[math-fun] New add-mult squares
by Christian Boyer 06 Feb '09

06 Feb '09

Help needed! Look at this matrix: 75 38 207 102 11 20 91 56 5 44 49 104 57 50 153 138 133 200 17 92 45 66 21 26 99 30 39 14 175 152 23 68 78 63 22 15 184 119 100 19 136 161 76 25 42 117 10 33 28 13 40 77 34 69 114 225 46 51 150 171 52 7 88 35 If you ADD the numbers of each row or column or diagonal, always the same sum S = 600. If you MULTIPLY the numbers of each row or column or diagonal, always the same product P = 67463283888000. This kind of object is called an additive-multiplicative (or addition-multiplication, or add-mult) magic square. Some few 8x8 and 9x9 squares are known: http://mathworld.wolfram.com/Addition-MultiplicationMagicSquare.html But larger squares (10x10 and above) are extremely rare, most of them being unknown. I have some new squares, from 10x10 to 25x25. But before their publication, I would like to be sure that they are fully correct. If you can help me, checking these squares (and that the n^2 used integers in each nxn square are distinct, very important...), send me a private message. Thanks in advance! Integer values < 15,000 Products P < 10^80 (multiprecision needed) Christian. www.multimagie.com/indexengl.htm

1 2

[math-fun] Muffin Calculations
by victor miller 04 Feb '09

04 Feb '09

I've been doing some calculations using MIP (mixed integer programming) related to the muffin problem. I've made a few observations that have apparently sped up some of the calculations by factors of over 1000. Here they are: 0) As Veit Elser suggested (below uses his scaling), if one has a putative lower bound u of the best minimum piece size, then one can determine if u really is a lower bound by checking feasibility of the MIP: sum_i x[i,j] = m for all j sum_j x[i,j] = n for all i y[i,j] = 0 or 1, and u*y[i,j] <= x[i,j] <= b*y[i,j] for all i,j and b is an upper bound for x[i,j] (we can take b = min(m,n)). One can then search for the true value of u by a binary search (at least within a given epsilon), for example. 1) There is a lot of symmetry in this MIP -- we can make arbitrary permutations of the rows and columns. It turns out (and it isn't immediately obvious -- see the paper "Double Orderings of (0,1) matrices" by Adolf Mader and Otto Mutzbauer in Ars Combinatorica, v 61 (2001), pp 81-95 -- that one can assume that the rows and columns of the y matrix are lexicographically sorted -- to ensure that one just interprets them as binary numbers (so that's a linear form). This observation alone sped things up (usually the infeasible case at the boundary) by factors of 1000. 2) As I mentioned before, if you are given a value of the y matrix you can determine the best u for that matrix by solving the linear program: maximize u, subject to sum_i x[i,j] = m sum_j x[i,j] = n if y[i,j] = 0, then x[i,j] = 0 if y[i,j] = 1 then u <= x[i,j] Using this observation one can quickly find the optimal value (but see below) as follows: fix an epsilon > 0 start with u=1, repeat the following: 1) Test feasibility of the MIP above. If it's feasible, let y be the y matrix that the MIP program gives you. Then solve the above LP for the maximum u given that y -- it will always be >= the old value of u. If it's not feasible output the previous value of u. 2) Set u = u + epsilon, and go back to (1). Note that doing this will cut off the previous y solution. This procedure always climbs very quickly to what turns out to be the best value of u. Virtually all the time spent is in showing the infeasibility of optimal(u) + epsilon. Victor

1 0

Re: [math-fun] muffin problem
by James Propp 04 Feb '09

04 Feb '09

One might view Mike Reid's "T(m,n)" version of the muffin problem in the broader context of finding the coarsest common refinement of two partitions of the number 1, where "coarsest" means "with smallest part as large as possible". However, David Eppstein tells me that even deciding whether one partition is a refinement of another partition is NP-hard; it has bin packing (or 3-partition) as a special case. Jim Propp

1 0

[math-fun] add-mult magic squares
by Schroeppel, Richard 01 Feb '09

01 Feb '09

I'm curious about small addition-multiplication squares. Assume we ditch the integer requirement, and allow real or complex numbers - presumably algebraic. We keep the requirement that the elements are distinct. If we drop the diagonals, then simple counting of constraints suggests there should be a 4x4 with a couple of degrees of freedom remaining; and there should be 5x5s for which the diagonals work. This seems like a good problem for multiple approaches: multivariate hill climbing; or some heavy-duty algebra. Rich

2 1