Recently on MathOverflow the following question was asked: “
The general question is: Solve 
For example, the RSA algorithm is implement in this way: Find two very large primes p and q. This can be done in polynomial time. Let 
The fact that you can find large primes fast but you can’t find discrete logarithms fast means that this method is safe. The fact that no one can prove you can’t find discrete logarithms fast means cryptographers worry about this a lot.
Send to KindleI have just posted a new Astounding Math Story. I have also rewritten the other two stories.
Send to KindleI am considering an Astounding Math story about how you can’t name an arbitrary real number. In this blog I will describe some of the math technicalities, teaching problems and writing problems that arise in writing the story. It would be great if other math popularizers would blog about the problems they faced in their writing and what decisions they made about them.
Consider first that we can name every rational number. You can describe rational numbers in terms of equivalence classes of expressions of the form “m/n” where m and n are names of integers, n not zero. Then any expression of the form “m/n” names a specific rational number and every rational number can be named in this way. Yes, the naming can be made unique by using expressions in lowest terms, but that is not the point here, which is that in theory you really can name every rational number.
Every real number has a decimal expansion. The expansion is nearly unique: some rational numbers have two different decimal expansions, but that is all (see (2) below). We may define a decimal expansion precisely using the “regular” expression [-]?[0..9]*[.][0..9]^(infinity). This means:
One minus sign or nothing
followed by
A string of any finite length of decimal digits
followed by
A decimal point
followed by
An infinite string of decimal digits.
This is not really a regular expression since regex’s don’t allow you to specify an infinite string. But it is a precise definition of decimal expansion, and every decimal expansion refers to a specific real number. You can then define the real numbers as equivalence classes of regular expressions of decimal digits, with each equivalence class containing one or two members.
The Astounding thing is that as a result of this construction
a) You can describe precisely the set of real numbers.
b) Each real number has a description as an infinitely long decimal expansion.
c) You cannot give a name to every real number. That’s because the description is an infinite sequence and you cannot give every infinite sequence even in theory (see (3).)
d) So when mathematicians deal with real numbers, they are dealing with things that in most cases they cannot refer to.
Complications
My purpose in writing Astounding Math Stories is to get people who are already somewhat familiar with math to have their consciousness raised about all the fascinating things that go on in math. This requires a delicate balancing act when I write them.
1) I get comments from readers like this one: “That is not astounding. I already knew about it.” This is probably inevitable. In the case of the names of real numbers, however, I’ll bet there are practicing mathematicians who understand item (d) implicitly but have never heard it said out loud.
2) You have to say precisely which two infinite sequences are in the same class. When I was teaching discrete math in the eighties and nineties, I realized that I had never seen this written out explicitly. Every description depended heavily on pattern recognition, as in the description “I am referring to the phenomenon that for example 0.9999… denotes the same number as 1.0000…” (See remark (6).) I included a nearly explicit description in my discrete math class notes (page 12).
Perhaps this problem should be slurred over. Really every real number has one decimal expansion. That thing with the 9’s is just a technicality. (This makes me a heretic. Mathematicians don’t usually say things like that.)
3) You cannot give the name of every real number because the set of linguistic expressions is countable and the set of infinitely long decimal expansions is uncountable. Do I just quote this fact? Do I write another Astounding Math Story about infinite cardinality? Probably.
Some would object that you can’t give the name of every rational number either. But there is a name (a finitely long linguistic expression) for every rational number. You can’t in physical fact “give” the humongous ones but that is a practical problem. In contrast, most real numbers have no linguistic expression naming them.
4) I need to keep the demands on the reader as low as is reasonable, but not lower. A minor example in this case is that I express everything in terms of decimal expansion instead of binary expansion or Cauchy sequences (more abstract) or Dedekind cuts (even more abstract). In theory, binary expansions are not any more abstract than decimal expansions and require less data, but in fact most of the people I am trying to attract are less familiar with binary than decimal, and that drags on their understanding.
5) When I say “You can describe a real number as an infinitely long decimal expansion” you run into the ubiquitous difficulties math-newbies have with infinite sequences. Namely, they think of then as progressing through time, so you never get to “the end”. In fact, experienced mathematicians think of an infinite sequence as existing all at once: every entry is there now.
Students complain that they can’t “visualize” the entries all at once, but that is not the point: You are not suppose to visualize the whole sequence at once, you are suppose to think and talk about the entries as if they are all there. That is, assent to the concept that the whole thing is “there”, which is not the same thing as visualizing it. (I also wrote about this phenomenon in abstractmath and in a previous blog.)
So when I write about the infinitely long decimal expansions I know many readers’ understanding will falter right there; they will not be able to take in the rest of what I write. What do I do about this? Well, I suppose I could include the last paragraph!
Note: This discussion is not about what infinite sequences “really are”, but about how you think about them. This way of thinking about them has been around for a couple of centuries and have produced many useful theorems and no known contradictions. Philosophers may have a problem with this point of view, but mathematicians don’t.
6) Studies show that most math students do not believe that 0.999… is the same number as 1.000… Some mathematicians I know say things like: “Why are you writing for people like that? They are too stupid to understand anything about abstract math.” But it is time mathematicians stopped insisting that there is no point in getting people who are not especially talented in math interested in math, or trying to explain anything to them. In fact, it appears to me that this elitist attitude is in the process of dying out. It had better be dying out.
Send to KindleAstounding 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 KindleI have written a second Astounding Math Story, this one about factoring integers and primality testing, published here. (I announced ASM here.)
These stories are aimed at people interested in math but not very far along in studying abstract math, the same audience that my abstractmath website is concerned with. That makes the stories hard to write.
For one thing, they need to be streamlined as much as possible. Each story should explain one astounding fact clearly, making as few mathematical demands on the reader as possible. I have put in links, mostly to Wikipedia, to explain concepts used in the story. This story has lots of footnotes telling about further developments and fine points.
Another point is that it is sometimes hard to convince students that they need to be astounded! I mentioned the phenomenon that primality testing is faster than factorization many times in my teaching (mostly to computing science students). Often I had to work hard to get them to realize that there was something shocking about this: Being a composite means having proper factors, but the fast ways of discovering compositeness tell you it is composite without giving any clue as to what the proper factors are. Research mathematicians are familiar with the idea of proving something exists without being able to say what it is, but students often have to be led by the nose to grasp this idea.
With this story I have experimented with making it a dialog. That makes it easier to write about a conflict between new ideas and old presuppositions. I would love to get comments about how these stories are written as well as the math involved.
Experienced research mathematicians will probably not be Astounded by these stories. But the ones I am writing about have often given mathematicians in previous centuries a lot of trouble — they seemed unbelievable or contradictory. And modern students have trouble with these ideas, too. In the current ASM I mention Kronecker’s problem with nonconstructive existence proofs.
One of the worst problems comes with infinite decimal expansions of real numbers (which I intend to write about). You can prove that 1.000… – .999… but the students don’t really believe it. That may be because they don’t really believe that all the decimal digits are really there. (A lot of philosophers don’t believe this either, but almost all research mathematicians talk and act as if they do.)
By the way, it is amazing how often there is an article in Wikipedia that says just what you want the reader to know (and of course usually a lot more) and does it pretty well. Lately I have run across just one exception, the articles on context. I have been writing about context in mathematical writing for abmath (don’t look, it isn’t there yet) and have wound up going into more detail than I wanted because I could not refer to Wikipedia.
Send to KindleAstounding Math Stories
I am in the process of selling my old collection of Astounding Science Fiction on Ebay. It occurred to me that math needs an Astounding Math magazine. It could contain short descriptions of some mathematical facts that are really weird that could awaken people’s interest in math. Well, geeky people anyway.
These astounding facts also illustrate some important ideas in math. For one thing, some of them are not astounding when you get the right representation or proof (for example e^{iπ} = –1). And some are simply frauds (infinite cardinals).
Each of the examples below will be fleshed out and given references. The first one, the Perrin function, has already been posted on the Astounding Math Stories website. Comments and suggestions are earnestly desired.
Perrin pseudoprimes
The Perrin function P(n) is a certain easily-defined function on the natural numbers with this property:
For all integers n e^{iπ} = –1
This is Astounding. Who would have thought that the numbers e, i and π would be related in this way? Well, actually, it is not hard to understand why it is true if you use Euler’s formula in the context of the Argand representation. And the fact that Euler’s formula works is not very difficult to understand. (Perhaps Euler’s formula is nevertheless Astounding. Feynman thought it was.) This is an excellent example of the ratchet effect: An amazing or incomprehensible statement about math suddenly becomes totally obvious and you can’t understand why you didn’t understand it before!
Infinite cardinals
There are “as many” integers as there are rational numbers. This is Astounding!
Really? In fact, this statement is a fraud. It depends on defining the cardinality of a set in terms of bijections (not a fraud) and then referring to the cardinality of the integers or rationals in terms of words like “many”.
What is happening is that, for finite sets, the cardinality function on sets Card(S) means the same as #(S). the number of elements of S. On infinite sets, the cardinality function does not have some of the familiar properties of the number of elements of a finite set; in particular, it can happen that S is a proper subset of T but Card(S) = Card(T). Unless you specifically state, “When I say S has as many elements as T, I mean Card(S) = Card(T)”, then you are deliberately using the word “many” with a nonstandard meaning that the listener may not know. This is like the politician who told his audience that his opponent was a “sexagenerian”. Playing on someone’s ignorance is FRAUD.
Composite numbers
It is possible to prove that an integer n is composite without knowing any nontrivial factors of n. This is Astounding! How could you show it is composite without finding a nontrivial factor? This is a consciousness-raising example that shows that just because you can’t think of how to do something doesn’t mean it is impossible.
To show that n is not a prime, all you have to do is find an integer a for which a^n – a is not divisible by n (Fermat’s Little Theorem). That is not even very hard to prove.
Humongous numbers
As far as we know, π(x) − li(x) changes sign for the first time at some humongous number. 1.397×10^316 is a LARGE number. Other even huger numbers are Moser’s number and Graham’s number. One could also refer to Ackerman’s function. All these are consciousness raising examples that show how big numbers can get.
Many years ago the Little Girl Next Door asked me what the next number after a trillion is. I said, a trillion and one. She was Disgusted.
Function Spaces
The Astounding thing about function spaces is that each point in a function space is a function. A whole function, like sin x or the Riemann Zeta function. Not its values, not its formula, but the whole thing. This story is going to be difficult to write, but if I can carry it off it may help the student along the way to understanding the concept of an encapsulated mathematical object.
Other topics:
The monster group
1^2+2^2+3^2+…+24^2 = 702 and the Leech Lattice
41 and 163
Send to Kindle