## Sunday, August 04, 2024

### Determing which math problems are hard is a hard problem

I was wondering what the hardest math problems were, and how to define it. So I googled

Hardest Math Problems

The first hit is here. The 10 problems given there bring up the question of  what is meant by hard?

I do not think the order they problems were given is an indication of hardness. Then again, they seem to  implicitly use many definitions of hardness

1) The 4-color problem. It required a computer to solve it and had lots of cases. But even if that is why its considered hard, the solution to the Kepler Conjecture (see here) is harder. And, of course, its possible that either of these may get simpler proofs (the 4-color theorem already has, though it still needs a computer).

2) Fermat's Last Theorem. Open a long time, used lots of hard math, so that makes sense.

3) The Monty Hall Paradox. Really? If hard means confusing to most people and even some mathematicians  then yes, its hard. But on a list of the 10 hardest math problems of all time? I think not.

4) The Traveling Salesperson problem. If they mean resolving P vs NP then yes, its hard. If they mean finding a poly time algorithm for TSP then it may be impossible.

5) The Twin Primes Conjecture. Yes that one is hard. Open a long time and the Sieve method is known to NOT be able to solve it. There is a song about it here.

6) The Poincare Conjecture. Yes, that was hard before it was solved. Its still hard. This is another issue with the list- they mix together SOLVED and UNSOLVED problems.

7) The Goldbach Conjecture. Yes, that one is hard.

8) The Riemann hypothesis is the only problem on both Hilbert's 23 problems in 1900 and on the Clay prize list. Respect! There is a song about it here.

9) The Collatz conjecture. Hard but this might not be a good problem. Fermat was a good problem since working on it lead to math of interest even before it was solved. Riemann is a good problem since we really want to know it. Collatz has not lead to that much math of interest and the final result is not that interesting.

10) Navier-Stokes and Smoothness. Hard! Note that its a Millennium problem.

NOTES

1) TSP, Poincare, Riemann, Navier-Stokes are all Millennium problems. While that's fine, it also means that there are some Millennium problems that were not included: The Hodge Conjecture,  The Birch and Swinnerton-Dyer Conjecture, Yang-Mills and the Mass gap (thats one problem: YM and the Mass gap). These three would be hard to explain to a layperson.Yang Mills and the Mass Gap is a good name for a rock band.

2) Four have been solved (4-color, FLT, Monty Hall (which was never open), Poincare) and six have not been solved (TSP, Twin primes, Goldbach, RH, Collatz, Navier-Stokes)

3) I have also asked the web for the longest amount of time between a problem being posed and solved. FLT seems to be the winner with 358 years, though I think the number is too precise since it not quite clear when it was posed. I have another candidate but you might not want to count it: The Greek Constructions of trisecting an angle, duplicating the cube, and squaring the circle. The problem is that the statement:

In 400BC the Greeks posed the question: Prove or Disprove that one can trisect an angle with a ruler and compass

is false on many level:

a) Nobody thought of prove or disprove back in 400BC (and that date is to precise).

b) Why would a compass, which helps you find where North is, help you with this problem?

(ADDED LATER: Some of the comments indicate that people do not know that point b is a joke. Perhaps not a good joke, but a joke.)

SO, when was it POSED in the modern sense is much harder to say. For more on this problem see the book Tales of Impossibility or read my review of it here.

(ADDED LATER: A comment pointed out that the constructing a trisection (and duplicating a cube and squaring the circuit) were proven impossible. I knew that but forgot to say it., and make the point of the very long time between posing and solving, so I will elaborate here:

1837: Wantzel showed that there is no way to, with a straightedge and compass, trisect an angle or duplicate the cute. This used Field Theory.

1882: Lindemann showed pi was transcendental and hence there is no straightedge and compass construction to square the circle.

So one could say it took 1882+400 years to solve the problem, but as noted above, to say the problem was posed in 400BC is not really right.)

4) Songs are needed for the other problems on this list UNION the Millennium problem. The Hodge Conjecture would be a challenge. I DID see some songs on You Tube that claimed to be about some of these problems, but they weren't. Some were instrumentals and some seemed to have no connection to the math.

5) Other lists I've seen include:

a) Prove there are no odd perfect numbers. That seems to be hard. This could have been posed before FLT was posed, but its hard to say.

b) Prove the following are transcendental: pi + e, the Euler-Mascheroni. There are other open problems here as well.

These lists make me think more carefully about what I mean by HARD and PROBLEM and even MATH.

1. I may be missing a joke, but to be clear this is the kind of compass that the Greeks were talking about: https://en.wikipedia.org/wiki/Compass_(drawing_tool)

2. I think compass is meant to be one of these: https://en.m.wikipedia.org/wiki/Compass_(drawing_tool)
(English uses the same word for the north-seeking tool and the drawing tool; this does not happen in other languages.)

3. "Why would a compass, which helps you find where North is, help you with this problem? " --> perhaps "compass" refers to the instrument used for drawing circles and arcs, not the instrument to locate the north :-)

4. Some quick thoughts:

- the impossibility of trisecting an angle with ruler and compass has been proved using field theory

- probably there are two distinct notions of "hard" one refferred to problems that have already been solved (which is more objective and "measurable"), and one referred to problems that are still unsolved

- in both cases it holds that Hardness(Solve_Problem_1) <= Hardness(Solve_Problem_1 AND Solve_Problem_2) :-)

5. “Why would a compass, which helps you find where North is, help you with this problem?” It is helpful to ensure that you don’t have your figure upside-down :-)

6. The trick is that the hardness of a math problem is NOT a question of mathematics, not even metamathematics.

It is a problem of... phenomenology!

7. (Bill) The reference to compass being a way to find north was a joke, or perhaps an attempt at a joke. However, when I was 8 years old I did wonder why they had the same word for compass (to draw circles) and compass (to find directions).

8. I believe the Twin Prime Conjecture dates back to the Greeks, in the B.C. era.

9. A compass used to draw circles, the only method available to precisely bisect angles, a prerequisite for creating a graduated magnetic compass... one of the many implausible (yet fun to conjure) reasons.

10. I see this as another unfortunate outcome of SEO spam and further evidence that search engines are unable to deliver high quality results. Apparently Google thinks that a website prominently featuring paid tutoring for children of age 7-16 is reliable enough when it comes to math that an article categorized as "Advanced Math, Grade 3, Grade 4, Grade 5, Grade 6" ranks top in its search results.