Problem 1

First argue that it suffices to prove the result for ${n}$ of the form ${2^k}$. Then proceed by induction: Assume ${(\pi(1), \dots, \pi(n))}$ is a permutation of ${(1, \dots, n)}$ that does not contain a monotone ${3}$-AP. Consider the sequence ${(2\pi(1)-1, 2\pi(2)-1, \dots, 2\pi(n)-1, 2\pi(1), 2\pi(2), \dots, 2\pi(n))}$.

Problem 2

Choose ${n \geq HJ(k,r)}$ and a prime number ${p > k}$. Consider the set

$\displaystyle A = \{a_0 + a_1p + \cdots + a_{n-1}p^{n-1}\colon 0 \leq a_i < k \}.$

Problem 3

Find a way how you can identify ${C^{ns}_t}$ with ${C^s_{t^n}}$, so that a line in ${C^s_{t^n}}$ can be identified with an ${n}$-dimensional subspace of ${C^{ns}_t}$. 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 ${2}$-color the integers. Let ${A}$ be a ${k}$-AP. Calculate the probability that ${A}$ is monochromatic.
• In HW 7, \#3 you computed the number of ${k}$-APs in ${[1,n]}$. Use this to show that the probability that a monochromatic ${k}$-AP exists in ${[1,n]}$ is

$\displaystyle \frac{n^2}{(k-1)2^k} (1+ o(1)).$

• Argue that for large enough ${k}$, ${n = 2^{k/2}}$ will make this less than ${1}$.

Problem 4

Here is a `template’: We show that ${+}$ is primitive recursive.

Then we argue as follows:

• We put ${f(0,y) = g(y)}$ with ${g = p_1}$, the identity. ${g}$ is primitive recursive since ${p_1}$ (projection of a unary function in the first coordinate) is.
• We put ${f(x+1,y) = h(x,y,f(x,y))}$, where ${h = S \circ p_3}$. ${h}$ is primitive recursive since successor ${S}$ and projection ${p_3}$ are, and the primitive recursive functions are closed under substitution (4).
• By closure under primitive recursion (5), ${f}$ is primitive recursive, and ${f}$ 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.