## 305 – A brief update on n(3)

April 12, 2012

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, 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.