[FOM] Intrinsic Interest of Effective Bounds

[Harvey Friedman]

The effective bound situation is definitely the UNIQUE place we can point to
now, at which proof theorists, f.o.m. people, constructivists, and core
mathematicians can have serious common grounds and interests. This is why I
continue the exchange concerning attitudes of core mathematicians. The
interest among core mathematicians is clearly sufficient to maintain dialogs
and serious interactions. This is a very good thing, and minimizing it would
serve no useful purpose.

On 4/13/06 12:52 PM, "Gabriel Stolzenberg" <gstolzen at math.bu.edu> wrote:
 
>  This morning I talked with a number theorist, who will be known
> here as "Deep Thought," who disagrees with the idea that bounds
> are intrinsically interesting and said that number theorists are
> sometimes able---often enough to make it interesting---to go from
> an "effective" bound to a realistic one.

The existence of an effective bound is always intrinsically interesting, and
many times it is completely trivial, and other times it is deep and solved,
and yet other times it is deep and unsolved. This is my view, and I also
regard its denial as indefensible.

The existence of a "realistic bound" is always intrinsically interesting,
although the notion of what is "realistic" is one of these informal ideas,
like finitism and predicativity, that splits into many different notions.
Various common words are attached to these bounds, at least in the case of
bounds that take the form of a function, rather than a single integer. E.g.,
one talks of linear bounds, quadratic bounds, polynomial bounds, exponential
bounds, primitive recursive bounds, etcetera. Of course, in these cases,
e.g., in the case of linear bounds, one also may wish to consider what the
constants are, and so forth. This is my view, and I also regard its denial
as indefensible.  

Now the issue under discussion generally has been: do number theorists share
these views, and to what extent?

It is clear from the examples I gave in some detail from Alan Baker and Efim
Zelmanov and also the Li - pi business, that

i) the existence of effective bounds is of clear interest to number
theorists and other core mathematicians;
ii) a not-very-good bound result leads to more work for better bounds, which
leads to more work for even better bounds, etcetera.
iii) the process seems to stop only when people run out of results, or when
lower and upper bounds "meet".
iv) there may be some issue as to how much of a "meet" in iii) is enough to
shut the interest down.

I conjecture that 

i) your "Deep Thought" would agree with me if I talked to him/her, as the
exact way in which these questions are phrased is extremely important;
and/or
ii) your "Deep Thought" is not adequately familiar with the SPECTACULAR
robustness of the formal treatment of the notion of algorithm.

ii) is rather common among mathematicians outside logic.

As a test, I would ask your "Deep Thought" whether a result to the effect
that 

"there is no effective bound whatsoever"

is intrinsically interesting.

It is even clearer from my experience that for a Pi03 theorems, proving that
there is NO effective bound, would be regarded as not only intrinsically
interesting (for interesting Pi03 theorems), but truly spectacular.

I believe that this is more than enough to justify the intrinsic interest of
the negation - i.e., the existence of an effective bound.
 
>  Finally, Deep Thought agrees that "effective" algorithm is an
> oxymoron.  

Would you prefer "algorithm"? Or "effective"? It is rather common to put
both together, and I thought that it was harmless.

On 4/14/06 3:00 PM, "Gabriel Stolzenberg" <gstolzen at math.bu.edu> wrote:

> 
> E.g., I haven't yet seen one example where an
> unrealistic bound is used to get a realistic one.  (I don't want to
> just hear about it.  I want to see it.)  Yet, once we have agreed that
> it is not a matter of an "intrinsic" interest in bounds, this seems to
> be the main reason for wanting them.

The natural progress of mathematics is to first prove something new, and
then to build on that success to prove something better, and then to build
on that success to prove something still better, etcetera.

In a situation where no effective bound is known, one naturally wants a good
effective bound, and ultimately a best effective bound. One may only see how
to get the existence of an effective bound, which may be uncomfortably
large. So one naturally disseminates that first, with the idea that one has
started the ball rolling, and one already has done something of intrinsic
interest. This is standard procedure throughout mathematics, science, and
engineering. 

The alternative would be to hold that unless one has a good bound from the
beginning, one should not disseminate any not-so-good bound. That attitude
goes counter to the standard mode of operation in mathematics, science,
engineering, business, etcetera.

This is my view, and I regard the denial as absurd. But the issue has
focused on what number theorists think. The evidence is conclusive to me
that they generally agree with this view.

>> However, there is still considerable interest in even a very high
>> bound, because it suggests the possibility that that upper bound
>> can be improved to a much lower upper bound.
> 
>  How does having an unrealistic upper bound suggest the possibility
> of getting a realistic one?  Past experience?

Obvious. And from past experience. However, one is of course on the lookout
for the possibility that there is, demonstrably, no good bound. I.e., the
lower bounds might get quite high. So one automatically sees the intrinsic
interest in both lower and upper bounds.

> How often does one go
> from a classical existence proof to a realistic bound, skipping an
> unrealistic one?  Is there a higher success rate if we stop to get an
> unrealistic one?

Practically every scenario has been realized in interesting cases. A very
common scenario is that a high upper bound is all that can be obtained
without additional massive work. So if one went directly for a low upper
bound, one would not have any results for a very long time. For example, it
may be the case that getting a high upper bound might be something that a
single good but not great researcher could do in a week. However, getting a
low upper bound might be something that requires several top researchers a
period of years. It may be that even to generate sustained interest among
the top flight researchers, who have lots of other things to do, and even
lots of other bound situations to investigate, there FIRST must be a
publication of a high upper bound.
> 
>> Note that this follows the pattern indicated above for Pi02 sentences,
>> exactly. Unreasonable bounds came first. Then a lot of activity to try
>> to make them better. They finally became "somewhat reasonable" but not
>> "reasonable" yet. Also serious interest in lower bounds. The matter is
>> surely quite ongoing...
> 
>  Right, but this is not what one would ordinarily call an "intrinsic
> interest" in unrealistic (unreasonable) bounds, which is more or less
> where I came in.

Independently of what I wrote, the mere existence of an effective bound is
generally recognized as being intrinsically interesting. Often, the
existence is first communicated through a report of the bad, but effective,
bound.

The Skewes case with Li - pi is already quite a story, involving a single
integer bound (not a function). The first bound has been reduced very very
dramatically, apparently using the earlier work each time, but still
tantalizingly bigger than what can be computed. However, the speculation is
that the bound could get lower, building on the existing work, down to the
outer threshold of computing. That would generate perhaps a very deep
collaboration between number theorists, theoretical computer scientists, and
practical computer architecture people, on pushing the threshold of
computing just to get to the first sign change. A very exciting prospect to
me. 

Harvey Friedman