## Section 14.6 William Ian Gasarch

William Ian Gasarch is an American computer scientist known for his work in computational complexity theory, computability theory, computational learning theory and Ramsey theory.

Professor Gasarch received his doctorate in computer science from Harvard in 1985, under the supervision of Professor Harry R. Lewis. He is currently a professor at the university of Maryland Department of Computer Science with an affiliate appointment in mathematics. [14.6.3.1]

In 2020, Dr. Gasarch co–authored the book *Mathematical Muffin Morsels: Nobody Wants a Small Piece*. [14.6.3.2]

### Subsection 14.6.1 William Gasarch's favourite proof

Dr. Gasarch sent us a pdf file with proofs of two theorems: van der Waerden's theorem, [14.6.3.4] , and the polynomial van der Waerden theorem, [14.6.3.5]. The pdf file with Dr. Gasarch's proofs is available HERE.

###### Theorem 14.6.1. van der Waerden's Theorem.

For all \(k,c\in \mathbb{N}\) there exists a number \(W\) such that for \(c\)–colourings \(\chi:[W]\to[c]\text{,}\) there exists \(a,d\n\mathbb{N}\) such that \(\chi(a)=\chi(a+d)=\cdots =\chi(a+(k-1)d)\text{.}\)

Gasarch appreciates the original proof by van der Waerden for several reasons:

I like the original proof by van der Waerden, even though the proof by Shelah gives better bounds. Why do I like it?

It has the

it is easier proof a harder theoremvibe in that it is easier to prove it for all \((k,c)\) rather than (say) proving that:For all \(k\in \mathbb{N}\) there exists \(W\) such that, for all \(2\)–colourings \(\chi: [W]\to [2]\text{,}\) there exist \(a,d\n\mathbb{N}\) such that \(\chi(a)=\chi(a+d)=\cdots =\chi(a+(k-1)d)\text{.}\)The proof is elementary, and can be taught to high school students.

It serves as an example of proof by induction on an ordering other than natural numbers, specifically the \(\omega^2\) ordering.

The bounds are enormous. This is a good way to introduce the notions of primitive recursion and Ackerman's function to people. (Though be careful to say that this is the BOUND FROM THE PROOF and is not the real bound since Shelah and later Gowers got prim rec bounds.)

That the bounds (and even those of Shelah and Gowers) seem very far from the few actual numbers that are known is a humbling lesson on how in math we don?t know everything. [14.6.3.3]

###### Theorem 14.6.2. The Polynomial van der Waerden Theorem.

Fix \(c\in \mathbb{N}\) and \(P\subset \mathbb{Z}[x]\) finite, with \((\forall p\in P)~[p(0)=0]\text{.}\) Then there exists \(W=W(P,c)\) such that, fo all \(c\)–colourings \(\chi:[W]\to[c]\text{,}\) teher are \(a,d\in [W]\text{,}\) such that the following set is monochromatic: \(\{a\}\cup\{a+p(d):p\in P\}\text{.}\)

In Professor Gasarch's words

I like the purely combinatorial proof by Walters even though (again!) the proof by Shelah gives better bounds. Why do I like it?

It has the

it is easier proof a harder theoremvibe as well.The proof is elementary, and can be taught to high school students. (Thought harder than vdW.)

It is a good example of proof by induction on an ordering other than natural numbers. It is on the \(\omega^\omega\) ordering.

The bounds are enormous, though this is not as impressive having seen vdW. The bounds are not that much bigger than vdW.

That the bounds (and even those of Shelah and Gowers) seem very far from the few actual numbers that are known is a humbling lesson on how in math we don?t know everything.

(Personal) The existence of an elementary proof of the Poly VDW theorem does not seem to be well known, so I've gotten a kick out of telling Ramsey Theorists who are much smarter than me of its existence. [14.6.3.3]

### Subsection 14.6.2 Reflection

We are both impressed and touched by Professor Gasarch's willingness to share his knowledge with us. The way how he has reflected about the two proofs made us appreciate even more what we have learned in our math classes.

### References 14.6.3 References

William Gasarch. (2024, January 17). Wikipedia. Retrieved April 7, 2024, from Wikipedia

Gasarch, W., Metz, E.,Prinz, J., Smolyak, D. (2020). *Mathematical Muffin Morsels: Nobody Wants A Small Piece*. World Scientific.

William Gasarch. Personal Communication. February 6, 2024.

B. L. van der Waerden, *Beweis einer Baudetschen Vermutung*, Nieuw Archief voor Wisjunde, vol. 15, pp, 212–216, 1927

Walters, M. (2000). *Combinatorial Proofs of the Polynomial van der Waerden Theorem and the Polynomial Hales–Jewett Theorem*. J. London Math. Soc. (2) 61, pp. 1-12.