A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems

Thi Xuan Vu

A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems

T0 review · 1 major / 0 minor · reviewed 2026-05-22 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict The abstract sketches a reduction to exploit composable structure before symbolic homotopy, claiming polynomial complexity, but without the full paper the claim cannot be checked. read the letter →

arxiv 2605.22514 v1 pith:6RWN5DRS submitted 2026-05-21 cs.SC math.ACmath.AG

Thi Xuan Vu This is my paper · ORCID

classification cs.SCmath.ACmath.AG

keywords composablepolynomialsystemssymbolichomotopyisolatedregularsolutionsprobabilisticalgorithmfinitereflectiongroupsinvariantpolynomialsChevalley-Shephard-Toddtheoremalgebraicindependence

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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.

Watch

Extended reading notes

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

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.

Editorial extensions

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.

Reading between the lines

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main point is that this abstract describes a probabilistic algorithm for isolated regular solutions of composable polynomial systems: each f_i is written as a composition h_i of the g_j's, the system is reduced in the g variables, and then symbolic homotopy is applied, with arithmetic complexity stated to be polynomial in input size and number of solutions. The reduction step that uses the explicit composable form looks like the actual algorithmic novelty relative to plain symbolic homotopy methods. The paper also does a clear job linking the idea to concrete settings, especially invariant rings of finite reflection groups via the Chevalley-Shephard-Todd theorem, with examples such as S_n, B_n, dihedral groups, and the exceptional groups E6 through H4. That connection is useful because those systems really do arise in practice and have the required algebraic independence of the g's. The reduction therefore targets a recurring structure rather than a generic dense system. The soft spots are straightforward and stem directly from the fact that only the abstract is available. The polynomial complexity bound is asserted but no derivation, lemmas on solution preservation, or handling of regularity conditions appear, so it is impossible to see whether the reduction step introduces hidden costs or fails on certain inputs. The central assumption that the system is composable is taken as given, which is fine for the intended class but leaves open how often real problems satisfy it exactly. No circularity or invented quantities are visible in what is shown. This paper is for researchers in symbolic computation and algebraic geometry who routinely solve structured polynomial systems, particularly those coming from invariant theory or symmetry. A reader who already works with homotopy continuation or needs speed-ups on reflection-group invariants would find the targeted reduction worth examining if the details hold. It deserves a serious referee because the idea addresses a practical bottleneck with a plausible structural shortcut and cites the right background theorems. I recommend sending it to peer review so the full algorithm, proofs, and complexity analysis can be evaluated by experts who can test the claims on examples.

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)

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

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

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

assumptions (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.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems." pith.science (2026). https://pith.science/paper/6RWN5DRS

@misc{pith2026260522514,
  author       = {Pith},
  title        = {Pith review of: A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6RWN5DRS}},
  note         = {Machine review of arXiv:2605.22514}
}

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\).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

[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]

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]

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]

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

work page 1955
[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]

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]

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]

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

Show all 40 references

[9]

2002.Computers and intractability

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

2002
[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

1997
[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

1998
[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

1995
[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

2001 doi
[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

2022
[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

2021
[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

1981
[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

2009
[18]

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

1988
[19]

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

1989
[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

1996
[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

2023
[22]

2009.Unitary reflection groups

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

2009
[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

2024
[24]

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

2025
[25]

Cordian Riener, Thorsten Theobald, Lina Jansson Andrén, and Jean B Lasserre
[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

2013
[27]

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

1999
[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

2000
[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

2018
[30]

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

1977
[31]

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

1971
[32]

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

1980
[33]

1993.Algorithms in Invariant Theory

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

1993
[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

2002
[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

2026
[36]

2013.Modern computer algebra

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

2013
[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)

2020
[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

2022
[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

2025
[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

2003 doi

Pith tools

Reviewed May 22, 2026 · model on record in the stance chip above.

[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