Using artificial intelligence methods, researchers at the ELKH Alfréd Rényi Institute of Mathematics (Rényi Institute) have confirmed a geometric conjecture related to plane colorings that has been unresolved for more than half a century. The proof, combining methods from geometry, Fourier analysis, linear programming, graph theory and computer science, required the collaboration of researchers from the Analysis, Geometry, and Artificial Intelligence departments of Rényi Institute. An internationally recognized benchmark of scientific popularization, Quanta Magazine, also reported on the result.
What fraction of the plane can be colored so that two colored points cannot be exactly a unit distance away from each other? This geometric question was formulated by Leo Moser in the early 1960s. According to a conjecture of Paul Erdős, this fraction must be less than ¼. The currently best lower bound of 0.2293 is given by a construction by Hallard Croft dating back to 1967. Several research groups have published partial results on the problem, gradually strengthening the initial upper density estimate of 0.2857 to 0.2544 over the last 60 years. The new result by Gergely Ambrus (University of Szeged and Rényi Institute), Adrián Csiszárik (Rényi Institute and Eötvös Loránd University), Máté Matolcsi (Budapest University of Technology and Rényi Institute), Dániel Varga (Rényi Institute) and Pál Zsámboki (Rényi Institute) shows that the density in question cannot exceed 0.247. Their paper is accepted in the prestigious D1-ranked journal, Mathematical Programming.
The conjecture has been attacked over the decades using a variety of methods. The approach previously used by Ambrus and Matolcsi builds on the work of F. Vallentin and F. M. Oliveira Filho and transforms the original discrete geometric problem into a linear programming problem using Fourier analysis. This approach allowed them to prove the strongest estimate previously known, but the 0.25 bound conjectured by Erdős still seemed a long way off.
Based on an idea of Dániel Varga, in a first breakthrough toward proving the conjecture, the researchers developed a common generalization of previous theoretical methods. This helped them to reduce the problem to a search task: to prove Erdős's conjecture, it was sufficient to find a set of points on the plane with a specific set of properties. The required properties are too complex, making it impossible to find the corresponding point set using paper and pencil. Therefore, the researchers employed artificial intelligence methods. For this purpose, the Rényi Institute's high performance computer cluster was used, provided by the Artificial Intelligence National Laboratory (MILAB). After several months of intensive experimentation and one week of runtime, the computer cluster finally found a 23-point set with the required properties, and Erdős’s conjecture was settled.
The researchers continue their successful collaboration between institutions and between mathematical disciplines, aiming to solve further problems related to plane colorings.