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.