Are we too “normal” in our approach to open problems?

Boris Spassky is the oldest living world chess champion. He held the title 1969 to 1972, until famously losing to Bobby Fischer in the Match of the Century. Watching the game from the US was made even more exciting by the PBS broadcast hosted by Shelby Lyman—see 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:

I move the piece whose aura is the brightest.

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.

## Seriously?

Ken helped me with our earlier 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 book by Daniel Kahneman, 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:

• Fast—automatic, intuitive, frequent, subconscious…
• Slow—logical, calculating, painstaking, conscious…

Well, I picked through the index of the book and found a 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 “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 hosted the Princeton Turing conference in May, wrote a book on when and whether a common chess sacrifice will succeed. By itself the sacrifice is a 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 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 post, is an example validated by proof. Here is one yet waiting.

## 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: 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.

## 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,

$\displaystyle (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 nonzero elements form an Abelian group under multiplication, and the two are connected by the distributive law. What distinguishes a field from a lesser system called a 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:

$\displaystyle 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

$\displaystyle 0 \times a = 0 \times b,$

which implies if ${0=1}$ that

$\displaystyle 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 here for a simple discussion that a field of one element in this sense forms the trivial ring.

## 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 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 notation for the object: ${F_1}$. A quote may help:

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}$.

Okay. I am puzzled. See these for more comments on the idea: Peter Cameron here, Noah Snyder here, and Lieven Le Bruyn here. The last one has the most fun with what is also called ${\mathsf{F_{un}}}$ in a French-English pun.

## 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:

When an object is impossible to construct explicitly, see if you can give an implicit, operational definition.

Here it is, or at least part of it:

${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.

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. See also its continuation.

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 described such a quantity as a 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:

“What is the sound of one hand (clapping)?”

## 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?

1. August 23, 2012 9:52 pm

What if one considers a set with just the number 1, and the two operations being multiplication and exponentiation? This circumvents the a!=b proof since there aren’t two distinct elements a & b in the set. Maybe I’m missing something.

Exponentiation is an unusual choice for “multiplication” since it’s not usually a commutative operation. But in this case, since we have only one element {1}, I guess the operation is Abelian in this set. Another quirk of this example is that the “zero” element actually has a “multiplicative” inverse, though I don’t know if that’s unacceptable.

• August 23, 2012 10:02 pm

Ah, well. After reading the Wiki link, I see that I’ve just given a realization of the trivial ring 😛

August 24, 2012 2:34 am

For my take, there is enough mysticism with oracles around in complexity theory, that don’t hold up in the real world, and with conventional wisdom about what can and can’t collapse…

3. August 24, 2012 2:51 am

Brilliant idea! Bend mathematics to show the truth! and bend truth to show mathematics!

August 24, 2012 6:15 am

One basic thing that confuses me a bit is the statement that 0 X a = 0 i.e. the additive’ identity multiplied’ by a number gives back the additive identity (Of course, we are very familiar with this in case of integers). Is suppose this is not an axiom but easily derivable – how?

August 24, 2012 7:39 am

0a = (0+0)a = 0a + 0a

5. August 24, 2012 12:20 pm

I supposed it comes down to the fact that you can define a mathematical objects to be anything you want with any properties. Then all you need to do is formalize them into a rigid system and explore how it all behaves. Some of these formal system may have unexpected parallels to the real world and thus become useful. Some of them will not.

Paul.

August 24, 2012 2:23 pm

Sadly, Bill Thurston has passed away. 😦

Bill’s MathOverflow profile is a fitting epitaph for a mathematical life well-lived:

Mathematics is a process of staring hard enough with enough perseverenceat at the fog of muddle and confusion to eventually break through to improved clarity.

I’m happy when I can admit, at least to myself, that my thinking is muddled, and I try to overcome the embarassment that I might reveal ignorance or confusion. Over the years, this has helped me develop clarity in some things, but I remain muddled in many others.

I enjoy questions that seem honest, even when they admit or reveal confusion, in preference to questions that appear designed to project sophistication.

Perhaps the mystical element that we mainly need in mathematics — in any enterprise — is as simple as a little bit of Bill Thurston’s spirit? 🙂

August 25, 2012 12:46 pm

Also apropos to non-rational mathematical understanding is Bill Thurston’s Foreword to Daina Taimina’s Crocheting Adventures with Hyperbolic Planes

Many people have the impression, based upon years of schooling, that mathematics is an austere and formal subject concerned with complicated and ultimately confusing rules for the manipulation of numbers, symbols, and equations, rather like the preparation of a complicated income tax return, where there are myriad unexplained steps, rules, exceptions, and gotchas.

Good mathematics is quite the opposite of this. Mathematics is an art of human understanding. Billions of years of evolution have given us many extraordinary capabilities that we ordinarily take for granted—but we deny these capabilities at our peril. In the abstract, the mere act of walking through a room without bumping into other people or things is a far greater accomplishment than the most sophisticated formal calculation ever done by mathematicians. Computers are far better than humans at formal computations, but humans far surpass current computers at informal and intuitive reasoning.

Our brains are complicated devices, with many specialized modules working behind the scenes to give us an integrated understanding of the world. Mathematical concepts are abstract, so it ends up that there are many different ways that they can sit in our brains. A given mathematical concept might be primarily a symbolic equation, a picture, a rhythmic pattern, a short movie — or best of all, an integrated combination of several different representations. These non-symbolic mental models for mathematical concepts are extremely important, but unfortunately, many of them are hard to share.

Mathematics sings when we feel it in our whole brain. People are generally inhibited about even trying to share their personal mental models. People like music, but they are afraid to sing.

You only learn to sing by singing.

For thus illuminating our mystical appreciation of mathematics — or more formally, by illuminating the practice of mathematics as among humanity’s greatest naturalizing and universalizing activities — the preceding appreciation and thanks is posted in tribute to the spirit of Bill Thurston! 🙂

August 24, 2012 5:38 pm

> … 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?

I couldn’t agree more with this. This is the second instance in history where scientists have been part of the problem they’re studying. The first instance – quantum mechanics – was dealt with by using probabilities instead of certainty. The present instance – computing complexity – could be treated by using complexity instead of certainty. I don’t know… Or maybe we could try to study problem solving more generally, rather that focusing on the use of algorithms. Problem complexity makes sense in many other contexts than just programming…

August 24, 2012 9:56 pm

I’d like to throw my hat in the ring and ask: “What are the odds the aura he references is based on some kind of synesthesia-like mapping?”

August 25, 2012 5:57 am

Here’s a comparison I like to use for myself : how hard is it to go to the moon? In the middle age it was impossible. In 1969 it became feasible. No serious scientist would speak of the inherent complexity of the problem “going to the moon”. Everyone is willing to admit that its complexity depends on the point in history when this problem was tackled. But when mathematical problems are concerned, scientists want a universal notion of complexity. In my view, this is wrong.

August 26, 2012 5:24 am

Sadly, the first man who walked on the moon has also just passed away. May he rest in peace on this planet.

10. August 25, 2012 8:06 am

the sound of one hand clapping should be inaudible infrasound, because that hand still moves through the air, causing waves in it.

11. September 11, 2012 1:33 pm

Do We Need Mysticism in Theory? My personal experience says yes, although instead word Mysticism I used a term “to have feeling”. You can see such my recent experience if you go to http://www.ab2you.com and see story about puzzle The Olympic Numerical Pentathlon 2012 and the story about Columbus’s numbers.

12. December 26, 2012 10:30 pm

Your mention of Fast vs. Slow Thinking (Quick vs. Dead Reckoning?) brings to mind the hoary old topic of Non-Demonstrative vs. Demonstrative Reasoning. This distinction goes back as far as Aristotle but got picked up and developed in modern times by the Pragmatists following C.S. Peirce. Aristotle and Peirce both distinguish the demonstrative style of inference that we know as deduction from two non-demonstrative styles of inference that translators of Aristotle usually render as abduction (plucking hypotheses out of thin air) and induction (checking theories against empirical data).

December 27, 2012 3:05 pm

Doesn’t Peirce call it Retroductive Logic?

http://www.helsinki.fi/science/commens/terms/retroduction.html

• December 27, 2012 11:50 pm

Yes, that was one of several names he used. I usually go with abductive inference if only for the sake of simplicity and lexical parallelism. Here are a couple of pertinent blog posts, with links to more information.

13. May 17, 2015 5:09 pm

Reblogged this on Human Mathematics.

14. May 17, 2015 10:30 pm

Seems like the combination of mysticism and rationality is a luxury only pure mathematicians can jointly entertain. I have no doubts about Colin Rourke’s work although his webpage has a crazy-looking 9/11 theory on it. Gödel worked on Anselm’s argument; Grothendieck wrote the Clef des Songes; Voevodsky had a spiritual experience in Salt Lake City. Maybe with the mind too far closed invention would be shut off as well.