Chromatic thresholds for linear equations and recurrence

This paper establishes that the chromatic threshold for a homogeneous linear equation over $\mathbb{F}_p$ is zero if and only if the equation contains a zero-sum subcollection of at least three coefficients, utilizing equivariant topological methods to resolve a question by Griesmer and extend results on recurrence in infinite abelian groups.

The Gist

Imagine you are organizing a massive party in a circular room with $p$ seats, numbered from 0 to $p-1$. You want to invite a large group of guests (a subset of the seats) to sit down, but you have a very specific rule: No three guests can sit in a pattern that satisfies a certain mathematical equation.

For example, if your rule is "No three guests can sit such that Guest A + Guest B = Guest C," you are trying to avoid "Schur triples."

This paper is about a fascinating question: If you manage to invite a huge crowd without breaking this rule, does the "social structure" of your party become chaotic, or can you still organize it neatly?

Here is the breakdown of the paper's discoveries using simple analogies.

1. The Two Ways to Measure "Chaos"

In mathematics, when we look at a group of people (or numbers) avoiding a pattern, we usually ask two questions:

• The "Roth" Question (Size): Can you have a huge crowd without breaking the rule?
  • Answer: Sometimes yes, sometimes no. If the rule is "A + B = C," you can't have a huge crowd. But if the rule is "A + 2B = C," you can have a huge crowd.
• The "Chromatic" Question (Organization): If you do have a huge crowd, can you color them with a small number of colors (like Red, Blue, Green) so that no two people who "know each other" (are connected by the rule) have the same color?
  • The "Cayley Graph" Metaphor: Imagine drawing a line between any two guests if their difference fits the rule. If you need 1,000,000 colors to paint this party so no connected people share a color, the party is "chaotic." If you only need 5 colors, it's "organized."

2. The Big Discovery: The "Three-Person" Rule

The authors discovered a surprising threshold that determines whether a party can be organized or not.

They found that the ability to organize the party (keep the number of colors low) depends entirely on the coefficients (the numbers multiplying the guests) in the equation.

• The "Bad" Case (Chaos): If the equation has a "zero-sum" group of three or more coefficients (e.g., $1 + 2 - 3 = 0$), then any huge crowd you invite will be chaotic. You will need an infinite number of colors as the party gets bigger. You cannot organize them neatly.
• The "Good" Case (Order): If the equation does not have a zero-sum group of three or more coefficients (e.g., the only way to get zero is $1 - 1 = 0$, which is just two people canceling each other out), then you can always organize the party. No matter how huge the crowd is, you can always color them with a fixed, small number of colors.

The Analogy:
Think of the equation as a set of instructions for a dance.

• If the instructions involve a complex trio move that cancels itself out (like a three-person circle that returns to the start), the dancers will inevitably get tangled up in a chaotic mess if there are too many of them.
• If the instructions only involve simple pairs canceling out, the dancers can always be sorted into neat, orderly lines, no matter how many people show up.

3. How They Proved It: The "Hamming Ball" and the "Topological Trap"

To prove that the "Bad" cases are truly chaotic, the authors had to build a specific type of party that is huge but impossible to organize.

• The Construction: They used a concept called a "Hamming ball." Imagine a high-dimensional space where every guest is a long string of numbers. They picked guests who are all "close" to a specific "all-ones" string (like a string of all 1s).
• The Topological Trap: To prove these guests can't be colored, they used a tool from topology (the study of shapes) called the Borsuk-Ulam Theorem.
  • The Metaphor: Imagine a sphere (like a beach ball). The theorem says that if you try to paint the surface of the ball with a limited number of colors, and you have a specific symmetry (like rotating the ball), you are forced to paint two opposite points the same color.
  • The authors built a "Kneser graph" (a complex web of connections) that fits inside this party. They showed that this web is so twisted and interconnected that, due to the "three-person" symmetry, it forces a contradiction: you simply cannot color it without running out of colors.

4. Why This Matters: The "Recurrence" Connection

The paper connects this math problem to dynamics (how things move and repeat over time).

• Measurable Recurrence: If you have a pattern that repeats often enough to be statistically guaranteed (like a clock ticking), it's "measurable."
• Topological Recurrence: If a pattern repeats in a way that is visible in the structure of the space, it's "topological."

For a long time, mathematicians wondered: If a pattern repeats topologically, does it also repeat measurably?

• In the world of even numbers (like $Z_2$), the answer is No. You can have a pattern that looks like it repeats everywhere, but statistically, it doesn't.
• This paper proves that this "No" answer applies to every infinite group of numbers, not just even ones. They showed that you can always find a set of numbers that is "topologically recurrent" (structurally repeating) but "not measurably recurrent" (statistically rare).

Summary

1. The Problem: Can we organize a huge group of numbers that avoids a specific linear equation?
2. The Answer: It depends on the equation.
   • If the equation has a "zero-sum" group of 3 or more numbers, the group is unorganizable (infinite colors needed).
   • If it doesn't, the group is organizable (finite colors needed).
3. The Method: They used high-dimensional geometry and topological "traps" (Borsuk-Ulam) to prove that certain groups are inherently chaotic.
4. The Impact: This solves a decades-old question about whether "structural repetition" implies "statistical repetition," showing that they are fundamentally different things in the mathematical universe.

In short: If your math rule involves a trio of numbers canceling each other out, chaos is inevitable. If it doesn't, order is always possible.

Technical Summary

Here is a detailed technical summary of the paper "Chromatic thresholds for linear equations and recurrence" by Hong Liu, Zhuo Wu, Ningyuan Yang, and Shengtong Zhang.

1. Problem Statement and Context

The paper investigates a chromatic analogue of classical Roth-type problems in additive combinatorics, specifically within the setting of linear equations over finite fields $\mathbb{F}_p$.

• Classical Context: Roth's theorem and its generalizations (Szemerédi's theorem) establish that any subset of a group with positive density must contain solutions to certain linear equations (e.g., arithmetic progressions).
• Graph-Theoretic Analogue: The authors shift focus from the size of solution-free sets to the structure of the Cayley graphs generated by these sets. For a homogeneous linear equation $L: \sum_{i=1}^k c_i x_i = 0$, let $A \subseteq \mathbb{F}_p$ be a set containing no solutions to $L$ with distinct elements. The authors study the Cayley graph $\text{Cay}(\mathbb{F}_p, A)$.
• The Core Question: Does a dense $L$-solution-free set $A$ necessarily induce a Cayley graph with a bounded chromatic number (independent of $p$)?
• Definition: The chromatic threshold $\delta_\chi(L)$ is defined as the infimum of densities $d > 0$ such that any $L$-solution-free set $A$ with $|A| \ge d p$ has $\chi(\text{Cay}(\mathbb{F}_p, A)) \le C$ for some constant $C$. The paper aims to classify exactly when $\delta_\chi(L) = 0$.

2. Main Results

The paper provides a complete classification of linear equations based on their chromatic threshold.

Theorem 1.4 (Main Classification):
Let $L: \sum_{i=1}^k c_i x_i = 0$ be a homogeneous linear equation with $k \ge 3$ and non-zero integer coefficients. The following are equivalent:

1. $\delta_\chi(L) = 0$. (i.e., Every dense $L$-solution-free set induces a Cayley graph with unbounded chromatic number).
2. There exists a subset of coefficients of $L$ of size at least three whose sum is zero.

Key Distinctions:

• Roth Degenerate: If $\sum c_i = 0$, positive density forces a solution (Roth's theorem).
• Ramsey-Turán Degenerate: If any non-empty subset of coefficients sums to zero, dense solution-free sets have small independence numbers (Theorem 1.2).
• Chromatic Threshold: The condition is strictly stronger than Ramsey-Turán degeneracy but weaker than full Roth degeneracy. Specifically, a zero-sum pair (e.g., $c_1 + c_2 = 0$) is insufficient to force bounded chromatic number; a zero-sum triple (or larger) is required.

Theorem 1.5 (Quantitative Lower Bound):
To prove the necessity of the zero-sum triple condition, the authors resolve a question by Griesmer regarding Cayley graphs on $\mathbb{Z}_p^n$ generated by Hamming balls.

• Let $S = \{x \in \mathbb{Z}_p^n : d(x, \mathbf{1}) \le p\sqrt{n}\}$.
• Then $\chi(\text{Cay}(\mathbb{Z}_p^n, S)) \ge \sqrt{n}/p^3$.
• Furthermore, the independence number $\alpha(\text{Cay}(\mathbb{Z}_p^n, S)) = \Omega(p^n)$, showing these graphs are dense but have large independent sets.

Corollary 1.6 (Dynamical Systems Application):
The results imply a separation between topological recurrence and measurable recurrence for every infinite discrete abelian group $\Gamma$. There exists a subset $S \subset \Gamma$ that is topologically recurrent (Cayley graph has infinite chromatic number) but not measurably recurrent. This extends seminal counterexamples by Kríž and Ruzsa (previously known only for characteristic 2) to all characteristics.

3. Methodology and Technical Approach

The proof involves two distinct directions, utilizing different mathematical tools.

Direction 1: $(b) \implies (a)$ (Zero-sum triple $\implies$ Bounded Chromatic Number)

• Assumption: $L$ has a zero-sum subcollection of coefficients of size $\ge 3$.
• Strategy: Fourier Analysis and Bohr Sets.
  1. Assume $A$ is $L$-solution-free and dense.
  2. Use a supersaturation theorem (Green's arithmetic removal lemma) to show that the restriction of $L$ to the zero-sum subset has many solutions.
  3. This forces a structural restriction: $A$ cannot have too many points in the "large spectrum" Bohr set associated with the equation.
  4. Coloring Construction: Partition $\mathbb{F}_p$ based on the phases of the characters in the large spectrum. This creates a bounded number of cells where differences lie within a small Bohr set.
  5. Since $A$ has few points in this Bohr set, the induced subgraph on each cell has bounded degree, implying bounded chromatic number via Brooks' theorem.
  6. Crucial Step: The "at least three coefficients" condition is essential here to control higher moments via Parseval's identity, which fails if only a pair sums to zero.

Direction 2: $(a) \implies (b)$ (No zero-sum triple $\implies$ Unbounded Chromatic Number)

• Assumption: No subset of coefficients of size $\ge 3$ sums to zero.
• Strategy: Constructive Combinatorics and Topological Obstructions.
  1. Stage 1: Topological Obstruction (Generalized Kneser Graphs).
     • The authors introduce a Generalized Kneser Graph $KN(n, k, p-1)$, where vertices are ordered $(p-1)$-tuples of disjoint $k$-sets.
     • Adjacency is defined by cyclic prefix-suffix disjointness.
     • Lower Bound: They prove $\chi(KN(n, k, p-1)) \ge \frac{n}{p-k} \frac{1}{p(p-1)}$ using an equivariant Borsuk-Ulam type argument.
     • Mechanism: They map the sphere $S^{2r-1}$ to a cover of open sets based on a proper coloring. An equivariant map forces a full $\mathbb{Z}_p$-orbit into one set, leading to a contradiction (either an edge within a color class or a boundary size violation).
  2. Embedding: They embed $KN(n, k, p-1)$ into the Cayley graph $\text{Cay}(\mathbb{Z}_p^n, S)$ where $S$ is a Hamming ball around the all-ones vector. This transfers the high chromatic number to the Cayley graph.
  3. Stage 2: Arithmetic Lifting.
     • The Hamming ball generator is not necessarily $L$-solution-free.
     • The authors construct a dense set $A \subset \mathbb{F}_p$ by lifting a set from a product group $\mathbb{Z}_m$.
     • They define a "furthest-from-endpoints" set $E_0$ (analogous to the Hamming ball) and an extension set $F_0$.
     • Using Berry-Esseen estimates (probabilistic methods), they show $F_0$ has linear size and does not introduce solutions to $L$ because the contributions from $E_0$ and $F_0$ cannot cancel out due to norm separation.
     • The final set $A = E \cup F$ is dense, $L$-solution-free, and contains the high-chromatic subgraph.

4. Significance and Implications

1. Resolution of Griesmer's Question: The paper confirms that Cayley graphs on $\mathbb{Z}_p^n$ generated by Hamming balls have unbounded chromatic number for odd primes $p$, a question left open by Griesmer.
2. Refinement of Extremal Theory: It establishes a precise hierarchy between different notions of degeneracy in linear equations:
   $$\text{Roth Degenerate} \subsetneq \text{Vanishing Chromatic Threshold} \subsetneq \text{Ramsey-Turán Degenerate}$$
   This highlights that the "zero-sum triple" condition is the exact threshold for bounded chromatic number, distinct from the conditions for forcing solutions or small independence numbers.
3. Topological Dynamics: The work provides a unified framework to separate topological recurrence from measurable recurrence in all infinite discrete abelian groups, not just those of characteristic 2. This deepens the understanding of the relationship between combinatorial structure (chromatic number) and dynamical properties (recurrence).
4. Methodological Innovation: The introduction of the Generalized Kneser Graph and the use of equivariant Borsuk-Ulam arguments in the context of additive combinatorics over $\mathbb{Z}_p^n$ represent significant technical advances, bridging topological combinatorics and additive number theory.

5. Open Problems

The authors conclude by noting that while they characterize when $\delta_\chi(L) = 0$, the exact positive values of $\delta_\chi(L)$ for equations where it is non-zero remain unknown. They specifically pose the problem of determining $\delta_\chi(\{x+y=z\})$ (the Schur equation). They also suggest investigating the VC-dimension threshold as a related measure of largeness for solution-free sets.