FOM: 71:Ackerman/Algebraic Geometry/1

[Harvey Friedman]

*Manuscript with proofs is available upon request.*

NOTE: This posting stops at the end of section 6. The next posting on
this topic will include sections 7 - 9.

This is a folowup to postings #40 and #43 about the Ackerman function
in algebraic geometry. We have obtained more striking presences of
Ackerman in algebraic geometry that imply the earlier results - at
least as far as asymptotics are concerned.

So this posting is entirely self contained.

We start with two sections that discuss the new presences of Ackerman
in algebraic geometry. We follow this by two sections on our earlier
presences of Ackerman which, in the case of ideals, was extensively
published on by A. Seidenberg. However, he obtained only very poor
upper bounds and no lower bounds. We conclude with two sections on
additional presences of Ackerman in algebraic geometry, the first of
which has been known to us for many years.

THE ACKERMAN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY
by
Harvey M. Friedman
friedman at math.ohio-state.edu
www.math.ohio-state.edu/~friedman/
December 10, 1999
abstract

1. Full subideals.
2. Algebraic approximations.
3. Upper bounds for algebraic approximations.
4. Ascending chains of ideals -  historical notes.
5. Ascending chains of ideals.
6. Decreasing chains of algebraic sets.
7. Degrees in ideal bases.
8. Degrees in polynomial presentations of algebraic sets.
9. Additional formulations.

The Ackerman hierarchy and Ackerman function is defined as follows. Let
f:Z^+ into Z^+ be strictly increasing.  Define f':Z^+ into Z^+ by f'(n)
= f... f(1), where there are n f's.

Define A_1:Z^+ into Z^+ as the doubling function; i.e., A_1(n) = 2n.
For each k >= 1, define A_k+1 = A_k'.

Finally, define A(k,n) = A_k(n), and A(k) = A(k,k). The former is the
binary Ackerman function, and the latter is the unary Ackerman
function.

The following facts about A are useful, and are easily proved in the
order stated.

LEMMA. For all k,n >= 1, n < A_k(n) < A_k(n+1). For all k >= 1 and n
>= 3, A_k(n) < A_k+1(n). For all k,n >= 1, A_k(n) <= A_k+1(n). For
all k >= 1, A_k(1) = 2, A_k(2) = 4, and A_k(3) >= 2^k+1. For all k >=
3, A_k(3) >= A_k-2(2^k) > A_k-2(k-2) = A(k-2). As a function of k,
A_k(3) eventually strictly dominates each A_n, n >= 1.

Ackerman's original definition is similar but is ternary. The growth
rates are the same.

1. FULL SUBIDEALS.

An ideal in a commutative ring with unit is any subgroup which is
closed under multiplication by any ring element. Thus the smallest ideal is
{0}. The ideal {0} is generated by the empty set (and also by {0}).

We say that J is a subideal of I if and only if J is an ideal that is
included in I.

The degree of an ideal in a polynomial ring is the least d such that the
ideal has a set of generators all of which have degree at most d.

Throughout this section, we fix a field F. Let k >= 0 and I be an ideal
in the polynomial ring F[x_1,...,x_k].

For each n >= 0, we let I*n be the ideal generated by the elements of I
of degree n. We let I*<=n be the ideal generated by the elements of I
of degree <= n. For this purpose, we take an empty intersection to be
all of F[x_1,...,x_k].

This basic construction can be studied in the much more general context
of an arbitrary subset I of the polynomial ring. However, we do not
disucss this here.

We refer to the I*n as the full subideals of I. Note that the ideals
{0} and I are full subideals of I provided I is not the whole
polynomial ring. If I is the whole polynomial ring then its only full
subideal is itself.

THEOREM 1.1. For all n >= 0, I*n = I*<=n. If I*n has degree d then I*n
= I*d. The full subideals of I form a chain under inclusion of length
at most deg(I)+1, with at most one exact subideal of any given degree
in the interval [0,deg(I)].

Note that there may be one or more missing full subideals of I. I.e.,
there may be at most deg(I) full subideals of I.

We call I rich if and only if it has a full complement of full
subideals - i.e., it has deg(I)+1 full subideals.

THEOREM 1.2. I is rich if and only if for all 0 <= n <= deg(I), I*n has
degree n.

THEOREM 1.3. Every full subideal of every rich ideal is a rich ideal.
The degrees of rich ideals in F[x_1,...,x_k] form an initial segment of
the nonnegative integers.

THEOREM 1.3. The degrees of the rich ideals of F[x_1,...,x_k] form a
finite initial segment of the nonnegative integers. The union of these
finite initial segments over all fields F is still finite.

Upper bounds for Theorem 1.3 follow from upper bounds in section 5.

Lower bounds for Theorem 1.3 are obtained by the following
construction, even for monomial ideals in any F[x_1,...,x_k].

Let z_1,...,z_t be elements of N^k, where

1) for each i, the sum of the coordinates of z_i is i;
2) for all i < j, it is not the case that z_i <= z_j coordinatewise.

For each z in N^k, let M(z) be the monomial x_1^z_1 x_2^z_2 ...
x_k^z_k.

Let I be the ideal in F[x_1,...,x_k] generated by M(z_1),...,M(z_t).

LEMMA 1.4. The ideal I generated by M(z_1),...,M(z_t) is rich. In
particular, for all 0 <= n <= t, I*n is the ideal generated by
M(z_1),...,M(z_n).

We had analyzed such sequences z_1,...,z_t from N^k already in the
1980's as a spinoff of our finite forms of Kruskal's theorem - and
finite statements associated with well quasi orders. As k grows, the
longest length of such sequences from N^k grows like Ackerman's
function, eventually strictly dominating all primitive recursive
functions, and being bounded by Ackerman's function at a constant multiple
of the argument. Much more exact estimates can be obtained with additional
work.

2. ALGEBRAIC APPROXIMATIONS.

Ideals are fine for algebraists. But geometers and others may prefer
algebraic sets, particularly in the reals or complexes.

Let F be a field and k >= 1. An algebraic subset of F^k is the set of
simultaneous zeros of a nonempty finite set of polynomials in k
variables with coefficients from F. The degree of an algebraic set is
the least d such that it is the set of simultaneous zeros of a nonempty
finite set of polynomials in k variables each of which have degree at most d.

***NOTE: This is not the most common notion of degree for algebraic geometry.
There is a close relationship between the degree concepts, and we will
discuss what happens to our results when alternative definitions of degree are
used - but in later postings. In particular, we already know that all
positive results and Ackerman upper bounds hold for a very wide range of
notions of degree including those used most commonly in algebraic geometry.
The issue is one of lower bounds. Do our lower bound results hold with more
sophisticated notions of degree?***

We say that an algebraic set E is defined by a set of polynomials if
and only if it is the set of simultaneous zeros of that set of
polynomials.

Throughout this section, we fix an infinite field F.

Let A be an algebraic subset of F^k. For each n >= 0, we let A*n be the
least algebraic superset of A of degree n. We let A*<=n be the
intersection of all algebraic supersets of A of degree <= n. For this
purpose, we take an empty intersection to be all of F^k.

We can apply this basic construction more generally to an arbitrary
subset of F^k. However, we do not discuss this here.

THEOREM 2.6. Let A be an algebraic subset of F^k, F infinite. For all n
>= 0, A*n = A*<=n.

THEROEM 2.7. Let A be an algebraic subset of F^k, F infinite. If A*n
has degree d then A*n = A*d. The algebraic approximations of A form a
chain under inclusion of length at most deg(A)+1, with at most one
algebraic aproximation of any given degree in the interval [0,deg(A)].

Note that there may be one or more missing algebraic approximations of
A. I.e., there may be at most deg(A) algebraic approximations of A.

We call A rich if and only if it has a full complement of algebraic
approximations - i.e., it has deg(A)+1 algebraic approximations.

THEOREM 2.8. A is rich if and only if for all 0 <= n <= deg(A), A*n has
degree n.

THEOREM 2.9. Every algebraic approximation of every rich algebraic set
is a rich algebraic set. The degrees of rich algebraic subsets of F^k
form an initial segment of the nonnegative integers.

THEOREM 2.10. The degrees of rich algebraic subsets of F^k form a
finite initial segment of the nonnegative integers. The union of these
finite initial segments over all fields F is still finite.

3. LOWER BOUNDS FOR ALGEBRAIC APPROXIMATIONS.

Lower bounds for Theorem 2.10 require a new construction.

An interesting aspect of these lower bounds is that we obtain them by
considering finite sets only. Finite sets are automatically algebraic,
but their degree is generally an intricate matter.

THEOREM 3.13. Let k >= 1 and F be an infinite field. There is a rich
finite subset of F^k+6 of degree A_k(k).

THEOREM 3.14. Let k >= 1 and F be a sufficiently large finite field. There
is a rich subset of F^k+6 of degree A_k(k).

In fact, the finite field need only be a little bit larger than A_k(k),
which we will eventually take the trouble to make precise.

4. ASCENDING CHAINS OF IDEALS - HISTORICAL NOTES.

The results here about ascending chains of ideals were obtained in the
80's and discussed here in postings #40 and #43.

Seidenberg had earlier intensively investigated the same statement
about ascending chains of ideals in the following papers:

A. Seidenberg, An elimination theory for differential algebra, Univ.
Calif. Pubs. Math. 3 (1956), 31-65.

A. Seidenberg, On the length of a Hilbert ascending chain, Proc. AMS,
Vol. 29, No. 3, August 1971, 443-450.

A. Seidenberg, Constructive proof of Hilbert's theorem on ascending
chains, Trans. AMS, Vol. 174, December 1972, 305-312.

The first paper is quoted in the last two and has a partial result.

Actually, his is more general in that he considers arbitrary bounds on
the degrees of the ideals. I had also dealt with this formulation but did
not report it in #40 and #43. Of course, my work is all after Seidenberg.

Seidenberg proves no lower bounds. Also, he states a multi recursive
bound in each dimension k, rather than my primitive recursive bounds. He
states only primitive recursive bounds in dimension <= 2, and states that
primitive recursivity for dimension >= 3 is "doubtful." Also, Seidenberg
does not consider corresponding statements about algebraic sets, which
of course follows from these statements about ideals.

Seidenberg also discusses these chains in

A. Seidenberg, Survey of constructions in Noetherian rings, Univ. of
Cal. Berkeley.

A. Seidenberg, Constructions in algebra, Trans. AMS, Vol. 197, 1974,
273-313.

I think he also disucces it in a fifth paper and probably others, entitled

"What is Noetherian" but I haven't got a hold of a copy of that paper.

Seidenberg's theorem can be viewed as a kind of finite form of the
Hilbert basis theorem. He himself viewed it as a constructive form of the
Hilbert basis theorem.

**Our original finite forms of Kruskal's theorem in 1981-82 are to
Kruskal's theorem as Sidenberg's theorem is to the Hilbert basis
theorem. Bounds on the degrees become bounds on the number of vertices of the
trees. It is interesting to note that Seidenberg and I had the same idea for
getting finite forms in the two contexts - Hilbert's basis theorem and
Kruskal's theorem - namely to look at finite sequences with bounds placed
on the terms. **

Yet we searched hard for a good finite form of Kruskal's theorem invovlinga
single tree rather than a sequence of trees. We were quite successful with
this, and reported the results in posting #27, together with sketches of
the proofs. After some experience with lecturing on this, my favorite is:

1) if T is a sufficiently tall thin tree, there exists 1 <= i < j <= hgt(T)
and an inf preserving embedding from T[<=i] into T[<=j] which maps T[i]
into T[j]. I.e., if T is a sufficiently tall tree of valence <= k, then
there exists ... .

It can be stated for arbitrary finite trees as follows.

2) for all k there exists n such that if T is any finite tree of valence <=
k, there exists 1 <= i < j <= n and an inf preserving embedding from T[<=i]
into T[<=j] which maps T[i] into T[j].

So it makes sense to search for theorems about a single ideal. We have
found such a theorem. See section 1. We have also found theorems about a
single algebraic set. See section 2.

5. ASCENDING CHAINS OF IDEALS.

We take an ideal (in a commutative ring with unit) to be any subgroup
which is closed under multiplication by any ring element. Thus the smallest
ideal is {0}. The ideal {0} is generated by the empty set (and also by {0}).

The degree of an ideal in a polynomial ring is the least d such that the
ideal has a set of generators all of which have degree at most d.

Here is Seidenberg's theorem on ascending chains:

THEOREM 5.1. For all k,p >= 1 there exists n >= 1 such that the
following holds. For any field F, there is no strictly ascending sequence of
ideals in F[x_1,...,x_k] of length n, where the i-th ideal has degree at most
p+i (i.e., a set of generators each of which has degree at most p+i).

Actually, Seidenberg states this for any bound on the degree of the
i-th ideal. Exactly analogous results hold. We prefer to state this as
above because of our interest in lower bounds and the elementary nature of
the result.

Seidenberg established a primitive recursive bound only for k <= 2,
and opently doubted whether a primitive recursive bound exists for even k =
3. He established no lower bounds.

We first wish to reduce this to a more manageable form. There is a
reasonable function G(k,i) such that for any field F, every ideal in
F[x_1,...,x_k] of degree at most i has a set of generators, each of
degree at most i, where there are at most G(k,i) generators. This function is
obtained by the obvious linear algebra.

LEMMA 5.2. For all k,p >= 1 there exists n >= 1 such that the
following holds. Let F be a field.  P[i,j] be a doubly indexed set of
polynomials
in F[x_1,...,x_k], where i,j satisfy 1 <= i <= n and 1 <= j <=
G(k,p+i). Assume P[i,j] has degree at most p+i. Then there exists 1 <= i <= n
such that for all 1 <= j <= G(k,p+i), P[i,j] lies in the ideal generated
by the P[i',j'] where i' < i. Furthermore, there exists 1 <= i <= n such
that for all 1 <= j <= G(k,p+i), P[i,j] can be written as an ideal element
from the P[i',j'], i' < i, using polynomial coefficients of degrees at most n.

It is interesting to also consider

THEOREM 5.3. For all k,p >= 1 there exists n >= 1 such that the
following holds. For any field F, there is no strictly ascending sequence of
ideals in F[x_1,...,x_k] of length n, where the i-th ideal has degree p+i.

Upper bounds for Theorem 5.2 give upper bounds for Theorem 5.3 and for
Theorem 5.1. The lower bound for Theorem 5.3 also follows immediately from
those given in section 1.

We now give primitive recursive bounds for each k, in Theorem 5.2,
using more logic.

Consider the Pi-0-2 sentence

*for all k,p >= 1 there exists n >= 1 such that T[k,p,n] is
inconsistent.*

Fix k. For any p, the least size of an inconsistency in T[k,p,n] is
clearly an upper bound on the relevant number in Theorem 1.1, because already n
is such an upper bound. But that least size is a primitive recursive function
of p because the above statement is provable in WKL_0 for any given k.

This is because the compactness theorem, the completeness theorem, and the
Hilbert
basis theorem are all provable in WKL_0

{In the manuscript with proofs, I formulate an appropriate first order
theories T[k,p,n]}.

6. CHAINS OF ALGEBRAIC SETS - PRIMITIVE RECURSIVE BOUNDS.

Let F be a field and k >= 1. An algebraic subset of F^k is the set of
simultaneous zeros of some finite set of polynomials in k variables
over F.

The degree of an algebraic set is taken here to mean the least d such
that it is the set of simultaneous zeros of some finite set of polynomials
in k variables of degree at most d.

THEOREM 6.1. For all k,p >= 1 there exists n >= 1 such that the
following holds. For any field F, there is no strictly decreasing sequence of
algebraic sets in F^k of length n, where the i-th algebraic set has
degree at most p+i (i.e., is the zero set of a finite system of k variable
polynomials over F of degree at most p+i).

Theorem 6.1 follows immediately from Theorem 5.1, and our upper bounds
for Theorem 5.1 also serve as upper bounds for Theorem 6.1.

It is interesting to also consider

THEOREM 6.2. For all k,p >= 1 there exists n >= 1 such that the following
holds. For any field F, there is no strictly ascending sequence of ideals
in F[x_1,...,x_k] of length n, where the i-th algebraic set has degree
p+i.

Upper bounds for Theorem 6.2 obviously give upper bounds for Theorem
5.3.

Lower bounds for Theorem 6.2 follow immediately from those given in
section 3.

**********

This is the 71st 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  5:11PM
43:More Enormous Integers/AlgGeom  5/25/99  6:00PM
44:Indiscernible Primes  5/27/99  12:53 PM
45:Result #1/Program A  7/14/99  11:07AM
46:Tamism  7/14/99  11:25AM
47:Subalgebras/Reverse Math  7/14/99  11:36AM
48:Continuous Embeddings/Reverse Mathematics  7/15/99  12:24PM
49:Ulm Theory/Reverse Mathematics  7/17/99  3:21PM
50:Enormous Integers/Number Theory  7/17/99  11:39PN
51:Enormous Integers/Plane Geometry  7/18/99  3:16PM
52:Cardinals and Cones  7/18/99  3:33PM
53:Free Sets/Reverse Math  7/19/99  2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry  8/27/99  3:01PM
57:Fixpoints/Summation/Large Cardinals  9/10/99  3:47AM
57':Restatement  9/11/99  7:06AM
58:Program A/Conjectures  9/12/99  1:03AM
59:Restricted summation:Pi-0-1 sentences  9/17/99  10:41AM
60:Program A/Results  9/17/99  1:32PM
61:Finitist proofs of conservation  9/29/99  11:52AM
62:Approximate fixed points revisited  10/11/99  1:35AM
63:Disjoint Covers/Large Cardinals  10/11/99  1:36AM
64:Finite Posets/Large Cardinals  10/11/99  1:37AM
65:Simplicity of Axioms/Conjectures  10/19/99  9:54AM
66:PA/an approach  10/21/99  8:02PM
67:Nested Min Recursion/Large Cardinals  10/25/99  8:00AM
68:Bad to Worse/Conjectures  10/28/99  10:00PM
69:Baby Real Analysis  11/1/99  6:59AM
70:Efficient Formulas and Schemes  11/1/99  1:46PM