Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?
Authors: Konrad Mundinger
Max Zimmer
Aldo Kiem
Christoph Spiegel
Sebastian Pokutta
Venue: ICML 2025 oral (2025)
Keywords: AI4Science
Mathematical Discovery
Neural Network
Scientific Machine Learning
Neural Representation Learning
Discrete Geometry
Geometric Deep Learning
Neural Approximation
Primary area: applications->everything_else
TL;DR: We use neural networks to discover novel colorings of the plane avoiding certain distances.

Abstract: We demonstrate how neural networks can drive mathematical discovery through a case study of the Hadwiger-Nelson problem, a long-standing open problem at the intersection of discrete geometry and extremal combinatorics that is concerned with coloring the plane while avoiding monochromatic unit-distance pairs. Using neural networks as approximators, we reformulate this mixed discrete-continuous geometric coloring problem with hard constraints as an optimization task with a probabilistic, differentiable loss function. This enables gradient-based exploration of admissible configurations that most significantly led to the discovery of two novel six-colorings, providing the first improvement in thirty years to the off-diagonal variant of the original problem (Mundinger et al., 2024a). Here, we establish the underlying machine learning approach used to obtain these results and demonstrate its broader applicability through additional numerical insights.

Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?
Konrad Mundinger 12
Max Zimmer 12
Aldo Kiem 12 Christoph Spiegel Sebastian Pokutta 12
Abstract
We demonstrate how neural networks can drive mathematical discovery through case study of the Weesiner-Nelson problem, a long-standing open problem at the intersection of discrete ge- ometry and extremal combinatorics that is con- cerned with coloring the plane while avoiding monochromatic unit-distance pairs. Using neu- ral networks approximators, reformulate this mixed discrete-continuond geometric coloring problem with hard constraints as an optimization task with a probabilistic, differentiable loss func- tion. This enables gradient- based exploration of admissible configurations that most significantly led to the discovery of novel six-colorings, providing the first improvement in thirty years to the off-oiagonal variant of the original problem (Mundinger et al., 2024a). Here, we establish the underlying machine learning approach used to ob- tain these results and demonstrate its broader ap- plicability through additional numerical insights.
Figure Neural network output (left) that inspired our for- mal construction (right) of a novel six-coloring of the plane, Red points avoid all distances between 0.418 and 0.657 while other colors avoid unit distances. The neural network was trained through gradient descent on continuous and differentiable relaxation of these geometric constraints.
through numerical methods, yet many important theoreti- cal problems involve both discrete and continuous aspects. These mixed discrete contrtee-ooniuuous problems have remained particularly challenging for traditional approaches.
1. Introduction
The discovery of mathematical constructions is fundamental to theoretical mathematics, where proving the existence of objects with certain properties can advance our understand- ing of abstract structures. Traditional computational meth- ods have aided the search for such constructions through exhaustive searches, optimization, and heuristics, while cent advances in Machine Learning (MI.) offer new ways to explore mathematical structures and guide intuition. Purely discrete problems can be approached through discrete and combinatorial optimization and purely continuous problems
The Hadwiger-Nelson (HN) problem perfectly illustrates these challenges: determine the minimum number of col- needed to color the Euclidean plane that two points at unit distance share the same color. This number is often referred to as the chromatic number of the plane x(?)). Despite its simple statement, this problem combines discrete choices (color assignments), continuous geometry (the Euclidean plane), and hard constraints (unit-distance requirements)
way that has resisted resolution for over seventy years. While SAT solvers and discrete optimiza- tion techniques have contributed to finding lower bounds, discovering new colorings has remained challenging.
DDeparment for AI in Science, Society, and Technol- ogy, Zuse Institute Berlin, Germany "Institute of Mathemat- ies. Technische Universität Berlin, Germany. Correspondence to: Konrad Mundinger smundinger@zibbl @itnngerr@ibbde..... Christoph Spiegel <spiegel zib.de>.
We present a framework that reformulates this geometric coloring problem as a continuous optimization task by in- troducing probabilistic colorings and a differentiable loss function. This continuous formulation enables us to use
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Neural Discovery in Mathematics
neural networks (NNs) as universal function approxima- tors to explore the solution space computationally. The networks return numerical approximations of colorings that are equally capable of representing regular patterns or un- expected, irregular solutions (largely) without any strong built-in assumptions about symmetry or periodicity,
Related Literature. Recent years have seen growing in- terest in applying ML to mathematical diseovery, from auto- mated theorem proving to finding novel constructions. We focus on the latter, specifically on approaches that use ML to discover mathematical objects with desired properties. For a broader perspective, we refer to recent surveys by Wang et al. (2023a); Krenn et al. (2022); Williamson (2023).
Our method serves as tool for mathematical discovery, operating across a spectrum spanning from fully automated approaches to human-assisted pattern recognition and for- malization. Importantly, numerical results do not constitute formal proof' but rather provide guidance that must be for- malized. In practice, our approach often discovers clearly interpretable patterns and tessellations that generate insights and candidate constructions, which can be turned into for- mal results through careful mathematical analysis or, in select cases with sufficient freedom in the solution space, through more automated computational approaches.
Several approaches have emerged for using ML in combina- torial discovery. Most closely related to our work, Karalias & Loukas (2020) developed an unsupervised GNN-based framework that uses probabilistic relaxations and differ- entiable loss functions to solve graph optimization prob- lems. While they focus on purely discrete problems like maximum clique finding, we consider a problem with an inherent continuous structure. Fawzi al. (2022) solved a discrete optimization problem using a reinforcement learn- ing approach, from which they were able to derive a faster matrix multiplication algorithm. Similarly, Wagner (2021) studied the ability of a reinforcement-leaminng approach to construct discrete counterexamples to conjectures in ex- tremal combinatorics. Building on this framework, Rou- cairol & Cazenave (2022) studied conjectures in spectral graph theory. However, Parczyk al. (2023) found that this approach was largely outperformed by well-established local searches while studying the Ramsey multiplicity prob- lem. This finding was at least in part supported by the work of Mchrabian et al. (2024). Charton et al. (2024) combine both approaches and propose PatternBoost. which trains an NN on the output of a local search and which was also used by Bérezi & Wagner (2024). Taking a markedly differentt approach, propose FunSearch, which uses LLMs to guide greedy search through evolutionary optimization of generated code. Novikov et al. (2025) very recently improved upon this ap- proach through AlphaEvolvee Other notable approaches of applying ML to mathematical problems in general in- clude Alfarano et al. (2024) and Trinh et al. (2024).
Contributions. The main contribution of this work is description of a continuous optimization framework for ge- ometric coloring problems that uses NNs and probabilistic colorings, enabling muddient-based exploration of solution spaces without strong prior assumptions or discretization of the underlying space. This framework was essential in the discovery of several novel colorings that imply improve- ments for variants of the HN problem:
1. We obtained two 6-colorings of the plane for a variant of the original problem where five colors must avoid unit distances while the sixth color avoids a differ- ent specified distance. These colorings significantly expand the known range of realizable distances to [0.354, 0.657] from the previous best of [0.415, 0.4-7] due to Hoffmann & Soifer (1996) and Soifer (1994b).
et al. (2024)
2. We obtained 5-coloring covering all but 3.74% of the plane where each of the five colors must avoid unit distances, improving on the previous best known bound of around 4.01 % due to Parts (2020b). We also obtained 14-coloring covering all but 3.46% of three- dimensional space.
Our approach differs from the ones used in these results, since we use MI. primarily covery requiring further interpretation and formalization, similar to work of Davies et al. (2021) on knot invariants, which laid the foundation for Davies et al. (2024) to prove a formal statement with significant additional mathematical effort. This approach of using Artificial Intelligence (AI) to guide mathematical intuition, while still requiring rigorous proofs, represents a challenging but underserved direction in Al-assisted mathematics - one that demands expertise in both ML and pure mathematics.
tool for mathematical dis-
3. We extended the range of monochromatic triangles avoidable when coloring the plane with given number of colors, another well-known variant. The previous best bounds are due to Aichholzer & Perz (2019).
Formal descriptions of the colorings underlying the first re- sult were published separately by Mundinger et al. (2024a), while papers describing the remaining results are currently in preparation. In the present article, besides describing the underlying framework that enabled this mathematical discovery, we provide additional numerical insights and include negative results for other variants where the frame- work indicated no avenue for improvement.
The paradigm of approximating functions by NNs which take coordinates as input is known as implicit neural repre- sentations (Park et al., 2019; Mescheder et al., 2019; Chen & Zhang, 2019). Our approach adopts this strategy while intro-
2

---

Neural Discovery in Mathematics
ducing loss function that penalizes deviations from desired geometric properties. This connects our method to physics- informed neural networks (Raissi et al., 2019; Cuomo et al., 2022; Wang et al., 2023b), where NNs approximate solu- tions to differential equations through unsupervised residual minimization. Berzins et al. (2024) recently extended these ideas to geometric constraints.
Finally, our approach fits within the broader Al4Science paradigm, where ML is revolutionizing scientific discovery in domains such as protein structure prediction (Jumper et al., 2021) or the earth sciences (Pauls et al., 2024).
2. The Hadwiger-Nelson Problem
First posed in 1950, the HN problem has become one of the most famous open questions in combinatorial geometry and graph theory, with rich history of partial results and increasingly sophisticated approaches. For comprehensive treatment of the problem, see Soifer (2009).
Figure 2: The formalized almost 5-coloring obtained using the discretization procedure described in Algorithm I. is periodic and constant on small parallelograms as indicated by the magnified section. The red color represents the part that covers 3. 3.74% of IR² and that needs to be removed.
Lower bounds for X(R) are typically established by con- structing unit distance graphs graphs whose vertices can be embedded as points in the plane in such a way that edges only connect vertices whose embeddings tance apart. The Moser spindle establishes that at least four colors are needed (Moser& & Moser, 1961) and this bound remained the best known until the breakthrough proof of de Grey (2018) established that x 2 5. His construc- tion, originally involving a unit distance graph with 20,425 vertices, sparked intense and largely computational efforts, including through Polymath project, to simplify and re- duce this graph (Heule, 2018; Exoo & Ismailescu, 2020; Parts, 2020a; Polymath, 2021; Gwyn & Stavrianos, 2020).
unit dis-
Variant 1: Almost coloring the plane. A natural ques- tion concerns how much of the plane needs to be removed before the remainder can be colored with six colors without monochromatic unit-distance pairs. Pritikin (1998), with later refinement due to Parts (2020b), established that 99. 985% of the plane can be colored with six colors while maintaining this property. This result also effectively bounds the density of potential counterexample: any unit distance graph requiring seven colors would need to have order at least 6 6,993, see Lemma 1 by Pritikin (1998) for a proof. The construction uses intersecting pentagonal rods and our NN approach, when applied to the original HN problem with six colors, consistently recovered structures remarkably similar to these pentagonal constructions. Parts (2020b) also studied the same question for fewer than six colors and we likewise applied our approach this setting with a modification in the form of Lagrangian term. This resulted an improve- ment for the 5-color variant, where our construction, see Figure 2, successfully covers all but 3.7356% of the plane. This improves on the previous best value of 4.0060% due to Parts (2020b), who explicitly asked in his paper for new approaches to push the value below the mark of 4%. See Section 4.1 for further details.
Upper bounds on the other hand are commonly established through explicit colorings of the plane. There exists a large number of distinct seven-colorings that avoid monochro- matic pairs at unit distance, the first of which used tiling of congruent regular hexagons and was already discovered in 1950 according to Soifer (2009). This upper bound of (TR²) < 7 has remained unchanged since. While computa- tional methods have proven highly successful in establishing lower bounds, there have been surprisingly few systematic computational approaches to constructing new colorings. The only one we are aware of was the use SAT solvers to color coarsely discretized versions of specific metric spaces as part of the discussions during the Polymath project (Poly- math, 2021), highlighting the need for techniques that can explore the continuous solution space more directly.
Variant 2: Avoiding different distances. Another nat- ural generalization of the problem considers colorings where different colors avoid different distances. More precisely, we say that an k-coloring of the plane has col- oring type (d,,..., de) if color does not realize dis- tance d,. This defines a natural 'off-diagonal' variant of the original problem, where finding a coloring of type
Given the challenge of closing the gap between the lower and upper bounds of the original problem, several natural variants have been proposed. Solutions these variants can provide additional insight into the underlying structure and complexity of the original problem.
3

---

Neural Discovery in Mathematics
polychromatic number computationally but found no way to improve the upper bound, see also Section 4.2.
5
1
6
5
4
Variant 3: Coloring n-dimensional space. This variant extends the HN problem to higher dimensions, seeking to determine the chromatic number x(R") of n-dimensional space while maintaining the constraint that points at unit distance must receive different colors. A general lower bound of ((P)) 2 n-+2 2 was established by Raiskii (1970a). The three-dimensional case has received particular attention: Nechushtan (2002) proved x(=)) Z 6 using a graph on approximately 400 vertices, which de Grey (2020) later refined to a 59-vertex construction. Regarding upper bounds, Coulson (2002) famously showed x(R) S 15, bound that Soifer (2009) conjectures to be tight. Our approach successfully found colorings using 15 colors as well as, applying the techniques from the first variant, a 14-coloring covering all but 3.4622% of R², see also Section 4.3.
3
6
3
2
5
4
Figure 3: Formalized version of a neural network-generated 6-coloring of the plane where no red points appear at dis- tance 0.45 and no other color has monochromatic unit- distance pairs. The dotted circles have unit distance radius while the dashed circle have radius 0.45.
Variant Avoiding triangles. Finally, one can ask how many colors are needed to avoid monochromatic triples of points each at unit distances to each other. The answer in this case is actually quite simple: coloring the plane with alternating parallel and half-open stripes of width v3/2 us- ing two colors, taking care to include the correct parts of the border of each strip in the color, avoids any monochro- matic such triangle. One may again consider a natural off- diagonal version of this problem in which the triples form triangles with prescribed side lengths 1, a, and b for some 0 S a, b S satisfying a + b 1. Note that the (degen- erate) case a 0 and b = 1 corresponds to the original HN problem. A conjecture of Erdös, Graham, Montgomery, Rothschild, Spencer, and Straus (Graham, 2003) states that three colors should always be sufficient, though so far little progress has been made towards that conjecture with some cases, where b is close to 1, still requiring seven colors, see Aichholzer & Perz (2019). Currier al. (2024) recently also proved that any two-coloring contains three-term arith- metic progressions, which can be viewed as degenerate triangle with a = b- = 0.5. Using our approach, we were able to extend the previous best bounds in several regions, see Figure 4 and Section 4.4.
11,1,1,1,1,1) would establish x(R3) 6. Stechkin found coloring of type 1,,,,,,,,/1,1,, (Raiskii, 1970b) and Woodall (1973) constructed one of type (1, 1,1,,,,///311// chromatic number of the plane (R²) (Soifer, 1992a), that is the smallest number of colors & such that there exist some ,d. and coloring of type (di,.... dz). So far no better bounds than 4 S Xp I are known. Soifer (1992b) found the first six-coloring with non-unit dis- tance in only one color, having type
1/11.). Erdös asked for the poly-
Hoffman & Soifer (1993) later found colorings of type 1,,,,1,1,1, 1, 12-11 1). These constructions are part of a fam- ily that realizes (1, 1, 1, d) for any v2-1 < S 1/v5 (Hoffman & Soifer, 1996; Soifer, 1994b). This led Soifer (1994a) to pose the 'still open and extremely difficult' (Nash & Rassias, 2016) problem of determining the continuum of six colorings- that is the set of all d for which six-coloring of type (1, 1, 1, 1, 1, d) exists.
Using our approach we discovered two novel colorings of the plane that extend the continuum of six colorings, provid- ing the first improvement in thirty years. The first coloring parameterized by d and valid for type (1, 1, 1, d) as long as 0.354 < d I 0.553, see Figure 3. The second color- ing is constant and covers the range of 0.418 < dl < 0.657, see Figure and Figure 11. Together they significantly ex- pand the range of distances for which colorings are known to exist. A complete description of these constructions is given by Mundinger et al. (2024a). We also explored the
Many other variants of the HN problem exist, including generalizations to other metric spaces, colorings avoiding arbitrary unit-distance graphs, or colorings avoiding several distinct differences in each color. Our framework should be largely applicable to these variants with minimal modifi- cations, providing a systematic tool for exploring potential constructions.

---

Neural Discovery in Mathematics
previous
ours
[ R, RJa. While we are ultimately interested in this loss as R tends infinity, in practice we study it for some fixed (sufficiently large) value of R and aim to solve
3 colors
colors
colors
arg min CR(P). P
(3)
colors
A coloring of a finite box [-R, R. RJ² does not necessarily extend valid coloring of the entire plane R However, our objective is to find patterns within this box that can be extended across the plane.'
B
Clearly, any valid discrete coloring g of the plane can be converted to probabilistic coloring through one-hot- encoding, yielding (n = 0 for all R > 0. In the other direction, we have the following simple result.
Figure 4: Location of the vertex C of triangles ABC with side AB of length 1 for which a coloring avoiding monochromatic copies of such a triangle is known to exist for between three and six colors. The previously known results due to Aichholzer & Perz (2019) are shown on the left and the results including our improvements on the right. Note that Figure 7 in (Aichholzer & Perz, 2019) contained an error that significantly under-reported the size of the four- color region and that has been corrected here.
Proposition 3.1. If R > 0 and p is probabilistic color- ing with (R( = O, then the coloring given by g(r) = arg max (p(z)) satisfies Equation (1) for almost all pairs {(x,)) E RRR, R22 x R | - yl = 13.
Proof. Let X S II-R, R|2 denote the set of points for which the inner integral JaB, (w) p(x)² p(y)dy is non-zero
and for any given x E [-R, R]2 let ((x) S 8B (1) de- note the set of points y for which the support of ply) is not disjoint from p(z). i.e., the points y with p(z)" > O. By basic properties of the Lehesgue measure and since p(x)² p(y) in the definition of LR(g) is non-negative as dot product of probability vectors, X has measure zero in [-R, RJ² and so does Y(x) in 0Bi (x) for any E R X. It follows that {(x, y) x DE X,y E (z)) {(x,y) x E [-R, RJ² \ X, y E Y())). like- wise has measure zero with respect to the uniform distribu- tion over ((x, E [- R, R2|2 x g² || yll = 1}.
3. Methodology
In this section we develop the formulation of the HN prob- lem as a continuous optimization problem using probabilis- tie colorings. The original problem asks whether there exists
a function g: I22 + {L. {l.....c) c} such that
g(x) + (v)) Vx, y E 2R with || fir-ylly v112= =1
(1)
We relax the constraints by replacing the discrete color as- signment with a probabilistic one. Instead of assigning a fixed color to each point, we assign a probability distribution the colors, represented by a mapping p: R + A.: where A. is the c-dimensional probability simplex. The inner product p(x)) p(y) then naturally captures the prob- ability that points x and receive the same color when independently sampling from their respective distributions.
The minimization of Equation (2) over probabilistic color- ings therefore provides a path to finding colorings for the original HN problem through Proposition 3.1, assuming a suitably parameterized family of functions that ideally can approximate arbitrary colorings.
Given such a probabilistic coloring p, we define a loss func- tion measuring the violation of the unit distance constraint in [- R, R22 through
3.1. Parameterizing the space of probabilistic colorings
We approximate probabilistic colorings p through NNs po of fixed architecture and size with trainable parameters turning Equation (3) into the finite-dmmensional optimiza- tion problem arg ming Cx(Pe). By virtue of the universal approximation property (Cybenko, 1989) and their inherent spectral bias towards low-frequency functions (Rahaman et al., 2019). NNs provide both the expressiveness needed
CR(P)= = /
p(x)" p(y) dy(y)d dp(z), (2)
[- RJ (B)
where (B) {y E RR| ||z- y| = =r} denotes the cu- clidean sphere of radius r around and v 24 (OB, as well as = 11 (I-R, R, R2)²) are uniform distributions over 0B, (I) and R- RJ2, respectively. The inner integral rep- resents the probability of a conflict between a fixed point x and a randomly sampled point y at unit distance from it, while the outer integral averages this over all points in
"Instead of sampling uniformly from finite box, one could sample from Gaussian distribution with variance corresponding roughly the box size R. In limited tests, this alternative did not yield significantly different or improved constructions.
5

---

Neural Discovery in Mathematics
capture complex spatial patterns and a natural tendency towards structured, interpretable solutions.
off between using the additional color and maintaining valid colorings.
We employ a standard multilayer perceptron which encodes geometric structure by operating on coordinates, making this a geometric learning approach despite its simple archi- tecture. Following best practices for implicit neural repre- sentations (Sitzmann et al., 2020), we implement pe with sine activation functions. The networks we used consisted of two to four hidden linear layers with 32 to 256 neurons each, directly mapping coordinates to color distributions through a softmax activation after the final layer.
Almost colorings contain some inherent freedom in the the solution space, as we can simply increase the size of the ad- ditional color by a small amount needed, so we designed fully automated pipeline to obtain rigorously verified col- orings. After identifying periodic structures in an initial trained NN in the form of tesselation using a parallelo- gram, retrain separate NN to enforce precisely that periodicity. We then discretize the output and eliminate any unit-distance conflicts through an iterative discrete heuris- tic. The periodic extension of this discrete solution yields a continuous almost coloring that provably satisfies all unit- distance constraints, see also Algorithm and Figure 2.
3.2. Batched gradient descent
To minimize the loss function, we employ gradient descent on the NN parameters 0. The main challenge lies in approx- imating (pon which involves nested integrals that we approximate through Monte Carlo sampling. Specifically, we sample n center points x; ~ U (I-R, R, R)22) and, for each center 24, sample m points Vij ~ U (0Br (zz)), obtaining the estimate
Algorithm Automated almost-coloring formalization
1. Initial training. Train pe R - Ae+1 to minimize Equation (5) on a large enough box |- RR R|
Periodicity extraction. Determine two vectors vi, U2 E I² with 0 < 2(v1, U2) < such that the coloring (largely) consists of tiling the parallelogram
po (2;)² po po(Wis)
voCn(po) 2 Vo
(4)
P = {arm + Bu2 a, B E [0, 1)
3.3. Considerations for each of the four variants
along the lattice A { [1 + n222 n1, 11,722 E Z}.
Let us outline how the formulation in Equation (2) can be adapted to the four variants described in Section 2, including necessary adjustments to the NN and sampling procedures already described.
3. Periodicity ible change- -ffage--o--bastte basis matrix M = [0] 0/2 E R2x Prepend the mapping x + M-1x (mod 1) to pa. which enforces exact periodicity over A, and retrain.
retraining. Form the invert-
Variant 1: Almost coloring the plane. To formalize the idea of an almost coloring, we introduce an additional color, in which no conflicts are penalized. We extend the co- domain of py Act1, with the last entry corresponding to the additional color. Formally, we then want to solve the constrained optimization problem
4. Discrete almost-coloring. Discretize P into kl copies of {am/ + :02/1: a E [o. 1)) and determine a color for each parallelogram pixel by sampling pa at its respective center.
5. Iteratively fix remaining conflicts. Determine a dis- crete mask in which conflicts need to be avoided around each parallclogram pixel to obtain a formal coloring. Iteratively reduce any remaining conflicts by solving an auxiliary minimum edge cover problem and recol- oring some parallelograms. After fixed number of rounds, resolve any remaining conflicts by recoloring with the additional color c 1.
arg min CR(Pg) Pe
S.t.
pa(x))+1 dp(x)= S
for some pre-determined 8 >>00 0, where p refers to the first e components of pa- More precisely, we want to determine the minimum 8 for which the answer to this problem zero In practice, solve the Lagrangian relaxation
Variant 2: Avoiding different distances. For colorings
/ [R
(i(p = Cn(p)) +
((0)+t1d((a)
(5)
of type (di,..., de) we modify the loss formulation to
While in theory there exists a corresponding X for each 8, we simply treat À as hyperparameter controlling the trade-
po(x); (o(x))Po()))) du(()) (6)
R.R (Ba,(w)
6

---

Neural Discovery in Mathematics
with μr - - ([-R, R(2) and uk u (Ba, (z)), i.e. we now need to choose the points y from the sphere a (ar of radius dy around for each color k. Minimizing the loss function finds probabilistic colorings that attempt to avoid distance dg for color k. Note that we recover Equation (2) for d1 =... de 1.
Figure 5: The almost coloring due to Pritikin (1998) and Parts (2020b) (left) and the coloring suggest by our approach (right). The wavy lines are caused by the inherent degrees of freedom present in many colorings.
This model can also be extended to handle sets or ranges of distances for some or all colors. To achieve this, we redefine the domain of the candidate functions g include the current distance. Given distance ranges [dgiin daax for each color k for example, we set
p: R X X
d dx + D.
min m
(7)
4. Experimental results
In this section present our numerical results for the orig- inal HN problem and its four variants. We implemented our approach in PyTorch, updating the parameters using the Adam optimizer (Kingma & Ba, 2015) with a learning rate schedule linearly decaying (Li et al., 2020) from an initial value between 10-3 and 10-4 We typically used between 16,384 and 65,536 training steps, sampling 1,024 to 4,096 points for x and 1 to 32 points for y on the circle(s) around during each step, resulting in 10 to 10 total samples during training. A single such run takes between two and 20 minutes on an NVIDIA V100 GPU, though adequate results can be achieved in under 10 minutes on a standard laptop CPU, Due to the heuristic nature of our approach and the need to tune hyperparameters, we did however per- form thousands of runs for each variant, particularly when exploring parameter spaces in the off-diagonal and triangle variants.
By integrating Equation (6) over this expanded domain, we average the loss across all distances within the speci- fied range for each color by sampling points on circles, corresponding do the distances dl, di....,de de. Note that this increases the effective batch size from to n c. This approach allows exploration of a larger part of the solution space instead of just a single type.
Variant Coloring n-dimensional space. To extend to higher dimensions, it suffices to integrate over IR"" and letting ²B (1r) represent the sphere in the appropriate space. We are particularly interested in the three-dimensional case. Apart from adapting the input dimension of go as well as sampling in the higher dimensional space, this case is anal- ogous to the two dimensional cases. The question of al- most colorings arises naturally in higher dimensions as well. Here, the automated verification procedure described in Algorithm 1 is particularly useful, visualization and inter- pretation of colorings gets much more challenging in higher dimensions.
Our initial experiments focused on six-color solutions in the classical setting. The method consistently recovered pat- terns resembling Pritikin's 's construction, providing early val- idation of our approach, see Figure 5. However, these results also revealed that NNs often introduce irregularities such as wavy lines, reflecting inherent freedoms in the solution space. This becomes even more pronounced for seven col- ors, see Figure 9 in the appendix. These findings highlight that our method can successfully discover valid colorings, but formalizing the discovered patterns into rigorous mathe- matical constructions may still require substantial additional effort. Additionally, the method's inability suggest valid colorings with fewer than seven colors provides additional numerical evidence that the chromatic number of the plane may in fact be seven. The code needed to reproduce our results and the constructions obtained using Algorithm I are available at iem125.
Variant 4: Avoiding triangles. In order to avoid monochromatic triangles with side lengths 1, a, and 6, we replace the integrand po (x)) po(y)s in Equation (2) with
Σ Po(x)) Po(v)a (po(z))u + po(2))))/2
(8)
where 21 and 22 are the two candidates for the the point 2 such that 2, y. and form a triangle with || - y/l = 1,
||æ - =|| = a and lyy - =|| = b, assuming a + >>> 1.
In this variant we sample center points x E R-,, Rtj2 and proximity points y on the unit circle as before. We then obtain the two candidates zι and 22 for the third point of the triangle by calculating the intersection points of the circles of radius and b around x and y, respectively. As in Variant 2, the domain of the function can be extended to 2 x [Amin m X [bmin- b to allow for continuous ranges of a and b within one network and we integrate the loss over the intervals [Omin, m and (Dminy D
4.1. Variant 1: Almost coloring the plane
Applying the Lagrangian- modified loss function described in Section 3.3 to six colors, we achieved conflict rates
7

---

Neural Discovery in Mathematics
Table I: We compare our results with the best known for almost coloring the plane, reporting the fraction of points that must be removed to color the remainder without unit- distance conflicts. Prior results are due Croft (1967) and Parts (2020b). Numerical values were obtained by evalu- ating trained model a parallelogram with periodical boundary conditions. The formalized values were obtained by applying Algorithm I.
Minimum fraction of conflicts over various runs
0.05
Fraction of conflies
0.04
0.03
0.02
colors
5
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
prior
77.04%
54.13%
31.20%
8.25%
4.01%
0.02%
Last colour distance
numerics
77.07%
54.21%
31.34%
8.29%
3.60%
0.03%
formalized
77.13%
54.29%
31,51%
8.52%
3.74%
0.04%
Figure Fraction of conflicting points versus the free dis- tance in colorings of type (1, 1, 1,
1, d). The thick blue line shows the minimum over multiple runs (thin lines). Or- ange and blue shaded regions indicate the previously known and our extended ranges of valid colorings, respectively.
of around 0.03% slightly higher than those reported by Parts (2020b). The optimization process proved sensitive to the Lagrangian term X, but consistently recovered known constructions once good range (typically between 10-3 and 1 was found. The discovered patterns for one to four colors closely match known constructions due to Croft (1967), see Figure 10 in the appendix. The five-color case exhibits patterns similar to those in the construction de- scribed by Parts (2020b), but the numerical value of around 3.60% suggested the possibility of an improvement. The formalized construction does in fact attain significantly improved value of 3.7356%. Complete numerical results for k L,..., 6 colors along with the formalized values obtained using Algorithm are reported in Table 1.
we found three regions of minimal conflicts: two symmetric regions near (di, 1) and (1, with di, d2 0.5, recover- ing our earlier (1, 1, 1, d) colorings, and an additional region near (0.5, 0.5) corresponding to construction simi- lar to Stechkin's 's see Figure 12.
Minimum conflict fractions
1.2
10
0.8
10-3
4.2. Variant 2: Avoiding different distances
0.6
We report the numerical results colorings of type (di...., ds) with a particular focus on the cases d; = 1 for either i 51 or i 4].
10-4
0.2
Following Section 3, we included the free distance d in the domain of the color- ing function, exploring the interval [0.2, 2.2]. This approach only allows optimization over continuous range of distances but also reveals smooth transitions between color- ings, see Figure 12 in the appendix, which proved crucial in identifying broader family of valid solutions. Figure 6 shows the conflict rates as a function of d for sixteen indi- vidual runs and their pointwise minimum. While previous work established valid colorings for d E [v2 1, 1/V5) (orange dashed lines), our constructions extend this range to (0.354, 0.657] (blue dashed lines). Additional regions of interest appear at se 1, corresponding the original HN problem and d = 1.6, where conflict rates fall below 1%.
Colorings of type 1,
Figure The fraction of conflicts in (1,1, d1, d2) col- orings function of di and d2 (center, showing minimum over sixteen networks). Three regions of minimal confficts emerge: symmetric regions near (d,, 1) and (1, d2) with d1, d2 = 0.5, and one near (0.5, 0.5). Sample colorings from these regions are shown in the surrounding plots.
Polychromatic Number. We investigated potential five- color solutions of type (d1,...,dd, d.), by including the dis- tances in the domain of the NN and determining the best candidates for such a type after training using first- and second-order methods. Our result achieved a minimal con- flict rate of 4.9% with distances d1 1, d2 z ds 1, and d4 R ds 0.56, see Figure 13 in the appendix. Despite extensive optimization. our inability to find a conflict-fres five-color solution provides additional evidence that the polychromatic number may indeed be six. More details are provided in Appendix C.
(,d1,,d) d2). Analogously, we treated the last two colors as free distances and augmented the domain of the NNs accordingly. The resulting colorings remain continuous in both d, and d2. As shown in Figure 7,
Colorings of type
8

---

Neural Discovery in Mathematics
4.3. Variant 3: Coloring n-dimensional space
Our method successfully found (near) conflict-free 15-color solutions, consistent with the bound established by Coulson (2002). Our attempt to improve this bound directly 14 was not successful. We also studied the almost coloring variant in three dimensions, which resulted in numerical solutions with a conflict rate of around 2.3%. Applying a three-dimensional modification of Algorithm 1 yielded a formal coloring covering all but 3.4622% of IR3,, though fur- ther refinements improving this value seem possible. More details are provided in Appendix D.
D3 colors
D 4 colors
5 colors
0 6 colors
4.4. Variant 4: Avoiding triangles
Figure 8: Numerical results showing the achievable color bounds when avoiding monochromatic triangles, together with a selection of found colorings. We trained thousands of networks on different sub-areas of the above region and say that a point can be achieved with three, four, five, six colors if the top 3% of runs for that point reported that less than 0.1% % of sampled triangles were monochromatic in the argmax coloring derived from the trained NNs.
We applied our approach to study triangles with sides of length 1, a, and b satisfying a + b 1. For four and five colors, our NNs consistently discovered constructions based on stripes and hexagonal tessellations, similar to those used by Aichholzer & Perz (2019). However, the numerical results suggested that alternative scalings of these basic patterns could yield improvements beyond those previously known, see the suggested patterns in Figure 8. We were able to formalize some of those based stripes, obtaining several new bounds that expand the regions where three to five colors suffice, as already shown previously in Figure 4. This significantly reduces the area of the parameter space still requiring seven colors, though further improvements seem possible.
framework could also potentially be extended to handle non-differentiable losses using auxiliary 'critic' or 'value" networks that learn to approximate these losses, similar to techniques used in adversarial and reinforcement learning.
We also experimented with other function families such as Fourier bases and Voronoi diagrams; however, NNs consis- tently performed best, due to their expressiveness, ease of training, and ability to represent complex functions with rel- atively few parameters. The approach required substantial amount of tuning, particularly in the choice of architecture and hyperparameters. Beyond the usually relevant parame- ters such the learning rate, the Lagrangian penalty term was particularly important: although calleseenittive, it led to stable and consistent results once a good range was found. The size of the bounding box was less critical, as long as it was large enough to avoid trivial colorings.
Beyond further resolving the parameter space with respect to the number of required colors both numerically (Figure 8) as well as via formalized patterns (Figure 4), the numeri- cal results also provide evidence against the conjecture of Graham (2003) that three colors should always suffice: our experiments consistently required more colors as one side of the triangle became shorter while the other became closer to unit length, suggesting these cases (which more closely resemble the original HN problem) may be fundamentally more challenging.
5. Discussion
We believe that the combination of Al-aided constructions with human insight is highly beneficial, leveraging the strengths of automated exploration alongside human inter- pretation and mathematical intuition. We also emphasize that, in the case of the almost colorings, we developed a fully automated pipeline that no longer requires human in- tervention. This automation was already helpful in two di- mensions, but became essential for dimensioalll vari- ants of the problem, where manual interpretation becomes increasingly challenging. More broadly, this work demon- strates how continuous relaxations and gradient- based opti- mization can bridge the gap between ML and mathematical discovery, potentially opening new paths to approaching long-standing open problems mathematics.
Our framework provides novel approach to exploring math- ematical structures through continuous optimization, lead- ing several concrete improvements to long-standing open problems. Beyond just being applicable to variants of the HN problem, we believe that it naturally extends to other problems in discrete geometry and extremal combinatorics. For instance, graph-theoretic problems involving discrete structures can often be reformulated through graph limits, where the objective becomes optimizing over continuous maps [0, 1j2 + [0, 1]. Our approach of using NNs as uni- versal function approximators combined with suitable loss functions could be directly applied in this setting. The

---

Neural Discovery in Mathematics
Acknowledgements
sets on hypercubes via generative AI. arXiv preprint 2rX1v:241.117734, 2024.
Research reported in this paper was partially supported through the A14Forest project, which is funded by the Ger- man Federal Ministry of Education and Research (BMBF; grant number 01IS23025A) and the Deutsche Forschungs- gemeinschaft (DFG) through the DFG Cluster of Excel- Ience MATH+ (grant number EXC-2046/1, project ID 390685689) as well as Sonderforschungsbbrecch (SFB) Transregio 154 (grant number 239904186). C.S. would also like thank Marijn Heule for his FoCM 2024 talk on HN that inspired this research project and Sagdeev Arsenii for suggesting the triangle variant of this problem. The authors would also like to thank Tibor Szabó for suggesting sam- pling from a Gaussian distribution instead of from finite box as well as the referees for many valuable suggestions.
Berzins, A., Radler, A., Sanokowski, S., Hochreiter, S., and
Brandstetter, J. Geometry-informed neural networks. In ICML 2024 Workshop on grouundd Represen- tation Learning and Generative Modeling, 2024.
Charton, F., Ellenberg, J. S., Wagner, Z., and Williamson, G. PatternBoost: Constructions in mathematics with a little help from AI. arXiv preprint 2rXiv:2411.00555 2024.
Chen, Z. and Zhang, H. Learning implicit fields for gener- ative shape modeling. pp. 5932-5941, June 2019, doi: 10. ww.1109/CVR.2219.00006
Coulson, D. A 15-colouring of 3-space omitting distance one. Discrete mathematics, 256(1-2):33-90, 2002.
Impact Statement
Croft, H. T. Incidence incidents. Eureka (Cambridge), (30): 22-26, 1967.
This work demonstrates how ML can drive scientific and mathematical discovery, using NNs explore solutions to the HN problem and related combinatorial geometry chal- lenges. Our approach bridges discrete and continuous math- ematical domains, enabling researchers to explore prob- lem spaces more broadly and deeply than traditional meth- ods allow. By reformulating complex mathematical prob- lems as optimization tasks, we provide tools for intuition- driven discovery that retain interpretability while accelerat- ing progress. While the immediate focus is on theoretical mathematics, the broader applicability of ML methods sim- ilar to our approach has the potential to transform diverse fields that require navigating hybrid discrete-contee continuous solution spaces, such as materials science, network opti- mization, and beyond. The socictal impact of this paradigm shift could significantly enhance ability address long- standing scientific and engineering problems.
Cuomo, S., Di Cola, V. S., Giampaolo, F., Rozza, G., Raissi, M., and Piccialli, F. Scientific machine learning through physics-informen informed neural networks: Where we are and what's next. Journal of Scientific Computing, 92(3):88, 2022.
Currier, G., Moore, K., and Yip. C. H. Any two-coloring of the plane contains monochromatic 3-term arithmetic progressions. Combinatorica, 44(6):1367-1380, Decem- ber 2024. ISSN 1439-6912. doi: 10. 10.10077/00493--024 00122-2.
Cybenko, G. Approximation by superpositions of a sig- moidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Davies, A., Veličković, P., Buesing, L., Blackwell, S., Zheng, D.. Tomašev, N., Tanburn, R., Battaglia, P., Blun- dell, C., Juhász, A., et al. Advancing mathematics by guiding human intuition with AI. Nature, 600(7887): 70-74, 2021.
References
Aichholzer, O. and Perz, D. Triangles in the colored eu- clidean plane. In 35th European Workshop on Computa- tional Geometry (EuroCG 2019), 2019.
Davies, A., Juhász, A., Lackenby, M., and Tomašev, N. The signature and cusp geometry of hyperbolic knots.
Alfarano, A., Charton, F., and Hayat, A. Global Yyарunov functions: a long-standing open problem in mathemat- ics, with symbolic transformers. Advances in Neural Information Processing Systems, 17:96643-93670, 2024.
Geometry & Topology, 28(5):2313-244) 2024.
de Grey, A. D. The chromatic number of the plane is at least 5. Geombinatorics Quarterly, XXVII(():18-31, 2018.
Barthe, F., Guédon, O., Mendelson, S., and Naor, A. A probabilistic approach to the geometry of the Ipn- ball. The Annals of Probability, 33(2):88--133 March 2005. ISSN 0091-1798, 2168-894X. 0091 I 1904000000874.
de Grey, A. D. J. A small 6-chromatic unit-distance graph in R3, Geombinatorics Quarterly, XXX(I):--13, 2020.
doi: 10.1214/
Exoo, G. and Ismailescu, D. The chromatic number of the
plane is at least a new proof. Discrete & Computational Geometry, 64(1):216-22) 2020.
Bérezi, G. and Wagner, A. Z. A note on small percolating
10

---

Neural Discovery in Mathematics
Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera- Paredes, B., Barekatain, M., Novikov, A., R Ruiz, F. J., Schrittwieser, J., Swirszcz, G., et al. Discovering faster matrix multiplication algorithms with reinforce- ment learning. Nature, 61047930):47-53, 2022.
Li, M., Yumer, E., and Ramanan, D. Budgeted training: Rethinking deep neural network training under resource constraints. In International Conference Learning Representations (ICLR), 2020.
Lu, L., Jin, P., Pang, G., Zhang, Z., and Karniadakis, G. E. Learning nonlinear operators via deeponet based on the universal approximation theorem of operators. Nature Machine Intelligence, 3(3):218-22) March 2021. ISSN 2522-5839. doi: 10. 0000008//42255--0--0000200222000
Graham, R. Problem 58:
Monochromatic trian- gles. The Open Problems Project (TOPP), 2003. Available at http::/ //cs smith. edu/-orourke// TOPP TOPP/P58.. htm.htmlle..... #ttmlerrobeem 58.
Mehrabian, A., Anand, A., Kim, H., Sonnerat, N., Balog, M., Comanici, G., Berariu, T., Lee, A., Ruoss, A., Bu- lanova, A., et al. Finding increasingly large extremal graphs with alphazero and tabu search. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pp. 6985-6993, 2024.
Gwyn, H. and Stavrianos, A finite graph approach to the probabilistic hadwiger-nelson nelson problem. arXiv preprint wwXiv:2008.079877 2020.
Heule, M. J. Computing small unit-distance graphs with chromatic number 5. Geombinatorics Quarterly, XXVIII (1):32-50, 2018.
Mescheder, L.,, Oechsle, M., Niemeyer, M., Nowozin, S., and Geiger, A. Occupancy networks: Learning 3d recon- struction in function space. In 2019 IEEE/CVF Con- ference Computer Vision and Pattern Recognition (CVPR). pp.
Hoffman, I. and Soifer, A. Almost chromatic number of the plane. Geombinatorics, 3(2):38-4)) 1993.
June 2019. doi: 10. 10.1109/C 2019 1099.0059, URL https: htt//eeeeeplrreee/ iew.ooreeeeee..ee.ee.e.ee.eee.e. ieee. org http//dccunnt//// /aaaumnnn/895555 88553555.
Hoffman, L. and Soifer, A. Another six-coloring of the plane. Discrete Mathematics, 150(1-3):427-44 1996.
Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Zidek, A., Potapenko, A., Bridgland, A., Meyer, C., Kohl, S. A. A., Ballard, A. J., Cowie, A., Romera-Paredes, B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen, S., Reiman, D., Clancy, E., Zielinski, M., Steinegger, M., Pacholska, M., Berghammer, T., Bodenstein, S., Silver, D., Vinyals, O., Senior, A. W., Kavukcuoglu, K., Kohli, P., and Hassabis, D. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-588, August 2021. ISSN 1476-4687. doi: 10.1038/s41586- 021-03819-2.
Moser, L. and Moser, W. Solution to problem 10, Canad Math. Bull, 4:187-189, 1961.
Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. Ex- tending the continuum of six-colorings. Geombinatorics Quarterly, 2024a.
Mundinger, K., Zimmer, M., and Pokutta, S. Neural param- eter regression for explicit representations of pde solution operators, 2024b.
Nash, J. F. and Rassias, M. T. Open problems in mathemat- ics. Springer, 2016.
Nechushtan, O. On the space chromatic number. Discrete
Karalias, N. and Loukas, A. Erdōs goes neural: an unsuper- vised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33:6659-6672, 2020.
mathematics, 256(1-2):499-007 2002.
Novikov, A., Vū, N., Eisenberger, M., Dupont, E., Huang, P.-S., Wagner, A. Z., Shirobokov, S., Kozlovskii, B., Ruiz, F. J. R., Mehrabian, A., Kumar, M. P., See, A., Chaudhuri, S., Holland, G., Davies, A., Nowozin, S., Kohli, P., and Balog, M. Alphaevolve: A coding agent for scientific and algorithmic discovery. White paper, May 2025. URL https: /ttttpp:///eepmiddd..ooooo. d a powereds cod soweerdddccoodnng-aggae------o-o advanced- httpe//ddlggoriiaaaaaaaaaaaaaare Accessed 2025-05-28.
Kingma, D. P. and Ba. J. Adam: A method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015.
Kovachki, N. B., Lanthaler, S., and Stuart, A. M. Oper- ator learning: Algorithms and analysis. Handbook of Numerical Analysis, 25:419 2024.
Krenn, M., Pollice, R., Guo, S. Y., Aldeghi, M., Cervera- Lierta, A., Friederich, P., dos Passos Gomes, G., Häse, F, Jinich, A., Nigam, A., et al. On scientific understanding with artificial intelligence. Nature Reviews Physics. 4 (12):761-769, 2022.
Parezyk, O., Pokutta, S., Spiegel, C., and Szabó, T. Fully cossuter-assisted proofs in extremal combinatorics. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 37, pp. 12482 12490, 2023.

---

Neural Discovery in Mathematics
Park, J., Florence, P., Straub, J., Newcombe, R., and Love- grove, S. Deepsdf: Learning continuous signed distance functions for shape representation. In 2019 IEEE/CVF Conference on Computer Vision and Pattem Recognition (CVPR), pp. 165-174, June 2019. doi: 10. 10.1 109/CVR.. 2019.00025. URL attps://ieeexplorss ieee. org/ htr//documett/BB0 / 8954065.
International Computing and Combinatories Conference, pp. 162-176. Springer, 2022.
Sitzmann, V., Martel, J., Bergman, A., Lindell, D., and Wetzstein, G. Implicit neural representations with peri- odic activation functions. Advances in neural information processing systems, 33:7462-7443, 2020.
Soifer, A. Relatives chromatic number of the plane I. Geombinatorics, 1(4):13-17, 1992a.
Parts, J. Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane. arXiv preprint arXiv:2010. /2665, 2020a.
Soifer, A. A six-coloring of the plane. Journal of Combina- torial Theory, Series A, 61(2):292-294, 1992b.
Parts, J. What percent of the plane be properly 5-and 6-colored? arXiv preprint arXiv:2010.1200 2020b.
Soifer, A. Six-realizable X6. Geombinatorics, III(4): 140-145, 1994a.
Pauls, J., Zimmer, M., Kelly, U. M., Schwartz, M., Saatchi, S., Ciais, P., Pokutta, S., Brandt, M., and Gieseke, F. Estimating Canopy Height at Scale. Proceedings of ICML. 5 2024.
Soifer, A. An infinite class of six-colorings of the plane.
Congressus Numerantium, pp. 83 83-86, 1994b.
Soifer, A. The mathematical coloring book: Mathematics of coloring and the colorful life of its creators. Springer, 2009.
Polymath, On the chromatic number of circular disks and infinite strips in the plane. Geombinatorics Quarterly, XXX(4):190 201, 2021.
Trinh, T. H., Wu, Y., Le, Q. V., He, H., and Luong, T. Solv- ing olympiad geometry without human demonstrations. Nature, 625(7995))476-482 2024.
Pritikin, D. All unit-distance graphs of order 6197 are 6- colorable, Journal of Combinatorial Theury, Series B, 73 (2):159-163, 1998.
Wagner, A. Z. Constructions in combinatories via neural networks. arXiv preprint vrXiv:2104.14555 2021.
Rahaman, N., Baratin, A., Arpit, D., Draxler, F. Lin, M., Hamprecht, F., Bengio, Y., and Courville, A. On the spec- tral bias of neural networks. In International conference on machine learning. pp. 5301-5310, PMLR, 2019.
Wang. H., Fu, T., Du, Y., Gao, W., Huang, K., Liu, Z.,
Chandak, P., Liu, S., Van Katwyk, P., Deac, A., al.
Scientific discovery in the age of artificial intelligence. Nature, 620(7972):47-60, 2023a.
Raiskii, D. E. Realization of all distances in a decomposition of the space rn into n+1 I parts. Mathematical notes of the Academy of Sciences of the USSR, 7(3):14--96, 1970a. doi: 10. 10.1007/BF00099111. URLhttps:/ /rgg
Wang. S., Wang. H., and Perdikaris, Learning the solution operator of parametric partial differential equations with physics-informed deeponets. Science Advances, 7(40): eabi8605, September 2021. doi: 10.11166sciadv..ab888
10. 1 007 00000///F/00311...
Raiskii, D. E. Realization all distances decomposition of the space R" into n parts. Mathematical notes of the Academy of Sciences of the USSR, 7:194 7:194-196, 1970b.
Wang. S., Sankaran, S., Wang, H., and Perdikaris, P. An ex- pert's guide to training physics-informed neural networks. CoRR, 2023b.
Raissi, M., Perdikaris, P., and Karniadakis, G. E. Physics- informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physies, 378:686-707, February 2019, ISSN 0021-9991. doi: 10. 10.1006//.jcpp220 10....0..5
Williamson, G. deep learning a useful tool for the pure mathematician? arXiv preprint arXiv:2304. /2602, 2023.
Woodall, D. R. Distances realized by sets covering the plane. Journal of Combinatorial Theory, Series A, 14(2): 187-200, 1973.
Pareere, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J., Ellenberg, S., Wang, P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468-477) 2024.
Roucairol, M. and Cazenave, T. Refutation of spectral graph theory conjectures with Monte Carlo search. In
12

---

Neural Discovery in Mathematics
A. Coloring the plane with seven colors
Figure Colorings found for the Hadwiger-Nelson problem with seven colors. Left and middle: Rather structured colorings.
Right: Less structured coloring.
13

---

Neural Discovery in Mathematics
B. Details on variant 1: Almost coloring the plane
ka) =1
(b) k:
ke)
(d) k ==4 4
(c) k =
(f) k 6
Figure 10: Almost colorings for k = 1,..., 6 obtained through Algorithm 1. The parallelograms indicate the fundamental domain along which periodicity is enforced.
In the case of almost colorings, we designed a fully automated pipeline to generate rigorously verified colorings which tessellate the plane using parallelograms and are piecewise constant on smaller parallelograms, as outlined in Algorithm I. To infer the directions of periodicity, we evaluate the trained models from step along radial lines from the origin and translate these lines by increasing offsets. direction is categorized as direction of periodicity if the similarity between the original and translated evaluations exceeds threshold after distance d. From all such directions, we then extract two vectors that have minimal norm and sufficiently separated in angle. These vectors span the fundamental parallelogram which tiles the plane.
We then retrain a new model enforcing periodicity on this parallelogram and subdivide it into smaller aab-parallelograms (which we refer to as 'cells") and treat the coloring as constant within each one. For each cell Chase- we determine all the cells which contain points that are at unit distance to any point in Caase by computing the cells that intersect with unit circles the corners of Cuase- We then turn the unit distance constraint into the stricter (but discrete) constraint of not having cells with the same color they contain unit distance pairs.
Finally, in step 5, we employ heuristic completely eliminate unit distance conflicts while minimizing the use of the "bonus" color. While one could trivially assign the "bonus" color to all conflicting cells, we instead construct an auxiliary conflict graph whose nodes are conflicting cells and whose edges connect same colored cells at approximate unit distance. By computing a minimum edge cover and setting the selected cells to the "bonus" color, we effectively resolve all remaining conflicts.
14

---

Neural Discovery in Mathematics
C. Details on variant 2: Avoiding different distances
2
6
5
Figure 11: A 6-coloring of the plane where red points appear any distance between 0.418 and 0.657 while other color has monochromatic unit-distance pairs. The dotted circles have unit distance radius, while the dashed circles have radius 0.637 and the dash-dotted circles have radius 0.418. Shown is the formalized version, which was inspired by the NN outputs, see also Figure 1.
Figure 12: A more detailed view of the colorings generated by a single model for different values the last distance. Upper row (from left to right): 0.4, 0.6, 0.8, d 1.0. Lower row (from left to right): 1.2, 1.4, 1.6, d 1.8.
The polychromatic number the plane the minimum number of colors needed such that no color realizes all distances its monochromatic pairs. While known to at most 6, finding five-color solution would constitute a significant improvement. Our search focused on colorings of type (dj.... ds), where we dj 1 without loss of generality. Our approach sampled distances from [0.2, 2.2] and included them directly in the domain of the NN. Rather than performing an expensive grid search over the four remaining distances, after training. This optimization led to our best result with distances d1 = 1, d2 d3 s 1 and d4 R ds R 0.56, achieving minimal conflict rate of approximately 5% (see Figure 13). This suggests that the polychromatic number of the plane may indeed be six.
employed first- and second-order optimization methods to find optimal values
Note that when including the distances in the domain of the function of the coloring, we conceptually parametrize a whole
15

---

Neural Discovery in Mathematics
3
3
2
2
I
1
1
0
0
-1
-3
-3
33
-2
Figure 13: The best five-coloring with dj = 1, d2 ~ dg 2 and d4 Rs ds Ri 0.56 and approximately 5% of conflicts in box size 3|2.
family of implicit neural representations. Instead of viewing this as a function of both coordinates and distances in Equation (7), we can view it as function-valued function (i.e., operator):
mnn
{glg: Ae).
(9)
k=1
This perspective connects to the rapidly growing field of operator learning (Kovachki et al., 2024). DeepONets (Lu et al., 2021) are particularly suitable architectures for such mappings, and have proven effective in the numerical treatment of differential equations (Wang et al., 2021; Mundinger et al., 2024b).
16

---

Neural Discovery in Mathematics
-3
-3
-1
2
3
2
0
Figure 14: Three different distance configurations generated by the same model: (d1, d2) = (1,0.4) (left), (0.5, 0.5) (middle), and (0.6, 1.0) (right). The bottom two rows show patterns similar to Stechkin's 's construction at (0.5, 0.5), while the outer columns reveal patterns that to our formalized constructions.
17

---

Neural Discovery in Mathematics
D. Details on Variant 3: Coloring three-dimensional space
Visualizing and thus also interpreting and formalizing a three-dimensional coloring is much more challenging than the two dimensional case. To better understand the structure of colorings, we extracted polyhedral regions from the NN output and explored them in interactive plots. One of these colorings is shown in Figure 15.
Since our numerical experiments did not suggest the existence of 14-coloring without unit distance conflicts, we applied an adapted version of Algorithm I to construct an almost- 14-coloring of space in fully automated fashion. It covers all but 3.4 3.46% of IR", though it seems that this value might be improved through a finer discretization.
N
Figure 15: A thrce-dimensional coloring found by our approach. We only show four out of the fourteen colors.
18

---

Neural Discovery in Mathematics
E. Details on Variant 4: Avoiding triangles
D 3 colors
4 colors
5 colors
6 colors
Figure 16: Numerical results showing the achievable color bounds when avoiding monochromatic triangles. We trained thousands of networks different sub-areas of the above region and say that point can be achieved with three, four, five, or six colors if the top 3% of runs for that point reported that less than 1% (left), 0.1 % (middle), and 0.01 1% (right) of sampled triangles were monochromatic in the argmax coloring derived from the trained NNs.
19

---

Neural Discovery in Mathematics
F. Different p-norms
Our approach extends to different norms in R", The loss function remains the same, while the respective ball B (x) is replaced by the L,-ball (z) {y I I --- yllp S 1}. To generate samples from the L,-ball, we use the probabilistic method proposed by Barthe et al. (2005). The cases = 1 and p = do in I2 are relatively straightforward to derive, as there exist colorings using four colors by arranging the balls in a regular grid. However, in particular the case p = 1 produces visually interesting results, as not only the trivial constructions are found but variations thereof, see Figure 17.
-1
Figure 17: Colorings found for the L norm. Left: The trivial grid coloring. Middle and right: Colorings which utilize the degrees of freedom present in the coloring.
20


Reviews:
[{"review_id": "r8DRa8a9tz", "reviewer": "Reviewer_cNSg", "summary": "The paper proposes a neural-net approach to solving the Hadwiger-Nelson problem. The problem involves coloring the plane under the constraint that no pair of points with unit distance has the same color. The paper treats this problem as an unsupervised combinatorial/continuous optimization problem. By adopting a probabilistic formulation of the problem, the authors design a differentiable loss function and use gradient descent to train a neural net to minimize the constraint violation for randomly sampled points in space. \n\nThe approach is flexible and enables solving several variations of the problem including a version that allows for different distance constraints on each color as well as coloring in higher dimensions. and is able to find new valid colorings for different variants of the problem.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and very relevant comments! Let us split our response into three parts.\n\n**The relationship between the NN output and formal results**\n\nYou point out an important aspect that we could have perhaps made more clear in our submission. The neural networks provide numerical approximations that serve as visual inspiration for formal mathematical constructions. These numerical outputs typically achieve very low loss values in Equation (2), around 1e-7 evaluated on a discretized grid of size 512 x 512, whenever they correspond to actual formal constructions fulfilling the constraints of Equation (1). However, translating the suggested colorings into rigorous mathematical constructions is a manual and ad-hoc process requiring human interpretation and verification. This process varies in difficulty:\n\n1. For the triangles (Variant 4), formalization was relatively straightforward as the networks simply suggested stripe-based colorings with previously not considered widths.\n2. For off-diagonal colorings (Variant 2), formalization was more complex though ultimately only relied on basic trigonometry and about a week’s worth of by-hand experimentation with pen and paper.\n3. For 3D colorings (Variant 3), formalization remains challenging despite promising numerical results. We are exploring approaches using Voronoi cells. The paper by Xu et al. that you pointed out may also prove relevant in this context, so thank you for that recommendation!\n\nWe should point out that this manual process is also why we chose to publish the actual formal constructions as separate results in journals more suited to these types of questions while choosing ICML as the venue where we describe the underlying machine-learning-guided framework that led to these discoveries, similar to the work of [Davies et al. (2021b)](https://www.nature.com/articles/s41586-021-04086-x.pdf) on knot invariants that was separately formalized by [Davies et al. (2021a)](https://msp.org/gt/2024/28-5/p06.xhtml). We will make sure to more clearly highlight this aspect in the revision of the paper.\n\n\n**Main achievements and tabular summary**\n\nFirstly, we see the main achievements obtained using the methodology described in this paper as follows:\n\n1. **Variant 1: “Re-discovered” previously known constructions due to Pritikin/Part (Table 1, Figures 4, 10).**  Note that, after reviewing the data in Table 1, we found some inaccuracies in our values. These errors occurred because our training box was too small, causing the results to be affected by the cyclical pattern of the coloring. We corrected this by conducting the training in a much larger box. This correction produced values that are now much more consistent with Pritikin's / Croft's findings.\n2. **Variant 2: Clear and formalized improvements in the form of the two colorings (Figure 2, 12).** The description of these was published independently in a journal specializing in combinatorial and geometric problems.\n3. **Variant 3: Suggests 3D space can \"almost\" be colored with 14 colors.** As already mentioned, the description of a formal result is still work-in-progress.\n4. **Variant 4: Clear and formalized improvements (Figure 3).** We intend to submit the description of these to a journal specializing in combinatorial and geometric problems.\n\nWe should emphasize that we view formalized (and preferably published) constructions as the ultimate benchmark required to validate the methodology presented in this submission. This, as well as the fact that improvement is often not measurably through a single metric, makes summarizing the results in a tabular environment a bit challenging. Your point is still valid and well received though and we will make sure to summarize and emphasize the results more clearly in our submission.\n\n\n**Additional points**\n\n* We tested values between 1e-5 and 5e-1 for the Lagrangian coefficient. Values from 1e-3 upwards led to runs where the constraint was (effectively) fulfilled. There was however not a clear \"sweet spot\" or tendency for larger weights to produce better colorings. We simply treated this as a hyperparameter that needed to be tuned.\n* There is no guarantee that patterns from a finite box extend to the entire plane, though all our promising candidates exhibited clear periodic structures. Boxes with side lengths anywhere between 6 and 10 units proved sufficient for clear patterns to emerge without computational overhead. Choosing a box that is too small would certainly lead to non-sensical results that do not relate to any coloring of the plane.\n* The paper by Xu et al. that you suggested seems very interesting and highly relevant and we will make sure to include a reference to it.\n\nWe would like to thank you again for your positive and constructive review. We hope to have addressed your concerns, please let us know if further clarification is needed.", "claims_and_evidence": "Some details are unclear. Some of the limitations of the approach are not adequately discussed.\n- The paper does not clearly explain how the 'formalized' colorings are obtained from the informal ones. There seem to be some subtleties around this that should be carefully discussed. For example, the numbers in table 1 suggest that the neural coloring proposed is an improvement. On the other hand, the comments in the table caption say that there are similarities with known constructions that prevent this coloring from being formalized. I believe observations like this merit further discussion and a more thorough explanation of the process of converting a 'neural' coloring to a formalized one should be given (perhaps in the appendix).", "methods_and_evaluation_criteria": "The benchmarking setup is clear. However, I recommend constructing a table that summarizes the results of the paper for each variant of the problem. One column could include the best-known result for the given variant (and a citation to the corresponding paper) and another with the best achieved by the proposed method. The table (or its caption) could also refer to specific figures or sections in the paper and/or provide additional context.", "theoretical_claims": "- The authors use the predictions of the neural network as plausible candidate patterns for formalized colorings. Indeed, the paper claims that strictly speaking, one cannot guarantee that the colorings discovered in a given box generalize to the entire plane.  What are the main obstructions when it comes to generalizing a pattern from a fixed box to the entire plane? Are there some known conditions?\n\n- As a follow-up to the question above, are there any conditions on the size of the box? I am asking this because it seems that a really small box (say [-1e-6, 1e-6] might introduce trivial colorings. Or is that not the case and why?  \n\n- Proposition 1 suggests that a valid probabilistic mapping will be found for points in the box and their neighbors in the plane. The integral for the loss is estimated by appropriately sampling points and minimizing the constraint violations for them. My question is: I suspect the loss is never quite 0, even for just the subset of points that the neural network sees in training. To get the results you demonstrate in the images, what values of the loss are sufficient? Are they really small/close to 0? Does the neural net converge to some small number that is clearly above zero?  Moreover, what happens when you use the Lagrangian relaxation with a specific coefficient? Did you have to eyeball the solutions in this case?", "experimental_designs_or_analyses": "See my other comments.", "relation_to_broader_scientific_literature": "The findings relate to mathematical discovery and ML-assisted theorem proving. The paper establishes new colorings that were previously not discovered.", "essential_references_not_discussed": "There's this paper on constructing aperiodic tilings with GNNs in an unsupervised fashion [1] which is somewhat similar in spirit to this one. The loss function isn't as rigorously constructed but I believe it should be mentioned in your paper. \n\n\n1. Hao Xu, Ka-Hei Hui, Chi-Wing Fu, and Hao Zhang. 2020. TilinGNN: learning to tile with self-supervised graph neural network. ACM Trans. Graph. 39, 4, Article 129 (August 2020), 16 pages. https://doi.org/10.1145/3386569.3392380", "other_strengths_and_weaknesses": "Overall, I like the paper and I think it provides a rather interesting perspective on theorem proving with the help of neural nets. The approach is fairly simple and it shows that one can leverage neural nets to naturally parameterize problems in math. I begin with a tentative score that I am willing to increase once some of my concerns and questions have been addressed.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I7vBERvE22", "reviewer": "Reviewer_uyCR", "summary": "The paper proposes an AI framework to tackle an open problem in coloring the plane in R^2. Some other variants consider R^n as well.\nAuthors reformulate the problem as an optimization task, they introduce a differentiable loss function and do greedy sampling to minimize the penalty loss they introduced. \nAlso authors discussed different variants of the same problem, describing exactly the loss to optimize again. \nThe work extends the d interval from where there exists a (1, 1, 1, 1, 1, d) coloring, a great advancement in the field.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments and taking the time to referee our submission! Let us address your points individually:\n\n> The authors state that constructions were \"formally verified\" in another venue (Anonymous, 2024), but given it's Anonymous we cannot verify this claim. Is there any other way to verify it?\n\nRegarding the anonymous citation, we would like to clarify that the referenced paper—submitted as supplementary material—was authored by us and provides a formal description of two colorings. It was published in a journal focused on combinatorial and geometric results. We consider formalized (and preferably published) constructions as the ultimate benchmark required to validate the methodology presented in this submission. However, conveying this clearly proved challenging due to the constraints of the double-blind review process. We are happy to allow our journal publication to be reviewed by the AC/SAC without disclosing our identities to the reviewers.\n\n\n> Maybe some lines of work on AI4Math where AI (partially) solved open problems? There are a few to mention, but notably https://deepmind.google/discover/blog/alphageometry-an-olympiad-level-ai-system-for-geometry/ or https://proceedings.neurips.cc/paper_files/paper/2024/hash/aa280e73c4e23e765fde232571116d3b-Abstract-Conference.html\n\nThank you for pointing out the two papers. We are happy to broaden the scope of the related literature section and include them.\n\n>  It would be interesting to see its applicability to other open research problems on geometric (or graph) coloring.\n\nWe fully agree. We are in the process of applying our methodology to other problems, but decided to focus on the Hadwiger-Nelson problem and its variants for this submission and reserved the application to other problems for future work.\n\n> The claim that this method \"consistently recovered patterns resembling Pritikin’s construction\" is not very quantifiable - we can visually inspect it, but there are some discrepancies. Is it possible to quantify them, or at least understand if the gap can be closed easily by human on harder problems?\n\nRegarding your question about recovering the results of Pritikin, this is unfortunately a point that is difficult to formally quantify. The neural networks provide numerical approximations that serve as visual inspiration for formal mathematical constructions. These numerical outputs typically achieve very low loss values in Equation (2), around 1e-7, whenever they correspond to actual formal constructions fulfilling the constraints of Equation (1). However, translating the suggested colorings into rigorous mathematical constructions is a manual and ad-hoc process requiring human interpretation and verification. This process varies in difficulty and for example required about a week’s worth of by-hand experimentation with pen and paper for Variant 2. In the case of Variant 1, we simply relied on visually inspecting the suggested colorings and the reported loss values and noting that they closely align with those described by Pritikin. Note that, after reviewing the data in Table 1, we found some inaccuracies in our values. These errors occurred because our training box was too small, causing the results to be affected by the cyclical pattern of the coloring. We corrected this by conducting the training in a much larger box. This correction produced values that are now much more consistent with Pritikin's / Croft's findings. We will make sure to update our submission to include the updated values. Regarding your questions of closing the gap when applying the approach to a harder problem: This depends heavily on the problem. In the case of Hadwiger-Nelson (in R^2), by its visual nature the problem can be approached by a human in a clear way. This may not be the case for other problems and could necessitate the application (or development) of other tools to construct formal solutions. For the Hadwiger-Nelson case (in higher dimensions), one could think of using Voronoi cells or other ways of creating polygons / parameterized geometrical shapes that closely match the output of the neural network but allow for a rigorous verification. In the general case, it is currently not possible for us to give a clear recipe on how to formalize the neural network outputs.\n\n> What's the density of points/R^2 you tested?\n\nRegarding your question about how many points we sampled for our numerical results, we evaluated the models on a grid of size 512 x 512 and uniformly sampled 256 points on a circle centered at each grid point. We will make sure to update our submission to include some more details regarding this in the appendix.\n\nThanks again for your review, please let us know if further clarification is needed.", "claims_and_evidence": "Main claim is the authors improve the known distance range for colorings. \n\nThe authors state that constructions were \"formally verified\" in another venue (Anonymous, 2024), but given it's Anonymous we cannot verify this claim. Is there any other way to verify it?", "methods_and_evaluation_criteria": "This doesn't apply, given AI is used as a baseline for human to validate and prove formally some geometrical constructions.", "theoretical_claims": "There aren't theoretical claims from the authors.", "experimental_designs_or_analyses": "Authors trained a simple MLP model, adding a sin activation and a final softmax. They claim they trained 100k runs, which, due to sampling and different training strategies is plausible. \nThey reported the AI result, which again seems very valid. \nThey could have added a bit more on lr, batch size to ensure reproducibility.", "relation_to_broader_scientific_literature": "The paper appropriately cites prior ML-for-math works (e.g., Karalias & Loukas, 2020; Fawzi et al., 2022) and connects to physics-informed NNs.", "essential_references_not_discussed": "Maybe some lines of work on AI4Math where AI (partially) solved open problems? There are a few to mention, but notably https://deepmind.google/discover/blog/alphageometry-an-olympiad-level-ai-system-for-geometry/ or https://proceedings.neurips.cc/paper_files/paper/2024/hash/aa280e73c4e23e765fde232571116d3b-Abstract-Conference.html", "other_strengths_and_weaknesses": "The framework’s adaptability to multiple variants is innovative. It would be interesting to see its applicability to other open research problems on geometric (or graph) coloring.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "The claim that this method \"consistently recovered patterns resembling Pritikin’s construction\" is not very quantifiable - we can visually inspect it, but there are some discrepancies. Is it possible to quantify them, or at least understand if the gap can be closed easily by human on harder problems?\n\nWhat's the density of points/R^2 you tested?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jZsdPlOrSm", "reviewer": "Reviewer_wpnp", "summary": "This paper tackles a combinatorics problem using neural networks, specifically the Hadwiger-Nelson problem, which involves coloring the plane under distance constraints. The problem is continuously relaxed through probabilistic coloring. Inspired by numerical outputs from neural networks, the authors derive a formal construction that advances the field. Additionally, the paper explores multiple variants with different constraints.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment! \n\nWe appreciate your thoughtful comments about our paper's position as a scientific contribution. You raise a fair point about methodological innovation versus application. We agree that it's always challenging to determine ML methodological contributions for these types of papers. In our view, progress often comes from either advancing methodology or applying reasonable/existing methods to new domains - we focused on the latter approach. This is similar to the work of [Davies et al. (2021b)](https://www.nature.com/articles/s41586-021-04086-x.pdf) and [Davies et al. (2021a)](https://msp.org/gt/2024/28-5/p06.xhtml), where the methodology of modeling statistical relations through neural networks and attributing relevance through gradients was not novel but nevertheless yielded interesting and relevant mathematical insights. \n\n> Are the authors planning to extend this work to other HN coloring problems or other discrete geometry problems?\n\nYes, we definitely intend to continue applying our approach to other HN coloring problems and discrete geometry challenges, which we plan to include in any future journal version based on this submission.\n\nThank you again for your review, please let us know if further clarification is needed.", "claims_and_evidence": "The paper is well-written with beautiful visualizations.", "methods_and_evaluation_criteria": "Intuitive and reasonable.", "theoretical_claims": "Seems to be correct.", "experimental_designs_or_analyses": "Seems to be correct.", "relation_to_broader_scientific_literature": "I was really impressed by Davies et al. (2021), which demonstrated that AI can significantly advance mathematics. While its capability in formal proving is limited, at least for complex problems that cannot be easily derived using Lean, AI can assist humans in optimizing better solutions for combinatorics problems. This paper serves as another strong example of AI as a co-scientist, contributing to progress in discrete geometry problems.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I believe this paper is a solid scientific contribution and would be relevant to the ML community working on combinatorial optimization.\n\nHowever, while this paper may inspire new applications, its technical contribution seems limited. Continuous relaxation for combinatorial optimization is a well-established approach, and relaxing the coloring problem into a probabilistic form is a natural choice. While I appreciate the authors' effort in designing formulations for different variants, it is unclear whether these formulations introduce non-trivial insights that could meaningfully influence future research in adapting similar techniques to other problems.\n\nFor this reason, I am inclined to accept the paper, but a higher recommendation should depend on its potential impact on the ICML audience.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Please let me know if I missed any ML methodological contributions.\n2. Are the authors planning to extend this work to other HN coloring problems or other discrete geometry problems?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4IahU3g3jJ", "reviewer": "Reviewer_dBz6", "summary": "This work demonstrates how neural networks can help mathematical discovery, focusing on the Hadwiger-Nelson problem, which seeks the minimum number of colours needed to colour the Euclidean plane while avoiding unit-distance monochromatic pairs. By reformulating this mixed discrete-continuous problem as an optimization task with a differentiable loss function, the authors leverage neural networks to explore admissible colourings. This approach led to the discovery of two novel six-colorings.\n\n## Update after rebuttal: \n\nThis paper presents an interesting contribution to the field of AI for Mathematics. It is generally well written, with only a few minor typos, which the authors have acknowledged and stated they have corrected.\n\nThere are, however, areas that could be improved. For instance, some statements come across as quite strong—for example, in lines 056–060: \"Rather than attempting to obtain proofs that are fully automated end-to-end, our method serves as a tool for mathematical discovery by providing the right intuition about potential constructions.\" This claim may not always hold and could benefit from a more balanced or cautious phrasing. The authors mentioned that will address this point. \n\nAnother noteworthy aspect of the paper is the discussion on using neural network outputs to guide the construction of HN contracts. The authors mention that this process still requires significant manual experimentation (see question/answer 4), which is an important limitation to highlight. The authors mentioned that will add this paper in the paper. \n\nOverall, I find the paper interesting and well-executed. In light of the rebuttal and improvements, I have increased my score from 3 to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and constructive feedback. Let us first address your questions and then the remaining comments:\n\n\n**Question 1:**\n\nRegarding the anonymous citation, we would like to clarify that the referenced paper—listed as \"Anonymous (2024)\" and included as supplementary material—was authored by us and presents specific mathematical constructions derived using the methodology introduced in this ICML submission. It has been accepted in a journal specializing in combinatorial and geometric problems, which we view as strong validation of our approach. Our ICML paper focuses on the underlying methodology that led to these results, in a manner similar to  [Davies et al. (2021b)](https://www.nature.com/articles/s41586-021-04086-x.pdf)  and [Davies et al. (2021a)](https://msp.org/gt/2024/28-5/p06.xhtml), where the methodological framework was presented in Nature and the resulting mathematical findings were published separately in more specialized venues. Due to the constraints of the double-blind review process, we anonymized the citation. We are happy to allow our journal publication to be reviewed by the AC/SAC without disclosing our identities to the reviewers.\n\n**Question 2:**\n\nWe consider the results covered in Figures 9, 10, and 11 to serve as validation examples, as they recover known constructions. However, we're happy to include specific additional examples with known solutions if that would strengthen the paper. Could you clarify what types of toy examples you have in mind that would be most helpful?\n\n**Question 3:**\n\nWe appreciate this suggestion. While we understand the value of direct comparisons, our work presents unique challenges for tabular representation for two key reasons:\n\n1. The improvements we demonstrate span multiple dimensions that cannot be easily reduced to single-value comparisons.\n2. We consider formalized, peer-reviewed constructions as the primary benchmark for validating our methodology, rather than simplified metrics.\n\nNevertheless, we recognize the importance of clearly presenting our contributions relative to previous work. In our revised submission, we will add a comprehensive comparison that highlights our achievements alongside previous approaches. This will provide a clearer picture of our contributions while maintaining the nuance necessary for proper evaluation.\n\n**Question 4:**\n\nThank you for this important question. The transition from continuous neural network output (left) to formal construction (right) involves careful human interpretation and mathematical formalization. The non-straight boundaries in the neural network output reflect the inherent flexibility in the solution space. We intentionally straightened these boundaries in the formalized version to simplify the mathematical description without compromising validity. For the off-diagonal colorings in Figure 2, this formalization process required about one week of manual experimentation using basic trigonometry to convert the neural network's patterns into precise mathematical expressions. The complexity of this step varies depending on the specific problem variant.\n\n\n**Additional Points:**\n\n* Regarding your statement about intuition not stemming from neural networks but rather from the continuous formulation: We appreciate this perspective, but would like to clarify that neural networks did provide the specific visual patterns that inspired our formal constructions. While one could certainly use alternative function families as universal approximators, the specific patterns produced by our neural network approach directly led to the insights that enabled our formal constructions. We'll revise our presentation to make this relationship clearer and more balanced.\n* We agree that including plots showing the loss decreasing during optimization would strengthen the paper. We'll add plots showing typical convergence patterns for our successful runs, with losses decreasing to values around 1e-7 for seven colors and 1e-6 for six colors (and sometimes as low as 1e-12) when evaluated on a 512 × 512 discretized grid.\n* Thank you for highlighting \"*A Finite Graph Approach to the Probabilistic Hadwiger-Nelson Problem*\". We are happy to expand the related literature section to include more references regarding improvements of the lower bounds.\n* We'll fix all the typographical errors and inconsistencies you noted.\n* We'll replace arXiv citations with published versions where available, this was definitely an oversight during our submission.\n* We'll add specific section references when referring to appendix materials and we'll add appropriate citations for Pritikin's and Stechkin's constructions whenever mentioned.\n\n\nThank you again for your thorough feedback, which will help us improve the clarity and rigor of our paper.", "claims_and_evidence": "The main evidence for this paper is based on a cited work listed as Anonymous, Anonymous Journal, 2024, indicating that the original idea originates from the same authors. The anonymous paper is included in the supplementary material. In lines 069–072, the authors mention that the anonymous work has been formally verified and published in a venue specializing in combinatorial geometric problems. Therefore, I see no reason why the anonymous paper was not consistently referenced, leading the reviewers to fail to realize that the authors are the same. This has resulted in a misunderstanding.", "methods_and_evaluation_criteria": "The approach to this problem makes sense; the authors aim to relax the discrete optimization of the Hadwiger-Nelson problem into a continuous format and minimize its loss using neural networks. It would be helpful for them to provide plots of the loss and the results of optimizing the hyperparameters of the neural network. Additionally, it would be beneficial to see an example where this approach is applied to a toy version of the Hadwiger-Nelson problem with a known solution, ensuring its validity before presenting results for the more complex cases.", "theoretical_claims": "There is one proposition that validates the transformation from discrete optimization to continuous optimization (see lines 239–243), which seems correct.", "experimental_designs_or_analyses": "Yes, I checked the experimental designs. They seem correct, but I believe there is room for improvement. For example, since the authors use a neural network to minimize the continuous loss for the Hadwiger-Nelson problem, there is no plot showing that this loss decreases to zero over time. Including such a plot would be helpful.", "relation_to_broader_scientific_literature": "From what I understand, this paper makes two main contributions: a) transforming the discrete optimization Hadwiger-Nelson problem into a continuous one and using neural networks to solve it, b) discovering two novel six-colorings of the plane for the off-diagonal Hadwiger-Nelson problem based on their results.", "essential_references_not_discussed": "The authors have included many related works, covering the most important ones. However, I found the paper \"A Finite Graph Approach to the Probabilistic Hadwiger-Nelson Problem\" by H. Gwyn et al., which appears relevant and could be added.", "other_strengths_and_weaknesses": "The paper introduces the idea of transforming the Hadwiger-Nelson (HN) problem from discrete optimization to continuous optimization, which is an interesting and, to the best of my knowledge, novel direction. Their findings are also noteworthy. However, while the discrete-to-continuous transformation is valuable, it is not a new concept in general. Regarding the statement in lines 056-060—\"Rather than attempting to obtain proofs that are fully automated end-to-end, our method serves as a tool for mathematical discovery by providing the right intuition about potential constructions.\"—I believe the underlying intuition does not stem from the use of neural networks but rather from the fact that the problem itself is now continuous. As a result, this claim seems somewhat strong and unrealistic, and it would be better to present it in a more cautious and balanced manner.", "other_comments_or_suggestions": "A) There are a few typos in the text:\n1) At the beginning, the authors refer to 'Neural Networks' as 'NN', so please ensure consistency throughout the text (see lines 049, 090, 420, 423, 442).\n2) The same applies to 'Machine Learning'—please maintain consistency (see lines 040, 096, 432, 442, 453).\n3) The word 'invariant' appears twice consecutively (see lines 076, 077).\n4) There is a typo in the word 'nuber', which should be 'number' (see line 308).\n5) 'Hadwiger-Nelson' should be replaced by HN, (see line 443).\n6) In the captions (see Figures 1 and 2), you write \"Neural Networks\" with a capitalized first letter, whereas in the abstract and main text, you sometimes use \"neural network\" in lowercase and other times \"NN\". Additionally, in the appendix figures, abbreviations are used inconsistently—for example, in Figure 9, \"HN\" is used instead of the full term, and similar inconsistencies appear in Figures 12 and 16. Please ensure consistency throughout. In the abstract and captions, use the full term \"neural networks\", while in the main text, introduce it as \"neural networks (NNs)\" the first time and then use \"NNs\" thereafter. Similarly, maintain a consistent approach for other abbreviations like \"HN\".\n7) You forgot the full stop in some cases after the bold text at the beginning of paragraphs (see lines 365, 373, and 380). Please ensure consistency by adding a full stop after the bold text where needed.\n\nB) Many citations reference ArXiv papers, despite the existence of official publications. Since ArXiv papers are not guaranteed to have undergone a peer review process, which is crucial, please replace ArXiv citations with the formal published versions. For example see line 459, the official paper is 'The signature and cusp geometry of hyperbolic knots Davies, A Juhasz, A Lackenby, M Tomasev, N Geometry and Topology volume 28 issue 2024 2313-2343 (24 Aug 2024)'\n\nC) In some parts of the text, you refer to details in the appendices but do not specify the exact section. Please be more specific, as seen in lines 321, 340, and 370. Follow the same approach as in line 383.\n\nD) Please be sure that you have added any relevant literature. For example the paper 'A finite graph approach to the probabilistic Hadwiger-Nelson problem, by H Gwyn et. al.' seems relevant to me. If it's not please explain me. \n\nE) In some parts of the text, references need to be added. For example, in line 316, when referring to Pritikin’s construction, and in line 352, when mentioning Stechkin’s construction, appropriate citations should be included for clarity and proper attribution.\n\nF) It is important to clearly understand your achievement regarding color planes. It would be helpful if you could add a table comparing previous findings with your own results. Could you include this? The table could be placed either in the introduction or the main text.", "questions_for_authors": "1) I’m a bit confused about the anonymous paper you added and how your work builds upon it. Could you clarify the key differences between your previous paper and the current one?\n\n2) Could you create a toy example of the Hadwiger-Nelson problem where the exact result is known and compare it with the outcome from the neural network? This would help demonstrate that your model performs well even in a simple case where a 'ground truth' exists, ensuring its validity before presenting results for more complex scenarios. \n\n3) Could you create a table comparing the results of previous works with your own? This would make it clearer what you have achieved in comparison to others.\n\n4) In Figure 1, on the left side, the boundaries between different colors are not straight lines, whereas on the right side, they are. How exactly did you construct this? More generally, what method do you use to transition from the continuous to the discrete problem?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is an excellent paper contributing to the emerging but still challenging field of using AI methods to derive new mathematical research. While the mathematical findings (new constructions for the Hadwiger-Nelson problem) have been peer-reviewed and published in a mathematical journal, this paper focuses on the underlying ML methods that were used to obtain mathematical intuitions that were the base of the novel constructions.
How to successfully use AI for math research remains a big challenge due to the unique rigorous and complex nature of mathematics. While there have been a handful previous works demonstrating that pairing up AI (to deliver intuitions) and math researchs (to make them rigorous) is a useful strategy, we are in desperate need of more success stories of that kind. This paper is such a success story.
Decision: Accept (oral)