Skip to content

Hints Homework 9

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 and Lecture Notes 10/24

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

History of computability and fast growing functions

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 🙂


Hints Homework 8

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

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

Homework 8

Homework 8 (due Oct 31) is available.

Lecture Notes 10/17

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