October 2012 - mathfun@mailman.xmission.com

[math-fun] Two twisted cubes
by Warren Smith 09 Oct '12

09 Oct '12

Oops, I do too have an upper bound. So I claim 0 < C1 < f(N) < C2 < 90 degrees for all large-enough N, and would be interested in whatever the best C1, C2 you can cook up, would be, and also in specific values of f(N).

1 0

[math-fun] Two twisted cubes
by Warren Smith 09 Oct '12

09 Oct '12

Consider two 0-centered N-dimensional hypercubes, rotated with respect to each other. Let f(N) = max(over all rotations) min(over all red-blue vertex pairs AB) angle(A0B). For example, f(1)=0, f(2)=45 degrees. This function f is an interesting geometrical quantity. How does this sequence continue? What are its asymptotics? Does f(N) --> 0 when N-->infinity? Or to some positive constant (what)? I know f(4)>=45 degrees. I can prove f(N) > C for some positive constant C (which I could compute) for all large-enough N. I have no upper bound of the form f(N) < C < 90 degrees, but surely one must be true.

1 0

[math-fun] A003114
by Bill Gosper 09 Oct '12

09 Oct '12

Suggested tweaks to the combinatorial interpretations of A003114: Also [number of partitions with all differences > 1, thus by Ferrers transposition,] number of partitions of n such that if k is the largest part, then each of {1, 2, ..., k-1} occur at least twice. Example: a(9)=5 because we have [3, 2, 2, 1, 1], [2, 2, 2, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1] and [1, 1, 1, 1, 1, 1, 1, 1, 1]. (Schur's remark in http://mathworld.wolfram.com/Rogers-RamanujanIdentities.html. Caution: Identity (7) is not true for general a !) Also (http://en.wikipedia.org/wiki/Glaisher%27s_theorem) Also (www.macalester.edu/~bressoud/pub/fpipc.tex) number of partitions into distinct parts with every even part > twice the number of odd parts. In[524]:= Table[ Length[Select[IntegerPartitions[k], FreeQ[Differences[#], 0] && Min[Select[#, EvenQ]] > 2*Length[Select[#, OddQ]] &]], {k, 0, 22}] Out[524]= {1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, 31, 35, 41} --rwg NJAS> Joerg, Yes, certainly! Thank you! Neil On Mon, Oct 8, 2012 at 10:25 AM, Joerg Arndt <arndt(a)jjj.de <http://gosper.org/webmail/src/compose.php?send_to=arndt%40jjj.de>> wrote: > * Bill Gosper <billgosper(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=billgosper%40gmail.com>> [Oct 08. 2012 08:02]:> > (For R-R, special-case a:=q)> >> > [...]> >> > [ inf 2 ]> > [ ==== n n ]> > [ \ a q ]> > [ 0 a > -------------- ]> > inf [ / qpoch(q, q, n) ]> > /===\ [ ==== ]> > | | [ 0 a ] [ n = 0 ]> > (d44) | | [ ] = [ ]> > | | [ k ] [ inf 2 ]> > k = 0 [ q 1 ] [ ==== n n - n ]> > [ \ a q ]> > [ 0 > -------------- ]> > [ / qpoch(q, q, n) ]> > [ ==== ]> > [ n = 0 ]> >> > [...]>> I toyed around a bit (note my start k=1 of the product):>>>> [ inf 2 ]> [ ==== n ]> [ \ q ]> [ 0 > -------------- ] (UR = H(q) => A003106)> inf [ / qpoch(q, q, n) ]> /===\ [ ==== ]> | | [ 0 1 ] [ n = 0 ]> (dxx) | | [ ] = [ ]> | | [ k ] [ inf 2 ]> k = 1 [ q 1 ] [ ==== n + n ]> [ \ q ]> [ 0 > -------------- ] (LR= G(q) => A003114)> [ / qpoch(q, q, n) ]> [ ==== ]> [ n = 0 ]>> I.e., R-R proper.> I am much tempted to put that into both A003106 and A003114> (obviously with attribution to RWG). OK, Neil ?>>>> [ inf 2 ]> [ ==== n - n ]> [ \ q ]> [ 0 q > -------------- ] (UR=A006141)> inf [ / qpoch(q, q, n) ]> /===\ [ ==== ]> | | [ 0 q ] [ n = 0 ]> (dxx) | | [ ] = [ ]> | | [ k ] [ inf 2 ]> k = 1 [ q 1 ] [ ==== n ]> [ \ q ]> [ 0 > -------------- ] (LR= H(q) => A003106)> [ / qpoch(q, q, n) ]> [ ==== ]> [ n = 0 ]>> inf> /===\> | | [ 0 q^n ] [ 0 D(q) ] (D=A000009)> (dxx) | | [ ] = [ ]> | | [ k ] [ 0 D(q) ] (D=A000009)> k = 1 [ 1+q 1 ]>>>> inf> /===\> | | [ 0 -q^n ] [ 0 E(q) ] (E=A010815 = 1/A000041)> (dxx) | | [ ] = [ ]> | | [ k ] [ 0 E(q) ] (E=A010815 = 1/A000041)> k = 1 [1-q 1 ]>>> ASCII for president!> SHHHHH! Rich said no politics.

2 1

Re: [math-fun] tiny 2x2 simultaneously computes both Rogers-Ramanujan sums
by Bill Gosper 08 Oct '12

08 Oct '12

Jörg>Nice. >Could you supply an non-garbled version (image?) of >the things below (c45)? Here's a png <http://gosper.org/r-r2x2.png>. I haven't yet figured out how to get the sums = products from the 3x3s. Interestingly, an eavesdropper also got a garble, but it was ungarbled (except for nonfixed font) as quoted back to me. Sometimes you can just delete some spurious linebreaks. But isn't it high time math-fun supported typesetting? I resorted to Macsyma's ancient ASCII rendering due to OutputForm's industrial strength preemptive garbling. --rwg Jörg>These may be of interest: {Johann Cigler: {A new class of $q$-Fibonacci polynomials}, The Electronic Journal of Combinatorics, vol.10, no.1, (2003). URL: \url{http://www.combinatorics.org/Volume_10/Abstracts/v10i1r19.html}.} {Johann Cigler: {$q$-Fibonacci Polynomials and the Rogers-Ramanujan Identities}, Annals of Combinatorics, vol.8, no.3, pp.269-285, (September-2004). URL: \url{http://homepage.univie.ac.at/johann.cigler/preprints/fibon.pdf}.} (I can email the final version of second, it's pay-walled). Possibly more pertinent papers at http://homepage.univie.ac.at/johann.cigler/electr.html Regards, jj * Bill Gosper <billgosper(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=billgosper%40gmail.com>> [Oct 08. 2012 08:02]:> (For R-R, special-case a:=q)> > (c44) 'PRODUCT(MATRIX([0,A],[Q^K,1]),K,0,INF) => MATRIX([0,SUM(A^(N+1)*Q^N^2/QPOCH(Q,Q,N),N,0,INF)],[0,SUM(A^N*Q^(N^2-N)/QPOCH(Q,Q,N),N,0,INF)]);> > [ inf 2 ]> [ ==== n n ]> [ \ a q ]> [ 0 a > -------------- ]> inf [ / qpoch(q, q, n) ]> /===\ [ ==== ]> | | [ 0 a ] [ n = 0 ]> (d44) | | [ ] = [ ]> | | [ k ] [ inf 2 ]> k = 0 [ q 1 ] [ ==== n n - n ]> [ \ a q ]> [ 0 > -------------- ]> [ / qpoch(q, q, n) ]> [ ==== ]> [ n = 0 ]> > (c45) TAYLOR(PRUD(PART(%,1,1),K,0,7) = MAKEPROD(RHS(%)),Q,0,6);> [GARBLED]

3 2

[math-fun] "binding box"?
by Marc LeBrun 07 Oct '12

07 Oct '12

This seems like it ought to be obvious, but I¹m not seeing it. I¹m interested in the problem of deciding whether a point is inside/outside a polygon. Given the vertexes of a polygon, there are a several of ³classic² ways known to compute this test (eg for graphics applications) . Furthermore, it¹s a commonplace computational optimization, to enable quicker culling of points far from the polygon, to construct a bounding box (eg a rectangle aligned with the axes) so that any point outside the box is certainly outside the polygon (eg box corner coordinates are min/max of the polygon¹s). I¹m wondering: how hard is it to compute a sort of ³conceptual dual², a ³binding box², such that any point inside the box is certainly inside the polygon? We can restrict the problem to non-self intersecting polygons, but they may have zigzagging concavities. Perhaps easier would be to use circles, maybe some kind of projective inversion?

4 3

[math-fun] stronger Hurwitz # thm
by Bill Gosper 07 Oct '12

07 Oct '12

The quasiperiod for the continued fraction of e ~ 2.718 can be written as the three polynomials {1,2k,1}, "modulo rotation and translation", e.g. {2k-2,1,1}. It can also be "inflated" by a factor of 2 or 3 or ..., e.g {1,4k,1,1,4k+2,1} or {1,6k,1,1,6k+2,1,1,6k+4,1} or ... . If I heard him right, Julian has proved that given the Hurwitz # x :={P0(k),P1(k),...}, there is an inflation factor Δ ≤ (ad-bc)^4 such that the quasiperiod of y:=(ax+b)/(cx+d) can be written by inflating x by Δ and then replacing each polynomial Pi with an even number of constant polynomials, followed by a polynomial with the same degree as Pi. In particular, linear terms cannot arise from nonlinear terms. The resulting CF of y may often be "deflated" to have a shorter quasiperiod than x. --rwg One use of this theorem is to detect the possibility or impossibility of finding a homographic transformation shortening a long quasiperiod. For some reason, Julian disavows calling this a "structure theorem". It can probably be extended to cover exponential (e.g.) as well as polynomial terms.

1 0

[math-fun] A problem on highly-cancelling polynomials
by Warren Smith 07 Oct '12

07 Oct '12

Let m be a "whoo-whee number" if there exist 4 polynomials A(x), B(x), C(x), D(x) with degree(A)=degree(B)=m, degree(C)=degree(D)=m+1, all coefficients in all polynomials +-1, and A(x)A(1/x)+B(x)B(1/x)+C(x)C(1/x)+D(x)D(1/x) = 4m+6. Note the right hand side does not depend on x, so we are asking for a lot of cancellation here. I can show there are an infinite set of whoo-whee numbers. Computers seem to think every number is a whoo-whee number (at least as far out as computers can see). THE (UNSOLVED) PROBLEM: prove the count of whoo-whee numbers below X ultimately grows at least like some positive power of X, for example X^0.001. Ideas welcome even if not solutions. This is an example of a frustrating combinatorial construction problem where the gulf between what seems true (all numbers) and what I can prove (a very sparse set of numbers) is enormous, but it might not be hard to break the impasse. Warren D. Smith warren.wds AT gmail.com

4 5

[math-fun] sets with distinct subset sums
by Warren Smith 05 Oct '12

05 Oct '12

PROBLEM: What is the largest N such that an M-element subset of {1,2,3,...,N} exists, with all subset-sums unequal? ALMOST EQUIVALENT PROBLEM: maximize M with N fixed. BOUNDS: It appears that the arguments Moulton & I were using, and various other arguments we did not use, all prove upper and lower bounds on M which when N is large are of the form lg(N) + c*lglg(N) + lower order terms for different real constants c, where lg(X)=log(X)/log(2). The naive upper bound has c=1. My cleverer Chebyshev-based argument with optimized k=sqrt(3) gets it down to c=1/2. [Perhaps something else could do better? I am unsure whether Moulton's technique is ultimately stronger or weaker than my Chebyshev-based technique.] A lower bound arising from just letting the M-subset be 1,2,4,8,16,...,2^(M-1) which obviously has distinct subset sums from binary number system, has c=0. Tom Bohman in 1997 paper reveals this all is actually a $500 Erdos problem (thanks a lot Miller...) and claims he has the best lower bound which is N>0.22002*2^M. But this still has c=0. cite: www.combinatorics.org/Volume_5/PDF/v5i1r3.pdf Bowman also reveals the best known upper bound due to Erdos & Moser and Elkies involves, like mine, c=1/2. cite: J.Combin.Th. A 41 (1986) 89-94. So as of now I've been unable to shrink the c-window below [0, 1/2], but it turns out all those other guys over a 60 year+ period have not been able to either.

1 0

Re: [math-fun] Disjoint subset sums problem by Victor Miller, solved CORRECTED.
by Warren Smith 04 Oct '12

04 Oct '12

Sorry, I think due to mouse typo I posted my wrong file, not my later correct file, giving the solution. (Arithmetic errors.) Here is the later solution. > Say that a finite set of integers, A, has *property P* is there are two > non-empty disjoint subsets S and T of A, such that sum(S) = sum(T) > (where sum(X) is the sum of the elements of X). > > 1) Show that every 10 element subset of {1,...,100} has property P (this > is fairly easy). > 2) Is it true that every 9 element subset of {1,...,100} has property P? --Suppose we have an M-element subset of {1,2,...,N}. Let us try to prove that is M is large enough, then the subset must have "Miller's property P" (while trying not to barf at the horrible name). The number of nonempty subsets of the M-set is 2^M-1. The subset sum must be in the range [1,2,...,N*M]. Hence two subset sums must be equal, if 2^M-1 > N*M. This sum-equality implies a sum-equality for DISJOINT sums because just remove the shared summands form both sums. When N=100 and M=10 we have 2^10-1 = 1023 > 10*100 = 1000, so Miller's question (1) is solved: 10 is impossible. ---- It would be possible to solve Miller's problem 2 by computer: There are binomial(100, 9) = 1.9*10^12 subsets. Can use negation symmetry to halve it, and shift-symetry for all subsets whose min and max elements are not full range, to get a large reduction... so it should be feasible to solve by brute force. ----- To solve his problem 2 without computer, we need a somewhat stronger bound. Consider only nonempty subsets of the M-set with L <= cardinality <= J. If Sum[K=L..J]of binomial(M, K) > N*J - L + 1 then two such subsets must have equal sum, and it is not possible for one to be contained in the other (since all summands positive) hence by removing shared elements we get two equal disjoint subset sums. But... this bound is not strong enough to solve Miller problem 2 with N=100, M=9>=J>L>0, although it would have been if N=77 using J=6. To do better, we need to use the fact that the subsubset sums are nonuniformly distributed within the permitted range [L ,..., N*J]. Considering a random J-subset of our M-set, its mean is J*Q (where Q is the mean value of an M-set element) and its variance<(min(J, M-J)/4)*(N-1)^2 where I am here cleverly using the fact we sample from the M-set WITHOUT replacement, that's why that min is there. (The variance of a sum is the same as variance of complement-set-sum.) We actually can even do a tiny bit better than that, reducing the (N-1)^2 / 4 to ((N-1)^2 + (N-3)^2 )/ 2 if we are talking about J=4 element sets, maximum variance occurring if the 4 elements are N, N-1, 1, and 2. The probability we are within k standard deviations off mean, is >=1-1/k^2 (http://en.wikipedia.org/wiki/Chebyshev's_inequality). This means we can, by choosing k optimally, "amplify" the effectiveness of the above naive bound. For example, M=9, there are 2^9-1=511 subsets. Of those 511 subsubset sums, at least 511*(1-1/1.746^2)=343.377 of them, i.e. at least 344 in view of integrality, lie within 1.746 standard deviations i.e. less than +-1.746*(N-1.5)=1.746*98.5=171.98 off mean, i.e. +-171 in view of integrality. Since 345 > 171+171+1 = 344 the theorem is (just barely!) proven -- 9 is not possible! ----- I have a sneaking suspicion Miller had a modular argument in mind. I also suspect by using better tail bounds than Chebyshev we could do a bit better still. You might want to consider those possibilities... by milking them all, what is the best bound one can get?

1 0

[math-fun] Causality in physics
by Warren Smith 04 Oct '12

04 Oct '12

> http://www.eurekalert.org/pub_releases/2012-10/uov-qcr100212.php > Subject: Re: [math-fun] A causes B causes A > Am I missing something here, or isn't this all rather obvious? --in QED (quantum electrodynamics, Feynman 1950s) and all subsequent particle physics, positrons can be interpreted as electrons moving backwards in time, and there is no one direction of causality in the Feymnamn diagram, several overlapping "directed causality paths" are overlapping and can go in "different directions" in portions. This has been well known since the 1950s and essentially all calculations in QED use it. It presumably is highly experimentally confirmed in the sense that QED is highly confirmed. So, if that press release is an accurate description of what they did (which I do not know), then that is pathetic.

2 1