pith. sign in

arxiv: 2601.04383 · v2 · submitted 2026-01-07 · 🧮 math.AG · cs.NA· math.NA

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

Paul Breiding , John Cobb , Aviva K. Englander , Nayda Farnsworth , Jonathan D. Hauenstein , Oskar Henriksson , David K. Johnson , Jordy Lopez Garcia
show 1 more author
Deepak Mundayur
This is my paper

Pith reviewed 2026-05-16 15:53 UTC · model grok-4.3

classification 🧮 math.AG cs.NAmath.NA
keywords real hypersurfacescomplementspseudo-witness setseliminationnumerical algebraic geometrydiscriminantsregionsprojections
0
0 comments X

The pith

Intersections with generic lines via pseudo-witness sets recover all regions in the real complement of a hypersurface without its equation.

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

The paper shows how to partition space into the open regions separated by a real hypersurface by sampling its intersections with generic lines. Because the hypersurface is given only as a projection, the authors avoid computing its explicit polynomial by using pseudo-witness sets that encode the necessary univariate data directly. This reduces the global complement problem to repeated univariate root-finding along lines, which is feasible even when elimination is intractable. A reader would care because many algebraic objects of interest, such as discriminants, appear only implicitly and their real geometry has previously been hard to access.

Core claim

The real complement of a hypersurface arising as a projection can be recovered by computing the real intersection points and multiplicities of the hypersurface with sufficiently many generic lines; these intersections are obtained from pseudo-witness sets, which supply the elimination information without ever producing a defining equation for the hypersurface.

What carries the argument

pseudo-witness sets for generic line sections, which encode the intersection data of the hypersurface with a line and permit counting real roots with multiplicity

If this is right

  • The method applies directly to discriminants and resultants given only by their defining ideals.
  • Connected components of the complement can be certified numerically without symbolic Gröbner bases or resultants.
  • The same line-sampling idea yields a practical algorithm implemented in a forthcoming Julia package.
  • All regions are recovered accurately on the tested examples, including cases where the explicit equation is infeasible.

Where Pith is reading between the lines

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

  • The technique may extend to computing real topology of higher-codimension varieties by intersecting with generic planes instead of lines.
  • It could be combined with existing numerical trackers to certify the number of chambers for larger projections.
  • One could test whether the same pseudo-witness data also determines the Euler characteristic or other topological invariants of the complement.

Load-bearing premise

Pseudo-witness sets computed for generic lines will always detect every real intersection point and its multiplicity without missing any components of the hypersurface.

What would settle it

Apply the algorithm to a hypersurface whose equation is known explicitly, compute the regions both ways, and check whether any real root or connected component of the complement is missed on some tested line.

Figures

Figures reproduced from arXiv: 2601.04383 by Aviva K. Englander, David K. Johnson, Deepak Mundayur, John Cobb, Jonathan D. Hauenstein, Jordy Lopez Garcia, Nayda Farnsworth, Oskar Henriksson, Paul Breiding.

Figure 1
Figure 1. Figure 1: During this computation, our algorithm never has direct access to the polynomial h. ♢ [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A witness set for the red curve X “ V pFq with F as in Example 3.3. The witness set is given by the intersection of the red curve X with the green linear space M. The intersection consists of the two points labeled W. It is important to note that the defining equations for X are not used in Definition 3.2; instead, X is represented using F. This can potentially introduce multiplicities, which is why we hav… view at source ↗
Figure 3
Figure 3. Figure 3: The left picture illustrates a pseudo-witness set for the purple projection [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Routing points and connecting paths for the discriminant of the Kuramoto model with three oscillators [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An example of a 3RPR mechanism. A fundamental problem is to determine all the ways a real motion of the mechanism can start and end in the same “home” configuration for a fixed set of leg lengths. The configuration variables are pp, ϕq “ pp1, p2, ϕ1, ϕ2q, where p “ pp1, p2q represents the translation of the platform and ϕ “ pϕ1, ϕ2q is a unit circle representation of its rotation. This yields a polynomial … view at source ↗
Figure 6
Figure 6. Figure 6: Routing points and connecting paths for the two-parameter version of the 3RPR system. The right picture [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Contours and critical points of a routing function for the modified discriminant ∆ [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
read the original abstract

Many hypersurfaces in algebraic geometry, such as discriminants, arise as the projection of another variety. The real complement of such a hypersurface partitions its ambient space into open regions. In this paper, we propose a new method for computing these regions. Existing methods for computing regions require the explicit equation of the hypersurface as input. However, computing this equation by elimination can be computationally demanding or even infeasible. Our approach instead derives from univariate interpolation by computing the intersection of the hypersurface with a line. Such an intersection can be done using so-called pseudo-witness sets without computing a defining equation for the hypersurface - we perform elimination without actually eliminating. We implement our approach in a forthcoming Julia package and demonstrate, on several examples, that the resulting algorithm accurately recovers all regions of the real complement of a hypersurface.

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

2 major / 1 minor

Summary. The manuscript proposes a numerical method to compute the connected components of the complement of a real hypersurface in R^n. Instead of performing symbolic elimination to obtain an explicit defining equation, the approach intersects the hypersurface with generic lines and recovers the real roots and their multiplicities via pseudo-witness sets; these data are then used to subdivide each line into intervals belonging to distinct regions of the complement. The method is implemented in a forthcoming Julia package and is illustrated on several examples.

Significance. If the pseudo-witness-set computations on generic lines reliably recover exact real roots together with correct parities of multiplicities, the technique would provide a practical route to real-complement computations in regimes where symbolic elimination is infeasible, such as high-degree discriminants or projections of high-dimensional varieties.

major comments (2)
  1. [Abstract and §4] Abstract and §4 (Examples): the claim of 'accurate recovery' on several examples is stated without quantitative validation, error analysis, tolerance studies, or comparison against any baseline method that does compute the eliminant. Because the central claim rests on the fidelity of the numerical real-root classification, the absence of such metrics leaves the soundness of the algorithm unverified.
  2. [Method section] Method section (presumably §3): the assertion that intersections computed via pseudo-witness sets on generic lines yield the exact real roots and their multiplicities of the unknown univariate eliminant is load-bearing. The manuscript must supply a concrete argument or numerical safeguard showing that even-multiplicity real roots are never misclassified as odd (or missed) under the chosen tolerances; otherwise the subsequent global assembly of region labels from multiple lines cannot be guaranteed correct.
minor comments (1)
  1. [Notation and implementation] Clarify the precise notion of 'pseudo-witness set' employed for real points and state the numerical tolerances used for reality filtering and multiplicity detection.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for stronger validation and explicit safeguards. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract and §4] Abstract and §4 (Examples): the claim of 'accurate recovery' on several examples is stated without quantitative validation, error analysis, tolerance studies, or comparison against any baseline method that does compute the eliminant. Because the central claim rests on the fidelity of the numerical real-root classification, the absence of such metrics leaves the soundness of the algorithm unverified.

    Authors: We agree that the current presentation of the examples would benefit from quantitative support. In the revised version we will augment §4 with tolerance studies (varying working precision and homotopy tolerances while tracking stability of the recovered regions), error metrics (e.g., Hausdorff distance between numerically and symbolically computed boundaries on low-degree instances), and direct comparisons against Gröbner-basis or resultant-based eliminants wherever the latter remain feasible. These additions will supply the concrete validation requested. revision: yes

  2. Referee: [Method section] Method section (presumably §3): the assertion that intersections computed via pseudo-witness sets on generic lines yield the exact real roots and their multiplicities of the unknown univariate eliminant is load-bearing. The manuscript must supply a concrete argument or numerical safeguard showing that even-multiplicity real roots are never misclassified as odd (or missed) under the chosen tolerances; otherwise the subsequent global assembly of region labels from multiple lines cannot be guaranteed correct.

    Authors: Pseudo-witness sets recover multiplicity by counting the number of homotopy paths that converge to each point; even multiplicity is therefore detected directly from path count rather than from root isolation alone. In the revised §3 we will insert a short subsection that (i) recalls this standard property of witness sets, (ii) describes the adaptive-precision safeguard we employ (doubling precision and re-running the homotopy whenever a path count is near an even/odd boundary), and (iii) notes that the generic choice of lines ensures that the probability of numerical misclassification falls below the working tolerance. This supplies the concrete argument and safeguard requested while preserving the numerical character of the method. revision: yes

Circularity Check

0 steps flagged

No circularity: method applies external pseudo-witness machinery to line intersections

full rationale

The derivation computes real complement regions by intersecting the hypersurface with generic lines via pseudo-witness sets, then using univariate interpolation on those points. No equation or step in the given abstract or description reduces a claimed result to a fitted parameter, self-definition, or self-citation chain by construction. The approach explicitly avoids computing the eliminant and treats pseudo-witness sets as an established black-box tool from numerical algebraic geometry. This is a standard non-circular application of prior machinery to a new task, consistent with the reader's assessment of score 2 (minor self-citation at most, not load-bearing).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard assumptions from numerical algebraic geometry that pseudo-witness sets correctly represent intersections; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption Pseudo-witness sets can be computed and used to determine real intersection points of a hypersurface with a generic line without the explicit equation
    Invoked when the abstract states that intersections are obtained using pseudo-witness sets.

pith-pipeline@v0.9.0 · 5481 in / 1223 out tokens · 32114 ms · 2026-05-16T15:53:06.406456+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Copositive Matrices with Ordered Off-Diagonal Entries

    math.OC 2026-05 unverdicted novelty 7.0

    Copositive matrices with nondecreasing off-diagonal entries admit a PSD plus nonnegative decomposition, which implies exactness of a natural relaxation for separable quadratic optimization over the simplex.

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages · cited by 1 Pith paper

  1. [1]

    Ambrosetti

    A. Ambrosetti. Elliptic equations with jumping nonlinearities.J. Math. Phys. Sci., 18(1):1–12, 1984

    work page 1984

  2. [2]

    Ambrosetti and P

    A. Ambrosetti and P. H. Rabinowitz. Dual variational methods in critical point theory and applications.J. Functional Analysis, 14:349–381, 1973

    work page 1973

  3. [3]

    S. Basu, R. Pollack, and M. F. Roy.Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, second edition, 2006

    work page 2006

  4. [4]

    D. J. Bates, P. Breiding, T. Chen, J. D. Hauenstein, A. Leykin, and F. Sottile. Numerical nonlinear algebra. InCombinatorial, Computational, and Applied Algebraic Geometry: A Tribute to Bernd Sturmfels, volume 111 ofProceedings of Symposia in Pure Mathematics, pages 229–270, Providence, RI, 2025. AMS. 20

    work page 2025

  5. [5]

    D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler.Numerically Solving Polynomial Systems With Bertini, volume 25 ofSoftware, Environments, and Tools. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2013

    work page 2013

  6. [6]

    Berec, E

    L. Berec, E. Angulo, and F. Courchamp. Multiple allee effects and population management. Trends in Ecology & Evolution, 22(4):185–191, 2007

    work page 2007

  7. [7]

    Bliss, T

    N. Bliss, T. Duff, A. Leykin, and J. Sommars. Monodromy solver: sequential and parallel. In 2018 ACM International Symposium on Symbolic and Algebraic Computation, pages 87–94, New York, July 2018

    work page 2018

  8. [8]

    Bonev, S

    I. Bonev, S. Briot, P. Wenger, and D. Chablat. Changing assembly modes without passing parallel singularities in non-cuspidal 3-RPR planar parallel robots. InSecond International Workshop on Fundamental Issues and Future Research Directions for Parallel Mechanisms and Manipulators, Montpellier, France, September 2008

    work page 2008

  9. [9]

    Brandenburg and C

    M.-C. Brandenburg and C. Meroni. Combinatorics of slices of cubes. Preprint, 2025. arXiv:2510.09265

    work page arXiv 2025

  10. [10]

    Breiding, B

    P. Breiding, B. Sturmfels, and K. Wang. Computing arrangements of hypersurfaces.J. Softw. Algebra Geom., 15(1):11–27, 2025

    work page 2025

  11. [11]

    Breiding and S

    P. Breiding and S. Timme.HomotopyContinuation.jl: A package for homotopy continuation in Julia. In J. H. Davenport, M. Kauers, G. Labahn, and J. Urban, editors,Mathematical Software – ICMS 2018, pages 458–465, Cham, 2018. Springer International Publishing

    work page 2018

  12. [12]

    J. Canny. Computing roadmaps of general semi-algebraic sets.Comput. J., 36(5):504–514, 1993

    work page 1993

  13. [13]

    Chen and J

    J. Chen and J. Kileel. Numerical implicitization.J. Softw. Algebra Geom., 9(1):55–63, 2019

    work page 2019

  14. [14]

    O. Coss, J. D. Hauenstein, H. Hong, and D. K. Molzahn. Locating and counting equilibria of the Kuramoto model with rank-one coupling.SIAM J. Appl. Algebra Geom., 2(1):45–71, 2018

    work page 2018

  15. [15]

    Cummings, K

    J. Cummings, K. J.-M. Dahlin, E. Gross, and J. D. Hauenstein. Routing Functions for Param- eter Space Decomposition to Describe Stability Landscapes of Ecological Models.Bull. Math. Biol., 87(12):Paper No. 177, 2025

    work page 2025

  16. [16]

    Cummings, J

    J. Cummings, J. D. Hauenstein, H. Hong, and C. D. Smyth. Smooth connectivity in real algebraic varieties.Numer. Algorithms, 100(1):63–84, 2025

    work page 2025

  17. [17]

    Decker, C

    W. Decker, C. Eder, C. Fieker, M. Horn, and M. Joswig, editors.The Computer Algebra System OSCAR: Algorithms and Examples, volume 32 ofAlgorithms and Computation in Mathematics. Springer, 1 edition, 2025

    work page 2025

  18. [18]

    T. Duff, C. Hill, A. Jensen, K. Lee, A. Leykin, and J. Sommars. Solving polynomial systems via homotopy continuation and monodromy.IMA J. Numer. Anal., 39(3):1421–1446, 2019

    work page 2019

  19. [19]

    Gelfand, M

    I. Gelfand, M. Kapranov, and A. Zelevinsky.Discriminants, Resultants, and Multidimensional Determinants. Birkh¨ auser, Boston, 1994

    work page 1994

  20. [20]

    C. M. Gosselin, J. Sefrioui, and M. J. Richard. Solutions polynomiales au probleme de la cinematique directe des manipulateurs paralleles plans a trois degres de liberte.Mech. Mach. Theory, 27(2):107–119, 1992

    work page 1992

  21. [21]

    J. D. Hauenstein, C. Ikenmeyer, and J. M. Landsberg. Equations for lower bounds on border 21 rank.Exp. Math., 22(4):372–383, 2013

    work page 2013

  22. [22]

    J. D. Hauenstein, L. Oeding, G. Ottaviani, and A. J. Sommese. Homotopy techniques for tensor decomposition and perfect identifiability.J. reine angew. Math., 2019(753):1–22, 2019

    work page 2019

  23. [23]

    J. D. Hauenstein and M. H. Regan. Evaluating and differentiating a polynomial using a pseudo- witness set. In A. M. Bigatti, J. Carette, J. H. Davenport, M. Joswig, and T. de Wolff, editors, Mathematical Software – ICMS 2020, pages 61–69, 2020

    work page 2020

  24. [24]

    J. D. Hauenstein and M. H. Regan. Real monodromy action.Appl. Math. Comput., 373:124983, 2020

    work page 2020

  25. [25]

    J. D. Hauenstein, J. I. Rodriguez, and F. Sottile. Numerical computation of Galois groups. Found. Comput. Math., 18(4):867–890, 2018

    work page 2018

  26. [26]

    J. D. Hauenstein and S. N. Sherman. Using monodromy to statistically estimate the number of solutions. In2nd IMA Conference on Mathematics of Robotics, pages 37–46, 2022

    work page 2022

  27. [27]

    J. D. Hauenstein and A. J. Sommese. Witness sets of projections.Appl. Math. Comput., 217(7):3349–3354, 2010

    work page 2010

  28. [28]

    J. D. Hauenstein and A. J. Sommese. Membership tests for images of algebraic sets by linear projections.Appl. Math. Comput., 219(12):6809–6818, 2013

    work page 2013

  29. [29]

    J. D. Hauenstein and A. J. Sommese. What is numerical algebraic geometry?Journal of Symbolic Computation, 79:499–507, 2017

    work page 2017

  30. [30]

    J. D. Hauenstein, A. J. Sommese, and C. W. Wampler. Regeneration homotopies for solving systems of polynomials.Math. Comp., 80(273):345–377, 2011

    work page 2011

  31. [31]

    J. D. Hauenstein and C. W. Wampler. Isosingular sets and deflation.Found. Comput. Math., 13(3):371–403, 2013

    work page 2013

  32. [32]

    J. D. Hauenstein and C. W. Wampler. Numerically intersecting algebraic varieties via witness sets.Appl. Math. Comput., 219(10):5730–5742, 2013

    work page 2013

  33. [33]

    Hayes.Kinematics of General Planar Stewart-Gough Platforms

    M. Hayes.Kinematics of General Planar Stewart-Gough Platforms. PhD thesis, McGill Uni- versity, 1999

    work page 1999

  34. [34]

    H. Hong. Connectivity in semi-algebraic sets. In12th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pages 4–7, Timisoara, Romania, September

    work page

  35. [35]

    IEEE Computer Society

    work page

  36. [36]

    H. Hong, J. Rohal, M. S. E. Din, and E. Schost. Connectivity in semi-algebraic sets I. Preprint,

    work page

  37. [37]

    M. L. Husty. Non-singular assembly mode change in 3-RPR-parallel manipulators. InCompu- tational Kinematics: Proceedings of the 5th International Workshop on Computational Kine- matics, pages 51–60. Springer, 2009

    work page 2009

  38. [38]

    Innocenti and V

    C. Innocenti and V. Parenti-Castelli. Singularity-free evolution from one configuration to another in serial and fully-parallel manipulators.J. Mech. Des., 120(1):73–79, 1998

    work page 1998

  39. [39]

    Kuramoto

    Y. Kuramoto. Self-entrainment of a population of coupled non-linear oscillators.Lect. Notes Phys., 39:420–422, 1975

    work page 1975

  40. [40]

    Kuramoto.Chemical oscillations, waves, and turbulence, volume 19 ofSpringer Series in Synergetics

    Y. Kuramoto.Chemical oscillations, waves, and turbulence, volume 19 ofSpringer Series in Synergetics. Springer-Verlag, Berlin, 1984. 22

    work page 1984

  41. [41]

    Macho, O

    E. Macho, O. Altuzarra, C. Pinto, and A. Hern´ andez. Singularity free change of assembly mode in parallel manipulators: Application to the 3-RPR planar platform. In12th IFToMM World Congr., pages 1–6, Besancon, France, 01 2007

    work page 2007

  42. [42]

    Mehta, N

    D. Mehta, N. S. Daleo, F. D¨ orfler, and J. D. Hauenstein. Algebraic geometrization of the Kuramoto model: equilibria and stability analysis.Chaos, 25(5):053103, 7, 2015

    work page 2015

  43. [43]

    J. J. Mor´ e and T. S. Munson. Computing mountain passes and transition states.Math. Program., 100(1):151–182, 2004

    work page 2004

  44. [44]

    OSCAR – Open Source Computer Algebra Research system, Version 1.6.0, 2025

    work page 2025

  45. [45]

    R¨ ost and A

    G. R¨ ost and A. Sadeghimanesh. Exotic bifurcations in three connected populations with allee effect.International Journal of Bifurcation and Chaos, 31(13):2150202, 2021

    work page 2021

  46. [46]

    Sadeghimanesh and M

    A. Sadeghimanesh and M. England. Resultant tools for parametric polynomial systems with application to population models, 2022

    work page 2022

  47. [47]

    Safey El Din and E

    M. Safey El Din and E. Schost. Polar varieties and computation of one point in each connected component of a smooth algebraic set. InProceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pages 224–231. ACM, New York, 2003

    work page 2003

  48. [48]

    A. J. Sommese, J. Verschelde, and C. W. Wampler. Using monodromy to decompose solution sets of polynomial systems into irreducible components. InApplications of algebraic geometry to coding theory, physics and computation (Eilat, 2001), volume 36 ofNATO Sci. Ser. II Math. Phys. Chem., pages 297–315. Kluwer Acad. Publ., Dordrecht, 2001

    work page 2001

  49. [49]

    A. J. Sommese, J. Verschelde, and C. W. Wampler. Homotopies for intersecting solution components of polynomial systems.SIAM J. Numer. Anal., 42(4):1552–1571, 2004

    work page 2004

  50. [50]

    A. J. Sommese, J. Verschelde, and C. W. Wampler. An intrinsic homotopy for intersecting algebraic varieties.Journal of Complexity, 21(4):593–608, 2005

    work page 2005

  51. [51]

    A. J. Sommese and C. W. Wampler.The Numerical Solution Of Systems Of Polynomials Arising In Engineering And Science. World Scientific, 2005

    work page 2005

  52. [52]

    Song and X

    K. Song and X. Tang. Steady state classification of Allee effect system. Preprint, 2025. arXiv:2501.19062

    work page arXiv 2025

  53. [53]

    Y.-L. Tsai. Bifurcations in a population model onNpatches with strong Allee effect and spatial dispersal through Jacobian matrices.J. Symbolic Comput., 135, 2026

    work page 2026

  54. [54]

    ¨Ozl¨ um C ¸ elik, P

    T. ¨Ozl¨ um C ¸ elik, P. A. Haas, G. Scholten, K. Wang, and G. Zucal. Strata of ecological coexis- tence via Grassmannians. Preprint, 2025. arXiv:2509.00165. Authors’ addresses: Paul Breiding, University of Osnabr¨ uckpbreiding@uni-osnabrueck.de John Cobb, Auburn Universityjohn.cobb@auburn.edu Aviva K. Englander, University of Wisconsin–Madisonakenglander...

    work page arXiv 2025