On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number".
Jane: Here's the gist of the paper. This paper investigates extensions of the existential theory of the reals by incorporating an additional unary predicate, R(xi Z), which denotes integer powers of a fixed computable real number xi > 0.
Tom: The decidability and complexity results for this theory depend critically on the nature of xi.
Jane: The satisfiability problem for R(xi Z) is generally undecidable if only a Turing machine computing xi is available.
Tom: However, an algorithm to decide satisfiability exists under specific conditions related to the algebraicity of xi.
Paper summary: Tom: We started by looking at extending the existential theory of real numbers by adding this new unary predicate, which we call xi Z. This is about integer powers of a fixed computable real number xi that’s greater than zero.
Jane: So the main claim is that if you only have a Turing machine that can compute xi, you generally can't decide whether a formula in this new theory is satisfiable. But they show there are specific conditions where it becomes decidable.
Lu: The key insight they give is that knowing the algebraicity of xi is enough to bypass the undecidability issue. If xi has an algebraic representation, the problem falls into ExpSpace complexity.
Meng: That’s a big win for certainty, right? So if we can prove something about a real number using this structure and it happens to be algebraic, we have a solvable path.
Tom: Right, but if xi is transcendental—like pi or e—the problem gets harder again. In that case, the complexity jumps to 3Exp <ref:2502.02220#pg3>. It’s not immediately decidable without more information about xi itself.
Jane: So the paper essentially sets up a spectrum of difficulty based on what kind of number you are working with, from NExpTime up to 3Exp for specific transcendental numbers <ref:2502.02220#pg3>.
Lu: And they also show that if xi is a computable transcendental number, an effective procedure exists, but it requires you to have a Turing machine that computes xi in unary form. That’s a very specific requirement on the input data.
Meng: That unary form requirement makes sense from an engineering standpoint; you need to be able to reliably represent that number for the algorithm to run even in its worst-case scenario.
Tom: And they establish complexity results under a proviso called a polynomial root barrier, which is how they manage those transcendental cases. This barrier dictates the complexity guarantees they can provide for those numbers like pi or e pi.
Jane: It matters because it gives us concrete complexity classes to discuss, moving beyond just saying "it's undecidable." We can now say "if xi is algebraic, we are in ExpSpace."
Lu: That’s the power of this work. They provide a formal way to categorize the computational difficulty based on the number theory of xi.
Meng: It moves it from abstract math into a framework where we can actually estimate resource needs for verification tasks, even if those estimates are just theoretical upper bounds.
Tom: So, in short, they’re mapping the problem onto the properties of xi to determine its computational cost. This is how they make sense of the complexity landscape.
Jane: And that sets us up perfectly for talking about what this actually means for applications outside of pure number theory and AI research.
Conclusion: Tom: So, looking at this paper, "On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number," it’s really about structuring a mathematical problem around the properties of a specific real number xi.
Jane: It’s about showing that if you add this power predicate to the theory of reals, your ability to solve satisfiability depends entirely on whether xi is natural, algebraic, or transcendental.
Lu: The authors provide this classification: natural numbers give NExpTime, algebraic numbers give ExpSpace, and certain transcendental families land in 3Exp complexity <ref:2502.02220#pg3>.
Meng: It means for us in production AI environments, we need to know what kind of number we are dealing with to estimate the computational cost of verifying related mathematical properties.
Tom: The implication is that for some types of numbers, like algebraic ones, verification is theoretically bounded by ExpSpace, which is a known class.
Jane: And for others, like computable transcendentals with a root barrier, they give you an algorithm that runs in non-deterministic exponential time. That’s the practical reality of what's possible right now.
Lu: The work also links this to stochastic games, showing that problems there are decidable in ExpTime even when the base is e or algebraic and the aversion factor is fixed algebraically.
Meng: So it gives us a consistent complexity ceiling for verifying these
IMDEA Software Institute · Universidad Politécnica de Madrid
cs.LO
Submitted: 2025-02-04
Updated: 2026-11-13
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 78/100
The gist: This paper investigates extensions of the existential theory of the reals by incorporating an additional unary predicate, R(xi Z)…
Key concepts
- Existential Theory of the Reals
- This is a mathematical theory dealing with properties and relationships within the set of real numbers. It provides a framework for studying how statements about real numbers can be true or false, often using logical quantifiers to describe these properties.
- $\exists R(\xi Z)$ Predicate
- This new addition to the theory checks if an integer power of a specific computable real number $\xi$ exists. It essentially asks whether there is some integer $Z$ such that $\xi^Z$ satisfies a certain condition, linking the theory to the properties of powers of $\xi$.
- Algebraic vs. Transcendental Numbers
- This classification determines the complexity results. Algebraic numbers are those that are roots of non-zero integer polynomials, while transcendental numbers are real numbers that cannot be expressed as such roots. This distinction dictates whether the satisfiability problem is decidable or not.
- Complexity Classes (NExpTime, ExpSpace)
- These terms describe how hard it is computationally to solve problems related to the theory. NExpTime and ExpSpace are specific complexity classes that tell us the resources (time or space) needed by algorithms to determine if a statement in this enriched theory is true.
Terminology
Summary
This paper investigates extensions of the existential theory of the reals by incorporating an additional unary predicate, R(xi Z), which denotes integer powers of a fixed computable real number xi > 0. p. 0 org
Abstract. This paper investigates the extension of the existential theory of the reals
by an additional unary predicate ξ
Z
for the integer powers of a fixed computable real
number ξ > 0. Our complexity results are shown by relying on well-established
machinery from Diophantine approximation and transcendental number theory, such as
bounds for the transcendence measure of numbers. As a by-product of our results, we are able to remove the appeal to Schanuel’s conjecture
from the proof of decidability of the entropic risk threshold problem for stochastic games
with rational probabilities, rewards, and threshold [Baier et al.Where the paper says it
Where the paper says it
The satisfiability problem for R(xi Z) is generally undecidable if only a Turing machine computing xi is available. p. 0 If all we have access to is a Turing
machine computing ξ, it is not possible to decide whether an input formula from this theory
is satisfiable. However, we show an algorithm to decide this problem when
• ξ is known to be transcendental, or
• ξ is a root of some given integer polynomial (that is, ξ is algebraic). However, we show an algorithm to decide this problem when
• ξ is known to be transcendental, or
• ξ is a root of some given integer polynomial (that is, ξ is algebraic). In other words, knowing the algebraicity of ξ suffices to circumvent undecidability. If all we have access to is a Turing
machine computing ξ, it is not possible to decide whether an input formula from this theory
is satisfiable. However, we show an algorithm to decide this problem when
• ξ is known to be transcendental, or
• ξ is a root of some given integer polynomial (that is, ξ is algebraic).Where the paper says it
Where the paper says it
Where the paper says it
The complexity results established are contingent upon whether xi falls into different categories:
-
If xi is a natural number, the satisfiability problem is in NExpTime. p. 0
Where the paper says it
Furthermore, we establish complexity results under the proviso that ξ enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of ∃R(ξ Z ) • is in NExpTime if ξ is a natural number, • is in ExpSpace if ξ is an algebraic number, and • is in 3Exp if ξ belongs to a family of transcendental numbers including π and Euler’s e.
-
If xi is an algebraic number, it is in ExpSpace. p. 0
Where the paper says it
Furthermore, we establish complexity results under the proviso that ξ enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of ∃R(ξ Z ) • is in NExpTime if ξ is a natural number, • is in ExpSpace if ξ is an algebraic number, and • is in 3Exp if ξ belongs to a family of transcendental numbers including π and Euler’s e.
-
If xi belongs to a family of transcendental numbers, such as pi and e, the problem resides in 3Exp. p. 0
Where the paper says it
Furthermore, we establish complexity results under the proviso that ξ enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of ∃R(ξ Z ) • is in NExpTime if ξ is a natural number, • is in ExpSpace if ξ is an algebraic number, and • is in 3Exp if ξ belongs to a family of transcendental numbers including π and Euler’s e.
The proof strategy involves reducing the satisfiability problem of R(xi Z) to solving quantifier-free instances of the theory of the reals where variables range over xi Z. p. 0 Using this notion, we show that the satisfiability problem of ∃R(ξ
Z
)
• is in NExpTime if ξ is a natural number,
• is in ExpSpace if ξ is an algebraic number, and
• is in 3Exp if ξ belongs to a family of transcendental numbers including π and Euler’s e. To establish our results, we first observe that the satisfiability problem of ∃R(ξ
Z
) reduces
in exponential time to the problem of solving quantifier-free instances of the theory of
the reals where variables range over ξ
Z
. To establish our results, we first observe that the satisfiability problem of ∃R(ξ
Z
) reduces
in exponential time to the problem of solving quantifier-free instances of the theory of
the reals where variables range over ξ
Z
. We then prove that these instances have a small
witness property: only finitely many integer powers of ξ must be considered to find whether
a formula is satisfiable. We then prove that these instances have a small
witness property: only finitely many integer powers of ξ must be considered to find whether
a formula is satisfiable. Our complexity results are shown by relying on well-established
machinery from Diophantine approximation and transcendental number theory, such as
bounds for the transcendence measure of numbers.Where the paper says it
Where the paper says it
Where the paper says it
The paper also details an algorithm for deciding R(xi Z) when xi is a computable number that is either transcendental or possesses a polynomial root barrier, showing it runs in non-deterministic exponential time due to necessary guesses. p. 6 Once more, we stress the fact that this representation is only used for algebraic numbers
that are fixed, and so the above refinement of ℓ and u takes constant time. An algorithm for deciding ∃R(ξ
Z)
Fix a computable number ξ > 0 that is either transcendental or has a polynomial root barrier. This procedure provides a partial answer to the question raised in [AY07] regarding the
complexity of removing a single existential variable in Tarski arithmetic extended with 2
Z:
within sentences of the existential fragment, such an elimination step can be performed in
elementary time. Coming back to our initial question on identifying computational tasks that might not
need the full power of R(e
x
), as a by-product of our results we show that the entropic risk
threshold problem for stochastic games studied by Baier, Chatterjee, Meggendorfer and
Piribauer [BCMP23] is unconditionally decidable in ExpTime even when the base of the
entropic risk is e (or algebraic) and the aversion factor is any (fixed) algebraic number.Where the paper says it
Where the paper says it
The overall theorem summarizes these complexity results based on whether xi is a natural number, algebraic, or transcendental. p. 0 Furthermore, we establish complexity results under the proviso that ξ enjoys what we call a
polynomial root barrier. Using this notion, we show that the satisfiability problem of ∃R(ξ
Z
)
• is in NExpTime if ξ is a natural number,
• is in ExpSpace if ξ is an algebraic number, and
• is in 3Exp if ξ belongs to a family of transcendental numbers including π and Euler’s e. To establish our results, we first observe that the satisfiability problem of ∃R(ξ
Z
) reduces
in exponential time to the problem of solving quantifier-free instances of the theory of
the reals where variables range over ξ
Z
. We then prove that these instances have a small
witness property: only finitely many integer powers of ξ must be considered to find whether
a formula is satisfiable.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Decision procedures for existential theories extended with integer powers of a computable number can be effectively implemented when the base number is known to be transcendental or algebraic, providing complexity bounds such as NExpTime for natural numbers and ExpSpace for algebraic numbers.
-
The satisfiability problem of ∃R(xiZ) can be solved in 3Exp if xi belongs to a family of transcendental numbers including pi and Euler’s e, which is achievable by leveraging polynomial root barriers.
-
A procedure exists to remove the appeal to Schanuel’s conjecture from proofs in areas like stochastic games, making certain problems unconditionally decidable in ExpTime when the base is e and the aversion factor is algebraic.
-
The satisfiability problem for ∃R(xiZ) can be solved for a computable transcendental number xi by relying on the fast-convergence sequence of rational numbers to find an appropriate witness, although this process has an unbounded asymptotic running time.
-
For algebraic numbers xi, a polynomial-time Turing machine can be constructed to compute xi by performing a dichotomy search to refine the interval representation of xi until an accurate rational approximation is found within a required error bound.
Abstract
This paper investigates R(r Z), that is the extension of the existential theory of the reals by an additional unary predicate r Z for the integer powers of a fixed computable real number r > 0. If all we have access to is a Turing machine computing r, it is not possible to decide whether an input formula from this theory satisfiable. However, we show an algorithm to decide this problem when: 1. r is known to be transcendental, or 2. r is a root of some given integer polynomial (that is, r is algebraic). In other words, knowing the algebraicity of r suffices to circumvent undecidability. Furthermore, we establish complexity results under the proviso that r enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of R(r Z) is 1. in NEXPTIME if r is a natural number, 2. in EXPSPACE if r is an algebraic number, and 3. in 3EXP if r belongs to a family of transcendental numbers including π and Euler's e. As a by-product of our results, we are able to remove the appeal to Schanuel's conjecture from the proof of decidability of the entropic risk threshold problem for stochastic games with rational probabilities, rewards and threshold [Baier et al., MFCS'23]: when the base of the entropic risk is Euler's e and the aversion factor is a fixed algebraic number, the problem is in EXP.
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring