On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number
summary
The gist
This paper investigates extensions of the existential theory of the reals by incorporating an additional unary predicate, R(xi Z)…
In short
The paper explores adding a predicate to real numbers called $\exists R(\xi Z)$, which checks for integer powers of a fixed computable real number $\xi$. The decidability and computational complexity of this system depend entirely on whether $\xi$ is algebraic or transcendental, leading to different complexity classes like NExpTime or ExpSpace.
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 used across episodes
This episode discusses
- On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number · Paper Radio
The paper
On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number · Read on arXiv
IMDEA Software Institute · Universidad Politécnica de Madrid
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.
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
More episodes
- 2411.16152-Optimizing Winograd Convolution on ARMv8 processors
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines