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.

20 Comments leave one →
  1. Andy permalink
    November 19, 2014 10:50 pm

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

  2. November 19, 2014 11:01 pm

    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…

  3. November 19, 2014 11:03 pm

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

  4. November 19, 2014 11:37 pm

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

  5. k-jl permalink
    November 20, 2014 3:04 am

    2 is the oddest prime!

  6. Chris permalink
    November 20, 2014 4:48 am

    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.

  7. Paul Beame permalink
    November 21, 2014 1:26 pm

    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.

  8. November 21, 2014 1:50 pm

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

  9. November 22, 2014 12:50 am

    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}
    
  10. November 22, 2014 11:48 am

    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.

  11. Pantelis Rodis permalink
    November 22, 2014 1:49 pm

    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.

  12. November 23, 2014 4:38 pm

    \bullet \mathbf{2 \overset{\scriptscriptstyle ?}{\ne} 3}  The planiverse!

  13. November 23, 2014 4:54 pm

    “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 2\to3 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!

    • Serge permalink
      November 23, 2014 6:54 pm

      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…

    • November 23, 2014 9:40 pm

      But what of Poncelet?

      • Serge permalink
        November 24, 2014 8:36 am

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

      • November 24, 2014 8:52 am

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

  14. Serge permalink
    November 23, 2014 7:56 pm

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

    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!

Trackbacks

  1. My Favorite Number | Anecdotal Math
  2. Why Is Discrete Math Hard To Teach? | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s