[FOM] Number theorist's interest in bounds

[Harvey Friedman]

On 4/8/06 11:42 AM, "Timothy Y. Chow" <tchow at alum.mit.edu> wrote:

> Gabriel Stolzenberg <gstolzen at math.bu.edu> wrote:
>>    I'm surprised that you don't tell us how this interest is manifested
>> mathematically.  Isn't that important?  I'd like to see some of the work
>> that he did on questions of this kind.
> 
> Oh, is that all you mean?  This request is easy to satisfy.  At one time
> I had an officemate, Mike Bennett, whose career was and is devoted to this
> kind of thing.  Browse his publications at
> 
> http://www.math.ubc.ca/~bennett/publ.html
> 
> and you'll quickly find that even the papers that don't have the words
> "effective" or "explicit" in the title are deeply concerned with effective
> methods in Diophantine approximation.  For him, a nonconstructive theorem
> such as Roth's theorem is little more than a starting point that guides
> his search for effective (and better, computationally efficient) methods.
> 

Alan Baker is NOT one of the three number theorists I contacted, but I have
met him, and perhaps I will contact him.

In the meantime, I looked at his book Transcendental Number Theory,
Cambridge University Press, 1975. First I looked at the list of references,
under Baker and found these:

Bounds for the solutions of the hyperelliptic equation, P.C.P.S. 65 (1969),
439-444.

Effective methods in Diophantine problems I, II, Proc. Symposia Pure Math.,
vol. 20 (Amer. Math. Soc., 1971), pp. 195-205; ibid. vol. 24, pp. 1-7.

Effective methods in the theory of numbers, Proc. Internat. Congress Math.
Nice, 1970, vol. 1 (Gauthier-Villars, Paris, 1971), pp. 19-26.

A sharpening of the bounds for linear forms in logarithms I, Ii, III, Acta
Arith. 21 (1972), 117-129, 24 (1973), 33-36, 27 (1974), 247-252.

I haven't looked these up yet - most require a visit to the library.

Then I looked at Chapter 3, Lower bounds for linear forms.

He opens with recalling a key standard definition that allows one to talk
about bounds in an intelligible way. This is the definition of the height of
an algebraic number as "the maximum of the absolute values of the relatively
prime integer coefficients in its minimal defining polynomial."

He presents a lot of history surrounding the non-vanishing of the linear
form

Lambda = beta_0 + beta_1 log alpha_1 + ... + beta_n log alpha_n
 
where the alpha's and beta's denote algebraic numbers. He cites that earlier
in the book, he proves that it suffices to assume that

the alpha's are not 0 or 1; and

beta_0 not= 0, or 1,beta_1,...,beta_n are linearly independent over the
rationals. 

The cited result is easily seen, with standard technology, to be a Pi02
sentence. 

Baker then says "in the present Chapter, quantitative extensions of the work
will be discussed, giving positive lower bounds for |Lambda| in terms of the
degrees and heights of the alpha's and beta's."

He then states the following Theorem.

THEOREM 3.1. Let alpha_1,...,alpha_n be non-zero algebraic numbers with
degrees at most d and heights at most A. Further, let beta_0,...,beta_n be
algebraic numbers with degrees at most d and heights at most B (>= 2). Then
either Lambda = 0 or |Lambda| > B^-C, where C is an effectively computable
number depending only on n,d,A, and the original determinations of the
logarithm. 

I don't quite know what the meaning is of the very last phrase. But this
statement, in and of itself, has virtually no content, as it is immediately
implied by general nonsense.

HOWEVER, Baker goes on to give an estimate for C, which then brings the
content to life. Firstly, he asserts that C takes the form

C'(log A)^k, where

k depends only on n, and C' depends only on n and d.

With these dependency conditions, Theorem 3.1 now has the logical form Pi03.

So at this exact moment, we have a Pi03 theorem without the phrase
"effectively computable". With the phrase "effectively computable", it
becomes a Sigma03 theorem. With the phrase, say, "iterated exponentially
computable", it becomes a Sigma02 theorem. And, finally, there appears to be
some actual decent effectively computable function roughly described, so
that the statement becomes Pi01.

Moving on to Chapter 4, I quote

"our purpose here is to apply the work of Chapter 3 to effectively resolve a
wide class of Diophantine equations. In particular, we will treat the Thue
equation F(x,y) = m defined over any algebraic number field, the famous
Mordell equation y2 = x3 + k, to which, incidentally, there attaches a
history dating back to Bachet in 1621, and we shall obtain an effective
algorithm for determining all the integer points on an arbitrary curve of
genus 1. Our theorems will be proved in an essentially qualitative form, but
it will be apparent that they can be adapted to yield explicit bounds for
the sizes of all the solutions of the equations. A summary of quantitative
aspects of the work is given in the last section."

Baker starts off with the following.

"Let K be an algebraic number field, with degree d, let alpha_1,...,alpha_n
be n >= 3 distinct algebraic integers in K, and let mu be any non-zero
algebraic ineger in K. We prove:

THEROEM 4.1. The equation (X - alpha_1 Y)...(X - alpha_n Y) = mu has only a
finite number of solutions in algebraic integers X,Y in K and these can be
effectively determined.

We define the size of any algebraic integer theta in K as the maximum of the
absolute values of its conjugates, and we signify the size of theta by
||theta||. With this notation, we shall in fact show how one can obtain an
explicit bound for ||X|| and ||Y|| for all X,Y as above. The bound can be
expressed in terms of d and the maximum of the heights of
alpha_1,...,alpha_n,mu and some algebraic integer generating K; ...

...

THEOREM 4.2. The equation Y^2 = (X - alpha_1)...(X - alpha_n) has only a
finite number of solutions in algebraic integers X,Y in K and these can be
effectively determined.

...

THEROEM 4.3. The equation f(x,y) = 0 has only a finite number of solutions
in integers x,y and these can be effectively determined.

...

5. Quantitative bounds.

As remarked earlier, the arguments employed here enable one to furnish
explicit upper bounds for the size of all of the solutions of the above
equations. To calculate these bounds one needs first a quantitative version
of Theorem 3.1, and, in this connection, the most useful result so far
established reads:

If alpha_1,...,alpha_n are n >= 2 non-zero algebraic numbers with degrees
and heights at most d (>= 4) and A (>= 4) respectively, and if rational
integers b_1,...,b_n exist with absolute values at most B such that

0 < |b_1 log alpha_1 + ... + b_n log alpha_n| < e^-delta B,

where 0 < delta <= 1, and the logarithms have their principal values, then

B < (4^(n^2) delta^-1 d^2n log A)^((2n+1)^2).

...

In special cases one has stronger bounds.

...

Much interest attaches to the size of the solutions of the original Thue
equation F(x,y) = m (see section 1) relative to m."

NOTE: Theorems 4.1 - 4.3 are Pi03 sentences without the effective bounds,
and with the effective bounds, they become Pi01 sentences.

Harvey Friedman