\documentclass[14pt]{article}

\usepackage{epsf}
\usepackage{epsfig}
\usepackage{color}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}  
\usepackage{amssymb}    
\usepackage{amsthm}
\usepackage{wrapfig}
\usepackage{subfigure}
\usepackage{hyperref}

%\usepackage{fancyheadings}
%\pagestyle{fancy}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex}
\widowpenalty 10000

\usepackage{color}
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.9}
\newcommand{\aside}[1]{\textcolor{MyDarkBlue}{#1}}

\usepackage{enumerate}


\usepackage{lineno}
%\linenumbers

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\mybox}[1] {
\begin{center} {\small
\framebox[3in]{
\begin{minipage}[t]{4.5in} {\sf #1}
\end{minipage} } }
\end{center}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength\oddsidemargin{0in}
%\setlength{\textwidth}{6.5in}
\setlength{\textwidth}{4in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\latex{latex }
\newcommand{\header}[1]{\section*{#1}}
\newcommand{\myquote}[1]{''{#1}''}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}


{\huge What Would Be Left, If...?}

{\it Apocalypses in math and theory, plus a complexity question}
\vspace{.2in}

%% http://mat.tepper.cmu.edu/blog/?p=1703

Douglas Adams wrote the watchword for today:

\begin{quotation}
Don't Panic.
\end{quotation}

Still, his novel and series {\it The Hitchhiker's Guide to the Galaxy} begins with the impending destruction of the Earth, which goes ahead 5 minutes too soon.  The remainder is post-apocalyptic.  It is also pre-apocalyptic, because there are multiple Earths that face destruction at different times.  At least having multiple days of prophesied doom is something we've really been dealing with.

Today---the last time we can use this word?---we wish to talk about real apocalypses in mathematical and scientific theories.  And what was left afterward.

%  The History Channel created a series \href{http://en.wikipedia.org/wiki/Life_After_People}{Life After People} in 2009--2010.  There is also a book \href{http://en.wikipedia.org/wiki/The_World_Without_Us}{The World Without Us}.  Both describe how Nature would reclaim our civilization's infrastructure, and how long our artifacts and information would survive.

We have already \href{http://rjlipton.wordpress.com/2012/09/29/why-we-lose-sleep-some-nights/}{blogged} about what would happen to complexity theory if $\mathsf{P = NP}$ were true and proved.  As we said, ``Most of the 573 pages of Arora-Barak would be gone.''  Well this is still hypothetical.  Now we will look at actual cases in the past where whole theories were blown up by a surprise result.  

This is different from theories going out of fashion and dying out, even if it was from internal causes.  Likewise we don't consider the fadeouts of past civilizations to be catastrophes, only ones \href{http://en.wikipedia.org/wiki/Minoan_eruption}{destroyed} by things like volcanoes.  Ironically, the branch of mathematics called \href{http://en.wikipedia.org/wiki/Catastrophe_theory}{catastrophe theory} itself is said to be one of the fadeouts.  As mathematical historian David Aubin wrote in ``Chapter III: Catastrophes'' of his 1998 Princeton PhD \href{http://www.math.jussieu.fr/~daubin/These/chap3.pdf}{thesis}:

\begin{quotation}
Catastrophe Theory is dead.  Today very, very few scientists identify themselves as `catastrophists'; the theory has no institutional basis, department, institute, or journal totally or even partly devoted to it.  But do mathematics die?
\end{quotation}

He goes on to cite an article by Charles Fisher that proclaimed the death of Invariant Theory.  To be sure, theories like that sometimes get \href{http://gct.cs.uchicago.edu/}{revived}.  But first a word about the Mayans and ultimate catastrophe.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Baktun The Future}

All the fuss is about today's ticking over of a Mayan unit of time called a \href{http://en.wikipedia.org/wiki/Baktun}{baktun}, or more properly b'ak'tun.  It's not even a once-in-5,000-years event like everyone says, but rather once-in-144,000 days, making just over 394 years.   The point is there have been 13 of them since the inception of the Mayan creation date according to their ``Long Count'' \href{http://en.wikipedia.org/wiki/Maya_calendar#Long_Count}{calendar}, making $13 \times 394.26 = 5,125.38$ years in all.  So the 14th b'ak'tun starts today---big whoop.  The buzz comes from many Mayan inscriptions seeming to max out at 13, but others go as far as 19 and it is known that they counted by 20.  Hence the real epoch will be when the 20th and final baktun ticks over to initiate the next {\bf piktun}.   That will be on October 13, 4772.  If human civilization lasts that long, that is.

This still has us thinking, what if Earth really were suddenly blown up by \href{http://en.wikipedia.org/wiki/Vogon}{Vogons} or by \href{http://en.wikipedia.org/wiki/Contact_(novel)}{Vegans} or by a space rock a little bigger than last week's?  What would be left?  Anything?  The reason is that according to a recently-agreed principle in fundamental physical theory, the answer should be {\em everything}.  

The principle, as enunciated in all-capitals by popular science author Charles Seife in his 2007 book \href{http://www.amazon.com/Decoding-Universe-Information-Explaining-Everything/dp/0143038397}{Decoding the Universe}, states

\begin{quotation}
{\sc Information Can Neither Be Created Nor Destroyed.}
\end{quotation}

As we \href{http://rjlipton.wordpress.com/2012/03/05/the-quantum-super-pac/}{mentioned} last March, the agreement was symbolized by Stephen Hawking conceding a bet to John Preskill, who has graced these pages.  Hawking underscored the point by making it a main part of the plot of a children's \href{http://www.amazon.com/Georges-Secret-Universe-Stephen-Hawking/dp/B0068EQ3AI}{novel} written with his daughter Lucy.  The father falls into a black hole, but is resurrected by a computer able to piece back all the information because it was all recoverable.  At least in theory.

Hence even if Earth really is swallowed up later today, or if we disappear leaving all our stored information and literary artefacts to decay within a 50,000-year estimated for The History Channel's series \href{http://en.wikipedia.org/wiki/Life_After_People}{Life After People}, all the information would in principle still exist.  Is this comforting?  Perhaps not.  It could be that while all natural processes conserve information, the more violent ones might embody the computation of a \href{http://en.wikipedia.org/wiki/One-way_function}{one-way function}.  It then becomes an issue of complexity theory whether the output of that function could be reverted to its pre-apocalyptic state.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Apocalypses In Math}

Here are a few examples from mathematics of ``extinction" events: usually the extinction was of a theory or whole approach to math.

$\bullet$ {\bf Bertrand Russell and Gottlob Frege:}

Frege was just finishing his tome on logic when {\bf the} letter from Russell arrived showing that Frege's system was inconsistent. The letter basically noticed that the set
	$$ \{ x | x \not \in x \}, $$
was not well defined. This destroyed the whole book that Frege had worked so hard on for years. Frege's \href{http://www.pithypedia.com/?author=Gottlob+Frege}{quote} is:
\begin{quotation}
A scientist can hardly meet with anything more undesirable than to have the foundations give way just as the work is finished. I was put in this position by a letter from Mr. Bertrand Russell when the work was nearly through the press.
\end{quotation}
A study in being low-key as we might say today.

$\bullet$ {\bf David Hilbert and Paul Gordan:}

Gordan was known as ``the king of invariant theory." His most famous result is that the ring of invariants of binary forms of fixed degree is finitely generated. Hilbert proved his famous theorem that replaced {\bf binary} by any degree, and replacing horribly complex arguments with a beautiful existence proof. This essentially to quote \href{ http://en.wikipedia.org/wiki/Invariant_theory}{Wikipedia}:
\begin{quotation}
almost put an end to classical invariant theory for several decades, though the classical epoch in the subject continued to the final publications of Alfred Young, more than 50 years later. 
\end{quotation}
Gordan was less low key than Frege, since his comment on Hilbert's brilliant work was: ``"This is not mathematics; this is theology." Oh well.

$\bullet$ {\bf Kurt G\"odel and David Hilbert:}

Hilbert, again, wanted to create a formal foundation of all mathematics based on an axiomatic approach. He had already done this for geometry in his famous work of 1899. No Eucild did have an axiomatic system thousands of years earlier, but it was not really formal. Some proofs relied on looking at diagrams and other obvious facts, so Hilbert added extra notions that made geometry based on a complete system. For example, Hilbert added the notion of \href{http://en.wikipedia.org/wiki/Hilbert's_axioms }{betweenness} of three points: point $x$ is between $y$ and $z$.

Of course G\"odel proved his famous Incompleteness Theorem that Hilbert could not do what he did for geometry was impossible to do for number theory. 


$\bullet$ {\bf Stephen Kleene and Barkley Rosser:} Once Alonzo Church's lambda calculus and Haskell Curry's combinators were discovered in the 1930's, it seemed natural to build systems of logic around them.  That was the original intent of both Curry and Church.  It was therefore a shock when Kleene and Rosser, as students of Church, \href{http://en.wikipedia.org/wiki/Kleene-Rosser_paradox}{showed} at a stroke that they were inconsistent.  The reason is that their standard of ``unambiguous definition'' claimed too extensive a reach, as with Frege's formalization of the notion of ``set.''  It essentially allowed defining an exhaustive countable list of unambiguously-defined real numbers, for which the Cantor diagonal number was unambiguously defined within the system, a contradiction.  I (Ken) liken this paradox phenomenon to the collapse of the Tower of Babel.


$\bullet$ {\bf Riemann's Non-Conjecture Refuted:}  At the very end of his famous 1859 \href{http://www.claymath.org/millennium/Riemann_Hypothesis/1859_manuscript/EZeta.pdf}{paper} which included the Riemann Hypothesis, Bernhard Riemann made a carefully-worded statement about the relationship between the prime-counting function $\pi(x)$ and the logarithmic integrals $li(x)$ and  $Li(x) = li(x) - li(2)$:

\begin{quotation}
Indeed, in the comparison of $Li(x)$ with the number of prime numbers
less than $x$, undertaken by Gauss and Goldschmidt and carried through up
to $x =$ three million, this number has shown itself out to be, in the rst
hundred thousand, always less than $Li(x)$; in fact the difference grows, with
many fluctuations, gradually with $x$.
\end{quotation}

Further calculations were consistent with inequality holding in general, until in 1914, John Littlewood refuted this not just once, but infinitely often.  That is, he did not find a counterexample by computation, but rather proved that $li(x) - \pi(x)$ must change sign infinitely often.  In fact, the first number giving a sign flip is still unknown, though it must be below $e^{727.951346801}$.  

Although this is included on Wikipedia's short \href{http://en.wikipedia.org/wiki/List_of_disproved_mathematical_ideas}{list of disproved mathematical ideas}, it's significance is not the inequality hypothesis itself, but the fallible nature of numerical evidence.  Michael Rubinstein and Peter Sarnak \href{http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.em/1048515870}{showed} an opposite surprise: the set of integers $x$ giving a negative sign has non-vanishing density, in fact about $0.00000026$, so it is disturbing that no such $x$ is within the current range of calculation.


$\bullet$ {\bf Mertens Conjecture Refuted:}  The \href{http://en.wikipedia.org/wiki/Mertens_conjecture}{conjecture}, which was first made in 1885 by Thomas Stieltjes not Franz Mertens, states that the sum of the first $n$ values of the \href{http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/}{M\"obius function} has absolute value at most $\sqrt{n}$.  That is,
\[
M(n) = |\sum_{k=1}^n \mu(k)| \leq \sqrt{n}.
\]
Despite the fact that all computer calculations {\em still} support this, Andrew Odlyzko and Herman te Riele disproved it theoretically in 1985.  At least it has an exponentially bigger leeway than the previous one: the best known upper bound on a bad $n$ is currently
$$
e^{15,900,000,000,000,000,000,000,000,000,000,000,000,000}.
$$
Moreover the following weaker statement, which Stieltjes thought he had proved, is still open: 
$$
(\exists C > 0)(\exists n_0 > 0)(\forall n \geq n_0) M(n) \leq Cn^{\frac{1}{2}}.
$$
The reason this is portentious is that the following slight further weakening,
$$
(\forall \epsilon > 0)(\exists C > 0)(\exists n_0 > 0)(\forall n \geq n_0) M(n) \leq Cn^{\frac{1}{2} + \epsilon},
$$
is actually {\bf equivalent} to the Riemann Hypothesis.  

The failure of Riemann would have a definite apocalyptic effect: it would wipe away all the many papers that assume it.  It is not clear whether those papers could even be saved by the kind of ``relativization'' we have in complexity theory, whereby results obtained assuming $\mathsf{P \neq NP}$ and so on may still be valid relative to {\em oracle languages} $B$ such that $\mathsf{P}^B \neq \mathsf{NP}^B$.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Our Neighbors' Houses}

Still, the loss of papers assuming Riemann would be less than what would happen in physics if \href{http://en.wikipedia.org/wiki/Supersymmetry}{supersymmetry} were \href{http://www.nature.com/scientificamerican/journal/v306/n5/full/scientificamerican0512-16.html}{disproved}, as its \href{http://www.scientificamerican.com/article.cfm?id=supersymmetry-fails-test-forcing-physics-seek-new-idea}{failure} \href{http://www.redorbit.com/news/science/1112729849/physics-theory-fails-test-111212/}{could} \href{https://simonsfoundation.org/features/science-news/mathematics-and-physical-science/as-supersymmetry-fails-tests-physicists-seek-new-ideas/}{take} all of \href{http://en.wikipedia.org/wiki/String_theory}{string} \href{http://blog.vixra.org/2012/06/12/bayes-and-string-theory/}{theory} \href{http://www.realclearscience.com/blog/2012/11/string-theory-in-deep-trouble.html}{down} with it.  The Standard Model of particle physics seems also to have survived problems the absence of the Higgs Boson would have caused, although issues with the \href{http://blog.vixra.org/2012/12/20/end-of-year-higgs-roundup/}{Higgs} are still causing apocalyptic \href{http://www.math.columbia.edu/~woit/wordpress/?p=5416}{reactions} from some physicists.  

Perhaps we in computer science theory are fortunate to experience less peril.  Even so, we are left with this \href{http://en.wikiquote.org/wiki/David_Hilbert}{quotation} attributed to Hilbert by Howard Eves:

\begin{quotation}
One can measure the importance of a scientific work by the number of earlier publications rendered superfluous by it.
\end{quotation}












%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Open Problems}

Do you have other favorite examples of results in the mathematical and general sciences that caused the collapse of theories?

Does Nature compute complexity-theoretic one-way functions?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}


