How important is it to take sides in complexity?
Barry Mazur has contributed to many areas of mathematics for many decades. His paper “Modular curves and the Eisenstein ideal” and related work furnished key ideas for Andrew Wiles’ ultimately-successful strategy on Fermat’s Last Theorem.
Today Ken and I want to discuss how well we guess.
Well not us—we guess that we two guess pretty poorly. The “we” refers to the theory community, or more generally the mathematics community.
Among many of us currently guessing how the strife in Congress to reach a deal on the US budget crisis will play out is Krystal Ball, who sometimes does analysis for Fox News. That’s right—a great name to humble experts who are really paid for educated guesses.
In 1994, Mazur won a Chauvenet Prize for Mathematical Exposition from the American Mathematical Society for his article “Number Theory as Gadfly” about the Shimura-Taniyama-Weil conjecture which is related to Fermat. His opening paragraph has these cautionary words for guessers:
“Number Theory…produces, without effort, innumerable problems which have a sweet, innocent air about them, tempting flowers; and yet…swarms with bugs, waiting to bite the tempted flower-lovers who, once bitten, are inspired to excesses of effort!”
These are words to take especially carefully from someone who even has a swindle named after him. Hence we offer a post on just how wary one should or should not be.
Two Old Examples
An old joke is that are all primes or prime powers. The next number, 13, confirms it, right?
The number , the digits going up and then down, looks like requiring a complicated factorization. For it to be prime or have simple factors might seem too much a coincidence. But in fact:
A Rash Conjecture
Barry Mazur in another neat paper points out what he calls a rash conjecture. The Bernoulli numbers are defined by:
The obvious guess is that is of the form where is a natural number. Unfortunately,
where is a prime. So this nice, but rash, conjecture blows up quickly.
Another Misleading Set of Examples
Cyclotomic polynomials are defined by the equation:
over all roots of unity that are primitive.
The first ten such polynomials and two others are listed here. A quick look shows that all the nonzero coefficients are :
You could continue this out past and still see coefficients of only . Must be a theorem, right? Alas, a surprise happens at the :
Notice the coefficient of lurking out there on the term. The theorem lurking out there is that the coefficients are when has at most two distinct odd prime factors, while .
Things are even more surprising. Define as the maximum coefficient, in absolute value, of all cyclotomic polynomials of degree at most . Then it is known that
for any function that tends to zero as grows.
A Strange Fact
The Fermat quotient is , where is a prime. By his “Little” theorem this is always an integer.
A guess might be that this integer is unlikely to be divisible by again. Wrong. There are primes so that
These are called Wieferich primes, and were first found by Arthur Wieferich in 1909.
Sky’s The Limit on Guessing
Ken and I are both reading Brian Greene’s new book The Hidden Reality: Parallel Universes and the Deep Laws of the Cosmos. Early on, Greene presents as focal the question of whether the spatial extent of the cosmos is finite or infinite. Which would you guess?
Both possibilities allow for some kind of multiverse, and Greene’s book surveys at least nine—count ’em nine—separate multiverse theories. The current August 2011 issue of Scientific American has some skepticism on most if not all of them.
String-theory skeptic Peter Woit recently blogged about an interview story in the July 2011 issue of Scientific American on Leonard Susskind, whom Woit identifies as “the most prominent promoter of the string-theory multiverse.” We re-post the same long excerpt Woit takes from that interview, but as an example of field-wide “guessing”:
A large fraction of the physics community has abandoned trying to explain our world as unique, as mathematically the only possible world. Right now the multiverse is the only game in town. Not everybody is working on it, but there is no coherent, sharp argument against it.
In 1974 I had an interesting experience about how scientific consensus forms. People were working on the as-yet-untested theory of hadrons called quantum chromodynamics, or QCD. Hadrons are subatomic particles that are believed to be made up of quarks held together by the strong force, and include protons and neutrons. At a physics conference I asked, “You people, I want to know your belief about the probability that QCD is the right theory of hadrons.” I took a poll. Nobody gave it more than 5 percent. Then I asked, “What are you working on?” QCD, QCD, QCD. They were all working on QCD. The consensus was formed, but for some odd reason, people wanted to show their skeptical side. They wanted to be hard-nosed. There’s an element of the same thing around the multiverse idea. A lot of physicists don’t want to simply fess up and say, “Look, we don’t know any other alternative.”
Here is our point: In physics, it takes much theoretical legwork to justify, then design, a proposed experiment bidding for time at a major collider or lab or observatory. Thus it seems one must make guesses and take sides in order to be creative. Is this so in computer science theory? We have previously advocated working on both sides of every hard question.
What about complexity theory? Do we have any rash conjectures—or are we great guessers? Do we need to be better guessers?
Also what about multiverse theories? Do they imply that there is a world where ?
Note that “” in a universe with different physical laws can possibly refer to a different class of feasibly computable problems from ours, which would also change the denotation—though not the definition—of “” in terms of it. This article by Scott Aaronson is a start, along with the view here implying that minds in such a universe would evolve to perceive that “” rather than ours.