Astounding Math Stories is intended to attract the interest of bright, technically oriented non-mathematicians or beginning math students by telling them about some of the phenomena in math that are more surprising than, say, Venn Diagrams. This is turning out to be hard to do. You get responses from sophisticated people who say, in effect, “Well I knew that!” or “That’s not surprising!”. But sometimes they uncover real difficulties. Example:

Last August, Pubkeybreaker posted this message on sci.math about Finding Factors or Not:

I’m not sure why being able to show that an integer is composite without finding a factor is “astounding”.
Even at a beginning, first year algebra level we know that linear equations (with real coefficients) have a real solution, without knowing what the solution is. Similarly for any odd degree polynomial. We know that positive real numbers have a positive square root without knowing its value…. etc. etc.
Why should it be astounding that we know something
exists yet not know its value?

This brings up a sticky point. I was trying to find a simpler example of the sort of nonconstructive proof of existence that Hilbert used for the finite basis theorem. In that proof there is an inductive construction where at each step you find a polynomial of minimal degree in a certain ideal. But the ideal is infinite, so how do you know when you have found a minimal degree member? That is why it is nonconstructive.

Now Fermat’s Little Theorem gives you a way (if it works — it doesn’t always) of finding a proper factor of a composite number without showing how to calculate it. But finding a proper factor of a composite number has an obvious algorithm: try every number up to its square root. This is a finite but slow process; it is not nonconstructive.

What FLT does is give you a fast way of showing the existence of the proper factor without give you a fast way to find it. (See the appendix below.) That is simply not the same situation as in the finite basis theorem.

Clearly I need to rewrite the FLT story in such a way as to emphasize speed-of-algorithm difference instead of the nonconstructive part. Then I need to write another Astounding Math Story that describes a truly nonconstructive proof directly. The Hilbert Basis Theorem itself might be a candidate; the ideas involved are not too hard, although they are more advanced than I was hoping for for Astounding Math Stories.

Appendix

Here are some more detailed comments on Pubkeybreaker’s specific examples:

The proof that odd degree real polynomials have a real root is that such a function goes to positive, resp. negative infinity in the positive, resp. negative direction, so must cross the x axis. This immediately suggests an algorithm for finding the solution: choose larger and larger inputs in both directions until you find one that gives positive output and one that gives negative output. Now you have trapped the solution between two real numbers. Now use bisection. The square root can be found in a similar way, although of course there are faster algorithms.

The proof that a number is composite using the contrapositive of Fermat’s Little Theorem does not obviously (or even non-obviously) suggest a way to find a proper factor of the number. Not only that, but people have fancier ways (only partly based on Fermat’s Little Theorem) to test for primality that always work, and work faster than any known method of producing an explicit proper factor. This is a real contrast to the situation with cubic polynomials.

Send to Kindle