MODNET
Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1437

Preprint Number 1437

Previous Next Preprint server


1437. Philipp Hieronymi, Danny Nguyen, Igor Pak
Presburger Arithmetic with algebraic scalar multiplications
E-mail:

Submission date: 9 May 2018

Abstract:

We study complexity of integer sentences in S_α=( ℝ , < , + , ℤ , x↦ αx), which is known to be decidable for quadratic α, and undecidable for non-quadratic irrationals. When α is quadratic and the sentence has r alternating quantifier blocks, we prove both lower and upper bounds as towers of height (r-3) and r, respectively. We also show that for α non-quadratic, already r=4 alternating quantifier blocks suffice for undecidability.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1805.03624: pdf, ps.


Last updated: June 12 2018 15:35 Please send your corrections to: