[FOM] Number theorist's interest in bounds

[Harvey Friedman]

Evidence from the number theorist Alan Baker, an unnamed well known number
theorist, and postings of Chow, and an expected posting about the situation
with Ax, Kochen, and Cohen, are pretty decisive concerning the general
character of number theorist's interest in bounds.

Here is a summary of what I conclude about the general situation.

There is considerable interest among number theorists concerning bounds in
the following contexts.

1. A Pi02 sentence has been proved. Of course, there is automatically an
effective upper bound by search. This they know. There is considerable
interest attached to finding a reasonable upper bound, the lower the better.
There is also considerable interest in finding a reasonable lower bound. The
higher the better. The interest attached, in this case, to the mere
existence of an effective bound is zero, since it is automatic by search.
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. The same with very low lower bounds. They suggest
the possibility that that lower bound can be improved to a much higher lower
bound.

2. Number theorists generally are only tangentially aware of a general
notion of effective. They are fully aware that the lower the amount of
computer time involved, or the lower the expression for the upper bound, the
sharper the result is.

3. A Pi03 sentence has been proved. There is considerable interest attached
to the question phrased simply as "is there an effective bound?" The reason
that this is already intrinsically interesting for them is that they are
familiar that effectivity is a sharp enough notion that one MIGHT be able to
establish that "there is no effective bound at all". Many know that this is
the case for Diophantine equations generally. I.e., they know about

for all Diophantine equations, there exists a vector x, such that if there
is a solution then x is a solution.

and know that there is no effective bound. They would not be so careful as
to state it that way. They would simply say "there is no effective procedure
for finding a solution to a solvable Diophantine equation." Logically
speaking, this amounts to the same thing.

4. They expect that if one does prove an effective bound exists for a Pi03
sentence, then in practice it is going to be "reasonable" or "somewhat
reasonable". For real world examples, this has always been the case, with a
few exceptions. I.e., an exponential stack of height 39 is counted as
"somewhat reasonable" but not "reasonable".

5. The most familiar cases of Pi03 theorems take the form

for all n, there are finitely many m such that P(n,m).

They are fully aware of the difference between getting an effective bound on
the number of m's, versus getting an effective bound on the m's. The latter
is much stronger. Often the former kind of effective bound is known and is
reasonable, whereas the latter kind of effective bound is not known, as in
the case of Roth's approximation theorem.

6. Here is an interesting example of a Pi02 theorem with upper bounds. First
the upper bounds were unreasonable - Ackermann level. Then a lot of activity
ensued to make them more reasonable - stacks of exponentials of fixed
height, finally. This is exactly the same as in the van der Waerden. First
Ackermann level. Then worse than a fixed stack of exponentials - Shelah.
Then, finally, short exponential stacks of fixed size, by totally new
methods of Gowers. 

Here is the relevant excerpt about this from

Michael Vaughan-Lee and Efim Zemanov, Upper bounds in the restricted
Burnside problem, J. Algebra 162 (1993), 107-145.

(There are more results, presumably, that are very relevant, in the sequel
Upper bounds in the restricted Burnside problem II, International J. Algebra
and Computation 6 (1996), 735-744. However, I don't have electronic access
to this).

NOTE: note the mentioning of the van der Waerden situation. This was after
Shelah and before Gowers.

"For groups of exponent p a primitive recursive upper bound for the orders
of finite m generator groups was found by Adjan and Razborov [3] (see also
[15]. Their proof is based on Kostrikin's original solution of the
restricted Burnside problem for groups of prime exponent. To give an idea of
the order of magnitude of the primitive recursive functions involved let us
define classes of the Grzegorchyk hierarchy (see [18]).

The upper bounds on the orders of finite m generator groups of prime
exponent p given by Adjan and Razborov [3] are of class Gr^5, as are the
bounds given in [15]. The bounds given in this paper are of class Gr^4, and
to achieve this it was necessary to obtain bounds of class Gr^3 for the
nilpotency class of sandwich algebras (see Section 1). It is interesting to
note that the proof that sandwich algebras are nilpotent which is given in
Kostrikin [15] leads to a bound for the nilpotency class which lies in Gr^4.
The simplest proof known to the authors of the nilpotency of sandwich
algebras does not even give a primitive recursive bound for the nilpotency
class. There was difficulty in extending our results from groups of prime
exponent to groups of prime-power exponent. An important step in the
original solution of the restricted Burnside problem for prime-power
exponent was Shirshov's proof of the so called N(k,s,n) lemma, which can be
viewed as a Ramsey-type statement (see [7]). The proof proceeds by a double
induction on n and k and yields the function

blah blah blah

This function is a variant of Ackermann's function [1], which is known to
grow faster than any primitive recursive function.

There are parallels between the results obtained here, and between results
in Ramsey theory. It has been an open problem for many years whether or not
there exists a primitive recursive upper bound in van der Warden's theorem
on periodicity in sets of integers and in other major Ramsey type theorems.
This problem was solved quite recently by Shelah [20]. The upper bound
constructed by Shelah lies in Gr^5. It is an open problem whether there
exists an upper bound in van der Wareden's theorem of class Gr^4.

[Subsequently solved by Gowers using Fourier methods, giving an exponential
stack of small height].

The known lower bounds in the restricted Burnside problem are of a
completely different order of magnitude from the upper bounds obtained here.
This parallels the situation in Ramsey theory [6,7]. Adjan and Repin [4]
have shown that if the prime p is sufficiently large then there exist finite
2 generator groups of exponent p with class at least 2^p/60. This lower
bound lies in Gr^3. As we mentioned above, our upper bounds lie in Gr^4, but
we conjecture that the least upper bound for the orders of finite m
generator groups of exponentn p^k lies in Gr^3. For some small exponents
much more can be said.

**************

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...

Harvey Friedman