**Problem 1**

First argue that it suffices to prove the result for of the form . Then proceed by induction: Assume is a permutation of that does not contain a monotone -AP. Consider the sequence .

**Problem 2**

Choose and a prime number . Consider the set

**Problem 3**

Find a way how you can identify with , so that a line in can be identified with an -dimensional subspace of . Then apply the Hales-Jewett Theorem.

Homework 9 (due 11/07) and the lecture notes for 10/24 (Hales-Jewett Theorem, Part I) are available.

The first part of the Wikipedia article on the Church-Turing Thesis gives an overview over the history of computability discussed in class.

Scott Aaronson’s “Who can name the bigger number” is a really nice introduction to fast-growing functions.

Finally, here is the promised photo from Niagara Falls ðŸ™‚

**Problem 3**

Proceed as follows:

- Randomly -color the integers. Let be a -AP. Calculate the probability that is monochromatic.
- In HW 7, \#3 you computed the number of -APs in . Use this to show that the probability that a monochromatic -AP exists in is
- Argue that for large enough , will make this less than .

**Problem 4**

Here is a `template’: We show that is primitive recursive.

Then we argue as follows:

- We put with , the identity. is primitive recursive since (projection of a unary function in the first coordinate) is.
- We put , where . is primitive recursive since successor and projection are, and the primitive recursive functions are closed under substitution (4).
- By closure under primitive recursion (5), is primitive recursive, and defines .

Lecture Notes 10/19 (Van der Waerden, Part II) are available.

Homework 8 (due Oct 31) is available.

Typeset Lecture Notes for 10/17 (Van der Waerden’s Theorem) are available.