- mathfun@mailman.xmission.com - mailman.xmission.com

[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

Re: [math-fun] meth-fun
by Henry Baker 29 Nov '16

29 Nov '16

[This is a serious question.] Although it isn't much talked about (in some cases because those who took it weren't aware of what they were taking), meth was heavily used on both sides in WWII to attempt to accomplish 'impossible' tasks. Having seen "The Imitation Game", I have the question: did those working on Enigma et al use meth? At 09:02 AM 11/29/2016, James Propp wrote: >Are meth and math so different? Both can provide temporary escape from reality. :-) > >Jim Propp > >On Mon, Nov 28, 2016 at 8:01 PM, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: > >> Serves 'em right --- they should have stuck to Matematica. WFL >> >> On 11/28/16, Bill Gosper <billgosper(a)gmail.com> wrote: >> > (via Carolyn Bickford) >> > >> > http://www.imediaethics.org/math-lab-bust-whoops-kentucky-tv-news-botches-o… >> > --rwg >> > And metaheadline writer botches oops into whoops.

1 0

[math-fun] meth-fun
by Bill Gosper 29 Nov '16

29 Nov '16

(via Carolyn Bickford) http://www.imediaethics.org/math-lab-bust-whoops-kentucky-tv -news-botches-on-air-caption/ --rwg And metaheadline writer botches oops into whoops.

3 2

[math-fun] Idea for a plaque
by Bill Gosper 28 Nov '16

28 Nov '16

Spelling lessons aren't quite as passé as spell-checkers might make them seam. --rwg

1 0

Re: [math-fun] Exactly Distributed Digits in the Initial Digits of Pi
by Dan Asimov 26 Nov '16

26 Nov '16

Yes, that is a famous result of George Polya from 1921 that is explained in Feller vol. 1. I found it amazing at first that 1 and 2 dimensions should differ from all higher dimensions in that respect. This also has implications for heat flow in those dimensions: If n-space is a (homogenous and isotropic) heat-conducting medium with the unit ball kept at unit temperature and the rest of n-space beginning at temperature 0 at t = 0, then for n = 1 and n = 2, n-space asymptotically warms up to unit temperature but not for n >= 3 (cf. "There's no space like home", The Sciences, September-October 1995). —Dan >From: Hans Havermann <gladhobo(a)bell.net> >Sent: Nov 26, 2016 9:46 AM >I have been informed by Warren D. Smith that it is known that 1- and 2-dimensional random walks are recurrent, while 3-dimensional (and higher) such walks are transient. From that perspective, it strikes me that the sequence 15, 18, ... (third term > 8*10^9) [the number of initial digits of ternary pi where the digits 0, 1, and 2 appear exactly the same number of times] should be recurrent because it can be modeled by a 2-dimensional (presumably random) walk (just as I had done in my blog article). The implication would be that this sequence is infinite!

3 2