August 2014 - mathfun@mailman.xmission.com

[math-fun] enhanced trapezoidal rule
by Warren D Smith 30 Aug '14

30 Aug '14

For computing integral F(x) dx integrated from -1 to +1, employ (1/N) * SUM_j F(x_j) summed over the N points x_j = [j-(N-1)/2] * 2/sqrt(N^2-1) for j=0,1,2,...,N-1. This is equal weight, equal spacing, and exact if F(x) is a polynomial of degree<=3. The two extreme points are located at +-sqrt((N-1)/(N+1)). If you try to integrate x^4 with this method, you get additive error = (8/15) / (N^2-1).

1 0

[math-fun] partitions into powers of 2
by Warren D Smith 30 Aug '14

30 Aug '14

How many ways PB(N), are there to partition N into powers of 2? Pretty soon I discovered most things I had to say about this, were already stated here: http://oeis.org/A018819 However, the OEIS, or at least this entry, does not discuss asymptotics. (Shouldn't there be a section "asymptotics" for many sequences?) It is easy to see that, if N>=1, then N^(A+B*lg(N)) <= PB(N) <= N^(C+D*lg(N)) where lg(x) = log(x)/log(2) and A,B,C,D are constants. Indeed, C=D=1 and A=0,B=1/4 are valid, the former ought to be obvious. To do a bit better: By using the recurrence PB(N) = SUM( PB(j), j=0..floor(N/2) ) we can show PB(N) <= (N/2+1)^lg(N). It follows that D=1, C=-1 should be valid asymptotically. We also can see from the same recurrence that PB(N) grows ultimately faster than N^((1-epsilon)*lg(N)) for any epsilon>0. Thus limit lg(PB(N))/lg(N)^2 = 1. It is not so obvious, though, whether there is some expression of our form (or any other simple form) that is asymptotic to PB(N) for large N... and if so, what it is. There are a huge number of generating function identities and recurrences you can write down. The recurrences PB(2m+1) = PB(2m) = PB(2m-1) + PB(m) suggest the approximate differential equation 2*PB'(x) = PB(x/2). It might be possible to determine the asymptotics of PB by substituting appropriate ansatzes into this differential equation. Saddlepoint methods involving generating functions might also work.

2 3

Re: [math-fun] Associativity & finite state machines
by Henry Baker 30 Aug '14

30 Aug '14

Bingo! Thanks! At 08:43 AM 8/30/2014, W. Edwin Clark wrote: >I believe the most sweeping result of the type you are looking for is the Krohn-Rhodes Theorem: > http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory ><http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory> >John Rhodes has written a book applying this theory to everything from evolution to the meaning of life: >*Applications of Automata Theory and Algebra via the Mathematical Theory of >Complexity to Biology, Physics, Psychology, Philosophy, and Games.* > >On Sat, Aug 30, 2014 at 10:58 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> I was trying to develop an intuition about associative operations over a >> finite set. >> >> There seems to be a close relationship between such operations and finite >> state machines. >> >> The associative operations that start to look like the operation of a >> "zero" seem to be those that "remember" something that happened at the left >> end of the string input into the finite state machine, or alternately, >> those that "remember" something that happened at the right end of the input >> string. >> >> Of course, you can compose direct products of such operations, so that the >> direct product finite state machine can remember things that happened at >> both ends. >> >> Finally, there are a much smaller number of such finite state machines >> that remember something more interesting about the input string as a >> whole. These include associative operations that are actually groups, >> including commutative groups. >> >> It's been a very long time since I've thought about these things. Are >> there any ready online references -- in particular about factoring such >> associative operations into direct products ?

1 0

[math-fun] Associativity & finite state machines
by Henry Baker 30 Aug '14

30 Aug '14

I was trying to develop an intuition about associative operations over a finite set. There seems to be a close relationship between such operations and finite state machines. The associative operations that start to look like the operation of a "zero" seem to be those that "remember" something that happened at the left end of the string input into the finite state machine, or alternately, those that "remember" something that happened at the right end of the input string. Of course, you can compose direct products of such operations, so that the direct product finite state machine can remember things that happened at both ends. Finally, there are a much smaller number of such finite state machines that remember something more interesting about the input string as a whole. These include associative operations that are actually groups, including commutative groups. It's been a very long time since I've thought about these things. Are there any ready online references -- in particular about factoring such associative operations into direct products ?

2 1

[math-fun] conformal & projective groups
by Warren D Smith 30 Aug '14

30 Aug '14

Perhaps you should consider "Joseph Liouville's theorem" stating that the only conformal transformations of D-dimensional space, if D>2, are spherical inversions, reflections in hyperplanes, and their compositions.

1 0

Re: [math-fun] Stupid associativity question
by Christian G. Bower 30 Aug '14

30 Aug '14

Some time ago Rich proposed the concept of "dull semigroup" defined as a(bc) = (de)f for all a,b,c,d,e,f that did a good job of characterizing the asymptotic behavior of semigroups. I'm not sure how to prove it, but it's fairly obvious that # dull semigroups / # semigroups rapidly goes to 1. Rich showed that while commutive initially grows faster than associative, associative eventually outgrows commutative and calculated when. (I think it was somewhat above n=100). Dull semigroup is essentially where every product of 3 elements is the 0 element. Thus we must have a zero element (0x = x0 = 0 for all x). There is a set of elements Z that produce 0 in any product, i.e. if z in Z zx=xz=0 for all x. All products produce an element of Z. ------ Original Message ------ Received: Tue, 19 Aug 2014 08:49:18 PM PDT From: Henry Baker <hbaker1(a)pipeline.com> To: math-fun <math-fun(a)mailman.xmission.com> Subject: Re: [math-fun] Stupid associativity question > Sorry, one additional question: > > 3. how constraining is associativity, in the sense of reducing the number of different operators? E.g., commutativity cuts out nearly half of the degrees of freedom; what % of the degrees of freedom does associativity cut out ? > > At 06:02 PM 8/19/2014, Henry Baker wrote: > >I'm interested in binary operations on a finite set S that are associative, period; no other constraints. > > > >1. Are there "fast" methods for checking associativity given the operation table? > > > >2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ? > > > >(RCS knows why I'm asking this question.) > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

[math-fun] Just curious
by David Wilson 30 Aug '14

30 Aug '14

Is there a closed form for f(x) = SUM n=1..inf (ln(n)*x^n)

2 2

[math-fun] Fano question
by David Wilson 29 Aug '14

29 Aug '14

Can the Fano plane be modeled as 7 distinct congruent circles (Fano lines) with 7 distinct intersection points (Fano points) in some R^n? Dropping "congruent" makes it easy, any 7 points in general position in R^3 will do.

1 0

Re: [math-fun] sum 1/Fib[n] finale(?)
by Bill Gosper 29 Aug '14

29 Aug '14

On 2014-08-29 06:30, Joerg Arndt wrote: > * Bill Gosper <billgosper(a)gmail.com> [Aug 29. 2014 14:30]: >> Choosing the simplest alternatives in >> http://mathworld.wolfram.com/ReciprocalFibonacciConstant.html >> leads to the remarkably simple http://gosper.org/recipfib.pdf . > > I was not aware of this. > Btw. those \Gamma^{(1,0)} and \Psi^{(0)} should be defined. Agreed. > >> Jörg, did you know about this all along? (My Borwein&Borwein >> is still AWOL.) > Thanks for the peek! Just as I remembered, they give only a Lambert series, which is practically a no-op. > All I know is in http://arxiv.org/abs/1202.6525 > Summation only for first terms 0 and 1, and determinant > 0 > (I did not find how to treat det < 0 IIRC). > > Was aimed at Fib. Quart., but gave up after finding > main result in an older paper (as now remarked). > > Pari code at > http://jjj.de/pari/ > (file lambert.gpi, at end of file) > > >> Wikipedia still has two articles maintaining >> no closed form. > > No closed form with > http://en.wikipedia.org/wiki/Reciprocal_Fibonacci_constant > But two (in Theta-nulls) with > http://en.wikipedia.org/wiki/Fibonacci_number#Reciprocal_sums No, they just have 1/Fib[2n+1] and 1/Fib[n]^2, etc, like your paper. "No closed formula for the reciprocal Fibonacci constant <https://en.wikipedia.org/wiki/Reciprocal_Fibonacci_constant> [image: \psi = \sum_{k=1}^{\infty} \frac{1}{F_k} = 3.359885666243 \dots] is known,..." > > >> Are they really stodgy with their definition, >> or just uninformed? > > Not sure what you are aiming at. Correcting the claim of no closed form. The talk page agonizes needlessly over whether 𝜗 is closed form, but the main Fib article uses it shamelessly for sum 1/Fib[2n+1] etc. > Certainly those theta formulas should appear > on the page Reciprocal_Fibonacci_constant as well! With credit to whom?? I followed a couple of Weisstein's leads and found the q-Gamma' formula nowhere. I'm betting he found it himself, quietly observing that the log derivative of the q-Gamma infinite product is a Lambert series. This is almost obvious, except that Mathematica makes it almost impossible to automatically turn log(product) into sum(logs). Maybe he secretly used Macsyma!-) >From the 23 May discussion, ----------- Jörg>Have you checked Borwein/Borwein "Pi and the AGM"? pp.91-101 might make you happy. rwg>Sadly not)-: They denote this Lambert series -L(q), but never give it in terms of Thetas or ThetaPrimes. Despite the section heading, they never deliver Sum 1/Fib(n) except in terms of L. It may well be inexpressible without some new special function. (They do give Sum 1/Fib(2*n+1) in Thetas, which is easy.)<rwg But did they give it in terms of q-digamma and I somehow missed or rejected it? http://mathworld.wolfram.com/ReciprocalFibonacciConstant.html claims they do! Could it have been added in a later edition? My (autographed) first edition is unhandy. Here I thought I had capped my 40 yr search, and the answer is sitting in Mathworld. --------------------- Weisstein apparently considers slipping his own results into Mathworld tantamount to public announcement. He did the same thing to NeilB, who worked for months to break the π continued fraction record, unaware that Weisstein had already done so. --rwg > >> >> --rwg >> > > Btw. It's a fun exercise to change between the English and the > German WikiPedias (even if you do not understand Krautisch). > > > Best, jj > >> [...]

1 0

[math-fun] sum 1/Fib[n] finale(?)
by Bill Gosper 29 Aug '14

29 Aug '14

Choosing the simplest alternatives in http://mathworld.wolfram.com/ReciprocalFibonacciConstant.html leads to the remarkably simple http://gosper.org/recipfib.pdf . Jörg, did you know about this all along? (My Borwein&Borwein is still AWOL.) Wikipedia still has two articles maintaining no closed form. Are they really stodgy with their definition, or just uninformed? --rwg To: math-fun(a)mailman.xmission.com Sent: Friday, May 23, 2014 3:00:22 AM Subject: sum 1/Fib[n] Argh! From: rwg(a)sdf.lonestar.org < rwg(a)sdf.lonestar.org > [Jul 12. 2008 16:01]: [...] but still nothing about plain old inf ==== n \ q > ------, / n ==== q - 1 n = 1 with which we could sum the reciprocal Fibonacci numbers. Jörg>Have you checked Borwein/Borwein "Pi and the AGM"? pp.91-101 might make you happy. rwg>Sadly not)-: They denote this Lambert series -L(q), but never give it in terms of Thetas or ThetaPrimes. Despite the section heading, they never deliver Sum 1/Fib(n) except in terms of L. It may well be inexpressible without some new special function. (They do give Sum 1/Fib(2*n+1) in Thetas, which is easy.)<rwg But did they give it in terms of q-digamma and I somehow missed or rejected it?http://mathworld.wolfram.com/ReciprocalFibonacciConstant.html claims they do! Could it have been added in a later edition? My (autographed) first edition is unhandy. Here I thought I had capped my 40 yr search, and the answer is sitting in Mathworld. The only consolation is that my answer doesn't use 𝜗s, so we get this peculiarity: EllipticTheta[2, 0, ϕ^-2]^2 = 2 Im[QPolyGamma[0, 1/2 + I π/(4 Log[ϕ]), ϕ^-2]]/Log[ϕ] ~ 3.26379 Can this generalize, or is it only about the Golden Ratio? --rwg

2 1