FOM: Re: F.O.M./pure math; general intellectual interest

[Harvey Friedman]

Lou writes:

>Okay, I had forgotten this old discussion where I mentioned number theory
>in connection with complexity (but even there it was in reaction to
>earlier claims by you concerning fom & complexity). Anyway, this is
>not worth our energies to spell out further, we do not have a real
>disagreement on this matter, I think.

OK.

>Otherwise I am not conceding anything. Sure, "suspect" is vague, so is
>"general intellectual interest", and perhaps even more, the significance
>of "general intellectual interest".

So you are refusing to explain "suspect?" I'll try again to get you to do
this. I claim that of these three, you are the only one on the fom list of
about 245 subscribers who would entertain the idea that they are of even
remotely comparable vagueness. If you don't explain what "suspect" is, I
might have to, and continue the brawl from there.

If you don't explain "suspect" you are just being silly and grossly unfair.
I have done a lot of preliminary explanation of "general intellectual
interest." You haven't even done any preliminary explaining of "suspect."

>I find P=NP a very interesting
>problem, and it sure has to do with our basic intuitions and experience
>with algorithms. As to how it would play for a fairly general audience
>compared to abc, I wouldn't be able to predict.

You are also the only one on the fom list of about 245 subscribers who
would assert (falsely) that "you wouldn't be able to predict." Let's have a
contest. We will design a meeting with selected participants and test the
matter. We could do this at Illinois or at OSU. Then we wouldn't have to
pay travel expenses for the judges.

>Both are the kind of
>mathematical questions that can be discussed in a Scientific American
>article (maybe this has already happened).

I subscribe to the Scientific American, and they have gotten away from
articles on things like abc. Want to test this? We can write to editors of
Scientific American testing out a possible submission for appropriateness
for the readership. Have you carefully listened to the video on Wiles? It
is extremely well done, and of great human interest. Do you think that a
single mathematical idea was communicated successfully compared to tapes on
other matters? It is clear that Scientific American published this article
because of the human interest involved, and the Mt. Everest aspect.

Historians - I seem to recall several articles touching on P=NP directly
and indirectly, but none on abc. Don't trust me on this. Is it mentioned in
the recent article on FLT?

>Anyway, if P=NP is false
>(as seems plausible), and even if it's true (with probably huge
>constants), and one of these is established, this would surely
>increase our theoretical understanding of algorithms in a big way,
>but there is no reason to think it would have direct practical
>(technological) consequences. In discussing P=NP for a general
>audience it seems to me this should be pointed out.

This is completely misleading. The actual situation is absolutely perfect
for a crucial mathematical problem. Almost nobody thinks that P=NP, and I
think that if P=NP, then it is very likely that we misunderstand algorithms
so much that the solution will have substantial practical consequences for
algorithm design. On the other hand, since notP=NP, there is the question
of the practical significance of that. Well, the right proof of that can be
expected to lead to rigorous proofs of the security of cryptosystems. This
is one of the motivations behind eliminating number theory in the design of
cryptosystems. Otherwise, one is faced with yet more work beyond a good
proof of notP=NP. The general point to be made to general audiences is
that, e.g., P=NP is intimately tied up with cryptosystems and everything
else, and that before good proofs of notP=NP are found, we simply cannot
begin to do what we need to do in order to know that cryptosystems are
secure. Beyond that, it is perhaps not known to be directly practical, but
is the ultimate in "theoretical practicalness," in the sense that it would
justify a lot of present ways of doing algorithms virtually everywhere as
best possible. This is always a great kind of "application." And the sense
of best possible will be more and more in tune with practical
considerations as the theory surrounding notP=NP is developed further and
further. What is so intriguing is that notP=NP is obviously an enormous
intellectual logjam. And everybody cares about this.

> As to abc, it seems to express a very basic and at the same time
>deep property of another kind of basic objects, namely natural
>numbers (their behavior under addition and prime factorization).
>(A special case says: there is a positive constant C such that if
>a+b=c, where a and b are positive integers with gcd=1, then
>c < C.P^2, where P is the product of the distinct prime factors of abc.
>Reference: S. Lang, Old and new conjectured diophantine inequalities,
>Bull. AMS 23, 37-74, 1990.)

This is a purely technical problem. P=NP is a deep conceptual problem as
well as a technical problem. Yours may even be a great technical problem.
If I recall it is related to FLT, and also involved in the kind of
elementary number theory that is relevant to current number theoretic
approaches to complexity(!). But the only way you can get anybody to care
about it outside math is to claim some relevance to something like P=NP or
cryptosystems - along with other math with relevance. Otherwise it has the
appearance of being an imbred occupation of a bunch of harmless genuises
who are best left alone to themselves. Its relevance to things like P=NP
and cryptosystems are the only way I see of getting any of the following to
care:

scientific philosophy, statistics, finance, computer security, complex
systems, complexity theory, database theory, algorithm design,
cryptography, logic, artificial intelligence, robotics, networking,
hardware design, control theory, operations research, neural nets, quantum
computing, expert systems, code verification, proof checking, statistical
mechanics, linguistics, dynamical systems, signal processing, etcetera; and
many, many more.

And it is among many pieces of math that are so relevant. How are you going
to get such people to see any intrinsic interest in such a problem? They
have no problem seeing intrinsic interest to things like P=NP and
cryptosystems.