On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918506567565312 |
|---|---|
| author | Bacik, Piotr Nieuwveld, Joris Ouaknine, Joël Vahanwala, Mihir Venkatesh, Madhavan Wieser, Emil Rugaard |
| author_facet | Bacik, Piotr Nieuwveld, Joris Ouaknine, Joël Vahanwala, Mihir Venkatesh, Madhavan Wieser, Emil Rugaard |
| contents | We consider expansions of Presburger arithmetic with families of monadic polynomial predicates. (Examples of such predicates are the set of perfect squares, or the set of integers of the form $2n^3-5n+3$, etc.) Although the full attendant first-order theories are well known to be undecidable, very little is known when one restricts the number of variables. In the case of single-variable theories, we obtain positive results for the following two families of predicates: (i) for perfect fixed powers, decidability ofthe corresponding theory follows from the solvability of hyperellipticDiophantine equations; and (ii) for polynomials of degree at most three, we establish decidability by relying on the low genus of the resulting algebraic curves. Finally, we discuss limitations and hardness results (via encodings of longstanding open Diophantine problems) as soon as any of the above restrictions are lifted. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_16985 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic Bacik, Piotr Nieuwveld, Joris Ouaknine, Joël Vahanwala, Mihir Venkatesh, Madhavan Wieser, Emil Rugaard Logic in Computer Science 03D99 (Primary), 11D99 (Secondary) F.4.1; F.4.3 We consider expansions of Presburger arithmetic with families of monadic polynomial predicates. (Examples of such predicates are the set of perfect squares, or the set of integers of the form $2n^3-5n+3$, etc.) Although the full attendant first-order theories are well known to be undecidable, very little is known when one restricts the number of variables. In the case of single-variable theories, we obtain positive results for the following two families of predicates: (i) for perfect fixed powers, decidability ofthe corresponding theory follows from the solvability of hyperellipticDiophantine equations; and (ii) for polynomials of degree at most three, we establish decidability by relying on the low genus of the resulting algebraic curves. Finally, we discuss limitations and hardness results (via encodings of longstanding open Diophantine problems) as soon as any of the above restrictions are lifted. |
| title | On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic |
| topic | Logic in Computer Science 03D99 (Primary), 11D99 (Secondary) F.4.1; F.4.3 |
| url | https://arxiv.org/abs/2605.16985 |