MATHNOTES

This is a collection of writeups of theorems and other things, in math, I find interesting and felt inspired to type in my notes for.

1. (In progress) An exposition of the Topological of van der Warden's theorem. ERGODIC.PS. ERGODIC.PDF.

2. An Exposition of Roth's Theorem which states that `big' sets of integers must contain arithmetic progressions of size 3. Formally          $(\forall \lambda>0)(\exists n_0\in N)(\forall n\ge n_0)(\forall A\subseteq [n])[\vert A\vert\ge \lambda n \rightarrow \hbox{$A$ has a 3-AP}].$ We present a proof that is essentially due to Szemeredi. SZ.PS. SZ.PDF.

3. The Weak Prime Number Theorem WEAKPNT.PS. WEAKPNT.PDF. For information on the Prime Number Theorem see PNT

4. An Application of Ramsey Theory to Communication Complexity PUDLAK.PS PUDLAK.PDF. This is a writeup of part of Pudlak's paper An application of Hindman's Theorem to a problem on Communication Complexity

5. Polynomials with Minimal Deviance- Chebyshev Polynomials CHEBY.PS. CHEBY.PDF.

6. Primality in P For the original paper see PRIMES. For a write up that is suitable for undergrads (but leaves out some of the proofs) see PRIMESHANDOUT.PS. PRIMESHANDOUT.PDF.

7. Van Der Waerden's Theorem- the k=3 Case. For all c there exists W(c)} such that, if you were to c-color {1,...,W(c), then there would exist a sequence of three numbers, in arithmetic progression, that are the same color! We prove this in detail in VDW3.PS. VDW3.PDF. More generally still, for all c and for all k there exists W(c,k) such that, if you were to c-color {1,...,W(c,k)}, then there would exist a sequence of k numbers, in arithmetic progression, that are the same color!

8. An Exposition of the Main Theorem in Enumerations of the Kolmogorov Function Authors of paper: Beigel, Buhrman, Fejer, Fortnow Grabowski, Longpre, Muchnik, Stephan, Torenvliet. Let $C(x)$ be the shortest description of $x$. It is known that $C$ is undecidable (the proof of this is also included). But what if we just want to, given $x$, enumerate $\le 17$ possibilities, one of which is $C(x)$. This manuscript shows that this cannot be done. KOLM.PS. KOLM.PDF.

9. Equations and Infinite Colorings An Exposition by Stephen Fenner and William Gasarch Consider the following statement which we denote $S$: For every $\omega$-coloring of $R$ there exists $e_1,e_2,e_3,e_4$ that are all the same color such that $e_1+e_2=e_3+e_4$. Is $S$ true or false? This exposition shows that $S$ is true iff $CH$ is false. Hence $S$ is true iff $CH$ is false. Hence $S$ is ind of ZFC. RADOZFC.PS. RADOZFC.PDF.

10. Sum-Product Theorems An Expostion by Bill Gasarch We present proofs of the following two theorems:
    1. If $A$ is a set of $n$ reals then either $\vert A+A\vert$ or $\vert A\cdot A\vert$ is $\Omega(n^{5/4})$.
    2. If $A$ is a set of $n$ reals then either $\vert A+A\vert$ or $\vert A\cdot A\vert$ is $\Omega(n^{14/11}/(\log n)^{3/11})$.
    SUMPRODUCT.PS. SUMPRODUCT.PDF.