December 2016 - mathfun@mailman.xmission.com

[math-fun] record computation of Pi ,
by Simon Plouffe 11 Dec '16

11 Dec '16

They made a new computation record of Pi, http://www.numberworld.org/y-cruncher/records.html 22 459 157 718 361 digits. This is big. the digits seems to be rather normal in base 10 and 16. https://arxiv.org/ftp/arxiv/papers/1612/1612.00489.pdf also : 22.459157718361 is Pi^E. Some explanations here : http://pi2e.ch/ best regards, Simon Plouffe

2 1

[math-fun] Grochow/Moore: "Matrix multiplication algorithms from group orbits"
by Joerg Arndt 10 Dec '16

10 Dec '16

Some of us may like the preprint at https://arxiv.org/abs/1612.01527 Abstract: We show how to construct highly symmetric algorithms for matrix multiplication. In particular, we consider algorithms which decompose the matrix multiplication tensor into a sum of rank-1 tensors, where the decomposition itself consists of orbits under some finite group action. We show how to use the representation theory of the corresponding group to derive simple constraints on the decomposition, which we solve by hand for n=2,3,4,5, recovering Strassen's algorithm (in a particularly symmetric form) and new algorithms for larger n. While these new algorithms do not improve the known upper bounds on tensor rank or the matrix multiplication exponent, they are beautiful in their own right, and we point out modifications of this idea that could plausibly lead to further improvements. Our constructions also suggest further patterns that could be mined for new algorithms, including a tantalizing connection with lattices. Best regards, jj

3 8

Re: [math-fun] overqualified typesetters
by Bill Gosper 09 Dec '16

09 Dec '16

Date: 2016-12-09 06:45 From: James Propp <jamespropp(a)gmail.com> I just posted to MathOverflow (tag: "terminology") to see if anyone can provide info on the radiculus function. Maybe G.H. Hardy collaborated with Alfred Haar on a two-author paper about the radiculus function, with Hardy getting priority in the author-list despite Haar being alphabetically prior? :-) Jim Propp On Friday, December 9, 2016, Dan Asimov <asimov(a)msri.org> wrote: > Do you call this utterly miscellaneous because why choose that particular > product, or because of how it's displayed (instead of gathering the powers > of 3 — or better, sqrt(3) — in one place) ? > > —Dan The former. I wouldn't consider eccentric notation "miscellaneous". But Gauss gave us a formula for Γ(x+1/n) Γ(x+2/n) ... Γ(x+1). Why exhibit this nebbish special case of it? --rwg > > > > On Dec 9, 2016, at 12:50 AM, Bill Gosper <billgosper(a)gmail.com > <javascript:;>> wrote: > > > > the utterly > > miscellaneous > > Product[Gamma[k/3], {k, 8}] == 640/3^6 (\[Pi]/Sqrt[3])^3 >

1 0

[math-fun] overqualified typesetters
by Bill Gosper 09 Dec '16

09 Dec '16

>From Littlewood's Miscellany: A minute I wrote (about 1917) for the Ballistic Office ended with the sentence `Thus σ should be made as small as possible'. This did not appear in the printed minute. But P. J. Grigg said, `What is that?' A speck in a blank space at the end proved to be the tiniest σ I have ever seen (the printers must have scoured London for it). Modern editions of Gradshteyn and Ryzhik, 8.338 (5.) give the utterly miscellaneous Product[Gamma[k/3], {k, 8}] == 640/3^6 (\[Pi]/Sqrt[3])^3 (Ascribed to WH. An exercise in Whittaker and Watson?) The first English edition absurdly has Product[Gamma[k/3], {k,∞)] presumably photocopied from the Russian original. The next English edition (which I can find neither online nor in my basement) has the formula obviously corrected by scissoring out the ∞ and turning it sideways. (Apropos my recent rantings, G&R has some exotic "ensemble sums" ascribed to JO (Jolley's Summation of Series?) which are completely bogus. More on this later, hopefully.) Watson's Treatise on the Theory of Bessel Functions, 17·6(3) has Sum(n^2*bessel_j[n](n*z)^2,n,1,inf)=z^2*(4+z^2)*(1-z^2)^(-1/2)/16 Empirically, it should be Sum(n^2*bessel_j[n](n*z)^2,n,1,inf)=z^2*(4+z^2)*(1-z^2)^(-7/2)/16 Presumably Watson had it right, but the printer found the exponent 7/2 too improbable. Additional clue: 17·6(2) also shows a factor of (1-z^2)^(-1/2), but displayed with a radical instead of parens. (I swear I once saw √(1-x²) called the radiculus function. Seems worth resurrecting.) (c19) SUM(N^2*BESSEL_J[N](N*Z)^2,N,1,INF) = Z^2*(4+Z^2)*(1-Z^2)^-(7/2)/16; Time= 0 msec. inf ==== 2 2 \ 2 2 z (z + 4) (d19) > n bessel_j (n z) = -------------- / n 2 7/2 ==== 16 (1 - z ) n = 1 (c20) TAYLOR(%,Z,0,11); Time= 140 msec. 2 4 6 8 10 z 15 z 35 z 525 z 3465 z (d20)/T/ -- + ----- + ----- + ------ + -------- + . . . = 4 16 16 128 512 2 4 6 8 10 z 15 z 35 z 525 z 3465 z -- + ----- + ----- + ------ + -------- + . . . 4 16 16 128 512 (c21) BLOCK([FANCY_DISPLAY : FALSE],PLAYBACK([19,21],TIME)); (Note Macsyma here. After all these decades, Mathematica's Series is still braindead.) --rwg

3 2

Re: [math-fun] propositional logic tautologies
by Henry Baker 05 Dec '16

05 Dec '16

FWIW, the Common Lisp "Boyer" standard benchmark performs propositional logic tautology testing. The following 2 short papers give a bit of detail on how Bob Boyer's algorithm works. http://home.pipeline.com/~hbaker1/LBoyer.html http://home.pipeline.com/~hbaker1/LBoyer.ps.gz http://home.pipeline.com/~hbaker1/BoyerB.html http://home.pipeline.com/~hbaker1/BoyerB.ps.gz At 01:28 PM 12/4/2016, rcs(a)xmission.com wrote: >True. >In fact, you can go a step further and reduce (P v ~P) to T. > >The catch is that the simple algorithm requires, in effect, >trying all combinations of the variables. The work is >about 2^V for V variables. The Satisfiability problem asks >"is there any choice of variables that makes the formula >f(a,b,c,...) true?". The co-problem asks "is f(...) true >for every combination?" SAT is verifiable if you can find >one choice that works; co-SAT is refutable by one counterexample. >But to confirm a tautology requires checking all examples, >or some equivalent, mathematically sound, procedure. > >This limits verification to ~50 variables (depending on your >computer and your patience). Similarly for a search for a >SAT example. There are algorithms & heuristics that improve >this situation somewhat, but the problems appear to be >of exponential difficulty. There's an annual(?) contest of >SAT-solvers; I think the best can handle hard problems of a >few hundred variables. Easy problems can be much bigger, with >thousands of variables. These have some real world uses. > >I don't think Henry expected to go beyond, say, 20 variables. >A complete list of tautologies with even 10 variables and >a few occurrences of each variable would be very big. > >Imagine a binary hypercube of dimension V, hypervolume 2^V cells. >Your job is to completely cover the hypercube with bricks of >volume 1/8 of the total, with overlap permitted. This might >represent the truth-volume of the clause (C & ~F & H). Your >formula has about 4.3 V clauses. Each has 3 variables, and >the clauses are ORed together to make the formula. Is it a >tautology? Observationally, it seems to be about a 50:50 proposition. >10 variables makes 960 clauses of this shape (8 for the negation >patterns, times bin(10,3)=120 for the variable choices). >Select 43 clauses at random: do they cover the whole hypercube? >If 50% of the formulas do, that's .50 * bin(960,43) tautologies. > >Rich > >---------- >Quoting Dan Asimov <asimov(a)msri.org>: > >>I would have guessed that any tautology can be reduced algorithmically >>to a simpler formula until it becomes p v ~p ??? >> >>(So that if the algorithm can't find such a reduction, then that >>proves it wasn't a tautology.) >> >>My main evidence to the contrary is that Rich didn't mention this. >> >>?Dan >> >>>On Dec 3, 2016, at 6:40 PM, Allan Wechsler <acwacw(a)gmail.com> wrote: >>> >>>What does it mean to "solve" a tautology? Is this somehow equivalent to >>>boolean satisfiability? >>> >>>On Sat, Dec 3, 2016 at 9:36 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: >>> >>>>At 06:28 AM 12/3/2016, Henry Baker wrote: >>>>>1. Is there an easy way to enumerate/generate (all and only) >>>>*tautologies* in more-or-less increasing complexity fashion? By >>>>complexity, I mean more-or-less increasing fashion wrt the number of >>>>distinct variables and the size of the expression. >>>> >>>>I thought about this during a long drive today and realized that there >>>>*can't* be an "efficient" (P) algorithm to enumerate all and only >>>>tautologies, else that algorithm would itself be useful to solve >>>>tautologies, and hence P=NP. >>>> >>>>So Rich's idea of generating formulae and then doing tautology-testing may >>>>well be nearly optimal.

1 0

[math-fun] The base 2-i, digits 0,i^0..3 spacefill
by Bill Gosper 05 Dec '16

05 Dec '16

(This Subject is by now completely wrong. Dragons are related to base i-1, digits 0,1.) It seems to me there should be 4 rep4tile "dragons": gosper.org/4flopfour.png , the Heighway and grid 2tiles, because they're also 4tiles, and one other proper 4tile. But my obvious guess makes gosper.org/bogus4tile.png which is not a rep4, maybe not a rep-anything. Jörg, what's the other rep4? Any idea what I blew to make this bogon --rwg -------- Original Message -------- Subject: Re: [math-fun] The base 2-i, digits 0,i^0..3 spacefill Date: 2016-11-21 01:28 From: Joerg Arndt <arndt(a)jjj.de> To: math-fun <math-fun(a)mailman.xmission.com> Reply-To: math-fun <math-fun(a)mailman.xmission.com> * Bill Gosper <billgosper(a)gmail.com> [Nov 21. 2016 10:12]: > [...] > > Even unto the lowly dyadic (Heighway) > > dragon which, if you conjugate at every level, becomes simply a triangular > > patch of a > > square grid. Two back-to-back: gosper.org/dragrid199.png > > --rwg > > Is there a gallery of variously flopped dragons anywhere? > > > Jörg? See http://jjj.de/fxt/demo/bits/#bit-paper-fold-general for "all" variations (for 2^64 \approx \infty). Crucially: static inline bool bit_paper_fold_general(ulong k, ulong w) // Return element number k of the general paper-folding sequence: // bit number x of the words w determines whether // a left or right fold is made at the step x. // With w==0 the result is ! bit_paper_fold(k). // With w==~0 the result is bit_paper_fold(k). // The result with ~w is the complement of the result with w. { ulong h = k & -k; // == lowest_one(k) h <<= 1; ulong t = h & (k^w); return ( t!=0 ); } For edge-covering curves on the grids (3^6), (4^4), and (3.6.3.6) there is http://jjj.de/3frac/ Dive into the directories p?/ (for ? \in {3,4,6}) for pdfs But these are only curves with simple L-systems. By the way, I am preparing high quality prints (poster size), two of which will be shown in Atlanta in January, see http://gallery.bridgesmathart.org/exhibitions/2017-joint-mathematics-meetin… Will any math-funster be there? I have yet to do all "paper-folding" curves a la Davis/Knuth/Dekking for other orders. It's not hard, but I have been working on other things. > > > Julian, can they be made with piecewiserecursivefractal? > > > No, but by another function in his same notebook! --rwg

2 1

[math-fun] propositional logic tautologies
by Henry Baker 04 Dec '16

04 Dec '16

I'm a little rusty on my propositional logic, so I can't remember (if I ever knew) the answer to the following questions: 1. Is there an easy way to enumerate/generate (all and only) *tautologies* in more-or-less increasing complexity fashion? By complexity, I mean more-or-less increasing fashion wrt the number of distinct variables and the size of the expression. 2. What % of prop logic expressions (of a particular complexity) are tautologies?

7 10

[math-fun] Trigonometric "ensemble"(?) sums (and products)
by Bill Gosper 02 Dec '16

02 Dec '16

I.e., equally spaced over a period. What's the term? (Special case of sum|product over a root system.) I once convinced myself that *all* of them, even such nasties as Sum[Cot[f + (j*Pi)/n]*Cot[g + (j*Pi)/n]*Cot[h + (j*Pi)/n], {j, 1, n}]/n == -Cot[f*n] - Cot[g*n] - Cot[h*n] - (1/2)*Csc[f - g]*Csc[f - h]*Csc[g - h]* ((-Cot[h*n])*Sin[2*f - 2*g] + Cot[g*n]*Sin[2*f - 2*h] - Cot[f*n]*Sin[2*g - 2*h]) come out in closed form as direct consequences of nothing more than x^n-1 == Product[x-I^(4*k/n), {k, 0,n -1}]. Computer algebra junkies may "enjoy" starting here and plowing through to Sum[1/(a + b*Cos[c + (2*k*Pi)/n]), {k, 0, -1 + n}] == ((b^(2*n) - (-a + Sqrt[a^2 - b^2])^(2*n))*n)/(Sqrt[a^2 - b^2]* (b^(2*n) + (-a + Sqrt[a^2 - b^2])^(2*n) - 2*b^n*(-a + Sqrt[a^2 - b^2])^n*Cos[c*n])) ("I ask a simple question; I get a pageant." --Stan Freberg) --rwg Note the messed up ordering of the nasty cot cot cot result. Is any Computer Algebra able to, e.g., convert Sin[x - y] - Sin[x - z] + Sin[y - z] to Sin[x - y] + Sin[y - z] + Sin[z - x] ? At least Macsyma had trigsign:false to partially inhibit the reverse transformation. But then the sum would be reversed. But it also had ordergreat and orderless, which aliased symbols to have different display orderings. It only accepted individual symbols, not relations between them, but it might barely suffice here. In Mathematica, you can Inactivate all the trigs and then run around manually flipping the anticyclic ones. I'll bet people have built such tools for themselves, but if anybody has a really good solution, WRI should have heard about it.

1 1

[math-fun] We missed it.
by Bill Gosper 02 Dec '16

02 Dec '16

RKG turned 100 on Sep 30 ! --rwg

2 2