Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working on a project presentation and would like to illustrate that it is often difficult or impossible to estimate how long a task would take. I’d like to make the point by presenting three math problems (proofs, probably) that on the surface look equally challenging. But…

  • One is simple to solve (or prove)
  • One is complex to solve (or prove)
  • And one is impossible

So if a mathematician can’t simply look at a problem and say, “I can solve that in a day, or a week, or a month, how can anyone else that is truly solving a problem? The very nature of problem solving is that we don’t know where the solutions lies and therefore we don’t know how long it will take to get there.

Any input or suggestions would be greatly appreciated.

share|improve this question
10  
How about Fermat's Last Theorem? We can find a, b, c such that $a^2 +b^2=c^2$, so that's easy. But for higher exponents.... –  The Chaz 2.0 Dec 6 '11 at 0:13
4  
We could also prove that 2 is irrational, but various results for $e$ and $\pi$ are known to be unknown –  The Chaz 2.0 Dec 6 '11 at 0:14
4  
@Emmad: This, this, and this beg to differ. –  J. M. Dec 6 '11 at 0:58
2  
"...it is often difficult or impossible to estimate how long a task would take." Just for fun, you might reference Hofstadter's Law. –  Austin Mohr Dec 6 '11 at 1:01
2  
@Emmad - Building a car is very different to designing a car. In software development, there's some disagreement over where the line between design and construction lies - see martinfowler.com/articles/newMethodology.html for an unconventional but compelling view. The same is probably true in mathematics - there's "design" (new models, proofs etc) and "construction" (following standard procedures). The latter may be fairly predictable, but the former clearly isn't. –  Steve314 Dec 6 '11 at 6:04

11 Answers 11

up vote 169 down vote accepted

This isn't exactly what you're asking for, but it should serve the same purpose very nicely.

Hilbert gave a talk in 1920 or so in which he discussed the difficulty of various problems.

He said that great progress had been made in analytic number theory in recent years, and he expected to live to see a proof of the Riemann Hypothesis.

Fermat's Last Theorem, he said, was harder; maybe the youngest members of his audience would live to see a proof.

But the problem of determining whether $2^{\sqrt2}$ is transcendental was so hard that not even the children of the youngest people in the audience would live to see a solution to that one.

With the benefit of hindsight, we can see that Hilbert had it exactly backwards.

$2^{\sqrt2}$ was settled in 1929 - Hilbert lived to see it.

Fermat, as we know, held out until the 1990s.

And the Riemann Hypothesis is still unsettled.

The point of the story is not to make fun of Hilbert. The point of the story is that if even Hilbert, the strongest mathematician of his era, could be so wrong in judging the relative difficulty of various mathematical problems, then it must be a really hard thing to do - which, I think, is the point you are trying to make.

share|improve this answer
12  
This is a great answer. It can be appreciated by a general audience even if people don't know what Fermat's last theorem or the Riemann hypothesis are about. –  KCd Dec 6 '11 at 4:52
4  
Gerry, the irrationality of $2^{\sqrt{2}}$ probably should be replaced by its transcendence, since Hilbert's 7th problem was about transcendence of such numbers. –  KCd Dec 6 '11 at 5:02
    
@KCd, yes, transcendence would be better. –  Gerry Myerson Dec 6 '11 at 5:28
1  
@Marvis, it could be that Hilbert just thought RH was more important than the other problems. Or it could be that developments during the years between the two quotes caused him to change his mind about the difficulty. Or it could be that Hilbert wasn't fettered by consistency, the hobgoblin of small minds. –  Gerry Myerson Jun 15 '12 at 11:33
2  
Just in case somebody is interested: $2^\sqrt{2}$ is irrational and a transcendental number. It is called Gelfond–Schneider constant. –  moose Sep 12 '12 at 6:09

For an integer $n$, let's seek integral solutions of $x^3 + y^3 + z^3 = n$.

1) When $n = 29$ a solution is easy to find: $(x,y,z) = (3,1,1)$.

2) When $n = 30$ it is harder to find a solution, but one is known: $$ (x,y,z) = (2220422932,-2218888517,-283059965). $$ This was found in 1999. (For more on this, see section 3.2 of N. Elkies, "Rational points near curves and small nonzero $|x^3-y^2|$ via lattice reduction", ANTS 2000, pp. 33--64.)

3) When $n = 33$ we expect there is a solution but none is currently known as far as I am aware.

share|improve this answer

One set that (I think) meets your requirements and for which the statements are accessible to many:

  1. Prove that $\sqrt{2}$ is irrational
  2. Prove that $e$ is irrational
  3. Prove that $e+\pi$ is irrational
share|improve this answer
3  
Is 3. "impossible"? –  Quinn Culver Dec 6 '11 at 4:34
1  
I might be mistaken, but I thought the sum of two irrational numbers was always irrational. If that's not true, can you give a counterexample? –  Peter Olson Dec 6 '11 at 4:54
2  
@Quinn, not necessarily. But it's an unanswered question to date. –  alex.jordan Dec 6 '11 at 4:56
30  
@Peter How about $\sqrt{2}+(-\sqrt{2})$? Or if you'd prefer $\sqrt{2}+(1-\sqrt{2})$. Basically, rational numbers make a vector subspace of $\mathbb{R}$, and irrationals just make the complement. There are always lots of ways to add two things from the complement of a subspace and land inside the subspace. –  alex.jordan Dec 6 '11 at 4:57
8  
@Gerry Yes, I mean $\mathbb{R}$ as a $\mathbb{Q}$-vector space. I really just want to put it out there that when "subthings" are additively closed, complements of "subthings" are usually not. –  alex.jordan Dec 6 '11 at 6:38

A famous example, although it might require more background than you'd like, is Burnside's problem, which asks the following: if a group is finitely-generated and has the property that every element has order $n$ for some fixed positive integer $n$, is it necessarily finite?

  • For $n = 2$ the answer is yes by a straightforward argument. If $a, b$ are two elements of the group, then $a^2 = b^2 = (ab)^2 = e$ implies $ab = ba$, so the group is abelian and has order dividing $2^m$ where $m$ is the number of generators.
  • For $n = 3, 4, 6$ the answer is still yes, but the argument is more difficult.
  • For $n = 5$ the problem is still open! (I think. According to Wikipedia, at the very least the specific case of two generators is still open.)
share|improve this answer
    
Would definitely require more background than what my intended audience will have, but it is a great example. Thank you! –  Judy Dec 6 '11 at 15:48

It's easy to multiply two 20-digit prime numbers, but what if you had to factor their product? There you have an easy problem and a hard problem.

share|improve this answer
15  
It's not easy to multiply two 20-digit numbers by hand. It is easy to multiply two 20-digit numbers by computer, but it's also easy to factor a 40-digit number by computer. Change that 20 to 200 and I think I'll go along. –  Gerry Myerson Dec 6 '11 at 5:34
16  
I believe I could multiply two 20-digit prime numbers by hand within a couple of hours, but I could not factor their product. –  Michael Hardy Dec 6 '11 at 18:52
11  
You overestimate the difficulty of multiplying by hand, I think. It’s 400 single-digit multiplications plus 40 sums of no more than 21 numbers. Shouldn’t take more than 15 or 20 minutes, by my reckoning. –  Jon Purdy Dec 8 '11 at 13:25
2  
Well, I said "within". I was being cautious. So I can do that, but I can't factor the product by hand. –  Michael Hardy Dec 8 '11 at 17:30

Take a look at the suggestions and the comments of each one.

Suggestions:

1 - $x^{x^{x^{x^{\cdot^{{\cdot}^{\cdot}}}}}}=2$, Solve for $x$.

2 - Poincaré conjecture (Every simply connected, closed 3-manifold is homeomorphic to the 3-sphere.).

3 - The Continuum Hypothesis (First Hilbert problem). This question is indecidible.

Comments:

1 - This problem looks a very hard one. How to find $x$ when we raised it to it infinite times and this should be equal to $2$.

The truth is this problem could be solved on a "easy" way. See this my own question.

2 - This question is a very hard one. It has proved by Grigori Perelman. See this link for more details.

3 - This question is "impossible" because is indecidible and find a final answer isn't possible. Reference.

share|improve this answer
    
To be more precise: Perelman proved Thurston's conjecture; Poincaré drops out as a side result. –  J. M. Dec 6 '11 at 18:46
7  
+1 for only person to mention a problem that is actually "impossible" (as opposed to all the others who listed open problems) –  BlueRaja - Danny Pflughoeft Dec 7 '11 at 21:28
    
Thx @BlueRaja-DannyPflughoeft . I really like these problems, I think they are very interesting ones. –  GarouDan Dec 7 '11 at 21:31
3  
@PaulOstrowski, $\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\ldots}}}=2$. So, that question have a solution. –  GarouDan Dec 8 '11 at 22:22
2  
@PaulOstrowski, you're wrong. This converge to 2. Take a read in this wikipedia article. –  GarouDan Dec 9 '11 at 19:13

What positive integers can be written as the sum of two squares? Sum of three squares? Sum of four?

For two squares, it's all positive integers of the form $a^2b$, where $b$ isn't divisible by any prime of the form $4k+3$, and the proof is easy.

For four squares, it's all positive integers, and the proof is moderately difficult, but covered in any course on number theory.

For three squares, it's positive integers not of the form $4^a (8b+7)$ and, while not impossible, the proof is considerably more difficult than the previous two.

share|improve this answer

Irrationality of the Riemann zeta function at integer values.

$\zeta(2)$ is irrational. This won't be an obvious fact to those without a mathematics background, but most mathematicians are familiar with a proof that $\zeta(2)=\frac{\pi^2}{6}$. (And there are similar statements for the zeta function of even integers).

$\zeta(3)$ is irrational. Known, but not until 1978. Here we have irrationality, but no closed expression in terms of well-understood constants. (Nor, to my knowledge, is there any reason to expect such an expression to exist).

$\zeta(5)$ is irrational. Open. We know that $\zeta(2k+1)$ is irrational infinitely often, and least one of $\zeta(5)$, $\zeta(7)$, $\zeta(9)$, and $\zeta(11)$ is irrational.

(See this post for links to more details. The Wikipedia article on Apéry's Theorem also lists some results.)

share|improve this answer

Sometimes a problem which seems very hard turns out to be "easy" because someone was clever enough to look at it in just the correct way. Two examples of this:

a. Construct lots of non-homiltonian planar 3-valent 3-connected graphs (such graphs can be realized by convex 3-dimensional polyhedra) The Grinberg condition provides a nifty approach to finding such graphs easily: http://en.wikipedia.org/wiki/Grinberg%27s_theorem

b. Klee's art gallery problem: find the number of vertex guards that are sometimes necessary and always sufficient to "see" all of the interior of a plane simple polygon with n vertices. V. Chvatal and Steve Fisk found simple ways to answer this question: http://en.wikipedia.org/wiki/Art_gallery_theorem

share|improve this answer

Have you considered the famous classification of all finite simple groups? See here for the history of this effort. In addition and intimately related, the conjecture of Burnside (1911): every finite group of odd order is solvable (or equivalently: every finite simple group has even order), which was settled by Walter Feit and John Thompson in 1963.

share|improve this answer

This famous pell equation $$\Large{ 61 x^{2} + 1 =y^{2}}$$ has an trivial solution $(0,\pm{1})$. But if you were to look out for positive integral solutions then the smallest positive integral solution is given by $(226153980,1766319049)$. More on this here at this link

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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