What are some lesser-known examples where increasing the dimensionality makes the problem easier to solve? [duplicate]

I feel like there is a common pattern in mathematics where increasing the dimensionality makes the problem easier to solve or provides a solution where otherwise one would not exist. Some examples:

• Going from real numbers to complex numbers
• Working with quaternions (4D) instead of (roll, pitch, yaw) or rotation matrices which have singularities
• Laplace transform which lets us solve differential equations with algebra (ok this isn't really increasing the dimensionality, more like working in a different dimension)

I'm not a mathematician but I imagine this appears in other areas. What else is there? Is there a "method" or systematic way for increasing the dimensionality of a problem to make it easier to solve? Bonus if there is something in the field of optimization and/or linear algebra, which I am most interested in at the moment.

Solution 1:

In dimensions greater than $4$ there are only three regular polytopes: the simplex, the hypercube and its dual the cross polytope. There are infinitely many in the plane, five in three dimensions and six in four.

The Poincare conjecture was settled for dimensions greater than $3$ well before it was settled for $3$.

Solution 2:

Desargues' Theorem (link to Wikipedia page) is a theorem of projective geometry which in-some-sense requires a higher-dimensional argument. I will attempt to explain.

There are two senses in which one can use the phrase "projective plane". One can consider "the projective plane over a (given) division ring" (more commonly over a field, a special case), which is a certain algebraic construction and essentially requires a choice of coordinates; this is the analytic approach. One can also consider a projective plane to be any collection of objects which satisfies a certain list of axioms; this is the synthetic approach. The points and lines in projective plane in the analytic sense satisfies the axioms of the synthetic approach, hence the name.

Desargues' Theorem holds in the analytic approach, and can be proved very cleanly by "going one dimension up". See the proof at Wikipedia. In rough: because the theorem is all about the geometry of perspective, it makes sense to think about it by imagining the image on the plane as being an image, drawn in perspective, of an actual construction in 3D space.

However, when it comes to planes in the synthetic sense, there exist examples of "non-Desarguesian planes" (link to Wikipedia page). So there exist projective planes in which the theorem doesn't actually hold; nevertheless, it is possible to recover the theorem by applying more restrictions to the plane. However, to quote Wikipedia (and this sentence has three reputable citations): "These conditions usually take the form of assuming the existence of sufficiently many collineations of a certain type, which in turn leads to showing that the underlying algebraic coordinate system must be a division ring (skewfield)."

In other words, the way to get back Desargues' Theorem in the most general synthetic sense is to apply conditions such that your projective plane is actually constructible in the analytic sense; and then the proof is to go one dimension up!

Solution 3:

Is there a "method" or systematic way for increasing the dimensionality of a problem to make it easier to solve?

No, there cannot be a systematic method to even identify when this is possible, nor efficiently find the way even if guaranteed to be possible. I just wanted to address this since the other answers did not do so. Since "increasing the dimensionality" is a vague concept, my statement is vague too, but if you attempt to make your question precise, very likely the answer will really be "no", for reasons of computable undecidability of optimization problems of this kind (i.e. "is there a solution shorter than ...?")

That said, I would consider this heuristic of lifting to higher dimension to be merely a special case of the more general heuristic of reparametrization. As you noted, reparametrization can be really very useful. An illustrative example is the solution to the egg-dropping puzzle. Some examples of actual lifting relevant to optimization can be found in this 2003 workshop talk by Parrilo and Lall.