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<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 Comment » | 305: Abstract Algebra I | Tagged: , , | Permalink
Posted by andrescaicedo

305 – A lower bound for n(3)

February 14, 2012

This continues the previous post on Friedman’s theorem.

I want to give a brief idea of the size of Friedman’s n(3), as defined on homework 2. The reference for what follows is

  • Harvey Friedman, Long finite sequences,  J. Combin. Theory Ser. A, 95 (1) (2001), 102–144.

Recall that n(3) is the largest possible size n of a sequence x_1 x_2 x_3\dots x_{n-1} x_n with property *, all of whose terms are 1, 2, or 3. Here, to have property * means that if i<j\le n/2, then the sequence x_i x_{i+1}\dots x_{2i} is not a subsequence of the sequence x_j x_{j+1}\dots x_{2j}.

In lecture we gave an example of such a sequence, of length 216, namely

12^2131^73^21313^813^513^{20}1^23^{53}13^{108},

where we use exponential notation to indicate the number of times a symbol appears consecutively, so the sequence begins

12213111111133131333333331\dots

Actually, n(3) is much larger than 216. We know it is finite but, as Friedman mentions in his paper, it is an incomprehensibly large number. To explain this, we should mention the Ackermann hierarchy of functions. These are functions A_1,A_2,\dots, with each A_i:{\mathbb Z}^+\to{\mathbb Z}^+ a strictly increasing function.

Define A_1(n)=2n. Also, set

A_{k+1}(n)=A_k(A_k(\dots(A_k(1))\dots)),

where there are n occurrences of A_k.

This is perhaps best understood by computing a few examples. We have A_1(1)=2, A_1(A_1(1))=A_1(2)=4=2^2, A_1(A_1(A_1(1)))=A_1(4)=8=2^3 and, by an easy induction, A_2(n)=2^n.

Now, A_2(1)=2, A_2(A_2(1))=A_2(2)=2^2, A_2(A_2(A_2(1)))=A_2(2^2)=2^{2^2} and, in general, A_3(n) is an exponential tower of 2s of height n.

The descriptions become more complicated now. For example, A_4(n) is an exponential tower of 2s, but its height is itself an exponential tower of 2s (of height n). For example,

\displaystyle A_4(4)=2^{\vdots ^2},

where the tower has height \displaystyle 2^{2^{2^2}}=65536.

Let me now quote from Friedman’s paper:

I submit that A_4 ( 4) is a ridiculously large number, but it is not an incomprehensibly large number. One can imagine a tower of 2’s of a large height, where that height is 65,536, and 65,536 is not ridiculously large.

However, if we go much further, then a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible. These higher levels of largeness blur, where one is unable to sense one level of largeness from another.

For instance, A_4( 5 ) is an exponential tower of 2’s of height A_4( 4 ).

It seems safe to assert that, say, A_5( 5 ) is incomprehensibly large. We propose this number as a sort of benchmark. In Section 4 we prove that n( 3 ) >A_7( 184 ), which is considerably larger.

Friedman actually goes much further than this. Using computer data provided by Randall Dougherty, Friedman proves in the last section of the paper that

n(3)>A_{7198}(158386).

For all I know, this could still be very far from the actual value of n(3). And I do not know a reasonable description of an upper bound.

In technical terms, Friedman proves that the function n(k) is not primitive recursive, and actually grows much faster than the usual examples of recursive functions that are not primitive recursive. He also describes a function H (a member of the so-called Hardy hierarchy) that grows faster than n(k). This means that n(k)<H(k) for all sufficiently large k, but the argument does not give a specific bound when k=3.

3 Comments | 305: Abstract Algebra I | Tagged: , , | Permalink
Posted by andrescaicedo

305 – Friedman’s theorem

February 4, 2012

I am sketching here a proof of Harvey Friedman‘s result mentioned in lecture. The proof will not be needed for the rest of the course, but it is a nice argument that you may enjoy reading.

Recall that a sequence x_0 x_1 \dots x_n has property * iff there are no integers i<j\le n/2 such that the sequence x_i x_{i+1}\dots x_{2i} is a subsequence of x_j x_{j+1}\dots x_{2j}.

Here, we are using the notion of subsequence where terms must appear in order but are not required to be consecutive: A sequence a_1 a_2\dots a_k is a subsequence of b_1 b_2\dots b_l iff there are indices 1\le i_1<i_2<\dots<i_k\le l such that

b_{i_1}=a_1,b_{i_2}=a_2,\dots,b_{i_k}=a_k.

Theorem (H. Friedman, 2001). For any positive integer k there is a longest finite sequence x_1 x_2\dots x_n in k letters with property *.

(Of course, once we know that the theorem is true, we can proceed as in lecture and define n(k) as the length of this longest sequence.)

Read the rest of this entry »

2 Comments | 305: Abstract Algebra I | Tagged: , , | Permalink
Posted by andrescaicedo

305 – Homework II

February 3, 2012

This homework set is due Wednesday, February 15th, at the beginning of lecture, but feel free to turn it in earlier if possible.

Read the rest of this entry »

6 Comments | 305: Abstract Algebra I | Tagged: , | Permalink
Posted by andrescaicedo