Schur Numbers (the world's biggest proof) - Numberphile

Key Concepts

Schur Numbers (S_k): The smallest integer n such that any coloring of the integers from 1 to n using k colors must contain a monochromatic solution to a + b = c.
Monochromatic Solution: A set of three numbers (a, b, c) of the same color such that a + b = c. The numbers a, b, and c do not have to be distinct.
Ramsey Theory: A branch of mathematics that studies the conditions under which order must appear. The video uses a concept from Ramsey theory (specifically, the party problem or friends and strangers problem) to prove the existence of Schur numbers.
Monochromatic Triangle: In graph theory, a triangle where all edges are the same color. This is used as an analogy to prove the existence of Schur numbers.
SAT Solver: A computational tool used to solve the Boolean satisfiability problem. It was used in the brute-force proof for S5.
Constructive Proof: A proof that not only shows a mathematical object exists but also provides a method for finding it. The video notes the lack of a constructive proof for Schur numbers.

Schur Numbers and the Coloring Problem

The video explores the concept of Schur numbers, which are related to a coloring problem. The challenge is to color integers from 1 to n using k colors such that there is no monochromatic solution to the equation a + b = c. This means that for any chosen color, there should not be three numbers of that color (a, b, c) where a + b = c. Note that a, b, and c are not required to be distinct.

Fixing Parameters

To address this problem, two parameters need to be fixed:

n: The upper limit of the integers to be colored (e.g., 1 to 4).
k: The number of colors available.

Example: Coloring 1 to 4 with 2 Colors

Let's illustrate with n = 4 and k = 2 colors (pink and green).

Coloring 1: Assign 1 to pink.
Coloring 2: If 2 were pink, then 1 + 1 = 2 would be a monochromatic solution (all pink). Therefore, 2 must be green.
Coloring 3: 3 could be either pink or green. If it were pink, 1 + 2 = 3 would involve two different colors (pink and green), so it wouldn't violate the condition.
Coloring 4: If 4 were green, then 2 + 2 = 4 would be a monochromatic solution (all green). Therefore, 4 must be pink.
Revisiting 3: Now that 4 is pink, if 3 were also pink, then 1 + 3 = 4 would be a monochromatic solution (all pink). Thus, 3 must be green.

The resulting coloring is: 1 (pink), 2 (green), 3 (green), 4 (pink). This coloring successfully avoids any monochromatic a + b = c solutions for n = 4 with k = 2 colors.

The First Failure Point: S2 = 5

When attempting to color integers up to 5 with 2 colors:

Using the coloring for 1 to 4 (1-pink, 2-green, 3-green, 4-pink).
Coloring 5:
- If 5 is pink: 1 + 4 = 5 would be all pink.
- If 5 is green: 2 + 3 = 5 would be all green.

Since 5 cannot be colored without creating a monochromatic solution, the failure point for 2 colors is 5. This means the second Schur number, denoted as S2, is 5.

Known Schur Numbers

S1: The failure point for 1 color is 2. With one color, 1 is fine. But adding 2 creates 1 + 1 = 2, which is monochromatic.
S2: As demonstrated, S2 = 5.
S3: The failure point for 3 colors is 14. It is possible to color numbers 1 to 13 with 3 colors without a monochromatic solution, but it's impossible for 1 to 14. The video presents this as a challenge to the viewer.
S4: The failure point for 4 colors is 45. It is possible to color 1 to 44, but not 1 to 45.

Proving the Existence of Schur Numbers

A crucial aspect is proving that Schur numbers exist for any number of colors k. This means there's always a breaking point n where a monochromatic solution becomes unavoidable.

Connection to Ramsey Theory (Friends and Strangers)

The proof of existence relies on a concept from Ramsey theory, specifically the "friends and strangers" problem. This theorem states that in any group of six people, there must be at least three who are mutual friends or three who are mutual strangers.

This can be visualized with dots (people) and lines (relationships) colored in two colors (e.g., green for friends, pink for strangers). The theorem guarantees that there will always be a monochromatic triangle (three people all friends or all strangers).

This principle can be extended: for k colors, there exists a number of dots (N) such that any coloring of the lines connecting these dots will result in a monochromatic triangle. The video uses the fact that for 2 colors, N = 6.

Constructing an Upper Bound for Schur Numbers

The video proposes a method to establish an upper bound for Schur numbers, thereby proving their existence.

Define n: Let n be the number of dots required to guarantee a monochromatic triangle for k colors (from Ramsey theory).
Coloring Integers 1 to n: Consider coloring the integers from 1 to n using k colors in any arbitrary way.
Graph Construction: Construct a graph with R_k^3 vertices (where R_k is the number from Ramsey theory for k colors). Label these vertices 1, 2, 3, ..., R_k^3.
Edge Coloring: Draw lines (edges) between all pairs of vertices. Color the edge between vertex i and vertex j based on the color of the difference |i - j| in the original coloring of integers 1 to n.
Monochromatic Triangle in the Graph: According to Ramsey theory, this graph must contain a monochromatic triangle. Let the vertices of this triangle be i, j, and k, with i < j < k.
Implication for a + b = c: Since the edges (k - j), (j - i), and (k - i) are monochromatic, their corresponding differences in the original integer coloring must have the same color.
- Let the color of (k - j) be C.
- Let the color of (j - i) be C.
- Let the color of (k - i) be C.
- We know that (k - j) + (j - i) = (k - i).
- This means we have found three numbers (a = k - j, b = j - i, c = k - i) of the same color C, such that a + b = c.

This construction demonstrates that if n is sufficiently large (specifically, n is at least R_k^3), then any coloring of integers 1 to n will inevitably lead to a monochromatic a + b = c solution. This proves that Schur numbers exist, as there is an upper bound for the failure point.

The Fifth Schur Number (S5) and the Largest Proof

The video highlights S5 as a significant achievement due to the immense effort involved in its determination.

Growth of Schur Numbers

The known Schur numbers show a rapid increase:

S1 = 2
S2 = 5 (increase of 3)
S3 = 14 (increase of 9)
S4 = 45 (increase of 31)

The growth appears to be roughly a multiplication by three, though not precisely.

S5 = 161

The fifth Schur number, S5, was determined to be 161. This means that it is possible to color integers from 1 to 160 using 5 colors without a monochromatic a + b = c solution, but it is impossible to do so for integers up to 161.

The "Biggest Mathematical Proof"

The proof for S5 is considered the largest mathematical proof ever, primarily due to its reliance on brute-force computation.

Computational Challenge: For n = 14 and k = 3, there are 3^14 possible colorings. As n and k increase, the number of combinations becomes astronomically large.
Brute-Force Method: The proof for S5 involved checking an enormous number of possibilities. This was achieved using a SAT solver, a computer program designed to determine the satisfiability of Boolean formulas.
Data Volume: The computation generated approximately 288 petabytes of data. (1 petabyte = 1000 terabytes).
Nature of the Proof: Some mathematicians do not consider this purely a "mathematical proof" because it relies heavily on computational verification rather than elegant theoretical deduction. However, it is recognized for its scale and the headline-grabbing nature of being the "biggest."

The Search for S6 and Beyond

The video discusses the ongoing quest for S6 and the challenges involved.

Computational Limits: Determining S6 is currently beyond our computational capabilities. The sheer number of possibilities to check is immense.
Lack of Constructive Proofs: There is no known constructive proof for Schur numbers. A constructive proof would not only show that a number exists but also provide a method to find it. This is a significant area for future mathematical research.
Difficulty of Finding Lower Bounds: To find the k-th Schur number, one must not only find a point of failure (n) but also prove that all numbers less than n do not fail. This requires extensive checking.
Future Guesses: The presenter speculates that S6 might be around 485, based on the observed multiplicative growth.

Conclusion and Takeaways

The video delves into the fascinating world of Schur numbers, illustrating a problem that starts with a simple coloring task and leads to deep mathematical concepts and computational challenges.

Schur numbers represent the limits of avoiding simple arithmetic patterns in colored sets.
Ramsey theory provides a theoretical basis for proving the existence of these numbers.
The determination of S5 highlights the power and limitations of brute-force computation in mathematics.
The search for higher Schur numbers (like S6) remains an open and computationally demanding problem, with a lack of elegant constructive proofs.
The problem, while seemingly abstract, touches upon the fundamental question of how much order can be found in seemingly random arrangements.