January 2019 - mathfun@mailman.xmission.com

[math-fun] What is the probability that a randomly thrown polyhedral die will land on a given face?
by Dan Asimov 30 Jan '19

30 Jan '19

Let F be a face of a bounded convex polyhedron K in R^3. Assume K is solid with constant density. Then: ----- What is the probability p = p(F; K) that if K is randomly thrown onto a horizontal surface, it will land on the face F ? ----- My guess back in high school was that p = (1/4π) * (solid angle(F), subtended from the center of gravity of K). I recently saw for sale some novelty dice that are irregular hexahedra with planar faces, advertised as having equal probabilities for all faces. So I'm wondering if this is just an issue of that solid angle fraction, or whether there is more to it. Maybe this depends on how "randomly thrown" is defined? A priori it seems that this might be possible, say, if some faces would be unlikely to be landed on if our polyhedral die K were rolling on the horizontal surfaces with enough velocity (or end-over-end angular momentum). So the random throws might have different statistical outcomes if there are many with high energy. Or not? —Dan

4 4

[math-fun] Error correction for integers (bignums)
by Henry Baker 30 Jan '19

30 Jan '19

The problem with standard ECC is that *all bits are treated the same*, regardless of bit position. Too bad if the corrupted will & testament reads "Mallory has just inherited $XYZ,000.00"; X matters a heck of a lot more than Y, which matters a heck of a lot more than Z. Clearly, one would like to put more redundancy into X than Y, and more into Y than Z. Alternatively, encode X into more bits than Y, which enables "standard" ECC to better deal with errors in X than in Y. As a warmup, consider mapping integers n in the range [0,2^k) into k-bit bit-strings; alternatively, use *unary* coding 1^(2^k) for these same integers. Although the unary coding has the desired property, it is quite inefficient. If I understand his papers, Gallager solved this problem back in the 1970's, by choosing a fixed large number M and unary encoding floor(n/M) and Huffman encoding mod(n,M) (almost always standard binary encoding of mod(n,M)). Although Gallager considered *variable- length codes*, so these unary codes don't have to be full length, I suspect that the answer doesn't change by more than a constant factor (??) if a fixed maximum length is specified for the unary coding of floor(n/M). Is there a better method of protecting the high order bits of n using a more sophisticated type of ECC than this unary encoding hack of Gallager's ?

5 7

Re: [math-fun] Complex Cheby (Chufty?!?)
by Henry Baker 28 Jan '19

28 Jan '19

Yes, I was aware of Chebfun & Trefethen, but I only realized the connection with complex *Joukowski* transforms just yesterday. Joukowski(z) = (z+1/z)/2 = (1+z^2)/(2*z) Joukowski(z) should look familiar: Joukowski(z) = z-(z^2-1)/diff(z^2-1,z) = (1+z^2)/(2*z) i.e., it is the *Newton-Raphson iteration for sqrt(1)* (in the complex plane, obviously!) Now here's the completely insanely cool thing: https://en.m.wikipedia.org/wiki/Joukowsky_transform the Joukowsky transform, named after Nikolai Zhukovsky (who published it in 1910), is a conformal map historically used to understand some principles of ***airfoil*** design. A Joukowsky airfoil is generated in the complex plane by applying the Joukowsky transform to a circle in the zeta-plane. The coordinates of the centre of the circle are variables, and varying them modifies the shape of the resulting airfoil. The circle encloses the point zeta=-1 (where the derivative is zero) and intersects the point zeta=1. This can be achieved for any allowable centre position x + i y by varying the radius of the circle. Joukowsky airfoils have a cusp at their trailing edge [and they look like -- wait for it -- the cross-section of a typical (subsonic) airplane wing!!]. --- In other words, an airplane wing section is the Joukowsky transform of a (slightly displaced) *circle* in the complex plane (pun intended!) ! BTW, there are *sailboats* who use *rotating cylinders* for sails, which basically *inverts* the Joukowsky airfoil. The cool thing about such *cylindrical sails*, is that they don't need constant "trimming" to present the best angle to the wind. Please add this as an entry into the 21st C. Hakmem. At 09:54 AM 1/28/2019, Victor Miller wrote: >Since you mentioned Lloyd Trefethen and Chebyshev polynomials, if you >haven't seen it, you should look at his excellent package Chebfun: >http://www.chebfun.org/ for doing really well-principled numerical >calculations. The main package is for matlab, but there are >implementations as C libraries and for python, for example. > >Victor > >On Mon, Jan 28, 2019 at 12:50 PM Henry Baker <hbaker1(a)pipeline.com> wrote: >> Cheby expansion: >> >> When complex z, |z|=1, >> >> T_k(x) = realpart(z^k) = (z^k+z^(-k))/2 >> >> (i.e., z=x+i*y) >> >> By *starting* with approximations in the complex domain, >> Trefethen shows how real Cheby approximations fall out in >> the wash, instead of appearing on stone tablets handed >> down from on high. Thus, the choice of x's as x-projections >> of *evenly spaced* points around the unit circle no longer >> seems forced -- indeed, it's *obvious*. >> >> A treatment of Cheby's in the *complex* domain also makes >> obvious the use of FFT's in various calculations involved >> with Cheby's. >> >> Finally, Trefethen shows in other papers that simply >> choosing these x-projections of equally spaced points >> on the unit circle *automatically* achieves the benefits >> of Cheby's when used for Lagrange interpolation, Newton >> divided differences, etc. So the problems with Lagrange, >> etc., aren't Lagrange's or Vandermonde's fault, but the >> fault of the unfortunate choice of equally spaced >> x-coordinates. >> >> I realize that Chebyshev polynomial approximations >> may not have originally been derived this way, but >> why do we still have to keep teaching them as if >> the complex domain never existed? >> >> For example, neither >> >> https://en.m.wikipedia.org/wiki/Chebyshev_polynomials >> >> nor >> >> https://en.m.wikipedia.org/wiki/Approximation_theory >> >> even hints at the elegant treatment that a view from >> the complex plane enables. >> >> http://people.maths.ox.ac.uk/trefethen/publication/PDF/1983_8.pdf >> >> Chebyshev Approximation on the Unit Disk >> >> Lloyd N. Trefethen

2 1

[math-fun] Complex Cheby (Chufty?!?)
by Henry Baker 28 Jan '19

28 Jan '19

Cheby expansion: When complex z, |z|=1, T_k(x) = realpart(z^k) = (z^k+z^(-k))/2 (i.e., z=x+i*y) By *starting* with approximations in the complex domain, Trefethen shows how real Cheby approximations fall out in the wash, instead of appearing on stone tablets handed down from on high. Thus, the choice of x's as x-projections of *evenly spaced* points around the unit circle no longer seems forced -- indeed, it's *obvious*. A treatment of Cheby's in the *complex* domain also makes obvious the use of FFT's in various calculations involved with Cheby's. Finally, Trefethen shows in other papers that simply choosing these x-projections of equally spaced points on the unit circle *automatically* achieves the benefits of Cheby's when used for Lagrange interpolation, Newton divided differences, etc. So the problems with Lagrange, etc., aren't Lagrange's or Vandermonde's fault, but the fault of the unfortunate choice of equally spaced x-coordinates. I realize that Chebyshev polynomial approximations may not have originally been derived this way, but why do we still have to keep teaching them as if the complex domain never existed? For example, neither https://en.m.wikipedia.org/wiki/Chebyshev_polynomials nor https://en.m.wikipedia.org/wiki/Approximation_theory even hints at the elegant treatment that a view from the complex plane enables. http://people.maths.ox.ac.uk/trefethen/publication/PDF/1983_8.pdf Chebyshev Approximation on the Unit Disk Lloyd N. Trefethen

2 1

[math-fun] The hazards of gradualism
by Bill Gosper 28 Jan '19

28 Jan '19

𝜂(𝛕) is defined throughout the upper halfplane, where it has period 24: DedekindEta[1 + 𝝉] == i^(1/6) DedekindEta[𝝉] By what does it scale if we only take half-steps? The formula for general 𝛕 becomes unclear. E.g., for 𝛕 := i√3, DedekindEta[1/2 + I Sqrt[3]] == (i^(1/12) ((1 + Sqrt[2]) (Sqrt[2] + Sqrt[3]))^(1/4) DedekindEta[I Sqrt[3]]) /(2^(3/16) (1 + Sqrt[3])^(3/8)) Presumably even worse for smaller steps. It's like particle physics—the closer you look, the more things crawl out of the woodwork. Trying for 1/3 of a step, (I DedekindEta[1/3 + I Sqrt[3]]^24)/DedekindEta[I Sqrt[3]]^24 == (1/59049)(10200 3^(1/6) + 1410 2^(1/3) 3^(1/6) - 25440 2^(2/3) 3^(1/6) + 11640 3^(5/6) - 8060 2^(1/3) 3^(5/6) - 5240 2^(2/3) 3^(5/6) - \[Sqrt](2682652239 + 568094400 2^(1/3) - 2140366320 2^(2/3) - 317440080 3^(1/3) - 499582620 2^(2/3) 3^(1/3) + 720388400 3^(2/3) - 704200460 2^(1/3) 3^(2/3) + 881386920 6^(1/3) - 159126160 6^(2/3))) To prove my point, I need to simplify the 24th root of this RHS. Gleep —rwg

2 1

Re: [math-fun] Fwd: Faulhabers 0 thru 12 in 4 iterations
by Dan Asimov 28 Jan '19

28 Jan '19

I didn't know who or what Faulhabers were, either (by name). (So had already been to the Wikipedia article.) I learned today what I hadn't known: That all the Faulh. polynomials F_n(x) for n odd are themselves polynomials in (x^2 + x)/2. Interesting! Now I'm wondering about a related matter: Given any rational p/q in Q - Z in lowest terms, then for any integer N we can form the sum S_p/q(N) = 1 + 2^(p/q) + ... + N^(p/q). Obviously (?) we can't hope for S_p/q(x) to be a polynomial in x, but I suspect it is a polynomial in x^(1/q), or S_1/q(x). Which brings up the question: Suppose P(x) are polynomials in Z[x] or Q[x]. When does there exist a polynomial X(x) (in one of those places) with P(x) = X(Q(x)) ??? Is this easy to determine? Something tells me differentiation might help. —Dan Fred Lunnon wrote: ----- For the benefit of anybody else who had never heard of this chap either, see Conway & Guy "Book of Numbers" https://en.wikipedia.org/wiki/Faulhaber's_formula https://www.emis.de/journals/AMEN/2018/AMEN-170803.pdf https://www.sciencedirect.com/science/article/pii/S0022247X06008791 -----

1 0

[math-fun] Fwd: Faulhabers 0 thru 12 in 4 iterations
by Bill Gosper 27 Jan '19

27 Jan '19

This message was received and forwarded without spurious linebreaks. If illegible, another gift from xmission.com. (But you can tediously delete the extra linebreaks.) —rwg (To certain eavesdroppers this is a SPOILER.) ---------- Forwarded message --------- From: Bill Gosper <billgosper(a)gmail.com> Date: Sat, Jan 26, 2019 at 5:33 PM Subject: Faulhaber 12 in 4 iterations To: Bill Gosper <billgosper(a)gmail.com> Shaved Pascal: Array[Binomial[#1, #2 - 1] Boole[#2 <= #1] &, {13, 13}]; 1 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 1 3 3 0 0 0 0 0 0 0 0 0 0 1 4 6 4 0 0 0 0 0 0 0 0 0 1 5 10 10 5 0 0 0 0 0 0 0 0 1 6 15 20 15 6 0 0 0 0 0 0 0 1 7 21 35 35 21 7 0 0 0 0 0 0 1 8 28 56 70 56 28 8 0 0 0 0 0 1 9 36 84 126 126 84 36 9 0 0 0 0 1 10 45 120 210 252 210 120 45 10 0 0 0 1 11 55 165 330 462 462 330 165 55 11 0 0 1 12 66 220 495 792 924 792 495 220 66 12 0 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 The only divisions are in the initialization: Boole[#1 == #2]/#1 MatrixForm /@ NestList[2 # - #.%.# &, Array[Boole[#1 == #2]/#1 &, {13, 13}], 4] 1 0 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/3 0 0 0 0 0 0 0 0 0 0 0 0 0 1/4 0 0 0 0 0 0 0 0 0 0 0 0 0 1/5 0 0 0 0 0 0 0 0 0 0 0 0 0 1/6 0 0 0 0 0 0 0 0 0 0 0 0 0 1/7 0 0 0 0 0 0 0 0 0 0 0 0 0 1/8 0 0 0 0 0 0 0 0 0 0 0 0 0 1/9 0 0 0 0 0 0 0 0 0 0 0 0 0 1/10 0 0 0 0 0 0 0 0 0 0 0 0 0 1/11 0 0 0 0 0 0 0 0 0 0 0 0 0 1/12 0 0 0 0 0 0 0 0 0 0 0 0 0 1/13 1 0 0 0 0 0 0 0 0 0 0 0 0 -1/2 1/2 0 0 0 0 0 0 0 0 0 0 0 -1/3 -1/2 1/3 0 0 0 0 0 0 0 0 0 0 -1/4 -1/2 -1/2 1/4 0 0 0 0 0 0 0 0 0 -1/5 -1/2 -2/3 -1/2 1/5 0 0 0 0 0 0 0 0 -1/6 -1/2 -5/6 -5/6 -1/2 1/6 0 0 0 0 0 0 0 -1/7 -1/2 -1 -5/4 -1 -1/2 1/7 0 0 0 0 0 0 -1/8 -1/2 -7/6 -7/4 -7/4 -7/6 -1/2 1/8 0 0 0 0 0 -1/9 -1/2 -4/3 -7/3 -14/5 -7/3 -4/3 -1/2 1/9 0 0 0 0 -1/10 -1/2 -3/2 -3 -21/5 -21/5 -3 -3/2 -1/2 1/10 0 0 0 -1/11 -1/2 -5/3 -15/4 -6 -7 -6 -15/4 -5/3 -1/2 1/11 0 0 -1/12 -1/2 -11/6 -55/12 -33/4 -11 -11 -33/4 -55/12 -11/6 -1/2 1/12 0 -1/13 -1/2 -2 -11/2 -11 -33/2 -132/7 -33/2 -11 -11/2 -2 -1/2 1/13 1 0 0 0 0 0 0 0 0 0 0 0 0 -1/2 1/2 0 0 0 0 0 0 0 0 0 0 0 1/6 -1/2 1/3 0 0 0 0 0 0 0 0 0 0 0 1/4 -1/2 1/4 0 0 0 0 0 0 0 0 0 -23/15 0 1/3 -1/2 1/5 0 0 0 0 0 0 0 0 -25/4 -23/6 0 5/12 -1/2 1/6 0 0 0 0 0 0 0 -1573/84 -75/4 -23/3 0 1/2 -1/2 1/7 0 0 0 0 0 0 -301/6 -1573/24 -175/4 -161/12 0 7/12 -1/2 1/8 0 0 0 0 0 -5759/45 -602/3 -1573/9 -175/2 -322/15 0 2/3 -1/2 1/9 0 0 0 0 -639/2 -5759/10 -602 -1573/4 -315/2 -161/5 0 3/4 -1/2 1/10 0 0 0 -52223/66 -3195/2 -5759/3 -1505 -1573/2 -525/2 -46 0 5/6 -1/2 1/11 0 0 -1958 -52223/12 -11715/2 -63349/12 -3311 -17303/12 -825/2 -253/4 0 11/12 -1/2 1/12 0 -2211491/455 -11748 -52223/3 -35145/2 -63349/5 -6622 -17303/7 -2475/4 -253/3 0 1 -1/2 1/13 1 0 0 0 0 0 0 0 0 0 0 0 0 -1/2 1/2 0 0 0 0 0 0 0 0 0 0 0 1/6 -1/2 1/3 0 0 0 0 0 0 0 0 0 0 0 1/4 -1/2 1/4 0 0 0 0 0 0 0 0 0 -1/30 0 1/3 -1/2 1/5 0 0 0 0 0 0 0 0 0 -1/12 0 5/12 -1/2 1/6 0 0 0 0 0 0 0 1/42 0 -1/6 0 1/2 -1/2 1/7 0 0 0 0 0 0 0 1/12 0 -7/24 0 7/12 -1/2 1/8 0 0 0 0 0 -2363/15 0 2/9 0 -7/15 0 2/3 -1/2 1/9 0 0 0 0 -12285/4 -7089/10 0 1/2 0 -7/10 0 3/4 -1/2 1/10 0 0 0 -4729715/132 -61425/4 -2363 0 1 0 -1 0 5/6 -1/2 1/11 0 0 -326865 -4729715/24 -225225/4 -25993/4 0 11/6 0 -11/8 0 11/12 -1/2 1/12 0 -14093005307/5460 -1961190 -4729715/6 -675675/4 -77979/5 0 22/7 0 -11/6 0 1 -1/2 1/13 1 0 0 0 0 0 0 0 0 0 0 0 0 -1/2 1/2 0 0 0 0 0 0 0 0 0 0 0 1/6 -1/2 1/3 0 0 0 0 0 0 0 0 0 0 0 1/4 -1/2 1/4 0 0 0 0 0 0 0 0 0 -1/30 0 1/3 -1/2 1/5 0 0 0 0 0 0 0 0 0 -1/12 0 5/12 -1/2 1/6 0 0 0 0 0 0 0 1/42 0 -1/6 0 1/2 -1/2 1/7 0 0 0 0 0 0 0 1/12 0 -7/24 0 7/12 -1/2 1/8 0 0 0 0 0 -1/30 0 2/9 0 -7/15 0 2/3 -1/2 1/9 0 0 0 0 0 -3/20 0 1/2 0 -7/10 0 3/4 -1/2 1/10 0 0 0 5/66 0 -1/2 0 1 0 -1 0 5/6 -1/2 1/11 0 0 0 5/12 0 -11/8 0 11/6 0 -11/8 0 11/12 -1/2 1/12 0 -691/2730 0 5/3 0 -33/10 0 22/7 0 -11/6 0 1 -1/2 1/13 In[35]:= Sum[k^12, {k, n - 1}] // Expand Out[35]= -691 n/2730 + 5 n^3/3 - 33 n^5/10 + 22 n^7/7 - 11 n^9/6 + n^11 - n^12/2 + n^13/13 —rwg (Probably don't need 5th iteration 'til Faulhaber 16. There's a bit to be gained by not recomputing the already-converged upper rows.)

3 2

[math-fun] Torus-with-a-hole puzzle
by Dan Asimov 27 Jan '19

27 Jan '19

Puzzle: ------- Using five congruent planar squares [0,1] x [0,1] in 3-space, such that when two of them meet, they meet along a common edge: Build a set topologically equivalent to a torus with an (open) disk removed. —Dan

1 0

Re: [math-fun] Error correction for integers (bignums)
by Henry Baker 26 Jan '19

26 Jan '19

Hi Victor: Yes, the Elias omega coding is interesting, but it's still going in the exactly wrong direction because a single-bit error can produce catastrophic results in the value decoded. Indeed, any of the usual "lossless compression" algorithms assume that *every individual bit* is accurate, with no errors possible. This is what is called the "digital cliff effect", whereby a cellphone or a digital TV which reaches the edge of its range suddenly finds *no signal at all*, rather than a smoothly degrading signal a la "analog TV" or "analog radio". The only way I can think of to encode integer N in a range [0,M^k) for some "large" M>0 is to utilize a sort of unary code for m bits, followed by a binary code for the remainder mod(N,M), in a manner very Golumb-like. The unary code has a fixed length dependent upon k, and decoding is easy: HammingWeight(unary code portion)*M+Binarycode(remainderbits) Thus a single-bit error in the unary part can cost at most M (out of M^k), and a single-bit error in the remainder costs at most M/2. Thus, no single bit can cause a catastrophic loss. At 09:27 AM 1/26/2019, Victor Miller wrote: >https://en.m.wikipedia.org/wiki/Elias_omega_coding > >On Sat, Jan 26, 2019 at 10:32 Henry Baker <hbaker1(a)pipeline.com> wrote: >> I just found that the canonical name >> for this type of coding is called >> "Golomb coding": >> >> We choose a suitable a priori fixed M >> based upon the (fixed) statistics of >> the integer N being encoded. >> >> Compute (q,r) = (floor(N/M),mod(N,M)). >> >> Then the code for N is unary(q)|binary(r). >> >> More accurately, we actually encode N-1: >> >> (q,r) = (floor((N-1)/M),mod(N-1,M)) >> >> code is unary(q)|1|binary(r). >> >> https://en.wikipedia.org/wiki/Golomb_coding >> >> Here's a page with worked-out examples: >> >> >> https://w3.ual.es/~vruiz/Docencia/Apuntes/Coding/Text/03-symbol_encoding/09… >> >> Once again, I claim that the Roman numeral requirement >> for unary coding of thousands, e.g., "MMMMMM" for 6,000, >> was an *advantage*, since the mere size of the representation >> would more quickly distinguish it from the representation >> for 3,000. The Roman numeral system *approximated Golumb >> coding* thousands of years before Golomb. >> >> https://en.wikipedia.org/wiki/Roman_numerals >> >> At 02:33 AM 1/26/2019, Dave Dyer wrote: >> >Assuming I had a large number of integers to protect, my thought >> >would be to feed them through a good compressor, maybe LZW, and >> >then apply ECC to the resulting high entropy strings. The initial >> >representation of the integers wouldn't matter much.

1 0

Re: [math-fun] Fwd: Visualization puzzles - SPOILERS
by Dan Asimov 26 Jan '19

26 Jan '19

I wondered about those rotated lattices, too. Let L_0 = Z^2 and Let e(t) = exp(2πit) for t in R. So e(t) = e(t') <=> t-t' in Z. L_t = e(t) * L_0 (so that L_t has period π/2) and ask: What is the average number of vertices of L_0 lying in a single cell (Voronoi region) of L_t (or vice versa — it's symmetrical). Possibly this is best asked as a function of the distance R from the origin (common to all L_t's). And asymptotically. So we'd like to know lim (# pts. v=(K,L) with |v| in [R, R + eps) / area(R, R+eps) R—>oo = lim (# pts. v=e(t)*(K,L) with |v| in [R, R + eps) / (π*eps(2*R + eps)) R—>oo where the denominator is the area of the annulus between radii R and R+eps. In case the limit depends on eps > 0, take the additional limit as eps —> 0. —Dan ----- On a similar note, let S be the set of lattice points Z^2 on R^2. Let T be S rotated by angle A about the origin. Is there a bijection f from S to T and constant c such that for all points p in S, |p - f(p)| <= c? -----

1 0