Sampling Polynomial Rational Remainders with SP ℚ \mathbb{Q} R: A new Package for Polynomial Division and Elimination

Vsevolod Chestnov, Giulio Crisanti · 2025

Read Sampling Polynomial Rational Remainders with SP ℚ \mathbb{Q} R: A new Package for Polynomial Division and Elimination by Vsevolod Chestnov, Giulio Crisanti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14875.txt.

Introduction

Vsevolod Chestnov and Giulio Crisanti introduce a software package that speeds up polynomial division and variable elimination by working over finite fields. Symbolic algebra often chokes on expression swell, where intermediate formulas balloon in size while building Gröbner bases. Their Mathematica package sidesteps the swell by sampling results at many finite-field points and rebuilding the true answer from the samples.

The trick mirrors methods now standard in calculations for particle physics. On hard resultant problems, the package cuts run time and memory by orders of magnitude over classic symbolic routes. Applied to Feynman integrals, it also uncovers singularity structures that were previously out of reach, linking pure algebra speed to physics payoffs.

Catalog record

CREATORVsevolod Chestnov, Giulio Crisanti
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14875

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sampling Polynomial Rational Remainders with SP ℚ \mathbb{Q} R: A new Package for Polynomial Division and Elimination Vsevolod Chestnov, Giulio Crisanti Abstract We introduce SP ℚ \mathbb{Q} R, a new Mathematica package for the division and elimination of variables from polynomial systems. SP ℚ \mathbb{Q} R works by sampling and reconstructing results over finite fields, in an analogous manner to many state of the art Integration by Parts algorithms for Feynman integrals. This allows SP ℚ \mathbb{Q} R to effectively overcome expression swell during the construction of Gröbner bases, which in many cases is the major bottleneck in such computations. Benchmarks on state of the art Macaulay resultants show that SP ℚ \mathbb{Q} R can deliver substantial gains over symbolic computer algebra workflows — reducing both runtime and memory footprint by multiple orders of magnitude. Likewise when applied to study Feynman integrals, we show how SP ℚ \mathbb{Q} R can be used to find previously unknown Landau singularities. 1 Introduction Understanding and solving systems of polynomial equations is ubiquitous in mathematics, physics and beyond. Out of the many algorithms one can employ when studying such problems, perhaps the most important is that of polynomial division . This algorithm forms the backbone of many of the most powerful tools known to process such systems. Indeed, for systems of equations in multiple variables, one of the most common uses of polynomial division is the construction of Gröbner bases 10.1145/1088216.1088219 . With such a basis at hand many properties of a polynomial system become manifest: the number and dimensionality of its roots can be readily determined and variables can be systematically eliminated. This last property is crucial for, among other things, a systematic algorithm to find the roots of polynomial systems. Other important applications include computing syzygies, simplifying and solving multivariate algebraic constraints, as well as studying polynomial varieties systematically Cox:2015ode ; CoxLittleOshea:2005 ; Sturmfels:2002 . Beyond these general applications with vast scope, polynomial division and Gröbner basis algorithms enjoy many more specific applications. In the field of scattering amplitudes alone these techniques have been applied to integration by parts (IBPs) Gluza:2010ws ; Schabinger:2011dz ; Ita:2015tya ; Larsen:2015ped ; Agarwal:2020dye ; Wu:2023upw based on syzygy computations, as well as intersection theory inspired approaches Page:2025gso ; exploration Bitoun:2017nre and implementation Bertolini:2025zud of parametric annihilators; intersection number computations Weinzierl:2020xyy ; Fontana:2022yux ; Fontana:2023amt ; Brunello:2023rpq ; Brunello:2024tqf ; spinor helicity computations DeLaurentis:2022otd ; Campbell:2025ftx ; gravitational waveforms Brunello:2025cot ; Landau analysis algorithms Fevola:2023fzn ; Helmer:2024wax ; integrand decompositions Zhang:2012ce ; Mastrolia:2012an ; determination of annihilators of Feynman integrals Muller-Stach:2011qkg ; Lairez:2022zkj ; delaCruz:2024xit and their structures Chestnov:2025whi ; as well as many other related problems Gasparotto:2023roh ; Heller:2021qkz . Given their importance, considerable effort has been devoted to developing more efficient strategies for computing Gröbner bases FAUGERE199961 ; 10.1145/780506.780516 ; FAUGERE1993329 and implementing these algorithms in fast and reliable computer codes DGPS ; M2 ; msolve . Despite significant progress however, building Gröbner basis often remains a major bottleneck in practical applications. Indeed in general their calculation is known to be demanding, with worst-case (saturated) upper bounds that grow doubly exponentially in the number of variables Hermann1926 . Another important phenomenon that can make Gröbner basis computations challenging is expression swell : during exact symbolic manipulations, intermediate results can grow by orders of magnitude, both in degree and in size, often far beyond those of the final output ARNOLD2003403 ; 10.1007/3-540-51084-2_12 . This process is greatly exacerbated when the roots of the given polynomial systems depend on many symbolic parameters. In practice, uncontrolled swell can render otherwise modest reductions intractable. Aside from polynomial algebra, expression swell is also frequently a problem in Integration by Parts algorithms (IBPs) for Feynman integrals Tkachov:1981wb ; Chetyrkin:1981qh ; Laporta:2001dd . Essentially IBPs amount to performing Gaußian elimination on very large systems of equations, where physical parameters often cause intermediate expressions to become unmanageable. In the last decade, this problem has been mitigated to great success with the introduction of finite field sampling and reconstruction methods Kauers:2008zz ; Kant:2013vta ; vonManteuffel:2014ixa ; Peraro:2016wsq ; Peraro:2019svx ; Smirnov:2019qkx ; Klappert:2019emp ; 10.1145/3717582.3717588 . The key idea behind these approaches is to substitute all parameters for integers and perform all computations numerically, modulo a (large) prime number. By performing the same computation on multiple numerical slices, the full parametric dependence of the output can be restored via interpolation methods. Any remaining numerical coefficients can then be lifted back to the rational numbers via Wang’s algorithm Wang:1981 and the Chinese remainder theorem if necessary Peraro:2016wsq ; Peraro:2019svx . This approach presents three important advantages. Firstly, the modulo arithmetic ensures that all integer expressions are capped in size. This avoids expression swell even on the numerical slices. Secondly, any complicated cancellations in the algorithm’s output happen numerically, and before any interpolation/reconstruction. This in many situations effectively avoids the need for heavy symbolic processing steps which are required to see algebraic simplifications in many implementations. Finally this strategy is massively parallelisable, as numerical evaluations of sample points are fully independent calculations. This allows for effective scaling against available computer resources. In this work we concretely demonstrate that finite field sampling and reconstruction methods can be extremely effective in tackling heavily parametric problems in polynomial algebra. Indeed, the construction of Gröbner bases can be recast as solving linear systems through the construction of suitably large Macaulay systems 947c5834c2744a6f9ab0a3a3d98eef20 ; Buchberger2017 ; cryptoeprint:2025/793 . Specifically one multiplies the generators of the ideal by a finite set of monomials, assembles the resulting relations into a matrix, and performs Gaußian elimination to read off the remainders of the target polynomials. By performing these operations with finite field sampling and reconstruction algorithms, it is thus possible to bypass the intermediate expression swells that many algebraic Gröbner basis algorithms suffer from ARNOLD2003403 ; 10.1007/3-540-51084-2_12 . The extra structure present in (zero-dimensional) polynomial ideals also allows for the introduction and extensive usage of companion (often also denoted multiplication ) matrices Sturmfels:2002 ; CoxLittleOshea:2005 ; Cox:2015ode ; Huang:2015yka ; Jiang:2017phk ; Telen:2020thesis ; FebresCordero:2023pww ; Brunello:2024tqf . These matrices provide an elegant method to polynomially reduce any multivariate rational function, beyond just polynomials. Furthermore, they can be used to eliminate variables from polynomial systems by analysing their respective eigenvalue systems alma9911250933502466 ; Cox:2020 . By their nature, operations with and on companion matrices can also be ported to a finite fields pipeline, allowing for a clean integration with any other algorithms. In this paper we present the Mathematica package SP \mathbb{Q} R, or Sampling Polynomial Rational Remainders in full. SP \mathbb{Q} R’s main goal is to perform polynomial division and variable elimination in polynomial systems using a fully finite fields workflow, designed to never encounter intermediate expression swells. As its backbone SP \mathbb{Q} R utilises extensively the package FiniteFlow Peraro:2019svx , which supports many basic operations on functions, lists and matrices over finite fields. SP \mathbb{Q} R then repackages these low level operations into high level user accessible commands aimed at the analysis of polynomial systems. Only the final desired output is numerically sampled and reconstructed, ensuring that any complicated cancellations always happen numerically. Crucially this also means that SP \mathbb{Q} R never symbolically builds an explicit Gröbner basis, as this is nearly

Read the complete text