Problem Solving With a Generator and Refuter

To prove a mathematical result, you need two people: a Generator and a Refuter.

Thanks to Nathan Sheffield for inspiring many of these ideas. Thanks to Alexa Pan for running a writing exercise that gave me the idea to write this. Notes: this post is unpolished. Also, the idea described here is quite similar (maybe identical) to this idea; but hopefully it’s a somewhat different perspective on the idea.

1.

To prove a mathematical result, you need two people: a Generator (G) and a Refuter (R).

At a high level, G is responsible for generating lots of potential pathways towards a solution, and R is responsible for narrowing the focus to pathways that aren’t obviously doomed.

If G, R must be the same person, I recommend separating them somehow. For instance, you could write a paper draft as G, just intuiting what the Lemmas should be and pounding out an argument for the Lemma. Then the next day you can come in as R, confident that the paper has important mistakes; you simply haven’t found exactly where they are yet.

Having G and R separated into two people can be quite nice though---when G, R are the same person there are often context-switching costs. There’s another even larger cost: When G, R are the same person then it’s hard for R to really give their all to the search for counter-examples, because this feels like shooting down the great idea that they just generated. This can create a feeling of exhaustion: doing a good job as R creates more work for G. If you’re just R, then spotting a flaw in an argument doesn’t give you the responsibility of fixing the flaw. You don’t need to think about how to fix it at all, just notice that it’s there.

When having G, R be two separate people it’s good to explicitly communicate that you want to use the GR approach. Without such communication, G might get deflated and stop proposing ideas. The G-R relationship is not supposed to be adversarial. G is not offended, or even surprised really, when R points out that an idea doesn’t work. G may even be relieved to have idea space pruned a bit.

I’ll focus on the case where G and R operate on a concrete math conjecture such as “Conjecture: there is an in-place (i.e., you only get logarithmic memory in addition to the memory that the input is written on; you overwrite the input with the output) algorithm for multiplying two numbers”. But the G-R approach can be extended to problems with fuzzier success criteria.

2.

The process of solving the mathematical question generally starts with G creating the simplest possible version of the problem in question.

The turn then goes to R, who looks for counterexamples to this simple conjecture. When searching for counterexamples to a conjecture it’s important to take the conjecture seriously. By which I mean: R should mercilessly optimize for disproving the conjecture. If there is some parameter regime where the conjecture is particularly questionable, R should focus on that parameter regime. If there are small somewhat degenerate cases that aren’t ruled out by the problem statement, R should try these as potential counter examples.

Some might say that R isn’t playing fair here. After finding such counterexamples, the G might complain that R’s counterexample doesn’t really their core hope. That’s fine. This is a great opportunity for G to generate a modified conjecture that isn’t addressed by the counterexample.

Taking the rules seriously, i.e., no-holds-barred optimizing for a counterexample is a good idea, because it means that you’re directly optimizing for something not confusing. This no-holds-barred optimization is often the quickest way to refine a conjecture into something that’s actually correct. In other cases, this kind of optimization can make you quickly realize that the thing that you wanted cannot exist, and thus can save you a ton of time.

3.

Once R has tried to find counterexamples to the conjecture for a time to no avail, G steps in to start generating again.

G generates more statements which feel vaguely similar to the original statement, and which are also simple. G recalls relevant results from the literature that are kind of similar.

G then picks a conjecture of interest, and generates a conjecture which both might plausibly be true, and might plausibly be useful for establishing a larger conjecture of interest.

G then hands this conjecture to R for a round of counterexample searching. This process, of generating and refuting conjectures is central to solving the problem, and to focussing the search for a solution into productive places.

4.

Now, once a simple conjecture has withstood R’s attempts at refutation for a while, we are ready for the next phase: G actually tries to prove this conjecture.

G tries the simplest possible things first. If G is trying to establish the existence of an object, G tries a random instantiation of the object (if that makes sense). If there’s some construction that worked for a different problem, G just proposes that we use the exact same construction as before, possibly with a modification or two as required by R’s refutations.

If an extremely simple technique works, and this feels “unsatisfying”, then it might be the case that the conjecture was too weak, and G can choose to increase the strength of the conjecture.

When finding errors in G’s claims, R should distinguish between local and global errors (h/t Terry Tao for this terminology). A global error is a counter-example to the entire approach. When possible it’s great for R to focus on finding global errors, because these are clearer to adjudicate. R is certainly allowed to object to more local steps though, and is encouraged to sometimes do so on heuristic grounds.

In early stages of trying to solve the problem, it’s often productive to temporarily grant lemmas if G is excited about pushing on a particular part of the problem.

5.

At the stage of solving a problem where you’re trying to write down your work in a way that is possible to communicate to other people, it’s really important to strive to have good lemmas. Scoping out what the key lemmas roughly should be is a good exercise for G when possible.

When R is reading a proof to try and understand if it’s correct, it’s a totally valid move for R to state: “I’m confused”. When R is confused like this, it can sometimes be helpful to first work through the proof in a really simple example.

But in a good proof, the truth-value of the final statement should feel obvious. To make the final statement feel obvious, it’s probably a good idea to have about 3 main lemmas. Each of the lemmas should make sense on its own. Ideally each lemma is intuitively plausible; for example, there might be simple heuristics which imply the lemmas. The derivation of the main result from the lemmas should also be simple.

Lemmas must be modular. It’s totally not kosher to use ideas that have fallen out of scope from the part of the argument where you introduced them.

Conclusion

In this post I’ve given a story for what the process of solving a math problem with a G-R approach might look like. Are these tools more broadly applicable?

Sure.

• Suppose you were writing a research project proposal. It seems productive to separate out the idea generating mode and the idea pruning modes.
• Suppose you are working on an empirical ML research project, and aren’t sure what to do next. It seems helpful to first generate a bunch of ideas and then prune down to the ones that are actually worth trying.
• The methodology seems quite helpful if you’re trying to answer a confusing conceptual question.
• The approach seems helpful for improving interpersonal relationships (generate ideas for how to improve, then prune to the most promising ones).