July 2012 - mathfun@mailman.xmission.com

[math-fun] Wechsler disk problem
by Warren Smith 21 Jul '12

21 Jul '12

> From: Allan Wechsler <acwacw(a)gmail.com> > Either find a circular disk that covers > these lattice points and no others, or prove that no such disk exists. > > Here is the set. I am abbreviating (x,y) to the two-digit code xy. > > 01 02 03 04 11 12 13 14 20 21 22 23 24 25 31 32 33 34 35 42 43 44. --Given a set of points P and another Q in the plane, the question of whether a disk D exists with P inside D but Q outside D, is a linear programming problem, for each point xy we demand a*x*x+b*x*y+a*y*y+c*x+d*y+e > 0 (or <0) and the linear programming will determine whether suitable (a,b,c,d,e) exist. Indeed by replacing the >0 by ">s" and the <0 by "< -s" and maximizing s, you can make the linear program find the "best" such circular disk (if any exist). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 2

[math-fun] Logicians: Theory of continued fractions?
by Henry Baker 21 Jul '12

21 Jul '12

Pressburger arithmetic deals with the theory of addition, more or less, and is decidable. My recent fiddling with gcd reminded me that adding "inversion" (1/x) to addition is strictly less powerful than adding multiplication. Notice that simply adding inversion doesn't give you division (y/x), because that would require multiplication (y*(1/x)). Has anyone studied Pressburger plus inversion? Just off-hand, I would guess that it is still decidable, and perhaps not increase the complexity all that much.

4 3

[math-fun] Disk polyomino puzzle
by Allan Wechsler 20 Jul '12

20 Jul '12

It's difficult to enumerate disk polyominoes, because it's hard to recognize them. To illustrate this, I present a modest puzzle. I will give a set of lattice points. Either find a circular disk that covers these lattice points and no others, or prove that no such disk exists. Here is the set. I am abbreviating (x,y) to the two-digit code xy. 01 02 03 04 11 12 13 14 20 21 22 23 24 25 31 32 33 34 35 42 43 44.

2 3

[math-fun] Average of a few integers
by Warren Smith 20 Jul '12

20 Jul '12

If you compute the average of two unsigned integers via mean = (x+y)/2 then you could lose because of integer overflow on a machine with bounded word size. However (in C language &=AND, ^=XOR) mean = (a&b)+(a^b)/2 will do the computation without overflow and without any IF-test. Rounds result downward to nearest integer if mean is fractional like 1.5. If you have 4 unsigned integers a,b,c,d then you can compute their average via x = (a&b)+((a^b)/2; //mean(a,b) rounded down y = (c|d)-((c^d)/2); //mean(c,d) rounded up (in C language |=OR) mean = (x&y)+((x^y)/2; which works IF you are willing to accept answer perhaps being as much as 0.75 too low and 0.25 too high. If you add 1 to a before starting (and hope this does not overflow!) then these error bounds are shifted to [-0.5, +0.5]. Now for a harder problem: what about the average of 3 unsigned integers? It's quite difficult to do this optimally. IF-tests and division and overflow all are undesirable. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] bzip compression; Move2Front algorithm
by Henry Baker 20 Jul '12

20 Jul '12

Thanks, Victor, for the reference & link to the paper. I looked through it, and Elias also ignores the Belady OPT "paging" algorithm. But it is forgivable for Elias -- he comes from a probability & coding background where the forwards and backwards sequences from a source won't be distinguishable using their probability distributions. But for Bentley, et al, who are computer scientists, they know that running a program backwards is very different from running it forwards, and probably taught Belady's OPT algorithm in their classes! Basically, I'm trying to build a "unified theory" for a computer's instruction set, which would incorporate both the register set (and/or stack) and the LRU cache, which shows that a "stack-like" architecture is optimal, at least as far as instruction encoding compactness is concerned. To the extent that moving items out of (cache) memory to the top of the stack is a form of "recency rank" encoding, such a stack machine is already performing a "move2front" compression algorithm. See this paper for some of my earlier thoughts on this problem, which maps a version of Lisp onto a Forth/Postscript stack machine interpreter. http://home.pipeline.com/~hbaker1/LinearLisp.html At 06:17 AM 7/20/2012, Victor Miller wrote: >Peter Elias gives a nice analysis of these schemes in >http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.9361 . > >Victor > >On Wed, Jul 18, 2012 at 12:15 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> I just saw a video lecture on data compression and it claimed that Bentley, et al's >> compression scheme in CACM 29,4 (April 1986),320-330, is used in current bzip (bzip2 ?). >> >> Basically, Bentley's scheme assumes that both the sender & receiver keep an >> ordered list (hopefully the same list!) and when a symbol is found on the list, >> the _index_ into the list is sent, and both parties move that symbol to the front >> of the list. If the symbol is not on the list, then "n+1" is sent, indicating >> that a new element is coming just after the index, and both sides then increase >> the size of their lists to n+1. >> >> If the file to be compressed has "locality of reference", then Bentley's scheme >> can do better than any static probability scheme -- e.g., Huffman coding. >> >> It's bizarre, but Bentley doesn't mention the relationship between his algorithm >> and Belady's OPT optimal page replacement algorithm (used in Knuth's TeX, for >> example, for "paging" character font info). Traditionally, Belady's OPT algorithm >> isn't used, because it basically does LRU on the _reversed_ reference string, so >> as to kick out the page to be used the furthest into the future. Only in certain >> restricted cases (e.g., multi-pass analysis on media files) can OPT be used, because >> the future isn't normally known in advance. >> >> The takeaway from Belady's algorithm & paper (as I recall) is that (forwards) LRU >> can do no worse than half as good as Belady OPT (backwards LRU) with twice the memory >> of Belady. >> >> But file compression would seem to be oblivious to the direction of processing, >> so whether the file is processed forwards or backwards shouldn't matter very much; >> if it does, do both & output the better result. >> >> I realize that it's been 25 years since Bentley published this paper, so _somebody_ >> must have noticed this similarity, especially because in the interim, the operating >> systems guys have stored _compressed_ page reference traces for later analysis. >> >> If Bentley & Belady are right, then any bzip-compressed reference traces are >> _already_ compressed if they've been through an LRU (i.e., "stack") page-replacement >> algorithm!

1 0

[math-fun] Vector puzzle (solutions)
by Warren Smith 20 Jul '12

20 Jul '12

My solution to my continuum version of the Vector Puzzle originally posed here by Dan Asimov (and tracing back to Michael Brand at an IBM website) is -- along with the old solutions to the discrete versions of the puzzle, cleaned up a bit by me as editor -- here: http://rangevoting.org/PuzzMBrand.html ...hope you like/accept it. This is really quite an amazing puzzle, so it is too bad its impact seems to be so insignificant. (Or: Are there applications?) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] bzip compression; Move2Front algorithm
by Henry Baker 20 Jul '12

20 Jul '12

I just saw a video lecture on data compression and it claimed that Bentley, et al's compression scheme in CACM 29,4 (April 1986),320-330, is used in current bzip (bzip2 ?). Basically, Bentley's scheme assumes that both the sender & receiver keep an ordered list (hopefully the same list!) and when a symbol is found on the list, the _index_ into the list is sent, and both parties move that symbol to the front of the list. If the symbol is not on the list, then "n+1" is sent, indicating that a new element is coming just after the index, and both sides then increase the size of their lists to n+1. If the file to be compressed has "locality of reference", then Bentley's scheme can do better than any static probability scheme -- e.g., Huffman coding. It's bizarre, but Bentley doesn't mention the relationship between his algorithm and Belady's OPT optimal page replacement algorithm (used in Knuth's TeX, for example, for "paging" character font info). Traditionally, Belady's OPT algorithm isn't used, because it basically does LRU on the _reversed_ reference string, so as to kick out the page to be used the furthest into the future. Only in certain restricted cases (e.g., multi-pass analysis on media files) can OPT be used, because the future isn't normally known in advance. The takeaway from Belady's algorithm & paper (as I recall) is that (forwards) LRU can do no worse than half as good as Belady OPT (backwards LRU) with twice the memory of Belady. But file compression would seem to be oblivious to the direction of processing, so whether the file is processed forwards or backwards shouldn't matter very much; if it does, do both & output the better result. I realize that it's been 25 years since Bentley published this paper, so _somebody_ must have noticed this similarity, especially because in the interim, the operating systems guys have stored _compressed_ page reference traces for later analysis. If Bentley & Belady are right, then any bzip-compressed reference traces are _already_ compressed if they've been through an LRU (i.e., "stack") page-replacement algorithm!

2 1

[math-fun] generalization of quaternion identity to (2^n)ons
by Warren Smith 19 Jul '12

19 Jul '12

In a paper of mine you can read here paper #73 at http://rangevoting.org/WarrenSmithPages/homepage/works.html I explain the "right" way to keep the sequence reals (1D), complex numbers (2D), quaternions (4D), octonions (8D)... going forever. [The "Cayley Dickson algebras" are not the right way, although are much better known than the 2^n-ons due to the way history went.] Anyway, my "2^n"ons stop being commutative at 4, stop being associative at 8, stop being distributive at 16, lose generic ability to divide and get unique answer at 32, etc But they keep many nice properties forever, such as having an identity element 1 and always being distributive on one side, let's say the right: a*(b+c)=ab+ac. Furthermore, they are distributive on the left provided either a, or both b and c, are "niners" meaning their last 2^n-9 coordinates all are 0. THEOREM (Inspired by RC Schroeppel): If a,b,c,... are each 2^n-ons which all happen to be niners, and there are min(2^n, 9) or more letters in all, then sum(all even perms of the letters) (((a*b)*c)*d)*... = same sum using odd perms. PROOF: By right-distributive and niner-left-distributive laws it suffices to prove it in the case where each letter is one of the min(2^n, 9) basis elements. (Reducing to finite set of cases.) (i) If at least one letter is 1, then since 1 associates, commutes, and distributes with everything we can move the 1 wherever we want, in particular swapping it with the letter cyclically to its left which is an odd perm, without changing anything. (ii) If at least two letters are same basis element, then we can swap those 2 letters (an odd perm) without changing anything. By pigeonhole principle at least one of cases (i) or (ii) must apply. Either way the identity is valid. QED WARNING: I have not checked this, I only proved it :). Unlike in my paper, where practically everything was checked by computer. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] quaternion determinant identity explained (really very general phenomenon)
by Warren Smith 19 Jul '12

19 Jul '12

RC Schroeppel: The quaternion matrix "determinant" for 4x4 matrix with all 4 rows = (a,b,c,d) and all letters quaternions, is 0. Fred Lunnon: argues this is true due to row operations enabling reduction to real# times form where a=1, b=i, c=j, d=k. WDS: to complete that argument, first of all, we would need to know that a row-op (e.g. adding a row to another) leaves the "determinant" unaltered. But det( ab 00 ) = 0 while det( ab ab ) = ab-ba is in general NOT zero for quaternions, so Lunnon's row-op-based demonstration is not legitimate. ---- So what is really going on here? Due to the distributive law (valid for quaternions) and the fact reals commute with everything, it would suffice to show the identity is valid when a,b,c,d are selected from the basis set {1,i,j,k} only, which is 4^4=256 cases to check. You could check that by brute force, but there is a better way. Since any two distinct among {i,j,k} anticommute, but everything commutes with itself and 1, it is possible to see the 256 cases work in your head without actually checking any of them. Essentially: in the commuting cases, it works. In the anticommuting cases, the terms T in question yield T = -T, which works exactly when T=0, which happens because of symmetry: with 4 letters abcd, each from {1,i,j,k}, by the pigeonhole principle it is necessary that either at least two must be identical or at least one must be 1. This pigeonhole observation also means you can always perform one well-chosen single interchange (an odd perm) without changing the result, and then all the other terms on the left side of the equation arise from the same orbit as on the right side. QED (that was really 2 distinct proofs, so I should add a second QED). This also shows that you can use any number>=4 of quaternion letters -- Schroeppel was using 4, but 5, 6,... also work. Note 2 and 3 do NOT work. Now let me generalize that: THEOREM: Let N>=1. Let each letter a,b,c,... be an NxN matrix with real (or complex) entries. Then: Sum of all multilinear monomials made of N*N distinct letters using odd-permutations only = same sum using even-perms only. (Each monomial term has degree=N*N. The total number of letters in the alphabet must be at least N*N otherwise we get the trivial 0=0 identity.) PROOF: Suffices to prove where each letter is a basis matrix (e.g. single entry 1 with rest 0... also the identity matrix is a basis matrix and we agree to get rid of 1 extra arbitrary basal). By pigeonhole principle >=two matrices must be same or >=one must be identity matrix which commutes with everything. Either way for them we can do an interchange which converts each term on left side into equal term on right making it obvious left=right. QED Similarly, even though I have not checked this at all, essentially the same argument I just made, should also show that sum of even-perm-based monomials (abcdefgh) = sum of odd-perm-based monomials (abcdefgh) where each letter is an octonion and where all monomials are parenthesized in all possible binary-tree manners. (You need to specify parenthesizations since octonion-mult is non-associative so ab*c and a*bc unequal.)

1 0

Re: [math-fun] bzip compression; Move2Front algorithm
by Steve Witham 19 Jul '12

19 Jul '12

>From: Henry Baker <hbaker1(a)pipeline.com> > >I just saw a video lecture on data compression and it claimed that >Bentley, et al's >compression scheme in CACM 29,4 (April 1986),320-330, is used in >current bzip (bzip2 ?). Yes. It is an LRU scheme. It's used as *part of* the bzip2 scheme. The main part is called the Burrows-Wheeler Transform (BWT). >Basically, Bentley's scheme assumes that both the sender & receiver keep an >ordered list (hopefully the same list!) and when a symbol is found >on the list, >the _index_ into the list is sent, and both parties move that symbol >to the front >of the list. If the symbol is not on the list, then "n+1" is sent, indicating >that a new element is coming just after the index, and both sides >then increase >the size of their lists to n+1. Or you start the list full of all the possibilities. In bzip2's case, 257. >If the file to be compressed has "locality of reference", then >Bentley's scheme >can do better than any static probability scheme -- e.g., Huffman coding. ...when combined with a combination of run-length and Huffman coding of the list indexes. (Otherwise you're just encoding bytes as bytes.) So, the BWT does this (not quite true): Say you have a message of N bytes. Append a unique EOF character. Treat the message as a loop of N+1 bytes. Take the length-N+1 string starting at each position of the loop: N+1 strings of N+1 bytes each. Sort the list lexically. Now, take the string formed by reading down the *last* column of the sorted list. That is the BWT. The process is reversible. Encode that with the LRU trick. Encode that with run-length and Huffman codes. Or as Burrows and Wheeler say, transform the input into a form that has locality, then transform that into a skewed distribution, then use a compression method that takes advantage of the skewed distribution. >Belady's OPT optimal page replacement algorithm... > basically does LRU on the _reversed_ reference string, so >as to kick out the page to be used the furthest into the future. Not familiar with. >But file compression would seem to be oblivious to the direction of >processing, >so whether the file is processed forwards or backwards shouldn't >matter very much; >if it does, do both & output the better result. (Or do both on the BWT of the file, which isn't really time-like.) >If Bentley & Belady are right, then any bzip-compressed reference traces are >_already_ compressed if they've been through an LRU (i.e., "stack") >page-replacement >algorithm! This may be foiled by having the BWT between the two LRUs. --Steve

1 0