Non-local Potts model on random lattice and chromatic number of a plane

This paper investigates the vacuum states and qualitative patterns of a non-local q-color Potts model on a random two-dimensional lattice through numerical simulations, exploring its conjectured relationship to the chromatic number of a plane problem.

The Gist

Imagine you are organizing a massive, chaotic dance party on a giant, irregularly shaped floor. The guests are scattered randomly, and they all have a specific rule: no two people standing exactly one "step" apart can be wearing the same color shirt.

This is the core puzzle the paper tackles, but it's dressed up in the language of physics and mathematics. Here is the story of what the authors did, explained simply.

The Big Problem: The "Coloring" Mystery

Mathematicians have been stuck on a puzzle for decades called the Hadwiger-Nelson problem. It asks: What is the minimum number of colors you need to paint a map (or a floor) so that no two points exactly one unit apart have the same color?

• 1D (A line): Easy. You just alternate Red, Blue, Red, Blue. (2 colors).
• 2D (A flat plane): This is the hard part.
  • We know 3 colors aren't enough (you'll always get a clash).
  • We know 7 colors are definitely enough (there's a known pattern that works).
  • The Mystery: Is the answer 4, 5, 6, or 7? For a long time, nobody knew. (Recent math suggests it's at least 5, but the paper explores this with physics).

The Experiment: A Physics Simulation

Instead of trying to solve this with pure math (which is incredibly hard), the authors turned it into a physics simulation.

1. The Setup: They created a computer model with 159,000 "particles" (dancers) scattered randomly on a 2D surface.
2. The Rule: Each particle has a "color" (like a shirt). If two particles are exactly one "step" away from each other (within a tiny margin), they "repel" each other if they have the same color.
3. The Goal: The system tries to find the "vacuum state"—the most relaxed, lowest-energy arrangement where everyone is happy and no clashes occur. If they find a state with zero energy, it means they found a perfect coloring.

They used a technique called Simulated Annealing. Think of this like shaking a box of marbles.

• At first, the box is hot and shaking wildly (high energy). The marbles can jump anywhere, even into bad spots.
• Slowly, they cool it down. The marbles settle into the lowest possible valleys.
• If they can't find a "zero energy" valley, it means the puzzle is impossible with that many colors.

What They Found

1. Too Few Colors (2, 3, 4)

When they tried with 2, 3, or 4 colors, the system got frustrated.

• 2 Colors: The dancers formed stripes, but there were still clashes.
• 3 Colors: They formed a honeycomb (hexagon) pattern, but it wasn't perfect.
• 4 Colors: Still not perfect. The energy was very low, but not zero.
• Conclusion: This confirms that 4 colors are not enough to solve the puzzle.

2. The Magic Number (7)

When they tried 7 colors, the system was a dream.

• The dancers instantly found a perfect pattern.
• Energy = 0.
• This proves that 7 colors are definitely enough.

3. The Mystery of 5 and 6

This is where it gets interesting.

• 6 Colors: The system mostly found perfect solutions (zero energy), but sometimes it got stuck in slightly imperfect patterns. It's a "maybe."
• 5 Colors: This is the big surprise. The system could never find a perfect solution.
  • Even after thousands of tries, the energy never hit zero.
  • The dancers tried to form a hexagon pattern, but one color kept getting pushed out of the way.
  • The Analogy: Imagine trying to fit 5 different types of furniture into a room designed for 4 or 6. One piece of furniture (the 5th color) just doesn't fit the geometry of the room. It gets squished into the corners or the middle, breaking the perfect symmetry.

The "Aha!" Moment: Why 5 Fails

The authors noticed something beautiful about the 5-color failure.

• Nature loves symmetry. Hexagons (6 sides) are very stable and fit together perfectly.
• But 5-fold symmetry (like a starfish or a pentagon) is geometrically "impossible" to tile a flat floor without gaps or overlaps.
• In their simulation, the "physics" of the floor forced the system to break the color symmetry. One color became the "odd one out," appearing much less frequently than the others, just to keep the peace. The geometry of the floor won the fight against the color rules.

The Takeaway

This paper uses a computer physics game to tackle a famous math mystery.

• It confirms that 4 colors are not enough.
• It strongly suggests that 5 colors are also not enough (because the system couldn't find a perfect solution, and the geometry fights against it).
• It shows that 7 colors work perfectly.

So, while the paper doesn't mathematically prove the answer is 5 or 6, it provides strong physical evidence that the answer is likely 5, 6, or 7, and that the number 5 is particularly difficult because our flat world just doesn't like the number 5!

Technical Summary

1. Problem Statement

The paper investigates a non-local $q$-color Potts model defined on a random 2D lattice (a set of $N$ points randomly distributed in a compact region). Unlike standard Potts models where interactions occur between nearest neighbors, this model features a non-local interaction kernel where spins interact only if their distance falls within a specific annular range: $R - \delta/2 \le |i - k| \le R + \delta/2$.

The primary objectives are:

1. To analyze the vacuum states (ground states) of this system by minimizing the energy functional.
2. To determine the minimal number of colors ($q$) required to achieve a zero-energy state (where no two spins of the same color interact).
3. To explore the connection between this statistical physics model and the Hadwiger-Nelson problem (EHN problem), a famous combinatorial topology problem asking for the minimum number of colors needed to color the Euclidean plane such that no two points at unit distance share the same color.

2. Methodology

Model Definition

• System: $N$ sites randomly distributed in a square of size $L \times L$.
• Spins: Each site $i$ has a spin $\sigma_i$ represented by a $q$-component vector where exactly one component is 1 (the "color") and others are 0.
• Interaction: Two spins interact if their distance is within a ring of radius $R$ and width $\delta$. The energy contribution is non-zero only if interacting spins have the same color.
• Energy Function: $E = \sum J_{xy} \delta_{i(x)i(y)}$, where the sum is over interacting pairs. The goal is to find configurations where $E=0$.
• Parameters:
  • $R = 1.0$ (interaction radius).
  • $\delta = 0.02$ (interaction width).
  • $L = 20.0$.
  • $N \approx 159,155$ (particle density fixed to ensure an average of $\langle n \rangle = 50$ interacting neighbors per spin).
  • $q \in \{2, 3, 4, 5, 6, 7\}$.

Boundary Conditions

Due to the non-local nature of the interaction, periodic boundary conditions were deemed unsuitable as they introduce artificial effects based on the ratio $L/R$. Instead, fixed boundary conditions were used: a "belt" of particles around the perimeter was assigned fixed colors and held constant during minimization. The energy was calculated only within an internal region ($11 \times 11$) to avoid boundary artifacts.

Algorithm

The authors employed Simulated Annealing rather than a simple greedy algorithm to avoid getting trapped in local minima.

• Process: Starting from a random configuration, the algorithm iterates through particles, randomly changing their colors.
• Acceptance: A new color is accepted if it lowers the energy. If it increases the energy, it is accepted with probability $P = \exp[(E - E')/T]$, where $T$ is a temperature parameter that decreases linearly over time.
• Execution: 200 independent runs were performed for each value of $q$.

3. Key Results

The study analyzed the ground state patterns and energy levels for different numbers of colors ($q$):

• $q = 2$: The system forms alternating stripes. The energy remains high (~65% of the initial random energy), indicating no zero-energy solution.
• $q = 3$: The system forms a hexagonal pattern. The energy drops significantly (~31% of initial), but the pattern is not a perfect hexagonal lattice; "mixing" at cluster borders reduces energy further.
• $q = 4$: The pattern remains hexagonal. The energy is very low (~3% of initial) but never reaches zero. The authors note that even "nearly perfect" colorings do not yield the global minimum, suggesting that 4 colors are insufficient for a zero-energy state on this random lattice.
• $q = 5$:
  • The system exhibits color symmetry breaking. While the geometric pattern remains hexagonal, only four of the five colors form the regular tiling. The fifth color is "displaced," forming irregular, random clusters.
  • Energy: Despite the low energy (~1% of initial), no zero-energy configurations were found in 200 runs. There is a distinct gap in the energy distribution between $q=5$ and $q=6$.
  • Symmetry: The ratio of the least represented color to the total number of particles remains low even for large areas, confirming a global rather than local symmetry breaking.
• $q = 6$: Zero-energy configurations appear in approximately 4% of runs. The pattern is a juxtaposition of regular lattices for each color.
• $q = 7$: As expected from the known mathematical solution to the EHN problem (using a regular hexagonal tiling), zero-energy states were found in 97.5% of runs. This validates the simulation algorithm.

4. Key Contributions

1. Numerical Validation of the Hadwiger-Nelson Problem: The study provides strong numerical evidence supporting the mathematical conjecture that 4 colors are insufficient to color the plane without unit-distance monochromatic pairs. It further suggests that 5 colors are also insufficient, narrowing the possible chromatic number of the plane to 6 or 7 (consistent with recent mathematical proofs that $q \ge 5$).
2. Discovery of Color Symmetry Breaking: The authors identified a novel phenomenon where the system minimizes energy by breaking color symmetry for $q=5$. The system prefers a geometrically optimal hexagonal tiling (which requires 6-fold symmetry) over equal representation of all 5 colors, effectively "discarding" one color to satisfy geometric constraints.
3. Non-Local Model Analysis: The paper characterizes the behavior of Potts models with non-local, ring-shaped interactions on random lattices, highlighting the differences between nearest-neighbor models and those with finite-range interactions.

5. Significance and Conclusion

The paper bridges statistical physics and combinatorial topology. By mapping the Hadwiger-Nelson problem onto a non-local Potts model on a random lattice, the authors demonstrate that the geometric constraints of the plane (specifically the lack of 5-fold crystallographic symmetry) dictate the coloring properties.

• Implication for EHN: The inability to find a zero-energy state for $q=5$ supports the recent mathematical proof that the chromatic number of the plane is at least 5.
• Physical Insight: The results illustrate that in systems with non-local interactions, the competition between geometric symmetry (hexagonal tiling) and discrete degrees of freedom (color count) can lead to spontaneous symmetry breaking, where the system sacrifices the uniformity of a specific degree of freedom to minimize global energy.

The authors conclude that while $q=7$ is a known solution and $q=4$ is insufficient, the case of $q=6$ requires further refinement to determine if it is the true minimum, though their data suggests $q=5$ is definitively not a solution.