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

Anyons exist in 2 dimensions, but not higher dimensions (due to the spin-statistics theorem).

This is connected to the fact that braid groups are trivial in higher dimensions.

Answer 2

Quadratic equations satisfy the Hasse principle while cubic equations don't.

Answer 3

The number $c_n$ of closed walks on $\mathbb Z^d$ of length $2n$ has a nice formula for $d=1,2$ (we have $c_n={2n\choose n}$ in dimension $d=1$, and $c_n={2n\choose n}^2$ in dimension $d=2$). Formulas for $d\ge 3$ are necessarily much worse, with at least a sum (see https://oeis.org/A002896).

This is linked to the fact that $[-1,1]^d$ is self-dual for $d=1,2$, but not for $d\ge 3$.

Answer 4

A subtle case where $3$ as the parameter gives a simpler result than $2$:

Consider the infinite product

$$\prod\limits_{n=2}^\infty\dfrac{n^k-1}{n^k+1},$$

which converges for all $k>1$. For $k=3$ we can use the factorizations of $a^3\pm b^3$ to telescope the product in terms of rational functions and thus guarantee a rational value, namely $2/3$. For $k=2$ a telescoping is still possible but more complicated, requiring the use of the gamma function and identities involving it to attain the result $\pi/{\sinh(\pi)}$.

Answer 5

Here is another example with Gaussian mixture models (GMMs). The landscape of loss for learning a mixture of 2 Gaussians seems to have no bad local optima but that is not the case for a mixture of 3 or more: https://arxiv.org/abs/1609.00978

Answer 6

Can one find a net of functions $(f_i)$ in the Fourier algebra of ${\rm SL}_n({\bf Z})$ such that the "amplified net" $(f_i \otimes 1)$, with $1$ denoting the constant function on ${\rm SU}(2)$, acts as an approximate identity for the Fourier algebra of ${\rm SL}_n({\bf Z})\times {\rm SU}(2)$?

The answer is positive for $n=2$ (follows from Haagerup's proof that ${\rm SL}_2({\bf Z})$ is "weakly amenable") but negative for all $n\geq 3$ (this is the statement that for such $n$, ${\rm SL}_n({\bf Z})$ does not have AP, proved by V. Lafforgue and M. de la Salle).

Answer 7

If all the roots of a (real, irreducible) quadratic are real, then they can be expressed in terms of real radicals. If all the roots of a (real, irreducible) cubic are real, then they can't be expressed in terms of real radicals.

Answer 8

On mobile now, but Gleason’s theorem needs to be on here https://en.m.wikipedia.org/wiki/Gleason%27s_theorem .

Answer 9

In reverse mathematics, some theorems that are weaker than $\mathsf{ACA}_0$ become equivalent to $\mathsf{ACA}_0$ by increasing a $2$ occurring in the statement to $3$.

An example is the infinite Ramsey theorem with finite dimension and arbitrarily many colors. Let $\mathrm R^n$ be the infinite Ramsey theorem for functions $f:\mathbb N^n\to\mathbb N$. Then $\mathsf{WKL}_0+\mathrm R^2$ is $\Pi^1_1$-conservative over $\mathsf B\Sigma^0_3$ (Slaman, Yokoyama, "The strength of Ramsey's theorem for pairs and arbitrarily many colors", 2018), in particular the theory $\mathsf{RCA}_0+\mathrm R^2$ cannot prove $\mathsf B\Sigma^0_4$, but $\mathrm R^2$ is provable in $\mathsf{ACA}_0$, so $\mathrm R^2$ must be strictly weaker than $\mathsf{ACA}_0$. However, $\mathrm R^3$ is equivalent to $\mathsf{ACA}_0$ (theorem III.7.6 of Simpson's Subsystems of Second-Order Arithmetic).

I remember hearing somewhere that strengthening weak Kőnig's lemma to include trees with labels from $\{0,1,2\}$ instead of labels from $\{0,1\}$ gives a statement equivalent to $\mathsf{ACA}_0$, but I am not able to find a source.

Answer 10

Discrete spheres: in $\mathbb{F}_2^n$ every element has a unique antipodal point at distance $n$. In $\mathbb{F}_3^n$ every element is distance $n$ from exactly $2^n$ points, so exponentially many.

Smooth spheres: In the $2$-sphere, the surface area between two lines of longitude depends only on the difference in height, and so is proportional to the area of the part of the enclosing cylinder. (As was known to Euclid.) In the $3$-sphere, the area is biggest at the equator, and smallest at the poles; the density function is $\sqrt{1-z^2}$ for $-1 \le z \le 1$.

Answer 11

For every $n \in \mathbb{N}$, there is a countable complete theory with exactly $n$ models (up to isomorphism) of cardinality $\aleph_0$, if and only if $n \neq 2$.

This is known as "Vaught's never 2 theorem".

Related reading: spectrum of a theory, Vaught conjecture.

Answer 12

The Jordan–Schönflies theorem does not hold for 3 dimensions: there is a subset of $\mathbb R^3$ that is homeomorphic to the 3-ball but its exterior is not simply connected. However, such analogous examples do not exist in 2D.

Answer 13

A two-player zero-sum game is easy to solve in polynomial time. It's essentially a convex optimization problem.

A three-player zero-sum game is PPAD-hard to solve, i.e. just as difficult as a general game and believed to require superpolynomial time. It's essentially a fixed-point problem, which is harder in general than convex optimization.

Answer 14

Two-variable logic is decidable. Three-variable logic is undecidable.

For a close study of this boundary, see An excursion to the border of decidability: between two- and three-variable logic by Fiuk and Kieroński.

Answer 15

Rationality of (sufficiently general) smooth hypersurfaces in projective space of degree $2$ (known in all dimensions) versus degree $3$ (open in all except a few dimensions).

Answer 16

Here is an example I encountered in my research:

Let $A=(a_{n, m})$ be an $N\times M$ matrix such that for all $n$ there exists $k=k(n)$ such that $a_{n,m}=0$ if $m\neq k, k+1$, that is in every row we have at most two non-zero numbers and they go one after the other, and assume that we want to know if $A$ is injective, that is whether there exists a non-zero vector $v$ such that $Av=0$. Then it is not terribly difficult to convince yourself that this can be done by only looking at which elements of the matrix $A$ are non-zero and which pairs of rows of $A$ are linearly independent and do some fairly simple combinatorics depending on this.

However, if we say that $a_{n, m}=0$ if $m\neq k, k+1, k+2$, that is if we allow for 3 consecutive non-zero elements, then the problem becomes at least as hard as the one of determining whether the Jacobi matrix is non-singular which is a subject of dozens of books and hundredths of papers, and in particular is a very difficult problem to approach analytically.

Answer 17

Let $G$ be a finite group and $K$ be a field. Consider the group algebra $K[G]$, and for $k\in \{2,3\}$ look for a largest linear subspace $X\subset K[G]$ for which $X^k=0$ (in the sense that $x_1x_2\ldots x_k=0$ for all $x_1,x_2,\ldots,x_k$ in $X$).

Theorem-2. For $k=2$, ${\rm codim}\, X\geqslant |G|/2$.

Proof. The bilinear form $(x,y)\to [e]xy$ (where $x,y\in K[G]$ and $[e]x$ means the coefficient of $e$ in the expansion of $x\in K[G]$ as a linear combination of elements of $G$) is non-degenerated, thus, if two subspaces (in our situation both subspaces are $X$) are orthogonal, the sum of their codimensions is not less than $|G|$.

Theorem-3. For $k=3$, it may appear that ${\rm codim}\, X<|G|^{0.99}$ for arbitrarily large $|G|$.

Proof. Say, for $G=C_2^n$, where $C_2$ is the cyclic group of order 2, denote the generator of $i$-th $C_2$ by $g_i$, and take for $X$ the span of elements $\prod_{i\in I} (g_i-e)$, where $I\subset \{1,\ldots,n\}$ and $|I|>n/3$. Since $(g_i-e)^2=0$ for all $i$, by pigeonhole principle we get $X^3=0$, and the codimension of $X$ is $\sum_{k\leqslant n/3} {n\choose k}<2^{0.92 n}$ by the entropy bound for binomial distribution.

This example may seem artificial, but actually the minimal codimension of the subspace with zero cube is an upper bound for many natural combinatorial characteristics of the group, like (the half of) the maximal size of a set without progressions of length 3, it is a group algebra view of the breakthrough paper by Croot--Lev--Pach.

Answer 18

Geometric theory and abstract algebra

Bisecting an angle can be accomplished with ruler and compass.

Trisecting an angle cannot be accomplished with ruler and compass.

---

Matrix theory

It is possible to construct $2$-by-$2$ Hadamard matrices.

It is impossible to construct $3$-by-$3$ Hadamard matrices.

It is possible to construct $2$-by-$2$ conference matrices.

It is impossible to construct $3$-by-$3$ conference matrices.

Answer 19

The group cohomology ring of $H^*(\mathbb{Z}/p;\mathbb{F}_p)$ is a polynomial ring when $p=2$, and a tensor product of a polynomial ring with an exterior algebra, when $p>2$. This often leads to differences so that the case of $p=2$ must be treated separately.

Answer 20

Mutual information of two random variables is non-negative and I daresay well understood. Mutual information of three or more random variables can be negative, and is monstrously unintuitive.

Answer 21

Applying Newton's method to find roots of degree 2 polynomial over $\mathbb{C}$ would produce two nice smooth basins of attraction. Doing the same for a polynomial of degree 3 would produce three fractal sets.

There's a very nice video on that: https://youtu.be/-RdOwhmqP5s?si=L4078Oc7t0Rl4E88

Answer 22

There's an important example from algorithmic complexity theory. The Boolean satisfiability problem (SAT) consists, given $n$ Boolean variables $x_1, \dots, x_n$, in asking whether we can assign truth values to these variables in a way that makes a given Boolean expression true, where the expression can use conjunction ($\wedge$, "and"), disjunction ($\vee$, "or"), and negation ($\neg$). For example, the expression

$$(x_1 \wedge \neg x_2) \vee (x_2 \wedge x_3)$$

is satisfiable: setting $x_1 = \top$, $x_2 = \bot$, $x_3 = \top$ makes it true (where $\top$ and $\bot$ denote true and false respectively). Note that variables can appear multiple times in the expression, as $x_2$ does above. In contrast, the expression

$$x_1 \wedge \neg x_1$$

is not satisfiable, as no truth value for $x_1$ can make this true.

We can consider restricted versions of SAT. The 2-SAT problem only considers expressions formed by taking the conjunction of clauses, where each clause is the disjunction of two (possibly negated) variables. For example:

$$(x_1 \vee x_2) \wedge (\neg x_1 \vee x_3) \wedge (x_2 \vee \neg x_3).$$

Similarly, 3-SAT restricts to expressions where each clause is the disjunction of three (possibly negated) variables, for example:

$$(x_1 \vee x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee \neg x_4) \wedge (x_2 \vee x_3 \vee x_4).$$

These two problems, while syntactically similar, have fundamentally different relationships to the SAT problem. Through a straightforward but clever construction, any SAT instance can be transformed into an equivalent 3-SAT instance by introducing auxiliary variables -- this is called a reduction. For example, the clause $(x_1 \vee x_2 \vee x_3 \vee x_4)$ can be replaced by $(x_1 \vee x_2 \vee y) \wedge (x_3 \vee x_4 \vee \neg y)$ where $y$ is a new auxiliary variable. No such reduction to 2-SAT exists in general.

This is already a big difference between 2 and 3, but it actually goes a lot deeper. We can algorithmically solve any 2-SAT instance in linear time by reducing the problem to finding the strongly connected components of a directed graph, making 2-SAT a problem of the class P, i.e., of problems that can be algorithmically solved in polynomial time. In contrast, 3-SAT is NP-complete. Cook's theorem (1971) showed that every problem in NP can be reduced to SAT, and the reduction from SAT to 3-SAT then implies that 3-SAT is also NP-complete. Under the assumption that P≠NP, this means that while 2-SAT can be solved efficiently, no polynomial-time algorithm can solve 3-SAT in general.

Answer 23

A finite cell complex of cohomological dimension (including twisted cohomology) $n>2$, is homotopy equivalent to a finite cell complex of dimension $n$. It is unknown if this is true for $n=2$.

Answer 24

Hilbert scheme of points on a smooth surface is irreducible. But for dimension greater than two, these are completely wild.

Answer 25

$0/1$ square matrix permanent modulo $2$ is in polynomial time but for modulo $3$ it is not.

Answer 26

$\mathbb{R}^d\setminus\{0\}$ is simply connected for $d\ge 3$, but not for $d=2$.

Answer 27

There is no infinite squarefree word on a binary alphabet, but there is one on an $n$-ary alphabet for $n>2$.

Answer 28

If you have two matroids $M_1,M_2$ with rank functions $r_1,r_2$ on the same ground set $E$, the collection $M_1\cap M_2$ of subsets of $E$ which are independent in both $M_1$ and $M_2$ is not, in general, a matroid. However, there exists a minimax formula $$\max_{A\subset M_1\cap M_2} |A|=\min_{E=E_1\sqcup E_2} r_1(E_1)+r_2(E_2)$$ It leads to a polynomial algorithm to find the largest size of a set in $M_1\cap M_2$.

For 3 matroids, no formula, and the analogous problem becomes NP-hard.

Answer 29

Application of the inverse spectral transform (IST) to the Korteweg-deVries and other non-linear partial differential equations in 2 dimensions (one space and one time) has been worked out in detail.

But 3 dimensional examples (two spatial dimensions) are much more scarce. The known examples (e.g. Kadomtsev–Petviashvili (KP) equation) have been described as "one and a half" dimensional problems, since the "soliton" solutions only involve two plane solitons interacting obliquely.

Answer 30

In dimension 2, every centrally symmetric convex polygon is a zonotope (Minkowski sum of segments). Equivalent reformulations:

$\bullet$ every 2-dimensional Banach space is a subspace of $L^1$;

$\bullet$ if $x_1,\ldots,x_n$ are vectors on the plane, $c_1,\ldots,c_n$ are real numbers and $\sum c_i|f(x_i)|\geqslant 0$ for every linear functional $f$, then $\sum c_i \|x_i\|\geqslant 0$ for every norm.

Not true in higher dimensions: an octahedron is not a sum of segments.