June 2006 - mathfun@mailman.xmission.com

[math-fun] Dedekind eta relations
by R. William Gosper 27 Jun '06

27 Jun '06

Let inf /===\ a a/24 | | a n h := eta(q ) = q | | (1 - q ). a | | n = 1 Then if r,s,t are rationals (or w.l.o.g. integers), it appears that there will always be some polynomial P_r,s,t (with integer coefficients) relating h_r, h_s, and h_t. E.g., 8 16 16 8 24 P = 16 h h + h h - h , 1, 2, 4 1 4 1 4 2 (Euler's "aequatio identica satis abstrusa", but our least abstruse.) 3 9 6 6 9 3 12 P = 27 h h + 9 h h + h h - h , 1, 3, 9 1 9 1 9 1 9 3 6 8 12 12 8 6 24 2 24 2 18 8 P = - 3125 h h h - 250 h h h + 256 h h + h h - h h , 1, 2, 5 1 2 5 1 2 5 2 5 1 5 1 2 12 24 48 24 24 36 36 24 24 P = 387420489 h h h + 19131876 h h h + 196830 h h h 1, 2, 3 1 2 3 1 2 3 1 2 3 72 12 24 48 12 48 24 12 72 12 60 24 - 16777216 h h - 196608 h h h - 12 h h h - h h + h h , 2 3 1 2 3 1 2 3 1 3 1 2 24 12 48 24 24 36 24 36 24 P = 387420489 h h h + 19131876 h h h + 196830 h h h 1, 2, 6 1 2 6 1 2 6 1 2 6 72 12 24 48 12 48 24 12 72 12 24 60 - 4096 h h - 12 h h h - 48 h h h - h h + h h , 2 6 1 2 6 1 2 6 1 6 1 2 12 72 12 24 48 60 24 12 48 24 P = 16777216 h h + 196608 h h h - 729 h h + 12 h h h 1, 3, 6 1 6 1 3 6 3 6 1 3 6 24 36 24 36 24 24 48 12 24 12 72 - 270 h h h - 36 h h h - h h h + h h , .... 1 3 6 1 3 6 1 3 6 1 3 These last two are interderivable with the (ever amazing) eta transformation formula that effectively takes P_a,b,c <-> P_a,ac/b,c. (The fancier modular eta transformations turn, e.g., P_1,2,3 into seriously weird (and algebraically independent) powers of q^pi^2 times e^(i pi^3) times q^(i pi ln q), a "prodigal square" (quadrigal?).) Similarly, P_1,3,9 could be derived from P_1,2,3 (= P_3,6,9) and P_1,3,6 via a resultant eliminating h_6. Thus, in principal, one need only tabulate P_1,2,p(rime). Perhaps by examining enough P_a,b,a+b, one could guess an addition formula relating eta(q), eta(p), and eta(pq). This optimism fades as the table grows: 4 12 48 12 12 40 20 12 32 P = 68719476736 h h h + 12884901888 h h h + 855638016 h h h 1, 3, 4 1 3 4 1 3 4 1 3 4 28 12 24 48 16 12 36 16 + 23068672 h h h - 6198727824 h h - 306110016 h h h 1 3 4 3 4 1 3 4 24 24 16 36 12 16 48 16 8 48 8 - 3149280 h h h + 196800 h h h - 16 h h - 387420489 h h h 1 3 4 1 3 4 1 4 1 3 4 20 36 8 32 24 8 44 12 8 56 8 52 12 - 19131876 h h h - 196830 h h h + 12 h h h - h h + h h , 1 3 4 1 3 4 1 3 4 1 4 1 3 96 108 6 36 5 288 6 P = 2 3 eta (q) eta (q ) eta (q ) 1, 5, 6 90 100 30 36 5 264 6 + 7 2 3 eta (q) eta (q ) eta (q ) + two hundred forty one similar terms 288 18 24 294 12 24 300 6 24 294 36 + 9 h h h - 6 h h h - h h h + h h . 1 5 6 1 5 6 1 5 6 1 5 I've had no luck reaching P_1,x,y, 1<x<y, y = 13, 17, or 19. (Or perhaps *not* reaching them is luck.) But notice how nice are P_1,2,4 and P_1,3,9. An alternative spanning scheme would be P_1,n,n^2, so, let's try n=6: 312 168 336 792 P = 6 h h h - 20323 * 324949 * 9624311 1, 6, 36 1 6 36 216 1008 72 * 23381814648630788600514603407190631043 h h h 1 6 36 plus 878 similar terms. Maple claims it's irreducible. Macsyma (compiled for Windows NT!) boggles. A few hundred Taylor terms are zero, but it is difficult to explore even the foothills of such a mountain. In the immortal words of Professor Doctor Bartolomeo Simpson: Eta my shorts. --rwg

1 0

RE: [math-fun] Prime Generating Polynomials
by dasimov＠earthlink.net 26 Jun '06

26 Jun '06

Rich wrote: << More sophisticated challenge: Find a formula whose prime likelihood is something different from Constant * 1/logN. . . . >> Is it known whether there is a polynomial of degree >= 2 whose asymptotic proportion of primes at integer arguments is the same as for the polynomial P(x) = x ? Also: If negative primes count just as positive primes do, then could using only positive integer arguments give a different result from using only negative integer arguments ? --Dan

2 1

[math-fun] Wanted: an _inefficient_ number representation
by Henry Baker 26 Jun '06

26 Jun '06

A "unary" representation of a natural number n is 1 "1" 2 "11" 3 "111" etc. A "positional" representation of a natural number to base b is d_0+d_1*b+d_2*b^2+...+d_n*b^n where 0<=d_i<b. The length of a unary representation of n is O(n), while the length of a positional representation of n is O(log(n)). Are there representations of n that grow as O(sqrt(n)) or O(cbrt(n)) ?

4 4

[math-fun] Universal ZipfHuffs
by Steve Witham 26 Jun '06

26 Jun '06

>From: Henry Baker <hbaker1(a)pipeline.com> > >Is there a better encoding of Zipf alphabets such that the encoding of >the symbol of relative probability 1/i is _independent_ of the alphabet >size and the encoding tends towards 100% efficiency asymptotically? Henry and others have shown a couple codes that meet this requirement. >From: franktaw(a)netscape.net > >I'm not sure exactly you define efficiency, You divide the entropy by the, er, weighted bits per symbol of the code. If P(s) is the probability of symbol s, then the entropy (in bits) of symbol s is -log2(P(s)), and the entropy for the whole alphabet is the sum of -log2( P(s) ) * P( s ) over the whole alphabet. If the code uses bits( s ) to encode symbol s, then the weighted bits per symbol for the alphabet is the sum of bits( s ) * P( s ) over the whole alphabet. The efficiency of the code is the entropy divided by the average bits per symbol. (Henry, that is the way you're calculating it, right?) > but I'm pretty sure that >this is impossible. If the first k values use half the available code >space, as n goes to infinity this half of the code space will be used >for values with asymptotically zero (O(1/log(n)) of the probability >distribution. I don't see how this can be anything but inefficient. I wanted to point out where this intuition went wrong. The code must be inefficient, but the inefficiency can approach zero for larger and larger alphabets, as a ratio of the size of the code word to what it would ideally be. "Half of the code space" is the misleading idea. Half of the code space means all the words that start with (say) a one bit. So, if half the code space is wasted, that means that there is one extra bit on every word. If only we could waste just half the code space! In fact as you use larger and larger alphabets, more and more code space is wasted on small numbers with less and less probability. But wasted bits are just the log of the wasted space. For the efficiency to approach 100%, the wasted bits just have to grow more slowly than the ideal size of the word. That's true if the they grow like log2( size of the word ), which is like log2( log2( s ) ). This is true of a couple codes that have been discussed here. A code where this property is easy to see encodes each number by: b zero bits, where b is the number of bits in the number of bits in s b bits encoding n = number of bits in s n bits encoding s So, 0 => 0 1 0 (not used for Zipf distributions) 1 => 0 1 1 2 => 00 10 10 3 => 00 10 11 4 => 00 11 100 256 => 0000 1001 100000000 65535 => 00000 10000 1111111111111111 2^32 - 1 => 000000 100000 11111111111111111111111111111111 This code is awful, but (e.g.) the efficiency for a 32 bit number is at worst 32 / ( 6 + 6 + 32 ) = 73%. You can see that the first two columns grow like the log of the size of the third column, so this meets Henry's requirement. For a kinda large number, take the bits on my hard disk as representing a single integer. 80 GB = 80 x 2^33 bits < 2^40 bits, so this would be represented by 40 zero bits, 40 size bits, and ~80 x 2^33 data bits. 80 wasted bits in 80 GB of data, 99.9999999884% efficiency. My whole disk packed efficiently into 1/2^80, one millionth of one millionth of one millionth of one millionth of the code space. --Steve

2 1

[math-fun] No Egyptian fractions equal in Huffman encoding of Zipf ??
by Henry Baker 24 Jun '06

24 Jun '06

In my implementation of Huffman encoding, I put in a special check for equality & asked the program to print out any time an equality was found. The program never printed out anything when checking Zipf distributions from 2 to 10,000. Conjecture: When encoding a Zipf distribution using Huffman, equality never occurs. This means that we never have the case that a fraction that comes up in the Huffman encoding has two completely different decompositions into Egyptian fractions. (This Huffman encoding sorts n numbers 1/i into ascending order, then adds the two smallest, inserts that sum back into the list in order, and again adds the smallest two numbers, etc. The end result is a singleton list with the n-th harmonic number, but apparently none of the intermediate lists ever have duplicates.)

1 0

Re: [math-fun] Chinese Mathematicians Prove Poincare Conjecture
by dasimov＠earthlink.net 23 Jun '06

23 Jun '06

<< Gary McGuire writes: dasimov(a)earthlink.net wrote: << P.S. I did not see this in the Xinhua press release, but the Asian Journal of Mathematics says (in the link provided by Ray) that the article in question finishes the proof of the Thurston Geometrization Conjecture (of which the Poincare conjecture is just one of many important consequences). Up to now, a few media (Scientific American in 1994, New York Times in the past year) have claimed the Poincare conjecture has been proved, although no respectable professional journal has reported any such thing (only comments like "time will tell.") And not even media outlets have reported that the Geometrization conjecture was proved. >> On the Arxiv there is a 192 page preprint http://arxiv.org/PS_cache/math/pdf/0605/0605667.pdf which claims that the Geometrization conjecture _is_ proved. >> A claim is one thing. The imprimatur of one or more eminent mathematicians is another. --Dan

1 0

Re: [math-fun] Re: More ZipfHuffing
by Henry Baker 22 Jun '06

22 Jun '06

[I subsequently ran some tests using Fibonacci to encode the length ("exponent"?) of the number, and straight binary (without the initial "1") for the actual value. Thus, the length is approx log2(n)+log2(log2(n))/log2(phi). This "combination" encoding is ever so slightly worse than ternary encoding, but finally passes ternary somewhere around 2^23. At 2^1000, ternary is about 20% worse than the combination code, and the combination code gets arbitrarily close to optimum. The combination code isn't as good as straight Fibonacci until 2^18, where the combination code passes Fibonacci for good. This combination Fib+Binary code is thus a pretty practical code, but which also retains its efficiency for arbitrarily large symbol sets.] I ran some tests on Fibonacci/Zeckendorf v. ternary (w/optimization) encoding on Zipf distributions of n symbols: Coding efficiency n Fib Tern Sept 2^1 39.4% 30.6% 18.4% 2^2 64.0% 50.4% 35.8% 2^3 78.0% 67.2% 49.5% 2^4 86.0% 75.5% 58.4% 2^5 90.6% 82.6% 67.0% 2^6 92.7% 86.9% 73.4% 2^7 93.8% 89.6% 77.3% 2^8 94.2% 92.0% 81.7% 2^9 94.2% 93.0% 84.5% 2^10 94.0% 93.9% 86.6% 2^11 93.5% 94.7% 89.1% 2^12 93.1% 94.8% 90.3% 2^13 92.6% 95.1% 91.6% 2^14 92.1% 95.2% 93.3% 2^15 91.5% 95.1% 93.8% 2^16 91.0% 95.2% 94.6% 2^17 90.5% 95.1% 95.6% 2^18 90.0% 94.9% 95.9% 2^19 89.6% 94.9% 96.5% 2^20 89.1% 94.6% 97.0% For large n, Fibonacci encoding takes approx log2(n)/log2(phi) bits, while for large n, ternary encoding takes approx log2(n)/log2(sqrt(3)), and sept encoding takes approx log2(n)/log2(root(3,7)) bits. Since phi=1.47..., sqrt(3)=1.73..., and root(3,7)=1.913, ternary encoding will eventually beat Fibonacci encoding, and sept encoding will eventually beat ternary encoding. However, as you pointed out, for large enough n, they will all eventually have arbitrarily small efficiencies. There are some codes that grow as log2(n)+log2(log2(n))+log2(log2(log2(n)))+..., which do not lose efficiency as n becomes larger. At 11:22 AM 6/21/2006, franktaw(a)netscape.net wrote: >You can improve this using Fibonacci (or Zeckendorf) encoding - every string ends in 11. So we have: > >1 11 2 bits >2 011 3 bits >3 0011 4 bits >4 1011 4 bits >5 00011 5 bits >6 10011 5 bits >7 01011 5 bits >8 000011 6 bits >etc. > >Note, by the way, that changing the radix as the number of symbols increases is *not* using the same encoding regardless of the number of symbols. > >Franklin T. Adams-Watters > >-----Original Message----- >From: Henry Baker <hbaker1(a)pipeline.com> > >Franklin, Steve, David, et al: > >After a little thinking, I reinvented ternary encoding (or arbitrary radix >encoding for radices 2^k-1). The idea is similar to normal decimal notation, >except that we use a radix of 3 or 7 or 15 or ... The reason for not using >binary encoding is that we have to encode a "comma" or something to delimit >the end of the integer, so we use up one of the "digits" for this purpose. >The larger the radix, the smaller the coding loss. > >Here are ternary encodings for small integers: > >1 1_ (4 bits, 2 bits per character) >2 2_ 4 bits >3 10_ 6 bits >4 11_ 6 bits >5 12_ 6 bits >6 20_ 6 bits >7 21_ 6 bits >8 22_ 6 bits >9 100_ 8 bits >... > >Actually, since the first digit is always 1 or 2, we can subtract 1 bit from the >(ternary) encoding without any loss. The calculation below did not make this >optimization. > >For a Zipf alphabet of 2^20 symbols, this ternary encoding scheme gets an >efficiency of 88.4%. For a Zipf alphabet of 2^20 symbols, a radix-7 >(septary?) scheme gets an efficiency of 97%. > >Once again, the smoothness of the Zipf distribution allows us to ignore some of >the inefficiencies for the first few symbols. > >At 02:48 PM 6/20/2006, franktaw(a)netscape.net wrote: >>I'm not sure exactly you define efficiency, but I'm pretty sure that >this is >impossible. If the first k values use half the available code space, as n goes >to infinity this half of the code space will be used for values with >asymptotically zero (O(1/log(n)) of the probability distribution. I don't see >how this can be anything but inefficient. > >>Franklin T. Adams-Watters >> >>-----Original Message----- >>From: Henry Baker <hbaker1(a)pipeline.com> >> >>Is there a better encoding of Zipf alphabets such that the encoding of >>the symbol of relative probability 1/i is _independent_ of the alphabet >>size and the encoding tends towards 100% efficiency asymptotically?

1 0

[math-fun] Re: More ZipfHuffing
by Henry Baker 22 Jun '06

22 Jun '06

While Huffman encoding does extremely well on Zipf distributions, with the efficiency increasing towards 100% as the size symbol set increases, the problem is that the encoding is particular to the size of the symbol set. David Eppstein proposed the use of an encoding which is independent of the number of symbols -- i.e., the encoding of the symbol of relative frequency 1/i (non-normalized) is encoded in 2*il(i)-1 bits -- e.g., the symbol of relative frequence (r.f.) 1/1 is encoded in 1 bit, that of r.f. 1/2 is encoded in 3 bits, that of r.f. 1/3 is encoded in 3 bits. Here, "il(i)" means "integer-length(i)", the function in Common Lisp that counts the number of bits in the base-2 representation of i. This Eppstein encoding thus always has an _odd_ number of bits, and is thus not the highest efficiency encoding. This Eppstein encoding is pretty good, in that from 2 to 15 symbols, the efficiency increases from 55% to 89%. However, from 16 symbols and higher, the efficiency continues to drop, albeit very slowly. Thus, for 2^20 symbols the efficiency drops below 70% to 69.6%, which is slightly below that for a straightforward block encoding of 20 bits per symbol. Asymptotically, this encoding appears to tend to 50% -- i.e., twice as many bits as should be necessary. Is there a better encoding of Zipf alphabets such that the encoding of the symbol of relative probability 1/i is _independent_ of the alphabet size and the encoding tends towards 100% efficiency asymptotically?

2 4

[math-fun] Schroedinger's daughter
by Cordwell, William R 22 Jun '06

22 Jun '06

OK, I thought that I understood this, but here's a variation: A friend writes a girl's name on a piece of paper and puts it (unopened) in your pocket. A random parent of two children comes up to you and says, "I have a daughter named Mary." At this point, the probability that Mary's sibling is a girl is 1/3 (I think). However, if you look at the piece of paper, and it says "Mary", the probability changes to 1/2 (approximately). Is this correct? Bill C.

3 3

Re: [math-fun] Schroedinger's daughter
by David Gale 21 Jun '06

21 Jun '06

The following clarified for me both the case of Mary and Bartholomew. There are two ways to pick a girl from a population of two child families. 1. Pick a family at random. If it contains a girl the odds are two to one that she has a brother. 2. Pick a girl at random. Then the odds are even that she has a brother, (because there are (roughly) the same number of girls with brothers as there are girls with sisters). Or is this is the classical rather than the quantum case. dg PS. Are there really twice as many boy-girl families as girl-girl or boy-boy? It shouldn't be too hard to check. Maybe certain couples are biologically more likely to produce one sex over the other. At 03:30 PM 6/20/2006, you wrote: >OK, I thought that I understood this, but here's a variation: > >A friend writes a girl's name on a piece of paper and puts it (unopened) >in your pocket. A random parent of two children comes up to you and says, >"I have a daughter named Mary." At this point, the probability that >Mary's sibling is a girl is 1/3 (I think). However, if you look at the >piece of paper, and it says "Mary", the probability changes to 1/2 >(approximately). > >Is this correct? > >Bill C. >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2