Ethan Fang, PhD, associate professor in the Department of Biostatistics and Bioinformatics at Duke University School of Medicine, co-authored a paper offering a formal proof of the Komlós conjecture, a mathematical problem that has puzzled mathematicians and theoretical computer scientists for decades.
In the preliminary version of the paper available from the arXiv preprint server, Fang and colleagues described how they used an AI system they developed to provide a proof for a mathematical proposition first stated about four decades earlier by the mathematician Janós Komloś.
“The Komlós conjecture asks a deceptively simple question: Can we divide a collection of items into two groups while keeping the groups balanced across many characteristics simultaneously?” said Fang.
Proposed by mathematician János Komlós in the 1980s, the conjecture predicts that such balance is possible under a specific condition: Each item’s overall contribution across the characteristics must be bounded. When that condition holds, the items can be divided so that the difference between the groups’ totals for every characteristic stays below a fixed constant, regardless of how many items or characteristics are involved.
The challenge is achieving that balance everywhere at once, and a division that balances one characteristic might leave another uneven. The team’s proof establishes that a sufficiently balanced division always exists, which proves that the Komlós conjecture is true.
“The Komlós conjecture is relevant to the types of questions that arise in situations such as assigning tasks, allocating resources, and rounding fractional solutions into actionable, yes-or-no decisions,” said Fang. “Our result shows that you can guarantee of a strong balance across many different characteristics or attributes simultaneously.”
This has substantial implications for various research fields that deal with highly complex systems. One of these fields is clinical research, where a constant concern in the design and analysis of clinical trials is whether the groups being compared – for instance, a group of participants receiving an experimental therapy and a group receiving a placebo-are similar enough that unmeasured differences might be affecting the results of the trial.
The work also highlights an emerging role for AI in mathematical discovery. The authors’ system, called the Odin Automatic AI Research Agent, is designed to carry out complex, multistep research tasks with human guidance. In this project, it discovered the proof, which the authors then scrutinized and organized into a mathematical paper.
“AI played a decisive role in discovering the argument,” said Fang. “Human researchers remain responsible for checking the reasoning carefully and communicating the results clearly.”
The Komlós preprint establishes that balanced divisions exist. In follow-up work, Fang and his colleagues have developed an efficient algorithm for finding such divisions, which they plan to release soon.
The team has also used Odin to investigate other longstanding mathematical problems. In another preprint, the researchers provided a proof of Talagrand’s 1989 convolution conjecture, which concerns how random noise smooths functions of many binary variables.
“Our work demonstrates the potential for AI systems to contribute new mathematical reasoning and help resolve longstanding research problems,” said Fang.
Read the paper at arXiv: Vector Balancing via Directional Total Variation
Related paper: Weak-Type Bounds for Convolution on the Boolean Hypercube.