{\huge Two Versus Three}

The role of 2 and 3 in mathematics \vspace{.2in}

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 $latex {180}&fg=000000$ 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:

\includegraphics[width=3.5in]{GLLcrossword.png}

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, $latex {2}&fg=000000$ is magic:

$latex \displaystyle 2 + 2 = 2 \times 2 = 2^{2}. &fg=000000$

$latex {\bullet }&fg=000000$ 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 $latex {p}&fg=000000$ be an odd prime and $latex {\dots}&fg=000000$ My friend asked ``what is an odd prime?''---thinking it must be special in some way. The answer back was: not two.

$latex {\bullet }&fg=000000$ In Group Theory: The famous Feit-Thompson Theorem shows that two 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 be even order, and must have an element $latex {x}&fg=000000$ so that $latex {x^{2}=1}&fg=000000$.

$latex {\bullet }&fg=000000$ In Complexity Theory: The evaluation of the permanent is believed to be hard. The best known algorithm still for an $latex {n \times n}&fg=000000$ 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

$latex \displaystyle -1 = 1 &fg=000000$

$latex {\bullet }&fg=000000$ 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:

\includegraphics[width=2.5in]{verse.png}

$latex {\bullet }&fg=000000$ 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 two. 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.

$latex {\bullet }&fg=000000$ 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.

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

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

$latex {\bullet }&fg=000000$ 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

$latex {\bullet }&fg=000000$ 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.

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

$latex {\bullet }&fg=000000$ 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 $latex {P + Q + R + S = 0}&fg=000000$ into $latex {P + Q + x = 0}&fg=000000$ and $latex {x - R - S = 0}&fg=000000$, 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 $latex {s,f}&fg=000000$ to be equal is $latex {\mathsf{EXPSPACE}}&fg=000000$-complete. The proof takes $latex {s}&fg=000000$ and $latex {f}&fg=000000$ 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 $latex {x}&fg=000000$, increment counter $latex {y}&fg=000000$, and go from state $latex {q}&fg=000000$ to state $latex {r}&fg=000000$ yields the binomial $latex {qx - ry}&fg=000000$. Thus a configuration such as $latex {qx^{12}y^{16}}&fg=000000$ becomes $latex {rx^{11}y^{17}}&fg=000000$ on substituting $latex {ry}&fg=000000$ for $latex {qx}&fg=000000$.

Not Known

$latex {\bullet }&fg=000000$ 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.

$latex {\bullet }&fg=000000$ 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 $latex {x^7}&fg=000000$ into $latex {(x^2 - u)^2 + (u^2 - v)^2 + }&fg=000000$ the terms you had with $latex {x^7}&fg=000000$ replaced by $latex {xuv}&fg=000000$. 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 $latex {2}&fg=000000$ is different from $latex {3}&fg=000000$ phenomenon? Recall that Albert Meyer once said:

Prove your theorem for $latex {3}&fg=000000$ and then let $latex {3}&fg=000000$ go to infinity.