Proof. Let $p$ be a huge prime, $p>\sum |a_i|$. I give to the number $x$ the colour $e(x)\in \{0,\dots ,p-1\}$. Then by assumption, there exists $x_1,\dots ,x_n$ of the same colour such that $\sum a_i{x}_i=0$.

In symbols, let $t=\min \{t(x_1),\dots ,t(x_n)\}$, $I=\{i:t(x_i)=t\}$. When we sum ${\sum }_{i\in [n]}{a}_i{x}_i=0$ and we look at the last digit $modp$, we get ${\sum }_{i\in I}{a}_{i}d=0$, where $d$is the colour of our $x_i$s. Then $d\left({\sum }_{i\in I}{a}_i\right)\equiv 0(modp)$. Then ${\sum }_{i\in I}{a}_i=0$ (and note $I$ is non-empty). □

Proof. If $\lambda =0$ then nothing to show.

If $\lambda <0$ then $z-\lambda y=x$, so these are equivalent.

Assume $\lambda >0$, $\lambda =\frac{r}{s}$, $r,s\in \mathbb{N}$.

Seek solution to $x+\frac{r}{s}=z$. Let $c:\mathbb{N}\to [k]$ be a finite colouring. Prove this by induction on $k$.

$k=1$ trivial.

Assume this is true for $k-1$ and we want to show it for $k$. Assume $n$ is suitable for $k-1$. We show that $W(k,nr+1)ns$ is suitable for $k$.

We now have $[W(k,nr+1)]$ $k$-coloured. There exists a monochromatic arithmetic progression of length $nr+1$, say $a,a+d,\dots ,a+dnr$ of colour red. Let us look at $dis$, where $i\in [n]$. Note $dis\le W(k,nr+1)ns$, so “it is in our set of coloured numbers”.

If $dis$ is also red, then $a,a+ird,dis$ is a monochromatic solution.

If no such $dis$ exists, then $\{ds,2ds,\dots ,nds\}$ is $k-1$ coloured. So there exists $i,j,k$ such that $c(ids)=c(jds)=c(kds)$ and $i+\lambda j=k$. Then $dsi+\lambda dsj=dsk$, i.e. $dsi,dsj,dsk$ is a monochromatic solution. □

Proof. We saw in Proposition 2.2 that if it is partition regular then it has the column property.

For the other direction, we know that ${\sum }_{i\in I}{a}_i=0$ and we need to show that given $c:\mathbb{N}\to [k]$ such that there exists monochromatic $(x_1,\dots ,x_n)$ such that $\sum a_i{x}_i=0$.

Fix $i_0\in I$ and we “cook up” the following vector:

Need $x,y,z$ monochromatic such that $({\sum }_{i\notin I}{a}_i)y+x{a}_{i_0}+({\sum }_{i\in I\setminus \{i_0\}}{a}_i)z=0$, which is the same as requiring $x{a}_{i_0}-z{a}_{i_0}+(\sum i\notin I{a}_i)y=0$.

Upon dividing by $a_{i_0}$, we see that this is the same as

which is true by Lemma 2.3. □

Proof. Let $C_1,\dots ,C_n$ be its columns. Fix $p$ prime.

Colour $\mathbb{N}$ as we did before, by $c(x)=e(x)$. By assumption there exists monochromatic $x_1$ such that ${\sum }_i{x}_i{C}_i=0$.

Let us partition $C_1,\dots ,C_n$ as $B_1\bigsqcup B_2\bigsqcup \cdots \bigsqcup B_l$ where $i,j\in B_k$ if and only if $t(x_i)=t(x_j)$, $i\in B_{k_1}$, $j\in B_{k_2}$ for $k_1<k_2$ if and only if $t(x_i)<t(x_j)$.

We do this for infinitely many $p$. Because there exist finitely many partitions, for infinitely many primes $p$ we will have the same blocks.

• For $B_1$: ${\sum }_i{x}_i{C}_i=0$, say all have colour $d$, i.e. $e(x_i)=d\in [1,\dots ,p-1]$. Then $\sum d{C}_i\equiv 0(modp)$ (by collecting the right-most terms in base $p$). Since this holds for infinitely many $p$, we have that ${\sum }_{i\in B_i}{C}_i=0(modp)$ for infinitely many primes (the large primes), and hence we have that ${\sum }_{i\in B_i}{C}_i=0$.

• ${\sum }_{i\in B_{k^{\prime }}}{p}^{t}d{C}_i+{\sum }_{i\in B_1,\dots B_{k^{\prime }-1}}{x}_i{C}_i\equiv 0(mod{p}^{t+1})$.

  Then ${\sum }_{i\in B_k}{p}^t{C}_i+{\sum }_{i\in B_1,\dots ,B_{k^{\prime }-1}}{x}_i{(d)}^{-1}{C}_i\equiv 0(mod{p}^{t+1})$ ($\ast$).

  Claim: ${\sum }_{i\in B_k}{C}_i\in {\mathrm{span}}_{i\in B_1\cup \cdots \cup B_{k-1}}⟨C_i⟩$.

  We will show that given $U$ such that $U\cdot C_i=0$ got sll $i\in B_1,\dots ,B_{k-1}$. Then

  $$u\cdot \left(\sum _{i\in B_k}{C}_i\right)=0$$

  which finishes the proof as this implies ${\sum }_{i\in B_k}{C}_i\in {\mathrm{span}}_{i\in B_1\cup \cdots \cup B_{k-1}}⟨C_i⟩$. Take the inner product of ($\ast$) with $u$. Get

  $$p^t\sum _{i\in B_k}u\cdot C_i\equiv 0(mod{p}^{t+1}),$$

  which is equivalent to ${\sum }_{i\in B_k}u\cdot C_i\equiv 0(modp)$. Since this happens for infinitely many $p$, we get ${\sum }_{i\in B_k}u\cdot C_i=0$. □

Proof. By the above remark, it is enough to find a $(k(m-1)+1,p,c)$-set set such that each row is monochromatic.

Let $n$ be large enough (enough in order to apply everything to follow). Let $A_1=\{c,2c,\dots ,c\lfloor \frac{n}{c}\rfloor \}$. By Van der Waerden, there exists a monochromatic arithmetic progression of length $2n_1+1$, with $n_1$ is large enough.

has colour $k_1$. Let $M=m(k-1)+1$. Now we restrict attention to

Observe that $c{x}_1+{\lambda }_1{b}_1+{\lambda }_2{b}_2+\cdots +{\lambda }_{M-1}{b}_{M-1}$ where $b_i\in B_i$, ${\lambda }_i\in [-p,p]$ is in $R_1$ for any ${\lambda }_i\in [-p,p]$ and any $b_1,\dots ,b_{M-1}$. Thus has colour $k_1$.

Next: look inside $B_1$:

Apply Van der Waerden to find an arithmetic progression of length $2n_2+1$, of colour $k_2$. Let

of colour $k_2$, and let

Note that for any $b_1,\dots ,b_{M-2}$ and ${\lambda }_1,\dots ,{\lambda }_{M-2}\in [-p,p]$. Then

is in $R_2$, thus has colour $k_2$.

Keep on doing this $M$ times. Restrict to $M$ generators (by setting some $\lambda$ to $0$). □

Proof. The previous theorem implies this: any $(m,1,1)$-set contains a set of the above desired form. □

Proof. Let $C_1,\dots ,C_n$ be the columns of $A$. Then there exists $B_1\bigsqcup B_2\bigsqcup \cdots \bigsqcup B_r$ a partition of $[n]$ such that

For all $k$, we have

with $q_{ik}\in \mathbb{Q}$.

For each $k$, let

Rewriting the above we get

for all $k$. We will take $m=r$. Let $x_1,\dots ,x_r$ be some integers. Let $y_i={\sum }_{k=1}^r{d}_{ik}{x}_k$.

Claim ${(y_1,\dots ,y_n)}^{\top }$ is a solution, i.e. ${\sum }_{i=1}^n{y}_i{C}_i=0$. Indeed:

Look at $y_i={\sum }_{k=1}^n{d}_{ik}{x}_k$. Have $d_{ik}\in \mathbb{Q}$. Let $c$ be the common denominator of all the $q_{ik}$s. Then

Also have that $cy$ is a solution. Our $c$ (for the $(r,p,c)$-set) is indeed the common denominator of the $q_{ik}$, and $p=c\cdot \max |\text{numerators}|$. □

Proof of Rado’s Theorem. Want to prove $A$ is partition regular if and only if it has the column property.

If $A$ is partition regular, then by Proposition 2.5, it has the column property.

For the other direction, let $\tilde{c}$ be a finite colouring of $\mathbb{N}$. Also, since $A$ has column property there exists $m,p,c$ such that $Ax=0$ solutions in any $(m,p,c)$-set. By Theorem 2.6 there exists a monochromatic $(m,p,c)$-set with respect to $\tilde{c}$. But this gives a monochromatic solution to $Ax=0$. □

Proof. Trivial check of column property. □

Proof. $\mathbb{N}=C_1\bigsqcup C_2\bigsqcup \cdots \bigsqcup C_k$. Assume for all $C_i$ that there exists $A_i$ that is partition regular, but has no solution in $C_i$. Look at

This is partition regular too, hence it has a monochromatic solution of colour say $C_t$. Then $A_t$ has a solution in $C_t$, contradiction. □

Proof.

• $\Leftarrow$ If I try to extend $U$ by adding in some $A\notin U$, then since $A^c\in U$, we would also have to have $A\cap A^c\in U$, which violated one of the properties of being a filter.
• $\Rightarrow$ Suppose $U$ is an ultrafilter and there exists $A$ such that $A,A^c$ are not in $U$.

  By maximality, if $A$ is not in $U$ then there exists $B\in U$ such that $A\cap B=\varnothing$. Indeed, suppose not. Then

  $$F^{\prime }=\{S:S\supseteq A\cap B\text{ for some }B\in U\}$$

  extends it (the only way this can fail to be a filter is if $\varnothing \in F^{\prime }$, which would require a $B$ such that $A\cap B=\varnothing$).

  Then $B\subseteq A^c$, so $A^c\in U$, contradicting the initial assumption. □

Proof. By Zorn’s lemma, it is enough to show that any chain of filters extending $F$ has an upper bound.

Let ${(F_i)}_{i\in I}$ be a chain of filters containing $F$, i.e. for all $i\ne j$ either $F_i\subseteq F_j$ or $F_j\subseteq F_i$. Let $F={\bigcup }_{i\in I}{F}_i$. Need to show $F$ is a filter:

• (1) $\varnothing \notin F$ since $\varnothing \notin F_i$ for each $i$.
• (2) If $A\in F$ and $A\subseteq B$ then $A\in F_i$ for some $i$, and then we have $B\in F_i$ for this same $i$ (as $F_i$ is a filter), so $B\in F$.
• (3) If $A,B\in F$ then say $A\in F_i$, $B\in F_j$. Since $(F_i)$ is a chain, we can suppose without loss of generality that $F_i\subseteq F_j$. Then $A,B\in F_j$, so $A\cap B\in F_j\subseteq F$, so $A\cap B\in F$.

and also clearly $F$ extends $F$. So $F$ is an upper bound. □

Proof. $\beta \mathbb{N}$ is Hausdorff: Let $U\ne V$ be two ultrafilters. Then there exists $A\in U$ such that $A\notin V$. Then $U\in C_A$ (and $C_A$ is open), and $A^c\in V$, hence $V\in C_{A^c}$ (and $C_{A^c}$ is open). Note $C_A\cap C_{A^c}=\varnothing$. So indeed $\beta \mathbb{N}$ is Hausdorff.

$\beta \mathbb{N}$ is compact: want to show that every open cover has a finite subcover. This is equivalent to showing that if a collection of closed sets has the property that no finite subset covers $\beta \mathbb{N}$, then the whole collection doesn’t cover $\beta \mathbb{N}$. This is equivalent to showing that if you have a collection of closed sets such that they have the finite intersection property (for any $J\subset I$ finite, ${\bigcap }_{i\in J}{F}_i\ne \varnothing$), then their intersection is non-empty.

Further, in the first sentence we can without loss of generality that the open sets are basis sets (i.e. of the form $C_A$), and carrying this forward tells us that we may assume that the closed sets in the last sentence are of the form $C_A^c$, or equivalently, of the form $C_A$.