On the decidability of Presburger arithmetic expanded with powers
<p>We prove that for any integers α, β > 1, the existential fragment of the first-order theory of the structure ⟨Z; 0, 1, <, +, αN, βN⟩ is decidable (where α N is the set of positive integer powers of α, and likewise for &...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2025
|
| _version_ | 1826317125156864000 |
|---|---|
| author | Karimov, T Luca, F Nieuwveld, J Ouaknine, J Worrell, J |
| author_facet | Karimov, T Luca, F Nieuwveld, J Ouaknine, J Worrell, J |
| author_sort | Karimov, T |
| collection | OXFORD |
| description | <p>We prove that for any integers α, β > 1, the existential fragment of the first-order theory of the structure ⟨Z; 0, 1, <, +, αN, βN⟩ is decidable (where α N is the set of positive integer powers of α, and likewise for β N). On the other hand, we show by way of hardness that decidability of the existential fragment of the theory of ⟨N; 0, 1, <, +, x 7→ α x , x 7→ β x ⟩ for any multiplicatively independent α, β > 1 would lead to mathematical breakthroughs regarding base-α and base-β expansions of certain transcendental numbers.</p> |
| first_indexed | 2024-12-09T03:18:58Z |
| format | Conference item |
| id | oxford-uuid:aa896e4c-216a-4eb9-b834-634f887f8bb7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2025-02-19T04:33:33Z |
| publishDate | 2025 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:aa896e4c-216a-4eb9-b834-634f887f8bb72025-01-16T09:37:26ZOn the decidability of Presburger arithmetic expanded with powersConference itemhttp://purl.org/coar/resource_type/c_5794uuid:aa896e4c-216a-4eb9-b834-634f887f8bb7EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2025Karimov, TLuca, FNieuwveld, JOuaknine, JWorrell, J<p>We prove that for any integers α, β > 1, the existential fragment of the first-order theory of the structure ⟨Z; 0, 1, <, +, αN, βN⟩ is decidable (where α N is the set of positive integer powers of α, and likewise for β N). On the other hand, we show by way of hardness that decidability of the existential fragment of the theory of ⟨N; 0, 1, <, +, x 7→ α x , x 7→ β x ⟩ for any multiplicatively independent α, β > 1 would lead to mathematical breakthroughs regarding base-α and base-β expansions of certain transcendental numbers.</p> |
| spellingShingle | Karimov, T Luca, F Nieuwveld, J Ouaknine, J Worrell, J On the decidability of Presburger arithmetic expanded with powers |
| title | On the decidability of Presburger arithmetic expanded with powers |
| title_full | On the decidability of Presburger arithmetic expanded with powers |
| title_fullStr | On the decidability of Presburger arithmetic expanded with powers |
| title_full_unstemmed | On the decidability of Presburger arithmetic expanded with powers |
| title_short | On the decidability of Presburger arithmetic expanded with powers |
| title_sort | on the decidability of presburger arithmetic expanded with powers |
| work_keys_str_mv | AT karimovt onthedecidabilityofpresburgerarithmeticexpandedwithpowers AT lucaf onthedecidabilityofpresburgerarithmeticexpandedwithpowers AT nieuwveldj onthedecidabilityofpresburgerarithmeticexpandedwithpowers AT ouakninej onthedecidabilityofpresburgerarithmeticexpandedwithpowers AT worrellj onthedecidabilityofpresburgerarithmeticexpandedwithpowers |