pith. sign in

arxiv: 2607.02153 · v1 · pith:G23KZNBInew · submitted 2026-07-02 · 💻 cs.SC

Local polynomial factorisation: improving the Montes algorithm

Poteaux Adrien , Weimann Martin This is my paper

Pith reviewed 2026-07-03 01:38 UTC · model grok-4.3

classification 💻 cs.SC
keywords Montes algorithmlocal polynomial factorizationHensel lemmaNewton polygonsOM-factorizationdiscrete valuation ringapproximate rootscomplexity
0
0 comments X

The pith

Extending Hensel lemma to generalized Newton polygons and using approximate roots as type representatives yields almost optimal complexity for the Montes algorithm when residual characteristic is zero or high enough.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an improved version of the Nart-Montes algorithm for factoring polynomials over a complete discrete valuation ring. It first extends the Hensel lemma to the setting of generalized Newton polygons and derives a divide-and-conquer strategy from that extension. When the residual characteristic is zero or sufficiently high, the work proves that approximate roots serve as convenient representatives of the types that appear in the algorithm. This produces nearly optimal complexity bounds for both irreducibility testing and full factorization, including the cost of any auxiliary factorizations over the residue field. For the concrete task of computing an OM-factorization of a polynomial F the running time improves by a factor equal to the valuation of the discriminant of F.

Core claim

By extending Hensel's lemma in the context of generalised Newton polygons we obtain a new divide-and-conquer strategy. If the residual characteristic is zero or high enough, approximate roots are convenient representatives of types. This yields an almost optimal complexity both for irreducibility and factorisation issues, plus the cost of factorisations above the residue field. For instance, to compute an OM-factorisation of F in A[x], the complexity improves by a factor δ, the discriminant valuation of F.

What carries the argument

Extension of the Hensel lemma to generalised Newton polygons, together with the use of approximate roots as convenient representatives of types.

If this is right

  • Complexity of OM-factorization improves by the factor δ equal to the discriminant valuation.
  • Almost optimal complexity is achieved for both irreducibility testing and full factorization.
  • The cost of auxiliary factorizations over the residue field is included in the improved bound.
  • The divide-and-conquer strategy applies directly inside the Montes algorithm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same approximate-root technique may shorten factorization routines in other complete local rings.
  • Practical running times for high-degree inputs could decrease proportionally to the size of the discriminant.
  • The divide-and-conquer strategy could be ported to related lifting problems that rely on Newton polygons.

Load-bearing premise

That approximate roots serve as convenient representatives of types when the residual characteristic is zero or sufficiently high.

What would settle it

Run the new algorithm on a polynomial whose residual characteristic is high enough for the claim to apply yet whose approximate roots fail to represent types correctly, and measure whether the stated complexity improvement by the discriminant valuation still occurs.

read the original abstract

We improve significantly the Nart-Montes algorithm for factoring polynomials over a complete discrete valuation ring $\mathbb{A}$. Our first contribution is to extend the Hensel lemma in the context of generalised Newton polygons, from which we derive a new divide and conquer strategy. Also, if $\mathbb{A}$ has residual characteristic zero or high enough, we prove that approximate roots are convenient representatives of types, leading finally to an almost optimal complexity both for irreducibility and factorisation issues, plus the cost of factorisations above the residue field. For instance, to compute an OM-factorisation of $F\in\mathbb{A}[x]$, we improve the complexity by a factor $\delta$, the discriminant valuation of $F$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper improves the Nart-Montes algorithm for factoring polynomials over a complete discrete valuation ring A. It extends Hensel's lemma to generalized Newton polygons to derive a divide-and-conquer strategy. When the residual characteristic is zero or sufficiently high, it proves that approximate roots serve as convenient representatives of types. This yields almost optimal complexity for irreducibility testing and factorization (including residue-field factorizations). As a concrete example, the complexity of an OM-factorization of F is improved by a factor equal to the discriminant valuation δ of F.

Significance. If the claimed extension of Hensel's lemma and the approximate-root property hold with the stated complexity bounds, the work would deliver a substantial practical improvement to local factorization algorithms, reducing cost by a factor tied to δ. The divide-and-conquer approach derived from the generalized Newton polygon setting is a clear technical contribution that could influence implementations in computer algebra systems.

major comments (2)
  1. [Section establishing the approximate-root property] The proof that approximate roots are convenient representatives of types (invoked to reach the almost-optimal complexity) is load-bearing for the main claim. The manuscript must supply explicit, computable bounds on how large the residual characteristic must be for the property to hold, rather than the qualitative phrase 'high enough'.
  2. [Complexity analysis section] The complexity improvement by a factor δ for OM-factorization must be accompanied by a precise accounting that separates the cost of the new divide-and-conquer steps from the cost of factorizations over the residue field; without this breakdown it is unclear whether the claimed factor-δ saving is realized in the full algorithm.
minor comments (2)
  1. Define 'types' and 'OM-factorization' with a short self-contained paragraph in the introduction, as these terms are central but may not be familiar to all readers of cs.SC.
  2. Add a table comparing the new complexity bounds with those of the original Nart-Montes algorithm, citing the relevant equations for each term.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comments on our manuscript. We address each major comment below and will revise the manuscript to incorporate the suggested clarifications.

read point-by-point responses

  1. Referee: [Section establishing the approximate-root property] The proof that approximate roots are convenient representatives of types (invoked to reach the almost-optimal complexity) is load-bearing for the main claim. The manuscript must supply explicit, computable bounds on how large the residual characteristic must be for the property to hold, rather than the qualitative phrase 'high enough'.

    Authors: We agree that explicit bounds strengthen the result. The proof of the approximate-root property proceeds by ensuring that the residual characteristic exceeds quantities depending on the degree of F and the valuations appearing in the successive generalized Newton polygons. In the revised manuscript we will extract these quantities from the proof and state explicit, computable bounds (in terms of deg(F) and the relevant valuations) in the theorem statement. revision: yes

  2. Referee: [Complexity analysis section] The complexity improvement by a factor δ for OM-factorization must be accompanied by a precise accounting that separates the cost of the new divide-and-conquer steps from the cost of factorizations over the residue field; without this breakdown it is unclear whether the claimed factor-δ saving is realized in the full algorithm.

    Authors: We accept that a finer-grained cost breakdown is required. The divide-and-conquer strategy reduces the number and depth of Hensel-lifting phases, while residue-field factorizations are performed by an independent subroutine whose cost is independent of δ. In the revision we will insert a detailed complexity table that isolates the cost of the new divide-and-conquer steps from the residue-field factorizations and shows precisely when the overall factor-δ improvement is realized. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation chain begins with an extension of Hensel's lemma to generalized Newton polygons (yielding a divide-and-conquer strategy) followed by a proof that approximate roots are convenient type representatives when the residual characteristic is zero or sufficiently high. These steps are presented as independent extensions of standard algebraic tools rather than reductions to fitted quantities, self-definitions, or self-citation chains. No equations or claims in the provided text equate a prediction to its own inputs by construction, and the complexity improvement (by factor δ) is derived from the stated assumptions without circular renaming or load-bearing self-citation. The result is self-contained against external benchmarks such as prior Hensel lifting results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed from abstract alone; no full text was supplied, preventing exhaustive extraction of parameters or axioms.

axioms (1)
  • domain assumption A is a complete discrete valuation ring
    Explicitly stated as the ambient ring for the factorization algorithm.

pith-pipeline@v0.9.1-grok · 5659 in / 1099 out tokens · 27700 ms · 2026-07-03T01:38:00.732635+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references

  1. [1]

    Abhyankar.Algebraic Geometry for Scientists and Engineers, volume 35 ofMath- ematical surveys and monographs

    S. Abhyankar.Algebraic Geometry for Scientists and Engineers, volume 35 ofMath- ematical surveys and monographs. Amer. Math. Soc., 1990

    1990

  2. [2]

    J.-D. Bauch. Computation of integral bases.Journal of Number Theory, 165:382– 407, 2016

    2016

  3. [3]

    Bauch, E

    J.-D. Bauch, E. Nart, and H. Stainsby. Complexity of the OM factorizations of poly- nomials over local fields.LMS Journal of Computation and Mathematics, 16:139– 171, 2013

    2013

  4. [4]

    D. G. Cantor and D. Gordon. Factoring polynomials over p-adic fields. InANTS-IV, volume 1838 ofLNCS. Springer Verlag, 2000

    2000

  5. [5]

    Caruso, D

    X. Caruso, D. Roe, and T. Vaccon. Division and slope factorization of p-adic polynomials. InProceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’16, pages 159–166, New York, NY, USA, 2016. ACM

    2016

  6. [6]

    D. Ford, S. Pauli, and X.-F. Roblot. A fast algorithm for polynomial factorization overQ p.Journal de Th´ eorie des Nombres de Bordeaux, 14:151–169, 2002

    2002

  7. [7]

    J. v. z. Gathen and J. Gerhard.Modern Computer Algebra. Cambridge University Press, New York, NY, USA, 3rd edition, 2013

    2013

  8. [8]

    Gu` ardia, J

    J. Gu` ardia, J. Montes, and E. Nart. Okutsu invariants and newton polygons.Acta Arithmetica, 145:83–108, 2010

    2010

  9. [9]

    Gu` ardia, J

    J. Gu` ardia, J. Montes, and E. Nart. Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields.Journal de Th´ eorie des Nombres de Bordeaux, 23(3):667–696, 2011. 18

    2011

  10. [10]

    Gu` ardia, J

    J. Gu` ardia, J. Montes, and E. Nart. Newton polygons of higher order in algebraic number theory.Transsactions of the American Mathematical Society, 364:361–416, 2012

    2012

  11. [11]

    Gu` ardia, E

    J. Gu` ardia, E. Nart, and S. Pauli. Single-factor lifting and factorization of poly- nomials over local fields.Journal of Symbolic Computation, 47(11):1318 – 1346, 2012

    2012

  12. [12]

    Hart and A

    W. Hart and A. Novocin. Practical divide-and-conquer algorithms for polynomial arithmetic. In V. P. Gerdt, W. Koepf, E. W. Mayr, and E. V. Vorozhtsov, editors, Computer Algebra in Scientific Computing, pages 200–214, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

    2011

  13. [13]

    F. Hess. Computing riemann–roch spaces in algebraic function fields and related topics.Journal of Symbolic Computation, 33(4):425–445, 2002

    2002

  14. [14]

    J. v. d. Hoeven and G. Lecerf. Directed evaluation.Journal of Complexity, 60:101498, 2020

    2020

  15. [15]

    J. v. d. Hoeven and G. Lecerf. Univariate polynomial factorization over finite fields with large extension degree.Applicable Algebra in Engineering, Communication and Computing, Jan 2022

    2022

  16. [16]

    Kaltofen

    E. Kaltofen. Greatest common divisors of polynomials given by straight-line pro- grams.J. ACM, 35(1):231–264, Jan. 1988

    1988

  17. [17]

    Lebreton

    R. Lebreton. Relaxed hensel lifting of triangular sets.Journal of Symbolic Compu- tation, 68, Part 2:230 – 258, 2015. Effective Methods in Algebraic Geometry

    2015

  18. [18]

    Mac Lane

    S. Mac Lane. A construction for prime ideals as absolute values of an algebraic field.Duke Math. J., 2(3):492–510, 1936

    1936

  19. [19]

    S. MacLane. A construction for absolute values in polynomial rings.Trans. Amer. Math. Soc., 40(3):363–395, 1936

    1936

  20. [20]

    Moroz and ´E

    G. Moroz and ´E. Schost. A fast algorithm for computing the truncated resultant. InISSAC ’16: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, pages 1–8, New York, NY, USA, 2016. ACM

    2016

  21. [21]

    E. Nart. Okutsu-montes representations of prime ideals of one-dimensional integral closures.Publicacions Matematiques - PUBL MAT, 55, 07 2011

    2011

  22. [22]

    E. Nart. Local computation of differents and discriminants.Mathematics of Com- putation, 83(287):1513–1534, 2014

    2014

  23. [23]

    Neiger, J

    V. Neiger, J. Rosenkilde, and E. Schost. Fast computation of the roots of polyno- mials over the ring of power series. InISSAC’17, pages 349–356. ACM, 2017

    2017

  24. [24]

    S. Pauli. Factoring polynomials over local fields.J. Symb. Comp., 32:533–547, 2001. 19

    2001

  25. [25]

    S. Pauli. Factoring polynomials over local fields, ii. InANTS-IX, LNCS. Springer Verlag, 2010

    2010

  26. [26]

    Popescu-Pampu

    P. Popescu-Pampu. Approximate roots.Fields Institute Communiations, 33:1–37, 2002

    2002

  27. [27]

    Poteaux and M

    A. Poteaux and M. Weimann. A quasi-linear irreducibility test inK[[x]][y].Preprint, pages 1–21, 2018

    2018

  28. [28]

    Poteaux and M

    A. Poteaux and M. Weimann. Computing the equisingularity type of a pseudo- irreducible polynomial.Applicable Algebra in Engineering, Communication and Computing, 31:435 – 460, 2020

    2020

  29. [29]

    Poteaux and M

    A. Poteaux and M. Weimann. Computing Puiseux series: a fast divide and conquer algorithm.Annales Henri Lebesgue, 4:1061–1102, 2021

    2021

  30. [30]

    M. Weimann. Bivariate factorization using a critical fiber.Journal of Foundations of Computational Mathematics, pages 1–45, 2016. 20

    2016