August 2013 - mathfun@mailman.xmission.com

[math-fun] H.Brady's |exp(ix)|=1 request
by Warren D Smith 11 Aug '13

11 Aug '13

What you want is exp(ix) =approx= (A+Bi) / (C+Di) where A,B,C,D are real polynomials in x with A^2+B^2=C^2+D^2. For example if A=C=even, B=-D=odd, this is achieved and also exp(-ix)=conjugate(exp(ix)) is always satisfied.

1 0

Re: [math-fun] 2D convex hull
by Henry Baker 10 Aug '13

10 Aug '13

Actually, you really want to compute a (hyper)plane (cross product) and then do dot products to partition the points. This is much faster (see my previous post on cross products as 'caches' of partially computed determinants.) Ditto for higher dimensions. At 01:33 PM 8/10/2013, Warren D Smith wrote: >For 2D, you need only to compute 3x3 determinant-signs in exact arithmetic >(sign of area of a triangle), also expressible using 2x2 determinants. > >In general a primitive to compute sign of (D+1)x(D+1) determinant >will suffice.

1 0

[math-fun] complex rational approximations to z=exp(i*x)
by Henry Baker 10 Aug '13

10 Aug '13

We're taught that |z|=|exp(i*x)|=1, for real x. But this doesn't work so well for rational approximations, especially when we rationalize the real & imaginary parts separately. So I'm seeking rational approximations to exp(i*x), x real, such that |exp(i*x)| is identically zero. Let t=rationalize(tan(x/2)) be a rational approximation to tan(x/2). Then z = ((t^2-1) + i*2*t)/(t^2+1) is rational, and |z| is identically 1. Question: Is this the best (or perhaps only) way to do this? Are there closer rational approximations that don't correspond to one of these forms? By 'closer', I mean closer for a given denominator size.

2 1

[math-fun] worst cases for 2D convex hulls ?
by Henry Baker 10 Aug '13

10 Aug '13

I'm testing a 2D convex hull algorithm that uses _exact_ rational arithmetic. Convex hull takes a list of points and produces an ordered list going around the circumference of the convex hull of the input points. Obviously, any interior points are dropped, as are 'redundant' points _exactly on_ an edge from one hull point to another. (It turns out that most convex hull algorithms produce the list in proper order 'for free' -- i.e., for no additional work above & beyond proving that they are hull points.) (Convex hull algorithms can sometimes screw up with inexact arithmetic.) What are the worst cases for such 2D hull algorithms, both in terms of run-time and exactness ? My guess is that worst case run-times happen in the case when the points are _already_ all hull points, and that the worst-case for exactness occurs when the points are all still hull points, but get incredibly close together. My first test simply arranged points around the unit circle; exp(2*pi*i/n) in complex-speak. My second test used the standard mapping: t -> ((1-t^2)+2*t*i)/(1+t^2) to produce points around the unit circle which converged upon the point -1. If you want faster convergence, use t=s^3, or even t=s*2^s. Are there any 2D _convex_ 'fractal' patterns that might make good convex hull tests?

3 3

[math-fun] Forget Hello Kitty; here comes Peta Yen
by Henry Baker 10 Aug '13

10 Aug '13

FYI -- >From the land that brought you 'Tamagotchi': http://en.wikipedia.org/wiki/Tamagotchi and 'Hello Kitty': http://en.wikipedia.org/wiki/Hello_Kitty we now get 'Peta Yen' (see below). While this number can still be represented in a 64-bit integer, one wonders how long this will be true so long as all the major countries try to outdo one another in devaluing their currency. http://www.nytimes.com/2013/08/10/world/asia/japans-debt-reaches-new-milest… JapanÂs Debt Looks Like This: 1,000,000,000,000,000 Yen By JOHN SCHWARTZ Published: August 9, 2013 JapanÂs soaring national debt, already more than twice the size of its economy, has reached a new milestone, surpassing one quadrillion yen. Let the word quadrillion roll around in your brain for a moment or two, because it is not something you hear every day. Quadrillion. 1,000,000,000,000,000. Really. A paltry million is the numeral one followed by six zeros. A billion? Nine zeros. A trillion is getting up there: 12 zeros. But the mighty quadrillion has 15 of them. The mind boggles. (Though it doesnÂt googol: that one is followed by 100 zeros. And thatÂs the actual spelling. You can Google it.) A quadrillion is a million billion, putting it into the kind of language used by middle schoolers to describe really humongous sums, along with gazillion and bazillion. Measuring any currency in quadrillions brings to mind the hyperinflation of Germany between the wars, or Zimbabwe in the last decade. But a country with a real currency? It is such a big and unusual word, describing such a big and unusual number, that its use is inconsistent: Bloomberg News used quadrillion in the headline of an early story on Friday about JapanÂs debt, but later in the day the stories and headlines referred to a Âthousand trillion,Â which is not nearly as much fun. Questions e-mailed to the Bloomberg editors responsible for those stories were not returned, suggesting perhaps a lexicographical quadrilliongate. How much is a quadrillion? The entire human body is said to have just 100 trillion cells; it takes 10 of us to make a quadrillion. Jeff Bezos has a personal fortune of some $25 billion, allowing him to plunk down $250 million for The Washington Post, which is essentially how much money he might find by looking behind his sofa cushions. To get to a quadrillion dollars, however, we would have to have 40,000 Bezoses, or as many people as live in Prescott, Ariz. Neil deGrasse Tyson, the astrophysicist and director of the Hayden Planetarium at the American Museum of Natural History, helpfully offered a few other ways to think about a quadrillion. ÂIt would take you 31 million years to count to a quadrillion Â one number per second, never sleeping,Â he said in an e-mail, adding that Âa quadrillion yen, stacked in 1,000-yen notes, would ascend 70,000 miles high.Â He also wrote, though it is not clear how he would know such a thing, that Âthe total number of all sounds and words ever uttered by all humans who have ever lived is about 100 quadrillion.Â ÂThis figure includes all Congressional debates and filibusters,Â Mr. Tyson wrote. Compared with Japan, the United States national debt is a mere $16 trillion or so. But if you convert that number into yen, it comes to about 1.5 quadrillion. So itÂs good to have a currency that conserves its zeros. Of course, that also means the total American debt is even larger than JapanÂs (though not, it should be noted, as a percentage of gross domestic product). Hmm. LetÂs not talk about that. A version of this article appeared in print on August 10, 2013, on page A4 of the New York edition with the headline: JapanÂs Debt Looks Like This: 1,000,000,000,000,000 Yen.

1 0

[math-fun] Extending ballot numbers / Catalan triangle
by Fred Lunnon 09 Aug '13

09 Aug '13

I've been thinking about ballot numbers recently (the way one does), particularly in connection with RWG's campaign to clean up the binomial coefficient extension to negative arguments. The traditional definition along the lines of B(n, k) == n+k_C_k (n-k)/(n+k) --- counting positive paths from (0, 0) to (n+k-1, n-k-1) --- breaks down when n+k = 0 , and makes proving identities awkward --- such as the fundamental convolution B(n, k) = \sum_j B(n-1-j, k-j) B(j+1, j) --- where in practice the range may be restricted to 0 <= j <= k . A more robust definition which extends immediately to negative arguments, and allows the range above to be infinite, is instead B(n, k) == (n+k-1)_C_k - (n+k-1)_C_(k-1) ; naturally, the binomial coefficient n_C_k = 0 for k < 0 and all n . A short table is appended. Do the numbers in the 2 o'clock sector have any interesting combinatorial significance? The only instance I have come across so far --- prompted by OEIS A000096, A005581 --- is that (-1)^k B(-n, k) apparently counts convex k-gons inscribed in a convex (n+k)-gon, with former vertices subset of latter and former edges disjoint from latter (proof?). For n > 0 NJAS has collected relevant material under A009766 . Fred Lunnon # Maple program for Feller ballot number B(n, k) extended to n,k integer # counts number of positive paths from (0, 0) to (n+k-1, n-k-1) ballot := proc (n, k) binom(n+k-1, k) - binom(n+k-1, k-1) end; m := 7; matrix([seq([seq(ballot(n, k), k = -m..m)], n = -m..m)]); [0, 0, 0, 0, 0, 0, 0, 1, -8, 27, -50, 55, -36, 13, -2] [0, 0, 0, 0, 0, 0, 0, 1, -7, 20, -30, 25, -11, 2, 0] [0, 0, 0, 0, 0, 0, 0, 1, -6, 14, -16, 9, -2, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -5, 9, -7, 2, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -4, 5, -2, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -3, 2, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -2, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1, -1, -1, -1, -1, -1, -1, -1] [0, 0, 0, 0, 0, 0, 0, 1, 0, -1, -2, -3, -4, -5, -6] [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, -2, -5, -9, -14, -20] [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0, -5, -14, -28, -48] [0, 0, 0, 0, 0, 0, 0, 1, 3, 5, 5, 0, -14, -42, -90] [0, 0, 0, 0, 0, 0, 0, 1, 4, 9, 14, 14, 0, -42, -132] [0, 0, 0, 0, 0, 0, 0, 1, 5, 14, 28, 42, 42, 0, -132] [0, 0, 0, 0, 0, 0, 0, 1, 6, 20, 48, 90, 132, 132, 0]

5 5

[math-fun] This looked weird
by Bill Gosper 08 Aug '13

08 Aug '13

After catching up on sleep I'll doubtless regret sending this, but while I was fooling with alternating binomial sums, Mma unsimplified one of them, resulting in HypergeometricPFQ[{1,1/2-n+Floor[n/2],1-n+Floor[n/2]},{3/2+Floor[n/2],2+Floor[n/2]},1]== ((4^n-(-1)^n Binomial[2 n,n]) Gamma[2 n-2 Floor[n/2]] Gamma[3+2 Floor[n/2]])/(2 Gamma[2+2 n]), integer n >0. It might be something simple that got bisected and reversed, but it seems a bit too exotic. Macsyma did it with Dixon's thm, but only after I separated the even and odd cases. Why didn't Mma? --rwg

1 0

[math-fun] solar cells using electron spin
by Warren D Smith 08 Aug '13

08 Aug '13

http://www.nature.com/nature/journal/vaop/ncurrent/full/nature12339.html http://www.cam.ac.uk/research/news/electron-spin-key-to-solar-cell-breakthr… perhaps some physicist can explain. Very vaguely, the idea is that in some organic semiconductor based solar cell, light generates an electron-hole pair. If pair then just recombines, you lose. However, by design of the organic molecule and.or crystal structure, you make it so the spins are not opposite, or so that if they are then the positions of the electron & hole are likely to be far apart (quantum entanglement). This beneficially prevents quick recombination. There is a built-in local electric field near any PN junction in any semiconductor, which then separates the e-hole pair, thus enabling you to generate power (current*voltage). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] ballot numbers review, questions
by Warren D Smith 08 Aug '13

08 Aug '13

That was an interesting essay on binomial coefficients by Lunnon. https://www.dropbox.com/s/anykne0pd55ehjg/binomial.pdf It had never occurred to me before that anybody could consider anything other than Lunnon's preferred EQ 12=assertion 7, but he indicates that mathematica and MAPLE both apparently are brain dead about this. Incredible. Consulting Feller vol.1 as Lunnon says re "ballot numbers"... we find THEOREM by W.A.Whitworth 1878 then J.L.F.Bertrand 1887: If candidate P gets p votes and rival candidate Q gets q votes, p>=q, then the probability that throughout the count P is always ahead, is (p-q)/(p+q). "THE BALLOT THEOREM": Let a>0, b>0 be integers. The number of paths -- on the usual integer square lattice where each step adds either (+1, +1) or (+1, -1) to current location -- from (0,0) to (a,b) which always lie above the x-axis, is (b/a) * Binomial(a, (a+b)/2). Equivalently, the number which never go below the x-axis is ((b-1)/(a-1)) * Binomial(a-1, (a+b)/2-1). This is proved with the brilliantly simple "reflection lemma" that (if a,b,c,d positive integers) the number of paths from (c,d) to (a,b) which cross the x-axis at least once, is the same as the number of unrestricted paths from (c,-d) to (a,b). --------------------- QUESTION: If candidate P gets p votes and rival candidate Q gets q votes, p>=q, what is the probability distribution of the number of "lead changes" as we count ballots? Or (almost equivalently) of the number of times P & Q tied for the lead? I do not know the answer, but one can write down certain expressions for prob(0), prob(1), prob(2),... and one can also get an approximate answer by using THEOREM OF L.TAKACS (1967): If you sum i.i.d. random integer variables each with mean=m, then the probability every partial sum is positive (forever), equals m if m>0, otherwise 0. Applying Takacs' theorem with the random variable which is +1 with prob=(p-q)/(p+q) and -1 with prob=2q/(p+q) we see that the chance that P stays ahead forever equals m=(p-3q)/(p+q) which it makes sense is a lower bound on the chance (p-q)/(p+q) that P stays ahead during the first p+q votes... although this is not a proof. The chance that P stays enters the lead exactly n>=1 times (over infinite time), is from Takacs theorem equal to (1-m)^(n-1) * m so this perhaps is a lower bound on the chance there are <=n "P enters lead" moments during the count of the p+q votes. QUESTION: If candidate P gets p votes and rival candidate Q gets q votes, p>=q, what is the probability distribution of the number of moments (among p+q total moments) at which P is not in the lead? It is possible these questions have some nice partial answers, albeit so far my attempts to answer them have only yielded horribly complicated expressions.

1 2

Re: [math-fun] math-fun Digest, Vol 126, Issue 14
by Warren D Smith 07 Aug '13

07 Aug '13

> Date: Thu, 8 Aug 2013 02:14:19 +0100 > From: Fred Lunnon <fred.lunnon(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: [math-fun] Extending ballot numbers / Catalan triangle > Message-ID: > <CAN57YqtFfZLnmY6rDWqXGVuw7Xn6yoFV+S2wektV40BC-GQG+A(a)mail.gmail.com> > Content-Type: text/plain; charset=ISO-8859-1 > > I've been thinking about ballot numbers recently (the way one does), > particularly in connection with RWG's campaign to clean up the binomial > coefficient extension to negative arguments. > > The traditional definition along the lines of > B(n, k) == n+k_C_k (n-k)/(n+k) > --- counting positive paths from (0, 0) to (n+k-1, n-k-1) --- > breaks down when n+k = 0 , and makes proving identities awkward --- > such as the fundamental convolution > B(n, k) = \sum_j B(n-1-j, k-j) B(j+1, j) > --- where in practice the range may be restricted to 0 <= j <= k . > > A more robust definition which extends immediately to negative arguments, > and allows the range above to be infinite, is instead > B(n, k) == (n+k-1)_C_k - (n+k-1)_C_(k-1) ; > naturally, the binomial coefficient n_C_k = 0 for k < 0 and all n . > A short table is appended. > > Do the numbers in the 2 o'clock sector have any interesting combinatorial > significance? The only instance I have come across so far --- prompted by > OEIS A000096, A005581 --- is that (-1)^k B(-n, k) apparently counts > convex > k-gons inscribed in a convex (n+k)-gon, with former vertices subset of > latter > and former edges disjoint from latter (proof?). > > For n > 0 NJAS has collected relevant material under A009766 . > > Fred Lunnon > > # Maple program for Feller ballot number B(n, k) extended to n,k > integer > # counts number of positive paths from (0, 0) to (n+k-1, n-k-1) > ballot := proc (n, k) > binom(n+k-1, k) - binom(n+k-1, k-1) end; > > m := 7; matrix([seq([seq(ballot(n, k), k = -m..m)], n = -m..m)]); > > [0, 0, 0, 0, 0, 0, 0, 1, -8, 27, -50, 55, -36, 13, -2] > [0, 0, 0, 0, 0, 0, 0, 1, -7, 20, -30, 25, -11, 2, 0] > [0, 0, 0, 0, 0, 0, 0, 1, -6, 14, -16, 9, -2, 0, 0] > [0, 0, 0, 0, 0, 0, 0, 1, -5, 9, -7, 2, 0, 0, 0] > [0, 0, 0, 0, 0, 0, 0, 1, -4, 5, -2, 0, 0, 0, 0] > [0, 0, 0, 0, 0, 0, 0, 1, -3, 2, 0, 0, 0, 0, 0] > [0, 0, 0, 0, 0, 0, 0, 1, -2, 0, 0, 0, 0, 0, 0] > [0, 0, 0, 0, 0, 0, 0, 1, -1, -1, -1, -1, -1, -1, -1] > [0, 0, 0, 0, 0, 0, 0, 1, 0, -1, -2, -3, -4, -5, -6] > [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, -2, -5, -9, -14, -20] > [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 0, -5, -14, -28, -48] > [0, 0, 0, 0, 0, 0, 0, 1, 3, 5, 5, 0, -14, -42, -90] > [0, 0, 0, 0, 0, 0, 0, 1, 4, 9, 14, 14, 0, -42, -132] > [0, 0, 0, 0, 0, 0, 0, 1, 5, 14, 28, 42, 42, 0, -132] > [0, 0, 0, 0, 0, 0, 0, 1, 6, 20, 48, 90, 132, 132, 0] --what do these have to do with "ballots"?

3 2