September 2007 - mathfun@mailman.xmission.com

[math-fun] Puzzle about coloring chess boards
by victor＠idaccr.org 19 Sep '07

19 Sep '07

The following puzzle had been knocking around work (actually it was first given in our place in 1994): Given an n x n chessboard we wish to color the squares black and white with the property that for any subsquare (of size at least 2x2) the four corner squares are not all the same color. These are orthogonal squares (and not tilted ones). The original poser of the puzzle gave a number of 5x5 examples, and asked to either prove that it can be done for all n, or to show that it can't be done for some (and therefore all bigger) n0. I coded up this problem as a satisfiability problem and found a solution for 14x14, but, after 1 1/2 hours of computation the SAT solver (SatEliteGTI) reported that 15x15 is unsatisfiable. Has anyone else seen this puzzle? It would be much more satisfying if there were a proof that 15x15 was impossible by hand. Victor

4 4

[math-fun] Factoring "15" with a Quantum Computer: Quantum Threat to Our Secret Data
by Henry Baker 19 Sep '07

19 Sep '07

FYI -- Only a few more bits to go... Quantum Threat to Our Secret Data New Scientist (09/13/07) Vol. 195, No. 2621, P. 30; Graham-Rowe, Duncan Quantum computing's ability to decrypt the codes that safeguard banking, e-commerce, and business data has taken a step closer to realization with the development of quantum computers that can run Shor's algorithm by two research groups working independently. RSA is an example of a highly common encryption system that can be defeated by Shor's algorithm. RSA involves a widely distributed public key for encrypting messages and a secret private key for decrypting them, and the trick to solving the private key is to work out the large prime numbers that produce the key when they are multiplied together. Shor's algorithm dramatically reduces the time it takes to find the prime factors by searching for telltale patterns in remainders when a key is divided by a prime factor, but quantum computation is essential for performing the massive number of calculations that the algorithm requires to be successful. The first quantum implementation of Shor's algorithm involved the manipulation of nuclear spin, while the more recent experiments--one led by Andrew White at Australia's University of Queensland and the other by Chao-Yang Lu of the University of Science and Technology of China--used quantum photonic computers. Photon pairs were produced with femtosecond lasers and passed through polarizing bismuth borate crystals to generate entangled qubits, which were coaxed by optical devices to run Shor's algorithm to factor the number 15 into its prime components. IT security specialist Bruce Schneier calls the development of techniques to run the algorithm using standard lab optics a significant achievement that could spell trouble for encryption down the road. White contends that cryptography would need to be fundamentally rethought if quantum calculations for much larger numbers could be carried out. "There are paths to a fully scalable quantum computer," he notes.

1 0

[math-fun] Want to be a computer scientist? Forget maths
by Henry Baker 14 Sep '07

14 Sep '07

FYI -- http://www.itwire.com.au/content/view/13339/53/ Want to be a computer scientist? Forget maths Contributed by Stuart Corner Thursday, 05 July 2007 A new book seeks to demolish the concept that computer science is rooted in mathematics and, in particular that the notion of the algorithm is fundamental to computer science. In particular, he says the notion of the algorithm, "has been largely ineffective as a paradigm for computer science." Fant argues that, because mathematicians, notably John Von Neumann and Alan Turing, were intimately involved with the early development of digital electronic computers in the 1940s they transplanted a mathematical model of computation, including the algorithm - commonly understood to be an exact prescription, defining a computational process, leading from various initial data to the desired result - into the fledgling science of computers. He claims that "What is essentially a discipline of pure mathematics has come to be called "the theory of computer science," and "the notion of the algorithm has been decreed to be a fundamental paradigm of computer science". However, he says this mathematical perspective "is the wrong point of view" and is asking the wrong questions. "Mathematicians and computer scientists are pursuing fundamentally different aims, and the mathematician's tools are not as appropriate as was once supposed to the questions of the computer scientist. The primary questions of computer science are not of computational possibilities but of expressional possibilities. Computer science does not need a theory of computation; it needs a comprehensive theory of process expression." This concept of 'process expression' is, he says, a common thread running through the various disciplines of computer science. "A logic circuit is an expression of a logical process; an architecture is an expression of a continuously acting process to interpret symbolically expressed processes; a program is a symbolic expression of a process; a programming language is an environment within which to create symbolic process expression; a compiler is an expression of a process that translates between symbolic process expressions in different languages; an operating system is an expression of a process that manages the interpretation of other process expressions; any application is an expression of the application process." And, he argues, important process expressions do not qualify as algorithms. "A logic circuit is not a sequence of operations. An operating system is not supposed to terminate, nor does it yield a singular solution. An operating system cannot be deterministic because it must relate to uncoordinated inputs from the outside world. Any program utilising random input to carry out its process, such...is not an algorithm." "The notion of the algorithm," he concludes "simply does not provide conceptual enlightenment for the questions that most computer scientists are concerned with." Fant is the founder and CEO of Theseus Research, a consulting firm specialising in the design and implementation of real-time image processing systems as well as ongoing research into the theory of computers. "Computer Science Reconsidered: The Invocation Model of Process Expression" is published by John Wiley. http://www.itwire.com Powered by Joomla! Generated: 9 September, 2007, 08:55

5 4

[math-fun] World's Largest Crossword puzzle (91,000 squares)
by Henry Baker 14 Sep '07

14 Sep '07

FYI -- perhaps someone here can come up with the world's largest sudoku ? http://www.gizmag.com/go/5594/

2 3

[math-fun] how to write consistently boring scientific literature
by Thane Plambeck 12 Sep '07

12 Sep '07

http://static.scribd.com/docs/dxmaczcxro62n.pdf -- Thane Plambeck tplambeck(a)gmail.com http://www.plambeck.org/ehome.htm

1 0

[math-fun] Re: Re: pi-3, 1/pi
by Bill Gosper 12 Sep '07

12 Sep '07

>I said >>[...]which will obey nonlinear, three term relations among pi(q), pi(q^a), and pi(q^b), for rational a and b. (Actually, we want Pi(q):=pi(q)/(1-q^2), which changes q^(6k^2) to q^(6(k^2-1/24)) in our series.) >E.g., 2 2 2 Pi (q) Pi (q ) 4 = ------------- - -------, 2 4 2 4 Pi(q ) Pi(q ) Pi (q ) 9 2 3 9 9 3 Pi(q) Pi(q ) + Pi (q ) = sqrt(Pi(q) Pi(q )) (3 Pi(q ) + Pi(q)), . . . >which Gene pointed out (in the 70s) give quadratic and cubic methods for pi >computation. I.e., you solve the first one, say, for Pi(q), and substitute sqrt(q) for q. Then choose an initial q (say 2^-4) for which Pi(q) and Pi(q^2) are very easy to evaluate, and use the recurrence to get Pi(sqrt q), Pi(sqrt(sqrt q)), Pi(q^(1/8)),..., Pi(q^2^-n). But this leads to a nice PUZZLE (or at least trick question): q^2^-n converges to 1 linearly with n: (2.d0^-4)^2^-9 = 0.99459942348363d0, and pi(q^2^-n) converges linearly to pi: 2 theta (0, q) theta (0, q) (1 - q ) 2 3 pi(q) = ---------------------------------- 2 subst(%th(2),q,%) pi(0.99459942348363d0) = 3.12464151346649d0 So how can we claim this is a quadratic method? --rwg Answer: Under the Jacobi imaginary transformation, 2 2 %pi %pi ------ ------ log(q) log(q) 2 %pi theta (0, %e ) theta (0, %e ) (1 - q ) 3 4 pi(q) = ----------------------------------------------------, 1 2 log(-) q so it is the quantity -n 2 n 2 n 1 2 %pi 2 %pi 2 2 log(-) pi(q ) ------- ------- q log(q) log(q) ---------------- = %pi theta (0, %e ) theta (0, %e ) 2 3 4 -- n n 2 2 (1 - q ) that converges quadratically, not pi(q^2^-n). (And thus requires a valuation of log q to get pi.) --------------------------------- Catch up on fall's hot new shows on Yahoo! TV. Watch previews, get listings, and more!

1 0

[math-fun] Re: Mobile math lab for cell phones
by Steve Witham 10 Sep '07

10 Sep '07

>From: Henry Baker <hbaker1(a)pipeline.com> > >FYI -- I haven't gotten these programs to work yet on my phone, but >perhaps someone else can. Neither have I. >http://media.haifa.ac.il/index.php?option=com_content&task=view&id=2458&Ite… My problem is that my phone is a Treo, e.g. a Palm, and getting "midlets" to run on Palms is a problem if your computer doesn't run Windows. Although there used to be a platform-neutral way over this hurdle called Converter.jar, and I found a copy, the converted file doesn't know it should run with my Java runtime. There is a windows-specific converter that comes with the Java runtime I downloaded from Palm; I will try that on my roommate's computer. There is an older (2001) runtime, coeval with Converter.jar, that I should probably try also. I'll let y'all know which if any of these ideas work. In the mean time if anyone knows a modern, official, and especially non-Windows solution to this midlet-to-Palm problem, I'd appreciate a clue. --Steve

1 0

[math-fun] Re: pi-3, 1/pi
by Bill Gosper 10 Sep '07

10 Sep '07

I said >Now I can apply the exact same process to Heine's series instead of Gauss's and get a q-extension [of Ramanujan's dyadic 1/pi = pFq[1/64]]. Here it is cleaned up. 2 2k+1 3 6k+1 6k+1 6k+3 3 6 k (q + 1) (1 - q ) q (1 - q ) [ 2 k ] inf q (------------------------ - -----------------) ([ ]) ==== 2 2 [ k ] \ 1 - q 1 - q q > -------------------------------------------------------------- / 6 3 ==== (- q; q) (- q; q) k = 0 k 2 k + 1 2 2 (q; q ) 1/4 inf q = -------------------- = ---- 2 pi 2 2 2 q (q ; q ) (1 - q ) inf where the (q; q) [ 2 k ] 2 k ([ ]) :=--------- [ k ] q 2 (q; q) k are the central q-binomial coefficients, and are polynomials in q: k qbin(2k,k) 0 1 1 q + 1 2 2 2 (q + 1) (q + q + 1) 2 2 4 3 2 3 (q + 1) (q + 1) (q - q + 1) (q + q + q + q + 1) 2 4 4 3 2 4 (q - q + 1) (q + 1) (q + q + q + q + 1) 6 5 4 3 2 (q + q + q + q + q + q + 1) 2 2 4 4 3 2 5 (q + 1) (q - q + 1) (q + q + 1) (q + 1) (q - q + q - q + 1) 6 3 6 5 4 3 2 (q + q + 1) (q + q + q + q + q + q + 1) 2 4 4 2 4 3 2 6 3 6 (q + 1) (q + 1) (q - q + 1) (q - q + q - q + 1) (q + q + 1) 6 5 4 3 2 (q + q + q + q + q + q + 1) 10 9 8 7 6 5 4 3 2 (q + q + q + q + q + q + q + q + q + q + 1) It's interesting where the 12k+4 powers of 2 come from. One from the 1-q^2 in the "numerator", 6k and 6k+3 from the q-pochhammers in the denominator. I said >[...]which will obey nonlinear, three term relations among pi(q), pi(q^a), and pi(q^b), for rational a and b. (Actually, we want Pi(q):=pi(q)/(1-q^2), which changes q^(6k^2) to q^(6(k^2-1/24)) in our series.) E.g., 2 2 2 Pi (q) Pi (q ) 4 = ------------- - -------, 2 4 2 4 Pi(q ) Pi(q ) Pi (q ) 9 2 3 9 9 3 Pi(q) Pi(q ) + Pi (q ) = sqrt(Pi(q) Pi(q )) (3 Pi(q ) + Pi(q)), . . . which Gene pointed out (in the 70s) give quadratic and cubic methods for pi computation. --rwg --------------------------------- Looking for a deal? Find great prices on flights and hotels with Yahoo! FareChase.

1 0

Re: [math-fun] Want to be a computer scientist? Forget maths
by Henry Baker 09 Sep '07

09 Sep '07

In some ways computers are more fun today -- we have plenty of computational power & memory to do things we never dreamed of being able to do in our lifetimes, and this power is cheap enough that we can do it in the privacy of our own homes without having to write grant proposals. So _something_ is working. What isn't fun anymore is doing research in or teaching CS. Very few institutions or research agencies are interested in fundamental problems -- they want you to work on making this seriously ugly chip or program 3% faster/cheaper. I think that Neal Koblitz's article addresses this issue a bit when he talks about the tremendous pressure to publish the largest number of "smallest publishable units", rather than waiting to put together a longer paper together which really addresses a problem in depth. Knuth is an anachronism -- he's a Victorian thinker (akin to Darwin or Hamilton or Maxwell) in the 21st century. He writes no paper or book "before its time". Which is why most of us on this group love him so much. When Microsoft killed all innovation in the PC, interesting people moved to innovating media players and cellphones. When cellphone services (Verizon/Sprint/Vodaphone) began crippling cellphones due to marketing brain damage, interesting people moved to distributed systems ("motes", etc.) and robotics. The commercial software business (e.g., "mainframe") has become so deadeningly boring that to a first approximation, there are no interesting people left in this field at all (at least in the US). My father worked for Ford Motor Company in the 1950's in the Edsel division (don't laugh). At least they were trying to do some sort of innovation, no matter how brain-damaged. By the end of the 1960's, Fortune Magazine wrote an article about how "A" & "B" students from good engineering schools didn't "fit in" very well at Ford, and that was OK by Ford. We know how the Japanese subsequently kicked Detroit's butt due to this attitude. It's probably time to come up with a new name for a new field. At MIT, the Media Lab tried to escape from the boredom of CS by moving down the street & working on new applications. Regardless of what you think about the Media Lab, they were at least trying to innovate. Fields become old well before they run out of problems, and usually well before many interesting problems are solved. One of the problems of the "linear era" in Electrical Engineering was the synthesis problem: how to synthesize a given linear system with passive components. This problem was never solved by mathematics at all, but by the invention of the "operational amplifier". And of course "delta-sigma" A/D's & D/A's (don't ask: http://en.wikipedia.org/wiki/Sigma-delta_modulation) & DSP's have completely replaced "op amps". When I entered MIT in the 1960's, no one in their right mind would go into electrical power engineering. Compared with computers, old-fashioned generators & motors were passe. Now, due to the interest in "green", people are once again becoming interested in power engineering. But this is _fifty_ years later! Perhaps Planck was right about more than physics when he said (approximately), "Physics progresses funeral by funeral". At least in a new field, there aren't tenured faculty around to constantly say "we worked on that problem 20/30/40 years ago", so the fun of inventing something "new" is still there. ---- From Rich: Neal Koblitz's article in the Notices, The Uneasy Relationship Between Mathematics and Cryptography is available, apparently free, at http://www.ams.org/notices/200708/tx070800972p.pdf I disagree with Neal on a number of points, but the article does discuss several interesting issues. ---- At 08:52 AM 9/9/2007, Thane Plambeck wrote: >Anyway: at the Stanford Computer Science Dept 40 year anniversary >event last year, they had a panel discussion about the direction of >computer science. Someone in the audience suggested that computer >science needs more students, but that a growing perception that CS >majors end up in dead-end programming jobs was working against that. > >Response from a panelist: CS is not about programming, it's about >ideas and creativity. > >Response by questioner: Perhaps, but still, aren't students right >that if you don't want to end up being a programmer, why choose CS? >People get boring jobs writing programs to APIs defined by >others---it's just a kind of primitive scripting and argument-passing >job. It makes for a boring career. > >I don't remember where it went from there, but I remember thinking, >"well, that questioner is on to something...". There was a bit of a >pall hanging over the room at that moment. > >Then, Don Knuth got up from the audience, and said something to the >effect of "It was suggested that Computer Science graduates are often >writing programs to interfaces, and that's not fun, and I think that >person is right...." [caveat --- this is not a quotation, but I >pretty sure that's the spirit of what he said, and I welcome >correction.]. "So," he went on, "how can we make it fun again? It's >not as much fun as it used to be." [ quote approximate caveat, again] > >I don't remember anyone giving a good answer to that

1 0

[math-fun] Wanted: examples of potentially 'unbalanced' parallelisable computational tasks
by Guy Haworth 09 Sep '07

09 Sep '07

A colleague is looking for examples of sizeable computational tasks which can be parallelized, but where the size of the parallel tasks are not the same and may not be easily sizead beforehand. The idea is that decisions about splitting tasks will be taken at runtime on the basis of whatever information becomes available. Contributions welcomed via my email address at www.tinyurl.com/law6k Thank you - Guy

2 1