FOM: 43:More Enormous Integers/AlgGeom

[Harvey Friedman]

This is the 42nd in a series of self contained postings to fom covering a
wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98
10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM
20:Proof Theoretic Degrees  8/2/98  9:37PM
21:Long Sequences/Update  10/13/98  3:18AM
22:Finite Trees/Impredicativity  10/20/98  10:13AM
23:Q-Systems and Proof Theoretic Ordinals  11/6/98  3:01AM
24:Predicatively Unfeasible Integers  11/10/98  10:44PM
25:Long Walks  11/16/98  7:05AM
26:Optimized functions/Large Cardinals  1/13/99  12:53PM
27:Finite Trees/Impredicativity:Sketches  1/13/99  12:54PM
28:Optimized Functions/Large Cardinals:more  1/27/99  4:37AM
28':Restatement  1/28/99  5:49AM
29:Large Cardinals/where are we? I  2/22/99  6:11AM
30:Large Cardinals/where are we? II  2/23/99  6:15AM
31:First Free Sets/Large Cardinals  2/27/99  1:43AM
32:Greedy Constructions/Large Cardinals  3/2/99  11:21PM
33:A Variant  3/4/99  1:52PM
34:Walks in N^k  3/7/99  1:43PM
35:Special AE Sentences  3/18/99  4:56AM
35':Restatement  3/21/99  2:20PM
36:Adjacent Ramsey Theory  3/23/99  1:00AM
37:Adjacent Ramsey Theory/more  5:45AM  3/25/99
38:Existential Properties of Numerical Functions  3/26/99  2:21PM
39:Large Cardinals/synthesis  4/7/99  11:43AM
40:Enormous Integers in Algebraic Geometry  5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees  5/25/99  6:01PM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of self contained postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

FAVORITE SELF CONTAINED POSTINGS: 21, 25, 27, 31, 32, 34, 35', 37, 38, 39,
41, 42.

This posting is a self contained restatement of #40.

This was motivated by a reconsideration of some work I had done in 1986
after digesting Simpson's result which shows the equivalence over RCA_0 of
the Hilbert basis theorem for polynomial rings in several variables over
fields with omega^omega is well ordered. See Steve Simpson, Ordinal numbers
and the Hilbert basis theorem, JSL 53 (1988), 961-974.

I gave a finite form of the Hilbert basis theorem, and gave upper and lower
bounds showing that the Ackerman hierarchy is spanned. Some years later, I
gave some further finite forms involving the degree spectrum of ideal
bases. But I now prefer the following closely related formulation in
algebraic geometry.

Let k >= 1 and F be a field. An algebraic subset of F^k is a subset of F^k
which
is the set of simultaneous zeros of a finite set of polynomials in
F[x_1,...,x_k].

The presentation degree of an algebraic set A containedin F^k is the least
d such
that A is the set of simultaneous zeros of a system of polynomials in
F[x_1,...,x_k] of degree at most d.

Let k,n >= 1. We define L(F,k,n) to be the longest possible length of any
decreasing chain of algebraic subsets of F where the presentation degree of
each succeeding set is exactly one higher than the presentation degree of
the preceding set.

By Hilbert's basis theorem, no such decreasing chain can be infinite.

THEOREM 1. For any k,n >= 1 and field F, L(F,k,n) exists. In fact, for any
k,n >= 1, L(k,n) = max{L(F,k,n): F is a field} exists. As k varies, the
functions L(k,n) of n are primitive recursive and every primitive recursive
function is dominated by almost all of them.

We now want to give a rather specific lower bound result. We use a standard
version of the Ackerman function A:Z+^2 into Z+ given by A(1,n) = 2n,
A(k+1,1) = A(k,n), A(k+1,n+1) = A(k,A(k+1,n)).

Define H:Z+^2 into Z+ as follows. H(1,n) = n. H(k+1,1) = H(k,2). H(k+1,n+1)
= H(k,H(k+1,n)+2).

THEOREM 2. For all k,n >= 1 and infinite fields F, L(F,k,n) > H(k,n)-n.

LEMMA 3. H(1,n) = n. H(2,n) = 2n. H(3,n) = (2^(n+2))-4. H(4,1) = H(3,2) =
12. H(4,2) = H(3,H(4,1)+2) = H(3,14) = 65,532. H(4,3) = H(3,65,534) =
(2^65,536)-4. H(4,4) > 2^2^65,535. For k >= 3 and n >= 1, H(k,n) >=
2A(k-1,n).

THEOREM 4. Let F be an infinite field. L(F,4,2) > 65,530. L(F,4,3) >
2^65,530. L(F,4,4) > 2^2^65,530. For all n >= 1, L(F,4,n+1) > 2^L(F,4,n).
For k >= 3 and n >= 1, L(F,k,n) > A(k-1,n).