[FOM] An optimal proof-theoretic classification of Hilbert's basis theorem

[Andreas Weiermann]

Dear members of FOM,

this posting is prompted by a FOM posting
of Harvey Friedman from 17.05.1999 about
an application of the Ackermann function
in elementary algebraic geometry.

We obtained the following optimal characterization,
which to my best knowledge is a strengthening
of the known results.


Context: Fix a numbertheoretic function f and a field
K, e.g. the reals.
Choose a natural number n and let 
R=K[X_1,...,X_n].
Choose a natural number d.
In step i choose a homogeneous polynomial
p_i of degree less than or equal to
d+f(i) such that p_i is not in the ideal
generated by p_1,...,p_{i-1}. 
Then this process stops after finitely many
steps due to Hilbert's basis theorem. 
Let F(f,d,n) be the maximal possible length
of this process.

Theorem 1: Let alpha be the inverse Ackermann
function and let f(i) be the alpha(i)-th root of i.
Then F(f,d,n) growth like the Ackermann function
and is not prim rec (in n).

Theorem 2: Fix a natural number k.
Let alpha_k be the inverse function of the
k-th branch of the Ackermann function
and let f(i) be the (alpha_k(i))-th root of i.
Then F(f,d,n) is prim rec (in d,n).

The proof is achieved by a subrecursiontheoretic
analysis of the corresponding well known results for
the function f=id. (I took here advantage of
an exposition by Moreno Socias.)


Best regards,
Andreas Weiermann