April 2003 - mathfun@mailman.xmission.com

[math-fun] biased to unbiased coin flips in real life
by Thomas Colthurst 16 Apr '03

16 Apr '03

So I assume you know the old problem of "convert a sequence of biased coin flips (with unknown bias) into a (not necessarily same length) sequence of unbiased coin flips". I recently learned two interesting things about this problem: it was apparently first posed (& of course solved) by Johnny von Neumann and that it is used in certain Intel chips as part of a hardware random number generator process. (See http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf for details.) While looking at this, I wondered if there was a more efficient scheme that processed more than two bits at a time. A little bit of thought revealed that there was, for example, this 4 bit code: 0000, 1111, 1100, 0011 -> output nothing 0001, 1110, 0101 -> 00 0010, 1101, 0110 -> 01 0100, 1011, 1001 -> 10 1000, 0111, 1010 -> 11 This is a win because the 2 bit code would only output 1 bit for sequences like 0001, while here we output 2 bits. In general, good codes can be obtained by mapping an n bit block with k 1's in it to an output with round_down( log_2( choose(n,k) ) ) bits, but these will only be more efficient than the two bit code for all biases when n is a power or two. The reason is that for very low or very high biases, the efficiency depends most on what you do when there is only one 0 or 1 in the input block. The two bit code will always output one bit in this circumstance, while most of the others (including those for all odd n) will sometimes output no bits. In fact, if we define the efficiency of a code as the ratio of the expected output length to the input length, then the efficiency of the 2^m block codes goes to 1 as m goes to infinity. The worst case is when p is very small (or very large); for these the efficiency is approximately p m. On the other hand, if the bias is known to be near 0.5, then odd length codes seem to be more efficient. (The length 7 code has efficiency 29/56, which is not beaten by any code of length less than 15.) I'm a little bit curious as to why Intel didn't implement a more efficient code. One guess is that they didn't know about them. Another is that the 2 bit code was good enough so as to make wasting silicon on more a complicated code not worth it. Still another possible reason is that the bias of the input coin flipper isn't exactly constant, but has (say) a small linear trend over time which is small enough to ignore over 2 bits but maybe not over longer lengths. -Thomas C

3 2

[math-fun] Parallel Universes
by Helger Lipmaa 15 Apr '03

15 Apr '03

http://www.sciam.com/article.cfm?articleID=000F1EDD-B48A-1E90-8EA5809EC5880… "In infinite space, even the most unlikely events must take place somewhere."

1 0

[math-fun] Possible proof of the Poincaré conjecture and the Geometrization conjecture
by asimovd＠aol.com 14 Apr '03

14 Apr '03

I predict that the following story will appear in the NY Times on Tuesday: --Dan ------------------------------------------------------------------------------ --------------------------------- April 15, 2003 Russian Reports He Has Solved a Celebrated Math Problem By SARA ROBINSON A Russian mathematician is reporting that he has proved the Poincaré Conjecture, one of the most famous unsolved problems in mathematics. The mathematician, Dr. Grigori Perelman of the Steklov Institute of Mathematics of the Russian Academy of Sciences in St. Petersburg, is describing his work in a series of papers, not yet completed. It will be months before the proof can be thoroughly checked. But if true, it will verify a statement about three-dimensional objects that has haunted mathematicians for nearly a century, and its consequences will reverberate through geometry and physics. If his proof is accepted for publication in a refereed research journal and survives two years of scrutiny, Dr. Perelman could be eligible for a $1 million prize sponsored by the Clay Mathematics Institute in Cambridge, Mass., for solving what the institute identifies as one of the seven most important unsolved mathematics problems of the millennium. Rumors about Dr. Perelman's work have been circulating since November, when he posted the first of his papers reporting the result on an Internet preprint server. Last week at the Massachusetts Institute of Technology, he gave his first formal lectures on his work to a packed auditorium. Dr. Perelman will give another lecture series at the State University of New York at Stony Brook starting on Monday. Dr. Perelman declined to be interviewed, saying publicity would be premature. For two months, Dr. Tomasz S. Mrowka, a mathematician at M.I.T., has been attending a seminar on Dr. Perelman's work, which relies on ideas pioneered by another mathematician, Richard Hamilton. So far, Dr. Mrowka said, every time someone brings up an issue or objection, Dr. Perelman has a clear and succinct response. "It's not certain, but we're taking it very seriously," Dr. Mrowka said. "He's obviously thought about this stuff very hard for a long time, and it will be very hard to find any mistakes." Formulated by the French mathematician Henri Poincaré in 1904, the Poincaré Conjecture is a central question in topology, the study of the geometrical properties of objects that do not change when the object is stretched, twisted or shrunk. The hollow shell of the surface of the earth is what topologists would call a two-dimensional sphere. It has the property that every lasso of string encircling it can be pulled tight to one spot. On the surface of a doughnut, by contrast, a lasso passing through the hole in the center cannot be shrunk to a point without cutting through the surface. Since the 19th century, mathematicians have known that the sphere is the only bounded two-dimensional space with this property, but what about higher dimensions? The Poincaré Conjecture makes a corresponding statement about the three-dimensional sphere, a concept that is a stretch for the nonmathematician to visualize. It says, essentially, that the three-dimensional sphere is the only bounded three-dimensional space with no holes. "The hard part is how to tell globally what a space looks like when you can only see a little piece of it at a time," said Dr. Benson Farb, a professor of mathematics at the University of Chicago. "It was pretty reasonable to think the earth was flat." That conjecture is notorious for the many "solutions" that later proved false. Indeed, Poincaré himself demonstrated that his earliest version of his conjecture was wrong. Since then, dozens of mathematicians have asserted that they had proofs until experts found fatal flaws. Although many experts say they are excited and hopeful about Dr. Perelman's effort, they also urge caution, noting that not all of the proof has been written down and that even the most reliable researchers make mistakes. That was the case in 1993 with Dr. Andrew J. Wiles, the Princeton professor whose celebrated proof for Fermat's Last Theorem turned out to have a serious gap that was repaired after months of effort by Dr. Wiles and a former student, Dr. Richard Taylor. Dr. Perelman's results go well beyond a solution to the problem at hand, as did those of Dr. Wiles. Dr. Perelman's results say he has proved a much broader conjecture about the geometry of three-dimensional spaces made in the 1970's. The Poincaré Conjecture is but a small part of that. Dr. Perelman's personal story has parallels to that of Dr. Wiles, who, without confiding in his colleagues, worked alone in his attic on Fermat's Last Theorem. Though his early work has earned him a reputation as a brilliant mathematician, Dr. Perelman spent the last eight years sequestered in Russia, not publishing. In his paper posted in November, Dr. Perelman, now in his late 30's, thanks the Courant Institute at New York University, SUNY Stony Brook and the University of California at Berkeley, because his savings from visiting positions at those institutions helped support him in Russia. His papers say that he has proved what is known as the Geometrization Conjecture, a complete characterization of the geometry of three-dimensional spaces. Since the 19th century, mathematicians have known that a type of two-dimensional space called a manifold can be given a rigid geometric structure that looks the same everywhere. Mathematicians could list all the possible shapes for two-dimensional manifolds and explain how a creature living on the surface of one can tell what kind of space he is on. In the 1950's, however, a Russian mathematician proved that the problem was impossible to resolve in four dimensions and that even for three dimensions, the question looked hopelessly complex. In the early 1970's, Dr. William P. Thurston, a professor at the University of California at Davis, conjectured that three-dimensional manifolds are composed of many homogeneous pieces that can be put together only in prescribed ways and proved that in many cases his conjecture was correct. Dr. Thurston won a Fields Medal, the highest honor in mathematics, for his work. Dr. Perelman's work, if correct, would provide the final piece of a complete description of the structure of three-dimensional manifolds and, almost as an afterthought, would resolve Poincaré's famous question. Dr. Perelman's approach uses a technique known as the Ricci flow, devised by Dr. Hamilton, who is now at Columbia University. The Ricci flow is an averaging process used to smooth out the bumps of a manifold and make it look more uniform. Dr. Hamilton uses the Ricci flow to prove the Geometrization Conjecture in some cases and outlined a general program of how it could be used to prove the Geometrization Conjecture in all cases. He ran into problems, however, coping with certain types of large lumps that tended to grow uncontrollably under the averaging process. "What Perelman has done is to figure out some new and interesting ways to tame these singularities," Dr. Mrowka said. "His work relies heavily on Hamilton's work but makes amazing new contributions to that program." If Dr. Perelman succeeds in resolving Poincaré, he will probably share the Clay Mathematics Institute Award with Dr. Hamilton, mathematicians said. Even if Dr. Perelman's work does not prove the Geometrization Conjecture, mathematicians said, it is clear that his work will make a substantial contribution to mathematics. "This is one of those happy circumstances where it's going to be fun no matter what," Dr. Mrowka said. "Either he's done it or he's made some really significant progress, and we're going to learn from it."

1 0

[math-fun] Patchy stretches of Primes
by Meeussen Wouter (bkarnd) 14 Apr '03

14 Apr '03

the denominator of the sum of the first n Harmonic numbers, [[see PS below]] equals LCM(1,2,..,n) for values of n of the form n=(p-1) , p prime. Not all primes qualify for the converse statement. Those that do (listed below by prime_index PrimePi(p) 1,2,3; 5,6,7; 10,11; 16; 24,25; 31,32,33,34,35,36; ... or as {start index of patch, length of patch} {{1, 3}, {5, 3}, {10, 2}, {16, 1}, {24, 2}, {31, 6}, {54, 5}, {62, 1}, {164, 16}, {220, 12}, {358, 10}, {446, 31}, {488, 24}, {520, 31}, {887, 10}, {910, 51}, {986, 5}, {1001, 7},... Who can explain this Patchy behaviour? PS. [[ (-n+(1+n)HarmonicNumber[n]) or -n +(1+n)(EulerGamma+PolyGamma[0,n+1]) since Mma burps on HarmonicNumber[k] with k>1000. ]] Wouter. =============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.

2 1

[math-fun] Fwd: math daily Subj-class mailing 408 1
by Michael Kleber 14 Apr '03

14 Apr '03

Since Thomas just mentioned the topic, I'll point out this paper, just posted to the arXiv: > Paper: math.PR/0304143 > From: Elchanan Mossel <mossel(a)stat.berkeley.edu> > Date: Thu, 10 Apr 2003 20:56:46 GMT (25kb) > > Title: New coins from old: computing with unknown bias > Authors: Elchanan Mossel and Yuval Peres > Comments: 3 figures, appendix by Christopher Hillar > Subj-class: Probability Theory; Combinatorics > \\ > Suppose that we are given a function f : (0,1) -> (0,1) and, for some > unknown > p in (0,1), a sequence of independent tosses of a p-coin (i.e., a coin > with > probability p of ``heads''). > For which functions f is it possible to simulate an f(p)-coin?; This > question > was raised by S. Asmussen and J. Propp. A simple simulation scheme for > the > constant function 1/2 was described by von Neumann (1951); this scheme > can be > easily implemented using a finite automaton. We prove that in general, > an > f(p)-coin can be simulated by a finite automaton for all p in (0,1), if > and > only if f is a rational function over Q. We also show that if an > f(p)-coin can > be simulated by a pushdown automaton, then f is an algebraic function > over Q; > however, pushdown automata can simulate f(p)-coins for certain > non-rational > functions such as the square root of p. These results complement the > work of > Keane and O'Brien (1994), who determined the functions $f$ for which an > f(p)-coin can be simulated when there are no computational restrictions > on the > simulation scheme. > \\ ( http://arXiv.org/abs/math/0304143 , 25kb) --Michael Kleber kleber(a)brandeis.edu

1 0

[math-fun] The Unabomber's Mathematical Locutions
by Thane Plambeck 14 Apr '03

14 Apr '03

Back in 1995 I remember reading a copy of the Unabomber Manifesto over lunch in a bar in Princeton, New Jersey. It had been just been published in the New York Times. He hadn't been caught yet, but was about to be. I remember thinking as I read it, you know, this guy uses a lot of mathematical turns of phrases. I even told the bartender my guess that the Unabomber was a mathematician, or maybe a physicist. A few weeks later he was arrested. I went into the same bar and the bartender remembered my prediction. He gave me a free lunch. Anyway here's a couple of chunks from the Manifesto. There are others... * * * In the past, human nature has been approximately constant, or at any rate has varied only within certain bounds... * * * * Throughout this article we've made imprecise statements and statements that ought to have had all sorts of qualifications and reservations attached to them; and some of our statements may be flatly false. Lack of sufficient information and the need for brevity made it impossible for us to fomulate our assertions more precisely or add all the necessary qualifications. And of course in a discussion of this kind one must rely heavily on intuitive judgment, and that can sometimes be wrong. So we don't claim that this article expresses more than a crude approximation to the truth... Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

3 3

[math-fun] Mass Destruction
by Henry Baker 12 Apr '03

12 Apr '03

Is it just me, or does anyone else think that "Weapons of Mass Destruction" is a pun on E=mc^2 ? Of course, if I learned physics right, the mass isn't really "destroyed", but converted into energy. And even the resulting energy still exerts the same gravitational force. And E=mc^2 works even for chemical weapons, and, indeed, for bows & arrows. So, the phrase "mass destruction" is ultimately a hollow phrase -- a distinction without a difference.

1 0

Re: [math-fun] mathematical criminals
by asimovd＠aol.com 12 Apr '03

12 Apr '03

Fred writes: << Dan means André Bloch, who did all of his mathematical work after being institutionalized. (Felix Bloch was a Nobel physicist.) >> Omigod. I guess I'm a Bloch-head. Thank you for the correction, and apologies to the memory of Felix Bloch. --Dan

1 0

Re: [math-fun] mathematical criminals
by asimovd＠aol.com 12 Apr '03

12 Apr '03

Thane writes: << If being a criminal means being put in jail, that casts a pretty wide net. Bertrand Russell jailed for opposing the First World War Andre Weil jailed in Finland as a spy, almost executed Galois jailed for threatening the King, (found 'not guilty' ) Fourier jailed in French Revolution >> Also Felix Bloch, most known for his work in complex variables, who shot and killed three people. Can't recall whether he was put in jail or a mental institution, but I think he remained incarcerated for the rest of his life.) (Not to mention a number contemporary mathematicians who were jailed for civil disobedience protesting the Vietnam War.) --Dan --Dan

3 2

[math-fun] tic tac toe variants --- please
by Thane Plambeck 12 Apr '03

12 Apr '03

Martin Gardner (I think) once suggested playing tic tac toe by instead having the two players choose integers from the set 1,2,3,4,5,6,7,8,9, the first player to obtain a sum of fifteen winning. The magic square 2 9 4 7 5 3 6 1 8 then proves useful. My question: does anyone know a way to make tic-tac-toe, or something like it, into an interesting game? My sons, 5 and 7, are always wanting to play it and I'm suffering. I'm too strong at dots and boxes to play them with enjoyment. Here's a problem for an idle moment: How many essentially different "cat" positions (ie, fully played-out draws) are there in tic-tac-toe with best play, if we regard two as the same under a rotation or reflection of the board? Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

5 5