pith. sign in

arxiv: 2605.18110 · v3 · pith:J5UFRVWPnew · submitted 2026-05-18 · 💻 cs.SC · math.AG

Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I

J\'er\'emy Berthomieu (PolSys) , Edern Gillot (PolSys) , Mohab Safey El Din (PolSys) This is my paper

Pith reviewed 2026-05-25 06:23 UTC · model grok-4.3

classification 💻 cs.SC math.AG
keywords semi-algebraic setsconnected componentscritical pointsreal algebraic geometrybit complexityprobabilistic algorithmsBézout boundsample points
0
0 comments X

The pith

A probabilistic algorithm computes sample points in each connected component of a semi-algebraic set defined by one polynomial inequality, with bit complexity cubic in the Bézout bound for parametrizations.

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

The paper presents a probabilistic method that reduces the task of finding one point in each connected component of the set where an n-variate polynomial of degree d is positive or nonzero to the solution of zero-dimensional polynomial systems. It proceeds by computing critical points of carefully chosen projection maps, assuming the hypersurface is smooth. Under this assumption the algorithm produces exact parametrizations of the sample points at essentially cubic cost in the Bézout bound d(d-1)^{n-1} and rational approximations precise enough to stay inside the same components at quartic cost. The analysis accounts for the actual degrees of the input and its derivatives, and the probability of success is quantified. Experiments on dense random polynomials and application instances show the method solves problems previously out of reach.

Core claim

Assuming the hypersurface defined by the input polynomial is smooth, the connected components of the semi-algebraic set can be captured by the real critical points of well-chosen maps; these critical points are obtained by reducing to zero-dimensional polynomial systems whose solutions are then filtered and certified, yielding a probabilistic algorithm whose bit complexity is essentially cubic in the Bézout bound d(d-1)^{n-1} for parametrizations of the real points and quartic for sufficiently precise rational approximations, with the degree structure of the partial derivatives taken into account.

What carries the argument

Critical points of well-chosen maps, obtained via reduction to zero-dimensional polynomial systems

If this is right

  • Sample points for positivity or non-vanishing semi-algebraic sets become available as a black-box routine for higher-level real-algebraic algorithms.
  • When the input polynomial and its derivatives have degrees below the generic maximum, the bit complexity improves accordingly.
  • The same reduction produces both exact algebraic parametrizations and certified rational approximations that remain inside the original components.
  • The success probability can be made arbitrarily close to 1 by repeating the random choices a logarithmic number of times.

Where Pith is reading between the lines

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

  • The method could be combined with existing real-root isolation routines to produce certified numerical approximations of the sample points.
  • Extending the smoothness assumption check to a preprocessing step would enlarge the class of inputs that can be handled without user intervention.
  • The cubic dependence on the Bézout bound suggests the algorithm remains practical for moderate n and d where previous critical-point methods scaled worse.

Load-bearing premise

The hypersurface defined by the input polynomial is smooth.

What would settle it

Run the algorithm on a smooth random dense polynomial of known degree and dimension whose connected components are already enumerated by another method; if any component lacks a returned sample point or if the observed bit complexity exceeds a small multiple of the cubic bound, the claim fails.

Figures

Figures reproduced from arXiv: 2605.18110 by Edern Gillot (PolSys), J\'er\'emy Berthomieu (PolSys), Mohab Safey El Din (PolSys).

Figure 1
Figure 1. Figure 1: Illustration of the first step of algorithm applied to [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the second step of algorithm applied to [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the third step of algorithm applied to [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of ℓξ,a on a two-dimensional example. Let us now define the univariate polynomial fξ,a(u) := f(ξ + au) ∈ R[u]. By con￾struction, the roots of fξ,a are the relative distances between ξ and the intersection points of V ∩ R n and ℓξ,a. In particular, 0 is a root of fξ,a, corresponding to ξ itself. Let us denote by {ζ1, . . . , ζr} the non-zero roots of fξ,a, when any exists. Finally, if ξ ∈ V , l… view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the output of HypersurfaceRegions applied to f = ((x0 − 1)2 +x 2 1 −1−1/2 16)((x0 + 1)2 +x 2 1 −1−1/2 16). Despite the success of the computation, the central component (in red) is missed (exaggerated size for visual clarity). We apply these algorithms to three types of examples: • generic dense polynomials of fixed degree 4 and height 6, with varying number n of variables, • generic polyno… view at source ↗
read the original abstract

We consider the problem of computing sample points in each connected component of a semi-algebraic set defined by the non-vanishing or the positivity of an n-variate polynomial of degree d, with rational coefficients of bit size bounded by $\tau$. Such a problem is a basic routine in effective real algebraic geometry, used in higher-level algorithms for solving polynomial systems over the reals and finds many applications in sciences. We design a probabilistic algorithm for solving this problem, which is based on reductions to different routines for solving zero-dimensional polynomial systems. It assumes that the input polynomial satisfies sufficiently generic properties (namely, smoothness of its defining hypersurface). This is done through the computations of critical points of well-chosen maps to capture the connected components of the semi-algebraic set under study. We derive a bit complexity estimate for the cost of this algorithm, which is, in terms of the B{\'e}zout bound d(d -1)^{n-1}, essentially cubic for obtaining parametrisations of the sought-for real points. Moreover, we also consider the case of obtaining rational approximations of those points, which are precise enough to lie in the same connected components as their exact counterparts, which yields a cost that is essentially quartic in the B{\'e}zout bound. In these complexity estimates, we take into account the degree structure of the input polynomial and its partial derivatives, allowing for a more refined bit complexity when the partial derivative of the input polynomial have degree lower than expected. We also analyse the probability of success of those algorithms. We report on practical experiments, benchmarking with random dense input polynomials as well as polynomials coming from applications, which were out of reach of the state-of-the-art implementations, and hence illustrate the practical efficiency of these new algorithms.

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

0 major / 3 minor

Summary. The manuscript presents a probabilistic algorithm for computing sample points in each connected component of the semi-algebraic set defined by f > 0 or f ≠ 0, where f is an n-variate polynomial of degree d with rational coefficients of bit size τ. The method reduces the problem to zero-dimensional polynomial system solving via critical points of suitably chosen maps, under the explicit hypothesis that the hypersurface V(f) is smooth. Bit complexity bounds are derived that are essentially cubic in the Bézout number d(d-1)^{n-1} for obtaining parametrizations of the real points and quartic for sufficiently precise rational approximations that lie in the same components; the analysis accounts for the actual degree structure of the input and its partial derivatives. Success probability is analyzed, and the algorithms are implemented and benchmarked on random dense instances as well as application-derived polynomials previously out of reach.

Significance. If the stated complexity bounds and correctness under the smoothness hypothesis hold, the work supplies an improved basic routine for sampling connected components of one-inequality semi-algebraic sets, a foundational task in effective real algebraic geometry. The refined treatment of degree structure in the partial derivatives and the explicit success-probability analysis are strengths. The reported practical experiments demonstrating scalability beyond prior implementations further indicate utility for higher-level real-solving algorithms.

minor comments (3)
  1. The abstract and title refer to 'Part I' without indicating the intended scope or division of material with any subsequent part; a brief statement of the overall plan would improve context.
  2. The phrases 'essentially cubic' and 'essentially quartic' in the complexity claims would benefit from explicit leading-term expressions or precise big-O statements that incorporate the degree-structure refinements.
  3. A short dedicated subsection comparing the new bit-complexity bounds with the best previously published bounds for the same problem would help readers assess the improvement quantitatively.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the work, and recommendation of minor revision. No major comments were provided in the report, so there are no specific points requiring detailed rebuttal or revision at this stage. We will incorporate any minor suggestions during the revision process.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central derivation reduces the connected-component sampling problem to standard zero-dimensional polynomial solving routines under an explicit generic smoothness hypothesis on V(f). Bit-complexity bounds (cubic/quartic in the Bézout number d(d-1)^{n-1}) are obtained by accounting for degree structure of partials and success-probability analysis; these steps rely on external, independently verifiable algebraic-geometry primitives rather than any self-definitional loop, fitted-input prediction, or load-bearing self-citation chain. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the generic smoothness assumption for the hypersurface and on standard algebraic geometry facts about critical points and zero-dimensional systems; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The input polynomial defines a smooth hypersurface
    Invoked to ensure critical points of chosen maps capture all connected components of the semi-algebraic set.

pith-pipeline@v0.9.0 · 5883 in / 1196 out tokens · 42480 ms · 2026-05-25T06:23:13.653533+00:00 · methodology

Review history (2 revisions) →

discussion (0)

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