305 – A brief update on n(3)

This continues the previous post on A lower bound for n(3).

Only recently I was made aware of a note dated November 22, 2001, posted on Harvey Friedman‘s page, “Lecture notes on enormous integers”. In section 8, Friedman recalls the definition of the function n(k), the length of the longest possible sequence x_1,x_2,\dots,x_n from \{1,2,\dots,k\} with the property that for no i<j\le n/2, the sequence x_i,x_{i+1},\dots,x_{2i} is a subsequence of x_j,x_{j+1},\dots,x_{2j}.

Friedman says that “A good upper bound for n(3) is work in progress”, and states (without proof):

Theorem. n(3)\le A_k(k), where k=A_5(5).

Here, A_1,A_2,\dots are the functions of the Ackermann hierarchy (as defined in the previous post).

He also indicates a much larger lower bound for n(4). We need some notation first: Let A(m)=A_m(m). Use exponential notation to denote composition, so A^3(n)=A(A(A(n))).

Theorem. Let m=A(187196). Then n(4)>A^m(1).

He also states a result relating the rate of growth of the function n(\cdot) to what logicians call subsystems of first-order arithmetic. A good reference for this topic is the book Metamathematics of First-order Arithmetic, by Hájek and Pudlák, available through Project Euclid.

There is a recent question on MathOverflow on this general topic.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: