A new ultrafilter proof of Van der Waerden's theorem

This paper presents a concise new proof of Van der Waerden's Theorem using algebra in the compact space of ultrafilters $\beta\mathbb{N}$, distinguishing itself from existing proofs by avoiding the use of minimal or idempotent ultrafilters.

The Gist

Here is an explanation of Mauro Di Nasso's paper, translated from the dense language of advanced mathematics into a story about organizing a chaotic party.

The Big Idea: Finding Order in Chaos

Imagine you have an infinite line of people, and you decide to paint each person either Red or Blue (or maybe Red, Blue, and Green). You do this randomly, with no pattern at all.

Van der Waerden's Theorem is a famous mathematical guarantee that says: No matter how chaotic your coloring is, if you look far enough down the line, you will eventually find a group of people standing in a perfect, evenly spaced line who are all the same color.

For example, you might find three people: Person #10 (Red), Person #20 (Red), and Person #30 (Red). They are all Red, and they are spaced exactly 10 steps apart. This is called a "monochromatic arithmetic progression."

The paper you shared presents a new, shorter way to prove that this pattern must exist.

The Old Way vs. The New Way

For decades, mathematicians proved this using very heavy machinery. They used tools called "minimal idempotent ultrafilters."

• The Analogy: Think of these old tools as a massive, complex Swiss Army knife with a thousand gadgets. It works, but it's heavy, complicated, and requires a PhD to figure out which button to press.

Di Nasso's new proof throws away the Swiss Army knife. He uses a much simpler, lighter tool: just a standard "ultrafilter" and a little bit of algebra.

• The Analogy: Instead of the Swiss Army knife, he uses a simple, sharp pocket knife. It does the job with fewer moving parts and no need for the "special" gadgets (minimal or idempotent filters) that previous proofs required.

How the Proof Works: The "Super-Observer"

To understand the proof, we need to understand what an Ultrafilter is.

1. The Ultrafilter as a "Super-Observer"
Imagine you are looking at the infinite line of colored people. A normal person can only see one specific spot. An Ultrafilter is like a magical, all-knowing observer that looks at the entire line at once and makes a single, decisive judgment: "The 'Red' group is the important one."

In math terms, the Ultrafilter picks out a specific "club" of numbers. If a set of numbers belongs to this club, the Ultrafilter says, "Yes, this matters." If not, it says, "No."

2. The "Witness" (The Inductive Step)
The proof works by building up the pattern step-by-step, like stacking blocks.

• Step 1: We assume we can find a pattern of length $\ell$ (say, 3 people). The proof says, "Okay, there is a Super-Observer (an Ultrafilter) that guarantees we can find these 3 people."
• Step 2: Now, we want to prove we can find 4 people.

3. The Magic Trick: The Cartesian Square ($N \times N$)
This is the clever part. Instead of just looking at the line of people, the author asks the Super-Observer to look at a grid (a square of people).

• Imagine a grid where the horizontal axis is the Starting Point ($a$) and the vertical axis is the Step Size ($d$).
• Every point on this grid represents a potential arithmetic progression. For example, the point $(10, 5)$ means "Start at 10, step by 5."

The author constructs a special Ultrafilter on this grid. This filter is designed so that it "witnesses" the existence of the pattern. It essentially says: "I know a specific Starting Point and a specific Step Size that will work."

4. The "Pigeonhole" Move
The proof then uses a simple logic trick called the Pigeonhole Principle.

• Imagine you have a bunch of different "clubs" (Ultrafilters) trying to claim the same color.
• The author creates a specific combination of these clubs.
• Because there are more clubs than colors, two of these clubs must agree on the same color.
• When they agree, it forces a mathematical collision that reveals the existence of the longer pattern (length $\ell + 1$).

The "Recipe" for the New Proof

Here is the simplified flow of the author's argument:

1. Assume the pattern exists for length $\ell$. (We have a magical filter that finds it).
2. Create a new, bigger filter on a grid of numbers. This filter combines the old pattern with the new colors.
3. Use Algebra: The author mixes these filters together (like mixing ingredients in a bowl) using a process called "pseudo-sum."
4. Find the Overlap: By mixing them, the math forces a situation where two different "views" of the grid must agree on a specific color.
5. The Result: This agreement proves that a pattern of length $\ell + 1$ must exist.
6. Repeat: Since we can go from 1 to 2, 2 to 3, and so on, we can prove it for any length.

Why This Matters

The beauty of this paper isn't just that it proves something we already knew. It's about elegance.

• Old Proof: "To find the pattern, we need to build a giant, complex machine with special parts that only exist in a very specific, rare state."
• New Proof: "Actually, we don't need the special parts. If we just look at the grid of possibilities and mix our filters correctly, the pattern reveals itself naturally."

It's like realizing you don't need a rocket ship to get to the moon; you just need a really good, simple catapult. The author has stripped away the unnecessary complexity to show the core logic of the theorem in a way that is shorter, cleaner, and surprisingly accessible to those who know the basics of the math.

Technical Summary

Here is a detailed technical summary of the paper "A New Ultrafilter Proof of Van der Waerden's Theorem" by Mauro Di Nasso.

1. Problem Statement

The paper addresses Van der Waerden's Theorem, a foundational result in combinatorics and Ramsey theory. The theorem states that for any finite partition (coloring) of the natural numbers $\mathbb{N} = C_1 \cup \dots \cup C_r$, and for any length $\ell \in \mathbb{N}$, there exists a monochromatic arithmetic progression of length $\ell$. That is, there exist integers $a$ (start) and $d$ (difference) such that the set $\{a, a+d, \dots, a+(\ell-1)d\}$ is entirely contained within one color class $C_i$.

While the theorem has been proven via:

• Complex combinatorial induction (original proof).
• Shelah's combinatorial proof.
• Algebraic methods using minimal idempotent ultrafilters in the Stone-Čech compactification $(\beta\mathbb{N}, \oplus)$ (Bergelson, Hindman, etc.).
• Proofs using "retractions" or "translation invariant" filters.

Di Nasso identifies a gap: existing ultrafilter proofs rely heavily on the existence and properties of minimal or idempotent ultrafilters, which are complex objects requiring deep topological dynamics. The paper aims to provide a proof that avoids these specific structures.

2. Methodology

The author employs algebra in the space of ultrafilters but utilizes a distinct construction strategy compared to previous works.

Core Tools

• Ultrafilters on $\mathbb{N} \times \mathbb{N}$: Instead of working solely on $\beta\mathbb{N}$, the proof constructs ultrafilters on the Cartesian square $\mathbb{N} \times \mathbb{N}$.
• Tensor Products ($\otimes$) and Pseudo-sums ($\oplus$): The proof relies on the algebraic operations of ultrafilters:
  • Tensor Product ($U \otimes V$): Defined on $I \times J$.
  • Pseudo-sum ($U \oplus V$): Defined on $\mathbb{N}$ via $A \in U \oplus V \iff \{n \mid A-n \in V\} \in U$.
• Transformation Maps ($T_j$): The proof utilizes maps $T_j: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ defined by $T_j(n, m) = n + jm$. These maps extract arithmetic progressions from pairs $(n, m)$.

The Inductive Strategy

The proof proceeds by induction on the length $\ell$ of the arithmetic progression:

1. Base Case: Trivial for $\ell=1, 2$.
2. Inductive Step: Assume the theorem holds for length $\ell$.
   • By Lemma 1.3, the inductive hypothesis implies the existence of an ultrafilter $W$ on $\mathbb{N} \times \mathbb{N}$ such that the images of $W$ under maps $T_0, T_1, \dots, T_{\ell-1}$ are identical (i.e., $T_0(W) = T_1(W) = \dots = T_{\ell-1}(W)$).
   • The author constructs a sequence of ultrafilters $Z_s$ on $\mathbb{N}$ using iterated pseudo-sums of $W$ and a specific ultrafilter $U$ derived from $W$.
   • Pigeonhole Principle: Given $r$ colors, the author considers $r+1$ specific ultrafilters $Z_1, \dots, Z_{r+1}$. By the pigeonhole principle, at least two of these ultrafilters ($Z_p$ and $Z_q$ with $p < q$) must contain the same color set $C$.
   • Algebraic Manipulation: The intersection of these conditions allows the extraction of a set $\Gamma$ that belongs to both $U_p \oplus V^{(q-p)}$ and $U_p \oplus U^{(q-p)}$.
   • Construction of the $(\ell+1)$-term Progression: By selecting specific elements from the intersection of pre-images under the maps $\psi_j$ (which are sums of the $T_j$ maps), the author constructs a new start point $a$ and difference $d$ such that the progression of length $\ell+1$ is monochromatic.

3. Key Contributions

• Elimination of Minimal/Idempotent Ultrafilters: This is the most significant contribution. Unlike the proofs by Bergelson, Hindman, and Koppelberg, this proof does not require the ultrafilters to be minimal or idempotent. It relies only on the existence of ultrafilters satisfying specific algebraic relations derived from the inductive hypothesis.
• Simplicity and Brevity: The proof is described as "short" and relies on a "simple induction." It avoids the heavy machinery of topological dynamics (e.g., Ellis semigroups) usually associated with ultrafilter proofs of Ramsey-type theorems.
• Use of $\mathbb{N} \times \mathbb{N}$: The shift to ultrafilters on the Cartesian square to "witness" the inductive step provides a fresh perspective on how to encode arithmetic progressions algebraically.
• Translation from Nonstandard Analysis: The author notes that the proof was originally derived using iterated nonstandard extensions (hyperintegers) and reformulated here into the language of ultrafilters, demonstrating the equivalence and utility of the ultrafilter approach for this specific problem.

4. Results

• Theorem 2.1: The paper successfully proves Van der Waerden's Theorem for any finite coloring and any length $\ell$.
• Lemma 1.3: Establishes a crucial equivalence: The existence of monochromatic $\ell$-term progressions is equivalent to the existence of an ultrafilter $W$ on $\mathbb{N} \times \mathbb{N}$ where the images under $T_0, \dots, T_{\ell-1}$ coincide. This lemma serves as the bridge between the combinatorial statement and the algebraic construction.
• Construction: The proof explicitly constructs the required arithmetic progression $a, a+d, \dots, a+\ell d$ by defining $a$ and $d$ as sums of components extracted from the tensor product of the ultrafilters.

5. Significance

• Methodological Innovation: The paper demonstrates that deep combinatorial results can be proven using ultrafilter algebra without invoking the most complex structural properties of $\beta\mathbb{N}$ (minimality/idempotence). This lowers the barrier to entry for understanding ultrafilter proofs of Ramsey theorems.
• Unification of Techniques: It bridges the gap between nonstandard analysis and ultrafilter theory, showing that the "witnessing" ultrafilters used in nonstandard proofs have direct, constructive counterparts in standard ultrafilter algebra.
• Potential for Generalization: By avoiding specific topological constraints (like minimality), this approach might be more adaptable to proving other partition regularity results where minimal idempotent ultrafilters are difficult to characterize or apply.

In summary, Di Nasso provides a streamlined, purely algebraic ultrafilter proof of Van der Waerden's Theorem that achieves the same result as previous, more complex proofs but with a significantly reduced reliance on advanced topological dynamics.