16
$\begingroup$

I recently read about the impossibility of trisecting an angle using compass and straight edge and its fascinating to see such a deceptively easy problem that is impossible to solve. I was wondering if there are more such problems like these which have been proven to be impossible to solve.

$\endgroup$

closed as too broad by RE60K, Najib Idrissi, Jack M, user147263, user21820 May 10 '15 at 7:05

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ The halting problem is one famous one, and subsequently Hilbert's goal of finding a terminating algorithm that will tell you if a theorem is true or false. But I suspect you are looking for more elementary sounding problems. Perhaps the roots to a quintic polynomial? $\endgroup$ – DanielV May 9 '15 at 6:12
  • 1
    $\begingroup$ Squaring the circle. I'm not even sure what it means geometrically but the phrase is thrown around just as often as trisecting an angle. Also, it is impossible to partition a square into an odd number of equal-area triangles. $\endgroup$ – Eoin May 9 '15 at 6:14
  • 7
    $\begingroup$ Squaring a circle means constructing a square with the same area as a given circle (given radius anyway). It was important to the original Greek mathematicians, because to them, if such a square couldn't be constructed, then it didn't exist. Those were different times. $\endgroup$ – DanielV May 9 '15 at 6:17
  • 1
    $\begingroup$ You can find an infinite number of integer solutions to $x^2+y^2=z^2.$ Apparently there aren't many integer solutions to $x^p+y^p=z^p,$ where $p=3,4,5,\dots.$ $\endgroup$ – matt biesecker May 9 '15 at 6:24
  • 1
    $\begingroup$ @mattbiesecker I don't think that is an example for this question, because not one ever seriously believed FLT was satisfiable. This question seems to be more focused on problems that "obviously" had a solution, but then they didn't. $\endgroup$ – DanielV May 9 '15 at 7:15
13
$\begingroup$

The proof that demonstrates the impossibility of trisecting an angle uses Galois theory. Galois theory can also be used to show that certain polygons cannot be constructed with compass and straightedge, and was originally used to show that, in general, polynomials of degree $\geq 5$ are not solvable.

To be specific, an $n$-gon is constructible via compass and straightedge $\displaystyle \iff n = 2^k \prod_{r=1}^m p_r$, for $k, m \in \mathbb{Z}_{\geq 0}$ and the $p_r$'s distinct Fermat primes.

Without getting into too much detail, Galois theory is a subset of abstract algebra which links together concepts in group theory and field theory, beginning with the observation that the set of automorphisms of a field forms a group. At any rate, I'm unsure of your level of background, so I'll just post a few Wikipedia links for to wet your appetite if you're interested:

Of course, there are many, many answers to your question, so I'll leave my post at that and let others have the opportunity to post more.

$\endgroup$
  • 1
    $\begingroup$ The impossibility of trisecting an angle, and the impossibility of ruler-and-compass constructions of those polygons, are done using Field Theory, but not Galois Theory – the relation between groups and fields doesn't enter into the proofs, just considerations of the degrees of various extensions. $\endgroup$ – Gerry Myerson Oct 10 '16 at 21:52
12
$\begingroup$

It is impossible to find a rational number whose square is 2.

$\endgroup$
  • 18
    $\begingroup$ I'm getting the sense that I didn't paraphrase my query properly $\endgroup$ – user34304 May 9 '15 at 11:08
  • 16
    $\begingroup$ You always have the option of editing your question to clarify what it is that you want. But it seems to me that finding a rational number whose square is 2 is exactly the same kind of deceptively easy problem as trisecting the angle with ruler and compass. $\endgroup$ – Gerry Myerson May 9 '15 at 12:09
  • $\begingroup$ I agree with Gerry. I was considered a big surprise when - some thousands of years ago - they proved this, and therefore that there are irrational numbers. $\endgroup$ – ypercubeᵀᴹ May 9 '15 at 13:34
  • 1
    $\begingroup$ I think this is a good example, because it shows that "impossibility proofs" go all the way back to Euclid. $\endgroup$ – Thomas Andrews May 9 '15 at 16:31
  • $\begingroup$ In the time of Euclid this problem might have been phrased a little more like this: "Find integers $p,q$ such that the ratio of the hypotenuse of an isoceles right triangle to its leg is $p : q$." (Only a little like this, however; for example, I don't think they had a word for "integer.") $\endgroup$ – David K May 9 '15 at 17:52
10
$\begingroup$

This answer takes a bit of background, but I think it's worth it. Please bear with me! If you already have the necessary background, you can skip to the last section for the punch line.


The surface of a sweet bun and the surface of a doughnut are both examples of two-dimensional manifolds: geometric spaces that look like planes from close up. An ant sitting on a sweet bun and an ant sitting on a doughnut see the same thing: a vast expanse of glazed pastry stretching off into the distance.

Although they don't have very good eyes, ants do have the ability to leave complicated scent trails as they walk around. Using this ability, even the tiniest ant can tell the difference between a sweet bun and a doughnut. One of the simplest ways to do this is to lay down trails that divide the surface into polygons, count the vertices, edges, and faces, and compute the Euler characteristic. With this technique, the ant can identify not only a sweet bun or a doughnut, but any pastry with a two-dimensional surface. (To make sure the ant doesn't have to walk forever, let's assume the pastry is compact—that is, finite in extent. If the pastry is infinite in extent, the ant should probably conclude that she's died and gone to ant heaven.)

To put it more technically, there's an algorithm an ant can use to identify any compact two-dimensional manifold.


There are also manifolds of other dimensions. A three-dimensional manifold, for example, is a geometric space that looks like a three-dimensional Euclidean space from close up. Our spacial universe is a classic example of a three-dimensional manifold. (In our best current cosmological models, it's the most boring one: just three-dimensional Euclidean space itself. However, it didn't have to be that way. If the density of the universe were a little bit higher, space would be curled up into the three-dimensional version of a sphere. Mark Peterson has argued, surprisingly convincingly, that the universe described in Dante's Divine Comedy has exactly this shape.)


You might guess that a clever ant should be able to identify a compact manifold of any dimension by laying down scent trails, maybe using a more sophisticated version of the technique we saw for two-dimensional manifolds. But you'd be wrong!

In 1960, Andrey Markov Jr. proved that for $n \ge 4$, there's no algorithm an ant can use to identify any compact $n$-dimensional manifold.

The reason is that an ant who could identify any compact four-dimensional manifold would also be able to identify any finitely presented group, and an ant who could do that would be able to solve the halting problem! James van Meter has a wonderful exposition of the proof, although it unavoidably requires some knowledge of abstract algebra and algebraic topology.

We've seen that compact two-dimensional manifolds can be identified algorithmically, but compact manifolds of dimension four and higher can't be. What about compact three-dimensional manifolds? As far as I can tell, we don't know! Our ant friend can certainly identify some of them, if she's willing to lug around this book, but I've never heard of an algorithm that works in general. If someone who knows more about low-dimensional topology could weigh in on this, I'd really appreciate it.

$\endgroup$
  • 1
    $\begingroup$ +1 Easy to understand and yet very much not trivial. This reminds me of obit stability, which also impossible for n>=4. Although these are probably not related (or ?). $\endgroup$ – Sanchises May 10 '15 at 20:15
  • $\begingroup$ This is a beautiful answer, definitely one of the best I've read. $\endgroup$ – Cameron Williams May 15 '15 at 4:54
  • $\begingroup$ @sanchises, I'd forgotten that the stability of Newtonian orbits depends on the dimension of spacetime! Such a cool result. I don't think it can be related to the unclassifiability of higher-dimensional manifolds, because as far as I can tell, what controls the stability of orbits is how fast the strength of gravity falls off with distance. This is a question of local geometry: the gravitational field near a tiny enough planetoid is virtually unaffected by the large-scale shape of space. That means the stability of orbits shouldn't tell you anything about the topology of space. $\endgroup$ – Vectornaut May 18 '15 at 20:57
  • $\begingroup$ (@sanchises) There could be some more subtle relationship, of course but I'd be very surprised to see one. In any case, although they may not be directly related, I'd say that the dimension cutoffs for the classifiability of manifolds and the stability of Newtonian orbits are both examples of a general phenomenon in math where things can depend sharply on the dimension of space, often in a surprising way! $\endgroup$ – Vectornaut May 18 '15 at 21:07
5
$\begingroup$

Constructing an algorithm to solve any Diophantine equation has been proven to be equivalent to solving the halting problem, as is computing the Kolmogorov complexity (optimal compression size) of any given input, for any given universal description language.

In general I think what you're looking for is either problems that are proven to be equivalent to the halting problem, or problems that are formally independent from, say, ZFC, such as the Continuum Hypothesis or more generally Gödel's incompleteness theorems.

$\endgroup$
  • $\begingroup$ In case anyone wants to learn more about why there's no general algorithm for solving Diophantine equations, a good phrase to search on is "Matiyasevich's theorem." $\endgroup$ – Vectornaut May 9 '15 at 18:16
5
$\begingroup$

One problem which I like is the Bridge of Konigsberg problem.

Bridges of Konigsberg

The challenge is to find a path that crosses each bridge exactly once.

It was eventually proved to be impossible by Euler and is considered one of the early applications of graph theory.

http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

$\endgroup$
4
$\begingroup$

There exists a set of Wang tiles for which it is undecidable whether they can tile the entire plane.

Wang tiles are nice and geometric and easily described, but you can encode each Turing machine so that the machine halts if and only if the tiles can't tile the entire plane.

$\endgroup$
  • $\begingroup$ I think you might want to reword this. The way you've written it, an algorithm to solve that problem would just be "return True" or "return False", since it only has to work for one specific set of tiles. $\endgroup$ – user2357112 May 10 '15 at 5:05
  • $\begingroup$ Undecidable and unsolvable are different things. I'm using an undecidable statement to show there is an unsolvable question. @user2357112 $\endgroup$ – Thomas Andrews May 10 '15 at 11:34
  • $\begingroup$ No, seriously. As you've stated it, the problem is decidable. The set of Wang tiles has to be an input, not hardcoded into the problem, for the problem to be undecidable. $\endgroup$ – user2357112 May 10 '15 at 19:23
  • 1
    $\begingroup$ "There is no algorithm that works for every set of tiles" is true. "There is a set of tiles without an algorithm" is false. As far as I can tell. $\endgroup$ – Akiva Weinberger May 15 '15 at 9:46
4
$\begingroup$

It's impossible to define mathematics in a way that satisfies all mathematicians.

This is likely not the answer you're after, but it stroke me when I first heard of it because definitions in mathematics are both exact and omnipresent, and I was not suspecting that providing a universal definition of mathematics itself could be such an intractable problem.

$\endgroup$
3
$\begingroup$

<< about the impossibility of trisecting an angle using compass and straight edge and its fascinating to see such a deceptively easy problem that is impossible to solve >>

This statement is false. Since it is now proved that "trisecting an angle using compass and straight edge is impossible", the problem is solved. So, the problem was not impossible to solve : it was not impossible to prove that "trisecting an angle using compass and straight edge is impossible".

Solving a problem is not necesserily giving an explicite solution, but ether giving a solution if a solution exists, or proving that no solution exists. In one of those two cases, the problem is solved. In the third case of no solution given and no prove given that no solution exists, the problem is not solved.

$\endgroup$
  • $\begingroup$ I know. What I mean is that has the impossibility of solving a particular problem been proved? $\endgroup$ – user34304 May 9 '15 at 9:20
  • 10
    $\begingroup$ This answer interprets the question too literally. Reread the question as 'Trisecting an angle with a compass and straightedge seems easy, but is in fact proven to be impossible. What other problems seem easy, but are proven to be impossible?' $\endgroup$ – Sanchises May 9 '15 at 9:32
  • $\begingroup$ @sanchises edit the question: it could help. $\endgroup$ – o0'. May 9 '15 at 13:50
1
$\begingroup$

As stated by JJacquelin, your example is wrong. However, the following theorem is impossible to solve with just the axioms of Zermelo–Fraenkel set theory:

the Cartesian product of a collection of non-empty sets is non-empty.

This led to the famous Axiom of choice being introduced (in another form) by Zermelo to address the issue. Previously, the axiom had been supposed true (implicitly) by several 19th-century logicists and mathematicians.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.