August 2012 - mathfun@mailman.xmission.com

[math-fun] A remarkable probability distribution on the (perimeter of the) unit circle
by Warren Smith 15 Aug '12

15 Aug '12

1. Consider the probability distribution where you are uniform on an arc of the unit circle |z|=1 in the complex plane having arc length 2*pi/P_n where P_n is the nth prime, P_1=2, P_2=3, P_3=5, etc. For concreteness use the arc whose midpoint is the complex number 1. This probability distribution has the property that the expected value of z^k (where z is a complex number sampled from it) is zero whenever the integer k>1 is a multiple of P_n. 2. Now convolve the probability distributions above based on P_1, P_2, ..., P_N together. The resulting probability distribution has the property that the expected value of z^k (where z is a complex number sampled from it) is zero whenever the integer k>1 is divisible by at least one of the first N primes. However, the expected value of z^1, otherwise known as z, is NOT zero, in fact it is some other real number. (Conceivably for some finite set of miraculous N it actually is zero, though for almost all N we shall see it is positive.) This distribution can also be regarded as a distribution on the angle theta of the sampled-point to the real axis, z=exp(i*theta), for -infinity<theta<infinity. In that case, this distribution has (3/pi)*variance(theta) = sum{n=1,2,...,N} (P_n)^(-2) which remains finite even in the limit N-->infinity. The sum on the right converges to 0.452247... Theta has an even-symmetric probability density which rises then falls (unimodal) and is described by a piecewise polynomial(theta) of degree<=N and a finite number of pieces. 3. The finite limit-variance (and finite all-other-moments) means there exists a limit-distribution in the limit N-->infinity. This distribution has a density function. (Its characteristic function can be written neatly as a certain infinite product, incidentally.) It is NOT the uniform density on the circle. It is unimodal and even-symmetric on the real theta-line. To get the density on the circle, you need to "wrap" the line version modulo 2*pi. This density on the circle shares the property with the plain uniform distribution on the circle that the expected value of z^k is ZERO for each integer k with |k|>1. However, when |k|=1 we (unlike plain uniform) do NOT get zero, we get 0.8281 approximately (and of course when k=0 we get 1). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Raghavendra's algorithm for solving linear systems over finite fields
by Warren Smith 15 Aug '12

15 Aug '12

>Preliminary draft: > http://www.eecs.berkeley.edu/~prasad/linsystems.pdf --I don't understand why anybody would want to use this algorithm for any purpose. It's slower than everything else I can think of and also randomized i.e. can fail. However... perhaps it might be useful if changed to be about finite RINGS not fields. In rings, you cannot divide, hence gaussian elimination is not usable. Hence this algorithm then has less competition. (Even then I'm dubious, but then it'd have at least a hope.)

1 0

[math-fun] HAKMEM Festschrift ??
by Henry Baker 15 Aug '12

15 Aug '12

Scott Guthery, whom I've known since Symbolics days (daze?), has approached me with an interesting idea: a followup to HAKMEM -- a sort of "where are they (the ideas/topics) now?" I think that Scott's idea lies very much in the realm of a kind of festschrift, but this time for HAKMEM itself, rather than for a particular individual. There has obviously been a ton of progress on nearly every one of the topics from HAKMEM, so one could conceivably write a whole chapter to go with each of the topics -- at least for the more interesting topics. Perhaps the author of the original topic might have first crack at an update of the topic. I suggested to Scott that organizing this might take a while (years), so it might end up being "HAKMEM at 50". Scott is the publisher of a little press, which seems to be involved in topics like computers/maths, etc.: http://docentpress.com/ Are any of you HAKMEM contributors out there interested in participating/writing ?

1 0

[math-fun] US population hits pi
by Henry Baker 15 Aug '12

15 Aug '12

FYI -- ok, Fibonacci lovers, on what date did the US population hit phi ? http://www.boston.com/news/source/2012/08/us_population_h.html US population hits pi Posted by Angela Nelson, Boston.com Staff August 14, 2012 03:05 PM The US population clock hit a mathematically significant milestone on Tuesday - pi. The US Census Bureau estimated that the clock struck 314,159,265 residents just after 2:29 p.m. That figure is pi (3.14159265) times 100 million. Pi is a mathematical constant that is the ratio of a circles circumference to its diameter. The US Census Bureau's top demographer celebrated with a pun. This is a once in many generations event...so go out and celebrate this American pi, Howard Hogan said in a written statement.

4 4

[math-fun] A New Way To Solve Linear Equations
by Ray Tayek 15 Aug '12

15 Aug '12

https://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equatio… August 9, 2012 tags: <https://rjlipton.wordpress.com/tag/algorithms/>Algorithms, <https://rjlipton.wordpress.com/tag/amplification/>amplification, <https://rjlipton.wordpress.com/tag/finite-fields/>finite fields, <https://rjlipton.wordpress.com/tag/linear-system/>linear system, <https://rjlipton.wordpress.com/tag/randomness/>randomness by <https://rjlipton.wordpress.com/author/rjlipton/>rjlipton Impossible but true: a new approach to linear systems Prasad Raghavendra is an expert in many aspects of complexity theory, especially the foundations of approximation theory. He recently was a colleague at Georgia Tech, but now has moved on to Berkeley. He will be greatly missed at Tech. Today I want to talk about a brilliant new result that Prasad has on linear equations. I was recently at the advisory meeting for the Berkeley Simons Theory Institute. During the meeting we had two presentations on new areas, besides talks on planned special projects. One was given by Prasad on theory, but almost in passing he mentioned that he had a way to solve linear systems. I liked the whole talk, but his almost causal comment surprised me. It seemed to me to be an entire new approach to solving linear systems. My initial thought was it must be something well known, but I did not know it. As soon as he finished his talk we had a break, and I ran up to thank him for a wonderful talk. I quickly asked was his result on linear systems new? Or was it something I had missed? He answered to several of us, who now were waiting to hear his answer, that it was something that he had just proved. I was relieved: I am not completely out of it. I asked if we could write about this result and he agreed. Even better, he wrote up a <http://www.eecs.berkeley.edu/%7Eprasad/linsystems.pdf>draft paper with just the algorithm and its analysis, which are part of larger results and projects that were the body of his talk. Solving Linear Systems The solving of linear systems of equations is ancient, dating back to 600 BCE. It is of extreme importance, and still an active area of research. For arbitrary systems Gaussian Elimination is still quite powerful. A historical note, apparently Carl Gauss only used the method named after him on six-variable problems. In those days there was no notion of, I can solve the general case in time cubic in {n} . There was no "n": of course there was the letter "n," but not the notion of solving a problem of size determined by {n} . Of course now we have faster methods than this for general systems, methods that descend from the famous breakthrough of Volker Strassen. For special systems there are almost-linear-time methods, but these all require that the system have special structure, and work over the reals. ... --- co-chair http://ocjug.org/

2 2

[math-fun] peculiar 2x2 products
by Bill Gosper 14 Aug '12

14 Aug '12

We're used to evaluating an infinite continued fraction as a limit of ratios of elements of a running product of 2x2 matrices, while the actual elements of the product blow up. E.g., for 4 arctan(1) In[1153]:= FoldList[Dot, {{0, 4}, {1, 0}}, Table[{{2*k - 1, k^2}, {1, 0}}, {k, 9}]] Out[1153]= {{{0, 4}, {1, 0}}, {{4, 0}, {1, 1}}, {{12, 16}, {4, 4}}, {{76, 108}, {24, 36}}, {{640, 1216}, {204, 384}}, {{6976, 16000}, {2220, 5100}}, {{92736, 251136}, {29520, 79920}}, {{1456704, 4544064}, {463680, 1446480}}, {{26394624, 93229056}, {8401680, 29675520}}, {{541937664, 2137964544}, {172504080, 680536080}}} In[1154]:= N[Divide @@ # & /@ Rest[%]] Out[1154]= {{4., 0.}, {3., 4.}, {3.16667, 3.}, {3.13725, 3.16667}, {3.14234, 3.13725}, {3.14146, 3.14234}, {3.14161, 3.14146}, {3.14159, 3.14161}, {3.14159, 3.14159}} But here's an infinite matrix product where the elements converge individually: Product[MatrixForm[{{(3*a^2 - 3*a*j + j^2)/(j*(-1 - 3*a + b + j)), a^3/(j*(-1 - 3*a + b + j))}, {1/j, 1}}], {j, b, ∞}] == MatrixForm[{{"?", (a^3*HypergeometricPFQ[{1 + a, 1 + a, 1 + a}, {1 + b, 1 + b}, 1])/b^2}, {"?", HypergeometricPFQ[{a, a, a}, {b, b}, 1]}}] (Product means matrix product, not Mathematica's product.) The ?s converge, too, but I don't know to what. Note that the determinant ≠ 1, but approaches 1 in a very particular way. It's not obvious to me how to scale a matrix to make its running product converge elementwise. I actually have an elementwise convergent 2x2 product for the general 3F2[1], but idiot Mathematica 8.04 takes (literally?) forever to convert a simple sum of Pochhammers to a 3F2. --rwg

1 3

[math-fun] Wilf pi problem
by Bill Gosper 14 Aug '12

14 Aug '12

From: Joerg Arndt <arndt(a)jjj.de <http://gosper.org/webmail/src/compose.php?send_to=arndt%40jjj.de>> To: math-fun <math-fun(a)mailman.xmission.com <http://gosper.org/webmail/src/compose.php?send_to=math-fun%40mailman.xmissi…>> Subject: Re: [math-fun] Wilf's pi and determinant problems Message-ID: <20120814160001.GB13398(a)jjj.de <http://gosper.org/webmail/src/compose.php?send_to=20120814160001.GB13398%40…>> Content-Type: text/plain; charset=us-ascii * Warren Smith <warren.wds(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=warren.wds%40gmail.com>> [Aug 14. 2012 17:26]:> > [...] >> ---I partially mis-worded the pi problem -- should have said the ratio> a(n)/a(n-1) was> rational function of n, and a(0)=rational. If none of the pi-experts> here can come up> with a positive solution, which would be the easy way to solve it,> then it is probably> a hard problem. One relevant piece of maths is "Siegel E-functions"> http://en.wikipedia.org/wiki/E-function jj>I guess 1/Pi is somehow verboten, but anyway: 2/Pi = 2F1([-1/2,1/2], [1], 1) 2F1[1/2, 1/2, 3/2, 1] = π/2. More generally, Hypergeometric2F1[1/2, 1/2, 3/2, x^2] = ArcSin[x]/x . wds>--no, no, no: one of Wilf's demands was that the series converge faster than geometrically. wds>For example, Wilf's problem would be trivially solved if he had said not "pi" but "e." > Wilf had a web page of "Herb's open problems" here:> http://www.math.upenn.edu/~wilf/website/UnsolvedProblems.pdf> and the 2 problems I gave were his #1 and #7. The π problem must be very hard, being dangerously close to the algebraic independence of e and π. Back before complexity theory had a name, Rich determined the time cost of pFq was ≤ "T2" for q≥p, and ≤ "T3" for p=q+1, where T2 was n*cost(n digit multiply) (which we assumed was n log n log log n) and T3 := n*T2. It seemed obvious that π was T3 and e was T2, and proving it would crack algebraic independence. Then Gene's AGM messed everything up by making π T2. But maybe there's still some hay to be made from "hypergeometric independence". --rwg

1 0

[math-fun] Wilf pi problem
by Warren Smith 14 Aug '12

14 Aug '12

From: Joerg Arndt <arndt(a)jjj.de> To: math-fun <math-fun(a)mailman.xmission.com> Subject: Re: [math-fun] Wilf's pi and determinant problems Message-ID: <20120814160001.GB13398(a)jjj.de> Content-Type: text/plain; charset=us-ascii * Warren Smith <warren.wds(a)gmail.com> [Aug 14. 2012 17:26]: > > [...] > > ---I partially mis-worded the pi problem -- should have said the ratio > a(n)/a(n-1) was > rational function of n, and a(0)=rational. If none of the pi-experts > here can come up > with a positive solution, which would be the easy way to solve it, > then it is probably > a hard problem. One relevant piece of maths is "Siegel E-functions" > http://en.wikipedia.org/wiki/E-function I guess 1/Pi is somehow verboten, but anyway: 2/Pi = 2F1([-1/2,1/2], [1], 1) --no, no, no: one of Wilf's demands was that the series converge faster than geometrically. For example, Wilf's problem would be trivially solved if he had said not "pi" but "e." > Wilf had a web page of "Herb's open problems" here: > http://www.math.upenn.edu/~wilf/website/UnsolvedProblems.pdf > and the 2 problems I gave were his #1 and #7.

2 1

[math-fun] my herb wilf story
by Thane Plambeck 14 Aug '12

14 Aug '12

herb wilf had an office in the stanford computer science building (margaret jacks hall) ca 1986 or 1987 or so. he was probably on sabbatical. his office wasn't too far away from my grad student cube farm and i got to know him a tiny bit. he told me about some problems having to do with symmetric chain decompositions of posets he also posed a generating functions problem later known as "n coins in a fountain" on my analysis of algorithms qualifying exam. A005169 - OEIS is relevant anyway, one day three people were walking in a line toward the front door of margaret jacks hall. the first person was herb wilf. the second person, following wilf about ten paces behind, was campus celebrity joe euclid (see link below). but i'm sure wilf didn't know about euclid. the third person, ten paces behind euclid, was me. with this staging of dramatis personae, events unfolded as follows wilf reaches the door of margaret jacks hall. as he opens the door, he notices euclid, following behind him holding a huge stack of papers. wilf pauses at the door, propping it open nicely for euclid. but euclid does not go in. instead, he pauses right in front of wilf. WILF: May I help you? EUCLID: Well, I suppose the FIRST THING IS, why doesn't ANYONE believe UFOS ARE REAL!!!!! (this last part almost screaming). I had the pleasure of slipping into the building and smiling at Wilf as I went through the door still being held open by him http://en.wikipedia.org/wiki/Joe_Jonah_Euclid -- Thane Plambeck tplambeck(a)gmail.com http://counterwave.com/

1 0

Re: [math-fun] Wilf's pi and determinant problems
by Henry Baker 14 Aug '12

14 Aug '12

I heard recently a (possibly apocryphal) story about a mathematician who gave co-authorship on a math paper to a dead (non-mathematician) friend. Apparently the friend came to him in a dream & helped him get to the answer. Perhaps someone here knows more about this story? At 07:51 PM 8/13/2012, you wrote: >I actually dreamed about Herb a few months ago. In my dream, I told >him about some recent mathematical discovery of mine (I no longer >remember what) that I thought he'd like. He replied that, being dead, >he no longer found math interesting.

1 1