When is 2 qualitatively different from 3?

Question

I'd like to get a list of instances in mathematics where a problem with two parameters (or some parameter set to $2$) is qualitatively different from the instance of that problem with the value set to $3$.

Examples include:

• Hypothesis testing, where for 2 alternatives there is an analytically computable minimax strategy (Neyman-Pearson), but for 3 or more, the minimax decision is NP-hard to compute.

• Voting theory: for 2 alternatives, simple majority vote is Pareto-efficient, non-dictatorial, and satisfies independence of irrelevant alternatives (trivially). For 3 or more, we have Arrow's impossibility theorem.

• Graph coloring/satisfiability: both 2-SAT and 2-COLORABILITY are in P, while 3-SAT and 3-COLORABILITY are NP-complete

If anyone has any unifying intuition for why/when 3 is qualitatively different from 2, that would be great too.

Answer 1

Random walks in 2 dimensions are recurrent whereas in higher dimensions random walks are not. And there is a wonderful colloquialism by Shizuo Kakutani to remember this: “A drunk man will find his way home but a drunk bird may get lost forever.”

Answer 2

Fermat's last theorem states that there are no non-trivial integer solutions to $x^n+y^n=z^n$ for $n=3$ (or in fact any $n\geq 3$), but there are of course many Pythagorean triples that give solutions for $n=2$.

Answer 3

Infinitely many regular polygons in dimension 2, five regular polyhedra in dimension 3.

Answer 4

N-body problems are another; the 2-body case is simple, the 3-body case is intractable.

Answer 5

It is relatively easy to "divide by 2" without choice, but it is very hard to "divide by 3".

Answer 6

As mentioned in another answer, free lattice on $2$ generators is finite, while a free lattice on $3$ generators is infinite.

Even more impressively though, a free complete lattice on $2$ elements is finite (it simply coincides with the free lattice) while a free complete lattice on $3$ elements does not exist.

Answer 7

There exist plenty of continuous maps $\mathbb R \to \mathbb R$ whose largest periodic cycle has length $2$, but no such maps whose largest cycle has length $3$. (This is a consequence of Sharkovskii's theorem.)

Answer 8

Lots of questions about tensors are easy when the order of the tensor is 2 (i.e., when it can be thought of as a matrix), but are NP-hard when the order of the tensor is 3 or higher. Examples include rank and spectral norm.

Answer 9

Every group in which every non-identity element has order 2 is abelian.

Answer 10

Ando's theorem: any pair of commuting contractions on a Hilbert space can be dilated to a pair of commuting unitaries. This fails for three commuting contractions.

Answer 11

Due to the Poincaré–Bendixson theorem, continuous dynamical systems can not be chaotic in two dimensions, while they can in three dimensions.

Answer 12

In a three or higher dimensional Euclidian space, the infinitesimal conformal transformations generate a finite dimensional Lie algebra, while in two dimensional Euclidian space, it is an infinite dimensional Lie algebra.

Answer 13

There exists a finitely additive isometry invariant measure on $\mathcal{P}(\mathbb{R}^n)$ extending the Lebesgue measure for $1 \leq n \leq 2$, but not for $n \geq 3$.

Answer 14

$SL_3(\mathbb R)$ and $SL_3(\mathbb Z)$ exhibit Kazhdan's property (T). $SL_2(\mathbb R)$ and $SL_2(\mathbb Z)$ do not.

Answer 15

Complex numbers exist only in dimension 2. That is the only multiplication laws on $R^n$ which satisfy all field axioms exist for $n=1$ (real numbers) and $n=2$ (complex numbers).

Answer 16

The automorphism group of $k[x_1,x_2]$ (the polynomial ring in two variables over a field $k$) is pretty well understood classically, but very little is known about the automorphism group of $k[x_1,\dotsc,x_n]$ for $n\geq 3$: see "The Tame and the Wild Automorphisms of Polynomial Rings in Three Variables," by Shestakov–Umirbaev. See also the Wikipedia page for the related problem on the ring of rational functions.

Answer 17

One can decide if a Diophantine equation of degree $d=2$ (and as many variables as you want) admits a solution over $\mathbb Z$ (Siegel 1972) or $\mathbb N$ (Grunewald and Segal 2006). The same question is wide open in degree $d=3$, and known to be undecidable in degree $d\ge 4$.

Answer 18

This is quantitative rather than qualitative, but it's so huge that it fits, perhaps:

TREE(2) vs TREE(3)

https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE_function

Answer 19

Let $G$ be a finite group. If the order of $G$ is not divisible by 2, then $G$ is solvable; if it is not divisible by 3, then no such conclusion can be drawn.

Answer 20

If $n$ is finite, then the number of clones on an $n$-element set is countable if $n\leq 2$ and has size continuum if $n\geq 3$.

Answer 21

For a subset $A$ of a (not necessarily abelian) group $G$, define the iterated product set $$A^n=\{a_1\cdots a_n \mid a_1,\ldots,a_n\in A\}.$$ Good control on the size of $A^3$ (small tripling of $A$) is enough to give control on the size of $A^n$: $$|A^3|\leq K|A|\implies |A^n|\leq K^{n-2}|A|\text{ for every }n\geq 3.$$ On the other hand, if one only knows $|A^2|\leq K|A|$ (small doubling of $A$), such strong bounds are (very) false. One example (copied from Example 2.5.2 in Tointon's Approximate Groups) is as follows: let $H$ be any finite group, let $G$ be the free product of $H$ with an infinite cyclic group generated by some element $x$. Let $A=H\cup\{x\}$. Then $$|A^2|=|H\cup xH\cup Hx\cup \{x^2\}|=3|H|+1<3|A|,$$ while $$|A^3|\geq|H\cup xH\cup Hx\cup HxH|=1+2|H|+|H|^2=|A|^2$$ is much larger than $|A|$.

Answer 22

Graph theory

Regular graphs of degree $2$ are just cycles (if connected), but regular graphs of degree $3$ are in some sense already as complicated as it can get.

Graphs of chromatic number $2$ behave so differently from chromatic number $\ge 3$ that they got a special name: bipartite graphs. OP already mentioned graph coloring, but I want to emphasize that the distinction goes much deeper and bipartite is not always the easy case. For example, the asymptotics of extremal edge numbers follows from the Erdős–Stone theorem when forbidding non-bipartite sub-graphs, but is mostly unknown when forbidding bipartite sub-graphs.

$r$-uniform hypergraphs for $r=2$ are just good old graphs and are much simpler objects than for $r\ge 3$.

Answer 23

An $n$-generated free lattice is finite if $n\leq 2$ and infinite if $n\geq 3$.

Answer 24

The Ising model is NP-complete for $d \geq 3$ but not $d \leq 2$.

The Ising Model Is NP-Complete. SIAM News, Volume 33, Number 6:

The three-dimensional spin glass model for the standard square lattice [is] NP-complete. More precisely, for the three-dimensional result, Barahona showed that a graph-theoretic problem known to be NP-complete—the task of finding a maximum set of independent edges (i.e., with no vertices in common) in a graph for which each vertex has degree 3—can be reduced to the problem of finding a ground state for the three-value coupling constant ($J_{ij}$ = –1, 0, or 1) on a cubic grid.

Answer 25

If we say that integer partitions correspond to $n=1$, plane partitions to $n=2$ and solid partitions to $n=3$, then the cases $n=1,2$ are special in the sense that a simple generating function is known, while for $n\geq3$ this is not the case.

Answer 26

The Banach-Tarski paradox holds in $\mathbb{R}^3$ but fails in $\mathbb{R}^2$.

Answer 27

The multiplicative group of $\mathbb{Z}/2^n \mathbb{Z}$ is $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{n-2}\mathbb{Z}$ and is non-cyclic whenever $n \ge 3$. The multiplicative group of $\mathbb{Z}/3^n \mathbb{Z}$ is cyclic of order $\phi(3^n) = 2 \times 3^{n-1}$.

Answer 28

The wave equation $$\partial_t^2u=\Delta_xu$$ exhibits different behaviour in space dimension $2$ and $3$ (more generally in even and odd space dimensions). The simplest is $d=3$ (!), where the fundamental solution (initial data $u(0,\cdot)\equiv0$ and $\partial_tu(0\cdot)\delta_0$, the Dirac mass) has a lacuna: it vanishes identically away from the light cone $\|x\|=|t|$. This implies the Huyghens principle. If instead $d=2$, then the fundamental solution is supported by the solid cone $\|x\|\le|t|$, and the Huyghens principle fails.

Answer 29

The congruence subgroup problem has a positive answer for $SL_n(\mathbb Z)$ for $n\geq 3$ - every finite index subgroup contains a subgroup of the form $\{A\mid A\equiv I_n\pmod N\}$ for some $N$.

For $n=2$, this is no longer the case - $SL_2(\mathbb Z)$ has many non-congruence finite index subgroups, in fact most (in asymptotic sense) of them are.

Answer 30

General relativity is topological for $\leq 2$ spatial dimensions.

Quantum gravity in 2 + 1 dimensions: The case of a closed universe:

A (2 + 1)-dimensional spacetime has no local degrees of freedom: There are no gravitational waves in the classical theory, and no propagating gravitons in the quantum theory.