Skip to content

Two Versus Three

November 19, 2014


The role of 2 and 3 in mathematics

Farrar
Electrika source

Margaret Farrar was the first crossword puzzle editor for The New York Times. Ken fondly recalls seeing her name while watching his father do the daily and weekly NYT puzzles—they were under Farrar’s byline as editor until 1969 when she retired from the Times. More than a maker of countless puzzles, she also created many of the meta-rules for crossword puzzles, which are still used today in modern puzzle design.

Today Ken and I wish to discuss a light topic: how 2 and 3 are different in many parts of theory and mathematics.

What do 2 and 3 have to do with crossword puzzles? Farrar enshrined the “rule of 2 and 3″ while producing the first crossword puzzle book in 1924 for the fledgling publisher Simon & Schuster. The rule says that 2-letter words are forbidden but 3-letter words are fine in moderation. In the crossword game Scrabble{{}^{\textsuperscript{\textregistered}}}, however, 2-letter words are not only allowed but are vital to strategy. So 2 and 3 are different—yes.

Additional meta-rules include this interesting one:

Nearly all the Times crossword grids have rotational symmetry: they can be rotated 180 degrees and remain identical.

When asked why, Farrar said:

“Because it is prettier.”

In other respects crossword puzzles are more liberal than Scrabble rules. Proper names, abbreviations, multiple-word phrases, prominent foreign words, and clean/trendy slang terms are allowed. Clues ending in ‘?’ may have puns and other wordplay. Here is a small example from us at GLL:


GLLcrossword


Where 2 and 3 Are Different

While 2 and 3 are different enough between crossword puzzles and Scrabble, they are even more so in mathematics. For example, 2 is magic:

\displaystyle  2 + 2 = 2 \times 2 = 2^{2}.

Try that with 3 or any other number. But we are after deeper examples of how 2 differs from 3.

{\bullet } In Number Theory: The number 2 is the only even prime. I recalled here a story of a colleague who works in systems. He was listening to a talk by a famous number theorist. The latter constantly said things like:

Let p be an odd prime and …

My friend asked, “what is an odd prime?”—thinking it must be special in some way. The answer back was: not 2.

{\bullet } In Group Theory: The famous Feit-Thompson Theorem shows that 2 is very special. Any group of odd order—a group with an odd number of elements—must be a solvable group. This was immensely important in the quest to classify all simple groups. Every non-cyclic simple group must have even order, and so must have an element {x} so that {x^{2}=1}.

{\bullet } In Complexity Theory: The evaluation of the permanent is believed to be hard. The best known algorithm still for an {n \times n} permanent is exponential. Yet modulo 2 the permanent and the determinant are equal and so it is easy to evaluate a permanent modulo 2. This relies on the deep insight that

\displaystyle  -1 = 1

modulo 2.

{\bullet } In Quadratic Forms: The theory is completely different over fields with odd characteristic compared to those with characteristic 2. A neat book by Manfred Knebusch begins with this telling verse:

verse

{\bullet } In Algebraic Geometry: I have talked about the famous, still open, Jacobian Conjecture (JC) many times. It is open for two variables or more. But it has long been solved for polynomial maps of degree at most 2. Degree three is enough to prove the general case:

Theorem 1 If the JC is true for any number of variables and maps of degree at most three, then the general case of JC is true.

{\bullet } In Complexity Theory: Many problems flip from easy to hard when a parameter goes from 2 to 3. This happens for coloring graphs and for SAT—to name just two examples.

{\bullet } In Physics: It is possible to solve the two-body problem exactly in Newtonian mechanics, but not three.

{\bullet } In Diophantine Equations: {x^2 + y^2 = z^2} is solvable in positive integers, but as Pierre Fermat correctly guessed, {x^3 + y^3 = z^3} and all higher powers are not.

{\bullet } In Voting and Preferences: Kenneth Arrow’s paradox and other headaches of preferences and apportionment set in as soon as there are 3 or more parties.

Where 2 Is Enough

{\bullet } Computing: Off-on, up-down, NS-EW, open-closed, excited-slack, hot-cold, 0-1 is all we need for computing, indeed counting in binary notation.

{\bullet } In Counting Complexity: Although {\mathsf{2SAT}} is in polynomial time, the counting version {\mathsf{\#2SAT}} is just as hard as {\mathsf{\#3SAT}}. Even more amazing, {\mathsf{\#2SAT}} remains {\mathsf{\#P}}-complete even for monotone formulas in 2CNF or in 2DNF (they are dual to each other).

{\bullet } In Polynomial Ideals: Every system of polynomial equations can be converted to equations of three terms, indeed where one term is a single variable occurring in just one other equation. The idea is simply to convert {P + Q + R + S = 0} into {P + Q + x = 0} and {x - R - S = 0}, and so on. This cannot be done with two terms.

However, systems with two terms, which generate so-called binomial ideals, share all the (bad) complexity properties of general ideals. In particular, testing whether a system forces two variables {s,f} to be equal is {\mathsf{EXPSPACE}}-complete. The proof takes {s} and {f} to be the start and accept states of a kind of 2-counter machine known to characterize exponential space. For example, an instruction to decrement counter {x}, increment counter {y}, and go from state {q} to state {r} yields the binomial {qx - ry}. Thus a configuration such as {qx^{12}y^{16}} becomes {rx^{11}y^{17}} on substituting {ry} for {qx}.

Not Known

{\bullet } In Diophantine Equations: Hilbert’s 10th problem is known to be undecidable for equations in 11 variables. A broad swath of classes of 2-variable Diophantine equations have been shown to be decidable, enough to promote significant belief that a decision procedure for all of them will be found. For three variables, however, the situation is highly unknown according to this 2008 survey by Bjorn Poonen. Only the trivial one-variable decidability is known.

{\bullet } In Diophantine Equations, yet again: Poonen also relates Thoralf Skolem’s observation that every Diophantine equation is equivalent to one of degree 4 in a few more variables. One simply breaks down a power like {x^7} into {(x^2 - u)^2 + (u^2 - v)^2 + } the terms you had with {x^7} replaced by {xuv}. Degree 2 is decidable, but degree 3 is unknown—the feeling is that it’s likely undecidable. All this recalls an old quote by James Thurber:

“Two is company, four is a party, three is a crowd. One is a wanderer.”

Open Problems

What is your favorite example of the {2} is different from {3} phenomenon? Recall that Albert Meyer once said:

Prove your theorem for {3} and then let {3} go to infinity.

Alexander Grothendieck 1928–2014

November 16, 2014


Creating vast beautiful mansions from the becoming of nothing

Grothendieck1975
L’espace d’un homme film source

Alexander Grothendieck, who signed his works in French “Alexandre” but otherwise kept the spelling of his German-Jewish heritage, passed away Thursday in southwestern France.

Today we mourn his passing, and try to describe some of his vision.
Read more…

Three In The Room

November 12, 2014


A puzzle and a conference

manna2

Zohar Manna is an expert on the mathematical concepts behind all types of programming. For example, his 1974 book the Mathematical Theory of Computation was one of the first on the foundations of computer programming. He wrote textbooks with the late Amir Pnueli on temporal logic for software systems. As remarked by Heiko Krumm in some brief notes on temporal logic, there is a contrast between analyzing the internal logic of pre- and post-conditions as each statement in a program is executed, and analyzing sequences of events as a system interacts with its environment.

Today I want to talk about an encounter with Zohar years ago, and how it relates to a puzzle that I love.
Read more…

A Conjecture Of Ulam

November 8, 2014


A pointed question about the plane

7205311_1046261214

Stanisław Ulam was one of the great mathematicians of the last century. We talked about him in a recent post on his prime spiral and other strange mathematical facts. He is associated with several famous problems, including the 3n+1 problem and the Graph Reconstruction conjecture.

Today we want to talk about one of his oldest conjectures.

The conjecture was first stated in 1945. It is simple to state, seems plausible that it is true, but so far has resisted all attempts at resolution. René Descartes could have stated in the 1600s—well almost. Read more…

DC Post

November 6, 2014


Discussing lower bounds for this blog’s 600th post

trinity-tpb-2-batman-vs-superman-fears-over-wonder-woman
source

Superman, Batman, and Wonder Woman are three of the best known superheroes in DC Comics books, which were a childhood staple for many of our age. They brought us action in color before our families had color TVs. There is a new nonfiction book on Wonder Woman. She and Superman have super powers: flying, super strength, X-ray vision, magical healing, and more. It is notable that Batman does not. All of his powers come from great training, great study, great equipment, and great helpers.

Today this blog makes post number 600, DC in Roman numerals. Read more…

Reconstructing Gödel

November 1, 2014


What exactly was his “Philosophical Viewpoint”?

GodelRB
By permission of Renee Bolinger, artist : source

Kurt Gödel left a large amount of unpublished writings and notebooks and preserved correspondence. Called his Nachlass, German for “after-leavings” or bequest, these writings were catalogued and organized by several—including his first biographer, John Dawson, for a heroic two years. Those of highest scientific and general interest were published in volumes III, IV, and V of Kurt Gödel: Collected Works. Among them was a list of 14 numbered assertions titled “My philosophical viewpoint” but without elaboration. They are believed associated to a lecture Gödel started preparing in the early 1960s but never gave, whose draft is in the Nachlass.

Today we are delighted to have new communications from Gödel, as we have previously received around Halloween and All Saints’ Day, so we can continue our series of interviews with him.
Read more…

Rebooting Computing

October 27, 2014


How to beat the end of Moore’s Law

Screen Shot 2014-10-27 at 2.25.21 PM

Elie Track and Tom Conte were co-chairs of the recently-held Third IEEE workshop on Rebooting Computing. Tom is a computer architect at Georgia Tech. A year ago he became the 2014 President-Elect of the IEEE Computer Society, which according to both the press release and Conte’s Wikipedia page entails that he “currently serves as the 2015 President.” I guess that is one way to stay focused on the future. Track is president of the IEEE Council on Superconductivity. A year ago he founded nVizix, a startup to develop photovoltaic power, and serves as CEO. He is also a senior partner at Hypres, a superconducting electronics company.

Today I wish to relate some of what happened last week at the meeting.
Read more…

Follow

Get every new post delivered to your Inbox.

Join 2,025 other followers