January 2005 - mathfun@mailman.xmission.com

[math-fun] Permanents
by Richard Schroeppel 14 Jan '05

14 Jan '05

I've found a couple of other Permanent formulas, which are probably well known (to those who know them). Our 19th century colleagues were especially good at this stuff. In the complex number construction, instead of selecting the elements of the random vector from the unit circle, one can select 50:50 from +-1, and the construction still works. This leads to a non-random formula, simply by going through all combinations of +-1 in the "random" vector. The first element can be forced to +1 without harm. This gives an (N-1) * 2^(N-1) multiplications method; the +-1 combinations can be traversed in gray-code to limit the amount of addition work required for computing the column-sums. This could also be the basis for a more standard QCmp approach using random bits: The +-1s could be fabulated in the usual 50:50 fashion, and the product computed using "ordinary quantum gates". The difficult part is estimating the expected value of the product. Another easy algorithm uses 0,1 in the random vector instead of +-1, but the product terms are signed +-1, depending on an even/odd number of 0s in the "random" vector. In this case the terms are simply added (or subtracted) to get the permanent. Example: Perm [ A B ] [ C D ] = (A+C)(B+D) - AB - CD + 0*0 = AD + BC Another way to look at the permanent: If the random vector is symbolic, (x y z ...), then the coefficient of the all-linear term in the product, xyz..., is the permanent. In the N=2 example, (Ax+Cy) (Bx + Dy) = AB x^2 + (AD+BC) xy + CD y^2. Of course it works the same with rows instead of columns. The minimum necessary for using permanents to solve NP problems is to distinguish (with accuracy > 50%) between a permanent value of 0 and a specific known non-zero value (something like 4^N * N!). If the matrix entries are non-negative numbers this is an easy problem. Unfortunately the insteresting problems involve (small) negative numbers. Dan will note that +-1 is just the 0-dim case of the unit circle, and wonder what happens if we step out to quaternions etc. Beyond noting that commutativity needs to be addressed, deponent sayeth not. Rich rcs(a)cs.arizona.edu

1 0

RE: [math-fun] Permanents
by Daniel Asimov 13 Jan '05

13 Jan '05

Rich writes: << Here's a theoretical way to compute the permanent of an nxn matrix M: Choose a random vector Z of n elements. Each entry is an independent randomly chosen complex number on the unit circle, |Z_k|=1. Compute V = ZM, giving another vector of complex numbers. (The typical entry is unlikely to be on the unit circle.) Multiply together all the complex numbers in V, and divide by the product of the complex numbers in Z. In rough symbols, compute product(elements of V) ------------------------------ = result P, another complex number. product(elements of Z) Then the expected value of P is the permanent of M. (I'm assuming the entries of Z are chosen uniformly.) >> This method is using random sampling to calculate the expected value of P, but this expected value could also be calculated directly, using integration over T^n (where T^n is the nth cartesian power of the unit circle in the complex plane). So the expectation should be (1/2pi)^n * integral over Z in T^n of (prod(ZM)/prod(Z)) dVol. Since T^n can be opened up to become [0,2pi]^n, and prod(exp(i ang_1),...,exp(i ang_n)) = exp(i (ang_1+...+ang_n)), this integration might not be so hard to perform directly without approximation. --Dan

1 0

[math-fun] Pancake cutting problem
by lkmitch＠att.net 13 Jan '05

13 Jan '05

Previously, I wrote: >>> I was looking at the "pancake cutting" problem on MathWorld (more precisely, the problem of circle division by lines): and its cousin, the problem of the plane divided by circles, and I'm wondering if there are "nice" ways to draw the images for larger numbers of cuts. I realize that "nice" is horribly ill-defined, but I'm thinking of images that are aesthetically appealing, as well as mathematically accurate. Or, if anyone has any hints to offer about drawing my own, I'd be oh so appreciative.<<< After playing with it for a while, I came up with a technique based on regular polygons that looks fairly nice. I'm sure someone has thought of this before, but it's new to me. The attached image shows the pancake numbers (numbers of regions) for 5 and 10 cuts. Kerry lkmitch(a)att.net www.fractalus.com/kerry

1 0

[math-fun] Simple(?) Fib problem
by David Wilson 13 Jan '05

13 Jan '05

For which m for do the Fibs have every residue mod m?

4 3

Re: [math-fun] Permanents
by Mike Stay 13 Jan '05

13 Jan '05

Rich wrote: > Multiply together all the complex > numbers in V, and divide by the product of the complex > numbers in Z. ... > But the operation of choosing random > elements on the unit circle suggests that it might be a > good algorithm for quantum computing. It'll be hard to compute the product of the phases on a quantum computer, since if you could do that (and have a decent probability of measuring the resulting phase in comparison to a known phase), you could solve NP-complete problems. Create an equal superposition of solutions in some subset of the problem domain and let all the phases be 1. Then negate the phase of the component that satisfies the circuit. By computing the product of the phases, you can know whether the solution exists or not in that subset of the domain. Binary search for the solution. -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

1 0

[math-fun] Permanents
by Richard Schroeppel 13 Jan '05

13 Jan '05

The Permanent is a function of a square matrix, a polynomial in the matrix elements. It's like the determinant, with N! terms, except that all the signs are +. [ A B ] Perm [ C D ] = AD+BC, while Det = AD-BC. It seems to be much harder to compute the permanent than the determinant. Some elementary row operations, like rowA += rowB, which preserve determinants, do not preserve permanents. These are what make the determinant easier to calculate. Permanents aren't nearly as useful as determinants, but they crop up in complexity theory. In particular, computing permanents can answer questions like "How many solutions are there to make this boolean formula true?" I have an "Is this known?" question for the group: Here's a theoretical way to compute the permanent of an NxN matrix M: Choose a random vector Z of N elements. Each entry is an independent randomly chosen complex number on the unit circle, |Zk|=1. Compute V = ZM, giving another vector of complex numbers. (The typical entry is unlikely to be on the unit circle.) Multiply together all the complex numbers in V, and divide by the product of the complex numbers in Z. In rough symbols, compute product(elements of V) ---------------------- = result P, another complex number. product(elements of Z) Then the expected value of P is the permanent of M. (I'm assuming the entries of Z are chosen uniformly.) [Is this already known?] This isn't a very practical way to compute permanents -- it bears a lot of similarity to Buffon's Needle method of computing pi. But the operation of choosing random elements on the unit circle suggests that it might be a good algorithm for quantum computing. Rich rcs(a)cs.arizona.edu

1 0

[math-fun] Maple LLL?
by R. William Gosper 13 Jan '05

13 Jan '05

Doc shows lattice([[1,2,3],[-1,0,1],[0,1,1]]); [[-1, 0, 1], [0, 1, 1], [0, -1, 1]] but then lattice([[-1,0,1],[0,1,1],[1,2,3]]); [[-1, 0, 1], [0, 1, 1], [1, -1, 0]] Why not some permutation of the first result? For less trivial lattices, the consequences of permuting the vectors become large, so that some of the shortest vectors are missing from most of the answers. E.g., looking for close products of small primes, I found 2 3 3 11 41 67 71 79 36100763589 31 41 59 79 20621900011 ----------------- = ----------- and --------------- = -----------, 3 36100763591 2 3 20621900013 19 23 31 47 59 3 11 13 37 73 but nothing this good when I reversed the list of vectors. Is this a bug in Maple, or a property of LLL? --rwg

1 0

[math-fun] puzzle
by David Wilson 12 Jan '05

12 Jan '05

Score card wise, how many different possible games of ten pins are there?

1 0

[math-fun] What is 3.1464466?
by N. J. A. Sloane 11 Jan '05

11 Jan '05

The following message gives an alternative value for Pi, 3.1464466. Does any one know what this constant is? Google didn't recognize it. NJAS > From: "Jain ( Mathemagics )" <jain(a)jainmathemagics.com> > Subject: JAIN, of Australia, World Tour 2005. South East Queensland, Australia Tour in Feburary. > Date: Tue, 11 Jan 2005 18:48:17 +1100 > > Dear Friends, > > Due to the popularity of my American Tour last year in 2004, I have been > invited again to teach in many destinations. I am sending you this email > for several reasons: > > ... > Day 1 Feb 5, Sat VEDIC MATHEMATICS FOR THE NEW MILLENNIUM: > > How to complete complex mathematics... in your head! Without a > calculator. > Rapid Mental Calculation. Increases Confidence and Memory Skills. > ... > > Day 5 PI: (Date To Be Announced). (Optional) > > The Western value of Pi 3.1415926 is wrong and disharmonic! > Discover the True and Exact Value of Indian Pi ( A ) which is 3.1464466. > > Highly controversial issue that will rewrite all the books. > > Experience 'Jain Magic' "Sacred Geometry", > with a spectacular 2-hour INTRODUCTORY PRESENTATION > on all the above topics! > ...

4 3

Re: [math-fun] Learning computer programming for a bright 13-year old?
by Phil Carmody 10 Jan '05

10 Jan '05

While I'm replying I'll deviate back to the original question and suggest JavaScript. It's got pretty much all the theoretical purity of languages like LISP or even ML; it's a close syntactic relative of the more mainstream C/C++/Java, so a useful familiariser for those; and to top it off, it typically sits inside a framework (a browser) where all input/output/display issues already neatly handled. To the mathematician in me, JavaScript, when programmed well, is a very satisfying language. (But 99% of all real-world use of it would get this message negatively moderated ;-) ) From: "R. William Gosper" <rwg(a)osots.com> > I said > > For a certain concrete thinker, I'm > > planning the following first program: Combine Macsyma's string > > manipulation functions, especially CARDINAL_STRING (12 -> "twelve") and > > ORDINAL_STRING (12 -> "twelfth") to make a FRACTION_STRING function > > (11/12 -> "eleven twelfths"). There are nice opportunities for bugs > > ("one twelfths", 1/2 -> "one second", 3 -> "three firsts") > > This went great!! After he got those fixed and was sure it all worked, > 3/2 -> "three halfs" and after the obvious fix, "three halvess". > He *really* enjoyed that session. > > Richard Fateman added > >You might be surprised to learn that speaking fractions is > ambiguous. > > 30/400 and 34/100 are quite different numbers, but > each can be pronounced > > thirty four hundredths > > Luckily, we dodged that one. It probably can't happen with reduced > fractions anyway, twenty three hundred and oneths? > but just for kicks: > block([gcd:false,fancy_display:false], > for x in [34/100,30/400] do print(x=number_string(x)))$ > > 34 > --- = thirty-four one hundredths > 100 > > 30 > --- = thirty four hundredths > 400 One thing that used to drive both my (US) girlfriend and (UK) me absolutely mad was hearing sports commentators say things like "X has beaten Y by three one thousandths of a second". "Three thousandths!" we'd both shout at the idiot box simultaneously. I don't know how widespread such ire is though. I believe the additional (to me) "one" is certainly more US, but the commentator in question (Murray Walker) was as British as the day is long. The disambiguation can typically happen in the phrasing, but that's a lower-bandwidth part of the signal, alas, and more susceptible to noise. Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

11 13