REPOSITORY > RESULTS

Abstract

Equation discovery, closely related to and frequently discussed under the term symbolic
regression, studies methods for identifying symbolic equations that describe relationships
in observed data. Most existing approaches to equation discovery are designed for noisy
measurements and therefore aim to discover approximate equations. In many mathematical
settings, however, approximation is not sufficient: the goal is to recover exact equations
from noise-free data. This dissertation introduces exact equation discovery, a form of
equation discovery concerned with finding equations that reconstruct the observed data
exactly and, where possible, are equivalent to the underlying ground-truth equations.
The dissertation is motivated by the need to discover exact laws in mathematical data,
such as the integer sequences from the On-Line Encyclopedia of Integer Sequences, OEIS.
Existing approaches to equation discovery typically come either from approximate symbolic
regression or from specialized methods in experimental mathematics and computer
algebra. This work combines these two types of approaches by developing broadly applicable
methods for exact equation discovery grounded in number theory and computational
algebraic geometry.
Two algorithms are developed in the dissertation. The first, Diofantos, reformulates
exact equation discovery over the integers as a problem of solving systems of linear Diophantine
equations. By replacing regression-based approximation with exact arithmetic
and Diophantine solving, Diofantos discovers polynomial equations that match the observed
data exactly. The second algorithm, MoadeeB, views equation discovery as the
computation of the vanishing ideal of the observed data. Using Gröbner bases, MoadeeB
supports the discovery of exact polynomial, implicit polynomial, and rational equations
over integers and rational numbers.
The methods are evaluated on large-scale OEIS benchmarks and synthetic benchmarks
generated from polynomial, rational, and implicit polynomial equations. On more than
30,000 OEIS sequences, they reconstruct known relations and discover undocumented ones.
They compare competitively with state-of-the-art symbolic regression, program synthesis,
and experimental mathematics approaches. Their practical value is further demonstrated
by the discovery of one simplified recurrence and two unknown recurrence relations for
OEIS sequences, subsequently approved by OEIS curators. The synthetic benchmarks
confirm their complementarity: Diofantos is best suited to polynomial equations, whereas
MoadeeB is better suited to rational and implicit equations.
Overall, the dissertation makes three main contributions. First, it defines exact equation
discovery as a distinct task at the intersection of equation discovery and experimental
mathematics. Second, it introduces two complementary methods for this task. Third,
it reformulates the discovery of recurrences from integer sequences as an equation discovery
problem, thereby connecting symbolic regression more directly with mathematical
databases such as the OEIS. Taken together, the results show that exact equation discovery
is feasible and holds promise for reconstructing known mathematical relations, generating
new mathematical hypotheses, and enriching mathematical knowledge bases.