58
$\begingroup$

May seem strange as I'm good in programming, but I just started diving into math. ATM I'm learning combinatorics at Khan Academy, and here's an example of a question that I struggled with (that's not the question):

The answer to «ways of getting $1$ head in $4$ flips» is $4$ (HTTT, THTT, TTHT, TTTH). But let's put it the other way round: «ways of getting $3$ tails in $4$ flips» (which is, obviously, the same question). It would be the number of places to put it: $4×3×2 = 24$, next divided by 3 to remove duplicates (i.e. TTTH is counted $3$ times): $24/3 = 8$. But $8 ≠ 4$! We used right calculations, reasoning, and got absolutely different answer, how is that possible?

I thought: there must be generic ways of debugging math problems, i.e. not just directly solving, but rather finding the problem when everything supposed to work, but it doesn't. I tried searching, and to my surprise found nothing, like nobody ever asked the question. Well, here's mine:

What are common ways to debug math problems; both generic and specialized would be nice to know. If you know any relevant articles, I'd be glad to read it too.

$\endgroup$
  • 45
    $\begingroup$ You should divide by $3!$, not by $3$ (I would end this statement with an exclamation mark, but that would make it a little ambiguous). $\endgroup$ – barak manos May 3 '16 at 9:40
  • 6
    $\begingroup$ You didn't find anything because "debug math" is a funny way to put it :-) Much better would be "finding the error" or "how to be sure a proof is correct". In a software, you make a mistake somewhere. You keep looking at every part of the code until you find the problem. In math you keep looking at every part of an argument until you find the problem. There are no shortcuts or methodologies: Keep looking until you find the error.If you wrote "debug" with the idea that you can find some parallels like unit testing or whatnot, well there aren't $\endgroup$ – Ant May 3 '16 at 9:44
  • 4
    $\begingroup$ I would rather say that there are no "generic shortcut", but if you know your area of math pretty well and have a little experience, you start to know what the common mistakes can be, and what kind of mistake can cause such and such final error. But that's all very dependant on a specific subject. $\endgroup$ – Captain Lama May 3 '16 at 9:47
  • 2
    $\begingroup$ Also worth noting that the quote is a little misleading: You didn't use "used right calculations, reasoning"; they were in fact wrong. It just seems to be true, but it is not (and this is why proofs are important!). As @barakmanos says, you should be dividing by $3! = 3 \cdot 2$ instead of only $3$.This is because you're not only counting $TTTH$ three times (hence divide by $3$) but you're also counting $TTHT$ two times (and should divide by $2$). This is just to get some intuition, is by no means rigorous $\endgroup$ – Ant May 3 '16 at 9:48
  • 3
    $\begingroup$ @Ant The $4\times3\times2$ calculation in fact counts $TTTH$ six times, not three. And again it counts $TTHT$ six times. If it overcounted different outcomes by different factors then overall it would overcount by a factor of some kind of average of the individual factors, not by the product of those factors. $\endgroup$ – David K May 3 '16 at 13:31
70
$\begingroup$

As a comp sci major who dabbles in math, let me throw my perspective into this.

Debugging math is a completely different experience from debugging programs. The difference is that while we have programs, they (tend to be) imperative - that is, they list out a series of steps that need to be followed.

(I know that this is a gross generalization, and that Haskell/LISP/Scheme/Functional Programming languages exist and they aren't that way, but most "general" programming languages are imperative.)

In math, you generally have a set of statements that you "bring together" to get a solution. It's more of an expression than a recipe if that makes sense to you.

However, the nice part is a lot of the intuition of debugging carries over.

Some principles that carry over very nicely:

  1. Isolate a problem, get the minimal failing example. This works in both math and compsci. If you have a general formula, substitute small values like $0$, $1$, etc. as a sanity check.

  2. Breaking things gives you a better understanding of how they work. When you read a theorem or code anything, always push the boundaries of what you're doing. Ask yourself - "what would happen if I do not have this statement in my proof"? "What if I eliminate this line"? "Is this assumption really necessary"? Playing with math and trying to break it often helps in learning it as well.

Also, some branches of math are just straight up weird, and require you to build intuition about them - You won't find the ideas intuitive at all when you begin (topology was like this for me when I began learning it), but you gradually pick up styles of thinking that complements the branch of math you're studying.

Another great "debugging tool" is to plug in good examples into theorems / problems whenever you face something too generic. Always arm yourself with at least 3 to 4 examples for any topic, so you can quickly fact-check about things (and refer back to those examples). It's also nice to have non-examples to things to know the difference.

If you've taken calculus, then knowing your examples would be

  1. a function that is discontinuous $f(x) = \text{floor}(x)$
  2. a continuous but not differentiable function - $f(x) = |x|$
  3. a function that is both continuous and differentiable - $f(x) = \sin x$
  4. a nowhere differentiable function - Weierstrass function
  5. a nowhere continuous function - Conway's base 13 function

There are books such as counterexamples in topology that will arm you with a whole bunch of examples to think about. Things like these are super useful the more abstract you get in math.

One last thing you can do as a programmer is to actually write code that checks a hunch you have - this is a huge advantage and don't be afraid to exploit this. Think something is true but feel too lazy to check it? Code it! It's not only practice, but it often teaches you some really cool math facts as well.

Hope this helps as a rough guide on how to debug math :)

$\endgroup$
  • 5
    $\begingroup$ Thanks. I will remove the obsolete comment. By the way, you might prefer to use \lfloor x \rfloor to get $\lfloor x \rfloor$. $\endgroup$ – filipos May 3 '16 at 12:28
  • 5
    $\begingroup$ Another nowhere continuous function : Dirichlet's Function $\endgroup$ – SchrodingersCat May 3 '16 at 17:26
  • 13
    $\begingroup$ I think the "good examples" is actually quite a close analogy for unit testing. Run your code on the input that seems most likely to break it - test the corner cases. $\endgroup$ – Nate Eldredge May 3 '16 at 19:24
  • 2
    $\begingroup$ Nice answer! Especially the last comment - I check almost everything I do with Sage, even if I have what I think is a proof. $\endgroup$ – Jair Taylor May 3 '16 at 23:17
  • 1
    $\begingroup$ +1 for the last line. It really does teach you cool math stuff! When I was in high school I wrote a program to calculate a certain probability, but I made (several) mistakes and my program was always outputting $2.7182818$ which I recognized as $e$. After inspection I found out I was actually calculating $1 + 1/2 + 1/6 + 1/24 + \dots$, and the only logical explanation was that $\sum_{n=1}^\infty \frac 1{n!} = e$ ! I did not know that at the time and I was absolutely thrilled :-) $\endgroup$ – Ant May 4 '16 at 9:19
27
$\begingroup$

A somewhat parallel to debugging would be to hand check the various intermediate steps in your reasoning for an instance of the problem that is small enough to work out everything on paper.

In your case "$4$ flips" is indeed such a small number. And it is easy enough to convince yourself that $4$ is the correct answer. So your second computation starts with only knowing things that are true under your assumptions and ends with a claim that you know is false. To find the fallacy you would look for the first step in the argument where you conclude something that is actually false.

The first step in your reasoning is that there are $4\times 3\times 2=24$ ways to pick the three tails positions, as long as you remember the order you choose them in. We can verify that by writing down those 24 ways and counting.

123       124       132       134       142       143
213       214       231       234       241       243
312       314       321       323       341       342
412       413       421       423       431       432

Count - there are 24 of them, and if you've been a bit systematic about it you're fairly sure that none have been forgotten.

Then next step is that each TTHT-like outcome appears for 3 of these situations. Let's check that that is true by noting down what the outcome is in each of our list of 24:

123 TTTH  124 TTHT  132 TTTH  134 THTT  142 TTHT  143 THTT
213 TTTH  214 TTHT  231 TTTH  234 ...   241       243
312       314       321       323       341       342
412       413       421       423       431       432

Whoops -- now we have found four combinations that lead to TTTH, but according to our claim there should only be three. So there must have been an error in the reasoning that concluded that each outcome appears only three times!

$\endgroup$
18
$\begingroup$

I'm a student currently learning math at the undergraduate level. I mostly learn by self-study, so "debugging" my thinking process during the learning process is crucial. (I will interpret "debug" a little less literally, so more as checking your own work using alternate solutions / shortcuts.) This list is not exhaustive, but off of the top of my head here are a few ways I "debug" my work in math problems:

  • Is the solution of the right magnitude? (There are $2^4 = 16$ possibilities after flipping a coin $4$ times, so a solution of $40$ to your problem would not make sense.)
  • Look at the divisors of the solution. Are they "reasonable"? (Here it makes sense that your solution is divisible by $4$, because here are $4$ "spots" for the H and it intuitively shouldn't matter which spot it occupies.)
  • If computing a part of the whole (combinatorics), can you compute the other parts relatively quickly? If so, does the sum of the parts equal the whole?
  • When checking a proof: did you use all of the assumptions or was the proof "too simple"? If not, you've probably oversimplified something. (For instance here, why it's important that $a$ is squarefree in order to prove that $\sqrt{a}$ is irrational. )
  • For combinatorics: double counting.
  • Whenever possible, try to gain understand a concept / problem in multiple ways. Your solution is more likely to be correct if it passes both checks. For instance in calculus, most ideas can be understood geometrically and algebraically.
  • Since you're using the term "debug", you're probably a programmer. Write programs to check your work when applicable. (Combinatorics, number theory, even more specialized areas if you check out software like sage. )
  • When working with functions, make sure the simplest cases make sense. (E.g.: does it make sense that $P(x) = -32 + 4x$ models profits selling $x$ units at a price of $4$ dollars apiece with initial cost $32$ dollars? Yes, since $P(0) = -32$ is negative (before selling you lose money on fixed costs), and $P(8) = 0$ is where you break even, just as expected.)
  • For anything with a geometric interpretation: try to make an accurate visualization (by hand, or using something like GeoGebra or WolframAlpha) and see how your solution holds up. (E.g. did you have a triangle with sides $1$, $1$ and $3$ that is not possible to draw?)

The best way to learn to debug math though is doing practice problems / proofs. The experience of bashing your head against a problem until you get it helps build intuition in that small area. And part of intuition is knowing which random tricks are best to "debug" that particular problem.

$\endgroup$
14
$\begingroup$

This is a question that can invite a wide variety of answers, but let me give two.

The primary way that most mathematicians "debug" their proved theorems is by testing -- much like software is debugged. In your example, you conclude that your reasoning must be wrong because it gives the wrong answer. Theorems are created to be applied: if they are wrong, you usually eventually run into a counterexample, and have to amend or restrict the theorem. There are no guarantees as to whether or when this will happen, but this is usually how errors are discovered.

Of course, the platonic ideal of a proof has no room for such errors; that is why mathematicians like proofs so much. In order to bring a human proof closer to the platonic ideal, one thing that you could do is formalize mathematics (e.g. in set theory/ZFC, or type theory/HoTT, or what have you), and give your proof within that formal system. Then, all you have to check is that each step follows from the previous steps, which is -- if your formalization makes sense -- a process that is very precise and mechanical.

In fact, taking it a step further: you could type your proof into a formal language for which you have a formal proof checker, and have a computer verify that your proof is correct. Now you can be as sure as you are sure that your proof checker is correct (and these are typically not immensely complex pieces of software). This is an endeavour that some mathematicians have undertaken, see e.g. the Mizar project or formalization in HoTT.

$\endgroup$
11
$\begingroup$

Regarding math at the graduate level and beyond, these programming debugging techniques can be quite effective:

  • Rubber duck debugging: Find someone/something to whom to explain the bug and your solution. This is also effective for helping undergraduates find bugs in their solutions to word problems. Code review, i.e., presenting your argument to an at least minimally interested colleague, finds many, many bugs by the same mechanism.
  • Bisection: Did the claim hold half-way through a construction? Either way, next check at the appropriate quarter point.
  • Unit Testing: In math, this comprises having a pool of "friendly" and a pool of "bizarre" objects to test claims on. Examples: Does this claim hold for $[0,1]$? How about for the Cantor set? How about for the uncountable product of copies of $[0,1]$? Does it work for Abelian groups? solvable groups? finitely generated groups? Lie groups? et al.
  • Precondition checking: This theorem holds if that measure is $\sigma$-finite. Is that measure $\sigma$-finite? (This catches many, many bugs. Notorious example involving a definition: manifolds are Hausdorff, but there are published papers that forget to check this.) In fact, all theorems are (software "design by contract") contracts.
$\endgroup$
8
$\begingroup$

There are two strategies I could use to debug this problem.

One is to write the steps out one at a time, with more detail. Let's use this as an example:

Claim: There are 24 ways to order 3 Ts and 1 H if the Ts are distinguishable

Claim: There are 3 Ts, so if the Ts are not distinguishable, each order is counted 3 times because each one is counted 3 times.

If you don't see which claim is false, you can try splitting up each claim into steps or add more detail, or you can try the second strategy: testing it out.

Let's test the first claim:

Suppose the Ts were distinguishable. I will list out the 24 possibilities to see if there are actually 24 (if this turns out to be too large, you can try a smaller example, but 24 isn't too large so I'll just do it; also, do this in a logical order so you don't miss or repeat any):

$\hspace{5pt}1.\hspace{5pt}T_1, T_2, T_3, H\hspace{10pt}$ $\hspace{5pt}2.\hspace{5pt}T_1, T_2, H, T_3\hspace{10pt}$ $\hspace{5pt}3.\hspace{5pt}T_1, H, T_2, T_3\hspace{10pt}$ $\hspace{5pt}4.\hspace{5pt}H, T_1, T_2, T_3$

$\hspace{5pt}5.\hspace{5pt}T_1, T_3, T_2, H\hspace{10pt}$ $\hspace{5pt}6.\hspace{5pt}T_1, T_3, H, T_2\hspace{10pt}$ $\hspace{5pt}7.\hspace{5pt}T_1, H, T_3, T_2\hspace{10pt}$ $\hspace{5pt}8.\hspace{5pt}H, T_1, T_3, T_2$

$\hspace{5pt}9.\hspace{5pt}T_2, T_1, T_3, H\hspace{10pt}$ $10.\hspace{5pt}T_2, T_1, H, T_3\hspace{10pt}$ $11.\hspace{5pt}T_2, H, T_1, T_3\hspace{10pt}$ $12.\hspace{5pt}H, T_2, T_1, T_3$

$13.\hspace{5pt}T_2, T_3, T_1, H\hspace{10pt}$ $14.\hspace{5pt}T_2, T_3, H, T_1\hspace{10pt}$ $15.\hspace{5pt}T_2, H, T_3, T_1\hspace{10pt}$ $16.\hspace{5pt}H, T_2, T_3, T_1$

$17.\hspace{5pt}T_3, T_1, T_2, H\hspace{10pt}$ $18.\hspace{5pt}T_3, T_1, H, T_2\hspace{10pt}$ $19.\hspace{5pt}T_3, H, T_1, T_2\hspace{10pt}$ $20.\hspace{5pt}H, T_3, T_1, T_2$

$21.\hspace{5pt}T_3, T_2, T_1, H\hspace{10pt}$ $22.\hspace{5pt}T_3, T_2, H, T_1\hspace{10pt}$ $23.\hspace{5pt}T_3, H, T_2, T_1\hspace{10pt}$ $24.\hspace{5pt}H, T_3, T_2, T_1$

Because you are good at programming, sometimes writing a program to write all the cases can be a fast way to do this.

Now we test claim 2. Is each configuration listed 3 times? No, each one is listed 6 times, so that is where the error is. We should divide by 6 instead, giving the correct (or at least matching) answer of $24/6=4$.

One more way of finding errors (doesn't quite apply to this problem) is that if you have a lot of steps, you can see if the conclusion you reached somewhere in the middle is consistent with the original statement or if it is consistent with the final answer (e.g. if you are solving an equation and you wrote out all of your steps you can plug in the values you got for each variable into one of the intermediate steps to see if the error was after that step). This is like a binary search in the steps for the error, but you might want to have some preference for the harder steps.

$\endgroup$
6
$\begingroup$

Another method is to apply your method to other inputs that leads to larger errors. The idea is that the larger the error, the more obvious it becomes where the error is coming from. So, instead of 3 T's where the error is just a factor 2, if you consider, say, 100 T's then the error is astronomically larger, making the source of the error much more apparent.

The Monty Hall problem is also good example. If you consider a set up with a million doors instead of 3 doors then it's intuitively very clear what the optimal strategy should be.

$\endgroup$
5
$\begingroup$

One approach which might interest you is Automated proof checking, where you write the proof in a form that a computer can check the validity of.

It is not easy to write proofs in this form, as humans tend to skip lots of "elementary" steps when writing proofs for other humans to read. A computer-checkable proof will be much longer and more tedious.

However, adding in those skipped steps will reveal mistakes and hidden assumptions or "bugs" as you might call them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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