How to actually come up with mathematical resultsAutor: Timo Kötzing
How do we go about finding mathematical results? What best practices, what approaches do we take? Can we make the process of science more explicit? George Pólya, in 1945, published the book How to solve it, where he already gives a number of hints for solving mathematical problems. This page gives sometimes similar, sometimes different concrete advice.
- Monster block
- Monster adjustment
- Sanity check
Propbably the most imortant approach: Work on many different problems, don't get stuck on a single big problem; something will work. You pluck the low-hanging fruits, gain a basic understanding and confidence for harder problems.
Maybe you start out with one question, but when working on the proof you find a solution for a slightly different problem. Congratulations! You now have proved something, your original problem morphed into one you can actually solve.
3. Monster block
This technique was described by Lakatos in his work Proofs and Refutations. He writes that when you cannot prove a theorem in all cases you would like it to hold, exclude cases. Maybe irrelevant cases, maybe unimportant cases. Maybe the cases blocked out are important, but at least you have a theorem for some important cases.
4. Monster adjustment
Also this technique was described by Lakatos in his work Proofs and Refutations. Maybe the theorem you try to prove does not hold generally, but maybe you can relax the conclusion so that (a) for important cases the conclusion is just as strong as originally intended and (b) it now holds generally. For example, one could want to show that the run time of some algorithm is \(O(n^2)\), but in the end it is just \(O(n^d)\), where \(d\) is the dimension of the underlying vector space; this way the important 2-dimensional case is proven as desired, and all other cases also have a result.
See the works and comments by Erdős. Write down what you believe could be true; write down good intuitive reasons for why this should be true. Now you have something to work on and to work with.
6. Sanity check
Does your conjecture imply false statements? Or does it fit nicely with other things you know about your subject? Can you make a computer simluation / plot to show that it holds for specific cases? Maybe you can see from these results that it probably holds more generally?
When trying to prove a conjecture, at the same time try to disprove it, even if you firmly believe in your conjecture: The attempt to disprove it might show you where the attempted proof for the opposite breaks, then you know what to exploit in your proof.
Difficult problems usually cannot be tackled directly; instead, one should try to build some intuitions in order to understand the object of study better, to find a suitable approach for the problem.
Especially when in a large landscape or with far away targets, make general statements about your subject of study. Slowly progress in the direction of your problem. Give structural insights and lemmas, write formulas and name them.
A second way of exploration is to make rough estimates before tackling your goal precisely. What is the rough run time of an algorithm, or a weak bound on for an arithmetic espression? How much do you think did you lose in this estimate? Also, make plots and zoom around in them in order to get a feel for what's going on.
A third way to explore is to run experiments. Is there a small counterexample to your claim? Is there a property that many small examples exhibit? Does a search heuristic always stay clustered or does it spread? This can help build valuable intuitions.
You can prove a special case of your theorem. On the one hand, you now already have a prove for something. On the other hand, you might now understand your problem better. Maybe you can even generalize the proof; for this, you sometimes want to show several special cases.
Already just because our brains cannot hold an unlimeted amount of information, simple statements are easier to grasp and solve than more complicated ones. Can I simplify my problem? Maybe I strengthen my assumptions just a bit so that it is simpler. Maybe even weakening it would make it simpler and maybe even easier to prove (this happens: instead of proving a special case, proving a general theorem which exhibits the actual problem can be much easier). Sometimes I can make use of normal forms: instead of working on arbitrary DFAs, maybe it is useful to work on canonical DFAs? It keeps the generality while giving me some additional assumptions to work with.
Once you found a proof, analyze it! Can you simplify it? Do you need all your restrictions, or does the proof hold more generally? Does a modification of the proof solve a variant of the problem of independent interest? These questions help you make the most of your efforts.
I want to thank Martin Krejca for help with this page as well as Pascal Lenzner for additional best practices.