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

Weak $n$-categories (or even groupoids) are equivalent to strict $n$-categories for $n \leq 2$ but not for $n \geq 3$. This famously tripped Kapranov and Voedvosky, and the counterexample is due to Simpson.

Answer 2

There are quite a few examples like this from quantum information theory (beyond the basic fact that 2-tensors are "easy" and 3-tensors are "hard", which I already mentioned in another answer). Here are a couple:

• A big problem in the field is, given a density matrix (mixed state) acting on $\mathbb{C}^n \otimes \mathbb{C}^n$, how can we determine whether or not it is separable? It turns out this problem is easy if $n = 2$: just compute the partial transpose and then compute eigenvalues (in particular, it's polynomial-time and just makes use of "standard" linear algebra tricks). By contrast, when $n \geq 3$, it is known that the set of separable states is not semidefinite representable (loosely: it's not possible to use "standard" linear algebra tricks to determine separability).
• How well can you distinguish two quantum states? If there are $n = 2$ states, there's an explicit formula for the maximum probability of distinguishing the states, and the measurements you should perform to distinguish them as well as possible come from eigenstuff (see Nielsen and Chuang's book, for example, or basically any book on quantum information theory). By contrast, when there are $n \geq 3$ states, there is a semidefinite program that can compute the optimal distinguishing probability and the optimal measurements, but there is no known explicit/closed-form formula for it (and as far as I know, it's expected that no closed-form-ish formula exists).

Answer 3

Let there be $k$ square matrices, $A_1, A_2, \dots, A_k : \mathbb{R}^{n \times n}$, let $f$ be the monoid morphism $\{1, 2, \dots, k\}^* \to \mathbb{R}^{n \times n}$ generated by $f(i) = A_i$ for $1 \le i \le k$ (considering concatenations of strings and multiplication of matrices), and consider $g(w) = \operatorname{Tr}(f(w))$. $g$ is always unchanged by rotations of the string, but for $k=n=2$ it's also unchanged by reversing $w$. This doesn't hold when increasing either $n$ or $k$ to 3 (or more).

Answer 4

Two Variables Are Not Enough:

Let n be the smallest integer such that every closed lambda term beta converts to one with at most n bound variables. We show that n = 3.

Answer 5

$p = 2$ is often an exception in number theory to statements about primes $p$. One of the most basic and yet nontrivial examples of this phenomenon is the primitive root theorem:

For all primes $p$, there exists a primitive root mod $p^k$ for all nonnegative integers $k$ if and only if $p >2$. Moreover, for $p = 2$, there exists a primitive root mod $p^k$ if and only if $k \leq 2$. More generally, for all positive integers $m$, there exists a primitive root mod $m$ if and only if $m = p^k$, $m = 2p^k$, or $m = 4$ for some prime $p > 2$ and some nonnegative integer $k$. Thus, such an $m$ can have at most two distinct prime factors, where the second prime factor can only be $2$!

Answer 6

The Bethe lattice (infinite symmetric tree) grows exponentially for degree $\geq 3$ and at most linearly for $\leq 2$.

Answer 7

Equivalence relations with at most two classes on a fixed set $E$ have a natural group-structure (identify them with the quotient group formed by maps from $E$ into $\{\pm 1\}$ modulo constant maps (the product is multiplication of function)). No natural product exists for equivalence relations with more than two classes.

Answer 8

A 2-input gate cannot be universal for reversible computing.

A 3-input gate can. For example, the Fredkin (CSWAP) gate or Toffoli (CCNOT) gate.

Answer 9

A cardinal $\kappa$ is regular iff $\forall a (\lvert a\rvert < \kappa \land (\forall b \in a) (\lvert b\rvert < \kappa) \to \lvert\bigcup a\rvert < \kappa)$.

That is, every union of fewer than $\kappa$ sets smaller than $\kappa$ is smaller than $\kappa$.

The finite regular cardinals are exactly 0, 1, and 2.

Answer 10

$a^n b^n$ is context-free. $a^n b^n c^n$ isn't.

Answer 11

Every ideal in a polynomial ring is isomorphic (after potentially adding variables) to a trinomial ideal (i.e., one generated by trinomials). But binomial ideals are very special. See the classic paper "Binomial Ideals" by Eisenbud and Sturmfels (https://arxiv.org/abs/alg-geom/9401001).