Skip to content

April Fool

April 1, 2015


Non-jokes on April Fool’s Day

nunspriest
Nun’s Priest’s Tale source

Faadosly Polir is the older brother of Lofa Polir. You may recall he invented new ways to apply powerful mathematical techniques to prove trivial theorems, and she once claimed a great result on integer factoring. We have heard from both since, but they haven’t given us any new April Fool’s Day material, mainly because they weren’t fooling to begin with.

Today Ken and I wished to help you enjoy April Fool’s day.

We usually try to have fun on this day, but this year we have no idea that seems to be funny. We considered fooling that some university had created a faculty line for a computer mathematician. We’ve considered making light of some recent data on theory and rankings, but it’s high noon of hiring season hence serious. Chess cheating jokes?—no, Ken has been dealing with more cases at once than ever before. Even our recent shout-out to co-pilots has been overcome by events beyond our ability to give other than condolences. Nor were we able to create a phony result to celebrate this day—because good phony results still require much research effort. We thought about re-running an old April Fool discussion, as something easy while lots of other stuff is happening. But we are committed to give you, our readers, your money’s worth. So we rejected the re-run idea.

April Fool’s Day itself may have begun because of a typographical error. Reading between the lines of Wikipedia’s account, Geoffrey Chaucer may have intended to write “Since March be gone, thirty days and two” in order to place the events of “The Nun’s Priest’s Tale” on the May 2 anniversary of a royal engagement. The text in surviving copies of his Canterbury Tales reads, however, “Since March began, thirty days and two”—placing on April 1 the action in which the proud rooster Chanticleer is tricked by a fox.

So…

So since we ran out of ideas we decided to give up on April fooling and list results that sound like April Fool jokes, but are actually true. We hope this is still fun, interesting, and informative.


{\bullet } Smale’s Paradox:

Stephen Smale proved in 1958 that there is a regular homotopy between the standard immersion {f: S^2 \rightarrow \mathbb{R}^3} of the sphere in 3-space and {-f}, which represents the sphere being turned inside-out. He proved this indirectly, by showing that there was only one homotopy class for a category that includes {f} and {-f}, by virtue of both causing the corresponding homotopy group in the Stiefel manifold to vanish. When faced with this particular example, Smale’s graduate adviser, Raoul Bott, retorted that the result was “obviously wrong.” The resulting eversion of the sphere—a process of turning it inside out differentiably continuously (allowing self-intersection but not creasing)—was first visualized concretely by Arthur Shapiro in consultation with others including Bernard Morin, who has been blind since childhood. An animation is included in Vladimir Bulatov’s gallery of geometrical VRML movies.


{\bullet } Nikodym Set:

A Nikodym set, named for Otto Nikodym who powerfully extended a theorem by Johan Radon in measure theory, is a set {N} of points in the unit square such that:

  • For every point {x \in N}, there is a straight line that goes through no other point in {N} but {x}, and yet:

  • The Lebesgue measure of {N} is {1}.

This is not like the Banach-Tarski paradox involving tricks with non-measurable sets: everything works nicely according to Hoyle or at least according to Henri Lebesgue.


{\bullet} Needle Sets:

A needle embedded in a circular disk of diameter 1 can be rotated continuously and snugly by 180 degrees within the disk. The same needle can also be inverted by rotating it inside a deltoid curve whose three points poke somewhat outside the circle but has smaller overall area. How small can a shape allowing the needle to rotate be? Soichi Kakeya raised the question and Abram Besicovitch answered it by showing that its Lebesgue measure can be as close to zero as desired. Moreover, if we only require that the needle can be placed pointing in any direction, without the continuous rotation, the measure can be zero. Then it supplements the Nikodym set. Zeev Dvir has written a nice survey connecting conjectured properties of analogous sets in higher dimensions to constructions over finite fields that relate to randomness extractors.


{\bullet } Potato Paradox:

Let’s move from topology and measure to simple counting. Suppose we have a 100-pound sack of hydrated potatoes that is 99% water. We let the sack dry out until it is 98% water. How much does it weigh now? The answer surprisingly is not {100 \times 98 / 99} but rather {50}. The simplest of various reasonings given here is that the 1% non-water of 100 pounds has stayed the same while becoming 2% of something, so that something must be 50 pounds.

SAYING-APRIL-FOOLS-DAY-CHURCHILL-300x300
April Fool’s quotes source

{\bullet} Polynomial Time is Big:

For all real numbers {a \geq 1} the complexity classes {\mathsf{DTIME}[n^a]} are all distinct owing to the Time Hierarchy Theorem: whenever {a < b} there is a language

\displaystyle  L \in \mathsf{DTIME}[n^b] \setminus \mathsf{DTIME}[n^a].

Moreover the classes nest, so {\mathsf{DTIME}[n^a] \subset \mathsf{DTIME}[n^b]}. Since there are uncountably many real numbers {b}, this seems to suggest there must be uncountably many languages {L = L_b} involved. But {\mathsf{P}} contains only countably many languages.

What is the answer? The answer is that over a hundred years before people defined complexity classes we had this kind of ‘paradox’ just in the number line. Define {\mathsf{D}[a]} to be the set of rational numbers between {1} and {a}. There are only countably many rational numbers, and yet {\mathsf{D}[a] \subset \mathsf{D}[b]} whenever {a < b}.


{\bullet} Probabilistic Polynomial Time Goes Hyper:

For any real number {0 < a < 1} we can also define {\mathsf{PP}_a} to be the class of languages {L} such that for some relation {R(x,y)} decidable in time polynomial in {n = |x|},

\displaystyle  x \in L \iff \Pr_y [R(x,y)] > a,

where {y} ranges over {\{0,1\}^{p(n)}} for some polynomial {p}. The standard complexity class {\mathsf{PP}} uses {a = 1/2}. It is not difficult to show that for any rational {a}, indeed any {a} for which the first {n} decimal places in binary {a_1\cdots a_n} are computable in {\mathsf{poly}(n)} time, {\mathsf{PP}_a = \mathsf{PP}}. However, when {a} is uncomputable, {\mathsf{PP}_a} contains undecidable languages. Indeed, take {R(x,y)} to be simply the relation {y \leq x}, take {p(n) = n}, and take {L_a} to be the “standard right cut” of {a}:

\displaystyle  L_a = \{x: x \geq a_1\cdots a_{|x|}\}.

Then {L_a \in \mathsf{PP}_a}, but {L_a} is undecidable. The paradox is, why should the complexity class {\mathsf{PP}_a} stay equal to the nice class {\mathsf{PP}} on a dense subset of {a} and yet suddenly jump up in power to include “hyper-computable” languages when {a} infinitesimally passes through an uncomputable value?


From math and complexity we go on to physics.


{\bullet } Mpemba Effect:

Erasto Mpemba of Tanzania, while a secondary school student in 1963, observed that ice cream mixes froze faster when they had been initially heated, compared to mixes that had been kept in cold storage before freezing. This effect is still under debate even at the level of basic controlled evidence. This must be the simplest natural physical phenomenon for which the human race, despite splitting the atom and finding the Higgs Boson, has been unable to devise a convincing closed-form experiment, let alone verify. Even subjective matters such as whether tea tastes different depending on whether milk or the tea has been added to the cup first have been verified by rigorous experiments.


{\bullet} Table-top Dark Energy:

This compact device enables extracting the ubiquitous tension energy of space in order to power homes in regions with too frequent cloud-cover for reliable solar energy. It departs from previously patented approaches based on the Casimir effect and improves a previous design for a room-temperature power device in 1989 by Martin Fleischmann and Stanley Pons. “This is after all almost 70% of the entire mass-energy content of the Universe, so we should be able to harness it,” said a spokesperson. Indeed according to equations of physics the device should have about {10^{120}} times the yield of a standard home gas furnace, and it was no surprise when Faadosly and Lofa told us they’d spent their year investing in it.

Open Problems

Have a fun and safe April Fool’s Day.

Is It New?

March 24, 2015


How to tell algorithms apart

egdaylightSummerPic

Edgar Daylight was trained both as a computer scientist and as a historian. He writes a historical blog themed for his near-namesake Edsger Dijkstra, titled, “Dijkstra’s Rallying Cry for Generalization.” He is a co-author with Don Knuth of the 2014 book: Algorithmic Barriers Failing: P=NP?, which consists of a series of interviews of Knuth, extending their first book in 2013.

Today I wish to talk about this book, focusing on one aspect.
Read more…

Leprechauns Will Find You

March 17, 2015

And perhaps even find your hidden prime factors

 

leprechaun_256

Neil L. is a Leprechaun. He has visited me every St. Patrick’s Day since I began the blog in 2009. In fact he visited me every St. Patrick’s Day before then, but I never talked about him. Sometimes he comes after midnight the night before, or falls asleep on my sofa waiting for me to rise. But this time there was no sign of him as I came back from a long day of teaching and meetings and went out again for errands.

Today Ken and I wish you all a Happy St. Patrick’s Day, and I am glad to report that Neil did find me.
Read more…

The Other Pi Day

March 14, 2015


It’s 3/14/15, do you know how much your Π costs?

pi-tag-usa-artikel-410
source

Larry Shaw apparently created the concept of Pi Day in 1988. He was then a physicist who worked at the San Francisco Exploratorium. He and his colleagues initially celebrated by marching around in circles, and then eating pies—that is fruit pies. As Homer Simpson would say: hmm.

Today Ken and I want to add to some of the fun of Pi Day, and come back to a different Pi that has occupied us.
Read more…

Lint For Math

March 8, 2015


Can we remove simple errors from math proofs?

825-SteveJohnson
simple-talk interview source

Stephen Johnson is one of the world’s top programmers. Top programmers are inherently lazy: they prefer to build tools rather than write code. This led Steve to create some of great software tools that made UNIX so powerful, especially in the “early days.” These included the parser generator named Yacc for “Yet Another Compiler Compiler.”
Read more…

News on Intermediate Problems

March 5, 2015


The Minimum Circuit Size Problem goes front and center

EricDasRyanCody

Eric Allender, Bireswar Das, Cody Murray, and Ryan Williams have proved new results about problems in the range between {\mathsf{P}} and {\mathsf{NP}}-complete. According to the wide majority view of complexity the range is vast, but it is populated by scant few natural computational problems. Only Factoring, Discrete Logarithm, Graph Isomorphism (GI), and the Minimum Circuit Size Problem (MCSP) regularly get prominent mention. There are related problems like group isomorphism and others in subjects such as lattice-based cryptosystems. We covered many of them some years back.

Today we are delighted to report recent progress on these problems.
Read more…

The Right Stuff of Emptiness

February 23, 2015


How ∅ versus {ε} can be a life-and-death difference

SkilesCockpit
Cropped from source

Jeff Skiles was the co-pilot on US Airways Flight 1549 from New York’s LaGuardia Airport headed for Charlotte on January 15, 2009. The Airbus A320 lost power in both engines after striking birds at altitude about 850 meters and famously ditched in the Hudson River with no loss of life. As Skiles’s website relates, he had manual charge of the takeoff but upon his losing his instrument panel when the engines failed,

“Captain Chesley Sullenberger took over flying the plane and tipped the nose down to retain airspeed.”

Skiles helped contact nearby airports for emergency landing permission but within 60 seconds Sullenberger and he determined that the Hudson was the only option. His front page does not say he did anything else.

Today we tell some stories about the technical content of forms of emptiness.
Read more…

Follow

Get every new post delivered to your Inbox.

Join 2,413 other followers