April 2014 - mathfun@mailman.xmission.com

[math-fun] WDS rewriting & repairing Fred Lunnon's proof of WDS's Knight-distance formula WRONG
by Warren D Smith 02 Apr '14

02 Apr '14

Nope. Upon reconsideration, my "repair of Lunnon's proof" still was inadequate. True situation is more complicated. What you really need, is to prove f(x,y) = min( f(x-1,y-2), f(x+1,y-2), f(x+2,y-1), ... , f(x-1,y+2) ) with 8 arguments inside the min. That is a pretty nasty recurrence. Lunnon thought with his "sorted x,y" trick he could get rid of the nastiness, and that plus his simplified form of my algorithm yielded his proof. But, while I think that thought is largely true, it is not then as trivial as he thought. Thus in the main "case i" besides (x',y') = (x-2, y-1) we really also need to consider (x',y')=(x-2, y+1), for example. [It may actually be that proving this is a good case for a computer symbolic manipulation program to do, not a human prover. Can we just make it verify the full f(x,y) function obeys the full 8-argument recurrence, and be done?] I think it should now be doable even by a mere human, but there are enough cases and enough error-potential that it is a pain.

1 1

[math-fun] WDS rewriting & repairing Fred Lunnon's proof of WDS's Knight-distance formula
by Warren D Smith 02 Apr '14

02 Apr '14

Lunnon had the right idea but got some details wrong. I repair here. Lunnon's first point is we only need to consider the distance from (0,0) to (x,y) for SORTED (decreasing) (x,y), i.e. with x>=y>=0. Lunnon's nicer rewriting of WDS's Knight-distance algorithm, call the returned value f(x,y): X = max(|x|,|y|); Y = min(|x|,|y|); p = X-Y; q = p-Y; if(q<0) r=3 else r=4 if(X=1 and Y=0) return distance = 3 if(X=2 and Y=2) return distance = 4 return distance = p - 2*floor(q/r); Proof of validity: By induction. Base case is verifying it when 0<=x,y<=8. [Both Lunnon and I did that.] Induction is that, if we are outside the base case, and x>=y>=0, then f(x,y)=f(x-2,y-1)+1. To establish this there are 3 cases: i. (x',y') = (x-2, y-1) also obeys the assumptions x>=y>=0 and min(x,y)>8, or ii. x=y, in which case p=0,q=-x,r=3,f=-2*floor(-x/3); let (x',y')=(x-1,x-2). iii. y=0, in which case p=x,q=x,r=4,f=x-2*floor(x/4); let (x',y')=(x-2,1). In case i, we have p'=p-1 and q'=q and r'=r hence f'=f-1. In case ii, p'=1, q'=3-x, r'=3, hence f'=1-2*floor((3-x)/3)=-1-2*floor(-x/3)=f-1. Lunnon had a wrong proof for this case, but the conclusion f'=f-1 is what matters, and that works. In case iii, which Lunnon just failed to consider, we have p'=x-3, q'=x-4, r'=4, f'=x-3-2*floor((x-4)/4)=x-1-2*floor(x/4)=f-1. No matter which case, you conclude f'=f-1, which is the inductive claim we needed. Q.E.D. -- Warren D. Smith http://RangeVoting.org

1 0

[math-fun] Gosper factorial stuff
by Bill Gosper 02 Apr '14

02 Apr '14

WDS> RWG, you should see work by Chowla & Selberg which I think pre-discovered what you were saying and a good deal more re factorial(n/24) for n=integer. <WDS Thanks. My objective, more clearly stated, is ultimately to automatically simplify factorials(n/d), not just factorials(n/24), by canonicalizing first to minimal d and then to minimal n. So far, reduction is possible for n/d, n>d/2 (by reflection) 1/2, 1/6, 3/8, 4/9, n/10, n/12, n/14, n/15, n>1 5/16, 7/16, n/18, n/20, n>1 n/21, n>2 n/22, n/24, n>1 11/25, 12/25, n/prime, apparently never for prime>2n It would be amazing to find a reduction inaccessible via reflection and tuplication. But how could we tell? --rwg

1 0

[math-fun] knight distance and Gosper factorial stuff
by Warren D Smith 02 Apr '14

02 Apr '14

RWG, you should see work by Chowla & Selberg which I think pre-discovered what you were saying and a good deal more re factorial(n/24) for n=integer. FWL, I don't currently understand what he did, but I think he thinks he produced a fairly short inductive proof of my Knight-distance formula. (Which I'd tried, but failed, to accomplish.) So if you are right, then congratulations. Myself, I had to believe there was a proof of this general ilk, but the only ways I could see to produce it, just sort of led me into a recurrence quagmire. I couldn't un-mess the mess. So anyhow FWL's proof seems suspiciously "too easy" plus I currently am not following it. But on the other hand, it may well be I was just mentally blocked from seeing something fairly easy, while he did. Sorry to be incoherent, I'm a bit sick right now.

1 0

Re: [math-fun] Near-integers
by Adam P. Goucher 01 Apr '14

01 Apr '14

> > 653 [sic] = 163*4, so it's no surprise that it's so close Note that Round[Exp[Pi Sqrt[163]]^2] is not equal to Round[Exp[Pi Sqrt[163]]]^2. Indeed, half of the difference is precisely 196884, the significance of which I'm sure I need not explain... Sincerely, Adam P. Goucher

1 0

[math-fun] HAKMEM Item 1
by Bill Gosper 01 Apr '14

01 Apr '14

ITEM 1 (Schroeppel): (1/3)! and (2/3)! are interexpressible. (1/4)! and (3/4)! are interexpressible. Thus these two pairs are of dimensionality one. (1/10)! and (2/10)! are sufficient to express (N/10)! for all N. (1/12)! and (2/12)! are sufficient to express (N/12)! for all N. (1/3)! and (1/4)! are sufficient to express (N/12)! for all N. Thus the three cases above are of dimensionality two. PROBLEM: Find some order to this dimensionality business. The reflection and multiplication formulas: pi Z Z! (-Z)! = --------- sin(pi Z) (N-1)/2 -NZ-1/2 (2 pi) N (NZ)! = Z! (Z-1/N)! (Z-2/N)! ... (Z-(N-1)/N)! -------------- I was under the misimpression that Mathematica had finally nailed this, but using LR[L_, N_] := Block[{$MaxExtraPrecision = N}, LatticeReduce[ Transpose[Prepend[IdentityMatrix[Length[L]], Round[10^N*L]]]]] (LR for Lattice Reduce or Linear Relation), which finds multiple solutions, unlike FindIntegerNullVector (PSLQ), to find relations among (k/12)! : In[17]:= Join[{2, 3, 5}, (Range[6]/12)!] Out[17]= {2, 3, 5, (1/12)!, (1/6)!, (1/4)!, (1/3)!, (5/ 12)!, Sqrt[\[Pi]]/2} In[18]:= LR[Log[%], 69][[1 ;; 3]] Out[18]= {{0, 6, -1, -2, 2, 3, -4, -6, 2, 3}, {-6, -2, 7, -4, 4, 0, -8, 0, 4, 0}, {-29420553, 655434586, 1447298892, -1344266042, -1749889224, 1253758671, 366295186, 83356101, -1110973039, -416024934}} In[19]:= Rest /@ %[[1 ;; 2]].Transpose[{Log[%%]}] Out[19]= {{6 Log[2] - Log[3] - 2 Log[5] + 3 Log[Sqrt[\[Pi]]/2] + 2 Log[(1/12)!] + 3 Log[(1/6)!] - 4 Log[(1/4)!] - 6 Log[(1/3)!] + 2 Log[(5/12)!]}, {-2 Log[2] + 7 Log[3] - 4 Log[5] + 4 Log[(1/12)!] - 8 Log[(1/4)!] + 4 Log[(5/12)!]}} In[20]:= First /@ Simplify[E^%] Out[20]= {(8 \[Pi]^(3/2) ((1/12)!)^2 ((1/6)!)^3 ((5/12)!)^2)/( 75 ((1/4)!)^4 ((1/3)!)^6), (2187 ((1/12)!)^4 ((5/12)!)^4)/( 2500 ((1/4)!)^8)} In[21]:= N[%] Out[21]= {1., 1.} In[22]:= MapAt[#^(1/4) &, %%, 2] Out[22]= {(8 \[Pi]^(3/2) ((1/12)!)^2 ((1/6)!)^3 ((5/12)!)^2)/( 75 ((1/4)!)^4 ((1/3)!)^6), (3 3^(3/4) (1/12)! (5/12)!)/( 5 Sqrt[2] ((1/4)!)^2)} In[23]:= Numerator[#] == Denominator[#] & /@ % Out[23]= {8 \[Pi]^(3/2) ((1/12)!)^2 ((1/6)!)^3 ((5/12)!)^2 == 75 ((1/4)!)^4 ((1/3)!)^6, 3 3^(3/4) (1/12)! (5/12)! == 5 Sqrt[2] ((1/4)!)^2} In[24]:= FullSimplify[FunctionExpand[%]] /. Gamma[z_] -> (z - 1)! Out[24]= {75 (1/4)!^4 (1/3)!^6 == 8 π^(3/2) (1/12)!^2 (1/6)!^3 (5/12)!^2, 5 Sqrt[2] (1/4)!^2 == 3 3^(3/4) (1/12)! (5/12)!} In[25]:= N[%] Out[25]= {True, True} Is this really that hard a problem? If we can "sort" these, we should move on to the higher factorials (e.g. BarnesG and Hyperfactorial), which have analogous reflection and tuplication formulæ. gosper.org/facfun.pdf . (Recall Date 2014-03-11 02:53 FunctionExpand also appears to disunderstand the tuplication formula Product[Hyperfactorial[-(i/n) + z], {i, 0, -1 + n}] == (E^(z1/n - n*z1)*Hyperfactorial[n*z]^(1/n))/ n^((1 + 6*n*z + 6*n^2*z^2)/(12*n)) whose need it artificially creates for itself when given the Alternating Sign Matrix formula In[171]:= FunctionExpand[Product[(3 k + 1)!/(n + k)!, {k, 0, n - 1}], n > 0 && n \[Element] Integers] Out[171]= (3^(2 - 5 n + 3/2 n (1 + n)) 8^(-1 + n) (BarnesG[5/3] BarnesG[7/3])^(-2 + n) (BarnesG[8/3] BarnesG[10/3])^(1 - n) BarnesG[2/3 + n] BarnesG[1 + n] BarnesG[4/3 + n] BarnesG[2 + n]^( 2 - n) BarnesG[3 + n]^(-1 + n) Gamma[2 + n]^( 1 - n))/(BarnesG[1 + 2 n] Gamma[1 + n]) ) --rwg Old business: I was unable to reproduce that -2=-1 hypergeometric mess for Wolfram's troubleshooters. Now I get a slightly smaller mess which seems numerically correct.

3 5

[math-fun] cos(π/7)^(9/7) ?
by Bill Gosper 01 Apr '14

01 Apr '14

I set about collecting a toolbox of identities relating (n/d)! to <pile of (p/q)!, with q<d, or failing that, (p/d)! with p<n >, in hopes of discerning a pattern. (3/14)! == (7 2^(3/7) Cos[\[Pi]/7]^(9/7) (2/7)! (3/7)! Sin[\[Pi]/7] (Sin[\[Pi]/14] Sin[(3 \[Pi])/14])^(2/7))/Sqrt[\[Pi]] per LatticeReduce, but presumably also from finite massage by the tuplication and reflection formulæ. Uh huh. --rwg Caution: Federal Law prohibits ... almost everything.

1 0