Polynesian Journal of Mathematics

Volume 2, Issue 4

Improvements of convex-dense factorization of bivariate polynomials

Martin Weimann

Abstract:

We develop a new algorithm for factoring a bivariate polynomial $F\in 𝕂[x,y]$ which takes full advantage of the geometry of the Newton polygon of $F$. Under some non degeneracy hypothesis, the complexity is $\widetilde{𝒪}\left(V{r}_0^{\omega -1}\right)$ where $V$ is the volume of the polygon and $r_0$ is its minimal lower lattice length. The integer $r_0$ reflects some combinatorial constraints imposed by the polygon, giving a reasonable and easy-to-compute upper bound for the number of non trivial indecomposable Minkowski summands. The proof is based on a new fast factorization algorithm in $𝕂\left[\right[x\left]\right]\left[y\right]$ with respect to a slope valuation, a result which has its own interest.

Citation:

Martin Weimann. Improvements of convex-dense factorization of bivariate polynomials. Polynesian Journal of Mathematics, Volume 2, Issue 4, Pages 1–34. (Jul. 2025) DOI: 10.69763/polyjmath.2.4

Download citation in BIBTEX format

Milestones:

Received 12 Dec 2024
Revised 2 Jul 2025
Accepted 22 Jul 2025
Published 24 Jul 2025
Communicated by Roger Oyono

The above content is released under the terms of the Creative Commons Attribution 4.0 International license.