Interesting Problems at Small Values

This post is based on the observation that, in a variety of fields (e.g. logic, computics, mathematics, physics), while certain classes of problems can be parameterized by some natural number nn, it appears that the interesting problems―not so simple as to be trivial, but not so complex as to be unsolvable, undecidable, intractable, or nonexistent―always occur at small nn. Below is a collection of such problems, describing at which nn they are interesting, and how so.

A Summary

  • First-order predicate logic
  • Rank-1, rank-2 polymorphic lambda calculus
  • System F3_3
  • 3-SAT, 3D matching, graph 3-colouring
  • (Semi)regular polytopes in 3D and 4D
  • Exotic R4\mathbb{R}^4 and exotic 4-spheres
  • 2-body problem
  • Stable bound orbits in 2D and 3D


Higher-order logic can be stratified into nn​th-order logics, beginning with propositional logic (n=0)(n = 0), first-order logic, second-order logic, and so on. As opposed to propositional logic, first-order logic can simulate computation (either by encoding a Turing machine as a formula or by representing recursive functions in a sufficiently rich arithmetic theory), and is therefore undecidable. However, FOL is both compact and admits a sound and complete finitary proof system, whereas second-order and higher-order logics do not. Therefore, FOL is interesting by being sufficiently complex while still well-behaved.


Polymorphic Lambda Calculus

The polymorphic lambda calculus System F can be stratified into systems of rank-​kk polymorphism, where forall quantifiers are restricted to no more than kk arrows deep on the left (e.g. ((∀ a. a → t1) ... → tk)). Beyond rank-1 (prenex or Hindley–Milner) and rank-2 polymorphism, type inference and type checking is undecidable [1], which makes these interesting in terms of practicality. Rank-0 polymorphism is essentially STLC (i.e. nonpolymorphic), where type inference and type checking are trivially decidable.

The higher-order polymorphic lambda calculus System F_ω\_{\omega} can be stratified into levels as well, where System F1_{_1} corresponds to STLC, System F2_2 corresponds to System F above, and System Fk_k allows type constructors with argument types of kind level (k1)(k - 1). While there exist (Curry-style) lambda terms that cannot be typed in F2_2 but can be typed in F3_3 and above [2, 3], it is conjectured [4, 5] that all terms typeable in F3_3 and above are also typeable in F3_3 itself; there is a supposedly incorrect proof of this [6]. This is not to say System F3_3 and above are uninteresting because they are too complex; in fact, it is interesting precisely because higher orders of polymorphism may collapse to F3_3. This is similar to NP-complete problems below, where classes of problems parametrized by nn are all NP-complete for n3n \geq 3.

Computational Complexity

There are many decision problems parametrized by nn whose complexity is NP-complete only for n=3n=3 or possibly higher. Here are three classical problems that are usually encountered. I won’t list any more simply because there are far too many of their kind.

  • n-SAT: Given a formula in conjunctive normal form where each clause has nn literals, is there an assignment of truth values to its variables such that the formula is satisfied? In 0-SAT, the answer is trivially yes; 1-SAT and 2-SAT are in P, while 3-SAT and higher are NP-complete.

  • n-dimensional matching: Given a natural number kk, nn finite disjoint sets, and a subset TT of their Cartesian product, is there a subset MM of TT such that M>k\|M\| > k and the elements of the tuples of MM are disjoint? 1D matching is trivial and 2D matching (bipartite matching) is in P, while 3-SAT and higher are NP-complete.

  • Graph k-colouring: Given a graph, is there a way to assign each node one of kk colours such that no two nodes of the same colour share an edge? 1-colouring is trivial and 2-colouring is in P, while 3-colouring is in NP. Interestingly, for 4-colouring the answer is always yes.


In mathematics, there appear to be many interesting structures in four-dimensional space. This is a vastly incomplete list; there are, as far as I know, some unique properties of 4D space to do with n-spheres as well.


In nn dimensions, there exist at least the following regular polytopes: the simplices, (with (n+1)(n+1) faces of (n1)(n-1)-dimensional simplices), the quadruplices (with 2n2n faces of (n1)(n-1)-dimensional quadruplices), and the orthoplices (with 2n2^n faces of (n1)(n-1)-dimensional simplices). In 0D and 1D, these all collpase to the trivial point and line, respectively. In 2D, there are infinitely many regular convex and star polytopes (polygons and stars). For dimensions greater than 4, there are no other regular polytopes. However, in 3D and 4D, there exist other regular polytopes than the three categories above. In 3D, the convex polyhedra are the icosahedron and the dodecahedron, and the star polyhedra are Kepler–Poinsot polyhedra. In 4D, the convex polychora are the 120-cell (corresponding to the dodecahedron), the 600-cell (corresponding to the icosahedron), and the 24-cell (with no 3D counterpart), while the star ones are Schläfli–Hess polychora.

Similarly, in nn dimensions, there exist at least the following semiregular polytopes: the k21k_{21} polytopes, and the regular polytopes as described above. In 0D, 1D, and 2D, the semiregular polytopes are exactly the regular polytopes. For dimensions greater than 4, there are no other semiregular polytopes. However, in 3D and 4D, there exist other regular polytopes than the k21k_{21} polytopes. In 3D, these are the prisms, the antiprisms, and the 13 Archimedean solids (excluding enantiomorphs). In 4D, these are the rectified 600-cell (analogous to the icosidodecahedron) and the snub 24-cell.


Exotic smooth structures on Rn\mathbb{R}^n are smooth topological manifolds that are homeomorphic but not diffeomorphic to Rn\mathbb{R}^n. It was shown by Stallings [7] that no such structures exist for n4n \neq 4, while it was shown by Taubes [8] that uncountably many exist for n=4n = 4. Similarly, exotic piecewise-linear structures on the nn-sphere are not PL-homeomorphic to the nn-sphere. The generalized PL Poincaré conjecture states that there are no such structures; this holds true for n4n \neq 4, but it is yet unknown whether this holds for n=4n = 4 (see [9]).


There are a few observations that point out the uniqueness of three spatial dimensions (and possibly two as well), usually as arguments for the anthropic principle.

In three dimensions, the gravitation potential is propotional to 14\frac{1}{4} (see below). The nn-body problem asks for a general closed-form solution to the paths of nn bodies mutually attracted by the gravitational forces due to this potential. A general solution exists only for 2 bodies; with 3 or more bodies, no general solutions exist, although there are many special periodic cases.

Gravitation and Electromagnetism

Given a potential field described by Poisson’s equation, the fundamental solution in dd dimensions is a potential propotional to 1rd2\frac{1}{r^{d-2}} (or to ln(r)\ln(r) for d=2d = 2), where rr is the distance from the source. This potential applies to Newtonian gravitation and classical electrodynamics. In only d=2d = 2 and d=3d = 3, there exist stable bound orbits (circular or elliptical); the concept of an orbit is undefined in fewer dimensions. The original result by Ehrenfest [10] (and reëxpressed by Freeman [11] in English) showed that bound planetary orbits and the Bohr model are not stable for d>3d > 3.

This has been generalized by Tangherlini [12] to a Schwarzschild field (due to a nonrotating, uncharged mass), with the result that stable bound orbits still do not exist in d>3d > 3. Since the Schwarzschild metric is a special case of other metrics (Kerr, for rotating masses; Reissner–Nördstrom, for charged masses; Kerr–Newman, for rotating, charged masses), it is not expected that these will have stable bound orbits in d>3d > 3 either. There probably are papers that deal with them explicitly.

On the other hand, it was shown [13] that bound states of a single electron in a 1rd2\frac{1}{r^{d-2}} potential using the Schrödinger equation do exist for d>4d > 4. As relativistic effects are usually small corrections, it would be expected that special relativistic equations (e.g. Dirac, Klein–Goron, Proca) would also yield the same results. But then we would delve into the world of quantum field theory and have to consider the strong force, the weak force, and Lagrangians, which is beyond the scope of this post. As a subaside, Tegmark [14] argues for the impossiblity of more or less than one time dimension.

[1] Kfoury, A. J. and Tiuryn, J. “Type Reconstruction in Finite Rank Fragments of the Second-Order λ-Calculus”. (1992). Information and Computation, 98:2, pp. 228–257.


[3] Giannini, P. and Della Rocca, S.R. “Characterization of typings in polymorphic type discipline”. (1988). Third Annual Symposium on Logic in Computer Science, pp. 61–70.


[5] Giannini, P., Honsell, F., and Ronchi Della Rocca, S. (1993). “Type Inference: Some results, Some problems”. Fondamenta Informaticae, 19:1–2, pp. 87–125.

[6] Malecki, S. (1997). “Proofs in system Fω can be done in system Fω1”. International Workshop on Computer Science Logic, pp. 297–315.

[7] Stallings, J. (1961). “The Piecewise-Linear Structure of Euclidean Space”. Proceedings of the Cambridge Philosophical Society, 58:, pp. 481–488.

[8] Taubes, C. H. (1987). “Gauge Theory on Asymptotically Periodic 4-Manifolds”. Journal of Differential Geometry, 25:3, pp. 363–430.

[9] Freedman, M., Gompf, R., Morrison, S., Walker, K. (2010). “Man and Machine Thinking about the Smooth 4-Dimensional Poincaré Conjecture”. Quantum Topology, 1:2, pp. 171–208.

[10] Ehrenfest, Paul. (1920). “Welche Rolle spielt die Dreidimensionalität des Raumes in den Grundgesetzen der Physik?”. Ann. Phys., 366:, pp. 440–446.

[11] Freeman, Ira M. (1969). “Why is Space Three-Dimensional?”. American Journal of Physics, 37:12, 1222–1224.

[12] Tangherlini, F. R. (1963). “Schwarzschild field inn dimensions and the dimensionality of space problem”. Nuovo Cim, 27:3, pp. 636–651.

[13] Caruso, F., Martins, J., and Oguri, V. (2013). “On the existence of hydrogen atoms in higher dimensional Euclidean spaces”. Physics Letters A, 377:9, pp. 694–698.

[14] Tegmark, Max. (1997). “On the dimensionality of spacetime”. Classical and Quantum Gravity, 14:4, pp. L69–L75.