Exact equations discovered by computing the Gröbner basis

In a striking example of mathematics and machine learning converging, researchers at the Jožef Stefan Institute in Slovenia have developed an algorithm that rediscovered the Fibonacci formula from nothing more than a handful of numbers—and then went on to find two recurrence relations that had never before been documented. The new method, called MoadeeB, treats equation discovery not as a problem of statistical fitting but as a question of pure algebra, and its large-scale tests on tens of thousands of integer sequences suggest it can outperform established symbolic regression, program synthesis, and neural approaches at their own game.

The work, published open access in the journal Machine Learning by Boštjan Gec, Sašo Džeroski, and Ljupčo Todorovski, addresses a deceptively simple question: given noise-free data, can a machine find the exact mathematical equation that generated it? Most symbolic regression systems, from evolutionary algorithms to neural networks, are built for the messy world of experimental measurement, where they seek approximate formulas that fit noisy data as closely as possible. But in mathematics, combinatorics, and symbolic domains, approximation is not good enough—an equation either holds exactly or it does not. The Slovenian team set out to build a learner in which exactness is guaranteed by construction, not bolted on afterward through rounding coefficients or validating outputs with heuristics.

The key insight comes from a classical corner of algebraic geometry. Every finite set of data points, viewed as points in space, determines what mathematicians call a vanishing ideal: the collection of all polynomial equations that evaluate to zero at every one of those points. Every polynomial in this ideal is, by definition, an exact equation satisfied by the data. The catch is that such ideals can be infinitely large, so the challenge becomes representing them compactly. This is where Gröbner bases enter the picture. A Gröbner basis is a canonical, finite set of polynomials that generates the entire ideal, and it can be computed algorithmically using methods dating back to Bruno Buchberger’s 1965 PhD thesis. In effect, the researchers repurposed a foundational tool of commutative algebra as a hypothesis class for machine learning—one whose members are, by definition, consistent with the training data.

To make the idea concrete, the authors show how the algorithm recovers the Fibonacci recurrence from the first few terms of the sequence: 0, 1, 1, 2, 3, 5, 8. The sequence is first converted into a tabular data set with columns for consecutive terms. Each row of the table is treated as a point, and each point determines its own simple ideal—for example, the row corresponding to the terms (1, 1, 0) yields the ideal generated by the polynomials that vanish at that single point. When multiple points are combined, the basis polynomials of their individual ideals are multiplied pairwise, producing a larger set of polynomials that all vanish on the combined set. Then, through repeated simplification using the axioms of ideals, this unwieldy collection collapses into a compact Gröbner basis. In the Fibonacci example, one of the polynomials that emerges is exactly the relation that each term equals the sum of the two before it. The algorithm, guided by Occam’s razor, simply selects the simplest polynomial in the basis—the one with the fewest terms and smallest coefficients.

Of course, the step-by-step construction is pedagogically inefficient. In practice, MoadeeB builds on the Möller-Buchberger algorithm, an exact method purpose-built for computing Gröbner bases of ideals of finite point sets. The algorithm takes a data matrix as input, removes duplicate points, computes the Gröbner basis of the corresponding vanishing ideal in exact rational arithmetic, then filters and sorts the resulting polynomials by a two-part complexity measure—one counting the number of terms, the other summing the number of digits in each coefficient’s numerator and denominator. It returns the simplest equations that hold perfectly for the data. Because everything is computed exactly over the rationals, no floating-point error, rounding, or post-processing ever enters the pipeline. Notably, the method can also produce equations in implicit form, where the relationship among variables is expressed as a polynomial equal to zero rather than solved for a single output variable—a capability that most symbolic regression tools, which assume explicit forms, lack entirely.

The empirical showcase for the method is the Online Encyclopedia of Integer Sequences, the vast curated database of number sequences maintained by the OEIS Foundation. The team evaluated MoadeeB on 34,831 sequences across three benchmarks. The first contained 27,236 sequences with documented linear recurrences, where the task was to reconstruct the known relations. Here MoadeeB exactly recovered the published recurrence for 10,222 sequences, with another 315 provably equivalent, and it found at least one valid exact equation for 92.3 percent of the entire benchmark—the lowest failure rate among the methods tested, though its provable reconstruction rate trailed Diofantos and SINDy, competitors that restrict their search to linear equations. MoadeeB’s broader hypothesis class means it often finds valid nonlinear relations whose equivalence to a known linear recurrence cannot be automatically verified, a trade-off the authors analyze in detail.

The more dramatic results came on the 164 “core” OEIS sequences, a set hand-picked by the encyclopedia’s curators as mathematically significant. On this benchmark, MoadeeB reconstructed eleven more equations than Diofantos and twelve more than SINDy, and it uncovered two recurrences that appear in no prior literature. For the sequence counting binary trees by height, the algorithm produced a nonlinear cubic recurrence; for the sequence of planted 3-tree counts, it found a related relation involving rational coefficients. Both equations were subsequently rigorously proved—by mathematician David E. Narváez—and formally accepted into the OEIS, a rare case of a machine learning system contributing genuinely new mathematics to a reference database. Notably, several of the equations only MoadeeB could recover involve integer division, such as recurrences for central binomial-like sequences, which the method captures naturally in implicit polynomial form but which lie outside the hypothesis spaces of its competitors.

The comparisons extended beyond symbolic regression. Against QSynt, a program-synthesis system that writes executable code for sequences, MoadeeB reconstructed more valid equations on the linear-recurrence benchmark, though QSynt’s Turing-complete search gave it an edge on the core sequences, where it can express patterns like exponential growth that are awkward to capture algebraically. Against classical computer-algebra “guessing” methods implemented in SageMath’s ore_algebra library—tools theoretically guaranteed to find linear recurrences given enough terms—MoadeeB reconstructed three more equations on the core benchmark, including four nonlinear relations that guessing methods cannot express. Only guessing managed to recover one high-degree linear recurrence that stumped MoadeeB. And against TM-OEIS, a transformer-based neural approach for inferring recurrences, MoadeeB achieved the best accuracy on predicting the next ten elements of 10,000 sequences when trained on 25 terms, and essentially matched the neural model on single-step prediction.

Efficiency is another point in the new method’s favor. A theoretical analysis shows that the Möller-Buchberger approach, applied to sequences with recurrence order o, runs in time asymptotically quadratic in the input size—better than the cubic complexity of the team’s earlier Diofantos system and exponentially better than SINDy when higher-degree polynomials are involved. In practice, MoadeeB was roughly ten times faster than Diofantos across the benchmarks, and on the core sequences it was the only method to complete its run within a two-day time limit. Part of this speed comes from a clever economy: rather than feeding hundreds of sequence terms into the algebraic machinery, MoadeeB incrementally increases the recurrence order and uses only the first few terms needed for each order, terminating as soon as a validated equation is found.

The implications reach beyond integer sequences. The authors demonstrate that MoadeeB can recover exact equations from general noise-free tabular data, including benchmarks drawn from graph theory, the geometry of Riemann surfaces, and symbolic computation tasks involving the rewriting of partial differential equation solutions. Because the method handles rational data and implicit equations natively, the researchers argue it is well suited to other curated mathematical databases, such as catalogs of knots and graphs. They also flag the method’s inherent limitation: because exact algebraic computation is brittle, MoadeeB cannot tolerate noise, so its domain is precisely the clean, symbolic data where approximate methods struggle philosophically rather than technically. With planned extensions incorporating sparse interpolation techniques and alternative vanishing-ideal algorithms, the work points toward a future in which automated mathematical discovery is not merely plausible-looking but provably exact.