pith. sign in

arxiv: 2605.22514 · v1 · pith:6RWN5DRSnew · submitted 2026-05-21 · 💻 cs.SC · math.AC· math.AG

A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems

Thi Xuan Vu This is my paper

Pith reviewed 2026-05-22 01:35 UTC · model grok-4.3

classification 💻 cs.SC math.ACmath.AG
keywords composable polynomial systemssymbolic homotopyisolated regular solutionsprobabilistic algorithmfinite reflection groupsinvariant polynomialsChevalley-Shephard-Todd theoremalgebraic independence
0
0 comments X

The pith

A probabilistic algorithm solves composable polynomial systems by reducing them to an equivalent system in the inner variables, with complexity polynomial in input size and number of solutions.

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

The paper focuses on polynomial systems where each equation is a composition of an outer polynomial with a shared set of inner polynomials. It shows that this structure permits reducing the original system in n variables to a simpler system involving only those inner polynomials. A probabilistic algorithm is then used to compute all isolated regular solutions of the reduced system. A sympathetic reader would care because many systems arising in invariant theory or algebraic computations possess this structure, making direct solution methods impractical due to high degrees while the reduced version stays manageable. The approach targets cases such as polynomials lying in a subring generated by algebraically independent elements or invariant rings of finite reflection groups.

Core claim

We study the problem of computing the isolated regular solutions of a system of n polynomial equations in n variables over a field of characteristic zero. For systems with composable structure, where each polynomial f_i equals h_i of the inner polynomials g_1 through g_n, we reduce the original system to one in the g_j variables. We present a probabilistic algorithm that computes all isolated regular solutions, with arithmetic complexity polynomial in the input size and in the number of solutions. Applications include systems belonging to the subring generated by algebraically independent g_j and systems of invariant polynomials under finite reflection groups such as symmetric groups, hyperc

What carries the argument

The composable structure, expressed as each f_i = h_i(g_1, …, g_n), which allows reduction of the full system to an equivalent system in the g variables before applying symbolic solution methods.

If this is right

  • The method directly applies to any system whose polynomials lie in the subring generated by a set of algebraically independent polynomials g_1 to g_n.
  • It solves systems of invariant polynomials under finite reflection groups because the Chevalley-Shephard-Todd theorem guarantees that the invariant ring is a polynomial algebra.
  • The reduction improves the efficiency of symbolic homotopy or other algebraic solvers for any system possessing the stated composable form.
  • The probabilistic nature of the algorithm yields all isolated regular solutions with high probability while keeping complexity polynomial.

Where Pith is reading between the lines

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

  • The same reduction idea could apply to other structured systems in algebraic geometry that exhibit similar functional composition without being explicitly labeled as composable.
  • If the inner polynomials are algebraically dependent, the reduction step would require additional handling of relations among the g_j, potentially preserving polynomial complexity only under extra conditions.
  • Implementation in computer algebra systems could make previously intractable invariant computations routine for larger reflection groups.

Load-bearing premise

The given polynomials must admit a composable structure in which every equation is a composition using the same collection of inner polynomials.

What would settle it

Running the algorithm on an explicit composable system with known isolated regular solutions and observing either that it misses some solutions or that its running time grows faster than polynomial in the input size and the number of solutions.

read the original abstract

We study the problem of computing the isolated regular solutions of a system \((f_1,\ldots,f_n)\) of \(n\) polynomial equations in \(n\) variables \((X_1, \dots, X_n)\) over a field of characteristic zero \(k\). We focus on systems with a \emph{composable structure}, where each polynomial \(f_i\) can be expressed as a composition \( f_i = h_i(g_1,\dots,g_n)\). Exploiting this structure allows us to reduce the original system to one in the \(g_j\) variables, thereby significantly improving the efficiency of symbolic solution algorithms. We present a probabilistic algorithm that computes all isolated regular solutions, with arithmetic complexity being polynomial in the input size and in the number of solutions. A first important application is when \(f_1, \dots, f_n\) belong to the subring \(k[g_1, \dots, g_n]\), where \(g_1, \dots, g_n\) are algebraically independent polynomials in \(k[X_1, \dots, X_n]\). Another important application is to systems of invariant polynomials under finite reflection groups, since by the Chevalley-Shephard-Todd theorem their invariant rings are polynomial algebras. Typical examples include the symmetric groups \(S_n\), the hyperoctahedral groups \(B_n\), the dihedral groups \(I_2(m)\), and the exceptional finite reflection groups \(E_6, E_7, E_8, F_4, H_3, H_4\).

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

1 major / 0 minor

Summary. The manuscript claims to present a probabilistic symbolic homotopy algorithm for computing all isolated regular solutions of a system of n polynomial equations in n variables over a field of characteristic zero, where the system has a composable structure (each f_i = h_i(g_1, ..., g_n)). Exploiting this structure reduces the problem to a system in the g_j variables. The algorithm is asserted to have arithmetic complexity polynomial in the input size and the number of solutions, with applications to subrings generated by algebraically independent polynomials and to invariant polynomials under finite reflection groups (e.g., S_n, B_n, exceptional groups E_6, E_7, E_8).

Significance. If the reduction, algorithm, and complexity bound hold, the result would be significant for symbolic computation and algebraic geometry. It targets a structured class of systems that arise naturally in invariant theory, where general-purpose solvers face high complexity; a polynomial bound in input size and solution count could make previously intractable problems practical, especially for reflection-group invariants.

major comments (1)
  1. Abstract: the central claim that the probabilistic algorithm achieves arithmetic complexity polynomial in the input size and number of solutions is asserted without any derivation, supporting lemmas, analysis of regularity conditions, or description of the homotopy construction and reduction step; these details are required to verify the claim and are absent from the provided manuscript (which consists only of the abstract).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their summary and for highlighting the potential significance of the work for symbolic computation and invariant theory. We agree that the current manuscript version is limited to the abstract and therefore lacks the requested derivations and details.

read point-by-point responses

  1. Referee: Abstract: the central claim that the probabilistic algorithm achieves arithmetic complexity polynomial in the input size and number of solutions is asserted without any derivation, supporting lemmas, analysis of regularity conditions, or description of the homotopy construction and reduction step; these details are required to verify the claim and are absent from the provided manuscript (which consists only of the abstract).

    Authors: We acknowledge that the provided manuscript consists solely of the abstract and does not contain the supporting derivations, lemmas, regularity analysis, or explicit description of the homotopy construction and reduction. In the revised full manuscript we will include: (i) the precise reduction from the composable system (f_1,…,f_n) to a system in the g_j variables, (ii) the construction of the probabilistic symbolic homotopy, (iii) the regularity conditions ensuring the isolated regular solutions are captured, and (iv) the arithmetic complexity analysis establishing the polynomial bound in input size and number of solutions. These additions will allow direct verification of the central claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The abstract presents a structural reduction exploiting the given composable form f_i = h_i(g_1,…,g_n) to obtain an equivalent system in the g_j variables, followed by an independent probabilistic homotopy algorithm whose arithmetic complexity is claimed to be polynomial in input size and number of solutions. No equation, parameter, or complexity expression is defined in terms of a fitted quantity taken from the same data, nor does any step rely on a self-citation chain or uniqueness theorem imported from the authors' prior work. The Chevalley-Shephard-Todd theorem is invoked only for the application to invariant polynomials and is an external result. With only the abstract available and no internal derivation steps shown to reduce by construction to the inputs, the claimed algorithm is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Ledger compiled from abstract statements only; no free parameters or invented entities are introduced in the visible text.

axioms (2)
  • standard math The base field k has characteristic zero.
    Explicitly required by the problem statement in the abstract.
  • domain assumption The target solutions are isolated and regular.
    The algorithm is stated to compute exactly the isolated regular solutions.

pith-pipeline@v0.9.0 · 5788 in / 1243 out tokens · 158481 ms · 2026-05-22T01:35:33.562264+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

40 extracted references · 40 canonical work pages

  1. [1]

    María Emilia Alonso, Eberhard Becker, Marie-François Roy, and Thorsten Wör- mann. 1996. Zeros, multiplicities, and idempotents for zero-dimensional systems. InAlgorithms in algebraic geometry and applications. Springer, 1–15

    work page 1996

  2. [2]

    Saugata Basu and Cordian Riener. 2017. Efficient algorithms for computing the euler-poincaré characteristic of symmetric semi-algebraic sets. InOrdered Alge- braic Structures and Related Topics: International Conference on Ordered Algebraic Structures and Related Topics, October 12–16, 2015, Centre International de Rencon- tres Mathématiques (CIRM), Lumin...

    work page 2017

  3. [3]

    David G Cantor and Erich Kaltofen. 1991. On fast multiplication of polynomials over arbitrary algebras.Acta Informatica28, 7 (1991), 693–701

    work page 1991

  4. [4]

    Claude Chevalley. 1955. Invariants of finite groups generated by reflections. American Journal of Mathematics77, 4 (1955), 778–782

    work page 1955

  5. [5]

    2002.Computational Invariant Theory

    Harm Derksen and Gregor Kemper. 2002.Computational Invariant Theory. Ency- clopaedia of Mathematical Sciences, Vol. 130. Springer

    work page 2002

  6. [6]

    Mohab Safey El Din and Éric Schost. 2017. A nearly optimal algorithm for deciding connectivity queries in smooth and nounded real algebraic sets.J. ACM 63, 6, Article 48 (2017), 37 pages. doi:10.1145/2996450

    work page doi:10.1145/2996450 2017

  7. [7]

    Jean-Charles Faugère, George Labahn, Mohab Safey El Din, Éric Schost, and Thi Xuan Vu. 2023. Computing critical points for invariant algebraic systems. Journal of Symbolic Computation116 (2023), 365–399

    work page 2023

  8. [8]

    Aviezri S Fraenkel and Yaacov Yesha. 1979. Complexity of problems in games, graphs and algebraic equations.Discrete Applied Mathematics1, 1-2 (1979), 15–30

    work page 1979

  9. [9]

    2002.Computers and intractability

    Michael R Garey and David S Johnson. 2002.Computers and intractability. Vol. 29. wh freeman New York

    work page 2002

  10. [10]

    Marc Giusti, J Heintz, K Hägele, Jose E Morais, LM Pardo, and JL Montana. 1997. Lower bounds for Diophantine approximations.Journal of Pure and Applied Algebra117 (1997), 277–317

    work page 1997

  11. [11]

    Marc Giusti, Joos Heintz, Jose Enrique Morais, Jacques Morgenstem, and Luis Miguel Pardo. 1998. Straight-line programs in geometric elimination theory. Journal of pure and applied algebra124, 1-3 (1998), 101–146

    work page 1998

  12. [12]

    Marc Giusti, Joos Heintz, Jose Enrique Morais, and Luis Miguel Pardo. 1995. When polynomial equation systems can be “solved” fast?. InInternational Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes. Springer, 205–231

    work page 1995

  13. [13]

    Marc Giusti, Grégoire Lecerf, and Bruno Salvy. 2001. A Gröbner free alternative for polynomial system solving.Journal of complexity17, 1 (2001), 154–211. doi:10.1006/jcom.2000.0571

    work page doi:10.1006/jcom.2000.0571 2001

  14. [14]

    David Harvey and Joris Van Der Hoeven. 2022. Polynomial multiplication over finite fields in time𝑂(𝑛log𝑛).Journal of the ACM (JACM)69, 2 (2022), 1–40

    work page 2022

  15. [15]

    Jon D Hauenstein, Mohab Safey El Din, Éric Schost, and Thi Xuan Vu. 2021. Solving determinantal systems using homotopy techniques.Journal of Symbolic Computation104 (2021), 754–804

    work page 2021

  16. [16]

    Joos Heintz and Malte Sieveking. 1981. Absolute primality of polynomials is decidable in random polynomial time in the number of variables. InInternational Colloquium on Automata, Languages, and Programming. Springer, 16–28

    work page 1981

  17. [17]

    Gabriela Jeronimo, Guillermo Matera, Pablo Solerno, and Ariel Waissbein. 2009. Deformation techniques for sparse systems.Foundations of Computational Math- ematics9, 1 (2009), 1–50

    work page 2009

  18. [18]

    Erich Kaltofen. 1988. Greatest common divisors of polynomials given by straight- line programs.Journal of the ACM (JACM)35, 1 (1988), 231–264

    work page 1988

  19. [19]

    Erich Kaltofen. 1989. Factorization of polynomials given by straight-line pro- grams.Adv. Comput. Res.5 (1989), 375–412

    work page 1989

  20. [20]

    Teresa Krick and Luis M Pardo. 1996. A computational method for diophantine approximation. InAlgorithms in Algebraic Geometry and Applications, Jean- Charles Faugère and André Galligo (Eds.). Progress in Mathematics, Vol. 143. Springer, Basel, 193–253

    work page 1996

  21. [21]

    George Labahn, Cordian Riener, Mohab Safey El Din, Éric Schost, and Thi Xuan Vu. 2023. Faster real root decision algorithm for symmetric polynomials. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Com- putation. 452–460

    work page 2023

  22. [22]

    2009.Unitary reflection groups

    Gustav I Lehrer and Donald E Taylor. 2009.Unitary reflection groups. Vol. 20. Cambridge University Press

    work page 2009

  23. [23]

    Cordian Riener, Robin Schabert, and Thi Xuan Vu. 2024. Connectivity in sym- metric semi-algebraic sets. InProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation. 162–169

    work page 2024

  24. [24]

    Cordian Riener, Robin Schabert, and Thi Xuan Vu. 2025. Deciding connectivity in symmetric semi-algebraic sets.arXiv preprint arXiv:2503.12275(2025)

    work page arXiv 2025

  25. [25]

    Cordian Riener, Thorsten Theobald, Lina Jansson Andrén, and Jean B Lasserre

    work page

  26. [26]

    Mathematics of Operations Research38, 1 (2013), 122–141

    Exploiting symmetries in SDP-relaxations for polynomial optimization. Mathematics of Operations Research38, 1 (2013), 122–141

    work page 2013

  27. [27]

    Fabrice Rouillier. 1999. Solving zero-dimensional systems through the rational univariate representation.Applicable Algebra in Engineering, Communication and Computing9, 5 (1999), 433–461

    work page 1999

  28. [28]

    Fabrice Rouillier, Marie-Francoise Roy, and Mohab Safey El Din. 2000. Finding at least one point in each connected component of a real algebraic set defined by a single equation.Journal of Complexity16, 4 (2000), 716–750

    work page 2000

  29. [29]

    Mohab Safey El Din and Éric Schost. 2018. Bit complexity for multi-homogeneous polynomial system solving-application to polynomial minimization.Journal of Symbolic Computation87 (2018), 176–206

    work page 2018

  30. [30]

    Arnold Schönhage. 1977. Schnelle Multiplikation von polynomen über Körpern der Charakteristik 2.Acta Informatica7, 4 (1977), 395–398

    work page 1977

  31. [31]

    Arnold Schönhage and Volker Strassen. 1971. Schnelle Multiplikation großer Zahlen.Computing7, 3 (1971), 281–292

    work page 1971

  32. [32]

    Jacob T Schwartz. 1980. Fast probabilistic algorithms for verification of polyno- mial identities.Journal of the ACM (JACM)27, 4 (1980), 701–717

    work page 1980

  33. [33]

    1993.Algorithms in Invariant Theory

    Bernd Sturmfels. 1993.Algorithms in Invariant Theory. Springer-Verlag, Vienna, Austria

    work page 1993

  34. [34]

    2002.Solving Systems of Polynomial Equations

    Bernd Sturmfels. 2002.Solving Systems of Polynomial Equations. CBMS Regional Conference Series in Mathematics, Vol. 97. American Mathematical Society

    work page 2002

  35. [35]

    Joris van der Hoeven and Grégoire Lecerf. 2026. Towards a library for straight- line programs.Applicable Algebra in Engineering, Communication and Computing 37, 2 (2026), 331–387

    work page 2026

  36. [36]

    2013.Modern computer algebra

    Joachim Von Zur Gathen and Jürgen Gerhard. 2013.Modern computer algebra. Cambridge university press

    work page 2013

  37. [37]

    2020.Homotopy algorithms for solving structured determinantal systems

    Thi Xuan Vu. 2020.Homotopy algorithms for solving structured determinantal systems. Ph. D. Dissertation. Sorbonne Université (France); University of Waterloo (Canada)

    work page 2020

  38. [38]

    Thi Xuan Vu. 2022. Computing critical points for algebraic systems defined by hyperoctahedral invariant polynomials. InProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation. 167–175

    work page 2022

  39. [39]

    Thi Xuan Vu. 2025. Computing polynomial representation in subrings of multi- variate polynomial rings. InProceedings of the 2025 International Symposium on Symbolic and Algebraic Computation. 284–292

    work page 2025

  40. [40]

    Éric Schost. 2003. Computing parametric geometric resolutions.Applicable Algebra in Engineering, Communication and Computing13, 5 (2003), 349–393. doi:10.1007/s00200-002-0109-x

    work page doi:10.1007/s00200-002-0109-x 2003