# Two Versus Three

* The role of 2 and 3 in mathematics *

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*, 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:

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

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

*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

pbe 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*.

*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 so that .

*In Complexity Theory*: The evaluation of the permanent is believed to be hard. The best known algorithm still for an 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

modulo 2.

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

*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 1If the JC is true for any number of variables and maps of degree at most three, then the general case of JC is true.

*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.

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

*In Diophantine Equations*: is solvable in positive integers, but as Pierre Fermat correctly guessed, and all higher powers are not.

*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

*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.

*In Counting Complexity*: Although is in polynomial time, the counting version is just as hard as . Even more amazing, remains -complete even for monotone formulas in 2CNF or in 2DNF (they are dual to each other).

*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 into and , 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 to be equal is -complete. The proof takes and 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 , increment counter , and go from state to state yields the binomial . Thus a configuration such as becomes on substituting for .

## Not Known

*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.

*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 into the terms you had with replaced by . 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 is different from phenomenon? Recall that Albert Meyer once said:

Prove your theorem for and then let go to infinity.

My favorite difference is the recurrence of a discrete random walk in two dimensions, and the non-recurrence in 3 dimensions. Or, as Shizuo Kakutani put it: “A drunk man will find his way home, but a drunk bird may get lost forever.”

I found interesting next fact (aka 2 is enough):

Every system of Diophantine equations is equivalent to a system of quadratic inequalities. That’s kinda surprising)

The process is the same as you describe for one equation of a degree 4 without last (or first) step.

You should create the same for 1 and all other natural:) Though maybe it wouldn’t be so interesting…

The generative potency of triadic relations In comparison with dyadic relations.

I’m surprised you didn’t mention the old saying “2 is the oddest prime”

2 is the oddest prime!

Two favourite examples: First, any random walk on a lattice in dimension two has unit probability to reach any point. This does not hold in dimension three anymore.

Second, in Vector Addition Systems with States (VASS), the set of reachable configurations in dimension two is semi-linear, whereas it is provably not semi-linear anymore for any dimension greater than two.

Some other random ones:

2-player Nash equilibria for rational payoffs are rational, 3 players not. (Though surprisingly, PPAD-completeness extends to 2 players despite the intuition that this might make a difference in complexity.)

(Related to the random walk example)

Embedding graphs in 2-D vs 3-D: Planar graphs have many nice properties: self-duality, low density etc. Embedding in 3-D says nothing.

Self-duality implies edge percolation on the 2-D grid has a threshold of 1/2. For the 3-D grid, no analytic way to calculate the threshold is known AFIK.

Continued fraction expansions of quadratic irrationals have repeating tails, while any algebraic irrationals of a higher degree do not.

Given a tensor of order 2, what is its rank? That’s very easy.

Given a tensor of order 3 (or higher), what is its rank? That’s

very hard!SequelaeOrder-2-tensor ranks are so easy to compute that quantum mechanics commonly is taught at the undergraduate level. Order-3-tensor ranks (and higher orders) are so hard that varietal dynamics (almost?)neveris.Alert (caveat?)Students who contemplate this difference follow in the footsteps of mathematicians Erich Kähler and Alexandre Grothendieck.——–

ReadingsDifferential Logic is basically just differential geometry over GF(2) and so it harbors a few surprises. Most people get stuck at the point where they tri to compute a Taylor series and tri to divide by 2! = 2 = 0, but I think there’s a way around that if you ask what the 2! is really about.

Spatial relationships between 2-dimensional objects are ralatevely easy to compute. The same kind of relationships for 3-dimensional objects are tricky as 3d objects are more complex. As an example consider whether two spatial objects share some space. If they are 1d or 2d objects and share some space, it is either that their boundaries intersect or that the one is enclosed in the other. In 3d these creteria are not enough and a most sophisticated aproach is required.

The planiverse!“Lifting” C.P. Snow’s two cultures(1)the rational culture of science, as apposed to(2)the moral culture of the humanities, lifts naturally to(3)a radical culture of internees.This lift is inspired by the roster of imprisoned/interned algebraic geometers and dynamicists that includes the names

Galois, Weil, Kähler, Kohn, Grothendieck, and Koblitz.Semi-serious questionWhy does imprisonment seemingly foster an enduring passion — and even an outstanding aptitude — for algebraic geometry and dynamics?A math-and-science passion that radically transcends C.P. Snow’s two cultures?

The world wonders!

Most probably, when people have been denied for too long the right to move their body within sufficient space, they later on take a revenge by defining new kinds of space and motion…

But what of Poncelet?

Nice example, projective geometry being among the sources of algebraic geometry.

True, but on the spectrum from algebraic geometry to geometric algebra he seems to be enprismed more toward the synthetic end.

Look at the couple computer-programmer. They were happy together until mathematicians began to ask which algorithms actually exist. The same is true with light and its admirers. Everyone was happy until physicists entered the scene with quantum mechanics. By doing so, they confirmed that things get more complex whenever a third actor comes in. But the couple phenomenon-observer is definitely out of date – it’s been replaced without notice by the triple phenomenon-observer-mathematician… for better or for worse!