Research map / Learning theory and algorithms / Combinatorial and search optimization
Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses neural networks trained on a probabilistic, differentiable relaxation of unit-distance coloring constraints to discover new colorings of the plane and related variants of the Hadwiger-Nelson problem.
Problem
The Hadwiger-Nelson problem (chromatic number of the plane) and its variants (almost colorings, off-diagonal distance colorings, higher dimensions, monochromatic triangles) require discovering colorings that avoid monochromatic distances, a mixed discrete-continuous problem with hard constraints.
Approach
Relax discrete color assignments into probability distributions over colors, define a differentiable loss penalizing expected monochromatic unit-distance pairs via Monte Carlo sampling, and approximate the coloring with a sine-activated MLP trained by gradient descent; then formalize discovered patterns into rigorous colorings.
Key results
- Two novel 6-colorings extend the known range of realizable distances for type (1,1,1,1,1,d) from [0.415, 0.447] to [0.354, 0.657].
- A formalized 5-coloring covers all but 3.7356% of the plane, improving the previous best of about 4.01%.
- A formalized 14-coloring of 3D space covers all but 3.4622% of R^3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use neural search and formalization for five-color almost coloring | Almost coloring method · Almost coloring the plane, 5 colors | fraction removed: 4.01% -> 3.74% | Helped |
| Use neural search and formalization for six-color almost coloring | Almost coloring method · Almost coloring the plane, 6 colors | fraction removed: 0.02% -> 0.04% | Hurt |
| Use neural search to extend the feasible free-distance range | Six-color coloring of type (1,1,1,1,1,d) · Off-diagonal coloring | valid distance range: [sqrt(2) - 1, 1/sqrt(5)] -> [0.354, 0.657] | Helped |
| Search five-color polychromatic distance configurations | Polychromatic coloring method · Five-color polychromatic coloring | conflict rate: 4.9% | Mixed |
| Use neural search for an exact 14-coloring rather than an almost coloring | Three-dimensional coloring method · R3, 14 colors | conflict-free coloring | Hurt |
| Apply the almost-coloring formalization pipeline in three dimensions | Three-dimensional coloring method · Almost coloring R3, 14 colors | fraction removed: 3.4622% | Helped |
| Use the neural framework to search triangle-avoidance colorings and formalize stripe-based patterns | Triangle-avoidance method · Plane triangles with side lengths 1, a, and b | number of colors sufficient | Helped |
| Search with neural networks for colorings using fewer than seven colors | Classical Hadwiger-Nelson problem · Plane, unit-distance coloring | number of colors found | Hurt |
Surprising findings
- The method could not find valid colorings with fewer than seven colors for the classical problem, numerically suggesting the chromatic number of the plane may be seven.
- Searches for a conflict-free five-color polychromatic coloring failed (minimum conflict rate about 4.9%), suggesting the polychromatic number may be six.
Limitations
- Numerical results are not formal proofs and require mathematical formalization.
- Neural networks introduce irregularities (wavy lines) reflecting freedom in the solution space, making patterns harder to formalize.
- Approach is heuristic and needs substantial hyperparameter tuning, with thousands of runs per variant.
Experimental setup
Benchmarks: Hadwiger-Nelson problem almost-coloring bounds off-diagonal coloring type (1,1,1,1,1,d) 3D chromatic number bounds monochromatic triangle avoidance regions
Metrics: fraction of conflicting points fraction of plane removed in almost coloring range of realizable distances d
Baselines: Pritikin almost-coloring construction Stechkin coloring FunSearch PatternBoost
Builds on: implicit neural representations physics-informed neural networks PatternBoost FunSearch
Closest papers by meaning
- Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics (ICML 2025 · similarity 0.87)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.84)
- Position: Algebra Unveils Deep Learning - An Invitation to Neuroalgebraic Geometry (ICML 2025 · similarity 0.83)
- Feature emergence via margin maximization: case studies in algebraic tasks (ICLR 2024 · similarity 0.83)
- Learning Interestingness in Automated Mathematical Theory Formation (NeurIPS 2025 · similarity 0.83)
- GNS: Solving Plane Geometry Problems by Neural-Symbolic Reasoning with Multi-Modal LLMs (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.