## Section14.6William 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]

### Subsection14.6.1William 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.

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?

1. It has the it is easier proof a harder theorem vibe 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{.}$

2. The proof is elementary, and can be taught to high school students.

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

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

5. 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]

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?

1. It has the it is easier proof a harder theorem vibe as well.

2. The proof is elementary, and can be taught to high school students. (Thought harder than vdW.)

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

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

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

6. (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]

### Subsection14.6.2Reflection

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.

### References14.6.3References

[1]

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

[2]

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

[3]

William Gasarch. Personal Communication. February 6, 2024.

[4]

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

[5]

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.