When we verify a car, a drone, or a spacecraft controller, we must compute the set of states the system can reach. Exact sets are intractable, so tools enclose them in simple shapes and re-enclose them after every time step and every discrete transition. Each re-enclosure adds empty space, and that empty space compounds step after step until safety can no longer be proven — this is the wrapping effect, and it is the main reason reachability tools time out or return bounds that are orders of magnitude too loose (The Wrapping Effect in Formal Reachability Analysis). The known cure is to keep correlations symbolically: polynomial zonotopes — sets written as polynomial combinations of uncertain factors — track shared dependencies through an exact sum operation instead of discarding them (Reachability Analysis for Linear Systems with Uncertain Parameters using Polynomial Zonotopes), and symbolic remainders do the same across neural-network layers (POLAR-Express: Efficient and Precise Formal Reachability Analysis of Neural-Network Controlled Systems). But this cure has a cost of its own: the number of generators and polynomial terms explodes, and the crude truncation used to contain that explosion re-injects the wrapping effect. The literature states this trade-off explicitly — avoiding geometric bloating shifts the bottleneck to algebraic intractability (Reachability Analysis for Linear Systems with Uncertain Parameters using Polynomial Zonotopes).
Hybrid systems make it worse. When a continuous flow of states meets a discrete switching condition (a "guard"), the tool must find when trajectories cross the guard surface — a polynomial root-finding problem. The ARCH-COMP competition report identifies guard crossings as a primary failure point: when trajectories graze the surface, tools lack multiplicity-aware root solvers and over-split into an explosion of branches (ARCH-COMP24 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics). This proposal builds a hybrid reachability engine that manages both swell problems with partial-commitment algorithms imported from two seemingly unrelated literatures: iterative partial coloring from discrepancy theory, and continued-fraction root isolation from exact symbolic computation. Coefficient bit-size explosion — the exponential growth of intermediate integers in exact arithmetic — is the constraint that shapes the whole design, because a certified pipeline is only useful if its exact arithmetic does not blow up.
Core Claim
The claim has three parts. First, generator reduction of (polynomial) zonotopes is naturally a discrepancy minimization problem, and iterative partial coloring solves it with a certified error bound, replacing the heuristic truncation that currently re-injects wrapping. Second, continued-fraction root isolation with multiplicity tracking turns guard crossings from a branch-explosion trigger into a certified, split-minimizing decision: an even-multiplicity root means a trajectory grazes the guard and should not be split at all. Third, both components can be kept in exact arithmetic without bit-size blowup by using subresultant identities instead of naive Euclidean remainder sequences, which is exactly where prior verified procedures fail (A Verified Decision Procedure for Univariate Real Arithmetic with the BKR Algorithm).
Research Program
Discrepancy-reduced zonotopes. A zonotope is a set $Z = c + \sum_{i=1}^{p} \alpha_i g_i$ where each $g_i \in \mathbb{R}^n$ is a generator vector and $\alpha_i \in [-1,1]$. Standard order reduction pairs generators and encloses each two-generator parallelogram in a box, halving $p$ but adding dead space whose size depends on how the pair members are aligned. We choose the alignment signs jointly rather than independently: picking $x \in \{-1,+1\}^{p/2}$ so that
$$Z \subseteq Z' \subseteq Z + [-\varepsilon, \varepsilon]^n, \qquad \varepsilon = \|A x\|_\infty,$$
where the rows of $A$ encode, per state coordinate, the residual over-approximation of each merged pair. Minimizing $\|Ax\|_\infty$ over signs is precisely the combinatorial discrepancy problem that iterative partial coloring attacks: color (fix) only a fraction of the generator pairs per round, keeping the rest symbolic, so that the dependencies that matter are preserved and only well-conditioned pairs are merged. This is the nibble discipline — commit partially, avoid cascading conflicts — transplanted from graph edge coloring (Near-Optimal, Distributed Edge Colouring via the Nibble Method) and discrepancy walks (Fast Discrepancy Minimization with Hereditary Guarantees, Spectral Sparsification by Deterministic Discrepancy Walk) into geometry. Two facts make this transfer favorable. The hereditary guarantee of the fast algorithm bounds the per-round enclosure growth by the hereditary discrepancy of $A$, so the reduction is certified rather than heuristic. And the algorithm's known weakness — an extra $\lg^{3/2} m$ factor in its bound relative to slower methods — is negligible here because $m$ is the state dimension (typically 4–12), not a free parameter. We will also derive a nibbled variant that reduces only the tail of small-norm generators per step, bounding per-step cost, and we will state a per-step guarantee in the style of the deterministic walk, which smooths the worst coordinate via a regularized potential and fixes coordinates on restricted subspaces.
Continued-fraction guards. At a guard crossing we must isolate the roots of a polynomial (the guard function composed with the flowpipe's trajectory bounds) and know their multiplicities. We use the continued-fraction solver of On the complexity of real root isolation using continued fractions, which repeatedly transforms the polynomial by shifts and inversions until Descartes' rule of signs certifies isolation, and which computes exact multiplicities during isolation via Sturm-Habicht subresultant sequences without extra asymptotic cost. The multiplicity is the payoff for reachability: an odd-multiplicity root is a genuine crossing (split the flowpipe there), while an even-multiplicity root is a tangent graze (the set touches the guard and turns back — no split, only a tightened enclosure). Clustered roots, the case where interval subdivision degenerates, are exactly where continued fractions shine, since their partial quotients adapt to root spacing instead of bisecting uniformly. We will formulate a grazing-aware guard-crossing rule and prove it sound: no crossing is ever missed, because every intersection interval is certified.
Controlling bit-size explosion end to end. The pipeline is exact: guard polynomials have integer coefficients, flowpipe endpoints are compared to algebraic quantities, and every sign comparison must be certified. The cautionary tale is the verified BKR decision procedure, whose naive Euclidean remainder sequences suffer rational coefficient explosion and time out at degree 22 (A Verified Decision Procedure for Univariate Real Arithmetic with the BKR Algorithm). We therefore build all sign and Tarski-query computations on subresultant sequences, whose determinant identities divide out the extraneous factors that make pseudo-division coefficients double at every step (A Probabilistic Algorithm for Computation of Polynomial Greatest Common with Smaller Factors), and we track worst-case intermediate bit sizes through the whole engine, aiming for per-event behavior matching the continued-fraction bound of $\tilde{O}_B(d^4 \tau^2)$ for degree $d$ and coefficient bit size $\tau$. One honesty point: that bound is average-case and rests on the unproven conjecture that algebraic numbers obey Khintchine's law (On the complexity of real root isolation using continued fractions). Guard polynomials per event have modest degree, so the practical risk is low, and even the unconditional worst case matches subdivision asymptotically — the practical advantage on clustered roots comes from the adaptive partial quotients, not the exponent. We will report measured intermediate bit sizes, not just asymptotics.
The deliverable is a prototype engine (on a polynomial-zonotope core, interfaced with CORA-style tooling) with three replaceable modules — reduction policy, guard solver, arithmetic backend — so every claim is testable by substitution.
Baselines
The do-nothing reference is standard zonotope order reduction by interval hulls of generator pairs with independently chosen alignments, as used inside existing toolboxes; it is the reference point because it is what every current implementation falls back on when generators accumulate, and it is the operation our discrepancy step replaces. The strongest existing competitor for the representation question is the polynomial-zonotope engine of Reachability Analysis for Linear Systems with Uncertain Parameters using Polynomial Zonotopes, which preserves dependencies via exact sums and controls term explosion with multi-affine zonotopes and vertex-cut graph decomposition; it reports 9 seconds versus 15 seconds for CORA on the 9-dimensional vehicle platooning benchmark and 0% relative error in 15–16 seconds on multi-affine optimization where splitting methods took hundreds of seconds or failed. We run it on the same benchmarks, machine, and time limits, with an equal tuning budget (a grid over reduction-order thresholds and truncation orders of the same size for both engines), and we count our approach as winning only if the final enclosure volume is smaller at equal or lower wall-clock, or equal volume at strictly lower clock. For the guard question the strongest baseline is interval bisection with constraint propagation, the DynIbex-style approach documented in ARCH-COMP24 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics, plus the subdivision-based exact solver rs as the exact-arithmetic competitor (On the complexity of real root isolation using continued fractions; on Mignotte clustered-root polynomials of degree 1000, rs failed within a 12,000-second limit while continued fractions finished in 6.22 seconds). Two ablations isolate the key ingredients: replacing the partial-coloring sign choice with random signs (same pairing, same everything else), and replacing the continued-fraction guard solver with bisection while keeping the rest of the engine fixed. Beating the guard baseline means fewer flowpipe branches per guard crossing with zero missed crossings, verified against exact continued-fraction intervals as ground truth.
Why not just…?
Why not just use interval hulls or PCA to trim generators? These are exactly the crude reductions that cause the compounding the field is trying to escape: replacing symbolic correlations with boxes re-triggers the wrapping effect, whose cascading growth across steps is documented directly (The Wrapping Effect in Formal Reachability Analysis), and convex or low-rank enclosures demonstrably add dead space on non-convex reachable sets — on the Dubins car turning benchmark, zonotope-based CORA enclosures were far looser than polynomial zonotopes (Reachability Analysis for Linear Systems with Uncertain Parameters using Polynomial Zonotopes). Our first experiment measures final enclosure volume against step count for hull, PCA, and partial coloring on the same trajectory, which settles the question empirically rather than by argument.
Why not just bisect at guards with subdivision? Subdivision has unconditional worst-case bounds and no dependence on number-theoretic conjectures, so a reviewer will rightly prefer it on principle. But rigid midpoint splitting is structurally bad at clustered and multiple roots, where the polynomial is nearly flat near the root: on Mignotte $M1$ polynomials the subdivision solver rs exceeded a 12,000-second timeout while continued fractions took 6.22 seconds (On the complexity of real root isolation using continued fractions), and flatness defeats fixed-precision solvers even more basically (Multiplicity Aware Real Root Isolation). Grazing guards are precisely the flat case. The bisection ablation above will show whether this transfers from synthetic polynomials to guard events; if bisection matches continued fractions on our synthetic grazing suite, that is a finding we will report, since it would mean the win comes only from multiplicity-aware splitting rather than the solver itself.
Why not just use floating-point or interval arithmetic and avoid bit-size explosion entirely? This is the most serious objection, because most reachability practice is already semi-numerical and fast. Three pieces of evidence bound the threat: outward rounding breaks the soundness requirements of certified pipelines (A Verified Decision Procedure for Univariate Real Arithmetic with the BKR Algorithm); fixed precision cannot distinguish a multiple root from a tight cluster (Multiplicity Aware Real Root Isolation); and interval-based DynIbex took over 800 seconds or failed on the coupled Van der Pol benchmark where Taylor-model propagation finished in 1.2 seconds (ARCH-COMP24 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics). Still, we take the objection seriously: the continued-fraction paper itself lists semi-numerical filtering as open future work, so we will implement a floating-point filter with an exact fallback as one arithmetic backend, and report the fraction of guard events resolved by the filter versus escalated to exact arithmetic. If the filter resolves nearly everything, the exact path costs little; if it fails on grazes, that is our evidence for the exact design.
Why not just sample random signs for the merges? Random sampling is the obvious cheap substitute for a discrepancy walk. It was tested directly against the partial-coloring algorithm on 4000×4000 matrices, where the walk's colorings were roughly 10 times smaller in discrepancy than a single random sample and 4 times smaller than multiple random samples run for the same duration (Fast Discrepancy Minimization with Hereditary Guarantees). Because these factors compound over time steps in reachability, we expect the gap to widen with horizon length; the random-sign ablation measures exactly this compounding.
Proposed Experiments and Decisive Checks
The primary benchmark is SPRE22, the space rendezvous hybrid benchmark whose guard crossings drive the branch explosion reported in ARCH-COMP24 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics, where CORA was the speed standout but no tool addresses grazing soundly and tightly at once. We add the Dubins car model (non-convex turning, where polynomial zonotopes beat CORA on tightness), the vehicle platooning system (direct comparison against the 9-second polynomial-zonotope result), and CVDP23 (nonlinearity stress test; JuliaReach finished it in 1.2 seconds where others took over 800 seconds, so it calibrates our engine against the field's best-case). To test guards in isolation we build a synthetic suite of grazing-guard hybrid systems whose guard functions are Mignotte-style polynomials with certified clustered and multiple roots, giving ground truth for split counts and missed crossings. Metrics throughout: final enclosure volume and tightness ratio, wall-clock time, flowpipe branch count per guard crossing, number of guard events escalated from the floating-point filter to exact arithmetic, and maximum intermediate coefficient bit size per event (contrasting Euclidean versus subresultant backends, where the BKR procedure's degree-22 timeout is the reference failure mode). The decisive checks are three. On representation: partial coloring must beat interval hull and PCA on enclosure volume versus step count on Dubins car, and match or beat the multi-affine polynomial-zonotope engine on platooning at equal tuning budget. On guards: on the synthetic grazing suite, the continued-fraction rule must produce strictly fewer branches than bisection with zero missed crossings. On arithmetic: the subresultant backend must keep measured bit growth near-linear in event degree where the Euclidean backend reproduces the explosive blowup documented at degree 22. If all three hold, the result is a reachability engine whose two swell problems — geometric and algebraic — are controlled by certified, partial-commitment algorithms rather than by heuristics that trade one for the other.
References
- ARCH-COMP21 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics
- Reachability analysis for linear systems with uncertain parameters using polynomial zonotopes
- POLAR-Express: Efficient and Precise Formal Reachability Analysis of Neural-Network Controlled Systems
- ARCH-COMP24 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics
- A Verified Decision Procedure for Univariate Real Arithmetic with the BKR Algorithm
- Near-Optimal, Distributed Edge Colouring via the Nibble Method
- Fast Discrepancy Minimization with Hereditary Guarantees
- Spectral Sparsification by Deterministic Discrepancy Walk
- On the complexity of real root isolation using continued fractions
- A Probabilistic Algorithm for Computation of Polynomial Greatest Common with Smaller Factors
- A prolongation-projection algorithm for computing the finite real variety of an ideal