## Properties of ultrafilters and a Theorem on arithmetic combinatorics

A Theorem of Schur (one of the earliest results in Ramsey Theory) asserts that given any finite coloring of the set of natural numbers ${{\mathbb N}}$, there exist ${x,y\in{\mathbb N}}$ of the same color such that ${x+y}$ also has the same color. As a Corollary (using any injective homomorphism between the semigroups ${({\mathbb N},+)}$ and ${({\mathbb N},\times)}$, for instance ${n\mapsto2^n}$) one gets that in any finite coloring of ${{\mathbb N}}$ there are ${x}$ and ${y}$ of the same color such that ${xy}$ is also of that color.

The next question is whether one can find ${x,y}$ of the same color such that both ${x+y}$ and ${xy}$ are also of the same color. This question is still open, and even the easier looking question of whether we can find ${x}$ and ${y}$ such that ${x+y}$ and ${xy}$ have the same color (but we don’t care about the colors of ${x}$ and ${y}$) is unanswered.

I was surprised to learn recently that the following related result has been proved (and has a nice proof):

Theorem 1 Let ${{\mathbb N}=\biguplus C_i}$ be a partition of the set of all natural numbers ${{\mathbb N}}$ into finitely many colors. Then there exist some ${x,y,a,b}$ all in the same color and such that ${xy=a+b}$.

In this post I will present a proof of this theorem, following the proof on this survey by Bergelson (it’s the Theorem 6.1 there). An independent proof of a more general case was found by Hindman.

The proof we will present uses the theory of idempotent ultrafilters on ${{\mathbb N}}$, one of my purposes here is to make a point for the usefulness of ultrafilters when dealing with problems from arithmetic combinatorics. I am also quite interested on this because it seems that ultrafilters are the only tool available so far to deal with combinatorics on ${{\mathbb N}}$ dealing with both addition and multiplication (one can argue that polynomials involve multiplication, but quadratic polynomials are just sums of linear polynomials and so on, and the theorems involving polynomials are proved using that way of thinking about polynomials. Another theorem that seems to have some of the multiplications structure is the Green-Tao Theorem, but really the only thing about primes that is used in the proof are some statistics on their distribution. Finally in this parenthesis I should say that there are results dealing with both addition and multiplication on finite fields, proved using Fourier analysis, but unlike results dealing with only addition, it seems harder (if not completely impossible) to use those results to establish analogues on the infinite set ${{\mathbb N}}$).

This post turned out to be a little longer than I initially expected, but that is mostly because I decided to make it completely self contained (apart from some standard results from point set topology).

— 1. Ultrafilters on countable sets —

I decided to work on a general countable (infinite) commutative ring, so in this post ${R}$ will always denote such a ring, so I actually present a proof of the Theorem 1 with ${{\mathbb N}}$ replaced by ${R}$. In this section though, I will only use the fact that ${R}$ is a countable set.

An ultrafilter on ${R}$ is a collection of subsets of ${R}$ respecting some properties. It is (equivalently) a point in the Stone-Čech compactification ${\beta R}$ of ${R}$, if we give ${R}$ the discrete topology.

Definition 2 (Ultrafilter) An ultrafilter ${p}$ is a non-empty collection of subsets of ${R}$ satisfying:

• ${\emptyset\notin p}$
• If ${A\subset B}$ and ${A\in p}$ then ${B\in p}$
• If ${A\in p}$ and ${B\in p}$ then also ${A\cap B\in p}$
• If ${A\cup B\in p}$ then either ${A\in p}$ or ${B\in p}$

In particular ${R\in p}$ by the second condition (and because ${p}$ is non-empty), so for each ${A\subset R}$, either ${A\in p}$ or ${R\setminus A\in p}$ (by the last property). Also, iterating the last property, we get that for any finite partition of ${R}$, one of the cells belongs to ${p}$ (and exactly one).

A trivial example of an ultrafilter can be given by the following: pick ${a\in R}$ and consider the family ${p_a:=\{A\subset R:a\in A\}}$. One can promptly check the conditions that define ultrafilters. However, in order to obtain any example of a non-principal ultrafilter, one requires (at least some weaker form of) the axiom of choice. This means that an explicit construction of an non-principal ultrafilter is hopeless. What we can (and will) do is prove existence of ultrafilters with some nice additional properties.

Proposition 3 There exist non-principal ultrafilters.

Proof: A family of subsets of ${R}$ satisfying the first three properties of the Definition 2 is called a filter. We first show that any maximal filter (for the partial order of inclusion) is an ultrafilter. Let ${p}$ be a maximal filter, let ${A,B\subset R}$ be non-empty sets such that ${A\cup B\in p}$. Assume ${B\notin p}$, consider ${p':=p\cup\{C\subset R: A\subset C\}\cup \{A\cap C:C\in p\}}$. I claim that ${p'}$ is also a filter, by maximality this will imply that ${p'=p}$ and so ${A\in p}$ as desired.

To prove that ${\emptyset\notin p'}$, assume it is. Since ${p}$ is a filter and ${A}$ is non-empty we have that ${A\cap C=\emptyset}$ for some ${C\in p}$. But since ${A\cup B\in p}$, we have ${(A\cup B)\cap C}$ is in ${p}$ and also a subset of ${B}$, contradicting the assumption that ${B\notin p}$. The second and third conditions for a filter trivially hold for ${p'}$ and this proves the claim.

Now it is also easy to check that the union of any totally ordered subset of filters is again a filter, so we can apply the Zorn’s lemma to conclude that any filter is contained in some ultrafilter. Since the filter of co-finite sets is not contained in any principal ultrafilter we get existence of a non-principal ultrafilter. $\Box$

As I mentioned earlier in this post, the set of all ultrafilters can be identified with the Stone-Čech compactification ${\beta R}$ of ${R}$. Let ${\Omega:=\{0,1\}^R}$ be the set of all functions ${f:R\rightarrow\{0,1\}}$. By identifying a subset ${A\subset R}$ with its indicator functions, we can also think of ${\Omega}$ as all subsets of ${R}$. We endow ${\{0,1\}}$ with the discrete topology and give ${\Omega}$ the product topology, making it into a compact space by the Tychonoff’s theorem. Now we consider the space ${X=\{0,1\}^\Omega}$ of all functions from ${\Omega}$ in ${\{0,1\}}$, it is also compact, again by the Tychonoff’s theorem. We can also think of a point in ${X}$ as a subset of ${\Omega}$ or, equivalently as a collection of subsets of ${R}$.

Now, for each ${n\in R}$, let ${\tilde{n}\in X}$ be the function ${\tilde n:\Omega\rightarrow\{0,1\}}$ given by ${\tilde n(f)=f(n)}$ for each ${f:R\rightarrow\{0,1\}}$. This gives an embedding of ${R}$ into ${X}$, that by an abuse of language we will also denote by ${R}$. The Stone-\v Cech compactification of ${R}$ is the closure ${\beta R}$ of ${R}$ in ${X}$ (it is compact because it is a closed subset of the compact Hausdorff space ${X}$).

A point ${p\in\beta R\subset X}$ is a map from ${\Omega}$ to ${\{0,1\}}$. By identifying points in ${\Omega}$ with subsets of ${R}$, we can associate ${p}$ with the family of subsets ${A\subset R}$ for which ${p(A)=1}$. By an abuse of language we will denote this collection of subsets of ${R}$ also by ${p}$ and we will use interchangeably the notations ${A\in p}$ and ${p(A)=1}$ with the same meaning. Note that the element ${\tilde n\in X}$ is the principal ultrafilters at ${n}$.

Proposition 4 Let ${p\in X}$ be a collection of subsets of ${R}$. Then ${p\in\beta R}$ if and only if ${p}$ is an ultrafilter on ${R}$.

Proof: Unraveling the meaning of product topology we see that ${p\in\beta R}$ if and only if for any finite collection ${A_1,...,A_k}$ of subsets of ${R}$ there exists some ${n\in R}$ such that ${\tilde n(A_i)=p(A_i)}$ for each ${i=1,...,k}$.

First assume that ${p\in\beta R}$. Since ${\tilde n(\emptyset)=0}$ for all ${n\in R}$, also ${p(\emptyset)=0}$ and hence ${\emptyset\notin p}$, proving the first property of the Definition 2. Now let ${A\in p}$ and suppose ${B\supset A}$. Let ${n\in R}$ be such that ${\tilde n(A)=p(A)}$ and ${\tilde n(B)=p(B)}$. Then ${n\in A}$ so ${n\in B}$ and thus ${p(B)=1}$, proving the second property. If both ${A}$ and ${B}$ are in ${p}$, let ${n\in R}$ be such that ${\tilde n}$ and ${p}$ agree at ${A,B}$ and ${A\cap B}$. Then we conclude that ${A\cap B\in p}$ proving the third property. Finally suppose that ${A\cup B\in p}$ and let ${n\in R}$ be such that ${\tilde n}$ agree with ${p}$ at ${A}$, ${B}$ and ${A\cup B}$. Thus either ${A}$ or ${B}$ will be in ${p}$ proving the fourth property. This implies that ${p}$ is indeed an ultrafilter.

Now suppose that ${p}$ is an ultrafilter. Given any subsets ${A_1,...,A_k}$ of ${R}$, assume that ${A_1,...,A_r}$ are in ${p}$ and ${A_{r+1},...,A_k}$ are not in ${p}$. Then the intersection

$\displaystyle \left(\bigcap_{i=1}^r A_i\right)\cap\left[\bigcap_{i=r+1}^k(R\setminus A_i)\right]$

is in ${p}$ and in particular it is non-empty. Let ${n}$ be in that intersection. Then ${\tilde n}$ agrees with ${p}$ at the sets ${A_1,...,A_k}$. Since the sets ${A_1,...,A_k}$ were arbitrary, we conclude that there exists some ${\tilde n}$ at each neighborhood of ${p}$, and hence ${p\in\beta R}$. $\Box$

This proves suggests the following observation about the topology of ${\beta R}$ that will be useful for us later. For a set ${A\subset R}$ we define its closure ${\bar A\subset \beta R}$ by ${p\in\bar A\iff A\in p}$. Note that ${\bar A}$ just defined is the closure on ${\beta R}$ of the set ${\{\tilde n:n\in A\}}$, but we will not need this fact.

Lemma 5 The sets ${\bar A}$ are clopen and form a basis for the topology on ${\beta R}$.

Proof: Let ${p\in X}$. By definition ${p\in\bar A\iff p(A)=1}$. Since ${1}$ is a clopen subset of ${\{0,1\}}$ and by the definition of product topology on ${X}$ we conclude that ${\bar A}$ is a clopen set of ${X}$, hence intersecting with ${\beta R}$ we get a clopen subset of ${\beta R}$.

To prove that they form a basis for the topology on ${\beta R}$, let ${k\in{\mathbb N}}$, let ${1\leq r\leq k}$, let ${A_1,...,A_k}$ be subsets of ${R}$ and let ${C:=\{p\in\beta R:A_1,...,A_r\in p, A_{r+1},...,A_k\notin p\}}$. Consider the intersection

$\displaystyle B=\left(\bigcap_{i=1}^r A_i\right)\cap\left[\bigcap_{i=r+1}^k(R\setminus A_i)\right]$

Then, by the ultrafilter property, ${p\in C\iff B\in p}$. Thus ${C=\bar B}$. $\Box$

— 2. Ultrafilters on semigroups —

So far we didn’t use any property of the set ${R}$ (except that it is infinite). Now we will see that a binary operation on ${R}$ induces a binary operation in ${\beta R}$. To motivate the definition it helps to think of ultrafilters in yet a third way, namely as finitely additive ${\{0,1\}}$-valued measures on ${R}$. In that way, the operation on ${\beta R}$ is just the usual convolution of measures.

Let ${\circ}$ be an associative binary operation on ${R}$ (we will only use ${\circ=+}$ and ${\circ=\times}$), let ${A\subset R}$ and ${n\in R}$. I use the notation ${A\circ n^{-1}}$ to denote the set ${\{x\in T:x\circ n\in A\}}$. In the case of additive notation we will use ${A-n}$ instead of ${A+n^{-1}}$.

Definition 6 Let ${p}$ and ${q}$ be ultrafilters on a semigroup ${(R,\circ)}$. We define the operation

$\displaystyle p\circ q:=\{A\subset R:\{n\in R:A\circ n^{-1}\in p\}\in q\}$

We first need to check that ${p\circ q}$ is indeed an ultrafilter on ${R}$:

Proposition 7 If ${p,q\in\beta R}$ then also ${p\circ q\in \beta R}$.

Proof: It is clear that ${\emptyset\notin p\circ q}$. Also, if ${A\subset B}$, then for each ${n}$ we have ${(A\circ n^{-1})\subset (B\circ n^{-1})}$. It is now easy to check that if ${A\in p\circ q}$ then also ${B\in p\circ q}$. Now assume that both ${A,B\in p\circ q}$. Since ${(A\circ n^{-1})\cap(B\circ n^{-1})=(A\cap B)\circ n^{-1}}$ for each ${n\in R}$, we have that ${\{n:(A\cap B)\circ n^{-1}\in p\}=\{n:A\circ n^{-1}\in p\}\cap\{n:B\circ n^{-1}\in p\}\in q}$ and hence ${A\cap B\in p\circ q}$.

Finally, if ${A\cup B\in p\circ q}$ then using the fact that ${p}$ is an ultrafilter (and the fact that ${(A\cup B)\circ n^{-1}=A\circ n^{-1}\cup B\circ n^{-1}}$) we have that for each ${n}$ in the set ${C:=\{n:(A\cup B)\circ n^{-1}\in p\}}$ either ${A\circ n^{-1}\in p}$ or ${B\circ n^{-1}\in p}$. Since ${q}$ is also an ultrafilter and ${C\in q}$, either ${\{n:A\circ n^{-1}\in p\}\in q}$ or ${\{n:B\circ n^{-1}\in p\}\in q}$ which is equivalent, respectively to ${A\in p\circ q}$ or ${B\in p\circ q}$. $\Box$

Moreover, this binary operation turns out to be associative:

Proposition 8 The binary operation on ${\beta R}$ just defined is associative.

Proof: We first note that for ${A\subset R}$ and ${n,m\in R}$ we have

$\displaystyle x\in(A\circ n^{-1})\circ m^{-1}\iff x\circ m\circ n\in A$

and so ${(A\circ n^{-1})\circ m^{-1}=A\circ(m\circ n)^{-1}}$.

Let ${p,q,r\in\beta R}$. Then ${A\in (p\circ q)\circ r}$ if and only if

$\displaystyle \begin{array}{rcl} \displaystyle\{n:A\circ n^{-1}\in p\circ q\}\in r&\iff&\displaystyle\{n:\{m:(A\circ n^{-1})\circ m^{-1}\in p\}\in q\}\in r\\&\iff&\displaystyle\{n:\{m:A\circ(m\circ n)^{-1}\in p\}\in q\}\in r\\&\iff&\displaystyle\{n:\{m:m\circ n\in\{x:A\circ x^{-1}\in p\}\}\in q\}\in r\\&\iff&\displaystyle\{n:\{x:A\circ x^{-1}\in p\}\circ n^{-1}\in q\}\in r\\&\iff&\displaystyle\{x:A\circ x^{-1}\in p\}\in q\circ r\\&\iff&\displaystyle A\in p\circ(q\circ r) \end{array}$

$\Box$

Thus ${(\beta R,\circ)}$ is a semigroup. It should be remarked that this operation extends the operation on ${R}$. More precisely, if ${n,m\in R}$ then ${\tilde n\circ\tilde m:=\widetilde{n\circ m}}$. However, the operation in ${\beta R}$ needs not be commutative even if ${\circ}$ is.

Another good property of the operation in ${\beta R}$ is that it is left continuous:

Proposition 9 For each ${p\in\beta R}$, the map ${\lambda_p:\beta R\rightarrow\beta R}$ defined by ${\lambda_p:q\mapsto p\circ q}$ is continuous.

Proof: We will use the Lemma 5. Fix ${p,q\in\beta R}$ and let ${\bar A}$ be an clopen neighborhood of ${\lambda_p(q)}$. I need to show that ${\{r:\lambda_p(r)\in\bar A\}}$ contains ${\bar B}$ for some ${B}$. We observe that ${\lambda_p(r)\in\bar A\iff A\in p\circ r\iff \{n:A\circ n^{-1}\in p\}\in r}$. Thus making ${B=\{n:A\circ n^{-1}\in p\}}$ we get that indeed ${\{r:\lambda_p(r)\in\bar A\}}$ contains ${\bar B}$. $\Box$

Quite special elements of the semigroup ${(\beta R,\circ)}$ are idempotent elements, i.e, ultrafilters ${p}$ such that ${p\circ p=p}$. However, the existence of such ultrafilters not obvious. Their existence can be assured using a Theorem by Ellis:

Theorem 10 (Ellis Theorem) If ${(S,\circ)}$ is a compact Hausdorff left topological semigroup, then ${S}$ contains an idempotent.

Proof: Consider the family

$\displaystyle V:=\{\emptyset\neq W\subset S: W\text{ is compact },W\circ W:\{w_1\circ w_2:w_1,w_2\in W\}=W\}$

${V}$ is non-empty because ${S\in V}$. Also the intersection of any nested subfamily of ${V}$ is still in ${V}$ (because a nested intersection of compacts in a Hausdorff space is non-empty). Applying Zorn’s lemma we find a minimal (for the partial order of inclusion) element ${W\in V}$.

For each ${x\in W}$ we have ${(x\circ W)\circ(x\circ W)\subset x\circ W\circ W\circ W\subset x\circ W}$, and by left continuity ${x\circ W}$ is compact, hence ${x\circ W\in V}$. Also ${x\circ W\subset W\circ W\subset W}$, so by minimality ${x\circ W=W}$.

In particular ${x=x\circ y}$ for some ${y\in W}$. Thus the set ${Z:=\{z\in W:x\circ z=x\}}$ is non-empty. By continuity we have that ${Z}$ is closed (hence compact) and if ${y,z\in Z}$ then ${x\circ(y\circ z)=x\circ z=x}$, hence ${Z\circ Z\subset Z}$. This implies that ${Z\in V}$, again by minimality we have that ${Z=W}$ and in particular ${x\in Z}$. We conclude that ${x\circ x=x}$, and this is our idempotent. $\Box$

This implies that there are idempotent ultrafilters on ${\beta R}$.

— 3. Idempotent ultrafilters and Hindman’s Theorem —

We are now concerned with a countable set ${R}$ with a commutative associative binary operation ${\circ}$. Given an infinite set ${I\subset R}$ we for the set of finite products of ${I}$:

$\displaystyle FP(I):=\{i_1\circ i_2\circ...\circ i_k:k\in{\mathbb N}, i_1,...,i_k\in I\text{ are all distinct}\}$

Hindman’s theorem asserts that, given any finite partition of ${R}$, one of the cells of the partition contains a set of the form ${FP(I)}$ for some infinite set ${I\subset R}$. Sets that contain ${FP(I)}$ for some infinite set ${I\subset R}$ are called IP sets.

In order to prove Hindman’s Theorem, it will suffice to prove the following:

Proposition 11 Let ${p\in\beta R}$ be an idempotent ultrafilter on ${R}$ and let ${A\in p}$. Then ${FP(I)\subset A}$ for some infinite set ${I\subset R}$.

The reason why this implies Hindman’s Theorem is that for any finite partition, one of the cells belong to ${p}$.

Proof: Since ${A\in p}$ and ${p\circ p=p}$, we have that ${\{n:A\circ n^{-1}\in p\}\in p}$. Thus also ${A\cap\{n:A\circ n^{-1}\in p\}\in p}$ and, in particular, this set is non-empty. Choose some ${n_1}$ in that set, note that ${n_1\in A}$ and ${A_1:=A\cap(A\circ n_1^{-1})\in p}$.

Now, by the same reasoning, also ${A_1\cap\{n:A_1\circ n^{-1}\in p\}\in p}$, choose some ${n_2}$ in that set and note that ${n_2\in A}$ and ${A_2:=A_1\cap(A_1\circ n_2^{-1})\in p}$. Moreover ${n_2\in A\circ n_1^{-1}}$, hence ${n_2\circ n_1\in A}$, in other words ${FP(\{n_1,n_2\})\subset A}$. Now inductively we prove that for each ${k>2}$ there is a set ${A_k\in p}$ such that ${A_k\subset A}$, and a sequence ${n_1,...,n_k}$ such that ${FP(\{n_1,...,n_k\})\subset A}$.

Now assume we have this for ${k-1}$, note that the set ${A_{k-1}\cap\{n:A_{k-1}\circ n^{-1}\in p\}\in p}$ and in particular is non-empty. Choose some ${n_k}$ on that set, note that ${n_k\in A}$ and that the set ${A_k:=A_{k-1}\cap(A_{k-1}\circ n_k^{-1})\in p}$. Moreover, for any ${x\in A}$ we have ${n_k\circ x\in A}$, since by induction ${FP(\{n_1,...,n_{k-1}\})\subset A}$ we get that ${FP(\{n_1,...,n_k\})\subset A}$ and this completes the induction.

Thus ${FP(\{n_1,n_2,...\})\subset A}$ as desired. $\Box$

We just proved that each set belonging to an idempotent ultrafilter is an IP set. We now prove a partial converse, and first we need a lemma:

Lemma 12 Let ${A\subset R}$ be an IP set. Then there exists some idempotent ${p\in\beta R}$ such that ${A\in p}$.

Proof: Let ${I\subset R}$ be an infinite set such that ${FP(I)\subset A}$ and let ${\mathcal I}$ denote the family of all co-finite subsets of ${I}$. Let

$\displaystyle S:=\bigcap_{J\in\mathcal I}\overline{FP(J)}\subset\beta R$

Since ${S}$ is the intersection of a nested sequence of compact sets is compact and non-empty. I claim that ${S}$ is a semigroup. Let ${p,q\in S}$, we need to show that for each ${J\in\mathcal I}$ we have ${FP(J)\subset p\circ q}$.

For each ${a\in FP(J)}$, we can write ${a=i_1\circ...\circ i_k}$ for some ${i_1,...,i_k\in I}$. Let ${J'=J\setminus\{i_1,...,i_k\}\in\mathcal I}$. Then ${FP(J')\circ a\subset FP(J)}$, in other words ${FP(J')\subset FP(J)\circ a^{-1}}$ and since ${FP(J')\in p}$ we have that ${\{a\in R:FP(J)\circ a^{-1}\in p\}\supset FP(J)}$ and hence is in ${q}$. This proves that ${FP(J)\in p\circ q}$ and hence ${S}$ is a semigroup.

Finally, we apply Ellis theorem to ${S}$ to find an idempotent there. $\Box$

Proposition 13 Let ${p\in\beta R}$ be an ultrafilter. Then that each ${A\in p}$ is an IP set if and only if ${p}$ is in ${\Gamma:=\overline{\{q\in\beta R:q+q=q\}}}$, the closure in ${\beta R}$ of the set of idempotent ultrafilters.

Proof: Assume first that every ${A\in p}$ is an IP set. Let ${U}$ be a neighborhood (in ${\beta R}$) of ${p}$. Then ${p\in\bar A\subset U}$ for some set ${A\subset R}$. This implies that ${A\in p}$ and hence ${A}$ is an IP set. By the previous Lemma ${A}$ is also contained in some idempotent ultrafilter ${q}$, so ${q\in\bar A}$ and thus ${p\in\Gamma}$.

Now suppose that ${p\in\Gamma}$ and let ${A\in p}$. Thus ${p\in \bar A}$ and hence there exists some idempotent ${q}$ such that also ${q\in\bar A}$. But this implies that ${A\in q}$ and hence ${A}$ is an IP set. $\Box$

— 4. Mixing addition and multiplication —

On this section we will (finally) use the fact that ${R}$ is a ring with two operations. This gives two notions of idempotents in ${\beta R}$. A natural question is whether there exist any ${p\in\beta R}$ which is idempotent with respect to both the additive and the multiplicative structure. Unfortunately the answer turns out to be negative in general (at least it is negative when ${R={\mathbb N}}$, I couldn’t find a proof for any other ring).
More precisely, there is no ultrafilter $p\in\beta\mathbb{N}$ such that $p+p=p.p$, this appears as Corollary 17.17 in this book of Hindman and Strauss.

However we can construct an ultrafilter almost as good:

Theorem 14 There exists an ultrafilter ${p\in\beta R}$ such that ${p}$ is multiplicative idempotent and every ${A\in p}$ is an additive IP set.

Proof: Let ${\Gamma=\overline{\{p\in\beta R:p+p=p\}}}$. In view of Ellis Theorem and the Proposition 13, it suffices to prove that ${\Gamma}$ is a multiplicative semigroup. It turns out that it is actually a left ideal (i.e. ${\Gamma.\beta R\subset\Gamma}$).

Let ${p\in\Gamma}$ and ${q\in\beta R}$. Let ${A\in p.q}$. Then ${\{n\in R: A.n^{-1}\in p\}\in q}$, and in particular that set is non-empty. Choose some ${n\in R}$ such that ${A.n^{-1}\in p}$. Then ${A.n^{-1}}$ is an additive IP set. Let ${I\subset R}$ be an infinite set such that the additive IP set ${FP(I)\subset A.n^{-1}}$. But then ${FP(nI)\subset A}$ and hence ${A}$ is an (additive) IP set as desired. Since ${A\in p.q}$ was chosen arbitrarily we get that ${p.q\in\Gamma}$ and we are done. $\Box$

— 5. Proof of the Theorem 1

We now present the proof of the Theorem 1, with ${{\mathbb N}}$ replaced by any countable abelian ring ${R}$.

For any ultrafilter ${p\in\beta R}$ we know that one cell of a finite partition must belong to ${p}$. Thus the Theorem reduces to the following:

Theorem 15 Let ${p\in\beta R}$ be a multiplicative idempotent such that each ${A\in p}$ is an additive IP set. Then for each ${A\in p}$ there are ${x,y,a,b\in A}$ such that ${xy=a+b}$.

Proof: Since ${p.p=p}$ we have that ${\{n:A.n^{-1}\in p\}\in p}$. Choose ${x}$ such that ${A_1:=A\cap A.x^{-1}\in p}$. Then ${A_1}$ is an additive IP set, by the Lemma 12 there exists some additive idempotent ${q\in\beta R}$ such that ${A_1\in q}$. Then ${\{n:A_1-n\in q\}\in q}$ and so also ${A_1\{n:A_1-n\in q\}\in q}$. Choose some ${z}$ in that intersection. Then ${z\in A_1}$ and ${A_1-z\in q}$. Then also ${A_2:=A_1\cap(A_1-z)\in q}$ and so that set is non-empty.

Since ${A.x^{-1}\subset A_1}$ we get that ${b:=zx\in A}$. Also we now have that ${A_3:=xA_2}$ is non-empty, and we can rewrite

$\displaystyle A_3=xA_2=xA_1\cap(xA_1-b)=xA\cap A\cap [(xA\cap A)-b]$

Let ${a\in A_3}$. Then ${a,b,x\in A}$ and ${a+b\in xA}$, so there exists some ${y\in A}$ such that ${a+b=xy}$ as desired.$\Box$

This entry was posted in Combinatorics, Ramsey Theory and tagged , , , , . Bookmark the permalink.

### 13 Responses to Properties of ultrafilters and a Theorem on arithmetic combinatorics

1. Pingback: Weak Mixing | YAMB

2. Pingback: Jin’s Theorem | YAMB

3. Eugene says:

Good morning! You said for $\mathbb N$ there is no idempotent with respect to both the additive and the multiplicative structure. Where could i find the proof of it?

• Joel Moreira says:

Hi, Eugene,

I added the reference to the text. In case you don’t have access to that book, the original proof that $p+p\neq p.p$ was found by Hindman in this paper: http://www.ams.org/mathscinet-getitem?mr=749511.
I would like to know if this result is still true in more general rings (for instance in $\mathbb{Q}$) but I was not able to extend the proof.

4. Eugene says:

Thanx!

5. Pingback: I Can't Believe It's Not Random!