Cam's Blog

December 9, 2009

Reduce a problem to one you can solve

Filed under: Elementary, Math, Music — cfranc @ 7:43 pm

Mathematicians are in the business of proving things. This business is subject to the basic rules of logic, plus in any given area of math, be it geometry, arithmetic or whatever, a bunch of axioms which enrich the set of rules that one can play with. Think of the axioms as a minimal list of facts taken to be true and which describe some area of mathematics. In geometry the axioms describe how points and lines behave. In arithmetic the axioms describe how integers behave. Once you’ve got your axioms fixed and you’re reasonably confident that they model whatever it is you want to study, then you can begin using the rules of logic to start deducing facts. This is the process of “proving theorems”.

There is no single way to prove everything that you might wish, a fact which has caused countless undergraduates hours of frustration. Indeed, coming up
with a good proof for a fact often requires great ingenuity and creativity. Having said this, there are many methods of proof that are often successful. I’d like to discuss the method of “reducing a problem to an already solved one”, or “reducing a problem to an easier case”. As you will of course have guessed, this method works by showing that to prove a given fact, it suffices to prove a different, hopefully easier, fact. For instance, to prove a theorem about positive integers, one sometimes first proves the theorem for square integers (1, 4, 9, 16, 25, etc). In this case the theorem may be easier. Then one would try to reduce the original problem to this case by “filling in the gaps” between squares. How might you think to use such a strategy to solve a problem? Well, after thinking for a long time, you may come up with an “easy” proof in the case of squares, which doesn’t seem to quite work in general. This is the hint that “reduction to an easy case” might be the method of proof for you: an easy and elegant proof for a broad class of special cases. I can’t think of any very simple examples of this method off the top of my head, unfortunately. Can you suggest any elementary examples? All of mine involve reducing theorems about modules to the free case!

Rather than consider special cases, mathematicians sometimes adopt this reduction method to reformulate the problem so that they can make use of incredibly powerful results obtained previously. A “powerful” result is something which has a lot of interesting consequences. Many math papers read as follows: the authors start with some result that they’d like to prove. They muck it up a bit and rearrange bits and pieces. After a bunch of hard work they say, “Hey look, this final bit follows immediately from the ‘Omnipotent Proving Machine Theorem‘”. Such a paper is using the technique of “reducing to the case of the ‘Omnipotent Proving Machine Theorem‘”. Often this method works because the theorem the authors are trying to prove really is as difficult as the results they rely on. Occasionally, though, mathematicians use very difficult and deep results to prove relatively simple things. Such proofs are usually unenlightening and should be avoided. This highlights one of the dangers of reducing problems to others. I can give a relatively simple example of this from my own undergraduate days.

During my first year as an undergraduate I took a course in abstract algebra — group theory mostly, with a bit of ring theory thrown in at the end. I had
never seen real mathematical proofs before, and so I was completely unfamiliar with the techniques that one might employ. On our first assignment we
were asked, amongst other things, to prove that every composite integer x > 1 has a prime factor which is no larger than \sqrt{x}. If I recall correctly, I reduced the problem to a question about a quadratic polynomial, a subject I was very familiar with from high school. This was a very stupid and convoluted proof that took me a page to write. There is absolutely no need to introduce polynomials; it was a contrived idea that I came up with because I was uncreative and fell back on known results. The grader assigned me full marks but wrote me a note explaining that despite the grade, my proof was quite poor. Indeed, we can prove this fact very easily by contradiction: a composite integer x > 1 has at least two prime factors, say p and q (which may be equal). If we had both \sqrt{x} < p and \sqrt{x} < q then we could multiply these to deduce that x < pq. But of course pq \leq x, which implies the contradiction that x < x! We conclude that either p \leq \sqrt{x} or q \leq \sqrt{x}, which is what we wanted to show. This proof is much more satisfying than my stupid “reduction to the quadratic formula”.

I’ll end this post by highlighting two dangers of reducing problems to others, one in the form of a joke, and the other a song. First the joke: a mathematician and an engineer are sitting in a faculty lounge when suddenly the coffee machine catches fire. The engineer rushes to the kitchen, grabs a bucket of water, and puts the fire out. The next day the mathematician and engineer are again sitting together in the faculty lounge. The coffee machine catches fire for a second time, but today it’s the mathematician that leaps to his feet. He runs to the kitchen and grabs a bucket of water, brings it back to the lounge, and hands it to the engineer. The engineer quickly puts out the flames, and then confusedly stares at the mathematician. “What?”, asks the mathematician, “I reduced the problem to one we had already solved!”

This joke highlights the danger of reduction which was mentioned above: there was no need for the mathematician to enlist the help of the engineer. The second example comes from the musician Hayden and his song “Skates“. Here are the lyrics:

When I was younger, a part-time job worker
Department store centre, I saw a man enter
He was middle-aged, deep lines on his face

Ice skates he asked for, in the middle of summer
He wanted a good pair, the price he did not care

And I looked at him, he looked at me
He looked so sad, I had to see
What did he want, what could it be
What had he been through before me seeing him
In the store I worked for that year, that year

I asked are you a pro, he looked sad and said no
These skates are my last hope
Without them I cannot cope

And he said my wife, she drowned this summer
Behind our house, the river took her
I cannot swim, I need to find her
I will wait till it freezes over

And then I will skate, as far as it takes
I will skate as far as it takes, to bring her back home
To bring her back home, to bring her back home
Back home

In this example the customer can’t swim out to save his drowning wife. However, he knows that eventually the ice will freeze. Since he can skate, his plan is to wait and save her in the winter. Of course this reduction strategy is doomed since his wife unfortunately won’t be able to hold her breath for that long. His reasoning fails due to unrealistic assumptions about his wife’s lung capacity. So in using reduction methods for proof, we must take care to ensure that our reduction step is logically sound. It won’t do to treat a simple case or an easier problem, and then assume that the desired result follows. (Of course, the “deep-lines” of the middle-aged man’s face tell us that he never actually believed his skating plan would save his wife — the song is not about logic, but rather about the absurdity and tragedy of life.)

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: