Presburger arithmetic with algebraic scalar multiplications

We consider Presburger arithmetic (PA) extended by scalar multiplication by an algebraic irrational number α, and call this extension α-Presburger arithmetic (α-PA). We show that the complexity of deciding sentences in α-PA is substantially harder than in PA. Indeed, when α is quadratic and r ≥ 4, deciding α-PA sentences with r alternating quantifier blocks and at most c r variables and inequalities requires space at least K 2^2…2Cℓ(S) ( tower of height r − 3 ), where the constants c, K, C > 0 only depend on α, and ℓ(S) is the length of the given α-PA sentence S. Furthermore deciding ∃⁶∀⁴∃¹¹ α-PA sentences with at most k inequalities is PSPACE-hard, where k is another constant depending only on α. When α is non-quadratic, already four alternating quantifier blocks suffice for undecidability of α-PA sentences.