On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number

arXiv:2502.02220 · cs.LO · Submitted 2025-02-04 · Read on arXiv

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

Where the paper says it

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.

The decidability and complexity results for this theory depend critically on the nature of xi. p. 0
Where the paper says it

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.

The satisfiability problem for R(xi Z) is generally undecidable if only a Turing machine computing xi is available. p. 0

Where the paper says it

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, an algorithm to decide satisfiability exists under specific conditions related to the algebraicity of xi. p. 0
Where the paper says it

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 xi is known to be transcendental, or if 1/xi is a root of some given integer polynomial (meaning xi is algebraic), the problem becomes decidable. p. 0
Where the paper says it

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).

The complexity results established are contingent upon whether xi falls into different categories:

  1. 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.

  2. 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.

  3. 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

Where the paper says it

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 .

A key finding is that a small witness property holds: only finitely many integer powers of xi need to be considered to determine formula satisfiability. p. 0
Where the paper says it

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.

The complexity analysis relies on established machinery from Diophantine approximation and transcendental number theory, specifically bounds for transcendence measures. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

Furthermore, the study connects this work to related problems in stochastic games; the satisfiability problem for stochastic games studied by Baier, Chatterjee, Meggendorfer and Piribauer [BCMP23] is shown to be 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. p. 2
Where the paper says it

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.

The overall theorem summarizes these complexity results based on whether xi is a natural number, algebraic, or transcendental. 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 core proof structure utilizes quantifier elimination procedures for the theory of the reals and a method to identify finite sets of integer powers that serve as witnesses for satisfiability. p. 0
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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