305 – Friedman’s theorem

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

We will prove the theorem in two stages: Fix k, and consider only sequences in k letters.

  • We will show that there is no infinite sequence with property *, and
  • We will show that this implies that there must be a longest finite sequence with property *.

I. Finiteness implies a longest sequence.

I will start with the second stage, as it is easier. This is a typical application of König’s lemma. (Here are some notes I wrote on this result:

But I will present the argument in a self contained way.)

The idea is simple. Suppose towards a contradiction that there are arbitrarily large finite sequences with property *. We use this to prove that there is an infinite such sequence. To simplify notation, “sequence” means “sequence with property *” throughout this section.

Clearly, if {\mathbf x} is a sequence, then any initial segment of {\mathbf x} is also a sequence (i.e., it has property * as well). It follows that there are sequences of all finite lengths. Now, since each term in the sequences is one of only k possible letters, the number of sequences of any fixed finite length must be finite. Introduce a (partial) order on sequences by saying that {\mathbf x}<{\mathbf y} iff {\mathbf x} is a proper initial segment of {\mathbf y}.

Now we define an infinite sequence by a recursive argument: Since there are infinitely many sequences and only finitely many “sequences of length 1”, at least one of these sequences, say x_1, must be smaller than infinitely many sequences. Otherwise, for each sequence of length 1 there are only finitely many larger sequences, but then there are only finitely many sequences in total, contradicting that there are sequences of arbitrarily large size.

Now restrict to the sequences that are larger than x_1. Since there are infinitely many of them, and only finitely many have size 2, among them there must be at least one, say x_1x_2, that is smaller than infinitely many other sequences. Continue this way: Once we have identified x_1 x_2\dots x_n smaller than infinitely many sequences, pick among these one of length n+1, say x_1 x_2\dots x_n x_{n+1}, that itself is smaller than infinitely many other sequences.

This process generates an infinite sequence x_1 x_2 \dots, and we are done: We have reached a contradiction. It follows that there cannot be arbitrarily large sequences, and therefore there must be some of largest possible size.

II. There are no infinite sequences with property *

Now we must argue that no infinite sequence in k letters can have property *. The argument makes use of Higman’s lemma, a basic result from the theory of well-quasi-orders, or wqo theory but, again, I keep the presentation self contained.

It turns out that it pays off to prove a stronger result. What we show is the following:

Theorem. Let k>0 be a positive integer. Suppose we are given a infinite sequence {\mathbf y}_1,{\mathbf y}_2,\dots, where each {\mathbf y}_i is itself a finite sequence, all of its terms coming from \{1,2,\dots,k\}. Then there are i<j such that {\mathbf y}_i is a subsequence of {\mathbf y}_j.

Note that the theorem immediately implies that there is no infinite sequence in k letters with property *, because if x_1 x_2\dots is a sequence, and each x_i is one of 1,2,\dots,k, we can define {\mathbf y}_i=x_i x_{i+1}\dots x_{2i}, and the theorem tells us precisely that x_1 x_2\dots does not have property *.

To prove the theorem, we proceed by contradiction. Call a sequence {\mathbf y}_1,{\mathbf y}_2,\dots, a bad sequence iff it contradicts the theorem, i.e., iff each {\mathbf y}_i is a finite sequence where each term comes from \{1,2,\dots,k\}, and no {\mathbf y}_i is a subsequence of a {\mathbf y}_j with i<j. So, towards a contradiction, assume that there is a bad sequence. Note that in no bad sequence we can have an empty {\mathbf y}_i.

Define {\mathbf y}_1 as a finite sequence of minimal length that starts a bad sequence. Now define {\mathbf y}_2 as a finite sequence of minimal length among the second terms of bad sequences that begin with {\mathbf y}_1. Then define {\mathbf y}_3 as a finite sequence of minimal length among the third terms of bad sequences that begin with {\mathbf y}_1,{\mathbf y}_2. Continue this way, so that a “minimal bad sequence”

{\mathcal Y}=({\mathbf y}_1,{\mathbf y}_2,\dots)

is produced.

Since the {\mathbf y}_i are non-empty, and their terms come from the finite set \{1,2,\dots,k\}, it must be the case that there are infinitely many {\mathbf y}_i that begin with the same term, say {\mathbf y}_{k_1},{\mathbf y}_{k_2},{\mathbf y}_{k_3},\dots

Define {\mathbf z}_i as the result of removing from {\mathbf y}_{k_i} this first term. Note that

{\mathcal Z}=({\mathbf y}_1,{\mathbf y}_2,\dots,{\mathbf y}_{k_1-1},{\mathbf z}_1,{\mathbf z}_2,{\mathbf z}_3,\dots)

is also a bad sequence: If i<k_1 and {\mathbf y}_i is a subsequence of {\mathbf z}_a, then it is also a subsequence of {\mathbf y}_{k_a}, contradicting that {\mathcal Y} is a bad sequence. On the other hand, if {\mathbf z}_i is a subsequence of {\mathbf z}_j for some i<j, then {\mathbf y}_{k_i} is a subsequence of {\mathbf y}_{k_j}, as their first term is the same, and again this contradicts that {\mathcal Y} is a bad sequence.

But now we have a problem, as the k_1-st term of {\mathcal Z} is shorter than {\mathbf y}_{k_1}, contradicting the way the sequence {\mathcal Y} was constructed. This contradiction completes the proof.

III. A closing remark

The results of Sections I and II prove Friedman’s theorem. Although the argument is very nice and actually simpler than one might have expected, it is also somewhat unsatisfactory, since the proof is highly nonconstructive. The problem with this is that, even though we now know that n(k) is a well defined finite number, the proof gives us no clue as to how large it must be, and it is not at all clear how to modify the argument in order to extract from it an upper bound for the size of n(k).

Friedman’s result comes from

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

Here is a link to the review of the paper on MathSciNet. As mentioned on Homework II, you may want to wait until after you have turned in your homework before looking at the paper (or the review), in order not to spoil problem 6.

Advertisements

2 Responses to 305 – Friedman’s theorem

  1. […] is much larger than 216. We know it is finite but, as Friedman mentions in his paper, it is an incomprehensibly large number. To […]

  2. […] This continues the previous post on Friedman’s theorem. […]

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: