Solution to Friedman's problem regarding Bolzano Weierstrass

[Andreas Weiermann]

Dear members of FOM,

Harvey M. Friedman formulated in his FOM 69 posting from November 1st 
1999 a problem regarding the Bolzano Weierstrass theorem.

For convenience I include a copy of his posting below.

At the end he asks:

"If we use 1/k_i then I don't understand what the c(n) look like. I am 
even confused about, say, 1/k_i(log(k_i)."

I spent some time on this problem and found it very interesting.

Now it seems that I have found an answer to the above question. It is 
that in both cases the function c(n) is bounded from above by an 
elementary function.

On the other hand functions of the form 
1/(k_i(log(k_i))...(log^d(k_i))^{1+epsilon}...)) will lead to 
Ackermannian lower bounds on c(n) whereas

functions of the form 1/(k_i(log(k_i))...(log^d(k_i))...)) still lead to 
elementary upper bounds for c(n). Here log^d refers to a d-times 
iterated log function.

With some extra efforts the phase transition can be refined further when 
the log operation is suitably iterated further (along transfinite ordinals).

All the best,

Andreas Weiermann



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

A staple of baby real analysis is the Bolzano-Weierstrass theorem, which 
we take in the following form:

THEOREM 1. Let x[1],x[2],... be an infinite sequence from the closed 
unit interval [0,1]. There exists k_1 < k_2 < ... such that the 
subsequence x[k_1],x[k_2],... converges.

We now want to discuss ways to suck finite information out of the 
Bolzano-Weierstrass theorem.

We begin with the following more precise statement, which relates to the 
rate of convergence of the subsequence.

THEOREM 2. Let x[1],x[2],... be an infinite sequence from the closed 
unit interval [0,1]. There exists k_1 < k_2 < ... such that

|x[k_i+1] - x[k_i+2]| < 1/(k_i)^2

holds for all i >= 1.

{Here k_i+1 is k sub i+1}.

This is an obvious consequence since any convergent sequence can be 
thinned out to have practically any kind of high powered convergence.

Now consider the following special case of Theorem 2.

THEOREM 3. Let x[1],x[2],... be an infinite sequence from the closed 
unit interval [0,1]. There exists k_1 < ... < k_11 such that

|x[k_i+1] - x[k_i+2]| < 1/(k_i)^2

holds for all i <= 9.

There is a very strong uniformity here that follows from the compactness 
of the Hilbert cube of infinite sequences from [0,1].

THEOREM 4. There is an integer constant c(11) such that the following 
holds. Let x[1],x[2],... be an infinite sequence from the closed unit 
interval [0,1]. There exists k_1 < ... < k_11 < c such that

|x[k_i+1] - x[k_i+2]| < 1/(k_i)^2

holds for all i <= 9.

To see this, note that by Theorem 3, for every x in the Hilbert cube, 
there exists 11 integers k_1 < ... < k_11 < c with the desired 
inequalities. This says that the open sets V(c) in the HIlbert cube 
cover the Hilbert cube, where V(c) is the set of points for which we can 
find the 11 k's below c. By the compactness of the Hilbert cube, this 
open cover has a finite subcover. Since the V's decrease as c increases, 
some V(c) is the whole space. This is the desired universal integer 
constant c for Theorem 4.

How big is c(11), which we take as the least constant for Theorem 4?

THEOREM 5. The c(11) of Theorem 4 exceeds A(3,64) = an exponential stack 
of 2's of height 64.

Here is a more general lower bound.

THEOREM 6. For all n >= 1 there exists c(n) such that the following 
holds. Let x[1],x[2],... be an infinite sequence from the closed unit 
interval [0,1]. There exists k_1 < ... < k_n < c such that

|x[k_i+1] - x[k_i+2]| < 1/(k_i)^2

holds for all i <= n-2.

THEOREM 7. For n >= 10, the least c(n) exceeds A(n-8,64). In particular, 
the least c(13) exceeds A(5,64). Here A is the Ackerman function.

There are neat upper bounds on c(n) in this same style, also.

We now discuss what happens when we modify the estimate1/(k_i)^2. 
Obviously any strictly positive function will make these statements 
hold, but the issue is the size of the associated constants c(n).

If we weaken the estimate by using a function that is somewhat larger 
than 1/k_i, then we get relatively small constants c(n). E.g., if we use 
log(k_i)/k_i, then we obtain merely exponential upper bounds.

On the other hand, if we use an estimate that is somewhat smaller than 
1/k_i, then we get roughly the same Ackerman function level upper and 
lower bounds as we have here. E.g., this happens when we use any 
(k_i)^t, where t < -1.

If we use 1/k_i then I don't understand what the c(n) look like. I am 
even confused about, say, 1/k_i(log(k_i).

HMF
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20230120/ec1b2b3e/attachment.html>