Presburger arithmetic with algebraic scalar multiplications

Philipp Hieronymi, Danny Nguyen, Igor Pak

Research output: Contribution to journalArticlepeer-review


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 22…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 ∃6411 α-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.

Original languageEnglish (US)
Pages (from-to)4:1-4:34
JournalLogical Methods in Computer Science
Issue number3
StatePublished - 2021

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Presburger arithmetic with algebraic scalar multiplications'. Together they form a unique fingerprint.

Cite this