April 2016 - mathfun@mailman.xmission.com

Re: [math-fun] holding much water
by Henry Baker 05 Apr '16

05 Apr '16

I'm less worried about atmospheric percentages than I am about absolute amounts. Venus's atmosphere is so thick that it drowns a lot of percentages. For example, the last time I did the calculation, Venus has approximately the *same* *absolute* amount of nitrogen in its atmosphere as does the Earth. I'm not worried about helium & neon, as I doubt that they are important for life -- either for or against -- unless you consider the neon lights of sleazy bars & hotels to be important for nightlife. So that leaves us with hydrogen. Once again, it would be interesting to know the absolute amounts of hydrogen on Venus -- including whatever hydrogen is bound up in other compounds -- not necessarily water. I'm not suggesting that the Moon isn't important for life -- it probably is, and probably far more important than the magnetic field for life. The Earth's Moon has had an incredible stabilizing effect on the Earth's rotation and its axis, and the process of formation of the Moon -- most likely a large amount coming from the Earth itself after a massive collision -- may have made things much better for life -- perhaps doing something to get rid of the bulk of the Venus-type gasses in the atmosphere. At 04:19 PM 4/4/2016, Warren D Smith wrote: >>And how's that werkin' out fer ya, Venus? >>I would say that, based upon a comparison of Earth & Venus, that >>atmospheric stripping theory doesn't hold much water. > >--Atmospheric stripping presumably would be most severe for hydrogen >and helium and neon. Mercury & Mars both have stripped atmospheres. >And Venus's atmosphere contains only 12 ppm helium and >well below 1 ppm hydrogen. The latter is far below Earth's atmospheric >H percentage. Venus also has 7ppm Neon versus Earth's 18. >But Venus's He does exceed Earth's. (Could it be Venus gets "refueled" >with He from solar wind?) > >-- >Warren D. Smith >http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] Quickies
by Keith F. Lynch 05 Apr '16

05 Apr '16

Victor Miller <victorsmiller(a)gmail.com> wrote: > Gareth McCaughan <gareth.mccaughan(a)pobox.com> wrote: >> William R. Somsky wrote: >>> If done w/ sufficient resolution, and barring a measure-zero set >>> of coincidences, your procedure w/ N dead presidents should result >>> in N(N-1)/2 different orderings. And nice question -- I solved it >>> while driving in the car to get dinner. :-) >> I think you have an off-by-one error. .... >> (You get one *change* in ordering per "line joining two >> of the points", not one *ordering*.) Correct. > Very cute puzzle. Thanks. Coming up with interesting puzzles is often even more difficult than solving them. > Believe it or not, this is related to the clever algorithm of Nimrod > Megiddo for linear programming in 2 dimensions. The idea is that if > you have N linear inequalities in 2 dimensions (which is what this > problem had) the vertices of the polytope given by their intersection > come from intersections of of pairs of the lines (there might be > some degeneracy) which are N(N-1)/2. > Megiddo's idea for minimizing a linear form over the polytope was a > divide and conquer, which done cleverly, only took time *linear* in N. Interesting. I'm not a visual thinker, so I didn't solve the dead presidents puzzle visually. I did notice that it's the same solution as the number of orderings of distances to N random points on a line. I have no idea whether this is a coincidence, or whether in some sense these are the same puzzle. In other words, if you have N random points on a line, and you measure their distances from a point, there are always (except, again, in the case of measure-zero coincidences) exactly N(N-1)/2 + 1 possible different sort orders. Which sort order you get depends on where the point you measure the distance from is. That point doesn't have to be on the line. Also, if you have N random points in M-dimensional space, there are once again N(N-1)/2 + 1 possible different sort orders, *if* the points you measure the distances from are all constrained to a line. But now I'm wondering about the more general case. For instance the number of sort orders of distances to N random points in a plane, as measured from any point in the plane. I think it would not be a constant. Maybe I should write a simulation. For definiteness, I'll say the N points are distributed, with equal probability density per unit area, within a circle. The point the distances are measured from need not be within the circle. Would I get a different answer if, instead of a region of a plane, the distribution was over the whole of a sphere, a torus, or a Klein bottle? (Distances of course to be measured along the surface in each case.) What about instead of a Euclidian metric (sqrt(x^2+y^2)), using a Minkowski metric (sqrt(x^2-y^2))? But then how would I sort the imaginary distances?

7 9

Re: [math-fun] Quickies
by Keith F. Lynch 05 Apr '16

05 Apr '16

Andy Latto <andy.latto(a)pobox.com> wrote: > Here's a fallacious proof I came up with for the wrong answer. > I had fun figuring out the fallacy, so maybe some other funsters > will too. > For any two of the points, A, B, draw the perpendicular bisector of > AB. If we measure from a point on one side of this bisector, A will > come before B in the ordering, while if we measure from a point on > the other side, B will come before A. So with N points, we have > N(N-1)/2 bisectors dividing up the plane into regions, and we'll get > a different ordering for each region. If we have K lines in the > plane in general position, they divide the plane into K(K + 1)/2 + 1 > regions; this is easily seen by induction; when we add the K'th > line, it intersects the existing K-1 lines in K points, dividing it > into K pieces (K-2 segments and 2 rays); each piece divides one > planar region in 2, so we have added K regions, so K lines give us > the 1 region we start with plus 1 + 2 + 3 + .... + K more. > So with N points, we have N(N-1)/2 perpendicular bisectors, so they > divide the plane into > 1 + (N(N-1)/2)((N(N-1)/2) + 1) / 2 = (N^4 - 2 N^3 + 3 N^2 - 2N + > 8)/8 possible orderings. Since nobody has responded.... For any three of the points, the perpendicular bisectors will always meet at a point. Hence for 3 points the plane will be divided into 6 regions, not 7. For N points, the plane will be divided into N-choose-3 fewer orderings than you suggest. Disclaimer: I can't take full credit for this discovery. Some guy named Euclid beat me to it.

1 0

Re: [math-fun] Database of math problems
by Keith F. Lynch 05 Apr '16

05 Apr '16

"Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: > Meta-problem: Find a problem that doesn't generate anything > searchable. Not sequences, not large integers, not unusual real > numbers, not even unusual keywords. Bonus points if it's not > obvious what, if any, existing branch of math it belongs to. I think I found one. Ironically, it's the very example I used of what ought to be *easy* to look up! > How large a subset of the N^2 points on an N-by-N square grid can > there be with none of the distances between the points in the subset > being equal? > Thanks to Sloane, there's also a way to look it up: I could "solve" > it, by brute force, for the first few N, then look up the resulting > sequence in OEIS. If anyone has a general solution, that will point > me at it. I went ahead and tried exactly that, with a simple but slow and inefficient program. The solutions for N=0 through 6 are all equal to N. I'm not going to bother to look up 0,1,2,3,4,5,6 in OEIS. Any suggestions on how to solve this problem? Or rather, on how to search for some previous solution? (This is not a Costas array, lest anyone suggest it is.) I did prove that the solution for N can never exceed N. The number of possible distinct distances in an N by N grid is at best only slightly more than N-choose-2, the number of pairwise distances between N points. For N=15, it's equal, and for N>15 it's less, meaning that for N>15 the solution can be at most N-1. Similarly, for N>23 the solution can be at most N-2. (Both numbers look like they grow quadratically, but the number of possible distances actually grows more slowly due to collisions from pythagorean triples and other coincidences (e.g. 1^2 + 7^2 equals 5^2 + 5^2).) And of course the solution for N+1 can never be less than the solution for N, since you can simply reuse the previous solution, leaving the new row and new column empty. Other than that, I've gotten nowhere. Here's a sample solution for N=6. Observe that the 15 pairwise distances between the 6 points are all different. There are just 19 different distances possible in a grid this size, so just 4 aren't used in this solution. A 7th point would result in 21 pairwise distances, so no 7th point is possible. * - - - - - - - - - * * - - - * - - * - - - - - - - - - - - * - - - - -

2 1

Re: [math-fun] holding much water
by Warren D Smith 04 Apr '16

04 Apr '16

>And how's that werkin' out fer ya, Venus? >I would say that, based upon a comparison of Earth & Venus, that >atmospheric stripping theory doesn't hold much water. --Atmospheric stripping presumably would be most severe for hydrogen and helium and neon. Mercury & Mars both have stripped atmospheres. And Venus's atmosphere contains only 12 ppm helium and well below 1 ppm hydrogen. The latter is far below Earth's atmospheric H percentage. Venus also has 7ppm Neon versus Earth's 18. But Venus's He does exceed Earth's. (Could it be Venus gets "refueled" with He from solar wind?) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] Moon needed for earth's magnetic field to last?
by Henry Baker 04 Apr '16

04 Apr '16

And how's that werkin' out fer ya, Venus? I would say that, based upon a comparison of Earth & Venus, that atmospheric stripping theory doesn't hold much water. At 02:48 PM 4/4/2016, Scott Huddleston wrote: >So solar wind doesn't strip off the atmosphere. > >On Mon, Apr 4, 2016 at 2:37 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> Other than to align grazing cows in a N-S direction, why does "life" >> depend upon the Earth's magnetic field? >> >> http://news.nationalgeographic.com/news/2008/08/080825-magnetic-cows.html >> >> At 02:30 PM 4/4/2016, Warren D Smith wrote: >> >Denis Andrault, Julien Monteux, Michael Le Bars, Henri Samuel: >> >The deep Earth may not be cooling down, >> >Earth and Planetary Science Letters >> >Available online 30 March 2016 >> > >> >Claims without the moon, the Earth's core would have cooled and shut off >> >its magnetic field long ago. And we and most life would probably be in >> deep trouble. >> >Mercury, Venus, and Mars all lack magnetic fields (anyhow 100X below Earth's). >> >Which is presumably not a coincidence. But some Jupiter moons still have a field >> >exceeding any of the above 3 planets. Ditto. >> > >> >-- >> >Warren D. Smith >> >http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Moon needed for earth's magnetic field to last?
by Warren D Smith 04 Apr '16

04 Apr '16

Denis Andrault, Julien Monteux, Michael Le Bars, Henri Samuel: The deep Earth may not be cooling down, Earth and Planetary Science Letters Available online 30 March 2016 Claims without the moon, the Earth's core would have cooled and shut off its magnetic field long ago. And we and most life would probably be in deep trouble. Mercury, Venus, and Mars all lack magnetic fields (anyhow 100X below Earth's). Which is presumably not a coincidence. But some Jupiter moons still have a field exceeding any of the above 3 planets. Ditto. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] very cool perm poly decomposition over GF(p)
by Hilarie Orman 04 Apr '16

04 Apr '16

By using that magic thing called "the Internet", one can easily find that Susan Landau's doctorate predated the work in question by several years. She is a close friend and colleague of several people on this list. Hilarie

2 1

[math-fun] very cool perm poly decomposition over GF(p)
by Henry Baker 04 Apr '16

04 Apr '16

I just found a really cool polynomial decomposition algorithm which works beautifully for polys over GF(p) whose degree is <p, i.e., particularly those which are permutation polynomials. I believe this algorithm is due to Ms. Susan Landau (now @ WPI), although I can't be 100% sure about this w/o asking her. Decompose monic f(x) = g(h(x)), where deg(f)=n=r*s=deg(g)*deg(h), where g(x) and h(x) are also monic. Compute fbar(x) = reverse(f(x)) = x^n*f(1/x). Compute hbar(x) = r'th root of fbar(x) to precision (degree) s=n/r. This is well defined if r<p because hbar(0)=fbar(0)=1, as f(x) is monic, so fbar(0)=1. Use Newton iteration on power series approx. to r'th root of fbar(x). Compute h(x) = reverse(hbar(x)) = x^s*hbar(1/x). Express f(x) in base-h(x) notation using classical number base conversion algorithm. Each of the "digits" is a polynomial of degree <deg(h)=s. If each of the digits is actually a *constant* -- i.e., free of the variable x, then these "digits" are the coefficients of a polynomial g(x), and we have shown that f(x)=g(h(x)). Note that decomposition is essentially *cheaper* than factoring. Who knew? Cool ! (Note that although the paper looks to be behind a paywall, I was still able to download it, and can email you a copy if necessary.) J. Symbolic Computation (1990) 9, 281-299 Functional Decomposition of Polynomials: the Tame Case JOACHIM VON ZUR GATHEN Department of Computer Science, University of Toronto Toronto, Ontario MSS 1A4, Canada Using fast polynomial arithmetic as quoted above, we can implement the algorithm of Kozen & Landau (1989) very efficiently. For a polynomial f = x^n+a_n-1 x^(n-1) +...+ a_0 in F[x], we denote by fbar = a_0 x^n +...+a_n-1 x + 1 = x^n f(1/x) the reversal of f. Algorithm: Univariate decomposition. Input: f in F[x], monic of degree n = r s, and r in N, not divisible by char(F). Output: The unique normal decomposition (g,h) of f with deg g = r, if such a decomposition exists, and "no decomposition" otherwise. 1. Let fbar be the reversal of f, and compute hbar in F[x] of degree less than s with hbar^r = fbar mod x^s and h(0) = 1. Let h = x^s hbar(1/x) in F[x]. 2. Compute b_0,..., b_r in F[x] as in "Taylor expansion". 3. If b_0,..., b_r in F, set g = sum(0<=i<=r, b_i x^i) in F[x] and return (g,h). Otherwise return "no decomposition".

3 2

[math-fun] Prof.Dr. Landau's polynomial decomposition
by Warren D Smith 04 Apr '16

04 Apr '16

I suppose you could call a poly "prime" if it has no such decomposition. (And I use the term literally: "de-composition.") New kind of primeness notion. Seems to me Macsyma et al ought to offer finding this decomposition as yet another capability. Could be useful. If Landau does it over finite fields then doing it over integers (and perhaps rationals?) could be done via some kind of chinese remaindering of finite field results. In a finite field, there is a problem however. Some polynomial decomposition F(x)=G(H(x)) could happen, even though H and/or G actually have greater degree than F. Right? Can Landau detect those? Doubt it. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 2