🔢 mathematics

Elimination Without Eliminating: Computing Complements of Real Hypersurfaces Using Pseudo-Witness Sets

This paper introduces a novel method for computing the real complement regions of hypersurfaces defined by projections, utilizing pseudo-witness sets and univariate interpolation to bypass the computationally expensive step of deriving explicit defining equations.

Original authors: Paul Breiding, John Cobb, Aviva K. Englander, Nayda Farnsworth, Jonathan D. Hauenstein, Oskar Henriksson, David K. Johnson, Jordy Lopez Garcia, Deepak Mundayur

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Paul Breiding, John Cobb, Aviva K. Englander, Nayda Farnsworth, Jonathan D. Hauenstein, Oskar Henriksson, David K. Johnson, Jordy Lopez Garcia, Deepak Mundayur

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 standing in a vast, foggy field. In the middle of this field, there is a mysterious, invisible wall. You can't see the wall, and you don't know the mathematical formula that describes its shape. However, you know that this wall divides the field into different "rooms" or regions.

Your goal is to map out these rooms: How many are there? Where are they? If you drop a ball in a specific spot, which room will it end up in?

Usually, to solve this, mathematicians would try to write down the exact equation of the wall first. But in complex real-world problems (like how a robot arm moves or how a population of animals grows), writing down that equation is like trying to solve a 10,000-piece puzzle while blindfolded. It takes too long, or it's impossible with current computers.

This paper introduces a clever trick: "Elimination Without Eliminating."

Instead of trying to write down the formula for the wall, the authors propose a method to explore the rooms by poking the wall with a stick.

The Core Idea: The "Stick" and the "Shadow"

Think of the invisible wall as a shadow cast by a 3D object (like a sculpture) onto a 2D floor.

The Problem: You want to map the shadow on the floor, but you don't know the shape of the shadow itself. You only know the rules for how the 3D sculpture is built.
The Old Way: Try to calculate the exact shape of the shadow from the sculpture's rules. This is the "elimination" step, and it's computationally heavy.
The New Way: Instead of calculating the whole shadow, just shine a laser pointer (a straight line) through the sculpture. Where the laser hits the shadow, you get a few points. By moving the laser around, you can figure out the shape of the shadow without ever writing down its full equation.

How the Algorithm Works (The "Routing" Game)

The authors use a concept called a Routing Function. Imagine you are a hiker in our foggy field, and you want to find the "rooms" separated by the wall.

The Hiker's Compass: The algorithm creates a special "compass" (the routing function). This compass points toward the wall but gets weaker as you get further away. It has "peaks" and "valleys" (critical points) in every room.
Finding the Peaks: To find the rooms, the algorithm looks for the "peaks" of this compass.
- The Challenge: To find a peak, you usually need the formula for the wall to know how the compass behaves.
- The Trick: The authors realized they don't need the formula. They can use the Pseudo-Witness Set. This is a data structure that acts like a "black box." You give it a location, and it tells you: "If you shine a line here, the wall intersects at these specific points."
The Magic Math: Using these intersection points, the algorithm can mathematically "guess" the slope and curvature of the wall at that spot. It's like feeling the texture of a wall with your hands to guess its shape, rather than seeing a blueprint.
Connecting the Dots: Once the algorithm finds the "peaks" (critical points) in each room, it uses a "gradient flow" (imagine water flowing downhill) to see which peaks are connected. If water flows from Peak A to Peak B, they are in the same room.

Real-World Examples from the Paper

The authors tested this on three tricky problems:

The Kuramoto Model (Synchronized Fireflies): Imagine a swarm of fireflies trying to sync their blinking. The "wall" represents the boundary where the fireflies stop syncing and start flashing randomly. The algorithm mapped out the different "sync zones" without needing the complex math that usually describes this boundary.
The 3RPR Robot Arm: Think of a robot arm with three legs. Sometimes, it can get stuck in a weird pose, or it can switch between two different ways of holding an object without breaking. The "wall" is the boundary where this switch happens. The algorithm found all the safe zones where the robot can move freely, even though writing the equation for that boundary would take days.
The Allee Effect (Population Dynamics): Imagine a species of animals. If there are too few, they die out. If there are too many, they starve. There's a "Goldilocks zone" where they thrive. The algorithm mapped out the different scenarios (how many animals can survive) based on their migration rates and food limits, again without solving the impossible equation.

Why This Matters

This paper is a breakthrough because it changes the rules of the game.

Before: "I can't solve this problem because I can't write the equation."
Now: "I can solve this problem by just poking the system with a line and watching where it breaks."

It allows scientists and engineers to explore complex systems—like climate models, biological networks, or robotic movements—that were previously too difficult to analyze because the math was too heavy. They can now navigate the "foggy field" and find all the rooms, even if they never see the walls clearly.

In short: They found a way to map a maze by feeling the walls with a stick, rather than trying to draw the whole maze on paper first.

1. Problem Statement

In algebraic geometry, many important hypersurfaces (such as discriminants) arise as the Zariski closure of the projection of a higher-dimensional variety. A central challenge in analyzing these objects is understanding the topology of their real complement (the space $\mathbb{R}^n \setminus H$ ), which is partitioned into open regions where the defining polynomial $h$ maintains a constant sign.

The Core Difficulty:
Existing numerical methods for computing these regions (specifically those using routing functions) require an explicit defining polynomial $h$ as input. However, obtaining $h$ via symbolic elimination (e.g., Gröbner bases or resultants) is often computationally intractable or impossible for moderate-to-large systems. This creates a bottleneck where the geometry of the hypersurface is known (via a parametric system), but its defining equation is not, preventing the application of powerful topological analysis tools.

2. Methodology

The authors propose a method to compute the regions of the real complement without ever computing the defining polynomial $h$ . The approach relies on Numerical Algebraic Geometry and Pseudo-Witness Sets.

A. The Routing Function Framework

The method builds upon the concept of routing functions ( $r$ ), which are rational functions designed to have critical points in every connected component of the complement.
$r(x) = \frac{|h(x)|}{(1 + \|x - c\|^2)^e}$
where $c$ is a generic point and $e > \deg(h)/2$ .

Standard Approach: Requires explicit $h$ to compute $\nabla r$ and $\text{Hess}(r)$ to find critical points and connect them via gradient flow.
New Approach: The authors observe that to compute routing points and their connectivity, one only needs:
1. The degree of $h$ ( $\deg h$ ).
2. The ability to evaluate $\nabla h$ and $\text{Hess}(h)$ at arbitrary points (up to scaling).

B. Pseudo-Witness Sets

Instead of $h$ , the hypersurface $H$ is represented by a pseudo-witness set. If $H = \pi(X)$ (the projection of a variety $X$ defined by $F$ ), a pseudo-witness set is a quadruple $(F, \pi, L \times L_1, W)$ , where:

$L$ is a generic line in the parameter space.
$L_1$ is a generic linear subspace in the fiber.
$W = X \cap (L \times L_1)$ is a finite set of points.
Projecting $W$ yields the intersection $H \cap L$ .

C. "Elimination Without Eliminating" (Theoretical Core)

The paper's main theoretical contribution is Theorem 3.8, which demonstrates how to compute the gradient and Hessian of $\log|h|$ using only the data from a single pseudo-witness set (intersection with one line).

Mechanism: By parameterizing the line $L$ passing through a point $p$ and analyzing the roots $t_j$ of the intersection $h(p+tb)=0$, the authors derive that:
$\nabla_p \log|h(p)| = -\sum_{j=1}^{\deg h} \nabla_b s_j(p,b)$
where $s_j = 1/t_j$ .
Implementation: The gradients and Hessians of the roots $s_j$ with respect to the direction vector $b$ are computed by solving linear systems derived from the Implicit Function Theorem applied to the defining system $F$ . This allows the evaluation of $\nabla r$ and $\text{Hess}(r)$ without knowing the symbolic form of $h$ .

D. The Algorithm (Algorithm 4)

Compute Pseudo-Witness Set: Determine the degree of $H$ and find the intersection points with a generic line.
Construct Routing Function: Define $r$ using the computed degree.
Compute Critical Points: Use Homotopy Continuation and Monodromy to solve $\nabla \log r = 0$ . Crucially, the evaluation of the Jacobian and Hessian during the homotopy steps uses the pseudo-witness set formulas (Algorithm 3) rather than symbolic derivatives.
Connect Components: Use Gradient Flow and the Mountain Pass Theorem to connect critical points of index 0 via unstable directions of higher-index points, thereby identifying the connected components (regions).

3. Key Contributions

Elimination-Free Computation: The first algorithm to compute the regions of a real hypersurface complement defined by a projection without symbolic elimination.
Efficient Derivative Evaluation: A novel method (Theorem 3.8) to compute gradients and Hessians of an unknown polynomial using a single line intersection, drastically reducing the complexity compared to previous methods that required multiple lines or full implicitization.
Numerical Robustness: The use of logarithmic routing functions ( $\log r$ ) and pseudo-witness sets allows for stable numerical computation even when the defining equation is too complex to write down.
Handling Non-Irreducibility: The paper addresses the issue of non-reduced witness sets (where components have multiplicities) and discusses strategies (like deflation or computing radicals) to handle cases where the projection is not a simple hypersurface.

4. Results and Case Studies

The authors implemented the method in a forthcoming Julia package and validated it on three complex applications:

Kuramoto Model (3 Oscillators):
- Problem: Analyze the discriminant of a synchronization model (degree 12, 41 terms).
- Result: Successfully identified 9 connected regions in the parameter space, matching known symbolic results, without using the discriminant polynomial.
3RPR Mechanism (Kinematics):
- Problem: Analyze assembly-mode changes in a parallel robot.
- Result:
  - 2-parameter case: Found all 8 regions (degree 12 curve).
  - 3-parameter case (fixed $c_3$ ): Found 9 regions (degree 12 surface).
  - 3-parameter case (variable $c_3$ ): The symbolic polynomial has 455 terms and is intractable. The method found 90 real critical points (out of 457 complex) and verified regions with root counts 2, 4, and 6. The monodromy step was computationally intensive (14 days), highlighting current limits but proving feasibility.
Allee Effect (Population Ecology):
- Problem: Determine non-negative steady states in a 3-patch population model.
- Challenge: The discriminant is not irreducible, and the defining equations yield a non-reduced pseudo-witness set.
- Result: The method initially computed the "reduced" part of the discriminant. By symbolically computing the radical of the ideal (using OSCAR) to create a reduced witness set, the authors successfully recovered the full discriminant structure, matching previous results obtained via Cylindrical Algebraic Decomposition (CAD).

5. Significance

This work bridges a critical gap between symbolic algebra (which provides exact equations but fails on complexity) and numerical algebraic geometry (which handles complexity but traditionally requires explicit equations).

Practical Impact: It enables the topological analysis of high-dimensional parameter spaces in engineering, physics, and biology where the governing equations are known, but the conditions for singularities (discriminants) are too complex to derive symbolically.
Theoretical Advancement: It reframes "elimination" not as a symbolic process of finding an equation, but as a numerical process of extracting geometric data (degree, gradients, Hessians) directly from the projection structure.
Future Directions: The authors note that while the method is powerful, the computational cost of monodromy loops remains a bottleneck for very high-degree systems. Future work involves optimizing the start solution generation and handling non-reduced components more robustly within the numerical framework.