The role of 2 and 3 in mathematics
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 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.
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 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.
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.
Like this:
Like Loading...
Related
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!
Sequelae Order-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?) never is.
Alert (caveat?) Students who contemplate this difference follow in the footsteps of mathematicians Erich Kähler and Alexandre Grothendieck.
——–
Readings
@book{Landsberg:2012fk, Address = {Providence, R.I.}, Author = {Landsberg, Joseph M.}, Publisher = {American Mathematical Society}, Title = {Tensors: Geometry and Applications}, Year = {2012}} @incollection{Ashtekar:1999yu, Address = {New York}, Author = {Abhay Ashtekar and Troy A. Schilling}, Booktitle = {On Einstein's Path}, Editor = {A. Harvey}, Pages = {23--65}, Publisher = {Springer}, Title = {Geometrical formulation of quantum mechanics}, Year = 1999}Differential 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.
“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 question Why 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!
Too bad the theorem fails for AC^0[q] as q in {2,3,\dots (but primes)} cannot contain AC^0[6] but latter can contain CH.
Too bad the theorem fails for AC^0[q] as q in {2,3,\dots (but primes)} cannot contain AC^0[2,3] but latter can contain CH ([2,3] stops at [2,3] and may not go to [2,3,5] as AC^0[2,3] can contain CH).