TY - JOUR

T1 - Presburger arithmetic with algebraic scalar multiplications

AU - Hieronymi, Philipp

AU - Nguyen, Danny

AU - Pak, Igor

N1 - Funding Information:
We are grateful to Matthias Aschenbrenner, Sasha Barvinok, Tristram Bogart, Artëm Chernikov, Jesús De Loera, Fritz Eisenbrand, John Goodrick, Robert Hildebrand, Ravi Kannan, Matthias Köppe, and Kevin Woods for interesting conversations and helpful remarks. We thank Eion Blanchard, Madie Farris and Ran Ji for closely reading an earlier draft of this manuscript. This work was finished while the last two authors were in residence of the MSRI long term Combinatorics program in the Fall of 2017; we thank MSRI for the hospitality. The first author was partially supported by NSF Grant DMS-1654725. The second author was partially supported by the UCLA Dissertation Year Fellowship. The third author was partially supported by the NSF.
Publisher Copyright:
© P. Hieronymi, D. Nguyen, and I. Pak.

PY - 2021

Y1 - 2021

N2 - 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 ∃6∀4∃11 α-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.

AB - 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 ∃6∀4∃11 α-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.

UR - http://www.scopus.com/inward/record.url?scp=85112129211&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85112129211&partnerID=8YFLogxK

U2 - 10.46298/LMCS-17(3:4)2021

DO - 10.46298/LMCS-17(3:4)2021

M3 - Article

AN - SCOPUS:85112129211

SN - 1860-5974

VL - 17

SP - 4:1-4:34

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

IS - 3

ER -