Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?

Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?

Speakers: Konrad Mundinger, Max Zimmer, Aldo Kiem, Christoph Spiegel, Sebastian Pokutta

Conference: ICML 2025

YouTube: https://slideslive.com/39044077

Overview

This talk, presented by researchers from the IOL Research Lab in Berlin, delves into the fascinating intersection of machine learning and pure mathematics, presenting a compelling case study of AI-driven scientific discovery. The central theme revolves around leveraging advanced ML tools, particularly implicit representations and gradient-based optimization, to guide mathematical intuition and uncover novel structures for long-standing open problems. The researchers frame their work as a method to assist in the discovery of "extremal structures," a common challenge in mathematics where the goal is to find an optimal configuration or arrangement under specific constraints.

The specific problem tackled is the Hadwiger-Nelson problem, also known as determining the chromatic number of the Euclidean plane. This problem, deceptively simple in its statement, has remained unresolved for over 50 years, asking for the minimum number of colors required to color the plane such that no two points at unit distance share the same color. The talk highlights how machine learning, traditionally associated with image generation, can be re-purposed to "dream up" and visualize potential solutions, effectively serving as a powerful assistant in the often-abstract world of mathematical proofs and disproofs.

The significance of this work extends beyond solving a particular mathematical puzzle. It pioneers a methodology for using continuous, differentiable models to explore discrete combinatorial problems, opening new avenues for computational mathematics. By demonstrating the ability of neural networks to recover known solutions and propose new, provable improvements for variants of the Hadwiger-Nelson problem, the research illustrates the profound potential of AI to accelerate and augment human creativity in fundamental scientific inquiry. The project underscores the idea that while machines may not yet write formal proofs, they can be indispensable in generating the hypotheses and structures that lead to them.

Background

▶ Watch: Introduction to AI for mathematical discovery (0:00)

The Hadwiger-Nelson problem is a classic in geometric graph theory, posing a seemingly straightforward question: what is the minimum number of colors needed to color every point in the Euclidean plane such that any two points exactly one unit apart have different colors? Despite its simple articulation, this problem has resisted a definitive solution for over five decades, making it a celebrated open problem in mathematics. It can be visualized as placing unit-length matchsticks on the plane; the ends of any matchstick must have different colors.

Historically, progress on the Hadwiger-Nelson problem has focused on establishing lower bounds (the minimum number of colors required) and upper bounds (the maximum number of colors known to be sufficient). For many years, the lower bound stood at 4, established by simple geometric arguments. A significant breakthrough occurred in 2018 when Aubrey de Grey demonstrated that at least 5 colors are necessary. The upper bound, however, has remained at 7 colors for a considerable time. This upper bound is typically achieved through explicit constructions involving tessellations or tilings of the plane with polytopal shapes. Common examples include shifted square tilings or hexagonal tilings, where careful coloring patterns ensure that no unit-distance points share a color. The challenge lies in reducing this upper bound or increasing the lower bound to finally converge on a single, definitive chromatic number for the plane.

Traditional computational approaches to such problems often involve discretizing the plane, essentially turning a continuous problem into a finite, albeit large, combinatorial one. While this can be effective for certain problems, it often sacrifices the inherent continuous nature of the Euclidean plane, potentially missing elegant, non-discrete solutions. The speakers were inspired by the power of AI-driven image generation, realizing that for some mathematical problems, a visual representation or "image" is intrinsically linked to its proof or disproof. They sought to explore if machine learning, specifically techniques capable of modeling continuous functions, could offer a fresh perspective on generating these elusive colorings, moving away from purely discrete computational methods. The goal was to harness the ability of neural networks to learn complex, continuous mappings and generate novel structures that might evade human intuition or traditional combinatorial searches.

Key Findings

▶ Watch: Current upper bound of seven colors and examples (2:29)

The research presented several key findings that underscore the potential of machine learning in mathematical discovery:

Firstly, the team successfully developed and validated a novel machine learning framework for generating colorings of the Euclidean plane. By employing implicit representations via feed-forward neural networks with sinus activations, they were able to model continuous probabilistic colorings. This approach not only recovered previously known constructions but did so in a way that demonstrated the network's ability to learn intricate geometric patterns. For instance, when tasked with finding a 6-coloring, the neural network independently converged on a structure strikingly similar to the pentagonal rod construction initially discovered by Pritikin in 1995. This validation step was crucial, showing that the ML approach could "rediscover" existing mathematical knowledge, thus building confidence in its ability to generate novel structures.

Secondly, the framework led to a provable improvement for a specific variant of the Hadwiger-Nelson problem. This variant asks how much of the plane needs to be removed to enable coloring with fewer than 6 or 7 colors. Specifically, for coloring with 5 colors, the neural network suggested a construction that required removing less than 4% of the plane, a notable improvement over previous best-known bounds which required more than 4%. The researchers were able to formalize this ML-generated insight into a mathematical theorem, demonstrating that the output of the neural network could serve as a powerful hypothesis generator, leading directly to new proofs. The process involved taking the neural network's non-intuitive output, isolating key regions, discretizing them, and then applying a "discrete polishing heuristic" to formalize the structure.

Thirdly, the research yielded new constructions for the "off-diagonal" variant of the problem, where the constraint on unit-length matchsticks is relaxed to allow for slightly different lengths. By making a minor modification to their approach, the team developed constructions that significantly expanded the range of distances for which 6-colorings are realizable. They presented two distinct colorings that collectively covered this expanded range, showcasing the versatility of their ML framework to adapt to modified problem constraints. These new constructions, again, were described as "beautiful" and "interesting," and unlikely to be discovered without computational assistance. Formalizing these particular findings required pulling out "some basic trigonometry," highlighting the complementary role of human mathematical expertise in transforming ML outputs into rigorous proofs.

Finally, the work emphasized a critical insight: while machine learning can brilliantly generate candidate solutions and guide intuition, its outputs are inherently numerical and not formal proofs. Bridging this gap requires human mathematical intervention, whether through discretization, heuristic polishing, or applying classical geometric and trigonometric principles. This highlights ML's role as an immensely powerful tool for exploration and hypothesis generation in mathematics, rather than an autonomous prover.

Technical Deep Dive

▶ Watch: Novel ML approach: probabilistic relaxation for colorings (3:38)

The core of this research lies in its innovative technical approach to tackling the Hadwiger-Nelson problem, moving from discrete combinatorial search to continuous optimization.

Probabilistic Relaxation:

Instead of directly assigning a discrete color to each point in the Euclidean plane, the team introduced a probabilistic relaxation. This means that every point (x, y) in the plane is assigned a categorical distribution over the available colors. For instance, if using k colors, each point would output a k-dimensional vector of probabilities summing to 1. This continuous representation is crucial because it makes the problem amenable to gradient-based optimization.

Loss Function and Differentiability:

To guide the learning process, a differentiable loss function was defined. This loss essentially quantifies the expected number of conflicts. If a unit-length matchstick is randomly dropped on the plane, the loss counts the probability that its two endpoints receive the same "color" (i.e., their assigned categorical distributions have high overlap for the same color). Crucially, if a probabilistic coloring achieves a loss of zero, it can be deterministically converted into a valid coloring (up to a measure zero set) that satisfies the original constraints. The key challenge then became finding an easily differentiable family of functions that could model these probabilistic colorings.

Neural Networks and Activation Functions:

The researchers opted for feed-forward neural networks as their parameterized function family. Neural networks are highly expressive and, as highlighted, their differentiability is key for optimization. A specific architectural choice was the use of sinus activations (e.g., sin(x) instead of ReLU) in the hidden layers. This choice was motivated by prior work on implicit representations, particularly the Siren (Sine Representation Networks) paper, which demonstrated that periodic activation functions are exceptionally powerful for representing continuous signals and coordinate-based neural networks. These networks are well-suited for tasks where the output is a function of spatial coordinates, like an image or a coloring of the plane.

Optimization Algorithm:

The training algorithm is remarkably simple yet effective: batch gradient descent with Monte Carlo sampling.

1. Batch Sampling: In each iteration, a "batch" consists of a collection of randomly sampled unit-length matchsticks placed on the plane. For each matchstick, its two endpoints are evaluated by the neural network to get their respective probabilistic color distributions.
2. Conflict Probability: For each matchstick, the probability that its two endpoints would receive the same color is computed based on their categorical distributions. This directly feeds into the loss function.
3. Gradient Computation: The gradient of this conflict probability (and thus the overall loss) with respect to the neural network's parameters is computed.
4. Parameter Update: The network parameters are then updated using gradient descent to minimize the loss, pushing the network towards configurations where unit-distance points are unlikely to share the same color.

Variants and Modifications:

The framework was adapted for different variants of the Hadwiger-Nelson problem:

• Plane Removal Variant: To find colorings that require removing the minimum amount of the plane, a Lagrangian term was added to the loss function. This term penalizes the "uncolored" or "removed" regions, encouraging the network to minimize their extent while still satisfying the coloring constraints for the remaining plane.
• Off-Diagonal Variant: For this variant, where the matchstick length can vary from the unit distance, the modification involved adjusting how the "conflict" was calculated based on the specific matchstick lengths being considered. This allowed the network to explore colorings valid for a range of distances, not just precisely one unit.

The choice of sinus activations and the careful handling of initialization (which was noted as a "huge issue" requiring specific scaling methods, again referencing the Siren paper) were crucial for the stability and effectiveness of the training process, enabling the neural network to converge on complex, structured colorings. The resulting output, while continuous, could then be interpreted (e.g., via argmax) to reveal the discrete coloring patterns.

Experimental Setup & Results

▶ Watch: Live demo: Neural network attempting a 6-coloring (5:18)

The experimental setup leveraged standard machine learning practices adapted for this unique mathematical problem. The core component was a feed-forward neural network with multiple hidden layers, utilizing sinus activation functions. The specific architecture (number of layers, width) was not detailed in the transcript but implied to be "very simple."

Training Methodology:

The networks were trained using batch gradient descent with Monte Carlo sampling. This involved iteratively:

1. Randomly sampling matchsticks (unit length for the standard problem, or varied lengths for the off-diagonal variant) within a specific sub-box of the Euclidean plane.
2. Evaluating the neural network at the endpoints of these matchsticks to obtain probabilistic color distributions.
3. Calculating the "expected number of conflicts" as the loss, based on these distributions.
4. Updating the neural network's parameters via gradient descent to minimize this loss.

The goal was to achieve a loss value "reasonably close to zero," which would indicate a high-quality probabilistic coloring convertible to a deterministic one.

Initialization Sensitivity:

A significant practical challenge highlighted was the sensitivity of the initialization for networks using periodic activation functions. The speakers noted this was "a huge issue" and referred to the Siren paper for specific initialization strategies (e.g., careful scaling) that increase the chance of successful convergence. Without proper initialization, the network might struggle to learn meaningful representations.

Results for 6-Coloring:

When the network was tasked with coloring the plane using six colors, it successfully converged on a structure characterized by "pentagon sort rods" intersecting and tiling the plane. While the loss was "reasonably close to zero," it was "not entirely zero," indicating some subtle issues. The speakers explained that these issues arise from the inherent geometric constraints of a 6-coloring: either a matchstick covers an entire colored "blob" (like a red pentagonal region), leading to conflicts between adjacent blobs, or the matchstick is scaled down to avoid these adjacent conflicts, but then conflicts emerge within the blob itself. Despite these minor imperfections, the generated pattern was recognized as a well-known construction, first described by Pritikin in 1995, providing strong validation for the ML approach's ability to recover existing mathematical insights.

Results for Plane Removal Variant (5 Colors):

For the variant where parts of the plane can be removed to allow coloring with fewer colors, the approach involved adding a Lagrangian term to the loss function. The numerical results were compelling:

• The model successfully recovered known bounds for coloring with one through four colors.
• Crucially, for five colors, the neural network suggested a construction that required removing less than 4% of the plane. This was an improvement over previous best-known results, which indicated needing "a bit more than 4%" of the plane removed.
• The neural network's output for this variant was visually "not entirely intuitive," but the researchers were able to formalize it into a theorem. This involved isolating specific areas, discretizing them into pixel values, and applying a "discrete polishing heuristic" to resolve any remaining numerical issues and yield a formal mathematical proof.

Results for Off-Diagonal Variant:

In the off-diagonal variant, where matchstick lengths could vary, the approach again involved a "minor modification" to the loss function to account for the range of distances. The results were equally impactful:

• The model generated new constructions that significantly expanded the range of distances for which 6-colorings are realizable.
• The team identified two distinct colorings that together covered this expanded range.
• Visually, these outputs were described as "quite beautiful," "interesting," and possessing properties that would make them "unlikely that you might come up with this without computer assistance."
• Formalization in this case required "pulling out some basic trigonometry," underscoring the necessity of human mathematical expertise to convert ML-generated insights into rigorous proofs.

Across all experiments, the emergence of periodic structures in the neural network's output was consistently observed, a characteristic that aligns with many known optimal colorings in the plane.

Practical Implications

▶ Watch: Resulting 'pentagon rods' pattern from 6-coloring attempt (6:00)

The research presented has several profound practical implications for practitioners in various fields, extending beyond pure mathematics to potentially impact infrastructure teams, model builders, and deployers working with complex optimization or design problems.

1. Machine Learning as an Intuition Engine for Mathematics:

The most significant implication is the establishment of ML, specifically through implicit representations and gradient-based optimization, as a powerful tool for guiding mathematical intuition and discovering novel structures. For mathematicians, this offers a new lens through which to explore long-standing open problems, particularly those involving extremal structures or geometric arrangements. It's a shift from ML as a prediction engine to ML as a hypothesis generator, allowing researchers to visualize and experiment with complex configurations that might be too intricate for manual derivation.

2. Bridging the Gap Between Numerical Discovery and Formal Proof:

The work highlights a critical challenge and opportunity: the inherent gap between a numerical output from an ML model and a rigorous mathematical proof. While neural networks can generate highly compelling candidate solutions, these are not formal proofs. Practitioners in computational science must understand that human mathematical expertise remains indispensable for translating these numerical insights into provable theorems. This might involve applying techniques like discretization, geometric analysis, or combinatorial polishing to formalize the ML-generated structures. This collaborative paradigm, where ML accelerates discovery and human intellect ensures rigor, could be a blueprint for future scientific endeavors.

3. Generalizability to Other Extremal Problems:

The methodology employed (probabilistic relaxation, implicit representations with sinus activations, gradient descent) is highly generalizable. It could be adapted to a wide array of other extremal problems in combinatorics, geometry, or even physical sciences where the goal is to find optimal configurations under constraints, and where the solution space is continuous. Examples might include optimal packing problems, material design, or even certain aspects of circuit layout. For model builders, this presents a new class of problems solvable by continuous optimization techniques, moving beyond traditional classification or regression tasks.

4. Trade-offs and Limitations:

Practitioners must be aware of the trade-offs. While ML offers speed and novelty in exploration, it comes with challenges:

• Initialization Sensitivity: As noted, neural networks with periodic activation functions can be highly sensitive to initialization, requiring careful tuning and potentially specialized methods (like those from Siren).
• Computational Cost: Exploring large, continuous spaces with Monte Carlo sampling and gradient descent can be computationally intensive, requiring significant GPU/TPU resources.
• Interpretability: While the visual output is helpful, understanding why the network arrived at a particular solution can still be opaque, making formalization a non-trivial task.
• Scope: The current approach excels at generating structures but doesn't inherently provide the logical steps for a proof.

5. Implications for Infrastructure and Software Stacks:

For infrastructure teams and deployers, this research suggests an increasing need for robust computational environments that can handle complex, continuous optimization tasks. The use of specialized activation functions and custom loss formulations might require flexible ML frameworks (e.g., PyTorch, TensorFlow) and efficient hardware accelerators. The iterative nature of research, where ML output informs human analysis which then guides further ML exploration, also demands flexible experimental platforms.

Ultimately, this work positions machine learning not just as an analytical tool, but as a creative partner in scientific discovery, pushing the boundaries of what is computationally feasible in fields previously dominated by human intuition and symbolic reasoning.

Key Takeaways

• ML as a Mathematical Intuition Guide: Machine learning, specifically neural networks, can serve as a powerful tool to guide mathematical intuition and discover novel structures for long-standing open problems in pure mathematics.
• Continuous Probabilistic Colorings: The Hadwiger-Nelson problem can be effectively approached by modeling continuous probabilistic colorings of the Euclidean plane using implicit representations via neural networks.
• Sinus Activations for Implicit Representations: Feed-forward neural networks with sinus activations (as in Siren networks) are particularly effective for modeling continuous functions over spatial coordinates, enabling the generation of intricate geometric colorings.
• Validated and Novel Discoveries: The ML framework successfully reproduced known 6-colorings (e.g., Pritikin's pentagonal rods) and led to new, formally provable improvements for variants of the problem, such as requiring less than 4% plane removal for 5-colorings and expanding the range of realizable distances for off-diagonal variants.
• Bridging Numerical Output to Formal Proof: While ML generates compelling numerical outputs, human mathematical expertise (e.g., discretization, trigonometry, heuristic polishing) remains crucial to formalize these insights into rigorous, provable theorems.
• Potential for Broader Application: The methodology holds significant promise for exploring other extremal problems in combinatorics, geometry, and other scientific domains where visual discovery and optimal structure generation are key.

About the Speaker(s)

The research presented was a collaborative effort by Konrad Mundinger, Max Zimmer, Aldo Kiem, Christoph Spiegel, and Sebastian Pokutta. All five co-authors are affiliated with the IOL Research Lab in Berlin. Konrad Mundinger and Max Zimmer were specifically noted to be present at the ICML 2025 conference, allowing for direct engagement and discussion regarding their fascinating work on neural discovery in mathematics. Their collective expertise spans the intersection of machine learning and fundamental mathematical inquiry, aiming to push the boundaries of AI's role in scientific discovery.