Pith. sign in

REVIEW 2 major objections 6 minor 24 references

Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For continuous dynamical systems, the point-escape problem is maximally decidable: a cube-overapproximation search halts on exactly the instances whose answer is stable under small perturbations.

desk verdict A sound and genuinely new completeness theorem for the Point Escape Problem, with a careful but not flawless write-up; deserves peer review. read the letter →

arxiv 2506.21481 v1 pith:2VWMZQVP submitted 2025-06-26 cs.LO

Eike Neumann This is my paper · ORCID
classification cs.LO MSC 03D78
keywords dynamicalsystemscomputabilityinanalysisescapeproblemrobustdecidabilitypartialdecisionmethodsinvariantsetsMandelbrotsethyperbolicityconjecture
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies a general escape question for dynamical systems: given a closed set $A \subseteq \mathbb{R}^d$, a continuous map $f \colon \mathbb{R}^d \to \mathbb{R}^d$, and a point $x_0 \in A$, decide whether some iterate of $f$ leaves $A$. Exact decision is impossible for continuous data, so the paper adopts the bit-model of real computation and redefines completeness: a decision method is complete when it halts on every instance whose answer is stable under all sufficiently small perturbations of the input. The paper gives one such method—a stage-by-stage search over dyadic cubes that either witnesses escape or finds a finite invariant set inside $A$—and proves it complete: no sound partial decision method can halt on more instances. The key dichotomy is that a trapped orbit is certifiable exactly when the point $f(x_0)$ lies in the interior of a robust invariant $V$ with $f(V) \subseteq V^\circ$; without such a set, arbitrarily small perturbations make the point escape. The same algorithm then yields complete methods for affine-linear systems (by compactifying the unbounded state space) and, conditional on the hyperbolicity conjecture, for the quadratic family that defines the Mandelbrot set.

What carries the argument

The load-bearing object is the robust invariant: a compact set $V$ with $f(V) \subseteq V^\circ$, that is, $f$ maps $V$ into its own interior. The algorithm never searches for $V$ abstractly; instead, at each stage $n$ it works with dyadic cube partitions of $[-2^n,2^n]^d$, maintains cube overapproximations $Q_{n,i}$ of the orbit points and $O_{n,i}$ of the orbit segment, and checks two conditions: that some $Q_{n,i}$ is separated from $A$ (escape), or that $F_n(O_{n,i}) \subseteq O_{n,i}$ and $O_{n,i} \Subset A$ (trapped). The completeness proof shows that the cube-level inclusion $F_n(V_n) \subseteq V_n$ forms a sound and complete certificate for the existence of a robust invariant: such a $V$ exists exactly when the finite-cube search eventually stabilises.

What would settle it

Find a trapped triple $(f, A, x_0)$ for which the algorithm never halts but, for some fixed $n$, every $g$ with $d(f, g) \le 2^{-n}$ in the compact-open metric (1) also traps $x_0$; that would directly contradict the lemma that absence of a robust invariant yields an arbitrarily small perturbed map $g$ under which $x_0$ escapes.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the point-escape problem is maximally decidable at the level of robust instances: Algorithm 1 terminates on every escaping instance and on every trapped instance for which $f(x_0)$ is contained in the interior of a robust invariant $V \subseteq A^\circ$, and if it fails to terminate the instance sits on the decision boundary, with arbitrarily close perturbations answering both ways. Equivalently, its halting set contains the halting set of every sound partial decision method for the problem. The proof builds on a perturbation lemma: whenever $x_0$ is trapped but no robust invariant contains $f(x_0)$, the map $f$ can be modified by an arbitrarily small amount (in the topology of uniform convergence on compact sets) so that $x_0$ escapes; when $A \neq \mathbb{R}^d$, this can be done while keeping $A$ and $x_0$ fixed. From this, the halting behaviour of the algorithm is exactly the boundary structure of the problem.

Load-bearing premise

The completeness result holds only for the weakest representation of continuous functions that makes evaluation computable; if functions are given with extra information—say a modulus of continuity or derivative bounds—then more instances are robust and the algorithm is no longer claimed to be complete.

Editorial extensions

If this is right

  • Every trapped orbit that is robust—stable under small perturbations of the function—is automatically certifiable by a finite cube computation; no additional mathematical insight about the map is needed once the invariant exists.
  • The halting set of the algorithm is dense in the space of all instances, and every boundary trapped instance has arbitrarily small perturbations that make it robustly trapped, so the undecidable cases are confined to decision boundaries rather than occupying open regions.
  • For any fixed closed set $A \neq \mathbb{R}^d$ and initial point $x_0$, the algorithm is already complete when only the map $f$ varies; no specialised method for that fixed $A$ and $x_0$ can decide more functions than the general algorithm.
  • For affine linear maps the robust trapped instances admit an explicit spectral classification, and a compactification reduction makes the unbounded linear escape problem decidable by the same algorithm.
  • For the quadratic family $z \mapsto z^2 + c$, the origin-escape problem reduces to the point-escape problem in a way that preserves robustness exactly if the hyperbolicity conjecture holds; under that conjecture the algorithm decides the Mandelbrot set, giving a new proof of the conditional computability result.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the completeness dichotomy is correct, then every sound trap-certification procedure that works from black-box evaluations of a continuous map is implicitly searching for a robust invariant; one could try to compile other certificate formats such as Lyapunov functions, barrier certificates, or reachability proofs into the cube-inclusion certificate the algorithm constructs.
  • The representation-dependence of the result is itself a predictive tool: adding one piece of information—a modulus of continuity, a derivative bound, or algebraic data—should enlarge the halting set exactly by the instances that become robust under the corresponding stronger topology, and this can be tested instance-by-instance.
  • The quadratic-family result suggests a template for higher-degree families: any family of maps for which hyperbolic parameters are dense would inherit a complete decision method from the same invariant-search algorithm, so proving such density would immediately yield new maximal decision procedures for Julia-type escape sets.
  • The compactification used for affine linear maps suggests that 'well-behaved at infinity' is the right hypothesis under which the general algorithm can be extended; polynomial maps or rational maps on projective space are natural candidates where the same conjugation idea might apply.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper studies the Point Escape Problem: given a continuous map f:R^d->R^d, a closed set A, and x0 in A, decide whether some iterate f^n(x0) leaves A. Working in the bit-model of computable analysis, the author proposes a partial decision method (Algorithm 1) that searches either for a certificate of escape or for a robust invariant set witnessing that the orbit is trapped. The central result, Theorem 15, states that this algorithm is complete in the maximal-partial-decidability sense: it halts exactly on the robust instances, where robustness is understood with respect to the compact-open topology on continuous functions (the topology induced by the weakest representation making evaluation computable). The paper also proves that the halting set is dense, analyzes the linear escape problem via a compactification reduction, and relates the quadratic family to the Mandelbrot set, giving a conditional alternative proof of Hertling's result subject to the density of hyperbolicity conjecture.

Significance. If the results hold, the paper gives a clean characterization of what is decidable about the escape problem for arbitrary continuous maps under a natural perturbation topology: the maximal partial decision method is exactly the search for robust invariants, and every non-robust instance is a genuine decision-boundary instance. This is a strong and surprising result, and the extension to affine linear systems and to the quadratic family shows that the general algorithm can compete with bespoke methods. The paper is also careful about the modeling assumptions: the compact-open topology is explicitly identified as the source of the notion of robustness, and the conditional nature of the Mandelbrot application is stated clearly. The main theorems are proved in detail in the appendices, and the central perturbation argument (Lemma 13) is substantial and, in substance, correct. The density result (Lemma 16 and Corollary 17) is an additional nice contribution.

major comments (2)
  1. [Lemma 14 (main text, Section 3.1)] The proof of Lemma 14 invokes Lemma 13 on compact sets K_n and C_n with only the assumption x0 in K_n (or x0 in C_n), but Lemma 13 requires x0 to lie in the interior of the compact set. When x0 lies on the boundary of A, no compact subset of A can contain x0 in its interior, so the invocation is unjustified as written. The statement is likely true and repairable—for the first part one may enlarge K_n with a small ball around x0 and take A_n to be that enlarged compact set, and for the fixed-A part one must argue via modifications supported outside [-2^n,2^n]^d—but the current proof does not supply this argument. Since Theorem 15 depends directly on Lemma 14, this gap is load-bearing and should be fixed.
  2. [Appendix B, Lemma 29] The written proof of Lemma 29 contains a logical inversion: from the claim that for each i there exists j with x_j in B(E_i, delta/2) and no earlier B(E_k, delta/2) containing x_j, the text concludes 'Hence, for all j there exists i' with x_j in B(E_i, delta/2). That inference is not valid. The lemma itself is true, and the intended argument is a pigeonhole principle: the sets B(E_i, delta/2) are pairwise disjoint, so an infinite sequence would require infinitely many distinct points x_j among finitely many candidates. The proof should be rewritten accordingly.
minor comments (6)
  1. [Theorem 15, item 3] The statement says 'with I ⊆ A^o'; the symbol I should be V, the robust invariant introduced in the preceding clause.
  2. [Theorem 15, item 4] The phrase 'fi,n → fn for i = 0,1' should read 'fi,n → f for i = 0,1', and the sequences A0,n and A1,n are not defined; the text should specify that A0,n = A1,n = A_n in the general case and A0,n = A1,n = A in the fixed-A case.
  3. [Lemma 14, second half] The justification of convergence fn → f is too terse: the displayed inequality only controls the sup-norm on C_n, which is not enough for the compact-open topology. The intended argument is that the modification is supported outside [-2^n,2^n]^d, so on every fixed B(0,2^m) the functions fn agree with gn for all n >= m and ||gn - f|| on that ball tends to zero. This should be stated explicitly.
  4. [Lemma 5] The proof uses F_n in the statement but discusses F_m and F_n interchangeably; the indexing should be fixed to avoid confusion.
  5. [Section 5, Theorem 22] In the non-hyperbolic case, the proof asserts that an unbounded orbit disjoint from K_c with 0 in K_c admits a uniform lower bound delta with |f_c^n(z_epsilon)| > delta for all n. This is true because an escaping orbit eventually leaves every compact set and has only finitely many early iterates, but the argument should be spelled out, since the current one-line justification is too compressed.
  6. [Appendix D, Lemma 19] The proof refers to 'routine exercise' derivations of effective bounds in cases 1--3. Since these bounds are used to justify robustness, it would be helpful to state at least the form of the bounds or cite the corresponding lemmas in [25] more precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the completeness theorem is proved from stated definitions and explicit perturbation lemmas; self-citations are not load-bearing.

full rationale

The paper's central derivation is self-contained. Definition 9 fixes the Point Escape Problem; Algorithm 1 searches either for an escape witness or for a dyadic orbit-inclusion with f(|O|) subset of |O| and |O| subset of the interior of A; Proposition 10 proves correctness directly from the over-approximation invariants; Proposition 12 proves termination on escaping instances and on trapped instances admitting a robust invariant; Lemmas 13 and 14 construct explicit perturbations f_n -> f and A_n -> A (or A_n = A) when no robust invariant V with f(x0) in V^o subset V subset A^o exists, so non-halting is shown to imply decision-boundary membership; Theorem 15 then assembles the completeness statement. The notion 'robust invariant' (Definition 11) is purely topological (f(V) subset of V^o) and is not defined in terms of Algorithm 1's output, and the perturbation construction in Appendix B does not invoke the algorithm, so there is no self-definitional or fitted-input circle. The only self-citation is [25, Proposition 2.1] for the equivalence between 'halts on all robust instances' and 'halting set contains every sound decision method's halting set'; Section 2.2 states this as framework and the main theorem is proved directly as halting-set-equals-robust-instances, so the citation is not load-bearing. Section 4 explicitly flags the modeling choice of the weakest function representation (compact-open topology), which narrows the robust instances; a modeling limitation is not circularity. The Mandelbrot application is explicitly conditional on the hyperbolicity conjecture and uses external results (Fatou, Douady-Hubbard, Hertling), so it does not smuggle its conclusion. A minor presentation gap in the written proof of Lemma 29 (a garbled 'Hence' step) does not affect the argument, since the lemma is true by a straightforward pigeonhole argument.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim relies on standard computable analysis and topology, on a prior result by the same author (the completeness-robustness equivalence), and, for the quadratic application, on an external complex dynamics theorem and the unproven hyperbolicity conjecture. No parameters are fitted to data and no new entities are introduced.

assumptions (5)
  • domain assumption The equivalence between completeness of a decision method and halting on all robust instances holds for open representations (Proposition 2.1 of [25], sketched in Section 2.2).
    This underpins the definition of completeness used throughout; it is a prior result by the same author, but also sketched in Section 2.2.
  • standard math The representations of points, continuous functions, and closed sets (Definitions 1, 3, 6) are open and admissible with the stated topologies.
    Proven in Appendix A (Propositions 26-28). This is a technical prerequisite for the robustness characterization.
  • standard math Classical mathematical analysis: Bolzano-Weierstrass, compactness, uniform continuity, Jordan normal form.
    Used throughout the appendix proofs, e.g., Lemma 13 and Appendix D.
  • domain assumption Douady-Hubbard theorem: if c is in a non-hyperbolic component of the interior of the Mandelbrot set, then c lies in K_c = ∂K_c.
    Invoked in the proof of Theorem 22 as [15]; this is an external theorem in complex dynamics.
  • domain assumption Density of hyperbolicity conjecture (conditional).
    The quadratic family completeness is conditional on this conjecture; the paper states this explicitly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space." pith.science (2026). https://pith.science/paper/2VWMZQVP

@misc{pith2026250621481,
  author       = {Pith},
  title        = {Pith review of: Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2VWMZQVP}},
  note         = {Machine review of arXiv:2506.21481}
}
abstract

We study the problem of deciding whether a point escapes a closed subset of $\mathbb{R}^d$ under the iteration of a continuous map $f \colon \mathbb{R}^d \to \mathbb{R}^d$ in the bit-model of real computation. We give a sound partial decision method for this problem which is complete in the sense that its halting set contains the halting set of all sound partial decision methods for the problem. Equivalently, our decision method terminates on all problem instances whose answer is robust under all sufficiently small perturbations of the function. We further show that the halting set of our algorithm is dense in the set of all problem instances. While our algorithm applies to general continuous functions, we demonstrate that it also yields complete decision methods for much more rigid function families: affine linear systems and quadratic complex polynomials. In the latter case, completeness is subject to the density of hyperbolicity conjecture in complex dynamics. This in particular yields an alternative proof of Hertling's (2004) conditional answer to a question raised by Penrose (1989) regarding the computability of the Mandelbrot set.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

  1. [1]

    fi agrees with f outside Si−1 j=0 B(x j, δ

    work page

  2. [2]

    On Positivity and Minimality for Second-Order Holonomic Sequences

    URL: http://dx.doi.org/10.1002/malq.200310124, doi:10.1002/malq.200310124. 18 Mathieu Hoyrup and Cristóbal Rojas. On the Information Carried by Programs About the Objects they Compute. Theor. Comp. Sys., 61(4):1214–1236, November 2017. doi:10.1007/ s00224-016-9726-9 . 19 Manuel Kauers and Veronika Pillwein. When can we detect that a P-finite sequence is p...

    work page Pith review arXiv

  3. [3]

    Ei ⊆ K for all i ≥ 1

    work page

  4. [4]

    contains x j andSi−1 k=0 B(Ek, δ

    work page

  5. [5]

    Indeed, since Ei is non-empty, it contains a point x

    does not contain x j. Indeed, since Ei is non-empty, it contains a point x. There must exist a point x j satisfying d(x, x j) < δ/2. If B(Ek, δ

    work page

  6. [6]

    It follows that d(y, x) < δ, contradicting the assumption that Ei is disjoint from B(Ek, δ)

    with k < i contains x j, then there exists y ∈ Ek with d(y, x j) < δ/2. It follows that d(y, x) < δ, contradicting the assumption that Ei is disjoint from B(Ek, δ). Hence, for all j ∈ {1,..., N} there exists i ∈ {1,..., N} such that x j ∈ B(Ei, δ 2). We obtain N[ i=1 B(Ei, δ) ⊇ N[ i=1 B(xi, δ

    work page

  7. [7]

    Now, EN+1 is required to be a non-empty subset of K, disjoint from K

    ⊇ K. Now, EN+1 is required to be a non-empty subset of K, disjoint from K. Contradiction! Î Ï Proposition 30. Let A ⊆ Rd be a closed set. Let U1,..., Um ⊆ Rd be open sets. Then the complement of the interior of A \ Sm i=1Ui in A is equal to A ∩ Sm i=1U i. Proof. If a point is contained in Sm i=1U i, then it cannot be an interior point of A \ Sm i=1Ui, sin...

    work page

  8. [8]

    x0 ∉ B(Ei, δ) for i < N

    work page

Show all 24 references
  1. [10]

    Ei is disjoint from Si−1 j=0 B(E j, δ) for all i

  2. [11]

    Suppose we have constructed E0,..., Em as above with x0 ∉ B(Ei, δ) for i = 0,..., m

    If N ≥ i +1 and x ∈ K \ Si j=0 B(E j, δ), then f (x) ∈ B(Ei, δ) if and only if x ∈ Ei+1. Suppose we have constructed E0,..., Em as above with x0 ∉ B(Ei, δ) for i = 0,..., m. To construct Em+1, consider the closed set A = K \ Sm i=0 B(Ei, δ). This set is non-empty, since it con...

  3. [13]

    for all i ∈ {1,..., N}

  4. [14]

    fi agrees with fi−1 on Si−2 j=0 B(x j, δ

  5. [15]

    for all i ∈ {2,..., N}

  6. [16]

    ||fi − f ||∞ < ε for all i ∈ {1,..., N}

  7. [17]

    fi(xi−1) = xi for all i ∈ {1,..., N}

  8. [18]

    xi ∈ EN−i for all i ∈ {1,..., N}

  9. [19]

    Observe that the balls B(x j, δ

    xN ∉ K. Observe that the balls B(x j, δ

  10. [20]

    Indeed, if j > k > 0 we have x j ∈ EN− j and xk ∈ EN−k, so that d(x j, xk) ≥ δ by the third property of the Eis

    are disjoint for 0 ≤ j < N. Indeed, if j > k > 0 we have x j ∈ EN− j and xk ∈ EN−k, so that d(x j, xk) ≥ δ by the third property of the Eis. Further, we have x0 ∉ B(EN− j, δ) for all j > 0 by the second property of the Eis. Hence, d(x0, x j) > δ for all j > 0. It then follows ...

  11. [21]

    There is no real eigenvalue ≥ 1

  12. [22]

    The largest real eigenvalue is ≥ 1 but is not simple or not strictly greater than all other eigenvalues

  13. [23]

    The largest real eigenvalue is simple, greater than all other eigenvalues, and equal to 1, but all eigenvectors v for ρ satisfy v ∉ P◦ 0 or in the decompositions x0 = αv+w and b = βv+u as above we have α ≤ 0 or β ≤ 0

  14. [24]

    We claim that the instance is not robustly trapped in any of the above cases

    The largest real eigenvalue ρ is simple, greater than all other eigenvalues, strictly greater than 1, but all eigenvectors v for ρ satisfy v ∉ P◦ 0 or in the decomposition x0 = αv + w as above we have α ≤ 0. We claim that the instance is not robustly trapped in any of the abov...

  15. [2005]

    7 Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale

    doi:10.1137/S0097539703425861. 7 Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and Real Computation. Springer, 1998. 8 Lenore Blum and Steve Smale. The Gödel Incompleteness Theorem and Decidability over a Ring, pages 321–339. Springer US, New York, NY, ...

    1998 doi

  16. [2014]

    29 Joël Ouaknine and James Worrell

    doi:10.1137/1.9781611973402.27. 29 Joël Ouaknine and James Worrell. Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st Intern...

    arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.