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

Thank you for your thoughtful review and constructive feedback. Let us first address your questions and then the remaining comments:

Question 1:

Regarding 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) and Davies et al. (2021a), 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.

Question 2:

We 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?

Question 3:

We appreciate this suggestion. While we understand the value of direct comparisons, our work presents unique challenges for tabular representation for two key reasons:

1. The improvements we demonstrate span multiple dimensions that cannot be easily reduced to single-value comparisons.
2. We consider formalized, peer-reviewed constructions as the primary benchmark for validating our methodology, rather than simplified metrics.

Nevertheless, 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.

Question 4:

Thank 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.

Additional Points:

• 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.
• 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.
• 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.
• We'll fix all the typographical errors and inconsistencies you noted.
• We'll replace arXiv citations with published versions where available, this was definitely an oversight during our submission.
• 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.

Thank you again for your thorough feedback, which will help us improve the clarity and rigor of our paper.

Thank you for your positive assessment!

We 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) and Davies et al. (2021a), 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.

Are the authors planning to extend this work to other HN coloring problems or other discrete geometry problems?

Yes, 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.

Thank you again for your review, please let us know if further clarification is needed.

Thank you for the valuable comments and taking the time to referee our submission! Let us address your points individually:

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?

Regarding 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.

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

Thank you for pointing out the two papers. We are happy to broaden the scope of the related literature section and include them.

It would be interesting to see its applicability to other open research problems on geometric (or graph) coloring.

We 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.

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?

Regarding 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.

What's the density of points/R^2 you tested?

Regarding 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.

Thanks again for your review, please let us know if further clarification is needed.

Thank you for your positive and very relevant comments! Let us split our response into three parts.

The relationship between the NN output and formal results

You 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:

1. For the triangles (Variant 4), formalization was relatively straightforward as the networks simply suggested stripe-based colorings with previously not considered widths.
2. 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.
3. 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!

We 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) on knot invariants that was separately formalized by Davies et al. (2021a). We will make sure to more clearly highlight this aspect in the revision of the paper.

Main achievements and tabular summary

Firstly, we see the main achievements obtained using the methodology described in this paper as follows:

1. 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.
2. 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.
3. 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.
4. 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.

We 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.

Additional points

• 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.
• 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.
• 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.

We 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.