$p$-adic algorithm for bivariate Gröbner bases

Abstract

We present a $p$-adic algorithm to recover the lexicographic Gröbner basis $\mathcal{G}$ of an ideal in $\mathbb{Q}[x,y]$ with a generating set in $\mathbb{Z}[x,y]$, with a complexity that is less than cubic in terms of the dimension of $\mathbb{Q}[x,y]/⟨\mathcal{G}⟩$ and softly linear in the height of its coefficients. We observe that previous results of Lazard's that use Hermite normal forms to compute Gröbner bases for ideals with two generators can be generalized to a set of $t\in {\mathbb{N}}^{+}$ generators. We use this result to obtain a bound on the height of the coefficients of $\mathcal{G}$, and to control the probability of choosing a \textit{good} prime $p$ to build the $p$-adic expansion of $\mathcal{G}$.

(ACM) Proceeding in International Symposium on Symbolic and Algebraic Computation 2023 (ISSAC 2023), July 24--27, 2023, Tromsø, Norway

References in corpus (4)

• On the asymptotic and practical complexity of solving bivariate systems over the reals
• Change of basis for m-primary ideals in one and two variables
• Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix
• Newton iteration for lexicographic Gröbner bases in two variables