🔢 mathematics

A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems

This paper presents a probabilistic symbolic homotopy algorithm that efficiently computes all isolated regular solutions of polynomial systems with a composable structure by reducing them to simpler systems in the component variables, with key applications to subrings generated by algebraically independent polynomials and invariant rings of finite reflection groups.

Original authors: Thi Xuan Vu

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thi Xuan Vu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, tangled knot of equations. In the world of computer algebra, this is like trying to untangle a ball of yarn where every strand is a complex polynomial equation. Usually, the bigger the knot, the harder it is to untie, and the more time your computer needs to figure out where the ends are.

This paper introduces a clever new way to untie these knots, specifically for a special type of knot called a "composable system."

Here is the simple breakdown of how it works, using some everyday analogies:

The Problem: The "Russian Nesting Doll" Knot

Imagine you have a system of equations that looks like a set of Russian nesting dolls.

The Outer Layer: You have a simple set of rules (let's call them the "Outer Map").
The Inner Layer: Inside those rules, there are other, slightly more complex rules (the "Inner Map").
The Result: When you combine them, you get a huge, complicated equation that looks terrifyingly difficult to solve.

Normally, if you try to solve the final, giant equation directly, your computer has to do a massive amount of work. It's like trying to count every single grain of sand in a beach by looking at the whole beach at once. The complexity explodes because the "degree" (a measure of how twisted the equations are) of the final result is the product of the degrees of all the layers inside.

The Solution: The "Two-Step Detour"

The author, Thi Xuan Vu, proposes a strategy that says: "Don't fight the giant knot. Untie the layers one by one."

Instead of attacking the final, messy equation, the algorithm does two things in order:

Solve the Outer Layer First: It ignores the inner complexity for a moment and solves the simpler "Outer Map." Because this layer is simpler, it's much faster to find the solutions. Think of this as finding the coordinates of the nesting dolls' centers.
Lift the Solutions Up: Once the outer solutions are found, the algorithm uses a mathematical "elevator" (called a homotopy lifting or Newton-Hensel lifting) to pull those solutions back through the inner layer to find the final answers.

The Magic Analogy: The Factory Assembly Line

Think of the problem as a factory assembly line:

The Raw Material: The variables $X$ .
Station A (Inner Map): A machine that processes $X$ into an intermediate product $Y$ .
Station B (Outer Map): A machine that takes $Y$ and turns it into the final product $Z$ .
The Goal: We want to find the specific $X$ that makes $Z$ equal to zero.

The Old Way: You try to reverse-engineer the entire factory at once. You look at the final product and try to guess what the raw material was, accounting for every twist and turn of both machines combined. This is computationally expensive and slow.

The New Way (This Paper):

First, you figure out exactly what the intermediate product $Y$ needs to be to make the final product $Z$ zero. This is easy because Station B is simple.
Then, you take those specific $Y$ values and ask Station A: "What raw material $X$ produces this specific $Y$ ?"
You combine the answers.

Why This is a Big Deal

The paper proves that by doing it this way, the computer doesn't have to deal with the "explosion" of complexity that happens when you multiply the degrees of the equations together.

The Old Cost: If the inner machine has a complexity of 10 and the outer has 10, the old way thinks the job is $10 \times 10 = 100$ times hard.
The New Cost: The new algorithm treats them separately. It does the work for the 10, then the work for the other 10. It's much, much faster.

Where This Applies

The paper highlights two main places where this "nesting doll" structure naturally appears:

Symmetry Groups: In math, when you have equations that look the same no matter how you swap variables (like the symmetric group), the equations often have this composable structure.
Invariant Rings: This is a fancy way of saying "equations that stay the same under certain transformations." Many problems in physics and geometry fall into this category.

The Bottom Line

The author presents a probabilistic algorithm (meaning it uses a bit of randomness to pick the best path, which is a standard and safe technique in this field) that solves these specific types of equations much faster than before.

Instead of trying to climb a mountain by scaling the sheer cliff face (solving the big equation directly), this method finds a hidden trail that goes around the mountain, solving the problem by breaking it into two manageable hills. The result is a significant speedup for computers trying to solve these specific mathematical puzzles.

Technical Summary: A Symbolic Homotopy Algorithm for Solving Composable Polynomial Systems

Problem Statement
The paper addresses the problem of computing the isolated regular solutions of a system of $n$ polynomial equations in $n$ variables, $\mathbf{f} = (f_1, \dots, f_n) \subset k[X_1, \dots, X_n]$ , over a field $k$ of characteristic zero. The focus is specifically on composable polynomial systems, where each equation $f_i$ can be expressed as a composition $f_i = h_i(g_1, \dots, g_n)$ . Here, $\mathbf{g} = (g_1, \dots, g_n)$ represents an inner polynomial map and $\mathbf{h} = (h_1, \dots, h_n)$ an outer polynomial map.

Directly solving $\mathbf{f} = 0$ is generally NP-hard, and standard symbolic algorithms often incur complexity dependent on the Bézout bound of the composed system, $\prod \deg(f_i)$ . Since $\deg(f_i)$ can be significantly larger than the degrees of the constituent maps $\mathbf{h}$ and $\mathbf{g}$ (due to composition), solving the system directly is computationally expensive. The paper targets scenarios where the algebraic structure of $\mathbf{f}$ as $\mathbf{h} \circ \mathbf{g}$ can be exploited to reduce this cost. Key applications include systems where $\mathbf{f}$ belongs to a subring generated by algebraically independent polynomials, and systems of invariant polynomials under finite reflection groups (e.g., symmetric groups $S_n$ , hyperoctahedral groups $B_n$ , and exceptional groups), where the invariant ring is a polynomial algebra generated by $\mathbf{g}$ .

Methodology
The proposed approach decomposes the solution process into two stages, leveraging the compositional structure $\mathbf{f} = \mathbf{h} \circ \mathbf{g}$ :

Solving the Outer System: The algorithm first solves the system $\mathbf{h}(\mathbf{Y}) = 0$ in the intermediate variables $\mathbf{Y}$ . This is achieved using a probabilistic symbolic homotopy algorithm (Homotopy_Nonsingular).
- It constructs a "start system" $\mathbf{p}$ consisting of products of random linear forms, which is easily solvable.
- A homotopy $\mathbf{r}(\mathbf{Y}, T) = (1-T)\mathbf{p}(\mathbf{Y}) + T\mathbf{h}(\mathbf{Y})$ deforms the start system to the target system.
- A global Newton-Hensel lifting procedure (GLS_Lifting) lifts the solutions of the start system along the homotopy curve to obtain a zero-dimensional parametrization (specifically a Rational Univariate Representation or Geometric Resolution) of the regular solutions of $\mathbf{h} = 0$ .
- Singular points are removed using a dedicated procedure.
Lifting through the Inner Map: Once the solutions of $\mathbf{h} = 0$ are parametrized as $\mathbf{Y} = \mathbf{v}(T)$ , the problem reduces to solving $\mathbf{g}(\mathbf{X}) = \mathbf{v}(T)$ .
- The algorithm treats this as a parametric system in variables $\mathbf{X}$ and parameter $T$ .
- It computes a geometric resolution of the fiber at a random point $s_0$ and then applies a parametric Newton-Hensel lifting scheme (Parametric) to lift these solutions to a parametrization over the variable $T$ up to a required precision.
- Rational function reconstruction is used to recover exact polynomial parametrizations.
Merging and Finalizing: The parametrizations of the outer and inner systems are combined. The system is reduced to finding the intersection of the homotopy curve of the outer system and the lifted curve of the inner system. A final geometric resolution is computed for the combined variables, and singular points are filtered out to yield the isolated regular solutions of the original system $\mathbf{f} = 0$ .

Key Contributions and Results

Algorithm: The paper presents a randomized (Monte Carlo) algorithm, Solve_h_circ_g, that computes a geometric resolution of the isolated regular solutions of composable systems.
Complexity Bounds: The primary theoretical result is that the arithmetic complexity is softly polynomial in the input size (specifically the lengths of the Straight-Line Programs, $L_\mathbf{h}$ $L_{h}$ and $L_\mathbf{g}$ $L_{g}$ ) and in quantities related to the degrees of the inner and outer maps separately, rather than their composition.
- Let $C = \prod \deg(h_i)$ (bound on solutions of outer system) and $D = \prod \deg(g_i)$ (bound on solutions of inner system).
- Let $E = \prod (\deg(h_i) + 1)$ and $J = \prod (\deg(g_i) + 1)$ .
- The complexity is $O^\sim(n(L_\mathbf{h} + L_\mathbf{g} + n^2(\gamma + \sigma))(CE + DJ + DC))$ , where $\gamma$ and $\sigma$ are the maximum degrees of $\mathbf{h}$ and $\mathbf{g}$ respectively.
Comparison to Direct Solving: In contrast, solving $\mathbf{f} = 0$ directly would typically depend on the Bézout bound $\prod \deg(f_i)$ , which can be exponentially larger than $C$ or $D$ . The proposed method achieves substantial savings by decoupling the complexity of the inner and outer maps.
Generality: The method handles systems where $\mathbf{f}$ is invariant under finite reflection groups, as their invariant rings are polynomial algebras generated by algebraically independent polynomials.

Significance and Claims
The paper claims that the main novelty lies in the structured decomposition of the problem. While homotopy lifting and geometric resolutions are classical tools, their combination with compositional structure to obtain complexity bounds depending separately on the inner and outer maps has not been previously exploited.

The authors state that this approach demonstrates that exploiting algebraic structure can substantially reduce the cost of symbolic polynomial system solving. The paper does not claim to solve singular or positive-dimensional components in its primary algorithm (though it notes that minor modifications can handle isolated singular points). It emphasizes that the algorithm is probabilistic, relying on random choices from Zariski open sets to ensure correctness with high probability.

The paper concludes by noting that while the theoretical complexity is favorable, practical efficiency requires further implementation work, particularly regarding Straight-Line Programs, and suggests future directions such as handling positive-dimensional components, developing sparse variants, and applying the framework to invariant theory, optimization, and multivariate cryptography.