🔢 mathematics

Engineered Complete Intersections: Algorithmic Aspects

This paper presents new algorithmic techniques and a software implementation for efficiently counting and solving Engineered Complete Intersection (ECI) systems via generalized tropical mixed subdivisions and homotopy continuation, while also providing methods to compute Newton polytopes of their eliminants and $A$ -discriminants.

Original authors: Alexander Esterov, Rafael Mohr, Yulia Mukhina

Published 2026-07-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander Esterov, Rafael Mohr, Yulia Mukhina

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 a detective trying to solve a mystery, but instead of fingerprints or footprints, your clues are equations. In the world of mathematics, specifically a field called algebraic geometry, scientists study the shapes that appear when you solve systems of polynomial equations. These shapes can be simple points, twisting curves, or complex, multi-dimensional surfaces. The challenge is that these equations often have too many variables or are too messy to solve with a pen and paper. To crack the code, mathematicians use a special tool called "tropical geometry." Think of this as a way to translate a complicated, curvy landscape into a rigid, blocky city made of straight lines and sharp corners. It's like turning a high-definition photograph into a pixelated image; you lose some of the smooth details, but the overall structure becomes much easier to count and measure. This is crucial because knowing the "shape" of the solution helps scientists predict how many answers a system has, which is vital for everything from designing chemical factories to understanding how the universe is built.

This paper introduces a new, super-efficient way to build these blocky maps for a specific, tricky class of equations called "Engineered Complete Intersections" (ECIs). These aren't just random equations; they are carefully constructed systems that pop up in real-world problems, like modeling how chemicals react in a beaker or finding the critical points where a surface changes shape. The authors, Alexander Esterov, Rafael Mohr, and Yulia Mukhina, have developed a set of algorithms that act like a high-speed GPS for these blocky cities. Instead of getting lost in the math, their method "tropicalizes" these systems, breaking them down into manageable pieces called "mixed subdivisions." They created a software package that can quickly count how many solutions exist and even figure out the exact shape of the resulting equations, doing so much faster than previous methods. In a fun twist, they used their own tools to prove that it's possible to build a specific 3D shape where every single "cusp" (a sharp pointy bit) is a real, physical object, not just a mathematical ghost.

The Detective's New Toolkit

The core of this work is about solving a specific type of puzzle. Imagine you have a set of rules (equations) that describe how different ingredients mix. In many scientific fields, like chemistry, these rules are "engineered" in a special way: the coefficients (the numbers multiplying the variables) aren't random; they are linked together in a fixed pattern. The authors call these Engineered Complete Intersections. While mathematicians have known how to count solutions for simpler systems for decades, these engineered ones were harder to crack because their structure was too complex for old tools.

The paper presents a new algorithmic approach to "tropicalize" these systems. In plain English, this means taking the complex, curvy equations and converting them into a simpler, piecewise-linear structure (like a map made of straight roads and intersections). The authors generalize a classic idea called a "mixed subdivision"—which is like a jigsaw puzzle where each piece represents a possible solution—to work specifically with these engineered systems.

How the Algorithm Works
The team designed a "tropical homotopy continuation" algorithm. You can think of this as a hiker walking through a mountain range. The hiker starts at a known, easy-to-understand location (a simple set of equations) and walks along a path toward the complex, unknown destination (the engineered system). As the hiker walks, they constantly check the terrain. Every time they cross a ridge or a valley (a mathematical "facet"), the map they are holding gets updated. The authors' innovation is that they figured out exactly how to update the map instantly when crossing these ridges, without having to redraw the whole thing from scratch. This allows them to efficiently count the total number of solutions (the "mixed volume") and find the specific coordinates of the solutions.

Real-World Testing
The authors didn't just write the math; they built a software package in the Julia programming language to test it. They ran their algorithms on real-world examples, including:

Chemical Reaction Networks: They tested systems describing how chemicals react, some with up to 42 variables. Their method solved these in seconds, whereas previous methods took minutes or even hours.
A-Discriminants: These are special polynomials that tell you when a system of equations has a "singular" point (like a sharp corner or a self-intersection). The authors used their tool to compute the shapes (Newton polytopes) of these discriminants for various complex sets of data, showing their method is competitive with or faster than existing specialized techniques.

The "Real" Cusp Discovery
One of the most playful results in the paper involves "real patchworking." This is a technique to determine not just how many solutions exist, but where they are located in the real world (as opposed to imaginary numbers). The authors combined their counting algorithm with this technique to prove a specific mathematical fact: they constructed a 4th-degree polynomial in three variables where all 24 of its "cusp" singularities (the sharpest points on the curve) are real numbers. They found this by randomly generating thousands of potential shapes until they found one that fit the criteria, a process that took a fraction of a second per attempt but required about 13,000 tries to find the perfect match.

Limitations and Confidence
The authors are very clear about what their tools can and cannot do. Their algorithms are proven to work for "generic" cases, meaning systems where the numbers aren't specially tuned to break the math. They explicitly note that for extremely large systems (like one with 86 variables), their current method might struggle because the initial step of creating a "regular triangulation" (the starting map) can take too long. They also mention that their software relies on floating-point arithmetic (using decimals), which can sometimes lead to rounding errors when the numbers get huge, though they suggest this can be fixed by switching to exact calculations if needed.

In summary, this paper provides a new, faster, and more flexible way to navigate the complex landscapes of engineered polynomial systems. By turning these abstract math problems into walkable, blocky maps, the authors have given scientists a better toolkit for counting solutions and understanding the shapes of the equations that govern our physical world.

Technical Summary: Engineered Complete Intersections: Algorithmic Aspects

Problem Statement

The paper addresses the computational challenges associated with Engineered Complete Intersections (ECIs), a class of sparse polynomial systems arising in enumerative geometry and applications such as chemical reaction networks. An ECI is defined by a finite multiset $A \subset \mathbb{Z}^n$ and a matrix $V \in \mathbb{C}^{k \times A}$ of rank $k$ , generating a parametric Laurent polynomial system where coefficients depend linearly on symbolic parameters.

While the tropical geometry of generic systems with fixed Newton polytopes is well-understood (relying on mixed subdivisions and the BKK theorem), ECIs present a distinct structure where equations are coupled via a fixed linear dependency. The primary problems tackled are:

Root Counting and Solving: Efficiently computing the number of solutions (mixed volume) and finding numerical solutions for square, zero-dimensional ECIs.
Real Root Counting: Determining the number of real solutions for ECIs depending on a single parameter.
Elimination: Computing the Newton polytope of the eliminant (e.g., A-discriminants) of an ECI without resorting to computationally expensive Gröbner basis elimination.

Methodology

The authors build upon the theoretical framework established in [Est24; Est25], which generalizes the polyhedral framework of [Ber75; Kho95; Kou76] to ECIs using conewise linear functions derived from the matroid structure of the matrix $V$ .

1. Tropical Homotopy Continuation for Mixed Subdivisions

The core algorithmic contribution is a tropical homotopy continuation algorithm designed to compute mixed subdivisions of Matroid Complete Intersections (MCIs), the combinatorial abstraction of ECIs.

Mechanism: The algorithm tracks a mixed subdivision along a linear path in the space of height vectors ( $d \in \mathbb{R}^A$ ).
Wall Walking: When the path crosses a facet of a "mixed cell cone" (a polyhedral cone defining the region where a specific mixed cell is a dual tropical root), the subdivision is updated. This update, termed WallWalk, modifies the current mixed cells by replacing them with new cells derived from the matroid quotient and affine circuits, avoiding the need to recompute the entire subdivision from scratch.
Initialization: To start the homotopy, the algorithm deforms the target MCI into a "uniform" MCI (associated with a regular triangulation of the support set $A$ ), for which the mixed subdivision is trivial to compute.

2. Real Patchworking via Linear Algebra over $\mathbb{F}_2$

To count real solutions, the paper adapts real patchworking techniques.

Reduction: For a generic height vector, the number of real solutions of the ECI is the sum of the real solutions of the "cancellation" systems associated with each dual tropical root (mixed cell).
Simplicial Supports: The cancellation systems have supports consisting of mutually transversal simplices. The paper proves that counting real solutions for such systems reduces to solving a linear system over the finite field $\mathbb{F}_2$ .
Algorithm: The number of real solutions is determined by the dimension of the kernel of a specific $\mathbb{F}_2$ -linear map $\Lambda$ constructed from the signs of the cofactors of the system's coefficient matrices.

3. Effective Tropical Elimination

The paper provides an algorithm to compute the Newton polytope of the eliminant of an ECI (e.g., an A-discriminant).

Vertex Oracle: Using the theory of moving sets and mixed volumes, the authors derive a formula to compute the support function of the eliminant's Newton polytope.
Implementation: This formula allows for the construction of a vertex oracle (a function that returns the vertex maximizing a given covector). By combining this oracle with the algorithm from [Hug06], the full Newton polytope can be reconstructed.
Efficiency: This approach avoids the direct computation of the full tropicalization of the input system, which can be prohibitively large.

Key Contributions

Generalization of Mixed Subdivisions: The authors successfully transport the notion of mixed subdivisions from collections of polytopes to ECIs/MCIs, defining "mixed cells" in terms of matroid circuits and affine independence.
Tropical Homotopy Algorithm: A practical algorithm (Algorithm 1 and 2) is presented to compute these mixed subdivisions. It generalizes techniques from [Jen16; Mal17] to the ECI setting, enabling the efficient tracking of subdivisions along homotopy paths.
Real Root Counting Procedure: An algorithmic method is established to count real solutions of ECIs by reducing the problem to linear algebra over $\mathbb{F}_2$ , leveraging the specific structure of the cancellation systems.
Newton Polytope Computation: An effective formula and algorithm (Algorithm 3) are provided to compute the vertices of the Newton polytope of eliminants, specifically targeting A-discriminants.

Results and Experimental Evaluation

The authors implemented their algorithms in a Julia package (MCISubdivisions.jl) using the Oscar computer algebra system. Experimental results demonstrate:

Chemical Reaction Networks: The algorithm computes mixed volumes for ECIs derived from chemical reaction networks (up to ~40 variables) significantly faster than previous methods described in [HHR24] and [Fel+26]. For example, a 9-site reaction network was solved in 3.1 seconds compared to ~262 seconds in prior work.
Real Patchworking Application: The authors computationally proved the existence of a degree 4 hypersurface in 3 variables where all 24 cusp singularities of its discriminant curve are real. This was achieved by sampling dual tropical roots and verifying the real root count of the associated cancellation systems.
A-Discriminants: The algorithm successfully computed Newton polytopes for A-discriminants of various sets $A$ . In several cases (e.g., $A_1, A_2$ ), the computation time was comparable to or faster than the tropical implicitization techniques described in [RST25].
Limitations: The authors note that for very large systems (e.g., 86 variables), the initial step of computing a regular triangulation (required for initialization) can fail to terminate within reasonable timeframes. Additionally, numerical rounding errors can occur in Algorithm 3 due to the large disparity in magnitude between entries in the support sets, though this is acknowledged as a potential area for exact arithmetic refinement.

Significance

The paper claims significance by providing the first effective algorithmic toolkit for the tropical geometry of Engineered Complete Intersections. By generalizing mixed subdivisions and homotopy continuation to this specific class of systems, the work enables:

Efficient Numerical Solving: Optimized homotopy methods for square ECI systems.
Real Algebraic Geometry: A practical method to count real solutions in contexts where standard methods are intractable.
Elimination Theory: A new, efficient pathway to compute Newton polytopes of eliminants (like A-discriminants) that bypasses the computational bottlenecks of traditional elimination techniques.

The work bridges the gap between the theoretical combinatorial descriptions of ECIs found in [Est24; Est25] and practical, implementable algorithms, demonstrating feasibility on problems of practical interest in chemical kinetics and algebraic geometry.