\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 Do We Need Mysticism In Theory?}     % Delete More?  

%%KWR: Yes.  Also *can* change subtitle to, "Do we overdo ``slow thinking'' in approaching open problems?"

{\it Are we too ``normal'' in our approach to open problems?}


\vspace{.5in}

Boris Spassky is the oldest living world chess champion. He held the title 1969 to 1972, until famously losing to Bobby Fischer in the \href{http://en.wikipedia.org/wiki/World_Chess_Championship_1972}{Match of the Century}. The game in the US was made even more exciting by the PBS broadcast hosted by Shelby Lyman---see \href{http://thelede.blogs.nytimes.com/2008/01/18/fischers-epochal-matchshelby-lymans-star-turn/}{here}. 

Today I want to talk about the role mysticism could play in computational complexity. Seriously.

I still recall watching Lyman's show when it covered a later world championship. As he often did he had on expert guests, and on this show one of the experts was Spassky. During the analysis Shelby turned to Boris and asked, ``Boris how do you decide what move to make?'' Spassky answered immediately:
\begin{quotation}
I move the piece whose aura is the brightest.
\end{quotation}
Shelby looked at him and was speechless for a moment. As a wood-pusher I had hoped for some interesting insight into the mind of a famous grandmaster. Instead I got a joke? Or was it actually the truth? Did Spassky see auras around pieces? I have no idea. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Seriously?}

Ken helped me with our earlier \href{http://rjlipton.wordpress.com/2011/02/09/unmasking-quantum-computation/}{post} mentioning this quotation by Spassky, and inserts this section.  

I (Ken) was actually thinking in similar ``aura'' terms about how I would judge a recent position in which a master made a speculative sacrifice to open lines for his pieces.  But while on a weekend getaway to a friend's summer house on an island near Parry Sound, Ontario, I read parts of a recent \href{http://en.wikipedia.org/wiki/Thinking,_Fast_and_Slow}{book} by Daniel Kahneman, {\it Thinking, Fast and Slow}.  Kahneman is famous for his Nobel Prize-winning work with Amos Tversky on how human decision-making differs from the ``strictly rational'' modeling of expected-utility theory.  His book takes a formative approach to human thought, which he divides into two spheres:

\begin{itemize}
\item
Fast---automatic, intuitive, frequent, subconscious...
\item
Slow---logical, calculating, painstaking, conscious...
\end{itemize}

Well, I picked through the index for the dozen-plus references to chess.  Five of them are concentrated in a chapter that asks how much reliance we can place on expertise based on intuition.  Much of what we call intuition is in turn based on patterns of long experience.  Indeed---this is not in the chapter---the documentary \href{http://docuwiki.net/index.php?title=My_Brilliant_Brain}{"My Brilliant Brain}'' conveys a study showing that selecting chess moves activates the same area of the brain as used for face recognition.  Kahneman ascribes a firefighter's ability to sense unexpected danger similarly to experience.  

Is experience, then, behind Spassky's ``aura''?  Certainly pattern-matching is.  In chess I often think of a pattern, and then try to calculate whether it will work in the current position.  Jonathan Edwards, who \href{http://rjlipton.wordpress.com/2012/05/17/turings-tiger-birthday-party/}{hosted} the Princeton Turing conference in May, wrote a \href{http://www.amazon.com/Sacking-Citadel-History-Practice-Sacrifice/dp/1888690747/ref=la_B001VWWN2Y_1_3?ie=UTF8&qid=1345500878&sr=1-3}{book} on when and whether a common chess sacrifice will succeed.  By itself the sacrifice is a {\it degenerate pattern}---one needs more information to formalize it in a specific position, let alone ``prove it correct.''  My angle on what is otherwise Dick's post is that we can encourage thinking in degenerate terms because we have a safety-net of {\it proof\/}, one lacked by the social fields which Kahneman addresses.  That multiplying a function by its logarithm obeys a degenerate derivative pattern, per Dick's recent \href{http://rjlipton.wordpress.com/2012/08/17/the-right-definition/}{post}, is an example validated by proof.  Here is one yet waiting.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{An Example From Mathematics}

We think of math as one of the most rational fields of thought. Results are not based on appeal to authority, nor to your own visions, they are not based on instincts, nor on wild guesses. A theorem is the rock on mathematics, and 
no measure of belief in theorems matters in the final analysis except proof.  A proof, while subject to human errors, is an argument that should be reproducible by others. It is a gold standard of correctness that makes math special.

Yet there is a place in math, believe it or not, for auras, for beliefs with no proof, and for a kind of Mysticism. I (Dick) would like to try to explain one example: {\it The quest for a field with one element}. I hasten to add that like many mystical beliefs it is hard to explain; it is hard to completely understand, but I will try.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Fields}

Before I talk about mysticism and math let me remind all of what a field $F$ is in mathematics. A field is a set that has two operations defined on its elements: addition ``$+$'' and multiplication ``$\times$''. These operations satisfy all the usual rules of algebra that you learned in grade school. For example,
	$$ (x + y \times z) \times x = x^{2} + x \times y \times z. $$
The most common examples of fields are the rational numbers, the real numbers, the complex numbers, and finite fields. 

In non-grade-school terms, a field forms an Abelian group under addition, its {\it nonzero} elements form an Abelian group under multiplication, and the two are connected by the distributive law.  What distinguishes a {\it field} from a lesser system called a {\it ring} is that there is a multiplicative inverse of every non-zero element: if $x \neq 0$, then there is an element $1/x$ so that $x \times 1/x = 1$.  The integers modulo $m$ are a field if and only if $m$ is prime, because any non-trivial divisor of $m$ would lack an inverse.

Each field has two special elements: ``$0$'' and ``$1$''. The former is the additive identity and the latter is the multiplicative identity:
	$$ 0 + x = x + 0 = x \text{ and } 1 \times x = x \times 1 = x. $$
Note it is impossible for these two elements to be equal. Suppose that $0=1$. Then all elements in the field must be equal, that is the field must contain one element. Suppose that $a \neq b$, then
	$$ 0 \times a = 0 \times b, $$
which implies if $0=1$ that
	$$ 1 \times a = 1 \times b. $$
But then $a=b$. So if $0=1$ the field must have one element. This is impossible, since by definition of a field it must contain at least two elements. See \href{http://en.wikipedia.org/wiki/Trivial_ring}{here} for a simple discussion that a field of one element in this sense forms the trivial ring. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Fields And Mysticism}

So a field must have two elements, or be the trivial ring of no real value. Yet mathematicians have looked for what they call {\it a field with one element}. What they want is mysterious to me: they want a field but somehow they want it to behave like it has one element. Yet not be the trivial ring. 

Okay. Sounds like chess auras to me.

They even have a \href{http://en.wikipedia.org/wiki/Field_with_one_element}{notation} for the object: $F_1$. A quote {\it may} help:
\begin{quotation}
The name ``field with one element" and the notation $F_1$ are only suggestive, as there is no field with one element in classical abstract algebra. Instead, $F_1$ refers to the idea that there should be a way to replace sets and operations, the traditional building blocks for abstract algebra, with other, more flexible objects. While there is still no field with a single element in these theories, there is a field-like object whose characteristic is one. This object is denoted $F_1$.
\end{quotation}

Okay. I am puzzled. See these for more comments on the idea: Peter Cameron \href{http://cameroncounts.wordpress.com/2011/07/20/the-field-with-one-element/}{here}, Noah Snyder \href{http://sbseminar.wordpress.com/2007/08/14/the-field-with-one-element/}{here}, and Lieven Le Bruyn \href{ http://www.neverendingbooks.org/index.php/the-f_un-folklore.html}{here}. The last one has the most fun with what is also called $\mathsf{F_{un}}$ in a French-English pun.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{So What Is $F_1$?}

The above links branch out to many more references including several papers.  We cannot begin to summarize all the aspects of $F_1$ here.  We can, however, tell a secret that seems common to several of these sources:

\begin{quotation}
When an object is impossible to construct explicitly, see if you can give an implicit, operational definition.
\end{quotation}

Here it is, or at least part of it:

\begin{quotation}
$F_1$ is the field such that for all $n$, the general linear group of invertible $n \times n$ matrices with entries in the field is the symmmetric group $S_n$, represented by permutation matrices.
\end{quotation}

The links go on to explain that insofar as permutations act on sets, vector spaces over $F_1$ are just sets, with the permutations as linear transforms.  As such, one can adjoin $0$ as a special element to every set, which the transforms map to itself.  The post by Le Bruyn derives that $F_1$ must be the field whose degree-$(q-1)$ extension is the finite field $F_q$, for all $q$---or at least all $q$ that are prime powers.

But let us go back to the entries of those permutation matrices.  Each row and column has a single $1$, and the products of these $1$'s are all that is needed to locate the $1$'s in the product matrix.  The remaining entries are standardly $0$s so as to make the other products $0$s, but do they really need to be $0$s?  The post by Snyder hints that $F_1$ might be definable by the rule that $1 + 1$ is not $0$ but rather some nebulous quantity $z$ which is some kind of superposition of $1$ and $0$.  It is a non-element, and then all that is needed to compose permutations via matrices is that its product with anything is a non-element.

In that case, the element $1$ takes on a new light.  It is a $1$ whose counterpart is not $0$, but rather absence of anything.  We \href{http://rjlipton.wordpress.com/2012/02/11/introducing-pip/}{described} such a quantity as a {\bf pip}.  So that's what we think: $F_1$ is the field of Pip.

Whether you agree or not, this reminds one of the great Zen question:
\begin{quotation}
``What is the sound of one hand (clapping)?" 
\end{quotation}

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

Do we need to be more open minded in theory research? What would be the analogy of a field with one element be for us? Ken suggests maybe we can make progress on lower bounds against $\mathsf{ACC^0}$ by pretending we have extra elements (or non-elements) lying around so we can treat $\mathbb{Z}_m$ like a field.  The point of all this discussion is to show that mainstream math is willing to be more flexible, more creative, and more mystical, than we seem to be in complexity theory. Perhaps this mysticism is the key to unlock new secrets of computing? What do you think?

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

